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