// 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);

 			}

 		}

 	}