📄 e32hashtab.h
字号:
// e32/include/e32hashtab.h
//
// Copyright (c) 2005-2006 Symbian Ltd. All rights reserved.
//
#ifndef __E32HASHTAB_H__
#define __E32HASHTAB_H__
#include <e32cmn.h>
/**
@publishedAll
@released
Defines a function type used by a THashFunction32 object.
A function of this type implements an algorithm for producing a 32 bit hash
value from a key.
@see THashFunction32
*/
typedef TUint32 (*TGeneralHashFunction32)(const TAny*);
/**
@publishedAll
@released
A templated class which packages a function that calculates a 32 bit hash
value from a key of templated type.
A THashFunction32<T> object is constructed and passed as a parameter to
member functions of the hash table classes RHashSet<T>, RPtrHashSet<T>,
RHashMap<T,V> and RPtrHashMap<T,V>.
@see RHashSet
@see RPtrHashSet
@see RHashMap
@see RPtrHashMap
*/
template <class T>
class THashFunction32
{
public:
inline THashFunction32( TUint32 (*aHashFunc)(const T&) )
{ iHashFunction = (TGeneralHashFunction32)aHashFunc; }
inline operator TGeneralHashFunction32() const
{ return iHashFunction; }
inline TUint32 Hash(const T& aKey) const
{ return (*iHashFunction)(&aKey); }
private:
TGeneralHashFunction32 iHashFunction;
};
/**
@publishedAll
@released
A set of common hashing functions for frequently occurring types.
@see RHashSet
@see RPtrHashSet
@see RHashMap
@see RPtrHashMap
*/
class DefaultHash
{
public:
IMPORT_C static TUint32 Integer(const TInt&);
IMPORT_C static TUint32 Des8(const TDesC8&);
IMPORT_C static TUint32 Des16(const TDesC16&);
};
class THashTableIterBase;
/**
@internalComponent
Base class used in the derivation of RHashSet<T>, RPtrHashSet<T>,
RHashMap<K,V> and RPtrHashMap<K,V>.
This class provides a general hash table implementation using probe sequences
generated by pseudo-double hashing.
The class is internal and is not intended for use.
*/
class RHashTableBase
{
public:
enum TDefaultSpecifier
{
EDefaultSpecifier_Normal,
};
protected:
template<class K, TDefaultSpecifier S>
class Defaults
{
public:
inline static TGeneralHashFunction32 Hash();
inline static TGeneralIdentityRelation Id();
};
protected:
enum TElementState
{
EEmpty=0, // entry is vacant
EDeleted=1, // entry has been deleted
EGen0=2, // entry is occupied, generation number 0
EGen1=3, // entry is occupied, generation number 1
EStateMask=3,
EOccupiedMask=2,
};
struct SElement
{
inline void SetEmpty() {iHash=EEmpty;}
inline void SetDeleted() {iHash=EDeleted;}
inline TBool IsEmpty() const {return (iHash&EStateMask)==EEmpty;}
inline TBool IsDeleted() const {return (iHash&EStateMask)==EDeleted;}
inline TBool IsEmptyOrDeleted() const {return !(iHash&EOccupiedMask);}
TUint32 iHash; // bits 2-31 = 30 bit hash value, bits 0,1 = state
};
protected:
IMPORT_C RHashTableBase(TGeneralHashFunction32, TGeneralIdentityRelation, TInt aElementSize, TInt aKeyOffset);
IMPORT_C void Close();
IMPORT_C TAny* Find(const TAny* aKey, TInt aOffset=0) const;
IMPORT_C TAny* FindL(const TAny* aKey, TInt aOffset=0) const;
TInt Insert(const TAny* aKey, TAny*& aElement);
IMPORT_C TInt PtrInsert(const TAny* aKey, const TAny* aValue);
IMPORT_C void PtrInsertL(const TAny* aKey, const TAny* aValue);
IMPORT_C TInt ValueInsert(const TAny* aKey, TInt aKeySize, const TAny* aValue, TInt aValueOffset, TInt aValueSize);
IMPORT_C void ValueInsertL(const TAny* aKey, TInt aKeySize, const TAny* aValue, TInt aValueOffset, TInt aValueSize);
IMPORT_C TInt Remove(const TAny* aKey);
IMPORT_C TInt Count() const;
IMPORT_C TInt Reserve(TInt aCount);
IMPORT_C void ReserveL(TInt aCount);
IMPORT_C void ConsistencyCheck(TUint32* aDeleted=0, TUint32* aComparisons=0, TUint32 aChainLimit=0, TUint32* aChainInfo=0);
private:
void SetThresholds();
TInt ExpandTable(TInt aNewIndexBits);
void ShrinkTable();
void ReformTable(TUint aNewIndexBits);
void VerifyReform();
private:
inline SElement* Element(TInt aIndex)
{return (SElement*)(((TUint8*)iElements) + aIndex*iElementSize);}
inline const SElement* ElementC(TInt aIndex) const
{return (const SElement*)(((TUint8*)iElements) + aIndex*iElementSize);}
inline TAny* GetKey(const SElement* aElement) const
{return iKeyOffset ? ((TUint8*)aElement + iKeyOffset) : (TAny*)((TUint32*)aElement)[1];}
private:
TGeneralHashFunction32 iHashFunc; // generates the hash from a given key
TGeneralIdentityRelation iIdFunc; // compare two keys for equality
TUint8 iIndexBits; // number of bits used to index the table
TUint8 iGeneration; // 2 or 3, generation number used when traversing entire table
TUint8 iKeyOffset; // offset to key
TUint8 iPad0;
TAny* iElements;
TUint32 iCount; // number of valid entries
TUint32 iEmptyCount; // number of empty entries
TUint32 iLowerThreshold; // shrink if count drops below this
TUint32 iUpperThreshold; // expand if count rises above this
TUint32 iCleanThreshold; // clean table if count of empty entries falls below this
TInt iElementSize;
TInt iPad1; // expansion room
TInt iPad2;
friend struct RHashTableBase::SElement;
friend class THashTableIterBase;
friend class HashTest;
};
/**
@internalComponent
*/
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TInt, RHashTableBase::EDefaultSpecifier_Normal>
{
public:
inline static TGeneralHashFunction32 Hash();
inline static TGeneralIdentityRelation Id();
};
/**
@internalComponent
*/
inline TGeneralHashFunction32 RHashTableBase::Defaults<TInt, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
{return (TGeneralHashFunction32)&DefaultHash::Integer;}
/**
@internalComponent
*/
inline TGeneralIdentityRelation RHashTableBase::Defaults<TInt, RHashTableBase::EDefaultSpecifier_Normal>::Id()
{return (TGeneralIdentityRelation)&DefaultIdentity::Integer;}
/**
@internalComponent
*/
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TInt32, RHashTableBase::EDefaultSpecifier_Normal>
{
public:
inline static TGeneralHashFunction32 Hash();
inline static TGeneralIdentityRelation Id();
};
/**
@internalComponent
*/
inline TGeneralHashFunction32 RHashTableBase::Defaults<TInt32, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
{return (TGeneralHashFunction32)&DefaultHash::Integer;}
/**
@internalComponent
*/
inline TGeneralIdentityRelation RHashTableBase::Defaults<TInt32, RHashTableBase::EDefaultSpecifier_Normal>::Id()
{return (TGeneralIdentityRelation)&DefaultIdentity::Integer;}
/**
@internalComponent
*/
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TUint, RHashTableBase::EDefaultSpecifier_Normal>
{
public:
inline static TGeneralHashFunction32 Hash();
inline static TGeneralIdentityRelation Id();
};
/**
@internalComponent
*/
inline TGeneralHashFunction32 RHashTableBase::Defaults<TUint, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
{return (TGeneralHashFunction32)&DefaultHash::Integer;}
/**
@internalComponent
*/
inline TGeneralIdentityRelation RHashTableBase::Defaults<TUint, RHashTableBase::EDefaultSpecifier_Normal>::Id()
{return (TGeneralIdentityRelation)&DefaultIdentity::Integer;}
/**
@internalComponent
*/
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TUint32, RHashTableBase::EDefaultSpecifier_Normal>
{
public:
inline static TGeneralHashFunction32 Hash();
inline static TGeneralIdentityRelation Id();
};
/**
@internalComponent
*/
inline TGeneralHashFunction32 RHashTableBase::Defaults<TUint32, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
{return (TGeneralHashFunction32)&DefaultHash::Integer;}
/**
@internalComponent
*/
inline TGeneralIdentityRelation RHashTableBase::Defaults<TUint32, RHashTableBase::EDefaultSpecifier_Normal>::Id()
{return (TGeneralIdentityRelation)&DefaultIdentity::Integer;}
/**
@internalComponent
*/
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TDesC8, RHashTableBase::EDefaultSpecifier_Normal>
{
public:
inline static TGeneralHashFunction32 Hash();
inline static TGeneralIdentityRelation Id();
};
/**
@internalComponent
*/
inline TGeneralHashFunction32 RHashTableBase::Defaults<TDesC8, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
{return (TGeneralHashFunction32)&DefaultHash::Des8;}
/**
@internalComponent
*/
inline TGeneralIdentityRelation RHashTableBase::Defaults<TDesC8, RHashTableBase::EDefaultSpecifier_Normal>::Id()
{return (TGeneralIdentityRelation)&DefaultIdentity::Des8;}
/**
@internalComponent
*/
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TDesC16, RHashTableBase::EDefaultSpecifier_Normal>
{
public:
inline static TGeneralHashFunction32 Hash();
inline static TGeneralIdentityRelation Id();
};
/**
@internalComponent
*/
inline TGeneralHashFunction32 RHashTableBase::Defaults<TDesC16, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
{return (TGeneralHashFunction32)&DefaultHash::Des16;}
/**
@internalComponent
*/
inline TGeneralIdentityRelation RHashTableBase::Defaults<TDesC16, RHashTableBase::EDefaultSpecifier_Normal>::Id()
{return (TGeneralIdentityRelation)&DefaultIdentity::Des16;}
/**
@internalComponent
Base class used in the derivation of THashSetIter<T>, TPtrHashSetIter<T>,
THashMapIter<K,V> and TPtrHashMapIter<K,V>.
This class provides iteration capability for the hash table classes derived
from RHashTableBase.
The class is internal and is not intended for use.
*/
class THashTableIterBase
{
protected:
IMPORT_C THashTableIterBase(const RHashTableBase& aTable);
IMPORT_C void Reset();
IMPORT_C const TAny* Next(TInt aOffset=0);
IMPORT_C const TAny* Current(TInt aOffset=0) const;
IMPORT_C void RemoveCurrent();
private:
const RHashTableBase& iTbl;
TInt iIndex;
TInt iPad1; // expansion room
TInt iPad2;
};
template <class T> class THashSetIter;
/**
@publishedAll
@released
A templated class which implements an unordered extensional set of objects of
type T using a probe-sequence hash table. The objects are copied into the set
when they are added. A bitwise binary copy is used here, so the type T must
not implement a nontrivial copy constructor.
*/
template <class T>
class RHashSet : public RHashTableBase
{
private:
friend class THashSetIter<T>;
struct SFullElement /**< @internalComponent */
{
TUint32 iHash;
T iT;
};
public:
/**
Construct a set of objects of type T using a specified hash function and identity relation.
The set is initially empty.
@param aHash The hash function used to hash the objects of type T.
@param aIdentity The identity relation used to determine if two objects of type T
should be considered identical.
*/
inline RHashSet(const THashFunction32<T>& aHash, const TIdentityRelation<T>& aIdentity)
: RHashTableBase(aHash, aIdentity, sizeof(SFullElement), _FOFF(SFullElement,iT))
{}
/**
Construct a set of objects of type T using a default hash function and identity relation.
The set is initially empty.
*/
inline RHashSet()
: RHashTableBase(Defaults<T,EDefaultSpecifier_Normal>::Hash(), Defaults<T,EDefaultSpecifier_Normal>::Id(), sizeof(SFullElement), _FOFF(SFullElement,iT))
{}
/**
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -