/*
- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2008 Apple Inc. All rights reserved.
*
- * @APPLE_LICENSE_HEADER_START@
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
*
- * The contents of this file constitute Original Code as defined in and
- * are subject to the Apple Public Source License Version 1.1 (the
- * "License"). You may not use this file except in compliance with the
- * License. Please obtain a copy of the License at
- * http://www.apple.com/publicsource and read it before using this file.
+ * 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. The rights granted to you under the License
+ * may not be used to create, or enable the creation or redistribution of,
+ * unlawful or unlicensed copies of an Apple operating system, or to
+ * circumvent, violate, or enable the circumvention or violation of, any
+ * terms of an Apple operating system software license agreement.
*
- * This Original Code and all software distributed under the License are
- * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * 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 OR NON-INFRINGEMENT. Please see the
- * License for the specific language governing rights and limitations
- * under the License.
+ * 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@
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
*/
/*
File: BTreeTreeOps.c
*/
#include "../headers/BTreesPrivate.h"
+#include "../../hfs_btreeio.h"
//
/////////////////////// Routines Internal To BTree Module ///////////////////////
static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr,
NodeDescPtr leftNode,
NodeDescPtr rightNode,
- UInt16 rightInsertIndex,
+ u_int16_t rightInsertIndex,
KeyPtr keyPtr,
- UInt8 * recPtr,
- UInt16 recSize,
- UInt16 *insertIndex,
- UInt32 *insertNodeNum,
+ u_int8_t * recPtr,
+ u_int16_t recSize,
+ u_int16_t *insertIndex,
+ u_int32_t *insertNodeNum,
Boolean *recordFit,
- UInt16 *recsRotated );
+ u_int16_t *recsRotated );
static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr,
NodeDescPtr leftNode,
static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr,
BlockDescriptor *leftNode,
BlockDescriptor *rightNode,
- UInt32 rightNodeNum,
- UInt16 index,
+ u_int32_t rightNodeNum,
+ u_int16_t index,
KeyPtr keyPtr,
- UInt8 * recPtr,
- UInt16 recSize,
- UInt16 *insertIndex,
- UInt32 *insertNodeNum,
- UInt16 *recsRotated );
+ u_int8_t * recPtr,
+ u_int16_t recSize,
+ u_int16_t *insertIndex,
+ u_int32_t *insertNodeNum,
+ u_int16_t *recsRotated );
InsertKey *primaryKey,
InsertKey *secondaryKey,
BlockDescriptor *targetNode,
- UInt16 index,
- UInt16 level,
- UInt32 *insertNode );
+ u_int16_t index,
+ u_int16_t level,
+ u_int32_t *insertNode );
static OSErr InsertNode (BTreeControlBlockPtr btreePtr,
InsertKey *key,
BlockDescriptor *rightNode,
- UInt32 node,
- UInt16 index,
- UInt32 *newNode,
- UInt16 *newIndex,
+ 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 UInt16 GetKeyLength (const BTreeControlBlock *btreePtr,
+static u_int16_t GetKeyLength (const BTreeControlBlock *btreePtr,
const BTreeKey *key,
Boolean forLeafNode );
OSStatus SearchTree (BTreeControlBlockPtr btreePtr,
BTreeKeyPtr searchKey,
TreePathTable treePathTable,
- UInt32 *nodeNum,
+ u_int32_t *nodeNum,
BlockDescriptor *nodePtr,
- UInt16 *returnIndex )
+ u_int16_t *returnIndex )
{
OSStatus err;
- SInt16 level;
- UInt32 curNodeNum;
+ int16_t level; // Expected depth of current node
+ u_int32_t curNodeNum; // Current node we're searching
NodeRec nodeRec;
- UInt16 index;
+ u_int16_t index;
Boolean keyFound;
+ int8_t nodeKind; // Kind of current node (index/leaf)
KeyPtr keyPtr;
- UInt8 * dataPtr;
- UInt16 dataSize;
+ u_int8_t * dataPtr;
+ u_int16_t dataSize;
+
+ curNodeNum = btreePtr->rootNode;
+ level = btreePtr->treeDepth;
- if (btreePtr->treeDepth == 0) // is the tree empty?
+ if (level == 0) // is the tree empty?
{
err = fsBTEmptyErr;
goto ErrorExit;
}
- curNodeNum = btreePtr->rootNode;
-
//\80\80 for debugging...
treePathTable [0].node = 0;
treePathTable [0].index = 0;
while (true)
{
- PanicIf(curNodeNum == 0, "\pSearchTree: curNodeNum is zero!");
-
- err = GetNode (btreePtr, curNodeNum, &nodeRec);
- if (err != noErr)
- {
- goto ErrorExit;
- }
-
- keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index);
-
- level = ((BTNodeDescriptor*)nodeRec.buffer)->height; //\80\80 or --level;
+ //
+ // [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("SearchTree: curNodeNum is zero!");
+ err = btBadNode;
+ goto ErrorExit;
+ }
+
+ err = GetNode (btreePtr, curNodeNum, 0, &nodeRec);
+ if (err != noErr)
+ {
+ goto ErrorExit;
+ }
-
- treePathTable [level].node = curNodeNum;
-
- if ( ((BTNodeDescriptor*)nodeRec.buffer)->kind == kBTLeafNode)
- {
- treePathTable [level].index = index;
- break; // were done...
- }
-
- if ( (keyFound != true) && (index != 0))
- --index;
-
- treePathTable [level].index = index;
-
- GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize);
- curNodeNum = *(UInt32 *)dataPtr;
- err = ReleaseNode (btreePtr, &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)
+ {
+// Panic("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)
+ {
+ // Panic("Incorrect node type: expected leaf");
+ err = btBadNode;
+ goto ReleaseAndExit;
+ }
+ }
+ else
+ {
+ // A node at any other depth must be an index node
+ if (nodeKind != kBTIndexNode)
+ {
+// Panic("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.
+
+ (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)
+ {
+ goto ErrorExit;
+ }
+
+ // The child node should be at a level one less than the parent.
+ --level;
}
*nodeNum = curNodeNum;
else
return fsBTRecordNotFoundErr; // searchKey not found, index identifies insert point
+ReleaseAndExit:
+ (void) ReleaseNode(btreePtr, &nodeRec);
+ // fall into ErrorExit
+
ErrorExit:
*nodeNum = 0;
OSStatus InsertTree ( BTreeControlBlockPtr btreePtr,
TreePathTable treePathTable,
KeyPtr keyPtr,
- UInt8 * recPtr,
- UInt16 recSize,
+ u_int8_t * recPtr,
+ u_int16_t recSize,
BlockDescriptor *targetNode,
- UInt16 index,
- UInt16 level,
+ u_int16_t index,
+ u_int16_t level,
Boolean replacingKey,
- UInt32 *insertNode )
+ u_int32_t *insertNode )
{
InsertKey primaryKey;
OSStatus err;
InsertKey *primaryKey,
InsertKey *secondaryKey,
BlockDescriptor *targetNode,
- UInt16 index,
- UInt16 level,
- UInt32 *insertNode )
+ u_int16_t index,
+ u_int16_t level,
+ u_int32_t *insertNode )
{
OSStatus err;
BlockDescriptor leftNode;
- UInt32 targetNodeNum;
- UInt32 newNodeNum;
- UInt16 newIndex;
+ 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__)
- PanicIf ((level == 1) && (((NodeDescPtr)targetNode->buffer)->kind != kBTLeafNode), "\P InsertLevel: non-leaf at level 1! ");
+ PanicIf ((level == 1) && (((NodeDescPtr)targetNode->buffer)->kind != kBTLeafNode), " InsertLevel: non-leaf at level 1! ");
#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);
M_ExitOnError (err);
if ( DEBUG_BUILD && updateParent && newRoot )
- DebugStr("\p InsertLevel: New root from primary key, update from secondary key...");
+ DebugStr(" InsertLevel: New root from primary key, update from secondary key...");
}
//////////////////////// Update Parent(s) ///////////////////////////////
if ( insertParent || updateParent )
{
BlockDescriptor parentNode;
- UInt32 parentNodeNum;
+ u_int32_t parentNodeNum;
KeyPtr keyPtr;
- UInt8 * recPtr;
- UInt16 recSize;
+ u_int8_t * recPtr;
+ u_int16_t recSize;
+ parentNode.buffer = nil;
+ parentNode.blockHeader = nil;
+
secondaryKey = nil;
- PanicIf ( (level == btreePtr->treeDepth), "\p InsertLevel: unfinished insert!?");
+ PanicIf ( (level == btreePtr->treeDepth), " InsertLevel: unfinished insert!?");
++level;
index = treePathTable [level].index;
parentNodeNum = treePathTable [level].node;
- PanicIf ( parentNodeNum == 0, "\p InsertLevel: parent node is zero!?");
+ PanicIf ( parentNodeNum == 0, " InsertLevel: parent node is zero!?");
- err = GetNode (btreePtr, parentNodeNum, &parentNode); // released as target node in next level up
+ err = GetNode (btreePtr, parentNodeNum, 0, &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! ");
+ PanicIf ( ((NodeDescPtr)parentNode.buffer)->kind != kBTIndexNode, " InsertLevel: parent node not an index node! ");
#endif
////////////////////////// Update Parent Index //////////////////////////////
if ( updateParent )
{
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &parentNode);
+
//\80\80Â 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!");
+ PanicIf( (*(u_int32_t *) recPtr) != targetNodeNum, " 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
primaryKey->keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
primaryKey->keyLength = GetKeyLength(btreePtr, primaryKey->keyPtr, false);
- primaryKey->recPtr = (UInt8 *) &targetNodeNum;
+ 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
if ( insertParent )
{
InsertKey *insertKeyPtr;
- InsertKey insertKey;
if ( updateParent )
{
insertKeyPtr->keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode.buffer, 0);
insertKeyPtr->keyLength = GetKeyLength(btreePtr, insertKeyPtr->keyPtr, false);
- insertKeyPtr->recPtr = (UInt8 *) &((NodeDescPtr)targetNode->buffer)->bLink;
- insertKeyPtr->recSize = sizeof(UInt32);
+ 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
}
(void) ReleaseNode (btreePtr, targetNode);
(void) ReleaseNode (btreePtr, &leftNode);
- Panic ("\p InsertLevel: an error occured!");
+ Panic (" InsertLevel: an error occurred!");
return err;
InsertKey *key,
BlockDescriptor *rightNode,
- UInt32 node,
- UInt16 index,
+ u_int32_t node,
+ u_int16_t index,
- UInt32 *newNode,
- UInt16 *newIndex,
+ u_int32_t *newNode,
+ u_int16_t *newIndex,
BlockDescriptor *leftNode,
Boolean *updateParent,
Boolean *rootSplit )
{
BlockDescriptor *targetNode;
- UInt32 leftNodeNum;
- UInt16 recsRotated;
+ u_int32_t leftNodeNum;
+ u_int16_t recsRotated;
OSErr err;
Boolean recordFit;
*rootSplit = false;
- PanicIf ( rightNode->buffer == leftNode->buffer, "\p InsertNode: rightNode == leftNode, huh?");
+ PanicIf ( rightNode->buffer == leftNode->buffer, " InsertNode: rightNode == leftNode, huh?");
leftNodeNum = ((NodeDescPtr) rightNode->buffer)->bLink;
/////////////////////// Try Simple Insert ///////////////////////////////
- if ( node == leftNodeNum )
- targetNode = leftNode;
- else
- targetNode = rightNode;
-
+ /* 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 )
if ( !recordFit && leftNodeNum > 0 )
{
- PanicIf ( leftNode->buffer != nil, "\p InsertNode: leftNode already aquired!");
+ PanicIf ( leftNode->buffer != nil, " InsertNode: leftNode already acquired!");
if ( leftNode->buffer == nil )
{
- err = GetNode (btreePtr, leftNodeNum, leftNode); // will be released by caller or a split below
+ err = GetNode (btreePtr, leftNodeNum, 0, leftNode); // will be released by caller or a split below
M_ExitOnError (err);
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, leftNode);
}
- PanicIf ( ((NodeDescPtr) leftNode->buffer)->fLink != node, "\p InsertNode, RotateLeft: invalid sibling link!" );
+ PanicIf ( ((NodeDescPtr) leftNode->buffer)->fLink != node, " InsertNode, RotateLeft: invalid sibling link!" );
if ( !key->skipRotate ) // are rotates allowed?
{
return noErr;
ErrorExit:
-
(void) ReleaseNode (btreePtr, leftNode);
return err;
OSStatus DeleteTree (BTreeControlBlockPtr btreePtr,
TreePathTable treePathTable,
BlockDescriptor *targetNode,
- UInt16 index,
- UInt16 level )
+ u_int16_t index,
+ u_int16_t level )
{
OSStatus err;
BlockDescriptor parentNode;
BTNodeDescriptor *targetNodePtr;
- UInt32 targetNodeNum;
+ 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;
- PanicIf (targetNodePtr == nil, "\pDeleteTree: targetNode has nil buffer!");
+ PanicIf (targetNodePtr == nil, "DeleteTree: targetNode has nil buffer!");
+
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, targetNode);
DeleteRecord (btreePtr, targetNodePtr, index);
if ( targetNodePtr->numRecords == 0 ) // did we delete the last record?
{
BlockDescriptor siblingNode;
- UInt32 siblingNodeNum;
+ 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, &siblingNode);
+ 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);
siblingNodeNum = targetNodePtr->fLink; // Right Sibling Node
if ( siblingNodeNum != 0 )
{
- err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
+ 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);
err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);
M_ExitOnError (err);
+
err = FreeNode (btreePtr, targetNodeNum);
M_ExitOnError (err);
}
//// Get Parent Node and index
index = treePathTable [level].index;
- err = GetNode (btreePtr, treePathTable[level].node, &parentNode);
+ err = GetNode (btreePtr, treePathTable[level].node, 0, &parentNode);
M_ExitOnError (err);
if ( updateRequired )
{
KeyPtr keyPtr;
- UInt8 * recPtr;
- UInt16 recSize;
- UInt32 insertNode;
+ u_int8_t * recPtr;
+ u_int16_t recSize;
+ u_int32_t insertNode;
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &parentNode);
+
//\80\80Â 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!!");
+ PanicIf( (*(u_int32_t *) recPtr) != targetNodeNum, " 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;
+ recPtr = (u_int8_t *) &targetNodeNum;
recSize = sizeof(targetNodeNum);
err = InsertTree (btreePtr, treePathTable, keyPtr, recPtr, recSize,
return noErr;
ErrorExit:
-
+
(void) ReleaseNode (btreePtr, targetNode);
(void) ReleaseNode (btreePtr, &parentNode);
BlockDescriptor *blockPtr )
{
OSStatus err;
- UInt32 originalRoot;
- UInt32 nodeNum;
+ u_int32_t originalRoot;
+ u_int32_t nodeNum;
originalRoot = btreePtr->rootNode;
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, blockPtr);
+
while (true)
{
if ( ((NodeDescPtr)blockPtr->buffer)->numRecords > 1)
M_ExitOnError (err);
//// Get New Root Node
- err = GetNode (btreePtr, btreePtr->rootNode, blockPtr);
+ err = GetNode (btreePtr, btreePtr->rootNode, 0, blockPtr);
M_ExitOnError (err);
+
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, blockPtr);
}
if (btreePtr->rootNode != originalRoot)
static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr,
NodeDescPtr leftNode,
NodeDescPtr rightNode,
- UInt16 rightInsertIndex,
+ u_int16_t rightInsertIndex,
KeyPtr keyPtr,
- UInt8 * recPtr,
- UInt16 recSize,
- UInt16 *insertIndex,
- UInt32 *insertNodeNum,
+ u_int8_t * recPtr,
+ u_int16_t recSize,
+ u_int16_t *insertIndex,
+ u_int32_t *insertNodeNum,
Boolean *recordFit,
- UInt16 *recsRotated )
+ u_int16_t *recsRotated )
{
OSStatus err;
- SInt32 insertSize;
- SInt32 nodeSize;
- SInt32 leftSize, rightSize;
- SInt32 moveSize = 0;
- UInt16 keyLength;
- UInt16 lengthFieldSize;
- UInt16 index, moveIndex;
+ 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 //////////////////////////
// the key's length field is 8-bits in HFS and 16-bits in HFS+
if ( btreePtr->attributes & kBTBigKeysMask )
- lengthFieldSize = sizeof(UInt16);
+ lengthFieldSize = sizeof(u_int16_t);
else
- lengthFieldSize = sizeof(UInt8);
+ lengthFieldSize = sizeof(u_int8_t);
- insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16);
+ insertSize = keyLength + lengthFieldSize + recSize + sizeof(u_int16_t);
if ( M_IsOdd (insertSize) )
++insertSize; // add pad byte;
{
if ( index == rightInsertIndex ) // insert new record in left node
{
- UInt16 leftInsertIndex;
+ u_int16_t leftInsertIndex;
leftInsertIndex = leftNode->numRecords;
keyPtr, keyLength, recPtr, recSize);
if ( !didItFit )
{
- Panic ("\pRotateLeft: InsertKeyRecord (left) returned false!");
+ Panic ("RotateLeft: InsertKeyRecord (left) returned false!");
err = fsBTBadRotateErr;
goto ErrorExit;
}
didItFit = RotateRecordLeft (btreePtr, leftNode, rightNode);
if ( !didItFit )
{
- Panic ("\pRotateLeft: RotateRecordLeft returned false!");
+ Panic ("RotateLeft: RotateRecordLeft returned false!");
err = fsBTBadRotateErr;
goto ErrorExit;
}
keyPtr, keyLength, recPtr, recSize);
if ( !didItFit )
{
- Panic ("\pRotateLeft: InsertKeyRecord (right) returned false!");
+ Panic ("RotateLeft: InsertKeyRecord (right) returned false!");
err = fsBTBadRotateErr;
goto ErrorExit;
}
static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr,
BlockDescriptor *leftNode,
BlockDescriptor *rightNode,
- UInt32 rightNodeNum,
- UInt16 index,
+ u_int32_t rightNodeNum,
+ u_int16_t index,
KeyPtr keyPtr,
- UInt8 * recPtr,
- UInt16 recSize,
- UInt16 *insertIndex,
- UInt32 *insertNodeNum,
- UInt16 *recsRotated )
+ 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;
- UInt32 newNodeNum;
+ u_int32_t newNodeNum;
Boolean recordFit;
right = rightNode->buffer;
left = leftNode->buffer;
- PanicIf ( right->bLink != 0 && left == 0, "\p SplitLeft: left sibling missing!?" );
+ PanicIf ( right->bLink != 0 && left == 0, " SplitLeft: left sibling missing!?" );
/* type should be kBTLeafNode or kBTIndexNode */
if ( left != nil )
{
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, leftNode);
+
left->fLink = newNodeNum;
err = UpdateNode (btreePtr, leftNode, 0, kLockTransaction);
M_ExitOnError (err);
err = GetNewNode (btreePtr, newNodeNum, leftNode);
M_ExitOnError (err);
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, leftNode);
+
left = leftNode->buffer;
left->fLink = rightNodeNum;
err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize,
insertIndex, insertNodeNum, &recordFit, recsRotated);
- M_ExitOnError (err);
+ M_ExitOnError (err);
+
return noErr;
ErrorExit:
NodeDescPtr leftNode,
NodeDescPtr rightNode )
{
- UInt16 size;
- UInt8 * recPtr;
+ u_int16_t size;
+ u_int8_t * recPtr;
Boolean recordFit;
size = GetRecordSize (btreePtr, rightNode, 0);
{
OSStatus err;
BlockDescriptor rootNode;
- UInt32 rootNum;
+ u_int32_t rootNum;
KeyPtr keyPtr;
Boolean didItFit;
- UInt16 keyLength;
+ u_int16_t keyLength;
- PanicIf (leftNode == nil, "\pAddNewRootNode: leftNode == nil");
- PanicIf (rightNode == nil, "\pAddNewRootNode: rightNode == nil");
+ rootNode.buffer = nil;
+ rootNode.blockHeader = nil;
+
+ PanicIf (leftNode == nil, "AddNewRootNode: leftNode == nil");
+ PanicIf (rightNode == nil, "AddNewRootNode: rightNode == nil");
/////////////////////// Initialize New Root Node ////////////////////////////
err = GetNewNode (btreePtr, rootNum, &rootNode);
M_ExitOnError (err);
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &rootNode);
+
((NodeDescPtr)rootNode.buffer)->kind = kBTIndexNode;
((NodeDescPtr)rootNode.buffer)->height = ++btreePtr->treeDepth;
keyLength = GetKeyLength(btreePtr, keyPtr, false);
didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 0, keyPtr, keyLength,
- (UInt8 *) &rightNode->bLink, 4 );
+ (u_int8_t *) &rightNode->bLink, 4 );
- PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for left index record");
+ PanicIf ( !didItFit, "AddNewRootNode:InsertKeyRecord failed for left index record");
//////////////////// Insert Right Node Index Record /////////////////////////
keyLength = GetKeyLength(btreePtr, keyPtr, false);
didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 1, keyPtr, keyLength,
- (UInt8 *) &leftNode->fLink, 4 );
+ (u_int8_t *) &leftNode->fLink, 4 );
- PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for right index record");
+ PanicIf ( !didItFit, "AddNewRootNode:InsertKeyRecord failed for right index record");
/////////////////////////// Release Root Node ///////////////////////////////
}
-static UInt16 GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode )
+static u_int16_t GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode )
{
- UInt16 length;
+ u_int16_t length;
if ( forLeafNode || btreePtr->attributes & kBTVariableIndexKeysMask )
length = KeyLength (btreePtr, key); // just use actual key length
projects / apple / xnu.git / blobdiff