1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/Hash.cpp Sun Sep 20 15:14:12 2009 -0700
1.3 @@ -0,0 +1,160 @@
1.4 +/*
1.5 + * Hash.cpp
1.6 + * Ottoman
1.7 + *
1.8 + * Created by Jens Alfke on 8/20/09.
1.9 + * Copyright 2009 Jens Alfke. All rights reserved.
1.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
1.11 + */
1.12 +
1.13 +#include "Hash.h"
1.14 +#include "Dictionary.h"
1.15 +#include <algorithm>
1.16 +
1.17 +namespace Mooseyard {
1.18 +
1.19 + class Hash::IndexEntry {
1.20 + public:
1.21 + IndexEntry (Key key, Hash::Value value =NULL)
1.22 + :_key(key),
1.23 + _value(value)
1.24 + { }
1.25 +
1.26 + Key key() const {return _key;}
1.27 + HashCode hash() const {return _key.hash;}
1.28 + Hash::Value value() const {return _key.bytes ?_value :NULL;}
1.29 + void setValue (Hash::Value value) {_value = value;}
1.30 +
1.31 + bool isAvailable() const {return _value == NULL;} // false if deleted
1.32 + bool hasValue() const {return _key.bytes != NULL;}// false if deleted
1.33 + bool operator==(const IndexEntry &e) const {return _key.hash==e._key.hash && _key.equals(e._key);}
1.34 + bool operator!=(const IndexEntry &e) const {return ! (*this==e);}
1.35 +
1.36 + void markDeleted() {_key.bytes = NULL; _value = (Hash::Value)-1;}
1.37 + void markEmpty() {_key.bytes = NULL; _value = NULL;}
1.38 +
1.39 + private:
1.40 + Key _key; // bytes will be NULL if empty or deleted
1.41 + Hash::Value _value; // NULL if empty, -1 if deleted
1.42 + };
1.43 +
1.44 +
1.45 + Hash::Hash (int capacity)
1.46 + :_count(0),
1.47 + _tableSize( Dictionary::choosePowerOfTwoSize(capacity) ),
1.48 + _table( (IndexEntry*) calloc(_tableSize,sizeof(IndexEntry)) )
1.49 + { }
1.50 +
1.51 + Hash::~Hash() {
1.52 + free(_table);
1.53 + }
1.54 +
1.55 + Hash::IndexEntry& Hash::_find (Key key) const {
1.56 + Key k = Key(key);
1.57 + IndexEntry newEntry(k);
1.58 + int index = newEntry.hash() % _tableSize;
1.59 + IndexEntry *found = &_table[index];
1.60 + int probe = 0;
1.61 + while (!found->isAvailable() && (!found->hasValue() || *found != newEntry)) {
1.62 + index = (index + ++probe) % _tableSize;
1.63 + found = &_table[index];
1.64 + }
1.65 + return *found;
1.66 + }
1.67 +
1.68 + Hash::IndexEntry& Hash::_findForPut (const Hash::IndexEntry &newEntry) {
1.69 + int index = newEntry.hash() % _tableSize;
1.70 + IndexEntry *found = &_table[index];
1.71 + int probe = 0;
1.72 + while (found->hasValue() && *found != newEntry) {
1.73 + index = (index + ++probe) % _tableSize;
1.74 + found = &_table[index];
1.75 + }
1.76 + return *found;
1.77 + }
1.78 +
1.79 + Hash::Value Hash::get(Key key) const {
1.80 + return _find(key).value();
1.81 + }
1.82 +
1.83 + void Hash::put(Key key, Hash::Value value) {
1.84 + IndexEntry newEntry = IndexEntry(Key(key),value);
1.85 + IndexEntry &found = _findForPut(newEntry);
1.86 + if (found.hasValue())
1.87 + found.setValue(value);
1.88 + else {
1.89 + found = newEntry;
1.90 + _count++;
1.91 + if (_count/(float)_tableSize > Dictionary::kMaxLoadFactor)
1.92 + _resize(2*_tableSize);
1.93 + }
1.94 + }
1.95 +
1.96 + bool Hash::remove(Key key) {
1.97 + IndexEntry &entry = _find(key);
1.98 + if (!entry.value())
1.99 + return false;
1.100 + entry.markDeleted();
1.101 + _count--;
1.102 + if (_count/(float)_tableSize < Dictionary::kMinLoadFactor)
1.103 + _resize(_tableSize/2);
1.104 + return true;
1.105 + }
1.106 +
1.107 + void Hash::removeAll() {
1.108 + memset(_table, 0, _tableSize*sizeof(*_table));
1.109 + _count = 0;
1.110 + }
1.111 +
1.112 + void Hash::dump() const {
1.113 + for (int index=0; index<_tableSize; index++)
1.114 + if (_table[index].hasValue()) {
1.115 + Blob key = _table[index].key();
1.116 + printf("%3i: %*s -> %p\n",
1.117 + index, (int)key.length,(const char*)key.bytes, _table[index].value());
1.118 + }
1.119 + }
1.120 +
1.121 +
1.122 + void Hash::_resize(int newSize) {
1.123 + newSize = std::max(newSize, Dictionary::kMinSize);
1.124 + if (newSize != _tableSize) {
1.125 + IndexEntry* oldTable = _table;
1.126 + int oldTableSize = _tableSize;
1.127 + _tableSize = newSize;
1.128 + _table = (IndexEntry*) calloc(_tableSize,sizeof(IndexEntry));
1.129 +
1.130 + // Add existing entries to new table:
1.131 + for (int index=0; index<oldTableSize; index++) {
1.132 + IndexEntry &entry = oldTable[index];
1.133 + if (entry.value())
1.134 + _findForPut(entry) = entry;
1.135 + }
1.136 + free(oldTable);
1.137 + }
1.138 + }
1.139 +
1.140 + Hash::Iterator::Iterator (const Hash *hash)
1.141 + :_entry(hash->_table-1), _end(hash->_table+hash->_tableSize)
1.142 + {
1.143 + next();
1.144 + }
1.145 +
1.146 + Hash::Iterator::Iterator (const Hash &hash)
1.147 + :_entry(hash._table-1), _end(hash._table+hash._tableSize)
1.148 + {
1.149 + next();
1.150 + }
1.151 +
1.152 + bool Hash::Iterator::next() {
1.153 + while (++_entry < _end) {
1.154 + if (_entry->hasValue())
1.155 + return true;
1.156 + }
1.157 + return false;
1.158 + }
1.159 +
1.160 + Key Hash::Iterator::key() const {return _entry->key();}
1.161 + Hash::Value Hash::Iterator::value() const {return _entry->value();}
1.162 +
1.163 +}