1/* 2 * Copyright (c) 1999, 2005-2006 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23/* 24 File: BTreeNodeOps.c 25 26 Contains: Single-node operations for the BTree Module. 27 28 Version: xxx put the technology version here xxx 29 30 Written by: Gordon Sheridan and Bill Bruffey 31 32 Copyright: � 1992-1999 by Apple Computer, Inc., all rights reserved. 33*/ 34 35#include "BTreePrivate.h" 36#include "hfs_endian.h" 37#include "../fsck_hfs.h" 38 39 40///////////////////////// BTree Module Node Operations ////////////////////////// 41// 42// GetNode - Call FS Agent to get node 43// GetNewNode - Call FS Agent to get a new node 44// ReleaseNode - Call FS Agent to release node obtained by GetNode. 45// UpdateNode - Mark a node as dirty and call FS Agent to release it. 46// 47// ClearNode - Clear a node to all zeroes. 48// 49// InsertRecord - Inserts a record into a BTree node. 50// InsertKeyRecord - Inserts a key and record pair into a BTree node. 51// DeleteRecord - Deletes a record from a BTree node. 52// 53// SearchNode - Return index for record that matches key. 54// LocateRecord - Return pointer to key and data, and size of data. 55// 56// GetNodeDataSize - Return the amount of space used for data in the node. 57// GetNodeFreeSize - Return the amount of free space in the node. 58// 59// GetRecordOffset - Return the offset for record "index". 60// GetRecordAddress - Return address of record "index". 61// GetOffsetAddress - Return address of offset for record "index". 62// 63// InsertOffset - Inserts a new offset into a node. 64// DeleteOffset - Deletes an offset from a node. 65// 66// MoveRecordsLeft - Move records left within a node. 67// MoveRecordsRight - Move records right within a node. 68// 69///////////////////////////////////////////////////////////////////////////////// 70 71 72 73////////////////////// Routines Internal To BTreeNodeOps.c ////////////////////// 74 75UInt16 GetRecordOffset (BTreeControlBlockPtr btree, 76 NodeDescPtr node, 77 UInt16 index ); 78 79UInt16 *GetOffsetAddress (BTreeControlBlockPtr btreePtr, 80 NodeDescPtr node, 81 UInt16 index ); 82 83void InsertOffset (BTreeControlBlockPtr btreePtr, 84 NodeDescPtr node, 85 UInt16 index, 86 UInt16 delta ); 87 88void DeleteOffset (BTreeControlBlockPtr btreePtr, 89 NodeDescPtr node, 90 UInt16 index ); 91 92 93///////////////////////////////////////////////////////////////////////////////// 94 95#define GetRecordOffset(btreePtr,node,index) (*(short *) ((UInt8 *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)) 96 97 98/*------------------------------------------------------------------------------- 99 100Routine: GetNode - Call FS Agent to get node 101 102Function: Gets an existing BTree node from FS Agent and verifies it. 103 104Input: btreePtr - pointer to BTree control block 105 nodeNum - number of node to request 106 107Output: nodePtr - pointer to beginning of node (nil if error) 108 109Result: 110 noErr - success 111 != noErr - failure 112-------------------------------------------------------------------------------*/ 113 114OSStatus GetNode (BTreeControlBlockPtr btreePtr, 115 UInt32 nodeNum, 116 NodeRec *nodePtr ) 117{ 118 OSStatus err; 119 GetBlockProcPtr getNodeProc; 120 121 122// LogStartTime(kTraceGetNode); 123 124 //�� is nodeNum within proper range? 125 if( nodeNum >= btreePtr->totalNodes ) 126 { 127 Panic("\pGetNode:nodeNum >= totalNodes"); 128 if (debug) fprintf(stderr, "%s(%d): nodeNum %u > totalNodes %u\n", __FUNCTION__, __LINE__, nodeNum, btreePtr->totalNodes); 129 err = fsBTInvalidNodeErr; 130 goto ErrorExit; 131 } 132 133 getNodeProc = btreePtr->getBlockProc; 134 err = getNodeProc (btreePtr->fcbPtr, 135 nodeNum, 136 kGetBlock, 137 nodePtr ); 138 139 if (err != noErr) 140 { 141 Panic ("\pGetNode: getNodeProc returned error."); 142 nodePtr->buffer = nil; 143 goto ErrorExit; 144 } 145 ++btreePtr->numGetNodes; 146 147 err = hfs_swap_BTNode(nodePtr, btreePtr->fcbPtr, kSwapBTNodeBigToHost); 148 if (err != noErr) 149 { 150 (void) TrashNode (btreePtr, nodePtr); // ignore error 151 goto ErrorExit; 152 } 153 154// LogEndTime(kTraceGetNode, noErr); 155 156 return noErr; 157 158ErrorExit: 159 nodePtr->buffer = nil; 160 nodePtr->blockHeader = nil; 161 162// LogEndTime(kTraceGetNode, err); 163 164 return err; 165} 166 167 168 169/*------------------------------------------------------------------------------- 170 171Routine: GetNewNode - Call FS Agent to get a new node 172 173Function: Gets a new BTree node from FS Agent and initializes it to an empty 174 state. 175 176Input: btreePtr - pointer to BTree control block 177 nodeNum - number of node to request 178 179Output: returnNodePtr - pointer to beginning of node (nil if error) 180 181Result: noErr - success 182 != noErr - failure 183-------------------------------------------------------------------------------*/ 184 185OSStatus GetNewNode (BTreeControlBlockPtr btreePtr, 186 UInt32 nodeNum, 187 NodeRec *returnNodePtr ) 188{ 189 OSStatus err; 190 NodeDescPtr node; 191 void *pos; 192 GetBlockProcPtr getNodeProc; 193 194 195 //////////////////////// get buffer for new node //////////////////////////// 196 197 getNodeProc = btreePtr->getBlockProc; 198 err = getNodeProc (btreePtr->fcbPtr, 199 nodeNum, 200 kGetBlock+kGetEmptyBlock, 201 returnNodePtr ); 202 203 if (err != noErr) 204 { 205 Panic ("\pGetNewNode: getNodeProc returned error."); 206 returnNodePtr->buffer = nil; 207 return err; 208 } 209 ++btreePtr->numGetNewNodes; 210 211 212 ////////////////////////// initialize the node ////////////////////////////// 213 214 node = returnNodePtr->buffer; 215 216 ClearNode (btreePtr, node); // clear the node 217 218 pos = (char *)node + btreePtr->nodeSize - 2; // find address of last offset 219 *(UInt16 *)pos = sizeof (BTNodeDescriptor); // set offset to beginning of free space 220 221 222 return noErr; 223} 224 225 226 227/*------------------------------------------------------------------------------- 228 229Routine: ReleaseNode - Call FS Agent to release node obtained by GetNode. 230 231Function: Informs the FS Agent that a BTree node may be released. 232 233Input: btreePtr - pointer to BTree control block 234 nodeNum - number of node to release 235 236Result: noErr - success 237 != noErr - failure 238-------------------------------------------------------------------------------*/ 239 240OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr, 241 NodePtr nodePtr ) 242{ 243 OSStatus err; 244 ReleaseBlockProcPtr releaseNodeProc; 245 ReleaseBlockOptions options = kReleaseBlock; 246 247// LogStartTime(kTraceReleaseNode); 248 249 err = noErr; 250 251 if (nodePtr->buffer != nil) 252 { 253 /* 254 * The nodes must remain in the cache as big endian! 255 */ 256 err = hfs_swap_BTNode(nodePtr, btreePtr->fcbPtr, kSwapBTNodeHostToBig); 257 if (err) 258 { 259 options |= kTrashBlock; 260 } 261 262 releaseNodeProc = btreePtr->releaseBlockProc; 263 err = releaseNodeProc (btreePtr->fcbPtr, 264 nodePtr, 265 options ); 266 PanicIf (err, "\pReleaseNode: releaseNodeProc returned error."); 267 ++btreePtr->numReleaseNodes; 268 } 269 270 nodePtr->buffer = nil; 271 nodePtr->blockHeader = nil; 272 273// LogEndTime(kTraceReleaseNode, err); 274 275 return err; 276} 277 278 279/*------------------------------------------------------------------------------- 280 281Routine: TrashNode - Call FS Agent to release node obtained by GetNode, and 282 not store it...mark it as bad. 283 284Function: Informs the FS Agent that a BTree node may be released and thrown away. 285 286Input: btreePtr - pointer to BTree control block 287 nodeNum - number of node to release 288 289Result: noErr - success 290 != noErr - failure 291-------------------------------------------------------------------------------*/ 292 293OSStatus TrashNode (BTreeControlBlockPtr btreePtr, 294 NodePtr nodePtr ) 295{ 296 OSStatus err; 297 ReleaseBlockProcPtr releaseNodeProc; 298 299 300 err = noErr; 301 302 if (nodePtr->buffer != nil) 303 { 304 releaseNodeProc = btreePtr->releaseBlockProc; 305 err = releaseNodeProc (btreePtr->fcbPtr, 306 nodePtr, 307 kReleaseBlock | kTrashBlock ); 308 PanicIf (err, "\pTrashNode: releaseNodeProc returned error."); 309 ++btreePtr->numReleaseNodes; 310 } 311 312 nodePtr->buffer = nil; 313 nodePtr->blockHeader = nil; 314 315 return err; 316} 317 318 319/*------------------------------------------------------------------------------- 320 321Routine: UpdateNode - Mark a node as dirty and call FS Agent to release it. 322 323Function: Marks a BTree node dirty and informs the FS Agent that it may be released. 324 325Input: btreePtr - pointer to BTree control block 326 nodeNum - number of node to release 327 328Result: noErr - success 329 != noErr - failure 330-------------------------------------------------------------------------------*/ 331 332OSStatus UpdateNode (BTreeControlBlockPtr btreePtr, 333 NodePtr nodePtr ) 334{ 335 OSStatus err; 336 ReleaseBlockProcPtr releaseNodeProc; 337 ReleaseBlockOptions options = kMarkBlockDirty; 338 339 err = noErr; 340 341 if (nodePtr->buffer != nil) //�� why call UpdateNode if nil ?!? 342 { 343 // LogStartTime(kTraceReleaseNode); 344 345 err = hfs_swap_BTNode(nodePtr, btreePtr->fcbPtr, kSwapBTNodeHostToBig); 346 if (err != noErr) 347 { 348 options = kReleaseBlock | kTrashBlock; 349 } 350 351 releaseNodeProc = btreePtr->releaseBlockProc; 352 err = releaseNodeProc (btreePtr->fcbPtr, 353 nodePtr, 354 options ); 355 356 // LogEndTime(kTraceReleaseNode, err); 357 358 M_ExitOnError (err); 359 ++btreePtr->numUpdateNodes; 360 } 361 362 nodePtr->buffer = nil; 363 nodePtr->blockHeader = nil; 364 365 return noErr; 366 367ErrorExit: 368 369 return err; 370} 371 372 373 374/*------------------------------------------------------------------------------- 375 376Routine: ClearNode - Clear a node to all zeroes. 377 378Function: Writes zeroes from beginning of node for nodeSize bytes. 379 380Input: btreePtr - pointer to BTree control block 381 node - pointer to node to clear 382 383Result: none 384-------------------------------------------------------------------------------*/ 385 386void ClearNode (BTreeControlBlockPtr btreePtr, NodeDescPtr node ) 387{ 388 ClearMemory( node, btreePtr->nodeSize ); 389} 390 391/*------------------------------------------------------------------------------- 392 393Routine: InsertRecord - Inserts a record into a BTree node. 394 395Function: 396 397Note: Record size must be even! 398 399Input: btreePtr - pointer to BTree control block 400 node - pointer to node to insert the record 401 index - position record is to be inserted 402 recPtr - pointer to record to insert 403 404Result: noErr - success 405 fsBTFullErr - record larger than remaining free space. 406-------------------------------------------------------------------------------*/ 407 408Boolean InsertRecord (BTreeControlBlockPtr btreePtr, 409 NodeDescPtr node, 410 UInt16 index, 411 RecordPtr recPtr, 412 UInt16 recSize ) 413{ 414 UInt16 freeSpace; 415 UInt16 indexOffset; 416 UInt16 freeOffset; 417 UInt16 bytesToMove; 418 void *src; 419 void *dst; 420 421 //// will new record fit in node? 422 423 freeSpace = GetNodeFreeSize (btreePtr, node); 424 //�� we could get freeOffset & calc freeSpace 425 if ( freeSpace < recSize + 2) 426 { 427 return false; 428 } 429 430 431 //// make hole for new record 432 433 indexOffset = GetRecordOffset (btreePtr, node, index); 434 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); 435 436 src = ((Ptr) node) + indexOffset; 437 dst = ((Ptr) src) + recSize; 438 bytesToMove = freeOffset - indexOffset; 439 MoveRecordsRight (src, dst, bytesToMove); 440 441 442 //// adjust offsets for moved records 443 444 InsertOffset (btreePtr, node, index, recSize); 445 446 447 //// move in the new record 448 449 dst = ((Ptr) node) + indexOffset; 450 MoveRecordsLeft (recPtr, dst, recSize); 451 452 return true; 453} 454 455 456 457/*------------------------------------------------------------------------------- 458 459Routine: InsertKeyRecord - Inserts a record into a BTree node. 460 461Function: 462 463Note: Record size must be even! 464 465Input: btreePtr - pointer to BTree control block 466 node - pointer to node to insert the record 467 index - position record is to be inserted 468 keyPtr - pointer to key for record to insert 469 keyLength - length of key (or maxKeyLength) 470 recPtr - pointer to record to insert 471 recSize - number of bytes to copy for record 472 473Result: noErr - success 474 fsBTFullErr - record larger than remaining free space. 475-------------------------------------------------------------------------------*/ 476 477Boolean InsertKeyRecord (BTreeControlBlockPtr btreePtr, 478 NodeDescPtr node, 479 UInt16 index, 480 KeyPtr keyPtr, 481 UInt16 keyLength, 482 RecordPtr recPtr, 483 UInt16 recSize ) 484{ 485 UInt16 freeSpace; 486 UInt16 indexOffset; 487 UInt16 freeOffset; 488 UInt16 bytesToMove; 489 UInt8 * src; 490 UInt8 * dst; 491 UInt16 keySize; 492 UInt16 rawKeyLength; 493 UInt16 sizeOfLength; 494 495 //// calculate actual key size 496 497 if ( btreePtr->attributes & kBTBigKeysMask ) 498 keySize = keyLength + sizeof(UInt16); 499 else 500 keySize = keyLength + sizeof(UInt8); 501 502 if ( M_IsOdd (keySize) ) 503 ++keySize; // add pad byte 504 505 506 //// will new record fit in node? 507 508 freeSpace = GetNodeFreeSize (btreePtr, node); 509 //�� we could get freeOffset & calc freeSpace 510 if ( freeSpace < keySize + recSize + 2) 511 { 512 return false; 513 } 514 515 516 //// make hole for new record 517 518 indexOffset = GetRecordOffset (btreePtr, node, index); 519 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); 520 521 src = ((UInt8 *) node) + indexOffset; 522 dst = ((UInt8 *) src) + keySize + recSize; 523 bytesToMove = freeOffset - indexOffset; 524 MoveRecordsRight (src, dst, bytesToMove); 525 526 527 //// adjust offsets for moved records 528 529 InsertOffset (btreePtr, node, index, keySize + recSize); 530 531 532 //// copy record key 533 534 dst = ((UInt8 *) node) + indexOffset; 535 536 if ( btreePtr->attributes & kBTBigKeysMask ) 537 { 538 *((UInt16 *)dst) = keyLength; // use keyLength rather than key.length 539 rawKeyLength = keyPtr->length16; 540 sizeOfLength = 2; 541 } 542 else 543 { 544 *dst = keyLength; // use keyLength rather than key.length 545 rawKeyLength = keyPtr->length8; 546 sizeOfLength = 1; 547 } 548 dst += sizeOfLength; 549 550 MoveRecordsLeft ( ((UInt8 *) keyPtr) + sizeOfLength, dst, rawKeyLength); // copy key 551 552 // any pad bytes? 553 bytesToMove = keySize - rawKeyLength; 554 if (bytesToMove) 555 ClearMemory (dst + rawKeyLength, bytesToMove); // clear pad bytes in index key 556 557 558 //// copy record data 559 560 dst = ((UInt8 *) node) + indexOffset + keySize; 561 MoveRecordsLeft (recPtr, dst, recSize); 562 563 return true; 564} 565 566 567 568/*------------------------------------------------------------------------------- 569 570Routine: DeleteRecord - Deletes a record from a BTree node. 571 572Function: 573 574Input: btreePtr - pointer to BTree control block 575 node - pointer to node to insert the record 576 index - position record is to be inserted 577 578Result: none 579-------------------------------------------------------------------------------*/ 580 581void DeleteRecord (BTreeControlBlockPtr btreePtr, 582 NodeDescPtr node, 583 UInt16 index ) 584{ 585 SInt16 indexOffset; 586 SInt16 nextOffset; 587 SInt16 freeOffset; 588 SInt16 bytesToMove; 589 void *src; 590 void *dst; 591 592 //// compress records 593 indexOffset = GetRecordOffset (btreePtr, node, index); 594 nextOffset = GetRecordOffset (btreePtr, node, index + 1); 595 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); 596 597 src = ((Ptr) node) + nextOffset; 598 dst = ((Ptr) node) + indexOffset; 599 bytesToMove = freeOffset - nextOffset; 600 MoveRecordsLeft (src, dst, bytesToMove); 601 602 //// Adjust the offsets 603 DeleteOffset (btreePtr, node, index); 604} 605 606 607 608/*------------------------------------------------------------------------------- 609 610Routine: SearchNode - Return index for record that matches key. 611 612Function: Returns the record index for the record that matches the search key. 613 If no record was found that matches the search key, the "insert index" 614 of where the record should go is returned instead. 615 616Algorithm: A binary search algorithm is used to find the specified key. 617 618Input: btreePtr - pointer to BTree control block 619 node - pointer to node that contains the record 620 searchKey - pointer to the key to match 621 622Output: index - pointer to beginning of key for record 623 624Result: true - success (index = record index) 625 false - key did not match anything in node (index = insert index) 626-------------------------------------------------------------------------------*/ 627 628Boolean SearchNode (BTreeControlBlockPtr btreePtr, 629 NodeDescPtr node, 630 KeyPtr searchKey, 631 UInt16 *returnIndex ) 632{ 633 SInt32 lowerBound; 634 SInt32 upperBound; 635 SInt32 index; 636 SInt32 result; 637 KeyPtr trialKey; 638#if !SupportsKeyDescriptors 639 KeyCompareProcPtr compareProc = btreePtr->keyCompareProc; 640#endif 641 642 lowerBound = 0; 643 upperBound = node->numRecords - 1; 644 645 while (lowerBound <= upperBound) 646 { 647 index = (lowerBound + upperBound) >> 1; // divide by 2 648 649 trialKey = (KeyPtr) GetRecordAddress (btreePtr, node, index ); 650 651 #if SupportsKeyDescriptors 652 result = CompareKeys (btreePtr, searchKey, trialKey); 653 #else 654 result = compareProc(searchKey, trialKey); 655 #endif 656 657 if (result < 0) upperBound = index - 1; // search < trial 658 else if (result > 0) lowerBound = index + 1; // search > trial 659 else // search = trial 660 { 661 *returnIndex = index; 662 return true; 663 } 664 } 665 666 *returnIndex = lowerBound; // lowerBound is insert index 667 return false; 668} 669 670 671/*------------------------------------------------------------------------------- 672 673Routine: GetRecordByIndex - Return pointer to key and data, and size of data. 674 675Function: Returns a pointer to beginning of key for record, a pointer to the 676 beginning of the data for the record, and the size of the record data 677 (does not include the size of the key). 678 679Input: btreePtr - pointer to BTree control block 680 node - pointer to node that contains the record 681 index - index of record to get 682 683Output: keyPtr - pointer to beginning of key for record 684 dataPtr - pointer to beginning of data for record 685 dataSize - size of the data portion of the record 686 687Result: none 688-------------------------------------------------------------------------------*/ 689 690OSStatus GetRecordByIndex (BTreeControlBlockPtr btreePtr, 691 NodeDescPtr node, 692 UInt16 index, 693 KeyPtr *keyPtr, 694 UInt8 * *dataPtr, 695 UInt16 *dataSize ) 696{ 697 UInt16 offset; 698 UInt16 nextOffset; 699 UInt16 keySize; 700 701 // 702 // Make sure index is valid (in range 0..numRecords-1) 703 // 704 if (index >= node->numRecords) 705 return fsBTRecordNotFoundErr; 706 707 //// find keyPtr 708 offset = GetRecordOffset (btreePtr, node, index); 709 *keyPtr = (KeyPtr) ((Ptr)node + offset); 710 711 //// find dataPtr 712 keySize = CalcKeySize(btreePtr, *keyPtr); 713 if ( M_IsOdd (keySize) ) 714 ++keySize; // add pad byte 715 716 offset += keySize; // add the key length to find data offset 717 *dataPtr = (UInt8 *) node + offset; 718 719 //// find dataSize 720 nextOffset = GetRecordOffset (btreePtr, node, index + 1); 721 *dataSize = nextOffset - offset; 722 723 return noErr; 724} 725 726 727 728/*------------------------------------------------------------------------------- 729 730Routine: GetNodeDataSize - Return the amount of space used for data in the node. 731 732Function: Gets the size of the data currently contained in a node, excluding 733 the node header. (record data + offset overhead) 734 735Input: btreePtr - pointer to BTree control block 736 node - pointer to node that contains the record 737 738Result: - number of bytes used for data and offsets in the node. 739-------------------------------------------------------------------------------*/ 740 741UInt16 GetNodeDataSize (BTreeControlBlockPtr btreePtr, NodeDescPtr node ) 742{ 743 UInt16 freeOffset; 744 745 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); 746 747 return freeOffset + (node->numRecords << 1) - sizeof (BTNodeDescriptor); 748} 749 750 751 752/*------------------------------------------------------------------------------- 753 754Routine: GetNodeFreeSize - Return the amount of free space in the node. 755 756Function: 757 758Input: btreePtr - pointer to BTree control block 759 node - pointer to node that contains the record 760 761Result: - number of bytes of free space in the node. 762-------------------------------------------------------------------------------*/ 763 764UInt16 GetNodeFreeSize (BTreeControlBlockPtr btreePtr, NodeDescPtr node ) 765{ 766 UInt16 freeOffset; 767 768 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); //�� inline? 769 770 return btreePtr->nodeSize - freeOffset - (node->numRecords << 1) - kOffsetSize; 771} 772 773 774 775/*------------------------------------------------------------------------------- 776 777Routine: GetRecordOffset - Return the offset for record "index". 778 779Function: 780 781Input: btreePtr - pointer to BTree control block 782 node - pointer to node that contains the record 783 index - record to obtain offset for 784 785Result: - offset (in bytes) from beginning of node of record specified by index 786-------------------------------------------------------------------------------*/ 787// make this a macro (for inlining) 788#if 0 789UInt16 GetRecordOffset (BTreeControlBlockPtr btreePtr, 790 NodeDescPtr node, 791 UInt16 index ) 792{ 793 void *pos; 794 795 796 pos = (UInt8 *)node + btreePtr->nodeSize - (index << 1) - kOffsetSize; 797 798 return *(short *)pos; 799} 800#endif 801 802 803 804/*------------------------------------------------------------------------------- 805 806Routine: GetRecordAddress - Return address of record "index". 807 808Function: 809 810Input: btreePtr - pointer to BTree control block 811 node - pointer to node that contains the record 812 index - record to obtain offset address for 813 814Result: - pointer to record "index". 815-------------------------------------------------------------------------------*/ 816// make this a macro (for inlining) 817#if 0 818UInt8 * GetRecordAddress (BTreeControlBlockPtr btreePtr, 819 NodeDescPtr node, 820 UInt16 index ) 821{ 822 UInt8 * pos; 823 824 pos = (UInt8 *)node + GetRecordOffset (btreePtr, node, index); 825 826 return pos; 827} 828#endif 829 830 831 832/*------------------------------------------------------------------------------- 833 834Routine: GetRecordSize - Return size of record "index". 835 836Function: 837 838Note: This does not work on the FreeSpace index! 839 840Input: btreePtr - pointer to BTree control block 841 node - pointer to node that contains the record 842 index - record to obtain record size for 843 844Result: - size of record "index". 845-------------------------------------------------------------------------------*/ 846 847UInt16 GetRecordSize (BTreeControlBlockPtr btreePtr, 848 NodeDescPtr node, 849 UInt16 index ) 850{ 851 UInt16 *pos; 852 853 pos = (UInt16 *) ((Ptr)node + btreePtr->nodeSize - (index << 1) - kOffsetSize); 854 855 return *(pos-1) - *pos; 856} 857 858 859 860/*------------------------------------------------------------------------------- 861Routine: GetOffsetAddress - Return address of offset for record "index". 862 863Function: 864 865Input: btreePtr - pointer to BTree control block 866 node - pointer to node that contains the record 867 index - record to obtain offset address for 868 869Result: - pointer to offset for record "index". 870-------------------------------------------------------------------------------*/ 871 872UInt16 *GetOffsetAddress (BTreeControlBlockPtr btreePtr, 873 NodeDescPtr node, 874 UInt16 index ) 875{ 876 void *pos; 877 878 pos = (Ptr)node + btreePtr->nodeSize - (index << 1) -2; 879 880 return (UInt16 *)pos; 881} 882 883 884 885/*------------------------------------------------------------------------------- 886Routine: GetChildNodeNum - Return child node number from index record "index". 887 888Function: Returns the first UInt32 stored after the key for record "index". 889 890Assumes: The node is an Index Node. 891 The key.length stored at record "index" is ODD. //�� change for variable length index keys 892 893Input: btreePtr - pointer to BTree control block 894 node - pointer to node that contains the record 895 index - record to obtain child node number from 896 897Result: - child node number from record "index". 898-------------------------------------------------------------------------------*/ 899 900UInt32 GetChildNodeNum (BTreeControlBlockPtr btreePtr, 901 NodeDescPtr nodePtr, 902 UInt16 index ) 903{ 904 UInt8 * pos; 905 906 pos = GetRecordAddress (btreePtr, nodePtr, index); 907 pos += CalcKeySize(btreePtr, (BTreeKey *) pos); // key.length + size of length field 908 909 return *(UInt32 *)pos; 910} 911 912 913 914/*------------------------------------------------------------------------------- 915Routine: InsertOffset - Add an offset and adjust existing offsets by delta. 916 917Function: Add an offset at 'index' by shifting 'index+1' through the last offset 918 and adjusting them by 'delta', the size of the record to be inserted. 919 The number of records contained in the node is also incremented. 920 921Input: btreePtr - pointer to BTree control block 922 node - pointer to node 923 index - index at which to insert record 924 delta - size of record to be inserted 925 926Result: none 927-------------------------------------------------------------------------------*/ 928 929void InsertOffset (BTreeControlBlockPtr btreePtr, 930 NodeDescPtr node, 931 UInt16 index, 932 UInt16 delta ) 933{ 934 UInt16 *src, *dst; 935 UInt16 numOffsets; 936 937 src = GetOffsetAddress (btreePtr, node, node->numRecords); // point to free offset 938 dst = src - 1; // point to new offset 939 numOffsets = node->numRecords++ - index; // subtract index & postincrement 940 941 do { 942 *dst++ = *src++ + delta; // to tricky? 943 } while (numOffsets--); 944} 945 946 947 948/*------------------------------------------------------------------------------- 949 950Routine: DeleteOffset - Delete an offset. 951 952Function: Delete the offset at 'index' by shifting 'index+1' through the last offset 953 and adjusting them by the size of the record 'index'. 954 The number of records contained in the node is also decremented. 955 956Input: btreePtr - pointer to BTree control block 957 node - pointer to node 958 index - index at which to delete record 959 960Result: none 961-------------------------------------------------------------------------------*/ 962 963void DeleteOffset (BTreeControlBlockPtr btreePtr, 964 NodeDescPtr node, 965 UInt16 index ) 966{ 967 UInt16 *src, *dst; 968 UInt16 numOffsets; 969 UInt16 delta; 970 971 dst = GetOffsetAddress (btreePtr, node, index); 972 src = dst - 1; 973 delta = *src - *dst; 974 numOffsets = --node->numRecords - index; // predecrement numRecords & subtract index 975 976 while (numOffsets--) 977 { 978 *--dst = *--src - delta; // work our way left 979 } 980} 981 982 983 984/*------------------------------------------------------------------------------- 985 986Routine: MoveRecordsLeft - Move records left within a node. 987 988Function: Moves a number of bytes from src to dst. Safely handles overlapping 989 ranges if the bytes are being moved to the "left". No bytes are moved 990 if bytesToMove is zero. 991 992Input: src - pointer to source 993 dst - pointer to destination 994 bytesToMove - number of bytes to move records 995 996Result: none 997-------------------------------------------------------------------------------*/ 998#if 0 999void MoveRecordsLeft (UInt8 * src, 1000 UInt8 * dst, 1001 UInt16 bytesToMove ) 1002{ 1003 while (bytesToMove--) 1004 *dst++ = *src++; 1005} 1006#endif 1007 1008 1009/*------------------------------------------------------------------------------- 1010 1011Routine: MoveRecordsRight - Move records right within a node. 1012 1013Function: Moves a number of bytes from src to dst. Safely handles overlapping 1014 ranges if the bytes are being moved to the "right". No bytes are moved 1015 if bytesToMove is zero. 1016 1017Input: src - pointer to source 1018 dst - pointer to destination 1019 bytesToMove - number of bytes to move records 1020 1021Result: none 1022-------------------------------------------------------------------------------*/ 1023#if 0 1024void MoveRecordsRight (UInt8 * src, 1025 UInt8 * dst, 1026 UInt16 bytesToMove ) 1027{ 1028 src += bytesToMove; 1029 dst += bytesToMove; 1030 1031 while (bytesToMove--) 1032 *--dst = *--src; 1033} 1034#endif 1035