diff -r c55016431358 -r 0a7b44b10206 symport/e32/euser/us_htab.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/symport/e32/euser/us_htab.cpp Thu Jun 25 15:59:54 2009 +0100 @@ -0,0 +1,669 @@ +// 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 "Symbian Foundation License v1.0" +// which accompanies this distribution, and is available +// at the URL "http://www.symbianfoundation.org/legal/sfl-v10.html". +// +// Initial Contributors: +// Nokia Corporation - initial contribution. +// +// Contributors: +// +// Description: +// e32/euser/us_htab.cpp +// +// + +#include "us_std.h" +#include + +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 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; + }