#include "BTreePrivate.h"
UInt16 CalcKeyRecordSize (UInt16 keySize,
UInt16 recSize )
{
if ( M_IsOdd (keySize) ) keySize += 1;
if (M_IsOdd (recSize) ) recSize += 1;
return (keySize + recSize);
}
OSStatus VerifyHeader (SFCB *filePtr,
BTHeaderRec *header )
{
UInt32 forkSize;
UInt32 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 = totalNodes * header->nodeSize;
if ( forkSize != filePtr->fcbLogicalSize )
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 UpdateHeader (BTreeControlBlockPtr btreePtr)
{
OSStatus err;
BlockDescriptor node;
BTHeaderRec *header;
if ((btreePtr->flags & kBTHeaderDirty) == 0) return noErr;
err = GetNode (btreePtr, kHeaderNodeNum, &node );
if (err != noErr)
return err;
header = (BTHeaderRec*) (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;
err = UpdateNode (btreePtr, &node);
btreePtr->flags &= (~kBTHeaderDirty);
return err;
}
OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
BTreeIteratorPtr iterator,
BlockDescriptor *left,
BlockDescriptor *middle,
BlockDescriptor *right,
UInt32 *returnNodeNum,
UInt16 *returnIndex,
Boolean *foundRecord )
{
OSStatus err;
Boolean foundIt;
UInt32 nodeNum;
UInt16 leftIndex, index, rightIndex;
Boolean validHint;
left->buffer = nil;
middle->buffer = nil;
right->buffer = nil;
foundIt = false;
if (iterator == nil) {
err = fsBTInvalidIteratorErr;
goto ErrorExit;
}
#if SupportsKeyDescriptors
if (btreePtr->keyDescPtr != nil)
{
err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength );
M_ExitOnError (err);
}
#endif
err = IsItAHint (btreePtr, iterator, &validHint);
M_ExitOnError (err);
nodeNum = iterator->hint.nodeNum;
if (! validHint) {
goto SearchTheTree;
}
err = GetNode (btreePtr, nodeNum, middle);
if( err == fsBTInvalidNodeErr ) goto SearchTheTree;
M_ExitOnError (err);
if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode ||
((NodeDescPtr) middle->buffer)->numRecords <= 0 )
{
goto SearchTheTree;
}
++btreePtr->numValidHints;
foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
if (foundIt == true)
{
goto SuccessfulExit;
}
if (index == 0)
{
if (((NodeDescPtr) middle->buffer)->bLink == 0) {
goto SuccessfulExit;
}
nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
err = GetLeftSiblingNode (btreePtr, middle->buffer, left);
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;
PanicIf (index != 0, "\pFindIteratorPosition: index != 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 (SFCB *filePtr,
BTreeIterator *iterator,
FSBufferDescriptor *record,
UInt16 recordLen )
{
BTreeControlBlockPtr btreePtr;
if (filePtr == nil) return paramErr;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
if (btreePtr == nil) return fsBTInvalidFileErr;
if (iterator == nil) return paramErr;
if (record == nil) return paramErr;
#if SupportsKeyDescriptors
if (btreePtr->keyDescPtr != nil)
{
OSStatus err;
err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
if (err != noErr)
return err;
}
#endif
if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
return fsBTRecordTooLargeErr;
return noErr;
}
OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
NodeDescPtr nodePtr,
BTreeIterator *iterator,
FSBufferDescriptor *record,
UInt16 recordLen,
Boolean *recordInserted )
{
UInt32 oldSpace;
UInt32 spaceNeeded;
UInt16 index;
UInt16 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 )
{
UInt8 * dst;
dst = GetRecordAddress (btreePtr, nodePtr, index);
if ( M_IsOdd (keySize) )
++keySize;
dst += keySize;
CopyMemory(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);
PanicIf (didItFit == false, "\pTrySimpleInsert: InsertKeyRecord returned false!");
*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;
}