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

// All rights reserved.

// This component and the accompanying materials are made available

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

// which accompanies this distribution, and is available

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

//

// Initial Contributors:

// Nokia Corporation - initial contribution.

//

// Contributors:

//

// Description:

// e32test\buffer\t_tbma.cpp

// 

//

#define __E32TEST_EXTENSION__

#include "t_tbma.h"

#include <cpudefs.h>

#include <e32atomics.h>

RTest test(_L("T_TBMA"));

/**************************************

 * class TBmaList

 **************************************/

TBmaList* TBmaList::New(TInt aNumBmas)

	{

	TBmaList* pL=new TBmaList;

	if (pL)

		{

		pL->iNumBmas=aNumBmas;

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

		if (pL->iBmaList)

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

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

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

			{

			delete pL;

			pL=NULL;

			}

		}

	return pL;

	}

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

	{

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

	if (!pL)

		return NULL;

	TInt i;

	pL->iBaseList[0]=0;

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

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

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

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

		{

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

		__ASSERT_ALWAYS(sz>0, TBMA_FAULT());

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

		if (!pL->iBmaList[i])

			{

			delete pL;

			return NULL;

			}

		TInt j;

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

			{

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

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

			}

		}

	return pL;

	}

TBmaList::TBmaList()

	{

	iNumBmas=0;

	iBmaList=NULL;

	iBaseList=NULL;

	}

TBmaList::~TBmaList()

	{

	TInt i;

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

		delete iBmaList[i];

	User::Free(iBmaList);

	User::Free(iBaseList);

	}

/*

 * Extended first fit allocator

 */

TInt TBmaList::AllocConsecutiveFF(TInt aLength)

	{

	TInt base=KErrNotFound;

	TInt bmalen=0;

	TInt carry=0;

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

	TBitMapAllocator** pE=ppA+iNumBmas;

	TInt* pB=iBaseList;

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

		{

		TBitMapAllocator* pA=*ppA;

		if (*pB!=base+bmalen)

			{

			// this BMA is not contiguous with previous one

			carry=0;

			}

		base=*pB;

		bmalen=pA->iSize;

		TInt l;

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

		if (r>=0)

			return base+r-carry;

		}

	return KErrNotFound;

	}

/*

 * Extended best fit allocator

 */

TInt TBmaList::AllocConsecutiveBF(TInt aLength)

	{

	TInt bmalen=0;

	TInt carry=0;

	TInt minrun=KMaxTInt;

	TInt minrunpos=KErrNotFound;

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

	TBitMapAllocator** pE=ppA+iNumBmas;

	TInt* pB=iBaseList;

	TInt base=*pB;

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

		{

		TBitMapAllocator* pA=*ppA;

		if (*pB!=base+bmalen)

			{

			// this BMA is not contiguous with previous one

			// check final run of previous BMA

			if (carry<minrun)

				{

				minrun=carry;

				minrunpos=base+bmalen-carry;

				}

			carry=0;

			}

		base=*pB;

		bmalen=pA->iSize;

		TInt l=KMaxTInt;

		TInt oldc=carry;

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

		if (r>=0)

			{

			// check shortest run in this BMA

			if (l<minrun)

				{

				minrun=l;

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

				if (minrun==aLength)

					break;				// exact match so finish

				}

			}

		}

	// check final run of last BMA

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

		minrunpos=base+bmalen-carry;

	return minrunpos;

	}

/*

 * Extended first fit aligned allocator

 */

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

	{

	TUint32 alignsize=1<<aAlign;

	TUint32 alignmask=alignsize-1;

	TInt base=KErrNotFound;

	TInt bmalen=0;

	TInt carry=0;

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

	TBitMapAllocator** pE=ppA+iNumBmas;

	TInt* pB=iBaseList;

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

		{

		TBitMapAllocator* pA=*ppA;

		if (*pB!=base+bmalen)

			{

			// this BMA is not contiguous with previous one

			carry=0;

			}

		base=*pB;

		bmalen=pA->iSize;

		TInt l;

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

		if (r>=0)

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

		}

	return KErrNotFound;

	}

/*

 * Extended best fit aligned allocator

 */

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

	{

	TInt bmalen=0;

	TInt carry=0;

	TInt minrun=KMaxTInt;

	TInt minrunpos=KErrNotFound;

	TUint32 alignsize=1<<aAlign;

	TUint32 alignmask=alignsize-1;

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

	TBitMapAllocator** pE=ppA+iNumBmas;

	TInt* pB=iBaseList;

	TInt base=*pB;

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

		{

		TBitMapAllocator* pA=*ppA;

		if (*pB!=base+bmalen)

			{

			// this BMA is not contiguous with previous one

			// check final run of previous BMA

			if (carry<minrun)

				{

				TInt fpos=base+bmalen-carry;

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

				if (carry-lost>=aLength)

					{

					minrun=carry;

					minrunpos=fpos;

					}

				}

			carry=0;

			}

		base=*pB;

		bmalen=pA->iSize;

		TInt l=KMaxTInt;

		TInt oldc=carry;

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

		if (r>=0)

			{

			// check shortest run in this BMA

			if (l<minrun)

				{

				minrun=l;

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

				if (minrun==aLength)

					break;				// exact match so finish

				}

			}

		}

	// check final run of last BMA

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

		{

		TInt fpos=base+bmalen-carry;

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

		if (carry-lost>=aLength)

			{

			minrun=carry;

			minrunpos=fpos;

			}

		}

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

	}

void Display(TBitMapAllocator* aBma)

	{

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

	TInt i;

	TInt l=0;

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

		{

		if (++l==10)

			{

			l=0;

//			test.Getch();

			}

		TUint32 x=aBma->iMap[i];

		TBuf<80> buf;

		buf.NumFixedWidth(x,EBinary,32);

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

		test.Printf(buf);

		}

	test.Getch();

	}

void Check(TBitMapAllocator& a)

	{

	TInt l=a.iSize;

	l=(l+31)>>5;

	TInt n=0;

	TInt i;

	TUint32* first=NULL;

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

		{

		TUint32 w=a.iMap[i];

		if (w && !first)

			first=a.iMap+i;

		n+=__e32_bit_count_32(w);

		}

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

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

	}

void TestConstruct(TInt aSize)

	{

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

	TBitMapAllocator* pA;

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

	test(pA!=NULL);

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

	Check(*pA);

	delete pA;

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

	test(pA!=NULL);

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

	Check(*pA);

	delete pA;

	}

void TestAlloc1(TInt aSize)

	{

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

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

	test(pA!=NULL);

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

	Check(*pA);

	TInt i;

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

		{

		TInt r=pA->Alloc();

		test(r==i);

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

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

		Check(*pA);

		}

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

	delete pA;

	}

void TestFree1(TInt aSize)

	{

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

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

	test(pA!=NULL);

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

	TInt i;

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

		{

		pA->Free(i);

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

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

		pA->Free(i);

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

		Check(*pA);

		}

	delete pA;

	}

void TestBlockAlloc(TInt aSize)

	{

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

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

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

	test(pA!=NULL);

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

	pA->Alloc(0,aSize);

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

	Check(*pA);

	pA->Free(0,aSize);

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

	Check(*pA);

	TInt i;

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

		{

		TInt j=begin[i];

		if (j>aSize)

			break;

		TInt l;

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

			{

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

			pA->Alloc(j,l);

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

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

			if (j+l<aSize)

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

			if (j>0)

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

			TInt r=pA->Alloc();

			if (j==0)

				{

				if (l<aSize)

					test(r==l);

				else

					test(r<0);

				}

			else

				test(r==0);

			if (r==0)

				{

				pA->Free(r);

				pA->Free(j,l);

				}

			else if (r>0)

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

			else

				pA->Free(j,l);

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

			Check(*pA);

			}

		}

	delete pA;

	}

void TestBlockFree(TInt aSize)

	{

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

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

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

	test(pA!=NULL);

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

	TInt i;

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

		{

		TInt j=begin[i];

		if (j>aSize)

			break;

		TInt l;

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

			{

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

			pA->Free(j,l);

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

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

			if (j+l<aSize)

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

			if (j>0)

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

			TInt r=pA->Alloc();

			test(r==j);

			if (l>1)

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

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

			Check(*pA);

			}

		}

	delete pA;

	}

void TestNotFree(TInt aSize)

	{

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

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

	test(pA!=NULL);

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

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

	TInt i;

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

		{

		pA->Alloc(i,1);

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

		TInt j;

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

			{

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

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

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

			}

		pA->Free(i);

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

		}

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

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

	const TInt* pB=begin;

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

	const TInt* pS=size;

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

	for (; pB<pBE; ++pB)

		{

		TInt b=*pB;

		if (b>=aSize)

			continue;

		for (; pS<pSE; ++pS)

			{

			TInt l=*pS;

			if (b+l>aSize)

				continue;

			pA->Alloc(b,l);

			TInt j;

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

				{

				if (j<=b)

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

				else

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

				if (aSize-j>=b+l)

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

				else

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

				}

			pA->Free(b,l);

			}

		}

	delete pA;

	}

void TestNotAllocated(TInt aSize)

	{

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

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

	test(pA!=NULL);

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

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

	TInt i;

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

		{

		pA->Free(i);