#include "../headers/BTreesPrivate.h"
#define kNumLeafRecSlack 10
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);
OSStatus BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc)
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
BTHeaderRec *header;
NodeRec nodeRec;
if ( filePtr == nil )
{
return paramErr;
}
if ( filePtr->fcbBTCBPtr != nil && keyCompareProc != nil) {
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
btreePtr->keyCompareProc = keyCompareProc;
return noErr;
}
if ( filePtr->fcbEOF < kMinNodeSize )
return fsBTInvalidFileErr;
btreePtr = (BTreeControlBlock*) NewPtrSysClear( sizeof( BTreeControlBlock ) );
if (btreePtr == nil)
{
Panic ("\pBTOpen: no memory for btreePtr.");
return memFullErr;
}
btreePtr->getBlockProc = GetBTreeBlock;
btreePtr->releaseBlockProc = ReleaseBTreeBlock;
btreePtr->setEndOfForkProc = ExtendBTreeFile;
btreePtr->keyCompareProc = keyCompareProc;
nodeRec.buffer = nil; btreePtr->fileRefNum = GetFileRefNumFromFCB(filePtr);
filePtr->fcbBTCBPtr = (Ptr) btreePtr;
nodeRec.blockSize = VTOHFS(btreePtr->fileRefNum)->hfs_phys_block_size;
if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
{
nodeRec.blockSize = FCBTOVCB(filePtr)->blockSize;
}
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
err = SetBTreeBlockSize (btreePtr->fileRefNum, nodeRec.blockSize, 1);
M_ExitOnError (err);
err = GetBTreeBlock(btreePtr->fileRefNum,
kHeaderNodeNum,
kGetBlock,
&nodeRec );
if (err != noErr)
{
nodeRec.buffer = nil;
nodeRec.blockHeader = nil;
Panic("\pBTOpen: getNodeProc returned error getting header node.");
goto ErrorExit;
}
++btreePtr->numGetNodes;
header = (BTHeaderRec*) ((u_long)nodeRec.buffer + sizeof(BTNodeDescriptor));
err = VerifyHeader (filePtr, header);
M_ExitOnError (err);
PanicIf ( (FCBTOVCB(filePtr)->vcbSigWord != 0x4244) && (header->nodeSize == 512), "\p BTOpenPath: wrong node size for HFS+ volume!");
btreePtr->treeDepth = header->treeDepth;
btreePtr->rootNode = header->rootNode;
btreePtr->leafRecords = header->leafRecords;
btreePtr->firstLeafNode = header->firstLeafNode;
btreePtr->lastLeafNode = header->lastLeafNode;
btreePtr->nodeSize = header->nodeSize;
btreePtr->maxKeyLength = header->maxKeyLength;
btreePtr->totalNodes = header->totalNodes;
btreePtr->freeNodes = header->freeNodes;
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->attributes |= (kBTBigKeysMask + kBTVariableIndexKeysMask);
btreePtr->version = kBTreeVersion;
btreePtr->flags = 0;
btreePtr->writeCount = 1;
if (btreePtr->nodeSize < nodeRec.blockSize)
{
if (btreePtr->leafRecords > 0 ||
VTOHFS(btreePtr->fileRefNum)->hfs_flags & HFS_WRITEABLE_MEDIA)
{
err = fsBTBadNodeSize;
goto ErrorExit;
}
}
if ( btreePtr->nodeSize == nodeRec.blockSize )
{
err = CheckNode (btreePtr, nodeRec.buffer);
if (err)
VTOVCB(btreePtr->fileRefNum)->vcbFlags |= kHFS_DamagedVolume;
M_ExitOnError (err);
}
else
{
err = SetBTreeBlockSize (btreePtr->fileRefNum, btreePtr->nodeSize, 32);
M_ExitOnError (err);
err = ReleaseBTreeBlock(btreePtr->fileRefNum, &nodeRec, kTrashBlock);
++btreePtr->numReleaseNodes;
M_ExitOnError (err);
err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec ); M_ExitOnError (err);
}
err = ReleaseNode (btreePtr, &nodeRec);
M_ExitOnError (err);
if ( FCBTOHFS(filePtr)->jnl && !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) ) {
return fsBTInvalidNodeErr;
}
return noErr;
ErrorExit:
filePtr->fcbBTCBPtr = nil;
(void) ReleaseNode (btreePtr, &nodeRec);
DisposePtr( (Ptr) btreePtr );
return err;
}
OSStatus BTClosePath (FCB *filePtr)
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
if (btreePtr == nil)
return fsBTInvalidFileErr;
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
btreePtr->attributes &= ~kBTBadCloseMask; err = UpdateHeader (btreePtr, true);
M_ExitOnError (err);
DisposePtr( (Ptr) btreePtr );
filePtr->fcbBTCBPtr = nil;
return noErr;
ErrorExit:
return err;
}
OSStatus BTSearchRecord (FCB *filePtr,
BTreeIterator *searchIterator,
FSBufferDescriptor *record,
UInt16 *recordLen,
BTreeIterator *resultIterator )
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
TreePathTable treePathTable;
UInt32 nodeNum;
BlockDescriptor node;
UInt16 index;
BTreeKeyPtr keyPtr;
RecordPtr recordPtr;
UInt16 len;
Boolean foundRecord;
Boolean validHint;
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;
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
foundRecord = false;
err = IsItAHint (btreePtr, searchIterator, &validHint);
M_ExitOnError (err);
if (validHint)
{
nodeNum = searchIterator->hint.nodeNum;
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);
}
else
{
++btreePtr->numValidHints;
}
}
if( foundRecord == false )
(void) BTInvalidateHint( searchIterator );
}
if (foundRecord == false)
{
err = SearchTree ( btreePtr, &searchIterator->key, treePathTable, &nodeNum, &node, &index);
switch (err)
{
case noErr: foundRecord = true; break;
case fsBTRecordNotFoundErr: break;
default: goto ErrorExit;
}
}
if (foundRecord == true)
{
GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
if (recordLen != nil) *recordLen = len;
if (record != nil)
{
ByteCount recordSize;
recordSize = record->itemCount * record->itemSize;
if (len > recordSize) len = recordSize;
BlockMoveData (recordPtr, record->bufferAddress, len);
}
}
if (resultIterator != nil)
{
resultIterator->hint.writeCount = btreePtr->writeCount;
resultIterator->hint.nodeNum = nodeNum;
resultIterator->hint.index = index;
#if DEBUG_BUILD
resultIterator->hint.reserved1 = 0;
resultIterator->hint.reserved2 = 0;
resultIterator->version = 0;
resultIterator->reserved = 0;
#endif
if (foundRecord == true)
BlockMoveData ((Ptr)keyPtr, (Ptr)&resultIterator->key, CalcKeySize(btreePtr, keyPtr));
else
BlockMoveData ((Ptr)&searchIterator->key, (Ptr)&resultIterator->key, CalcKeySize(btreePtr, &searchIterator->key));
}
err = ReleaseNode (btreePtr, &node);
M_ExitOnError (err);
if (foundRecord == false) return fsBTRecordNotFoundErr;
else return noErr;
ErrorExit:
if (recordLen != nil)
*recordLen = 0;
if (resultIterator != nil)
{
resultIterator->hint.writeCount = 0;
resultIterator->hint.nodeNum = 0;
resultIterator->hint.index = 0;
resultIterator->hint.reserved1 = 0;
resultIterator->hint.reserved2 = 0;
resultIterator->version = 0;
resultIterator->reserved = 0;
resultIterator->key.length16 = 0; }
if ( err == fsBTEmptyErr )
err = fsBTRecordNotFoundErr;
return err;
}
OSStatus BTIterateRecord (FCB *filePtr,
BTreeIterationOperation operation,
BTreeIterator *iterator,
FSBufferDescriptor *record,
UInt16 *recordLen )
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
BTreeKeyPtr keyPtr;
RecordPtr recordPtr;
UInt16 len;
Boolean foundRecord;
UInt32 nodeNum;
BlockDescriptor left, node, right;
UInt16 index;
left.buffer = nil;
left.blockHeader = nil;
right.buffer = nil;
right.blockHeader = nil;
node.buffer = nil;
node.blockHeader = nil;
if (filePtr == nil)
{
return paramErr;
}
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
if (btreePtr == nil)
{
return fsBTInvalidFileErr; }
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
if ((operation != kBTreeFirstRecord) &&
(operation != kBTreeNextRecord) &&
(operation != kBTreeCurrentRecord) &&
(operation != kBTreePrevRecord) &&
(operation != kBTreeLastRecord))
{
err = fsInvalidIterationMovmentErr;
goto ErrorExit;
}
if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
{
if (operation == kBTreeFirstRecord) nodeNum = btreePtr->firstLeafNode;
else nodeNum = btreePtr->lastLeafNode;
if (nodeNum == 0)
{
err = fsBTEmptyErr;
goto ErrorExit;
}
err = GetNode (btreePtr, nodeNum, &node);
M_ExitOnError (err);
if ( ((NodeDescPtr) node.buffer)->kind != kBTLeafNode ||
((NodeDescPtr) node.buffer)->numRecords <= 0 )
{
err = ReleaseNode (btreePtr, &node);
M_ExitOnError (err);
err = fsBTInvalidNodeErr;
MARK_VOLUMEDAMAGED(filePtr);
goto ErrorExit;
}
if (operation == kBTreeFirstRecord) index = 0;
else index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1;
goto CopyData; }
err = FindIteratorPosition (btreePtr, iterator,
&left, &node, &right, &nodeNum, &index, &foundRecord);
M_ExitOnError (err);
if (operation == kBTreePrevRecord)
{
if (index > 0)
{
--index;
}
else
{
if (left.buffer == nil)
{
nodeNum = ((NodeDescPtr) node.buffer)->bLink;
if ( nodeNum > 0)
{
err = GetNode (btreePtr, nodeNum, &left);
M_ExitOnError (err);
} else {
err = fsBTStartOfIterationErr;
goto ErrorExit;
}
}
if (right.buffer != nil) {
err = ReleaseNode(btreePtr, &right);
M_ExitOnError(err);
}
right = node;
node = left;
left.buffer = nil;
index = ((NodeDescPtr) node.buffer)->numRecords -1;
}
}
else if (operation == kBTreeNextRecord)
{
if ((foundRecord != true) &&
(((NodeDescPtr) node.buffer)->fLink == 0) &&
(index == ((NodeDescPtr) node.buffer)->numRecords))
{
err = fsBTEndOfIterationErr;
goto ErrorExit;
}
if ((foundRecord == false) && (index != ((NodeDescPtr) node.buffer)->numRecords))
goto CopyData;
if (index < ((NodeDescPtr) node.buffer)->numRecords -1)
{
++index;
}
else
{
if (right.buffer == nil)
{
nodeNum = ((NodeDescPtr) node.buffer)->fLink;
if ( nodeNum > 0)
{
err = GetNode (btreePtr, nodeNum, &right);
M_ExitOnError (err);
} else {
err = fsBTEndOfIterationErr;
goto ErrorExit;
}
}
if (left.buffer != nil) {
err = ReleaseNode(btreePtr, &left);
M_ExitOnError(err);
}
left = node;
node = right;
right.buffer = nil;
index = 0;
}
}
else {
if ((foundRecord != true) &&
(index >= ((NodeDescPtr) node.buffer)->numRecords))
{
err = fsBTEndOfIterationErr;
goto ErrorExit;
}
}
CopyData:
err = GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
M_ExitOnError (err);
if (recordLen != nil)
*recordLen = len;
if (record != nil)
{
ByteCount recordSize;
recordSize = record->itemCount * record->itemSize;
if (len > recordSize) len = recordSize;
BlockMoveData (recordPtr, record->bufferAddress, len);
}
if (iterator != nil) {
iterator->hint.writeCount = btreePtr->writeCount;
iterator->hint.nodeNum = nodeNum;
iterator->hint.index = index;
iterator->hint.reserved1 = 0;
iterator->hint.reserved2 = 0;
iterator->version = 0;
iterator->reserved = 0;
if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
iterator->hitCount = 1;
else if (operation != kBTreeCurrentRecord)
iterator->hitCount += 1;
iterator->maxLeafRecs = max(btreePtr->leafRecords, iterator->maxLeafRecs);
#if 0
if (iterator->hitCount > iterator->maxLeafRecs + kNumLeafRecSlack)
{
err = fsBTInvalidNodeErr;
MARK_VOLUMEDAMAGED(filePtr);
goto ErrorExit;
}
#endif
BlockMoveData ((Ptr)keyPtr, (Ptr)&iterator->key, CalcKeySize(btreePtr, keyPtr));
}
err = ReleaseNode (btreePtr, &node);
M_ExitOnError (err);
if (left.buffer != nil)
{
err = ReleaseNode (btreePtr, &left);
M_ExitOnError (err);
}
if (right.buffer != nil)
{
err = ReleaseNode (btreePtr, &right);
M_ExitOnError (err);
}
return noErr;
ErrorExit:
(void) ReleaseNode (btreePtr, &left);
(void) ReleaseNode (btreePtr, &node);
(void) ReleaseNode (btreePtr, &right);
if (recordLen != nil)
*recordLen = 0;
if (iterator != nil)
{
iterator->hint.writeCount = 0;
iterator->hint.nodeNum = 0;
iterator->hint.index = 0;
iterator->hint.reserved1 = 0;
iterator->hint.reserved2 = 0;
iterator->version = 0;
iterator->reserved = 0;
iterator->key.length16 = 0;
}
if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
err = fsBTRecordNotFoundErr;
return err;
}
OSStatus
BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator *iterator,
IterateCallBackProcPtr callBackProc, void * callBackState)
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
BTreeKeyPtr keyPtr;
RecordPtr recordPtr;
UInt16 len;
Boolean foundRecord;
UInt32 nodeNum;
BlockDescriptor left, node, right;
UInt16 index;
left.buffer = nil;
left.blockHeader = nil;
right.buffer = nil;
right.blockHeader = nil;
node.buffer = nil;
node.blockHeader = nil;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
if ((operation != kBTreeFirstRecord) &&
(operation != kBTreeNextRecord) &&
(operation != kBTreeCurrentRecord) &&
(operation != kBTreePrevRecord) &&
(operation != kBTreeLastRecord))
{
err = fsInvalidIterationMovmentErr;
goto ErrorExit;
}
if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
{
if (operation == kBTreeFirstRecord)
nodeNum = btreePtr->firstLeafNode;
else
nodeNum = btreePtr->lastLeafNode;
if (nodeNum == 0)
{
err = fsBTEmptyErr;
goto ErrorExit;
}
err = GetNode(btreePtr, nodeNum, &node);
M_ExitOnError(err);
if ( ((NodeDescPtr)node.buffer)->kind != kBTLeafNode ||
((NodeDescPtr)node.buffer)->numRecords <= 0 )
{
err = ReleaseNode(btreePtr, &node);
M_ExitOnError(err);
err = fsBTInvalidNodeErr;
MARK_VOLUMEDAMAGED(filePtr);
goto ErrorExit;
}
if (operation == kBTreeFirstRecord)
index = 0;
else
index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1;
goto ProcessData;
}
err = FindIteratorPosition(btreePtr, iterator, &left, &node, &right,
&nodeNum, &index, &foundRecord);
if (err == fsBTRecordNotFoundErr)
err = 0;
M_ExitOnError(err);
if (operation == kBTreePrevRecord)
{
if (index > 0)
{
--index;
}
else
{
if (left.buffer == nil)
{
nodeNum = ((NodeDescPtr) node.buffer)->bLink;
if ( nodeNum > 0)
{
err = GetNode(btreePtr, nodeNum, &left);
M_ExitOnError(err);
} else {
err = fsBTStartOfIterationErr;
goto ErrorExit;
}
}
if (right.buffer != nil) {
err = ReleaseNode(btreePtr, &right);
M_ExitOnError(err);
}
right = node;
node = left;
left.buffer = nil;
index = ((NodeDescPtr) node.buffer)->numRecords -1;
}
}
else if (operation == kBTreeNextRecord)
{
if ((foundRecord != true) &&
(((NodeDescPtr)node.buffer)->fLink == 0) &&
(index == ((NodeDescPtr)node.buffer)->numRecords))
{
err = fsBTEndOfIterationErr;
goto ErrorExit;
}
if ((foundRecord == false) && (index != ((NodeDescPtr)node.buffer)->numRecords))
goto ProcessData;
if (index < ((NodeDescPtr)node.buffer)->numRecords -1)
{
++index;
}
else
{
if (right.buffer == nil)
{
nodeNum = ((NodeDescPtr)node.buffer)->fLink;
if ( nodeNum > 0)
{
err = GetNode(btreePtr, nodeNum, &right);
M_ExitOnError(err);
} else {
err = fsBTEndOfIterationErr;
goto ErrorExit;
}
}
if (left.buffer != nil) {
err = ReleaseNode(btreePtr, &left);
M_ExitOnError(err);
}
left = node;
node = right;
right.buffer = nil;
index = 0;
}
}
else {
if ((foundRecord != true) &&
(index >= ((NodeDescPtr)node.buffer)->numRecords))
{
err = fsBTEndOfIterationErr;
goto ErrorExit;
}
}
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)
break;
if ((index+1) < ((NodeDescPtr)node.buffer)->numRecords) {
++index;
} else {
if (right.buffer == nil)
{
nodeNum = ((NodeDescPtr)node.buffer)->fLink;
if ( nodeNum > 0)
{
err = GetNode(btreePtr, nodeNum, &right);
M_ExitOnError(err);
} else {
err = fsBTEndOfIterationErr;
break;
}
}
if (left.buffer != nil) {
err = ReleaseNode(btreePtr, &left);
M_ExitOnError(err);
}
left = node;
node = right;
right.buffer = nil;
index = 0;
}
err = GetRecordByIndex(btreePtr, node.buffer, index,
&keyPtr, &recordPtr, &len);
if (err) {
err = btBadNode;
goto ErrorExit;
}
}
if (iterator != nil) {
iterator->hint.writeCount = btreePtr->writeCount;
iterator->hint.nodeNum = nodeNum;
iterator->hint.index = index;
iterator->version = 0;
BlockMoveData((Ptr)keyPtr, (Ptr)&iterator->key, CalcKeySize(btreePtr, keyPtr));
}
M_ExitOnError(err);
err = ReleaseNode(btreePtr, &node);
M_ExitOnError(err);
if (left.buffer != nil)
{
err = ReleaseNode(btreePtr, &left);
M_ExitOnError(err);
}
if (right.buffer != nil)
{
err = ReleaseNode(btreePtr, &right);
M_ExitOnError(err);
}
return noErr;
ErrorExit:
(void) ReleaseNode(btreePtr, &left);
(void) ReleaseNode(btreePtr, &node);
(void) ReleaseNode(btreePtr, &right);
if (iterator != nil)
{
iterator->hint.writeCount = 0;
iterator->hint.nodeNum = 0;
iterator->hint.index = 0;
iterator->version = 0;
iterator->key.length16 = 0;
}
if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
err = fsBTRecordNotFoundErr;
return err;
}
OSStatus BTInsertRecord (FCB *filePtr,
BTreeIterator *iterator,
FSBufferDescriptor *record,
UInt16 recordLen )
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
TreePathTable treePathTable;
SInt32 nodesNeeded;
BlockDescriptor nodeRec;
UInt32 insertNodeNum;
UInt16 index;
Boolean recordFit;
nodeRec.buffer = nil; nodeRec.blockHeader = nil;
err = CheckInsertParams (filePtr, iterator, record, recordLen);
if (err != noErr)
return err;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
switch (err) {
case noErr: err = fsBTDuplicateRecordErr;
goto ErrorExit;
case fsBTRecordNotFoundErr: break;
case fsBTEmptyErr:
if (BTAvailableNodes(btreePtr) == 0)
{
err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
M_ExitOnError (err);
}
err = AllocateNode (btreePtr, &insertNodeNum);
M_ExitOnError (err);
err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
M_ExitOnError (err);
ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
((NodeDescPtr)nodeRec.buffer)->height = 1;
recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0,
&iterator->key, KeyLength(btreePtr, &iterator->key),
record->bufferAddress, recordLen );
if (recordFit != true)
{
err = fsBTRecordTooLargeErr;
goto ErrorExit;
}
err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
M_ExitOnError (err);
btreePtr->treeDepth = 1;
btreePtr->rootNode = insertNodeNum;
btreePtr->firstLeafNode = insertNodeNum;
btreePtr->lastLeafNode = insertNodeNum;
M_BTreeHeaderDirty (btreePtr);
goto Success;
default: goto ErrorExit;
}
if (index > 0)
{
ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
&iterator->key, KeyLength(btreePtr, &iterator->key),
record->bufferAddress, recordLen);
if (recordFit == true)
{
err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
M_ExitOnError (err);
goto Success;
}
}
nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
if (nodesNeeded > 0)
{
nodesNeeded += (SInt32)btreePtr->totalNodes;
if (nodesNeeded > CalcMapBits (btreePtr)) ++nodesNeeded;
err = ExtendBTree (btreePtr, nodesNeeded);
M_ExitOnError (err);
}
err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
recordLen, &nodeRec, index, 1, kInsertRecord, &insertNodeNum);
M_ExitOnError (err);
Success:
++btreePtr->writeCount;
++btreePtr->leafRecords;
M_BTreeHeaderDirty (btreePtr);
iterator->hint.writeCount = btreePtr->writeCount;
iterator->hint.nodeNum = insertNodeNum;
iterator->hint.index = 0; iterator->hint.reserved1 = 0;
iterator->hint.reserved2 = 0;
return noErr;
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;
if (err == fsBTEmptyErr)
err = fsBTRecordNotFoundErr;
return err;
}
OSStatus BTReplaceRecord (FCB *filePtr,
BTreeIterator *iterator,
FSBufferDescriptor *record,
UInt16 recordLen )
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
TreePathTable treePathTable;
SInt32 nodesNeeded;
BlockDescriptor nodeRec;
UInt32 insertNodeNum;
UInt16 index;
Boolean recordFit;
Boolean validHint;
nodeRec.buffer = nil; nodeRec.blockHeader = nil;
err = CheckInsertParams (filePtr, iterator, record, recordLen);
if (err != noErr)
return err;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
err = IsItAHint (btreePtr, iterator, &validHint);
M_ExitOnError (err);
if (validHint)
{
insertNodeNum = iterator->hint.nodeNum;
err = GetNode (btreePtr, insertNodeNum, &nodeRec);
if( err == noErr )
{
ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
M_ExitOnError (err);
if (recordFit)
{
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 );
}
}
err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
M_ExitOnError (err);
ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
M_ExitOnError (err);
if (recordFit)
{
err = UpdateNode (btreePtr, &nodeRec, 0, 0);
M_ExitOnError (err);
goto Success;
}
nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
if (nodesNeeded > 0)
{
nodesNeeded += (SInt32)btreePtr->totalNodes;
if (nodesNeeded > CalcMapBits (btreePtr)) ++nodesNeeded;
err = ExtendBTree (btreePtr, nodesNeeded);
M_ExitOnError (err);
}
ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
DeleteRecord (btreePtr, nodeRec.buffer, index);
err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
recordLen, &nodeRec, index, 1, kReplaceRecord, &insertNodeNum);
M_ExitOnError (err);
++btreePtr->writeCount;
Success:
iterator->hint.writeCount = btreePtr->writeCount;
iterator->hint.nodeNum = insertNodeNum;
iterator->hint.index = 0; iterator->hint.reserved1 = 0;
iterator->hint.reserved2 = 0;
return noErr;
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;
}
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;
nodeRec.buffer = nil; nodeRec.blockHeader = nil;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
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);
ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
err = callBackProc(keyPtr, recordPtr, recordLen, 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 );
}
}
err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
M_ExitOnError (err);
err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
M_ExitOnError (err);
ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
err = callBackProc(keyPtr, recordPtr, recordLen, callBackState);
M_ExitOnError (err);
err = UpdateNode (btreePtr, &nodeRec, 0, 0);
M_ExitOnError (err);
Success:
iterator->hint.writeCount = btreePtr->writeCount;
iterator->hint.nodeNum = insertNodeNum;
iterator->hint.index = 0;
iterator->hint.reserved1 = 0;
iterator->hint.reserved2 = 0;
return noErr;
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;
}
OSStatus BTDeleteRecord (FCB *filePtr,
BTreeIterator *iterator )
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
TreePathTable treePathTable;
BlockDescriptor nodeRec;
SInt32 nodesNeeded;
UInt32 nodeNum;
UInt16 index;
nodeRec.buffer = nil; nodeRec.blockHeader = nil;
M_ReturnErrorIf (filePtr == nil, paramErr);
M_ReturnErrorIf (iterator == nil, paramErr);
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
if (btreePtr == nil)
{
err = fsBTInvalidFileErr;
goto ErrorExit;
}
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
err = SearchTree (btreePtr, &iterator->key, treePathTable, &nodeNum, &nodeRec, &index);
M_ExitOnError (err);
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);
}
err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
M_ExitOnError (err);
++btreePtr->writeCount;
--btreePtr->leafRecords;
M_BTreeHeaderDirty (btreePtr);
iterator->hint.nodeNum = 0;
return noErr;
ErrorExit:
(void) ReleaseNode (btreePtr, &nodeRec);
return err;
}
OSStatus BTGetInformation (FCB *filePtr,
UInt16 version,
BTreeInfoRec *info )
{
#pragma unused (version)
BTreeControlBlockPtr btreePtr;
M_ReturnErrorIf (filePtr == nil, paramErr);
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
M_ReturnErrorIf (info == nil, paramErr);
info->nodeSize = btreePtr->nodeSize;
info->maxKeyLength = btreePtr->maxKeyLength;
info->treeDepth = btreePtr->treeDepth;
info->numRecords = btreePtr->leafRecords;
info->numNodes = btreePtr->totalNodes;
info->numFreeNodes = btreePtr->freeNodes;
info->lastfsync = btreePtr->lastfsync;
info->keyCompareType = btreePtr->keyCompareType;
return noErr;
}
__private_extern__
OSStatus
BTIsDirty(FCB *filePtr)
{
BTreeControlBlockPtr btreePtr;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
return TreeIsDirty(btreePtr);
}
OSStatus BTFlushPath (FCB *filePtr)
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
M_ReturnErrorIf (filePtr == nil, paramErr);
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
err = UpdateHeader (btreePtr, false);
return err;
}
OSStatus
BTReloadData(FCB *filePtr)
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
BlockDescriptor node;
BTHeaderRec *header;
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 != noErr)
return (err);
header = (BTHeaderRec*)((char *)node.buffer + sizeof(BTNodeDescriptor));
if ((err = VerifyHeader (filePtr, header)) == 0) {
btreePtr->treeDepth = header->treeDepth;
btreePtr->rootNode = header->rootNode;
btreePtr->leafRecords = header->leafRecords;
btreePtr->firstLeafNode = header->firstLeafNode;
btreePtr->lastLeafNode = header->lastLeafNode;
btreePtr->maxKeyLength = header->maxKeyLength;
btreePtr->totalNodes = header->totalNodes;
btreePtr->freeNodes = header->freeNodes;
btreePtr->btreeType = header->btreeType;
btreePtr->flags &= (~kBTHeaderDirty);
}
(void) ReleaseNode(btreePtr, &node);
return err;
}
OSStatus BTInvalidateHint (BTreeIterator *iterator )
{
if (iterator == nil)
return paramErr;
iterator->hint.nodeNum = 0;
return noErr;
}
OSStatus BTGetLastSync (FCB *filePtr,
UInt32 *lastsync)
{
BTreeControlBlockPtr btreePtr;
M_ReturnErrorIf (filePtr == nil, paramErr);
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
M_ReturnErrorIf (lastsync == nil, paramErr);
*lastsync = btreePtr->lastfsync;
return noErr;
}
OSStatus BTSetLastSync (FCB *filePtr,
UInt32 lastsync)
{
BTreeControlBlockPtr btreePtr;
M_ReturnErrorIf (filePtr == nil, paramErr);
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
M_ReturnErrorIf (lastsync == nil, paramErr);
btreePtr->lastfsync = lastsync;
return noErr;
}
__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);
}
__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);
}
__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);
}