Return to HashTable.h CVS log

Up to [Pegasus] / pegasus / src / Pegasus / Common

More hash table implementation.

//%/////////////////////////////////////////////////////////////////////////////
//
// Copyright (c) 2000 The Open Group, BMC Software, Tivoli Systems, IBM
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software"),
// to deal in the Software without restriction, including without limitation
// the rights to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.
//
//==============================================================================
//
// Author: Mike Brasher (mbrasher@bmc.com)
//
// Modified By:
//
//%/////////////////////////////////////////////////////////////////////////////

#ifndef Pegasus_HashTable_h
#define Pegasus_HashTable_h

#include <Pegasus/Common/Config.h>
#include <Pegasus/Common/String.h>

PEGASUS_NAMESPACE_BEGIN

PEGASUS_COMMON_LINKAGE Uint32 Hash(const String& str);

inline Uint32 Hash(Uint32 x) { return x + 13; }

/** Representation for a bucket. The HashTable class derives from this
    bucket to append a key and value. This base class just defines
    the pointer to the next bucket in the chain.
*/
class PEGASUS_COMMON_LINKAGE _BucketBase
{
public:

    /** Default constructor. */
    _BucketBase() : next(0) { }

    /** Virtual destructor to ensure destruction of derived class 
	elements.
    */
    virtual ~_BucketBase();

    /** returns true if the key pointed to by the key argument is equal
	to the internal key of this bucket. This method must be overridden
	by the derived class.
    */
    virtual Boolean equal(const void* key) const = 0;

    /** Clone this bucket. */
    virtual _BucketBase* clone() const = 0;

    _BucketBase* next;
};

class _HashTableBase;

/** This class implements a simple hash table forward iterator. */
class PEGASUS_COMMON_LINKAGE _HashTableIteratorBase
{
public:
    
    _HashTableIteratorBase() : _first(0), _last(0), _bucket(0) { }

    operator Boolean() const { return _bucket != 0; }

    _HashTableIteratorBase operator++(int);

    _HashTableIteratorBase& operator++();

    _HashTableIteratorBase(_BucketBase** first, _BucketBase** last);

protected:

    _BucketBase** _first;
    _BucketBase** _last;
    _BucketBase* _bucket;
    friend _HashTableBase;
};

/** The _HashTableBase class is the base class which HashTable derives from. 

    This code is primarily an internal class used to implement the HashTable.
    But there may be occasions to use it directly.

    _HashTableBase parcels out much of the large code so that that code is not 
    instantiated by the HashTable template class many times. This scheme helps 
    reduce code bloat caused by templates. The HashTable template class below
    acts as kind of a wrapper around this class.

    _HashTableBase is implemented as an array of pointers to chains of hash
    buckets. The table initially allocates some number of chains (which can
    be controlled by the constructor) and then may increase the number of
    chains later (resulting in a reorganization of the hash table).

    ATTN: reorganization not supported yet.
*/
class PEGASUS_COMMON_LINKAGE _HashTableBase
{
public:

    /** This constructor allocates an array of pointers to chains of buckets,
	which of course are all empty at this time. The numChains argument
	If the numChains argument is less than eight, then eight chains will
	be created.
	@param numChains - specifies the initial number of chains.
    */
    _HashTableBase(Uint32 numChains);

    /** Copy constructor. */
    _HashTableBase(const _HashTableBase& x);

    /** Destructor. */
    ~_HashTableBase();

    /** Assignment operator. */
    _HashTableBase& operator=(const _HashTableBase& x);

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

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

    /** Inserts new key-value pair into hash table. Deletes the bucket on
	failure so caller need not.
	@param hashCode - hash code generated by caller's hash function.
	@param bucket - bucket to be inserted.
	@param key - pointer to key.
	@return true if insertion successful; false if duplicate key.
    */
    Boolean insert(Uint32 hashCode, _BucketBase* bucket, const void* key);

    /** Finds the bucket with the given key. This method uses the
	_BucketBase::equal() method to compare keys.
	@param hashCode - hash code generated by caller's hash function.
	@param key - void pointer to key.
	@return pointer to bucket with that key or zero otherwise.
    */
    const _BucketBase* lookup(Uint32 hashCode, const void* key);

    /** Removes the bucket with the given key. This method uses the
	_BucketBase::equal() method to compare keys.
	@param hashCode - hash code generated by caller's hash function.
	@param key - void pointer to key.
	@return true if entry found and removed and false otherwise.
    */
    Boolean remove(Uint32 hashCode, const void* key);

protected:

    Uint32 _size;
    Uint32 _numChains;
    _BucketBase** _chains;
};

/** The _Bucket class is used to implement the HashTable class.
*/
template<class K, class V>
class _Bucket : public _BucketBase
{
public:

    _Bucket(const K& key, const V& value) : _key(key), _value(value) { }

    virtual ~_Bucket();

    virtual Boolean equal(const void* key) const;

    virtual _BucketBase* clone() const;

    K& getKey() { return _key; }

    V& getValue() { return _value; }

private:

    K _key;
    V _value;
};

template<class K, class V>
Boolean _Bucket<K,V>::equal(const void* key) const
{
    return *((K*)key) == _key;
}

template<class K, class V>
_Bucket<K,V>::~_Bucket()
{

}

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

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

    _HashTableIterator() 
	: _HashTableIteratorBase() { }

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

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

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

/** HashTable provides a simple hash table implementation which associates
    key-value pairs.
*/
template<class K, class V>
class HashTable : public _HashTableBase
{
public:

    typedef _HashTableIterator<K,V> 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) 
	: _HashTableBase(numChains)
    {
    }

    /** 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 _HashTableBase::insert(
	    Hash(key), new _Bucket<K,V>(key, value), &key);
    }

    /** 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);

    /** 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 _HashTableBase::remove(Hash(key), &key);
    }

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

template<class K, class V>
inline Boolean HashTable<K,V>::lookup(const K& key, V& value)
{
    _Bucket<K,V>* bucket 
	= (_Bucket<K,V>*)_HashTableBase::lookup(Hash(key), &key);

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

    return false;
}

PEGASUS_NAMESPACE_END

#endif /* Pegasus_HashTable_h */