splaysup.c File Reference

#include "fatprocs.h"

Include dependency graph for splaysup.c:

Go to the source code of this file.

Macros
#define	BugCheckFileId   (FAT_BUG_CHECK_SPLAYSUP)
#define	Dbg   (DEBUG_TRACE_SPLAYSUP)

Functions
VOID	FatInsertName (IN PIRP_CONTEXT IrpContext, IN PRTL_SPLAY_LINKS *RootNode, IN PFILE_NAME_NODE Name)
VOID	FatRemoveNames (IN PIRP_CONTEXT IrpContext, IN PFCB Fcb)
PFCB	FatFindFcb (IN PIRP_CONTEXT IrpContext, IN OUT PRTL_SPLAY_LINKS *RootNode, IN PSTRING Name, OUT PBOOLEAN FileNameDos OPTIONAL)
COMPARISON	FatCompareNames (IN PSTRING NameA, IN PSTRING NameB)

Macro Definition Documentation

BugCheckFileId

#define BugCheckFileId   (FAT_BUG_CHECK_SPLAYSUP)

Definition at line 22 of file splaysup.c.

Dbg

#define Dbg   (DEBUG_TRACE_SPLAYSUP)

Definition at line 28 of file splaysup.c.

Function Documentation

FatCompareNames()

COMPARISON FatCompareNames	(	IN PSTRING	NameA,
		IN PSTRING	NameB
	)

Definition at line 421 of file splaysup.c.

{
    ULONG i;
    ULONG MinLength;
 
    PAGED_CODE();
 
    //
    //  Figure out the minimum of the two lengths
    //
 
    MinLength = NameA->Length < NameB->Length ? NameA->Length :
                                                NameB->Length;
 
    //
    //  Loop through looking at all of the characters in both strings
    //  testing for equalilty, less than, and greater than
    //
 
    i = (ULONG)RtlCompareMemory( NameA->Buffer, NameB->Buffer, MinLength );
 
 
    if (i < MinLength) {
 
        return NameA->Buffer[i] < NameB->Buffer[i] ? IsLessThan :
                                                     IsGreaterThan;
    }
 
    if (NameA->Length < NameB->Length) {
 
        return IsLessThan;
    }
 
    if (NameA->Length > NameB->Length) {
 
        return IsGreaterThan;
    }
 
    return IsEqual;
}

FatFindFcb()

PFCB FatFindFcb	(	IN PIRP_CONTEXT	IrpContext,
		IN OUT PRTL_SPLAY_LINKS *	RootNode,
		IN PSTRING	Name,
		OUT PBOOLEAN FileNameDos	OPTIONAL
	)

Definition at line 306 of file splaysup.c.

{
    COMPARISON Comparison;
    PFILE_NAME_NODE Node;
    PRTL_SPLAY_LINKS Links;
 
    PAGED_CODE();
    UNREFERENCED_PARAMETER( IrpContext );
 
    Links = *RootNode;
 
    while (Links != NULL) {
 
        Node = CONTAINING_RECORD(Links, FILE_NAME_NODE, Links);
 
        //
        //  Compare the prefix in the tree with the full name
        //
 
        Comparison = CompareNames(&Node->Name.Oem, Name);
 
        //
        //  See if they don't match
        //
 
        if (Comparison == IsGreaterThan) {
 
            //
            //  The prefix is greater than the full name
            //  so we go down the left child
            //
 
            Links = RtlLeftChild(Links);
 
            //
            //  And continue searching down this tree
            //
 
        } else if (Comparison == IsLessThan) {
 
            //
            //  The prefix is less than the full name
            //  so we go down the right child
            //
 
            Links = RtlRightChild(Links);
 
            //
            //  And continue searching down this tree
            //
 
        } else {
 
            //
            //  We found it.
            //
            //  Splay the tree and save the new root.
            //
 
            *RootNode = RtlSplay(Links);
 
            //
            //  Tell the caller what kind of name we hit
            //
 
            if (FileNameDos) {
 
                *FileNameDos = Node->FileNameDos;
            }
 
            return Node->Fcb;
        }
    }
 
    //
    //  We didn't find the Fcb.
    //
 
    return NULL;
}

Referenced by FatConstructNamesInFcb().

FatInsertName()

VOID FatInsertName	(	IN PIRP_CONTEXT	IrpContext,
		IN PRTL_SPLAY_LINKS *	RootNode,
		IN PFILE_NAME_NODE	Name
	)

Definition at line 39 of file splaysup.c.

{
    COMPARISON Comparison;
    PFILE_NAME_NODE Node;
 
    PAGED_CODE();
 
    RtlInitializeSplayLinks(&Name->Links);
 
Restart:
 
    //
    //  If we are the first entry in the tree, just become the root.
    //
 
    if (*RootNode == NULL) {
 
        *RootNode = &Name->Links;
 
        return;
    }
 
    Node = CONTAINING_RECORD( *RootNode, FILE_NAME_NODE, Links );
 
    while (TRUE) {
 
        //
        //  Compare the prefix in the tree with the prefix we want
        //  to insert.  Note that Oem here doesn't mean anything.
        //
 
        Comparison = CompareNames(&Node->Name.Oem, &Name->Name.Oem);
 
        //
        //  We should never find the name in the table already.
        //
 
        if (Comparison == IsEqual) {
 
            //
            //  Almost. If the removable media was taken to another machine and
            //  back, and we have something like:
            //
            //  Old: abcdef~1  /  abcdefxyz
            //  New: abcdef~1  /  abcdefxyzxyz
            //
            //  but a handle was kept open to abcdefxyz so we couldn't purge
            //  away the Fcb in the verify path ... opening abcdefxyzxyz will
            //  try to insert a duplicate shortname. Bang!
            //
            //  Invalidate it and the horse it came in on.  This new one wins.
            //  The old one is gone.  Only if the old one is in normal state
            //  do we really have a problem.
            //
 
            if (Node->Fcb->FcbState == FcbGood) {
 
#ifdef _MSC_VER
#pragma prefast( suppress:28159, "things are seriously wrong if we get here" )
#endif
                FatBugCheck( (ULONG_PTR)*RootNode, (ULONG_PTR)Name, (ULONG_PTR)Node );
            }
 
            //
            //  Note, once we zap the prefix links we need to restart our walk
            //  of the tree. Note that we aren't properly synchronized to
            //  recursively mark bad.
            //
 
            FatMarkFcbCondition( IrpContext, Node->Fcb, FcbBad, FALSE );
            FatRemoveNames( IrpContext, Node->Fcb );
 
            goto Restart;
        }
 
        //
        //  If the tree prefix is greater than the new prefix then
        //  we go down the left subtree
        //
 
        if (Comparison == IsGreaterThan) {
 
            //
            //  We want to go down the left subtree, first check to see
            //  if we have a left subtree
            //
 
            if (RtlLeftChild(&Node->Links) == NULL) {
 
                //
                //  there isn't a left child so we insert ourselves as the
                //  new left child
                //
 
                RtlInsertAsLeftChild(&Node->Links, &Name->Links);
 
                //
                //  and exit the while loop
                //
 
                break;
 
            } else {
 
                //
                //  there is a left child so simply go down that path, and
                //  go back to the top of the loop
                //
 
                Node = CONTAINING_RECORD( RtlLeftChild(&Node->Links),
                                          FILE_NAME_NODE,
                                          Links );
            }
 
        } else {
 
            //
            //  The tree prefix is either less than or a proper prefix
            //  of the new string.  We treat both cases a less than when
            //  we do insert.  So we want to go down the right subtree,
            //  first check to see if we have a right subtree
            //
 
            if (RtlRightChild(&Node->Links) == NULL) {
 
                //
                //  These isn't a right child so we insert ourselves as the
                //  new right child
                //
 
                RtlInsertAsRightChild(&Node->Links, &Name->Links);
 
                //
                //  and exit the while loop
                //
 
                break;
 
            } else {
 
                //
                //  there is a right child so simply go down that path, and
                //  go back to the top of the loop
                //
 
                Node = CONTAINING_RECORD( RtlRightChild(&Node->Links),
                                          FILE_NAME_NODE,
                                          Links );
            }
 
        }
    }
 
    return;
}

Referenced by FatConstructNamesInFcb().

FatRemoveNames()

VOID FatRemoveNames	(	IN PIRP_CONTEXT	IrpContext,
		IN PFCB	Fcb
	)

Definition at line 222 of file splaysup.c.

{
    PDCB Parent;
    PRTL_SPLAY_LINKS NewRoot;
 
    PAGED_CODE();
    UNREFERENCED_PARAMETER( IrpContext );
 
    Parent = Fcb->ParentDcb;
 
    //
    //  We used to assert this condition, but it really isn't good.  If
    //  someone rapidly renames a directory multiple times and we can't
    //  flush the lower fcbs fast enough (that didn't go away synch.)
    //  well, well hit some of them again.
    //
    //  NT_ASSERT( FlagOn( Fcb->FcbState, FCB_STATE_NAMES_IN_SPLAY_TREE ));
    //
 
    if (FlagOn( Fcb->FcbState, FCB_STATE_NAMES_IN_SPLAY_TREE )) {
 
        //
        //  Delete the node short name.
        //
 
        NewRoot = RtlDelete(&Fcb->ShortName.Links);
 
        Parent->Specific.Dcb.RootOemNode = NewRoot;
 
        //
        //  Now check for the presence of long name and delete it.
        //
 
        if (FlagOn( Fcb->FcbState, FCB_STATE_HAS_OEM_LONG_NAME )) {
 
            NewRoot = RtlDelete(&Fcb->LongName.Oem.Links);
 
            Parent->Specific.Dcb.RootOemNode = NewRoot;
 
            RtlFreeOemString( &Fcb->LongName.Oem.Name.Oem );
 
            ClearFlag( Fcb->FcbState, FCB_STATE_HAS_OEM_LONG_NAME );
        }
 
        if (FlagOn( Fcb->FcbState, FCB_STATE_HAS_UNICODE_LONG_NAME )) {
 
            NewRoot = RtlDelete(&Fcb->LongName.Unicode.Links);
 
            Parent->Specific.Dcb.RootUnicodeNode = NewRoot;
 
            RtlFreeUnicodeString( &Fcb->LongName.Unicode.Name.Unicode );
 
            ClearFlag( Fcb->FcbState, FCB_STATE_HAS_UNICODE_LONG_NAME );
        }
 
        ClearFlag( Fcb->FcbState, FCB_STATE_NAMES_IN_SPLAY_TREE );
    }
 
    return;
}

Referenced by _Requires_lock_held_(), FatDeleteFcb(), FatInsertName(), and FatSetRenameInfo().