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