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

 // All rights reserved.

 // This component and the accompanying materials are made available

 // under the terms of the License "Eclipse Public License v1.0"

 // which accompanies this distribution, and is available

 // at the URL "http://www.eclipse.org/legal/epl-v10.html".

 //

 // Initial Contributors:

 // Nokia Corporation - initial contribution.

 //

 // Contributors:

 //

 // Description:

 // e32/euser/us_htab.cpp

 // 

 //

 #include "us_std.h"

 #include <e32hashtab.h>

 const TUint KDefaultIndexBits = 4;

 const TUint KMaxIndexBits = 28;

 extern TUint32 DefaultIntegerHash(const TAny*);

 extern TUint32 DefaultStringHash(const TUint8*, TInt);

 extern TUint32 DefaultWStringHash(const TUint16*, TInt);

 #define	_DEBUG_HASH_TABLE

 #ifndef	_DEBUG

 #undef	_DEBUG_HASH_TABLE

 #endif

 #define __PANIC(x) Panic(x)

 EXPORT_C RHashTableBase::RHashTableBase(TGeneralHashFunction32 aHash, TGeneralIdentityRelation aId, TInt aElementSize, TInt aKeyOffset)

 	:	iHashFunc(aHash),

 		iIdFunc(aId),

 		iIndexBits(TUint8(KDefaultIndexBits)),

 		iGeneration(EGen0),

 		iPad0(0),

 		iElements(0),

 		iCount(0),

 		iPad1(0),

 		iPad2(0)

 	{

 	__ASSERT_ALWAYS(aHash!=NULL, __PANIC(EHashTableNoHashFunc));

 	__ASSERT_ALWAYS(aId!=NULL, __PANIC(EHashTableNoIdentityRelation));

 	__ASSERT_ALWAYS(aElementSize>0, __PANIC(EHashTableBadElementSize));

 	__ASSERT_ALWAYS(aKeyOffset==0 || TUint(aKeyOffset-4)<(TUint)Min(252,aElementSize-4), __PANIC(EHashTableBadKeyOffset));

 	iElementSize = aElementSize;

 	iKeyOffset = (TUint8)aKeyOffset;	// 0 means ptr at offset 4

 	iEmptyCount = 0;

 	SetThresholds();

 	}

 void RHashTableBase::SetThresholds()

 	{

 	TUint32 max = 1u << iIndexBits;

 	if (iIndexBits == KMaxIndexBits)

 		iUpperThreshold = KMaxTUint;

 	else

 		iUpperThreshold = (max>>1) + (max>>2);	// 3/4 of max

 	if (iIndexBits == KDefaultIndexBits)

 		iLowerThreshold = 0;

 	else

 		iLowerThreshold = max >> 2;				// 1/4 of max

 	// clean table if <1/8 of entries empty

 	iCleanThreshold = max>>3;

 	}

 EXPORT_C void RHashTableBase::Close()

 	{

 	User::Free(iElements);

 	new (this) RHashTableBase(iHashFunc, iIdFunc, iElementSize, iKeyOffset);

 	}

 EXPORT_C TInt RHashTableBase::Count() const

 	{

 	return (TInt)iCount;

 	}

 EXPORT_C TAny* RHashTableBase::Find(const TAny* aKey, TInt aOffset) const

 	{

 	if (!iElements)

 		return NULL;

 	TUint32 hash = (*iHashFunc)(aKey);

 	TUint32 ix = hash >> (32 - iIndexBits);		// top bits of hash used as initial index

 	hash = (hash &~ EStateMask) | iGeneration;

 	TUint32 mask = (1u << iIndexBits) - 1;		// iIndexBits 1's

 	TUint32 step = (hash >> 1) & mask;			// iIndexBits-1 LSBs of hash followed by 1

 	FOREVER

 		{

 		const SElement* e = ElementC(ix);

 		if (e->iHash==hash && (*iIdFunc)(aKey, GetKey(e)))

 			{

 			if (aOffset >= 0)

 				return ((TUint8*)e) + aOffset;

 			return *(TAny**)((TUint8*)e - aOffset);

 			}

 		if (e->IsEmpty())

 			break;

 		ix = (ix + step) & mask;

 		}

 	return NULL;

 	}

 EXPORT_C TAny* RHashTableBase::FindL(const TAny* aKey, TInt aOffset) const

 	{

 	TAny* p = Find(aKey, aOffset);

 	if (!p)

 		User::Leave(KErrNotFound);

 	return p;

 	}

 TInt RHashTableBase::Insert(const TAny* aKey, TAny*& aElement)

 	{

 	TInt r = KErrNone;

 	TUint32 max = 1u << iIndexBits;

 	if (!iElements)

 		{

 		iElements = User::AllocZ(max * iElementSize);

 		if (!iElements)

 			return KErrNoMemory;

 		iEmptyCount = max;

 		}

 	else if (iCount > iUpperThreshold)

 		{

 		r = ExpandTable(iIndexBits+1);

 		if (iEmptyCount>1)

 			r = KErrNone;	// doesn't matter if expand fails unless there is only one empty slot left

 		max = 1u << iIndexBits;

 		}

 	else if (iEmptyCount < iCleanThreshold)

 		ReformTable(iIndexBits);

 	TUint32 hash = (*iHashFunc)(aKey);

 	TUint32 ix = hash >> (32 - iIndexBits);

 	TUint32 mask = max - 1;

 	hash = (hash &~ EStateMask) | iGeneration;

 	TUint32 step = (hash >> 1) & mask;			// iIndexBits-1 LSBs of hash followed by 1

 	SElement* e = 0;

 	SElement* d = 0;

 	FOREVER

 		{

 		e = Element(ix);

 		if (e->IsEmpty())

 			break;

 		if (e->IsDeleted())

 			{

 			if (!d)

 				d = e;

 			}

 		else if (e->iHash==hash && (*iIdFunc)(aKey, GetKey(e)))

 			{

 			aElement = e;

 			return KErrNone;	// duplicate so always succeed

 			}

 		ix = (ix + step) & mask;

 		}

 	if (d)

 		e = d;		// if we can reuse a deleted slot, always succeed

 	else

 		{

 		if (r!=KErrNone)

 			return r;	// new slot needed - if we failed to expand, fail the request here

 		--iEmptyCount;

 		}

 	e->iHash = hash;

 	aElement = e;

 	++iCount;

 	return KErrNone;

 	}

 EXPORT_C TInt RHashTableBase::PtrInsert(const TAny* aKey, const TAny* aValue)

 	{

 	const TAny** e;

 	TInt r = Insert(aKey, (TAny*&)e);

 	if (r==KErrNone)

 		{

 		e[1] = aKey;

 		if (iElementSize>=12)

 			e[2] = aValue;

 		}

 	return r;

 	}

 EXPORT_C void RHashTableBase::PtrInsertL(const TAny* aKey, const TAny* aValue)

 	{

 	const TAny** e;

 	User::LeaveIfError(Insert(aKey, (TAny*&)e));

 	e[1] = aKey;

 	if (iElementSize>=12)

 		e[2] = aValue;

 	}

 EXPORT_C TInt RHashTableBase::ValueInsert(const TAny* aKey, TInt aKeySize, const TAny* aValue, TInt aValueOffset, TInt aValueSize)

 	{

 	TUint8* e;

 	TInt r = Insert(aKey, (TAny*&)e);

 	if (r==KErrNone)

 		{

 		memcpy(e+iKeyOffset, aKey, aKeySize);

 		if (aValue)

 			memcpy(e+aValueOffset, aValue, aValueSize);

 		}

 	return r;

 	}

 EXPORT_C void RHashTableBase::ValueInsertL(const TAny* aKey, TInt aKeySize, const TAny* aValue, TInt aValueOffset, TInt aValueSize)

 	{

 	TUint8* e;

 	User::LeaveIfError(Insert(aKey, (TAny*&)e));

 	memcpy(e+iKeyOffset, aKey, aKeySize);

 	if (aValue)

 		memcpy(e+aValueOffset, aValue, aValueSize);

 	}

 EXPORT_C TInt RHashTableBase::Remove(const TAny* aKey)

 	{

 	SElement* e = (SElement*)Find(aKey);

 	if (!e)

 		return KErrNotFound;

 	e->SetDeleted();

 	if (--iCount == 0)

 		{

 		Close();

 		return KErrNone;

 		}

 	if (iCount < iLowerThreshold)

 		ShrinkTable();

 	return KErrNone;

 	}

 void RHashTableBase::ReformTable(TUint aNewIndexBits)

 	{

 	if (!iElements)

 		return;

 	TUint32 max = 1u << iIndexBits;

 	TUint32 newmax = 1u << aNewIndexBits;

 	TUint32 newmask = newmax - 1;

 	TUint32 ix = 0;

 	TUint32 newsh = 32 - aNewIndexBits;

 	iGeneration ^= 1;	// change generation so we know which entries have been updated

 	for (; ix < max; ++ix)

 		{

 		SElement* e = Element(ix);

 		if (e->IsEmpty())

 			continue;		// skip empty entries

 		if (e->IsDeleted())

 			{

 			e->SetEmpty();	// mark deleted entries as empty

 			continue;

 			}

 		if ((e->iHash & EStateMask) == iGeneration)	// entry has been processed so leave it alone

 			continue;

 		TUint32 pos = e->iHash >> newsh;

 		if (pos == ix)

 			{

 			e->iHash ^= 1;		// entry is in first position for its hash so leave it there

 			continue;

 			}

 		TUint32 step = (e->iHash >> 1) & newmask;

 		FOREVER

 			{

 			SElement* d = Element(pos);

 			if (d->IsEmptyOrDeleted())

 				{

 				memcpy(d, e, iElementSize);

 				d->iHash &= ~EStateMask;

 				d->iHash |= iGeneration;	// mark it as processed

 				e->SetEmpty();				// remove old entry

 				break;

 				}

 			if ((d->iHash & EStateMask) != iGeneration)

 				{

 				if (pos == ix)

 					{

 					e->iHash ^= 1;		// entry is already in correct position so leave it there

 					break;

 					}

 				if ((d->iHash >> newsh) == pos)

 					{

 					// candidate for replacement is in correct position so leave it and look elsewhere

 					d->iHash ^= 1;

 					}

 				else

 					{

 					Mem::Swap(d, e, iElementSize);	// switch entries

 					d->iHash ^= 1;		// mark entry as processed

 					--ix;				// process current position again

 					break;

 					}

 				}

 			pos = (pos + step) & newmask;

 			}

 		}

 	iIndexBits = (TUint8)aNewIndexBits;

 	iEmptyCount = newmax - iCount;

 	SetThresholds();

 #ifdef _DEBUG_HASH_TABLE

 	VerifyReform();

 #endif

 	}

 #ifdef _DEBUG_HASH_TABLE

 void RHashTableBase::VerifyReform()

 	{

 	TUint32 dcount;

 	ConsistencyCheck(&dcount);

 	__ASSERT_ALWAYS(dcount==0, __PANIC(EHashTableDeletedEntryAfterReform));

 	}

 #endif

 EXPORT_C void RHashTableBase::ConsistencyCheck(TUint32* aDeleted, TUint32* aComparisons, TUint32 aChainLimit, TUint32* aChainInfo)

 	{

 #ifdef _DEBUG_HASH_TABLE

 	TUint32 count = 0;

 	TUint32 dcount = 0;

 	TUint32 ecount = 0;

 	TUint32 max = 1u << iIndexBits;

 	TUint32 mask = max - 1;

 	TUint32 sh = 32 - iIndexBits;

 	TUint32 ix = 0;

 	TUint32 cmp = 0;

 	if (aChainInfo)

 		memclr(aChainInfo, aChainLimit*sizeof(TUint32));

 	if (iElements)

 		{

 		for (ix = 0; ix < max; ++ix)

 			{

 			SElement* e = Element(ix);

 			if (e->IsEmpty())

 				{

 				++ecount;

 				continue;

 				}

 			if (e->IsDeleted())

 				{

 				++dcount;

 				continue;

 				}

 			++count;

 			__ASSERT_ALWAYS((e->iHash & EStateMask) == iGeneration, __PANIC(EHashTableBadGeneration));

 			TUint32 hash = (*iHashFunc)(GetKey(e));

 			hash = (hash &~ EStateMask) | iGeneration;

 			__ASSERT_ALWAYS(e->iHash == hash, __PANIC(EHashTableBadHash));

 			TUint32 pos = hash >> sh;

 			TUint32 step = (hash >> 1) & mask;

 			SElement* f = 0;

 			TUint32 cl = 0;

 			FOREVER

 				{

 				f = Element(pos);

 				if (f->IsEmpty())

 					{

 					f = 0;

 					break;

 					}

 				++cl;

 				if (!f->IsDeleted() && f->iHash==hash)

 					{

 					++cmp;

 					if (e==f || (*iIdFunc)(GetKey(e), GetKey(f)))

 						break;

 					}

 				pos = (pos + step) & mask;

 				}

 			__ASSERT_ALWAYS(e==f, __PANIC(EHashTableEntryLost));

 			if (aChainInfo && cl<aChainLimit)

 				++aChainInfo[cl];

 			}

 		}

 	if (aDeleted)

 		*aDeleted = dcount;

 	if (aComparisons)

 		*aComparisons = cmp;

 	__ASSERT_ALWAYS(iCount==count, __PANIC(EHashTableCountWrong));

 	__ASSERT_ALWAYS(iEmptyCount==ecount, __PANIC(EHashTableEmptyCountWrong));

 #else

 	if (aDeleted)

 		*aDeleted = KMaxTUint;

 	if (aComparisons)

 		*aComparisons = KMaxTUint;

 	if (aChainInfo)

 		memclr(aChainInfo, aChainLimit*sizeof(TUint32));

 #endif

 	}

 void RHashTableBase::ShrinkTable()

 	{

 	ReformTable(iIndexBits - 1);

 	TUint32 max = 1u << iIndexBits;

 	iElements = User::ReAlloc(iElements, max * iElementSize);

 	}

 TInt RHashTableBase::ExpandTable(TInt aNewIndexBits)

 	{

 	TUint32 newmax = 1u << aNewIndexBits;

 	if (!iElements)

 		{

 		iElements = User::AllocZ(newmax * iElementSize);

 		if (!iElements)

 			return KErrNoMemory;

 		iIndexBits = (TUint8)aNewIndexBits;

 		iEmptyCount = newmax;

 		SetThresholds();

 		return KErrNone;

 		}

 	TUint32 max = 1u << iIndexBits;

 	TAny* p = User::ReAlloc(iElements, newmax * iElementSize);

 	if (!p)

 		return KErrNoMemory;

 	iElements = p;

 	memclr(Element(max), (newmax-max)*iElementSize);

 	ReformTable(aNewIndexBits);

 	return KErrNone;

 	}

 EXPORT_C TInt RHashTableBase::Reserve(TInt aCount)

 	{

 	__ASSERT_ALWAYS((TUint)aCount<0x40000000u, __PANIC(EHashTableBadReserveCount));

 	TInt new_ixb = iIndexBits;

 	TUint grow_threshold = iUpperThreshold;

 	while (TUint(aCount) > grow_threshold)

 		{

 		grow_threshold <<= 1;

 		++new_ixb;

 		}

 	// Expand the table if it isn't large enough to fit aCount elements in it

 	// or if the table hasn't yet been created, create it with ExpandTable

 	if (new_ixb > TInt(iIndexBits) || !iElements)

 		{

 		return ExpandTable(new_ixb);

 		}

 	return KErrNone;

 	}

 EXPORT_C void RHashTableBase::ReserveL(TInt aCount)

 	{

 	User::LeaveIfError(Reserve(aCount));

 	}

 EXPORT_C THashTableIterBase::THashTableIterBase(const RHashTableBase& aTable)

 	:	iTbl(aTable), iIndex(-1), iPad1(0), iPad2(0)

 	{

 	}

 EXPORT_C void THashTableIterBase::Reset()

 	{

 	iIndex = -1;

 	}

 EXPORT_C const TAny* THashTableIterBase::Next(TInt aOffset)

 	{

 	TInt max = 1 << iTbl.iIndexBits;

 	if (!iTbl.iElements)

 		return NULL;

 	__ASSERT_DEBUG(iIndex>=-1 && iIndex<=max, __PANIC(EHashTableIterNextBadIndex));

 	if (iIndex < max)

 		++iIndex;

 	for(; iIndex < max; ++iIndex)

 		{

 		const RHashTableBase::SElement* e = iTbl.ElementC(iIndex);

 		if (!e->IsEmptyOrDeleted())

 			{

 			if (aOffset >= 0)

 				return (TUint8*)e + aOffset;

 			return *(const TAny**)((TUint8*)e - aOffset);

 			}

 		}

 	return NULL;

 	}

 EXPORT_C const TAny* THashTableIterBase::Current(TInt aOffset) const

 	{

 	TInt max = 1 << iTbl.iIndexBits;

 	if (!iTbl.iElements || iIndex<0 || iIndex>=max)

 		return NULL;

 	const RHashTableBase::SElement* e = iTbl.ElementC(iIndex);

 	__ASSERT_DEBUG(!e->IsEmptyOrDeleted(), __PANIC(EHashTableIterCurrentBadIndex));

 	if (aOffset >= 0)

 		return (TUint8*)e + aOffset;

 	return *(const TAny**)((TUint8*)e - aOffset);

 	}

 EXPORT_C void THashTableIterBase::RemoveCurrent()

 	{

 	TInt max = 1 << iTbl.iIndexBits;

 	if (!iTbl.iElements || iIndex<0 || iIndex>=max)

 		return;

 	RHashTableBase& tbl = (RHashTableBase&)iTbl;

 	RHashTableBase::SElement* e = tbl.Element(iIndex);

 	__ASSERT_DEBUG(!e->IsEmptyOrDeleted(), __PANIC(EHashTableIterCurrentBadIndex));

 	// mark entry as deleted but don't shrink the array since that will mess up the iteration

 	e->SetDeleted();

 	if (--tbl.iCount == 0)

 		{

 		memclr(tbl.iElements, max * tbl.iElementSize);

 		tbl.iEmptyCount = max;

 		tbl.iGeneration = RHashTableBase::EGen0;

 		}

 	}

 /**

 @publishedAll

 @released

 Calculate a 32 bit hash from an 8 bit descriptor.

 @param	aDes	The descriptor to be hashed.

 @return			The calculated 32 bit hash value.

 */

 EXPORT_C TUint32 DefaultHash::Des8(const TDesC8& aDes)

 	{

 	return DefaultStringHash(aDes.Ptr(), aDes.Length());

 	}

 /**

 @publishedAll

 @released

 Calculate a 32 bit hash from a 16 bit descriptor.

 @param	aDes	The descriptor to be hashed.

 @return			The calculated 32 bit hash value.

 */

 EXPORT_C TUint32 DefaultHash::Des16(const TDesC16& aDes)

 	{

 	return DefaultWStringHash(aDes.Ptr(), aDes.Size());

 	}

 /**

 @publishedAll

 @released

 Calculate a 32 bit hash from a TInt pointer.

 @param	aPtr	The TInt pointer to be hashed.

 @return			The calculated 32 bit hash value.

 */

 EXPORT_C TUint32 DefaultHash::IntegerPtr(TInt* const& aPtr)

 	{

 	return Integer((TInt)aPtr);

 	}

 /**

 @publishedAll

 @released

 Calculate a 32 bit hash from a TDesC8 pointer.

 @param	aPtr	The TDesC8 pointer to be hashed.

 @return			The calculated 32 bit hash value.

 */

 EXPORT_C TUint32 DefaultHash::Des8Ptr(TDesC8* const& aPtr)

 	{

 	return Integer((TInt)aPtr);

 	}

 /**

 @publishedAll

 @released

 Calculate a 32 bit hash from a TDesC16 pointer.

 @param	aPtr	The TDesC16 pointer to be hashed.

 @return			The calculated 32 bit hash value.

 */

 EXPORT_C TUint32 DefaultHash::Des16Ptr(TDesC16* const& aPtr)

 	{

 	return Integer((TInt)aPtr);

 	}

 /**

 @publishedAll

 @released

 Compare two integers for equality.

 @param	aA	The first integer to be compared

 @param	aB	The second integer to be compared

 @return		ETrue if the arguments are equal, EFalse otherwise.

 */

 EXPORT_C TBool DefaultIdentity::Integer(const TInt& aA, const TInt& aB)

 	{

 	return aA == aB;

 	}

 /**

 @publishedAll

 @released

 Compare two 8 bit descriptors for exact binary equality.

 @param	aA	The first integer to be compared

 @param	aB	The second integer to be compared

 @return		ETrue if the arguments are identical, EFalse otherwise.

 */

 EXPORT_C TBool DefaultIdentity::Des8(const TDesC8& aA, const TDesC8& aB)

 	{

 	return aA == aB;

 	}

 /**

 @publishedAll

 @released

 Compare two 16 bit descriptors for exact binary equality.

 @param	aA	The first integer to be compared

 @param	aB	The second integer to be compared

 @return		ETrue if the arguments are identical, EFalse otherwise.

 */

 EXPORT_C TBool DefaultIdentity::Des16(const TDesC16& aA, const TDesC16& aB)

 	{

 	return aA == aB;

 	}

 /**

 @publishedAll

 @released

 Compare two TInt pointers for equality.

 @param	aA	The first pointer to be compared

 @param	aB	The second pointer to be compared

 @return		ETrue if the arguments are equal, EFalse otherwise.

 */

 EXPORT_C TBool DefaultIdentity::IntegerPtr(TInt* const& aA,TInt* const& aB)

 	{

 	return aA == aB;

 	}

 /**

 @publishedAll

 @released

 Compare two TDesC8 pointers for equality.

 @param	aA	The first pointer to be compared

 @param	aB	The second pointer to be compared

 @return		ETrue if the arguments are equal, EFalse otherwise.

 */

 EXPORT_C TBool DefaultIdentity::Des8Ptr(TDesC8* const& aA,TDesC8* const& aB)

 	{

 	return aA == aB;

 	}

 /**

 @publishedAll

 @released

 Compare two TDesC16 pointers for equality.

 @param	aA	The first pointer to be compared

 @param	aB	The second pointer to be compared

 @return		ETrue if the arguments are equal, EFalse otherwise.

 */

 EXPORT_C TBool DefaultIdentity::Des16Ptr(TDesC16* const& aA,TDesC16* const& aB)

 	{

 	return aA == aB;

 	}