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

     2 // All rights reserved.

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

     4 // under the terms of the License "Eclipse Public License v1.0"

     5 // which accompanies this distribution, and is available

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

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 // e32test\buffer\t_tbma.cpp

    15 // 

    16 //

    17 

    18 #define __E32TEST_EXTENSION__

    19 #include "t_tbma.h"

    20 #include <cpudefs.h>

    21 #include <e32atomics.h>

    22 

    23 RTest test(_L("T_TBMA"));

    24 

    25 

    26 /**************************************

    27  * class TBmaList

    28  **************************************/

    29 

    30 TBmaList* TBmaList::New(TInt aNumBmas)

    31 	{

    32 	TBmaList* pL=new TBmaList;

    33 	if (pL)

    34 		{

    35 		pL->iNumBmas=aNumBmas;

    36 		pL->iBmaList=(TBitMapAllocator**)User::Alloc(aNumBmas*sizeof(TBitMapAllocator*));

    37 		if (pL->iBmaList)

    38 			Mem::FillZ(pL->iBmaList, aNumBmas*sizeof(TBitMapAllocator*));

    39 		pL->iBaseList=(TInt*)User::Alloc((aNumBmas+1)*sizeof(TInt));

    40 		if (!pL->iBmaList || !pL->iBaseList)

    41 			{

    42 			delete pL;

    43 			pL=NULL;

    44 			}

    45 		}

    46 	return pL;

    47 	}

    48 

    49 TBmaList* TBmaList::New(const TBitMapAllocator& aBma, TInt aNumSplits, VA_LIST aList)

    50 	{

    51 	TBmaList* pL=TBmaList::New(aNumSplits+1);

    52 	if (!pL)

    53 		return NULL;

    54 	TInt i;

    55 	pL->iBaseList[0]=0;

    56 	for (i=1; i<=aNumSplits; ++i)

    57 		pL->iBaseList[i]=VA_ARG(aList,TInt);

    58 	pL->iBaseList[aNumSplits+1]=aBma.iSize;

    59 	for (i=0; i<=aNumSplits; ++i)

    60 		{

    61 		TInt sz=pL->iBaseList[i+1]-pL->iBaseList[i];

    62 		__ASSERT_ALWAYS(sz>0, TBMA_FAULT());

    63 		pL->iBmaList[i]=TBitMapAllocator::New(sz,EFalse);

    64 		if (!pL->iBmaList[i])

    65 			{

    66 			delete pL;

    67 			return NULL;

    68 			}

    69 		TInt j;

    70 		for (j=0; j<sz; ++j)

    71 			{

    72 			if (aBma.NotAllocated(j+pL->iBaseList[i],1))

    73 				pL->iBmaList[i]->Free(j);

    74 			}

    75 		}

    76 	return pL;

    77 	}

    78 

    79 TBmaList::TBmaList()

    80 	{

    81 	iNumBmas=0;

    82 	iBmaList=NULL;

    83 	iBaseList=NULL;

    84 	}

    85 

    86 TBmaList::~TBmaList()

    87 	{

    88 	TInt i;

    89 	for (i=0; i<iNumBmas; ++i)

    90 		delete iBmaList[i];

    91 	User::Free(iBmaList);

    92 	User::Free(iBaseList);

    93 	}

    94 /*

    95  * Extended first fit allocator

    96  */

    97 TInt TBmaList::AllocConsecutiveFF(TInt aLength)

    98 	{

    99 	TInt base=KErrNotFound;

   100 	TInt bmalen=0;

   101 	TInt carry=0;

   102 	TBitMapAllocator** ppA=iBmaList;		// pointer to list of TBitMapAllocator*

   103 	TBitMapAllocator** pE=ppA+iNumBmas;

   104 	TInt* pB=iBaseList;

   105 	for (; ppA<pE; ++ppA, ++pB)

   106 		{

   107 		TBitMapAllocator* pA=*ppA;

   108 		if (*pB!=base+bmalen)

   109 			{

   110 			// this BMA is not contiguous with previous one

   111 			carry=0;

   112 			}

   113 		base=*pB;

   114 		bmalen=pA->iSize;

   115 		TInt l;

   116 		TInt r=pA->AllocAligned(aLength,0,0,EFalse,carry,l);

   117 		if (r>=0)

   118 			return base+r-carry;

   119 		}

   120 	return KErrNotFound;

   121 	}

   122 

   123 /*

   124  * Extended best fit allocator

   125  */

   126 TInt TBmaList::AllocConsecutiveBF(TInt aLength)

   127 	{

   128 	TInt bmalen=0;

   129 	TInt carry=0;

   130 	TInt minrun=KMaxTInt;

   131 	TInt minrunpos=KErrNotFound;

   132 	TBitMapAllocator** ppA=iBmaList;		// pointer to list of TBitMapAllocator*

   133 	TBitMapAllocator** pE=ppA+iNumBmas;

   134 	TInt* pB=iBaseList;

   135 	TInt base=*pB;

   136 	for (; ppA<pE; ++ppA, ++pB)

   137 		{

   138 		TBitMapAllocator* pA=*ppA;

   139 		if (*pB!=base+bmalen)

   140 			{

   141 			// this BMA is not contiguous with previous one

   142 			// check final run of previous BMA

   143 			if (carry<minrun)

   144 				{

   145 				minrun=carry;

   146 				minrunpos=base+bmalen-carry;

   147 				}

   148 			carry=0;

   149 			}

   150 		base=*pB;

   151 		bmalen=pA->iSize;

   152 		TInt l=KMaxTInt;

   153 		TInt oldc=carry;

   154 		TInt r=pA->AllocAligned(aLength,0,0,ETrue,carry,l);

   155 		if (r>=0)

   156 			{

   157 			// check shortest run in this BMA

   158 			if (l<minrun)

   159 				{

   160 				minrun=l;

   161 				minrunpos=r ? (base+r) : (base-oldc);

   162 				if (minrun==aLength)

   163 					break;				// exact match so finish

   164 				}

   165 			}

   166 		}

   167 	// check final run of last BMA

   168 	if (ppA==pE && carry>=aLength && carry<minrun)

   169 		minrunpos=base+bmalen-carry;

   170 	return minrunpos;

   171 	}

   172 

   173 /*

   174  * Extended first fit aligned allocator

   175  */

   176 TInt TBmaList::AllocAlignedFF(TInt aLength, TInt aAlign)

   177 	{

   178 	TUint32 alignsize=1<<aAlign;

   179 	TUint32 alignmask=alignsize-1;

   180 	TInt base=KErrNotFound;

   181 	TInt bmalen=0;

   182 	TInt carry=0;

   183 	TBitMapAllocator** ppA=iBmaList;		// pointer to list of TBitMapAllocator*

   184 	TBitMapAllocator** pE=ppA+iNumBmas;

   185 	TInt* pB=iBaseList;

   186 	for (; ppA<pE; ++ppA, ++pB)

   187 		{

   188 		TBitMapAllocator* pA=*ppA;

   189 		if (*pB!=base+bmalen)

   190 			{

   191 			// this BMA is not contiguous with previous one

   192 			carry=0;

   193 			}

   194 		base=*pB;

   195 		bmalen=pA->iSize;

   196 		TInt l;

   197 		TInt r=pA->AllocAligned(aLength,aAlign,base,EFalse,carry,l);

   198 		if (r>=0)

   199 			return (base+r-carry+alignmask)&~alignmask;

   200 		}

   201 	return KErrNotFound;

   202 	}

   203 

   204 /*

   205  * Extended best fit aligned allocator

   206  */

   207 TInt TBmaList::AllocAlignedBF(TInt aLength, TInt aAlign)

   208 	{

   209 	TInt bmalen=0;

   210 	TInt carry=0;

   211 	TInt minrun=KMaxTInt;

   212 	TInt minrunpos=KErrNotFound;

   213 	TUint32 alignsize=1<<aAlign;

   214 	TUint32 alignmask=alignsize-1;

   215 	TBitMapAllocator** ppA=iBmaList;		// pointer to list of TBitMapAllocator*

   216 	TBitMapAllocator** pE=ppA+iNumBmas;

   217 	TInt* pB=iBaseList;

   218 	TInt base=*pB;

   219 	for (; ppA<pE; ++ppA, ++pB)

   220 		{

   221 		TBitMapAllocator* pA=*ppA;

   222 		if (*pB!=base+bmalen)

   223 			{

   224 			// this BMA is not contiguous with previous one

   225 			// check final run of previous BMA

   226 			if (carry<minrun)

   227 				{

   228 				TInt fpos=base+bmalen-carry;

   229 				TInt lost=((fpos+base+alignmask)&~alignmask)-base-fpos;

   230 				if (carry-lost>=aLength)

   231 					{

   232 					minrun=carry;

   233 					minrunpos=fpos;

   234 					}

   235 				}

   236 			carry=0;

   237 			}

   238 		base=*pB;

   239 		bmalen=pA->iSize;

   240 		TInt l=KMaxTInt;

   241 		TInt oldc=carry;

   242 		TInt r=pA->AllocAligned(aLength,aAlign,base,ETrue,carry,l);

   243 		if (r>=0)

   244 			{

   245 			// check shortest run in this BMA

   246 			if (l<minrun)

   247 				{

   248 				minrun=l;

   249 				minrunpos=r ? (base+r) : (base-oldc);

   250 				if (minrun==aLength)

   251 					break;				// exact match so finish

   252 				}

   253 			}

   254 		}

   255 	// check final run of last BMA

   256 	if (ppA==pE && carry<minrun)

   257 		{

   258 		TInt fpos=base+bmalen-carry;

   259 		TInt lost=((fpos+alignmask)&~alignmask)-fpos;

   260 		if (carry-lost>=aLength)

   261 			{

   262 			minrun=carry;

   263 			minrunpos=fpos;

   264 			}

   265 		}

   266 	return (minrunpos<0) ? minrunpos : ((minrunpos+alignmask)&~alignmask);

   267 	}

   268 

   269 

   270 

   271 

   272 

   273 

   274 

   275 

   276 void Display(TBitMapAllocator* aBma)

   277 	{

   278 	test.Printf(_L("Free %d FirstCheck %08x Size %d Map %08x\n"),aBma->iAvail,aBma->iCheckFirst,aBma->iSize,aBma->iMap);

   279 	TInt i;

   280 	TInt l=0;

   281 	for (i=0; i<((aBma->iSize+31)>>5); i++)

   282 		{

   283 		if (++l==10)

   284 			{

   285 			l=0;

   286 //			test.Getch();

   287 			}

   288 		TUint32 x=aBma->iMap[i];

   289 		TBuf<80> buf;

   290 		buf.NumFixedWidth(x,EBinary,32);

   291 		buf.Append(_L("\n"));

   292 		test.Printf(buf);

   293 		}

   294 	test.Getch();

   295 	}

   296 

   297 void Check(TBitMapAllocator& a)

   298 	{

   299 	TInt l=a.iSize;

   300 	l=(l+31)>>5;

   301 	TInt n=0;

   302 	TInt i;

   303 	TUint32* first=NULL;

   304 	for (i=0; i<l; ++i)

   305 		{

   306 		TUint32 w=a.iMap[i];

   307 		if (w && !first)

   308 			first=a.iMap+i;

   309 		n+=__e32_bit_count_32(w);

   310 		}

   311 	test(a.Avail()==n);

   312 	test(first?(a.iCheckFirst<=first):(a.iCheckFirst>=a.iMap && a.iCheckFirst<=a.iMap+l));

   313 	}

   314 

   315 void TestConstruct(TInt aSize)

   316 	{

   317 	test.Printf(_L("TestConstruct %d\n"),aSize);

   318 	TBitMapAllocator* pA;

   319 	pA=TBitMapAllocator::New(aSize, EFalse);

   320 	test(pA!=NULL);

   321 	test(pA->Avail()==0);

   322 	Check(*pA);

   323 	delete pA;

   324 	pA=TBitMapAllocator::New(aSize, ETrue);

   325 	test(pA!=NULL);

   326 	test(pA->Avail()==aSize);

   327 	Check(*pA);

   328 	delete pA;

   329 	}

   330 

   331 void TestAlloc1(TInt aSize)

   332 	{

   333 	test.Printf(_L("TestAlloc1 %d\n"),aSize);

   334 	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, ETrue);

   335 	test(pA!=NULL);

   336 	test(pA->Avail()==aSize);

   337 	Check(*pA);

   338 	TInt i;

   339 	for (i=0; i<aSize; ++i)

   340 		{

   341 		TInt r=pA->Alloc();

   342 		test(r==i);

   343 		test(pA->Avail()==aSize-i-1);

   344 		test(pA->iCheckFirst==pA->iMap+i/32);

   345 		Check(*pA);

   346 		}

   347 	test(pA->Alloc()<0);

   348 	delete pA;

   349 	}

   350 

   351 void TestFree1(TInt aSize)

   352 	{

   353 	test.Printf(_L("TestFree1 %d\n"),aSize);

   354 	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);

   355 	test(pA!=NULL);

   356 	test(pA->Avail()==0);

   357 	TInt i;

   358 	for (i=aSize-1; i>=0; --i)

   359 		{

   360 		pA->Free(i);

   361 		test(pA->Avail()==aSize-i);

   362 		test(pA->Alloc()==i);

   363 		pA->Free(i);

   364 		test(pA->iCheckFirst==pA->iMap+i/32);

   365 		Check(*pA);

   366 		}

   367 	delete pA;

   368 	}

   369 

   370 void TestBlockAlloc(TInt aSize)

   371 	{

   372 	test.Printf(_L("TestBlockAlloc %d\n"),aSize);

   373 	const TInt begin[]={0,1,2,7,16,29,31,32,33,63,64,65,83,128};

   374 	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, ETrue);

   375 	test(pA!=NULL);

   376 	test(pA->Avail()==aSize);

   377 	pA->Alloc(0,aSize);

   378 	test(pA->Avail()==0);

   379 	Check(*pA);

   380 	pA->Free(0,aSize);

   381 	test(pA->Avail()==aSize);

   382 	Check(*pA);

   383 	TInt i;

   384 	for (i=0; i<(TInt)(sizeof(begin)/sizeof(TInt)); ++i)

   385 		{

   386 		TInt j=begin[i];

   387 		if (j>aSize)

   388 			break;

   389 		TInt l;

   390 		for (l=1; l<=aSize-j; ++l)

   391 			{

   392 //			test.Printf(_L("j=%d, l=%d, s=%d\n"),j,l,aSize);

   393 			pA->Alloc(j,l);

   394 			test(pA->Avail()==aSize-l);

   395 			test(!pA->NotAllocated(j,l));

   396 			if (j+l<aSize)

   397 				test(pA->NotAllocated(j,l+1));

   398 			if (j>0)

   399 				test(pA->NotAllocated(j-1,l));

   400 			TInt r=pA->Alloc();

   401 			if (j==0)

   402 				{

   403 				if (l<aSize)

   404 					test(r==l);

   405 				else

   406 					test(r<0);

   407 				}

   408 			else

   409 				test(r==0);

   410 			if (r==0)

   411 				{

   412 				pA->Free(r);

   413 				pA->Free(j,l);

   414 				}

   415 			else if (r>0)

   416 				pA->Free(j,l+1);

   417 			else

   418 				pA->Free(j,l);

   419 			test(pA->Avail()==aSize);

   420 			Check(*pA);

   421 			}

   422 		}

   423 	delete pA;

   424 	}

   425 

   426 void TestBlockFree(TInt aSize)

   427 	{

   428 	test.Printf(_L("TestBlockFree %d\n"),aSize);

   429 	const TInt begin[]={0,1,2,7,16,29,31,32,33,63,64,65,83,128};

   430 	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);

   431 	test(pA!=NULL);

   432 	test(pA->Avail()==0);

   433 	TInt i;

   434 	for (i=0; i<(TInt)(sizeof(begin)/sizeof(TInt)); ++i)

   435 		{

   436 		TInt j=begin[i];

   437 		if (j>aSize)

   438 			break;

   439 		TInt l;

   440 		for (l=1; l<=aSize-j; ++l)

   441 			{

   442 //			test.Printf(_L("j=%d, l=%d, s=%d\n"),j,l,aSize);

   443 			pA->Free(j,l);

   444 			test(pA->Avail()==l);

   445 			test(!pA->NotFree(j,l));

   446 			if (j+l<aSize)

   447 				test(pA->NotFree(j,l+1));

   448 			if (j>0)

   449 				test(pA->NotFree(j-1,l));

   450 			TInt r=pA->Alloc();

   451 			test(r==j);

   452 			if (l>1)

   453 				pA->Alloc(j+1,l-1);

   454 			test(pA->Avail()==0);

   455 			Check(*pA);

   456 			}

   457 		}

   458 	delete pA;

   459 	}

   460 

   461 void TestNotFree(TInt aSize)

   462 	{

   463 	test.Printf(_L("TestNotFree %d\n"),aSize);

   464 	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, ETrue);

   465 	test(pA!=NULL);

   466 	test(pA->Avail()==aSize);

   467 	test(!pA->NotFree(0,aSize));

   468 	TInt i;

   469 	for (i=0; i<aSize; ++i)

   470 		{

   471 		pA->Alloc(i,1);

   472 		test(pA->NotFree(0,aSize));

   473 		TInt j;

   474 		for (j=1; j*j<=i || j*j+i<=aSize; ++j)

   475 			{

   476 			TInt a=Max(i-j*j,0);

   477 			TInt b=Min(i+j*j,aSize);

   478 			test(pA->NotFree(a,b-a));

   479 			}

   480 		pA->Free(i);

   481 		test(!pA->NotFree(0,aSize));

   482 		}

   483 	const TInt begin[]={0,1,2,7,16,29,31,32,33,63,64,65,83,128};

   484 	const TInt size[]={2,3,7,16,23,31,32,33,63,64,65,89,128};

   485 	const TInt* pB=begin;

   486 	const TInt* pBE=pB+sizeof(begin)/sizeof(TInt);

   487 	const TInt* pS=size;

   488 	const TInt* pSE=pS+sizeof(size)/sizeof(TInt);

   489 	for (; pB<pBE; ++pB)

   490 		{

   491 		TInt b=*pB;

   492 		if (b>=aSize)

   493 			continue;

   494 		for (; pS<pSE; ++pS)

   495 			{

   496 			TInt l=*pS;

   497 			if (b+l>aSize)

   498 				continue;

   499 			pA->Alloc(b,l);

   500 			TInt j;

   501 			for (j=1; j<aSize; ++j)

   502 				{

   503 				if (j<=b)

   504 					test(!pA->NotFree(0,j));

   505 				else

   506 					test(pA->NotFree(0,j));

   507 				if (aSize-j>=b+l)

   508 					test(!pA->NotFree(aSize-j,j));

   509 				else

   510 					test(pA->NotFree(aSize-j,j));

   511 				}

   512 			pA->Free(b,l);

   513 			}

   514 		}

   515 	delete pA;

   516 	}

   517 

   518 void TestNotAllocated(TInt aSize)

   519 	{

   520 	test.Printf(_L("TestNotAllocated %d\n"),aSize);

   521 	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);

   522 	test(pA!=NULL);

   523 	test(pA->Avail()==0);

   524 	test(!pA->NotAllocated(0,aSize));

   525 	TInt i;

   526 	for (i=0; i<aSize; ++i)

   527 		{

   528 		pA->Free(i);

   529 		test(pA->NotAllocated(0,aSize));

   530 		TInt j;

   531 		for (j=1; j*j<=i || j*j+i<=aSize; ++j)

   532 			{

   533 			TInt a=Max(i-j*j,0);

   534 			TInt b=Min(i+j*j,aSize);

   535 			test(pA->NotAllocated(a,b-a));

   536 			}

   537 		pA->Alloc(i,1);

   538 		test(!pA->NotAllocated(0,aSize));

   539 		}

   540 	const TInt begin[]={0,1,2,7,16,29,31,32,33,63,64,65,83,128};

   541 	const TInt size[]={2,3,7,16,23,31,32,33,63,64,65,89,128};

   542 	const TInt* pB=begin;

   543 	const TInt* pBE=pB+sizeof(begin)/sizeof(TInt);

   544 	const TInt* pS=size;

   545 	const TInt* pSE=pS+sizeof(size)/sizeof(TInt);

   546 	for (; pB<pBE; ++pB)

   547 		{

   548 		TInt b=*pB;

   549 		if (b>=aSize)

   550 			continue;

   551 		for (; pS<pSE; ++pS)

   552 			{

   553 			TInt l=*pS;

   554 			if (b+l>aSize)

   555 				continue;

   556 			pA->Free(b,l);

   557 			TInt j;

   558 			for (j=1; j<aSize; ++j)

   559 				{

   560 				if (j<=b)

   561 					test(!pA->NotAllocated(0,j));

   562 				else

   563 					test(pA->NotAllocated(0,j));

   564 				if (aSize-j>=b+l)

   565 					test(!pA->NotAllocated(aSize-j,j));

   566 				else

   567 					test(pA->NotAllocated(aSize-j,j));

   568 				}

   569 			pA->Alloc(b,l);

   570 			}

   571 		}

   572 	delete pA;

   573 	}

   574 

   575 void TestAllocList(TInt aSize)

   576 	{

   577 	test.Printf(_L("TestAllocList %d\n"),aSize);

   578 	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);

   579 	test(pA!=NULL);

   580 	test(pA->Avail()==0);

   581 	TInt i;

   582 	TInt list[256];

   583 	for (i=0; i<aSize; ++i)

   584 		{

   585 		pA->Free(i);

   586 		test(pA->AllocList(128,list)==1);

   587 		test(list[0]==i);

   588 		test(pA->Avail()==0);

   589 		}

   590 	TInt j;

   591 	for (i=0; i<aSize-1; ++i)

   592 		{

   593 		for (j=i+1; j<aSize; ++j)

   594 			{

   595 			pA->Free(i);

   596 			pA->Free(j);

   597 			test(pA->AllocList(1,list)==1);

   598 			test(list[0]==i);

   599 			test(pA->Avail()==1);

   600 			pA->Free(i);

   601 			test(pA->AllocList(128,list)==2);

   602 			test(list[0]==i && list[1]==j);

   603 			test(pA->Avail()==0);

   604 			}

   605 		}

   606 	TInt l;

   607 	for (l=1; l<80; ++l)

   608 		{

   609 		if (2*l+1>aSize)

   610 			break;

   611 		for (i=l+1; i<=aSize-l; ++i)

   612 			{

   613 			pA->Free(0,l);

   614 			pA->Free(i,l);

   615 			test(pA->Avail()==2*l);

   616 			TInt l2;

   617 			for (l2=Max(l-1,1); l2<=2*l; ++l2)

   618 				{

   619 				TInt r=pA->AllocList(l2,list);

   620 //				test.Printf(_L("l2=%d r=%d\n"),l2,r);

   621 				test(r==l2);

   622 				for (j=0; j<Min(l2,l); j++)

   623 					test(list[j]==j);

   624 				for (j=l; j<l2; j++)

   625 					test(list[j]==j-l+i);

   626 				for (j=0; j<l2; ++j)

   627 					pA->Free(list[j]);

   628 				pA->SelectiveFree(0,l);

   629 				pA->SelectiveFree(i,l);

   630 				test(pA->Avail()==2*l);

   631 				}

   632 			pA->Alloc(0,l);

   633 			pA->Alloc(i,l);

   634 			Check(*pA);

   635 			}

   636 		}

   637 	delete pA;

   638 	}

   639 

   640 void TestSelectiveFree(TInt aSize)

   641 	{

   642 	test.Printf(_L("TestSelectiveFree %d\n"),aSize);

   643 	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, ETrue);

   644 	test(pA!=NULL);

   645 	test(pA->Avail()==aSize);

   646 	TInt i;

   647 	TInt j;

   648 	TInt l;

   649 	for (i=2; i<8; ++i)

   650 		{

   651 		for (l=1; l<=aSize; ++l)

   652 			{

   653 			new (pA) TBitMapAllocator(aSize, ETrue);

   654 			for (j=0; j<aSize; j+=i)

   655 				pA->Alloc(j,1);

   656 			TInt orig=pA->Avail();

   657 			test(orig==aSize-(aSize+i-1)/i);

   658 			pA->SelectiveFree(0,l);

   659 			TInt freed=pA->Avail()-orig;

   660 			test(freed==(l+i-1)/i);

   661 			Check(*pA);

   662 			}

   663 		}

   664 	for (i=0; i<=Min(32,aSize-1); ++i)

   665 		{

   666 		for (l=1; l<=aSize-i; ++l)

   667 			{

   668 			for (j=1; j<=aSize; ++j)

   669 				{

   670 				new (pA) TBitMapAllocator(aSize, ETrue);

   671 				pA->Alloc(i,l);

   672 				test(pA->Avail()==aSize-l);

   673 				pA->SelectiveFree(0,j);

   674 				test(pA->Avail()==aSize-l+Max(0,Min(i+l,j)-i));

   675 				test(!pA->NotFree(0,j));

   676 				if (j>=i && j<i+l)

   677 					test(pA->NotFree(0,j+1));

   678 				Check(*pA);

   679 				}

   680 			}

   681 		}

   682 	delete pA;

   683 	}

   684 

   685 TBitMapAllocator* DoSetupBMA(TInt aSize, VA_LIST aList)

   686 	{

   687 	TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);

   688 	test(pA!=NULL);

   689 	test(pA->Avail()==0);

   690 	TInt totalfree=0;

   691 	FOREVER

   692 		{

   693 		TInt i=VA_ARG(aList,TInt);

   694 		if (i<0)

   695 			break;

   696 		TInt l=VA_ARG(aList,TInt);

   697 		pA->Free(i,l);

   698 		totalfree+=l;

   699 		}

   700 	test(pA->Avail()==totalfree);

   701 	return pA;

   702 	}

   703 

   704 TBitMapAllocator* SetupBMA(TInt aSize, ...)

   705 	{

   706 	VA_LIST list;

   707 	VA_START(list,aSize);

   708 	return DoSetupBMA(aSize,list);

   709 	}

   710 

   711 void PopulateRangeArray(RArray<SRange>& aArray, VA_LIST aList)

   712 	{

   713 	aArray.Reset();

   714 	TInt n=0;

   715 	FOREVER

   716 		{

   717 		SRange rng;

   718 		rng.iBase=VA_ARG(aList,TInt);

   719 		if (rng.iBase<0)

   720 			break;

   721 		rng.iLength=VA_ARG(aList,TInt);

   722 		rng.iLength<<=8;

   723 		rng.iLength+=n;

   724 		++n;

   725 		test(aArray.Append(rng)==KErrNone);

   726 		}

   727 	}

   728 

   729 TInt FirstFitPos(RArray<SRange>& aArray, TInt aLength)

   730 	{

   731 	TInt c=aArray.Count();

   732 	SRange* pR=&aArray[0];

   733 	SRange* pE=pR+c;

   734 	for (; pR<pE; ++pR)

   735 		{

   736 		TInt l=pR->iLength>>8;

   737 		if (l>=aLength)

   738 			{

   739 //			test.Printf(_L("FFP %d = %d\n"),aLength,pR->iBase);

   740 			return pR->iBase;

   741 			}

   742 		}

   743 //	test.Printf(_L("FFP %d = -1\n"),aLength);

   744 	return -1;

   745 	}

   746 

   747 TInt AlignedFirstFitPos(RArray<SRange>& aArray, TInt aSize, TInt aLength, TInt aAlign, TInt aBase, TInt aOffset=0, TBool aBestFit=EFalse)

   748 	{

   749 	TInt alignSize=1<<aAlign;

   750 	TInt alignMask=alignSize-1;

   751 	TInt minRun=0;

   752 	TInt minRunStart=0;

   753 	TBool runFound = EFalse;

   754 	TInt c=aArray.Count();

   755 	SRange* pR=&aArray[0];

   756 	// Best fit mode should ignore any final run TBitMapAllocator will 

   757 	// always ignore the final run in best fit mode and rely on carry being

   758 	// checked by the caller.

   759 	SRange* pE = pR + c - 1;

   760 	if (!aBestFit || aSize > pE->iBase + (pE->iLength >> 8))

   761 		pE++;

   762 

   763 	for (; pR<pE; ++pR)

   764 		{

   765 		TInt l=pR->iLength>>8;

   766 		TInt b=pR->iBase;

   767 		if (aOffset != 0)

   768 			{

   769 			aOffset = ((aOffset + aBase + alignMask) & ~alignMask) - aBase;

   770 			if (aOffset + aLength - 1 >= b + l)

   771 				{// The offset is after the end of this region.

   772 				continue;

   773 				}

   774 			l -= (aOffset <= b)? 0 : aOffset - b;

   775 			b += (aOffset <= b)? 0 : aOffset - b;	// Start the search from aOffset

   776 			}

   777 		TInt ab=((b+aBase+alignMask)&~alignMask)-aBase;

   778 		TInt al = l + b - ab;

   779 		if (al >= aLength)

   780 			{

   781 			if (!aBestFit || l == aLength)

   782 				{

   783 //				test.Printf(_L("AFFP %d %d %d = %d\n"),aLength,aAlign,aBase,ab);

   784 				return ab;

   785 				}

   786 			if (!runFound || minRun > l)

   787 				{ 

   788 				minRun = l;

   789 				minRunStart = ab;

   790 				runFound = ETrue;

   791 				}

   792 			}

   793 		}

   794 	if (runFound)

   795 		{

   796 		return minRunStart;

   797 		}

   798 //	test.Printf(_L("AFFP %d %d %d = -1\n"),aLength,aAlign,aBase);

   799 	return -1;

   800 	}

   801 

   802 void DoConsecTest(TInt aSize, ...)

   803 	{

   804 	test.Printf(_L("DoConsecTest %d\n"),aSize);

   805 	VA_LIST list;

   806 	VA_LIST list2;

   807 	VA_START(list,aSize);

   808 	VA_START(list2,aSize);

   809 	TBitMapAllocator* pA=DoSetupBMA(aSize,list2);

   810 	RArray<SRange> rangeArray(8,_FOFF(SRange,iLength));

   811 	PopulateRangeArray(rangeArray, list);

   812 	TInt n;

   813 	for (n=1; n<=aSize; ++n)

   814 		{

   815 		TInt r1=pA->AllocConsecutive(n,EFalse);

   816 		TInt r2=FirstFitPos(rangeArray,n);

   817 //		test.Printf(_L("ALC(%d,0) = %d [%d]\n"),n,r1,r2);

   818 		test_Equal(r2, r1);

   819 		}

   820 	rangeArray.SortUnsigned();	// sort array in ascending order of length

   821 	for (n=1; n<=aSize; ++n)

   822 		{

   823 		TInt r1=pA->AllocConsecutive(n,ETrue);

   824 		TInt r2=FirstFitPos(rangeArray,n);

   825 //		test.Printf(_L("ALC(%d,1) = %d [%d]\n"),n,r1,r2);

   826 		test_Equal(r2, r1);

   827 		}

   828 	rangeArray.Close();

   829 	delete pA;

   830 	}

   831 

   832 void DoAlignedTest(TInt aSize, ...)

   833 	{

   834 	test.Printf(_L("DoAlignedTest %d\n"),aSize);

   835 	VA_LIST list;

   836 	VA_LIST list2;

   837 	VA_START(list,aSize);

   838 	VA_START(list2,aSize);

   839 	TBitMapAllocator* pA=DoSetupBMA(aSize,list2);

   840 	RArray<SRange> rangeArray(8,_FOFF(SRange,iLength));

   841 	PopulateRangeArray(rangeArray, list);

   842 	TInt finalRunLength = 0;

   843 	SRange& lastRun = rangeArray[rangeArray.Count() - 1];

   844 	if (lastRun.iBase + (lastRun.iLength>>8) == aSize)

   845 		{// The last run is at the end of the bma.

   846 		finalRunLength = lastRun.iLength >> 8;

   847 		}

   848 	TInt a;

   849 	TInt b;

   850 	TInt n;

   851 	TUint offset;

   852 	for (a=0; ((1<<a)<=aSize); ++a)

   853 		{

   854 		TInt alignsize=1<<a;

   855 		TInt alignmask=alignsize-1;

   856 		for (b=0; b<(1<<a); ++b)

   857 			{

   858 //			test.Printf(_L("size %d a=%d b=%d First\n"),aSize,a,b);

   859 			for (n=1; n<=aSize; ++n)

   860 				{

   861 				for (offset = 1; offset < (TUint)aSize; offset <<= 1)

   862 					{

   863 					TInt carry = 0;

   864 					TInt runLength;

   865 					TInt r1=pA->AllocAligned(n,a,b,EFalse, carry, runLength, offset);

   866 					TInt r2=AlignedFirstFitPos(rangeArray,aSize, n,a,b, offset);

   867 					if (r2 < 0 && pA->iSize == pA->iAvail)

   868 						{// Totally empty bmas return KErrOverflow on failure.

   869 						r2 = KErrOverflow;

   870 						}

   871 //					test.Printf(_L("ALA %d %d %d %d 0 = %d [%d]\n"),n,a,b,offset,r1,r2);

   872 					test( (r1<0) || ((r1+b)&alignmask)==0 );

   873 					test( (r1<0) || !pA->NotFree(r1,n));

   874 					test( (r1<0) || runLength >= n);

   875 					test_Equal(r2, r1);

   876 					}

   877 				}

   878 			}

   879 		}

   880 	for (a=0; ((1<<a)<=aSize); ++a)

   881 		{

   882 		TInt alignsize=1<<a;

   883 		TInt alignmask=alignsize-1;

   884 		for (b=0; b<(1<<a); ++b)

   885 			{

   886 //			test.Printf(_L("size %d a=%d b=%d Best\n"),aSize,a,b);

   887 			for (n=1; n<=aSize; ++n)

   888 				{// test for with offset=0 as that has screwed best fit in past.

   889 				for (offset = 0; offset < (TUint)aSize; offset <<= 1)

   890 					{

   891 					TInt carry = 0;

   892 					TInt runLength;

   893 					TInt r1=pA->AllocAligned(n,a,b,ETrue, carry, runLength, offset);

   894 					TInt r2=AlignedFirstFitPos(rangeArray,aSize, n,a,b, offset, ETrue);

   895 					if (pA->iSize == pA->iAvail)

   896 						{// Totally empty bmas return KErrOverflow always on best fit mode.

   897 						r2 = KErrOverflow;

   898 						}

   899 //					test.Printf(_L("ALA %d %d %d 1 = %d [%d]\n"),n,a,b,r1,r2);

   900 					test( (r1<0) || ((r1+b)&alignmask)==0 );

   901 					test( (r1<0) || !pA->NotFree(r1,n));

   902 					test( (r1<0) || runLength >= n);

   903 					test_Equal(r2, r1);

   904 					// No carry in so if run found then carry should be zero.

   905 					// If no run found then carry should set to the length of

   906 					// any run at the end of the bma minus the aligned offset.

   907 					TInt lost = 0;

   908 					TInt alignOffset = ((offset + b + alignmask) & ~alignmask) - b;

   909 					if (finalRunLength && offset &&	lastRun.iBase < alignOffset)

   910 						{// This search had started past the start of the final run

   911 						// so the final run length found will be shorter than its 

   912 						// total length.

   913 						if (alignOffset < aSize)

   914 							{

   915 							lost = Min(alignOffset - lastRun.iBase, finalRunLength);

   916 							}

   917 						else // alignedOffset starts past end of bma.

   918 							lost = finalRunLength;

   919 						}

   920 					test((r1>=0 && carry == 0) || carry == finalRunLength - lost);

   921 					offset = (offset)? offset : 1;

   922 					}

   923 				}

   924 			}

   925 		}

   926 	rangeArray.Close();

   927 	delete pA;

   928 	}

   929 

   930 void Clone(TAny* aDest, const TBitMapAllocator* aSrc)

   931 	{

   932 	TInt nmapw=(aSrc->iSize+31)>>5;

   933 	TInt memsz=sizeof(TBitMapAllocator)+(nmapw-1)*sizeof(TUint32);

   934 	Mem::Move(aDest,aSrc,memsz);

   935 	}

   936 

   937 void TestAllocConsecutive()

   938 	{

   939 	test.Printf(_L("TestAllocConsecutive\n"));

   940 	DoConsecTest(256, 0,4 , 20,8 , 38,1 , 58,6 , 65,10, 78,16 , 127,72, 222,19 , 244,12 , -1);

   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,

   942 																	118,19 , 138,23 , 162,47 , 254,1 , -1);

   943 	DoConsecTest(1023, 0,2 , 32,32 , 65,31 , 99,30 , 144,64 , 256,519 , 776,1, 778,245 , -1);

   944 

   945 	DoAlignedTest(256, 0,4 , 20,8 , 38,1 , 58,6 , 65,10, 78,16 , 127,72, 222,19 , 244,12 , -1);

   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,

   947 																	118,19 , 138,23 , 162,47 , 254,1 , -1);

   948 	DoAlignedTest(1023, 0,2 , 32,32 , 65,31 , 99,30 , 144,64 , 256,519 , 776,1, 778,245 , -1);

   949 	// Test some completely free bmas

   950 	DoAlignedTest(255, 0,255, -1);

   951 	DoAlignedTest(256, 0,256, -1);

   952 	DoAlignedTest(1023, 0,1023, -1);

   953 	DoAlignedTest(1024, 0,1024, -1);

   954 	}

   955 

   956 void DoTestChain(const TBitMapAllocator& aBma, TInt aNumSplits, ...)

   957 	{

   958 	test.Printf(_L("DoTestChain %d %d\n"),aBma.iSize,aNumSplits);

   959 	VA_LIST list;

   960 	VA_START(list,aNumSplits);

   961 

   962 	TBmaList* pL=TBmaList::New(aBma,aNumSplits,list);

   963 	test(pL!=NULL);

   964 

   965 	TInt n;

   966 	for (n=1; n<=aBma.iSize; ++n)

   967 		{

   968 		TInt r1=aBma.AllocConsecutive(n,EFalse);

   969 		TInt r2=pL->AllocConsecutiveFF(n);

   970 //		test.Printf(_L("CHAIN C FF %d: r1=%d r2=%d\n"),n,r1,r2);

   971 		test(r1==r2);

   972 		}

   973 	for (n=1; n<=aBma.iSize; ++n)

   974 		{

   975 		TInt r1=aBma.AllocConsecutive(n,ETrue);

   976 		TInt r2=pL->AllocConsecutiveBF(n);

   977 //		test.Printf(_L("CHAIN C BF %d: r1=%d r2=%d\n"),n,r1,r2);

   978 		test(r1==r2);

   979 		}

   980 

   981 	TInt a;

   982 	for (a=0; ((1<<a)<=aBma.iSize); ++a)

   983 		{

   984 		for (n=1; n<=aBma.iSize; ++n)

   985 			{

   986 			if (n==264 && a==9)

   987 				{

   988 				++n;

   989 				--n;

   990 				}

   991 			TInt r1=aBma.AllocAligned(n,a,0,EFalse);

   992 			TInt r2=pL->AllocAlignedFF(n,a);

   993 //			test.Printf(_L("CHAIN A FF %d,%d: r1=%d r2=%d\n"),n,a,r1,r2);

   994 			test(r1==r2);

   995 			}

   996 		}

   997 	for (a=0; ((1<<a)<=aBma.iSize); ++a)

   998 		{

   999 		for (n=1; n<=aBma.iSize; ++n)

  1000 			{

  1001 			if (n==240 && a==3)

  1002 				{

  1003 				++n;

  1004 				--n;

  1005 				}

  1006 			TInt r1=aBma.AllocAligned(n,a,0,ETrue);

  1007 			TInt r2=pL->AllocAlignedBF(n,a);

  1008 //			test.Printf(_L("CHAIN A BF %d,%d: r1=%d r2=%d\n"),n,a,r1,r2);

  1009 			test(r1==r2);

  1010 			}

  1011 		}

  1012 

  1013 	delete pL;

  1014 	}

  1015 

  1016 void TestChain()

  1017 	{

  1018 	test.Printf(_L("TestChain\n"));

  1019 	TBitMapAllocator* pA;

  1020 	pA=SetupBMA(1023, 0,2 , 32,32 , 65,31 , 99,30 , 144,64 , 256,519 , 776,1, 778,245 , -1);

  1021 	test(pA!=NULL);

  1022 	DoTestChain(*pA, 2, 300, 700);

  1023 	DoTestChain(*pA, 3, 64, 301, 702);

  1024 	delete pA;

  1025 	pA=SetupBMA(512, 0,2 , 20,10 , 32,32 , 65,31 , 144,64 , 399,113 , -1);

  1026 	test(pA!=NULL);

  1027 	DoTestChain(*pA, 2, 256, 384);

  1028 	DoTestChain(*pA, 3, 128, 256, 384);

  1029 	DoTestChain(*pA, 3, 80, 208, 384);

  1030 	DoTestChain(*pA, 3, 80, 208, 400);

  1031 	delete pA;

  1032 	}

  1033 

  1034 void TestBitOps()

  1035 	{

  1036 	test.Next(_L("Bit operations (32 bit)"));

  1037 	test(__e32_find_ls1_32(0x00000000)==-1);

  1038 	TInt i, j, k;

  1039 	TInt count = 0;

  1040 	for (i=0; i<=31; ++i)

  1041 		test(__e32_find_ls1_32(1u<<i)==i);

  1042 	TUint x = 0;

  1043 	for (i=0; i<1000; ++i)

  1044 		{

  1045 		x = 69069*x + 41;

  1046 		TInt bit = x&31;

  1047 

  1048 		x = 69069*x + 41;

  1049 		TUint y = ((x|1)<<bit);

  1050 

  1051 		test(__e32_find_ls1_32(y) == bit);

  1052 		}

  1053 

  1054 	test(__e32_find_ms1_32(0x00000000)==-1);

  1055 	for (i=0; i<=31; ++i)

  1056 		test(__e32_find_ms1_32(1u<<i)==i);

  1057 	for (i=0; i<1000; ++i)

  1058 		{

  1059 		x = 69069*x + 41;

  1060 		TInt bit = x&31;

  1061 

  1062 		x = 69069*x + 41;

  1063 		TUint y = ((x|0x80000000u)>>bit);

  1064 

  1065 		test(__e32_find_ms1_32(y) == 31-bit);

  1066 		}

  1067 

  1068 	test(__e32_bit_count_32(0)==0);

  1069 	test(__e32_bit_count_32(0xffffffff)==32);

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

  1071 		{

  1072 		TUint32 y = 0xffffffffu << i;

  1073 		TUint32 z = 0xffffffffu >> i;

  1074 		test(__e32_bit_count_32(y) == 32-i);

  1075 		test(__e32_bit_count_32(z) == 32-i);

  1076 		test(__e32_bit_count_32(~y) == i);

  1077 		test(__e32_bit_count_32(~z) == i);

  1078 		}

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

  1080 		for (j=0; j<32; ++j)

  1081 			for (k=0; k<32; ++k)

  1082 				{

  1083 				TUint32 b0 = 1u<<i;

  1084 				TUint32 b1 = 1u<<j;

  1085 				TUint32 b2 = 1u<<k;

  1086 				TUint32 y = b0 | b1 | b2;

  1087 				TInt n;

  1088 				if (i==j && j==k) n=1;

  1089 				else if (i==j || j==k || i==k) n=2;

  1090 				else n=3;

  1091 				test(__e32_bit_count_32(y) == n);

  1092 				test(__e32_bit_count_32(~y) == 32-n);

  1093 				++count;

  1094 				}

  1095 	test.Printf(_L("%d iterations done\n"), count);

  1096 	for (i=0; i<=31; ++i)

  1097 		{

  1098 		test(__e32_bit_count_32(0xaaaaaaaau<<i)==16-(i+1)/2);

  1099 		test(__e32_bit_count_32(0x55555555u<<i)==16-i/2);

  1100 		}

  1101 	test(__e32_bit_count_32(0x33333333u)==16);

  1102 	test(__e32_bit_count_32(0x88888888u)==8);

  1103 

  1104 	test.Next(_L("Bit operations (64 bit)"));

  1105 	test(__e32_find_ls1_64(0x00000000)==-1);

  1106 	for (i=0; i<=63; ++i)

  1107 		{

  1108 		TUint64 x = 1u;

  1109 		x<<=i;

  1110 		test(__e32_find_ls1_64(x)==i);

  1111 		}

  1112 	x = 487;

  1113 	for (i=0; i<1000; ++i)

  1114 		{

  1115 		x = 69069*x + 41;

  1116 		TInt bit = x&63;

  1117 

  1118 		x = 69069*x + 41;

  1119 		TUint32 xl = x|1;

  1120 		x = 69069*x + 41;

  1121 		TUint32 xh = x;

  1122 		TUint64 y = MAKE_TUINT64(xh,xl);

  1123 		y <<= bit;

  1124 		test(__e32_find_ls1_64(y) == bit);

  1125 		}

  1126 

  1127 	test(__e32_find_ms1_64(0x00000000)==-1);

  1128 	for (i=0; i<=63; ++i)

  1129 		{

  1130 		TUint64 x = 1u;

  1131 		x<<=i;

  1132 		test(__e32_find_ms1_64(x)==i);

  1133 		}

  1134 	x = 1039;