1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/kernelhwsrv/kernel/eka/euser/cbase/ub_bma.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,571 @@
1.4 +// Copyright (c) 1997-2009 Nokia Corporation and/or its subsidiary(-ies).
1.5 +// All rights reserved.
1.6 +// This component and the accompanying materials are made available
1.7 +// under the terms of the License "Eclipse Public License v1.0"
1.8 +// which accompanies this distribution, and is available
1.9 +// at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.10 +//
1.11 +// Initial Contributors:
1.12 +// Nokia Corporation - initial contribution.
1.13 +//
1.14 +// Contributors:
1.15 +//
1.16 +// Description:
1.17 +// e32\euser\cbase\ub_bma.cpp
1.18 +//
1.19 +//
1.20 +
1.21 +#include "ub_std.h"
1.22 +
1.23 +const TInt KBitsPerInt=32;
1.24 +const TInt KBitsPerIntMask=(KBitsPerInt-1);
1.25 +const TInt KBitsPerIntShift=5;
1.26 +
1.27 +
1.28 +inline TInt FindLeastSignificantZero(register TUint n)
1.29 + {
1.30 + register TInt i=0;
1.31 + n=~n;
1.32 + if (n<<16==0) n>>=16, i+=16;
1.33 + if (n<<24==0) n>>=8, i+=8;
1.34 + if (n<<28==0) n>>=4, i+=4;
1.35 + if (n<<30==0) n>>=2, i+=2;
1.36 + if (n<<31==0) n>>=1, i+=1;
1.37 + return i;
1.38 + }
1.39 +
1.40 +inline TInt FindLeastSignificantZero(register TUint n, TUint aFrom)
1.41 + {
1.42 + n |= ((1<<aFrom)-1);
1.43 + return FindLeastSignificantZero(n);
1.44 + }
1.45 +
1.46 +inline TInt FindLeastSignificantOne(register TUint n)
1.47 + {
1.48 + register TInt i=0;
1.49 + if (n<<16==0) n>>=16, i+=16;
1.50 + if (n<<24==0) n>>=8, i+=8;
1.51 + if (n<<28==0) n>>=4, i+=4;
1.52 + if (n<<30==0) n>>=2, i+=2;
1.53 + if (n<<31==0) n>>=1, i+=1;
1.54 + return i;
1.55 + }
1.56 +
1.57 +inline TInt FindMostSignificantZero(register TUint n)
1.58 + {
1.59 + register TInt i=31;
1.60 + n=~n;
1.61 + if (n<0x00010000) n<<=16, i-=16;
1.62 + if (n<0x01000000) n<<=8, i-=8;
1.63 + if (n<0x10000000) n<<=4, i-=4;
1.64 + if (n<0x40000000) n<<=2, i-=2;
1.65 + if (n<0x80000000) n<<=1, i-=1;
1.66 + return i;
1.67 + }
1.68 +
1.69 +EXPORT_C CBitMapAllocator::CBitMapAllocator(TInt aSize,TInt aLength)
1.70 +//
1.71 +// Constructor
1.72 +//
1.73 + : iAvail(aSize),iSize(aSize),iLength(aLength)
1.74 + {
1.75 + TInt rem=aSize&KBitsPerIntMask;
1.76 + if (rem)
1.77 + {
1.78 + TInt last=(aSize-1)>>KBitsPerIntShift;
1.79 + iMap[last]=0xFFFFFFFFu<<rem;
1.80 + }
1.81 + }
1.82 +
1.83 +EXPORT_C CBitMapAllocator::~CBitMapAllocator()
1.84 +//
1.85 +// Destructor
1.86 +//
1.87 + {
1.88 + }
1.89 +
1.90 +EXPORT_C CBitMapAllocator *CBitMapAllocator::New(TInt aSize)
1.91 +//
1.92 +// Create a new bit map allocator.
1.93 +//
1.94 + {
1.95 + __ASSERT_ALWAYS(aSize>0,Panic(EBmaSizeLessOrEqualToZero));
1.96 + TInt sz=((aSize+KBitsPerIntMask)>>KBitsPerIntShift)-1;
1.97 + return(new(sz*sizeof(TUint)) CBitMapAllocator(aSize,sz+1));
1.98 + }
1.99 +
1.100 +EXPORT_C CBitMapAllocator *CBitMapAllocator::NewL(TInt aSize)
1.101 +//
1.102 +// Create a new bit map allocator. Leave on any error.
1.103 +//
1.104 + {
1.105 + CBitMapAllocator *pA=New(aSize);
1.106 + User::LeaveIfNull(pA);
1.107 + return(pA);
1.108 + }
1.109 +
1.110 +EXPORT_C TInt CBitMapAllocator::Alloc()
1.111 +//
1.112 +// Allocate the next position.
1.113 +//
1.114 + {
1.115 + if (iAvail)
1.116 + {
1.117 + TUint *pS=iMap;
1.118 + TUint *pE=pS+iLength;
1.119 + do {
1.120 + register TUint n=*pS++;
1.121 + if (n!=0xFFFFFFFFu)
1.122 + {
1.123 + iAvail--;
1.124 + TInt bit=FindLeastSignificantZero(n);
1.125 + *--pS=n|(1<<bit);
1.126 + return((TInt(pS-iMap)<<KBitsPerIntShift)+bit);
1.127 + }
1.128 + } while(pS<pE);
1.129 + Panic(EBmaInconsistentState);
1.130 + }
1.131 + return(KErrNoMemory);
1.132 + }
1.133 +
1.134 +EXPORT_C TInt CBitMapAllocator::AllocFrom(TInt aPos)
1.135 +//
1.136 +// Allocate the next position after aPos.
1.137 +//
1.138 + {
1.139 + __ASSERT_ALWAYS((aPos>=0 && aPos<iSize),Panic(EBmaAllocFromOutOfRange));
1.140 + if (iAvail)
1.141 + {
1.142 + TUint *pS=iMap+(aPos>>KBitsPerIntShift);
1.143 + TUint *pE=iMap+iLength;
1.144 + TInt start=aPos&KBitsPerIntMask;
1.145 + register TUint n;
1.146 + if (start)
1.147 + {
1.148 + n=*pS++ | ~(0xFFFFFFFFu<<start);
1.149 + if (n!=0xFFFFFFFFu)
1.150 + goto found;
1.151 + }
1.152 + while(pS<pE)
1.153 + {
1.154 + n=*pS++;
1.155 + if (n!=0xFFFFFFFFu)
1.156 + {
1.157 +found:
1.158 + iAvail--;
1.159 + TInt bit=FindLeastSignificantZero(n);
1.160 + *--pS |= (1<<bit);
1.161 + return((TInt(pS-iMap)<<KBitsPerIntShift)+bit);
1.162 + }
1.163 + }
1.164 + }
1.165 + return(KErrNoMemory);
1.166 + }
1.167 +
1.168 +EXPORT_C TInt CBitMapAllocator::AllocFromTop()
1.169 +//
1.170 +// Allocate the next position.
1.171 +//
1.172 + {
1.173 + if (iAvail)
1.174 + {
1.175 + TUint *pS=iMap;
1.176 + TUint *pE=pS+iLength;
1.177 + do {
1.178 + register TUint n=*--pE;
1.179 + if (n!=0xFFFFFFFFu)
1.180 + {
1.181 + iAvail--;
1.182 + TInt bit=FindMostSignificantZero(n);
1.183 + *pE=n|(1<<bit);
1.184 + return((TInt(pE-pS)<<KBitsPerIntShift)+bit);
1.185 + }
1.186 + } while(pE>pS);
1.187 + Panic(EBmaInconsistentState);
1.188 + }
1.189 + return(KErrNoMemory);
1.190 + }
1.191 +
1.192 +EXPORT_C TInt CBitMapAllocator::AllocFromTopFrom(TInt aPos)
1.193 +//
1.194 +// Allocate the next position after aPos.
1.195 +//
1.196 + {
1.197 + __ASSERT_ALWAYS((aPos>=0 && aPos<iSize),Panic(EBmaAllocFromTopFromOutOfRange));
1.198 + if (iAvail)
1.199 + {
1.200 + TUint *pS=iMap;
1.201 + TUint *pE=pS+((aPos+1)>>KBitsPerIntShift);
1.202 + TInt start=(aPos+1)&KBitsPerIntMask;
1.203 + register TUint n;
1.204 + if (start)
1.205 + {
1.206 + n=*pE | (0xFFFFFFFFu<<start);
1.207 + if (n!=0xFFFFFFFFu)
1.208 + goto found;
1.209 + }
1.210 + while(pE>pS)
1.211 + {
1.212 + n=*--pE;
1.213 + if (n!=0xFFFFFFFFu)
1.214 + {
1.215 +found:
1.216 + iAvail--;
1.217 + TInt bit=FindMostSignificantZero(n);
1.218 + *pE|=(1<<bit);
1.219 + return((TInt(pE-pS)<<KBitsPerIntShift)+bit);
1.220 + }
1.221 + }
1.222 + }
1.223 + return(KErrNoMemory);
1.224 + }
1.225 +
1.226 +EXPORT_C TInt CBitMapAllocator::Alloc(TInt aCount, TInt& aConsecutive)
1.227 + {
1.228 + __ASSERT_ALWAYS((aCount>0),Panic(EBmaAllocCountNegative));
1.229 + TInt initPos;
1.230 + if (iAvail)
1.231 + {
1.232 + TUint *pS=iMap;
1.233 + TUint *pE=pS+iLength;
1.234 + register TUint n;
1.235 + do {
1.236 + n=*pS++;
1.237 + if (n!=0xFFFFFFFFu)
1.238 + goto found;
1.239 + } while(pS<pE);
1.240 + Panic(EBmaInconsistentState);
1.241 +found:
1.242 + register TInt c;
1.243 + pS--;
1.244 + TInt bit=FindLeastSignificantZero(n);
1.245 + initPos=(TInt(pS-iMap)<<KBitsPerIntShift)+bit;
1.246 + n>>=bit;
1.247 + if (n)
1.248 + {
1.249 + c=FindLeastSignificantOne(n);
1.250 + if (aCount<c) c=aCount;
1.251 + *pS |= ~(0xFFFFFFFFu<<c)<<bit;
1.252 + iAvail-=c;
1.253 + aConsecutive=c;
1.254 + return initPos;
1.255 + }
1.256 + c=KBitsPerInt-bit;
1.257 + if (c>=aCount)
1.258 + {
1.259 + c=aCount;
1.260 + if (c<KBitsPerInt)
1.261 + *pS |= ~(0xFFFFFFFFu<<c)<<bit;
1.262 + else
1.263 + *pS |= 0xFFFFFFFFu<<bit;
1.264 + iAvail-=c;
1.265 + aConsecutive=c;
1.266 + return initPos;
1.267 + }
1.268 + c=aCount-c;
1.269 + *pS=0xFFFFFFFFu;
1.270 + while(++pS<pE && (n=*pS)==0 && c>=KBitsPerInt)
1.271 + *pS=0xFFFFFFFFu, c-=KBitsPerInt;
1.272 + if (c && pS<pE && n!=0xFFFFFFFFu)
1.273 + {
1.274 + bit=n?FindLeastSignificantOne(n):KBitsPerInt;
1.275 + if (bit>c) bit=c;
1.276 + *pS |= ~(0xFFFFFFFFu<<bit);
1.277 + c-=bit;
1.278 + }
1.279 + aConsecutive=aCount-c;
1.280 + iAvail-=aConsecutive;
1.281 + return initPos;
1.282 + }
1.283 + aConsecutive=0;
1.284 + return KErrNoMemory;
1.285 + }
1.286 +
1.287 +LOCAL_D const TUint AlignedSearchMask[] =
1.288 + {0x00000000,0xAAAAAAAA,0xEEEEEEEE,0xFEFEFEFE,0xFFFEFFFE};
1.289 +
1.290 +EXPORT_C TInt CBitMapAllocator::AllocAligned(TInt anAlignment)
1.291 + {
1.292 + __ASSERT_ALWAYS((anAlignment>=0 && anAlignment<32),Panic(EBmaAllAlgnOutOfRange));
1.293 + if (iAvail==0)
1.294 + return KErrNoMemory;
1.295 + TUint mask;
1.296 + TInt step;
1.297 + if (anAlignment>=KBitsPerIntShift)
1.298 + {
1.299 + mask=0xFFFFFFFEu;
1.300 + step=1<<(anAlignment-KBitsPerIntShift);
1.301 + }
1.302 + else
1.303 + {
1.304 + mask=AlignedSearchMask[anAlignment];
1.305 + step=1;
1.306 + }
1.307 + TUint *pM=iMap;
1.308 + TUint *pE=pM+iLength;
1.309 + do {
1.310 + register TUint n=*pM | mask;
1.311 + if (n!=0xFFFFFFFFu)
1.312 + {
1.313 + iAvail--;
1.314 + TInt bit=(mask==0xFFFFFFFEu)?0:FindLeastSignificantZero(n);
1.315 + *pM |= (1<<bit);
1.316 + return((TInt(pM-iMap)<<KBitsPerIntShift)+bit);
1.317 + }
1.318 + pM+=step;
1.319 + } while(pM<pE);
1.320 + return KErrNoMemory;
1.321 + }
1.322 +
1.323 +EXPORT_C TInt CBitMapAllocator::AllocAlignedBlock(TInt anAlignment)
1.324 + {
1.325 + __ASSERT_ALWAYS((anAlignment>=0 && anAlignment<32),Panic(EBmaAllAlgnBOutOfRange));
1.326 + if (iAvail==0)
1.327 + return KErrNoMemory;
1.328 + TInt blocksz=1<<anAlignment;
1.329 + TUint mask;
1.330 + TUint block;
1.331 + TInt step;
1.332 + if (anAlignment>=KBitsPerIntShift)
1.333 + {
1.334 + mask=0xFFFFFFFEu;
1.335 + step=1<<(anAlignment-KBitsPerIntShift);
1.336 + block=0xFFFFFFFFu;
1.337 + }
1.338 + else
1.339 + {
1.340 + mask=AlignedSearchMask[anAlignment];
1.341 + step=1;
1.342 + block=~(0xFFFFFFFFu<<blocksz);
1.343 + }
1.344 + TUint *pM=iMap;
1.345 + TUint *pE=pM+iLength;
1.346 + do {
1.347 + register TUint n=*pM | mask;
1.348 + if (n!=0xFFFFFFFFu)
1.349 + {
1.350 + if (blocksz>=KBitsPerInt)
1.351 + {
1.352 + n=0;
1.353 + TUint *pS=pM+step;
1.354 + if (pS<=pE)
1.355 + {
1.356 + do n|=*pM++; while(pM<pS);
1.357 + pM-=step;
1.358 + if (n==0)
1.359 + {
1.360 + iAvail-=blocksz;
1.361 + do *pM++=0xFFFFFFFFu; while(pM<pS);
1.362 + pM-=step;
1.363 + return (TInt(pM-iMap)<<KBitsPerIntShift);
1.364 + }
1.365 + }
1.366 + }
1.367 + else
1.368 + {
1.369 + TInt bit=FindLeastSignificantZero(n);
1.370 + mask=block<<bit;
1.371 + n=*pM;
1.372 + do {
1.373 + if ((n&mask)==0)
1.374 + {
1.375 + *pM |= mask;
1.376 + iAvail-=blocksz;
1.377 + return((TInt(pM-iMap)<<KBitsPerIntShift)+bit);
1.378 + }
1.379 + bit+=blocksz;
1.380 + mask<<=blocksz;
1.381 + } while(mask);
1.382 + }
1.383 + }
1.384 + pM+=step;
1.385 + } while(pM<pE);
1.386 + return KErrNoMemory;
1.387 + }
1.388 +
1.389 +EXPORT_C void CBitMapAllocator::AllocAt(TInt aPos)
1.390 +//
1.391 +// Allocate a required position.
1.392 +//
1.393 + {
1.394 + __ASSERT_ALWAYS(aPos>=0 && aPos<iSize,Panic(EBmaAllocOutOfRange));
1.395 + TUint *pM=iMap+(aPos>>KBitsPerIntShift);
1.396 + TUint mask=1<<(aPos&KBitsPerIntMask);
1.397 + __ASSERT_ALWAYS(!(*pM&mask),Panic(EBmaAllocAtAlreadyAllocated));
1.398 + *pM |= mask;
1.399 + iAvail--;
1.400 + }
1.401 +
1.402 +EXPORT_C void CBitMapAllocator::AllocAt(TInt aPos, TInt aCount)
1.403 + {
1.404 + __ASSERT_ALWAYS((aPos>=0 && (aPos+aCount)<=iSize),Panic(EBmaAllocBlkOutOfRange));
1.405 + TUint *pM=iMap+(aPos>>KBitsPerIntShift);
1.406 + TInt c=aPos&KBitsPerIntMask;
1.407 + TUint m;
1.408 + if (aCount<(KBitsPerInt-c))
1.409 + {
1.410 + m=~(0xFFFFFFFFu<<aCount)<<c;
1.411 + if (*pM & m)
1.412 + Panic(EBmaAllocBlkNotFree);
1.413 + *pM |= m;
1.414 + iAvail-=aCount;
1.415 + return;
1.416 + }
1.417 + m=0xFFFFFFFFu<<c;
1.418 + if (*pM & m)
1.419 + Panic(EBmaAllocBlkNotFree);
1.420 + *pM++ |= m;
1.421 + c=aCount-KBitsPerInt+c;
1.422 + while(c>=KBitsPerInt)
1.423 + {
1.424 + if (*pM)
1.425 + Panic(EBmaAllocBlkNotFree);
1.426 + *pM++=0xFFFFFFFFu;
1.427 + c-=KBitsPerInt;
1.428 + }
1.429 + if (c)
1.430 + {
1.431 + m=0xFFFFFFFFu>>(KBitsPerInt-c);
1.432 + if (*pM & m)
1.433 + Panic(EBmaAllocBlkNotFree);
1.434 + *pM++ |= m;
1.435 + }
1.436 + iAvail-=aCount;
1.437 + }
1.438 +
1.439 +EXPORT_C TInt CBitMapAllocator::ExtractRamPages(TInt aConsecutive,TInt& aPageNo)
1.440 + {
1.441 + if(iAvail<aConsecutive)
1.442 + return KErrNoMemory;
1.443 +
1.444 + TUint *pS=iMap;
1.445 + TUint *pE=pS+iLength;
1.446 +
1.447 + do {
1.448 + register TUint n=*pS++;
1.449 + if (n!=0xFFFFFFFFu)
1.450 + {
1.451 + TInt x = 0;
1.452 + do
1.453 + {
1.454 + TInt bit=FindLeastSignificantZero(n,x);
1.455 + TInt pos=(TInt((pS-1)-iMap)<<KBitsPerIntShift)+bit;
1.456 + if(pos+aConsecutive > iSize)
1.457 + return KErrNoMemory;
1.458 + if(IsFree(pos,aConsecutive))
1.459 + {
1.460 + AllocAt(pos,aConsecutive);
1.461 + aPageNo=pos;
1.462 + return KErrNone;
1.463 + }
1.464 + else
1.465 + {
1.466 + x = bit+2;
1.467 + }
1.468 + }
1.469 + while (x < KBitsPerInt);
1.470 + }
1.471 + } while(pS<pE);
1.472 + return KErrNoMemory;
1.473 + }
1.474 +
1.475 +EXPORT_C TBool CBitMapAllocator::IsFree(TInt aPos)
1.476 +//
1.477 +// Check a required position is available
1.478 +//
1.479 + {
1.480 + __ASSERT_ALWAYS(aPos>=0 && aPos<iSize,Panic(EBmaFreeOutOfRange));
1.481 + TUint n=iMap[aPos>>KBitsPerIntShift];
1.482 + return !(n>>(aPos&KBitsPerIntMask)&1);
1.483 + }
1.484 +
1.485 +EXPORT_C TBool CBitMapAllocator::IsFree(TInt aPos, TInt aCount)
1.486 + {
1.487 + __ASSERT_ALWAYS((aPos>=0 && (aPos+aCount)<=iSize),Panic(EBmaChkBlkOutOfRange));
1.488 + TUint *pM=iMap+(aPos>>KBitsPerIntShift);
1.489 + TUint m=*pM++;
1.490 + TInt c=aPos&KBitsPerIntMask;
1.491 + m>>=c;
1.492 + if (aCount<(KBitsPerInt-c))
1.493 + {
1.494 + return !(m&~(0xFFFFFFFFu<<aCount));
1.495 + }
1.496 + aCount-=(KBitsPerInt-c);
1.497 + while(aCount>=KBitsPerInt)
1.498 + {
1.499 + m |= *pM++;
1.500 + aCount-=KBitsPerInt;
1.501 + }
1.502 + if (aCount)
1.503 + {
1.504 + m|=(*pM<<(KBitsPerInt-aCount));
1.505 + }
1.506 + return(!m);
1.507 + }
1.508 +
1.509 +EXPORT_C void CBitMapAllocator::Free(TInt aPos)
1.510 +//
1.511 +// Free a position.
1.512 +//
1.513 + {
1.514 + __ASSERT_ALWAYS(aPos>=0 && aPos<iSize,Panic(EBmaFreeOutOfRange));
1.515 + TUint *pM=iMap+(aPos>>KBitsPerIntShift);
1.516 + TUint mask=1<<(aPos&KBitsPerIntMask);
1.517 + __ASSERT_ALWAYS((*pM&mask),Panic(EBmaFreeNotAllocated));
1.518 + *pM &= ~mask;
1.519 + iAvail++;
1.520 + }
1.521 +
1.522 +EXPORT_C void CBitMapAllocator::Free(TInt aPos, TInt aCount)
1.523 + {
1.524 + __ASSERT_ALWAYS((aPos>=0 && (aPos+aCount)<=iSize),Panic(EBmaFreeBlkOutOfRange));
1.525 + TUint *pM=iMap+(aPos>>KBitsPerIntShift);
1.526 + TInt c=aPos&KBitsPerIntMask;
1.527 + TUint m;
1.528 + if (aCount<(KBitsPerInt-c))
1.529 + {
1.530 + m=~(0xFFFFFFFFu<<aCount)<<c;
1.531 + if ((*pM & m)!=m)
1.532 + Panic(EBmaFreeBlkNotAllocated);
1.533 + *pM &= ~m;
1.534 + iAvail+=aCount;
1.535 + return;
1.536 + }
1.537 + m=0xFFFFFFFFu<<c;
1.538 + if ((*pM & m)!=m)
1.539 + Panic(EBmaFreeBlkNotAllocated);
1.540 + *pM++ &= ~m;
1.541 + c=aCount-KBitsPerInt+c;
1.542 + while(c>=KBitsPerInt)
1.543 + {
1.544 + if (*pM!=0xFFFFFFFF)
1.545 + Panic(EBmaFreeBlkNotAllocated);
1.546 + *pM++=0;
1.547 + c-=KBitsPerInt;
1.548 + }
1.549 + if (c)
1.550 + {
1.551 + m=0xFFFFFFFFu>>(KBitsPerInt-c);
1.552 + if ((*pM & m)!=m)
1.553 + Panic(EBmaFreeBlkNotAllocated);
1.554 + *pM++ &= ~m;
1.555 + }
1.556 + iAvail+=aCount;
1.557 + }
1.558 +
1.559 +EXPORT_C TInt CBitMapAllocator::Avail()
1.560 +//
1.561 +// Get the available blocks count.
1.562 +//
1.563 + {
1.564 + return(iAvail);
1.565 + }
1.566 +
1.567 +EXPORT_C TInt CBitMapAllocator::Size()
1.568 +//
1.569 +// Get the size of all available blocks.
1.570 +//
1.571 + {
1.572 + return(iSize);
1.573 + }
1.574 +