dvander@54: /*
dvander@54:  * Copyright (C) 2012 David Anderson
dvander@54:  *
dvander@54:  * This file is part of JITCraft.
dvander@54:  *
dvander@54:  * JITCraft is free software: you can redistribute it and/or modify it under
dvander@54:  * the terms of the GNU General Public License as published by the Free
dvander@54:  * Software Foundation, either version 3 of the License, or (at your option)
dvander@54:  * any later version.
dvander@54:  * 
dvander@54:  * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
dvander@54:  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
dvander@54:  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
dvander@54:  *
dvander@54:  * You should have received a copy of the GNU General Public License along with
dvander@54:  * JITCraft. If not, see http://www.gnu.org/licenses/.
dvander@54:  */
dvander@0: #ifndef _INCLUDE_KEIMA_HASHTABLE_H_
dvander@0: #define _INCLUDE_KEIMA_HASHTABLE_H_
dvander@0: 
dvander@0: #include <new>
dvander@0: #include <limits.h>
dvander@54: #include "Utility.h"
dvander@0: 
dvander@59: namespace ke {
dvander@0: 
dvander@0: template <typename T>
dvander@0: class HashTableEntry
dvander@0: {
dvander@0:     uint32 hash_;
dvander@0:     T t_;
dvander@0: 
dvander@0:   public:
dvander@0:     static const uint32 kFreeHash = 0;
dvander@0:     static const uint32 kRemovedHash = 1;
dvander@0: 
dvander@0:   public:
dvander@0:     void setHash(uint32 hash) {
dvander@0:         hash_ = hash;
dvander@0:     }
dvander@0:     uint32 hash() const {
dvander@0:         return hash_;
dvander@0:     }
dvander@0:     void setRemoved() {
dvander@0:         hash_ = kRemovedHash;
dvander@54:         t_ = T();
dvander@0:     }
dvander@0:     void construct() {
dvander@54:         hash_ = kFreeHash;
dvander@0:         new (&t_) T();
dvander@0:     }
dvander@0:     void destruct() {
dvander@0:         t_.~T();
dvander@0:     }
dvander@0:     bool removed() const {
dvander@0:         return hash_ == kRemovedHash;
dvander@0:     }
dvander@0:     bool free() const {
dvander@0:         return hash_ == kFreeHash;
dvander@0:     }
dvander@0:     bool isLive() const {
dvander@0:         return hash_ > kRemovedHash;
dvander@0:     }
dvander@0:     T &payload() {
dvander@0:         return t_;
dvander@0:     }
dvander@0:     bool sameHash(uint32 hash) const {
dvander@0:         return hash_ == hash;
dvander@0:     }
dvander@0: };
dvander@0: 
dvander@0: template <typename HashPolicy, typename AllocPolicy>
dvander@0: class HashTable : public AllocPolicy
dvander@0: {
dvander@54:     friend class iterator;
dvander@54: 
dvander@0:     typedef typename HashPolicy::Payload Payload;
dvander@0:     typedef HashTableEntry<Payload> Entry;
dvander@0: 
dvander@0:     uint32 capacity_;
dvander@0:     uint32 nelements_;
dvander@0:     uint32 ndeleted_;
dvander@0:     Entry *table_;
dvander@54:     uint32 minCapacity_;
dvander@0: 
dvander@0:   private:
dvander@0:     static const uint32 kMinCapacity = 16;
dvander@0:     static const uint32 kMaxCapacity = INT_MAX / sizeof(Entry);
dvander@0: 
dvander@0:     template <typename Key>
dvander@0:     uint32 computeHash(const Key &key) {
dvander@0:         // Multiply by golden ratio.
dvander@0:         uint32 hash = HashPolicy::hash(key) * 0x9E3779B9;
dvander@0:         if (hash == Entry::kFreeHash || hash == Entry::kRemovedHash)
dvander@0:             hash += 2;
dvander@0:         return hash;
dvander@0:     }
dvander@0: 
dvander@0:     Entry *createTable(uint32 capacity) {
dvander@54:         assert(capacity <= kMaxCapacity);
dvander@0: 
dvander@0:         Entry *table = (Entry *)this->malloc(capacity * sizeof(Entry));
dvander@0:         if (!table)
dvander@0:             return NULL;
dvander@0: 
dvander@0:         for (size_t i = 0; i < capacity; i++)
dvander@0:             table[i].construct();
dvander@0: 
dvander@0:         return table;
dvander@0:     }
dvander@0: 
dvander@0:   public:
dvander@0:     class Result
dvander@0:     {
dvander@0:         friend class HashTable;
dvander@0: 
dvander@0:         Entry *entry_;
dvander@0: 
dvander@0:         Entry &entry() {
dvander@0:             return *entry_;
dvander@0:         }
dvander@0: 
dvander@0:       public:
dvander@0:         Result(Entry *entry)
dvander@0:           : entry_(entry)
dvander@0:         { }
dvander@0: 
dvander@0:         Payload * operator ->() {
dvander@0:             return entry_->payload();
dvander@0:         }
dvander@0:         Payload & operator *() {
dvander@0:             return entry_->payload();
dvander@0:         }
dvander@0: 
dvander@0:         bool found() const {
dvander@0:             return entry_->isLive();
dvander@0:         }
dvander@0:     };
dvander@0: 
dvander@0:     class Insert : public Result
dvander@0:     {
dvander@0:         uint32 hash_;
dvander@0: 
dvander@0:       public:
dvander@0:         Insert(Entry *entry, uint32 hash)
dvander@0:           : Result(entry),
dvander@0:             hash_(hash)
dvander@0:         {
dvander@0:         }
dvander@0: 
dvander@0:         uint32 hash() const {
dvander@0:             return hash_;
dvander@0:         }
dvander@0:     };
dvander@0: 
dvander@0:   private:
dvander@0:     class Probulator {
dvander@0:         uint32 hash_;
dvander@0:         uint32 capacity_;
dvander@0: 
dvander@0:       public:
dvander@0:         Probulator(uint32 hash, uint32 capacity)
dvander@0:           : hash_(hash),
dvander@0:             capacity_(capacity)
dvander@0:         {
dvander@54:             assert(IsPowerOfTwo(capacity_)); 
dvander@0:         }
dvander@0: 
dvander@0:         uint32 entry() const {
dvander@0:             return hash_ & (capacity_ - 1);
dvander@0:         }
dvander@0:         uint32 next() {
dvander@0:             hash_++;
dvander@0:             return entry();
dvander@0:         }
dvander@0:     };
dvander@0: 
dvander@0:     bool underloaded() const {
dvander@0:         // Check if the table is underloaded: < 25% entries used.
dvander@0:         return (capacity_ > kMinCapacity) && (nelements_ + ndeleted_ < capacity_ / 4);
dvander@0:     }
dvander@0:     bool overloaded() const {
dvander@0:         // Grow if the table is overloaded: > 75% entries used.
dvander@0:         return (nelements_ + ndeleted_) > ((capacity_ / 2) + (capacity_ / 4));
dvander@0:     }
dvander@0: 
dvander@0:     bool shrink() {
dvander@54:         if ((capacity_ >> 1) < minCapacity_)
dvander@54:             return true;
dvander@0:         return changeCapacity(capacity_ >> 1);
dvander@0:     }
dvander@0:     
dvander@0:     bool grow() {
dvander@54:         assert(IsPowerOfTwo(kMaxCapacity));
dvander@0:         if (capacity_ >= kMaxCapacity) {
dvander@0:             this->reportAllocationOverflow();
dvander@0:             return false;
dvander@0:         }
dvander@0:         return changeCapacity(capacity_ << 1);
dvander@0:     }
dvander@0: 
dvander@0:     bool changeCapacity(uint32 newCapacity) {
dvander@54:         assert(newCapacity <= kMaxCapacity);
dvander@0: 
dvander@0:         Entry *newTable = createTable(newCapacity);
dvander@0:         if (!newTable)
dvander@0:             return false;
dvander@0: 
dvander@0:         Entry *oldTable = table_;
dvander@0:         uint32 oldCapacity = capacity_;
dvander@0: 
dvander@0:         table_ = newTable;
dvander@0:         capacity_ = newCapacity;
dvander@0:         ndeleted_ = 0;
dvander@0: 
dvander@0:         for (uint32 i = 0; i < oldCapacity; i++) {
dvander@0:             Entry &oldEntry = oldTable[i];
dvander@0:             if (oldEntry.isLive()) {
dvander@0:                 Insert p = insertUnique(oldEntry.hash());
dvander@0:                 p.entry().setHash(p.hash());
dvander@0:                 p.entry().payload() = oldEntry.payload();
dvander@0:             }
dvander@0:             oldEntry.destruct();
dvander@0:         }
dvander@54:         this->free(oldTable);
dvander@0: 
dvander@0:         return true;
dvander@0:     }
dvander@0: 
dvander@0:     // For use when the key is known to be unique.
dvander@0:     Insert insertUnique(uint32 hash) {
dvander@0:         Probulator probulator(hash, capacity_);
dvander@0: 
dvander@0:         Entry *e = &table_[probulator.entry()];
dvander@0:         for (;;) {
dvander@0:             if (e->free() || e->removed())
dvander@0:                 break;
dvander@0:             e = &table_[probulator.next()];
dvander@0:         }
dvander@0: 
dvander@0:         return Insert(e, hash);
dvander@0:     }
dvander@0: 
dvander@0:     template <typename Key>
dvander@0:     Result lookup(const Key &key) {
dvander@0:         uint32 hash = computeHash(key);
dvander@0:         Probulator probulator(hash, capacity_);
dvander@0: 
dvander@0:         Entry *e = &table_[probulator.entry()];
dvander@0:         for (;;) {
dvander@0:             if (e->free())
dvander@0:                 break;
dvander@0:             if (e->isLive() &&
dvander@0:                 e->sameHash(hash) &&
dvander@0:                 HashPolicy::matches(key, e->payload()))
dvander@0:             {
dvander@0:                 return Result(e);
dvander@0:             }
dvander@0:             e = &table_[probulator.next()];
dvander@0:         }
dvander@0: 
dvander@0:         return Result(e);
dvander@0:     }
dvander@0: 
dvander@0:     template <typename Key>
dvander@0:     Insert lookupForAdd(const Key &key) {
dvander@0:         uint32 hash = computeHash(key);
dvander@0:         Probulator probulator(hash, capacity_);
dvander@0: 
dvander@0:         Entry *e = &table_[probulator.entry()];
dvander@0:         for (;;) {
dvander@0:             if (!e->isLive())
dvander@0:                 break;
dvander@0:             if (e->sameHash(hash) && HashPolicy::matches(key, e->payload()))
dvander@0:                 break;
dvander@0:             e = &table_[probulator.next()];
dvander@0:         }
dvander@0: 
dvander@0:         return Insert(e, hash);
dvander@0:     }
dvander@0: 
dvander@0:     bool add(Insert &i) {
dvander@54:         assert(!i.found());
dvander@0: 
dvander@0:         // If the entry is deleted, just re-use the slot.
dvander@0:         if (i.entry().removed()) {
dvander@0:             ndeleted_--;
dvander@0:             return true;
dvander@0:         }
dvander@0: 
dvander@0:         // Otherwise, see if we're at max capacity.
dvander@0:         if (nelements_ == kMaxCapacity) {
dvander@0:             this->reportAllocationOverflow();
dvander@0:             return false;
dvander@0:         }
dvander@0: 
dvander@0:         // Check if the table is over or underloaded. The table is always at
dvander@0:         // least 25% free, so this check is enough to guarantee one free slot.
dvander@0:         // (Without one free slot, insertion search could infinite loop.)
dvander@0:         uint32 oldCapacity = capacity_;
dvander@0:         if (!checkDensity())
dvander@0:             return false;
dvander@0: 
dvander@0:         // If the table changed size, we need to find a new insertion point.
dvander@0:         // Note that a removed entry is impossible: either we caught it above,
dvander@0:         // or we just resized and no entries are removed.
dvander@0:         if (capacity_ != oldCapacity)
dvander@0:             i = insertUnique(i.hash());
dvander@0: 
dvander@0:         i.entry().setHash(i.hash());
dvander@0:         nelements_++;
dvander@0: 
dvander@0:         return true;
dvander@0:     }
dvander@0: 
dvander@54:     void remove(Entry &e) {
dvander@62:         assert(e.isLive());
dvander@54:         e.setRemoved();
dvander@54:         ndeleted_++;
dvander@54:         nelements_--;
dvander@54:     }
dvander@54: 
dvander@0:   public:
dvander@0:     HashTable(AllocPolicy ap)
dvander@0:       : AllocPolicy(ap),
dvander@0:         capacity_(0),
dvander@0:         nelements_(0),
dvander@0:         ndeleted_(0),
dvander@54:         table_(NULL),
dvander@54:         minCapacity_(kMinCapacity)
dvander@0:     {
dvander@0:     }
dvander@0: 
dvander@0:     ~HashTable()
dvander@0:     {
dvander@0:         for (uint32 i = 0; i < capacity_; i++)
dvander@0:             table_[i].destruct();
dvander@0:         this->free(table_);
dvander@0:     }
dvander@0: 
dvander@0:     bool init(uint32 capacity = 0) {
dvander@0:         if (capacity < kMinCapacity)
dvander@0:             capacity = kMinCapacity;
dvander@0:         else if (capacity > kMaxCapacity)
dvander@0:             capacity = kMaxCapacity;
dvander@0: 
dvander@54:         minCapacity_ = capacity;
dvander@54: 
dvander@54:         assert(IsPowerOfTwo(capacity));
dvander@0:         capacity_ = capacity;
dvander@0: 
dvander@0:         table_ = createTable(capacity_);
dvander@0:         if (!table_)
dvander@0:             return false;
dvander@0: 
dvander@0:         return true;
dvander@0:     }
dvander@0: 
dvander@0:     template <typename Key>
dvander@0:     Result find(const Key &key) {
dvander@0:         return lookup(key);
dvander@0:     }
dvander@0: 
dvander@0:     template <typename Key>
dvander@0:     Insert findForAdd(const Key &key) {
dvander@0:         return lookupForAdd(key);
dvander@0:     }
dvander@0: 
dvander@0:     bool add(Insert &i, const Payload &payload) {
dvander@0:         if (!add(i))
dvander@0:             return false;
dvander@0:         *i = payload;
dvander@0:         return true;
dvander@0:     }
dvander@54: 
dvander@54:     bool checkDensity() {
dvander@54:         if (underloaded())
dvander@54:             return shrink(); 
dvander@54:         if (overloaded())
dvander@54:             return grow();
dvander@54:         return true;
dvander@54:     }
dvander@54: 
dvander@54:   public:
dvander@54:     class iterator
dvander@54:     {
dvander@54:         HashTable *table_;
dvander@54:         Entry *i_;
dvander@54:         Entry *end_;
dvander@54: 
dvander@54:       public:
dvander@54:         iterator(HashTable *table)
dvander@54:           : table_(table),
dvander@54:             i_(table->table_),
dvander@54:             end_(table->table_ + table->capacity_)
dvander@54:         {
dvander@54:             while (i_ < end_ && !i_->isLive())
dvander@54:                 i_++;
dvander@54:         }
dvander@54: 
dvander@54:         bool empty() const {
dvander@54:             return i_ == end_;
dvander@54:         }
dvander@54: 
dvander@54:         void erase() {
dvander@54:             assert(!empty());
dvander@54:             table_->remove(*i_);
dvander@54:         }
dvander@54: 
dvander@54:         const Payload &operator *() const {
dvander@54:             return i_->payload();
dvander@54:         }
dvander@54: 
dvander@54:         void next() {
dvander@62:             do {
dvander@54:                 i_++;
dvander@62:             } while (i_ < end_ && !i_->isLive());
dvander@54:         }
dvander@54:     };
dvander@0: };
dvander@0: 
dvander@0: }
dvander@0: 
dvander@0: #endif // _INCLUDE_KEIMA_HASHTABLE_H_