/*

 *  Index.cpp

 *  Ottoman

 *

 *  Created by Jens Alfke on 8/27/09.

 *  Copyright 2009 Jens Alfke. All rights reserved.

 *  BSD-Licensed: See the file "LICENSE.txt" for details.

 */

#include "Index.h"

#include "Chunk.h"

#include "File.h"

#include "Dictionary.h"

#include <assert.h>

#include <errno.h>

#include <algorithm>

#include <math.h>

#include <stdint.h>

namespace Mooseyard {

    // Quadratic probing results in fewer bucket tests on lookup, but makes the hash tables

    // significantly larger, which increases the file size. In practice a smaller table size seems

    // to be a bigger win since disk I/O is slow.

    #define PROBE_QUADRATIC 0

    // Similarly use a higher max load than for memory-resident tables, to save space.

    static const float kMaxLoadFactor = 0.85f;

    static const uint32_t kIndexMagicNumber = 0x54378543;

    /** An index (hash-table) entry as stored in the memory-mapped file. */

    class Index::Entry {

    public:

        explicit Entry()                        :_hash(0), _valuePosition(0) { }

        explicit Entry (HashCode h, FilePosition p)

                                                :_hash(h), _valuePosition(p) { }

        LittleEndian<HashCode> hash() const       {return _hash;}

        bool hasHash (LittleEndian<HashCode> h) const {return _hash == h;}

        const KeyValueChunk* value (const File *file) const {

            return (const KeyValueChunk*) file->mappedPosition(_valuePosition);

        }

        FilePosition valuePosition() const      {return _valuePosition;}

        bool isAvailable() const                {return _valuePosition == 0;}   // false if deleted

        bool hasValue() const                   {return _valuePosition > 1;}    // false if deleted

        void markDeleted()                      {_valuePosition = kDeletedPosition;}

        void markEmpty()                        {_valuePosition = 0;}

        static const FilePosition kDeletedPosition = 1;

    private:

        LittleEndian<HashCode> _hash;

        LittleEndian<FilePosition> _valuePosition;

    };

#pragma mark -

#pragma mark CREATION:

    Index::Index (uint32_t itsTableSize)

        :Chunk(sizeof(Index) + itsTableSize*sizeof(Index::Entry), kChunkType),

         _magicNumber(kIndexMagicNumber),

         _count(0),

         _tableSize(itsTableSize)

    { }

    Index* Index::create (int capacity) {

#if PROBE_QUADRATIC

        int tableSize = Dictionary::choosePowerOfTwoSize(capacity);

#else

        int tableSize = Dictionary::chooseAnyOldSize(capacity, kMaxLoadFactor);

#endif

        size_t size = sizeof(Index) + tableSize*sizeof(Index::Entry);

        void* storage = ::operator new(size);

        memset(storage,0,size);

        return new(storage) Index(tableSize);

    }

    const Index* Index::indexMappedAt (const void* ptr) {

        const Index *index = (const Index*)ptr;

        index->validate();

        return index;

    }

    void Index::validate() const  throw(File::Error) {

        if (_magicNumber != kIndexMagicNumber)

            throw File::Error(ERANGE, "Bad Index (wrong magic number)");

        if (_tableSize < 2 || _count > _tableSize)

            throw File::Error(ERANGE, "Bad Index (wrong count or tableSize)");

#if PROBE_QUADRATIC

        if ((_tableSize & (_tableSize-1)) != 0)

            throw File::Error(ERANGE, "Bad Index (size not power of 2)");

#endif

        if (size() != sizeof(Index)+_tableSize*sizeof(Index::Entry))

            throw File::Error(ERANGE, "Bad Index (wrong size)");

    }

    void Index::validateEntries (const File *file) const  throw(File::Error) {

        validate();

        uint32_t size = _tableSize;

        uint32_t count = 0;

        const Entry *entry = table(0);

        for (uint32_t i=0; i<size; i++, entry++) {

            if (entry->hasValue()) {

                count++;

                const KeyValueChunk *chunk = entry->value(file);

                if ((void*)chunk->end() > (void*)this)

                    throw File::Error(ERANGE, "Bad Index entry (points beyond index)");

                chunk->validate();

                if (entry->hash() != Key::computeHash(chunk->key()))

                    throw File::Error(ERANGE, "Bad Index entry (wrong hash code)");

            }

        }

        if (count != _count)

            throw File::Error(ERANGE, "Bad Index (inconsistent count)");

    }

#pragma mark -

#pragma mark LOOKUP:

    const Index::Entry* Index::table (int index) const {

        return &((const Index::Entry*)&_table)[index];

    }

    Index::Entry* Index::table (int index) {

        return &((Index::Entry*)&_table)[index];

    }

    const KeyValueChunk* Index::_find (File *file, Key key) const {

        int index = key.hash % _tableSize;

        LittleEndian<HashCode> lhash = key.hash;

#if PROBE_QUADRATIC

        int probe = 0;

#endif

        for(;;) {

            const Index::Entry *found = table(index);

            if (found->isAvailable()) {

                return NULL;

            } else if (found->hasHash(lhash)) {

                const KeyValueChunk *value = found->value(file);

                if (value->hasKey(key)) {

                    return value;

                }

            }

#if PROBE_QUADRATIC

            index = (index + ++probe) % _tableSize;

#else

            index = (index + 1) % _tableSize;

#endif

        }

    }

    Blob Index::get (File *file, Key key) const {

        const KeyValueChunk *kv = _find(file, key);

        return kv ?kv->value() :Blob();

    }

    // Common implementation of put and delete. (If deleting, valuePosition will be kDeletedPosition.)

    // While searching, entries past maxPosition should be considered newly-added and not compared,

    // since they're not in the memory-mapped part of the file yet.

    // Returns true if the entry was added/removed.

    bool Index::_put (File *file, Key key, FilePosition valuePosition, FilePosition maxPosition) {

        bool result = (valuePosition <= Entry::kDeletedPosition);

        int index = key.hash % _tableSize;

        Index::Entry entry(key.hash, valuePosition);

#if PROBE_QUADRATIC

        int probe = 0;

#endif

        Index::Entry *found;

        for(;;) {

            found = table(index);

            if (!found->hasValue()) {

                if (entry.hasValue()) {

                    result = true;

                    break;                  // it's a put and we found an empty entry

                } else if (found->isAvailable()) {

                    return false;           // it's a delete but the key wasn't found

                }

            }

            else if (found->hasHash(entry.hash())) {

                if (!file)

                    break;                  // no file given, so assume no duplicate keys

                else if (found->valuePosition() < maxPosition && found->value(file)->hasKey(key))

                    break;                  // found existing (not newly-inserted) entry with the matching key

                /*else

                    printf("** hash collision! hash=%u\n", key.hash);*/

            }

#if PROBE_QUADRATIC

            index = (index + ++probe) % _tableSize;

#else

            index = (index + 1) % _tableSize;

#endif

        }

        // Finally found where to put it:

        *found = entry;

        return result;

    }

    bool Index::put (File *file, Key key, FilePosition valuePosition, FilePosition maxPosition) {

        bool added = _put(file, key, valuePosition, maxPosition);

        if (added)

            ++_count;

        return added;

    }

    bool Index::remove (File *file, Key key, FilePosition maxPosition) {

        bool removed = _put(file, key, Index::Entry::kDeletedPosition, maxPosition);

        if (removed) {

            assert(_count > 0);

            --_count;

        }

        return removed;

    }

    void Index::removeAll () {

        memset(table(0), 0, _tableSize*sizeof(Entry));

        _count = 0;

    }

    void Index::copyFrom (File *file, const Index *index) {

        const Entry *src = index->table(0);

        if (index->_tableSize == _tableSize) {

            memcpy(table(0), src, _tableSize*sizeof(Entry));

        } else {

            removeAll();

            for (uint32_t i=0; i<index->_tableSize; i++,src++)

                if (src->hasValue())

                    _put(NULL, Key(NULL,0,src->hash()), src->valuePosition(), UINT32_MAX);

        }

        _count = index->count();

    }        

    Index::Iterator::Iterator (File *file, const Index *index)

        :_file(file),

         _current(index->table(-1)),

         _end(index->table(index->_tableSize))

    {

        next();

    }

    bool Index::Iterator::hasValue() const  {return _current != NULL;}

    Key Index::Iterator::key() const        {return Key(_current->value(_file)->key(), _current->hash());}

    Blob Index::Iterator::value() const     {return _current->value(_file)->value();}

    bool Index::Iterator::next() {

        if (_current) {

            while (++_current < _end) {

                if (_current->hasValue())

                    return true;

            }

            _current = NULL;

        }

        return false;

    }

    FilePosition Index::Iterator::valuePosition() {

        return _current ?_current->valuePosition() :0;

    }

}