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