summaryrefslogtreecommitdiff
path: root/yapf/hashtable.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'yapf/hashtable.hpp')
-rw-r--r--yapf/hashtable.hpp240
1 files changed, 0 insertions, 240 deletions
diff --git a/yapf/hashtable.hpp b/yapf/hashtable.hpp
deleted file mode 100644
index c6b52e50a..000000000
--- a/yapf/hashtable.hpp
+++ /dev/null
@@ -1,240 +0,0 @@
-/* $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 */
generated by cgit v1.2.3-54-g00ecf (git 2.44.0) at 2024-08-03 17:44:05 +0000