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