--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/kernel/eka/euser/cbase/ub_bma.cpp	Mon Oct 19 15:55:17 2009 +0100
@@ -0,0 +1,571 @@
+// 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)
+			Panic(EBmaFreeBlkNotAllocated);
+		*pM &= ~m;
+		iAvail+=aCount;
+		return;
+		}
+	m=0xFFFFFFFFu<<c;
+	if ((*pM & m)!=m)
+		Panic(EBmaFreeBlkNotAllocated);
+	*pM++ &= ~m;
+	c=aCount-KBitsPerInt+c;
+	while(c>=KBitsPerInt)
+		{
+		if (*pM!=0xFFFFFFFF)
+			Panic(EBmaFreeBlkNotAllocated);
+		*pM++=0;
+		c-=KBitsPerInt;
+		}
+	if (c)
+		{
+		m=0xFFFFFFFFu>>(KBitsPerInt-c);
+		if ((*pM & m)!=m)
+			Panic(EBmaFreeBlkNotAllocated);
+		*pM++ &= ~m;
+		}
+	iAvail+=aCount;
+	}
+
+EXPORT_C TInt CBitMapAllocator::Avail()
+//
+// Get the available blocks count.
+//
+	{
+	return(iAvail);
+	}
+
+EXPORT_C TInt CBitMapAllocator::Size()
+//
+// Get the size of all available blocks.
+//
+	{
+	return(iSize);
+	}
+