Windows: AFSRemoveCaseInsensitiveDirEntry corrections
[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_WARNING,
372                               "AFSInsertCaseSensitiveDirEntry Attempt to re-insert a CRC %I64X\n",
373                               DirEntry->CaseSensitiveTreeEntry.HashIndex);
374
375                 ASSERT( FALSE);
376
377                 ntStatus = STATUS_UNSUCCESSFUL;
378
379                 break;
380             }
381         }
382
383 try_exit:
384
385         NOTHING;
386     }
387
388     return ntStatus;
389 }
390
391 NTSTATUS
392 AFSInsertCaseInsensitiveDirEntry( IN AFSDirectoryCB *RootNode,
393                                   IN AFSDirectoryCB *DirEntry)
394 {
395
396     NTSTATUS ntStatus = STATUS_SUCCESS;
397     AFSDirectoryCB *pCurrentEntry = NULL;
398
399     pCurrentEntry = RootNode;
400
401     __Enter
402     {
403
404         //
405         // If we have no root node then we can;t start the search.
406         //
407
408         if( pCurrentEntry == NULL)
409         {
410
411             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
412                           AFS_TRACE_LEVEL_WARNING,
413                           "AFSInsertCaseInsensitiveDirEntry Invalid root node\n");
414
415             try_return( ntStatus = STATUS_UNSUCCESSFUL);
416         }
417
418         //
419         // Locate the branch end to insert the node
420         //
421
422         while( pCurrentEntry != NULL)
423         {
424
425             //
426             // Greater vlued indices are to the right link
427             //
428
429             if( DirEntry->CaseInsensitiveTreeEntry.HashIndex > pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
430             {
431
432                 //
433                 // Go to the next RIGHT entry, if it exists
434                 //
435
436                 if( pCurrentEntry->CaseInsensitiveTreeEntry.rightLink != NULL)
437                 {
438                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.rightLink;
439                 }
440                 else
441                 {
442
443                     //
444                     // Located the end of the branch line so insert the node
445                     //
446
447                     pCurrentEntry->CaseInsensitiveTreeEntry.rightLink = (void *)DirEntry;
448
449                     DirEntry->CaseInsensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
450
451                     SetFlag( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
452
453                     break;
454                 }
455             }
456             else if( DirEntry->CaseInsensitiveTreeEntry.HashIndex < pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
457             {
458
459                 //
460                 // Go to the next LEFT entry, if it exists
461                 //
462
463                 if( pCurrentEntry->CaseInsensitiveTreeEntry.leftLink != NULL)
464                 {
465                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.leftLink;
466                 }
467                 else
468                 {
469
470                     //
471                     // Located the branch line end so insert the node here
472                     //
473
474                     pCurrentEntry->CaseInsensitiveTreeEntry.leftLink = (void *)DirEntry;
475
476                     DirEntry->CaseInsensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
477
478                     SetFlag( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
479
480                     break;
481                 }
482             }
483             else
484             {
485
486                 //
487                 // Inser the the entry at the end of the insensitive list
488                 //
489
490                 while( pCurrentEntry->CaseInsensitiveList.fLink != NULL)
491                 {
492
493                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveList.fLink;
494                 }
495
496                 pCurrentEntry->CaseInsensitiveList.fLink = (void *)DirEntry;
497
498                 DirEntry->CaseInsensitiveList.bLink = (void *)pCurrentEntry;
499
500                 break;
501             }
502         }
503
504 try_exit:
505
506         NOTHING;
507     }
508
509     return ntStatus;
510 }
511
512 NTSTATUS
513 AFSRemoveCaseSensitiveDirEntry( IN AFSDirectoryCB **RootNode,
514                                 IN AFSDirectoryCB *DirEntry)
515 {
516
517     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
518     AFSDirectoryCB *pRightNode = NULL;
519     AFSDirectoryCB *pLeftNode = NULL;
520     AFSDirectoryCB *pCurrentNode = NULL;
521     AFSDirectoryCB *pParentNode = NULL;
522
523     pRightNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.rightLink;
524     pLeftNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.leftLink;
525     pParentNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.parentLink;
526
527     __Enter
528     {
529
530         if( (pRightNode == NULL) && (pLeftNode == NULL))
531         {
532
533             if( pParentNode != NULL)
534             {
535
536                 if( pParentNode->CaseSensitiveTreeEntry.leftLink == DirEntry)
537                 {
538
539                     pParentNode->CaseSensitiveTreeEntry.leftLink = NULL;
540                 }
541                 else
542                 {
543
544                     pParentNode->CaseSensitiveTreeEntry.rightLink = NULL;
545                 }
546             }
547             else
548             {
549
550                 //
551                 // Removing the top node
552                 //
553
554                 *RootNode = NULL;
555             }
556         }
557         else
558         {
559
560             if( pRightNode != NULL)
561             {
562
563                 if( pParentNode != NULL)
564                 {
565
566                     // Replace the parent node where this entry was.
567                     if( pParentNode->CaseSensitiveTreeEntry.rightLink == DirEntry)
568                     {
569
570                         pParentNode->CaseSensitiveTreeEntry.rightLink = pRightNode;
571                     }
572                     else
573                     {
574
575                         pParentNode->CaseSensitiveTreeEntry.leftLink = pRightNode;
576                     }
577                 }
578                 else
579                 {
580
581                     *RootNode = pRightNode;
582
583                     pRightNode->CaseSensitiveTreeEntry.parentLink = NULL;
584                 }
585
586                 pRightNode->CaseSensitiveTreeEntry.parentLink = pParentNode;
587             }
588
589             if( pLeftNode != NULL)
590             {
591
592                 // To connect the left node, we must walk the chain of the
593                 // right nodes left side until we reach the end.
594                 // At the end attach the leftNode
595                 if( pRightNode != NULL)
596                 {
597
598                     pCurrentNode = pRightNode;
599
600                     while( pCurrentNode->CaseSensitiveTreeEntry.leftLink != NULL)
601                     {
602
603                         pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseSensitiveTreeEntry.leftLink;
604                     }
605
606                     pCurrentNode->CaseSensitiveTreeEntry.leftLink = pLeftNode;
607
608                     pLeftNode->CaseSensitiveTreeEntry.parentLink = pCurrentNode;
609                 }
610                 else
611                 {
612
613                     if( pParentNode != NULL)
614                     {
615
616                         // This is where we have a left node with no right node.
617                         // So, attach the left node to the parent of
618                         // the removed nodes branch
619                         if( pParentNode->CaseSensitiveTreeEntry.rightLink == DirEntry)
620                         {
621
622                             pParentNode->CaseSensitiveTreeEntry.rightLink = pLeftNode;
623                         }
624                         else
625                         {
626
627                             pParentNode->CaseSensitiveTreeEntry.leftLink = pLeftNode;
628                         }
629
630                         pLeftNode->CaseSensitiveTreeEntry.parentLink = pParentNode;
631                     }
632                     else
633                     {
634
635                         *RootNode = pLeftNode;
636
637                         pLeftNode->CaseSensitiveTreeEntry.parentLink = NULL;
638                     }
639                 }
640             }
641         }
642
643         //
644         // Cleanup the just removed node
645         //
646
647         DirEntry->CaseSensitiveTreeEntry.leftLink = NULL;
648         DirEntry->CaseSensitiveTreeEntry.parentLink = NULL;
649         DirEntry->CaseSensitiveTreeEntry.rightLink = NULL;
650
651         ntStatus = STATUS_SUCCESS;
652     }
653
654     return ntStatus;
655 }
656
657 NTSTATUS
658 AFSRemoveCaseInsensitiveDirEntry( IN AFSDirectoryCB **RootNode,
659                                   IN AFSDirectoryCB *DirEntry)
660 {
661
662     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
663     AFSDirectoryCB *pRightNode = NULL;
664     AFSDirectoryCB *pLeftNode = NULL;
665     AFSDirectoryCB *pCurrentNode = NULL;
666     AFSDirectoryCB *pParentNode = NULL;
667     AFSDirectoryCB *pNewHeadEntry = NULL;
668
669     pRightNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.rightLink;
670     pLeftNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.leftLink;
671     pParentNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.parentLink;
672
673     __Enter
674     {
675
676         //
677         // If this is not a head of list entry then just update the pointers for it
678         //
679
680         if( !BooleanFlagOn( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD))
681         {
682
683             ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.bLink)->CaseInsensitiveList.fLink = DirEntry->CaseInsensitiveList.fLink;
684
685             if( DirEntry->CaseInsensitiveList.fLink != NULL)
686             {
687
688                 ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink)->CaseInsensitiveList.bLink = DirEntry->CaseInsensitiveList.bLink;
689             }
690
691             try_return( ntStatus);
692         }
693
694         if( DirEntry->CaseInsensitiveList.fLink != NULL)
695         {
696
697             //
698             // Removing the head of a list of entries so just update pointers
699             //
700
701             pNewHeadEntry = (AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink;
702
703             if( pParentNode != NULL)
704             {
705
706                 if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
707                 {
708                     pParentNode->CaseInsensitiveTreeEntry.rightLink = (void *)pNewHeadEntry;
709                 }
710                 else
711                 {
712                     pParentNode->CaseInsensitiveTreeEntry.leftLink = (void *)pNewHeadEntry;
713                 }
714             }
715             else
716             {
717                 *RootNode = pNewHeadEntry;
718             }
719
720             if( pRightNode != NULL)
721             {
722
723                 pRightNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
724             }
725
726             if( pLeftNode != NULL)
727             {
728
729                 pLeftNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
730             }
731
732             pNewHeadEntry->CaseInsensitiveList.bLink = NULL;
733
734             pNewHeadEntry->CaseInsensitiveTreeEntry.parentLink = pParentNode;
735
736             pNewHeadEntry->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
737
738             pNewHeadEntry->CaseInsensitiveTreeEntry.rightLink = pRightNode;
739
740             SetFlag( pNewHeadEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
741
742             try_return( ntStatus);
743         }
744
745         if( (pRightNode == NULL) && (pLeftNode == NULL))
746         {
747
748             if( pParentNode != NULL)
749             {
750
751                 if( pParentNode->CaseInsensitiveTreeEntry.leftLink == DirEntry)
752                 {
753
754                     pParentNode->CaseInsensitiveTreeEntry.leftLink = NULL;
755                 }
756                 else
757                 {
758
759                     pParentNode->CaseInsensitiveTreeEntry.rightLink = NULL;
760                 }
761             }
762             else
763             {
764
765                 //
766                 // Removing the top node
767                 //
768
769                 *RootNode = NULL;
770             }
771         }
772         else
773         {
774
775             if( pRightNode != NULL)
776             {
777
778                 if( pParentNode != NULL)
779                 {
780
781                     // Replace the parent node where this entry was.
782                     if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
783                     {
784
785                         pParentNode->CaseInsensitiveTreeEntry.rightLink = pRightNode;
786                     }
787                     else
788                     {
789
790                         pParentNode->CaseInsensitiveTreeEntry.leftLink = pRightNode;
791                     }
792                 }
793                 else
794                 {
795
796                     *RootNode = pRightNode;
797
798                     pRightNode->CaseInsensitiveTreeEntry.parentLink = NULL;
799                 }
800
801                 pRightNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
802             }
803
804             if( pLeftNode != NULL)
805             {
806
807                 // To connect the left node, we must walk the chain of the
808                 // right nodes left side until we reach the end.
809                 // At the end attach the leftNode
810                 if( pRightNode != NULL)
811                 {
812
813                     pCurrentNode = pRightNode;
814
815                     while( pCurrentNode->CaseInsensitiveTreeEntry.leftLink != NULL)
816                     {
817
818                         pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseInsensitiveTreeEntry.leftLink;
819                     }
820
821                     pCurrentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
822
823                     pLeftNode->CaseInsensitiveTreeEntry.parentLink = pCurrentNode;
824                 }
825                 else
826                 {
827
828                     if( pParentNode != NULL)
829                     {
830
831                         // This is where we have a left node with no right node.
832                         // So, attach the left node to the parent of
833                         // the removed nodes branch
834                         if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
835                         {
836
837                             pParentNode->CaseInsensitiveTreeEntry.rightLink = pLeftNode;
838                         }
839                         else
840                         {
841
842                             pParentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
843                         }
844
845                         pLeftNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
846                     }
847                     else
848                     {
849
850                         *RootNode = pLeftNode;
851
852                         pLeftNode->CaseInsensitiveTreeEntry.parentLink = NULL;
853                     }
854                 }
855             }
856         }
857
858 try_exit:
859
860         //
861         // Cleanup the just removed node
862         //
863
864         DirEntry->CaseInsensitiveTreeEntry.leftLink = NULL;
865         DirEntry->CaseInsensitiveTreeEntry.parentLink = NULL;
866         DirEntry->CaseInsensitiveTreeEntry.rightLink = NULL;
867
868         DirEntry->CaseInsensitiveList.bLink = NULL;
869         DirEntry->CaseInsensitiveList.fLink = NULL;
870
871         ntStatus = STATUS_SUCCESS;
872     }
873
874     return ntStatus;
875 }
876
877 NTSTATUS
878 AFSLocateShortNameDirEntry( IN AFSDirectoryCB *RootNode,
879                             IN ULONG Index,
880                             IN OUT AFSDirectoryCB **DirEntry)
881 {
882
883     NTSTATUS    ntStatus = STATUS_SUCCESS;
884     AFSDirectoryCB   *pEntry = NULL;
885     AFSDirectoryCB   *pCurrentEntry = NULL;
886
887     pCurrentEntry = RootNode;
888
889     __Enter
890     {
891
892         *DirEntry = NULL;
893
894         //
895         // If the rootnode passed is null then the directory is empty
896         //
897
898         if( RootNode == NULL)
899         {
900
901             try_return( ntStatus = STATUS_INVALID_PARAMETER);
902         }
903
904         //
905         // If the requestor is looking for the root node itself, then return it.
906         //
907
908         if( RootNode->Type.Data.ShortNameTreeEntry.HashIndex == Index)
909         {
910
911             *DirEntry = RootNode;
912
913             try_return( ntStatus);
914         }
915
916         //
917         // Loop through the nodes in the tree
918         //
919
920         while( pCurrentEntry != NULL)
921         {
922
923             //
924             // Greater values are to the right link.
925             //
926
927             if( Index > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
928             {
929
930                 //
931                 // Go to the next RIGHT entry, if there is one
932                 //
933
934                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
935                 {
936
937                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
938                 }
939                 else
940                 {
941
942                     //
943                     // Came to the end of the branch so bail
944                     //
945
946                     pCurrentEntry = NULL;
947
948                     break;
949                 }
950             }
951             else if( Index < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
952             {
953
954                 //
955                 // Go to the next LEFT entry, if one exists
956                 //
957
958                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
959                 {
960
961                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
962                 }
963                 else
964                 {
965
966                     //
967                     // End of the branch ...
968                     //
969
970                     pCurrentEntry = NULL;
971
972                     break;
973                 }
974             }
975             else
976             {
977
978                 //
979                 // Found the entry.
980                 //
981
982                 *DirEntry = pCurrentEntry;
983
984                 break;
985             }
986         }
987
988 try_exit:
989
990         NOTHING;
991     }
992
993     return ntStatus;
994 }
995
996 NTSTATUS
997 AFSInsertShortNameDirEntry( IN AFSDirectoryCB *RootNode,
998                             IN AFSDirectoryCB *DirEntry)
999 {
1000
1001     NTSTATUS ntStatus = STATUS_SUCCESS;
1002     AFSDirectoryCB *pCurrentEntry = NULL;
1003
1004     pCurrentEntry = RootNode;
1005
1006     __Enter
1007     {
1008
1009         //
1010         // If we have no root node then we can;t start the search.
1011         //
1012
1013         if( pCurrentEntry == NULL)
1014         {
1015
1016             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1017                           AFS_TRACE_LEVEL_WARNING,
1018                           "AFSInsertShortNameDirEntry Invalid root node\n");
1019
1020             try_return( ntStatus = STATUS_UNSUCCESSFUL);
1021         }
1022
1023         //
1024         // Locate the branch end to insert the node
1025         //
1026
1027         while( pCurrentEntry != NULL)
1028         {
1029
1030             //
1031             // Greater valued indices are to the right link
1032             //
1033
1034             if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1035             {
1036
1037                 //
1038                 // Go to the next RIGHT entry, if it exists
1039                 //
1040
1041                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
1042                 {
1043                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
1044                 }
1045                 else
1046                 {
1047
1048                     //
1049                     // Located the end of the branch line so insert the node
1050                     //
1051
1052                     pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink = (void *)DirEntry;
1053
1054                     DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1055
1056                     break;
1057                 }
1058             }
1059             else if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1060             {
1061
1062                 //
1063                 // Go to the next LEFT entry, if it exists
1064                 //
1065
1066                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1067                 {
1068                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
1069                 }
1070                 else
1071                 {
1072
1073                     //
1074                     // Located the branch line end so insert the node here
1075                     //
1076
1077                     pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink = (void *)DirEntry;
1078
1079                     DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1080
1081                     break;
1082                 }
1083             }
1084             else
1085             {
1086
1087                 break;
1088             }
1089         }
1090
1091 try_exit:
1092
1093         NOTHING;
1094     }
1095
1096     return ntStatus;
1097 }
1098
1099 NTSTATUS
1100 AFSRemoveShortNameDirEntry( IN AFSDirectoryCB **RootNode,
1101                             IN AFSDirectoryCB *DirEntry)
1102 {
1103
1104     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1105     AFSDirectoryCB *pRightNode = NULL;
1106     AFSDirectoryCB *pLeftNode = NULL;
1107     AFSDirectoryCB *pCurrentNode = NULL;
1108     AFSDirectoryCB *pParentNode = NULL;
1109
1110     pRightNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.rightLink;
1111     pLeftNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.leftLink;
1112     pParentNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.parentLink;
1113
1114     __Enter
1115     {
1116
1117         if( (pRightNode == NULL) && (pLeftNode == NULL))
1118         {
1119
1120             if( pParentNode != NULL)
1121             {
1122
1123                 if( pParentNode->Type.Data.ShortNameTreeEntry.leftLink == DirEntry)
1124                 {
1125
1126                     pParentNode->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1127                 }
1128                 else
1129                 {
1130
1131                     pParentNode->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1132                 }
1133             }
1134             else
1135             {
1136
1137                 //
1138                 // Removing the top node
1139                 //
1140
1141                 *RootNode = NULL;
1142             }
1143         }
1144         else
1145         {
1146
1147             if( pRightNode != NULL)
1148             {
1149
1150                 if( pParentNode != NULL)
1151                 {
1152
1153                     // Replace the parent node where this entry was.
1154                     if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1155                     {
1156
1157                         pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pRightNode;
1158                     }
1159                     else
1160                     {
1161
1162                         pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pRightNode;
1163                     }
1164                 }
1165                 else
1166                 {
1167
1168                     *RootNode = pRightNode;
1169
1170                     pRightNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1171                 }
1172
1173                 pRightNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1174             }
1175
1176             if( pLeftNode != NULL)
1177             {
1178
1179                 // To connect the left node, we must walk the chain of the
1180                 // right nodes left side until we reach the end.
1181                 // At the end attach the leftNode
1182                 if( pRightNode != NULL)
1183                 {
1184
1185                     pCurrentNode = pRightNode;
1186
1187                     while( pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1188                     {
1189
1190                         pCurrentNode = (AFSDirectoryCB *)pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink;
1191                     }
1192
1193                     pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1194
1195                     pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pCurrentNode;
1196                 }
1197                 else
1198                 {
1199
1200                     if( pParentNode != NULL)
1201                     {
1202
1203                         // This is where we have a left node with no right node.
1204                         // So, attach the left node to the parent of
1205                         // the removed nodes branch
1206                         if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1207                         {
1208
1209                             pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pLeftNode;
1210                         }
1211                         else
1212                         {
1213
1214                             pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1215                         }
1216
1217                         pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1218                     }
1219                     else
1220                     {
1221
1222                         *RootNode = pLeftNode;
1223
1224                         pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1225                     }
1226                 }
1227             }
1228         }
1229
1230         //
1231         // Cleanup the just removed node
1232         //
1233
1234         DirEntry->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1235         DirEntry->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1236         DirEntry->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1237
1238         ntStatus = STATUS_SUCCESS;
1239     }
1240
1241     return ntStatus;
1242 }
1243
1244 NTSTATUS
1245 AFSLocateHashEntry( IN AFSBTreeEntry *TopNode,
1246                     IN ULONGLONG HashIndex,
1247                     IN OUT AFSBTreeEntry **TreeEntry)
1248 {
1249
1250     NTSTATUS         ntStatus = STATUS_SUCCESS;
1251     AFSBTreeEntry   *pEntry = NULL;
1252     AFSBTreeEntry   *pCurrentEntry = NULL;
1253
1254     pCurrentEntry = TopNode;
1255
1256     __Enter
1257     {
1258
1259         //
1260         // If the rootnode passed is null then the directory is empty
1261         //
1262
1263         if( TopNode == NULL)
1264         {
1265
1266             try_return( ntStatus = STATUS_INVALID_PARAMETER);
1267         }
1268
1269         //
1270         // If the requestor is looking for the root node itself, then return it.
1271         //
1272
1273         if( TopNode->HashIndex == HashIndex)
1274         {
1275
1276             *TreeEntry = TopNode;
1277
1278             try_return( ntStatus);
1279         }
1280
1281         //
1282         // Loop through the nodes in the tree
1283         //
1284
1285         while( pCurrentEntry != NULL)
1286         {
1287
1288             //
1289             // Greater values are to the right link.
1290             //
1291
1292             if( HashIndex > pCurrentEntry->HashIndex)
1293             {
1294
1295                 //
1296                 // Go to the next RIGHT entry, if there is one
1297                 //
1298
1299                 if( pCurrentEntry->rightLink != NULL)
1300                 {
1301
1302                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1303                 }
1304                 else
1305                 {
1306
1307                     //
1308                     // Came to the end of the branch so bail
1309                     //
1310
1311                     pCurrentEntry = NULL;
1312
1313                     break;
1314                 }
1315             }
1316             else if( HashIndex < pCurrentEntry->HashIndex)
1317             {
1318
1319                 //
1320                 // Go to the next LEFT entry, if one exists
1321                 //
1322
1323                 if( pCurrentEntry->leftLink != NULL)
1324                 {
1325
1326                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1327                 }
1328                 else
1329                 {
1330
1331                     //
1332                     // End of the branch ...
1333                     //
1334
1335                     pCurrentEntry = NULL;
1336
1337                     break;
1338                 }
1339             }
1340             else
1341             {
1342
1343                 //
1344                 // Found the entry.
1345                 //
1346
1347                 *TreeEntry = pCurrentEntry;
1348
1349                 break;
1350             }
1351         }
1352
1353 try_exit:
1354
1355         NOTHING;
1356     }
1357
1358     return ntStatus;
1359 }
1360
1361 NTSTATUS
1362 AFSInsertHashEntry( IN AFSBTreeEntry *TopNode,
1363                     IN AFSBTreeEntry *FileIDEntry)
1364 {
1365
1366     NTSTATUS ntStatus = STATUS_SUCCESS;
1367     AFSBTreeEntry *pCurrentEntry = NULL;
1368
1369     pCurrentEntry = TopNode;
1370
1371     __Enter
1372     {
1373
1374         //
1375         // If we have no root node then we can;t start the search.
1376         //
1377
1378         if( pCurrentEntry == NULL)
1379         {
1380
1381             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1382                           AFS_TRACE_LEVEL_WARNING,
1383                           "AFSInsertHashEntry Invalid root node\n");
1384
1385             try_return( ntStatus = STATUS_UNSUCCESSFUL);
1386         }
1387
1388         //
1389         // Locate the branch end to insert the node
1390         //
1391
1392         while( pCurrentEntry != NULL)
1393         {
1394
1395             //
1396             // Greater vlued indices are to the right link
1397             //
1398
1399             if( FileIDEntry->HashIndex > pCurrentEntry->HashIndex)
1400             {
1401
1402                 //
1403                 // Go to the next RIGHT entry, if it exists
1404                 //
1405
1406                 if( pCurrentEntry->rightLink != NULL)
1407                 {
1408                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1409                 }
1410                 else
1411                 {
1412
1413                     //
1414                     // Located the end of the branch line so insert the node
1415                     //
1416
1417                     pCurrentEntry->rightLink = (void *)FileIDEntry;
1418
1419                     FileIDEntry->parentLink = (void *)pCurrentEntry;
1420
1421                     break;
1422                 }
1423             }
1424             else if( FileIDEntry->HashIndex < pCurrentEntry->HashIndex)
1425             {
1426
1427                 //
1428                 // Go to the next LEFT entry, if it exists
1429                 //
1430
1431                 if( pCurrentEntry->leftLink != NULL)
1432                 {
1433                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1434                 }
1435                 else
1436                 {
1437
1438                     //
1439                     // Located the branch line end so insert the node here
1440                     //
1441
1442                     pCurrentEntry->leftLink = (void *)FileIDEntry;
1443
1444                     FileIDEntry->parentLink = (void *)pCurrentEntry;
1445
1446                     break;
1447                 }
1448             }
1449             else
1450             {
1451
1452                 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1453                               AFS_TRACE_LEVEL_WARNING,
1454                               "AFSInsertHashEntry Attempt to re-insert a CRC %I64X\n",
1455                               FileIDEntry->HashIndex);
1456
1457                 ASSERT( FALSE);
1458
1459                 ntStatus = STATUS_UNSUCCESSFUL;
1460
1461                 break;
1462             }
1463         }
1464
1465 try_exit:
1466
1467         NOTHING;
1468     }
1469
1470     return ntStatus;
1471 }
1472
1473 NTSTATUS
1474 AFSRemoveHashEntry( IN AFSBTreeEntry **TopNode,
1475                     IN AFSBTreeEntry *FileIDEntry)
1476 {
1477
1478     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1479     AFSBTreeEntry *pRightNode = NULL;
1480     AFSBTreeEntry *pLeftNode = NULL;
1481     AFSBTreeEntry *pCurrentNode = NULL;
1482     AFSBTreeEntry *pParentNode = NULL;
1483
1484     pRightNode = (AFSBTreeEntry *)FileIDEntry->rightLink;
1485     pLeftNode = (AFSBTreeEntry *)FileIDEntry->leftLink;
1486     pParentNode = (AFSBTreeEntry *)FileIDEntry->parentLink;
1487
1488     __Enter
1489     {
1490
1491         if( (pRightNode == NULL) && (pLeftNode == NULL))
1492         {
1493
1494             if( pParentNode != NULL)
1495             {
1496
1497                 if( pParentNode->leftLink == FileIDEntry)
1498                 {
1499
1500                     pParentNode->leftLink = NULL;
1501                 }
1502                 else
1503                 {
1504
1505                     pParentNode->rightLink = NULL;
1506                 }
1507             }
1508             else
1509             {
1510
1511                 //
1512                 // Removing the top node
1513                 //
1514
1515                 *TopNode = NULL;
1516             }
1517         }
1518         else
1519         {
1520
1521             if( pRightNode != NULL)
1522             {
1523
1524                 if( pParentNode != NULL)
1525                 {
1526
1527                     // Replace the parent node where this entry was.
1528                     if( pParentNode->rightLink == FileIDEntry)
1529                     {
1530
1531                         pParentNode->rightLink = pRightNode;
1532                     }
1533                     else
1534                     {
1535
1536                         pParentNode->leftLink = pRightNode;
1537                     }
1538                 }
1539                 else
1540                 {
1541
1542                     *TopNode = pRightNode;
1543
1544                     pRightNode->parentLink = NULL;
1545                 }
1546
1547                 pRightNode->parentLink = pParentNode;
1548             }
1549
1550             if( pLeftNode != NULL)
1551             {
1552
1553                 // To connect the left node, we must walk the chain of the
1554                 // right nodes left side until we reach the end.
1555                 // At the end attach the leftNode
1556                 if( pRightNode != NULL)
1557                 {
1558
1559                     pCurrentNode = pRightNode;
1560
1561                     while( pCurrentNode->leftLink != NULL)
1562                     {
1563
1564                         pCurrentNode = (AFSBTreeEntry *)pCurrentNode->leftLink;
1565                     }
1566
1567                     pCurrentNode->leftLink = pLeftNode;
1568
1569                     pLeftNode->parentLink = pCurrentNode;
1570                 }
1571                 else
1572                 {
1573
1574                     if( pParentNode != NULL)
1575                     {
1576
1577                         // This is where we have a left node with no right node.
1578                         // So, attach the left node to the parent of
1579                         // the removed nodes branch
1580                         if( pParentNode->rightLink == FileIDEntry)
1581                         {
1582
1583                             pParentNode->rightLink = pLeftNode;
1584                         }
1585                         else
1586                         {
1587
1588                             pParentNode->leftLink = pLeftNode;
1589                         }
1590
1591                         pLeftNode->parentLink = pParentNode;
1592                     }
1593                     else
1594                     {
1595
1596                         *TopNode = pLeftNode;
1597
1598                         pLeftNode->parentLink = NULL;
1599                     }
1600                 }
1601             }
1602         }
1603
1604         //
1605         // Cleanup the just removed node
1606         //
1607
1608         FileIDEntry->leftLink = NULL;
1609         FileIDEntry->parentLink = NULL;
1610         FileIDEntry->rightLink = NULL;
1611
1612         ntStatus = STATUS_SUCCESS;
1613     }
1614
1615     return ntStatus;
1616 }