jens@0: /*
jens@0:  *  Hash.h
jens@0:  *  Ottoman
jens@0:  *
jens@0:  *  Created by Jens Alfke on 8/20/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_HASH_
jens@0: #define _MOOSEYARD_HASH_
jens@0: #include "Base.h"
jens@0: #include "Dictionary.h"
jens@0: 
jens@0: namespace Mooseyard {
jens@0:         
jens@0:     /** A fairly low-level hash-table class whose keys and values are arbitrary data blobs.
jens@0:         This class does no memory management of the keys and values: the memory ranges
jens@0:         pointed to by the key and value parameters to put() must remain valid as long as
jens@0:         that key or value remains in the hash-table. */
jens@0:     class Hash {
jens@0:         
jens@0:     public:
jens@0:         typedef void* Value;
jens@0:         
jens@0:         /** Creates a new, empty Hash. */
jens@0:         explicit Hash (int capacity = 50);
jens@0:         
jens@0:         ~Hash();
jens@0:         
jens@0:         /** Gets the value associated with the given key. */
jens@0:         Value get(Key) const;
jens@0:         Value operator[] (Key key) const                        {return get(key);}
jens@0:         
jens@0:         /** Returns the number of values in the Hash. */
jens@0:         int count() const                                       {return _count;}
jens@0:         
jens@0:         /** Sets the given value for the given key, replacing any existing value. */
jens@0:         void put(Key, Value);
jens@0:         
jens@0:         /** Removes the value with the given key. */
jens@0:         bool remove(Key);
jens@0:         
jens@0:         /** Removes all values. */
jens@0:         void removeAll();
jens@0:         
jens@0:         void dump() const;
jens@0:         
jens@0:         class IndexEntry;
jens@0:         
jens@0:         class Iterator {
jens@0:         public:
jens@0:             Iterator (const Hash *h);
jens@0:             Iterator (const Hash &h);
jens@0:             operator bool() const                           {return hasValue();}
jens@0:             Value operator*() const                         {return value();}
jens@0:             Iterator& operator++()                          {next(); return *this;}
jens@0:             
jens@0:             Key key() const;
jens@0:             Value value() const;
jens@0:             bool hasValue() const                           {return _entry < _end;}
jens@0:             bool next();
jens@0:         private:
jens@0:             Iterator (IndexEntry *start, IndexEntry*end);
jens@0:             IndexEntry* _entry;
jens@0:             IndexEntry* const _end;
jens@0:             UNCOPYABLE(Iterator);
jens@0:         };
jens@0:         
jens@0:     private:
jens@0:         IndexEntry& _find (Key key) const;
jens@0:         IndexEntry& _findForPut (const IndexEntry &newEntry);
jens@0:         void _resize(int newSize);
jens@0:         void _read();
jens@0:         UNCOPYABLE(Hash);
jens@0:         
jens@0:         int _count;
jens@0:         int _tableSize;
jens@0:         IndexEntry *_table;
jens@0:         
jens@0:         friend class Iterator;
jens@0:     };
jens@0:     
jens@0: 
jens@0: 
jens@0:     /** A concrete Dictionary implemented with a Hash. */
jens@0:     class HashDictionary :public MutableDictionary {
jens@0:     public:
jens@0:         explicit HashDictionary (int capacity =50)  :_hash(capacity) { }
jens@0:         virtual ~HashDictionary();
jens@0:         virtual int count() const                   {return _hash.count();}
jens@0:         virtual bool contains (Key) const;
jens@0:         virtual Blob get (Key key) const            {return _convertValue(_hash.get(key));}
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 HashDictionary &d)      :_it(d._hash) { }
jens@0:             virtual Key key() const                 {return _it.key();}
jens@0:             virtual Blob value() const              {return _convertValue(_it.value());}
jens@0:             virtual bool hasValue() const           {return _it.hasValue();}
jens@0:             virtual bool next()                     {return _it.next();}
jens@0:         private:
jens@0:             Hash::Iterator _it;
jens@0:         };
jens@0:         
jens@0:     private:
jens@0:         static Blob _convertValue (void*);
jens@0:         Hash _hash;
jens@0:         friend class Iterator;
jens@0:     };
jens@0:     
jens@0:     
jens@0: }
jens@0: 
jens@0: #endif _MOOSEYARD_HASH_