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         else 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
 715             if( pRightNode != NULL)
 716             {
 717
 718                 pRightNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
 719             }
 720
 721             if( pLeftNode != NULL)
 722             {
 723
 724                 pLeftNode->CaseInsensitiveTreeEntry.parentLink = (void *)pNewHeadEntry;
 725             }
 726
 727             pNewHeadEntry->CaseInsensitiveList.bLink = NULL;
 728
 729             pNewHeadEntry->CaseInsensitiveTreeEntry.parentLink = pParentNode;
 730
 731             pNewHeadEntry->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
 732
 733             pNewHeadEntry->CaseInsensitiveTreeEntry.rightLink = pRightNode;
 734
 735             SetFlag( ((AFSDirectoryCB *)DirEntry->CaseInsensitiveList.fLink)->Flags, AFS_DIR_ENTRY_CASE_INSENSTIVE_LIST_HEAD);
 736
 737             try_return( ntStatus);
 738         }
 739
 740         if( (pRightNode == NULL) && (pLeftNode == NULL))
 741         {
 742
 743             if( pParentNode != NULL)
 744             {
 745
 746                 if( pParentNode->CaseInsensitiveTreeEntry.leftLink == DirEntry)
 747                 {
 748
 749                     pParentNode->CaseInsensitiveTreeEntry.leftLink = NULL;
 750                 }
 751                 else
 752                 {
 753
 754                     pParentNode->CaseInsensitiveTreeEntry.rightLink = NULL;
 755                 }
 756             }
 757             else
 758             {
 759
 760                 //
 761                 // Removing the top node
 762                 //
 763
 764                 *RootNode = NULL;
 765             }
 766         }
 767         else
 768         {
 769
 770             if( pRightNode != NULL)
 771             {
 772
 773                 if( pParentNode != NULL)
 774                 {
 775
 776                     // Replace the parent node where this entry was.
 777                     if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
 778                     {
 779
 780                         pParentNode->CaseInsensitiveTreeEntry.rightLink = pRightNode;
 781                     }
 782                     else
 783                     {
 784
 785                         pParentNode->CaseInsensitiveTreeEntry.leftLink = pRightNode;
 786                     }
 787                 }
 788                 else
 789                 {
 790
 791                     *RootNode = pRightNode;
 792
 793                     pRightNode->CaseInsensitiveTreeEntry.parentLink = NULL;
 794                 }
 795
 796                 pRightNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
 797             }
 798
 799             if( pLeftNode != NULL)
 800             {
 801
 802                 // To connect the left node, we must walk the chain of the
 803                 // right nodes left side until we reach the end.
 804                 // At the end attach the leftNode
 805                 if( pRightNode != NULL)
 806                 {
 807
 808                     pCurrentNode = pRightNode;
 809
 810                     while( pCurrentNode->CaseInsensitiveTreeEntry.leftLink != NULL)
 811                     {
 812
 813                         pCurrentNode = (AFSDirectoryCB *)pCurrentNode->CaseInsensitiveTreeEntry.leftLink;
 814                     }
 815
 816                     pCurrentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
 817
 818                     pLeftNode->CaseInsensitiveTreeEntry.parentLink = pCurrentNode;
 819                 }
 820                 else
 821                 {
 822
 823                     if( pParentNode != NULL)
 824                     {
 825
 826                         // This is where we have a left node with no right node.
 827                         // So, attach the left node to the parent of
 828                         // the removed nodes branch
 829                         if( pParentNode->CaseInsensitiveTreeEntry.rightLink == DirEntry)
 830                         {
 831
 832                             pParentNode->CaseInsensitiveTreeEntry.rightLink = pLeftNode;
 833                         }
 834                         else
 835                         {
 836
 837                             pParentNode->CaseInsensitiveTreeEntry.leftLink = pLeftNode;
 838                         }
 839
 840                         pLeftNode->CaseInsensitiveTreeEntry.parentLink = pParentNode;
 841                     }
 842                     else
 843                     {
 844
 845                         *RootNode = pLeftNode;
 846
 847                         pLeftNode->CaseInsensitiveTreeEntry.parentLink = NULL;
 848                     }
 849                 }
 850             }
 851         }
 852
 853 try_exit:
 854
 855         //
 856         // Cleanup the just removed node
 857         //
 858
 859         DirEntry->CaseInsensitiveTreeEntry.leftLink = NULL;
 860         DirEntry->CaseInsensitiveTreeEntry.parentLink = NULL;
 861         DirEntry->CaseInsensitiveTreeEntry.rightLink = NULL;
 862
 863         DirEntry->CaseInsensitiveList.bLink = NULL;
 864         DirEntry->CaseInsensitiveList.fLink = NULL;
 865
 866         ntStatus = STATUS_SUCCESS;
 867     }
 868
 869     return ntStatus;
 870 }
 871
 872 NTSTATUS
 873 AFSLocateShortNameDirEntry( IN AFSDirectoryCB *RootNode,
 874                             IN ULONG Index,
 875                             IN OUT AFSDirectoryCB **DirEntry)
 876 {
 877
 878     NTSTATUS    ntStatus = STATUS_SUCCESS;
 879     AFSDirectoryCB   *pEntry = NULL;
 880     AFSDirectoryCB   *pCurrentEntry = NULL;
 881
 882     pCurrentEntry = RootNode;
 883
 884     __Enter
 885     {
 886
 887         *DirEntry = NULL;
 888
 889         //
 890         // If the rootnode passed is null then the directory is empty
 891         //
 892
 893         if( RootNode == NULL)
 894         {
 895
 896             try_return( ntStatus = STATUS_INVALID_PARAMETER);
 897         }
 898
 899         //
 900         // If the requestor is looking for the root node itself, then return it.
 901         //
 902
 903         if( RootNode->Type.Data.ShortNameTreeEntry.HashIndex == Index)
 904         {
 905
 906             *DirEntry = RootNode;
 907
 908             try_return( ntStatus);
 909         }
 910
 911         //
 912         // Loop through the nodes in the tree
 913         //
 914
 915         while( pCurrentEntry != NULL)
 916         {
 917
 918             //
 919             // Greater values are to the right link.
 920             //
 921
 922             if( Index > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
 923             {
 924
 925                 //
 926                 // Go to the next RIGHT entry, if there is one
 927                 //
 928
 929                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
 930                 {
 931
 932                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
 933                 }
 934                 else
 935                 {
 936
 937                     //
 938                     // Came to the end of the branch so bail
 939                     //
 940
 941                     pCurrentEntry = NULL;
 942
 943                     break;
 944                 }
 945             }
 946             else if( Index < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
 947             {
 948
 949                 //
 950                 // Go to the next LEFT entry, if one exists
 951                 //
 952
 953                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
 954                 {
 955
 956                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
 957                 }
 958                 else
 959                 {
 960
 961                     //
 962                     // End of the branch ...
 963                     //
 964
 965                     pCurrentEntry = NULL;
 966
 967                     break;
 968                 }
 969             }
 970             else
 971             {
 972
 973                 //
 974                 // Found the entry.
 975                 //
 976
 977                 *DirEntry = pCurrentEntry;
 978
 979                 break;
 980             }
 981         }
 982
 983 try_exit:
 984
 985         NOTHING;
 986     }
 987
 988     return ntStatus;
 989 }
 990
 991 NTSTATUS
 992 AFSInsertShortNameDirEntry( IN AFSDirectoryCB *RootNode,
 993                             IN AFSDirectoryCB *DirEntry)
 994 {
 995
 996     NTSTATUS ntStatus = STATUS_SUCCESS;
 997     AFSDirectoryCB *pCurrentEntry = NULL;
 998
 999     pCurrentEntry = RootNode;
1000
1001     __Enter
1002     {
1003
1004         //
1005         // If we have no root node then we can;t start the search.
1006         //
1007
1008         if( pCurrentEntry == NULL)
1009         {
1010
1011             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1012                           AFS_TRACE_LEVEL_WARNING,
1013                           "AFSInsertShortNameDirEntry Invalid root node\n");
1014
1015             try_return( ntStatus = STATUS_UNSUCCESSFUL);
1016         }
1017
1018         //
1019         // Locate the branch end to insert the node
1020         //
1021
1022         while( pCurrentEntry != NULL)
1023         {
1024
1025             //
1026             // Greater valued indices are to the right link
1027             //
1028
1029             if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex > pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1030             {
1031
1032                 //
1033                 // Go to the next RIGHT entry, if it exists
1034                 //
1035
1036                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink != NULL)
1037                 {
1038                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink;
1039                 }
1040                 else
1041                 {
1042
1043                     //
1044                     // Located the end of the branch line so insert the node
1045                     //
1046
1047                     pCurrentEntry->Type.Data.ShortNameTreeEntry.rightLink = (void *)DirEntry;
1048
1049                     DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1050
1051                     break;
1052                 }
1053             }
1054             else if( DirEntry->Type.Data.ShortNameTreeEntry.HashIndex < pCurrentEntry->Type.Data.ShortNameTreeEntry.HashIndex)
1055             {
1056
1057                 //
1058                 // Go to the next LEFT entry, if it exists
1059                 //
1060
1061                 if( pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1062                 {
1063                     pCurrentEntry = (AFSDirectoryCB *)pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink;
1064                 }
1065                 else
1066                 {
1067
1068                     //
1069                     // Located the branch line end so insert the node here
1070                     //
1071
1072                     pCurrentEntry->Type.Data.ShortNameTreeEntry.leftLink = (void *)DirEntry;
1073
1074                     DirEntry->Type.Data.ShortNameTreeEntry.parentLink = (void *)pCurrentEntry;
1075
1076                     break;
1077                 }
1078             }
1079             else
1080             {
1081
1082                 break;
1083             }
1084         }
1085
1086 try_exit:
1087
1088         NOTHING;
1089     }
1090
1091     return ntStatus;
1092 }
1093
1094 NTSTATUS
1095 AFSRemoveShortNameDirEntry( IN AFSDirectoryCB **RootNode,
1096                             IN AFSDirectoryCB *DirEntry)
1097 {
1098
1099     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1100     AFSDirectoryCB *pRightNode = NULL;
1101     AFSDirectoryCB *pLeftNode = NULL;
1102     AFSDirectoryCB *pCurrentNode = NULL;
1103     AFSDirectoryCB *pParentNode = NULL;
1104
1105     pRightNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.rightLink;
1106     pLeftNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.leftLink;
1107     pParentNode = (AFSDirectoryCB *)DirEntry->Type.Data.ShortNameTreeEntry.parentLink;
1108
1109     __Enter
1110     {
1111
1112         if( (pRightNode == NULL) && (pLeftNode == NULL))
1113         {
1114
1115             if( pParentNode != NULL)
1116             {
1117
1118                 if( pParentNode->Type.Data.ShortNameTreeEntry.leftLink == DirEntry)
1119                 {
1120
1121                     pParentNode->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1122                 }
1123                 else
1124                 {
1125
1126                     pParentNode->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1127                 }
1128             }
1129             else
1130             {
1131
1132                 //
1133                 // Removing the top node
1134                 //
1135
1136                 *RootNode = NULL;
1137             }
1138         }
1139         else
1140         {
1141
1142             if( pRightNode != NULL)
1143             {
1144
1145                 if( pParentNode != NULL)
1146                 {
1147
1148                     // Replace the parent node where this entry was.
1149                     if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1150                     {
1151
1152                         pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pRightNode;
1153                     }
1154                     else
1155                     {
1156
1157                         pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pRightNode;
1158                     }
1159                 }
1160                 else
1161                 {
1162
1163                     *RootNode = pRightNode;
1164
1165                     pRightNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1166                 }
1167
1168                 pRightNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1169             }
1170
1171             if( pLeftNode != NULL)
1172             {
1173
1174                 // To connect the left node, we must walk the chain of the
1175                 // right nodes left side until we reach the end.
1176                 // At the end attach the leftNode
1177                 if( pRightNode != NULL)
1178                 {
1179
1180                     pCurrentNode = pRightNode;
1181
1182                     while( pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink != NULL)
1183                     {
1184
1185                         pCurrentNode = (AFSDirectoryCB *)pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink;
1186                     }
1187
1188                     pCurrentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1189
1190                     pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pCurrentNode;
1191                 }
1192                 else
1193                 {
1194
1195                     if( pParentNode != NULL)
1196                     {
1197
1198                         // This is where we have a left node with no right node.
1199                         // So, attach the left node to the parent of
1200                         // the removed nodes branch
1201                         if( pParentNode->Type.Data.ShortNameTreeEntry.rightLink == DirEntry)
1202                         {
1203
1204                             pParentNode->Type.Data.ShortNameTreeEntry.rightLink = pLeftNode;
1205                         }
1206                         else
1207                         {
1208
1209                             pParentNode->Type.Data.ShortNameTreeEntry.leftLink = pLeftNode;
1210                         }
1211
1212                         pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = pParentNode;
1213                     }
1214                     else
1215                     {
1216
1217                         *RootNode = pLeftNode;
1218
1219                         pLeftNode->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1220                     }
1221                 }
1222             }
1223         }
1224
1225         //
1226         // Cleanup the just removed node
1227         //
1228
1229         DirEntry->Type.Data.ShortNameTreeEntry.leftLink = NULL;
1230         DirEntry->Type.Data.ShortNameTreeEntry.parentLink = NULL;
1231         DirEntry->Type.Data.ShortNameTreeEntry.rightLink = NULL;
1232
1233         ntStatus = STATUS_SUCCESS;
1234     }
1235
1236     return ntStatus;
1237 }
1238
1239 NTSTATUS
1240 AFSLocateHashEntry( IN AFSBTreeEntry *TopNode,
1241                     IN ULONGLONG HashIndex,
1242                     IN OUT AFSBTreeEntry **TreeEntry)
1243 {
1244
1245     NTSTATUS         ntStatus = STATUS_SUCCESS;
1246     AFSBTreeEntry   *pEntry = NULL;
1247     AFSBTreeEntry   *pCurrentEntry = NULL;
1248
1249     pCurrentEntry = TopNode;
1250
1251     __Enter
1252     {
1253
1254         //
1255         // If the rootnode passed is null then the directory is empty
1256         //
1257
1258         if( TopNode == NULL)
1259         {
1260
1261             try_return( ntStatus = STATUS_INVALID_PARAMETER);
1262         }
1263
1264         //
1265         // If the requestor is looking for the root node itself, then return it.
1266         //
1267
1268         if( TopNode->HashIndex == HashIndex)
1269         {
1270
1271             *TreeEntry = TopNode;
1272
1273             try_return( ntStatus);
1274         }
1275
1276         //
1277         // Loop through the nodes in the tree
1278         //
1279
1280         while( pCurrentEntry != NULL)
1281         {
1282
1283             //
1284             // Greater values are to the right link.
1285             //
1286
1287             if( HashIndex > pCurrentEntry->HashIndex)
1288             {
1289
1290                 //
1291                 // Go to the next RIGHT entry, if there is one
1292                 //
1293
1294                 if( pCurrentEntry->rightLink != NULL)
1295                 {
1296
1297                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1298                 }
1299                 else
1300                 {
1301
1302                     //
1303                     // Came to the end of the branch so bail
1304                     //
1305
1306                     pCurrentEntry = NULL;
1307
1308                     break;
1309                 }
1310             }
1311             else if( HashIndex < pCurrentEntry->HashIndex)
1312             {
1313
1314                 //
1315                 // Go to the next LEFT entry, if one exists
1316                 //
1317
1318                 if( pCurrentEntry->leftLink != NULL)
1319                 {
1320
1321                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1322                 }
1323                 else
1324                 {
1325
1326                     //
1327                     // End of the branch ...
1328                     //
1329
1330                     pCurrentEntry = NULL;
1331
1332                     break;
1333                 }
1334             }
1335             else
1336             {
1337
1338                 //
1339                 // Found the entry.
1340                 //
1341
1342                 *TreeEntry = pCurrentEntry;
1343
1344                 break;
1345             }
1346         }
1347
1348 try_exit:
1349
1350         NOTHING;
1351     }
1352
1353     return ntStatus;
1354 }
1355
1356 NTSTATUS
1357 AFSInsertHashEntry( IN AFSBTreeEntry *TopNode,
1358                     IN AFSBTreeEntry *FileIDEntry)
1359 {
1360
1361     NTSTATUS ntStatus = STATUS_SUCCESS;
1362     AFSBTreeEntry *pCurrentEntry = NULL;
1363
1364     pCurrentEntry = TopNode;
1365
1366     __Enter
1367     {
1368
1369         //
1370         // If we have no root node then we can;t start the search.
1371         //
1372
1373         if( pCurrentEntry == NULL)
1374         {
1375
1376             AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1377                           AFS_TRACE_LEVEL_WARNING,
1378                           "AFSInsertHashEntry Invalid root node\n");
1379
1380             try_return( ntStatus = STATUS_UNSUCCESSFUL);
1381         }
1382
1383         //
1384         // Locate the branch end to insert the node
1385         //
1386
1387         while( pCurrentEntry != NULL)
1388         {
1389
1390             //
1391             // Greater vlued indices are to the right link
1392             //
1393
1394             if( FileIDEntry->HashIndex > pCurrentEntry->HashIndex)
1395             {
1396
1397                 //
1398                 // Go to the next RIGHT entry, if it exists
1399                 //
1400
1401                 if( pCurrentEntry->rightLink != NULL)
1402                 {
1403                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->rightLink;
1404                 }
1405                 else
1406                 {
1407
1408                     //
1409                     // Located the end of the branch line so insert the node
1410                     //
1411
1412                     pCurrentEntry->rightLink = (void *)FileIDEntry;
1413
1414                     FileIDEntry->parentLink = (void *)pCurrentEntry;
1415
1416                     break;
1417                 }
1418             }
1419             else if( FileIDEntry->HashIndex < pCurrentEntry->HashIndex)
1420             {
1421
1422                 //
1423                 // Go to the next LEFT entry, if it exists
1424                 //
1425
1426                 if( pCurrentEntry->leftLink != NULL)
1427                 {
1428                     pCurrentEntry = (AFSBTreeEntry *)pCurrentEntry->leftLink;
1429                 }
1430                 else
1431                 {
1432
1433                     //
1434                     // Located the branch line end so insert the node here
1435                     //
1436
1437                     pCurrentEntry->leftLink = (void *)FileIDEntry;
1438
1439                     FileIDEntry->parentLink = (void *)pCurrentEntry;
1440
1441                     break;
1442                 }
1443             }
1444             else
1445             {
1446
1447                 AFSDbgLogMsg( AFS_SUBSYSTEM_FILE_PROCESSING,
1448                               AFS_TRACE_LEVEL_WARNING,
1449                               "AFSInsertHashEntry Attempt to re-insert a CRC %I64X\n",
1450                               FileIDEntry->HashIndex);
1451
1452                 ASSERT( FALSE);
1453
1454                 ntStatus = STATUS_UNSUCCESSFUL;
1455
1456                 break;
1457             }
1458         }
1459
1460 try_exit:
1461
1462         NOTHING;
1463     }
1464
1465     return ntStatus;
1466 }
1467
1468 NTSTATUS
1469 AFSRemoveHashEntry( IN AFSBTreeEntry **TopNode,
1470                     IN AFSBTreeEntry *FileIDEntry)
1471 {
1472
1473     NTSTATUS ntStatus = STATUS_UNSUCCESSFUL;
1474     AFSBTreeEntry *pRightNode = NULL;
1475     AFSBTreeEntry *pLeftNode = NULL;
1476     AFSBTreeEntry *pCurrentNode = NULL;
1477     AFSBTreeEntry *pParentNode = NULL;
1478
1479     pRightNode = (AFSBTreeEntry *)FileIDEntry->rightLink;
1480     pLeftNode = (AFSBTreeEntry *)FileIDEntry->leftLink;
1481     pParentNode = (AFSBTreeEntry *)FileIDEntry->parentLink;
1482
1483     __Enter
1484     {
1485
1486         if( (pRightNode == NULL) && (pLeftNode == NULL))
1487         {
1488
1489             if( pParentNode != NULL)
1490             {
1491
1492                 if( pParentNode->leftLink == FileIDEntry)
1493                 {
1494
1495                     pParentNode->leftLink = NULL;
1496                 }
1497                 else
1498                 {
1499
1500                     pParentNode->rightLink = NULL;
1501                 }
1502             }
1503             else
1504             {
1505
1506                 //
1507                 // Removing the top node
1508                 //
1509
1510                 *TopNode = NULL;
1511             }
1512         }
1513         else
1514         {
1515
1516             if( pRightNode != NULL)
1517             {
1518
1519                 if( pParentNode != NULL)
1520                 {
1521
1522                     // Replace the parent node where this entry was.
1523                     if( pParentNode->rightLink == FileIDEntry)
1524                     {
1525
1526                         pParentNode->rightLink = pRightNode;
1527                     }
1528                     else
1529                     {
1530
1531                         pParentNode->leftLink = pRightNode;
1532                     }
1533                 }
1534                 else
1535                 {
1536
1537                     *TopNode = pRightNode;
1538
1539                     pRightNode->parentLink = NULL;
1540                 }
1541
1542                 pRightNode->parentLink = pParentNode;
1543             }
1544
1545             if( pLeftNode != NULL)
1546             {
1547
1548                 // To connect the left node, we must walk the chain of the
1549                 // right nodes left side until we reach the end.
1550                 // At the end attach the leftNode
1551                 if( pRightNode != NULL)
1552                 {
1553
1554                     pCurrentNode = pRightNode;
1555
1556                     while( pCurrentNode->leftLink != NULL)
1557                     {
1558
1559                         pCurrentNode = (AFSBTreeEntry *)pCurrentNode->leftLink;
1560                     }
1561
1562                     pCurrentNode->leftLink = pLeftNode;
1563
1564                     pLeftNode->parentLink = pCurrentNode;
1565                 }
1566                 else
1567                 {
1568
1569                     if( pParentNode != NULL)
1570                     {
1571
1572                         // This is where we have a left node with no right node.
1573                         // So, attach the left node to the parent of
1574                         // the removed nodes branch
1575                         if( pParentNode->rightLink == FileIDEntry)
1576                         {
1577
1578                             pParentNode->rightLink = pLeftNode;
1579                         }
1580                         else
1581                         {
1582
1583                             pParentNode->leftLink = pLeftNode;
1584                         }
1585
1586                         pLeftNode->parentLink = pParentNode;
1587                     }
1588                     else
1589                     {
1590
1591                         *TopNode = pLeftNode;
1592
1593                         pLeftNode->parentLink = NULL;
1594                     }
1595                 }
1596             }
1597         }
1598
1599         //
1600         // Cleanup the just removed node
1601         //
1602
1603         FileIDEntry->leftLink = NULL;
1604         FileIDEntry->parentLink = NULL;
1605         FileIDEntry->rightLink = NULL;
1606
1607         ntStatus = STATUS_SUCCESS;
1608     }
1609
1610     return ntStatus;
1611 }