Return to BTreeTreeOps.c CVS log

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

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

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