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_WARNING,
 372                               "AFSInsertCaseSensitiveDirEntry Attempt to re-insert a CRC %I64X\n",
 373                               DirEntry->CaseSensitiveTreeEntry.HashIndex);
 374
 375                 ASSERT( FALSE);
 376
 377                 ntStatus = STATUS_UNSUCCESSFUL;
 378
 379                 break;
 380             }
 381         }
 382
 383 try_exit:
 384
 385         NOTHING;
 386     }
 387
 388     return ntStatus;
 389 }
 390
 391 NTSTATUS
 392 AFSInsertCaseInsensitiveDirEntry( IN AFSDirectoryCB *RootNode,
 393                                   IN AFSDirectoryCB *DirEntry)
 394 {
 395
 396     NTSTATUS ntStatus = STATUS_SUCCESS;
 397     AFSDirectoryCB *pCurrentEntry = NULL;
 398
 399     pCurrentEntry = RootNode;
 400
 401     __Enter
 402     {
 403
 404         //
 405         // If we have no root node then we can;t start the search.
 406         //
 407
 408         if( pCurrentEntry == NULL)
 409         {
 410
 411             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
 412                           AFS_TRACE_LEVEL_WARNING,
 413                           "AFSInsertCaseInsensitiveDirEntry Invalid root node\n");
 414
 415             try_return( ntStatus = STATUS_UNSUCCESSFUL);
 416         }
 417
 418         //
 419         // Locate the branch end to insert the node
 420         //
 421
 422         while( pCurrentEntry != NULL)
 423         {
 424
 425             //
 426             // Greater vlued indices are to the right link
 427             //
 428
 429             if( DirEntry->CaseInsensitiveTreeEntry.HashIndex > pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
 430             {
 431
 432                 //
 433                 // Go to the next RIGHT entry, if it exists
 434                 //
 435
 436                 if( pCurrentEntry->CaseInsensitiveTreeEntry.rightLink != NULL)
 437                 {
 438                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.rightLink;
 439                 }
 440                 else
 441                 {
 442
 443                     //
 444                     // Located the end of the branch line so insert the node
 445                     //
 446
 447                     pCurrentEntry->CaseInsensitiveTreeEntry.rightLink = (void *)DirEntry;
 448
 449                     DirEntry->CaseInsensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
 450
 451                     SetFlag( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
 452
 453                     break;
 454                 }
 455             }
 456             else if( DirEntry->CaseInsensitiveTreeEntry.HashIndex < pCurrentEntry->CaseInsensitiveTreeEntry.HashIndex)
 457             {
 458
 459                 //
 460                 // Go to the next LEFT entry, if it exists
 461                 //
 462
 463                 if( pCurrentEntry->CaseInsensitiveTreeEntry.leftLink != NULL)
 464                 {
 465                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveTreeEntry.leftLink;
 466                 }
 467                 else
 468                 {
 469
 470                     //
 471                     // Located the branch line end so insert the node here
 472                     //
 473
 474                     pCurrentEntry->CaseInsensitiveTreeEntry.leftLink = (void *)DirEntry;
 475
 476                     DirEntry->CaseInsensitiveTreeEntry.parentLink = (void *)pCurrentEntry;
 477
 478                     SetFlag( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
 479
 480                     break;
 481                 }
 482             }
 483             else
 484             {
 485
 486                 //
 487                 // Inser the the entry at the end of the insensitive list
 488                 //
 489
 490                 while( pCurrentEntry->CaseInsensitiveList.fLink != NULL)
 491                 {
 492
 493                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->CaseInsensitiveList.fLink;
 494                 }
 495
 496                 pCurrentEntry->CaseInsensitiveList.fLink = (void *)DirEntry;
 497
 498                 DirEntry->CaseInsensitiveList.bLink = (void *)pCurrentEntry;
 499
 500                 break;
 501             }
 502         }
 503
 504 try_exit:
 505
 506         NOTHING;
 507     }
 508
 509     return ntStatus;
 510 }
 511
 512 NTSTATUS
 513 AFSRemoveCaseSensitiveDirEntry( IN AFSDirectoryCB **RootNode,
 514                                 IN AFSDirectoryCB *DirEntry)
 515 {
 516
 517     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
 518     AFSDirectoryCB *pRightNode = NULL;
 519     AFSDirectoryCB *pLeftNode = NULL;
 520     AFSDirectoryCB *pCurrentNode = NULL;
 521     AFSDirectoryCB *pParentNode = NULL;
 522
 523     pRightNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.rightLink;
 524     pLeftNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.leftLink;
 525     pParentNode = (AFSDirectoryCB *)DirEntry->CaseSensitiveTreeEntry.parentLink;
 526
 527     __Enter
 528     {
 529
 530         if( (pRightNode == NULL) && (pLeftNode == NULL))
 531         {
 532
 533             if( pParentNode != NULL)
 534             {
 535
 536                 if( pParentNode->CaseSensitiveTreeEntry.leftLink == DirEntry)
 537                 {
 538
 539                     pParentNode->CaseSensitiveTreeEntry.leftLink = NULL;
 540                 }
 541                 else
 542                 {
 543
 544                     pParentNode->CaseSensitiveTreeEntry.rightLink = NULL;
 545                 }
 546             }
 547             else
 548             {
 549
 550                 //
 551                 // Removing the top node
 552                 //
 553
 554                 *RootNode = NULL;
 555             }
 556         }
 557         else
 558         {
 559
 560             if( pRightNode != NULL)
 561             {
 562
 563                 if( pParentNode != NULL)
 564                 {
 565
 566                     // Replace the parent node where this entry was.
 567                     if( pParentNode->CaseSensitiveTreeEntry.rightLink == DirEntry)
 568                     {
 569
 570                         pParentNode->CaseSensitiveTreeEntry.rightLink = pRightNode;
 571                     }
 572                     else
 573                     {
 574
 575                         pParentNode->CaseSensitiveTreeEntry.leftLink = pRightNode;
 576                     }
 577                 }
 578                 else
 579                 {
 580
 581                     *RootNode = pRightNode;
 582
 583                     pRightNode->CaseSensitiveTreeEntry.parentLink = NULL;
 584                 }
 585
 586                 pRightNode->CaseSensitiveTreeEntry.parentLink = pParentNode;
 587             }
 588
 589             if( pLeftNode != NULL)
 590             {
 591
 592                 // To connect the left node, we must walk the chain of the
 593                 // right nodes left side until we reach the end.
 594                 // At the end attach the leftNode
 595                 if( pRightNode != NULL)
 596                 {
 597
 598                     pCurrentNode = pRightNode;
 599
 600                     while( pCurrentNode->CaseSensitiveTreeEntry.leftLink != NULL)
 601                     {
 602
 603                         pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseSensitiveTreeEntry.leftLink;
 604                     }
 605
 606                     pCurrentNode->CaseSensitiveTreeEntry.leftLink = pLeftNode;
 607
 608                     pLeftNode->CaseSensitiveTreeEntry.parentLink = pCurrentNode;
 609                 }
 610                 else
 611                 {
 612
 613                     if( pParentNode != NULL)
 614                     {
 615
 616                         // This is where we have a left node with no right node.
 617                         // So, attach the left node to the parent of
 618                         // the removed nodes branch
 619                         if( pParentNode->CaseSensitiveTreeEntry.rightLink == DirEntry)
 620                         {
 621
 622                             pParentNode->CaseSensitiveTreeEntry.rightLink = pLeftNode;
 623                         }
 624                         else
 625                         {
 626
 627                             pParentNode->CaseSensitiveTreeEntry.leftLink = pLeftNode;
 628                         }
 629
 630                         pLeftNode->CaseSensitiveTreeEntry.parentLink = pParentNode;
 631                     }
 632                     else
 633                     {
 634
 635                         *RootNode = pLeftNode;
 636
 637                         pLeftNode->CaseSensitiveTreeEntry.parentLink = NULL;
 638                     }
 639                 }
 640             }
 641         }
 642
 643         //
 644         // Cleanup the just removed node
 645         //
 646
 647         DirEntry->CaseSensitiveTreeEntry.leftLink = NULL;
 648         DirEntry->CaseSensitiveTreeEntry.parentLink = NULL;
 649         DirEntry->CaseSensitiveTreeEntry.rightLink = NULL;
 650
 651         ntStatus = STATUS_SUCCESS;
 652     }
 653
 654     return ntStatus;
 655 }
 656
 657 NTSTATUS
 658 AFSRemoveCaseInsensitiveDirEntry( IN AFSDirectoryCB **RootNode,
 659                                   IN AFSDirectoryCB *DirEntry)
 660 {
 661
 662     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
 663     AFSDirectoryCB *pRightNode = NULL;
 664     AFSDirectoryCB *pLeftNode = NULL;
 665     AFSDirectoryCB *pCurrentNode = NULL;
 666     AFSDirectoryCB *pParentNode = NULL;
 667     AFSDirectoryCB *pNewHeadEntry = NULL;
 668
 669     pRightNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.rightLink;
 670     pLeftNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.leftLink;
 671     pParentNode = (AFSDirectoryCB *)DirEntry->CaseInsensitiveTreeEntry.parentLink;
 672
 673     __Enter
 674     {
 675
 676         //
 677         // If this is not a head of list entry then just update the pointers for it
 678         //
 679
 680         if( !BooleanFlagOn( DirEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD))
 681         {
 682
 683             ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.bLink)->CaseInsensitiveList.fLink = DirEntry->CaseInsensitiveList.fLink;
 684
 685             if( DirEntry->CaseInsensitiveList.fLink != NULL)
 686             {
 687
 688                 ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink)->CaseInsensitiveList.bLink = DirEntry->CaseInsensitiveList.bLink;
 689             }
 690
 691             try_return( ntStatus);
 692         }
 693
 694         if( DirEntry->CaseInsensitiveList.fLink != NULL)
 695         {
 696
 697             //
 698             // Removing the head of a list of entries so just update pointers
 699             //
 700
 701             pNewHeadEntry = (AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink;
 702
 703             if( pParentNode != NULL)
 704             {
 705
 706                 if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
 707                 {
 708                     pParentNode->CaseInsensitiveTreeEntry.rightLink = (void *)pNewHeadEntry;
 709                 }
 710                 else
 711                 {
 712                     pParentNode->CaseInsensitiveTreeEntry.leftLink = (void *)pNewHeadEntry;
 713                 }
 714             }
 715             else
 716             {
 717                 *RootNode = pNewHeadEntry;
 718             }
 719
 720             if( pRightNode != NULL)
 721             {
 722
 723                 pRightNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
 724             }
 725
 726             if( pLeftNode != NULL)
 727             {
 728
 729                 pLeftNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
 730             }
 731
 732             pNewHeadEntry->CaseInsensitiveList.bLink = NULL;
 733
 734             pNewHeadEntry->CaseInsensitiveTreeEntry.parentLink = pParentNode;
 735
 736             pNewHeadEntry->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
 737
 738             pNewHeadEntry->CaseInsensitiveTreeEntry.rightLink = pRightNode;
 739
 740             SetFlag( pNewHeadEntry->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
 741
 742             try_return( ntStatus);
 743         }
 744
 745         if( (pRightNode == NULL) && (pLeftNode == NULL))
 746         {
 747
 748             if( pParentNode != NULL)
 749             {
 750
 751                 if( pParentNode->CaseInsensitiveTreeEntry.leftLink == DirEntry)
 752                 {
 753
 754                     pParentNode->CaseInsensitiveTreeEntry.leftLink = NULL;
 755                 }
 756                 else
 757                 {
 758
 759                     pParentNode->CaseInsensitiveTreeEntry.rightLink = NULL;
 760                 }
 761             }
 762             else
 763             {
 764
 765                 //
 766                 // Removing the top node
 767                 //
 768
 769                 *RootNode = NULL;
 770             }
 771         }
 772         else
 773         {
 774
 775             if( pRightNode != NULL)
 776             {
 777
 778                 if( pParentNode != NULL)
 779                 {
 780
 781                     // Replace the parent node where this entry was.
 782                     if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
 783                     {
 784
 785                         pParentNode->CaseInsensitiveTreeEntry.rightLink = pRightNode;
 786                     }
 787                     else
 788                     {
 789
 790                         pParentNode->CaseInsensitiveTreeEntry.leftLink = pRightNode;
 791                     }
 792                 }
 793                 else
 794                 {
 795
 796                     *RootNode = pRightNode;
 797
 798                     pRightNode->CaseInsensitiveTreeEntry.parentLink = NULL;
 799                 }
 800
 801                 pRightNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
 802             }
 803
 804             if( pLeftNode != NULL)
 805             {
 806
 807                 // To connect the left node, we must walk the chain of the
 808                 // right nodes left side until we reach the end.
 809                 // At the end attach the leftNode
 810                 if( pRightNode != NULL)
 811                 {
 812
 813                     pCurrentNode = pRightNode;
 814
 815                     while( pCurrentNode->CaseInsensitiveTreeEntry.leftLink != NULL)
 816                     {
 817
 818                         pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseInsensitiveTreeEntry.leftLink;
 819                     }
 820
 821                     pCurrentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
 822
 823                     pLeftNode->CaseInsensitiveTreeEntry.parentLink = pCurrentNode;
 824                 }
 825                 else
 826                 {
 827
 828                     if( pParentNode != NULL)
 829                     {
 830
 831                         // This is where we have a left node with no right node.
 832                         // So, attach the left node to the parent of
 833                         // the removed nodes branch
 834                         if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
 835                         {
 836
 837                             pParentNode->CaseInsensitiveTreeEntry.rightLink = pLeftNode;
 838                         }
 839                         else
 840                         {
 841
 842                             pParentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
 843                         }
 844
 845                         pLeftNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
 846                     }
 847                     else
 848                     {
 849
 850                         *RootNode = pLeftNode;
 851
 852                         pLeftNode->CaseInsensitiveTreeEntry.parentLink = NULL;
 853                     }
 854                 }
 855             }
 856         }
 857
 858 try_exit:
 859
 860         //
 861         // Cleanup the just removed node
 862         //
 863
 864         DirEntry->CaseInsensitiveTreeEntry.leftLink = NULL;
 865         DirEntry->CaseInsensitiveTreeEntry.parentLink = NULL;
 866         DirEntry->CaseInsensitiveTreeEntry.rightLink = NULL;
 867
 868         DirEntry->CaseInsensitiveList.bLink = NULL;
 869         DirEntry->CaseInsensitiveList.fLink = NULL;
 870
 871         ntStatus = STATUS_SUCCESS;
 872     }
 873
 874     return ntStatus;
 875 }
 876
 877 NTSTATUS
 878 AFSLocateShortNameDirEntry( IN AFSDirectoryCB *RootNode,
 879                             IN ULONG Index,
 880                             IN OUT AFSDirectoryCB **DirEntry)
 881 {
 882
 883     NTSTATUS    ntStatus = STATUS_SUCCESS;
 884     AFSDirectoryCB   *pEntry = NULL;
 885     AFSDirectoryCB   *pCurrentEntry = NULL;
 886
 887     pCurrentEntry = RootNode;
 888
 889     __Enter
 890     {
 891
 892         *DirEntry = NULL;
 893
 894         //
 895         // If the rootnode passed is null then the directory is empty
 896         //
 897
 898         if( RootNode == NULL)
 899         {
 900
 901             try_return( ntStatus = STATUS_INVALID_PARAMETER);
 902         }
 903
 904         //
 905         // If the requestor is looking for the root node itself, then return it.
 906         //
 907
 908         if( RootNode->Type.Data.ShortNameTreeEntry.HashIndex == Index)
 909         {
 910
 911             *DirEntry = RootNode;
 912
 913             try_return( ntStatus);
 914         }
 915
 916         //
 917         // Loop through the nodes in the tree
 918         //
 919
 920         while( pCurrentEntry != NULL)
 921         {
 922
 923             //
 924             // Greater values are to the right link.
 925             //
 926
 927             if( Index > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
 928             {
 929
 930                 //
 931                 // Go to the next RIGHT entry, if there is one
 932                 //
 933
 934                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
 935                 {
 936
 937                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
 938                 }
 939                 else
 940                 {
 941
 942                     //
 943                     // Came to the end of the branch so bail
 944                     //
 945
 946                     pCurrentEntry = NULL;
 947
 948                     break;
 949                 }
 950             }
 951             else if( Index < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
 952             {
 953
 954                 //
 955                 // Go to the next LEFT entry, if one exists
 956                 //
 957
 958                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
 959                 {
 960
 961                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
 962                 }
 963                 else
 964                 {
 965
 966                     //
 967                     // End of the branch ...
 968                     //
 969
 970                     pCurrentEntry = NULL;
 971
 972                     break;
 973                 }
 974             }
 975             else
 976             {
 977
 978                 //
 979                 // Found the entry.
 980                 //
 981
 982                 *DirEntry = pCurrentEntry;
 983
 984                 break;
 985             }
 986         }
 987
 988 try_exit:
 989
 990         NOTHING;
 991     }
 992
 993     return ntStatus;
 994 }
 995
 996 NTSTATUS
 997 AFSInsertShortNameDirEntry( IN AFSDirectoryCB *RootNode,
 998                             IN AFSDirectoryCB *DirEntry)
 999 {
1000
1001     NTSTATUS ntStatus = STATUS_SUCCESS;
1002     AFSDirectoryCB *pCurrentEntry = NULL;
1003
1004     pCurrentEntry = RootNode;
1005
1006     __Enter
1007     {
1008
1009         //
1010         // If we have no root node then we can;t start the search.
1011         //
1012
1013         if( pCurrentEntry == NULL)
1014         {
1015
1016             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1017                           AFS_TRACE_LEVEL_WARNING,
1018                           "AFSInsertShortNameDirEntry Invalid root node\n");
1019
1020             try_return( ntStatus = STATUS_UNSUCCESSFUL);
1021         }
1022
1023         //
1024         // Locate the branch end to insert the node
1025         //
1026
1027         while( pCurrentEntry != NULL)
1028         {
1029
1030             //
1031             // Greater valued indices are to the right link
1032             //
1033
1034             if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1035             {
1036
1037                 //
1038                 // Go to the next RIGHT entry, if it exists
1039                 //
1040
1041                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
1042                 {
1043                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
1044                 }
1045                 else
1046                 {
1047
1048                     //
1049                     // Located the end of the branch line so insert the node
1050                     //
1051
1052                     pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink = (void *)DirEntry;
1053
1054                     DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1055
1056                     break;
1057                 }
1058             }
1059             else if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1060             {
1061
1062                 //
1063                 // Go to the next LEFT entry, if it exists
1064                 //
1065
1066                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1067                 {
1068                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
1069                 }
1070                 else
1071                 {
1072
1073                     //
1074                     // Located the branch line end so insert the node here
1075                     //
1076
1077                     pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink = (void *)DirEntry;
1078
1079                     DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1080
1081                     break;
1082                 }
1083             }
1084             else
1085             {
1086
1087                 break;
1088             }
1089         }
1090
1091 try_exit:
1092
1093         NOTHING;
1094     }
1095
1096     return ntStatus;
1097 }
1098
1099 NTSTATUS
1100 AFSRemoveShortNameDirEntry( IN AFSDirectoryCB **RootNode,
1101                             IN AFSDirectoryCB *DirEntry)
1102 {
1103
1104     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1105     AFSDirectoryCB *pRightNode = NULL;
1106     AFSDirectoryCB *pLeftNode = NULL;
1107     AFSDirectoryCB *pCurrentNode = NULL;
1108     AFSDirectoryCB *pParentNode = NULL;
1109
1110     pRightNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.rightLink;
1111     pLeftNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.leftLink;
1112     pParentNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.parentLink;
1113
1114     __Enter
1115     {
1116
1117         if( (pRightNode == NULL) && (pLeftNode == NULL))
1118         {
1119
1120             if( pParentNode != NULL)
1121             {
1122
1123                 if( pParentNode->Type.Data.ShortNameTreeEntry.leftLink == DirEntry)
1124                 {
1125
1126                     pParentNode->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1127                 }
1128                 else
1129                 {
1130
1131                     pParentNode->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1132                 }
1133             }
1134             else
1135             {
1136
1137                 //
1138                 // Removing the top node
1139                 //
1140
1141                 *RootNode = NULL;
1142             }
1143         }
1144         else
1145         {
1146
1147             if( pRightNode != NULL)
1148             {
1149
1150                 if( pParentNode != NULL)
1151                 {
1152
1153                     // Replace the parent node where this entry was.
1154                     if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1155                     {
1156
1157                         pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pRightNode;
1158                     }
1159                     else
1160                     {
1161
1162                         pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pRightNode;
1163                     }
1164                 }
1165                 else
1166                 {
1167
1168                     *RootNode = pRightNode;
1169
1170                     pRightNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1171                 }
1172
1173                 pRightNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1174             }
1175
1176             if( pLeftNode != NULL)
1177             {
1178
1179                 // To connect the left node, we must walk the chain of the
1180                 // right nodes left side until we reach the end.
1181                 // At the end attach the leftNode
1182                 if( pRightNode != NULL)
1183                 {
1184
1185                     pCurrentNode = pRightNode;
1186
1187                     while( pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1188                     {
1189
1190                         pCurrentNode = (AFSDirectoryCB *)pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink;
1191                     }
1192
1193                     pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1194
1195                     pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pCurrentNode;
1196                 }
1197                 else
1198                 {
1199
1200                     if( pParentNode != NULL)
1201                     {
1202
1203                         // This is where we have a left node with no right node.
1204                         // So, attach the left node to the parent of
1205                         // the removed nodes branch
1206                         if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1207                         {
1208
1209                             pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pLeftNode;
1210                         }
1211                         else
1212                         {
1213
1214                             pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1215                         }
1216
1217                         pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1218                     }
1219                     else
1220                     {
1221
1222                         *RootNode = pLeftNode;
1223
1224                         pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1225                     }
1226                 }
1227             }
1228         }
1229
1230         //
1231         // Cleanup the just removed node
1232         //
1233
1234         DirEntry->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1235         DirEntry->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1236         DirEntry->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1237
1238         ntStatus = STATUS_SUCCESS;
1239     }
1240
1241     return ntStatus;
1242 }
1243
1244 NTSTATUS
1245 AFSLocateHashEntry( IN AFSBTreeEntry *TopNode,
1246                     IN ULONGLONG HashIndex,
1247                     IN OUT AFSBTreeEntry **TreeEntry)
1248 {
1249
1250     NTSTATUS         ntStatus = STATUS_SUCCESS;
1251     AFSBTreeEntry   *pEntry = NULL;
1252     AFSBTreeEntry   *pCurrentEntry = NULL;
1253
1254     pCurrentEntry = TopNode;
1255
1256     __Enter
1257     {
1258
1259         //
1260         // If the rootnode passed is null then the directory is empty
1261         //
1262
1263         if( TopNode == NULL)
1264         {
1265
1266             try_return( ntStatus = STATUS_INVALID_PARAMETER);
1267         }
1268
1269         //
1270         // If the requestor is looking for the root node itself, then return it.
1271         //
1272
1273         if( TopNode->HashIndex == HashIndex)
1274         {
1275
1276             *TreeEntry = TopNode;
1277
1278             try_return( ntStatus);
1279         }
1280
1281         //
1282         // Loop through the nodes in the tree
1283         //
1284
1285         while( pCurrentEntry != NULL)
1286         {
1287
1288             //
1289             // Greater values are to the right link.
1290             //
1291
1292             if( HashIndex > pCurrentEntry->HashIndex)
1293             {
1294
1295                 //
1296                 // Go to the next RIGHT entry, if there is one
1297                 //
1298
1299                 if( pCurrentEntry->rightLink != NULL)
1300                 {
1301
1302                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1303                 }
1304                 else
1305                 {
1306
1307                     //
1308                     // Came to the end of the branch so bail
1309                     //
1310
1311                     pCurrentEntry = NULL;
1312
1313                     break;
1314                 }
1315             }
1316             else if( HashIndex < pCurrentEntry->HashIndex)
1317             {
1318
1319                 //
1320                 // Go to the next LEFT entry, if one exists
1321                 //
1322
1323                 if( pCurrentEntry->leftLink != NULL)
1324                 {
1325
1326                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1327                 }
1328                 else
1329                 {
1330
1331                     //
1332                     // End of the branch ...
1333                     //
1334
1335                     pCurrentEntry = NULL;
1336
1337                     break;
1338                 }
1339             }
1340             else
1341             {
1342
1343                 //
1344                 // Found the entry.
1345                 //
1346
1347                 *TreeEntry = pCurrentEntry;
1348
1349                 break;
1350             }
1351         }
1352
1353 try_exit:
1354
1355         NOTHING;
1356     }
1357
1358     return ntStatus;
1359 }
1360
1361 NTSTATUS
1362 AFSInsertHashEntry( IN AFSBTreeEntry *TopNode,
1363                     IN AFSBTreeEntry *FileIDEntry)
1364 {
1365
1366     NTSTATUS ntStatus = STATUS_SUCCESS;
1367     AFSBTreeEntry *pCurrentEntry = NULL;
1368
1369     pCurrentEntry = TopNode;
1370
1371     __Enter
1372     {
1373
1374         //
1375         // If we have no root node then we can;t start the search.
1376         //
1377
1378         if( pCurrentEntry == NULL)
1379         {
1380
1381             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1382                           AFS_TRACE_LEVEL_WARNING,
1383                           "AFSInsertHashEntry Invalid root node\n");
1384
1385             try_return( ntStatus = STATUS_UNSUCCESSFUL);
1386         }
1387
1388         //
1389         // Locate the branch end to insert the node
1390         //
1391
1392         while( pCurrentEntry != NULL)
1393         {
1394
1395             //
1396             // Greater vlued indices are to the right link
1397             //
1398
1399             if( FileIDEntry->HashIndex > pCurrentEntry->HashIndex)
1400             {
1401
1402                 //
1403                 // Go to the next RIGHT entry, if it exists
1404                 //
1405
1406                 if( pCurrentEntry->rightLink != NULL)
1407                 {
1408                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1409                 }
1410                 else
1411                 {
1412
1413                     //
1414                     // Located the end of the branch line so insert the node
1415                     //
1416
1417                     pCurrentEntry->rightLink = (void *)FileIDEntry;
1418
1419                     FileIDEntry->parentLink = (void *)pCurrentEntry;
1420
1421                     break;
1422                 }
1423             }
1424             else if( FileIDEntry->HashIndex < pCurrentEntry->HashIndex)
1425             {
1426
1427                 //
1428                 // Go to the next LEFT entry, if it exists
1429                 //
1430
1431                 if( pCurrentEntry->leftLink != NULL)
1432                 {
1433                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1434                 }
1435                 else
1436                 {
1437
1438                     //
1439                     // Located the branch line end so insert the node here
1440                     //
1441
1442                     pCurrentEntry->leftLink = (void *)FileIDEntry;
1443
1444                     FileIDEntry->parentLink = (void *)pCurrentEntry;
1445
1446                     break;
1447                 }
1448             }
1449             else
1450             {
1451
1452                 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1453                               AFS_TRACE_LEVEL_WARNING,
1454                               "AFSInsertHashEntry Attempt to re-insert a CRC %I64X\n",
1455                               FileIDEntry->HashIndex);
1456
1457                 ASSERT( FALSE);
1458
1459                 ntStatus = STATUS_UNSUCCESSFUL;
1460
1461                 break;
1462             }
1463         }
1464
1465 try_exit:
1466
1467         NOTHING;
1468     }
1469
1470     return ntStatus;
1471 }
1472
1473 NTSTATUS
1474 AFSRemoveHashEntry( IN AFSBTreeEntry **TopNode,
1475                     IN AFSBTreeEntry *FileIDEntry)
1476 {
1477
1478     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1479     AFSBTreeEntry *pRightNode = NULL;
1480     AFSBTreeEntry *pLeftNode = NULL;
1481     AFSBTreeEntry *pCurrentNode = NULL;
1482     AFSBTreeEntry *pParentNode = NULL;
1483
1484     pRightNode = (AFSBTreeEntry *)FileIDEntry->rightLink;
1485     pLeftNode = (AFSBTreeEntry *)FileIDEntry->leftLink;
1486     pParentNode = (AFSBTreeEntry *)FileIDEntry->parentLink;
1487
1488     __Enter
1489     {
1490
1491         if( (pRightNode == NULL) && (pLeftNode == NULL))
1492         {
1493
1494             if( pParentNode != NULL)
1495             {
1496
1497                 if( pParentNode->leftLink == FileIDEntry)
1498                 {
1499
1500                     pParentNode->leftLink = NULL;
1501                 }
1502                 else
1503                 {
1504
1505                     pParentNode->rightLink = NULL;
1506                 }
1507             }
1508             else
1509             {
1510
1511                 //
1512                 // Removing the top node
1513                 //
1514
1515                 *TopNode = NULL;
1516             }
1517         }
1518         else
1519         {
1520
1521             if( pRightNode != NULL)
1522             {
1523
1524                 if( pParentNode != NULL)
1525                 {
1526
1527                     // Replace the parent node where this entry was.
1528                     if( pParentNode->rightLink == FileIDEntry)
1529                     {
1530
1531                         pParentNode->rightLink = pRightNode;
1532                     }
1533                     else
1534                     {
1535
1536                         pParentNode->leftLink = pRightNode;
1537                     }
1538                 }
1539                 else
1540                 {
1541
1542                     *TopNode = pRightNode;
1543
1544                     pRightNode->parentLink = NULL;
1545                 }
1546
1547                 pRightNode->parentLink = pParentNode;
1548             }
1549
1550             if( pLeftNode != NULL)
1551             {
1552
1553                 // To connect the left node, we must walk the chain of the
1554                 // right nodes left side until we reach the end.
1555                 // At the end attach the leftNode
1556                 if( pRightNode != NULL)
1557                 {
1558
1559                     pCurrentNode = pRightNode;
1560
1561                     while( pCurrentNode->leftLink != NULL)
1562                     {
1563
1564                         pCurrentNode = (AFSBTreeEntry *)pCurrentNode->leftLink;
1565                     }
1566
1567                     pCurrentNode->leftLink = pLeftNode;
1568
1569                     pLeftNode->parentLink = pCurrentNode;
1570                 }
1571                 else
1572                 {
1573
1574                     if( pParentNode != NULL)
1575                     {
1576
1577                         // This is where we have a left node with no right node.
1578                         // So, attach the left node to the parent of
1579                         // the removed nodes branch
1580                         if( pParentNode->rightLink == FileIDEntry)
1581                         {
1582
1583                             pParentNode->rightLink = pLeftNode;
1584                         }
1585                         else
1586                         {
1587
1588                             pParentNode->leftLink = pLeftNode;
1589                         }
1590
1591                         pLeftNode->parentLink = pParentNode;
1592                     }
1593                     else
1594                     {
1595
1596                         *TopNode = pLeftNode;
1597
1598                         pLeftNode->parentLink = NULL;
1599                     }
1600                 }
1601             }
1602         }
1603
1604         //
1605         // Cleanup the just removed node
1606         //
1607
1608         FileIDEntry->leftLink = NULL;
1609         FileIDEntry->parentLink = NULL;
1610         FileIDEntry->rightLink = NULL;
1611
1612         ntStatus = STATUS_SUCCESS;
1613     }
1614
1615     return ntStatus;
1616 }