Windows: Directory Entry Processing
[openafs.git] / src / WINNT / afsrdr / kernel / lib / AFSBTreeSupport.cpp
1 /*
2  * Copyright (c) 2008, 2009, 2010, 2011 Kernel Drivers, LLC.
3  * Copyright (c) 2009, 2010, 2011 Your File System, Inc.
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * - Redistributions of source code must retain the above copyright notice,
11  *   this list of conditions and the following disclaimer.
12  * - Redistributions in binary form must reproduce the above copyright
13  *   notice,
14  *   this list of conditions and the following disclaimer in the
15  *   documentation
16  *   and/or other materials provided with the distribution.
17  * - Neither the names of Kernel Drivers, LLC and Your File System, Inc.
18  *   nor the names of their contributors may be used to endorse or promote
19  *   products derived from this software without specific prior written
20  *   permission from Kernel Drivers, LLC and Your File System, Inc.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
23  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
24  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
25  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
26  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
27  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
28  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
29  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
30  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
31  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
32  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33  */
34
35 //
36 // File: AFSBTreeSupport.cpp
37 //
38
39 #include "AFSCommon.h"
40
41 NTSTATUS
42 AFSLocateCaseSensitiveDirEntry( IN AFSDirectoryCB *RootNode,
43                                 IN ULONG Index,
44                                 IN OUT AFSDirectoryCB **DirEntry)
45 {
46
47     NTSTATUS    ntStatus = STATUS_SUCCESS;
48     AFSDirectoryCB   *pEntry = NULL;
49     AFSDirectoryCB   *pCurrentEntry = NULL;
50
51     pCurrentEntry = RootNode;
52
53     __Enter
54     {
55
56         *DirEntry = NULL;
57
58         //
59         // If the rootnode passed is null then the directory is empty
60         //
61
62         if( RootNode == NULL)
63         {
64
65             try_return( ntStatus = STATUS_INVALID_PARAMETER);
66         }
67
68         //
69         // If the requestor is looking for the root node itself, then return it.
70         //
71
72         if( RootNode->CaseSensitiveTreeEntry.HashIndex == Index)
73         {
74
75             *DirEntry = RootNode;
76
77             try_return( ntStatus);
78         }
79
80         //
81         // Loop through the nodes in the tree
82         //
83
84         while( pCurrentEntry != NULL)
85         {
86
87             //
88             // Greater values are to the right link.
89             //
90
91             if( Index > pCurrentEntry->CaseSensitiveTreeEntry.HashIndex)
92             {
93
94                 //
95                 // Go to the next RIGHT entry, if there is one
96                 //
97
98                 if( pCurrentEntry->CaseSensitiveTreeEntry.rightLink != NULL)
99                 {
100
101                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseSensitiveTreeEntry.rightLink;
102                 }
103                 else
104                 {
105
106                     //
107                     // Came to the end of the branch so bail
108                     //
109
110                     pCurrentEntry = NULL;
111
112                     break;
113                 }
114             }
115             else if( Index < pCurrentEntry->CaseSensitiveTreeEntry.HashIndex)
116             {
117
118                 //
119                 // Go to the next LEFT entry, if one exists
120                 //
121
122                 if( pCurrentEntry->CaseSensitiveTreeEntry.leftLink != NULL)
123                 {
124
125                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseSensitiveTreeEntry.leftLink;
126                 }
127                 else
128                 {
129
130                     //
131                     // End of the branch ...
132                     //
133
134                     pCurrentEntry = NULL;
135
136                     break;
137                 }
138             }
139             else
140             {
141
142                 //
143                 // Found the entry.
144                 //
145
146                 *DirEntry = pCurrentEntry;
147
148                 break;
149             }
150         }
151
152 try_exit:
153
154         NOTHING;
155     }
156
157     return ntStatus;
158 }
159
160 NTSTATUS
161 AFSLocateCaseInsensitiveDirEntry( IN AFSDirectoryCB *RootNode,
162                                   IN ULONG Index,
163                                   IN OUT AFSDirectoryCB **DirEntry)
164 {
165
166     NTSTATUS    ntStatus = STATUS_SUCCESS;
167     AFSDirectoryCB   *pEntry = NULL;
168     AFSDirectoryCB   *pCurrentEntry = NULL;
169
170     pCurrentEntry = RootNode;
171
172     __Enter
173     {
174
175         *DirEntry = NULL;
176
177         //
178         // If the rootnode passed is null then the directory is empty
179         //
180
181         if( RootNode == NULL)
182         {
183
184             try_return( ntStatus = STATUS_INVALID_PARAMETER);
185         }
186
187         //
188         // If the requestor is looking for the root node itself, then return it.
189         //
190
191         if( RootNode->CaseInsensitiveTreeEntry.HashIndex == Index)
192         {
193
194             *DirEntry = RootNode;
195
196             try_return( ntStatus);
197         }
198
199         //
200         // Loop through the nodes in the tree
201         //
202
203         while( pCurrentEntry != NULL)
204         {
205
206             //
207             // Greater values are to the right link.
208             //
209
210             if( Index > pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
211             {
212
213                 //
214                 // Go to the next RIGHT entry, if there is one
215                 //
216
217                 if( pCurrentEntry->CaseInsensitiveTreeEntry.rightLink != NULL)
218                 {
219
220                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.rightLink;
221                 }
222                 else
223                 {
224
225                     //
226                     // Came to the end of the branch so bail
227                     //
228
229                     pCurrentEntry = NULL;
230
231                     break;
232                 }
233             }
234             else if( Index < pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
235             {
236
237                 //
238                 // Go to the next LEFT entry, if one exists
239                 //
240
241                 if( pCurrentEntry->CaseInsensitiveTreeEntry.leftLink != NULL)
242                 {
243
244                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.leftLink;
245                 }
246                 else
247                 {
248
249                     //
250                     // End of the branch ...
251                     //
252
253                     pCurrentEntry = NULL;
254
255                     break;
256                 }
257             }
258             else
259             {
260
261                 //
262                 // Found the entry.
263                 //
264
265                 *DirEntry = pCurrentEntry;
266
267                 break;
268             }
269         }
270
271 try_exit:
272
273         NOTHING;
274     }
275
276     return ntStatus;
277 }
278
279 NTSTATUS
280 AFSInsertCaseSensitiveDirEntry( IN AFSDirectoryCB *RootNode,
281                                 IN AFSDirectoryCB *DirEntry)
282 {
283
284     NTSTATUS ntStatus = STATUS_SUCCESS;
285     AFSDirectoryCB *pCurrentEntry = NULL;
286
287     pCurrentEntry = RootNode;
288
289     __Enter
290     {
291
292         //
293         // If we have no root node then we can;t start the search.
294         //
295
296         if( pCurrentEntry == NULL)
297         {
298
299             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
300                           AFS_TRACE_LEVEL_WARNING,
301                           "AFSInsertCaseSensitiveDirEntry Invalid root node\n");
302
303             try_return( ntStatus = STATUS_UNSUCCESSFUL);
304         }
305
306         //
307         // Locate the branch end to insert the node
308         //
309
310         while( pCurrentEntry != NULL)
311         {
312
313             //
314             // Greater vlued indices are to the right link
315             //
316
317             if( DirEntry->CaseSensitiveTreeEntry.HashIndex > pCurrentEntry->CaseSensitiveTreeEntry.HashIndex)
318             {
319
320                 //
321                 // Go to the next RIGHT entry, if it exists
322                 //
323
324                 if( pCurrentEntry->CaseSensitiveTreeEntry.rightLink != NULL)
325                 {
326                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseSensitiveTreeEntry.rightLink;
327                 }
328                 else
329                 {
330
331                     //
332                     // Located the end of the branch line so insert the node
333                     //
334
335                     pCurrentEntry->CaseSensitiveTreeEntry.rightLink = (void *)DirEntry;
336
337                     DirEntry->CaseSensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
338
339                     break;
340                 }
341             }
342             else if( DirEntry->CaseSensitiveTreeEntry.HashIndex < pCurrentEntry->CaseSensitiveTreeEntry.HashIndex)
343             {
344
345                 //
346                 // Go to the next LEFT entry, if it exists
347                 //
348
349                 if( pCurrentEntry->CaseSensitiveTreeEntry.leftLink != NULL)
350                 {
351                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseSensitiveTreeEntry.leftLink;
352                 }
353                 else
354                 {
355
356                     //
357                     // Located the branch line end so insert the node here
358                     //
359
360                     pCurrentEntry->CaseSensitiveTreeEntry.leftLink = (void *)DirEntry;
361
362                     DirEntry->CaseSensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
363
364                     break;
365                 }
366             }
367             else
368             {
369
370                 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
371                               AFS_TRACE_LEVEL_VERBOSE,
372                               "AFSInsertCaseSensitiveDirEntry Collision with DE %p for %wZ\n",
373                               pCurrentEntry,
374                               &pCurrentEntry->NameInformation.FileName);
375
376                 ntStatus = STATUS_UNSUCCESSFUL;
377
378                 break;
379             }
380         }
381
382 try_exit:
383
384         NOTHING;
385     }
386
387     return ntStatus;
388 }
389
390 NTSTATUS
391 AFSInsertCaseInsensitiveDirEntry( IN AFSDirectoryCB *RootNode,
392                                   IN AFSDirectoryCB *DirEntry)
393 {
394
395     NTSTATUS ntStatus = STATUS_SUCCESS;
396     AFSDirectoryCB *pCurrentEntry = NULL;
397
398     pCurrentEntry = RootNode;
399
400     __Enter
401     {
402
403         //
404         // If we have no root node then we can;t start the search.
405         //
406
407         if( pCurrentEntry == NULL)
408         {
409
410             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
411                           AFS_TRACE_LEVEL_WARNING,
412                           "AFSInsertCaseInsensitiveDirEntry Invalid root node\n");
413
414             try_return( ntStatus = STATUS_UNSUCCESSFUL);
415         }
416
417         //
418         // Locate the branch end to insert the node
419         //
420
421         while( pCurrentEntry != NULL)
422         {
423
424             //
425             // Greater vlued indices are to the right link
426             //
427
428             if( DirEntry->CaseInsensitiveTreeEntry.HashIndex > pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
429             {
430
431                 //
432                 // Go to the next RIGHT entry, if it exists
433                 //
434
435                 if( pCurrentEntry->CaseInsensitiveTreeEntry.rightLink != NULL)
436                 {
437                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.rightLink;
438                 }
439                 else
440                 {
441
442                     //
443                     // Located the end of the branch line so insert the node
444                     //
445
446                     pCurrentEntry->CaseInsensitiveTreeEntry.rightLink = (void *)DirEntry;
447
448                     DirEntry->CaseInsensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
449
450                     SetFlag( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
451
452                     break;
453                 }
454             }
455             else if( DirEntry->CaseInsensitiveTreeEntry.HashIndex < pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
456             {
457
458                 //
459                 // Go to the next LEFT entry, if it exists
460                 //
461
462                 if( pCurrentEntry->CaseInsensitiveTreeEntry.leftLink != NULL)
463                 {
464                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.leftLink;
465                 }
466                 else
467                 {
468
469                     //
470                     // Located the branch line end so insert the node here
471                     //
472
473                     pCurrentEntry->CaseInsensitiveTreeEntry.leftLink = (void *)DirEntry;
474
475                     DirEntry->CaseInsensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
476
477                     SetFlag( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
478
479                     break;
480                 }
481             }
482             else
483             {
484
485                 //
486                 // Inser the the entry at the end of the insensitive list
487                 //
488
489                 while( pCurrentEntry->CaseInsensitiveList.fLink != NULL)
490                 {
491
492                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveList.fLink;
493                 }
494
495                 pCurrentEntry->CaseInsensitiveList.fLink = (void *)DirEntry;
496
497                 DirEntry->CaseInsensitiveList.bLink = (void *)pCurrentEntry;
498
499                 break;
500             }
501         }
502
503 try_exit:
504
505         NOTHING;
506     }
507
508     return ntStatus;
509 }
510
511 NTSTATUS
512 AFSRemoveCaseSensitiveDirEntry( IN AFSDirectoryCB **RootNode,
513                                 IN AFSDirectoryCB *DirEntry)
514 {
515
516     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
517     AFSDirectoryCB *pRightNode = NULL;
518     AFSDirectoryCB *pLeftNode = NULL;
519     AFSDirectoryCB *pCurrentNode = NULL;
520     AFSDirectoryCB *pParentNode = NULL;
521
522     pRightNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.rightLink;
523     pLeftNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.leftLink;
524     pParentNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.parentLink;
525
526     __Enter
527     {
528
529         if( (pRightNode == NULL) && (pLeftNode == NULL))
530         {
531
532             if( pParentNode != NULL)
533             {
534
535                 if( pParentNode->CaseSensitiveTreeEntry.leftLink == DirEntry)
536                 {
537
538                     pParentNode->CaseSensitiveTreeEntry.leftLink = NULL;
539                 }
540                 else
541                 {
542
543                     pParentNode->CaseSensitiveTreeEntry.rightLink = NULL;
544                 }
545             }
546             else
547             {
548
549                 //
550                 // Removing the top node
551                 //
552
553                 *RootNode = NULL;
554             }
555         }
556         else
557         {
558
559             if( pRightNode != NULL)
560             {
561
562                 if( pParentNode != NULL)
563                 {
564
565                     // Replace the parent node where this entry was.
566                     if( pParentNode->CaseSensitiveTreeEntry.rightLink == DirEntry)
567                     {
568
569                         pParentNode->CaseSensitiveTreeEntry.rightLink = pRightNode;
570                     }
571                     else
572                     {
573
574                         pParentNode->CaseSensitiveTreeEntry.leftLink = pRightNode;
575                     }
576                 }
577                 else
578                 {
579
580                     *RootNode = pRightNode;
581
582                     pRightNode->CaseSensitiveTreeEntry.parentLink = NULL;
583                 }
584
585                 pRightNode->CaseSensitiveTreeEntry.parentLink = pParentNode;
586             }
587
588             if( pLeftNode != NULL)
589             {
590
591                 // To connect the left node, we must walk the chain of the
592                 // right nodes left side until we reach the end.
593                 // At the end attach the leftNode
594                 if( pRightNode != NULL)
595                 {
596
597                     pCurrentNode = pRightNode;
598
599                     while( pCurrentNode->CaseSensitiveTreeEntry.leftLink != NULL)
600                     {
601
602                         pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseSensitiveTreeEntry.leftLink;
603                     }
604
605                     pCurrentNode->CaseSensitiveTreeEntry.leftLink = pLeftNode;
606
607                     pLeftNode->CaseSensitiveTreeEntry.parentLink = pCurrentNode;
608                 }
609                 else
610                 {
611
612                     if( pParentNode != NULL)
613                     {
614
615                         // This is where we have a left node with no right node.
616                         // So, attach the left node to the parent of
617                         // the removed nodes branch
618                         if( pParentNode->CaseSensitiveTreeEntry.rightLink == DirEntry)
619                         {
620
621                             pParentNode->CaseSensitiveTreeEntry.rightLink = pLeftNode;
622                         }
623                         else
624                         {
625
626                             pParentNode->CaseSensitiveTreeEntry.leftLink = pLeftNode;
627                         }
628
629                         pLeftNode->CaseSensitiveTreeEntry.parentLink = pParentNode;
630                     }
631                     else
632                     {
633
634                         *RootNode = pLeftNode;
635
636                         pLeftNode->CaseSensitiveTreeEntry.parentLink = NULL;
637                     }
638                 }
639             }
640         }
641
642         //
643         // Cleanup the just removed node
644         //
645
646         DirEntry->CaseSensitiveTreeEntry.leftLink = NULL;
647         DirEntry->CaseSensitiveTreeEntry.parentLink = NULL;
648         DirEntry->CaseSensitiveTreeEntry.rightLink = NULL;
649
650         ntStatus = STATUS_SUCCESS;
651     }
652
653     return ntStatus;
654 }
655
656 NTSTATUS
657 AFSRemoveCaseInsensitiveDirEntry( IN AFSDirectoryCB **RootNode,
658                                   IN AFSDirectoryCB *DirEntry)
659 {
660
661     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
662     AFSDirectoryCB *pRightNode = NULL;
663     AFSDirectoryCB *pLeftNode = NULL;
664     AFSDirectoryCB *pCurrentNode = NULL;
665     AFSDirectoryCB *pParentNode = NULL;
666     AFSDirectoryCB *pNewHeadEntry = NULL;
667
668     pRightNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.rightLink;
669     pLeftNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.leftLink;
670     pParentNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.parentLink;
671
672     __Enter
673     {
674
675         //
676         // If this is not a head of list entry then just update the pointers for it
677         //
678
679         if( !BooleanFlagOn( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD))
680         {
681
682             ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.bLink)->CaseInsensitiveList.fLink = DirEntry->CaseInsensitiveList.fLink;
683
684             if( DirEntry->CaseInsensitiveList.fLink != NULL)
685             {
686
687                 ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink)->CaseInsensitiveList.bLink = DirEntry->CaseInsensitiveList.bLink;
688             }
689
690             try_return( ntStatus);
691         }
692
693         if( DirEntry->CaseInsensitiveList.fLink != NULL)
694         {
695
696             //
697             // Removing the head of a list of entries so just update pointers
698             //
699
700             pNewHeadEntry = (AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink;
701
702             if( pParentNode != NULL)
703             {
704
705                 if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
706                 {
707                     pParentNode->CaseInsensitiveTreeEntry.rightLink = (void *)pNewHeadEntry;
708                 }
709                 else
710                 {
711                     pParentNode->CaseInsensitiveTreeEntry.leftLink = (void *)pNewHeadEntry;
712                 }
713             }
714             else
715             {
716                 *RootNode = pNewHeadEntry;
717             }
718
719             if( pRightNode != NULL)
720             {
721
722                 pRightNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
723             }
724
725             if( pLeftNode != NULL)
726             {
727
728                 pLeftNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
729             }
730
731             pNewHeadEntry->CaseInsensitiveList.bLink = NULL;
732
733             pNewHeadEntry->CaseInsensitiveTreeEntry.parentLink = pParentNode;
734
735             pNewHeadEntry->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
736
737             pNewHeadEntry->CaseInsensitiveTreeEntry.rightLink = pRightNode;
738
739             SetFlag( pNewHeadEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
740
741             try_return( ntStatus);
742         }
743
744         if( (pRightNode == NULL) && (pLeftNode == NULL))
745         {
746
747             if( pParentNode != NULL)
748             {
749
750                 if( pParentNode->CaseInsensitiveTreeEntry.leftLink == DirEntry)
751                 {
752
753                     pParentNode->CaseInsensitiveTreeEntry.leftLink = NULL;
754                 }
755                 else
756                 {
757
758                     pParentNode->CaseInsensitiveTreeEntry.rightLink = NULL;
759                 }
760             }
761             else
762             {
763
764                 //
765                 // Removing the top node
766                 //
767
768                 *RootNode = NULL;
769             }
770         }
771         else
772         {
773
774             if( pRightNode != NULL)
775             {
776
777                 if( pParentNode != NULL)
778                 {
779
780                     // Replace the parent node where this entry was.
781                     if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
782                     {
783
784                         pParentNode->CaseInsensitiveTreeEntry.rightLink = pRightNode;
785                     }
786                     else
787                     {
788
789                         pParentNode->CaseInsensitiveTreeEntry.leftLink = pRightNode;
790                     }
791                 }
792                 else
793                 {
794
795                     *RootNode = pRightNode;
796
797                     pRightNode->CaseInsensitiveTreeEntry.parentLink = NULL;
798                 }
799
800                 pRightNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
801             }
802
803             if( pLeftNode != NULL)
804             {
805
806                 // To connect the left node, we must walk the chain of the
807                 // right nodes left side until we reach the end.
808                 // At the end attach the leftNode
809                 if( pRightNode != NULL)
810                 {
811
812                     pCurrentNode = pRightNode;
813
814                     while( pCurrentNode->CaseInsensitiveTreeEntry.leftLink != NULL)
815                     {
816
817                         pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseInsensitiveTreeEntry.leftLink;
818                     }
819
820                     pCurrentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
821
822                     pLeftNode->CaseInsensitiveTreeEntry.parentLink = pCurrentNode;
823                 }
824                 else
825                 {
826
827                     if( pParentNode != NULL)
828                     {
829
830                         // This is where we have a left node with no right node.
831                         // So, attach the left node to the parent of
832                         // the removed nodes branch
833                         if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
834                         {
835
836                             pParentNode->CaseInsensitiveTreeEntry.rightLink = pLeftNode;
837                         }
838                         else
839                         {
840
841                             pParentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
842                         }
843
844                         pLeftNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
845                     }
846                     else
847                     {
848
849                         *RootNode = pLeftNode;
850
851                         pLeftNode->CaseInsensitiveTreeEntry.parentLink = NULL;
852                     }
853                 }
854             }
855         }
856
857 try_exit:
858
859         //
860         // Cleanup the just removed node
861         //
862
863         DirEntry->CaseInsensitiveTreeEntry.leftLink = NULL;
864         DirEntry->CaseInsensitiveTreeEntry.parentLink = NULL;
865         DirEntry->CaseInsensitiveTreeEntry.rightLink = NULL;
866
867         DirEntry->CaseInsensitiveList.bLink = NULL;
868         DirEntry->CaseInsensitiveList.fLink = NULL;
869
870         ntStatus = STATUS_SUCCESS;
871     }
872
873     return ntStatus;
874 }
875
876 NTSTATUS
877 AFSLocateShortNameDirEntry( IN AFSDirectoryCB *RootNode,
878                             IN ULONG Index,
879                             IN OUT AFSDirectoryCB **DirEntry)
880 {
881
882     NTSTATUS    ntStatus = STATUS_SUCCESS;
883     AFSDirectoryCB   *pEntry = NULL;
884     AFSDirectoryCB   *pCurrentEntry = NULL;
885
886     pCurrentEntry = RootNode;
887
888     __Enter
889     {
890
891         *DirEntry = NULL;
892
893         //
894         // If the rootnode passed is null then the directory is empty
895         //
896
897         if( RootNode == NULL)
898         {
899
900             try_return( ntStatus = STATUS_INVALID_PARAMETER);
901         }
902
903         //
904         // If the requestor is looking for the root node itself, then return it.
905         //
906
907         if( RootNode->Type.Data.ShortNameTreeEntry.HashIndex == Index)
908         {
909
910             *DirEntry = RootNode;
911
912             try_return( ntStatus);
913         }
914
915         //
916         // Loop through the nodes in the tree
917         //
918
919         while( pCurrentEntry != NULL)
920         {
921
922             //
923             // Greater values are to the right link.
924             //
925
926             if( Index > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
927             {
928
929                 //
930                 // Go to the next RIGHT entry, if there is one
931                 //
932
933                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
934                 {
935
936                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
937                 }
938                 else
939                 {
940
941                     //
942                     // Came to the end of the branch so bail
943                     //
944
945                     pCurrentEntry = NULL;
946
947                     break;
948                 }
949             }
950             else if( Index < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
951             {
952
953                 //
954                 // Go to the next LEFT entry, if one exists
955                 //
956
957                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
958                 {
959
960                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
961                 }
962                 else
963                 {
964
965                     //
966                     // End of the branch ...
967                     //
968
969                     pCurrentEntry = NULL;
970
971                     break;
972                 }
973             }
974             else
975             {
976
977                 //
978                 // Found the entry.
979                 //
980
981                 *DirEntry = pCurrentEntry;
982
983                 break;
984             }
985         }
986
987 try_exit:
988
989         NOTHING;
990     }
991
992     return ntStatus;
993 }
994
995 NTSTATUS
996 AFSInsertShortNameDirEntry( IN AFSDirectoryCB *RootNode,
997                             IN AFSDirectoryCB *DirEntry)
998 {
999
1000     NTSTATUS ntStatus = STATUS_SUCCESS;
1001     AFSDirectoryCB *pCurrentEntry = NULL;
1002
1003     pCurrentEntry = RootNode;
1004
1005     __Enter
1006     {
1007
1008         //
1009         // If we have no root node then we can;t start the search.
1010         //
1011
1012         if( pCurrentEntry == NULL)
1013         {
1014
1015             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1016                           AFS_TRACE_LEVEL_WARNING,
1017                           "AFSInsertShortNameDirEntry Invalid root node\n");
1018
1019             try_return( ntStatus = STATUS_UNSUCCESSFUL);
1020         }
1021
1022         //
1023         // Locate the branch end to insert the node
1024         //
1025
1026         while( pCurrentEntry != NULL)
1027         {
1028
1029             //
1030             // Greater valued indices are to the right link
1031             //
1032
1033             if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1034             {
1035
1036                 //
1037                 // Go to the next RIGHT entry, if it exists
1038                 //
1039
1040                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
1041                 {
1042                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
1043                 }
1044                 else
1045                 {
1046
1047                     //
1048                     // Located the end of the branch line so insert the node
1049                     //
1050
1051                     pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink = (void *)DirEntry;
1052
1053                     DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1054
1055                     break;
1056                 }
1057             }
1058             else if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1059             {
1060
1061                 //
1062                 // Go to the next LEFT entry, if it exists
1063                 //
1064
1065                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1066                 {
1067                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
1068                 }
1069                 else
1070                 {
1071
1072                     //
1073                     // Located the branch line end so insert the node here
1074                     //
1075
1076                     pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink = (void *)DirEntry;
1077
1078                     DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1079
1080                     break;
1081                 }
1082             }
1083             else
1084             {
1085
1086                 ntStatus = STATUS_UNSUCCESSFUL;
1087
1088                 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1089                               AFS_TRACE_LEVEL_VERBOSE,
1090                               "AFSInsertShortNameDirEntry Collision with DE %p for shortname %S and %wZ\n",
1091                               pCurrentEntry,
1092                               pCurrentEntry->NameInformation.ShortName,
1093                               &pCurrentEntry->NameInformation.FileName);
1094
1095                 break;
1096             }
1097         }
1098
1099 try_exit:
1100
1101         NOTHING;
1102     }
1103
1104     return ntStatus;
1105 }
1106
1107 NTSTATUS
1108 AFSRemoveShortNameDirEntry( IN AFSDirectoryCB **RootNode,
1109                             IN AFSDirectoryCB *DirEntry)
1110 {
1111
1112     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1113     AFSDirectoryCB *pRightNode = NULL;
1114     AFSDirectoryCB *pLeftNode = NULL;
1115     AFSDirectoryCB *pCurrentNode = NULL;
1116     AFSDirectoryCB *pParentNode = NULL;
1117
1118     pRightNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.rightLink;
1119     pLeftNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.leftLink;
1120     pParentNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.parentLink;
1121
1122     __Enter
1123     {
1124
1125         if( (pRightNode == NULL) && (pLeftNode == NULL))
1126         {
1127
1128             if( pParentNode != NULL)
1129             {
1130
1131                 if( pParentNode->Type.Data.ShortNameTreeEntry.leftLink == DirEntry)
1132                 {
1133
1134                     pParentNode->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1135                 }
1136                 else
1137                 {
1138
1139                     pParentNode->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1140                 }
1141             }
1142             else
1143             {
1144
1145                 //
1146                 // Removing the top node
1147                 //
1148
1149                 *RootNode = NULL;
1150             }
1151         }
1152         else
1153         {
1154
1155             if( pRightNode != NULL)
1156             {
1157
1158                 if( pParentNode != NULL)
1159                 {
1160
1161                     // Replace the parent node where this entry was.
1162                     if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1163                     {
1164
1165                         pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pRightNode;
1166                     }
1167                     else
1168                     {
1169
1170                         pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pRightNode;
1171                     }
1172                 }
1173                 else
1174                 {
1175
1176                     *RootNode = pRightNode;
1177
1178                     pRightNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1179                 }
1180
1181                 pRightNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1182             }
1183
1184             if( pLeftNode != NULL)
1185             {
1186
1187                 // To connect the left node, we must walk the chain of the
1188                 // right nodes left side until we reach the end.
1189                 // At the end attach the leftNode
1190                 if( pRightNode != NULL)
1191                 {
1192
1193                     pCurrentNode = pRightNode;
1194
1195                     while( pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1196                     {
1197
1198                         pCurrentNode = (AFSDirectoryCB *)pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink;
1199                     }
1200
1201                     pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1202
1203                     pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pCurrentNode;
1204                 }
1205                 else
1206                 {
1207
1208                     if( pParentNode != NULL)
1209                     {
1210
1211                         // This is where we have a left node with no right node.
1212                         // So, attach the left node to the parent of
1213                         // the removed nodes branch
1214                         if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1215                         {
1216
1217                             pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pLeftNode;
1218                         }
1219                         else
1220                         {
1221
1222                             pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1223                         }
1224
1225                         pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1226                     }
1227                     else
1228                     {
1229
1230                         *RootNode = pLeftNode;
1231
1232                         pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1233                     }
1234                 }
1235             }
1236         }
1237
1238         //
1239         // Cleanup the just removed node
1240         //
1241
1242         DirEntry->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1243         DirEntry->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1244         DirEntry->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1245
1246         ntStatus = STATUS_SUCCESS;
1247     }
1248
1249     return ntStatus;
1250 }
1251
1252 NTSTATUS
1253 AFSLocateHashEntry( IN AFSBTreeEntry *TopNode,
1254                     IN ULONGLONG HashIndex,
1255                     IN OUT AFSBTreeEntry **TreeEntry)
1256 {
1257
1258     NTSTATUS         ntStatus = STATUS_SUCCESS;
1259     AFSBTreeEntry   *pEntry = NULL;
1260     AFSBTreeEntry   *pCurrentEntry = NULL;
1261
1262     pCurrentEntry = TopNode;
1263
1264     __Enter
1265     {
1266
1267         //
1268         // If the rootnode passed is null then the directory is empty
1269         //
1270
1271         if( TopNode == NULL)
1272         {
1273
1274             try_return( ntStatus = STATUS_INVALID_PARAMETER);
1275         }
1276
1277         //
1278         // If the requestor is looking for the root node itself, then return it.
1279         //
1280
1281         if( TopNode->HashIndex == HashIndex)
1282         {
1283
1284             *TreeEntry = TopNode;
1285
1286             try_return( ntStatus);
1287         }
1288
1289         //
1290         // Loop through the nodes in the tree
1291         //
1292
1293         while( pCurrentEntry != NULL)
1294         {
1295
1296             //
1297             // Greater values are to the right link.
1298             //
1299
1300             if( HashIndex > pCurrentEntry->HashIndex)
1301             {
1302
1303                 //
1304                 // Go to the next RIGHT entry, if there is one
1305                 //
1306
1307                 if( pCurrentEntry->rightLink != NULL)
1308                 {
1309
1310                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1311                 }
1312                 else
1313                 {
1314
1315                     //
1316                     // Came to the end of the branch so bail
1317                     //
1318
1319                     pCurrentEntry = NULL;
1320
1321                     break;
1322                 }
1323             }
1324             else if( HashIndex < pCurrentEntry->HashIndex)
1325             {
1326
1327                 //
1328                 // Go to the next LEFT entry, if one exists
1329                 //
1330
1331                 if( pCurrentEntry->leftLink != NULL)
1332                 {
1333
1334                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1335                 }
1336                 else
1337                 {
1338
1339                     //
1340                     // End of the branch ...
1341                     //
1342
1343                     pCurrentEntry = NULL;
1344
1345                     break;
1346                 }
1347             }
1348             else
1349             {
1350
1351                 //
1352                 // Found the entry.
1353                 //
1354
1355                 *TreeEntry = pCurrentEntry;
1356
1357                 break;
1358             }
1359         }
1360
1361 try_exit:
1362
1363         NOTHING;
1364     }
1365
1366     return ntStatus;
1367 }
1368
1369 NTSTATUS
1370 AFSInsertHashEntry( IN AFSBTreeEntry *TopNode,
1371                     IN AFSBTreeEntry *FileIDEntry)
1372 {
1373
1374     NTSTATUS ntStatus = STATUS_SUCCESS;
1375     AFSBTreeEntry *pCurrentEntry = NULL;
1376
1377     pCurrentEntry = TopNode;
1378
1379     __Enter
1380     {
1381
1382         //
1383         // If we have no root node then we can;t start the search.
1384         //
1385
1386         if( pCurrentEntry == NULL)
1387         {
1388
1389             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1390                           AFS_TRACE_LEVEL_WARNING,
1391                           "AFSInsertHashEntry Invalid root node\n");
1392
1393             try_return( ntStatus = STATUS_UNSUCCESSFUL);
1394         }
1395
1396         //
1397         // Locate the branch end to insert the node
1398         //
1399
1400         while( pCurrentEntry != NULL)
1401         {
1402
1403             //
1404             // Greater vlued indices are to the right link
1405             //
1406
1407             if( FileIDEntry->HashIndex > pCurrentEntry->HashIndex)
1408             {
1409
1410                 //
1411                 // Go to the next RIGHT entry, if it exists
1412                 //
1413
1414                 if( pCurrentEntry->rightLink != NULL)
1415                 {
1416                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1417                 }
1418                 else
1419                 {
1420
1421                     //
1422                     // Located the end of the branch line so insert the node
1423                     //
1424
1425                     pCurrentEntry->rightLink = (void *)FileIDEntry;
1426
1427                     FileIDEntry->parentLink = (void *)pCurrentEntry;
1428
1429                     break;
1430                 }
1431             }
1432             else if( FileIDEntry->HashIndex < pCurrentEntry->HashIndex)
1433             {
1434
1435                 //
1436                 // Go to the next LEFT entry, if it exists
1437                 //
1438
1439                 if( pCurrentEntry->leftLink != NULL)
1440                 {
1441                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1442                 }
1443                 else
1444                 {
1445
1446                     //
1447                     // Located the branch line end so insert the node here
1448                     //
1449
1450                     pCurrentEntry->leftLink = (void *)FileIDEntry;
1451
1452                     FileIDEntry->parentLink = (void *)pCurrentEntry;
1453
1454                     break;
1455                 }
1456             }
1457             else
1458             {
1459
1460                 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1461                               AFS_TRACE_LEVEL_WARNING,
1462                               "AFSInsertHashEntry Attempt to re-insert a CRC %I64X\n",
1463                               FileIDEntry->HashIndex);
1464
1465                 ASSERT( FALSE);
1466
1467                 ntStatus = STATUS_UNSUCCESSFUL;
1468
1469                 break;
1470             }
1471         }
1472
1473 try_exit:
1474
1475         NOTHING;
1476     }
1477
1478     return ntStatus;
1479 }
1480
1481 NTSTATUS
1482 AFSRemoveHashEntry( IN AFSBTreeEntry **TopNode,
1483                     IN AFSBTreeEntry *FileIDEntry)
1484 {
1485
1486     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1487     AFSBTreeEntry *pRightNode = NULL;
1488     AFSBTreeEntry *pLeftNode = NULL;
1489     AFSBTreeEntry *pCurrentNode = NULL;
1490     AFSBTreeEntry *pParentNode = NULL;
1491
1492     pRightNode = (AFSBTreeEntry *)FileIDEntry->rightLink;
1493     pLeftNode = (AFSBTreeEntry *)FileIDEntry->leftLink;
1494     pParentNode = (AFSBTreeEntry *)FileIDEntry->parentLink;
1495
1496     __Enter
1497     {
1498
1499         if( (pRightNode == NULL) && (pLeftNode == NULL))
1500         {
1501
1502             if( pParentNode != NULL)
1503             {
1504
1505                 if( pParentNode->leftLink == FileIDEntry)
1506                 {
1507
1508                     pParentNode->leftLink = NULL;
1509                 }
1510                 else
1511                 {
1512
1513                     pParentNode->rightLink = NULL;
1514                 }
1515             }
1516             else
1517             {
1518
1519                 //
1520                 // Removing the top node
1521                 //
1522
1523                 *TopNode = NULL;
1524             }
1525         }
1526         else
1527         {
1528
1529             if( pRightNode != NULL)
1530             {
1531
1532                 if( pParentNode != NULL)
1533                 {
1534
1535                     // Replace the parent node where this entry was.
1536                     if( pParentNode->rightLink == FileIDEntry)
1537                     {
1538
1539                         pParentNode->rightLink = pRightNode;
1540                     }
1541                     else
1542                     {
1543
1544                         pParentNode->leftLink = pRightNode;
1545                     }
1546                 }
1547                 else
1548                 {
1549
1550                     *TopNode = pRightNode;
1551
1552                     pRightNode->parentLink = NULL;
1553                 }
1554
1555                 pRightNode->parentLink = pParentNode;
1556             }
1557
1558             if( pLeftNode != NULL)
1559             {
1560
1561                 // To connect the left node, we must walk the chain of the
1562                 // right nodes left side until we reach the end.
1563                 // At the end attach the leftNode
1564                 if( pRightNode != NULL)
1565                 {
1566
1567                     pCurrentNode = pRightNode;
1568
1569                     while( pCurrentNode->leftLink != NULL)
1570                     {
1571
1572                         pCurrentNode = (AFSBTreeEntry *)pCurrentNode->leftLink;
1573                     }
1574
1575                     pCurrentNode->leftLink = pLeftNode;
1576
1577                     pLeftNode->parentLink = pCurrentNode;
1578                 }
1579                 else
1580                 {
1581
1582                     if( pParentNode != NULL)
1583                     {
1584
1585                         // This is where we have a left node with no right node.
1586                         // So, attach the left node to the parent of
1587                         // the removed nodes branch
1588                         if( pParentNode->rightLink == FileIDEntry)
1589                         {
1590
1591                             pParentNode->rightLink = pLeftNode;
1592                         }
1593                         else
1594                         {
1595
1596                             pParentNode->leftLink = pLeftNode;
1597                         }
1598
1599                         pLeftNode->parentLink = pParentNode;
1600                     }
1601                     else
1602                     {
1603
1604                         *TopNode = pLeftNode;
1605
1606                         pLeftNode->parentLink = NULL;
1607                     }
1608                 }
1609             }
1610         }
1611
1612         //
1613         // Cleanup the just removed node
1614         //
1615
1616         FileIDEntry->leftLink = NULL;
1617         FileIDEntry->parentLink = NULL;
1618         FileIDEntry->rightLink = NULL;
1619
1620         ntStatus = STATUS_SUCCESS;
1621     }
1622
1623     return ntStatus;
1624 }