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