Return to pa_hash.h CVS log

Up to [parser3project] / parser3 / src / include

continued with Hash

/** @file
	Parser: hash class decl.

	Copyright (c) 2001, 2003 ArtLebedev Group (http://www.artlebedev.com)

	Author: Alexandr Petrosian <paf@design.ru> (http://paf.design.ru)
*/

/*
	The prime numbers used from zend_hash.c,
	the part of Zend scripting engine library,
	Copyrighted (C) 1999-2000    Zend Technologies Ltd.
	http://www.zend.com/license/0_92.txt
	For more information about Zend please visit http://www.zend.com/
*/

#ifndef PA_HASH_H
#define PA_HASH_H

static const char* IDENT_HASH_H="$Date: 2003/01/23 11:37:55 $";

#include "pa_pool.h"
#include "pa_types.h"

/** 
	Simple hash.

	Automatically rehashed when almost is_full.
	Contains no 0 values. 
		get returning 0 means there were no such.
		"put value 0" means "remove"
*/
template<typename K, typename V> class Hash: public PA_Object {
public:

	typename K key_type;
	typename V value_type;

	Hash() { 
		allocated=allocates[allocates_index=0];
		threshold=allocated*THRESHOLD_PERCENT/100;
		fpairs_count=fused_refs=0;
		refs=static_cast<Pair **>(pa_calloc(sizeof(Pair *)*allocated));
	}

	Hash(const Hash& source) {
		allocates_index=source.allocates_index;
		allocated=source.allocated;
		threshold=source.threshold;
		fused_refs=source.fused_refs;
		fpairs_count=source.fpairs_count;
		refs=new Pair*[allocated];
		memcpy(refs, source.refs, sizeof(Pair *)*allocated);
	}
	~Hash() {
		destroy_pairs();
		delete refs;
	}

	/// useful generic hash function
	static uint generic_code(uint aresult, const char *start, uint allocated) {
		uint result=aresult, g;
		const char *end=start+allocated;

		while (start<end) {
			result=(result<<4)+*start++;
			if ((g=(result&0xF0000000))) {
				result=result^(g>>24);
				result=result^g;
			}
		}
		return result;
	}

	/// put a [value] under the [key] @returns existed or not
	bool put(const K key, V value) {
		if(is_full()) 
			expand();

		uint code=key.hash_code();
		uint index=code%allocated;
		Pair **ref=&refs[index];
		for(Pair *pair=*ref; pair; pair=pair->link)
			if(pair->code==code && pair->key==key) {
				// found a pair with the same key
				pair->value=value;
				return true;
			}
		
		// proper pair not found -- create&link_in new pair
		if(!*ref) // root cell were fused_refs?
			fused_refs++; // not, we'll use it and record the fact
		*ref=new Pair(code, key, value, *ref);
		fpairs_count++;
		return false;
	}

	/// remove the [key] @returns existed or not
	bool remove(const K key) {
		uint code=key.hash_code();
		uint index=code%allocated;
		for(Pair **ref=&refs[index]; *ref; ref=&(*ref)->link)
			if((*ref)->code==code && (*ref)->key==key) {
				// found a pair with the same key
				Pair *next=(*ref)->link;
				delete *ref;
				*ref=next;
				--fpairs_count;
				return true;
			}

		return false;
	}

	/// get associated [value] by the [key]
	V get(const K key) const {
		uint code=key.hash_code();
		uint index=code%allocated;
		for(Pair *pair=refs[index]; pair; pair=pair->link)
			if(pair->code==code && pair->key==key)
				return pair->value;
		
		return 0;
	}

	/// put a [value] under the [key] if that [key] existed @returns existed or not
	bool put_replace(const K key, V value) {
		uint code=key.hash_code();
		uint index=code%allocated;
		for(Pair *pair=refs[index]; pair; pair=pair->link)
			if(pair->code==code && pair->key==key) {
				// found a pair with the same key, replacing
				pair->value=value;
				return true;
			}

		// proper pair not found 
		return false;
	}

	/// put a [value] under the [key] if that [key] NOT existed @returns existed or not
	bool put_dont_replace(const K key, V value) {
		if(is_full()) 
			expand();

		uint code=key.hash_code();
		uint index=code%allocated;
		Pair **ref=&refs[index];
		for(Pair *pair=*ref; pair; pair=pair->link)
			if(pair->code==code && pair->key==key) {
				// found a pair with the same key, NOT replacing
				return true;
			}

		// proper pair not found -- create&link_in new pair
		if(!*ref) // root cell were fused_refs?
			fused_refs++; // not, we'll use it and record the fact
		*ref=new Pair(code, key, value, *ref);
		fpairs_count++;
		return false;
	}

	/// put all 'src' values if NO with same key existed
	void merge_dont_replace(const Hash& src) {
		for(int i=0; i<src.allocated; i++)
			for(Pair *pair=src.refs[i]; pair; pair=pair->link)
				put_dont_replace(pair->key, pair->value);
		// MAY:optimize this.allocated==src.allocated case
	}

	void put(const K key, int     value) { put(key, reinterpret_cast<V >(value)); }
	void put(const K key, const String *value) { 
		put(key, static_cast<V >(const_cast<String *>(value))); 
	}

	/// number of elements in hash
	int count() const { return fpairs_count; }

	/// iterate over all pairs
	template<typename I> void for_each(void callback(K, V, I), I info) const {
		Pair **ref=refs;
		for(int index=0; index<allocated; index++)
			for(Pair *pair=*ref++; pair; pair=pair->link)
				callback(pair->key, pair->value, info);
	}

	/// iterate over all pairs, passing references
	template<typename I> void for_each(void callback(K, V&, I), I info) const {
		Pair **ref=refs;
		for(int index=0; index<allocated; index++)
			for(Pair *pair=*ref++; pair; pair=pair->link)
				callback(pair->key, pair->value, info);
	}

	/// iterate over all pairs until condition becomes true, return that element
	template<typename I> V *first_that(bool callback(K, V, I), I info) const {
		Pair **ref=refs;
		for(int index=0; index<allocated; index++)
			for(Pair *pair=*ref++; pair; pair=pair->link)
				if(callback(pair->key, pair->value, info))
					return &pair->value;
		
		return 0;
	}

	/// remove all elements
	void clear() {
		destroy_pairs(); memset(refs, 0, sizeof(*refs)*allocated);
		fpairs_count=fused_refs=0;	
	}

private:

	/// expand when these %% of allocated exausted
	enum {
		THRESHOLD_PERCENT=75
	};

	/// the index of [allocated] in [allocates]
	int allocates_index;

	/// possible [allocates]. prime numbers
	/* Zend comment: Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster */
	static uint allocates[]={
		5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963, 
		16229, 32531, 65407, 130987, 262237, 524521, 1048793, 
		2097397, 4194103, 8388857, 16777447, 33554201, 67108961, 
		134217487, 268435697, 536870683, 1073741621, 2147483399};

	static int allocates_count=sizeof(allocates)/sizeof(uint);

	/// number of allocated pairs
	int allocated;

	/// helper: expanding when fused_refs == threshold
	int threshold;

	/// used pairs
	int fused_refs;

	/// stored pairs total (including those by links)
	int fpairs_count;

	/// pair storage
	class Pair: public PA_Allocated {
		//friend class Hash;

		uint code;
		const K key;
		V value;
		Pair *link;
		
		Pair(uint acode, const K akey, V avalue, Pair *alink) :
			code(acode),
			key(akey),
			value(avalue),
			link(alink) {}
	} **refs;

	/// filled to threshold: needs expanding
	bool is_full() { return fused_refs==threshold; }

	/// allocate larger buffer & rehash
	void expand() {
		int old_allocated=allocated;
		Pair **old_refs=refs;

		// allocated bigger refs array
		allocates_index=allocates_index+1<allocates_count?allocates_index+1:allocates_count-1;
		allocated=allocates[allocates_index];
		threshold=allocated*THRESHOLD_PERCENT/100;
		refs=static_cast<Pair **>(pa_calloc(sizeof(Pair *)*allocated));

		// rehash
		Pair **old_ref=old_refs;
		for(int old_index=0; old_index<old_allocated; old_index++)
			for(Pair *pair=*old_ref++; pair; ) {
				Pair *next=pair->link;

				uint new_index=pair->code%allocated;
				Pair **new_ref=&refs[new_index];
				pair->link=*new_ref;
				*new_ref=pair;

				pair=next;
			}

		delete old_refs;
	}

	void destroy_pairs() {
		Pair **ref=refs;
		for(int index=0; index<allocated; index++) {
			Pair *pair=*ref++; 
			while(pair) {
				Pair *next=pair->link;
				delete pair;
				pair=next;
			}
		}
	}

private: //disabled

	Hash& operator = (const Hash&) { return *this; }
};

///	Auto-object used to temporarily substituting/removing hash values
template <typename K, typename V>
class Temp_hash_value {
	Hash& fhash;
	const K fname;
	V saved_value;
public:
	Temp_hash_value(Hash<K, V>& ahash, const K aname, V avalue) : 
		fhash(ahash),
		fname(aname),
		saved_value(ahash.get(aname)) {
		fhash.put(aname, avalue);
	}
	~Temp_hash_value() { 
		fhash.put(fname, saved_value);
	}
};

#endif