Symaptic: os/kernelhwsrv/kerneltest/e32test/buffer/t

     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 "Eclipse Public License v1.0"

     5 // which accompanies this distribution, and is available

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

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 // e32test/buffer/t_hashtab.cpp

    15 //

    16 //

    18 #include <e32test.h>

    19 #include <e32hashtab.h>

    20 #include <hal.h>

    22 #if defined(__VC32__) || defined(__CW32__)

    23 typedef unsigned short wch;

    24 #else

    25 typedef wchar_t wch;

    26 #endif

    29 RTest test(_L("T_HASHTAB"));

    30 TInt NanoTickPeriod;

    32 typedef TBuf8<80> TTestName;

    33 typedef RHashSet<TInt> TIntSet;

    34 typedef RHashSet<TTestName> TNameSet;

    35 typedef RPtrHashSet<TDesC8> TStringSet8;

    36 typedef RPtrHashSet<TDesC16> TStringSet16;

    37 typedef RPtrHashMap<TDesC8,TDesC8> TStringMap8;

    38 typedef RPtrHashMap<TDesC16,TDesC16> TStringMap16;

    40 #define INTSET(x)	TIntSet x

    41 #define NAMESET(x)	TNameSet x(&HashTestName, &TestNameIdentity)

    42 #define STRSET8(x)	TStringSet8 x

    43 #define STRSET16(x)	TStringSet16 x

    44 #define STRMAP8(x)	TStringMap8 x

    45 #define STRMAP16(x)	TStringMap16 x

    47 RPointerArray<TDesC8> DesC8Array;

    48 RPointerArray<TDesC16> DesC16Array;

    50 class HashTest : public RHashTableBase

    51 	{

    52 public:

    53 	HashTest() : RHashTableBase(0,0,0,0) {}

    54 	using RHashTableBase::ConsistencyCheck;

    55 	using RHashTableBase::Count;

    56 	};

    58 void CCheck(RHashTableBase& aHT)

    59 	{

    60 	TUint32 ci[1024];

    61 	TUint32 dc;

    62 	TUint32 cmp;

    63 	HashTest* h = (HashTest*)&aHT;

    64 	h->ConsistencyCheck(&dc, &cmp, 1024, ci);

    65 	test.Printf(_L("Count = %d, Deleted = %d, Cmp = %d\n"), h->Count(), dc, cmp);

    66 	TInt i;

    67 	for (i=0; i<1024; ++i)

    68 		{

    69 		if (ci[i])

    70 			test.Printf(_L("%d chains of length %d\n"), ci[i], i);

    71 		}

    72 	}

    74 const char* Numbers[] =

    75 	{

    76 	"zero",

    77 	"one",

    78 	"two",

    79 	"three",

    80 	"four",

    81 	"five",

    82 	"six",

    83 	"seven",

    84 	"eight",

    85 	"nine",

    86 	"ten",

    87 	"eleven",

    88 	"twelve",

    89 	"thirteen",

    90 	"fourteen",

    91 	"fifteen",

    92 	"sixteen",

    93 	"seventeen",

    94 	"eighteen",

    95 	"nineteen",

    96 	"twenty",

    97 	"thirty",

    98 	"forty",

    99 	"fifty",

   100 	"sixty",

   101 	"seventy",

   102 	"eighty",

   103 	"ninety",

   104 	"hundred",

   105 	"thousand"

   106 	};

   108 TTestName NumberInWords(const TInt& aNum)

   109 	{

   110 	TInt a = aNum;

   111 	TTestName n;

   112 	if (a<20)

   113 		{

   114 		n.Copy((const TUint8*)Numbers[a]);

   115 		return n;

   116 		}

   117 	if (a<100)

   118 		{

   119 		TInt tens = a/10;

   120 		TInt units = a%10;

   121 		n.Copy((const TUint8*)Numbers[tens-2+20]);

   122 		if (units)

   123 			{

   124 			n.Append(' ');

   125 			n.Append(TPtrC8((const TUint8*)Numbers[units]));

   126 			}

   127 		return n;

   128 		}

   129 	if (a<1000)

   130 		{

   131 		TInt h = a/100;

   132 		n.Copy((const TUint8*)Numbers[h]);

   133 		n.Append(' ');

   134 		n.Append(TPtrC8((const TUint8*)Numbers[28]));

   135 		a%=100;

   136 		if (a)

   137 			{

   138 			TTestName n2(NumberInWords(a));

   139 			n.Append(_L8(" and "));

   140 			n+=n2;

   141 			}

   142 		return n;

   143 		}

   144 	TInt t = a/1000;

   145 	n = NumberInWords(t);

   146 	n.Append(' ');

   147 	n.Append(TPtrC8((const TUint8*)Numbers[29]));

   148 	a%=1000;

   149 	if (a)

   150 		{

   151 		TTestName n2(NumberInWords(a));

   152 		if (a<100)

   153 			n.Append(_L8(" and "));

   154 		else

   155 			n.Append(' ');

   156 		n+=n2;

   157 		}

   158 	return n;

   159 	}

   161 void PrintNumberInWords(TInt a)

   162 	{

   163 	TBuf<256> buf;

   164 	TTestName n(NumberInWords(a));

   165 	buf.Copy(n);

   166 	test.Printf(_L("%d: %S\n"), a, &buf);

   167 	}

   169 TUint32 HashTestName(const TTestName& aN)

   170 	{

   171 	return DefaultHash::Des8(aN);

   172 	}

   174 TBool TestNameIdentity(const TTestName& aA, const TTestName& aB)

   175 	{

   176 	return aA == aB;

   177 	}

   179 /******************************************************************************

   180  * Utility functions for RHashSet<T>

   181  ******************************************************************************/

   182 template <class T>

   183 void Union(RHashSet<T>& aD, const RHashSet<T>& aS)

   184 	{

   185 	TInt c = aS.Count();

   186 	TInt c2 = c;

   187 	TInt d0 = aD.Count();

   188 	TInt d1 = d0;

   189 	typename RHashSet<T>::TIter iS(aS);

   190 	FOREVER

   191 		{

   192 		const T* p = iS.Next();

   193 		if (!p)

   194 			break;

   195 		--c2;

   196 		TInt r = aD.Insert(*p);

   197 		test(r==KErrNone);

   198 		++d1;

   199 		}

   200 	test(d1 == aD.Count());

   201 	test(c2 == 0);

   202 	}

   204 template <class T>

   205 void Subtract(RHashSet<T>& aD, const RHashSet<T>& aS)

   206 	{

   207 	TInt c = aS.Count();

   208 	TInt c2 = c;

   209 	TInt d0 = aD.Count();

   210 	TInt d1 = d0;

   211 	TInt nfd = 0;

   212 	typename RHashSet<T>::TIter iS(aS);

   213 	FOREVER

   214 		{

   215 		const T* p = iS.Next();

   216 		if (!p)

   217 			break;

   218 		--c2;

   219 		TInt r = aD.Remove(*p);

   220 		test(r==KErrNone || r==KErrNotFound);

   221 		if (r==KErrNotFound)

   222 			++nfd;

   223 		else

   224 			--d1;

   225 		}

   226 	test(d1 == aD.Count());

   227 	test(c2 == 0);

   228 	test( (d0-d1) + nfd == c);

   229 	}

   231 template <class T>

   232 void Intersect(RHashSet<T>& aD, const RHashSet<T>& aS)

   233 	{

   234 	typename RHashSet<T>::TIter iD(aD);

   235 	FOREVER

   236 		{

   237 		const T* p = iD.Next();

   238 		if (!p)

   239 			break;

   240 		if (!aS.Find(*p))

   241 			iD.RemoveCurrent();

   242 		}

   243 	}

   245 template <class T>

   246 void CheckIdentical(const RHashSet<T>& aA, const RHashSet<T>& aB)

   247 	{

   248 	test(aA.Count()==aB.Count());

   249 	TInt c = aA.Count();

   250 	typename RHashSet<T>::TIter iA(aA);

   251 	FOREVER

   252 		{

   253 		const T* p = iA.Next();

   254 		if (!p)

   255 			break;

   256 		--c;

   257 		test(aB.Find(*p)!=0);

   258 		}

   259 	test(c==0);

   260 	c = aA.Count();

   261 	typename RHashSet<T>::TIter iB(aB);

   262 	FOREVER

   263 		{

   264 		const T* p = iB.Next();

   265 		if (!p)

   266 			break;

   267 		--c;

   268 		test(aA.Find(*p)!=0);

   269 		}

   270 	test(c==0);

   271 	}

   274 /******************************************************************************

   275  * Utility functions for RPtrHashSet<T>

   276  ******************************************************************************/

   277 template <class T>

   278 void Union(RPtrHashSet<T>& aD, const RPtrHashSet<T>& aS)

   279 	{

   280 	TInt c = aS.Count();

   281 	TInt c2 = c;

   282 	TInt d0 = aD.Count();

   283 	TInt d1 = d0;

   284 	typename RPtrHashSet<T>::TIter iS(aS);

   285 	FOREVER

   286 		{

   287 		const T* p = iS.Next();

   288 		if (!p)

   289 			break;

   290 		--c2;

   291 		TInt r = aD.Insert(p);

   292 		test(r==KErrNone);

   293 		++d1;

   294 		}

   295 	test(d1 == aD.Count());

   296 	test(c2 == 0);

   297 	}

   299 template <class T>

   300 void Subtract(RPtrHashSet<T>& aD, const RPtrHashSet<T>& aS)

   301 	{

   302 	TInt c = aS.Count();

   303 	TInt c2 = c;

   304 	TInt d0 = aD.Count();

   305 	TInt d1 = d0;

   306 	TInt nfd = 0;

   307 	typename RPtrHashSet<T>::TIter iS(aS);

   308 	FOREVER

   309 		{

   310 		const T* p = iS.Next();

   311 		if (!p)

   312 			break;

   313 		--c2;

   314 		TInt r = aD.Remove(p);

   315 		test(r==KErrNone || r==KErrNotFound);

   316 		if (r==KErrNotFound)

   317 			++nfd;

   318 		else

   319 			--d1;

   320 		}

   321 	test(d1 == aD.Count());

   322 	test(c2 == 0);

   323 	test( (d0-d1) + nfd == c);

   324 	}

   326 template <class T>

   327 void Intersect(RPtrHashSet<T>& aD, const RPtrHashSet<T>& aS)

   328 	{

   329 	typename RPtrHashSet<T>::TIter iD(aD);

   330 	FOREVER

   331 		{

   332 		const T* p = iD.Next();

   333 		if (!p)

   334 			break;

   335 		if (!aS.Find(*p))

   336 			iD.RemoveCurrent();

   337 		}

   338 	}

   340 template <class T>

   341 void CheckIdentical(const RPtrHashSet<T>& aA, const RPtrHashSet<T>& aB)

   342 	{

   343 	test(aA.Count()==aB.Count());

   344 	TInt c = aA.Count();

   345 	typename RPtrHashSet<T>::TIter iA(aA);

   346 	FOREVER

   347 		{

   348 		const T* p = iA.Next();

   349 		if (!p)

   350 			break;

   351 		--c;

   352 		test(aB.Find(*p)!=0);

   353 		}

   354 	test(c==0);

   355 	c = aA.Count();

   356 	typename RPtrHashSet<T>::TIter iB(aB);

   357 	FOREVER

   358 		{

   359 		const T* p = iB.Next();

   360 		if (!p)

   361 			break;

   362 		--c;

   363 		test(aA.Find(*p)!=0);

   364 		}

   365 	test(c==0);

   366 	}

   369 /******************************************************************************

   370  * Utility functions for RHashMap<K,V>

   371  ******************************************************************************/

   372 template <class K, class V>

   373 void UnionTransform(RHashMap<K,V>& aD, const RHashSet<K>& aS, V (*aTransform)(const K&) )

   374 	{

   375 	TInt c = aS.Count();

   376 	TInt c2 = c;

   377 	TInt d0 = aD.Count();

   378 	TInt d1 = d0;

   379 	typename RHashSet<K>::TIter iS(aS);

   380 	FOREVER

   381 		{

   382 		const K* p = iS.Next();

   383 		if (!p)

   384 			break;

   385 		--c2;

   386 		TInt r = aD.Insert(*p, (*aTransform)(*p) );

   387 		test(r==KErrNone);

   388 		++d1;

   389 		}

   390 	test(d1 == aD.Count());

   391 	test(c2 == 0);

   392 	}

   395 template <class K, class V>

   396 void UnionMap(RHashSet<V>& aD, const RHashSet<K>& aS, const RHashMap<K,V>& aM)

   397 	{

   398 	TInt c = aS.Count();

   399 	TInt c2 = c;

   400 	TInt d0 = aD.Count();

   401 	TInt d1 = d0;

   402 	typename RHashSet<K>::TIter iS(aS);

   403 	FOREVER

   404 		{

   405 		const K* p = iS.Next();

   406 		if (!p)

   407 			break;

   408 		--c2;

   409 		const V* q = aM.Find(*p);

   410 		if (!q)

   411 			continue;

   412 		TInt r = aD.Insert(*q);

   413 		test(r==KErrNone);

   414 		++d1;

   415 		}

   416 	test(d1 == aD.Count());

   417 	test(c2 == 0);

   418 	}

   421 template <class K, class V>

   422 void UnionKeys(RHashSet<K>& aD, const RHashMap<K,V>& aM)

   423 	{

   424 	typename RHashMap<K,V>::TIter iM(aM);

   425 	FOREVER

   426 		{

   427 		const K* p = iM.NextKey();

   428 		if (!p)

   429 			break;

   430 		aD.Insert(*p);

   431 		}

   432 	}

   435 template <class K, class V>

   436 void UnionValues(RHashSet<V>& aD, const RHashMap<K,V>& aM)

   437 	{

   438 	typename RHashMap<K,V>::TIter iM(aM);

   439 	FOREVER

   440 		{

   441 		const K* p = iM.NextKey();

   442 		if (!p)

   443 			break;

   444 		const V* q = iM.CurrentValue();

   445 		aD.Insert(*q);

   446 		}

   447 	}

   450 template <class K, class V>

   451 void UnionTransform(RHashMap<K,V>& aD, const RHashMap<K,V>& aS, V (*aTransform)(const V&) )

   452 	{

   453 	TInt c = aS.Count();

   454 	TInt c2 = c;

   455 	TInt d0 = aD.Count();

   456 	TInt d1 = d0;

   457 	typename RHashMap<K,V>::TIter iS(aS);

   458 	FOREVER

   459 		{

   460 		const K* p = iS.NextKey();

   461 		if (!p)

   462 			break;

   463 		--c2;

   464 		TInt r = aD.Insert(*p, (*aTransform)(*iS.CurrentValue()) );

   465 		test(r==KErrNone);

   466 		++d1;

   467 		}

   468 	test(d1 == aD.Count());

   469 	test(c2 == 0);

   470 	}

   473 template <class K, class V>

   474 void UnionInverse(RHashMap<V,K>& aD, const RHashMap<K,V>& aS)

   475 	{

   476 	TInt c = aS.Count();

   477 	TInt c2 = c;

   478 	TInt d0 = aD.Count();

   479 	TInt d1 = d0;

   480 	typename RHashMap<K,V>::TIter iS(aS);

   481 	FOREVER

   482 		{

   483 		const K* p = iS.NextKey();

   484 		if (!p)

   485 			break;

   486 		--c2;

   487 		const V* q = iS.CurrentValue();

   488 		TInt r = aD.Insert(*q, *p);

   489 		test(r==KErrNone);

   490 		++d1;

   491 		}

   492 	test(d1 == aD.Count());

   493 	test(c2 == 0);

   494 	}

   496 template <class K, class V>

   497 void SetMap(RHashMap<V,K>& aM, const V& aV)

   498 	{

   499 	typename RHashMap<K,V>::TIter iM(aM);

   500 	FOREVER

   501 		{

   502 		const K* p = iM.NextKey();

   503 		if (!p)

   504 			break;

   505 		V* q = iM.CurrentValue();

   506 		*q = aV;

   507 		test(*q == aV);

   508 		}

   509 	}

   512 /******************************************************************************

   513  * Utility functions for RPtrHashMap<K,V>

   514  ******************************************************************************/

   515 template <class K, class V>

   516 void UnionTransform(RPtrHashMap<K,V>& aD, const RPtrHashMap<K,V>& aS, V* (*aTransform)(const V*) )

   517 	{

   518 	TInt c = aS.Count();

   519 	TInt c2 = c;

   520 	TInt d0 = aD.Count();

   521 	TInt d1 = d0;

   522 	typename RPtrHashMap<K,V>::TIter iS(aS);

   523 	FOREVER

   524 		{

   525 		const K* p = iS.NextKey();

   526 		if (!p)

   527 			break;

   528 		--c2;

   529 		TInt r = aD.Insert(p, (*aTransform)(iS.CurrentValue()) );

   530 		test(r==KErrNone);

   531 		++d1;

   532 		}

   533 	test(d1 == aD.Count());

   534 	test(c2 == 0);

   535 	}

   538 template <class A, class B>

   539 void UnionInverse(RPtrHashMap<B,A>& aD, const RPtrHashMap<A,B>& a1)

   540 	{

   541 	typename RPtrHashMap<A,B>::TIter iter(a1);

   542 	const A* pA;

   543 	while ( (pA=iter.NextKey()) != 0 )

   544 		{

   545 		const B* pB = iter.CurrentValue();

   546 		TInt r = aD.Insert(pB, pA);

   547 		test(r==KErrNone);

   548 		}

   549 	}

   552 template <class A, class B, class C>

   553 void UnionCompose(RPtrHashMap<A,C>& aD, const RPtrHashMap<A,B>& a1, const RPtrHashMap<B,C>& a2)

   554 	{

   555 	typename RPtrHashMap<A,B>::TIter iter(a1);

   556 	const A* pA;

   557 	while ( (pA=iter.NextKey()) != 0 )

   558 		{

   559 		const B* pB = iter.CurrentValue();

   560 		const C* pC = a2.Find(*pB);

   561 		if (pC)

   562 			{

   563 			TInt r = aD.Insert(pA, pC);

   564 			test(r==KErrNone);

   565 			}

   566 		}

   567 	}

   570 template <class K, class V>

   571 void CheckIdenticalMaps(const RPtrHashMap<K,V>& aA, const RPtrHashMap<K,V>& aB)

   572 	{

   573 	test(aA.Count()==aB.Count());

   574 	TInt c = aA.Count();

   575 	const K* p;

   576 	const V* q;

   577 	typename RPtrHashMap<K,V>::TIter iA(aA);

   578 	while( (p=iA.NextKey()) != 0)

   579 		{

   580 		--c;

   581 		q = aB.Find(*p);

   582 		test(q && q==iA.CurrentValue());

   583 		}

   584 	test(c==0);

   585 	c = aB.Count();

   586 	typename RPtrHashMap<K,V>::TIter iB(aB);

   587 	while( (p=iB.NextKey()) != 0)

   588 		{

   589 		--c;

   590 		q = aA.Find(*p);

   591 		test(q && q==iB.CurrentValue());

   592 		}

   593 	test(c==0);

   594 	}

   600 /******************************************************************************

   601  * Tests of TIntSet

   602  ******************************************************************************/

   603 void Populate(TIntSet& aH, TInt aS, TInt aE, TInt aM)

   604 	{

   605 	TInt x = aS;

   606 	for (; x<=aE; x+=aM)

   607 		aH.Insert(x);

   608 	}

   610 void PrimeSieve(TIntSet& aH, TInt aStart, TInt aEnd)

   611 	{

   612 	TInt x;

   613 	TInt e = (aEnd&1) ? aEnd : aEnd-1;

   614 	TInt s = (aStart<2) ? 2 : aStart|1;

   615 	for (x=s; x<=e; ++x)

   616 		{

   617 //		test.Printf(_L("add %d\n"),x);

   618 		aH.Insert(x);

   619 		}

   620 	TInt m=2;

   621 	FOREVER

   622 		{

   623 		for (; m*m<=e && !aH.Find(m); ++m)

   624 			{}

   625 		if (m*m > e)

   626 			break;

   627 		for (x=m*2; x<=e; x+=m)

   628 			{

   629 //			test.Printf(_L("remove %d\n"),x);

   630 			aH.Remove(x);

   631 			}

   632 		++m;

   633 		}

   634 	}

   636 TBool IsPrime(TInt x)

   637 	{

   638 	if (x==2)

   639 		return ETrue;

   640 	if (!(x&1))

   641 		return EFalse;

   642 	TInt d;

   643 	for (d=3; d*d<=x; d+=2)

   644 		{

   645 		if (x%d==0)

   646 			return EFalse;

   647 		}

   648 	return ETrue;

   649 	}

   651 void CheckSieveOutput(TIntSet& aH)

   652 	{

   653 	RHashSet<TInt>::TIter iter(aH);

   654 	TInt min = KMaxTInt;

   655 	TInt max = KMinTInt;

   656 	TInt c = 0;

   657 	test.Printf(_L("%d elements:\n"),aH.Count());

   658 	FOREVER

   659 		{

   660 		const TInt* p = iter.Next();

   661 		if (!p)

   662 			break;

   663 		++c;

   664 		if (*p>max) max=*p;

   665 		if (*p<min) min=*p;

   666 //		test.Printf(_L("%d\n"),*p);

   667 		test(IsPrime(*p));

   668 		}

   669 	test(c==aH.Count());

   670 	TInt x;

   671 	if (min==2)

   672 		{

   673 		test(aH.Find(2)!=0);

   674 		min++;

   675 		}

   676 	for (x=min; x<=max; x+=2)

   677 		{

   678 		if (IsPrime(x))

   679 			test(aH.Find(x)!=0);

   680 		}

   681 	for (x=min; x<=max; x+=2)

   682 		{

   683 		if (IsPrime(x))

   684 			test(aH.Find(x)==&aH.FindL(x));

   685 		else

   686 			{

   687 			TRAPD(rr,aH.FindL(x));

   688 			test(rr==KErrNotFound);

   689 			}

   690 		}

   691 	}

   693 TUint32 CheckSmallHashSet(const TIntSet& aA)

   694 	{

   695 	TUint32 m = 0;

   696 	RHashSet<TInt>::TIter iter(aA);

   697 	FOREVER

   698 		{

   699 		const TInt* p = iter.Next();

   700 		if (!p)

   701 			break;

   702 		m |= (1<<*p);

   703 		}

   704 	return m;

   705 	}

   707 void AddToSmallHashSet(TIntSet& aA, TUint32 aMask)

   708 	{

   709 	CheckSmallHashSet(aA);

   710 	TInt i;

   711 	TInt r;

   712 	for (i=0; i<32; ++i)

   713 		{

   714 		if (aMask & (1<<i))

   715 			{

   716 			r = aA.Insert(i);

   717 			test(r==KErrNone);

   718 			}

   719 		}

   720 	}

   722 void RemoveFromSmallHashSet(TIntSet& aA, TUint32 aMask)

   723 	{

   724 	TUint32 m = CheckSmallHashSet(aA);

   725 	TInt i;

   726 	TInt r;

   727 	for (i=0; i<32; ++i)

   728 		{

   729 		if (aMask & (1<<i))

   730 			{

   731 			r = aA.Remove(i);

   732 			if (m & (1<<i))

   733 				test(r==KErrNone);

   734 			else

   735 				test(r==KErrNotFound);

   736 			}

   737 		}

   738 	}

   740 void TestHashSet()

   741 	{

   742 	test.Next(_L("Test RHashSet"));

   744 	INTSET(hs);

   745 	CCheck(hs);		// check consistency for empty table

   746 	INTSET(hs2);

   747 	INTSET(hs3);

   748 	PrimeSieve(hs, 1, 100);

   749 	CheckSieveOutput(hs);

   750 	test(hs.Reserve(1000)==KErrNone);

   751 	CCheck(hs);

   752 	CheckSieveOutput(hs);	// check that Reserve() preserves existing entries

   754 	INTSET(m1);

   755 	INTSET(m2);

   756 	INTSET(m3);

   757 	INTSET(m5);

   758 	INTSET(m7);

   759 	Populate(m1,2,100,1);

   760 	Populate(m2,4,100,2);

   761 	Populate(m3,6,100,3);

   762 	Populate(m5,10,100,5);

   763 	Populate(m7,14,100,7);

   764 	Union(hs3, m1);

   765 	Subtract(hs3, m2);

   766 	Subtract(hs3, m3);

   767 	Subtract(hs3, m5);

   768 	Subtract(hs3, m7);

   769 	CheckSieveOutput(hs3);

   770 	CheckIdentical(hs,hs3);

   771 	hs3.Close();

   772 	INTSET(cm2);

   773 	INTSET(cm3);

   774 	INTSET(cm5);

   775 	INTSET(cm7);

   776 	Union(cm2, m1);

   777 	Subtract(cm2, m2);

   778 	Union(cm3, m1);

   779 	Subtract(cm3, m3);

   780 	Union(cm5, m1);

   781 	Subtract(cm5, m5);

   782 	Union(cm7, m1);

   783 	Subtract(cm7, m7);

   784 	Union(hs3, m1);

   785 	Intersect(hs3, cm7);

   786 	Intersect(hs3, cm3);

   787 	Intersect(hs3, cm5);

   788 	Intersect(hs3, cm2);

   789 	CheckSieveOutput(hs3);

   790 	CheckIdentical(hs,hs3);

   791 	hs3.Close();

   794 	cm2.Close();

   795 	cm3.Close();

   796 	cm5.Close();

   797 	cm7.Close();

   798 	m1.Close();

   799 	m2.Close();

   800 	m3.Close();

   801 	m5.Close();

   802 	m7.Close();

   804 	PrimeSieve(hs2, 1, 1000);

   805 	CheckSieveOutput(hs2);

   806 	test(hs2.Reserve(1000)==KErrNone);

   807 	CCheck(hs2);

   808 	CheckSieveOutput(hs2);	// check that Reserve() preserves existing entries

   810 	PrimeSieve(hs, 100, 997);

   811 	CheckSieveOutput(hs);

   812 	CCheck(hs);

   813 	CheckIdentical(hs,hs2);

   815 	hs2.Close();

   816 	Union(hs2, hs);

   817 	CheckIdentical(hs,hs2);

   818 	CheckSieveOutput(hs2);

   820 	hs2.Close();

   821 	hs.Close();

   823 	test(CheckSmallHashSet(hs)==0);

   824 	AddToSmallHashSet(hs, 1);

   825 	test(CheckSmallHashSet(hs)==1);

   826 	AddToSmallHashSet(hs, 4);

   827 	test(CheckSmallHashSet(hs)==5);

   828 	AddToSmallHashSet(hs, 0x80000001);

   829 	test(CheckSmallHashSet(hs)==0x80000005);

   830 	AddToSmallHashSet(hs, 0x317217f8);

   831 	test(CheckSmallHashSet(hs)==0xb17217fd);

   832 	RemoveFromSmallHashSet(hs, 0x00000007);

   833 	test(CheckSmallHashSet(hs)==0xb17217f8);

   834 	RemoveFromSmallHashSet(hs, 0xffffffff);

   835 	test(CheckSmallHashSet(hs)==0);

   836 	hs.Close();

   837 	}

   839 void TestHashIter()

   840 	{

   841 	test.Next(_L("Test iterators"));

   843 	RHashSet<TInt> hs;		// empty

   844 	RHashSet<TInt>::TIter iter(hs);

   845 	test(iter.Next() == 0);

   846 	test(iter.Current() == 0);

   847 	iter.RemoveCurrent();

   848 	test(iter.Next() == 0);

   849 	test(iter.Current() == 0);

   851 	test(hs.Insert(1) == KErrNone);

   852 	test(hs.Insert(2) == KErrNone);

   853 	test(hs.Insert(3) == KErrNone);

   854 	iter.Reset();

   855 	TUint mask = 14;

   856 	TInt i;

   857 	for (i=0; i<3; ++i)

   858 		{

   859 		const TInt* p = iter.Next();

   860 		test(p!=0);

   861 		TInt x = *p;

   862 		test (x>=1 && x<=3 && (mask&(1<<x))!=0);

   863 		mask &= ~(1<<x);

   864 		}

   865 	test(iter.Next() == 0);

   866 	test(mask==0);

   867 	test(CheckSmallHashSet(hs)==0x0e);

   868 	test(hs.Insert(4) == KErrNone);

   869 	test(hs.Insert(5) == KErrNone);

   870 	test(hs.Insert(6) == KErrNone);

   871 	test(hs.Insert(7) == KErrNone);

   872 	test(CheckSmallHashSet(hs)==0xfe);

   873 	iter.Reset();

   874 	while(iter.Next())

   875 		{

   876 		if ((*iter.Current() & 1) == 0)

   877 			iter.RemoveCurrent();

   878 		}

   879 	test(CheckSmallHashSet(hs)==0xaa);

   880 	iter.Reset();

   881 	while(iter.Next())

   882 		{

   883 		iter.RemoveCurrent();

   884 		}

   885 	test(CheckSmallHashSet(hs)==0);

   886 	iter.Reset();

   887 	test(iter.Next() == 0);

   888 	test(iter.Current() == 0);

   889 	RHashSet<TInt> empty;

   890 	CheckIdentical(hs, empty);

   891 #ifdef _DEBUG

   892 	__UHEAP_FAILNEXT(1);

   893 	test(empty.Insert(1)==KErrNoMemory);

   894 	test(empty.Insert(1)==KErrNone);

   895 	empty.Close();

   896 	__UHEAP_FAILNEXT(1);

   897 	test(hs.Insert(1)==KErrNone);

   898 	hs.Close();

   899 	__UHEAP_FAILNEXT(1);

   900 	test(hs.Insert(1)==KErrNoMemory);

   901 #endif

   902 	hs.Close();

   903 	}

   905 void Print(const char* aTitle, const RHashMap<TInt,TTestName>& aM)

   906 	{

   907 	TBuf<256> buf;

   908 	buf.Copy(TPtrC8((const TUint8*)aTitle));

   909 	test.Printf(_L("%S\n"), &buf);

   910 	RHashMap<TInt,TTestName>::TIter iter(aM);

   911 	FOREVER

   912 		{

   913 		const TInt* p = iter.NextKey();

   914 		if (!p) break;

   915 		buf.Copy(*iter.CurrentValue());

   916 		test.Printf(_L("%d: %S\n"), *p, &buf);

   917 		}

   918 	}

   920 void Print(const char* aTitle, const RHashSet<TTestName>& aS)

   921 	{

   922 	TBuf<256> buf;

   923 	buf.Copy(TPtrC8((const TUint8*)aTitle));

   924 	test.Printf(_L("%S\n"), &buf);

   925 	RHashSet<TTestName>::TIter iter(aS);

   926 	FOREVER

   927 		{

   928 		if (!iter.Next())

   929 			break;

   930 		buf.Copy(*iter.Current());

   931 		test.Printf(_L("%S\n"), &buf);

   932 		}

   933 	}

   935 void TestHashMap()

   936 	{

   937 	test.Next(_L("Test RHashMap"));

   939 	RHashMap<TInt,TInt> ht;

   940 	CCheck(ht);		// check consistency for empty table

   941 	TInt x;

   942 	for (x=0; x<200; x++)

   943 		{

   944 		TInt r = ht.Insert(x*x, x);

   945 		test(r==KErrNone);

   946 		}

   947 	test(ht.Count()==200);

   949 	TInt z = 0;

   950 	TInt y;

   951 	for (x=0; x<40000; x++)

   952 		{

   953 		const TInt* e = ht.Find(x);

   954 		if (e)

   955 			{

   956 			const TInt& ee = ht.FindL(x);

   957 			test(&ee==e);

   958 			y = *e;

   959 //			test.Printf(_L("Find(%d) -> %d\n"), x, y);

   960 			test(x == z*z);

   961 			test(y == z);

   962 			++z;

   963 			}

   964 		else

   965 			{

   966 			TRAPD(rr, ht.FindL(x));

   967 			test(rr==KErrNotFound);

   968 			}

   969 		}

   970 	CCheck(ht);

   972 	for (x=0; x<200; x++)

   973 		{

   974 		TInt r = ht.Insert(x*x*x, x);

   975 		test(r==KErrNone);

   976 		}

   977 	test(ht.Count()==200*2-6);

   978 	CCheck(ht);

   980 	TInt sq = 0;

   981 	TInt cb = 0;

   982 	for (x=0; x<8000000; x++)

   983 		{

   984 		const TInt* e = ht.Find(x);

   985 		if (e)

   986 			{

   987 			const TInt& ee = ht.FindL(x);

   988 			test(&ee==e);

   989 			y = *e;

   990 //			test.Printf(_L("Find(%d) -> %d\n"), x, y);

   991 			if (x == cb*cb*cb)

   992 				{

   993 				test(y==cb);

   994 				++cb;

   995 				if (x == sq*sq)

   996 					++sq;

   997 				}

   998 			else if (x == sq*sq)

   999 				{

  1000 				test(y==sq);

  1001 				++sq;

  1002 				}

  1003 			}

  1004 		}

  1006 	for (x=0; x<200; x++)

  1007 		{

  1008 		TInt r = ht.Remove(x*x);

  1009 		test(r==KErrNone);

  1010 		}

  1011 	test(ht.Count()==200-6);

  1012 	CCheck(ht);

  1014 	cb = 2;

  1015 	for (x=2; x<8000000; x++)

  1016 		{

  1017 		const TInt* e = ht.Find(x);

  1018 		if (e)

  1019 			{

  1020 			const TInt& ee = ht.FindL(x);

  1021 			test(&ee==e);

  1022 			y = *e;

  1023 //			test.Printf(_L("Find(%d) -> %d\n"), x, y);

  1024 			if (cb == 4 || cb == 9 || cb == 16 || cb == 25) ++cb;

  1025 			test(x == cb*cb*cb);

  1026 			test(y == cb);

  1027 			++cb;

  1028 			}

  1029 		}

  1031 	SetMap<TInt,TInt>(ht, 17);

  1033 	ht.Close();

  1035 	PrintNumberInWords(2000);

  1036 	PrintNumberInWords(2001);

  1037 	PrintNumberInWords(131072);

  1038 	PrintNumberInWords(111111);

  1039 	PrintNumberInWords(524288);

  1041 	INTSET(all);

  1042 	Populate(all,0,1000,1);

  1043 	RHashMap<TInt,TTestName> to_words(&DefaultHash::Integer, &DefaultIdentity::Integer);

  1044 	UnionTransform<TInt,TTestName>(to_words, all, &NumberInWords);

  1045 	RHashMap<TTestName,TInt> from_words(&HashTestName, &TestNameIdentity);

  1046 	UnionInverse<TInt,TTestName>(from_words, to_words);

  1047 //	Print("TO WORDS:", to_words);

  1048 	INTSET(primes);

  1049 	PrimeSieve(primes, 1, 100);

  1050 //	Print("Primes 1-100", primes);

  1051 	RHashMap<TInt,TTestName> prime_map(&DefaultHash::Integer, &DefaultIdentity::Integer);

  1052 	UnionTransform<TInt,TTestName>(prime_map, primes, &NumberInWords);

  1053 //	Print("Prime map 1-100", prime_map);

  1054 	INTSET(pmkeys);

  1055 	UnionKeys<TInt,TTestName>(pmkeys, prime_map);

  1056 	NAMESET(pmval);

  1057 	NAMESET(pmval2);

  1058 	UnionValues<TInt,TTestName>(pmval, prime_map);

  1059 	CheckIdentical(pmkeys, primes);

  1060 	INTSET(pr2);

  1061 	UnionMap<TTestName,TInt>(pr2, pmval, from_words);

  1062 	CheckIdentical(pr2, primes);

  1063 	pr2.Close();

  1064 	Union(pmval2, pmval);

  1065 //	Print("pmval",pmval);

  1066 //	Print("pmval2",pmval2);

  1067 	CheckIdentical(pmval2, pmval);

  1068 	UnionMap<TTestName,TInt>(pr2, pmval2, from_words);

  1069 	CheckIdentical(pr2, primes);

  1071 	pr2.Close();

  1072 	pmval.Close();

  1073 	pmval2.Close();

  1074 	pmkeys.Close();

  1075 	prime_map.Close();

  1076 	primes.Close();

  1077 	all.Close();

  1079 	INTSET(m);

  1080 	Populate(all,2,1000,1);

  1082 	NAMESET(pr3);

  1083 	NAMESET(nm);

  1084 	UnionMap<TInt,TTestName>(pr3, all, to_words);

  1085 	all.Close();

  1086 	CCheck(pr3);

  1088 	Populate(m,4,1000,2);

  1089 	UnionMap<TInt,TTestName>(nm, m, to_words);

  1090 	m.Close();

  1091 	Subtract(pr3, nm);

  1092 	nm.Close();

  1094 	Populate(m,6,1000,3);

  1095 	UnionMap<TInt,TTestName>(nm, m, to_words);

  1096 	m.Close();

  1097 	Subtract(pr3, nm);

  1098 	nm.Close();

  1100 	Populate(m,10,1000,5);

  1101 	UnionMap<TInt,TTestName>(nm, m, to_words);

  1102 	m.Close();

  1103 	Subtract(pr3, nm);

  1104 	nm.Close();

  1106 	Populate(m,14,1000,7);

  1107 	UnionMap<TInt,TTestName>(nm, m, to_words);

  1108 	m.Close();

  1109 	Subtract(pr3, nm);

  1110 	nm.Close();

  1112 	Populate(m,22,1000,11);

  1113 	UnionMap<TInt,TTestName>(nm, m, to_words);

  1114 	m.Close();

  1115 	Subtract(pr3, nm);

  1116 	nm.Close();

  1118 	Populate(m,26,1000,13);

  1119 	UnionMap<TInt,TTestName>(nm, m, to_words);

  1120 	m.Close();

  1121 	Subtract(pr3, nm);

  1122 	nm.Close();

  1124 	Populate(m,34,1000,17);

  1125 	UnionMap<TInt,TTestName>(nm, m, to_words);

  1126 	m.Close();

  1127 	Subtract(pr3, nm);

  1128 	nm.Close();

  1130 	Populate(m,38,1000,19);

  1131 	UnionMap<TInt,TTestName>(nm, m, to_words);

  1132 	m.Close();

  1133 	Subtract(pr3, nm);

  1134 	nm.Close();

  1136 	Populate(m,46,1000,23);

  1137 	UnionMap<TInt,TTestName>(nm, m, to_words);

  1138 	m.Close();

  1139 	Subtract(pr3, nm);

  1140 	nm.Close();

  1142 	Populate(m,58,1000,29);

  1143 	UnionMap<TInt,TTestName>(nm, m, to_words);

  1144 	m.Close();

  1145 	Subtract(pr3, nm);

  1146 	nm.Close();

  1148 	Populate(m,62,1000,31);

  1149 	UnionMap<TInt,TTestName>(nm, m, to_words);

  1150 	m.Close();

  1151 	Subtract(pr3, nm);

  1152 	nm.Close();

  1154 //	Print("pr3",pr3);

  1155 	PrimeSieve(primes, 1, 1000);

  1156 	UnionMap<TInt,TTestName>(nm, primes, to_words);

  1157 	CheckIdentical(nm, pr3);

  1158 	CCheck(pr3);

  1159 	UnionMap<TTestName,TInt>(m, pr3, from_words);

  1160 	CheckIdentical(m, primes);

  1162 	m.Close();

  1163 	nm.Close();

  1164 	primes.Close();

  1165 	pr3.Close();

  1166 	from_words.Close();

  1167 	to_words.Close();

  1168 	}

  1170 void PopulateArray8(TInt aMax)

  1171 	{

  1172 	TInt i;

  1173 	for (i=0; i<aMax; ++i)

  1174 		{

  1175 		TTestName n(NumberInWords(i));

  1176 		HBufC8* p = n.Alloc();

  1177 		test(p!=0);

  1178 		TInt r = DesC8Array.Append(p);

  1179 		test(r==KErrNone);

  1180 		}

  1181 	}

  1183 void PopulateArray16(TInt aMax)

  1184 	{

  1185 	TInt i;

  1186 	for (i=0; i<aMax; ++i)

  1187 		{

  1188 		TTestName n(NumberInWords(i));

  1189 		TBuf<128> n16;

  1190 		n16.Copy(n);

  1191 		HBufC16* p = n16.Alloc();

  1192 		test(p!=0);

  1193 		TInt r = DesC16Array.Append(p);

  1194 		test(r==KErrNone);

  1195 		}

  1196 	}

  1198 TUint32 istrh8(const TDesC8* const & a)

  1199 	{

  1200 	return DefaultHash::Des8(*a);

  1201 	}

  1203 TBool istrid8(const TDesC8* const & aA, const TDesC8* const & aB)

  1204 	{

  1205 	return *aA == *aB;

  1206 	}

  1208 TUint32 istrh16(const TDesC16* const & a)

  1209 	{

  1210 	return DefaultHash::Des16(*a);

  1211 	}

  1213 TBool istrid16(const TDesC16* const & aA, const TDesC16* const & aB)

  1214 	{

  1215 	return *aA == *aB;

  1216 	}

  1218 void TestPtrHashSet()

  1219 	{

  1220 	test.Next(_L("Test RPtrHashSet"));

  1222 	STRSET8(s);

  1223 	CCheck(s);		// check consistency for empty table

  1224 	RHashMap<const TDesC8*, TInt> hm(&istrh8, &istrid8);

  1225 	RPtrHashSet<TDesC8>::TIter iter(s);

  1226 	const TDesC8* q;

  1227 	TInt i;

  1228 	for (i=0; i<4096; ++i)

  1229 		{

  1230 		TInt r = s.Insert(DesC8Array[i]);

  1231 		test(r==KErrNone);

  1232 		r = hm.Insert(DesC8Array[i], i);

  1233 		test(r==KErrNone);

  1234 		}

  1235 	CCheck(s);

  1236 	for (i=0; i<4100; ++i)

  1237 		{

  1238 		TTestName n(NumberInWords(i));

  1239 		const TDesC8* p = s.Find(n);

  1240 		if (i<4096)

  1241 			{

  1242 			const TDesC8& pp = s.FindL(n);

  1243 			test(p && *p==n && p==DesC8Array[i]);

  1244 			test(&pp == p);

  1245 			}

  1246 		else

  1247 			{

  1248 			test(!p);

  1249 			TRAPD(rr,s.FindL(n));

  1250 			test(rr==KErrNotFound);

  1251 			}

  1252 		}

  1253 	while((q=iter.Next())!=0)

  1254 		{

  1255 		const TInt* qi = hm.Find(q);

  1256 		test(qi!=0 && *qi>=0 && *qi<4096);

  1257 		test(DesC8Array[*qi]==q);

  1258 		}

  1259 	for (i=0; i<4100; i+=2)

  1260 		{

  1261 		TTestName n(NumberInWords(i));

  1262 		TInt r = s.Remove(&n);

  1263 		if (i<4096)

  1264 			test(r==KErrNone);

  1265 		else

  1266 			test(r==KErrNotFound);

  1267 		}

  1268 	test(s.Count()==2048);

  1269 	CCheck(s);

  1270 	for (i=0; i<4100; ++i)

  1271 		{

  1272 		TTestName n(NumberInWords(i));

  1273 		const TDesC8* p = s.Find(n);

  1274 		if (i<4096 && (i&1))

  1275 			test(p && *p==n && p==DesC8Array[i]);

  1276 		else

  1277 			test(!p);

  1278 		}

  1279 	iter.Reset();

  1280 	while((q=iter.Next())!=0)

  1281 		{

  1282 		const TInt* qi = hm.Find(q);

  1283 		test(qi!=0 && *qi>=0 && *qi<4096 && (*qi&1));

  1284 		test(DesC8Array[*qi]==q);

  1285 		}

  1286 	for (i=2; i<4096; i+=4)

  1287 		{

  1288 		TInt r = s.Insert(DesC8Array[i]);

  1289 		test(r==KErrNone);

  1290 		}

  1291 	test(s.Count()==3072);

  1292 	CCheck(s);

  1293 	for (i=0; i<4100; ++i)

  1294 		{

  1295 		TTestName n(NumberInWords(i));

  1296 		const TDesC8* p = s.Find(n);

  1297 		if (i<4096 && (i&3))

  1298 			test(p && *p==n && p==DesC8Array[i]);

  1299 		else

  1300 			test(!p);

  1301 		}

  1302 	iter.Reset();

  1303 	while((q=iter.Next())!=0)

  1304 		{

  1305 		const TInt* qi = hm.Find(q);

  1306 		test(qi!=0 && *qi>=0 && *qi<4096 && (*qi&3));

  1307 		test(DesC8Array[*qi]==q);

  1308 		}

  1309 	s.Close();

  1311 	// test ResetAndDestroy

  1312 	for (i=0; i<16; ++i)

  1313 		{

  1314 		TInt r = s.Insert(DesC8Array[i]->Alloc());

  1315 		test(r==KErrNone);

  1316 		}

  1317 	iter.Reset();

  1318 	while((q=iter.Next())!=0)

  1319 		{

  1320 		const TInt* qi = hm.Find(q);

  1321 		test(qi!=0 && *qi>=0 && *qi<16);

  1322 		test(*DesC8Array[*qi]==*q);

  1323 		test(DesC8Array[*qi]!=q);

  1324 		}

  1325 	s.ResetAndDestroy();

  1326 	hm.Close();

  1329 	STRSET16(S);

  1330 	RHashMap<const TDesC16*, TInt> HM(&istrh16, &istrid16);

  1331 	RPtrHashSet<TDesC16>::TIter ITER(S);

  1332 	const TDesC16* Q;

  1333 	for (i=0; i<4096; ++i)

  1334 		{

  1335 		TInt r = S.Insert(DesC16Array[i]);

  1336 		test(r==KErrNone);

  1337 		r = HM.Insert(DesC16Array[i], i);

  1338 		test(r==KErrNone);

  1339 		}

  1340 	CCheck(S);

  1341 	for (i=0; i<4100; ++i)

  1342 		{

  1343 		TTestName n(NumberInWords(i));

  1344 		TBuf<80> buf;

  1345 		buf.Copy(n);

  1346 		const TDesC16* p = S.Find(buf);

  1347 		if (i<4096)

  1348 			test(p && *p==buf && p==DesC16Array[i]);

  1349 		else

  1350 			test(!p);

  1351 		}

  1352 	while((Q=ITER.Next())!=0)

  1353 		{

  1354 		const TInt* qi = HM.Find(Q);

  1355 		test(qi!=0 && *qi>=0 && *qi<4096);

  1356 		test(DesC16Array[*qi]==Q);

  1357 		}

  1358 	for (i=0; i<4100; i+=2)

  1359 		{

  1360 		TTestName n(NumberInWords(i));

  1361 		TBuf<80> buf;

  1362 		buf.Copy(n);

  1363 		TInt r = S.Remove(&buf);

  1364 		if (i<4096)

  1365 			test(r==KErrNone);

  1366 		else

  1367 			test(r==KErrNotFound);

  1368 		}

  1369 	test(S.Count()==2048);

  1370 	CCheck(S);

  1371 	for (i=0; i<4100; ++i)

  1372 		{

  1373 		TTestName n(NumberInWords(i));

  1374 		TBuf<80> buf;

  1375 		buf.Copy(n);

  1376 		const TDesC16* p = S.Find(buf);

  1377 		if (i<4096 && (i&1))

  1378 			test(p && *p==buf && p==DesC16Array[i]);

  1379 		else

  1380 			test(!p);

  1381 		}

  1382 	ITER.Reset();

  1383 	while((Q=ITER.Next())!=0)

  1384 		{

  1385 		const TInt* qi = HM.Find(Q);

  1386 		test(qi!=0 && *qi>=0 && *qi<4096 && (*qi&1));

  1387 		test(DesC16Array[*qi]==Q);

  1388 		}

  1389 	for (i=2; i<4096; i+=4)

  1390 		{

  1391 		TInt r = S.Insert(DesC16Array[i]);

  1392 		test(r==KErrNone);

  1393 		}

  1394 	test(S.Count()==3072);

  1395 	CCheck(S);

  1396 	for (i=0; i<4100; ++i)

  1397 		{

  1398 		TTestName n(NumberInWords(i));

  1399 		TBuf<80> buf;

  1400 		buf.Copy(n);

  1401 		const TDesC16* p = S.Find(buf);

  1402 		if (i<4096 && (i&3))

  1403 			test(p && *p==buf && p==DesC16Array[i]);

  1404 		else

  1405 			test(!p);

  1406 		}

  1407 	ITER.Reset();

  1408 	while((Q=ITER.Next())!=0)

  1409 		{

  1410 		const TInt* qi = HM.Find(Q);

  1411 		test(qi!=0 && *qi>=0 && *qi<4096 && (*qi&3));

  1412 		test(DesC16Array[*qi]==Q);

  1413 		}

  1414 	S.Close();

  1416 	// test ResetAndDestroy

  1417 	for (i=0; i<16; ++i)

  1418 		{

  1419 		TInt r = S.Insert(DesC16Array[i]->Alloc());

  1420 		test(r==KErrNone);

  1421 		}

  1422 	ITER.Reset();

  1423 	while((Q=ITER.Next())!=0)

  1424 		{

  1425 		const TInt* qi = HM.Find(Q);

  1426 		test(qi!=0 && *qi>=0 && *qi<16);

  1427 		test(*DesC16Array[*qi]==*Q);

  1428 		test(DesC16Array[*qi]!=Q);

  1429 		}

  1430 	S.ResetAndDestroy();

  1431 	HM.Close();

  1432 	}

  1434 void TestPtrHashMap()

  1435 	{

  1436 	test.Next(_L("Test RPtrHashMap"));

  1438 	STRMAP8(map);

  1439 	CCheck(map);		// check consistency for empty table

  1440 	STRMAP8(id);

  1441 	TInt i;

  1442 	for (i=0; i<4096; ++i)

  1443 		{

  1444 		TInt r = map.Insert(DesC8Array[i], DesC8Array[(i+1)&0xfff]);

  1445 		test(r==KErrNone);

  1446 		r = id.Insert(DesC8Array[i], DesC8Array[i]);

  1447 		test(r==KErrNone);

  1448 		}

  1449 	for (i=0; i<4096; ++i)

  1450 		{

  1451 		const TDesC8* p = map.Find(*DesC8Array[i]);

  1452 		test(p == DesC8Array[(i+1)&0xfff]);

  1453 		const TDesC8& pp = map.FindL(*DesC8Array[i]);

  1454 		test(&pp == p);

  1455 		}

  1456 	TRAPD(rr,map.FindL(_L8("two")));

  1457 	test(rr==KErrNone);

  1458 	TRAP(rr,map.FindL(_L8("twx")));

  1459 	test(rr==KErrNotFound);

  1460 	CCheck(map);

  1461 	STRMAP8(map2);

  1462 	STRMAP8(mapi);

  1463 	STRMAP8(map3);

  1464 	UnionInverse<TDesC8,TDesC8>(mapi, map);

  1465 	UnionCompose<TDesC8,TDesC8,TDesC8>(map2, map, map);

  1466 	UnionCompose<TDesC8,TDesC8,TDesC8>(map3, map, mapi);

  1467 	CheckIdenticalMaps<TDesC8,TDesC8>(map3, id);

  1468 	map3.Close();

  1469 	UnionCompose<TDesC8,TDesC8,TDesC8>(map3, map2, mapi);

  1470 	CheckIdenticalMaps<TDesC8,TDesC8>(map3, map);

  1471 	map3.Close();

  1472 	for (i=0; i<4096; ++i)

  1473 		{

  1474 		TInt r = map3.Insert(DesC8Array[i], DesC8Array[(i+2)&0xfff]);

  1475 		test(r==KErrNone);

  1476 		}

  1477 	CheckIdenticalMaps<TDesC8,TDesC8>(map3, map2);

  1478 	map3.Close();

  1480 	mapi.Close();

  1481 	map2.Close();

  1482 	id.Close();

  1483 	map.Close();

  1485 	// test ResetAndDestroy()

  1486 	for(i=0; i<16; ++i)

  1487 		{

  1488 		TInt r = map.Insert(DesC8Array[i]->Alloc(), DesC8Array[i*i]->Alloc());

  1489 		test(r==KErrNone);

  1490 		}

  1491 	map.ResetAndDestroy();

  1492 	}

  1494 void TestOOM()

  1495 	{

  1496 	// Max out memory and check it still works

  1497 	test.Next(_L("Test OOM"));

  1499 	TInt x = 0;

  1500 	TInt n = 0;

  1501 	TInt r;

  1502 	INTSET(set);

  1503 	FOREVER

  1504 		{

  1505 		x += 0x58b90bfb;

  1506 		r = set.Insert(x);

  1507 		if (r != KErrNone)

  1508 			break;

  1509 		++n;

  1510 		}

  1511 	test(r==KErrNoMemory);

  1512 	TRAPD(rr,set.InsertL(x));

  1513 	test(rr==KErrNoMemory);

  1514 	test.Printf(_L("%d integers stored\n"), n);

  1515 	test(set.Count()==n);

  1516 	TRAP(rr,set.InsertL(0x58b90bfb));	// already there

  1517 	test(rr==KErrNone);	// should succeed

  1519 	// final count should be a power of 2 minus 1

  1520 	test( (n&(n+1)) == 0 );

  1522 	x = 0;

  1523 	TInt i;

  1524 	for (i=0; i<=n; ++i)		// check everything has been stored correctly

  1525 		{

  1526 		x += 0x58b90bfb;

  1527 		const TInt* p = set.Find(x);

  1528 		if (i < n)

  1529 			test(p && *p == x);

  1530 		else

  1531 			test(!p);

  1532 		}

  1533 	set.Close();

  1534 	TInt nn;

  1535 	for (nn=256; nn<=n+256; nn+=256)

  1536 		{

  1537 		r = set.Reserve(nn);

  1538 		set.Close();

  1539 		if (r!=KErrNone)

  1540 			break;

  1541 		}

  1542 	test.Printf(_L("Max reserve %d\n"),nn);

  1543 	TInt thresh = 3*((n+1)>>2);

  1544 	test(nn == thresh + 256);

  1545 	}

  1547 class RDummyAllocator : public RAllocator

  1548 	{

  1549 public:

  1550 	virtual TAny* Alloc(TInt) {test(0); return 0;}

  1551 	virtual void Free(TAny*) {test(0);}

  1552 	virtual TAny* ReAlloc(TAny*, TInt, TInt) {test(0); return 0;}

  1553 	virtual TInt AllocLen(const TAny*) const  {test(0); return 0;}

  1554 	virtual TInt Compress() {test(0); return 0;}

  1555 	virtual void Reset() {test(0);}

  1556 	virtual TInt AllocSize(TInt&) const  {test(0); return 0;}

  1557 	virtual TInt Available(TInt&) const  {test(0); return 0;}

  1558 	virtual TInt DebugFunction(TInt, TAny*, TAny*) {test(0); return 0;}

  1559 	virtual TInt Extension_(TUint, TAny*&, TAny*) {test(0); return 0;}

  1560 	};

  1562 void IntegerBenchmark(TInt aCount, TBool aReserve)

  1563 	{

  1564 	RArray<TInt> array;

  1565 	TUint32 before, after, diff;

  1566 	TInt x=0;

  1567 	TInt i;

  1568 	double avg;

  1570 	test.Printf(_L("**** INTEGER BENCHMARKS ***\n"));

  1572 	if (!aReserve)

  1573 		{

  1574 		before = User::NTickCount();

  1575 		for (i=0; i<aCount; ++i)

  1576 			{

  1577 			x += 0x58b90bfb;

  1578 			TInt r = array.InsertInOrder(x);

  1579 			test(r==KErrNone);

  1580 			}

  1581 		after = User::NTickCount();

  1582 		diff = after - before;

  1583 		diff *= NanoTickPeriod;

  1584 		avg = (double)diff / (double)aCount;

  1585 		test.Printf(_L("ARRAY:      %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);

  1587 		x=0;

  1588 		before = User::NTickCount();

  1589 		for (i=0; i<aCount; ++i)

  1590 			{

  1591 			x += 0x58b90bfb;

  1592 			TInt r = array.FindInOrder(x);

  1593 			test(r>=0);

  1594 			}

  1595 		after = User::NTickCount();

  1596 		diff = after - before;

  1597 		diff *= NanoTickPeriod;

  1598 		avg = (double)diff / (double)aCount;

  1599 		test.Printf(_L("ARRAY:      %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);

  1601 		before = User::NTickCount();

  1602 		for (i=0; i<aCount; ++i)

  1603 			{

  1604 			x += 0x58b90bfb;

  1605 			TInt r = array.FindInOrder(x);

  1606 			test(r==KErrNotFound);

  1607 			}

  1608 		after = User::NTickCount();

  1609 		diff = after - before;

  1610 		diff *= NanoTickPeriod;

  1611 		avg = (double)diff / (double)aCount;

  1612 		test.Printf(_L("ARRAY:      %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);

  1614 		x=0;

  1615 		before = User::NTickCount();

  1616 		for (i=0; i<aCount; ++i)

  1617 			{

  1618 			x += 0x58b90bfb;

  1619 			TInt r = array.FindInOrder(x);

  1620 			test(r>=0);

  1621 			array.Remove(r);

  1622 			}

  1623 		after = User::NTickCount();

  1624 		diff = after - before;

  1625 		diff *= NanoTickPeriod;

  1626 		avg = (double)diff / (double)aCount;

  1627 		test.Printf(_L("ARRAY:      %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);

  1628 		array.Close();

  1629 		}

  1631 	INTSET(set);

  1632 	x=0;

  1633 	RAllocator* pA = 0;

  1634 	RDummyAllocator da;

  1635 	if (aReserve)

  1636 		{

  1637 		test(set.Reserve(aCount)==KErrNone);

  1638 		pA = User::SwitchAllocator(&da);			// check that no memory accesses occur

  1639 		test(set.Reserve(10)==KErrNone);			// shouldn't need to do anything

  1640 		test(set.Reserve(aCount/2)==KErrNone);		// shouldn't need to do anything

  1641 		test(set.Reserve(aCount)==KErrNone);		// shouldn't need to do anything

  1642 		}

  1643 	before = User::NTickCount();

  1644 	for (i=0; i<aCount; ++i)

  1645 		{

  1646 		x += 0x58b90bfb;

  1647 		TInt r = set.Insert(x);	// we have no heap here so this tests that Reserve() has preallocated sufficient memory

  1648 		test(r==KErrNone);

  1649 		}

  1650 	after = User::NTickCount();

  1651 	diff = after - before;

  1652 	diff *= NanoTickPeriod;

  1653 	avg = (double)diff / (double)aCount;

  1654 	if (aReserve)

  1655 		User::SwitchAllocator(pA);

  1656 	test.Printf(_L("HASH TABLE: %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);

  1658 	x=0;

  1659 	before = User::NTickCount();

  1660 	for (i=0; i<aCount; ++i)

  1661 		{

  1662 		x += 0x58b90bfb;

  1663 		const TInt* p = set.Find(x);

  1664 		test(p!=0);

  1665 		}

  1666 	after = User::NTickCount();

  1667 	diff = after - before;

  1668 	diff *= NanoTickPeriod;

  1669 	avg = (double)diff / (double)aCount;

  1670 	test.Printf(_L("HASH TABLE: %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);

  1672 	before = User::NTickCount();

  1673 	for (i=0; i<aCount; ++i)

  1674 		{

  1675 		x += 0x58b90bfb;

  1676 		const TInt* p = set.Find(x);

  1677 		test(!p);

  1678 		}

  1679 	after = User::NTickCount();

  1680 	diff = after - before;

  1681 	diff *= NanoTickPeriod;

  1682 	avg = (double)diff / (double)aCount;

  1683 	test.Printf(_L("HASH TABLE: %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);

  1685 	x=0;

  1686 	before = User::NTickCount();

  1687 	for (i=0; i<aCount; ++i)

  1688 		{

  1689 		x += 0x58b90bfb;

  1690 		TInt r = set.Remove(x);

  1691 		test(r==KErrNone);

  1692 		}

  1693 	after = User::NTickCount();

  1694 	diff = after - before;

  1695 	diff *= NanoTickPeriod;

  1696 	avg = (double)diff / (double)aCount;

  1697 	test.Printf(_L("HASH TABLE: %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);

  1698 	set.Close();

  1699 	}

  1701 TInt des8order(const TDesC8& aA, const TDesC8& aB)

  1702 	{

  1703 	return aA.Compare(aB);

  1704 	}

  1706 void StringBenchmark8(TInt aCount, TBool aReserve)

  1707 	{

  1708 	RPointerArray<TDesC8> array;

  1709 	TUint32 before, after, diff;

  1710 	TInt x=0;

  1711 	TInt i;

  1712 	double avg;

  1713 	const TDesC8** base = (const TDesC8**)&DesC8Array[0];

  1714 	test(base[1331] == DesC8Array[1331]);

  1716 	test.Printf(_L("**** 8 BIT STRING BENCHMARKS ***\n"));

  1718 	if (!aReserve)

  1719 		{

  1720 		before = User::NTickCount();

  1721 		for (i=0; i<aCount; ++i)

  1722 			{

  1723 			x = (x+4339)&0x3fff;

  1724 			TInt r = array.InsertInOrder(base[x], &des8order);

  1725 			test(r==KErrNone);

  1726 			}

  1727 		after = User::NTickCount();

  1728 		diff = after - before;

  1729 		diff *= NanoTickPeriod;

  1730 		avg = (double)diff / (double)aCount;

  1731 		test.Printf(_L("ARRAY:      %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);

  1733 		x=0;

  1734 		before = User::NTickCount();

  1735 		for (i=0; i<aCount; ++i)

  1736 			{

  1737 			x = (x+4339)&0x3fff;

  1738 			TInt r = array.FindInOrder(base[x], &des8order);

  1739 			test(r>=0);

  1740 			}

  1741 		after = User::NTickCount();

  1742 		diff = after - before;

  1743 		diff *= NanoTickPeriod;

  1744 		avg = (double)diff / (double)aCount;

  1745 		test.Printf(_L("ARRAY:      %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);

  1747 		before = User::NTickCount();

  1748 		for (i=0; i<aCount; ++i)

  1749 			{

  1750 			x = (x+4339)&0x3fff;

  1751 			TInt r = array.FindInOrder(base[x], &des8order);

  1752 			test(r==KErrNotFound);

  1753 			}

  1754 		after = User::NTickCount();

  1755 		diff = after - before;

  1756 		diff *= NanoTickPeriod;

  1757 		avg = (double)diff / (double)aCount;

  1758 		test.Printf(_L("ARRAY:      %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);

  1760 		x=0;

  1761 		before = User::NTickCount();

  1762 		for (i=0; i<aCount; ++i)

  1763 			{

  1764 			x = (x+4339)&0x3fff;

  1765 			TInt r = array.FindInOrder(base[x], &des8order);

  1766 			test(r>=0);

  1767 			array.Remove(r);

  1768 			}

  1769 		after = User::NTickCount();

  1770 		diff = after - before;

  1771 		diff *= NanoTickPeriod;

  1772 		avg = (double)diff / (double)aCount;

  1773 		test.Printf(_L("ARRAY:      %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);

  1774 		array.Close();

  1775 		}

  1777 	STRSET8(set);

  1778 	x=0;

  1779 	if (aReserve)

  1780 		test(set.Reserve(aCount)==KErrNone);

  1781 	before = User::NTickCount();

  1782 	for (i=0; i<aCount; ++i)

  1783 		{

  1784 		x = (x+4339)&0x3fff;

  1785 		TInt r = set.Insert(base[x]);

  1786 		test(r==KErrNone);

  1787 		}

  1788 	after = User::NTickCount();

  1789 	diff = after - before;

  1790 	diff *= NanoTickPeriod;

  1791 	avg = (double)diff / (double)aCount;

  1792 	test.Printf(_L("HASH TABLE: %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);

  1794 	x=0;

  1795 	before = User::NTickCount();

  1796 	for (i=0; i<aCount; ++i)

  1797 		{

  1798 		x = (x+4339)&0x3fff;

  1799 		const TDesC8* p = set.Find(*base[x]);

  1800 		test(p!=0);

  1801 		}

  1802 	after = User::NTickCount();

  1803 	diff = after - before;

  1804 	diff *= NanoTickPeriod;

  1805 	avg = (double)diff / (double)aCount;

  1806 	test.Printf(_L("HASH TABLE: %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);

  1808 	before = User::NTickCount();

  1809 	for (i=0; i<aCount; ++i)

  1810 		{

  1811 		x = (x+4339)&0x3fff;

  1812 		const TDesC8* p = set.Find(*base[x]);

  1813 		test(!p);

  1814 		}

  1815 	after = User::NTickCount();

  1816 	diff = after - before;

  1817 	diff *= NanoTickPeriod;

  1818 	avg = (double)diff / (double)aCount;

  1819 	test.Printf(_L("HASH TABLE: %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);

  1821 	x=0;

  1822 	before = User::NTickCount();

  1823 	for (i=0; i<aCount; ++i)

  1824 		{

  1825 		x = (x+4339)&0x3fff;

  1826 		TInt r = set.Remove(base[x]);

  1827 		test(r==KErrNone);

  1828 		}

  1829 	after = User::NTickCount();

  1830 	diff = after - before;

  1831 	diff *= NanoTickPeriod;

  1832 	avg = (double)diff / (double)aCount;

  1833 	test.Printf(_L("HASH TABLE: %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);

  1834 	set.Close();

  1835 	}

  1837 TInt des16order(const TDesC16& aA, const TDesC16& aB)

  1838 	{

  1839 	return aA.Compare(aB);

  1840 	}

  1842 void StringBenchmark16(TInt aCount, TBool aReserve)

  1843 	{

  1844 	RPointerArray<TDesC16> array;

  1845 	TUint32 before, after, diff;

  1846 	TInt x=0;

  1847 	TInt i;

  1848 	double avg;

  1849 	const TDesC16** base = (const TDesC16**)&DesC16Array[0];

  1850 	test(base[1331] == DesC16Array[1331]);

  1852 	test.Printf(_L("**** 16 BIT STRING BENCHMARKS ***\n"));

  1854 	if (!aReserve)

  1855 		{

  1856 		before = User::NTickCount();

  1857 		for (i=0; i<aCount; ++i)

  1858 			{

  1859 			x = (x+4339)&0x3fff;

  1860 			TInt r = array.InsertInOrder(base[x], &des16order);

  1861 			test(r==KErrNone);

  1862 			}

  1863 		after = User::NTickCount();

  1864 		diff = after - before;

  1865 		diff *= NanoTickPeriod;

  1866 		avg = (double)diff / (double)aCount;

  1867 		test.Printf(_L("ARRAY:      %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);

  1869 		x=0;

  1870 		before = User::NTickCount();

  1871 		for (i=0; i<aCount; ++i)

  1872 			{

  1873 			x = (x+4339)&0x3fff;

  1874 			TInt r = array.FindInOrder(base[x], &des16order);

  1875 			test(r>=0);

  1876 			}

  1877 		after = User::NTickCount();

  1878 		diff = after - before;

  1879 		diff *= NanoTickPeriod;

  1880 		avg = (double)diff / (double)aCount;

  1881 		test.Printf(_L("ARRAY:      %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);

  1883 		before = User::NTickCount();

  1884 		for (i=0; i<aCount; ++i)

  1885 			{

  1886 			x = (x+4339)&0x3fff;

  1887 			TInt r = array.FindInOrder(base[x], &des16order);

  1888 			test(r==KErrNotFound);

  1889 			}

  1890 		after = User::NTickCount();

  1891 		diff = after - before;

  1892 		diff *= NanoTickPeriod;

  1893 		avg = (double)diff / (double)aCount;

  1894 		test.Printf(_L("ARRAY:      %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);

  1896 		x=0;

  1897 		before = User::NTickCount();

  1898 		for (i=0; i<aCount; ++i)

  1899 			{

  1900 			x = (x+4339)&0x3fff;

  1901 			TInt r = array.FindInOrder(base[x], &des16order);

  1902 			test(r>=0);

  1903 			array.Remove(r);

  1904 			}

  1905 		after = User::NTickCount();

  1906 		diff = after - before;

  1907 		diff *= NanoTickPeriod;

  1908 		avg = (double)diff / (double)aCount;

  1909 		test.Printf(_L("ARRAY:      %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);

  1910 		array.Close();

  1911 		}

  1913 	STRSET16(set);

  1914 	x=0;

  1915 	if (aReserve)

  1916 		test(set.Reserve(aCount)==KErrNone);

  1917 	before = User::NTickCount();

  1918 	for (i=0; i<aCount; ++i)

  1919 		{

  1920 		x = (x+4339)&0x3fff;

  1921 		TInt r = set.Insert(base[x]);

  1922 		test(r==KErrNone);

  1923 		}

  1924 	after = User::NTickCount();

  1925 	diff = after - before;

  1926 	diff *= NanoTickPeriod;

  1927 	avg = (double)diff / (double)aCount;

  1928 	test.Printf(_L("HASH TABLE: %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);

  1930 	x=0;

  1931 	before = User::NTickCount();

  1932 	for (i=0; i<aCount; ++i)

  1933 		{

  1934 		x = (x+4339)&0x3fff;

  1935 		const TDesC16* p = set.Find(*base[x]);

  1936 		test(p!=0);

  1937 		}

  1938 	after = User::NTickCount();

  1939 	diff = after - before;

  1940 	diff *= NanoTickPeriod;

  1941 	avg = (double)diff / (double)aCount;

  1942 	test.Printf(_L("HASH TABLE: %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);

  1944 	before = User::NTickCount();

  1945 	for (i=0; i<aCount; ++i)

  1946 		{

  1947 		x = (x+4339)&0x3fff;

  1948 		const TDesC16* p = set.Find(*base[x]);

  1949 		test(!p);

  1950 		}

  1951 	after = User::NTickCount();

  1952 	diff = after - before;

  1953 	diff *= NanoTickPeriod;

  1954 	avg = (double)diff / (double)aCount;

  1955 	test.Printf(_L("HASH TABLE: %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);

  1957 	x=0;

  1958 	before = User::NTickCount();

  1959 	for (i=0; i<aCount; ++i)

  1960 		{

  1961 		x = (x+4339)&0x3fff;

  1962 		TInt r = set.Remove(base[x]);

  1963 		test(r==KErrNone);

  1964 		}

  1965 	after = User::NTickCount();

  1966 	diff = after - before;

  1967 	diff *= NanoTickPeriod;

  1968 	avg = (double)diff / (double)aCount;

  1969 	test.Printf(_L("HASH TABLE: %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);

  1970 	set.Close();

  1971 	}

  1973 void Benchmark()

  1974 	{

  1975 	test.Next(_L("Benchmarks ..."));

  1977 	IntegerBenchmark(1000, EFalse);

  1978 	IntegerBenchmark(1000, ETrue);

  1979 	IntegerBenchmark(2000, EFalse);

  1980 	IntegerBenchmark(2000, ETrue);

  1981 	IntegerBenchmark(4000, EFalse);

  1982 	IntegerBenchmark(4000, ETrue);

  1983 	IntegerBenchmark(8000, EFalse);

  1984 	IntegerBenchmark(8000, ETrue);

  1985 	IntegerBenchmark(16000, EFalse);

  1986 	IntegerBenchmark(16000, ETrue);

  1987 	IntegerBenchmark(32000, EFalse);

  1988 	IntegerBenchmark(32000, ETrue);

  1990 	PopulateArray8(16384);

  1991 	StringBenchmark8(1000, EFalse);

  1992 	StringBenchmark8(2000, EFalse);

  1993 	StringBenchmark8(4000, EFalse);

  1994 	StringBenchmark8(8000, EFalse);

  1995 	DesC8Array.ResetAndDestroy();

  1997 	PopulateArray16(16384);

  1998 	StringBenchmark16(1000, EFalse);

  1999 	StringBenchmark16(2000, EFalse);

  2000 	StringBenchmark16(4000, EFalse);

  2001 	StringBenchmark16(8000, EFalse);

  2002 	DesC16Array.ResetAndDestroy();

  2003 	}

  2006 TUint32 mp(TUint32 x)

  2007 	{

  2008 	TUint32 x3 = x+(x<<1);

  2009 	TUint32 x7 = x+(x3<<1);

  2010 	TUint32 x15 = x+(x7<<1);

  2011 	TUint32 y = x + (x7<<3) + (x3<<7) + (x15<<11) + (x7<<16) + (x3<<20) + (x15<<25) + (x<<31);

  2012 	return y;

  2013 	}

  2015 TUint32 strh(const char* aIn)

  2016 	{

  2017 	TUint32 h = 0;

  2018 	TInt i = 0;

  2019 	while (*aIn)

  2020 		{

  2021 		if (i==0)

  2022 			h = mp(h);

  2023 		TUint32 c = *aIn++;

  2024 		c <<= (8*i);

  2025 		h ^= c;

  2026 		i = (i+1)&3;

  2027 		}

  2028 	return mp(h);

  2029 	}

  2031 TUint32 strh(const wch* aIn)

  2032 	{

  2033 	TUint32 h = 0;

  2034 	TInt i = 0;

  2035 	while (*aIn)

  2036 		{

  2037 		if (i==0)

  2038 			h = mp(h);

  2039 		TUint32 c = *aIn++;

  2040 		switch (i)

  2041 			{

  2042 			case 0:		break;

  2043 			case 1:		c<<=16; break;

  2044 			case 2:		c<<=8; break;

  2045 			default:	c=(c<<24)|(c>>8); break;

  2046 			};

  2047 		h ^= c;

  2048 		i = (i+1)&3;

  2049 		}

  2050 	return mp(h);

  2051 	}

  2053 void TestHash(TInt* aIn, TUint32 aExpected)

  2054 	{

  2055 	THashFunction32<TInt*> hf(&DefaultHash::IntegerPtr);

  2056 	TUint32 out = hf.Hash(aIn);

  2057 	test(aExpected == mp((TUint32)aIn));

  2058 	if (out != aExpected)

  2059 		{

  2060 		test.Printf(_L("Hashing %08x Expected %08x Got %08x\n"), aIn, aExpected, out);

  2061 		test(0);

  2062 		}

  2063 	}

  2065 void TestHash(TDesC8* aIn, TUint32 aExpected)

  2066 	{

  2067 	THashFunction32<TDesC8*> hf(&DefaultHash::Des8Ptr);

  2068 	TUint32 out = hf.Hash(aIn);

  2069 	test(aExpected == mp((TUint32)aIn));

  2070 	if (out != aExpected)

  2071 		{

  2072 		test.Printf(_L("Hashing %08x Expected %08x Got %08x\n"), aIn, aExpected, out);

  2073 		test(0);

  2074 		}

  2075 	}

  2077 void TestHash(TDesC16* aIn, TUint32 aExpected)

  2078 	{

  2079 	THashFunction32<TDesC16*> hf(&DefaultHash::Des16Ptr);

  2080 	TUint32 out = hf.Hash(aIn);

  2081 	test(aExpected == mp((TUint32)aIn));

  2082 	if (out != aExpected)

  2083 		{

  2084 		test.Printf(_L("Hashing %08x Expected %08x Got %08x\n"), aIn, aExpected, out);

  2085 		test(0);

  2086 		}

  2087 	}

  2090 void TestHash(TInt aIn, TUint32 aExpected)

  2091 	{

  2092 	THashFunction32<TInt> hf(&DefaultHash::Integer);

  2093 	TUint32 out = hf.Hash(aIn);

  2094 	test(aExpected == mp((TUint32)aIn));

  2095 	if (out != aExpected)

  2096 		{

  2097 		test.Printf(_L("Hashing %08x Expected %08x Got %08x\n"), aIn, aExpected, out);

  2098 		test(0);

  2099 		}

  2100 	}

  2102 void TestHash(const char* aIn, TUint32 aExpected)

  2103 	{

  2104 	THashFunction32<TDesC8> hf(&DefaultHash::Des8);

  2105 	TPtrC8 p((const TUint8*)aIn);

  2106 	TUint32 out = hf.Hash(p);

  2107 	test(aExpected == strh(aIn));

  2108 	if (out != aExpected)

  2109 		{

  2110 		TBuf<256> buf;

  2111 		buf.Copy(p);

  2112 		test.Printf(_L("Hashing %S (len %d) Expected %08x Got %08x\n"), &buf, p.Length(), aExpected, out);

  2113 		test(0);

  2114 		}

  2115 	}

  2117 void TestHash(const wch* aIn)

  2118 	{

  2119 	THashFunction32<TDesC16> hf(&DefaultHash::Des16);

  2120 	TPtrC16 p((const TUint16*)aIn);

  2121 	TUint32 out = hf.Hash(p);

  2122 	TUint32 exp = strh(aIn);

  2123 	if (out != exp)

  2124 		{

  2125 		test.Printf(_L("Hashing %S (len %d) Expected %08x Got %08x\n"), &p, p.Size(), exp, out);

  2126 		test(0);

  2127 		}

  2128 	}

  2130 void TestHash()

  2131 	{

  2132 	test.Next(_L("Test integer hash"));

  2133 	TestHash(1,0x9e3779b9);

  2134 	TestHash(2,0x3c6ef372);

  2135 	TestHash(4,0x78dde6e4);

  2136 	TestHash(8,0xf1bbcdc8);

  2137 	TestHash(16,0xe3779b90);

  2138 	TestHash(0xc90fdaa2,0xbf999112);

  2139 	TestHash(0xb504f334,0x7fb35494);

  2140 	TestHash(0xddb3d743,0xd11a3a6b);

  2141 	TestHash(0xadf85458,0x873a8b98);

  2142 	TestHash(0x11730859,0xb4321951);

  2143 	TestHash(0x64636261,0x8628f119);

  2144 	}

  2146 void TestIntegerPtrHash()

  2147 	{

  2148 	TInt i[5];

  2149 	TInt* ptr;

  2150 	test.Next(_L("Test Integer pointer hash"));

  2151 	for (ptr=i; ptr<i+5; ptr++)

  2152 		{

  2153 		TestHash(ptr, DefaultHash::IntegerPtr(ptr));

  2154 		}

  2155 	}

  2157 void TestDes8PtrHash()

  2158 	{

  2159 	TBuf8<8> i[5];

  2160 	TDesC8* ptr;

  2161 	test.Next(_L("Test Des8 pointer hash"));

  2162 	for (ptr=i; ptr<i+5; ptr++)

  2163 		{

  2164 		TestHash(ptr, DefaultHash::Des8Ptr(ptr));

  2165 		}

  2166 	}

  2168 void TestDes16PtrHash()

  2169 	{

  2170 	TBuf16<8> i[5];

  2171 	TDesC16* ptr;

  2172 	test.Next(_L("Test Des16 pointer hash"));

  2173 	for (ptr=i; ptr<i+5; ptr++)

  2174 		{

  2175 		TestHash(ptr, DefaultHash::Des16Ptr(ptr));

  2176 		}

  2177 	}

  2179 const char teststr[] = "zyxwvutsrq";

  2180 void TestStringHash()

  2181 	{

  2182 	test.Next(_L("Test 8 bit string hash"));

  2183 	TestHash("",0x0);

  2184 	TestHash("a",0xf3051f19);

  2185 	TestHash("b",0x913c98d2);

  2186 	TestHash("ab",0x2f9df119);

  2187 	TestHash("ba",0x965bb1d2);

  2188 	TestHash("abc",0x4228f119);

  2189 	TestHash("abcd",0x8628f119);

  2190 	TestHash("abcde",0xb75e1e9c);

  2191 	TestHash("abcdef",0x3693149c);

  2192 	TestHash("abcdefg",0xc1c2149c);

  2193 	TestHash("abcdefgh",0xe9c2149c);

  2194 	TestHash("abcdefghi",0x5fcbf20d);

  2195 	TestHash("abcdefghj",0xfe036bc6);

  2197 	TestHash(teststr, 0x108ca51e);

  2198 	TestHash(teststr+1, 0x551002ad);

  2199 	TestHash(teststr+2, 0x37dc0d6c);

  2200 	TestHash(teststr+3, 0x2937f92c);

  2201 	TestHash(teststr+4, 0xf0818a94);

  2202 	TestHash(teststr+5, 0xb1b25f1c);

  2203 	TestHash(teststr+6, 0x7a3342d4);

  2204 	TestHash(teststr+7, 0x81c9101b);

  2205 	TestHash(teststr+8, 0xf16edd62);

  2206 	TestHash(teststr+9, 0xd67cbaa9);

  2207 	TestHash(teststr+10, 0);

  2209 	char t[16];

  2210 	int i,j;

  2211 	for (i=0; i<=4; ++i)

  2212 		{

  2213 		for (j=0; j<=10; ++j)

  2214 			{

  2215 			const char* s = teststr + j;

  2216 			int l = User::StringLength((const TUint8*)s);

  2217 			memset(t, 0xbb, 16);

  2218 			memcpy(t+i, s, l+1);

  2219 			TUint32 h;

  2220 			switch (j)

  2221 				{

  2222 				case 0: h = 0x108ca51e; break;

  2223 				case 1: h = 0x551002ad; break;

  2224 				case 2: h = 0x37dc0d6c; break;

  2225 				case 3: h = 0x2937f92c; break;

  2226 				case 4: h = 0xf0818a94; break;

  2227 				case 5: h = 0xb1b25f1c; break;

  2228 				case 6: h = 0x7a3342d4; break;

  2229 				case 7: h = 0x81c9101b; break;

  2230 				case 8: h = 0xf16edd62; break;

  2231 				case 9: h = 0xd67cbaa9; break;

  2232 				default: h = 0; break;

  2233 				};

  2234 			TestHash(t+i, h);

  2235 			}

  2236 		}

  2237 	}

  2239 const wch wteststr[] = L"zyxwvutsrq";

  2240 void TestWStringHash()

  2241 	{

  2242 	test.Next(_L("Test 16 bit string hash"));

  2243 	TestHash(L"");

  2244 	TestHash(L"a");

  2245 	TestHash(L"b");

  2246 	TestHash(L"ab");

  2247 	TestHash(L"ba");

  2248 	TestHash(L"abc");

  2249 	TestHash(L"abcd");

  2250 	TestHash(L"abcde");

  2251 	TestHash(L"abcdef");

  2252 	TestHash(L"abcdefg");

  2253 	TestHash(L"abcdefgh");

  2254 	TestHash(L"abcdefghi");

  2255 	TestHash(L"abcdefghj");

  2257 	TestHash(wteststr);

  2258 	TestHash(wteststr+1);

  2259 	TestHash(wteststr+2);

  2260 	TestHash(wteststr+3);

  2261 	TestHash(wteststr+4);

  2262 	TestHash(wteststr+5);

  2263 	TestHash(wteststr+6);

  2264 	TestHash(wteststr+7);

  2265 	TestHash(wteststr+8);

  2266 	TestHash(wteststr+9);

  2267 	TestHash(wteststr+10);

  2269 	wch t[16];

  2270 	int i,j;

  2271 	for (i=0; i<=4; ++i)

  2272 		{

  2273 		for (j=0; j<=10; ++j)

  2274 			{

  2275 			const wch* s = wteststr + j;

  2276 			int l = User::StringLength((const TUint16*)s);

  2277 			memset(t, 0xbb, 2*16);

  2278 			memcpy(t+i, s, 2*(l+1));

  2279 			TestHash(t+i);

  2280 			}

  2281 		}

  2282 	}

  2283 template <class K,class V>

  2284 void TestHashMapPtr(RHashMap<K,V> &map, K ptr, V* i)

  2285 {

  2286 	test(map.Reserve(5) == KErrNone);

  2287 	for (ptr=i;ptr<i+5;ptr++)

  2288 		{

  2289 		test(map.Insert(ptr,*ptr) == KErrNone);

  2290 		}

  2291 	for (ptr=i+4;ptr>=i;ptr--)

  2292 		{

  2293 		test(*(map.Find(ptr)) == *ptr);

  2294 		}

  2295 	test(map.Count() == 5);

  2296 	test(map.Remove(i) == KErrNone);

  2297 	test(map.Count()==4);

  2298 	test(map.Find(i)==NULL);

  2299 	map.Close();

  2300 }

  2302 void TestPtrHashMaps()

  2303 	{

  2305 	test.Next(_L("Test RHashMap of default pointer types"));

  2306 	TInt i[5];

  2307 	TInt *ptr=i;

  2308 	RHashMap<TInt*,TInt> mp;

  2309 	TestHashMapPtr(mp, ptr, i);

  2311 	TInt32 i1[5];

  2312 	TInt32 *ptr1=i1;

  2313 	RHashMap<TInt32*,TInt32> mp1;

  2314 	TestHashMapPtr(mp1,ptr1,i1);

  2316 	TUint i2[5];

  2317 	TUint *ptr2=i2;

  2318 	RHashMap<TUint*,TUint> mp2;

  2319 	TestHashMapPtr(mp2,ptr2,i2);

  2321 	TUint32 i3[5];

  2322 	TUint32 *ptr3=i3;

  2323 	RHashMap<TUint32*,TUint32> mp3;

  2324 	TestHashMapPtr(mp3,ptr3,i3);

  2326 	TBuf8<5> i4[5];

  2327 	TBuf8<5> *ptr4=i4;

  2328 	RHashMap<TDesC8*,TDesC8> mp4;

  2329 	for (ptr4=i4; ptr4 < i4+5; ptr4++)

  2330 		{

  2331 		test(mp4.Insert(ptr4,*ptr4) == KErrNone);

  2332 		}

  2333 	for (ptr4=i4+4; ptr4 >= i4; ptr4--)

  2334 		{

  2335 		test(*(mp4.Find(ptr4)) == *ptr4);

  2336 		}

  2337 	test(mp4.Count()==5);

  2338 	test(mp4.Remove(i4) == KErrNone);

  2339 	test(mp4.Find(i4) == NULL);

  2340 	test(mp4.Count()==4);

  2341 	mp4.Close();

  2344 	TBuf16<5> i5[5];

  2345 	TBuf16<5> *ptr5=i5;

  2346 	RHashMap<TDesC16*,TDesC16> mp5;

  2347 	for (ptr5=i5; ptr5 < i5+5; ptr5++)

  2348 		{

  2349 		test(mp5.Insert(ptr5,*ptr5) == KErrNone);

  2350 		}

  2351 	for (ptr5=i5+4; ptr5 >= i5; ptr5--)

  2352 		{

  2353 		test(*(mp5.Find(ptr5)) == *ptr5);

  2354 		}

  2355 	test(mp5.Count()==5);

  2356 	test(mp5.Remove(i5) == KErrNone);

  2357 	test(mp5.Find(i5) == NULL);

  2358 	test(mp5.Count()==4);

  2359 	mp5.Close();

  2361 }

  2363 /** Tests that Reserve() will always allocate memory for new tables

  2364 	even for small reserve sizes

  2365 	See DEF087906.

  2366 */

  2367 void TestSmallReserve()

  2368 	{

  2369 	test.Next(_L("Test RHashTableBase::Reserve preallocates memory, even for small no of elements"));

  2370 	RAllocator* pA = 0;

  2371 	RDummyAllocator da;

  2373 	// Reserve should allocate the memory required for the table of 1 element

  2374 	INTSET(set);

  2375 	RHashMap<TInt,TInt> hashMap;

  2377 	test(set.Reserve(1) == KErrNone);

  2378 	test(hashMap.Reserve(1) == KErrNone);

  2380 	pA = User::SwitchAllocator(&da);

  2382 	// No more memory should be allocated for the table as it should

  2383 	// have been already allocated by Reserve()

  2384 	test(set.Insert(123) == KErrNone);

  2385 	test(hashMap.Insert(123,456) == KErrNone);

  2387 	// Switch back to allow set to be closed

  2388 	User::SwitchAllocator(pA);

  2389 	set.Close();

  2390 	hashMap.Close();

  2391 	}

  2394 TInt E32Main()

  2395 	{

  2396 	test.Title();

  2398 	test(HAL::Get(HAL::ENanoTickPeriod, NanoTickPeriod)==KErrNone);

  2399 	test.Printf(_L("NanoTickPeriod %dus\n"), NanoTickPeriod);

  2401 	__UHEAP_MARK;

  2403 	test.Start(_L("Testing hash tables"));

  2405 	TestHash();

  2406 	TestStringHash();

  2407 	TestWStringHash();

  2408 	TestIntegerPtrHash();

  2409 	TestDes8PtrHash();

  2410 	TestDes16PtrHash();

  2412 	TestHashSet();

  2413 	TestHashIter();

  2414 	TestHashMap();

  2415 	TestPtrHashMaps();

  2417 	PopulateArray8(4096);

  2418 	PopulateArray16(4096);

  2419 	TestPtrHashSet();

  2420 	TestPtrHashMap();

  2421 	DesC16Array.ResetAndDestroy();

  2422 	DesC8Array.ResetAndDestroy();

  2425 	TestOOM();

  2426 	Benchmark();

  2427 	TestSmallReserve();

  2429 	test.End();

  2431 	__UHEAP_MARKEND;

  2432 	return 0;

  2433 	}

author	sl
	Tue, 10 Jun 2014 14:32:02 +0200
changeset 1	260cb5ec6c19
permissions	-rw-r--r--