/* $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 - clears the slot by simple forgetting its items */ FORCEINLINE void Clear() {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 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 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 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 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 static const int Thash_bits = Thash_bits_; // publish num of hash bits static 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;} /** simple clear - forget all items - used by CSegmentCostCacheT.Flush() */ FORCEINLINE void Clear() const {for (int i = 0; i < Tcapacity; i++) m_slots[i].Clear();} /** 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 */