Return to BTreeNodeOps.c CVS log

Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / BTree

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

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
        !             3:  *
        !             4:  * @APPLE_LICENSE_HEADER_START@
        !             5:  * 
        !             6:  * Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
        !             7:  * Reserved.  This file contains Original Code and/or Modifications of
        !             8:  * Original Code as defined in and that are subject to the Apple Public
        !             9:  * Source License Version 1.1 (the "License").  You may not use this file
        !            10:  * except in compliance with the License.  Please obtain a copy of the
        !            11:  * License at http://www.apple.com/publicsource and read it before using
        !            12:  * this file.
        !            13:  * 
        !            14:  * The Original Code and all software distributed under the License are
        !            15:  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
        !            16:  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
        !            17:  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
        !            18:  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
        !            19:  * License for the specific language governing rights and limitations
        !            20:  * under the License.
        !            21:  * 
        !            22:  * @APPLE_LICENSE_HEADER_END@
        !            23:  */
        !            24: 
        !            25: /*
        !            26:        File:           BTreeNodeOps.c
        !            27: 
        !            28:        Contains:       Single-node operations for the BTree Module.
        !            29: 
        !            30:        Version:        xxx put the technology version here xxx
        !            31: 
        !            32:        Written by:     Gordon Sheridan and Bill Bruffey
        !            33: 
        !            34:        Copyright:      � 1992-1997 by Apple Computer, Inc., all rights reserved.
        !            35: 
        !            36:        File Ownership:
        !            37: 
        !            38:                DRI:                            Don Brady
        !            39: 
        !            40:                Other Contact:          Mark Day
        !            41: 
        !            42:                Technology:                     File Systems
        !            43: 
        !            44:        Writers:
        !            45: 
        !            46:                (msd)   Mark Day
        !            47:                (djb)   Don Brady
        !            48: 
        !            49:        Change History (most recent first):
        !            50: 
        !            51:           <Rhap1>       3/26/97        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/system/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 TARGET_OS_RHAPSODY && DIAGNOSTIC
        !           167:        #ifdef KERNEL
        !           168:                #include <sys/systm.h>
        !           169:            #define PRINTIT kprintf
        !           170:        #else /* !KERNEL */
        !           171:            #define PRINTIT printf
        !           172:        #endif /* KERNEL */
        !           173: 
        !           174: static void PrintNode(const NodeDescPtr node, UInt16 nodeSize, UInt32 nodeNumber);
        !           175: #endif
        !           176: 
        !           177: 
        !           178: 
        !           179: /*-------------------------------------------------------------------------------
        !           180: 
        !           181: Routine:       GetNode -       Call FS Agent to get node
        !           182: 
        !           183: Function:      Gets an existing BTree node from FS Agent and verifies it.
        !           184: 
        !           185: Input:         btreePtr        - pointer to BTree control block
        !           186:                        nodeNum         - number of node to request
        !           187:                        
        !           188: Output:                nodePtr         - pointer to beginning of node (nil if error)
        !           189:                        
        !           190: Result:
        !           191:                        noErr           - success
        !           192:                        != noErr        - failure
        !           193: -------------------------------------------------------------------------------*/
        !           194: 
        !           195: OSStatus       GetNode         (BTreeControlBlockPtr    btreePtr,
        !           196:                                                 UInt32                                  nodeNum,
        !           197:                                                 NodeRec                                *nodePtr )
        !           198: {
        !           199:        OSStatus                        err;
        !           200:        GetBlockProcPtr         getNodeProc;
        !           201:        
        !           202: 
        !           203:        LogStartTime(kTraceGetNode);
        !           204: 
        !           205:        //�� is nodeNum within proper range?
        !           206:        if( nodeNum >= btreePtr->totalNodes )
        !           207:        {
        !           208:                Panic("\pGetNode:nodeNum >= totalNodes");
        !           209:                err = fsBTInvalidNodeErr;
        !           210:                goto ErrorExit;
        !           211:        }
        !           212:        
        !           213:        nodePtr->blockSize = btreePtr->nodeSize;        // indicate the size of a node
        !           214:        
        !           215:        getNodeProc = btreePtr->getBlockProc;
        !           216:        err = getNodeProc (btreePtr->fileRefNum,
        !           217:                                           nodeNum,
        !           218:                                           kGetBlock,
        !           219:                                           nodePtr );
        !           220: 
        !           221:        if (err != noErr)
        !           222:        {
        !           223:                Panic ("\pGetNode: getNodeProc returned error.");
        !           224:                goto ErrorExit;
        !           225:        }
        !           226:        ++btreePtr->numGetNodes;
        !           227:        
        !           228:        //
        !           229:        // Optimization
        !           230:        // Only call CheckNode if the node came from disk.
        !           231:        // If it was in the cache, we'll assume its already a valid node.
        !           232:        //
        !           233:        
        !           234:        if ( nodePtr->blockReadFromDisk )       // if we read it from disk then check it
        !           235:        {
        !           236:                err = CheckNode (btreePtr, nodePtr->buffer);
        !           237: 
        !           238:                if (err != noErr)
        !           239:                {
        !           240:                  #if TARGET_OS_RHAPSODY && 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:                return err;
        !           332:        }
        !           333:        ++btreePtr->numGetNewNodes;
        !           334:        
        !           335: 
        !           336:        ////////////////////////// initialize the node //////////////////////////////
        !           337: 
        !           338:        node = returnNodePtr->buffer;
        !           339:        
        !           340:        ClearNode (btreePtr, node);                                             // clear the node
        !           341: 
        !           342:        pos = (char *)node + btreePtr->nodeSize - 2;    // find address of last offset
        !           343:        *(UInt16 *)pos = sizeof (BTNodeDescriptor);             // set offset to beginning of free space
        !           344: 
        !           345: 
        !           346:        return noErr;
        !           347: }
        !           348: 
        !           349: 
        !           350: 
        !           351: /*-------------------------------------------------------------------------------
        !           352: 
        !           353: Routine:       ReleaseNode     -       Call FS Agent to release node obtained by GetNode.
        !           354: 
        !           355: Function:      Informs the FS Agent that a BTree node may be released.
        !           356: 
        !           357: Input:         btreePtr                - pointer to BTree control block
        !           358:                        nodeNum                 - number of node to release
        !           359:                                                
        !           360: Result:                noErr           - success
        !           361:                        != noErr        - failure
        !           362: -------------------------------------------------------------------------------*/
        !           363: 
        !           364: OSStatus       ReleaseNode     (BTreeControlBlockPtr    btreePtr,
        !           365:                                                 NodePtr                                 nodePtr )
        !           366: {
        !           367:        OSStatus                         err;
        !           368:        ReleaseBlockProcPtr      releaseNodeProc;
        !           369:        
        !           370:        
        !           371:        LogStartTime(kTraceReleaseNode);
        !           372: 
        !           373:        err = noErr;
        !           374:        
        !           375:        if (nodePtr->buffer != nil)
        !           376:        {
        !           377:                releaseNodeProc = btreePtr->releaseBlockProc;
        !           378:                err = releaseNodeProc (btreePtr->fileRefNum,
        !           379:                                                           nodePtr,
        !           380:                                                           kReleaseBlock );
        !           381:                PanicIf (err, "\pReleaseNode: releaseNodeProc returned error.");
        !           382:                ++btreePtr->numReleaseNodes;
        !           383:        }
        !           384:        
        !           385:        nodePtr->buffer                 = nil;
        !           386:        nodePtr->blockHeader    = nil;
        !           387:        
        !           388:        LogEndTime(kTraceReleaseNode, err);
        !           389: 
        !           390:        return err;
        !           391: }
        !           392: 
        !           393: 
        !           394: 
        !           395: /*-------------------------------------------------------------------------------
        !           396: 
        !           397: Routine:       UpdateNode      -       Mark a node as dirty and call FS Agent to release it.
        !           398: 
        !           399: Function:      Marks a BTree node dirty and informs the FS Agent that it may be released.
        !           400: 
        !           401:                        //�� have another routine that clears & writes a node, so we can call
        !           402:                        CheckNode from this routine.
        !           403: 
        !           404: Input:         btreePtr                - pointer to BTree control block
        !           405:                        nodeNum                 - number of node to release
        !           406:                                                
        !           407: Result:                noErr           - success
        !           408:                        != noErr        - failure
        !           409: -------------------------------------------------------------------------------*/
        !           410: 
        !           411: OSStatus       UpdateNode      (BTreeControlBlockPtr    btreePtr,
        !           412:                                                 NodePtr                                 nodePtr )
        !           413: {
        !           414:        OSStatus                         err;
        !           415:        ReleaseBlockProcPtr      releaseNodeProc;
        !           416:        
        !           417:        
        !           418:        err = noErr;
        !           419:                
        !           420:        if (nodePtr->buffer != nil)                     //�� why call UpdateNode if nil ?!?
        !           421:        {
        !           422:                if (DEBUG_BUILD)
        !           423:                {
        !           424:                        if ( btreePtr->attributes & kBTVariableIndexKeysMask )
        !           425:                                (void) CheckNode (btreePtr, nodePtr->buffer);
        !           426:                }
        !           427: 
        !           428:                LogStartTime(kTraceReleaseNode);
        !           429: 
        !           430:                releaseNodeProc = btreePtr->releaseBlockProc;
        !           431:                err = releaseNodeProc (btreePtr->fileRefNum,
        !           432:                                                           nodePtr,
        !           433:                                                           kMarkBlockDirty );
        !           434:                                                           
        !           435:                LogEndTime(kTraceReleaseNode, err);
        !           436: 
        !           437:                M_ExitOnError (err);
        !           438:                ++btreePtr->numUpdateNodes;
        !           439:        }
        !           440:        
        !           441:        nodePtr->buffer                 = nil;
        !           442:        nodePtr->blockHeader    = nil;
        !           443: 
        !           444:        return  noErr;
        !           445: 
        !           446: ErrorExit:
        !           447:        
        !           448:        return  err;
        !           449: }
        !           450: 
        !           451: 
        !           452: 
        !           453: /*-------------------------------------------------------------------------------
        !           454: 
        !           455: Routine:       CheckNode       -       Checks the validity of a node.
        !           456: 
        !           457: Function:      Checks the validity of a node by verifying that the fLink and bLink fields
        !           458:                        are within the forks EOF. The node type must be one of the four known
        !           459:                        types. The node height must be less than or equal to the tree height. The
        !           460:                        node must not have more than the maximum number of records, and the record
        !           461:                        offsets must make sense.
        !           462: 
        !           463: Input:         btreePtr                - pointer to BTree control block
        !           464:                        node                    - pointer to node to check
        !           465:                                                
        !           466: Result:                noErr           - success
        !           467:                        fsBTInvalidNodeErr              - failure
        !           468: -------------------------------------------------------------------------------*/
        !           469: 
        !           470: OSStatus       CheckNode       (BTreeControlBlockPtr    btreePtr, NodeDescPtr   node )
        !           471: {
        !           472:        SInt32          index;
        !           473:        SInt32          maxRecords;
        !           474:        UInt32          maxNode;
        !           475:        UInt16          nodeSize;
        !           476:        UInt16          offset;
        !           477:        UInt16          prevOffset;
        !           478: 
        !           479: #if DEBUG_BUILD
        !           480:        KeyPtr                          thisKey, lastKey = NULL;
        !           481:        KeyCompareProcPtr       compareProc = NULL;
        !           482: #endif
        !           483: 
        !           484:        
        !           485:        nodeSize = btreePtr->nodeSize;
        !           486: 
        !           487:        ///////////////////// are fLink and bLink within EOF ////////////////////////
        !           488:        
        !           489:        maxNode = (GetFileControlBlock(btreePtr->fileRefNum)->fcbEOF / nodeSize) - 1;
        !           490:        
        !           491:        if ( (node->fLink > maxNode) || (node->bLink > maxNode) )
        !           492:                return fsBTInvalidNodeErr;
        !           493:        
        !           494:        
        !           495:        /////////////// check node type (leaf, index, header, map) //////////////////
        !           496:        
        !           497:        if ( (node->type < kLeafNode) || (node->type > kMapNode) )
        !           498:                return fsBTInvalidNodeErr;
        !           499:        
        !           500: 
        !           501:        ///////////////////// is node height > tree depth? //////////////////////////
        !           502: 
        !           503:        if ( node->height > btreePtr->treeDepth )
        !           504:                return fsBTInvalidNodeErr;
        !           505:        
        !           506: 
        !           507:        //////////////////////// check number of records ////////////////////////////
        !           508:                
        !           509:        //�� can we calculate a more accurate minimum record size?
        !           510:        maxRecords = ( nodeSize - sizeof (BTNodeDescriptor) ) >> 3;
        !           511:        
        !           512:        if (node->numRecords > maxRecords)
        !           513:                return fsBTInvalidNodeErr;
        !           514: 
        !           515: 
        !           516:        ////////////////////////// check record offsets /////////////////////////////
        !           517: 
        !           518:        index = node->numRecords;                                       // begin with free space offset
        !           519:        offset = nodeSize - (index << 1);                               // init offset to max free offset+2
        !           520:        
        !           521: #if DEBUG_BUILD
        !           522:        if ( btreePtr->attributes & kBTVariableIndexKeysMask )
        !           523:        {
        !           524:                compareProc = btreePtr->keyCompareProc;
        !           525:                lastKey = NULL;
        !           526:        }
        !           527: #endif
        !           528: 
        !           529:        do {
        !           530:                prevOffset = offset;
        !           531:                offset = GetRecordOffset (btreePtr, node, index);       
        !           532: 
        !           533: #if DEBUG_BUILD        
        !           534:                if ( btreePtr->attributes & kBTVariableIndexKeysMask    &&
        !           535:                         index < node->numRecords                                                       &&
        !           536:                         (node->type == kLeafNode || node->type == kIndexNode) )
        !           537:                {
        !           538:                        thisKey = (KeyPtr) GetRecordAddress (btreePtr, node, index );
        !           539:        
        !           540:                        if ( (lastKey != NULL) && (compareProc(thisKey, lastKey) >= 0) )
        !           541:                        {
        !           542:                                Panic ( "\p CheckNode: keys out of order! ");
        !           543:                                return fsBTInvalidNodeErr;
        !           544:                        }
        !           545:                        
        !           546:                        lastKey = thisKey;
        !           547:                }
        !           548: #endif
        !           549: 
        !           550:                if (offset < sizeof (BTNodeDescriptor) )        // offset < minimum
        !           551:                        return fsBTInvalidNodeErr;
        !           552:                        
        !           553:                if (offset & 1)                                                         // offset is odd
        !           554:                        return fsBTInvalidNodeErr;
        !           555:                
        !           556:                if (offset >= prevOffset)                                       // offset >= previous offset
        !           557:                        return fsBTInvalidNodeErr;
        !           558:                
        !           559:                if (offset >= nodeSize)                                         // offset beyond end of node
        !           560:                        return fsBTInvalidNodeErr;
        !           561:                
        !           562:        } while ( --index >= 0 );
        !           563:        
        !           564:        
        !           565:        return noErr;
        !           566: }
        !           567: 
        !           568: 
        !           569: #if TARGET_OS_RHAPSODY && DIAGNOSTIC
        !           570: static void PrintNode(const NodeDescPtr node, UInt16 nodeSize, UInt32 nodeNumber)
        !           571: {
        !           572:        struct row {
        !           573:                UInt16  word[8];
        !           574:        };
        !           575:        struct row      *offset;
        !           576:        UInt16  rows;
        !           577:        UInt32  *lp;
        !           578: 
        !           579:        PRINTIT("Dump of B-tree node #%ld ($%08lX)\n", nodeNumber, nodeNumber);
        !           580: 
        !           581:        rows = nodeSize/16;
        !           582:        lp = (UInt32*) node;
        !           583:        offset = 0;
        !           584:        
        !           585:        while (rows-- > 0)
        !           586:                PRINTIT("%04X: %08lX %08lX %08lX %08lX\n", (u_int)offset++, *lp++, *lp++, *lp++, *lp++);
        !           587: }
        !           588: #endif
        !           589: 
        !           590: 
        !           591: /*-------------------------------------------------------------------------------
        !           592: 
        !           593: Routine:       ClearNode       -       Clear a node to all zeroes.
        !           594: 
        !           595: Function:      Writes zeroes from beginning of node for nodeSize bytes.
        !           596: 
        !           597: Input:         btreePtr                - pointer to BTree control block
        !           598:                        node                    - pointer to node to clear
        !           599:                                                
        !           600: Result:                none
        !           601: -------------------------------------------------------------------------------*/
        !           602: 
        !           603: void   ClearNode       (BTreeControlBlockPtr   btreePtr, NodeDescPtr    node )
        !           604: {
        !           605:        ClearMemory( node, btreePtr->nodeSize );
        !           606: }
        !           607: 
        !           608: /*-------------------------------------------------------------------------------
        !           609: 
        !           610: Routine:       InsertRecord    -       Inserts a record into a BTree node.
        !           611: 
        !           612: Function:      
        !           613: 
        !           614: Note:          Record size must be even!
        !           615: 
        !           616: Input:         btreePtr                - pointer to BTree control block
        !           617:                        node                    - pointer to node to insert the record
        !           618:                        index                   - position record is to be inserted
        !           619:                        recPtr                  - pointer to record to insert
        !           620: 
        !           621: Result:                noErr           - success
        !           622:                        fsBTFullErr     - record larger than remaining free space.
        !           623: -------------------------------------------------------------------------------*/
        !           624: 
        !           625: Boolean                InsertRecord    (BTreeControlBlockPtr   btreePtr,
        !           626:                                                         NodeDescPtr                    node,
        !           627:                                                         UInt16                                 index,
        !           628:                                                         RecordPtr                              recPtr,
        !           629:                                                         UInt16                                 recSize )
        !           630: {
        !           631:        UInt16          freeSpace;
        !           632:        UInt16          indexOffset;
        !           633:        UInt16          freeOffset;
        !           634:        UInt16          bytesToMove;
        !           635:        void       *src;
        !           636:        void       *dst;
        !           637:        
        !           638:        //// will new record fit in node?
        !           639: 
        !           640:        freeSpace = GetNodeFreeSize (btreePtr, node);
        !           641:                                                                                        //�� we could get freeOffset & calc freeSpace
        !           642:        if ( freeSpace < recSize + 2)
        !           643:        {
        !           644:                return false;
        !           645:        }
        !           646: 
        !           647:        
        !           648:        //// make hole for new record
        !           649: 
        !           650:        indexOffset = GetRecordOffset (btreePtr, node, index);
        !           651:        freeOffset      = GetRecordOffset (btreePtr, node, node->numRecords);
        !           652: 
        !           653:        src = ((Ptr) node) + indexOffset;
        !           654:        dst = ((Ptr) src)  + recSize;
        !           655:        bytesToMove = freeOffset - indexOffset;
        !           656:        MoveRecordsRight (src, dst, bytesToMove);
        !           657: 
        !           658: 
        !           659:        //// adjust offsets for moved records
        !           660: 
        !           661:        InsertOffset (btreePtr, node, index, recSize);
        !           662: 
        !           663: 
        !           664:        //// move in the new record
        !           665: 
        !           666:        dst = ((Ptr) node) + indexOffset;
        !           667:        MoveRecordsLeft (recPtr, dst, recSize);
        !           668: 
        !           669:        return true;
        !           670: }
        !           671: 
        !           672: 
        !           673: 
        !           674: /*-------------------------------------------------------------------------------
        !           675: 
        !           676: Routine:       InsertKeyRecord -       Inserts a record into a BTree node.
        !           677: 
        !           678: Function:      
        !           679: 
        !           680: Note:          Record size must be even!
        !           681: 
        !           682: Input:         btreePtr                - pointer to BTree control block
        !           683:                        node                    - pointer to node to insert the record
        !           684:                        index                   - position record is to be inserted
        !           685:                        keyPtr                  - pointer to key for record to insert
        !           686:                        keyLength               - length of key (or maxKeyLength)
        !           687:                        recPtr                  - pointer to record to insert
        !           688:                        recSize                 - number of bytes to copy for record
        !           689: 
        !           690: Result:                noErr           - success
        !           691:                        fsBTFullErr     - record larger than remaining free space.
        !           692: -------------------------------------------------------------------------------*/
        !           693: 
        !           694: Boolean                InsertKeyRecord         (BTreeControlBlockPtr    btreePtr,
        !           695:                                                                 NodeDescPtr                     node,
        !           696:                                                                 UInt16                                  index,
        !           697:                                                                 KeyPtr                                  keyPtr,
        !           698:                                                                 UInt16                                  keyLength,
        !           699:                                                                 RecordPtr                               recPtr,
        !           700:                                                                 UInt16                                  recSize )
        !           701: {
        !           702:        UInt16          freeSpace;
        !           703:        UInt16          indexOffset;
        !           704:        UInt16          freeOffset;
        !           705:        UInt16          bytesToMove;
        !           706:        UInt8 *         src;
        !           707:        UInt8 *         dst;
        !           708:        UInt16          keySize;
        !           709:        UInt16          rawKeyLength;
        !           710:        UInt16          sizeOfLength;
        !           711:        
        !           712:        //// calculate actual key size
        !           713: 
        !           714:        if ( btreePtr->attributes & kBTBigKeysMask )
        !           715:                keySize = keyLength + sizeof(UInt16);
        !           716:        else
        !           717:                keySize = keyLength + sizeof(UInt8);
        !           718:        
        !           719:        if ( M_IsOdd (keySize) )
        !           720:                ++keySize;                      // add pad byte
        !           721: 
        !           722: 
        !           723:        //// will new record fit in node?
        !           724: 
        !           725:        freeSpace = GetNodeFreeSize (btreePtr, node);
        !           726:                                                                                        //�� we could get freeOffset & calc freeSpace
        !           727:        if ( freeSpace < keySize + recSize + 2)
        !           728:        {
        !           729:                return false;
        !           730:        }
        !           731: 
        !           732:        
        !           733:        //// make hole for new record
        !           734: 
        !           735:        indexOffset = GetRecordOffset (btreePtr, node, index);
        !           736:        freeOffset      = GetRecordOffset (btreePtr, node, node->numRecords);
        !           737: 
        !           738:        src = ((UInt8 *) node) + indexOffset;
        !           739:        dst = ((UInt8 *) src) + keySize + recSize;
        !           740:        bytesToMove = freeOffset - indexOffset;
        !           741:        MoveRecordsRight (src, dst, bytesToMove);
        !           742: 
        !           743: 
        !           744:        //// adjust offsets for moved records
        !           745: 
        !           746:        InsertOffset (btreePtr, node, index, keySize + recSize);
        !           747:        
        !           748: 
        !           749:        //// copy record key
        !           750: 
        !           751:        dst = ((UInt8 *) node) + indexOffset;
        !           752: 
        !           753:        if ( btreePtr->attributes & kBTBigKeysMask )
        !           754:        {
        !           755:                *((UInt16*) dst)++ = keyLength;         // use keyLength rather than key.length
        !           756:                rawKeyLength = keyPtr->length16;
        !           757:                sizeOfLength = 2;
        !           758:        }
        !           759:        else
        !           760:        {
        !           761:                *dst++ = keyLength;                                     // use keyLength rather than key.length
        !           762:                rawKeyLength = keyPtr->length8;
        !           763:                sizeOfLength = 1;
        !           764:        }
        !           765:        
        !           766:        MoveRecordsLeft ( ((UInt8 *) keyPtr) + sizeOfLength, dst, rawKeyLength);        // copy key
        !           767: 
        !           768:        // any pad bytes?
        !           769:        bytesToMove = keySize - rawKeyLength;
        !           770:        if (bytesToMove)
        !           771:                ClearMemory (dst + rawKeyLength, bytesToMove);  // clear pad bytes in index key
        !           772: 
        !           773: 
        !           774:        //// copy record data
        !           775: 
        !           776:        dst = ((UInt8 *) node) + indexOffset + keySize;
        !           777:        MoveRecordsLeft (recPtr, dst, recSize);
        !           778: 
        !           779:        return true;
        !           780: }
        !           781: 
        !           782: 
        !           783: 
        !           784: /*-------------------------------------------------------------------------------
        !           785: 
        !           786: Routine:       DeleteRecord    -       Deletes a record from a BTree node.
        !           787: 
        !           788: Function:      
        !           789: 
        !           790: Input:         btreePtr                - pointer to BTree control block
        !           791:                        node                    - pointer to node to insert the record
        !           792:                        index                   - position record is to be inserted
        !           793: 
        !           794: Result:                none
        !           795: -------------------------------------------------------------------------------*/
        !           796: 
        !           797: void           DeleteRecord    (BTreeControlBlockPtr   btreePtr,
        !           798:                                                         NodeDescPtr                    node,
        !           799:                                                         UInt16                                 index )
        !           800: {
        !           801:        SInt16          indexOffset;
        !           802:        SInt16          nextOffset;
        !           803:        SInt16          freeOffset;
        !           804:        SInt16          bytesToMove;
        !           805:        void       *src;
        !           806:        void       *dst;
        !           807:        
        !           808:        //// compress records
        !           809:        indexOffset = GetRecordOffset (btreePtr, node, index);
        !           810:        nextOffset      = GetRecordOffset (btreePtr, node, index + 1);
        !           811:        freeOffset      = GetRecordOffset (btreePtr, node, node->numRecords);
        !           812: 
        !           813:        src = ((Ptr) node) + nextOffset;
        !           814:        dst = ((Ptr) node) + indexOffset;
        !           815:        bytesToMove = freeOffset - nextOffset;
        !           816:        MoveRecordsLeft (src, dst, bytesToMove);
        !           817: 
        !           818:        //// Adjust the offsets
        !           819:        DeleteOffset (btreePtr, node, index);
        !           820: }
        !           821: 
        !           822: 
        !           823: 
        !           824: /*-------------------------------------------------------------------------------
        !           825: 
        !           826: Routine:       SearchNode      -       Return index for record that matches key.
        !           827: 
        !           828: Function:      Returns the record index for the record that matches the search key.
        !           829:                        If no record was found that matches the search key, the "insert index"
        !           830:                        of where the record should go is returned instead.
        !           831: 
        !           832: Algorithm:     A binary search algorithm is used to find the specified key.
        !           833: 
        !           834: Input:         btreePtr        - pointer to BTree control block
        !           835:                        node            - pointer to node that contains the record
        !           836:                        searchKey       - pointer to the key to match
        !           837: 
        !           838: Output:                index           - pointer to beginning of key for record
        !           839: 
        !           840: Result:                true    - success (index = record index)
        !           841:                        false   - key did not match anything in node (index = insert index)
        !           842: -------------------------------------------------------------------------------*/
        !           843: #if !TARGET_CPU_68K
        !           844: 
        !           845: Boolean                SearchNode              (BTreeControlBlockPtr    btreePtr,
        !           846:                                                         NodeDescPtr                     node,
        !           847:                                                         KeyPtr                                  searchKey,
        !           848:                                                         UInt16                                 *returnIndex )
        !           849: {
        !           850:        SInt32          lowerBound;
        !           851:        SInt32          upperBound;
        !           852:        SInt32          index;
        !           853:        SInt32          result;
        !           854:        KeyPtr          trialKey;
        !           855: #if !SupportsKeyDescriptors
        !           856:        KeyCompareProcPtr       compareProc = btreePtr->keyCompareProc;
        !           857: #endif 
        !           858: 
        !           859:        lowerBound = 0;
        !           860:        upperBound = node->numRecords - 1;
        !           861:        
        !           862:        while (lowerBound <= upperBound)
        !           863:        {
        !           864:                index = (lowerBound + upperBound) >> 1;         // divide by 2
        !           865:                
        !           866:                trialKey = (KeyPtr) GetRecordAddress (btreePtr, node, index );
        !           867:                
        !           868:        #if SupportsKeyDescriptors
        !           869:                result = CompareKeys (btreePtr, searchKey, trialKey);
        !           870:        #else
        !           871:                result = compareProc(searchKey, trialKey);
        !           872:        #endif
        !           873:                
        !           874:                if              (result <  0)           upperBound = index - 1;         // search < trial
        !           875:                else if (result >  0)           lowerBound = index + 1;         // search > trial
        !           876:                else                                                                                                    // search = trial
        !           877:                {
        !           878:                        *returnIndex = index;
        !           879:                        return true;
        !           880:                }
        !           881:        }
        !           882:        
        !           883:        *returnIndex = lowerBound;                              // lowerBound is insert index
        !           884:        return false;
        !           885: }
        !           886: 
        !           887: #endif
        !           888: 
        !           889: 
        !           890: /*-------------------------------------------------------------------------------
        !           891: 
        !           892: Routine:       GetRecordByIndex        -       Return pointer to key and data, and size of data.
        !           893: 
        !           894: Function:      Returns a pointer to beginning of key for record, a pointer to the
        !           895:                        beginning of the data for the record, and the size of the record data
        !           896:                        (does not include the size of the key).
        !           897: 
        !           898: Input:         btreePtr        - pointer to BTree control block
        !           899:                        node            - pointer to node that contains the record
        !           900:                        index           - index of record to get
        !           901: 
        !           902: Output:                keyPtr          - pointer to beginning of key for record
        !           903:                        dataPtr         - pointer to beginning of data for record
        !           904:                        dataSize        - size of the data portion of the record
        !           905: 
        !           906: Result:                none
        !           907: -------------------------------------------------------------------------------*/
        !           908: 
        !           909: OSStatus       GetRecordByIndex        (BTreeControlBlockPtr    btreePtr,
        !           910:                                                                 NodeDescPtr                     node,
        !           911:                                                                 UInt16                                  index,
        !           912:                                                                 KeyPtr                                 *keyPtr,
        !           913:                                                                 UInt8 *                                *dataPtr,
        !           914:                                                                 UInt16                                 *dataSize )
        !           915: {
        !           916:        UInt16          offset;
        !           917:        UInt16          nextOffset;
        !           918:        UInt16          keySize;
        !           919:        
        !           920:        //
        !           921:        //      Make sure index is valid (in range 0..numRecords-1)
        !           922:        //
        !           923:        if (index >= node->numRecords)
        !           924:                return fsBTRecordNotFoundErr;
        !           925: 
        !           926:        //// find keyPtr
        !           927:        offset          = GetRecordOffset (btreePtr, node, index);
        !           928:        *keyPtr         = (KeyPtr) ((Ptr)node + offset);
        !           929: 
        !           930:        //// find dataPtr
        !           931:        keySize = CalcKeySize(btreePtr, *keyPtr);
        !           932:        if ( M_IsOdd (keySize) )
        !           933:                ++keySize;      // add pad byte
        !           934: 
        !           935:        offset += keySize;                      // add the key length to find data offset
        !           936:        *dataPtr = (UInt8 *) node + offset;
        !           937:        
        !           938:        //// find dataSize
        !           939:        nextOffset      = GetRecordOffset (btreePtr, node, index + 1);
        !           940:        *dataSize       = nextOffset - offset;
        !           941:        
        !           942:        return noErr;
        !           943: }
        !           944:                                                                 
        !           945: 
        !           946: 
        !           947: /*-------------------------------------------------------------------------------
        !           948: 
        !           949: Routine:       GetNodeDataSize -       Return the amount of space used for data in the node.
        !           950: 
        !           951: Function:      Gets the size of the data currently contained in a node, excluding
        !           952:                        the node header. (record data + offset overhead)
        !           953: 
        !           954: Input:         btreePtr                - pointer to BTree control block
        !           955:                        node                    - pointer to node that contains the record
        !           956: 
        !           957: Result:                - number of bytes used for data and offsets in the node.
        !           958: -------------------------------------------------------------------------------*/
        !           959: 
        !           960: UInt16         GetNodeDataSize (BTreeControlBlockPtr   btreePtr, NodeDescPtr    node )
        !           961: {
        !           962:        UInt16 freeOffset;
        !           963:        
        !           964:        freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
        !           965:        
        !           966:        return  freeOffset + (node->numRecords << 1) - sizeof (BTNodeDescriptor);
        !           967: }
        !           968: 
        !           969: 
        !           970: 
        !           971: /*-------------------------------------------------------------------------------
        !           972: 
        !           973: Routine:       GetNodeFreeSize -       Return the amount of free space in the node.
        !           974: 
        !           975: Function:      
        !           976: 
        !           977: Input:         btreePtr                - pointer to BTree control block
        !           978:                        node                    - pointer to node that contains the record
        !           979: 
        !           980: Result:                - number of bytes of free space in the node.
        !           981: -------------------------------------------------------------------------------*/
        !           982: 
        !           983: UInt16         GetNodeFreeSize (BTreeControlBlockPtr   btreePtr, NodeDescPtr    node )
        !           984: {
        !           985:        UInt16  freeOffset;
        !           986:        
        !           987:        freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);        //�� inline?
        !           988:        
        !           989:        return btreePtr->nodeSize - freeOffset - (node->numRecords << 1) - kOffsetSize;
        !           990: }
        !           991: 
        !           992: 
        !           993: 
        !           994: /*-------------------------------------------------------------------------------
        !           995: 
        !           996: Routine:       GetRecordOffset -       Return the offset for 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 for
        !          1003: 
        !          1004: Result:                - offset (in bytes) from beginning of node of record specified by index
        !          1005: -------------------------------------------------------------------------------*/
        !          1006: // make this a macro (for inlining)
        !          1007: #if 0
        !          1008: UInt16         GetRecordOffset (BTreeControlBlockPtr   btreePtr,
        !          1009:                                                         NodeDescPtr                    node,
        !          1010:                                                         UInt16                                 index )
        !          1011: {
        !          1012:        void    *pos;
        !          1013:        
        !          1014:                
        !          1015:        pos = (UInt8 *)node + btreePtr->nodeSize - (index << 1) - kOffsetSize;
        !          1016:        
        !          1017:        return *(short *)pos;
        !          1018: }
        !          1019: #endif
        !          1020: 
        !          1021: 
        !          1022: 
        !          1023: /*-------------------------------------------------------------------------------
        !          1024: 
        !          1025: Routine:       GetRecordAddress        -       Return address of record "index".
        !          1026: 
        !          1027: Function:      
        !          1028: 
        !          1029: Input:         btreePtr                - pointer to BTree control block
        !          1030:                        node                    - pointer to node that contains the record
        !          1031:                        index                   - record to obtain offset address for
        !          1032: 
        !          1033: Result:                - pointer to record "index".
        !          1034: -------------------------------------------------------------------------------*/
        !          1035: // make this a macro (for inlining)
        !          1036: #if 0
        !          1037: UInt8 *                GetRecordAddress        (BTreeControlBlockPtr   btreePtr,
        !          1038:                                                                 NodeDescPtr                    node,
        !          1039:                                                                 UInt16                                 index )
        !          1040: {
        !          1041:        UInt8 *         pos;
        !          1042:        
        !          1043:        pos = (UInt8 *)node + GetRecordOffset (btreePtr, node, index);
        !          1044:        
        !          1045:        return pos;
        !          1046: }
        !          1047: #endif
        !          1048: 
        !          1049: 
        !          1050: 
        !          1051: /*-------------------------------------------------------------------------------
        !          1052: 
        !          1053: Routine:       GetRecordSize   -       Return size of record "index".
        !          1054: 
        !          1055: Function:      
        !          1056: 
        !          1057: Note:          This does not work on the FreeSpace index!
        !          1058: 
        !          1059: Input:         btreePtr                - pointer to BTree control block
        !          1060:                        node                    - pointer to node that contains the record
        !          1061:                        index                   - record to obtain record size for
        !          1062: 
        !          1063: Result:                - size of record "index".
        !          1064: -------------------------------------------------------------------------------*/
        !          1065: 
        !          1066: UInt16         GetRecordSize           (BTreeControlBlockPtr   btreePtr,
        !          1067:                                                                 NodeDescPtr                    node,
        !          1068:                                                                 UInt16                                 index )
        !          1069: {
        !          1070:        UInt16  *pos;
        !          1071:                
        !          1072:        pos = (UInt16 *) ((Ptr)node + btreePtr->nodeSize - (index << 1) - kOffsetSize);
        !          1073:        
        !          1074:        return  *(pos-1) - *pos;
        !          1075: }
        !          1076: 
        !          1077: 
        !          1078: 
        !          1079: /*-------------------------------------------------------------------------------
        !          1080: Routine:       GetOffsetAddress        -       Return address of offset for record "index".
        !          1081: 
        !          1082: Function:      
        !          1083: 
        !          1084: Input:         btreePtr                - pointer to BTree control block
        !          1085:                        node                    - pointer to node that contains the record
        !          1086:                        index                   - record to obtain offset address for
        !          1087: 
        !          1088: Result:                - pointer to offset for record "index".
        !          1089: -------------------------------------------------------------------------------*/
        !          1090: 
        !          1091: UInt16    *GetOffsetAddress    (BTreeControlBlockPtr   btreePtr,
        !          1092:                                                                 NodeDescPtr                    node,
        !          1093:                                                                 UInt16                                 index )
        !          1094: {
        !          1095:        void    *pos;
        !          1096:        
        !          1097:        pos = (Ptr)node + btreePtr->nodeSize - (index << 1) -2;
        !          1098:        
        !          1099:        return (UInt16 *)pos;
        !          1100: }
        !          1101: 
        !          1102: 
        !          1103: 
        !          1104: /*-------------------------------------------------------------------------------
        !          1105: Routine:       GetChildNodeNum -       Return child node number from index record "index".
        !          1106: 
        !          1107: Function:      Returns the first UInt32 stored after the key for record "index".
        !          1108: 
        !          1109: Assumes:       The node is an Index Node.
        !          1110:                        The key.length stored at record "index" is ODD. //�� change for variable length index keys
        !          1111: 
        !          1112: Input:         btreePtr                - pointer to BTree control block
        !          1113:                        node                    - pointer to node that contains the record
        !          1114:                        index                   - record to obtain child node number from
        !          1115: 
        !          1116: Result:                - child node number from record "index".
        !          1117: -------------------------------------------------------------------------------*/
        !          1118: 
        !          1119: UInt32         GetChildNodeNum                 (BTreeControlBlockPtr    btreePtr,
        !          1120:                                                                         NodeDescPtr                     nodePtr,
        !          1121:                                                                         UInt16                                  index )
        !          1122: {
        !          1123:        UInt8 *         pos;
        !          1124:        
        !          1125:        pos = GetRecordAddress (btreePtr, nodePtr, index);
        !          1126:        pos += CalcKeySize(btreePtr, (BTreeKey *) pos);         // key.length + size of length field
        !          1127:        
        !          1128:        return  *(UInt32 *)pos;
        !          1129: }
        !          1130: 
        !          1131: 
        !          1132: 
        !          1133: /*-------------------------------------------------------------------------------
        !          1134: Routine:       InsertOffset    -       Add an offset and adjust existing offsets by delta.
        !          1135: 
        !          1136: Function:      Add an offset at 'index' by shifting 'index+1' through the last offset
        !          1137:                        and adjusting them by 'delta', the size of the record to be inserted.
        !          1138:                        The number of records contained in the node is also incremented.
        !          1139: 
        !          1140: Input:         btreePtr        - pointer to BTree control block
        !          1141:                        node            - pointer to node
        !          1142:                        index           - index at which to insert record
        !          1143:                        delta           - size of record to be inserted
        !          1144: 
        !          1145: Result:                none
        !          1146: -------------------------------------------------------------------------------*/
        !          1147: 
        !          1148: void           InsertOffset            (BTreeControlBlockPtr    btreePtr,
        !          1149:                                                                 NodeDescPtr                     node,
        !          1150:                                                                 UInt16                                  index,
        !          1151:                                                                 UInt16                                  delta )
        !          1152: {
        !          1153:        UInt16          *src, *dst;
        !          1154:        UInt16           numOffsets;
        !          1155:        
        !          1156:        src = GetOffsetAddress (btreePtr, node, node->numRecords);      // point to free offset
        !          1157:        dst = src - 1;                                                                                          // point to new offset
        !          1158:        numOffsets = node->numRecords++ - index;                        // subtract index  & postincrement
        !          1159:        
        !          1160:        do {
        !          1161:                *dst++ = *src++ + delta;                                                                // to tricky?
        !          1162:        } while (numOffsets--);
        !          1163: }
        !          1164: 
        !          1165: 
        !          1166: 
        !          1167: /*-------------------------------------------------------------------------------
        !          1168: 
        !          1169: Routine:       DeleteOffset    -       Delete an offset.
        !          1170: 
        !          1171: Function:      Delete the offset at 'index' by shifting 'index+1' through the last offset
        !          1172:                        and adjusting them by the size of the record 'index'.
        !          1173:                        The number of records contained in the node is also decremented.
        !          1174: 
        !          1175: Input:         btreePtr        - pointer to BTree control block
        !          1176:                        node            - pointer to node
        !          1177:                        index           - index at which to delete record
        !          1178: 
        !          1179: Result:                none
        !          1180: -------------------------------------------------------------------------------*/
        !          1181: 
        !          1182: void           DeleteOffset            (BTreeControlBlockPtr    btreePtr,
        !          1183:                                                                 NodeDescPtr                     node,
        !          1184:                                                                 UInt16                                  index )
        !          1185: {
        !          1186:        UInt16          *src, *dst;
        !          1187:        UInt16           numOffsets;
        !          1188:        UInt16           delta;
        !          1189:        
        !          1190:        dst                     = GetOffsetAddress (btreePtr, node, index);
        !          1191:        src                     = dst - 1;
        !          1192:        delta           = *src - *dst;
        !          1193:        numOffsets      = --node->numRecords - index;   // predecrement numRecords & subtract index
        !          1194:        
        !          1195:        while (numOffsets--)
        !          1196:        {
        !          1197:                *--dst = *--src - delta;                                // work our way left
        !          1198:        }
        !          1199: }
        !          1200: 
        !          1201: 
        !          1202: 
        !          1203: /*-------------------------------------------------------------------------------
        !          1204: 
        !          1205: Routine:       MoveRecordsLeft -       Move records left within a node.
        !          1206: 
        !          1207: Function:      Moves a number of bytes from src to dst. Safely handles overlapping
        !          1208:                        ranges if the bytes are being moved to the "left". No bytes are moved
        !          1209:                        if bytesToMove is zero.
        !          1210: 
        !          1211: Input:         src                             - pointer to source
        !          1212:                        dst                             - pointer to destination
        !          1213:                        bytesToMove             - number of bytes to move records
        !          1214: 
        !          1215: Result:                none
        !          1216: -------------------------------------------------------------------------------*/
        !          1217: #if 0
        !          1218: void           MoveRecordsLeft         (UInt8 *                                 src,
        !          1219:                                                                 UInt8 *                                 dst,
        !          1220:                                                                 UInt16                                  bytesToMove )
        !          1221: {
        !          1222:        while (bytesToMove--)
        !          1223:                *dst++ = *src++;
        !          1224: }
        !          1225: #endif                                                  
        !          1226: 
        !          1227: 
        !          1228: /*-------------------------------------------------------------------------------
        !          1229: 
        !          1230: Routine:       MoveRecordsRight        -       Move records right within a node.
        !          1231: 
        !          1232: Function:      Moves a number of bytes from src to dst. Safely handles overlapping
        !          1233:                        ranges if the bytes are being moved to the "right". No bytes are moved
        !          1234:                        if bytesToMove is zero.
        !          1235: 
        !          1236: Input:         src                             - pointer to source
        !          1237:                        dst                             - pointer to destination
        !          1238:                        bytesToMove             - number of bytes to move records
        !          1239:                        
        !          1240: Result:                none
        !          1241: -------------------------------------------------------------------------------*/
        !          1242: #if 0
        !          1243: void           MoveRecordsRight        (UInt8 *                                 src,
        !          1244:                                                                 UInt8 *                                 dst,
        !          1245:                                                                 UInt16                                  bytesToMove )
        !          1246: {
        !          1247:        src += bytesToMove;
        !          1248:        dst += bytesToMove;
        !          1249:        
        !          1250:        while (bytesToMove--)
        !          1251:                *--dst = *--src;
        !          1252: }
        !          1253: #endif

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