oaHashSet.h

Go to the documentation of this file.

// *****************************************************************************
// *****************************************************************************
// oaHashSet.h
//
// This file contains the definitions of the oaHashSet class. This class
// implements a hash set, optimized according to the size of the key type. If
// the key is no larger than an oaUInt4, then the oaHashSet stores the keys
// directly in an underlying oaHashTbl. If the key is larger than this, then
// the keys are stored in a separate array and indices into that array are
// stored in the underlying oaHashTbl. (This saves the space that would
// otherwise be consumed by a lot of empty key slots.)
//
//  oaHashSet
//      This class implements a base class that can be used for all types of
//      hash sets. It is used by deriving from it for a particular key type
//      and then overriding the virtual functions hash() and compare() for
//      that particular key type.
//
//  oaHashSetIter
//      This class implements an iterator over all objects in a hash set.
//
// The following classes are private implementation classes used by the public
// classes described above.
//
//  oaHashSetTbl
//      This class implements a hash table that stores indices into a separate
//      array of keys that is stored in a separate, owning class.
//
//  oaKeySizedHashSet
//      This class implements the hash set, with two separate templatized
//      implementations based on whether they is is larger than an oaUInt4.
//
// *****************************************************************************
// Except as specified in the OpenAccess terms of use of Cadence or Silicon
// Integration Initiative, this material may not be copied, modified,
// re-published, uploaded, executed, or distributed in any way, in any medium,
// in whole or in part, without prior written permission from Cadence.
//
//                Copyright 2002-2005 Cadence Design Systems, Inc.
//                           All Rights Reserved.
//
//  $Author: icftcm $
//  $Revision: #1 $
//  $Date: 2010/08/09 $
//  $State: Exp $
// *****************************************************************************
// *****************************************************************************



#if !defined(oaHashSet_P)
#define oaHashSet_P



// *****************************************************************************
// Nested includes
// *****************************************************************************
#include "oaArray.h"
#include "oaHashTbl.h"



// *****************************************************************************
// Declare and define types in the OpenAccess namespace.
// *****************************************************************************
BEGIN_OA_NAMESPACE



// *****************************************************************************
// Forward declarations.
// *****************************************************************************
template<class K, bool KeyIsSmall>
class oaKeySizedHashSet;
template<class K, bool KeyIsSmall>
class oaKeySizedHashSetIter;



// *****************************************************************************
// oaHashSetTbl
//
// This class implements a hash table that stores indices into an array of keys
// that is stored in an owning class.
// *****************************************************************************
template<class K>
class oaHashSetTbl : public oaHashTbl<oaUInt4> {
protected:
                                oaHashSetTbl(oaUInt4 sizeIn = 32);

    virtual void                hash(oaUInt4    index,
                                     oaUInt4    &start,
                                     oaUInt4    &stride) const;
    virtual oaBoolean           compare(oaUInt4     index,
                                        const void  *data) const;

    void                        setOwner(oaKeySizedHashSet<K, false> *ownerIn);

    oaKeySizedHashSet<K, false> *owner;

    friend class oaKeySizedHashSet<K, false>;
};



// *****************************************************************************
// oaKeySizedHashSet<K, false>
//
// This class implements the hash set for key types larger than 4 bytes.
// *****************************************************************************
template<class K>
class oaKeySizedHashSet<K, false> {
public:
    void                    add(const K &key);
    oaBoolean               find(const K &key) const;
    void                    remove(const K &key);

    oaUInt4                 getNumEntries() const;

protected:
                            oaKeySizedHashSet(oaUInt4 sizeIn = 32);

    virtual void            hash(K          key,
                                 oaUInt4    &start,
                                 oaUInt4    &stride) const = 0;
    virtual oaBoolean       compare(K   key1,
                                    K   key2) const = 0;

    void                    hashIndex(oaUInt4   index,
                                      oaUInt4   &start,
                                      oaUInt4   &stride) const;
    oaBoolean               compareIndex(oaUInt4    index,
                                         const K    &key) const;

    const oaHashSetTbl<K>   *getHashTbl() const;

    oaHashSetTbl<K>         tbl;

private:
    oaArray<K>              keys;

    friend class oaHashSetTbl<K>;
    friend class oaKeySizedHashSetIter<K, false>;
};



// *****************************************************************************
// oaKeySizedHashSetIter<K, false>
//
// This class definition defines the hash set iterator for keys larger than
// 4 bytes.
// *****************************************************************************
template<class K>
class oaKeySizedHashSetIter<K, false> {
public:
                                oaKeySizedHashSetIter(oaKeySizedHashSet<K, false> &setIn);

    void                        reset();

    oaBoolean                   getNext(K &key);

protected:
    oaKeySizedHashSet<K, false> *set;
    oaUInt4                     index;
};



// *****************************************************************************
// oaKeySizedHashSet<K, true>
//
// This class implements the hash set for key types 4 bytes in size or smaller.
// *****************************************************************************
template<class K>
class oaKeySizedHashSet<K, true> : public oaHashTbl<K> {
public:
                            oaKeySizedHashSet(oaUInt4 sizeIn = 32);

    oaBoolean               find(const K &key) const;

protected:
    virtual oaBoolean       compare(K           key,
                                    const void  *data) const;
    virtual oaBoolean       compare(K   key1,
                                    K   key2) const = 0;

    oaHashTbl<K>            *getHashTbl() const;

    friend class oaKeySizedHashSetIter<K, true>;
};



// *****************************************************************************
// oaKeySizedHashSetIter<K, true>
//
// This class definition defines the hash set iterator for keys not larger than
// 4 bytes.
// *****************************************************************************
template<class K>
class oaKeySizedHashSetIter<K, true> {
public:
                                oaKeySizedHashSetIter(oaKeySizedHashSet<K, true> &setIn);

    void                        reset();

    oaBoolean                   getNext(K &key);

protected:
    oaKeySizedHashSet<K, true>  &set;
    oaUInt4                     index;
};



// *****************************************************************************
// oaHashSet<K>
//
// This class definition defines oaHashSet<K> according to one of two different
// implementations, depending on whether K is larger than 4 bytes.
// *****************************************************************************
template<class K>
class oaHashSet : public oaKeySizedHashSet<K, sizeof(K) <= sizeof(oaUInt4)> {
public:
                            oaHashSet(oaUInt4 sizeIn = 32);
};



// *****************************************************************************
// Explicit template instantiations
// *****************************************************************************
#if defined(OA_BASE_DLL_EXTERN)
OA_BASE_DLL_EXTERN template
class OA_BASE_DLL_PVT oaHashSet<oaUInt4>;
#endif



// *****************************************************************************
// oaHashSetIter<K>
//
// This class definition defines the hash set iterator according to one of two
// different implementations, depending on whether K is larger than 4 bytes.
// *****************************************************************************
template<class K>
class oaHashSetIter : public oaKeySizedHashSetIter<K, sizeof(K) <= sizeof(oaUInt4)> {
public:
                            oaHashSetIter(oaHashSet<K> &setIn);
};



// *****************************************************************************
// Explicit template instantiations
// *****************************************************************************
#if defined(OA_BASE_DLL_EXTERN)
OA_BASE_DLL_EXTERN template
class OA_BASE_DLL_PVT oaHashSetIter<oaUInt4>;
#endif



END_OA_NAMESPACE

#endif

Return to top of page

Copyright © 2002 - 2010 Cadence Design Systems, Inc.
All Rights Reserved.