jens@0: /*
jens@0:  *  Index.cpp
jens@0:  *  Ottoman
jens@0:  *
jens@0:  *  Created by Jens Alfke on 8/27/09.
jens@0:  *  Copyright 2009 Jens Alfke. All rights reserved.
jens@0:  *  BSD-Licensed: See the file "LICENSE.txt" for details.
jens@0:  */
jens@0: 
jens@0: #include "Index.h"
jens@0: #include "Chunk.h"
jens@0: #include "File.h"
jens@0: #include "Dictionary.h"
jens@0: #include <assert.h>
jens@0: #include <errno.h>
jens@0: #include <algorithm>
jens@0: #include <math.h>
jbm@8: #include <stdint.h>
jbm@8: 
jbm@8: 
jens@0: namespace Mooseyard {
jens@0:         
jens@0:     // Quadratic probing results in fewer bucket tests on lookup, but makes the hash tables
jens@0:     // significantly larger, which increases the file size. In practice a smaller table size seems
jens@0:     // to be a bigger win since disk I/O is slow.
jens@0:     #define PROBE_QUADRATIC 0
jens@0: 
jens@0:     // Similarly use a higher max load than for memory-resident tables, to save space.
jens@2:     static const float kMaxLoadFactor = 0.85f;
jens@0: 
jens@0:     static const uint32_t kIndexMagicNumber = 0x54378543;
jens@0:     
jens@0: 
jens@0:     /** An index (hash-table) entry as stored in the memory-mapped file. */
jens@0:     class Index::Entry {
jens@0:     public:
jens@0:         explicit Entry()                        :_hash(0), _valuePosition(0) { }
jens@0:         explicit Entry (HashCode h, FilePosition p)
jens@0:                                                 :_hash(h), _valuePosition(p) { }
jens@0:         LittleEndian<HashCode> hash() const       {return _hash;}
jens@0:         bool hasHash (LittleEndian<HashCode> h) const {return _hash == h;}
jens@0:         
jens@0:         const KeyValueChunk* value (const File *file) const {
jens@0:             return (const KeyValueChunk*) file->mappedPosition(_valuePosition);
jens@0:         }
jens@0:         FilePosition valuePosition() const      {return _valuePosition;}
jens@0:         
jens@0:         
jens@0:         bool isAvailable() const                {return _valuePosition == 0;}   // false if deleted
jens@0:         bool hasValue() const                   {return _valuePosition > 1;}    // false if deleted
jens@0:         
jens@0:         void markDeleted()                      {_valuePosition = kDeletedPosition;}
jens@0:         void markEmpty()                        {_valuePosition = 0;}
jens@0:         
jens@0:         
jens@0:         static const FilePosition kDeletedPosition = 1;
jens@0:                 
jens@0:     private:
jens@0:         LittleEndian<HashCode> _hash;
jens@0:         LittleEndian<FilePosition> _valuePosition;
jens@0:     };
jens@0:         
jens@0:     
jens@0: #pragma mark -
jens@0: #pragma mark CREATION:
jens@0:         
jens@0:     Index::Index (uint32_t itsTableSize)
jens@0:         :Chunk(sizeof(Index) + itsTableSize*sizeof(Index::Entry), kChunkType),
jens@0:          _magicNumber(kIndexMagicNumber),
jens@0:          _count(0),
jens@0:          _tableSize(itsTableSize)
jens@0:     { }
jens@0:     
jens@0:     Index* Index::create (int capacity) {
jens@0: #if PROBE_QUADRATIC
jens@0:         int tableSize = Dictionary::choosePowerOfTwoSize(capacity);
jens@0: #else
jens@0:         int tableSize = Dictionary::chooseAnyOldSize(capacity, kMaxLoadFactor);
jens@0: #endif
jens@0:         size_t size = sizeof(Index) + tableSize*sizeof(Index::Entry);
jens@0:         void* storage = ::operator new(size);
jens@0:         memset(storage,0,size);
jens@0:         return new(storage) Index(tableSize);
jens@0:     }
jens@0:     
jens@0:     const Index* Index::indexMappedAt (const void* ptr) {
jens@0:         const Index *index = (const Index*)ptr;
jens@0:         index->validate();
jens@0:         return index;
jens@0:     }
jens@0:     
jens@0:     void Index::validate() const  throw(File::Error) {
jens@0:         if (_magicNumber != kIndexMagicNumber)
jens@0:             throw File::Error(ERANGE, "Bad Index (wrong magic number)");
jens@0:         if (_tableSize < 2 || _count > _tableSize)
jens@0:             throw File::Error(ERANGE, "Bad Index (wrong count or tableSize)");
jens@0: #if PROBE_QUADRATIC
jens@0:         if ((_tableSize & (_tableSize-1)) != 0)
jens@0:             throw File::Error(ERANGE, "Bad Index (size not power of 2)");
jens@0: #endif
jens@0:         if (size() != sizeof(Index)+_tableSize*sizeof(Index::Entry))
jens@0:             throw File::Error(ERANGE, "Bad Index (wrong size)");
jens@0:     }
jens@0:     
jens@0:     void Index::validateEntries (const File *file) const  throw(File::Error) {
jens@0:         validate();
jens@0:         uint32_t size = _tableSize;
jens@0:         uint32_t count = 0;
jens@0:         const Entry *entry = table(0);
jens@0:         for (uint32_t i=0; i<size; i++, entry++) {
jens@0:             if (entry->hasValue()) {
jens@0:                 count++;
jens@0:                 const KeyValueChunk *chunk = entry->value(file);
jens@0:                 if ((void*)chunk->end() > (void*)this)
jens@0:                     throw File::Error(ERANGE, "Bad Index entry (points beyond index)");
jens@0:                 chunk->validate();
jens@0:                 if (entry->hash() != Key::computeHash(chunk->key()))
jens@0:                     throw File::Error(ERANGE, "Bad Index entry (wrong hash code)");
jens@0:             }
jens@0:         }
jens@0:         if (count != _count)
jens@0:             throw File::Error(ERANGE, "Bad Index (inconsistent count)");
jens@0:     }
jens@0:     
jens@0:     
jens@0: #pragma mark -
jens@0: #pragma mark LOOKUP:
jens@0:     
jens@0:     const Index::Entry* Index::table (int index) const {
jens@0:         return &((const Index::Entry*)&_table)[index];
jens@0:     }
jens@0:     
jens@0:     Index::Entry* Index::table (int index) {
jens@0:         return &((Index::Entry*)&_table)[index];
jens@0:     }
jens@0:     
jens@0:         
jens@0:     const KeyValueChunk* Index::_find (File *file, Key key) const {
jens@0:         int index = key.hash % _tableSize;
jens@0:         LittleEndian<HashCode> lhash = key.hash;
jens@0: #if PROBE_QUADRATIC
jens@0:         int probe = 0;
jens@0: #endif
jens@0:         for(;;) {
jens@0:             const Index::Entry *found = table(index);
jens@0:             if (found->isAvailable()) {
jens@0:                 return NULL;
jens@0:             } else if (found->hasHash(lhash)) {
jens@0:                 const KeyValueChunk *value = found->value(file);
jens@0:                 if (value->hasKey(key)) {
jens@0:                     return value;
jens@0:                 }
jens@0:             }
jens@0: #if PROBE_QUADRATIC
jens@0:             index = (index + ++probe) % _tableSize;
jens@0: #else
jens@0:             index = (index + 1) % _tableSize;
jens@0: #endif
jens@0:         }
jens@0:     }
jens@0:     
jens@0:     Blob Index::get (File *file, Key key) const {
jens@0:         const KeyValueChunk *kv = _find(file, key);
jens@0:         return kv ?kv->value() :Blob();
jens@0:     }
jens@0:     
jens@0: 
jens@0:     // Common implementation of put and delete. (If deleting, valuePosition will be kDeletedPosition.)
jens@0:     // While searching, entries past maxPosition should be considered newly-added and not compared,
jens@0:     // since they're not in the memory-mapped part of the file yet.
jens@0:     // Returns true if the entry was added/removed.
jens@0:     bool Index::_put (File *file, Key key, FilePosition valuePosition, FilePosition maxPosition) {
jens@0:         bool result = (valuePosition <= Entry::kDeletedPosition);
jens@0:         int index = key.hash % _tableSize;
jens@0:         Index::Entry entry(key.hash, valuePosition);
jens@0: #if PROBE_QUADRATIC
jens@0:         int probe = 0;
jens@0: #endif
jens@0:         Index::Entry *found;
jens@0:         for(;;) {
jens@0:             found = table(index);
jens@0:             if (!found->hasValue()) {
jens@0:                 if (entry.hasValue()) {
jens@0:                     result = true;
jens@0:                     break;                  // it's a put and we found an empty entry
jens@0:                 } else if (found->isAvailable()) {
jens@0:                     return false;           // it's a delete but the key wasn't found
jens@0:                 }
jens@0:             }
jens@0:             else if (found->hasHash(entry.hash())) {
jens@0:                 if (!file)
jens@0:                     break;                  // no file given, so assume no duplicate keys
jens@0:                 else if (found->valuePosition() < maxPosition && found->value(file)->hasKey(key))
jens@0:                     break;                  // found existing (not newly-inserted) entry with the matching key
jens@0:                 /*else
jens@0:                     printf("** hash collision! hash=%u\n", key.hash);*/
jens@0:             }
jens@0: #if PROBE_QUADRATIC
jens@0:             index = (index + ++probe) % _tableSize;
jens@0: #else
jens@0:             index = (index + 1) % _tableSize;
jens@0: #endif
jens@0:         }
jens@0:         // Finally found where to put it:
jens@0:         *found = entry;
jens@0:         return result;
jens@0:     }
jens@0:         
jens@0:     bool Index::put (File *file, Key key, FilePosition valuePosition, FilePosition maxPosition) {
jens@0:         bool added = _put(file, key, valuePosition, maxPosition);
jens@0:         if (added)
jens@0:             ++_count;
jens@0:         return added;
jens@0:     }
jens@0:     
jens@0:     bool Index::remove (File *file, Key key, FilePosition maxPosition) {
jens@0:         bool removed = _put(file, key, Index::Entry::kDeletedPosition, maxPosition);
jens@0:         if (removed) {
jens@0:             assert(_count > 0);
jens@0:             --_count;
jens@0:         }
jens@0:         return removed;
jens@0:     }
jens@0:     
jens@0:     void Index::removeAll () {
jens@0:         memset(table(0), 0, _tableSize*sizeof(Entry));
jens@0:         _count = 0;
jens@0:     }
jens@0:     
jens@0:     
jens@0:     void Index::copyFrom (File *file, const Index *index) {
jens@0:         const Entry *src = index->table(0);
jens@0:         if (index->_tableSize == _tableSize) {
jens@0:             memcpy(table(0), src, _tableSize*sizeof(Entry));
jens@0:         } else {
jens@0:             removeAll();
jens@0:             for (uint32_t i=0; i<index->_tableSize; i++,src++)
jens@0:                 if (src->hasValue())
jens@0:                     _put(NULL, Key(NULL,0,src->hash()), src->valuePosition(), UINT32_MAX);
jens@0:         }
jens@0:         _count = index->count();
jens@0:     }        
jens@0:     
jens@0: 
jens@0: 
jens@0:     Index::Iterator::Iterator (File *file, const Index *index)
jens@0:         :_file(file),
jens@0:          _current(index->table(-1)),
jens@0:          _end(index->table(index->_tableSize))
jens@0:     {
jens@0:         next();
jens@0:     }
jens@0:     
jens@0:     bool Index::Iterator::hasValue() const  {return _current != NULL;}
jens@0:     Key Index::Iterator::key() const        {return Key(_current->value(_file)->key(), _current->hash());}
jens@0:     Blob Index::Iterator::value() const     {return _current->value(_file)->value();}
jens@0:     
jens@0:     bool Index::Iterator::next() {
jens@0:         if (_current) {
jens@0:             while (++_current < _end) {
jens@0:                 if (_current->hasValue())
jens@0:                     return true;
jens@0:             }
jens@0:             _current = NULL;
jens@0:         }
jens@0:         return false;
jens@0:     }
jens@0:     
jens@0:     FilePosition Index::Iterator::valuePosition() {
jens@0:         return _current ?_current->valuePosition() :0;
jens@0:     }
jens@0: }