/*
- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2003, 2005-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: BTreeMiscOps.c
*/
#include "../headers/BTreesPrivate.h"
+#include "../../hfs_btreeio.h"
////////////////////////////// Routine Definitions //////////////////////////////
Output: none
-Result: UInt16 - size of combined key/record that will be inserted in btree
+Result: u_int16_t - size of combined key/record that will be inserted in btree
-------------------------------------------------------------------------------*/
-UInt16 CalcKeyRecordSize (UInt16 keySize,
- UInt16 recSize )
+u_int16_t CalcKeyRecordSize (u_int16_t keySize,
+ u_int16_t recSize )
{
if ( M_IsOdd (keySize) ) keySize += 1; // pad byte
OSStatus VerifyHeader (FCB *filePtr,
BTHeaderRec *header )
{
- UInt64 forkSize;
- UInt32 totalNodes;
+ u_int64_t forkSize;
+ u_int32_t totalNodes;
switch (header->nodeSize) // node size == 512*2^n
totalNodes = header->totalNodes;
- forkSize = (UInt64)totalNodes * (UInt64)header->nodeSize;
+ forkSize = (u_int64_t)totalNodes * (u_int64_t)header->nodeSize;
- if ( forkSize != filePtr->fcbEOF )
+ if ( forkSize > (u_int64_t)filePtr->fcbEOF )
return fsBTInvalidHeaderErr;
if ( header->freeNodes >= totalNodes )
OSStatus err;
BlockDescriptor node;
BTHeaderRec *header;
- UInt32 options;
+ u_int32_t options;
if ((btreePtr->flags & kBTHeaderDirty) == 0) // btree info already flushed
return noErr;
- err = GetNode (btreePtr, kHeaderNodeNum, &node );
+ err = GetNode (btreePtr, kHeaderNodeNum, 0, &node );
if (err != noErr) {
return err;
}
BlockDescriptor *left,
BlockDescriptor *middle,
BlockDescriptor *right,
- UInt32 *returnNodeNum,
- UInt16 *returnIndex,
+ u_int32_t *returnNodeNum,
+ u_int16_t *returnIndex,
Boolean *foundRecord )
{
OSStatus err;
Boolean foundIt;
- UInt32 nodeNum;
- UInt16 leftIndex, index, rightIndex;
+ u_int32_t nodeNum;
+ u_int16_t leftIndex, index, rightIndex;
Boolean validHint;
// assume btreePtr valid
// assume left, middle, right point to BlockDescriptors
- // assume nodeNum points to UInt32
- // assume index points to UInt16
+ // assume nodeNum points to u_int32_t
+ // assume index points to u_int16_t
// assume foundRecord points to Boolean
left->buffer = nil;
goto SearchTheTree;
}
- err = GetNode (btreePtr, nodeNum, middle);
+ err = GetNode (btreePtr, nodeNum, kGetNodeHint, middle);
if( err == fsBTInvalidNodeErr ) // returned if nodeNum is out of range
goto SearchTheTree;
((NodeDescPtr) middle->buffer)->numRecords <= 0 )
{
goto SearchTheTree;
- }
-
- ++btreePtr->numValidHints;
+ }
foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
if (foundIt == true)
{
+ ++btreePtr->numValidHints;
goto SuccessfulExit;
}
-
+ iterator->hint.nodeNum = 0;
+
if (index == 0)
{
if (((NodeDescPtr) middle->buffer)->bLink == 0) // before 1st btree record
nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
- err = GetLeftSiblingNode (btreePtr, middle->buffer, left);
+ // BTree nodes are always grabbed in left to right order.
+ // Therefore release the current node before looking up the
+ // left node.
+ err = ReleaseNode(btreePtr, middle);
+ M_ExitOnError(err);
+
+ // Look up the left node
+ err = GetNode (btreePtr, nodeNum, 0, left);
M_ExitOnError (err);
-
+
+ // Look up the current node again
+ err = GetRightSiblingNode (btreePtr, left->buffer, middle);
+ M_ExitOnError (err);
+
if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode ||
((NodeDescPtr) left->buffer)->numRecords <= 0 )
{
{
nodeNum = ((NodeDescPtr) left->buffer)->fLink;
- PanicIf (index != 0, "\pFindIteratorPosition: index != 0"); //\80\80 just checking...
+ PanicIf (index != 0, "FindIteratorPosition: index != 0"); //\80\80 just checking...
goto SuccessfulExit;
}
else
OSStatus CheckInsertParams (FCB *filePtr,
BTreeIterator *iterator,
FSBufferDescriptor *record,
- UInt16 recordLen )
+ u_int16_t recordLen )
{
BTreeControlBlockPtr btreePtr;
NodeDescPtr nodePtr,
BTreeIterator *iterator,
FSBufferDescriptor *record,
- UInt16 recordLen,
+ u_int16_t recordLen,
Boolean *recordInserted )
{
- UInt32 oldSpace;
- UInt32 spaceNeeded;
- UInt16 index;
- UInt16 keySize;
+ u_int32_t oldSpace;
+ u_int32_t spaceNeeded;
+ u_int16_t index;
+ u_int16_t keySize;
Boolean foundIt;
Boolean didItFit;
if ( spaceNeeded == oldSpace )
{
- UInt8 * dst;
+ u_int8_t * dst;
dst = GetRecordAddress (btreePtr, nodePtr, index);
didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
&iterator->key, KeyLength(btreePtr, &iterator->key),
record->bufferAddress, recordLen);
- PanicIf (didItFit == false, "\pTrySimpleInsert: InsertKeyRecord returned false!");
+ PanicIf (didItFit == false, "TrySimpleInsert: InsertKeyRecord returned false!");
*recordInserted = true;
}
projects / apple / xnu.git / blobdiff