@@ -68,194 +68,192 @@ struct CHashTableSlotT
m_pFirst = item_to_remove.GetHashNext();
item_to_remove.SetHashNext(NULL);
return true;
}
Titem_ *pItem = m_pFirst;
for (;;) {
if (pItem == NULL) {
return false;
Titem_ *pNextItem = pItem->GetHashNext();
if (pNextItem == &item_to_remove) break;
pItem = pNextItem;
pItem->SetHashNext(item_to_remove.GetHashNext());
/** hash table slot helper - remove and return item from a slot */
inline 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;
};
/**
* 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[Tcapacity]; // here we store our data (array of blobs)
int m_num_items; // item counter
/* default constructor */
inline CHashTableT() : m_num_items(0)
/** static helper - return hash for the given key modulo number of slots */
inline 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;
uint32 hash = key.CalcHash();
hash -= (hash >> 17); // hash * 131071 / 131072
hash -= (hash >> 5); // * 31 / 32
hash &= (1 << Thash_bits) - 1; // modulo slots
return hash;
/** static helper - return hash for the given item modulo number of slots */
inline static int CalcHash(const Titem_ &item)
return CalcHash(item.GetKey());
/** item count */
inline int Count() const
return m_num_items;
/** simple clear - forget all items - used by CSegmentCostCacheT.Flush() */
inline void Clear()
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)
Slot &slot = m_slots[hash];
Titem_ *item = slot.Find(key);
/** non-const item search & optional removal (if found) */
Titem_ *TryPop(const Tkey &key)
Titem_ *item = slot.Detach(key);
if (item != NULL) {
m_num_items--;
/** non-const item search & removal */
Titem_& Pop(const Tkey &key)
Titem_ *item = TryPop(key);
assert(item != NULL);
return *item;
bool TryPop(Titem_ &item)
const Tkey &key = item.GetKey();
bool ret = slot.Detach(item);
if (ret) {
return ret;
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);
assert(slot.Find(new_item.GetKey()) == NULL);
slot.Attach(new_item);
m_num_items++;
#endif /* HASHTABLE_HPP */
Status change: