--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/kerneltest/e32test/buffer/t_tbma.cpp Thu Dec 17 09:24:54 2009 +0200
@@ -0,0 +1,1256 @@
+// Copyright (c) 1995-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:
+// e32test\buffer\t_tbma.cpp
+//
+//
+
+#define __E32TEST_EXTENSION__
+#include "t_tbma.h"
+#include <cpudefs.h>
+#include <e32atomics.h>
+
+RTest test(_L("T_TBMA"));
+
+
+/**************************************
+ * class TBmaList
+ **************************************/
+
+TBmaList* TBmaList::New(TInt aNumBmas)
+ {
+ TBmaList* pL=new TBmaList;
+ if (pL)
+ {
+ pL->iNumBmas=aNumBmas;
+ pL->iBmaList=(TBitMapAllocator**)User::Alloc(aNumBmas*sizeof(TBitMapAllocator*));
+ if (pL->iBmaList)
+ Mem::FillZ(pL->iBmaList, aNumBmas*sizeof(TBitMapAllocator*));
+ pL->iBaseList=(TInt*)User::Alloc((aNumBmas+1)*sizeof(TInt));
+ if (!pL->iBmaList || !pL->iBaseList)
+ {
+ delete pL;
+ pL=NULL;
+ }
+ }
+ return pL;
+ }
+
+TBmaList* TBmaList::New(const TBitMapAllocator& aBma, TInt aNumSplits, VA_LIST aList)
+ {
+ TBmaList* pL=TBmaList::New(aNumSplits+1);
+ if (!pL)
+ return NULL;
+ TInt i;
+ pL->iBaseList[0]=0;
+ for (i=1; i<=aNumSplits; ++i)
+ pL->iBaseList[i]=VA_ARG(aList,TInt);
+ pL->iBaseList[aNumSplits+1]=aBma.iSize;
+ for (i=0; i<=aNumSplits; ++i)
+ {
+ TInt sz=pL->iBaseList[i+1]-pL->iBaseList[i];
+ __ASSERT_ALWAYS(sz>0, TBMA_FAULT());
+ pL->iBmaList[i]=TBitMapAllocator::New(sz,EFalse);
+ if (!pL->iBmaList[i])
+ {
+ delete pL;
+ return NULL;
+ }
+ TInt j;
+ for (j=0; j<sz; ++j)
+ {
+ if (aBma.NotAllocated(j+pL->iBaseList[i],1))
+ pL->iBmaList[i]->Free(j);
+ }
+ }
+ return pL;
+ }
+
+TBmaList::TBmaList()
+ {
+ iNumBmas=0;
+ iBmaList=NULL;
+ iBaseList=NULL;
+ }
+
+TBmaList::~TBmaList()
+ {
+ TInt i;
+ for (i=0; i<iNumBmas; ++i)
+ delete iBmaList[i];
+ User::Free(iBmaList);
+ User::Free(iBaseList);
+ }
+/*
+ * Extended first fit allocator
+ */
+TInt TBmaList::AllocConsecutiveFF(TInt aLength)
+ {
+ TInt base=KErrNotFound;
+ TInt bmalen=0;
+ TInt carry=0;
+ TBitMapAllocator** ppA=iBmaList; // pointer to list of TBitMapAllocator*
+ TBitMapAllocator** pE=ppA+iNumBmas;
+ TInt* pB=iBaseList;
+ for (; ppA<pE; ++ppA, ++pB)
+ {
+ TBitMapAllocator* pA=*ppA;
+ if (*pB!=base+bmalen)
+ {
+ // this BMA is not contiguous with previous one
+ carry=0;
+ }
+ base=*pB;
+ bmalen=pA->iSize;
+ TInt l;
+ TInt r=pA->AllocAligned(aLength,0,0,EFalse,carry,l);
+ if (r>=0)
+ return base+r-carry;
+ }
+ return KErrNotFound;
+ }
+
+/*
+ * Extended best fit allocator
+ */
+TInt TBmaList::AllocConsecutiveBF(TInt aLength)
+ {
+ TInt bmalen=0;
+ TInt carry=0;
+ TInt minrun=KMaxTInt;
+ TInt minrunpos=KErrNotFound;
+ TBitMapAllocator** ppA=iBmaList; // pointer to list of TBitMapAllocator*
+ TBitMapAllocator** pE=ppA+iNumBmas;
+ TInt* pB=iBaseList;
+ 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)
+ {
+ minrun=carry;
+ minrunpos=base+bmalen-carry;
+ }
+ carry=0;
+ }
+ base=*pB;
+ bmalen=pA->iSize;
+ TInt l=KMaxTInt;
+ TInt oldc=carry;
+ TInt r=pA->AllocAligned(aLength,0,0,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
+ if (ppA==pE && carry>=aLength && carry<minrun)
+ minrunpos=base+bmalen-carry;
+ return minrunpos;
+ }
+
+/*
+ * Extended first fit aligned allocator
+ */
+TInt TBmaList::AllocAlignedFF(TInt aLength, TInt aAlign)
+ {
+ TUint32 alignsize=1<<aAlign;
+ TUint32 alignmask=alignsize-1;
+ TInt base=KErrNotFound;
+ TInt bmalen=0;
+ TInt carry=0;
+ TBitMapAllocator** ppA=iBmaList; // pointer to list of TBitMapAllocator*
+ TBitMapAllocator** pE=ppA+iNumBmas;
+ TInt* pB=iBaseList;
+ for (; ppA<pE; ++ppA, ++pB)
+ {
+ TBitMapAllocator* pA=*ppA;
+ if (*pB!=base+bmalen)
+ {
+ // this BMA is not contiguous with previous one
+ carry=0;
+ }
+ base=*pB;
+ bmalen=pA->iSize;
+ TInt l;
+ TInt r=pA->AllocAligned(aLength,aAlign,base,EFalse,carry,l);
+ if (r>=0)
+ return (base+r-carry+alignmask)&~alignmask;
+ }
+ return KErrNotFound;
+ }
+
+/*
+ * Extended best fit aligned allocator
+ */
+TInt TBmaList::AllocAlignedBF(TInt aLength, TInt aAlign)
+ {
+ TInt bmalen=0;
+ TInt carry=0;
+ TInt minrun=KMaxTInt;
+ TInt minrunpos=KErrNotFound;
+ TUint32 alignsize=1<<aAlign;
+ TUint32 alignmask=alignsize-1;
+ TBitMapAllocator** ppA=iBmaList; // pointer to list of TBitMapAllocator*
+ TBitMapAllocator** pE=ppA+iNumBmas;
+ TInt* pB=iBaseList;
+ 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;
+ 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
+ if (ppA==pE && carry<minrun)
+ {
+ TInt fpos=base+bmalen-carry;
+ TInt lost=((fpos+alignmask)&~alignmask)-fpos;
+ if (carry-lost>=aLength)
+ {
+ minrun=carry;
+ minrunpos=fpos;
+ }
+ }
+ return (minrunpos<0) ? minrunpos : ((minrunpos+alignmask)&~alignmask);
+ }
+
+
+
+
+
+
+
+
+void Display(TBitMapAllocator* aBma)
+ {
+ test.Printf(_L("Free %d FirstCheck %08x Size %d Map %08x\n"),aBma->iAvail,aBma->iCheckFirst,aBma->iSize,aBma->iMap);
+ TInt i;
+ TInt l=0;
+ for (i=0; i<((aBma->iSize+31)>>5); i++)
+ {
+ if (++l==10)
+ {
+ l=0;
+// test.Getch();
+ }
+ TUint32 x=aBma->iMap[i];
+ TBuf<80> buf;
+ buf.NumFixedWidth(x,EBinary,32);
+ buf.Append(_L("\n"));
+ test.Printf(buf);
+ }
+ test.Getch();
+ }
+
+void Check(TBitMapAllocator& a)
+ {
+ TInt l=a.iSize;
+ l=(l+31)>>5;
+ TInt n=0;
+ TInt i;
+ TUint32* first=NULL;
+ for (i=0; i<l; ++i)
+ {
+ TUint32 w=a.iMap[i];
+ if (w && !first)
+ first=a.iMap+i;
+ n+=__e32_bit_count_32(w);
+ }
+ test(a.Avail()==n);
+ test(first?(a.iCheckFirst<=first):(a.iCheckFirst>=a.iMap && a.iCheckFirst<=a.iMap+l));
+ }
+
+void TestConstruct(TInt aSize)
+ {
+ test.Printf(_L("TestConstruct %d\n"),aSize);
+ TBitMapAllocator* pA;
+ pA=TBitMapAllocator::New(aSize, EFalse);
+ test(pA!=NULL);
+ test(pA->Avail()==0);
+ Check(*pA);
+ delete pA;
+ pA=TBitMapAllocator::New(aSize, ETrue);
+ test(pA!=NULL);
+ test(pA->Avail()==aSize);
+ Check(*pA);
+ delete pA;
+ }
+
+void TestAlloc1(TInt aSize)
+ {
+ test.Printf(_L("TestAlloc1 %d\n"),aSize);
+ TBitMapAllocator* pA=TBitMapAllocator::New(aSize, ETrue);
+ test(pA!=NULL);
+ test(pA->Avail()==aSize);
+ Check(*pA);
+ TInt i;
+ for (i=0; i<aSize; ++i)
+ {
+ TInt r=pA->Alloc();
+ test(r==i);
+ test(pA->Avail()==aSize-i-1);
+ test(pA->iCheckFirst==pA->iMap+i/32);
+ Check(*pA);
+ }
+ test(pA->Alloc()<0);
+ delete pA;
+ }
+
+void TestFree1(TInt aSize)
+ {
+ test.Printf(_L("TestFree1 %d\n"),aSize);
+ TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);
+ test(pA!=NULL);
+ test(pA->Avail()==0);
+ TInt i;
+ for (i=aSize-1; i>=0; --i)
+ {
+ pA->Free(i);
+ test(pA->Avail()==aSize-i);
+ test(pA->Alloc()==i);
+ pA->Free(i);
+ test(pA->iCheckFirst==pA->iMap+i/32);
+ Check(*pA);
+ }
+ delete pA;
+ }
+
+void TestBlockAlloc(TInt aSize)
+ {
+ test.Printf(_L("TestBlockAlloc %d\n"),aSize);
+ const TInt begin[]={0,1,2,7,16,29,31,32,33,63,64,65,83,128};
+ TBitMapAllocator* pA=TBitMapAllocator::New(aSize, ETrue);
+ test(pA!=NULL);
+ test(pA->Avail()==aSize);
+ pA->Alloc(0,aSize);
+ test(pA->Avail()==0);
+ Check(*pA);
+ pA->Free(0,aSize);
+ test(pA->Avail()==aSize);
+ Check(*pA);
+ TInt i;
+ for (i=0; i<(TInt)(sizeof(begin)/sizeof(TInt)); ++i)
+ {
+ TInt j=begin[i];
+ if (j>aSize)
+ break;
+ TInt l;
+ for (l=1; l<=aSize-j; ++l)
+ {
+// test.Printf(_L("j=%d, l=%d, s=%d\n"),j,l,aSize);
+ pA->Alloc(j,l);
+ test(pA->Avail()==aSize-l);
+ test(!pA->NotAllocated(j,l));
+ if (j+l<aSize)
+ test(pA->NotAllocated(j,l+1));
+ if (j>0)
+ test(pA->NotAllocated(j-1,l));
+ TInt r=pA->Alloc();
+ if (j==0)
+ {
+ if (l<aSize)
+ test(r==l);
+ else
+ test(r<0);
+ }
+ else
+ test(r==0);
+ if (r==0)
+ {
+ pA->Free(r);
+ pA->Free(j,l);
+ }
+ else if (r>0)
+ pA->Free(j,l+1);
+ else
+ pA->Free(j,l);
+ test(pA->Avail()==aSize);
+ Check(*pA);
+ }
+ }
+ delete pA;
+ }
+
+void TestBlockFree(TInt aSize)
+ {
+ test.Printf(_L("TestBlockFree %d\n"),aSize);
+ const TInt begin[]={0,1,2,7,16,29,31,32,33,63,64,65,83,128};
+ TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);
+ test(pA!=NULL);
+ test(pA->Avail()==0);
+ TInt i;
+ for (i=0; i<(TInt)(sizeof(begin)/sizeof(TInt)); ++i)
+ {
+ TInt j=begin[i];
+ if (j>aSize)
+ break;
+ TInt l;
+ for (l=1; l<=aSize-j; ++l)
+ {
+// test.Printf(_L("j=%d, l=%d, s=%d\n"),j,l,aSize);
+ pA->Free(j,l);
+ test(pA->Avail()==l);
+ test(!pA->NotFree(j,l));
+ if (j+l<aSize)
+ test(pA->NotFree(j,l+1));
+ if (j>0)
+ test(pA->NotFree(j-1,l));
+ TInt r=pA->Alloc();
+ test(r==j);
+ if (l>1)
+ pA->Alloc(j+1,l-1);
+ test(pA->Avail()==0);
+ Check(*pA);
+ }
+ }
+ delete pA;
+ }
+
+void TestNotFree(TInt aSize)
+ {
+ test.Printf(_L("TestNotFree %d\n"),aSize);
+ TBitMapAllocator* pA=TBitMapAllocator::New(aSize, ETrue);
+ test(pA!=NULL);
+ test(pA->Avail()==aSize);
+ test(!pA->NotFree(0,aSize));
+ TInt i;
+ for (i=0; i<aSize; ++i)
+ {
+ pA->Alloc(i,1);
+ test(pA->NotFree(0,aSize));
+ TInt j;
+ for (j=1; j*j<=i || j*j+i<=aSize; ++j)
+ {
+ TInt a=Max(i-j*j,0);
+ TInt b=Min(i+j*j,aSize);
+ test(pA->NotFree(a,b-a));
+ }
+ pA->Free(i);
+ test(!pA->NotFree(0,aSize));
+ }
+ const TInt begin[]={0,1,2,7,16,29,31,32,33,63,64,65,83,128};
+ const TInt size[]={2,3,7,16,23,31,32,33,63,64,65,89,128};
+ const TInt* pB=begin;
+ const TInt* pBE=pB+sizeof(begin)/sizeof(TInt);
+ const TInt* pS=size;
+ const TInt* pSE=pS+sizeof(size)/sizeof(TInt);
+ for (; pB<pBE; ++pB)
+ {
+ TInt b=*pB;
+ if (b>=aSize)
+ continue;
+ for (; pS<pSE; ++pS)
+ {
+ TInt l=*pS;
+ if (b+l>aSize)
+ continue;
+ pA->Alloc(b,l);
+ TInt j;
+ for (j=1; j<aSize; ++j)
+ {
+ if (j<=b)
+ test(!pA->NotFree(0,j));
+ else
+ test(pA->NotFree(0,j));
+ if (aSize-j>=b+l)
+ test(!pA->NotFree(aSize-j,j));
+ else
+ test(pA->NotFree(aSize-j,j));
+ }
+ pA->Free(b,l);
+ }
+ }
+ delete pA;
+ }
+
+void TestNotAllocated(TInt aSize)
+ {
+ test.Printf(_L("TestNotAllocated %d\n"),aSize);
+ TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);
+ test(pA!=NULL);
+ test(pA->Avail()==0);
+ test(!pA->NotAllocated(0,aSize));
+ TInt i;
+ for (i=0; i<aSize; ++i)
+ {
+ pA->Free(i);
+ test(pA->NotAllocated(0,aSize));
+ TInt j;
+ for (j=1; j*j<=i || j*j+i<=aSize; ++j)
+ {
+ TInt a=Max(i-j*j,0);
+ TInt b=Min(i+j*j,aSize);
+ test(pA->NotAllocated(a,b-a));
+ }
+ pA->Alloc(i,1);
+ test(!pA->NotAllocated(0,aSize));
+ }
+ const TInt begin[]={0,1,2,7,16,29,31,32,33,63,64,65,83,128};
+ const TInt size[]={2,3,7,16,23,31,32,33,63,64,65,89,128};
+ const TInt* pB=begin;
+ const TInt* pBE=pB+sizeof(begin)/sizeof(TInt);
+ const TInt* pS=size;
+ const TInt* pSE=pS+sizeof(size)/sizeof(TInt);
+ for (; pB<pBE; ++pB)
+ {
+ TInt b=*pB;
+ if (b>=aSize)
+ continue;
+ for (; pS<pSE; ++pS)
+ {
+ TInt l=*pS;
+ if (b+l>aSize)
+ continue;
+ pA->Free(b,l);
+ TInt j;
+ for (j=1; j<aSize; ++j)
+ {
+ if (j<=b)
+ test(!pA->NotAllocated(0,j));
+ else
+ test(pA->NotAllocated(0,j));
+ if (aSize-j>=b+l)
+ test(!pA->NotAllocated(aSize-j,j));
+ else
+ test(pA->NotAllocated(aSize-j,j));
+ }
+ pA->Alloc(b,l);
+ }
+ }
+ delete pA;
+ }
+
+void TestAllocList(TInt aSize)
+ {
+ test.Printf(_L("TestAllocList %d\n"),aSize);
+ TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);
+ test(pA!=NULL);
+ test(pA->Avail()==0);
+ TInt i;
+ TInt list[256];
+ for (i=0; i<aSize; ++i)
+ {
+ pA->Free(i);
+ test(pA->AllocList(128,list)==1);
+ test(list[0]==i);
+ test(pA->Avail()==0);
+ }
+ TInt j;
+ for (i=0; i<aSize-1; ++i)
+ {
+ for (j=i+1; j<aSize; ++j)
+ {
+ pA->Free(i);
+ pA->Free(j);
+ test(pA->AllocList(1,list)==1);
+ test(list[0]==i);
+ test(pA->Avail()==1);
+ pA->Free(i);
+ test(pA->AllocList(128,list)==2);
+ test(list[0]==i && list[1]==j);
+ test(pA->Avail()==0);
+ }
+ }
+ TInt l;
+ for (l=1; l<80; ++l)
+ {
+ if (2*l+1>aSize)
+ break;
+ for (i=l+1; i<=aSize-l; ++i)
+ {
+ pA->Free(0,l);
+ pA->Free(i,l);
+ test(pA->Avail()==2*l);
+ TInt l2;
+ for (l2=Max(l-1,1); l2<=2*l; ++l2)
+ {
+ TInt r=pA->AllocList(l2,list);
+// test.Printf(_L("l2=%d r=%d\n"),l2,r);
+ test(r==l2);
+ for (j=0; j<Min(l2,l); j++)
+ test(list[j]==j);
+ for (j=l; j<l2; j++)
+ test(list[j]==j-l+i);
+ for (j=0; j<l2; ++j)
+ pA->Free(list[j]);
+ pA->SelectiveFree(0,l);
+ pA->SelectiveFree(i,l);
+ test(pA->Avail()==2*l);
+ }
+ pA->Alloc(0,l);
+ pA->Alloc(i,l);
+ Check(*pA);
+ }
+ }
+ delete pA;
+ }
+
+void TestSelectiveFree(TInt aSize)
+ {
+ test.Printf(_L("TestSelectiveFree %d\n"),aSize);
+ TBitMapAllocator* pA=TBitMapAllocator::New(aSize, ETrue);
+ test(pA!=NULL);
+ test(pA->Avail()==aSize);
+ TInt i;
+ TInt j;
+ TInt l;
+ for (i=2; i<8; ++i)
+ {
+ for (l=1; l<=aSize; ++l)
+ {
+ new (pA) TBitMapAllocator(aSize, ETrue);
+ for (j=0; j<aSize; j+=i)
+ pA->Alloc(j,1);
+ TInt orig=pA->Avail();
+ test(orig==aSize-(aSize+i-1)/i);
+ pA->SelectiveFree(0,l);
+ TInt freed=pA->Avail()-orig;
+ test(freed==(l+i-1)/i);
+ Check(*pA);
+ }
+ }
+ for (i=0; i<=Min(32,aSize-1); ++i)
+ {
+ for (l=1; l<=aSize-i; ++l)
+ {
+ for (j=1; j<=aSize; ++j)
+ {
+ new (pA) TBitMapAllocator(aSize, ETrue);
+ pA->Alloc(i,l);
+ test(pA->Avail()==aSize-l);
+ pA->SelectiveFree(0,j);
+ test(pA->Avail()==aSize-l+Max(0,Min(i+l,j)-i));
+ test(!pA->NotFree(0,j));
+ if (j>=i && j<i+l)
+ test(pA->NotFree(0,j+1));
+ Check(*pA);
+ }
+ }
+ }
+ delete pA;
+ }
+
+TBitMapAllocator* DoSetupBMA(TInt aSize, VA_LIST aList)
+ {
+ TBitMapAllocator* pA=TBitMapAllocator::New(aSize, EFalse);
+ test(pA!=NULL);
+ test(pA->Avail()==0);
+ TInt totalfree=0;
+ FOREVER
+ {
+ TInt i=VA_ARG(aList,TInt);
+ if (i<0)
+ break;
+ TInt l=VA_ARG(aList,TInt);
+ pA->Free(i,l);
+ totalfree+=l;
+ }
+ test(pA->Avail()==totalfree);
+ return pA;
+ }
+
+TBitMapAllocator* SetupBMA(TInt aSize, ...)
+ {
+ VA_LIST list;
+ VA_START(list,aSize);
+ return DoSetupBMA(aSize,list);
+ }
+
+void PopulateRangeArray(RArray<SRange>& aArray, VA_LIST aList)
+ {
+ aArray.Reset();
+ TInt n=0;
+ FOREVER
+ {
+ SRange rng;
+ rng.iBase=VA_ARG(aList,TInt);
+ if (rng.iBase<0)
+ break;
+ rng.iLength=VA_ARG(aList,TInt);
+ rng.iLength<<=8;
+ rng.iLength+=n;
+ ++n;
+ test(aArray.Append(rng)==KErrNone);
+ }
+ }
+
+TInt FirstFitPos(RArray<SRange>& aArray, TInt aLength)
+ {
+ TInt c=aArray.Count();
+ SRange* pR=&aArray[0];
+ SRange* pE=pR+c;
+ for (; pR<pE; ++pR)
+ {
+ TInt l=pR->iLength>>8;
+ if (l>=aLength)
+ {
+// test.Printf(_L("FFP %d = %d\n"),aLength,pR->iBase);
+ return pR->iBase;
+ }
+ }
+// test.Printf(_L("FFP %d = -1\n"),aLength);
+ return -1;
+ }
+
+TInt AlignedFirstFitPos(RArray<SRange>& aArray, TInt aSize, TInt aLength, TInt aAlign, TInt aBase, TInt aOffset=0, TBool aBestFit=EFalse)
+ {
+ TInt alignSize=1<<aAlign;
+ TInt alignMask=alignSize-1;
+ TInt minRun=0;
+ TInt minRunStart=0;
+ TBool runFound = EFalse;
+ TInt c=aArray.Count();
+ SRange* pR=&aArray[0];
+ // Best fit mode should ignore any final run TBitMapAllocator will
+ // always ignore the final run in best fit mode and rely on carry being
+ // checked by the caller.
+ SRange* pE = pR + c - 1;
+ if (!aBestFit || aSize > pE->iBase + (pE->iLength >> 8))
+ pE++;
+
+ for (; pR<pE; ++pR)
+ {
+ TInt l=pR->iLength>>8;
+ TInt b=pR->iBase;
+ if (aOffset != 0)
+ {
+ aOffset = ((aOffset + aBase + alignMask) & ~alignMask) - aBase;
+ if (aOffset + aLength - 1 >= b + l)
+ {// The offset is after the end of this region.
+ continue;
+ }
+ l -= (aOffset <= b)? 0 : aOffset - b;
+ b += (aOffset <= b)? 0 : aOffset - b; // Start the search from aOffset
+ }
+ TInt ab=((b+aBase+alignMask)&~alignMask)-aBase;
+ TInt al = l + b - ab;
+ if (al >= aLength)
+ {
+ if (!aBestFit || l == aLength)
+ {
+// test.Printf(_L("AFFP %d %d %d = %d\n"),aLength,aAlign,aBase,ab);
+ return ab;
+ }
+ if (!runFound || minRun > l)
+ {
+ minRun = l;
+ minRunStart = ab;
+ runFound = ETrue;
+ }
+ }
+ }
+ if (runFound)
+ {
+ return minRunStart;
+ }
+// test.Printf(_L("AFFP %d %d %d = -1\n"),aLength,aAlign,aBase);
+ return -1;
+ }
+
+void DoConsecTest(TInt aSize, ...)
+ {
+ test.Printf(_L("DoConsecTest %d\n"),aSize);
+ VA_LIST list;
+ VA_LIST list2;
+ VA_START(list,aSize);
+ VA_START(list2,aSize);
+ TBitMapAllocator* pA=DoSetupBMA(aSize,list2);
+ RArray<SRange> rangeArray(8,_FOFF(SRange,iLength));
+ PopulateRangeArray(rangeArray, list);
+ TInt n;
+ for (n=1; n<=aSize; ++n)
+ {
+ TInt r1=pA->AllocConsecutive(n,EFalse);
+ TInt r2=FirstFitPos(rangeArray,n);
+// test.Printf(_L("ALC(%d,0) = %d [%d]\n"),n,r1,r2);
+ test_Equal(r2, r1);
+ }
+ rangeArray.SortUnsigned(); // sort array in ascending order of length
+ for (n=1; n<=aSize; ++n)
+ {
+ TInt r1=pA->AllocConsecutive(n,ETrue);
+ TInt r2=FirstFitPos(rangeArray,n);
+// test.Printf(_L("ALC(%d,1) = %d [%d]\n"),n,r1,r2);
+ test_Equal(r2, r1);
+ }
+ rangeArray.Close();
+ delete pA;
+ }
+
+void DoAlignedTest(TInt aSize, ...)
+ {
+ test.Printf(_L("DoAlignedTest %d\n"),aSize);
+ VA_LIST list;
+ VA_LIST list2;
+ VA_START(list,aSize);
+ VA_START(list2,aSize);
+ TBitMapAllocator* pA=DoSetupBMA(aSize,list2);
+ RArray<SRange> rangeArray(8,_FOFF(SRange,iLength));
+ PopulateRangeArray(rangeArray, list);
+ TInt finalRunLength = 0;
+ SRange& lastRun = rangeArray[rangeArray.Count() - 1];
+ if (lastRun.iBase + (lastRun.iLength>>8) == aSize)
+ {// The last run is at the end of the bma.
+ finalRunLength = lastRun.iLength >> 8;
+ }
+ TInt a;
+ TInt b;
+ TInt n;
+ TUint offset;
+ for (a=0; ((1<<a)<=aSize); ++a)
+ {
+ TInt alignsize=1<<a;
+ TInt alignmask=alignsize-1;
+ for (b=0; b<(1<<a); ++b)
+ {
+// test.Printf(_L("size %d a=%d b=%d First\n"),aSize,a,b);
+ for (n=1; n<=aSize; ++n)
+ {
+ for (offset = 1; offset < (TUint)aSize; offset <<= 1)
+ {
+ TInt carry = 0;
+ TInt runLength;
+ TInt r1=pA->AllocAligned(n,a,b,EFalse, carry, runLength, offset);
+ TInt r2=AlignedFirstFitPos(rangeArray,aSize, n,a,b, offset);
+ if (r2 < 0 && pA->iSize == pA->iAvail)
+ {// Totally empty bmas return KErrOverflow on failure.
+ r2 = KErrOverflow;
+ }
+// test.Printf(_L("ALA %d %d %d %d 0 = %d [%d]\n"),n,a,b,offset,r1,r2);
+ test( (r1<0) || ((r1+b)&alignmask)==0 );
+ test( (r1<0) || !pA->NotFree(r1,n));
+ test( (r1<0) || runLength >= n);
+ test_Equal(r2, r1);
+ }
+ }
+ }
+ }
+ for (a=0; ((1<<a)<=aSize); ++a)
+ {
+ TInt alignsize=1<<a;
+ TInt alignmask=alignsize-1;
+ for (b=0; b<(1<<a); ++b)
+ {
+// test.Printf(_L("size %d a=%d b=%d Best\n"),aSize,a,b);
+ for (n=1; n<=aSize; ++n)
+ {// test for with offset=0 as that has screwed best fit in past.
+ for (offset = 0; offset < (TUint)aSize; offset <<= 1)
+ {
+ TInt carry = 0;
+ TInt runLength;
+ TInt r1=pA->AllocAligned(n,a,b,ETrue, carry, runLength, offset);
+ TInt r2=AlignedFirstFitPos(rangeArray,aSize, n,a,b, offset, ETrue);
+ if (pA->iSize == pA->iAvail)
+ {// Totally empty bmas return KErrOverflow always on best fit mode.
+ r2 = KErrOverflow;
+ }
+// test.Printf(_L("ALA %d %d %d 1 = %d [%d]\n"),n,a,b,r1,r2);
+ test( (r1<0) || ((r1+b)&alignmask)==0 );
+ test( (r1<0) || !pA->NotFree(r1,n));
+ test( (r1<0) || runLength >= n);
+ test_Equal(r2, r1);
+ // No carry in so if run found then carry should be zero.
+ // If no run found then carry should set to the length of
+ // any run at the end of the bma minus the aligned offset.
+ TInt lost = 0;
+ TInt alignOffset = ((offset + b + alignmask) & ~alignmask) - b;
+ if (finalRunLength && offset && lastRun.iBase < alignOffset)
+ {// This search had started past the start of the final run
+ // so the final run length found will be shorter than its
+ // total length.
+ if (alignOffset < aSize)
+ {
+ lost = Min(alignOffset - lastRun.iBase, finalRunLength);
+ }
+ else // alignedOffset starts past end of bma.
+ lost = finalRunLength;
+ }
+ test((r1>=0 && carry == 0) || carry == finalRunLength - lost);
+ offset = (offset)? offset : 1;
+ }
+ }
+ }
+ }
+ rangeArray.Close();
+ delete pA;
+ }
+
+void Clone(TAny* aDest, const TBitMapAllocator* aSrc)
+ {
+ TInt nmapw=(aSrc->iSize+31)>>5;
+ TInt memsz=sizeof(TBitMapAllocator)+(nmapw-1)*sizeof(TUint32);
+ Mem::Move(aDest,aSrc,memsz);
+ }
+
+void TestAllocConsecutive()
+ {
+ test.Printf(_L("TestAllocConsecutive\n"));
+ DoConsecTest(256, 0,4 , 20,8 , 38,1 , 58,6 , 65,10, 78,16 , 127,72, 222,19 , 244,12 , -1);
+ DoConsecTest(255, 0,2 , 3,2 , 6,3 , 10,3 , 14,5 , 20,5 , 26,7 , 34,7 , 42,11 , 54,11 , 66,13 , 80,37,
+ 118,19 , 138,23 , 162,47 , 254,1 , -1);
+ DoConsecTest(1023, 0,2 , 32,32 , 65,31 , 99,30 , 144,64 , 256,519 , 776,1, 778,245 , -1);
+
+ DoAlignedTest(256, 0,4 , 20,8 , 38,1 , 58,6 , 65,10, 78,16 , 127,72, 222,19 , 244,12 , -1);
+ DoAlignedTest(255, 0,2 , 3,2 , 6,3 , 10,3 , 14,5 , 20,5 , 26,7 , 34,7 , 42,11 , 54,11 , 66,13 , 80,37,
+ 118,19 , 138,23 , 162,47 , 254,1 , -1);
+ DoAlignedTest(1023, 0,2 , 32,32 , 65,31 , 99,30 , 144,64 , 256,519 , 776,1, 778,245 , -1);
+ // Test some completely free bmas
+ DoAlignedTest(255, 0,255, -1);
+ DoAlignedTest(256, 0,256, -1);
+ DoAlignedTest(1023, 0,1023, -1);
+ DoAlignedTest(1024, 0,1024, -1);
+ }
+
+void DoTestChain(const TBitMapAllocator& aBma, TInt aNumSplits, ...)
+ {
+ test.Printf(_L("DoTestChain %d %d\n"),aBma.iSize,aNumSplits);
+ VA_LIST list;
+ VA_START(list,aNumSplits);
+
+ TBmaList* pL=TBmaList::New(aBma,aNumSplits,list);
+ test(pL!=NULL);
+
+ TInt n;
+ for (n=1; n<=aBma.iSize; ++n)
+ {
+ TInt r1=aBma.AllocConsecutive(n,EFalse);
+ TInt r2=pL->AllocConsecutiveFF(n);
+// test.Printf(_L("CHAIN C FF %d: r1=%d r2=%d\n"),n,r1,r2);
+ test(r1==r2);
+ }
+ for (n=1; n<=aBma.iSize; ++n)
+ {
+ TInt r1=aBma.AllocConsecutive(n,ETrue);
+ TInt r2=pL->AllocConsecutiveBF(n);
+// test.Printf(_L("CHAIN C BF %d: r1=%d r2=%d\n"),n,r1,r2);
+ test(r1==r2);
+ }
+
+ TInt a;
+ for (a=0; ((1<<a)<=aBma.iSize); ++a)
+ {
+ for (n=1; n<=aBma.iSize; ++n)
+ {
+ if (n==264 && a==9)
+ {
+ ++n;
+ --n;
+ }
+ TInt r1=aBma.AllocAligned(n,a,0,EFalse);
+ TInt r2=pL->AllocAlignedFF(n,a);
+// test.Printf(_L("CHAIN A FF %d,%d: r1=%d r2=%d\n"),n,a,r1,r2);
+ test(r1==r2);
+ }
+ }
+ for (a=0; ((1<<a)<=aBma.iSize); ++a)
+ {
+ for (n=1; n<=aBma.iSize; ++n)
+ {
+ if (n==240 && a==3)
+ {
+ ++n;
+ --n;
+ }
+ TInt r1=aBma.AllocAligned(n,a,0,ETrue);
+ TInt r2=pL->AllocAlignedBF(n,a);
+// test.Printf(_L("CHAIN A BF %d,%d: r1=%d r2=%d\n"),n,a,r1,r2);
+ test(r1==r2);
+ }
+ }
+
+ delete pL;
+ }
+
+void TestChain()
+ {
+ test.Printf(_L("TestChain\n"));
+ TBitMapAllocator* pA;
+ pA=SetupBMA(1023, 0,2 , 32,32 , 65,31 , 99,30 , 144,64 , 256,519 , 776,1, 778,245 , -1);
+ test(pA!=NULL);
+ DoTestChain(*pA, 2, 300, 700);
+ DoTestChain(*pA, 3, 64, 301, 702);
+ delete pA;
+ pA=SetupBMA(512, 0,2 , 20,10 , 32,32 , 65,31 , 144,64 , 399,113 , -1);
+ test(pA!=NULL);
+ DoTestChain(*pA, 2, 256, 384);
+ DoTestChain(*pA, 3, 128, 256, 384);
+ DoTestChain(*pA, 3, 80, 208, 384);
+ DoTestChain(*pA, 3, 80, 208, 400);
+ delete pA;
+ }
+
+void TestBitOps()
+ {
+ test.Next(_L("Bit operations (32 bit)"));
+ test(__e32_find_ls1_32(0x00000000)==-1);
+ TInt i, j, k;
+ TInt count = 0;
+ for (i=0; i<=31; ++i)
+ test(__e32_find_ls1_32(1u<<i)==i);
+ TUint x = 0;
+ for (i=0; i<1000; ++i)
+ {
+ x = 69069*x + 41;
+ TInt bit = x&31;
+
+ x = 69069*x + 41;
+ TUint y = ((x|1)<<bit);
+
+ test(__e32_find_ls1_32(y) == bit);
+ }
+
+ test(__e32_find_ms1_32(0x00000000)==-1);
+ for (i=0; i<=31; ++i)
+ test(__e32_find_ms1_32(1u<<i)==i);
+ for (i=0; i<1000; ++i)
+ {
+ x = 69069*x + 41;
+ TInt bit = x&31;
+
+ x = 69069*x + 41;
+ TUint y = ((x|0x80000000u)>>bit);
+
+ test(__e32_find_ms1_32(y) == 31-bit);
+ }
+
+ test(__e32_bit_count_32(0)==0);
+ test(__e32_bit_count_32(0xffffffff)==32);
+ for (i=0; i<32; ++i)
+ {
+ TUint32 y = 0xffffffffu << i;
+ TUint32 z = 0xffffffffu >> i;
+ test(__e32_bit_count_32(y) == 32-i);
+ test(__e32_bit_count_32(z) == 32-i);
+ test(__e32_bit_count_32(~y) == i);
+ test(__e32_bit_count_32(~z) == i);
+ }
+ for (i=0; i<32; ++i)
+ for (j=0; j<32; ++j)
+ for (k=0; k<32; ++k)
+ {
+ TUint32 b0 = 1u<<i;
+ TUint32 b1 = 1u<<j;
+ TUint32 b2 = 1u<<k;
+ TUint32 y = b0 | b1 | b2;
+ TInt n;
+ if (i==j && j==k) n=1;
+ else if (i==j || j==k || i==k) n=2;
+ else n=3;
+ test(__e32_bit_count_32(y) == n);
+ test(__e32_bit_count_32(~y) == 32-n);
+ ++count;
+ }
+ test.Printf(_L("%d iterations done\n"), count);
+ for (i=0; i<=31; ++i)
+ {
+ test(__e32_bit_count_32(0xaaaaaaaau<<i)==16-(i+1)/2);
+ test(__e32_bit_count_32(0x55555555u<<i)==16-i/2);
+ }
+ test(__e32_bit_count_32(0x33333333u)==16);
+ test(__e32_bit_count_32(0x88888888u)==8);
+
+ test.Next(_L("Bit operations (64 bit)"));
+ test(__e32_find_ls1_64(0x00000000)==-1);
+ for (i=0; i<=63; ++i)
+ {
+ TUint64 x = 1u;
+ x<<=i;
+ test(__e32_find_ls1_64(x)==i);
+ }
+ x = 487;
+ for (i=0; i<1000; ++i)
+ {
+ x = 69069*x + 41;
+ TInt bit = x&63;
+
+ x = 69069*x + 41;
+ TUint32 xl = x|1;
+ x = 69069*x + 41;
+ TUint32 xh = x;
+ TUint64 y = MAKE_TUINT64(xh,xl);
+ y <<= bit;
+ test(__e32_find_ls1_64(y) == bit);
+ }
+
+ test(__e32_find_ms1_64(0x00000000)==-1);
+ for (i=0; i<=63; ++i)
+ {
+ TUint64 x = 1u;
+ x<<=i;
+ test(__e32_find_ms1_64(x)==i);
+ }
+ x = 1039;
+ for (i=0; i<1000; ++i)
+ {
+ x = 69069*x + 41;
+ TInt bit = x&63;
+
+ x = 69069*x + 41;
+ TUint32 xl = x;
+ x = 69069*x + 41;
+ TUint32 xh = x|0x80000000u;
+ TUint64 y = MAKE_TUINT64(xh,xl);
+ y >>= bit;
+ test(__e32_find_ms1_64(y) == 63-bit);
+ }
+
+ test(__e32_bit_count_64(0)==0);
+ test(__e32_bit_count_64(MAKE_TUINT64(0x00000000,0xffffffff))==32);
+ test(__e32_bit_count_64(MAKE_TUINT64(0xffffffff,0x00000000))==32);
+ test(__e32_bit_count_64(MAKE_TUINT64(0xffffffff,0xffffffff))==64);
+ for (i=0; i<64; ++i)
+ {
+ TUint64 y = MAKE_TUINT64(0xffffffff,0xffffffff);
+ TUint64 z = y >> i;
+ y <<= i;
+ test(__e32_bit_count_64(y) == 64-i);
+ test(__e32_bit_count_64(z) == 64-i);
+ test(__e32_bit_count_64(~y) == i);
+ test(__e32_bit_count_64(~z) == i);
+ }
+ count = 0;
+ for (i=0; i<64; ++i)
+ for (j=0; j<64; ++j)
+ for (k=0; k<64; ++k)
+ {
+ TUint64 b0 = 1u;
+ TUint64 b1 = 1u;
+ TUint64 b2 = 1u;
+ b0 <<= i;
+ b1 <<= j;
+ b2 <<= k;
+ TUint64 y = b0 | b1 | b2;
+ TUint64 z = ~y;
+ TInt n;
+ if (i==j && j==k) n=1;
+ else if (i==j || j==k || i==k) n=2;
+ else n=3;
+ test(__e32_bit_count_64(y) == n);
+ test(__e32_bit_count_64(z) == 64-n);
+ ++count;
+ }
+ test.Printf(_L("%d iterations done\n"), count);
+ for (i=0; i<64; ++i)
+ {
+ TUint64 y = MAKE_TUINT64(0xaaaaaaaa,0xaaaaaaaa);
+ TUint64 z = ~y;
+ test(__e32_bit_count_64(y<<i)==32-(i+1)/2);
+ test(__e32_bit_count_64(z<<i)==32-i/2);
+ }
+ test(__e32_bit_count_64(MAKE_TUINT64(0x33333333u,0x33333333u))==32);
+ test(__e32_bit_count_64(MAKE_TUINT64(0x88888888u,0x88888888u))==16);
+ }
+
+GLDEF_C TInt E32Main()
+ {
+ test.Title();
+ __UHEAP_MARK;
+ test.Start(_L("TBitMapAllocator tests"));
+
+ TestBitOps();
+
+ TestConstruct(3);
+ TestConstruct(29);
+ TestConstruct(256);
+ TestConstruct(487);
+
+ TestAlloc1(3);
+ TestAlloc1(29);
+ TestAlloc1(256);
+ TestAlloc1(181);
+
+ TestFree1(3);
+ TestFree1(29);
+ TestFree1(256);
+ TestFree1(181);
+
+ TestBlockAlloc(3);
+ TestBlockAlloc(29);
+ TestBlockAlloc(256);
+ TestBlockAlloc(179);
+
+ TestBlockFree(3);
+ TestBlockFree(31);
+ TestBlockFree(256);
+ TestBlockFree(149);
+
+ TestNotFree(3);
+ TestNotFree(31);
+ TestNotFree(256);
+ TestNotFree(149);
+
+ TestNotAllocated(3);
+ TestNotAllocated(31);
+ TestNotAllocated(256);
+ TestNotAllocated(149);
+
+ TestAllocList(3);
+ TestAllocList(31);
+ TestAllocList(128);
+ TestAllocList(149);
+
+ TestSelectiveFree(3);
+ TestSelectiveFree(31);
+ TestSelectiveFree(128);
+ TestSelectiveFree(149);
+
+ TestAllocConsecutive();
+
+ TestChain();
+
+ __UHEAP_MARKEND;
+ test.End();
+ return 0;
+ }