jens@0: /* jens@0: * Dictionary.h 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: #ifndef _MOOSEYARD_DICTIONARY_ jens@0: #define _MOOSEYARD_DICTIONARY_ jens@0: #include "Base.h" jens@0: jens@0: namespace Mooseyard { jens@0: jens@0: typedef uint32_t HashCode; jens@0: jens@0: /** A Key is a data blob treated as a dictionary key. jens@0: It carries its hash-code around with it, to avoid redundant computation. */ jens@0: struct Key :public Blob { jens@0: HashCode hash; jens@0: jens@0: Key () :Blob(), hash(0) { } jens@0: explicit Key (const Blob &b) :Blob(b), hash(computeHash(b)) { } jens@0: Key (const Blob &b, HashCode h) :Blob(b), hash(h) { } jens@0: Key (const char *str) :Blob(str), hash(computeHash(*this)) { } jens@0: Key (const void *b, uint32_t len, HashCode h) :Blob(b,len), hash(h) { } jens@0: jens@0: static HashCode computeHash (Blob); jens@0: }; jens@0: jens@0: jens@0: /** An abstract interface for key/value dictionaries. jens@0: Dictionary itself is read-only; its subclass MutableDictionary allows changes. */ jens@0: class Dictionary { jens@0: public: jens@0: class Iterator; jens@0: class ChangeIterator; jens@0: jens@0: virtual ~Dictionary(); jens@0: jens@0: /** The number of items in the dictionary. */ jens@0: virtual int count() const =0; jens@0: jens@0: /** Returns the value associated with the given key. jens@0: Keys are compared by exact binary data equality. jens@0: The data pointed to by the value returned is valid at least until the next call to jens@0: this Dictionary; some subclasses may guarantee a longer lifetime. jens@0: If there is no value for the given key, a Blob of {NULL, 0} will be returned. */ jens@0: virtual Blob get (Key) const =0; jens@0: jens@0: /** Returns true iff there is a value associated with the given key. */ jens@0: virtual bool contains (Key key) const {return get(key).bytes != NULL;} jens@0: jens@0: /** Returns a pointer to a new Iterator object that can be used to iterate this Dictionary. jens@0: The iterator must be deleted when you're done with it. */ jens@0: virtual Iterator* iterate() const =0; jens@0: jens@0: /** A singleton empty Dictionary. */ jens@0: static const Dictionary& kEmpty; jens@0: jens@0: // utilities jens@0: /** Returns a suggested size for a hash table that can hold 'capacity' items without jens@0: being more than the 'load' fraction full; result is always a power of two. */ jens@0: static int choosePowerOfTwoSize (int capacity, float load = kMaxLoadFactor); jens@0: jens@0: static int chooseAnyOldSize (int capacity, float load = kMaxLoadFactor); jens@0: jens@0: static const int kMinSize; jens@0: static const float kMinLoadFactor; jens@0: static const float kMaxLoadFactor; jens@0: jens@0: protected: jens@0: Dictionary(); jens@0: }; jens@0: jens@0: jens@0: /** An abstract interface for mutable key/value dictionaries; extends Dictionary. */ jens@0: class MutableDictionary : public Dictionary { jens@0: public: jens@0: /** Stores the given value for the given key, replacing any prior value. jens@0: The memory for the key and value is copied, so you don't need to preserve it after jens@0: the call returns. */ jens@0: virtual void put (Key, Blob value) =0; jens@0: jens@0: /** Adds the contents of the given Dictionary to this one. jens@0: Effectively calls this->put() with every key/value pair in the source Dictionary. */ jens@0: virtual void add (Dictionary*); jens@0: jens@0: /** Removes the value for the given key, if any. jens@0: Returns true if the value was removed, false if there was no value. */ jens@0: virtual bool remove (Key) =0; jens@0: jens@0: /** Removes all keys and values, returning the dictionary to an empty state. */ jens@0: virtual void removeAll() = 0; jens@0: }; jens@0: jens@0: jens@0: /** Abstract iterator interface. Each Dictionary subclass defines its own. jens@0: The order in which items are returned is undefined, and in effect quite random, due to jens@0: the properties of hash tables. */ jens@0: class Dictionary::Iterator { jens@0: public: jens@0: virtual ~Iterator(); jens@0: jens@0: /** The current key the iterator is pointing to. */ jens@0: virtual Key key() const =0; jens@0: /** The current value the iterator is pointing to. */ jens@0: virtual Blob value() const =0; jens@0: /** Returns true if the iterator has a current item, or false if it's reached the end. */ jens@0: virtual bool hasValue() const {return key().bytes != 0;} jens@0: /** Advances the Iterator to the next item. Returns false if it's reached the end. jens@0: (Note that the order of items is undefined and in practice quite random.) */ jens@0: virtual bool next() =0; jens@0: jens@0: operator bool() const {return hasValue();} jens@0: Iterator& operator++() {next(); return *this;} jens@0: }; jens@0: jens@0: class OverlayDictionary; jens@0: jens@0: jens@0: /** An iterator that walks through the differences between two Dictionaries. */ jens@0: class Dictionary::ChangeIterator :public Dictionary::Iterator { jens@0: public: jens@0: ChangeIterator (const Dictionary *dict1, const Dictionary *dict2); jens@0: explicit ChangeIterator (const OverlayDictionary*); jens@0: virtual ~ChangeIterator(); jens@0: jens@0: /** Returns the current key, whose values in the two dictionaries differ. */ jens@0: virtual Key key() const {return _iter->key();} jens@0: /** Returns the corresponding value from dict1. jens@0: May be empty (NULL,0) if the key does not appear in dict1 (i.e. inserted into dict2.) */ jens@0: virtual Blob value() const {return _iter->value();} jens@0: /** Returns the corresponding value from dict2. jens@0: May be empty (NULL,0) if the key does not appear in dict2 (i.e. deleted from dict2.) */ jens@0: virtual Blob otherValue() const {return _otherValue;} jens@0: virtual bool hasValue() const {return _iter->hasValue();} jens@0: virtual bool next(); jens@0: jens@0: private: jens@0: void _init (const Dictionary *dict1, const Dictionary *dict2); jens@0: bool _skipMatching(); jens@0: const Dictionary *_dict2; jens@0: Iterator *_iter; jens@0: Blob _otherValue; jens@0: }; jens@0: jens@0: jens@0: /** Adapter class that allows a Dictionary to appear to be mutable, by using a separate jens@0: mutable dictionary to remember the changes. */ jens@0: class OverlayDictionary :public MutableDictionary { jens@0: public: jens@0: /** Creates a mutable dictionary that overlays base. Initially its contents will appear jens@0: identical to base. It can be changed, but the changes will not affect the base. */ jens@0: explicit OverlayDictionary (const Dictionary *base); jens@0: virtual ~OverlayDictionary(); jens@0: jens@0: /** The base dictionary this is overlaying. */ jens@0: const Dictionary* base() const {return _base;} jens@0: /** The dictionary that contains the changes made to the base. jens@0: Only keys/values that have been changed appear here. */ jens@0: const Dictionary* overlay() const {return _overlay;} jens@0: /** Returns true if changes have been made. */ jens@0: bool isChanged() const; jens@0: /** Returns true if the base has been completely replaced by calling removeAll. */ jens@0: bool baseReplaced() const {return _allRemoved;} jens@0: jens@0: /** Removes all changes, restoring the overlay to look identical to the base. */ jens@0: void revert(); jens@0: /** Changes the overlay to a new base, clearing all changes. */ jens@0: void revertTo (const Dictionary* newBase); jens@0: jens@0: /** Changes the base without clearing changes. */ jens@0: void rebase (const Dictionary* newBase); jens@0: jens@0: virtual int count() const; jens@0: virtual Blob get (Key) const; jens@0: virtual bool contains (Key) const; jens@0: virtual void put (Key, Blob value); jens@0: virtual bool remove (Key); jens@0: virtual void removeAll(); jens@0: virtual Iterator* iterate() const {return new Iterator(*this);} jens@0: jens@0: class Iterator :public Dictionary::Iterator { jens@0: public: jens@0: explicit Iterator (const OverlayDictionary&); jens@0: virtual Key key() const; jens@0: virtual Blob value() const; jens@0: virtual bool next(); jens@0: private: jens@0: bool skipCurrentState(); jens@0: Dictionary::Iterator *_iter; jens@0: const MutableDictionary *_overlay; jens@0: }; jens@0: jens@0: private: jens@0: const Dictionary *_base; jens@0: MutableDictionary *_overlay; jens@0: int _count; jens@0: bool _allRemoved; jens@0: friend class ChangeIterator; jens@0: }; jens@0: jens@0: jens@0: } jens@0: jens@0: #endif _MOOSEYARD_DICTIONARY_