Return to BTree.c CVS log

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

Annotation of XNU/bsd/hfs/hfscommon/BTree/BTree.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:           BTree.c
        !            24: 
        !            25:        Contains:       Implementation of public interface routines for B-tree manager.
        !            26: 
        !            27:        Version:        HFS Plus 1.0
        !            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:                (DSH)   Deric Horn
        !            45:                (djb)   Don Brady
        !            46: 
        !            47:        Change History (most recent first):
        !            48:          <MOSXS>        9/22/99        ser             Added routines  BTGetLastSync and BTSetLastSync
        !            49:           <MOSXS>        6/1/99        djb             Sync up with Mac OS 8.6.
        !            50:           <MOSXS>       6/30/98        djb             In BTOpenPath make sure nodes are contiguous on disk (radar #2249539).
        !            51:           <MOSXS>       4/15/98        djb             In BTOpenPath need to clear nodeRec.buffer if GetBlockProc fails.
        !            52:           <MOSXS>       4/11/98        djb             Add RequireFileLock checking to all external entry points.
        !            53: 
        !            54:           <MOSXS>      03/23/98        djb             In BTOpenPath use kTrashBlock option when releasing the header so
        !            55:                                                                        that we get a full node when we call GetNode. 
        !            56: 
        !            57:           <CS9>        12/12/97        djb             Radar #2202682, BTIterateRecord with kBTreeCurrentRecord was not
        !            58:                                                                        checking if we had a record and could call BlockMove with an
        !            59:                                                                        uninitialize source pointer (causing a bus error).
        !            60:           <CS8>        10/24/97        msd             In BTIterateRecord, when moving to the previous or next record
        !            61:                                                                        and we have to move to another node, see if we need to release
        !            62:                                                                        the node about to be "shifted out" (opposite sibling of the
        !            63:                                                                        direction we need to move).
        !            64:           <CS7>         7/25/97        DSH             BTSearchRecord now takes a heuristicHint, nodeNum, and tries it
        !            65:                                                                        before calling SearchBTree
        !            66:           <CS6>         7/24/97        djb             GetBlockProc now take a file refnum instead of an FCB ptr.
        !            67:           <CS5>         7/22/97        djb             Move trace points from BTreeWrapper.c to here.
        !            68:           <CS4>         7/21/97        djb             LogEndTime now takes an error code.
        !            69:           <CS3>         7/16/97        DSH             FilesInternal.i renamed FileMgrInternal.i to avoid name
        !            70:                                                                        collision
        !            71:           <CS2>         5/19/97        djb             Add summary traces to BTIterateRecord.
        !            72:           <CS1>         4/23/97        djb             first checked in
        !            73: 
        !            74:          <HFS7>         2/19/97        djb             Enable variable sized index keys for HFS+ volumes. Added node
        !            75:                                                                        cache to support nodes larger than 512 bytes.
        !            76:          <HFS6>         1/27/97        djb             Calls to InsertTree and DeleteTree are now recursive (to support
        !            77:                                                                        variable sized index keys).
        !            78:          <HFS5>         1/13/97        djb             Added support for getting current record to BTIterateRecord.
        !            79:          <HFS4>          1/6/97        djb             Initialize "BigKeys" attribute in BTOpen.
        !            80:          <HFS3>          1/3/97        djb             Added support for large keys.
        !            81:          <HFS2>        12/23/96        djb             On exit map fsBTEmptyErr and fsBTEndOfIterationErr to
        !            82:                                                                        fsBTRecordNotFoundErr.
        !            83:          <HFS1>        12/19/96        djb             first checked in
        !            84: 
        !            85:        History applicable to original Scarecrow Design:
        !            86: 
        !            87:                <13>    10/25/96        ser             Changing for new VFPI
        !            88:                <12>    10/18/96        ser             Converting over VFPI changes
        !            89:                <11>     9/17/96        dkh             More BTree statistics. Modified hint checks to not bail out when
        !            90:                                                                        an error is returned from GetNode.
        !            91:                <10>     9/16/96        dkh             Revised BTree statistics.
        !            92:                 <9>     8/23/96        dkh             Remove checks for multiple paths to BTree file. Need to add
        !            93:                                                                        equivalent mechanism later.
        !            94:                 <8>     6/20/96        dkh             Radar #1358740. Switch from using Pools to debug MemAllocators.
        !            95:                 <7>     3/14/96        jev             Fix BTreeSetRecord, recordFound was not set for the case of a
        !            96:                                                                        simple replace causing the leafRecords count to get bumped even
        !            97:                                                                        though we didn't have to add a record.
        !            98:                 <6>      3/1/96        prp             Fix lint problems. Bug in BTSetRecord that does not initialize
        !            99:                                                                        recordFound.
        !           100:                 <5>     1/22/96        dkh             Add #include Memory.h
        !           101:                 <4>     1/10/96        msd             Use the real function names from Math64.i.
        !           102:                 <3>      1/4/96        jev             Fix BTItererateRecord for the condition when the iterator
        !           103:                                                                        position routine does not find the record and we are looking for
        !           104:                                                                        the next record. In such a case, if the node's forrward link is
        !           105:                                                                        non-zero, we have to keep iterating next and not return
        !           106:                                                                        fsBTEndOfIterationErr error.
        !           107:                 <2>     12/7/95        dkh             D10E2 build. Changed usage of Ref data type to LogicalAddress.
        !           108:                 <1>    10/18/95        rst             Moved from Scarecrow project.
        !           109: 
        !           110:                <24>     7/18/95        mbb             Change MoveData & ClearBytes to BlockMoveData & BlockZero.
        !           111:                <23>     1/31/95        prp             GetBlockProc interface uses a 64 bit node number.
        !           112:                <22>     1/12/95        wjk             Adopt Model FileSystem changes in D5.
        !           113:                <21>    11/16/94        prp             Add IsItAHint routine and use it whenever hint's node number was
        !           114:                                                                        used for testing.
        !           115:                <20>    11/10/94        prp             BTGetInfo name collides with the same name in FileManagerPriv.i.
        !           116:                                                                        Change it to BTGetInformation.
        !           117:                <19>     9/30/94        prp             Get in sync with D2 interface changes.
        !           118:                <18>     7/22/94        wjk             Convert to the new set of header files.
        !           119:                <17>     12/9/93        wjk             Cleanup usage of char, Byte, int8, UInt8, etc.
        !           120:                <16>     12/2/93        wjk             Move from Makefiles to BuildFiles. Fit into the ModernOS and
        !           121:                                                                        NRCmds environments.
        !           122:                <15>    11/30/93        wjk             Move from Makefiles to BuildFiles. Fit into the ModernOS and
        !           123:                                                                        NRCmds environments.
        !           124:                <14>     9/30/93        gs              Rename E_NoGetNodeProc and E_NoReleaseNodeProc to
        !           125:                                                                        E_NoXxxxBlockProc.
        !           126:                <13>     8/31/93        prp             Use Set64U instead of Set64.
        !           127:                <12>     8/16/93        prp             In BTSearchRecord, if the input hint found the node and record,
        !           128:                                                                        set the local nodeNum variable correctly so that the resultant
        !           129:                                                                        iterator gets set correctly.
        !           130:                <11>      7/1/93        gs              Fix bug in BTIterateRecord related to kBTreePrevRecord
        !           131:                                                                        operation.
        !           132:                <10>      6/2/93        gs              Update for changes to FSErrors.h and add some comments.
        !           133:                 <9>     5/24/93        gs              Fix bug in BTInsert/Set/ReplaceRecord which didn't set node hint
        !           134:                                                                        properly in some cases.
        !           135:                 <8>     5/24/93        gs              Do NOT map fsBTEmptyErr to fsBTRecordNotFoundErr in BTSearchRecord.
        !           136:                 <7>     5/24/93        gs              Rename BTFlush to BTFlushPath.
        !           137:                 <6>     5/21/93        gs              Add hint optimization to Set/Replace routines.
        !           138:                 <5>     5/10/93        gs              Remove Panic from BTInitialize for small logicalEOF. Implement
        !           139:                                                                        Insert, Set, Replace, and Delete.
        !           140:                 <4>     3/23/93        gs              Finish BTInitialize.
        !           141:                 <3>      2/8/93        gs              Implement BTSearchRecord and BTIterateRecord.
        !           142:                 <2>     12/8/92        gs              Implement Open and Close routines.
        !           143:                 <1>    11/15/92        gs              first checked in
        !           144: 
        !           145: */
        !           146: 
        !           147: #include "../headers/BTreesPrivate.h"
        !           148: 
        !           149: #include "../headers/HFSInstrumentation.h"
        !           150: 
        !           151: 
        !           152: //////////////////////////////////// Globals ////////////////////////////////////
        !           153: 
        !           154: 
        !           155: /////////////////////////// BTree Module Entry Points ///////////////////////////
        !           156: 
        !           157: 
        !           158: 
        !           159: /*-------------------------------------------------------------------------------
        !           160: Routine:       BTOpenPath      -       Open a file for access as a B*Tree.
        !           161: 
        !           162: Function:      Create BTree control block for a file, if necessary. Validates the
        !           163:                        file to be sure it looks like a BTree file.
        !           164: 
        !           165: 
        !           166: Input:         filePtr                         - pointer to file to open as a B-tree
        !           167:                        keyCompareProc          - pointer to client's KeyCompare function
        !           168:                        getBlockProc            - pointer to client's GetBlock function
        !           169:                        releaseBlockProc        - pointer to client's ReleaseBlock function
        !           170:                        setEndOfForkProc        - pointer to client's SetEOF function
        !           171: 
        !           172: Result:                noErr                           - success
        !           173:                        paramErr                        - required ptr was nil
        !           174:                        fsBTInvalidFileErr                              -
        !           175:                        memFullErr                      -
        !           176:                        != noErr                        - failure
        !           177: -------------------------------------------------------------------------------*/
        !           178: 
        !           179: OSStatus       BTOpenPath                      (FCB                                    *filePtr,
        !           180:                                                                 KeyCompareProcPtr               keyCompareProc,
        !           181:                                                                 GetBlockProcPtr                 getBlockProc,
        !           182:                                                                 ReleaseBlockProcPtr     releaseBlockProc,
        !           183:                                                                 SetEndOfForkProcPtr     setEndOfForkProc,
        !           184:                                                                 SetBlockSizeProcPtr     setBlockSizeProc )
        !           185: {
        !           186:        OSStatus                                err;
        !           187:        BTreeControlBlockPtr    btreePtr;
        !           188:        BTHeaderRec                             *header;
        !           189:        NodeRec                                 nodeRec;
        !           190: 
        !           191:        LogStartTime(kTraceOpenBTree);
        !           192: 
        !           193:        ////////////////////// Preliminary Error Checking ///////////////////////////
        !           194: 
        !           195:        if ( filePtr == nil                             ||
        !           196:                 getBlockProc == nil            ||
        !           197:                 releaseBlockProc == nil        ||
        !           198:                 setEndOfForkProc == nil        ||
        !           199:                 setBlockSizeProc == nil )
        !           200:        {
        !           201:                return  paramErr;
        !           202:        }
        !           203: 
        !           204:        if ( filePtr->fcbBTCBPtr != nil )                       // already has a BTreeCB
        !           205:                return noErr;
        !           206: 
        !           207:                                                                                                // is file large enough to contain header node?
        !           208:        if ( filePtr->fcbEOF < kMinNodeSize )
        !           209:                return fsBTInvalidFileErr;                                                      //�� or E_BadHeader?
        !           210: 
        !           211: 
        !           212:        //////////////////////// Allocate Control Block /////////////////////////////
        !           213: 
        !           214:        btreePtr = (BTreeControlBlock*) NewPtrSysClear( sizeof( BTreeControlBlock ) );
        !           215:        if (btreePtr == nil)
        !           216:        {
        !           217:                Panic ("\pBTOpen: no memory for btreePtr.");
        !           218:                return  memFullErr;
        !           219:        }
        !           220: 
        !           221:        btreePtr->getBlockProc          = getBlockProc;
        !           222:        btreePtr->releaseBlockProc      = releaseBlockProc;
        !           223:        btreePtr->setEndOfForkProc      = setEndOfForkProc;
        !           224:        btreePtr->keyCompareProc        = keyCompareProc;
        !           225: 
        !           226:        /////////////////////////// Read Header Node ////////////////////////////////
        !           227: 
        !           228:        nodeRec.buffer                          = nil;                          // so we can call ReleaseNode
        !           229:        nodeRec.blockSize                       = kMinNodeSize;
        !           230:        btreePtr->fileRefNum            = GetFileRefNumFromFCB(filePtr);
        !           231:        filePtr->fcbBTCBPtr                     = (Ptr) btreePtr;       // attach btree cb to file
        !           232: 
        !           233:        RequireFileLock(btreePtr->fileRefNum, false);
        !           234: 
        !           235:        // it is now safe to call M_ExitOnError (err)
        !           236: 
        !           237:        err = setBlockSizeProc (btreePtr->fileRefNum, kMinNodeSize, 1);
        !           238:        M_ExitOnError (err);
        !           239: 
        !           240: 
        !           241:        err = getBlockProc (btreePtr->fileRefNum,
        !           242:                                                kHeaderNodeNum,
        !           243:                                                kGetBlock,
        !           244:                                                &nodeRec );
        !           245:        if (err != noErr)
        !           246:        {
        !           247:                nodeRec.buffer = nil;
        !           248:                nodeRec.blockHeader     = nil;
        !           249:                Panic("\pBTOpen: getNodeProc returned error getting header node.");
        !           250:                goto ErrorExit;
        !           251:        }
        !           252: 
        !           253:        header = (BTHeaderRec*) ((u_long)nodeRec.buffer + sizeof(BTNodeDescriptor));
        !           254: 
        !           255: 
        !           256:        ///////////////////////////// verify header /////////////////////////////////
        !           257: 
        !           258:        err = VerifyHeader (filePtr, header);
        !           259:        M_ExitOnError (err);
        !           260: 
        !           261: 
        !           262:        ///////////////////// Initalize fields from header //////////////////////////
        !           263:        
        !           264:     PanicIf ( (FCBTOVCB(filePtr)->vcbSigWord != 0x4244) && (header->nodeSize == 512), "\p BTOpenPath: wrong node size for HFS+ volume!");      // 0x4244 = 'BD'
        !           265: 
        !           266:        btreePtr->treeDepth                     = header->treeDepth;
        !           267:        btreePtr->rootNode                      = header->rootNode;
        !           268:        btreePtr->leafRecords           = header->leafRecords;
        !           269:        btreePtr->firstLeafNode         = header->firstLeafNode;
        !           270:        btreePtr->lastLeafNode          = header->lastLeafNode;
        !           271:        btreePtr->nodeSize                      = header->nodeSize;
        !           272:        btreePtr->maxKeyLength          = header->maxKeyLength;
        !           273:        btreePtr->totalNodes            = header->totalNodes;
        !           274:        btreePtr->freeNodes                     = header->freeNodes;
        !           275:        // ignore                                         header->clumpSize;    //�� rename this field?
        !           276:        btreePtr->btreeType                     = header->btreeType;
        !           277: 
        !           278:        btreePtr->attributes            = header->attributes;
        !           279: 
        !           280:        if ( btreePtr->maxKeyLength > 40 )
        !           281:                btreePtr->attributes |= (kBTBigKeysMask + kBTVariableIndexKeysMask);    //�� we need a way to save these attributes
        !           282: 
        !           283:        /////////////////////// Initialize dynamic fields ///////////////////////////
        !           284: 
        !           285:        btreePtr->version                       = kBTreeVersion;
        !           286:        btreePtr->flags                         = 0;
        !           287:        btreePtr->writeCount            = 1;
        !           288: 
        !           289:        btreePtr->numGetNodes           = 1;            // for earlier call to getNodeProc
        !           290: 
        !           291:        /////////////////////////// Check Header Node ///////////////////////////////
        !           292: 
        !           293:        //�� set kBadClose attribute bit, and UpdateNode
        !           294: 
        !           295:        // if nodeSize is 512 then we don't need to release, just CheckNode
        !           296: 
        !           297:        if ( btreePtr->nodeSize == kMinNodeSize )
        !           298:        {
        !           299:                err = CheckNode (btreePtr, nodeRec.buffer);
        !           300:                if (err)
        !           301:                        VTOVCB(btreePtr->fileRefNum)->vcbFlags |= kHFS_DamagedVolume;
        !           302:                M_ExitOnError (err);
        !           303:        }
        !           304:        else
        !           305:        {
        !           306:                err = setBlockSizeProc (btreePtr->fileRefNum, btreePtr->nodeSize, 32);  //���we should try and get this down to 8
        !           307:                M_ExitOnError (err);
        !           308: 
        !           309:                /*
        !           310:                 * Need to use kTrashBlock option to force the
        !           311:                 * buffer cache to read the entire node
        !           312:                 */
        !           313:                err = releaseBlockProc(btreePtr->fileRefNum, &nodeRec, kTrashBlock);
        !           314:                M_ExitOnError (err);
        !           315: 
        !           316:                err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec );            // calls CheckNode...
        !           317:                M_ExitOnError (err);
        !           318:        }
        !           319: 
        !           320:        //�� total nodes * node size <= LEOF?
        !           321: 
        !           322: 
        !           323:        err = ReleaseNode (btreePtr, &nodeRec);
        !           324:        M_ExitOnError (err);
        !           325: 
        !           326:        /*
        !           327:         * Under Mac OS, b-tree nodes can be non-contiguous on disk when the
        !           328:         * allocation block size is smaller than the b-tree node size.
        !           329:         */
        !           330:        if ( !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) )
        !           331:                return fsBTInvalidNodeErr;
        !           332: 
        !           333:        //////////////////////////////// Success ////////////////////////////////////
        !           334: 
        !           335:        //�� align LEOF to multiple of node size?       - just on close
        !           336: 
        !           337:        LogEndTime(kTraceOpenBTree, noErr);
        !           338: 
        !           339:        return noErr;
        !           340: 
        !           341: 
        !           342:        /////////////////////// Error - Clean up and Exit ///////////////////////////
        !           343: 
        !           344: ErrorExit:
        !           345: 
        !           346:        filePtr->fcbBTCBPtr = nil;
        !           347:        (void) ReleaseNode (btreePtr, &nodeRec);
        !           348:        DisposePtr( (Ptr) btreePtr );
        !           349: 
        !           350:        LogEndTime(kTraceOpenBTree, err);
        !           351: 
        !           352:        return err;
        !           353: }
        !           354: 
        !           355: 
        !           356: 
        !           357: /*-------------------------------------------------------------------------------
        !           358: Routine:       BTClosePath     -       Flush BTree Header and Deallocate Memory for BTree.
        !           359: 
        !           360: Function:      Flush the BTreeControlBlock fields to header node, and delete BTree control
        !           361:                        block and key descriptor associated with the file if filePtr is last
        !           362:                        path of type kBTreeType ('btre').
        !           363: 
        !           364: 
        !           365: Input:         filePtr         - pointer to file to delete BTree control block for.
        !           366: 
        !           367: Result:                noErr                   - success
        !           368:                        fsBTInvalidFileErr      -
        !           369:                        != noErr                - failure
        !           370: -------------------------------------------------------------------------------*/
        !           371: 
        !           372: OSStatus       BTClosePath                     (FCB                                    *filePtr)
        !           373: {
        !           374:        OSStatus                                err;
        !           375:        BTreeControlBlockPtr    btreePtr;
        !           376: 
        !           377:        LogStartTime(kTraceCloseBTree);
        !           378: 
        !           379:        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        !           380: 
        !           381:        if (btreePtr == nil)
        !           382:                return fsBTInvalidFileErr;
        !           383: 
        !           384:        RequireFileLock(btreePtr->fileRefNum, false);
        !           385: 
        !           386:        ////////////////////// Check for other BTree Paths //////////////////////////
        !           387: 
        !           388:        btreePtr->attributes &= ~kBTBadCloseMask;               // clear "bad close" attribute bit
        !           389:        err = UpdateHeader (btreePtr);
        !           390:        M_ExitOnError (err);
        !           391: 
        !           392:        DisposePtr( (Ptr) btreePtr );
        !           393:        filePtr->fcbBTCBPtr = nil;
        !           394: 
        !           395:        LogEndTime(kTraceCloseBTree, noErr);
        !           396: 
        !           397:        return  noErr;
        !           398: 
        !           399:        /////////////////////// Error - Clean Up and Exit ///////////////////////////
        !           400: 
        !           401: ErrorExit:
        !           402: 
        !           403:        LogEndTime(kTraceCloseBTree, err);
        !           404: 
        !           405:        return  err;
        !           406: }
        !           407: 
        !           408: 
        !           409: 
        !           410: /*-------------------------------------------------------------------------------
        !           411: Routine:       BTSearchRecord  -       Search BTree for a record with a matching key.
        !           412: 
        !           413: Function:      Search for position in B*Tree indicated by searchKey. If a valid node hint
        !           414:                        is provided, it will be searched first, then SearchTree will be called.
        !           415:                        If a BTreeIterator is provided, it will be set to the position found as
        !           416:                        a result of the search. If a record exists at that position, and a BufferDescriptor
        !           417:                        is supplied, the record will be copied to the buffer (as much as will fit),
        !           418:                        and recordLen will be set to the length of the record.
        !           419: 
        !           420:                        If an error other than fsBTRecordNotFoundErr occurs, the BTreeIterator, if any,
        !           421:                        is invalidated, and recordLen is set to 0.
        !           422: 
        !           423: 
        !           424: Input:         pathPtr                 - pointer to path for BTree file.
        !           425:                        searchKey               - pointer to search key to match.
        !           426:                        hintPtr                 - pointer to hint (may be nil)
        !           427: 
        !           428: Output:                record                  - pointer to BufferDescriptor containing record
        !           429:                        recordLen               - length of data at recordPtr
        !           430:                        iterator                - pointer to BTreeIterator indicating position result of search
        !           431: 
        !           432: Result:                noErr                   - success, record contains copy of record found
        !           433:                        fsBTRecordNotFoundErr   - record was not found, no data copied
        !           434:                        fsBTInvalidFileErr      - no BTreeControlBlock is allocated for the fork
        !           435:                        fsBTInvalidKeyLengthErr         -
        !           436:                        != noErr                - failure
        !           437: -------------------------------------------------------------------------------*/
        !           438: 
        !           439: OSStatus       BTSearchRecord          (FCB                                            *filePtr,
        !           440:                                                                 BTreeIterator                          *searchIterator,
        !           441:                                                                 UInt32                                         heuristicHint,
        !           442:                                                                 FSBufferDescriptor                     *record,
        !           443:                                                                 UInt16                                         *recordLen,
        !           444:                                                                 BTreeIterator                          *resultIterator )
        !           445: {
        !           446:        OSStatus                                err;
        !           447:        BTreeControlBlockPtr    btreePtr;
        !           448:        TreePathTable                   treePathTable;
        !           449:        UInt32                                  nodeNum;
        !           450:        BlockDescriptor                 node;
        !           451:        UInt16                                  index;
        !           452:        BTreeKeyPtr                             keyPtr;
        !           453:        RecordPtr                               recordPtr;
        !           454:        UInt16                                  len;
        !           455:        Boolean                                 foundRecord;
        !           456:        Boolean                                 validHint;
        !           457: 
        !           458: 
        !           459:        LogStartTime(kTraceSearchBTree);
        !           460: 
        !           461:        if (filePtr == nil)                                                                     return  paramErr;
        !           462:        if (searchIterator == nil)                                                      return  paramErr;
        !           463: 
        !           464:        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        !           465:        if (btreePtr == nil)                                                            return  fsBTInvalidFileErr;
        !           466: 
        !           467:        RequireFileLock(btreePtr->fileRefNum, true);
        !           468: 
        !           469:        foundRecord = false;
        !           470: 
        !           471:        ////////////////////////////// Take A Hint //////////////////////////////////
        !           472: 
        !           473:        err = IsItAHint (btreePtr, searchIterator, &validHint);
        !           474:        M_ExitOnError (err);
        !           475: 
        !           476:        if (validHint)
        !           477:        {
        !           478:                nodeNum = searchIterator->hint.nodeNum;
        !           479:                
        !           480:                err = GetNode (btreePtr, nodeNum, &node);
        !           481:                if( err == noErr )
        !           482:                {
        !           483:                        if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode &&
        !           484:                                 ((BTNodeDescriptor*) node.buffer)->numRecords  >  0 )
        !           485:                        {
        !           486:                                foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
        !           487: 
        !           488:                                //�� if !foundRecord, we could still skip tree search if ( 0 < index < numRecords )
        !           489:                        }
        !           490: 
        !           491:                        if (foundRecord == false)
        !           492:                        {
        !           493:                                err = ReleaseNode (btreePtr, &node);
        !           494:                                M_ExitOnError (err);
        !           495:                        }
        !           496:                        else
        !           497:                        {
        !           498:                                ++btreePtr->numValidHints;
        !           499:                        }
        !           500:                }
        !           501:                
        !           502:                if( foundRecord == false )
        !           503:                        (void) BTInvalidateHint( searchIterator );
        !           504:        }
        !           505: 
        !           506:        ////////////////////////////// Try the heuristicHint //////////////////////////////////
        !           507: 
        !           508:        if ( (foundRecord == false) && (heuristicHint != kInvalidMRUCacheKey) && (nodeNum != heuristicHint) )
        !           509:        {
        !           510:                LogStartTime(kHeuristicHint);
        !           511:                nodeNum = heuristicHint;
        !           512:                
        !           513:                err = GetNode (btreePtr, nodeNum, &node);
        !           514:                if( err == noErr )
        !           515:                {
        !           516:                        if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode &&
        !           517:                                 ((BTNodeDescriptor*) node.buffer)->numRecords  >  0 )
        !           518:                        {
        !           519:                                foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
        !           520:                        }
        !           521: 
        !           522:                        if (foundRecord == false)
        !           523:                        {
        !           524:                                err = ReleaseNode (btreePtr, &node);
        !           525:                                M_ExitOnError (err);
        !           526:                        }
        !           527:                }
        !           528:                LogEndTime(kHeuristicHint, (foundRecord == false));
        !           529:        }
        !           530: 
        !           531:        //////////////////////////// Search The Tree ////////////////////////////////
        !           532: 
        !           533:        if (foundRecord == false)
        !           534:        {
        !           535:                err = SearchTree ( btreePtr, &searchIterator->key, treePathTable, &nodeNum, &node, &index);
        !           536:                switch (err)
        !           537:                {
        !           538:                        case noErr:                     foundRecord = true;                             break;
        !           539:                        case fsBTRecordNotFoundErr:                                                                     break;
        !           540:                        default:                                goto ErrorExit;
        !           541:                }
        !           542:        }
        !           543: 
        !           544: 
        !           545:        //////////////////////////// Get the Record /////////////////////////////////
        !           546: 
        !           547:        if (foundRecord == true)
        !           548:        {
        !           549:                //XXX Should check for errors! Or BlockMove could choke on recordPtr!!!
        !           550:                GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
        !           551: 
        !           552:                if (recordLen != nil)                   *recordLen = len;
        !           553: 
        !           554:                if (record != nil)
        !           555:                {
        !           556:                        ByteCount recordSize;
        !           557: 
        !           558:                        recordSize = record->itemCount * record->itemSize;
        !           559:                        
        !           560:                        if (len > recordSize)   len = recordSize;
        !           561: 
        !           562:                        BlockMoveData (recordPtr, record->bufferAddress, len);
        !           563:                }
        !           564:        }
        !           565: 
        !           566: 
        !           567:        /////////////////////// Success - Update Iterator ///////////////////////////
        !           568: 
        !           569:        if (resultIterator != nil)
        !           570:        {
        !           571:                resultIterator->hint.writeCount = btreePtr->writeCount;
        !           572:                resultIterator->hint.nodeNum = nodeNum;
        !           573:                resultIterator->hint.index = index;
        !           574: #if DEBUG_BUILD
        !           575:                resultIterator->hint.reserved1 = 0;
        !           576:                resultIterator->hint.reserved2 = 0;
        !           577:                resultIterator->version = 0;
        !           578:                resultIterator->reserved = 0;
        !           579: #endif
        !           580:                // copy the key in the BTree when found rather than searchIterator->key to get proper case/diacriticals
        !           581:                if (foundRecord == true)
        !           582:                        BlockMoveData ((Ptr)keyPtr, (Ptr)&resultIterator->key, CalcKeySize(btreePtr, keyPtr));
        !           583:                else
        !           584:                        BlockMoveData ((Ptr)&searchIterator->key, (Ptr)&resultIterator->key, CalcKeySize(btreePtr, &searchIterator->key));
        !           585:        }
        !           586: 
        !           587:        err = ReleaseNode (btreePtr, &node);
        !           588:        M_ExitOnError (err);
        !           589: 
        !           590:        LogEndTime(kTraceSearchBTree, (foundRecord == false));
        !           591: 
        !           592:        if (foundRecord == false)       return  fsBTRecordNotFoundErr;
        !           593:        else                                            return  noErr;
        !           594: 
        !           595: 
        !           596:        /////////////////////// Error - Clean Up and Exit ///////////////////////////
        !           597: 
        !           598: ErrorExit:
        !           599: 
        !           600:        if (recordLen != nil)
        !           601:                *recordLen = 0;
        !           602: 
        !           603:        if (resultIterator != nil)
        !           604:        {
        !           605:                resultIterator->hint.writeCount = 0;
        !           606:                resultIterator->hint.nodeNum    = 0;
        !           607:                resultIterator->hint.index              = 0;
        !           608:                resultIterator->hint.reserved1  = 0;
        !           609:                resultIterator->hint.reserved2  = 0;
        !           610: 
        !           611:                resultIterator->version                 = 0;
        !           612:                resultIterator->reserved                = 0;
        !           613:                resultIterator->key.length16    = 0;    // zero out two bytes to cover both types of keys
        !           614:        }
        !           615: 
        !           616:        if ( err == fsBTEmptyErr )
        !           617:                err = fsBTRecordNotFoundErr;
        !           618: 
        !           619:        LogEndTime(kTraceSearchBTree, err);
        !           620: 
        !           621:        return err;
        !           622: }
        !           623: 
        !           624: 
        !           625: 
        !           626: /*-------------------------------------------------------------------------------
        !           627: Routine:       BTIterateRecord -       Find the first, next, previous, or last record.
        !           628: 
        !           629: Function:      Find the first, next, previous, or last record in the BTree
        !           630: 
        !           631: Input:         pathPtr                 - pointer to path iterate records for.
        !           632:                        operation               - iteration operation (first,next,prev,last)
        !           633:                        iterator                - pointer to iterator indicating start position
        !           634: 
        !           635: Output:                iterator                - iterator is updated to indicate new position
        !           636:                        newKeyPtr               - pointer to buffer to copy key found by iteration
        !           637:                        record                  - pointer to buffer to copy record found by iteration
        !           638:                        recordLen               - length of record
        !           639: 
        !           640: Result:                noErr                   - success
        !           641:                        != noErr                - failure
        !           642: -------------------------------------------------------------------------------*/
        !           643: 
        !           644: OSStatus       BTIterateRecord         (FCB                                            *filePtr,
        !           645:                                                                 BTreeIterationOperation         operation,
        !           646:                                                                 BTreeIterator                          *iterator,
        !           647:                                                                 FSBufferDescriptor                     *record,
        !           648:                                                                 UInt16                                         *recordLen )
        !           649: {
        !           650:        OSStatus                                        err;
        !           651:        BTreeControlBlockPtr            btreePtr;
        !           652:        BTreeKeyPtr                                     keyPtr;
        !           653:        RecordPtr                                       recordPtr;
        !           654:        UInt16                                          len;
        !           655: 
        !           656:        Boolean                                         foundRecord;
        !           657:        UInt32                                          nodeNum;
        !           658: 
        !           659:        BlockDescriptor                         left,           node,           right;
        !           660:        UInt16                                          index;
        !           661: 
        !           662: 
        !           663:        LogStartTime(kTraceGetBTreeRecord);
        !           664: 
        !           665:        ////////////////////////// Priliminary Checks ///////////////////////////////
        !           666: 
        !           667:        left.buffer             = nil;
        !           668:        right.buffer    = nil;
        !           669:        node.buffer             = nil;
        !           670: 
        !           671: 
        !           672:        if (filePtr == nil)
        !           673:        {
        !           674:                return  paramErr;
        !           675:        }
        !           676: 
        !           677:        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        !           678:        if (btreePtr == nil)
        !           679:        {
        !           680:                return  fsBTInvalidFileErr;                     //�� handle properly
        !           681:        }
        !           682: 
        !           683:        RequireFileLock(btreePtr->fileRefNum, true);
        !           684: 
        !           685:        if ((operation != kBTreeFirstRecord)    &&
        !           686:                (operation != kBTreeNextRecord)         &&
        !           687:                (operation != kBTreeCurrentRecord)      &&
        !           688:                (operation != kBTreePrevRecord)         &&
        !           689:                (operation != kBTreeLastRecord))
        !           690:        {
        !           691:                err = fsInvalidIterationMovmentErr;
        !           692:                goto ErrorExit;
        !           693:        }
        !           694: 
        !           695:        /////////////////////// Find First or Last Record ///////////////////////////
        !           696: 
        !           697:        if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
        !           698:        {
        !           699:                if (operation == kBTreeFirstRecord)             nodeNum = btreePtr->firstLeafNode;
        !           700:                else                                                                    nodeNum = btreePtr->lastLeafNode;
        !           701: 
        !           702:                if (nodeNum == 0)
        !           703:                {
        !           704:                        err = fsBTEmptyErr;
        !           705:                        goto ErrorExit;
        !           706:                }
        !           707: 
        !           708:                err = GetNode (btreePtr, nodeNum, &node);
        !           709:                M_ExitOnError (err);
        !           710: 
        !           711:                if ( ((NodeDescPtr) node.buffer)->kind != kBTLeafNode ||
        !           712:                         ((NodeDescPtr) node.buffer)->numRecords <=  0 )
        !           713:                {
        !           714:                        err = ReleaseNode (btreePtr, &node);
        !           715:                        M_ExitOnError (err);
        !           716: 
        !           717:                        err = fsBTInvalidNodeErr;
        !           718:                        goto ErrorExit;
        !           719:                }
        !           720: 
        !           721:                if (operation == kBTreeFirstRecord)             index = 0;
        !           722:                else                                                                    index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1;
        !           723: 
        !           724:                goto CopyData;                                          //�� is there a cleaner way?
        !           725:        }
        !           726: 
        !           727: 
        !           728:        //////////////////////// Find Iterator Position /////////////////////////////
        !           729: 
        !           730:        err = FindIteratorPosition (btreePtr, iterator,
        !           731:                                                                &left, &node, &right, &nodeNum, &index, &foundRecord);
        !           732:        M_ExitOnError (err);
        !           733: 
        !           734: 
        !           735:        ///////////////////// Find Next Or Previous Record //////////////////////////
        !           736: 
        !           737:        if (operation == kBTreePrevRecord)
        !           738:        {
        !           739:                if (index > 0)
        !           740:                {
        !           741:                        --index;
        !           742:                }
        !           743:                else
        !           744:                {
        !           745:                        if (left.buffer == nil)
        !           746:                        {
        !           747:                                nodeNum = ((NodeDescPtr) node.buffer)->bLink;
        !           748:                                if ( nodeNum > 0)
        !           749:                                {
        !           750:                                        err = GetNode (btreePtr, nodeNum, &left);
        !           751:                                        M_ExitOnError (err);
        !           752:                                } else {
        !           753:                                        err = fsBTStartOfIterationErr;
        !           754:                                        goto ErrorExit;
        !           755:                                }
        !           756:                        }
        !           757:                        //      Before we stomp on "right", we'd better release it if needed
        !           758:                        if (right.buffer != nil) {
        !           759:                                err = ReleaseNode(btreePtr, &right);
        !           760:                                M_ExitOnError(err);
        !           761:                        }
        !           762:                        right           = node;
        !           763:                        node            = left;
        !           764:                        left.buffer     = nil;
        !           765:                        index           = ((NodeDescPtr) node.buffer)->numRecords -1;
        !           766:                }
        !           767:        }
        !           768:        else if (operation == kBTreeNextRecord)
        !           769:        {
        !           770:                if ((foundRecord != true) &&
        !           771:                        (((NodeDescPtr) node.buffer)->fLink == 0) &&
        !           772:                        (index == ((NodeDescPtr) node.buffer)->numRecords))
        !           773:                {
        !           774:                        err = fsBTEndOfIterationErr;
        !           775:                        goto ErrorExit;
        !           776:                } 
        !           777:        
        !           778:                // we did not find the record but the index is already positioned correctly
        !           779:                if ((foundRecord == false) && (index != ((NodeDescPtr) node.buffer)->numRecords)) 
        !           780:                        goto CopyData;
        !           781: 
        !           782:                // we found the record OR we have to look in the next node
        !           783:                if (index < ((NodeDescPtr) node.buffer)->numRecords -1)
        !           784:                {
        !           785:                        ++index;
        !           786:                }
        !           787:                else
        !           788:                {
        !           789:                        if (right.buffer == nil)
        !           790:                        {
        !           791:                                nodeNum = ((NodeDescPtr) node.buffer)->fLink;
        !           792:                                if ( nodeNum > 0)
        !           793:                                {
        !           794:                                        err = GetNode (btreePtr, nodeNum, &right);
        !           795:                                        M_ExitOnError (err);
        !           796:                                } else {
        !           797:                                        err = fsBTEndOfIterationErr;
        !           798:                                        goto ErrorExit;
        !           799:                                }
        !           800:                        }
        !           801:                        //      Before we stomp on "left", we'd better release it if needed
        !           802:                        if (left.buffer != nil) {
        !           803:                                err = ReleaseNode(btreePtr, &left);
        !           804:                                M_ExitOnError(err);
        !           805:                        }
        !           806:                        left             = node;
        !           807:                        node             = right;
        !           808:                        right.buffer = nil;
        !           809:                        index            = 0;
        !           810:                }
        !           811:        }
        !           812:        else // operation == kBTreeCurrentRecord
        !           813:        {
        !           814:                // make sure we have something... <CS9>
        !           815:                if ((foundRecord != true) &&
        !           816:                        (index >= ((NodeDescPtr) node.buffer)->numRecords))
        !           817:                {
        !           818:                        err = fsBTEndOfIterationErr;
        !           819:                        goto ErrorExit;
        !           820:                } 
        !           821:        }
        !           822: 
        !           823:        //////////////////// Copy Record And Update Iterator ////////////////////////
        !           824: 
        !           825: CopyData:
        !           826: 
        !           827:        // added check for errors <CS9>
        !           828:        err = GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
        !           829:        M_ExitOnError (err);
        !           830: 
        !           831:        if (recordLen != nil)
        !           832:                *recordLen = len;
        !           833: 
        !           834:        if (record != nil)
        !           835:        {
        !           836:                ByteCount recordSize;
        !           837: 
        !           838:                recordSize = record->itemCount * record->itemSize;
        !           839:        
        !           840:                if (len > recordSize)   len = recordSize;
        !           841: 
        !           842:                BlockMoveData (recordPtr, record->bufferAddress, len);
        !           843:        }
        !           844: 
        !           845:        if (iterator != nil)                                            // first & last do not require iterator
        !           846:        {
        !           847:                iterator->hint.writeCount       = btreePtr->writeCount;
        !           848:                iterator->hint.nodeNum          = nodeNum;
        !           849:                iterator->hint.index            = index;
        !           850:                iterator->hint.reserved1        = 0;
        !           851:                iterator->hint.reserved2        = 0;
        !           852: 
        !           853:                iterator->version                       = 0;
        !           854:                iterator->reserved                      = 0;
        !           855: 
        !           856:                BlockMoveData ((Ptr)keyPtr, (Ptr)&iterator->key, CalcKeySize(btreePtr, keyPtr));
        !           857:        }
        !           858: 
        !           859: 
        !           860:        ///////////////////////////// Release Nodes /////////////////////////////////
        !           861: 
        !           862:        err = ReleaseNode (btreePtr, &node);
        !           863:        M_ExitOnError (err);
        !           864: 
        !           865:        if (left.buffer != nil)
        !           866:        {
        !           867:                err = ReleaseNode (btreePtr, &left);
        !           868:                M_ExitOnError (err);
        !           869:        }
        !           870: 
        !           871:        if (right.buffer != nil)
        !           872:        {
        !           873:                err = ReleaseNode (btreePtr, &right);
        !           874:                M_ExitOnError (err);
        !           875:        }
        !           876: 
        !           877:        LogEndTime(kTraceGetBTreeRecord, noErr);
        !           878: 
        !           879:        return noErr;
        !           880: 
        !           881:        /////////////////////// Error - Clean Up and Exit ///////////////////////////
        !           882: 
        !           883: ErrorExit:
        !           884: 
        !           885:        (void)  ReleaseNode (btreePtr, &left);
        !           886:        (void)  ReleaseNode (btreePtr, &node);
        !           887:        (void)  ReleaseNode (btreePtr, &right);
        !           888: 
        !           889:        if (recordLen != nil)
        !           890:                *recordLen = 0;
        !           891: 
        !           892:        if (iterator != nil)
        !           893:        {
        !           894:                iterator->hint.writeCount       = 0;
        !           895:                iterator->hint.nodeNum          = 0;
        !           896:                iterator->hint.index            = 0;
        !           897:                iterator->hint.reserved1        = 0;
        !           898:                iterator->hint.reserved2        = 0;
        !           899: 
        !           900:                iterator->version                       = 0;
        !           901:                iterator->reserved                      = 0;
        !           902:                iterator->key.length16          = 0;
        !           903:        }
        !           904: 
        !           905:        if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
        !           906:                err = fsBTRecordNotFoundErr;
        !           907: 
        !           908:        LogEndTime(kTraceGetBTreeRecord, err);
        !           909: 
        !           910:        return err;
        !           911: }
        !           912: 
        !           913: 
        !           914: /*-------------------------------------------------------------------------------
        !           915: Routine:       BTIterateRecords
        !           916: 
        !           917: Function:      Find a series of records
        !           918: 
        !           919: Input:         filePtr         - b-tree file
        !           920:                operation       - iteration operation (first,next,prev,last)
        !           921:                iterator        - pointer to iterator indicating start position
        !           922:                callBackProc    - pointer to routince to process a record
        !           923:                callBackState   - pointer to state data (used by callBackProc)
        !           924: 
        !           925: Output:                iterator        - iterator is updated to indicate new position
        !           926: 
        !           927: Result:                noErr           - success
        !           928:                != noErr        - failure
        !           929: -------------------------------------------------------------------------------*/
        !           930: 
        !           931: OSStatus
        !           932: BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator *iterator,
        !           933:                 IterateCallBackProcPtr  callBackProc, void * callBackState)
        !           934: {
        !           935:        OSStatus                err;
        !           936:        BTreeControlBlockPtr    btreePtr;
        !           937:        BTreeKeyPtr             keyPtr;
        !           938:        RecordPtr               recordPtr;
        !           939:        UInt16                  len;
        !           940:        Boolean                 foundRecord;
        !           941:        UInt32                  nodeNum;
        !           942:        BlockDescriptor         left, node, right;
        !           943:        UInt16                  index;
        !           944: 
        !           945: 
        !           946:        ////////////////////////// Priliminary Checks ///////////////////////////////
        !           947: 
        !           948:        left.buffer  = nil;
        !           949:        right.buffer = nil;
        !           950:        node.buffer  = nil;
        !           951: 
        !           952:        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        !           953: 
        !           954:        RequireFileLock(btreePtr->fileRefNum, true);
        !           955: 
        !           956:        if ((operation != kBTreeFirstRecord)    &&
        !           957:                (operation != kBTreeNextRecord)         &&
        !           958:                (operation != kBTreeCurrentRecord)      &&
        !           959:                (operation != kBTreePrevRecord)         &&
        !           960:                (operation != kBTreeLastRecord))
        !           961:        {
        !           962:                err = fsInvalidIterationMovmentErr;
        !           963:                goto ErrorExit;
        !           964:        }
        !           965: 
        !           966:        /////////////////////// Find First or Last Record ///////////////////////////
        !           967: 
        !           968:        if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
        !           969:        {
        !           970:                if (operation == kBTreeFirstRecord)
        !           971:                        nodeNum = btreePtr->firstLeafNode;
        !           972:                else
        !           973:                        nodeNum = btreePtr->lastLeafNode;
        !           974: 
        !           975:                if (nodeNum == 0)
        !           976:                {
        !           977:                        err = fsBTEmptyErr;
        !           978:                        goto ErrorExit;
        !           979:                }
        !           980: 
        !           981:                err = GetNode(btreePtr, nodeNum, &node);
        !           982:                M_ExitOnError(err);
        !           983: 
        !           984:                if ( ((NodeDescPtr)node.buffer)->kind != kBTLeafNode ||
        !           985:                         ((NodeDescPtr)node.buffer)->numRecords <=  0 )
        !           986:                {
        !           987:                        err = ReleaseNode(btreePtr, &node);
        !           988:                        M_ExitOnError(err);
        !           989: 
        !           990:                        err = fsBTInvalidNodeErr;
        !           991:                        goto ErrorExit;
        !           992:                }
        !           993: 
        !           994:                if (operation == kBTreeFirstRecord)
        !           995:                        index = 0;
        !           996:                else
        !           997:                        index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1;
        !           998: 
        !           999:                goto ProcessData;
        !          1000:        }
        !          1001: 
        !          1002:        //////////////////////// Find Iterator Position /////////////////////////////
        !          1003: 
        !          1004:        err = FindIteratorPosition(btreePtr, iterator, &left, &node, &right,
        !          1005:                                   &nodeNum, &index, &foundRecord);
        !          1006:        M_ExitOnError(err);
        !          1007: 
        !          1008: 
        !          1009:        ///////////////////// Find Next Or Previous Record //////////////////////////
        !          1010: 
        !          1011:        if (operation == kBTreePrevRecord)
        !          1012:        {
        !          1013:                if (index > 0)
        !          1014:                {
        !          1015:                        --index;
        !          1016:                }
        !          1017:                else
        !          1018:                {
        !          1019:                        if (left.buffer == nil)
        !          1020:                        {
        !          1021:                                nodeNum = ((NodeDescPtr) node.buffer)->bLink;
        !          1022:                                if ( nodeNum > 0)
        !          1023:                                {
        !          1024:                                        err = GetNode(btreePtr, nodeNum, &left);
        !          1025:                                        M_ExitOnError(err);
        !          1026:                                } else {
        !          1027:                                        err = fsBTStartOfIterationErr;
        !          1028:                                        goto ErrorExit;
        !          1029:                                }
        !          1030:                        }
        !          1031:                        // Before we stomp on "right", we'd better release it if needed
        !          1032:                        if (right.buffer != nil) {
        !          1033:                                err = ReleaseNode(btreePtr, &right);
        !          1034:                                M_ExitOnError(err);
        !          1035:                        }
        !          1036:                        right       = node;
        !          1037:                        node        = left;
        !          1038:                        left.buffer = nil;
        !          1039:                        index       = ((NodeDescPtr) node.buffer)->numRecords -1;
        !          1040:                }
        !          1041:        }
        !          1042:        else if (operation == kBTreeNextRecord)
        !          1043:        {
        !          1044:                if ((foundRecord != true) &&
        !          1045:                        (((NodeDescPtr)node.buffer)->fLink == 0) &&
        !          1046:                        (index == ((NodeDescPtr)node.buffer)->numRecords))
        !          1047:                {
        !          1048:                        err = fsBTEndOfIterationErr;
        !          1049:                        goto ErrorExit;
        !          1050:                } 
        !          1051:        
        !          1052:                // we did not find the record but the index is already positioned correctly
        !          1053:                if ((foundRecord == false) && (index != ((NodeDescPtr)node.buffer)->numRecords)) 
        !          1054:                        goto ProcessData;
        !          1055: 
        !          1056:                // we found the record OR we have to look in the next node
        !          1057:                if (index < ((NodeDescPtr)node.buffer)->numRecords -1)
        !          1058:                {
        !          1059:                        ++index;
        !          1060:                }
        !          1061:                else
        !          1062:                {
        !          1063:                        if (right.buffer == nil)
        !          1064:                        {
        !          1065:                                nodeNum = ((NodeDescPtr)node.buffer)->fLink;
        !          1066:                                if ( nodeNum > 0)
        !          1067:                                {
        !          1068:                                        err = GetNode(btreePtr, nodeNum, &right);
        !          1069:                                        M_ExitOnError(err);
        !          1070:                                } else {
        !          1071:                                        err = fsBTEndOfIterationErr;
        !          1072:                                        goto ErrorExit;
        !          1073:                                }
        !          1074:                        }
        !          1075:                        // Before we stomp on "left", we'd better release it if needed
        !          1076:                        if (left.buffer != nil) {
        !          1077:                                err = ReleaseNode(btreePtr, &left);
        !          1078:                                M_ExitOnError(err);
        !          1079:                        }
        !          1080:                        left         = node;
        !          1081:                        node         = right;
        !          1082:                        right.buffer = nil;
        !          1083:                        index        = 0;
        !          1084:                }
        !          1085:        }
        !          1086:        else // operation == kBTreeCurrentRecord
        !          1087:        {
        !          1088:                // make sure we have something... <CS9>
        !          1089:                if ((foundRecord != true) &&
        !          1090:                        (index >= ((NodeDescPtr)node.buffer)->numRecords))
        !          1091:                {
        !          1092:                        err = fsBTEndOfIterationErr;
        !          1093:                        goto ErrorExit;
        !          1094:                } 
        !          1095:        }
        !          1096: 
        !          1097:        ////////////////////  Process Records Using Callback  ////////////////////////
        !          1098: 
        !          1099: ProcessData:
        !          1100:        err = GetRecordByIndex(btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
        !          1101:        
        !          1102:        while (err == 0) {
        !          1103:                if (callBackProc(keyPtr, recordPtr, len, callBackState) == 0)
        !          1104:                        break;
        !          1105:                
        !          1106:                if ((index+1) < ((NodeDescPtr)node.buffer)->numRecords) {
        !          1107:                        ++index;
        !          1108:                } else {
        !          1109:                        if (right.buffer == nil)
        !          1110:                        {
        !          1111:                                nodeNum = ((NodeDescPtr)node.buffer)->fLink;
        !          1112:                                if ( nodeNum > 0)
        !          1113:                                {
        !          1114:                                        err = GetNode(btreePtr, nodeNum, &right);
        !          1115:                                        M_ExitOnError(err);
        !          1116:                                } else {
        !          1117:                                        err = fsBTEndOfIterationErr;
        !          1118:                                        break;
        !          1119:                                }
        !          1120:                        }
        !          1121:                        // Before we stomp on "left", we'd better release it if needed
        !          1122:                        if (left.buffer != nil) {
        !          1123:                                err = ReleaseNode(btreePtr, &left);
        !          1124:                                M_ExitOnError(err);
        !          1125:                        }
        !          1126:                        left         = node;
        !          1127:                        node         = right;
        !          1128:                        right.buffer = nil;
        !          1129:                        index        = 0;
        !          1130:                }
        !          1131:                err = GetRecordByIndex(btreePtr, node.buffer, index,
        !          1132:                                                &keyPtr, &recordPtr, &len);
        !          1133:        }
        !          1134: 
        !          1135: 
        !          1136:        ///////////////// Update Iterator to Last Item Processed /////////////////////
        !          1137: 
        !          1138: 
        !          1139:        if (iterator != nil)    // first & last have optional iterator
        !          1140:        {
        !          1141:                iterator->hint.writeCount = btreePtr->writeCount;
        !          1142:                iterator->hint.nodeNum    = nodeNum;
        !          1143:                iterator->hint.index      = index;
        !          1144:                iterator->version         = 0;
        !          1145: 
        !          1146:                BlockMoveData((Ptr)keyPtr, (Ptr)&iterator->key, CalcKeySize(btreePtr, keyPtr));
        !          1147:        }
        !          1148:        M_ExitOnError(err);
        !          1149: 
        !          1150: 
        !          1151:        ///////////////////////////// Release Nodes /////////////////////////////////
        !          1152: 
        !          1153:        err = ReleaseNode(btreePtr, &node);
        !          1154:        M_ExitOnError(err);
        !          1155: 
        !          1156:        if (left.buffer != nil)
        !          1157:        {
        !          1158:                err = ReleaseNode(btreePtr, &left);
        !          1159:                M_ExitOnError(err);
        !          1160:        }
        !          1161: 
        !          1162:        if (right.buffer != nil)
        !          1163:        {
        !          1164:                err = ReleaseNode(btreePtr, &right);
        !          1165:                M_ExitOnError(err);
        !          1166:        }
        !          1167: 
        !          1168:        return noErr;
        !          1169: 
        !          1170:        /////////////////////// Error - Clean Up and Exit ///////////////////////////
        !          1171: 
        !          1172: ErrorExit:
        !          1173: 
        !          1174:        (void) ReleaseNode(btreePtr, &left);
        !          1175:        (void) ReleaseNode(btreePtr, &node);
        !          1176:        (void) ReleaseNode(btreePtr, &right);
        !          1177: 
        !          1178:        if (iterator != nil)
        !          1179:        {
        !          1180:                iterator->hint.writeCount = 0;
        !          1181:                iterator->hint.nodeNum    = 0;
        !          1182:                iterator->hint.index      = 0;
        !          1183:                iterator->version         = 0;
        !          1184:                iterator->key.length16    = 0;
        !          1185:        }
        !          1186: 
        !          1187:        if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
        !          1188:                err = fsBTRecordNotFoundErr;
        !          1189: 
        !          1190:        return err;
        !          1191: }
        !          1192: 
        !          1193: 
        !          1194: //////////////////////////////// BTInsertRecord /////////////////////////////////
        !          1195: 
        !          1196: OSStatus       BTInsertRecord          (FCB                                            *filePtr,
        !          1197:                                                                 BTreeIterator                          *iterator,
        !          1198:                                                                 FSBufferDescriptor                     *record,
        !          1199:                                                                 UInt16                                          recordLen )
        !          1200: {
        !          1201:        OSStatus                                err;
        !          1202:        BTreeControlBlockPtr    btreePtr;
        !          1203:        TreePathTable                   treePathTable;
        !          1204:        SInt32                                  nodesNeeded;
        !          1205:        BlockDescriptor                 nodeRec;
        !          1206:        UInt32                                  insertNodeNum;
        !          1207:        UInt16                                  index;
        !          1208:        Boolean                                 recordFit;
        !          1209: 
        !          1210: 
        !          1211:        ////////////////////////// Priliminary Checks ///////////////////////////////
        !          1212: 
        !          1213:        nodeRec.buffer = nil;                                   // so we can call ReleaseNode
        !          1214: 
        !          1215:        err = CheckInsertParams (filePtr, iterator, record, recordLen);
        !          1216:        if (err != noErr)
        !          1217:                return  err;
        !          1218: 
        !          1219:        LogStartTime(kTraceInsertBTreeRecord);
        !          1220: 
        !          1221:        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        !          1222: 
        !          1223:        RequireFileLock(btreePtr->fileRefNum, false);
        !          1224: 
        !          1225: 
        !          1226:        ///////////////////////// Find Insert Position //////////////////////////////
        !          1227: 
        !          1228:        // always call SearchTree for Insert
        !          1229:        err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
        !          1230: 
        !          1231:        switch (err)                            // set/replace/insert decision point
        !          1232:        {
        !          1233:                case noErr:                     err = fsBTDuplicateRecordErr;
        !          1234:                                                                goto ErrorExit;
        !          1235: 
        !          1236:                case fsBTRecordNotFoundErr:     break;
        !          1237: 
        !          1238:                case fsBTEmptyErr:      // if tree empty add 1st leaf node
        !          1239: 
        !          1240:                                                                if (btreePtr->freeNodes == 0)
        !          1241:                                                                {
        !          1242:                                                                        err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
        !          1243:                                                                        M_ExitOnError (err);
        !          1244:                                                                }
        !          1245: 
        !          1246:                                                                err = AllocateNode (btreePtr, &insertNodeNum);
        !          1247:                                                                M_ExitOnError (err);
        !          1248: 
        !          1249:                                                                err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
        !          1250:                                                                M_ExitOnError (err);
        !          1251: 
        !          1252:                                                                ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
        !          1253:                                                                ((NodeDescPtr)nodeRec.buffer)->height   = 1;
        !          1254: 
        !          1255:                                                                recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0,
        !          1256:                                                                                                                         &iterator->key, KeyLength(btreePtr, &iterator->key),
        !          1257:                                                                                                                         record->bufferAddress, recordLen );
        !          1258:                                                                if (recordFit != true)
        !          1259:                                                                {
        !          1260:                                                                        err = fsBTRecordTooLargeErr;
        !          1261:                                                                        goto ErrorExit;
        !          1262:                                                                }
        !          1263: 
        !          1264:                                                                err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
        !          1265:                                                                M_ExitOnError (err);
        !          1266: 
        !          1267:                                                                // update BTreeControlBlock
        !          1268:                                                                btreePtr->treeDepth                     = 1;
        !          1269:                                                                btreePtr->rootNode                      = insertNodeNum;
        !          1270:                                                                btreePtr->firstLeafNode         = insertNodeNum;
        !          1271:                                                                btreePtr->lastLeafNode          = insertNodeNum;
        !          1272:                                                                M_BTreeHeaderDirty (btreePtr);
        !          1273: 
        !          1274:                                                                goto Success;
        !          1275: 
        !          1276:                default:                                goto ErrorExit;
        !          1277:        }
        !          1278: 
        !          1279:        if (index > 0)
        !          1280:        {
        !          1281:                recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
        !          1282:                                                                                &iterator->key, KeyLength(btreePtr, &iterator->key),
        !          1283:                                                                                record->bufferAddress, recordLen);
        !          1284:                if (recordFit == true)
        !          1285:                {
        !          1286:                        err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
        !          1287:                        M_ExitOnError (err);
        !          1288: 
        !          1289:                        goto Success;
        !          1290:                }
        !          1291:        }
        !          1292: 
        !          1293:        /////////////////////// Extend File If Necessary ////////////////////////////
        !          1294: 
        !          1295:        nodesNeeded =  btreePtr->treeDepth + 1 - btreePtr->freeNodes;   //�� math limit
        !          1296:        if (nodesNeeded > 0)
        !          1297:        {
        !          1298:                nodesNeeded += btreePtr->totalNodes;
        !          1299:                if (nodesNeeded > CalcMapBits (btreePtr))       // we'll need to add a map node too!
        !          1300:                        ++nodesNeeded;
        !          1301: 
        !          1302:                err = ExtendBTree (btreePtr, nodesNeeded);
        !          1303:                M_ExitOnError (err);
        !          1304:        }
        !          1305: 
        !          1306:        // no need to delete existing record
        !          1307: 
        !          1308:        err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
        !          1309:                                          recordLen, &nodeRec, index, 1, kInsertRecord, &insertNodeNum);
        !          1310:        M_ExitOnError (err);
        !          1311: 
        !          1312: 
        !          1313:        //////////////////////////////// Success ////////////////////////////////////
        !          1314: 
        !          1315: Success:
        !          1316:        ++btreePtr->writeCount;
        !          1317:        ++btreePtr->leafRecords;
        !          1318:        M_BTreeHeaderDirty (btreePtr);
        !          1319: 
        !          1320:        // create hint
        !          1321:        iterator->hint.writeCount       = btreePtr->writeCount;
        !          1322:        iterator->hint.nodeNum          = insertNodeNum;
        !          1323:        iterator->hint.index            = 0;                                            // unused
        !          1324:        iterator->hint.reserved1        = 0;
        !          1325:        iterator->hint.reserved2        = 0;
        !          1326: 
        !          1327:        LogEndTime(kTraceInsertBTreeRecord, noErr);
        !          1328: 
        !          1329:        return noErr;
        !          1330: 
        !          1331: 
        !          1332:        ////////////////////////////// Error Exit ///////////////////////////////////
        !          1333: 
        !          1334: ErrorExit:
        !          1335: 
        !          1336:        (void) ReleaseNode (btreePtr, &nodeRec);
        !          1337: 
        !          1338:        iterator->hint.writeCount       = 0;
        !          1339:        iterator->hint.nodeNum          = 0;
        !          1340:        iterator->hint.index            = 0;
        !          1341:        iterator->hint.reserved1        = 0;
        !          1342:        iterator->hint.reserved2        = 0;
        !          1343:        
        !          1344:        if (err == fsBTEmptyErr)
        !          1345:                err = fsBTRecordNotFoundErr;
        !          1346: 
        !          1347:        LogEndTime(kTraceInsertBTreeRecord, err);
        !          1348: 
        !          1349:        return err;
        !          1350: }
        !          1351: 
        !          1352: 
        !          1353: //////////////////////////////// BTReplaceRecord ////////////////////////////////
        !          1354: 
        !          1355: OSStatus       BTReplaceRecord         (FCB                                            *filePtr,
        !          1356:                                                                 BTreeIterator                          *iterator,
        !          1357:                                                                 FSBufferDescriptor                     *record,
        !          1358:                                                                 UInt16                                          recordLen )
        !          1359: {
        !          1360:        OSStatus                                err;
        !          1361:        BTreeControlBlockPtr    btreePtr;
        !          1362:        TreePathTable                   treePathTable;
        !          1363:        SInt32                                  nodesNeeded;
        !          1364:        BlockDescriptor                 nodeRec;
        !          1365:        UInt32                                  insertNodeNum;
        !          1366:        UInt16                                  index;
        !          1367:        Boolean                                 recordFit;
        !          1368:        Boolean                                 validHint;
        !          1369: 
        !          1370: 
        !          1371:        ////////////////////////// Priliminary Checks ///////////////////////////////
        !          1372: 
        !          1373:        nodeRec.buffer = nil;                                   // so we can call ReleaseNode
        !          1374: 
        !          1375:        err = CheckInsertParams (filePtr, iterator, record, recordLen);
        !          1376:        if (err != noErr)
        !          1377:                return err;
        !          1378: 
        !          1379:        LogStartTime(kTraceReplaceBTreeRecord);
        !          1380: 
        !          1381:        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        !          1382: 
        !          1383:        RequireFileLock(btreePtr->fileRefNum, false);
        !          1384: 
        !          1385:        ////////////////////////////// Take A Hint //////////////////////////////////
        !          1386: 
        !          1387:        err = IsItAHint (btreePtr, iterator, &validHint);
        !          1388:        M_ExitOnError (err);
        !          1389: 
        !          1390:        if (validHint)
        !          1391:        {
        !          1392:                insertNodeNum = iterator->hint.nodeNum;
        !          1393: 
        !          1394:                err = GetNode (btreePtr, insertNodeNum, &nodeRec);
        !          1395:                if( err == noErr )
        !          1396:                {
        !          1397:                        err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
        !          1398:                        M_ExitOnError (err);
        !          1399: 
        !          1400:                        if (recordFit)
        !          1401:                        {
        !          1402:                                err = UpdateNode (btreePtr, &nodeRec, 0, 0);
        !          1403:                                M_ExitOnError (err);
        !          1404: 
        !          1405:                                ++btreePtr->numValidHints;
        !          1406: 
        !          1407:                                goto Success;
        !          1408:                        }
        !          1409:                        else
        !          1410:                        {
        !          1411:                                (void) BTInvalidateHint( iterator );
        !          1412:                        }
        !          1413:                        
        !          1414:                        err = ReleaseNode (btreePtr, &nodeRec);
        !          1415:                        M_ExitOnError (err);
        !          1416:                }
        !          1417:                else
        !          1418:                {
        !          1419:                        (void) BTInvalidateHint( iterator );
        !          1420:                }
        !          1421:        }
        !          1422: 
        !          1423: 
        !          1424:        ////////////////////////////// Get A Clue ///////////////////////////////////
        !          1425: 
        !          1426:        err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
        !          1427:        M_ExitOnError (err);                                    // record must exit for Replace
        !          1428: 
        !          1429:        // optimization - if simple replace will work then don't extend btree
        !          1430:        // �� if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
        !          1431: 
        !          1432:        err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
        !          1433:        M_ExitOnError (err);
        !          1434: 
        !          1435:        if (recordFit)
        !          1436:        {
        !          1437:                err = UpdateNode (btreePtr, &nodeRec, 0, 0);
        !          1438:                M_ExitOnError (err);
        !          1439: 
        !          1440:                goto Success;
        !          1441:        }
        !          1442: 
        !          1443: 
        !          1444:        //////////////////////////// Make Some Room /////////////////////////////////
        !          1445: 
        !          1446:        nodesNeeded =  btreePtr->treeDepth + 1 - btreePtr->freeNodes;   //�� math limit
        !          1447:        if (nodesNeeded > 0)
        !          1448:        {
        !          1449:                nodesNeeded += btreePtr->totalNodes;
        !          1450:                if (nodesNeeded > CalcMapBits (btreePtr))       // we'll need to add a map node too!
        !          1451:                        ++nodesNeeded;
        !          1452: 
        !          1453:                err = ExtendBTree (btreePtr, nodesNeeded);
        !          1454:                M_ExitOnError (err);
        !          1455:        }
        !          1456: 
        !          1457: 
        !          1458:        DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record
        !          1459: 
        !          1460:        err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
        !          1461:                                          recordLen, &nodeRec, index, 1, kReplaceRecord, &insertNodeNum);
        !          1462:        M_ExitOnError (err);
        !          1463: 
        !          1464:        ++btreePtr->writeCount; /* writeCount changes only if the tree structure changed */
        !          1465: 
        !          1466: Success:
        !          1467:        // create hint
        !          1468:        iterator->hint.writeCount       = btreePtr->writeCount;
        !          1469:        iterator->hint.nodeNum          = insertNodeNum;
        !          1470:        iterator->hint.index            = 0;                                            // unused
        !          1471:        iterator->hint.reserved1        = 0;
        !          1472:        iterator->hint.reserved2        = 0;
        !          1473: 
        !          1474:        LogEndTime(kTraceReplaceBTreeRecord, noErr);
        !          1475: 
        !          1476:        return noErr;
        !          1477: 
        !          1478: 
        !          1479:        ////////////////////////////// Error Exit ///////////////////////////////////
        !          1480: 
        !          1481: ErrorExit:
        !          1482: 
        !          1483:        (void) ReleaseNode (btreePtr, &nodeRec);
        !          1484: 
        !          1485:        iterator->hint.writeCount       = 0;
        !          1486:        iterator->hint.nodeNum          = 0;
        !          1487:        iterator->hint.index            = 0;
        !          1488:        iterator->hint.reserved1        = 0;
        !          1489:        iterator->hint.reserved2        = 0;
        !          1490: 
        !          1491: 
        !          1492:        LogEndTime(kTraceReplaceBTreeRecord, err);
        !          1493: 
        !          1494:        return err;
        !          1495: }
        !          1496: 
        !          1497: 
        !          1498: 
        !          1499: //////////////////////////////// BTDeleteRecord /////////////////////////////////
        !          1500: 
        !          1501: OSStatus       BTDeleteRecord          (FCB                                            *filePtr,
        !          1502:                                                                 BTreeIterator                          *iterator )
        !          1503: {
        !          1504:        OSStatus                                err;
        !          1505:        BTreeControlBlockPtr    btreePtr;
        !          1506:        TreePathTable                   treePathTable;
        !          1507:        BlockDescriptor                 nodeRec;
        !          1508:        UInt32                                  nodeNum;
        !          1509:        UInt16                                  index;
        !          1510: 
        !          1511:        LogStartTime(kTraceDeleteBTreeRecord);
        !          1512: 
        !          1513:        ////////////////////////// Priliminary Checks ///////////////////////////////
        !          1514: 
        !          1515:        nodeRec.buffer = nil;                                   // so we can call ReleaseNode
        !          1516: 
        !          1517:        M_ReturnErrorIf (filePtr == nil,        paramErr);
        !          1518:        M_ReturnErrorIf (iterator == nil,       paramErr);
        !          1519: 
        !          1520:        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        !          1521:        if (btreePtr == nil)
        !          1522:        {
        !          1523:                err = fsBTInvalidFileErr;
        !          1524:                goto ErrorExit;
        !          1525:        }
        !          1526: 
        !          1527:        RequireFileLock(btreePtr->fileRefNum, false);
        !          1528: 
        !          1529: 
        !          1530:        /////////////////////////////// Find Key ////////////////////////////////////
        !          1531: 
        !          1532:        //�� check hint for simple delete case (index > 0, numRecords > 2)
        !          1533: 
        !          1534:        err = SearchTree (btreePtr, &iterator->key, treePathTable, &nodeNum, &nodeRec, &index);
        !          1535:        M_ExitOnError (err);                                    // record must exit for Delete
        !          1536: 
        !          1537: 
        !          1538:        ///////////////////////////// Delete Record /////////////////////////////////
        !          1539: 
        !          1540:        err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
        !          1541:        M_ExitOnError (err);
        !          1542: 
        !          1543:        ++btreePtr->writeCount;
        !          1544:        --btreePtr->leafRecords;
        !          1545:        M_BTreeHeaderDirty (btreePtr);
        !          1546: 
        !          1547:        iterator->hint.nodeNum  = 0;
        !          1548: 
        !          1549:        LogEndTime(kTraceDeleteBTreeRecord, noErr);
        !          1550: 
        !          1551:        return noErr;
        !          1552: 
        !          1553:        ////////////////////////////// Error Exit ///////////////////////////////////
        !          1554: 
        !          1555: ErrorExit:
        !          1556:        (void) ReleaseNode (btreePtr, &nodeRec);
        !          1557: 
        !          1558:        LogEndTime(kTraceDeleteBTreeRecord, err);
        !          1559: 
        !          1560:        return  err;
        !          1561: }
        !          1562: 
        !          1563: 
        !          1564: 
        !          1565: OSStatus       BTGetInformation        (FCB                                    *filePtr,
        !          1566:                                                                 UInt16                                  version,
        !          1567:                                                                 BTreeInfoRec                   *info )
        !          1568: {
        !          1569: #pragma unused (version)
        !          1570: 
        !          1571:        BTreeControlBlockPtr    btreePtr;
        !          1572: 
        !          1573: 
        !          1574:        M_ReturnErrorIf (filePtr == nil,        paramErr);
        !          1575: 
        !          1576:        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        !          1577: 
        !          1578:        RequireFileLock(btreePtr->fileRefNum, true);
        !          1579: 
        !          1580:        M_ReturnErrorIf (btreePtr == nil,       fsBTInvalidFileErr);
        !          1581:        M_ReturnErrorIf (info == nil,           paramErr);
        !          1582: 
        !          1583:        //�� check version?
        !          1584: 
        !          1585:        info->nodeSize          = btreePtr->nodeSize;
        !          1586:        info->maxKeyLength      = btreePtr->maxKeyLength;
        !          1587:        info->treeDepth         = btreePtr->treeDepth;
        !          1588:        info->numRecords        = btreePtr->leafRecords;
        !          1589:        info->numNodes          = btreePtr->totalNodes;
        !          1590:        info->numFreeNodes      = btreePtr->freeNodes;
        !          1591:        info->lastfsync         = btreePtr->lastfsync;
        !          1592:        info->reserved          = 0;
        !          1593: 
        !          1594:        return noErr;
        !          1595: }
        !          1596: 
        !          1597: 
        !          1598: 
        !          1599: /*-------------------------------------------------------------------------------
        !          1600: Routine:       BTFlushPath     -       Flush BTreeControlBlock to Header Node.
        !          1601: 
        !          1602: Function:      Brief_description_of_the_function_and_any_side_effects
        !          1603: 
        !          1604: 
        !          1605: Input:         pathPtr         - pointer to path control block for B*Tree file to flush
        !          1606: 
        !          1607: Output:                none
        !          1608: 
        !          1609: Result:                noErr           - success
        !          1610:                        != noErr        - failure
        !          1611: -------------------------------------------------------------------------------*/
        !          1612: 
        !          1613: OSStatus       BTFlushPath                             (FCB                                    *filePtr)
        !          1614: {
        !          1615:        OSStatus                                err;
        !          1616:        BTreeControlBlockPtr    btreePtr;
        !          1617: 
        !          1618: 
        !          1619:        LogStartTime(kTraceFlushBTree);
        !          1620: 
        !          1621:        M_ReturnErrorIf (filePtr == nil,        paramErr);
        !          1622: 
        !          1623:        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        !          1624: 
        !          1625:        M_ReturnErrorIf (btreePtr == nil,       fsBTInvalidFileErr);
        !          1626: 
        !          1627:        RequireFileLock(btreePtr->fileRefNum, false);
        !          1628: 
        !          1629:        err = UpdateHeader (btreePtr);
        !          1630: 
        !          1631:        LogEndTime(kTraceFlushBTree, err);
        !          1632: 
        !          1633:        return  err;
        !          1634: }
        !          1635: 
        !          1636: 
        !          1637: 
        !          1638: /*-------------------------------------------------------------------------------
        !          1639: Routine:       BTInvalidateHint        -       Invalidates the hint within a BTreeInterator.
        !          1640: 
        !          1641: Function:      Invalidates the hint within a BTreeInterator.
        !          1642: 
        !          1643: 
        !          1644: Input:         iterator        - pointer to BTreeIterator
        !          1645: 
        !          1646: Output:                iterator        - iterator with the hint.nodeNum cleared
        !          1647: 
        !          1648: Result:                noErr                   - success
        !          1649:                        paramErr        - iterator == nil
        !          1650: -------------------------------------------------------------------------------*/
        !          1651: 
        !          1652: 
        !          1653: OSStatus       BTInvalidateHint        (BTreeIterator                          *iterator )
        !          1654: {
        !          1655:        if (iterator == nil)
        !          1656:                return  paramErr;
        !          1657: 
        !          1658:        iterator->hint.nodeNum = 0;
        !          1659: 
        !          1660:        return  noErr;
        !          1661: }
        !          1662: 
        !          1663: 
        !          1664: 
        !          1665: 
        !          1666: /*-------------------------------------------------------------------------------
        !          1667: Routine:       BTGetLastSync
        !          1668: 
        !          1669: Function:      Returns the last time that this btree was flushed, does not include header.
        !          1670: 
        !          1671: Input:         filePtr - pointer file control block
        !          1672: 
        !          1673: Output:                lastfsync       - time in seconds of last update
        !          1674: 
        !          1675: Result:                noErr                   - success
        !          1676:                        paramErr        - iterator == nil
        !          1677: -------------------------------------------------------------------------------*/
        !          1678: 
        !          1679: 
        !          1680: OSStatus       BTGetLastSync           (FCB                                    *filePtr,
        !          1681:                                                                 UInt32                                 *lastsync)
        !          1682: {
        !          1683:        BTreeControlBlockPtr    btreePtr;
        !          1684: 
        !          1685: 
        !          1686:        M_ReturnErrorIf (filePtr == nil,        paramErr);
        !          1687: 
        !          1688:        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        !          1689:        
        !          1690:        /* Maybe instead of requiring a lock..an atomic set might be more appropriate */
        !          1691:        RequireFileLock(btreePtr->fileRefNum, true);
        !          1692: 
        !          1693:        M_ReturnErrorIf (btreePtr == nil,       fsBTInvalidFileErr);
        !          1694:        M_ReturnErrorIf (lastsync == nil,       paramErr);
        !          1695: 
        !          1696:        *lastsync               = btreePtr->lastfsync;
        !          1697: 
        !          1698:        return noErr;
        !          1699: }
        !          1700: 
        !          1701: 
        !          1702: 
        !          1703: 
        !          1704: /*-------------------------------------------------------------------------------
        !          1705: Routine:       BTSetLastSync
        !          1706: 
        !          1707: Function:      Sets the last time that this btree was flushed, does not include header.
        !          1708: 
        !          1709: 
        !          1710: Input:         fcb     - pointer file control block
        !          1711: 
        !          1712: Output:                lastfsync       - time in seconds of last update
        !          1713: 
        !          1714: Result:                noErr                   - success
        !          1715:                        paramErr        - iterator == nil
        !          1716: -------------------------------------------------------------------------------*/
        !          1717: 
        !          1718: 
        !          1719: OSStatus       BTSetLastSync           (FCB                                    *filePtr,
        !          1720:                                                                 UInt32                                 lastsync)
        !          1721: {
        !          1722:        BTreeControlBlockPtr    btreePtr;
        !          1723: 
        !          1724: 
        !          1725:        M_ReturnErrorIf (filePtr == nil,        paramErr);
        !          1726: 
        !          1727:        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        !          1728:        
        !          1729:        /* Maybe instead of requiring a lock..an atomic set might be more appropriate */
        !          1730:        RequireFileLock(btreePtr->fileRefNum, true);
        !          1731: 
        !          1732:        M_ReturnErrorIf (btreePtr == nil,       fsBTInvalidFileErr);
        !          1733:        M_ReturnErrorIf (lastsync == nil,       paramErr);
        !          1734: 
        !          1735:        btreePtr->lastfsync = lastsync;
        !          1736: 
        !          1737:        return noErr;
        !          1738: }
        !          1739: 
        !          1740: 

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