[CDFS_NEW] Fix headers inclusion so that it can work on a *nix platform
[reactos.git] / drivers / filesystems / cdfs_new / prefxsup.c
1 /*++
2
3 Copyright (c) 1989-2000 Microsoft Corporation
4
5 Module Name:
6
7 PrefxSup.c
8
9 Abstract:
10
11 This module implements the Cdfs Prefix support routines
12
13
14 --*/
15
16 #include "cdprocs.h"
17
18 //
19 // The Bug check file id for this module
20 //
21
22 #define BugCheckFileId (CDFS_BUG_CHECK_PREFXSUP)
23
24 //
25 // Local support routines.
26 //
27
28 PNAME_LINK
29 CdFindNameLink (
30 IN PIRP_CONTEXT IrpContext,
31 IN PRTL_SPLAY_LINKS *RootNode,
32 IN PUNICODE_STRING Name
33 );
34
35 BOOLEAN
36 CdInsertNameLink (
37 IN PIRP_CONTEXT IrpContext,
38 IN PRTL_SPLAY_LINKS *RootNode,
39 IN PNAME_LINK NameLink
40 );
41
42 #ifdef ALLOC_PRAGMA
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)
48 #endif
49
50 \f
51 VOID
52 CdInsertPrefix (
53 IN PIRP_CONTEXT IrpContext,
54 IN PFCB Fcb,
55 IN PCD_NAME Name,
56 IN BOOLEAN IgnoreCase,
57 IN BOOLEAN ShortNameMatch,
58 IN PFCB ParentFcb
59 )
60
61 /*++
62
63 Routine Description:
64
65 This routine inserts the names in the given Lcb into the links for the
66 parent.
67
68 Arguments:
69
70 Fcb - This is the Fcb whose name is being inserted into the tree.
71
72 Name - This is the name for the component. The IgnoreCase flag tells
73 us which entry this belongs to.
74
75 IgnoreCase - Indicates if we should insert the case-insensitive name.
76
77 ShortNameMatch - Indicates if this is the short name.
78
79 ParentFcb - This is the ParentFcb. The prefix tree is attached to this.
80
81 Return Value:
82
83 None.
84
85 --*/
86
87 {
88 ULONG PrefixFlags;
89 PNAME_LINK NameLink;
90 PPREFIX_ENTRY PrefixEntry;
91 PRTL_SPLAY_LINKS *TreeRoot;
92
93 PWCHAR NameBuffer;
94
95 PAGED_CODE();
96
97 //
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
100 // insert the name.
101 //
102
103 PrefixEntry = &Fcb->FileNamePrefix;
104
105 if (ShortNameMatch) {
106
107 if (Fcb->ShortNamePrefix == NULL) {
108
109 Fcb->ShortNamePrefix = ExAllocatePoolWithTag( CdPagedPool,
110 sizeof( PREFIX_ENTRY ),
111 TAG_PREFIX_ENTRY );
112
113 if (Fcb->ShortNamePrefix == NULL) { return; }
114
115 RtlZeroMemory( Fcb->ShortNamePrefix, sizeof( PREFIX_ENTRY ));
116 }
117
118 PrefixEntry = Fcb->ShortNamePrefix;
119 }
120
121 //
122 // Capture the local variables for the separate cases.
123 //
124
125 if (IgnoreCase) {
126
127 PrefixFlags = PREFIX_FLAG_IGNORE_CASE_IN_TREE;
128 NameLink = &PrefixEntry->IgnoreCaseName;
129 TreeRoot = &ParentFcb->IgnoreCaseRoot;
130
131 } else {
132
133 PrefixFlags = PREFIX_FLAG_EXACT_CASE_IN_TREE;
134 NameLink = &PrefixEntry->ExactCaseName;
135 TreeRoot = &ParentFcb->ExactCaseRoot;
136 }
137
138 //
139 // If neither name is in the tree then check whether we have a buffer for this
140 // name
141 //
142
143 if (!FlagOn( PrefixEntry->PrefixFlags,
144 PREFIX_FLAG_EXACT_CASE_IN_TREE | PREFIX_FLAG_IGNORE_CASE_IN_TREE )) {
145
146 //
147 // Allocate a new buffer if the embedded buffer is too small.
148 //
149
150 NameBuffer = PrefixEntry->FileNameBuffer;
151
152 if (Name->FileName.Length > BYTE_COUNT_EMBEDDED_NAME) {
153
154 NameBuffer = ExAllocatePoolWithTag( CdPagedPool,
155 Name->FileName.Length * 2,
156 TAG_PREFIX_NAME );
157
158 //
159 // Exit if no name buffer.
160 //
161
162 if (NameBuffer == NULL) { return; }
163 }
164
165 //
166 // Split the buffer and fill in the separate components.
167 //
168
169 PrefixEntry->ExactCaseName.FileName.Buffer = NameBuffer;
170 PrefixEntry->IgnoreCaseName.FileName.Buffer = Add2Ptr( NameBuffer,
171 Name->FileName.Length,
172 PWCHAR );
173
174 PrefixEntry->IgnoreCaseName.FileName.MaximumLength =
175 PrefixEntry->IgnoreCaseName.FileName.Length =
176 PrefixEntry->ExactCaseName.FileName.MaximumLength =
177 PrefixEntry->ExactCaseName.FileName.Length = Name->FileName.Length;
178 }
179
180 //
181 // Only insert the name if not already present.
182 //
183
184 if (!FlagOn( PrefixEntry->PrefixFlags, PrefixFlags )) {
185
186 //
187 // Initialize the name in the prefix entry.
188 //
189
190 RtlCopyMemory( NameLink->FileName.Buffer,
191 Name->FileName.Buffer,
192 Name->FileName.Length );
193
194 CdInsertNameLink( IrpContext,
195 TreeRoot,
196 NameLink );
197
198 PrefixEntry->Fcb = Fcb;
199 SetFlag( PrefixEntry->PrefixFlags, PrefixFlags );
200 }
201
202 return;
203 }
204
205 \f
206 VOID
207 CdRemovePrefix (
208 IN PIRP_CONTEXT IrpContext,
209 IN PFCB Fcb
210 )
211
212 /*++
213
214 Routine Description:
215
216 This routine is called to remove all of the previx entries of a
217 given Fcb from its parent Fcb.
218
219 Arguments:
220
221 Fcb - Fcb whose entries are to be removed.
222
223 Return Value:
224
225 None
226
227 --*/
228
229 {
230 PAGED_CODE();
231
232 //
233 // Start with the short name prefix entry.
234 //
235
236 if (Fcb->ShortNamePrefix != NULL) {
237
238 if (FlagOn( Fcb->ShortNamePrefix->PrefixFlags, PREFIX_FLAG_IGNORE_CASE_IN_TREE )) {
239
240 Fcb->ParentFcb->IgnoreCaseRoot = RtlDelete( &Fcb->ShortNamePrefix->IgnoreCaseName.Links );
241 }
242
243 if (FlagOn( Fcb->ShortNamePrefix->PrefixFlags, PREFIX_FLAG_EXACT_CASE_IN_TREE )) {
244
245 Fcb->ParentFcb->ExactCaseRoot = RtlDelete( &Fcb->ShortNamePrefix->ExactCaseName.Links );
246 }
247
248 ClearFlag( Fcb->ShortNamePrefix->PrefixFlags,
249 PREFIX_FLAG_IGNORE_CASE_IN_TREE | PREFIX_FLAG_EXACT_CASE_IN_TREE );
250 }
251
252 //
253 // Now do the long name prefix entries.
254 //
255
256 if (FlagOn( Fcb->FileNamePrefix.PrefixFlags, PREFIX_FLAG_IGNORE_CASE_IN_TREE )) {
257
258 Fcb->ParentFcb->IgnoreCaseRoot = RtlDelete( &Fcb->FileNamePrefix.IgnoreCaseName.Links );
259 }
260
261 if (FlagOn( Fcb->FileNamePrefix.PrefixFlags, PREFIX_FLAG_EXACT_CASE_IN_TREE )) {
262
263 Fcb->ParentFcb->ExactCaseRoot = RtlDelete( &Fcb->FileNamePrefix.ExactCaseName.Links );
264 }
265
266 ClearFlag( Fcb->FileNamePrefix.PrefixFlags,
267 PREFIX_FLAG_IGNORE_CASE_IN_TREE | PREFIX_FLAG_EXACT_CASE_IN_TREE );
268
269 //
270 // Deallocate any buffer we may have allocated.
271 //
272
273 if ((Fcb->FileNamePrefix.ExactCaseName.FileName.Buffer != (PWCHAR) &Fcb->FileNamePrefix.FileNameBuffer) &&
274 (Fcb->FileNamePrefix.ExactCaseName.FileName.Buffer != NULL)) {
275
276 CdFreePool( &Fcb->FileNamePrefix.ExactCaseName.FileName.Buffer );
277 Fcb->FileNamePrefix.ExactCaseName.FileName.Buffer = NULL;
278 }
279
280 return;
281 }
282
283 \f
284 VOID
285 CdFindPrefix (
286 IN PIRP_CONTEXT IrpContext,
287 IN OUT PFCB *CurrentFcb,
288 IN OUT PUNICODE_STRING RemainingName,
289 IN BOOLEAN IgnoreCase
290 )
291
292 /*++
293
294 Routine Description:
295
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
302 hold that resource.
303
304 Arguments:
305
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
308 Fcb to examine.
309
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
312 IgnoreCase flag.
313
314 IgnoreCase - Indicates if we are doing a case-insensitive compare.
315
316 Return Value:
317
318 None
319
320 --*/
321
322 {
323 UNICODE_STRING LocalRemainingName;
324
325 UNICODE_STRING FinalName;
326
327 PNAME_LINK NameLink;
328 PPREFIX_ENTRY PrefixEntry;
329
330 PAGED_CODE();
331
332 //
333 // Make a local copy of the input strings.
334 //
335
336 LocalRemainingName = *RemainingName;
337
338 //
339 // Loop until we find the longest matching prefix.
340 //
341
342 while (TRUE) {
343
344 //
345 // If there are no characters left or we are not at an IndexFcb then
346 // return immediately.
347 //
348
349 if ((LocalRemainingName.Length == 0) ||
350 (SafeNodeType( *CurrentFcb ) != CDFS_NTC_FCB_INDEX)) {
351
352 return;
353 }
354
355 //
356 // Split off the next component from the name.
357 //
358
359 CdDissectName( IrpContext,
360 &LocalRemainingName,
361 &FinalName );
362
363 //
364 // Check if this name is in the splay tree for this Scb.
365 //
366
367 if (IgnoreCase) {
368
369 NameLink = CdFindNameLink( IrpContext,
370 &(*CurrentFcb)->IgnoreCaseRoot,
371 &FinalName );
372
373 //
374 // Get the prefix entry from this NameLink. Don't access any
375 // fields within it until we verify we have a name link.
376 //
377
378 PrefixEntry = (PPREFIX_ENTRY) CONTAINING_RECORD( NameLink,
379 PREFIX_ENTRY,
380 IgnoreCaseName );
381
382 } else {
383
384 NameLink = CdFindNameLink( IrpContext,
385 &(*CurrentFcb)->ExactCaseRoot,
386 &FinalName );
387
388 PrefixEntry = (PPREFIX_ENTRY) CONTAINING_RECORD( NameLink,
389 PREFIX_ENTRY,
390 ExactCaseName );
391 }
392
393 //
394 // If we didn't find a match then exit.
395 //
396
397 if (NameLink == NULL) { return; }
398
399 //
400 // If this is a case-insensitive match then copy the exact case of the name into
401 // the input buffer.
402 //
403
404 if (IgnoreCase) {
405
406 RtlCopyMemory( FinalName.Buffer,
407 PrefixEntry->ExactCaseName.FileName.Buffer,
408 PrefixEntry->ExactCaseName.FileName.Length );
409 }
410
411 //
412 // Update the caller's remaining name string to reflect the fact that we found
413 // a match.
414 //
415
416 *RemainingName = LocalRemainingName;
417
418 //
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.
422 //
423
424 if (!CdAcquireFcbExclusive( IrpContext, PrefixEntry->Fcb, TRUE )) {
425
426 //
427 // If we can't wait then raise CANT_WAIT.
428 //
429
430 if (!FlagOn( IrpContext->Flags, IRP_CONTEXT_FLAG_WAIT )) {
431
432 CdRaiseStatus( IrpContext, STATUS_CANT_WAIT );
433 }
434
435 CdLockVcb( IrpContext, IrpContext->Vcb );
436 PrefixEntry->Fcb->FcbReference += 1;
437 CdUnlockVcb( IrpContext, IrpContext->Vcb );
438
439 CdReleaseFcb( IrpContext, *CurrentFcb );
440 CdAcquireFcbExclusive( IrpContext, PrefixEntry->Fcb, FALSE );
441
442 CdLockVcb( IrpContext, IrpContext->Vcb );
443 PrefixEntry->Fcb->FcbReference -= 1;
444 CdUnlockVcb( IrpContext, IrpContext->Vcb );
445
446 } else {
447
448 CdReleaseFcb( IrpContext, *CurrentFcb );
449 }
450
451 *CurrentFcb = PrefixEntry->Fcb;
452 }
453 }
454
455 \f
456 //
457 // Local support routine
458 //
459
460 PNAME_LINK
461 CdFindNameLink (
462 IN PIRP_CONTEXT IrpContext,
463 IN PRTL_SPLAY_LINKS *RootNode,
464 IN PUNICODE_STRING Name
465 )
466
467 /*++
468
469 Routine Description:
470
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
473 tree.
474
475 Arguments:
476
477 RootNode - Supplies the parent to search.
478
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.
481
482 Return Value:
483
484 PNAME_LINK - The name link found or NULL if there is no match.
485
486 --*/
487
488 {
489 FSRTL_COMPARISON_RESULT Comparison;
490 PNAME_LINK Node;
491 PRTL_SPLAY_LINKS Links;
492
493 PAGED_CODE();
494
495 Links = *RootNode;
496
497 while (Links != NULL) {
498
499 Node = CONTAINING_RECORD( Links, NAME_LINK, Links );
500
501 //
502 // Compare the prefix in the tree with the full name
503 //
504
505 Comparison = CdFullCompareNames( IrpContext, &Node->FileName, Name );
506
507 //
508 // See if they don't match
509 //
510
511 if (Comparison == GreaterThan) {
512
513 //
514 // The prefix is greater than the full name
515 // so we go down the left child
516 //
517
518 Links = RtlLeftChild( Links );
519
520 //
521 // And continue searching down this tree
522 //
523
524 } else if (Comparison == LessThan) {
525
526 //
527 // The prefix is less than the full name
528 // so we go down the right child
529 //
530
531 Links = RtlRightChild( Links );
532
533 //
534 // And continue searching down this tree
535 //
536
537 } else {
538
539 //
540 // We found it.
541 //
542 // Splay the tree and save the new root.
543 //
544
545 *RootNode = RtlSplay( Links );
546
547 return Node;
548 }
549 }
550
551 //
552 // We didn't find the Link.
553 //
554
555 return NULL;
556 }
557
558 \f
559 //
560 // Local support routine
561 //
562
563 BOOLEAN
564 CdInsertNameLink (
565 IN PIRP_CONTEXT IrpContext,
566 IN PRTL_SPLAY_LINKS *RootNode,
567 IN PNAME_LINK NameLink
568 )
569
570 /*++
571
572 Routine Description:
573
574 This routine will insert a name in the splay tree pointed to
575 by RootNode.
576
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.
579
580 Arguments:
581
582 RootNode - Supplies a pointer to the table.
583
584 NameLink - Contains the new link to enter.
585
586 Return Value:
587
588 BOOLEAN - TRUE if the name is inserted, FALSE otherwise.
589
590 --*/
591
592 {
593 FSRTL_COMPARISON_RESULT Comparison;
594 PNAME_LINK Node;
595
596 PAGED_CODE();
597
598 RtlInitializeSplayLinks( &NameLink->Links );
599
600 //
601 // If we are the first entry in the tree, just become the root.
602 //
603
604 if (*RootNode == NULL) {
605
606 *RootNode = &NameLink->Links;
607
608 return TRUE;
609 }
610
611 Node = CONTAINING_RECORD( *RootNode, NAME_LINK, Links );
612
613 while (TRUE) {
614
615 //
616 // Compare the prefix in the tree with the prefix we want
617 // to insert.
618 //
619
620 Comparison = CdFullCompareNames( IrpContext, &Node->FileName, &NameLink->FileName );
621
622 //
623 // If we found the entry, return immediately.
624 //
625
626 if (Comparison == EqualTo) { return FALSE; }
627
628 //
629 // If the tree prefix is greater than the new prefix then
630 // we go down the left subtree
631 //
632
633 if (Comparison == GreaterThan) {
634
635 //
636 // We want to go down the left subtree, first check to see
637 // if we have a left subtree
638 //
639
640 if (RtlLeftChild( &Node->Links ) == NULL) {
641
642 //
643 // there isn't a left child so we insert ourselves as the
644 // new left child
645 //
646
647 RtlInsertAsLeftChild( &Node->Links, &NameLink->Links );
648
649 //
650 // and exit the while loop
651 //
652
653 break;
654
655 } else {
656
657 //
658 // there is a left child so simply go down that path, and
659 // go back to the top of the loop
660 //
661
662 Node = CONTAINING_RECORD( RtlLeftChild( &Node->Links ),
663 NAME_LINK,
664 Links );
665 }
666
667 } else {
668
669 //
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
674 //
675
676 if (RtlRightChild( &Node->Links ) == NULL) {
677
678 //
679 // These isn't a right child so we insert ourselves as the
680 // new right child
681 //
682
683 RtlInsertAsRightChild( &Node->Links, &NameLink->Links );
684
685 //
686 // and exit the while loop
687 //
688
689 break;
690
691 } else {
692
693 //
694 // there is a right child so simply go down that path, and
695 // go back to the top of the loop
696 //
697
698 Node = CONTAINING_RECORD( RtlRightChild( &Node->Links ),
699 NAME_LINK,
700 Links );
701 }
702 }
703 }
704
705 return TRUE;
706 }
707
708
709
710
711