1/* 2 * Copyright (c) 2000, 2002, 2005-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: BTreeNodeOps.c 30 31 Contains: Single-node operations for the BTree Module. 32 33 Version: xxx put the technology version here xxx 34 35 Written by: Gordon Sheridan and Bill Bruffey 36 37 Copyright: � 1992-1999 by Apple Computer, Inc., all rights reserved. 38 39 File Ownership: 40 41 DRI: Don Brady 42 43 Other Contact: Mark Day 44 45 Technology: File Systems 46 47 Writers: 48 49 (msd) Mark Day 50 (djb) Don Brady 51 52 Change History (most recent first): 53 54 <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6. 55 <MOSXS> 4/113/99 djb Fix key size checking bug in CheckNode. 56 <MOSXS> 3/19/99 djb Added key size checking to CheckNode. 57 <MOSXS> 3/26/98 djb Added PrintNode for debugging. 58 <CS5> 9/4/97 djb Removed GetRightSiblingNode and GetLeftSiblingNode - they are 59 now macros. SearchNode is now in BTreeSearchNode.a. 60 <CS4> 8/22/97 djb Turn off debugging code in CheckKey. 61 <CS3> 7/24/97 djb Add summary traces for Get/Rel Node. Made GetRecordOffset into a 62 macro. Only call CheckNode if the node came from disk. 63 <CS2> 7/21/97 msd Make GetRecordByIndex check its record index input; it now 64 returns an OSStatus. 65 <CS1> 4/23/97 djb first checked in 66 67 <HFS3> 2/19/97 djb Changes to support big node cache. 68 <HFS2> 1/3/97 djb Added support for large keys. 69 <HFS1> 12/19/96 djb first checked in 70 71 72 History applicable to original Scarecrow Design: 73 74 <6> 10/25/96 ser Changing for new VFPI 75 <5> 9/17/96 dkh Add bounds checking to GetNode. Update GetNode to not assert 76 that CheckNode failed if the node is all zeroes. This can happen 77 if the hint case if the fetched node has been deallocated 78 <4> 3/7/96 dkh Change GetNewNode() to not use kGetEmptyBlock. Instead use 79 kGetBlock to fetch a block from the disk itself. ��� Why? 80 <3> 1/22/96 dkh Add #include Memory.h 81 <2> 1/10/96 msd Change 64-bit math to use real function names from Math64.i. 82 <1> 10/18/95 rst Moved from Scarecrow project. 83 84 <17> 7/18/95 mbb Change MoveData & ClearBytes to BlockMoveData & BlockZero. 85 <16> 1/31/95 prp GetBlockProc interface uses a 64 bit node number. 86 <15> 1/12/95 wjk Adopt Model FileSystem changes in D5. 87 <14> 9/30/94 prp Get in sync with D2 interface changes. 88 <13> 7/25/94 wjk Eliminate usage of BytePtr in favor of UInt8 *. 89 <12> 7/22/94 wjk Convert to the new set of header files. 90 <11> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and 91 NRCmds environments. 92 <10> 11/30/93 wjk Change some Ptr's to BytePtr's in function definitions so they 93 agree with their prototypes. 94 <9> 8/31/93 prp Use U64SetU instead of S64Set. 95 <8> 5/21/93 gs Maintain statistical counters on Get/Release node routines. 96 <7> 5/10/93 gs Change keySize parameter to keyLength for InsertKeyRecord 97 routine. Calculate number of bytes in key from keyLength to 98 account for length and pad bytes. Add GetChildNodeNum routine. 99 <6> 3/23/93 gs Add InsertKeyRecord routine. 100 <5> 2/8/93 gs Fix bug in SearchNode that caused "off by 1" error when final 101 compare was searchKey > trialKey. Add UpdateNode. 102 <4> 12/10/92 gs Change keyLength field of key to 'length'. 103 <3> 12/8/92 gs Incorporate suggestions from preliminary code review. 104 <2> 12/2/92 gs Implement routines. 105 <1> 11/15/92 gs Define routine interfaces. 106 107*/ 108 109#include "../headers/BTreesPrivate.h" 110 111 112 113///////////////////////// BTree Module Node Operations ////////////////////////// 114// 115// GetNode - Call FS Agent to get node 116// GetNewNode - Call FS Agent to get a new node 117// ReleaseNode - Call FS Agent to release node obtained by GetNode. 118// UpdateNode - Mark a node as dirty and call FS Agent to release it. 119// 120// ClearNode - Clear a node to all zeroes. 121// 122// InsertRecord - Inserts a record into a BTree node. 123// InsertKeyRecord - Inserts a key and record pair into a BTree node. 124// DeleteRecord - Deletes a record from a BTree node. 125// 126// SearchNode - Return index for record that matches key. 127// LocateRecord - Return pointer to key and data, and size of data. 128// 129// GetNodeDataSize - Return the amount of space used for data in the node. 130// GetNodeFreeSize - Return the amount of free space in the node. 131// 132// GetRecordOffset - Return the offset for record "index". 133// GetRecordAddress - Return address of record "index". 134// GetOffsetAddress - Return address of offset for record "index". 135// 136// InsertOffset - Inserts a new offset into a node. 137// DeleteOffset - Deletes an offset from a node. 138// 139///////////////////////////////////////////////////////////////////////////////// 140 141 142 143////////////////////// Routines Internal To BTreeNodeOps.c ////////////////////// 144 145u_int16_t GetRecordOffset (BTreeControlBlockPtr btree, 146 NodeDescPtr node, 147 u_int16_t index ); 148 149u_int16_t *GetOffsetAddress (BTreeControlBlockPtr btreePtr, 150 NodeDescPtr node, 151 u_int16_t index ); 152 153void InsertOffset (BTreeControlBlockPtr btreePtr, 154 NodeDescPtr node, 155 u_int16_t index, 156 u_int16_t delta ); 157 158void DeleteOffset (BTreeControlBlockPtr btreePtr, 159 NodeDescPtr node, 160 u_int16_t index ); 161 162 163///////////////////////////////////////////////////////////////////////////////// 164 165#define GetRecordOffset(btreePtr,node,index) (*(short *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)) 166 167#if HFS_DIAGNOSTIC 168 #include <sys/systm.h> 169 #define PRINTIT kprintf 170static void PrintNode(const NodeDescPtr node, u_int16_t nodeSize, u_int32_t nodeNumber); 171#endif /* HFS_DIAGNOSTIC */ 172 173 174 175 176/*------------------------------------------------------------------------------- 177 178Routine: GetNode - Call FS Agent to get node 179 180Function: Gets an existing BTree node from FS Agent and verifies it. 181 182Input: btreePtr - pointer to BTree control block 183 nodeNum - number of node to request 184 185Output: nodePtr - pointer to beginning of node (nil if error) 186 187Result: 188 noErr - success 189 != noErr - failure 190-------------------------------------------------------------------------------*/ 191 192OSStatus GetNode (BTreeControlBlockPtr btreePtr, 193 u_int32_t nodeNum, 194 u_int32_t flags, 195 NodeRec *nodePtr ) 196{ 197 OSStatus err; 198 GetBlockProcPtr getNodeProc; 199 u_int32_t options; 200 201 202 // is nodeNum within proper range? 203 if( nodeNum >= btreePtr->totalNodes ) 204 { 205 Panic("GetNode:nodeNum >= totalNodes"); 206 err = fsBTInvalidNodeErr; 207 goto ErrorExit; 208 } 209 210 nodePtr->blockSize = btreePtr->nodeSize; // indicate the size of a node 211 212 options = kGetBlock; 213 if ( flags & kGetNodeHint ) 214 { 215 options |= kGetBlockHint; 216 } 217 218 getNodeProc = btreePtr->getBlockProc; 219 err = getNodeProc (btreePtr->fileRefNum, 220 nodeNum, 221 options, 222 nodePtr ); 223 224 if (err != noErr) 225 { 226 Panic ("GetNode: getNodeProc returned error."); 227 goto ErrorExit; 228 } 229 ++btreePtr->numGetNodes; 230 231 return noErr; 232 233ErrorExit: 234 nodePtr->buffer = nil; 235 nodePtr->blockHeader = nil; 236 237 return err; 238} 239 240 241 242/*------------------------------------------------------------------------------- 243 244Routine: GetNewNode - Call FS Agent to get a new node 245 246Function: Gets a new BTree node from FS Agent and initializes it to an empty 247 state. 248 249Input: btreePtr - pointer to BTree control block 250 nodeNum - number of node to request 251 252Output: returnNodePtr - pointer to beginning of node (nil if error) 253 254Result: noErr - success 255 != noErr - failure 256-------------------------------------------------------------------------------*/ 257 258OSStatus GetNewNode (BTreeControlBlockPtr btreePtr, 259 u_int32_t nodeNum, 260 NodeRec *returnNodePtr ) 261{ 262 OSStatus err; 263 NodeDescPtr node; 264 void *pos; 265 GetBlockProcPtr getNodeProc; 266 267 268 //////////////////////// get buffer for new node //////////////////////////// 269 270 returnNodePtr->blockSize = btreePtr->nodeSize; // indicate the size of a node 271 272 getNodeProc = btreePtr->getBlockProc; 273 err = getNodeProc (btreePtr->fileRefNum, 274 nodeNum, 275 kGetBlock+kGetEmptyBlock, 276 returnNodePtr ); 277 278 if (err != noErr) 279 { 280 Panic ("GetNewNode: getNodeProc returned error."); 281 // returnNodePtr->buffer = nil; 282 return err; 283 } 284 ++btreePtr->numGetNewNodes; 285 286 287 ////////////////////////// initialize the node ////////////////////////////// 288 289 node = returnNodePtr->buffer; 290 291 ClearNode (btreePtr, node); // clear the node 292 293 pos = (char *)node + btreePtr->nodeSize - 2; // find address of last offset 294 *(u_int16_t *)pos = sizeof (BTNodeDescriptor); // set offset to beginning of free space 295 296 297 return noErr; 298} 299 300 301 302/*------------------------------------------------------------------------------- 303 304Routine: ReleaseNode - Call FS Agent to release node obtained by GetNode. 305 306Function: Informs the FS Agent that a BTree node may be released. 307 308Input: btreePtr - pointer to BTree control block 309 nodeNum - number of node to release 310 311Result: noErr - success 312 != noErr - failure 313-------------------------------------------------------------------------------*/ 314 315OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr, 316 NodePtr nodePtr ) 317{ 318 OSStatus err; 319 ReleaseBlockProcPtr releaseNodeProc; 320 321 322 err = noErr; 323 324 if (nodePtr->buffer != nil) 325 { 326 releaseNodeProc = btreePtr->releaseBlockProc; 327 err = releaseNodeProc (btreePtr->fileRefNum, 328 nodePtr, 329 kReleaseBlock ); 330 PanicIf (err, "ReleaseNode: releaseNodeProc returned error."); 331 ++btreePtr->numReleaseNodes; 332 } 333 334 nodePtr->buffer = nil; 335 nodePtr->blockHeader = nil; 336 337 return err; 338} 339 340 341 342 343/*------------------------------------------------------------------------------- 344 345Routine: TrashNode - Call FS Agent to release node obtained by GetNode, and 346 not store it...mark it as bad. 347 348Function: Informs the FS Agent that a BTree node may be released and thrown away. 349 350Input: btreePtr - pointer to BTree control block 351 nodeNum - number of node to release 352 353Result: noErr - success 354 != noErr - failure 355-------------------------------------------------------------------------------*/ 356 357OSStatus TrashNode (BTreeControlBlockPtr btreePtr, 358 NodePtr nodePtr ) 359{ 360 OSStatus err; 361 ReleaseBlockProcPtr releaseNodeProc; 362 363 364 err = noErr; 365 366 if (nodePtr->buffer != nil) 367 { 368 releaseNodeProc = btreePtr->releaseBlockProc; 369 err = releaseNodeProc (btreePtr->fileRefNum, 370 nodePtr, 371 kReleaseBlock | kTrashBlock ); 372 PanicIf (err, "TrashNode: releaseNodeProc returned error."); 373 ++btreePtr->numReleaseNodes; 374 } 375 376 nodePtr->buffer = nil; 377 nodePtr->blockHeader = nil; 378 379 return err; 380} 381 382 383 384/*------------------------------------------------------------------------------- 385 386Routine: UpdateNode - Mark a node as dirty and call FS Agent to release it. 387 388Function: Marks a BTree node dirty and informs the FS Agent that it may be released. 389 390Input: btreePtr - pointer to BTree control block 391 nodeNum - number of node to release 392 transactionID - ID of transaction this node update is a part of 393 flags - special flags to pass to ReleaseNodeProc 394 395Result: noErr - success 396 != noErr - failure 397-------------------------------------------------------------------------------*/ 398 399OSStatus UpdateNode (BTreeControlBlockPtr btreePtr, 400 NodePtr nodePtr, 401 u_int32_t transactionID, 402 u_int32_t flags ) 403{ 404#pragma unused(transactionID) 405 406 OSStatus err; 407 ReleaseBlockProcPtr releaseNodeProc; 408 409 410 err = noErr; 411 412 if (nodePtr->buffer != nil) // Why call UpdateNode if nil ?!? 413 { 414 releaseNodeProc = btreePtr->releaseBlockProc; 415 err = releaseNodeProc (btreePtr->fileRefNum, 416 nodePtr, 417 flags | kMarkBlockDirty ); 418 ++btreePtr->numUpdateNodes; 419 M_ExitOnError (err); 420 } 421 422 nodePtr->buffer = nil; 423 nodePtr->blockHeader = nil; 424 425 return noErr; 426 427ErrorExit: 428 429 return err; 430} 431 432 433 434#if HFS_DIAGNOSTIC 435static void PrintNode(const NodeDescPtr node, u_int16_t nodeSize, u_int32_t nodeNumber) 436{ 437 struct row { 438 u_int16_t word[8]; 439 }; 440 struct row *offset; 441 u_int16_t rows; 442 u_int32_t *lp; 443 444 PRINTIT("Dump of B-tree node #%ld ($%08lX)\n", nodeNumber, nodeNumber); 445 446 rows = nodeSize/16; 447 lp = (u_int32_t*) node; 448 offset = 0; 449 450 while (rows-- > 0) 451 PRINTIT("%04X: %08lX %08lX %08lX %08lX\n", (u_int)offset++, *lp++, *lp++, *lp++, *lp++); 452} 453#endif 454 455 456/*------------------------------------------------------------------------------- 457 458Routine: ClearNode - Clear a node to all zeroes. 459 460Function: Writes zeroes from beginning of node for nodeSize bytes. 461 462Input: btreePtr - pointer to BTree control block 463 node - pointer to node to clear 464 465Result: none 466-------------------------------------------------------------------------------*/ 467 468void ClearNode (BTreeControlBlockPtr btreePtr, NodeDescPtr node ) 469{ 470 ClearMemory( node, btreePtr->nodeSize ); 471} 472 473/*------------------------------------------------------------------------------- 474 475Routine: InsertRecord - Inserts a record into a BTree node. 476 477Function: 478 479Note: Record size must be even! 480 481Input: btreePtr - pointer to BTree control block 482 node - pointer to node to insert the record 483 index - position record is to be inserted 484 recPtr - pointer to record to insert 485 486Result: noErr - success 487 fsBTFullErr - record larger than remaining free space. 488-------------------------------------------------------------------------------*/ 489 490Boolean InsertRecord (BTreeControlBlockPtr btreePtr, 491 NodeDescPtr node, 492 u_int16_t index, 493 RecordPtr recPtr, 494 u_int16_t recSize ) 495{ 496 u_int16_t freeSpace; 497 u_int16_t indexOffset; 498 u_int16_t freeOffset; 499 u_int16_t bytesToMove; 500 void *src; 501 void *dst; 502 503 //// will new record fit in node? 504 505 freeSpace = GetNodeFreeSize (btreePtr, node); 506 //�� we could get freeOffset & calc freeSpace 507 if ( freeSpace < recSize + 2) 508 { 509 return false; 510 } 511 512 513 //// make hole for new record 514 515 indexOffset = GetRecordOffset (btreePtr, node, index); 516 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); 517 518 src = ((Ptr) node) + indexOffset; 519 dst = ((Ptr) src) + recSize; 520 bytesToMove = freeOffset - indexOffset; 521 if (bytesToMove) 522 MoveRecordsRight (src, dst, bytesToMove); 523 524 525 //// adjust offsets for moved records 526 527 InsertOffset (btreePtr, node, index, recSize); 528 529 530 //// move in the new record 531 532 dst = ((Ptr) node) + indexOffset; 533 MoveRecordsLeft (recPtr, dst, recSize); 534 535 return true; 536} 537 538 539 540/*------------------------------------------------------------------------------- 541 542Routine: InsertKeyRecord - Inserts a record into a BTree node. 543 544Function: 545 546Note: Record size must be even! 547 548Input: btreePtr - pointer to BTree control block 549 node - pointer to node to insert the record 550 index - position record is to be inserted 551 keyPtr - pointer to key for record to insert 552 keyLength - length of key (or maxKeyLength) 553 recPtr - pointer to record to insert 554 recSize - number of bytes to copy for record 555 556Result: noErr - success 557 fsBTFullErr - record larger than remaining free space. 558-------------------------------------------------------------------------------*/ 559 560Boolean InsertKeyRecord (BTreeControlBlockPtr btreePtr, 561 NodeDescPtr node, 562 u_int16_t index, 563 KeyPtr keyPtr, 564 u_int16_t keyLength, 565 RecordPtr recPtr, 566 u_int16_t recSize ) 567{ 568 u_int16_t freeSpace; 569 u_int16_t indexOffset; 570 u_int16_t freeOffset; 571 u_int16_t bytesToMove; 572 u_int8_t * src; 573 u_int8_t * dst; 574 u_int16_t keySize; 575 u_int16_t rawKeyLength; 576 u_int16_t sizeOfLength; 577 578 //// calculate actual key size 579 580 if ( btreePtr->attributes & kBTBigKeysMask ) 581 keySize = keyLength + sizeof(u_int16_t); 582 else 583 keySize = keyLength + sizeof(u_int8_t); 584 585 if ( M_IsOdd (keySize) ) 586 ++keySize; // add pad byte 587 588 589 //// will new record fit in node? 590 591 freeSpace = GetNodeFreeSize (btreePtr, node); 592 //�� we could get freeOffset & calc freeSpace 593 if ( freeSpace < keySize + recSize + 2) 594 { 595 return false; 596 } 597 598 599 //// make hole for new record 600 601 indexOffset = GetRecordOffset (btreePtr, node, index); 602 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); 603 604 src = ((u_int8_t *) node) + indexOffset; 605 dst = ((u_int8_t *) src) + keySize + recSize; 606 bytesToMove = freeOffset - indexOffset; 607 if (bytesToMove) 608 MoveRecordsRight (src, dst, bytesToMove); 609 610 611 //// adjust offsets for moved records 612 613 InsertOffset (btreePtr, node, index, keySize + recSize); 614 615 616 //// copy record key 617 618 dst = ((u_int8_t *) node) + indexOffset; 619 620 if ( btreePtr->attributes & kBTBigKeysMask ) 621 { 622 *((u_int16_t *)dst) = keyLength; // use keyLength rather than key.length 623 dst = (u_int8_t *) (((u_int16_t *)dst) + 1); 624 rawKeyLength = keyPtr->length16; 625 sizeOfLength = 2; 626 } 627 else 628 { 629 *dst++ = keyLength; // use keyLength rather than key.length 630 rawKeyLength = keyPtr->length8; 631 sizeOfLength = 1; 632 } 633 634 MoveRecordsLeft ( ((u_int8_t *) keyPtr) + sizeOfLength, dst, rawKeyLength); // copy key 635 636 // any pad bytes? 637 bytesToMove = keySize - rawKeyLength; 638 if (bytesToMove) 639 ClearMemory (dst + rawKeyLength, bytesToMove); // clear pad bytes in index key 640 641 642 //// copy record data 643 644 dst = ((u_int8_t *) node) + indexOffset + keySize; 645 MoveRecordsLeft (recPtr, dst, recSize); 646 647 return true; 648} 649 650 651 652/*------------------------------------------------------------------------------- 653 654Routine: DeleteRecord - Deletes a record from a BTree node. 655 656Function: 657 658Input: btreePtr - pointer to BTree control block 659 node - pointer to node to insert the record 660 index - position record is to be inserted 661 662Result: none 663-------------------------------------------------------------------------------*/ 664 665void DeleteRecord (BTreeControlBlockPtr btreePtr, 666 NodeDescPtr node, 667 u_int16_t index ) 668{ 669 int16_t indexOffset; 670 int16_t nextOffset; 671 int16_t freeOffset; 672 int16_t bytesToMove; 673 void *src; 674 void *dst; 675 676 //// compress records 677 indexOffset = GetRecordOffset (btreePtr, node, index); 678 nextOffset = GetRecordOffset (btreePtr, node, index + 1); 679 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); 680 681 src = ((Ptr) node) + nextOffset; 682 dst = ((Ptr) node) + indexOffset; 683 bytesToMove = freeOffset - nextOffset; 684 if (bytesToMove) 685 MoveRecordsLeft (src, dst, bytesToMove); 686 687 //// Adjust the offsets 688 DeleteOffset (btreePtr, node, index); 689 690 /* clear out new free space */ 691 bytesToMove = nextOffset - indexOffset; 692 ClearMemory(GetRecordAddress(btreePtr, node, node->numRecords), bytesToMove); 693 694} 695 696 697 698/*------------------------------------------------------------------------------- 699 700Routine: SearchNode - Return index for record that matches key. 701 702Function: Returns the record index for the record that matches the search key. 703 If no record was found that matches the search key, the "insert index" 704 of where the record should go is returned instead. 705 706Algorithm: A binary search algorithm is used to find the specified key. 707 708Input: btreePtr - pointer to BTree control block 709 node - pointer to node that contains the record 710 searchKey - pointer to the key to match 711 712Output: index - pointer to beginning of key for record 713 714Result: true - success (index = record index) 715 false - key did not match anything in node (index = insert index) 716-------------------------------------------------------------------------------*/ 717Boolean 718SearchNode( BTreeControlBlockPtr btreePtr, 719 NodeDescPtr node, 720 KeyPtr searchKey, 721 u_int16_t *returnIndex ) 722{ 723 int32_t lowerBound; 724 int32_t upperBound; 725 int32_t index; 726 int32_t result; 727 KeyPtr trialKey; 728 u_int16_t *offset; 729 KeyCompareProcPtr compareProc = btreePtr->keyCompareProc; 730 731 lowerBound = 0; 732 upperBound = node->numRecords - 1; 733 offset = (u_int16_t *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - kOffsetSize); 734 735 while (lowerBound <= upperBound) { 736 index = (lowerBound + upperBound) >> 1; 737 738 trialKey = (KeyPtr) ((u_int8_t *)node + *(offset - index)); 739 740 result = compareProc(searchKey, trialKey); 741 742 if (result < 0) { 743 upperBound = index - 1; /* search < trial */ 744 } else if (result > 0) { 745 lowerBound = index + 1; /* search > trial */ 746 } else { 747 *returnIndex = index; /* search == trial */ 748 return true; 749 } 750 } 751 752 *returnIndex = lowerBound; /* lowerBound is insert index */ 753 return false; 754} 755 756 757/*------------------------------------------------------------------------------- 758 759Routine: GetRecordByIndex - Return pointer to key and data, and size of data. 760 761Function: Returns a pointer to beginning of key for record, a pointer to the 762 beginning of the data for the record, and the size of the record data 763 (does not include the size of the key). 764 765Input: btreePtr - pointer to BTree control block 766 node - pointer to node that contains the record 767 index - index of record to get 768 769Output: keyPtr - pointer to beginning of key for record 770 dataPtr - pointer to beginning of data for record 771 dataSize - size of the data portion of the record 772 773Result: none 774-------------------------------------------------------------------------------*/ 775 776OSStatus GetRecordByIndex (BTreeControlBlockPtr btreePtr, 777 NodeDescPtr node, 778 u_int16_t index, 779 KeyPtr *keyPtr, 780 u_int8_t * *dataPtr, 781 u_int16_t *dataSize ) 782{ 783 u_int16_t offset; 784 u_int16_t nextOffset; 785 u_int16_t keySize; 786 787 // 788 // Make sure index is valid (in range 0..numRecords-1) 789 // 790 if (index >= node->numRecords) 791 return fsBTRecordNotFoundErr; 792 793 //// find keyPtr 794 offset = GetRecordOffset (btreePtr, node, index); 795 *keyPtr = (KeyPtr) ((Ptr)node + offset); 796 797 //// find dataPtr 798 keySize = CalcKeySize(btreePtr, *keyPtr); 799 if ( M_IsOdd (keySize) ) 800 ++keySize; // add pad byte 801 802 offset += keySize; // add the key length to find data offset 803 *dataPtr = (u_int8_t *) node + offset; 804 805 //// find dataSize 806 nextOffset = GetRecordOffset (btreePtr, node, index + 1); 807 *dataSize = nextOffset - offset; 808 809 return noErr; 810} 811 812 813 814/*------------------------------------------------------------------------------- 815 816Routine: GetNodeDataSize - Return the amount of space used for data in the node. 817 818Function: Gets the size of the data currently contained in a node, excluding 819 the node header. (record data + offset overhead) 820 821Input: btreePtr - pointer to BTree control block 822 node - pointer to node that contains the record 823 824Result: - number of bytes used for data and offsets in the node. 825-------------------------------------------------------------------------------*/ 826 827u_int16_t GetNodeDataSize (BTreeControlBlockPtr btreePtr, NodeDescPtr node ) 828{ 829 u_int16_t freeOffset; 830 831 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); 832 833 return freeOffset + (node->numRecords << 1) - sizeof (BTNodeDescriptor); 834} 835 836 837 838/*------------------------------------------------------------------------------- 839 840Routine: GetNodeFreeSize - Return the amount of free space in the node. 841 842Function: 843 844Input: btreePtr - pointer to BTree control block 845 node - pointer to node that contains the record 846 847Result: - number of bytes of free space in the node. 848-------------------------------------------------------------------------------*/ 849 850u_int16_t GetNodeFreeSize (BTreeControlBlockPtr btreePtr, NodeDescPtr node ) 851{ 852 u_int16_t freeOffset; 853 854 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); //�� inline? 855 856 return btreePtr->nodeSize - freeOffset - (node->numRecords << 1) - kOffsetSize; 857} 858 859 860 861/*------------------------------------------------------------------------------- 862 863Routine: GetRecordOffset - Return the offset for record "index". 864 865Function: 866 867Input: btreePtr - pointer to BTree control block 868 node - pointer to node that contains the record 869 index - record to obtain offset for 870 871Result: - offset (in bytes) from beginning of node of record specified by index 872-------------------------------------------------------------------------------*/ 873// make this a macro (for inlining) 874#if 0 875u_int16_t GetRecordOffset (BTreeControlBlockPtr btreePtr, 876 NodeDescPtr node, 877 u_int16_t index ) 878{ 879 void *pos; 880 881 882 pos = (u_int8_t *)node + btreePtr->nodeSize - (index << 1) - kOffsetSize; 883 884 return *(short *)pos; 885} 886#endif 887 888 889 890/*------------------------------------------------------------------------------- 891 892Routine: GetRecordAddress - Return address of record "index". 893 894Function: 895 896Input: btreePtr - pointer to BTree control block 897 node - pointer to node that contains the record 898 index - record to obtain offset address for 899 900Result: - pointer to record "index". 901-------------------------------------------------------------------------------*/ 902// make this a macro (for inlining) 903#if 0 904u_int8_t * GetRecordAddress (BTreeControlBlockPtr btreePtr, 905 NodeDescPtr node, 906 u_int16_t index ) 907{ 908 u_int8_t * pos; 909 910 pos = (u_int8_t *)node + GetRecordOffset (btreePtr, node, index); 911 912 return pos; 913} 914#endif 915 916 917 918/*------------------------------------------------------------------------------- 919 920Routine: GetRecordSize - Return size of record "index". 921 922Function: 923 924Note: This does not work on the FreeSpace index! 925 926Input: btreePtr - pointer to BTree control block 927 node - pointer to node that contains the record 928 index - record to obtain record size for 929 930Result: - size of record "index". 931-------------------------------------------------------------------------------*/ 932 933u_int16_t GetRecordSize (BTreeControlBlockPtr btreePtr, 934 NodeDescPtr node, 935 u_int16_t index ) 936{ 937 u_int16_t *pos; 938 939 pos = (u_int16_t *) ((Ptr)node + btreePtr->nodeSize - (index << 1) - kOffsetSize); 940 941 return *(pos-1) - *pos; 942} 943 944 945 946/*------------------------------------------------------------------------------- 947Routine: GetOffsetAddress - Return address of offset for record "index". 948 949Function: 950 951Input: btreePtr - pointer to BTree control block 952 node - pointer to node that contains the record 953 index - record to obtain offset address for 954 955Result: - pointer to offset for record "index". 956-------------------------------------------------------------------------------*/ 957 958u_int16_t *GetOffsetAddress (BTreeControlBlockPtr btreePtr, 959 NodeDescPtr node, 960 u_int16_t index ) 961{ 962 void *pos; 963 964 pos = (Ptr)node + btreePtr->nodeSize - (index << 1) -2; 965 966 return (u_int16_t *)pos; 967} 968 969 970 971/*------------------------------------------------------------------------------- 972Routine: GetChildNodeNum - Return child node number from index record "index". 973 974Function: Returns the first u_int32_t stored after the key for record "index". 975 976Assumes: The node is an Index Node. 977 The key.length stored at record "index" is ODD. //�� change for variable length index keys 978 979Input: btreePtr - pointer to BTree control block 980 node - pointer to node that contains the record 981 index - record to obtain child node number from 982 983Result: - child node number from record "index". 984-------------------------------------------------------------------------------*/ 985 986u_int32_t GetChildNodeNum (BTreeControlBlockPtr btreePtr, 987 NodeDescPtr nodePtr, 988 u_int16_t index ) 989{ 990 u_int8_t * pos; 991 992 pos = GetRecordAddress (btreePtr, nodePtr, index); 993 pos += CalcKeySize(btreePtr, (BTreeKey *) pos); // key.length + size of length field 994 995 return *(u_int32_t *)pos; 996} 997 998 999 1000/*------------------------------------------------------------------------------- 1001Routine: InsertOffset - Add an offset and adjust existing offsets by delta. 1002 1003Function: Add an offset at 'index' by shifting 'index+1' through the last offset 1004 and adjusting them by 'delta', the size of the record to be inserted. 1005 The number of records contained in the node is also incremented. 1006 1007Input: btreePtr - pointer to BTree control block 1008 node - pointer to node 1009 index - index at which to insert record 1010 delta - size of record to be inserted 1011 1012Result: none 1013-------------------------------------------------------------------------------*/ 1014 1015void InsertOffset (BTreeControlBlockPtr btreePtr, 1016 NodeDescPtr node, 1017 u_int16_t index, 1018 u_int16_t delta ) 1019{ 1020 u_int16_t *src, *dst; 1021 u_int16_t numOffsets; 1022 1023 src = GetOffsetAddress (btreePtr, node, node->numRecords); // point to free offset 1024 dst = src - 1; // point to new offset 1025 numOffsets = node->numRecords++ - index; // subtract index & postincrement 1026 1027 do { 1028 *dst++ = *src++ + delta; // to tricky? 1029 } while (numOffsets--); 1030} 1031 1032 1033 1034/*------------------------------------------------------------------------------- 1035 1036Routine: DeleteOffset - Delete an offset. 1037 1038Function: Delete the offset at 'index' by shifting 'index+1' through the last offset 1039 and adjusting them by the size of the record 'index'. 1040 The number of records contained in the node is also decremented. 1041 1042Input: btreePtr - pointer to BTree control block 1043 node - pointer to node 1044 index - index at which to delete record 1045 1046Result: none 1047-------------------------------------------------------------------------------*/ 1048 1049void DeleteOffset (BTreeControlBlockPtr btreePtr, 1050 NodeDescPtr node, 1051 u_int16_t index ) 1052{ 1053 u_int16_t *src, *dst; 1054 u_int16_t numOffsets; 1055 u_int16_t delta; 1056 1057 dst = GetOffsetAddress (btreePtr, node, index); 1058 src = dst - 1; 1059 delta = *src - *dst; 1060 numOffsets = --node->numRecords - index; // predecrement numRecords & subtract index 1061 1062 while (numOffsets--) 1063 { 1064 *--dst = *--src - delta; // work our way left 1065 } 1066} 1067 1068 1069