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: BTree.c 30 31 Contains: Implementation of public interface routines for B-tree manager. 32 33 Version: HFS Plus 1.0 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 <MOSXS> 9/22/99 ser Added routines BTGetLastSync and BTSetLastSync 55 <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6. 56 <MOSXS> 6/30/98 djb In BTOpenPath make sure nodes are contiguous on disk (radar #2249539). 57 <MOSXS> 4/15/98 djb In BTOpenPath need to clear nodeRec.buffer if GetBlockProc fails. 58 <MOSXS> 4/11/98 djb Add RequireFileLock checking to all external entry points. 59 60 <MOSXS> 03/23/98 djb In BTOpenPath use kTrashBlock option when releasing the header so 61 that we get a full node when we call GetNode. 62 63 <CS9> 12/12/97 djb Radar #2202682, BTIterateRecord with kBTreeCurrentRecord was not 64 checking if we had a record and could call BlockMove with an 65 uninitialize source pointer (causing a bus error). 66 <CS8> 10/24/97 msd In BTIterateRecord, when moving to the previous or next record 67 and we have to move to another node, see if we need to release 68 the node about to be "shifted out" (opposite sibling of the 69 direction we need to move). 70 <CS7> 7/25/97 DSH BTSearchRecord now takes a heuristicHint, nodeNum, and tries it 71 before calling SearchBTree 72 <CS6> 7/24/97 djb GetBlockProc now take a file refnum instead of an FCB ptr. 73 <CS5> 7/22/97 djb Move trace points from BTreeWrapper.c to here. 74 <CS4> 7/21/97 djb LogEndTime now takes an error code. 75 <CS3> 7/16/97 DSH FilesInternal.i renamed FileMgrInternal.i to avoid name 76 collision 77 <CS2> 5/19/97 djb Add summary traces to BTIterateRecord. 78 <CS1> 4/23/97 djb first checked in 79 80 <HFS7> 2/19/97 djb Enable variable sized index keys for HFS+ volumes. Added node 81 cache to support nodes larger than 512 bytes. 82 <HFS6> 1/27/97 djb Calls to InsertTree and DeleteTree are now recursive (to support 83 variable sized index keys). 84 <HFS5> 1/13/97 djb Added support for getting current record to BTIterateRecord. 85 <HFS4> 1/6/97 djb Initialize "BigKeys" attribute in BTOpen. 86 <HFS3> 1/3/97 djb Added support for large keys. 87 <HFS2> 12/23/96 djb On exit map fsBTEmptyErr and fsBTEndOfIterationErr to 88 fsBTRecordNotFoundErr. 89 <HFS1> 12/19/96 djb first checked in 90 91 History applicable to original Scarecrow Design: 92 93 <13> 10/25/96 ser Changing for new VFPI 94 <12> 10/18/96 ser Converting over VFPI changes 95 <11> 9/17/96 dkh More BTree statistics. Modified hint checks to not bail out when 96 an error is returned from GetNode. 97 <10> 9/16/96 dkh Revised BTree statistics. 98 <9> 8/23/96 dkh Remove checks for multiple paths to BTree file. Need to add 99 equivalent mechanism later. 100 <8> 6/20/96 dkh Radar #1358740. Switch from using Pools to debug MemAllocators. 101 <7> 3/14/96 jev Fix BTreeSetRecord, recordFound was not set for the case of a 102 simple replace causing the leafRecords count to get bumped even 103 though we didn't have to add a record. 104 <6> 3/1/96 prp Fix lint problems. Bug in BTSetRecord that does not initialize 105 recordFound. 106 <5> 1/22/96 dkh Add #include Memory.h 107 <4> 1/10/96 msd Use the real function names from Math64.i. 108 <3> 1/4/96 jev Fix BTItererateRecord for the condition when the iterator 109 position routine does not find the record and we are looking for 110 the next record. In such a case, if the node's forrward link is 111 non-zero, we have to keep iterating next and not return 112 fsBTEndOfIterationErr error. 113 <2> 12/7/95 dkh D10E2 build. Changed usage of Ref data type to LogicalAddress. 114 <1> 10/18/95 rst Moved from Scarecrow project. 115 116 <24> 7/18/95 mbb Change MoveData & ClearBytes to BlockMoveData & BlockZero. 117 <23> 1/31/95 prp GetBlockProc interface uses a 64 bit node number. 118 <22> 1/12/95 wjk Adopt Model FileSystem changes in D5. 119 <21> 11/16/94 prp Add IsItAHint routine and use it whenever hint's node number was 120 used for testing. 121 <20> 11/10/94 prp BTGetInfo name collides with the same name in FileManagerPriv.i. 122 Change it to BTGetInformation. 123 <19> 9/30/94 prp Get in sync with D2 interface changes. 124 <18> 7/22/94 wjk Convert to the new set of header files. 125 <17> 12/9/93 wjk Cleanup usage of char, Byte, int8, UInt8, etc. 126 <16> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and 127 NRCmds environments. 128 <15> 11/30/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and 129 NRCmds environments. 130 <14> 9/30/93 gs Rename E_NoGetNodeProc and E_NoReleaseNodeProc to 131 E_NoXxxxBlockProc. 132 <13> 8/31/93 prp Use Set64U instead of Set64. 133 <12> 8/16/93 prp In BTSearchRecord, if the input hint found the node and record, 134 set the local nodeNum variable correctly so that the resultant 135 iterator gets set correctly. 136 <11> 7/1/93 gs Fix bug in BTIterateRecord related to kBTreePrevRecord 137 operation. 138 <10> 6/2/93 gs Update for changes to FSErrors.h and add some comments. 139 <9> 5/24/93 gs Fix bug in BTInsert/Set/ReplaceRecord which didn't set node hint 140 properly in some cases. 141 <8> 5/24/93 gs Do NOT map fsBTEmptyErr to fsBTRecordNotFoundErr in BTSearchRecord. 142 <7> 5/24/93 gs Rename BTFlush to BTFlushPath. 143 <6> 5/21/93 gs Add hint optimization to Set/Replace routines. 144 <5> 5/10/93 gs Remove Panic from BTInitialize for small logicalEOF. Implement 145 Insert, Set, Replace, and Delete. 146 <4> 3/23/93 gs Finish BTInitialize. 147 <3> 2/8/93 gs Implement BTSearchRecord and BTIterateRecord. 148 <2> 12/8/92 gs Implement Open and Close routines. 149 <1> 11/15/92 gs first checked in 150 151*/ 152 153#include "../headers/BTreesPrivate.h" 154#include "../../hfs_btreeio.h" 155 156/* 157 * The amount that the BTree header leaf count can be wrong before we assume 158 * it is in an infinite loop. 159 */ 160#define kNumLeafRecSlack 10 161 162//////////////////////////////////// Globals //////////////////////////////////// 163 164 165/////////////////////////// BTree Module Entry Points /////////////////////////// 166 167 168 169/*------------------------------------------------------------------------------- 170Routine: BTOpenPath - Open a file for access as a B*Tree. 171 172Function: Create BTree control block for a file, if necessary. Validates the 173 file to be sure it looks like a BTree file. 174 175 176Input: filePtr - pointer to file to open as a B-tree 177 keyCompareProc - pointer to client's KeyCompare function 178 179Result: noErr - success 180 paramErr - required ptr was nil 181 fsBTInvalidFileErr - 182 memFullErr - 183 != noErr - failure 184-------------------------------------------------------------------------------*/ 185 186OSStatus BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc) 187{ 188 OSStatus err; 189 BTreeControlBlockPtr btreePtr; 190 BTHeaderRec *header; 191 NodeRec nodeRec; 192 193 ////////////////////// Preliminary Error Checking /////////////////////////// 194 195 if ( filePtr == nil ) 196 { 197 return paramErr; 198 } 199 200 /* 201 * Subsequent opens allow key compare proc to be changed. 202 */ 203 if ( filePtr->fcbBTCBPtr != nil && keyCompareProc != nil) { 204 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 205 btreePtr->keyCompareProc = keyCompareProc; 206 return noErr; 207 } 208 209 if ( filePtr->fcbEOF < kMinNodeSize ) 210 return fsBTInvalidFileErr; 211 212 213 //////////////////////// Allocate Control Block ///////////////////////////// 214 215 btreePtr = (BTreeControlBlock*) NewPtrSysClear( sizeof( BTreeControlBlock ) ); 216 if (btreePtr == nil) 217 { 218 Panic ("BTOpen: no memory for btreePtr."); 219 return memFullErr; 220 } 221 222 btreePtr->getBlockProc = GetBTreeBlock; 223 btreePtr->releaseBlockProc = ReleaseBTreeBlock; 224 btreePtr->setEndOfForkProc = ExtendBTreeFile; 225 btreePtr->keyCompareProc = keyCompareProc; 226 227 /////////////////////////// Read Header Node //////////////////////////////// 228 229 nodeRec.buffer = nil; // so we can call ReleaseNode 230 btreePtr->fileRefNum = GetFileRefNumFromFCB(filePtr); 231 filePtr->fcbBTCBPtr = (Ptr) btreePtr; // attach btree cb to file 232 233 /* Prefer doing I/O a physical block at a time */ 234 nodeRec.blockSize = VTOHFS(btreePtr->fileRefNum)->hfs_physical_block_size; 235 236 /* Start with the allocation block size for regular files. */ 237 if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID) 238 { 239 nodeRec.blockSize = FCBTOVCB(filePtr)->blockSize; 240 } 241 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false); 242 243 // it is now safe to call M_ExitOnError (err) 244 245 err = SetBTreeBlockSize (btreePtr->fileRefNum, nodeRec.blockSize, 1); 246 M_ExitOnError (err); 247 248 249 err = GetBTreeBlock(btreePtr->fileRefNum, 250 kHeaderNodeNum, 251 kGetBlock, 252 &nodeRec ); 253 if (err != noErr) 254 { 255 nodeRec.buffer = nil; 256 nodeRec.blockHeader = nil; 257 Panic("BTOpen: getNodeProc returned error getting header node."); 258 goto ErrorExit; 259 } 260 ++btreePtr->numGetNodes; 261 header = (BTHeaderRec*) ((uintptr_t)nodeRec.buffer + sizeof(BTNodeDescriptor)); 262 263 264 ///////////////////////////// verify header ///////////////////////////////// 265 266 err = VerifyHeader (filePtr, header); 267 M_ExitOnError (err); 268 269 270 ///////////////////// Initalize fields from header ////////////////////////// 271 272 PanicIf ( (FCBTOVCB(filePtr)->vcbSigWord != 0x4244) && (header->nodeSize == 512), " BTOpenPath: wrong node size for HFS+ volume!"); // 0x4244 = 'BD' 273 274 btreePtr->treeDepth = header->treeDepth; 275 btreePtr->rootNode = header->rootNode; 276 btreePtr->leafRecords = header->leafRecords; 277 btreePtr->firstLeafNode = header->firstLeafNode; 278 btreePtr->lastLeafNode = header->lastLeafNode; 279 btreePtr->nodeSize = header->nodeSize; 280 btreePtr->maxKeyLength = header->maxKeyLength; 281 btreePtr->totalNodes = header->totalNodes; 282 btreePtr->freeNodes = header->freeNodes; 283 if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID) 284 filePtr->ff_clumpsize = header->clumpSize; 285 btreePtr->btreeType = header->btreeType; 286 287 btreePtr->keyCompareType = header->keyCompareType; 288 289 btreePtr->attributes = header->attributes; 290 291 if ( btreePtr->maxKeyLength > 40 ) 292 btreePtr->attributes |= (kBTBigKeysMask + kBTVariableIndexKeysMask); //�� we need a way to save these attributes 293 294 /////////////////////// Initialize dynamic fields /////////////////////////// 295 296 btreePtr->version = kBTreeVersion; 297 btreePtr->flags = 0; 298 btreePtr->writeCount = 1; 299 300 /////////////////////////// Check Header Node /////////////////////////////// 301 302 // set kBadClose attribute bit, and UpdateNode 303 304 /* b-tree node size must be at least as big as the logical block size */ 305 if (btreePtr->nodeSize < VTOHFS(btreePtr->fileRefNum)->hfs_logical_block_size) 306 { 307 /* 308 * If this tree has any records or the media is writeable then 309 * we cannot mount using the current physical block size. 310 */ 311 if (btreePtr->leafRecords > 0 || 312 VTOHFS(btreePtr->fileRefNum)->hfs_flags & HFS_WRITEABLE_MEDIA) 313 { 314 err = fsBTBadNodeSize; 315 goto ErrorExit; 316 } 317 } 318 319 /* 320 * If the actual node size is different than the amount we read, 321 * then release and trash this block, and re-read with the correct 322 * node size. 323 */ 324 if ( btreePtr->nodeSize != nodeRec.blockSize ) 325 { 326 err = SetBTreeBlockSize (btreePtr->fileRefNum, btreePtr->nodeSize, 32); 327 M_ExitOnError (err); 328 329 /* 330 * Need to use kTrashBlock option to force the 331 * buffer cache to read the entire node 332 */ 333 err = ReleaseBTreeBlock(btreePtr->fileRefNum, &nodeRec, kTrashBlock); 334 ++btreePtr->numReleaseNodes; 335 M_ExitOnError (err); 336 337 err = GetNode (btreePtr, kHeaderNodeNum, 0, &nodeRec ); 338 M_ExitOnError (err); 339 } 340 341 //�� total nodes * node size <= LEOF? 342 343 344 err = ReleaseNode (btreePtr, &nodeRec); 345 M_ExitOnError (err); 346 347 /* 348 * Under Mac OS, b-tree nodes can be non-contiguous on disk when the 349 * allocation block size is smaller than the b-tree node size. 350 * 351 * If journaling is turned on for this volume we can't deal with this 352 * situation and so we bail out. If journaling isn't on it's ok as 353 * hfs_strategy_fragmented() deals with it. Journaling can't support 354 * this because it assumes that if you give it a block that it's 355 * contiguous on disk. 356 */ 357 if ( FCBTOHFS(filePtr)->jnl && !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) ) { 358 return fsBTInvalidNodeErr; 359 } 360 361 //////////////////////////////// Success //////////////////////////////////// 362 363 //�� align LEOF to multiple of node size? - just on close 364 365 return noErr; 366 367 368 /////////////////////// Error - Clean up and Exit /////////////////////////// 369 370ErrorExit: 371 372 filePtr->fcbBTCBPtr = nil; 373 (void) ReleaseNode (btreePtr, &nodeRec); 374 DisposePtr( (Ptr) btreePtr ); 375 376 return err; 377} 378 379 380 381/*------------------------------------------------------------------------------- 382Routine: BTClosePath - Flush BTree Header and Deallocate Memory for BTree. 383 384Function: Flush the BTreeControlBlock fields to header node, and delete BTree control 385 block and key descriptor associated with the file if filePtr is last 386 path of type kBTreeType ('btre'). 387 388 389Input: filePtr - pointer to file to delete BTree control block for. 390 391Result: noErr - success 392 fsBTInvalidFileErr - 393 != noErr - failure 394-------------------------------------------------------------------------------*/ 395 396OSStatus BTClosePath (FCB *filePtr) 397{ 398 OSStatus err; 399 BTreeControlBlockPtr btreePtr; 400 401 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 402 403 if (btreePtr == nil) 404 return fsBTInvalidFileErr; 405 406 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false); 407 408 ////////////////////// Check for other BTree Paths ////////////////////////// 409 410 btreePtr->attributes &= ~kBTBadCloseMask; // clear "bad close" attribute bit 411 err = UpdateHeader (btreePtr, true); 412 M_ExitOnError (err); 413 414 DisposePtr( (Ptr) btreePtr ); 415 filePtr->fcbBTCBPtr = nil; 416 417 return noErr; 418 419 /////////////////////// Error - Clean Up and Exit /////////////////////////// 420 421ErrorExit: 422 423 return err; 424} 425 426 427 428/*------------------------------------------------------------------------------- 429Routine: BTSearchRecord - Search BTree for a record with a matching key. 430 431Function: Search for position in B*Tree indicated by searchKey. If a valid node hint 432 is provided, it will be searched first, then SearchTree will be called. 433 If a BTreeIterator is provided, it will be set to the position found as 434 a result of the search. If a record exists at that position, and a BufferDescriptor 435 is supplied, the record will be copied to the buffer (as much as will fit), 436 and recordLen will be set to the length of the record. 437 438 If an error other than fsBTRecordNotFoundErr occurs, the BTreeIterator, if any, 439 is invalidated, and recordLen is set to 0. 440 441 442Input: pathPtr - pointer to path for BTree file. 443 searchKey - pointer to search key to match. 444 hintPtr - pointer to hint (may be nil) 445 446Output: record - pointer to BufferDescriptor containing record 447 recordLen - length of data at recordPtr 448 iterator - pointer to BTreeIterator indicating position result of search 449 450Result: noErr - success, record contains copy of record found 451 fsBTRecordNotFoundErr - record was not found, no data copied 452 fsBTInvalidFileErr - no BTreeControlBlock is allocated for the fork 453 fsBTInvalidKeyLengthErr - 454 != noErr - failure 455-------------------------------------------------------------------------------*/ 456 457OSStatus BTSearchRecord (FCB *filePtr, 458 BTreeIterator *searchIterator, 459 FSBufferDescriptor *record, 460 u_int16_t *recordLen, 461 BTreeIterator *resultIterator ) 462{ 463 OSStatus err; 464 BTreeControlBlockPtr btreePtr; 465 TreePathTable treePathTable; 466 u_int32_t nodeNum; 467 BlockDescriptor node; 468 u_int16_t index; 469 BTreeKeyPtr keyPtr; 470 RecordPtr recordPtr; 471 u_int16_t len; 472 Boolean foundRecord; 473 Boolean validHint; 474 475 if (filePtr == nil) 476 { 477 return paramErr; 478 } 479 480 if (searchIterator == nil) 481 { 482 return paramErr; 483 } 484 485 node.buffer = nil; 486 node.blockHeader = nil; 487 488 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 489 if (btreePtr == nil) 490 { 491 return fsBTInvalidFileErr; 492 } 493 494 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true); 495 496 foundRecord = false; 497 498 ////////////////////////////// Take A Hint ////////////////////////////////// 499 500 err = IsItAHint (btreePtr, searchIterator, &validHint); 501 M_ExitOnError (err); 502 503 if (validHint) 504 { 505 nodeNum = searchIterator->hint.nodeNum; 506 507 err = GetNode (btreePtr, nodeNum, kGetNodeHint, &node); 508 if( err == noErr ) 509 { 510 if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode && 511 ((BTNodeDescriptor*) node.buffer)->numRecords > 0 ) 512 { 513 foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index); 514 515 //�� if !foundRecord, we could still skip tree search if ( 0 < index < numRecords ) 516 } 517 518 if (foundRecord == false) 519 { 520 err = ReleaseNode (btreePtr, &node); 521 M_ExitOnError (err); 522 } 523 else 524 { 525 ++btreePtr->numValidHints; 526 } 527 } 528 529 if( foundRecord == false ) 530 (void) BTInvalidateHint( searchIterator ); 531 } 532 533 534 //////////////////////////// Search The Tree //////////////////////////////// 535 536 if (foundRecord == false) 537 { 538 err = SearchTree ( btreePtr, &searchIterator->key, treePathTable, &nodeNum, &node, &index); 539 switch (err) 540 { 541 case noErr: 542 foundRecord = true; 543 break; 544 case fsBTRecordNotFoundErr: 545 break; 546 default: 547 goto ErrorExit; 548 } 549 } 550 551 552 //////////////////////////// Get the Record ///////////////////////////////// 553 554 if (foundRecord == true) 555 { 556 //XXX Should check for errors! Or BlockMove could choke on recordPtr!!! 557 GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len); 558 559 if (recordLen != nil) *recordLen = len; 560 561 if (record != nil) 562 { 563 ByteCount recordSize; 564 565 recordSize = record->itemCount * record->itemSize; 566 567 if (len > recordSize) len = recordSize; 568 569 BlockMoveData (recordPtr, record->bufferAddress, len); 570 } 571 } 572 573 574 /////////////////////// Success - Update Iterator /////////////////////////// 575 576 if (resultIterator != nil) 577 { 578 if (foundRecord) { 579 resultIterator->hint.writeCount = btreePtr->writeCount; 580 resultIterator->hint.nodeNum = nodeNum; 581 resultIterator->hint.index = index; 582 } 583#if DEBUG_BUILD 584 resultIterator->hint.reserved1 = 0; 585 resultIterator->hint.reserved2 = 0; 586 resultIterator->version = 0; 587 resultIterator->reserved = 0; 588#endif 589 // copy the key in the BTree when found rather than searchIterator->key to get proper case/diacriticals 590 if (foundRecord == true) 591 BlockMoveData ((Ptr)keyPtr, (Ptr)&resultIterator->key, CalcKeySize(btreePtr, keyPtr)); 592 else 593 BlockMoveData ((Ptr)&searchIterator->key, (Ptr)&resultIterator->key, CalcKeySize(btreePtr, &searchIterator->key)); 594 } 595 596 err = ReleaseNode (btreePtr, &node); 597 M_ExitOnError (err); 598 599 if (foundRecord == false) return fsBTRecordNotFoundErr; 600 else return noErr; 601 602 603 /////////////////////// Error - Clean Up and Exit /////////////////////////// 604 605ErrorExit: 606 607 if (recordLen != nil) 608 *recordLen = 0; 609 610 if (resultIterator != nil) 611 { 612 resultIterator->hint.writeCount = 0; 613 resultIterator->hint.nodeNum = 0; 614 resultIterator->hint.index = 0; 615 resultIterator->hint.reserved1 = 0; 616 resultIterator->hint.reserved2 = 0; 617 618 resultIterator->version = 0; 619 resultIterator->reserved = 0; 620 resultIterator->key.length16 = 0; // zero out two bytes to cover both types of keys 621 } 622 623 if ( err == fsBTEmptyErr ) 624 err = fsBTRecordNotFoundErr; 625 626 return err; 627} 628 629 630 631/*------------------------------------------------------------------------------- 632Routine: BTIterateRecord - Find the first, next, previous, or last record. 633 634Function: Find the first, next, previous, or last record in the BTree 635 636Input: pathPtr - pointer to path iterate records for. 637 operation - iteration operation (first,next,prev,last) 638 iterator - pointer to iterator indicating start position 639 640Output: iterator - iterator is updated to indicate new position 641 newKeyPtr - pointer to buffer to copy key found by iteration 642 record - pointer to buffer to copy record found by iteration 643 recordLen - length of record 644 645Result: noErr - success 646 != noErr - failure 647-------------------------------------------------------------------------------*/ 648 649OSStatus BTIterateRecord (FCB *filePtr, 650 BTreeIterationOperation operation, 651 BTreeIterator *iterator, 652 FSBufferDescriptor *record, 653 u_int16_t *recordLen ) 654{ 655 OSStatus err; 656 BTreeControlBlockPtr btreePtr; 657 BTreeKeyPtr keyPtr; 658 RecordPtr recordPtr; 659 u_int16_t len; 660 661 Boolean foundRecord; 662 u_int32_t nodeNum; 663 664 BlockDescriptor left, node, right; 665 u_int16_t index; 666 667 668 ////////////////////////// Priliminary Checks /////////////////////////////// 669 670 left.buffer = nil; 671 left.blockHeader = nil; 672 right.buffer = nil; 673 right.blockHeader = nil; 674 node.buffer = nil; 675 node.blockHeader = nil; 676 677 678 if (filePtr == nil) 679 { 680 return paramErr; 681 } 682 683 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 684 if (btreePtr == nil) 685 { 686 return fsBTInvalidFileErr; //�� handle properly 687 } 688 689 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true); 690 691 if ((operation != kBTreeFirstRecord) && 692 (operation != kBTreeNextRecord) && 693 (operation != kBTreeCurrentRecord) && 694 (operation != kBTreePrevRecord) && 695 (operation != kBTreeLastRecord)) 696 { 697 err = fsInvalidIterationMovmentErr; 698 goto ErrorExit; 699 } 700 701 /////////////////////// Find First or Last Record /////////////////////////// 702 703 if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord)) 704 { 705 if (operation == kBTreeFirstRecord) nodeNum = btreePtr->firstLeafNode; 706 else nodeNum = btreePtr->lastLeafNode; 707 708 if (nodeNum == 0) 709 { 710 err = fsBTEmptyErr; 711 goto ErrorExit; 712 } 713 714 err = GetNode (btreePtr, nodeNum, 0, &node); 715 M_ExitOnError (err); 716 717 if ( ((NodeDescPtr) node.buffer)->kind != kBTLeafNode || 718 ((NodeDescPtr) node.buffer)->numRecords <= 0 ) 719 { 720 err = ReleaseNode (btreePtr, &node); 721 M_ExitOnError (err); 722 723 err = fsBTInvalidNodeErr; 724 printf ("hfs: BTIterateRecord() found invalid btree node on volume %s\n", FCBTOVCB(filePtr)->vcbVN); 725 hfs_mark_volume_inconsistent(FCBTOVCB(filePtr)); 726 goto ErrorExit; 727 } 728 729 if (operation == kBTreeFirstRecord) index = 0; 730 else index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1; 731 732 goto CopyData; //�� is there a cleaner way? 733 } 734 735 736 //////////////////////// Find Iterator Position ///////////////////////////// 737 738 // Not called for (operation == kBTreeFirstRecord || operation == kBTreeLastRecord) 739 err = FindIteratorPosition (btreePtr, iterator, 740 &left, &node, &right, &nodeNum, &index, &foundRecord); 741 M_ExitOnError (err); 742 743 744 ///////////////////// Find Next Or Previous Record ////////////////////////// 745 746 if (operation == kBTreePrevRecord) 747 { 748 if (index > 0) 749 { 750 --index; 751 } 752 else 753 { 754 if (left.buffer == nil) 755 { 756 nodeNum = ((NodeDescPtr) node.buffer)->bLink; 757 if ( nodeNum > 0) 758 { 759 // BTree nodes are always grabbed in left to right order. 760 // Therefore release the current node before looking up the 761 // left node. 762 err = ReleaseNode(btreePtr, &node); 763 M_ExitOnError(err); 764 765 // Look up the left node 766 err = GetNode (btreePtr, nodeNum, 0, &left); 767 M_ExitOnError (err); 768 769 // Look up the current node again 770 err = GetRightSiblingNode (btreePtr, left.buffer, &node); 771 M_ExitOnError (err); 772 } else { 773 err = fsBTStartOfIterationErr; 774 goto ErrorExit; 775 } 776 } 777 // Before we stomp on "right", we'd better release it if needed 778 if (right.buffer != nil) { 779 err = ReleaseNode(btreePtr, &right); 780 M_ExitOnError(err); 781 } 782 right = node; 783 node = left; 784 left.buffer = nil; 785 index = ((NodeDescPtr) node.buffer)->numRecords -1; 786 } 787 } 788 else if (operation == kBTreeNextRecord) 789 { 790 if ((foundRecord != true) && 791 (((NodeDescPtr) node.buffer)->fLink == 0) && 792 (index == ((NodeDescPtr) node.buffer)->numRecords)) 793 { 794 err = fsBTEndOfIterationErr; 795 goto ErrorExit; 796 } 797 798 // we did not find the record but the index is already positioned correctly 799 if ((foundRecord == false) && (index != ((NodeDescPtr) node.buffer)->numRecords)) 800 goto CopyData; 801 802 // we found the record OR we have to look in the next node 803 if (index < ((NodeDescPtr) node.buffer)->numRecords -1) 804 { 805 ++index; 806 } 807 else 808 { 809 if (right.buffer == nil) 810 { 811 nodeNum = ((NodeDescPtr) node.buffer)->fLink; 812 if ( nodeNum > 0) 813 { 814 err = GetNode (btreePtr, nodeNum, 0, &right); 815 M_ExitOnError (err); 816 } else { 817 err = fsBTEndOfIterationErr; 818 goto ErrorExit; 819 } 820 } 821 // Before we stomp on "left", we'd better release it if needed 822 if (left.buffer != nil) { 823 err = ReleaseNode(btreePtr, &left); 824 M_ExitOnError(err); 825 } 826 left = node; 827 node = right; 828 right.buffer = nil; 829 index = 0; 830 } 831 } 832 else // operation == kBTreeCurrentRecord 833 { 834 // make sure we have something... <CS9> 835 if ((foundRecord != true) && 836 (index >= ((NodeDescPtr) node.buffer)->numRecords)) 837 { 838 err = fsBTEndOfIterationErr; 839 goto ErrorExit; 840 } 841 } 842 843 //////////////////// Copy Record And Update Iterator //////////////////////// 844 845CopyData: 846 847 // added check for errors <CS9> 848 err = GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len); 849 M_ExitOnError (err); 850 851 if (recordLen != nil) 852 *recordLen = len; 853 854 if (record != nil) 855 { 856 ByteCount recordSize; 857 858 recordSize = record->itemCount * record->itemSize; 859 860 if (len > recordSize) len = recordSize; 861 862 BlockMoveData (recordPtr, record->bufferAddress, len); 863 } 864 865 if (iterator != nil) // first & last do not require iterator 866 { 867 iterator->hint.writeCount = btreePtr->writeCount; 868 iterator->hint.nodeNum = nodeNum; 869 iterator->hint.index = index; 870 iterator->hint.reserved1 = 0; 871 iterator->hint.reserved2 = 0; 872 873 iterator->version = 0; 874 iterator->reserved = 0; 875 876 /* SER 877 * Check for infinite loops by making sure we do not 878 * process more leaf records, than can possibly be (or the BTree header 879 * is seriously damaged)....a brute force method. 880 */ 881 if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord)) 882 iterator->hitCount = 1; 883 else if (operation != kBTreeCurrentRecord) 884 iterator->hitCount += 1; 885 /* Always use the highest max, in case the grows while iterating */ 886 iterator->maxLeafRecs = max(btreePtr->leafRecords, iterator->maxLeafRecs); 887 888#if 0 889 if (iterator->hitCount > iterator->maxLeafRecs + kNumLeafRecSlack) 890 { 891 err = fsBTInvalidNodeErr; 892 printf ("hfs: BTIterateRecord() found invalid btree node on volume %s\n", FCBTOVCB(filePtr)->vcbVN); 893 hfs_mark_volume_inconsistent(FCBTOVCB(filePtr)); 894 goto ErrorExit; 895 } 896#endif 897 898 BlockMoveData ((Ptr)keyPtr, (Ptr)&iterator->key, CalcKeySize(btreePtr, keyPtr)); 899 } 900 901 902 ///////////////////////////// Release Nodes ///////////////////////////////// 903 904 err = ReleaseNode (btreePtr, &node); 905 M_ExitOnError (err); 906 907 if (left.buffer != nil) 908 { 909 err = ReleaseNode (btreePtr, &left); 910 M_ExitOnError (err); 911 } 912 913 if (right.buffer != nil) 914 { 915 err = ReleaseNode (btreePtr, &right); 916 M_ExitOnError (err); 917 } 918 919 return noErr; 920 921 /////////////////////// Error - Clean Up and Exit /////////////////////////// 922 923ErrorExit: 924 925 (void) ReleaseNode (btreePtr, &left); 926 (void) ReleaseNode (btreePtr, &node); 927 (void) ReleaseNode (btreePtr, &right); 928 929 if (recordLen != nil) 930 *recordLen = 0; 931 932 if (iterator != nil) 933 { 934 iterator->hint.writeCount = 0; 935 iterator->hint.nodeNum = 0; 936 iterator->hint.index = 0; 937 iterator->hint.reserved1 = 0; 938 iterator->hint.reserved2 = 0; 939 940 iterator->version = 0; 941 iterator->reserved = 0; 942 iterator->key.length16 = 0; 943 } 944 945 if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr ) 946 err = fsBTRecordNotFoundErr; 947 948 return err; 949} 950 951 952/*------------------------------------------------------------------------------- 953Routine: BTIterateRecords 954 955Function: Find a series of records 956 957Input: filePtr - b-tree file 958 operation - iteration operation (first,next,prev,last) 959 iterator - pointer to iterator indicating start position 960 callBackProc - pointer to routince to process a record 961 callBackState - pointer to state data (used by callBackProc) 962 963Output: iterator - iterator is updated to indicate new position 964 965Result: noErr - success 966 != noErr - failure 967-------------------------------------------------------------------------------*/ 968 969OSStatus 970BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator *iterator, 971 IterateCallBackProcPtr callBackProc, void * callBackState) 972{ 973 OSStatus err; 974 BTreeControlBlockPtr btreePtr; 975 BTreeKeyPtr keyPtr; 976 RecordPtr recordPtr; 977 u_int16_t len; 978 Boolean foundRecord; 979 u_int32_t nodeNum; 980 BlockDescriptor left, node, right; 981 u_int16_t index; 982 983 984 ////////////////////////// Priliminary Checks /////////////////////////////// 985 986 left.buffer = nil; 987 left.blockHeader = nil; 988 right.buffer = nil; 989 right.blockHeader = nil; 990 node.buffer = nil; 991 node.blockHeader = nil; 992 993 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 994 995 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true); 996 997 if ((operation != kBTreeFirstRecord) && 998 (operation != kBTreeNextRecord) && 999 (operation != kBTreeCurrentRecord) && 1000 (operation != kBTreePrevRecord) && 1001 (operation != kBTreeLastRecord)) 1002 { 1003 err = fsInvalidIterationMovmentErr; 1004 goto ErrorExit; 1005 } 1006 1007 /////////////////////// Find First or Last Record /////////////////////////// 1008 1009 if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord)) 1010 { 1011 if (operation == kBTreeFirstRecord) 1012 nodeNum = btreePtr->firstLeafNode; 1013 else 1014 nodeNum = btreePtr->lastLeafNode; 1015 1016 if (nodeNum == 0) 1017 { 1018 err = fsBTEmptyErr; 1019 goto ErrorExit; 1020 } 1021 1022 err = GetNode(btreePtr, nodeNum, 0, &node); 1023 M_ExitOnError(err); 1024 1025 if ( ((NodeDescPtr)node.buffer)->kind != kBTLeafNode || 1026 ((NodeDescPtr)node.buffer)->numRecords <= 0 ) 1027 { 1028 err = ReleaseNode(btreePtr, &node); 1029 M_ExitOnError(err); 1030 1031 err = fsBTInvalidNodeErr; 1032 printf ("hfs: BTIterateRecords() found invalid btree node on volume %s\n", FCBTOVCB(filePtr)->vcbVN); 1033 hfs_mark_volume_inconsistent(FCBTOVCB(filePtr)); 1034 goto ErrorExit; 1035 } 1036 1037 if (operation == kBTreeFirstRecord) 1038 index = 0; 1039 else 1040 index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1; 1041 1042 goto ProcessData; 1043 } 1044 1045 //////////////////////// Find Iterator Position ///////////////////////////// 1046 1047 // Not called for (operation == kBTreeFirstRecord || operation == kBTreeLastRecord) 1048 err = FindIteratorPosition(btreePtr, iterator, &left, &node, &right, 1049 &nodeNum, &index, &foundRecord); 1050 if (err == fsBTRecordNotFoundErr) 1051 err = 0; 1052 M_ExitOnError(err); 1053 1054 1055 ///////////////////// Find Next Or Previous Record ////////////////////////// 1056 1057 if (operation == kBTreePrevRecord) 1058 { 1059 if (index > 0) 1060 { 1061 --index; 1062 } 1063 else 1064 { 1065 if (left.buffer == nil) 1066 { 1067 nodeNum = ((NodeDescPtr) node.buffer)->bLink; 1068 if ( nodeNum > 0) 1069 { 1070 // BTree nodes are always grabbed in left to right order. 1071 // Therefore release the current node before looking up the 1072 // left node. 1073 err = ReleaseNode(btreePtr, &node); 1074 M_ExitOnError(err); 1075 1076 // Look up the left node 1077 err = GetNode (btreePtr, nodeNum, 0, &left); 1078 M_ExitOnError (err); 1079 1080 // Look up the current node again 1081 err = GetRightSiblingNode (btreePtr, left.buffer, &node); 1082 M_ExitOnError (err); 1083 } else { 1084 err = fsBTStartOfIterationErr; 1085 goto ErrorExit; 1086 } 1087 } 1088 // Before we stomp on "right", we'd better release it if needed 1089 if (right.buffer != nil) { 1090 err = ReleaseNode(btreePtr, &right); 1091 M_ExitOnError(err); 1092 } 1093 right = node; 1094 node = left; 1095 left.buffer = nil; 1096 index = ((NodeDescPtr) node.buffer)->numRecords -1; 1097 } 1098 } 1099 else if (operation == kBTreeNextRecord) 1100 { 1101 if ((foundRecord != true) && 1102 (((NodeDescPtr)node.buffer)->fLink == 0) && 1103 (index == ((NodeDescPtr)node.buffer)->numRecords)) 1104 { 1105 err = fsBTEndOfIterationErr; 1106 goto ErrorExit; 1107 } 1108 1109 // we did not find the record but the index is already positioned correctly 1110 if ((foundRecord == false) && (index != ((NodeDescPtr)node.buffer)->numRecords)) 1111 goto ProcessData; 1112 1113 // we found the record OR we have to look in the next node 1114 if (index < ((NodeDescPtr)node.buffer)->numRecords -1) 1115 { 1116 ++index; 1117 } 1118 else 1119 { 1120 if (right.buffer == nil) 1121 { 1122 nodeNum = ((NodeDescPtr)node.buffer)->fLink; 1123 if ( nodeNum > 0) 1124 { 1125 err = GetNode(btreePtr, nodeNum, 0, &right); 1126 M_ExitOnError(err); 1127 } else { 1128 err = fsBTEndOfIterationErr; 1129 goto ErrorExit; 1130 } 1131 } 1132 // Before we stomp on "left", we'd better release it if needed 1133 if (left.buffer != nil) { 1134 err = ReleaseNode(btreePtr, &left); 1135 M_ExitOnError(err); 1136 } 1137 left = node; 1138 node = right; 1139 right.buffer = nil; 1140 index = 0; 1141 } 1142 } 1143 else // operation == kBTreeCurrentRecord 1144 { 1145 // make sure we have something... <CS9> 1146 if ((foundRecord != true) && 1147 (index >= ((NodeDescPtr)node.buffer)->numRecords)) 1148 { 1149 err = fsBTEndOfIterationErr; 1150 goto ErrorExit; 1151 } 1152 } 1153 1154 //////////////////// Process Records Using Callback //////////////////////// 1155 1156ProcessData: 1157 err = GetRecordByIndex(btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len); 1158 if (err) { 1159 err = btBadNode; 1160 goto ErrorExit; 1161 } 1162 1163 while (err == 0) { 1164 if (callBackProc(keyPtr, recordPtr, callBackState) == 0) 1165 break; 1166 1167 if ((index+1) < ((NodeDescPtr)node.buffer)->numRecords) { 1168 ++index; 1169 } else { 1170 if (right.buffer == nil) 1171 { 1172 nodeNum = ((NodeDescPtr)node.buffer)->fLink; 1173 if ( nodeNum > 0) 1174 { 1175 err = GetNode(btreePtr, nodeNum, 0, &right); 1176 M_ExitOnError(err); 1177 } else { 1178 err = fsBTEndOfIterationErr; 1179 break; 1180 } 1181 } 1182 // Before we stomp on "left", we'd better release it if needed 1183 if (left.buffer != nil) { 1184 err = ReleaseNode(btreePtr, &left); 1185 M_ExitOnError(err); 1186 } 1187 left = node; 1188 node = right; 1189 right.buffer = nil; 1190 index = 0; 1191 } 1192 err = GetRecordByIndex(btreePtr, node.buffer, index, 1193 &keyPtr, &recordPtr, &len); 1194 if (err) { 1195 err = btBadNode; 1196 goto ErrorExit; 1197 } 1198 } 1199 1200 1201 ///////////////// Update Iterator to Last Item Processed ///////////////////// 1202 1203 1204 if (iterator != nil) // first & last have optional iterator 1205 { 1206 iterator->hint.writeCount = btreePtr->writeCount; 1207 iterator->hint.nodeNum = nodeNum; 1208 iterator->hint.index = index; 1209 iterator->version = 0; 1210 1211 BlockMoveData((Ptr)keyPtr, (Ptr)&iterator->key, CalcKeySize(btreePtr, keyPtr)); 1212 } 1213 M_ExitOnError(err); 1214 1215 1216 ///////////////////////////// Release Nodes ///////////////////////////////// 1217 1218 err = ReleaseNode(btreePtr, &node); 1219 M_ExitOnError(err); 1220 1221 if (left.buffer != nil) 1222 { 1223 err = ReleaseNode(btreePtr, &left); 1224 M_ExitOnError(err); 1225 } 1226 1227 if (right.buffer != nil) 1228 { 1229 err = ReleaseNode(btreePtr, &right); 1230 M_ExitOnError(err); 1231 } 1232 1233 return noErr; 1234 1235 /////////////////////// Error - Clean Up and Exit /////////////////////////// 1236 1237ErrorExit: 1238 1239 (void) ReleaseNode(btreePtr, &left); 1240 (void) ReleaseNode(btreePtr, &node); 1241 (void) ReleaseNode(btreePtr, &right); 1242 1243 if (iterator != nil) 1244 { 1245 iterator->hint.writeCount = 0; 1246 iterator->hint.nodeNum = 0; 1247 iterator->hint.index = 0; 1248 iterator->version = 0; 1249 iterator->key.length16 = 0; 1250 } 1251 1252 if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr ) 1253 err = fsBTRecordNotFoundErr; 1254 1255 return err; 1256} 1257 1258 1259//////////////////////////////// BTInsertRecord ///////////////////////////////// 1260 1261OSStatus BTInsertRecord (FCB *filePtr, 1262 BTreeIterator *iterator, 1263 FSBufferDescriptor *record, 1264 u_int16_t recordLen ) 1265{ 1266 OSStatus err; 1267 BTreeControlBlockPtr btreePtr; 1268 TreePathTable treePathTable; 1269 u_int32_t nodesNeeded; 1270 BlockDescriptor nodeRec; 1271 u_int32_t insertNodeNum; 1272 u_int16_t index; 1273 Boolean recordFit; 1274 1275 ////////////////////////// Priliminary Checks /////////////////////////////// 1276 1277 nodeRec.buffer = nil; // so we can call ReleaseNode 1278 nodeRec.blockHeader = nil; 1279 1280 err = CheckInsertParams (filePtr, iterator, record, recordLen); 1281 if (err != noErr) 1282 return err; 1283 1284 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 1285 1286 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false); 1287 1288 1289 ///////////////////////// Find Insert Position ////////////////////////////// 1290 1291 // always call SearchTree for Insert 1292 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index); 1293 1294 switch (err) // set/replace/insert decision point 1295 { 1296 case noErr: err = fsBTDuplicateRecordErr; 1297 goto ErrorExit; 1298 1299 case fsBTRecordNotFoundErr: break; 1300 1301 case fsBTEmptyErr: // if tree empty add 1st leaf node 1302 1303 if (btreePtr->freeNodes == 0) 1304 { 1305 err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1); 1306 M_ExitOnError (err); 1307 } 1308 1309 err = AllocateNode (btreePtr, &insertNodeNum); 1310 M_ExitOnError (err); 1311 1312 err = GetNewNode (btreePtr, insertNodeNum, &nodeRec); 1313 M_ExitOnError (err); 1314 1315 // XXXdbg 1316 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec); 1317 1318 ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode; 1319 ((NodeDescPtr)nodeRec.buffer)->height = 1; 1320 1321 recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0, 1322 &iterator->key, KeyLength(btreePtr, &iterator->key), 1323 record->bufferAddress, recordLen ); 1324 if (recordFit != true) 1325 { 1326 err = fsBTRecordTooLargeErr; 1327 goto ErrorExit; 1328 } 1329 1330 /* 1331 * Update the B-tree control block. Do this before 1332 * calling UpdateNode since it will compare the node's 1333 * height with treeDepth. 1334 */ 1335 btreePtr->treeDepth = 1; 1336 btreePtr->rootNode = insertNodeNum; 1337 btreePtr->firstLeafNode = insertNodeNum; 1338 btreePtr->lastLeafNode = insertNodeNum; 1339 1340 err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction); 1341 M_ExitOnError (err); 1342 1343 M_BTreeHeaderDirty (btreePtr); 1344 1345 goto Success; 1346 1347 default: goto ErrorExit; 1348 } 1349 1350 if (index > 0) 1351 { 1352 // XXXdbg 1353 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec); 1354 1355 recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index, 1356 &iterator->key, KeyLength(btreePtr, &iterator->key), 1357 record->bufferAddress, recordLen); 1358 if (recordFit == true) 1359 { 1360 err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction); 1361 M_ExitOnError (err); 1362 1363 goto Success; 1364 } 1365 } 1366 1367 /////////////////////// Extend File If Necessary //////////////////////////// 1368 1369 if ((btreePtr->treeDepth + 1UL) > btreePtr->freeNodes) 1370 { 1371 nodesNeeded = btreePtr->treeDepth + 1 + btreePtr->totalNodes - btreePtr->freeNodes; 1372 if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too! 1373 ++nodesNeeded; 1374 1375 err = ExtendBTree (btreePtr, nodesNeeded); 1376 M_ExitOnError (err); 1377 } 1378 1379 // no need to delete existing record 1380 1381 err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress, 1382 recordLen, &nodeRec, index, 1, kInsertRecord, &insertNodeNum); 1383 M_ExitOnError (err); 1384 1385 1386 //////////////////////////////// Success //////////////////////////////////// 1387 1388Success: 1389 ++btreePtr->writeCount; 1390 ++btreePtr->leafRecords; 1391 M_BTreeHeaderDirty (btreePtr); 1392 1393 // create hint 1394 iterator->hint.writeCount = btreePtr->writeCount; 1395 iterator->hint.nodeNum = insertNodeNum; 1396 iterator->hint.index = 0; // unused 1397 iterator->hint.reserved1 = 0; 1398 iterator->hint.reserved2 = 0; 1399 1400 return noErr; 1401 1402 1403 ////////////////////////////// Error Exit /////////////////////////////////// 1404 1405ErrorExit: 1406 1407 (void) ReleaseNode (btreePtr, &nodeRec); 1408 1409 iterator->hint.writeCount = 0; 1410 iterator->hint.nodeNum = 0; 1411 iterator->hint.index = 0; 1412 iterator->hint.reserved1 = 0; 1413 iterator->hint.reserved2 = 0; 1414 1415 if (err == fsBTEmptyErr) 1416 err = fsBTRecordNotFoundErr; 1417 1418 return err; 1419} 1420 1421 1422//////////////////////////////// BTReplaceRecord //////////////////////////////// 1423 1424OSStatus BTReplaceRecord (FCB *filePtr, 1425 BTreeIterator *iterator, 1426 FSBufferDescriptor *record, 1427 u_int16_t recordLen ) 1428{ 1429 OSStatus err; 1430 BTreeControlBlockPtr btreePtr; 1431 TreePathTable treePathTable; 1432 u_int32_t nodesNeeded; 1433 BlockDescriptor nodeRec; 1434 u_int32_t insertNodeNum; 1435 u_int16_t index; 1436 Boolean recordFit; 1437 Boolean validHint; 1438 1439 1440 ////////////////////////// Priliminary Checks /////////////////////////////// 1441 1442 nodeRec.buffer = nil; // so we can call ReleaseNode 1443 nodeRec.blockHeader = nil; 1444 1445 err = CheckInsertParams (filePtr, iterator, record, recordLen); 1446 if (err != noErr) 1447 return err; 1448 1449 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 1450 1451 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false); 1452 1453 ////////////////////////////// Take A Hint ////////////////////////////////// 1454 1455 err = IsItAHint (btreePtr, iterator, &validHint); 1456 M_ExitOnError (err); 1457 1458 if (validHint) 1459 { 1460 insertNodeNum = iterator->hint.nodeNum; 1461 1462 err = GetNode (btreePtr, insertNodeNum, kGetNodeHint, &nodeRec); 1463 if( err == noErr ) 1464 { 1465 // XXXdbg 1466 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec); 1467 1468 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit); 1469 M_ExitOnError (err); 1470 1471 if (recordFit) 1472 { 1473 err = UpdateNode (btreePtr, &nodeRec, 0, 0); 1474 M_ExitOnError (err); 1475 1476 ++btreePtr->numValidHints; 1477 1478 goto Success; 1479 } 1480 else 1481 { 1482 (void) BTInvalidateHint( iterator ); 1483 } 1484 1485 err = ReleaseNode (btreePtr, &nodeRec); 1486 M_ExitOnError (err); 1487 } 1488 else 1489 { 1490 (void) BTInvalidateHint( iterator ); 1491 } 1492 } 1493 1494 1495 ////////////////////////////// Get A Clue /////////////////////////////////// 1496 1497 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index); 1498 M_ExitOnError (err); // record must exit for Replace 1499 1500 // optimization - if simple replace will work then don't extend btree 1501 // �� if we tried this before, and failed because it wouldn't fit then we shouldn't try this again... 1502 1503 // XXXdbg 1504 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec); 1505 1506 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit); 1507 M_ExitOnError (err); 1508 1509 if (recordFit) 1510 { 1511 err = UpdateNode (btreePtr, &nodeRec, 0, 0); 1512 M_ExitOnError (err); 1513 1514 goto Success; 1515 } 1516 1517 1518 //////////////////////////// Make Some Room ///////////////////////////////// 1519 1520 if ((btreePtr->treeDepth + 1UL) > btreePtr->freeNodes) 1521 { 1522 nodesNeeded = btreePtr->treeDepth + 1 + btreePtr->totalNodes - btreePtr->freeNodes; 1523 if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too! 1524 ++nodesNeeded; 1525 1526 err = ExtendBTree (btreePtr, nodesNeeded); 1527 M_ExitOnError (err); 1528 } 1529 1530 // XXXdbg 1531 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec); 1532 1533 DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record 1534 1535 err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress, 1536 recordLen, &nodeRec, index, 1, kReplaceRecord, &insertNodeNum); 1537 M_ExitOnError (err); 1538 1539 ++btreePtr->writeCount; /* writeCount changes only if the tree structure changed */ 1540 1541Success: 1542 // create hint 1543 iterator->hint.writeCount = btreePtr->writeCount; 1544 iterator->hint.nodeNum = insertNodeNum; 1545 iterator->hint.index = 0; // unused 1546 iterator->hint.reserved1 = 0; 1547 iterator->hint.reserved2 = 0; 1548 1549 return noErr; 1550 1551 1552 ////////////////////////////// Error Exit /////////////////////////////////// 1553 1554ErrorExit: 1555 1556 (void) ReleaseNode (btreePtr, &nodeRec); 1557 1558 iterator->hint.writeCount = 0; 1559 iterator->hint.nodeNum = 0; 1560 iterator->hint.index = 0; 1561 iterator->hint.reserved1 = 0; 1562 iterator->hint.reserved2 = 0; 1563 1564 return err; 1565} 1566 1567 1568 1569//////////////////////////////// BTUpdateRecord //////////////////////////////// 1570 1571OSStatus 1572BTUpdateRecord(FCB *filePtr, BTreeIterator *iterator, 1573 IterateCallBackProcPtr callBackProc, void * callBackState) 1574{ 1575 OSStatus err; 1576 BTreeControlBlockPtr btreePtr; 1577 TreePathTable treePathTable; 1578 BlockDescriptor nodeRec; 1579 RecordPtr recordPtr; 1580 BTreeKeyPtr keyPtr; 1581 u_int32_t insertNodeNum; 1582 u_int16_t recordLen; 1583 u_int16_t index; 1584 Boolean validHint; 1585 1586 1587 ////////////////////////// Priliminary Checks /////////////////////////////// 1588 1589 nodeRec.buffer = nil; // so we can call ReleaseNode 1590 nodeRec.blockHeader = nil; 1591 1592 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 1593 1594 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true); 1595 1596 ////////////////////////////// Take A Hint ////////////////////////////////// 1597 1598 err = IsItAHint (btreePtr, iterator, &validHint); 1599 M_ExitOnError (err); 1600 1601 if (validHint) 1602 { 1603 insertNodeNum = iterator->hint.nodeNum; 1604 1605 err = GetNode (btreePtr, insertNodeNum, kGetNodeHint, &nodeRec); 1606 if (err == noErr) 1607 { 1608 if (((NodeDescPtr)nodeRec.buffer)->kind == kBTLeafNode && 1609 SearchNode (btreePtr, nodeRec.buffer, &iterator->key, &index)) 1610 { 1611 err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen); 1612 M_ExitOnError (err); 1613 1614 // XXXdbg 1615 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec); 1616 1617 err = callBackProc(keyPtr, recordPtr, callBackState); 1618 M_ExitOnError (err); 1619 1620 err = UpdateNode (btreePtr, &nodeRec, 0, 0); 1621 M_ExitOnError (err); 1622 1623 ++btreePtr->numValidHints; 1624 1625 goto Success; 1626 } 1627 else 1628 { 1629 (void) BTInvalidateHint( iterator ); 1630 } 1631 1632 err = ReleaseNode (btreePtr, &nodeRec); 1633 M_ExitOnError (err); 1634 } 1635 else 1636 { 1637 (void) BTInvalidateHint( iterator ); 1638 } 1639 } 1640 1641 ////////////////////////////// Get A Clue /////////////////////////////////// 1642 1643 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index); 1644 M_ExitOnError (err); 1645 1646 err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen); 1647 M_ExitOnError (err); 1648 1649 // XXXdbg 1650 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec); 1651 1652 err = callBackProc(keyPtr, recordPtr, callBackState); 1653 M_ExitOnError (err); 1654 1655 err = UpdateNode (btreePtr, &nodeRec, 0, 0); 1656 M_ExitOnError (err); 1657 1658Success: 1659 // create hint 1660 iterator->hint.writeCount = btreePtr->writeCount; 1661 iterator->hint.nodeNum = insertNodeNum; 1662 iterator->hint.index = 0; 1663 iterator->hint.reserved1 = 0; 1664 iterator->hint.reserved2 = 0; 1665 return noErr; 1666 1667 ////////////////////////////// Error Exit /////////////////////////////////// 1668 1669ErrorExit: 1670 1671 (void) ReleaseNode (btreePtr, &nodeRec); 1672 1673 iterator->hint.writeCount = 0; 1674 iterator->hint.nodeNum = 0; 1675 iterator->hint.index = 0; 1676 iterator->hint.reserved1 = 0; 1677 iterator->hint.reserved2 = 0; 1678 return err; 1679} 1680 1681 1682 1683//////////////////////////////// BTDeleteRecord ///////////////////////////////// 1684 1685OSStatus BTDeleteRecord (FCB *filePtr, 1686 BTreeIterator *iterator ) 1687{ 1688 OSStatus err; 1689 BTreeControlBlockPtr btreePtr; 1690 TreePathTable treePathTable; 1691 BlockDescriptor nodeRec; 1692 u_int32_t nodesNeeded; 1693 u_int32_t nodeNum; 1694 u_int16_t index; 1695 1696 1697 ////////////////////////// Priliminary Checks /////////////////////////////// 1698 1699 nodeRec.buffer = nil; // so we can call ReleaseNode 1700 nodeRec.blockHeader = nil; 1701 1702 M_ReturnErrorIf (filePtr == nil, paramErr); 1703 M_ReturnErrorIf (iterator == nil, paramErr); 1704 1705 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 1706 if (btreePtr == nil) 1707 { 1708 err = fsBTInvalidFileErr; 1709 goto ErrorExit; 1710 } 1711 1712 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false); 1713 1714 1715 /////////////////////////////// Find Key //////////////////////////////////// 1716 1717 // check hint for simple delete case (index > 0, numRecords > 2) 1718 1719 err = SearchTree (btreePtr, &iterator->key, treePathTable, &nodeNum, &nodeRec, &index); 1720 M_ExitOnError (err); // record must exit for Delete 1721 1722 1723 /////////////////////// Extend File If Necessary //////////////////////////// 1724 1725 if ((btreePtr->treeDepth + 1UL) > btreePtr->totalNodes) 1726 { 1727 nodesNeeded = btreePtr->treeDepth + 1 + btreePtr->totalNodes; 1728 if (nodesNeeded > CalcMapBits (btreePtr)) 1729 ++nodesNeeded; 1730 1731 err = ExtendBTree (btreePtr, nodesNeeded); 1732 M_ExitOnError (err); 1733 } 1734 1735 ///////////////////////////// Delete Record ///////////////////////////////// 1736 1737 err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1); 1738 M_ExitOnError (err); 1739 1740 ++btreePtr->writeCount; 1741 --btreePtr->leafRecords; 1742 M_BTreeHeaderDirty (btreePtr); 1743 1744 iterator->hint.nodeNum = 0; 1745 1746 return noErr; 1747 1748 ////////////////////////////// Error Exit /////////////////////////////////// 1749 1750ErrorExit: 1751 (void) ReleaseNode (btreePtr, &nodeRec); 1752 1753 return err; 1754} 1755 1756 1757 1758OSStatus BTGetInformation (FCB *filePtr, 1759 u_int16_t file_version, 1760 BTreeInfoRec *info ) 1761{ 1762#pragma unused (file_version) 1763 1764 BTreeControlBlockPtr btreePtr; 1765 1766 1767 M_ReturnErrorIf (filePtr == nil, paramErr); 1768 1769 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 1770 1771 /* 1772 * XXX SER 1773 * This should not require the whole tree to be locked, just maybe the BTreeControlBlockPtr 1774 * 1775 * REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true); 1776 */ 1777 1778 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr); 1779 M_ReturnErrorIf (info == nil, paramErr); 1780 1781 //�� check version? 1782 1783 info->nodeSize = btreePtr->nodeSize; 1784 info->maxKeyLength = btreePtr->maxKeyLength; 1785 info->treeDepth = btreePtr->treeDepth; 1786 info->numRecords = btreePtr->leafRecords; 1787 info->numNodes = btreePtr->totalNodes; 1788 info->numFreeNodes = btreePtr->freeNodes; 1789 info->lastfsync = btreePtr->lastfsync; 1790 info->keyCompareType = btreePtr->keyCompareType; 1791 return noErr; 1792} 1793 1794// XXXdbg 1795__private_extern__ 1796OSStatus 1797BTIsDirty(FCB *filePtr) 1798{ 1799 BTreeControlBlockPtr btreePtr; 1800 1801 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 1802 return TreeIsDirty(btreePtr); 1803} 1804 1805/*------------------------------------------------------------------------------- 1806Routine: BTFlushPath - Flush BTreeControlBlock to Header Node. 1807 1808Function: Brief_description_of_the_function_and_any_side_effects 1809 1810 1811Input: pathPtr - pointer to path control block for B*Tree file to flush 1812 1813Output: none 1814 1815Result: noErr - success 1816 != noErr - failure 1817-------------------------------------------------------------------------------*/ 1818 1819OSStatus BTFlushPath (FCB *filePtr) 1820{ 1821 OSStatus err; 1822 BTreeControlBlockPtr btreePtr; 1823 1824 1825 M_ReturnErrorIf (filePtr == nil, paramErr); 1826 1827 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 1828 1829 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr); 1830 1831 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true); 1832 1833 err = UpdateHeader (btreePtr, false); 1834 1835 return err; 1836} 1837 1838 1839/*------------------------------------------------------------------------------- 1840Routine: BTReload - Reload B-tree Header Data. 1841 1842Function: Reload B-tree header data from disk. This is called after fsck 1843 has made repairs to the root filesystem. The filesystem is 1844 mounted read-only when BTReload is caled. 1845 1846 1847Input: filePtr - the B*Tree file that needs its header updated 1848 1849Output: none 1850 1851Result: noErr - success 1852 != noErr - failure 1853-------------------------------------------------------------------------------*/ 1854 1855OSStatus 1856BTReloadData(FCB *filePtr) 1857{ 1858 OSStatus err; 1859 BTreeControlBlockPtr btreePtr; 1860 BlockDescriptor node; 1861 BTHeaderRec *header; 1862 1863 1864 node.buffer = nil; 1865 node.blockHeader = nil; 1866 1867 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 1868 if (btreePtr == nil) 1869 return (fsBTInvalidFileErr); 1870 1871 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false); 1872 1873 err = GetNode(btreePtr, kHeaderNodeNum, 0, &node); 1874 if (err != noErr) 1875 return (err); 1876 1877 header = (BTHeaderRec*)((char *)node.buffer + sizeof(BTNodeDescriptor)); 1878 if ((err = VerifyHeader (filePtr, header)) == 0) { 1879 btreePtr->treeDepth = header->treeDepth; 1880 btreePtr->rootNode = header->rootNode; 1881 btreePtr->leafRecords = header->leafRecords; 1882 btreePtr->firstLeafNode = header->firstLeafNode; 1883 btreePtr->lastLeafNode = header->lastLeafNode; 1884 btreePtr->maxKeyLength = header->maxKeyLength; 1885 btreePtr->totalNodes = header->totalNodes; 1886 btreePtr->freeNodes = header->freeNodes; 1887 btreePtr->btreeType = header->btreeType; 1888 1889 btreePtr->flags &= (~kBTHeaderDirty); 1890 } 1891 1892 (void) ReleaseNode(btreePtr, &node); 1893 1894 return err; 1895} 1896 1897 1898/*------------------------------------------------------------------------------- 1899Routine: BTInvalidateHint - Invalidates the hint within a BTreeInterator. 1900 1901Function: Invalidates the hint within a BTreeInterator. 1902 1903 1904Input: iterator - pointer to BTreeIterator 1905 1906Output: iterator - iterator with the hint.nodeNum cleared 1907 1908Result: noErr - success 1909 paramErr - iterator == nil 1910-------------------------------------------------------------------------------*/ 1911 1912 1913OSStatus BTInvalidateHint (BTreeIterator *iterator ) 1914{ 1915 if (iterator == nil) 1916 return paramErr; 1917 1918 iterator->hint.nodeNum = 0; 1919 1920 return noErr; 1921} 1922 1923 1924 1925 1926/*------------------------------------------------------------------------------- 1927Routine: BTGetLastSync 1928 1929Function: Returns the last time that this btree was flushed, does not include header. 1930 1931Input: filePtr - pointer file control block 1932 1933Output: lastfsync - time in seconds of last update 1934 1935Result: noErr - success 1936 paramErr - iterator == nil 1937-------------------------------------------------------------------------------*/ 1938 1939 1940OSStatus BTGetLastSync (FCB *filePtr, 1941 u_int32_t *lastsync) 1942{ 1943 BTreeControlBlockPtr btreePtr; 1944 1945 1946 M_ReturnErrorIf (filePtr == nil, paramErr); 1947 1948 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 1949 1950 /* Maybe instead of requiring a lock..an atomic set might be more appropriate */ 1951 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true); 1952 1953 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr); 1954 M_ReturnErrorIf (lastsync == nil, paramErr); 1955 1956 *lastsync = btreePtr->lastfsync; 1957 1958 return noErr; 1959} 1960 1961 1962 1963 1964/*------------------------------------------------------------------------------- 1965Routine: BTSetLastSync 1966 1967Function: Sets the last time that this btree was flushed, does not include header. 1968 1969 1970Input: fcb - pointer file control block 1971 1972Output: lastfsync - time in seconds of last update 1973 1974Result: noErr - success 1975 paramErr - iterator == nil 1976-------------------------------------------------------------------------------*/ 1977 1978 1979OSStatus BTSetLastSync (FCB *filePtr, 1980 u_int32_t lastsync) 1981{ 1982 BTreeControlBlockPtr btreePtr; 1983 1984 1985 M_ReturnErrorIf (filePtr == nil, paramErr); 1986 1987 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 1988 1989 /* Maybe instead of requiring a lock..an atomic set might be more appropriate */ 1990 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true); 1991 1992 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr); 1993 M_ReturnErrorIf (lastsync == 0, paramErr); 1994 1995 btreePtr->lastfsync = lastsync; 1996 1997 return noErr; 1998} 1999 2000__private_extern__ 2001OSStatus BTHasContiguousNodes (FCB *filePtr) 2002{ 2003 BTreeControlBlockPtr btreePtr; 2004 2005 2006 M_ReturnErrorIf (filePtr == nil, paramErr); 2007 2008 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 2009 2010 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true); 2011 2012 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr); 2013 2014 return NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize); 2015} 2016 2017 2018/*------------------------------------------------------------------------------- 2019Routine: BTGetUserData 2020 2021Function: Read the user data area of the b-tree header node. 2022 2023-------------------------------------------------------------------------------*/ 2024OSStatus 2025BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize) 2026{ 2027 BTreeControlBlockPtr btreePtr; 2028 BlockDescriptor node; 2029 char * offset; 2030 OSStatus err; 2031 2032 if (dataSize > kBTreeHeaderUserBytes) 2033 return (EINVAL); 2034 node.buffer = nil; 2035 node.blockHeader = nil; 2036 2037 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 2038 if (btreePtr == nil) 2039 return (fsBTInvalidFileErr); 2040 2041 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false); 2042 2043 err = GetNode(btreePtr, kHeaderNodeNum, 0, &node); 2044 if (err) 2045 return (err); 2046 2047 offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec); 2048 bcopy(offset, dataPtr, dataSize); 2049 2050 (void) ReleaseNode(btreePtr, &node); 2051 2052 return (0); 2053} 2054 2055 2056/*------------------------------------------------------------------------------- 2057Routine: BTSetUserData 2058 2059Function: Write the user data area of the b-tree header node. 2060-------------------------------------------------------------------------------*/ 2061OSStatus 2062BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize) 2063{ 2064 BTreeControlBlockPtr btreePtr; 2065 BlockDescriptor node; 2066 char * offset; 2067 OSStatus err; 2068 2069 if (dataSize > kBTreeHeaderUserBytes) 2070 return (EINVAL); 2071 node.buffer = nil; 2072 node.blockHeader = nil; 2073 2074 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 2075 if (btreePtr == nil) 2076 return (fsBTInvalidFileErr); 2077 2078 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false); 2079 2080 err = GetNode(btreePtr, kHeaderNodeNum, 0, &node); 2081 if (err) 2082 return (err); 2083 2084 ModifyBlockStart(btreePtr->fileRefNum, &node); 2085 2086 offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec); 2087 bcopy(dataPtr, offset, dataSize); 2088 2089 err = UpdateNode (btreePtr, &node, 0, 0); 2090 2091 return (err); 2092} 2093 2094