extern char debug;
#include "BTree.h"
#include "BTreePrivate.h"
extern Boolean NodesAreContiguous(SFCB *fcb, UInt32 nodeSize);
extern void fplog(FILE *stream, const char *fmt, ...);
static void CopyKey(BTreeControlBlockPtr btcb, const BTreeKey *srcKey, BTreeKey *destKey)
{
unsigned keySize = CalcKeySize(btcb, srcKey);
unsigned maxKeySize = MaxKeySize(btcb);
int fixLength = 0;
if (keySize > maxKeySize)
{
keySize = maxKeySize;
fixLength = 1;
}
CopyMemory(srcKey, destKey, keySize);
if (fixLength)
{
if (btcb->attributes & kBTBigKeysMask)
destKey->length16 = btcb->maxKeyLength;
else
destKey->length8 = btcb->maxKeyLength;
}
}
OSStatus InitBTreeModule(void)
{
return noErr;
}
#if 0
OSStatus BTInitialize (FCB *filePtr,
UInt16 maxKeyLength,
UInt16 nodeSize,
UInt8 btreeType,
KeyDescriptorPtr keyDescPtr )
{
OSStatus err;
FSForkControlBlockPtr forkPtr;
BTreeControlBlockPtr btreePtr;
BlockDescriptor headerNode;
HeaderPtr header;
Ptr pos;
FSSize minEOF, maxEOF;
SetEndOfForkProcPtr setEndOfForkProc;
SetBlockSizeProcPtr setBlockSizeProc;
headerNode.buffer = nil;
if (pathPtr == nil) return paramErr;
setEndOfForkProc = pathPtr->agentPtr->agent.setEndOfForkProc;
setBlockSizeProc = pathPtr->agentPtr->agent.setBlockSizeProc;
if (pathPtr->agentPtr->agent.getBlockProc == nil) return E_NoGetBlockProc;
if (pathPtr->agentPtr->agent.releaseBlockProc == nil) return E_NoReleaseBlockProc;
if (setEndOfForkProc == nil) return E_NoSetEndOfForkProc;
if (setBlockSizeProc == nil) return E_NoSetBlockSizeProc;
forkPtr = pathPtr->path.forkPtr;
if (forkPtr->fork.btreePtr != nil) return fsBTrFileAlreadyOpenErr;
if ((maxKeyLength == 0) ||
(maxKeyLength > kMaxKeyLength)) return fsBTInvalidKeyLengthErr;
if ( M_IsEven (maxKeyLength)) ++maxKeyLength;
switch (nodeSize) {
case 512:
case 1024:
case 2048:
case 4096:
case 8192:
case 16384:
case 32768: break;
default: return E_BadNodeType;
}
switch (btreeType)
{
case kHFSBTreeType:
case kUserBTreeType:
case kReservedBTreeType: break;
default: return fsBTUnknownVersionErr; }
M_RESIDENT_ALLOCATE_FIXED_CLEAR( &btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType );
if (btreePtr == nil)
{
err = memFullErr;
goto ErrorExit;
}
btreePtr->version = kBTreeVersion; btreePtr->reserved1 = 0;
btreePtr->flags = 0;
btreePtr->attributes = 0;
btreePtr->forkPtr = forkPtr;
btreePtr->keyCompareProc = nil;
btreePtr->keyDescPtr = keyDescPtr;
btreePtr->btreeType = btreeType;
btreePtr->treeDepth = 0;
btreePtr->rootNode = 0;
btreePtr->leafRecords = 0;
btreePtr->firstLeafNode = 0;
btreePtr->lastLeafNode = 0;
btreePtr->nodeSize = nodeSize;
btreePtr->maxKeyLength = maxKeyLength;
btreePtr->totalNodes = 1; btreePtr->freeNodes = 0;
btreePtr->writeCount = 1;
err = setBlockSizeProc (forkPtr, nodeSize);
M_ExitOnError (err);
minEOF = nodeSize;
if ( forkPtr->fork.logicalEOF < minEOF )
{
maxEOF 0xFFFFFFFFL;
err = setEndOfForkProc (forkPtr, minEOF, maxEOF);
M_ExitOnError (err);
};
err = GetNewNode (btreePtr, kHeaderNodeNum, &headerNode);
M_ExitOnError (err);
header = headerNode.buffer;
header->node.type = kHeaderNode;
header->node.numRecords = 3;
header->nodeSize = nodeSize;
header->maxKeyLength = maxKeyLength;
header->btreeType = btreeType;
header->totalNodes = btreePtr->totalNodes;
header->freeNodes = btreePtr->totalNodes - 1;
pos = ((Ptr)headerNode.buffer) + kHeaderMapRecOffset;
*pos = 0x80;
pos = ((Ptr)headerNode.buffer) + nodeSize;
pos -= 2; *((UInt16 *)pos) = kHeaderRecOffset;
pos -= 2; *((UInt16 *)pos) = kKeyDescRecOffset;
pos -= 2; *((UInt16 *)pos) = kHeaderMapRecOffset;
pos -= 2; *((UInt16 *)pos) = nodeSize - 8;
#if SupportsKeyDescriptors
if (keyDescPtr != nil)
{
err = CheckKeyDescriptor (keyDescPtr, maxKeyLength);
M_ExitOnError (err);
pos = ((Ptr)headerNode.buffer) + kKeyDescRecOffset;
CopyMemory (keyDescPtr, pos, keyDescPtr->length + 1);
}
#endif
err = UpdateNode (btreePtr, &headerNode);
M_ExitOnError (err);
err = ExtendBTree (btreePtr, forkPtr->fork.logicalEOF.lo / nodeSize); M_ExitOnError (err);
err = UpdateHeader (btreePtr);
M_ExitOnError (err);
pathPtr->path.forkPtr->fork.btreePtr = nil;
M_RESIDENT_DEALLOCATE_FIXED( btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType );
return noErr;
ErrorExit:
(void) ReleaseNode (btreePtr, &headerNode);
if (btreePtr != nil)
M_RESIDENT_DEALLOCATE_FIXED( btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType );
return err;
}
#endif
OSStatus BTOpenPath (SFCB *filePtr,
KeyCompareProcPtr keyCompareProc,
GetBlockProcPtr getBlockProc,
ReleaseBlockProcPtr releaseBlockProc,
SetEndOfForkProcPtr setEndOfForkProc,
SetBlockSizeProcPtr setBlockSizeProc )
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
BTHeaderRec *header;
NodeRec nodeRec;
if ( filePtr == nil ||
getBlockProc == nil ||
releaseBlockProc == nil ||
setEndOfForkProc == nil ||
setBlockSizeProc == nil )
{
return paramErr;
}
if ( filePtr->fcbBtree != nil ) return noErr;
if ( filePtr->fcbLogicalSize < kMinNodeSize )
return fsBTInvalidFileErr;
btreePtr = (BTreeControlBlock*) AllocateClearMemory( sizeof( BTreeControlBlock ) );
if (btreePtr == nil)
{
Panic ("\pBTOpen: no memory for btreePtr.");
return memFullErr;
}
btreePtr->getBlockProc = getBlockProc;
btreePtr->releaseBlockProc = releaseBlockProc;
btreePtr->setEndOfForkProc = setEndOfForkProc;
btreePtr->keyCompareProc = keyCompareProc;
nodeRec.buffer = nil;
btreePtr->fcbPtr = filePtr;
filePtr->fcbBtree = (void *) btreePtr;
err = setBlockSizeProc (btreePtr->fcbPtr, kMinNodeSize);
M_ExitOnError (err);
err = getBlockProc (btreePtr->fcbPtr,
kHeaderNodeNum,
kGetBlock,
&nodeRec );
PanicIf (err != noErr, "\pBTOpen: getNodeProc returned error getting header node.");
M_ExitOnError (err);
header = (BTHeaderRec*) (nodeRec.buffer + sizeof(BTNodeDescriptor));
err = VerifyHeader (filePtr, header);
M_ExitOnError (err);
PanicIf ( (filePtr->fcbVolume->vcbSignature != 0x4244) && (btreePtr->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;
btreePtr->btreeType = header->btreeType;
btreePtr->attributes = header->attributes;
if ( btreePtr->maxKeyLength > 40 )
btreePtr->attributes |= (kBTBigKeysMask + kBTVariableIndexKeysMask);
btreePtr->version = kBTreeVersion;
btreePtr->flags = 0;
btreePtr->writeCount = 1;
btreePtr->numGetNodes = 1;
if ( btreePtr->nodeSize != kMinNodeSize )
{
err = setBlockSizeProc (btreePtr->fcbPtr, btreePtr->nodeSize);
M_ExitOnError (err);
#if BSD
err = releaseBlockProc(btreePtr->fcbPtr, &nodeRec, kTrashBlock);
#else
err = ReleaseNode (btreePtr, &nodeRec);
#endif
err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec ); M_ExitOnError (err);
}
#if SupportsKeyDescriptors
if ( keyCompareProc == nil ) {
err = GetKeyDescriptor (btreePtr, nodeRec.buffer); M_ExitOnError (err);
err = CheckKeyDescriptor (btreePtr->keyDescPtr, btreePtr->maxKeyLength);
M_ExitOnError (err);
}
else
#endif
{
btreePtr->keyDescPtr = nil; }
err = ReleaseNode (btreePtr, &nodeRec);
M_ExitOnError (err);
#if BSD
if ( !NodesAreContiguous(filePtr, btreePtr->nodeSize) ) {
if (debug) fplog(stderr, "Nodes are not contiguous -- this is fatal\n");
return fsBTInvalidNodeErr;
}
#endif
return noErr;
ErrorExit:
filePtr->fcbBtree = nil;
(void) ReleaseNode (btreePtr, &nodeRec);
DisposeMemory( btreePtr );
return err;
}
OSStatus BTClosePath (SFCB *filePtr)
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
#if 0
FSPathControlBlockPtr tempPath;
Boolean otherBTreePathsOpen;
#endif
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
if (btreePtr == nil)
return fsBTInvalidFileErr;
#if 0
otherBTreePathsOpen = false;
tempPath = forkPtr->fork.pathList.head;
while ( (tempPath != (FSPathControlBlockPtr) &forkPtr->fork.pathList) &&
(otherBTreePathsOpen == false) )
{
if ((tempPath != pathPtr) && (tempPath->path.pathType == kBTreeType))
{
otherBTreePathsOpen = true;
break; }
tempPath = tempPath->next;
}
if (otherBTreePathsOpen == true)
{
err = UpdateHeader (btreePtr); return err; }
#endif
btreePtr->attributes &= ~kBTBadCloseMask; err = UpdateHeader (btreePtr);
M_ExitOnError (err);
#if SupportsKeyDescriptors
if (btreePtr->keyDescPtr != nil) {
DisposeMemory( btreePtr->keyDescPtr );
}
#endif
DisposeMemory( btreePtr );
filePtr->fcbBtree = nil;
return noErr;
ErrorExit:
return err;
}
OSStatus BTSearchRecord (SFCB *filePtr,
BTreeIterator *searchIterator,
UInt32 heuristicHint,
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;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
if (btreePtr == nil) return fsBTInvalidFileErr;
#if SupportsKeyDescriptors
if (btreePtr->keyCompareProc == nil) {
err = CheckKey (&searchIterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
M_ExitOnError (err);
}
#endif
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) && (heuristicHint != kInvalidMRUCacheKey) && (nodeNum != heuristicHint) )
{
nodeNum = heuristicHint;
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);
}
}
}
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;
PanicIf(len > recordSize, "\pBTSearchRecord: truncating record!");
if (len > recordSize) len = recordSize;
CopyMemory (recordPtr, record->bufferAddress, len);
}
}
if (resultIterator != nil)
{
resultIterator->hint.writeCount = btreePtr->writeCount;
resultIterator->hint.nodeNum = nodeNum;
resultIterator->hint.index = index;
resultIterator->hint.reserved1 = 0;
resultIterator->hint.reserved2 = 0;
resultIterator->version = 0;
resultIterator->reserved = 0;
if (foundRecord == true)
CopyKey(btreePtr, keyPtr, &resultIterator->key);
else
CopyKey(btreePtr, &searchIterator->key, &resultIterator->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 (SFCB *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;
right.buffer = nil;
node.buffer = nil;
if (filePtr == nil)
{
return paramErr;
}
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
if (btreePtr == nil)
{
return fsBTInvalidFileErr; }
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);
if (debug) fprintf(stderr, "%s(%d): returning fsBTInvalidNodeErr\n", __FUNCTION__, __LINE__);
err = fsBTInvalidNodeErr;
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;
PanicIf(len > recordSize, "\pBTIterateRecord: truncating record!");
if (len > recordSize) len = recordSize;
CopyMemory (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;
CopyKey(btreePtr, keyPtr, &iterator->key);
}
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 BTInsertRecord (SFCB *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;
err = CheckInsertParams (filePtr, iterator, record, recordLen);
if (err != noErr)
return err;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
switch (err) {
case noErr: err = fsBTDuplicateRecordErr;
goto ErrorExit;
case fsBTRecordNotFoundErr: break;
case fsBTEmptyErr:
if (btreePtr->freeNodes == 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);
((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);
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)
{
recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
&iterator->key, KeyLength(btreePtr, &iterator->key),
record->bufferAddress, recordLen);
if (recordFit == true)
{
err = UpdateNode (btreePtr, &nodeRec);
M_ExitOnError (err);
goto Success;
}
}
nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; if (nodesNeeded > 0)
{
nodesNeeded += 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;
}
#if 0
OSStatus BTSetRecord (SFCB *filePtr,
BTreeIterator *iterator,
FSBufferDescriptor *record,
UInt16 recordLen )
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
TreePathTable treePathTable;
SInt32 nodesNeeded;
BlockDescriptor nodeRec;
UInt32 insertNodeNum;
UInt16 index;
Boolean recordFound = false;
Boolean recordFit;
Boolean operation;
Boolean validHint;
nodeRec.buffer = nil;
err = CheckInsertParams (filePtr, iterator, record, recordLen);
if (err != noErr)
return err;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
err = IsItAHint (btreePtr, iterator, &validHint);
M_ExitOnError (err);
if (validHint)
{
insertNodeNum = iterator->hint.nodeNum;
err = GetNode (btreePtr, insertNodeNum, &nodeRec);
if( err == noErr )
{
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
M_ExitOnError (err);
if (recordFit)
{
err = UpdateNode (btreePtr, &nodeRec);
M_ExitOnError (err);
recordFound = true;
++btreePtr->numValidHints;
goto Success;
} else
{
(void) BTInvalidateHint( iterator );
}
err = ReleaseNode (btreePtr, &nodeRec);
M_ExitOnError (err);
}
}
err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
switch (err) {
case noErr: recordFound = true;
break;
case fsBTRecordNotFoundErr: break;
case fsBTEmptyErr:
if (btreePtr->freeNodes == 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);
((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);
M_ExitOnError (err);
btreePtr->rootNode = insertNodeNum;
btreePtr->treeDepth = 1;
btreePtr->flags |= kBTHeaderDirty;
goto Success;
default: goto ErrorExit;
}
if (recordFound == true) {
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
M_ExitOnError (err);
if (recordFit)
{
err = UpdateNode (btreePtr, &nodeRec);
M_ExitOnError (err);
goto Success;
}
}
nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; if (nodesNeeded > 0)
{
nodesNeeded += btreePtr->totalNodes;
if (nodesNeeded > CalcMapBits (btreePtr)) ++nodesNeeded;
err = ExtendBTree (btreePtr, nodesNeeded);
M_ExitOnError (err);
}
if (recordFound == true) {
DeleteRecord (btreePtr, nodeRec.buffer, index);
operation = kReplaceRecord;
} else {
operation = kInsertRecord;
}
err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
recordLen, &nodeRec, index, 1, operation, &insertNodeNum);
M_ExitOnError (err);
++btreePtr->writeCount;
Success:
if (recordFound == false)
{
++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;
return err;
}
#endif
OSStatus BTReplaceRecord (SFCB *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;
err = CheckInsertParams (filePtr, iterator, record, recordLen);
if (err != noErr)
return err;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
err = IsItAHint (btreePtr, iterator, &validHint);
M_ExitOnError (err);
if (validHint)
{
insertNodeNum = iterator->hint.nodeNum;
err = GetNode (btreePtr, insertNodeNum, &nodeRec);
if( err == noErr )
{
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
M_ExitOnError (err);
if (recordFit)
{
err = UpdateNode (btreePtr, &nodeRec);
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 = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
M_ExitOnError (err);
if (recordFit)
{
err = UpdateNode (btreePtr, &nodeRec);
M_ExitOnError (err);
goto Success;
}
nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; if (nodesNeeded > 0)
{
nodesNeeded += btreePtr->totalNodes;
if (nodesNeeded > CalcMapBits (btreePtr)) ++nodesNeeded;
err = ExtendBTree (btreePtr, nodesNeeded);
M_ExitOnError (err);
}
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 BTDeleteRecord (SFCB *filePtr,
BTreeIterator *iterator )
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
TreePathTable treePathTable;
BlockDescriptor nodeRec;
UInt32 nodeNum;
UInt16 index;
nodeRec.buffer = nil;
M_ReturnErrorIf (filePtr == nil, paramErr);
M_ReturnErrorIf (iterator == nil, paramErr);
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
if (btreePtr == nil)
{
err = fsBTInvalidFileErr;
goto ErrorExit;
}
#if SupportsKeyDescriptors
if (btreePtr->keyDescPtr != nil)
{
err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
M_ExitOnError (err);
}
#endif
err = SearchTree (btreePtr, &iterator->key, treePathTable, &nodeNum, &nodeRec, &index);
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 (SFCB *filePtr,
UInt16 version,
BTreeInfoRec *info )
{
#pragma unused (version)
BTreeControlBlockPtr btreePtr;
M_ReturnErrorIf (filePtr == nil, paramErr);
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
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->keyDescriptor = btreePtr->keyDescPtr; info->reserved = 0;
if (btreePtr->keyDescPtr == nil)
info->keyDescLength = 0;
else
info->keyDescLength = (UInt32) btreePtr->keyDescPtr->length;
return noErr;
}
OSStatus BTFlushPath (SFCB *filePtr)
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
M_ReturnErrorIf (filePtr == nil, paramErr);
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
err = UpdateHeader (btreePtr);
return err;
}
OSStatus BTInvalidateHint (BTreeIterator *iterator )
{
if (iterator == nil)
return paramErr;
iterator->hint.nodeNum = 0;
return noErr;
}