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