numset.cxx

EFI（Extensible Firmware Interface)是下一代BIOS

    PNUMBER_EXTENT  new_extent;
    BIG_INT         next;

    DebugAssert(_iterator);
    DebugAssert(Duplicate);

    *Duplicate = FALSE;

    _iterator->Reset();
    while (p = (PNUMBER_EXTENT) _iterator->GetPrevious()) {
        if (p->Start <= Number) {
            break;
        }
    }

    if (p) {

        next = p->Start + p->Length;

        if (Number < next) {
            *Duplicate = TRUE;
            return TRUE;
        }

        if (Number == next) {

            p->Length += 1;
            _card += 1;

            if (pn = (PNUMBER_EXTENT) _iterator->GetNext()) {

                if (pn->Start == Number + 1) {

                    p->Length += pn->Length;
                    pn = (PNUMBER_EXTENT) _list.Remove(_iterator);
                    DELETE(pn);
                }
            }

            return TRUE;
        }
    }

    if (p = (PNUMBER_EXTENT) _iterator->GetNext()) {

        if (Number + 1 == p->Start) {

            p->Start = Number;
            p->Length += 1;
            _card += 1;
            return TRUE;
        }
    }

    if (!(new_extent = NEW NUMBER_EXTENT)) {
        return FALSE;
    }

    new_extent->Start = Number;
    new_extent->Length = 1;

    if (!_list.Insert(new_extent, _iterator)) {
        DELETE(new_extent);
        return FALSE;
    }

    _card += 1;

    return TRUE;
}

IFSUTIL_EXPORT
BOOLEAN
NUMBER_SET::Remove(
    IN  BIG_INT     Number
    )
/*++

Routine Description:

    This routine removes a number from the number set.

Arguments:

    Number  - Supplies the number to remove.

Routine Description:

    FALSE   - Failure.
    TRUE    - Success.

--*/
{
    PNUMBER_EXTENT  p;
    PNUMBER_EXTENT  new_extent;
    BIG_INT         next, new_length;

    DebugAssert(_iterator);

    _iterator->Reset();
    while (p = (PNUMBER_EXTENT) _iterator->GetNext()) {
        if (p->Start > Number) {
            break;
        }
    }

    if (p = (PNUMBER_EXTENT) _iterator->GetPrevious()) {

        next = p->Start + p->Length;

        if (p->Start == Number) {
            p->Start += 1;
            p->Length -= 1;
            _card -= 1;

            if (p->Length == 0) {
                p = (PNUMBER_EXTENT) _list.Remove(_iterator);
                DELETE(p);
            }

            return TRUE;
        }

        if (Number + 1 == next) {
            p->Length -= 1;
            _card -= 1;
            return TRUE;
        }

        if (Number < next) {

            if (!(new_extent = NEW NUMBER_EXTENT)) {
                return FALSE;
            }

            _iterator->GetNext();

            if (!_list.Insert(new_extent, _iterator)) {
                DELETE(new_extent);
                return FALSE;
            }

            new_length = Number - p->Start;

            new_extent->Start = Number + 1;
            new_extent->Length = p->Length - 1 - new_length;

            p->Length = new_length;

            _card -= 1;
        }
    }

    return TRUE;
}

IFSUTIL_EXPORT
BOOLEAN
NUMBER_SET::RemoveAll(
     )
{
    PNUMBER_EXTENT  p;

    DebugAssert(_iterator);

    _iterator->Reset();
    if ((p = (PNUMBER_EXTENT) _iterator->GetNext()))
        do {
            p = (PNUMBER_EXTENT) _list.Remove(_iterator);
            DELETE(p);
        } while ((p=(PNUMBER_EXTENT)_iterator->GetCurrent()));
    _card = 0;
    return TRUE;
}

IFSUTIL_EXPORT
BOOLEAN
NUMBER_SET::CheckAndRemove(
    IN  BIG_INT     Number,
     OUT PBOOLEAN   DoesExists
    )
/*++

Routine Description:

    This routine removes a number from the number set.

Arguments:

    Number      - Supplies the number to remove.
     DoesExists - TRUE if Number was found in the set

Routine Description:

    FALSE   - Failure.
    TRUE    - Success.

--*/
{
    PNUMBER_EXTENT  p;
    PNUMBER_EXTENT  new_extent;
    BIG_INT         next, new_length;

    DebugAssert(_iterator);
    DebugAssert(DoesExists);

    *DoesExists = FALSE;

    _iterator->Reset();
    while (p = (PNUMBER_EXTENT) _iterator->GetNext()) {
        if (p->Start > Number) {
            break;
        }
    }

    if (p = (PNUMBER_EXTENT) _iterator->GetPrevious()) {

        next = p->Start + p->Length;

        if (p->Start == Number) {
            p->Start += 1;
            p->Length -= 1;
            _card -= 1;
            *DoesExists = TRUE;

            if (p->Length == 0) {
                p = (PNUMBER_EXTENT) _list.Remove(_iterator);
                DELETE(p);
            }

            return TRUE;
        }

        if (Number + 1 == next) {
            p->Length -= 1;
            _card -= 1;
            *DoesExists = TRUE;
            return TRUE;
        }

        if (Number < next) {

            if (!(new_extent = NEW NUMBER_EXTENT)) {
                return FALSE;
            }

            _iterator->GetNext();

            if (!_list.Insert(new_extent, _iterator)) {
                DELETE(new_extent);
                return FALSE;
            }

            new_length = Number - p->Start;

            new_extent->Start = Number + 1;
            new_extent->Length = p->Length - 1 - new_length;

            p->Length = new_length;

            _card -= 1;
            *DoesExists = TRUE;
        }
    }

    return TRUE;
}


IFSUTIL_EXPORT
BOOLEAN
NUMBER_SET::Remove(
    IN  BIG_INT Start,
    IN  BIG_INT Length
    )
/*++

Routine Description:

    This routine removes the given range from the number set.

Arguments:

    Start   - Supplies the beginning of the range.
    Length  - Supplies the length of the range.

Routine Description:

    FALSE   - Failure.
    TRUE    - Success.

--*/
{
    BIG_INT i, sup;
    BOOLEAN r;

    sup = Start + Length;

    r = TRUE;
    for (i = Start; i < sup; i += 1) {
        r = Remove(i) && r;
    }

    return r;
}


IFSUTIL_EXPORT
BOOLEAN
NUMBER_SET::Remove(
    IN  PCNUMBER_SET    NumberSet
    )
/*++

Routine Description:

    This routine removes all of the elements in the given number set from
    this one.

Arguments:

    NumberSet   - Supplies the numbers to remove.

Return Value:

    FALSE   - Failure.
    TRUE    - Success.

--*/
{
    ULONG   i, n;
    BIG_INT s, l;

    n = NumberSet->QueryNumDisjointRanges();
    for (i = 0; i < n; i++) {

        NumberSet->QueryDisjointRange(i, &s, &l);

        if (!Remove(s, l)) {
            return FALSE;
        }
    }

    return TRUE;
}


IFSUTIL_EXPORT
BIG_INT
NUMBER_SET::QueryNumber(
    IN  BIG_INT Index
    ) CONST
/*++

Routine Description:

    This routine returns the Nth number contained in this set.

Arguments:

    Index   - Supplies a zero-based index into the ordered set.

Return Value:

    The Nth number in this set.

--*/
{
    PNUMBER_EXTENT  p;
    BIG_INT         r;
    BIG_INT         count;

    DebugAssert(Index < _card);

    _iterator->Reset();
    count = 0;
    while (p = (PNUMBER_EXTENT) _iterator->GetNext()) {

        count += p->Length;

        if (count > Index) {
            break;
        }
    }

    DebugAssert(p);

    return p->Start + Index - (count - p->Length);
}


IFSUTIL_EXPORT
BOOLEAN
NUMBER_SET::DoesIntersectSet(
    IN  BIG_INT Start,
    IN  BIG_INT Length
    ) CONST
/*++

Routine Description:

    This routine computes whether or not the range specified intersects
    the current number set.  This routine will return FALSE if the
    intersection is empty, TRUE otherwise.

Arguments:

    Start   - Supplies the start of the range.
    Length  - Supplies the length of the range.

Return Value:

    FALSE   - The specified range does not intersect the number set.
    TRUE    - The specified range makes a non-empty intersection with
                the number set.

--*/
{
    PNUMBER_EXTENT  p;
    BIG_INT         pnext, next;

    DebugAssert(_iterator);

    if (Length == 0) {
        return FALSE;
    }

    next = Start + Length;

    _iterator->Reset();
    while (p = (PNUMBER_EXTENT) _iterator->GetNext()) {

        pnext = p->Start + p->Length;

        if (Start >= p->Start) {

            if (Start < pnext) {
                return TRUE;
            }
        } else {

            if (next > p->Start) {
                return TRUE;
            }
        }
    }

    return FALSE;
}


IFSUTIL_EXPORT
VOID
NUMBER_SET::QueryDisjointRange(
    IN  ULONG       Index,
    OUT PBIG_INT    Start,
    OUT PBIG_INT    Length
    ) CONST
/*++

Routine Description:

    This routine returns the 'Index'th disjoint range.  (This is zero
    based).

Arguments:

    Index   - Supplies the index of the disjoint range.
    Start   - Returns the start of the disjoint range.
    Length  - Returns the length of the disjoint range.

Return Value:

    None.

--*/
{
    ULONG           i;
    PNUMBER_EXTENT  p;

    DebugAssert(_iterator);

    _iterator->Reset();
    for (i = 0; i <= Index; i++) {
        p = (PNUMBER_EXTENT) _iterator->GetNext();
    }

    DebugAssert(p);
    DebugAssert(Start);
    DebugAssert(Length);

    *Start = p->Start;
    *Length = p->Length;
}


IFSUTIL_EXPORT
BOOLEAN
NUMBER_SET::QueryContainingRange(
    IN  BIG_INT     Number,
    OUT PBIG_INT    Start,
    OUT PBIG_INT    Length
    ) CONST
/*++

Routine Description:

    This routine returns the range that contains the given number.

Arguments:

    Number  - Supplies the number.
    Start   - Returns the start of the range.
    Length  - Returns the length of the range.

Return Value:

    FALSE   - The given number was not in the set.
    TRUE    - Success.

--*/
{
    PNUMBER_EXTENT  p;

    DebugAssert(_iterator);

    _iterator->Reset();
    while (p = (PNUMBER_EXTENT) _iterator->GetPrevious()) {
        if (p->Start <= Number) {
            break;
        }
    }

    if (!p || Number >= p->Start + p->Length) {
        return FALSE;
    }

    *Start = p->Start;
    *Length = p->Length;

    return TRUE;
}