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.
9 /* INCLUDES *****************************************************************/
16 /* TYPES ********************************************************************/
18 typedef struct _RTL_RANGE_ENTRY
22 } RTL_RANGE_ENTRY
, *PRTL_RANGE_ENTRY
;
24 /* FUNCTIONS ***************************************************************/
26 /**********************************************************************
31 * Adds a range to a range list.
34 * RangeList Range list.
46 * - Support shared ranges.
51 RtlAddRange (IN OUT PRTL_RANGE_LIST RangeList
,
56 IN PVOID UserData OPTIONAL
,
57 IN PVOID Owner OPTIONAL
)
59 PRTL_RANGE_ENTRY RangeEntry
;
60 PRTL_RANGE_ENTRY Previous
;
61 PRTL_RANGE_ENTRY Current
;
65 return STATUS_INVALID_PARAMETER
;
67 /* Create new range entry */
68 RangeEntry
= RtlpAllocateMemory(sizeof(RTL_RANGE_ENTRY
), 'elRR');
69 if (RangeEntry
== NULL
)
70 return STATUS_INSUFFICIENT_RESOURCES
;
72 /* Initialize range entry */
73 RangeEntry
->Range
.Start
= Start
;
74 RangeEntry
->Range
.End
= End
;
75 RangeEntry
->Range
.Attributes
= Attributes
;
76 RangeEntry
->Range
.UserData
= UserData
;
77 RangeEntry
->Range
.Owner
= Owner
;
79 RangeEntry
->Range
.Flags
= 0;
80 if (Flags
& RTL_RANGE_LIST_ADD_SHARED
)
81 RangeEntry
->Range
.Flags
|= RTL_RANGE_SHARED
;
83 /* Insert range entry */
84 if (RangeList
->Count
== 0)
86 InsertTailList (&RangeList
->ListHead
,
90 return STATUS_SUCCESS
;
95 Entry
= RangeList
->ListHead
.Flink
;
96 while (Entry
!= &RangeList
->ListHead
)
98 Current
= CONTAINING_RECORD (Entry
, RTL_RANGE_ENTRY
, Entry
);
99 if (Current
->Range
.Start
> RangeEntry
->Range
.End
)
101 /* Insert before current */
102 DPRINT ("Insert before current\n");
103 InsertTailList (&Current
->Entry
,
108 return STATUS_SUCCESS
;
112 Entry
= Entry
->Flink
;
115 DPRINT ("Insert tail\n");
116 InsertTailList (&RangeList
->ListHead
,
120 return STATUS_SUCCESS
;
123 RtlpFreeMemory(RangeEntry
, 0);
125 return STATUS_UNSUCCESSFUL
;
129 /**********************************************************************
137 * CopyRangeList Pointer to the destination range list.
138 * RangeList Pointer to the source range list.
146 RtlCopyRangeList (OUT PRTL_RANGE_LIST CopyRangeList
,
147 IN PRTL_RANGE_LIST RangeList
)
149 PRTL_RANGE_ENTRY Current
;
150 PRTL_RANGE_ENTRY NewEntry
;
153 CopyRangeList
->Flags
= RangeList
->Flags
;
155 Entry
= RangeList
->ListHead
.Flink
;
156 while (Entry
!= &RangeList
->ListHead
)
158 Current
= CONTAINING_RECORD (Entry
, RTL_RANGE_ENTRY
, Entry
);
160 NewEntry
= RtlpAllocateMemory(sizeof(RTL_RANGE_ENTRY
), 'elRR');
161 if (NewEntry
== NULL
)
162 return STATUS_INSUFFICIENT_RESOURCES
;
164 RtlCopyMemory (&NewEntry
->Range
,
166 sizeof(RTL_RANGE_ENTRY
));
168 InsertTailList (&CopyRangeList
->ListHead
,
171 CopyRangeList
->Count
++;
173 Entry
= Entry
->Flink
;
176 CopyRangeList
->Stamp
++;
178 return STATUS_SUCCESS
;
182 /**********************************************************************
184 * RtlDeleteOwnersRanges
187 * Delete all ranges that belong to the given owner.
190 * RangeList Pointer to the range list.
191 * Owner User supplied value that identifies the owner
192 * of the ranges to be deleted.
200 RtlDeleteOwnersRanges (IN OUT PRTL_RANGE_LIST RangeList
,
203 PRTL_RANGE_ENTRY Current
;
206 Entry
= RangeList
->ListHead
.Flink
;
207 while (Entry
!= &RangeList
->ListHead
)
209 Current
= CONTAINING_RECORD (Entry
, RTL_RANGE_ENTRY
, Entry
);
210 if (Current
->Range
.Owner
== Owner
)
212 RemoveEntryList (Entry
);
213 RtlpFreeMemory(Current
, 0);
219 Entry
= Entry
->Flink
;
222 return STATUS_SUCCESS
;
226 /**********************************************************************
231 * Deletes a given range.
234 * RangeList Pointer to the range list.
235 * Start Start of the range to be deleted.
236 * End End of the range to be deleted.
237 * Owner Owner of the ranges to be deleted.
245 RtlDeleteRange (IN OUT PRTL_RANGE_LIST RangeList
,
250 PRTL_RANGE_ENTRY Current
;
253 Entry
= RangeList
->ListHead
.Flink
;
254 while (Entry
!= &RangeList
->ListHead
)
256 Current
= CONTAINING_RECORD (Entry
, RTL_RANGE_ENTRY
, Entry
);
257 if (Current
->Range
.Start
== Start
&&
258 Current
->Range
.End
== End
&&
259 Current
->Range
.Owner
== Owner
)
261 RemoveEntryList (Entry
);
263 RtlpFreeMemory(Current
, 0);
267 return STATUS_SUCCESS
;
270 Entry
= Entry
->Flink
;
273 return STATUS_RANGE_NOT_FOUND
;
277 /**********************************************************************
282 * Searches for an unused range.
285 * RangeList Pointer to the range list.
291 * AttributeAvailableMask
300 * Support shared ranges and callback.
305 RtlFindRange (IN PRTL_RANGE_LIST RangeList
,
306 IN ULONGLONG Minimum
,
307 IN ULONGLONG Maximum
,
311 IN UCHAR AttributeAvailableMask
,
312 IN PVOID Context OPTIONAL
,
313 IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL
,
314 OUT PULONGLONG Start
)
316 PRTL_RANGE_ENTRY CurrentEntry
;
317 PRTL_RANGE_ENTRY NextEntry
;
322 if (Alignment
== 0 || Length
== 0)
324 return STATUS_INVALID_PARAMETER
;
327 if (IsListEmpty(&RangeList
->ListHead
))
329 *Start
= ROUND_DOWN (Maximum
- (Length
- 1), Alignment
);
330 return STATUS_SUCCESS
;
334 Entry
= RangeList
->ListHead
.Blink
;
335 while (Entry
!= &RangeList
->ListHead
)
337 CurrentEntry
= CONTAINING_RECORD (Entry
, RTL_RANGE_ENTRY
, Entry
);
339 RangeMax
= NextEntry
? (NextEntry
->Range
.Start
- 1) : Maximum
;
340 if (RangeMax
+ (Length
- 1) < Minimum
)
342 return STATUS_RANGE_NOT_FOUND
;
345 RangeMin
= ROUND_DOWN (RangeMax
- (Length
- 1), Alignment
);
346 if (RangeMin
< Minimum
||
347 (RangeMax
- RangeMin
) < (Length
- 1))
349 return STATUS_RANGE_NOT_FOUND
;
352 DPRINT("RangeMax: %I64x\n", RangeMax
);
353 DPRINT("RangeMin: %I64x\n", RangeMin
);
355 if (RangeMin
> CurrentEntry
->Range
.End
)
358 return STATUS_SUCCESS
;
361 NextEntry
= CurrentEntry
;
362 Entry
= Entry
->Blink
;
365 RangeMax
= NextEntry
? (NextEntry
->Range
.Start
- 1) : Maximum
;
366 if (RangeMax
+ (Length
- 1) < Minimum
)
368 return STATUS_RANGE_NOT_FOUND
;
371 RangeMin
= ROUND_DOWN (RangeMax
- (Length
- 1), Alignment
);
372 if (RangeMin
< Minimum
||
373 (RangeMax
- RangeMin
) < (Length
- 1))
375 return STATUS_RANGE_NOT_FOUND
;
378 DPRINT("RangeMax: %I64x\n", RangeMax
);
379 DPRINT("RangeMin: %I64x\n", RangeMin
);
383 return STATUS_SUCCESS
;
387 /**********************************************************************
392 * Deletes all ranges in a range list.
395 * RangeList Pointer to the range list.
403 RtlFreeRangeList (IN PRTL_RANGE_LIST RangeList
)
406 PRTL_RANGE_ENTRY Current
;
408 while (!IsListEmpty(&RangeList
->ListHead
))
410 Entry
= RemoveHeadList (&RangeList
->ListHead
);
411 Current
= CONTAINING_RECORD (Entry
, RTL_RANGE_ENTRY
, Entry
);
413 DPRINT ("Range start: %I64u\n", Current
->Range
.Start
);
414 DPRINT ("Range end: %I64u\n", Current
->Range
.End
);
416 RtlpFreeMemory(Current
, 0);
419 RangeList
->Flags
= 0;
420 RangeList
->Count
= 0;
424 /**********************************************************************
429 * Retrieves the first range of a range list.
432 * RangeList Pointer to the range list.
433 * Iterator Pointer to a user supplied list state buffer.
434 * Range Pointer to the first range.
442 RtlGetFirstRange (IN PRTL_RANGE_LIST RangeList
,
443 OUT PRTL_RANGE_LIST_ITERATOR Iterator
,
444 OUT PRTL_RANGE
*Range
)
446 Iterator
->RangeListHead
= &RangeList
->ListHead
;
447 Iterator
->MergedHead
= NULL
;
448 Iterator
->Stamp
= RangeList
->Stamp
;
449 if (IsListEmpty(&RangeList
->ListHead
))
451 Iterator
->Current
= NULL
;
453 return STATUS_NO_MORE_ENTRIES
;
456 Iterator
->Current
= RangeList
->ListHead
.Flink
;
457 *Range
= &((PRTL_RANGE_ENTRY
)Iterator
->Current
)->Range
;
459 return STATUS_SUCCESS
;
463 /**********************************************************************
468 * Retrieves the next (or previous) range of a range list.
471 * Iterator Pointer to a user supplied list state buffer.
472 * Range Pointer to the first range.
473 * MoveForwards TRUE, get next range
474 * FALSE, get previous range
482 RtlGetNextRange (IN OUT PRTL_RANGE_LIST_ITERATOR Iterator
,
483 OUT PRTL_RANGE
*Range
,
484 IN BOOLEAN MoveForwards
)
486 PRTL_RANGE_LIST RangeList
;
489 RangeList
= CONTAINING_RECORD(Iterator
->RangeListHead
, RTL_RANGE_LIST
, ListHead
);
490 if (Iterator
->Stamp
!= RangeList
->Stamp
)
491 return STATUS_INVALID_PARAMETER
;
495 Next
= ((PRTL_RANGE_ENTRY
)Iterator
->Current
)->Entry
.Flink
;
499 Next
= ((PRTL_RANGE_ENTRY
)Iterator
->Current
)->Entry
.Blink
;
502 if (Next
== Iterator
->RangeListHead
)
503 return STATUS_NO_MORE_ENTRIES
;
505 Iterator
->Current
= Next
;
506 *Range
= &((PRTL_RANGE_ENTRY
)Next
)->Range
;
508 return STATUS_SUCCESS
;
512 /**********************************************************************
514 * RtlInitializeRangeList
517 * Initializes a range list.
520 * RangeList Pointer to a user supplied range list.
528 RtlInitializeRangeList (IN OUT PRTL_RANGE_LIST RangeList
)
530 InitializeListHead (&RangeList
->ListHead
);
531 RangeList
->Flags
= 0;
532 RangeList
->Count
= 0;
533 RangeList
->Stamp
= 0;
537 /**********************************************************************
542 * Inverts a range list.
545 * InvertedRangeList Inverted range list.
546 * RangeList Range list.
554 RtlInvertRangeList (OUT PRTL_RANGE_LIST InvertedRangeList
,
555 IN PRTL_RANGE_LIST RangeList
)
557 PRTL_RANGE_ENTRY Previous
;
558 PRTL_RANGE_ENTRY Current
;
562 /* Don't invert an empty range list */
563 if (IsListEmpty(&RangeList
->ListHead
))
565 return STATUS_SUCCESS
;
568 /* Add leading and intermediate ranges */
570 Entry
= RangeList
->ListHead
.Flink
;
571 while (Entry
!= &RangeList
->ListHead
)
573 Current
= CONTAINING_RECORD (Entry
, RTL_RANGE_ENTRY
, Entry
);
575 if (Previous
== NULL
)
577 if (Current
->Range
.Start
!= (ULONGLONG
)0)
579 Status
= RtlAddRange (InvertedRangeList
,
581 Current
->Range
.Start
- 1,
586 if (!NT_SUCCESS(Status
))
592 if (Previous
->Range
.End
+ 1 != Current
->Range
.Start
)
594 Status
= RtlAddRange (InvertedRangeList
,
595 Previous
->Range
.End
+ 1,
596 Current
->Range
.Start
- 1,
601 if (!NT_SUCCESS(Status
))
607 Entry
= Entry
->Flink
;
610 /* Add trailing range */
611 if (Previous
->Range
.End
+ 1 != (ULONGLONG
)-1)
613 Status
= RtlAddRange (InvertedRangeList
,
614 Previous
->Range
.End
+ 1,
620 if (!NT_SUCCESS(Status
))
624 return STATUS_SUCCESS
;
628 /**********************************************************************
630 * RtlIsRangeAvailable
633 * Checks whether a range is available or not.
636 * RangeList Pointer to the range list.
640 * AttributeAvailableMask
649 * - honor Flags and AttributeAvailableMask.
654 RtlIsRangeAvailable (IN PRTL_RANGE_LIST RangeList
,
658 IN UCHAR AttributeAvailableMask
,
659 IN PVOID Context OPTIONAL
,
660 IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL
,
661 OUT PBOOLEAN Available
)
663 PRTL_RANGE_ENTRY Current
;
668 Entry
= RangeList
->ListHead
.Flink
;
669 while (Entry
!= &RangeList
->ListHead
)
671 Current
= CONTAINING_RECORD (Entry
, RTL_RANGE_ENTRY
, Entry
);
672 if (!((Current
->Range
.Start
>= End
&& Current
->Range
.End
> End
) ||
673 (Current
->Range
.Start
<= Start
&& Current
->Range
.End
< Start
&&
674 (!(Flags
& RTL_RANGE_SHARED
) ||
675 !(Current
->Range
.Flags
& RTL_RANGE_SHARED
)))))
677 if (Callback
!= NULL
)
679 *Available
= Callback (Context
,
688 Entry
= Entry
->Flink
;
691 return STATUS_SUCCESS
;
695 /**********************************************************************
700 * Merges two range lists.
703 * MergedRangeList Resulting range list.
704 * RangeList1 First range list.
705 * RangeList2 Second range list
714 RtlMergeRangeLists (OUT PRTL_RANGE_LIST MergedRangeList
,
715 IN PRTL_RANGE_LIST RangeList1
,
716 IN PRTL_RANGE_LIST RangeList2
,
719 RTL_RANGE_LIST_ITERATOR Iterator
;
723 /* Copy range list 1 to the merged range list */
724 Status
= RtlCopyRangeList (MergedRangeList
,
726 if (!NT_SUCCESS(Status
))
729 /* Add range list 2 entries to the merged range list */
730 Status
= RtlGetFirstRange (RangeList2
,
733 if (!NT_SUCCESS(Status
))
734 return (Status
== STATUS_NO_MORE_ENTRIES
) ? STATUS_SUCCESS
: Status
;
738 Status
= RtlAddRange (MergedRangeList
,
742 Range
->Flags
| Flags
,
745 if (!NT_SUCCESS(Status
))
748 Status
= RtlGetNextRange (&Iterator
,
751 if (!NT_SUCCESS(Status
))
755 return (Status
== STATUS_NO_MORE_ENTRIES
) ? STATUS_SUCCESS
: Status
;