Import HashTable.
authorDavid Anderson <dvander@alliedmods.net>
Fri Aug 23 22:36:08 2013 -0700 (2013-08-23)
changeset 1d5286b4d7c2d
parent 0 ba3d4abaf3f1
child 2 5fe3546d3336
Import HashTable.
include/am-hashtable.h
     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_