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

     2 // All rights reserved.

     3 // This component and the accompanying materials are made available

     4 // under the terms of the License "Symbian Foundation License v1.0"

     5 // which accompanies this distribution, and is available

     6 // at the URL "http://www.symbianfoundation.org/legal/sfl-v10.html".

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 // e32/include/e32hashtab.h

    15 // 

    16 //

    17 

    18 #ifndef __E32HASHTAB_H__

    19 #define __E32HASHTAB_H__

    20 #include <e32cmn.h>

    21 

    22 /**

    23 @publishedAll

    24 @released

    25 

    26 Defines a function type used by a THashFunction32 object. 

    27 

    28 A function of this type implements an algorithm for producing a 32 bit hash

    29 value from a key.

    30 

    31 @see THashFunction32

    32 */

    33 typedef TUint32 (*TGeneralHashFunction32)(const TAny*);

    34 

    35 

    36 /**

    37 @publishedAll

    38 @released

    39 

    40 A templated class which packages a function that calculates a 32 bit hash

    41 value from a key of templated type.

    42 

    43 A THashFunction32<T> object is constructed and passed as a parameter to 

    44 member functions of the hash table classes RHashSet<T>, RPtrHashSet<T>,

    45 RHashMap<T,V> and RPtrHashMap<T,V>.

    46 

    47 @see RHashSet

    48 @see RPtrHashSet

    49 @see RHashMap

    50 @see RPtrHashMap

    51 */

    52 template <class T>

    53 class THashFunction32

    54 	{

    55 public:

    56 	inline THashFunction32( TUint32 (*aHashFunc)(const T&) )

    57 		{ iHashFunction = (TGeneralHashFunction32)aHashFunc; }

    58 	inline operator TGeneralHashFunction32() const

    59 		{ return iHashFunction; }

    60 	inline TUint32 Hash(const T& aKey) const

    61 		{ return (*iHashFunction)(&aKey); }

    62 private:

    63 	TGeneralHashFunction32 iHashFunction;

    64 	};

    65 

    66 

    67 /**

    68 @publishedAll

    69 @released

    70 

    71 A set of common hashing functions for frequently occurring types.

    72 

    73 @see RHashSet

    74 @see RPtrHashSet

    75 @see RHashMap

    76 @see RPtrHashMap

    77 */

    78 class DefaultHash

    79 	{

    80 public:

    81 	IMPORT_C static TUint32 Integer(const TInt&);

    82 	IMPORT_C static TUint32 Des8(const TDesC8&);

    83 	IMPORT_C static TUint32 Des16(const TDesC16&);

    84 	IMPORT_C static TUint32 IntegerPtr(TInt* const &);

    85 	IMPORT_C static TUint32 Des8Ptr(TDesC8* const &);

    86 	IMPORT_C static TUint32 Des16Ptr(TDesC16* const &);

    87 	};

    88 

    89 

    90 

    91 class THashTableIterBase;

    92 

    93 /**

    94 @internalComponent

    95 

    96 Base class used in the derivation of RHashSet<T>, RPtrHashSet<T>,

    97 RHashMap<K,V> and RPtrHashMap<K,V>.

    98 

    99 This class provides a general hash table implementation using probe sequences

   100 generated by pseudo-double hashing.

   101 The class is internal and is not intended for use.

   102 */

   103 class RHashTableBase

   104 	{

   105 public:

   106 	enum TDefaultSpecifier

   107 		{

   108 		EDefaultSpecifier_Normal,

   109 		};

   110 

   111 protected:

   112 	template<class K, TDefaultSpecifier S>

   113 	class Defaults

   114 		{

   115 	public:

   116 		inline static TGeneralHashFunction32 Hash();

   117 		inline static TGeneralIdentityRelation Id();

   118 		};

   119 

   120 protected:

   121 	enum TElementState

   122 		{

   123 		EEmpty=0,		// entry is vacant

   124 		EDeleted=1,		// entry has been deleted

   125 		EGen0=2,		// entry is occupied, generation number 0

   126 		EGen1=3,		// entry is occupied, generation number 1

   127 		EStateMask=3,

   128 		EOccupiedMask=2,

   129 		};

   130 

   131 	struct SElement

   132 		{

   133 		inline void SetEmpty() {iHash=EEmpty;}

   134 		inline void SetDeleted() {iHash=EDeleted;}

   135 		inline TBool IsEmpty() const {return (iHash&EStateMask)==EEmpty;}

   136 		inline TBool IsDeleted() const {return (iHash&EStateMask)==EDeleted;}

   137 		inline TBool IsEmptyOrDeleted() const {return !(iHash&EOccupiedMask);}

   138 

   139 		TUint32	iHash;			// bits 2-31 = 30 bit hash value, bits 0,1 = state

   140 		};

   141 

   142 protected:

   143 	IMPORT_C RHashTableBase(TGeneralHashFunction32, TGeneralIdentityRelation, TInt aElementSize, TInt aKeyOffset);

   144 	IMPORT_C void Close();

   145 	IMPORT_C TAny* Find(const TAny* aKey, TInt aOffset=0) const;

   146 	IMPORT_C TAny* FindL(const TAny* aKey, TInt aOffset=0) const;

   147 	TInt Insert(const TAny* aKey, TAny*& aElement);

   148 	IMPORT_C TInt PtrInsert(const TAny* aKey, const TAny* aValue);

   149 	IMPORT_C void PtrInsertL(const TAny* aKey, const TAny* aValue);

   150 	IMPORT_C TInt ValueInsert(const TAny* aKey, TInt aKeySize, const TAny* aValue, TInt aValueOffset, TInt aValueSize);

   151 	IMPORT_C void ValueInsertL(const TAny* aKey, TInt aKeySize, const TAny* aValue, TInt aValueOffset, TInt aValueSize);

   152 	IMPORT_C TInt Remove(const TAny* aKey);

   153 	IMPORT_C TInt Count() const;

   154 	IMPORT_C TInt Reserve(TInt aCount);

   155 	IMPORT_C void ReserveL(TInt aCount);

   156 	IMPORT_C void ConsistencyCheck(TUint32* aDeleted=0, TUint32* aComparisons=0, TUint32 aChainLimit=0, TUint32* aChainInfo=0);

   157 private:

   158 	void SetThresholds();

   159 	TInt ExpandTable(TInt aNewIndexBits);

   160 	void ShrinkTable();

   161 	void ReformTable(TUint aNewIndexBits);

   162 	void VerifyReform();

   163 private:

   164 	inline SElement* Element(TInt aIndex)

   165 		{return (SElement*)(((TUint8*)iElements) + aIndex*iElementSize);}

   166 	inline const SElement* ElementC(TInt aIndex) const

   167 		{return (const SElement*)(((TUint8*)iElements) + aIndex*iElementSize);}

   168 	inline TAny* GetKey(const SElement* aElement) const

   169 		{return iKeyOffset ? ((TUint8*)aElement + iKeyOffset) : (TAny*)((TUint32*)aElement)[1];}

   170 private:

   171 	TGeneralHashFunction32 iHashFunc;	// generates the hash from a given key

   172 	TGeneralIdentityRelation iIdFunc;	// compare two keys for equality

   173 	TUint8 iIndexBits;					// number of bits used to index the table

   174 	TUint8 iGeneration;					// 2 or 3, generation number used when traversing entire table

   175 	TUint8 iKeyOffset;					// offset to key

   176 	TUint8 iPad0;

   177 	TAny* iElements;

   178 	TUint32 iCount;						// number of valid entries

   179 	TUint32 iEmptyCount;				// number of empty entries

   180 	TUint32 iLowerThreshold;			// shrink if count drops below this

   181 	TUint32 iUpperThreshold;			// expand if count rises above this

   182 	TUint32 iCleanThreshold;			// clean table if count of empty entries falls below this

   183 	TInt iElementSize;

   184 	TInt iPad1;							// expansion room

   185 	TInt iPad2;

   186 

   187 	friend struct RHashTableBase::SElement;

   188 	friend class THashTableIterBase;

   189 	friend class HashTest;

   190 	};

   191 

   192 

   193 /**

   194 @internalComponent

   195 */

   196 TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TInt*, RHashTableBase::EDefaultSpecifier_Normal>

   197 	{

   198 public:

   199 	inline static TGeneralHashFunction32 Hash();

   200 	inline static TGeneralIdentityRelation Id();

   201 	};

   202 

   203 /**

   204 @internalComponent

   205 */

   206 inline TGeneralHashFunction32 RHashTableBase::Defaults<TInt*, RHashTableBase::EDefaultSpecifier_Normal>::Hash()

   207 	{return (TGeneralHashFunction32)&DefaultHash::IntegerPtr;}

   208 

   209 /**

   210 @internalComponent

   211 */

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

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

   214 

   215 /**

   216 @internalComponent

   217 */

   218 TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TInt32*, RHashTableBase::EDefaultSpecifier_Normal>

   219 	{

   220 public:

   221 	inline static TGeneralHashFunction32 Hash();

   222 	inline static TGeneralIdentityRelation Id();

   223 	};

   224 

   225 /**

   226 @internalComponent

   227 */

   228 inline TGeneralHashFunction32 RHashTableBase::Defaults<TInt32*, RHashTableBase::EDefaultSpecifier_Normal>::Hash()

   229 	{return (TGeneralHashFunction32)&DefaultHash::IntegerPtr;}

   230 

   231 /**

   232 @internalComponent

   233 */

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

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

   236 

   237 /**

   238 @internalComponent

   239 */

   240 TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TUint*, RHashTableBase::EDefaultSpecifier_Normal>

   241 	{

   242 public:

   243 	inline static TGeneralHashFunction32 Hash();

   244 	inline static TGeneralIdentityRelation Id();

   245 	};

   246 /**

   247 @internalComponent

   248 */

   249 inline TGeneralHashFunction32 RHashTableBase::Defaults<TUint*, RHashTableBase::EDefaultSpecifier_Normal>::Hash()

   250 	{return (TGeneralHashFunction32)&DefaultHash::IntegerPtr;}

   251 

   252 /**

   253 @internalComponent

   254 */

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

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

   257 

   258 

   259 /**

   260 @internalComponent

   261 */

   262 TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TUint32*, RHashTableBase::EDefaultSpecifier_Normal>

   263 	{

   264 public:

   265 	inline static TGeneralHashFunction32 Hash();

   266 	inline static TGeneralIdentityRelation Id();

   267 	};

   268 /**

   269 @internalComponent

   270 */

   271 inline TGeneralHashFunction32 RHashTableBase::Defaults<TUint32*, RHashTableBase::EDefaultSpecifier_Normal>::Hash()

   272 	{return (TGeneralHashFunction32)&DefaultHash::IntegerPtr;}

   273 

   274 /**

   275 @internalComponent

   276 */

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

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

   279 

   280 /**

   281 @internalComponent

   282 */

   283 TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TDesC8*, RHashTableBase::EDefaultSpecifier_Normal>

   284 	{

   285 public:

   286 	inline static TGeneralHashFunction32 Hash();

   287 	inline static TGeneralIdentityRelation Id();

   288 	};

   289 /**

   290 @internalComponent

   291 */

   292 inline TGeneralHashFunction32 RHashTableBase::Defaults<TDesC8*, RHashTableBase::EDefaultSpecifier_Normal>::Hash()

   293 	{return (TGeneralHashFunction32)&DefaultHash::Des8Ptr;}

   294 

   295 /**

   296 @internalComponent

   297 */

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

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

   300 

   301 /**

   302 @internalComponent

   303 */

   304 TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TDesC16*, RHashTableBase::EDefaultSpecifier_Normal>

   305 	{

   306 public:

   307 	inline static TGeneralHashFunction32 Hash();

   308 	inline static TGeneralIdentityRelation Id();

   309 	};

   310 /**

   311 @internalComponent

   312 */

   313 inline TGeneralHashFunction32 RHashTableBase::Defaults<TDesC16*, RHashTableBase::EDefaultSpecifier_Normal>::Hash()

   314 	{return (TGeneralHashFunction32)&DefaultHash::Des16Ptr;}

   315 

   316 /**

   317 @internalComponent

   318 */

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

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

   321 

   322 /**

   323 @internalComponent

   324 */

   325 TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TInt, RHashTableBase::EDefaultSpecifier_Normal>

   326 	{

   327 public:

   328 	inline static TGeneralHashFunction32 Hash();

   329 	inline static TGeneralIdentityRelation Id();

   330 	};

   331 

   332 /**

   333 @internalComponent

   334 */

   335 inline TGeneralHashFunction32 RHashTableBase::Defaults<TInt, RHashTableBase::EDefaultSpecifier_Normal>::Hash()

   336 	{return (TGeneralHashFunction32)&DefaultHash::Integer;}

   337 

   338 /**

   339 @internalComponent

   340 */

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

   342 	{return (TGeneralIdentityRelation)&DefaultIdentity::Integer;}

   343 

   344 /**

   345 @internalComponent

   346 */

   347 TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TInt32, RHashTableBase::EDefaultSpecifier_Normal>

   348 	{

   349 public:

   350 	inline static TGeneralHashFunction32 Hash();

   351 	inline static TGeneralIdentityRelation Id();

   352 	};

   353 

   354 /**

   355 @internalComponent

   356 */

   357 inline TGeneralHashFunction32 RHashTableBase::Defaults<TInt32, RHashTableBase::EDefaultSpecifier_Normal>::Hash()

   358 	{return (TGeneralHashFunction32)&DefaultHash::Integer;}

   359 

   360 /**

   361 @internalComponent

   362 */

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

   364 	{return (TGeneralIdentityRelation)&DefaultIdentity::Integer;}

   365 

   366 /**

   367 @internalComponent

   368 */

   369 TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TUint, RHashTableBase::EDefaultSpecifier_Normal>

   370 	{

   371 public:

   372 	inline static TGeneralHashFunction32 Hash();

   373 	inline static TGeneralIdentityRelation Id();

   374 	};

   375 

   376 /**

   377 @internalComponent

   378 */

   379 inline TGeneralHashFunction32 RHashTableBase::Defaults<TUint, RHashTableBase::EDefaultSpecifier_Normal>::Hash()

   380 	{return (TGeneralHashFunction32)&DefaultHash::Integer;}

   381 

   382 /**

   383 @internalComponent

   384 */

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

   386 	{return (TGeneralIdentityRelation)&DefaultIdentity::Integer;}

   387 

   388 

   389 /**

   390 @internalComponent

   391 */

   392 TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TUint32, RHashTableBase::EDefaultSpecifier_Normal>

   393 	{

   394 public:

   395 	inline static TGeneralHashFunction32 Hash();

   396 	inline static TGeneralIdentityRelation Id();

   397 	};

   398 

   399 /**

   400 @internalComponent

   401 */

   402 inline TGeneralHashFunction32 RHashTableBase::Defaults<TUint32, RHashTableBase::EDefaultSpecifier_Normal>::Hash()

   403 	{return (TGeneralHashFunction32)&DefaultHash::Integer;}

   404 

   405 /**

   406 @internalComponent

   407 */

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

   409 	{return (TGeneralIdentityRelation)&DefaultIdentity::Integer;}

   410 

   411 

   412 /**

   413 @internalComponent

   414 */

   415 TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TDesC8, RHashTableBase::EDefaultSpecifier_Normal>

   416 	{

   417 public:

   418 	inline static TGeneralHashFunction32 Hash();

   419 	inline static TGeneralIdentityRelation Id();

   420 	};

   421 

   422 /**

   423 @internalComponent

   424 */

   425 inline TGeneralHashFunction32 RHashTableBase::Defaults<TDesC8, RHashTableBase::EDefaultSpecifier_Normal>::Hash()

   426 	{return (TGeneralHashFunction32)&DefaultHash::Des8;}

   427 

   428 /**

   429 @internalComponent

   430 */

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

   432 	{return (TGeneralIdentityRelation)&DefaultIdentity::Des8;}

   433 

   434 

   435 /**

   436 @internalComponent

   437 */

   438 TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TDesC16, RHashTableBase::EDefaultSpecifier_Normal>

   439 	{

   440 public:

   441 	inline static TGeneralHashFunction32 Hash();

   442 	inline static TGeneralIdentityRelation Id();

   443 	};

   444 

   445 /**

   446 @internalComponent

   447 */

   448 inline TGeneralHashFunction32 RHashTableBase::Defaults<TDesC16, RHashTableBase::EDefaultSpecifier_Normal>::Hash()

   449 	{return (TGeneralHashFunction32)&DefaultHash::Des16;}

   450 

   451 /**

   452 @internalComponent

   453 */

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

   455 	{return (TGeneralIdentityRelation)&DefaultIdentity::Des16;}

   456 

   457 

   458 

   459 

   460 /**

   461 @internalComponent

   462 

   463 Base class used in the derivation of THashSetIter<T>, TPtrHashSetIter<T>,

   464 THashMapIter<K,V> and TPtrHashMapIter<K,V>.

   465 

   466 This class provides iteration capability for the hash table classes derived

   467 from RHashTableBase.

   468 The class is internal and is not intended for use.

   469 */

   470 class THashTableIterBase

   471 	{

   472 protected:

   473 	IMPORT_C THashTableIterBase(const RHashTableBase& aTable);

   474 	IMPORT_C void Reset();

   475 	IMPORT_C const TAny* Next(TInt aOffset=0);

   476 	IMPORT_C const TAny* Current(TInt aOffset=0) const;

   477 	IMPORT_C void RemoveCurrent();

   478 private:

   479 	const RHashTableBase& iTbl;

   480 	TInt iIndex;

   481 	TInt iPad1;							// expansion room

   482 	TInt iPad2;

   483 	};

   484 

   485 

   486 

   487 template <class T> class THashSetIter;

   488 

   489 /**

   490 @publishedAll

   491 @released

   492 

   493 A templated class which implements an unordered extensional set of objects of

   494 type T using a probe-sequence hash table. The objects are copied into the set

   495 when they are added. A bitwise binary copy is used here, so the type T must

   496 not implement a nontrivial copy constructor.

   497 

   498 */

   499 template <class T>

   500 class RHashSet : public RHashTableBase

   501 	{

   502 private:

   503 	friend class THashSetIter<T>;

   504 	

   505 	struct SFullElement

   506 		{

   507 		TUint32 iHash;

   508 		T iT;

   509 		};

   510 

   511 public:

   512 

   513 /**

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

   515 

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

   517 or the iteration operations may malfunction or panic.

   518 

   519 @see THashSetIter<T>

   520 */

   521 	typedef THashSetIter<T> TIter;

   522 	

   523 /**

   524 Construct a set of objects of type T using a specified hash function and identity relation.

   525 The set is initially empty.

   526 

   527 @param	aHash		The hash function used to hash the objects of type T.

   528 @param	aIdentity	The identity relation used to determine if two objects of type T

   529 					should be considered identical.

   530 */

   531 	inline RHashSet(const THashFunction32<T>& aHash, const TIdentityRelation<T>& aIdentity)

   532 		:	RHashTableBase(aHash, aIdentity, sizeof(SFullElement), _FOFF(SFullElement,iT))

   533 		{}

   534 

   535 

   536 /**

   537 Construct a set of objects of type T using a default hash function and identity relation.

   538 The set is initially empty.

   539 */

   540 	inline RHashSet()

   541 		:	RHashTableBase(Defaults<T,EDefaultSpecifier_Normal>::Hash(), Defaults<T,EDefaultSpecifier_Normal>::Id(), sizeof(SFullElement), _FOFF(SFullElement,iT))

   542 		{}

   543 

   544 

   545 /**

   546 Free all memory used by this set.

   547 Returns the set to the same state it had following construction.

   548 */

   549 	inline void Close()

   550 		{ RHashTableBase::Close(); }

   551 

   552 

   553 /**

   554 Locate a specified element in the set.

   555 

   556 @param	aKey	The object of type T to search for.

   557 @return			A pointer to the copy of the specified object in the set, if it

   558 				exists. The object may not be modified via this pointer.

   559 				NULL if the specified object is not a member of this set.

   560 */

   561 	inline const T* Find(const T& aKey) const

   562 		{ return (const T*)RHashTableBase::Find(&aKey, _FOFF(SFullElement,iT)); }

   563 

   564 

   565 /**

   566 Locate a specified element in the set.

   567 

   568 @param	aKey	The object of type T to search for.

   569 @return			A reference to the copy of the specified object in the set, if it

   570 				exists. The object may not be modified via this reference.

   571 @leave			KErrNotFound if the specified object is not a member of this set.

   572 */

   573 	inline const T& FindL(const T& aKey) const

   574 		{ return *(const T*)RHashTableBase::FindL(&aKey, _FOFF(SFullElement,iT)); }

   575 

   576 

   577 /**

   578 Locate a specified element in the set.

   579 

   580 @param	aKey	The object of type T to search for.

   581 @return			A pointer to the copy of the specified object in the set, if it

   582 				exists. The object may be modified via this pointer. Care should

   583 				be taken not to modify any parts of the object which are used by

   584 				either the hash function or the identity relation for this set.

   585 				If this is done the set may become inconsistent, resulting in

   586 				malfunctions and/or panics at a later time.

   587 				NULL if the specified object is not a member of this set.

   588 */

   589 	inline T* Find(const T& aKey)

   590 		{ return (T*)RHashTableBase::Find(&aKey, _FOFF(SFullElement,iT)); }

   591 

   592 

   593 /**

   594 Locate a specified element in the set.

   595 

   596 @param	aKey	The object of type T to search for.

   597 @return			A reference to the copy of the specified object in the set, if it

   598 				exists. The object may be modified via this reference. Care should

   599 				be taken not to modify any parts of the object which are used by

   600 				either the hash function or the identity relation for this set.

   601 				If this is done the set may become inconsistent, resulting in

   602 				malfunctions and/or panics at a later time.

   603 @leave			KErrNotFound if the specified object is not a member of this set.

   604 */

   605 	inline T& FindL(const T& aKey)

   606 		{ return *(T*)RHashTableBase::FindL(&aKey, _FOFF(SFullElement,iT)); }

   607 

   608 

   609 /**

   610 Insert an element into the set.

   611 

   612 If the specified object is not currently a member of the set, a copy of the

   613 object is added to the set and KErrNone is returned.

   614 If the specified object is currently a member of the set, the existing copy

   615 of the object is replaced by the provided object and KErrNone is

   616 returned.

   617 In both cases the object is copied bitwise into the set.

   618 

   619 @param	aKey	The object of type T to add to the set.

   620 @return			KErrNone if the object was added successfully.

   621 				KErrNoMemory if memory could not be allocated to store

   622 					the copy of aKey.

   623 */

   624 	inline TInt Insert(const T& aKey)

   625 		{ return RHashTableBase::ValueInsert(&aKey, sizeof(T), 0, 0, 0); }

   626 

   627 

   628 /**

   629 Insert an element into the set.

   630 

   631 If the specified object is not currently a member of the set, a copy of the

   632 object is added to the set and KErrNone is returned.

   633 If the specified object is currently a member of the set, the existing copy

   634 of the object is replaced by the provided object and KErrNone is

   635 returned.

   636 In both cases the object is copied bitwise into the set.

   637 

   638 @param	aKey	The object of type T to add to the set.

   639 @leave			KErrNoMemory if memory could not be allocated to store

   640 					the copy of aKey.

   641 */

   642 	inline void InsertL(const T& aKey)

   643 		{ RHashTableBase::ValueInsertL(&aKey, sizeof(T), 0, 0, 0); }

   644 

   645 

   646 /**

   647 Remove an element from the set.

   648 

   649 @param	aKey	The object to be removed.

   650 @return			KErrNone if the object was removed successfully.

   651 				KErrNotFound if the object was not present in the set.

   652 */

   653 	inline TInt Remove(const T& aKey)

   654 		{ return RHashTableBase::Remove(&aKey); }

   655 

   656 

   657 /**

   658 Query the number of elements in the set.

   659 

   660 @return	The number of elements currently in the set.

   661 */

   662 	inline TInt Count() const

   663 		{ return RHashTableBase::Count(); }

   664 

   665 

   666 /**

   667 Expand the set to accommodate a specified number of elements.

   668 If the set already has enough space for the specified number of elements, no

   669 action is taken. Any elements already in the set are retained.

   670 

   671 @param	aCount	The number of elements for which space should be allocated.

   672 @return	KErrNone if the operation completed successfully.

   673 @return	KErrNoMemory if sufficient memory could not be allocated.

   674 */

   675 	inline TInt Reserve(TInt aCount)

   676 		{ return RHashTableBase::Reserve(aCount); }

   677 

   678 

   679 /**

   680 Expand the set to accommodate a specified number of elements.

   681 If the set already has enough space for the specified number of elements, no

   682 action is taken. Any elements already in the set are retained.

   683 

   684 @param	aCount	The number of elements for which space should be allocated.

   685 @leave	KErrNoMemory if sufficient memory could not be allocated.

   686 */

   687 	inline void ReserveL(TInt aCount)

   688 		{ RHashTableBase::ReserveL(aCount); }

   689 

   690 	};

   691 

   692 

   693 /**

   694 @publishedAll

   695 @released

   696 

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

   698 class.

   699 

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

   701 or the iteration operations may malfunction or panic.

   702 

   703 @see RHashSet<T>

   704 */

   705 template <class T>

   706 class THashSetIter : public THashTableIterBase

   707 	{

   708 private:

   709 	

   710 	struct SFullElement

   711 		{

   712 		TUint32 iHash;

   713 		T iT;

   714 		};

   715 

   716 public:

   717 

   718 /**

   719 Construct an iterator over the specified set.

   720 The iterator starts at conceptual position one before the beginning of the list

   721 being iterated.

   722 

   723 @param	aSet	The set to be iterated over.

   724 */

   725 	inline THashSetIter(const RHashSet<T>& aSet)

   726 		:	THashTableIterBase(aSet)

   727 		{}

   728 

   729 

   730 /**

   731 Reset the iterator to its initial state.

   732 

   733 @param	aSet	The set to be iterated over.

   734 */

   735 	inline void Reset()

   736 		{ THashTableIterBase::Reset(); }

   737 

   738 

   739 /**

   740 Return the current position of the iterator.

   741 

   742 @return	A pointer to the set member corresponding to the current position of the

   743 		iterator.

   744 		NULL if the iterator has just been constructed or reset, or if it has

   745 		previously reached the end of an iteration.

   746 */

   747 	inline const T* Current() const

   748 		{ return (const T*)THashTableIterBase::Current(_FOFF(SFullElement,iT)); }

   749 

   750 

   751 /**

   752 Steps the iterator to the next position.

   753 

   754 @return	A pointer to the set member corresponding to the next position of the

   755 		iterator.

   756 		NULL if the iterator has exhausted all the available set elements.

   757 */

   758 	inline const T* Next()

   759 		{ return (const T*)THashTableIterBase::Next(_FOFF(SFullElement,iT)); }

   760 

   761 

   762 /**

   763 Removes the element at the current iterator position from the hash table.

   764 If the iterator does not currently point to a valid element, no action is taken.

   765 Note that the iterator position is not altered so it no longer points to a valid

   766 element following the Remove(). It is illegal to call Current() on the iterator

   767 after calling Remove() - the only legal operations are Reset() and Next().

   768 

   769 */

   770 	inline void RemoveCurrent()

   771 		{ THashTableIterBase::RemoveCurrent(); }

   772 	};

   773 

   774 

   775 

   776 template <class T> class TPtrHashSetIter;

   777 

   778 /**

   779 @publishedAll

   780 @released

   781 

   782 A templated class which implements an unordered extensional set of objects of

   783 type T using a probe-sequence hash table. The objects are not copied into the set

   784 when they are added; rather the set stores pointers to the contained objects.

   785 

   786 */

   787 template <class T>

   788 class RPtrHashSet : public RHashTableBase

   789 	{

   790 private:

   791 	friend class TPtrHashSetIter<T>;

   792 	

   793 	struct SFullElement

   794 		{

   795 		TUint32 iHash;

   796 		T* iT;

   797 		};

   798 

   799 public:

   800 

   801 /**

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

   803 

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

   805 or the iteration operations may malfunction or panic.

   806 

   807 @see TPtrHashSetIter<T>

   808 */

   809 	typedef TPtrHashSetIter<T> TIter;

   810 

   811 /**

   812 Construct a set of objects of type T using a specified hash function and identity relation.

   813 The set is initially empty.

   814 

   815 @param	aHash		The hash function used to hash the objects of type T.

   816 @param	aIdentity	The identity relation used to determine if two objects of type T

   817 					should be considered identical.

   818 */

   819 	inline RPtrHashSet(const THashFunction32<T>& aHash, const TIdentityRelation<T>& aIdentity)

   820 		:	RHashTableBase(aHash, aIdentity, sizeof(SFullElement), 0)

   821 		{}

   822 

   823 

   824 /**

   825 Construct a set of objects of type T using a default hash function and identity relation.

   826 The set is initially empty.

   827 */

   828 	inline RPtrHashSet()

   829 		:	RHashTableBase(Defaults<T,EDefaultSpecifier_Normal>::Hash(), Defaults<T,EDefaultSpecifier_Normal>::Id(), sizeof(SFullElement), 0)

   830 		{}

   831 

   832 

   833 /**

   834 Free all memory used by this set.

   835 Returns the set to the same state it had following construction.

   836 */

   837 	inline void Close()

   838 		{ RHashTableBase::Close(); }

   839 

   840 

   841 /**

   842 Locate a specified element in the set.

   843 

   844 @param	aKey	The object of type T to search for.

   845 @return			A pointer to the specified object, if it is in the set.

   846 				The object may not be modified via this pointer.

   847 				NULL if the specified object is not a member of this set.

   848 */

   849 	inline const T* Find(const T& aKey) const

   850 		{ return (const T*)RHashTableBase::Find(&aKey, -_FOFF(SFullElement,iT)); }

   851 

   852 

   853 /**

   854 Locate a specified element in the set.

   855 

   856 @param	aKey	The object of type T to search for.

   857 @return			A reference to the specified object, if it is in the set.

   858 				The object may not be modified via this reference.

   859 @leave	KErrNotFound if the specified object is not a member of this set.

   860 */

   861 	inline const T& FindL(const T& aKey) const

   862 		{ return *(const T*)RHashTableBase::FindL(&aKey, -_FOFF(SFullElement,iT)); }

   863 

   864 

   865 /**

   866 Locate a specified element in the set.

   867 

   868 @param	aKey	The object of type T to search for.

   869 @return			A pointer to the specified object, if it is in the set.

   870 				The object may be modified via this pointer. Care should

   871 				be taken not to modify any parts of the object which are used by

   872 				either the hash function or the identity relation for this set.

   873 				If this is done the set may become inconsistent, resulting in

   874 				malfunctions and/or panics at a later time.

   875 				NULL if the specified object is not a member of this set.

   876 */

   877 	inline T* Find(const T& aKey)

   878 		{ return (T*)RHashTableBase::Find(&aKey, -_FOFF(SFullElement,iT)); }

   879 

   880 

   881 /**

   882 Locate a specified element in the set.

   883 

   884 @param	aKey	The object of type T to search for.

   885 @return			A reference to the specified object, if it is in the set.

   886 				The object may be modified via this reference. Care should

   887 				be taken not to modify any parts of the object which are used by

   888 				either the hash function or the identity relation for this set.

   889 				If this is done the set may become inconsistent, resulting in

   890 				malfunctions and/or panics at a later time.

   891 @leave	KErrNotFound if the specified object is not a member of this set.

   892 */

   893 	inline T& FindL(const T& aKey)

   894 		{ return *(T*)RHashTableBase::FindL(&aKey, -_FOFF(SFullElement,iT)); }

   895 

   896 

   897 /**

   898 Insert an element into the set.

   899 

   900 If the specified object is not currently a member of the set, a pointer to the

   901 object is added to the set and KErrNone is returned.

   902 If the specified object is currently a member of the set, the existing pointer

   903 to the object is replaced by the provided pointer and KErrNone is

   904 returned.

   905 In both cases only a pointer to the object is stored - the object is never copied.

   906 

   907 @param	aKey	A pointer to the object of type T to add to the set.

   908 @return			KErrNone if the object was added successfully.

   909 				KErrNoMemory if memory could not be allocated to store

   910 					the pointer to the new object.

   911 */

   912 	inline TInt Insert(const T* aKey)

   913 		{ return RHashTableBase::PtrInsert(aKey, 0); }

   914 

   915 

   916 /**

   917 Insert an element into the set.

   918 

   919 If the specified object is not currently a member of the set, a pointer to the

   920 object is added to the set and KErrNone is returned.

   921 If the specified object is currently a member of the set, the existing pointer

   922 to the object is replaced by the provided pointer and KErrNone is

   923 returned.

   924 In both cases only a pointer to the object is stored - the object is never copied.

   925 

   926 @param	aKey	A pointer to the object of type T to add to the set.

   927 @leave	KErrNoMemory if memory could not be allocated to store the pointer to the new object.

   928 */

   929 	inline void InsertL(const T* aKey)

   930 		{ RHashTableBase::PtrInsertL(aKey, 0); }

   931 

   932 

   933 /**

   934 Remove an element from the set.

   935 

   936 @param	aKey	A pointer to the object to be removed.

   937 @return			KErrNone if the object was removed successfully.

   938 				KErrNotFound if the object was not present in the set.

   939 */

   940 	inline TInt Remove(const T* aKey)

   941 		{ return RHashTableBase::Remove(aKey); }

   942 

   943 

   944 /**

   945 Query the number of elements in the set.

   946 

   947 @return	The number of elements currently in the set.

   948 */

   949 	inline TInt Count() const

   950 		{ return RHashTableBase::Count(); }

   951 

   952 

   953 /**

   954 Expand the set to accommodate a specified number of elements.

   955 If the set already has enough space for the specified number of elements, no

   956 action is taken. Any elements already in the set are retained.

   957 

   958 @param	aCount	The number of elements for which space should be allocated.

   959 @return	KErrNone if the operation completed successfully.

   960 @return	KErrNoMemory if sufficient memory could not be allocated.

   961 */

   962 	inline TInt Reserve(TInt aCount)

   963 		{ return RHashTableBase::Reserve(aCount); }

   964 

   965 

   966 /**

   967 Expand the set to accommodate a specified number of elements.

   968 If the set already has enough space for the specified number of elements, no

   969 action is taken. Any elements already in the set are retained.

   970 

   971 @param	aCount	The number of elements for which space should be allocated.

   972 @leave	KErrNoMemory if sufficient memory could not be allocated.

   973 */

   974 	inline void ReserveL(TInt aCount)

   975 		{ RHashTableBase::ReserveL(aCount); }

   976 

   977 

   978 	void ResetAndDestroy();

   979 	};

   980 

   981 

   982 /**

   983 @publishedAll

   984 @released

   985 

   986 A templated class which allows iteration over the elements of a RPtrHashSet<T>

   987 class.

   988 

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

   990 or the iteration operations may malfunction or panic.

   991 

   992 @see RPtrHashSet<T>

   993 */

   994 template <class T>

   995 class TPtrHashSetIter : public THashTableIterBase

   996 	{

   997 private:

   998 	

   999 	struct SFullElement		

  1000 		{

  1001 		TUint32 iHash;

  1002 		T* iT;

  1003 		};

  1004 

  1005 public:

  1006 

  1007 /**

  1008 Construct an iterator over the specified set.

  1009 The iterator starts at conceptual position one before the beginning of the list

  1010 being iterated.

  1011 

  1012 @param	aSet	The set to be iterated over.

  1013 */

  1014 	inline TPtrHashSetIter(const RPtrHashSet<T>& aSet)

  1015 		:	THashTableIterBase(aSet)

  1016 		{}

  1017 

  1018 

  1019 /**

  1020 Reset the iterator to its initial state.

  1021 

  1022 @param	aSet	The set to be iterated over.

  1023 */

  1024 	inline void Reset()

  1025 		{ THashTableIterBase::Reset(); }

  1026 

  1027 

  1028 /**

  1029 Return the current position of the iterator.

  1030 

  1031 @return	A pointer to the set member corresponding to the current position of the

  1032 		iterator.

  1033 		NULL if the iterator has just been constructed or reset, or if it has

  1034 		previously reached the end of an iteration.

  1035 */

  1036 	inline const T* Current() const

  1037 		{ return (const T*)THashTableIterBase::Current(-_FOFF(SFullElement,iT)); }

  1038 

  1039 

  1040 /**

  1041 Steps the iterator to the next position.

  1042 

  1043 @return	A pointer to the set member corresponding to the next position of the

  1044 		iterator.

  1045 		NULL if the iterator has exhausted all the available set elements.

  1046 */

  1047 	inline const T* Next()

  1048 		{ return (const T*)THashTableIterBase::Next(-_FOFF(SFullElement,iT)); }

  1049 

  1050 

  1051 /**

  1052 Removes the element at the current iterator position from the hash table.

  1053 If the iterator does not currently point to a valid element, no action is taken.

  1054 Note that the iterator position is not altered so it no longer points to a valid

  1055 element following the Remove(). It is illegal to call Current() on the iterator

  1056 after calling Remove() - the only legal operations are Reset() and Next().

  1057 

  1058 */

  1059 	inline void RemoveCurrent()

  1060 		{ THashTableIterBase::RemoveCurrent(); }

  1061 	};

  1062 

  1063 

  1064 

  1065 template <class K, class V> class THashMapIter;

  1066 

  1067 /**

  1068 @publishedAll

  1069 @released

  1070 

  1071 A templated class which implements an associative array with key type K and value type V,

  1072 using a probe-sequence hash table. Both the key and value objects are copied into the

  1073 table when they are added. A bitwise binary copy is used here, so neither of the types

  1074 K and V may implement a nontrivial copy constructor.

  1075 

  1076 */

  1077 template <class K, class V>

  1078 class RHashMap : public RHashTableBase

  1079 	{

  1080 private:

  1081 	friend class THashMapIter<K,V>;

  1082 	

  1083 	struct SFullElement

  1084 		{

  1085 		TUint32 iHash;

  1086 		K iK;

  1087 		V iV;

  1088 		};

  1089 

  1090 public:

  1091 

  1092 /**

  1093 A class which allows iteration over the elements of a RHashMap<K,V> class.

  1094 

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

  1096 or the iteration operations may malfunction or panic.

  1097 

  1098 @see THashMapIter<K,V>

  1099 */

  1100 	typedef THashMapIter<K,V> TIter;

  1101 

  1102 /**

  1103 Construct an associative array of key-value pairs of type (K,V) using a

  1104 specified hash function and identity relation.

  1105 The array initially contains no key-value pairs.

  1106 

  1107 @param	aHash		The hash function used to hash the key objects of type K.

  1108 @param	aIdentity	The identity relation used to determine if two key objects

  1109 					of type K should be considered identical.

  1110 */

  1111 	inline RHashMap(const THashFunction32<K>& aHash, const TIdentityRelation<K>& aIdentity)

  1112 		:	RHashTableBase(aHash, aIdentity, sizeof(SFullElement), _FOFF(SFullElement,iK))

  1113 		{}

  1114 

  1115 

  1116 /**

  1117 Construct an associative array of key-value pairs of type (K,V) using a

  1118 default hash function and identity relation.

  1119 The array initially contains no key-value pairs.

  1120 */

  1121 	inline RHashMap()

  1122 		:	RHashTableBase(Defaults<K,EDefaultSpecifier_Normal>::Hash(), Defaults<K,EDefaultSpecifier_Normal>::Id(), sizeof(SFullElement), _FOFF(SFullElement,iK))

  1123 		{}

  1124 

  1125 

  1126 /**

  1127 Free all memory used by this array.

  1128 Returns the array to the same state it had following construction.

  1129 */

  1130 	inline void Close()

  1131 		{ RHashTableBase::Close(); }

  1132 

  1133 

  1134 /**