⭐ 欢迎来到虫虫下载站! | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站

📄 e32hashtab.h

📁 symbian下读取服务的程序
💻 H
📖 第 1 页 / 共 4 页
字号:
// 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 + -