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