Symaptic: os/kernelhwsrv/kerneltest/e32test/buffer/t_hashtab.cpp@bde4ae8d615e (annotated)

sl@0	1	// Copyright (c) 2005-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0	2	// All rights reserved.
sl@0	3	// This component and the accompanying materials are made available
sl@0	4	// under the terms of the License "Eclipse Public License v1.0"
sl@0	5	// which accompanies this distribution, and is available
sl@0	6	// at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0	7	//
sl@0	8	// Initial Contributors:
sl@0	9	// Nokia Corporation - initial contribution.
sl@0	10	//
sl@0	11	// Contributors:
sl@0	12	//
sl@0	13	// Description:
sl@0	14	// e32test/buffer/t_hashtab.cpp
sl@0	15	//
sl@0	16	//
sl@0	17
sl@0	18	#include <e32test.h>
sl@0	19	#include <e32hashtab.h>
sl@0	20	#include <hal.h>
sl@0	21
sl@0	22	#if defined(__VC32__) \|\| defined(__CW32__)
sl@0	23	typedef unsigned short wch;
sl@0	24	#else
sl@0	25	typedef wchar_t wch;
sl@0	26	#endif
sl@0	27
sl@0	28
sl@0	29	RTest test(_L("T_HASHTAB"));
sl@0	30	TInt NanoTickPeriod;
sl@0	31
sl@0	32	typedef TBuf8<80> TTestName;
sl@0	33	typedef RHashSet<TInt> TIntSet;
sl@0	34	typedef RHashSet<TTestName> TNameSet;
sl@0	35	typedef RPtrHashSet<TDesC8> TStringSet8;
sl@0	36	typedef RPtrHashSet<TDesC16> TStringSet16;
sl@0	37	typedef RPtrHashMap<TDesC8,TDesC8> TStringMap8;
sl@0	38	typedef RPtrHashMap<TDesC16,TDesC16> TStringMap16;
sl@0	39
sl@0	40	#define INTSET(x) TIntSet x
sl@0	41	#define NAMESET(x) TNameSet x(&HashTestName, &TestNameIdentity)
sl@0	42	#define STRSET8(x) TStringSet8 x
sl@0	43	#define STRSET16(x) TStringSet16 x
sl@0	44	#define STRMAP8(x) TStringMap8 x
sl@0	45	#define STRMAP16(x) TStringMap16 x
sl@0	46
sl@0	47	RPointerArray<TDesC8> DesC8Array;
sl@0	48	RPointerArray<TDesC16> DesC16Array;
sl@0	49
sl@0	50	class HashTest : public RHashTableBase
sl@0	51	{
sl@0	52	public:
sl@0	53	HashTest() : RHashTableBase(0,0,0,0) {}
sl@0	54	using RHashTableBase::ConsistencyCheck;
sl@0	55	using RHashTableBase::Count;
sl@0	56	};
sl@0	57
sl@0	58	void CCheck(RHashTableBase& aHT)
sl@0	59	{
sl@0	60	TUint32 ci[1024];
sl@0	61	TUint32 dc;
sl@0	62	TUint32 cmp;
sl@0	63	HashTest* h = (HashTest*)&aHT;
sl@0	64	h->ConsistencyCheck(&dc, &cmp, 1024, ci);
sl@0	65	test.Printf(_L("Count = %d, Deleted = %d, Cmp = %d\n"), h->Count(), dc, cmp);
sl@0	66	TInt i;
sl@0	67	for (i=0; i<1024; ++i)
sl@0	68	{
sl@0	69	if (ci[i])
sl@0	70	test.Printf(_L("%d chains of length %d\n"), ci[i], i);
sl@0	71	}
sl@0	72	}
sl@0	73
sl@0	74	const char* Numbers[] =
sl@0	75	{
sl@0	76	"zero",
sl@0	77	"one",
sl@0	78	"two",
sl@0	79	"three",
sl@0	80	"four",
sl@0	81	"five",
sl@0	82	"six",
sl@0	83	"seven",
sl@0	84	"eight",
sl@0	85	"nine",
sl@0	86	"ten",
sl@0	87	"eleven",
sl@0	88	"twelve",
sl@0	89	"thirteen",
sl@0	90	"fourteen",
sl@0	91	"fifteen",
sl@0	92	"sixteen",
sl@0	93	"seventeen",
sl@0	94	"eighteen",
sl@0	95	"nineteen",
sl@0	96	"twenty",
sl@0	97	"thirty",
sl@0	98	"forty",
sl@0	99	"fifty",
sl@0	100	"sixty",
sl@0	101	"seventy",
sl@0	102	"eighty",
sl@0	103	"ninety",
sl@0	104	"hundred",
sl@0	105	"thousand"
sl@0	106	};
sl@0	107
sl@0	108	TTestName NumberInWords(const TInt& aNum)
sl@0	109	{
sl@0	110	TInt a = aNum;
sl@0	111	TTestName n;
sl@0	112	if (a<20)
sl@0	113	{
sl@0	114	n.Copy((const TUint8*)Numbers[a]);
sl@0	115	return n;
sl@0	116	}
sl@0	117	if (a<100)
sl@0	118	{
sl@0	119	TInt tens = a/10;
sl@0	120	TInt units = a%10;
sl@0	121	n.Copy((const TUint8*)Numbers[tens-2+20]);
sl@0	122	if (units)
sl@0	123	{
sl@0	124	n.Append(' ');
sl@0	125	n.Append(TPtrC8((const TUint8*)Numbers[units]));
sl@0	126	}
sl@0	127	return n;
sl@0	128	}
sl@0	129	if (a<1000)
sl@0	130	{
sl@0	131	TInt h = a/100;
sl@0	132	n.Copy((const TUint8*)Numbers[h]);
sl@0	133	n.Append(' ');
sl@0	134	n.Append(TPtrC8((const TUint8*)Numbers[28]));
sl@0	135	a%=100;
sl@0	136	if (a)
sl@0	137	{
sl@0	138	TTestName n2(NumberInWords(a));
sl@0	139	n.Append(_L8(" and "));
sl@0	140	n+=n2;
sl@0	141	}
sl@0	142	return n;
sl@0	143	}
sl@0	144	TInt t = a/1000;
sl@0	145	n = NumberInWords(t);
sl@0	146	n.Append(' ');
sl@0	147	n.Append(TPtrC8((const TUint8*)Numbers[29]));
sl@0	148	a%=1000;
sl@0	149	if (a)
sl@0	150	{
sl@0	151	TTestName n2(NumberInWords(a));
sl@0	152	if (a<100)
sl@0	153	n.Append(_L8(" and "));
sl@0	154	else
sl@0	155	n.Append(' ');
sl@0	156	n+=n2;
sl@0	157	}
sl@0	158	return n;
sl@0	159	}
sl@0	160
sl@0	161	void PrintNumberInWords(TInt a)
sl@0	162	{
sl@0	163	TBuf<256> buf;
sl@0	164	TTestName n(NumberInWords(a));
sl@0	165	buf.Copy(n);
sl@0	166	test.Printf(_L("%d: %S\n"), a, &buf);
sl@0	167	}
sl@0	168
sl@0	169	TUint32 HashTestName(const TTestName& aN)
sl@0	170	{
sl@0	171	return DefaultHash::Des8(aN);
sl@0	172	}
sl@0	173
sl@0	174	TBool TestNameIdentity(const TTestName& aA, const TTestName& aB)
sl@0	175	{
sl@0	176	return aA == aB;
sl@0	177	}
sl@0	178
sl@0	179	/******************************************************************************
sl@0	180	* Utility functions for RHashSet<T>
sl@0	181	******************************************************************************/
sl@0	182	template <class T>
sl@0	183	void Union(RHashSet<T>& aD, const RHashSet<T>& aS)
sl@0	184	{
sl@0	185	TInt c = aS.Count();
sl@0	186	TInt c2 = c;
sl@0	187	TInt d0 = aD.Count();
sl@0	188	TInt d1 = d0;
sl@0	189	typename RHashSet<T>::TIter iS(aS);
sl@0	190	FOREVER
sl@0	191	{
sl@0	192	const T* p = iS.Next();
sl@0	193	if (!p)
sl@0	194	break;
sl@0	195	--c2;
sl@0	196	TInt r = aD.Insert(*p);
sl@0	197	test(r==KErrNone);
sl@0	198	++d1;
sl@0	199	}
sl@0	200	test(d1 == aD.Count());
sl@0	201	test(c2 == 0);
sl@0	202	}
sl@0	203
sl@0	204	template <class T>
sl@0	205	void Subtract(RHashSet<T>& aD, const RHashSet<T>& aS)
sl@0	206	{
sl@0	207	TInt c = aS.Count();
sl@0	208	TInt c2 = c;
sl@0	209	TInt d0 = aD.Count();
sl@0	210	TInt d1 = d0;
sl@0	211	TInt nfd = 0;
sl@0	212	typename RHashSet<T>::TIter iS(aS);
sl@0	213	FOREVER
sl@0	214	{
sl@0	215	const T* p = iS.Next();
sl@0	216	if (!p)
sl@0	217	break;
sl@0	218	--c2;
sl@0	219	TInt r = aD.Remove(*p);
sl@0	220	test(r==KErrNone \|\| r==KErrNotFound);
sl@0	221	if (r==KErrNotFound)
sl@0	222	++nfd;
sl@0	223	else
sl@0	224	--d1;
sl@0	225	}
sl@0	226	test(d1 == aD.Count());
sl@0	227	test(c2 == 0);
sl@0	228	test( (d0-d1) + nfd == c);
sl@0	229	}
sl@0	230
sl@0	231	template <class T>
sl@0	232	void Intersect(RHashSet<T>& aD, const RHashSet<T>& aS)
sl@0	233	{
sl@0	234	typename RHashSet<T>::TIter iD(aD);
sl@0	235	FOREVER
sl@0	236	{
sl@0	237	const T* p = iD.Next();
sl@0	238	if (!p)
sl@0	239	break;
sl@0	240	if (!aS.Find(*p))
sl@0	241	iD.RemoveCurrent();
sl@0	242	}
sl@0	243	}
sl@0	244
sl@0	245	template <class T>
sl@0	246	void CheckIdentical(const RHashSet<T>& aA, const RHashSet<T>& aB)
sl@0	247	{
sl@0	248	test(aA.Count()==aB.Count());
sl@0	249	TInt c = aA.Count();
sl@0	250	typename RHashSet<T>::TIter iA(aA);
sl@0	251	FOREVER
sl@0	252	{
sl@0	253	const T* p = iA.Next();
sl@0	254	if (!p)
sl@0	255	break;
sl@0	256	--c;
sl@0	257	test(aB.Find(*p)!=0);
sl@0	258	}
sl@0	259	test(c==0);
sl@0	260	c = aA.Count();
sl@0	261	typename RHashSet<T>::TIter iB(aB);
sl@0	262	FOREVER
sl@0	263	{
sl@0	264	const T* p = iB.Next();
sl@0	265	if (!p)
sl@0	266	break;
sl@0	267	--c;
sl@0	268	test(aA.Find(*p)!=0);
sl@0	269	}
sl@0	270	test(c==0);
sl@0	271	}
sl@0	272
sl@0	273
sl@0	274	/******************************************************************************
sl@0	275	* Utility functions for RPtrHashSet<T>
sl@0	276	******************************************************************************/
sl@0	277	template <class T>
sl@0	278	void Union(RPtrHashSet<T>& aD, const RPtrHashSet<T>& aS)
sl@0	279	{
sl@0	280	TInt c = aS.Count();
sl@0	281	TInt c2 = c;
sl@0	282	TInt d0 = aD.Count();
sl@0	283	TInt d1 = d0;
sl@0	284	typename RPtrHashSet<T>::TIter iS(aS);
sl@0	285	FOREVER
sl@0	286	{
sl@0	287	const T* p = iS.Next();
sl@0	288	if (!p)
sl@0	289	break;
sl@0	290	--c2;
sl@0	291	TInt r = aD.Insert(p);
sl@0	292	test(r==KErrNone);
sl@0	293	++d1;
sl@0	294	}
sl@0	295	test(d1 == aD.Count());
sl@0	296	test(c2 == 0);
sl@0	297	}
sl@0	298
sl@0	299	template <class T>
sl@0	300	void Subtract(RPtrHashSet<T>& aD, const RPtrHashSet<T>& aS)
sl@0	301	{
sl@0	302	TInt c = aS.Count();
sl@0	303	TInt c2 = c;
sl@0	304	TInt d0 = aD.Count();
sl@0	305	TInt d1 = d0;
sl@0	306	TInt nfd = 0;
sl@0	307	typename RPtrHashSet<T>::TIter iS(aS);
sl@0	308	FOREVER
sl@0	309	{
sl@0	310	const T* p = iS.Next();
sl@0	311	if (!p)
sl@0	312	break;
sl@0	313	--c2;
sl@0	314	TInt r = aD.Remove(p);
sl@0	315	test(r==KErrNone \|\| r==KErrNotFound);
sl@0	316	if (r==KErrNotFound)
sl@0	317	++nfd;
sl@0	318	else
sl@0	319	--d1;
sl@0	320	}
sl@0	321	test(d1 == aD.Count());
sl@0	322	test(c2 == 0);
sl@0	323	test( (d0-d1) + nfd == c);
sl@0	324	}
sl@0	325
sl@0	326	template <class T>
sl@0	327	void Intersect(RPtrHashSet<T>& aD, const RPtrHashSet<T>& aS)
sl@0	328	{
sl@0	329	typename RPtrHashSet<T>::TIter iD(aD);
sl@0	330	FOREVER
sl@0	331	{
sl@0	332	const T* p = iD.Next();
sl@0	333	if (!p)
sl@0	334	break;
sl@0	335	if (!aS.Find(*p))
sl@0	336	iD.RemoveCurrent();
sl@0	337	}
sl@0	338	}
sl@0	339
sl@0	340	template <class T>
sl@0	341	void CheckIdentical(const RPtrHashSet<T>& aA, const RPtrHashSet<T>& aB)
sl@0	342	{
sl@0	343	test(aA.Count()==aB.Count());
sl@0	344	TInt c = aA.Count();
sl@0	345	typename RPtrHashSet<T>::TIter iA(aA);
sl@0	346	FOREVER
sl@0	347	{
sl@0	348	const T* p = iA.Next();
sl@0	349	if (!p)
sl@0	350	break;
sl@0	351	--c;
sl@0	352	test(aB.Find(*p)!=0);
sl@0	353	}
sl@0	354	test(c==0);
sl@0	355	c = aA.Count();
sl@0	356	typename RPtrHashSet<T>::TIter iB(aB);
sl@0	357	FOREVER
sl@0	358	{
sl@0	359	const T* p = iB.Next();
sl@0	360	if (!p)
sl@0	361	break;
sl@0	362	--c;
sl@0	363	test(aA.Find(*p)!=0);
sl@0	364	}
sl@0	365	test(c==0);
sl@0	366	}
sl@0	367
sl@0	368
sl@0	369	/******************************************************************************
sl@0	370	* Utility functions for RHashMap<K,V>
sl@0	371	******************************************************************************/
sl@0	372	template <class K, class V>
sl@0	373	void UnionTransform(RHashMap<K,V>& aD, const RHashSet<K>& aS, V (*aTransform)(const K&) )
sl@0	374	{
sl@0	375	TInt c = aS.Count();
sl@0	376	TInt c2 = c;
sl@0	377	TInt d0 = aD.Count();
sl@0	378	TInt d1 = d0;
sl@0	379	typename RHashSet<K>::TIter iS(aS);
sl@0	380	FOREVER
sl@0	381	{
sl@0	382	const K* p = iS.Next();
sl@0	383	if (!p)
sl@0	384	break;
sl@0	385	--c2;
sl@0	386	TInt r = aD.Insert(p, (aTransform)(*p) );
sl@0	387	test(r==KErrNone);
sl@0	388	++d1;
sl@0	389	}
sl@0	390	test(d1 == aD.Count());
sl@0	391	test(c2 == 0);
sl@0	392	}
sl@0	393
sl@0	394
sl@0	395	template <class K, class V>
sl@0	396	void UnionMap(RHashSet<V>& aD, const RHashSet<K>& aS, const RHashMap<K,V>& aM)
sl@0	397	{
sl@0	398	TInt c = aS.Count();
sl@0	399	TInt c2 = c;
sl@0	400	TInt d0 = aD.Count();
sl@0	401	TInt d1 = d0;
sl@0	402	typename RHashSet<K>::TIter iS(aS);
sl@0	403	FOREVER
sl@0	404	{
sl@0	405	const K* p = iS.Next();
sl@0	406	if (!p)
sl@0	407	break;
sl@0	408	--c2;
sl@0	409	const V* q = aM.Find(*p);
sl@0	410	if (!q)
sl@0	411	continue;
sl@0	412	TInt r = aD.Insert(*q);
sl@0	413	test(r==KErrNone);
sl@0	414	++d1;
sl@0	415	}
sl@0	416	test(d1 == aD.Count());
sl@0	417	test(c2 == 0);
sl@0	418	}
sl@0	419
sl@0	420
sl@0	421	template <class K, class V>
sl@0	422	void UnionKeys(RHashSet<K>& aD, const RHashMap<K,V>& aM)
sl@0	423	{
sl@0	424	typename RHashMap<K,V>::TIter iM(aM);
sl@0	425	FOREVER
sl@0	426	{
sl@0	427	const K* p = iM.NextKey();
sl@0	428	if (!p)
sl@0	429	break;
sl@0	430	aD.Insert(*p);
sl@0	431	}
sl@0	432	}
sl@0	433
sl@0	434
sl@0	435	template <class K, class V>
sl@0	436	void UnionValues(RHashSet<V>& aD, const RHashMap<K,V>& aM)
sl@0	437	{
sl@0	438	typename RHashMap<K,V>::TIter iM(aM);
sl@0	439	FOREVER
sl@0	440	{
sl@0	441	const K* p = iM.NextKey();
sl@0	442	if (!p)
sl@0	443	break;
sl@0	444	const V* q = iM.CurrentValue();
sl@0	445	aD.Insert(*q);
sl@0	446	}
sl@0	447	}
sl@0	448
sl@0	449
sl@0	450	template <class K, class V>
sl@0	451	void UnionTransform(RHashMap<K,V>& aD, const RHashMap<K,V>& aS, V (*aTransform)(const V&) )
sl@0	452	{
sl@0	453	TInt c = aS.Count();
sl@0	454	TInt c2 = c;
sl@0	455	TInt d0 = aD.Count();
sl@0	456	TInt d1 = d0;
sl@0	457	typename RHashMap<K,V>::TIter iS(aS);
sl@0	458	FOREVER
sl@0	459	{
sl@0	460	const K* p = iS.NextKey();
sl@0	461	if (!p)
sl@0	462	break;
sl@0	463	--c2;
sl@0	464	TInt r = aD.Insert(p, (aTransform)(*iS.CurrentValue()) );
sl@0	465	test(r==KErrNone);
sl@0	466	++d1;
sl@0	467	}
sl@0	468	test(d1 == aD.Count());
sl@0	469	test(c2 == 0);
sl@0	470	}
sl@0	471
sl@0	472
sl@0	473	template <class K, class V>
sl@0	474	void UnionInverse(RHashMap<V,K>& aD, const RHashMap<K,V>& aS)
sl@0	475	{
sl@0	476	TInt c = aS.Count();
sl@0	477	TInt c2 = c;
sl@0	478	TInt d0 = aD.Count();
sl@0	479	TInt d1 = d0;
sl@0	480	typename RHashMap<K,V>::TIter iS(aS);
sl@0	481	FOREVER
sl@0	482	{
sl@0	483	const K* p = iS.NextKey();
sl@0	484	if (!p)
sl@0	485	break;
sl@0	486	--c2;
sl@0	487	const V* q = iS.CurrentValue();
sl@0	488	TInt r = aD.Insert(q, p);
sl@0	489	test(r==KErrNone);
sl@0	490	++d1;
sl@0	491	}
sl@0	492	test(d1 == aD.Count());
sl@0	493	test(c2 == 0);
sl@0	494	}
sl@0	495
sl@0	496	template <class K, class V>
sl@0	497	void SetMap(RHashMap<V,K>& aM, const V& aV)
sl@0	498	{
sl@0	499	typename RHashMap<K,V>::TIter iM(aM);
sl@0	500	FOREVER
sl@0	501	{
sl@0	502	const K* p = iM.NextKey();
sl@0	503	if (!p)
sl@0	504	break;
sl@0	505	V* q = iM.CurrentValue();
sl@0	506	*q = aV;
sl@0	507	test(*q == aV);
sl@0	508	}
sl@0	509	}
sl@0	510
sl@0	511
sl@0	512	/******************************************************************************
sl@0	513	* Utility functions for RPtrHashMap<K,V>
sl@0	514	******************************************************************************/
sl@0	515	template <class K, class V>
sl@0	516	void UnionTransform(RPtrHashMap<K,V>& aD, const RPtrHashMap<K,V>& aS, V* (aTransform)(const V) )
sl@0	517	{
sl@0	518	TInt c = aS.Count();
sl@0	519	TInt c2 = c;
sl@0	520	TInt d0 = aD.Count();
sl@0	521	TInt d1 = d0;
sl@0	522	typename RPtrHashMap<K,V>::TIter iS(aS);
sl@0	523	FOREVER
sl@0	524	{
sl@0	525	const K* p = iS.NextKey();
sl@0	526	if (!p)
sl@0	527	break;
sl@0	528	--c2;
sl@0	529	TInt r = aD.Insert(p, (*aTransform)(iS.CurrentValue()) );
sl@0	530	test(r==KErrNone);
sl@0	531	++d1;
sl@0	532	}
sl@0	533	test(d1 == aD.Count());
sl@0	534	test(c2 == 0);
sl@0	535	}
sl@0	536
sl@0	537
sl@0	538	template <class A, class B>
sl@0	539	void UnionInverse(RPtrHashMap<B,A>& aD, const RPtrHashMap<A,B>& a1)
sl@0	540	{
sl@0	541	typename RPtrHashMap<A,B>::TIter iter(a1);
sl@0	542	const A* pA;
sl@0	543	while ( (pA=iter.NextKey()) != 0 )
sl@0	544	{
sl@0	545	const B* pB = iter.CurrentValue();
sl@0	546	TInt r = aD.Insert(pB, pA);
sl@0	547	test(r==KErrNone);
sl@0	548	}
sl@0	549	}
sl@0	550
sl@0	551
sl@0	552	template <class A, class B, class C>
sl@0	553	void UnionCompose(RPtrHashMap<A,C>& aD, const RPtrHashMap<A,B>& a1, const RPtrHashMap<B,C>& a2)
sl@0	554	{
sl@0	555	typename RPtrHashMap<A,B>::TIter iter(a1);
sl@0	556	const A* pA;
sl@0	557	while ( (pA=iter.NextKey()) != 0 )
sl@0	558	{
sl@0	559	const B* pB = iter.CurrentValue();
sl@0	560	const C* pC = a2.Find(*pB);
sl@0	561	if (pC)
sl@0	562	{
sl@0	563	TInt r = aD.Insert(pA, pC);
sl@0	564	test(r==KErrNone);
sl@0	565	}
sl@0	566	}
sl@0	567	}
sl@0	568
sl@0	569
sl@0	570	template <class K, class V>
sl@0	571	void CheckIdenticalMaps(const RPtrHashMap<K,V>& aA, const RPtrHashMap<K,V>& aB)
sl@0	572	{
sl@0	573	test(aA.Count()==aB.Count());
sl@0	574	TInt c = aA.Count();
sl@0	575	const K* p;
sl@0	576	const V* q;
sl@0	577	typename RPtrHashMap<K,V>::TIter iA(aA);
sl@0	578	while( (p=iA.NextKey()) != 0)
sl@0	579	{
sl@0	580	--c;
sl@0	581	q = aB.Find(*p);
sl@0	582	test(q && q==iA.CurrentValue());
sl@0	583	}
sl@0	584	test(c==0);
sl@0	585	c = aB.Count();
sl@0	586	typename RPtrHashMap<K,V>::TIter iB(aB);
sl@0	587	while( (p=iB.NextKey()) != 0)
sl@0	588	{
sl@0	589	--c;
sl@0	590	q = aA.Find(*p);
sl@0	591	test(q && q==iB.CurrentValue());
sl@0	592	}
sl@0	593	test(c==0);
sl@0	594	}
sl@0	595
sl@0	596
sl@0	597
sl@0	598
sl@0	599
sl@0	600	/******************************************************************************
sl@0	601	* Tests of TIntSet
sl@0	602	******************************************************************************/
sl@0	603	void Populate(TIntSet& aH, TInt aS, TInt aE, TInt aM)
sl@0	604	{
sl@0	605	TInt x = aS;
sl@0	606	for (; x<=aE; x+=aM)
sl@0	607	aH.Insert(x);
sl@0	608	}
sl@0	609
sl@0	610	void PrimeSieve(TIntSet& aH, TInt aStart, TInt aEnd)
sl@0	611	{
sl@0	612	TInt x;
sl@0	613	TInt e = (aEnd&1) ? aEnd : aEnd-1;
sl@0	614	TInt s = (aStart<2) ? 2 : aStart\|1;
sl@0	615	for (x=s; x<=e; ++x)
sl@0	616	{
sl@0	617	// test.Printf(_L("add %d\n"),x);
sl@0	618	aH.Insert(x);
sl@0	619	}
sl@0	620	TInt m=2;
sl@0	621	FOREVER
sl@0	622	{
sl@0	623	for (; m*m<=e && !aH.Find(m); ++m)
sl@0	624	{}
sl@0	625	if (m*m > e)
sl@0	626	break;
sl@0	627	for (x=m*2; x<=e; x+=m)
sl@0	628	{
sl@0	629	// test.Printf(_L("remove %d\n"),x);
sl@0	630	aH.Remove(x);
sl@0	631	}
sl@0	632	++m;
sl@0	633	}
sl@0	634	}
sl@0	635
sl@0	636	TBool IsPrime(TInt x)
sl@0	637	{
sl@0	638	if (x==2)
sl@0	639	return ETrue;
sl@0	640	if (!(x&1))
sl@0	641	return EFalse;
sl@0	642	TInt d;
sl@0	643	for (d=3; d*d<=x; d+=2)
sl@0	644	{
sl@0	645	if (x%d==0)
sl@0	646	return EFalse;
sl@0	647	}
sl@0	648	return ETrue;
sl@0	649	}
sl@0	650
sl@0	651	void CheckSieveOutput(TIntSet& aH)
sl@0	652	{
sl@0	653	RHashSet<TInt>::TIter iter(aH);
sl@0	654	TInt min = KMaxTInt;
sl@0	655	TInt max = KMinTInt;
sl@0	656	TInt c = 0;
sl@0	657	test.Printf(_L("%d elements:\n"),aH.Count());
sl@0	658	FOREVER
sl@0	659	{
sl@0	660	const TInt* p = iter.Next();
sl@0	661	if (!p)
sl@0	662	break;
sl@0	663	++c;
sl@0	664	if (p>max) max=p;
sl@0	665	if (p<min) min=p;
sl@0	666	// test.Printf(_L("%d\n"),*p);
sl@0	667	test(IsPrime(*p));
sl@0	668	}
sl@0	669	test(c==aH.Count());
sl@0	670	TInt x;
sl@0	671	if (min==2)
sl@0	672	{
sl@0	673	test(aH.Find(2)!=0);
sl@0	674	min++;
sl@0	675	}
sl@0	676	for (x=min; x<=max; x+=2)
sl@0	677	{
sl@0	678	if (IsPrime(x))
sl@0	679	test(aH.Find(x)!=0);
sl@0	680	}
sl@0	681	for (x=min; x<=max; x+=2)
sl@0	682	{
sl@0	683	if (IsPrime(x))
sl@0	684	test(aH.Find(x)==&aH.FindL(x));
sl@0	685	else
sl@0	686	{
sl@0	687	TRAPD(rr,aH.FindL(x));
sl@0	688	test(rr==KErrNotFound);
sl@0	689	}
sl@0	690	}
sl@0	691	}
sl@0	692
sl@0	693	TUint32 CheckSmallHashSet(const TIntSet& aA)
sl@0	694	{
sl@0	695	TUint32 m = 0;
sl@0	696	RHashSet<TInt>::TIter iter(aA);
sl@0	697	FOREVER
sl@0	698	{
sl@0	699	const TInt* p = iter.Next();
sl@0	700	if (!p)
sl@0	701	break;
sl@0	702	m \|= (1<<*p);
sl@0	703	}
sl@0	704	return m;
sl@0	705	}
sl@0	706
sl@0	707	void AddToSmallHashSet(TIntSet& aA, TUint32 aMask)
sl@0	708	{
sl@0	709	CheckSmallHashSet(aA);
sl@0	710	TInt i;
sl@0	711	TInt r;
sl@0	712	for (i=0; i<32; ++i)
sl@0	713	{
sl@0	714	if (aMask & (1<<i))
sl@0	715	{
sl@0	716	r = aA.Insert(i);
sl@0	717	test(r==KErrNone);
sl@0	718	}
sl@0	719	}
sl@0	720	}
sl@0	721
sl@0	722	void RemoveFromSmallHashSet(TIntSet& aA, TUint32 aMask)
sl@0	723	{
sl@0	724	TUint32 m = CheckSmallHashSet(aA);
sl@0	725	TInt i;
sl@0	726	TInt r;
sl@0	727	for (i=0; i<32; ++i)
sl@0	728	{
sl@0	729	if (aMask & (1<<i))
sl@0	730	{
sl@0	731	r = aA.Remove(i);
sl@0	732	if (m & (1<<i))
sl@0	733	test(r==KErrNone);
sl@0	734	else
sl@0	735	test(r==KErrNotFound);
sl@0	736	}
sl@0	737	}
sl@0	738	}
sl@0	739
sl@0	740	void TestHashSet()
sl@0	741	{
sl@0	742	test.Next(_L("Test RHashSet"));
sl@0	743
sl@0	744	INTSET(hs);
sl@0	745	CCheck(hs); // check consistency for empty table
sl@0	746	INTSET(hs2);
sl@0	747	INTSET(hs3);
sl@0	748	PrimeSieve(hs, 1, 100);
sl@0	749	CheckSieveOutput(hs);
sl@0	750	test(hs.Reserve(1000)==KErrNone);
sl@0	751	CCheck(hs);
sl@0	752	CheckSieveOutput(hs); // check that Reserve() preserves existing entries
sl@0	753
sl@0	754	INTSET(m1);
sl@0	755	INTSET(m2);
sl@0	756	INTSET(m3);
sl@0	757	INTSET(m5);
sl@0	758	INTSET(m7);
sl@0	759	Populate(m1,2,100,1);
sl@0	760	Populate(m2,4,100,2);
sl@0	761	Populate(m3,6,100,3);
sl@0	762	Populate(m5,10,100,5);
sl@0	763	Populate(m7,14,100,7);
sl@0	764	Union(hs3, m1);
sl@0	765	Subtract(hs3, m2);
sl@0	766	Subtract(hs3, m3);
sl@0	767	Subtract(hs3, m5);
sl@0	768	Subtract(hs3, m7);
sl@0	769	CheckSieveOutput(hs3);
sl@0	770	CheckIdentical(hs,hs3);
sl@0	771	hs3.Close();
sl@0	772	INTSET(cm2);
sl@0	773	INTSET(cm3);
sl@0	774	INTSET(cm5);
sl@0	775	INTSET(cm7);
sl@0	776	Union(cm2, m1);
sl@0	777	Subtract(cm2, m2);
sl@0	778	Union(cm3, m1);
sl@0	779	Subtract(cm3, m3);
sl@0	780	Union(cm5, m1);
sl@0	781	Subtract(cm5, m5);
sl@0	782	Union(cm7, m1);
sl@0	783	Subtract(cm7, m7);
sl@0	784	Union(hs3, m1);
sl@0	785	Intersect(hs3, cm7);
sl@0	786	Intersect(hs3, cm3);
sl@0	787	Intersect(hs3, cm5);
sl@0	788	Intersect(hs3, cm2);
sl@0	789	CheckSieveOutput(hs3);
sl@0	790	CheckIdentical(hs,hs3);
sl@0	791	hs3.Close();
sl@0	792
sl@0	793
sl@0	794	cm2.Close();
sl@0	795	cm3.Close();
sl@0	796	cm5.Close();
sl@0	797	cm7.Close();
sl@0	798	m1.Close();
sl@0	799	m2.Close();
sl@0	800	m3.Close();
sl@0	801	m5.Close();
sl@0	802	m7.Close();
sl@0	803
sl@0	804	PrimeSieve(hs2, 1, 1000);
sl@0	805	CheckSieveOutput(hs2);
sl@0	806	test(hs2.Reserve(1000)==KErrNone);
sl@0	807	CCheck(hs2);
sl@0	808	CheckSieveOutput(hs2); // check that Reserve() preserves existing entries
sl@0	809
sl@0	810	PrimeSieve(hs, 100, 997);
sl@0	811	CheckSieveOutput(hs);
sl@0	812	CCheck(hs);
sl@0	813	CheckIdentical(hs,hs2);
sl@0	814
sl@0	815	hs2.Close();
sl@0	816	Union(hs2, hs);
sl@0	817	CheckIdentical(hs,hs2);
sl@0	818	CheckSieveOutput(hs2);
sl@0	819
sl@0	820	hs2.Close();
sl@0	821	hs.Close();
sl@0	822
sl@0	823	test(CheckSmallHashSet(hs)==0);
sl@0	824	AddToSmallHashSet(hs, 1);
sl@0	825	test(CheckSmallHashSet(hs)==1);
sl@0	826	AddToSmallHashSet(hs, 4);
sl@0	827	test(CheckSmallHashSet(hs)==5);
sl@0	828	AddToSmallHashSet(hs, 0x80000001);
sl@0	829	test(CheckSmallHashSet(hs)==0x80000005);
sl@0	830	AddToSmallHashSet(hs, 0x317217f8);
sl@0	831	test(CheckSmallHashSet(hs)==0xb17217fd);
sl@0	832	RemoveFromSmallHashSet(hs, 0x00000007);
sl@0	833	test(CheckSmallHashSet(hs)==0xb17217f8);
sl@0	834	RemoveFromSmallHashSet(hs, 0xffffffff);
sl@0	835	test(CheckSmallHashSet(hs)==0);
sl@0	836	hs.Close();
sl@0	837	}
sl@0	838
sl@0	839	void TestHashIter()
sl@0	840	{
sl@0	841	test.Next(_L("Test iterators"));
sl@0	842
sl@0	843	RHashSet<TInt> hs; // empty
sl@0	844	RHashSet<TInt>::TIter iter(hs);
sl@0	845	test(iter.Next() == 0);
sl@0	846	test(iter.Current() == 0);
sl@0	847	iter.RemoveCurrent();
sl@0	848	test(iter.Next() == 0);
sl@0	849	test(iter.Current() == 0);
sl@0	850
sl@0	851	test(hs.Insert(1) == KErrNone);
sl@0	852	test(hs.Insert(2) == KErrNone);
sl@0	853	test(hs.Insert(3) == KErrNone);
sl@0	854	iter.Reset();
sl@0	855	TUint mask = 14;
sl@0	856	TInt i;
sl@0	857	for (i=0; i<3; ++i)
sl@0	858	{
sl@0	859	const TInt* p = iter.Next();
sl@0	860	test(p!=0);
sl@0	861	TInt x = *p;
sl@0	862	test (x>=1 && x<=3 && (mask&(1<<x))!=0);
sl@0	863	mask &= ~(1<<x);
sl@0	864	}
sl@0	865	test(iter.Next() == 0);
sl@0	866	test(mask==0);
sl@0	867	test(CheckSmallHashSet(hs)==0x0e);
sl@0	868	test(hs.Insert(4) == KErrNone);
sl@0	869	test(hs.Insert(5) == KErrNone);
sl@0	870	test(hs.Insert(6) == KErrNone);
sl@0	871	test(hs.Insert(7) == KErrNone);
sl@0	872	test(CheckSmallHashSet(hs)==0xfe);
sl@0	873	iter.Reset();
sl@0	874	while(iter.Next())
sl@0	875	{
sl@0	876	if ((*iter.Current() & 1) == 0)
sl@0	877	iter.RemoveCurrent();
sl@0	878	}
sl@0	879	test(CheckSmallHashSet(hs)==0xaa);
sl@0	880	iter.Reset();
sl@0	881	while(iter.Next())
sl@0	882	{
sl@0	883	iter.RemoveCurrent();
sl@0	884	}
sl@0	885	test(CheckSmallHashSet(hs)==0);
sl@0	886	iter.Reset();
sl@0	887	test(iter.Next() == 0);
sl@0	888	test(iter.Current() == 0);
sl@0	889	RHashSet<TInt> empty;
sl@0	890	CheckIdentical(hs, empty);
sl@0	891	#ifdef _DEBUG
sl@0	892	__UHEAP_FAILNEXT(1);
sl@0	893	test(empty.Insert(1)==KErrNoMemory);
sl@0	894	test(empty.Insert(1)==KErrNone);
sl@0	895	empty.Close();
sl@0	896	__UHEAP_FAILNEXT(1);
sl@0	897	test(hs.Insert(1)==KErrNone);
sl@0	898	hs.Close();
sl@0	899	__UHEAP_FAILNEXT(1);
sl@0	900	test(hs.Insert(1)==KErrNoMemory);
sl@0	901	#endif
sl@0	902	hs.Close();
sl@0	903	}
sl@0	904
sl@0	905	void Print(const char* aTitle, const RHashMap<TInt,TTestName>& aM)
sl@0	906	{
sl@0	907	TBuf<256> buf;
sl@0	908	buf.Copy(TPtrC8((const TUint8*)aTitle));
sl@0	909	test.Printf(_L("%S\n"), &buf);
sl@0	910	RHashMap<TInt,TTestName>::TIter iter(aM);
sl@0	911	FOREVER
sl@0	912	{
sl@0	913	const TInt* p = iter.NextKey();
sl@0	914	if (!p) break;
sl@0	915	buf.Copy(*iter.CurrentValue());
sl@0	916	test.Printf(_L("%d: %S\n"), *p, &buf);
sl@0	917	}
sl@0	918	}
sl@0	919
sl@0	920	void Print(const char* aTitle, const RHashSet<TTestName>& aS)
sl@0	921	{
sl@0	922	TBuf<256> buf;
sl@0	923	buf.Copy(TPtrC8((const TUint8*)aTitle));
sl@0	924	test.Printf(_L("%S\n"), &buf);
sl@0	925	RHashSet<TTestName>::TIter iter(aS);
sl@0	926	FOREVER
sl@0	927	{
sl@0	928	if (!iter.Next())
sl@0	929	break;
sl@0	930	buf.Copy(*iter.Current());
sl@0	931	test.Printf(_L("%S\n"), &buf);
sl@0	932	}
sl@0	933	}
sl@0	934
sl@0	935	void TestHashMap()
sl@0	936	{
sl@0	937	test.Next(_L("Test RHashMap"));
sl@0	938
sl@0	939	RHashMap<TInt,TInt> ht;
sl@0	940	CCheck(ht); // check consistency for empty table
sl@0	941	TInt x;
sl@0	942	for (x=0; x<200; x++)
sl@0	943	{
sl@0	944	TInt r = ht.Insert(x*x, x);
sl@0	945	test(r==KErrNone);
sl@0	946	}
sl@0	947	test(ht.Count()==200);
sl@0	948
sl@0	949	TInt z = 0;
sl@0	950	TInt y;
sl@0	951	for (x=0; x<40000; x++)
sl@0	952	{
sl@0	953	const TInt* e = ht.Find(x);
sl@0	954	if (e)
sl@0	955	{
sl@0	956	const TInt& ee = ht.FindL(x);
sl@0	957	test(&ee==e);
sl@0	958	y = *e;
sl@0	959	// test.Printf(_L("Find(%d) -> %d\n"), x, y);
sl@0	960	test(x == z*z);
sl@0	961	test(y == z);
sl@0	962	++z;
sl@0	963	}
sl@0	964	else
sl@0	965	{
sl@0	966	TRAPD(rr, ht.FindL(x));
sl@0	967	test(rr==KErrNotFound);
sl@0	968	}
sl@0	969	}
sl@0	970	CCheck(ht);
sl@0	971
sl@0	972	for (x=0; x<200; x++)
sl@0	973	{
sl@0	974	TInt r = ht.Insert(xxx, x);
sl@0	975	test(r==KErrNone);
sl@0	976	}
sl@0	977	test(ht.Count()==200*2-6);
sl@0	978	CCheck(ht);
sl@0	979
sl@0	980	TInt sq = 0;
sl@0	981	TInt cb = 0;
sl@0	982	for (x=0; x<8000000; x++)
sl@0	983	{
sl@0	984	const TInt* e = ht.Find(x);
sl@0	985	if (e)
sl@0	986	{
sl@0	987	const TInt& ee = ht.FindL(x);
sl@0	988	test(&ee==e);
sl@0	989	y = *e;
sl@0	990	// test.Printf(_L("Find(%d) -> %d\n"), x, y);
sl@0	991	if (x == cbcbcb)
sl@0	992	{
sl@0	993	test(y==cb);
sl@0	994	++cb;
sl@0	995	if (x == sq*sq)
sl@0	996	++sq;
sl@0	997	}
sl@0	998	else if (x == sq*sq)
sl@0	999	{
sl@0	1000	test(y==sq);
sl@0	1001	++sq;
sl@0	1002	}
sl@0	1003	}
sl@0	1004	}
sl@0	1005
sl@0	1006	for (x=0; x<200; x++)
sl@0	1007	{
sl@0	1008	TInt r = ht.Remove(x*x);
sl@0	1009	test(r==KErrNone);
sl@0	1010	}
sl@0	1011	test(ht.Count()==200-6);
sl@0	1012	CCheck(ht);
sl@0	1013
sl@0	1014	cb = 2;
sl@0	1015	for (x=2; x<8000000; x++)
sl@0	1016	{
sl@0	1017	const TInt* e = ht.Find(x);
sl@0	1018	if (e)
sl@0	1019	{
sl@0	1020	const TInt& ee = ht.FindL(x);
sl@0	1021	test(&ee==e);
sl@0	1022	y = *e;
sl@0	1023	// test.Printf(_L("Find(%d) -> %d\n"), x, y);
sl@0	1024	if (cb == 4 \|\| cb == 9 \|\| cb == 16 \|\| cb == 25) ++cb;
sl@0	1025	test(x == cbcbcb);
sl@0	1026	test(y == cb);
sl@0	1027	++cb;
sl@0	1028	}
sl@0	1029	}
sl@0	1030
sl@0	1031	SetMap<TInt,TInt>(ht, 17);
sl@0	1032
sl@0	1033	ht.Close();
sl@0	1034
sl@0	1035	PrintNumberInWords(2000);
sl@0	1036	PrintNumberInWords(2001);
sl@0	1037	PrintNumberInWords(131072);
sl@0	1038	PrintNumberInWords(111111);
sl@0	1039	PrintNumberInWords(524288);
sl@0	1040
sl@0	1041	INTSET(all);
sl@0	1042	Populate(all,0,1000,1);
sl@0	1043	RHashMap<TInt,TTestName> to_words(&DefaultHash::Integer, &DefaultIdentity::Integer);
sl@0	1044	UnionTransform<TInt,TTestName>(to_words, all, &NumberInWords);
sl@0	1045	RHashMap<TTestName,TInt> from_words(&HashTestName, &TestNameIdentity);
sl@0	1046	UnionInverse<TInt,TTestName>(from_words, to_words);
sl@0	1047	// Print("TO WORDS:", to_words);
sl@0	1048	INTSET(primes);
sl@0	1049	PrimeSieve(primes, 1, 100);
sl@0	1050	// Print("Primes 1-100", primes);
sl@0	1051	RHashMap<TInt,TTestName> prime_map(&DefaultHash::Integer, &DefaultIdentity::Integer);
sl@0	1052	UnionTransform<TInt,TTestName>(prime_map, primes, &NumberInWords);
sl@0	1053	// Print("Prime map 1-100", prime_map);
sl@0	1054	INTSET(pmkeys);
sl@0	1055	UnionKeys<TInt,TTestName>(pmkeys, prime_map);
sl@0	1056	NAMESET(pmval);
sl@0	1057	NAMESET(pmval2);
sl@0	1058	UnionValues<TInt,TTestName>(pmval, prime_map);
sl@0	1059	CheckIdentical(pmkeys, primes);
sl@0	1060	INTSET(pr2);
sl@0	1061	UnionMap<TTestName,TInt>(pr2, pmval, from_words);
sl@0	1062	CheckIdentical(pr2, primes);
sl@0	1063	pr2.Close();
sl@0	1064	Union(pmval2, pmval);
sl@0	1065	// Print("pmval",pmval);
sl@0	1066	// Print("pmval2",pmval2);
sl@0	1067	CheckIdentical(pmval2, pmval);
sl@0	1068	UnionMap<TTestName,TInt>(pr2, pmval2, from_words);
sl@0	1069	CheckIdentical(pr2, primes);
sl@0	1070
sl@0	1071	pr2.Close();
sl@0	1072	pmval.Close();
sl@0	1073	pmval2.Close();
sl@0	1074	pmkeys.Close();
sl@0	1075	prime_map.Close();
sl@0	1076	primes.Close();
sl@0	1077	all.Close();
sl@0	1078
sl@0	1079	INTSET(m);
sl@0	1080	Populate(all,2,1000,1);
sl@0	1081
sl@0	1082	NAMESET(pr3);
sl@0	1083	NAMESET(nm);
sl@0	1084	UnionMap<TInt,TTestName>(pr3, all, to_words);
sl@0	1085	all.Close();
sl@0	1086	CCheck(pr3);
sl@0	1087
sl@0	1088	Populate(m,4,1000,2);
sl@0	1089	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0	1090	m.Close();
sl@0	1091	Subtract(pr3, nm);
sl@0	1092	nm.Close();
sl@0	1093
sl@0	1094	Populate(m,6,1000,3);
sl@0	1095	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0	1096	m.Close();
sl@0	1097	Subtract(pr3, nm);
sl@0	1098	nm.Close();
sl@0	1099
sl@0	1100	Populate(m,10,1000,5);
sl@0	1101	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0	1102	m.Close();
sl@0	1103	Subtract(pr3, nm);
sl@0	1104	nm.Close();
sl@0	1105
sl@0	1106	Populate(m,14,1000,7);
sl@0	1107	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0	1108	m.Close();
sl@0	1109	Subtract(pr3, nm);
sl@0	1110	nm.Close();
sl@0	1111
sl@0	1112	Populate(m,22,1000,11);
sl@0	1113	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0	1114	m.Close();
sl@0	1115	Subtract(pr3, nm);
sl@0	1116	nm.Close();
sl@0	1117
sl@0	1118	Populate(m,26,1000,13);
sl@0	1119	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0	1120	m.Close();
sl@0	1121	Subtract(pr3, nm);
sl@0	1122	nm.Close();
sl@0	1123
sl@0	1124	Populate(m,34,1000,17);
sl@0	1125	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0	1126	m.Close();
sl@0	1127	Subtract(pr3, nm);
sl@0	1128	nm.Close();
sl@0	1129
sl@0	1130	Populate(m,38,1000,19);
sl@0	1131	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0	1132	m.Close();
sl@0	1133	Subtract(pr3, nm);
sl@0	1134	nm.Close();
sl@0	1135
sl@0	1136	Populate(m,46,1000,23);
sl@0	1137	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0	1138	m.Close();
sl@0	1139	Subtract(pr3, nm);
sl@0	1140	nm.Close();
sl@0	1141
sl@0	1142	Populate(m,58,1000,29);
sl@0	1143	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0	1144	m.Close();
sl@0	1145	Subtract(pr3, nm);
sl@0	1146	nm.Close();
sl@0	1147
sl@0	1148	Populate(m,62,1000,31);
sl@0	1149	UnionMap<TInt,TTestName>(nm, m, to_words);
sl@0	1150	m.Close();
sl@0	1151	Subtract(pr3, nm);
sl@0	1152	nm.Close();
sl@0	1153
sl@0	1154	// Print("pr3",pr3);
sl@0	1155	PrimeSieve(primes, 1, 1000);
sl@0	1156	UnionMap<TInt,TTestName>(nm, primes, to_words);
sl@0	1157	CheckIdentical(nm, pr3);
sl@0	1158	CCheck(pr3);
sl@0	1159	UnionMap<TTestName,TInt>(m, pr3, from_words);
sl@0	1160	CheckIdentical(m, primes);
sl@0	1161
sl@0	1162	m.Close();
sl@0	1163	nm.Close();
sl@0	1164	primes.Close();
sl@0	1165	pr3.Close();
sl@0	1166	from_words.Close();
sl@0	1167	to_words.Close();
sl@0	1168	}
sl@0	1169
sl@0	1170	void PopulateArray8(TInt aMax)
sl@0	1171	{
sl@0	1172	TInt i;
sl@0	1173	for (i=0; i<aMax; ++i)
sl@0	1174	{
sl@0	1175	TTestName n(NumberInWords(i));
sl@0	1176	HBufC8* p = n.Alloc();
sl@0	1177	test(p!=0);
sl@0	1178	TInt r = DesC8Array.Append(p);
sl@0	1179	test(r==KErrNone);
sl@0	1180	}
sl@0	1181	}
sl@0	1182
sl@0	1183	void PopulateArray16(TInt aMax)
sl@0	1184	{
sl@0	1185	TInt i;
sl@0	1186	for (i=0; i<aMax; ++i)
sl@0	1187	{
sl@0	1188	TTestName n(NumberInWords(i));
sl@0	1189	TBuf<128> n16;
sl@0	1190	n16.Copy(n);
sl@0	1191	HBufC16* p = n16.Alloc();
sl@0	1192	test(p!=0);
sl@0	1193	TInt r = DesC16Array.Append(p);
sl@0	1194	test(r==KErrNone);
sl@0	1195	}
sl@0	1196	}
sl@0	1197
sl@0	1198	TUint32 istrh8(const TDesC8* const & a)
sl@0	1199	{
sl@0	1200	return DefaultHash::Des8(*a);
sl@0	1201	}
sl@0	1202
sl@0	1203	TBool istrid8(const TDesC8* const & aA, const TDesC8* const & aB)
sl@0	1204	{
sl@0	1205	return aA == aB;
sl@0	1206	}
sl@0	1207
sl@0	1208	TUint32 istrh16(const TDesC16* const & a)
sl@0	1209	{
sl@0	1210	return DefaultHash::Des16(*a);
sl@0	1211	}
sl@0	1212
sl@0	1213	TBool istrid16(const TDesC16* const & aA, const TDesC16* const & aB)
sl@0	1214	{
sl@0	1215	return aA == aB;
sl@0	1216	}
sl@0	1217
sl@0	1218	void TestPtrHashSet()
sl@0	1219	{
sl@0	1220	test.Next(_L("Test RPtrHashSet"));
sl@0	1221
sl@0	1222	STRSET8(s);
sl@0	1223	CCheck(s); // check consistency for empty table
sl@0	1224	RHashMap<const TDesC8*, TInt> hm(&istrh8, &istrid8);
sl@0	1225	RPtrHashSet<TDesC8>::TIter iter(s);
sl@0	1226	const TDesC8* q;
sl@0	1227	TInt i;
sl@0	1228	for (i=0; i<4096; ++i)
sl@0	1229	{
sl@0	1230	TInt r = s.Insert(DesC8Array[i]);
sl@0	1231	test(r==KErrNone);
sl@0	1232	r = hm.Insert(DesC8Array[i], i);
sl@0	1233	test(r==KErrNone);
sl@0	1234	}
sl@0	1235	CCheck(s);
sl@0	1236	for (i=0; i<4100; ++i)
sl@0	1237	{
sl@0	1238	TTestName n(NumberInWords(i));
sl@0	1239	const TDesC8* p = s.Find(n);
sl@0	1240	if (i<4096)
sl@0	1241	{
sl@0	1242	const TDesC8& pp = s.FindL(n);
sl@0	1243	test(p && *p==n && p==DesC8Array[i]);
sl@0	1244	test(&pp == p);
sl@0	1245	}
sl@0	1246	else
sl@0	1247	{
sl@0	1248	test(!p);
sl@0	1249	TRAPD(rr,s.FindL(n));
sl@0	1250	test(rr==KErrNotFound);
sl@0	1251	}
sl@0	1252	}
sl@0	1253	while((q=iter.Next())!=0)
sl@0	1254	{
sl@0	1255	const TInt* qi = hm.Find(q);
sl@0	1256	test(qi!=0 && qi>=0 && qi<4096);
sl@0	1257	test(DesC8Array[*qi]==q);
sl@0	1258	}
sl@0	1259	for (i=0; i<4100; i+=2)
sl@0	1260	{
sl@0	1261	TTestName n(NumberInWords(i));
sl@0	1262	TInt r = s.Remove(&n);
sl@0	1263	if (i<4096)
sl@0	1264	test(r==KErrNone);
sl@0	1265	else
sl@0	1266	test(r==KErrNotFound);
sl@0	1267	}
sl@0	1268	test(s.Count()==2048);
sl@0	1269	CCheck(s);
sl@0	1270	for (i=0; i<4100; ++i)
sl@0	1271	{
sl@0	1272	TTestName n(NumberInWords(i));
sl@0	1273	const TDesC8* p = s.Find(n);
sl@0	1274	if (i<4096 && (i&1))
sl@0	1275	test(p && *p==n && p==DesC8Array[i]);
sl@0	1276	else
sl@0	1277	test(!p);
sl@0	1278	}
sl@0	1279	iter.Reset();
sl@0	1280	while((q=iter.Next())!=0)
sl@0	1281	{
sl@0	1282	const TInt* qi = hm.Find(q);
sl@0	1283	test(qi!=0 && qi>=0 && qi<4096 && (*qi&1));
sl@0	1284	test(DesC8Array[*qi]==q);
sl@0	1285	}
sl@0	1286	for (i=2; i<4096; i+=4)
sl@0	1287	{
sl@0	1288	TInt r = s.Insert(DesC8Array[i]);
sl@0	1289	test(r==KErrNone);
sl@0	1290	}
sl@0	1291	test(s.Count()==3072);
sl@0	1292	CCheck(s);
sl@0	1293	for (i=0; i<4100; ++i)
sl@0	1294	{
sl@0	1295	TTestName n(NumberInWords(i));
sl@0	1296	const TDesC8* p = s.Find(n);
sl@0	1297	if (i<4096 && (i&3))
sl@0	1298	test(p && *p==n && p==DesC8Array[i]);
sl@0	1299	else
sl@0	1300	test(!p);
sl@0	1301	}
sl@0	1302	iter.Reset();
sl@0	1303	while((q=iter.Next())!=0)
sl@0	1304	{
sl@0	1305	const TInt* qi = hm.Find(q);
sl@0	1306	test(qi!=0 && qi>=0 && qi<4096 && (*qi&3));
sl@0	1307	test(DesC8Array[*qi]==q);
sl@0	1308	}
sl@0	1309	s.Close();
sl@0	1310
sl@0	1311	// test ResetAndDestroy
sl@0	1312	for (i=0; i<16; ++i)
sl@0	1313	{
sl@0	1314	TInt r = s.Insert(DesC8Array[i]->Alloc());
sl@0	1315	test(r==KErrNone);
sl@0	1316	}
sl@0	1317	iter.Reset();
sl@0	1318	while((q=iter.Next())!=0)
sl@0	1319	{
sl@0	1320	const TInt* qi = hm.Find(q);
sl@0	1321	test(qi!=0 && qi>=0 && qi<16);
sl@0	1322	test(DesC8Array[qi]==*q);
sl@0	1323	test(DesC8Array[*qi]!=q);
sl@0	1324	}
sl@0	1325	s.ResetAndDestroy();
sl@0	1326	hm.Close();
sl@0	1327
sl@0	1328
sl@0	1329	STRSET16(S);
sl@0	1330	RHashMap<const TDesC16*, TInt> HM(&istrh16, &istrid16);
sl@0	1331	RPtrHashSet<TDesC16>::TIter ITER(S);
sl@0	1332	const TDesC16* Q;
sl@0	1333	for (i=0; i<4096; ++i)
sl@0	1334	{
sl@0	1335	TInt r = S.Insert(DesC16Array[i]);
sl@0	1336	test(r==KErrNone);
sl@0	1337	r = HM.Insert(DesC16Array[i], i);
sl@0	1338	test(r==KErrNone);
sl@0	1339	}
sl@0	1340	CCheck(S);
sl@0	1341	for (i=0; i<4100; ++i)
sl@0	1342	{
sl@0	1343	TTestName n(NumberInWords(i));
sl@0	1344	TBuf<80> buf;
sl@0	1345	buf.Copy(n);
sl@0	1346	const TDesC16* p = S.Find(buf);
sl@0	1347	if (i<4096)
sl@0	1348	test(p && *p==buf && p==DesC16Array[i]);
sl@0	1349	else
sl@0	1350	test(!p);
sl@0	1351	}
sl@0	1352	while((Q=ITER.Next())!=0)
sl@0	1353	{
sl@0	1354	const TInt* qi = HM.Find(Q);
sl@0	1355	test(qi!=0 && qi>=0 && qi<4096);
sl@0	1356	test(DesC16Array[*qi]==Q);
sl@0	1357	}
sl@0	1358	for (i=0; i<4100; i+=2)
sl@0	1359	{
sl@0	1360	TTestName n(NumberInWords(i));
sl@0	1361	TBuf<80> buf;
sl@0	1362	buf.Copy(n);
sl@0	1363	TInt r = S.Remove(&buf);
sl@0	1364	if (i<4096)
sl@0	1365	test(r==KErrNone);
sl@0	1366	else
sl@0	1367	test(r==KErrNotFound);
sl@0	1368	}
sl@0	1369	test(S.Count()==2048);
sl@0	1370	CCheck(S);
sl@0	1371	for (i=0; i<4100; ++i)
sl@0	1372	{
sl@0	1373	TTestName n(NumberInWords(i));
sl@0	1374	TBuf<80> buf;
sl@0	1375	buf.Copy(n);
sl@0	1376	const TDesC16* p = S.Find(buf);
sl@0	1377	if (i<4096 && (i&1))
sl@0	1378	test(p && *p==buf && p==DesC16Array[i]);
sl@0	1379	else
sl@0	1380	test(!p);
sl@0	1381	}
sl@0	1382	ITER.Reset();
sl@0	1383	while((Q=ITER.Next())!=0)
sl@0	1384	{
sl@0	1385	const TInt* qi = HM.Find(Q);
sl@0	1386	test(qi!=0 && qi>=0 && qi<4096 && (*qi&1));
sl@0	1387	test(DesC16Array[*qi]==Q);
sl@0	1388	}
sl@0	1389	for (i=2; i<4096; i+=4)
sl@0	1390	{
sl@0	1391	TInt r = S.Insert(DesC16Array[i]);
sl@0	1392	test(r==KErrNone);
sl@0	1393	}
sl@0	1394	test(S.Count()==3072);
sl@0	1395	CCheck(S);
sl@0	1396	for (i=0; i<4100; ++i)
sl@0	1397	{
sl@0	1398	TTestName n(NumberInWords(i));
sl@0	1399	TBuf<80> buf;
sl@0	1400	buf.Copy(n);
sl@0	1401	const TDesC16* p = S.Find(buf);
sl@0	1402	if (i<4096 && (i&3))
sl@0	1403	test(p && *p==buf && p==DesC16Array[i]);
sl@0	1404	else
sl@0	1405	test(!p);
sl@0	1406	}
sl@0	1407	ITER.Reset();
sl@0	1408	while((Q=ITER.Next())!=0)
sl@0	1409	{
sl@0	1410	const TInt* qi = HM.Find(Q);
sl@0	1411	test(qi!=0 && qi>=0 && qi<4096 && (*qi&3));
sl@0	1412	test(DesC16Array[*qi]==Q);
sl@0	1413	}
sl@0	1414	S.Close();
sl@0	1415
sl@0	1416	// test ResetAndDestroy
sl@0	1417	for (i=0; i<16; ++i)
sl@0	1418	{
sl@0	1419	TInt r = S.Insert(DesC16Array[i]->Alloc());
sl@0	1420	test(r==KErrNone);
sl@0	1421	}
sl@0	1422	ITER.Reset();
sl@0	1423	while((Q=ITER.Next())!=0)
sl@0	1424	{
sl@0	1425	const TInt* qi = HM.Find(Q);
sl@0	1426	test(qi!=0 && qi>=0 && qi<16);
sl@0	1427	test(DesC16Array[qi]==*Q);
sl@0	1428	test(DesC16Array[*qi]!=Q);
sl@0	1429	}
sl@0	1430	S.ResetAndDestroy();
sl@0	1431	HM.Close();
sl@0	1432	}
sl@0	1433
sl@0	1434	void TestPtrHashMap()
sl@0	1435	{
sl@0	1436	test.Next(_L("Test RPtrHashMap"));
sl@0	1437
sl@0	1438	STRMAP8(map);
sl@0	1439	CCheck(map); // check consistency for empty table
sl@0	1440	STRMAP8(id);
sl@0	1441	TInt i;
sl@0	1442	for (i=0; i<4096; ++i)
sl@0	1443	{
sl@0	1444	TInt r = map.Insert(DesC8Array[i], DesC8Array[(i+1)&0xfff]);
sl@0	1445	test(r==KErrNone);
sl@0	1446	r = id.Insert(DesC8Array[i], DesC8Array[i]);
sl@0	1447	test(r==KErrNone);
sl@0	1448	}
sl@0	1449	for (i=0; i<4096; ++i)
sl@0	1450	{
sl@0	1451	const TDesC8* p = map.Find(*DesC8Array[i]);
sl@0	1452	test(p == DesC8Array[(i+1)&0xfff]);
sl@0	1453	const TDesC8& pp = map.FindL(*DesC8Array[i]);
sl@0	1454	test(&pp == p);
sl@0	1455	}
sl@0	1456	TRAPD(rr,map.FindL(_L8("two")));
sl@0	1457	test(rr==KErrNone);
sl@0	1458	TRAP(rr,map.FindL(_L8("twx")));
sl@0	1459	test(rr==KErrNotFound);
sl@0	1460	CCheck(map);
sl@0	1461	STRMAP8(map2);
sl@0	1462	STRMAP8(mapi);
sl@0	1463	STRMAP8(map3);
sl@0	1464	UnionInverse<TDesC8,TDesC8>(mapi, map);
sl@0	1465	UnionCompose<TDesC8,TDesC8,TDesC8>(map2, map, map);
sl@0	1466	UnionCompose<TDesC8,TDesC8,TDesC8>(map3, map, mapi);
sl@0	1467	CheckIdenticalMaps<TDesC8,TDesC8>(map3, id);
sl@0	1468	map3.Close();
sl@0	1469	UnionCompose<TDesC8,TDesC8,TDesC8>(map3, map2, mapi);
sl@0	1470	CheckIdenticalMaps<TDesC8,TDesC8>(map3, map);
sl@0	1471	map3.Close();
sl@0	1472	for (i=0; i<4096; ++i)
sl@0	1473	{
sl@0	1474	TInt r = map3.Insert(DesC8Array[i], DesC8Array[(i+2)&0xfff]);
sl@0	1475	test(r==KErrNone);
sl@0	1476	}
sl@0	1477	CheckIdenticalMaps<TDesC8,TDesC8>(map3, map2);
sl@0	1478	map3.Close();
sl@0	1479
sl@0	1480	mapi.Close();
sl@0	1481	map2.Close();
sl@0	1482	id.Close();
sl@0	1483	map.Close();
sl@0	1484
sl@0	1485	// test ResetAndDestroy()
sl@0	1486	for(i=0; i<16; ++i)
sl@0	1487	{
sl@0	1488	TInt r = map.Insert(DesC8Array[i]->Alloc(), DesC8Array[i*i]->Alloc());
sl@0	1489	test(r==KErrNone);
sl@0	1490	}
sl@0	1491	map.ResetAndDestroy();
sl@0	1492	}
sl@0	1493
sl@0	1494	void TestOOM()
sl@0	1495	{
sl@0	1496	// Max out memory and check it still works
sl@0	1497	test.Next(_L("Test OOM"));
sl@0	1498
sl@0	1499	TInt x = 0;
sl@0	1500	TInt n = 0;
sl@0	1501	TInt r;
sl@0	1502	INTSET(set);
sl@0	1503	FOREVER
sl@0	1504	{
sl@0	1505	x += 0x58b90bfb;
sl@0	1506	r = set.Insert(x);
sl@0	1507	if (r != KErrNone)
sl@0	1508	break;
sl@0	1509	++n;
sl@0	1510	}
sl@0	1511	test(r==KErrNoMemory);
sl@0	1512	TRAPD(rr,set.InsertL(x));
sl@0	1513	test(rr==KErrNoMemory);
sl@0	1514	test.Printf(_L("%d integers stored\n"), n);
sl@0	1515	test(set.Count()==n);
sl@0	1516	TRAP(rr,set.InsertL(0x58b90bfb)); // already there
sl@0	1517	test(rr==KErrNone); // should succeed
sl@0	1518
sl@0	1519	// final count should be a power of 2 minus 1
sl@0	1520	test( (n&(n+1)) == 0 );
sl@0	1521
sl@0	1522	x = 0;
sl@0	1523	TInt i;
sl@0	1524	for (i=0; i<=n; ++i) // check everything has been stored correctly
sl@0	1525	{
sl@0	1526	x += 0x58b90bfb;
sl@0	1527	const TInt* p = set.Find(x);
sl@0	1528	if (i < n)
sl@0	1529	test(p && *p == x);
sl@0	1530	else
sl@0	1531	test(!p);
sl@0	1532	}
sl@0	1533	set.Close();
sl@0	1534	TInt nn;
sl@0	1535	for (nn=256; nn<=n+256; nn+=256)
sl@0	1536	{
sl@0	1537	r = set.Reserve(nn);
sl@0	1538	set.Close();
sl@0	1539	if (r!=KErrNone)
sl@0	1540	break;
sl@0	1541	}
sl@0	1542	test.Printf(_L("Max reserve %d\n"),nn);
sl@0	1543	TInt thresh = 3*((n+1)>>2);
sl@0	1544	test(nn == thresh + 256);
sl@0	1545	}
sl@0	1546
sl@0	1547	class RDummyAllocator : public RAllocator
sl@0	1548	{
sl@0	1549	public:
sl@0	1550	virtual TAny* Alloc(TInt) {test(0); return 0;}
sl@0	1551	virtual void Free(TAny*) {test(0);}
sl@0	1552	virtual TAny* ReAlloc(TAny*, TInt, TInt) {test(0); return 0;}
sl@0	1553	virtual TInt AllocLen(const TAny*) const {test(0); return 0;}
sl@0	1554	virtual TInt Compress() {test(0); return 0;}
sl@0	1555	virtual void Reset() {test(0);}
sl@0	1556	virtual TInt AllocSize(TInt&) const {test(0); return 0;}
sl@0	1557	virtual TInt Available(TInt&) const {test(0); return 0;}
sl@0	1558	virtual TInt DebugFunction(TInt, TAny, TAny) {test(0); return 0;}
sl@0	1559	virtual TInt Extension_(TUint, TAny&, TAny) {test(0); return 0;}
sl@0	1560	};
sl@0	1561
sl@0	1562	void IntegerBenchmark(TInt aCount, TBool aReserve)
sl@0	1563	{
sl@0	1564	RArray<TInt> array;
sl@0	1565	TUint32 before, after, diff;
sl@0	1566	TInt x=0;
sl@0	1567	TInt i;
sl@0	1568	double avg;
sl@0	1569
sl@0	1570	test.Printf(_L("** INTEGER BENCHMARKS *\n"));
sl@0	1571
sl@0	1572	if (!aReserve)
sl@0	1573	{
sl@0	1574	before = User::NTickCount();
sl@0	1575	for (i=0; i<aCount; ++i)
sl@0	1576	{
sl@0	1577	x += 0x58b90bfb;
sl@0	1578	TInt r = array.InsertInOrder(x);
sl@0	1579	test(r==KErrNone);
sl@0	1580	}
sl@0	1581	after = User::NTickCount();
sl@0	1582	diff = after - before;
sl@0	1583	diff *= NanoTickPeriod;
sl@0	1584	avg = (double)diff / (double)aCount;
sl@0	1585	test.Printf(_L("ARRAY: %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1586
sl@0	1587	x=0;
sl@0	1588	before = User::NTickCount();
sl@0	1589	for (i=0; i<aCount; ++i)
sl@0	1590	{
sl@0	1591	x += 0x58b90bfb;
sl@0	1592	TInt r = array.FindInOrder(x);
sl@0	1593	test(r>=0);
sl@0	1594	}
sl@0	1595	after = User::NTickCount();
sl@0	1596	diff = after - before;
sl@0	1597	diff *= NanoTickPeriod;
sl@0	1598	avg = (double)diff / (double)aCount;
sl@0	1599	test.Printf(_L("ARRAY: %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1600
sl@0	1601	before = User::NTickCount();
sl@0	1602	for (i=0; i<aCount; ++i)
sl@0	1603	{
sl@0	1604	x += 0x58b90bfb;
sl@0	1605	TInt r = array.FindInOrder(x);
sl@0	1606	test(r==KErrNotFound);
sl@0	1607	}
sl@0	1608	after = User::NTickCount();
sl@0	1609	diff = after - before;
sl@0	1610	diff *= NanoTickPeriod;
sl@0	1611	avg = (double)diff / (double)aCount;
sl@0	1612	test.Printf(_L("ARRAY: %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1613
sl@0	1614	x=0;
sl@0	1615	before = User::NTickCount();
sl@0	1616	for (i=0; i<aCount; ++i)
sl@0	1617	{
sl@0	1618	x += 0x58b90bfb;
sl@0	1619	TInt r = array.FindInOrder(x);
sl@0	1620	test(r>=0);
sl@0	1621	array.Remove(r);
sl@0	1622	}
sl@0	1623	after = User::NTickCount();
sl@0	1624	diff = after - before;
sl@0	1625	diff *= NanoTickPeriod;
sl@0	1626	avg = (double)diff / (double)aCount;
sl@0	1627	test.Printf(_L("ARRAY: %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1628	array.Close();
sl@0	1629	}
sl@0	1630
sl@0	1631	INTSET(set);
sl@0	1632	x=0;
sl@0	1633	RAllocator* pA = 0;
sl@0	1634	RDummyAllocator da;
sl@0	1635	if (aReserve)
sl@0	1636	{
sl@0	1637	test(set.Reserve(aCount)==KErrNone);
sl@0	1638	pA = User::SwitchAllocator(&da); // check that no memory accesses occur
sl@0	1639	test(set.Reserve(10)==KErrNone); // shouldn't need to do anything
sl@0	1640	test(set.Reserve(aCount/2)==KErrNone); // shouldn't need to do anything
sl@0	1641	test(set.Reserve(aCount)==KErrNone); // shouldn't need to do anything
sl@0	1642	}
sl@0	1643	before = User::NTickCount();
sl@0	1644	for (i=0; i<aCount; ++i)
sl@0	1645	{
sl@0	1646	x += 0x58b90bfb;
sl@0	1647	TInt r = set.Insert(x); // we have no heap here so this tests that Reserve() has preallocated sufficient memory
sl@0	1648	test(r==KErrNone);
sl@0	1649	}
sl@0	1650	after = User::NTickCount();
sl@0	1651	diff = after - before;
sl@0	1652	diff *= NanoTickPeriod;
sl@0	1653	avg = (double)diff / (double)aCount;
sl@0	1654	if (aReserve)
sl@0	1655	User::SwitchAllocator(pA);
sl@0	1656	test.Printf(_L("HASH TABLE: %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1657
sl@0	1658	x=0;
sl@0	1659	before = User::NTickCount();
sl@0	1660	for (i=0; i<aCount; ++i)
sl@0	1661	{
sl@0	1662	x += 0x58b90bfb;
sl@0	1663	const TInt* p = set.Find(x);
sl@0	1664	test(p!=0);
sl@0	1665	}
sl@0	1666	after = User::NTickCount();
sl@0	1667	diff = after - before;
sl@0	1668	diff *= NanoTickPeriod;
sl@0	1669	avg = (double)diff / (double)aCount;
sl@0	1670	test.Printf(_L("HASH TABLE: %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1671
sl@0	1672	before = User::NTickCount();
sl@0	1673	for (i=0; i<aCount; ++i)
sl@0	1674	{
sl@0	1675	x += 0x58b90bfb;
sl@0	1676	const TInt* p = set.Find(x);
sl@0	1677	test(!p);
sl@0	1678	}
sl@0	1679	after = User::NTickCount();
sl@0	1680	diff = after - before;
sl@0	1681	diff *= NanoTickPeriod;
sl@0	1682	avg = (double)diff / (double)aCount;
sl@0	1683	test.Printf(_L("HASH TABLE: %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1684
sl@0	1685	x=0;
sl@0	1686	before = User::NTickCount();
sl@0	1687	for (i=0; i<aCount; ++i)
sl@0	1688	{
sl@0	1689	x += 0x58b90bfb;
sl@0	1690	TInt r = set.Remove(x);
sl@0	1691	test(r==KErrNone);
sl@0	1692	}
sl@0	1693	after = User::NTickCount();
sl@0	1694	diff = after - before;
sl@0	1695	diff *= NanoTickPeriod;
sl@0	1696	avg = (double)diff / (double)aCount;
sl@0	1697	test.Printf(_L("HASH TABLE: %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1698	set.Close();
sl@0	1699	}
sl@0	1700
sl@0	1701	TInt des8order(const TDesC8& aA, const TDesC8& aB)
sl@0	1702	{
sl@0	1703	return aA.Compare(aB);
sl@0	1704	}
sl@0	1705
sl@0	1706	void StringBenchmark8(TInt aCount, TBool aReserve)
sl@0	1707	{
sl@0	1708	RPointerArray<TDesC8> array;
sl@0	1709	TUint32 before, after, diff;
sl@0	1710	TInt x=0;
sl@0	1711	TInt i;
sl@0	1712	double avg;
sl@0	1713	const TDesC8 base = (const TDesC8)&DesC8Array[0];
sl@0	1714	test(base[1331] == DesC8Array[1331]);
sl@0	1715
sl@0	1716	test.Printf(_L("** 8 BIT STRING BENCHMARKS *\n"));
sl@0	1717
sl@0	1718	if (!aReserve)
sl@0	1719	{
sl@0	1720	before = User::NTickCount();
sl@0	1721	for (i=0; i<aCount; ++i)
sl@0	1722	{
sl@0	1723	x = (x+4339)&0x3fff;
sl@0	1724	TInt r = array.InsertInOrder(base[x], &des8order);
sl@0	1725	test(r==KErrNone);
sl@0	1726	}
sl@0	1727	after = User::NTickCount();
sl@0	1728	diff = after - before;
sl@0	1729	diff *= NanoTickPeriod;
sl@0	1730	avg = (double)diff / (double)aCount;
sl@0	1731	test.Printf(_L("ARRAY: %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1732
sl@0	1733	x=0;
sl@0	1734	before = User::NTickCount();
sl@0	1735	for (i=0; i<aCount; ++i)
sl@0	1736	{
sl@0	1737	x = (x+4339)&0x3fff;
sl@0	1738	TInt r = array.FindInOrder(base[x], &des8order);
sl@0	1739	test(r>=0);
sl@0	1740	}
sl@0	1741	after = User::NTickCount();
sl@0	1742	diff = after - before;
sl@0	1743	diff *= NanoTickPeriod;
sl@0	1744	avg = (double)diff / (double)aCount;
sl@0	1745	test.Printf(_L("ARRAY: %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1746
sl@0	1747	before = User::NTickCount();
sl@0	1748	for (i=0; i<aCount; ++i)
sl@0	1749	{
sl@0	1750	x = (x+4339)&0x3fff;
sl@0	1751	TInt r = array.FindInOrder(base[x], &des8order);
sl@0	1752	test(r==KErrNotFound);
sl@0	1753	}
sl@0	1754	after = User::NTickCount();
sl@0	1755	diff = after - before;
sl@0	1756	diff *= NanoTickPeriod;
sl@0	1757	avg = (double)diff / (double)aCount;
sl@0	1758	test.Printf(_L("ARRAY: %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1759
sl@0	1760	x=0;
sl@0	1761	before = User::NTickCount();
sl@0	1762	for (i=0; i<aCount; ++i)
sl@0	1763	{
sl@0	1764	x = (x+4339)&0x3fff;
sl@0	1765	TInt r = array.FindInOrder(base[x], &des8order);
sl@0	1766	test(r>=0);
sl@0	1767	array.Remove(r);
sl@0	1768	}
sl@0	1769	after = User::NTickCount();
sl@0	1770	diff = after - before;
sl@0	1771	diff *= NanoTickPeriod;
sl@0	1772	avg = (double)diff / (double)aCount;
sl@0	1773	test.Printf(_L("ARRAY: %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1774	array.Close();
sl@0	1775	}
sl@0	1776
sl@0	1777	STRSET8(set);
sl@0	1778	x=0;
sl@0	1779	if (aReserve)
sl@0	1780	test(set.Reserve(aCount)==KErrNone);
sl@0	1781	before = User::NTickCount();
sl@0	1782	for (i=0; i<aCount; ++i)
sl@0	1783	{
sl@0	1784	x = (x+4339)&0x3fff;
sl@0	1785	TInt r = set.Insert(base[x]);
sl@0	1786	test(r==KErrNone);
sl@0	1787	}
sl@0	1788	after = User::NTickCount();
sl@0	1789	diff = after - before;
sl@0	1790	diff *= NanoTickPeriod;
sl@0	1791	avg = (double)diff / (double)aCount;
sl@0	1792	test.Printf(_L("HASH TABLE: %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1793
sl@0	1794	x=0;
sl@0	1795	before = User::NTickCount();
sl@0	1796	for (i=0; i<aCount; ++i)
sl@0	1797	{
sl@0	1798	x = (x+4339)&0x3fff;
sl@0	1799	const TDesC8* p = set.Find(*base[x]);
sl@0	1800	test(p!=0);
sl@0	1801	}
sl@0	1802	after = User::NTickCount();
sl@0	1803	diff = after - before;
sl@0	1804	diff *= NanoTickPeriod;
sl@0	1805	avg = (double)diff / (double)aCount;
sl@0	1806	test.Printf(_L("HASH TABLE: %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1807
sl@0	1808	before = User::NTickCount();
sl@0	1809	for (i=0; i<aCount; ++i)
sl@0	1810	{
sl@0	1811	x = (x+4339)&0x3fff;
sl@0	1812	const TDesC8* p = set.Find(*base[x]);
sl@0	1813	test(!p);
sl@0	1814	}
sl@0	1815	after = User::NTickCount();
sl@0	1816	diff = after - before;
sl@0	1817	diff *= NanoTickPeriod;
sl@0	1818	avg = (double)diff / (double)aCount;
sl@0	1819	test.Printf(_L("HASH TABLE: %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1820
sl@0	1821	x=0;
sl@0	1822	before = User::NTickCount();
sl@0	1823	for (i=0; i<aCount; ++i)
sl@0	1824	{
sl@0	1825	x = (x+4339)&0x3fff;
sl@0	1826	TInt r = set.Remove(base[x]);
sl@0	1827	test(r==KErrNone);
sl@0	1828	}
sl@0	1829	after = User::NTickCount();
sl@0	1830	diff = after - before;
sl@0	1831	diff *= NanoTickPeriod;
sl@0	1832	avg = (double)diff / (double)aCount;
sl@0	1833	test.Printf(_L("HASH TABLE: %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1834	set.Close();
sl@0	1835	}
sl@0	1836
sl@0	1837	TInt des16order(const TDesC16& aA, const TDesC16& aB)
sl@0	1838	{
sl@0	1839	return aA.Compare(aB);
sl@0	1840	}
sl@0	1841
sl@0	1842	void StringBenchmark16(TInt aCount, TBool aReserve)
sl@0	1843	{
sl@0	1844	RPointerArray<TDesC16> array;
sl@0	1845	TUint32 before, after, diff;
sl@0	1846	TInt x=0;
sl@0	1847	TInt i;
sl@0	1848	double avg;
sl@0	1849	const TDesC16 base = (const TDesC16)&DesC16Array[0];
sl@0	1850	test(base[1331] == DesC16Array[1331]);
sl@0	1851
sl@0	1852	test.Printf(_L("** 16 BIT STRING BENCHMARKS *\n"));
sl@0	1853
sl@0	1854	if (!aReserve)
sl@0	1855	{
sl@0	1856	before = User::NTickCount();
sl@0	1857	for (i=0; i<aCount; ++i)
sl@0	1858	{
sl@0	1859	x = (x+4339)&0x3fff;
sl@0	1860	TInt r = array.InsertInOrder(base[x], &des16order);
sl@0	1861	test(r==KErrNone);
sl@0	1862	}
sl@0	1863	after = User::NTickCount();
sl@0	1864	diff = after - before;
sl@0	1865	diff *= NanoTickPeriod;
sl@0	1866	avg = (double)diff / (double)aCount;
sl@0	1867	test.Printf(_L("ARRAY: %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1868
sl@0	1869	x=0;
sl@0	1870	before = User::NTickCount();
sl@0	1871	for (i=0; i<aCount; ++i)
sl@0	1872	{
sl@0	1873	x = (x+4339)&0x3fff;
sl@0	1874	TInt r = array.FindInOrder(base[x], &des16order);
sl@0	1875	test(r>=0);
sl@0	1876	}
sl@0	1877	after = User::NTickCount();
sl@0	1878	diff = after - before;
sl@0	1879	diff *= NanoTickPeriod;
sl@0	1880	avg = (double)diff / (double)aCount;
sl@0	1881	test.Printf(_L("ARRAY: %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1882
sl@0	1883	before = User::NTickCount();
sl@0	1884	for (i=0; i<aCount; ++i)
sl@0	1885	{
sl@0	1886	x = (x+4339)&0x3fff;
sl@0	1887	TInt r = array.FindInOrder(base[x], &des16order);
sl@0	1888	test(r==KErrNotFound);
sl@0	1889	}
sl@0	1890	after = User::NTickCount();
sl@0	1891	diff = after - before;
sl@0	1892	diff *= NanoTickPeriod;
sl@0	1893	avg = (double)diff / (double)aCount;
sl@0	1894	test.Printf(_L("ARRAY: %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1895
sl@0	1896	x=0;
sl@0	1897	before = User::NTickCount();
sl@0	1898	for (i=0; i<aCount; ++i)
sl@0	1899	{
sl@0	1900	x = (x+4339)&0x3fff;
sl@0	1901	TInt r = array.FindInOrder(base[x], &des16order);
sl@0	1902	test(r>=0);
sl@0	1903	array.Remove(r);
sl@0	1904	}
sl@0	1905	after = User::NTickCount();
sl@0	1906	diff = after - before;
sl@0	1907	diff *= NanoTickPeriod;
sl@0	1908	avg = (double)diff / (double)aCount;
sl@0	1909	test.Printf(_L("ARRAY: %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1910	array.Close();
sl@0	1911	}
sl@0	1912
sl@0	1913	STRSET16(set);
sl@0	1914	x=0;
sl@0	1915	if (aReserve)
sl@0	1916	test(set.Reserve(aCount)==KErrNone);
sl@0	1917	before = User::NTickCount();
sl@0	1918	for (i=0; i<aCount; ++i)
sl@0	1919	{
sl@0	1920	x = (x+4339)&0x3fff;
sl@0	1921	TInt r = set.Insert(base[x]);
sl@0	1922	test(r==KErrNone);
sl@0	1923	}
sl@0	1924	after = User::NTickCount();
sl@0	1925	diff = after - before;
sl@0	1926	diff *= NanoTickPeriod;
sl@0	1927	avg = (double)diff / (double)aCount;
sl@0	1928	test.Printf(_L("HASH TABLE: %d insertions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1929
sl@0	1930	x=0;
sl@0	1931	before = User::NTickCount();
sl@0	1932	for (i=0; i<aCount; ++i)
sl@0	1933	{
sl@0	1934	x = (x+4339)&0x3fff;
sl@0	1935	const TDesC16* p = set.Find(*base[x]);
sl@0	1936	test(p!=0);
sl@0	1937	}
sl@0	1938	after = User::NTickCount();
sl@0	1939	diff = after - before;
sl@0	1940	diff *= NanoTickPeriod;
sl@0	1941	avg = (double)diff / (double)aCount;
sl@0	1942	test.Printf(_L("HASH TABLE: %d successful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1943
sl@0	1944	before = User::NTickCount();
sl@0	1945	for (i=0; i<aCount; ++i)
sl@0	1946	{
sl@0	1947	x = (x+4339)&0x3fff;
sl@0	1948	const TDesC16* p = set.Find(*base[x]);
sl@0	1949	test(!p);
sl@0	1950	}
sl@0	1951	after = User::NTickCount();
sl@0	1952	diff = after - before;
sl@0	1953	diff *= NanoTickPeriod;
sl@0	1954	avg = (double)diff / (double)aCount;
sl@0	1955	test.Printf(_L("HASH TABLE: %d unsuccessful finds take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1956
sl@0	1957	x=0;
sl@0	1958	before = User::NTickCount();
sl@0	1959	for (i=0; i<aCount; ++i)
sl@0	1960	{
sl@0	1961	x = (x+4339)&0x3fff;
sl@0	1962	TInt r = set.Remove(base[x]);
sl@0	1963	test(r==KErrNone);
sl@0	1964	}
sl@0	1965	after = User::NTickCount();
sl@0	1966	diff = after - before;
sl@0	1967	diff *= NanoTickPeriod;
sl@0	1968	avg = (double)diff / (double)aCount;
sl@0	1969	test.Printf(_L("HASH TABLE: %d deletions take %dus (%.2gus each)\n"), aCount, diff, avg);
sl@0	1970	set.Close();
sl@0	1971	}
sl@0	1972
sl@0	1973	void Benchmark()
sl@0	1974	{
sl@0	1975	test.Next(_L("Benchmarks ..."));
sl@0	1976
sl@0	1977	IntegerBenchmark(1000, EFalse);
sl@0	1978	IntegerBenchmark(1000, ETrue);
sl@0	1979	IntegerBenchmark(2000, EFalse);
sl@0	1980	IntegerBenchmark(2000, ETrue);
sl@0	1981	IntegerBenchmark(4000, EFalse);
sl@0	1982	IntegerBenchmark(4000, ETrue);
sl@0	1983	IntegerBenchmark(8000, EFalse);
sl@0	1984	IntegerBenchmark(8000, ETrue);
sl@0	1985	IntegerBenchmark(16000, EFalse);
sl@0	1986	IntegerBenchmark(16000, ETrue);
sl@0	1987	IntegerBenchmark(32000, EFalse);
sl@0	1988	IntegerBenchmark(32000, ETrue);
sl@0	1989
sl@0	1990	PopulateArray8(16384);
sl@0	1991	StringBenchmark8(1000, EFalse);
sl@0	1992	StringBenchmark8(2000, EFalse);
sl@0	1993	StringBenchmark8(4000, EFalse);
sl@0	1994	StringBenchmark8(8000, EFalse);
sl@0	1995	DesC8Array.ResetAndDestroy();
sl@0	1996
sl@0	1997	PopulateArray16(16384);
sl@0	1998	StringBenchmark16(1000, EFalse);
sl@0	1999	StringBenchmark16(2000, EFalse);
sl@0	2000	StringBenchmark16(4000, EFalse);
sl@0	2001	StringBenchmark16(8000, EFalse);
sl@0	2002	DesC16Array.ResetAndDestroy();
sl@0	2003	}
sl@0	2004
sl@0	2005
sl@0	2006	TUint32 mp(TUint32 x)
sl@0	2007	{
sl@0	2008	TUint32 x3 = x+(x<<1);
sl@0	2009	TUint32 x7 = x+(x3<<1);
sl@0	2010	TUint32 x15 = x+(x7<<1);
sl@0	2011	TUint32 y = x + (x7<<3) + (x3<<7) + (x15<<11) + (x7<<16) + (x3<<20) + (x15<<25) + (x<<31);
sl@0	2012	return y;
sl@0	2013	}
sl@0	2014
sl@0	2015	TUint32 strh(const char* aIn)
sl@0	2016	{
sl@0	2017	TUint32 h = 0;
sl@0	2018	TInt i = 0;
sl@0	2019	while (*aIn)
sl@0	2020	{
sl@0	2021	if (i==0)
sl@0	2022	h = mp(h);
sl@0	2023	TUint32 c = *aIn++;
sl@0	2024	c <<= (8*i);
sl@0	2025	h ^= c;
sl@0	2026	i = (i+1)&3;
sl@0	2027	}
sl@0	2028	return mp(h);
sl@0	2029	}
sl@0	2030
sl@0	2031	TUint32 strh(const wch* aIn)
sl@0	2032	{
sl@0	2033	TUint32 h = 0;
sl@0	2034	TInt i = 0;
sl@0	2035	while (*aIn)
sl@0	2036	{
sl@0	2037	if (i==0)
sl@0	2038	h = mp(h);
sl@0	2039	TUint32 c = *aIn++;
sl@0	2040	switch (i)
sl@0	2041	{
sl@0	2042	case 0: break;
sl@0	2043	case 1: c<<=16; break;
sl@0	2044	case 2: c<<=8; break;
sl@0	2045	default: c=(c<<24)\|(c>>8); break;
sl@0	2046	};
sl@0	2047	h ^= c;
sl@0	2048	i = (i+1)&3;
sl@0	2049	}
sl@0	2050	return mp(h);
sl@0	2051	}
sl@0	2052
sl@0	2053	void TestHash(TInt* aIn, TUint32 aExpected)
sl@0	2054	{
sl@0	2055	THashFunction32<TInt*> hf(&DefaultHash::IntegerPtr);
sl@0	2056	TUint32 out = hf.Hash(aIn);
sl@0	2057	test(aExpected == mp((TUint32)aIn));
sl@0	2058	if (out != aExpected)
sl@0	2059	{
sl@0	2060	test.Printf(_L("Hashing %08x Expected %08x Got %08x\n"), aIn, aExpected, out);
sl@0	2061	test(0);
sl@0	2062	}
sl@0	2063	}
sl@0	2064
sl@0	2065	void TestHash(TDesC8* aIn, TUint32 aExpected)
sl@0	2066	{
sl@0	2067	THashFunction32<TDesC8*> hf(&DefaultHash::Des8Ptr);
sl@0	2068	TUint32 out = hf.Hash(aIn);
sl@0	2069	test(aExpected == mp((TUint32)aIn));
sl@0	2070	if (out != aExpected)
sl@0	2071	{
sl@0	2072	test.Printf(_L("Hashing %08x Expected %08x Got %08x\n"), aIn, aExpected, out);
sl@0	2073	test(0);
sl@0	2074	}
sl@0	2075	}
sl@0	2076
sl@0	2077	void TestHash(TDesC16* aIn, TUint32 aExpected)
sl@0	2078	{
sl@0	2079	THashFunction32<TDesC16*> hf(&DefaultHash::Des16Ptr);
sl@0	2080	TUint32 out = hf.Hash(aIn);
sl@0	2081	test(aExpected == mp((TUint32)aIn));
sl@0	2082	if (out != aExpected)
sl@0	2083	{
sl@0	2084	test.Printf(_L("Hashing %08x Expected %08x Got %08x\n"), aIn, aExpected, out);
sl@0	2085	test(0);
sl@0	2086	}
sl@0	2087	}
sl@0	2088
sl@0	2089
sl@0	2090	void TestHash(TInt aIn, TUint32 aExpected)
sl@0	2091	{
sl@0	2092	THashFunction32<TInt> hf(&DefaultHash::Integer);
sl@0	2093	TUint32 out = hf.Hash(aIn);
sl@0	2094	test(aExpected == mp((TUint32)aIn));
sl@0	2095	if (out != aExpected)
sl@0	2096	{
sl@0	2097	test.Printf(_L("Hashing %08x Expected %08x Got %08x\n"), aIn, aExpected, out);
sl@0	2098	test(0);
sl@0	2099	}
sl@0	2100	}
sl@0	2101
sl@0	2102	void TestHash(const char* aIn, TUint32 aExpected)
sl@0	2103	{
sl@0	2104	THashFunction32<TDesC8> hf(&DefaultHash::Des8);
sl@0	2105	TPtrC8 p((const TUint8*)aIn);
sl@0	2106	TUint32 out = hf.Hash(p);
sl@0	2107	test(aExpected == strh(aIn));
sl@0	2108	if (out != aExpected)
sl@0	2109	{
sl@0	2110	TBuf<256> buf;
sl@0	2111	buf.Copy(p);
sl@0	2112	test.Printf(_L("Hashing %S (len %d) Expected %08x Got %08x\n"), &buf, p.Length(), aExpected, out);
sl@0	2113	test(0);
sl@0	2114	}
sl@0	2115	}
sl@0	2116
sl@0	2117	void TestHash(const wch* aIn)
sl@0	2118	{
sl@0	2119	THashFunction32<TDesC16> hf(&DefaultHash::Des16);
sl@0	2120	TPtrC16 p((const TUint16*)aIn);
sl@0	2121	TUint32 out = hf.Hash(p);
sl@0	2122	TUint32 exp = strh(aIn);
sl@0	2123	if (out != exp)
sl@0	2124	{
sl@0	2125	test.Printf(_L("Hashing %S (len %d) Expected %08x Got %08x\n"), &p, p.Size(), exp, out);
sl@0	2126	test(0);
sl@0	2127	}
sl@0	2128	}
sl@0	2129
sl@0	2130	void TestHash()
sl@0	2131	{
sl@0	2132	test.Next(_L("Test integer hash"));
sl@0	2133	TestHash(1,0x9e3779b9);
sl@0	2134	TestHash(2,0x3c6ef372);
sl@0	2135	TestHash(4,0x78dde6e4);
sl@0	2136	TestHash(8,0xf1bbcdc8);
sl@0	2137	TestHash(16,0xe3779b90);
sl@0	2138	TestHash(0xc90fdaa2,0xbf999112);
sl@0	2139	TestHash(0xb504f334,0x7fb35494);
sl@0	2140	TestHash(0xddb3d743,0xd11a3a6b);
sl@0	2141	TestHash(0xadf85458,0x873a8b98);
sl@0	2142	TestHash(0x11730859,0xb4321951);
sl@0	2143	TestHash(0x64636261,0x8628f119);
sl@0	2144	}
sl@0	2145
sl@0	2146	void TestIntegerPtrHash()
sl@0	2147	{
sl@0	2148	TInt i[5];
sl@0	2149	TInt* ptr;
sl@0	2150	test.Next(_L("Test Integer pointer hash"));
sl@0	2151	for (ptr=i; ptr<i+5; ptr++)
sl@0	2152	{
sl@0	2153	TestHash(ptr, DefaultHash::IntegerPtr(ptr));
sl@0	2154	}
sl@0	2155	}
sl@0	2156
sl@0	2157	void TestDes8PtrHash()
sl@0	2158	{
sl@0	2159	TBuf8<8> i[5];
sl@0	2160	TDesC8* ptr;
sl@0	2161	test.Next(_L("Test Des8 pointer hash"));
sl@0	2162	for (ptr=i; ptr<i+5; ptr++)
sl@0	2163	{
sl@0	2164	TestHash(ptr, DefaultHash::Des8Ptr(ptr));
sl@0	2165	}
sl@0	2166	}
sl@0	2167
sl@0	2168	void TestDes16PtrHash()
sl@0	2169	{
sl@0	2170	TBuf16<8> i[5];
sl@0	2171	TDesC16* ptr;
sl@0	2172	test.Next(_L("Test Des16 pointer hash"));
sl@0	2173	for (ptr=i; ptr<i+5; ptr++)
sl@0	2174	{
sl@0	2175	TestHash(ptr, DefaultHash::Des16Ptr(ptr));
sl@0	2176	}
sl@0	2177	}
sl@0	2178
sl@0	2179	const char teststr[] = "zyxwvutsrq";
sl@0	2180	void TestStringHash()
sl@0	2181	{
sl@0	2182	test.Next(_L("Test 8 bit string hash"));
sl@0	2183	TestHash("",0x0);
sl@0	2184	TestHash("a",0xf3051f19);
sl@0	2185	TestHash("b",0x913c98d2);
sl@0	2186	TestHash("ab",0x2f9df119);
sl@0	2187	TestHash("ba",0x965bb1d2);
sl@0	2188	TestHash("abc",0x4228f119);
sl@0	2189	TestHash("abcd",0x8628f119);
sl@0	2190	TestHash("abcde",0xb75e1e9c);
sl@0	2191	TestHash("abcdef",0x3693149c);
sl@0	2192	TestHash("abcdefg",0xc1c2149c);
sl@0	2193	TestHash("abcdefgh",0xe9c2149c);
sl@0	2194	TestHash("abcdefghi",0x5fcbf20d);
sl@0	2195	TestHash("abcdefghj",0xfe036bc6);
sl@0	2196
sl@0	2197	TestHash(teststr, 0x108ca51e);
sl@0	2198	TestHash(teststr+1, 0x551002ad);
sl@0	2199	TestHash(teststr+2, 0x37dc0d6c);
sl@0	2200	TestHash(teststr+3, 0x2937f92c);
sl@0	2201	TestHash(teststr+4, 0xf0818a94);
sl@0	2202	TestHash(teststr+5, 0xb1b25f1c);
sl@0	2203	TestHash(teststr+6, 0x7a3342d4);
sl@0	2204	TestHash(teststr+7, 0x81c9101b);
sl@0	2205	TestHash(teststr+8, 0xf16edd62);
sl@0	2206	TestHash(teststr+9, 0xd67cbaa9);
sl@0	2207	TestHash(teststr+10, 0);
sl@0	2208
sl@0	2209	char t[16];
sl@0	2210	int i,j;
sl@0	2211	for (i=0; i<=4; ++i)
sl@0	2212	{
sl@0	2213	for (j=0; j<=10; ++j)
sl@0	2214	{
sl@0	2215	const char* s = teststr + j;
sl@0	2216	int l = User::StringLength((const TUint8*)s);
sl@0	2217	memset(t, 0xbb, 16);
sl@0	2218	memcpy(t+i, s, l+1);
sl@0	2219	TUint32 h;
sl@0	2220	switch (j)
sl@0	2221	{
sl@0	2222	case 0: h = 0x108ca51e; break;
sl@0	2223	case 1: h = 0x551002ad; break;
sl@0	2224	case 2: h = 0x37dc0d6c; break;
sl@0	2225	case 3: h = 0x2937f92c; break;
sl@0	2226	case 4: h = 0xf0818a94; break;
sl@0	2227	case 5: h = 0xb1b25f1c; break;
sl@0	2228	case 6: h = 0x7a3342d4; break;
sl@0	2229	case 7: h = 0x81c9101b; break;
sl@0	2230	case 8: h = 0xf16edd62; break;
sl@0	2231	case 9: h = 0xd67cbaa9; break;
sl@0	2232	default: h = 0; break;
sl@0	2233	};
sl@0	2234	TestHash(t+i, h);
sl@0	2235	}
sl@0	2236	}
sl@0	2237	}
sl@0	2238
sl@0	2239	const wch wteststr[] = L"zyxwvutsrq";
sl@0	2240	void TestWStringHash()
sl@0	2241	{
sl@0	2242	test.Next(_L("Test 16 bit string hash"));
sl@0	2243	TestHash(L"");
sl@0	2244	TestHash(L"a");
sl@0	2245	TestHash(L"b");
sl@0	2246	TestHash(L"ab");
sl@0	2247	TestHash(L"ba");
sl@0	2248	TestHash(L"abc");
sl@0	2249	TestHash(L"abcd");
sl@0	2250	TestHash(L"abcde");
sl@0	2251	TestHash(L"abcdef");
sl@0	2252	TestHash(L"abcdefg");
sl@0	2253	TestHash(L"abcdefgh");
sl@0	2254	TestHash(L"abcdefghi");
sl@0	2255	TestHash(L"abcdefghj");
sl@0	2256
sl@0	2257	TestHash(wteststr);
sl@0	2258	TestHash(wteststr+1);
sl@0	2259	TestHash(wteststr+2);
sl@0	2260	TestHash(wteststr+3);
sl@0	2261	TestHash(wteststr+4);
sl@0	2262	TestHash(wteststr+5);
sl@0	2263	TestHash(wteststr+6);
sl@0	2264	TestHash(wteststr+7);
sl@0	2265	TestHash(wteststr+8);
sl@0	2266	TestHash(wteststr+9);
sl@0	2267	TestHash(wteststr+10);
sl@0	2268
sl@0	2269	wch t[16];
sl@0	2270	int i,j;
sl@0	2271	for (i=0; i<=4; ++i)
sl@0	2272	{
sl@0	2273	for (j=0; j<=10; ++j)
sl@0	2274	{
sl@0	2275	const wch* s = wteststr + j;
sl@0	2276	int l = User::StringLength((const TUint16*)s);
sl@0	2277	memset(t, 0xbb, 2*16);
sl@0	2278	memcpy(t+i, s, 2*(l+1));
sl@0	2279	TestHash(t+i);
sl@0	2280	}
sl@0	2281	}
sl@0	2282	}
sl@0	2283	template <class K,class V>
sl@0	2284	void TestHashMapPtr(RHashMap<K,V> &map, K ptr, V* i)
sl@0	2285	{
sl@0	2286	test(map.Reserve(5) == KErrNone);
sl@0	2287	for (ptr=i;ptr<i+5;ptr++)
sl@0	2288	{
sl@0	2289	test(map.Insert(ptr,*ptr) == KErrNone);
sl@0	2290	}
sl@0	2291	for (ptr=i+4;ptr>=i;ptr--)
sl@0	2292	{
sl@0	2293	test((map.Find(ptr)) == ptr);
sl@0	2294	}
sl@0	2295	test(map.Count() == 5);
sl@0	2296	test(map.Remove(i) == KErrNone);
sl@0	2297	test(map.Count()==4);
sl@0	2298	test(map.Find(i)==NULL);
sl@0	2299	map.Close();
sl@0	2300	}
sl@0	2301
sl@0	2302	void TestPtrHashMaps()
sl@0	2303	{
sl@0	2304
sl@0	2305	test.Next(_L("Test RHashMap of default pointer types"));
sl@0	2306	TInt i[5];
sl@0	2307	TInt *ptr=i;
sl@0	2308	RHashMap<TInt*,TInt> mp;
sl@0	2309	TestHashMapPtr(mp, ptr, i);
sl@0	2310
sl@0	2311	TInt32 i1[5];
sl@0	2312	TInt32 *ptr1=i1;
sl@0	2313	RHashMap<TInt32*,TInt32> mp1;
sl@0	2314	TestHashMapPtr(mp1,ptr1,i1);
sl@0	2315
sl@0	2316	TUint i2[5];
sl@0	2317	TUint *ptr2=i2;
sl@0	2318	RHashMap<TUint*,TUint> mp2;
sl@0	2319	TestHashMapPtr(mp2,ptr2,i2);
sl@0	2320
sl@0	2321	TUint32 i3[5];
sl@0	2322	TUint32 *ptr3=i3;
sl@0	2323	RHashMap<TUint32*,TUint32> mp3;
sl@0	2324	TestHashMapPtr(mp3,ptr3,i3);
sl@0	2325
sl@0	2326	TBuf8<5> i4[5];
sl@0	2327	TBuf8<5> *ptr4=i4;
sl@0	2328	RHashMap<TDesC8*,TDesC8> mp4;
sl@0	2329	for (ptr4=i4; ptr4 < i4+5; ptr4++)
sl@0	2330	{
sl@0	2331	test(mp4.Insert(ptr4,*ptr4) == KErrNone);
sl@0	2332	}
sl@0	2333	for (ptr4=i4+4; ptr4 >= i4; ptr4--)
sl@0	2334	{
sl@0	2335	test((mp4.Find(ptr4)) == ptr4);
sl@0	2336	}
sl@0	2337	test(mp4.Count()==5);
sl@0	2338	test(mp4.Remove(i4) == KErrNone);
sl@0	2339	test(mp4.Find(i4) == NULL);
sl@0	2340	test(mp4.Count()==4);
sl@0	2341	mp4.Close();
sl@0	2342
sl@0	2343
sl@0	2344	TBuf16<5> i5[5];
sl@0	2345	TBuf16<5> *ptr5=i5;
sl@0	2346	RHashMap<TDesC16*,TDesC16> mp5;
sl@0	2347	for (ptr5=i5; ptr5 < i5+5; ptr5++)
sl@0	2348	{
sl@0	2349	test(mp5.Insert(ptr5,*ptr5) == KErrNone);
sl@0	2350	}
sl@0	2351	for (ptr5=i5+4; ptr5 >= i5; ptr5--)
sl@0	2352	{
sl@0	2353	test((mp5.Find(ptr5)) == ptr5);
sl@0	2354	}
sl@0	2355	test(mp5.Count()==5);
sl@0	2356	test(mp5.Remove(i5) == KErrNone);
sl@0	2357	test(mp5.Find(i5) == NULL);
sl@0	2358	test(mp5.Count()==4);
sl@0	2359	mp5.Close();
sl@0	2360
sl@0	2361	}
sl@0	2362
sl@0	2363	/** Tests that Reserve() will always allocate memory for new tables
sl@0	2364	even for small reserve sizes
sl@0	2365	See DEF087906.
sl@0	2366	*/
sl@0	2367	void TestSmallReserve()
sl@0	2368	{
sl@0	2369	test.Next(_L("Test RHashTableBase::Reserve preallocates memory, even for small no of elements"));
sl@0	2370	RAllocator* pA = 0;
sl@0	2371	RDummyAllocator da;
sl@0	2372
sl@0	2373	// Reserve should allocate the memory required for the table of 1 element
sl@0	2374	INTSET(set);
sl@0	2375	RHashMap<TInt,TInt> hashMap;
sl@0	2376
sl@0	2377	test(set.Reserve(1) == KErrNone);
sl@0	2378	test(hashMap.Reserve(1) == KErrNone);
sl@0	2379
sl@0	2380	pA = User::SwitchAllocator(&da);
sl@0	2381
sl@0	2382	// No more memory should be allocated for the table as it should
sl@0	2383	// have been already allocated by Reserve()
sl@0	2384	test(set.Insert(123) == KErrNone);
sl@0	2385	test(hashMap.Insert(123,456) == KErrNone);
sl@0	2386
sl@0	2387	// Switch back to allow set to be closed
sl@0	2388	User::SwitchAllocator(pA);
sl@0	2389	set.Close();
sl@0	2390	hashMap.Close();
sl@0	2391	}
sl@0	2392
sl@0	2393
sl@0	2394	TInt E32Main()
sl@0	2395	{
sl@0	2396	test.Title();
sl@0	2397
sl@0	2398	test(HAL::Get(HAL::ENanoTickPeriod, NanoTickPeriod)==KErrNone);
sl@0	2399	test.Printf(_L("NanoTickPeriod %dus\n"), NanoTickPeriod);
sl@0	2400
sl@0	2401	__UHEAP_MARK;
sl@0	2402
sl@0	2403	test.Start(_L("Testing hash tables"));
sl@0	2404
sl@0	2405	TestHash();
sl@0	2406	TestStringHash();
sl@0	2407	TestWStringHash();
sl@0	2408	TestIntegerPtrHash();
sl@0	2409	TestDes8PtrHash();
sl@0	2410	TestDes16PtrHash();
sl@0	2411
sl@0	2412	TestHashSet();
sl@0	2413	TestHashIter();
sl@0	2414	TestHashMap();
sl@0	2415	TestPtrHashMaps();
sl@0	2416
sl@0	2417	PopulateArray8(4096);
sl@0	2418	PopulateArray16(4096);
sl@0	2419	TestPtrHashSet();
sl@0	2420	TestPtrHashMap();
sl@0	2421	DesC16Array.ResetAndDestroy();
sl@0	2422	DesC8Array.ResetAndDestroy();
sl@0	2423
sl@0	2424
sl@0	2425	TestOOM();
sl@0	2426	Benchmark();
sl@0	2427	TestSmallReserve();
sl@0	2428
sl@0	2429	test.End();
sl@0	2430
sl@0	2431	__UHEAP_MARKEND;
sl@0	2432	return 0;
sl@0	2433	}

author	sl@SLION-WIN7.fritz.box
	Fri, 15 Jun 2012 03:10:57 +0200
changeset 0	bde4ae8d615e
permissions	-rw-r--r--