/* * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. * * @APPLE_LICENSE_HEADER_START@ * * Copyright (c) 1999-2003 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 2.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.opensource.apple.com/apsl/ 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, QUIET ENJOYMENT 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