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 }