Return Value:

    The cluster number of the 'Index'th cluster in the cluster chain
    beginning with cluster 'StartingCluster' or 0.

--*/
{
    for (; Index; Index--) {

        if (!IsInRange(StartingCluster)) {
            return 0;
        }

        StartingCluster = QueryEntry(StartingCluster);
    }

    return StartingCluster;
}


UFAT_EXPORT
ULONG
FAT::QueryLengthOfChain(
    IN  ULONG    StartingCluster,
    OUT PULONG   LastCluster
    ) CONST
/*++

Routine Description:

    This routine computes the length of a cluster chain given the number
    of its first cluster.

    This routine depends on the chain being valid.  In particular, if the
    chain contains any cycles then this routine will not finish.  The
    routine 'ScrubChain' will turn an invalid chain into a valid one.

Arguments:

    StartingCluster - Supplies the first cluster of a cluster chain.
    LastCluster     - Returns the number of the last cluster in the chain.

Return Value:

    The length of the cluster chain beginning with 'StartingCluster'.

--*/
{
    ULONG    length;

    if (!StartingCluster) {
        if (LastCluster) {
            *LastCluster = 0;
        }
        return 0;
    }

    for (length = 1; IsInRange(StartingCluster) && !IsEndOfChain(StartingCluster); length++) {
        StartingCluster = QueryEntry(StartingCluster);
    }

    if (LastCluster) {
        *LastCluster = StartingCluster;
    }

    return length;
}


ULONG
FAT::QueryLengthOfChain(
    IN  ULONG    StartingCluster,
    IN  ULONG    EndingCluster
    ) CONST
/*++

Routine Description:

    This routine computes the length of a cluster chain given the number
    of its first cluster and the number of its last cluster.  To compute
    the length of a chain which is terminated by "end of chain", see
    the one parameter version of this routine above.  If 'EndingCluster'
    is not a member of the chain beginning with 'StartingCluster' then
    this routine will return 0.

    This routine depends on the chain being valid.

Arguments:

    StartingCluster - Supplies the first cluster of the cluster chain.
    EndingCluster   - Supplies the last cluster of the cluster chain.

Return Value:

    The length of the cluster chain beginning with 'StartingCluster' and
    ending with 'EndingCluster' or 0.

--*/
{
    ULONG    length;

    if (!StartingCluster) {
        return 0;
    }

    for (length = 1; StartingCluster != EndingCluster &&
                     !IsEndOfChain(StartingCluster); length++) {
        StartingCluster = QueryEntry(StartingCluster);
    }

    return StartingCluster == EndingCluster ? length : 0;
}


ULONG
FAT::QueryPrevious(
    IN  ULONG    Cluster
    ) CONST
/*++

Routine Description:

    Obtains the previous cluster in a chain, i.e. the cluster that
    references the given cluster.

Arguments:

    Cluster -   Supplies the cluster whose predecesor we're looking for.

Return Value:

    The predecesor of the given cluster. 0 if there is no predecesor.

--*/

{
    ULONG    i;

    DebugAssert( Cluster );

    if ( !IsClusterFree( Cluster ) ) {
        for (i = FirstDiskCluster; IsInRange(i); i++) {
            if ( QueryEntry(i) == Cluster ) {
                return i;
            }
        }
    }

    return 0;
}


VOID
FAT::Scrub(
    OUT PBOOLEAN    ChangesMade
    )
/*++

Routine Description:

    This routine goes through all of the FAT entries changing invalid values
    to reasonable values for the purposes of CHKDSK.

    Illegal FAT entries are those that are set out of disk range and that
    are not magic values.  This routine will set all illegal FAT entries to
    the "end of chain" magic value.

Arguments:

    ChangesMade - Returns TRUE if any changes were made to the FAT.

Return Value:

    None.

--*/
{
    ULONG    i;

    if (ChangesMade) {
        *ChangesMade = FALSE;
    }

    for (i = FirstDiskCluster; IsInRange(i); i++) {
        if (!IsInRange(QueryEntry(i)) &&
            !IsClusterFree(i) &&
            !IsEndOfChain(i) &&
            !IsClusterBad(i) &&
            !IsClusterReserved(i)) {

            SetEndOfChain(i);

            if (ChangesMade) {
                *ChangesMade = TRUE;
            }
        }
    }
}


VOID
FAT::ScrubChain(
    IN      ULONG        StartingCluster,
    OUT     PBOOLEAN     ChangesMade
    )
/*++

Routine Description:

    This routine goes through all of the FAT entries in the chain beginning
    with cluster 'StartingCluster'.  It is expected that all of the entries
    in this chain point to valid clusters on the disk.  This routine will
    mark the first invalid entry, if any, as the final cluster of the chain
    thus transforming the invalid chain into a valid one.

Arguments:

    StartingCluster - Supplies the first cluster of the chain to
                      scrub.
    ChangesMade     - Returns TRUE if changes were made to correct
                      the chain.

Return Value:

    None.

--*/
{
    ULONG    clus, next;

    DebugAssert(IsInRange(StartingCluster));
    DebugAssert(ChangesMade);

    *ChangesMade = FALSE;

    clus = StartingCluster;
    while (!IsEndOfChain(clus)) {

        next = QueryEntry(clus);
        if (!IsInRange(next) || IsClusterFree(next)) {
            SetEndOfChain(clus);
            *ChangesMade = TRUE;
            return;
        }

        clus = next;
    }
}


VOID
FAT::ScrubChain(
    IN      ULONG       StartingCluster,
    OUT     PBITVECTOR  FatBitMap,
    OUT     PBOOLEAN    ChangesMade,
    OUT     PBOOLEAN    CrossLinkDetected,
    OUT     PULONG      CrossLinkPreviousCluster
    )
/*++

Routine Description:

    This routine goes through all of the FAT entries in the chain beginning
    with cluster 'StartingCluster'.  It is expected that all of the entries
    in this chain point to valid clusters on the disk.  This routine will
    mark the first invalid entry, if any, as the final cluster of the chain
    thus transforming the invalid chain into a valid one.

    This routine will also eliminate any cycles in the cluster chain as well
    as detect cross-links.

Arguments:

    StartingCluster             - Supplies the first cluster of the chain to
                                    scrub.
    UsedClusters                - Supplies a bitvector marking all used
                                    clusters.
    ChangesMade                 - Returns TRUE if changes were made to correct
                                    the chain.
    CrossLinkDetected           - Returns TRUE if a cluster in the chain was
                                    already claimed in the 'FatBitMap'.
    CrossLinkPreviousCluster    - Returns the cluster number previous to the
                                    cross linked cluster number or 0 if the
                                    cross linked cluster number was the first
                                    in the chain.

Return Value:

    None.

--*/
{
    ULONG    clus, next;

    DebugAssert(IsInRange(StartingCluster));
    DebugAssert(ChangesMade);
    DebugAssert(CrossLinkDetected);
    DebugAssert(CrossLinkPreviousCluster);

    *ChangesMade = FALSE;
    *CrossLinkDetected = FALSE;

    if (FatBitMap->IsBitSet(StartingCluster)) {
        *CrossLinkDetected = TRUE;
        *CrossLinkPreviousCluster = 0;
        return;
    }

    clus = StartingCluster;
    while (!IsEndOfChain(clus)) {

        FatBitMap->SetBit(clus);

        next = QueryEntry(clus);
        if (!IsInRange(next) || IsClusterFree(next)) {
            SetEndOfChain(clus);
            *ChangesMade = TRUE;
            return;
        }

        if (FatBitMap->IsBitSet(next)) {

            if (clus == next) {       // Cluster points to itself.
                *ChangesMade = TRUE;
                SetEndOfChain(clus);
                return;
            }

            while (StartingCluster != clus) {

                if (StartingCluster == next) { // Cluster points to previous.
                    *ChangesMade = TRUE;
                    SetEndOfChain(clus);
                    return;
                }

                StartingCluster = QueryEntry(StartingCluster);
            }

            // Otherwise it's a cross link, not a cycle.

            *CrossLinkDetected = TRUE;
            *CrossLinkPreviousCluster = clus;
            return;
        }

        clus = next;
    }

    FatBitMap->SetBit(clus);
}

NONVIRTUAL
BOOLEAN
FAT::IsValidChain(
    IN  ULONG    StartingCluster
    ) CONST
/*++

Routine Description:

    This method determines whether the chain is valid, ie. that it
    consists of a chain of valid cluster numbers ending with an end
    of chain entry.

Arguments:

    StartingCluster - Supplies the first cluster of the chain.

Return Value:

    TRUE if the chain is valid.

--*/
{
    ULONG    current;
    ULONG    clusters_in_chain = 0;

    current = StartingCluster;

    for( ;; ) {

        if (!IsInRange(current) ||
            clusters_in_chain++ > _num_entries ) {

            // Either a bad entry or an infinite loop detected.
            //
            return FALSE;
        }

        if (IsEndOfChain(current)) {
            break;
        }

        current = QueryEntry(current);
    }

    return TRUE;
}


UFAT_EXPORT
ULONG
FAT::AllocChain(
    IN  ULONG    Length,
    OUT PULONG   LastCluster
    )
/*++

Routine Description:

    This routine attempts to allocate a chain of length 'Length' from the
    FAT.  If this routine is successful it will return the cluster number
    of the beginning of the chain.  Upon failure this routine will return
    0 and will make no changes to the FAT.

Arguments:

    Length      - Supplies the length of the chain desired.
    LastCluster - Returns the last cluster of the allocated chain.

Return Value:

    The cluster number of the beginning of the allocated chain or 0.

--*/
{
    ULONG    i, j;
    ULONG    start;
    ULONG    prev;

    if (!Length) {
        return 0;
    }

    start = 0;
    prev = 0;
    for (i = FirstDiskCluster; IsInRange(i); i++) {
        if (IsClusterFree(i)) {
            if (!start) {
                start = i;
            } else {
                SetEntry(prev, i);
            }
            prev = i;
            Length--;
            if (!Length) {
                SetEndOfChain(i);

                if (LastCluster) {
                    *LastCluster = i;
                }

                return start;
            }
        }
    }

    // There is not enough disk space for the chain so free what was taken.
    for (i = start; i != prev; ) {
        j = QueryEntry(i);
        SetClusterFree(i);
        i = j;
    }

    return 0;
}


ULONG
FAT::ReAllocChain(
    IN  ULONG    StartOfChain,
    IN  ULONG    NewLength,
    OUT PULONG   LastCluster
    )
/*++

Routine Description:

    This routine insures that the cluster chain beginning at cluster
    'StartOfChain' is of length greater than or equal to 'NewSize'.
    If it is not then this routine will attempt to grow the chain by
    allocating new clusters.  Failure to allocate sufficient clusters
    to grow the chain to 'NewSize' clusters will cause this routine to
    restore the chain to its original length and state.  This routine will
    return the current length of the chain : either the old length or the
    new length.  If an error occurs then 0 will be returned.

Arguments:

    StartOfChain    - Supplies the first cluster of the chain.
    NewLength       - Supplies the desired new length of the chain.
    LastCluster     - Returns the last cluster of the chain.

Return Value:

    The current length of the chain or 0.

--*/
{
    ULONG    length;
    ULONG    new_clusters_needed;
    ULONG    end_of_chain;
    ULONG    i, j;
    ULONG    start;

    if (!IsInRange(StartOfChain)) {
        return 0;
    }

    for (length = 1; !IsEndOfChain(StartOfChain); length++) {
        StartOfChain = QueryEntry(StartOfChain);
        if (!IsInRange(StartOfChain)) {
            return 0;
        }
    }

    if (length >= NewLength) {
        if (LastCluster) {
            *LastCluster = StartOfChain;
        }
        return length;
    }

    new_clusters_needed = NewLength - length;

    start = end_of_chain = StartOfChain;
    for (i = FirstDiskCluster; IsInRange(i); i++) {
        if (IsClusterFree(i)) {
            SetEntry(end_of_chain, i);
            end_of_chain = i;
            new_clusters_needed--;
            if (!new_clusters_needed) {
                SetEndOfChain(i);
                if (LastCluster) {
                    *LastCluster = i;
                }
                return NewLength;
            }
        }
    }

    // There is not enough disk space to lengthen the new chain so
    // settle for the old length.

    for (i = start; i != end_of_chain; ) {
        j = QueryEntry(i);
        SetClusterFree(i);
        i = j;
    }

    SetEndOfChain(start);

    if (LastCluster) {
        *LastCluster = start;
    }

    return length;
}


UFAT_EXPORT
VOID
FAT::FreeChain(
    IN  ULONG    StartOfChain
    )
/*++

Routine Description:

    This routine sets free all of the clusters in the cluster chain
    beginning with 'StartOfChain'.

Arguments:

    StartOfChain    - Supplies the first cluster of the chain to free.

Return Value:

    None.

--*/
{
    ULONG    tmp;

    while (!IsEndOfChain(StartOfChain)) {
        tmp = QueryEntry(StartOfChain);
        SetClusterFree(StartOfChain);
        StartOfChain = tmp;
    }
    SetClusterFree(StartOfChain);
}