diff -r c55016431358 -r 0a7b44b10206 symport/e32/include/e32hashtab.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/symport/e32/include/e32hashtab.h Thu Jun 25 15:59:54 2009 +0100 @@ -0,0 +1,1748 @@ +// 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/include/e32hashtab.h +// +// + +#ifndef __E32HASHTAB_H__ +#define __E32HASHTAB_H__ +#include + +/** +@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 object is constructed and passed as a parameter to +member functions of the hash table classes RHashSet, RPtrHashSet, +RHashMap and RPtrHashMap. + +@see RHashSet +@see RPtrHashSet +@see RHashMap +@see RPtrHashMap +*/ +template +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, RPtrHashSet, +RHashMap and RPtrHashMap. + +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 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 + { +public: + inline static TGeneralHashFunction32 Hash(); + inline static TGeneralIdentityRelation Id(); + }; + +/** +@internalComponent +*/ +inline TGeneralHashFunction32 RHashTableBase::Defaults::Hash() + {return (TGeneralHashFunction32)&DefaultHash::IntegerPtr;} + +/** +@internalComponent +*/ +inline TGeneralIdentityRelation RHashTableBase::Defaults::Id() + {return (TGeneralIdentityRelation)&DefaultIdentity::IntegerPtr;} + +/** +@internalComponent +*/ +TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults + { +public: + inline static TGeneralHashFunction32 Hash(); + inline static TGeneralIdentityRelation Id(); + }; + +/** +@internalComponent +*/ +inline TGeneralHashFunction32 RHashTableBase::Defaults::Hash() + {return (TGeneralHashFunction32)&DefaultHash::IntegerPtr;} + +/** +@internalComponent +*/ +inline TGeneralIdentityRelation RHashTableBase::Defaults::Id() + {return (TGeneralIdentityRelation)&DefaultIdentity::IntegerPtr;} + +/** +@internalComponent +*/ +TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults + { +public: + inline static TGeneralHashFunction32 Hash(); + inline static TGeneralIdentityRelation Id(); + }; +/** +@internalComponent +*/ +inline TGeneralHashFunction32 RHashTableBase::Defaults::Hash() + {return (TGeneralHashFunction32)&DefaultHash::IntegerPtr;} + +/** +@internalComponent +*/ +inline TGeneralIdentityRelation RHashTableBase::Defaults::Id() + {return (TGeneralIdentityRelation)&DefaultIdentity::IntegerPtr;} + + +/** +@internalComponent +*/ +TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults + { +public: + inline static TGeneralHashFunction32 Hash(); + inline static TGeneralIdentityRelation Id(); + }; +/** +@internalComponent +*/ +inline TGeneralHashFunction32 RHashTableBase::Defaults::Hash() + {return (TGeneralHashFunction32)&DefaultHash::IntegerPtr;} + +/** +@internalComponent +*/ +inline TGeneralIdentityRelation RHashTableBase::Defaults::Id() + {return (TGeneralIdentityRelation)&DefaultIdentity::IntegerPtr;} + +/** +@internalComponent +*/ +TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults + { +public: + inline static TGeneralHashFunction32 Hash(); + inline static TGeneralIdentityRelation Id(); + }; +/** +@internalComponent +*/ +inline TGeneralHashFunction32 RHashTableBase::Defaults::Hash() + {return (TGeneralHashFunction32)&DefaultHash::Des8Ptr;} + +/** +@internalComponent +*/ +inline TGeneralIdentityRelation RHashTableBase::Defaults::Id() + {return (TGeneralIdentityRelation)&DefaultIdentity::Des8Ptr;} + +/** +@internalComponent +*/ +TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults + { +public: + inline static TGeneralHashFunction32 Hash(); + inline static TGeneralIdentityRelation Id(); + }; +/** +@internalComponent +*/ +inline TGeneralHashFunction32 RHashTableBase::Defaults::Hash() + {return (TGeneralHashFunction32)&DefaultHash::Des16Ptr;} + +/** +@internalComponent +*/ +inline TGeneralIdentityRelation RHashTableBase::Defaults::Id() + {return (TGeneralIdentityRelation)&DefaultIdentity::Des16Ptr;} + +/** +@internalComponent +*/ +TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults + { +public: + inline static TGeneralHashFunction32 Hash(); + inline static TGeneralIdentityRelation Id(); + }; + +/** +@internalComponent +*/ +inline TGeneralHashFunction32 RHashTableBase::Defaults::Hash() + {return (TGeneralHashFunction32)&DefaultHash::Integer;} + +/** +@internalComponent +*/ +inline TGeneralIdentityRelation RHashTableBase::Defaults::Id() + {return (TGeneralIdentityRelation)&DefaultIdentity::Integer;} + +/** +@internalComponent +*/ +TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults + { +public: + inline static TGeneralHashFunction32 Hash(); + inline static TGeneralIdentityRelation Id(); + }; + +/** +@internalComponent +*/ +inline TGeneralHashFunction32 RHashTableBase::Defaults::Hash() + {return (TGeneralHashFunction32)&DefaultHash::Integer;} + +/** +@internalComponent +*/ +inline TGeneralIdentityRelation RHashTableBase::Defaults::Id() + {return (TGeneralIdentityRelation)&DefaultIdentity::Integer;} + +/** +@internalComponent +*/ +TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults + { +public: + inline static TGeneralHashFunction32 Hash(); + inline static TGeneralIdentityRelation Id(); + }; + +/** +@internalComponent +*/ +inline TGeneralHashFunction32 RHashTableBase::Defaults::Hash() + {return (TGeneralHashFunction32)&DefaultHash::Integer;} + +/** +@internalComponent +*/ +inline TGeneralIdentityRelation RHashTableBase::Defaults::Id() + {return (TGeneralIdentityRelation)&DefaultIdentity::Integer;} + + +/** +@internalComponent +*/ +TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults + { +public: + inline static TGeneralHashFunction32 Hash(); + inline static TGeneralIdentityRelation Id(); + }; + +/** +@internalComponent +*/ +inline TGeneralHashFunction32 RHashTableBase::Defaults::Hash() + {return (TGeneralHashFunction32)&DefaultHash::Integer;} + +/** +@internalComponent +*/ +inline TGeneralIdentityRelation RHashTableBase::Defaults::Id() + {return (TGeneralIdentityRelation)&DefaultIdentity::Integer;} + + +/** +@internalComponent +*/ +TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults + { +public: + inline static TGeneralHashFunction32 Hash(); + inline static TGeneralIdentityRelation Id(); + }; + +/** +@internalComponent +*/ +inline TGeneralHashFunction32 RHashTableBase::Defaults::Hash() + {return (TGeneralHashFunction32)&DefaultHash::Des8;} + +/** +@internalComponent +*/ +inline TGeneralIdentityRelation RHashTableBase::Defaults::Id() + {return (TGeneralIdentityRelation)&DefaultIdentity::Des8;} + + +/** +@internalComponent +*/ +TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults + { +public: + inline static TGeneralHashFunction32 Hash(); + inline static TGeneralIdentityRelation Id(); + }; + +/** +@internalComponent +*/ +inline TGeneralHashFunction32 RHashTableBase::Defaults::Hash() + {return (TGeneralHashFunction32)&DefaultHash::Des16;} + +/** +@internalComponent +*/ +inline TGeneralIdentityRelation RHashTableBase::Defaults::Id() + {return (TGeneralIdentityRelation)&DefaultIdentity::Des16;} + + + + +/** +@internalComponent + +Base class used in the derivation of THashSetIter, TPtrHashSetIter, +THashMapIter and TPtrHashMapIter. + +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 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 RHashSet : public RHashTableBase + { +private: + friend class THashSetIter; + + struct SFullElement + { + TUint32 iHash; + T iT; + }; + +public: + +/** +A class which allows iteration over the elements of a RHashSet 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 +*/ + typedef THashSetIter 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 + should be considered identical. +*/ + inline RHashSet(const THashFunction32& aHash, const TIdentityRelation& 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::Hash(), Defaults::Id(), sizeof(SFullElement), _FOFF(SFullElement,iT)) + {} + + +/** +Free all memory used by this set. +Returns the set to the same state it had following construction. +*/ + inline void Close() + { RHashTableBase::Close(); } + + +/** +Locate a specified element in the set. + +@param aKey The object of type T to search for. +@return A pointer to the copy of the specified object in the set, if it + exists. The object may not be modified via this pointer. + NULL if the specified object is not a member of this set. +*/ + inline const T* Find(const T& aKey) const + { return (const T*)RHashTableBase::Find(&aKey, _FOFF(SFullElement,iT)); } + + +/** +Locate a specified element in the set. + +@param aKey The object of type T to search for. +@return A reference to the copy of the specified object in the set, if it + exists. The object may not be modified via this reference. +@leave KErrNotFound if the specified object is not a member of this set. +*/ + inline const T& FindL(const T& aKey) const + { return *(const T*)RHashTableBase::FindL(&aKey, _FOFF(SFullElement,iT)); } + + +/** +Locate a specified element in the set. + +@param aKey The object of type T to search for. +@return A pointer to the copy of the specified object in the set, if it + exists. The object may be modified via this pointer. Care should + be taken not to modify any parts of the object which are used by + either the hash function or the identity relation for this set. + If this is done the set may become inconsistent, resulting in + malfunctions and/or panics at a later time. + NULL if the specified object is not a member of this set. +*/ + inline T* Find(const T& aKey) + { return (T*)RHashTableBase::Find(&aKey, _FOFF(SFullElement,iT)); } + + +/** +Locate a specified element in the set. + +@param aKey The object of type T to search for. +@return A reference to the copy of the specified object in the set, if it + exists. The object may be modified via this reference. Care should + be taken not to modify any parts of the object which are used by + either the hash function or the identity relation for this set. + If this is done the set may become inconsistent, resulting in + malfunctions and/or panics at a later time. +@leave KErrNotFound if the specified object is not a member of this set. +*/ + inline T& FindL(const T& aKey) + { return *(T*)RHashTableBase::FindL(&aKey, _FOFF(SFullElement,iT)); } + + +/** +Insert an element into the set. + +If the specified object is not currently a member of the set, a copy of the +object is added to the set and KErrNone is returned. +If the specified object is currently a member of the set, the existing copy +of the object is replaced by the provided object and KErrNone is +returned. +In both cases the object is copied bitwise into the set. + +@param aKey The object of type T to add to the set. +@return KErrNone if the object was added successfully. + KErrNoMemory if memory could not be allocated to store + the copy of aKey. +*/ + inline TInt Insert(const T& aKey) + { return RHashTableBase::ValueInsert(&aKey, sizeof(T), 0, 0, 0); } + + +/** +Insert an element into the set. + +If the specified object is not currently a member of the set, a copy of the +object is added to the set and KErrNone is returned. +If the specified object is currently a member of the set, the existing copy +of the object is replaced by the provided object and KErrNone is +returned. +In both cases the object is copied bitwise into the set. + +@param aKey The object of type T to add to the set. +@leave KErrNoMemory if memory could not be allocated to store + the copy of aKey. +*/ + inline void InsertL(const T& aKey) + { RHashTableBase::ValueInsertL(&aKey, sizeof(T), 0, 0, 0); } + + +/** +Remove an element from the set. + +@param aKey The object to be removed. +@return KErrNone if the object was removed successfully. + KErrNotFound if the object was not present in the set. +*/ + inline TInt Remove(const T& aKey) + { return RHashTableBase::Remove(&aKey); } + + +/** +Query the number of elements in the set. + +@return The number of elements currently in the set. +*/ + inline TInt Count() const + { return RHashTableBase::Count(); } + + +/** +Expand the set to accommodate a specified number of elements. +If the set already has enough space for the specified number of elements, no +action is taken. Any elements already in the set are retained. + +@param aCount The number of elements for which space should be allocated. +@return KErrNone if the operation completed successfully. +@return KErrNoMemory if sufficient memory could not be allocated. +*/ + inline TInt Reserve(TInt aCount) + { return RHashTableBase::Reserve(aCount); } + + +/** +Expand the set to accommodate a specified number of elements. +If the set already has enough space for the specified number of elements, no +action is taken. Any elements already in the set are retained. + +@param aCount The number of elements for which space should be allocated. +@leave KErrNoMemory if sufficient memory could not be allocated. +*/ + inline void ReserveL(TInt aCount) + { RHashTableBase::ReserveL(aCount); } + + }; + + +/** +@publishedAll +@released + +A templated class which allows iteration over the elements of a RHashSet +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 RHashSet +*/ +template +class THashSetIter : public THashTableIterBase + { +private: + + struct SFullElement + { + TUint32 iHash; + T iT; + }; + +public: + +/** +Construct an iterator over the specified set. +The iterator starts at conceptual position one before the beginning of the list +being iterated. + +@param aSet The set to be iterated over. +*/ + inline THashSetIter(const RHashSet& aSet) + : THashTableIterBase(aSet) + {} + + +/** +Reset the iterator to its initial state. + +@param aSet The set to be iterated over. +*/ + inline void Reset() + { THashTableIterBase::Reset(); } + + +/** +Return the current position of the iterator. + +@return A pointer to the set member corresponding to the current position of the + iterator. + NULL if the iterator has just been constructed or reset, or if it has + previously reached the end of an iteration. +*/ + inline const T* Current() const + { return (const T*)THashTableIterBase::Current(_FOFF(SFullElement,iT)); } + + +/** +Steps the iterator to the next position. + +@return A pointer to the set member corresponding to the next position of the + iterator. + NULL if the iterator has exhausted all the available set elements. +*/ + inline const T* Next() + { return (const T*)THashTableIterBase::Next(_FOFF(SFullElement,iT)); } + + +/** +Removes the element at the current iterator position from the hash table. +If the iterator does not currently point to a valid element, no action is taken. +Note that the iterator position is not altered so it no longer points to a valid +element following the Remove(). It is illegal to call Current() on the iterator +after calling Remove() - the only legal operations are Reset() and Next(). + +*/ + inline void RemoveCurrent() + { THashTableIterBase::RemoveCurrent(); } + }; + + + +template class TPtrHashSetIter; + +/** +@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 not copied into the set +when they are added; rather the set stores pointers to the contained objects. + +*/ +template +class RPtrHashSet : public RHashTableBase + { +private: + friend class TPtrHashSetIter; + + struct SFullElement + { + TUint32 iHash; + T* iT; + }; + +public: + +/** +A class which allows iteration over the elements of a RPtrHashSet 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 TPtrHashSetIter +*/ + typedef TPtrHashSetIter 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 + should be considered identical. +*/ + inline RPtrHashSet(const THashFunction32& aHash, const TIdentityRelation& aIdentity) + : RHashTableBase(aHash, aIdentity, sizeof(SFullElement), 0) + {} + + +/** +Construct a set of objects of type T using a default hash function and identity relation. +The set is initially empty. +*/ + inline RPtrHashSet() + : RHashTableBase(Defaults::Hash(), Defaults::Id(), sizeof(SFullElement), 0) + {} + + +/** +Free all memory used by this set. +Returns the set to the same state it had following construction. +*/ + inline void Close() + { RHashTableBase::Close(); } + + +/** +Locate a specified element in the set. + +@param aKey The object of type T to search for. +@return A pointer to the specified object, if it is in the set. + The object may not be modified via this pointer. + NULL if the specified object is not a member of this set. +*/ + inline const T* Find(const T& aKey) const + { return (const T*)RHashTableBase::Find(&aKey, -_FOFF(SFullElement,iT)); } + + +/** +Locate a specified element in the set. + +@param aKey The object of type T to search for. +@return A reference to the specified object, if it is in the set. + The object may not be modified via this reference. +@leave KErrNotFound if the specified object is not a member of this set. +*/ + inline const T& FindL(const T& aKey) const + { return *(const T*)RHashTableBase::FindL(&aKey, -_FOFF(SFullElement,iT)); } + + +/** +Locate a specified element in the set. + +@param aKey The object of type T to search for. +@return A pointer to the specified object, if it is in the set. + The object may be modified via this pointer. Care should + be taken not to modify any parts of the object which are used by + either the hash function or the identity relation for this set. + If this is done the set may become inconsistent, resulting in + malfunctions and/or panics at a later time. + NULL if the specified object is not a member of this set. +*/ + inline T* Find(const T& aKey) + { return (T*)RHashTableBase::Find(&aKey, -_FOFF(SFullElement,iT)); } + + +/** +Locate a specified element in the set. + +@param aKey The object of type T to search for. +@return A reference to the specified object, if it is in the set. + The object may be modified via this reference. Care should + be taken not to modify any parts of the object which are used by + either the hash function or the identity relation for this set. + If this is done the set may become inconsistent, resulting in + malfunctions and/or panics at a later time. +@leave KErrNotFound if the specified object is not a member of this set. +*/ + inline T& FindL(const T& aKey) + { return *(T*)RHashTableBase::FindL(&aKey, -_FOFF(SFullElement,iT)); } + + +/** +Insert an element into the set. + +If the specified object is not currently a member of the set, a pointer to the +object is added to the set and KErrNone is returned. +If the specified object is currently a member of the set, the existing pointer +to the object is replaced by the provided pointer and KErrNone is +returned. +In both cases only a pointer to the object is stored - the object is never copied. + +@param aKey A pointer to the object of type T to add to the set. +@return KErrNone if the object was added successfully. + KErrNoMemory if memory could not be allocated to store + the pointer to the new object. +*/ + inline TInt Insert(const T* aKey) + { return RHashTableBase::PtrInsert(aKey, 0); } + + +/** +Insert an element into the set. + +If the specified object is not currently a member of the set, a pointer to the +object is added to the set and KErrNone is returned. +If the specified object is currently a member of the set, the existing pointer +to the object is replaced by the provided pointer and KErrNone is +returned. +In both cases only a pointer to the object is stored - the object is never copied. + +@param aKey A pointer to the object of type T to add to the set. +@leave KErrNoMemory if memory could not be allocated to store the pointer to the new object. +*/ + inline void InsertL(const T* aKey) + { RHashTableBase::PtrInsertL(aKey, 0); } + + +/** +Remove an element from the set. + +@param aKey A pointer to the object to be removed. +@return KErrNone if the object was removed successfully. + KErrNotFound if the object was not present in the set. +*/ + inline TInt Remove(const T* aKey) + { return RHashTableBase::Remove(aKey); } + + +/** +Query the number of elements in the set. + +@return The number of elements currently in the set. +*/ + inline TInt Count() const + { return RHashTableBase::Count(); } + + +/** +Expand the set to accommodate a specified number of elements. +If the set already has enough space for the specified number of elements, no +action is taken. Any elements already in the set are retained. + +@param aCount The number of elements for which space should be allocated. +@return KErrNone if the operation completed successfully. +@return KErrNoMemory if sufficient memory could not be allocated. +*/ + inline TInt Reserve(TInt aCount) + { return RHashTableBase::Reserve(aCount); } + + +/** +Expand the set to accommodate a specified number of elements. +If the set already has enough space for the specified number of elements, no +action is taken. Any elements already in the set are retained. + +@param aCount The number of elements for which space should be allocated. +@leave KErrNoMemory if sufficient memory could not be allocated. +*/ + inline void ReserveL(TInt aCount) + { RHashTableBase::ReserveL(aCount); } + + + void ResetAndDestroy(); + }; + + +/** +@publishedAll +@released + +A templated class which allows iteration over the elements of a RPtrHashSet +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 RPtrHashSet +*/ +template +class TPtrHashSetIter : public THashTableIterBase + { +private: + + struct SFullElement + { + TUint32 iHash; + T* iT; + }; + +public: + +/** +Construct an iterator over the specified set. +The iterator starts at conceptual position one before the beginning of the list +being iterated. + +@param aSet The set to be iterated over. +*/ + inline TPtrHashSetIter(const RPtrHashSet& aSet) + : THashTableIterBase(aSet) + {} + + +/** +Reset the iterator to its initial state. + +@param aSet The set to be iterated over. +*/ + inline void Reset() + { THashTableIterBase::Reset(); } + + +/** +Return the current position of the iterator. + +@return A pointer to the set member corresponding to the current position of the + iterator. + NULL if the iterator has just been constructed or reset, or if it has + previously reached the end of an iteration. +*/ + inline const T* Current() const + { return (const T*)THashTableIterBase::Current(-_FOFF(SFullElement,iT)); } + + +/** +Steps the iterator to the next position. + +@return A pointer to the set member corresponding to the next position of the + iterator. + NULL if the iterator has exhausted all the available set elements. +*/ + inline const T* Next() + { return (const T*)THashTableIterBase::Next(-_FOFF(SFullElement,iT)); } + + +/** +Removes the element at the current iterator position from the hash table. +If the iterator does not currently point to a valid element, no action is taken. +Note that the iterator position is not altered so it no longer points to a valid +element following the Remove(). It is illegal to call Current() on the iterator +after calling Remove() - the only legal operations are Reset() and Next(). + +*/ + inline void RemoveCurrent() + { THashTableIterBase::RemoveCurrent(); } + }; + + + +template class THashMapIter; + +/** +@publishedAll +@released + +A templated class which implements an associative array with key type K and value type V, +using a probe-sequence hash table. Both the key and value objects are copied into the +table when they are added. A bitwise binary copy is used here, so neither of the types +K and V may implement a nontrivial copy constructor. + +*/ +template +class RHashMap : public RHashTableBase + { +private: + friend class THashMapIter; + + struct SFullElement + { + TUint32 iHash; + K iK; + V iV; + }; + +public: + +/** +A class which allows iteration over the elements of a RHashMap class. + +The array being iterated over may not be modified while an iteration is in progress +or the iteration operations may malfunction or panic. + +@see THashMapIter +*/ + typedef THashMapIter TIter; + +/** +Construct an associative array of key-value pairs of type (K,V) using a +specified hash function and identity relation. +The array initially contains no key-value pairs. + +@param aHash The hash function used to hash the key objects of type K. +@param aIdentity The identity relation used to determine if two key objects + of type K should be considered identical. +*/ + inline RHashMap(const THashFunction32& aHash, const TIdentityRelation& aIdentity) + : RHashTableBase(aHash, aIdentity, sizeof(SFullElement), _FOFF(SFullElement,iK)) + {} + + +/** +Construct an associative array of key-value pairs of type (K,V) using a +default hash function and identity relation. +The array initially contains no key-value pairs. +*/ + inline RHashMap() + : RHashTableBase(Defaults::Hash(), Defaults::Id(), sizeof(SFullElement), _FOFF(SFullElement,iK)) + {} + + +/** +Free all memory used by this array. +Returns the array to the same state it had following construction. +*/ + inline void Close() + { RHashTableBase::Close(); } + + +/** +Look up a specified key in the associative array and return a pointer to the +corresponding value. + +@param aKey The key object of type K to look up. +@return A pointer to the copy of the corresponding value object in the + array, if the specified key object was found. + The value object may not be modified via this pointer. + NULL if the specified key object was not found. +*/ + inline const V* Find(const K& aKey) const + { return (const V*)RHashTableBase::Find(&aKey, _FOFF(SFullElement,iV)); } + + +/** +Look up a specified key in the associative array and return a pointer to the +corresponding value. + +@param aKey The key object of type K to look up. +@return A reference to the copy of the corresponding value object in the + array, if the specified key object was found. + The value object may not be modified via this reference. +@leave KErrNotFound if the specified key object was not found. +*/ + inline const V& FindL(const K& aKey) const + { return *(const V*)RHashTableBase::FindL(&aKey, _FOFF(SFullElement,iV)); } + + +/** +Look up a specified key in the associative array and return a pointer to the +corresponding value. + +@param aKey The key object of type K to look up. +@return A pointer to the copy of the corresponding value object in the + array, if the specified key object was found. + The value object may be modified via this pointer. + NULL if the specified key object was not found. +*/ + inline V* Find(const K& aKey) + { return (V*)RHashTableBase::Find(&aKey, _FOFF(SFullElement,iV)); } + + +/** +Look up a specified key in the associative array and return a pointer to the +corresponding value. + +@param aKey The key object of type K to look up. +@return A reference to the copy of the corresponding value object in the + array, if the specified key object was found. + The value object may be modified via this reference. +@leave KErrNotFound if the specified key object was not found. +*/ + inline V& FindL(const K& aKey) + { return *(V*)RHashTableBase::FindL(&aKey, _FOFF(SFullElement,iV)); } + + +/** +Insert a key-value pair into the array. + +If the specified key object is not found in the array, a copy of the +key object along with a copy of the value object are added to the array +and KErrNone is returned. +If the specified key object is found in the array, the existing copies +of both the key and value objects are replaced by the provided objects +and KErrNone is returned. +In both cases the objects are copied bitwise into the array. + +@param aKey The key object of type K to add to the array. +@param aValue The value object of type V to associate with aKey. +@return KErrNone if the key-value pair was added successfully. + KErrNoMemory if memory could not be allocated to store + the copies of aKey and aValue. +*/ + inline TInt Insert(const K& aKey, const V& aValue) + { return RHashTableBase::ValueInsert(&aKey, sizeof(K), &aValue, _FOFF(SFullElement,iV), sizeof(V)); } + + +/** +Insert a key-value pair into the array. + +If the specified key object is not found in the array, a copy of the +key object along with a copy of the value object are added to the array +and KErrNone is returned. +If the specified key object is found in the array, the existing copies +of both the key and value objects are replaced by the provided objects +and KErrNone is returned. +In both cases the objects are copied bitwise into the array. + +@param aKey The key object of type K to add to the array. +@param aValue The value object of type V to associate with aKey. +@leave KErrNoMemory if memory could not be allocated to store the copies of aKey and aValue. +*/ + inline void InsertL(const K& aKey, const V& aValue) + { RHashTableBase::ValueInsertL(&aKey, sizeof(K), &aValue, _FOFF(SFullElement,iV), sizeof(V)); } + + +/** +Remove a key-value pair from the array. + +@param aKey The key to be removed. +@return KErrNone if the key object and corresponding value object were + removed successfully. + KErrNotFound if the key object was not present in the array. +*/ + inline TInt Remove(const K& aKey) + { return RHashTableBase::Remove(&aKey); } + + +/** +Query the number of key-value pairs in the array. + +@return The number of key-value pairs currently in the array. +*/ + inline TInt Count() const + { return RHashTableBase::Count(); } + + +/** +Expand the array to accommodate a specified number of key-value pairs. +If the set already has enough space for the specified number of elements, no +action is taken. Any elements already in the set are retained. + +@param aCount The number of key-value pairs for which space should be allocated. +@return KErrNone if the operation completed successfully. +@return KErrNoMemory if sufficient memory could not be allocated. +*/ + inline TInt Reserve(TInt aCount) + { return RHashTableBase::Reserve(aCount); } + + +/** +Expand the array to accommodate a specified number of key-value pairs. +If the set already has enough space for the specified number of elements, no +action is taken. Any elements already in the set are retained. + +@param aCount The number of key-value pairs for which space should be allocated. +@leave KErrNoMemory if sufficient memory could not be allocated. +*/ + inline void ReserveL(TInt aCount) + { RHashTableBase::ReserveL(aCount); } + + }; + + +/** +@publishedAll +@released + +A templated class which allows iteration over the elements of a RHashMap +class. + +The array being iterated over may not be modified while an iteration is in progress +or the iteration operations may malfunction or panic. + +@see RHashMap +*/ +template +class THashMapIter : public THashTableIterBase + { +private: + + struct SFullElement + { + TUint32 iHash; + K iK; + V iV; + }; + +public: + +/** +Construct an iterator over the specified associative array. +The iterator starts at conceptual position one before the beginning of the list +being iterated. + +@param aMap The array to be iterated over. +*/ + inline THashMapIter(const RHashMap& aMap) + : THashTableIterBase(aMap) + {} + + +/** +Reset the iterator to its initial state. + +@param aSet The set to be iterated over. +*/ + inline void Reset() + { THashTableIterBase::Reset(); } + + +/** +Return the key corresponding to the current position of the iterator. + +@return A pointer to the key object corresponding to the current position of the + iterator. + NULL if the iterator has just been constructed or reset, or if it has + previously reached the end of an iteration. +*/ + inline const K* CurrentKey() const + { return (const K*)THashTableIterBase::Current(_FOFF(SFullElement,iK)); } + + +/** +Steps the iterator to the next position and returns the corresponding key. + +@return A pointer to the key object corresponding to the next position of the + iterator. + NULL if the iterator has exhausted all the available key-value pairs. +*/ + inline const K* NextKey() + { return (const K*)THashTableIterBase::Next(_FOFF(SFullElement,iK)); } + + +/** +Return the value corresponding to the current position of the iterator. + +@return A pointer to the value object corresponding to the current position of the + iterator. + NULL if the iterator has just been constructed or reset, or if it has + previously reached the end of an iteration. +*/ + inline V* CurrentValue() + { return (V*)THashTableIterBase::Current(_FOFF(SFullElement,iV)); } + + +/** +Steps the iterator to the next position and returns the corresponding value. + +@return A pointer to the value object corresponding to the next position of the + iterator. + NULL if the iterator has exhausted all the available key-value pairs. +*/ + inline const V* NextValue() + { return (const V*)THashTableIterBase::Next(_FOFF(SFullElement,iV)); } + + +/** +Removes the element at the current iterator position from the hash table. +If the iterator does not currently point to a valid element, no action is taken. +Note that the iterator position is not altered so it no longer points to a valid +element following the Remove(). It is illegal to call either CurrentKey() or +CurrentValue() on the iterator after calling Remove() - the only legal +operations are Reset(), NextKey() or NextValue(). + +*/ + inline void RemoveCurrent() + { THashTableIterBase::RemoveCurrent(); } + }; + + + +template class TPtrHashMapIter; + +/** +@publishedAll +@released + +A templated class which implements an associative array with key type K and value type V, +using a probe-sequence hash table. Neither the key nor value objects are copied into the +table when they are added - only pointers are stored. + +*/ +template +class RPtrHashMap : public RHashTableBase + { +private: + friend class TPtrHashMapIter; + + struct SFullElement + { + TUint32 iHash; + K* iK; + V* iV; + }; +public: + +/** +A class which allows iteration over the elements of a RPtrHashMap class. + +The array being iterated over may not be modified while an iteration is in progress +or the iteration operations may malfunction or panic. + +@see TPtrHashMapIter +*/ + typedef TPtrHashMapIter TIter; + +/** +Construct an associative array of key-value pairs of type (K,V) using a +specified hash function and identity relation. +The array initially contains no key-value pairs. + +@param aHash The hash function used to hash the key objects of type K. +@param aIdentity The identity relation used to determine if two key objects + of type K should be considered identical. +*/ + inline RPtrHashMap(const THashFunction32& aHash, const TIdentityRelation& aIdentity) + : RHashTableBase(aHash, aIdentity, sizeof(SFullElement), 0) + {} + + +/** +Construct an associative array of key-value pairs of type (K,V) using a +default hash function and identity relation. +The array initially contains no key-value pairs. +*/ + inline RPtrHashMap() + : RHashTableBase(Defaults::Hash(), Defaults::Id(), sizeof(SFullElement), 0) + {} + + +/** +Free all memory used by this array. +Returns the array to the same state it had following construction. +*/ + inline void Close() + { RHashTableBase::Close(); } + + +/** +Look up a specified key in the associative array and return a pointer to the +corresponding value. + +@param aKey The key object of type K to look up. +@return A pointer to corresponding value object if the specified key + object was found. The value object may not be modified via + this pointer. + NULL if the specified key object was not found. +*/ + inline const V* Find(const K& aKey) const + { return (const V*)RHashTableBase::Find(&aKey, -_FOFF(SFullElement,iV)); } + + +/** +Look up a specified key in the associative array and return a pointer to the +corresponding value. + +@param aKey The key object of type K to look up. +@return A reference to corresponding value object if the specified key + object was found. The value object may not be modified via + this reference. +@leave KErrNotFound if the specified key object was not found. +*/ + inline const V& FindL(const K& aKey) const + { return *(const V*)RHashTableBase::FindL(&aKey, -_FOFF(SFullElement,iV)); } + + +/** +Look up a specified key in the associative array and return a pointer to the +corresponding value. + +@param aKey The key object of type K to look up. +@return A pointer to corresponding value object if the specified key + object was found. The value object may be modified via + this pointer. + NULL if the specified key object was not found. +*/ + inline V* Find(const K& aKey) + { return (V*)RHashTableBase::Find(&aKey, -_FOFF(SFullElement,iV)); } + + +/** +Look up a specified key in the associative array and return a pointer to the +corresponding value. + +@param aKey The key object of type K to look up. +@return A reference to corresponding value object if the specified key + object was found. The value object may be modified via + this reference. +@leave KErrNotFound if the specified key object was not found. +*/ + inline V& FindL(const K& aKey) + { return *(V*)RHashTableBase::FindL(&aKey, -_FOFF(SFullElement,iV)); } + + +/** +Insert a key-value pair into the array. + +If the specified key object is not found in the array, a pointer to the +key object along with a pointer to the value object are added to the array +and KErrNone is returned. +If the specified key object is found in the array, the existing pointers +to both the key and value objects are replaced by the provided pointers +and KErrNone is returned. +In both cases only pointers are stored in the array - the objects themselves +are not copied. + +@param aKey A pointer to the key object of type K to add to the array. +@param aValue A pointer to the value object of type V to associate with aKey. +@return KErrNone if the key-value pair was added successfully. + KErrNoMemory if memory could not be allocated to store + the pointers aKey and aValue. +*/ + inline TInt Insert(const K* aKey, const V* aValue) + { return RHashTableBase::PtrInsert(aKey, aValue); } + + +/** +Insert a key-value pair into the array. + +If the specified key object is not found in the array, a pointer to the +key object along with a pointer to the value object are added to the array +and KErrNone is returned. +If the specified key object is found in the array, the existing pointers +to both the key and value objects are replaced by the provided pointers +and KErrNone is returned. +In both cases only pointers are stored in the array - the objects themselves +are not copied. + +@param aKey A pointer to the key object of type K to add to the array. +@param aValue A pointer to the value object of type V to associate with aKey. +@leave KErrNoMemory if memory could not be allocated to store the pointers aKey and aValue. +*/ + inline void InsertL(const K* aKey, const V* aValue) + { RHashTableBase::PtrInsertL(aKey, aValue); } + + +/** +Remove a key-value pair from the array. + +@param aKey A pointer to the key to be removed. +@return KErrNone if the pointers to the key object and corresponding + value object were removed successfully. + KErrNotFound if the key object was not present in the array. +*/ + inline TInt Remove(const K* aKey) + { return RHashTableBase::Remove(aKey); } + + +/** +Query the number of key-value pairs in the array. + +@return The number of key-value pairs currently in the array. +*/ + inline TInt Count() const + { return RHashTableBase::Count(); } + + +/** +Expand the array to accommodate a specified number of key-value pairs. +If the set already has enough space for the specified number of elements, no +action is taken. Any elements already in the set are retained. + +@param aCount The number of key-value pairs for which space should be allocated. +@return KErrNone if the operation completed successfully. +@return KErrNoMemory if sufficient memory could not be allocated. +*/ + inline TInt Reserve(TInt aCount) + { return RHashTableBase::Reserve(aCount); } + + +/** +Expand the array to accommodate a specified number of key-value pairs. +If the set already has enough space for the specified number of elements, no +action is taken. Any elements already in the set are retained. + +@param aCount The number of key-value pairs for which space should be allocated. +@leave KErrNoMemory if sufficient memory could not be allocated. +*/ + inline void ReserveL(TInt aCount) + { RHashTableBase::ReserveL(aCount); } + + + void ResetAndDestroy(); + }; + + +/** +@publishedAll +@released + +A templated class which allows iteration over the elements of a RPtrHashMap +class. + +The array being iterated over may not be modified while an iteration is in progress +or the iteration operations may malfunction or panic. + +@see RPtrHashMap +*/ +template +class TPtrHashMapIter : public THashTableIterBase + { +private: + + struct SFullElement + { + TUint32 iHash; + K* iK; + V* iV; + }; +public: + +/** +Construct an iterator over the specified associative array. +The iterator starts at conceptual position one before the beginning of the list +being iterated. + +@param aMap The array to be iterated over. +*/ + inline TPtrHashMapIter(const RPtrHashMap& aMap) + : THashTableIterBase(aMap) + {} + + +/** +Reset the iterator to its initial state. + +@param aSet The set to be iterated over. +*/ + inline void Reset() + { THashTableIterBase::Reset(); } + + +/** +Return the key corresponding to the current position of the iterator. + +@return A pointer to the key object corresponding to the current position of the + iterator. + NULL if the iterator has just been constructed or reset, or if it has + previously reached the end of an iteration. +*/ + inline const K* CurrentKey() const + { return (const K*)THashTableIterBase::Current(-_FOFF(SFullElement,iK)); } + + +/** +Steps the iterator to the next position and returns the corresponding key. + +@return A pointer to the key object corresponding to the next position of the + iterator. + NULL if the iterator has exhausted all the available key-value pairs. +*/ + inline const K* NextKey() + { return (const K*)THashTableIterBase::Next(-_FOFF(SFullElement,iK)); } + + +/** +Return the value corresponding to the current position of the iterator. + +@return A pointer to the value object corresponding to the current position of the + iterator. + NULL if the iterator has just been constructed or reset, or if it has + previously reached the end of an iteration. +*/ + inline const V* CurrentValue() const + { return (const V*)THashTableIterBase::Current(-_FOFF(SFullElement,iV)); } + + +/** +Steps the iterator to the next position and returns the corresponding value. + +@return A pointer to the value object corresponding to the next position of the + iterator. + NULL if the iterator has exhausted all the available key-value pairs. +*/ + inline const V* NextValue() + { return (const V*)THashTableIterBase::Next(-_FOFF(SFullElement,iV)); } + + +/** +Removes the element at the current iterator position from the hash table. +If the iterator does not currently point to a valid element, no action is taken. +Note that the iterator position is not altered so it no longer points to a valid +element following the Remove(). It is illegal to call either CurrentKey() or +CurrentValue() on the iterator after calling Remove() - the only legal +operations are Reset(), NextKey() or NextValue(). + +*/ + inline void RemoveCurrent() + { THashTableIterBase::RemoveCurrent(); } + }; + + + +/** +Deletes all the objects of type T to which pointers are stored in this set. +Then frees all the memory used by the set and returns the set to the same state +as immediately following construction. +*/ +template +void RPtrHashSet::ResetAndDestroy() + { + TPtrHashSetIter iter(*this); + T* p; + do { + p = (T*)iter.Next(); + delete p; + } while(p); + Close(); + } + + +/** +Deletes all the key objects of type K and corresponding value objects of type V +to which pointers are stored in this array. +Then frees all the memory used by the array and returns the array to the same +state as immediately following construction. +*/ +template +void RPtrHashMap::ResetAndDestroy() + { + TPtrHashMapIter iter(*this); + K* p; + V* q; + do { + p = (K*)iter.NextKey(); + q = (V*)iter.CurrentValue(); + delete p; + delete q; + } while(p); + Close(); + } + + +#endif