// 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_bma.cpp

// Overview:

// Test the bitmap allocation abilities of the CBitMapAllocator class.

// API Information:

// CBitMapAllocator.

// Details:

// - Create an instance of CBitMapAllocator class with positive size using New and NewL methods, 

// verify that object is created and deleted successfully, test the heap allocation failure. 

// - Verify that the heap has not been corrupted by the test.

// - Test Alloc, AllocFromTop, AllocAt, Free, and AllocFromTopFrom methods of 

// CBitMapAllocator class are as expected.

// - Allocate all available memory using Alloc, AllocFromTop, AllocFromTopFrom

// and check that available free space is zero.

// - Allocate more than available memory using Alloc, AllocFromTop,

// AllocFromTopFrom and check the return value is KErrorNoMemory.

// - Free the memory and check that available free space is equal to the size.

// - Allocate at specified blocks, check the allocation and available free block 

// is as expected.

// - Free the block and check the available space is as expected. 

// - Check the alignment of blocks after allocation is as expected.

// - Perform all of the above tests for CBitMapAllocator size of 1, 4, 32, 33, 68, 96, 64, 65 and 63 bits.

// - Allocate some contiguous pages of RAM from the kernel's free page pool with pattern of 

// increasingly large gaps and test that the pages are allocated as specified.

// - Check KErrorNoMemory is returned when extracting a page beyond the available space.

// - Perform a test specifically for defect EXT-5AMDKP, Alloc, Free and ExtractRamPages. Test for 

// expected results.

// - Test whether the heap has been corrupted by any of the tests.

// Platforms/Drives/Compatibility:

// All 

// Assumptions/Requirement/Pre-requisites:

// Failures and causes:

// Base Port information:

// 

//

#include <e32test.h>

#include <e32base.h>

#include <e32base_private.h>

#include <e32def.h>

#include <e32def_private.h>

const TInt KMaxAllocations=50;

LOCAL_D RTest test(_L("T_BMA"));

LOCAL_C void testNew(TInt aSize)

//

//	Test New

//

	{

	test.Start(_L("New"));

	__UHEAP_MARK;

	CBitMapAllocator* pBitMapAllocator=CBitMapAllocator::New(aSize);

	test(pBitMapAllocator!=NULL);

	test(pBitMapAllocator->Size()==pBitMapAllocator->Avail());

	delete pBitMapAllocator;

	__UHEAP_CHECK(0);

	for (TInt i=1;i<KMaxAllocations;i++)

		{

		test.Printf(_L("Try %d\n"),i);

		__UHEAP_SETFAIL(RHeap::EDeterministic,i);

		pBitMapAllocator=CBitMapAllocator::New(aSize);

		if (pBitMapAllocator!=NULL)

			break;

		__UHEAP_CHECK(0);

		}

	delete pBitMapAllocator;

	__UHEAP_MARKEND;

	__UHEAP_RESET;

	test.End();

	}

LOCAL_C void testNewL(TInt aSize)

//

//	Test NewL

//

	{

	test.Start(_L("NewL"));

	__UHEAP_MARK;

	CBitMapAllocator* pBitMapAllocator=CBitMapAllocator::NewL(aSize);

	test(pBitMapAllocator!=NULL);

	test(pBitMapAllocator->Size()==pBitMapAllocator->Avail());

	delete pBitMapAllocator;

	__UHEAP_CHECK(0);

	test.Next(_L("Repetitive NewL"));

	for (TInt i=1;i<KMaxAllocations;i++)

		{

		test.Printf(_L("Try %d\n"),i);

		__UHEAP_SETFAIL(RHeap::EDeterministic,i);

		TRAPD(r,pBitMapAllocator=CBitMapAllocator::NewL(aSize));

		if (r==KErrNone)

			break;

		__UHEAP_CHECK(0);

		}

	delete pBitMapAllocator;

	__UHEAP_MARKEND;

	__UHEAP_RESET;

  	test.End();	

	}

LOCAL_C void testAlloc(TInt aSize)

//

//	Test Alloc, AllocFromTop, AllocAt, and Free, and AllocFromTopFrom

//

	{

	CBitMapAllocator* pBitMapAllocator=CBitMapAllocator::New(aSize);

	test(pBitMapAllocator!=NULL);

	test.Start(_L("Alloc all available"));

	TInt available=pBitMapAllocator->Avail();

	TInt i=0;

	for (;i<available;i++)

		{

		TInt j=pBitMapAllocator->Alloc();

		test(j==i);

		}

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

//

	test.Next(_L("Try to alloc more than available"));

	i=pBitMapAllocator->Alloc();

	test(i==KErrNoMemory);

//

	test.Next(_L("Free"));

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

		pBitMapAllocator->Free(i);

	test(pBitMapAllocator->Avail()==pBitMapAllocator->Size());

//

	test.Next(_L("AllocFromTop"));	

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

		{

		TInt j=pBitMapAllocator->AllocFromTop();

		test(j==i);

		}

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

//

	test.Next(_L("Try to AllocFromTop more than available"));

	i=pBitMapAllocator->AllocFromTop();

	test(i==KErrNoMemory);

//

	test.Next(_L("Free (again)"));

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

		pBitMapAllocator->Free(i);

	test(pBitMapAllocator->Avail()==pBitMapAllocator->Size());

//

	test.Next(_L("AllocAt"));

	pBitMapAllocator->AllocAt(aSize-1);

	test(pBitMapAllocator->Avail()==pBitMapAllocator->Size()-1);

//

//	test.Next(_L("AllocAt an already allocated cell"));	// this test should cause a Panic.

//	pBitMapAllocator->AllocAt(aSize-1);

//	test(pBitMapAllocator->Avail()==pBitMapAllocator->Size()-1);

//

	test.Next(_L("Free (again)"));

	pBitMapAllocator->Free(aSize-1);

	test(pBitMapAllocator->Avail()==pBitMapAllocator->Size());

//

	test.Next(_L("AllocFromTopFrom"));

	TInt x;

	for (x=available-1;x>0;x--)

		{

		for (i=x;i>=0;i--)

			{

			TInt j=pBitMapAllocator->AllocFromTopFrom(x);

			test(j==i);

			test(!pBitMapAllocator->IsFree(j));

			}

		test(pBitMapAllocator->Avail()==available-x-1);

		test.Next(_L("Try to AllocFromTopFrom more than available"));

		i=pBitMapAllocator->AllocFromTopFrom(x);

		test(i==KErrNoMemory);

//

		TInt y;

		for (y=0;y<=x;y++)

			{

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

				{

				if (pBitMapAllocator->Avail()<=available-x-1)

					pBitMapAllocator->Free(y);

				TInt j=pBitMapAllocator->AllocFromTopFrom(i);

				if (i<y)

					test(j==KErrNoMemory);

				else

					{

					test(j==y);

					test(!pBitMapAllocator->IsFree(j));

					}

				}

			}

//

		test.Next(_L("Free (again)"));

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

			pBitMapAllocator->Free(i);

		test(pBitMapAllocator->Avail()==pBitMapAllocator->Size());

		}

//

	for (x=available-1;x>0;x--)

		{

		for (i=x;i>=0;i--)

			{

			TInt j=pBitMapAllocator->AllocFromTopFrom(x);

			test(j==i);

			}

		test(pBitMapAllocator->Avail()==available-x-1);

		test.Next(_L("Try to AllocFromTopFrom more than available"));

		i=pBitMapAllocator->AllocFromTopFrom(x);

		test(i==KErrNoMemory);

	//

		test.Next(_L("Free (again)"));

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

			pBitMapAllocator->Free(i);

		test(pBitMapAllocator->Avail()==pBitMapAllocator->Size());

		}

	test.End();

	delete pBitMapAllocator;

	}

LOCAL_C void testBlock(TInt aSize)

//

// Test Alloc(TInt, TInt&), AllocAligned, AllocAlignedBlock, AllocAt(TInt, TInt),

// IsFree(TInt, TInt), Free(TInt, TInt)

//

	{

	CBitMapAllocator* pB=CBitMapAllocator::New(aSize);

	test(pB!=NULL);

	test.Start(_L("AllocAt block, Free block, IsFree block"));

	TInt available=pB->Avail();

	test(available==aSize);

	TInt start, len;

	for(start=0; start<available; start++)

		{

		for(len=1; len<=available-start; len++)

			{

			pB->AllocAt(start,len);

			test(pB->Avail()==available-len);

			for(TInt i=0; i<available; i++)

				{

				if (i>=start && i<start+len)

					{

					if(pB->IsFree(i))

						test(0);

					}

				else

					{

					if(!pB->IsFree(i))

						test(0);

					}

				}

			if (start)

				test(pB->IsFree(0,start));

			test(!pB->IsFree(0,start+1));

			if (start+len<available)

				{

				test(pB->IsFree(start+len,available-(start+len)));

				test(!pB->IsFree(start+len-1,available-(start+len-1)));

				}

			pB->Free(start,len);

			test(pB->Avail()==available);

			test(pB->IsFree(start,len));

			test(pB->IsFree(0,available));

			}

		}

	test.End();

	test.Start(_L("Alloc consecutive block"));

	TInt askfor, init, pos, consec;

	for(askfor=1; askfor<=available; askfor++)

		{

		test.Printf(_L("Ask for %d\n"),askfor);

		for(init=0; init<available; init++)

			{

			if (init)

				pB->AllocAt(0,init);

			for(pos=init+1; pos<available; pos++)

				{

				pB->AllocAt(pos);

				TInt firstfree=pB->Alloc(askfor, consec);

				if (firstfree!=init)

					test(0);

				TInt number=(pos-init>askfor)?askfor:pos-init;

				if (consec!=number)

					test(0);

				if (number<pos-init)

					{

					firstfree=pB->Alloc(pos-init-number,consec);

					if(firstfree!=init+number)

						test(0);

					if(consec!=pos-init-number)

						test(0);

					}

				test(pB->Avail()==available-pos-1);

				TInt freeto=available;

				if (pos<available-1)

					{

					firstfree=pB->Alloc(askfor,consec);

					number=(available-pos-1>askfor)?askfor:available-pos-1;

					if (firstfree!=pos+1)

						test(0);

					if (consec!=number)

						test(0);

					freeto=pos+1+number;

					}

				test(pB->Avail()==available-freeto);

				if (available==freeto)

					{

					firstfree=pB->Alloc(1,consec);

					if (firstfree!=KErrNoMemory)

						test(0);

					if (consec!=0)

						test(0);

					}

				pB->Free(init,freeto-init);

				}

			if (init)

				pB->Free(0,init);

			test(pB->Avail()==available);

			}

		}

	test.End();

	test.Start(_L("AllocAligned"));

	TInt alignment, alignstep;

	for(alignment=0, alignstep=1; alignstep<available; alignment++, alignstep<<=1 )

		{

		TInt numaligned=(available+alignstep-1)/alignstep;

		TInt next=0;

		TInt r;

		do	{

			r=pB->AllocAligned(alignment);

			if (r>=0)

				{

				if (r!=next)

					test(0);

				next+=alignstep;

				}

			else if (r!=KErrNoMemory)

				test(0);

			} while(r>=0);

		if (pB->Avail()!=available-numaligned)

			test(0);

		for(TInt i=0; i<available; i++)

			{

			if (i==((i>>alignment)<<alignment) )

				{

				if (pB->IsFree(i))

					test(0);

				pB->Free(i);

				}

			else

				{

				if (!pB->IsFree(i))

					test(0);

				}

			}

		test(pB->Avail()==available);

		}

	test.End();

	test.Start(_L("AllocAlignedBlock"));

	for(alignment=0, alignstep=1; alignstep<available; alignment++, alignstep<<=1 )

		{

		TInt numalignedblocks=available/alignstep;

		TInt next=0;

		TInt r;

		do	{

			r=pB->AllocAlignedBlock(alignment);

			if (r>=0)

				{

				if (r!=next)

					test(0);

				next+=alignstep;

				}

			else if (r!=KErrNoMemory)

				test(0);

			} while(r>=0);

		if (pB->Avail()!=available-numalignedblocks*alignstep)

			test(0);

		if (pB->Avail()!=0)

			{

			if ( !pB->IsFree(numalignedblocks*alignstep,pB->Avail()) )

				test(0);

			r=pB->Alloc();

			if (r!=numalignedblocks*alignstep)

				test(0);

			pB->Free(r);

			}

		pB->Free(0,numalignedblocks*alignstep);

		if (pB->Avail()!=available)

			test(0);

		TInt freepos, blockpos, c;

		for (freepos=0; freepos<available; freepos+=alignstep)

			{

			for (blockpos=0; blockpos<alignstep; blockpos++)

				{

				c=0;

				for(TInt i=blockpos; i<freepos; i+=alignstep)

					{

					pB->AllocAt(i);

					c++;

					}

				if (pB->Avail()!=available-c)

					test(0);

				r=pB->AllocAlignedBlock(alignment);

				if (available-freepos<alignstep)

					{

					if (r!=KErrNoMemory)

						test(0);

					if (pB->Avail()!=available-c)

						test(0);

					}

				else

					{

					if (r!=freepos)

						test(0);

					if (pB->Avail()!=available-c-alignstep)

						test(0);

					pB->Free(freepos,alignstep);

					if (pB->Avail()!=available-c)

						test(0);

					}

				for(TInt j=blockpos; j<freepos; j+=alignstep)

					pB->Free(j);

				if (pB->Avail()!=available)

					test(0);

				}

			}

		}

	delete pB;

	test.End();

	}

LOCAL_C void testContiguousAllocation(TInt aSize)

	{//test RemoveRamPages()

	//set up bitmap with pattern of increasingly large gaps -

	//page 1      - in use,page  2        - free

	//pages 3,4   - in use,pages 5,6      - free

	//pages 7,8,9 - in use,pages 10,11,12 - free  ...etc

	test.Start(_L("Create swiss cheese effect..."));

 	CBitMapAllocator* pB=CBitMapAllocator::New(aSize);

	test(pB!=NULL);

	TInt available=pB->Avail();

	test(available==aSize);

	TInt i=0;

	TInt j=0;

	TInt k=1;

	while(k<46)

		{

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

			{

			pB->AllocAt(i+j);

			test(!pB->IsFree(i+j));

			}

		i+=2*k;

		k++;

		}

	TInt ret=KErrNone;

	TInt pageNo=0;

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

		{

		ret=pB->ExtractRamPages(i,pageNo);	//look for a gap of size i pages and allocate it

		test(pageNo==i*i);				//test the right page no is returned

		test.Printf(_L("OK  -pageNo is :%d\r\n"),pageNo);

		for(j=i*i;j<i*i + i;j++)		//test that the pages are actually allocated

			test(!pB->IsFree(j));

		}

	ret=pB->ExtractRamPages(45,pageNo);//there's not a big enough space in the bitmap for this to succeed

	test(ret==KErrNoMemory);

	delete pB;

	test.End();

	}

LOCAL_C void testAll(TInt aSize)

//

//	Test all BMA functions using a BMA of size aSize

//

	{

	TBuf<0x40> b;

	b.Format(_L("BitMapAllocator size = %d"),aSize);

	test.Start(b);

//

	testNew(aSize);

	testNewL(aSize);

	testAlloc(aSize);

	testBlock(aSize);

//

	test.End();

	}

GLDEF_C TInt E32Main()

//

// Test bitmap allocator

//

	{

	test.Title();

	__UHEAP_MARK;

//

	test.Start(_L("1 bit"));

	testAll(1);

	test.Next(_L("4 bit"));

	testAll(4);

//

	test.Next(_L("32 bit"));

	testAll(32);

//

	test.Next(_L("33 bit"));

	testAll(33);

//

	test.Next(_L("68 bit"));

	testAll(68);

//

	test.Next(_L("96 bit"));

	testAll(96);

//

	test.Next(_L("64 bit"));

	testAll(64);

//

	test.Next(_L("65 bit"));

	testAll(65);

//

	test.Next(_L("63 bit"));

	testAll(63);

	testContiguousAllocation(2048);

	test.Next(_L("test defect EXT-5AMDKP"));

	CBitMapAllocator* pB = CBitMapAllocator::New(64);

	test(pB != NULL);

	pB->AllocAt(0, 32);

	pB->Free(2, 2);

	pB->Free(5, 2);

	pB->Free(8, 2);

	pB->Free(12, 3);

	pB->Free(30, 2);

	TInt page = -1;

	pB->ExtractRamPages(3, page);

	test(page == 12);

	pB->ExtractRamPages(4, page);

	test(page == 30);

	pB->ExtractRamPages(1, page);

	test(page == 2);

	pB->ExtractRamPages(5, page);

	test(page == 34);

	pB->ExtractRamPages(2, page);

	test(page == 5);

	delete pB;	

	__UHEAP_MARKEND;

	test.End();

	return(KErrNone);

	}