X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/9bccf70c0258c7cac2dcb80011b2a964d884c552..4a2492630c73add3c3aa8a805ba4ff343d4a58ea:/bsd/hfs/hfscommon/BTree/BTreeTreeOps.c diff --git a/bsd/hfs/hfscommon/BTree/BTreeTreeOps.c b/bsd/hfs/hfscommon/BTree/BTreeTreeOps.c index 2de280321..5268c653c 100644 --- a/bsd/hfs/hfscommon/BTree/BTreeTreeOps.c +++ b/bsd/hfs/hfscommon/BTree/BTreeTreeOps.c @@ -3,19 +3,22 @@ * * @APPLE_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. + * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved. * - * This Original Code and all software distributed under the License are - * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * 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 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@ */ @@ -395,13 +398,17 @@ OSStatus InsertLevel (BTreeControlBlockPtr btreePtr, PanicIf ((level == 1) && (((NodeDescPtr)targetNode->buffer)->kind != kBTLeafNode), "\P 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); @@ -446,6 +453,9 @@ OSStatus InsertLevel (BTreeControlBlockPtr btreePtr, UInt8 * recPtr; UInt16 recSize; + parentNode.buffer = nil; + parentNode.blockHeader = nil; + secondaryKey = nil; PanicIf ( (level == btreePtr->treeDepth), "\p InsertLevel: unfinished insert!?"); @@ -468,6 +478,9 @@ OSStatus InsertLevel (BTreeControlBlockPtr btreePtr, if ( updateParent ) { + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &parentNode); + //€€ 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!"); @@ -594,6 +607,8 @@ static OSErr InsertNode (BTreeControlBlockPtr btreePtr, { err = GetNode (btreePtr, leftNodeNum, 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!" ); @@ -642,7 +657,6 @@ static OSErr InsertNode (BTreeControlBlockPtr btreePtr, return noErr; ErrorExit: - (void) ReleaseNode (btreePtr, leftNode); return err; @@ -678,7 +692,11 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, 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; @@ -686,6 +704,9 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, targetNodePtr = targetNode->buffer; PanicIf (targetNodePtr == nil, "\pDeleteTree: targetNode has nil buffer!"); + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, targetNode); + DeleteRecord (btreePtr, targetNodePtr, index); //€€ coalesce remaining records? @@ -697,6 +718,9 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, deleteRequired = true; + siblingNode.buffer = nil; + siblingNode.blockHeader = nil; + ////////////////// Get Siblings & Update Links ////////////////////////// siblingNodeNum = targetNodePtr->bLink; // Left Sibling Node @@ -704,6 +728,10 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, { err = GetNode (btreePtr, siblingNodeNum, &siblingNode); M_ExitOnError (err); + + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &siblingNode); + ((NodeDescPtr)siblingNode.buffer)->fLink = targetNodePtr->fLink; err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction); M_ExitOnError (err); @@ -718,6 +746,10 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, { err = GetNode (btreePtr, siblingNodeNum, &siblingNode); M_ExitOnError (err); + + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &siblingNode); + ((NodeDescPtr)siblingNode.buffer)->bLink = targetNodePtr->bLink; err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction); M_ExitOnError (err); @@ -733,6 +765,7 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction); M_ExitOnError (err); + err = FreeNode (btreePtr, targetNodeNum); M_ExitOnError (err); } @@ -776,6 +809,9 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, UInt16 recSize; UInt32 insertNode; + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &parentNode); + //€€ 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!!"); @@ -805,7 +841,7 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, return noErr; ErrorExit: - + (void) ReleaseNode (btreePtr, targetNode); (void) ReleaseNode (btreePtr, &parentNode); @@ -826,6 +862,9 @@ static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr, originalRoot = btreePtr->rootNode; + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, blockPtr); + while (true) { if ( ((NodeDescPtr)blockPtr->buffer)->numRecords > 1) @@ -848,6 +887,9 @@ static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr, //// Get New Root Node err = GetNode (btreePtr, btreePtr->rootNode, blockPtr); M_ExitOnError (err); + + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, blockPtr); } if (btreePtr->rootNode != originalRoot) @@ -1110,6 +1152,9 @@ static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr, if ( left != nil ) { + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, leftNode); + left->fLink = newNodeNum; err = UpdateNode (btreePtr, leftNode, 0, kLockTransaction); M_ExitOnError (err); @@ -1121,6 +1166,9 @@ static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr, err = GetNewNode (btreePtr, newNodeNum, leftNode); M_ExitOnError (err); + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, leftNode); + left = leftNode->buffer; left->fLink = rightNodeNum; @@ -1145,8 +1193,9 @@ static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr, err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize, insertIndex, insertNodeNum, &recordFit, recsRotated); - M_ExitOnError (err); + M_ExitOnError (err); + return noErr; ErrorExit: @@ -1202,6 +1251,9 @@ static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr, Boolean didItFit; UInt16 keyLength; + rootNode.buffer = nil; + rootNode.blockHeader = nil; + PanicIf (leftNode == nil, "\pAddNewRootNode: leftNode == nil"); PanicIf (rightNode == nil, "\pAddNewRootNode: rightNode == nil"); @@ -1214,6 +1266,9 @@ static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr, err = GetNewNode (btreePtr, rootNum, &rootNode); M_ExitOnError (err); + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &rootNode); + ((NodeDescPtr)rootNode.buffer)->kind = kBTIndexNode; ((NodeDescPtr)rootNode.buffer)->height = ++btreePtr->treeDepth;