hashtable.h

Pegasus is an open-source implementationof the DMTF CIM and WBEM standards. It is designed to be por

{

}

template<class K, class V, class E>
_BucketBase* _Bucket<K, V, E>::clone() const
{
    return new _Bucket<K, V, E>(_key, _value);
}

/* Iterator for HashTable class. */
template<class K, class V, class E>
class _HashTableIterator : public _HashTableIteratorBase
{
public:

    _HashTableIterator()
        : _HashTableIteratorBase() { }

    _HashTableIterator(_BucketBase** first, _BucketBase** last)
        : _HashTableIteratorBase(first, last) { }

    const K& key() const { return ((_Bucket<K, V, E>*)_bucket)->getKey(); }

    const V& value() const { return ((_Bucket<K, V, E>*)_bucket)->getValue(); }
};

/** The HashTable class provides a simple hash table implementation which
    associates key-value pairs.

    This implementation minimizes template bloat considerably by factoring out
    most of the code into a common non-template class (see _HashTableRep).
    The HashTable class is mostly a wrapper to add proper type semantics to the
    use of its representation class.

    Hashing as always is O(1).

    HashTable uses the most popular hash table implementation which utilizes
    an array of pointers to bucket chains. This is organized as follows:

        <pre>
           +---+
           |   |   +-----+-------+
         0 | ----->| key | value |
           |   |   +-----+-------+
           +---+
           |   |   +-----+-------+   +-----+-------+   +-----+-------+
         1 | ----->| key | value |-->| key | value |-->| key | value |
           |   |   +-----+-------+   +-----+-------+   +-----+-------+
           +---+
             .
             .
             .
           +---+
           |   |   +-----+-------+   +-----+-------+
        N-1| ----->| key | value |-->| key | value |
           |   |   +-----+-------+   +-----+-------+
           +---+
        </pre>

    To locate an item a hash function is applied to the key to produce an
    integer value. Then the modulo of that integer is taken with N to select
    a chain (as shown above). Then the chain is searched for a bucket whose
    key value is the same as the target key.

    The number of chains default to DEFAULT_NUM_CHAINS but should be about
    one-third the number of expected entries (so that the average chain
    will be three long). Making the number of chains too large will waste
    space causing the hash table to be very sparse. But for optimal efficiency,
    one might set the number of chains to be the same as the expected number
    of entries.

    This implementation does have NOT an adaptive growth algorithm yet which
    would allow it to increase the number of chains periodically based on some
    statistic (e.g., when the number of entries is more than three times the
    number of chains; this would keep the average chain length below three).

    The following example shows how to instantiate a HashTable which associates
    String keys with Uint32 values.

        <pre>
        typedef HashTable&lt;String, Uint32&gt; HT;
        HT ht;
        </pre>

    Some of the template arguments are defaulted in the above example (the
    third and forth). The instantiation is explicitly qualified like this
    (which by the way has exactly the same effect).

        <pre>
        typedef HashTable&lt;String, Uint32,
            EqualFunc&lt;String&gt;, HashFunc&lt;String&gt;&gt; HT;
        </pre>

    The third and fourth arguments are described more in detail later.

    Then, entries may be inserted like this:

        <pre>
        ht.insert("Red", 111);
        ht.insert("Green", 222);
        ht.insert("Blue", 222);
        </pre>

    And entries may be looked up as follows:

        <pre>
        Uint32 value;
        ht.lookup("Red", value);
        </pre>

    And entries may be removed like this:

        <pre>
        h.remove("Red");
        </pre>

    Iteration is done like this:

        <pre>
        for (HT::Iterator i = ht.start(); i; i++)
        {
            // To access the key call i.key()!
            // To access the value call i.value()!
        }
        </pre>

    Note that only forward iteration is supported (no backwards iteration),
    AND that the hashtable MUST NOT be modified during the iteration!!!

    Equality of keys is determined using the EqualFunc class which is
    the default third argument of the template argument list. A new function
    object may be defined and passed to modify the behavior (for example, one
    might define equality of strings to ignore whitespace). Here is how to
    define and use a new equality function object:

        <pre>
        struct MyEqualFunc
        {
            static Boolean equal(const String& x, const String& y)
            {
                // do something here to test for equality!
            }
        };

        ...

        EqualFunc&lt;String, Uint32, MyEqualFunc&gt; ht;
        </pre>

    When the lookup(), insert(), and remove() methods are called, the
    MyEqualFunc::equal() method will be used to determine equality.

    Hash functions are provided for common types (as part of the default
    HashFunc class). For other types it is possible to define a custom function
    object as follows:

        <pre>
        struct MyHashFunc
        {
            static Uint32 hash(const String& x)
            {
                // Do some hashing here!
            }
        };

        ...

        EqualFunc&lt;String, Uint32, MyEqualFunc, MyHashFunc&gt; ht;
        </pre>

    As always, the hash function should provide a reasonably uniform
    distrubtion so that all of the entries don't get crowded into a few
    chains. Note that a hash function which returns zero, would force
    the pathalogical case in which all entries are placed in the first
    chain.
*/
template<class K, class V, class E , class H >
class HashTable
{
public:

    typedef _HashTableIterator<K, V, E> Iterator;

    /* By default, we create this many chains initially */
    enum { DEFAULT_NUM_CHAINS = 32 };

    /** Constructor.
        @param numChains number of chains to create.
    */
    HashTable(Uint32 numChains = DEFAULT_NUM_CHAINS) : _rep(numChains)
    {

    }

    /** Copy constructor. */
    HashTable(const HashTable<K,V,E,H>& x) : _rep(x._rep)
    {

    }

    /** Assignment operator. */
    HashTable<K,V,E,H>& operator=(const HashTable<K,V,E,H>& x)
    {
        if (this != &x)
            _rep = x._rep;
        return *this;
    }

    /** Returns the size of this hash table (the number of entries). */
    Uint32 size() const { return _rep.size(); }

    /** Clears the contents of this hash table. After this is called, the
        size() method returns zero.
    */
    void clear() { _rep.clear(); }

    /** Inserts new key-value pair into hash table.
        @param key key component.
        @param value value component.
        @return true on success; false if duplicate key.
    */
    Boolean insert(const K& key, const V& value)
    {
        return _rep.insert(
            H::hash(key), new _Bucket<K, V, E>(key, value), &key);
    }

    /** Checks to see if hash table contains an entry with the given key.
        @param key key to be searched for
        @return true if hash table contains an entry with the given key.
    */
    Boolean contains(const K& key) const
    {
        V value;
        return lookup(key, value);
    }

    /** Looks up the entry with the given key.
        @param key key of entry to be located.
        @param value output value.
        @return true if found; false otherwise.
    */
    Boolean lookup(const K& key, V& value) const;

    /** Removes the entry with the given key.
        @param key key of entry to be removed.
        @return true on success; false otherwise.
    */
    Boolean remove(const K& key)
    {
        return _rep.remove(H::hash(key), &key);
    }

    /** Obtains an iterator for this object. */
    Iterator start() const
    {
        return Iterator(
            _rep.getChains(), _rep.getChains() + _rep.getNumChains());
    }

private:

    _HashTableRep _rep;
};

template<class K, class V, class E, class H>
inline Boolean HashTable<K, V, E, H>::lookup(const K& key, V& value) const
{
    _Bucket<K, V, E>* bucket
        = (_Bucket<K, V, E>*)_rep.lookup(H::hash(key), &key);

    if (bucket)
    {
        value = bucket->getValue();
        return true;
    }

    return false;
}

PEGASUS_NAMESPACE_END

#endif /* Pegasus_HashTable_h */