2 * Copyright (c) 2008, 2009, 2010, 2011 Kernel Drivers, LLC.
3 * Copyright (c) 2009, 2010, 2011 Your File System, Inc.
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
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
14 * this list of conditions and the following disclaimer in the
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.
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.
36 // File: AFSBTreeSupport.cpp
39 #include "AFSCommon.h"
42 AFSLocateCaseSensitiveDirEntry( IN AFSDirectoryCB *RootNode,
44 IN OUT AFSDirectoryCB **DirEntry)
47 NTSTATUS ntStatus = STATUS_SUCCESS;
48 AFSDirectoryCB *pCurrentEntry = NULL;
50 pCurrentEntry = RootNode;
58 // If the rootnode passed is null then the directory is empty
64 try_return( ntStatus = STATUS_INVALID_PARAMETER);
68 // If the requestor is looking for the root node itself, then return it.
71 if( RootNode->CaseSensitiveTreeEntry.HashIndex == Index)
76 try_return( ntStatus);
80 // Loop through the nodes in the tree
83 while( pCurrentEntry != NULL)
87 // Greater values are to the right link.
90 if( Index > pCurrentEntry->CaseSensitiveTreeEntry.HashIndex)
94 // Go to the next RIGHT entry, if there is one
97 if( pCurrentEntry->CaseSensitiveTreeEntry.rightLink != NULL)
100 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseSensitiveTreeEntry.rightLink;
106 // Came to the end of the branch so bail
109 pCurrentEntry = NULL;
114 else if( Index < pCurrentEntry->CaseSensitiveTreeEntry.HashIndex)
118 // Go to the next LEFT entry, if one exists
121 if( pCurrentEntry->CaseSensitiveTreeEntry.leftLink != NULL)
124 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseSensitiveTreeEntry.leftLink;
130 // End of the branch ...
133 pCurrentEntry = NULL;
145 *DirEntry = pCurrentEntry;
160 AFSLocateCaseInsensitiveDirEntry( IN AFSDirectoryCB *RootNode,
162 IN OUT AFSDirectoryCB **DirEntry)
165 NTSTATUS ntStatus = STATUS_SUCCESS;
166 AFSDirectoryCB *pCurrentEntry = NULL;
168 pCurrentEntry = RootNode;
176 // If the rootnode passed is null then the directory is empty
179 if( RootNode == NULL)
182 try_return( ntStatus = STATUS_INVALID_PARAMETER);
186 // If the requestor is looking for the root node itself, then return it.
189 if( RootNode->CaseInsensitiveTreeEntry.HashIndex == Index)
192 *DirEntry = RootNode;
194 try_return( ntStatus);
198 // Loop through the nodes in the tree
201 while( pCurrentEntry != NULL)
205 // Greater values are to the right link.
208 if( Index > pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
212 // Go to the next RIGHT entry, if there is one
215 if( pCurrentEntry->CaseInsensitiveTreeEntry.rightLink != NULL)
218 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.rightLink;
224 // Came to the end of the branch so bail
227 pCurrentEntry = NULL;
232 else if( Index < pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
236 // Go to the next LEFT entry, if one exists
239 if( pCurrentEntry->CaseInsensitiveTreeEntry.leftLink != NULL)
242 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.leftLink;
248 // End of the branch ...
251 pCurrentEntry = NULL;
263 *DirEntry = pCurrentEntry;
278 AFSInsertCaseSensitiveDirEntry( IN AFSDirectoryCB *RootNode,
279 IN AFSDirectoryCB *DirEntry)
282 NTSTATUS ntStatus = STATUS_SUCCESS;
283 AFSDirectoryCB *pCurrentEntry = NULL;
285 pCurrentEntry = RootNode;
291 // If we have no root node then we can;t start the search.
294 if( pCurrentEntry == NULL)
297 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
298 AFS_TRACE_LEVEL_WARNING,
299 "AFSInsertCaseSensitiveDirEntry Invalid root node\n");
301 try_return( ntStatus = STATUS_UNSUCCESSFUL);
305 // Locate the branch end to insert the node
308 while( pCurrentEntry != NULL)
312 // Greater vlued indices are to the right link
315 if( DirEntry->CaseSensitiveTreeEntry.HashIndex > pCurrentEntry->CaseSensitiveTreeEntry.HashIndex)
319 // Go to the next RIGHT entry, if it exists
322 if( pCurrentEntry->CaseSensitiveTreeEntry.rightLink != NULL)
324 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseSensitiveTreeEntry.rightLink;
330 // Located the end of the branch line so insert the node
333 pCurrentEntry->CaseSensitiveTreeEntry.rightLink = (void *)DirEntry;
335 DirEntry->CaseSensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
340 else if( DirEntry->CaseSensitiveTreeEntry.HashIndex < pCurrentEntry->CaseSensitiveTreeEntry.HashIndex)
344 // Go to the next LEFT entry, if it exists
347 if( pCurrentEntry->CaseSensitiveTreeEntry.leftLink != NULL)
349 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseSensitiveTreeEntry.leftLink;
355 // Located the branch line end so insert the node here
358 pCurrentEntry->CaseSensitiveTreeEntry.leftLink = (void *)DirEntry;
360 DirEntry->CaseSensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
368 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
369 AFS_TRACE_LEVEL_VERBOSE,
370 "AFSInsertCaseSensitiveDirEntry Collision with DE %p for %wZ\n",
372 &pCurrentEntry->NameInformation.FileName);
374 ntStatus = STATUS_UNSUCCESSFUL;
389 AFSInsertCaseInsensitiveDirEntry( IN AFSDirectoryCB *RootNode,
390 IN AFSDirectoryCB *DirEntry)
393 NTSTATUS ntStatus = STATUS_SUCCESS;
394 AFSDirectoryCB *pCurrentEntry = NULL;
396 pCurrentEntry = RootNode;
402 // If we have no root node then we can;t start the search.
405 if( pCurrentEntry == NULL)
408 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
409 AFS_TRACE_LEVEL_WARNING,
410 "AFSInsertCaseInsensitiveDirEntry Invalid root node\n");
412 try_return( ntStatus = STATUS_UNSUCCESSFUL);
416 // Locate the branch end to insert the node
419 while( pCurrentEntry != NULL)
423 // Greater vlued indices are to the right link
426 if( DirEntry->CaseInsensitiveTreeEntry.HashIndex > pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
430 // Go to the next RIGHT entry, if it exists
433 if( pCurrentEntry->CaseInsensitiveTreeEntry.rightLink != NULL)
435 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.rightLink;
441 // Located the end of the branch line so insert the node
444 pCurrentEntry->CaseInsensitiveTreeEntry.rightLink = (void *)DirEntry;
446 DirEntry->CaseInsensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
448 SetFlag( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
453 else if( DirEntry->CaseInsensitiveTreeEntry.HashIndex < pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
457 // Go to the next LEFT entry, if it exists
460 if( pCurrentEntry->CaseInsensitiveTreeEntry.leftLink != NULL)
462 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.leftLink;
468 // Located the branch line end so insert the node here
471 pCurrentEntry->CaseInsensitiveTreeEntry.leftLink = (void *)DirEntry;
473 DirEntry->CaseInsensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
475 SetFlag( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
484 // Insert the the entry at the end of the insensitive list
487 while( pCurrentEntry->CaseInsensitiveList.fLink != NULL)
490 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveList.fLink;
493 pCurrentEntry->CaseInsensitiveList.fLink = (void *)DirEntry;
495 DirEntry->CaseInsensitiveList.bLink = (void *)pCurrentEntry;
510 AFSRemoveCaseSensitiveDirEntry( IN AFSDirectoryCB **RootNode,
511 IN AFSDirectoryCB *DirEntry)
514 NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
515 AFSDirectoryCB *pRightNode = NULL;
516 AFSDirectoryCB *pLeftNode = NULL;
517 AFSDirectoryCB *pCurrentNode = NULL;
518 AFSDirectoryCB *pParentNode = NULL;
520 pRightNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.rightLink;
521 pLeftNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.leftLink;
522 pParentNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.parentLink;
527 if( (pRightNode == NULL) && (pLeftNode == NULL))
530 if( pParentNode != NULL)
533 if( pParentNode->CaseSensitiveTreeEntry.leftLink == DirEntry)
536 pParentNode->CaseSensitiveTreeEntry.leftLink = NULL;
541 pParentNode->CaseSensitiveTreeEntry.rightLink = NULL;
548 // Removing the top node
557 if( pRightNode != NULL)
560 if( pParentNode != NULL)
563 // Replace the parent node where this entry was.
564 if( pParentNode->CaseSensitiveTreeEntry.rightLink == DirEntry)
567 pParentNode->CaseSensitiveTreeEntry.rightLink = pRightNode;
572 pParentNode->CaseSensitiveTreeEntry.leftLink = pRightNode;
578 *RootNode = pRightNode;
580 pRightNode->CaseSensitiveTreeEntry.parentLink = NULL;
583 pRightNode->CaseSensitiveTreeEntry.parentLink = pParentNode;
586 if( pLeftNode != NULL)
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)
595 pCurrentNode = pRightNode;
597 while( pCurrentNode->CaseSensitiveTreeEntry.leftLink != NULL)
600 pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseSensitiveTreeEntry.leftLink;
603 pCurrentNode->CaseSensitiveTreeEntry.leftLink = pLeftNode;
605 pLeftNode->CaseSensitiveTreeEntry.parentLink = pCurrentNode;
610 if( pParentNode != NULL)
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)
619 pParentNode->CaseSensitiveTreeEntry.rightLink = pLeftNode;
624 pParentNode->CaseSensitiveTreeEntry.leftLink = pLeftNode;
627 pLeftNode->CaseSensitiveTreeEntry.parentLink = pParentNode;
632 *RootNode = pLeftNode;
634 pLeftNode->CaseSensitiveTreeEntry.parentLink = NULL;
641 // Cleanup the just removed node
644 DirEntry->CaseSensitiveTreeEntry.leftLink = NULL;
645 DirEntry->CaseSensitiveTreeEntry.parentLink = NULL;
646 DirEntry->CaseSensitiveTreeEntry.rightLink = NULL;
648 ntStatus = STATUS_SUCCESS;
655 AFSRemoveCaseInsensitiveDirEntry( IN AFSDirectoryCB **RootNode,
656 IN AFSDirectoryCB *DirEntry)
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;
666 pRightNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.rightLink;
667 pLeftNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.leftLink;
668 pParentNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.parentLink;
674 // If this is not a head of list entry then just update the pointers for it
677 if( !BooleanFlagOn( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD))
680 ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.bLink)->CaseInsensitiveList.fLink = DirEntry->CaseInsensitiveList.fLink;
682 if( DirEntry->CaseInsensitiveList.fLink != NULL)
685 ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink)->CaseInsensitiveList.bLink = DirEntry->CaseInsensitiveList.bLink;
688 try_return( ntStatus);
691 if( DirEntry->CaseInsensitiveList.fLink != NULL)
695 // Removing the head of a list of entries so just update pointers
698 pNewHeadEntry = (AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink;
700 if( pParentNode != NULL)
703 if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
705 pParentNode->CaseInsensitiveTreeEntry.rightLink = (void *)pNewHeadEntry;
709 pParentNode->CaseInsensitiveTreeEntry.leftLink = (void *)pNewHeadEntry;
714 *RootNode = pNewHeadEntry;
717 if( pRightNode != NULL)
720 pRightNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
723 if( pLeftNode != NULL)
726 pLeftNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
729 pNewHeadEntry->CaseInsensitiveList.bLink = NULL;
731 pNewHeadEntry->CaseInsensitiveTreeEntry.parentLink = pParentNode;
733 pNewHeadEntry->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
735 pNewHeadEntry->CaseInsensitiveTreeEntry.rightLink = pRightNode;
737 SetFlag( pNewHeadEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
739 try_return( ntStatus);
742 if( (pRightNode == NULL) && (pLeftNode == NULL))
745 if( pParentNode != NULL)
748 if( pParentNode->CaseInsensitiveTreeEntry.leftLink == DirEntry)
751 pParentNode->CaseInsensitiveTreeEntry.leftLink = NULL;
756 pParentNode->CaseInsensitiveTreeEntry.rightLink = NULL;
763 // Removing the top node
772 if( pRightNode != NULL)
775 if( pParentNode != NULL)
778 // Replace the parent node where this entry was.
779 if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
782 pParentNode->CaseInsensitiveTreeEntry.rightLink = pRightNode;
787 pParentNode->CaseInsensitiveTreeEntry.leftLink = pRightNode;
793 *RootNode = pRightNode;
795 pRightNode->CaseInsensitiveTreeEntry.parentLink = NULL;
798 pRightNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
801 if( pLeftNode != NULL)
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)
810 pCurrentNode = pRightNode;
812 while( pCurrentNode->CaseInsensitiveTreeEntry.leftLink != NULL)
815 pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseInsensitiveTreeEntry.leftLink;
818 pCurrentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
820 pLeftNode->CaseInsensitiveTreeEntry.parentLink = pCurrentNode;
825 if( pParentNode != NULL)
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)
834 pParentNode->CaseInsensitiveTreeEntry.rightLink = pLeftNode;
839 pParentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
842 pLeftNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
847 *RootNode = pLeftNode;
849 pLeftNode->CaseInsensitiveTreeEntry.parentLink = NULL;
858 // Cleanup the just removed node
861 DirEntry->CaseInsensitiveTreeEntry.leftLink = NULL;
862 DirEntry->CaseInsensitiveTreeEntry.parentLink = NULL;
863 DirEntry->CaseInsensitiveTreeEntry.rightLink = NULL;
865 DirEntry->CaseInsensitiveList.bLink = NULL;
866 DirEntry->CaseInsensitiveList.fLink = NULL;
868 ntStatus = STATUS_SUCCESS;
875 AFSLocateShortNameDirEntry( IN AFSDirectoryCB *RootNode,
877 IN OUT AFSDirectoryCB **DirEntry)
880 NTSTATUS ntStatus = STATUS_SUCCESS;
881 AFSDirectoryCB *pCurrentEntry = NULL;
883 pCurrentEntry = RootNode;
891 // If the rootnode passed is null then the directory is empty
894 if( RootNode == NULL)
897 try_return( ntStatus = STATUS_INVALID_PARAMETER);
901 // If the requestor is looking for the root node itself, then return it.
904 if( RootNode->Type.Data.ShortNameTreeEntry.HashIndex == Index)
907 *DirEntry = RootNode;
909 try_return( ntStatus);
913 // Loop through the nodes in the tree
916 while( pCurrentEntry != NULL)
920 // Greater values are to the right link.
923 if( Index > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
927 // Go to the next RIGHT entry, if there is one
930 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
933 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
939 // Came to the end of the branch so bail
942 pCurrentEntry = NULL;
947 else if( Index < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
951 // Go to the next LEFT entry, if one exists
954 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
957 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
963 // End of the branch ...
966 pCurrentEntry = NULL;
978 *DirEntry = pCurrentEntry;
993 AFSInsertShortNameDirEntry( IN AFSDirectoryCB *RootNode,
994 IN AFSDirectoryCB *DirEntry)
997 NTSTATUS ntStatus = STATUS_SUCCESS;
998 AFSDirectoryCB *pCurrentEntry = NULL;
1000 pCurrentEntry = RootNode;
1006 // If we have no root node then we can;t start the search.
1009 if( pCurrentEntry == NULL)
1012 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1013 AFS_TRACE_LEVEL_WARNING,
1014 "AFSInsertShortNameDirEntry Invalid root node\n");
1016 try_return( ntStatus = STATUS_UNSUCCESSFUL);
1020 // Locate the branch end to insert the node
1023 while( pCurrentEntry != NULL)
1027 // Greater valued indices are to the right link
1030 if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1034 // Go to the next RIGHT entry, if it exists
1037 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
1039 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
1045 // Located the end of the branch line so insert the node
1048 pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink = (void *)DirEntry;
1050 DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1055 else if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1059 // Go to the next LEFT entry, if it exists
1062 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1064 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
1070 // Located the branch line end so insert the node here
1073 pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink = (void *)DirEntry;
1075 DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1083 ntStatus = STATUS_UNSUCCESSFUL;
1085 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1086 AFS_TRACE_LEVEL_VERBOSE,
1087 "AFSInsertShortNameDirEntry Collision with DE %p for shortname %S and %wZ\n",
1089 pCurrentEntry->NameInformation.ShortName,
1090 &pCurrentEntry->NameInformation.FileName);
1105 AFSRemoveShortNameDirEntry( IN AFSDirectoryCB **RootNode,
1106 IN AFSDirectoryCB *DirEntry)
1109 NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1110 AFSDirectoryCB *pRightNode = NULL;
1111 AFSDirectoryCB *pLeftNode = NULL;
1112 AFSDirectoryCB *pCurrentNode = NULL;
1113 AFSDirectoryCB *pParentNode = NULL;
1115 pRightNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.rightLink;
1116 pLeftNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.leftLink;
1117 pParentNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.parentLink;
1122 if( (pRightNode == NULL) && (pLeftNode == NULL))
1125 if( pParentNode != NULL)
1128 if( pParentNode->Type.Data.ShortNameTreeEntry.leftLink == DirEntry)
1131 pParentNode->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1136 pParentNode->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1143 // Removing the top node
1152 if( pRightNode != NULL)
1155 if( pParentNode != NULL)
1158 // Replace the parent node where this entry was.
1159 if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1162 pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pRightNode;
1167 pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pRightNode;
1173 *RootNode = pRightNode;
1175 pRightNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1178 pRightNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1181 if( pLeftNode != NULL)
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)
1190 pCurrentNode = pRightNode;
1192 while( pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1195 pCurrentNode = (AFSDirectoryCB *)pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink;
1198 pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1200 pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pCurrentNode;
1205 if( pParentNode != NULL)
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)
1214 pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pLeftNode;
1219 pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1222 pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1227 *RootNode = pLeftNode;
1229 pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1236 // Cleanup the just removed node
1239 DirEntry->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1240 DirEntry->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1241 DirEntry->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1243 ntStatus = STATUS_SUCCESS;
1250 AFSLocateHashEntry( IN AFSBTreeEntry *TopNode,
1251 IN ULONGLONG HashIndex,
1252 IN OUT AFSBTreeEntry **TreeEntry)
1255 NTSTATUS ntStatus = STATUS_SUCCESS;
1256 AFSBTreeEntry *pCurrentEntry = NULL;
1258 pCurrentEntry = TopNode;
1264 // If the rootnode passed is null then the directory is empty
1267 if( TopNode == NULL)
1270 try_return( ntStatus = STATUS_INVALID_PARAMETER);
1274 // If the requestor is looking for the root node itself, then return it.
1277 if( TopNode->HashIndex == HashIndex)
1280 *TreeEntry = TopNode;
1282 try_return( ntStatus);
1286 // Loop through the nodes in the tree
1289 while( pCurrentEntry != NULL)
1293 // Greater values are to the right link.
1296 if( HashIndex > pCurrentEntry->HashIndex)
1300 // Go to the next RIGHT entry, if there is one
1303 if( pCurrentEntry->rightLink != NULL)
1306 pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1312 // Came to the end of the branch so bail
1315 pCurrentEntry = NULL;
1320 else if( HashIndex < pCurrentEntry->HashIndex)
1324 // Go to the next LEFT entry, if one exists
1327 if( pCurrentEntry->leftLink != NULL)
1330 pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1336 // End of the branch ...
1339 pCurrentEntry = NULL;
1351 *TreeEntry = pCurrentEntry;
1366 AFSInsertHashEntry( IN AFSBTreeEntry *TopNode,
1367 IN AFSBTreeEntry *FileIDEntry)
1370 NTSTATUS ntStatus = STATUS_SUCCESS;
1371 AFSBTreeEntry *pCurrentEntry = NULL;
1373 pCurrentEntry = TopNode;
1379 // If we have no root node then we can;t start the search.
1382 if( pCurrentEntry == NULL)
1385 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1386 AFS_TRACE_LEVEL_WARNING,
1387 "AFSInsertHashEntry Invalid root node\n");
1389 try_return( ntStatus = STATUS_UNSUCCESSFUL);
1393 // Locate the branch end to insert the node
1396 while( pCurrentEntry != NULL)
1400 // Greater vlued indices are to the right link
1403 if( FileIDEntry->HashIndex > pCurrentEntry->HashIndex)
1407 // Go to the next RIGHT entry, if it exists
1410 if( pCurrentEntry->rightLink != NULL)
1412 pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1418 // Located the end of the branch line so insert the node
1421 pCurrentEntry->rightLink = (void *)FileIDEntry;
1423 FileIDEntry->parentLink = (void *)pCurrentEntry;
1428 else if( FileIDEntry->HashIndex < pCurrentEntry->HashIndex)
1432 // Go to the next LEFT entry, if it exists
1435 if( pCurrentEntry->leftLink != NULL)
1437 pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1443 // Located the branch line end so insert the node here
1446 pCurrentEntry->leftLink = (void *)FileIDEntry;
1448 FileIDEntry->parentLink = (void *)pCurrentEntry;
1456 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1457 AFS_TRACE_LEVEL_WARNING,
1458 "AFSInsertHashEntry Attempt to re-insert a CRC %I64X\n",
1459 FileIDEntry->HashIndex);
1461 ntStatus = STATUS_UNSUCCESSFUL;
1476 AFSRemoveHashEntry( IN AFSBTreeEntry **TopNode,
1477 IN AFSBTreeEntry *FileIDEntry)
1480 NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1481 AFSBTreeEntry *pRightNode = NULL;
1482 AFSBTreeEntry *pLeftNode = NULL;
1483 AFSBTreeEntry *pCurrentNode = NULL;
1484 AFSBTreeEntry *pParentNode = NULL;
1486 pRightNode = (AFSBTreeEntry *)FileIDEntry->rightLink;
1487 pLeftNode = (AFSBTreeEntry *)FileIDEntry->leftLink;
1488 pParentNode = (AFSBTreeEntry *)FileIDEntry->parentLink;
1493 if( (pRightNode == NULL) && (pLeftNode == NULL))
1496 if( pParentNode != NULL)
1499 if( pParentNode->leftLink == FileIDEntry)
1502 pParentNode->leftLink = NULL;
1507 pParentNode->rightLink = NULL;
1514 // Removing the top node
1523 if( pRightNode != NULL)
1526 if( pParentNode != NULL)
1529 // Replace the parent node where this entry was.
1530 if( pParentNode->rightLink == FileIDEntry)
1533 pParentNode->rightLink = pRightNode;
1538 pParentNode->leftLink = pRightNode;
1544 *TopNode = pRightNode;
1546 pRightNode->parentLink = NULL;
1549 pRightNode->parentLink = pParentNode;
1552 if( pLeftNode != NULL)
1555 // To connect the left node, we must walk the chain of the
1556 // right nodes left side until we reach the end.
1557 // At the end attach the leftNode
1558 if( pRightNode != NULL)
1561 pCurrentNode = pRightNode;
1563 while( pCurrentNode->leftLink != NULL)
1566 pCurrentNode = (AFSBTreeEntry *)pCurrentNode->leftLink;
1569 pCurrentNode->leftLink = pLeftNode;
1571 pLeftNode->parentLink = pCurrentNode;
1576 if( pParentNode != NULL)
1579 // This is where we have a left node with no right node.
1580 // So, attach the left node to the parent of
1581 // the removed nodes branch
1582 if( pParentNode->rightLink == FileIDEntry)
1585 pParentNode->rightLink = pLeftNode;
1590 pParentNode->leftLink = pLeftNode;
1593 pLeftNode->parentLink = pParentNode;
1598 *TopNode = pLeftNode;
1600 pLeftNode->parentLink = NULL;
1607 // Cleanup the just removed node
1610 FileIDEntry->leftLink = NULL;
1611 FileIDEntry->parentLink = NULL;
1612 FileIDEntry->rightLink = NULL;
1614 ntStatus = STATUS_SUCCESS;