diff -r 000000000000 -r a41df078684a kernel/eka/klib/bma.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/kernel/eka/klib/bma.cpp	Mon Oct 19 15:55:17 2009 +0100
@@ -0,0 +1,800 @@
+// Copyright (c) 1994-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\klib\bma.cpp
+// This file is directly included in the test harness t_tbma
+// 
+//
+
+#include <kernel/kbma.h>
+
+#ifdef TBMA_TEST_CODE
+
+#ifdef __MARM__
+#define __TBMA_MACHINE_CODED__
+#endif
+
+#include <e32std.h>
+#include <e32std_private.h>
+#include <e32atomics.h>
+
+#define __ALLOC(x)		User::Alloc(x)
+
+void TBmaFault(TInt aLine)
+	{
+	User::Panic(_L("TBMA"),aLine);
+	}
+
+#else
+
+#include <kernel/kern_priv.h>
+
+#define __ALLOC(x)		Kern::Alloc(x)
+
+void TBmaFault(TInt aLine)
+	{
+	Kern::Fault("TBMA",aLine);
+	}
+
+#endif
+
+#define TBMA_FAULT()	TBmaFault(__LINE__)
+
+/**	Creates a new TBitMapAllocator object.
+
+	@param	aSize The number of bit positions required, must be >0.
+	@param	aState	TRUE if all bit positions initially free
+					FALSE if all bit positions initially allocated.
+	
+	@return	Pointer to new object, NULL if out of memory.
+
+    @pre    Calling thread must be in a critical section.
+    @pre    No fast mutex can be held.
+	@pre	Call in a thread context.
+	@pre	Interrupts must be enabled.
+	@pre	Kernel must be unlocked.
+ */
+EXPORT_C TBitMapAllocator* TBitMapAllocator::New(TInt aSize, TBool aState)
+	{
+	#ifndef TBMA_TEST_CODE
+	CHECK_PRECONDITIONS(MASK_THREAD_CRITICAL,"TBitMapAllocator::New");	
+	#endif
+	TInt nmapw=(aSize+31)>>5;
+	TInt memsz=sizeof(TBitMapAllocator)+(nmapw-1)*sizeof(TUint32);
+	TBitMapAllocator* pA=(TBitMapAllocator*)__ALLOC(memsz);
+	if (pA)
+		new(pA) TBitMapAllocator(aSize, aState);
+	return pA;
+	}
+
+
+/**	Finds a set of consecutive bit positions with specified alignment, with
+	support for chaining multiple allocators.
+	
+	Note that this function does not mark the positions as allocated.
+
+	In first fit mode:
+	1. Any initial run is added to the carry in
+	2. If all bits free, if BMA size+carry<=request length return 0 and leave carry alone
+		else add size to carry and return KErrOverflow
+	3. If request satisfied by initial run + carry return 0 and leave carry alone
+	4. If request satisfied by an intermediate or final run, return start pos of run and set carry=0
+	5. Otherwise carry = length of any final run and return KErrNotFound
+
+	With a single allocator set aCarry (and usually aBase) to zero and ignore
+	aRunLength. The return value then indicates the required position (after
+	being aligned up as necessary) or KErrNotFound.
+
+	With multiple allocators, this function should be called on each allocator in
+	increasing logical bit number order. The carry should be set to zero initially
+	and if there is a gap in the logical bit number between two allocators, otherwise
+	it should be left alone. The first call which returns a nonnegative value indicates
+	success and the required logical bit position is given by aligning up
+		logical bit number of first bit of allocator + return value - carry
+
+	In best fit mode:
+	1. Any initial run is added to the carry in
+	2. If all bits free, add bma length to carry and return KErrOverflow
+	3. If any run including initial+carry but not final has length >= request length
+		return start pos and length of smallest such, also set carry = length of final run
+		unless exact match found, when carry is either unchanged or set to 0
+	4. If only final run large enough, return KErrNotFound and set carry = length of final run
+		carry=0 if no final run
+
+	Here is an example of how to use this for multiple allocators:
+	@code
+	// aLength = run length required, aAlign = alignment constraint
+	TInt bmalen=0;
+	TInt carry=0;
+	TInt minrun=KMaxTInt;					// this will track the length of the shortest useful run
+	TInt minrunpos=KErrNotFound;			// this will track the start position of the shortest useful run
+	TUint32 alignsize=1<<aAlign;
+	TUint32 alignmask=alignsize-1;
+	TBitMapAllocator** ppA=iBmaList;		// pointer to list of TBitMapAllocator*
+	TBitMapAllocator** pE=ppA+iNumBmas;		// pointer to end of list
+	TInt* pB=iBaseList;						// pointer to list of initial logical bit numbers
+	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;	// need to save this for the case where the best run is the initial one
+		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 (unless exact match already found)
+	if (ppA==pE && carry<minrun)
+		{
+		TInt fpos=base+bmalen-carry;
+		TInt lost=((fpos+alignmask)&~alignmask)-fpos;
+		if (carry-lost>=aLength)
+			{
+			minrun=carry;
+			minrunpos=fpos;
+			}
+		}
+	result = (minrunpos<0) ? minrunpos : ((minrunpos+alignmask)&~alignmask);
+
+	@endcode
+
+
+	@param	aLength		number of consecutive bit positions to allocate.
+	@param	aAlign		logarithm to base 2 of the alignment required.
+	@param	aBase		the alignment of the first bit of this allocator - only significant modulo 2^aAlign.
+	@param	aBestFit	TRUE for best fit allocation strategy, FALSE for first fit.
+	@param	aCarry		carry in/carry out.
+	@param	aRunLength	Holds best run length found so far.  This will be set to KMaxTInt when no
+						suitable run length has been found.  In best fit mode aCarry should also be
+						checked as aRunLength will not be set if aCarry is the only suitable run length
+						found.
+	
+	@return	Start position, if a suitable run was found;
+	        KErrNotFound, if no suitable run was found;
+	        KErrOverflow, if all positions free and best fit mode, or if all positions free 
+			in first fit mode and length requested > number of positions available.
+
+	@see	TBitMapAllocator::AllocConsecutive(TInt aLength, TBool aBestFit)
+	@see	TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit)
+ */
+EXPORT_C TInt TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit, TInt& aCarry, TInt& aRunLength) const
+	{
+	return AllocAligned(aLength, aAlign, aBase, aBestFit, aCarry, aRunLength, 0);
+	}
+
+
+/**	Allocates the next available bit position starting from the specified offset.
+
+	Note - If no free bit positions can be found after aOffset this method will
+	wrap around and continue the search from the start of the bit map.
+
+	@param aOffset	The offset from the start of the bit map.
+	@return	The number of the bit position allocated, -1 if all positions are occupied.
+ */
+EXPORT_C TInt TBitMapAllocator::AllocFrom(TUint aOffset)
+	{
+	__ASSERT_ALWAYS(aOffset < (TUint)iSize, TBMA_FAULT());
+
+	if (!iAvail)
+		return -1;
+	--iAvail;
+	const TUint32* pEnd = iMap + ((iSize+31)>>5);
+	TUint32* pW = iMap + (aOffset >> 5);
+	// Only check the bits after aOffset in this word.
+	TUint wordMask = 0xffffffffu >> (aOffset & 0x1f);
+	#ifdef _DEBUG
+	if(!((aOffset&0x1f)==0 || (wordMask&0x80000000u)==0)) // check compiler has done unsigned >>
+		TBMA_FAULT();
+	#endif
+	TUint word = *pW & wordMask;
+	// No free bit positions in this word so search through the rest of the words.
+	while (!word)
+		{
+		++pW;
+		if (pW >= pEnd)
+			pW = iMap;
+		word = *pW;
+		}
+	TInt n = __e32_find_ms1_32(word);
+	*pW &= ~(1 << n);
+	n = (31 - n) + ((pW - iMap) << 5);
+	return n;
+	}
+
+
+#if !defined( __TBMA_MACHINE_CODED__) | defined(__EABI_CTORS__)
+/**	Constructs a new TBitMapAllocator object.
+
+	@param	aSize The number of bit positions required.
+	@param	aState	TRUE if all bit positions initially free;
+					FALSE if all bit positions initially allocated.
+ */
+EXPORT_C TBitMapAllocator::TBitMapAllocator(TInt aSize, TBool aState)
+	{
+	__ASSERT_ALWAYS(aSize>0, TBMA_FAULT());
+	iSize=aSize;
+	if (aState)
+		{
+		iCheckFirst=iMap;
+		iAvail=aSize;
+		TUint32* pW=iMap;
+		for (; aSize>=32; aSize-=32)
+			*pW++=0xffffffff;
+		if (aSize)
+			*pW=((0xffffffffu)<<(32-aSize));
+		}
+	else
+		{
+		TInt nmapw=(aSize+31)>>5;
+		iAvail=0;
+		iCheckFirst=iMap+nmapw-1;
+		memclr(iMap, nmapw*sizeof(TUint32));
+		}
+	}
+#endif
+
+
+#if !defined( __TBMA_MACHINE_CODED__)
+/**	Allocates the next available bit position.
+
+	@return	Number of position allocated, -1 if all positions occupied.
+ */
+EXPORT_C TInt TBitMapAllocator::Alloc()
+	{
+	if (!iAvail)
+		return -1;
+	--iAvail;
+	TUint32* pW=iCheckFirst;
+	while (!*pW)
+		++pW;
+	iCheckFirst=pW;
+	TInt n=__e32_find_ms1_32(*pW);
+	*pW &= ~(1<<n);
+	n=(31-n)+((pW-iMap)<<5);
+	return n;
+	}
+
+
+/**	Frees the specified bit position.
+
+	@param	aPos Number of bit position to be freed; must be currently allocated.
+ */
+EXPORT_C void TBitMapAllocator::Free(TInt aPos)
+	{
+	__ASSERT_ALWAYS(TUint(aPos)<TUint(iSize), TBMA_FAULT());
+	TUint32* pW=iMap+(aPos>>5);
+	TUint32 b=0x80000000u>>(aPos&31);
+	__ASSERT_ALWAYS(!(*pW & b), TBMA_FAULT());
+	*pW |= b;
+	++iAvail;
+	if (pW<iCheckFirst)
+		iCheckFirst=pW;
+	}
+
+
+/**	Allocates a specific range of bit positions.
+
+	The specified range must lie within the total range for this allocator and all
+	the positions must currently be free.
+
+	@param	aStart	First position to allocate.
+	@param	aLength	Number of consecutive positions to allocate, must be >0.
+ */
+EXPORT_C void TBitMapAllocator::Alloc(TInt aStart, TInt aLength)
+	{
+	__ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT());
+	__ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT());
+	__ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT());
+	TInt wix=aStart>>5;
+	TInt sbit=aStart&31;
+	TUint32* pW=iMap+wix;
+	iAvail-=aLength;
+	TInt ebit=sbit+aLength;
+	if (ebit<32)
+		{
+		TUint32 b=(~(0xffffffffu>>aLength)>>sbit);
+		TUint32 w=*pW;
+		__ASSERT_ALWAYS((w|b)==w, TBMA_FAULT());
+		*pW=w&~b;
+		return;
+		}
+	TUint32 b=(0xffffffffu>>sbit);
+	while (ebit>0)
+		{
+		TUint32 w=*pW;
+		__ASSERT_ALWAYS((w|b)==w, TBMA_FAULT());
+		*pW++=w&~b;
+		b=0xffffffffu;
+		ebit-=32;
+		if (ebit<32)
+			b=~(b>>ebit);
+		}
+	}
+
+
+/**	Frees a specific range of bit positions.
+
+	The specified range must lie within the total range for this allocator and all
+	the positions must currently be allocated.
+
+	@param	aStart	First position to free.
+	@param	aLength	Number of consecutive positions to free, must be >0.
+ */
+EXPORT_C void TBitMapAllocator::Free(TInt aStart, TInt aLength)
+	{
+	__ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT());
+	__ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT());
+	__ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT());
+	TInt wix=aStart>>5;
+	TInt sbit=aStart&31;
+	TUint32* pW=iMap+wix;
+	if (!iAvail || pW<iCheckFirst)
+		iCheckFirst=pW;
+	iAvail+=aLength;
+	TInt ebit=sbit+aLength;
+	if (ebit<32)
+		{
+		TUint32 b=(~(0xffffffffu>>aLength)>>sbit);
+		TUint32 w=*pW;
+		__ASSERT_ALWAYS((w&b)==0, TBMA_FAULT());
+		*pW=w|b;
+		return;
+		}
+	TUint32 b=(0xffffffffu>>sbit);
+	while (ebit>0)
+		{
+		TUint32 w=*pW;
+		__ASSERT_ALWAYS((w&b)==0, TBMA_FAULT());
+		*pW++=w|b;
+		b=0xffffffffu;
+		ebit-=32;
+		if (ebit<32)
+			b=~(b>>ebit);
+		}
+	}
+
+
+/**	Frees a specific range of bit positions.
+	
+	The specified range must lie within the total range for this allocator but it is
+	not necessary that all the positions are currently allocated.
+
+	@param	aStart	First position to free.
+	@param	aLength	Number of consecutive positions to free, must be >0.
+ */
+EXPORT_C void TBitMapAllocator::SelectiveFree(TInt aStart, TInt aLength)
+	{
+	__ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT());
+	__ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT());
+	__ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT());
+	TInt wix=aStart>>5;
+	TInt sbit=aStart&31;
+	TUint32* pW=iMap+wix;
+	if (!iAvail || pW<iCheckFirst)
+		iCheckFirst=pW;
+	iAvail+=aLength;	// update free count assuming no positions already free
+	TInt ebit=sbit+aLength;
+	if (ebit<32)
+		{
+		TUint32 b=(~(0xffffffffu>>aLength)>>sbit);
+		TUint32 w=*pW;
+		*pW=w|b;		// mark all positions free
+		iAvail-=__e32_bit_count_32(w&b);	// reduce free count by number of positions already free
+		return;
+		}
+	TUint32 b=(0xffffffffu>>sbit);
+	while (ebit>0)
+		{
+		TUint32 w=*pW;
+		*pW++=w|b;		// mark all positions free
+		iAvail-=__e32_bit_count_32(w&b);	// reduce free count by number of positions already free
+		b=0xffffffffu;
+		ebit-=32;
+		if (ebit<32)
+			b=~(b>>ebit);
+		}
+	}
+
+
+/**	Tests whether a specific range of bit positions are all free.
+
+	The specified range must lie within the total range for this allocator.
+
+	@param	aStart	First position to check.
+	@param	aLength	Number of consecutive positions to check, must be >0.
+	
+	@return	FALSE if all positions free, TRUE if at least one is occupied.
+ */
+EXPORT_C TBool TBitMapAllocator::NotFree(TInt aStart, TInt aLength) const
+	{
+	// Inverse logic - returns 0 if all positions free, nonzero otherwise
+	__ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT());
+	__ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT());
+	__ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT());
+	TInt wix=aStart>>5;
+	TInt sbit=aStart&31;
+	const TUint32* pW=iMap+wix;
+	TInt ebit=sbit+aLength;
+	if (ebit<32)
+		{
+		TUint32 b=(~(0xffffffffu>>aLength)>>sbit);
+		return (*pW^b)&b;
+		}
+	TUint32 b=(0xffffffffu>>sbit);
+	TUint32 r=0;
+	while (ebit>0)
+		{
+		r|=((*pW++^b)&b);
+		b=0xffffffffu;
+		ebit-=32;
+		if (ebit<32)
+			b=~(b>>ebit);
+		}
+	return r;
+	}
+
+
+/**	Tests whether a specific range of bit positions are all occupied.
+
+	The specified range must lie within the total range for this allocator.
+
+	@param	aStart	First position to check.
+	@param	aLength	Number of consecutive positions to check, must be >0.
+	
+	@return	FALSE if all positions occupied, TRUE if at least one is free.
+ */
+EXPORT_C TBool TBitMapAllocator::NotAllocated(TInt aStart, TInt aLength) const
+	{
+	// Inverse logic - returns 0 if all positions allocated, nonzero otherwise
+	__ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT());
+	__ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT());
+	__ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT());
+	TInt wix=aStart>>5;
+	TInt sbit=aStart&31;
+	const TUint32* pW=iMap+wix;
+	TInt ebit=sbit+aLength;
+	if (ebit<32)
+		{
+		TUint32 b=(~(0xffffffffu>>aLength)>>sbit);
+		return *pW&b;
+		}
+	TUint32 b=(0xffffffffu>>sbit);
+	TUint32 r=0;
+	while (ebit>0)
+		{
+		r|=(*pW++&b);
+		b=0xffffffffu;
+		ebit-=32;
+		if (ebit<32)
+			b=~(b>>ebit);
+		}
+	return r;
+	}
+
+
+/**	Allocates up to a specified number of available bit positions.
+
+	The allocated positions are not required to bear any relationship to
+	each other.
+	If the number of free positions is less than the number requested,
+	allocate all currently free positions.
+
+	@param	aLength	Maximum number of positions to allocate.
+	@param	aList	Pointer to memory area where allocated bit numbers should be stored.
+
+	@return	The number of positions allocated.
+ */
+EXPORT_C TInt TBitMapAllocator::AllocList(TInt aLength, TInt* aList)
+	{
+	__ASSERT_ALWAYS(aLength>0, TBMA_FAULT());
+	if (aLength>iAvail)
+		aLength=iAvail;
+	TInt c=aLength;
+	while (c--)
+		*aList++=Alloc();
+	return aLength;
+	}
+
+
+/**	Finds a set of consecutive bit positions with specified alignment starting the 
+	search from the specfied bit position offset, with support for chaining 
+	multiple allocators.
+	
+	For further details see:
+	TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit, TInt& aCarry, TInt& aRunLength)
+
+	@param	aLength		number of consecutive bit positions to allocate.
+	@param	aAlign		logarithm to base 2 of the alignment required.
+	@param	aBase		the alignment of the first bit of this allocator - only significant modulo 2^aAlign.
+	@param	aBestFit	TRUE for best fit allocation strategy, FALSE for first fit.
+	@param	aCarry		carry in/carry out.
+	@param	aRunLength	Holds best run length found so far.  This will be set to KMaxTInt when no
+						suitable run length has been found.  In best fit mode aCarry should also be
+						checked as aRunLength will not be set if aCarry is the only suitable run length
+						found.
+	@param	aOffset		The bit position to start the search from, set to 0 to search all bit positions.
+						aOffset will be aligned so all bits before an aligned aOffset will be
+						ignored.  This can only be non-zero if aCarry is zero as any carry in bits will be
+						ignored if aOffset is non-zero.
+	
+	@return	Start position, if a suitable run was found;
+	        KErrNotFound, if no suitable run was found;
+	        KErrOverflow, if all positions free and best fit mode, or if all positions free 
+			in first fit mode and length requested > number of positions available.
+
+	@see TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit, TInt& aCarry, TInt& aRunLength)
+ */
+EXPORT_C TInt TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit, TInt& aCarry, TInt& aRunLength, TUint aOffset) const
+	{
+	TInt minrl=KMaxTInt;
+	__ASSERT_ALWAYS(aLength>0, TBMA_FAULT());
+	__ASSERT_ALWAYS(TUint(aAlign)<31, TBMA_FAULT());
+	__ASSERT_ALWAYS(aOffset < (TUint)iSize, TBMA_FAULT());
+	__ASSERT_ALWAYS(!aCarry || !aOffset, TBMA_FAULT());
+	TUint32 alignsize=1<<aAlign;
+	TUint32 alignmask=alignsize-1;
+	aBase&=alignmask;
+	if (iAvail==iSize)
+		{
+		// Align aOffset if it is set so we ignore all bits before the aligned offset.
+		aOffset = (!aOffset)? aOffset : ((aOffset + aBase + alignmask) & ~alignmask) - aBase;
+		TInt runLength = (aOffset < (TUint)iSize)? iSize - aOffset : 0;
+		if (!aBestFit)
+			{
+			TInt alignedStartPos = ((aOffset - aCarry + aBase + alignmask) & ~alignmask) - aBase;
+			TInt lost = alignedStartPos - (aOffset - aCarry);
+			if (runLength + aCarry - lost >= aLength)
+				{
+				aRunLength = runLength;
+				if (alignedStartPos >= 0)
+					{
+					aCarry=0;	// clear carry if not initial run
+					}
+				return (alignedStartPos >= 0)? alignedStartPos : 0; // return start pos of exact run
+				}
+			}
+		if (aOffset)
+			aCarry = runLength;
+		else
+			aCarry += iAvail;
+		aRunLength = KMaxTInt;
+		return KErrOverflow;
+		}
+	const TUint32* pW=aCarry?iMap:iCheckFirst;
+	const TUint32* pE=iMap+((iSize+31)>>5);
+	TInt n=((pW-iMap)<<5);
+	TInt p=-1;
+	TInt q=-aCarry;
+	TUint32 s=aCarry?~0:0;	// 0 when searching for 1's, FFFFFFFF when searching for 0's
+
+	TUint32 offsetMask = 0;
+	if (aOffset)
+		{// Start search from aOffset.  Only align aOffset if aOffset is to
+		// be used otherwise the best fit mode may fail as aligning aOffset
+		// may cause the search to skip past parts of the bit map.
+		aOffset = ((aOffset + aBase + alignmask) & ~alignmask) - aBase;
+		const TUint32* offsetWord = iMap + (aOffset >> 5);
+		if (offsetWord >= pW)
+			{
+			pW = offsetWord;
+			n = aOffset & 0xffffffe0;
+			offsetMask = 0xffffffff >> (aOffset & 31);
+			__ASSERT_ALWAYS(offsetMask, TBMA_FAULT());
+			}
+		}
+	while (pW<pE)
+		{
+		TUint32 word = *pW++;
+		if (offsetMask)
+			{// Start search after bit aOffset.
+			word &= offsetMask; // Mask off any bits before the aOffset
+			offsetMask = 0;		// Reset so future iterations use whole of next word.
+			}
+		if (word==s)		// check if any of required bit present
+			{
+			n+=32;			// if not, step bit number on by 32
+			continue;
+			}
+		TInt rl=-1;
+		for (TUint32 b=0x80000000; b; ++n, b>>=1)
+			{
+			if ((word ^ s) & b)
+				{
+				if (s && n==iSize)
+					break;	// reached end
+				// bit found - invert search bit
+				s=~s;
+				if (s)
+					q=n;	// 1 found so save position
+				else
+					{
+					rl=n-q;	// 0 found, calculate run length of 1's
+					TInt alignedStartPos = ((q + aBase + alignmask) & ~alignmask) - aBase;
+					TInt lost = alignedStartPos - q;
+					if (rl-lost>=aLength)
+						{
+						if (!aBestFit || rl==aLength)
+							{
+							// first fit or exact match - we're finished
+							if (alignedStartPos >= 0)
+								{
+								aCarry=0;	// clear carry if not initial run
+								}
+							aRunLength=rl;
+							return (alignedStartPos >= 0)? alignedStartPos : 0;
+							}
+						if (rl<minrl)
+							{
+							// best fit and this run is smallest so far, so record its position and length
+							minrl=rl;
+							p = (alignedStartPos >= 0)? alignedStartPos : 0;
+							}
+						}
+					}
+				}
+			}
+		}
+	if (minrl!=aLength)
+		{
+		// exact match not found or first fit and no match found
+		TInt rl=0;
+		if (s)
+			{
+			// we were looking for 0, so this counts as a run
+			// get run length
+			rl=n-q;
+			if (!aBestFit)
+				{
+				TInt alignedStartPos = ((q + aBase + alignmask) & ~alignmask) - aBase;
+				TInt lost = alignedStartPos - q;
+				if (rl-lost>=aLength)
+					{// BMA is not totally empty so this can't be the initial run
+					// and the final run.  Therefore the start pos must be within
+					// this bma so clear carry and return start pos.
+					aCarry=0;
+					aRunLength=rl;
+					return alignedStartPos;
+					}
+				}
+			}
+		aCarry=rl;	// set carry to length of final run or 0 if none
+		}
+	aRunLength=minrl;	// return best run length found
+	return p;		// return start position of run or -1 if run not found
+	}
+#endif
+
+
+/** Finds a set of consecutive free positions on a single bit map allocator.
+
+	@param	aLength		number of consecutive bit positions to allocate.
+	@param	aBestFit	TRUE for best fit allocation strategy, FALSE for first fit.
+	
+	@return	Start position, if a suitable run was found;
+	        KErrNotFound, if no suitable run was found.
+ */
+EXPORT_C TInt TBitMapAllocator::AllocConsecutive(TInt aLength, TBool aBestFit) const
+	{
+	TInt carry=0;
+	TInt l=KMaxTInt;
+	TInt r=AllocAligned(aLength,0,0,aBestFit,carry,l);
+	if (aBestFit)
+		{
+		// must check final run if any
+		if (carry>=aLength && carry<l)
+			r=iSize-carry;
+		}
+	if (r<0)
+		r=KErrNotFound;
+	return r;
+	}
+
+
+/** Finds a set of consecutive free positions on a single bit map allocator with
+	specified alignment.
+
+	@param	aLength		number of consecutive bit positions to allocate.
+	@param	aAlign		logarithm to base 2 of the alignment required.
+	@param	aBase		the alignment of the first bit of this allocator - only significant modulo 2^aAlign.
+	@param	aBestFit	TRUE for best fit allocation strategy, FALSE for first fit.
+	
+	@return	Start position, if a suitable run was found;
+	        KErrNotFound, if no suitable run was found.
+ */
+EXPORT_C TInt TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit) const
+	{
+	TInt carry=0;
+	TInt l=KMaxTInt;
+	TUint32 alignsize=1<<aAlign;
+	TUint32 alignmask=alignsize-1;
+	aBase&=alignmask;
+	TInt r=AllocAligned(aLength,aAlign,aBase,aBestFit,carry,l);
+	if (aBestFit)
+		{
+		// must check final run if any
+		TInt fpos=iSize-carry;
+		TInt lost=((fpos+aBase+alignmask)&~alignmask)-aBase-fpos;
+		if (carry-lost>=aLength && carry<l)
+			r=fpos+lost;
+		}
+	if (r<0)
+		r=KErrNotFound;
+	else
+		r=((r+aBase+alignmask)&~alignmask)-aBase;
+	return r;
+	}
+
+
+/** Copies a range from another allocator, mark remainder as occupied.
+
+	Values of bit positions from aFirst to aFirst+aLen-1 inclusive in allocator
+	aA are copied to bit positions in this allocator starting with aFirst mod 32.
+	Remaining bit positions in this allocator are marked as occupied.
+
+	@param	aA		Pointer to source allocator.
+	@param	aFirst	Number in source allocator of first bit to copy.
+	@param	aLen	Number of bits to copy from source allocator.
+ */
+EXPORT_C void TBitMapAllocator::CopyAlignedRange(const TBitMapAllocator* aA, TInt aFirst, TInt aLen)
+	{
+	const TUint32* srcptr = aA->iMap + (aFirst>>5);
+	TInt last = aFirst + aLen - 1;
+	TInt len = (((last+32)&~31)-(aFirst&~31))>>3;	// bytes
+	__ASSERT_ALWAYS(len<=iSize, TBMA_FAULT());
+	TInt remain = ((iSize+31)&~31)-(len<<3);
+	wordmove(iMap, srcptr, len);
+	memclr(iMap+(len>>2), remain>>3);
+	TUint32* p = iMap;
+	TUint32* pE = p + (len>>2);
+	*p &= (0xffffffffu >> (aFirst&31));
+	pE[-1] &= (0xffffffffu << (31-(last&31)));
+	iCheckFirst = pE-1;
+	iAvail = 0;
+	for (; p<pE; ++p)
+		{
+		TUint32 x = *p;
+		if (x)
+			{
+			if (p<iCheckFirst)
+				iCheckFirst = p;
+			iAvail += __e32_bit_count_32(x);
+			}
+		}
+	}