lf_hfs_btree_misc_ops.c [plain text]
#include "lf_hfs_btrees_private.h"
#include "lf_hfs_btrees_io.h"
#include "lf_hfs_utils.h"
u_int16_t CalcKeyRecordSize (u_int16_t keySize,
u_int16_t recSize )
{
if ( M_IsOdd (keySize) ) keySize += 1;
if (M_IsOdd (recSize) ) recSize += 1;
return (keySize + recSize);
}
OSStatus VerifyHeader (FCB *filePtr,
BTHeaderRec *header )
{
u_int64_t forkSize;
u_int32_t totalNodes;
switch (header->nodeSize) {
case 512:
case 1024:
case 2048:
case 4096:
case 8192:
case 16384:
case 32768: break;
default: return fsBTInvalidHeaderErr; }
totalNodes = header->totalNodes;
forkSize = (u_int64_t)totalNodes * (u_int64_t)header->nodeSize;
if ( forkSize > (u_int64_t)filePtr->fcbEOF )
return fsBTInvalidHeaderErr;
if ( header->freeNodes >= totalNodes )
return fsBTInvalidHeaderErr;
if ( header->rootNode >= totalNodes )
return fsBTInvalidHeaderErr;
if ( header->firstLeafNode >= totalNodes )
return fsBTInvalidHeaderErr;
if ( header->lastLeafNode >= totalNodes )
return fsBTInvalidHeaderErr;
if ( header->treeDepth > kMaxTreeDepth )
return fsBTInvalidHeaderErr;
switch (header->btreeType)
{
case 0: case kUserBTreeType: case kReservedBTreeType: break;
default: return fsBTUnknownVersionErr;
}
return noErr;
}
OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr)
{
return (btreePtr->flags & kBTHeaderDirty);
}
OSStatus UpdateHeader(BTreeControlBlockPtr btreePtr, Boolean forceWrite)
{
OSStatus err;
BlockDescriptor node;
BTHeaderRec *header;
u_int32_t options;
if ((btreePtr->flags & kBTHeaderDirty) == 0) return noErr;
err = GetNode (btreePtr, kHeaderNodeNum, 0, &node );
if (err != noErr) {
return err;
}
ModifyBlockStart(btreePtr->fileRefNum, &node);
header = (BTHeaderRec*) ((char *)node.buffer + sizeof(BTNodeDescriptor));
header->treeDepth = btreePtr->treeDepth;
header->rootNode = btreePtr->rootNode;
header->leafRecords = btreePtr->leafRecords;
header->firstLeafNode = btreePtr->firstLeafNode;
header->lastLeafNode = btreePtr->lastLeafNode;
header->nodeSize = btreePtr->nodeSize; header->maxKeyLength = btreePtr->maxKeyLength; header->totalNodes = btreePtr->totalNodes;
header->freeNodes = btreePtr->freeNodes;
header->btreeType = btreePtr->btreeType;
if (forceWrite)
options = kForceWriteBlock;
else
options = kLockTransaction;
err = UpdateNode (btreePtr, &node, 0, options);
btreePtr->flags &= (~kBTHeaderDirty);
return err;
}
OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
BTreeIteratorPtr iterator,
BlockDescriptor *left,
BlockDescriptor *middle,
BlockDescriptor *right,
u_int32_t *returnNodeNum,
u_int16_t *returnIndex,
Boolean *foundRecord )
{
OSStatus err;
Boolean foundIt;
u_int32_t nodeNum;
u_int16_t leftIndex, index, rightIndex;
Boolean validHint;
left->buffer = nil;
left->blockHeader = nil;
middle->buffer = nil;
middle->blockHeader = nil;
right->buffer = nil;
right->blockHeader = nil;
foundIt = false;
if (iterator == nil) {
err = fsBTInvalidIteratorErr;
goto ErrorExit;
}
err = IsItAHint (btreePtr, iterator, &validHint);
M_ExitOnError (err);
nodeNum = iterator->hint.nodeNum;
if (! validHint) {
goto SearchTheTree;
}
err = GetNode (btreePtr, nodeNum, kGetNodeHint, middle);
if( err == fsBTInvalidNodeErr ) goto SearchTheTree;
M_ExitOnError (err);
if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode ||
((NodeDescPtr) middle->buffer)->numRecords <= 0 )
{
goto SearchTheTree;
}
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) {
goto SuccessfulExit;
}
nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
err = ReleaseNode(btreePtr, middle);
M_ExitOnError(err);
err = GetNode (btreePtr, nodeNum, 0, left);
M_ExitOnError (err);
err = GetRightSiblingNode (btreePtr, left->buffer, middle);
M_ExitOnError (err);
if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode ||
((NodeDescPtr) left->buffer)->numRecords <= 0 )
{
goto SearchTheTree;
}
foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
if (foundIt == true)
{
*right = *middle;
*middle = *left;
left->buffer = nil;
index = leftIndex;
goto SuccessfulExit;
}
if (leftIndex == 0) {
goto SearchTheTree;
}
else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
{
nodeNum = ((NodeDescPtr) left->buffer)->fLink;
if (index != 0)
{
LFHFS_LOG(LEVEL_ERROR, "FindIteratorPosition: index != 0\n");
hfs_assert(0);
}
goto SuccessfulExit;
}
else
{
*right = *middle;
*middle = *left;
left->buffer = nil;
index = leftIndex;
goto SuccessfulExit;
}
}
else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
{
if (((NodeDescPtr) middle->buffer)->fLink == 0) {
goto SuccessfulExit;
}
nodeNum = ((NodeDescPtr) middle->buffer)->fLink;
err = GetRightSiblingNode (btreePtr, middle->buffer, right);
M_ExitOnError (err);
if ( ((NodeDescPtr) right->buffer)->kind != kBTLeafNode ||
((NodeDescPtr) right->buffer)->numRecords <= 0 )
{
goto SearchTheTree;
}
foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords) {
goto SearchTheTree;
}
else {
*left = *middle;
*middle = *right;
right->buffer = nil;
index = rightIndex;
goto SuccessfulExit;
}
}
SearchTheTree:
{
TreePathTable treePathTable;
err = ReleaseNode (btreePtr, left); M_ExitOnError (err);
err = ReleaseNode (btreePtr, middle); M_ExitOnError (err);
err = ReleaseNode (btreePtr, right); M_ExitOnError (err);
err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
switch (err) {
case noErr: foundIt = true; break;
case fsBTRecordNotFoundErr: break;
default: goto ErrorExit;
}
}
SuccessfulExit:
*returnNodeNum = nodeNum;
*returnIndex = index;
*foundRecord = foundIt;
return noErr;
ErrorExit:
(void) ReleaseNode (btreePtr, left);
(void) ReleaseNode (btreePtr, middle);
(void) ReleaseNode (btreePtr, right);
*returnNodeNum = 0;
*returnIndex = 0;
*foundRecord = false;
return err;
}
OSStatus CheckInsertParams (FCB *filePtr,
BTreeIterator *iterator,
FSBufferDescriptor *record,
u_int16_t recordLen )
{
BTreeControlBlockPtr btreePtr;
if (filePtr == nil) return paramErr;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
if (btreePtr == nil) return fsBTInvalidFileErr;
if (iterator == nil) return paramErr;
if (record == nil) return paramErr;
if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
return fsBTRecordTooLargeErr;
return noErr;
}
OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
NodeDescPtr nodePtr,
BTreeIterator *iterator,
FSBufferDescriptor *record,
u_int16_t recordLen,
Boolean *recordInserted )
{
u_int32_t oldSpace;
u_int32_t spaceNeeded;
u_int16_t index;
u_int16_t keySize;
Boolean foundIt;
Boolean didItFit;
*recordInserted = false;
if ( nodePtr->kind != kBTLeafNode )
return noErr;
foundIt = SearchNode (btreePtr, nodePtr, &iterator->key, &index);
if ( foundIt == false )
return noErr;
keySize = CalcKeySize(btreePtr, &iterator->key);
spaceNeeded = CalcKeyRecordSize (keySize, recordLen);
oldSpace = GetRecordSize (btreePtr, nodePtr, index);
if ( spaceNeeded == oldSpace )
{
u_int8_t * dst;
dst = GetRecordAddress (btreePtr, nodePtr, index);
if ( M_IsOdd (keySize) )
++keySize;
dst += keySize;
BlockMoveData(record->bufferAddress, dst, recordLen);
*recordInserted = true;
}
else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
{
DeleteRecord (btreePtr, nodePtr, index);
didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
&iterator->key, KeyLength(btreePtr, &iterator->key),
record->bufferAddress, recordLen);
if (didItFit == false)
{
LFHFS_LOG(LEVEL_ERROR, "TrySimpleInsert: InsertKeyRecord returned false!");
hfs_assert(0);
}
*recordInserted = true;
}
return noErr;
}
OSStatus IsItAHint (BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer)
{
++btreePtr->numHintChecks;
if (iterator->hint.nodeNum == 0)
{
*answer = false;
}
else
{
*answer = true;
++btreePtr->numPossibleHints;
}
return noErr;
}