1 /* $Id: bitmap.c,v 1.7 2004/02/02 13:34:01 ekohl 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 #include <ddk/ntddk.h>
15 #include <ntdll/ntdll.h>
17 #define ALIGN(x,align) (((x)+(align)-1) / (align))
20 /* FUNCTIONS *****************************************************************/
28 PRTL_BITMAP BitMapHeader
,
33 BitMapHeader
->SizeOfBitMap
= SizeOfBitMap
;
34 BitMapHeader
->Buffer
= BitMapBuffer
;
44 PRTL_BITMAP BitMapHeader
,
49 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
54 if (StartingIndex
>= Size
||
56 (StartingIndex
+ Length
> Size
))
59 Ptr
= (PUCHAR
)BitMapHeader
->Buffer
+ (StartingIndex
/ 8);
62 /* get bit shift in current byte */
63 Shift
= StartingIndex
& 7;
65 /* get number of bits to check in current byte */
66 Count
= (Length
> 8 - Shift
) ? 8 - Shift
: Length
;
69 if (*Ptr
& (~(0xFF << Count
) << Shift
))
74 StartingIndex
+= Count
;
87 PRTL_BITMAP BitMapHeader
,
92 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
98 if (StartingIndex
>= Size
||
100 (StartingIndex
+ Length
> Size
))
103 Ptr
= (PUCHAR
)BitMapHeader
->Buffer
+ (StartingIndex
/ 8);
106 /* get bit shift in current byte */
107 Shift
= StartingIndex
& 7;
109 /* get number of bits to check in current byte */
110 Count
= (Length
> 8 - Shift
) ? 8 - Shift
: Length
;
112 /* bulid check byte */
113 Check
= ~(0xFF << Count
) << Shift
;
116 if ((*Ptr
& Check
) != Check
)
121 StartingIndex
+= Count
;
134 IN OUT PRTL_BITMAP BitMapHeader
137 memset (BitMapHeader
->Buffer
,
139 ALIGN(BitMapHeader
->SizeOfBitMap
, 8));
149 PRTL_BITMAP BitMapHeader
,
154 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
159 if (StartingIndex
>= Size
|| NumberToClear
== 0)
162 if (StartingIndex
+ NumberToClear
> Size
)
163 NumberToClear
= Size
- StartingIndex
;
165 Ptr
= (PCHAR
)(BitMapHeader
->Buffer
+ (StartingIndex
/ 8));
166 while (NumberToClear
)
168 /* bit shift in current byte */
169 Shift
= StartingIndex
& 7;
171 /* number of bits to change in current byte */
172 Count
= (NumberToClear
> 8 - Shift
) ? 8 - Shift
: NumberToClear
;
175 *Ptr
&= ~(~(0xFF << Count
) << Shift
);
178 NumberToClear
-= Count
;
179 StartingIndex
+= Count
;
190 PRTL_BITMAP BitMapHeader
,
195 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
201 if (NumberToFind
> Size
|| NumberToFind
== 0)
204 if (HintIndex
>= Size
)
208 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (Index
/ 8);
209 Mask
= 1 << (Index
& 7);
211 while (HintIndex
< Size
)
213 /* count clear bits */
214 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
216 if (++Count
>= NumberToFind
)
227 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
248 RtlFindClearBitsAndSet (
249 PRTL_BITMAP BitMapHeader
,
256 Index
= RtlFindClearBits (BitMapHeader
,
259 if (Index
!= (ULONG
)-1)
260 RtlSetBits (BitMapHeader
,
272 RtlFindClearRuns (PRTL_BITMAP BitMapHeader
,
273 PRTL_BITMAP_RUN RunArray
,
274 ULONG SizeOfRunArray
,
275 BOOLEAN LocateLongestRuns
)
283 RtlFindFirstRunClear (
284 PRTL_BITMAP BitMapHeader
,
288 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
294 if (*StartingIndex
> Size
)
296 *StartingIndex
= (ULONG
)-1;
300 Index
= *StartingIndex
;
301 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (Index
/ 8);
302 Mask
= 1 << (Index
& 7);
305 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
315 /* return index of first clear bit */
318 *StartingIndex
= (ULONG
)-1;
322 *StartingIndex
= Index
;
324 /* count clear bits */
325 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
343 PRTL_BITMAP BitMapHeader
,
347 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
353 if (*StartingIndex
> Size
)
355 *StartingIndex
= (ULONG
)-1;
359 Index
= *StartingIndex
;
360 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (Index
/ 8);
361 Mask
= 1 << (Index
& 7);
363 /* skip clear bits */
364 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
374 /* return index of first set bit */
377 *StartingIndex
= (ULONG
)-1;
381 *StartingIndex
= Index
;
384 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
403 RtlFindLastBackwardRunClear (IN PRTL_BITMAP BitMapHeader
,
405 IN PULONG StartingRunIndex
)
416 RtlFindLongestRunClear (
417 PRTL_BITMAP BitMapHeader
,
421 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
422 PCHAR Ptr
= (PCHAR
)BitMapHeader
->Buffer
;
434 /* count clear bits */
435 for (Count
= 0; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
447 for (; Index
< Size
&& *Ptr
& Mask
; Index
++)
465 *StartingIndex
= Maxstart
;
476 RtlFindLongestRunSet (
477 PRTL_BITMAP BitMapHeader
,
481 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
482 PCHAR Ptr
= (PCHAR
)BitMapHeader
->Buffer
;
495 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
506 /* skip clear bits */
507 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
525 *StartingIndex
= Maxstart
;
535 RtlFindNextForwardRunClear (IN PRTL_BITMAP BitMapHeader
,
537 IN PULONG StartingRunIndex
)
549 PRTL_BITMAP BitMapHeader
,
554 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
560 if (NumberToFind
> Size
|| NumberToFind
== 0)
563 if (HintIndex
>= Size
)
567 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (Index
/ 8);
568 Mask
= 1 << (Index
& 7);
570 while (HintIndex
< Size
)
573 for (Count
= 0; Index
< Size
&& *Ptr
& Mask
; Index
++)
575 if (++Count
>= NumberToFind
)
585 /* skip clear bits */
586 for (; Index
< Size
&& ~*Ptr
& Mask
; Index
++)
607 RtlFindSetBitsAndClear (
608 PRTL_BITMAP BitMapHeader
,
615 Index
= RtlFindSetBits (BitMapHeader
,
618 if (Index
!= (ULONG
)-1)
619 RtlClearBits (BitMapHeader
,
632 RtlNumberOfClearBits (
633 PRTL_BITMAP BitMapHeader
636 PCHAR Ptr
= (PCHAR
)BitMapHeader
->Buffer
;
637 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
642 for (Mask
= 1, Index
= 0, Count
= 0; Index
< Size
; Index
++)
665 PRTL_BITMAP BitMapHeader
668 PCHAR Ptr
= (PCHAR
)BitMapHeader
->Buffer
;
669 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
674 for (Mask
= 1, Index
= 0, Count
= 0; Index
< Size
; Index
++)
697 IN OUT PRTL_BITMAP BitMapHeader
700 memset (BitMapHeader
->Buffer
,
702 ALIGN(BitMapHeader
->SizeOfBitMap
, 8));
712 PRTL_BITMAP BitMapHeader
,
717 ULONG Size
= BitMapHeader
->SizeOfBitMap
;
722 if (StartingIndex
>= Size
|| NumberToSet
== 0)
725 if (StartingIndex
+ NumberToSet
> Size
)
726 NumberToSet
= Size
- StartingIndex
;
728 Ptr
= (PCHAR
)BitMapHeader
->Buffer
+ (StartingIndex
/ 8);
731 /* bit shift in current byte */
732 Shift
= StartingIndex
& 7;
734 /* number of bits to change in current byte */
735 Count
= (NumberToSet
> 8 - Shift
) ? 8 - Shift
: NumberToSet
;
738 *Ptr
|= ~(0xFF << Count
) << Shift
;
741 NumberToSet
-= Count
;
742 StartingIndex
+= Count
;
751 RtlFindLeastSignificantBit (IN ULONGLONG Set
)
758 for (i
= 0; i
< 64; i
++)
772 RtlFindMostSignificantBit (IN ULONGLONG Set
)
779 for (i
= 63; i
>= 0; i
--)