livefiles_hfs_plugin/lf_hfs_btree_node_ops.c

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