13 #include "../core/math_func.hpp"
15 template <
class TItem>
18 typedef typename TItem::Key Key;
20 TItem *first_item =
nullptr;
25 this->first_item =
nullptr;
29 inline const TItem *
Find(
const Key &key)
const
31 for (
const TItem *item = this->first_item; item !=
nullptr; item = item->GetHashNext()) {
32 if (item->GetKey() == key) {
41 inline TItem *
Find(
const Key &key)
43 for (TItem *item = this->first_item; item !=
nullptr; item = item->GetHashNext()) {
44 if (item->GetKey() == key) {
55 assert(new_item.GetHashNext() ==
nullptr);
56 new_item.SetHashNext(this->first_item);
57 this->first_item = &new_item;
61 inline bool Detach(TItem &item_to_remove)
63 if (this->first_item == &item_to_remove) {
64 this->first_item = item_to_remove.GetHashNext();
65 item_to_remove.SetHashNext(
nullptr);
68 TItem *item = this->first_item;
70 if (item ==
nullptr) {
73 TItem *next_item = item->GetHashNext();
74 if (next_item == &item_to_remove)
break;
77 item->SetHashNext(item_to_remove.GetHashNext());
78 item_to_remove.SetHashNext(
nullptr);
86 if (this->first_item ==
nullptr) {
90 if (this->first_item->GetKey() == key) {
91 TItem &ret_item = *this->first_item;
92 this->first_item = this->first_item->GetHashNext();
93 ret_item.SetHashNext(
nullptr);
97 TItem *previous_item = this->first_item;
98 for (TItem *item = this->first_item->GetHashNext(); item !=
nullptr; previous_item = item, item = item->GetHashNext()) {
99 if (item->GetKey() == key) {
101 previous_item->SetHashNext(item->GetHashNext());
102 item->SetHashNext(
nullptr);
132 template <
class Titem,
int Thash_bits_>
135 typedef typename Titem::Key Tkey;
136 static constexpr
int HASH_BITS = Thash_bits_;
137 static constexpr
int CAPACITY = 1 << HASH_BITS;
146 Slot slots[CAPACITY];
147 int number_of_items = 0;
152 uint32_t hash = key.CalcHash();
153 hash -= (hash >> 17);
155 hash &= (1 << HASH_BITS) - 1;
169 return this->number_of_items;
175 for (
int i = 0; i < CAPACITY; i++) this->slots[i].
Clear();
176 this->number_of_items = 0;
180 const Titem *
Find(
const Tkey &key)
const
183 const Slot &slot = this->slots[hash];
184 const Titem *item = slot.
Find(key);
192 Slot &slot = this->slots[hash];
193 Titem *item = slot.
Find(key);
201 Slot &slot = this->slots[hash];
202 Titem *item = slot.
Detach(key);
203 if (item !=
nullptr) {
204 this->number_of_items--;
210 Titem &
Pop(
const Tkey &key)
212 Titem *item =
TryPop(key);
213 assert(item !=
nullptr);
220 const Tkey &key = item.GetKey();
222 Slot &slot = this->slots[hash];
223 bool ret = slot.
Detach(item);
225 this->number_of_items--;
233 [[maybe_unused]]
bool ret =
TryPop(item);
241 Slot &slot = this->slots[hash];
242 assert(slot.
Find(new_item.GetKey()) ==
nullptr);
244 this->number_of_items++;
class HashTable<Titem, HASH_BITS> - simple hash table of pointers allocated elsewhere.
const Titem * Find(const Tkey &key) const
const item search
void Push(Titem &new_item)
add one item - copy it from the given item
int Count() const
item count
void Clear()
simple clear - forget all items - used by CSegmentCostCacheT.Flush()
Titem * Find(const Tkey &key)
non-const item search
static int CalcHash(const Titem &item)
static helper - return hash for the given item modulo number of slots
HashTableSlot< Titem > Slot
each slot contains pointer to the first item in the list, Titem contains pointer to the next item - G...
bool TryPop(Titem &item)
non-const item search & optional removal (if found)
Titem & Pop(const Tkey &key)
non-const item search & removal
Titem * TryPop(const Tkey &key)
non-const item search & optional removal (if found)
static int CalcHash(const Tkey &key)
static helper - return hash for the given key modulo number of slots
void Pop(Titem &item)
non-const item search & removal
TItem * Detach(const Key &key)
hash table slot helper - remove and return item from a slot
bool Detach(TItem &item_to_remove)
hash table slot helper - remove item from a slot
const TItem * Find(const Key &key) const
hash table slot helper - linear search for item with given key through the given blob - const version
void Attach(TItem &new_item)
hash table slot helper - add new item to the slot
void Clear()
hash table slot helper - clears the slot by simple forgetting its items
TItem * Find(const Key &key)
hash table slot helper - linear search for item with given key through the given blob - non-const ver...