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_VERBOSE,
372 "AFSInsertCaseSensitiveDirEntry Collision with DE %p for %wZ\n",
374 &pCurrentEntry->NameInformation.FileName);
376 ntStatus = STATUS_UNSUCCESSFUL;
391 AFSInsertCaseInsensitiveDirEntry( IN AFSDirectoryCB *RootNode,
392 IN AFSDirectoryCB *DirEntry)
395 NTSTATUS ntStatus = STATUS_SUCCESS;
396 AFSDirectoryCB *pCurrentEntry = NULL;
398 pCurrentEntry = RootNode;
404 // If we have no root node then we can;t start the search.
407 if( pCurrentEntry == NULL)
410 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
411 AFS_TRACE_LEVEL_WARNING,
412 "AFSInsertCaseInsensitiveDirEntry Invalid root node\n");
414 try_return( ntStatus = STATUS_UNSUCCESSFUL);
418 // Locate the branch end to insert the node
421 while( pCurrentEntry != NULL)
425 // Greater vlued indices are to the right link
428 if( DirEntry->CaseInsensitiveTreeEntry.HashIndex > pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
432 // Go to the next RIGHT entry, if it exists
435 if( pCurrentEntry->CaseInsensitiveTreeEntry.rightLink != NULL)
437 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.rightLink;
443 // Located the end of the branch line so insert the node
446 pCurrentEntry->CaseInsensitiveTreeEntry.rightLink = (void *)DirEntry;
448 DirEntry->CaseInsensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
450 SetFlag( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
455 else if( DirEntry->CaseInsensitiveTreeEntry.HashIndex < pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
459 // Go to the next LEFT entry, if it exists
462 if( pCurrentEntry->CaseInsensitiveTreeEntry.leftLink != NULL)
464 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.leftLink;
470 // Located the branch line end so insert the node here
473 pCurrentEntry->CaseInsensitiveTreeEntry.leftLink = (void *)DirEntry;
475 DirEntry->CaseInsensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
477 SetFlag( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
486 // Inser the the entry at the end of the insensitive list
489 while( pCurrentEntry->CaseInsensitiveList.fLink != NULL)
492 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveList.fLink;
495 pCurrentEntry->CaseInsensitiveList.fLink = (void *)DirEntry;
497 DirEntry->CaseInsensitiveList.bLink = (void *)pCurrentEntry;
512 AFSRemoveCaseSensitiveDirEntry( IN AFSDirectoryCB **RootNode,
513 IN AFSDirectoryCB *DirEntry)
516 NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
517 AFSDirectoryCB *pRightNode = NULL;
518 AFSDirectoryCB *pLeftNode = NULL;
519 AFSDirectoryCB *pCurrentNode = NULL;
520 AFSDirectoryCB *pParentNode = NULL;
522 pRightNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.rightLink;
523 pLeftNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.leftLink;
524 pParentNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.parentLink;
529 if( (pRightNode == NULL) && (pLeftNode == NULL))
532 if( pParentNode != NULL)
535 if( pParentNode->CaseSensitiveTreeEntry.leftLink == DirEntry)
538 pParentNode->CaseSensitiveTreeEntry.leftLink = NULL;
543 pParentNode->CaseSensitiveTreeEntry.rightLink = NULL;
550 // Removing the top node
559 if( pRightNode != NULL)
562 if( pParentNode != NULL)
565 // Replace the parent node where this entry was.
566 if( pParentNode->CaseSensitiveTreeEntry.rightLink == DirEntry)
569 pParentNode->CaseSensitiveTreeEntry.rightLink = pRightNode;
574 pParentNode->CaseSensitiveTreeEntry.leftLink = pRightNode;
580 *RootNode = pRightNode;
582 pRightNode->CaseSensitiveTreeEntry.parentLink = NULL;
585 pRightNode->CaseSensitiveTreeEntry.parentLink = pParentNode;
588 if( pLeftNode != NULL)
591 // To connect the left node, we must walk the chain of the
592 // right nodes left side until we reach the end.
593 // At the end attach the leftNode
594 if( pRightNode != NULL)
597 pCurrentNode = pRightNode;
599 while( pCurrentNode->CaseSensitiveTreeEntry.leftLink != NULL)
602 pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseSensitiveTreeEntry.leftLink;
605 pCurrentNode->CaseSensitiveTreeEntry.leftLink = pLeftNode;
607 pLeftNode->CaseSensitiveTreeEntry.parentLink = pCurrentNode;
612 if( pParentNode != NULL)
615 // This is where we have a left node with no right node.
616 // So, attach the left node to the parent of
617 // the removed nodes branch
618 if( pParentNode->CaseSensitiveTreeEntry.rightLink == DirEntry)
621 pParentNode->CaseSensitiveTreeEntry.rightLink = pLeftNode;
626 pParentNode->CaseSensitiveTreeEntry.leftLink = pLeftNode;
629 pLeftNode->CaseSensitiveTreeEntry.parentLink = pParentNode;
634 *RootNode = pLeftNode;
636 pLeftNode->CaseSensitiveTreeEntry.parentLink = NULL;
643 // Cleanup the just removed node
646 DirEntry->CaseSensitiveTreeEntry.leftLink = NULL;
647 DirEntry->CaseSensitiveTreeEntry.parentLink = NULL;
648 DirEntry->CaseSensitiveTreeEntry.rightLink = NULL;
650 ntStatus = STATUS_SUCCESS;
657 AFSRemoveCaseInsensitiveDirEntry( IN AFSDirectoryCB **RootNode,
658 IN AFSDirectoryCB *DirEntry)
661 NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
662 AFSDirectoryCB *pRightNode = NULL;
663 AFSDirectoryCB *pLeftNode = NULL;
664 AFSDirectoryCB *pCurrentNode = NULL;
665 AFSDirectoryCB *pParentNode = NULL;
666 AFSDirectoryCB *pNewHeadEntry = NULL;
668 pRightNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.rightLink;
669 pLeftNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.leftLink;
670 pParentNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.parentLink;
676 // If this is not a head of list entry then just update the pointers for it
679 if( !BooleanFlagOn( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD))
682 ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.bLink)->CaseInsensitiveList.fLink = DirEntry->CaseInsensitiveList.fLink;
684 if( DirEntry->CaseInsensitiveList.fLink != NULL)
687 ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink)->CaseInsensitiveList.bLink = DirEntry->CaseInsensitiveList.bLink;
690 try_return( ntStatus);
693 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;
716 *RootNode = pNewHeadEntry;
719 if( pRightNode != NULL)
722 pRightNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
725 if( pLeftNode != NULL)
728 pLeftNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
731 pNewHeadEntry->CaseInsensitiveList.bLink = NULL;
733 pNewHeadEntry->CaseInsensitiveTreeEntry.parentLink = pParentNode;
735 pNewHeadEntry->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
737 pNewHeadEntry->CaseInsensitiveTreeEntry.rightLink = pRightNode;
739 SetFlag( pNewHeadEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
741 try_return( ntStatus);
744 if( (pRightNode == NULL) && (pLeftNode == NULL))
747 if( pParentNode != NULL)
750 if( pParentNode->CaseInsensitiveTreeEntry.leftLink == DirEntry)
753 pParentNode->CaseInsensitiveTreeEntry.leftLink = NULL;
758 pParentNode->CaseInsensitiveTreeEntry.rightLink = NULL;
765 // Removing the top node
774 if( pRightNode != NULL)
777 if( pParentNode != NULL)
780 // Replace the parent node where this entry was.
781 if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
784 pParentNode->CaseInsensitiveTreeEntry.rightLink = pRightNode;
789 pParentNode->CaseInsensitiveTreeEntry.leftLink = pRightNode;
795 *RootNode = pRightNode;
797 pRightNode->CaseInsensitiveTreeEntry.parentLink = NULL;
800 pRightNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
803 if( pLeftNode != NULL)
806 // To connect the left node, we must walk the chain of the
807 // right nodes left side until we reach the end.
808 // At the end attach the leftNode
809 if( pRightNode != NULL)
812 pCurrentNode = pRightNode;
814 while( pCurrentNode->CaseInsensitiveTreeEntry.leftLink != NULL)
817 pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseInsensitiveTreeEntry.leftLink;
820 pCurrentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
822 pLeftNode->CaseInsensitiveTreeEntry.parentLink = pCurrentNode;
827 if( pParentNode != NULL)
830 // This is where we have a left node with no right node.
831 // So, attach the left node to the parent of
832 // the removed nodes branch
833 if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
836 pParentNode->CaseInsensitiveTreeEntry.rightLink = pLeftNode;
841 pParentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
844 pLeftNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
849 *RootNode = pLeftNode;
851 pLeftNode->CaseInsensitiveTreeEntry.parentLink = NULL;
860 // Cleanup the just removed node
863 DirEntry->CaseInsensitiveTreeEntry.leftLink = NULL;
864 DirEntry->CaseInsensitiveTreeEntry.parentLink = NULL;
865 DirEntry->CaseInsensitiveTreeEntry.rightLink = NULL;
867 DirEntry->CaseInsensitiveList.bLink = NULL;
868 DirEntry->CaseInsensitiveList.fLink = NULL;
870 ntStatus = STATUS_SUCCESS;
877 AFSLocateShortNameDirEntry( IN AFSDirectoryCB *RootNode,
879 IN OUT AFSDirectoryCB **DirEntry)
882 NTSTATUS ntStatus = STATUS_SUCCESS;
883 AFSDirectoryCB *pEntry = NULL;
884 AFSDirectoryCB *pCurrentEntry = NULL;
886 pCurrentEntry = RootNode;
894 // If the rootnode passed is null then the directory is empty
897 if( RootNode == NULL)
900 try_return( ntStatus = STATUS_INVALID_PARAMETER);
904 // If the requestor is looking for the root node itself, then return it.
907 if( RootNode->Type.Data.ShortNameTreeEntry.HashIndex == Index)
910 *DirEntry = RootNode;
912 try_return( ntStatus);
916 // Loop through the nodes in the tree
919 while( pCurrentEntry != NULL)
923 // Greater values are to the right link.
926 if( Index > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
930 // Go to the next RIGHT entry, if there is one
933 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
936 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
942 // Came to the end of the branch so bail
945 pCurrentEntry = NULL;
950 else if( Index < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
954 // Go to the next LEFT entry, if one exists
957 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
960 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
966 // End of the branch ...
969 pCurrentEntry = NULL;
981 *DirEntry = pCurrentEntry;
996 AFSInsertShortNameDirEntry( IN AFSDirectoryCB *RootNode,
997 IN AFSDirectoryCB *DirEntry)
1000 NTSTATUS ntStatus = STATUS_SUCCESS;
1001 AFSDirectoryCB *pCurrentEntry = NULL;
1003 pCurrentEntry = RootNode;
1009 // If we have no root node then we can;t start the search.
1012 if( pCurrentEntry == NULL)
1015 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1016 AFS_TRACE_LEVEL_WARNING,
1017 "AFSInsertShortNameDirEntry Invalid root node\n");
1019 try_return( ntStatus = STATUS_UNSUCCESSFUL);
1023 // Locate the branch end to insert the node
1026 while( pCurrentEntry != NULL)
1030 // Greater valued indices are to the right link
1033 if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1037 // Go to the next RIGHT entry, if it exists
1040 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
1042 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
1048 // Located the end of the branch line so insert the node
1051 pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink = (void *)DirEntry;
1053 DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1058 else if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1062 // Go to the next LEFT entry, if it exists
1065 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1067 pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
1073 // Located the branch line end so insert the node here
1076 pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink = (void *)DirEntry;
1078 DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1086 ntStatus = STATUS_UNSUCCESSFUL;
1088 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1089 AFS_TRACE_LEVEL_VERBOSE,
1090 "AFSInsertShortNameDirEntry Collision with DE %p for shortname %S and %wZ\n",
1092 pCurrentEntry->NameInformation.ShortName,
1093 &pCurrentEntry->NameInformation.FileName);
1108 AFSRemoveShortNameDirEntry( IN AFSDirectoryCB **RootNode,
1109 IN AFSDirectoryCB *DirEntry)
1112 NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1113 AFSDirectoryCB *pRightNode = NULL;
1114 AFSDirectoryCB *pLeftNode = NULL;
1115 AFSDirectoryCB *pCurrentNode = NULL;
1116 AFSDirectoryCB *pParentNode = NULL;
1118 pRightNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.rightLink;
1119 pLeftNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.leftLink;
1120 pParentNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.parentLink;
1125 if( (pRightNode == NULL) && (pLeftNode == NULL))
1128 if( pParentNode != NULL)
1131 if( pParentNode->Type.Data.ShortNameTreeEntry.leftLink == DirEntry)
1134 pParentNode->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1139 pParentNode->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1146 // Removing the top node
1155 if( pRightNode != NULL)
1158 if( pParentNode != NULL)
1161 // Replace the parent node where this entry was.
1162 if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1165 pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pRightNode;
1170 pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pRightNode;
1176 *RootNode = pRightNode;
1178 pRightNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1181 pRightNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1184 if( pLeftNode != NULL)
1187 // To connect the left node, we must walk the chain of the
1188 // right nodes left side until we reach the end.
1189 // At the end attach the leftNode
1190 if( pRightNode != NULL)
1193 pCurrentNode = pRightNode;
1195 while( pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1198 pCurrentNode = (AFSDirectoryCB *)pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink;
1201 pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1203 pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pCurrentNode;
1208 if( pParentNode != NULL)
1211 // This is where we have a left node with no right node.
1212 // So, attach the left node to the parent of
1213 // the removed nodes branch
1214 if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1217 pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pLeftNode;
1222 pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1225 pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1230 *RootNode = pLeftNode;
1232 pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1239 // Cleanup the just removed node
1242 DirEntry->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1243 DirEntry->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1244 DirEntry->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1246 ntStatus = STATUS_SUCCESS;
1253 AFSLocateHashEntry( IN AFSBTreeEntry *TopNode,
1254 IN ULONGLONG HashIndex,
1255 IN OUT AFSBTreeEntry **TreeEntry)
1258 NTSTATUS ntStatus = STATUS_SUCCESS;
1259 AFSBTreeEntry *pEntry = NULL;
1260 AFSBTreeEntry *pCurrentEntry = NULL;
1262 pCurrentEntry = TopNode;
1268 // If the rootnode passed is null then the directory is empty
1271 if( TopNode == NULL)
1274 try_return( ntStatus = STATUS_INVALID_PARAMETER);
1278 // If the requestor is looking for the root node itself, then return it.
1281 if( TopNode->HashIndex == HashIndex)
1284 *TreeEntry = TopNode;
1286 try_return( ntStatus);
1290 // Loop through the nodes in the tree
1293 while( pCurrentEntry != NULL)
1297 // Greater values are to the right link.
1300 if( HashIndex > pCurrentEntry->HashIndex)
1304 // Go to the next RIGHT entry, if there is one
1307 if( pCurrentEntry->rightLink != NULL)
1310 pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1316 // Came to the end of the branch so bail
1319 pCurrentEntry = NULL;
1324 else if( HashIndex < pCurrentEntry->HashIndex)
1328 // Go to the next LEFT entry, if one exists
1331 if( pCurrentEntry->leftLink != NULL)
1334 pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1340 // End of the branch ...
1343 pCurrentEntry = NULL;
1355 *TreeEntry = pCurrentEntry;
1370 AFSInsertHashEntry( IN AFSBTreeEntry *TopNode,
1371 IN AFSBTreeEntry *FileIDEntry)
1374 NTSTATUS ntStatus = STATUS_SUCCESS;
1375 AFSBTreeEntry *pCurrentEntry = NULL;
1377 pCurrentEntry = TopNode;
1383 // If we have no root node then we can;t start the search.
1386 if( pCurrentEntry == NULL)
1389 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1390 AFS_TRACE_LEVEL_WARNING,
1391 "AFSInsertHashEntry Invalid root node\n");
1393 try_return( ntStatus = STATUS_UNSUCCESSFUL);
1397 // Locate the branch end to insert the node
1400 while( pCurrentEntry != NULL)
1404 // Greater vlued indices are to the right link
1407 if( FileIDEntry->HashIndex > pCurrentEntry->HashIndex)
1411 // Go to the next RIGHT entry, if it exists
1414 if( pCurrentEntry->rightLink != NULL)
1416 pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1422 // Located the end of the branch line so insert the node
1425 pCurrentEntry->rightLink = (void *)FileIDEntry;
1427 FileIDEntry->parentLink = (void *)pCurrentEntry;
1432 else if( FileIDEntry->HashIndex < pCurrentEntry->HashIndex)
1436 // Go to the next LEFT entry, if it exists
1439 if( pCurrentEntry->leftLink != NULL)
1441 pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1447 // Located the branch line end so insert the node here
1450 pCurrentEntry->leftLink = (void *)FileIDEntry;
1452 FileIDEntry->parentLink = (void *)pCurrentEntry;
1460 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1461 AFS_TRACE_LEVEL_WARNING,
1462 "AFSInsertHashEntry Attempt to re-insert a CRC %I64X\n",
1463 FileIDEntry->HashIndex);
1467 ntStatus = STATUS_UNSUCCESSFUL;
1482 AFSRemoveHashEntry( IN AFSBTreeEntry **TopNode,
1483 IN AFSBTreeEntry *FileIDEntry)
1486 NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1487 AFSBTreeEntry *pRightNode = NULL;
1488 AFSBTreeEntry *pLeftNode = NULL;
1489 AFSBTreeEntry *pCurrentNode = NULL;
1490 AFSBTreeEntry *pParentNode = NULL;
1492 pRightNode = (AFSBTreeEntry *)FileIDEntry->rightLink;
1493 pLeftNode = (AFSBTreeEntry *)FileIDEntry->leftLink;
1494 pParentNode = (AFSBTreeEntry *)FileIDEntry->parentLink;
1499 if( (pRightNode == NULL) && (pLeftNode == NULL))
1502 if( pParentNode != NULL)
1505 if( pParentNode->leftLink == FileIDEntry)
1508 pParentNode->leftLink = NULL;
1513 pParentNode->rightLink = NULL;
1520 // Removing the top node
1529 if( pRightNode != NULL)
1532 if( pParentNode != NULL)
1535 // Replace the parent node where this entry was.
1536 if( pParentNode->rightLink == FileIDEntry)
1539 pParentNode->rightLink = pRightNode;
1544 pParentNode->leftLink = pRightNode;
1550 *TopNode = pRightNode;
1552 pRightNode->parentLink = NULL;
1555 pRightNode->parentLink = pParentNode;
1558 if( pLeftNode != NULL)
1561 // To connect the left node, we must walk the chain of the
1562 // right nodes left side until we reach the end.
1563 // At the end attach the leftNode
1564 if( pRightNode != NULL)
1567 pCurrentNode = pRightNode;
1569 while( pCurrentNode->leftLink != NULL)
1572 pCurrentNode = (AFSBTreeEntry *)pCurrentNode->leftLink;
1575 pCurrentNode->leftLink = pLeftNode;
1577 pLeftNode->parentLink = pCurrentNode;
1582 if( pParentNode != NULL)
1585 // This is where we have a left node with no right node.
1586 // So, attach the left node to the parent of
1587 // the removed nodes branch
1588 if( pParentNode->rightLink == FileIDEntry)
1591 pParentNode->rightLink = pLeftNode;
1596 pParentNode->leftLink = pLeftNode;
1599 pLeftNode->parentLink = pParentNode;
1604 *TopNode = pLeftNode;
1606 pLeftNode->parentLink = NULL;
1613 // Cleanup the just removed node
1616 FileIDEntry->leftLink = NULL;
1617 FileIDEntry->parentLink = NULL;
1618 FileIDEntry->rightLink = NULL;
1620 ntStatus = STATUS_SUCCESS;