/*
- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2003 Apple Computer, Inc. All rights reserved.
*
* @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@
*/
*/
#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;
////////////////////// 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 );
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 )
* we cannot mount using the current physical block size.
*/
if (btreePtr->leafRecords > 0 ||
- VTOHFS(btreePtr->fileRefNum)->hfs_media_writeable)
+ VTOHFS(btreePtr->fileRefNum)->hfs_flags & HFS_WRITEABLE_MEDIA)
{
err = fsBTBadNodeSize;
goto ErrorExit;
}
else
{
- 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);
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);
/////////////////////// 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;
//////////////////////////// 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);
BTreeControlBlockPtr btreePtr;
TreePathTable treePathTable;
BlockDescriptor nodeRec;
+ SInt32 nodesNeeded;
UInt32 nodeNum;
UInt16 index;
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);
info->numNodes = btreePtr->totalNodes;
info->numFreeNodes = btreePtr->freeNodes;
info->lastfsync = btreePtr->lastfsync;
- info->reserved = 0;
-
+ info->keyCompareType = btreePtr->keyCompareType;
return noErr;
}
}
-/*-------------------------------------------------------------------------------
-Routine: BTCheckFreeSpace
-
-Function: Makes sure there is enough free space so that a tree operation
- will succeed.
-
-Input: fcb - pointer file control block
-
-Output: none
-
-Result: noErr - success
-
--------------------------------------------------------------------------------*/
-
__private_extern__
-OSStatus BTCheckFreeSpace (FCB *filePtr)
+OSStatus BTHasContiguousNodes (FCB *filePtr)
{
BTreeControlBlockPtr btreePtr;
- int nodesNeeded, err = noErr;
M_ReturnErrorIf (filePtr == nil, paramErr);
M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
- // XXXdbg this is highly conservative but so much better than
- // winding up with turds on your disk.
- //
- nodesNeeded = (btreePtr->treeDepth + 1) * 10;
+ 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);
- if (btreePtr->freeNodes < nodesNeeded) {
- err = ExtendBTree(btreePtr, nodesNeeded + btreePtr->totalNodes - btreePtr->freeNodes);
- }
+ offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
+ bcopy(offset, dataPtr, dataSize);
- return err;
+ (void) ReleaseNode(btreePtr, &node);
+
+ return (0);
}
+/*-------------------------------------------------------------------------------
+Routine: BTSetUserData
+
+Function: Write the user data area of the b-tree header node.
+-------------------------------------------------------------------------------*/
__private_extern__
-OSStatus BTHasContiguousNodes (FCB *filePtr)
+OSStatus
+BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize)
{
- BTreeControlBlockPtr btreePtr;
- int nodesNeeded, err = noErr;
-
+ BTreeControlBlockPtr btreePtr;
+ BlockDescriptor node;
+ char * offset;
+ OSStatus err;
- M_ReturnErrorIf (filePtr == nil, paramErr);
+ 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);
- REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
+ ModifyBlockStart(btreePtr->fileRefNum, &node);
- M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
+ offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
+ bcopy(dataPtr, offset, dataSize);
- return NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize);
+ err = UpdateNode (btreePtr, &node, 0, 0);
+
+ return (err);
}
+
projects / apple / xnu.git / blobdiff