diff options
Diffstat (limited to 'src/yapf/hashtable.hpp')
| -rw-r--r-- | src/yapf/hashtable.hpp | 240 |
1 files changed, 240 insertions, 0 deletions
diff --git a/src/yapf/hashtable.hpp b/src/yapf/hashtable.hpp new file mode 100644 index 000000000..c6b52e50a --- /dev/null +++ b/src/yapf/hashtable.hpp @@ -0,0 +1,240 @@ +/* $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 */ |