ReactOS 0.4.15-dev-7918-g2a2556c
rangelist.c File Reference
#include <rtl.h>
#include <debug.h>
Include dependency graph for rangelist.c:

Go to the source code of this file.

Classes

struct  _RTL_RANGE_ENTRY
 

Macros

#define NDEBUG
 

Typedefs

typedef struct _RTL_RANGE_ENTRY RTL_RANGE_ENTRY
 
typedef struct _RTL_RANGE_ENTRYPRTL_RANGE_ENTRY
 

Functions

NTSTATUS NTAPI RtlAddRange (IN OUT PRTL_RANGE_LIST RangeList, IN ULONGLONG Start, IN ULONGLONG End, IN UCHAR Attributes, IN ULONG Flags, IN PVOID UserData OPTIONAL, IN PVOID Owner OPTIONAL)
 
NTSTATUS NTAPI RtlCopyRangeList (OUT PRTL_RANGE_LIST CopyRangeList, IN PRTL_RANGE_LIST RangeList)
 
NTSTATUS NTAPI RtlDeleteOwnersRanges (IN OUT PRTL_RANGE_LIST RangeList, IN PVOID Owner)
 
NTSTATUS NTAPI RtlDeleteRange (IN OUT PRTL_RANGE_LIST RangeList, IN ULONGLONG Start, IN ULONGLONG End, IN PVOID Owner)
 
NTSTATUS NTAPI RtlFindRange (IN PRTL_RANGE_LIST RangeList, IN ULONGLONG Minimum, IN ULONGLONG Maximum, IN ULONG Length, IN ULONG Alignment, IN ULONG Flags, IN UCHAR AttributeAvailableMask, IN PVOID Context OPTIONAL, IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL, OUT PULONGLONG Start)
 
VOID NTAPI RtlFreeRangeList (IN PRTL_RANGE_LIST RangeList)
 
NTSTATUS NTAPI RtlGetFirstRange (IN PRTL_RANGE_LIST RangeList, OUT PRTL_RANGE_LIST_ITERATOR Iterator, OUT PRTL_RANGE *Range)
 
NTSTATUS NTAPI RtlGetNextRange (IN OUT PRTL_RANGE_LIST_ITERATOR Iterator, OUT PRTL_RANGE *Range, IN BOOLEAN MoveForwards)
 
VOID NTAPI RtlInitializeRangeList (IN OUT PRTL_RANGE_LIST RangeList)
 
NTSTATUS NTAPI RtlInvertRangeList (OUT PRTL_RANGE_LIST InvertedRangeList, IN PRTL_RANGE_LIST RangeList)
 
NTSTATUS NTAPI RtlIsRangeAvailable (IN PRTL_RANGE_LIST RangeList, IN ULONGLONG Start, IN ULONGLONG End, IN ULONG Flags, IN UCHAR AttributeAvailableMask, IN PVOID Context OPTIONAL, IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL, OUT PBOOLEAN Available)
 
NTSTATUS NTAPI RtlMergeRangeLists (OUT PRTL_RANGE_LIST MergedRangeList, IN PRTL_RANGE_LIST RangeList1, IN PRTL_RANGE_LIST RangeList2, IN ULONG Flags)
 

Macro Definition Documentation

◆ NDEBUG

#define NDEBUG

Definition at line 13 of file rangelist.c.

Typedef Documentation

◆ PRTL_RANGE_ENTRY

◆ RTL_RANGE_ENTRY

Function Documentation

◆ RtlAddRange()

NTSTATUS NTAPI RtlAddRange ( IN OUT PRTL_RANGE_LIST  RangeList,
IN ULONGLONG  Start,
IN ULONGLONG  End,
IN UCHAR  Attributes,
IN ULONG  Flags,
IN PVOID UserData  OPTIONAL,
IN PVOID Owner  OPTIONAL 
)

Definition at line 52 of file rangelist.c.

59{
60 PRTL_RANGE_ENTRY RangeEntry;
61 //PRTL_RANGE_ENTRY Previous;
62 PRTL_RANGE_ENTRY Current;
64
65 if (Start > End)
67
68 /* Create new range entry */
69 RangeEntry = RtlpAllocateMemory(sizeof(RTL_RANGE_ENTRY), 'elRR');
70 if (RangeEntry == NULL)
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;
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 {
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}
#define NULL
Definition: types.h:112
#define InsertTailList(ListHead, Entry)
struct tagUserData UserData
_Out_writes_bytes_to_opt_ AbsoluteSecurityDescriptorSize PSECURITY_DESCRIPTOR _Inout_ PULONG _Out_writes_bytes_to_opt_ DaclSize PACL _Inout_ PULONG _Out_writes_bytes_to_opt_ SaclSize PACL _Inout_ PULONG _Out_writes_bytes_to_opt_ OwnerSize PSID Owner
Definition: rtlfuncs.h:1597
#define RTL_RANGE_LIST_ADD_SHARED
Definition: rtltypes.h:82
#define RTL_RANGE_SHARED
Definition: rtltypes.h:84
PVOID NTAPI RtlpAllocateMemory(_In_ ULONG Bytes, _In_ ULONG Tag)
Definition: rtlcompat.c:34
VOID NTAPI RtlpFreeMemory(_In_ PVOID Mem, _In_ ULONG Tag)
Definition: rtlcompat.c:45
#define STATUS_SUCCESS
Definition: shellext.h:65
#define DPRINT
Definition: sndvol32.h:71
base of all file and directory entries
Definition: entries.h:83
Definition: typedefs.h:120
Definition: libsupp.c:19
LIST_ENTRY Entry
Definition: libsupp.c:20
RTL_RANGE Range
Definition: libsupp.c:21
ULONGLONG End
Definition: rtltypes.h:1470
ULONGLONG Start
Definition: rtltypes.h:1469
UCHAR Attributes
Definition: rtltypes.h:1473
PVOID UserData
Definition: rtltypes.h:1471
PVOID Owner
Definition: rtltypes.h:1472
UCHAR Flags
Definition: rtltypes.h:1474
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
#define STATUS_INVALID_PARAMETER
Definition: udferr_usr.h:135
#define STATUS_UNSUCCESSFUL
Definition: udferr_usr.h:132
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
@ Start
Definition: partlist.h:33
_Must_inspect_result_ _In_ WDFDMAENABLER _In_ _In_opt_ PWDF_OBJECT_ATTRIBUTES Attributes
_Must_inspect_result_ _In_ ULONG Flags
Definition: wsk.h:170

Referenced by RtlInvertRangeList(), and RtlMergeRangeLists().

◆ RtlCopyRangeList()

NTSTATUS NTAPI RtlCopyRangeList ( OUT PRTL_RANGE_LIST  CopyRangeList,
IN PRTL_RANGE_LIST  RangeList 
)

Definition at line 148 of file rangelist.c.

150{
151 PRTL_RANGE_ENTRY Current;
152 PRTL_RANGE_ENTRY NewEntry;
154
155 CopyRangeList->Flags = RangeList->Flags;
156
157 Entry = RangeList->ListHead.Flink;
158 while (Entry != &RangeList->ListHead)
159 {
161
162 NewEntry = RtlpAllocateMemory(sizeof(RTL_RANGE_ENTRY), 'elRR');
163 if (NewEntry == NULL)
165
166 RtlCopyMemory(&NewEntry->Range,
167 &Current->Range,
168 sizeof(RTL_RANGE));
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}
#define RtlCopyMemory(Destination, Source, Length)
Definition: typedefs.h:263

Referenced by RtlMergeRangeLists().

◆ RtlDeleteOwnersRanges()

NTSTATUS NTAPI RtlDeleteOwnersRanges ( IN OUT PRTL_RANGE_LIST  RangeList,
IN PVOID  Owner 
)

Definition at line 203 of file rangelist.c.

205{
206 PRTL_RANGE_ENTRY Current;
208
209 Entry = RangeList->ListHead.Flink;
210 while (Entry != &RangeList->ListHead)
211 {
213 if (Current->Range.Owner == Owner)
214 {
216 RtlpFreeMemory(Current, 0);
217
218 RangeList->Count--;
219 RangeList->Stamp++;
220 }
221
222 Entry = Entry->Flink;
223 }
224
225 return STATUS_SUCCESS;
226}
#define RemoveEntryList(Entry)
Definition: env_spec_w32.h:986

◆ RtlDeleteRange()

NTSTATUS NTAPI RtlDeleteRange ( IN OUT PRTL_RANGE_LIST  RangeList,
IN ULONGLONG  Start,
IN ULONGLONG  End,
IN PVOID  Owner 
)

Definition at line 249 of file rangelist.c.

253{
254 PRTL_RANGE_ENTRY Current;
256
257 Entry = RangeList->ListHead.Flink;
258 while (Entry != &RangeList->ListHead)
259 {
261 if (Current->Range.Start == Start &&
262 Current->Range.End == End &&
263 Current->Range.Owner == Owner)
264 {
266
267 RtlpFreeMemory(Current, 0);
268
269 RangeList->Count--;
270 RangeList->Stamp++;
271 return STATUS_SUCCESS;
272 }
273
274 Entry = Entry->Flink;
275 }
276
278}
#define STATUS_RANGE_NOT_FOUND
Definition: ntstatus.h:768

◆ RtlFindRange()

NTSTATUS NTAPI RtlFindRange ( IN PRTL_RANGE_LIST  RangeList,
IN ULONGLONG  Minimum,
IN ULONGLONG  Maximum,
IN ULONG  Length,
IN ULONG  Alignment,
IN ULONG  Flags,
IN UCHAR  AttributeAvailableMask,
IN PVOID Context  OPTIONAL,
IN PRTL_CONFLICT_RANGE_CALLBACK Callback  OPTIONAL,
OUT PULONGLONG  Start 
)

Definition at line 310 of file rangelist.c.

320{
321 PRTL_RANGE_ENTRY CurrentEntry;
322 PRTL_RANGE_ENTRY NextEntry;
324 ULONGLONG RangeMin;
325 ULONGLONG RangeMax;
326
327 if (Alignment == 0 || Length == 0)
328 {
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 {
343
344 RangeMax = NextEntry ? (NextEntry->Range.Start - 1) : Maximum;
345 if (RangeMax + (Length - 1) < Minimum)
346 {
348 }
349
350 RangeMin = ROUND_DOWN(RangeMax - (Length - 1), Alignment);
351 if (RangeMin < Minimum ||
352 (RangeMax - RangeMin) < (Length - 1))
353 {
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 {
374 }
375
376 RangeMin = ROUND_DOWN(RangeMax - (Length - 1), Alignment);
377 if (RangeMin < Minimum ||
378 (RangeMax - RangeMin) < (Length - 1))
379 {
381 }
382
383 DPRINT("RangeMax: %I64x\n", RangeMax);
384 DPRINT("RangeMin: %I64x\n", RangeMin);
385
386 *Start = RangeMin;
387
388 return STATUS_SUCCESS;
389}
#define IsListEmpty(ListHead)
Definition: env_spec_w32.h:954
#define ROUND_DOWN(n, align)
Definition: eventvwr.h:33
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:102
uint64_t ULONGLONG
Definition: typedefs.h:67

◆ RtlFreeRangeList()

VOID NTAPI RtlFreeRangeList ( IN PRTL_RANGE_LIST  RangeList)

Definition at line 409 of file rangelist.c.

410{
412 PRTL_RANGE_ENTRY Current;
413
414 while (!IsListEmpty(&RangeList->ListHead))
415 {
416 Entry = RemoveHeadList(&RangeList->ListHead);
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}
#define RemoveHeadList(ListHead)
Definition: env_spec_w32.h:964

◆ RtlGetFirstRange()

NTSTATUS NTAPI RtlGetFirstRange ( IN PRTL_RANGE_LIST  RangeList,
OUT PRTL_RANGE_LIST_ITERATOR  Iterator,
OUT PRTL_RANGE Range 
)

Definition at line 449 of file rangelist.c.

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;
462 }
463
464 Iterator->Current = RangeList->ListHead.Flink;
465 *Range = &((PRTL_RANGE_ENTRY)Iterator->Current)->Range;
466
467 return STATUS_SUCCESS;
468}
#define STATUS_NO_MORE_ENTRIES
Definition: ntstatus.h:205
struct _RTL_RANGE_ENTRY * PRTL_RANGE_ENTRY
Definition: range.c:39
_In_ WDFCHILDLIST _In_ PWDF_CHILD_LIST_ITERATOR Iterator
Definition: wdfchildlist.h:656

Referenced by RtlMergeRangeLists().

◆ RtlGetNextRange()

NTSTATUS NTAPI RtlGetNextRange ( IN OUT PRTL_RANGE_LIST_ITERATOR  Iterator,
OUT PRTL_RANGE Range,
IN BOOLEAN  MoveForwards 
)

Definition at line 491 of file rangelist.c.

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)
501
502 if (Iterator->Current == NULL)
503 {
504 *Range = NULL;
506 }
507
508 if (MoveForwards)
509 {
510 Next = ((PRTL_RANGE_ENTRY)Iterator->Current)->Entry.Flink;
511 }
512 else
513 {
514 Next = ((PRTL_RANGE_ENTRY)Iterator->Current)->Entry.Blink;
515 }
516
517 if (Next == Iterator->RangeListHead)
518 {
519 Iterator->Current = NULL;
520 *Range = NULL;
522 }
523
524 Iterator->Current = Next;
525 *Range = &((PRTL_RANGE_ENTRY)Next)->Range;
526
527 return STATUS_SUCCESS;
528}
struct _LIST_ENTRY * Blink
Definition: typedefs.h:122
struct _LIST_ENTRY * Flink
Definition: typedefs.h:121

Referenced by RtlMergeRangeLists().

◆ RtlInitializeRangeList()

VOID NTAPI RtlInitializeRangeList ( IN OUT PRTL_RANGE_LIST  RangeList)

Definition at line 548 of file rangelist.c.

549{
550 InitializeListHead(&RangeList->ListHead);
551 RangeList->Flags = 0;
552 RangeList->Count = 0;
553 RangeList->Stamp = 0;
554}
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944

◆ RtlInvertRangeList()

NTSTATUS NTAPI RtlInvertRangeList ( OUT PRTL_RANGE_LIST  InvertedRangeList,
IN PRTL_RANGE_LIST  RangeList 
)

Definition at line 575 of file rangelist.c.

577{
578 PRTL_RANGE_ENTRY Previous;
579 PRTL_RANGE_ENTRY Current;
582
583 /* Add leading and intermediate ranges */
584 Previous = NULL;
585 Entry = RangeList->ListHead.Flink;
586 while (Entry != &RangeList->ListHead)
587 {
589
590 if (Previous == NULL)
591 {
592 if (Current->Range.Start != (ULONGLONG)0)
593 {
594 Status = RtlAddRange(InvertedRangeList,
595 (ULONGLONG)0,
596 Current->Range.Start - 1,
597 0,
598 0,
599 NULL,
600 NULL);
601 if (!NT_SUCCESS(Status))
602 return Status;
603 }
604 }
605 else
606 {
607 if (Previous->Range.End + 1 != Current->Range.Start)
608 {
609 Status = RtlAddRange(InvertedRangeList,
610 Previous->Range.End + 1,
611 Current->Range.Start - 1,
612 0,
613 0,
614 NULL,
615 NULL);
616 if (!NT_SUCCESS(Status))
617 return Status;
618 }
619 }
620
621 Previous = Current;
622 Entry = Entry->Flink;
623 }
624
625 /* Check if the list was empty */
626 if (Previous == NULL)
627 {
628 /* We're done */
629 return STATUS_SUCCESS;
630 }
631
632 /* Add trailing range */
633 if (Previous->Range.End + 1 != (ULONGLONG)-1)
634 {
635 Status = RtlAddRange(InvertedRangeList,
636 Previous->Range.End + 1,
637 (ULONGLONG)-1,
638 0,
639 0,
640 NULL,
641 NULL);
642 if (!NT_SUCCESS(Status))
643 return Status;
644 }
645
646 return STATUS_SUCCESS;
647}
LONG NTSTATUS
Definition: precomp.h:26
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
Status
Definition: gdiplustypes.h:25
NTSTATUS NTAPI RtlAddRange(IN OUT PRTL_RANGE_LIST RangeList, IN ULONGLONG Start, IN ULONGLONG End, IN UCHAR Attributes, IN ULONG Flags, IN PVOID UserData OPTIONAL, IN PVOID Owner OPTIONAL)
Definition: rangelist.c:52

◆ RtlIsRangeAvailable()

NTSTATUS NTAPI RtlIsRangeAvailable ( IN PRTL_RANGE_LIST  RangeList,
IN ULONGLONG  Start,
IN ULONGLONG  End,
IN ULONG  Flags,
IN UCHAR  AttributeAvailableMask,
IN PVOID Context  OPTIONAL,
IN PRTL_CONFLICT_RANGE_CALLBACK Callback  OPTIONAL,
OUT PBOOLEAN  Available 
)

Definition at line 677 of file rangelist.c.

685{
686 PRTL_RANGE_ENTRY Current;
688
689 *Available = TRUE;
690
691 Entry = RangeList->ListHead.Flink;
692 while (Entry != &RangeList->ListHead)
693 {
695
696 if (!((Current->Range.Start >= End && Current->Range.End > End) ||
697 (Current->Range.Start <= Start && Current->Range.End < Start &&
698 (!(Flags & RTL_RANGE_SHARED) ||
699 !(Current->Range.Flags & RTL_RANGE_SHARED)))))
700 {
701 if (Callback != NULL)
702 {
703 *Available = Callback(Context,
704 &Current->Range);
705 }
706 else
707 {
708 *Available = FALSE;
709 }
710 }
711
712 Entry = Entry->Flink;
713 }
714
715 return STATUS_SUCCESS;
716}
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
_In_ WDFINTERRUPT _In_ PFN_WDF_INTERRUPT_SYNCHRONIZE Callback
Definition: wdfinterrupt.h:458

◆ RtlMergeRangeLists()

NTSTATUS NTAPI RtlMergeRangeLists ( OUT PRTL_RANGE_LIST  MergedRangeList,
IN PRTL_RANGE_LIST  RangeList1,
IN PRTL_RANGE_LIST  RangeList2,
IN ULONG  Flags 
)

Definition at line 739 of file rangelist.c.

743{
747
748 /* Copy range list 1 to the merged range list */
749 Status = RtlCopyRangeList(MergedRangeList,
750 RangeList1);
751 if (!NT_SUCCESS(Status))
752 return Status;
753
754 /* Add range list 2 entries to the merged range list */
755 Status = RtlGetFirstRange(RangeList2,
756 &Iterator,
757 &Range);
758 if (!NT_SUCCESS(Status))
760
761 while (TRUE)
762 {
763 Status = RtlAddRange(MergedRangeList,
764 Range->Start,
765 Range->End,
766 Range->Attributes,
767 Range->Flags | Flags,
768 Range->UserData,
769 Range->Owner);
770 if (!NT_SUCCESS(Status))
771 break;
772
774 &Range,
775 TRUE);
776 if (!NT_SUCCESS(Status))
777 break;
778 }
779
781}
struct tagRange Range
NTSTATUS NTAPI RtlGetFirstRange(IN PRTL_RANGE_LIST RangeList, OUT PRTL_RANGE_LIST_ITERATOR Iterator, OUT PRTL_RANGE *Range)
Definition: rangelist.c:449
NTSTATUS NTAPI RtlCopyRangeList(OUT PRTL_RANGE_LIST CopyRangeList, IN PRTL_RANGE_LIST RangeList)
Definition: rangelist.c:148
NTSTATUS NTAPI RtlGetNextRange(IN OUT PRTL_RANGE_LIST_ITERATOR Iterator, OUT PRTL_RANGE *Range, IN BOOLEAN MoveForwards)
Definition: rangelist.c:491