Add tests.
1 // vim: set sts=8 ts=2 sw=2 tw=99 et:
3 // Copyright (C) 2013, David Anderson and AlliedModders LLC
4 // All rights reserved.
6 // Redistribution and use in source and binary forms, with or without
7 // modification, are permitted provided that the following conditions are met:
9 // * Redistributions of source code must retain the above copyright notice, this
10 // list of conditions and the following disclaimer.
11 // * Redistributions in binary form must reproduce the above copyright notice,
12 // this list of conditions and the following disclaimer in the documentation
13 // and/or other materials provided with the distribution.
14 // * Neither the name of AlliedModders LLC nor the names of its contributors
15 // may be used to endorse or promote products derived from this software
16 // without specific prior written permission.
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
22 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 // POSSIBILITY OF SUCH DAMAGE.
30 #ifndef _INCLUDE_KEIMA_HASHTABLE_H_
31 #define _INCLUDE_KEIMA_HASHTABLE_H_
36 #include "am-allocator-policies.h"
37 #include "am-utility.h"
38 #include "am-moveable.h"
50 static const uint32_t kFreeHash = 0;
51 static const uint32_t kRemovedHash = 1;
54 void setHash(uint32_t hash) {
60 void construct(const T &t) {
63 void construct(Moveable<T> t) {
66 uint32_t hash() const {
84 bool removed() const {
85 return hash_ == kRemovedHash;
88 return hash_ == kFreeHash;
91 return hash_ > kRemovedHash;
97 bool sameHash(uint32_t hash) const {
102 HashTableEntry(const HashTableEntry &other) KE_DELETE;
103 HashTableEntry &operator =(const HashTableEntry &other) KE_DELETE;
107 // The HashPolicy for the table must have the following members:
110 // static uint32_t hash(const LookupType &key);
111 // static bool matches(const LookupType &key, const Payload &other);
113 // Payload must be a type, and LookupType is any type that lookups will be
114 // performed with (these functions can be overloaded). Example:
117 // typedef KeyValuePair Payload;
118 // static uint32 hash(const Key &key) {
121 // static bool matches(const Key &key, const KeyValuePair &pair) {
126 // Note that the table is not usable until init() has been called.
128 template <typename HashPolicy, typename AllocPolicy = SystemAllocatorPolicy>
129 class HashTable : public AllocPolicy
131 friend class iterator;
133 typedef typename HashPolicy::Payload Payload;
134 typedef detail::HashTableEntry<Payload> Entry;
137 static const uint32_t kMinCapacity = 16;
138 static const uint32_t kMaxCapacity = INT_MAX / sizeof(Entry);
140 template <typename Key>
141 uint32_t computeHash(const Key &key) {
142 // Multiply by golden ratio.
143 uint32_t hash = HashPolicy::hash(key) * 0x9E3779B9;
144 if (hash == Entry::kFreeHash || hash == Entry::kRemovedHash)
149 Entry *createTable(uint32_t capacity) {
150 assert(capacity <= kMaxCapacity);
152 Entry *table = (Entry *)this->malloc(capacity * sizeof(Entry));
156 for (size_t i = 0; i < capacity; i++)
157 table[i].initialize();
165 friend class HashTable;
178 Payload * operator ->() {
179 return &entry_->payload();
181 Payload & operator *() {
182 return entry_->payload();
186 return entry_->isLive();
190 class Insert : public Result
195 Insert(Entry *entry, uint32_t hash)
201 uint32_t hash() const {
212 Probulator(uint32_t hash, uint32_t capacity)
216 assert(IsPowerOfTwo(capacity_));
219 uint32_t entry() const {
220 return hash_ & (capacity_ - 1);
228 bool underloaded() const {
229 // Check if the table is underloaded: < 25% entries used.
230 return (capacity_ > kMinCapacity) && (nelements_ + ndeleted_ < capacity_ / 4);
232 bool overloaded() const {
233 // Grow if the table is overloaded: > 75% entries used.
234 return (nelements_ + ndeleted_) > ((capacity_ / 2) + (capacity_ / 4));
238 if ((capacity_ >> 1) < minCapacity_)
240 return changeCapacity(capacity_ >> 1);
244 if (capacity_ >= kMaxCapacity) {
245 this->reportAllocationOverflow();
248 return changeCapacity(capacity_ << 1);
251 bool changeCapacity(uint32_t newCapacity) {
252 assert(newCapacity <= kMaxCapacity);
254 Entry *newTable = createTable(newCapacity);
258 Entry *oldTable = table_;
259 uint32_t oldCapacity = capacity_;
262 capacity_ = newCapacity;
265 for (uint32_t i = 0; i < oldCapacity; i++) {
266 Entry &oldEntry = oldTable[i];
267 if (oldEntry.isLive()) {
268 Insert p = insertUnique(oldEntry.hash());
269 p.entry().setHash(p.hash());
270 p.entry().construct(Moveable<Payload>(oldEntry.payload()));
274 this->free(oldTable);
279 // For use when the key is known to be unique.
280 Insert insertUnique(uint32_t hash) {
281 Probulator probulator(hash, capacity_);
283 Entry *e = &table_[probulator.entry()];
285 if (e->free() || e->removed())
287 e = &table_[probulator.next()];
290 return Insert(e, hash);
293 template <typename Key>
294 Result lookup(const Key &key) {
295 uint32_t hash = computeHash(key);
296 Probulator probulator(hash, capacity_);
298 Entry *e = &table_[probulator.entry()];
304 HashPolicy::matches(key, e->payload()))
308 e = &table_[probulator.next()];
314 template <typename Key>
315 Insert lookupForAdd(const Key &key) {
316 uint32_t hash = computeHash(key);
317 Probulator probulator(hash, capacity_);
319 Entry *e = &table_[probulator.entry()];
323 if (e->sameHash(hash) && HashPolicy::matches(key, e->payload()))
325 e = &table_[probulator.next()];
328 return Insert(e, hash);
331 bool internalAdd(Insert &i) {
334 // If the entry is deleted, just re-use the slot.
335 if (i.entry().removed()) {
338 // Otherwise, see if we're at max capacity.
339 if (nelements_ == kMaxCapacity) {
340 this->reportAllocationOverflow();
344 // Check if the table is over or underloaded. The table is always at
345 // least 25% free, so this check is enough to guarantee one free slot.
346 // (Without one free slot, insertion search could infinite loop.)
347 uint32_t oldCapacity = capacity_;
351 // If the table changed size, we need to find a new insertion point.
352 // Note that a removed entry is impossible: either we caught it above,
353 // or we just resized and no entries are removed.
354 if (capacity_ != oldCapacity)
355 i = insertUnique(i.hash());
359 i.entry().setHash(i.hash());
363 void removeEntry(Entry &e) {
371 HashTable(AllocPolicy ap = AllocPolicy())
377 minCapacity_(kMinCapacity)
383 for (uint32_t i = 0; i < capacity_; i++)
384 table_[i].destruct();
388 bool init(uint32_t capacity = 0) {
389 if (capacity < kMinCapacity) {
390 capacity = kMinCapacity;
391 } else if (capacity > kMaxCapacity) {
392 this->reportAllocationOverflow();
396 minCapacity_ = capacity;
398 assert(IsPowerOfTwo(capacity));
399 capacity_ = capacity;
401 table_ = createTable(capacity_);
408 // The Result object must not be used past mutating table operations.
409 template <typename Key>
410 Result find(const Key &key) {
414 // The Insert object must not be used past mutating table operations.
415 template <typename Key>
416 Insert findForAdd(const Key &key) {
417 return lookupForAdd(key);
420 template <typename Key>
421 void removeIfExists(const Key &key) {
422 Result r = find(key);
428 void remove(Result &r) {
430 removeEntry(r.entry());
433 // The table must not have been mutated in between findForAdd() and add().
434 // The Insert object is still valid after add() returns, however.
435 bool add(Insert &i, const Payload &payload) {
438 i.entry().construct(payload);
441 bool add(Insert &i, Moveable<Payload> payload) {
444 i.entry().construct(payload);
447 bool add(Insert &i) {
450 i.entry().construct();
454 bool checkDensity() {
463 for (size_t i = 0; i < capacity_; i++) {
470 size_t elements() const {
474 size_t estimateMemoryUse() const {
475 return sizeof(Entry) * capacity_;
479 // It is illegal to mutate a HashTable during iteration.
483 iterator(HashTable *table)
486 end_(table->table_ + table->capacity_)
488 while (i_ < end_ && !i_->isLive())
498 table_->removeEntry(*i_);
501 Payload *operator ->() const {
502 return &i_->payload();
504 Payload &operator *() const {
505 return i_->payload();
511 } while (i_ < end_ && !i_->isLive());
521 HashTable(const HashTable &other) KE_DELETE;
522 HashTable &operator =(const HashTable &other) KE_DELETE;
529 uint32_t minCapacity_;
532 // Bob Jenkin's one-at-a-time hash function[1].
534 // [1] http://burtleburtle.net/bob/hash/doobs.html
535 class CharacterStreamHasher
540 CharacterStreamHasher()
546 hash += (hash << 10);
550 void add(const char *s, size_t length) {
551 for (size_t i = 0; i < length; i++)
557 hash ^= (hash >> 11);
558 hash += (hash << 15);
563 static inline uint32_t
564 HashCharSequence(const char *s, size_t length)
566 CharacterStreamHasher hasher;
567 hasher.add(s, length);
568 return hasher.result();
571 static inline uint32_t
572 FastHashCharSequence(const char *s, size_t length)
575 for (size_t i = 0; i < length; i++)
576 hash = s[i] + (hash << 6) + (hash << 16) - hash;
580 // From http://burtleburtle.net/bob/hash/integer.html
581 static inline uint32_t
584 a = (a ^ 61) ^ (a >> 16);
592 // From http://www.cris.com/~Ttwang/tech/inthash.htm
593 static inline uint32_t
594 HashInt64(int64_t key)
596 key = (~key) + (key << 18); // key = (key << 18) - key - 1;
597 key = key ^ (uint64_t(key) >> 31);
598 key = key * 21; // key = (key + (key << 2)) + (key << 4);
599 key = key ^ (uint64_t(key) >> 11);
600 key = key + (key << 6);
601 key = key ^ (uint64_t(key) >> 22);
602 return uint32_t(key);
605 template <size_t Size>
606 static inline uint32_t
607 HashInteger(uintptr_t value);
611 HashInteger<4>(uintptr_t value)
613 return HashInt32(value);
618 HashInteger<8>(uintptr_t value)
620 return HashInt64(value);
623 static inline uint32_t
624 HashPointer(void *ptr)
626 return HashInteger<sizeof(ptr)>(reinterpret_cast<uintptr_t>(ptr));
631 #endif // _INCLUDE_KEIMA_HASHTABLE_H_