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