1 /* $Id: bitmap.c,v 1.9 2003/07/11 01:23:15 royce 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))
25 PRTL_BITMAP BitMapHeader
,
30 BitMapHeader
->SizeOfBitMap
= SizeOfBitMap
;
31 BitMapHeader
->Buffer
= BitMapBuffer
;
41 PRTL_BITMAP BitMapHeader
,
46 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
51 if (StartingIndex
>= Size
||
53 (StartingIndex
+ Length
> Size
))
56 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (StartingIndex
/ 32);
59 /* get bit shift in current dword */
60 Shift
= StartingIndex
& 0x1F;
62 /* get number of bits to check in current dword */
63 Count
= (Length
> 32 - Shift
) ? 32 - Shift
: Length
;
66 if (*Ptr
++ & MASK(Count
, Shift
))
70 StartingIndex
+= Count
;
83 PRTL_BITMAP BitMapHeader
,
88 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
93 if (StartingIndex
>= Size
||
95 (StartingIndex
+ Length
> Size
))
98 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (StartingIndex
/ 32);
101 /* get bit shift in current dword */
102 Shift
= StartingIndex
& 0x1F;
104 /* get number of bits to check in current dword */
105 Count
= (Length
> 32 - Shift
) ? 32 - Shift
: Length
;
108 if (~*Ptr
++ & MASK(Count
, Shift
))
112 StartingIndex
+= Count
;
125 IN OUT PRTL_BITMAP BitMapHeader
128 memset (BitMapHeader
->Buffer
,
130 ALIGN(BitMapHeader
->SizeOfBitMap
, 8));
140 PRTL_BITMAP BitMapHeader
,
145 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
150 if (StartingIndex
>= Size
|| NumberToClear
== 0)
153 if (StartingIndex
+ NumberToClear
> Size
)
154 NumberToClear
= Size
- StartingIndex
;
156 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (StartingIndex
/ 32);
157 while (NumberToClear
)
159 /* bit shift in current dword */
160 Shift
= StartingIndex
& 0x1F;
162 /* number of bits to change in current dword */
163 Count
= (NumberToClear
> 32 - Shift
) ? 32 - Shift
: NumberToClear
;
166 *Ptr
++ &= ~MASK(Count
, Shift
);
167 NumberToClear
-= Count
;
168 StartingIndex
+= Count
;
179 PRTL_BITMAP BitMapHeader
,
184 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
190 if (NumberToFind
> Size
|| NumberToFind
== 0)
193 if (HintIndex
>= Size
)
197 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (Index
/ 32);
198 Mask
= 1 << (Index
& 0x1F);
200 while (HintIndex
< Size
)
202 /* count clear bits */
203 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
205 if (++Count
>= NumberToFind
)
216 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
237 RtlFindClearBitsAndSet (
238 PRTL_BITMAP BitMapHeader
,
245 Index
= RtlFindClearBits (BitMapHeader
,
248 if (Index
!= (ULONG
)-1)
249 RtlSetBits (BitMapHeader
,
262 RtlFindFirstRunClear (
263 PRTL_BITMAP BitMapHeader
,
267 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
273 if (*StartingIndex
> Size
)
275 *StartingIndex
= (ULONG
)-1;
279 Index
= *StartingIndex
;
280 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (Index
/ 32);
281 Mask
= 1 << (Index
& 0x1F);
284 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
294 /* return index of first clear bit */
297 *StartingIndex
= (ULONG
)-1;
301 *StartingIndex
= Index
;
303 /* count clear bits */
304 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
322 PRTL_BITMAP BitMapHeader
,
326 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
332 if (*StartingIndex
> Size
)
334 *StartingIndex
= (ULONG
)-1;
338 Index
= *StartingIndex
;
339 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (Index
/ 32);
340 Mask
= 1 << (Index
& 0x1F);
342 /* skip clear bits */
343 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
353 /* return index of first set bit */
356 *StartingIndex
= (ULONG
)-1;
360 *StartingIndex
= Index
;
363 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
383 RtlFindLongestRunClear (
384 PRTL_BITMAP BitMapHeader
,
388 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
389 PULONG Ptr
= (PULONG
)BitMapHeader
->Buffer
;
401 /* count clear bits */
402 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
414 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
432 *StartingIndex
= Maxstart
;
440 RtlFindLongestRunSet (
441 PRTL_BITMAP BitMapHeader
,
445 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
446 PULONG Ptr
= (PULONG
)BitMapHeader
->Buffer
;
459 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
470 /* skip clear bits */
471 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
489 *StartingIndex
= Maxstart
;
501 PRTL_BITMAP BitMapHeader
,
506 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
512 if (NumberToFind
> Size
|| NumberToFind
== 0)
515 if (HintIndex
>= Size
)
519 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (Index
/ 32);
520 Mask
= 1 << (Index
& 0x1F);
522 while (HintIndex
< Size
)
525 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
527 if (++Count
>= NumberToFind
)
537 /* skip clear bits */
538 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
559 RtlFindSetBitsAndClear (
560 PRTL_BITMAP BitMapHeader
,
567 Index
= RtlFindSetBits (BitMapHeader
,
570 if (Index
!= (ULONG
)-1)
571 RtlClearBits (BitMapHeader
,
584 RtlNumberOfClearBits (
585 PRTL_BITMAP BitMapHeader
588 PULONG Ptr
= (PULONG
)BitMapHeader
->Buffer
;
589 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
594 for (Mask
= 1, Index
= 0, Count
= 0; Index
< Size
; Index
++)
617 PRTL_BITMAP BitMapHeader
620 PULONG Ptr
= (PULONG
)BitMapHeader
->Buffer
;
621 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
626 for (Mask
= 1, Index
= 0, Count
= 0; Index
< Size
; Index
++)
649 IN OUT PRTL_BITMAP BitMapHeader
652 memset (BitMapHeader
->Buffer
,
654 ALIGN(BitMapHeader
->SizeOfBitMap
, 8));
664 PRTL_BITMAP BitMapHeader
,
669 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
674 if (StartingIndex
>= Size
|| NumberToSet
== 0)
677 if (StartingIndex
+ NumberToSet
> Size
)
678 NumberToSet
= Size
- StartingIndex
;
680 Ptr
= (PULONG
)BitMapHeader
->Buffer
+ (StartingIndex
/ 32);
683 /* bit shift in current dword */
684 Shift
= StartingIndex
& 0x1F;
686 /* number of bits to change in current dword */
687 Count
= (NumberToSet
> 32 - Shift
) ? 32 - Shift
: NumberToSet
;
690 *Ptr
++ |= MASK(Count
, Shift
);
691 NumberToSet
-= Count
;
692 StartingIndex
+= Count
;