// 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/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.