a2f5664c48d96c46e352fc7572966366cd78b0c8
[reactos.git] / reactos / lib / rtl / rangelist.c
1 /*
2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS system libraries
4 * FILE: lib/rtl/rangelist.c
5 * PURPOSE: Range list implementation
6 * PROGRAMMERS: No programmer listed.
7 */
8
9 /* INCLUDES *****************************************************************/
10
11 #include <rtl.h>
12
13 #define NDEBUG
14 #include <debug.h>
15
16 /* TYPES ********************************************************************/
17
18 typedef struct _RTL_RANGE_ENTRY
19 {
20 LIST_ENTRY Entry;
21 RTL_RANGE Range;
22 } RTL_RANGE_ENTRY, *PRTL_RANGE_ENTRY;
23
24 /* FUNCTIONS ***************************************************************/
25
26 /**********************************************************************
27 * NAME EXPORTED
28 * RtlAddRange
29 *
30 * DESCRIPTION
31 * Adds a range to a range list.
32 *
33 * ARGUMENTS
34 * RangeList Range list.
35 * Start
36 * End
37 * Attributes
38 * Flags
39 * UserData
40 * Owner
41 *
42 * RETURN VALUE
43 * Status
44 *
45 * TODO:
46 * - Support shared ranges.
47 *
48 * @implemented
49 */
50 NTSTATUS
51 NTAPI
52 RtlAddRange(IN OUT PRTL_RANGE_LIST RangeList,
53 IN ULONGLONG Start,
54 IN ULONGLONG End,
55 IN UCHAR Attributes,
56 IN ULONG Flags,
57 IN PVOID UserData OPTIONAL,
58 IN PVOID Owner OPTIONAL)
59 {
60 PRTL_RANGE_ENTRY RangeEntry;
61 //PRTL_RANGE_ENTRY Previous;
62 PRTL_RANGE_ENTRY Current;
63 PLIST_ENTRY Entry;
64
65 if (Start > End)
66 return STATUS_INVALID_PARAMETER;
67
68 /* Create new range entry */
69 RangeEntry = RtlpAllocateMemory(sizeof(RTL_RANGE_ENTRY), 'elRR');
70 if (RangeEntry == NULL)
71 return STATUS_INSUFFICIENT_RESOURCES;
72
73 /* Initialize range entry */
74 RangeEntry->Range.Start = Start;
75 RangeEntry->Range.End = End;
76 RangeEntry->Range.Attributes = Attributes;
77 RangeEntry->Range.UserData = UserData;
78 RangeEntry->Range.Owner = Owner;
79
80 RangeEntry->Range.Flags = 0;
81 if (Flags & RTL_RANGE_LIST_ADD_SHARED)
82 RangeEntry->Range.Flags |= RTL_RANGE_SHARED;
83
84 /* Insert range entry */
85 if (RangeList->Count == 0)
86 {
87 InsertTailList(&RangeList->ListHead,
88 &RangeEntry->Entry);
89 RangeList->Count++;
90 RangeList->Stamp++;
91 return STATUS_SUCCESS;
92 }
93 else
94 {
95 //Previous = NULL;
96 Entry = RangeList->ListHead.Flink;
97 while (Entry != &RangeList->ListHead)
98 {
99 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
100 if (Current->Range.Start > RangeEntry->Range.End)
101 {
102 /* Insert before current */
103 DPRINT("Insert before current\n");
104 InsertTailList(&Current->Entry,
105 &RangeEntry->Entry);
106
107 RangeList->Count++;
108 RangeList->Stamp++;
109 return STATUS_SUCCESS;
110 }
111
112 //Previous = Current;
113 Entry = Entry->Flink;
114 }
115
116 DPRINT("Insert tail\n");
117 InsertTailList(&RangeList->ListHead,
118 &RangeEntry->Entry);
119 RangeList->Count++;
120 RangeList->Stamp++;
121 return STATUS_SUCCESS;
122 }
123
124 RtlpFreeMemory(RangeEntry, 0);
125
126 return STATUS_UNSUCCESSFUL;
127 }
128
129
130 /**********************************************************************
131 * NAME EXPORTED
132 * RtlCopyRangeList
133 *
134 * DESCRIPTION
135 * Copy a range list.
136 *
137 * ARGUMENTS
138 * CopyRangeList Pointer to the destination range list.
139 * RangeList Pointer to the source range list.
140 *
141 * RETURN VALUE
142 * Status
143 *
144 * @implemented
145 */
146 NTSTATUS
147 NTAPI
148 RtlCopyRangeList(OUT PRTL_RANGE_LIST CopyRangeList,
149 IN PRTL_RANGE_LIST RangeList)
150 {
151 PRTL_RANGE_ENTRY Current;
152 PRTL_RANGE_ENTRY NewEntry;
153 PLIST_ENTRY Entry;
154
155 CopyRangeList->Flags = RangeList->Flags;
156
157 Entry = RangeList->ListHead.Flink;
158 while (Entry != &RangeList->ListHead)
159 {
160 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
161
162 NewEntry = RtlpAllocateMemory(sizeof(RTL_RANGE_ENTRY), 'elRR');
163 if (NewEntry == NULL)
164 return STATUS_INSUFFICIENT_RESOURCES;
165
166 RtlCopyMemory(&NewEntry->Range,
167 &Current->Range,
168 sizeof(RTL_RANGE_ENTRY));
169
170 InsertTailList(&CopyRangeList->ListHead,
171 &NewEntry->Entry);
172
173 CopyRangeList->Count++;
174
175 Entry = Entry->Flink;
176 }
177
178 CopyRangeList->Stamp++;
179
180 return STATUS_SUCCESS;
181 }
182
183
184 /**********************************************************************
185 * NAME EXPORTED
186 * RtlDeleteOwnersRanges
187 *
188 * DESCRIPTION
189 * Delete all ranges that belong to the given owner.
190 *
191 * ARGUMENTS
192 * RangeList Pointer to the range list.
193 * Owner User supplied value that identifies the owner
194 * of the ranges to be deleted.
195 *
196 * RETURN VALUE
197 * Status
198 *
199 * @implemented
200 */
201 NTSTATUS
202 NTAPI
203 RtlDeleteOwnersRanges(IN OUT PRTL_RANGE_LIST RangeList,
204 IN PVOID Owner)
205 {
206 PRTL_RANGE_ENTRY Current;
207 PLIST_ENTRY Entry;
208
209 Entry = RangeList->ListHead.Flink;
210 while (Entry != &RangeList->ListHead)
211 {
212 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
213 if (Current->Range.Owner == Owner)
214 {
215 RemoveEntryList (Entry);
216 RtlpFreeMemory(Current, 0);
217
218 RangeList->Count--;
219 RangeList->Stamp++;
220 }
221
222 Entry = Entry->Flink;
223 }
224
225 return STATUS_SUCCESS;
226 }
227
228
229 /**********************************************************************
230 * NAME EXPORTED
231 * RtlDeleteRange
232 *
233 * DESCRIPTION
234 * Deletes a given range.
235 *
236 * ARGUMENTS
237 * RangeList Pointer to the range list.
238 * Start Start of the range to be deleted.
239 * End End of the range to be deleted.
240 * Owner Owner of the ranges to be deleted.
241 *
242 * RETURN VALUE
243 * Status
244 *
245 * @implemented
246 */
247 NTSTATUS
248 NTAPI
249 RtlDeleteRange(IN OUT PRTL_RANGE_LIST RangeList,
250 IN ULONGLONG Start,
251 IN ULONGLONG End,
252 IN PVOID Owner)
253 {
254 PRTL_RANGE_ENTRY Current;
255 PLIST_ENTRY Entry;
256
257 Entry = RangeList->ListHead.Flink;
258 while (Entry != &RangeList->ListHead)
259 {
260 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
261 if (Current->Range.Start == Start &&
262 Current->Range.End == End &&
263 Current->Range.Owner == Owner)
264 {
265 RemoveEntryList(Entry);
266
267 RtlpFreeMemory(Current, 0);
268
269 RangeList->Count--;
270 RangeList->Stamp++;
271 return STATUS_SUCCESS;
272 }
273
274 Entry = Entry->Flink;
275 }
276
277 return STATUS_RANGE_NOT_FOUND;
278 }
279
280
281 /**********************************************************************
282 * NAME EXPORTED
283 * RtlFindRange
284 *
285 * DESCRIPTION
286 * Searches for an unused range.
287 *
288 * ARGUMENTS
289 * RangeList Pointer to the range list.
290 * Minimum
291 * Maximum
292 * Length
293 * Alignment
294 * Flags
295 * AttributeAvailableMask
296 * Context
297 * Callback
298 * Start
299 *
300 * RETURN VALUE
301 * Status
302 *
303 * TODO
304 * Support shared ranges and callback.
305 *
306 * @implemented
307 */
308 NTSTATUS
309 NTAPI
310 RtlFindRange(IN PRTL_RANGE_LIST RangeList,
311 IN ULONGLONG Minimum,
312 IN ULONGLONG Maximum,
313 IN ULONG Length,
314 IN ULONG Alignment,
315 IN ULONG Flags,
316 IN UCHAR AttributeAvailableMask,
317 IN PVOID Context OPTIONAL,
318 IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL,
319 OUT PULONGLONG Start)
320 {
321 PRTL_RANGE_ENTRY CurrentEntry;
322 PRTL_RANGE_ENTRY NextEntry;
323 PLIST_ENTRY Entry;
324 ULONGLONG RangeMin;
325 ULONGLONG RangeMax;
326
327 if (Alignment == 0 || Length == 0)
328 {
329 return STATUS_INVALID_PARAMETER;
330 }
331
332 if (IsListEmpty(&RangeList->ListHead))
333 {
334 *Start = ROUND_DOWN(Maximum - (Length - 1), Alignment);
335 return STATUS_SUCCESS;
336 }
337
338 NextEntry = NULL;
339 Entry = RangeList->ListHead.Blink;
340 while (Entry != &RangeList->ListHead)
341 {
342 CurrentEntry = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
343
344 RangeMax = NextEntry ? (NextEntry->Range.Start - 1) : Maximum;
345 if (RangeMax + (Length - 1) < Minimum)
346 {
347 return STATUS_RANGE_NOT_FOUND;
348 }
349
350 RangeMin = ROUND_DOWN(RangeMax - (Length - 1), Alignment);
351 if (RangeMin < Minimum ||
352 (RangeMax - RangeMin) < (Length - 1))
353 {
354 return STATUS_RANGE_NOT_FOUND;
355 }
356
357 DPRINT("RangeMax: %I64x\n", RangeMax);
358 DPRINT("RangeMin: %I64x\n", RangeMin);
359
360 if (RangeMin > CurrentEntry->Range.End)
361 {
362 *Start = RangeMin;
363 return STATUS_SUCCESS;
364 }
365
366 NextEntry = CurrentEntry;
367 Entry = Entry->Blink;
368 }
369
370 RangeMax = NextEntry ? (NextEntry->Range.Start - 1) : Maximum;
371 if (RangeMax + (Length - 1) < Minimum)
372 {
373 return STATUS_RANGE_NOT_FOUND;
374 }
375
376 RangeMin = ROUND_DOWN(RangeMax - (Length - 1), Alignment);
377 if (RangeMin < Minimum ||
378 (RangeMax - RangeMin) < (Length - 1))
379 {
380 return STATUS_RANGE_NOT_FOUND;
381 }
382
383 DPRINT("RangeMax: %I64x\n", RangeMax);
384 DPRINT("RangeMin: %I64x\n", RangeMin);
385
386 *Start = RangeMin;
387
388 return STATUS_SUCCESS;
389 }
390
391
392 /**********************************************************************
393 * NAME EXPORTED
394 * RtlFreeRangeList
395 *
396 * DESCRIPTION
397 * Deletes all ranges in a range list.
398 *
399 * ARGUMENTS
400 * RangeList Pointer to the range list.
401 *
402 * RETURN VALUE
403 * None
404 *
405 * @implemented
406 */
407 VOID
408 NTAPI
409 RtlFreeRangeList(IN PRTL_RANGE_LIST RangeList)
410 {
411 PLIST_ENTRY Entry;
412 PRTL_RANGE_ENTRY Current;
413
414 while (!IsListEmpty(&RangeList->ListHead))
415 {
416 Entry = RemoveHeadList(&RangeList->ListHead);
417 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
418
419 DPRINT ("Range start: %I64u\n", Current->Range.Start);
420 DPRINT ("Range end: %I64u\n", Current->Range.End);
421
422 RtlpFreeMemory(Current, 0);
423 }
424
425 RangeList->Flags = 0;
426 RangeList->Count = 0;
427 }
428
429
430 /**********************************************************************
431 * NAME EXPORTED
432 * RtlGetFirstRange
433 *
434 * DESCRIPTION
435 * Retrieves the first range of a range list.
436 *
437 * ARGUMENTS
438 * RangeList Pointer to the range list.
439 * Iterator Pointer to a user supplied list state buffer.
440 * Range Pointer to the first range.
441 *
442 * RETURN VALUE
443 * Status
444 *
445 * @implemented
446 */
447 NTSTATUS
448 NTAPI
449 RtlGetFirstRange(IN PRTL_RANGE_LIST RangeList,
450 OUT PRTL_RANGE_LIST_ITERATOR Iterator,
451 OUT PRTL_RANGE *Range)
452 {
453 Iterator->RangeListHead = &RangeList->ListHead;
454 Iterator->MergedHead = NULL;
455 Iterator->Stamp = RangeList->Stamp;
456
457 if (IsListEmpty(&RangeList->ListHead))
458 {
459 Iterator->Current = NULL;
460 *Range = NULL;
461 return STATUS_NO_MORE_ENTRIES;
462 }
463
464 Iterator->Current = RangeList->ListHead.Flink;
465 *Range = &((PRTL_RANGE_ENTRY)Iterator->Current)->Range;
466
467 return STATUS_SUCCESS;
468 }
469
470
471 /**********************************************************************
472 * NAME EXPORTED
473 * RtlGetNextRange
474 *
475 * DESCRIPTION
476 * Retrieves the next (or previous) range of a range list.
477 *
478 * ARGUMENTS
479 * Iterator Pointer to a user supplied list state buffer.
480 * Range Pointer to the first range.
481 * MoveForwards TRUE, get next range
482 * FALSE, get previous range
483 *
484 * RETURN VALUE
485 * Status
486 *
487 * @implemented
488 */
489 NTSTATUS
490 NTAPI
491 RtlGetNextRange(IN OUT PRTL_RANGE_LIST_ITERATOR Iterator,
492 OUT PRTL_RANGE *Range,
493 IN BOOLEAN MoveForwards)
494 {
495 PRTL_RANGE_LIST RangeList;
496 PLIST_ENTRY Next;
497
498 RangeList = CONTAINING_RECORD(Iterator->RangeListHead, RTL_RANGE_LIST, ListHead);
499 if (Iterator->Stamp != RangeList->Stamp)
500 return STATUS_INVALID_PARAMETER;
501
502 if (MoveForwards)
503 {
504 Next = ((PRTL_RANGE_ENTRY)Iterator->Current)->Entry.Flink;
505 }
506 else
507 {
508 Next = ((PRTL_RANGE_ENTRY)Iterator->Current)->Entry.Blink;
509 }
510
511 if (Next == Iterator->RangeListHead)
512 return STATUS_NO_MORE_ENTRIES;
513
514 Iterator->Current = Next;
515 *Range = &((PRTL_RANGE_ENTRY)Next)->Range;
516
517 return STATUS_SUCCESS;
518 }
519
520
521 /**********************************************************************
522 * NAME EXPORTED
523 * RtlInitializeRangeList
524 *
525 * DESCRIPTION
526 * Initializes a range list.
527 *
528 * ARGUMENTS
529 * RangeList Pointer to a user supplied range list.
530 *
531 * RETURN VALUE
532 * None
533 *
534 * @implemented
535 */
536 VOID
537 NTAPI
538 RtlInitializeRangeList(IN OUT PRTL_RANGE_LIST RangeList)
539 {
540 InitializeListHead(&RangeList->ListHead);
541 RangeList->Flags = 0;
542 RangeList->Count = 0;
543 RangeList->Stamp = 0;
544 }
545
546
547 /**********************************************************************
548 * NAME EXPORTED
549 * RtlInvertRangeList
550 *
551 * DESCRIPTION
552 * Inverts a range list.
553 *
554 * ARGUMENTS
555 * InvertedRangeList Inverted range list.
556 * RangeList Range list.
557 *
558 * RETURN VALUE
559 * Status
560 *
561 * @implemented
562 */
563 NTSTATUS
564 NTAPI
565 RtlInvertRangeList(OUT PRTL_RANGE_LIST InvertedRangeList,
566 IN PRTL_RANGE_LIST RangeList)
567 {
568 PRTL_RANGE_ENTRY Previous;
569 PRTL_RANGE_ENTRY Current;
570 PLIST_ENTRY Entry;
571 NTSTATUS Status;
572
573 /* Don't invert an empty range list */
574 if (IsListEmpty(&RangeList->ListHead))
575 {
576 return STATUS_SUCCESS;
577 }
578
579 /* Add leading and intermediate ranges */
580 Previous = NULL;
581 Entry = RangeList->ListHead.Flink;
582 while (Entry != &RangeList->ListHead)
583 {
584 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
585
586 if (Previous == NULL)
587 {
588 if (Current->Range.Start != (ULONGLONG)0)
589 {
590 Status = RtlAddRange(InvertedRangeList,
591 (ULONGLONG)0,
592 Current->Range.Start - 1,
593 0,
594 0,
595 NULL,
596 NULL);
597 if (!NT_SUCCESS(Status))
598 return Status;
599 }
600 }
601 else
602 {
603 if (Previous->Range.End + 1 != Current->Range.Start)
604 {
605 Status = RtlAddRange(InvertedRangeList,
606 Previous->Range.End + 1,
607 Current->Range.Start - 1,
608 0,
609 0,
610 NULL,
611 NULL);
612 if (!NT_SUCCESS(Status))
613 return Status;
614 }
615 }
616
617 Previous = Current;
618 Entry = Entry->Flink;
619 }
620
621 /* Add trailing range */
622 if (Previous->Range.End + 1 != (ULONGLONG)-1)
623 {
624 Status = RtlAddRange(InvertedRangeList,
625 Previous->Range.End + 1,
626 (ULONGLONG)-1,
627 0,
628 0,
629 NULL,
630 NULL);
631 if (!NT_SUCCESS(Status))
632 return Status;
633 }
634
635 return STATUS_SUCCESS;
636 }
637
638
639 /**********************************************************************
640 * NAME EXPORTED
641 * RtlIsRangeAvailable
642 *
643 * DESCRIPTION
644 * Checks whether a range is available or not.
645 *
646 * ARGUMENTS
647 * RangeList Pointer to the range list.
648 * Start
649 * End
650 * Flags
651 * AttributeAvailableMask
652 * Context
653 * Callback
654 * Available
655 *
656 * RETURN VALUE
657 * Status
658 *
659 * TODO:
660 * - honor Flags and AttributeAvailableMask.
661 *
662 * @implemented
663 */
664 NTSTATUS
665 NTAPI
666 RtlIsRangeAvailable(IN PRTL_RANGE_LIST RangeList,
667 IN ULONGLONG Start,
668 IN ULONGLONG End,
669 IN ULONG Flags,
670 IN UCHAR AttributeAvailableMask,
671 IN PVOID Context OPTIONAL,
672 IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL,
673 OUT PBOOLEAN Available)
674 {
675 PRTL_RANGE_ENTRY Current;
676 PLIST_ENTRY Entry;
677
678 *Available = TRUE;
679
680 Entry = RangeList->ListHead.Flink;
681 while (Entry != &RangeList->ListHead)
682 {
683 Current = CONTAINING_RECORD (Entry, RTL_RANGE_ENTRY, Entry);
684
685 if (!((Current->Range.Start >= End && Current->Range.End > End) ||
686 (Current->Range.Start <= Start && Current->Range.End < Start &&
687 (!(Flags & RTL_RANGE_SHARED) ||
688 !(Current->Range.Flags & RTL_RANGE_SHARED)))))
689 {
690 if (Callback != NULL)
691 {
692 *Available = Callback(Context,
693 &Current->Range);
694 }
695 else
696 {
697 *Available = FALSE;
698 }
699 }
700
701 Entry = Entry->Flink;
702 }
703
704 return STATUS_SUCCESS;
705 }
706
707
708 /**********************************************************************
709 * NAME EXPORTED
710 * RtlMergeRangeList
711 *
712 * DESCRIPTION
713 * Merges two range lists.
714 *
715 * ARGUMENTS
716 * MergedRangeList Resulting range list.
717 * RangeList1 First range list.
718 * RangeList2 Second range list
719 * Flags
720 *
721 * RETURN VALUE
722 * Status
723 *
724 * @implemented
725 */
726 NTSTATUS
727 NTAPI
728 RtlMergeRangeLists(OUT PRTL_RANGE_LIST MergedRangeList,
729 IN PRTL_RANGE_LIST RangeList1,
730 IN PRTL_RANGE_LIST RangeList2,
731 IN ULONG Flags)
732 {
733 RTL_RANGE_LIST_ITERATOR Iterator;
734 PRTL_RANGE Range;
735 NTSTATUS Status;
736
737 /* Copy range list 1 to the merged range list */
738 Status = RtlCopyRangeList(MergedRangeList,
739 RangeList1);
740 if (!NT_SUCCESS(Status))
741 return Status;
742
743 /* Add range list 2 entries to the merged range list */
744 Status = RtlGetFirstRange(RangeList2,
745 &Iterator,
746 &Range);
747 if (!NT_SUCCESS(Status))
748 return (Status == STATUS_NO_MORE_ENTRIES) ? STATUS_SUCCESS : Status;
749
750 while (TRUE)
751 {
752 Status = RtlAddRange(MergedRangeList,
753 Range->Start,
754 Range->End,
755 Range->Attributes,
756 Range->Flags | Flags,
757 Range->UserData,
758 Range->Owner);
759 if (!NT_SUCCESS(Status))
760 break;
761
762 Status = RtlGetNextRange(&Iterator,
763 &Range,
764 TRUE);
765 if (!NT_SUCCESS(Status))
766 break;
767 }
768
769 return (Status == STATUS_NO_MORE_ENTRIES) ? STATUS_SUCCESS : Status;
770 }
771
772 /* EOF */