// 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_