livefiles_hfs_plugin/lf_hfs_btree_tree_ops.c

   1 //
   2 //  lf_hfs_btree_tree_ops.c
   3 //  livefiles_hfs
   4 //
   5 //  Created by Yakov Ben Zaken on 22/03/2018.
   6 //
   7
   8 #include "lf_hfs_btrees_private.h"
   9 #include "lf_hfs_btrees_io.h"
  10 #include "lf_hfs_utils.h"
  11 #include "lf_hfs_generic_buf.h"
  12 //
  13 /////////////////////// Routines Internal To BTree Module ///////////////////////
  14 //
  15 //    SearchTree
  16 //    InsertTree
  17 //
  18 ////////////////////// Routines Internal To BTreeTreeOps.c //////////////////////
  19
  20 static OSStatus   AddNewRootNode    (BTreeControlBlockPtr         btreePtr,
  21                                      NodeDescPtr                 leftNode,
  22                                      NodeDescPtr                 rightNode );
  23
  24 static OSStatus   CollapseTree        (BTreeControlBlockPtr         btreePtr,
  25                                        BlockDescriptor            *blockPtr );
  26
  27 static OSStatus   RotateLeft        (BTreeControlBlockPtr         btreePtr,
  28                                      NodeDescPtr                 leftNode,
  29                                      NodeDescPtr                 rightNode,
  30                                      u_int16_t                     rightInsertIndex,
  31                                      KeyPtr                         keyPtr,
  32                                      u_int8_t *                     recPtr,
  33                                      u_int16_t                     recSize,
  34                                      u_int16_t                    *insertIndex,
  35                                      u_int32_t                    *insertNodeNum,
  36                                      Boolean                    *recordFit,
  37                                      u_int16_t                    *recsRotated );
  38
  39 static Boolean       RotateRecordLeft    (BTreeControlBlockPtr         btreePtr,
  40                                           NodeDescPtr                 leftNode,
  41                                           NodeDescPtr                 rightNode );
  42
  43 static OSStatus       SplitLeft        (BTreeControlBlockPtr         btreePtr,
  44                                         BlockDescriptor            *leftNode,
  45                                         BlockDescriptor            *rightNode,
  46                                         u_int32_t                     rightNodeNum,
  47                                         u_int16_t                     index,
  48                                         KeyPtr                         keyPtr,
  49                                         u_int8_t *                     recPtr,
  50                                         u_int16_t                     recSize,
  51                                         u_int16_t                    *insertIndex,
  52                                         u_int32_t                    *insertNodeNum,
  53                                         u_int16_t                    *recsRotated );
  54
  55
  56
  57 static    OSStatus    InsertLevel        (BTreeControlBlockPtr         btreePtr,
  58                                           TreePathTable                 treePathTable,
  59                                           InsertKey                    *primaryKey,
  60                                           InsertKey                    *secondaryKey,
  61                                           BlockDescriptor            *targetNode,
  62                                           u_int16_t                     index,
  63                                           u_int16_t                     level,
  64                                           u_int32_t                    *insertNode );
  65
  66 static OSErr        InsertNode         (BTreeControlBlockPtr         btreePtr,
  67                                         InsertKey                    *key,
  68                                         BlockDescriptor            *rightNode,
  69                                         u_int32_t                     node,
  70                                         u_int16_t                      index,
  71                                         u_int32_t                    *newNode,
  72                                         u_int16_t                    *newIndex,
  73                                         BlockDescriptor            *leftNode,
  74                                         Boolean                    *updateParent,
  75                                         Boolean                    *insertParent,
  76                                         Boolean                    *rootSplit );
  77
  78 static u_int16_t        GetKeyLength    (const BTreeControlBlock *btreePtr,
  79                                          const BTreeKey *key,
  80                                          Boolean forLeafNode );
  81
  82
  83
  84 //////////////////////// BTree Multi-node Tree Operations ///////////////////////
  85
  86
  87 /*-------------------------------------------------------------------------------
  88
  89  Routine:    SearchTree    -    Search BTree for key and set up Tree Path Table.
  90
  91  Function:    Searches BTree for specified key, setting up the Tree Path Table to
  92  reflect the search path.
  93
  94
  95  Input:        btreePtr        - pointer to control block of BTree to search
  96  keyPtr            - pointer to the key to search for
  97  treePathTable    - pointer to the tree path table to construct
  98
  99  Output:        nodeNum            - number of the node containing the key position
 100  iterator        - BTreeIterator specifying record or insert position
 101
 102  Result:        noErr            - key found, index is record index
 103  fsBTRecordNotFoundErr    - key not found, index is insert index
 104  fsBTEmptyErr        - key not found, return params are nil
 105  otherwise            - catastrophic failure (GetNode/ReleaseNode failed)
 106  -------------------------------------------------------------------------------*/
 107
 108 OSStatus    SearchTree    (BTreeControlBlockPtr     btreePtr,
 109                            BTreeKeyPtr             searchKey,
 110                            TreePathTable             treePathTable,
 111                            u_int32_t                *nodeNum,
 112                            BlockDescriptor        *nodePtr,
 113                            u_int16_t                *returnIndex )
 114 {
 115     OSStatus    err;
 116     int16_t        level;                    //    Expected depth of current node
 117     u_int32_t    curNodeNum;                //    Current node we're searching
 118     NodeRec        nodeRec;
 119     u_int16_t    index;
 120     Boolean        keyFound;
 121     int8_t        nodeKind;                //    Kind of current node (index/leaf)
 122     KeyPtr        keyPtr;
 123     u_int8_t *    dataPtr;
 124     u_int16_t    dataSize;
 125
 126
 127     curNodeNum        = btreePtr->rootNode;
 128     level            = btreePtr->treeDepth;
 129
 130     if (level == 0)                        // is the tree empty?
 131     {
 132         err = fsBTEmptyErr;
 133         goto ErrorExit;
 134     }
 135
 136     //for debugging...
 137     treePathTable [0].node        = 0;
 138     treePathTable [0].index        = 0;
 139
 140     while (true)
 141     {
 142         //
 143         //    [2550929] Node number 0 is the header node.  It is never a valid
 144         //    index or leaf node.  If we're ever asked to search through node 0,
 145         //    something has gone wrong (typically a bad child node number, or
 146         //    we found a node full of zeroes that we thought was an index node).
 147         //
 148         if (curNodeNum == 0)
 149         {
 150             LFHFS_LOG(LEVEL_ERROR, "SearchTree: curNodeNum is zero!");
 151             err = btBadNode;
 152             goto ErrorExit;
 153         }
 154
 155         err = GetNode (btreePtr, curNodeNum, 0, &nodeRec);
 156         if (err != noErr)
 157         {
 158             LFHFS_LOG(LEVEL_ERROR, "SearchTree: GetNode returned with error %d!",err);
 159             goto ErrorExit;
 160         }
 161
 162         //
 163         //    [2550929] Sanity check the node height and node type.  We expect
 164         //    particular values at each iteration in the search.  This checking
 165         //    quickly finds bad pointers, loops, and other damage to the
 166         //    hierarchy of the B-tree.
 167         //
 168         if (((BTNodeDescriptor*)nodeRec.buffer)->height != level)
 169         {
 170             LFHFS_LOG(LEVEL_ERROR, "Incorrect node height");
 171             err = btBadNode;
 172             goto ReleaseAndExit;
 173         }
 174         nodeKind = ((BTNodeDescriptor*)nodeRec.buffer)->kind;
 175         if (level == 1)
 176         {
 177             //    Nodes at level 1 must be leaves, by definition
 178             if (nodeKind != kBTLeafNode)
 179             {
 180                 LFHFS_LOG(LEVEL_ERROR, "Incorrect node type: expected leaf");
 181                 err = btBadNode;
 182                 goto ReleaseAndExit;
 183             }
 184         }
 185         else
 186         {
 187             //    A node at any other depth must be an index node
 188             if (nodeKind != kBTIndexNode)
 189             {
 190                 LFHFS_LOG(LEVEL_ERROR, "Incorrect node type: expected index");
 191                 err = btBadNode;
 192                 goto ReleaseAndExit;
 193             }
 194         }
 195
 196         keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index);
 197
 198         treePathTable [level].node        = curNodeNum;
 199
 200         if (nodeKind == kBTLeafNode)
 201         {
 202             treePathTable [level].index = index;
 203             break;            // were done...
 204         }
 205
 206         if ( (keyFound != true) && (index != 0))
 207             --index;
 208
 209         treePathTable [level].index = index;
 210
 211         err = GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize);
 212         if (err != noErr)
 213         {
 214             //    [2550929] If we got an error, it is probably because the index was bad
 215             //    (typically a corrupt node that confused SearchNode).  Invalidate the node
 216             //    so we won't accidentally use the corrupted contents.  NOTE: the Mac OS 9
 217             //    sources call this InvalidateNode.
 218             LFHFS_LOG(LEVEL_ERROR, "SearchTree: GetRecordByIndex returned with errpr %d!",err);
 219
 220             (void) TrashNode(btreePtr, &nodeRec);
 221             goto ErrorExit;
 222         }
 223
 224         //    Get the child pointer out of this index node.  We're now done with the current
 225         //    node and can continue the search with the child node.
 226         curNodeNum = *(u_int32_t *)dataPtr;
 227         err = ReleaseNode (btreePtr, &nodeRec);
 228         if (err != noErr)
 229         {
 230             LFHFS_LOG(LEVEL_ERROR, "SearchTree: ReleaseNode returned with errpr %d!",err);
 231             goto ErrorExit;
 232         }
 233
 234         //    The child node should be at a level one less than the parent.
 235         --level;
 236     }
 237
 238     *nodeNum            = curNodeNum;
 239     *nodePtr            = nodeRec;
 240     *returnIndex        = index;
 241
 242     if (keyFound)
 243         return    noErr;            // searchKey found, index identifies record in node
 244     else
 245         return    fsBTRecordNotFoundErr;    // searchKey not found, index identifies insert point
 246
 247 ReleaseAndExit:
 248     (void) ReleaseNode(btreePtr, &nodeRec);
 249     //    fall into ErrorExit
 250
 251 ErrorExit:
 252
 253     *nodeNum                    = 0;
 254     nodePtr->buffer                = nil;
 255     nodePtr->blockHeader        = nil;
 256     *returnIndex                = 0;
 257     return    err;
 258 }
 259
 260 ////////////////////////////////// InsertTree ///////////////////////////////////
 261
 262 OSStatus    InsertTree ( BTreeControlBlockPtr         btreePtr,
 263                         TreePathTable                 treePathTable,
 264                         KeyPtr                         keyPtr,
 265                         u_int8_t *                     recPtr,
 266                         u_int16_t                     recSize,
 267                         BlockDescriptor            *targetNode,
 268                         u_int16_t                     index,
 269                         u_int16_t                     level,
 270                         Boolean                     replacingKey,
 271                         u_int32_t                    *insertNode )
 272 {
 273     InsertKey            primaryKey;
 274     OSStatus            err;
 275
 276     primaryKey.keyPtr        = keyPtr;
 277     primaryKey.keyLength    = GetKeyLength(btreePtr, primaryKey.keyPtr, (level == 1));
 278     primaryKey.recPtr        = recPtr;
 279     primaryKey.recSize        = recSize;
 280     primaryKey.replacingKey    = replacingKey;
 281     primaryKey.skipRotate    = false;
 282
 283     err    = InsertLevel (btreePtr, treePathTable, &primaryKey, nil,
 284                           targetNode, index, level, insertNode );
 285
 286     return err;
 287
 288 } // End of InsertTree
 289
 290
 291 ////////////////////////////////// InsertLevel //////////////////////////////////
 292
 293 OSStatus    InsertLevel (BTreeControlBlockPtr         btreePtr,
 294                          TreePathTable                 treePathTable,
 295                          InsertKey                    *primaryKey,
 296                          InsertKey                    *secondaryKey,
 297                          BlockDescriptor            *targetNode,
 298                          u_int16_t                     index,
 299                          u_int16_t                     level,
 300                          u_int32_t                    *insertNode )
 301 {
 302     OSStatus             err;
 303     BlockDescriptor         leftNode;
 304     u_int32_t             targetNodeNum;
 305     u_int32_t             newNodeNum;
 306     u_int16_t             newIndex;
 307     Boolean                 insertParent;
 308     Boolean                 updateParent;
 309     Boolean                 newRoot;
 310     InsertKey            insertKey;
 311
 312 #if defined(applec) && !defined(__SC__)
 313     if ((level == 1) && (((NodeDescPtr)targetNode->buffer)->kind != kBTLeafNode))
 314     {
 315         LFHFS_LOG(LEVEL_ERROR, " InsertLevel: non-leaf at level 1! ");
 316         hfs_assert(0);
 317     }
 318 #endif
 319     leftNode.buffer = nil;
 320     leftNode.blockHeader = nil;
 321     targetNodeNum = treePathTable [level].node;
 322
 323     insertParent = false;
 324     updateParent = false;
 325
 326     // XXXdbg
 327     ModifyBlockStart(btreePtr->fileRefNum, targetNode);
 328
 329     ////// process first insert //////
 330
 331     err = InsertNode (btreePtr, primaryKey, targetNode, targetNodeNum, index,
 332                       &newNodeNum, &newIndex, &leftNode, &updateParent, &insertParent, &newRoot );
 333     M_ExitOnError (err);
 334
 335     if ( newRoot )
 336     {
 337         // Extend the treePathTable by adding an entry for the new
 338         // root node that references the current targetNode.
 339         //
 340         // If inserting the secondaryKey changes the first key of
 341         // the target node, then we'll have to update the second
 342         // key in the new root node.
 343
 344         treePathTable [level + 1].node  = btreePtr->rootNode;
 345         treePathTable [level + 1].index = 1;    // 1 since we always split/rotate left
 346     }
 347
 348     if ( level == 1 )
 349         *insertNode = newNodeNum;
 350
 351     ////// process second insert (if any) //////
 352
 353     if  ( secondaryKey != nil )
 354     {
 355         Boolean                temp;
 356
 357         err = InsertNode (btreePtr, secondaryKey, targetNode, newNodeNum, newIndex,
 358                           &newNodeNum, &newIndex, &leftNode, &updateParent, &insertParent, &temp);
 359         M_ExitOnError (err);
 360     }
 361
 362     //////////////////////// Update Parent(s) ///////////////////////////////
 363
 364     if ( insertParent || updateParent )
 365     {
 366         BlockDescriptor        parentNode;
 367         u_int32_t            parentNodeNum;
 368         KeyPtr                keyPtr;
 369         u_int8_t *            recPtr;
 370         u_int16_t            recSize;
 371
 372         parentNode.buffer = nil;
 373         parentNode.blockHeader = nil;
 374
 375         secondaryKey = nil;
 376
 377         if (level == btreePtr->treeDepth)
 378         {
 379             LFHFS_LOG(LEVEL_ERROR, " InsertLevel: unfinished insert!?");
 380             hfs_assert(0);
 381         }
 382         ++level;
 383
 384         // Get Parent Node data...
 385         index = treePathTable [level].index;
 386         parentNodeNum = treePathTable [level].node;
 387
 388         if (parentNodeNum == 0)
 389         {
 390             LFHFS_LOG(LEVEL_ERROR, " InsertLevel: parent node is zero!?");
 391             hfs_assert(0);
 392         }
 393
 394         err = GetNode (btreePtr, parentNodeNum, 0, &parentNode);    // released as target node in next level up
 395         M_ExitOnError (err);
 396         ////////////////////////// Update Parent Index //////////////////////////////
 397
 398         if ( updateParent )
 399         {
 400             // XXXdbg
 401             ModifyBlockStart(btreePtr->fileRefNum, &parentNode);
 402
 403             // debug: check if ptr == targetNodeNum
 404             GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
 405             if ((*(u_int32_t *) recPtr) != targetNodeNum)
 406             {
 407                 LFHFS_LOG(LEVEL_ERROR, " InsertLevel: parent ptr doesn't match target node!");
 408                 hfs_assert(0);
 409             }
 410
 411             // need to delete and re-insert this parent key/ptr
 412             // we delete it here and it gets re-inserted in the
 413             // InsertLevel call below.
 414             DeleteRecord (btreePtr, parentNode.buffer, index);
 415
 416             primaryKey->keyPtr         = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
 417             primaryKey->keyLength     = GetKeyLength(btreePtr, primaryKey->keyPtr, false);
 418             primaryKey->recPtr         = (u_int8_t *) &targetNodeNum;
 419             primaryKey->recSize         = sizeof(targetNodeNum);
 420             primaryKey->replacingKey = kReplaceRecord;
 421             primaryKey->skipRotate   = insertParent;        // don't rotate left if we have two inserts occuring
 422         }
 423
 424         ////////////////////////// Add New Parent Index /////////////////////////////
 425
 426         if ( insertParent )
 427         {
 428             InsertKey    *insertKeyPtr;
 429
 430             if ( updateParent )
 431             {
 432                 insertKeyPtr = &insertKey;
 433                 secondaryKey = &insertKey;
 434             }
 435             else
 436             {
 437                 insertKeyPtr = primaryKey;
 438             }
 439
 440             insertKeyPtr->keyPtr        = (KeyPtr) GetRecordAddress (btreePtr, leftNode.buffer, 0);
 441             insertKeyPtr->keyLength        = GetKeyLength(btreePtr, insertKeyPtr->keyPtr, false);
 442             insertKeyPtr->recPtr        = (u_int8_t *) &((NodeDescPtr)targetNode->buffer)->bLink;
 443             insertKeyPtr->recSize        = sizeof(u_int32_t);
 444             insertKeyPtr->replacingKey    = kInsertRecord;
 445             insertKeyPtr->skipRotate    = false;        // a rotate is OK during second insert
 446         }
 447
 448         err = InsertLevel (btreePtr, treePathTable, primaryKey, secondaryKey,
 449                            &parentNode, index, level, insertNode );
 450         M_ExitOnError (err);
 451     }
 452
 453     err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);    // all done with target
 454     M_ExitOnError (err);
 455
 456     err = UpdateNode (btreePtr, &leftNode, 0, kLockTransaction);        // all done with left sibling
 457     M_ExitOnError (err);
 458
 459     return    noErr;
 460
 461 ErrorExit:
 462
 463     (void) ReleaseNode (btreePtr, targetNode);
 464     (void) ReleaseNode (btreePtr, &leftNode);
 465
 466     LFHFS_LOG(LEVEL_ERROR, " InsertLevel: an error occurred!");
 467
 468     return    err;
 469
 470 } // End of InsertLevel
 471
 472
 473
 474 ////////////////////////////////// InsertNode ///////////////////////////////////
 475
 476 static OSErr    InsertNode    (BTreeControlBlockPtr     btreePtr,
 477                                InsertKey                *key,
 478
 479                                BlockDescriptor        *rightNode,
 480                                u_int32_t                 node,
 481                                u_int16_t                  index,
 482
 483                                u_int32_t                *newNode,
 484                                u_int16_t                *newIndex,
 485
 486                                BlockDescriptor        *leftNode,
 487                                Boolean                *updateParent,
 488                                Boolean                *insertParent,
 489                                Boolean                *rootSplit )
 490 {
 491     BlockDescriptor        *targetNode = NULL;
 492     u_int32_t             leftNodeNum;
 493     u_int16_t             recsRotated;
 494     OSErr                 err;
 495     Boolean                 recordFit;
 496
 497     *rootSplit = false;
 498
 499     if (rightNode->buffer == leftNode->buffer)
 500     {
 501         LFHFS_LOG(LEVEL_ERROR, " InsertNode: rightNode == leftNode");
 502         hfs_assert(0);
 503     }
 504
 505     leftNodeNum = ((NodeDescPtr) rightNode->buffer)->bLink;
 506
 507
 508     /////////////////////// Try Simple Insert ///////////////////////////////
 509
 510     /* sanity check our left and right nodes here. */
 511     if (node == leftNodeNum) {
 512         if (leftNode->buffer == NULL) {
 513             err = fsBTInvalidNodeErr;
 514             M_ExitOnError(err);
 515         }
 516         else{
 517             targetNode = leftNode;
 518         }
 519     }
 520     else {
 521         // we can assume right node is initialized.
 522         targetNode = rightNode;
 523     }
 524
 525
 526     recordFit = InsertKeyRecord (btreePtr, targetNode->buffer, index, key->keyPtr, key->keyLength, key->recPtr, key->recSize);
 527
 528     if ( recordFit )
 529     {
 530         *newNode  = node;
 531         *newIndex = index;
 532
 533         if ( (index == 0) && (((NodeDescPtr) targetNode->buffer)->height != btreePtr->treeDepth) )
 534             *updateParent = true;    // the first record changed so we need to update the parent
 535     }
 536
 537
 538     //////////////////////// Try Rotate Left ////////////////////////////////
 539
 540     if ( !recordFit && leftNodeNum > 0 )
 541     {
 542         if (leftNode->buffer != nil)
 543         {
 544             LFHFS_LOG(LEVEL_ERROR, " InsertNode: leftNode already acquired!");
 545             hfs_assert(0);
 546         }
 547
 548         if ( leftNode->buffer == nil )
 549         {
 550             err = GetNode (btreePtr, leftNodeNum, 0, leftNode);    // will be released by caller or a split below
 551             M_ExitOnError (err);
 552             // XXXdbg
 553             ModifyBlockStart(btreePtr->fileRefNum, leftNode);
 554         }
 555
 556         if (((NodeDescPtr) leftNode->buffer)->fLink != node)
 557         {
 558             LFHFS_LOG(LEVEL_ERROR, " InsertNode, RotateLeft: invalid sibling link!");
 559             hfs_assert(0);
 560         }
 561
 562         if ( !key->skipRotate )        // are rotates allowed?
 563         {
 564             err = RotateLeft (btreePtr, leftNode->buffer, rightNode->buffer, index, key->keyPtr, key->recPtr,
 565                               key->recSize, newIndex, newNode, &recordFit, &recsRotated );
 566             M_ExitOnError (err);
 567
 568             if ( recordFit )
 569             {
 570                 if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
 571                     *updateParent = true;
 572             }
 573         }
 574     }
 575
 576
 577     //////////////////////// Try Split Left /////////////////////////////////
 578
 579     if ( !recordFit )
 580     {
 581         // might not have left node...
 582         err = SplitLeft (btreePtr, leftNode, rightNode, node, index, key->keyPtr,
 583                          key->recPtr, key->recSize, newIndex, newNode, &recsRotated);
 584         M_ExitOnError (err);
 585
 586         // if we split root node - add new root
 587
 588         if ( ((NodeDescPtr) rightNode->buffer)->height == btreePtr->treeDepth )
 589         {
 590             err = AddNewRootNode (btreePtr, leftNode->buffer, rightNode->buffer);    // Note: does not update TPT
 591             M_ExitOnError (err);
 592             *rootSplit = true;
 593         }
 594         else
 595         {
 596             *insertParent = true;
 597
 598             if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
 599                 *updateParent = true;
 600         }
 601     }
 602
 603     return noErr;
 604
 605 ErrorExit:
 606     (void) ReleaseNode (btreePtr, leftNode);
 607     return err;
 608
 609 } // End of InsertNode
 610
 611
 612 /*-------------------------------------------------------------------------------
 613  Routine:    DeleteTree    -    One_line_description.
 614
 615  Function:    Brief_description_of_the_function_and_any_side_effects
 616
 617  ToDo:
 618
 619  Input:        btreePtr        - description
 620  treePathTable    - description
 621  targetNode        - description
 622  index            - description
 623
 624  Result:        noErr        - success
 625  != noErr    - failure
 626  -------------------------------------------------------------------------------*/
 627
 628 OSStatus    DeleteTree            (BTreeControlBlockPtr         btreePtr,
 629                                    TreePathTable                 treePathTable,
 630                                    BlockDescriptor            *targetNode,
 631                                    u_int16_t                     index,
 632                                    u_int16_t                     level )
 633 {
 634     OSStatus            err;
 635     BlockDescriptor        parentNode;
 636     BTNodeDescriptor    *targetNodePtr;
 637     u_int32_t            targetNodeNum;
 638     Boolean                deleteRequired;
 639     Boolean                updateRequired;
 640
 641     // XXXdbg - initialize these to null in case we get an
 642     //          error and try to exit before it's initialized
 643     parentNode.buffer      = nil;
 644     parentNode.blockHeader = nil;
 645
 646     deleteRequired = false;
 647     updateRequired = false;
 648
 649     targetNodeNum = treePathTable[level].node;
 650     targetNodePtr = targetNode->buffer;
 651     if (targetNodePtr == nil)
 652     {
 653         LFHFS_LOG(LEVEL_ERROR, "DeleteTree: targetNode has nil buffer!");
 654         hfs_assert(0);
 655     }
 656
 657     // XXXdbg
 658     ModifyBlockStart(btreePtr->fileRefNum, targetNode);
 659
 660     DeleteRecord (btreePtr, targetNodePtr, index);
 661
 662     //coalesce remaining records?
 663
 664     if ( targetNodePtr->numRecords == 0 )    // did we delete the last record?
 665     {
 666         BlockDescriptor        siblingNode;
 667         u_int32_t            siblingNodeNum;
 668
 669         deleteRequired = true;
 670
 671         siblingNode.buffer = nil;
 672         siblingNode.blockHeader = nil;
 673
 674         ////////////////// Get Siblings & Update Links //////////////////////////
 675
 676         siblingNodeNum = targetNodePtr->bLink;                // Left Sibling Node
 677         if ( siblingNodeNum != 0 )
 678         {
 679             err = GetNode (btreePtr, siblingNodeNum, 0, &siblingNode);
 680             M_ExitOnError (err);
 681
 682             // XXXdbg
 683             ModifyBlockStart(btreePtr->fileRefNum, &siblingNode);
 684
 685             ((NodeDescPtr)siblingNode.buffer)->fLink = targetNodePtr->fLink;
 686             err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction);
 687             M_ExitOnError (err);
 688         }
 689         else if ( targetNodePtr->kind == kBTLeafNode )        // update firstLeafNode
 690         {
 691             btreePtr->firstLeafNode = targetNodePtr->fLink;
 692         }
 693
 694         siblingNodeNum = targetNodePtr->fLink;                // Right Sibling Node
 695         if ( siblingNodeNum != 0 )
 696         {
 697             err = GetNode (btreePtr, siblingNodeNum, 0, &siblingNode);
 698             M_ExitOnError (err);
 699
 700             // XXXdbg
 701             ModifyBlockStart(btreePtr->fileRefNum, &siblingNode);
 702
 703             ((NodeDescPtr)siblingNode.buffer)->bLink = targetNodePtr->bLink;
 704             err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction);
 705             M_ExitOnError (err);
 706         }
 707         else if ( targetNodePtr->kind == kBTLeafNode )        // update lastLeafNode
 708         {
 709             btreePtr->lastLeafNode = targetNodePtr->bLink;
 710         }
 711
 712         //////////////////////// Free Empty Node ////////////////////////////////
 713
 714         GenericLFBuf *psBuf = targetNode->blockHeader;
 715         lf_hfs_generic_buf_set_cache_flag(psBuf, GEN_BUF_LITTLE_ENDIAN);
 716         ClearNode (btreePtr, targetNodePtr);
 717
 718         err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);
 719         M_ExitOnError (err);
 720
 721         err = FreeNode (btreePtr, targetNodeNum);
 722         M_ExitOnError (err);
 723     }
 724     else if ( index == 0 )            // did we delete the first record?
 725     {
 726         updateRequired = true;        // yes, so we need to update parent
 727     }
 728
 729
 730     if ( level == btreePtr->treeDepth )        // then targetNode->buffer is the root node
 731     {
 732         deleteRequired = false;
 733         updateRequired = false;
 734
 735         if ( targetNode->buffer == nil )    // then root was freed and the btree is empty
 736         {
 737             btreePtr->rootNode  = 0;
 738             btreePtr->treeDepth = 0;
 739         }
 740         else if ( ((NodeDescPtr)targetNode->buffer)->numRecords == 1 )
 741         {
 742             err = CollapseTree (btreePtr, targetNode);
 743             M_ExitOnError (err);
 744         }
 745     }
 746
 747
 748     if ( updateRequired || deleteRequired )
 749     {
 750         ++level;    // next level
 751
 752         //// Get Parent Node and index
 753         index = treePathTable [level].index;
 754         err = GetNode (btreePtr, treePathTable[level].node, 0, &parentNode);
 755         M_ExitOnError (err);
 756
 757         if ( updateRequired )
 758         {
 759             KeyPtr        keyPtr;
 760             u_int8_t *    recPtr;
 761             u_int16_t    recSize;
 762             u_int32_t    insertNode;
 763
 764             // XXXdbg
 765             ModifyBlockStart(btreePtr->fileRefNum, &parentNode);
 766
 767             //debug: check if ptr == targetNodeNum
 768             GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
 769             if ((*(u_int32_t *) recPtr) != targetNodeNum)
 770             {
 771                 LFHFS_LOG(LEVEL_ERROR, " DeleteTree: parent ptr doesn't match targetNodeNum!!");
 772                 hfs_assert(0);
 773             }
 774
 775             // need to delete and re-insert this parent key/ptr
 776             DeleteRecord (btreePtr, parentNode.buffer, index);
 777
 778             keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
 779             recPtr = (u_int8_t *) &targetNodeNum;
 780             recSize = sizeof(targetNodeNum);
 781
 782             err = InsertTree (btreePtr, treePathTable, keyPtr, recPtr, recSize,
 783                               &parentNode, index, level, kReplaceRecord, &insertNode);
 784             M_ExitOnError (err);
 785         }
 786         else // deleteRequired
 787         {
 788             err = DeleteTree (btreePtr, treePathTable, &parentNode, index, level);
 789             M_ExitOnError (err);
 790         }
 791     }
 792
 793
 794     err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);
 795     M_ExitOnError (err);
 796
 797     return    noErr;
 798
 799 ErrorExit:
 800
 801     (void) ReleaseNode (btreePtr, targetNode);
 802     (void) ReleaseNode (btreePtr, &parentNode);
 803
 804     return    err;
 805
 806 } // end DeleteTree
 807
 808
 809
 810 ///////////////////////////////// CollapseTree //////////////////////////////////
 811
 812 static OSStatus    CollapseTree    (BTreeControlBlockPtr        btreePtr,
 813                                     BlockDescriptor            *blockPtr )
 814 {
 815     OSStatus        err;
 816     u_int32_t        originalRoot;
 817     u_int32_t        nodeNum;
 818
 819     originalRoot    = btreePtr->rootNode;
 820
 821     // XXXdbg
 822     ModifyBlockStart(btreePtr->fileRefNum, blockPtr);
 823
 824     while (true)
 825     {
 826         if ( ((NodeDescPtr)blockPtr->buffer)->numRecords > 1)
 827             break;                            // this will make a fine root node
 828
 829         if ( ((NodeDescPtr)blockPtr->buffer)->kind == kBTLeafNode)
 830             break;                            // we've hit bottom
 831
 832         nodeNum               = btreePtr->rootNode;
 833         btreePtr->rootNode    = GetChildNodeNum (btreePtr, blockPtr->buffer, 0);
 834         --btreePtr->treeDepth;
 835
 836         //// Clear and Free Current Old Root Node ////
 837         GenericLFBuf *psBuf = blockPtr->blockHeader;
 838         lf_hfs_generic_buf_set_cache_flag(psBuf, GEN_BUF_LITTLE_ENDIAN);
 839         ClearNode (btreePtr, blockPtr->buffer);
 840         err = UpdateNode (btreePtr, blockPtr, 0, kLockTransaction);
 841         M_ExitOnError (err);
 842         err = FreeNode (btreePtr, nodeNum);
 843         M_ExitOnError (err);
 844
 845         //// Get New Root Node
 846         err = GetNode (btreePtr, btreePtr->rootNode, 0, blockPtr);
 847         M_ExitOnError (err);
 848
 849         // XXXdbg
 850         ModifyBlockStart(btreePtr->fileRefNum, blockPtr);
 851     }
 852
 853     if (btreePtr->rootNode != originalRoot)
 854         M_BTreeHeaderDirty (btreePtr);
 855
 856     err = UpdateNode (btreePtr, blockPtr, 0, kLockTransaction);    // always update!
 857     M_ExitOnError (err);
 858
 859     return    noErr;
 860
 861
 862     /////////////////////////////////// ErrorExit ///////////////////////////////////
 863
 864 ErrorExit:
 865     (void)    ReleaseNode (btreePtr, blockPtr);
 866     return    err;
 867 }
 868
 869
 870
 871 ////////////////////////////////// RotateLeft ///////////////////////////////////
 872
 873 /*-------------------------------------------------------------------------------
 874
 875  Routine:    RotateLeft    -    One_line_description.
 876
 877  Function:    Brief_description_of_the_function_and_any_side_effects
 878
 879  Algorithm:    if rightIndex > insertIndex, subtract 1 for actual rightIndex
 880
 881  Input:        btreePtr            - description
 882  leftNode            - description
 883  rightNode            - description
 884  rightInsertIndex    - description
 885  keyPtr                - description
 886  recPtr                - description
 887  recSize                - description
 888
 889  Output:        insertIndex
 890  insertNodeNum        - description
 891  recordFit            - description
 892  recsRotated
 893
 894  Result:        noErr        - success
 895  != noErr    - failure
 896  -------------------------------------------------------------------------------*/
 897
 898 static OSStatus    RotateLeft        (BTreeControlBlockPtr         btreePtr,
 899                                       NodeDescPtr                 leftNode,
 900                                       NodeDescPtr                 rightNode,
 901                                       u_int16_t                     rightInsertIndex,
 902                                       KeyPtr                         keyPtr,
 903                                       u_int8_t *                     recPtr,
 904                                       u_int16_t                     recSize,
 905                                       u_int16_t                    *insertIndex,
 906                                       u_int32_t                    *insertNodeNum,
 907                                       Boolean                    *recordFit,
 908                                       u_int16_t                    *recsRotated )
 909 {
 910     OSStatus            err;
 911     int32_t                insertSize;
 912     int32_t                nodeSize;
 913     int32_t                leftSize, rightSize;
 914     int32_t                moveSize = 0;
 915     u_int16_t            keyLength;
 916     u_int16_t            lengthFieldSize;
 917     u_int16_t            index, moveIndex;
 918     Boolean                didItFit;
 919
 920     ///////////////////// Determine If Record Will Fit //////////////////////////
 921
 922     keyLength = GetKeyLength(btreePtr, keyPtr, (rightNode->kind == kBTLeafNode));
 923
 924     // the key's length field is 8-bits in HFS and 16-bits in HFS+
 925     if ( btreePtr->attributes & kBTBigKeysMask )
 926         lengthFieldSize = sizeof(u_int16_t);
 927     else
 928         lengthFieldSize = sizeof(u_int8_t);
 929
 930     insertSize = keyLength + lengthFieldSize + recSize + sizeof(u_int16_t);
 931
 932     if ( M_IsOdd (insertSize) )
 933         ++insertSize;    // add pad byte;
 934
 935     nodeSize        = btreePtr->nodeSize;
 936
 937     // add size of insert record to right node
 938     rightSize        = nodeSize - GetNodeFreeSize (btreePtr, rightNode) + insertSize;
 939     leftSize        = nodeSize - GetNodeFreeSize (btreePtr, leftNode);
 940
 941     moveIndex    = 0;
 942
 943     while ( leftSize < rightSize )
 944     {
 945         if ( moveIndex < rightInsertIndex )
 946         {
 947             moveSize = GetRecordSize (btreePtr, rightNode, moveIndex) + 2;
 948         }
 949         else if ( moveIndex == rightInsertIndex )
 950         {
 951             moveSize = insertSize;
 952         }
 953         else // ( moveIndex > rightInsertIndex )
 954         {
 955             moveSize = GetRecordSize (btreePtr, rightNode, moveIndex - 1) + 2;
 956         }
 957
 958         leftSize    += moveSize;
 959         rightSize    -= moveSize;
 960         ++moveIndex;
 961     }
 962
 963     if ( leftSize > nodeSize )    // undo last move
 964     {
 965         rightSize    += moveSize;
 966         --moveIndex;
 967     }
 968
 969     if ( rightSize > nodeSize )    // record won't fit - failure, but not error
 970     {
 971         *insertIndex    = 0;
 972         *insertNodeNum    = 0;
 973         *recordFit        = false;
 974         *recsRotated    = 0;
 975
 976         return    noErr;
 977     }
 978
 979     // we've found balance point, moveIndex == number of records moved into leftNode
 980
 981
 982     //////////////////////////// Rotate Records /////////////////////////////////
 983
 984     *recsRotated    = moveIndex;
 985     *recordFit        = true;
 986     index            = 0;
 987
 988     while ( index < moveIndex )
 989     {
 990         if ( index == rightInsertIndex )    // insert new record in left node
 991         {
 992             u_int16_t    leftInsertIndex;
 993
 994             leftInsertIndex = leftNode->numRecords;
 995
 996             didItFit = InsertKeyRecord (btreePtr, leftNode, leftInsertIndex,
 997                                         keyPtr, keyLength, recPtr, recSize);
 998             if ( !didItFit )
 999             {
1000                 LFHFS_LOG(LEVEL_ERROR, "RotateLeft: InsertKeyRecord (left) returned false!");
1001                 err = fsBTBadRotateErr;
1002                 goto ErrorExit;
1003             }
1004
1005             *insertIndex = leftInsertIndex;
1006             *insertNodeNum = rightNode->bLink;
1007         }
1008         else
1009         {
1010             didItFit = RotateRecordLeft (btreePtr, leftNode, rightNode);
1011             if ( !didItFit )
1012             {
1013                 LFHFS_LOG(LEVEL_ERROR, "RotateLeft: RotateRecordLeft returned false!");
1014                 err = fsBTBadRotateErr;
1015                 goto ErrorExit;
1016             }
1017         }
1018
1019         ++index;
1020     }
1021
1022     if ( moveIndex <= rightInsertIndex )    // then insert new record in right node
1023     {
1024         rightInsertIndex -= index;            // adjust for records already rotated
1025
1026         didItFit = InsertKeyRecord (btreePtr, rightNode, rightInsertIndex,
1027                                     keyPtr, keyLength, recPtr, recSize);
1028         if ( !didItFit )
1029         {
1030             LFHFS_LOG(LEVEL_ERROR, "RotateLeft: InsertKeyRecord (right) returned false!");
1031             err = fsBTBadRotateErr;
1032             goto ErrorExit;
1033         }
1034
1035         *insertIndex = rightInsertIndex;
1036         *insertNodeNum = leftNode->fLink;
1037     }
1038
1039
1040     return noErr;
1041
1042
1043     ////////////////////////////// Error Exit ///////////////////////////////////
1044
1045 ErrorExit:
1046
1047     *insertIndex    = 0;
1048     *insertNodeNum    = 0;
1049     *recordFit        = false;
1050     *recsRotated    = 0;
1051
1052     return    err;
1053 }
1054
1055
1056
1057 /////////////////////////////////// SplitLeft ///////////////////////////////////
1058
1059 static OSStatus    SplitLeft        (BTreeControlBlockPtr         btreePtr,
1060                                      BlockDescriptor            *leftNode,
1061                                      BlockDescriptor            *rightNode,
1062                                      u_int32_t                     rightNodeNum,
1063                                      u_int16_t                     index,
1064                                      KeyPtr                         keyPtr,
1065                                      u_int8_t *                     recPtr,
1066                                      u_int16_t                     recSize,
1067                                      u_int16_t                    *insertIndex,
1068                                      u_int32_t                    *insertNodeNum,
1069                                      u_int16_t                    *recsRotated )
1070 {
1071     OSStatus            err;
1072     NodeDescPtr            left, right;
1073     u_int32_t            newNodeNum;
1074     Boolean                recordFit;
1075
1076
1077     ///////////////////////////// Compare Nodes /////////////////////////////////
1078
1079     right = rightNode->buffer;
1080     left  = leftNode->buffer;
1081
1082     if (right->bLink != 0 && left == 0)
1083     {
1084         LFHFS_LOG(LEVEL_ERROR, " SplitLeft: left sibling missing!?" );
1085         hfs_assert(0);
1086     }
1087     /* type should be kBTLeafNode or kBTIndexNode */
1088
1089     if ( (right->height == 1) && (right->kind != kBTLeafNode) )
1090         return    fsBTInvalidNodeErr;
1091
1092     if ( left != nil )
1093     {
1094         if ( left->fLink != rightNodeNum )
1095             return fsBTInvalidNodeErr;                                        //E_BadSibling ?
1096
1097         if ( left->height != right->height )
1098             return    fsBTInvalidNodeErr;                                        //E_BadNodeHeight ?
1099
1100         if ( left->kind != right->kind )
1101             return    fsBTInvalidNodeErr;                                        //E_BadNodeType ?
1102     }
1103
1104
1105     ///////////////////////////// Allocate Node /////////////////////////////////
1106
1107     err = AllocateNode (btreePtr, &newNodeNum);
1108     M_ExitOnError (err);
1109
1110
1111     /////////////// Update Forward Link In Original Left Node ///////////////////
1112
1113     if ( left != nil )
1114     {
1115         // XXXdbg
1116         ModifyBlockStart(btreePtr->fileRefNum, leftNode);
1117
1118         left->fLink    = newNodeNum;
1119         err = UpdateNode (btreePtr, leftNode, 0, kLockTransaction);
1120         M_ExitOnError (err);
1121     }
1122
1123
1124     /////////////////////// Initialize New Left Node ////////////////////////////
1125
1126     err = GetNewNode (btreePtr, newNodeNum, leftNode);
1127     M_ExitOnError (err);
1128
1129     // XXXdbg
1130     ModifyBlockStart(btreePtr->fileRefNum, leftNode);
1131
1132     left        = leftNode->buffer;
1133     left->fLink    = rightNodeNum;
1134
1135
1136     // Steal Info From Right Node
1137
1138     left->bLink  = right->bLink;
1139     left->kind   = right->kind;
1140     left->height = right->height;
1141
1142     right->bLink        = newNodeNum;            // update Right bLink
1143
1144     if ( (left->kind == kBTLeafNode) && (left->bLink == 0) )
1145     {
1146         // if we're adding a new first leaf node - update BTreeInfoRec
1147
1148         btreePtr->firstLeafNode = newNodeNum;
1149         M_BTreeHeaderDirty (btreePtr);        //AllocateNode should have set the bit already...
1150     }
1151
1152     ////////////////////////////// Rotate Left //////////////////////////////////
1153
1154     err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize,
1155                       insertIndex, insertNodeNum, &recordFit, recsRotated);
1156
1157     M_ExitOnError (err);
1158
1159     return noErr;
1160
1161 ErrorExit:
1162
1163     (void) ReleaseNode (btreePtr, leftNode);
1164     (void) ReleaseNode (btreePtr, rightNode);
1165
1166     //Free new node if allocated?
1167
1168     *insertIndex    = 0;
1169     *insertNodeNum    = 0;
1170     *recsRotated    = 0;
1171
1172     return    err;
1173 }
1174
1175
1176
1177 /////////////////////////////// RotateRecordLeft ////////////////////////////////
1178
1179 static Boolean RotateRecordLeft (BTreeControlBlockPtr        btreePtr,
1180                                  NodeDescPtr                leftNode,
1181                                  NodeDescPtr                rightNode )
1182 {
1183     u_int16_t    size;
1184     u_int8_t *    recPtr;
1185     Boolean        recordFit;
1186
1187     size    = GetRecordSize (btreePtr, rightNode, 0);
1188     recPtr    = GetRecordAddress (btreePtr, rightNode, 0);
1189
1190     recordFit = InsertRecord (btreePtr, leftNode, leftNode->numRecords, recPtr, size);
1191
1192     if ( !recordFit )
1193         return false;
1194
1195     DeleteRecord (btreePtr, rightNode, 0);
1196
1197     return true;
1198 }
1199
1200
1201 //////////////////////////////// AddNewRootNode /////////////////////////////////
1202
1203 static OSStatus    AddNewRootNode    (BTreeControlBlockPtr     btreePtr,
1204                                       NodeDescPtr             leftNode,
1205                                       NodeDescPtr             rightNode )
1206 {
1207     OSStatus            err;
1208     BlockDescriptor        rootNode;
1209     u_int32_t            rootNum;
1210     KeyPtr                keyPtr;
1211     Boolean                didItFit;
1212     u_int16_t            keyLength;
1213
1214     rootNode.buffer = nil;
1215     rootNode.blockHeader = nil;
1216
1217     if (leftNode == nil || rightNode == nil)
1218     {
1219         LFHFS_LOG(LEVEL_ERROR, "AddNewRootNode: %s nil", (leftNode == nil && rightNode == nil)? "left and right node are" : ((leftNode == nil) ? "left node is" : "right node is"));
1220         hfs_assert(0);
1221     }
1222
1223     /////////////////////// Initialize New Root Node ////////////////////////////
1224
1225     err = AllocateNode (btreePtr, &rootNum);
1226     M_ExitOnError (err);
1227
1228     err = GetNewNode (btreePtr, rootNum, &rootNode);
1229     M_ExitOnError (err);
1230
1231     // XXXdbg
1232     ModifyBlockStart(btreePtr->fileRefNum, &rootNode);
1233
1234     ((NodeDescPtr)rootNode.buffer)->kind   = kBTIndexNode;
1235     ((NodeDescPtr)rootNode.buffer)->height = ++btreePtr->treeDepth;
1236
1237
1238     ///////////////////// Insert Left Node Index Record /////////////////////////
1239
1240     keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode, 0);
1241     keyLength = GetKeyLength(btreePtr, keyPtr, false);
1242
1243     didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 0, keyPtr, keyLength,
1244                                 (u_int8_t *) &rightNode->bLink, 4 );
1245     if (!didItFit)
1246     {
1247         LFHFS_LOG(LEVEL_ERROR, "AddNewRootNode:InsertKeyRecord failed for left index record\n");
1248         hfs_assert(0);
1249     }
1250
1251     //////////////////// Insert Right Node Index Record /////////////////////////
1252
1253     keyPtr = (KeyPtr) GetRecordAddress (btreePtr, rightNode, 0);
1254     keyLength = GetKeyLength(btreePtr, keyPtr, false);
1255
1256     didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 1, keyPtr, keyLength,
1257                                 (u_int8_t *) &leftNode->fLink, 4 );
1258
1259     if (!didItFit)
1260     {
1261         LFHFS_LOG(LEVEL_ERROR, "AddNewRootNode:InsertKeyRecord failed for right index record\n");
1262         hfs_assert(0);
1263     }
1264
1265     /////////////////////////// Release Root Node ///////////////////////////////
1266
1267     err = UpdateNode (btreePtr, &rootNode, 0, kLockTransaction);
1268     M_ExitOnError (err);
1269
1270     // update BTreeInfoRec
1271
1272     btreePtr->rootNode     = rootNum;
1273     M_BTreeHeaderDirty(btreePtr);
1274
1275     return noErr;
1276
1277
1278     ////////////////////////////// Error Exit ///////////////////////////////////
1279
1280 ErrorExit:
1281
1282     return    err;
1283 }
1284
1285
1286 static u_int16_t    GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode )
1287 {
1288     u_int16_t length;
1289
1290     if ( forLeafNode || btreePtr->attributes & kBTVariableIndexKeysMask )
1291         length = KeyLength (btreePtr, key);        // just use actual key length
1292     else
1293         length = btreePtr->maxKeyLength;        // fixed sized index key (i.e. HFS)        //shouldn't we clear the pad bytes?
1294
1295     return length;
1296 }
1297
1298