diff -r 000000000000 -r 31a43d94cc26 src/Hash.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/Hash.cpp	Sun Sep 20 15:14:12 2009 -0700
@@ -0,0 +1,160 @@
+/*
+ *  Hash.cpp
+ *  Ottoman
+ *
+ *  Created by Jens Alfke on 8/20/09.
+ *  Copyright 2009 Jens Alfke. All rights reserved.
+ *  BSD-Licensed: See the file "LICENSE.txt" for details.
+ */
+
+#include "Hash.h"
+#include "Dictionary.h"
+#include <algorithm>
+
+namespace Mooseyard {
+    
+    class Hash::IndexEntry {
+    public:
+        IndexEntry (Key key, Hash::Value value =NULL)
+            :_key(key), 
+             _value(value) 
+        { }
+        
+        Key key() const                             {return _key;}
+        HashCode hash() const                       {return _key.hash;}
+        Hash::Value value() const                   {return _key.bytes ?_value :NULL;}
+        void setValue (Hash::Value value)           {_value = value;}
+        
+        bool isAvailable() const                    {return _value == NULL;}    // false if deleted
+        bool hasValue() const                       {return _key.bytes != NULL;}// false if deleted
+        bool operator==(const IndexEntry &e) const  {return _key.hash==e._key.hash && _key.equals(e._key);}
+        bool operator!=(const IndexEntry &e) const  {return ! (*this==e);}
+        
+        void markDeleted()                          {_key.bytes = NULL; _value = (Hash::Value)-1;}
+        void markEmpty()                            {_key.bytes = NULL; _value = NULL;}
+        
+    private:
+        Key _key;                       // bytes will be NULL if empty or deleted
+        Hash::Value _value;             // NULL if empty, -1 if deleted
+    };
+        
+            
+    Hash::Hash (int capacity)
+        :_count(0),
+         _tableSize( Dictionary::choosePowerOfTwoSize(capacity) ),
+         _table( (IndexEntry*) calloc(_tableSize,sizeof(IndexEntry)) )
+    { }
+    
+    Hash::~Hash() {
+        free(_table);
+    }
+    
+    Hash::IndexEntry& Hash::_find (Key key) const {
+        Key k = Key(key);
+        IndexEntry newEntry(k);
+        int index = newEntry.hash() % _tableSize;
+        IndexEntry *found = &_table[index];
+        int probe = 0;
+        while (!found->isAvailable() && (!found->hasValue() || *found != newEntry)) {
+            index = (index + ++probe) % _tableSize;
+            found = &_table[index];
+        }
+        return *found;
+    }
+    
+    Hash::IndexEntry& Hash::_findForPut (const Hash::IndexEntry &newEntry) {
+        int index = newEntry.hash() % _tableSize;
+        IndexEntry *found = &_table[index];
+        int probe = 0;
+        while (found->hasValue() && *found != newEntry) {
+            index = (index + ++probe) % _tableSize;
+            found = &_table[index];
+        }
+        return *found;
+    }
+    
+    Hash::Value Hash::get(Key key) const {
+        return _find(key).value();
+    }
+    
+    void Hash::put(Key key, Hash::Value value) {
+        IndexEntry newEntry = IndexEntry(Key(key),value);
+        IndexEntry &found = _findForPut(newEntry);
+        if (found.hasValue())
+            found.setValue(value);
+        else {
+            found = newEntry;
+            _count++;
+            if (_count/(float)_tableSize > Dictionary::kMaxLoadFactor)
+                _resize(2*_tableSize);
+        }
+    }
+    
+    bool Hash::remove(Key key) {
+        IndexEntry &entry = _find(key);
+        if (!entry.value())
+            return false;
+        entry.markDeleted();
+        _count--;
+        if (_count/(float)_tableSize < Dictionary::kMinLoadFactor)
+            _resize(_tableSize/2);
+        return true;
+    }
+        
+    void Hash::removeAll() {
+        memset(_table, 0, _tableSize*sizeof(*_table));
+        _count = 0;
+    }
+    
+    void Hash::dump() const {
+        for (int index=0; index<_tableSize; index++)
+            if (_table[index].hasValue()) {
+                Blob key = _table[index].key();
+                printf("%3i: %*s -> %p\n", 
+                       index, (int)key.length,(const char*)key.bytes, _table[index].value());
+            }
+    }
+    
+    
+    void Hash::_resize(int newSize) {
+        newSize = std::max(newSize, Dictionary::kMinSize);
+        if (newSize != _tableSize) {
+            IndexEntry* oldTable = _table;
+            int oldTableSize = _tableSize;
+            _tableSize = newSize;
+            _table = (IndexEntry*) calloc(_tableSize,sizeof(IndexEntry));
+            
+            // Add existing entries to new table:
+            for (int index=0; index<oldTableSize; index++) {
+                IndexEntry &entry = oldTable[index];
+                if (entry.value())
+                    _findForPut(entry) = entry;
+            }
+            free(oldTable);
+        }
+    }
+    
+    Hash::Iterator::Iterator (const Hash *hash)
+        :_entry(hash->_table-1), _end(hash->_table+hash->_tableSize)
+    {
+        next();
+    }
+
+    Hash::Iterator::Iterator (const Hash &hash)
+        :_entry(hash._table-1), _end(hash._table+hash._tableSize)
+    {
+        next();
+    }
+
+    bool Hash::Iterator::next() {
+        while (++_entry < _end) {
+            if (_entry->hasValue())
+                return true;
+        }
+        return false;
+    }
+
+    Key Hash::Iterator::key() const                 {return _entry->key();}
+    Hash::Value Hash::Iterator::value() const       {return _entry->value();}
+    
+}