1 /* $Id: bitmap.c,v 1.2 2000/03/08 01:54:34 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))
20 PRTL_BITMAP BitMapHeader
,
25 BitMapHeader
->SizeOfBitMap
= SizeOfBitMap
;
26 BitMapHeader
->Buffer
= BitMapBuffer
;
33 PRTL_BITMAP BitMapHeader
,
38 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
43 if (StartingIndex
>= Size
||
45 (StartingIndex
+ Length
> Size
))
48 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (StartingIndex
/ 8);
51 /* get bit shift in current byte */
52 Shift
= StartingIndex
& 7;
54 /* get number of bits to check in current byte */
55 Count
= (Length
> 8 - Shift
) ? 8 - Shift
: Length
;
58 if (*Ptr
++ & (~(0xFF << Count
) << Shift
))
62 StartingIndex
+= Count
;
72 PRTL_BITMAP BitMapHeader
,
77 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
82 if (StartingIndex
>= Size
||
84 (StartingIndex
+ Length
> Size
))
87 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (StartingIndex
/ 8);
90 /* get bit shift in current byte */
91 Shift
= StartingIndex
& 7;
93 /* get number of bits to check in current byte */
94 Count
= (Length
> 8 - Shift
) ? 8 - Shift
: Length
;
97 if (~*Ptr
++ & (~(0xFF << Count
) << Shift
))
101 StartingIndex
+= Count
;
111 IN OUT PRTL_BITMAP BitMapHeader
114 memset (BitMapHeader
->Buffer
,
116 ALIGN(BitMapHeader
->SizeOfBitMap
, 8));
123 PRTL_BITMAP BitMapHeader
,
128 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
133 if (StartingIndex
>= Size
|| NumberToClear
== 0)
136 if (StartingIndex
+ NumberToClear
> Size
)
137 NumberToClear
= Size
- StartingIndex
;
139 Ptr
= (PCHAR
)(BitMapHeader
->Buffer
+ (StartingIndex
/ 8));
140 while (NumberToClear
)
142 /* bit shift in current byte */
143 Shift
= StartingIndex
& 7;
145 /* number of bits to change in current byte */
146 Count
= (NumberToClear
> 8 - Shift
) ? 8 - Shift
: NumberToClear
;
149 *Ptr
++ &= ~(~(0xFF << Count
) << Shift
);
150 NumberToClear
-= Count
;
151 StartingIndex
+= Count
;
159 PRTL_BITMAP BitMapHeader
,
164 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
170 if (NumberToFind
> Size
|| NumberToFind
== 0)
173 if (HintIndex
>= Size
)
177 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (Index
/ 8);
178 Mask
= 1 << (Index
& 7);
180 while (HintIndex
< Size
)
182 /* count clear bits */
183 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
185 if (++Count
>= NumberToFind
)
196 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
214 RtlFindClearBitsAndSet (
215 PRTL_BITMAP BitMapHeader
,
222 Index
= RtlFindClearBits (BitMapHeader
,
225 if (Index
!= (ULONG
)-1)
226 RtlSetBits (BitMapHeader
,
236 RtlFindFirstRunClear (
237 PRTL_BITMAP BitMapHeader
,
241 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
247 if (*StartingIndex
> Size
)
249 *StartingIndex
= (ULONG
)-1;
253 Index
= *StartingIndex
;
254 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (Index
/ 8);
255 Mask
= 1 << (Index
& 7);
258 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
268 /* return index of first clear bit */
271 *StartingIndex
= (ULONG
)-1;
275 *StartingIndex
= Index
;
277 /* count clear bits */
278 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
296 PRTL_BITMAP BitMapHeader
,
300 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
306 if (*StartingIndex
> Size
)
308 *StartingIndex
= (ULONG
)-1;
312 Index
= *StartingIndex
;
313 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (Index
/ 8);
314 Mask
= 1 << (Index
& 7);
316 /* skip clear bits */
317 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
327 /* return index of first set bit */
330 *StartingIndex
= (ULONG
)-1;
334 *StartingIndex
= Index
;
337 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
354 RtlFindLongestRunClear (
355 PRTL_BITMAP BitMapHeader
,
359 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
360 PCHAR Ptr
= (PCHAR
)BitMapHeader
->Buffer
;
372 /* count clear bits */
373 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
385 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
403 *StartingIndex
= Maxstart
;
411 RtlFindLongestRunSet (
412 PRTL_BITMAP BitMapHeader
,
416 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
417 PCHAR Ptr
= (PCHAR
)BitMapHeader
->Buffer
;
430 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
441 /* skip clear bits */
442 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
460 *StartingIndex
= Maxstart
;
469 PRTL_BITMAP BitMapHeader
,
474 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
480 if (NumberToFind
> Size
|| NumberToFind
== 0)
483 if (HintIndex
>= Size
)
487 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (Index
/ 8);
488 Mask
= 1 << (Index
& 7);
490 while (HintIndex
< Size
)
493 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
495 if (++Count
>= NumberToFind
)
505 /* skip clear bits */
506 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
524 RtlFindSetBitsAndClear (
525 PRTL_BITMAP BitMapHeader
,
532 Index
= RtlFindSetBits (BitMapHeader
,
535 if (Index
!= (ULONG
)-1)
536 RtlClearBits (BitMapHeader
,
546 RtlNumberOfClearBits (
547 PRTL_BITMAP BitMapHeader
550 PCHAR Ptr
= (PCHAR
)BitMapHeader
->Buffer
;
551 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
556 for (Mask
= 1, Index
= 0, Count
= 0; Index
< Size
; Index
++)
576 PRTL_BITMAP BitMapHeader
579 PCHAR Ptr
= (PCHAR
)BitMapHeader
->Buffer
;
580 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
585 for (Mask
= 1, Index
= 0, Count
= 0; Index
< Size
; Index
++)
605 IN OUT PRTL_BITMAP BitMapHeader
608 memset (BitMapHeader
->Buffer
,
610 ALIGN(BitMapHeader
->SizeOfBitMap
, 8));
617 PRTL_BITMAP BitMapHeader
,
622 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
627 if (StartingIndex
>= Size
|| NumberToSet
== 0)
630 if (StartingIndex
+ NumberToSet
> Size
)
631 NumberToSet
= Size
- StartingIndex
;
633 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (StartingIndex
/ 8);
636 /* bit shift in current byte */
637 Shift
= StartingIndex
& 7;
639 /* number of bits to change in current byte */
640 Count
= (NumberToSet
> 8 - Shift
) ? 8 - Shift
: NumberToSet
;
643 *Ptr
++ |= ~(0xFF << Count
) << Shift
;
644 NumberToSet
-= Count
;
645 StartingIndex
+= Count
;