|
1 // Copyright (c) 1994-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\klib\bma.cpp |
|
15 // This file is directly included in the test harness t_tbma |
|
16 // |
|
17 // |
|
18 |
|
19 #include <kernel/kbma.h> |
|
20 |
|
21 #ifdef TBMA_TEST_CODE |
|
22 |
|
23 #ifdef __MARM__ |
|
24 #define __TBMA_MACHINE_CODED__ |
|
25 #endif |
|
26 |
|
27 #include <e32std.h> |
|
28 #include <e32std_private.h> |
|
29 #include <e32atomics.h> |
|
30 |
|
31 #define __ALLOC(x) User::Alloc(x) |
|
32 |
|
33 void TBmaFault(TInt aLine) |
|
34 { |
|
35 User::Panic(_L("TBMA"),aLine); |
|
36 } |
|
37 |
|
38 #else |
|
39 |
|
40 #include <kernel/kern_priv.h> |
|
41 |
|
42 #define __ALLOC(x) Kern::Alloc(x) |
|
43 |
|
44 void TBmaFault(TInt aLine) |
|
45 { |
|
46 Kern::Fault("TBMA",aLine); |
|
47 } |
|
48 |
|
49 #endif |
|
50 |
|
51 #define TBMA_FAULT() TBmaFault(__LINE__) |
|
52 |
|
53 /** Creates a new TBitMapAllocator object. |
|
54 |
|
55 @param aSize The number of bit positions required, must be >0. |
|
56 @param aState TRUE if all bit positions initially free |
|
57 FALSE if all bit positions initially allocated. |
|
58 |
|
59 @return Pointer to new object, NULL if out of memory. |
|
60 |
|
61 @pre Calling thread must be in a critical section. |
|
62 @pre No fast mutex can be held. |
|
63 @pre Call in a thread context. |
|
64 @pre Interrupts must be enabled. |
|
65 @pre Kernel must be unlocked. |
|
66 */ |
|
67 EXPORT_C TBitMapAllocator* TBitMapAllocator::New(TInt aSize, TBool aState) |
|
68 { |
|
69 #ifndef TBMA_TEST_CODE |
|
70 CHECK_PRECONDITIONS(MASK_THREAD_CRITICAL,"TBitMapAllocator::New"); |
|
71 #endif |
|
72 TInt nmapw=(aSize+31)>>5; |
|
73 TInt memsz=sizeof(TBitMapAllocator)+(nmapw-1)*sizeof(TUint32); |
|
74 TBitMapAllocator* pA=(TBitMapAllocator*)__ALLOC(memsz); |
|
75 if (pA) |
|
76 new(pA) TBitMapAllocator(aSize, aState); |
|
77 return pA; |
|
78 } |
|
79 |
|
80 |
|
81 /** Finds a set of consecutive bit positions with specified alignment, with |
|
82 support for chaining multiple allocators. |
|
83 |
|
84 Note that this function does not mark the positions as allocated. |
|
85 |
|
86 In first fit mode: |
|
87 1. Any initial run is added to the carry in |
|
88 2. If all bits free, if BMA size+carry<=request length return 0 and leave carry alone |
|
89 else add size to carry and return KErrOverflow |
|
90 3. If request satisfied by initial run + carry return 0 and leave carry alone |
|
91 4. If request satisfied by an intermediate or final run, return start pos of run and set carry=0 |
|
92 5. Otherwise carry = length of any final run and return KErrNotFound |
|
93 |
|
94 With a single allocator set aCarry (and usually aBase) to zero and ignore |
|
95 aRunLength. The return value then indicates the required position (after |
|
96 being aligned up as necessary) or KErrNotFound. |
|
97 |
|
98 With multiple allocators, this function should be called on each allocator in |
|
99 increasing logical bit number order. The carry should be set to zero initially |
|
100 and if there is a gap in the logical bit number between two allocators, otherwise |
|
101 it should be left alone. The first call which returns a nonnegative value indicates |
|
102 success and the required logical bit position is given by aligning up |
|
103 logical bit number of first bit of allocator + return value - carry |
|
104 |
|
105 In best fit mode: |
|
106 1. Any initial run is added to the carry in |
|
107 2. If all bits free, add bma length to carry and return KErrOverflow |
|
108 3. If any run including initial+carry but not final has length >= request length |
|
109 return start pos and length of smallest such, also set carry = length of final run |
|
110 unless exact match found, when carry is either unchanged or set to 0 |
|
111 4. If only final run large enough, return KErrNotFound and set carry = length of final run |
|
112 carry=0 if no final run |
|
113 |
|
114 Here is an example of how to use this for multiple allocators: |
|
115 @code |
|
116 // aLength = run length required, aAlign = alignment constraint |
|
117 TInt bmalen=0; |
|
118 TInt carry=0; |
|
119 TInt minrun=KMaxTInt; // this will track the length of the shortest useful run |
|
120 TInt minrunpos=KErrNotFound; // this will track the start position of the shortest useful run |
|
121 TUint32 alignsize=1<<aAlign; |
|
122 TUint32 alignmask=alignsize-1; |
|
123 TBitMapAllocator** ppA=iBmaList; // pointer to list of TBitMapAllocator* |
|
124 TBitMapAllocator** pE=ppA+iNumBmas; // pointer to end of list |
|
125 TInt* pB=iBaseList; // pointer to list of initial logical bit numbers |
|
126 TInt base=*pB; |
|
127 for (; ppA<pE; ++ppA, ++pB) |
|
128 { |
|
129 TBitMapAllocator* pA=*ppA; |
|
130 if (*pB!=base+bmalen) |
|
131 { |
|
132 // this BMA is not contiguous with previous one |
|
133 // check final run of previous BMA |
|
134 if (carry<minrun) |
|
135 { |
|
136 TInt fpos=base+bmalen-carry; |
|
137 TInt lost=((fpos+base+alignmask)&~alignmask)-base-fpos; |
|
138 if (carry-lost>=aLength) |
|
139 { |
|
140 minrun=carry; |
|
141 minrunpos=fpos; |
|
142 } |
|
143 } |
|
144 carry=0; |
|
145 } |
|
146 base=*pB; |
|
147 bmalen=pA->iSize; |
|
148 TInt l=KMaxTInt; |
|
149 TInt oldc=carry; // need to save this for the case where the best run is the initial one |
|
150 TInt r=pA->AllocAligned(aLength,aAlign,base,ETrue,carry,l); |
|
151 if (r>=0) |
|
152 { |
|
153 // check shortest run in this BMA |
|
154 if (l<minrun) |
|
155 { |
|
156 minrun=l; |
|
157 minrunpos=r ? (base+r) : (base-oldc); |
|
158 if (minrun==aLength) |
|
159 break; // exact match so finish |
|
160 } |
|
161 } |
|
162 } |
|
163 // check final run of last BMA (unless exact match already found) |
|
164 if (ppA==pE && carry<minrun) |
|
165 { |
|
166 TInt fpos=base+bmalen-carry; |
|
167 TInt lost=((fpos+alignmask)&~alignmask)-fpos; |
|
168 if (carry-lost>=aLength) |
|
169 { |
|
170 minrun=carry; |
|
171 minrunpos=fpos; |
|
172 } |
|
173 } |
|
174 result = (minrunpos<0) ? minrunpos : ((minrunpos+alignmask)&~alignmask); |
|
175 |
|
176 @endcode |
|
177 |
|
178 |
|
179 @param aLength number of consecutive bit positions to allocate. |
|
180 @param aAlign logarithm to base 2 of the alignment required. |
|
181 @param aBase the alignment of the first bit of this allocator - only significant modulo 2^aAlign. |
|
182 @param aBestFit TRUE for best fit allocation strategy, FALSE for first fit. |
|
183 @param aCarry carry in/carry out. |
|
184 @param aRunLength Holds best run length found so far. This will be set to KMaxTInt when no |
|
185 suitable run length has been found. In best fit mode aCarry should also be |
|
186 checked as aRunLength will not be set if aCarry is the only suitable run length |
|
187 found. |
|
188 |
|
189 @return Start position, if a suitable run was found; |
|
190 KErrNotFound, if no suitable run was found; |
|
191 KErrOverflow, if all positions free and best fit mode, or if all positions free |
|
192 in first fit mode and length requested > number of positions available. |
|
193 |
|
194 @see TBitMapAllocator::AllocConsecutive(TInt aLength, TBool aBestFit) |
|
195 @see TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit) |
|
196 */ |
|
197 EXPORT_C TInt TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit, TInt& aCarry, TInt& aRunLength) const |
|
198 { |
|
199 return AllocAligned(aLength, aAlign, aBase, aBestFit, aCarry, aRunLength, 0); |
|
200 } |
|
201 |
|
202 |
|
203 /** Allocates the next available bit position starting from the specified offset. |
|
204 |
|
205 Note - If no free bit positions can be found after aOffset this method will |
|
206 wrap around and continue the search from the start of the bit map. |
|
207 |
|
208 @param aOffset The offset from the start of the bit map. |
|
209 @return The number of the bit position allocated, -1 if all positions are occupied. |
|
210 */ |
|
211 EXPORT_C TInt TBitMapAllocator::AllocFrom(TUint aOffset) |
|
212 { |
|
213 __ASSERT_ALWAYS(aOffset < (TUint)iSize, TBMA_FAULT()); |
|
214 |
|
215 if (!iAvail) |
|
216 return -1; |
|
217 --iAvail; |
|
218 const TUint32* pEnd = iMap + ((iSize+31)>>5); |
|
219 TUint32* pW = iMap + (aOffset >> 5); |
|
220 // Only check the bits after aOffset in this word. |
|
221 TUint wordMask = 0xffffffffu >> (aOffset & 0x1f); |
|
222 #ifdef _DEBUG |
|
223 if(!((aOffset&0x1f)==0 || (wordMask&0x80000000u)==0)) // check compiler has done unsigned >> |
|
224 TBMA_FAULT(); |
|
225 #endif |
|
226 TUint word = *pW & wordMask; |
|
227 // No free bit positions in this word so search through the rest of the words. |
|
228 while (!word) |
|
229 { |
|
230 ++pW; |
|
231 if (pW >= pEnd) |
|
232 pW = iMap; |
|
233 word = *pW; |
|
234 } |
|
235 TInt n = __e32_find_ms1_32(word); |
|
236 *pW &= ~(1 << n); |
|
237 n = (31 - n) + ((pW - iMap) << 5); |
|
238 return n; |
|
239 } |
|
240 |
|
241 |
|
242 #if !defined( __TBMA_MACHINE_CODED__) | defined(__EABI_CTORS__) |
|
243 /** Constructs a new TBitMapAllocator object. |
|
244 |
|
245 @param aSize The number of bit positions required. |
|
246 @param aState TRUE if all bit positions initially free; |
|
247 FALSE if all bit positions initially allocated. |
|
248 */ |
|
249 EXPORT_C TBitMapAllocator::TBitMapAllocator(TInt aSize, TBool aState) |
|
250 { |
|
251 __ASSERT_ALWAYS(aSize>0, TBMA_FAULT()); |
|
252 iSize=aSize; |
|
253 if (aState) |
|
254 { |
|
255 iCheckFirst=iMap; |
|
256 iAvail=aSize; |
|
257 TUint32* pW=iMap; |
|
258 for (; aSize>=32; aSize-=32) |
|
259 *pW++=0xffffffff; |
|
260 if (aSize) |
|
261 *pW=((0xffffffffu)<<(32-aSize)); |
|
262 } |
|
263 else |
|
264 { |
|
265 TInt nmapw=(aSize+31)>>5; |
|
266 iAvail=0; |
|
267 iCheckFirst=iMap+nmapw-1; |
|
268 memclr(iMap, nmapw*sizeof(TUint32)); |
|
269 } |
|
270 } |
|
271 #endif |
|
272 |
|
273 |
|
274 #if !defined( __TBMA_MACHINE_CODED__) |
|
275 /** Allocates the next available bit position. |
|
276 |
|
277 @return Number of position allocated, -1 if all positions occupied. |
|
278 */ |
|
279 EXPORT_C TInt TBitMapAllocator::Alloc() |
|
280 { |
|
281 if (!iAvail) |
|
282 return -1; |
|
283 --iAvail; |
|
284 TUint32* pW=iCheckFirst; |
|
285 while (!*pW) |
|
286 ++pW; |
|
287 iCheckFirst=pW; |
|
288 TInt n=__e32_find_ms1_32(*pW); |
|
289 *pW &= ~(1<<n); |
|
290 n=(31-n)+((pW-iMap)<<5); |
|
291 return n; |
|
292 } |
|
293 |
|
294 |
|
295 /** Frees the specified bit position. |
|
296 |
|
297 @param aPos Number of bit position to be freed; must be currently allocated. |
|
298 */ |
|
299 EXPORT_C void TBitMapAllocator::Free(TInt aPos) |
|
300 { |
|
301 __ASSERT_ALWAYS(TUint(aPos)<TUint(iSize), TBMA_FAULT()); |
|
302 TUint32* pW=iMap+(aPos>>5); |
|
303 TUint32 b=0x80000000u>>(aPos&31); |
|
304 __ASSERT_ALWAYS(!(*pW & b), TBMA_FAULT()); |
|
305 *pW |= b; |
|
306 ++iAvail; |
|
307 if (pW<iCheckFirst) |
|
308 iCheckFirst=pW; |
|
309 } |
|
310 |
|
311 |
|
312 /** Allocates a specific range of bit positions. |
|
313 |
|
314 The specified range must lie within the total range for this allocator and all |
|
315 the positions must currently be free. |
|
316 |
|
317 @param aStart First position to allocate. |
|
318 @param aLength Number of consecutive positions to allocate, must be >0. |
|
319 */ |
|
320 EXPORT_C void TBitMapAllocator::Alloc(TInt aStart, TInt aLength) |
|
321 { |
|
322 __ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT()); |
|
323 __ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT()); |
|
324 __ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT()); |
|
325 TInt wix=aStart>>5; |
|
326 TInt sbit=aStart&31; |
|
327 TUint32* pW=iMap+wix; |
|
328 iAvail-=aLength; |
|
329 TInt ebit=sbit+aLength; |
|
330 if (ebit<32) |
|
331 { |
|
332 TUint32 b=(~(0xffffffffu>>aLength)>>sbit); |
|
333 TUint32 w=*pW; |
|
334 __ASSERT_ALWAYS((w|b)==w, TBMA_FAULT()); |
|
335 *pW=w&~b; |
|
336 return; |
|
337 } |
|
338 TUint32 b=(0xffffffffu>>sbit); |
|
339 while (ebit>0) |
|
340 { |
|
341 TUint32 w=*pW; |
|
342 __ASSERT_ALWAYS((w|b)==w, TBMA_FAULT()); |
|
343 *pW++=w&~b; |
|
344 b=0xffffffffu; |
|
345 ebit-=32; |
|
346 if (ebit<32) |
|
347 b=~(b>>ebit); |
|
348 } |
|
349 } |
|
350 |
|
351 |
|
352 /** Frees a specific range of bit positions. |
|
353 |
|
354 The specified range must lie within the total range for this allocator and all |
|
355 the positions must currently be allocated. |
|
356 |
|
357 @param aStart First position to free. |
|
358 @param aLength Number of consecutive positions to free, must be >0. |
|
359 */ |
|
360 EXPORT_C void TBitMapAllocator::Free(TInt aStart, TInt aLength) |
|
361 { |
|
362 __ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT()); |
|
363 __ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT()); |
|
364 __ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT()); |
|
365 TInt wix=aStart>>5; |
|
366 TInt sbit=aStart&31; |
|
367 TUint32* pW=iMap+wix; |
|
368 if (!iAvail || pW<iCheckFirst) |
|
369 iCheckFirst=pW; |
|
370 iAvail+=aLength; |
|
371 TInt ebit=sbit+aLength; |
|
372 if (ebit<32) |
|
373 { |
|
374 TUint32 b=(~(0xffffffffu>>aLength)>>sbit); |
|
375 TUint32 w=*pW; |
|
376 __ASSERT_ALWAYS((w&b)==0, TBMA_FAULT()); |
|
377 *pW=w|b; |
|
378 return; |
|
379 } |
|
380 TUint32 b=(0xffffffffu>>sbit); |
|
381 while (ebit>0) |
|
382 { |
|
383 TUint32 w=*pW; |
|
384 __ASSERT_ALWAYS((w&b)==0, TBMA_FAULT()); |
|
385 *pW++=w|b; |
|
386 b=0xffffffffu; |
|
387 ebit-=32; |
|
388 if (ebit<32) |
|
389 b=~(b>>ebit); |
|
390 } |
|
391 } |
|
392 |
|
393 |
|
394 /** Frees a specific range of bit positions. |
|
395 |
|
396 The specified range must lie within the total range for this allocator but it is |
|
397 not necessary that all the positions are currently allocated. |
|
398 |
|
399 @param aStart First position to free. |
|
400 @param aLength Number of consecutive positions to free, must be >0. |
|
401 */ |
|
402 EXPORT_C void TBitMapAllocator::SelectiveFree(TInt aStart, TInt aLength) |
|
403 { |
|
404 __ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT()); |
|
405 __ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT()); |
|
406 __ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT()); |
|
407 TInt wix=aStart>>5; |
|
408 TInt sbit=aStart&31; |
|
409 TUint32* pW=iMap+wix; |
|
410 if (!iAvail || pW<iCheckFirst) |
|
411 iCheckFirst=pW; |
|
412 iAvail+=aLength; // update free count assuming no positions already free |
|
413 TInt ebit=sbit+aLength; |
|
414 if (ebit<32) |
|
415 { |
|
416 TUint32 b=(~(0xffffffffu>>aLength)>>sbit); |
|
417 TUint32 w=*pW; |
|
418 *pW=w|b; // mark all positions free |
|
419 iAvail-=__e32_bit_count_32(w&b); // reduce free count by number of positions already free |
|
420 return; |
|
421 } |
|
422 TUint32 b=(0xffffffffu>>sbit); |
|
423 while (ebit>0) |
|
424 { |
|
425 TUint32 w=*pW; |
|
426 *pW++=w|b; // mark all positions free |
|
427 iAvail-=__e32_bit_count_32(w&b); // reduce free count by number of positions already free |
|
428 b=0xffffffffu; |
|
429 ebit-=32; |
|
430 if (ebit<32) |
|
431 b=~(b>>ebit); |
|
432 } |
|
433 } |
|
434 |
|
435 |
|
436 /** Tests whether a specific range of bit positions are all free. |
|
437 |
|
438 The specified range must lie within the total range for this allocator. |
|
439 |
|
440 @param aStart First position to check. |
|
441 @param aLength Number of consecutive positions to check, must be >0. |
|
442 |
|
443 @return FALSE if all positions free, TRUE if at least one is occupied. |
|
444 */ |
|
445 EXPORT_C TBool TBitMapAllocator::NotFree(TInt aStart, TInt aLength) const |
|
446 { |
|
447 // Inverse logic - returns 0 if all positions free, nonzero otherwise |
|
448 __ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT()); |
|
449 __ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT()); |
|
450 __ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT()); |
|
451 TInt wix=aStart>>5; |
|
452 TInt sbit=aStart&31; |
|
453 const TUint32* pW=iMap+wix; |
|
454 TInt ebit=sbit+aLength; |
|
455 if (ebit<32) |
|
456 { |
|
457 TUint32 b=(~(0xffffffffu>>aLength)>>sbit); |
|
458 return (*pW^b)&b; |
|
459 } |
|
460 TUint32 b=(0xffffffffu>>sbit); |
|
461 TUint32 r=0; |
|
462 while (ebit>0) |
|
463 { |
|
464 r|=((*pW++^b)&b); |
|
465 b=0xffffffffu; |
|
466 ebit-=32; |
|
467 if (ebit<32) |
|
468 b=~(b>>ebit); |
|
469 } |
|
470 return r; |
|
471 } |
|
472 |
|
473 |
|
474 /** Tests whether a specific range of bit positions are all occupied. |
|
475 |
|
476 The specified range must lie within the total range for this allocator. |
|
477 |
|
478 @param aStart First position to check. |
|
479 @param aLength Number of consecutive positions to check, must be >0. |
|
480 |
|
481 @return FALSE if all positions occupied, TRUE if at least one is free. |
|
482 */ |
|
483 EXPORT_C TBool TBitMapAllocator::NotAllocated(TInt aStart, TInt aLength) const |
|
484 { |
|
485 // Inverse logic - returns 0 if all positions allocated, nonzero otherwise |
|
486 __ASSERT_ALWAYS(TUint(aStart)<TUint(iSize), TBMA_FAULT()); |
|
487 __ASSERT_ALWAYS(TUint(aStart+aLength)>=TUint(aStart), TBMA_FAULT()); |
|
488 __ASSERT_ALWAYS(TUint(aStart+aLength)<=TUint(iSize), TBMA_FAULT()); |
|
489 TInt wix=aStart>>5; |
|
490 TInt sbit=aStart&31; |
|
491 const TUint32* pW=iMap+wix; |
|
492 TInt ebit=sbit+aLength; |
|
493 if (ebit<32) |
|
494 { |
|
495 TUint32 b=(~(0xffffffffu>>aLength)>>sbit); |
|
496 return *pW&b; |
|
497 } |
|
498 TUint32 b=(0xffffffffu>>sbit); |
|
499 TUint32 r=0; |
|
500 while (ebit>0) |
|
501 { |
|
502 r|=(*pW++&b); |
|
503 b=0xffffffffu; |
|
504 ebit-=32; |
|
505 if (ebit<32) |
|
506 b=~(b>>ebit); |
|
507 } |
|
508 return r; |
|
509 } |
|
510 |
|
511 |
|
512 /** Allocates up to a specified number of available bit positions. |
|
513 |
|
514 The allocated positions are not required to bear any relationship to |
|
515 each other. |
|
516 If the number of free positions is less than the number requested, |
|
517 allocate all currently free positions. |
|
518 |
|
519 @param aLength Maximum number of positions to allocate. |
|
520 @param aList Pointer to memory area where allocated bit numbers should be stored. |
|
521 |
|
522 @return The number of positions allocated. |
|
523 */ |
|
524 EXPORT_C TInt TBitMapAllocator::AllocList(TInt aLength, TInt* aList) |
|
525 { |
|
526 __ASSERT_ALWAYS(aLength>0, TBMA_FAULT()); |
|
527 if (aLength>iAvail) |
|
528 aLength=iAvail; |
|
529 TInt c=aLength; |
|
530 while (c--) |
|
531 *aList++=Alloc(); |
|
532 return aLength; |
|
533 } |
|
534 |
|
535 |
|
536 /** Finds a set of consecutive bit positions with specified alignment starting the |
|
537 search from the specfied bit position offset, with support for chaining |
|
538 multiple allocators. |
|
539 |
|
540 For further details see: |
|
541 TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit, TInt& aCarry, TInt& aRunLength) |
|
542 |
|
543 @param aLength number of consecutive bit positions to allocate. |
|
544 @param aAlign logarithm to base 2 of the alignment required. |
|
545 @param aBase the alignment of the first bit of this allocator - only significant modulo 2^aAlign. |
|
546 @param aBestFit TRUE for best fit allocation strategy, FALSE for first fit. |
|
547 @param aCarry carry in/carry out. |
|
548 @param aRunLength Holds best run length found so far. This will be set to KMaxTInt when no |
|
549 suitable run length has been found. In best fit mode aCarry should also be |
|
550 checked as aRunLength will not be set if aCarry is the only suitable run length |
|
551 found. |
|
552 @param aOffset The bit position to start the search from, set to 0 to search all bit positions. |
|
553 aOffset will be aligned so all bits before an aligned aOffset will be |
|
554 ignored. This can only be non-zero if aCarry is zero as any carry in bits will be |
|
555 ignored if aOffset is non-zero. |
|
556 |
|
557 @return Start position, if a suitable run was found; |
|
558 KErrNotFound, if no suitable run was found; |
|
559 KErrOverflow, if all positions free and best fit mode, or if all positions free |
|
560 in first fit mode and length requested > number of positions available. |
|
561 |
|
562 @see TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit, TInt& aCarry, TInt& aRunLength) |
|
563 */ |
|
564 EXPORT_C TInt TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit, TInt& aCarry, TInt& aRunLength, TUint aOffset) const |
|
565 { |
|
566 TInt minrl=KMaxTInt; |
|
567 __ASSERT_ALWAYS(aLength>0, TBMA_FAULT()); |
|
568 __ASSERT_ALWAYS(TUint(aAlign)<31, TBMA_FAULT()); |
|
569 __ASSERT_ALWAYS(aOffset < (TUint)iSize, TBMA_FAULT()); |
|
570 __ASSERT_ALWAYS(!aCarry || !aOffset, TBMA_FAULT()); |
|
571 TUint32 alignsize=1<<aAlign; |
|
572 TUint32 alignmask=alignsize-1; |
|
573 aBase&=alignmask; |
|
574 if (iAvail==iSize) |
|
575 { |
|
576 // Align aOffset if it is set so we ignore all bits before the aligned offset. |
|
577 aOffset = (!aOffset)? aOffset : ((aOffset + aBase + alignmask) & ~alignmask) - aBase; |
|
578 TInt runLength = (aOffset < (TUint)iSize)? iSize - aOffset : 0; |
|
579 if (!aBestFit) |
|
580 { |
|
581 TInt alignedStartPos = ((aOffset - aCarry + aBase + alignmask) & ~alignmask) - aBase; |
|
582 TInt lost = alignedStartPos - (aOffset - aCarry); |
|
583 if (runLength + aCarry - lost >= aLength) |
|
584 { |
|
585 aRunLength = runLength; |
|
586 if (alignedStartPos >= 0) |
|
587 { |
|
588 aCarry=0; // clear carry if not initial run |
|
589 } |
|
590 return (alignedStartPos >= 0)? alignedStartPos : 0; // return start pos of exact run |
|
591 } |
|
592 } |
|
593 if (aOffset) |
|
594 aCarry = runLength; |
|
595 else |
|
596 aCarry += iAvail; |
|
597 aRunLength = KMaxTInt; |
|
598 return KErrOverflow; |
|
599 } |
|
600 const TUint32* pW=aCarry?iMap:iCheckFirst; |
|
601 const TUint32* pE=iMap+((iSize+31)>>5); |
|
602 TInt n=((pW-iMap)<<5); |
|
603 TInt p=-1; |
|
604 TInt q=-aCarry; |
|
605 TUint32 s=aCarry?~0:0; // 0 when searching for 1's, FFFFFFFF when searching for 0's |
|
606 |
|
607 TUint32 offsetMask = 0; |
|
608 if (aOffset) |
|
609 {// Start search from aOffset. Only align aOffset if aOffset is to |
|
610 // be used otherwise the best fit mode may fail as aligning aOffset |
|
611 // may cause the search to skip past parts of the bit map. |
|
612 aOffset = ((aOffset + aBase + alignmask) & ~alignmask) - aBase; |
|
613 const TUint32* offsetWord = iMap + (aOffset >> 5); |
|
614 if (offsetWord >= pW) |
|
615 { |
|
616 pW = offsetWord; |
|
617 n = aOffset & 0xffffffe0; |
|
618 offsetMask = 0xffffffff >> (aOffset & 31); |
|
619 __ASSERT_ALWAYS(offsetMask, TBMA_FAULT()); |
|
620 } |
|
621 } |
|
622 while (pW<pE) |
|
623 { |
|
624 TUint32 word = *pW++; |
|
625 if (offsetMask) |
|
626 {// Start search after bit aOffset. |
|
627 word &= offsetMask; // Mask off any bits before the aOffset |
|
628 offsetMask = 0; // Reset so future iterations use whole of next word. |
|
629 } |
|
630 if (word==s) // check if any of required bit present |
|
631 { |
|
632 n+=32; // if not, step bit number on by 32 |
|
633 continue; |
|
634 } |
|
635 TInt rl=-1; |
|
636 for (TUint32 b=0x80000000; b; ++n, b>>=1) |
|
637 { |
|
638 if ((word ^ s) & b) |
|
639 { |
|
640 if (s && n==iSize) |
|
641 break; // reached end |
|
642 // bit found - invert search bit |
|
643 s=~s; |
|
644 if (s) |
|
645 q=n; // 1 found so save position |
|
646 else |
|
647 { |
|
648 rl=n-q; // 0 found, calculate run length of 1's |
|
649 TInt alignedStartPos = ((q + aBase + alignmask) & ~alignmask) - aBase; |
|
650 TInt lost = alignedStartPos - q; |
|
651 if (rl-lost>=aLength) |
|
652 { |
|
653 if (!aBestFit || rl==aLength) |
|
654 { |
|
655 // first fit or exact match - we're finished |
|
656 if (alignedStartPos >= 0) |
|
657 { |
|
658 aCarry=0; // clear carry if not initial run |
|
659 } |
|
660 aRunLength=rl; |
|
661 return (alignedStartPos >= 0)? alignedStartPos : 0; |
|
662 } |
|
663 if (rl<minrl) |
|
664 { |
|
665 // best fit and this run is smallest so far, so record its position and length |
|
666 minrl=rl; |
|
667 p = (alignedStartPos >= 0)? alignedStartPos : 0; |
|
668 } |
|
669 } |
|
670 } |
|
671 } |
|
672 } |
|
673 } |
|
674 if (minrl!=aLength) |
|
675 { |
|
676 // exact match not found or first fit and no match found |
|
677 TInt rl=0; |
|
678 if (s) |
|
679 { |
|
680 // we were looking for 0, so this counts as a run |
|
681 // get run length |
|
682 rl=n-q; |
|
683 if (!aBestFit) |
|
684 { |
|
685 TInt alignedStartPos = ((q + aBase + alignmask) & ~alignmask) - aBase; |
|
686 TInt lost = alignedStartPos - q; |
|
687 if (rl-lost>=aLength) |
|
688 {// BMA is not totally empty so this can't be the initial run |
|
689 // and the final run. Therefore the start pos must be within |
|
690 // this bma so clear carry and return start pos. |
|
691 aCarry=0; |
|
692 aRunLength=rl; |
|
693 return alignedStartPos; |
|
694 } |
|
695 } |
|
696 } |
|
697 aCarry=rl; // set carry to length of final run or 0 if none |
|
698 } |
|
699 aRunLength=minrl; // return best run length found |
|
700 return p; // return start position of run or -1 if run not found |
|
701 } |
|
702 #endif |
|
703 |
|
704 |
|
705 /** Finds a set of consecutive free positions on a single bit map allocator. |
|
706 |
|
707 @param aLength number of consecutive bit positions to allocate. |
|
708 @param aBestFit TRUE for best fit allocation strategy, FALSE for first fit. |
|
709 |
|
710 @return Start position, if a suitable run was found; |
|
711 KErrNotFound, if no suitable run was found. |
|
712 */ |
|
713 EXPORT_C TInt TBitMapAllocator::AllocConsecutive(TInt aLength, TBool aBestFit) const |
|
714 { |
|
715 TInt carry=0; |
|
716 TInt l=KMaxTInt; |
|
717 TInt r=AllocAligned(aLength,0,0,aBestFit,carry,l); |
|
718 if (aBestFit) |
|
719 { |
|
720 // must check final run if any |
|
721 if (carry>=aLength && carry<l) |
|
722 r=iSize-carry; |
|
723 } |
|
724 if (r<0) |
|
725 r=KErrNotFound; |
|
726 return r; |
|
727 } |
|
728 |
|
729 |
|
730 /** Finds a set of consecutive free positions on a single bit map allocator with |
|
731 specified alignment. |
|
732 |
|
733 @param aLength number of consecutive bit positions to allocate. |
|
734 @param aAlign logarithm to base 2 of the alignment required. |
|
735 @param aBase the alignment of the first bit of this allocator - only significant modulo 2^aAlign. |
|
736 @param aBestFit TRUE for best fit allocation strategy, FALSE for first fit. |
|
737 |
|
738 @return Start position, if a suitable run was found; |
|
739 KErrNotFound, if no suitable run was found. |
|
740 */ |
|
741 EXPORT_C TInt TBitMapAllocator::AllocAligned(TInt aLength, TInt aAlign, TInt aBase, TBool aBestFit) const |
|
742 { |
|
743 TInt carry=0; |
|
744 TInt l=KMaxTInt; |
|
745 TUint32 alignsize=1<<aAlign; |
|
746 TUint32 alignmask=alignsize-1; |
|
747 aBase&=alignmask; |
|
748 TInt r=AllocAligned(aLength,aAlign,aBase,aBestFit,carry,l); |
|
749 if (aBestFit) |
|
750 { |
|
751 // must check final run if any |
|
752 TInt fpos=iSize-carry; |
|
753 TInt lost=((fpos+aBase+alignmask)&~alignmask)-aBase-fpos; |
|
754 if (carry-lost>=aLength && carry<l) |
|
755 r=fpos+lost; |
|
756 } |
|
757 if (r<0) |
|
758 r=KErrNotFound; |
|
759 else |
|
760 r=((r+aBase+alignmask)&~alignmask)-aBase; |
|
761 return r; |
|
762 } |
|
763 |
|
764 |
|
765 /** Copies a range from another allocator, mark remainder as occupied. |
|
766 |
|
767 Values of bit positions from aFirst to aFirst+aLen-1 inclusive in allocator |
|
768 aA are copied to bit positions in this allocator starting with aFirst mod 32. |
|
769 Remaining bit positions in this allocator are marked as occupied. |
|
770 |
|
771 @param aA Pointer to source allocator. |
|
772 @param aFirst Number in source allocator of first bit to copy. |
|
773 @param aLen Number of bits to copy from source allocator. |
|
774 */ |
|
775 EXPORT_C void TBitMapAllocator::CopyAlignedRange(const TBitMapAllocator* aA, TInt aFirst, TInt aLen) |
|
776 { |
|
777 const TUint32* srcptr = aA->iMap + (aFirst>>5); |
|
778 TInt last = aFirst + aLen - 1; |
|
779 TInt len = (((last+32)&~31)-(aFirst&~31))>>3; // bytes |
|
780 __ASSERT_ALWAYS(len<=iSize, TBMA_FAULT()); |
|
781 TInt remain = ((iSize+31)&~31)-(len<<3); |
|
782 wordmove(iMap, srcptr, len); |
|
783 memclr(iMap+(len>>2), remain>>3); |
|
784 TUint32* p = iMap; |
|
785 TUint32* pE = p + (len>>2); |
|
786 *p &= (0xffffffffu >> (aFirst&31)); |
|
787 pE[-1] &= (0xffffffffu << (31-(last&31))); |
|
788 iCheckFirst = pE-1; |
|
789 iAvail = 0; |
|
790 for (; p<pE; ++p) |
|
791 { |
|
792 TUint32 x = *p; |
|
793 if (x) |
|
794 { |
|
795 if (p<iCheckFirst) |
|
796 iCheckFirst = p; |
|
797 iAvail += __e32_bit_count_32(x); |
|
798 } |
|
799 } |
|
800 } |