Return to BTreeMiscOps.c CVS log

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

Annotation of kernel/bsd/hfs/hfscommon/BTree/BTreeMiscOps.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:           BTreeMiscOps.c
        !            27: 
        !            28:        Contains:       Miscellaneous operations for the BTree Module.
        !            29: 
        !            30:        Version:        xxx put the technology version here xxx
        !            31: 
        !            32:        Written by:     Gordon Sheridan and Bill Bruffey
        !            33: 
        !            34:        Copyright:      � 1992-1997 by Apple Computer, Inc., all rights reserved.
        !            35: 
        !            36:        File Ownership:
        !            37: 
        !            38:                DRI:                            Don Brady
        !            39: 
        !            40:                Other Contact:          Mark Day
        !            41: 
        !            42:                Technology:                     File Systems
        !            43: 
        !            44:        Writers:
        !            45: 
        !            46:                (DSH)   Deric Horn
        !            47:                (msd)   Mark Day
        !            48:                (djb)   Don Brady
        !            49: 
        !            50:        Change History (most recent first):
        !            51: 
        !            52:           <CS2>          9/4/97        djb             Optimize TrySimpleReplace for the case where record size is not
        !            53:                                                                        changing.
        !            54:           <CS1>         4/23/97        djb             first checked in
        !            55: 
        !            56:          <HFS7>         3/31/97        djb             Move ClearMemory to Utilities.c.
        !            57:          <HFS6>         3/17/97        DSH             Casting for DFA
        !            58:          <HFS5>         2/27/97        msd             Remove temporary fix from last revision. BTree EOF's should be
        !            59:                                                                        correct now, so check for strict equality.
        !            60:          <HFS4>         2/26/97        msd             Fix a casting problem in ClearMemory. TEMPORARY FIX: Made
        !            61:                                                                        VerifyHeader more lenient, allowing the EOF to be greater than
        !            62:                                                                        the amount actually used by nodes; this should really be fixed
        !            63:                                                                        in the formatting code (which needs to compute the real BTree
        !            64:                                                                        sizes before writing the volume header).
        !            65:          <HFS3>         2/19/97        djb             Added ClearMemory. Changed CalcKeyLength to KeyLength.
        !            66:          <HFS2>          1/3/97        djb             Added support for large keys.
        !            67:          <HFS1>        12/19/96        djb             first checked in
        !            68: 
        !            69:        History applicable to original Scarecrow Design:
        !            70: 
        !            71:                 <9>    10/25/96        ser             Changing for new VFPI
        !            72:                 <8>    10/18/96        ser             Converting over VFPI changes
        !            73:                 <7>     9/17/96        dkh             More BTree statistics. Change IsItAHint to not always check to
        !            74:                                                                        see if the hint node is allocated.
        !            75:                 <6>     9/16/96        dkh             Revised BTree statistics.
        !            76:                 <5>     6/20/96        dkh             Radar #1358740. Change from using Pools to debug MemAllocators.
        !            77:                 <4>     1/22/96        dkh             Change Pools.i inclusion to PoolsPriv.i
        !            78:                 <3>     1/10/96        msd             Change 64-bit math to use real function names from Math64.i.
        !            79:                 <2>     12/7/95        dkh             D10E2 build. Changed usage of Ref data type to LogicalAddress.
        !            80:                 <1>    10/18/95        rst             Moved from Scarecrow project.
        !            81: 
        !            82:                <19>     4/26/95        prp             In UpdateHeader, clear the dirty flag after the BTree is updated.
        !            83:                <18>     1/12/95        wjk             Adopt Model FileSystem changes in D5.
        !            84:                <17>    11/16/94        prp             Add IsItAHint routine and use it whenever hint's node number was
        !            85:                                                                        used for testing.
        !            86:                <16>     10/5/94        bk              add pools.h include file
        !            87:                <15>     9/30/94        prp             Get in sync with D2 interface changes.
        !            88:                <14>     7/22/94        wjk             Convert to the new set of header files.
        !            89:                <13>     12/2/93        wjk             Move from Makefiles to BuildFiles. Fit into the ModernOS and
        !            90:                                                                        NRCmds environments.
        !            91:                <12>    11/30/93        wjk             Move from Makefiles to BuildFiles. Fit into the ModernOS and
        !            92:                                                                        NRCmds environments.
        !            93:                <11>    11/23/93        wjk             Changes required to compile on the RS6000.
        !            94:                <10>     8/31/93        prp             Use U64SetU instead of S64Set.
        !            95:                 <9>      6/2/93        gs              Update for changes to FSErrors.h and add some comments.
        !            96:                 <8>     5/21/93        gs              Modify UpdateHeader to write out attributes. Remove
        !            97:                                                                        Get/UpdateNode from TrySimpleReplace.
        !            98:                 <7>     5/10/93        gs              Add TrySimpleReplace routine.
        !            99:                 <6>     3/23/93        gs              Change MoveData to take void * instead of Ptr. Add UpdateHeader
        !           100:                                                                        and ClearBytes routines.
        !           101:                 <5>      2/8/93        gs              Add FindIteratorPosition.
        !           102:                 <4>    12/10/92        gs              Implement CheckKeyDescriptor and the KeyDescriptor interpreter.
        !           103:                 <3>     12/8/92        gs              Add GetKeyDescriptor, VerifyHeader, and Alloc/Dealloc memory
        !           104:                                                                        routines.
        !           105:                 <2>     12/2/92        gs              Add CompareKeys routine.
        !           106:                 <1>    11/15/92        gs              first checked in
        !           107: 
        !           108: */
        !           109: 
        !           110: #include "../headers/BTreesPrivate.h"
        !           111: 
        !           112: 
        !           113: ////////////////////////////// Routine Definitions //////////////////////////////
        !           114: 
        !           115: /*-------------------------------------------------------------------------------
        !           116: Routine:       CalcKeyRecordSize       -       Return size of combined key/record structure.
        !           117: 
        !           118: Function:      Rounds keySize and recSize so they will end on word boundaries.
        !           119:                        Does NOT add size of offset.
        !           120: 
        !           121: Input:         keySize         - length of key (including length field)
        !           122:                        recSize         - length of record data
        !           123: 
        !           124: Output:                none
        !           125:                        
        !           126: Result:                UInt16          - size of combined key/record that will be inserted in btree
        !           127: -------------------------------------------------------------------------------*/
        !           128: 
        !           129: UInt16         CalcKeyRecordSize               (UInt16                                  keySize,
        !           130:                                                                         UInt16                                  recSize )
        !           131: {
        !           132:        if ( M_IsOdd (keySize) )        keySize += 1;   // pad byte
        !           133:        
        !           134:        if (M_IsOdd (recSize) )         recSize += 1;   // pad byte
        !           135:        
        !           136:        return  (keySize + recSize);
        !           137: }
        !           138: 
        !           139: 
        !           140: 
        !           141: /*-------------------------------------------------------------------------------
        !           142: Routine:       VerifyHeader    -       Validate fields of the BTree header record.
        !           143: 
        !           144: Function:      Examines the fields of the BTree header record to determine if the
        !           145:                        fork appears to contain a valid BTree.
        !           146:                        
        !           147: Input:         forkPtr         - pointer to fork control block
        !           148:                        header          - pointer to BTree header
        !           149:                        
        !           150:                        
        !           151: Result:                noErr           - success
        !           152:                        != noErr        - failure
        !           153: -------------------------------------------------------------------------------*/
        !           154: 
        !           155: OSStatus       VerifyHeader    (FCB                            *filePtr,
        !           156:                                                         HeaderPtr                       header )
        !           157: {
        !           158:        UInt32          forkSize;
        !           159:        UInt32          totalNodes;
        !           160:        
        !           161: 
        !           162:        switch (header->nodeSize)                                                       // node size == 512*2^n
        !           163:        {
        !           164:                case   512:
        !           165:                case  1024:
        !           166:                case  2048:
        !           167:                case  4096:
        !           168:                case  8192:
        !           169:                case 16384:
        !           170:                case 32768:             break;
        !           171:                default:                return  fsBTInvalidHeaderErr;                   //�� E_BadNodeType
        !           172:        }
        !           173:        
        !           174:        totalNodes = header->totalNodes;
        !           175: 
        !           176:        forkSize = totalNodes * header->nodeSize;
        !           177:        
        !           178:        if ( forkSize != filePtr->fcbEOF )
        !           179:                return fsBTInvalidHeaderErr;
        !           180:        
        !           181:        if ( header->freeNodes >= totalNodes )
        !           182:                return fsBTInvalidHeaderErr;
        !           183:        
        !           184:        if ( header->rootNode >= totalNodes )
        !           185:                return fsBTInvalidHeaderErr;
        !           186:        
        !           187:        if ( header->firstLeafNode >= totalNodes )
        !           188:                return fsBTInvalidHeaderErr;
        !           189:        
        !           190:        if ( header->lastLeafNode >= totalNodes )
        !           191:                return fsBTInvalidHeaderErr;
        !           192:        
        !           193:        if ( header->treeDepth > kMaxTreeDepth )
        !           194:                return fsBTInvalidHeaderErr;
        !           195: 
        !           196: 
        !           197:        /////////////////////////// Check BTree Type ////////////////////////////////
        !           198:        
        !           199:        switch (header->btreeType)
        !           200:        {
        !           201:                case    0:                                      // HFS Type - no Key Descriptor
        !           202:                case    kUserBTreeType:         // with Key Descriptors etc.
        !           203:                case    kReservedBTreeType:     // Desktop Mgr BTree ?
        !           204:                                                                        break;
        !           205: 
        !           206:                default:                                        return fsBTUnknownVersionErr;           
        !           207:        }
        !           208:        
        !           209:        return noErr;
        !           210: }
        !           211: 
        !           212: 
        !           213: 
        !           214: /*-------------------------------------------------------------------------------
        !           215: Routine:       UpdateHeader    -       Write BTreeInfoRec fields to Header node.
        !           216: 
        !           217: Function:      Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the
        !           218:                        header node if necessary.
        !           219:                        
        !           220: Input:         btreePtr                - pointer to BTreeInfoRec
        !           221:                        
        !           222:                        
        !           223: Result:                noErr           - success
        !           224:                        != noErr        - failure
        !           225: -------------------------------------------------------------------------------*/
        !           226: 
        !           227: OSStatus       UpdateHeader    (BTreeControlBlockPtr           btreePtr)
        !           228: {
        !           229:        OSStatus                                err;
        !           230:        BlockDescriptor                 node;
        !           231:        HeaderPtr                               header; 
        !           232: 
        !           233:        
        !           234:        if ((btreePtr->flags & kBTHeaderDirty) == 0)                    // btree info already flushed
        !           235:        return  noErr;
        !           236:        
        !           237:        
        !           238:        err = GetNode (btreePtr, kHeaderNodeNum, &node );
        !           239:        if (err != noErr)
        !           240:                return  err;
        !           241:        
        !           242:        header  = node.buffer;
        !           243:        
        !           244:        header->treeDepth               = btreePtr->treeDepth;
        !           245:        header->rootNode                = btreePtr->rootNode;
        !           246:        header->leafRecords             = btreePtr->leafRecords;
        !           247:        header->firstLeafNode   = btreePtr->firstLeafNode;
        !           248:        header->lastLeafNode    = btreePtr->lastLeafNode;
        !           249:        header->nodeSize                = btreePtr->nodeSize;                   //�� this shouldn't change
        !           250:        header->maxKeyLength    = btreePtr->maxKeyLength;               //�� neither should this
        !           251:        header->totalNodes              = btreePtr->totalNodes;
        !           252:        header->freeNodes               = btreePtr->freeNodes;
        !           253:        header->btreeType               = btreePtr->btreeType;
        !           254: 
        !           255:        // ignore       header->clumpSize;                                                      //�� rename this field?
        !           256: 
        !           257:        err = UpdateNode (btreePtr, &node);
        !           258: 
        !           259:        btreePtr->flags &= (~kBTHeaderDirty);
        !           260: 
        !           261:        return  err;
        !           262: }
        !           263: 
        !           264: 
        !           265: 
        !           266: /*-------------------------------------------------------------------------------
        !           267: Routine:       FindIteratorPosition    -       One_line_description.
        !           268: 
        !           269: Function:      Brief_description_of_the_function_and_any_side_effects
        !           270: 
        !           271: Algorithm:     see FSC.BT.BTIterateRecord.PICT
        !           272: 
        !           273: Note:          //�� document side-effects of bad node hints
        !           274: 
        !           275: Input:         btreePtr                - description
        !           276:                        iterator                - description
        !           277:                        
        !           278: 
        !           279: Output:                iterator                - description
        !           280:                        left                    - description
        !           281:                        middle                  - description
        !           282:                        right                   - description
        !           283:                        nodeNum                 - description
        !           284:                        returnIndex             - description
        !           285:                        foundRecord             - description
        !           286:                        
        !           287:                        
        !           288: Result:                noErr           - success
        !           289:                        != noErr        - failure
        !           290: -------------------------------------------------------------------------------*/
        !           291: 
        !           292: OSStatus       FindIteratorPosition    (BTreeControlBlockPtr    btreePtr,
        !           293:                                                                         BTreeIteratorPtr                iterator,
        !           294:                                                                         BlockDescriptor                *left,
        !           295:                                                                         BlockDescriptor                *middle,
        !           296:                                                                         BlockDescriptor                *right,
        !           297:                                                                         UInt32                                 *returnNodeNum,
        !           298:                                                                         UInt16                                 *returnIndex,
        !           299:                                                                         Boolean                                *foundRecord )
        !           300: {
        !           301:        OSStatus                err;
        !           302:        Boolean                 foundIt;
        !           303:        UInt32                  nodeNum;
        !           304:        UInt16                  leftIndex,      index,  rightIndex;
        !           305:        Boolean                 validHint;
        !           306: 
        !           307:        // assume btreePtr valid
        !           308:        // assume left, middle, right point to BlockDescriptors
        !           309:        // assume nodeNum points to UInt32
        !           310:        // assume index points to UInt16
        !           311:        // assume foundRecord points to Boolean
        !           312:        
        !           313:        left->buffer            = nil;
        !           314:        middle->buffer          = nil;
        !           315:        right->buffer           = nil;
        !           316:        
        !           317:        foundIt                         = false;
        !           318:        
        !           319:        if (iterator == nil)                                            // do we have an iterator?
        !           320:        {
        !           321:                err = fsBTInvalidIteratorErr;
        !           322:                goto ErrorExit;
        !           323:        }
        !           324: 
        !           325: #if SupportsKeyDescriptors
        !           326:        //�� verify iterator key (change CheckKey to take btreePtr instead of keyDescPtr?)
        !           327:        if (btreePtr->keyDescPtr != nil)
        !           328:        {
        !           329:                err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength );
        !           330:                M_ExitOnError (err);
        !           331:        }
        !           332: #endif
        !           333: 
        !           334:        err = IsItAHint (btreePtr, iterator, &validHint);
        !           335:        M_ExitOnError (err);
        !           336: 
        !           337:        nodeNum = iterator->hint.nodeNum;
        !           338:        if (! validHint)                                                        // does the hint appear to be valid?
        !           339:        {
        !           340:                goto SearchTheTree;
        !           341:        }
        !           342:        
        !           343:        err = GetNode (btreePtr, nodeNum, middle);
        !           344:        if( err == fsBTInvalidNodeErr ) // returned if nodeNum is out of range
        !           345:                goto SearchTheTree;
        !           346:                
        !           347:        M_ExitOnError (err);
        !           348:        
        !           349:        if ( ((NodeDescPtr) middle->buffer)->type               !=      kLeafNode ||
        !           350:                 ((NodeDescPtr) middle->buffer)->numRecords     <=  0 )
        !           351:        {       
        !           352:                goto SearchTheTree;
        !           353:        }
        !           354:                
        !           355:        ++btreePtr->numValidHints;
        !           356:        
        !           357:        foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
        !           358:        if (foundIt == true)
        !           359:        {
        !           360:                goto SuccessfulExit;
        !           361:        }
        !           362:        
        !           363:        if (index == 0)
        !           364:        {
        !           365:                if (((NodeDescPtr) middle->buffer)->bLink == 0)         // before 1st btree record
        !           366:                {
        !           367:                        goto SuccessfulExit;
        !           368:                }
        !           369:                
        !           370:                nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
        !           371:                
        !           372:                err = GetLeftSiblingNode (btreePtr, middle->buffer, left);
        !           373:                M_ExitOnError (err);
        !           374:                
        !           375:                if ( ((NodeDescPtr) left->buffer)->type                 !=      kLeafNode ||
        !           376:                         ((NodeDescPtr) left->buffer)->numRecords       <=  0 )
        !           377:                {       
        !           378:                        goto SearchTheTree;
        !           379:                }
        !           380:                
        !           381:                foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
        !           382:                if (foundIt == true)
        !           383:                {
        !           384:                        *right                  = *middle;
        !           385:                        *middle                 = *left;
        !           386:                        left->buffer    = nil;
        !           387:                        index                   = leftIndex;
        !           388:                        
        !           389:                        goto SuccessfulExit;
        !           390:                }
        !           391:                
        !           392:                if (leftIndex == 0)                                                                     // we're lost!
        !           393:                {
        !           394:                        goto SearchTheTree;
        !           395:                }
        !           396:                else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
        !           397:                {
        !           398:                        nodeNum = ((NodeDescPtr) left->buffer)->fLink;
        !           399:                        
        !           400:                        PanicIf (index != 0, "\pFindIteratorPosition: index != 0");     //�� just checking...
        !           401:                        goto SuccessfulExit;
        !           402:                }
        !           403:                else
        !           404:                {
        !           405:                        *right                  = *middle;
        !           406:                        *middle                 = *left;
        !           407:                        left->buffer    = nil;
        !           408:                        index                   = leftIndex;
        !           409:                        
        !           410:                        goto SuccessfulExit;
        !           411:                }
        !           412:        }
        !           413:        else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
        !           414:        {
        !           415:                if (((NodeDescPtr) middle->buffer)->fLink == 0) // beyond last record
        !           416:                {
        !           417:                        goto SuccessfulExit;
        !           418:                }
        !           419:                
        !           420:                nodeNum = ((NodeDescPtr) middle->buffer)->fLink;
        !           421:                
        !           422:                err = GetRightSiblingNode (btreePtr, middle->buffer, right);
        !           423:                M_ExitOnError (err);
        !           424:                
        !           425:                if ( ((NodeDescPtr) right->buffer)->type                != kLeafNode ||
        !           426:                         ((NodeDescPtr) right->buffer)->numRecords      <=  0 )
        !           427:                {       
        !           428:                        goto SearchTheTree;
        !           429:                }
        !           430: 
        !           431:                foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
        !           432:                if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords)            // we're lost
        !           433:                {
        !           434:                        goto SearchTheTree;
        !           435:                }
        !           436:                else    // we found it, or rightIndex==0, or rightIndex<numRecs
        !           437:                {
        !           438:                        *left                   = *middle;
        !           439:                        *middle                 = *right;
        !           440:                        right->buffer   = nil;
        !           441:                        index                   = rightIndex;
        !           442:                        
        !           443:                        goto SuccessfulExit;
        !           444:                }
        !           445:        }
        !           446: 
        !           447:        
        !           448:        //////////////////////////// Search The Tree ////////////////////////////////   
        !           449: 
        !           450: SearchTheTree:
        !           451:        {
        !           452:                TreePathTable   treePathTable;          // so we only use stack space if we need to
        !           453: 
        !           454:                err = ReleaseNode (btreePtr, left);                     M_ExitOnError (err);
        !           455:                err = ReleaseNode (btreePtr, middle);           M_ExitOnError (err);
        !           456:                err = ReleaseNode (btreePtr, right);            M_ExitOnError (err);
        !           457:        
        !           458:                err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
        !           459:                switch (err)                            //�� separate find condition from exceptions
        !           460:                {
        !           461:                        case noErr:                     foundIt = true;                         break;
        !           462:                        case fsBTRecordNotFoundErr:                                             break;
        !           463:                        default:                                goto ErrorExit;
        !           464:                }
        !           465:        }
        !           466: 
        !           467:        /////////////////////////////// Success! ////////////////////////////////////
        !           468: 
        !           469: SuccessfulExit:
        !           470:        
        !           471:        *returnNodeNum  = nodeNum;
        !           472:        *returnIndex    = index;
        !           473:        *foundRecord    = foundIt;
        !           474:        
        !           475:        return  noErr;
        !           476:        
        !           477:        
        !           478:        ////////////////////////////// Error Exit ///////////////////////////////////
        !           479: 
        !           480: ErrorExit:
        !           481: 
        !           482:        (void)  ReleaseNode (btreePtr, left);
        !           483:        (void)  ReleaseNode (btreePtr, middle);
        !           484:        (void)  ReleaseNode (btreePtr, right);
        !           485: 
        !           486:        *returnNodeNum  = 0;
        !           487:        *returnIndex    = 0;
        !           488:        *foundRecord    = false;
        !           489: 
        !           490:        return  err;
        !           491: }
        !           492: 
        !           493: 
        !           494: 
        !           495: /////////////////////////////// CheckInsertParams ///////////////////////////////
        !           496: 
        !           497: OSStatus       CheckInsertParams               (FCB                                            *filePtr,
        !           498:                                                                         BTreeIterator                          *iterator,
        !           499:                                                                         FSBufferDescriptor                     *record,
        !           500:                                                                         UInt16                                          recordLen )
        !           501: {
        !           502:        BTreeControlBlockPtr    btreePtr;
        !           503:        
        !           504:        if (filePtr == nil)                                                                     return  paramErr;
        !           505: 
        !           506:        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        !           507:        if (btreePtr == nil)                                                            return  fsBTInvalidFileErr;
        !           508:        if (iterator == nil)                                                            return  paramErr;
        !           509:        if (record       == nil)                                                                return  paramErr;
        !           510:        
        !           511: #if SupportsKeyDescriptors
        !           512:        if (btreePtr->keyDescPtr != nil)
        !           513:        {
        !           514:                OSStatus        err;
        !           515: 
        !           516:                err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
        !           517:                if (err != noErr)
        !           518:                        return  err;
        !           519:        }
        !           520: #endif
        !           521: 
        !           522:        //      check total key/record size limit
        !           523:        if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
        !           524:                return  fsBTRecordTooLargeErr;
        !           525:        
        !           526:        return  noErr;
        !           527: }
        !           528: 
        !           529: 
        !           530: 
        !           531: /*-------------------------------------------------------------------------------
        !           532: Routine:       TrySimpleReplace        -       Attempts a simple insert, set, or replace.
        !           533: 
        !           534: Function:      If a hint exitst for the iterator, attempt to find the key in the hint
        !           535:                        node. If the key is found, an insert operation fails. If the is not
        !           536:                        found, a replace operation fails. If the key was not found, and the
        !           537:                        insert position is greater than 0 and less than numRecords, the record
        !           538:                        is inserted, provided there is enough freeSpace.  If the key was found,
        !           539:                        and there is more freeSpace than the difference between the new record
        !           540:                        and the old record, the old record is deleted and the new record is
        !           541:                        inserted.
        !           542: 
        !           543: Assumptions:   iterator key has already been checked by CheckKey
        !           544: 
        !           545: 
        !           546: Input:         btreePtr                - description
        !           547:                        iterator                - description
        !           548:                        record                  - description
        !           549:                        recordLen               - description
        !           550:                        operation               - description
        !           551:                        
        !           552: 
        !           553: Output:                recordInserted          - description
        !           554:                        
        !           555:                                                
        !           556: Result:                noErr                   - success
        !           557:                        E_RecordExits           - insert operation failure
        !           558:                        != noErr                - GetNode, ReleaseNode, UpdateNode returned an error
        !           559: -------------------------------------------------------------------------------*/
        !           560: 
        !           561: OSStatus       TrySimpleReplace                (BTreeControlBlockPtr    btreePtr,
        !           562:                                                                         NodeDescPtr                     nodePtr,
        !           563:                                                                         BTreeIterator                  *iterator,
        !           564:                                                                         FSBufferDescriptor             *record,
        !           565:                                                                         UInt16                                  recordLen,
        !           566:                                                                         Boolean                                *recordInserted )
        !           567: {
        !           568:        UInt32                          oldSpace;
        !           569:        UInt32                          spaceNeeded;
        !           570:        UInt16                          index;
        !           571:        UInt16                          keySize;
        !           572:        Boolean                         foundIt;
        !           573:        Boolean                         didItFit;
        !           574:        
        !           575:        
        !           576:        *recordInserted = false;                                                                // we'll assume this won't work...
        !           577:        
        !           578:        if ( nodePtr->type != kLeafNode )
        !           579:                return  noErr;  // we're in the weeds!
        !           580: 
        !           581:        foundIt = SearchNode (btreePtr, nodePtr, &iterator->key, &index);       
        !           582: 
        !           583:        if ( foundIt == false )
        !           584:                return  noErr;  // we might be lost...
        !           585:                
        !           586:        keySize = CalcKeySize(btreePtr, &iterator->key);        // includes length field
        !           587:        
        !           588:        spaceNeeded     = CalcKeyRecordSize (keySize, recordLen);
        !           589:        
        !           590:        oldSpace = GetRecordSize (btreePtr, nodePtr, index);
        !           591:        
        !           592:        if ( spaceNeeded == oldSpace )
        !           593:        {
        !           594:                UInt8 *         dst;
        !           595: 
        !           596:                dst = GetRecordAddress (btreePtr, nodePtr, index);
        !           597: 
        !           598:                if ( M_IsOdd (keySize) )
        !           599:                        ++keySize;                      // add pad byte
        !           600:                
        !           601:                dst += keySize;         // skip over key to point at record
        !           602: 
        !           603:                BlockMoveData(record->bufferAddress, dst, recordLen);   // blast away...
        !           604: 
        !           605:                *recordInserted = true;
        !           606:        }
        !           607:        else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
        !           608:        {
        !           609:                DeleteRecord (btreePtr, nodePtr, index);
        !           610:        
        !           611:                didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
        !           612:                                                                                &iterator->key, KeyLength(btreePtr, &iterator->key),
        !           613:                                                                                record->bufferAddress, recordLen);
        !           614:                PanicIf (didItFit == false, "\pTrySimpleInsert: InsertKeyRecord returned false!");
        !           615: 
        !           616:                *recordInserted = true;
        !           617:        }
        !           618:        // else not enough space...
        !           619: 
        !           620:        return  noErr;
        !           621: }
        !           622: 
        !           623: 
        !           624: /*-------------------------------------------------------------------------------
        !           625: Routine:       IsItAHint       -       checks the hint within a BTreeInterator.
        !           626: 
        !           627: Function:      checks the hint within a BTreeInterator.  If it is non-zero, it may 
        !           628:                        possibly be valid. 
        !           629: 
        !           630: Input:         btreePtr        - pointer to control block for BTree file
        !           631:                        iterator        - pointer to BTreeIterator
        !           632:                        
        !           633: Output:                answer          - true if the hint looks reasonable
        !           634:                                                - false if the hint is 0
        !           635:                        
        !           636: Result:                noErr                   - success
        !           637: -------------------------------------------------------------------------------*/
        !           638: 
        !           639: 
        !           640: OSStatus       IsItAHint       (BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer)
        !           641: {
        !           642:        ++btreePtr->numHintChecks;
        !           643:        
        !           644:        //�� shouldn't we do a range check?
        !           645:        if (iterator->hint.nodeNum == 0)
        !           646:        {
        !           647:                *answer = false;
        !           648:        }
        !           649:        else
        !           650:        {
        !           651:                *answer = true;
        !           652:                ++btreePtr->numPossibleHints;
        !           653:        }
        !           654:        
        !           655:        return noErr;
        !           656: }

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