|
dvander@1
|
1 |
// vim: set sts=8 ts=2 sw=2 tw=99 et: |
|
dvander@1
|
2 |
// |
|
dvander@1
|
3 |
// Copyright (C) 2013, David Anderson and AlliedModders LLC |
|
dvander@1
|
4 |
// All rights reserved. |
|
dvander@1
|
5 |
// |
|
dvander@1
|
6 |
// Redistribution and use in source and binary forms, with or without |
|
dvander@1
|
7 |
// modification, are permitted provided that the following conditions are met: |
|
dvander@1
|
8 |
// |
|
dvander@1
|
9 |
// * Redistributions of source code must retain the above copyright notice, this |
|
dvander@1
|
10 |
// list of conditions and the following disclaimer. |
|
dvander@1
|
11 |
// * Redistributions in binary form must reproduce the above copyright notice, |
|
dvander@1
|
12 |
// this list of conditions and the following disclaimer in the documentation |
|
dvander@1
|
13 |
// and/or other materials provided with the distribution. |
|
dvander@1
|
14 |
// * Neither the name of AlliedModders LLC nor the names of its contributors |
|
dvander@1
|
15 |
// may be used to endorse or promote products derived from this software |
|
dvander@1
|
16 |
// without specific prior written permission. |
|
dvander@1
|
17 |
// |
|
dvander@1
|
18 |
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
|
dvander@1
|
19 |
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
|
dvander@1
|
20 |
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
|
dvander@1
|
21 |
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
|
dvander@1
|
22 |
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
|
dvander@1
|
23 |
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
|
dvander@1
|
24 |
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
|
dvander@1
|
25 |
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
|
dvander@1
|
26 |
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
|
dvander@1
|
27 |
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
|
dvander@1
|
28 |
// POSSIBILITY OF SUCH DAMAGE. |
|
dvander@1
|
29 |
|
|
dvander@1
|
30 |
#ifndef _INCLUDE_KEIMA_HASHTABLE_H_ |
|
dvander@1
|
31 |
#define _INCLUDE_KEIMA_HASHTABLE_H_ |
|
dvander@1
|
32 |
|
|
dvander@1
|
33 |
#include <new> |
|
dvander@1
|
34 |
#include <limits.h> |
|
dvander@1
|
35 |
#include <stdlib.h> |
|
dvander@1
|
36 |
#include "am-utility.h" |
|
dvander@1
|
37 |
|
|
dvander@1
|
38 |
namespace ke { |
|
dvander@1
|
39 |
|
|
dvander@1
|
40 |
namespace detail { |
|
dvander@1
|
41 |
template <typename T> |
|
dvander@1
|
42 |
class HashTableEntry |
|
dvander@1
|
43 |
{ |
|
dvander@1
|
44 |
uint32_t hash_; |
|
dvander@1
|
45 |
T t_; |
|
dvander@1
|
46 |
|
|
dvander@1
|
47 |
public: |
|
dvander@1
|
48 |
static const uint32_t kFreeHash = 0; |
|
dvander@1
|
49 |
static const uint32_t kRemovedHash = 1; |
|
dvander@1
|
50 |
|
|
dvander@1
|
51 |
public: |
|
dvander@1
|
52 |
void setHash(uint32_t hash, const T &t) { |
|
dvander@1
|
53 |
hash_ = hash; |
|
dvander@1
|
54 |
new (&t_) T(t); |
|
dvander@1
|
55 |
} |
|
dvander@1
|
56 |
uint32_t hash() const { |
|
dvander@1
|
57 |
return hash_; |
|
dvander@1
|
58 |
} |
|
dvander@1
|
59 |
void setRemoved() { |
|
dvander@1
|
60 |
destruct(); |
|
dvander@1
|
61 |
hash_ = kRemovedHash; |
|
dvander@1
|
62 |
} |
|
dvander@9
|
63 |
void setFree() { |
|
dvander@9
|
64 |
destruct(); |
|
dvander@9
|
65 |
hash_ = kFreeHash; |
|
dvander@9
|
66 |
} |
|
dvander@1
|
67 |
void initialize() { |
|
dvander@1
|
68 |
hash_ = kFreeHash; |
|
dvander@1
|
69 |
} |
|
dvander@1
|
70 |
void destruct() { |
|
dvander@1
|
71 |
if (isLive()) |
|
dvander@1
|
72 |
t_.~T(); |
|
dvander@1
|
73 |
} |
|
dvander@1
|
74 |
bool removed() const { |
|
dvander@1
|
75 |
return hash_ == kRemovedHash; |
|
dvander@1
|
76 |
} |
|
dvander@1
|
77 |
bool free() const { |
|
dvander@1
|
78 |
return hash_ == kFreeHash; |
|
dvander@1
|
79 |
} |
|
dvander@1
|
80 |
bool isLive() const { |
|
dvander@1
|
81 |
return hash_ > kRemovedHash; |
|
dvander@1
|
82 |
} |
|
dvander@1
|
83 |
T &payload() { |
|
dvander@1
|
84 |
assert(isLive()); |
|
dvander@1
|
85 |
return t_; |
|
dvander@1
|
86 |
} |
|
dvander@1
|
87 |
bool sameHash(uint32_t hash) const { |
|
dvander@1
|
88 |
return hash_ == hash; |
|
dvander@1
|
89 |
} |
|
dvander@1
|
90 |
|
|
dvander@1
|
91 |
private: |
|
dvander@1
|
92 |
HashTableEntry(const HashTableEntry &other) KE_DELETE; |
|
dvander@1
|
93 |
HashTableEntry &operator =(const HashTableEntry &other) KE_DELETE; |
|
dvander@1
|
94 |
}; |
|
dvander@1
|
95 |
} |
|
dvander@1
|
96 |
|
|
dvander@1
|
97 |
// The HashPolicy for the table must have the following members: |
|
dvander@1
|
98 |
// |
|
dvander@1
|
99 |
// Payload |
|
dvander@1
|
100 |
// static uint32_t hash(const LookupType &key); |
|
dvander@1
|
101 |
// static bool matches(const LookupType &key, const Payload &other); |
|
dvander@1
|
102 |
// |
|
dvander@1
|
103 |
// Payload must be a type, and LookupType is any type that lookups will be |
|
dvander@1
|
104 |
// performed with (these functions can be overloaded). Example: |
|
dvander@1
|
105 |
// |
|
dvander@1
|
106 |
// struct Policy { |
|
dvander@1
|
107 |
// typedef KeyValuePair Payload; |
|
dvander@1
|
108 |
// static uint32 hash(const Key &key) { |
|
dvander@1
|
109 |
// ... |
|
dvander@1
|
110 |
// } |
|
dvander@1
|
111 |
// static bool matches(const Key &key, const KeyValuePair &pair) { |
|
dvander@1
|
112 |
// ... |
|
dvander@1
|
113 |
// } |
|
dvander@1
|
114 |
// }; |
|
dvander@1
|
115 |
// |
|
dvander@1
|
116 |
// Note that the table is not usable until init() has been called. |
|
dvander@1
|
117 |
// |
|
dvander@1
|
118 |
template <typename HashPolicy, typename AllocPolicy = SystemAllocatorPolicy> |
|
dvander@1
|
119 |
class HashTable : public AllocPolicy |
|
dvander@1
|
120 |
{ |
|
dvander@1
|
121 |
friend class iterator; |
|
dvander@1
|
122 |
|
|
dvander@1
|
123 |
typedef typename HashPolicy::Payload Payload; |
|
dvander@1
|
124 |
typedef detail::HashTableEntry<Payload> Entry; |
|
dvander@1
|
125 |
|
|
dvander@1
|
126 |
private: |
|
dvander@1
|
127 |
static const uint32_t kMinCapacity = 16; |
|
dvander@1
|
128 |
static const uint32_t kMaxCapacity = INT_MAX / sizeof(Entry); |
|
dvander@1
|
129 |
|
|
dvander@1
|
130 |
template <typename Key> |
|
dvander@1
|
131 |
uint32_t computeHash(const Key &key) { |
|
dvander@1
|
132 |
// Multiply by golden ratio. |
|
dvander@1
|
133 |
uint32_t hash = HashPolicy::hash(key) * 0x9E3779B9; |
|
dvander@1
|
134 |
if (hash == Entry::kFreeHash || hash == Entry::kRemovedHash) |
|
dvander@1
|
135 |
hash += 2; |
|
dvander@1
|
136 |
return hash; |
|
dvander@1
|
137 |
} |
|
dvander@1
|
138 |
|
|
dvander@1
|
139 |
Entry *createTable(uint32_t capacity) { |
|
dvander@1
|
140 |
assert(capacity <= kMaxCapacity); |
|
dvander@1
|
141 |
|
|
dvander@1
|
142 |
Entry *table = (Entry *)this->malloc(capacity * sizeof(Entry)); |
|
dvander@1
|
143 |
if (!table) |
|
dvander@1
|
144 |
return NULL; |
|
dvander@1
|
145 |
|
|
dvander@1
|
146 |
for (size_t i = 0; i < capacity; i++) |
|
dvander@1
|
147 |
table[i].initialize(); |
|
dvander@1
|
148 |
|
|
dvander@1
|
149 |
return table; |
|
dvander@1
|
150 |
} |
|
dvander@1
|
151 |
|
|
dvander@1
|
152 |
public: |
|
dvander@1
|
153 |
class Result |
|
dvander@1
|
154 |
{ |
|
dvander@1
|
155 |
friend class HashTable; |
|
dvander@1
|
156 |
|
|
dvander@1
|
157 |
Entry *entry_; |
|
dvander@1
|
158 |
|
|
dvander@1
|
159 |
Entry &entry() { |
|
dvander@1
|
160 |
return *entry_; |
|
dvander@1
|
161 |
} |
|
dvander@1
|
162 |
|
|
dvander@1
|
163 |
public: |
|
dvander@1
|
164 |
Result(Entry *entry) |
|
dvander@1
|
165 |
: entry_(entry) |
|
dvander@1
|
166 |
{ } |
|
dvander@1
|
167 |
|
|
dvander@1
|
168 |
Payload * operator ->() { |
|
dvander@1
|
169 |
return &entry_->payload(); |
|
dvander@1
|
170 |
} |
|
dvander@1
|
171 |
Payload & operator *() { |
|
dvander@1
|
172 |
return entry_->payload(); |
|
dvander@1
|
173 |
} |
|
dvander@1
|
174 |
|
|
dvander@1
|
175 |
bool found() const { |
|
dvander@1
|
176 |
return entry_->isLive(); |
|
dvander@1
|
177 |
} |
|
dvander@1
|
178 |
}; |
|
dvander@1
|
179 |
|
|
dvander@1
|
180 |
class Insert : public Result |
|
dvander@1
|
181 |
{ |
|
dvander@1
|
182 |
uint32_t hash_; |
|
dvander@1
|
183 |
|
|
dvander@1
|
184 |
public: |
|
dvander@1
|
185 |
Insert(Entry *entry, uint32_t hash) |
|
dvander@1
|
186 |
: Result(entry), |
|
dvander@1
|
187 |
hash_(hash) |
|
dvander@1
|
188 |
{ |
|
dvander@1
|
189 |
} |
|
dvander@1
|
190 |
|
|
dvander@1
|
191 |
uint32_t hash() const { |
|
dvander@1
|
192 |
return hash_; |
|
dvander@1
|
193 |
} |
|
dvander@1
|
194 |
}; |
|
dvander@1
|
195 |
|
|
dvander@1
|
196 |
private: |
|
dvander@1
|
197 |
class Probulator { |
|
dvander@1
|
198 |
uint32_t hash_; |
|
dvander@1
|
199 |
uint32_t capacity_; |
|
dvander@1
|
200 |
|
|
dvander@1
|
201 |
public: |
|
dvander@1
|
202 |
Probulator(uint32_t hash, uint32_t capacity) |
|
dvander@1
|
203 |
: hash_(hash), |
|
dvander@1
|
204 |
capacity_(capacity) |
|
dvander@1
|
205 |
{ |
|
dvander@1
|
206 |
assert(IsPowerOfTwo(capacity_)); |
|
dvander@1
|
207 |
} |
|
dvander@1
|
208 |
|
|
dvander@1
|
209 |
uint32_t entry() const { |
|
dvander@1
|
210 |
return hash_ & (capacity_ - 1); |
|
dvander@1
|
211 |
} |
|
dvander@1
|
212 |
uint32_t next() { |
|
dvander@1
|
213 |
hash_++; |
|
dvander@1
|
214 |
return entry(); |
|
dvander@1
|
215 |
} |
|
dvander@1
|
216 |
}; |
|
dvander@1
|
217 |
|
|
dvander@1
|
218 |
bool underloaded() const { |
|
dvander@1
|
219 |
// Check if the table is underloaded: < 25% entries used. |
|
dvander@1
|
220 |
return (capacity_ > kMinCapacity) && (nelements_ + ndeleted_ < capacity_ / 4); |
|
dvander@1
|
221 |
} |
|
dvander@1
|
222 |
bool overloaded() const { |
|
dvander@1
|
223 |
// Grow if the table is overloaded: > 75% entries used. |
|
dvander@1
|
224 |
return (nelements_ + ndeleted_) > ((capacity_ / 2) + (capacity_ / 4)); |
|
dvander@1
|
225 |
} |
|
dvander@1
|
226 |
|
|
dvander@1
|
227 |
bool shrink() { |
|
dvander@1
|
228 |
if ((capacity_ >> 1) < minCapacity_) |
|
dvander@1
|
229 |
return true; |
|
dvander@1
|
230 |
return changeCapacity(capacity_ >> 1); |
|
dvander@1
|
231 |
} |
|
dvander@1
|
232 |
|
|
dvander@1
|
233 |
bool grow() { |
|
dvander@1
|
234 |
if (capacity_ >= kMaxCapacity) { |
|
dvander@1
|
235 |
this->reportAllocationOverflow(); |
|
dvander@1
|
236 |
return false; |
|
dvander@1
|
237 |
} |
|
dvander@1
|
238 |
return changeCapacity(capacity_ << 1); |
|
dvander@1
|
239 |
} |
|
dvander@1
|
240 |
|
|
dvander@1
|
241 |
bool changeCapacity(uint32_t newCapacity) { |
|
dvander@1
|
242 |
assert(newCapacity <= kMaxCapacity); |
|
dvander@1
|
243 |
|
|
dvander@1
|
244 |
Entry *newTable = createTable(newCapacity); |
|
dvander@1
|
245 |
if (!newTable) |
|
dvander@1
|
246 |
return false; |
|
dvander@1
|
247 |
|
|
dvander@1
|
248 |
Entry *oldTable = table_; |
|
dvander@1
|
249 |
uint32_t oldCapacity = capacity_; |
|
dvander@1
|
250 |
|
|
dvander@1
|
251 |
table_ = newTable; |
|
dvander@1
|
252 |
capacity_ = newCapacity; |
|
dvander@1
|
253 |
ndeleted_ = 0; |
|
dvander@1
|
254 |
|
|
dvander@1
|
255 |
for (uint32_t i = 0; i < oldCapacity; i++) { |
|
dvander@1
|
256 |
Entry &oldEntry = oldTable[i]; |
|
dvander@1
|
257 |
if (oldEntry.isLive()) { |
|
dvander@1
|
258 |
Insert p = insertUnique(oldEntry.hash()); |
|
dvander@1
|
259 |
p.entry().setHash(p.hash(), oldEntry.payload()); |
|
dvander@1
|
260 |
} |
|
dvander@1
|
261 |
oldEntry.destruct(); |
|
dvander@1
|
262 |
} |
|
dvander@1
|
263 |
this->free(oldTable); |
|
dvander@1
|
264 |
|
|
dvander@1
|
265 |
return true; |
|
dvander@1
|
266 |
} |
|
dvander@1
|
267 |
|
|
dvander@1
|
268 |
// For use when the key is known to be unique. |
|
dvander@1
|
269 |
Insert insertUnique(uint32_t hash) { |
|
dvander@1
|
270 |
Probulator probulator(hash, capacity_); |
|
dvander@1
|
271 |
|
|
dvander@1
|
272 |
Entry *e = &table_[probulator.entry()]; |
|
dvander@1
|
273 |
for (;;) { |
|
dvander@1
|
274 |
if (e->free() || e->removed()) |
|
dvander@1
|
275 |
break; |
|
dvander@1
|
276 |
e = &table_[probulator.next()]; |
|
dvander@1
|
277 |
} |
|
dvander@1
|
278 |
|
|
dvander@1
|
279 |
return Insert(e, hash); |
|
dvander@1
|
280 |
} |
|
dvander@1
|
281 |
|
|
dvander@1
|
282 |
template <typename Key> |
|
dvander@1
|
283 |
Result lookup(const Key &key) { |
|
dvander@1
|
284 |
uint32_t hash = computeHash(key); |
|
dvander@1
|
285 |
Probulator probulator(hash, capacity_); |
|
dvander@1
|
286 |
|
|
dvander@1
|
287 |
Entry *e = &table_[probulator.entry()]; |
|
dvander@1
|
288 |
for (;;) { |
|
dvander@1
|
289 |
if (e->free()) |
|
dvander@1
|
290 |
break; |
|
dvander@1
|
291 |
if (e->isLive() && |
|
dvander@1
|
292 |
e->sameHash(hash) && |
|
dvander@1
|
293 |
HashPolicy::matches(key, e->payload())) |
|
dvander@1
|
294 |
{ |
|
dvander@1
|
295 |
return Result(e); |
|
dvander@1
|
296 |
} |
|
dvander@1
|
297 |
e = &table_[probulator.next()]; |
|
dvander@1
|
298 |
} |
|
dvander@1
|
299 |
|
|
dvander@1
|
300 |
return Result(e); |
|
dvander@1
|
301 |
} |
|
dvander@1
|
302 |
|
|
dvander@1
|
303 |
template <typename Key> |
|
dvander@1
|
304 |
Insert lookupForAdd(const Key &key) { |
|
dvander@1
|
305 |
uint32_t hash = computeHash(key); |
|
dvander@1
|
306 |
Probulator probulator(hash, capacity_); |
|
dvander@1
|
307 |
|
|
dvander@1
|
308 |
Entry *e = &table_[probulator.entry()]; |
|
dvander@1
|
309 |
for (;;) { |
|
dvander@1
|
310 |
if (!e->isLive()) |
|
dvander@1
|
311 |
break; |
|
dvander@1
|
312 |
if (e->sameHash(hash) && HashPolicy::matches(key, e->payload())) |
|
dvander@1
|
313 |
break; |
|
dvander@1
|
314 |
e = &table_[probulator.next()]; |
|
dvander@1
|
315 |
} |
|
dvander@1
|
316 |
|
|
dvander@1
|
317 |
return Insert(e, hash); |
|
dvander@1
|
318 |
} |
|
dvander@1
|
319 |
|
|
dvander@1
|
320 |
bool internalAdd(Insert &i, const Payload &payload) { |
|
dvander@1
|
321 |
assert(!i.found()); |
|
dvander@1
|
322 |
|
|
dvander@1
|
323 |
// If the entry is deleted, just re-use the slot. |
|
dvander@1
|
324 |
if (i.entry().removed()) { |
|
dvander@1
|
325 |
ndeleted_--; |
|
dvander@1
|
326 |
} else { |
|
dvander@1
|
327 |
// Otherwise, see if we're at max capacity. |
|
dvander@1
|
328 |
if (nelements_ == kMaxCapacity) { |
|
dvander@1
|
329 |
this->reportAllocationOverflow(); |
|
dvander@1
|
330 |
return false; |
|
dvander@1
|
331 |
} |
|
dvander@1
|
332 |
|
|
dvander@1
|
333 |
// Check if the table is over or underloaded. The table is always at |
|
dvander@1
|
334 |
// least 25% free, so this check is enough to guarantee one free slot. |
|
dvander@1
|
335 |
// (Without one free slot, insertion search could infinite loop.) |
|
dvander@1
|
336 |
uint32_t oldCapacity = capacity_; |
|
dvander@1
|
337 |
if (!checkDensity()) |
|
dvander@1
|
338 |
return false; |
|
dvander@1
|
339 |
|
|
dvander@1
|
340 |
// If the table changed size, we need to find a new insertion point. |
|
dvander@1
|
341 |
// Note that a removed entry is impossible: either we caught it above, |
|
dvander@1
|
342 |
// or we just resized and no entries are removed. |
|
dvander@1
|
343 |
if (capacity_ != oldCapacity) |
|
dvander@1
|
344 |
i = insertUnique(i.hash()); |
|
dvander@1
|
345 |
} |
|
dvander@1
|
346 |
|
|
dvander@1
|
347 |
i.entry().setHash(i.hash(), payload); |
|
dvander@1
|
348 |
nelements_++; |
|
dvander@1
|
349 |
return true; |
|
dvander@1
|
350 |
} |
|
dvander@1
|
351 |
|
|
dvander@1
|
352 |
void removeEntry(Entry &e) { |
|
dvander@1
|
353 |
assert(e.isLive()); |
|
dvander@1
|
354 |
e.setRemoved(); |
|
dvander@1
|
355 |
ndeleted_++; |
|
dvander@1
|
356 |
nelements_--; |
|
dvander@1
|
357 |
} |
|
dvander@1
|
358 |
|
|
dvander@1
|
359 |
public: |
|
dvander@8
|
360 |
HashTable(AllocPolicy ap = AllocPolicy()) |
|
dvander@1
|
361 |
: AllocPolicy(ap), |
|
dvander@1
|
362 |
capacity_(0), |
|
dvander@1
|
363 |
nelements_(0), |
|
dvander@1
|
364 |
ndeleted_(0), |
|
dvander@1
|
365 |
table_(NULL), |
|
dvander@1
|
366 |
minCapacity_(kMinCapacity) |
|
dvander@1
|
367 |
{ |
|
dvander@1
|
368 |
} |
|
dvander@1
|
369 |
|
|
dvander@1
|
370 |
~HashTable() |
|
dvander@1
|
371 |
{ |
|
dvander@1
|
372 |
for (uint32_t i = 0; i < capacity_; i++) |
|
dvander@1
|
373 |
table_[i].destruct(); |
|
dvander@1
|
374 |
this->free(table_); |
|
dvander@1
|
375 |
} |
|
dvander@1
|
376 |
|
|
dvander@1
|
377 |
bool init(uint32_t capacity = 0) { |
|
dvander@1
|
378 |
if (capacity < kMinCapacity) { |
|
dvander@1
|
379 |
capacity = kMinCapacity; |
|
dvander@1
|
380 |
} else if (capacity > kMaxCapacity) { |
|
dvander@1
|
381 |
this->reportAllocationOverflow(); |
|
dvander@1
|
382 |
return false; |
|
dvander@1
|
383 |
} |
|
dvander@1
|
384 |
|
|
dvander@1
|
385 |
minCapacity_ = capacity; |
|
dvander@1
|
386 |
|
|
dvander@1
|
387 |
assert(IsPowerOfTwo(capacity)); |
|
dvander@1
|
388 |
capacity_ = capacity; |
|
dvander@1
|
389 |
|
|
dvander@1
|
390 |
table_ = createTable(capacity_); |
|
dvander@1
|
391 |
if (!table_) |
|
dvander@1
|
392 |
return false; |
|
dvander@1
|
393 |
|
|
dvander@1
|
394 |
return true; |
|
dvander@1
|
395 |
} |
|
dvander@1
|
396 |
|
|
dvander@1
|
397 |
// The Result object must not be used past mutating table operations. |
|
dvander@1
|
398 |
template <typename Key> |
|
dvander@1
|
399 |
Result find(const Key &key) { |
|
dvander@1
|
400 |
return lookup(key); |
|
dvander@1
|
401 |
} |
|
dvander@1
|
402 |
|
|
dvander@1
|
403 |
// The Insert object must not be used past mutating table operations. |
|
dvander@1
|
404 |
template <typename Key> |
|
dvander@1
|
405 |
Insert findForAdd(const Key &key) { |
|
dvander@1
|
406 |
return lookupForAdd(key); |
|
dvander@1
|
407 |
} |
|
dvander@1
|
408 |
|
|
dvander@1
|
409 |
template <typename Key> |
|
dvander@1
|
410 |
void removeIfExists(const Key &key) { |
|
dvander@1
|
411 |
Result r = find(key); |
|
dvander@1
|
412 |
if (!r.found()) |
|
dvander@1
|
413 |
return; |
|
dvander@1
|
414 |
remove(r); |
|
dvander@1
|
415 |
} |
|
dvander@1
|
416 |
|
|
dvander@1
|
417 |
void remove(Result &r) { |
|
dvander@1
|
418 |
assert(r.found()); |
|
dvander@1
|
419 |
removeEntry(r.entry()); |
|
dvander@1
|
420 |
} |
|
dvander@1
|
421 |
|
|
dvander@1
|
422 |
// The table must not have been mutated in between findForAdd() and add(). |
|
dvander@1
|
423 |
// The Insert object is still valid after add() returns, however. |
|
dvander@1
|
424 |
bool add(Insert &i, const Payload &payload) { |
|
dvander@1
|
425 |
return internalAdd(i, payload); |
|
dvander@1
|
426 |
} |
|
dvander@8
|
427 |
bool add(Insert &i) { |
|
dvander@8
|
428 |
return internalAdd(i, Payload()); |
|
dvander@8
|
429 |
} |
|
dvander@1
|
430 |
|
|
dvander@1
|
431 |
bool checkDensity() { |
|
dvander@1
|
432 |
if (underloaded()) |
|
dvander@1
|
433 |
return shrink(); |
|
dvander@1
|
434 |
if (overloaded()) |
|
dvander@1
|
435 |
return grow(); |
|
dvander@1
|
436 |
return true; |
|
dvander@1
|
437 |
} |
|
dvander@1
|
438 |
|
|
dvander@9
|
439 |
void clear() { |
|
dvander@9
|
440 |
for (size_t i = 0; i < capacity_; i++) { |
|
dvander@9
|
441 |
table_[i].setFree(); |
|
dvander@9
|
442 |
} |
|
dvander@9
|
443 |
ndeleted_ = 0; |
|
dvander@9
|
444 |
nelements_ = 0; |
|
dvander@9
|
445 |
} |
|
dvander@9
|
446 |
|
|
dvander@1
|
447 |
size_t estimateMemoryUse() const { |
|
dvander@1
|
448 |
return sizeof(Entry) * capacity_; |
|
dvander@1
|
449 |
} |
|
dvander@1
|
450 |
|
|
dvander@1
|
451 |
public: |
|
dvander@1
|
452 |
// It is illegal to mutate a HashTable during iteration. |
|
dvander@1
|
453 |
class iterator |
|
dvander@1
|
454 |
{ |
|
dvander@1
|
455 |
public: |
|
dvander@1
|
456 |
iterator(HashTable *table) |
|
dvander@1
|
457 |
: table_(table), |
|
dvander@1
|
458 |
i_(table->table_), |
|
dvander@1
|
459 |
end_(table->table_ + table->capacity_) |
|
dvander@1
|
460 |
{ |
|
dvander@1
|
461 |
while (i_ < end_ && !i_->isLive()) |
|
dvander@1
|
462 |
i_++; |
|
dvander@1
|
463 |
} |
|
dvander@1
|
464 |
|
|
dvander@1
|
465 |
bool empty() const { |
|
dvander@1
|
466 |
return i_ == end_; |
|
dvander@1
|
467 |
} |
|
dvander@1
|
468 |
|
|
dvander@1
|
469 |
void erase() { |
|
dvander@1
|
470 |
assert(!empty()); |
|
dvander@1
|
471 |
table_->removeEntry(*i_); |
|
dvander@1
|
472 |
} |
|
dvander@1
|
473 |
|
|
dvander@1
|
474 |
const Payload &operator *() const { |
|
dvander@1
|
475 |
return i_->payload(); |
|
dvander@1
|
476 |
} |
|
dvander@1
|
477 |
|
|
dvander@1
|
478 |
void next() { |
|
dvander@1
|
479 |
do { |
|
dvander@1
|
480 |
i_++; |
|
dvander@1
|
481 |
} while (i_ < end_ && !i_->isLive()); |
|
dvander@1
|
482 |
} |
|
dvander@1
|
483 |
|
|
dvander@1
|
484 |
private: |
|
dvander@1
|
485 |
HashTable *table_; |
|
dvander@1
|
486 |
Entry *i_; |
|
dvander@1
|
487 |
Entry *end_; |
|
dvander@1
|
488 |
}; |
|
dvander@1
|
489 |
|
|
dvander@1
|
490 |
private: |
|
dvander@1
|
491 |
HashTable(const HashTable &other) KE_DELETE; |
|
dvander@1
|
492 |
HashTable &operator =(const HashTable &other) KE_DELETE; |
|
dvander@1
|
493 |
|
|
dvander@1
|
494 |
private: |
|
dvander@1
|
495 |
uint32_t capacity_; |
|
dvander@1
|
496 |
uint32_t nelements_; |
|
dvander@1
|
497 |
uint32_t ndeleted_; |
|
dvander@1
|
498 |
Entry *table_; |
|
dvander@1
|
499 |
uint32_t minCapacity_; |
|
dvander@1
|
500 |
}; |
|
dvander@1
|
501 |
|
|
dvander@1
|
502 |
// Bob Jenkin's one-at-a-time hash function[1]. |
|
dvander@1
|
503 |
// |
|
dvander@1
|
504 |
// [1] http://burtleburtle.net/bob/hash/doobs.html |
|
dvander@1
|
505 |
class CharacterStreamHasher |
|
dvander@1
|
506 |
{ |
|
dvander@1
|
507 |
uint32_t hash; |
|
dvander@1
|
508 |
|
|
dvander@1
|
509 |
public: |
|
dvander@1
|
510 |
CharacterStreamHasher() |
|
dvander@1
|
511 |
: hash(0) |
|
dvander@1
|
512 |
{ } |
|
dvander@1
|
513 |
|
|
dvander@1
|
514 |
void add(char c) { |
|
dvander@1
|
515 |
hash += c; |
|
dvander@1
|
516 |
hash += (hash << 10); |
|
dvander@1
|
517 |
hash ^= (hash >> 6); |
|
dvander@1
|
518 |
} |
|
dvander@1
|
519 |
|
|
dvander@1
|
520 |
void add(const char *s, size_t length) { |
|
dvander@1
|
521 |
for (size_t i = 0; i < length; i++) |
|
dvander@1
|
522 |
add(s[i]); |
|
dvander@1
|
523 |
} |
|
dvander@1
|
524 |
|
|
dvander@1
|
525 |
uint32_t result() { |
|
dvander@1
|
526 |
hash += (hash << 3); |
|
dvander@1
|
527 |
hash ^= (hash >> 11); |
|
dvander@1
|
528 |
hash += (hash << 15); |
|
dvander@1
|
529 |
return hash; |
|
dvander@1
|
530 |
} |
|
dvander@1
|
531 |
}; |
|
dvander@1
|
532 |
|
|
dvander@1
|
533 |
static inline uint32_t |
|
dvander@1
|
534 |
HashCharSequence(const char *s, size_t length) |
|
dvander@1
|
535 |
{ |
|
dvander@1
|
536 |
CharacterStreamHasher hasher; |
|
dvander@1
|
537 |
hasher.add(s, length); |
|
dvander@1
|
538 |
return hasher.result(); |
|
dvander@1
|
539 |
} |
|
dvander@1
|
540 |
|
|
dvander@1
|
541 |
static inline uint32_t |
|
dvander@1
|
542 |
FastHashCharSequence(const char *s, size_t length) |
|
dvander@1
|
543 |
{ |
|
dvander@1
|
544 |
uint32_t hash = 0; |
|
dvander@1
|
545 |
for (size_t i = 0; i < length; i++) |
|
dvander@1
|
546 |
hash = s[i] + (hash << 6) + (hash << 16) - hash; |
|
dvander@1
|
547 |
return hash; |
|
dvander@1
|
548 |
} |
|
dvander@1
|
549 |
|
|
dvander@1
|
550 |
// From http://burtleburtle.net/bob/hash/integer.html |
|
dvander@1
|
551 |
static inline uint32_t |
|
dvander@1
|
552 |
HashInt32(int32_t a) |
|
dvander@1
|
553 |
{ |
|
dvander@1
|
554 |
a = (a ^ 61) ^ (a >> 16); |
|
dvander@1
|
555 |
a = a + (a << 3); |
|
dvander@1
|
556 |
a = a ^ (a >> 4); |
|
dvander@1
|
557 |
a = a * 0x27d4eb2d; |
|
dvander@1
|
558 |
a = a ^ (a >> 15); |
|
dvander@1
|
559 |
return a; |
|
dvander@1
|
560 |
} |
|
dvander@1
|
561 |
|
|
dvander@1
|
562 |
// From http://www.cris.com/~Ttwang/tech/inthash.htm |
|
dvander@1
|
563 |
static inline uint32_t |
|
dvander@1
|
564 |
HashInt64(int64_t key) |
|
dvander@1
|
565 |
{ |
|
dvander@1
|
566 |
key = (~key) + (key << 18); // key = (key << 18) - key - 1; |
|
dvander@1
|
567 |
key = key ^ (uint64(key) >> 31); |
|
dvander@1
|
568 |
key = key * 21; // key = (key + (key << 2)) + (key << 4); |
|
dvander@1
|
569 |
key = key ^ (uint64(key) >> 11); |
|
dvander@1
|
570 |
key = key + (key << 6); |
|
dvander@1
|
571 |
key = key ^ (uint64(key) >> 22); |
|
dvander@1
|
572 |
return uint32(key); |
|
dvander@1
|
573 |
} |
|
dvander@1
|
574 |
|
|
dvander@1
|
575 |
template <size_t Size> |
|
dvander@1
|
576 |
static inline uint32_t |
|
dvander@1
|
577 |
HashInteger(uintptr_t value); |
|
dvander@1
|
578 |
|
|
dvander@1
|
579 |
template <> |
|
dvander@1
|
580 |
inline uint32_t |
|
dvander@1
|
581 |
HashInteger<4>(uintptr_t value) |
|
dvander@1
|
582 |
{ |
|
dvander@1
|
583 |
return HashInt32(value); |
|
dvander@1
|
584 |
} |
|
dvander@1
|
585 |
|
|
dvander@1
|
586 |
template <> |
|
dvander@1
|
587 |
inline uint32_t |
|
dvander@1
|
588 |
HashInteger<8>(uintptr_t value) |
|
dvander@1
|
589 |
{ |
|
dvander@1
|
590 |
return HashInt64(value); |
|
dvander@1
|
591 |
} |
|
dvander@1
|
592 |
|
|
dvander@1
|
593 |
static inline uint32_t |
|
dvander@1
|
594 |
HashPointer(void *ptr) |
|
dvander@1
|
595 |
{ |
|
dvander@1
|
596 |
return HashInteger<sizeof(ptr)>(reinterpret_cast<uintptr_t>(ptr)); |
|
dvander@1
|
597 |
} |
|
dvander@1
|
598 |
|
|
dvander@1
|
599 |
} // namespace ke |
|
dvander@1
|
600 |
|
|
dvander@1
|
601 |
#endif // _INCLUDE_KEIMA_HASHTABLE_H_ |