13 #include "../core/math_func.hpp" 15 template <
class Titem_>
18 typedef typename Titem_::Key Key;
31 inline const Titem_ *
Find(
const Key &key)
const 33 for (
const Titem_ *pItem = m_pFirst; pItem !=
nullptr; pItem = pItem->GetHashNext()) {
34 if (pItem->GetKey() == key) {
43 inline Titem_ *
Find(
const Key &key)
45 for (Titem_ *pItem = m_pFirst; pItem !=
nullptr; pItem = pItem->GetHashNext()) {
46 if (pItem->GetKey() == key) {
57 assert(new_item.GetHashNext() ==
nullptr);
58 new_item.SetHashNext(m_pFirst);
63 inline bool Detach(Titem_ &item_to_remove)
65 if (m_pFirst == &item_to_remove) {
66 m_pFirst = item_to_remove.GetHashNext();
67 item_to_remove.SetHashNext(
nullptr);
70 Titem_ *pItem = m_pFirst;
72 if (pItem ==
nullptr) {
75 Titem_ *pNextItem = pItem->GetHashNext();
76 if (pNextItem == &item_to_remove)
break;
79 pItem->SetHashNext(item_to_remove.GetHashNext());
80 item_to_remove.SetHashNext(
nullptr);
85 inline Titem_ *
Detach(
const Key &key)
88 if (m_pFirst ==
nullptr) {
92 if (m_pFirst->GetKey() == key) {
93 Titem_ &ret_item = *m_pFirst;
94 m_pFirst = m_pFirst->GetHashNext();
95 ret_item.SetHashNext(
nullptr);
99 Titem_ *pPrev = m_pFirst;
100 for (Titem_ *pItem = m_pFirst->GetHashNext(); pItem !=
nullptr; pPrev = pItem, pItem = pItem->GetHashNext()) {
101 if (pItem->GetKey() == key) {
103 pPrev->SetHashNext(pItem->GetHashNext());
104 pItem->SetHashNext(
nullptr);
134 template <
class Titem_,
int Thash_bits_>
137 typedef Titem_ Titem;
138 typedef typename Titem_::Key Tkey;
139 static const int Thash_bits = Thash_bits_;
140 static const int Tcapacity = 1 << Thash_bits;
149 Slot m_slots[Tcapacity];
162 uint32 hash = key.CalcHash();
163 hash -= (hash >> 17);
165 hash &= (1 << Thash_bits) - 1;
172 return CalcHash(item.GetKey());
185 for (
int i = 0; i < Tcapacity; i++) m_slots[i].
Clear();
189 const Titem_ *
Find(
const Tkey &key)
const 191 int hash = CalcHash(key);
192 const Slot &slot = m_slots[hash];
193 const Titem_ *item = slot.
Find(key);
200 int hash = CalcHash(key);
201 Slot &slot = m_slots[hash];
202 Titem_ *item = slot.
Find(key);
209 int hash = CalcHash(key);
210 Slot &slot = m_slots[hash];
211 Titem_ *item = slot.
Detach(key);
212 if (item !=
nullptr) {
219 Titem_&
Pop(
const Tkey &key)
221 Titem_ *item = TryPop(key);
222 assert(item !=
nullptr);
229 const Tkey &key = item.GetKey();
230 int hash = CalcHash(key);
231 Slot &slot = m_slots[hash];
232 bool ret = slot.
Detach(item);
242 bool ret = TryPop(item);
249 int hash = CalcHash(new_item);
250 Slot &slot = m_slots[hash];
251 assert(slot.
Find(new_item.GetKey()) ==
nullptr);
static int CalcHash(const Tkey &key)
static helper - return hash for the given key modulo number of slots
class CHashTableT<Titem, Thash_bits> - simple hash table of pointers allocated elsewhere.
void Push(Titem_ &new_item)
add one item - copy it from the given item
CHashTableSlotT< Titem_ > Slot
each slot contains pointer to the first item in the list, Titem contains pointer to the next item - G...
Titem_ & Pop(const Tkey &key)
non-const item search & removal
const Titem_ * Find(const Key &key) const
hash table slot helper - linear search for item with given key through the given blob - const version...
bool TryPop(Titem_ &item)
non-const item search & optional removal (if found)
Titem_ * Find(const Key &key)
hash table slot helper - linear search for item with given key through the given blob - non-const ver...
const Titem_ * Find(const Tkey &key) const
const item search
bool Detach(Titem_ &item_to_remove)
hash table slot helper - remove item from a slot
void Clear()
simple clear - forget all items - used by CSegmentCostCacheT.Flush()
Titem_ * Detach(const Key &key)
hash table slot helper - remove and return item from a slot
void Pop(Titem_ &item)
non-const item search & removal
Titem_ * TryPop(const Tkey &key)
non-const item search & optional removal (if found)
int Count() const
item count
void Clear()
hash table slot helper - clears the slot by simple forgetting its items
void Attach(Titem_ &new_item)
hash table slot helper - add new item to the slot
static int CalcHash(const Titem_ &item)
static helper - return hash for the given item modulo number of slots
Titem_ * Find(const Tkey &key)
non-const item search