#include "BTreePrivate.h"
#define DEBUG_TREEOPS 0
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
enum
{
kInsertParent = 0x0001,
kUpdateParent = 0x0002,
kNewRoot = 0x0004,
kInsertedInRight = 0x0008,
kRecordFits = 0x0010
};
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; KeyPtr keyPtr;
UInt8 * dataPtr;
UInt16 dataSize;
curNodeNum = btreePtr->rootNode;
level = btreePtr->treeDepth;
if (level == 0) {
err = fsBTEmptyErr;
goto ErrorExit;
}
treePathTable [0].node = 0;
treePathTable [0].index = 0;
while (true)
{
if (curNodeNum == 0)
{
err = fsBTInvalidNodeErr;
goto ErrorExit;
}
err = GetNode (btreePtr, curNodeNum, &nodeRec);
if (err != noErr)
{
goto ErrorExit;
}
if (((BTNodeDescriptor*)nodeRec.buffer)->height != level)
{
err = fsBTInvalidNodeErr;
goto ReleaseAndExit;
}
nodeKind = ((BTNodeDescriptor*)nodeRec.buffer)->kind;
if (level == 1)
{
if (nodeKind != kBTLeafNode)
{
err = fsBTInvalidNodeErr;
goto ReleaseAndExit;
}
}
else
{
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; }
if ( (keyFound != true) && (index != 0))
--index;
treePathTable [level].index = index;
err = GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize);
if (err != noErr)
{
(void) TrashNode(btreePtr, &nodeRec);
goto ErrorExit;
}
curNodeNum = *(UInt32 *)dataPtr;
err = ReleaseNode (btreePtr, &nodeRec);
if (err != noErr)
{
goto ErrorExit;
}
--level;
}
*nodeNum = curNodeNum;
*nodePtr = nodeRec;
*returnIndex = index;
if (keyFound)
return noErr; else
return fsBTRecordNotFoundErr;
ReleaseAndExit:
(void) ReleaseNode(btreePtr, &nodeRec);
ErrorExit:
*nodeNum = 0;
nodePtr->buffer = nil;
nodePtr->blockHeader = nil;
*returnIndex = 0;
return err;
}
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;
}
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;
err = InsertNode (btreePtr, primaryKey, targetNode, targetNodeNum, index,
&newNodeNum, &newIndex, &siblingNode, &updateParent, &insertParent, &newRoot );
M_ExitOnError (err);
if ( newRoot )
{
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;
if ( secondaryKey != nil )
{
Boolean temp;
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...");
}
if ( insertParent || updateParent )
{
BlockDescriptor parentNode;
UInt32 parentNodeNum;
KeyPtr keyPtr;
UInt8 * recPtr;
UInt16 recSize;
secondaryKey = nil;
PanicIf ( (level == btreePtr->treeDepth), "\p InsertLevel: unfinished insert!?");
++level;
index = treePathTable [level].index;
parentNodeNum = treePathTable [level].node;
PanicIf ( parentNodeNum == 0, "\p InsertLevel: parent node is zero!?");
err = GetNode (btreePtr, parentNodeNum, &parentNode); 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
if ( updateParent )
{
GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p InsertLevel: parent ptr doesn't match target node!");
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; }
if ( insertParent )
{
InsertKey *insertKeyPtr;
InsertKey insertKey;
if ( updateParent )
{
insertKeyPtr = &insertKey;
secondaryKey = &insertKey;
}
else
{
insertKeyPtr = primaryKey;
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; }
err = InsertLevel (btreePtr, treePathTable, primaryKey, secondaryKey,
&parentNode, index, level, insertNode );
M_ExitOnError (err);
}
err = UpdateNode (btreePtr, targetNode); M_ExitOnError (err);
err = UpdateNode (btreePtr, &siblingNode); M_ExitOnError (err);
return noErr;
ErrorExit:
(void) ReleaseNode (btreePtr, targetNode);
(void) ReleaseNode (btreePtr, &siblingNode);
Panic ("\p InsertLevel: an error occured!");
return err;
}
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;
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; goto ExitThisRoutine;
}
if ( leftNodeNum > 0 )
{
PanicIf ( siblingNode->buffer != nil, "\p InsertNode: siblingNode already aquired!");
if ( siblingNode->buffer == nil )
{
err = GetNode (btreePtr, leftNodeNum, siblingNode); M_ExitOnError (err);
}
PanicIf ( ((NodeDescPtr) siblingNode->buffer)->fLink != nodeNum, "\p InsertNode, RotateLeft: invalid sibling link!" );
if ( !key->skipRotate ) {
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;
}
}
}
(void) ReleaseNode( btreePtr, siblingNode );
err = SplitRight( btreePtr, targetNode, siblingNode, nodeNum, index, key->keyPtr,
key->recPtr, key->recSize, newIndex, newNodeNumPtr, &recsRotated );
M_ExitOnError (err);
if ( ((NodeDescPtr) targetNode->buffer)->height == btreePtr->treeDepth )
{
err = AddNewRootNode( btreePtr, targetNode->buffer, siblingNode->buffer ); M_ExitOnError (err);
*rootSplit = true;
}
else
{
*insertParent = true;
if ( key->replacingKey || ( index == 0 && *newIndex == 0 ) )
*updateParent = true;
}
ExitThisRoutine:
return noErr;
ErrorExit:
(void) ReleaseNode (btreePtr, siblingNode);
return err;
}
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);
if ( targetNodePtr->numRecords == 0 ) {
BlockDescriptor siblingNode;
UInt32 siblingNodeNum;
deleteRequired = true;
siblingNodeNum = targetNodePtr->bLink; 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 ) {
btreePtr->firstLeafNode = targetNodePtr->fLink;
}
siblingNodeNum = targetNodePtr->fLink; 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 ) {
btreePtr->lastLeafNode = targetNodePtr->bLink;
}
ClearNode (btreePtr, targetNodePtr);
err = UpdateNode (btreePtr, targetNode);
M_ExitOnError (err);
err = FreeNode (btreePtr, targetNodeNum);
M_ExitOnError (err);
}
else if ( index == 0 ) {
updateRequired = true; }
if ( level == btreePtr->treeDepth ) {
deleteRequired = false;
updateRequired = false;
if ( targetNode->buffer == nil ) {
btreePtr->rootNode = 0;
btreePtr->treeDepth = 0;
}
else if ( ((NodeDescPtr)targetNode->buffer)->numRecords == 1 )
{
err = CollapseTree (btreePtr, targetNode);
M_ExitOnError (err);
}
}
if ( updateRequired || deleteRequired )
{
++level;
index = treePathTable [level].index;
err = GetNode (btreePtr, treePathTable[level].node, &parentNode);
M_ExitOnError (err);
if ( updateRequired )
{
KeyPtr keyPtr;
UInt8 * recPtr;
UInt16 recSize;
UInt32 insertNode;
GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p DeleteTree: parent ptr doesn't match targetNodeNum!!");
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 {
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;
}
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;
if ( ((NodeDescPtr)blockPtr->buffer)->kind == kBTLeafNode)
break;
nodeNum = btreePtr->rootNode;
btreePtr->rootNode = GetChildNodeNum (btreePtr, blockPtr->buffer, 0);
--btreePtr->treeDepth;
ClearNode (btreePtr, blockPtr->buffer);
err = UpdateNode (btreePtr, blockPtr);
M_ExitOnError (err);
err = FreeNode (btreePtr, nodeNum);
M_ExitOnError (err);
err = GetNode (btreePtr, btreePtr->rootNode, blockPtr);
M_ExitOnError (err);
}
if (btreePtr->rootNode != originalRoot)
M_BTreeHeaderDirty (btreePtr);
err = UpdateNode (btreePtr, blockPtr); M_ExitOnError (err);
return noErr;
ErrorExit:
(void) ReleaseNode (btreePtr, blockPtr);
return err;
}
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;
keyLength = GetKeyLength(btreePtr, keyPtr, (rightNode->kind == kBTLeafNode));
if ( btreePtr->attributes & kBTBigKeysMask )
lengthFieldSize = sizeof(UInt16);
else
lengthFieldSize = sizeof(UInt8);
insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16);
if ( M_IsOdd (insertSize) )
++insertSize;
nodeSize = btreePtr->nodeSize;
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 {
moveSize = GetRecordSize (btreePtr, rightNode, moveIndex - 1) + 2;
}
leftSize += moveSize;
rightSize -= moveSize;
++moveIndex;
}
if ( leftSize > nodeSize ) {
leftSize -= moveSize;
rightSize += moveSize;
--moveIndex;
}
if ( rightSize > nodeSize ) {
*insertIndex = 0;
*insertNodeNum = 0;
*recordFit = false;
*recsRotated = 0;
return noErr;
}
*recsRotated = moveIndex;
*recordFit = true;
index = 0;
while ( index < moveIndex )
{
if ( index == rightInsertIndex ) {
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 ) {
rightInsertIndex -= index;
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;
ErrorExit:
*insertIndex = 0;
*insertNodeNum = 0;
*recordFit = false;
*recsRotated = 0;
return err;
}
#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 )
{
OSStatus err;
NodeDescPtr left, right;
UInt32 newNodeNum;
Boolean recordFit;
right = rightNode->buffer;
left = leftNode->buffer;
PanicIf ( right->bLink != 0 && left == 0, "\p SplitLeft: left sibling missing!?" );
if ( (right->height == 1) && (right->kind != kBTLeafNode) )
return fsBTInvalidNodeErr;
if ( left != nil )
{
if ( left->fLink != rightNodeNum )
return fsBTInvalidNodeErr;
if ( left->height != right->height )
return fsBTInvalidNodeErr;
if ( left->kind != right->kind )
return fsBTInvalidNodeErr; }
err = AllocateNode (btreePtr, &newNodeNum);
M_ExitOnError (err);
if ( left != nil )
{
left->fLink = newNodeNum;
err = UpdateNode (btreePtr, leftNode);
M_ExitOnError (err);
}
err = GetNewNode (btreePtr, newNodeNum, leftNode);
M_ExitOnError (err);
left = leftNode->buffer;
left->fLink = rightNodeNum;
left->bLink = right->bLink;
left->kind = right->kind;
left->height = right->height;
right->bLink = newNodeNum;
if ( (left->kind == kBTLeafNode) && (left->bLink == 0) )
{
btreePtr->firstLeafNode = newNodeNum;
M_BTreeHeaderDirty (btreePtr); }
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);
*insertIndex = 0;
*insertNodeNum = 0;
*recsRotated = 0;
return err;
}
#endif
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;
}
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");
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;
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");
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
err = UpdateNode (btreePtr, &rootNode);
M_ExitOnError (err);
btreePtr->rootNode = rootNum;
btreePtr->flags |= kBTHeaderDirty;
return noErr;
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); else
length = btreePtr->maxKeyLength;
return length;
}
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;
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!?" );
if ( (leftPtr->height == 1) && (leftPtr->kind != kBTLeafNode) )
return fsBTInvalidNodeErr;
if ( rightPtr != nil )
{
if ( rightPtr->bLink != nodeNum )
return fsBTInvalidNodeErr;
if ( rightPtr->height != leftPtr->height )
return fsBTInvalidNodeErr;
if ( rightPtr->kind != leftPtr->kind )
return fsBTInvalidNodeErr; }
err = AllocateNode (btreePtr, &newNodeNum);
M_ExitOnError (err);
if ( rightPtr != nil )
{
rightPtr->bLink = newNodeNum;
err = UpdateNode (btreePtr, rightNodePtr);
M_ExitOnError (err);
}
err = GetNewNode (btreePtr, newNodeNum, rightNodePtr );
M_ExitOnError (err);
rightPtr = rightNodePtr->buffer;
rightPtr->bLink = nodeNum;
rightPtr->fLink = leftPtr->fLink;
rightPtr->kind = leftPtr->kind;
rightPtr->height = leftPtr->height;
leftPtr->fLink = newNodeNum;
if ( (rightPtr->kind == kBTLeafNode) && (rightPtr->fLink == 0) )
{
btreePtr->lastLeafNode = newNodeNum;
M_BTreeHeaderDirty (btreePtr); }
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);
*insertIndexPtr = 0;
*newNodeNumPtr = 0;
*recsRotatedPtr = 0;
return err;
}
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;
keyLength = GetKeyLength( btreePtr, keyPtr, (leftNodePtr->kind == kBTLeafNode) );
if ( btreePtr->attributes & kBTBigKeysMask )
lengthFieldSize = sizeof(UInt16);
else
lengthFieldSize = sizeof(UInt8);
insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16);
if ( M_IsOdd (insertSize) )
++insertSize; nodeSize = btreePtr->nodeSize;
rightSize = nodeSize - GetNodeFreeSize( btreePtr, rightNodePtr );
leftSize = nodeSize - GetNodeFreeSize( btreePtr, leftNodePtr ) + insertSize;
moveIndex = leftNodePtr->numRecords - 1; 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 ) {
leftSize += moveSize;
rightSize -= moveSize;
++moveIndex;
}
if ( leftSize > nodeSize ) {
*insertIndexPtr = 0;
*newNodeNumPtr = 0;
*didRecordFitPtr = false;
*recsRotatedPtr = 0;
return noErr;
}
*didRecordFitPtr = true;
index = leftNodePtr->numRecords - 1;
*recsRotatedPtr = index - moveIndex;
myInsertIndex = 0;
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;
}
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 ) {
didItFit = InsertKeyRecord (btreePtr, rightNodePtr, 0,
keyPtr, keyLength, recPtr, recSize);
if ( !didItFit )
{
Panic ("\pRotateRight: InsertKeyRecord (left) returned false!");
err = fsBTBadRotateErr;
goto ErrorExit;
}
doIncrement = true;
myInsertIndex = -1;
*newNodeNumPtr = leftNodePtr->fLink;
}
if ( doIncrement )
myInsertIndex++;
--index;
}
*insertIndexPtr = myInsertIndex;
if ( moveIndex >= leftInsertIndex ) {
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;
ErrorExit:
*insertIndexPtr = 0;
*newNodeNumPtr = 0;
*didRecordFitPtr = false;
*recsRotatedPtr = 0;
return err;
}
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;
}
#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 );
}
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
{
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 );
}
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" );
}
#endif // DEBUG_TREEOPS