Logo Search packages:      
Sourcecode: hfsprogs version File versions  Download package

BTreeTreeOps.c

/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * "Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
 * Reserved.  This file contains Original Code and/or Modifications of
 * Original Code as defined in and that are subject to the Apple Public
 * Source License Version 1.0 (the 'License').  You may not use this file
 * except in compliance with the License.  Please obtain a copy of the
 * License at http://www.apple.com/publicsource and read it before using
 * this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License."
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*
      File:       BTreeTreeOps.c

      Contains:   Multi-node tree operations for the BTree Module.

      Version:    xxx put the technology version here xxx

      Written by: Gordon Sheridan and Bill Bruffey

      Copyright:  © 1992-1997, 1999 by Apple Computer, Inc., all rights reserved.
*/

#include "BTreePrivate.h"

#define DEBUG_TREEOPS 0

/////////////////////// Routines Internal To BTree Module ///////////////////////
//
//    SearchTree
//    InsertTree
//
////////////////////// Routines Internal To BTreeTreeOps.c //////////////////////

static OSStatus   AddNewRootNode    (BTreeControlBlockPtr          btreePtr,
                                                       NodeDescPtr                         leftNode,
                                                       NodeDescPtr                         rightNode );

static OSStatus   CollapseTree            (BTreeControlBlockPtr          btreePtr,
                                                       BlockDescriptor              *blockPtr );

static OSStatus   RotateLeft        (BTreeControlBlockPtr          btreePtr,
                                                       NodeDescPtr                         leftNode,
                                                       NodeDescPtr                         rightNode,
                                                       UInt16                                    rightInsertIndex,
                                                       KeyPtr                                    keyPtr,
                                                       UInt8 *                             recPtr,
                                                       UInt16                                    recSize,
                                                       UInt16                                   *insertIndex,
                                                       UInt32                                   *insertNodeNum,
                                                       Boolean                            *recordFit,
                                                       UInt16                                   *recsRotated );

static Boolean       RotateRecordLeft     (BTreeControlBlockPtr          btreePtr,
                                                       NodeDescPtr                         leftNode,
                                                       NodeDescPtr                         rightNode );

#if 0 
static OSStatus      SplitLeft            (BTreeControlBlockPtr          btreePtr,
                                                       BlockDescriptor              *leftNode,
                                                       BlockDescriptor              *rightNode,
                                                       UInt32                                    rightNodeNum,
                                                       UInt16                                    index,
                                                       KeyPtr                                    keyPtr,
                                                       UInt8 *                             recPtr,
                                                       UInt16                                    recSize,
                                                       UInt16                                   *insertIndex,
                                                       UInt32                                   *insertNodeNum,
                                                       UInt16                                   *recsRotated );
#endif


static      OSStatus    InsertLevel       (BTreeControlBlockPtr          btreePtr,
                                                       TreePathTable                       treePathTable,
                                                       InsertKey                          *primaryKey,
                                                       InsertKey                          *secondaryKey,
                                                       BlockDescriptor              *targetNode,
                                                       UInt16                                    index,
                                                       UInt16                                    level,
                                                       UInt32                                   *insertNode );
                                     
static OSErr            InsertNode        (BTreeControlBlockPtr          btreePtr,
                                                       InsertKey                          *key,
                                                       BlockDescriptor              *targetNode,
                                                       UInt32                                    node,
                                                       UInt16                                    index,
                                                       UInt32                                   *newNode,   
                                                       UInt16                                   *newIndex,
                                                       BlockDescriptor              *leftNode,
                                                       Boolean                            *updateParent,
                                                       Boolean                            *insertParent,
                                                       Boolean                            *rootSplit );
                                                       
static UInt16           GetKeyLength      (const BTreeControlBlock *btreePtr,
                                                       const BTreeKey *key,
                                                       Boolean forLeafNode );

static Boolean          RotateRecordRight(      BTreeControlBlockPtr          btreePtr,
                                                            NodeDescPtr                   leftNode,
                                                            NodeDescPtr                   rightNode );
                                                            
static OSStatus         RotateRight(      BTreeControlBlockPtr           btreePtr,
                                                      NodeDescPtr                          leftNode,
                                                      NodeDescPtr                          rightNode,
                                                      UInt16                                     leftInsertIndex,
                                                      KeyPtr                                     keyPtr,
                                                      UInt8 *                                    recPtr,
                                                      UInt16                                     recSize,
                                                      UInt16                                    *insertIndex,
                                                      UInt32                                    *insertNodeNum,
                                                      Boolean                                   *recordFit,
                                                      UInt16                                    *recsRotated );
                                                      
static OSStatus         SplitRight(       BTreeControlBlockPtr           btreePtr,
                                                      BlockDescriptor                     *nodePtr,
                                                      BlockDescriptor                     *rightNodePtr,
                                                      UInt32                                     nodeNum,
                                                      UInt16                                     index,
                                                      KeyPtr                                     keyPtr,
                                                      UInt8                                     *recPtr,
                                                      UInt16                                     recSize,
                                                      UInt16                                    *insertIndexPtr,
                                                      UInt32                                    *newNodeNumPtr,
                                                      UInt16                                    *recsRotatedPtr );

#if DEBUG_TREEOPS
static int DoKeyCheck( NodeDescPtr nodeP, BTreeControlBlock *btcb );
static int  DoKeyCheckAcrossNodes(  NodeDescPtr theLeftNodePtr, 
                                                      NodeDescPtr theRightNodePtr, 
                                                      BTreeControlBlock *theTreePtr,
                                                      Boolean printKeys );
static void PrintNodeDescriptor( NodeDescPtr  thePtr );
static void PrintKey( UInt8 *  myPtr, int mySize );
#endif // DEBUG_TREEOPS


/* used by InsertLevel (and called routines) to communicate the state of an insert operation */
enum
{
      kInsertParent                 = 0x0001,
      kUpdateParent                 = 0x0002,
      kNewRoot                      = 0x0004,
      kInsertedInRight        = 0x0008,
      kRecordFits                   = 0x0010
};


//////////////////////// BTree Multi-node Tree Operations ///////////////////////


/*-------------------------------------------------------------------------------

Routine:    SearchTree  -     Search BTree for key and set up Tree Path Table.

Function:   Searches BTree for specified key, setting up the Tree Path Table to
                  reflect the search path.


Input:            btreePtr          - pointer to control block of BTree to search
                  keyPtr                  - pointer to the key to search for
                  treePathTable     - pointer to the tree path table to construct
                  
Output:           nodeNum                 - number of the node containing the key position
                  iterator          - BTreeIterator specifying record or insert position
                  
Result:           noErr             - key found, index is record index
                  fsBTRecordNotFoundErr   - key not found, index is insert index
                  fsBTEmptyErr            - key not found, return params are nil
                  otherwise               - catastrophic failure (GetNode/ReleaseNode failed)
-------------------------------------------------------------------------------*/

OSStatus    SearchTree  (BTreeControlBlockPtr    btreePtr,
                                     BTreeKeyPtr                   searchKey,
                                     TreePathTable                 treePathTable,
                                     UInt32                             *nodeNum,
                                     BlockDescriptor        *nodePtr,
                                     UInt16                             *returnIndex )
{
      OSStatus    err;
      SInt16            level;
      UInt32            curNodeNum;
      NodeRec           nodeRec;
      UInt16            index;
      Boolean           keyFound;
      SInt8       nodeKind;                     //    Kind of current node (index/leaf)
      KeyPtr            keyPtr;
      UInt8 *           dataPtr;
      UInt16            dataSize;
      
      
      curNodeNum        = btreePtr->rootNode;
      level             = btreePtr->treeDepth;
      
      if (level == 0)                                 // is the tree empty?
      {
            err = fsBTEmptyErr;
            goto ErrorExit;
      }
      
      //„„ for debugging...
      treePathTable [0].node        = 0;
      treePathTable [0].index       = 0;

      while (true)
      {
        //
        //  [2550929] Node number 0 is the header node.  It is never a valid
        //  index or leaf node.  If we're ever asked to search through node 0,
        //  something has gone wrong (typically a bad child node number, or
        //  we found a node full of zeroes that we thought was an index node).
        //
        if (curNodeNum == 0)
        {
//          Panic("\pSearchTree: curNodeNum is zero!");
            err = fsBTInvalidNodeErr;
            goto ErrorExit;
        }

            err = GetNode (btreePtr, curNodeNum, &nodeRec);
            if (err != noErr)
            {
                  goto ErrorExit;
            }

        //
        //  [2550929] Sanity check the node height and node type.  We expect
        //  particular values at each iteration in the search.  This checking
        //  quickly finds bad pointers, loops, and other damage to the
        //  hierarchy of the B-tree.
        //
        if (((BTNodeDescriptor*)nodeRec.buffer)->height != level)
        {
                err = fsBTInvalidNodeErr;
                goto ReleaseAndExit;
        }
        nodeKind = ((BTNodeDescriptor*)nodeRec.buffer)->kind;
        if (level == 1)
        {
            //    Nodes at level 1 must be leaves, by definition
            if (nodeKind != kBTLeafNode)
            {
                err = fsBTInvalidNodeErr;
                goto ReleaseAndExit;           
            }
        }
        else
        {
            //    A node at any other depth must be an index node
            if (nodeKind != kBTIndexNode)
            {
                err = fsBTInvalidNodeErr;
                goto ReleaseAndExit;
            }
        }
                  
            keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index);

            treePathTable [level].node          = curNodeNum;

        if (nodeKind == kBTLeafNode)
            {
                  treePathTable [level].index = index;
                  break;                  // were done...
            }
            
            if ( (keyFound != true) && (index != 0))
                  --index;

            treePathTable [level].index = index;
            
            err = GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize);
        if (err != noErr)
        {
            //    [2550929] If we got an error, it is probably because the index was bad
            //    (typically a corrupt node that confused SearchNode).  Invalidate the node
            //    so we won't accidentally use the corrupted contents.  NOTE: the Mac OS 9
            //    sources call this InvalidateNode.
            
                (void) TrashNode(btreePtr, &nodeRec);
                goto ErrorExit;
        }

        //  Get the child pointer out of this index node.  We're now done with the current
        //  node and can continue the search with the child node.
            curNodeNum = *(UInt32 *)dataPtr;
            err = ReleaseNode (btreePtr, &nodeRec);
            if (err != noErr)
            {
                  goto ErrorExit;
            }
        
        //  The child node should be at a level one less than the parent.
        --level;
      }
      
      *nodeNum                = curNodeNum;
      *nodePtr                = nodeRec;
      *returnIndex            = index;

      if (keyFound)
            return      noErr;                  // searchKey found, index identifies record in node
      else
            return      fsBTRecordNotFoundErr;  // searchKey not found, index identifies insert point

ReleaseAndExit:
    (void) ReleaseNode(btreePtr, &nodeRec);
    //      fall into ErrorExit

ErrorExit:
      
      *nodeNum                            = 0;
      nodePtr->buffer                     = nil;
      nodePtr->blockHeader          = nil;
      *returnIndex                        = 0;

      return      err;
}




////////////////////////////////// InsertTree ///////////////////////////////////

OSStatus    InsertTree ( BTreeControlBlockPtr          btreePtr,
                                     TreePathTable                       treePathTable,
                                     KeyPtr                                    keyPtr,
                                     UInt8 *                             recPtr,
                                     UInt16                                    recSize,
                                     BlockDescriptor              *targetNode,
                                     UInt16                                    index,
                                     UInt16                                    level,
                                     Boolean                             replacingKey,
                                     UInt32                                   *insertNode )
{
      InsertKey               primaryKey;
      OSStatus                err;

      primaryKey.keyPtr       = keyPtr;
      primaryKey.keyLength    = GetKeyLength(btreePtr, primaryKey.keyPtr, (level == 1));
      primaryKey.recPtr       = recPtr;
      primaryKey.recSize            = recSize;
      primaryKey.replacingKey = replacingKey;
      primaryKey.skipRotate   = false;

      err   = InsertLevel (btreePtr, treePathTable, &primaryKey, nil,
                                 targetNode, index, level, insertNode );
                                    
      return err;

} // End of InsertTree


////////////////////////////////// InsertLevel //////////////////////////////////

OSStatus    InsertLevel (BTreeControlBlockPtr          btreePtr,
                                     TreePathTable                       treePathTable,
                                     InsertKey                          *primaryKey,
                                     InsertKey                          *secondaryKey,
                                     BlockDescriptor              *targetNode,
                                     UInt16                                    index,
                                     UInt16                                    level,
                                     UInt32                                   *insertNode )
{
      OSStatus                 err;
      BlockDescriptor          siblingNode;
      UInt32                         targetNodeNum;
      UInt32                         newNodeNum;
      UInt16                         newIndex;
      Boolean                        insertParent;
      Boolean                        updateParent;
      Boolean                        newRoot;

#if defined(applec) && !defined(__SC__)
      PanicIf ((level == 1) && (((NodeDescPtr)targetNode->buffer)->kind != kBTLeafNode), "\P InsertLevel: non-leaf at level 1! ");
#endif
      siblingNode.buffer = nil;
      targetNodeNum = treePathTable [level].node;

      insertParent = false;
      updateParent = false;
      
      ////// process first insert //////
      
      err = InsertNode (btreePtr, primaryKey, targetNode, targetNodeNum, index,
                                &newNodeNum, &newIndex, &siblingNode, &updateParent, &insertParent, &newRoot );
      M_ExitOnError (err);

      if ( newRoot )
      {
            // Extend the treePathTable by adding an entry for the new
            // root node that references the current targetNode.
            // 
            // When we split right the index in the new root is 0 if the new
            // node is the same as the target node or 1 otherwise.  When the
            // new node number and the target node number are the same then
            // we inserted the new record into the left node (the orignial target)
            // after the split.

            treePathTable [level + 1].node  = btreePtr->rootNode;
            if ( targetNodeNum == newNodeNum )
                  treePathTable [level + 1].index = 0;  // 
            else
                  treePathTable [level + 1].index = 1;
      }
      
      if ( level == 1 )
            *insertNode = newNodeNum;           
      
      ////// process second insert (if any) //////

      if  ( secondaryKey != nil )
      {
            Boolean                       temp;

            // NOTE - we only get here if we have split a child node to the right and 
            // we are currently updating the child's parent.   newIndex + 1 refers to
            // the location in the parent node where we insert the new index record that
            // represents the new child node (the new right node). 
            err = InsertNode (btreePtr, secondaryKey, targetNode, newNodeNum, newIndex + 1,
                                      &newNodeNum, &newIndex, &siblingNode, &updateParent, &insertParent, &temp);
            M_ExitOnError (err);
            
            if ( DEBUG_BUILD && updateParent && newRoot )
                  DebugStr("\p InsertLevel: New root from primary key, update from secondary key...");
      }

      //////////////////////// Update Parent(s) ///////////////////////////////

      if ( insertParent || updateParent )
      {
            BlockDescriptor         parentNode;
            UInt32                        parentNodeNum;
            KeyPtr                        keyPtr;
            UInt8 *                       recPtr;
            UInt16                        recSize;
            
            secondaryKey = nil;
            
            PanicIf ( (level == btreePtr->treeDepth), "\p InsertLevel: unfinished insert!?");

            ++level;

            // Get Parent Node data...
            index = treePathTable [level].index;
            parentNodeNum = treePathTable [level].node;

            PanicIf ( parentNodeNum == 0, "\p InsertLevel: parent node is zero!?");

            err = GetNode (btreePtr, parentNodeNum, &parentNode); // released as target node in next level up
            M_ExitOnError (err);
#if defined(applec) && !defined(__SC__)
            if (DEBUG_BUILD && level > 1)
                  PanicIf ( ((NodeDescPtr)parentNode.buffer)->kind != kBTIndexNode, "\P InsertLevel: parent node not an index node! ");
#endif
            ////////////////////////// Update Parent Index //////////////////////////////
      
            if ( updateParent )
            {
                  //„„Źdebug: check if ptr == targetNodeNum
                  GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
                  PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p InsertLevel: parent ptr doesn't match target node!");
                  
                  // need to delete and re-insert this parent key/ptr
                  // we delete it here and it gets re-inserted in the
                  // InsertLevel call below.
                  DeleteRecord (btreePtr, parentNode.buffer, index);
      
                  primaryKey->keyPtr             = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
                  primaryKey->keyLength    = GetKeyLength(btreePtr, primaryKey->keyPtr, false);
                  primaryKey->recPtr             = (UInt8 *) &targetNodeNum;
                  primaryKey->recSize            = sizeof(targetNodeNum);
                  primaryKey->replacingKey = kReplaceRecord;
                  primaryKey->skipRotate   = insertParent;        // don't rotate left if we have two inserts occuring
            }
      
            ////////////////////////// Add New Parent Index /////////////////////////////
      
            if ( insertParent )
            {
                  InsertKey   *insertKeyPtr;
                  InsertKey   insertKey;
                  
                  if ( updateParent )
                  {
                        insertKeyPtr = &insertKey;
                        secondaryKey = &insertKey;
                  }
                  else
                  {
                        insertKeyPtr = primaryKey;
                        // split right but not updating parent for our left node then 
                        // we want to insert the key for the new right node just after 
                        // the key for our left node.
                        index++;
                  }
                  
                  insertKeyPtr->keyPtr          = (KeyPtr) GetRecordAddress (btreePtr, siblingNode.buffer, 0);
                  insertKeyPtr->keyLength       = GetKeyLength(btreePtr, insertKeyPtr->keyPtr, false);
                  insertKeyPtr->recPtr          = (UInt8 *) &((NodeDescPtr)targetNode->buffer)->fLink;
                  insertKeyPtr->recSize         = sizeof(UInt32);
                  insertKeyPtr->replacingKey    = kInsertRecord;
                  insertKeyPtr->skipRotate      = false;          // a rotate is OK during second insert
            }     
            
            err = InsertLevel (btreePtr, treePathTable, primaryKey, secondaryKey,
                                       &parentNode, index, level, insertNode );
            M_ExitOnError (err);
      }

      err = UpdateNode (btreePtr, targetNode);  // all done with target
      M_ExitOnError (err);

      err = UpdateNode (btreePtr, &siblingNode);            // all done with left sibling
      M_ExitOnError (err);

      return      noErr;

ErrorExit:

      (void) ReleaseNode (btreePtr, targetNode);
      (void) ReleaseNode (btreePtr, &siblingNode);

      Panic ("\p InsertLevel: an error occured!");

      return      err;

} // End of InsertLevel



////////////////////////////////// InsertNode ///////////////////////////////////

static OSErr      InsertNode  (BTreeControlBlockPtr    btreePtr,
                                           InsertKey                    *key,

                                           BlockDescriptor        *targetNode,
                                           UInt32                              nodeNum,
                                           UInt16                              index,

                                           UInt32                             *newNodeNumPtr,   
                                           UInt16                             *newIndex,

                                           BlockDescriptor        *siblingNode,
                                           Boolean                      *updateParent,
                                           Boolean                      *insertParent,
                                           Boolean                      *rootSplit )
{
      BlockDescriptor         *tempNode;
      UInt32                         leftNodeNum;
      UInt32                         rightNodeNum;
      UInt16                         recsRotated;
      OSErr                    err;
      Boolean                        recordFit;

      *rootSplit = false;
      
      PanicIf ( targetNode->buffer == siblingNode->buffer, "\p InsertNode: targetNode == siblingNode, huh?");
      
      leftNodeNum = ((NodeDescPtr) targetNode->buffer)->bLink;
      rightNodeNum = ((NodeDescPtr) targetNode->buffer)->fLink;


      /////////////////////// Try Simple Insert ///////////////////////////////

      if ( nodeNum == leftNodeNum )
            tempNode = siblingNode;
      else
            tempNode = targetNode;

      recordFit = InsertKeyRecord (btreePtr, tempNode->buffer, index, key->keyPtr, key->keyLength, key->recPtr, key->recSize);

      if ( recordFit )
      {
            *newNodeNumPtr  = nodeNum;
            *newIndex = index;
      
#if DEBUG_TREEOPS
            if ( DoKeyCheck( tempNode->buffer, btreePtr ) != noErr )
            {
                  printf( "\n%s - bad key order in node num %d: \n", __FUNCTION__ , nodeNum );
                  PrintNodeDescriptor( tempNode->buffer );
                  err = fsBTBadRotateErr;
                  goto ErrorExit;
            }
#endif // DEBUG_TREEOPS

            if ( (index == 0) && (((NodeDescPtr) tempNode->buffer)->height != btreePtr->treeDepth) )
                  *updateParent = true;   // the first record changed so we need to update the parent
            goto ExitThisRoutine;
      }


      //////////////////////// Try Rotate Left ////////////////////////////////
      
      if ( leftNodeNum > 0 )
      {
            PanicIf ( siblingNode->buffer != nil, "\p InsertNode: siblingNode already aquired!");

            if ( siblingNode->buffer == nil )
            {
                  err = GetNode (btreePtr, leftNodeNum, siblingNode);   // will be released by caller or a split below
                  M_ExitOnError (err);
            }

            PanicIf ( ((NodeDescPtr) siblingNode->buffer)->fLink != nodeNum, "\p InsertNode, RotateLeft: invalid sibling link!" );

            if ( !key->skipRotate )       // are rotates allowed?
            {
                  err = RotateLeft (btreePtr, siblingNode->buffer, targetNode->buffer, index, key->keyPtr, key->recPtr,
                                            key->recSize, newIndex, newNodeNumPtr, &recordFit, &recsRotated );    
                  M_ExitOnError (err);

                  if ( recordFit )
                  {
                        if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
                              *updateParent = true;               
                        goto ExitThisRoutine;
                  }
            }
      }     


      //////////////////////// Try Split Right /////////////////////////////////

      (void) ReleaseNode( btreePtr, siblingNode );
      err = SplitRight( btreePtr, targetNode, siblingNode, nodeNum, index, key->keyPtr,
                                key->recPtr, key->recSize, newIndex, newNodeNumPtr, &recsRotated );
      M_ExitOnError (err);

      // if we split root node - add new root
      if ( ((NodeDescPtr) targetNode->buffer)->height == btreePtr->treeDepth )
      {
            err = AddNewRootNode( btreePtr, targetNode->buffer, siblingNode->buffer );    // Note: does not update TPT
            M_ExitOnError (err);
            *rootSplit = true;
      }
      else
      {
            *insertParent = true;

            // update parent index node when replacingKey is true or when
            // we inserted a new record at the beginning of our target node.
            if ( key->replacingKey || ( index == 0 && *newIndex == 0 ) )
                  *updateParent = true;
      }
      
ExitThisRoutine:

      return noErr;

ErrorExit:

      (void) ReleaseNode (btreePtr, siblingNode);
      return err;
      
} // End of InsertNode


/*-------------------------------------------------------------------------------
Routine:    DeleteTree  -     One_line_description.

Function:   Brief_description_of_the_function_and_any_side_effects

ToDo:       

Input:            btreePtr          - description
                  treePathTable     - description
                  targetNode        - description
                  index             - description
                                    
Result:           noErr       - success
                  != noErr    - failure
-------------------------------------------------------------------------------*/

OSStatus    DeleteTree              (BTreeControlBlockPtr          btreePtr,
                                                 TreePathTable                       treePathTable,
                                                 BlockDescriptor              *targetNode,
                                                 UInt16                                    index,
                                                 UInt16                                    level )
{
      OSStatus                err;
      BlockDescriptor         parentNode;
      BTNodeDescriptor  *targetNodePtr;
      UInt32                        targetNodeNum;
      Boolean                       deleteRequired;
      Boolean                       updateRequired;


      deleteRequired = false;
      updateRequired = false;

      targetNodeNum = treePathTable[level].node;
      targetNodePtr = targetNode->buffer;
      PanicIf (targetNodePtr == nil, "\pDeleteTree: targetNode has nil buffer!");

      DeleteRecord (btreePtr, targetNodePtr, index);
            
      //„„ coalesce remaining records?

      if ( targetNodePtr->numRecords == 0 )     // did we delete the last record?
      {
            BlockDescriptor         siblingNode;
            UInt32                        siblingNodeNum;

            deleteRequired = true;
            
            ////////////////// Get Siblings & Update Links //////////////////////////
            
            siblingNodeNum = targetNodePtr->bLink;                      // Left Sibling Node
            if ( siblingNodeNum != 0 )
            {
                  err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
                  M_ExitOnError (err);
                  ((NodeDescPtr)siblingNode.buffer)->fLink = targetNodePtr->fLink;
                  err = UpdateNode (btreePtr, &siblingNode);
                  M_ExitOnError (err);
            }
            else if ( targetNodePtr->kind == kBTLeafNode )        // update firstLeafNode
            {
                  btreePtr->firstLeafNode = targetNodePtr->fLink;
            }

            siblingNodeNum = targetNodePtr->fLink;                      // Right Sibling Node
            if ( siblingNodeNum != 0 )
            {
                  err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
                  M_ExitOnError (err);
                  ((NodeDescPtr)siblingNode.buffer)->bLink = targetNodePtr->bLink;
                  err = UpdateNode (btreePtr, &siblingNode);
                  M_ExitOnError (err);
            }
            else if ( targetNodePtr->kind == kBTLeafNode )        // update lastLeafNode
            {
                  btreePtr->lastLeafNode = targetNodePtr->bLink;
            }
            
            //////////////////////// Free Empty Node ////////////////////////////////

            ClearNode (btreePtr, targetNodePtr);
            
            err = UpdateNode (btreePtr, targetNode);
            M_ExitOnError (err);
            err = FreeNode (btreePtr, targetNodeNum);
            M_ExitOnError (err);
      }
      else if ( index == 0 )              // did we delete the first record?
      {
            updateRequired = true;        // yes, so we need to update parent
      }


      if ( level == btreePtr->treeDepth )       // then targetNode->buffer is the root node
      {
            deleteRequired = false;
            updateRequired = false;
            
            if ( targetNode->buffer == nil )    // then root was freed and the btree is empty
            {
                  btreePtr->rootNode  = 0;
                  btreePtr->treeDepth = 0;
            }
            else if ( ((NodeDescPtr)targetNode->buffer)->numRecords == 1 )
            {
                  err = CollapseTree (btreePtr, targetNode);
                  M_ExitOnError (err);
            }
      }


      if ( updateRequired || deleteRequired )
      {
            ++level;    // next level

            //// Get Parent Node and index
            index = treePathTable [level].index;
            err = GetNode (btreePtr, treePathTable[level].node, &parentNode);
            M_ExitOnError (err);

            if ( updateRequired )
            {
                   KeyPtr           keyPtr;
                   UInt8 *    recPtr;
                   UInt16           recSize;
                   UInt32           insertNode;
                   
                  //„„Źdebug: check if ptr == targetNodeNum
                  GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
                  PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p DeleteTree: parent ptr doesn't match targetNodeNum!!");
                  
                  // need to delete and re-insert this parent key/ptr
                  DeleteRecord (btreePtr, parentNode.buffer, index);
      
                  keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
                  recPtr = (UInt8 *) &targetNodeNum;
                  recSize = sizeof(targetNodeNum);
                  
                  err = InsertTree (btreePtr, treePathTable, keyPtr, recPtr, recSize,
                                            &parentNode, index, level, kReplaceRecord, &insertNode);
                  M_ExitOnError (err);
            }
            else // deleteRequired
            {
                  err = DeleteTree (btreePtr, treePathTable, &parentNode, index, level);
                  M_ExitOnError (err);
            }
      }     


      err = UpdateNode (btreePtr, targetNode);
      M_ExitOnError (err);

      return      noErr;

ErrorExit:
      
      (void) ReleaseNode (btreePtr, targetNode);
      (void) ReleaseNode (btreePtr, &parentNode);

      return      err;

} // end DeleteTree



///////////////////////////////// CollapseTree //////////////////////////////////

static OSStatus   CollapseTree      (BTreeControlBlockPtr         btreePtr,
                                                 BlockDescriptor              *blockPtr )
{
      OSStatus          err;
      UInt32                  originalRoot;
      UInt32                  nodeNum;
      
      originalRoot      = btreePtr->rootNode;
      
      while (true)
      {
            if ( ((NodeDescPtr)blockPtr->buffer)->numRecords > 1)
                  break;                                          // this will make a fine root node
            
            if ( ((NodeDescPtr)blockPtr->buffer)->kind == kBTLeafNode)
                  break;                                          // we've hit bottom
            
            nodeNum                       = btreePtr->rootNode;
            btreePtr->rootNode      = GetChildNodeNum (btreePtr, blockPtr->buffer, 0);
            --btreePtr->treeDepth;

            //// Clear and Free Current Old Root Node ////
            ClearNode (btreePtr, blockPtr->buffer);
            err = UpdateNode (btreePtr, blockPtr);
            M_ExitOnError (err);
            err = FreeNode (btreePtr, nodeNum);
            M_ExitOnError (err);
            
            //// Get New Root Node
            err = GetNode (btreePtr, btreePtr->rootNode, blockPtr);
            M_ExitOnError (err);
      }
      
      if (btreePtr->rootNode != originalRoot)
            M_BTreeHeaderDirty (btreePtr);
            
      err = UpdateNode (btreePtr, blockPtr);    // always update!
      M_ExitOnError (err);
      
      return      noErr;
      

/////////////////////////////////// ErrorExit ///////////////////////////////////

ErrorExit:
      (void)      ReleaseNode (btreePtr, blockPtr);
      return      err;
}



////////////////////////////////// RotateLeft ///////////////////////////////////

/*-------------------------------------------------------------------------------

Routine:    RotateLeft  -     One_line_description.

Function:   Brief_description_of_the_function_and_any_side_effects

Algorithm:  if rightIndex > insertIndex, subtract 1 for actual rightIndex

Input:            btreePtr                - description
                  leftNode                - description
                  rightNode               - description
                  rightInsertIndex  - description
                  keyPtr                        - description
                  recPtr                        - description
                  recSize                       - description
                  
Output:           insertIndex
                  insertNodeNum           - description
                  recordFit               - description
                  recsRotated
                  
Result:           noErr       - success
                  != noErr    - failure
-------------------------------------------------------------------------------*/

static OSStatus   RotateLeft        (BTreeControlBlockPtr          btreePtr,
                                                 NodeDescPtr                         leftNode,
                                                 NodeDescPtr                         rightNode,
                                                 UInt16                                    rightInsertIndex,
                                                 KeyPtr                                    keyPtr,
                                                 UInt8 *                             recPtr,
                                                 UInt16                                    recSize,
                                                 UInt16                                   *insertIndex,
                                                 UInt32                                   *insertNodeNum,
                                                 Boolean                            *recordFit,
                                                 UInt16                                   *recsRotated )
{
      OSStatus                err;
      SInt32                        insertSize;
      SInt32                        nodeSize;
      SInt32                        leftSize, rightSize;
      SInt32                        moveSize;
      UInt16                        keyLength;
      UInt16                        lengthFieldSize;
      UInt16                        index, moveIndex;
      Boolean                       didItFit;

      ///////////////////// Determine If Record Will Fit //////////////////////////
      
      keyLength = GetKeyLength(btreePtr, keyPtr, (rightNode->kind == kBTLeafNode));

      // the key's length field is 8-bits in HFS and 16-bits in HFS+
      if ( btreePtr->attributes & kBTBigKeysMask )
            lengthFieldSize = sizeof(UInt16);
      else
            lengthFieldSize = sizeof(UInt8);

      insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16);

      if ( M_IsOdd (insertSize) )
            ++insertSize;     // add pad byte;

      nodeSize          = btreePtr->nodeSize;

      // add size of insert record to right node
      rightSize         = nodeSize - GetNodeFreeSize (btreePtr, rightNode) + insertSize;
      leftSize          = nodeSize - GetNodeFreeSize (btreePtr, leftNode);

      moveIndex   = 0;
      moveSize    = 0;

      while ( leftSize < rightSize )
      {
            if ( moveIndex < rightInsertIndex )
            {
                  moveSize = GetRecordSize (btreePtr, rightNode, moveIndex) + 2;
            }
            else if ( moveIndex == rightInsertIndex )
            {
                  moveSize = insertSize;
            }
            else // ( moveIndex > rightInsertIndex )
            {
                  moveSize = GetRecordSize (btreePtr, rightNode, moveIndex - 1) + 2;
            }
            
            leftSize    += moveSize;
            rightSize   -= moveSize;
            ++moveIndex;
      }     
      
      if ( leftSize > nodeSize )    // undo last move
      {
            leftSize    -= moveSize;
            rightSize   += moveSize;
            --moveIndex;
      }
      
      if ( rightSize > nodeSize )   // record won't fit - failure, but not error
      {
            *insertIndex      = 0;
            *insertNodeNum    = 0;
            *recordFit        = false;
            *recsRotated      = 0;
            
            return      noErr;
      }
      
      // we've found balance point, moveIndex == number of records moved into leftNode
      

      //////////////////////////// Rotate Records /////////////////////////////////

      *recsRotated      = moveIndex;
      *recordFit        = true;
      index             = 0;

      while ( index < moveIndex )
      {
            if ( index == rightInsertIndex )    // insert new record in left node
            {
                  UInt16      leftInsertIndex;
                  
                  leftInsertIndex = leftNode->numRecords;

                  didItFit = InsertKeyRecord (btreePtr, leftNode, leftInsertIndex,
                                                            keyPtr, keyLength, recPtr, recSize);
                  if ( !didItFit )
                  {
                        Panic ("\pRotateLeft: InsertKeyRecord (left) returned false!");
                        err = fsBTBadRotateErr;
                        goto ErrorExit;
                  }
                  
                  *insertIndex = leftInsertIndex;
                  *insertNodeNum = rightNode->bLink;
            }
            else
            {
                  didItFit = RotateRecordLeft (btreePtr, leftNode, rightNode);
                  if ( !didItFit )
                  {
                        Panic ("\pRotateLeft: RotateRecordLeft returned false!");
                        err = fsBTBadRotateErr;
                        goto ErrorExit;
                  }
            }
            
            ++index;
      }
      
      if ( moveIndex <= rightInsertIndex )      // then insert new record in right node
      {
            rightInsertIndex -= index;                // adjust for records already rotated
            
            didItFit = InsertKeyRecord (btreePtr, rightNode, rightInsertIndex,
                                                      keyPtr, keyLength, recPtr, recSize);
            if ( !didItFit )
            {
                  Panic ("\pRotateLeft: InsertKeyRecord (right) returned false!");
                  err = fsBTBadRotateErr;
                  goto ErrorExit;
            }
      
            *insertIndex = rightInsertIndex;
            *insertNodeNum = leftNode->fLink;
      }

#if DEBUG_TREEOPS
      if ( DoKeyCheck( leftNode, btreePtr ) != noErr )
      {
            printf( "\n%s - bad key order in left node num %d: \n", __FUNCTION__ , rightNode->bLink );
            PrintNodeDescriptor( leftNode );
            err = fsBTBadRotateErr;
            goto ErrorExit;
      }
      if ( DoKeyCheck( rightNode, btreePtr ) != noErr )
      {
            printf( "\n%s - bad key order in left node num %d: \n", __FUNCTION__ , leftNode->fLink );
            PrintNodeDescriptor( rightNode );
            err = fsBTBadRotateErr;
            goto ErrorExit;
      }
#endif // DEBUG_TREEOPS


      return noErr;


      ////////////////////////////// Error Exit ///////////////////////////////////

ErrorExit:

      *insertIndex      = 0;
      *insertNodeNum    = 0;
      *recordFit        = false;
      *recsRotated      = 0;
      
      return      err;
}


#if 0 
/////////////////////////////////// SplitLeft ///////////////////////////////////

static OSStatus   SplitLeft         (BTreeControlBlockPtr          btreePtr,
                                                 BlockDescriptor              *leftNode,
                                                 BlockDescriptor              *rightNode,
                                                 UInt32                                    rightNodeNum,
                                                 UInt16                                    index,
                                                 KeyPtr                                    keyPtr,
                                                 UInt8 *                             recPtr,
                                                 UInt16                                    recSize,
                                                 UInt16                                   *insertIndex,
                                                 UInt32                                   *insertNodeNum,
                                                 UInt16                                   *recsRotated )
{
      OSStatus                err;
      NodeDescPtr             left, right;
      UInt32                        newNodeNum;
      Boolean                       recordFit;
      
      
      ///////////////////////////// Compare Nodes /////////////////////////////////

      right = rightNode->buffer;
      left  = leftNode->buffer;
      
      PanicIf ( right->bLink != 0 && left == 0, "\p SplitLeft: left sibling missing!?" );
      
      //„„ type should be kLeafNode or kIndexNode
      
      if ( (right->height == 1) && (right->kind != kBTLeafNode) )
            return      fsBTInvalidNodeErr;
      
      if ( left != nil )
      {
            if ( left->fLink != rightNodeNum )
                  return fsBTInvalidNodeErr;                                                          //„„ E_BadSibling ?
      
            if ( left->height != right->height )
                  return      fsBTInvalidNodeErr;                                                           //„„ E_BadNodeHeight ?
            
            if ( left->kind != right->kind )
                  return      fsBTInvalidNodeErr;                                                           //„„ E_BadNodeType ?
      }
      

      ///////////////////////////// Allocate Node /////////////////////////////////

      err = AllocateNode (btreePtr, &newNodeNum);
      M_ExitOnError (err);
      

      /////////////// Update Forward Link In Original Left Node ///////////////////

      if ( left != nil )
      {
            left->fLink = newNodeNum;
            err = UpdateNode (btreePtr, leftNode);
            M_ExitOnError (err);
      }


      /////////////////////// Initialize New Left Node ////////////////////////////

      err = GetNewNode (btreePtr, newNodeNum, leftNode);
      M_ExitOnError (err);
      
      left        = leftNode->buffer;
      left->fLink = rightNodeNum;
      

      // Steal Info From Right Node
      
      left->bLink  = right->bLink;
      left->kind   = right->kind;
      left->height = right->height;
      
      right->bLink            = newNodeNum;                 // update Right bLink

      if ( (left->kind == kBTLeafNode) && (left->bLink == 0) )
      {
            // if we're adding a new first leaf node - update BTreeInfoRec
            
            btreePtr->firstLeafNode = newNodeNum;
            M_BTreeHeaderDirty (btreePtr);            //„„ AllocateNode should have set the bit already...
      }

      ////////////////////////////// Rotate Left //////////////////////////////////

      err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize,
                                insertIndex, insertNodeNum, &recordFit, recsRotated);
      M_ExitOnError (err);
      
      return noErr;
      
ErrorExit:
      
      (void) ReleaseNode (btreePtr, leftNode);
      (void) ReleaseNode (btreePtr, rightNode);
      
      //„„ Free new node if allocated?

      *insertIndex      = 0;
      *insertNodeNum    = 0;
      *recsRotated      = 0;
      
      return      err;
}
#endif



/////////////////////////////// RotateRecordLeft ////////////////////////////////

static Boolean RotateRecordLeft (BTreeControlBlockPtr       btreePtr,
                                                 NodeDescPtr                        leftNode,
                                                 NodeDescPtr                        rightNode )
{
      UInt16            size;
      UInt8 *           recPtr;
      Boolean           recordFit;
      
      size  = GetRecordSize (btreePtr, rightNode, 0);
      recPtr      = GetRecordAddress (btreePtr, rightNode, 0);
      
      recordFit = InsertRecord (btreePtr, leftNode, leftNode->numRecords, recPtr, size);
      
      if ( !recordFit )
            return false;

      DeleteRecord (btreePtr, rightNode, 0);
      
      return true;
}


//////////////////////////////// AddNewRootNode /////////////////////////////////

static OSStatus   AddNewRootNode    (BTreeControlBlockPtr    btreePtr,
                                                 NodeDescPtr                   leftNode,
                                                 NodeDescPtr                   rightNode )
{
      OSStatus                err;
      BlockDescriptor         rootNode;
      UInt32                        rootNum;
      KeyPtr                        keyPtr;
      Boolean                       didItFit;
      UInt16                        keyLength;  
      
      PanicIf (leftNode == nil, "\pAddNewRootNode: leftNode == nil");
      PanicIf (rightNode == nil, "\pAddNewRootNode: rightNode == nil");
      
      
      /////////////////////// Initialize New Root Node ////////////////////////////
      
      err = AllocateNode (btreePtr, &rootNum);
      M_ExitOnError (err);
      
      err = GetNewNode (btreePtr, rootNum, &rootNode);
      M_ExitOnError (err);
            
      ((NodeDescPtr)rootNode.buffer)->kind      = kBTIndexNode;
      ((NodeDescPtr)rootNode.buffer)->height    = ++btreePtr->treeDepth;
      

      ///////////////////// Insert Left Node Index Record ///////////////////////// 

      keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode, 0);
      keyLength = GetKeyLength(btreePtr, keyPtr, false);

      didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 0, keyPtr, keyLength,
                                                 (UInt8 *) &rightNode->bLink, 4 );

      PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for left index record");


      //////////////////// Insert Right Node Index Record /////////////////////////

      keyPtr = (KeyPtr) GetRecordAddress (btreePtr, rightNode, 0);
      keyLength = GetKeyLength(btreePtr, keyPtr, false);

      didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 1, keyPtr, keyLength,
                                                 (UInt8 *) &leftNode->fLink, 4 );

      PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for right index record");


#if DEBUG_TREEOPS
      if ( DoKeyCheck( rootNode.buffer, btreePtr ) != noErr )
      {
            printf( "\n%s - bad key order in root node num %d: \n", __FUNCTION__ , rootNum );
            PrintNodeDescriptor( rootNode.buffer );
            err = fsBTBadRotateErr;
            goto ErrorExit;
      }
#endif // DEBUG_TREEOPS

      
      /////////////////////////// Release Root Node ///////////////////////////////
      
      err = UpdateNode (btreePtr, &rootNode);
      M_ExitOnError (err);
      
      // update BTreeInfoRec
      
      btreePtr->rootNode       = rootNum;
      btreePtr->flags         |= kBTHeaderDirty;
      
      return noErr;


      ////////////////////////////// Error Exit ///////////////////////////////////

ErrorExit:

      return      err;
}


static UInt16     GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode )
{
      UInt16 length;

      if ( forLeafNode || btreePtr->attributes & kBTVariableIndexKeysMask )
            length = KeyLength (btreePtr, key);       // just use actual key length
      else
            length = btreePtr->maxKeyLength;          // fixed sized index key (i.e. HFS)       //„„ shouldn't we clear the pad bytes?

      return length;
}



/////////////////////////////////// SplitRight ///////////////////////////////////

static OSStatus   SplitRight        (BTreeControlBlockPtr          btreePtr,
                                                 BlockDescriptor              *nodePtr,
                                                 BlockDescriptor              *rightNodePtr,
                                                 UInt32                                    nodeNum,
                                                 UInt16                                    index,
                                                 KeyPtr                                    keyPtr,
                                                 UInt8                              *recPtr,
                                                 UInt16                                    recSize,
                                                 UInt16                                   *insertIndexPtr,
                                                 UInt32                                   *newNodeNumPtr,
                                                 UInt16                                   *recsRotatedPtr )
{
      OSStatus                err;
      NodeDescPtr             leftPtr, rightPtr;
      UInt32                        newNodeNum;
      Boolean                       recordFit;
      
      
      ///////////////////////////// Compare Nodes /////////////////////////////////

      leftPtr  = nodePtr->buffer;
      
      if ( leftPtr->fLink != 0 )
      {
            err = GetNode( btreePtr, leftPtr->fLink, rightNodePtr );
            M_ExitOnError( err );
      }
      rightPtr = rightNodePtr->buffer;
      
      PanicIf ( leftPtr->fLink != 0 && rightPtr == 0, "\p SplitRight: right sibling missing!?" );
      
      //„„ type should be kLeafNode or kIndexNode
      
      if ( (leftPtr->height == 1) && (leftPtr->kind != kBTLeafNode) )
            return      fsBTInvalidNodeErr;
      
      if ( rightPtr != nil )
      {
            if ( rightPtr->bLink != nodeNum )
                  return fsBTInvalidNodeErr;                                                          //„„ E_BadSibling ?
      
            if ( rightPtr->height != leftPtr->height )
                  return      fsBTInvalidNodeErr;                                                           //„„ E_BadNodeHeight ?
            
            if ( rightPtr->kind != leftPtr->kind )
                  return      fsBTInvalidNodeErr;                                                           //„„ E_BadNodeType ?
      }
      

      ///////////////////////////// Allocate Node /////////////////////////////////

      err = AllocateNode (btreePtr, &newNodeNum);
      M_ExitOnError (err);

      /////////////// Update backward Link In Original Right Node ///////////////////

      if ( rightPtr != nil )
      {
            rightPtr->bLink   = newNodeNum;
            err = UpdateNode (btreePtr, rightNodePtr);
            M_ExitOnError (err);
      }

      /////////////////////// Initialize New Right Node ////////////////////////////

      err = GetNewNode (btreePtr, newNodeNum, rightNodePtr );
      M_ExitOnError (err);
      
      rightPtr                = rightNodePtr->buffer;
      rightPtr->bLink         = nodeNum;
      

      // Steal Info From Left Node
      
      rightPtr->fLink  = leftPtr->fLink;
      rightPtr->kind   = leftPtr->kind;
      rightPtr->height = leftPtr->height;
      
      leftPtr->fLink          = newNodeNum;                 // update Left fLink

      if ( (rightPtr->kind == kBTLeafNode) && (rightPtr->fLink == 0) )
      {
            // if we're adding a new last leaf node - update BTreeInfoRec
            
            btreePtr->lastLeafNode = newNodeNum;
            M_BTreeHeaderDirty (btreePtr);            //„„ AllocateNode should have set the bit already...
      }

      ////////////////////////////// Rotate Right //////////////////////////////////

      err = RotateRight (btreePtr, leftPtr, rightPtr, index, keyPtr, recPtr, recSize,
                                insertIndexPtr, newNodeNumPtr, &recordFit, recsRotatedPtr);
      M_ExitOnError (err);
      
      return noErr;
      
ErrorExit:
      
      (void) ReleaseNode (btreePtr, nodePtr);
      (void) ReleaseNode (btreePtr, rightNodePtr);
      
      //„„ Free new node if allocated?

      *insertIndexPtr   = 0;
      *newNodeNumPtr    = 0;
      *recsRotatedPtr   = 0;
      
      return      err;
      
} /* SplitRight */



////////////////////////////////// RotateRight ///////////////////////////////////

/*-------------------------------------------------------------------------------

Routine:    RotateRight -     rotate half of .

Function:   Brief_description_of_the_function_and_any_side_effects

Algorithm:  if rightIndex > insertIndex, subtract 1 for actual rightIndex

Input:            btreePtr                - description
                  leftNode                - description
                  rightNode               - description
                  leftInsertIndex         - description
                  keyPtr                        - description
                  recPtr                        - description
                  recSize                       - description
                  
Output:           insertIndex
                  insertNodeNum           - description
                  recordFit               - description
                  recsRotated
                  
Result:           noErr       - success
                  != noErr    - failure
-------------------------------------------------------------------------------*/

static OSStatus   RotateRight       (BTreeControlBlockPtr          btreePtr,
                                                 NodeDescPtr                         leftNodePtr,
                                                 NodeDescPtr                         rightNodePtr,
                                                 UInt16                                    leftInsertIndex,
                                                 KeyPtr                                    keyPtr,
                                                 UInt8                                    *recPtr,
                                                 UInt16                                    recSize,
                                                 UInt16                                   *insertIndexPtr,
                                                 UInt32                                   *newNodeNumPtr,
                                                 Boolean                            *didRecordFitPtr,
                                                 UInt16                                   *recsRotatedPtr )
{
      OSStatus                err;
      SInt32                        insertSize;
      SInt32                        nodeSize;
      SInt32                        leftSize, rightSize;
      SInt32                        moveSize;
      UInt16                        keyLength;
      UInt16                        lengthFieldSize;
      SInt16                        index, moveIndex, myInsertIndex;
      Boolean                       didItFit;
      Boolean                       doIncrement = false;

      ///////////////////// Determine If Record Will Fit //////////////////////////
      
      keyLength = GetKeyLength( btreePtr, keyPtr, (leftNodePtr->kind == kBTLeafNode) );

      // the key's length field is 8-bits in HFS and 16-bits in HFS+
      if ( btreePtr->attributes & kBTBigKeysMask )
            lengthFieldSize = sizeof(UInt16);
      else
            lengthFieldSize = sizeof(UInt8);

      insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16);
      if ( M_IsOdd (insertSize) )
            ++insertSize;     // add pad byte;
      nodeSize          = btreePtr->nodeSize;

      // add size of insert record to left node
      rightSize         = nodeSize - GetNodeFreeSize( btreePtr, rightNodePtr );
      leftSize          = nodeSize - GetNodeFreeSize( btreePtr, leftNodePtr ) + insertSize;

      moveIndex   = leftNodePtr->numRecords - 1; // start at last record in the node
      moveSize    = 0;

      while ( rightSize < leftSize )
      {
            moveSize = GetRecordSize( btreePtr, leftNodePtr, moveIndex ) + 2;

            if ( moveIndex == leftInsertIndex || leftNodePtr->numRecords == leftInsertIndex )
                  moveSize += insertSize;
            
            leftSize    -= moveSize;
            rightSize   += moveSize;
            --moveIndex;
      }     
      
      if ( rightSize > nodeSize )   // undo last move
      {
            leftSize    += moveSize;
            rightSize   -= moveSize;
            ++moveIndex;
      }
      
      if ( leftSize > nodeSize )    // record won't fit - failure, but not error
      {
            *insertIndexPtr         = 0;
            *newNodeNumPtr          = 0;
            *didRecordFitPtr  = false;
            *recsRotatedPtr         = 0;
            
            return      noErr;
      }
      
      // we've found balance point, 

      //////////////////////////// Rotate Records /////////////////////////////////

      *didRecordFitPtr  = true;
      index                   = leftNodePtr->numRecords - 1;
      *recsRotatedPtr         = index - moveIndex;
      myInsertIndex           = 0;
      
      // handle case where the new record is inserting after the last
      // record in our left node.
      if ( leftNodePtr->numRecords == leftInsertIndex )
      {
            didItFit = InsertKeyRecord (btreePtr, rightNodePtr, 0,
                                                      keyPtr, keyLength, recPtr, recSize);
            if ( !didItFit )
            {
                  Panic ("\pRotateRight: InsertKeyRecord (left) returned false!");
                  err = fsBTBadRotateErr;
                  goto ErrorExit;
            }
            
            // NOTE - our insert location will slide as we insert more records
            doIncrement = true;
            *newNodeNumPtr = leftNodePtr->fLink;
      }

      while ( index > moveIndex )
      {
            didItFit = RotateRecordRight( btreePtr, leftNodePtr, rightNodePtr );
            if ( !didItFit )
            {
                  Panic ("\pRotateRight: RotateRecordRight returned false!");
                  err = fsBTBadRotateErr;
                  goto ErrorExit;
            }

            if ( index == leftInsertIndex )     // insert new record in right node
            {
                  didItFit = InsertKeyRecord (btreePtr, rightNodePtr, 0,
                                                            keyPtr, keyLength, recPtr, recSize);
                  if ( !didItFit )
                  {
                        Panic ("\pRotateRight: InsertKeyRecord (left) returned false!");
                        err = fsBTBadRotateErr;
                        goto ErrorExit;
                  }
                  
                  // NOTE - our insert index will slide as we insert more records
                  doIncrement = true;
                  myInsertIndex = -1;
                  *newNodeNumPtr = leftNodePtr->fLink;
            }

            if ( doIncrement )
                  myInsertIndex++;
            --index;
      }
      
      *insertIndexPtr = myInsertIndex;
      
      if ( moveIndex >= leftInsertIndex ) // then insert new record in left node
      {
            didItFit = InsertKeyRecord (btreePtr, leftNodePtr, leftInsertIndex,
                                                      keyPtr, keyLength, recPtr, recSize);
            if ( !didItFit )
            {
                  Panic ("\pRotateRight: InsertKeyRecord (right) returned false!");
                  err = fsBTBadRotateErr;
                  goto ErrorExit;
            }
      
            *insertIndexPtr = leftInsertIndex;
            *newNodeNumPtr = rightNodePtr->bLink;
      }

#if DEBUG_TREEOPS
      if ( DoKeyCheck( rightNodePtr, btreePtr ) != noErr )
      {
            printf( "\n%s - bad key order in right node num %d: \n", __FUNCTION__ , leftNodePtr->fLink);
            PrintNodeDescriptor( rightNodePtr );
            err = fsBTBadRotateErr;
            goto ErrorExit;
      }
      if ( DoKeyCheck( leftNodePtr, btreePtr ) != noErr )
      {
            printf( "\n%s - bad key order in left node num %d: \n", __FUNCTION__ , rightNodePtr->bLink);
            PrintNodeDescriptor( leftNodePtr );
            err = fsBTBadRotateErr;
            goto ErrorExit;
      }
      if ( DoKeyCheckAcrossNodes( leftNodePtr, rightNodePtr, btreePtr, false ) != noErr )
      {
            printf( "\n%s - bad key order across nodes left %d right %d: \n", 
                  __FUNCTION__ , rightNodePtr->bLink, leftNodePtr->fLink );
            PrintNodeDescriptor( leftNodePtr );
            PrintNodeDescriptor( rightNodePtr );
            err = fsBTBadRotateErr;
            goto ErrorExit;
      }
#endif // DEBUG_TREEOPS

      return noErr;


      ////////////////////////////// Error Exit ///////////////////////////////////

ErrorExit:

      *insertIndexPtr   = 0;
      *newNodeNumPtr    = 0;
      *didRecordFitPtr = false;
      *recsRotatedPtr   = 0;
      
      return      err;
      
} /* RotateRight */



/////////////////////////////// RotateRecordRight ////////////////////////////////

static Boolean RotateRecordRight (BTreeControlBlockPtr            btreePtr,
                                                 NodeDescPtr                        leftNodePtr,
                                                 NodeDescPtr                        rightNodePtr )
{
      UInt16            size;
      UInt8 *           recPtr;
      Boolean           didRecordFit;
      
      size  = GetRecordSize( btreePtr, leftNodePtr, leftNodePtr->numRecords - 1 ) ;
      recPtr      = GetRecordAddress( btreePtr, leftNodePtr, leftNodePtr->numRecords - 1 ) ;
      
      didRecordFit = InsertRecord( btreePtr, rightNodePtr, 0, recPtr, size );
      if ( !didRecordFit )
            return false;
      
      DeleteRecord( btreePtr, leftNodePtr, leftNodePtr->numRecords - 1 );
      
      return true;
      
} /* RotateRecordRight */



#if DEBUG_TREEOPS
static int  DoKeyCheckAcrossNodes(  NodeDescPtr theLeftNodePtr, 
                                                      NodeDescPtr theRightNodePtr, 
                                                      BTreeControlBlock *theTreePtr,
                                                      Boolean printKeys ) 
{
      UInt16                        myLeftDataSize;
      UInt16                        myRightDataSize;
      UInt16                        myRightKeyLen;
      UInt16                        myLeftKeyLen;
      KeyPtr                        myLeftKeyPtr;
      KeyPtr                        myRightKeyPtr;
      UInt8 *                       myLeftDataPtr;
      UInt8 *                       myRightDataPtr;


      GetRecordByIndex( theTreePtr, theLeftNodePtr, (theLeftNodePtr->numRecords - 1), 
                                &myLeftKeyPtr, &myLeftDataPtr, &myLeftDataSize );
      GetRecordByIndex( theTreePtr, theRightNodePtr, 0, 
                                &myRightKeyPtr, &myRightDataPtr, &myRightDataSize );

      if ( theTreePtr->attributes & kBTBigKeysMask )
      {
            myRightKeyLen = myRightKeyPtr->length16;
            myLeftKeyLen = myLeftKeyPtr->length16;
      }
      else
      {
            myRightKeyLen = myRightKeyPtr->length8;
            myLeftKeyLen = myLeftKeyPtr->length8;
      }

      if ( printKeys )
      {
            printf( "%s - left and right keys:\n", __FUNCTION__ );
            PrintKey( (UInt8 *) myLeftKeyPtr, myLeftKeyLen );
            PrintKey( (UInt8 *) myRightKeyPtr, myRightKeyLen );
      }
      
      if ( CompareKeys( theTreePtr, myLeftKeyPtr, myRightKeyPtr ) >= 0 )
            return( -1 );

      return( noErr );
      
} /* DoKeyCheckAcrossNodes */


static int DoKeyCheck( NodeDescPtr nodeP, BTreeControlBlock *btcb )
{
      SInt16                        index;
      UInt16                        dataSize;
      UInt16                        keyLength;
      KeyPtr                        keyPtr;
      UInt8                   *dataPtr;
      KeyPtr                        prevkeyP    = nil;


      if ( nodeP->numRecords == 0 )
      {
            if ( (nodeP->fLink == 0) && (nodeP->bLink == 0) )
                  return( -1 );
      }
      else
      {
            /*
             * Loop on number of records in node
             */
            for ( index = 0; index < nodeP->numRecords; index++)
            {
                  GetRecordByIndex( (BTreeControlBlock *)btcb, nodeP, (UInt16) index, &keyPtr, &dataPtr, &dataSize );
      
                  if (btcb->attributes & kBTBigKeysMask)
                        keyLength = keyPtr->length16;
                  else
                        keyLength = keyPtr->length8;
                        
                  if ( keyLength > btcb->maxKeyLength )
                  {
                        return( -1 );
                  }
      
                  if ( prevkeyP != nil )
                  {
                        if ( CompareKeys( (BTreeControlBlockPtr)btcb, prevkeyP, keyPtr ) >= 0 )
                        {
                              return( -1 );
                        }
                  }
                  prevkeyP = keyPtr;
            }
      }

      return( noErr );
      
} /* DoKeyCheck */

static void PrintNodeDescriptor( NodeDescPtr  thePtr )
{
      printf( "    fLink %d bLink %d kind %d height %d numRecords %d \n",
                  thePtr->fLink, thePtr->bLink, thePtr->kind, thePtr->height, thePtr->numRecords );
}


static void PrintKey( UInt8 *  myPtr, int mySize )
{
      int         i;
      
      for ( i = 0; i < mySize+2; i++ )
      {
            printf("%02X", *(myPtr + i) );
      }
      printf("\n" );
} /* PrintKey */


#endif // DEBUG_TREEOPS

Generated by  Doxygen 1.6.0   Back to index