/*
- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2004 Apple Computer, 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: BTree.c
#include "../headers/BTreesPrivate.h"
-#include "../headers/HFSInstrumentation.h"
-
/*
* The amount that the BTree header leaf count can be wrong before we assume
* it is in an infinite loop.
*/
#define kNumLeafRecSlack 10
+/* BTree accessor routines */
+extern OSStatus GetBTreeBlock(FileReference vp, UInt32 blockNum, GetBlockOptions options, BlockDescriptor *block);
+extern OSStatus SetBTreeBlockSize(FileReference vp, ByteCount blockSize, ItemCount minBlockCount);
+extern OSStatus ExtendBTreeFile(FileReference vp, FSSize minEOF, FSSize maxEOF);
+extern OSStatus ReleaseBTreeBlock(FileReference vp, BlockDescPtr blockPtr, ReleaseBlockOptions options);
+
//////////////////////////////////// Globals ////////////////////////////////////
Input: filePtr - pointer to file to open as a B-tree
keyCompareProc - pointer to client's KeyCompare function
- getBlockProc - pointer to client's GetBlock function
- releaseBlockProc - pointer to client's ReleaseBlock function
- setEndOfForkProc - pointer to client's SetEOF function
Result: noErr - success
paramErr - required ptr was nil
!= noErr - failure
-------------------------------------------------------------------------------*/
-OSStatus BTOpenPath (FCB *filePtr,
- KeyCompareProcPtr keyCompareProc,
- GetBlockProcPtr getBlockProc,
- ReleaseBlockProcPtr releaseBlockProc,
- SetEndOfForkProcPtr setEndOfForkProc,
- SetBlockSizeProcPtr setBlockSizeProc )
+OSStatus BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc)
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
BTHeaderRec *header;
NodeRec nodeRec;
- LogStartTime(kTraceOpenBTree);
-
////////////////////// Preliminary Error Checking ///////////////////////////
- if ( filePtr == nil ||
- getBlockProc == nil ||
- releaseBlockProc == nil ||
- setEndOfForkProc == nil ||
- setBlockSizeProc == nil )
+ if ( filePtr == nil )
{
return paramErr;
}
- if ( filePtr->fcbBTCBPtr != nil ) // already has a BTreeCB
+ /*
+ * Subsequent opens allow key compare proc to be changed.
+ */
+ if ( filePtr->fcbBTCBPtr != nil && keyCompareProc != nil) {
+ btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+ btreePtr->keyCompareProc = keyCompareProc;
return noErr;
+ }
- // is file large enough to contain header node?
if ( filePtr->fcbEOF < kMinNodeSize )
- return fsBTInvalidFileErr; //\80\80 or E_BadHeader?
+ return fsBTInvalidFileErr;
//////////////////////// Allocate Control Block /////////////////////////////
return memFullErr;
}
- btreePtr->getBlockProc = getBlockProc;
- btreePtr->releaseBlockProc = releaseBlockProc;
- btreePtr->setEndOfForkProc = setEndOfForkProc;
+ btreePtr->getBlockProc = GetBTreeBlock;
+ btreePtr->releaseBlockProc = ReleaseBTreeBlock;
+ btreePtr->setEndOfForkProc = ExtendBTreeFile;
btreePtr->keyCompareProc = keyCompareProc;
/////////////////////////// Read Header Node ////////////////////////////////
/* The minimum node size is the physical block size */
nodeRec.blockSize = VTOHFS(btreePtr->fileRefNum)->hfs_phys_block_size;
+ /* Start with the allocation block size for regular files. */
+ if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
+ {
+ nodeRec.blockSize = FCBTOVCB(filePtr)->blockSize;
+ }
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
// it is now safe to call M_ExitOnError (err)
- err = setBlockSizeProc (btreePtr->fileRefNum, nodeRec.blockSize, 1);
+ err = SetBTreeBlockSize (btreePtr->fileRefNum, nodeRec.blockSize, 1);
M_ExitOnError (err);
- err = getBlockProc (btreePtr->fileRefNum,
+ err = GetBTreeBlock(btreePtr->fileRefNum,
kHeaderNodeNum,
kGetBlock,
&nodeRec );
Panic("\pBTOpen: getNodeProc returned error getting header node.");
goto ErrorExit;
}
-
+ ++btreePtr->numGetNodes;
header = (BTHeaderRec*) ((u_long)nodeRec.buffer + sizeof(BTNodeDescriptor));
btreePtr->maxKeyLength = header->maxKeyLength;
btreePtr->totalNodes = header->totalNodes;
btreePtr->freeNodes = header->freeNodes;
- // ignore header->clumpSize; //\80\80 rename this field?
+ if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
+ filePtr->ff_clumpsize = header->clumpSize;
btreePtr->btreeType = header->btreeType;
+ btreePtr->keyCompareType = header->keyCompareType;
+
btreePtr->attributes = header->attributes;
if ( btreePtr->maxKeyLength > 40 )
btreePtr->flags = 0;
btreePtr->writeCount = 1;
- btreePtr->numGetNodes = 1; // for earlier call to getNodeProc
-
/////////////////////////// Check Header Node ///////////////////////////////
- //\80\80 set kBadClose attribute bit, and UpdateNode
-
- // if nodeSize matches then we don't need to release, just CheckNode
+ // set kBadClose attribute bit, and UpdateNode
/* b-tree node size must be at least as big as the physical block size */
- if (btreePtr->nodeSize < nodeRec.blockSize) {
- err = fsBTBadNodeSize;
- goto ErrorExit;
- }
-
- if ( btreePtr->nodeSize == nodeRec.blockSize )
+ if (btreePtr->nodeSize < nodeRec.blockSize)
{
- err = CheckNode (btreePtr, nodeRec.buffer);
- if (err)
- VTOVCB(btreePtr->fileRefNum)->vcbFlags |= kHFS_DamagedVolume;
- M_ExitOnError (err);
+ /*
+ * If this tree has any records or the media is writeable then
+ * we cannot mount using the current physical block size.
+ */
+ if (btreePtr->leafRecords > 0 ||
+ VTOHFS(btreePtr->fileRefNum)->hfs_flags & HFS_WRITEABLE_MEDIA)
+ {
+ err = fsBTBadNodeSize;
+ goto ErrorExit;
+ }
}
- else
+
+ /*
+ * If the actual node size is different than the amount we read,
+ * then release and trash this block, and re-read with the correct
+ * node size.
+ */
+ if ( btreePtr->nodeSize != nodeRec.blockSize )
{
- err = setBlockSizeProc (btreePtr->fileRefNum, btreePtr->nodeSize, 32); //\80\80 we should try and get this down to 8
+ err = SetBTreeBlockSize (btreePtr->fileRefNum, btreePtr->nodeSize, 32);
M_ExitOnError (err);
/*
* Need to use kTrashBlock option to force the
* buffer cache to read the entire node
*/
- err = releaseBlockProc(btreePtr->fileRefNum, &nodeRec, kTrashBlock);
+ err = ReleaseBTreeBlock(btreePtr->fileRefNum, &nodeRec, kTrashBlock);
+ ++btreePtr->numReleaseNodes;
M_ExitOnError (err);
- err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec ); // calls CheckNode...
+ err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec );
M_ExitOnError (err);
}
/*
* Under Mac OS, b-tree nodes can be non-contiguous on disk when the
* allocation block size is smaller than the b-tree node size.
+ *
+ * If journaling is turned on for this volume we can't deal with this
+ * situation and so we bail out. If journaling isn't on it's ok as
+ * hfs_strategy_fragmented() deals with it. Journaling can't support
+ * this because it assumes that if you give it a block that it's
+ * contiguous on disk.
*/
- if ( !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) )
+ if ( FCBTOHFS(filePtr)->jnl && !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) ) {
return fsBTInvalidNodeErr;
+ }
//////////////////////////////// Success ////////////////////////////////////
//\80\80 align LEOF to multiple of node size? - just on close
- LogEndTime(kTraceOpenBTree, noErr);
-
return noErr;
(void) ReleaseNode (btreePtr, &nodeRec);
DisposePtr( (Ptr) btreePtr );
- LogEndTime(kTraceOpenBTree, err);
-
return err;
}
OSStatus err;
BTreeControlBlockPtr btreePtr;
- LogStartTime(kTraceCloseBTree);
-
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
if (btreePtr == nil)
DisposePtr( (Ptr) btreePtr );
filePtr->fcbBTCBPtr = nil;
- LogEndTime(kTraceCloseBTree, noErr);
-
return noErr;
/////////////////////// Error - Clean Up and Exit ///////////////////////////
ErrorExit:
- LogEndTime(kTraceCloseBTree, err);
-
return err;
}
OSStatus BTSearchRecord (FCB *filePtr,
BTreeIterator *searchIterator,
- UInt32 heuristicHint,
FSBufferDescriptor *record,
UInt16 *recordLen,
BTreeIterator *resultIterator )
Boolean foundRecord;
Boolean validHint;
-
- LogStartTime(kTraceSearchBTree);
-
if (filePtr == nil) return paramErr;
if (searchIterator == nil) return paramErr;
+ node.buffer = nil;
+ node.blockHeader = nil;
+
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
if (btreePtr == nil) return fsBTInvalidFileErr;
(void) BTInvalidateHint( searchIterator );
}
- ////////////////////////////// Try the heuristicHint //////////////////////////////////
-
- if ( (foundRecord == false) && (heuristicHint != kInvalidMRUCacheKey) && (nodeNum != heuristicHint) )
- {
- LogStartTime(kHeuristicHint);
- nodeNum = heuristicHint;
-
- err = GetNode (btreePtr, nodeNum, &node);
- if( err == noErr )
- {
- if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode &&
- ((BTNodeDescriptor*) node.buffer)->numRecords > 0 )
- {
- foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
- }
-
- if (foundRecord == false)
- {
- err = ReleaseNode (btreePtr, &node);
- M_ExitOnError (err);
- }
- }
- LogEndTime(kHeuristicHint, (foundRecord == false));
- }
//////////////////////////// Search The Tree ////////////////////////////////
err = ReleaseNode (btreePtr, &node);
M_ExitOnError (err);
- LogEndTime(kTraceSearchBTree, (foundRecord == false));
-
if (foundRecord == false) return fsBTRecordNotFoundErr;
else return noErr;
if ( err == fsBTEmptyErr )
err = fsBTRecordNotFoundErr;
- LogEndTime(kTraceSearchBTree, err);
-
return err;
}
UInt16 index;
- LogStartTime(kTraceGetBTreeRecord);
-
////////////////////////// Priliminary Checks ///////////////////////////////
- left.buffer = nil;
- right.buffer = nil;
- node.buffer = nil;
+ left.buffer = nil;
+ left.blockHeader = nil;
+ right.buffer = nil;
+ right.blockHeader = nil;
+ node.buffer = nil;
+ node.blockHeader = nil;
if (filePtr == nil)
M_ExitOnError (err);
}
- LogEndTime(kTraceGetBTreeRecord, noErr);
-
return noErr;
/////////////////////// Error - Clean Up and Exit ///////////////////////////
if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
err = fsBTRecordNotFoundErr;
- LogEndTime(kTraceGetBTreeRecord, err);
-
return err;
}
////////////////////////// Priliminary Checks ///////////////////////////////
- left.buffer = nil;
- right.buffer = nil;
- node.buffer = nil;
+ left.buffer = nil;
+ left.blockHeader = nil;
+ right.buffer = nil;
+ right.blockHeader = nil;
+ node.buffer = nil;
+ node.blockHeader = nil;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
err = FindIteratorPosition(btreePtr, iterator, &left, &node, &right,
&nodeNum, &index, &foundRecord);
+ if (err == fsBTRecordNotFoundErr)
+ err = 0;
M_ExitOnError(err);
ProcessData:
err = GetRecordByIndex(btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
+ if (err) {
+ err = btBadNode;
+ goto ErrorExit;
+ }
while (err == 0) {
- if (callBackProc(keyPtr, recordPtr, len, callBackState) == 0)
+ if (callBackProc(keyPtr, recordPtr, callBackState) == 0)
break;
if ((index+1) < ((NodeDescPtr)node.buffer)->numRecords) {
}
err = GetRecordByIndex(btreePtr, node.buffer, index,
&keyPtr, &recordPtr, &len);
+ if (err) {
+ err = btBadNode;
+ goto ErrorExit;
+ }
}
UInt16 index;
Boolean recordFit;
-
////////////////////////// Priliminary Checks ///////////////////////////////
nodeRec.buffer = nil; // so we can call ReleaseNode
+ nodeRec.blockHeader = nil;
err = CheckInsertParams (filePtr, iterator, record, recordLen);
if (err != noErr)
return err;
- LogStartTime(kTraceInsertBTreeRecord);
-
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
case fsBTEmptyErr: // if tree empty add 1st leaf node
- if (btreePtr->freeNodes == 0)
+ if (BTAvailableNodes(btreePtr) == 0)
{
err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
M_ExitOnError (err);
err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
M_ExitOnError (err);
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
((NodeDescPtr)nodeRec.buffer)->height = 1;
goto ErrorExit;
}
- err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
- M_ExitOnError (err);
-
- // update BTreeControlBlock
+ /*
+ * Update the B-tree control block. Do this before
+ * calling UpdateNode since it will compare the node's
+ * height with treeDepth.
+ */
btreePtr->treeDepth = 1;
btreePtr->rootNode = insertNodeNum;
btreePtr->firstLeafNode = insertNodeNum;
btreePtr->lastLeafNode = insertNodeNum;
+
+ err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
+ M_ExitOnError (err);
+
M_BTreeHeaderDirty (btreePtr);
goto Success;
if (index > 0)
{
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
&iterator->key, KeyLength(btreePtr, &iterator->key),
record->bufferAddress, recordLen);
/////////////////////// Extend File If Necessary ////////////////////////////
- nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //\80\80 math limit
+ nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
if (nodesNeeded > 0)
{
- nodesNeeded += btreePtr->totalNodes;
+ nodesNeeded += (SInt32)btreePtr->totalNodes;
if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
++nodesNeeded;
++btreePtr->writeCount;
++btreePtr->leafRecords;
M_BTreeHeaderDirty (btreePtr);
-
+
// create hint
iterator->hint.writeCount = btreePtr->writeCount;
iterator->hint.nodeNum = insertNodeNum;
iterator->hint.reserved1 = 0;
iterator->hint.reserved2 = 0;
- LogEndTime(kTraceInsertBTreeRecord, noErr);
-
return noErr;
if (err == fsBTEmptyErr)
err = fsBTRecordNotFoundErr;
- LogEndTime(kTraceInsertBTreeRecord, err);
-
return err;
}
////////////////////////// Priliminary Checks ///////////////////////////////
nodeRec.buffer = nil; // so we can call ReleaseNode
+ nodeRec.blockHeader = nil;
err = CheckInsertParams (filePtr, iterator, record, recordLen);
if (err != noErr)
return err;
- LogStartTime(kTraceReplaceBTreeRecord);
-
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
err = GetNode (btreePtr, insertNodeNum, &nodeRec);
if( err == noErr )
{
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
M_ExitOnError (err);
// optimization - if simple replace will work then don't extend btree
// \80\80 if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
M_ExitOnError (err);
//////////////////////////// Make Some Room /////////////////////////////////
- nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //\80\80 math limit
+ nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
if (nodesNeeded > 0)
{
- nodesNeeded += btreePtr->totalNodes;
+ nodesNeeded += (SInt32)btreePtr->totalNodes;
if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
++nodesNeeded;
M_ExitOnError (err);
}
-
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record
err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
iterator->hint.reserved1 = 0;
iterator->hint.reserved2 = 0;
- LogEndTime(kTraceReplaceBTreeRecord, noErr);
-
return noErr;
iterator->hint.reserved1 = 0;
iterator->hint.reserved2 = 0;
+ return err;
+}
+
+
+
+//////////////////////////////// BTUpdateRecord ////////////////////////////////
+
+OSStatus
+BTUpdateRecord(FCB *filePtr, BTreeIterator *iterator,
+ IterateCallBackProcPtr callBackProc, void * callBackState)
+{
+ OSStatus err;
+ BTreeControlBlockPtr btreePtr;
+ TreePathTable treePathTable;
+ BlockDescriptor nodeRec;
+ RecordPtr recordPtr;
+ BTreeKeyPtr keyPtr;
+ UInt32 insertNodeNum;
+ UInt16 recordLen;
+ UInt16 index;
+ Boolean validHint;
+
+
+ ////////////////////////// Priliminary Checks ///////////////////////////////
+
+ nodeRec.buffer = nil; // so we can call ReleaseNode
+ nodeRec.blockHeader = nil;
+
+ btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+
+ REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
+
+ ////////////////////////////// Take A Hint //////////////////////////////////
+
+ err = IsItAHint (btreePtr, iterator, &validHint);
+ M_ExitOnError (err);
+
+ if (validHint)
+ {
+ insertNodeNum = iterator->hint.nodeNum;
+
+ err = GetNode (btreePtr, insertNodeNum, &nodeRec);
+ if (err == noErr)
+ {
+ if (((NodeDescPtr)nodeRec.buffer)->kind == kBTLeafNode &&
+ SearchNode (btreePtr, nodeRec.buffer, &iterator->key, &index))
+ {
+ err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
+ M_ExitOnError (err);
+
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
+ err = callBackProc(keyPtr, recordPtr, callBackState);
+ M_ExitOnError (err);
+
+ err = UpdateNode (btreePtr, &nodeRec, 0, 0);
+ M_ExitOnError (err);
+
+ ++btreePtr->numValidHints;
+
+ goto Success;
+ }
+ else
+ {
+ (void) BTInvalidateHint( iterator );
+ }
+
+ err = ReleaseNode (btreePtr, &nodeRec);
+ M_ExitOnError (err);
+ }
+ else
+ {
+ (void) BTInvalidateHint( iterator );
+ }
+ }
+
+ ////////////////////////////// Get A Clue ///////////////////////////////////
+
+ err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
+ M_ExitOnError (err);
+
+ err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
+ M_ExitOnError (err);
+
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
+ err = callBackProc(keyPtr, recordPtr, callBackState);
+ M_ExitOnError (err);
+
+ err = UpdateNode (btreePtr, &nodeRec, 0, 0);
+ M_ExitOnError (err);
+
+Success:
+ // create hint
+ iterator->hint.writeCount = btreePtr->writeCount;
+ iterator->hint.nodeNum = insertNodeNum;
+ iterator->hint.index = 0;
+ iterator->hint.reserved1 = 0;
+ iterator->hint.reserved2 = 0;
+ return noErr;
+
+ ////////////////////////////// Error Exit ///////////////////////////////////
- LogEndTime(kTraceReplaceBTreeRecord, err);
+ErrorExit:
+ (void) ReleaseNode (btreePtr, &nodeRec);
+
+ iterator->hint.writeCount = 0;
+ iterator->hint.nodeNum = 0;
+ iterator->hint.index = 0;
+ iterator->hint.reserved1 = 0;
+ iterator->hint.reserved2 = 0;
return err;
}
BTreeControlBlockPtr btreePtr;
TreePathTable treePathTable;
BlockDescriptor nodeRec;
+ SInt32 nodesNeeded;
UInt32 nodeNum;
UInt16 index;
- LogStartTime(kTraceDeleteBTreeRecord);
////////////////////////// Priliminary Checks ///////////////////////////////
nodeRec.buffer = nil; // so we can call ReleaseNode
+ nodeRec.blockHeader = nil;
M_ReturnErrorIf (filePtr == nil, paramErr);
M_ReturnErrorIf (iterator == nil, paramErr);
M_ExitOnError (err); // record must exit for Delete
+ /////////////////////// Extend File If Necessary ////////////////////////////
+
+ nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
+ if ((btreePtr->attributes & kBTVariableIndexKeysMask) && (nodesNeeded > 0))
+ {
+ nodesNeeded += (SInt32)btreePtr->totalNodes;
+ if (nodesNeeded > CalcMapBits (btreePtr))
+ ++nodesNeeded;
+
+ err = ExtendBTree (btreePtr, nodesNeeded);
+ M_ExitOnError (err);
+ }
+
///////////////////////////// Delete Record /////////////////////////////////
err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
++btreePtr->writeCount;
--btreePtr->leafRecords;
M_BTreeHeaderDirty (btreePtr);
-
+
iterator->hint.nodeNum = 0;
- LogEndTime(kTraceDeleteBTreeRecord, noErr);
-
return noErr;
////////////////////////////// Error Exit ///////////////////////////////////
ErrorExit:
(void) ReleaseNode (btreePtr, &nodeRec);
- LogEndTime(kTraceDeleteBTreeRecord, err);
-
return err;
}
info->numNodes = btreePtr->totalNodes;
info->numFreeNodes = btreePtr->freeNodes;
info->lastfsync = btreePtr->lastfsync;
- info->reserved = 0;
-
+ info->keyCompareType = btreePtr->keyCompareType;
return noErr;
}
+// XXXdbg
+__private_extern__
+OSStatus
+BTIsDirty(FCB *filePtr)
+{
+ BTreeControlBlockPtr btreePtr;
+ btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+ return TreeIsDirty(btreePtr);
+}
/*-------------------------------------------------------------------------------
Routine: BTFlushPath - Flush BTreeControlBlock to Header Node.
BTreeControlBlockPtr btreePtr;
- LogStartTime(kTraceFlushBTree);
-
M_ReturnErrorIf (filePtr == nil, paramErr);
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
- REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+ REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
err = UpdateHeader (btreePtr, false);
- LogEndTime(kTraceFlushBTree, err);
-
return err;
}
BTHeaderRec *header;
+ node.buffer = nil;
+ node.blockHeader = nil;
+
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
if (btreePtr == nil)
return (fsBTInvalidFileErr);
}
+__private_extern__
+OSStatus BTHasContiguousNodes (FCB *filePtr)
+{
+ BTreeControlBlockPtr btreePtr;
+
+
+ M_ReturnErrorIf (filePtr == nil, paramErr);
+
+ btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+
+ REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
+
+ M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
+
+ return NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize);
+}
+
+
+/*-------------------------------------------------------------------------------
+Routine: BTGetUserData
+
+Function: Read the user data area of the b-tree header node.
+
+-------------------------------------------------------------------------------*/
+__private_extern__
+OSStatus
+BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize)
+{
+ BTreeControlBlockPtr btreePtr;
+ BlockDescriptor node;
+ char * offset;
+ OSStatus err;
+
+ if (dataSize > kBTreeHeaderUserBytes)
+ return (EINVAL);
+ node.buffer = nil;
+ node.blockHeader = nil;
+
+ btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+ if (btreePtr == nil)
+ return (fsBTInvalidFileErr);
+
+ REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+
+ err = GetNode(btreePtr, kHeaderNodeNum, &node);
+ if (err)
+ return (err);
+
+ offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
+ bcopy(offset, dataPtr, dataSize);
+
+ (void) ReleaseNode(btreePtr, &node);
+
+ return (0);
+}
+
+
+/*-------------------------------------------------------------------------------
+Routine: BTSetUserData
+
+Function: Write the user data area of the b-tree header node.
+-------------------------------------------------------------------------------*/
+__private_extern__
+OSStatus
+BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize)
+{
+ BTreeControlBlockPtr btreePtr;
+ BlockDescriptor node;
+ char * offset;
+ OSStatus err;
+
+ if (dataSize > kBTreeHeaderUserBytes)
+ return (EINVAL);
+ node.buffer = nil;
+ node.blockHeader = nil;
+
+ btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+ if (btreePtr == nil)
+ return (fsBTInvalidFileErr);
+
+ REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+
+ err = GetNode(btreePtr, kHeaderNodeNum, &node);
+ if (err)
+ return (err);
+
+ ModifyBlockStart(btreePtr->fileRefNum, &node);
+
+ offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
+ bcopy(dataPtr, offset, dataSize);
+
+ err = UpdateNode (btreePtr, &node, 0, 0);
+
+ return (err);
+}
+
projects / apple / xnu.git / blobdiff