OpenTTD
hashtable.hpp
Go to the documentation of this file.
1 /* $Id$ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * 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.
6  * 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.
7  * 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/>.
8  */
9 
12 #ifndef HASHTABLE_HPP
13 #define HASHTABLE_HPP
14 
15 #include "../core/math_func.hpp"
16 
17 template <class Titem_>
19 {
20  typedef typename Titem_::Key Key; // make Titem_::Key a property of HashTable
21 
22  Titem_ *m_pFirst;
23 
24  inline CHashTableSlotT() : m_pFirst(NULL) {}
25 
27  inline void Clear()
28  {
29  m_pFirst = NULL;
30  }
31 
33  inline const Titem_ *Find(const Key &key) const
34  {
35  for (const Titem_ *pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {
36  if (pItem->GetKey() == key) {
37  /* we have found the item, return it */
38  return pItem;
39  }
40  }
41  return NULL;
42  }
43 
45  inline Titem_ *Find(const Key &key)
46  {
47  for (Titem_ *pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) {
48  if (pItem->GetKey() == key) {
49  /* we have found the item, return it */
50  return pItem;
51  }
52  }
53  return NULL;
54  }
55 
57  inline void Attach(Titem_ &new_item)
58  {
59  assert(new_item.GetHashNext() == NULL);
60  new_item.SetHashNext(m_pFirst);
61  m_pFirst = &new_item;
62  }
63 
65  inline bool Detach(Titem_ &item_to_remove)
66  {
67  if (m_pFirst == &item_to_remove) {
68  m_pFirst = item_to_remove.GetHashNext();
69  item_to_remove.SetHashNext(NULL);
70  return true;
71  }
72  Titem_ *pItem = m_pFirst;
73  for (;;) {
74  if (pItem == NULL) {
75  return false;
76  }
77  Titem_ *pNextItem = pItem->GetHashNext();
78  if (pNextItem == &item_to_remove) break;
79  pItem = pNextItem;
80  }
81  pItem->SetHashNext(item_to_remove.GetHashNext());
82  item_to_remove.SetHashNext(NULL);
83  return true;
84  }
85 
87  inline Titem_ *Detach(const Key &key)
88  {
89  /* do we have any items? */
90  if (m_pFirst == NULL) {
91  return NULL;
92  }
93  /* is it our first item? */
94  if (m_pFirst->GetKey() == key) {
95  Titem_ &ret_item = *m_pFirst;
96  m_pFirst = m_pFirst->GetHashNext();
97  ret_item.SetHashNext(NULL);
98  return &ret_item;
99  }
100  /* find it in the following items */
101  Titem_ *pPrev = m_pFirst;
102  for (Titem_ *pItem = m_pFirst->GetHashNext(); pItem != NULL; pPrev = pItem, pItem = pItem->GetHashNext()) {
103  if (pItem->GetKey() == key) {
104  /* we have found the item, unlink and return it */
105  pPrev->SetHashNext(pItem->GetHashNext());
106  pItem->SetHashNext(NULL);
107  return pItem;
108  }
109  }
110  return NULL;
111  }
112 };
113 
136 template <class Titem_, int Thash_bits_>
137 class CHashTableT {
138 public:
139  typedef Titem_ Titem; // make Titem_ visible from outside of class
140  typedef typename Titem_::Key Tkey; // make Titem_::Key a property of HashTable
141  static const int Thash_bits = Thash_bits_; // publish num of hash bits
142  static const int Tcapacity = 1 << Thash_bits; // and num of slots 2^bits
143 
144 protected:
150 
151  Slot m_slots[Tcapacity]; // here we store our data (array of blobs)
152  int m_num_items; // item counter
153 
154 public:
155  /* default constructor */
156  inline CHashTableT() : m_num_items(0)
157  {
158  }
159 
160 protected:
162  inline static int CalcHash(const Tkey &key)
163  {
164  uint32 hash = key.CalcHash();
165  hash -= (hash >> 17); // hash * 131071 / 131072
166  hash -= (hash >> 5); // * 31 / 32
167  hash &= (1 << Thash_bits) - 1; // modulo slots
168  return hash;
169  }
170 
172  inline static int CalcHash(const Titem_ &item)
173  {
174  return CalcHash(item.GetKey());
175  }
176 
177 public:
179  inline int Count() const
180  {
181  return m_num_items;
182  }
183 
185  inline void Clear()
186  {
187  for (int i = 0; i < Tcapacity; i++) m_slots[i].Clear();
188  }
189 
191  const Titem_ *Find(const Tkey &key) const
192  {
193  int hash = CalcHash(key);
194  const Slot &slot = m_slots[hash];
195  const Titem_ *item = slot.Find(key);
196  return item;
197  }
198 
200  Titem_ *Find(const Tkey &key)
201  {
202  int hash = CalcHash(key);
203  Slot &slot = m_slots[hash];
204  Titem_ *item = slot.Find(key);
205  return item;
206  }
207 
209  Titem_ *TryPop(const Tkey &key)
210  {
211  int hash = CalcHash(key);
212  Slot &slot = m_slots[hash];
213  Titem_ *item = slot.Detach(key);
214  if (item != NULL) {
215  m_num_items--;
216  }
217  return item;
218  }
219 
221  Titem_& Pop(const Tkey &key)
222  {
223  Titem_ *item = TryPop(key);
224  assert(item != NULL);
225  return *item;
226  }
227 
229  bool TryPop(Titem_ &item)
230  {
231  const Tkey &key = item.GetKey();
232  int hash = CalcHash(key);
233  Slot &slot = m_slots[hash];
234  bool ret = slot.Detach(item);
235  if (ret) {
236  m_num_items--;
237  }
238  return ret;
239  }
240 
242  void Pop(Titem_ &item)
243  {
244  bool ret = TryPop(item);
245  assert(ret);
246  }
247 
249  void Push(Titem_ &new_item)
250  {
251  int hash = CalcHash(new_item);
252  Slot &slot = m_slots[hash];
253  assert(slot.Find(new_item.GetKey()) == NULL);
254  slot.Attach(new_item);
255  m_num_items++;
256  }
257 };
258 
259 #endif /* HASHTABLE_HPP */
static int CalcHash(const Tkey &key)
static helper - return hash for the given key modulo number of slots
Definition: hashtable.hpp:162
class CHashTableT<Titem, Thash_bits> - simple hash table of pointers allocated elsewhere.
Definition: hashtable.hpp:137
void Push(Titem_ &new_item)
add one item - copy it from the given item
Definition: hashtable.hpp:249
CHashTableSlotT< Titem_ > Slot
each slot contains pointer to the first item in the list, Titem contains pointer to the next item - G...
Definition: hashtable.hpp:149
Titem_ & Pop(const Tkey &key)
non-const item search & removal
Definition: hashtable.hpp:221
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:33
bool TryPop(Titem_ &item)
non-const item search & optional removal (if found)
Definition: hashtable.hpp:229
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:45
const Titem_ * Find(const Tkey &key) const
const item search
Definition: hashtable.hpp:191
bool Detach(Titem_ &item_to_remove)
hash table slot helper - remove item from a slot
Definition: hashtable.hpp:65
void Clear()
simple clear - forget all items - used by CSegmentCostCacheT.Flush()
Definition: hashtable.hpp:185
Titem_ * Detach(const Key &key)
hash table slot helper - remove and return item from a slot
Definition: hashtable.hpp:87
void Pop(Titem_ &item)
non-const item search & removal
Definition: hashtable.hpp:242
Titem_ * TryPop(const Tkey &key)
non-const item search & optional removal (if found)
Definition: hashtable.hpp:209
int Count() const
item count
Definition: hashtable.hpp:179
void Clear()
hash table slot helper - clears the slot by simple forgetting its items
Definition: hashtable.hpp:27
void Attach(Titem_ &new_item)
hash table slot helper - add new item to the slot
Definition: hashtable.hpp:57
static int CalcHash(const Titem_ &item)
static helper - return hash for the given item modulo number of slots
Definition: hashtable.hpp:172
Titem_ * Find(const Tkey &key)
non-const item search
Definition: hashtable.hpp:200