1 /* $Id: bitmap.c,v 1.3 2002/09/07 15:12:40 chorns Exp $
3 * COPYRIGHT: See COPYING in the top level directory
4 * PROJECT: ReactOS kernel
5 * FILE: lib/ntdll/rtl/bitmap.c
6 * PURPOSE: Bitmap functions
8 * 20/08/99 Created by Eric Kohl
11 #define NTOS_USER_MODE
17 #define ALIGN(x,align) (((x)+(align)-1) / (align))
20 /* FUNCTIONS *****************************************************************/
25 PRTL_BITMAP BitMapHeader
,
30 BitMapHeader
->SizeOfBitMap
= SizeOfBitMap
;
31 BitMapHeader
->Buffer
= BitMapBuffer
;
38 PRTL_BITMAP BitMapHeader
,
43 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
48 if (StartingIndex
>= Size
||
50 (StartingIndex
+ Length
> Size
))
53 Ptr
= (PUCHAR
)BitMapHeader
->Buffer
+ (StartingIndex
/ 8);
56 /* get bit shift in current byte */
57 Shift
= StartingIndex
& 7;
59 /* get number of bits to check in current byte */
60 Count
= (Length
> 8 - Shift
) ? 8 - Shift
: Length
;
63 if (*Ptr
& (~(0xFF << Count
) << Shift
))
68 StartingIndex
+= Count
;
78 PRTL_BITMAP BitMapHeader
,
83 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
89 if (StartingIndex
>= Size
||
91 (StartingIndex
+ Length
> Size
))
94 Ptr
= (PUCHAR
)BitMapHeader
->Buffer
+ (StartingIndex
/ 8);
97 /* get bit shift in current byte */
98 Shift
= StartingIndex
& 7;
100 /* get number of bits to check in current byte */
101 Count
= (Length
> 8 - Shift
) ? 8 - Shift
: Length
;
103 /* bulid check byte */
104 Check
= ~(0xFF << Count
) << Shift
;
107 if ((*Ptr
& Check
) != Check
)
112 StartingIndex
+= Count
;
122 IN OUT PRTL_BITMAP BitMapHeader
125 memset (BitMapHeader
->Buffer
,
127 ALIGN(BitMapHeader
->SizeOfBitMap
, 8));
134 PRTL_BITMAP BitMapHeader
,
139 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
144 if (StartingIndex
>= Size
|| NumberToClear
== 0)
147 if (StartingIndex
+ NumberToClear
> Size
)
148 NumberToClear
= Size
- StartingIndex
;
150 Ptr
= (PCHAR
)(BitMapHeader
->Buffer
+ (StartingIndex
/ 8));
151 while (NumberToClear
)
153 /* bit shift in current byte */
154 Shift
= StartingIndex
& 7;
156 /* number of bits to change in current byte */
157 Count
= (NumberToClear
> 8 - Shift
) ? 8 - Shift
: NumberToClear
;
160 *Ptr
&= ~(~(0xFF << Count
) << Shift
);
163 NumberToClear
-= Count
;
164 StartingIndex
+= Count
;
172 PRTL_BITMAP BitMapHeader
,
177 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
183 if (NumberToFind
> Size
|| NumberToFind
== 0)
186 if (HintIndex
>= Size
)
190 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (Index
/ 8);
191 Mask
= 1 << (Index
& 7);
193 while (HintIndex
< Size
)
195 /* count clear bits */
196 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
198 if (++Count
>= NumberToFind
)
209 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
227 RtlFindClearBitsAndSet (
228 PRTL_BITMAP BitMapHeader
,
235 Index
= RtlFindClearBits (BitMapHeader
,
238 if (Index
!= (ULONG
)-1)
239 RtlSetBits (BitMapHeader
,
249 RtlFindFirstRunClear (
250 PRTL_BITMAP BitMapHeader
,
254 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
260 if (*StartingIndex
> Size
)
262 *StartingIndex
= (ULONG
)-1;
266 Index
= *StartingIndex
;
267 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (Index
/ 8);
268 Mask
= 1 << (Index
& 7);
271 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
281 /* return index of first clear bit */
284 *StartingIndex
= (ULONG
)-1;
288 *StartingIndex
= Index
;
290 /* count clear bits */
291 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
309 PRTL_BITMAP BitMapHeader
,
313 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
319 if (*StartingIndex
> Size
)
321 *StartingIndex
= (ULONG
)-1;
325 Index
= *StartingIndex
;
326 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (Index
/ 8);
327 Mask
= 1 << (Index
& 7);
329 /* skip clear bits */
330 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
340 /* return index of first set bit */
343 *StartingIndex
= (ULONG
)-1;
347 *StartingIndex
= Index
;
350 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
367 RtlFindLongestRunClear (
368 PRTL_BITMAP BitMapHeader
,
372 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
373 PCHAR Ptr
= (PCHAR
)BitMapHeader
->Buffer
;
385 /* count clear bits */
386 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
398 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
416 *StartingIndex
= Maxstart
;
424 RtlFindLongestRunSet (
425 PRTL_BITMAP BitMapHeader
,
429 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
430 PCHAR Ptr
= (PCHAR
)BitMapHeader
->Buffer
;
443 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
454 /* skip clear bits */
455 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
473 *StartingIndex
= Maxstart
;
482 PRTL_BITMAP BitMapHeader
,
487 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
493 if (NumberToFind
> Size
|| NumberToFind
== 0)
496 if (HintIndex
>= Size
)
500 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (Index
/ 8);
501 Mask
= 1 << (Index
& 7);
503 while (HintIndex
< Size
)
506 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
508 if (++Count
>= NumberToFind
)
518 /* skip clear bits */
519 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
537 RtlFindSetBitsAndClear (
538 PRTL_BITMAP BitMapHeader
,
545 Index
= RtlFindSetBits (BitMapHeader
,
548 if (Index
!= (ULONG
)-1)
549 RtlClearBits (BitMapHeader
,
559 RtlNumberOfClearBits (
560 PRTL_BITMAP BitMapHeader
563 PCHAR Ptr
= (PCHAR
)BitMapHeader
->Buffer
;
564 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
569 for (Mask
= 1, Index
= 0, Count
= 0; Index
< Size
; Index
++)
589 PRTL_BITMAP BitMapHeader
592 PCHAR Ptr
= (PCHAR
)BitMapHeader
->Buffer
;
593 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
598 for (Mask
= 1, Index
= 0, Count
= 0; Index
< Size
; Index
++)
618 IN OUT PRTL_BITMAP BitMapHeader
621 memset (BitMapHeader
->Buffer
,
623 ALIGN(BitMapHeader
->SizeOfBitMap
, 8));
630 PRTL_BITMAP BitMapHeader
,
635 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
640 if (StartingIndex
>= Size
|| NumberToSet
== 0)
643 if (StartingIndex
+ NumberToSet
> Size
)
644 NumberToSet
= Size
- StartingIndex
;
646 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (StartingIndex
/ 8);
649 /* bit shift in current byte */
650 Shift
= StartingIndex
& 7;
652 /* number of bits to change in current byte */
653 Count
= (NumberToSet
> 8 - Shift
) ? 8 - Shift
: NumberToSet
;
656 *Ptr
|= ~(0xFF << Count
) << Shift
;
659 NumberToSet
-= Count
;
660 StartingIndex
+= Count
;