// Copyright (c) 2005-2009 Nokia Corporation and/or its subsidiary(-ies).

// All rights reserved.

// This component and the accompanying materials are made available

// which accompanies this distribution, and is available

//

// Initial Contributors:

// Nokia Corporation - initial contribution.

//

// Contributors:

//

// Description:

// e32/include/e32hashtab.h

// 

//

#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&);

	IMPORT_C static TUint32 IntegerPtr(TInt* const &);

	IMPORT_C static TUint32 Des8Ptr(TDesC8* const &);

	IMPORT_C static TUint32 Des16Ptr(TDesC16* const &);

	};

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::IntegerPtr;}

/**

@internalComponent

*/

inline TGeneralIdentityRelation RHashTableBase::Defaults<TInt*, RHashTableBase::EDefaultSpecifier_Normal>::Id()

	{return (TGeneralIdentityRelation)&DefaultIdentity::IntegerPtr;}

/**

@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::IntegerPtr;}

/**

@internalComponent

*/

inline TGeneralIdentityRelation RHashTableBase::Defaults<TInt32*, RHashTableBase::EDefaultSpecifier_Normal>::Id()

	{return (TGeneralIdentityRelation)&DefaultIdentity::IntegerPtr;}

/**

@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::IntegerPtr;}

/**

@internalComponent

*/

inline TGeneralIdentityRelation RHashTableBase::Defaults<TUint*, RHashTableBase::EDefaultSpecifier_Normal>::Id()

	{return (TGeneralIdentityRelation)&DefaultIdentity::IntegerPtr;}

/**

@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::IntegerPtr;}

/**

@internalComponent

*/

inline TGeneralIdentityRelation RHashTableBase::Defaults<TUint32*, RHashTableBase::EDefaultSpecifier_Normal>::Id()

	{return (TGeneralIdentityRelation)&DefaultIdentity::IntegerPtr;}

/**

@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::Des8Ptr;}

/**

@internalComponent

*/

inline TGeneralIdentityRelation RHashTableBase::Defaults<TDesC8*, RHashTableBase::EDefaultSpecifier_Normal>::Id()

	{return (TGeneralIdentityRelation)&DefaultIdentity::Des8Ptr;}

/**

@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::Des16Ptr;}

/**

@internalComponent

*/

inline TGeneralIdentityRelation RHashTableBase::Defaults<TDesC16*, RHashTableBase::EDefaultSpecifier_Normal>::Id()

	{return (TGeneralIdentityRelation)&DefaultIdentity::Des16Ptr;}

/**

@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

		{

		TUint32 iHash;

		T iT;

		};

public:

/**

A class which allows iteration over the elements of a RHashSet<T> class.

The set being iterated over may not be modified while an iteration is in progress

or the iteration operations may malfunction or panic.

@see THashSetIter<T>

*/

	typedef THashSetIter<T> TIter;

/**

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