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