1/* 2 * Copyright (c) 1999, 2005 Apple Computer, 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: BTree.c 25 26 Contains: Implementation of public interface routines for B-tree manager. 27 28 Version: HFS Plus 1.0 29 30 Written by: Gordon Sheridan and Bill Bruffey 31 32 Copyright: � 1992-1999 by Apple Computer, Inc., all rights reserved. 33*/ 34 35extern char debug; 36 37#include "BTree.h" 38#include "BTreePrivate.h" 39//#include "HFSInstrumentation.h" 40 41 42extern Boolean NodesAreContiguous(SFCB *fcb, UInt32 nodeSize); 43extern void fplog(FILE *stream, const char *fmt, ...); 44 45/*------------------------------------------------------------------------------- 46Routine: CopyKey 47 48Function: Copy a BTree key. Sanity check the key length; if it is too large, 49 then set the copy's length to the BTree's maximum key length. 50 51Inputs: btcb BTree whose key is being copied 52 srcKey Source key being copied 53 54Output: destKey Destination where copy will be stored 55 56Result: none (void) 57-------------------------------------------------------------------------------*/ 58static void CopyKey(BTreeControlBlockPtr btcb, const BTreeKey *srcKey, BTreeKey *destKey) 59{ 60 unsigned keySize = CalcKeySize(btcb, srcKey); 61 unsigned maxKeySize = MaxKeySize(btcb); 62 int fixLength = 0; 63 64 /* 65 * If the key length is too long (corrupted), then constrain the number 66 * of bytes to copy. Remember that we did this so we can also update 67 * the copy's length field later. 68 */ 69 if (keySize > maxKeySize) 70 { 71 keySize = maxKeySize; 72 fixLength = 1; 73 } 74 75 CopyMemory(srcKey, destKey, keySize); 76 77 /* 78 * If we had to constrain the key size above, then also update the 79 * key length in the copy. This will prevent the caller from dereferencing 80 * part of the key which we never actually copied. 81 */ 82 if (fixLength) 83 { 84 if (btcb->attributes & kBTBigKeysMask) 85 destKey->length16 = btcb->maxKeyLength; 86 else 87 destKey->length8 = btcb->maxKeyLength; 88 } 89} 90 91 92//////////////////////////////////// Globals //////////////////////////////////// 93 94 95/////////////////////////// BTree Module Entry Points /////////////////////////// 96 97 98/*------------------------------------------------------------------------------- 99Routine: InitBTreeModule - Initialize BTree Module Global(s). 100 101Function: Initialize BTree code, if necessary 102 103Input: none 104 105Output: none 106 107Result: noErr - success 108 != noErr - can't happen 109-------------------------------------------------------------------------------*/ 110 111OSStatus InitBTreeModule(void) 112{ 113 return noErr; 114} 115 116 117/*------------------------------------------------------------------------------- 118Routine: BTInitialize - Initialize a fork for access as a B*Tree. 119 120Function: Write Header node and create any map nodes necessary to map the fork 121 as a B*Tree. If the fork is not large enough for the header node, the 122 FS Agent is called to extend the LEOF. Additional map nodes will be 123 allocated if necessary to represent the size of the fork. This allows 124 the FS Agent to specify the initial size of B*Tree files. 125 126 127Input: pathPtr - pointer to path control block 128 maxKeyLength - maximum length that will be used for any key in this B*Tree 129 nodeSize - node size for B*Tree (must be 2^n, 9 >= n >= 15) 130 btreeType - type of B*Tree 131 keyDescPtr - pointer to key descriptor (optional if key compare proc is used) 132 133Output: none 134 135Result: noErr - success 136 paramErr - mandatory parameter was missing 137 E_NoGetBlockProc - FS Agent CB has no GetNodeProcPtr 138 E_NoReleaseBlockProc - FS Agent CB has no ReleaseNodeProcPtr 139 E_NoSetEndOfForkProc - FS Agent CB has no SetEndOfForkProcPtr 140 E_NoSetBlockSizeProc - FS Agent CB has no SetBlockSizeProcPtr 141 fsBTrFileAlreadyOpenErr - fork is already open as a B*Tree 142 fsBTInvalidKeyLengthErr - maximum key length is out of range 143 E_BadNodeType - node size is an illegal value 144 fsBTUnknownVersionErr - the B*Tree type is unknown by this module 145 memFullErr - not enough memory to initialize B*Tree 146 != noErr - failure 147-------------------------------------------------------------------------------*/ 148#if 0 149OSStatus BTInitialize (FCB *filePtr, 150 UInt16 maxKeyLength, 151 UInt16 nodeSize, 152 UInt8 btreeType, 153 KeyDescriptorPtr keyDescPtr ) 154{ 155 OSStatus err; 156 FSForkControlBlockPtr forkPtr; 157 BTreeControlBlockPtr btreePtr; 158 BlockDescriptor headerNode; 159 HeaderPtr header; 160 Ptr pos; 161 FSSize minEOF, maxEOF; 162 SetEndOfForkProcPtr setEndOfForkProc; 163 SetBlockSizeProcPtr setBlockSizeProc; 164 165 ////////////////////// Preliminary Error Checking /////////////////////////// 166 167 headerNode.buffer = nil; 168 169 if (pathPtr == nil) return paramErr; 170 171 setEndOfForkProc = pathPtr->agentPtr->agent.setEndOfForkProc; 172 setBlockSizeProc = pathPtr->agentPtr->agent.setBlockSizeProc; 173 174 if (pathPtr->agentPtr->agent.getBlockProc == nil) return E_NoGetBlockProc; 175 if (pathPtr->agentPtr->agent.releaseBlockProc == nil) return E_NoReleaseBlockProc; 176 if (setEndOfForkProc == nil) return E_NoSetEndOfForkProc; 177 if (setBlockSizeProc == nil) return E_NoSetBlockSizeProc; 178 179 forkPtr = pathPtr->path.forkPtr; 180 181 if (forkPtr->fork.btreePtr != nil) return fsBTrFileAlreadyOpenErr; 182 183 if ((maxKeyLength == 0) || 184 (maxKeyLength > kMaxKeyLength)) return fsBTInvalidKeyLengthErr; 185 186 if ( M_IsEven (maxKeyLength)) ++maxKeyLength; // len byte + even bytes + pad byte 187 188 switch (nodeSize) // node size == 512*2^n 189 { 190 case 512: 191 case 1024: 192 case 2048: 193 case 4096: 194 case 8192: 195 case 16384: 196 case 32768: break; 197 default: return E_BadNodeType; 198 } 199 200 switch (btreeType) 201 { 202 case kHFSBTreeType: 203 case kUserBTreeType: 204 case kReservedBTreeType: break; 205 206 default: return fsBTUnknownVersionErr; //�� right? 207 } 208 209 210 //////////////////////// Allocate Control Block ///////////////////////////// 211 212 M_RESIDENT_ALLOCATE_FIXED_CLEAR( &btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType ); 213 if (btreePtr == nil) 214 { 215 err = memFullErr; 216 goto ErrorExit; 217 } 218 219 btreePtr->version = kBTreeVersion; //�� what is the version? 220 btreePtr->reserved1 = 0; 221 btreePtr->flags = 0; 222 btreePtr->attributes = 0; 223 btreePtr->forkPtr = forkPtr; 224 btreePtr->keyCompareProc = nil; 225 btreePtr->keyDescPtr = keyDescPtr; 226 btreePtr->btreeType = btreeType; 227 btreePtr->treeDepth = 0; 228 btreePtr->rootNode = 0; 229 btreePtr->leafRecords = 0; 230 btreePtr->firstLeafNode = 0; 231 btreePtr->lastLeafNode = 0; 232 btreePtr->nodeSize = nodeSize; 233 btreePtr->maxKeyLength = maxKeyLength; 234 btreePtr->totalNodes = 1; // so ExtendBTree adds maps nodes properly 235 btreePtr->freeNodes = 0; 236 btreePtr->writeCount = 1; // <CS10>, for BTree scanner 237 238 // set block size = nodeSize 239 err = setBlockSizeProc (forkPtr, nodeSize); 240 M_ExitOnError (err); 241 242 ////////////////////////////// Check LEOF /////////////////////////////////// 243 244 minEOF = nodeSize; 245 if ( forkPtr->fork.logicalEOF < minEOF ) 246 { 247 // allocate more space if necessary 248 maxEOF 0xFFFFFFFFL; 249 250 err = setEndOfForkProc (forkPtr, minEOF, maxEOF); 251 M_ExitOnError (err); 252 }; 253 254 255 //////////////////////// Initialize Header Node ///////////////////////////// 256 257 err = GetNewNode (btreePtr, kHeaderNodeNum, &headerNode); 258 M_ExitOnError (err); 259 260 header = headerNode.buffer; 261 262 header->node.type = kHeaderNode; 263 header->node.numRecords = 3; // header rec, key desc, map rec 264 265 header->nodeSize = nodeSize; 266 header->maxKeyLength = maxKeyLength; 267 header->btreeType = btreeType; 268 header->totalNodes = btreePtr->totalNodes; 269 header->freeNodes = btreePtr->totalNodes - 1; 270 // ignore header->clumpSize; //�� rename this field? 271 272 // mark header node allocated in map record 273 pos = ((Ptr)headerNode.buffer) + kHeaderMapRecOffset; 274 *pos = 0x80; 275 276 // set node offsets ( nodeSize-8, F8, 78, 0E) 277 pos = ((Ptr)headerNode.buffer) + nodeSize; 278 pos -= 2; *((UInt16 *)pos) = kHeaderRecOffset; 279 pos -= 2; *((UInt16 *)pos) = kKeyDescRecOffset; 280 pos -= 2; *((UInt16 *)pos) = kHeaderMapRecOffset; 281 pos -= 2; *((UInt16 *)pos) = nodeSize - 8; 282 283 284 ///////////////////// Copy Key Descriptor To Header ///////////////////////// 285#if SupportsKeyDescriptors 286 if (keyDescPtr != nil) 287 { 288 err = CheckKeyDescriptor (keyDescPtr, maxKeyLength); 289 M_ExitOnError (err); 290 291 // copy to header node 292 pos = ((Ptr)headerNode.buffer) + kKeyDescRecOffset; 293 CopyMemory (keyDescPtr, pos, keyDescPtr->length + 1); 294 } 295#endif 296 297 // write header node 298 err = UpdateNode (btreePtr, &headerNode); 299 M_ExitOnError (err); 300 301 302 ////////////////////////// Allocate Map Nodes /////////////////////////////// 303 304 err = ExtendBTree (btreePtr, forkPtr->fork.logicalEOF.lo / nodeSize); // sets totalNodes 305 M_ExitOnError (err); 306 307 308 ////////////////////////////// Close BTree ////////////////////////////////// 309 310 err = UpdateHeader (btreePtr); 311 M_ExitOnError (err); 312 313 pathPtr->path.forkPtr->fork.btreePtr = nil; 314 M_RESIDENT_DEALLOCATE_FIXED( btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType ); 315 316 return noErr; 317 318 319 /////////////////////// Error - Clean up and Exit /////////////////////////// 320 321ErrorExit: 322 323 (void) ReleaseNode (btreePtr, &headerNode); 324 if (btreePtr != nil) 325 M_RESIDENT_DEALLOCATE_FIXED( btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType ); 326 327 return err; 328} 329#endif 330 331 332/*------------------------------------------------------------------------------- 333Routine: BTOpenPath - Open a file for access as a B*Tree. 334 335Function: Create BTree control block for a file, if necessary. Validates the 336 file to be sure it looks like a BTree file. 337 338 339Input: filePtr - pointer to file to open as a B-tree 340 keyCompareProc - pointer to client's KeyCompare function 341 getBlockProc - pointer to client's GetBlock function 342 releaseBlockProc - pointer to client's ReleaseBlock function 343 setEndOfForkProc - pointer to client's SetEOF function 344 345Result: noErr - success 346 paramErr - required ptr was nil 347 fsBTInvalidFileErr - 348 memFullErr - 349 != noErr - failure 350-------------------------------------------------------------------------------*/ 351 352OSStatus BTOpenPath (SFCB *filePtr, 353 KeyCompareProcPtr keyCompareProc, 354 GetBlockProcPtr getBlockProc, 355 ReleaseBlockProcPtr releaseBlockProc, 356 SetEndOfForkProcPtr setEndOfForkProc, 357 SetBlockSizeProcPtr setBlockSizeProc ) 358{ 359 OSStatus err; 360 BTreeControlBlockPtr btreePtr; 361 BTHeaderRec *header; 362 NodeRec nodeRec; 363 364// LogStartTime(kTraceOpenBTree); 365 366 ////////////////////// Preliminary Error Checking /////////////////////////// 367 368 if ( filePtr == nil || 369 getBlockProc == nil || 370 releaseBlockProc == nil || 371 setEndOfForkProc == nil || 372 setBlockSizeProc == nil ) 373 { 374 return paramErr; 375 } 376 377 if ( filePtr->fcbBtree != nil ) // already has a BTreeCB 378 return noErr; 379 380 // is file large enough to contain header node? 381 if ( filePtr->fcbLogicalSize < kMinNodeSize ) 382 return fsBTInvalidFileErr; //�� or E_BadHeader? 383 384 385 //////////////////////// Allocate Control Block ///////////////////////////// 386 387 btreePtr = (BTreeControlBlock*) AllocateClearMemory( sizeof( BTreeControlBlock ) ); 388 if (btreePtr == nil) 389 { 390 Panic ("\pBTOpen: no memory for btreePtr."); 391 return memFullErr; 392 } 393 394 btreePtr->getBlockProc = getBlockProc; 395 btreePtr->releaseBlockProc = releaseBlockProc; 396 btreePtr->setEndOfForkProc = setEndOfForkProc; 397 btreePtr->keyCompareProc = keyCompareProc; 398 399 /////////////////////////// Read Header Node //////////////////////////////// 400 401 nodeRec.buffer = nil; // so we can call ReleaseNode 402 403 btreePtr->fcbPtr = filePtr; 404 filePtr->fcbBtree = (void *) btreePtr; // attach btree cb to file 405 406 // it is now safe to call M_ExitOnError (err) 407 408 err = setBlockSizeProc (btreePtr->fcbPtr, kMinNodeSize); 409 M_ExitOnError (err); 410 411 412 err = getBlockProc (btreePtr->fcbPtr, 413 kHeaderNodeNum, 414 kGetBlock, 415 &nodeRec ); 416 417 PanicIf (err != noErr, "\pBTOpen: getNodeProc returned error getting header node."); 418 M_ExitOnError (err); 419 420 header = (BTHeaderRec*) (nodeRec.buffer + sizeof(BTNodeDescriptor)); 421 422 423 ///////////////////////////// verify header ///////////////////////////////// 424 425 err = VerifyHeader (filePtr, header); 426 M_ExitOnError (err); 427 428 429 ///////////////////// Initalize fields from header ////////////////////////// 430 431 PanicIf ( (filePtr->fcbVolume->vcbSignature != 0x4244) && (btreePtr->nodeSize == 512), "\p BTOpenPath: wrong node size for HFS+ volume!"); 432 433 btreePtr->treeDepth = header->treeDepth; 434 btreePtr->rootNode = header->rootNode; 435 btreePtr->leafRecords = header->leafRecords; 436 btreePtr->firstLeafNode = header->firstLeafNode; 437 btreePtr->lastLeafNode = header->lastLeafNode; 438 btreePtr->nodeSize = header->nodeSize; 439 btreePtr->maxKeyLength = header->maxKeyLength; 440 btreePtr->totalNodes = header->totalNodes; 441 btreePtr->freeNodes = header->freeNodes; 442 // ignore header->clumpSize; //�� rename this field? 443 btreePtr->btreeType = header->btreeType; 444 445 btreePtr->attributes = header->attributes; 446 447 if ( btreePtr->maxKeyLength > 40 ) 448 btreePtr->attributes |= (kBTBigKeysMask + kBTVariableIndexKeysMask); //�� we need a way to save these attributes 449 450 /////////////////////// Initialize dynamic fields /////////////////////////// 451 452 btreePtr->version = kBTreeVersion; 453 btreePtr->flags = 0; 454 btreePtr->writeCount = 1; // <CS10>, for BTree scanner 455 456 btreePtr->numGetNodes = 1; // for earlier call to getNodeProc 457 458 /////////////////////////// Check Header Node /////////////////////////////// 459 460 //�� set kBadClose attribute bit, and UpdateNode 461 462 /* 463 * If the actual node size is different than the amount we read, 464 * then release and trash this block, and re-read with the correct 465 * node size. 466 */ 467 if ( btreePtr->nodeSize != kMinNodeSize ) 468 { 469 err = setBlockSizeProc (btreePtr->fcbPtr, btreePtr->nodeSize); 470 M_ExitOnError (err); 471 472#if BSD 473 /* 474 * Need to use kTrashBlock option to force the 475 * buffer cache to re-read the entire node 476 */ 477 err = releaseBlockProc(btreePtr->fcbPtr, &nodeRec, kTrashBlock); 478#else 479 err = ReleaseNode (btreePtr, &nodeRec); 480#endif 481 482 err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec ); // calls CheckNode... 483 M_ExitOnError (err); 484 } 485 486 //�� total nodes * node size <= LEOF? 487 488 489 ////////////////////////// Get Key Descriptor /////////////////////////////// 490#if SupportsKeyDescriptors 491 if ( keyCompareProc == nil ) // if no key compare proc then get key descriptor 492 { 493 err = GetKeyDescriptor (btreePtr, nodeRec.buffer); //�� it should check amount of memory allocated... 494 M_ExitOnError (err); 495 496 err = CheckKeyDescriptor (btreePtr->keyDescPtr, btreePtr->maxKeyLength); 497 M_ExitOnError (err); 498 499 } 500 else 501#endif 502 { 503 btreePtr->keyDescPtr = nil; // clear it so we don't dispose garbage later 504 } 505 506 err = ReleaseNode (btreePtr, &nodeRec); 507 M_ExitOnError (err); 508 509 510#if BSD 511 /* 512 * Under Mac OS, b-tree nodes can be non-contiguous on disk when the 513 * allocation block size is smaller than the b-tree node size. 514 */ 515 if ( !NodesAreContiguous(filePtr, btreePtr->nodeSize) ) { 516 if (debug) fplog(stderr, "Nodes are not contiguous -- this is fatal\n"); 517 return fsBTInvalidNodeErr; 518 } 519#endif 520 521 //////////////////////////////// Success //////////////////////////////////// 522 523 //�� align LEOF to multiple of node size? - just on close 524 525// LogEndTime(kTraceOpenBTree, noErr); 526 527 return noErr; 528 529 530 /////////////////////// Error - Clean up and Exit /////////////////////////// 531 532ErrorExit: 533 534 filePtr->fcbBtree = nil; 535 (void) ReleaseNode (btreePtr, &nodeRec); 536 DisposeMemory( btreePtr ); 537 538// LogEndTime(kTraceOpenBTree, err); 539 540 return err; 541} 542 543 544 545/*------------------------------------------------------------------------------- 546Routine: BTClosePath - Flush BTree Header and Deallocate Memory for BTree. 547 548Function: Flush the BTreeControlBlock fields to header node, and delete BTree control 549 block and key descriptor associated with the file if filePtr is last 550 path of type kBTreeType ('btre'). 551 552 553Input: filePtr - pointer to file to delete BTree control block for. 554 555Result: noErr - success 556 fsBTInvalidFileErr - 557 != noErr - failure 558-------------------------------------------------------------------------------*/ 559 560OSStatus BTClosePath (SFCB *filePtr) 561{ 562 OSStatus err; 563 BTreeControlBlockPtr btreePtr; 564#if 0 565 FSPathControlBlockPtr tempPath; 566 Boolean otherBTreePathsOpen; 567#endif 568 569// LogStartTime(kTraceCloseBTree); 570 571 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; 572 573 if (btreePtr == nil) 574 return fsBTInvalidFileErr; 575 576 ////////////////////// Check for other BTree Paths ////////////////////////// 577 578#if 0 579//�� Need replacement field for pathType 580 otherBTreePathsOpen = false; 581 tempPath = forkPtr->fork.pathList.head; 582 while ( (tempPath != (FSPathControlBlockPtr) &forkPtr->fork.pathList) && 583 (otherBTreePathsOpen == false) ) 584 { 585 if ((tempPath != pathPtr) && (tempPath->path.pathType == kBTreeType)) 586 { 587 otherBTreePathsOpen = true; 588 break; // done with loop check 589 } 590 591 tempPath = tempPath->next; 592 } 593 594 ////////////////////////// Update Header Node /////////////////////////////// 595 596 597 if (otherBTreePathsOpen == true) 598 { 599 err = UpdateHeader (btreePtr); // update header even if we aren't closing 600 return err; // we only clean up after the last user... 601 } 602#endif 603 604 btreePtr->attributes &= ~kBTBadCloseMask; // clear "bad close" attribute bit 605 err = UpdateHeader (btreePtr); 606 M_ExitOnError (err); 607 608#if SupportsKeyDescriptors 609 if (btreePtr->keyDescPtr != nil) // deallocate keyDescriptor, if any 610 { 611 DisposeMemory( btreePtr->keyDescPtr ); 612 } 613#endif 614 615 DisposeMemory( btreePtr ); 616 filePtr->fcbBtree = nil; 617 618// LogEndTime(kTraceCloseBTree, noErr); 619 620 return noErr; 621 622 /////////////////////// Error - Clean Up and Exit /////////////////////////// 623 624ErrorExit: 625 626// LogEndTime(kTraceCloseBTree, err); 627 628 return err; 629} 630 631 632 633/*------------------------------------------------------------------------------- 634Routine: BTSearchRecord - Search BTree for a record with a matching key. 635 636Function: Search for position in B*Tree indicated by searchKey. If a valid node hint 637 is provided, it will be searched first, then SearchTree will be called. 638 If a BTreeIterator is provided, it will be set to the position found as 639 a result of the search. If a record exists at that position, and a BufferDescriptor 640 is supplied, the record will be copied to the buffer (as much as will fit), 641 and recordLen will be set to the length of the record. 642 643 If an error other than fsBTRecordNotFoundErr occurs, the BTreeIterator, if any, 644 is invalidated, and recordLen is set to 0. 645 646 647Input: pathPtr - pointer to path for BTree file. 648 searchKey - pointer to search key to match. 649 hintPtr - pointer to hint (may be nil) 650 651Output: record - pointer to BufferDescriptor containing record 652 recordLen - length of data at recordPtr 653 iterator - pointer to BTreeIterator indicating position result of search 654 655Result: noErr - success, record contains copy of record found 656 fsBTRecordNotFoundErr - record was not found, no data copied 657 fsBTInvalidFileErr - no BTreeControlBlock is allocated for the fork 658 fsBTInvalidKeyLengthErr - 659 != noErr - failure 660-------------------------------------------------------------------------------*/ 661 662OSStatus BTSearchRecord (SFCB *filePtr, 663 BTreeIterator *searchIterator, 664 UInt32 heuristicHint, 665 FSBufferDescriptor *record, 666 UInt16 *recordLen, 667 BTreeIterator *resultIterator ) 668{ 669 OSStatus err; 670 BTreeControlBlockPtr btreePtr; 671 TreePathTable treePathTable; 672 UInt32 nodeNum = 0; 673 BlockDescriptor node; 674 UInt16 index; 675 BTreeKeyPtr keyPtr; 676 RecordPtr recordPtr; 677 UInt16 len; 678 Boolean foundRecord; 679 Boolean validHint; 680 681 682// LogStartTime(kTraceSearchBTree); 683 684 if (filePtr == nil) return paramErr; 685 if (searchIterator == nil) return paramErr; 686 687 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; 688 if (btreePtr == nil) return fsBTInvalidFileErr; 689 690#if SupportsKeyDescriptors 691 if (btreePtr->keyCompareProc == nil) // CheckKey if we using Key Descriptor 692 { 693 err = CheckKey (&searchIterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength); 694 M_ExitOnError (err); 695 } 696#endif 697 698 foundRecord = false; 699 700 ////////////////////////////// Take A Hint ////////////////////////////////// 701 702 err = IsItAHint (btreePtr, searchIterator, &validHint); 703 M_ExitOnError (err); 704 705 if (validHint) 706 { 707 nodeNum = searchIterator->hint.nodeNum; 708 709 err = GetNode (btreePtr, nodeNum, &node); 710 if( err == noErr ) 711 { 712 if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode && 713 ((BTNodeDescriptor*) node.buffer)->numRecords > 0 ) 714 { 715 foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index); 716 717 //�� if !foundRecord, we could still skip tree search if ( 0 < index < numRecords ) 718 } 719 720 if (foundRecord == false) 721 { 722 err = ReleaseNode (btreePtr, &node); 723 M_ExitOnError (err); 724 } 725 else 726 { 727 ++btreePtr->numValidHints; 728 } 729 } 730 731 if( foundRecord == false ) 732 (void) BTInvalidateHint( searchIterator ); 733 } 734 735 ////////////////////////////// Try the heuristicHint ////////////////////////////////// 736 737 if ( (foundRecord == false) && (heuristicHint != kInvalidMRUCacheKey) && (nodeNum != heuristicHint) ) 738 { 739 // LogStartTime(kHeuristicHint); 740 nodeNum = heuristicHint; 741 742 err = GetNode (btreePtr, nodeNum, &node); 743 if( err == noErr ) 744 { 745 if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode && 746 ((BTNodeDescriptor*) node.buffer)->numRecords > 0 ) 747 { 748 foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index); 749 } 750 751 if (foundRecord == false) 752 { 753 err = ReleaseNode (btreePtr, &node); 754 M_ExitOnError (err); 755 } 756 } 757 // LogEndTime(kHeuristicHint, (foundRecord == false)); 758 } 759 760 //////////////////////////// Search The Tree //////////////////////////////// 761 762 if (foundRecord == false) 763 { 764 err = SearchTree ( btreePtr, &searchIterator->key, treePathTable, &nodeNum, &node, &index); 765 switch (err) 766 { 767 case noErr: foundRecord = true; break; 768 case fsBTRecordNotFoundErr: break; 769 default: goto ErrorExit; 770 } 771 } 772 773 774 //////////////////////////// Get the Record ///////////////////////////////// 775 776 if (foundRecord == true) 777 { 778 //�� Should check for errors! Or BlockMove could choke on recordPtr!!! 779 GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len); 780 781 if (recordLen != nil) *recordLen = len; 782 783 if (record != nil) 784 { 785 ByteCount recordSize; 786 787 recordSize = record->itemCount * record->itemSize; 788 789 PanicIf(len > recordSize, "\pBTSearchRecord: truncating record!"); 790 791 if (len > recordSize) len = recordSize; 792 793 CopyMemory (recordPtr, record->bufferAddress, len); 794 } 795 } 796 797 798 /////////////////////// Success - Update Iterator /////////////////////////// 799 800 if (resultIterator != nil) 801 { 802 resultIterator->hint.writeCount = btreePtr->writeCount; 803 resultIterator->hint.nodeNum = nodeNum; 804 resultIterator->hint.index = index; 805 resultIterator->hint.reserved1 = 0; 806 resultIterator->hint.reserved2 = 0; 807 808 resultIterator->version = 0; 809 resultIterator->reserved = 0; 810 811 // copy the key in the BTree when found rather than searchIterator->key to get proper case/diacriticals 812 if (foundRecord == true) 813 CopyKey(btreePtr, keyPtr, &resultIterator->key); 814 else 815 CopyKey(btreePtr, &searchIterator->key, &resultIterator->key); 816 } 817 818 err = ReleaseNode (btreePtr, &node); 819 M_ExitOnError (err); 820 821// LogEndTime(kTraceSearchBTree, (foundRecord == false)); 822 823 if (foundRecord == false) return fsBTRecordNotFoundErr; 824 else return noErr; 825 826 827 /////////////////////// Error - Clean Up and Exit /////////////////////////// 828 829ErrorExit: 830 831 if (recordLen != nil) 832 *recordLen = 0; 833 834 if (resultIterator != nil) 835 { 836 resultIterator->hint.writeCount = 0; 837 resultIterator->hint.nodeNum = 0; 838 resultIterator->hint.index = 0; 839 resultIterator->hint.reserved1 = 0; 840 resultIterator->hint.reserved2 = 0; 841 842 resultIterator->version = 0; 843 resultIterator->reserved = 0; 844 resultIterator->key.length16 = 0; // zero out two bytes to cover both types of keys 845 } 846 847 if ( err == fsBTEmptyErr ) 848 err = fsBTRecordNotFoundErr; 849 850// LogEndTime(kTraceSearchBTree, err); 851 852 return err; 853} 854 855 856 857/*------------------------------------------------------------------------------- 858Routine: BTIterateRecord - Find the first, next, previous, or last record. 859 860Function: Find the first, next, previous, or last record in the BTree 861 862Input: pathPtr - pointer to path iterate records for. 863 operation - iteration operation (first,next,prev,last) 864 iterator - pointer to iterator indicating start position 865 866Output: iterator - iterator is updated to indicate new position 867 newKeyPtr - pointer to buffer to copy key found by iteration 868 record - pointer to buffer to copy record found by iteration 869 recordLen - length of record 870 871Result: noErr - success 872 != noErr - failure 873-------------------------------------------------------------------------------*/ 874 875OSStatus BTIterateRecord (SFCB *filePtr, 876 BTreeIterationOperation operation, 877 BTreeIterator *iterator, 878 FSBufferDescriptor *record, 879 UInt16 *recordLen ) 880{ 881 OSStatus err; 882 BTreeControlBlockPtr btreePtr; 883 BTreeKeyPtr keyPtr; 884 RecordPtr recordPtr; 885 UInt16 len; 886 887 Boolean foundRecord; 888 UInt32 nodeNum; 889 890 BlockDescriptor left, node, right; 891 UInt16 index; 892 893 894// LogStartTime(kTraceGetBTreeRecord); 895 896 ////////////////////////// Priliminary Checks /////////////////////////////// 897 898 left.buffer = nil; 899 right.buffer = nil; 900 node.buffer = nil; 901 902 903 if (filePtr == nil) 904 { 905 return paramErr; 906 } 907 908 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; 909 if (btreePtr == nil) 910 { 911 return fsBTInvalidFileErr; //�� handle properly 912 } 913 914 if ((operation != kBTreeFirstRecord) && 915 (operation != kBTreeNextRecord) && 916 (operation != kBTreeCurrentRecord) && 917 (operation != kBTreePrevRecord) && 918 (operation != kBTreeLastRecord)) 919 { 920 err = fsInvalidIterationMovmentErr; 921 goto ErrorExit; 922 } 923 924 /////////////////////// Find First or Last Record /////////////////////////// 925 926 if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord)) 927 { 928 if (operation == kBTreeFirstRecord) nodeNum = btreePtr->firstLeafNode; 929 else nodeNum = btreePtr->lastLeafNode; 930 931 if (nodeNum == 0) 932 { 933 err = fsBTEmptyErr; 934 goto ErrorExit; 935 } 936 937 err = GetNode (btreePtr, nodeNum, &node); 938 M_ExitOnError (err); 939 940 if ( ((NodeDescPtr) node.buffer)->kind != kBTLeafNode || 941 ((NodeDescPtr) node.buffer)->numRecords <= 0 ) 942 { 943 err = ReleaseNode (btreePtr, &node); 944 M_ExitOnError (err); 945 946 if (debug) fprintf(stderr, "%s(%d): returning fsBTInvalidNodeErr\n", __FUNCTION__, __LINE__); 947 err = fsBTInvalidNodeErr; 948 goto ErrorExit; 949 } 950 951 if (operation == kBTreeFirstRecord) index = 0; 952 else index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1; 953 954 goto CopyData; //�� is there a cleaner way? 955 } 956 957 958 //////////////////////// Find Iterator Position ///////////////////////////// 959 960 err = FindIteratorPosition (btreePtr, iterator, 961 &left, &node, &right, &nodeNum, &index, &foundRecord); 962 M_ExitOnError (err); 963 964 965 ///////////////////// Find Next Or Previous Record ////////////////////////// 966 967 if (operation == kBTreePrevRecord) 968 { 969 if (index > 0) 970 { 971 --index; 972 } 973 else 974 { 975 if (left.buffer == nil) 976 { 977 nodeNum = ((NodeDescPtr) node.buffer)->bLink; 978 if ( nodeNum > 0) 979 { 980 err = GetNode (btreePtr, nodeNum, &left); 981 M_ExitOnError (err); 982 } else { 983 err = fsBTStartOfIterationErr; 984 goto ErrorExit; 985 } 986 } 987 // Before we stomp on "right", we'd better release it if needed 988 if (right.buffer != nil) { 989 err = ReleaseNode(btreePtr, &right); 990 M_ExitOnError(err); 991 } 992 right = node; 993 node = left; 994 left.buffer = nil; 995 index = ((NodeDescPtr) node.buffer)->numRecords -1; 996 } 997 } 998 else if (operation == kBTreeNextRecord) 999 { 1000 if ((foundRecord != true) && 1001 (((NodeDescPtr) node.buffer)->fLink == 0) && 1002 (index == ((NodeDescPtr) node.buffer)->numRecords)) 1003 { 1004 err = fsBTEndOfIterationErr; 1005 goto ErrorExit; 1006 } 1007 1008 // we did not find the record but the index is already positioned correctly 1009 if ((foundRecord == false) && (index != ((NodeDescPtr) node.buffer)->numRecords)) 1010 goto CopyData; 1011 1012 // we found the record OR we have to look in the next node 1013 if (index < ((NodeDescPtr) node.buffer)->numRecords -1) 1014 { 1015 ++index; 1016 } 1017 else 1018 { 1019 if (right.buffer == nil) 1020 { 1021 nodeNum = ((NodeDescPtr) node.buffer)->fLink; 1022 if ( nodeNum > 0) 1023 { 1024 err = GetNode (btreePtr, nodeNum, &right); 1025 M_ExitOnError (err); 1026 } else { 1027 err = fsBTEndOfIterationErr; 1028 goto ErrorExit; 1029 } 1030 } 1031 // Before we stomp on "left", we'd better release it if needed 1032 if (left.buffer != nil) { 1033 err = ReleaseNode(btreePtr, &left); 1034 M_ExitOnError(err); 1035 } 1036 left = node; 1037 node = right; 1038 right.buffer = nil; 1039 index = 0; 1040 } 1041 } 1042 else // operation == kBTreeCurrentRecord 1043 { 1044 // make sure we have something... <CS9> 1045 if ((foundRecord != true) && 1046 (index >= ((NodeDescPtr) node.buffer)->numRecords)) 1047 { 1048 err = fsBTEndOfIterationErr; 1049 goto ErrorExit; 1050 } 1051 } 1052 1053 //////////////////// Copy Record And Update Iterator //////////////////////// 1054 1055CopyData: 1056 1057 // added check for errors <CS9> 1058 err = GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len); 1059 M_ExitOnError (err); 1060 1061 if (recordLen != nil) *recordLen = len; 1062 1063 if (record != nil) 1064 { 1065 ByteCount recordSize; 1066 1067 recordSize = record->itemCount * record->itemSize; 1068 1069 PanicIf(len > recordSize, "\pBTIterateRecord: truncating record!"); 1070 1071 if (len > recordSize) len = recordSize; 1072 1073 CopyMemory (recordPtr, record->bufferAddress, len); 1074 } 1075 1076 if (iterator != nil) // first & last do not require iterator 1077 { 1078 iterator->hint.writeCount = btreePtr->writeCount; 1079 iterator->hint.nodeNum = nodeNum; 1080 iterator->hint.index = index; 1081 iterator->hint.reserved1 = 0; 1082 iterator->hint.reserved2 = 0; 1083 1084 iterator->version = 0; 1085 iterator->reserved = 0; 1086 1087 CopyKey(btreePtr, keyPtr, &iterator->key); 1088 } 1089 1090 1091 ///////////////////////////// Release Nodes ///////////////////////////////// 1092 1093 err = ReleaseNode (btreePtr, &node); 1094 M_ExitOnError (err); 1095 1096 if (left.buffer != nil) 1097 { 1098 err = ReleaseNode (btreePtr, &left); 1099 M_ExitOnError (err); 1100 } 1101 1102 if (right.buffer != nil) 1103 { 1104 err = ReleaseNode (btreePtr, &right); 1105 M_ExitOnError (err); 1106 } 1107 1108// LogEndTime(kTraceGetBTreeRecord, noErr); 1109 1110 return noErr; 1111 1112 /////////////////////// Error - Clean Up and Exit /////////////////////////// 1113 1114ErrorExit: 1115 1116 (void) ReleaseNode (btreePtr, &left); 1117 (void) ReleaseNode (btreePtr, &node); 1118 (void) ReleaseNode (btreePtr, &right); 1119 1120 if (recordLen != nil) 1121 *recordLen = 0; 1122 1123 if (iterator != nil) 1124 { 1125 iterator->hint.writeCount = 0; 1126 iterator->hint.nodeNum = 0; 1127 iterator->hint.index = 0; 1128 iterator->hint.reserved1 = 0; 1129 iterator->hint.reserved2 = 0; 1130 1131 iterator->version = 0; 1132 iterator->reserved = 0; 1133 iterator->key.length16 = 0; 1134 } 1135 1136 if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr ) 1137 err = fsBTRecordNotFoundErr; 1138 1139// LogEndTime(kTraceGetBTreeRecord, err); 1140 1141 return err; 1142} 1143 1144 1145//////////////////////////////// BTInsertRecord ///////////////////////////////// 1146 1147OSStatus BTInsertRecord (SFCB *filePtr, 1148 BTreeIterator *iterator, 1149 FSBufferDescriptor *record, 1150 UInt16 recordLen ) 1151{ 1152 OSStatus err; 1153 BTreeControlBlockPtr btreePtr; 1154 TreePathTable treePathTable; 1155 SInt32 nodesNeeded; 1156 BlockDescriptor nodeRec; 1157 UInt32 insertNodeNum; 1158 UInt16 index; 1159 Boolean recordFit; 1160 1161 1162 ////////////////////////// Priliminary Checks /////////////////////////////// 1163 1164 nodeRec.buffer = nil; // so we can call ReleaseNode 1165 1166 err = CheckInsertParams (filePtr, iterator, record, recordLen); 1167 if (err != noErr) 1168 return err; 1169 1170// LogStartTime(kTraceInsertBTreeRecord); 1171 1172 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; 1173 1174 ///////////////////////// Find Insert Position ////////////////////////////// 1175 1176 // always call SearchTree for Insert 1177 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index); 1178 1179 switch (err) // set/replace/insert decision point 1180 { 1181 case noErr: err = fsBTDuplicateRecordErr; 1182 goto ErrorExit; 1183 1184 case fsBTRecordNotFoundErr: break; 1185 1186 case fsBTEmptyErr: // if tree empty add 1st leaf node 1187 1188 if (btreePtr->freeNodes == 0) 1189 { 1190 err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1); 1191 M_ExitOnError (err); 1192 } 1193 1194 err = AllocateNode (btreePtr, &insertNodeNum); 1195 M_ExitOnError (err); 1196 1197 err = GetNewNode (btreePtr, insertNodeNum, &nodeRec); 1198 M_ExitOnError (err); 1199 1200 ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode; 1201 ((NodeDescPtr)nodeRec.buffer)->height = 1; 1202 1203 recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0, 1204 &iterator->key, KeyLength(btreePtr, &iterator->key), 1205 record->bufferAddress, recordLen ); 1206 if (recordFit != true) 1207 { 1208 err = fsBTRecordTooLargeErr; 1209 goto ErrorExit; 1210 } 1211 1212 err = UpdateNode (btreePtr, &nodeRec); 1213 M_ExitOnError (err); 1214 1215 // update BTreeControlBlock 1216 btreePtr->treeDepth = 1; 1217 btreePtr->rootNode = insertNodeNum; 1218 btreePtr->firstLeafNode = insertNodeNum; 1219 btreePtr->lastLeafNode = insertNodeNum; 1220 M_BTreeHeaderDirty (btreePtr); 1221 1222 goto Success; 1223 1224 default: 1225 goto ErrorExit; 1226 } 1227 1228 if (index > 0) 1229 { 1230 recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index, 1231 &iterator->key, KeyLength(btreePtr, &iterator->key), 1232 record->bufferAddress, recordLen); 1233 if (recordFit == true) 1234 { 1235 err = UpdateNode (btreePtr, &nodeRec); 1236 M_ExitOnError (err); 1237 1238 goto Success; 1239 } 1240 } 1241 1242 /////////////////////// Extend File If Necessary //////////////////////////// 1243 1244 nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //�� math limit 1245 if (nodesNeeded > 0) 1246 { 1247 nodesNeeded += btreePtr->totalNodes; 1248 if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too! 1249 ++nodesNeeded; 1250 1251 err = ExtendBTree (btreePtr, nodesNeeded); 1252 M_ExitOnError (err); 1253 } 1254 1255 // no need to delete existing record 1256 1257 err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress, 1258 recordLen, &nodeRec, index, 1, kInsertRecord, &insertNodeNum); 1259 M_ExitOnError (err); 1260 1261 1262 //////////////////////////////// Success //////////////////////////////////// 1263 1264Success: 1265 ++btreePtr->writeCount; // <CS10> 1266 ++btreePtr->leafRecords; 1267 M_BTreeHeaderDirty (btreePtr); 1268 1269 // create hint 1270 iterator->hint.writeCount = btreePtr->writeCount; // unused until <CS10> 1271 iterator->hint.nodeNum = insertNodeNum; 1272 iterator->hint.index = 0; // unused 1273 iterator->hint.reserved1 = 0; 1274 iterator->hint.reserved2 = 0; 1275 1276// LogEndTime(kTraceInsertBTreeRecord, noErr); 1277 1278 return noErr; 1279 1280 1281 ////////////////////////////// Error Exit /////////////////////////////////// 1282 1283ErrorExit: 1284 (void) ReleaseNode (btreePtr, &nodeRec); 1285 1286 iterator->hint.writeCount = 0; 1287 iterator->hint.nodeNum = 0; 1288 iterator->hint.index = 0; 1289 iterator->hint.reserved1 = 0; 1290 iterator->hint.reserved2 = 0; 1291 1292 if (err == fsBTEmptyErr) 1293 err = fsBTRecordNotFoundErr; 1294 1295// LogEndTime(kTraceInsertBTreeRecord, err); 1296 1297 return err; 1298} 1299 1300 1301 1302////////////////////////////////// BTSetRecord ////////////////////////////////// 1303#if 0 1304OSStatus BTSetRecord (SFCB *filePtr, 1305 BTreeIterator *iterator, 1306 FSBufferDescriptor *record, 1307 UInt16 recordLen ) 1308{ 1309 OSStatus err; 1310 BTreeControlBlockPtr btreePtr; 1311 TreePathTable treePathTable; 1312 SInt32 nodesNeeded; 1313 BlockDescriptor nodeRec; 1314 UInt32 insertNodeNum; 1315 UInt16 index; 1316 Boolean recordFound = false; 1317 Boolean recordFit; 1318 Boolean operation; 1319 Boolean validHint; 1320 1321 1322 ////////////////////////// Priliminary Checks /////////////////////////////// 1323 1324 nodeRec.buffer = nil; // so we can call ReleaseNode 1325 1326 err = CheckInsertParams (filePtr, iterator, record, recordLen); 1327 if (err != noErr) 1328 return err; 1329 1330 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; 1331 1332 1333 ///////////////////////// Find Insert Position ////////////////////////////// 1334 1335 err = IsItAHint (btreePtr, iterator, &validHint); 1336 M_ExitOnError (err); 1337 1338 if (validHint) 1339 { 1340 insertNodeNum = iterator->hint.nodeNum; 1341 1342 err = GetNode (btreePtr, insertNodeNum, &nodeRec); 1343 if( err == noErr ) 1344 { 1345 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit); 1346 M_ExitOnError (err); 1347 1348 if (recordFit) 1349 { 1350 err = UpdateNode (btreePtr, &nodeRec); 1351 M_ExitOnError (err); 1352 1353 recordFound = true; 1354 ++btreePtr->numValidHints; 1355 goto Success; 1356 } // else 1357 else 1358 { 1359 (void) BTInvalidateHint( iterator ); 1360 } 1361 1362 err = ReleaseNode (btreePtr, &nodeRec); 1363 M_ExitOnError (err); 1364 } 1365 } 1366 1367 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index); 1368 1369 switch (err) // set/replace/insert decision point 1370 { 1371 case noErr: recordFound = true; 1372 break; 1373 1374 case fsBTRecordNotFoundErr: break; 1375 1376 case fsBTEmptyErr: // if tree empty add 1st leaf node 1377 1378 if (btreePtr->freeNodes == 0) 1379 { 1380 err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1); 1381 M_ExitOnError (err); 1382 } 1383 1384 err = AllocateNode (btreePtr, &insertNodeNum); 1385 M_ExitOnError (err); 1386 1387 err = GetNewNode (btreePtr, insertNodeNum, &nodeRec); 1388 M_ExitOnError (err); 1389 1390 ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode; 1391 ((NodeDescPtr)nodeRec.buffer)->height = 1; 1392 1393 recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0, 1394 &iterator->key, KeyLength(btreePtr, &iterator->key), 1395 record->bufferAddress, recordLen ); 1396 if (recordFit != true) 1397 { 1398 err = fsBTRecordTooLargeErr; 1399 goto ErrorExit; 1400 } 1401 1402 err = UpdateNode (btreePtr, &nodeRec); 1403 M_ExitOnError (err); 1404 1405 // update BTreeControlBlock 1406 btreePtr->rootNode = insertNodeNum; 1407 btreePtr->treeDepth = 1; 1408 btreePtr->flags |= kBTHeaderDirty; 1409 1410 goto Success; 1411 1412 default: goto ErrorExit; 1413 } 1414 1415 1416 if (recordFound == true) // Simple Replace - optimization avoids unecessary ExtendBTree 1417 { 1418 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit); 1419 M_ExitOnError (err); 1420 1421 if (recordFit) 1422 { 1423 err = UpdateNode (btreePtr, &nodeRec); 1424 M_ExitOnError (err); 1425 1426 goto Success; 1427 } 1428 } 1429 1430 1431 /////////////////////// Extend File If Necessary //////////////////////////// 1432 1433 nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //�� math limit 1434 if (nodesNeeded > 0) 1435 { 1436 nodesNeeded += btreePtr->totalNodes; 1437 if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too! 1438 ++nodesNeeded; 1439 1440 err = ExtendBTree (btreePtr, nodesNeeded); 1441 M_ExitOnError (err); 1442 } 1443 1444 1445 if (recordFound == true) // Delete existing record 1446 { 1447 DeleteRecord (btreePtr, nodeRec.buffer, index); 1448 operation = kReplaceRecord; 1449 } else { 1450 operation = kInsertRecord; 1451 } 1452 1453 err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress, 1454 recordLen, &nodeRec, index, 1, operation, &insertNodeNum); 1455 M_ExitOnError (err); 1456 1457 ++btreePtr->writeCount; // <CS10> writeCount changes only if the tree structure changed 1458 1459Success: 1460 if (recordFound == false) 1461 { 1462 ++btreePtr->leafRecords; 1463 M_BTreeHeaderDirty (btreePtr); 1464 } 1465 1466 // create hint 1467 iterator->hint.writeCount = btreePtr->writeCount; // unused until <CS10> 1468 iterator->hint.nodeNum = insertNodeNum; 1469 iterator->hint.index = 0; // unused 1470 iterator->hint.reserved1 = 0; 1471 iterator->hint.reserved2 = 0; 1472 1473 return noErr; 1474 1475 1476 ////////////////////////////// Error Exit /////////////////////////////////// 1477 1478ErrorExit: 1479 1480 (void) ReleaseNode (btreePtr, &nodeRec); 1481 1482 iterator->hint.writeCount = 0; 1483 iterator->hint.nodeNum = 0; 1484 iterator->hint.index = 0; 1485 iterator->hint.reserved1 = 0; 1486 iterator->hint.reserved2 = 0; 1487 1488 return err; 1489} 1490#endif 1491 1492 1493//////////////////////////////// BTReplaceRecord //////////////////////////////// 1494 1495OSStatus BTReplaceRecord (SFCB *filePtr, 1496 BTreeIterator *iterator, 1497 FSBufferDescriptor *record, 1498 UInt16 recordLen ) 1499{ 1500 OSStatus err; 1501 BTreeControlBlockPtr btreePtr; 1502 TreePathTable treePathTable; 1503 SInt32 nodesNeeded; 1504 BlockDescriptor nodeRec; 1505 UInt32 insertNodeNum; 1506 UInt16 index; 1507 Boolean recordFit; 1508 Boolean validHint; 1509 1510 1511 ////////////////////////// Priliminary Checks /////////////////////////////// 1512 1513 nodeRec.buffer = nil; // so we can call ReleaseNode 1514 1515 err = CheckInsertParams (filePtr, iterator, record, recordLen); 1516 if (err != noErr) 1517 return err; 1518 1519// LogStartTime(kTraceReplaceBTreeRecord); 1520 1521 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; 1522 1523 ////////////////////////////// Take A Hint ////////////////////////////////// 1524 1525 err = IsItAHint (btreePtr, iterator, &validHint); 1526 M_ExitOnError (err); 1527 1528 if (validHint) 1529 { 1530 insertNodeNum = iterator->hint.nodeNum; 1531 1532 err = GetNode (btreePtr, insertNodeNum, &nodeRec); 1533 if( err == noErr ) 1534 { 1535 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit); 1536 M_ExitOnError (err); 1537 1538 if (recordFit) 1539 { 1540 err = UpdateNode (btreePtr, &nodeRec); 1541 M_ExitOnError (err); 1542 1543 ++btreePtr->numValidHints; 1544 1545 goto Success; 1546 } 1547 else 1548 { 1549 (void) BTInvalidateHint( iterator ); 1550 } 1551 1552 err = ReleaseNode (btreePtr, &nodeRec); 1553 M_ExitOnError (err); 1554 } 1555 else 1556 { 1557 (void) BTInvalidateHint( iterator ); 1558 } 1559 } 1560 1561 1562 ////////////////////////////// Get A Clue /////////////////////////////////// 1563 1564 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index); 1565 M_ExitOnError (err); // record must exit for Replace 1566 1567 // optimization - if simple replace will work then don't extend btree 1568 // �� if we tried this before, and failed because it wouldn't fit then we shouldn't try this again... 1569 1570 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit); 1571 M_ExitOnError (err); 1572 1573 if (recordFit) 1574 { 1575 err = UpdateNode (btreePtr, &nodeRec); 1576 M_ExitOnError (err); 1577 1578 goto Success; 1579 } 1580 1581 1582 //////////////////////////// Make Some Room ///////////////////////////////// 1583 1584 nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //�� math limit 1585 if (nodesNeeded > 0) 1586 { 1587 nodesNeeded += btreePtr->totalNodes; 1588 if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too! 1589 ++nodesNeeded; 1590 1591 err = ExtendBTree (btreePtr, nodesNeeded); 1592 M_ExitOnError (err); 1593 } 1594 1595 1596 DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record 1597 1598 err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress, 1599 recordLen, &nodeRec, index, 1, kReplaceRecord, &insertNodeNum); 1600 M_ExitOnError (err); 1601 1602 ++btreePtr->writeCount; // <CS10> writeCount changes only if the tree structure changed 1603 1604Success: 1605 // create hint 1606 iterator->hint.writeCount = btreePtr->writeCount; // unused until <CS10> 1607 iterator->hint.nodeNum = insertNodeNum; 1608 iterator->hint.index = 0; // unused 1609 iterator->hint.reserved1 = 0; 1610 iterator->hint.reserved2 = 0; 1611 1612// LogEndTime(kTraceReplaceBTreeRecord, noErr); 1613 1614 return noErr; 1615 1616 1617 ////////////////////////////// Error Exit /////////////////////////////////// 1618 1619ErrorExit: 1620 1621 (void) ReleaseNode (btreePtr, &nodeRec); 1622 1623 iterator->hint.writeCount = 0; 1624 iterator->hint.nodeNum = 0; 1625 iterator->hint.index = 0; 1626 iterator->hint.reserved1 = 0; 1627 iterator->hint.reserved2 = 0; 1628 1629// LogEndTime(kTraceReplaceBTreeRecord, err); 1630 1631 return err; 1632} 1633 1634 1635 1636//////////////////////////////// BTDeleteRecord ///////////////////////////////// 1637 1638OSStatus BTDeleteRecord (SFCB *filePtr, 1639 BTreeIterator *iterator ) 1640{ 1641 OSStatus err; 1642 BTreeControlBlockPtr btreePtr; 1643 TreePathTable treePathTable; 1644 BlockDescriptor nodeRec; 1645 UInt32 nodeNum; 1646 UInt16 index; 1647 1648// LogStartTime(kTraceDeleteBTreeRecord); 1649 1650 ////////////////////////// Priliminary Checks /////////////////////////////// 1651 1652 nodeRec.buffer = nil; // so we can call ReleaseNode 1653 1654 M_ReturnErrorIf (filePtr == nil, paramErr); 1655 M_ReturnErrorIf (iterator == nil, paramErr); 1656 1657 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; 1658 if (btreePtr == nil) 1659 { 1660 err = fsBTInvalidFileErr; 1661 goto ErrorExit; 1662 } 1663 1664#if SupportsKeyDescriptors 1665 if (btreePtr->keyDescPtr != nil) 1666 { 1667 err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength); 1668 M_ExitOnError (err); 1669 } 1670#endif 1671 1672 /////////////////////////////// Find Key //////////////////////////////////// 1673 1674 //�� check hint for simple delete case (index > 0, numRecords > 2) 1675 1676 err = SearchTree (btreePtr, &iterator->key, treePathTable, &nodeNum, &nodeRec, &index); 1677 M_ExitOnError (err); // record must exit for Delete 1678 1679 1680 ///////////////////////////// Delete Record ///////////////////////////////// 1681 1682 err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1); 1683 M_ExitOnError (err); 1684 1685//Success: 1686 ++btreePtr->writeCount; // <CS10> 1687 --btreePtr->leafRecords; 1688 M_BTreeHeaderDirty (btreePtr); 1689 1690 iterator->hint.nodeNum = 0; 1691 1692// LogEndTime(kTraceDeleteBTreeRecord, noErr); 1693 1694 return noErr; 1695 1696 ////////////////////////////// Error Exit /////////////////////////////////// 1697 1698ErrorExit: 1699 (void) ReleaseNode (btreePtr, &nodeRec); 1700 1701// LogEndTime(kTraceDeleteBTreeRecord, err); 1702 1703 return err; 1704} 1705 1706 1707 1708OSStatus BTGetInformation (SFCB *filePtr, 1709 UInt16 version, 1710 BTreeInfoRec *info ) 1711{ 1712#pragma unused (version) 1713 1714 BTreeControlBlockPtr btreePtr; 1715 1716 1717 M_ReturnErrorIf (filePtr == nil, paramErr); 1718 1719 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; 1720 1721 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr); 1722 M_ReturnErrorIf (info == nil, paramErr); 1723 1724 //�� check version? 1725 1726 info->nodeSize = btreePtr->nodeSize; 1727 info->maxKeyLength = btreePtr->maxKeyLength; 1728 info->treeDepth = btreePtr->treeDepth; 1729 info->numRecords = btreePtr->leafRecords; 1730 info->numNodes = btreePtr->totalNodes; 1731 info->numFreeNodes = btreePtr->freeNodes; 1732 info->keyDescriptor = btreePtr->keyDescPtr; //�� this won't do at all... 1733 info->reserved = 0; 1734 1735 if (btreePtr->keyDescPtr == nil) 1736 info->keyDescLength = 0; 1737 else 1738 info->keyDescLength = (UInt32) btreePtr->keyDescPtr->length; 1739 1740 return noErr; 1741} 1742 1743 1744 1745/*------------------------------------------------------------------------------- 1746Routine: BTFlushPath - Flush BTreeControlBlock to Header Node. 1747 1748Function: Brief_description_of_the_function_and_any_side_effects 1749 1750 1751Input: pathPtr - pointer to path control block for B*Tree file to flush 1752 1753Output: none 1754 1755Result: noErr - success 1756 != noErr - failure 1757-------------------------------------------------------------------------------*/ 1758 1759OSStatus BTFlushPath (SFCB *filePtr) 1760{ 1761 OSStatus err; 1762 BTreeControlBlockPtr btreePtr; 1763 1764 1765// LogStartTime(kTraceFlushBTree); 1766 1767 M_ReturnErrorIf (filePtr == nil, paramErr); 1768 1769 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; 1770 1771 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr); 1772 1773 err = UpdateHeader (btreePtr); 1774 1775// LogEndTime(kTraceFlushBTree, err); 1776 1777 return err; 1778} 1779 1780 1781 1782/*------------------------------------------------------------------------------- 1783Routine: BTInvalidateHint - Invalidates the hint within a BTreeInterator. 1784 1785Function: Invalidates the hint within a BTreeInterator. 1786 1787 1788Input: iterator - pointer to BTreeIterator 1789 1790Output: iterator - iterator with the hint.nodeNum cleared 1791 1792Result: noErr - success 1793 paramErr - iterator == nil 1794-------------------------------------------------------------------------------*/ 1795 1796 1797OSStatus BTInvalidateHint (BTreeIterator *iterator ) 1798{ 1799 if (iterator == nil) 1800 return paramErr; 1801 1802 iterator->hint.nodeNum = 0; 1803 1804 return noErr; 1805} 1806 1807