Return to BTreeTreeOps.c CVS log

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

Annotation of XNU/bsd/hfs/hfscommon/BTree/BTreeTreeOps.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:           BTreeTreeOps.c
        !            24: 
        !            25:        Contains:       Multi-node tree operations 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:                (msd)   Mark Day
        !            44:                (DSH)   Deric Horn
        !            45:                (djb)   Don Brady
        !            46: 
        !            47:        Change History (most recent first):
        !            48: 
        !            49:           <MOSXS>        6/1/99        djb             Sync up with Mac OS 8.6.
        !            50:           <CS5>         12/8/97        djb             Radar #2200632, CollapseTree wasn't marking root node dirty.
        !            51:           <CS4>        11/24/97        djb             Radar #2005325, InsertLevel incorrectly handled root splits!
        !            52:           <CS3>        10/17/97        msd             Conditionalize DebugStrs.
        !            53:           <CS2>         5/16/97        msd             InsertNode() needs a return statement in ErrorExit.
        !            54:           <CS1>         4/23/97        djb             first checked in
        !            55: 
        !            56:          <HFS8>         3/17/97        DSH             Conditionalize out Panic assertion for SC.
        !            57:          <HFS7>          3/3/97        djb             Removed DebugStr in InsertLevel.
        !            58:          <HFS6>         2/19/97        djb             Major re-write of insert code; added InsertLevel and InsertNode.
        !            59:          <HFS5>         1/27/97        djb             InsertTree and DeleteTree are now recursive and support variable
        !            60:                                                                        sized index keys.
        !            61:          <HFS4>         1/16/97        djb             Removed DebugStr in SearchTree. Added initial support for
        !            62:                                                                        variable sized index keys.
        !            63:          <HFS3>          1/3/97        djb             Changed len8 to length8.
        !            64:          <HFS2>          1/3/97        djb             Added support for large keys.
        !            65:          <HFS1>        12/19/96        djb             first checked in
        !            66: 
        !            67:        History applicable to original Scarecrow Design:
        !            68: 
        !            69:                 <3>    10/25/96        ser             Changing for new VFPI
        !            70:                 <2>     1/22/96        dkh             Add #include Memory.h
        !            71:                 <1>    10/18/95        rst             Moved from Scarecrow project.
        !            72: 
        !            73:                <12>     7/18/95        mbb             Change MoveData & ClearBytes to BlockMoveData & BlockZero.
        !            74:                <11>     9/30/94        prp             Get in sync with D2 interface changes.
        !            75:                <10>     7/25/94        wjk             Eliminate usage of BytePtr in favor of UInt8 *.
        !            76:                 <9>     7/22/94        wjk             Convert to the new set of header files.
        !            77:                 <8>     12/2/93        wjk             Move from Makefiles to BuildFiles. Fit into the ModernOS and
        !            78:                                                                        NRCmds environments.
        !            79:                 <7>    11/30/93        wjk             Change some Ptr's to BytePtr's in function definitions so they
        !            80:                                                                        agree with their prototypes.
        !            81:                 <6>     5/21/93        gs              Debug DeleteTree. Modify InsertTree for BTReplaceRecord.
        !            82:                 <5>     5/10/93        gs              Modify RotateLeft, and add DeleteTree, CollapseTree routines.
        !            83:                 <4>     3/23/93        gs              revise RotateLeft to use InsertKeyRecord instead of
        !            84:                                                                        InsertRecord.
        !            85:                 <3>     3/23/93        gs              Implement SplitLeft, InsertTree routine.
        !            86:                 <2>      2/8/93        gs              Implement SearchTree, and RotateLeft.
        !            87:                 <1>    11/15/92        gs              first checked in
        !            88: 
        !            89: */
        !            90: 
        !            91: #include "../headers/BTreesPrivate.h"
        !            92: 
        !            93: //
        !            94: /////////////////////// Routines Internal To BTree Module ///////////////////////
        !            95: //
        !            96: //     SearchTree
        !            97: //     InsertTree
        !            98: //
        !            99: ////////////////////// Routines Internal To BTreeTreeOps.c //////////////////////
        !           100: 
        !           101: static OSStatus   AddNewRootNode       (BTreeControlBlockPtr            btreePtr,
        !           102:                                                                         NodeDescPtr                             leftNode,
        !           103:                                                                         NodeDescPtr                             rightNode );
        !           104: 
        !           105: static OSStatus   CollapseTree         (BTreeControlBlockPtr            btreePtr,
        !           106:                                                                         BlockDescriptor                        *blockPtr );
        !           107: 
        !           108: static OSStatus   RotateLeft           (BTreeControlBlockPtr            btreePtr,
        !           109:                                                                         NodeDescPtr                             leftNode,
        !           110:                                                                         NodeDescPtr                             rightNode,
        !           111:                                                                         UInt16                                          rightInsertIndex,
        !           112:                                                                         KeyPtr                                          keyPtr,
        !           113:                                                                         UInt8 *                                         recPtr,
        !           114:                                                                         UInt16                                          recSize,
        !           115:                                                                         UInt16                                         *insertIndex,
        !           116:                                                                         UInt32                                         *insertNodeNum,
        !           117:                                                                         Boolean                                        *recordFit,
        !           118:                                                                         UInt16                                         *recsRotated );
        !           119: 
        !           120: static Boolean    RotateRecordLeft     (BTreeControlBlockPtr            btreePtr,
        !           121:                                                                         NodeDescPtr                             leftNode,
        !           122:                                                                         NodeDescPtr                             rightNode );
        !           123: 
        !           124: static OSStatus           SplitLeft            (BTreeControlBlockPtr            btreePtr,
        !           125:                                                                         BlockDescriptor                        *leftNode,
        !           126:                                                                         BlockDescriptor                        *rightNode,
        !           127:                                                                         UInt32                                          rightNodeNum,
        !           128:                                                                         UInt16                                          index,
        !           129:                                                                         KeyPtr                                          keyPtr,
        !           130:                                                                         UInt8 *                                         recPtr,
        !           131:                                                                         UInt16                                          recSize,
        !           132:                                                                         UInt16                                         *insertIndex,
        !           133:                                                                         UInt32                                         *insertNodeNum,
        !           134:                                                                         UInt16                                         *recsRotated );
        !           135:                                                                 
        !           136: 
        !           137: 
        !           138: static OSStatus        InsertLevel             (BTreeControlBlockPtr            btreePtr,
        !           139:                                                                         TreePathTable                           treePathTable,
        !           140:                                                                         InsertKey                                      *primaryKey,
        !           141:                                                                         InsertKey                                      *secondaryKey,
        !           142:                                                                         BlockDescriptor                        *targetNode,
        !           143:                                                                         UInt16                                          index,
        !           144:                                                                         UInt16                                          level,
        !           145:                                                                         UInt32                                         *insertNode );
        !           146:                                                 
        !           147: static OSErr           InsertNode              (BTreeControlBlockPtr            btreePtr,
        !           148:                                                                         InsertKey                                      *key,
        !           149:                                                                         BlockDescriptor                        *rightNode,
        !           150:                                                                         UInt32                                          node,
        !           151:                                                                         UInt16                                          index,
        !           152:                                                                         UInt32                                         *newNode,       
        !           153:                                                                         UInt16                                         *newIndex,
        !           154:                                                                         BlockDescriptor                        *leftNode,
        !           155:                                                                         Boolean                                        *updateParent,
        !           156:                                                                         Boolean                                        *insertParent,
        !           157:                                                                         Boolean                                        *rootSplit );
        !           158:                                                                         
        !           159: static UInt16          GetKeyLength    (const BTreeControlBlock *btreePtr,
        !           160:                                                                         const BTreeKey *key,
        !           161:                                                                         Boolean forLeafNode );
        !           162: 
        !           163: 
        !           164: 
        !           165: //////////////////////// BTree Multi-node Tree Operations ///////////////////////
        !           166: 
        !           167: 
        !           168: /*-------------------------------------------------------------------------------
        !           169: 
        !           170: Routine:       SearchTree      -       Search BTree for key and set up Tree Path Table.
        !           171: 
        !           172: Function:      Searches BTree for specified key, setting up the Tree Path Table to
        !           173:                        reflect the search path.
        !           174: 
        !           175: 
        !           176: Input:         btreePtr                - pointer to control block of BTree to search
        !           177:                        keyPtr                  - pointer to the key to search for
        !           178:                        treePathTable   - pointer to the tree path table to construct
        !           179:                        
        !           180: Output:                nodeNum                 - number of the node containing the key position
        !           181:                        iterator                - BTreeIterator specifying record or insert position
        !           182:                        
        !           183: Result:                noErr                   - key found, index is record index
        !           184:                        fsBTRecordNotFoundErr   - key not found, index is insert index
        !           185:                        fsBTEmptyErr            - key not found, return params are nil
        !           186:                        otherwise                       - catastrophic failure (GetNode/ReleaseNode failed)
        !           187: -------------------------------------------------------------------------------*/
        !           188: 
        !           189: OSStatus       SearchTree      (BTreeControlBlockPtr    btreePtr,
        !           190:                                                 BTreeKeyPtr                     searchKey,
        !           191:                                                 TreePathTable                   treePathTable,
        !           192:                                                 UInt32                                 *nodeNum,
        !           193:                                                 BlockDescriptor                *nodePtr,
        !           194:                                                 UInt16                                 *returnIndex )
        !           195: {
        !           196:        OSStatus        err;
        !           197:        SInt16          level;
        !           198:        UInt32          curNodeNum;
        !           199:        NodeRec         nodeRec;
        !           200:        UInt16          index;
        !           201:        Boolean         keyFound;
        !           202:        KeyPtr          keyPtr;
        !           203:        UInt8 *         dataPtr;
        !           204:        UInt16          dataSize;
        !           205:        
        !           206:        
        !           207:        if (btreePtr->treeDepth == 0)                                           // is the tree empty?
        !           208:        {
        !           209:                err = fsBTEmptyErr;
        !           210:                goto ErrorExit;
        !           211:        }
        !           212:        
        !           213:        curNodeNum              = btreePtr->rootNode;
        !           214:        
        !           215:        //�� for debugging...
        !           216:        treePathTable [0].node          = 0;
        !           217:        treePathTable [0].index         = 0;
        !           218: 
        !           219:        while (true)
        !           220:        {
        !           221:                PanicIf(curNodeNum == 0, "\pSearchTree: curNodeNum is zero!");
        !           222: 
        !           223:                err = GetNode (btreePtr, curNodeNum, &nodeRec);
        !           224:                if (err != noErr)
        !           225:                {
        !           226:                        goto ErrorExit;
        !           227:                }
        !           228:                
        !           229:                keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index);
        !           230: 
        !           231:                level = ((BTNodeDescriptor*)nodeRec.buffer)->height;    //�� or --level;
        !           232:                
        !           233: 
        !           234:                treePathTable [level].node              = curNodeNum;
        !           235: 
        !           236:                if ( ((BTNodeDescriptor*)nodeRec.buffer)->kind == kBTLeafNode)
        !           237:                {
        !           238:                        treePathTable [level].index = index;
        !           239:                        break;                  // were done...
        !           240:                }
        !           241:                
        !           242:                if ( (keyFound != true) && (index != 0))
        !           243:                        --index;
        !           244: 
        !           245:                treePathTable [level].index = index;
        !           246:                
        !           247:                GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize);
        !           248:                curNodeNum = *(UInt32 *)dataPtr;
        !           249:                err = ReleaseNode (btreePtr, &nodeRec);
        !           250:                if (err != noErr)
        !           251:                {
        !           252:                        goto ErrorExit;
        !           253:                }
        !           254:        }
        !           255:        
        !           256:        *nodeNum                        = curNodeNum;
        !           257:        *nodePtr                        = nodeRec;
        !           258:        *returnIndex            = index;
        !           259: 
        !           260:        if (keyFound)
        !           261:                return  noErr;                  // searchKey found, index identifies record in node
        !           262:        else
        !           263:                return  fsBTRecordNotFoundErr;  // searchKey not found, index identifies insert point
        !           264: 
        !           265: ErrorExit:
        !           266:        
        !           267:        *nodeNum                                        = 0;
        !           268:        nodePtr->buffer                         = nil;
        !           269:        nodePtr->blockHeader            = nil;
        !           270:        *returnIndex                            = 0;
        !           271: 
        !           272:        return  err;
        !           273: }
        !           274: 
        !           275: 
        !           276: 
        !           277: 
        !           278: ////////////////////////////////// InsertTree ///////////////////////////////////
        !           279: 
        !           280: OSStatus       InsertTree ( BTreeControlBlockPtr                btreePtr,
        !           281:                                                 TreePathTable                           treePathTable,
        !           282:                                                 KeyPtr                                          keyPtr,
        !           283:                                                 UInt8 *                                         recPtr,
        !           284:                                                 UInt16                                          recSize,
        !           285:                                                 BlockDescriptor                        *targetNode,
        !           286:                                                 UInt16                                          index,
        !           287:                                                 UInt16                                          level,
        !           288:                                                 Boolean                                         replacingKey,
        !           289:                                                 UInt32                                         *insertNode )
        !           290: {
        !           291:        InsertKey                       primaryKey;
        !           292:        OSStatus                        err;
        !           293: 
        !           294:        primaryKey.keyPtr               = keyPtr;
        !           295:        primaryKey.keyLength    = GetKeyLength(btreePtr, primaryKey.keyPtr, (level == 1));
        !           296:        primaryKey.recPtr               = recPtr;
        !           297:        primaryKey.recSize              = recSize;
        !           298:        primaryKey.replacingKey = replacingKey;
        !           299:        primaryKey.skipRotate   = false;
        !           300: 
        !           301:        err     = InsertLevel (btreePtr, treePathTable, &primaryKey, nil,
        !           302:                                           targetNode, index, level, insertNode );
        !           303:                                                
        !           304:        return err;
        !           305: 
        !           306: } // End of InsertTree
        !           307: 
        !           308: 
        !           309: ////////////////////////////////// InsertLevel //////////////////////////////////
        !           310: 
        !           311: OSStatus       InsertLevel (BTreeControlBlockPtr                btreePtr,
        !           312:                                                 TreePathTable                           treePathTable,
        !           313:                                                 InsertKey                                      *primaryKey,
        !           314:                                                 InsertKey                                      *secondaryKey,
        !           315:                                                 BlockDescriptor                        *targetNode,
        !           316:                                                 UInt16                                          index,
        !           317:                                                 UInt16                                          level,
        !           318:                                                 UInt32                                         *insertNode )
        !           319: {
        !           320:        OSStatus                         err;
        !           321:        BlockDescriptor          leftNode;
        !           322:        UInt32                           targetNodeNum;
        !           323:        UInt32                           newNodeNum;
        !           324:        UInt16                           newIndex;
        !           325:        Boolean                          insertParent;
        !           326:        Boolean                          updateParent;
        !           327:        Boolean                          newRoot;
        !           328: 
        !           329: #if defined(applec) && !defined(__SC__)
        !           330:        PanicIf ((level == 1) && (((NodeDescPtr)targetNode->buffer)->kind != kBTLeafNode), "\P InsertLevel: non-leaf at level 1! ");
        !           331: #endif
        !           332:        leftNode.buffer = nil;
        !           333:        targetNodeNum = treePathTable [level].node;
        !           334: 
        !           335:        insertParent = false;
        !           336:        updateParent = false;
        !           337: 
        !           338:        ////// process first insert //////
        !           339:        
        !           340:        err = InsertNode (btreePtr, primaryKey, targetNode, targetNodeNum, index,
        !           341:                                          &newNodeNum, &newIndex, &leftNode, &updateParent, &insertParent, &newRoot );
        !           342:        M_ExitOnError (err);
        !           343: 
        !           344:        if ( newRoot )
        !           345:        {
        !           346:                // Extend the treePathTable by adding an entry for the new
        !           347:                // root node that references the current targetNode.
        !           348:                // 
        !           349:                // If inserting the secondaryKey changes the first key of
        !           350:                // the target node, then we'll have to update the second
        !           351:                // key in the new root node.
        !           352: 
        !           353:                treePathTable [level + 1].node  = btreePtr->rootNode;
        !           354:                treePathTable [level + 1].index = 1;    // 1 since we always split/rotate left
        !           355:        }
        !           356:        
        !           357:        if ( level == 1 )
        !           358:                *insertNode = newNodeNum;               
        !           359:        
        !           360:        ////// process second insert (if any) //////
        !           361: 
        !           362:        if  ( secondaryKey != nil )
        !           363:        {
        !           364:                Boolean                         temp;
        !           365: 
        !           366:                err = InsertNode (btreePtr, secondaryKey, targetNode, newNodeNum, newIndex,
        !           367:                                                  &newNodeNum, &newIndex, &leftNode, &updateParent, &insertParent, &temp);
        !           368:                M_ExitOnError (err);
        !           369:                
        !           370:                if ( DEBUG_BUILD && updateParent && newRoot )
        !           371:                        DebugStr("\p InsertLevel: New root from primary key, update from secondary key...");
        !           372:        }
        !           373: 
        !           374:        //////////////////////// Update Parent(s) ///////////////////////////////
        !           375: 
        !           376:        if ( insertParent || updateParent )
        !           377:        {
        !           378:                BlockDescriptor         parentNode;
        !           379:                UInt32                          parentNodeNum;
        !           380:                KeyPtr                          keyPtr;
        !           381:                UInt8 *                         recPtr;
        !           382:                UInt16                          recSize;
        !           383:                
        !           384:                secondaryKey = nil;
        !           385:                
        !           386:                PanicIf ( (level == btreePtr->treeDepth), "\p InsertLevel: unfinished insert!?");
        !           387: 
        !           388:                ++level;
        !           389: 
        !           390:                // Get Parent Node data...
        !           391:                index = treePathTable [level].index;
        !           392:                parentNodeNum = treePathTable [level].node;
        !           393: 
        !           394:                PanicIf ( parentNodeNum == 0, "\p InsertLevel: parent node is zero!?");
        !           395: 
        !           396:                err = GetNode (btreePtr, parentNodeNum, &parentNode);   // released as target node in next level up
        !           397:                M_ExitOnError (err);
        !           398: #if defined(applec) && !defined(__SC__)
        !           399:                if (DEBUG_BUILD && level > 1)
        !           400:                        PanicIf ( ((NodeDescPtr)parentNode.buffer)->kind != kBTIndexNode, "\P InsertLevel: parent node not an index node! ");
        !           401: #endif
        !           402:                ////////////////////////// Update Parent Index //////////////////////////////
        !           403:        
        !           404:                if ( updateParent )
        !           405:                {
        !           406:                        //���debug: check if ptr == targetNodeNum
        !           407:                        GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
        !           408:                        PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p InsertLevel: parent ptr doesn't match target node!");
        !           409:                        
        !           410:                        // need to delete and re-insert this parent key/ptr
        !           411:                        // we delete it here and it gets re-inserted in the
        !           412:                        // InsertLevel call below.
        !           413:                        DeleteRecord (btreePtr, parentNode.buffer, index);
        !           414:        
        !           415:                        primaryKey->keyPtr               = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
        !           416:                        primaryKey->keyLength    = GetKeyLength(btreePtr, primaryKey->keyPtr, false);
        !           417:                        primaryKey->recPtr               = (UInt8 *) &targetNodeNum;
        !           418:                        primaryKey->recSize              = sizeof(targetNodeNum);
        !           419:                        primaryKey->replacingKey = kReplaceRecord;
        !           420:                        primaryKey->skipRotate   = insertParent;                // don't rotate left if we have two inserts occuring
        !           421:                }
        !           422:        
        !           423:                ////////////////////////// Add New Parent Index /////////////////////////////
        !           424:        
        !           425:                if ( insertParent )
        !           426:                {
        !           427:                        InsertKey       *insertKeyPtr;
        !           428:                        InsertKey       insertKey;
        !           429:                        
        !           430:                        if ( updateParent )
        !           431:                        {
        !           432:                                insertKeyPtr = &insertKey;
        !           433:                                secondaryKey = &insertKey;
        !           434:                        }
        !           435:                        else
        !           436:                        {
        !           437:                                insertKeyPtr = primaryKey;
        !           438:                        }
        !           439:                        
        !           440:                        insertKeyPtr->keyPtr            = (KeyPtr) GetRecordAddress (btreePtr, leftNode.buffer, 0);
        !           441:                        insertKeyPtr->keyLength         = GetKeyLength(btreePtr, insertKeyPtr->keyPtr, false);
        !           442:                        insertKeyPtr->recPtr            = (UInt8 *) &((NodeDescPtr)targetNode->buffer)->bLink;
        !           443:                        insertKeyPtr->recSize           = sizeof(UInt32);
        !           444:                        insertKeyPtr->replacingKey      = kInsertRecord;
        !           445:                        insertKeyPtr->skipRotate        = false;                // a rotate is OK during second insert
        !           446:                }       
        !           447:                
        !           448:                err = InsertLevel (btreePtr, treePathTable, primaryKey, secondaryKey,
        !           449:                                                   &parentNode, index, level, insertNode );
        !           450:                M_ExitOnError (err);
        !           451:        }
        !           452: 
        !           453:        err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);   // all done with target
        !           454:        M_ExitOnError (err);
        !           455: 
        !           456:        err = UpdateNode (btreePtr, &leftNode, 0, kLockTransaction);            // all done with left sibling
        !           457:        M_ExitOnError (err);
        !           458:        
        !           459:        return  noErr;
        !           460: 
        !           461: ErrorExit:
        !           462: 
        !           463:        (void) ReleaseNode (btreePtr, targetNode);
        !           464:        (void) ReleaseNode (btreePtr, &leftNode);
        !           465: 
        !           466:        Panic ("\p InsertLevel: an error occured!");
        !           467: 
        !           468:        return  err;
        !           469: 
        !           470: } // End of InsertLevel
        !           471: 
        !           472: 
        !           473: 
        !           474: ////////////////////////////////// InsertNode ///////////////////////////////////
        !           475: 
        !           476: static OSErr   InsertNode      (BTreeControlBlockPtr    btreePtr,
        !           477:                                                         InsertKey                              *key,
        !           478: 
        !           479:                                                         BlockDescriptor                *rightNode,
        !           480:                                                         UInt32                                  node,
        !           481:                                                         UInt16                                  index,
        !           482: 
        !           483:                                                         UInt32                                 *newNode,       
        !           484:                                                         UInt16                                 *newIndex,
        !           485: 
        !           486:                                                         BlockDescriptor                *leftNode,
        !           487:                                                         Boolean                                *updateParent,
        !           488:                                                         Boolean                                *insertParent,
        !           489:                                                         Boolean                                *rootSplit )
        !           490: {
        !           491:        BlockDescriptor         *targetNode;
        !           492:        UInt32                           leftNodeNum;
        !           493:        UInt16                           recsRotated;
        !           494:        OSErr                            err;
        !           495:        Boolean                          recordFit;
        !           496: 
        !           497:        *rootSplit = false;
        !           498:        
        !           499:        PanicIf ( rightNode->buffer == leftNode->buffer, "\p InsertNode: rightNode == leftNode, huh?");
        !           500:        
        !           501:        leftNodeNum = ((NodeDescPtr) rightNode->buffer)->bLink;
        !           502: 
        !           503: 
        !           504:        /////////////////////// Try Simple Insert ///////////////////////////////
        !           505: 
        !           506:        if ( node == leftNodeNum )
        !           507:                targetNode = leftNode;
        !           508:        else
        !           509:                targetNode = rightNode;
        !           510: 
        !           511:        recordFit = InsertKeyRecord (btreePtr, targetNode->buffer, index, key->keyPtr, key->keyLength, key->recPtr, key->recSize);
        !           512: 
        !           513:        if ( recordFit )
        !           514:        {
        !           515:                *newNode  = node;
        !           516:                *newIndex = index;
        !           517:        
        !           518:                if ( (index == 0) && (((NodeDescPtr) targetNode->buffer)->height != btreePtr->treeDepth) )
        !           519:                        *updateParent = true;   // the first record changed so we need to update the parent
        !           520:        }
        !           521: 
        !           522: 
        !           523:        //////////////////////// Try Rotate Left ////////////////////////////////
        !           524:        
        !           525:        if ( !recordFit && leftNodeNum > 0 )
        !           526:        {
        !           527:                PanicIf ( leftNode->buffer != nil, "\p InsertNode: leftNode already aquired!");
        !           528: 
        !           529:                if ( leftNode->buffer == nil )
        !           530:                {
        !           531:                        err = GetNode (btreePtr, leftNodeNum, leftNode);        // will be released by caller or a split below
        !           532:                        M_ExitOnError (err);
        !           533:                }
        !           534: 
        !           535:                PanicIf ( ((NodeDescPtr) leftNode->buffer)->fLink != node, "\p InsertNode, RotateLeft: invalid sibling link!" );
        !           536: 
        !           537:                if ( !key->skipRotate )         // are rotates allowed?
        !           538:                {
        !           539:                        err = RotateLeft (btreePtr, leftNode->buffer, rightNode->buffer, index, key->keyPtr, key->recPtr,
        !           540:                                                          key->recSize, newIndex, newNode, &recordFit, &recsRotated );  
        !           541:                        M_ExitOnError (err);
        !           542: 
        !           543:                        if ( recordFit )
        !           544:                        {
        !           545:                                if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
        !           546:                                        *updateParent = true;                   
        !           547:                        }
        !           548:                }
        !           549:        }       
        !           550: 
        !           551: 
        !           552:        //////////////////////// Try Split Left /////////////////////////////////
        !           553: 
        !           554:        if ( !recordFit )
        !           555:        {
        !           556:                // might not have left node...
        !           557:                err = SplitLeft (btreePtr, leftNode, rightNode, node, index, key->keyPtr,
        !           558:                                                 key->recPtr, key->recSize, newIndex, newNode, &recsRotated);
        !           559:                M_ExitOnError (err);
        !           560: 
        !           561:                // if we split root node - add new root
        !           562:                
        !           563:                if ( ((NodeDescPtr) rightNode->buffer)->height == btreePtr->treeDepth )
        !           564:                {
        !           565:                        err = AddNewRootNode (btreePtr, leftNode->buffer, rightNode->buffer);   // Note: does not update TPT
        !           566:                        M_ExitOnError (err);
        !           567:                        *rootSplit = true;
        !           568:                }
        !           569:                else
        !           570:                {
        !           571:                        *insertParent = true;
        !           572: 
        !           573:                        if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
        !           574:                                *updateParent = true;
        !           575:                }
        !           576:        }
        !           577:        
        !           578:        return noErr;
        !           579: 
        !           580: ErrorExit:
        !           581: 
        !           582:        (void) ReleaseNode (btreePtr, leftNode);
        !           583:        return err;
        !           584:        
        !           585: } // End of InsertNode
        !           586: 
        !           587: 
        !           588: /*-------------------------------------------------------------------------------
        !           589: Routine:       DeleteTree      -       One_line_description.
        !           590: 
        !           591: Function:      Brief_description_of_the_function_and_any_side_effects
        !           592: 
        !           593: ToDo:          
        !           594: 
        !           595: Input:         btreePtr                - description
        !           596:                        treePathTable   - description
        !           597:                        targetNode              - description
        !           598:                        index                   - description
        !           599:                                                
        !           600: Result:                noErr           - success
        !           601:                        != noErr        - failure
        !           602: -------------------------------------------------------------------------------*/
        !           603: 
        !           604: OSStatus       DeleteTree                      (BTreeControlBlockPtr            btreePtr,
        !           605:                                                                 TreePathTable                           treePathTable,
        !           606:                                                                 BlockDescriptor                        *targetNode,
        !           607:                                                                 UInt16                                          index,
        !           608:                                                                 UInt16                                          level )
        !           609: {
        !           610:        OSStatus                        err;
        !           611:        BlockDescriptor         parentNode;
        !           612:        BTNodeDescriptor        *targetNodePtr;
        !           613:        UInt32                          targetNodeNum;
        !           614:        Boolean                         deleteRequired;
        !           615:        Boolean                         updateRequired;
        !           616: 
        !           617: 
        !           618:        deleteRequired = false;
        !           619:        updateRequired = false;
        !           620: 
        !           621:        targetNodeNum = treePathTable[level].node;
        !           622:        targetNodePtr = targetNode->buffer;
        !           623:        PanicIf (targetNodePtr == nil, "\pDeleteTree: targetNode has nil buffer!");
        !           624: 
        !           625:        DeleteRecord (btreePtr, targetNodePtr, index);
        !           626:                
        !           627:        //�� coalesce remaining records?
        !           628: 
        !           629:        if ( targetNodePtr->numRecords == 0 )   // did we delete the last record?
        !           630:        {
        !           631:                BlockDescriptor         siblingNode;
        !           632:                UInt32                          siblingNodeNum;
        !           633: 
        !           634:                deleteRequired = true;
        !           635:                
        !           636:                ////////////////// Get Siblings & Update Links //////////////////////////
        !           637:                
        !           638:                siblingNodeNum = targetNodePtr->bLink;                          // Left Sibling Node
        !           639:                if ( siblingNodeNum != 0 )
        !           640:                {
        !           641:                        err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
        !           642:                        M_ExitOnError (err);
        !           643:                        ((NodeDescPtr)siblingNode.buffer)->fLink = targetNodePtr->fLink;
        !           644:                        err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction);
        !           645:                        M_ExitOnError (err);
        !           646:                }
        !           647:                else if ( targetNodePtr->kind == kBTLeafNode )          // update firstLeafNode
        !           648:                {
        !           649:                        btreePtr->firstLeafNode = targetNodePtr->fLink;
        !           650:                }
        !           651: 
        !           652:                siblingNodeNum = targetNodePtr->fLink;                          // Right Sibling Node
        !           653:                if ( siblingNodeNum != 0 )
        !           654:                {
        !           655:                        err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
        !           656:                        M_ExitOnError (err);
        !           657:                        ((NodeDescPtr)siblingNode.buffer)->bLink = targetNodePtr->bLink;
        !           658:                        err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction);
        !           659:                        M_ExitOnError (err);
        !           660:                }
        !           661:                else if ( targetNodePtr->kind == kBTLeafNode )          // update lastLeafNode
        !           662:                {
        !           663:                        btreePtr->lastLeafNode = targetNodePtr->bLink;
        !           664:                }
        !           665:                
        !           666:                //////////////////////// Free Empty Node ////////////////////////////////
        !           667: 
        !           668:                ClearNode (btreePtr, targetNodePtr);
        !           669:                
        !           670:                err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);
        !           671:                M_ExitOnError (err);
        !           672:                err = FreeNode (btreePtr, targetNodeNum);
        !           673:                M_ExitOnError (err);
        !           674:        }
        !           675:        else if ( index == 0 )                  // did we delete the first record?
        !           676:        {
        !           677:                updateRequired = true;          // yes, so we need to update parent
        !           678:        }
        !           679: 
        !           680: 
        !           681:        if ( level == btreePtr->treeDepth )             // then targetNode->buffer is the root node
        !           682:        {
        !           683:                deleteRequired = false;
        !           684:                updateRequired = false;
        !           685:                
        !           686:                if ( targetNode->buffer == nil )        // then root was freed and the btree is empty
        !           687:                {
        !           688:                        btreePtr->rootNode  = 0;
        !           689:                        btreePtr->treeDepth = 0;
        !           690:                }
        !           691:                else if ( ((NodeDescPtr)targetNode->buffer)->numRecords == 1 )
        !           692:                {
        !           693:                        err = CollapseTree (btreePtr, targetNode);
        !           694:                        M_ExitOnError (err);
        !           695:                }
        !           696:        }
        !           697: 
        !           698: 
        !           699:        if ( updateRequired || deleteRequired )
        !           700:        {
        !           701:                ++level;        // next level
        !           702: 
        !           703:                //// Get Parent Node and index
        !           704:                index = treePathTable [level].index;
        !           705:                err = GetNode (btreePtr, treePathTable[level].node, &parentNode);
        !           706:                M_ExitOnError (err);
        !           707: 
        !           708:                if ( updateRequired )
        !           709:                {
        !           710:                         KeyPtr         keyPtr;
        !           711:                         UInt8 *        recPtr;
        !           712:                         UInt16         recSize;
        !           713:                         UInt32         insertNode;
        !           714:                         
        !           715:                        //���debug: check if ptr == targetNodeNum
        !           716:                        GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
        !           717:                        PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p DeleteTree: parent ptr doesn't match targetNodeNum!!");
        !           718:                        
        !           719:                        // need to delete and re-insert this parent key/ptr
        !           720:                        DeleteRecord (btreePtr, parentNode.buffer, index);
        !           721:        
        !           722:                        keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
        !           723:                        recPtr = (UInt8 *) &targetNodeNum;
        !           724:                        recSize = sizeof(targetNodeNum);
        !           725:                        
        !           726:                        err = InsertTree (btreePtr, treePathTable, keyPtr, recPtr, recSize,
        !           727:                                                          &parentNode, index, level, kReplaceRecord, &insertNode);
        !           728:                        M_ExitOnError (err);
        !           729:                }
        !           730:                else // deleteRequired
        !           731:                {
        !           732:                        err = DeleteTree (btreePtr, treePathTable, &parentNode, index, level);
        !           733:                        M_ExitOnError (err);
        !           734:                }
        !           735:        }       
        !           736: 
        !           737: 
        !           738:        err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);
        !           739:        M_ExitOnError (err);
        !           740: 
        !           741:        return  noErr;
        !           742: 
        !           743: ErrorExit:
        !           744:        
        !           745:        (void) ReleaseNode (btreePtr, targetNode);
        !           746:        (void) ReleaseNode (btreePtr, &parentNode);
        !           747: 
        !           748:        return  err;
        !           749: 
        !           750: } // end DeleteTree
        !           751: 
        !           752: 
        !           753: 
        !           754: ///////////////////////////////// CollapseTree //////////////////////////////////
        !           755: 
        !           756: static OSStatus        CollapseTree    (BTreeControlBlockPtr           btreePtr,
        !           757:                                                                 BlockDescriptor                        *blockPtr )
        !           758: {
        !           759:        OSStatus                err;
        !           760:        UInt32                  originalRoot;
        !           761:        UInt32                  nodeNum;
        !           762:        
        !           763:        originalRoot    = btreePtr->rootNode;
        !           764:        
        !           765:        while (true)
        !           766:        {
        !           767:                if ( ((NodeDescPtr)blockPtr->buffer)->numRecords > 1)
        !           768:                        break;                                                  // this will make a fine root node
        !           769:                
        !           770:                if ( ((NodeDescPtr)blockPtr->buffer)->kind == kBTLeafNode)
        !           771:                        break;                                                  // we've hit bottom
        !           772:                
        !           773:                nodeNum                         = btreePtr->rootNode;
        !           774:                btreePtr->rootNode      = GetChildNodeNum (btreePtr, blockPtr->buffer, 0);
        !           775:                --btreePtr->treeDepth;
        !           776: 
        !           777:                //// Clear and Free Current Old Root Node ////
        !           778:                ClearNode (btreePtr, blockPtr->buffer);
        !           779:                err = UpdateNode (btreePtr, blockPtr, 0, kLockTransaction);
        !           780:                M_ExitOnError (err);
        !           781:                err = FreeNode (btreePtr, nodeNum);
        !           782:                M_ExitOnError (err);
        !           783:                
        !           784:                //// Get New Root Node
        !           785:                err = GetNode (btreePtr, btreePtr->rootNode, blockPtr);
        !           786:                M_ExitOnError (err);
        !           787:        }
        !           788:        
        !           789:        if (btreePtr->rootNode != originalRoot)
        !           790:                M_BTreeHeaderDirty (btreePtr);
        !           791:                
        !           792:        err = UpdateNode (btreePtr, blockPtr, 0, kLockTransaction);     // always update!
        !           793:        M_ExitOnError (err);
        !           794:        
        !           795:        return  noErr;
        !           796:        
        !           797: 
        !           798: /////////////////////////////////// ErrorExit ///////////////////////////////////
        !           799: 
        !           800: ErrorExit:
        !           801:        (void)  ReleaseNode (btreePtr, blockPtr);
        !           802:        return  err;
        !           803: }
        !           804: 
        !           805: 
        !           806: 
        !           807: ////////////////////////////////// RotateLeft ///////////////////////////////////
        !           808: 
        !           809: /*-------------------------------------------------------------------------------
        !           810: 
        !           811: Routine:       RotateLeft      -       One_line_description.
        !           812: 
        !           813: Function:      Brief_description_of_the_function_and_any_side_effects
        !           814: 
        !           815: Algorithm:     if rightIndex > insertIndex, subtract 1 for actual rightIndex
        !           816: 
        !           817: Input:         btreePtr                        - description
        !           818:                        leftNode                        - description
        !           819:                        rightNode                       - description
        !           820:                        rightInsertIndex        - description
        !           821:                        keyPtr                          - description
        !           822:                        recPtr                          - description
        !           823:                        recSize                         - description
        !           824:                        
        !           825: Output:                insertIndex
        !           826:                        insertNodeNum           - description
        !           827:                        recordFit                       - description
        !           828:                        recsRotated
        !           829:                        
        !           830: Result:                noErr           - success
        !           831:                        != noErr        - failure
        !           832: -------------------------------------------------------------------------------*/
        !           833: 
        !           834: static OSStatus        RotateLeft              (BTreeControlBlockPtr            btreePtr,
        !           835:                                                                 NodeDescPtr                             leftNode,
        !           836:                                                                 NodeDescPtr                             rightNode,
        !           837:                                                                 UInt16                                          rightInsertIndex,
        !           838:                                                                 KeyPtr                                          keyPtr,
        !           839:                                                                 UInt8 *                                         recPtr,
        !           840:                                                                 UInt16                                          recSize,
        !           841:                                                                 UInt16                                         *insertIndex,
        !           842:                                                                 UInt32                                         *insertNodeNum,
        !           843:                                                                 Boolean                                        *recordFit,
        !           844:                                                                 UInt16                                         *recsRotated )
        !           845: {
        !           846:        OSStatus                        err;
        !           847:        SInt32                          insertSize;
        !           848:        SInt32                          nodeSize;
        !           849:        SInt32                          leftSize, rightSize;
        !           850:        SInt32                          moveSize = 0;
        !           851:        UInt16                          keyLength;
        !           852:        UInt16                          lengthFieldSize;
        !           853:        UInt16                          index, moveIndex;
        !           854:        Boolean                         didItFit;
        !           855: 
        !           856:        ///////////////////// Determine If Record Will Fit //////////////////////////
        !           857:        
        !           858:        keyLength = GetKeyLength(btreePtr, keyPtr, (rightNode->kind == kBTLeafNode));
        !           859: 
        !           860:        // the key's length field is 8-bits in HFS and 16-bits in HFS+
        !           861:        if ( btreePtr->attributes & kBTBigKeysMask )
        !           862:                lengthFieldSize = sizeof(UInt16);
        !           863:        else
        !           864:                lengthFieldSize = sizeof(UInt8);
        !           865: 
        !           866:        insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16);
        !           867: 
        !           868:        if ( M_IsOdd (insertSize) )
        !           869:                ++insertSize;   // add pad byte;
        !           870: 
        !           871:        nodeSize                = btreePtr->nodeSize;
        !           872: 
        !           873:        // add size of insert record to right node
        !           874:        rightSize               = nodeSize - GetNodeFreeSize (btreePtr, rightNode) + insertSize;
        !           875:        leftSize                = nodeSize - GetNodeFreeSize (btreePtr, leftNode);
        !           876: 
        !           877:        moveIndex       = 0;
        !           878: 
        !           879:        while ( leftSize < rightSize )
        !           880:        {
        !           881:                if ( moveIndex < rightInsertIndex )
        !           882:                {
        !           883:                        moveSize = GetRecordSize (btreePtr, rightNode, moveIndex) + 2;
        !           884:                }
        !           885:                else if ( moveIndex == rightInsertIndex )
        !           886:                {
        !           887:                        moveSize = insertSize;
        !           888:                }
        !           889:                else // ( moveIndex > rightInsertIndex )
        !           890:                {
        !           891:                        moveSize = GetRecordSize (btreePtr, rightNode, moveIndex - 1) + 2;
        !           892:                }
        !           893:                
        !           894:                leftSize        += moveSize;
        !           895:                rightSize       -= moveSize;
        !           896:                ++moveIndex;
        !           897:        }       
        !           898:        
        !           899:        if ( leftSize > nodeSize )      // undo last move
        !           900:        {
        !           901:                leftSize        -= moveSize;
        !           902:                rightSize       += moveSize;
        !           903:                --moveIndex;
        !           904:        }
        !           905:        
        !           906:        if ( rightSize > nodeSize )     // record won't fit - failure, but not error
        !           907:        {
        !           908:                *insertIndex    = 0;
        !           909:                *insertNodeNum  = 0;
        !           910:                *recordFit              = false;
        !           911:                *recsRotated    = 0;
        !           912:                
        !           913:                return  noErr;
        !           914:        }
        !           915:        
        !           916:        // we've found balance point, moveIndex == number of records moved into leftNode
        !           917:        
        !           918: 
        !           919:        //////////////////////////// Rotate Records /////////////////////////////////
        !           920: 
        !           921:        *recsRotated    = moveIndex;
        !           922:        *recordFit              = true;
        !           923:        index                   = 0;
        !           924: 
        !           925:        while ( index < moveIndex )
        !           926:        {
        !           927:                if ( index == rightInsertIndex )        // insert new record in left node
        !           928:                {
        !           929:                        UInt16  leftInsertIndex;
        !           930:                        
        !           931:                        leftInsertIndex = leftNode->numRecords;
        !           932: 
        !           933:                        didItFit = InsertKeyRecord (btreePtr, leftNode, leftInsertIndex,
        !           934:                                                                                keyPtr, keyLength, recPtr, recSize);
        !           935:                        if ( !didItFit )
        !           936:                        {
        !           937:                                Panic ("\pRotateLeft: InsertKeyRecord (left) returned false!");
        !           938:                                err = fsBTBadRotateErr;
        !           939:                                goto ErrorExit;
        !           940:                        }
        !           941:                        
        !           942:                        *insertIndex = leftInsertIndex;
        !           943:                        *insertNodeNum = rightNode->bLink;
        !           944:                }
        !           945:                else
        !           946:                {
        !           947:                        didItFit = RotateRecordLeft (btreePtr, leftNode, rightNode);
        !           948:                        if ( !didItFit )
        !           949:                        {
        !           950:                                Panic ("\pRotateLeft: RotateRecordLeft returned false!");
        !           951:                                err = fsBTBadRotateErr;
        !           952:                                goto ErrorExit;
        !           953:                        }
        !           954:                }
        !           955:                
        !           956:                ++index;
        !           957:        }
        !           958:        
        !           959:        if ( moveIndex <= rightInsertIndex )    // then insert new record in right node
        !           960:        {
        !           961:                rightInsertIndex -= index;                      // adjust for records already rotated
        !           962:                
        !           963:                didItFit = InsertKeyRecord (btreePtr, rightNode, rightInsertIndex,
        !           964:                                                                        keyPtr, keyLength, recPtr, recSize);
        !           965:                if ( !didItFit )
        !           966:                {
        !           967:                        Panic ("\pRotateLeft: InsertKeyRecord (right) returned false!");
        !           968:                        err = fsBTBadRotateErr;
        !           969:                        goto ErrorExit;
        !           970:                }
        !           971:        
        !           972:                *insertIndex = rightInsertIndex;
        !           973:                *insertNodeNum = leftNode->fLink;
        !           974:        }
        !           975: 
        !           976: 
        !           977:        return noErr;
        !           978: 
        !           979: 
        !           980:        ////////////////////////////// Error Exit ///////////////////////////////////
        !           981: 
        !           982: ErrorExit:
        !           983: 
        !           984:        *insertIndex    = 0;
        !           985:        *insertNodeNum  = 0;
        !           986:        *recordFit              = false;
        !           987:        *recsRotated    = 0;
        !           988:        
        !           989:        return  err;
        !           990: }
        !           991: 
        !           992: 
        !           993: 
        !           994: /////////////////////////////////// SplitLeft ///////////////////////////////////
        !           995: 
        !           996: static OSStatus        SplitLeft               (BTreeControlBlockPtr            btreePtr,
        !           997:                                                                 BlockDescriptor                        *leftNode,
        !           998:                                                                 BlockDescriptor                        *rightNode,
        !           999:                                                                 UInt32                                          rightNodeNum,
        !          1000:                                                                 UInt16                                          index,
        !          1001:                                                                 KeyPtr                                          keyPtr,
        !          1002:                                                                 UInt8 *                                         recPtr,
        !          1003:                                                                 UInt16                                          recSize,
        !          1004:                                                                 UInt16                                         *insertIndex,
        !          1005:                                                                 UInt32                                         *insertNodeNum,
        !          1006:                                                                 UInt16                                         *recsRotated )
        !          1007: {
        !          1008:        OSStatus                        err;
        !          1009:        NodeDescPtr                     left, right;
        !          1010:        UInt32                          newNodeNum;
        !          1011:        Boolean                         recordFit;
        !          1012:        
        !          1013:        
        !          1014:        ///////////////////////////// Compare Nodes /////////////////////////////////
        !          1015: 
        !          1016:        right = rightNode->buffer;
        !          1017:        left  = leftNode->buffer;
        !          1018:        
        !          1019:        PanicIf ( right->bLink != 0 && left == 0, "\p SplitLeft: left sibling missing!?" );
        !          1020:        
        !          1021:        /* type should be kBTLeafNode or kBTIndexNode */
        !          1022:        
        !          1023:        if ( (right->height == 1) && (right->kind != kBTLeafNode) )
        !          1024:                return  fsBTInvalidNodeErr;
        !          1025:        
        !          1026:        if ( left != nil )
        !          1027:        {
        !          1028:                if ( left->fLink != rightNodeNum )
        !          1029:                        return fsBTInvalidNodeErr;                                                                              //�� E_BadSibling ?
        !          1030:        
        !          1031:                if ( left->height != right->height )
        !          1032:                        return  fsBTInvalidNodeErr;                                                                             //�� E_BadNodeHeight ?
        !          1033:                
        !          1034:                if ( left->kind != right->kind )
        !          1035:                        return  fsBTInvalidNodeErr;                                                                             //�� E_BadNodeType ?
        !          1036:        }
        !          1037:        
        !          1038: 
        !          1039:        ///////////////////////////// Allocate Node /////////////////////////////////
        !          1040: 
        !          1041:        err = AllocateNode (btreePtr, &newNodeNum);
        !          1042:        M_ExitOnError (err);
        !          1043:        
        !          1044: 
        !          1045:        /////////////// Update Forward Link In Original Left Node ///////////////////
        !          1046: 
        !          1047:        if ( left != nil )
        !          1048:        {
        !          1049:                left->fLink     = newNodeNum;
        !          1050:                err = UpdateNode (btreePtr, leftNode, 0, kLockTransaction);
        !          1051:                M_ExitOnError (err);
        !          1052:        }
        !          1053: 
        !          1054: 
        !          1055:        /////////////////////// Initialize New Left Node ////////////////////////////
        !          1056: 
        !          1057:        err = GetNewNode (btreePtr, newNodeNum, leftNode);
        !          1058:        M_ExitOnError (err);
        !          1059:        
        !          1060:        left            = leftNode->buffer;
        !          1061:        left->fLink     = rightNodeNum;
        !          1062:        
        !          1063: 
        !          1064:        // Steal Info From Right Node
        !          1065:        
        !          1066:        left->bLink  = right->bLink;
        !          1067:        left->kind   = right->kind;
        !          1068:        left->height = right->height;
        !          1069:        
        !          1070:        right->bLink            = newNodeNum;                   // update Right bLink
        !          1071: 
        !          1072:        if ( (left->kind == kBTLeafNode) && (left->bLink == 0) )
        !          1073:        {
        !          1074:                // if we're adding a new first leaf node - update BTreeInfoRec
        !          1075:                
        !          1076:                btreePtr->firstLeafNode = newNodeNum;
        !          1077:                M_BTreeHeaderDirty (btreePtr);          //�� AllocateNode should have set the bit already...
        !          1078:        }
        !          1079: 
        !          1080:        ////////////////////////////// Rotate Left //////////////////////////////////
        !          1081: 
        !          1082:        err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize,
        !          1083:                                          insertIndex, insertNodeNum, &recordFit, recsRotated);
        !          1084:        M_ExitOnError (err);
        !          1085:        
        !          1086:        return noErr;
        !          1087:        
        !          1088: ErrorExit:
        !          1089:        
        !          1090:        (void) ReleaseNode (btreePtr, leftNode);
        !          1091:        (void) ReleaseNode (btreePtr, rightNode);
        !          1092:        
        !          1093:        //�� Free new node if allocated?
        !          1094: 
        !          1095:        *insertIndex    = 0;
        !          1096:        *insertNodeNum  = 0;
        !          1097:        *recsRotated    = 0;
        !          1098:        
        !          1099:        return  err;
        !          1100: }
        !          1101: 
        !          1102: 
        !          1103: 
        !          1104: /////////////////////////////// RotateRecordLeft ////////////////////////////////
        !          1105: 
        !          1106: static Boolean RotateRecordLeft (BTreeControlBlockPtr          btreePtr,
        !          1107:                                                                 NodeDescPtr                            leftNode,
        !          1108:                                                                 NodeDescPtr                            rightNode )
        !          1109: {
        !          1110:        UInt16          size;
        !          1111:        UInt8 *         recPtr;
        !          1112:        Boolean         recordFit;
        !          1113:        
        !          1114:        size    = GetRecordSize (btreePtr, rightNode, 0);
        !          1115:        recPtr  = GetRecordAddress (btreePtr, rightNode, 0);
        !          1116:        
        !          1117:        recordFit = InsertRecord (btreePtr, leftNode, leftNode->numRecords, recPtr, size);
        !          1118:        
        !          1119:        if ( !recordFit )
        !          1120:                return false;
        !          1121:        
        !          1122:        DeleteRecord (btreePtr, rightNode, 0);
        !          1123:        
        !          1124:        return true;
        !          1125: }
        !          1126: 
        !          1127: 
        !          1128: //////////////////////////////// AddNewRootNode /////////////////////////////////
        !          1129: 
        !          1130: static OSStatus        AddNewRootNode  (BTreeControlBlockPtr    btreePtr,
        !          1131:                                                                 NodeDescPtr                     leftNode,
        !          1132:                                                                 NodeDescPtr                     rightNode )
        !          1133: {
        !          1134:        OSStatus                        err;
        !          1135:        BlockDescriptor         rootNode;
        !          1136:        UInt32                          rootNum;
        !          1137:        KeyPtr                          keyPtr;
        !          1138:        Boolean                         didItFit;
        !          1139:        UInt16                          keyLength;      
        !          1140:        
        !          1141:        PanicIf (leftNode == nil, "\pAddNewRootNode: leftNode == nil");
        !          1142:        PanicIf (rightNode == nil, "\pAddNewRootNode: rightNode == nil");
        !          1143:        
        !          1144:        
        !          1145:        /////////////////////// Initialize New Root Node ////////////////////////////
        !          1146:        
        !          1147:        err = AllocateNode (btreePtr, &rootNum);
        !          1148:        M_ExitOnError (err);
        !          1149:        
        !          1150:        err = GetNewNode (btreePtr, rootNum, &rootNode);
        !          1151:        M_ExitOnError (err);
        !          1152:                
        !          1153:        ((NodeDescPtr)rootNode.buffer)->kind = kBTIndexNode;
        !          1154:        ((NodeDescPtr)rootNode.buffer)->height  = ++btreePtr->treeDepth;
        !          1155:        
        !          1156: 
        !          1157:        ///////////////////// Insert Left Node Index Record /////////////////////////   
        !          1158: 
        !          1159:        keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode, 0);
        !          1160:        keyLength = GetKeyLength(btreePtr, keyPtr, false);
        !          1161: 
        !          1162:        didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 0, keyPtr, keyLength,
        !          1163:                                                                 (UInt8 *) &rightNode->bLink, 4 );
        !          1164: 
        !          1165:        PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for left index record");
        !          1166: 
        !          1167: 
        !          1168:        //////////////////// Insert Right Node Index Record /////////////////////////
        !          1169: 
        !          1170:        keyPtr = (KeyPtr) GetRecordAddress (btreePtr, rightNode, 0);
        !          1171:        keyLength = GetKeyLength(btreePtr, keyPtr, false);
        !          1172: 
        !          1173:        didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 1, keyPtr, keyLength,
        !          1174:                                                                 (UInt8 *) &leftNode->fLink, 4 );
        !          1175: 
        !          1176:        PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for right index record");
        !          1177: 
        !          1178:        
        !          1179:        /////////////////////////// Release Root Node ///////////////////////////////
        !          1180:        
        !          1181:        err = UpdateNode (btreePtr, &rootNode, 0, kLockTransaction);
        !          1182:        M_ExitOnError (err);
        !          1183:        
        !          1184:        // update BTreeInfoRec
        !          1185:        
        !          1186:        btreePtr->rootNode       = rootNum;
        !          1187:        btreePtr->flags         |= kBTHeaderDirty;
        !          1188:        
        !          1189:        return noErr;
        !          1190: 
        !          1191: 
        !          1192:        ////////////////////////////// Error Exit ///////////////////////////////////
        !          1193: 
        !          1194: ErrorExit:
        !          1195: 
        !          1196:        return  err;
        !          1197: }
        !          1198: 
        !          1199: 
        !          1200: static UInt16  GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode )
        !          1201: {
        !          1202:        UInt16 length;
        !          1203: 
        !          1204:        if ( forLeafNode || btreePtr->attributes & kBTVariableIndexKeysMask )
        !          1205:                length = KeyLength (btreePtr, key);             // just use actual key length
        !          1206:        else
        !          1207:                length = btreePtr->maxKeyLength;                // fixed sized index key (i.e. HFS)             //�� shouldn't we clear the pad bytes?
        !          1208: 
        !          1209:        return length;
        !          1210: }
        !          1211: 

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