diff -r 000000000000 -r 31a43d94cc26 src/Dictionary.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/Dictionary.cpp	Sun Sep 20 15:14:12 2009 -0700
@@ -0,0 +1,376 @@
+/*
+ *  Dictionary.cpp
+ *  Ottoman
+ *
+ *  Created by Jens Alfke on 8/23/09.
+ *  Copyright 2009 Jens Alfke. All rights reserved.
+ *  BSD-Licensed: See the file "LICENSE.txt" for details.
+ */
+
+#include "Dictionary.h"
+#include "Hash.h"
+#include <assert.h>
+#include <algorithm>
+#include <math.h>
+
+namespace Mooseyard {
+    
+    Dictionary::Dictionary() {
+    }
+    
+    Dictionary::~Dictionary() {
+    }
+    
+    Dictionary::Iterator::~Iterator() {
+    }
+    
+    
+    const int Dictionary::kMinSize = 8;
+    const float Dictionary::kMinLoadFactor = 0.25;
+    const float Dictionary::kMaxLoadFactor = 0.75;
+        
+    // Choose the smallest power of two that's large enough to hold the given capacity
+    // of entries with no greater than the given load (fraction full).
+    int Dictionary::choosePowerOfTwoSize (int capacity, float load) {
+        int idealSize = capacity / load;
+        int size;
+        for (size=kMinSize; size<idealSize; size *= 2)
+            ;
+        return size;
+    }
+    
+    int Dictionary::chooseAnyOldSize (int capacity, float load) {
+        return std::max((int)::ceil(capacity / load), 2);
+    }
+    
+    
+    //-----------------------------------------------------------------------------
+    // MurmurHashNeutral2, by Austin Appleby
+    // http://murmurhash.googlepages.com/MurmurHashNeutral2.cpp
+    
+    // Same as MurmurHash2, but endian- and alignment-neutral.
+    // Half the speed though, alas.
+    
+    static uint32_t MurmurHashNeutral2 ( const void * key, int32_t len, uint32_t seed )
+    {
+        static const uint32_t m = 0x5bd1e995;
+        static const int32_t r = 24;
+        
+        uint32_t h = seed ^ len;
+        
+        const unsigned char * data = (const unsigned char *)key;
+        
+        while(len >= 4)
+        {
+            uint32_t k;
+            
+            k  = data[0];
+            k |= data[1] << 8;
+            k |= data[2] << 16;
+            k |= data[3] << 24;
+            
+            k *= m; 
+            k ^= k >> r; 
+            k *= m;
+            
+            h *= m;
+            h ^= k;
+            
+            data += 4;
+            len -= 4;
+        }
+        
+        switch(len)
+        {
+            case 3: h ^= data[2] << 16;
+            case 2: h ^= data[1] << 8;
+            case 1: h ^= data[0];
+                h *= m;
+        };
+        
+        h ^= h >> 13;
+        h *= m;
+        h ^= h >> 15;
+        
+        return h;
+    } 
+    
+    HashCode Key::computeHash (Blob key) {
+        return MurmurHashNeutral2(key.bytes, key.length, 0);
+    }
+    
+    
+    
+    void MutableDictionary::add (Dictionary* dict) {
+        Iterator *it = dict->iterate();
+        for (; *it; it->next())
+            put(it->key(), it->value());
+        delete it;
+    }
+    
+    
+        
+    const Dictionary& Dictionary::kEmpty = * new HashDictionary();
+    
+
+#pragma mark -
+#pragma mark KEY AND VALUE
+    
+    class KeyAndValue {
+    public:
+        static KeyAndValue* create (Blob key, Blob value) {
+            size_t size = 2*sizeof(uint32_t) + key.length;
+            size = (size + 0x3) & ~0x3; // 32-bit align start of value
+            if (value!=kDeletedValue)
+                size += value.length;
+            KeyAndValue *kv = (KeyAndValue*) ::operator new(size);
+            kv->_keyLength = key.length;
+            memcpy(&kv->_keyLength + 1, key.bytes, key.length);
+            uint32_t *valueLengthPtr = const_cast<uint32_t*>(kv->valueLengthPtr());
+            *valueLengthPtr = value.length;
+            if (value!=kDeletedValue)
+                memcpy(valueLengthPtr + 1, value.bytes, value.length);
+            return kv;
+        }
+        Blob key() const {
+            return Blob(&_keyLength+1, _keyLength);
+        }
+        
+        Blob value() const{
+            const uint32_t *v = this->valueLengthPtr();
+            if (*v != kDeletedValue.length)
+                return Blob(v+1, *v);
+            else
+                return kDeletedValue;
+        }
+
+        /** Magic value OverlayDictionary stores in me to represent a deleted value. */
+        static const Blob kDeletedValue;
+    private:
+        const uint32_t* valueLengthPtr() const {
+            size_t ptr = (size_t)(&_keyLength + 1) + _keyLength;
+            ptr = (ptr + 0x3) & ~0x3;       // 32-bit align
+            return (uint32_t*)ptr;
+        }
+        
+        uint32_t _keyLength;
+        //...there follows the key, valueLength and value...
+    };
+
+    const Blob KeyAndValue::kDeletedValue(NULL, (size_t)-1);
+
+    
+
+    
+#pragma mark -
+#pragma mark HASH DICTIONARY:
+    
+    HashDictionary::~HashDictionary() {
+        removeAll();
+    }
+    
+    Blob HashDictionary::_convertValue (void *value) {
+        return value ?((KeyAndValue*)value)->value() :Blob();
+    }
+    
+    bool HashDictionary::contains (Key key) const {
+        Blob value = get(key);
+        return value.bytes || value.length;
+    }
+
+    
+    void HashDictionary::put (Key key, Blob value) {
+        // Allocate a block to store both the Blob struct and the data
+        KeyAndValue *kv = KeyAndValue::create(key,value);
+        _hash.put(Key(kv->key(),key.hash), kv);
+    }
+    
+    bool HashDictionary::remove (Key key) {
+        KeyAndValue *kv = (KeyAndValue*) _hash.get(key);
+        if (kv) {
+            free(kv);
+            return true;
+        } else
+            return false;
+    }
+    
+    void HashDictionary::removeAll() {
+        for (Hash::Iterator it(&_hash); it; ++it)
+            free(it.value());
+        _hash.removeAll();
+    }
+        
+    
+    
+    
+#pragma mark -
+#pragma mark OVERLAY DICTIONARY:
+    
+    
+    OverlayDictionary::OverlayDictionary (const Dictionary *base)
+    :_base(base),
+     _overlay(new HashDictionary()),
+     _count(base->count()),
+     _allRemoved(false)
+    { }
+    
+    OverlayDictionary::~OverlayDictionary() {
+        delete _overlay;
+    }
+    
+    int OverlayDictionary::count() const {
+        return _count;
+    }
+    
+    bool OverlayDictionary::isChanged() const {
+        return _overlay->count() > 0;
+    }
+    
+    Blob OverlayDictionary::get (Key key) const {
+        Blob result = _overlay->get(key);
+        if (!result) {
+            if (result==KeyAndValue::kDeletedValue)
+                result = Blob();                // It's been marked as deleted
+            else if (!_allRemoved)
+                result = _base->get(key);
+        }
+        return result;
+    }
+    
+    bool OverlayDictionary::contains (Key key) const {
+        Blob result = _overlay->get(key);
+        if (result)
+            return true;
+        else if (result==KeyAndValue::kDeletedValue)
+            return false;
+        else if (!_allRemoved)
+            return _base->get(key);
+        else 
+            return false;
+    }
+    
+    void OverlayDictionary::put (Key key, Blob value) {
+        assert(value.bytes || value.length==0);    // make sure it doesn't look like magic kDeletedValue
+        _overlay->put(key,value);
+        if (_allRemoved || !_base->contains(key))
+            _count++;
+    }
+    
+    bool OverlayDictionary::remove (Key key) {
+        if (!_allRemoved && _base->contains(key)) {
+            _overlay->put(key,KeyAndValue::kDeletedValue);
+            _count--;
+            return true;
+        } else if (_overlay->remove(key)) {
+            _count--;
+            return true;
+        } else
+            return false;
+    }
+    
+    void OverlayDictionary::removeAll() {
+        _allRemoved = true;
+        _count = 0;
+    }
+    
+    
+    void OverlayDictionary::revert() {
+        _overlay->removeAll();
+        _count = _base->count();
+        _allRemoved = false;
+    }
+    
+    void OverlayDictionary::revertTo (const Dictionary* newBase) {
+        _base = newBase;
+        revert();
+    }
+    
+    void OverlayDictionary::rebase (const Dictionary* newBase) {
+        _base = newBase;
+    }
+
+    OverlayDictionary::Iterator::Iterator (const OverlayDictionary &dict)
+        :_iter(dict.base()->iterate()),
+         _overlay(dict._overlay)
+    {
+        if (skipCurrentState())
+            next();
+    }
+    
+    Key OverlayDictionary::Iterator::key() const        {return _iter ?_iter->key() :Key();}
+    Blob OverlayDictionary::Iterator::value() const     {return _iter ?_iter->value() :Blob();}
+    
+    bool OverlayDictionary::Iterator::next() {
+        if (_iter) {
+            do {
+                _iter->next();
+            } while (skipCurrentState());
+        }
+        return _iter && *_iter;
+    }
+    
+    bool OverlayDictionary::Iterator::skipCurrentState() {
+        if (_iter) {
+            if (*_iter) {
+                if (_overlay) {
+                    if (_overlay->contains(_iter->key()))
+                        return true;        // Skip overridden value in base dict
+                } else {
+                    if (_iter->value() == KeyAndValue::kDeletedValue)
+                        return true;        // Skip marked-deleted value in overlay dict
+                }
+            } else {
+                delete _iter;
+                if (_overlay) {
+                    // end of base iterator; switch to overlay
+                    _iter = _overlay->iterate();
+                    _overlay = NULL;
+                    return skipCurrentState();
+                } else {
+                    _iter = NULL;
+                }
+            }
+        }
+        return false;
+    }
+    
+    
+#pragma mark -
+#pragma mark CHANGE ITERATOR:
+    
+    
+    Dictionary::ChangeIterator::ChangeIterator (const Dictionary *dict1, const Dictionary *dict2) {
+        _init(dict1, dict2);
+    }
+    
+    Dictionary::ChangeIterator::ChangeIterator (const OverlayDictionary *overlay) {
+        _init(overlay->_overlay, overlay->base());
+    }
+    
+    void Dictionary::ChangeIterator::_init(const Dictionary *dict1, const Dictionary *dict2) {
+        _dict2 = dict2;
+        _iter = dict1->iterate();
+        if (*_iter)
+            _skipMatching();
+    }
+    
+    Dictionary::ChangeIterator::~ChangeIterator() {
+        delete _iter;
+    }
+    
+    bool Dictionary::ChangeIterator::next() {
+        return _iter->next() && this->_skipMatching();
+    }
+    
+    bool Dictionary::ChangeIterator::_skipMatching() {
+        do{
+            _otherValue = _dict2->get(_iter->key());
+            if (!_otherValue.equals(_iter->value()))
+                return true;
+        }while (_iter->next());
+        return false;
+    }
+    
+    
+
+}