Return to BTreeAllocate.c CVS log

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

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

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