Return to BTreeNodeOps.c CVS log

Up to [Apple XNU] / XNU / bsd / hfs / hfscommon / BTree

Annotation of XNU/bsd/hfs/hfscommon/BTree/BTreeNodeOps.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.