5 * Created by Jens Alfke on 8/23/09.
6 * Copyright 2009 Jens Alfke. All rights reserved.
7 * BSD-Licensed: See the file "LICENSE.txt" for details.
10 #ifndef _MOOSEYARD_DICTIONARY_
11 #define _MOOSEYARD_DICTIONARY_
16 typedef uint32_t HashCode;
18 /** A Key is a data blob treated as a dictionary key.
19 It carries its hash-code around with it, to avoid redundant computation. */
20 struct Key :public Blob {
23 Key () :Blob(), hash(0) { }
24 explicit Key (const Blob &b) :Blob(b), hash(computeHash(b)) { }
25 Key (const Blob &b, HashCode h) :Blob(b), hash(h) { }
26 Key (const char *str) :Blob(str), hash(computeHash(*this)) { }
27 Key (const void *b, uint32_t len, HashCode h) :Blob(b,len), hash(h) { }
29 static HashCode computeHash (Blob);
33 /** An abstract interface for key/value dictionaries.
34 Dictionary itself is read-only; its subclass MutableDictionary allows changes. */
40 virtual ~Dictionary();
42 /** The number of items in the dictionary. */
43 virtual int count() const =0;
45 /** Returns the value associated with the given key.
46 Keys are compared by exact binary data equality.
47 The data pointed to by the value returned is valid at least until the next call to
48 this Dictionary; some subclasses may guarantee a longer lifetime.
49 If there is no value for the given key, a Blob of {NULL, 0} will be returned. */
50 virtual Blob get (Key) const =0;
52 /** Returns true iff there is a value associated with the given key. */
53 virtual bool contains (Key key) const {return get(key).bytes != NULL;}
55 /** Returns a pointer to a new Iterator object that can be used to iterate this Dictionary.
56 The iterator must be deleted when you're done with it. */
57 virtual Iterator* iterate() const =0;
59 /** A singleton empty Dictionary. */
60 static const Dictionary& kEmpty;
63 /** Returns a suggested size for a hash table that can hold 'capacity' items without
64 being more than the 'load' fraction full; result is always a power of two. */
65 static int choosePowerOfTwoSize (int capacity, float load = kMaxLoadFactor);
67 static int chooseAnyOldSize (int capacity, float load = kMaxLoadFactor);
69 static const int kMinSize;
70 static const float kMinLoadFactor;
71 static const float kMaxLoadFactor;
78 /** An abstract interface for mutable key/value dictionaries; extends Dictionary. */
79 class MutableDictionary : public Dictionary {
81 /** Stores the given value for the given key, replacing any prior value.
82 The memory for the key and value is copied, so you don't need to preserve it after
84 virtual void put (Key, Blob value) =0;
86 /** Adds the contents of the given Dictionary to this one.
87 Effectively calls this->put() with every key/value pair in the source Dictionary. */
88 virtual void add (Dictionary*);
90 /** Removes the value for the given key, if any.
91 Returns true if the value was removed, false if there was no value. */
92 virtual bool remove (Key) =0;
94 /** Removes all keys and values, returning the dictionary to an empty state. */
95 virtual void removeAll() = 0;
99 /** Abstract iterator interface. Each Dictionary subclass defines its own.
100 The order in which items are returned is undefined, and in effect quite random, due to
101 the properties of hash tables. */
102 class Dictionary::Iterator {
106 /** The current key the iterator is pointing to. */
107 virtual Key key() const =0;
108 /** The current value the iterator is pointing to. */
109 virtual Blob value() const =0;
110 /** Returns true if the iterator has a current item, or false if it's reached the end. */
111 virtual bool hasValue() const {return key().bytes != 0;}
112 /** Advances the Iterator to the next item. Returns false if it's reached the end.
113 (Note that the order of items is undefined and in practice quite random.) */
114 virtual bool next() =0;
116 operator bool() const {return hasValue();}
117 Iterator& operator++() {next(); return *this;}
120 class OverlayDictionary;
123 /** An iterator that walks through the differences between two Dictionaries. */
124 class Dictionary::ChangeIterator :public Dictionary::Iterator {
126 ChangeIterator (const Dictionary *dict1, const Dictionary *dict2);
127 explicit ChangeIterator (const OverlayDictionary*);
128 virtual ~ChangeIterator();
130 /** Returns the current key, whose values in the two dictionaries differ. */
131 virtual Key key() const {return _iter->key();}
132 /** Returns the corresponding value from dict1.
133 May be empty (NULL,0) if the key does not appear in dict1 (i.e. inserted into dict2.) */
134 virtual Blob value() const {return _iter->value();}
135 /** Returns the corresponding value from dict2.
136 May be empty (NULL,0) if the key does not appear in dict2 (i.e. deleted from dict2.) */
137 virtual Blob otherValue() const {return _otherValue;}
138 virtual bool hasValue() const {return _iter->hasValue();}
142 void _init (const Dictionary *dict1, const Dictionary *dict2);
143 bool _skipMatching();
144 const Dictionary *_dict2;
150 /** Adapter class that allows a Dictionary to appear to be mutable, by using a separate
151 mutable dictionary to remember the changes. */
152 class OverlayDictionary :public MutableDictionary {
154 /** Creates a mutable dictionary that overlays base. Initially its contents will appear
155 identical to base. It can be changed, but the changes will not affect the base. */
156 explicit OverlayDictionary (const Dictionary *base);
157 virtual ~OverlayDictionary();
159 /** The base dictionary this is overlaying. */
160 const Dictionary* base() const {return _base;}
161 /** The dictionary that contains the changes made to the base.
162 Only keys/values that have been changed appear here. */
163 const Dictionary* overlay() const {return _overlay;}
164 /** Returns true if changes have been made. */
165 bool isChanged() const;
166 /** Returns true if the base has been completely replaced by calling removeAll. */
167 bool baseReplaced() const {return _allRemoved;}
169 /** Removes all changes, restoring the overlay to look identical to the base. */
171 /** Changes the overlay to a new base, clearing all changes. */
172 void revertTo (const Dictionary* newBase);
174 /** Changes the base without clearing changes. */
175 void rebase (const Dictionary* newBase);
177 virtual int count() const;
178 virtual Blob get (Key) const;
179 virtual bool contains (Key) const;
180 virtual void put (Key, Blob value);
181 virtual bool remove (Key);
182 virtual void removeAll();
183 virtual Iterator* iterate() const {return new Iterator(*this);}
185 class Iterator :public Dictionary::Iterator {
187 explicit Iterator (const OverlayDictionary&);
188 virtual Key key() const;
189 virtual Blob value() const;
192 bool skipCurrentState();
193 Dictionary::Iterator *_iter;
194 const MutableDictionary *_overlay;
198 const Dictionary *_base;
199 MutableDictionary *_overlay;
202 friend class ChangeIterator;
208 #endif _MOOSEYARD_DICTIONARY_