// vim: set ts=4 sw=4 tw=99 et:

 //

 //  

 // (C) Copyright 2010-2011 AlliedModders LLC

 //

 // Initial Author: David Anderson

 // Contributors:

 //

 //

 #ifndef _INCLUDE_KEIMA_HASHTABLE_H_

 #define _INCLUDE_KEIMA_HASHTABLE_H_

 #include <new>

 #include <limits.h>

 #include "Object.h"

 #include "vm/Array.h"

 #include "Environment.h"

 namespace ke {

 template <typename T>

 class HashTableEntry

 {

     uint32 hash_;

     T t_;

   public:

     static const uint32 kFreeHash = 0;

     static const uint32 kRemovedHash = 1;

   public:

     void setHash(uint32 hash) {

         hash_ = hash;

     }

     uint32 hash() const {

         return hash_;

     }

     void setRemoved() {

         hash_ = kRemovedHash;

         destruct();

     }

     void construct() {

         new (&t_) T();

     }

     void destruct() {

         t_.~T();

     }

     bool removed() const {

         return hash_ == kRemovedHash;

     }

     bool free() const {

         return hash_ == kFreeHash;

     }

     bool isLive() const {

         return hash_ > kRemovedHash;

     }

     T &payload() {

         return t_;

     }

     bool sameHash(uint32 hash) const {

         return hash_ == hash;

     }

 };

 template <typename HashPolicy, typename AllocPolicy>

 class HashTable : public AllocPolicy

 {

     typedef typename HashPolicy::Payload Payload;

     typedef HashTableEntry<Payload> Entry;

     uint32 capacity_;

     uint32 nelements_;

     uint32 ndeleted_;

     Entry *table_;

   private:

     static const uint32 kMinCapacity = 16;

     static const uint32 kMaxCapacity = INT_MAX / sizeof(Entry);

     template <typename Key>

     uint32 computeHash(const Key &key) {

         // Multiply by golden ratio.

         uint32 hash = HashPolicy::hash(key) * 0x9E3779B9;

         if (hash == Entry::kFreeHash || hash == Entry::kRemovedHash)

             hash += 2;

         return hash;

     }

     Entry *createTable(uint32 capacity) {

         KE_ASSERT(capacity <= kMaxCapacity);

         Entry *table = (Entry *)this->malloc(capacity * sizeof(Entry));

         if (!table)

             return NULL;

         for (size_t i = 0; i < capacity; i++)

             table[i].construct();

         return table;

     }

   public:

     class Result

     {

         friend class HashTable;

         Entry *entry_;

         Entry &entry() {

             return *entry_;

         }

       public:

         Result(Entry *entry)

           : entry_(entry)

         { }

         Payload * operator ->() {

             return entry_->payload();

         }

         Payload & operator *() {

             return entry_->payload();

         }

         bool found() const {

             return entry_->isLive();

         }

     };

     class Insert : public Result

     {

         uint32 hash_;

       public:

         Insert(Entry *entry, uint32 hash)

           : Result(entry),

             hash_(hash)

         {

         }

         uint32 hash() const {

             return hash_;

         }

     };

   private:

     class Probulator {

         uint32 hash_;

         uint32 capacity_;

       public:

         Probulator(uint32 hash, uint32 capacity)

           : hash_(hash),

             capacity_(capacity)

         {

             KE_ASSERT(IsPowerOfTwo(capacity_)); 

         }

         uint32 entry() const {

             return hash_ & (capacity_ - 1);

         }

         uint32 next() {

             hash_++;

             return entry();

         }

     };

     bool underloaded() const {

         // Check if the table is underloaded: < 25% entries used.

         return (capacity_ > kMinCapacity) && (nelements_ + ndeleted_ < capacity_ / 4);

     }

     bool overloaded() const {

         // Grow if the table is overloaded: > 75% entries used.

         return (nelements_ + ndeleted_) > ((capacity_ / 2) + (capacity_ / 4));

     }

     bool shrink() {

         return changeCapacity(capacity_ >> 1);

     }

     bool grow() {

         KE_ASSERT(IsPowerOfTwo(kMaxCapacity));

         if (capacity_ >= kMaxCapacity) {

             this->reportAllocationOverflow();

             return false;

         }

         return changeCapacity(capacity_ << 1);

     }

     bool checkDensity() {

         if (underloaded())

             return shrink(); 

         if (overloaded())

             return grow();

         return true;

     }

     bool changeCapacity(uint32 newCapacity) {

         KE_ASSERT(newCapacity <= kMaxCapacity);

         Entry *newTable = createTable(newCapacity);

         if (!newTable)

             return false;

         Entry *oldTable = table_;

         uint32 oldCapacity = capacity_;

         table_ = newTable;

         capacity_ = newCapacity;

         ndeleted_ = 0;

         for (uint32 i = 0; i < oldCapacity; i++) {

             Entry &oldEntry = oldTable[i];

             if (oldEntry.isLive()) {

                 Insert p = insertUnique(oldEntry.hash());

                 p.entry().setHash(p.hash());

                 p.entry().payload() = oldEntry.payload();

             }

             oldEntry.destruct();

         }

         this->free(table_);

         return true;

     }

     // For use when the key is known to be unique.

     Insert insertUnique(uint32 hash) {

         Probulator probulator(hash, capacity_);

         Entry *e = &table_[probulator.entry()];

         for (;;) {

             if (e->free() || e->removed())

                 break;

             e = &table_[probulator.next()];

         }

         return Insert(e, hash);

     }

     template <typename Key>

     Result lookup(const Key &key) {

         uint32 hash = computeHash(key);

         Probulator probulator(hash, capacity_);

         Entry *e = &table_[probulator.entry()];

         for (;;) {

             if (e->free())

                 break;

             if (e->isLive() &&

                 e->sameHash(hash) &&

                 HashPolicy::matches(key, e->payload()))

             {

                 return Result(e);

             }

             e = &table_[probulator.next()];

         }

         return Result(e);

     }

     template <typename Key>

     Insert lookupForAdd(const Key &key) {

         uint32 hash = computeHash(key);

         Probulator probulator(hash, capacity_);

         Entry *e = &table_[probulator.entry()];

         for (;;) {

             if (!e->isLive())

                 break;

             if (e->sameHash(hash) && HashPolicy::matches(key, e->payload()))

                 break;

             e = &table_[probulator.next()];

         }

         return Insert(e, hash);

     }

     bool add(Insert &i) {

         KE_ASSERT(!i.found());

         // If the entry is deleted, just re-use the slot.

         if (i.entry().removed()) {

             ndeleted_--;

             return true;

         }

         // Otherwise, see if we're at max capacity.

         if (nelements_ == kMaxCapacity) {

             this->reportAllocationOverflow();

             return false;

         }

         // Check if the table is over or underloaded. The table is always at

         // least 25% free, so this check is enough to guarantee one free slot.

         // (Without one free slot, insertion search could infinite loop.)

         uint32 oldCapacity = capacity_;

         if (!checkDensity())

             return false;

         // If the table changed size, we need to find a new insertion point.

         // Note that a removed entry is impossible: either we caught it above,

         // or we just resized and no entries are removed.

         if (capacity_ != oldCapacity)

             i = insertUnique(i.hash());

         i.entry().setHash(i.hash());

         nelements_++;

         return true;

     }

   public:

     HashTable(AllocPolicy ap)

       : AllocPolicy(ap),

         capacity_(0),

         nelements_(0),

         ndeleted_(0),

         table_(NULL)

     {

     }

     ~HashTable()

     {

         for (uint32 i = 0; i < capacity_; i++)

             table_[i].destruct();

         this->free(table_);

     }

     bool init(uint32 capacity = 0) {

         if (capacity < kMinCapacity)

             capacity = kMinCapacity;

         else if (capacity > kMaxCapacity)

             capacity = kMaxCapacity;

         KE_ASSERT(IsPowerOfTwo(capacity));

         capacity_ = capacity;

         table_ = createTable(capacity_);

         if (!table_)

             return false;

         return true;

     }

     template <typename Key>

     Result find(const Key &key) {

         return lookup(key);

     }

     template <typename Key>

     Insert findForAdd(const Key &key) {

         return lookupForAdd(key);

     }

     bool add(Insert &i, const Payload &payload) {

         if (!add(i))

             return false;

         *i = payload;

         return true;

     }

 };

 }

 #endif // _INCLUDE_KEIMA_HASHTABLE_H_