1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/Dictionary.cpp Sun Sep 20 15:14:12 2009 -0700
1.3 @@ -0,0 +1,376 @@
1.4 +/*
1.5 + * Dictionary.cpp
1.6 + * Ottoman
1.7 + *
1.8 + * Created by Jens Alfke on 8/23/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 "Dictionary.h"
1.14 +#include "Hash.h"
1.15 +#include <assert.h>
1.16 +#include <algorithm>
1.17 +#include <math.h>
1.18 +
1.19 +namespace Mooseyard {
1.20 +
1.21 + Dictionary::Dictionary() {
1.22 + }
1.23 +
1.24 + Dictionary::~Dictionary() {
1.25 + }
1.26 +
1.27 + Dictionary::Iterator::~Iterator() {
1.28 + }
1.29 +
1.30 +
1.31 + const int Dictionary::kMinSize = 8;
1.32 + const float Dictionary::kMinLoadFactor = 0.25;
1.33 + const float Dictionary::kMaxLoadFactor = 0.75;
1.34 +
1.35 + // Choose the smallest power of two that's large enough to hold the given capacity
1.36 + // of entries with no greater than the given load (fraction full).
1.37 + int Dictionary::choosePowerOfTwoSize (int capacity, float load) {
1.38 + int idealSize = capacity / load;
1.39 + int size;
1.40 + for (size=kMinSize; size<idealSize; size *= 2)
1.41 + ;
1.42 + return size;
1.43 + }
1.44 +
1.45 + int Dictionary::chooseAnyOldSize (int capacity, float load) {
1.46 + return std::max((int)::ceil(capacity / load), 2);
1.47 + }
1.48 +
1.49 +
1.50 + //-----------------------------------------------------------------------------
1.51 + // MurmurHashNeutral2, by Austin Appleby
1.52 + // http://murmurhash.googlepages.com/MurmurHashNeutral2.cpp
1.53 +
1.54 + // Same as MurmurHash2, but endian- and alignment-neutral.
1.55 + // Half the speed though, alas.
1.56 +
1.57 + static uint32_t MurmurHashNeutral2 ( const void * key, int32_t len, uint32_t seed )
1.58 + {
1.59 + static const uint32_t m = 0x5bd1e995;
1.60 + static const int32_t r = 24;
1.61 +
1.62 + uint32_t h = seed ^ len;
1.63 +
1.64 + const unsigned char * data = (const unsigned char *)key;
1.65 +
1.66 + while(len >= 4)
1.67 + {
1.68 + uint32_t k;
1.69 +
1.70 + k = data[0];
1.71 + k |= data[1] << 8;
1.72 + k |= data[2] << 16;
1.73 + k |= data[3] << 24;
1.74 +
1.75 + k *= m;
1.76 + k ^= k >> r;
1.77 + k *= m;
1.78 +
1.79 + h *= m;
1.80 + h ^= k;
1.81 +
1.82 + data += 4;
1.83 + len -= 4;
1.84 + }
1.85 +
1.86 + switch(len)
1.87 + {
1.88 + case 3: h ^= data[2] << 16;
1.89 + case 2: h ^= data[1] << 8;
1.90 + case 1: h ^= data[0];
1.91 + h *= m;
1.92 + };
1.93 +
1.94 + h ^= h >> 13;
1.95 + h *= m;
1.96 + h ^= h >> 15;
1.97 +
1.98 + return h;
1.99 + }
1.100 +
1.101 + HashCode Key::computeHash (Blob key) {
1.102 + return MurmurHashNeutral2(key.bytes, key.length, 0);
1.103 + }
1.104 +
1.105 +
1.106 +
1.107 + void MutableDictionary::add (Dictionary* dict) {
1.108 + Iterator *it = dict->iterate();
1.109 + for (; *it; it->next())
1.110 + put(it->key(), it->value());
1.111 + delete it;
1.112 + }
1.113 +
1.114 +
1.115 +
1.116 + const Dictionary& Dictionary::kEmpty = * new HashDictionary();
1.117 +
1.118 +
1.119 +#pragma mark -
1.120 +#pragma mark KEY AND VALUE
1.121 +
1.122 + class KeyAndValue {
1.123 + public:
1.124 + static KeyAndValue* create (Blob key, Blob value) {
1.125 + size_t size = 2*sizeof(uint32_t) + key.length;
1.126 + size = (size + 0x3) & ~0x3; // 32-bit align start of value
1.127 + if (value!=kDeletedValue)
1.128 + size += value.length;
1.129 + KeyAndValue *kv = (KeyAndValue*) ::operator new(size);
1.130 + kv->_keyLength = key.length;
1.131 + memcpy(&kv->_keyLength + 1, key.bytes, key.length);
1.132 + uint32_t *valueLengthPtr = const_cast<uint32_t*>(kv->valueLengthPtr());
1.133 + *valueLengthPtr = value.length;
1.134 + if (value!=kDeletedValue)
1.135 + memcpy(valueLengthPtr + 1, value.bytes, value.length);
1.136 + return kv;
1.137 + }
1.138 + Blob key() const {
1.139 + return Blob(&_keyLength+1, _keyLength);
1.140 + }
1.141 +
1.142 + Blob value() const{
1.143 + const uint32_t *v = this->valueLengthPtr();
1.144 + if (*v != kDeletedValue.length)
1.145 + return Blob(v+1, *v);
1.146 + else
1.147 + return kDeletedValue;
1.148 + }
1.149 +
1.150 + /** Magic value OverlayDictionary stores in me to represent a deleted value. */
1.151 + static const Blob kDeletedValue;
1.152 + private:
1.153 + const uint32_t* valueLengthPtr() const {
1.154 + size_t ptr = (size_t)(&_keyLength + 1) + _keyLength;
1.155 + ptr = (ptr + 0x3) & ~0x3; // 32-bit align
1.156 + return (uint32_t*)ptr;
1.157 + }
1.158 +
1.159 + uint32_t _keyLength;
1.160 + //...there follows the key, valueLength and value...
1.161 + };
1.162 +
1.163 + const Blob KeyAndValue::kDeletedValue(NULL, (size_t)-1);
1.164 +
1.165 +
1.166 +
1.167 +
1.168 +#pragma mark -
1.169 +#pragma mark HASH DICTIONARY:
1.170 +
1.171 + HashDictionary::~HashDictionary() {
1.172 + removeAll();
1.173 + }
1.174 +
1.175 + Blob HashDictionary::_convertValue (void *value) {
1.176 + return value ?((KeyAndValue*)value)->value() :Blob();
1.177 + }
1.178 +
1.179 + bool HashDictionary::contains (Key key) const {
1.180 + Blob value = get(key);
1.181 + return value.bytes || value.length;
1.182 + }
1.183 +
1.184 +
1.185 + void HashDictionary::put (Key key, Blob value) {
1.186 + // Allocate a block to store both the Blob struct and the data
1.187 + KeyAndValue *kv = KeyAndValue::create(key,value);
1.188 + _hash.put(Key(kv->key(),key.hash), kv);
1.189 + }
1.190 +
1.191 + bool HashDictionary::remove (Key key) {
1.192 + KeyAndValue *kv = (KeyAndValue*) _hash.get(key);
1.193 + if (kv) {
1.194 + free(kv);
1.195 + return true;
1.196 + } else
1.197 + return false;
1.198 + }
1.199 +
1.200 + void HashDictionary::removeAll() {
1.201 + for (Hash::Iterator it(&_hash); it; ++it)
1.202 + free(it.value());
1.203 + _hash.removeAll();
1.204 + }
1.205 +
1.206 +
1.207 +
1.208 +
1.209 +#pragma mark -
1.210 +#pragma mark OVERLAY DICTIONARY:
1.211 +
1.212 +
1.213 + OverlayDictionary::OverlayDictionary (const Dictionary *base)
1.214 + :_base(base),
1.215 + _overlay(new HashDictionary()),
1.216 + _count(base->count()),
1.217 + _allRemoved(false)
1.218 + { }
1.219 +
1.220 + OverlayDictionary::~OverlayDictionary() {
1.221 + delete _overlay;
1.222 + }
1.223 +
1.224 + int OverlayDictionary::count() const {
1.225 + return _count;
1.226 + }
1.227 +
1.228 + bool OverlayDictionary::isChanged() const {
1.229 + return _overlay->count() > 0;
1.230 + }
1.231 +
1.232 + Blob OverlayDictionary::get (Key key) const {
1.233 + Blob result = _overlay->get(key);
1.234 + if (!result) {
1.235 + if (result==KeyAndValue::kDeletedValue)
1.236 + result = Blob(); // It's been marked as deleted
1.237 + else if (!_allRemoved)
1.238 + result = _base->get(key);
1.239 + }
1.240 + return result;
1.241 + }
1.242 +
1.243 + bool OverlayDictionary::contains (Key key) const {
1.244 + Blob result = _overlay->get(key);
1.245 + if (result)
1.246 + return true;
1.247 + else if (result==KeyAndValue::kDeletedValue)
1.248 + return false;
1.249 + else if (!_allRemoved)
1.250 + return _base->get(key);
1.251 + else
1.252 + return false;
1.253 + }
1.254 +
1.255 + void OverlayDictionary::put (Key key, Blob value) {
1.256 + assert(value.bytes || value.length==0); // make sure it doesn't look like magic kDeletedValue
1.257 + _overlay->put(key,value);
1.258 + if (_allRemoved || !_base->contains(key))
1.259 + _count++;
1.260 + }
1.261 +
1.262 + bool OverlayDictionary::remove (Key key) {
1.263 + if (!_allRemoved && _base->contains(key)) {
1.264 + _overlay->put(key,KeyAndValue::kDeletedValue);
1.265 + _count--;
1.266 + return true;
1.267 + } else if (_overlay->remove(key)) {
1.268 + _count--;
1.269 + return true;
1.270 + } else
1.271 + return false;
1.272 + }
1.273 +
1.274 + void OverlayDictionary::removeAll() {
1.275 + _allRemoved = true;
1.276 + _count = 0;
1.277 + }
1.278 +
1.279 +
1.280 + void OverlayDictionary::revert() {
1.281 + _overlay->removeAll();
1.282 + _count = _base->count();
1.283 + _allRemoved = false;
1.284 + }
1.285 +
1.286 + void OverlayDictionary::revertTo (const Dictionary* newBase) {
1.287 + _base = newBase;
1.288 + revert();
1.289 + }
1.290 +
1.291 + void OverlayDictionary::rebase (const Dictionary* newBase) {
1.292 + _base = newBase;
1.293 + }
1.294 +
1.295 + OverlayDictionary::Iterator::Iterator (const OverlayDictionary &dict)
1.296 + :_iter(dict.base()->iterate()),
1.297 + _overlay(dict._overlay)
1.298 + {
1.299 + if (skipCurrentState())
1.300 + next();
1.301 + }
1.302 +
1.303 + Key OverlayDictionary::Iterator::key() const {return _iter ?_iter->key() :Key();}
1.304 + Blob OverlayDictionary::Iterator::value() const {return _iter ?_iter->value() :Blob();}
1.305 +
1.306 + bool OverlayDictionary::Iterator::next() {
1.307 + if (_iter) {
1.308 + do {
1.309 + _iter->next();
1.310 + } while (skipCurrentState());
1.311 + }
1.312 + return _iter && *_iter;
1.313 + }
1.314 +
1.315 + bool OverlayDictionary::Iterator::skipCurrentState() {
1.316 + if (_iter) {
1.317 + if (*_iter) {
1.318 + if (_overlay) {
1.319 + if (_overlay->contains(_iter->key()))
1.320 + return true; // Skip overridden value in base dict
1.321 + } else {
1.322 + if (_iter->value() == KeyAndValue::kDeletedValue)
1.323 + return true; // Skip marked-deleted value in overlay dict
1.324 + }
1.325 + } else {
1.326 + delete _iter;
1.327 + if (_overlay) {
1.328 + // end of base iterator; switch to overlay
1.329 + _iter = _overlay->iterate();
1.330 + _overlay = NULL;
1.331 + return skipCurrentState();
1.332 + } else {
1.333 + _iter = NULL;
1.334 + }
1.335 + }
1.336 + }
1.337 + return false;
1.338 + }
1.339 +
1.340 +
1.341 +#pragma mark -
1.342 +#pragma mark CHANGE ITERATOR:
1.343 +
1.344 +
1.345 + Dictionary::ChangeIterator::ChangeIterator (const Dictionary *dict1, const Dictionary *dict2) {
1.346 + _init(dict1, dict2);
1.347 + }
1.348 +
1.349 + Dictionary::ChangeIterator::ChangeIterator (const OverlayDictionary *overlay) {
1.350 + _init(overlay->_overlay, overlay->base());
1.351 + }
1.352 +
1.353 + void Dictionary::ChangeIterator::_init(const Dictionary *dict1, const Dictionary *dict2) {
1.354 + _dict2 = dict2;
1.355 + _iter = dict1->iterate();
1.356 + if (*_iter)
1.357 + _skipMatching();
1.358 + }
1.359 +
1.360 + Dictionary::ChangeIterator::~ChangeIterator() {
1.361 + delete _iter;
1.362 + }
1.363 +
1.364 + bool Dictionary::ChangeIterator::next() {
1.365 + return _iter->next() && this->_skipMatching();
1.366 + }
1.367 +
1.368 + bool Dictionary::ChangeIterator::_skipMatching() {
1.369 + do{
1.370 + _otherValue = _dict2->get(_iter->key());
1.371 + if (!_otherValue.equals(_iter->value()))
1.372 + return true;
1.373 + }while (_iter->next());
1.374 + return false;
1.375 + }
1.376 +
1.377 +
1.378 +
1.379 +}