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 *pEntry = NULL;
49 AFSDirectoryCB *pCurrentEntry = NULL;
51 pCurrentEntry = RootNode;
59 // If the rootnode passed is null then the directory is empty
65 try_return( ntStatus = STATUS_INVALID_PARAMETER);
69 // If the requestor is looking for the root node itself, then return it.
72 if( RootNode->CaseSensitiveTreeEntry.HashIndex == Index)
77 try_return( ntStatus);
81 // Loop through the nodes in the tree
84 while( pCurrentEntry != NULL)
88 // Greater values are to the right link.
91 if( Index > pCurrentEntry->CaseSensitiveTreeEntry.HashIndex)
95 // Go to the next RIGHT entry, if there is one
98 if( pCurrentEntry->CaseSensitiveTreeEntry.rightLink != NULL)
101 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseSensitiveTreeEntry.rightLink;
107 // Came to the end of the branch so bail
110 pCurrentEntry = NULL;
115 else if( Index < pCurrentEntry->CaseSensitiveTreeEntry.HashIndex)
119 // Go to the next LEFT entry, if one exists
122 if( pCurrentEntry->CaseSensitiveTreeEntry.leftLink != NULL)
125 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseSensitiveTreeEntry.leftLink;
131 // End of the branch ...
134 pCurrentEntry = NULL;
146 *DirEntry = pCurrentEntry;
161 AFSLocateCaseInsensitiveDirEntry( IN AFSDirectoryCB *RootNode,
163 IN OUT AFSDirectoryCB **DirEntry)
166 NTSTATUS ntStatus = STATUS_SUCCESS;
167 AFSDirectoryCB *pEntry = NULL;
168 AFSDirectoryCB *pCurrentEntry = NULL;
170 pCurrentEntry = RootNode;
178 // If the rootnode passed is null then the directory is empty
181 if( RootNode == NULL)
184 try_return( ntStatus = STATUS_INVALID_PARAMETER);
188 // If the requestor is looking for the root node itself, then return it.
191 if( RootNode->CaseInsensitiveTreeEntry.HashIndex == Index)
194 *DirEntry = RootNode;
196 try_return( ntStatus);
200 // Loop through the nodes in the tree
203 while( pCurrentEntry != NULL)
207 // Greater values are to the right link.
210 if( Index > pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
214 // Go to the next RIGHT entry, if there is one
217 if( pCurrentEntry->CaseInsensitiveTreeEntry.rightLink != NULL)
220 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.rightLink;
226 // Came to the end of the branch so bail
229 pCurrentEntry = NULL;
234 else if( Index < pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
238 // Go to the next LEFT entry, if one exists
241 if( pCurrentEntry->CaseInsensitiveTreeEntry.leftLink != NULL)
244 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.leftLink;
250 // End of the branch ...
253 pCurrentEntry = NULL;
265 *DirEntry = pCurrentEntry;
280 AFSInsertCaseSensitiveDirEntry( IN AFSDirectoryCB *RootNode,
281 IN AFSDirectoryCB *DirEntry)
284 NTSTATUS ntStatus = STATUS_SUCCESS;
285 AFSDirectoryCB *pCurrentEntry = NULL;
287 pCurrentEntry = RootNode;
293 // If we have no root node then we can;t start the search.
296 if( pCurrentEntry == NULL)
299 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
300 AFS_TRACE_LEVEL_WARNING,
301 "AFSInsertCaseSensitiveDirEntry Invalid root node\n");
303 try_return( ntStatus = STATUS_UNSUCCESSFUL);
307 // Locate the branch end to insert the node
310 while( pCurrentEntry != NULL)
314 // Greater vlued indices are to the right link
317 if( DirEntry->CaseSensitiveTreeEntry.HashIndex > pCurrentEntry->CaseSensitiveTreeEntry.HashIndex)
321 // Go to the next RIGHT entry, if it exists
324 if( pCurrentEntry->CaseSensitiveTreeEntry.rightLink != NULL)
326 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseSensitiveTreeEntry.rightLink;
332 // Located the end of the branch line so insert the node
335 pCurrentEntry->CaseSensitiveTreeEntry.rightLink = (void *)DirEntry;
337 DirEntry->CaseSensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
342 else if( DirEntry->CaseSensitiveTreeEntry.HashIndex < pCurrentEntry->CaseSensitiveTreeEntry.HashIndex)
346 // Go to the next LEFT entry, if it exists
349 if( pCurrentEntry->CaseSensitiveTreeEntry.leftLink != NULL)
351 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseSensitiveTreeEntry.leftLink;
357 // Located the branch line end so insert the node here
360 pCurrentEntry->CaseSensitiveTreeEntry.leftLink = (void *)DirEntry;
362 DirEntry->CaseSensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
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);
377 ntStatus = STATUS_UNSUCCESSFUL;
392 AFSInsertCaseInsensitiveDirEntry( IN AFSDirectoryCB *RootNode,
393 IN AFSDirectoryCB *DirEntry)
396 NTSTATUS ntStatus = STATUS_SUCCESS;
397 AFSDirectoryCB *pCurrentEntry = NULL;
399 pCurrentEntry = RootNode;
405 // If we have no root node then we can;t start the search.
408 if( pCurrentEntry == NULL)
411 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
412 AFS_TRACE_LEVEL_WARNING,
413 "AFSInsertCaseInsensitiveDirEntry Invalid root node\n");
415 try_return( ntStatus = STATUS_UNSUCCESSFUL);
419 // Locate the branch end to insert the node
422 while( pCurrentEntry != NULL)
426 // Greater vlued indices are to the right link
429 if( DirEntry->CaseInsensitiveTreeEntry.HashIndex > pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
433 // Go to the next RIGHT entry, if it exists
436 if( pCurrentEntry->CaseInsensitiveTreeEntry.rightLink != NULL)
438 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.rightLink;
444 // Located the end of the branch line so insert the node
447 pCurrentEntry->CaseInsensitiveTreeEntry.rightLink = (void *)DirEntry;
449 DirEntry->CaseInsensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
451 SetFlag( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
456 else if( DirEntry->CaseInsensitiveTreeEntry.HashIndex < pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
460 // Go to the next LEFT entry, if it exists
463 if( pCurrentEntry->CaseInsensitiveTreeEntry.leftLink != NULL)
465 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.leftLink;
471 // Located the branch line end so insert the node here
474 pCurrentEntry->CaseInsensitiveTreeEntry.leftLink = (void *)DirEntry;
476 DirEntry->CaseInsensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
478 SetFlag( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
487 // Inser the the entry at the end of the insensitive list
490 while( pCurrentEntry->CaseInsensitiveList.fLink != NULL)
493 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveList.fLink;
496 pCurrentEntry->CaseInsensitiveList.fLink = (void *)DirEntry;
498 DirEntry->CaseInsensitiveList.bLink = (void *)pCurrentEntry;
513 AFSRemoveCaseSensitiveDirEntry( IN AFSDirectoryCB **RootNode,
514 IN AFSDirectoryCB *DirEntry)
517 NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
518 AFSDirectoryCB *pRightNode = NULL;
519 AFSDirectoryCB *pLeftNode = NULL;
520 AFSDirectoryCB *pCurrentNode = NULL;
521 AFSDirectoryCB *pParentNode = NULL;
523 pRightNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.rightLink;
524 pLeftNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.leftLink;
525 pParentNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.parentLink;
530 if( (pRightNode == NULL) && (pLeftNode == NULL))
533 if( pParentNode != NULL)
536 if( pParentNode->CaseSensitiveTreeEntry.leftLink == DirEntry)
539 pParentNode->CaseSensitiveTreeEntry.leftLink = NULL;
544 pParentNode->CaseSensitiveTreeEntry.rightLink = NULL;
551 // Removing the top node
560 if( pRightNode != NULL)
563 if( pParentNode != NULL)
566 // Replace the parent node where this entry was.
567 if( pParentNode->CaseSensitiveTreeEntry.rightLink == DirEntry)
570 pParentNode->CaseSensitiveTreeEntry.rightLink = pRightNode;
575 pParentNode->CaseSensitiveTreeEntry.leftLink = pRightNode;
581 *RootNode = pRightNode;
583 pRightNode->CaseSensitiveTreeEntry.parentLink = NULL;
586 pRightNode->CaseSensitiveTreeEntry.parentLink = pParentNode;
589 if( pLeftNode != NULL)
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)
598 pCurrentNode = pRightNode;
600 while( pCurrentNode->CaseSensitiveTreeEntry.leftLink != NULL)
603 pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseSensitiveTreeEntry.leftLink;
606 pCurrentNode->CaseSensitiveTreeEntry.leftLink = pLeftNode;
608 pLeftNode->CaseSensitiveTreeEntry.parentLink = pCurrentNode;
613 if( pParentNode != NULL)
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)
622 pParentNode->CaseSensitiveTreeEntry.rightLink = pLeftNode;
627 pParentNode->CaseSensitiveTreeEntry.leftLink = pLeftNode;
630 pLeftNode->CaseSensitiveTreeEntry.parentLink = pParentNode;
635 *RootNode = pLeftNode;
637 pLeftNode->CaseSensitiveTreeEntry.parentLink = NULL;
644 // Cleanup the just removed node
647 DirEntry->CaseSensitiveTreeEntry.leftLink = NULL;
648 DirEntry->CaseSensitiveTreeEntry.parentLink = NULL;
649 DirEntry->CaseSensitiveTreeEntry.rightLink = NULL;
651 ntStatus = STATUS_SUCCESS;
658 AFSRemoveCaseInsensitiveDirEntry( IN AFSDirectoryCB **RootNode,
659 IN AFSDirectoryCB *DirEntry)
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;
669 pRightNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.rightLink;
670 pLeftNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.leftLink;
671 pParentNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.parentLink;
677 // If this is not a head of list entry then just update the pointers for it
680 if( !BooleanFlagOn( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD))
683 ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.bLink)->CaseInsensitiveList.fLink = DirEntry->CaseInsensitiveList.fLink;
685 if( DirEntry->CaseInsensitiveList.fLink != NULL)
688 ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink)->CaseInsensitiveList.bLink = DirEntry->CaseInsensitiveList.bLink;
691 try_return( ntStatus);
693 else if( DirEntry->CaseInsensitiveList.fLink != NULL)
697 // Removing the head of a list of entries so just update pointers
700 pNewHeadEntry = (AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink;
702 if( pParentNode != NULL)
705 if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
707 pParentNode->CaseInsensitiveTreeEntry.rightLink = (void *)pNewHeadEntry;
711 pParentNode->CaseInsensitiveTreeEntry.leftLink = (void *)pNewHeadEntry;
715 if( pRightNode != NULL)
718 pRightNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
721 if( pLeftNode != NULL)
724 pLeftNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
727 pNewHeadEntry->CaseInsensitiveList.bLink = NULL;
729 pNewHeadEntry->CaseInsensitiveTreeEntry.parentLink = pParentNode;
731 pNewHeadEntry->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
733 pNewHeadEntry->CaseInsensitiveTreeEntry.rightLink = pRightNode;
735 SetFlag( ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink)->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
737 try_return( ntStatus);
740 if( (pRightNode == NULL) && (pLeftNode == NULL))
743 if( pParentNode != NULL)
746 if( pParentNode->CaseInsensitiveTreeEntry.leftLink == DirEntry)
749 pParentNode->CaseInsensitiveTreeEntry.leftLink = NULL;
754 pParentNode->CaseInsensitiveTreeEntry.rightLink = NULL;
761 // Removing the top node
770 if( pRightNode != NULL)
773 if( pParentNode != NULL)
776 // Replace the parent node where this entry was.
777 if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
780 pParentNode->CaseInsensitiveTreeEntry.rightLink = pRightNode;
785 pParentNode->CaseInsensitiveTreeEntry.leftLink = pRightNode;
791 *RootNode = pRightNode;
793 pRightNode->CaseInsensitiveTreeEntry.parentLink = NULL;
796 pRightNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
799 if( pLeftNode != NULL)
802 // To connect the left node, we must walk the chain of the
803 // right nodes left side until we reach the end.
804 // At the end attach the leftNode
805 if( pRightNode != NULL)
808 pCurrentNode = pRightNode;
810 while( pCurrentNode->CaseInsensitiveTreeEntry.leftLink != NULL)
813 pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseInsensitiveTreeEntry.leftLink;
816 pCurrentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
818 pLeftNode->CaseInsensitiveTreeEntry.parentLink = pCurrentNode;
823 if( pParentNode != NULL)
826 // This is where we have a left node with no right node.
827 // So, attach the left node to the parent of
828 // the removed nodes branch
829 if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
832 pParentNode->CaseInsensitiveTreeEntry.rightLink = pLeftNode;
837 pParentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
840 pLeftNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
845 *RootNode = pLeftNode;
847 pLeftNode->CaseInsensitiveTreeEntry.parentLink = NULL;
856 // Cleanup the just removed node
859 DirEntry->CaseInsensitiveTreeEntry.leftLink = NULL;
860 DirEntry->CaseInsensitiveTreeEntry.parentLink = NULL;
861 DirEntry->CaseInsensitiveTreeEntry.rightLink = NULL;
863 DirEntry->CaseInsensitiveList.bLink = NULL;
864 DirEntry->CaseInsensitiveList.fLink = NULL;
866 ntStatus = STATUS_SUCCESS;
873 AFSLocateShortNameDirEntry( IN AFSDirectoryCB *RootNode,
875 IN OUT AFSDirectoryCB **DirEntry)
878 NTSTATUS ntStatus = STATUS_SUCCESS;
879 AFSDirectoryCB *pEntry = NULL;
880 AFSDirectoryCB *pCurrentEntry = NULL;
882 pCurrentEntry = RootNode;
890 // If the rootnode passed is null then the directory is empty
893 if( RootNode == NULL)
896 try_return( ntStatus = STATUS_INVALID_PARAMETER);
900 // If the requestor is looking for the root node itself, then return it.
903 if( RootNode->Type.Data.ShortNameTreeEntry.HashIndex == Index)
906 *DirEntry = RootNode;
908 try_return( ntStatus);
912 // Loop through the nodes in the tree
915 while( pCurrentEntry != NULL)
919 // Greater values are to the right link.
922 if( Index > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
926 // Go to the next RIGHT entry, if there is one
929 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
932 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
938 // Came to the end of the branch so bail
941 pCurrentEntry = NULL;
946 else if( Index < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
950 // Go to the next LEFT entry, if one exists
953 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
956 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
962 // End of the branch ...
965 pCurrentEntry = NULL;
977 *DirEntry = pCurrentEntry;
992 AFSInsertShortNameDirEntry( IN AFSDirectoryCB *RootNode,
993 IN AFSDirectoryCB *DirEntry)
996 NTSTATUS ntStatus = STATUS_SUCCESS;
997 AFSDirectoryCB *pCurrentEntry = NULL;
999 pCurrentEntry = RootNode;
1005 // If we have no root node then we can;t start the search.
1008 if( pCurrentEntry == NULL)
1011 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1012 AFS_TRACE_LEVEL_WARNING,
1013 "AFSInsertShortNameDirEntry Invalid root node\n");
1015 try_return( ntStatus = STATUS_UNSUCCESSFUL);
1019 // Locate the branch end to insert the node
1022 while( pCurrentEntry != NULL)
1026 // Greater valued indices are to the right link
1029 if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1033 // Go to the next RIGHT entry, if it exists
1036 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
1038 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
1044 // Located the end of the branch line so insert the node
1047 pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink = (void *)DirEntry;
1049 DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1054 else if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1058 // Go to the next LEFT entry, if it exists
1061 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1063 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
1069 // Located the branch line end so insert the node here
1072 pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink = (void *)DirEntry;
1074 DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1095 AFSRemoveShortNameDirEntry( IN AFSDirectoryCB **RootNode,
1096 IN AFSDirectoryCB *DirEntry)
1099 NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1100 AFSDirectoryCB *pRightNode = NULL;
1101 AFSDirectoryCB *pLeftNode = NULL;
1102 AFSDirectoryCB *pCurrentNode = NULL;
1103 AFSDirectoryCB *pParentNode = NULL;
1105 pRightNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.rightLink;
1106 pLeftNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.leftLink;
1107 pParentNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.parentLink;
1112 if( (pRightNode == NULL) && (pLeftNode == NULL))
1115 if( pParentNode != NULL)
1118 if( pParentNode->Type.Data.ShortNameTreeEntry.leftLink == DirEntry)
1121 pParentNode->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1126 pParentNode->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1133 // Removing the top node
1142 if( pRightNode != NULL)
1145 if( pParentNode != NULL)
1148 // Replace the parent node where this entry was.
1149 if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1152 pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pRightNode;
1157 pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pRightNode;
1163 *RootNode = pRightNode;
1165 pRightNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1168 pRightNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1171 if( pLeftNode != NULL)
1174 // To connect the left node, we must walk the chain of the
1175 // right nodes left side until we reach the end.
1176 // At the end attach the leftNode
1177 if( pRightNode != NULL)
1180 pCurrentNode = pRightNode;
1182 while( pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1185 pCurrentNode = (AFSDirectoryCB *)pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink;
1188 pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1190 pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pCurrentNode;
1195 if( pParentNode != NULL)
1198 // This is where we have a left node with no right node.
1199 // So, attach the left node to the parent of
1200 // the removed nodes branch
1201 if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1204 pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pLeftNode;
1209 pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1212 pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1217 *RootNode = pLeftNode;
1219 pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1226 // Cleanup the just removed node
1229 DirEntry->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1230 DirEntry->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1231 DirEntry->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1233 ntStatus = STATUS_SUCCESS;
1240 AFSLocateHashEntry( IN AFSBTreeEntry *TopNode,
1241 IN ULONGLONG HashIndex,
1242 IN OUT AFSBTreeEntry **TreeEntry)
1245 NTSTATUS ntStatus = STATUS_SUCCESS;
1246 AFSBTreeEntry *pEntry = NULL;
1247 AFSBTreeEntry *pCurrentEntry = NULL;
1249 pCurrentEntry = TopNode;
1255 // If the rootnode passed is null then the directory is empty
1258 if( TopNode == NULL)
1261 try_return( ntStatus = STATUS_INVALID_PARAMETER);
1265 // If the requestor is looking for the root node itself, then return it.
1268 if( TopNode->HashIndex == HashIndex)
1271 *TreeEntry = TopNode;
1273 try_return( ntStatus);
1277 // Loop through the nodes in the tree
1280 while( pCurrentEntry != NULL)
1284 // Greater values are to the right link.
1287 if( HashIndex > pCurrentEntry->HashIndex)
1291 // Go to the next RIGHT entry, if there is one
1294 if( pCurrentEntry->rightLink != NULL)
1297 pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1303 // Came to the end of the branch so bail
1306 pCurrentEntry = NULL;
1311 else if( HashIndex < pCurrentEntry->HashIndex)
1315 // Go to the next LEFT entry, if one exists
1318 if( pCurrentEntry->leftLink != NULL)
1321 pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1327 // End of the branch ...
1330 pCurrentEntry = NULL;
1342 *TreeEntry = pCurrentEntry;
1357 AFSInsertHashEntry( IN AFSBTreeEntry *TopNode,
1358 IN AFSBTreeEntry *FileIDEntry)
1361 NTSTATUS ntStatus = STATUS_SUCCESS;
1362 AFSBTreeEntry *pCurrentEntry = NULL;
1364 pCurrentEntry = TopNode;
1370 // If we have no root node then we can;t start the search.
1373 if( pCurrentEntry == NULL)
1376 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1377 AFS_TRACE_LEVEL_WARNING,
1378 "AFSInsertHashEntry Invalid root node\n");
1380 try_return( ntStatus = STATUS_UNSUCCESSFUL);
1384 // Locate the branch end to insert the node
1387 while( pCurrentEntry != NULL)
1391 // Greater vlued indices are to the right link
1394 if( FileIDEntry->HashIndex > pCurrentEntry->HashIndex)
1398 // Go to the next RIGHT entry, if it exists
1401 if( pCurrentEntry->rightLink != NULL)
1403 pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1409 // Located the end of the branch line so insert the node
1412 pCurrentEntry->rightLink = (void *)FileIDEntry;
1414 FileIDEntry->parentLink = (void *)pCurrentEntry;
1419 else if( FileIDEntry->HashIndex < pCurrentEntry->HashIndex)
1423 // Go to the next LEFT entry, if it exists
1426 if( pCurrentEntry->leftLink != NULL)
1428 pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1434 // Located the branch line end so insert the node here
1437 pCurrentEntry->leftLink = (void *)FileIDEntry;
1439 FileIDEntry->parentLink = (void *)pCurrentEntry;
1447 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1448 AFS_TRACE_LEVEL_WARNING,
1449 "AFSInsertHashEntry Attempt to re-insert a CRC %I64X\n",
1450 FileIDEntry->HashIndex);
1454 ntStatus = STATUS_UNSUCCESSFUL;
1469 AFSRemoveHashEntry( IN AFSBTreeEntry **TopNode,
1470 IN AFSBTreeEntry *FileIDEntry)
1473 NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1474 AFSBTreeEntry *pRightNode = NULL;
1475 AFSBTreeEntry *pLeftNode = NULL;
1476 AFSBTreeEntry *pCurrentNode = NULL;
1477 AFSBTreeEntry *pParentNode = NULL;
1479 pRightNode = (AFSBTreeEntry *)FileIDEntry->rightLink;
1480 pLeftNode = (AFSBTreeEntry *)FileIDEntry->leftLink;
1481 pParentNode = (AFSBTreeEntry *)FileIDEntry->parentLink;
1486 if( (pRightNode == NULL) && (pLeftNode == NULL))
1489 if( pParentNode != NULL)
1492 if( pParentNode->leftLink == FileIDEntry)
1495 pParentNode->leftLink = NULL;
1500 pParentNode->rightLink = NULL;
1507 // Removing the top node
1516 if( pRightNode != NULL)
1519 if( pParentNode != NULL)
1522 // Replace the parent node where this entry was.
1523 if( pParentNode->rightLink == FileIDEntry)
1526 pParentNode->rightLink = pRightNode;
1531 pParentNode->leftLink = pRightNode;
1537 *TopNode = pRightNode;
1539 pRightNode->parentLink = NULL;
1542 pRightNode->parentLink = pParentNode;
1545 if( pLeftNode != NULL)
1548 // To connect the left node, we must walk the chain of the
1549 // right nodes left side until we reach the end.
1550 // At the end attach the leftNode
1551 if( pRightNode != NULL)
1554 pCurrentNode = pRightNode;
1556 while( pCurrentNode->leftLink != NULL)
1559 pCurrentNode = (AFSBTreeEntry *)pCurrentNode->leftLink;
1562 pCurrentNode->leftLink = pLeftNode;
1564 pLeftNode->parentLink = pCurrentNode;
1569 if( pParentNode != NULL)
1572 // This is where we have a left node with no right node.
1573 // So, attach the left node to the parent of
1574 // the removed nodes branch
1575 if( pParentNode->rightLink == FileIDEntry)
1578 pParentNode->rightLink = pLeftNode;
1583 pParentNode->leftLink = pLeftNode;
1586 pLeftNode->parentLink = pParentNode;
1591 *TopNode = pLeftNode;
1593 pLeftNode->parentLink = NULL;
1600 // Cleanup the just removed node
1603 FileIDEntry->leftLink = NULL;
1604 FileIDEntry->parentLink = NULL;
1605 FileIDEntry->rightLink = NULL;
1607 ntStatus = STATUS_SUCCESS;