Return to BTree.c CVS log

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

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

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

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