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