// 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.

 */