Import HashTable.
Import HashTable.
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/include/am-hashtable.h Fri Aug 23 22:36:08 2013 -0700
1.3 @@ -0,0 +1,586 @@
1.4 +// vim: set sts=8 ts=2 sw=2 tw=99 et:
1.5 +//
1.6 +// Copyright (C) 2013, David Anderson and AlliedModders LLC
1.7 +// All rights reserved.
1.8 +//
1.9 +// Redistribution and use in source and binary forms, with or without
1.10 +// modification, are permitted provided that the following conditions are met:
1.11 +//
1.12 +// * Redistributions of source code must retain the above copyright notice, this
1.13 +// list of conditions and the following disclaimer.
1.14 +// * Redistributions in binary form must reproduce the above copyright notice,
1.15 +// this list of conditions and the following disclaimer in the documentation
1.16 +// and/or other materials provided with the distribution.
1.17 +// * Neither the name of AlliedModders LLC nor the names of its contributors
1.18 +// may be used to endorse or promote products derived from this software
1.19 +// without specific prior written permission.
1.20 +//
1.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.22 +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.23 +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.24 +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.25 +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.26 +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.27 +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.28 +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.29 +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.30 +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.31 +// POSSIBILITY OF SUCH DAMAGE.
1.32 +
1.33 +#ifndef _INCLUDE_KEIMA_HASHTABLE_H_
1.34 +#define _INCLUDE_KEIMA_HASHTABLE_H_
1.35 +
1.36 +#include <new>
1.37 +#include <limits.h>
1.38 +#include <stdlib.h>
1.39 +#include "am-utility.h"
1.40 +
1.41 +namespace ke {
1.42 +
1.43 +namespace detail {
1.44 + template <typename T>
1.45 + class HashTableEntry
1.46 + {
1.47 + uint32_t hash_;
1.48 + T t_;
1.49 +
1.50 + public:
1.51 + static const uint32_t kFreeHash = 0;
1.52 + static const uint32_t kRemovedHash = 1;
1.53 +
1.54 + public:
1.55 + void setHash(uint32_t hash, const T &t) {
1.56 + hash_ = hash;
1.57 + new (&t_) T(t);
1.58 + }
1.59 + uint32_t hash() const {
1.60 + return hash_;
1.61 + }
1.62 + void setRemoved() {
1.63 + destruct();
1.64 + hash_ = kRemovedHash;
1.65 + }
1.66 + void initialize() {
1.67 + hash_ = kFreeHash;
1.68 + }
1.69 + void destruct() {
1.70 + if (isLive())
1.71 + t_.~T();
1.72 + }
1.73 + bool removed() const {
1.74 + return hash_ == kRemovedHash;
1.75 + }
1.76 + bool free() const {
1.77 + return hash_ == kFreeHash;
1.78 + }
1.79 + bool isLive() const {
1.80 + return hash_ > kRemovedHash;
1.81 + }
1.82 + T &payload() {
1.83 + assert(isLive());
1.84 + return t_;
1.85 + }
1.86 + bool sameHash(uint32_t hash) const {
1.87 + return hash_ == hash;
1.88 + }
1.89 +
1.90 + private:
1.91 + HashTableEntry(const HashTableEntry &other) KE_DELETE;
1.92 + HashTableEntry &operator =(const HashTableEntry &other) KE_DELETE;
1.93 + };
1.94 +}
1.95 +
1.96 +// The HashPolicy for the table must have the following members:
1.97 +//
1.98 +// Payload
1.99 +// static uint32_t hash(const LookupType &key);
1.100 +// static bool matches(const LookupType &key, const Payload &other);
1.101 +//
1.102 +// Payload must be a type, and LookupType is any type that lookups will be
1.103 +// performed with (these functions can be overloaded). Example:
1.104 +//
1.105 +// struct Policy {
1.106 +// typedef KeyValuePair Payload;
1.107 +// static uint32 hash(const Key &key) {
1.108 +// ...
1.109 +// }
1.110 +// static bool matches(const Key &key, const KeyValuePair &pair) {
1.111 +// ...
1.112 +// }
1.113 +// };
1.114 +//
1.115 +// Note that the table is not usable until init() has been called.
1.116 +//
1.117 +template <typename HashPolicy, typename AllocPolicy = SystemAllocatorPolicy>
1.118 +class HashTable : public AllocPolicy
1.119 +{
1.120 + friend class iterator;
1.121 +
1.122 + typedef typename HashPolicy::Payload Payload;
1.123 + typedef detail::HashTableEntry<Payload> Entry;
1.124 +
1.125 + private:
1.126 + static const uint32_t kMinCapacity = 16;
1.127 + static const uint32_t kMaxCapacity = INT_MAX / sizeof(Entry);
1.128 +
1.129 + template <typename Key>
1.130 + uint32_t computeHash(const Key &key) {
1.131 + // Multiply by golden ratio.
1.132 + uint32_t hash = HashPolicy::hash(key) * 0x9E3779B9;
1.133 + if (hash == Entry::kFreeHash || hash == Entry::kRemovedHash)
1.134 + hash += 2;
1.135 + return hash;
1.136 + }
1.137 +
1.138 + Entry *createTable(uint32_t capacity) {
1.139 + assert(capacity <= kMaxCapacity);
1.140 +
1.141 + Entry *table = (Entry *)this->malloc(capacity * sizeof(Entry));
1.142 + if (!table)
1.143 + return NULL;
1.144 +
1.145 + for (size_t i = 0; i < capacity; i++)
1.146 + table[i].initialize();
1.147 +
1.148 + return table;
1.149 + }
1.150 +
1.151 + public:
1.152 + class Result
1.153 + {
1.154 + friend class HashTable;
1.155 +
1.156 + Entry *entry_;
1.157 +
1.158 + Entry &entry() {
1.159 + return *entry_;
1.160 + }
1.161 +
1.162 + public:
1.163 + Result(Entry *entry)
1.164 + : entry_(entry)
1.165 + { }
1.166 +
1.167 + Payload * operator ->() {
1.168 + return &entry_->payload();
1.169 + }
1.170 + Payload & operator *() {
1.171 + return entry_->payload();
1.172 + }
1.173 +
1.174 + bool found() const {
1.175 + return entry_->isLive();
1.176 + }
1.177 + };
1.178 +
1.179 + class Insert : public Result
1.180 + {
1.181 + uint32_t hash_;
1.182 +
1.183 + public:
1.184 + Insert(Entry *entry, uint32_t hash)
1.185 + : Result(entry),
1.186 + hash_(hash)
1.187 + {
1.188 + }
1.189 +
1.190 + uint32_t hash() const {
1.191 + return hash_;
1.192 + }
1.193 + };
1.194 +
1.195 + private:
1.196 + class Probulator {
1.197 + uint32_t hash_;
1.198 + uint32_t capacity_;
1.199 +
1.200 + public:
1.201 + Probulator(uint32_t hash, uint32_t capacity)
1.202 + : hash_(hash),
1.203 + capacity_(capacity)
1.204 + {
1.205 + assert(IsPowerOfTwo(capacity_));
1.206 + }
1.207 +
1.208 + uint32_t entry() const {
1.209 + return hash_ & (capacity_ - 1);
1.210 + }
1.211 + uint32_t next() {
1.212 + hash_++;
1.213 + return entry();
1.214 + }
1.215 + };
1.216 +
1.217 + bool underloaded() const {
1.218 + // Check if the table is underloaded: < 25% entries used.
1.219 + return (capacity_ > kMinCapacity) && (nelements_ + ndeleted_ < capacity_ / 4);
1.220 + }
1.221 + bool overloaded() const {
1.222 + // Grow if the table is overloaded: > 75% entries used.
1.223 + return (nelements_ + ndeleted_) > ((capacity_ / 2) + (capacity_ / 4));
1.224 + }
1.225 +
1.226 + bool shrink() {
1.227 + if ((capacity_ >> 1) < minCapacity_)
1.228 + return true;
1.229 + return changeCapacity(capacity_ >> 1);
1.230 + }
1.231 +
1.232 + bool grow() {
1.233 + if (capacity_ >= kMaxCapacity) {
1.234 + this->reportAllocationOverflow();
1.235 + return false;
1.236 + }
1.237 + return changeCapacity(capacity_ << 1);
1.238 + }
1.239 +
1.240 + bool changeCapacity(uint32_t newCapacity) {
1.241 + assert(newCapacity <= kMaxCapacity);
1.242 +
1.243 + Entry *newTable = createTable(newCapacity);
1.244 + if (!newTable)
1.245 + return false;
1.246 +
1.247 + Entry *oldTable = table_;
1.248 + uint32_t oldCapacity = capacity_;
1.249 +
1.250 + table_ = newTable;
1.251 + capacity_ = newCapacity;
1.252 + ndeleted_ = 0;
1.253 +
1.254 + for (uint32_t i = 0; i < oldCapacity; i++) {
1.255 + Entry &oldEntry = oldTable[i];
1.256 + if (oldEntry.isLive()) {
1.257 + Insert p = insertUnique(oldEntry.hash());
1.258 + p.entry().setHash(p.hash(), oldEntry.payload());
1.259 + }
1.260 + oldEntry.destruct();
1.261 + }
1.262 + this->free(oldTable);
1.263 +
1.264 + return true;
1.265 + }
1.266 +
1.267 + // For use when the key is known to be unique.
1.268 + Insert insertUnique(uint32_t hash) {
1.269 + Probulator probulator(hash, capacity_);
1.270 +
1.271 + Entry *e = &table_[probulator.entry()];
1.272 + for (;;) {
1.273 + if (e->free() || e->removed())
1.274 + break;
1.275 + e = &table_[probulator.next()];
1.276 + }
1.277 +
1.278 + return Insert(e, hash);
1.279 + }
1.280 +
1.281 + template <typename Key>
1.282 + Result lookup(const Key &key) {
1.283 + uint32_t hash = computeHash(key);
1.284 + Probulator probulator(hash, capacity_);
1.285 +
1.286 + Entry *e = &table_[probulator.entry()];
1.287 + for (;;) {
1.288 + if (e->free())
1.289 + break;
1.290 + if (e->isLive() &&
1.291 + e->sameHash(hash) &&
1.292 + HashPolicy::matches(key, e->payload()))
1.293 + {
1.294 + return Result(e);
1.295 + }
1.296 + e = &table_[probulator.next()];
1.297 + }
1.298 +
1.299 + return Result(e);
1.300 + }
1.301 +
1.302 + template <typename Key>
1.303 + Insert lookupForAdd(const Key &key) {
1.304 + uint32_t hash = computeHash(key);
1.305 + Probulator probulator(hash, capacity_);
1.306 +
1.307 + Entry *e = &table_[probulator.entry()];
1.308 + for (;;) {
1.309 + if (!e->isLive())
1.310 + break;
1.311 + if (e->sameHash(hash) && HashPolicy::matches(key, e->payload()))
1.312 + break;
1.313 + e = &table_[probulator.next()];
1.314 + }
1.315 +
1.316 + return Insert(e, hash);
1.317 + }
1.318 +
1.319 + bool internalAdd(Insert &i, const Payload &payload) {
1.320 + assert(!i.found());
1.321 +
1.322 + // If the entry is deleted, just re-use the slot.
1.323 + if (i.entry().removed()) {
1.324 + ndeleted_--;
1.325 + } else {
1.326 + // Otherwise, see if we're at max capacity.
1.327 + if (nelements_ == kMaxCapacity) {
1.328 + this->reportAllocationOverflow();
1.329 + return false;
1.330 + }
1.331 +
1.332 + // Check if the table is over or underloaded. The table is always at
1.333 + // least 25% free, so this check is enough to guarantee one free slot.
1.334 + // (Without one free slot, insertion search could infinite loop.)
1.335 + uint32_t oldCapacity = capacity_;
1.336 + if (!checkDensity())
1.337 + return false;
1.338 +
1.339 + // If the table changed size, we need to find a new insertion point.
1.340 + // Note that a removed entry is impossible: either we caught it above,
1.341 + // or we just resized and no entries are removed.
1.342 + if (capacity_ != oldCapacity)
1.343 + i = insertUnique(i.hash());
1.344 + }
1.345 +
1.346 + i.entry().setHash(i.hash(), payload);
1.347 + nelements_++;
1.348 + return true;
1.349 + }
1.350 +
1.351 + void removeEntry(Entry &e) {
1.352 + assert(e.isLive());
1.353 + e.setRemoved();
1.354 + ndeleted_++;
1.355 + nelements_--;
1.356 + }
1.357 +
1.358 + public:
1.359 + HashTable(AllocPolicy ap)
1.360 + : AllocPolicy(ap),
1.361 + capacity_(0),
1.362 + nelements_(0),
1.363 + ndeleted_(0),
1.364 + table_(NULL),
1.365 + minCapacity_(kMinCapacity)
1.366 + {
1.367 + }
1.368 +
1.369 + ~HashTable()
1.370 + {
1.371 + for (uint32_t i = 0; i < capacity_; i++)
1.372 + table_[i].destruct();
1.373 + this->free(table_);
1.374 + }
1.375 +
1.376 + bool init(uint32_t capacity = 0) {
1.377 + if (capacity < kMinCapacity) {
1.378 + capacity = kMinCapacity;
1.379 + } else if (capacity > kMaxCapacity) {
1.380 + this->reportAllocationOverflow();
1.381 + return false;
1.382 + }
1.383 +
1.384 + minCapacity_ = capacity;
1.385 +
1.386 + assert(IsPowerOfTwo(capacity));
1.387 + capacity_ = capacity;
1.388 +
1.389 + table_ = createTable(capacity_);
1.390 + if (!table_)
1.391 + return false;
1.392 +
1.393 + return true;
1.394 + }
1.395 +
1.396 + // The Result object must not be used past mutating table operations.
1.397 + template <typename Key>
1.398 + Result find(const Key &key) {
1.399 + return lookup(key);
1.400 + }
1.401 +
1.402 + // The Insert object must not be used past mutating table operations.
1.403 + template <typename Key>
1.404 + Insert findForAdd(const Key &key) {
1.405 + return lookupForAdd(key);
1.406 + }
1.407 +
1.408 + template <typename Key>
1.409 + void removeIfExists(const Key &key) {
1.410 + Result r = find(key);
1.411 + if (!r.found())
1.412 + return;
1.413 + remove(r);
1.414 + }
1.415 +
1.416 + void remove(Result &r) {
1.417 + assert(r.found());
1.418 + removeEntry(r.entry());
1.419 + }
1.420 +
1.421 + // The table must not have been mutated in between findForAdd() and add().
1.422 + // The Insert object is still valid after add() returns, however.
1.423 + bool add(Insert &i, const Payload &payload) {
1.424 + return internalAdd(i, payload);
1.425 + }
1.426 +
1.427 + bool checkDensity() {
1.428 + if (underloaded())
1.429 + return shrink();
1.430 + if (overloaded())
1.431 + return grow();
1.432 + return true;
1.433 + }
1.434 +
1.435 + size_t estimateMemoryUse() const {
1.436 + return sizeof(Entry) * capacity_;
1.437 + }
1.438 +
1.439 + public:
1.440 + // It is illegal to mutate a HashTable during iteration.
1.441 + class iterator
1.442 + {
1.443 + public:
1.444 + iterator(HashTable *table)
1.445 + : table_(table),
1.446 + i_(table->table_),
1.447 + end_(table->table_ + table->capacity_)
1.448 + {
1.449 + while (i_ < end_ && !i_->isLive())
1.450 + i_++;
1.451 + }
1.452 +
1.453 + bool empty() const {
1.454 + return i_ == end_;
1.455 + }
1.456 +
1.457 + void erase() {
1.458 + assert(!empty());
1.459 + table_->removeEntry(*i_);
1.460 + }
1.461 +
1.462 + const Payload &operator *() const {
1.463 + return i_->payload();
1.464 + }
1.465 +
1.466 + void next() {
1.467 + do {
1.468 + i_++;
1.469 + } while (i_ < end_ && !i_->isLive());
1.470 + }
1.471 +
1.472 + private:
1.473 + HashTable *table_;
1.474 + Entry *i_;
1.475 + Entry *end_;
1.476 + };
1.477 +
1.478 + private:
1.479 + HashTable(const HashTable &other) KE_DELETE;
1.480 + HashTable &operator =(const HashTable &other) KE_DELETE;
1.481 +
1.482 + private:
1.483 + uint32_t capacity_;
1.484 + uint32_t nelements_;
1.485 + uint32_t ndeleted_;
1.486 + Entry *table_;
1.487 + uint32_t minCapacity_;
1.488 +};
1.489 +
1.490 +// Bob Jenkin's one-at-a-time hash function[1].
1.491 +//
1.492 +// [1] http://burtleburtle.net/bob/hash/doobs.html
1.493 +class CharacterStreamHasher
1.494 +{
1.495 + uint32_t hash;
1.496 +
1.497 + public:
1.498 + CharacterStreamHasher()
1.499 + : hash(0)
1.500 + { }
1.501 +
1.502 + void add(char c) {
1.503 + hash += c;
1.504 + hash += (hash << 10);
1.505 + hash ^= (hash >> 6);
1.506 + }
1.507 +
1.508 + void add(const char *s, size_t length) {
1.509 + for (size_t i = 0; i < length; i++)
1.510 + add(s[i]);
1.511 + }
1.512 +
1.513 + uint32_t result() {
1.514 + hash += (hash << 3);
1.515 + hash ^= (hash >> 11);
1.516 + hash += (hash << 15);
1.517 + return hash;
1.518 + }
1.519 +};
1.520 +
1.521 +static inline uint32_t
1.522 +HashCharSequence(const char *s, size_t length)
1.523 +{
1.524 + CharacterStreamHasher hasher;
1.525 + hasher.add(s, length);
1.526 + return hasher.result();
1.527 +}
1.528 +
1.529 +static inline uint32_t
1.530 +FastHashCharSequence(const char *s, size_t length)
1.531 +{
1.532 + uint32_t hash = 0;
1.533 + for (size_t i = 0; i < length; i++)
1.534 + hash = s[i] + (hash << 6) + (hash << 16) - hash;
1.535 + return hash;
1.536 +}
1.537 +
1.538 +// From http://burtleburtle.net/bob/hash/integer.html
1.539 +static inline uint32_t
1.540 +HashInt32(int32_t a)
1.541 +{
1.542 + a = (a ^ 61) ^ (a >> 16);
1.543 + a = a + (a << 3);
1.544 + a = a ^ (a >> 4);
1.545 + a = a * 0x27d4eb2d;
1.546 + a = a ^ (a >> 15);
1.547 + return a;
1.548 +}
1.549 +
1.550 +// From http://www.cris.com/~Ttwang/tech/inthash.htm
1.551 +static inline uint32_t
1.552 +HashInt64(int64_t key)
1.553 +{
1.554 + key = (~key) + (key << 18); // key = (key << 18) - key - 1;
1.555 + key = key ^ (uint64(key) >> 31);
1.556 + key = key * 21; // key = (key + (key << 2)) + (key << 4);
1.557 + key = key ^ (uint64(key) >> 11);
1.558 + key = key + (key << 6);
1.559 + key = key ^ (uint64(key) >> 22);
1.560 + return uint32(key);
1.561 +}
1.562 +
1.563 +template <size_t Size>
1.564 +static inline uint32_t
1.565 +HashInteger(uintptr_t value);
1.566 +
1.567 +template <>
1.568 +inline uint32_t
1.569 +HashInteger<4>(uintptr_t value)
1.570 +{
1.571 + return HashInt32(value);
1.572 +}
1.573 +
1.574 +template <>
1.575 +inline uint32_t
1.576 +HashInteger<8>(uintptr_t value)
1.577 +{
1.578 + return HashInt64(value);
1.579 +}
1.580 +
1.581 +static inline uint32_t
1.582 +HashPointer(void *ptr)
1.583 +{
1.584 + return HashInteger<sizeof(ptr)>(reinterpret_cast<uintptr_t>(ptr));
1.585 +}
1.586 +
1.587 +} // namespace ke
1.588 +
1.589 +#endif // _INCLUDE_KEIMA_HASHTABLE_H_