Return to BTreeAllocate.c CVS log

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

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

1.1     ! root        1: /*
        !             2:  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
        !             3:  *
        !             4:  * @APPLE_LICENSE_HEADER_START@
        !             5:  * 
        !             6:  * The contents of this file constitute Original Code as defined in and
        !             7:  * are subject to the Apple Public Source License Version 1.1 (the
        !             8:  * "License").  You may not use this file except in compliance with the
        !             9:  * License.  Please obtain a copy of the License at
        !            10:  * http://www.apple.com/publicsource and read it before using this file.
        !            11:  * 
        !            12:  * This Original Code and all software distributed under the License are
        !            13:  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
        !            14:  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
        !            15:  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
        !            16:  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
        !            17:  * License for the specific language governing rights and limitations
        !            18:  * under the License.
        !            19:  * 
        !            20:  * @APPLE_LICENSE_HEADER_END@
        !            21:  */
        !            22: /*
        !            23:        File:           BTreeAllocate.c
        !            24: 
        !            25:        Contains:       BTree Node Allocation routines for the BTree Module.
        !            26: 
        !            27:        Version:        xxx put the technology version here xxx
        !            28: 
        !            29:        Written by:     Gordon Sheridan and Bill Bruffey
        !            30: 
        !            31:        Copyright:      � 1992-1999 by Apple Computer, Inc., all rights reserved.
        !            32: 
        !            33:        File Ownership:
        !            34: 
        !            35:                DRI:                            Don Brady
        !            36: 
        !            37:                Other Contact:          Mark Day
        !            38: 
        !            39:                Technology:                     File Systems
        !            40: 
        !            41:        Writers:
        !            42: 
        !            43:                (djb)   Don Brady
        !            44:                (ser)   Scott Roberts
        !            45:                (msd)   Mark Day
        !            46: 
        !            47:        Change History (most recent first):
        !            48: 
        !            49:           <MOSXS>        6/1/99        djb             Sync up with Mac OS 8.6.
        !            50:           <CS3>        11/24/97        djb             Remove some debug code (Panic calls).
        !            51:           <CS2>         7/24/97        djb             CallbackProcs now take refnum instead of an FCB.
        !            52:           <CS1>         4/23/97        djb             first checked in
        !            53: 
        !            54:          <HFS2>         2/19/97        djb             Change E_BadNodeType to fsBTBadNodeType.
        !            55:          <HFS1>        12/19/96        djb             first checked in
        !            56: 
        !            57:        History applicable to original Scarecrow Design:
        !            58: 
        !            59:                 <4>    10/25/96        ser             Changing for new VFPI
        !            60:                 <3>    10/18/96        ser             Converting over VFPI changes
        !            61:                 <2>     1/10/96        msd             Change 64-bit math to use real function names from Math64.i.
        !            62:                 <1>    10/18/95        rst             Moved from Scarecrow project.
        !            63: 
        !            64:                 <8>     1/12/95        wjk             Adopt Model FileSystem changes in D5.
        !            65:                 <7>     9/30/94        prp             Get in sync with D2 interface changes.
        !            66:                 <6>     7/22/94        wjk             Convert to the new set of header files.
        !            67:                 <5>     8/31/93        prp             Use U64SetU instead of S64Set.
        !            68:                 <4>     5/21/93        gs              Fix ExtendBTree bug.
        !            69:                 <3>     5/10/93        gs              Fix pointer arithmetic bug in AllocateNode.
        !            70:                 <2>     3/23/93        gs              finish ExtendBTree routine.
        !            71:                 <1>      2/8/93        gs              first checked in
        !            72:                 <0>      1/1/93        gs              begin AllocateNode and FreeNode
        !            73: 
        !            74: */
        !            75: 
        !            76: #include "../headers/BTreesPrivate.h"
        !            77: 
        !            78: ///////////////////// Routines Internal To BTreeAllocate.c //////////////////////
        !            79: 
        !            80: OSStatus       GetMapNode (BTreeControlBlockPtr          btreePtr,
        !            81:                                                BlockDescriptor                  *nodePtr,
        !            82:                                                UInt16                                  **mapPtr,
        !            83:                                                UInt16                                   *mapSize );
        !            84: 
        !            85: /////////////////////////////////////////////////////////////////////////////////
        !            86: 
        !            87: /*-------------------------------------------------------------------------------
        !            88: 
        !            89: Routine:       AllocateNode    -       Find Free Node, Mark It Used, and Return Node Number.
        !            90: 
        !            91: Function:      Searches the map records for the first free node, marks it "in use" and
        !            92:                        returns the node number found. This routine should really only be called
        !            93:                        when we know there are free blocks, otherwise it's just a waste of time.
        !            94: 
        !            95: Note:          We have to examine map nodes a word at a time rather than a long word
        !            96:                        because the External BTree Mgr used map records that were not an integral
        !            97:                        number of long words. Too bad. In our spare time could develop a more
        !            98:                        sophisticated algorithm that read map records by long words (and long
        !            99:                        word aligned) and handled the spare bytes at the beginning and end
        !           100:                        appropriately.
        !           101: 
        !           102: Input:         btreePtr        - pointer to control block for BTree file               
        !           103: 
        !           104: Output:                nodeNum         - number of node allocated
        !           105:                        
        !           106:                        
        !           107: Result:                noErr                   - success
        !           108:                        fsBTNoMoreMapNodesErr   - no free blocks were found
        !           109:                        != noErr                - failure
        !           110: -------------------------------------------------------------------------------*/
        !           111: 
        !           112: OSStatus       AllocateNode (BTreeControlBlockPtr              btreePtr, UInt32        *nodeNum)
        !           113: {
        !           114:        OSStatus                 err;
        !           115:        BlockDescriptor  node;
        !           116:        UInt16                  *mapPtr, *pos;
        !           117:        UInt16                   mapSize, size;
        !           118:        UInt16                   freeWord;
        !           119:        UInt16                   mask;
        !           120:        UInt16                   bitOffset;
        !           121:        UInt32                   nodeNumber;
        !           122:        
        !           123:        
        !           124:        nodeNumber              = 0;                            // first node number of header map record
        !           125:        node.buffer             = nil;                          // clear node.buffer to get header node
        !           126:                                                                                //      - and for ErrorExit
        !           127:        
        !           128:        while (true)
        !           129:        {
        !           130:                err = GetMapNode (btreePtr, &node, &mapPtr, &mapSize);
        !           131:                M_ExitOnError (err);
        !           132:                
        !           133:        //////////////////////// Find Word with Free Bit ////////////////////////////
        !           134: 
        !           135:                pos             = mapPtr;
        !           136:                size    = mapSize;
        !           137:                size  >>= 1;                                            // convert to number of words
        !           138:                                                //�� assumes mapRecords contain an integral number of words
        !           139: 
        !           140:                while ( size-- )
        !           141:                {
        !           142:                        if ( *pos++ != 0xFFFF )                 // assume test fails, and increment pos
        !           143:                                break;
        !           144:                }
        !           145: 
        !           146:                --pos;                                                          // whoa! backup
        !           147: 
        !           148:                if (*pos != 0xFFFF)                                     // hey, we got one!
        !           149:                        break;
        !           150:                
        !           151:                nodeNumber += mapSize << 3;                     // covert to number of bits (nodes)
        !           152:        }
        !           153:        
        !           154:        ///////////////////////// Find Free Bit in Word /////////////////////////////
        !           155: 
        !           156:        freeWord        = *pos;
        !           157:        bitOffset       =  15;
        !           158:        mask            =  0x8000;
        !           159:        
        !           160:        do {
        !           161:                if ( (freeWord & mask) == 0)
        !           162:                        break;
        !           163:                mask >>= 1;
        !           164:        } while (--bitOffset);
        !           165: 
        !           166:        ////////////////////// Calculate Free Node Number ///////////////////////////
        !           167:        
        !           168:        nodeNumber += ((pos - mapPtr) << 4) + (15 - bitOffset); // (pos-mapPtr) = # of words!
        !           169:        
        !           170:        
        !           171:        ///////////////////////// Check for End of Map //////////////////////////////
        !           172: 
        !           173:        if (nodeNumber >= btreePtr->totalNodes)
        !           174:        {
        !           175:                err = fsBTFullErr;
        !           176:                goto ErrorExit;
        !           177:        }
        !           178: 
        !           179:        /////////////////////////// Allocate the Node ///////////////////////////////
        !           180: 
        !           181:        *pos |= mask;                                           // set the map bit for the node
        !           182: 
        !           183:        err = UpdateNode (btreePtr, &node, 0, kLockTransaction);
        !           184:        M_ExitOnError (err);
        !           185:        
        !           186:        --btreePtr->freeNodes;
        !           187:        btreePtr->flags |= kBTHeaderDirty;
        !           188:        *nodeNum = nodeNumber;
        !           189:        
        !           190:        return noErr;
        !           191: 
        !           192: ////////////////////////////////// Error Exit ///////////////////////////////////
        !           193: 
        !           194: ErrorExit:
        !           195:        
        !           196:        (void) ReleaseNode (btreePtr, &node);
        !           197:        *nodeNum = 0;
        !           198:        
        !           199:        return  err;
        !           200: }
        !           201: 
        !           202: 
        !           203: 
        !           204: /*-------------------------------------------------------------------------------
        !           205: 
        !           206: Routine:       FreeNode        -       Clear allocation bit for node.
        !           207: 
        !           208: Function:      Finds the bit representing the node specified by nodeNum in the node
        !           209:                        map and clears the bit.
        !           210: 
        !           211: 
        !           212: Input:         btreePtr        - pointer to control block for BTree file
        !           213:                        nodeNum         - number of node to mark free
        !           214: 
        !           215: Output:                none                    
        !           216:                        
        !           217: Result:                noErr                   - success
        !           218:                        fsBTNoMoreMapNodesErr   - node number is beyond end of node map
        !           219:                        != noErr                - GetNode or ReleaseNode encountered some difficulty
        !           220: -------------------------------------------------------------------------------*/
        !           221: 
        !           222: OSStatus       FreeNode (BTreeControlBlockPtr          btreePtr, UInt32        nodeNum)
        !           223: {
        !           224:        OSStatus                 err;
        !           225:        BlockDescriptor  node;
        !           226:        UInt32                   nodeIndex;
        !           227:        UInt16                   mapSize;
        !           228:        UInt16                  *mapPos;
        !           229:        UInt16                   bitOffset;
        !           230:        
        !           231: 
        !           232:        //////////////////////////// Find Map Record ////////////////////////////////
        !           233:        nodeIndex                       = 0;                            // first node number of header map record
        !           234:        node.buffer                     = nil;                          // invalidate node.buffer to get header node
        !           235:        
        !           236:        while (nodeNum >= nodeIndex)
        !           237:        {
        !           238:                err = GetMapNode (btreePtr, &node, &mapPos, &mapSize);
        !           239:                M_ExitOnError (err);
        !           240:                
        !           241:                nodeIndex += mapSize << 3;                      // covert to number of bits (nodes)
        !           242:        }
        !           243:        
        !           244:        //////////////////////////// Mark Node Free /////////////////////////////////
        !           245: 
        !           246:        nodeNum -= (nodeIndex - (mapSize << 3));                        // relative to this map record
        !           247:        bitOffset = 15 - (nodeNum & 0x0000000F);                        // last 4 bits are bit offset
        !           248:        mapPos += nodeNum >> 4;                                                         // point to word containing map bit
        !           249:        M_ClearBitNum (*mapPos, bitOffset);                                     // clear it
        !           250:        
        !           251:        err = UpdateNode (btreePtr, &node, 0, kLockTransaction);
        !           252:        M_ExitOnError (err);
        !           253:        
        !           254: 
        !           255:        ++btreePtr->freeNodes;
        !           256:        btreePtr->flags |= kBTHeaderDirty;                                      //�� how about a macro for this
        !           257: 
        !           258:        return noErr;
        !           259: 
        !           260: ErrorExit:
        !           261: 
        !           262:        (void) ReleaseNode (btreePtr, &node);
        !           263: 
        !           264:        return  err;
        !           265: }
        !           266: 
        !           267: 
        !           268: 
        !           269: /*-------------------------------------------------------------------------------
        !           270: 
        !           271: Routine:       ExtendBTree     -       Call FSAgent to extend file, and allocate necessary map nodes.
        !           272: 
        !           273: Function:      This routine calls the the FSAgent to extend the end of fork, if necessary,
        !           274:                        to accomodate the number of nodes requested. It then allocates as many
        !           275:                        map nodes as are necessary to account for all the nodes in the B*Tree.
        !           276:                        If newTotalNodes is less than the current number of nodes, no action is
        !           277:                        taken.
        !           278: 
        !           279: Note:          Internal HFS File Manager BTree Module counts on an integral number of
        !           280:                        long words in map records, although they are not long word aligned.
        !           281: 
        !           282: Input:         btreePtr                - pointer to control block for BTree file
        !           283:                        newTotalNodes   - total number of nodes the B*Tree is to extended to
        !           284:                        
        !           285: Output:                none
        !           286:                        
        !           287: Result:                noErr           - success
        !           288:                        != noErr        - failure
        !           289: -------------------------------------------------------------------------------*/
        !           290: 
        !           291: OSStatus       ExtendBTree     (BTreeControlBlockPtr   btreePtr,
        !           292:                                                 UInt32                                 newTotalNodes )
        !           293: {
        !           294:        OSStatus                                 err;
        !           295:        FCB                                             *filePtr;
        !           296:        FSSize                                   minEOF, maxEOF;        
        !           297:        UInt16                                   nodeSize;
        !           298:        UInt32                                   oldTotalNodes;
        !           299:        UInt32                                   newMapNodes;
        !           300:        UInt32                                   mapBits, totalMapBits;
        !           301:        UInt32                                   recStartBit;
        !           302:        UInt32                                   nodeNum, nextNodeNum;
        !           303:        UInt32                                   firstNewMapNodeNum, lastNewMapNodeNum;
        !           304:        BlockDescriptor                  mapNode, newNode;
        !           305:        UInt16                                  *mapPos;
        !           306:        UInt16                                  *mapStart;
        !           307:        UInt16                                   mapSize;
        !           308:        UInt16                                   mapNodeRecSize;
        !           309:        UInt32                                   bitInWord, bitInRecord;
        !           310:        UInt16                                   mapIndex;
        !           311: 
        !           312: 
        !           313:        oldTotalNodes           = btreePtr->totalNodes;
        !           314:        if (newTotalNodes  <= oldTotalNodes)                            // we're done!
        !           315:                return  noErr;
        !           316: 
        !           317:        nodeSize                        = btreePtr->nodeSize;
        !           318:        filePtr                         = GetFileControlBlock(btreePtr->fileRefNum);
        !           319:        
        !           320:        mapNode.buffer          = nil;
        !           321:        newNode.buffer          = nil;
        !           322: 
        !           323:        mapNodeRecSize  = nodeSize - sizeof(BTNodeDescriptor) - 6;      // 2 bytes of free space (see note)
        !           324: 
        !           325:        //�� update for proper 64 bit arithmetic!!
        !           326: 
        !           327: 
        !           328:        //////////////////////// Count Bits In Node Map /////////////////////////////
        !           329:        
        !           330:        totalMapBits = 0;
        !           331:        do {
        !           332:                err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize);
        !           333:                M_ExitOnError (err);
        !           334:                
        !           335:                mapBits         = mapSize << 3;                         // mapSize (in bytes) * 8
        !           336:                recStartBit     = totalMapBits;                         // bit number of first bit in map record
        !           337:                totalMapBits  += mapBits;
        !           338:                
        !           339:        } while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 );
        !           340: 
        !           341:        if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr))
        !           342:                Panic ("\pExtendBTree: totalMapBits != CalcMapBits");
        !           343:                
        !           344:        /////////////////////// Extend LEOF If Necessary ////////////////////////////
        !           345: 
        !           346:        minEOF = newTotalNodes * nodeSize;
        !           347:        if ( filePtr->fcbEOF < minEOF )
        !           348:        {
        !           349:                //��
        !           350:                //��    ???? Does this B*Tree pack stop working when LEOF > 2^32-1?
        !           351:                //��
        !           352:                maxEOF = ((UInt32)0xFFFFFFFFL);
        !           353: 
        !           354:                err = btreePtr->setEndOfForkProc (btreePtr->fileRefNum, minEOF, maxEOF);
        !           355:                M_ExitOnError (err);
        !           356:        }
        !           357: 
        !           358:        
        !           359:        //////////////////// Calc New Total Number Of Nodes /////////////////////////
        !           360:        
        !           361:        newTotalNodes = filePtr->fcbEOF / nodeSize;             //�� hack!
        !           362:        //�� do we wish to perform any verification of newTotalNodes at this point?
        !           363: 
        !           364:        btreePtr->totalNodes     =  newTotalNodes;              //�� do we need to update freeNodes here too?
        !           365: 
        !           366: 
        !           367:        ////////////// Calculate Number Of New Map Nodes Required ///////////////////
        !           368: 
        !           369:        newMapNodes             = 0;
        !           370:        if (newTotalNodes > totalMapBits)
        !           371:        {
        !           372:                newMapNodes                     = (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1;
        !           373:                firstNewMapNodeNum      = oldTotalNodes;
        !           374:                lastNewMapNodeNum       = firstNewMapNodeNum + newMapNodes - 1;
        !           375:        }
        !           376:        else
        !           377:        {
        !           378:                err = ReleaseNode (btreePtr, &mapNode);
        !           379:                M_ExitOnError (err);
        !           380:        
        !           381:                goto Success;
        !           382:        }
        !           383:        
        !           384: 
        !           385:        /////////////////////// Initialize New Map Nodes ////////////////////////////
        !           386: 
        !           387:        ((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum;
        !           388: 
        !           389:        nodeNum         = firstNewMapNodeNum;
        !           390:        while (true)
        !           391:        {
        !           392:                err = GetNewNode (btreePtr, nodeNum, &newNode);
        !           393:                M_ExitOnError (err);
        !           394:                
        !           395:                ((NodeDescPtr)newNode.buffer)->numRecords       = 1;
        !           396:                ((NodeDescPtr)newNode.buffer)->kind = kBTMapNode;
        !           397:                
        !           398:                // set free space offset
        !           399:                *(UInt16 *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6;
        !           400: 
        !           401:                if (nodeNum++ == lastNewMapNodeNum)
        !           402:                        break;
        !           403: 
        !           404:                ((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum;   // point to next map node
        !           405:                        
        !           406:                err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
        !           407:                M_ExitOnError (err);
        !           408:        }
        !           409:        
        !           410:        err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
        !           411:        M_ExitOnError (err);
        !           412:                
        !           413: 
        !           414:        ///////////////////// Mark New Map Nodes Allocated //////////////////////////
        !           415: 
        !           416:        nodeNum = firstNewMapNodeNum;
        !           417:        do {    
        !           418:                bitInRecord     = nodeNum - recStartBit;
        !           419: 
        !           420:                while (bitInRecord >= mapBits)
        !           421:                {
        !           422:                        nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink;
        !           423:                        if ( nextNodeNum == 0)
        !           424:                        {
        !           425:                                err = fsBTNoMoreMapNodesErr;
        !           426:                                goto ErrorExit;
        !           427:                        }
        !           428:                        
        !           429:                        err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction);
        !           430:                        M_ExitOnError (err);
        !           431:                        
        !           432:                        err = GetNode (btreePtr, nextNodeNum, &mapNode);
        !           433:                        M_ExitOnError (err);
        !           434:                        
        !           435:                        mapIndex = 0;
        !           436:                        
        !           437:                        mapStart         = (UInt16 *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex);
        !           438:                        mapSize          = GetRecordSize (btreePtr, mapNode.buffer, mapIndex);
        !           439:                        
        !           440:                        if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) )
        !           441:                        {
        !           442:                                Panic ("\pExtendBTree: mapSize != M_MapRecordSize");
        !           443:                        }
        !           444:                        
        !           445:                        mapBits         = mapSize << 3;         // mapSize (in bytes) * 8
        !           446:                        recStartBit     = totalMapBits;         // bit number of first bit in map record
        !           447:                        totalMapBits  += mapBits;
        !           448: 
        !           449:                        bitInRecord     = nodeNum - recStartBit;
        !           450:                }
        !           451: 
        !           452:                mapPos          = mapStart + ((nodeNum - recStartBit) >> 4);
        !           453:                bitInWord       = 15 - ((nodeNum - recStartBit) & 0x0000000F);
        !           454:                M_SetBitNum (*mapPos, bitInWord);
        !           455:                
        !           456:                ++nodeNum;
        !           457:                
        !           458:        } while (nodeNum <= lastNewMapNodeNum);
        !           459: 
        !           460:        err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction);
        !           461:        M_ExitOnError (err);
        !           462: 
        !           463:        
        !           464:        //////////////////////////////// Success ////////////////////////////////////
        !           465: 
        !           466: Success:
        !           467:        
        !           468:        btreePtr->totalNodes     =  newTotalNodes;
        !           469:        btreePtr->freeNodes             += (newTotalNodes - oldTotalNodes) - newMapNodes;
        !           470: 
        !           471:        btreePtr->flags                 |= kBTHeaderDirty;              //�� how about a macro for this
        !           472:        
        !           473:        return  noErr;
        !           474: 
        !           475: 
        !           476:        ////////////////////////////// Error Exit ///////////////////////////////////
        !           477: 
        !           478: ErrorExit:
        !           479: 
        !           480:        (void) ReleaseNode (btreePtr, &mapNode);
        !           481:        (void) ReleaseNode (btreePtr, &newNode);
        !           482:        
        !           483:        return  err;
        !           484: }
        !           485: 
        !           486: 
        !           487: 
        !           488: /*-------------------------------------------------------------------------------
        !           489: 
        !           490: Routine:       GetMapNode      -       Get the next map node and pointer to the map record.
        !           491: 
        !           492: Function:      Given a BlockDescriptor to a map node in nodePtr, GetMapNode releases
        !           493:                        it and gets the next node. If nodePtr->buffer is nil, then the header
        !           494:                        node is retrieved.
        !           495: 
        !           496: 
        !           497: Input:         btreePtr        - pointer to control block for BTree file
        !           498:                        nodePtr         - pointer to a BlockDescriptor of a map node
        !           499:                        
        !           500: Output:                nodePtr         - pointer to the BlockDescriptor for the next map node
        !           501:                        mapPtr          - pointer to the map record within the map node
        !           502:                        mapSize         - number of bytes in the map record
        !           503:                        
        !           504: Result:                noErr                   - success
        !           505:                        fsBTNoMoreMapNodesErr   - we've run out of map nodes
        !           506:                        fsBTInvalidNodeErr                      - bad node, or not node type kMapNode
        !           507:                        != noErr                - failure
        !           508: -------------------------------------------------------------------------------*/
        !           509: 
        !           510: OSStatus       GetMapNode (BTreeControlBlockPtr          btreePtr,
        !           511:                                                BlockDescriptor                  *nodePtr,
        !           512:                                                UInt16                                  **mapPtr,
        !           513:                                                UInt16                                   *mapSize )
        !           514: {
        !           515:        OSStatus        err;
        !           516:        UInt16          mapIndex;
        !           517:        UInt32          nextNodeNum;
        !           518:        
        !           519:        if (nodePtr->buffer != nil)             // if iterator is valid...
        !           520:        {
        !           521:                nextNodeNum = ((NodeDescPtr)nodePtr->buffer)->fLink;
        !           522:                if (nextNodeNum == 0)
        !           523:                {
        !           524:                        err = fsBTNoMoreMapNodesErr;
        !           525:                        goto ErrorExit;
        !           526:                }
        !           527:                
        !           528:                err = ReleaseNode (btreePtr, nodePtr);
        !           529:                M_ExitOnError (err);
        !           530:                
        !           531:                err = GetNode (btreePtr, nextNodeNum, nodePtr);
        !           532:                M_ExitOnError (err);
        !           533:                
        !           534:                if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTMapNode)
        !           535:                {
        !           536:                        err = fsBTBadNodeType;
        !           537:                        goto ErrorExit;
        !           538:                }
        !           539:                
        !           540:                ++btreePtr->numMapNodesRead;
        !           541:                mapIndex = 0;
        !           542:        } else {
        !           543:                err = GetNode (btreePtr, kHeaderNodeNum, nodePtr);
        !           544:                M_ExitOnError (err);
        !           545:                
        !           546:                if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTHeaderNode)
        !           547:                {
        !           548:                        err = fsBTInvalidHeaderErr;                             //�� or fsBTBadNodeType
        !           549:                        goto ErrorExit;
        !           550:                }
        !           551:                
        !           552:                mapIndex = 2;
        !           553:        }
        !           554:        
        !           555:                
        !           556:        *mapPtr         = (UInt16 *) GetRecordAddress (btreePtr, nodePtr->buffer, mapIndex);
        !           557:        *mapSize        = GetRecordSize (btreePtr, nodePtr->buffer, mapIndex);
        !           558:        
        !           559:        return noErr;
        !           560:        
        !           561:        
        !           562: ErrorExit:
        !           563:        
        !           564:        (void) ReleaseNode (btreePtr, nodePtr);
        !           565:        
        !           566:        *mapPtr         = nil;
        !           567:        *mapSize        = 0;
        !           568:        
        !           569:        return  err;
        !           570: }
        !           571: 
        !           572: 
        !           573: 
        !           574: ////////////////////////////////// CalcMapBits //////////////////////////////////
        !           575: 
        !           576: UInt32         CalcMapBits     (BTreeControlBlockPtr    btreePtr)
        !           577: {
        !           578:        UInt32          mapBits;
        !           579:        
        !           580:        mapBits         = M_HeaderMapRecordSize (btreePtr->nodeSize) << 3;
        !           581:        
        !           582:        while (mapBits < btreePtr->totalNodes)
        !           583:                mapBits += M_MapRecordSize (btreePtr->nodeSize) << 3;
        !           584:        
        !           585:        return  mapBits;
        !           586: }

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