// Copyright (c) 1997-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:

// e32\euser\cbase\ub_bma.cpp

// 

//

#include "ub_std.h"

const TInt KBitsPerInt=32;

const TInt KBitsPerIntMask=(KBitsPerInt-1);

const TInt KBitsPerIntShift=5;

inline TInt FindLeastSignificantZero(register TUint n)

	{

	register TInt i=0;

	n=~n;

	if (n<<16==0) n>>=16, i+=16;

	if (n<<24==0) n>>=8, i+=8;

	if (n<<28==0) n>>=4, i+=4;

	if (n<<30==0) n>>=2, i+=2;

	if (n<<31==0) n>>=1, i+=1;

	return i;

	}

inline TInt FindLeastSignificantZero(register TUint n, TUint aFrom)

	{

	n |= ((1<<aFrom)-1);

	return FindLeastSignificantZero(n);

	}

inline TInt FindLeastSignificantOne(register TUint n)

	{

	register TInt i=0;

	if (n<<16==0) n>>=16, i+=16;

	if (n<<24==0) n>>=8, i+=8;

	if (n<<28==0) n>>=4, i+=4;

	if (n<<30==0) n>>=2, i+=2;

	if (n<<31==0) n>>=1, i+=1;

	return i;

	}

inline TInt FindMostSignificantZero(register TUint n)

	{

	register TInt i=31;

	n=~n;

	if (n<0x00010000) n<<=16, i-=16;

	if (n<0x01000000) n<<=8, i-=8;

	if (n<0x10000000) n<<=4, i-=4;

	if (n<0x40000000) n<<=2, i-=2;

	if (n<0x80000000) n<<=1, i-=1;

	return i;

	}

EXPORT_C CBitMapAllocator::CBitMapAllocator(TInt aSize,TInt aLength)

//

// Constructor

//

	: iAvail(aSize),iSize(aSize),iLength(aLength)

	{

	TInt rem=aSize&KBitsPerIntMask;

	if (rem)

		{

		TInt last=(aSize-1)>>KBitsPerIntShift;

		iMap[last]=0xFFFFFFFFu<<rem;

		}

	}

EXPORT_C CBitMapAllocator::~CBitMapAllocator()

//

// Destructor

//

	{

	}

EXPORT_C CBitMapAllocator *CBitMapAllocator::New(TInt aSize)

//

// Create a new bit map allocator.

//

	{

	__ASSERT_ALWAYS(aSize>0,Panic(EBmaSizeLessOrEqualToZero));

	TInt sz=((aSize+KBitsPerIntMask)>>KBitsPerIntShift)-1;

	return(new(sz*sizeof(TUint)) CBitMapAllocator(aSize,sz+1));

	}

EXPORT_C CBitMapAllocator *CBitMapAllocator::NewL(TInt aSize)

//

// Create a new bit map allocator. Leave on any error.

//

	{

	CBitMapAllocator *pA=New(aSize);

	User::LeaveIfNull(pA);

	return(pA);

	}

EXPORT_C TInt CBitMapAllocator::Alloc()

//

// Allocate the next position.

//

	{

	if (iAvail)

		{

		TUint *pS=iMap;

		TUint *pE=pS+iLength;

		do	{

			register TUint n=*pS++;

			if (n!=0xFFFFFFFFu)

				{

				iAvail--;

				TInt bit=FindLeastSignificantZero(n);

				*--pS=n|(1<<bit);

				return((TInt(pS-iMap)<<KBitsPerIntShift)+bit);

				}

			} while(pS<pE);

		Panic(EBmaInconsistentState);

		}

	return(KErrNoMemory);

	}

EXPORT_C TInt CBitMapAllocator::AllocFrom(TInt aPos)

//

// Allocate the next position after aPos.

//

	{

	__ASSERT_ALWAYS((aPos>=0 && aPos<iSize),Panic(EBmaAllocFromOutOfRange));

	if (iAvail)

		{

		TUint *pS=iMap+(aPos>>KBitsPerIntShift);

		TUint *pE=iMap+iLength;

		TInt start=aPos&KBitsPerIntMask;

		register TUint n;

		if (start)

			{

			n=*pS++ | ~(0xFFFFFFFFu<<start);

			if (n!=0xFFFFFFFFu)

				goto found;

			}

		while(pS<pE)

			{

			n=*pS++;

			if (n!=0xFFFFFFFFu)

				{

found:

				iAvail--;

				TInt bit=FindLeastSignificantZero(n);

				*--pS |= (1<<bit);

				return((TInt(pS-iMap)<<KBitsPerIntShift)+bit);

				}

			}

		}

	return(KErrNoMemory);

	}

EXPORT_C TInt CBitMapAllocator::AllocFromTop()

//

// Allocate the next position.

//

	{

	if (iAvail)

		{

		TUint *pS=iMap;

		TUint *pE=pS+iLength;

		do	{

			register TUint n=*--pE;

			if (n!=0xFFFFFFFFu)

				{

				iAvail--;

				TInt bit=FindMostSignificantZero(n);

				*pE=n|(1<<bit);

				return((TInt(pE-pS)<<KBitsPerIntShift)+bit);

				}

			} while(pE>pS);

		Panic(EBmaInconsistentState);

		}

	return(KErrNoMemory);

	}

EXPORT_C TInt CBitMapAllocator::AllocFromTopFrom(TInt aPos)

//

// Allocate the next position after aPos.

//

	{

	__ASSERT_ALWAYS((aPos>=0 && aPos<iSize),Panic(EBmaAllocFromTopFromOutOfRange));

	if (iAvail)

		{

		TUint *pS=iMap;

		TUint *pE=pS+((aPos+1)>>KBitsPerIntShift);

		TInt start=(aPos+1)&KBitsPerIntMask;

		register TUint n;

		if (start)

			{

			n=*pE | (0xFFFFFFFFu<<start);

			if (n!=0xFFFFFFFFu)

				goto found;

			}

		while(pE>pS)

			{

			n=*--pE;

			if (n!=0xFFFFFFFFu)

				{

found:

				iAvail--;

				TInt bit=FindMostSignificantZero(n);

				*pE|=(1<<bit);

				return((TInt(pE-pS)<<KBitsPerIntShift)+bit);

				}

			}

		}

	return(KErrNoMemory);

	}

EXPORT_C TInt CBitMapAllocator::Alloc(TInt aCount, TInt& aConsecutive)

	{

	__ASSERT_ALWAYS((aCount>0),Panic(EBmaAllocCountNegative));

	TInt initPos;

	if (iAvail)

		{

		TUint *pS=iMap;

		TUint *pE=pS+iLength;

		register TUint n;

		do	{

			n=*pS++;

			if (n!=0xFFFFFFFFu)

				goto found;

			} while(pS<pE);

		Panic(EBmaInconsistentState);

found:

		register TInt c;

		pS--;

		TInt bit=FindLeastSignificantZero(n);

		initPos=(TInt(pS-iMap)<<KBitsPerIntShift)+bit;

		n>>=bit;

		if (n)

			{

			c=FindLeastSignificantOne(n);

			if (aCount<c) c=aCount;

			*pS |= ~(0xFFFFFFFFu<<c)<<bit;

			iAvail-=c;

			aConsecutive=c;

			return initPos;

			}

		c=KBitsPerInt-bit;

		if (c>=aCount)

			{

			c=aCount;

			if (c<KBitsPerInt)

				*pS |= ~(0xFFFFFFFFu<<c)<<bit;

			else

				*pS |= 0xFFFFFFFFu<<bit;

			iAvail-=c;

			aConsecutive=c;

			return initPos;

			}

		c=aCount-c;

		*pS=0xFFFFFFFFu;

		while(++pS<pE && (n=*pS)==0 && c>=KBitsPerInt)

			*pS=0xFFFFFFFFu, c-=KBitsPerInt;

		if (c && pS<pE && n!=0xFFFFFFFFu)

			{

			bit=n?FindLeastSignificantOne(n):KBitsPerInt;

			if (bit>c) bit=c;

			*pS |= ~(0xFFFFFFFFu<<bit);

			c-=bit;

			}

		aConsecutive=aCount-c;

		iAvail-=aConsecutive;

		return initPos;

		}

	aConsecutive=0;

	return KErrNoMemory;

	}

LOCAL_D const TUint AlignedSearchMask[] =

	{0x00000000,0xAAAAAAAA,0xEEEEEEEE,0xFEFEFEFE,0xFFFEFFFE};

EXPORT_C TInt CBitMapAllocator::AllocAligned(TInt anAlignment)

	{

	__ASSERT_ALWAYS((anAlignment>=0 && anAlignment<32),Panic(EBmaAllAlgnOutOfRange));

	if (iAvail==0)

		return KErrNoMemory;

	TUint mask;

	TInt step;

	if (anAlignment>=KBitsPerIntShift)

		{

		mask=0xFFFFFFFEu;

		step=1<<(anAlignment-KBitsPerIntShift);

		}

	else

		{

		mask=AlignedSearchMask[anAlignment];

		step=1;

		}

	TUint *pM=iMap;

	TUint *pE=pM+iLength;

	do	{

		register TUint n=*pM | mask;

		if (n!=0xFFFFFFFFu)

			{

			iAvail--;

			TInt bit=(mask==0xFFFFFFFEu)?0:FindLeastSignificantZero(n);

			*pM |= (1<<bit);

			return((TInt(pM-iMap)<<KBitsPerIntShift)+bit);

			}

		pM+=step;

		} while(pM<pE);

	return KErrNoMemory;

	}

EXPORT_C TInt CBitMapAllocator::AllocAlignedBlock(TInt anAlignment)

	{

	__ASSERT_ALWAYS((anAlignment>=0 && anAlignment<32),Panic(EBmaAllAlgnBOutOfRange));

	if (iAvail==0)

		return KErrNoMemory;

	TInt blocksz=1<<anAlignment;

	TUint mask;

	TUint block;

	TInt step;

	if (anAlignment>=KBitsPerIntShift)

		{

		mask=0xFFFFFFFEu;

		step=1<<(anAlignment-KBitsPerIntShift);

		block=0xFFFFFFFFu;

		}

	else

		{

		mask=AlignedSearchMask[anAlignment];

		step=1;

		block=~(0xFFFFFFFFu<<blocksz);

		}

	TUint *pM=iMap;

	TUint *pE=pM+iLength;

	do	{

		register TUint n=*pM | mask;

		if (n!=0xFFFFFFFFu)

			{

			if (blocksz>=KBitsPerInt)

				{

				n=0;

				TUint *pS=pM+step;

				if (pS<=pE)

					{

					do n|=*pM++; while(pM<pS);

					pM-=step;

					if (n==0)

						{

						iAvail-=blocksz;

						do *pM++=0xFFFFFFFFu; while(pM<pS);

						pM-=step;

						return (TInt(pM-iMap)<<KBitsPerIntShift);

						}

					}

				}

			else

				{

				TInt bit=FindLeastSignificantZero(n);

				mask=block<<bit;

				n=*pM;

				do	{

					if ((n&mask)==0)

						{

						*pM |= mask;

						iAvail-=blocksz;

						return((TInt(pM-iMap)<<KBitsPerIntShift)+bit);

						}

					bit+=blocksz;

					mask<<=blocksz;

					} while(mask);

				}

			}

		pM+=step;

		} while(pM<pE);

	return KErrNoMemory;

	}

EXPORT_C void CBitMapAllocator::AllocAt(TInt aPos)

//

// Allocate a required position.

//

	{

	__ASSERT_ALWAYS(aPos>=0 && aPos<iSize,Panic(EBmaAllocOutOfRange));

	TUint *pM=iMap+(aPos>>KBitsPerIntShift);

	TUint mask=1<<(aPos&KBitsPerIntMask);

	__ASSERT_ALWAYS(!(*pM&mask),Panic(EBmaAllocAtAlreadyAllocated));

	*pM |= mask;

	iAvail--;

	}

EXPORT_C void CBitMapAllocator::AllocAt(TInt aPos, TInt aCount)

	{

	__ASSERT_ALWAYS((aPos>=0 && (aPos+aCount)<=iSize),Panic(EBmaAllocBlkOutOfRange));

	TUint *pM=iMap+(aPos>>KBitsPerIntShift);

	TInt c=aPos&KBitsPerIntMask;

	TUint m;

	if (aCount<(KBitsPerInt-c))

		{

		m=~(0xFFFFFFFFu<<aCount)<<c;

		if (*pM & m)

			Panic(EBmaAllocBlkNotFree);

		*pM |= m;

		iAvail-=aCount;

		return;

		}

	m=0xFFFFFFFFu<<c;

	if (*pM & m)

		Panic(EBmaAllocBlkNotFree);

	*pM++ |= m;

	c=aCount-KBitsPerInt+c;

	while(c>=KBitsPerInt)

		{

		if (*pM)

			Panic(EBmaAllocBlkNotFree);

		*pM++=0xFFFFFFFFu;

		c-=KBitsPerInt;

		}

	if (c)

		{

		m=0xFFFFFFFFu>>(KBitsPerInt-c);

		if (*pM & m)

			Panic(EBmaAllocBlkNotFree);

		*pM++ |= m;

		}

	iAvail-=aCount;

	}

EXPORT_C TInt CBitMapAllocator::ExtractRamPages(TInt aConsecutive,TInt& aPageNo)

	{

	if(iAvail<aConsecutive)

		return KErrNoMemory;

	TUint *pS=iMap;

	TUint *pE=pS+iLength;

	do	{

		register TUint n=*pS++;

		if (n!=0xFFFFFFFFu)

			{

			TInt x = 0;

			do

				{

				TInt bit=FindLeastSignificantZero(n,x);

				TInt pos=(TInt((pS-1)-iMap)<<KBitsPerIntShift)+bit;

				if(pos+aConsecutive > iSize)

					return KErrNoMemory;

				if(IsFree(pos,aConsecutive))

					{

					AllocAt(pos,aConsecutive);

					aPageNo=pos;

					return KErrNone;

					}

				else

					{

					x = bit+2;

					}

				}

			while (x < KBitsPerInt);

			} 

		} while(pS<pE);

	return KErrNoMemory;

	}

EXPORT_C TBool CBitMapAllocator::IsFree(TInt aPos)

//

// Check a required position is available

//

	{

	__ASSERT_ALWAYS(aPos>=0 && aPos<iSize,Panic(EBmaFreeOutOfRange));

	TUint n=iMap[aPos>>KBitsPerIntShift];

	return !(n>>(aPos&KBitsPerIntMask)&1);

	}

EXPORT_C TBool CBitMapAllocator::IsFree(TInt aPos, TInt aCount)

	{

	__ASSERT_ALWAYS((aPos>=0 && (aPos+aCount)<=iSize),Panic(EBmaChkBlkOutOfRange));

	TUint *pM=iMap+(aPos>>KBitsPerIntShift);

	TUint m=*pM++;

	TInt c=aPos&KBitsPerIntMask;

	m>>=c;

	if (aCount<(KBitsPerInt-c))

		{

		return !(m&~(0xFFFFFFFFu<<aCount));

		}

	aCount-=(KBitsPerInt-c);

	while(aCount>=KBitsPerInt)

		{

		m |= *pM++;

		aCount-=KBitsPerInt;

		}

	if (aCount)

		{

		m|=(*pM<<(KBitsPerInt-aCount));

		}

	return(!m);

	}

EXPORT_C void CBitMapAllocator::Free(TInt aPos)

//

// Free a position.

//

	{

	__ASSERT_ALWAYS(aPos>=0 && aPos<iSize,Panic(EBmaFreeOutOfRange));

	TUint *pM=iMap+(aPos>>KBitsPerIntShift);

	TUint mask=1<<(aPos&KBitsPerIntMask);

	__ASSERT_ALWAYS((*pM&mask),Panic(EBmaFreeNotAllocated));

	*pM &= ~mask;

	iAvail++;

	}

EXPORT_C void CBitMapAllocator::Free(TInt aPos, TInt aCount)

	{

	__ASSERT_ALWAYS((aPos>=0 && (aPos+aCount)<=iSize),Panic(EBmaFreeBlkOutOfRange));

	TUint *pM=iMap+(aPos>>KBitsPerIntShift);

	TInt c=aPos&KBitsPerIntMask;

	TUint m;

	if (aCount<(KBitsPerInt-c))

		{

		m=~(0xFFFFFFFFu<<aCount)<<c;

		if ((*pM & m)!=m)