include the right files
[reactos.git] / reactos / ntoskrnl / rtl / bitmap.c
1 /* $Id: bitmap.c,v 1.10 2004/08/05 18:17:37 ion Exp $
2 *
3 * COPYRIGHT: See COPYING in the top level directory
4 * PROJECT: ReactOS kernel
5 * FILE: ntoskrnl/rtl/bitmap.c
6 * PURPOSE: Bitmap functions
7 * UPDATE HISTORY:
8 * 20/08/99 Created by Eric Kohl
9 */
10
11 #include <ddk/ntddk.h>
12
13 #define NDEBUG
14 #include <debug.h>
15
16 #define ALIGN(x,align) (((x)+(align)-1) / (align))
17
18 #define MASK(Count, Shift) ((Count) == 32 ? 0xFFFFFFFF : ~(0xFFFFFFFF << (Count)) << (Shift))
19
20
21 /*
22 * @implemented
23 */
24 VOID
25 STDCALL
26 RtlInitializeBitMap (
27 PRTL_BITMAP BitMapHeader,
28 PULONG BitMapBuffer,
29 ULONG SizeOfBitMap
30 )
31 {
32 BitMapHeader->SizeOfBitMap = SizeOfBitMap;
33 BitMapHeader->Buffer = BitMapBuffer;
34 }
35
36
37 /*
38 * @implemented
39 */
40 BOOLEAN
41 STDCALL
42 RtlAreBitsClear (
43 PRTL_BITMAP BitMapHeader,
44 ULONG StartingIndex,
45 ULONG Length
46 )
47 {
48 ULONG Size = BitMapHeader->SizeOfBitMap;
49 ULONG Shift;
50 ULONG Count;
51 PULONG Ptr;
52
53 if (StartingIndex >= Size ||
54 !Length ||
55 (StartingIndex + Length > Size))
56 return FALSE;
57
58 Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
59 while (Length)
60 {
61 /* get bit shift in current dword */
62 Shift = StartingIndex & 0x1F;
63
64 /* get number of bits to check in current dword */
65 Count = (Length > 32 - Shift) ? 32 - Shift : Length;
66
67 /* check dword */
68 if (*Ptr++ & MASK(Count, Shift))
69 return FALSE;
70
71 Length -= Count;
72 StartingIndex += Count;
73 }
74
75 return TRUE;
76 }
77
78
79 /*
80 * @implemented
81 */
82 BOOLEAN
83 STDCALL
84 RtlAreBitsSet (
85 PRTL_BITMAP BitMapHeader,
86 ULONG StartingIndex,
87 ULONG Length
88 )
89 {
90 ULONG Size = BitMapHeader->SizeOfBitMap;
91 ULONG Shift;
92 ULONG Count;
93 PULONG Ptr;
94
95 if (StartingIndex >= Size ||
96 !Length ||
97 (StartingIndex + Length > Size))
98 return FALSE;
99
100 Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
101 while (Length)
102 {
103 /* get bit shift in current dword */
104 Shift = StartingIndex & 0x1F;
105
106 /* get number of bits to check in current dword */
107 Count = (Length > 32 - Shift) ? 32 - Shift : Length;
108
109 /* check dword */
110 if (~*Ptr++ & MASK(Count, Shift))
111 return FALSE;
112
113 Length -= Count;
114 StartingIndex += Count;
115 }
116
117 return TRUE;
118 }
119
120
121 /*
122 * @implemented
123 */
124 VOID
125 STDCALL
126 RtlClearAllBits (
127 IN OUT PRTL_BITMAP BitMapHeader
128 )
129 {
130 memset (BitMapHeader->Buffer,
131 0x00,
132 ALIGN(BitMapHeader->SizeOfBitMap, 8));
133 }
134
135 /*
136 * @unimplemented
137 */
138 VOID
139 STDCALL
140 RtlClearBit (
141 PRTL_BITMAP BitMapHeader,
142 ULONG BitNumber
143 )
144 {
145 UNIMPLEMENTED;
146 }
147
148 /*
149 * @implemented
150 */
151 VOID
152 STDCALL
153 RtlClearBits (
154 PRTL_BITMAP BitMapHeader,
155 ULONG StartingIndex,
156 ULONG NumberToClear
157 )
158 {
159 ULONG Size = BitMapHeader->SizeOfBitMap;
160 ULONG Count;
161 ULONG Shift;
162 PULONG Ptr;
163
164 if (StartingIndex >= Size || NumberToClear == 0)
165 return;
166
167 if (StartingIndex + NumberToClear > Size)
168 NumberToClear = Size - StartingIndex;
169
170 Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
171 while (NumberToClear)
172 {
173 /* bit shift in current dword */
174 Shift = StartingIndex & 0x1F;
175
176 /* number of bits to change in current dword */
177 Count = (NumberToClear > 32 - Shift ) ? 32 - Shift : NumberToClear;
178
179 /* adjust dword */
180 *Ptr++ &= ~MASK(Count, Shift);
181 NumberToClear -= Count;
182 StartingIndex += Count;
183 }
184 }
185
186
187 /*
188 * @implemented
189 */
190 ULONG
191 STDCALL
192 RtlFindClearBits (
193 PRTL_BITMAP BitMapHeader,
194 ULONG NumberToFind,
195 ULONG HintIndex
196 )
197 {
198 ULONG Size = BitMapHeader->SizeOfBitMap;
199 ULONG Index;
200 ULONG Count;
201 PULONG Ptr;
202 ULONG Mask;
203
204 if (NumberToFind > Size || NumberToFind == 0)
205 return -1;
206
207 if (HintIndex >= Size)
208 HintIndex = 0;
209
210 Index = HintIndex;
211 Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
212 Mask = 1 << (Index & 0x1F);
213
214 while (HintIndex < Size)
215 {
216 /* count clear bits */
217 for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
218 {
219 if (++Count >= NumberToFind)
220 return HintIndex;
221 Mask <<= 1;
222 if (Mask == 0)
223 {
224 Mask = 1;
225 Ptr++;
226 }
227 }
228
229 /* skip set bits */
230 for (; Index < Size && *Ptr & Mask; Index++)
231 {
232 Mask <<= 1;
233 if (Mask == 0)
234 {
235 Mask = 1;
236 Ptr++;
237 }
238 }
239 HintIndex = Index;
240 }
241
242 return -1;
243 }
244
245
246 /*
247 * @implemented
248 */
249 ULONG
250 STDCALL
251 RtlFindClearBitsAndSet (
252 PRTL_BITMAP BitMapHeader,
253 ULONG NumberToFind,
254 ULONG HintIndex
255 )
256 {
257 ULONG Index;
258
259 Index = RtlFindClearBits (BitMapHeader,
260 NumberToFind,
261 HintIndex);
262 if (Index != (ULONG)-1)
263 RtlSetBits (BitMapHeader,
264 Index,
265 NumberToFind);
266
267 return Index;
268 }
269
270
271 /*
272 * @implemented
273 */
274 ULONG
275 STDCALL
276 RtlFindFirstRunClear (
277 PRTL_BITMAP BitMapHeader,
278 PULONG StartingIndex
279 )
280 {
281 ULONG Size = BitMapHeader->SizeOfBitMap;
282 ULONG Index;
283 ULONG Count;
284 PULONG Ptr;
285 ULONG Mask;
286
287 if (*StartingIndex > Size)
288 {
289 *StartingIndex = (ULONG)-1;
290 return 0;
291 }
292
293 Index = *StartingIndex;
294 Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
295 Mask = 1 << (Index & 0x1F);
296
297 /* skip set bits */
298 for (; Index < Size && *Ptr & Mask; Index++)
299 {
300 Mask <<= 1;
301 if (Mask == 0)
302 {
303 Mask = 1;
304 Ptr++;
305 }
306 }
307
308 /* return index of first clear bit */
309 if (Index >= Size)
310 {
311 *StartingIndex = (ULONG)-1;
312 return 0;
313 }
314 else
315 *StartingIndex = Index;
316
317 /* count clear bits */
318 for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
319 {
320 Count++;
321 Mask <<= 1;
322 if (Mask == 0)
323 {
324 Mask = 1;
325 Ptr++;
326 }
327 }
328
329 return Count;
330 }
331
332 /*
333 * @unimplemented
334 */
335 ULONG
336 STDCALL
337 RtlFindClearRuns (
338 PRTL_BITMAP BitMapHeader,
339 PRTL_BITMAP_RUN RunArray,
340 ULONG SizeOfRunArray,
341 BOOLEAN LocateLongestRuns
342 )
343 {
344 UNIMPLEMENTED;
345 return 0;
346 }
347
348 /*
349 * @unimplemented
350 */
351 ULONG
352 STDCALL
353 RtlFindLastBackwardRunClear (
354 IN PRTL_BITMAP BitMapHeader,
355 IN ULONG FromIndex,
356 IN PULONG StartingRunIndex
357 )
358 {
359 UNIMPLEMENTED;
360 return 0;
361 }
362
363 /*
364 * @unimplemented
365 */
366 ULONG
367 STDCALL
368 RtlFindNextForwardRunClear (
369 IN PRTL_BITMAP BitMapHeader,
370 IN ULONG FromIndex,
371 IN PULONG StartingRunIndex
372 )
373 {
374 UNIMPLEMENTED;
375 return 0;
376 }
377
378 ULONG
379 STDCALL
380 RtlFindFirstRunSet (
381 PRTL_BITMAP BitMapHeader,
382 PULONG StartingIndex
383 )
384 {
385 ULONG Size = BitMapHeader->SizeOfBitMap;
386 ULONG Index;
387 ULONG Count;
388 PULONG Ptr;
389 ULONG Mask;
390
391 if (*StartingIndex > Size)
392 {
393 *StartingIndex = (ULONG)-1;
394 return 0;
395 }
396
397 Index = *StartingIndex;
398 Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
399 Mask = 1 << (Index & 0x1F);
400
401 /* skip clear bits */
402 for (; Index < Size && ~*Ptr & Mask; Index++)
403 {
404 Mask <<= 1;
405 if (Mask == 0)
406 {
407 Mask = 1;
408 Ptr++;
409 }
410 }
411
412 /* return index of first set bit */
413 if (Index >= Size)
414 {
415 *StartingIndex = (ULONG)-1;
416 return 0;
417 }
418 else
419 *StartingIndex = Index;
420
421 /* count set bits */
422 for (Count = 0; Index < Size && *Ptr & Mask; Index++)
423 {
424 Count++;
425 Mask <<= 1;
426 if (Mask == 0)
427 {
428 Mask = 1;
429 Ptr++;
430 }
431 }
432
433 return Count;
434 }
435
436
437 /*
438 * @implemented
439 */
440 ULONG
441 STDCALL
442 RtlFindLongestRunClear (
443 PRTL_BITMAP BitMapHeader,
444 PULONG StartingIndex
445 )
446 {
447 ULONG Size = BitMapHeader->SizeOfBitMap;
448 PULONG Ptr = (PULONG)BitMapHeader->Buffer;
449 ULONG Index = 0;
450 ULONG Count;
451 ULONG Max = 0;
452 ULONG Start;
453 ULONG Maxstart = 0;
454 ULONG Mask = 1;
455
456 while (Index < Size)
457 {
458 Start = Index;
459
460 /* count clear bits */
461 for (Count = 0; Index < Size && ~*Ptr & Mask; Index++)
462 {
463 Count++;
464 Mask <<= 1;
465 if (Mask == 0)
466 {
467 Mask = 1;
468 Ptr++;
469 }
470 }
471
472 /* skip set bits */
473 for (; Index < Size && *Ptr & Mask; Index++)
474 {
475 Mask <<= 1;
476 if (Mask == 0)
477 {
478 Mask = 1;
479 Ptr++;
480 }
481 }
482
483 if (Count > Max)
484 {
485 Max = Count;
486 Maxstart = Start;
487 }
488 }
489
490 if (StartingIndex)
491 *StartingIndex = Maxstart;
492
493 return Max;
494 }
495
496
497 ULONG
498 STDCALL
499 RtlFindLongestRunSet (
500 PRTL_BITMAP BitMapHeader,
501 PULONG StartingIndex
502 )
503 {
504 ULONG Size = BitMapHeader->SizeOfBitMap;
505 PULONG Ptr = (PULONG)BitMapHeader->Buffer;
506 ULONG Index = 0;
507 ULONG Count;
508 ULONG Max = 0;
509 ULONG Start;
510 ULONG Maxstart = 0;
511 ULONG Mask = 1;
512
513 while (Index < Size)
514 {
515 Start = Index;
516
517 /* count set bits */
518 for (Count = 0; Index < Size && *Ptr & Mask; Index++)
519 {
520 Count++;
521 Mask <<= 1;
522 if (Mask == 0)
523 {
524 Mask = 1;
525 Ptr++;
526 }
527 }
528
529 /* skip clear bits */
530 for (; Index < Size && ~*Ptr & Mask; Index++)
531 {
532 Mask <<= 1;
533 if (Mask == 0)
534 {
535 Mask = 1;
536 Ptr++;
537 }
538 }
539
540 if (Count > Max)
541 {
542 Max = Count;
543 Maxstart = Start;
544 }
545 }
546
547 if (StartingIndex)
548 *StartingIndex = Maxstart;
549
550 return Max;
551 }
552
553
554 /*
555 * @implemented
556 */
557 ULONG
558 STDCALL
559 RtlFindSetBits (
560 PRTL_BITMAP BitMapHeader,
561 ULONG NumberToFind,
562 ULONG HintIndex
563 )
564 {
565 ULONG Size = BitMapHeader->SizeOfBitMap;
566 ULONG Index;
567 ULONG Count;
568 PULONG Ptr;
569 ULONG Mask;
570
571 if (NumberToFind > Size || NumberToFind == 0)
572 return (ULONG)-1;
573
574 if (HintIndex >= Size)
575 HintIndex = 0;
576
577 Index = HintIndex;
578 Ptr = (PULONG)BitMapHeader->Buffer + (Index / 32);
579 Mask = 1 << (Index & 0x1F);
580
581 while (HintIndex < Size)
582 {
583 /* count set bits */
584 for (Count = 0; Index < Size && *Ptr & Mask; Index++)
585 {
586 if (++Count >= NumberToFind)
587 return HintIndex;
588 Mask <<= 1;
589 if (Mask == 0)
590 {
591 Mask = 1;
592 Ptr++;
593 }
594 }
595
596 /* skip clear bits */
597 for (; Index < Size && ~*Ptr & Mask; Index++)
598 {
599 Mask <<= 1;
600 if (Mask == 0)
601 {
602 Mask = 1;
603 Ptr++;
604 }
605 }
606 HintIndex = Index;
607 }
608
609 return (ULONG)-1;
610 }
611
612
613 /*
614 * @implemented
615 */
616 ULONG
617 STDCALL
618 RtlFindSetBitsAndClear (
619 PRTL_BITMAP BitMapHeader,
620 ULONG NumberToFind,
621 ULONG HintIndex
622 )
623 {
624 ULONG Index;
625
626 Index = RtlFindSetBits (BitMapHeader,
627 NumberToFind,
628 HintIndex);
629 if (Index != (ULONG)-1)
630 RtlClearBits (BitMapHeader,
631 Index,
632 NumberToFind);
633
634 return Index;
635 }
636
637
638 /*
639 * @implemented
640 */
641 ULONG
642 STDCALL
643 RtlNumberOfClearBits (
644 PRTL_BITMAP BitMapHeader
645 )
646 {
647 PULONG Ptr = (PULONG)BitMapHeader->Buffer;
648 ULONG Size = BitMapHeader->SizeOfBitMap;
649 ULONG Index;
650 ULONG Count;
651 ULONG Mask;
652
653 for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++)
654 {
655 if (~*Ptr & Mask)
656 Count++;
657
658 Mask <<= 1;
659 if (Mask == 0)
660 {
661 Mask = 1;
662 Ptr++;
663 }
664 }
665
666 return Count;
667 }
668
669
670 /*
671 * @implemented
672 */
673 ULONG
674 STDCALL
675 RtlNumberOfSetBits (
676 PRTL_BITMAP BitMapHeader
677 )
678 {
679 PULONG Ptr = (PULONG)BitMapHeader->Buffer;
680 ULONG Size = BitMapHeader->SizeOfBitMap;
681 ULONG Index;
682 ULONG Count;
683 ULONG Mask;
684
685 for (Mask = 1, Index = 0, Count = 0; Index < Size; Index++)
686 {
687 if (*Ptr & Mask)
688 Count++;
689
690 Mask <<= 1;
691 if (Mask == 0)
692 {
693 Mask = 1;
694 Ptr++;
695 }
696 }
697
698 return Count;
699 }
700
701
702 /*
703 * @implemented
704 */
705 VOID
706 STDCALL
707 RtlSetAllBits (
708 IN OUT PRTL_BITMAP BitMapHeader
709 )
710 {
711 memset (BitMapHeader->Buffer,
712 0xFF,
713 ALIGN(BitMapHeader->SizeOfBitMap, 8));
714 }
715
716 /*
717 * @unimplemented
718 */
719 VOID
720 STDCALL
721 RtlSetBit (
722 PRTL_BITMAP BitMapHeader,
723 ULONG BitNumber
724 )
725 {
726 UNIMPLEMENTED;
727 }
728
729 /*
730 * @implemented
731 */
732 VOID
733 STDCALL
734 RtlSetBits (
735 PRTL_BITMAP BitMapHeader,
736 ULONG StartingIndex,
737 ULONG NumberToSet
738 )
739 {
740 ULONG Size = BitMapHeader->SizeOfBitMap;
741 ULONG Count;
742 ULONG Shift;
743 PULONG Ptr;
744
745 if (StartingIndex >= Size || NumberToSet == 0)
746 return;
747
748 if (StartingIndex + NumberToSet > Size)
749 NumberToSet = Size - StartingIndex;
750
751 Ptr = (PULONG)BitMapHeader->Buffer + (StartingIndex / 32);
752 while (NumberToSet)
753 {
754 /* bit shift in current dword */
755 Shift = StartingIndex & 0x1F;
756
757 /* number of bits to change in current dword */
758 Count = (NumberToSet > 32 - Shift) ? 32 - Shift : NumberToSet;
759
760 /* adjust dword */
761 *Ptr++ |= MASK(Count, Shift);
762 NumberToSet -= Count;
763 StartingIndex += Count;
764 }
765 }
766
767 /*
768 * @unimplemented
769 */
770 BOOLEAN
771 STDCALL
772 RtlTestBit (
773 PRTL_BITMAP BitMapHeader,
774 ULONG BitNumber
775 )
776 {
777 UNIMPLEMENTED;
778 return FALSE;
779 }
780 /* EOF */