From 5e73dce0e71791b87e5b096a890578eefcc26639 Mon Sep 17 00:00:00 2001 From: KUDr Date: Sat, 27 May 2006 16:12:16 +0000 Subject: (svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing. --- yapf/hashtable.hpp | 234 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 234 insertions(+) create mode 100644 yapf/hashtable.hpp (limited to 'yapf/hashtable.hpp') diff --git a/yapf/hashtable.hpp b/yapf/hashtable.hpp new file mode 100644 index 000000000..bab5bccfc --- /dev/null +++ b/yapf/hashtable.hpp @@ -0,0 +1,234 @@ +/* $Id$ */ + +#ifndef HASHTABLE_HPP +#define HASHTABLE_HPP + +template +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 - 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 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 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 */ -- cgit v1.2.3-70-g09d2