hashtable.h

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

//%2006////////////////////////////////////////////////////////////////////////
//
// Copyright (c) 2000, 2001, 2002 BMC Software; Hewlett-Packard Development
// Company, L.P.; IBM Corp.; The Open Group; Tivoli Systems.
// Copyright (c) 2003 BMC Software; Hewlett-Packard Development Company, L.P.;
// IBM Corp.; EMC Corporation, The Open Group.
// Copyright (c) 2004 BMC Software; Hewlett-Packard Development Company, L.P.;
// IBM Corp.; EMC Corporation; VERITAS Software Corporation; The Open Group.
// Copyright (c) 2005 Hewlett-Packard Development Company, L.P.; IBM Corp.;
// EMC Corporation; VERITAS Software Corporation; The Open Group.
// Copyright (c) 2006 Hewlett-Packard Development Company, L.P.; IBM Corp.;
// EMC Corporation; Symantec Corporation; The Open Group.
//
// 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 ABOVE COPYRIGHT NOTICE AND THIS PERMISSION NOTICE SHALL BE INCLUDED IN
// ALL COPIES OR SUBSTANTIAL PORTIONS OF THE SOFTWARE. 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.
//
//==============================================================================
//
//%/////////////////////////////////////////////////////////////////////////////

#ifndef Pegasus_HashTable_h
#define Pegasus_HashTable_h

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

PEGASUS_NAMESPACE_BEGIN

/*  This is the default hash function object used by the HashTable template.
    Specializations are provided for common types.
*/
template<class K>
struct HashFunc
{
};

PEGASUS_TEMPLATE_SPECIALIZATION struct PEGASUS_COMMON_LINKAGE HashFunc<String>
{
    static Uint32 hash(const String& str);
};

PEGASUS_TEMPLATE_SPECIALIZATION struct HashFunc<Uint32>
{
    static Uint32 hash(Uint32 x) { return x + 13; }
};

PEGASUS_TEMPLATE_SPECIALIZATION struct HashFunc <CIMObjectPath>
{
    static Uint32 hash (const CIMObjectPath & path)
    {
        return path.makeHashCode ();
    }
};

//
// Computes a hash code for a string without regard to case. For example, it
// yields the same hash code for "AB", "ab", "Ab", and "aB".
//
struct PEGASUS_COMMON_LINKAGE HashLowerCaseFunc
{
    static Uint32 hash(const String& str);
};

/*  This is a function object used by the HashTable to compare keys. This is
    the default implementation. Others may be defined and passed in the
    template argument list to perform other kinds of comparisons.
*/
template<class K>
struct EqualFunc
{
    static Boolean equal(const K& x, const K& y)
    {
        return x == y;
    }
};

PEGASUS_TEMPLATE_SPECIALIZATION struct EqualFunc <CIMObjectPath>
{
    static Boolean equal (const CIMObjectPath & x, const CIMObjectPath & y)
    {
        return x.identical (y);
    }
};

/*
    Equal function object that can be used by HashTable to compare keys that
    should be treated as case insensitive.

    This function can be used for hash table keys constructed from strings that
    should be treated as case insensitive (e.g. class names, namespace names,
    system names).

    Note: this function compares Strings based on the process locale.
*/
struct EqualNoCaseFunc
{
    static Boolean equal (const String & x, const String & y)
    {
        return (0 == String::compareNoCase (x, y));
    }
};

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

/* This class implements a simple hash table forward iterator. */
class PEGASUS_COMMON_LINKAGE _HashTableIteratorBase
{
public:

    _HashTableIteratorBase() : _first(0), _last(0), _bucket(0) { }

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

    _HashTableIteratorBase operator++(int);

    _HashTableIteratorBase& operator++();

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

protected:

    _BucketBase** _first;
    _BucketBase** _last;
    _BucketBase* _bucket;
    friend class _HashTableRep;
};

// ATTN: reorganization not supported yet.

/*- The _HashTableRep class is the representation class used by HashTable.

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

    _HashTableRep 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.

    _HashTableRep 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).
*/
class PEGASUS_COMMON_LINKAGE _HashTableRep
{
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.
    */
    _HashTableRep(Uint32 numChains);

    /*- Copy constructor. */
    _HashTableRep(const _HashTableRep& x);

    /*- Destructor. */
    ~_HashTableRep();

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

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

    /*- Clears the contents of this hash table. After this is called, the
        size() 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) const;

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

    _BucketBase** getChains() const { return _chains; }

    Uint32 getNumChains() const { return _numChains; }

protected:

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

/* The _Bucket class is used to implement the HashTable class.
*/
template<class K, class V, class E>
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, class E>
Boolean _Bucket<K, V, E>::equal(const void* key) const
{
    return E::equal(*((K*)key), _key);
}

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