1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/include/Dictionary.h Sun Sep 20 15:14:12 2009 -0700
1.3 @@ -0,0 +1,208 @@
1.4 +/*
1.5 + * Dictionary.h
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 +#ifndef _MOOSEYARD_DICTIONARY_
1.14 +#define _MOOSEYARD_DICTIONARY_
1.15 +#include "Base.h"
1.16 +
1.17 +namespace Mooseyard {
1.18 +
1.19 + typedef uint32_t HashCode;
1.20 +
1.21 + /** A Key is a data blob treated as a dictionary key.
1.22 + It carries its hash-code around with it, to avoid redundant computation. */
1.23 + struct Key :public Blob {
1.24 + HashCode hash;
1.25 +
1.26 + Key () :Blob(), hash(0) { }
1.27 + explicit Key (const Blob &b) :Blob(b), hash(computeHash(b)) { }
1.28 + Key (const Blob &b, HashCode h) :Blob(b), hash(h) { }
1.29 + Key (const char *str) :Blob(str), hash(computeHash(*this)) { }
1.30 + Key (const void *b, uint32_t len, HashCode h) :Blob(b,len), hash(h) { }
1.31 +
1.32 + static HashCode computeHash (Blob);
1.33 + };
1.34 +
1.35 +
1.36 + /** An abstract interface for key/value dictionaries.
1.37 + Dictionary itself is read-only; its subclass MutableDictionary allows changes. */
1.38 + class Dictionary {
1.39 + public:
1.40 + class Iterator;
1.41 + class ChangeIterator;
1.42 +
1.43 + virtual ~Dictionary();
1.44 +
1.45 + /** The number of items in the dictionary. */
1.46 + virtual int count() const =0;
1.47 +
1.48 + /** Returns the value associated with the given key.
1.49 + Keys are compared by exact binary data equality.
1.50 + The data pointed to by the value returned is valid at least until the next call to
1.51 + this Dictionary; some subclasses may guarantee a longer lifetime.
1.52 + If there is no value for the given key, a Blob of {NULL, 0} will be returned. */
1.53 + virtual Blob get (Key) const =0;
1.54 +
1.55 + /** Returns true iff there is a value associated with the given key. */
1.56 + virtual bool contains (Key key) const {return get(key).bytes != NULL;}
1.57 +
1.58 + /** Returns a pointer to a new Iterator object that can be used to iterate this Dictionary.
1.59 + The iterator must be deleted when you're done with it. */
1.60 + virtual Iterator* iterate() const =0;
1.61 +
1.62 + /** A singleton empty Dictionary. */
1.63 + static const Dictionary& kEmpty;
1.64 +
1.65 + // utilities
1.66 + /** Returns a suggested size for a hash table that can hold 'capacity' items without
1.67 + being more than the 'load' fraction full; result is always a power of two. */
1.68 + static int choosePowerOfTwoSize (int capacity, float load = kMaxLoadFactor);
1.69 +
1.70 + static int chooseAnyOldSize (int capacity, float load = kMaxLoadFactor);
1.71 +
1.72 + static const int kMinSize;
1.73 + static const float kMinLoadFactor;
1.74 + static const float kMaxLoadFactor;
1.75 +
1.76 + protected:
1.77 + Dictionary();
1.78 + };
1.79 +
1.80 +
1.81 + /** An abstract interface for mutable key/value dictionaries; extends Dictionary. */
1.82 + class MutableDictionary : public Dictionary {
1.83 + public:
1.84 + /** Stores the given value for the given key, replacing any prior value.
1.85 + The memory for the key and value is copied, so you don't need to preserve it after
1.86 + the call returns. */
1.87 + virtual void put (Key, Blob value) =0;
1.88 +
1.89 + /** Adds the contents of the given Dictionary to this one.
1.90 + Effectively calls this->put() with every key/value pair in the source Dictionary. */
1.91 + virtual void add (Dictionary*);
1.92 +
1.93 + /** Removes the value for the given key, if any.
1.94 + Returns true if the value was removed, false if there was no value. */
1.95 + virtual bool remove (Key) =0;
1.96 +
1.97 + /** Removes all keys and values, returning the dictionary to an empty state. */
1.98 + virtual void removeAll() = 0;
1.99 + };
1.100 +
1.101 +
1.102 + /** Abstract iterator interface. Each Dictionary subclass defines its own.
1.103 + The order in which items are returned is undefined, and in effect quite random, due to
1.104 + the properties of hash tables. */
1.105 + class Dictionary::Iterator {
1.106 + public:
1.107 + virtual ~Iterator();
1.108 +
1.109 + /** The current key the iterator is pointing to. */
1.110 + virtual Key key() const =0;
1.111 + /** The current value the iterator is pointing to. */
1.112 + virtual Blob value() const =0;
1.113 + /** Returns true if the iterator has a current item, or false if it's reached the end. */
1.114 + virtual bool hasValue() const {return key().bytes != 0;}
1.115 + /** Advances the Iterator to the next item. Returns false if it's reached the end.
1.116 + (Note that the order of items is undefined and in practice quite random.) */
1.117 + virtual bool next() =0;
1.118 +
1.119 + operator bool() const {return hasValue();}
1.120 + Iterator& operator++() {next(); return *this;}
1.121 + };
1.122 +
1.123 + class OverlayDictionary;
1.124 +
1.125 +
1.126 + /** An iterator that walks through the differences between two Dictionaries. */
1.127 + class Dictionary::ChangeIterator :public Dictionary::Iterator {
1.128 + public:
1.129 + ChangeIterator (const Dictionary *dict1, const Dictionary *dict2);
1.130 + explicit ChangeIterator (const OverlayDictionary*);
1.131 + virtual ~ChangeIterator();
1.132 +
1.133 + /** Returns the current key, whose values in the two dictionaries differ. */
1.134 + virtual Key key() const {return _iter->key();}
1.135 + /** Returns the corresponding value from dict1.
1.136 + May be empty (NULL,0) if the key does not appear in dict1 (i.e. inserted into dict2.) */
1.137 + virtual Blob value() const {return _iter->value();}
1.138 + /** Returns the corresponding value from dict2.
1.139 + May be empty (NULL,0) if the key does not appear in dict2 (i.e. deleted from dict2.) */
1.140 + virtual Blob otherValue() const {return _otherValue;}
1.141 + virtual bool hasValue() const {return _iter->hasValue();}
1.142 + virtual bool next();
1.143 +
1.144 + private:
1.145 + void _init (const Dictionary *dict1, const Dictionary *dict2);
1.146 + bool _skipMatching();
1.147 + const Dictionary *_dict2;
1.148 + Iterator *_iter;
1.149 + Blob _otherValue;
1.150 + };
1.151 +
1.152 +
1.153 + /** Adapter class that allows a Dictionary to appear to be mutable, by using a separate
1.154 + mutable dictionary to remember the changes. */
1.155 + class OverlayDictionary :public MutableDictionary {
1.156 + public:
1.157 + /** Creates a mutable dictionary that overlays base. Initially its contents will appear
1.158 + identical to base. It can be changed, but the changes will not affect the base. */
1.159 + explicit OverlayDictionary (const Dictionary *base);
1.160 + virtual ~OverlayDictionary();
1.161 +
1.162 + /** The base dictionary this is overlaying. */
1.163 + const Dictionary* base() const {return _base;}
1.164 + /** The dictionary that contains the changes made to the base.
1.165 + Only keys/values that have been changed appear here. */
1.166 + const Dictionary* overlay() const {return _overlay;}
1.167 + /** Returns true if changes have been made. */
1.168 + bool isChanged() const;
1.169 + /** Returns true if the base has been completely replaced by calling removeAll. */
1.170 + bool baseReplaced() const {return _allRemoved;}
1.171 +
1.172 + /** Removes all changes, restoring the overlay to look identical to the base. */
1.173 + void revert();
1.174 + /** Changes the overlay to a new base, clearing all changes. */
1.175 + void revertTo (const Dictionary* newBase);
1.176 +
1.177 + /** Changes the base without clearing changes. */
1.178 + void rebase (const Dictionary* newBase);
1.179 +
1.180 + virtual int count() const;
1.181 + virtual Blob get (Key) const;
1.182 + virtual bool contains (Key) const;
1.183 + virtual void put (Key, Blob value);
1.184 + virtual bool remove (Key);
1.185 + virtual void removeAll();
1.186 + virtual Iterator* iterate() const {return new Iterator(*this);}
1.187 +
1.188 + class Iterator :public Dictionary::Iterator {
1.189 + public:
1.190 + explicit Iterator (const OverlayDictionary&);
1.191 + virtual Key key() const;
1.192 + virtual Blob value() const;
1.193 + virtual bool next();
1.194 + private:
1.195 + bool skipCurrentState();
1.196 + Dictionary::Iterator *_iter;
1.197 + const MutableDictionary *_overlay;
1.198 + };
1.199 +
1.200 + private:
1.201 + const Dictionary *_base;
1.202 + MutableDictionary *_overlay;
1.203 + int _count;
1.204 + bool _allRemoved;
1.205 + friend class ChangeIterator;
1.206 + };
1.207 +
1.208 +
1.209 +}
1.210 +
1.211 +#endif _MOOSEYARD_DICTIONARY_