1 /* $Id: bitmap.c,v 1.8 2003/02/08 20:59:50 ekohl Exp $
3 * COPYRIGHT: See COPYING in the top level directory
4 * PROJECT: ReactOS kernel
5 * FILE: ntoskrnl/rtl/bitmap.c
6 * PURPOSE: Bitmap functions
8 * 20/08/99 Created by Eric Kohl
11 #include <ddk/ntddk.h>
14 #define ALIGN(x,align) (((x)+(align)-1) / (align))
16 #define MASK(Count, Shift) ((Count) == 32 ? 0xFFFFFFFF : ~(0xFFFFFFFF << (Count)) << (Shift))
22 PRTL_BITMAP BitMapHeader
,
27 BitMapHeader
->SizeOfBitMap
= SizeOfBitMap
;
28 BitMapHeader
->Buffer
= BitMapBuffer
;
35 PRTL_BITMAP BitMapHeader
,
40 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
45 if (StartingIndex
>= Size
||
47 (StartingIndex
+ Length
> Size
))
50 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (StartingIndex
/ 32);
53 /* get bit shift in current dword */
54 Shift
= StartingIndex
& 0x1F;
56 /* get number of bits to check in current dword */
57 Count
= (Length
> 32 - Shift
) ? 32 - Shift
: Length
;
60 if (*Ptr
++ & MASK(Count
, Shift
))
64 StartingIndex
+= Count
;
74 PRTL_BITMAP BitMapHeader
,
79 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
84 if (StartingIndex
>= Size
||
86 (StartingIndex
+ Length
> Size
))
89 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (StartingIndex
/ 32);
92 /* get bit shift in current dword */
93 Shift
= StartingIndex
& 0x1F;
95 /* get number of bits to check in current dword */
96 Count
= (Length
> 32 - Shift
) ? 32 - Shift
: Length
;
99 if (~*Ptr
++ & MASK(Count
, Shift
))
103 StartingIndex
+= Count
;
113 IN OUT PRTL_BITMAP BitMapHeader
116 memset (BitMapHeader
->Buffer
,
118 ALIGN(BitMapHeader
->SizeOfBitMap
, 8));
125 PRTL_BITMAP BitMapHeader
,
130 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
135 if (StartingIndex
>= Size
|| NumberToClear
== 0)
138 if (StartingIndex
+ NumberToClear
> Size
)
139 NumberToClear
= Size
- StartingIndex
;
141 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (StartingIndex
/ 32);
142 while (NumberToClear
)
144 /* bit shift in current dword */
145 Shift
= StartingIndex
& 0x1F;
147 /* number of bits to change in current dword */
148 Count
= (NumberToClear
> 32 - Shift
) ? 32 - Shift
: NumberToClear
;
151 *Ptr
++ &= ~MASK(Count
, Shift
);
152 NumberToClear
-= Count
;
153 StartingIndex
+= Count
;
161 PRTL_BITMAP BitMapHeader
,
166 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
172 if (NumberToFind
> Size
|| NumberToFind
== 0)
175 if (HintIndex
>= Size
)
179 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (Index
/ 32);
180 Mask
= 1 << (Index
& 0x1F);
182 while (HintIndex
< Size
)
184 /* count clear bits */
185 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
187 if (++Count
>= NumberToFind
)
198 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
216 RtlFindClearBitsAndSet (
217 PRTL_BITMAP BitMapHeader
,
224 Index
= RtlFindClearBits (BitMapHeader
,
227 if (Index
!= (ULONG
)-1)
228 RtlSetBits (BitMapHeader
,
238 RtlFindFirstRunClear (
239 PRTL_BITMAP BitMapHeader
,
243 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
249 if (*StartingIndex
> Size
)
251 *StartingIndex
= (ULONG
)-1;
255 Index
= *StartingIndex
;
256 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (Index
/ 32);
257 Mask
= 1 << (Index
& 0x1F);
260 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
270 /* return index of first clear bit */
273 *StartingIndex
= (ULONG
)-1;
277 *StartingIndex
= Index
;
279 /* count clear bits */
280 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
298 PRTL_BITMAP BitMapHeader
,
302 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
308 if (*StartingIndex
> Size
)
310 *StartingIndex
= (ULONG
)-1;
314 Index
= *StartingIndex
;
315 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (Index
/ 32);
316 Mask
= 1 << (Index
& 0x1F);
318 /* skip clear bits */
319 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
329 /* return index of first set bit */
332 *StartingIndex
= (ULONG
)-1;
336 *StartingIndex
= Index
;
339 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
356 RtlFindLongestRunClear (
357 PRTL_BITMAP BitMapHeader
,
361 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
362 PULONG Ptr
= (PULONG
)BitMapHeader
->Buffer
;
374 /* count clear bits */
375 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
387 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
405 *StartingIndex
= Maxstart
;
413 RtlFindLongestRunSet (
414 PRTL_BITMAP BitMapHeader
,
418 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
419 PULONG Ptr
= (PULONG
)BitMapHeader
->Buffer
;
432 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
443 /* skip clear bits */
444 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
462 *StartingIndex
= Maxstart
;
471 PRTL_BITMAP BitMapHeader
,
476 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
482 if (NumberToFind
> Size
|| NumberToFind
== 0)
485 if (HintIndex
>= Size
)
489 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (Index
/ 32);
490 Mask
= 1 << (Index
& 0x1F);
492 while (HintIndex
< Size
)
495 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
497 if (++Count
>= NumberToFind
)
507 /* skip clear bits */
508 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
526 RtlFindSetBitsAndClear (
527 PRTL_BITMAP BitMapHeader
,
534 Index
= RtlFindSetBits (BitMapHeader
,
537 if (Index
!= (ULONG
)-1)
538 RtlClearBits (BitMapHeader
,
548 RtlNumberOfClearBits (
549 PRTL_BITMAP BitMapHeader
552 PULONG Ptr
= (PULONG
)BitMapHeader
->Buffer
;
553 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
558 for (Mask
= 1, Index
= 0, Count
= 0; Index
< Size
; Index
++)
578 PRTL_BITMAP BitMapHeader
581 PULONG Ptr
= (PULONG
)BitMapHeader
->Buffer
;
582 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
587 for (Mask
= 1, Index
= 0, Count
= 0; Index
< Size
; Index
++)
607 IN OUT PRTL_BITMAP BitMapHeader
610 memset (BitMapHeader
->Buffer
,
612 ALIGN(BitMapHeader
->SizeOfBitMap
, 8));
619 PRTL_BITMAP BitMapHeader
,
624 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
629 if (StartingIndex
>= Size
|| NumberToSet
== 0)
632 if (StartingIndex
+ NumberToSet
> Size
)
633 NumberToSet
= Size
- StartingIndex
;
635 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (StartingIndex
/ 32);
638 /* bit shift in current dword */
639 Shift
= StartingIndex
& 0x1F;
641 /* number of bits to change in current dword */
642 Count
= (NumberToSet
> 32 - Shift
) ? 32 - Shift
: NumberToSet
;
645 *Ptr
++ |= MASK(Count
, Shift
);
646 NumberToSet
-= Count
;
647 StartingIndex
+= Count
;