OpenTTD Source  20241121-master-g67a0fccfad
hashtable.hpp
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
6  */
7 
10 #ifndef HASHTABLE_HPP
11 #define HASHTABLE_HPP
12 
13 #include "../core/math_func.hpp"
14 
15 template <class TItem>
17 {
18  typedef typename TItem::Key Key; // make Titem::Key a property of HashTable
19 
20  TItem *first_item = nullptr;
21 
23  inline void Clear()
24  {
25  this->first_item = nullptr;
26  }
27 
29  inline const TItem *Find(const Key &key) const
30  {
31  for (const TItem *item = this->first_item; item != nullptr; item = item->GetHashNext()) {
32  if (item->GetKey() == key) {
33  /* we have found the item, return it */
34  return item;
35  }
36  }
37  return nullptr;
38  }
39 
41  inline TItem *Find(const Key &key)
42  {
43  for (TItem *item = this->first_item; item != nullptr; item = item->GetHashNext()) {
44  if (item->GetKey() == key) {
45  /* we have found the item, return it */
46  return item;
47  }
48  }
49  return nullptr;
50  }
51 
53  inline void Attach(TItem &new_item)
54  {
55  assert(new_item.GetHashNext() == nullptr);
56  new_item.SetHashNext(this->first_item);
57  this->first_item = &new_item;
58  }
59 
61  inline bool Detach(TItem &item_to_remove)
62  {
63  if (this->first_item == &item_to_remove) {
64  this->first_item = item_to_remove.GetHashNext();
65  item_to_remove.SetHashNext(nullptr);
66  return true;
67  }
68  TItem *item = this->first_item;
69  for (;;) {
70  if (item == nullptr) {
71  return false;
72  }
73  TItem *next_item = item->GetHashNext();
74  if (next_item == &item_to_remove) break;
75  item = next_item;
76  }
77  item->SetHashNext(item_to_remove.GetHashNext());
78  item_to_remove.SetHashNext(nullptr);
79  return true;
80  }
81 
83  inline TItem *Detach(const Key &key)
84  {
85  /* do we have any items? */
86  if (this->first_item == nullptr) {
87  return nullptr;
88  }
89  /* is it our first item? */
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);
94  return &ret_item;
95  }
96  /* find it in the following items */
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) {
100  /* we have found the item, unlink and return it */
101  previous_item->SetHashNext(item->GetHashNext());
102  item->SetHashNext(nullptr);
103  return item;
104  }
105  }
106  return nullptr;
107  }
108 };
109 
132 template <class Titem, int Thash_bits_>
133 class HashTable {
134 public:
135  typedef typename Titem::Key Tkey; // make Titem::Key a property of HashTable
136  static constexpr int HASH_BITS = Thash_bits_; // publish num of hash bits
137  static constexpr int CAPACITY = 1 << HASH_BITS; // and num of slots 2^bits
138 
139 protected:
145 
146  Slot slots[CAPACITY]; // here we store our data (array of blobs)
147  int number_of_items = 0; // item counter
148 
150  inline static int CalcHash(const Tkey &key)
151  {
152  uint32_t hash = key.CalcHash();
153  hash -= (hash >> 17); // hash * 131071 / 131072
154  hash -= (hash >> 5); // * 31 / 32
155  hash &= (1 << HASH_BITS) - 1; // modulo slots
156  return hash;
157  }
158 
160  inline static int CalcHash(const Titem &item)
161  {
162  return CalcHash(item.GetKey());
163  }
164 
165 public:
167  inline int Count() const
168  {
169  return this->number_of_items;
170  }
171 
173  inline void Clear()
174  {
175  for (int i = 0; i < CAPACITY; i++) this->slots[i].Clear();
176  this->number_of_items = 0;
177  }
178 
180  const Titem *Find(const Tkey &key) const
181  {
182  int hash = CalcHash(key);
183  const Slot &slot = this->slots[hash];
184  const Titem *item = slot.Find(key);
185  return item;
186  }
187 
189  Titem *Find(const Tkey &key)
190  {
191  int hash = CalcHash(key);
192  Slot &slot = this->slots[hash];
193  Titem *item = slot.Find(key);
194  return item;
195  }
196 
198  Titem *TryPop(const Tkey &key)
199  {
200  int hash = CalcHash(key);
201  Slot &slot = this->slots[hash];
202  Titem *item = slot.Detach(key);
203  if (item != nullptr) {
204  this->number_of_items--;
205  }
206  return item;
207  }
208 
210  Titem &Pop(const Tkey &key)
211  {
212  Titem *item = TryPop(key);
213  assert(item != nullptr);
214  return *item;
215  }
216 
218  bool TryPop(Titem &item)
219  {
220  const Tkey &key = item.GetKey();
221  int hash = CalcHash(key);
222  Slot &slot = this->slots[hash];
223  bool ret = slot.Detach(item);
224  if (ret) {
225  this->number_of_items--;
226  }
227  return ret;
228  }
229 
231  void Pop(Titem &item)
232  {
233  [[maybe_unused]] bool ret = TryPop(item);
234  assert(ret);
235  }
236 
238  void Push(Titem &new_item)
239  {
240  int hash = CalcHash(new_item);
241  Slot &slot = this->slots[hash];
242  assert(slot.Find(new_item.GetKey()) == nullptr);
243  slot.Attach(new_item);
244  this->number_of_items++;
245  }
246 };
247 
248 #endif /* HASHTABLE_HPP */
class HashTable<Titem, HASH_BITS> - simple hash table of pointers allocated elsewhere.
Definition: hashtable.hpp:133
const Titem * Find(const Tkey &key) const
const item search
Definition: hashtable.hpp:180
void Push(Titem &new_item)
add one item - copy it from the given item
Definition: hashtable.hpp:238
int Count() const
item count
Definition: hashtable.hpp:167
void Clear()
simple clear - forget all items - used by CSegmentCostCacheT.Flush()
Definition: hashtable.hpp:173
Titem * Find(const Tkey &key)
non-const item search
Definition: hashtable.hpp:189
static int CalcHash(const Titem &item)
static helper - return hash for the given item modulo number of slots
Definition: hashtable.hpp:160
HashTableSlot< Titem > Slot
each slot contains pointer to the first item in the list, Titem contains pointer to the next item - G...
Definition: hashtable.hpp:144
bool TryPop(Titem &item)
non-const item search & optional removal (if found)
Definition: hashtable.hpp:218
Titem & Pop(const Tkey &key)
non-const item search & removal
Definition: hashtable.hpp:210
Titem * TryPop(const Tkey &key)
non-const item search & optional removal (if found)
Definition: hashtable.hpp:198
static int CalcHash(const Tkey &key)
static helper - return hash for the given key modulo number of slots
Definition: hashtable.hpp:150
void Pop(Titem &item)
non-const item search & removal
Definition: hashtable.hpp:231
TItem * Detach(const Key &key)
hash table slot helper - remove and return item from a slot
Definition: hashtable.hpp:83
bool Detach(TItem &item_to_remove)
hash table slot helper - remove item from a slot
Definition: hashtable.hpp:61
const TItem * Find(const Key &key) const
hash table slot helper - linear search for item with given key through the given blob - const version
Definition: hashtable.hpp:29
void Attach(TItem &new_item)
hash table slot helper - add new item to the slot
Definition: hashtable.hpp:53
void Clear()
hash table slot helper - clears the slot by simple forgetting its items
Definition: hashtable.hpp:23
TItem * Find(const Key &key)
hash table slot helper - linear search for item with given key through the given blob - non-const ver...
Definition: hashtable.hpp:41