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