sl@0: // Copyright (c) 2005-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: // All rights reserved.
sl@0: // This component and the accompanying materials are made available
sl@0: // under the terms of the License "Eclipse Public License v1.0"
sl@0: // which accompanies this distribution, and is available
sl@0: // at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: //
sl@0: // Initial Contributors:
sl@0: // Nokia Corporation - initial contribution.
sl@0: //
sl@0: // Contributors:
sl@0: //
sl@0: // Description:
sl@0: // e32test/buffer/t_hashtab.cpp
sl@0: // 
sl@0: //
sl@0: 
sl@0: #include <e32test.h>
sl@0: #include <e32hashtab.h>
sl@0: #include <hal.h>
sl@0: 
sl@0: #if defined(__VC32__) || defined(__CW32__)
sl@0: typedef unsigned short wch;
sl@0: #else
sl@0: typedef wchar_t wch;
sl@0: #endif
sl@0: 
sl@0: 
sl@0: RTest test(_L("T_HASHTAB"));
sl@0: TInt NanoTickPeriod;
sl@0: 
sl@0: typedef TBuf8<80> TTestName;
sl@0: typedef RHashSet<TInt> TIntSet;
sl@0: typedef RHashSet<TTestName> TNameSet;
sl@0: typedef RPtrHashSet<TDesC8> TStringSet8;
sl@0: typedef RPtrHashSet<TDesC16> TStringSet16;
sl@0: typedef RPtrHashMap<TDesC8,TDesC8> TStringMap8;
sl@0: typedef RPtrHashMap<TDesC16,TDesC16> TStringMap16;
sl@0: 
sl@0: #define INTSET(x)	TIntSet x
sl@0: #define NAMESET(x)	TNameSet x(&HashTestName, &TestNameIdentity)
sl@0: #define STRSET8(x)	TStringSet8 x
sl@0: #define STRSET16(x)	TStringSet16 x
sl@0: #define STRMAP8(x)	TStringMap8 x
sl@0: #define STRMAP16(x)	TStringMap16 x
sl@0: 
sl@0: RPointerArray<TDesC8> DesC8Array;
sl@0: RPointerArray<TDesC16> DesC16Array;
sl@0: 
sl@0: class HashTest : public RHashTableBase
sl@0: 	{
sl@0: public:
sl@0: 	HashTest() : RHashTableBase(0,0,0,0) {}
sl@0: 	using RHashTableBase::ConsistencyCheck;
sl@0: 	using RHashTableBase::Count;
sl@0: 	};
sl@0: 
sl@0: void CCheck(RHashTableBase& aHT)
sl@0: 	{
sl@0: 	TUint32 ci[1024];
sl@0: 	TUint32 dc;
sl@0: 	TUint32 cmp;
sl@0: 	HashTest* h = (HashTest*)&aHT;
sl@0: 	h->ConsistencyCheck(&dc, &cmp, 1024, ci);
sl@0: 	test.Printf(_L("Count = %d, Deleted = %d, Cmp = %d\n"), h->Count(), dc, cmp);
sl@0: 	TInt i;
sl@0: 	for (i=0; i<1024; ++i)
sl@0: 		{
sl@0: 		if (ci[i])
sl@0: 			test.Printf(_L("%d chains of length %d\n"), ci[i], i);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: const char* Numbers[] =
sl@0: 	{
sl@0: 	"zero",
sl@0: 	"one",
sl@0: 	"two",
sl@0: 	"three",
sl@0: 	"four",
sl@0: 	"five",
sl@0: 	"six",
sl@0: 	"seven",
sl@0: 	"eight",
sl@0: 	"nine",
sl@0: 	"ten",
sl@0: 	"eleven",
sl@0: 	"twelve",
sl@0: 	"thirteen",
sl@0: 	"fourteen",
sl@0: 	"fifteen",
sl@0: 	"sixteen",
sl@0: 	"seventeen",
sl@0: 	"eighteen",
sl@0: 	"nineteen",
sl@0: 	"twenty",
sl@0: 	"thirty",
sl@0: 	"forty",
sl@0: 	"fifty",
sl@0: 	"sixty",
sl@0: 	"seventy",
sl@0: 	"eighty",
sl@0: 	"ninety",
sl@0: 	"hundred",
sl@0: 	"thousand"
sl@0: 	};
sl@0: 
sl@0: TTestName NumberInWords(const TInt& aNum)
sl@0: 	{
sl@0: 	TInt a = aNum;
sl@0: 	TTestName n;
sl@0: 	if (a<20)
sl@0: 		{
sl@0: 		n.Copy((const TUint8*)Numbers[a]);
sl@0: 		return n;
sl@0: 		}
sl@0: 	if (a<100)
sl@0: 		{
sl@0: 		TInt tens = a/10;
sl@0: 		TInt units = a%10;
sl@0: 		n.Copy((const TUint8*)Numbers[tens-2+20]);
sl@0: 		if (units)
sl@0: 			{
sl@0: 			n.Append(' ');
sl@0: 			n.Append(TPtrC8((const TUint8*)Numbers[units]));
sl@0: 			}
sl@0: 		return n;
sl@0: 		}
sl@0: 	if (a<1000)
sl@0: 		{
sl@0: 		TInt h = a/100;
sl@0: 		n.Copy((const TUint8*)Numbers[h]);
sl@0: 		n.Append(' ');
sl@0: 		n.Append(TPtrC8((const TUint8*)Numbers[28]));
sl@0: 		a%=100;
sl@0: 		if (a)
sl@0: 			{
sl@0: 			TTestName n2(NumberInWords(a));
sl@0: 			n.Append(_L8(" and "));
sl@0: 			n+=n2;
sl@0: 			}
sl@0: 		return n;
sl@0: 		}
sl@0: 	TInt t = a/1000;
sl@0: 	n = NumberInWords(t);
sl@0: 	n.Append(' ');
sl@0: 	n.Append(TPtrC8((const TUint8*)Numbers[29]));
sl@0: 	a%=1000;
sl@0: 	if (a)
sl@0: 		{
sl@0: 		TTestName n2(NumberInWords(a));
sl@0: 		if (a<100)
sl@0: 			n.Append(_L8(" and "));
sl@0: 		else
sl@0: 			n.Append(' ');
sl@0: 		n+=n2;
sl@0: 		}
sl@0: 	return n;
sl@0: 	}
sl@0: 
sl@0: void PrintNumberInWords(TInt a)
sl@0: 	{
sl@0: 	TBuf<256> buf;
sl@0: 	TTestName n(NumberInWords(a));
sl@0: 	buf.Copy(n);
sl@0: 	test.Printf(_L("%d: %S\n"), a, &buf);
sl@0: 	}
sl@0: 
sl@0: TUint32 HashTestName(const TTestName& aN)
sl@0: 	{
sl@0: 	return DefaultHash::Des8(aN);
sl@0: 	}
sl@0: 
sl@0: TBool TestNameIdentity(const TTestName& aA, const TTestName& aB)
sl@0: 	{
sl@0: 	return aA == aB;
sl@0: 	}
sl@0: 
sl@0: /******************************************************************************
sl@0:  * Utility functions for RHashSet<T>
sl@0:  ******************************************************************************/
sl@0: template <class T>
sl@0: void Union(RHashSet<T>& aD, const RHashSet<T>& aS)
sl@0: 	{
sl@0: 	TInt c = aS.Count();
sl@0: 	TInt c2 = c;
sl@0: 	TInt d0 = aD.Count();
sl@0: 	TInt d1 = d0;
sl@0: 	typename RHashSet<T>::TIter iS(aS);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const T* p = iS.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c2;
sl@0: 		TInt r = aD.Insert(*p);
sl@0: 		test(r==KErrNone);
sl@0: 		++d1;
sl@0: 		}
sl@0: 	test(d1 == aD.Count());
sl@0: 	test(c2 == 0);
sl@0: 	}
sl@0: 
sl@0: template <class T>
sl@0: void Subtract(RHashSet<T>& aD, const RHashSet<T>& aS)
sl@0: 	{
sl@0: 	TInt c = aS.Count();
sl@0: 	TInt c2 = c;
sl@0: 	TInt d0 = aD.Count();
sl@0: 	TInt d1 = d0;
sl@0: 	TInt nfd = 0;
sl@0: 	typename RHashSet<T>::TIter iS(aS);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const T* p = iS.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c2;
sl@0: 		TInt r = aD.Remove(*p);
sl@0: 		test(r==KErrNone || r==KErrNotFound);
sl@0: 		if (r==KErrNotFound)
sl@0: 			++nfd;
sl@0: 		else
sl@0: 			--d1;
sl@0: 		}
sl@0: 	test(d1 == aD.Count());
sl@0: 	test(c2 == 0);
sl@0: 	test( (d0-d1) + nfd == c);
sl@0: 	}
sl@0: 
sl@0: template <class T>
sl@0: void Intersect(RHashSet<T>& aD, const RHashSet<T>& aS)
sl@0: 	{
sl@0: 	typename RHashSet<T>::TIter iD(aD);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const T* p = iD.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		if (!aS.Find(*p))
sl@0: 			iD.RemoveCurrent();
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: template <class T>
sl@0: void CheckIdentical(const RHashSet<T>& aA, const RHashSet<T>& aB)
sl@0: 	{
sl@0: 	test(aA.Count()==aB.Count());
sl@0: 	TInt c = aA.Count();
sl@0: 	typename RHashSet<T>::TIter iA(aA);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const T* p = iA.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c;
sl@0: 		test(aB.Find(*p)!=0);
sl@0: 		}
sl@0: 	test(c==0);
sl@0: 	c = aA.Count();
sl@0: 	typename RHashSet<T>::TIter iB(aB);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const T* p = iB.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c;
sl@0: 		test(aA.Find(*p)!=0);
sl@0: 		}
sl@0: 	test(c==0);
sl@0: 	}
sl@0: 
sl@0: 
sl@0: /******************************************************************************
sl@0:  * Utility functions for RPtrHashSet<T>
sl@0:  ******************************************************************************/
sl@0: template <class T>
sl@0: void Union(RPtrHashSet<T>& aD, const RPtrHashSet<T>& aS)
sl@0: 	{
sl@0: 	TInt c = aS.Count();
sl@0: 	TInt c2 = c;
sl@0: 	TInt d0 = aD.Count();
sl@0: 	TInt d1 = d0;
sl@0: 	typename RPtrHashSet<T>::TIter iS(aS);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const T* p = iS.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c2;
sl@0: 		TInt r = aD.Insert(p);
sl@0: 		test(r==KErrNone);
sl@0: 		++d1;
sl@0: 		}
sl@0: 	test(d1 == aD.Count());
sl@0: 	test(c2 == 0);
sl@0: 	}
sl@0: 
sl@0: template <class T>
sl@0: void Subtract(RPtrHashSet<T>& aD, const RPtrHashSet<T>& aS)
sl@0: 	{
sl@0: 	TInt c = aS.Count();
sl@0: 	TInt c2 = c;
sl@0: 	TInt d0 = aD.Count();
sl@0: 	TInt d1 = d0;
sl@0: 	TInt nfd = 0;
sl@0: 	typename RPtrHashSet<T>::TIter iS(aS);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const T* p = iS.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c2;
sl@0: 		TInt r = aD.Remove(p);
sl@0: 		test(r==KErrNone || r==KErrNotFound);
sl@0: 		if (r==KErrNotFound)
sl@0: 			++nfd;
sl@0: 		else
sl@0: 			--d1;
sl@0: 		}
sl@0: 	test(d1 == aD.Count());
sl@0: 	test(c2 == 0);
sl@0: 	test( (d0-d1) + nfd == c);
sl@0: 	}
sl@0: 
sl@0: template <class T>
sl@0: void Intersect(RPtrHashSet<T>& aD, const RPtrHashSet<T>& aS)
sl@0: 	{
sl@0: 	typename RPtrHashSet<T>::TIter iD(aD);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const T* p = iD.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		if (!aS.Find(*p))
sl@0: 			iD.RemoveCurrent();
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: template <class T>
sl@0: void CheckIdentical(const RPtrHashSet<T>& aA, const RPtrHashSet<T>& aB)
sl@0: 	{
sl@0: 	test(aA.Count()==aB.Count());
sl@0: 	TInt c = aA.Count();
sl@0: 	typename RPtrHashSet<T>::TIter iA(aA);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const T* p = iA.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c;
sl@0: 		test(aB.Find(*p)!=0);
sl@0: 		}
sl@0: 	test(c==0);
sl@0: 	c = aA.Count();
sl@0: 	typename RPtrHashSet<T>::TIter iB(aB);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const T* p = iB.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c;
sl@0: 		test(aA.Find(*p)!=0);
sl@0: 		}
sl@0: 	test(c==0);
sl@0: 	}
sl@0: 
sl@0: 
sl@0: /******************************************************************************
sl@0:  * Utility functions for RHashMap<K,V>
sl@0:  ******************************************************************************/
sl@0: template <class K, class V>
sl@0: void UnionTransform(RHashMap<K,V>& aD, const RHashSet<K>& aS, V (*aTransform)(const K&) )
sl@0: 	{
sl@0: 	TInt c = aS.Count();
sl@0: 	TInt c2 = c;
sl@0: 	TInt d0 = aD.Count();
sl@0: 	TInt d1 = d0;
sl@0: 	typename RHashSet<K>::TIter iS(aS);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const K* p = iS.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c2;
sl@0: 		TInt r = aD.Insert(*p, (*aTransform)(*p) );
sl@0: 		test(r==KErrNone);
sl@0: 		++d1;
sl@0: 		}
sl@0: 	test(d1 == aD.Count());
sl@0: 	test(c2 == 0);
sl@0: 	}
sl@0: 
sl@0: 
sl@0: template <class K, class V>
sl@0: void UnionMap(RHashSet<V>& aD, const RHashSet<K>& aS, const RHashMap<K,V>& aM)
sl@0: 	{
sl@0: 	TInt c = aS.Count();
sl@0: 	TInt c2 = c;
sl@0: 	TInt d0 = aD.Count();
sl@0: 	TInt d1 = d0;
sl@0: 	typename RHashSet<K>::TIter iS(aS);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const K* p = iS.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c2;
sl@0: 		const V* q = aM.Find(*p);
sl@0: 		if (!q)
sl@0: 			continue;
sl@0: 		TInt r = aD.Insert(*q);
sl@0: 		test(r==KErrNone);
sl@0: 		++d1;
sl@0: 		}
sl@0: 	test(d1 == aD.Count());
sl@0: 	test(c2 == 0);
sl@0: 	}
sl@0: 
sl@0: 
sl@0: template <class K, class V>
sl@0: void UnionKeys(RHashSet<K>& aD, const RHashMap<K,V>& aM)
sl@0: 	{
sl@0: 	typename RHashMap<K,V>::TIter iM(aM);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const K* p = iM.NextKey();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		aD.Insert(*p);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: 
sl@0: template <class K, class V>
sl@0: void UnionValues(RHashSet<V>& aD, const RHashMap<K,V>& aM)
sl@0: 	{
sl@0: 	typename RHashMap<K,V>::TIter iM(aM);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const K* p = iM.NextKey();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		const V* q = iM.CurrentValue();
sl@0: 		aD.Insert(*q);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: 
sl@0: template <class K, class V>
sl@0: void UnionTransform(RHashMap<K,V>& aD, const RHashMap<K,V>& aS, V (*aTransform)(const V&) )
sl@0: 	{
sl@0: 	TInt c = aS.Count();
sl@0: 	TInt c2 = c;
sl@0: 	TInt d0 = aD.Count();
sl@0: 	TInt d1 = d0;
sl@0: 	typename RHashMap<K,V>::TIter iS(aS);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const K* p = iS.NextKey();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c2;
sl@0: 		TInt r = aD.Insert(*p, (*aTransform)(*iS.CurrentValue()) );
sl@0: 		test(r==KErrNone);
sl@0: 		++d1;
sl@0: 		}
sl@0: 	test(d1 == aD.Count());
sl@0: 	test(c2 == 0);
sl@0: 	}
sl@0: 
sl@0: 
sl@0: template <class K, class V>
sl@0: void UnionInverse(RHashMap<V,K>& aD, const RHashMap<K,V>& aS)
sl@0: 	{
sl@0: 	TInt c = aS.Count();
sl@0: 	TInt c2 = c;
sl@0: 	TInt d0 = aD.Count();
sl@0: 	TInt d1 = d0;
sl@0: 	typename RHashMap<K,V>::TIter iS(aS);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const K* p = iS.NextKey();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c2;
sl@0: 		const V* q = iS.CurrentValue();
sl@0: 		TInt r = aD.Insert(*q, *p);
sl@0: 		test(r==KErrNone);
sl@0: 		++d1;
sl@0: 		}
sl@0: 	test(d1 == aD.Count());
sl@0: 	test(c2 == 0);
sl@0: 	}
sl@0: 
sl@0: template <class K, class V>
sl@0: void SetMap(RHashMap<V,K>& aM, const V& aV)
sl@0: 	{
sl@0: 	typename RHashMap<K,V>::TIter iM(aM);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const K* p = iM.NextKey();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		V* q = iM.CurrentValue();
sl@0: 		*q = aV;
sl@0: 		test(*q == aV);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: 
sl@0: /******************************************************************************
sl@0:  * Utility functions for RPtrHashMap<K,V>
sl@0:  ******************************************************************************/
sl@0: template <class K, class V>
sl@0: void UnionTransform(RPtrHashMap<K,V>& aD, const RPtrHashMap<K,V>& aS, V* (*aTransform)(const V*) )
sl@0: 	{
sl@0: 	TInt c = aS.Count();
sl@0: 	TInt c2 = c;
sl@0: 	TInt d0 = aD.Count();
sl@0: 	TInt d1 = d0;
sl@0: 	typename RPtrHashMap<K,V>::TIter iS(aS);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const K* p = iS.NextKey();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		--c2;
sl@0: 		TInt r = aD.Insert(p, (*aTransform)(iS.CurrentValue()) );
sl@0: 		test(r==KErrNone);
sl@0: 		++d1;
sl@0: 		}
sl@0: 	test(d1 == aD.Count());
sl@0: 	test(c2 == 0);
sl@0: 	}
sl@0: 
sl@0: 
sl@0: template <class A, class B>
sl@0: void UnionInverse(RPtrHashMap<B,A>& aD, const RPtrHashMap<A,B>& a1)
sl@0: 	{
sl@0: 	typename RPtrHashMap<A,B>::TIter iter(a1);
sl@0: 	const A* pA;
sl@0: 	while ( (pA=iter.NextKey()) != 0 )
sl@0: 		{
sl@0: 		const B* pB = iter.CurrentValue();
sl@0: 		TInt r = aD.Insert(pB, pA);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: 
sl@0: template <class A, class B, class C>
sl@0: void UnionCompose(RPtrHashMap<A,C>& aD, const RPtrHashMap<A,B>& a1, const RPtrHashMap<B,C>& a2)
sl@0: 	{
sl@0: 	typename RPtrHashMap<A,B>::TIter iter(a1);
sl@0: 	const A* pA;
sl@0: 	while ( (pA=iter.NextKey()) != 0 )
sl@0: 		{
sl@0: 		const B* pB = iter.CurrentValue();
sl@0: 		const C* pC = a2.Find(*pB);
sl@0: 		if (pC)
sl@0: 			{
sl@0: 			TInt r = aD.Insert(pA, pC);
sl@0: 			test(r==KErrNone);
sl@0: 			}
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: 
sl@0: template <class K, class V>
sl@0: void CheckIdenticalMaps(const RPtrHashMap<K,V>& aA, const RPtrHashMap<K,V>& aB)
sl@0: 	{
sl@0: 	test(aA.Count()==aB.Count());
sl@0: 	TInt c = aA.Count();
sl@0: 	const K* p;
sl@0: 	const V* q;
sl@0: 	typename RPtrHashMap<K,V>::TIter iA(aA);
sl@0: 	while( (p=iA.NextKey()) != 0)
sl@0: 		{
sl@0: 		--c;
sl@0: 		q = aB.Find(*p);
sl@0: 		test(q && q==iA.CurrentValue());
sl@0: 		}
sl@0: 	test(c==0);
sl@0: 	c = aB.Count();
sl@0: 	typename RPtrHashMap<K,V>::TIter iB(aB);
sl@0: 	while( (p=iB.NextKey()) != 0)
sl@0: 		{
sl@0: 		--c;
sl@0: 		q = aA.Find(*p);
sl@0: 		test(q && q==iB.CurrentValue());
sl@0: 		}
sl@0: 	test(c==0);
sl@0: 	}
sl@0: 
sl@0: 
sl@0: 
sl@0: 
sl@0: 
sl@0: /******************************************************************************
sl@0:  * Tests of TIntSet
sl@0:  ******************************************************************************/
sl@0: void Populate(TIntSet& aH, TInt aS, TInt aE, TInt aM)
sl@0: 	{
sl@0: 	TInt x = aS;
sl@0: 	for (; x<=aE; x+=aM)
sl@0: 		aH.Insert(x);
sl@0: 	}
sl@0: 
sl@0: void PrimeSieve(TIntSet& aH, TInt aStart, TInt aEnd)
sl@0: 	{
sl@0: 	TInt x;
sl@0: 	TInt e = (aEnd&1) ? aEnd : aEnd-1;
sl@0: 	TInt s = (aStart<2) ? 2 : aStart|1;
sl@0: 	for (x=s; x<=e; ++x)
sl@0: 		{
sl@0: //		test.Printf(_L("add %d\n"),x);
sl@0: 		aH.Insert(x);
sl@0: 		}
sl@0: 	TInt m=2;
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		for (; m*m<=e && !aH.Find(m); ++m)
sl@0: 			{}
sl@0: 		if (m*m > e)
sl@0: 			break;
sl@0: 		for (x=m*2; x<=e; x+=m)
sl@0: 			{
sl@0: //			test.Printf(_L("remove %d\n"),x);
sl@0: 			aH.Remove(x);
sl@0: 			}
sl@0: 		++m;
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: TBool IsPrime(TInt x)
sl@0: 	{
sl@0: 	if (x==2)
sl@0: 		return ETrue;
sl@0: 	if (!(x&1))
sl@0: 		return EFalse;
sl@0: 	TInt d;
sl@0: 	for (d=3; d*d<=x; d+=2)
sl@0: 		{
sl@0: 		if (x%d==0)
sl@0: 			return EFalse;
sl@0: 		}
sl@0: 	return ETrue;
sl@0: 	}
sl@0: 
sl@0: void CheckSieveOutput(TIntSet& aH)
sl@0: 	{
sl@0: 	RHashSet<TInt>::TIter iter(aH);
sl@0: 	TInt min = KMaxTInt;
sl@0: 	TInt max = KMinTInt;
sl@0: 	TInt c = 0;
sl@0: 	test.Printf(_L("%d elements:\n"),aH.Count());
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const TInt* p = iter.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		++c;
sl@0: 		if (*p>max) max=*p;
sl@0: 		if (*p<min) min=*p;
sl@0: //		test.Printf(_L("%d\n"),*p);
sl@0: 		test(IsPrime(*p));
sl@0: 		}
sl@0: 	test(c==aH.Count());
sl@0: 	TInt x;
sl@0: 	if (min==2)
sl@0: 		{
sl@0: 		test(aH.Find(2)!=0);
sl@0: 		min++;
sl@0: 		}
sl@0: 	for (x=min; x<=max; x+=2)
sl@0: 		{
sl@0: 		if (IsPrime(x))
sl@0: 			test(aH.Find(x)!=0);
sl@0: 		}
sl@0: 	for (x=min; x<=max; x+=2)
sl@0: 		{
sl@0: 		if (IsPrime(x))
sl@0: 			test(aH.Find(x)==&aH.FindL(x));
sl@0: 		else
sl@0: 			{
sl@0: 			TRAPD(rr,aH.FindL(x));
sl@0: 			test(rr==KErrNotFound);
sl@0: 			}
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: TUint32 CheckSmallHashSet(const TIntSet& aA)
sl@0: 	{
sl@0: 	TUint32 m = 0;
sl@0: 	RHashSet<TInt>::TIter iter(aA);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const TInt* p = iter.Next();
sl@0: 		if (!p)
sl@0: 			break;
sl@0: 		m |= (1<<*p);
sl@0: 		}
sl@0: 	return m;
sl@0: 	}
sl@0: 
sl@0: void AddToSmallHashSet(TIntSet& aA, TUint32 aMask)
sl@0: 	{
sl@0: 	CheckSmallHashSet(aA);
sl@0: 	TInt i;
sl@0: 	TInt r;
sl@0: 	for (i=0; i<32; ++i)
sl@0: 		{
sl@0: 		if (aMask & (1<<i))
sl@0: 			{
sl@0: 			r = aA.Insert(i);
sl@0: 			test(r==KErrNone);
sl@0: 			}
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void RemoveFromSmallHashSet(TIntSet& aA, TUint32 aMask)
sl@0: 	{
sl@0: 	TUint32 m = CheckSmallHashSet(aA);
sl@0: 	TInt i;
sl@0: 	TInt r;
sl@0: 	for (i=0; i<32; ++i)
sl@0: 		{
sl@0: 		if (aMask & (1<<i))
sl@0: 			{
sl@0: 			r = aA.Remove(i);
sl@0: 			if (m & (1<<i))
sl@0: 				test(r==KErrNone);
sl@0: 			else
sl@0: 				test(r==KErrNotFound);
sl@0: 			}
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TestHashSet()
sl@0: 	{
sl@0: 	test.Next(_L("Test RHashSet"));
sl@0: 
sl@0: 	INTSET(hs);
sl@0: 	CCheck(hs);		// check consistency for empty table
sl@0: 	INTSET(hs2);
sl@0: 	INTSET(hs3);
sl@0: 	PrimeSieve(hs, 1, 100);
sl@0: 	CheckSieveOutput(hs);
sl@0: 	test(hs.Reserve(1000)==KErrNone);
sl@0: 	CCheck(hs);
sl@0: 	CheckSieveOutput(hs);	// check that Reserve() preserves existing entries
sl@0: 
sl@0: 	INTSET(m1);
sl@0: 	INTSET(m2);
sl@0: 	INTSET(m3);
sl@0: 	INTSET(m5);
sl@0: 	INTSET(m7);
sl@0: 	Populate(m1,2,100,1);
sl@0: 	Populate(m2,4,100,2);
sl@0: 	Populate(m3,6,100,3);
sl@0: 	Populate(m5,10,100,5);
sl@0: 	Populate(m7,14,100,7);
sl@0: 	Union(hs3, m1);
sl@0: 	Subtract(hs3, m2);
sl@0: 	Subtract(hs3, m3);
sl@0: 	Subtract(hs3, m5);
sl@0: 	Subtract(hs3, m7);
sl@0: 	CheckSieveOutput(hs3);
sl@0: 	CheckIdentical(hs,hs3);
sl@0: 	hs3.Close();
sl@0: 	INTSET(cm2);
sl@0: 	INTSET(cm3);
sl@0: 	INTSET(cm5);
sl@0: 	INTSET(cm7);
sl@0: 	Union(cm2, m1);
sl@0: 	Subtract(cm2, m2);
sl@0: 	Union(cm3, m1);
sl@0: 	Subtract(cm3, m3);
sl@0: 	Union(cm5, m1);
sl@0: 	Subtract(cm5, m5);
sl@0: 	Union(cm7, m1);
sl@0: 	Subtract(cm7, m7);
sl@0: 	Union(hs3, m1);
sl@0: 	Intersect(hs3, cm7);
sl@0: 	Intersect(hs3, cm3);
sl@0: 	Intersect(hs3, cm5);
sl@0: 	Intersect(hs3, cm2);
sl@0: 	CheckSieveOutput(hs3);
sl@0: 	CheckIdentical(hs,hs3);
sl@0: 	hs3.Close();
sl@0: 
sl@0: 
sl@0: 	cm2.Close();
sl@0: 	cm3.Close();
sl@0: 	cm5.Close();
sl@0: 	cm7.Close();
sl@0: 	m1.Close();
sl@0: 	m2.Close();
sl@0: 	m3.Close();
sl@0: 	m5.Close();
sl@0: 	m7.Close();
sl@0: 
sl@0: 	PrimeSieve(hs2, 1, 1000);
sl@0: 	CheckSieveOutput(hs2);
sl@0: 	test(hs2.Reserve(1000)==KErrNone);
sl@0: 	CCheck(hs2);
sl@0: 	CheckSieveOutput(hs2);	// check that Reserve() preserves existing entries
sl@0: 
sl@0: 	PrimeSieve(hs, 100, 997);
sl@0: 	CheckSieveOutput(hs);
sl@0: 	CCheck(hs);
sl@0: 	CheckIdentical(hs,hs2);
sl@0: 
sl@0: 	hs2.Close();
sl@0: 	Union(hs2, hs);
sl@0: 	CheckIdentical(hs,hs2);
sl@0: 	CheckSieveOutput(hs2);
sl@0: 
sl@0: 	hs2.Close();
sl@0: 	hs.Close();
sl@0: 
sl@0: 	test(CheckSmallHashSet(hs)==0);
sl@0: 	AddToSmallHashSet(hs, 1);
sl@0: 	test(CheckSmallHashSet(hs)==1);
sl@0: 	AddToSmallHashSet(hs, 4);
sl@0: 	test(CheckSmallHashSet(hs)==5);
sl@0: 	AddToSmallHashSet(hs, 0x80000001);
sl@0: 	test(CheckSmallHashSet(hs)==0x80000005);
sl@0: 	AddToSmallHashSet(hs, 0x317217f8);
sl@0: 	test(CheckSmallHashSet(hs)==0xb17217fd);
sl@0: 	RemoveFromSmallHashSet(hs, 0x00000007);
sl@0: 	test(CheckSmallHashSet(hs)==0xb17217f8);
sl@0: 	RemoveFromSmallHashSet(hs, 0xffffffff);
sl@0: 	test(CheckSmallHashSet(hs)==0);
sl@0: 	hs.Close();
sl@0: 	}
sl@0: 
sl@0: void TestHashIter()
sl@0: 	{
sl@0: 	test.Next(_L("Test iterators"));
sl@0: 
sl@0: 	RHashSet<TInt> hs;		// empty
sl@0: 	RHashSet<TInt>::TIter iter(hs);
sl@0: 	test(iter.Next() == 0);
sl@0: 	test(iter.Current() == 0);
sl@0: 	iter.RemoveCurrent();
sl@0: 	test(iter.Next() == 0);
sl@0: 	test(iter.Current() == 0);
sl@0: 
sl@0: 	test(hs.Insert(1) == KErrNone);
sl@0: 	test(hs.Insert(2) == KErrNone);
sl@0: 	test(hs.Insert(3) == KErrNone);
sl@0: 	iter.Reset();
sl@0: 	TUint mask = 14;
sl@0: 	TInt i;
sl@0: 	for (i=0; i<3; ++i)
sl@0: 		{
sl@0: 		const TInt* p = iter.Next();
sl@0: 		test(p!=0);
sl@0: 		TInt x = *p;
sl@0: 		test (x>=1 && x<=3 && (mask&(1<<x))!=0);
sl@0: 		mask &= ~(1<<x);
sl@0: 		}
sl@0: 	test(iter.Next() == 0);
sl@0: 	test(mask==0);
sl@0: 	test(CheckSmallHashSet(hs)==0x0e);
sl@0: 	test(hs.Insert(4) == KErrNone);
sl@0: 	test(hs.Insert(5) == KErrNone);
sl@0: 	test(hs.Insert(6) == KErrNone);
sl@0: 	test(hs.Insert(7) == KErrNone);
sl@0: 	test(CheckSmallHashSet(hs)==0xfe);
sl@0: 	iter.Reset();
sl@0: 	while(iter.Next())
sl@0: 		{
sl@0: 		if ((*iter.Current() & 1) == 0)
sl@0: 			iter.RemoveCurrent();
sl@0: 		}
sl@0: 	test(CheckSmallHashSet(hs)==0xaa);
sl@0: 	iter.Reset();
sl@0: 	while(iter.Next())
sl@0: 		{
sl@0: 		iter.RemoveCurrent();
sl@0: 		}
sl@0: 	test(CheckSmallHashSet(hs)==0);
sl@0: 	iter.Reset();
sl@0: 	test(iter.Next() == 0);
sl@0: 	test(iter.Current() == 0);
sl@0: 	RHashSet<TInt> empty;
sl@0: 	CheckIdentical(hs, empty);
sl@0: #ifdef _DEBUG
sl@0: 	__UHEAP_FAILNEXT(1);
sl@0: 	test(empty.Insert(1)==KErrNoMemory);
sl@0: 	test(empty.Insert(1)==KErrNone);
sl@0: 	empty.Close();
sl@0: 	__UHEAP_FAILNEXT(1);
sl@0: 	test(hs.Insert(1)==KErrNone);
sl@0: 	hs.Close();
sl@0: 	__UHEAP_FAILNEXT(1);
sl@0: 	test(hs.Insert(1)==KErrNoMemory);
sl@0: #endif
sl@0: 	hs.Close();
sl@0: 	}
sl@0: 
sl@0: void Print(const char* aTitle, const RHashMap<TInt,TTestName>& aM)
sl@0: 	{
sl@0: 	TBuf<256> buf;
sl@0: 	buf.Copy(TPtrC8((const TUint8*)aTitle));
sl@0: 	test.Printf(_L("%S\n"), &buf);
sl@0: 	RHashMap<TInt,TTestName>::TIter iter(aM);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		const TInt* p = iter.NextKey();
sl@0: 		if (!p) break;
sl@0: 		buf.Copy(*iter.CurrentValue());
sl@0: 		test.Printf(_L("%d: %S\n"), *p, &buf);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void Print(const char* aTitle, const RHashSet<TTestName>& aS)
sl@0: 	{
sl@0: 	TBuf<256> buf;
sl@0: 	buf.Copy(TPtrC8((const TUint8*)aTitle));
sl@0: 	test.Printf(_L("%S\n"), &buf);
sl@0: 	RHashSet<TTestName>::TIter iter(aS);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		if (!iter.Next())
sl@0: 			break;
sl@0: 		buf.Copy(*iter.Current());
sl@0: 		test.Printf(_L("%S\n"), &buf);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TestHashMap()
sl@0: 	{
sl@0: 	test.Next(_L("Test RHashMap"));
sl@0: 
sl@0: 	RHashMap<TInt,TInt> ht;
sl@0: 	CCheck(ht);		// check consistency for empty table
sl@0: 	TInt x;
sl@0: 	for (x=0; x<200; x++)
sl@0: 		{
sl@0: 		TInt r = ht.Insert(x*x, x);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	test(ht.Count()==200);
sl@0: 
sl@0: 	TInt z = 0;
sl@0: 	TInt y;
sl@0: 	for (x=0; x<40000; x++)
sl@0: 		{
sl@0: 		const TInt* e = ht.Find(x);
sl@0: 		if (e)
sl@0: 			{
sl@0: 			const TInt& ee = ht.FindL(x);
sl@0: 			test(&ee==e);
sl@0: 			y = *e;
sl@0: //			test.Printf(_L("Find(%d) -> %d\n"), x, y);
sl@0: 			test(x == z*z);
sl@0: 			test(y == z);
sl@0: 			++z;
sl@0: 			}
sl@0: 		else
sl@0: 			{
sl@0: 			TRAPD(rr, ht.FindL(x));
sl@0: 			test(rr==KErrNotFound);
sl@0: 			}
sl@0: 		}
sl@0: 	CCheck(ht);
sl@0: 
sl@0: 	for (x=0; x<200; x++)
sl@0: 		{
sl@0: 		TInt r = ht.Insert(x*x*x, x);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	test(ht.Count()==200*2-6);
sl@0: 	CCheck(ht);
sl@0: 
sl@0: 	TInt sq = 0;
sl@0: 	TInt cb = 0;
sl@0: 	for (x=0; x<8000000; x++)
sl@0: 		{
sl@0: 		const TInt* e = ht.Find(x);
sl@0: 		if (e)
sl@0: 			{
sl@0: 			const TInt& ee = ht.FindL(x);
sl@0: 			test(&ee==e);
sl@0: 			y = *e;
sl@0: //			test.Printf(_L("Find(%d) -> %d\n"), x, y);
sl@0: 			if (x == cb*cb*cb)
sl@0: 				{
sl@0: 				test(y==cb);
sl@0: 				++cb;
sl@0: 				if (x == sq*sq)
sl@0: 					++sq;
sl@0: 				}
sl@0: 			else if (x == sq*sq)
sl@0: 				{
sl@0: 				test(y==sq);
sl@0: 				++sq;
sl@0: 				}
sl@0: 			}
sl@0: 		}
sl@0: 
sl@0: 	for (x=0; x<200; x++)
sl@0: 		{
sl@0: 		TInt r = ht.Remove(x*x);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	test(ht.Count()==200-6);
sl@0: 	CCheck(ht);
sl@0: 
sl@0: 	cb = 2;
sl@0: 	for (x=2; x<8000000; x++)
sl@0: 		{
sl@0: 		const TInt* e = ht.Find(x);
sl@0: 		if (e)
sl@0: 			{
sl@0: 			const TInt& ee = ht.FindL(x);
sl@0: 			test(&ee==e);
sl@0: 			y = *e;
sl@0: //			test.Printf(_L("Find(%d) -> %d\n"), x, y);
sl@0: 			if (cb == 4 || cb == 9 || cb == 16 || cb == 25) ++cb;
sl@0: 			test(x == cb*cb*cb);
sl@0: 			test(y == cb);
sl@0: 			++cb;
sl@0: 			}
sl@0: 		}
sl@0: 
sl@0: 	SetMap<TInt,TInt>(ht, 17);
sl@0: 
sl@0: 	ht.Close();
sl@0: 
sl@0: 	PrintNumberInWords(2000);
sl@0: 	PrintNumberInWords(2001);
sl@0: 	PrintNumberInWords(131072);
sl@0: 	PrintNumberInWords(111111);
sl@0: 	PrintNumberInWords(524288);
sl@0: 
sl@0: 	INTSET(all);
sl@0: 	Populate(all,0,1000,1);
sl@0: 	RHashMap<TInt,TTestName> to_words(&DefaultHash::Integer, &DefaultIdentity::Integer);
sl@0: 	UnionTransform<TInt,TTestName>(to_words, all, &NumberInWords);
sl@0: 	RHashMap<TTestName,TInt> from_words(&HashTestName, &TestNameIdentity);
sl@0: 	UnionInverse<TInt,TTestName>(from_words, to_words);
sl@0: //	Print("TO WORDS:", to_words);
sl@0: 	INTSET(primes);
sl@0: 	PrimeSieve(primes, 1, 100);
sl@0: //	Print("Primes 1-100", primes);
sl@0: 	RHashMap<TInt,TTestName> prime_map(&DefaultHash::Integer, &DefaultIdentity::Integer);
sl@0: 	UnionTransform<TInt,TTestName>(prime_map, primes, &NumberInWords);
sl@0: //	Print("Prime map 1-100", prime_map);
sl@0: 	INTSET(pmkeys);
sl@0: 	UnionKeys<TInt,TTestName>(pmkeys, prime_map);
sl@0: 	NAMESET(pmval);
sl@0: 	NAMESET(pmval2);
sl@0: 	UnionValues<TInt,TTestName>(pmval, prime_map);
sl@0: 	CheckIdentical(pmkeys, primes);
sl@0: 	INTSET(pr2);
sl@0: 	UnionMap<TTestName,TInt>(pr2, pmval, from_words);
sl@0: 	CheckIdentical(pr2, primes);
sl@0: 	pr2.Close();
sl@0: 	Union(pmval2, pmval);
sl@0: //	Print("pmval",pmval);
sl@0: //	Print("pmval2",pmval2);
sl@0: 	CheckIdentical(pmval2, pmval);
sl@0: 	UnionMap<TTestName,TInt>(pr2, pmval2, from_words);
sl@0: 	CheckIdentical(pr2, primes);
sl@0: 
sl@0: 	pr2.Close();
sl@0: 	pmval.Close();
sl@0: 	pmval2.Close();
sl@0: 	pmkeys.Close();
sl@0: 	prime_map.Close();
sl@0: 	primes.Close();
sl@0: 	all.Close();
sl@0: 
sl@0: 	INTSET(m);
sl@0: 	Populate(all,2,1000,1);
sl@0: 
sl@0: 	NAMESET(pr3);
sl@0: 	NAMESET(nm);
sl@0: 	UnionMap<TInt,TTestName>(pr3, all, to_words);
sl@0: 	all.Close();
sl@0: 	CCheck(pr3);
sl@0: 
sl@0: 	Populate(m,4,1000,2);
sl@0: 	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0: 	m.Close();
sl@0: 	Subtract(pr3, nm);
sl@0: 	nm.Close();
sl@0: 
sl@0: 	Populate(m,6,1000,3);
sl@0: 	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0: 	m.Close();
sl@0: 	Subtract(pr3, nm);
sl@0: 	nm.Close();
sl@0: 
sl@0: 	Populate(m,10,1000,5);
sl@0: 	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0: 	m.Close();
sl@0: 	Subtract(pr3, nm);
sl@0: 	nm.Close();
sl@0: 
sl@0: 	Populate(m,14,1000,7);
sl@0: 	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0: 	m.Close();
sl@0: 	Subtract(pr3, nm);
sl@0: 	nm.Close();
sl@0: 
sl@0: 	Populate(m,22,1000,11);
sl@0: 	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0: 	m.Close();
sl@0: 	Subtract(pr3, nm);
sl@0: 	nm.Close();
sl@0: 
sl@0: 	Populate(m,26,1000,13);
sl@0: 	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0: 	m.Close();
sl@0: 	Subtract(pr3, nm);
sl@0: 	nm.Close();
sl@0: 
sl@0: 	Populate(m,34,1000,17);
sl@0: 	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0: 	m.Close();
sl@0: 	Subtract(pr3, nm);
sl@0: 	nm.Close();
sl@0: 
sl@0: 	Populate(m,38,1000,19);
sl@0: 	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0: 	m.Close();
sl@0: 	Subtract(pr3, nm);
sl@0: 	nm.Close();
sl@0: 
sl@0: 	Populate(m,46,1000,23);
sl@0: 	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0: 	m.Close();
sl@0: 	Subtract(pr3, nm);
sl@0: 	nm.Close();
sl@0: 
sl@0: 	Populate(m,58,1000,29);
sl@0: 	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0: 	m.Close();
sl@0: 	Subtract(pr3, nm);
sl@0: 	nm.Close();
sl@0: 
sl@0: 	Populate(m,62,1000,31);
sl@0: 	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0: 	m.Close();
sl@0: 	Subtract(pr3, nm);
sl@0: 	nm.Close();
sl@0: 
sl@0: //	Print("pr3",pr3);
sl@0: 	PrimeSieve(primes, 1, 1000);
sl@0: 	UnionMap<TInt,TTestName>(nm, primes, to_words);
sl@0: 	CheckIdentical(nm, pr3);
sl@0: 	CCheck(pr3);
sl@0: 	UnionMap<TTestName,TInt>(m, pr3, from_words);
sl@0: 	CheckIdentical(m, primes);
sl@0: 
sl@0: 	m.Close();
sl@0: 	nm.Close();
sl@0: 	primes.Close();
sl@0: 	pr3.Close();
sl@0: 	from_words.Close();
sl@0: 	to_words.Close();
sl@0: 	}
sl@0: 
sl@0: void PopulateArray8(TInt aMax)
sl@0: 	{
sl@0: 	TInt i;
sl@0: 	for (i=0; i<aMax; ++i)
sl@0: 		{
sl@0: 		TTestName n(NumberInWords(i));
sl@0: 		HBufC8* p = n.Alloc();
sl@0: 		test(p!=0);
sl@0: 		TInt r = DesC8Array.Append(p);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void PopulateArray16(TInt aMax)
sl@0: 	{
sl@0: 	TInt i;
sl@0: 	for (i=0; i<aMax; ++i)
sl@0: 		{
sl@0: 		TTestName n(NumberInWords(i));
sl@0: 		TBuf<128> n16;
sl@0: 		n16.Copy(n);
sl@0: 		HBufC16* p = n16.Alloc();
sl@0: 		test(p!=0);
sl@0: 		TInt r = DesC16Array.Append(p);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: TUint32 istrh8(const TDesC8* const & a)
sl@0: 	{
sl@0: 	return DefaultHash::Des8(*a);
sl@0: 	}
sl@0: 
sl@0: TBool istrid8(const TDesC8* const & aA, const TDesC8* const & aB)
sl@0: 	{
sl@0: 	return *aA == *aB;
sl@0: 	}
sl@0: 
sl@0: TUint32 istrh16(const TDesC16* const & a)
sl@0: 	{
sl@0: 	return DefaultHash::Des16(*a);
sl@0: 	}
sl@0: 
sl@0: TBool istrid16(const TDesC16* const & aA, const TDesC16* const & aB)
sl@0: 	{
sl@0: 	return *aA == *aB;
sl@0: 	}
sl@0: 
sl@0: void TestPtrHashSet()
sl@0: 	{
sl@0: 	test.Next(_L("Test RPtrHashSet"));
sl@0: 
sl@0: 	STRSET8(s);
sl@0: 	CCheck(s);		// check consistency for empty table
sl@0: 	RHashMap<const TDesC8*, TInt> hm(&istrh8, &istrid8);
sl@0: 	RPtrHashSet<TDesC8>::TIter iter(s);
sl@0: 	const TDesC8* q;
sl@0: 	TInt i;
sl@0: 	for (i=0; i<4096; ++i)
sl@0: 		{
sl@0: 		TInt r = s.Insert(DesC8Array[i]);
sl@0: 		test(r==KErrNone);
sl@0: 		r = hm.Insert(DesC8Array[i], i);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	CCheck(s);
sl@0: 	for (i=0; i<4100; ++i)
sl@0: 		{
sl@0: 		TTestName n(NumberInWords(i));
sl@0: 		const TDesC8* p = s.Find(n);
sl@0: 		if (i<4096)
sl@0: 			{
sl@0: 			const TDesC8& pp = s.FindL(n);
sl@0: 			test(p && *p==n && p==DesC8Array[i]);
sl@0: 			test(&pp == p);
sl@0: 			}
sl@0: 		else
sl@0: 			{
sl@0: 			test(!p);
sl@0: 			TRAPD(rr,s.FindL(n));
sl@0: 			test(rr==KErrNotFound);
sl@0: 			}
sl@0: 		}
sl@0: 	while((q=iter.Next())!=0)
sl@0: 		{
sl@0: 		const TInt* qi = hm.Find(q);
sl@0: 		test(qi!=0 && *qi>=0 && *qi<4096);
sl@0: 		test(DesC8Array[*qi]==q);
sl@0: 		}
sl@0: 	for (i=0; i<4100; i+=2)
sl@0: 		{
sl@0: 		TTestName n(NumberInWords(i));
sl@0: 		TInt r = s.Remove(&n);
sl@0: 		if (i<4096)
sl@0: 			test(r==KErrNone);
sl@0: 		else
sl@0: 			test(r==KErrNotFound);
sl@0: 		}
sl@0: 	test(s.Count()==2048);
sl@0: 	CCheck(s);
sl@0: 	for (i=0; i<4100; ++i)
sl@0: 		{
sl@0: 		TTestName n(NumberInWords(i));
sl@0: 		const TDesC8* p = s.Find(n);
sl@0: 		if (i<4096 && (i&1))
sl@0: 			test(p && *p==n && p==DesC8Array[i]);
sl@0: 		else
sl@0: 			test(!p);
sl@0: 		}
sl@0: 	iter.Reset();
sl@0: 	while((q=iter.Next())!=0)
sl@0: 		{
sl@0: 		const TInt* qi = hm.Find(q);
sl@0: 		test(qi!=0 && *qi>=0 && *qi<4096 && (*qi&1));
sl@0: 		test(DesC8Array[*qi]==q);
sl@0: 		}
sl@0: 	for (i=2; i<4096; i+=4)
sl@0: 		{
sl@0: 		TInt r = s.Insert(DesC8Array[i]);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	test(s.Count()==3072);
sl@0: 	CCheck(s);
sl@0: 	for (i=0; i<4100; ++i)
sl@0: 		{
sl@0: 		TTestName n(NumberInWords(i));
sl@0: 		const TDesC8* p = s.Find(n);
sl@0: 		if (i<4096 && (i&3))
sl@0: 			test(p && *p==n && p==DesC8Array[i]);
sl@0: 		else
sl@0: 			test(!p);
sl@0: 		}
sl@0: 	iter.Reset();
sl@0: 	while((q=iter.Next())!=0)
sl@0: 		{
sl@0: 		const TInt* qi = hm.Find(q);
sl@0: 		test(qi!=0 && *qi>=0 && *qi<4096 && (*qi&3));
sl@0: 		test(DesC8Array[*qi]==q);
sl@0: 		}
sl@0: 	s.Close();
sl@0: 
sl@0: 	// test ResetAndDestroy
sl@0: 	for (i=0; i<16; ++i)
sl@0: 		{
sl@0: 		TInt r = s.Insert(DesC8Array[i]->Alloc());
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	iter.Reset();
sl@0: 	while((q=iter.Next())!=0)
sl@0: 		{
sl@0: 		const TInt* qi = hm.Find(q);
sl@0: 		test(qi!=0 && *qi>=0 && *qi<16);
sl@0: 		test(*DesC8Array[*qi]==*q);
sl@0: 		test(DesC8Array[*qi]!=q);
sl@0: 		}
sl@0: 	s.ResetAndDestroy();
sl@0: 	hm.Close();
sl@0: 
sl@0: 
sl@0: 	STRSET16(S);
sl@0: 	RHashMap<const TDesC16*, TInt> HM(&istrh16, &istrid16);
sl@0: 	RPtrHashSet<TDesC16>::TIter ITER(S);
sl@0: 	const TDesC16* Q;
sl@0: 	for (i=0; i<4096; ++i)
sl@0: 		{
sl@0: 		TInt r = S.Insert(DesC16Array[i]);
sl@0: 		test(r==KErrNone);
sl@0: 		r = HM.Insert(DesC16Array[i], i);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	CCheck(S);
sl@0: 	for (i=0; i<4100; ++i)
sl@0: 		{
sl@0: 		TTestName n(NumberInWords(i));
sl@0: 		TBuf<80> buf;
sl@0: 		buf.Copy(n);
sl@0: 		const TDesC16* p = S.Find(buf);
sl@0: 		if (i<4096)
sl@0: 			test(p && *p==buf && p==DesC16Array[i]);
sl@0: 		else
sl@0: 			test(!p);
sl@0: 		}
sl@0: 	while((Q=ITER.Next())!=0)
sl@0: 		{
sl@0: 		const TInt* qi = HM.Find(Q);
sl@0: 		test(qi!=0 && *qi>=0 && *qi<4096);
sl@0: 		test(DesC16Array[*qi]==Q);
sl@0: 		}
sl@0: 	for (i=0; i<4100; i+=2)
sl@0: 		{
sl@0: 		TTestName n(NumberInWords(i));
sl@0: 		TBuf<80> buf;
sl@0: 		buf.Copy(n);
sl@0: 		TInt r = S.Remove(&buf);
sl@0: 		if (i<4096)
sl@0: 			test(r==KErrNone);
sl@0: 		else
sl@0: 			test(r==KErrNotFound);
sl@0: 		}
sl@0: 	test(S.Count()==2048);
sl@0: 	CCheck(S);
sl@0: 	for (i=0; i<4100; ++i)
sl@0: 		{
sl@0: 		TTestName n(NumberInWords(i));
sl@0: 		TBuf<80> buf;
sl@0: 		buf.Copy(n);
sl@0: 		const TDesC16* p = S.Find(buf);
sl@0: 		if (i<4096 && (i&1))
sl@0: 			test(p && *p==buf && p==DesC16Array[i]);
sl@0: 		else
sl@0: 			test(!p);
sl@0: 		}
sl@0: 	ITER.Reset();
sl@0: 	while((Q=ITER.Next())!=0)
sl@0: 		{
sl@0: 		const TInt* qi = HM.Find(Q);
sl@0: 		test(qi!=0 && *qi>=0 && *qi<4096 && (*qi&1));
sl@0: 		test(DesC16Array[*qi]==Q);
sl@0: 		}
sl@0: 	for (i=2; i<4096; i+=4)
sl@0: 		{
sl@0: 		TInt r = S.Insert(DesC16Array[i]);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	test(S.Count()==3072);
sl@0: 	CCheck(S);
sl@0: 	for (i=0; i<4100; ++i)
sl@0: 		{
sl@0: 		TTestName n(NumberInWords(i));
sl@0: 		TBuf<80> buf;
sl@0: 		buf.Copy(n);
sl@0: 		const TDesC16* p = S.Find(buf);
sl@0: 		if (i<4096 && (i&3))
sl@0: 			test(p && *p==buf && p==DesC16Array[i]);
sl@0: 		else
sl@0: 			test(!p);
sl@0: 		}
sl@0: 	ITER.Reset();
sl@0: 	while((Q=ITER.Next())!=0)
sl@0: 		{
sl@0: 		const TInt* qi = HM.Find(Q);
sl@0: 		test(qi!=0 && *qi>=0 && *qi<4096 && (*qi&3));
sl@0: 		test(DesC16Array[*qi]==Q);
sl@0: 		}
sl@0: 	S.Close();
sl@0: 
sl@0: 	// test ResetAndDestroy
sl@0: 	for (i=0; i<16; ++i)
sl@0: 		{
sl@0: 		TInt r = S.Insert(DesC16Array[i]->Alloc());
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	ITER.Reset();
sl@0: 	while((Q=ITER.Next())!=0)
sl@0: 		{
sl@0: 		const TInt* qi = HM.Find(Q);
sl@0: 		test(qi!=0 && *qi>=0 && *qi<16);
sl@0: 		test(*DesC16Array[*qi]==*Q);
sl@0: 		test(DesC16Array[*qi]!=Q);
sl@0: 		}
sl@0: 	S.ResetAndDestroy();
sl@0: 	HM.Close();
sl@0: 	}
sl@0: 
sl@0: void TestPtrHashMap()
sl@0: 	{
sl@0: 	test.Next(_L("Test RPtrHashMap"));
sl@0: 
sl@0: 	STRMAP8(map);
sl@0: 	CCheck(map);		// check consistency for empty table
sl@0: 	STRMAP8(id);
sl@0: 	TInt i;
sl@0: 	for (i=0; i<4096; ++i)
sl@0: 		{
sl@0: 		TInt r = map.Insert(DesC8Array[i], DesC8Array[(i+1)&0xfff]);
sl@0: 		test(r==KErrNone);
sl@0: 		r = id.Insert(DesC8Array[i], DesC8Array[i]);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	for (i=0; i<4096; ++i)
sl@0: 		{
sl@0: 		const TDesC8* p = map.Find(*DesC8Array[i]);
sl@0: 		test(p == DesC8Array[(i+1)&0xfff]);
sl@0: 		const TDesC8& pp = map.FindL(*DesC8Array[i]);
sl@0: 		test(&pp == p);
sl@0: 		}
sl@0: 	TRAPD(rr,map.FindL(_L8("two")));
sl@0: 	test(rr==KErrNone);
sl@0: 	TRAP(rr,map.FindL(_L8("twx")));
sl@0: 	test(rr==KErrNotFound);
sl@0: 	CCheck(map);
sl@0: 	STRMAP8(map2);
sl@0: 	STRMAP8(mapi);
sl@0: 	STRMAP8(map3);
sl@0: 	UnionInverse<TDesC8,TDesC8>(mapi, map);
sl@0: 	UnionCompose<TDesC8,TDesC8,TDesC8>(map2, map, map);
sl@0: 	UnionCompose<TDesC8,TDesC8,TDesC8>(map3, map, mapi);
sl@0: 	CheckIdenticalMaps<TDesC8,TDesC8>(map3, id);
sl@0: 	map3.Close();
sl@0: 	UnionCompose<TDesC8,TDesC8,TDesC8>(map3, map2, mapi);
sl@0: 	CheckIdenticalMaps<TDesC8,TDesC8>(map3, map);
sl@0: 	map3.Close();
sl@0: 	for (i=0; i<4096; ++i)
sl@0: 		{
sl@0: 		TInt r = map3.Insert(DesC8Array[i], DesC8Array[(i+2)&0xfff]);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	CheckIdenticalMaps<TDesC8,TDesC8>(map3, map2);
sl@0: 	map3.Close();
sl@0: 
sl@0: 	mapi.Close();
sl@0: 	map2.Close();
sl@0: 	id.Close();
sl@0: 	map.Close();
sl@0: 
sl@0: 	// test ResetAndDestroy()
sl@0: 	for(i=0; i<16; ++i)
sl@0: 		{
sl@0: 		TInt r = map.Insert(DesC8Array[i]->Alloc(), DesC8Array[i*i]->Alloc());
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	map.ResetAndDestroy();
sl@0: 	}
sl@0: 
sl@0: void TestOOM()
sl@0: 	{
sl@0: 	// Max out memory and check it still works
sl@0: 	test.Next(_L("Test OOM"));
sl@0: 
sl@0: 	TInt x = 0;
sl@0: 	TInt n = 0;
sl@0: 	TInt r;
sl@0: 	INTSET(set);
sl@0: 	FOREVER
sl@0: 		{
sl@0: 		x += 0x58b90bfb;
sl@0: 		r = set.Insert(x);
sl@0: 		if (r != KErrNone)
sl@0: 			break;
sl@0: 		++n;
sl@0: 		}
sl@0: 	test(r==KErrNoMemory);
sl@0: 	TRAPD(rr,set.InsertL(x));
sl@0: 	test(rr==KErrNoMemory);
sl@0: 	test.Printf(_L("%d integers stored\n"), n);
sl@0: 	test(set.Count()==n);
sl@0: 	TRAP(rr,set.InsertL(0x58b90bfb));	// already there
sl@0: 	test(rr==KErrNone);	// should succeed
sl@0: 
sl@0: 	// final count should be a power of 2 minus 1
sl@0: 	test( (n&(n+1)) == 0 );
sl@0: 
sl@0: 	x = 0;
sl@0: 	TInt i;
sl@0: 	for (i=0; i<=n; ++i)		// check everything has been stored correctly
sl@0: 		{
sl@0: 		x += 0x58b90bfb;
sl@0: 		const TInt* p = set.Find(x);
sl@0: 		if (i < n)
sl@0: 			test(p && *p == x);
sl@0: 		else
sl@0: 			test(!p);
sl@0: 		}
sl@0: 	set.Close();
sl@0: 	TInt nn;
sl@0: 	for (nn=256; nn<=n+256; nn+=256)
sl@0: 		{
sl@0: 		r = set.Reserve(nn);
sl@0: 		set.Close();
sl@0: 		if (r!=KErrNone)
sl@0: 			break;
sl@0: 		}
sl@0: 	test.Printf(_L("Max reserve %d\n"),nn);
sl@0: 	TInt thresh = 3*((n+1)>>2);
sl@0: 	test(nn == thresh + 256);
sl@0: 	}
sl@0: 
sl@0: class RDummyAllocator : public RAllocator
sl@0: 	{
sl@0: public:
sl@0: 	virtual TAny* Alloc(TInt) {test(0); return 0;}
sl@0: 	virtual void Free(TAny*) {test(0);}
sl@0: 	virtual TAny* ReAlloc(TAny*, TInt, TInt) {test(0); return 0;}
sl@0: 	virtual TInt AllocLen(const TAny*) const  {test(0); return 0;}
sl@0: 	virtual TInt Compress() {test(0); return 0;}
sl@0: 	virtual void Reset() {test(0);}
sl@0: 	virtual TInt AllocSize(TInt&) const  {test(0); return 0;}
sl@0: 	virtual TInt Available(TInt&) const  {test(0); return 0;}
sl@0: 	virtual TInt DebugFunction(TInt, TAny*, TAny*) {test(0); return 0;}
sl@0: 	virtual TInt Extension_(TUint, TAny*&, TAny*) {test(0); return 0;}
sl@0: 	};
sl@0: 
sl@0: void IntegerBenchmark(TInt aCount, TBool aReserve)
sl@0: 	{
sl@0: 	RArray<TInt> array;
sl@0: 	TUint32 before, after, diff;
sl@0: 	TInt x=0;
sl@0: 	TInt i;
sl@0: 	double avg;
sl@0: 
sl@0: 	test.Printf(_L("**** INTEGER BENCHMARKS ***\n"));
sl@0: 
sl@0: 	if (!aReserve)
sl@0: 		{
sl@0: 		before = User::NTickCount();
sl@0: 		for (i=0; i<aCount; ++i)
sl@0: 			{
sl@0: 			x += 0x58b90bfb;
sl@0: 			TInt r = array.InsertInOrder(x);
sl@0: 			test(r==KErrNone);
sl@0: 			}
sl@0: 		after = User::NTickCount();
sl@0: 		diff = after - before;
sl@0: 		diff *= NanoTickPeriod;
sl@0: 		avg = (double)diff / (double)aCount;
sl@0: 		test.Printf(_L("ARRAY:      %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 		x=0;
sl@0: 		before = User::NTickCount();
sl@0: 		for (i=0; i<aCount; ++i)
sl@0: 			{
sl@0: 			x += 0x58b90bfb;
sl@0: 			TInt r = array.FindInOrder(x);
sl@0: 			test(r>=0);
sl@0: 			}
sl@0: 		after = User::NTickCount();
sl@0: 		diff = after - before;
sl@0: 		diff *= NanoTickPeriod;
sl@0: 		avg = (double)diff / (double)aCount;
sl@0: 		test.Printf(_L("ARRAY:      %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 		before = User::NTickCount();
sl@0: 		for (i=0; i<aCount; ++i)
sl@0: 			{
sl@0: 			x += 0x58b90bfb;
sl@0: 			TInt r = array.FindInOrder(x);
sl@0: 			test(r==KErrNotFound);
sl@0: 			}
sl@0: 		after = User::NTickCount();
sl@0: 		diff = after - before;
sl@0: 		diff *= NanoTickPeriod;
sl@0: 		avg = (double)diff / (double)aCount;
sl@0: 		test.Printf(_L("ARRAY:      %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 		x=0;
sl@0: 		before = User::NTickCount();
sl@0: 		for (i=0; i<aCount; ++i)
sl@0: 			{
sl@0: 			x += 0x58b90bfb;
sl@0: 			TInt r = array.FindInOrder(x);
sl@0: 			test(r>=0);
sl@0: 			array.Remove(r);
sl@0: 			}
sl@0: 		after = User::NTickCount();
sl@0: 		diff = after - before;
sl@0: 		diff *= NanoTickPeriod;
sl@0: 		avg = (double)diff / (double)aCount;
sl@0: 		test.Printf(_L("ARRAY:      %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 		array.Close();
sl@0: 		}
sl@0: 
sl@0: 	INTSET(set);
sl@0: 	x=0;
sl@0: 	RAllocator* pA = 0;
sl@0: 	RDummyAllocator da;
sl@0: 	if (aReserve)
sl@0: 		{
sl@0: 		test(set.Reserve(aCount)==KErrNone);
sl@0: 		pA = User::SwitchAllocator(&da);			// check that no memory accesses occur
sl@0: 		test(set.Reserve(10)==KErrNone);			// shouldn't need to do anything
sl@0: 		test(set.Reserve(aCount/2)==KErrNone);		// shouldn't need to do anything
sl@0: 		test(set.Reserve(aCount)==KErrNone);		// shouldn't need to do anything
sl@0: 		}
sl@0: 	before = User::NTickCount();
sl@0: 	for (i=0; i<aCount; ++i)
sl@0: 		{
sl@0: 		x += 0x58b90bfb;
sl@0: 		TInt r = set.Insert(x);	// we have no heap here so this tests that Reserve() has preallocated sufficient memory
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	after = User::NTickCount();
sl@0: 	diff = after - before;
sl@0: 	diff *= NanoTickPeriod;
sl@0: 	avg = (double)diff / (double)aCount;
sl@0: 	if (aReserve)
sl@0: 		User::SwitchAllocator(pA);
sl@0: 	test.Printf(_L("HASH TABLE: %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 	x=0;
sl@0: 	before = User::NTickCount();
sl@0: 	for (i=0; i<aCount; ++i)
sl@0: 		{
sl@0: 		x += 0x58b90bfb;
sl@0: 		const TInt* p = set.Find(x);
sl@0: 		test(p!=0);
sl@0: 		}
sl@0: 	after = User::NTickCount();
sl@0: 	diff = after - before;
sl@0: 	diff *= NanoTickPeriod;
sl@0: 	avg = (double)diff / (double)aCount;
sl@0: 	test.Printf(_L("HASH TABLE: %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 	before = User::NTickCount();
sl@0: 	for (i=0; i<aCount; ++i)
sl@0: 		{
sl@0: 		x += 0x58b90bfb;
sl@0: 		const TInt* p = set.Find(x);
sl@0: 		test(!p);
sl@0: 		}
sl@0: 	after = User::NTickCount();
sl@0: 	diff = after - before;
sl@0: 	diff *= NanoTickPeriod;
sl@0: 	avg = (double)diff / (double)aCount;
sl@0: 	test.Printf(_L("HASH TABLE: %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 	x=0;
sl@0: 	before = User::NTickCount();
sl@0: 	for (i=0; i<aCount; ++i)
sl@0: 		{
sl@0: 		x += 0x58b90bfb;
sl@0: 		TInt r = set.Remove(x);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	after = User::NTickCount();
sl@0: 	diff = after - before;
sl@0: 	diff *= NanoTickPeriod;
sl@0: 	avg = (double)diff / (double)aCount;
sl@0: 	test.Printf(_L("HASH TABLE: %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 	set.Close();
sl@0: 	}
sl@0: 
sl@0: TInt des8order(const TDesC8& aA, const TDesC8& aB)
sl@0: 	{
sl@0: 	return aA.Compare(aB);
sl@0: 	}
sl@0: 
sl@0: void StringBenchmark8(TInt aCount, TBool aReserve)
sl@0: 	{
sl@0: 	RPointerArray<TDesC8> array;
sl@0: 	TUint32 before, after, diff;
sl@0: 	TInt x=0;
sl@0: 	TInt i;
sl@0: 	double avg;
sl@0: 	const TDesC8** base = (const TDesC8**)&DesC8Array[0];
sl@0: 	test(base[1331] == DesC8Array[1331]);
sl@0: 
sl@0: 	test.Printf(_L("**** 8 BIT STRING BENCHMARKS ***\n"));
sl@0: 
sl@0: 	if (!aReserve)
sl@0: 		{
sl@0: 		before = User::NTickCount();
sl@0: 		for (i=0; i<aCount; ++i)
sl@0: 			{
sl@0: 			x = (x+4339)&0x3fff;
sl@0: 			TInt r = array.InsertInOrder(base[x], &des8order);
sl@0: 			test(r==KErrNone);
sl@0: 			}
sl@0: 		after = User::NTickCount();
sl@0: 		diff = after - before;
sl@0: 		diff *= NanoTickPeriod;
sl@0: 		avg = (double)diff / (double)aCount;
sl@0: 		test.Printf(_L("ARRAY:      %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 		x=0;
sl@0: 		before = User::NTickCount();
sl@0: 		for (i=0; i<aCount; ++i)
sl@0: 			{
sl@0: 			x = (x+4339)&0x3fff;
sl@0: 			TInt r = array.FindInOrder(base[x], &des8order);
sl@0: 			test(r>=0);
sl@0: 			}
sl@0: 		after = User::NTickCount();
sl@0: 		diff = after - before;
sl@0: 		diff *= NanoTickPeriod;
sl@0: 		avg = (double)diff / (double)aCount;
sl@0: 		test.Printf(_L("ARRAY:      %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 		before = User::NTickCount();
sl@0: 		for (i=0; i<aCount; ++i)
sl@0: 			{
sl@0: 			x = (x+4339)&0x3fff;
sl@0: 			TInt r = array.FindInOrder(base[x], &des8order);
sl@0: 			test(r==KErrNotFound);
sl@0: 			}
sl@0: 		after = User::NTickCount();
sl@0: 		diff = after - before;
sl@0: 		diff *= NanoTickPeriod;
sl@0: 		avg = (double)diff / (double)aCount;
sl@0: 		test.Printf(_L("ARRAY:      %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 		x=0;
sl@0: 		before = User::NTickCount();
sl@0: 		for (i=0; i<aCount; ++i)
sl@0: 			{
sl@0: 			x = (x+4339)&0x3fff;
sl@0: 			TInt r = array.FindInOrder(base[x], &des8order);
sl@0: 			test(r>=0);
sl@0: 			array.Remove(r);
sl@0: 			}
sl@0: 		after = User::NTickCount();
sl@0: 		diff = after - before;
sl@0: 		diff *= NanoTickPeriod;
sl@0: 		avg = (double)diff / (double)aCount;
sl@0: 		test.Printf(_L("ARRAY:      %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 		array.Close();
sl@0: 		}
sl@0: 
sl@0: 	STRSET8(set);
sl@0: 	x=0;
sl@0: 	if (aReserve)
sl@0: 		test(set.Reserve(aCount)==KErrNone);
sl@0: 	before = User::NTickCount();
sl@0: 	for (i=0; i<aCount; ++i)
sl@0: 		{
sl@0: 		x = (x+4339)&0x3fff;
sl@0: 		TInt r = set.Insert(base[x]);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	after = User::NTickCount();
sl@0: 	diff = after - before;
sl@0: 	diff *= NanoTickPeriod;
sl@0: 	avg = (double)diff / (double)aCount;
sl@0: 	test.Printf(_L("HASH TABLE: %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 	x=0;
sl@0: 	before = User::NTickCount();
sl@0: 	for (i=0; i<aCount; ++i)
sl@0: 		{
sl@0: 		x = (x+4339)&0x3fff;
sl@0: 		const TDesC8* p = set.Find(*base[x]);
sl@0: 		test(p!=0);
sl@0: 		}
sl@0: 	after = User::NTickCount();
sl@0: 	diff = after - before;
sl@0: 	diff *= NanoTickPeriod;
sl@0: 	avg = (double)diff / (double)aCount;
sl@0: 	test.Printf(_L("HASH TABLE: %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 	before = User::NTickCount();
sl@0: 	for (i=0; i<aCount; ++i)
sl@0: 		{
sl@0: 		x = (x+4339)&0x3fff;
sl@0: 		const TDesC8* p = set.Find(*base[x]);
sl@0: 		test(!p);
sl@0: 		}
sl@0: 	after = User::NTickCount();
sl@0: 	diff = after - before;
sl@0: 	diff *= NanoTickPeriod;
sl@0: 	avg = (double)diff / (double)aCount;
sl@0: 	test.Printf(_L("HASH TABLE: %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 	x=0;
sl@0: 	before = User::NTickCount();
sl@0: 	for (i=0; i<aCount; ++i)
sl@0: 		{
sl@0: 		x = (x+4339)&0x3fff;
sl@0: 		TInt r = set.Remove(base[x]);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	after = User::NTickCount();
sl@0: 	diff = after - before;
sl@0: 	diff *= NanoTickPeriod;
sl@0: 	avg = (double)diff / (double)aCount;
sl@0: 	test.Printf(_L("HASH TABLE: %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 	set.Close();
sl@0: 	}
sl@0: 
sl@0: TInt des16order(const TDesC16& aA, const TDesC16& aB)
sl@0: 	{
sl@0: 	return aA.Compare(aB);
sl@0: 	}
sl@0: 
sl@0: void StringBenchmark16(TInt aCount, TBool aReserve)
sl@0: 	{
sl@0: 	RPointerArray<TDesC16> array;
sl@0: 	TUint32 before, after, diff;
sl@0: 	TInt x=0;
sl@0: 	TInt i;
sl@0: 	double avg;
sl@0: 	const TDesC16** base = (const TDesC16**)&DesC16Array[0];
sl@0: 	test(base[1331] == DesC16Array[1331]);
sl@0: 
sl@0: 	test.Printf(_L("**** 16 BIT STRING BENCHMARKS ***\n"));
sl@0: 
sl@0: 	if (!aReserve)
sl@0: 		{
sl@0: 		before = User::NTickCount();
sl@0: 		for (i=0; i<aCount; ++i)
sl@0: 			{
sl@0: 			x = (x+4339)&0x3fff;
sl@0: 			TInt r = array.InsertInOrder(base[x], &des16order);
sl@0: 			test(r==KErrNone);
sl@0: 			}
sl@0: 		after = User::NTickCount();
sl@0: 		diff = after - before;
sl@0: 		diff *= NanoTickPeriod;
sl@0: 		avg = (double)diff / (double)aCount;
sl@0: 		test.Printf(_L("ARRAY:      %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 		x=0;
sl@0: 		before = User::NTickCount();
sl@0: 		for (i=0; i<aCount; ++i)
sl@0: 			{
sl@0: 			x = (x+4339)&0x3fff;
sl@0: 			TInt r = array.FindInOrder(base[x], &des16order);
sl@0: 			test(r>=0);
sl@0: 			}
sl@0: 		after = User::NTickCount();
sl@0: 		diff = after - before;
sl@0: 		diff *= NanoTickPeriod;
sl@0: 		avg = (double)diff / (double)aCount;
sl@0: 		test.Printf(_L("ARRAY:      %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 		before = User::NTickCount();
sl@0: 		for (i=0; i<aCount; ++i)
sl@0: 			{
sl@0: 			x = (x+4339)&0x3fff;
sl@0: 			TInt r = array.FindInOrder(base[x], &des16order);
sl@0: 			test(r==KErrNotFound);
sl@0: 			}
sl@0: 		after = User::NTickCount();
sl@0: 		diff = after - before;
sl@0: 		diff *= NanoTickPeriod;
sl@0: 		avg = (double)diff / (double)aCount;
sl@0: 		test.Printf(_L("ARRAY:      %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 		x=0;
sl@0: 		before = User::NTickCount();
sl@0: 		for (i=0; i<aCount; ++i)
sl@0: 			{
sl@0: 			x = (x+4339)&0x3fff;
sl@0: 			TInt r = array.FindInOrder(base[x], &des16order);
sl@0: 			test(r>=0);
sl@0: 			array.Remove(r);
sl@0: 			}
sl@0: 		after = User::NTickCount();
sl@0: 		diff = after - before;
sl@0: 		diff *= NanoTickPeriod;
sl@0: 		avg = (double)diff / (double)aCount;
sl@0: 		test.Printf(_L("ARRAY:      %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 		array.Close();
sl@0: 		}
sl@0: 
sl@0: 	STRSET16(set);
sl@0: 	x=0;
sl@0: 	if (aReserve)
sl@0: 		test(set.Reserve(aCount)==KErrNone);
sl@0: 	before = User::NTickCount();
sl@0: 	for (i=0; i<aCount; ++i)
sl@0: 		{
sl@0: 		x = (x+4339)&0x3fff;
sl@0: 		TInt r = set.Insert(base[x]);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	after = User::NTickCount();
sl@0: 	diff = after - before;
sl@0: 	diff *= NanoTickPeriod;
sl@0: 	avg = (double)diff / (double)aCount;
sl@0: 	test.Printf(_L("HASH TABLE: %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 	x=0;
sl@0: 	before = User::NTickCount();
sl@0: 	for (i=0; i<aCount; ++i)
sl@0: 		{
sl@0: 		x = (x+4339)&0x3fff;
sl@0: 		const TDesC16* p = set.Find(*base[x]);
sl@0: 		test(p!=0);
sl@0: 		}
sl@0: 	after = User::NTickCount();
sl@0: 	diff = after - before;
sl@0: 	diff *= NanoTickPeriod;
sl@0: 	avg = (double)diff / (double)aCount;
sl@0: 	test.Printf(_L("HASH TABLE: %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 	before = User::NTickCount();
sl@0: 	for (i=0; i<aCount; ++i)
sl@0: 		{
sl@0: 		x = (x+4339)&0x3fff;
sl@0: 		const TDesC16* p = set.Find(*base[x]);
sl@0: 		test(!p);
sl@0: 		}
sl@0: 	after = User::NTickCount();
sl@0: 	diff = after - before;
sl@0: 	diff *= NanoTickPeriod;
sl@0: 	avg = (double)diff / (double)aCount;
sl@0: 	test.Printf(_L("HASH TABLE: %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 
sl@0: 	x=0;
sl@0: 	before = User::NTickCount();
sl@0: 	for (i=0; i<aCount; ++i)
sl@0: 		{
sl@0: 		x = (x+4339)&0x3fff;
sl@0: 		TInt r = set.Remove(base[x]);
sl@0: 		test(r==KErrNone);
sl@0: 		}
sl@0: 	after = User::NTickCount();
sl@0: 	diff = after - before;
sl@0: 	diff *= NanoTickPeriod;
sl@0: 	avg = (double)diff / (double)aCount;
sl@0: 	test.Printf(_L("HASH TABLE: %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0: 	set.Close();
sl@0: 	}
sl@0: 
sl@0: void Benchmark()
sl@0: 	{
sl@0: 	test.Next(_L("Benchmarks ..."));
sl@0: 
sl@0: 	IntegerBenchmark(1000, EFalse);
sl@0: 	IntegerBenchmark(1000, ETrue);
sl@0: 	IntegerBenchmark(2000, EFalse);
sl@0: 	IntegerBenchmark(2000, ETrue);
sl@0: 	IntegerBenchmark(4000, EFalse);
sl@0: 	IntegerBenchmark(4000, ETrue);
sl@0: 	IntegerBenchmark(8000, EFalse);
sl@0: 	IntegerBenchmark(8000, ETrue);
sl@0: 	IntegerBenchmark(16000, EFalse);
sl@0: 	IntegerBenchmark(16000, ETrue);
sl@0: 	IntegerBenchmark(32000, EFalse);
sl@0: 	IntegerBenchmark(32000, ETrue);
sl@0: 
sl@0: 	PopulateArray8(16384);
sl@0: 	StringBenchmark8(1000, EFalse);
sl@0: 	StringBenchmark8(2000, EFalse);
sl@0: 	StringBenchmark8(4000, EFalse);
sl@0: 	StringBenchmark8(8000, EFalse);
sl@0: 	DesC8Array.ResetAndDestroy();
sl@0: 
sl@0: 	PopulateArray16(16384);
sl@0: 	StringBenchmark16(1000, EFalse);
sl@0: 	StringBenchmark16(2000, EFalse);
sl@0: 	StringBenchmark16(4000, EFalse);
sl@0: 	StringBenchmark16(8000, EFalse);
sl@0: 	DesC16Array.ResetAndDestroy();
sl@0: 	}
sl@0: 
sl@0: 
sl@0: TUint32 mp(TUint32 x)
sl@0: 	{
sl@0: 	TUint32 x3 = x+(x<<1);
sl@0: 	TUint32 x7 = x+(x3<<1);
sl@0: 	TUint32 x15 = x+(x7<<1);
sl@0: 	TUint32 y = x + (x7<<3) + (x3<<7) + (x15<<11) + (x7<<16) + (x3<<20) + (x15<<25) + (x<<31);
sl@0: 	return y;
sl@0: 	}
sl@0: 
sl@0: TUint32 strh(const char* aIn)
sl@0: 	{
sl@0: 	TUint32 h = 0;
sl@0: 	TInt i = 0;
sl@0: 	while (*aIn)
sl@0: 		{
sl@0: 		if (i==0)
sl@0: 			h = mp(h);
sl@0: 		TUint32 c = *aIn++;
sl@0: 		c <<= (8*i);
sl@0: 		h ^= c;
sl@0: 		i = (i+1)&3;
sl@0: 		}
sl@0: 	return mp(h);
sl@0: 	}
sl@0: 
sl@0: TUint32 strh(const wch* aIn)
sl@0: 	{
sl@0: 	TUint32 h = 0;
sl@0: 	TInt i = 0;
sl@0: 	while (*aIn)
sl@0: 		{
sl@0: 		if (i==0)
sl@0: 			h = mp(h);
sl@0: 		TUint32 c = *aIn++;
sl@0: 		switch (i)
sl@0: 			{
sl@0: 			case 0:		break;
sl@0: 			case 1:		c<<=16; break;
sl@0: 			case 2:		c<<=8; break;
sl@0: 			default:	c=(c<<24)|(c>>8); break;
sl@0: 			};
sl@0: 		h ^= c;
sl@0: 		i = (i+1)&3;
sl@0: 		}
sl@0: 	return mp(h);
sl@0: 	}
sl@0: 
sl@0: void TestHash(TInt* aIn, TUint32 aExpected)
sl@0: 	{
sl@0: 	THashFunction32<TInt*> hf(&DefaultHash::IntegerPtr);
sl@0: 	TUint32 out = hf.Hash(aIn);
sl@0: 	test(aExpected == mp((TUint32)aIn));
sl@0: 	if (out != aExpected)
sl@0: 		{
sl@0: 		test.Printf(_L("Hashing %08x Expected %08x Got %08x\n"), aIn, aExpected, out);
sl@0: 		test(0);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TestHash(TDesC8* aIn, TUint32 aExpected)
sl@0: 	{
sl@0: 	THashFunction32<TDesC8*> hf(&DefaultHash::Des8Ptr);
sl@0: 	TUint32 out = hf.Hash(aIn);
sl@0: 	test(aExpected == mp((TUint32)aIn));
sl@0: 	if (out != aExpected)
sl@0: 		{
sl@0: 		test.Printf(_L("Hashing %08x Expected %08x Got %08x\n"), aIn, aExpected, out);
sl@0: 		test(0);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TestHash(TDesC16* aIn, TUint32 aExpected)
sl@0: 	{
sl@0: 	THashFunction32<TDesC16*> hf(&DefaultHash::Des16Ptr);
sl@0: 	TUint32 out = hf.Hash(aIn);
sl@0: 	test(aExpected == mp((TUint32)aIn));
sl@0: 	if (out != aExpected)
sl@0: 		{
sl@0: 		test.Printf(_L("Hashing %08x Expected %08x Got %08x\n"), aIn, aExpected, out);
sl@0: 		test(0);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: 
sl@0: void TestHash(TInt aIn, TUint32 aExpected)
sl@0: 	{
sl@0: 	THashFunction32<TInt> hf(&DefaultHash::Integer);
sl@0: 	TUint32 out = hf.Hash(aIn);
sl@0: 	test(aExpected == mp((TUint32)aIn));
sl@0: 	if (out != aExpected)
sl@0: 		{
sl@0: 		test.Printf(_L("Hashing %08x Expected %08x Got %08x\n"), aIn, aExpected, out);
sl@0: 		test(0);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TestHash(const char* aIn, TUint32 aExpected)
sl@0: 	{
sl@0: 	THashFunction32<TDesC8> hf(&DefaultHash::Des8);
sl@0: 	TPtrC8 p((const TUint8*)aIn);
sl@0: 	TUint32 out = hf.Hash(p);
sl@0: 	test(aExpected == strh(aIn));
sl@0: 	if (out != aExpected)
sl@0: 		{
sl@0: 		TBuf<256> buf;
sl@0: 		buf.Copy(p);
sl@0: 		test.Printf(_L("Hashing %S (len %d) Expected %08x Got %08x\n"), &buf, p.Length(), aExpected, out);
sl@0: 		test(0);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TestHash(const wch* aIn)
sl@0: 	{
sl@0: 	THashFunction32<TDesC16> hf(&DefaultHash::Des16);
sl@0: 	TPtrC16 p((const TUint16*)aIn);
sl@0: 	TUint32 out = hf.Hash(p);
sl@0: 	TUint32 exp = strh(aIn);
sl@0: 	if (out != exp)
sl@0: 		{
sl@0: 		test.Printf(_L("Hashing %S (len %d) Expected %08x Got %08x\n"), &p, p.Size(), exp, out);
sl@0: 		test(0);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TestHash()
sl@0: 	{
sl@0: 	test.Next(_L("Test integer hash"));
sl@0: 	TestHash(1,0x9e3779b9);
sl@0: 	TestHash(2,0x3c6ef372);
sl@0: 	TestHash(4,0x78dde6e4);
sl@0: 	TestHash(8,0xf1bbcdc8);
sl@0: 	TestHash(16,0xe3779b90);
sl@0: 	TestHash(0xc90fdaa2,0xbf999112);
sl@0: 	TestHash(0xb504f334,0x7fb35494);
sl@0: 	TestHash(0xddb3d743,0xd11a3a6b);
sl@0: 	TestHash(0xadf85458,0x873a8b98);
sl@0: 	TestHash(0x11730859,0xb4321951);
sl@0: 	TestHash(0x64636261,0x8628f119);
sl@0: 	}
sl@0: 
sl@0: void TestIntegerPtrHash()
sl@0: 	{
sl@0: 	TInt i[5];
sl@0: 	TInt* ptr;
sl@0: 	test.Next(_L("Test Integer pointer hash"));
sl@0: 	for (ptr=i; ptr<i+5; ptr++)
sl@0: 		{
sl@0: 		TestHash(ptr, DefaultHash::IntegerPtr(ptr));
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TestDes8PtrHash()
sl@0: 	{
sl@0: 	TBuf8<8> i[5];
sl@0: 	TDesC8* ptr;
sl@0: 	test.Next(_L("Test Des8 pointer hash"));
sl@0: 	for (ptr=i; ptr<i+5; ptr++)
sl@0: 		{
sl@0: 		TestHash(ptr, DefaultHash::Des8Ptr(ptr));
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TestDes16PtrHash()
sl@0: 	{
sl@0: 	TBuf16<8> i[5];
sl@0: 	TDesC16* ptr;
sl@0: 	test.Next(_L("Test Des16 pointer hash"));
sl@0: 	for (ptr=i; ptr<i+5; ptr++)
sl@0: 		{
sl@0: 		TestHash(ptr, DefaultHash::Des16Ptr(ptr));
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: const char teststr[] = "zyxwvutsrq";
sl@0: void TestStringHash()
sl@0: 	{
sl@0: 	test.Next(_L("Test 8 bit string hash"));
sl@0: 	TestHash("",0x0);
sl@0: 	TestHash("a",0xf3051f19);
sl@0: 	TestHash("b",0x913c98d2);
sl@0: 	TestHash("ab",0x2f9df119);
sl@0: 	TestHash("ba",0x965bb1d2);
sl@0: 	TestHash("abc",0x4228f119);
sl@0: 	TestHash("abcd",0x8628f119);
sl@0: 	TestHash("abcde",0xb75e1e9c);
sl@0: 	TestHash("abcdef",0x3693149c);
sl@0: 	TestHash("abcdefg",0xc1c2149c);
sl@0: 	TestHash("abcdefgh",0xe9c2149c);
sl@0: 	TestHash("abcdefghi",0x5fcbf20d);
sl@0: 	TestHash("abcdefghj",0xfe036bc6);
sl@0: 
sl@0: 	TestHash(teststr, 0x108ca51e);
sl@0: 	TestHash(teststr+1, 0x551002ad);
sl@0: 	TestHash(teststr+2, 0x37dc0d6c);
sl@0: 	TestHash(teststr+3, 0x2937f92c);
sl@0: 	TestHash(teststr+4, 0xf0818a94);
sl@0: 	TestHash(teststr+5, 0xb1b25f1c);
sl@0: 	TestHash(teststr+6, 0x7a3342d4);
sl@0: 	TestHash(teststr+7, 0x81c9101b);
sl@0: 	TestHash(teststr+8, 0xf16edd62);
sl@0: 	TestHash(teststr+9, 0xd67cbaa9);
sl@0: 	TestHash(teststr+10, 0);
sl@0: 
sl@0: 	char t[16];
sl@0: 	int i,j;
sl@0: 	for (i=0; i<=4; ++i)
sl@0: 		{
sl@0: 		for (j=0; j<=10; ++j)
sl@0: 			{
sl@0: 			const char* s = teststr + j;
sl@0: 			int l = User::StringLength((const TUint8*)s);
sl@0: 			memset(t, 0xbb, 16);
sl@0: 			memcpy(t+i, s, l+1);
sl@0: 			TUint32 h;
sl@0: 			switch (j)
sl@0: 				{
sl@0: 				case 0: h = 0x108ca51e; break;
sl@0: 				case 1: h = 0x551002ad; break;
sl@0: 				case 2: h = 0x37dc0d6c; break;
sl@0: 				case 3: h = 0x2937f92c; break;
sl@0: 				case 4: h = 0xf0818a94; break;
sl@0: 				case 5: h = 0xb1b25f1c; break;
sl@0: 				case 6: h = 0x7a3342d4; break;
sl@0: 				case 7: h = 0x81c9101b; break;
sl@0: 				case 8: h = 0xf16edd62; break;
sl@0: 				case 9: h = 0xd67cbaa9; break;
sl@0: 				default: h = 0; break;
sl@0: 				};
sl@0: 			TestHash(t+i, h);
sl@0: 			}
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: const wch wteststr[] = L"zyxwvutsrq";
sl@0: void TestWStringHash()
sl@0: 	{
sl@0: 	test.Next(_L("Test 16 bit string hash"));
sl@0: 	TestHash(L"");
sl@0: 	TestHash(L"a");
sl@0: 	TestHash(L"b");
sl@0: 	TestHash(L"ab");
sl@0: 	TestHash(L"ba");
sl@0: 	TestHash(L"abc");
sl@0: 	TestHash(L"abcd");
sl@0: 	TestHash(L"abcde");
sl@0: 	TestHash(L"abcdef");
sl@0: 	TestHash(L"abcdefg");
sl@0: 	TestHash(L"abcdefgh");
sl@0: 	TestHash(L"abcdefghi");
sl@0: 	TestHash(L"abcdefghj");
sl@0: 
sl@0: 	TestHash(wteststr);
sl@0: 	TestHash(wteststr+1);
sl@0: 	TestHash(wteststr+2);
sl@0: 	TestHash(wteststr+3);
sl@0: 	TestHash(wteststr+4);
sl@0: 	TestHash(wteststr+5);
sl@0: 	TestHash(wteststr+6);
sl@0: 	TestHash(wteststr+7);
sl@0: 	TestHash(wteststr+8);
sl@0: 	TestHash(wteststr+9);
sl@0: 	TestHash(wteststr+10);
sl@0: 
sl@0: 	wch t[16];
sl@0: 	int i,j;
sl@0: 	for (i=0; i<=4; ++i)
sl@0: 		{
sl@0: 		for (j=0; j<=10; ++j)
sl@0: 			{
sl@0: 			const wch* s = wteststr + j;
sl@0: 			int l = User::StringLength((const TUint16*)s);
sl@0: 			memset(t, 0xbb, 2*16);
sl@0: 			memcpy(t+i, s, 2*(l+1));
sl@0: 			TestHash(t+i);
sl@0: 			}
sl@0: 		}
sl@0: 	}
sl@0: template <class K,class V> 
sl@0: void TestHashMapPtr(RHashMap<K,V> &map, K ptr, V* i)
sl@0: {
sl@0: 	test(map.Reserve(5) == KErrNone);
sl@0: 	for (ptr=i;ptr<i+5;ptr++)
sl@0: 		{
sl@0: 		test(map.Insert(ptr,*ptr) == KErrNone);
sl@0: 		}
sl@0: 	for (ptr=i+4;ptr>=i;ptr--)
sl@0: 		{
sl@0: 		test(*(map.Find(ptr)) == *ptr);
sl@0: 		}
sl@0: 	test(map.Count() == 5);
sl@0: 	test(map.Remove(i) == KErrNone);
sl@0: 	test(map.Count()==4);
sl@0: 	test(map.Find(i)==NULL);
sl@0: 	map.Close();
sl@0: }
sl@0: 
sl@0: void TestPtrHashMaps()
sl@0: 	{	
sl@0: 
sl@0: 	test.Next(_L("Test RHashMap of default pointer types"));
sl@0: 	TInt i[5];
sl@0: 	TInt *ptr=i;
sl@0: 	RHashMap<TInt*,TInt> mp;
sl@0: 	TestHashMapPtr(mp, ptr, i);
sl@0: 
sl@0: 	TInt32 i1[5];
sl@0: 	TInt32 *ptr1=i1;
sl@0: 	RHashMap<TInt32*,TInt32> mp1;
sl@0: 	TestHashMapPtr(mp1,ptr1,i1);
sl@0: 	
sl@0: 	TUint i2[5];
sl@0: 	TUint *ptr2=i2;
sl@0: 	RHashMap<TUint*,TUint> mp2;
sl@0: 	TestHashMapPtr(mp2,ptr2,i2);
sl@0: 
sl@0: 	TUint32 i3[5];
sl@0: 	TUint32 *ptr3=i3;
sl@0: 	RHashMap<TUint32*,TUint32> mp3;
sl@0: 	TestHashMapPtr(mp3,ptr3,i3);
sl@0: 
sl@0: 	TBuf8<5> i4[5];
sl@0: 	TBuf8<5> *ptr4=i4;
sl@0: 	RHashMap<TDesC8*,TDesC8> mp4;
sl@0: 	for (ptr4=i4; ptr4 < i4+5; ptr4++) 
sl@0: 		{
sl@0: 		test(mp4.Insert(ptr4,*ptr4) == KErrNone);
sl@0: 		}
sl@0: 	for (ptr4=i4+4; ptr4 >= i4; ptr4--) 
sl@0: 		{
sl@0: 		test(*(mp4.Find(ptr4)) == *ptr4);
sl@0: 		}
sl@0: 	test(mp4.Count()==5);
sl@0: 	test(mp4.Remove(i4) == KErrNone);
sl@0: 	test(mp4.Find(i4) == NULL);
sl@0: 	test(mp4.Count()==4);
sl@0: 	mp4.Close();
sl@0: 
sl@0: 
sl@0: 	TBuf16<5> i5[5];
sl@0: 	TBuf16<5> *ptr5=i5;
sl@0: 	RHashMap<TDesC16*,TDesC16> mp5;
sl@0: 	for (ptr5=i5; ptr5 < i5+5; ptr5++) 
sl@0: 		{
sl@0: 		test(mp5.Insert(ptr5,*ptr5) == KErrNone);
sl@0: 		}
sl@0: 	for (ptr5=i5+4; ptr5 >= i5; ptr5--) 
sl@0: 		{
sl@0: 		test(*(mp5.Find(ptr5)) == *ptr5);
sl@0: 		}
sl@0: 	test(mp5.Count()==5);
sl@0: 	test(mp5.Remove(i5) == KErrNone);
sl@0: 	test(mp5.Find(i5) == NULL);
sl@0: 	test(mp5.Count()==4);
sl@0: 	mp5.Close();
sl@0: 	
sl@0: }
sl@0: 
sl@0: /** Tests that Reserve() will always allocate memory for new tables 
sl@0: 	even for small reserve sizes
sl@0: 	See DEF087906.
sl@0: */
sl@0: void TestSmallReserve()
sl@0: 	{
sl@0: 	test.Next(_L("Test RHashTableBase::Reserve preallocates memory, even for small no of elements"));
sl@0: 	RAllocator* pA = 0;
sl@0: 	RDummyAllocator da;
sl@0: 	
sl@0: 	// Reserve should allocate the memory required for the table of 1 element
sl@0: 	INTSET(set);
sl@0: 	RHashMap<TInt,TInt> hashMap;
sl@0: 	
sl@0: 	test(set.Reserve(1) == KErrNone);
sl@0: 	test(hashMap.Reserve(1) == KErrNone);
sl@0: 	
sl@0: 	pA = User::SwitchAllocator(&da);
sl@0: 	
sl@0: 	// No more memory should be allocated for the table as it should
sl@0: 	// have been already allocated by Reserve()
sl@0: 	test(set.Insert(123) == KErrNone);
sl@0: 	test(hashMap.Insert(123,456) == KErrNone);
sl@0: 	
sl@0: 	// Switch back to allow set to be closed
sl@0: 	User::SwitchAllocator(pA);
sl@0: 	set.Close();
sl@0: 	hashMap.Close();
sl@0: 	}
sl@0: 	
sl@0: 
sl@0: TInt E32Main()
sl@0: 	{
sl@0: 	test.Title();
sl@0: 
sl@0: 	test(HAL::Get(HAL::ENanoTickPeriod, NanoTickPeriod)==KErrNone);
sl@0: 	test.Printf(_L("NanoTickPeriod %dus\n"), NanoTickPeriod);
sl@0: 
sl@0: 	__UHEAP_MARK;
sl@0: 
sl@0: 	test.Start(_L("Testing hash tables"));
sl@0: 
sl@0: 	TestHash();
sl@0: 	TestStringHash();
sl@0: 	TestWStringHash();
sl@0: 	TestIntegerPtrHash();
sl@0: 	TestDes8PtrHash();
sl@0: 	TestDes16PtrHash();
sl@0: 
sl@0: 	TestHashSet();
sl@0: 	TestHashIter();
sl@0: 	TestHashMap();
sl@0: 	TestPtrHashMaps();
sl@0: 
sl@0: 	PopulateArray8(4096);
sl@0: 	PopulateArray16(4096);
sl@0: 	TestPtrHashSet();
sl@0: 	TestPtrHashMap();
sl@0: 	DesC16Array.ResetAndDestroy();
sl@0: 	DesC8Array.ResetAndDestroy();
sl@0: 
sl@0: 
sl@0: 	TestOOM();
sl@0: 	Benchmark();
sl@0: 	TestSmallReserve();
sl@0: 
sl@0: 	test.End();
sl@0: 
sl@0: 	__UHEAP_MARKEND;
sl@0: 	return 0;
sl@0: 	}