--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/yapf/hashtable.hpp Sat May 27 16:12:16 2006 +0000
@@ -0,0 +1,234 @@
+/* $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 */