1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/include/Hash.h	Sun Sep 20 15:14:12 2009 -0700
     1.3 @@ -0,0 +1,119 @@
     1.4 +/*
     1.5 + *  Hash.h
     1.6 + *  Ottoman
     1.7 + *
     1.8 + *  Created by Jens Alfke on 8/20/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_HASH_
    1.14 +#define _MOOSEYARD_HASH_
    1.15 +#include "Base.h"
    1.16 +#include "Dictionary.h"
    1.17 +
    1.18 +namespace Mooseyard {
    1.19 +        
    1.20 +    /** A fairly low-level hash-table class whose keys and values are arbitrary data blobs.
    1.21 +        This class does no memory management of the keys and values: the memory ranges
    1.22 +        pointed to by the key and value parameters to put() must remain valid as long as
    1.23 +        that key or value remains in the hash-table. */
    1.24 +    class Hash {
    1.25 +        
    1.26 +    public:
    1.27 +        typedef void* Value;
    1.28 +        
    1.29 +        /** Creates a new, empty Hash. */
    1.30 +        explicit Hash (int capacity = 50);
    1.31 +        
    1.32 +        ~Hash();
    1.33 +        
    1.34 +        /** Gets the value associated with the given key. */
    1.35 +        Value get(Key) const;
    1.36 +        Value operator[] (Key key) const                        {return get(key);}
    1.37 +        
    1.38 +        /** Returns the number of values in the Hash. */
    1.39 +        int count() const                                       {return _count;}
    1.40 +        
    1.41 +        /** Sets the given value for the given key, replacing any existing value. */
    1.42 +        void put(Key, Value);
    1.43 +        
    1.44 +        /** Removes the value with the given key. */
    1.45 +        bool remove(Key);
    1.46 +        
    1.47 +        /** Removes all values. */
    1.48 +        void removeAll();
    1.49 +        
    1.50 +        void dump() const;
    1.51 +        
    1.52 +        class IndexEntry;
    1.53 +        
    1.54 +        class Iterator {
    1.55 +        public:
    1.56 +            Iterator (const Hash *h);
    1.57 +            Iterator (const Hash &h);
    1.58 +            operator bool() const                           {return hasValue();}
    1.59 +            Value operator*() const                         {return value();}
    1.60 +            Iterator& operator++()                          {next(); return *this;}
    1.61 +            
    1.62 +            Key key() const;
    1.63 +            Value value() const;
    1.64 +            bool hasValue() const                           {return _entry < _end;}
    1.65 +            bool next();
    1.66 +        private:
    1.67 +            Iterator (IndexEntry *start, IndexEntry*end);
    1.68 +            IndexEntry* _entry;
    1.69 +            IndexEntry* const _end;
    1.70 +            UNCOPYABLE(Iterator);
    1.71 +        };
    1.72 +        
    1.73 +    private:
    1.74 +        IndexEntry& _find (Key key) const;
    1.75 +        IndexEntry& _findForPut (const IndexEntry &newEntry);
    1.76 +        void _resize(int newSize);
    1.77 +        void _read();
    1.78 +        UNCOPYABLE(Hash);
    1.79 +        
    1.80 +        int _count;
    1.81 +        int _tableSize;
    1.82 +        IndexEntry *_table;
    1.83 +        
    1.84 +        friend class Iterator;
    1.85 +    };
    1.86 +    
    1.87 +
    1.88 +
    1.89 +    /** A concrete Dictionary implemented with a Hash. */
    1.90 +    class HashDictionary :public MutableDictionary {
    1.91 +    public:
    1.92 +        explicit HashDictionary (int capacity =50)  :_hash(capacity) { }
    1.93 +        virtual ~HashDictionary();
    1.94 +        virtual int count() const                   {return _hash.count();}
    1.95 +        virtual bool contains (Key) const;
    1.96 +        virtual Blob get (Key key) const            {return _convertValue(_hash.get(key));}
    1.97 +        virtual void put (Key, Blob value);
    1.98 +        virtual bool remove (Key);
    1.99 +        virtual void removeAll();
   1.100 +        virtual Iterator* iterate() const           {return new Iterator(*this);}
   1.101 +        
   1.102 +        class Iterator :public Dictionary::Iterator {
   1.103 +        public:
   1.104 +            explicit Iterator (const HashDictionary &d)      :_it(d._hash) { }
   1.105 +            virtual Key key() const                 {return _it.key();}
   1.106 +            virtual Blob value() const              {return _convertValue(_it.value());}
   1.107 +            virtual bool hasValue() const           {return _it.hasValue();}
   1.108 +            virtual bool next()                     {return _it.next();}
   1.109 +        private:
   1.110 +            Hash::Iterator _it;
   1.111 +        };
   1.112 +        
   1.113 +    private:
   1.114 +        static Blob _convertValue (void*);
   1.115 +        Hash _hash;
   1.116 +        friend class Iterator;
   1.117 +    };
   1.118 +    
   1.119 +    
   1.120 +}
   1.121 +
   1.122 +#endif _MOOSEYARD_HASH_