1/* 2 * Copyright (c) 1999-2000, 2002, 2007-2008 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23/* 24 File: BTreeTreeOps.c 25 26 Contains: Multi-node tree operations for the BTree Module. 27 28 Version: xxx put the technology version here xxx 29 30 Written by: Gordon Sheridan and Bill Bruffey 31 32 Copyright: � 1992-1997, 1999 by Apple Computer, Inc., all rights reserved. 33*/ 34 35#include "BTreePrivate.h" 36#include "../fsck_debug.h" 37extern char debug; 38extern void plog(const char *fmt, ...); 39 40#define DEBUG_TREEOPS 0 41 42/////////////////////// Routines Internal To BTree Module /////////////////////// 43// 44// SearchTree 45// InsertTree 46// 47////////////////////// Routines Internal To BTreeTreeOps.c ////////////////////// 48 49static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr, 50 NodeDescPtr leftNode, 51 NodeDescPtr rightNode ); 52 53static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr, 54 BlockDescriptor *blockPtr ); 55 56static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr, 57 NodeDescPtr leftNode, 58 NodeDescPtr rightNode, 59 UInt16 rightInsertIndex, 60 KeyPtr keyPtr, 61 UInt8 * recPtr, 62 UInt16 recSize, 63 UInt16 *insertIndex, 64 UInt32 *insertNodeNum, 65 Boolean *recordFit, 66 UInt16 *recsRotated ); 67 68static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr, 69 NodeDescPtr leftNode, 70 NodeDescPtr rightNode ); 71 72#if 0 73static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr, 74 BlockDescriptor *leftNode, 75 BlockDescriptor *rightNode, 76 UInt32 rightNodeNum, 77 UInt16 index, 78 KeyPtr keyPtr, 79 UInt8 * recPtr, 80 UInt16 recSize, 81 UInt16 *insertIndex, 82 UInt32 *insertNodeNum, 83 UInt16 *recsRotated ); 84#endif 85 86 87static OSStatus InsertLevel (BTreeControlBlockPtr btreePtr, 88 TreePathTable treePathTable, 89 InsertKey *primaryKey, 90 InsertKey *secondaryKey, 91 BlockDescriptor *targetNode, 92 UInt16 index, 93 UInt16 level, 94 UInt32 *insertNode ); 95 96static OSErr InsertNode (BTreeControlBlockPtr btreePtr, 97 InsertKey *key, 98 BlockDescriptor *targetNode, 99 UInt32 node, 100 UInt16 index, 101 UInt32 *newNode, 102 UInt16 *newIndex, 103 BlockDescriptor *leftNode, 104 Boolean *updateParent, 105 Boolean *insertParent, 106 Boolean *rootSplit ); 107 108static UInt16 GetKeyLength (const BTreeControlBlock *btreePtr, 109 const BTreeKey *key, 110 Boolean forLeafNode ); 111 112static Boolean RotateRecordRight( BTreeControlBlockPtr btreePtr, 113 NodeDescPtr leftNode, 114 NodeDescPtr rightNode ); 115 116static OSStatus RotateRight( BTreeControlBlockPtr btreePtr, 117 NodeDescPtr leftNode, 118 NodeDescPtr rightNode, 119 UInt16 leftInsertIndex, 120 KeyPtr keyPtr, 121 UInt8 * recPtr, 122 UInt16 recSize, 123 UInt16 *insertIndex, 124 UInt32 *insertNodeNum, 125 Boolean *recordFit, 126 UInt16 *recsRotated ); 127 128static OSStatus SplitRight( BTreeControlBlockPtr btreePtr, 129 BlockDescriptor *nodePtr, 130 BlockDescriptor *rightNodePtr, 131 UInt32 nodeNum, 132 UInt16 index, 133 KeyPtr keyPtr, 134 UInt8 *recPtr, 135 UInt16 recSize, 136 UInt16 *insertIndexPtr, 137 UInt32 *newNodeNumPtr, 138 UInt16 *recsRotatedPtr ); 139 140#if DEBUG_TREEOPS 141static int DoKeyCheck( NodeDescPtr nodeP, BTreeControlBlock *btcb ); 142static int DoKeyCheckAcrossNodes( NodeDescPtr theLeftNodePtr, 143 NodeDescPtr theRightNodePtr, 144 BTreeControlBlock *theTreePtr, 145 Boolean printKeys ); 146static void PrintNodeDescriptor( NodeDescPtr thePtr ); 147static void PrintKey( UInt8 * myPtr, int mySize ); 148#endif // DEBUG_TREEOPS 149 150 151/* used by InsertLevel (and called routines) to communicate the state of an insert operation */ 152enum 153{ 154 kInsertParent = 0x0001, 155 kUpdateParent = 0x0002, 156 kNewRoot = 0x0004, 157 kInsertedInRight = 0x0008, 158 kRecordFits = 0x0010 159}; 160 161 162//////////////////////// BTree Multi-node Tree Operations /////////////////////// 163 164 165/*------------------------------------------------------------------------------- 166 167Routine: SearchTree - Search BTree for key and set up Tree Path Table. 168 169Function: Searches BTree for specified key, setting up the Tree Path Table to 170 reflect the search path. 171 172 173Input: btreePtr - pointer to control block of BTree to search 174 keyPtr - pointer to the key to search for 175 treePathTable - pointer to the tree path table to construct 176 177Output: nodeNum - number of the node containing the key position 178 iterator - BTreeIterator specifying record or insert position 179 180Result: noErr - key found, index is record index 181 fsBTRecordNotFoundErr - key not found, index is insert index 182 fsBTEmptyErr - key not found, return params are nil 183 otherwise - catastrophic failure (GetNode/ReleaseNode failed) 184-------------------------------------------------------------------------------*/ 185 186OSStatus SearchTree (BTreeControlBlockPtr btreePtr, 187 BTreeKeyPtr searchKey, 188 TreePathTable treePathTable, 189 UInt32 *nodeNum, 190 BlockDescriptor *nodePtr, 191 UInt16 *returnIndex ) 192{ 193 OSStatus err; 194 SInt16 level; 195 UInt32 curNodeNum; 196 NodeRec nodeRec; 197 UInt16 index; 198 Boolean keyFound; 199 SInt8 nodeKind; // Kind of current node (index/leaf) 200 KeyPtr keyPtr; 201 UInt8 * dataPtr; 202 UInt16 dataSize; 203 204 205 curNodeNum = btreePtr->rootNode; 206 level = btreePtr->treeDepth; 207 208 if (level == 0) // is the tree empty? 209 { 210 err = fsBTEmptyErr; 211 goto ErrorExit; 212 } 213 214 //�� for debugging... 215 treePathTable [0].node = 0; 216 treePathTable [0].index = 0; 217 218 while (true) 219 { 220 // 221 // [2550929] Node number 0 is the header node. It is never a valid 222 // index or leaf node. If we're ever asked to search through node 0, 223 // something has gone wrong (typically a bad child node number, or 224 // we found a node full of zeroes that we thought was an index node). 225 // 226 if (curNodeNum == 0) 227 { 228// Panic("\pSearchTree: curNodeNum is zero!"); 229 if (debug) fprintf(stderr, "%s(%d): curNodeNum is 0\n", __FUNCTION__, __LINE__); 230 err = fsBTInvalidNodeErr; 231 goto ErrorExit; 232 } 233 234 err = GetNode (btreePtr, curNodeNum, &nodeRec); 235 if (err != noErr) 236 { 237 goto ErrorExit; 238 } 239 240 // 241 // [2550929] Sanity check the node height and node type. We expect 242 // particular values at each iteration in the search. This checking 243 // quickly finds bad pointers, loops, and other damage to the 244 // hierarchy of the B-tree. 245 // 246 if (((BTNodeDescriptor*)nodeRec.buffer)->height != level) 247 { 248 if (debug) 249 { 250 fprintf(stderr, "%s(line %d): height %d != level %d\n", __FUNCTION__, __LINE__, ((BTNodeDescriptor*)nodeRec.buffer)->height, level); 251 fprintf(stderr, " curNodeNum = %u\n", curNodeNum); 252 if (cur_debug_level & d_dump_node) 253 { 254 HexDump(nodeRec.buffer, nodeRec.blockSize, true); 255 } 256 } 257 err = fsBTInvalidNodeErr; 258 goto ReleaseAndExit; 259 } 260 nodeKind = ((BTNodeDescriptor*)nodeRec.buffer)->kind; 261 if (level == 1) 262 { 263 // Nodes at level 1 must be leaves, by definition 264 if (nodeKind != kBTLeafNode) 265 { 266 if (debug) fprintf(stderr, "%s(%d): wrong kind of node\n", __FUNCTION__, __LINE__); 267 err = fsBTInvalidNodeErr; 268 goto ReleaseAndExit; 269 } 270 } 271 else 272 { 273 // A node at any other depth must be an index node 274 if (nodeKind != kBTIndexNode) 275 { 276 if (debug) fprintf(stderr, "%s(%d): other wrong kind of node\n", __FUNCTION__, __LINE__); 277 err = fsBTInvalidNodeErr; 278 goto ReleaseAndExit; 279 } 280 } 281 282 keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index); 283 284 treePathTable [level].node = curNodeNum; 285 286 if (nodeKind == kBTLeafNode) 287 { 288 treePathTable [level].index = index; 289 break; // were done... 290 } 291 292 if ( (keyFound != true) && (index != 0)) 293 --index; 294 295 treePathTable [level].index = index; 296 297 err = GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize); 298 if (err != noErr) 299 { 300 // [2550929] If we got an error, it is probably because the index was bad 301 // (typically a corrupt node that confused SearchNode). Invalidate the node 302 // so we won't accidentally use the corrupted contents. NOTE: the Mac OS 9 303 // sources call this InvalidateNode. 304 305 (void) TrashNode(btreePtr, &nodeRec); 306 goto ErrorExit; 307 } 308 309 // Get the child pointer out of this index node. We're now done with the current 310 // node and can continue the search with the child node. 311 curNodeNum = *(UInt32 *)dataPtr; 312 err = ReleaseNode (btreePtr, &nodeRec); 313 if (err != noErr) 314 { 315 goto ErrorExit; 316 } 317 318 // The child node should be at a level one less than the parent. 319 --level; 320 } 321 322 *nodeNum = curNodeNum; 323 *nodePtr = nodeRec; 324 *returnIndex = index; 325 326 if (keyFound) 327 return noErr; // searchKey found, index identifies record in node 328 else 329 return fsBTRecordNotFoundErr; // searchKey not found, index identifies insert point 330 331ReleaseAndExit: 332 (void) ReleaseNode(btreePtr, &nodeRec); 333 // fall into ErrorExit 334 335ErrorExit: 336 337 *nodeNum = 0; 338 nodePtr->buffer = nil; 339 nodePtr->blockHeader = nil; 340 *returnIndex = 0; 341 342 return err; 343} 344 345 346 347 348////////////////////////////////// InsertTree /////////////////////////////////// 349 350OSStatus InsertTree ( BTreeControlBlockPtr btreePtr, 351 TreePathTable treePathTable, 352 KeyPtr keyPtr, 353 UInt8 * recPtr, 354 UInt16 recSize, 355 BlockDescriptor *targetNode, 356 UInt16 index, 357 UInt16 level, 358 Boolean replacingKey, 359 UInt32 *insertNode ) 360{ 361 InsertKey primaryKey; 362 OSStatus err; 363 364 primaryKey.keyPtr = keyPtr; 365 primaryKey.keyLength = GetKeyLength(btreePtr, primaryKey.keyPtr, (level == 1)); 366 primaryKey.recPtr = recPtr; 367 primaryKey.recSize = recSize; 368 primaryKey.replacingKey = replacingKey; 369 primaryKey.skipRotate = false; 370 371 err = InsertLevel (btreePtr, treePathTable, &primaryKey, nil, 372 targetNode, index, level, insertNode ); 373 374 return err; 375 376} // End of InsertTree 377 378 379////////////////////////////////// InsertLevel ////////////////////////////////// 380 381OSStatus InsertLevel (BTreeControlBlockPtr btreePtr, 382 TreePathTable treePathTable, 383 InsertKey *primaryKey, 384 InsertKey *secondaryKey, 385 BlockDescriptor *targetNode, 386 UInt16 index, 387 UInt16 level, 388 UInt32 *insertNode ) 389{ 390 OSStatus err; 391 BlockDescriptor siblingNode; 392 UInt32 targetNodeNum; 393 UInt32 newNodeNum; 394 UInt16 newIndex; 395 Boolean insertParent; 396 Boolean updateParent; 397 Boolean newRoot; 398 399#if defined(applec) && !defined(__SC__) 400 PanicIf ((level == 1) && (((NodeDescPtr)targetNode->buffer)->kind != kBTLeafNode), "\P InsertLevel: non-leaf at level 1! "); 401#endif 402 siblingNode.buffer = nil; 403 targetNodeNum = treePathTable [level].node; 404 405 insertParent = false; 406 updateParent = false; 407 408 ////// process first insert ////// 409 410 err = InsertNode (btreePtr, primaryKey, targetNode, targetNodeNum, index, 411 &newNodeNum, &newIndex, &siblingNode, &updateParent, &insertParent, &newRoot ); 412 M_ExitOnError (err); 413 414 if ( newRoot ) 415 { 416 // Extend the treePathTable by adding an entry for the new 417 // root node that references the current targetNode. 418 // 419 // When we split right the index in the new root is 0 if the new 420 // node is the same as the target node or 1 otherwise. When the 421 // new node number and the target node number are the same then 422 // we inserted the new record into the left node (the orignial target) 423 // after the split. 424 425 treePathTable [level + 1].node = btreePtr->rootNode; 426 if ( targetNodeNum == newNodeNum ) 427 treePathTable [level + 1].index = 0; // 428 else 429 treePathTable [level + 1].index = 1; 430 } 431 432 if ( level == 1 ) 433 *insertNode = newNodeNum; 434 435 ////// process second insert (if any) ////// 436 437 if ( secondaryKey != nil ) 438 { 439 Boolean temp; 440 441 // NOTE - we only get here if we have split a child node to the right and 442 // we are currently updating the child's parent. newIndex + 1 refers to 443 // the location in the parent node where we insert the new index record that 444 // represents the new child node (the new right node). 445 err = InsertNode (btreePtr, secondaryKey, targetNode, newNodeNum, newIndex + 1, 446 &newNodeNum, &newIndex, &siblingNode, &updateParent, &insertParent, &temp); 447 M_ExitOnError (err); 448 449 if ( DEBUG_BUILD && updateParent && newRoot ) 450 DebugStr("\p InsertLevel: New root from primary key, update from secondary key..."); 451 } 452 453 //////////////////////// Update Parent(s) /////////////////////////////// 454 455 if ( insertParent || updateParent ) 456 { 457 BlockDescriptor parentNode; 458 UInt32 parentNodeNum; 459 KeyPtr keyPtr; 460 UInt8 * recPtr; 461 UInt16 recSize; 462 463 secondaryKey = nil; 464 465 PanicIf ( (level == btreePtr->treeDepth), "\p InsertLevel: unfinished insert!?"); 466 467 ++level; 468 469 // Get Parent Node data... 470 index = treePathTable [level].index; 471 parentNodeNum = treePathTable [level].node; 472 473 PanicIf ( parentNodeNum == 0, "\p InsertLevel: parent node is zero!?"); 474 475 err = GetNode (btreePtr, parentNodeNum, &parentNode); // released as target node in next level up 476 M_ExitOnError (err); 477#if defined(applec) && !defined(__SC__) 478 if (DEBUG_BUILD && level > 1) 479 PanicIf ( ((NodeDescPtr)parentNode.buffer)->kind != kBTIndexNode, "\P InsertLevel: parent node not an index node! "); 480#endif 481 ////////////////////////// Update Parent Index ////////////////////////////// 482 483 if ( updateParent ) 484 { 485 //���debug: check if ptr == targetNodeNum 486 GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize); 487 PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p InsertLevel: parent ptr doesn't match target node!"); 488 489 // need to delete and re-insert this parent key/ptr 490 // we delete it here and it gets re-inserted in the 491 // InsertLevel call below. 492 DeleteRecord (btreePtr, parentNode.buffer, index); 493 494 primaryKey->keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 ); 495 primaryKey->keyLength = GetKeyLength(btreePtr, primaryKey->keyPtr, false); 496 primaryKey->recPtr = (UInt8 *) &targetNodeNum; 497 primaryKey->recSize = sizeof(targetNodeNum); 498 primaryKey->replacingKey = kReplaceRecord; 499 primaryKey->skipRotate = insertParent; // don't rotate left if we have two inserts occuring 500 } 501 502 ////////////////////////// Add New Parent Index ///////////////////////////// 503 504 if ( insertParent ) 505 { 506 InsertKey *insertKeyPtr; 507 InsertKey insertKey; 508 509 if ( updateParent ) 510 { 511 insertKeyPtr = &insertKey; 512 secondaryKey = &insertKey; 513 } 514 else 515 { 516 insertKeyPtr = primaryKey; 517 // split right but not updating parent for our left node then 518 // we want to insert the key for the new right node just after 519 // the key for our left node. 520 index++; 521 } 522 523 insertKeyPtr->keyPtr = (KeyPtr) GetRecordAddress (btreePtr, siblingNode.buffer, 0); 524 insertKeyPtr->keyLength = GetKeyLength(btreePtr, insertKeyPtr->keyPtr, false); 525 insertKeyPtr->recPtr = (UInt8 *) &((NodeDescPtr)targetNode->buffer)->fLink; 526 insertKeyPtr->recSize = sizeof(UInt32); 527 insertKeyPtr->replacingKey = kInsertRecord; 528 insertKeyPtr->skipRotate = false; // a rotate is OK during second insert 529 } 530 531 err = InsertLevel (btreePtr, treePathTable, primaryKey, secondaryKey, 532 &parentNode, index, level, insertNode ); 533 M_ExitOnError (err); 534 } 535 536 err = UpdateNode (btreePtr, targetNode); // all done with target 537 M_ExitOnError (err); 538 539 err = UpdateNode (btreePtr, &siblingNode); // all done with left sibling 540 M_ExitOnError (err); 541 542 return noErr; 543 544ErrorExit: 545 546 (void) ReleaseNode (btreePtr, targetNode); 547 (void) ReleaseNode (btreePtr, &siblingNode); 548 549 Panic ("\p InsertLevel: an error occured!"); 550 551 return err; 552 553} // End of InsertLevel 554 555 556 557////////////////////////////////// InsertNode /////////////////////////////////// 558 559static OSErr InsertNode (BTreeControlBlockPtr btreePtr, 560 InsertKey *key, 561 562 BlockDescriptor *targetNode, 563 UInt32 nodeNum, 564 UInt16 index, 565 566 UInt32 *newNodeNumPtr, 567 UInt16 *newIndex, 568 569 BlockDescriptor *siblingNode, 570 Boolean *updateParent, 571 Boolean *insertParent, 572 Boolean *rootSplit ) 573{ 574 BlockDescriptor *tempNode; 575 UInt32 leftNodeNum; 576 UInt32 rightNodeNum; 577 UInt16 recsRotated; 578 OSErr err; 579 Boolean recordFit; 580 581 *rootSplit = false; 582 583 PanicIf ( targetNode->buffer == siblingNode->buffer, "\p InsertNode: targetNode == siblingNode, huh?"); 584 585 leftNodeNum = ((NodeDescPtr) targetNode->buffer)->bLink; 586 rightNodeNum = ((NodeDescPtr) targetNode->buffer)->fLink; 587 588 589 /////////////////////// Try Simple Insert /////////////////////////////// 590 591 if ( nodeNum == leftNodeNum ) 592 tempNode = siblingNode; 593 else 594 tempNode = targetNode; 595 596 recordFit = InsertKeyRecord (btreePtr, tempNode->buffer, index, key->keyPtr, key->keyLength, key->recPtr, key->recSize); 597 598 if ( recordFit ) 599 { 600 *newNodeNumPtr = nodeNum; 601 *newIndex = index; 602 603#if DEBUG_TREEOPS 604 if ( DoKeyCheck( tempNode->buffer, btreePtr ) != noErr ) 605 { 606 plog( "\n%s - bad key order in node num %d: \n", __FUNCTION__ , nodeNum ); 607 PrintNodeDescriptor( tempNode->buffer ); 608 err = fsBTBadRotateErr; 609 goto ErrorExit; 610 } 611#endif // DEBUG_TREEOPS 612 613 if ( (index == 0) && (((NodeDescPtr) tempNode->buffer)->height != btreePtr->treeDepth) ) 614 *updateParent = true; // the first record changed so we need to update the parent 615 goto ExitThisRoutine; 616 } 617 618 619 //////////////////////// Try Rotate Left //////////////////////////////// 620 621 if ( leftNodeNum > 0 ) 622 { 623 PanicIf ( siblingNode->buffer != nil, "\p InsertNode: siblingNode already aquired!"); 624 625 if ( siblingNode->buffer == nil ) 626 { 627 err = GetNode (btreePtr, leftNodeNum, siblingNode); // will be released by caller or a split below 628 M_ExitOnError (err); 629 } 630 631 PanicIf ( ((NodeDescPtr) siblingNode->buffer)->fLink != nodeNum, "\p InsertNode, RotateLeft: invalid sibling link!" ); 632 633 if ( !key->skipRotate ) // are rotates allowed? 634 { 635 err = RotateLeft (btreePtr, siblingNode->buffer, targetNode->buffer, index, key->keyPtr, key->recPtr, 636 key->recSize, newIndex, newNodeNumPtr, &recordFit, &recsRotated ); 637 M_ExitOnError (err); 638 639 if ( recordFit ) 640 { 641 if ( key->replacingKey || (recsRotated > 1) || (index > 0) ) 642 *updateParent = true; 643 goto ExitThisRoutine; 644 } 645 } 646 } 647 648 649 //////////////////////// Try Split Right ///////////////////////////////// 650 651 (void) ReleaseNode( btreePtr, siblingNode ); 652 err = SplitRight( btreePtr, targetNode, siblingNode, nodeNum, index, key->keyPtr, 653 key->recPtr, key->recSize, newIndex, newNodeNumPtr, &recsRotated ); 654 M_ExitOnError (err); 655 656 // if we split root node - add new root 657 if ( ((NodeDescPtr) targetNode->buffer)->height == btreePtr->treeDepth ) 658 { 659 err = AddNewRootNode( btreePtr, targetNode->buffer, siblingNode->buffer ); // Note: does not update TPT 660 M_ExitOnError (err); 661 *rootSplit = true; 662 } 663 else 664 { 665 *insertParent = true; 666 667 // update parent index node when replacingKey is true or when 668 // we inserted a new record at the beginning of our target node. 669 if ( key->replacingKey || ( index == 0 && *newIndex == 0 ) ) 670 *updateParent = true; 671 } 672 673ExitThisRoutine: 674 675 return noErr; 676 677ErrorExit: 678 679 (void) ReleaseNode (btreePtr, siblingNode); 680 return err; 681 682} // End of InsertNode 683 684 685/*------------------------------------------------------------------------------- 686Routine: DeleteTree - One_line_description. 687 688Function: Brief_description_of_the_function_and_any_side_effects 689 690ToDo: 691 692Input: btreePtr - description 693 treePathTable - description 694 targetNode - description 695 index - description 696 697Result: noErr - success 698 != noErr - failure 699-------------------------------------------------------------------------------*/ 700 701OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, 702 TreePathTable treePathTable, 703 BlockDescriptor *targetNode, 704 UInt16 index, 705 UInt16 level ) 706{ 707 OSStatus err; 708 BlockDescriptor parentNode; 709 BTNodeDescriptor *targetNodePtr; 710 UInt32 targetNodeNum; 711 Boolean deleteRequired; 712 Boolean updateRequired; 713 714 715 deleteRequired = false; 716 updateRequired = false; 717 718 targetNodeNum = treePathTable[level].node; 719 targetNodePtr = targetNode->buffer; 720 PanicIf (targetNodePtr == nil, "\pDeleteTree: targetNode has nil buffer!"); 721 722 DeleteRecord (btreePtr, targetNodePtr, index); 723 724 //�� coalesce remaining records? 725 726 if ( targetNodePtr->numRecords == 0 ) // did we delete the last record? 727 { 728 BlockDescriptor siblingNode; 729 UInt32 siblingNodeNum; 730 731 deleteRequired = true; 732 733 ////////////////// Get Siblings & Update Links ////////////////////////// 734 735 siblingNodeNum = targetNodePtr->bLink; // Left Sibling Node 736 if ( siblingNodeNum != 0 ) 737 { 738 err = GetNode (btreePtr, siblingNodeNum, &siblingNode); 739 M_ExitOnError (err); 740 ((NodeDescPtr)siblingNode.buffer)->fLink = targetNodePtr->fLink; 741 err = UpdateNode (btreePtr, &siblingNode); 742 M_ExitOnError (err); 743 } 744 else if ( targetNodePtr->kind == kBTLeafNode ) // update firstLeafNode 745 { 746 btreePtr->firstLeafNode = targetNodePtr->fLink; 747 } 748 749 siblingNodeNum = targetNodePtr->fLink; // Right Sibling Node 750 if ( siblingNodeNum != 0 ) 751 { 752 err = GetNode (btreePtr, siblingNodeNum, &siblingNode); 753 M_ExitOnError (err); 754 ((NodeDescPtr)siblingNode.buffer)->bLink = targetNodePtr->bLink; 755 err = UpdateNode (btreePtr, &siblingNode); 756 M_ExitOnError (err); 757 } 758 else if ( targetNodePtr->kind == kBTLeafNode ) // update lastLeafNode 759 { 760 btreePtr->lastLeafNode = targetNodePtr->bLink; 761 } 762 763 //////////////////////// Free Empty Node //////////////////////////////// 764 765 ClearNode (btreePtr, targetNodePtr); 766 767 err = UpdateNode (btreePtr, targetNode); 768 M_ExitOnError (err); 769 err = FreeNode (btreePtr, targetNodeNum); 770 M_ExitOnError (err); 771 } 772 else if ( index == 0 ) // did we delete the first record? 773 { 774 updateRequired = true; // yes, so we need to update parent 775 } 776 777 778 if ( level == btreePtr->treeDepth ) // then targetNode->buffer is the root node 779 { 780 deleteRequired = false; 781 updateRequired = false; 782 783 if ( targetNode->buffer == nil ) // then root was freed and the btree is empty 784 { 785 btreePtr->rootNode = 0; 786 btreePtr->treeDepth = 0; 787 } 788 else if ( ((NodeDescPtr)targetNode->buffer)->numRecords == 1 ) 789 { 790 err = CollapseTree (btreePtr, targetNode); 791 M_ExitOnError (err); 792 } 793 } 794 795 796 if ( updateRequired || deleteRequired ) 797 { 798 ++level; // next level 799 800 //// Get Parent Node and index 801 index = treePathTable [level].index; 802 err = GetNode (btreePtr, treePathTable[level].node, &parentNode); 803 M_ExitOnError (err); 804 805 if ( updateRequired ) 806 { 807 KeyPtr keyPtr; 808 UInt8 * recPtr; 809 UInt16 recSize; 810 UInt32 insertNode; 811 812 //���debug: check if ptr == targetNodeNum 813 GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize); 814 PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p DeleteTree: parent ptr doesn't match targetNodeNum!!"); 815 816 // need to delete and re-insert this parent key/ptr 817 DeleteRecord (btreePtr, parentNode.buffer, index); 818 819 keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 ); 820 recPtr = (UInt8 *) &targetNodeNum; 821 recSize = sizeof(targetNodeNum); 822 823 err = InsertTree (btreePtr, treePathTable, keyPtr, recPtr, recSize, 824 &parentNode, index, level, kReplaceRecord, &insertNode); 825 M_ExitOnError (err); 826 } 827 else // deleteRequired 828 { 829 err = DeleteTree (btreePtr, treePathTable, &parentNode, index, level); 830 M_ExitOnError (err); 831 } 832 } 833 834 835 err = UpdateNode (btreePtr, targetNode); 836 M_ExitOnError (err); 837 838 return noErr; 839 840ErrorExit: 841 842 (void) ReleaseNode (btreePtr, targetNode); 843 (void) ReleaseNode (btreePtr, &parentNode); 844 845 return err; 846 847} // end DeleteTree 848 849 850 851///////////////////////////////// CollapseTree ////////////////////////////////// 852 853static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr, 854 BlockDescriptor *blockPtr ) 855{ 856 OSStatus err; 857 UInt32 originalRoot; 858 UInt32 nodeNum; 859 860 originalRoot = btreePtr->rootNode; 861 862 while (true) 863 { 864 if ( ((NodeDescPtr)blockPtr->buffer)->numRecords > 1) 865 break; // this will make a fine root node 866 867 if ( ((NodeDescPtr)blockPtr->buffer)->kind == kBTLeafNode) 868 break; // we've hit bottom 869 870 nodeNum = btreePtr->rootNode; 871 btreePtr->rootNode = GetChildNodeNum (btreePtr, blockPtr->buffer, 0); 872 --btreePtr->treeDepth; 873 874 //// Clear and Free Current Old Root Node //// 875 ClearNode (btreePtr, blockPtr->buffer); 876 err = UpdateNode (btreePtr, blockPtr); 877 M_ExitOnError (err); 878 err = FreeNode (btreePtr, nodeNum); 879 M_ExitOnError (err); 880 881 //// Get New Root Node 882 err = GetNode (btreePtr, btreePtr->rootNode, blockPtr); 883 M_ExitOnError (err); 884 } 885 886 if (btreePtr->rootNode != originalRoot) 887 M_BTreeHeaderDirty (btreePtr); 888 889 err = UpdateNode (btreePtr, blockPtr); // always update! 890 M_ExitOnError (err); 891 892 return noErr; 893 894 895/////////////////////////////////// ErrorExit /////////////////////////////////// 896 897ErrorExit: 898 (void) ReleaseNode (btreePtr, blockPtr); 899 return err; 900} 901 902 903 904////////////////////////////////// RotateLeft /////////////////////////////////// 905 906/*------------------------------------------------------------------------------- 907 908Routine: RotateLeft - One_line_description. 909 910Function: Brief_description_of_the_function_and_any_side_effects 911 912Algorithm: if rightIndex > insertIndex, subtract 1 for actual rightIndex 913 914Input: btreePtr - description 915 leftNode - description 916 rightNode - description 917 rightInsertIndex - description 918 keyPtr - description 919 recPtr - description 920 recSize - description 921 922Output: insertIndex 923 insertNodeNum - description 924 recordFit - description 925 recsRotated 926 927Result: noErr - success 928 != noErr - failure 929-------------------------------------------------------------------------------*/ 930 931static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr, 932 NodeDescPtr leftNode, 933 NodeDescPtr rightNode, 934 UInt16 rightInsertIndex, 935 KeyPtr keyPtr, 936 UInt8 * recPtr, 937 UInt16 recSize, 938 UInt16 *insertIndex, 939 UInt32 *insertNodeNum, 940 Boolean *recordFit, 941 UInt16 *recsRotated ) 942{ 943 OSStatus err; 944 SInt32 insertSize; 945 SInt32 nodeSize; 946 SInt32 leftSize, rightSize; 947 SInt32 moveSize; 948 UInt16 keyLength; 949 UInt16 lengthFieldSize; 950 UInt16 index, moveIndex; 951 Boolean didItFit; 952 953 ///////////////////// Determine If Record Will Fit ////////////////////////// 954 955 keyLength = GetKeyLength(btreePtr, keyPtr, (rightNode->kind == kBTLeafNode)); 956 957 // the key's length field is 8-bits in HFS and 16-bits in HFS+ 958 if ( btreePtr->attributes & kBTBigKeysMask ) 959 lengthFieldSize = sizeof(UInt16); 960 else 961 lengthFieldSize = sizeof(UInt8); 962 963 insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16); 964 965 if ( M_IsOdd (insertSize) ) 966 ++insertSize; // add pad byte; 967 968 nodeSize = btreePtr->nodeSize; 969 970 // add size of insert record to right node 971 rightSize = nodeSize - GetNodeFreeSize (btreePtr, rightNode) + insertSize; 972 leftSize = nodeSize - GetNodeFreeSize (btreePtr, leftNode); 973 974 moveIndex = 0; 975 moveSize = 0; 976 977 while ( leftSize < rightSize ) 978 { 979 if ( moveIndex < rightInsertIndex ) 980 { 981 moveSize = GetRecordSize (btreePtr, rightNode, moveIndex) + 2; 982 } 983 else if ( moveIndex == rightInsertIndex ) 984 { 985 moveSize = insertSize; 986 } 987 else // ( moveIndex > rightInsertIndex ) 988 { 989 moveSize = GetRecordSize (btreePtr, rightNode, moveIndex - 1) + 2; 990 } 991 992 leftSize += moveSize; 993 rightSize -= moveSize; 994 ++moveIndex; 995 } 996 997 if ( leftSize > nodeSize ) // undo last move 998 { 999 leftSize -= moveSize; 1000 rightSize += moveSize; 1001 --moveIndex; 1002 } 1003 1004 if ( rightSize > nodeSize ) // record won't fit - failure, but not error 1005 { 1006 *insertIndex = 0; 1007 *insertNodeNum = 0; 1008 *recordFit = false; 1009 *recsRotated = 0; 1010 1011 return noErr; 1012 } 1013 1014 // we've found balance point, moveIndex == number of records moved into leftNode 1015 1016 1017 //////////////////////////// Rotate Records ///////////////////////////////// 1018 1019 *recsRotated = moveIndex; 1020 *recordFit = true; 1021 index = 0; 1022 1023 while ( index < moveIndex ) 1024 { 1025 if ( index == rightInsertIndex ) // insert new record in left node 1026 { 1027 UInt16 leftInsertIndex; 1028 1029 leftInsertIndex = leftNode->numRecords; 1030 1031 didItFit = InsertKeyRecord (btreePtr, leftNode, leftInsertIndex, 1032 keyPtr, keyLength, recPtr, recSize); 1033 if ( !didItFit ) 1034 { 1035 Panic ("\pRotateLeft: InsertKeyRecord (left) returned false!"); 1036 err = fsBTBadRotateErr; 1037 goto ErrorExit; 1038 } 1039 1040 *insertIndex = leftInsertIndex; 1041 *insertNodeNum = rightNode->bLink; 1042 } 1043 else 1044 { 1045 didItFit = RotateRecordLeft (btreePtr, leftNode, rightNode); 1046 if ( !didItFit ) 1047 { 1048 Panic ("\pRotateLeft: RotateRecordLeft returned false!"); 1049 err = fsBTBadRotateErr; 1050 goto ErrorExit; 1051 } 1052 } 1053 1054 ++index; 1055 } 1056 1057 if ( moveIndex <= rightInsertIndex ) // then insert new record in right node 1058 { 1059 rightInsertIndex -= index; // adjust for records already rotated 1060 1061 didItFit = InsertKeyRecord (btreePtr, rightNode, rightInsertIndex, 1062 keyPtr, keyLength, recPtr, recSize); 1063 if ( !didItFit ) 1064 { 1065 Panic ("\pRotateLeft: InsertKeyRecord (right) returned false!"); 1066 err = fsBTBadRotateErr; 1067 goto ErrorExit; 1068 } 1069 1070 *insertIndex = rightInsertIndex; 1071 *insertNodeNum = leftNode->fLink; 1072 } 1073 1074#if DEBUG_TREEOPS 1075 if ( DoKeyCheck( leftNode, btreePtr ) != noErr ) 1076 { 1077 plog( "\n%s - bad key order in left node num %d: \n", __FUNCTION__ , rightNode->bLink ); 1078 PrintNodeDescriptor( leftNode ); 1079 err = fsBTBadRotateErr; 1080 goto ErrorExit; 1081 } 1082 if ( DoKeyCheck( rightNode, btreePtr ) != noErr ) 1083 { 1084 plog( "\n%s - bad key order in left node num %d: \n", __FUNCTION__ , leftNode->fLink ); 1085 PrintNodeDescriptor( rightNode ); 1086 err = fsBTBadRotateErr; 1087 goto ErrorExit; 1088 } 1089#endif // DEBUG_TREEOPS 1090 1091 1092 return noErr; 1093 1094 1095 ////////////////////////////// Error Exit /////////////////////////////////// 1096 1097ErrorExit: 1098 1099 *insertIndex = 0; 1100 *insertNodeNum = 0; 1101 *recordFit = false; 1102 *recsRotated = 0; 1103 1104 return err; 1105} 1106 1107 1108#if 0 1109/////////////////////////////////// SplitLeft /////////////////////////////////// 1110 1111static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr, 1112 BlockDescriptor *leftNode, 1113 BlockDescriptor *rightNode, 1114 UInt32 rightNodeNum, 1115 UInt16 index, 1116 KeyPtr keyPtr, 1117 UInt8 * recPtr, 1118 UInt16 recSize, 1119 UInt16 *insertIndex, 1120 UInt32 *insertNodeNum, 1121 UInt16 *recsRotated ) 1122{ 1123 OSStatus err; 1124 NodeDescPtr left, right; 1125 UInt32 newNodeNum; 1126 Boolean recordFit; 1127 1128 1129 ///////////////////////////// Compare Nodes ///////////////////////////////// 1130 1131 right = rightNode->buffer; 1132 left = leftNode->buffer; 1133 1134 PanicIf ( right->bLink != 0 && left == 0, "\p SplitLeft: left sibling missing!?" ); 1135 1136 //�� type should be kLeafNode or kIndexNode 1137 1138 if ( (right->height == 1) && (right->kind != kBTLeafNode) ) 1139 return fsBTInvalidNodeErr; 1140 1141 if ( left != nil ) 1142 { 1143 if ( left->fLink != rightNodeNum ) 1144 return fsBTInvalidNodeErr; //�� E_BadSibling ? 1145 1146 if ( left->height != right->height ) 1147 return fsBTInvalidNodeErr; //�� E_BadNodeHeight ? 1148 1149 if ( left->kind != right->kind ) 1150 return fsBTInvalidNodeErr; //�� E_BadNodeType ? 1151 } 1152 1153 1154 ///////////////////////////// Allocate Node ///////////////////////////////// 1155 1156 err = AllocateNode (btreePtr, &newNodeNum); 1157 M_ExitOnError (err); 1158 1159 1160 /////////////// Update Forward Link In Original Left Node /////////////////// 1161 1162 if ( left != nil ) 1163 { 1164 left->fLink = newNodeNum; 1165 err = UpdateNode (btreePtr, leftNode); 1166 M_ExitOnError (err); 1167 } 1168 1169 1170 /////////////////////// Initialize New Left Node //////////////////////////// 1171 1172 err = GetNewNode (btreePtr, newNodeNum, leftNode); 1173 M_ExitOnError (err); 1174 1175 left = leftNode->buffer; 1176 left->fLink = rightNodeNum; 1177 1178 1179 // Steal Info From Right Node 1180 1181 left->bLink = right->bLink; 1182 left->kind = right->kind; 1183 left->height = right->height; 1184 1185 right->bLink = newNodeNum; // update Right bLink 1186 1187 if ( (left->kind == kBTLeafNode) && (left->bLink == 0) ) 1188 { 1189 // if we're adding a new first leaf node - update BTreeInfoRec 1190 1191 btreePtr->firstLeafNode = newNodeNum; 1192 M_BTreeHeaderDirty (btreePtr); //�� AllocateNode should have set the bit already... 1193 } 1194 1195 ////////////////////////////// Rotate Left ////////////////////////////////// 1196 1197 err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize, 1198 insertIndex, insertNodeNum, &recordFit, recsRotated); 1199 M_ExitOnError (err); 1200 1201 return noErr; 1202 1203ErrorExit: 1204 1205 (void) ReleaseNode (btreePtr, leftNode); 1206 (void) ReleaseNode (btreePtr, rightNode); 1207 1208 //�� Free new node if allocated? 1209 1210 *insertIndex = 0; 1211 *insertNodeNum = 0; 1212 *recsRotated = 0; 1213 1214 return err; 1215} 1216#endif 1217 1218 1219 1220/////////////////////////////// RotateRecordLeft //////////////////////////////// 1221 1222static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr, 1223 NodeDescPtr leftNode, 1224 NodeDescPtr rightNode ) 1225{ 1226 UInt16 size; 1227 UInt8 * recPtr; 1228 Boolean recordFit; 1229 1230 size = GetRecordSize (btreePtr, rightNode, 0); 1231 recPtr = GetRecordAddress (btreePtr, rightNode, 0); 1232 1233 recordFit = InsertRecord (btreePtr, leftNode, leftNode->numRecords, recPtr, size); 1234 1235 if ( !recordFit ) 1236 return false; 1237 1238 DeleteRecord (btreePtr, rightNode, 0); 1239 1240 return true; 1241} 1242 1243 1244//////////////////////////////// AddNewRootNode ///////////////////////////////// 1245 1246static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr, 1247 NodeDescPtr leftNode, 1248 NodeDescPtr rightNode ) 1249{ 1250 OSStatus err; 1251 BlockDescriptor rootNode; 1252 UInt32 rootNum; 1253 KeyPtr keyPtr; 1254 Boolean didItFit; 1255 UInt16 keyLength; 1256 1257 PanicIf (leftNode == nil, "\pAddNewRootNode: leftNode == nil"); 1258 PanicIf (rightNode == nil, "\pAddNewRootNode: rightNode == nil"); 1259 1260 1261 /////////////////////// Initialize New Root Node //////////////////////////// 1262 1263 err = AllocateNode (btreePtr, &rootNum); 1264 M_ExitOnError (err); 1265 1266 err = GetNewNode (btreePtr, rootNum, &rootNode); 1267 M_ExitOnError (err); 1268 1269 ((NodeDescPtr)rootNode.buffer)->kind = kBTIndexNode; 1270 ((NodeDescPtr)rootNode.buffer)->height = ++btreePtr->treeDepth; 1271 1272 1273 ///////////////////// Insert Left Node Index Record ///////////////////////// 1274 1275 keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode, 0); 1276 keyLength = GetKeyLength(btreePtr, keyPtr, false); 1277 1278 didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 0, keyPtr, keyLength, 1279 (UInt8 *) &rightNode->bLink, 4 ); 1280 1281 PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for left index record"); 1282 1283 1284 //////////////////// Insert Right Node Index Record ///////////////////////// 1285 1286 keyPtr = (KeyPtr) GetRecordAddress (btreePtr, rightNode, 0); 1287 keyLength = GetKeyLength(btreePtr, keyPtr, false); 1288 1289 didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 1, keyPtr, keyLength, 1290 (UInt8 *) &leftNode->fLink, 4 ); 1291 1292 PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for right index record"); 1293 1294 1295#if DEBUG_TREEOPS 1296 if ( DoKeyCheck( rootNode.buffer, btreePtr ) != noErr ) 1297 { 1298 plog( "\n%s - bad key order in root node num %d: \n", __FUNCTION__ , rootNum ); 1299 PrintNodeDescriptor( rootNode.buffer ); 1300 err = fsBTBadRotateErr; 1301 goto ErrorExit; 1302 } 1303#endif // DEBUG_TREEOPS 1304 1305 1306 /////////////////////////// Release Root Node /////////////////////////////// 1307 1308 err = UpdateNode (btreePtr, &rootNode); 1309 M_ExitOnError (err); 1310 1311 // update BTreeInfoRec 1312 1313 btreePtr->rootNode = rootNum; 1314 btreePtr->flags |= kBTHeaderDirty; 1315 1316 return noErr; 1317 1318 1319 ////////////////////////////// Error Exit /////////////////////////////////// 1320 1321ErrorExit: 1322 1323 return err; 1324} 1325 1326 1327static UInt16 GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode ) 1328{ 1329 UInt16 length; 1330 1331 if ( forLeafNode || btreePtr->attributes & kBTVariableIndexKeysMask ) 1332 length = KeyLength (btreePtr, key); // just use actual key length 1333 else 1334 length = btreePtr->maxKeyLength; // fixed sized index key (i.e. HFS) //�� shouldn't we clear the pad bytes? 1335 1336 return length; 1337} 1338 1339 1340 1341/////////////////////////////////// SplitRight /////////////////////////////////// 1342 1343static OSStatus SplitRight (BTreeControlBlockPtr btreePtr, 1344 BlockDescriptor *nodePtr, 1345 BlockDescriptor *rightNodePtr, 1346 UInt32 nodeNum, 1347 UInt16 index, 1348 KeyPtr keyPtr, 1349 UInt8 *recPtr, 1350 UInt16 recSize, 1351 UInt16 *insertIndexPtr, 1352 UInt32 *newNodeNumPtr, 1353 UInt16 *recsRotatedPtr ) 1354{ 1355 OSStatus err; 1356 NodeDescPtr leftPtr, rightPtr; 1357 UInt32 newNodeNum; 1358 Boolean recordFit; 1359 1360 1361 ///////////////////////////// Compare Nodes ///////////////////////////////// 1362 1363 leftPtr = nodePtr->buffer; 1364 1365 if ( leftPtr->fLink != 0 ) 1366 { 1367 err = GetNode( btreePtr, leftPtr->fLink, rightNodePtr ); 1368 M_ExitOnError( err ); 1369 } 1370 rightPtr = rightNodePtr->buffer; 1371 1372 PanicIf ( leftPtr->fLink != 0 && rightPtr == 0, "\p SplitRight: right sibling missing!?" ); 1373 1374 //�� type should be kLeafNode or kIndexNode 1375 1376 if ( (leftPtr->height == 1) && (leftPtr->kind != kBTLeafNode) ) 1377 return fsBTInvalidNodeErr; 1378 1379 if ( rightPtr != nil ) 1380 { 1381 if ( rightPtr->bLink != nodeNum ) 1382 return fsBTInvalidNodeErr; //�� E_BadSibling ? 1383 1384 if ( rightPtr->height != leftPtr->height ) 1385 return fsBTInvalidNodeErr; //�� E_BadNodeHeight ? 1386 1387 if ( rightPtr->kind != leftPtr->kind ) 1388 return fsBTInvalidNodeErr; //�� E_BadNodeType ? 1389 } 1390 1391 1392 ///////////////////////////// Allocate Node ///////////////////////////////// 1393 1394 err = AllocateNode (btreePtr, &newNodeNum); 1395 M_ExitOnError (err); 1396 1397 /////////////// Update backward Link In Original Right Node /////////////////// 1398 1399 if ( rightPtr != nil ) 1400 { 1401 rightPtr->bLink = newNodeNum; 1402 err = UpdateNode (btreePtr, rightNodePtr); 1403 M_ExitOnError (err); 1404 } 1405 1406 /////////////////////// Initialize New Right Node //////////////////////////// 1407 1408 err = GetNewNode (btreePtr, newNodeNum, rightNodePtr ); 1409 M_ExitOnError (err); 1410 1411 rightPtr = rightNodePtr->buffer; 1412 rightPtr->bLink = nodeNum; 1413 1414 1415 // Steal Info From Left Node 1416 1417 rightPtr->fLink = leftPtr->fLink; 1418 rightPtr->kind = leftPtr->kind; 1419 rightPtr->height = leftPtr->height; 1420 1421 leftPtr->fLink = newNodeNum; // update Left fLink 1422 1423 if ( (rightPtr->kind == kBTLeafNode) && (rightPtr->fLink == 0) ) 1424 { 1425 // if we're adding a new last leaf node - update BTreeInfoRec 1426 1427 btreePtr->lastLeafNode = newNodeNum; 1428 M_BTreeHeaderDirty (btreePtr); //�� AllocateNode should have set the bit already... 1429 } 1430 1431 ////////////////////////////// Rotate Right ////////////////////////////////// 1432 1433 err = RotateRight (btreePtr, leftPtr, rightPtr, index, keyPtr, recPtr, recSize, 1434 insertIndexPtr, newNodeNumPtr, &recordFit, recsRotatedPtr); 1435 M_ExitOnError (err); 1436 1437 return noErr; 1438 1439ErrorExit: 1440 1441 (void) ReleaseNode (btreePtr, nodePtr); 1442 (void) ReleaseNode (btreePtr, rightNodePtr); 1443 1444 //�� Free new node if allocated? 1445 1446 *insertIndexPtr = 0; 1447 *newNodeNumPtr = 0; 1448 *recsRotatedPtr = 0; 1449 1450 return err; 1451 1452} /* SplitRight */ 1453 1454 1455 1456////////////////////////////////// RotateRight /////////////////////////////////// 1457 1458/*------------------------------------------------------------------------------- 1459 1460Routine: RotateRight - rotate half of . 1461 1462Function: Brief_description_of_the_function_and_any_side_effects 1463 1464Algorithm: if rightIndex > insertIndex, subtract 1 for actual rightIndex 1465 1466Input: btreePtr - description 1467 leftNode - description 1468 rightNode - description 1469 leftInsertIndex - description 1470 keyPtr - description 1471 recPtr - description 1472 recSize - description 1473 1474Output: insertIndex 1475 insertNodeNum - description 1476 recordFit - description 1477 recsRotated 1478 1479Result: noErr - success 1480 != noErr - failure 1481-------------------------------------------------------------------------------*/ 1482 1483static OSStatus RotateRight (BTreeControlBlockPtr btreePtr, 1484 NodeDescPtr leftNodePtr, 1485 NodeDescPtr rightNodePtr, 1486 UInt16 leftInsertIndex, 1487 KeyPtr keyPtr, 1488 UInt8 *recPtr, 1489 UInt16 recSize, 1490 UInt16 *insertIndexPtr, 1491 UInt32 *newNodeNumPtr, 1492 Boolean *didRecordFitPtr, 1493 UInt16 *recsRotatedPtr ) 1494{ 1495 OSStatus err; 1496 SInt32 insertSize; 1497 SInt32 nodeSize; 1498 SInt32 leftSize, rightSize; 1499 SInt32 moveSize; 1500 UInt16 keyLength; 1501 UInt16 lengthFieldSize; 1502 SInt16 index, moveIndex, myInsertIndex; 1503 Boolean didItFit; 1504 Boolean doIncrement = false; 1505 1506 ///////////////////// Determine If Record Will Fit ////////////////////////// 1507 1508 keyLength = GetKeyLength( btreePtr, keyPtr, (leftNodePtr->kind == kBTLeafNode) ); 1509 1510 // the key's length field is 8-bits in HFS and 16-bits in HFS+ 1511 if ( btreePtr->attributes & kBTBigKeysMask ) 1512 lengthFieldSize = sizeof(UInt16); 1513 else 1514 lengthFieldSize = sizeof(UInt8); 1515 1516 /* 1517 * A record size in a node is the size of the key, the size of the key length field, 1518 * the size of the record, and the size of the record offset index. 1519 */ 1520 insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16); 1521 if ( M_IsOdd (insertSize) ) 1522 ++insertSize; // add pad byte; 1523 nodeSize = btreePtr->nodeSize; 1524 1525 // add size of insert record to left node 1526 rightSize = nodeSize - GetNodeFreeSize( btreePtr, rightNodePtr ); 1527 leftSize = nodeSize - GetNodeFreeSize( btreePtr, leftNodePtr ) + insertSize; 1528 1529 moveIndex = leftNodePtr->numRecords; // start at last record in the node 1530 moveSize = 0; 1531 1532 /* 1533 * The goal here is to attempt to make the nodes as balanced as 1534 * possible. We do this by "moving" records from the left node to 1535 * the right node, until the right node is larger than the left 1536 * node. 1537 * 1538 * We also need to factor in the new record for this; what we are 1539 * trying to do, as a result, is consider a virtual node that has 1540 * all of the old records in it, plus the new record inserted at 1541 * the proper place. (This is the reason for the if cases in the 1542 * loop.) 1543 */ 1544 while ( rightSize < leftSize ) 1545 { 1546 /* 1547 * We set moveSize to the size of the record being moved in this 1548 * pass. We need to add sizeof(UInt16) because we need to account 1549 * for the record offset index, which is two bytes. This was already 1550 * added to insertSize above. 1551 */ 1552 if (moveIndex > leftInsertIndex) 1553 moveSize = GetRecordSize( btreePtr, leftNodePtr, moveIndex - 1) + sizeof(UInt16); 1554 else if (moveIndex == leftInsertIndex) 1555 moveSize = insertSize; 1556 else // (moveIndex < leftInsertIndex) 1557 moveSize = GetRecordSize( btreePtr, leftNodePtr, moveIndex) + sizeof(UInt16); 1558 1559 leftSize -= moveSize; 1560 rightSize += moveSize; 1561 --moveIndex; 1562 } 1563 1564 if ( rightSize > nodeSize ) // undo last move 1565 { 1566 leftSize += moveSize; 1567 rightSize -= moveSize; 1568 ++moveIndex; 1569 } 1570 1571 if ( leftSize > nodeSize ) // record won't fit - failure, but not error 1572 { 1573 *insertIndexPtr = 0; 1574 *newNodeNumPtr = 0; 1575 *didRecordFitPtr = false; 1576 *recsRotatedPtr = 0; 1577 1578 return noErr; 1579 } 1580 1581 // we've found balance point, we rotate up to moveIndex into right node 1582 1583 //////////////////////////// Rotate Records ///////////////////////////////// 1584 1585 *didRecordFitPtr = true; 1586 index = leftNodePtr->numRecords; 1587 *recsRotatedPtr = index - moveIndex; 1588 myInsertIndex = 0; 1589 1590 // handle case where the new record is inserting after the last 1591 // record in our left node. 1592 if ( leftNodePtr->numRecords == leftInsertIndex ) 1593 { 1594 didItFit = InsertKeyRecord (btreePtr, rightNodePtr, 0, 1595 keyPtr, keyLength, recPtr, recSize); 1596 if ( !didItFit ) 1597 { 1598 if (debug) plog ("RotateRight: InsertKeyRecord (left) returned false!\n"); 1599 err = fsBTBadRotateErr; 1600 goto ErrorExit; 1601 } 1602 1603 // NOTE - our insert location will slide as we insert more records 1604 doIncrement = true; 1605 *newNodeNumPtr = leftNodePtr->fLink; 1606 index--; 1607 } 1608 1609 while ( index > moveIndex ) 1610 { 1611 if ( index == leftInsertIndex ) // insert new record in right node 1612 { 1613 didItFit = InsertKeyRecord (btreePtr, rightNodePtr, 0, 1614 keyPtr, keyLength, recPtr, recSize); 1615 if ( !didItFit ) 1616 { 1617 if (debug) plog ("RotateRight: InsertKeyRecord (right) returned false!\n"); 1618 err = fsBTBadRotateErr; 1619 goto ErrorExit; 1620 } 1621 1622 // NOTE - our insert index will slide as we insert more records 1623 doIncrement = true; 1624 myInsertIndex = -1; 1625 *newNodeNumPtr = leftNodePtr->fLink; 1626 } 1627 else 1628 { 1629 didItFit = RotateRecordRight( btreePtr, leftNodePtr, rightNodePtr ); 1630 if ( !didItFit ) 1631 { 1632 if (debug) plog ("RotateRight: RotateRecordRight returned false!\n"); 1633 err = fsBTBadRotateErr; 1634 goto ErrorExit; 1635 } 1636 } 1637 1638 if ( doIncrement ) 1639 myInsertIndex++; 1640 --index; 1641 } 1642 1643 *insertIndexPtr = myInsertIndex; 1644 1645 if ( moveIndex >= leftInsertIndex ) // then insert new record in left node 1646 { 1647 didItFit = InsertKeyRecord (btreePtr, leftNodePtr, leftInsertIndex, 1648 keyPtr, keyLength, recPtr, recSize); 1649 if ( !didItFit ) 1650 { 1651 if (debug) plog ("RotateRight: InsertKeyRecord (left) returned false!\n"); 1652 err = fsBTBadRotateErr; 1653 goto ErrorExit; 1654 } 1655 1656 *insertIndexPtr = leftInsertIndex; 1657 *newNodeNumPtr = rightNodePtr->bLink; 1658 } 1659 1660#if DEBUG_TREEOPS 1661 if ( DoKeyCheck( rightNodePtr, btreePtr ) != noErr ) 1662 { 1663 plog( "\n%s - bad key order in right node num %d: \n", __FUNCTION__ , leftNodePtr->fLink); 1664 PrintNodeDescriptor( rightNodePtr ); 1665 err = fsBTBadRotateErr; 1666 goto ErrorExit; 1667 } 1668 if ( DoKeyCheck( leftNodePtr, btreePtr ) != noErr ) 1669 { 1670 plog( "\n%s - bad key order in left node num %d: \n", __FUNCTION__ , rightNodePtr->bLink); 1671 PrintNodeDescriptor( leftNodePtr ); 1672 err = fsBTBadRotateErr; 1673 goto ErrorExit; 1674 } 1675 if ( DoKeyCheckAcrossNodes( leftNodePtr, rightNodePtr, btreePtr, false ) != noErr ) 1676 { 1677 plog( "\n%s - bad key order across nodes left %d right %d: \n", 1678 __FUNCTION__ , rightNodePtr->bLink, leftNodePtr->fLink ); 1679 PrintNodeDescriptor( leftNodePtr ); 1680 PrintNodeDescriptor( rightNodePtr ); 1681 err = fsBTBadRotateErr; 1682 goto ErrorExit; 1683 } 1684#endif // DEBUG_TREEOPS 1685 1686 return noErr; 1687 1688 1689 ////////////////////////////// Error Exit /////////////////////////////////// 1690 1691ErrorExit: 1692 1693 *insertIndexPtr = 0; 1694 *newNodeNumPtr = 0; 1695 *didRecordFitPtr = false; 1696 *recsRotatedPtr = 0; 1697 1698 return err; 1699 1700} /* RotateRight */ 1701 1702 1703 1704/////////////////////////////// RotateRecordRight //////////////////////////////// 1705 1706static Boolean RotateRecordRight (BTreeControlBlockPtr btreePtr, 1707 NodeDescPtr leftNodePtr, 1708 NodeDescPtr rightNodePtr ) 1709{ 1710 UInt16 size; 1711 UInt8 * recPtr; 1712 Boolean didRecordFit; 1713 1714 size = GetRecordSize( btreePtr, leftNodePtr, leftNodePtr->numRecords - 1 ) ; 1715 recPtr = GetRecordAddress( btreePtr, leftNodePtr, leftNodePtr->numRecords - 1 ) ; 1716 1717 didRecordFit = InsertRecord( btreePtr, rightNodePtr, 0, recPtr, size ); 1718 if ( !didRecordFit ) 1719 return false; 1720 1721 DeleteRecord( btreePtr, leftNodePtr, leftNodePtr->numRecords - 1 ); 1722 1723 return true; 1724 1725} /* RotateRecordRight */ 1726 1727 1728 1729#if DEBUG_TREEOPS 1730static int DoKeyCheckAcrossNodes( NodeDescPtr theLeftNodePtr, 1731 NodeDescPtr theRightNodePtr, 1732 BTreeControlBlock *theTreePtr, 1733 Boolean printKeys ) 1734{ 1735 UInt16 myLeftDataSize; 1736 UInt16 myRightDataSize; 1737 UInt16 myRightKeyLen; 1738 UInt16 myLeftKeyLen; 1739 KeyPtr myLeftKeyPtr; 1740 KeyPtr myRightKeyPtr; 1741 UInt8 * myLeftDataPtr; 1742 UInt8 * myRightDataPtr; 1743 1744 1745 GetRecordByIndex( theTreePtr, theLeftNodePtr, (theLeftNodePtr->numRecords - 1), 1746 &myLeftKeyPtr, &myLeftDataPtr, &myLeftDataSize ); 1747 GetRecordByIndex( theTreePtr, theRightNodePtr, 0, 1748 &myRightKeyPtr, &myRightDataPtr, &myRightDataSize ); 1749 1750 if ( theTreePtr->attributes & kBTBigKeysMask ) 1751 { 1752 myRightKeyLen = myRightKeyPtr->length16; 1753 myLeftKeyLen = myLeftKeyPtr->length16; 1754 } 1755 else 1756 { 1757 myRightKeyLen = myRightKeyPtr->length8; 1758 myLeftKeyLen = myLeftKeyPtr->length8; 1759 } 1760 1761 if ( printKeys ) 1762 { 1763 plog( "%s - left and right keys:\n", __FUNCTION__ ); 1764 PrintKey( (UInt8 *) myLeftKeyPtr, myLeftKeyLen ); 1765 PrintKey( (UInt8 *) myRightKeyPtr, myRightKeyLen ); 1766 } 1767 1768 if ( CompareKeys( theTreePtr, myLeftKeyPtr, myRightKeyPtr ) >= 0 ) 1769 return( -1 ); 1770 1771 return( noErr ); 1772 1773} /* DoKeyCheckAcrossNodes */ 1774 1775 1776static int DoKeyCheck( NodeDescPtr nodeP, BTreeControlBlock *btcb ) 1777{ 1778 SInt16 index; 1779 UInt16 dataSize; 1780 UInt16 keyLength; 1781 KeyPtr keyPtr; 1782 UInt8 *dataPtr; 1783 KeyPtr prevkeyP = nil; 1784 1785 1786 if ( nodeP->numRecords == 0 ) 1787 { 1788 if ( (nodeP->fLink == 0) && (nodeP->bLink == 0) ) 1789 return( -1 ); 1790 } 1791 else 1792 { 1793 /* 1794 * Loop on number of records in node 1795 */ 1796 for ( index = 0; index < nodeP->numRecords; index++) 1797 { 1798 GetRecordByIndex( (BTreeControlBlock *)btcb, nodeP, (UInt16) index, &keyPtr, &dataPtr, &dataSize ); 1799 1800 if (btcb->attributes & kBTBigKeysMask) 1801 keyLength = keyPtr->length16; 1802 else 1803 keyLength = keyPtr->length8; 1804 1805 if ( keyLength > btcb->maxKeyLength ) 1806 { 1807 return( -1 ); 1808 } 1809 1810 if ( prevkeyP != nil ) 1811 { 1812 if ( CompareKeys( (BTreeControlBlockPtr)btcb, prevkeyP, keyPtr ) >= 0 ) 1813 { 1814 return( -1 ); 1815 } 1816 } 1817 prevkeyP = keyPtr; 1818 } 1819 } 1820 1821 return( noErr ); 1822 1823} /* DoKeyCheck */ 1824 1825static void PrintNodeDescriptor( NodeDescPtr thePtr ) 1826{ 1827 plog( " fLink %d bLink %d kind %d height %d numRecords %d \n", 1828 thePtr->fLink, thePtr->bLink, thePtr->kind, thePtr->height, thePtr->numRecords ); 1829} 1830 1831 1832static void PrintKey( UInt8 * myPtr, int mySize ) 1833{ 1834 int i; 1835 1836 for ( i = 0; i < mySize+2; i++ ) 1837 { 1838 plog("%02X", *(myPtr + i) ); 1839 } 1840 plog("\n" ); 1841} /* PrintKey */ 1842 1843 1844#endif // DEBUG_TREEOPS 1845