You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2266 lines
58 KiB
2266 lines
58 KiB
/*++
|
|
|
|
Copyright (c) Microsoft Corporation. All rights reserved.
|
|
|
|
Module Name:
|
|
|
|
range.c
|
|
|
|
Abstract:
|
|
|
|
This module contains the API routines that operate directly on ranges.
|
|
|
|
CM_Add_Range
|
|
CM_Create_Range_List
|
|
CM_Delete_Range
|
|
CM_Dup_Range_List
|
|
CM_Find_Range
|
|
CM_First_Range
|
|
CM_Free_Range_List
|
|
CM_Intersect_Range_List
|
|
CM_Invert_Range_List
|
|
CM_Merge_Range_List
|
|
CM_Next_Range
|
|
CM_Test_Range_Available
|
|
|
|
Author:
|
|
|
|
Paula Tomlinson (paulat) 10-17-1995
|
|
|
|
Environment:
|
|
|
|
User mode only.
|
|
|
|
Revision History:
|
|
|
|
17-Oct-1995 paulat
|
|
|
|
Creation and initial implementation.
|
|
|
|
--*/
|
|
|
|
|
|
//
|
|
// includes
|
|
//
|
|
#include "precomp.h"
|
|
#pragma hdrstop
|
|
#include "cfgi.h"
|
|
|
|
|
|
//
|
|
// Private prototypes
|
|
//
|
|
BOOL
|
|
IsValidRangeList(
|
|
IN RANGE_LIST rlh
|
|
);
|
|
|
|
CONFIGRET
|
|
AddRange(
|
|
IN PRange_Element pParentElement,
|
|
IN DWORDLONG ullStartValue,
|
|
IN DWORDLONG ullEndValue,
|
|
IN ULONG ulFlags
|
|
);
|
|
|
|
CONFIGRET
|
|
InsertRange(
|
|
IN PRange_Element pParentElement,
|
|
IN DWORDLONG ullStartValue,
|
|
IN DWORDLONG ullEndValue
|
|
);
|
|
|
|
CONFIGRET
|
|
DeleteRange(
|
|
IN PRange_Element pParentElement
|
|
);
|
|
|
|
CONFIGRET
|
|
JoinRange(
|
|
IN PRange_Element pParentElement,
|
|
IN DWORDLONG ullStartValue,
|
|
IN DWORDLONG ullEndValue
|
|
);
|
|
|
|
CONFIGRET
|
|
CopyRanges(
|
|
IN PRange_Element pFromRange,
|
|
IN PRange_Element pToRange
|
|
);
|
|
|
|
CONFIGRET
|
|
ClearRanges(
|
|
IN PRange_Element pRange
|
|
);
|
|
|
|
CONFIGRET
|
|
TestRange(
|
|
IN PRange_Element rlh,
|
|
IN DWORDLONG ullStartValue,
|
|
IN DWORDLONG ullEndValue,
|
|
OUT PRange_Element *pConflictingRange
|
|
);
|
|
|
|
|
|
//
|
|
// global data
|
|
//
|
|
|
|
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CM_Add_Range(
|
|
IN DWORDLONG ullStartValue,
|
|
IN DWORDLONG ullEndValue,
|
|
IN RANGE_LIST rlh,
|
|
IN ULONG ulFlags
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine adds a memory range to a range list.
|
|
|
|
Parameters:
|
|
|
|
ullStartValue Low end of the range.
|
|
|
|
ullEndValue High end of the range.
|
|
|
|
rlh Handle of a range list.
|
|
|
|
ulFlags Supplies flags specifying options for ranges that conflict
|
|
with ranges alread in the list. May be one of the
|
|
following values:
|
|
|
|
CM_ADD_RANGE_ADDIFCONFLICT New range is merged with the
|
|
ranges it conflicts with.
|
|
CM_ADD_RANGE_DONOTADDIFCONFLICT Returns CR_FAILURE if there
|
|
is a conflict.
|
|
|
|
Return Value:
|
|
|
|
If the function succeeds, the return value is CR_SUCCESS.
|
|
If the function fails, the return value is one of the following:
|
|
CR_FAILURE,
|
|
CR_INVALID_FLAG,
|
|
CR_INVALID_RANGE,
|
|
CR_INVALID_RANGE_LIST, or
|
|
CR_OUT_OF_MEMORY.
|
|
--*/
|
|
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
BOOL bLock = FALSE;
|
|
|
|
try {
|
|
//
|
|
// validate parameters
|
|
//
|
|
if (!IsValidRangeList(rlh)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (INVALID_FLAGS(ulFlags, CM_ADD_RANGE_BITS)) {
|
|
Status = CR_INVALID_FLAG;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (ullStartValue > ullEndValue) {
|
|
Status = CR_INVALID_RANGE;
|
|
goto Clean0;
|
|
}
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
bLock = TRUE;
|
|
|
|
Status = AddRange((PRange_Element)rlh, ullStartValue,
|
|
ullEndValue, ulFlags);
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
bLock = bLock; // needed to prevent optimizing this flag away
|
|
Status = CR_FAILURE;
|
|
}
|
|
|
|
if (bLock) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CM_Add_Range
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CM_Create_Range_List(
|
|
OUT PRANGE_LIST prlh,
|
|
IN ULONG ulFlags
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine creates a list of ranges.
|
|
|
|
Parameters:
|
|
|
|
prlh Supplies the address of the variable that receives a
|
|
handle to the new range list.
|
|
|
|
ulFlags Must be zero.
|
|
|
|
|
|
Return Value:
|
|
|
|
If the function succeeds, the return value is CR_SUCCESS.
|
|
If the function fails, the return value is one of the following:
|
|
CR_INVALID_FLAG,
|
|
CR_INVALID_POINTER, or
|
|
CR_OUT_OF_MEMORY.
|
|
|
|
--*/
|
|
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
PRange_List_Hdr pRangeHdr = NULL;
|
|
|
|
|
|
try {
|
|
//
|
|
// validate parameters
|
|
//
|
|
if (INVALID_FLAGS(ulFlags, 0)) {
|
|
Status = CR_INVALID_FLAG;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (prlh == NULL) {
|
|
Status = CR_INVALID_POINTER;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// allocate a buffer for the range list header struct
|
|
//
|
|
pRangeHdr = pSetupMalloc(sizeof(Range_List_Hdr));
|
|
|
|
if (pRangeHdr == NULL) {
|
|
Status = CR_OUT_OF_MEMORY;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// initialize the range list header buffer
|
|
//
|
|
pRangeHdr->RLH_Head = 0;
|
|
pRangeHdr->RLH_Header = (ULONG_PTR)pRangeHdr;
|
|
pRangeHdr->RLH_Signature = Range_List_Signature;
|
|
|
|
//
|
|
// initialize the private resource lock
|
|
//
|
|
InitPrivateResource(&(pRangeHdr->RLH_Lock));
|
|
|
|
//
|
|
// return a pointer to range list buffer to the caller
|
|
//
|
|
*prlh = (RANGE_LIST)pRangeHdr;
|
|
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
Status = CR_FAILURE;
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CM_Create_Range_List
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CM_Delete_Range(
|
|
IN DWORDLONG ullStartValue,
|
|
IN DWORDLONG ullEndValue,
|
|
IN RANGE_LIST rlh,
|
|
IN ULONG ulFlags
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine deletes a range from a range list. If ullStartValue
|
|
and ullEndValue are set to 0 and DWORD_MAX, this API carries out
|
|
a special case, quickly emptying the lower 4 Gigabytes of the range.
|
|
If ullEndValue is instead DWORDLONG_MAX, the entire range list is
|
|
cleared, without having to process each element.
|
|
|
|
Parameters:
|
|
|
|
ullStartValue Low end of the range.
|
|
|
|
ullEndValue High end of the range.
|
|
|
|
rlh Handle of a range list.
|
|
|
|
ulFlags Must be zero.
|
|
|
|
|
|
Return Value:
|
|
|
|
If the function succeeds, the return value is CR_SUCCESS.
|
|
If the function fails, the return value is one of the following:
|
|
CR_FAILURE,
|
|
CR_INVALID_FLAG,
|
|
CR_INVALID_RANGE,
|
|
CR_INVALID_RANGE_LIST, or
|
|
CR_OUT_OF_MEMORY.
|
|
|
|
--*/
|
|
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
PRange_Element pRange = NULL, pPrevious = NULL, pCurrent = NULL;
|
|
BOOL bLock = FALSE;
|
|
|
|
try {
|
|
//
|
|
// validate parameters
|
|
//
|
|
if (!IsValidRangeList(rlh)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (INVALID_FLAGS(ulFlags, 0)) {
|
|
Status = CR_INVALID_FLAG;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (ullStartValue > ullEndValue) {
|
|
Status = CR_INVALID_RANGE;
|
|
goto Clean0;
|
|
}
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
bLock = TRUE;
|
|
|
|
pPrevious = (PRange_Element)rlh;
|
|
|
|
|
|
//-------------------------------------------------------------
|
|
// first check the special case range values
|
|
//-------------------------------------------------------------
|
|
|
|
if (ullStartValue == 0) {
|
|
|
|
if (ullEndValue == DWORDLONG_MAX) {
|
|
//
|
|
// quick clear of all ranges
|
|
//
|
|
ClearRanges(pPrevious);
|
|
}
|
|
|
|
else if (ullEndValue == DWORD_MAX) {
|
|
//
|
|
// quick clear of lower 4 GB ranges
|
|
//
|
|
while (pPrevious->RL_Next != 0) {
|
|
pCurrent = (PRange_Element)pPrevious->RL_Next;
|
|
|
|
if (pCurrent->RL_Start >= DWORD_MAX) {
|
|
goto Clean0; // done
|
|
}
|
|
|
|
if (pCurrent->RL_End >= DWORD_MAX) {
|
|
pCurrent->RL_Start = DWORD_MAX;
|
|
goto Clean0; // done
|
|
}
|
|
|
|
DeleteRange(pPrevious); // pass the parent
|
|
}
|
|
goto Clean0;
|
|
}
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------
|
|
// search through each range in this list, if any part of the
|
|
// specified range is contained in this range list, remove the
|
|
// intersections
|
|
//-------------------------------------------------------------
|
|
|
|
while (pPrevious->RL_Next != 0) {
|
|
pRange = (PRange_Element)pPrevious->RL_Next;
|
|
|
|
//
|
|
// if this range is completely before the current range, then
|
|
// we can stop
|
|
//
|
|
if (ullEndValue < pRange->RL_Start) {
|
|
break;
|
|
}
|
|
|
|
//
|
|
// if this range is completely after the current range, then
|
|
// skip to the next range
|
|
//
|
|
if (ullStartValue > pRange->RL_End) {
|
|
goto NextRange;
|
|
}
|
|
|
|
//
|
|
// if the range is completely contained, then delete the whole
|
|
// thing
|
|
//
|
|
if (ullStartValue <= pRange->RL_Start &&
|
|
ullEndValue >= pRange->RL_End) {
|
|
|
|
DeleteRange(pPrevious); // pass the parent range
|
|
|
|
//
|
|
// don't goto next range because that would increment the
|
|
// pPrevious counter. Since the current range was just deleted,
|
|
// we need to process the current spot still.
|
|
//
|
|
continue;
|
|
}
|
|
|
|
//
|
|
// if the start of the specified range intersects the current range,
|
|
// adjust the current range to exclude it
|
|
//
|
|
if (ullStartValue > pRange->RL_Start &&
|
|
ullStartValue <= pRange->RL_End) {
|
|
//
|
|
// if the specified range is in the middle of this range, then
|
|
// in addition to shrinking the first part of the range, I'll
|
|
// have to create a range for the second part
|
|
// | |<-- delete --->| |
|
|
//
|
|
if (ullEndValue < pRange->RL_End) {
|
|
AddRange(pRange, ullEndValue+1, pRange->RL_End,
|
|
CM_ADD_RANGE_ADDIFCONFLICT);
|
|
}
|
|
|
|
pRange->RL_End = ullStartValue-1;
|
|
|
|
//
|
|
// reset the delete range for further processing
|
|
//
|
|
if (ullEndValue > pRange->RL_End) {
|
|
ullStartValue = pRange->RL_End+1;
|
|
}
|
|
}
|
|
|
|
//
|
|
// if the end of the specified range intersects the current range,
|
|
// adjust the current range to exclude it
|
|
//
|
|
if (ullEndValue >= pRange->RL_Start &&
|
|
ullEndValue <= pRange->RL_End) {
|
|
|
|
pRange->RL_Start = ullEndValue+1;
|
|
|
|
//
|
|
// reset the delete range for further processing
|
|
//
|
|
if (ullEndValue > pRange->RL_End) {
|
|
ullStartValue = pRange->RL_End+1;
|
|
}
|
|
}
|
|
|
|
|
|
NextRange:
|
|
|
|
pPrevious = (PRange_Element)pPrevious->RL_Next;
|
|
}
|
|
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
bLock = bLock; // needed to prevent optimizing this flag away
|
|
Status = CR_FAILURE;
|
|
}
|
|
|
|
if (bLock) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CM_Delete_Range
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CM_Dup_Range_List(
|
|
IN RANGE_LIST rlhOld,
|
|
IN RANGE_LIST rlhNew,
|
|
IN ULONG ulFlags
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine copies a range list.
|
|
|
|
Parameters:
|
|
|
|
rlhOld Supplies the handle of the range list to copy.
|
|
|
|
rlhNew Supplies the handle of a valid range list into which rlhOld
|
|
is copied. Anything contained in the rlhNew range list is
|
|
removed by the copy operation.
|
|
|
|
ulFlags Must be zero.
|
|
|
|
Return Value:
|
|
|
|
If the function succeeds, the return value is CR_SUCCESS.
|
|
If the function fails, the return value is one of the following:
|
|
CR_INVALID_FLAG,
|
|
CR_INVALID_RANGE_LIST, or
|
|
CR_OUT_OF_MEMORY
|
|
|
|
--*/
|
|
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
PRange_Element pRangeNew = NULL, pRangeOld = NULL;
|
|
BOOL bLockOld = FALSE, bLockNew = FALSE;
|
|
|
|
try {
|
|
//
|
|
// validate parameters
|
|
//
|
|
if (!IsValidRangeList(rlhOld)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (!IsValidRangeList(rlhNew)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (INVALID_FLAGS(ulFlags, 0)) {
|
|
Status = CR_INVALID_FLAG;
|
|
goto Clean0;
|
|
}
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlhOld)->RLH_Lock);
|
|
bLockOld = TRUE;
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlhNew)->RLH_Lock);
|
|
bLockNew = TRUE;
|
|
|
|
pRangeNew = (PRange_Element)rlhNew;
|
|
pRangeOld = (PRange_Element)rlhOld;
|
|
|
|
//
|
|
// If the new range list is not empty, then delete ranges
|
|
//
|
|
if (pRangeNew->RL_Next != 0) {
|
|
ClearRanges(pRangeNew);
|
|
}
|
|
|
|
Status = CR_SUCCESS; // reset status flag to okay
|
|
|
|
|
|
//
|
|
// duplicate each of the old ranges
|
|
//
|
|
pRangeOld = (PRange_Element)pRangeOld->RL_Next;
|
|
CopyRanges(pRangeOld, pRangeNew);
|
|
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
bLockOld = bLockOld; // needed to prevent optimizing this flag away
|
|
bLockNew = bLockNew; // needed to prevent optimizing this flag away
|
|
Status = CR_FAILURE;
|
|
}
|
|
|
|
|
|
if (bLockOld) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlhOld)->RLH_Lock);
|
|
}
|
|
if (bLockNew) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlhNew)->RLH_Lock);
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CM_Dup_Range_List
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CM_Find_Range(
|
|
OUT PDWORDLONG pullStart,
|
|
IN DWORDLONG ullStart,
|
|
IN ULONG ulLength,
|
|
IN DWORDLONG ullAlignment,
|
|
IN DWORDLONG ullEnd,
|
|
IN RANGE_LIST rlh,
|
|
IN ULONG ulFlags
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine attempts to find a range in the supplied range list that
|
|
will accommodate the range requirements specified. [TBD: Verify
|
|
that this description is correct.]
|
|
|
|
Parameters:
|
|
|
|
pullStart Supplies the address of a variable that receives the
|
|
starting value of the allocated range.
|
|
|
|
ullStart Supplies the starting address that the range can have.
|
|
|
|
ulLength Supplies the length needed for the allocated range.
|
|
|
|
ullAlignment Supplies the alignment bitmask that specifies where the
|
|
allocated range can start. [TBD: verify that this is indeed
|
|
a bitmask]
|
|
|
|
ullEnd Supplies the ending address of the area from which the range
|
|
may be allocated.
|
|
|
|
rlh Supplies a handle to a range list in which the specified
|
|
range is to be found.
|
|
|
|
ulFlags TBD
|
|
|
|
|
|
Return Value:
|
|
|
|
If the function succeeds, the return value is CR_SUCCESS.
|
|
If the function fails, the return value is one of the following:
|
|
CR_INVALID_FLAG,
|
|
CR_INVALID_POINTER,
|
|
CR_FAILURE
|
|
|
|
--*/
|
|
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
PRange_Element pRange = NULL;
|
|
DWORDLONG ullNewEnd;
|
|
BOOL bLock = FALSE;
|
|
|
|
try {
|
|
//
|
|
// validate parameters
|
|
//
|
|
if (!IsValidRangeList(rlh)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (pullStart == NULL) {
|
|
Status = CR_INVALID_POINTER;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (INVALID_FLAGS(ulFlags, 0)) {
|
|
Status = CR_INVALID_FLAG;
|
|
goto Clean0;
|
|
}
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
bLock = TRUE;
|
|
|
|
//
|
|
// Normalize aligment. Alignments are now like 0x00000FFF.
|
|
//
|
|
ullAlignment =~ ullAlignment;
|
|
|
|
//
|
|
// Test for impossible alignments (-1, not a power of 2 or start is
|
|
// less than alignment away from wrapping). Also test for invalid
|
|
// length.
|
|
//
|
|
if ((ullAlignment == DWORD_MAX) |
|
|
(ulLength == 0) |
|
|
((ullAlignment & (ullAlignment + 1)) != 0) |
|
|
(ullStart + ullAlignment < ullStart)) {
|
|
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// Align the base.
|
|
//
|
|
ullStart += ullAlignment;
|
|
ullStart &= ~ullAlignment;
|
|
|
|
//
|
|
// Compute the new end.
|
|
//
|
|
ullNewEnd = ullStart + ulLength - 1;
|
|
|
|
//
|
|
// Make sure we do have space.
|
|
//
|
|
if ((ullNewEnd < ullStart) || (ullNewEnd > ullEnd)) {
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// Check if that range fits
|
|
//
|
|
if (TestRange((PRange_Element)rlh, ullStart, ullStart + ulLength - 1,
|
|
&pRange) == CR_SUCCESS) {
|
|
//
|
|
// We got it then, on the first try.
|
|
//
|
|
*pullStart = ullStart;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// Search for a spot where this range will fit.
|
|
//
|
|
for ( ; ; ) {
|
|
//
|
|
// Start at the end of the conflicting range.
|
|
//
|
|
ullStart = pRange->RL_End + 1;
|
|
|
|
//
|
|
// Check for wrapping.
|
|
//
|
|
if (!ullStart) {
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// Make sure the alignment adjustment won't wrap.
|
|
//
|
|
if (ullStart + ullAlignment < ullStart) {
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// Adjust the alignment.
|
|
//
|
|
ullStart += ullAlignment;
|
|
ullStart &= ~ullAlignment;
|
|
|
|
//
|
|
// Compute the new end.
|
|
//
|
|
ullNewEnd = ullStart + ulLength - 1;
|
|
|
|
//
|
|
// Make sure the new end does not wrap and is still valid.
|
|
//
|
|
if ((ullNewEnd < ullStart) | (ullStart + ulLength - 1 > ullEnd)) {
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// Skip any prls which existed only below our new range
|
|
// (because we moved ulStart upward of them).
|
|
//
|
|
while ((pRange = (PRange_Element)pRange->RL_Next) != NULL &&
|
|
ullStart > pRange->RL_End) {
|
|
}
|
|
|
|
//
|
|
// If we don't have a prl or it's begining is after our end
|
|
//
|
|
if (pRange == NULL || ullNewEnd < pRange->RL_Start) {
|
|
*pullStart = ullStart;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// Otherwise try with the new prl.
|
|
//
|
|
}
|
|
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
bLock = bLock; // needed to prevent optimizing this flag away
|
|
Status = CR_FAILURE;
|
|
}
|
|
|
|
if (bLock) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CM_Find_Range
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CM_First_Range(
|
|
IN RANGE_LIST rlh,
|
|
OUT PDWORDLONG pullStart,
|
|
OUT PDWORDLONG pullEnd,
|
|
OUT PRANGE_ELEMENT preElement,
|
|
IN ULONG ulFlags
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine retrieves the first range element in a range list.
|
|
|
|
Parameters:
|
|
|
|
rlh Supplies the handle of a range list.
|
|
|
|
pullStart Supplies the address of a variable that receives the
|
|
starting value of the first range element.
|
|
|
|
pullEnd Supplies the address of a variable that receives the
|
|
ending value of the first range element.
|
|
|
|
preElement Supplies the address of a variable that receives the
|
|
handle of the next range element.
|
|
|
|
ulFlags Must be zero.
|
|
|
|
|
|
Return Value:
|
|
|
|
If the function succeeds, the return value is CR_SUCCESS.
|
|
If the function fails, the return value is one of the following:
|
|
CR_FAILURE,
|
|
CR_INVALID_FLAG,
|
|
CR_INVALID_POINTER, or
|
|
CR_INVALID_RANGE_LIST.
|
|
|
|
--*/
|
|
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
PRange_Element pRange = NULL;
|
|
BOOL bLock = FALSE;
|
|
|
|
try {
|
|
//
|
|
// validate parameters
|
|
//
|
|
if (!IsValidRangeList(rlh)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (pullEnd == NULL || pullStart == NULL || preElement == NULL) {
|
|
Status = CR_INVALID_POINTER;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (INVALID_FLAGS(ulFlags, 0)) {
|
|
Status = CR_INVALID_FLAG;
|
|
goto Clean0;
|
|
}
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
bLock = TRUE;
|
|
|
|
pRange = (PRange_Element)rlh;
|
|
|
|
//
|
|
// is the range list empty?
|
|
//
|
|
if (pRange->RL_Next == 0) {
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// skip over the header to the first element
|
|
//
|
|
pRange = (PRange_Element)pRange->RL_Next;
|
|
|
|
*pullStart = pRange->RL_Start;
|
|
*pullEnd = pRange->RL_End;
|
|
*preElement = (RANGE_ELEMENT)pRange->RL_Next;
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
bLock = bLock; // needed to prevent optimizing this flag away
|
|
Status = CR_FAILURE;
|
|
}
|
|
|
|
|
|
if (bLock) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CM_First_Range
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CM_Free_Range_List(
|
|
IN RANGE_LIST rlh,
|
|
IN ULONG ulFlags
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine frees the specified range list and the memory allocated
|
|
for it.
|
|
|
|
Parameters:
|
|
|
|
rlh Supplies the handle of the range list to be freed.
|
|
|
|
ulFlags Must be zero.
|
|
|
|
|
|
Return Value:
|
|
|
|
If the function succeeds, the return value is CR_SUCCESS.
|
|
If the function fails, the return value is one of the following:
|
|
CR_INVALID_FLAG,
|
|
CR_INVALID_RANGE_LIST.
|
|
|
|
--*/
|
|
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS, Status1 = CR_SUCCESS;
|
|
BOOL bLock = FALSE;
|
|
|
|
try {
|
|
//
|
|
// validate parameters
|
|
//
|
|
if (!IsValidRangeList(rlh)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (INVALID_FLAGS(ulFlags, 0)) {
|
|
Status = CR_INVALID_FLAG;
|
|
goto Clean0;
|
|
}
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
bLock = TRUE;
|
|
|
|
while (Status1 == CR_SUCCESS) {
|
|
//
|
|
// keep deleting the first range after the header (pass parent
|
|
// of range to delete)
|
|
//
|
|
Status1 = DeleteRange((PRange_Element)rlh);
|
|
}
|
|
|
|
//
|
|
// destroy the private resource lock
|
|
//
|
|
DestroyPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
|
|
//
|
|
// delete the range header
|
|
//
|
|
((PRange_List_Hdr)rlh)->RLH_Signature = 0;
|
|
pSetupFree((PRange_Element)rlh);
|
|
bLock = FALSE;
|
|
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
bLock = bLock; // needed to prevent optimizing this flag away
|
|
Status = CR_FAILURE;
|
|
}
|
|
|
|
if (bLock) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CM_Free_Range_List
|
|
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CM_Intersect_Range_List(
|
|
IN RANGE_LIST rlhOld1,
|
|
IN RANGE_LIST rlhOld2,
|
|
IN RANGE_LIST rlhNew,
|
|
IN ULONG ulFlags
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine creates a range list from the intersection of two specified
|
|
range lists. If this API returns CR_OUT_OF_MEMORY, rlhNew is the handle
|
|
of a valid but empty range list.
|
|
|
|
Parameters:
|
|
|
|
rlhOld1 Supplies the handle of a range list to be used as part of the
|
|
intersection.
|
|
|
|
rlhOld2 Supplies the handle of a range list to be used as part of the
|
|
intersection.
|
|
|
|
rlhNew Supplies the handle of the range list that receives the
|
|
intersection of rlhOld1 and rlhOld2. Anything previously contained
|
|
in the rlhNew ragne list is removed by this operation.
|
|
|
|
ulFlags Must be zero.
|
|
|
|
|
|
Return Value:
|
|
|
|
If the function succeeds, the return value is CR_SUCCESS.
|
|
If the function fails, the return value is one of the following:
|
|
CR_INVALID_FLAG,
|
|
CR_INVALID_RANGE_LIST, or
|
|
CR_OUT_OF_MEMORY.
|
|
|
|
--*/
|
|
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
DWORDLONG ulStart = 0, ulEnd = 0;
|
|
PRange_Element pRangeNew = NULL, pRangeOld1 = NULL, pRangeOld2 = NULL;
|
|
BOOL bLock1 = FALSE, bLock2 = FALSE, bLockNew = FALSE;
|
|
|
|
try {
|
|
//
|
|
// validate parameters
|
|
//
|
|
if (!IsValidRangeList(rlhOld1)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (!IsValidRangeList(rlhOld2)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (!IsValidRangeList(rlhNew)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (INVALID_FLAGS(ulFlags, 0)) {
|
|
Status = CR_INVALID_FLAG;
|
|
goto Clean0;
|
|
}
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlhOld1)->RLH_Lock);
|
|
bLock1 = TRUE;
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlhOld2)->RLH_Lock);
|
|
bLock2 = TRUE;
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlhNew)->RLH_Lock);
|
|
bLockNew = TRUE;
|
|
|
|
pRangeNew = (PRange_Element)rlhNew;
|
|
pRangeOld1 = (PRange_Element)rlhOld1;
|
|
pRangeOld2 = (PRange_Element)rlhOld2;
|
|
|
|
//
|
|
// If the new range list is not empty, then delete ranges
|
|
//
|
|
if (pRangeNew->RL_Next != 0) {
|
|
ClearRanges(pRangeNew);
|
|
}
|
|
|
|
//
|
|
// Special case: if either range is empty then there is no
|
|
// intersection by definition
|
|
//
|
|
if (pRangeOld1->RL_Next == 0 || pRangeOld2->RL_Next == 0) {
|
|
goto Clean0;
|
|
}
|
|
|
|
|
|
pRangeOld1 = (PRange_Element)pRangeOld1->RL_Next;
|
|
pRangeOld2 = (PRange_Element)pRangeOld2->RL_Next;
|
|
|
|
for ( ; ; ) {
|
|
//
|
|
// skip over Old2 ranges until intersects with or exceeds
|
|
// current Old1 range (or no more Old2 ranges left)
|
|
//
|
|
while (pRangeOld2->RL_End < pRangeOld1->RL_Start) {
|
|
|
|
if (pRangeOld2->RL_Next == 0) {
|
|
goto Clean0; // Old2 exhausted, we're done
|
|
}
|
|
pRangeOld2 = (PRange_Element)pRangeOld2->RL_Next;
|
|
}
|
|
|
|
//
|
|
// if this Old2 range exceeds Old1 range, then go to the
|
|
// next Old1 range and go through the main loop again
|
|
//
|
|
if (pRangeOld2->RL_Start > pRangeOld1->RL_End) {
|
|
|
|
if (pRangeOld1->RL_Next == 0) {
|
|
goto Clean0; // Old1 exhausted, we're done
|
|
}
|
|
pRangeOld1 = (PRange_Element)pRangeOld1->RL_Next;
|
|
continue;
|
|
}
|
|
|
|
//
|
|
// if we got here there must be an intersection so add
|
|
// the intersected range to New
|
|
//
|
|
ulStart = max(pRangeOld1->RL_Start, pRangeOld2->RL_Start);
|
|
ulEnd = min(pRangeOld1->RL_End, pRangeOld2->RL_End);
|
|
|
|
Status = InsertRange(pRangeNew, ulStart, ulEnd);
|
|
if (Status != CR_SUCCESS) {
|
|
goto Clean0;
|
|
}
|
|
pRangeNew = (PRange_Element)pRangeNew->RL_Next;
|
|
|
|
//
|
|
// after handling the intersection, skip to next ranges in
|
|
// Old1 and Old2 as appropriate
|
|
//
|
|
if (pRangeOld1->RL_End <= ulEnd) {
|
|
if (pRangeOld1->RL_Next == 0) {
|
|
goto Clean0; // Old1 exhausted, we're done
|
|
}
|
|
pRangeOld1 = (PRange_Element)pRangeOld1->RL_Next;
|
|
}
|
|
|
|
if (pRangeOld2->RL_End <= ulEnd) {
|
|
if (pRangeOld2->RL_Next == 0) {
|
|
goto Clean0; // Old1 exhausted, we're done
|
|
}
|
|
pRangeOld2 = (PRange_Element)pRangeOld2->RL_Next;
|
|
}
|
|
}
|
|
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
bLock1 = bLock1; // needed to prevent optimizing this flag away
|
|
bLock2 = bLock2; // needed to prevent optimizing this flag away
|
|
bLockNew = bLockNew; // needed to prevent optimizing this flag away
|
|
Status = CR_FAILURE;
|
|
}
|
|
|
|
|
|
if (bLock1) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlhOld1)->RLH_Lock);
|
|
}
|
|
if (bLock2) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlhOld2)->RLH_Lock);
|
|
}
|
|
if (bLockNew) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlhNew)->RLH_Lock);
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CM_Intersect_Range_List
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CM_Invert_Range_List(
|
|
IN RANGE_LIST rlhOld,
|
|
IN RANGE_LIST rlhNew,
|
|
IN DWORDLONG ullMaxValue,
|
|
IN ULONG ulFlags
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine creates a range list that is the inverse of a specified
|
|
range list; all claimed ranges in the new list are specified as free
|
|
in the old list, and vice-versa. For example, the inversion of
|
|
{[2,4],[6,8]} when the ulMaxValue parameter is 15 is {[0,1],[5,5],[9,15]}.
|
|
If this API returns CR_OUT_OF_MEMORY, rlhNew is the handle of a valid
|
|
but empty range list.
|
|
|
|
|
|
Parameters:
|
|
|
|
rlhOld Supplies the handle of a range list to be inverted.
|
|
|
|
rlhNew Supplies the handle of the range list that receives the
|
|
inverted copy of rlhOld. Anything previously contained in
|
|
the rlhNew range list is removed by this operation.
|
|
|
|
ullMaxValue Uppermost value of the inverted range list.
|
|
|
|
ulFlags Must be zero.
|
|
|
|
|
|
Return Value:
|
|
|
|
If the function succeeds, the return value is CR_SUCCESS.
|
|
If the function fails, the return value is one of the following:
|
|
CR_INVALID_FLAG,
|
|
CR_INVALID_RANGE_LIST,
|
|
CR_OUT_OF_MEMORY.
|
|
|
|
--*/
|
|
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
PRange_Element pRangeNew = NULL, pRangeOld = NULL;
|
|
DWORDLONG ullStart = 0, ullEnd = 0;
|
|
BOOL bLockOld = FALSE, bLockNew = FALSE;
|
|
|
|
try {
|
|
//
|
|
// validate parameters
|
|
//
|
|
if (!IsValidRangeList(rlhOld)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (!IsValidRangeList(rlhNew)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (INVALID_FLAGS(ulFlags, 0)) {
|
|
Status = CR_INVALID_FLAG;
|
|
goto Clean0;
|
|
}
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlhOld)->RLH_Lock);
|
|
bLockOld = TRUE;
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlhNew)->RLH_Lock);
|
|
bLockNew = TRUE;
|
|
|
|
pRangeNew = (PRange_Element)rlhNew;
|
|
pRangeOld = (PRange_Element)rlhOld;
|
|
|
|
//
|
|
// If the new range list is not empty, then delete ranges
|
|
//
|
|
if (pRangeNew->RL_Next != 0) {
|
|
ClearRanges(pRangeNew);
|
|
}
|
|
|
|
//
|
|
// special case: if the old range is empty, then the new range
|
|
// is the entire range (up to max)
|
|
//
|
|
if (pRangeOld->RL_Next == 0) {
|
|
Status = InsertRange(pRangeNew, 0, ullMaxValue);
|
|
goto Clean0;
|
|
}
|
|
|
|
|
|
//
|
|
// invert each of the old ranges
|
|
//
|
|
ullStart = ullEnd = 0;
|
|
|
|
while (pRangeOld->RL_Next != 0) {
|
|
|
|
pRangeOld = (PRange_Element)pRangeOld->RL_Next;
|
|
|
|
//
|
|
// Special start case: if range starts at 0, skip over it
|
|
//
|
|
if (pRangeOld->RL_Start != 0) {
|
|
|
|
//
|
|
// Special end case: check if we've hit the max for the new range
|
|
//
|
|
if (pRangeOld->RL_End >= ullMaxValue) {
|
|
|
|
ullEnd = min(ullMaxValue, pRangeOld->RL_Start - 1);
|
|
Status = InsertRange(pRangeNew, ullStart, ullEnd);
|
|
goto Clean0; // we're done
|
|
}
|
|
|
|
Status = InsertRange(pRangeNew, ullStart, pRangeOld->RL_Start - 1);
|
|
if (Status != CR_SUCCESS) {
|
|
goto Clean0;
|
|
}
|
|
|
|
pRangeNew = (PRange_Element)pRangeNew->RL_Next;
|
|
}
|
|
|
|
ullStart = pRangeOld->RL_End + 1;
|
|
}
|
|
|
|
//
|
|
// add the range that incorporates the end of the old range up to
|
|
// the max value specified
|
|
//
|
|
if (ullStart <= ullMaxValue) {
|
|
Status = InsertRange(pRangeNew, ullStart, ullMaxValue);
|
|
}
|
|
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
bLockOld = bLockOld; // needed to prevent optimizing this flag away
|
|
bLockNew = bLockNew; // needed to prevent optimizing this flag away
|
|
Status = CR_FAILURE;
|
|
}
|
|
|
|
|
|
if (bLockOld) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlhOld)->RLH_Lock);
|
|
}
|
|
if (bLockNew) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlhNew)->RLH_Lock);
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CM_Invert_Range_List
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CM_Merge_Range_List(
|
|
IN RANGE_LIST rlhOld1,
|
|
IN RANGE_LIST rlhOld2,
|
|
IN RANGE_LIST rlhNew,
|
|
IN ULONG ulFlags
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine creates a range list from the union of two specified range
|
|
lists. If this API returns CR_OUT_OF_MEMORY, rlhNew is the handle of a
|
|
valid but empty range list.
|
|
|
|
Parameters:
|
|
|
|
rlhOld1 Supplies the handle of a range list to be used as part of the
|
|
union.
|
|
|
|
rlhOld2 Supplies the handle of a range list to be used as part of the
|
|
union.
|
|
|
|
rlhNew Supplies the handle of the range list that receives the union
|
|
of rlhOld1 and rlhOld2. Anything previously contained in the
|
|
rlhNew range list is removed by this operation.
|
|
|
|
ulFlags Must be zero.
|
|
|
|
|
|
Return Value:
|
|
|
|
If the function succeeds, the return value is CR_SUCCESS.
|
|
If the function fails, the return value is one of the following:
|
|
CR_INVALID_FLAG,
|
|
CR_INVALID_RANGE_LIST, or
|
|
CR_OUT_OF_MEMORY.
|
|
|
|
--*/
|
|
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
DWORDLONG ullStart = 0, ullEnd = 0;
|
|
BOOL bOld1Empty = FALSE, bOld2Empty = FALSE;
|
|
PRange_Element pRangeNew = NULL, pRangeOld1 = NULL, pRangeOld2 = NULL;
|
|
BOOL bLock1 = FALSE, bLock2 = FALSE, bLockNew = FALSE;
|
|
|
|
try {
|
|
//
|
|
// validate parameters
|
|
//
|
|
if (!IsValidRangeList(rlhOld1)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (!IsValidRangeList(rlhOld2)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (!IsValidRangeList(rlhNew)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (INVALID_FLAGS(ulFlags, 0)) {
|
|
Status = CR_INVALID_FLAG;
|
|
goto Clean0;
|
|
}
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlhOld1)->RLH_Lock);
|
|
bLock1 = TRUE;
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlhOld2)->RLH_Lock);
|
|
bLock2 = TRUE;
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlhNew)->RLH_Lock);
|
|
bLockNew = TRUE;
|
|
|
|
pRangeNew = (PRange_Element)rlhNew;
|
|
pRangeOld1 = (PRange_Element)rlhOld1;
|
|
pRangeOld2 = (PRange_Element)rlhOld2;
|
|
|
|
//
|
|
// If the new range list is not empty, then clear it
|
|
//
|
|
if (pRangeNew->RL_Next != 0) {
|
|
ClearRanges(pRangeNew);
|
|
}
|
|
|
|
//
|
|
// Special case: if both ranges are empty then there is no
|
|
// union by definition
|
|
//
|
|
if (pRangeOld1->RL_Next == 0 && pRangeOld2->RL_Next == 0) {
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// Special case: if one range is empty, then the union is just the other
|
|
//
|
|
if (pRangeOld1->RL_Next == 0) {
|
|
pRangeOld2 = (PRange_Element)pRangeOld2->RL_Next;
|
|
CopyRanges(pRangeOld2, pRangeNew); // from -> to
|
|
goto Clean0;
|
|
}
|
|
|
|
if (pRangeOld2->RL_Next == 0) {
|
|
pRangeOld1 = (PRange_Element)pRangeOld1->RL_Next;
|
|
CopyRanges(pRangeOld1, pRangeNew); // from -> to
|
|
goto Clean0;
|
|
}
|
|
|
|
|
|
pRangeOld1 = (PRange_Element)pRangeOld1->RL_Next;
|
|
pRangeOld2 = (PRange_Element)pRangeOld2->RL_Next;
|
|
|
|
|
|
for ( ; ; ) {
|
|
//
|
|
// Pick whichever range comes first between current Old1 range
|
|
// and current Old2 range
|
|
//
|
|
if (pRangeOld1->RL_Start <= pRangeOld2->RL_Start) {
|
|
|
|
ullStart = pRangeOld1->RL_Start;
|
|
ullEnd = pRangeOld1->RL_End;
|
|
|
|
if (pRangeOld1->RL_Next == 0) {
|
|
bOld1Empty = TRUE;
|
|
} else {
|
|
pRangeOld1 = (PRange_Element)pRangeOld1->RL_Next;
|
|
}
|
|
|
|
} else {
|
|
|
|
ullStart = pRangeOld2->RL_Start;
|
|
ullEnd = pRangeOld2->RL_End;
|
|
|
|
if (pRangeOld2->RL_Next == 0) {
|
|
bOld2Empty = TRUE;
|
|
} else {
|
|
pRangeOld2 = (PRange_Element)pRangeOld2->RL_Next;
|
|
}
|
|
}
|
|
|
|
//
|
|
// gather any ranges in Old1 that intersect (ullStart,ullEnd)
|
|
//
|
|
while (pRangeOld1->RL_Start <= ullEnd) {
|
|
|
|
ullEnd = max(ullEnd, pRangeOld1->RL_End);
|
|
|
|
if (pRangeOld1->RL_Next == 0) {
|
|
bOld1Empty = TRUE;
|
|
break;
|
|
}
|
|
pRangeOld1 = (PRange_Element)pRangeOld1->RL_Next;
|
|
}
|
|
|
|
//
|
|
// gather any ranges in Old2 that intersect (ullStart,ullEnd)
|
|
//
|
|
while (pRangeOld2->RL_Start <= ullEnd) {
|
|
|
|
ullEnd = max(ullEnd, pRangeOld2->RL_End);
|
|
|
|
if (pRangeOld2->RL_Next == 0) {
|
|
bOld2Empty = TRUE;
|
|
break;
|
|
}
|
|
pRangeOld2 = (PRange_Element)pRangeOld2->RL_Next;
|
|
}
|
|
|
|
//
|
|
// add (ullStart,ullEnd) to the new range
|
|
//
|
|
Status = InsertRange(pRangeNew, ullStart, ullEnd);
|
|
if (Status != CR_SUCCESS) {
|
|
goto Clean0;
|
|
}
|
|
pRangeNew = (PRange_Element)pRangeNew->RL_Next;
|
|
|
|
//
|
|
// As an optimization, if either range is exhausted first,
|
|
// then only need to duplicate the other remaining ranges.
|
|
//
|
|
if (bOld1Empty && bOld2Empty) {
|
|
goto Clean0; // both exhausted during last pass, we're done
|
|
}
|
|
|
|
if (bOld1Empty) { // Old1 exhausted, copy remaining from Old2
|
|
CopyRanges(pRangeOld2, pRangeNew);
|
|
goto Clean0;
|
|
}
|
|
|
|
if (bOld2Empty) { // Old2 exhausted, copy remaining from Old1
|
|
CopyRanges(pRangeOld1, pRangeNew);
|
|
goto Clean0;
|
|
}
|
|
}
|
|
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
bLock1 = bLock1; // needed to prevent optimizing this flag away
|
|
bLock2 = bLock2; // needed to prevent optimizing this flag away
|
|
bLockNew = bLockNew; // needed to prevent optimizing this flag away
|
|
Status = CR_FAILURE;
|
|
}
|
|
|
|
|
|
if (bLock1) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlhOld1)->RLH_Lock);
|
|
}
|
|
if (bLock2) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlhOld2)->RLH_Lock);
|
|
}
|
|
if (bLockNew) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlhNew)->RLH_Lock);
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CM_Merge_Range_List
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CM_Next_Range(
|
|
IN OUT PRANGE_ELEMENT preElement,
|
|
OUT PDWORDLONG pullStart,
|
|
OUT PDWORDLONG pullEnd,
|
|
IN ULONG ulFlags
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine returns the next range element in a range list. This
|
|
API returns CR_FAILURE if there are no more elements in the range
|
|
list.
|
|
|
|
Parameters:
|
|
|
|
preElement Supplies the address of the handle for the current range
|
|
element. Upon return, this variable receives the handle
|
|
of the next range element.
|
|
|
|
pullStart Supplies the address of the variable that receives the
|
|
starting value of the next range.
|
|
|
|
pullEnd Supplies the address of the variable that receives the
|
|
ending value of the next range.
|
|
|
|
ulFlags Must be zero.
|
|
|
|
|
|
Return Value:
|
|
|
|
If the function succeeds, the return value is CR_SUCCESS.
|
|
If the function fails, the return value is one of the following:
|
|
CR_FAILURE,
|
|
CR_INVALID_FLAG,
|
|
CR_INVALID_POINTER, or
|
|
CR_INVALID_RANGE.
|
|
|
|
--*/
|
|
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
PRange_Element pRange = NULL;
|
|
BOOL bLock = FALSE;
|
|
PRange_List_Hdr prlh = NULL;
|
|
|
|
|
|
try {
|
|
//
|
|
// validate parameters
|
|
//
|
|
if (preElement == NULL || *preElement == 0) {
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (pullEnd == NULL || pullStart == NULL) {
|
|
Status = CR_INVALID_POINTER;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (INVALID_FLAGS(ulFlags, 0)) {
|
|
Status = CR_INVALID_FLAG;
|
|
goto Clean0;
|
|
}
|
|
|
|
prlh = (PRange_List_Hdr)((PRange_Element)(*preElement))->RL_Header;
|
|
LockPrivateResource(&(prlh->RLH_Lock));
|
|
bLock = TRUE;
|
|
|
|
pRange = (PRange_Element)(*preElement);
|
|
|
|
*pullStart = pRange->RL_Start;
|
|
*pullEnd = pRange->RL_End;
|
|
*preElement = (RANGE_ELEMENT)pRange->RL_Next;
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
bLock = bLock; // needed to prevent optimizing this flag away
|
|
Status = CR_FAILURE;
|
|
}
|
|
|
|
if (bLock) {
|
|
UnlockPrivateResource(&(prlh->RLH_Lock));
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CM_Next_Range
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CM_Test_Range_Available(
|
|
IN DWORDLONG ullStartValue,
|
|
IN DWORDLONG ullEndValue,
|
|
IN RANGE_LIST rlh,
|
|
IN ULONG ulFlags
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine checks a range against a range list to ensure that no
|
|
conflicts exist.
|
|
|
|
Parameters:
|
|
|
|
ullStartValue Supplies the low end of the range.
|
|
|
|
ullEndValue Supplies the high end of the range.
|
|
|
|
rlh Supplies the handle to a range list.
|
|
|
|
ulFlags Must be zero.
|
|
|
|
Return Value:
|
|
|
|
If the function succeeds, the return value is CR_SUCCESS.
|
|
If the function fails, the return value is one of the following:
|
|
CR_FAILURE,
|
|
CR_INVALID_FLAG,
|
|
CR_INVALID_RANGE, or
|
|
CR_INVALID_RANGE_LIST.
|
|
|
|
--*/
|
|
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
PRange_Element pRange = NULL;
|
|
BOOL bLock = FALSE;
|
|
|
|
try {
|
|
//
|
|
// validate parameters
|
|
//
|
|
if (!IsValidRangeList(rlh)) {
|
|
Status = CR_INVALID_RANGE_LIST;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (INVALID_FLAGS(ulFlags, 0)) {
|
|
Status = CR_INVALID_FLAG;
|
|
goto Clean0;
|
|
}
|
|
|
|
if (ullEndValue < ullStartValue) {
|
|
Status = CR_INVALID_RANGE;
|
|
goto Clean0;
|
|
}
|
|
|
|
LockPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
bLock = TRUE;
|
|
|
|
pRange = (PRange_Element)rlh;
|
|
|
|
//
|
|
// check each range for a conflict
|
|
//
|
|
while (pRange->RL_Next != 0) {
|
|
|
|
pRange = (PRange_Element)pRange->RL_Next;
|
|
|
|
//
|
|
// If I've already passed the test range, then it's available
|
|
//
|
|
if (ullEndValue < pRange->RL_Start) {
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// check if the start of the test range intersects the current range
|
|
//
|
|
if (ullStartValue >= pRange->RL_Start &&
|
|
ullStartValue <= pRange->RL_End) {
|
|
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// check if the end of the test range intersects the current range
|
|
//
|
|
if (ullEndValue >= pRange->RL_Start &&
|
|
ullEndValue <= pRange->RL_End) {
|
|
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// check if it's a complete overlap
|
|
//
|
|
if (ullStartValue <= pRange->RL_Start &&
|
|
ullEndValue >= pRange->RL_End) {
|
|
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
}
|
|
|
|
//
|
|
// if we got this far, then we made it through the range list
|
|
// without hitting a conflict
|
|
//
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
bLock = bLock; // needed to prevent optimizing this flag away
|
|
Status = CR_FAILURE;
|
|
}
|
|
|
|
if (bLock) {
|
|
UnlockPrivateResource(&((PRange_List_Hdr)rlh)->RLH_Lock);
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CM_Test_Range_Available
|
|
|
|
|
|
|
|
|
|
//------------------------------------------------------------------------
|
|
// Private Utility Functions
|
|
//------------------------------------------------------------------------
|
|
|
|
|
|
BOOL
|
|
IsValidRangeList(
|
|
IN RANGE_LIST rlh
|
|
)
|
|
{
|
|
BOOL Status = TRUE;
|
|
PRange_List_Hdr pRangeHdr = NULL;
|
|
|
|
try {
|
|
|
|
if ((rlh == 0) || (rlh == ((DWORD)-1))) {
|
|
Status = FALSE;
|
|
goto Clean0;
|
|
}
|
|
|
|
pRangeHdr = (PRange_List_Hdr)rlh;
|
|
|
|
if (pRangeHdr->RLH_Signature != Range_List_Signature) {
|
|
Status = FALSE;
|
|
goto Clean0;
|
|
}
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
Status = FALSE;
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // IsValidRangeList
|
|
|
|
|
|
|
|
|
|
CONFIGRET
|
|
AddRange(
|
|
IN PRange_Element prlh,
|
|
IN DWORDLONG ullStartValue,
|
|
IN DWORDLONG ullEndValue,
|
|
IN ULONG ulFlags
|
|
)
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
PRange_Element pPrevious = NULL, pCurrent = NULL;
|
|
|
|
|
|
try {
|
|
|
|
pPrevious = prlh;
|
|
|
|
if (pPrevious->RL_Next == 0) {
|
|
//
|
|
// the range is empty
|
|
//
|
|
Status = InsertRange(pPrevious, ullStartValue, ullEndValue);
|
|
goto Clean0;
|
|
}
|
|
|
|
|
|
while (pPrevious->RL_Next != 0) {
|
|
|
|
pCurrent = (PRange_Element)pPrevious->RL_Next;
|
|
|
|
|
|
if (ullStartValue < pCurrent->RL_Start) {
|
|
|
|
if (ullEndValue < pCurrent->RL_Start) {
|
|
//
|
|
// new range completely contained before this one,
|
|
// add new range between previous and current range
|
|
//
|
|
Status = InsertRange(pPrevious, ullStartValue, ullEndValue);
|
|
goto Clean0;
|
|
}
|
|
|
|
if (ullEndValue <= pCurrent->RL_End) {
|
|
//
|
|
// new range intersects current range, on the low side,
|
|
// enlarge this range to include the new range
|
|
//
|
|
if (ulFlags == CM_ADD_RANGE_DONOTADDIFCONFLICT) {
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
pCurrent->RL_Start = ullStartValue;
|
|
goto Clean0;
|
|
}
|
|
|
|
if ((pCurrent->RL_Next == 0) ||
|
|
(ullEndValue < ((PRange_Element)(pCurrent->RL_Next))->RL_Start)) {
|
|
//
|
|
// new range intersects current range on high and low
|
|
// side, extent range to include the new range
|
|
//
|
|
if (ulFlags == CM_ADD_RANGE_DONOTADDIFCONFLICT) {
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
pCurrent->RL_Start = ullStartValue;
|
|
pCurrent->RL_End = ullEndValue;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// new range intersects more than one range, needs to be
|
|
// merged
|
|
//
|
|
if (ulFlags == CM_ADD_RANGE_DONOTADDIFCONFLICT) {
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
Status = JoinRange(pPrevious, ullStartValue, ullEndValue);
|
|
goto Clean0;
|
|
}
|
|
|
|
|
|
if (ullStartValue <= pCurrent->RL_End+1) {
|
|
|
|
if (ullEndValue <= pCurrent->RL_End) {
|
|
//
|
|
// new range is completely contained inside the current
|
|
// range so nothing to do
|
|
//
|
|
if (ulFlags == CM_ADD_RANGE_DONOTADDIFCONFLICT) {
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
goto Clean0;
|
|
}
|
|
|
|
if ((pCurrent->RL_Next == 0) ||
|
|
(ullEndValue < ((PRange_Element)(pCurrent->RL_Next))->RL_Start)) {
|
|
//
|
|
// new range intersects current range on high end only,
|
|
// extend range to include the new range
|
|
//
|
|
if (ulFlags == CM_ADD_RANGE_DONOTADDIFCONFLICT) {
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
pCurrent->RL_End = ullEndValue;
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// new range intersects more than one range, needs to be
|
|
// merged
|
|
//
|
|
if (ulFlags == CM_ADD_RANGE_DONOTADDIFCONFLICT) {
|
|
Status = CR_FAILURE;
|
|
goto Clean0;
|
|
}
|
|
|
|
Status = JoinRange(pPrevious, ullStartValue, ullEndValue);
|
|
goto Clean0;
|
|
}
|
|
|
|
//
|
|
// step to the next range
|
|
//
|
|
pPrevious = pCurrent;
|
|
pCurrent = (PRange_Element)pCurrent->RL_Next;
|
|
}
|
|
|
|
//
|
|
// if we got here then we need to just insert this range to the end
|
|
// of the range list
|
|
//
|
|
Status = InsertRange(pPrevious, ullStartValue, ullEndValue);
|
|
|
|
Clean0:
|
|
NOTHING;
|
|
|
|
} except(EXCEPTION_EXECUTE_HANDLER) {
|
|
Status = 0;
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // AddRange
|
|
|
|
|
|
|
|
CONFIGRET
|
|
InsertRange(
|
|
IN PRange_Element pParentElement,
|
|
IN DWORDLONG ullStartValue,
|
|
IN DWORDLONG ullEndValue)
|
|
{
|
|
PRange_Element pNewElement = NULL;
|
|
|
|
|
|
pNewElement = (PRange_Element)pSetupMalloc(sizeof(Range_Element));
|
|
|
|
if (pNewElement == NULL) {
|
|
return CR_OUT_OF_MEMORY;
|
|
}
|
|
|
|
pNewElement->RL_Next = pParentElement->RL_Next; // rejoin the link
|
|
pNewElement->RL_Start = ullStartValue;
|
|
pNewElement->RL_End = ullEndValue;
|
|
pNewElement->RL_Header = pParentElement->RL_Header;
|
|
pParentElement->RL_Next = (ULONG_PTR)pNewElement;
|
|
|
|
return CR_SUCCESS;
|
|
|
|
} // InsertRange
|
|
|
|
|
|
|
|
CONFIGRET
|
|
DeleteRange(
|
|
IN PRange_Element pParentElement
|
|
)
|
|
{
|
|
PRange_Element pTemp = NULL;
|
|
|
|
//
|
|
// must pass a valid parent of the range to delete (in otherwords,
|
|
// can't pass the last range)
|
|
//
|
|
|
|
if (pParentElement == 0) {
|
|
return CR_FAILURE;
|
|
}
|
|
|
|
pTemp = (PRange_Element)(pParentElement->RL_Next);
|
|
if (pTemp == 0) {
|
|
return CR_FAILURE;
|
|
}
|
|
|
|
pParentElement->RL_Next =
|
|
((PRange_Element)(pParentElement->RL_Next))->RL_Next;
|
|
|
|
pSetupFree(pTemp);
|
|
|
|
return CR_SUCCESS;
|
|
|
|
} // DeleteRange
|
|
|
|
|
|
|
|
CONFIGRET
|
|
JoinRange(
|
|
IN PRange_Element pParentElement,
|
|
IN DWORDLONG ullStartValue,
|
|
IN DWORDLONG ullEndValue
|
|
)
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
PRange_Element pCurrent = NULL, pNext = NULL;
|
|
|
|
|
|
if (pParentElement->RL_Next == 0) {
|
|
return CR_SUCCESS; // at the end, nothing to join
|
|
}
|
|
|
|
//
|
|
// pCurrent is the starting range of intersecting ranges that need
|
|
// to be joined
|
|
//
|
|
pCurrent = (PRange_Element)pParentElement->RL_Next;
|
|
|
|
//
|
|
// set start of joined range
|
|
//
|
|
if (ullStartValue < pCurrent->RL_Start) {
|
|
pCurrent->RL_Start = ullStartValue;
|
|
}
|
|
|
|
//
|
|
// find the end of the joined range
|
|
//
|
|
while (pCurrent->RL_Next != 0) {
|
|
pNext = (PRange_Element)pCurrent->RL_Next;
|
|
|
|
//
|
|
// I know this next range needs to be absorbed in all cases so
|
|
// reset the end point to at least include the next range
|
|
//
|
|
pCurrent->RL_End = pNext->RL_End;
|
|
|
|
if (ullEndValue <= pNext->RL_End) {
|
|
DeleteRange(pCurrent); // delete the range following current
|
|
break; // we're done
|
|
}
|
|
|
|
if ((pNext->RL_Next == 0) ||
|
|
(ullEndValue < ((PRange_Element)(pNext->RL_Next))->RL_Start)) {
|
|
//
|
|
// adjust the end point of the newly joined range and then we're done
|
|
//
|
|
pCurrent->RL_End = ullEndValue;
|
|
DeleteRange(pCurrent); // delete the range following current
|
|
break;
|
|
}
|
|
|
|
DeleteRange(pCurrent); // delete the range following current
|
|
|
|
// if we got here, there are more ranges to join
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // JoinRange
|
|
|
|
|
|
|
|
CONFIGRET
|
|
CopyRanges(
|
|
IN PRange_Element pFromRange,
|
|
IN PRange_Element pToRange
|
|
)
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
|
|
//
|
|
// copy each range in pFromRange to pToRange
|
|
//
|
|
for ( ; ; ) {
|
|
|
|
Status = AddRange(pToRange,
|
|
pFromRange->RL_Start,
|
|
pFromRange->RL_End,
|
|
CM_ADD_RANGE_ADDIFCONFLICT);
|
|
|
|
if (Status != CR_SUCCESS) {
|
|
break;
|
|
}
|
|
|
|
pToRange = (PRange_Element)pToRange->RL_Next;
|
|
|
|
if (pFromRange->RL_Next == 0) {
|
|
break;
|
|
}
|
|
|
|
pFromRange = (PRange_Element)pFromRange->RL_Next;
|
|
}
|
|
|
|
return Status;
|
|
|
|
} // CopyRanges
|
|
|
|
|
|
|
|
CONFIGRET
|
|
ClearRanges(
|
|
IN PRange_Element pRange
|
|
)
|
|
{
|
|
CONFIGRET Status = CR_SUCCESS;
|
|
|
|
//
|
|
// If the range list is not empty, then delete ranges
|
|
//
|
|
if (pRange->RL_Next != 0) {
|
|
|
|
while (Status == CR_SUCCESS) {
|
|
//
|
|
// keep deleting the first range after the header (pass parent
|
|
// of range to delete)
|
|
//
|
|
Status = DeleteRange(pRange);
|
|
}
|
|
}
|
|
|
|
return CR_SUCCESS; // Status is set to end deleting ranges, don't return it
|
|
|
|
} // ClearRanges
|
|
|
|
|
|
|
|
CONFIGRET
|
|
TestRange(
|
|
IN PRange_Element rlh,
|
|
IN DWORDLONG ullStartValue,
|
|
IN DWORDLONG ullEndValue,
|
|
OUT PRange_Element *pConflictingRange
|
|
)
|
|
|
|
{
|
|
PRange_Element pRange = (PRange_Element)rlh;
|
|
|
|
//
|
|
// check each range for a conflict
|
|
//
|
|
while (pRange->RL_Next != 0) {
|
|
|
|
pRange = (PRange_Element)pRange->RL_Next;
|
|
|
|
if (pRange->RL_Start > ullEndValue) {
|
|
//
|
|
// We've gone past the range in question so no conflict
|
|
//
|
|
return CR_SUCCESS;
|
|
}
|
|
|
|
if (pRange->RL_End < ullStartValue) {
|
|
//
|
|
// this range is still below the range in question, skip to next range
|
|
//
|
|
continue;
|
|
}
|
|
|
|
//
|
|
// otherwise there's a conflict
|
|
//
|
|
*pConflictingRange = pRange;
|
|
return CR_FAILURE;
|
|
}
|
|
|
|
return CR_SUCCESS;
|
|
|
|
} // TestRange
|
|
|
|
|