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