lf_hfs_btree_tree_ops.c   [plain text]

//
//  lf_hfs_btree_tree_ops.c
//  livefiles_hfs
//
//  Created by Yakov Ben Zaken on 22/03/2018.
//

#include "lf_hfs_btrees_private.h"
#include "lf_hfs_btrees_io.h"
#include "lf_hfs_utils.h"
#include "lf_hfs_generic_buf.h"
//
/////////////////////// 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,
                                     u_int16_t                     rightInsertIndex,
                                     KeyPtr                         keyPtr,
                                     u_int8_t *                     recPtr,
                                     u_int16_t                     recSize,
                                     u_int16_t                    *insertIndex,
                                     u_int32_t                    *insertNodeNum,
                                     Boolean                    *recordFit,
                                     u_int16_t                    *recsRotated );

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

static OSStatus       SplitLeft        (BTreeControlBlockPtr         btreePtr,
                                        BlockDescriptor            *leftNode,
                                        BlockDescriptor            *rightNode,
                                        u_int32_t                     rightNodeNum,
                                        u_int16_t                     index,
                                        KeyPtr                         keyPtr,
                                        u_int8_t *                     recPtr,
                                        u_int16_t                     recSize,
                                        u_int16_t                    *insertIndex,
                                        u_int32_t                    *insertNodeNum,
                                        u_int16_t                    *recsRotated );



static    OSStatus    InsertLevel        (BTreeControlBlockPtr         btreePtr,
                                          TreePathTable                 treePathTable,
                                          InsertKey                    *primaryKey,
                                          InsertKey                    *secondaryKey,
                                          BlockDescriptor            *targetNode,
                                          u_int16_t                     index,
                                          u_int16_t                     level,
                                          u_int32_t                    *insertNode );

static OSErr        InsertNode         (BTreeControlBlockPtr         btreePtr,
                                        InsertKey                    *key,
                                        BlockDescriptor            *rightNode,
                                        u_int32_t                     node,
                                        u_int16_t                      index,
                                        u_int32_t                    *newNode,
                                        u_int16_t                    *newIndex,
                                        BlockDescriptor            *leftNode,
                                        Boolean                    *updateParent,
                                        Boolean                    *insertParent,
                                        Boolean                    *rootSplit );

static u_int16_t        GetKeyLength    (const BTreeControlBlock *btreePtr,
                                         const BTreeKey *key,
                                         Boolean forLeafNode );



//////////////////////// 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,
                           u_int32_t                *nodeNum,
                           BlockDescriptor        *nodePtr,
                           u_int16_t                *returnIndex )
{
    OSStatus    err;
    int16_t        level;                    //    Expected depth of current node
    u_int32_t    curNodeNum;                //    Current node we're searching
    NodeRec        nodeRec;
    u_int16_t    index;
    Boolean        keyFound;
    int8_t        nodeKind;                //    Kind of current node (index/leaf)
    KeyPtr        keyPtr;
    u_int8_t *    dataPtr;
    u_int16_t    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)
        {
            LFHFS_LOG(LEVEL_ERROR, "SearchTree: curNodeNum is zero!");
            err = btBadNode;
            goto ErrorExit;
        }

        err = GetNode (btreePtr, curNodeNum, 0, &nodeRec);
        if (err != noErr)
        {
            LFHFS_LOG(LEVEL_ERROR, "SearchTree: GetNode returned with error %d!",err);
            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)
        {
            LFHFS_LOG(LEVEL_ERROR, "Incorrect node height");
            err = btBadNode;
            goto ReleaseAndExit;
        }
        nodeKind = ((BTNodeDescriptor*)nodeRec.buffer)->kind;
        if (level == 1)
        {
            //    Nodes at level 1 must be leaves, by definition
            if (nodeKind != kBTLeafNode)
            {
                LFHFS_LOG(LEVEL_ERROR, "Incorrect node type: expected leaf");
                err = btBadNode;
                goto ReleaseAndExit;
            }
        }
        else
        {
            //    A node at any other depth must be an index node
            if (nodeKind != kBTIndexNode)
            {
                LFHFS_LOG(LEVEL_ERROR, "Incorrect node type: expected index");
                err = btBadNode;
                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.
            LFHFS_LOG(LEVEL_ERROR, "SearchTree: GetRecordByIndex returned with errpr %d!",err);

            (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 = *(u_int32_t *)dataPtr;
        err = ReleaseNode (btreePtr, &nodeRec);
        if (err != noErr)
        {
            LFHFS_LOG(LEVEL_ERROR, "SearchTree: ReleaseNode returned with errpr %d!",err);
            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,
                        u_int8_t *                     recPtr,
                        u_int16_t                     recSize,
                        BlockDescriptor            *targetNode,
                        u_int16_t                     index,
                        u_int16_t                     level,
                        Boolean                     replacingKey,
                        u_int32_t                    *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,
                         u_int16_t                     index,
                         u_int16_t                     level,
                         u_int32_t                    *insertNode )
{
    OSStatus             err;
    BlockDescriptor         leftNode;
    u_int32_t             targetNodeNum;
    u_int32_t             newNodeNum;
    u_int16_t             newIndex;
    Boolean                 insertParent;
    Boolean                 updateParent;
    Boolean                 newRoot;
    InsertKey            insertKey;

#if defined(applec) && !defined(__SC__)
    if ((level == 1) && (((NodeDescPtr)targetNode->buffer)->kind != kBTLeafNode))
    {
        LFHFS_LOG(LEVEL_ERROR, " InsertLevel: non-leaf at level 1! ");
        hfs_assert(0);
    }
#endif
    leftNode.buffer = nil;
    leftNode.blockHeader = nil;
    targetNodeNum = treePathTable [level].node;

    insertParent = false;
    updateParent = false;

    // XXXdbg
    ModifyBlockStart(btreePtr->fileRefNum, targetNode);

    ////// process first insert //////

    err = InsertNode (btreePtr, primaryKey, targetNode, targetNodeNum, index,
                      &newNodeNum, &newIndex, &leftNode, &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.
        //
        // If inserting the secondaryKey changes the first key of
        // the target node, then we'll have to update the second
        // key in the new root node.

        treePathTable [level + 1].node  = btreePtr->rootNode;
        treePathTable [level + 1].index = 1;    // 1 since we always split/rotate left
    }

    if ( level == 1 )
        *insertNode = newNodeNum;

    ////// process second insert (if any) //////

    if  ( secondaryKey != nil )
    {
        Boolean                temp;

        err = InsertNode (btreePtr, secondaryKey, targetNode, newNodeNum, newIndex,
                          &newNodeNum, &newIndex, &leftNode, &updateParent, &insertParent, &temp);
        M_ExitOnError (err);
    }

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

    if ( insertParent || updateParent )
    {
        BlockDescriptor        parentNode;
        u_int32_t            parentNodeNum;
        KeyPtr                keyPtr;
        u_int8_t *            recPtr;
        u_int16_t            recSize;

        parentNode.buffer = nil;
        parentNode.blockHeader = nil;

        secondaryKey = nil;

        if (level == btreePtr->treeDepth)
        {
            LFHFS_LOG(LEVEL_ERROR, " InsertLevel: unfinished insert!?");
            hfs_assert(0);
        }
        ++level;

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

        if (parentNodeNum == 0)
        {
            LFHFS_LOG(LEVEL_ERROR, " InsertLevel: parent node is zero!?");
            hfs_assert(0);
        }

        err = GetNode (btreePtr, parentNodeNum, 0, &parentNode);    // released as target node in next level up
        M_ExitOnError (err);
        ////////////////////////// Update Parent Index //////////////////////////////

        if ( updateParent )
        {
            // XXXdbg
            ModifyBlockStart(btreePtr->fileRefNum, &parentNode);

            // debug: check if ptr == targetNodeNum
            GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
            if ((*(u_int32_t *) recPtr) != targetNodeNum)
            {
                LFHFS_LOG(LEVEL_ERROR, " InsertLevel: parent ptr doesn't match target node!");
                hfs_assert(0);
            }

            // 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         = (u_int8_t *) &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;

            if ( updateParent )
            {
                insertKeyPtr = &insertKey;
                secondaryKey = &insertKey;
            }
            else
            {
                insertKeyPtr = primaryKey;
            }

            insertKeyPtr->keyPtr        = (KeyPtr) GetRecordAddress (btreePtr, leftNode.buffer, 0);
            insertKeyPtr->keyLength        = GetKeyLength(btreePtr, insertKeyPtr->keyPtr, false);
            insertKeyPtr->recPtr        = (u_int8_t *) &((NodeDescPtr)targetNode->buffer)->bLink;
            insertKeyPtr->recSize        = sizeof(u_int32_t);
            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, 0, kLockTransaction);    // all done with target
    M_ExitOnError (err);

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

    return    noErr;

ErrorExit:

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

    LFHFS_LOG(LEVEL_ERROR, " InsertLevel: an error occurred!");
    
    return    err;

} // End of InsertLevel



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

static OSErr    InsertNode    (BTreeControlBlockPtr     btreePtr,
                               InsertKey                *key,

                               BlockDescriptor        *rightNode,
                               u_int32_t                 node,
                               u_int16_t                  index,

                               u_int32_t                *newNode,
                               u_int16_t                *newIndex,

                               BlockDescriptor        *leftNode,
                               Boolean                *updateParent,
                               Boolean                *insertParent,
                               Boolean                *rootSplit )
{
    BlockDescriptor        *targetNode = NULL;
    u_int32_t             leftNodeNum;
    u_int16_t             recsRotated;
    OSErr                 err;
    Boolean                 recordFit;

    *rootSplit = false;

    if (rightNode->buffer == leftNode->buffer)
    {
        LFHFS_LOG(LEVEL_ERROR, " InsertNode: rightNode == leftNode");
        hfs_assert(0);
    }
    
    leftNodeNum = ((NodeDescPtr) rightNode->buffer)->bLink;


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

    /* sanity check our left and right nodes here. */
    if (node == leftNodeNum) {
        if (leftNode->buffer == NULL) {
            err = fsBTInvalidNodeErr;
            M_ExitOnError(err);
        }
        else{
            targetNode = leftNode;
        }
    }
    else {
        // we can assume right node is initialized.
        targetNode = rightNode;
    }


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

    if ( recordFit )
    {
        *newNode  = node;
        *newIndex = index;

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


    //////////////////////// Try Rotate Left ////////////////////////////////

    if ( !recordFit && leftNodeNum > 0 )
    {
        if (leftNode->buffer != nil)
        {
            LFHFS_LOG(LEVEL_ERROR, " InsertNode: leftNode already acquired!");
            hfs_assert(0);
        }
        
        if ( leftNode->buffer == nil )
        {
            err = GetNode (btreePtr, leftNodeNum, 0, leftNode);    // will be released by caller or a split below
            M_ExitOnError (err);
            // XXXdbg
            ModifyBlockStart(btreePtr->fileRefNum, leftNode);
        }

        if (((NodeDescPtr) leftNode->buffer)->fLink != node)
        {
            LFHFS_LOG(LEVEL_ERROR, " InsertNode, RotateLeft: invalid sibling link!");
            hfs_assert(0);
        }
        
        if ( !key->skipRotate )        // are rotates allowed?
        {
            err = RotateLeft (btreePtr, leftNode->buffer, rightNode->buffer, index, key->keyPtr, key->recPtr,
                              key->recSize, newIndex, newNode, &recordFit, &recsRotated );
            M_ExitOnError (err);

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


    //////////////////////// Try Split Left /////////////////////////////////

    if ( !recordFit )
    {
        // might not have left node...
        err = SplitLeft (btreePtr, leftNode, rightNode, node, index, key->keyPtr,
                         key->recPtr, key->recSize, newIndex, newNode, &recsRotated);
        M_ExitOnError (err);

        // if we split root node - add new root

        if ( ((NodeDescPtr) rightNode->buffer)->height == btreePtr->treeDepth )
        {
            err = AddNewRootNode (btreePtr, leftNode->buffer, rightNode->buffer);    // Note: does not update TPT
            M_ExitOnError (err);
            *rootSplit = true;
        }
        else
        {
            *insertParent = true;

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

    return noErr;

ErrorExit:
    (void) ReleaseNode (btreePtr, leftNode);
    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,
                                   u_int16_t                     index,
                                   u_int16_t                     level )
{
    OSStatus            err;
    BlockDescriptor        parentNode;
    BTNodeDescriptor    *targetNodePtr;
    u_int32_t            targetNodeNum;
    Boolean                deleteRequired;
    Boolean                updateRequired;

    // XXXdbg - initialize these to null in case we get an
    //          error and try to exit before it's initialized
    parentNode.buffer      = nil;
    parentNode.blockHeader = nil;

    deleteRequired = false;
    updateRequired = false;

    targetNodeNum = treePathTable[level].node;
    targetNodePtr = targetNode->buffer;
    if (targetNodePtr == nil)
    {
        LFHFS_LOG(LEVEL_ERROR, "DeleteTree: targetNode has nil buffer!");
        hfs_assert(0);
    }
    
    // XXXdbg
    ModifyBlockStart(btreePtr->fileRefNum, targetNode);

    DeleteRecord (btreePtr, targetNodePtr, index);

    //coalesce remaining records?

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

        deleteRequired = true;

        siblingNode.buffer = nil;
        siblingNode.blockHeader = nil;

        ////////////////// Get Siblings & Update Links //////////////////////////

        siblingNodeNum = targetNodePtr->bLink;                // Left Sibling Node
        if ( siblingNodeNum != 0 )
        {
            err = GetNode (btreePtr, siblingNodeNum, 0, &siblingNode);
            M_ExitOnError (err);

            // XXXdbg
            ModifyBlockStart(btreePtr->fileRefNum, &siblingNode);

            ((NodeDescPtr)siblingNode.buffer)->fLink = targetNodePtr->fLink;
            err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction);
            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, 0, &siblingNode);
            M_ExitOnError (err);

            // XXXdbg
            ModifyBlockStart(btreePtr->fileRefNum, &siblingNode);

            ((NodeDescPtr)siblingNode.buffer)->bLink = targetNodePtr->bLink;
            err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction);
            M_ExitOnError (err);
        }
        else if ( targetNodePtr->kind == kBTLeafNode )        // update lastLeafNode
        {
            btreePtr->lastLeafNode = targetNodePtr->bLink;
        }

        //////////////////////// Free Empty Node ////////////////////////////////

        GenericLFBuf *psBuf = targetNode->blockHeader;
        lf_hfs_generic_buf_set_cache_flag(psBuf, GEN_BUF_LITTLE_ENDIAN);
        ClearNode (btreePtr, targetNodePtr);

        err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);
        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, 0, &parentNode);
        M_ExitOnError (err);

        if ( updateRequired )
        {
            KeyPtr        keyPtr;
            u_int8_t *    recPtr;
            u_int16_t    recSize;
            u_int32_t    insertNode;

            // XXXdbg
            ModifyBlockStart(btreePtr->fileRefNum, &parentNode);

            //debug: check if ptr == targetNodeNum
            GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
            if ((*(u_int32_t *) recPtr) != targetNodeNum)
            {
                LFHFS_LOG(LEVEL_ERROR, " DeleteTree: parent ptr doesn't match targetNodeNum!!");
                hfs_assert(0);
            }
            
            // need to delete and re-insert this parent key/ptr
            DeleteRecord (btreePtr, parentNode.buffer, index);

            keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
            recPtr = (u_int8_t *) &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, 0, kLockTransaction);
    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;
    u_int32_t        originalRoot;
    u_int32_t        nodeNum;

    originalRoot    = btreePtr->rootNode;

    // XXXdbg
    ModifyBlockStart(btreePtr->fileRefNum, blockPtr);

    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 ////
        GenericLFBuf *psBuf = blockPtr->blockHeader;
        lf_hfs_generic_buf_set_cache_flag(psBuf, GEN_BUF_LITTLE_ENDIAN);
        ClearNode (btreePtr, blockPtr->buffer);
        err = UpdateNode (btreePtr, blockPtr, 0, kLockTransaction);
        M_ExitOnError (err);
        err = FreeNode (btreePtr, nodeNum);
        M_ExitOnError (err);

        //// Get New Root Node
        err = GetNode (btreePtr, btreePtr->rootNode, 0, blockPtr);
        M_ExitOnError (err);

        // XXXdbg
        ModifyBlockStart(btreePtr->fileRefNum, blockPtr);
    }

    if (btreePtr->rootNode != originalRoot)
        M_BTreeHeaderDirty (btreePtr);

    err = UpdateNode (btreePtr, blockPtr, 0, kLockTransaction);    // 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,
                                      u_int16_t                     rightInsertIndex,
                                      KeyPtr                         keyPtr,
                                      u_int8_t *                     recPtr,
                                      u_int16_t                     recSize,
                                      u_int16_t                    *insertIndex,
                                      u_int32_t                    *insertNodeNum,
                                      Boolean                    *recordFit,
                                      u_int16_t                    *recsRotated )
{
    OSStatus            err;
    int32_t                insertSize;
    int32_t                nodeSize;
    int32_t                leftSize, rightSize;
    int32_t                moveSize = 0;
    u_int16_t            keyLength;
    u_int16_t            lengthFieldSize;
    u_int16_t            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(u_int16_t);
    else
        lengthFieldSize = sizeof(u_int8_t);

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

    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;

    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
    {
        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
        {
            u_int16_t    leftInsertIndex;

            leftInsertIndex = leftNode->numRecords;

            didItFit = InsertKeyRecord (btreePtr, leftNode, leftInsertIndex,
                                        keyPtr, keyLength, recPtr, recSize);
            if ( !didItFit )
            {
                LFHFS_LOG(LEVEL_ERROR, "RotateLeft: InsertKeyRecord (left) returned false!");
                err = fsBTBadRotateErr;
                goto ErrorExit;
            }

            *insertIndex = leftInsertIndex;
            *insertNodeNum = rightNode->bLink;
        }
        else
        {
            didItFit = RotateRecordLeft (btreePtr, leftNode, rightNode);
            if ( !didItFit )
            {
                LFHFS_LOG(LEVEL_ERROR, "RotateLeft: 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 )
        {
            LFHFS_LOG(LEVEL_ERROR, "RotateLeft: InsertKeyRecord (right) returned false!");
            err = fsBTBadRotateErr;
            goto ErrorExit;
        }

        *insertIndex = rightInsertIndex;
        *insertNodeNum = leftNode->fLink;
    }


    return noErr;


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

ErrorExit:

    *insertIndex    = 0;
    *insertNodeNum    = 0;
    *recordFit        = false;
    *recsRotated    = 0;

    return    err;
}



/////////////////////////////////// SplitLeft ///////////////////////////////////

static OSStatus    SplitLeft        (BTreeControlBlockPtr         btreePtr,
                                     BlockDescriptor            *leftNode,
                                     BlockDescriptor            *rightNode,
                                     u_int32_t                     rightNodeNum,
                                     u_int16_t                     index,
                                     KeyPtr                         keyPtr,
                                     u_int8_t *                     recPtr,
                                     u_int16_t                     recSize,
                                     u_int16_t                    *insertIndex,
                                     u_int32_t                    *insertNodeNum,
                                     u_int16_t                    *recsRotated )
{
    OSStatus            err;
    NodeDescPtr            left, right;
    u_int32_t            newNodeNum;
    Boolean                recordFit;


    ///////////////////////////// Compare Nodes /////////////////////////////////

    right = rightNode->buffer;
    left  = leftNode->buffer;

    if (right->bLink != 0 && left == 0)
    {
        LFHFS_LOG(LEVEL_ERROR, " SplitLeft: left sibling missing!?" );
        hfs_assert(0);
    }
    /* type should be kBTLeafNode or kBTIndexNode */

    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 )
    {
        // XXXdbg
        ModifyBlockStart(btreePtr->fileRefNum, leftNode);

        left->fLink    = newNodeNum;
        err = UpdateNode (btreePtr, leftNode, 0, kLockTransaction);
        M_ExitOnError (err);
    }


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

    err = GetNewNode (btreePtr, newNodeNum, leftNode);
    M_ExitOnError (err);

    // XXXdbg
    ModifyBlockStart(btreePtr->fileRefNum, leftNode);

    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;
}



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

static Boolean RotateRecordLeft (BTreeControlBlockPtr        btreePtr,
                                 NodeDescPtr                leftNode,
                                 NodeDescPtr                rightNode )
{
    u_int16_t    size;
    u_int8_t *    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;
    u_int32_t            rootNum;
    KeyPtr                keyPtr;
    Boolean                didItFit;
    u_int16_t            keyLength;

    rootNode.buffer = nil;
    rootNode.blockHeader = nil;

    if (leftNode == nil || rightNode == nil)
    {
        LFHFS_LOG(LEVEL_ERROR, "AddNewRootNode: %s nil", (leftNode == nil && rightNode == nil)? "left and right node are" : ((leftNode == nil) ? "left node is" : "right node is"));
        hfs_assert(0);
    }

    /////////////////////// Initialize New Root Node ////////////////////////////

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

    err = GetNewNode (btreePtr, rootNum, &rootNode);
    M_ExitOnError (err);

    // XXXdbg
    ModifyBlockStart(btreePtr->fileRefNum, &rootNode);

    ((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,
                                (u_int8_t *) &rightNode->bLink, 4 );
    if (!didItFit)
    {
        LFHFS_LOG(LEVEL_ERROR, "AddNewRootNode:InsertKeyRecord failed for left index record\n");
        hfs_assert(0);
    }

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

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

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

    if (!didItFit)
    {
        LFHFS_LOG(LEVEL_ERROR, "AddNewRootNode:InsertKeyRecord failed for right index record\n");
        hfs_assert(0);
    }

    /////////////////////////// Release Root Node ///////////////////////////////

    err = UpdateNode (btreePtr, &rootNode, 0, kLockTransaction);
    M_ExitOnError (err);

    // update BTreeInfoRec

    btreePtr->rootNode     = rootNum;
    M_BTreeHeaderDirty(btreePtr);

    return noErr;


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

ErrorExit:

    return    err;
}


static u_int16_t    GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode )
{
    u_int16_t 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;
}