KUDr@3900: /* $Id$ */
KUDr@3900: 
KUDr@3900: #ifndef  HASHTABLE_HPP
KUDr@3900: #define  HASHTABLE_HPP
KUDr@3900: 
KUDr@3900: template <class Titem_>
KUDr@3900: struct CHashTableSlotT
KUDr@3900: {
KUDr@3900: 	typedef typename Titem_::Key Key;          // make Titem_::Key a property of HashTable
KUDr@3900: 
KUDr@3900: 	Titem_*    m_pFirst;
KUDr@3900: 
KUDr@3900: 	CHashTableSlotT() : m_pFirst(NULL) {}
KUDr@3900: 
KUDr@3900: 	/** hash table slot helper - linear search for item with given key through the given blob - const version */
KUDr@3900: 	FORCEINLINE const Titem_& Find(const Key& key) const
KUDr@3900: 	{
KUDr@3900: 		for (const Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {
KUDr@3900: 			if (pItem->GetKey() == key) {
KUDr@3900: 				// we have found the item, return it
KUDr@3900: 				return *pItem;
KUDr@3900: 			}
KUDr@3900: 		}
KUDr@3900: 		return *(Titem_*)NULL;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	/** hash table slot helper - linear search for item with given key through the given blob - non-const version */
KUDr@3900: 	FORCEINLINE Titem_& Find(const Key& key)
KUDr@3900: 	{
KUDr@3900: 		for (Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {
KUDr@3900: 			if (pItem->GetKey() == key) {
KUDr@3900: 				// we have found the item, return it
KUDr@3900: 				return *pItem;
KUDr@3900: 			}
KUDr@3900: 		}
KUDr@3900: 		return *(Titem_*)NULL;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	/** hash table slot helper - add new item to the slot */
KUDr@3900: 	FORCEINLINE void Attach(Titem_& new_item)
KUDr@3900: 	{
KUDr@3900: 		assert(new_item.GetHashNext() == NULL);
KUDr@3900: 		new_item.SetHashNext(m_pFirst);
KUDr@3900: 		m_pFirst = &new_item;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	/** hash table slot helper - remove item from a slot */
KUDr@3900: 	FORCEINLINE bool Detach(Titem_& item_to_remove)
KUDr@3900: 	{
KUDr@3900: 		if (m_pFirst == &item_to_remove) {
KUDr@3900: 			m_pFirst = item_to_remove.GetHashNext();
KUDr@3900: 			item_to_remove.SetHashNext(NULL);
KUDr@3900: 			return true;
KUDr@3900: 		}
KUDr@3900: 		Titem_* pItem = m_pFirst;
KUDr@3900: 		while (true) {
KUDr@3900: 			if (pItem == NULL) {
KUDr@3900: 				return false;
KUDr@3900: 			}
KUDr@3900: 			Titem_* pNextItem = pItem->GetHashNext();
KUDr@3900: 			if (pNextItem == &item_to_remove) break;
KUDr@3900: 			pItem = pNextItem;
KUDr@3900: 		}
KUDr@3900: 		pItem->SetHashNext(item_to_remove.GetHashNext());
KUDr@3900: 		item_to_remove.SetHashNext(NULL);
KUDr@3900: 		return true;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	/** hash table slot helper - remove and return item from a slot */
KUDr@3900: 	FORCEINLINE Titem_& Detach(const Key& key)
KUDr@3900: 	{
KUDr@3900: 		// do we have any items?
KUDr@3900: 		if (m_pFirst == NULL) {
KUDr@3900: 			return *(Titem_*)NULL;
KUDr@3900: 		}
KUDr@3900: 		// is it our first item?
KUDr@3900: 		if (m_pFirst->GetKey() == key) {
KUDr@3900: 			Titem_& ret_item = *m_pFirst;
KUDr@3900: 			m_pFirst = m_pFirst->GetHashNext();
KUDr@3900: 			ret_item.SetHashNext(NULL);
KUDr@3900: 			return ret_item;
KUDr@3900: 		}
KUDr@3900: 		// find it in the following items
KUDr@3900: 		Titem_* pPrev = m_pFirst;
KUDr@3900: 		for (Titem_* pItem = m_pFirst->GetHashNext(); pItem != NULL; pPrev = pItem, pItem = pItem->GetHashNext()) {
KUDr@3900: 			if (pItem->GetKey() == key) {
KUDr@3900: 				// we have found the item, unlink and return it
KUDr@3900: 				pPrev->SetHashNext(pItem->GetHashNext());
KUDr@3900: 				pItem->SetHashNext(NULL);
KUDr@3900: 				return *pItem;
KUDr@3900: 			}
KUDr@3900: 		}
KUDr@3900: 		return *(Titem_*)NULL;
KUDr@3900: 	}
KUDr@3900: };
KUDr@3900: 
KUDr@3900: /** @class CHashTableT<Titem, Thash_bits> - simple hash table
rubidium@4549:  *  of pointers allocated elsewhere.
rubidium@4549:  *
rubidium@4549:  *  Supports: Add/Find/Remove of Titems.
rubidium@4549:  *
rubidium@4549:  *  Your Titem must meet some extra requirements to be CHashTableT
rubidium@4549:  *  compliant:
rubidium@4549:  *    - its constructor/destructor (if any) must be public
rubidium@4549:  *    - if the copying of item requires an extra resource management,
rubidium@4549:  *        you must define also copy constructor
rubidium@4549:  *    - must support nested type (struct, class or typedef) Titem::Key
rubidium@4549:  *        that defines the type of key class for that item
rubidium@4549:  *    - must support public method:
rubidium@4549:  *        const Key& GetKey() const; // return the item's key object
rubidium@4549:  *
rubidium@4549:  *  In addition, the Titem::Key class must support:
rubidium@4549:  *    - public method that calculates key's hash:
rubidium@4549:  *        int CalcHash() const;
rubidium@4549:  *    - public 'equality' operator to compare the key with another one
rubidium@4549:  *        bool operator == (const Key& other) const;
rubidium@4549:  */
KUDr@3900: template <class Titem_, int Thash_bits_>
KUDr@3900: class CHashTableT {
KUDr@3900: public:
KUDr@3900: 	typedef Titem_ Titem;                       // make Titem_ visible from outside of class
KUDr@3900: 	typedef typename Titem_::Key Tkey;          // make Titem_::Key a property of HashTable
KUDr@3900: 	ST_CONST(int, Thash_bits = Thash_bits_);    // publish num of hash bits
KUDr@3900: 	ST_CONST(int, Tcapacity = 1 << Thash_bits); // and num of slots 2^bits
KUDr@3900: 
KUDr@3900: protected:
KUDr@3900: 	/** each slot contains pointer to the first item in the list,
rubidium@4549: 	 *  Titem contains pointer to the next item - GetHashNext(), SetHashNext() */
KUDr@3900: 	typedef CHashTableSlotT<Titem_> Slot;
KUDr@3900: 
KUDr@3900: 	Slot*  m_slots;     // here we store our data (array of blobs)
KUDr@3900: 	int    m_num_items; // item counter
KUDr@3900: 
KUDr@3900: public:
KUDr@3900: 	// default constructor
KUDr@3900: 	FORCEINLINE CHashTableT()
KUDr@3900: 	{
KUDr@3900: 		// construct all slots
KUDr@3900: 		m_slots = new Slot[Tcapacity];
KUDr@3900: 		m_num_items = 0;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	~CHashTableT() {delete [] m_slots; m_num_items = 0; m_slots = NULL;}
KUDr@3900: 
KUDr@3900: protected:
KUDr@3900: 	/** static helper - return hash for the given key modulo number of slots */
KUDr@3900: 	FORCEINLINE static int CalcHash(const Tkey& key)
KUDr@3900: 	{
KUDr@3900: 		int32 hash = key.CalcHash();
KUDr@3900: 		if ((8 * Thash_bits) < 32) hash ^= hash >> (min(8 * Thash_bits, 31));
KUDr@3900: 		if ((4 * Thash_bits) < 32) hash ^= hash >> (min(4 * Thash_bits, 31));
KUDr@3900: 		if ((2 * Thash_bits) < 32) hash ^= hash >> (min(2 * Thash_bits, 31));
KUDr@3900: 		if ((1 * Thash_bits) < 32) hash ^= hash >> (min(1 * Thash_bits, 31));
KUDr@3900: 		hash &= (1 << Thash_bits) - 1;
KUDr@3900: 		return hash;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	/** static helper - return hash for the given item modulo number of slots */
KUDr@3900: 	FORCEINLINE static int CalcHash(const Titem_& item) {return CalcHash(item.GetKey());}
KUDr@3900: 
KUDr@3900: public:
KUDr@3900: 	/** item count */
KUDr@3900: 	FORCEINLINE int Count() const {return m_num_items;}
KUDr@3900: 
KUDr@3900: 	/** const item search */
KUDr@3900: 	const Titem_& Find(const Tkey& key) const
KUDr@3900: 	{
KUDr@3900: 		int hash = CalcHash(key);
KUDr@3900: 		const Slot& slot = m_slots[hash];
KUDr@3900: 		const Titem_& item = slot.Find(key);
KUDr@3900: 		return item;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	/** non-const item search */
KUDr@3900: 	Titem_& Find(const Tkey& key)
KUDr@3900: 	{
KUDr@3900: 		int hash = CalcHash(key);
KUDr@3900: 		Slot& slot = m_slots[hash];
KUDr@3900: 		Titem_& item = slot.Find(key);
KUDr@3900: 		return item;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	/** non-const item search & optional removal (if found) */
KUDr@3900: 	Titem_& TryPop(const Tkey& key)
KUDr@3900: 	{
KUDr@3900: 		int hash = CalcHash(key);
KUDr@3900: 		Slot& slot = m_slots[hash];
KUDr@3900: 		Titem_& item = slot.Detach(key);
KUDr@3900: 		if (&item != NULL) {
KUDr@3900: 			m_num_items--;
KUDr@3900: 		}
KUDr@3900: 		return item;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	/** non-const item search & removal */
KUDr@3900: 	Titem_& Pop(const Tkey& key)
KUDr@3900: 	{
KUDr@3900: 		Titem_& item = TryPop(key);
KUDr@3900: 		assert(&item != NULL);
KUDr@3900: 		return item;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	/** non-const item search & optional removal (if found) */
KUDr@3900: 	bool TryPop(Titem_& item)
KUDr@3900: 	{
KUDr@3900: 		const Tkey& key = item.GetKey();
KUDr@3900: 		int hash = CalcHash(key);
KUDr@3900: 		Slot& slot = m_slots[hash];
KUDr@3900: 		bool ret = slot.Detach(item);
KUDr@3900: 		if (ret) {
KUDr@3900: 			m_num_items--;
KUDr@3900: 		}
KUDr@3900: 		return ret;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	/** non-const item search & removal */
KUDr@3900: 	void Pop(Titem_& item)
KUDr@3900: 	{
KUDr@3900: 		bool ret = TryPop(item);
KUDr@3900: 		assert(ret);
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	/** add one item - copy it from the given item */
KUDr@3900: 	void Push(Titem_& new_item)
KUDr@3900: 	{
KUDr@3900: 		int hash = CalcHash(new_item);
KUDr@3900: 		Slot& slot = m_slots[hash];
KUDr@3900: 		assert(&slot.Find(new_item.GetKey()) == NULL);
KUDr@3900: 		slot.Attach(new_item);
KUDr@3900: 		m_num_items++;
KUDr@3900: 	}
KUDr@3900: };
KUDr@3900: 
KUDr@3900: #endif /* HASHTABLE_HPP */