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

  *

  * Copyright (C) 2012 David Anderson

  *

  * This file is part of SourcePawn.

  *

  * SourcePawn is free software: you can redistribute it and/or modify it under

  * the terms of the GNU General Public License as published by the Free

  * Software Foundation, either version 3 of the License, or (at your option)

  * any later version.

  * 

  * SourcePawn is distributed in the hope that it will be useful, but WITHOUT ANY

  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS

  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

  *

  * You should have received a copy of the GNU General Public License along with

  * SourcePawn. If not, see http://www.gnu.org/licenses/.

  */

 #ifndef _INCLUDE_KEIMA_HASHTABLE_H_

 #define _INCLUDE_KEIMA_HASHTABLE_H_

 #include <new>

 #include <limits.h>

 #include "Utility.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;

         t_ = T();

     }

     void construct() {

         hash_ = kFreeHash;

         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

 {

     friend class iterator;

     typedef typename HashPolicy::Payload Payload;

     typedef HashTableEntry<Payload> Entry;

     uint32 capacity_;

     uint32 nelements_;

     uint32 ndeleted_;

     Entry *table_;

     uint32 minCapacity_;

   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) {

         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)

         {

             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() {

         if ((capacity_ >> 1) < minCapacity_)

             return true;

         return changeCapacity(capacity_ >> 1);

     }

     bool grow() {

         if (capacity_ >= kMaxCapacity) {

             this->reportAllocationOverflow();

             return false;

         }

         return changeCapacity(capacity_ << 1);

     }

     bool changeCapacity(uint32 newCapacity) {

         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(oldTable);

         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) {

         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;

     }

     void remove(Entry &e) {

         assert(e.isLive());

         e.setRemoved();

         ndeleted_++;

         nelements_--;

     }

   public:

     HashTable(AllocPolicy ap)

       : AllocPolicy(ap),

         capacity_(0),

         nelements_(0),

         ndeleted_(0),

         table_(NULL),

         minCapacity_(kMinCapacity)

     {

     }

     ~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) {

             this->reportAllocationOverflow();

             return false;

         }

         minCapacity_ = capacity;

         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;

     }

     bool checkDensity() {

         if (underloaded())

             return shrink(); 

         if (overloaded())

             return grow();

         return true;

     }

   public:

     class iterator

     {

         HashTable *table_;

         Entry *i_;

         Entry *end_;

       public:

         iterator(HashTable *table)

           : table_(table),

             i_(table->table_),

             end_(table->table_ + table->capacity_)

         {

             while (i_ < end_ && !i_->isLive())

                 i_++;

         }

         bool empty() const {

             return i_ == end_;

         }

         void erase() {

             assert(!empty());

             table_->remove(*i_);

         }

         const Payload &operator *() const {

             return i_->payload();

         }

         void next() {

             do {

                 i_++;

             } while (i_ < end_ && !i_->isLive());

         }

     };

 };

 }

 #endif // _INCLUDE_KEIMA_HASHTABLE_H_