3 Copyright (c) 1989-2000 Microsoft Corporation
11 This module implements the Cdfs Prefix support routines
19 // The Bug check file id for this module
22 #define BugCheckFileId (CDFS_BUG_CHECK_PREFXSUP)
25 // Local support routines.
30 IN PIRP_CONTEXT IrpContext
,
31 IN PRTL_SPLAY_LINKS
*RootNode
,
32 IN PUNICODE_STRING Name
37 IN PIRP_CONTEXT IrpContext
,
38 IN PRTL_SPLAY_LINKS
*RootNode
,
39 IN PNAME_LINK NameLink
43 #pragma alloc_text(PAGE, CdFindNameLink)
44 #pragma alloc_text(PAGE, CdFindPrefix)
45 #pragma alloc_text(PAGE, CdInsertNameLink)
46 #pragma alloc_text(PAGE, CdInsertPrefix)
47 #pragma alloc_text(PAGE, CdRemovePrefix)
53 IN PIRP_CONTEXT IrpContext
,
56 IN BOOLEAN IgnoreCase
,
57 IN BOOLEAN ShortNameMatch
,
65 This routine inserts the names in the given Lcb into the links for the
70 Fcb - This is the Fcb whose name is being inserted into the tree.
72 Name - This is the name for the component. The IgnoreCase flag tells
73 us which entry this belongs to.
75 IgnoreCase - Indicates if we should insert the case-insensitive name.
77 ShortNameMatch - Indicates if this is the short name.
79 ParentFcb - This is the ParentFcb. The prefix tree is attached to this.
90 PPREFIX_ENTRY PrefixEntry
;
91 PRTL_SPLAY_LINKS
*TreeRoot
;
98 // Check if we need to allocate a prefix entry for the short name.
99 // If we can't allocate one then fail quietly. We don't have to
103 PrefixEntry
= &Fcb
->FileNamePrefix
;
105 if (ShortNameMatch
) {
107 if (Fcb
->ShortNamePrefix
== NULL
) {
109 Fcb
->ShortNamePrefix
= ExAllocatePoolWithTag( CdPagedPool
,
110 sizeof( PREFIX_ENTRY
),
113 if (Fcb
->ShortNamePrefix
== NULL
) { return; }
115 RtlZeroMemory( Fcb
->ShortNamePrefix
, sizeof( PREFIX_ENTRY
));
118 PrefixEntry
= Fcb
->ShortNamePrefix
;
122 // Capture the local variables for the separate cases.
127 PrefixFlags
= PREFIX_FLAG_IGNORE_CASE_IN_TREE
;
128 NameLink
= &PrefixEntry
->IgnoreCaseName
;
129 TreeRoot
= &ParentFcb
->IgnoreCaseRoot
;
133 PrefixFlags
= PREFIX_FLAG_EXACT_CASE_IN_TREE
;
134 NameLink
= &PrefixEntry
->ExactCaseName
;
135 TreeRoot
= &ParentFcb
->ExactCaseRoot
;
139 // If neither name is in the tree then check whether we have a buffer for this
143 if (!FlagOn( PrefixEntry
->PrefixFlags
,
144 PREFIX_FLAG_EXACT_CASE_IN_TREE
| PREFIX_FLAG_IGNORE_CASE_IN_TREE
)) {
147 // Allocate a new buffer if the embedded buffer is too small.
150 NameBuffer
= PrefixEntry
->FileNameBuffer
;
152 if (Name
->FileName
.Length
> BYTE_COUNT_EMBEDDED_NAME
) {
154 NameBuffer
= ExAllocatePoolWithTag( CdPagedPool
,
155 Name
->FileName
.Length
* 2,
159 // Exit if no name buffer.
162 if (NameBuffer
== NULL
) { return; }
166 // Split the buffer and fill in the separate components.
169 PrefixEntry
->ExactCaseName
.FileName
.Buffer
= NameBuffer
;
170 PrefixEntry
->IgnoreCaseName
.FileName
.Buffer
= Add2Ptr( NameBuffer
,
171 Name
->FileName
.Length
,
174 PrefixEntry
->IgnoreCaseName
.FileName
.MaximumLength
=
175 PrefixEntry
->IgnoreCaseName
.FileName
.Length
=
176 PrefixEntry
->ExactCaseName
.FileName
.MaximumLength
=
177 PrefixEntry
->ExactCaseName
.FileName
.Length
= Name
->FileName
.Length
;
181 // Only insert the name if not already present.
184 if (!FlagOn( PrefixEntry
->PrefixFlags
, PrefixFlags
)) {
187 // Initialize the name in the prefix entry.
190 RtlCopyMemory( NameLink
->FileName
.Buffer
,
191 Name
->FileName
.Buffer
,
192 Name
->FileName
.Length
);
194 CdInsertNameLink( IrpContext
,
198 PrefixEntry
->Fcb
= Fcb
;
199 SetFlag( PrefixEntry
->PrefixFlags
, PrefixFlags
);
208 IN PIRP_CONTEXT IrpContext
,
216 This routine is called to remove all of the previx entries of a
217 given Fcb from its parent Fcb.
221 Fcb - Fcb whose entries are to be removed.
233 // Start with the short name prefix entry.
236 if (Fcb
->ShortNamePrefix
!= NULL
) {
238 if (FlagOn( Fcb
->ShortNamePrefix
->PrefixFlags
, PREFIX_FLAG_IGNORE_CASE_IN_TREE
)) {
240 Fcb
->ParentFcb
->IgnoreCaseRoot
= RtlDelete( &Fcb
->ShortNamePrefix
->IgnoreCaseName
.Links
);
243 if (FlagOn( Fcb
->ShortNamePrefix
->PrefixFlags
, PREFIX_FLAG_EXACT_CASE_IN_TREE
)) {
245 Fcb
->ParentFcb
->ExactCaseRoot
= RtlDelete( &Fcb
->ShortNamePrefix
->ExactCaseName
.Links
);
248 ClearFlag( Fcb
->ShortNamePrefix
->PrefixFlags
,
249 PREFIX_FLAG_IGNORE_CASE_IN_TREE
| PREFIX_FLAG_EXACT_CASE_IN_TREE
);
253 // Now do the long name prefix entries.
256 if (FlagOn( Fcb
->FileNamePrefix
.PrefixFlags
, PREFIX_FLAG_IGNORE_CASE_IN_TREE
)) {
258 Fcb
->ParentFcb
->IgnoreCaseRoot
= RtlDelete( &Fcb
->FileNamePrefix
.IgnoreCaseName
.Links
);
261 if (FlagOn( Fcb
->FileNamePrefix
.PrefixFlags
, PREFIX_FLAG_EXACT_CASE_IN_TREE
)) {
263 Fcb
->ParentFcb
->ExactCaseRoot
= RtlDelete( &Fcb
->FileNamePrefix
.ExactCaseName
.Links
);
266 ClearFlag( Fcb
->FileNamePrefix
.PrefixFlags
,
267 PREFIX_FLAG_IGNORE_CASE_IN_TREE
| PREFIX_FLAG_EXACT_CASE_IN_TREE
);
270 // Deallocate any buffer we may have allocated.
273 if ((Fcb
->FileNamePrefix
.ExactCaseName
.FileName
.Buffer
!= (PWCHAR
) &Fcb
->FileNamePrefix
.FileNameBuffer
) &&
274 (Fcb
->FileNamePrefix
.ExactCaseName
.FileName
.Buffer
!= NULL
)) {
276 CdFreePool( &Fcb
->FileNamePrefix
.ExactCaseName
.FileName
.Buffer
);
277 Fcb
->FileNamePrefix
.ExactCaseName
.FileName
.Buffer
= NULL
;
286 IN PIRP_CONTEXT IrpContext
,
287 IN OUT PFCB
*CurrentFcb
,
288 IN OUT PUNICODE_STRING RemainingName
,
289 IN BOOLEAN IgnoreCase
296 This routine begins from the given CurrentFcb and walks through all of
297 components of the name looking for the longest match in the prefix
298 splay trees. The search is relative to the starting Fcb so the
299 full name may not begin with a '\'. On return this routine will
300 update Current Fcb with the lowest point it has travelled in the
301 tree. It will also hold only that resource on return and it must
306 CurrentFcb - Address to store the lowest Fcb we find on this search.
307 On return we will have acquired this Fcb. On entry this is the
310 RemainingName - Supplies a buffer to store the exact case of the name being
311 searched for. Initially will contain the upcase name based on the
314 IgnoreCase - Indicates if we are doing a case-insensitive compare.
323 UNICODE_STRING LocalRemainingName
;
325 UNICODE_STRING FinalName
;
328 PPREFIX_ENTRY PrefixEntry
;
333 // Make a local copy of the input strings.
336 LocalRemainingName
= *RemainingName
;
339 // Loop until we find the longest matching prefix.
345 // If there are no characters left or we are not at an IndexFcb then
346 // return immediately.
349 if ((LocalRemainingName
.Length
== 0) ||
350 (SafeNodeType( *CurrentFcb
) != CDFS_NTC_FCB_INDEX
)) {
356 // Split off the next component from the name.
359 CdDissectName( IrpContext
,
364 // Check if this name is in the splay tree for this Scb.
369 NameLink
= CdFindNameLink( IrpContext
,
370 &(*CurrentFcb
)->IgnoreCaseRoot
,
374 // Get the prefix entry from this NameLink. Don't access any
375 // fields within it until we verify we have a name link.
378 PrefixEntry
= (PPREFIX_ENTRY
) CONTAINING_RECORD( NameLink
,
384 NameLink
= CdFindNameLink( IrpContext
,
385 &(*CurrentFcb
)->ExactCaseRoot
,
388 PrefixEntry
= (PPREFIX_ENTRY
) CONTAINING_RECORD( NameLink
,
394 // If we didn't find a match then exit.
397 if (NameLink
== NULL
) { return; }
400 // If this is a case-insensitive match then copy the exact case of the name into
406 RtlCopyMemory( FinalName
.Buffer
,
407 PrefixEntry
->ExactCaseName
.FileName
.Buffer
,
408 PrefixEntry
->ExactCaseName
.FileName
.Length
);
412 // Update the caller's remaining name string to reflect the fact that we found
416 *RemainingName
= LocalRemainingName
;
419 // Move down to the next component in the tree. Acquire without waiting.
420 // If this fails then lock the Fcb to reference this Fcb and then drop
421 // the parent and acquire the child.
424 if (!CdAcquireFcbExclusive( IrpContext
, PrefixEntry
->Fcb
, TRUE
)) {
427 // If we can't wait then raise CANT_WAIT.
430 if (!FlagOn( IrpContext
->Flags
, IRP_CONTEXT_FLAG_WAIT
)) {
432 CdRaiseStatus( IrpContext
, STATUS_CANT_WAIT
);
435 CdLockVcb( IrpContext
, IrpContext
->Vcb
);
436 PrefixEntry
->Fcb
->FcbReference
+= 1;
437 CdUnlockVcb( IrpContext
, IrpContext
->Vcb
);
439 CdReleaseFcb( IrpContext
, *CurrentFcb
);
440 CdAcquireFcbExclusive( IrpContext
, PrefixEntry
->Fcb
, FALSE
);
442 CdLockVcb( IrpContext
, IrpContext
->Vcb
);
443 PrefixEntry
->Fcb
->FcbReference
-= 1;
444 CdUnlockVcb( IrpContext
, IrpContext
->Vcb
);
448 CdReleaseFcb( IrpContext
, *CurrentFcb
);
451 *CurrentFcb
= PrefixEntry
->Fcb
;
457 // Local support routine
462 IN PIRP_CONTEXT IrpContext
,
463 IN PRTL_SPLAY_LINKS
*RootNode
,
464 IN PUNICODE_STRING Name
471 This routine searches through a splay link tree looking for a match for the
472 input name. If we find the corresponding name we will rebalance the
477 RootNode - Supplies the parent to search.
479 Name - This is the name to search for. Note if we are doing a case
480 insensitive search the name would have been upcased already.
484 PNAME_LINK - The name link found or NULL if there is no match.
489 FSRTL_COMPARISON_RESULT Comparison
;
491 PRTL_SPLAY_LINKS Links
;
497 while (Links
!= NULL
) {
499 Node
= CONTAINING_RECORD( Links
, NAME_LINK
, Links
);
502 // Compare the prefix in the tree with the full name
505 Comparison
= CdFullCompareNames( IrpContext
, &Node
->FileName
, Name
);
508 // See if they don't match
511 if (Comparison
== GreaterThan
) {
514 // The prefix is greater than the full name
515 // so we go down the left child
518 Links
= RtlLeftChild( Links
);
521 // And continue searching down this tree
524 } else if (Comparison
== LessThan
) {
527 // The prefix is less than the full name
528 // so we go down the right child
531 Links
= RtlRightChild( Links
);
534 // And continue searching down this tree
542 // Splay the tree and save the new root.
545 *RootNode
= RtlSplay( Links
);
552 // We didn't find the Link.
560 // Local support routine
565 IN PIRP_CONTEXT IrpContext
,
566 IN PRTL_SPLAY_LINKS
*RootNode
,
567 IN PNAME_LINK NameLink
574 This routine will insert a name in the splay tree pointed to
577 The name could already exist in this tree for a case-insensitive tree.
578 In that case we simply return FALSE and do nothing.
582 RootNode - Supplies a pointer to the table.
584 NameLink - Contains the new link to enter.
588 BOOLEAN - TRUE if the name is inserted, FALSE otherwise.
593 FSRTL_COMPARISON_RESULT Comparison
;
598 RtlInitializeSplayLinks( &NameLink
->Links
);
601 // If we are the first entry in the tree, just become the root.
604 if (*RootNode
== NULL
) {
606 *RootNode
= &NameLink
->Links
;
611 Node
= CONTAINING_RECORD( *RootNode
, NAME_LINK
, Links
);
616 // Compare the prefix in the tree with the prefix we want
620 Comparison
= CdFullCompareNames( IrpContext
, &Node
->FileName
, &NameLink
->FileName
);
623 // If we found the entry, return immediately.
626 if (Comparison
== EqualTo
) { return FALSE
; }
629 // If the tree prefix is greater than the new prefix then
630 // we go down the left subtree
633 if (Comparison
== GreaterThan
) {
636 // We want to go down the left subtree, first check to see
637 // if we have a left subtree
640 if (RtlLeftChild( &Node
->Links
) == NULL
) {
643 // there isn't a left child so we insert ourselves as the
647 RtlInsertAsLeftChild( &Node
->Links
, &NameLink
->Links
);
650 // and exit the while loop
658 // there is a left child so simply go down that path, and
659 // go back to the top of the loop
662 Node
= CONTAINING_RECORD( RtlLeftChild( &Node
->Links
),
670 // The tree prefix is either less than or a proper prefix
671 // of the new string. We treat both cases as less than when
672 // we do insert. So we want to go down the right subtree,
673 // first check to see if we have a right subtree
676 if (RtlRightChild( &Node
->Links
) == NULL
) {
679 // These isn't a right child so we insert ourselves as the
683 RtlInsertAsRightChild( &Node
->Links
, &NameLink
->Links
);
686 // and exit the while loop
694 // there is a right child so simply go down that path, and
695 // go back to the top of the loop
698 Node
= CONTAINING_RECORD( RtlRightChild( &Node
->Links
),