1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/HashTable.h Tue Jul 24 23:53:34 2012 -0700
1.3 @@ -0,0 +1,424 @@
1.4 +/*
1.5 + * Copyright (C) 2012 David Anderson
1.6 + *
1.7 + * This file is part of JITCraft.
1.8 + *
1.9 + * JITCraft is free software: you can redistribute it and/or modify it under
1.10 + * the terms of the GNU General Public License as published by the Free
1.11 + * Software Foundation, either version 3 of the License, or (at your option)
1.12 + * any later version.
1.13 + *
1.14 + * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
1.15 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.16 + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License along with
1.19 + * JITCraft. If not, see http://www.gnu.org/licenses/.
1.20 + */
1.21 +#ifndef _INCLUDE_KEIMA_HASHTABLE_H_
1.22 +#define _INCLUDE_KEIMA_HASHTABLE_H_
1.23 +
1.24 +#include <new>
1.25 +#include <limits.h>
1.26 +#include "Utility.h"
1.27 +
1.28 +namespace ke {
1.29 +
1.30 +template <typename T>
1.31 +class HashTableEntry
1.32 +{
1.33 + uint32 hash_;
1.34 + T t_;
1.35 +
1.36 + public:
1.37 + static const uint32 kFreeHash = 0;
1.38 + static const uint32 kRemovedHash = 1;
1.39 +
1.40 + public:
1.41 + void setHash(uint32 hash) {
1.42 + hash_ = hash;
1.43 + }
1.44 + uint32 hash() const {
1.45 + return hash_;
1.46 + }
1.47 + void setRemoved() {
1.48 + hash_ = kRemovedHash;
1.49 + t_ = T();
1.50 + }
1.51 + void construct() {
1.52 + hash_ = kFreeHash;
1.53 + new (&t_) T();
1.54 + }
1.55 + void destruct() {
1.56 + t_.~T();
1.57 + }
1.58 + bool removed() const {
1.59 + return hash_ == kRemovedHash;
1.60 + }
1.61 + bool free() const {
1.62 + return hash_ == kFreeHash;
1.63 + }
1.64 + bool isLive() const {
1.65 + return hash_ > kRemovedHash;
1.66 + }
1.67 + T &payload() {
1.68 + return t_;
1.69 + }
1.70 + bool sameHash(uint32 hash) const {
1.71 + return hash_ == hash;
1.72 + }
1.73 +};
1.74 +
1.75 +template <typename HashPolicy, typename AllocPolicy>
1.76 +class HashTable : public AllocPolicy
1.77 +{
1.78 + friend class iterator;
1.79 +
1.80 + typedef typename HashPolicy::Payload Payload;
1.81 + typedef HashTableEntry<Payload> Entry;
1.82 +
1.83 + uint32 capacity_;
1.84 + uint32 nelements_;
1.85 + uint32 ndeleted_;
1.86 + Entry *table_;
1.87 + uint32 minCapacity_;
1.88 +
1.89 + private:
1.90 + static const uint32 kMinCapacity = 16;
1.91 + static const uint32 kMaxCapacity = INT_MAX / sizeof(Entry);
1.92 +
1.93 + template <typename Key>
1.94 + uint32 computeHash(const Key &key) {
1.95 + // Multiply by golden ratio.
1.96 + uint32 hash = HashPolicy::hash(key) * 0x9E3779B9;
1.97 + if (hash == Entry::kFreeHash || hash == Entry::kRemovedHash)
1.98 + hash += 2;
1.99 + return hash;
1.100 + }
1.101 +
1.102 + Entry *createTable(uint32 capacity) {
1.103 + assert(capacity <= kMaxCapacity);
1.104 +
1.105 + Entry *table = (Entry *)this->malloc(capacity * sizeof(Entry));
1.106 + if (!table)
1.107 + return NULL;
1.108 +
1.109 + for (size_t i = 0; i < capacity; i++)
1.110 + table[i].construct();
1.111 +
1.112 + return table;
1.113 + }
1.114 +
1.115 + public:
1.116 + class Result
1.117 + {
1.118 + friend class HashTable;
1.119 +
1.120 + Entry *entry_;
1.121 +
1.122 + Entry &entry() {
1.123 + return *entry_;
1.124 + }
1.125 +
1.126 + public:
1.127 + Result(Entry *entry)
1.128 + : entry_(entry)
1.129 + { }
1.130 +
1.131 + Payload * operator ->() {
1.132 + return entry_->payload();
1.133 + }
1.134 + Payload & operator *() {
1.135 + return entry_->payload();
1.136 + }
1.137 +
1.138 + bool found() const {
1.139 + return entry_->isLive();
1.140 + }
1.141 + };
1.142 +
1.143 + class Insert : public Result
1.144 + {
1.145 + uint32 hash_;
1.146 +
1.147 + public:
1.148 + Insert(Entry *entry, uint32 hash)
1.149 + : Result(entry),
1.150 + hash_(hash)
1.151 + {
1.152 + }
1.153 +
1.154 + uint32 hash() const {
1.155 + return hash_;
1.156 + }
1.157 + };
1.158 +
1.159 + private:
1.160 + class Probulator {
1.161 + uint32 hash_;
1.162 + uint32 capacity_;
1.163 +
1.164 + public:
1.165 + Probulator(uint32 hash, uint32 capacity)
1.166 + : hash_(hash),
1.167 + capacity_(capacity)
1.168 + {
1.169 + assert(IsPowerOfTwo(capacity_));
1.170 + }
1.171 +
1.172 + uint32 entry() const {
1.173 + return hash_ & (capacity_ - 1);
1.174 + }
1.175 + uint32 next() {
1.176 + hash_++;
1.177 + return entry();
1.178 + }
1.179 + };
1.180 +
1.181 + bool underloaded() const {
1.182 + // Check if the table is underloaded: < 25% entries used.
1.183 + return (capacity_ > kMinCapacity) && (nelements_ + ndeleted_ < capacity_ / 4);
1.184 + }
1.185 + bool overloaded() const {
1.186 + // Grow if the table is overloaded: > 75% entries used.
1.187 + return (nelements_ + ndeleted_) > ((capacity_ / 2) + (capacity_ / 4));
1.188 + }
1.189 +
1.190 + bool shrink() {
1.191 + if ((capacity_ >> 1) < minCapacity_)
1.192 + return true;
1.193 + return changeCapacity(capacity_ >> 1);
1.194 + }
1.195 +
1.196 + bool grow() {
1.197 + assert(IsPowerOfTwo(kMaxCapacity));
1.198 + if (capacity_ >= kMaxCapacity) {
1.199 + this->reportAllocationOverflow();
1.200 + return false;
1.201 + }
1.202 + return changeCapacity(capacity_ << 1);
1.203 + }
1.204 +
1.205 + bool changeCapacity(uint32 newCapacity) {
1.206 + assert(newCapacity <= kMaxCapacity);
1.207 +
1.208 + Entry *newTable = createTable(newCapacity);
1.209 + if (!newTable)
1.210 + return false;
1.211 +
1.212 + Entry *oldTable = table_;
1.213 + uint32 oldCapacity = capacity_;
1.214 +
1.215 + table_ = newTable;
1.216 + capacity_ = newCapacity;
1.217 + ndeleted_ = 0;
1.218 +
1.219 + for (uint32 i = 0; i < oldCapacity; i++) {
1.220 + Entry &oldEntry = oldTable[i];
1.221 + if (oldEntry.isLive()) {
1.222 + Insert p = insertUnique(oldEntry.hash());
1.223 + p.entry().setHash(p.hash());
1.224 + p.entry().payload() = oldEntry.payload();
1.225 + }
1.226 + oldEntry.destruct();
1.227 + }
1.228 + this->free(oldTable);
1.229 +
1.230 + return true;
1.231 + }
1.232 +
1.233 + // For use when the key is known to be unique.
1.234 + Insert insertUnique(uint32 hash) {
1.235 + Probulator probulator(hash, capacity_);
1.236 +
1.237 + Entry *e = &table_[probulator.entry()];
1.238 + for (;;) {
1.239 + if (e->free() || e->removed())
1.240 + break;
1.241 + e = &table_[probulator.next()];
1.242 + }
1.243 +
1.244 + return Insert(e, hash);
1.245 + }
1.246 +
1.247 + template <typename Key>
1.248 + Result lookup(const Key &key) {
1.249 + uint32 hash = computeHash(key);
1.250 + Probulator probulator(hash, capacity_);
1.251 +
1.252 + Entry *e = &table_[probulator.entry()];
1.253 + for (;;) {
1.254 + if (e->free())
1.255 + break;
1.256 + if (e->isLive() &&
1.257 + e->sameHash(hash) &&
1.258 + HashPolicy::matches(key, e->payload()))
1.259 + {
1.260 + return Result(e);
1.261 + }
1.262 + e = &table_[probulator.next()];
1.263 + }
1.264 +
1.265 + return Result(e);
1.266 + }
1.267 +
1.268 + template <typename Key>
1.269 + Insert lookupForAdd(const Key &key) {
1.270 + uint32 hash = computeHash(key);
1.271 + Probulator probulator(hash, capacity_);
1.272 +
1.273 + Entry *e = &table_[probulator.entry()];
1.274 + for (;;) {
1.275 + if (!e->isLive())
1.276 + break;
1.277 + if (e->sameHash(hash) && HashPolicy::matches(key, e->payload()))
1.278 + break;
1.279 + e = &table_[probulator.next()];
1.280 + }
1.281 +
1.282 + return Insert(e, hash);
1.283 + }
1.284 +
1.285 + bool add(Insert &i) {
1.286 + assert(!i.found());
1.287 +
1.288 + // If the entry is deleted, just re-use the slot.
1.289 + if (i.entry().removed()) {
1.290 + ndeleted_--;
1.291 + return true;
1.292 + }
1.293 +
1.294 + // Otherwise, see if we're at max capacity.
1.295 + if (nelements_ == kMaxCapacity) {
1.296 + this->reportAllocationOverflow();
1.297 + return false;
1.298 + }
1.299 +
1.300 + // Check if the table is over or underloaded. The table is always at
1.301 + // least 25% free, so this check is enough to guarantee one free slot.
1.302 + // (Without one free slot, insertion search could infinite loop.)
1.303 + uint32 oldCapacity = capacity_;
1.304 + if (!checkDensity())
1.305 + return false;
1.306 +
1.307 + // If the table changed size, we need to find a new insertion point.
1.308 + // Note that a removed entry is impossible: either we caught it above,
1.309 + // or we just resized and no entries are removed.
1.310 + if (capacity_ != oldCapacity)
1.311 + i = insertUnique(i.hash());
1.312 +
1.313 + i.entry().setHash(i.hash());
1.314 + nelements_++;
1.315 +
1.316 + return true;
1.317 + }
1.318 +
1.319 + void remove(Entry &e) {
1.320 + assert(e.isLive());
1.321 + e.setRemoved();
1.322 + ndeleted_++;
1.323 + nelements_--;
1.324 + }
1.325 +
1.326 + public:
1.327 + HashTable(AllocPolicy ap)
1.328 + : AllocPolicy(ap),
1.329 + capacity_(0),
1.330 + nelements_(0),
1.331 + ndeleted_(0),
1.332 + table_(NULL),
1.333 + minCapacity_(kMinCapacity)
1.334 + {
1.335 + }
1.336 +
1.337 + ~HashTable()
1.338 + {
1.339 + for (uint32 i = 0; i < capacity_; i++)
1.340 + table_[i].destruct();
1.341 + this->free(table_);
1.342 + }
1.343 +
1.344 + bool init(uint32 capacity = 0) {
1.345 + if (capacity < kMinCapacity)
1.346 + capacity = kMinCapacity;
1.347 + else if (capacity > kMaxCapacity)
1.348 + capacity = kMaxCapacity;
1.349 +
1.350 + minCapacity_ = capacity;
1.351 +
1.352 + assert(IsPowerOfTwo(capacity));
1.353 + capacity_ = capacity;
1.354 +
1.355 + table_ = createTable(capacity_);
1.356 + if (!table_)
1.357 + return false;
1.358 +
1.359 + return true;
1.360 + }
1.361 +
1.362 + template <typename Key>
1.363 + Result find(const Key &key) {
1.364 + return lookup(key);
1.365 + }
1.366 +
1.367 + template <typename Key>
1.368 + Insert findForAdd(const Key &key) {
1.369 + return lookupForAdd(key);
1.370 + }
1.371 +
1.372 + bool add(Insert &i, const Payload &payload) {
1.373 + if (!add(i))
1.374 + return false;
1.375 + *i = payload;
1.376 + return true;
1.377 + }
1.378 +
1.379 + bool checkDensity() {
1.380 + if (underloaded())
1.381 + return shrink();
1.382 + if (overloaded())
1.383 + return grow();
1.384 + return true;
1.385 + }
1.386 +
1.387 + public:
1.388 + class iterator
1.389 + {
1.390 + HashTable *table_;
1.391 + Entry *i_;
1.392 + Entry *end_;
1.393 +
1.394 + public:
1.395 + iterator(HashTable *table)
1.396 + : table_(table),
1.397 + i_(table->table_),
1.398 + end_(table->table_ + table->capacity_)
1.399 + {
1.400 + while (i_ < end_ && !i_->isLive())
1.401 + i_++;
1.402 + }
1.403 +
1.404 + bool empty() const {
1.405 + return i_ == end_;
1.406 + }
1.407 +
1.408 + void erase() {
1.409 + assert(!empty());
1.410 + table_->remove(*i_);
1.411 + }
1.412 +
1.413 + const Payload &operator *() const {
1.414 + return i_->payload();
1.415 + }
1.416 +
1.417 + void next() {
1.418 + do {
1.419 + i_++;
1.420 + } while (i_ < end_ && !i_->isLive());
1.421 + }
1.422 + };
1.423 +};
1.424 +
1.425 +}
1.426 +
1.427 +#endif // _INCLUDE_KEIMA_HASHTABLE_H_
