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_ENTRY *	PRTL_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

typedef struct _RTL_RANGE_ENTRY * PRTL_RANGE_ENTRY

RTL_RANGE_ENTRY

typedef struct _RTL_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.

{
    PRTL_RANGE_ENTRY RangeEntry;
    //PRTL_RANGE_ENTRY Previous;
    PRTL_RANGE_ENTRY Current;
    PLIST_ENTRY Entry;
 
    if (Start > End)
        return STATUS_INVALID_PARAMETER;
 
    /* Create new range entry */
    RangeEntry = RtlpAllocateMemory(sizeof(RTL_RANGE_ENTRY), 'elRR');
    if (RangeEntry == NULL)
        return STATUS_INSUFFICIENT_RESOURCES;
 
    /* Initialize range entry */
    RangeEntry->Range.Start = Start;
    RangeEntry->Range.End = End;
    RangeEntry->Range.Attributes = Attributes;
    RangeEntry->Range.UserData = UserData;
    RangeEntry->Range.Owner = Owner;
 
    RangeEntry->Range.Flags = 0;
    if (Flags & RTL_RANGE_LIST_ADD_SHARED)
        RangeEntry->Range.Flags |= RTL_RANGE_SHARED;
 
    /* Insert range entry */
    if (RangeList->Count == 0)
    {
        InsertTailList(&RangeList->ListHead,
                       &RangeEntry->Entry);
        RangeList->Count++;
        RangeList->Stamp++;
        return STATUS_SUCCESS;
    }
    else
    {
         //Previous = NULL;
        Entry = RangeList->ListHead.Flink;
        while (Entry != &RangeList->ListHead)
        {
            Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
            if (Current->Range.Start > RangeEntry->Range.End)
            {
                /* Insert before current */
                DPRINT("Insert before current\n");
                InsertTailList(&Current->Entry,
                               &RangeEntry->Entry);
 
                RangeList->Count++;
                RangeList->Stamp++;
                return STATUS_SUCCESS;
            }
 
            //Previous = Current;
            Entry = Entry->Flink;
        }
 
        DPRINT("Insert tail\n");
        InsertTailList(&RangeList->ListHead,
                       &RangeEntry->Entry);
        RangeList->Count++;
        RangeList->Stamp++;
        return STATUS_SUCCESS;
    }
 
    RtlpFreeMemory(RangeEntry, 0);
 
    return STATUS_UNSUCCESSFUL;
}

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.

{
    PRTL_RANGE_ENTRY Current;
    PRTL_RANGE_ENTRY NewEntry;
    PLIST_ENTRY Entry;
 
    CopyRangeList->Flags = RangeList->Flags;
 
    Entry = RangeList->ListHead.Flink;
    while (Entry != &RangeList->ListHead)
    {
        Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
 
        NewEntry = RtlpAllocateMemory(sizeof(RTL_RANGE_ENTRY), 'elRR');
        if (NewEntry == NULL)
            return STATUS_INSUFFICIENT_RESOURCES;
 
        RtlCopyMemory(&NewEntry->Range,
                      &Current->Range,
                      sizeof(RTL_RANGE));
 
        InsertTailList(&CopyRangeList->ListHead,
                       &NewEntry->Entry);
 
        CopyRangeList->Count++;
 
        Entry = Entry->Flink;
    }
 
    CopyRangeList->Stamp++;
 
    return STATUS_SUCCESS;
}

Referenced by RtlMergeRangeLists().

RtlDeleteOwnersRanges()

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

Definition at line 203 of file rangelist.c.

{
    PRTL_RANGE_ENTRY Current;
    PLIST_ENTRY Entry;
 
    Entry = RangeList->ListHead.Flink;
    while (Entry != &RangeList->ListHead)
    {
        Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
        if (Current->Range.Owner == Owner)
        {
            RemoveEntryList (Entry);
            RtlpFreeMemory(Current, 0);
 
            RangeList->Count--;
            RangeList->Stamp++;
        }
 
        Entry = Entry->Flink;
    }
 
    return STATUS_SUCCESS;
}

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.

{
    PRTL_RANGE_ENTRY Current;
    PLIST_ENTRY Entry;
 
    Entry = RangeList->ListHead.Flink;
    while (Entry != &RangeList->ListHead)
    {
        Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
        if (Current->Range.Start == Start &&
            Current->Range.End == End &&
            Current->Range.Owner == Owner)
        {
            RemoveEntryList(Entry);
 
            RtlpFreeMemory(Current, 0);
 
            RangeList->Count--;
            RangeList->Stamp++;
            return STATUS_SUCCESS;
        }
 
        Entry = Entry->Flink;
    }
 
    return STATUS_RANGE_NOT_FOUND;
}

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.

{
    PRTL_RANGE_ENTRY CurrentEntry;
    PRTL_RANGE_ENTRY NextEntry;
    PLIST_ENTRY Entry;
    ULONGLONG RangeMin;
    ULONGLONG RangeMax;
 
    if (Alignment == 0 || Length == 0)
    {
        return STATUS_INVALID_PARAMETER;
    }
 
    if (IsListEmpty(&RangeList->ListHead))
    {
        *Start = ROUND_DOWN(Maximum - (Length - 1), Alignment);
        return STATUS_SUCCESS;
    }
 
    NextEntry = NULL;
    Entry = RangeList->ListHead.Blink;
    while (Entry != &RangeList->ListHead)
    {
        CurrentEntry = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
 
        RangeMax = NextEntry ? (NextEntry->Range.Start - 1) : Maximum;
        if (RangeMax + (Length - 1) < Minimum)
        {
            return STATUS_RANGE_NOT_FOUND;
        }
 
        RangeMin = ROUND_DOWN(RangeMax - (Length - 1), Alignment);
        if (RangeMin < Minimum ||
            (RangeMax - RangeMin) < (Length - 1))
        {
            return STATUS_RANGE_NOT_FOUND;
        }
 
        DPRINT("RangeMax: %I64x\n", RangeMax);
        DPRINT("RangeMin: %I64x\n", RangeMin);
 
        if (RangeMin > CurrentEntry->Range.End)
        {
            *Start = RangeMin;
            return STATUS_SUCCESS;
        }
 
        NextEntry = CurrentEntry;
        Entry = Entry->Blink;
    }
 
    RangeMax = NextEntry ? (NextEntry->Range.Start - 1) : Maximum;
    if (RangeMax + (Length - 1) < Minimum)
    {
        return STATUS_RANGE_NOT_FOUND;
    }
 
    RangeMin = ROUND_DOWN(RangeMax - (Length - 1), Alignment);
    if (RangeMin < Minimum ||
        (RangeMax - RangeMin) < (Length - 1))
    {
        return STATUS_RANGE_NOT_FOUND;
    }
 
    DPRINT("RangeMax: %I64x\n", RangeMax);
    DPRINT("RangeMin: %I64x\n", RangeMin);
 
    *Start = RangeMin;
 
    return STATUS_SUCCESS;
}

RtlFreeRangeList()

VOID NTAPI RtlFreeRangeList

(

IN PRTL_RANGE_LIST

RangeList

)

Definition at line 409 of file rangelist.c.

{
    PLIST_ENTRY Entry;
    PRTL_RANGE_ENTRY Current;
 
    while (!IsListEmpty(&RangeList->ListHead))
    {
        Entry = RemoveHeadList(&RangeList->ListHead);
        Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
 
        DPRINT ("Range start: %I64u\n", Current->Range.Start);
        DPRINT ("Range end:   %I64u\n", Current->Range.End);
 
        RtlpFreeMemory(Current, 0);
    }
 
    RangeList->Flags = 0;
    RangeList->Count = 0;
}

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.

{
    Iterator->RangeListHead = &RangeList->ListHead;
    Iterator->MergedHead = NULL;
    Iterator->Stamp = RangeList->Stamp;
 
    if (IsListEmpty(&RangeList->ListHead))
    {
        Iterator->Current = NULL;
        *Range = NULL;
        return STATUS_NO_MORE_ENTRIES;
    }
 
    Iterator->Current = RangeList->ListHead.Flink;
    *Range = &((PRTL_RANGE_ENTRY)Iterator->Current)->Range;
 
    return STATUS_SUCCESS;
}

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.

{
    PRTL_RANGE_LIST RangeList;
    PLIST_ENTRY Next;
 
    RangeList = CONTAINING_RECORD(Iterator->RangeListHead, RTL_RANGE_LIST, ListHead);
    if (Iterator->Stamp != RangeList->Stamp)
        return STATUS_INVALID_PARAMETER;
 
    if (Iterator->Current == NULL)
    {
        *Range = NULL;
        return STATUS_NO_MORE_ENTRIES;
    }
 
    if (MoveForwards)
    {
        Next = ((PRTL_RANGE_ENTRY)Iterator->Current)->Entry.Flink;
    }
    else
    {
        Next = ((PRTL_RANGE_ENTRY)Iterator->Current)->Entry.Blink;
    }
 
    if (Next == Iterator->RangeListHead)
    {
        Iterator->Current = NULL;
        *Range = NULL;
        return STATUS_NO_MORE_ENTRIES;
    }
 
    Iterator->Current = Next;
    *Range = &((PRTL_RANGE_ENTRY)Next)->Range;
 
    return STATUS_SUCCESS;
}

Referenced by RtlMergeRangeLists().

RtlInitializeRangeList()

VOID NTAPI RtlInitializeRangeList

(

IN OUT PRTL_RANGE_LIST

RangeList

)

Definition at line 548 of file rangelist.c.

{
    InitializeListHead(&RangeList->ListHead);
    RangeList->Flags = 0;
    RangeList->Count = 0;
    RangeList->Stamp = 0;
}

RtlInvertRangeList()

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

Definition at line 575 of file rangelist.c.

{
    PRTL_RANGE_ENTRY Previous;
    PRTL_RANGE_ENTRY Current;
    PLIST_ENTRY Entry;
    NTSTATUS Status;
 
    /* Add leading and intermediate ranges */
    Previous = NULL;
    Entry = RangeList->ListHead.Flink;
    while (Entry != &RangeList->ListHead)
    {
        Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry);
 
        if (Previous == NULL)
        {
            if (Current->Range.Start != (ULONGLONG)0)
            {
                Status = RtlAddRange(InvertedRangeList,
                                     (ULONGLONG)0,
                                     Current->Range.Start - 1,
                                     0,
                                     0,
                                     NULL,
                                     NULL);
                if (!NT_SUCCESS(Status))
                    return Status;
            }
        }
        else
        {
            if (Previous->Range.End + 1 != Current->Range.Start)
            {
                Status = RtlAddRange(InvertedRangeList,
                                     Previous->Range.End + 1,
                                     Current->Range.Start - 1,
                                     0,
                                     0,
                                     NULL,
                                     NULL);
                if (!NT_SUCCESS(Status))
                    return Status;
            }
        }
 
        Previous = Current;
        Entry = Entry->Flink;
    }
 
    /* Check if the list was empty */
    if (Previous == NULL)
    {
        /* We're done */
        return STATUS_SUCCESS;
    }
 
    /* Add trailing range */
    if (Previous->Range.End + 1 != (ULONGLONG)-1)
    {
        Status = RtlAddRange(InvertedRangeList,
                             Previous->Range.End + 1,
                             (ULONGLONG)-1,
                             0,
                             0,
                             NULL,
                             NULL);
        if (!NT_SUCCESS(Status))
            return Status;
    }
 
    return STATUS_SUCCESS;
}

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.

{
    PRTL_RANGE_ENTRY Current;
    PLIST_ENTRY Entry;
 
    *Available = TRUE;
 
    Entry = RangeList->ListHead.Flink;
    while (Entry != &RangeList->ListHead)
    {
        Current = CONTAINING_RECORD (Entry, RTL_RANGE_ENTRY, Entry);
 
        if (!((Current->Range.Start >= End && Current->Range.End > End) ||
              (Current->Range.Start <= Start && Current->Range.End < Start &&
               (!(Flags & RTL_RANGE_SHARED) ||
                !(Current->Range.Flags & RTL_RANGE_SHARED)))))
        {
            if (Callback != NULL)
            {
                *Available = Callback(Context,
                                      &Current->Range);
            }
            else
            {
                *Available = FALSE;
            }
        }
 
        Entry = Entry->Flink;
    }
 
    return STATUS_SUCCESS;
}

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.

{
    RTL_RANGE_LIST_ITERATOR Iterator;
    PRTL_RANGE Range;
    NTSTATUS Status;
 
    /* Copy range list 1 to the merged range list */
    Status = RtlCopyRangeList(MergedRangeList,
                              RangeList1);
    if (!NT_SUCCESS(Status))
        return Status;
 
    /* Add range list 2 entries to the merged range list */
    Status = RtlGetFirstRange(RangeList2,
                              &Iterator,
                              &Range);
    if (!NT_SUCCESS(Status))
        return (Status == STATUS_NO_MORE_ENTRIES) ? STATUS_SUCCESS : Status;
 
    while (TRUE)
    {
        Status = RtlAddRange(MergedRangeList,
                             Range->Start,
                             Range->End,
                             Range->Attributes,
                             Range->Flags | Flags,
                             Range->UserData,
                             Range->Owner);
        if (!NT_SUCCESS(Status))
            break;
 
        Status = RtlGetNextRange(&Iterator,
                                 &Range,
                                 TRUE);
        if (!NT_SUCCESS(Status))
            break;
    }
 
    return (Status == STATUS_NO_MORE_ENTRIES) ? STATUS_SUCCESS : Status;
}