1 // Copyright (c) 1997-2009 Nokia Corporation and/or its subsidiary(-ies).

     2 // All rights reserved.

     3 // This component and the accompanying materials are made available

     4 // under the terms of the License "Eclipse Public License v1.0"

     5 // which accompanies this distribution, and is available

     6 // at the URL "http://www.eclipse.org/legal/epl-v10.html".

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 // e32\euser\cbase\ub_bma.cpp

    15 // 

    16 //

    17 

    18 #include "ub_std.h"

    19 

    20 const TInt KBitsPerInt=32;

    21 const TInt KBitsPerIntMask=(KBitsPerInt-1);

    22 const TInt KBitsPerIntShift=5;

    23 

    24 

    25 inline TInt FindLeastSignificantZero(register TUint n)

    26 	{

    27 	register TInt i=0;

    28 	n=~n;

    29 	if (n<<16==0) n>>=16, i+=16;

    30 	if (n<<24==0) n>>=8, i+=8;

    31 	if (n<<28==0) n>>=4, i+=4;

    32 	if (n<<30==0) n>>=2, i+=2;

    33 	if (n<<31==0) n>>=1, i+=1;

    34 	return i;

    35 	}

    36 

    37 inline TInt FindLeastSignificantZero(register TUint n, TUint aFrom)

    38 	{

    39 	n |= ((1<<aFrom)-1);

    40 	return FindLeastSignificantZero(n);

    41 	}

    42 

    43 inline TInt FindLeastSignificantOne(register TUint n)

    44 	{

    45 	register TInt i=0;

    46 	if (n<<16==0) n>>=16, i+=16;

    47 	if (n<<24==0) n>>=8, i+=8;

    48 	if (n<<28==0) n>>=4, i+=4;

    49 	if (n<<30==0) n>>=2, i+=2;

    50 	if (n<<31==0) n>>=1, i+=1;

    51 	return i;

    52 	}

    53 

    54 inline TInt FindMostSignificantZero(register TUint n)

    55 	{

    56 	register TInt i=31;

    57 	n=~n;

    58 	if (n<0x00010000) n<<=16, i-=16;

    59 	if (n<0x01000000) n<<=8, i-=8;

    60 	if (n<0x10000000) n<<=4, i-=4;

    61 	if (n<0x40000000) n<<=2, i-=2;

    62 	if (n<0x80000000) n<<=1, i-=1;

    63 	return i;

    64 	}

    65 

    66 EXPORT_C CBitMapAllocator::CBitMapAllocator(TInt aSize,TInt aLength)

    67 //

    68 // Constructor

    69 //

    70 	: iAvail(aSize),iSize(aSize),iLength(aLength)

    71 	{

    72 	TInt rem=aSize&KBitsPerIntMask;

    73 	if (rem)

    74 		{

    75 		TInt last=(aSize-1)>>KBitsPerIntShift;

    76 		iMap[last]=0xFFFFFFFFu<<rem;

    77 		}

    78 	}

    79 

    80 EXPORT_C CBitMapAllocator::~CBitMapAllocator()

    81 //

    82 // Destructor

    83 //

    84 	{

    85 	}

    86 

    87 EXPORT_C CBitMapAllocator *CBitMapAllocator::New(TInt aSize)

    88 //

    89 // Create a new bit map allocator.

    90 //

    91 	{

    92 	__ASSERT_ALWAYS(aSize>0,Panic(EBmaSizeLessOrEqualToZero));

    93 	TInt sz=((aSize+KBitsPerIntMask)>>KBitsPerIntShift)-1;

    94 	return(new(sz*sizeof(TUint)) CBitMapAllocator(aSize,sz+1));

    95 	}

    96 

    97 EXPORT_C CBitMapAllocator *CBitMapAllocator::NewL(TInt aSize)

    98 //

    99 // Create a new bit map allocator. Leave on any error.

   100 //

   101 	{

   102 	CBitMapAllocator *pA=New(aSize);

   103 	User::LeaveIfNull(pA);

   104 	return(pA);

   105 	}

   106 

   107 EXPORT_C TInt CBitMapAllocator::Alloc()

   108 //

   109 // Allocate the next position.

   110 //

   111 	{

   112 	if (iAvail)

   113 		{

   114 		TUint *pS=iMap;

   115 		TUint *pE=pS+iLength;

   116 		do	{

   117 			register TUint n=*pS++;

   118 			if (n!=0xFFFFFFFFu)

   119 				{

   120 				iAvail--;

   121 				TInt bit=FindLeastSignificantZero(n);

   122 				*--pS=n|(1<<bit);

   123 				return((TInt(pS-iMap)<<KBitsPerIntShift)+bit);

   124 				}

   125 			} while(pS<pE);

   126 		Panic(EBmaInconsistentState);

   127 		}

   128 	return(KErrNoMemory);

   129 	}

   130 

   131 EXPORT_C TInt CBitMapAllocator::AllocFrom(TInt aPos)

   132 //

   133 // Allocate the next position after aPos.

   134 //

   135 	{

   136 	__ASSERT_ALWAYS((aPos>=0 && aPos<iSize),Panic(EBmaAllocFromOutOfRange));

   137 	if (iAvail)

   138 		{

   139 		TUint *pS=iMap+(aPos>>KBitsPerIntShift);

   140 		TUint *pE=iMap+iLength;

   141 		TInt start=aPos&KBitsPerIntMask;

   142 		register TUint n;

   143 		if (start)

   144 			{

   145 			n=*pS++ | ~(0xFFFFFFFFu<<start);

   146 			if (n!=0xFFFFFFFFu)

   147 				goto found;

   148 			}

   149 		while(pS<pE)

   150 			{

   151 			n=*pS++;

   152 			if (n!=0xFFFFFFFFu)

   153 				{

   154 found:

   155 				iAvail--;

   156 				TInt bit=FindLeastSignificantZero(n);

   157 				*--pS |= (1<<bit);

   158 				return((TInt(pS-iMap)<<KBitsPerIntShift)+bit);

   159 				}

   160 			}

   161 		}

   162 	return(KErrNoMemory);

   163 	}

   164 

   165 EXPORT_C TInt CBitMapAllocator::AllocFromTop()

   166 //

   167 // Allocate the next position.

   168 //

   169 	{

   170 	if (iAvail)

   171 		{

   172 		TUint *pS=iMap;

   173 		TUint *pE=pS+iLength;

   174 		do	{

   175 			register TUint n=*--pE;

   176 			if (n!=0xFFFFFFFFu)

   177 				{

   178 				iAvail--;

   179 				TInt bit=FindMostSignificantZero(n);

   180 				*pE=n|(1<<bit);

   181 				return((TInt(pE-pS)<<KBitsPerIntShift)+bit);

   182 				}

   183 			} while(pE>pS);

   184 		Panic(EBmaInconsistentState);

   185 		}

   186 	return(KErrNoMemory);

   187 	}

   188 

   189 EXPORT_C TInt CBitMapAllocator::AllocFromTopFrom(TInt aPos)

   190 //

   191 // Allocate the next position after aPos.

   192 //

   193 	{

   194 	__ASSERT_ALWAYS((aPos>=0 && aPos<iSize),Panic(EBmaAllocFromTopFromOutOfRange));

   195 	if (iAvail)

   196 		{

   197 		TUint *pS=iMap;

   198 		TUint *pE=pS+((aPos+1)>>KBitsPerIntShift);

   199 		TInt start=(aPos+1)&KBitsPerIntMask;

   200 		register TUint n;

   201 		if (start)

   202 			{

   203 			n=*pE | (0xFFFFFFFFu<<start);

   204 			if (n!=0xFFFFFFFFu)

   205 				goto found;

   206 			}

   207 		while(pE>pS)

   208 			{

   209 			n=*--pE;

   210 			if (n!=0xFFFFFFFFu)

   211 				{

   212 found:

   213 				iAvail--;

   214 				TInt bit=FindMostSignificantZero(n);

   215 				*pE|=(1<<bit);

   216 				return((TInt(pE-pS)<<KBitsPerIntShift)+bit);

   217 				}

   218 			}

   219 		}

   220 	return(KErrNoMemory);

   221 	}

   222 

   223 EXPORT_C TInt CBitMapAllocator::Alloc(TInt aCount, TInt& aConsecutive)

   224 	{

   225 	__ASSERT_ALWAYS((aCount>0),Panic(EBmaAllocCountNegative));

   226 	TInt initPos;

   227 	if (iAvail)

   228 		{

   229 		TUint *pS=iMap;

   230 		TUint *pE=pS+iLength;

   231 		register TUint n;

   232 		do	{

   233 			n=*pS++;

   234 			if (n!=0xFFFFFFFFu)

   235 				goto found;

   236 			} while(pS<pE);

   237 		Panic(EBmaInconsistentState);

   238 found:

   239 		register TInt c;

   240 		pS--;

   241 		TInt bit=FindLeastSignificantZero(n);

   242 		initPos=(TInt(pS-iMap)<<KBitsPerIntShift)+bit;

   243 		n>>=bit;

   244 		if (n)

   245 			{

   246 			c=FindLeastSignificantOne(n);

   247 			if (aCount<c) c=aCount;

   248 			*pS |= ~(0xFFFFFFFFu<<c)<<bit;

   249 			iAvail-=c;

   250 			aConsecutive=c;

   251 			return initPos;

   252 			}

   253 		c=KBitsPerInt-bit;

   254 		if (c>=aCount)

   255 			{

   256 			c=aCount;

   257 			if (c<KBitsPerInt)

   258 				*pS |= ~(0xFFFFFFFFu<<c)<<bit;

   259 			else

   260 				*pS |= 0xFFFFFFFFu<<bit;

   261 			iAvail-=c;

   262 			aConsecutive=c;

   263 			return initPos;

   264 			}

   265 		c=aCount-c;

   266 		*pS=0xFFFFFFFFu;

   267 		while(++pS<pE && (n=*pS)==0 && c>=KBitsPerInt)

   268 			*pS=0xFFFFFFFFu, c-=KBitsPerInt;

   269 		if (c && pS<pE && n!=0xFFFFFFFFu)

   270 			{

   271 			bit=n?FindLeastSignificantOne(n):KBitsPerInt;

   272 			if (bit>c) bit=c;

   273 			*pS |= ~(0xFFFFFFFFu<<bit);

   274 			c-=bit;

   275 			}

   276 		aConsecutive=aCount-c;

   277 		iAvail-=aConsecutive;

   278 		return initPos;

   279 		}

   280 	aConsecutive=0;

   281 	return KErrNoMemory;

   282 	}

   283 

   284 LOCAL_D const TUint AlignedSearchMask[] =

   285 	{0x00000000,0xAAAAAAAA,0xEEEEEEEE,0xFEFEFEFE,0xFFFEFFFE};

   286 

   287 EXPORT_C TInt CBitMapAllocator::AllocAligned(TInt anAlignment)

   288 	{

   289 	__ASSERT_ALWAYS((anAlignment>=0 && anAlignment<32),Panic(EBmaAllAlgnOutOfRange));

   290 	if (iAvail==0)

   291 		return KErrNoMemory;

   292 	TUint mask;

   293 	TInt step;

   294 	if (anAlignment>=KBitsPerIntShift)

   295 		{

   296 		mask=0xFFFFFFFEu;

   297 		step=1<<(anAlignment-KBitsPerIntShift);

   298 		}

   299 	else

   300 		{

   301 		mask=AlignedSearchMask[anAlignment];

   302 		step=1;

   303 		}

   304 	TUint *pM=iMap;

   305 	TUint *pE=pM+iLength;

   306 	do	{

   307 		register TUint n=*pM | mask;

   308 		if (n!=0xFFFFFFFFu)

   309 			{

   310 			iAvail--;

   311 			TInt bit=(mask==0xFFFFFFFEu)?0:FindLeastSignificantZero(n);

   312 			*pM |= (1<<bit);

   313 			return((TInt(pM-iMap)<<KBitsPerIntShift)+bit);

   314 			}

   315 		pM+=step;

   316 		} while(pM<pE);

   317 	return KErrNoMemory;

   318 	}

   319 

   320 EXPORT_C TInt CBitMapAllocator::AllocAlignedBlock(TInt anAlignment)

   321 	{

   322 	__ASSERT_ALWAYS((anAlignment>=0 && anAlignment<32),Panic(EBmaAllAlgnBOutOfRange));

   323 	if (iAvail==0)

   324 		return KErrNoMemory;

   325 	TInt blocksz=1<<anAlignment;

   326 	TUint mask;

   327 	TUint block;

   328 	TInt step;

   329 	if (anAlignment>=KBitsPerIntShift)

   330 		{

   331 		mask=0xFFFFFFFEu;

   332 		step=1<<(anAlignment-KBitsPerIntShift);

   333 		block=0xFFFFFFFFu;

   334 		}

   335 	else

   336 		{

   337 		mask=AlignedSearchMask[anAlignment];

   338 		step=1;

   339 		block=~(0xFFFFFFFFu<<blocksz);

   340 		}

   341 	TUint *pM=iMap;

   342 	TUint *pE=pM+iLength;

   343 	do	{

   344 		register TUint n=*pM | mask;

   345 		if (n!=0xFFFFFFFFu)

   346 			{

   347 			if (blocksz>=KBitsPerInt)

   348 				{

   349 				n=0;

   350 				TUint *pS=pM+step;

   351 				if (pS<=pE)

   352 					{

   353 					do n|=*pM++; while(pM<pS);

   354 					pM-=step;

   355 					if (n==0)

   356 						{

   357 						iAvail-=blocksz;

   358 						do *pM++=0xFFFFFFFFu; while(pM<pS);

   359 						pM-=step;

   360 						return (TInt(pM-iMap)<<KBitsPerIntShift);

   361 						}

   362 					}

   363 				}

   364 			else

   365 				{

   366 				TInt bit=FindLeastSignificantZero(n);

   367 				mask=block<<bit;

   368 				n=*pM;

   369 				do	{

   370 					if ((n&mask)==0)

   371 						{

   372 						*pM |= mask;

   373 						iAvail-=blocksz;

   374 						return((TInt(pM-iMap)<<KBitsPerIntShift)+bit);

   375 						}

   376 					bit+=blocksz;

   377 					mask<<=blocksz;

   378 					} while(mask);

   379 				}

   380 			}

   381 		pM+=step;

   382 		} while(pM<pE);

   383 	return KErrNoMemory;

   384 	}

   385 

   386 EXPORT_C void CBitMapAllocator::AllocAt(TInt aPos)

   387 //

   388 // Allocate a required position.

   389 //

   390 	{

   391 	__ASSERT_ALWAYS(aPos>=0 && aPos<iSize,Panic(EBmaAllocOutOfRange));

   392 	TUint *pM=iMap+(aPos>>KBitsPerIntShift);

   393 	TUint mask=1<<(aPos&KBitsPerIntMask);

   394 	__ASSERT_ALWAYS(!(*pM&mask),Panic(EBmaAllocAtAlreadyAllocated));

   395 	*pM |= mask;

   396 	iAvail--;

   397 	}

   398 

   399 EXPORT_C void CBitMapAllocator::AllocAt(TInt aPos, TInt aCount)

   400 	{

   401 	__ASSERT_ALWAYS((aPos>=0 && (aPos+aCount)<=iSize),Panic(EBmaAllocBlkOutOfRange));

   402 	TUint *pM=iMap+(aPos>>KBitsPerIntShift);

   403 	TInt c=aPos&KBitsPerIntMask;

   404 	TUint m;

   405 	if (aCount<(KBitsPerInt-c))

   406 		{

   407 		m=~(0xFFFFFFFFu<<aCount)<<c;

   408 		if (*pM & m)

   409 			Panic(EBmaAllocBlkNotFree);

   410 		*pM |= m;

   411 		iAvail-=aCount;

   412 		return;

   413 		}

   414 	m=0xFFFFFFFFu<<c;

   415 	if (*pM & m)

   416 		Panic(EBmaAllocBlkNotFree);

   417 	*pM++ |= m;

   418 	c=aCount-KBitsPerInt+c;

   419 	while(c>=KBitsPerInt)

   420 		{

   421 		if (*pM)

   422 			Panic(EBmaAllocBlkNotFree);

   423 		*pM++=0xFFFFFFFFu;

   424 		c-=KBitsPerInt;

   425 		}

   426 	if (c)

   427 		{

   428 		m=0xFFFFFFFFu>>(KBitsPerInt-c);

   429 		if (*pM & m)

   430 			Panic(EBmaAllocBlkNotFree);

   431 		*pM++ |= m;

   432 		}

   433 	iAvail-=aCount;

   434 	}

   435 

   436 EXPORT_C TInt CBitMapAllocator::ExtractRamPages(TInt aConsecutive,TInt& aPageNo)

   437 	{

   438 	if(iAvail<aConsecutive)

   439 		return KErrNoMemory;

   440 

   441 	TUint *pS=iMap;

   442 	TUint *pE=pS+iLength;

   443 

   444 	do	{

   445 		register TUint n=*pS++;

   446 		if (n!=0xFFFFFFFFu)

   447 			{

   448 			TInt x = 0;

   449 			do

   450 				{

   451 				TInt bit=FindLeastSignificantZero(n,x);

   452 				TInt pos=(TInt((pS-1)-iMap)<<KBitsPerIntShift)+bit;

   453 				if(pos+aConsecutive > iSize)

   454 					return KErrNoMemory;

   455 				if(IsFree(pos,aConsecutive))

   456 					{

   457 					AllocAt(pos,aConsecutive);

   458 					aPageNo=pos;

   459 					return KErrNone;

   460 					}

   461 				else

   462 					{

   463 					x = bit+2;

   464 					}

   465 				}

   466 			while (x < KBitsPerInt);

   467 			} 

   468 		} while(pS<pE);

   469 	return KErrNoMemory;

   470 	}

   471 

   472 EXPORT_C TBool CBitMapAllocator::IsFree(TInt aPos)

   473 //

   474 // Check a required position is available

   475 //

   476 	{

   477 	__ASSERT_ALWAYS(aPos>=0 && aPos<iSize,Panic(EBmaFreeOutOfRange));

   478 	TUint n=iMap[aPos>>KBitsPerIntShift];

   479 	return !(n>>(aPos&KBitsPerIntMask)&1);

   480 	}

   481 

   482 EXPORT_C TBool CBitMapAllocator::IsFree(TInt aPos, TInt aCount)

   483 	{

   484 	__ASSERT_ALWAYS((aPos>=0 && (aPos+aCount)<=iSize),Panic(EBmaChkBlkOutOfRange));

   485 	TUint *pM=iMap+(aPos>>KBitsPerIntShift);

   486 	TUint m=*pM++;

   487 	TInt c=aPos&KBitsPerIntMask;

   488 	m>>=c;

   489 	if (aCount<(KBitsPerInt-c))

   490 		{

   491 		return !(m&~(0xFFFFFFFFu<<aCount));

   492 		}

   493 	aCount-=(KBitsPerInt-c);

   494 	while(aCount>=KBitsPerInt)

   495 		{

   496 		m |= *pM++;

   497 		aCount-=KBitsPerInt;

   498 		}

   499 	if (aCount)

   500 		{

   501 		m|=(*pM<<(KBitsPerInt-aCount));

   502 		}

   503 	return(!m);

   504 	}

   505 

   506 EXPORT_C void CBitMapAllocator::Free(TInt aPos)

   507 //

   508 // Free a position.

   509 //

   510 	{

   511 	__ASSERT_ALWAYS(aPos>=0 && aPos<iSize,Panic(EBmaFreeOutOfRange));

   512 	TUint *pM=iMap+(aPos>>KBitsPerIntShift);

   513 	TUint mask=1<<(aPos&KBitsPerIntMask);

   514 	__ASSERT_ALWAYS((*pM&mask),Panic(EBmaFreeNotAllocated));

   515 	*pM &= ~mask;

   516 	iAvail++;

   517 	}

   518 

   519 EXPORT_C void CBitMapAllocator::Free(TInt aPos, TInt aCount)

   520 	{

   521 	__ASSERT_ALWAYS((aPos>=0 && (aPos+aCount)<=iSize),Panic(EBmaFreeBlkOutOfRange));

   522 	TUint *pM=iMap+(aPos>>KBitsPerIntShift);

   523 	TInt c=aPos&KBitsPerIntMask;

   524 	TUint m;

   525 	if (aCount<(KBitsPerInt-c))

   526 		{

   527 		m=~(0xFFFFFFFFu<<aCount)<<c;

   528 		if ((*pM & m)!=m)

   529 			Panic(EBmaFreeBlkNotAllocated);

   530 		*pM &= ~m;

   531 		iAvail+=aCount;

   532 		return;

   533 		}

   534 	m=0xFFFFFFFFu<<c;

   535 	if ((*pM & m)!=m)

   536 		Panic(EBmaFreeBlkNotAllocated);

   537 	*pM++ &= ~m;

   538 	c=aCount-KBitsPerInt+c;

   539 	while(c>=KBitsPerInt)

   540 		{

   541 		if (*pM!=0xFFFFFFFF)

   542 			Panic(EBmaFreeBlkNotAllocated);

   543 		*pM++=0;

   544 		c-=KBitsPerInt;

   545 		}

   546 	if (c)

   547 		{

   548 		m=0xFFFFFFFFu>>(KBitsPerInt-c);

   549 		if ((*pM & m)!=m)

   550 			Panic(EBmaFreeBlkNotAllocated);

   551 		*pM++ &= ~m;

   552 		}

   553 	iAvail+=aCount;

   554 	}

   555 

   556 EXPORT_C TInt CBitMapAllocator::Avail()

   557 //

   558 // Get the available blocks count.

   559 //

   560 	{

   561 	return(iAvail);

   562 	}

   563 

   564 EXPORT_C TInt CBitMapAllocator::Size()

   565 //

   566 // Get the size of all available blocks.

   567 //

   568 	{

   569 	return(iSize);

   570 	}

   571