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

sl@0	1	// Copyright (c) 1995-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_tbma.cpp
sl@0	15	//
sl@0	16	//
sl@0	17
sl@0	18	#define __E32TEST_EXTENSION__
sl@0	19	#include "t_tbma.h"
sl@0	20	#include <cpudefs.h>
sl@0	21	#include <e32atomics.h>
sl@0	22
sl@0	23	RTest test(_L("T_TBMA"));
sl@0	24
sl@0	25
sl@0	26	/**************************************
sl@0	27	* class TBmaList
sl@0	28	**************************************/
sl@0	29
sl@0	30	TBmaList* TBmaList::New(TInt aNumBmas)
sl@0	31	{
sl@0	32	TBmaList* pL=new TBmaList;
sl@0	33	if (pL)
sl@0	34	{
sl@0	35	pL->iNumBmas=aNumBmas;
sl@0	36	pL->iBmaList=(TBitMapAllocator*)User::Alloc(aNumBmassizeof(TBitMapAllocator*));
sl@0	37	if (pL->iBmaList)
sl@0	38	Mem::FillZ(pL->iBmaList, aNumBmassizeof(TBitMapAllocator));
sl@0	39	pL->iBaseList=(TInt)User::Alloc((aNumBmas+1)sizeof(TInt));
sl@0	40	if (!pL->iBmaList \|\| !pL->iBaseList)
sl@0	41	{
sl@0	42	delete pL;
sl@0	43	pL=NULL;
sl@0	44	}
sl@0	45	}
sl@0	46	return pL;
sl@0	47	}
sl@0	48
sl@0	49	TBmaList* TBmaList::New(const TBitMapAllocator& aBma, TInt aNumSplits, VA_LIST aList)
sl@0	50	{
sl@0	51	TBmaList* pL=TBmaList::New(aNumSplits+1);
sl@0	52	if (!pL)
sl@0	53	return NULL;
sl@0	54	TInt i;
sl@0	55	pL->iBaseList[0]=0;
sl@0	56	for (i=1; i<=aNumSplits; ++i)
sl@0	57	pL->iBaseList[i]=VA_ARG(aList,TInt);
sl@0	58	pL->iBaseList[aNumSplits+1]=aBma.iSize;
sl@0	59	for (i=0; i<=aNumSplits; ++i)
sl@0	60	{
sl@0	61	TInt sz=pL->iBaseList[i+1]-pL->iBaseList[i];
sl@0	62	__ASSERT_ALWAYS(sz>0, TBMA_FAULT());
sl@0	63	pL->iBmaList[i]=TBitMapAllocator::New(sz,EFalse);
sl@0	64	if (!pL->iBmaList[i])
sl@0	65	{
sl@0	66	delete pL;
sl@0	67	return NULL;
sl@0	68	}
sl@0	69	TInt j;
sl@0	70	for (j=0; j<sz; ++j)
sl@0	71	{
sl@0	72	if (aBma.NotAllocated(j+pL->iBaseList[i],1))
sl@0	73	pL->iBmaList[i]->Free(j);
sl@0	74	}
sl@0	75	}
sl@0	76	return pL;
sl@0	77	}
sl@0	78
sl@0	79	TBmaList::TBmaList()
sl@0	80	{
sl@0	81	iNumBmas=0;
sl@0	82	iBmaList=NULL;
sl@0	83	iBaseList=NULL;
sl@0	84	}
sl@0	85
sl@0	86	TBmaList::~TBmaList()
sl@0	87	{
sl@0	88	TInt i;
sl@0	89	for (i=0; i<iNumBmas; ++i)
sl@0	90	delete iBmaList[i];
sl@0	91	User::Free(iBmaList);
sl@0	92	User::Free(iBaseList);
sl@0	93	}
sl@0	94	/*
sl@0	95	* Extended first fit allocator
sl@0	96	*/
sl@0	97	TInt TBmaList::AllocConsecutiveFF(TInt aLength)
sl@0	98	{
sl@0	99	TInt base=KErrNotFound;
sl@0	100	TInt bmalen=0;
sl@0	101	TInt carry=0;
sl@0	102	TBitMapAllocator** ppA=iBmaList; // pointer to list of TBitMapAllocator*
sl@0	103	TBitMapAllocator** pE=ppA+iNumBmas;
sl@0	104	TInt* pB=iBaseList;
sl@0	105	for (; ppA<pE; ++ppA, ++pB)
sl@0	106	{
sl@0	107	TBitMapAllocator* pA=*ppA;
sl@0	108	if (*pB!=base+bmalen)
sl@0	109	{
sl@0	110	// this BMA is not contiguous with previous one
sl@0	111	carry=0;
sl@0	112	}
sl@0	113	base=*pB;
sl@0	114	bmalen=pA->iSize;
sl@0	115	TInt l;
sl@0	116	TInt r=pA->AllocAligned(aLength,0,0,EFalse,carry,l);
sl@0	117	if (r>=0)
sl@0	118	return base+r-carry;
sl@0	119	}
sl@0	120	return KErrNotFound;
sl@0	121	}
sl@0	122
sl@0	123	/*
sl@0	124	* Extended best fit allocator
sl@0	125	*/
sl@0	126	TInt TBmaList::AllocConsecutiveBF(TInt aLength)
sl@0	127	{
sl@0	128	TInt bmalen=0;
sl@0	129	TInt carry=0;
sl@0	130	TInt minrun=KMaxTInt;
sl@0	131	TInt minrunpos=KErrNotFound;
sl@0	132	TBitMapAllocator** ppA=iBmaList; // pointer to list of TBitMapAllocator*
sl@0	133	TBitMapAllocator** pE=ppA+iNumBmas;
sl@0	134	TInt* pB=iBaseList;
sl@0	135	TInt base=*pB;
sl@0	136	for (; ppA<pE; ++ppA, ++pB)
sl@0	137	{
sl@0	138	TBitMapAllocator* pA=*ppA;
sl@0	139	if (*pB!=base+bmalen)
sl@0	140	{
sl@0	141	// this BMA is not contiguous with previous one
sl@0	142	// check final run of previous BMA
sl@0	143	if (carry<minrun)
sl@0	144	{
sl@0	145	minrun=carry;
sl@0	146	minrunpos=base+bmalen-carry;
sl@0	147	}
sl@0	148	carry=0;
sl@0	149	}
sl@0	150	base=*pB;
sl@0	151	bmalen=pA->iSize;
sl@0	152	TInt l=KMaxTInt;
sl@0	153	TInt oldc=carry;
sl@0	154	TInt r=pA->AllocAligned(aLength,0,0,ETrue,carry,l);
sl@0	155	if (r>=0)
sl@0	156	{
sl@0	157	// check shortest run in this BMA
sl@0	158	if (l<minrun)
sl@0	159	{
sl@0	160	minrun=l;
sl@0	161	minrunpos=r ? (base+r) : (base-oldc);
sl@0	162	if (minrun==aLength)
sl@0	163	break; // exact match so finish
sl@0	164	}
sl@0	165	}
sl@0	166	}
sl@0	167	// check final run of last BMA
sl@0	168	if (ppA==pE && carry>=aLength && carry<minrun)
sl@0	169	minrunpos=base+bmalen-carry;
sl@0	170	return minrunpos;
sl@0	171	}
sl@0	172
sl@0	173	/*
sl@0	174	* Extended first fit aligned allocator
sl@0	175	*/
sl@0	176	TInt TBmaList::AllocAlignedFF(TInt aLength, TInt aAlign)
sl@0	177	{
sl@0	178	TUint32 alignsize=1<<aAlign;
sl@0	179	TUint32 alignmask=alignsize-1;
sl@0	180	TInt base=KErrNotFound;
sl@0	181	TInt bmalen=0;
sl@0	182	TInt carry=0;
sl@0	183	TBitMapAllocator** ppA=iBmaList; // pointer to list of TBitMapAllocator*
sl@0	184	TBitMapAllocator** pE=ppA+iNumBmas;
sl@0	185	TInt* pB=iBaseList;
sl@0	186	for (; ppA<pE; ++ppA, ++pB)
sl@0	187	{
sl@0	188	TBitMapAllocator* pA=*ppA;
sl@0	189	if (*pB!=base+bmalen)
sl@0	190	{
sl@0	191	// this BMA is not contiguous with previous one
sl@0	192	carry=0;
sl@0	193	}
sl@0	194	base=*pB;
sl@0	195	bmalen=pA->iSize;
sl@0	196	TInt l;
sl@0	197	TInt r=pA->AllocAligned(aLength,aAlign,base,EFalse,carry,l);
sl@0	198	if (r>=0)
sl@0	199	return (base+r-carry+alignmask)&~alignmask;
sl@0	200	}
sl@0	201	return KErrNotFound;
sl@0	202	}
sl@0	203
sl@0	204	/*
sl@0	205	* Extended best fit aligned allocator
sl@0	206	*/
sl@0	207	TInt TBmaList::AllocAlignedBF(TInt aLength, TInt aAlign)
sl@0	208	{
sl@0	209	TInt bmalen=0;
sl@0	210	TInt carry=0;
sl@0	211	TInt minrun=KMaxTInt;
sl@0	212	TInt minrunpos=KErrNotFound;
sl@0	213	TUint32 alignsize=1<<aAlign;
sl@0	214	TUint32 alignmask=alignsize-1;
sl@0	215	TBitMapAllocator** ppA=iBmaList; // pointer to list of TBitMapAllocator*
sl@0	216	TBitMapAllocator** pE=ppA+iNumBmas;
sl@0	217	TInt* pB=iBaseList;
sl@0	218	TInt base=*pB;
sl@0	219	for (; ppA<pE; ++ppA, ++pB)
sl@0	220	{
sl@0	221	TBitMapAllocator* pA=*ppA;
sl@0	222	if (*pB!=base+bmalen)
sl@0	223	{
sl@0	224	// this BMA is not contiguous with previous one
sl@0	225	// check final run of previous BMA
sl@0	226	if (carry<minrun)
sl@0	227	{
sl@0	228	TInt fpos=base+bmalen-carry;
sl@0	229	TInt lost=((fpos+base+alignmask)&~alignmask)-base-fpos;
sl@0	230	if (carry-lost>=aLength)
sl@0	231	{
sl@0	232	minrun=carry;
sl@0	233	minrunpos=fpos;
sl@0	234	}
sl@0	235	}
sl@0	236	carry=0;
sl@0	237	}
sl@0	238	base=*pB;
sl@0	239	bmalen=pA->iSize;
sl@0	240	TInt l=KMaxTInt;
sl@0	241	TInt oldc=carry;
sl@0	242	TInt r=pA->AllocAligned(aLength,aAlign,base,ETrue,carry,l);
sl@0	243	if (r>=0)
sl@0	244	{
sl@0	245	// check shortest run in this BMA
sl@0	246	if (l<minrun)
sl@0	247	{
sl@0	248	minrun=l;
sl@0	249	minrunpos=r ? (base+r) : (base-oldc);
sl@0	250	if (minrun==aLength)
sl@0	251	break; // exact match so finish
sl@0	252	}
sl@0	253	}
sl@0	254	}
sl@0	255	// check final run of last BMA
sl@0	256	if (ppA==pE && carry<minrun)
sl@0	257	{
sl@0	258	TInt fpos=base+bmalen-carry;
sl@0	259	TInt lost=((fpos+alignmask)&~alignmask)-fpos;
sl@0	260	if (carry-lost>=aLength)
sl@0	261	{
sl@0	262	minrun=carry;
sl@0	263	minrunpos=fpos;
sl@0	264	}
sl@0	265	}
sl@0	266	return (minrunpos<0) ? minrunpos : ((minrunpos+alignmask)&~alignmask);
sl@0	267	}
sl@0	268
sl@0	269
sl@0	270
sl@0	271
sl@0	272
sl@0	273
sl@0	274
sl@0	275
sl@0	276	void Display(TBitMapAllocator* aBma)
sl@0	277	{
sl@0	278	test.Printf(_L("Free %d FirstCheck %08x Size %d Map %08x\n"),aBma->iAvail,aBma->iCheckFirst,aBma->iSize,aBma->iMap);
sl@0	279	TInt i;
sl@0	280	TInt l=0;
sl@0	281	for (i=0; i<((aBma->iSize+31)>>5); i++)
sl@0	282	{
sl@0	283	if (++l==10)
sl@0	284	{
sl@0	285	l=0;
sl@0	286	// test.Getch();
sl@0	287	}
sl@0	288	TUint32 x=aBma->iMap[i];
sl@0	289	TBuf<80> buf;
sl@0	290	buf.NumFixedWidth(x,EBinary,32);
sl@0	291	buf.Append(_L("\n"));
sl@0	292	test.Printf(buf);
sl@0	293	}
sl@0	294	test.Getch();
sl@0	295	}
sl@0	296
sl@0	297	void Check(TBitMapAllocator& a)
sl@0	298	{
sl@0	299	TInt l=a.iSize;
sl@0	300	l=(l+31)>>5;
sl@0	301	TInt n=0;
sl@0	302	TInt i;
sl@0	303	TUint32* first=NULL;
sl@0	304	for (i=0; i<l; ++i)
sl@0	305	{
sl@0	306	TUint32 w=a.iMap[i];
sl@0	307	if (w && !first)
sl@0	308	first=a.iMap+i;
sl@0	309	n+=__e32_bit_count_32(w);
sl@0	310	}
sl@0	311	test(a.Avail()==n);
sl@0	312	test(first?(a.iCheckFirst<=first):(a.iCheckFirst>=a.iMap && a.iCheckFirst<=a.iMap+l));
sl@0	313	}
sl@0	314
sl@0	315	void TestConstruct(TInt aSize)
sl@0	316	{
sl@0	317	test.Printf(_L("TestConstruct %d\n"),aSize);
sl@0	318	TBitMapAllocator* pA;
sl@0	319	pA=TBitMapAllocator::New(aSize, EFalse);
sl@0	320	test(pA!=NULL);
sl@0	321	test(pA->Avail()==0);
sl@0	322	Check(*pA);
sl@0	323	delete pA;
sl@0	324	pA=TBitMapAllocator::New(aSize, ETrue);
sl@0	325	test(pA!=NULL);
sl@0	326	test(pA->Avail()==aSize);
sl@0	327	Check(*pA);
sl@0	328	delete pA;
sl@0	329	}
sl@0	330
sl@0	331	void TestAlloc1(TInt aSize)
sl@0	332	{
sl@0	333	test.Printf(_L("TestAlloc1 %d\n"),aSize);
sl@0	334	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, ETrue);
sl@0	335	test(pA!=NULL);
sl@0	336	test(pA->Avail()==aSize);
sl@0	337	Check(*pA);
sl@0	338	TInt i;
sl@0	339	for (i=0; i<aSize; ++i)
sl@0	340	{
sl@0	341	TInt r=pA->Alloc();
sl@0	342	test(r==i);
sl@0	343	test(pA->Avail()==aSize-i-1);
sl@0	344	test(pA->iCheckFirst==pA->iMap+i/32);
sl@0	345	Check(*pA);
sl@0	346	}
sl@0	347	test(pA->Alloc()<0);
sl@0	348	delete pA;
sl@0	349	}
sl@0	350
sl@0	351	void TestFree1(TInt aSize)
sl@0	352	{
sl@0	353	test.Printf(_L("TestFree1 %d\n"),aSize);
sl@0	354	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);
sl@0	355	test(pA!=NULL);
sl@0	356	test(pA->Avail()==0);
sl@0	357	TInt i;
sl@0	358	for (i=aSize-1; i>=0; --i)
sl@0	359	{
sl@0	360	pA->Free(i);
sl@0	361	test(pA->Avail()==aSize-i);
sl@0	362	test(pA->Alloc()==i);
sl@0	363	pA->Free(i);
sl@0	364	test(pA->iCheckFirst==pA->iMap+i/32);
sl@0	365	Check(*pA);
sl@0	366	}
sl@0	367	delete pA;
sl@0	368	}
sl@0	369
sl@0	370	void TestBlockAlloc(TInt aSize)
sl@0	371	{
sl@0	372	test.Printf(_L("TestBlockAlloc %d\n"),aSize);
sl@0	373	const TInt begin[]={0,1,2,7,16,29,31,32,33,63,64,65,83,128};
sl@0	374	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, ETrue);
sl@0	375	test(pA!=NULL);
sl@0	376	test(pA->Avail()==aSize);
sl@0	377	pA->Alloc(0,aSize);
sl@0	378	test(pA->Avail()==0);
sl@0	379	Check(*pA);
sl@0	380	pA->Free(0,aSize);
sl@0	381	test(pA->Avail()==aSize);
sl@0	382	Check(*pA);
sl@0	383	TInt i;
sl@0	384	for (i=0; i<(TInt)(sizeof(begin)/sizeof(TInt)); ++i)
sl@0	385	{
sl@0	386	TInt j=begin[i];
sl@0	387	if (j>aSize)
sl@0	388	break;
sl@0	389	TInt l;
sl@0	390	for (l=1; l<=aSize-j; ++l)
sl@0	391	{
sl@0	392	// test.Printf(_L("j=%d, l=%d, s=%d\n"),j,l,aSize);
sl@0	393	pA->Alloc(j,l);
sl@0	394	test(pA->Avail()==aSize-l);
sl@0	395	test(!pA->NotAllocated(j,l));
sl@0	396	if (j+l<aSize)
sl@0	397	test(pA->NotAllocated(j,l+1));
sl@0	398	if (j>0)
sl@0	399	test(pA->NotAllocated(j-1,l));
sl@0	400	TInt r=pA->Alloc();
sl@0	401	if (j==0)
sl@0	402	{
sl@0	403	if (l<aSize)
sl@0	404	test(r==l);
sl@0	405	else
sl@0	406	test(r<0);
sl@0	407	}
sl@0	408	else
sl@0	409	test(r==0);
sl@0	410	if (r==0)
sl@0	411	{
sl@0	412	pA->Free(r);
sl@0	413	pA->Free(j,l);
sl@0	414	}
sl@0	415	else if (r>0)
sl@0	416	pA->Free(j,l+1);
sl@0	417	else
sl@0	418	pA->Free(j,l);
sl@0	419	test(pA->Avail()==aSize);
sl@0	420	Check(*pA);
sl@0	421	}
sl@0	422	}
sl@0	423	delete pA;
sl@0	424	}
sl@0	425
sl@0	426	void TestBlockFree(TInt aSize)
sl@0	427	{
sl@0	428	test.Printf(_L("TestBlockFree %d\n"),aSize);
sl@0	429	const TInt begin[]={0,1,2,7,16,29,31,32,33,63,64,65,83,128};
sl@0	430	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);
sl@0	431	test(pA!=NULL);
sl@0	432	test(pA->Avail()==0);
sl@0	433	TInt i;
sl@0	434	for (i=0; i<(TInt)(sizeof(begin)/sizeof(TInt)); ++i)
sl@0	435	{
sl@0	436	TInt j=begin[i];
sl@0	437	if (j>aSize)
sl@0	438	break;
sl@0	439	TInt l;
sl@0	440	for (l=1; l<=aSize-j; ++l)
sl@0	441	{
sl@0	442	// test.Printf(_L("j=%d, l=%d, s=%d\n"),j,l,aSize);
sl@0	443	pA->Free(j,l);
sl@0	444	test(pA->Avail()==l);
sl@0	445	test(!pA->NotFree(j,l));
sl@0	446	if (j+l<aSize)
sl@0	447	test(pA->NotFree(j,l+1));
sl@0	448	if (j>0)
sl@0	449	test(pA->NotFree(j-1,l));
sl@0	450	TInt r=pA->Alloc();
sl@0	451	test(r==j);
sl@0	452	if (l>1)
sl@0	453	pA->Alloc(j+1,l-1);
sl@0	454	test(pA->Avail()==0);
sl@0	455	Check(*pA);
sl@0	456	}
sl@0	457	}
sl@0	458	delete pA;
sl@0	459	}
sl@0	460
sl@0	461	void TestNotFree(TInt aSize)
sl@0	462	{
sl@0	463	test.Printf(_L("TestNotFree %d\n"),aSize);
sl@0	464	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, ETrue);
sl@0	465	test(pA!=NULL);
sl@0	466	test(pA->Avail()==aSize);
sl@0	467	test(!pA->NotFree(0,aSize));
sl@0	468	TInt i;
sl@0	469	for (i=0; i<aSize; ++i)
sl@0	470	{
sl@0	471	pA->Alloc(i,1);
sl@0	472	test(pA->NotFree(0,aSize));
sl@0	473	TInt j;
sl@0	474	for (j=1; jj<=i \|\| jj+i<=aSize; ++j)
sl@0	475	{
sl@0	476	TInt a=Max(i-j*j,0);
sl@0	477	TInt b=Min(i+j*j,aSize);
sl@0	478	test(pA->NotFree(a,b-a));
sl@0	479	}
sl@0	480	pA->Free(i);
sl@0	481	test(!pA->NotFree(0,aSize));
sl@0	482	}
sl@0	483	const TInt begin[]={0,1,2,7,16,29,31,32,33,63,64,65,83,128};
sl@0	484	const TInt size[]={2,3,7,16,23,31,32,33,63,64,65,89,128};
sl@0	485	const TInt* pB=begin;
sl@0	486	const TInt* pBE=pB+sizeof(begin)/sizeof(TInt);
sl@0	487	const TInt* pS=size;
sl@0	488	const TInt* pSE=pS+sizeof(size)/sizeof(TInt);
sl@0	489	for (; pB<pBE; ++pB)
sl@0	490	{
sl@0	491	TInt b=*pB;
sl@0	492	if (b>=aSize)
sl@0	493	continue;
sl@0	494	for (; pS<pSE; ++pS)
sl@0	495	{
sl@0	496	TInt l=*pS;
sl@0	497	if (b+l>aSize)
sl@0	498	continue;
sl@0	499	pA->Alloc(b,l);
sl@0	500	TInt j;
sl@0	501	for (j=1; j<aSize; ++j)
sl@0	502	{
sl@0	503	if (j<=b)
sl@0	504	test(!pA->NotFree(0,j));
sl@0	505	else
sl@0	506	test(pA->NotFree(0,j));
sl@0	507	if (aSize-j>=b+l)
sl@0	508	test(!pA->NotFree(aSize-j,j));
sl@0	509	else
sl@0	510	test(pA->NotFree(aSize-j,j));
sl@0	511	}
sl@0	512	pA->Free(b,l);
sl@0	513	}
sl@0	514	}
sl@0	515	delete pA;
sl@0	516	}
sl@0	517
sl@0	518	void TestNotAllocated(TInt aSize)
sl@0	519	{
sl@0	520	test.Printf(_L("TestNotAllocated %d\n"),aSize);
sl@0	521	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);
sl@0	522	test(pA!=NULL);
sl@0	523	test(pA->Avail()==0);
sl@0	524	test(!pA->NotAllocated(0,aSize));
sl@0	525	TInt i;
sl@0	526	for (i=0; i<aSize; ++i)
sl@0	527	{
sl@0	528	pA->Free(i);
sl@0	529	test(pA->NotAllocated(0,aSize));
sl@0	530	TInt j;
sl@0	531	for (j=1; jj<=i \|\| jj+i<=aSize; ++j)
sl@0	532	{
sl@0	533	TInt a=Max(i-j*j,0);
sl@0	534	TInt b=Min(i+j*j,aSize);
sl@0	535	test(pA->NotAllocated(a,b-a));
sl@0	536	}
sl@0	537	pA->Alloc(i,1);
sl@0	538	test(!pA->NotAllocated(0,aSize));
sl@0	539	}
sl@0	540	const TInt begin[]={0,1,2,7,16,29,31,32,33,63,64,65,83,128};
sl@0	541	const TInt size[]={2,3,7,16,23,31,32,33,63,64,65,89,128};
sl@0	542	const TInt* pB=begin;
sl@0	543	const TInt* pBE=pB+sizeof(begin)/sizeof(TInt);
sl@0	544	const TInt* pS=size;
sl@0	545	const TInt* pSE=pS+sizeof(size)/sizeof(TInt);
sl@0	546	for (; pB<pBE; ++pB)
sl@0	547	{
sl@0	548	TInt b=*pB;
sl@0	549	if (b>=aSize)
sl@0	550	continue;
sl@0	551	for (; pS<pSE; ++pS)
sl@0	552	{
sl@0	553	TInt l=*pS;
sl@0	554	if (b+l>aSize)
sl@0	555	continue;
sl@0	556	pA->Free(b,l);
sl@0	557	TInt j;
sl@0	558	for (j=1; j<aSize; ++j)
sl@0	559	{
sl@0	560	if (j<=b)
sl@0	561	test(!pA->NotAllocated(0,j));
sl@0	562	else
sl@0	563	test(pA->NotAllocated(0,j));
sl@0	564	if (aSize-j>=b+l)
sl@0	565	test(!pA->NotAllocated(aSize-j,j));
sl@0	566	else
sl@0	567	test(pA->NotAllocated(aSize-j,j));
sl@0	568	}
sl@0	569	pA->Alloc(b,l);
sl@0	570	}
sl@0	571	}
sl@0	572	delete pA;
sl@0	573	}
sl@0	574
sl@0	575	void TestAllocList(TInt aSize)
sl@0	576	{
sl@0	577	test.Printf(_L("TestAllocList %d\n"),aSize);
sl@0	578	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);
sl@0	579	test(pA!=NULL);
sl@0	580	test(pA->Avail()==0);
sl@0	581	TInt i;
sl@0	582	TInt list[256];
sl@0	583	for (i=0; i<aSize; ++i)
sl@0	584	{
sl@0	585	pA->Free(i);
sl@0	586	test(pA->AllocList(128,list)==1);
sl@0	587	test(list[0]==i);
sl@0	588	test(pA->Avail()==0);
sl@0	589	}
sl@0	590	TInt j;
sl@0	591	for (i=0; i<aSize-1; ++i)
sl@0	592	{
sl@0	593	for (j=i+1; j<aSize; ++j)
sl@0	594	{
sl@0	595	pA->Free(i);
sl@0	596	pA->Free(j);
sl@0	597	test(pA->AllocList(1,list)==1);
sl@0	598	test(list[0]==i);
sl@0	599	test(pA->Avail()==1);
sl@0	600	pA->Free(i);
sl@0	601	test(pA->AllocList(128,list)==2);
sl@0	602	test(list[0]==i && list[1]==j);
sl@0	603	test(pA->Avail()==0);
sl@0	604	}
sl@0	605	}
sl@0	606	TInt l;
sl@0	607	for (l=1; l<80; ++l)
sl@0	608	{
sl@0	609	if (2*l+1>aSize)
sl@0	610	break;
sl@0	611	for (i=l+1; i<=aSize-l; ++i)
sl@0	612	{
sl@0	613	pA->Free(0,l);
sl@0	614	pA->Free(i,l);
sl@0	615	test(pA->Avail()==2*l);
sl@0	616	TInt l2;
sl@0	617	for (l2=Max(l-1,1); l2<=2*l; ++l2)
sl@0	618	{
sl@0	619	TInt r=pA->AllocList(l2,list);
sl@0	620	// test.Printf(_L("l2=%d r=%d\n"),l2,r);
sl@0	621	test(r==l2);
sl@0	622	for (j=0; j<Min(l2,l); j++)
sl@0	623	test(list[j]==j);
sl@0	624	for (j=l; j<l2; j++)
sl@0	625	test(list[j]==j-l+i);
sl@0	626	for (j=0; j<l2; ++j)
sl@0	627	pA->Free(list[j]);
sl@0	628	pA->SelectiveFree(0,l);
sl@0	629	pA->SelectiveFree(i,l);
sl@0	630	test(pA->Avail()==2*l);
sl@0	631	}
sl@0	632	pA->Alloc(0,l);
sl@0	633	pA->Alloc(i,l);
sl@0	634	Check(*pA);
sl@0	635	}
sl@0	636	}
sl@0	637	delete pA;
sl@0	638	}
sl@0	639
sl@0	640	void TestSelectiveFree(TInt aSize)
sl@0	641	{
sl@0	642	test.Printf(_L("TestSelectiveFree %d\n"),aSize);
sl@0	643	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, ETrue);
sl@0	644	test(pA!=NULL);
sl@0	645	test(pA->Avail()==aSize);
sl@0	646	TInt i;
sl@0	647	TInt j;
sl@0	648	TInt l;
sl@0	649	for (i=2; i<8; ++i)
sl@0	650	{
sl@0	651	for (l=1; l<=aSize; ++l)
sl@0	652	{
sl@0	653	new (pA) TBitMapAllocator(aSize, ETrue);
sl@0	654	for (j=0; j<aSize; j+=i)
sl@0	655	pA->Alloc(j,1);
sl@0	656	TInt orig=pA->Avail();
sl@0	657	test(orig==aSize-(aSize+i-1)/i);
sl@0	658	pA->SelectiveFree(0,l);
sl@0	659	TInt freed=pA->Avail()-orig;
sl@0	660	test(freed==(l+i-1)/i);
sl@0	661	Check(*pA);
sl@0	662	}
sl@0	663	}
sl@0	664	for (i=0; i<=Min(32,aSize-1); ++i)
sl@0	665	{
sl@0	666	for (l=1; l<=aSize-i; ++l)
sl@0	667	{
sl@0	668	for (j=1; j<=aSize; ++j)
sl@0	669	{
sl@0	670	new (pA) TBitMapAllocator(aSize, ETrue);
sl@0	671	pA->Alloc(i,l);
sl@0	672	test(pA->Avail()==aSize-l);
sl@0	673	pA->SelectiveFree(0,j);
sl@0	674	test(pA->Avail()==aSize-l+Max(0,Min(i+l,j)-i));
sl@0	675	test(!pA->NotFree(0,j));
sl@0	676	if (j>=i && j<i+l)
sl@0	677	test(pA->NotFree(0,j+1));
sl@0	678	Check(*pA);
sl@0	679	}
sl@0	680	}
sl@0	681	}
sl@0	682	delete pA;
sl@0	683	}
sl@0	684
sl@0	685	TBitMapAllocator* DoSetupBMA(TInt aSize, VA_LIST aList)
sl@0	686	{
sl@0	687	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);
sl@0	688	test(pA!=NULL);
sl@0	689	test(pA->Avail()==0);
sl@0	690	TInt totalfree=0;
sl@0	691	FOREVER
sl@0	692	{
sl@0	693	TInt i=VA_ARG(aList,TInt);
sl@0	694	if (i<0)
sl@0	695	break;
sl@0	696	TInt l=VA_ARG(aList,TInt);
sl@0	697	pA->Free(i,l);
sl@0	698	totalfree+=l;
sl@0	699	}
sl@0	700	test(pA->Avail()==totalfree);
sl@0	701	return pA;
sl@0	702	}
sl@0	703
sl@0	704	TBitMapAllocator* SetupBMA(TInt aSize, ...)
sl@0	705	{
sl@0	706	VA_LIST list;
sl@0	707	VA_START(list,aSize);
sl@0	708	return DoSetupBMA(aSize,list);
sl@0	709	}
sl@0	710
sl@0	711	void PopulateRangeArray(RArray<SRange>& aArray, VA_LIST aList)
sl@0	712	{
sl@0	713	aArray.Reset();
sl@0	714	TInt n=0;
sl@0	715	FOREVER
sl@0	716	{
sl@0	717	SRange rng;
sl@0	718	rng.iBase=VA_ARG(aList,TInt);
sl@0	719	if (rng.iBase<0)
sl@0	720	break;
sl@0	721	rng.iLength=VA_ARG(aList,TInt);
sl@0	722	rng.iLength<<=8;
sl@0	723	rng.iLength+=n;
sl@0	724	++n;
sl@0	725	test(aArray.Append(rng)==KErrNone);
sl@0	726	}
sl@0	727	}
sl@0	728
sl@0	729	TInt FirstFitPos(RArray<SRange>& aArray, TInt aLength)
sl@0	730	{
sl@0	731	TInt c=aArray.Count();
sl@0	732	SRange* pR=&aArray[0];
sl@0	733	SRange* pE=pR+c;
sl@0	734	for (; pR<pE; ++pR)
sl@0	735	{
sl@0	736	TInt l=pR->iLength>>8;
sl@0	737	if (l>=aLength)
sl@0	738	{
sl@0	739	// test.Printf(_L("FFP %d = %d\n"),aLength,pR->iBase);
sl@0	740	return pR->iBase;
sl@0	741	}
sl@0	742	}
sl@0	743	// test.Printf(_L("FFP %d = -1\n"),aLength);
sl@0	744	return -1;
sl@0	745	}
sl@0	746
sl@0	747	TInt AlignedFirstFitPos(RArray<SRange>& aArray, TInt aSize, TInt aLength, TInt aAlign, TInt aBase, TInt aOffset=0, TBool aBestFit=EFalse)
sl@0	748	{
sl@0	749	TInt alignSize=1<<aAlign;
sl@0	750	TInt alignMask=alignSize-1;
sl@0	751	TInt minRun=0;
sl@0	752	TInt minRunStart=0;
sl@0	753	TBool runFound = EFalse;
sl@0	754	TInt c=aArray.Count();
sl@0	755	SRange* pR=&aArray[0];
sl@0	756	// Best fit mode should ignore any final run TBitMapAllocator will
sl@0	757	// always ignore the final run in best fit mode and rely on carry being
sl@0	758	// checked by the caller.
sl@0	759	SRange* pE = pR + c - 1;
sl@0	760	if (!aBestFit \|\| aSize > pE->iBase + (pE->iLength >> 8))
sl@0	761	pE++;
sl@0	762
sl@0	763	for (; pR<pE; ++pR)
sl@0	764	{
sl@0	765	TInt l=pR->iLength>>8;
sl@0	766	TInt b=pR->iBase;
sl@0	767	if (aOffset != 0)
sl@0	768	{
sl@0	769	aOffset = ((aOffset + aBase + alignMask) & ~alignMask) - aBase;
sl@0	770	if (aOffset + aLength - 1 >= b + l)
sl@0	771	{// The offset is after the end of this region.
sl@0	772	continue;
sl@0	773	}
sl@0	774	l -= (aOffset <= b)? 0 : aOffset - b;
sl@0	775	b += (aOffset <= b)? 0 : aOffset - b; // Start the search from aOffset
sl@0	776	}
sl@0	777	TInt ab=((b+aBase+alignMask)&~alignMask)-aBase;
sl@0	778	TInt al = l + b - ab;
sl@0	779	if (al >= aLength)
sl@0	780	{
sl@0	781	if (!aBestFit \|\| l == aLength)
sl@0	782	{
sl@0	783	// test.Printf(_L("AFFP %d %d %d = %d\n"),aLength,aAlign,aBase,ab);
sl@0	784	return ab;
sl@0	785	}
sl@0	786	if (!runFound \|\| minRun > l)
sl@0	787	{
sl@0	788	minRun = l;
sl@0	789	minRunStart = ab;
sl@0	790	runFound = ETrue;
sl@0	791	}
sl@0	792	}
sl@0	793	}
sl@0	794	if (runFound)
sl@0	795	{
sl@0	796	return minRunStart;
sl@0	797	}
sl@0	798	// test.Printf(_L("AFFP %d %d %d = -1\n"),aLength,aAlign,aBase);
sl@0	799	return -1;
sl@0	800	}
sl@0	801
sl@0	802	void DoConsecTest(TInt aSize, ...)
sl@0	803	{
sl@0	804	test.Printf(_L("DoConsecTest %d\n"),aSize);
sl@0	805	VA_LIST list;
sl@0	806	VA_LIST list2;
sl@0	807	VA_START(list,aSize);
sl@0	808	VA_START(list2,aSize);
sl@0	809	TBitMapAllocator* pA=DoSetupBMA(aSize,list2);
sl@0	810	RArray<SRange> rangeArray(8,_FOFF(SRange,iLength));
sl@0	811	PopulateRangeArray(rangeArray, list);
sl@0	812	TInt n;
sl@0	813	for (n=1; n<=aSize; ++n)
sl@0	814	{
sl@0	815	TInt r1=pA->AllocConsecutive(n,EFalse);
sl@0	816	TInt r2=FirstFitPos(rangeArray,n);
sl@0	817	// test.Printf(_L("ALC(%d,0) = %d [%d]\n"),n,r1,r2);
sl@0	818	test_Equal(r2, r1);
sl@0	819	}
sl@0	820	rangeArray.SortUnsigned(); // sort array in ascending order of length
sl@0	821	for (n=1; n<=aSize; ++n)
sl@0	822	{
sl@0	823	TInt r1=pA->AllocConsecutive(n,ETrue);
sl@0	824	TInt r2=FirstFitPos(rangeArray,n);
sl@0	825	// test.Printf(_L("ALC(%d,1) = %d [%d]\n"),n,r1,r2);
sl@0	826	test_Equal(r2, r1);
sl@0	827	}
sl@0	828	rangeArray.Close();
sl@0	829	delete pA;
sl@0	830	}
sl@0	831
sl@0	832	void DoAlignedTest(TInt aSize, ...)
sl@0	833	{
sl@0	834	test.Printf(_L("DoAlignedTest %d\n"),aSize);
sl@0	835	VA_LIST list;
sl@0	836	VA_LIST list2;
sl@0	837	VA_START(list,aSize);
sl@0	838	VA_START(list2,aSize);
sl@0	839	TBitMapAllocator* pA=DoSetupBMA(aSize,list2);
sl@0	840	RArray<SRange> rangeArray(8,_FOFF(SRange,iLength));
sl@0	841	PopulateRangeArray(rangeArray, list);
sl@0	842	TInt finalRunLength = 0;
sl@0	843	SRange& lastRun = rangeArray[rangeArray.Count() - 1];
sl@0	844	if (lastRun.iBase + (lastRun.iLength>>8) == aSize)
sl@0	845	{// The last run is at the end of the bma.
sl@0	846	finalRunLength = lastRun.iLength >> 8;
sl@0	847	}
sl@0	848	TInt a;
sl@0	849	TInt b;
sl@0	850	TInt n;
sl@0	851	TUint offset;
sl@0	852	for (a=0; ((1<<a)<=aSize); ++a)
sl@0	853	{
sl@0	854	TInt alignsize=1<<a;
sl@0	855	TInt alignmask=alignsize-1;
sl@0	856	for (b=0; b<(1<<a); ++b)
sl@0	857	{
sl@0	858	// test.Printf(_L("size %d a=%d b=%d First\n"),aSize,a,b);
sl@0	859	for (n=1; n<=aSize; ++n)
sl@0	860	{
sl@0	861	for (offset = 1; offset < (TUint)aSize; offset <<= 1)
sl@0	862	{
sl@0	863	TInt carry = 0;
sl@0	864	TInt runLength;
sl@0	865	TInt r1=pA->AllocAligned(n,a,b,EFalse, carry, runLength, offset);
sl@0	866	TInt r2=AlignedFirstFitPos(rangeArray,aSize, n,a,b, offset);
sl@0	867	if (r2 < 0 && pA->iSize == pA->iAvail)
sl@0	868	{// Totally empty bmas return KErrOverflow on failure.
sl@0	869	r2 = KErrOverflow;
sl@0	870	}
sl@0	871	// test.Printf(_L("ALA %d %d %d %d 0 = %d [%d]\n"),n,a,b,offset,r1,r2);
sl@0	872	test( (r1<0) \|\| ((r1+b)&alignmask)==0 );
sl@0	873	test( (r1<0) \|\| !pA->NotFree(r1,n));
sl@0	874	test( (r1<0) \|\| runLength >= n);
sl@0	875	test_Equal(r2, r1);
sl@0	876	}
sl@0	877	}
sl@0	878	}
sl@0	879	}
sl@0	880	for (a=0; ((1<<a)<=aSize); ++a)
sl@0	881	{
sl@0	882	TInt alignsize=1<<a;
sl@0	883	TInt alignmask=alignsize-1;
sl@0	884	for (b=0; b<(1<<a); ++b)
sl@0	885	{
sl@0	886	// test.Printf(_L("size %d a=%d b=%d Best\n"),aSize,a,b);
sl@0	887	for (n=1; n<=aSize; ++n)
sl@0	888	{// test for with offset=0 as that has screwed best fit in past.
sl@0	889	for (offset = 0; offset < (TUint)aSize; offset <<= 1)
sl@0	890	{
sl@0	891	TInt carry = 0;
sl@0	892	TInt runLength;
sl@0	893	TInt r1=pA->AllocAligned(n,a,b,ETrue, carry, runLength, offset);
sl@0	894	TInt r2=AlignedFirstFitPos(rangeArray,aSize, n,a,b, offset, ETrue);
sl@0	895	if (pA->iSize == pA->iAvail)
sl@0	896	{// Totally empty bmas return KErrOverflow always on best fit mode.
sl@0	897	r2 = KErrOverflow;
sl@0	898	}
sl@0	899	// test.Printf(_L("ALA %d %d %d 1 = %d [%d]\n"),n,a,b,r1,r2);
sl@0	900	test( (r1<0) \|\| ((r1+b)&alignmask)==0 );
sl@0	901	test( (r1<0) \|\| !pA->NotFree(r1,n));
sl@0	902	test( (r1<0) \|\| runLength >= n);
sl@0	903	test_Equal(r2, r1);
sl@0	904	// No carry in so if run found then carry should be zero.
sl@0	905	// If no run found then carry should set to the length of
sl@0	906	// any run at the end of the bma minus the aligned offset.
sl@0	907	TInt lost = 0;
sl@0	908	TInt alignOffset = ((offset + b + alignmask) & ~alignmask) - b;
sl@0	909	if (finalRunLength && offset && lastRun.iBase < alignOffset)
sl@0	910	{// This search had started past the start of the final run
sl@0	911	// so the final run length found will be shorter than its
sl@0	912	// total length.
sl@0	913	if (alignOffset < aSize)
sl@0	914	{
sl@0	915	lost = Min(alignOffset - lastRun.iBase, finalRunLength);
sl@0	916	}
sl@0	917	else // alignedOffset starts past end of bma.
sl@0	918	lost = finalRunLength;
sl@0	919	}
sl@0	920	test((r1>=0 && carry == 0) \|\| carry == finalRunLength - lost);
sl@0	921	offset = (offset)? offset : 1;
sl@0	922	}
sl@0	923	}
sl@0	924	}
sl@0	925	}
sl@0	926	rangeArray.Close();
sl@0	927	delete pA;
sl@0	928	}
sl@0	929
sl@0	930	void Clone(TAny* aDest, const TBitMapAllocator* aSrc)
sl@0	931	{
sl@0	932	TInt nmapw=(aSrc->iSize+31)>>5;
sl@0	933	TInt memsz=sizeof(TBitMapAllocator)+(nmapw-1)*sizeof(TUint32);
sl@0	934	Mem::Move(aDest,aSrc,memsz);
sl@0	935	}
sl@0	936
sl@0	937	void TestAllocConsecutive()
sl@0	938	{
sl@0	939	test.Printf(_L("TestAllocConsecutive\n"));
sl@0	940	DoConsecTest(256, 0,4 , 20,8 , 38,1 , 58,6 , 65,10, 78,16 , 127,72, 222,19 , 244,12 , -1);
sl@0	941	DoConsecTest(255, 0,2 , 3,2 , 6,3 , 10,3 , 14,5 , 20,5 , 26,7 , 34,7 , 42,11 , 54,11 , 66,13 , 80,37,
sl@0	942	118,19 , 138,23 , 162,47 , 254,1 , -1);
sl@0	943	DoConsecTest(1023, 0,2 , 32,32 , 65,31 , 99,30 , 144,64 , 256,519 , 776,1, 778,245 , -1);
sl@0	944
sl@0	945	DoAlignedTest(256, 0,4 , 20,8 , 38,1 , 58,6 , 65,10, 78,16 , 127,72, 222,19 , 244,12 , -1);
sl@0	946	DoAlignedTest(255, 0,2 , 3,2 , 6,3 , 10,3 , 14,5 , 20,5 , 26,7 , 34,7 , 42,11 , 54,11 , 66,13 , 80,37,
sl@0	947	118,19 , 138,23 , 162,47 , 254,1 , -1);
sl@0	948	DoAlignedTest(1023, 0,2 , 32,32 , 65,31 , 99,30 , 144,64 , 256,519 , 776,1, 778,245 , -1);
sl@0	949	// Test some completely free bmas
sl@0	950	DoAlignedTest(255, 0,255, -1);
sl@0	951	DoAlignedTest(256, 0,256, -1);
sl@0	952	DoAlignedTest(1023, 0,1023, -1);
sl@0	953	DoAlignedTest(1024, 0,1024, -1);
sl@0	954	}
sl@0	955
sl@0	956	void DoTestChain(const TBitMapAllocator& aBma, TInt aNumSplits, ...)
sl@0	957	{
sl@0	958	test.Printf(_L("DoTestChain %d %d\n"),aBma.iSize,aNumSplits);
sl@0	959	VA_LIST list;
sl@0	960	VA_START(list,aNumSplits);
sl@0	961
sl@0	962	TBmaList* pL=TBmaList::New(aBma,aNumSplits,list);
sl@0	963	test(pL!=NULL);
sl@0	964
sl@0	965	TInt n;
sl@0	966	for (n=1; n<=aBma.iSize; ++n)
sl@0	967	{
sl@0	968	TInt r1=aBma.AllocConsecutive(n,EFalse);
sl@0	969	TInt r2=pL->AllocConsecutiveFF(n);
sl@0	970	// test.Printf(_L("CHAIN C FF %d: r1=%d r2=%d\n"),n,r1,r2);
sl@0	971	test(r1==r2);
sl@0	972	}
sl@0	973	for (n=1; n<=aBma.iSize; ++n)
sl@0	974	{
sl@0	975	TInt r1=aBma.AllocConsecutive(n,ETrue);
sl@0	976	TInt r2=pL->AllocConsecutiveBF(n);
sl@0	977	// test.Printf(_L("CHAIN C BF %d: r1=%d r2=%d\n"),n,r1,r2);
sl@0	978	test(r1==r2);
sl@0	979	}
sl@0	980
sl@0	981	TInt a;
sl@0	982	for (a=0; ((1<<a)<=aBma.iSize); ++a)
sl@0	983	{
sl@0	984	for (n=1; n<=aBma.iSize; ++n)
sl@0	985	{
sl@0	986	if (n==264 && a==9)
sl@0	987	{
sl@0	988	++n;
sl@0	989	--n;
sl@0	990	}
sl@0	991	TInt r1=aBma.AllocAligned(n,a,0,EFalse);
sl@0	992	TInt r2=pL->AllocAlignedFF(n,a);
sl@0	993	// test.Printf(_L("CHAIN A FF %d,%d: r1=%d r2=%d\n"),n,a,r1,r2);
sl@0	994	test(r1==r2);
sl@0	995	}
sl@0	996	}
sl@0	997	for (a=0; ((1<<a)<=aBma.iSize); ++a)
sl@0	998	{
sl@0	999	for (n=1; n<=aBma.iSize; ++n)
sl@0	1000	{
sl@0	1001	if (n==240 && a==3)
sl@0	1002	{
sl@0	1003	++n;
sl@0	1004	--n;
sl@0	1005	}
sl@0	1006	TInt r1=aBma.AllocAligned(n,a,0,ETrue);
sl@0	1007	TInt r2=pL->AllocAlignedBF(n,a);
sl@0	1008	// test.Printf(_L("CHAIN A BF %d,%d: r1=%d r2=%d\n"),n,a,r1,r2);
sl@0	1009	test(r1==r2);
sl@0	1010	}
sl@0	1011	}
sl@0	1012
sl@0	1013	delete pL;
sl@0	1014	}
sl@0	1015
sl@0	1016	void TestChain()
sl@0	1017	{
sl@0	1018	test.Printf(_L("TestChain\n"));
sl@0	1019	TBitMapAllocator* pA;
sl@0	1020	pA=SetupBMA(1023, 0,2 , 32,32 , 65,31 , 99,30 , 144,64 , 256,519 , 776,1, 778,245 , -1);
sl@0	1021	test(pA!=NULL);
sl@0	1022	DoTestChain(*pA, 2, 300, 700);
sl@0	1023	DoTestChain(*pA, 3, 64, 301, 702);
sl@0	1024	delete pA;
sl@0	1025	pA=SetupBMA(512, 0,2 , 20,10 , 32,32 , 65,31 , 144,64 , 399,113 , -1);
sl@0	1026	test(pA!=NULL);
sl@0	1027	DoTestChain(*pA, 2, 256, 384);
sl@0	1028	DoTestChain(*pA, 3, 128, 256, 384);
sl@0	1029	DoTestChain(*pA, 3, 80, 208, 384);
sl@0	1030	DoTestChain(*pA, 3, 80, 208, 400);
sl@0	1031	delete pA;
sl@0	1032	}
sl@0	1033
sl@0	1034	void TestBitOps()
sl@0	1035	{
sl@0	1036	test.Next(_L("Bit operations (32 bit)"));
sl@0	1037	test(__e32_find_ls1_32(0x00000000)==-1);
sl@0	1038	TInt i, j, k;
sl@0	1039	TInt count = 0;
sl@0	1040	for (i=0; i<=31; ++i)
sl@0	1041	test(__e32_find_ls1_32(1u<<i)==i);
sl@0	1042	TUint x = 0;
sl@0	1043	for (i=0; i<1000; ++i)
sl@0	1044	{
sl@0	1045	x = 69069*x + 41;
sl@0	1046	TInt bit = x&31;
sl@0	1047
sl@0	1048	x = 69069*x + 41;
sl@0	1049	TUint y = ((x\|1)<<bit);
sl@0	1050
sl@0	1051	test(__e32_find_ls1_32(y) == bit);
sl@0	1052	}
sl@0	1053
sl@0	1054	test(__e32_find_ms1_32(0x00000000)==-1);
sl@0	1055	for (i=0; i<=31; ++i)
sl@0	1056	test(__e32_find_ms1_32(1u<<i)==i);
sl@0	1057	for (i=0; i<1000; ++i)
sl@0	1058	{
sl@0	1059	x = 69069*x + 41;
sl@0	1060	TInt bit = x&31;
sl@0	1061
sl@0	1062	x = 69069*x + 41;
sl@0	1063	TUint y = ((x\|0x80000000u)>>bit);
sl@0	1064
sl@0	1065	test(__e32_find_ms1_32(y) == 31-bit);
sl@0	1066	}
sl@0	1067
sl@0	1068	test(__e32_bit_count_32(0)==0);
sl@0	1069	test(__e32_bit_count_32(0xffffffff)==32);
sl@0	1070	for (i=0; i<32; ++i)
sl@0	1071	{
sl@0	1072	TUint32 y = 0xffffffffu << i;
sl@0	1073	TUint32 z = 0xffffffffu >> i;
sl@0	1074	test(__e32_bit_count_32(y) == 32-i);
sl@0	1075	test(__e32_bit_count_32(z) == 32-i);
sl@0	1076	test(__e32_bit_count_32(~y) == i);
sl@0	1077	test(__e32_bit_count_32(~z) == i);
sl@0	1078	}
sl@0	1079	for (i=0; i<32; ++i)
sl@0	1080	for (j=0; j<32; ++j)
sl@0	1081	for (k=0; k<32; ++k)
sl@0	1082	{
sl@0	1083	TUint32 b0 = 1u<<i;
sl@0	1084	TUint32 b1 = 1u<<j;
sl@0	1085	TUint32 b2 = 1u<<k;
sl@0	1086	TUint32 y = b0 \| b1 \| b2;
sl@0	1087	TInt n;
sl@0	1088	if (i==j && j==k) n=1;
sl@0	1089	else if (i==j \|\| j==k \|\| i==k) n=2;
sl@0	1090	else n=3;
sl@0	1091	test(__e32_bit_count_32(y) == n);
sl@0	1092	test(__e32_bit_count_32(~y) == 32-n);
sl@0	1093	++count;
sl@0	1094	}
sl@0	1095	test.Printf(_L("%d iterations done\n"), count);
sl@0	1096	for (i=0; i<=31; ++i)
sl@0	1097	{
sl@0	1098	test(__e32_bit_count_32(0xaaaaaaaau<<i)==16-(i+1)/2);
sl@0	1099	test(__e32_bit_count_32(0x55555555u<<i)==16-i/2);
sl@0	1100	}
sl@0	1101	test(__e32_bit_count_32(0x33333333u)==16);
sl@0	1102	test(__e32_bit_count_32(0x88888888u)==8);
sl@0	1103
sl@0	1104	test.Next(_L("Bit operations (64 bit)"));
sl@0	1105	test(__e32_find_ls1_64(0x00000000)==-1);
sl@0	1106	for (i=0; i<=63; ++i)
sl@0	1107	{
sl@0	1108	TUint64 x = 1u;
sl@0	1109	x<<=i;
sl@0	1110	test(__e32_find_ls1_64(x)==i);
sl@0	1111	}
sl@0	1112	x = 487;
sl@0	1113	for (i=0; i<1000; ++i)
sl@0	1114	{
sl@0	1115	x = 69069*x + 41;
sl@0	1116	TInt bit = x&63;
sl@0	1117
sl@0	1118	x = 69069*x + 41;
sl@0	1119	TUint32 xl = x\|1;
sl@0	1120	x = 69069*x + 41;
sl@0	1121	TUint32 xh = x;
sl@0	1122	TUint64 y = MAKE_TUINT64(xh,xl);
sl@0	1123	y <<= bit;
sl@0	1124	test(__e32_find_ls1_64(y) == bit);
sl@0	1125	}
sl@0	1126
sl@0	1127	test(__e32_find_ms1_64(0x00000000)==-1);
sl@0	1128	for (i=0; i<=63; ++i)
sl@0	1129	{
sl@0	1130	TUint64 x = 1u;
sl@0	1131	x<<=i;
sl@0	1132	test(__e32_find_ms1_64(x)==i);
sl@0	1133	}
sl@0	1134	x = 1039;
sl@0	1135	for (i=0; i<1000; ++i)
sl@0	1136	{
sl@0	1137	x = 69069*x + 41;
sl@0	1138	TInt bit = x&63;
sl@0	1139
sl@0	1140	x = 69069*x + 41;
sl@0	1141	TUint32 xl = x;
sl@0	1142	x = 69069*x + 41;
sl@0	1143	TUint32 xh = x\|0x80000000u;
sl@0	1144	TUint64 y = MAKE_TUINT64(xh,xl);
sl@0	1145	y >>= bit;
sl@0	1146	test(__e32_find_ms1_64(y) == 63-bit);
sl@0	1147	}
sl@0	1148
sl@0	1149	test(__e32_bit_count_64(0)==0);
sl@0	1150	test(__e32_bit_count_64(MAKE_TUINT64(0x00000000,0xffffffff))==32);
sl@0	1151	test(__e32_bit_count_64(MAKE_TUINT64(0xffffffff,0x00000000))==32);
sl@0	1152	test(__e32_bit_count_64(MAKE_TUINT64(0xffffffff,0xffffffff))==64);
sl@0	1153	for (i=0; i<64; ++i)
sl@0	1154	{
sl@0	1155	TUint64 y = MAKE_TUINT64(0xffffffff,0xffffffff);
sl@0	1156	TUint64 z = y >> i;
sl@0	1157	y <<= i;
sl@0	1158	test(__e32_bit_count_64(y) == 64-i);
sl@0	1159	test(__e32_bit_count_64(z) == 64-i);
sl@0	1160	test(__e32_bit_count_64(~y) == i);
sl@0	1161	test(__e32_bit_count_64(~z) == i);
sl@0	1162	}
sl@0	1163	count = 0;
sl@0	1164	for (i=0; i<64; ++i)
sl@0	1165	for (j=0; j<64; ++j)
sl@0	1166	for (k=0; k<64; ++k)
sl@0	1167	{
sl@0	1168	TUint64 b0 = 1u;
sl@0	1169	TUint64 b1 = 1u;
sl@0	1170	TUint64 b2 = 1u;
sl@0	1171	b0 <<= i;
sl@0	1172	b1 <<= j;
sl@0	1173	b2 <<= k;
sl@0	1174	TUint64 y = b0 \| b1 \| b2;
sl@0	1175	TUint64 z = ~y;
sl@0	1176	TInt n;
sl@0	1177	if (i==j && j==k) n=1;
sl@0	1178	else if (i==j \|\| j==k \|\| i==k) n=2;
sl@0	1179	else n=3;
sl@0	1180	test(__e32_bit_count_64(y) == n);
sl@0	1181	test(__e32_bit_count_64(z) == 64-n);
sl@0	1182	++count;
sl@0	1183	}
sl@0	1184	test.Printf(_L("%d iterations done\n"), count);
sl@0	1185	for (i=0; i<64; ++i)
sl@0	1186	{
sl@0	1187	TUint64 y = MAKE_TUINT64(0xaaaaaaaa,0xaaaaaaaa);
sl@0	1188	TUint64 z = ~y;
sl@0	1189	test(__e32_bit_count_64(y<<i)==32-(i+1)/2);
sl@0	1190	test(__e32_bit_count_64(z<<i)==32-i/2);
sl@0	1191	}
sl@0	1192	test(__e32_bit_count_64(MAKE_TUINT64(0x33333333u,0x33333333u))==32);
sl@0	1193	test(__e32_bit_count_64(MAKE_TUINT64(0x88888888u,0x88888888u))==16);
sl@0	1194	}
sl@0	1195
sl@0	1196	GLDEF_C TInt E32Main()
sl@0	1197	{
sl@0	1198	test.Title();
sl@0	1199	__UHEAP_MARK;
sl@0	1200	test.Start(_L("TBitMapAllocator tests"));
sl@0	1201
sl@0	1202	TestBitOps();
sl@0	1203
sl@0	1204	TestConstruct(3);
sl@0	1205	TestConstruct(29);
sl@0	1206	TestConstruct(256);
sl@0	1207	TestConstruct(487);
sl@0	1208
sl@0	1209	TestAlloc1(3);
sl@0	1210	TestAlloc1(29);
sl@0	1211	TestAlloc1(256);
sl@0	1212	TestAlloc1(181);
sl@0	1213
sl@0	1214	TestFree1(3);
sl@0	1215	TestFree1(29);
sl@0	1216	TestFree1(256);
sl@0	1217	TestFree1(181);
sl@0	1218
sl@0	1219	TestBlockAlloc(3);
sl@0	1220	TestBlockAlloc(29);
sl@0	1221	TestBlockAlloc(256);
sl@0	1222	TestBlockAlloc(179);
sl@0	1223
sl@0	1224	TestBlockFree(3);
sl@0	1225	TestBlockFree(31);
sl@0	1226	TestBlockFree(256);
sl@0	1227	TestBlockFree(149);
sl@0	1228
sl@0	1229	TestNotFree(3);
sl@0	1230	TestNotFree(31);
sl@0	1231	TestNotFree(256);
sl@0	1232	TestNotFree(149);
sl@0	1233
sl@0	1234	TestNotAllocated(3);
sl@0	1235	TestNotAllocated(31);
sl@0	1236	TestNotAllocated(256);
sl@0	1237	TestNotAllocated(149);
sl@0	1238
sl@0	1239	TestAllocList(3);
sl@0	1240	TestAllocList(31);
sl@0	1241	TestAllocList(128);
sl@0	1242	TestAllocList(149);
sl@0	1243
sl@0	1244	TestSelectiveFree(3);
sl@0	1245	TestSelectiveFree(31);
sl@0	1246	TestSelectiveFree(128);
sl@0	1247	TestSelectiveFree(149);
sl@0	1248
sl@0	1249	TestAllocConsecutive();
sl@0	1250
sl@0	1251	TestChain();
sl@0	1252
sl@0	1253	__UHEAP_MARKEND;
sl@0	1254	test.End();
sl@0	1255	return 0;
sl@0	1256	}

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