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