jens@0: /*
jens@0:  *  Hash.cpp
jens@0:  *  Ottoman
jens@0:  *
jens@0:  *  Created by Jens Alfke on 8/20/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 "Hash.h"
jens@0: #include "Dictionary.h"
jens@0: #include <algorithm>
jens@0: 
jens@0: namespace Mooseyard {
jens@0:     
jens@0:     class Hash::IndexEntry {
jens@0:     public:
jens@0:         IndexEntry (Key key, Hash::Value value =NULL)
jens@0:             :_key(key), 
jens@0:              _value(value) 
jens@0:         { }
jens@0:         
jens@0:         Key key() const                             {return _key;}
jens@0:         HashCode hash() const                       {return _key.hash;}
jens@0:         Hash::Value value() const                   {return _key.bytes ?_value :NULL;}
jens@0:         void setValue (Hash::Value value)           {_value = value;}
jens@0:         
jens@0:         bool isAvailable() const                    {return _value == NULL;}    // false if deleted
jens@0:         bool hasValue() const                       {return _key.bytes != NULL;}// false if deleted
jens@0:         bool operator==(const IndexEntry &e) const  {return _key.hash==e._key.hash && _key.equals(e._key);}
jens@0:         bool operator!=(const IndexEntry &e) const  {return ! (*this==e);}
jens@0:         
jens@0:         void markDeleted()                          {_key.bytes = NULL; _value = (Hash::Value)-1;}
jens@0:         void markEmpty()                            {_key.bytes = NULL; _value = NULL;}
jens@0:         
jens@0:     private:
jens@0:         Key _key;                       // bytes will be NULL if empty or deleted
jens@0:         Hash::Value _value;             // NULL if empty, -1 if deleted
jens@0:     };
jens@0:         
jens@0:             
jens@0:     Hash::Hash (int capacity)
jens@0:         :_count(0),
jens@0:          _tableSize( Dictionary::choosePowerOfTwoSize(capacity) ),
jens@0:          _table( (IndexEntry*) calloc(_tableSize,sizeof(IndexEntry)) )
jens@0:     { }
jens@0:     
jens@0:     Hash::~Hash() {
jens@0:         free(_table);
jens@0:     }
jens@0:     
jens@0:     Hash::IndexEntry& Hash::_find (Key key) const {
jens@0:         Key k = Key(key);
jens@0:         IndexEntry newEntry(k);
jens@0:         int index = newEntry.hash() % _tableSize;
jens@0:         IndexEntry *found = &_table[index];
jens@0:         int probe = 0;
jens@0:         while (!found->isAvailable() && (!found->hasValue() || *found != newEntry)) {
jens@0:             index = (index + ++probe) % _tableSize;
jens@0:             found = &_table[index];
jens@0:         }
jens@0:         return *found;
jens@0:     }
jens@0:     
jens@0:     Hash::IndexEntry& Hash::_findForPut (const Hash::IndexEntry &newEntry) {
jens@0:         int index = newEntry.hash() % _tableSize;
jens@0:         IndexEntry *found = &_table[index];
jens@0:         int probe = 0;
jens@0:         while (found->hasValue() && *found != newEntry) {
jens@0:             index = (index + ++probe) % _tableSize;
jens@0:             found = &_table[index];
jens@0:         }
jens@0:         return *found;
jens@0:     }
jens@0:     
jens@0:     Hash::Value Hash::get(Key key) const {
jens@0:         return _find(key).value();
jens@0:     }
jens@0:     
jens@0:     void Hash::put(Key key, Hash::Value value) {
jens@0:         IndexEntry newEntry = IndexEntry(Key(key),value);
jens@0:         IndexEntry &found = _findForPut(newEntry);
jens@0:         if (found.hasValue())
jens@0:             found.setValue(value);
jens@0:         else {
jens@0:             found = newEntry;
jens@0:             _count++;
jens@0:             if (_count/(float)_tableSize > Dictionary::kMaxLoadFactor)
jens@0:                 _resize(2*_tableSize);
jens@0:         }
jens@0:     }
jens@0:     
jens@0:     bool Hash::remove(Key key) {
jens@0:         IndexEntry &entry = _find(key);
jens@0:         if (!entry.value())
jens@0:             return false;
jens@0:         entry.markDeleted();
jens@0:         _count--;
jens@0:         if (_count/(float)_tableSize < Dictionary::kMinLoadFactor)
jens@0:             _resize(_tableSize/2);
jens@0:         return true;
jens@0:     }
jens@0:         
jens@0:     void Hash::removeAll() {
jens@0:         memset(_table, 0, _tableSize*sizeof(*_table));
jens@0:         _count = 0;
jens@0:     }
jens@0:     
jens@0:     void Hash::dump() const {
jens@0:         for (int index=0; index<_tableSize; index++)
jens@0:             if (_table[index].hasValue()) {
jens@0:                 Blob key = _table[index].key();
jens@0:                 printf("%3i: %*s -> %p\n", 
jens@0:                        index, (int)key.length,(const char*)key.bytes, _table[index].value());
jens@0:             }
jens@0:     }
jens@0:     
jens@0:     
jens@0:     void Hash::_resize(int newSize) {
jens@0:         newSize = std::max(newSize, Dictionary::kMinSize);
jens@0:         if (newSize != _tableSize) {
jens@0:             IndexEntry* oldTable = _table;
jens@0:             int oldTableSize = _tableSize;
jens@0:             _tableSize = newSize;
jens@0:             _table = (IndexEntry*) calloc(_tableSize,sizeof(IndexEntry));
jens@0:             
jens@0:             // Add existing entries to new table:
jens@0:             for (int index=0; index<oldTableSize; index++) {
jens@0:                 IndexEntry &entry = oldTable[index];
jens@0:                 if (entry.value())
jens@0:                     _findForPut(entry) = entry;
jens@0:             }
jens@0:             free(oldTable);
jens@0:         }
jens@0:     }
jens@0:     
jens@0:     Hash::Iterator::Iterator (const Hash *hash)
jens@0:         :_entry(hash->_table-1), _end(hash->_table+hash->_tableSize)
jens@0:     {
jens@0:         next();
jens@0:     }
jens@0: 
jens@0:     Hash::Iterator::Iterator (const Hash &hash)
jens@0:         :_entry(hash._table-1), _end(hash._table+hash._tableSize)
jens@0:     {
jens@0:         next();
jens@0:     }
jens@0: 
jens@0:     bool Hash::Iterator::next() {
jens@0:         while (++_entry < _end) {
jens@0:             if (_entry->hasValue())
jens@0:                 return true;
jens@0:         }
jens@0:         return false;
jens@0:     }
jens@0: 
jens@0:     Key Hash::Iterator::key() const                 {return _entry->key();}
jens@0:     Hash::Value Hash::Iterator::value() const       {return _entry->value();}
jens@0:     
jens@0: }