2
* Copyright (c) 1999, 2005 Apple Computer, Inc. All rights reserved.
4
* @APPLE_LICENSE_HEADER_START@
6
* "Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7
* Reserved. This file contains Original Code and/or Modifications of
8
* Original Code as defined in and that are subject to the Apple Public
9
* Source License Version 1.0 (the 'License'). You may not use this file
10
* except in compliance with the License. Please obtain a copy of the
11
* License at http://www.apple.com/publicsource and read it before using
14
* The Original Code and all software distributed under the License are
15
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18
* FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19
* License for the specific language governing rights and limitations
22
* @APPLE_LICENSE_HEADER_END@
27
Contains: Implementation of public interface routines for B-tree manager.
31
Written by: Gordon Sheridan and Bill Bruffey
33
Copyright: � 1992-1999 by Apple Computer, Inc., all rights reserved.
38
#include "BTreePrivate.h"
39
//#include "HFSInstrumentation.h"
42
extern Boolean NodesAreContiguous(SFCB *fcb, UInt32 nodeSize);
44
/*-------------------------------------------------------------------------------
47
Function: Copy a BTree key. Sanity check the key length; if it is too large,
48
then set the copy's length to the BTree's maximum key length.
50
Inputs: btcb BTree whose key is being copied
51
srcKey Source key being copied
53
Output: destKey Destination where copy will be stored
56
-------------------------------------------------------------------------------*/
57
static void CopyKey(BTreeControlBlockPtr btcb, const BTreeKey *srcKey, BTreeKey *destKey)
59
unsigned keySize = CalcKeySize(btcb, srcKey);
60
unsigned maxKeySize = MaxKeySize(btcb);
64
* If the key length is too long (corrupted), then constrain the number
65
* of bytes to copy. Remember that we did this so we can also update
66
* the copy's length field later.
68
if (keySize > maxKeySize)
74
CopyMemory(srcKey, destKey, keySize);
77
* If we had to constrain the key size above, then also update the
78
* key length in the copy. This will prevent the caller from dereferencing
79
* part of the key which we never actually copied.
83
if (btcb->attributes & kBTBigKeysMask)
84
destKey->length16 = btcb->maxKeyLength;
86
destKey->length8 = btcb->maxKeyLength;
91
//////////////////////////////////// Globals ////////////////////////////////////
94
/////////////////////////// BTree Module Entry Points ///////////////////////////
97
/*-------------------------------------------------------------------------------
98
Routine: InitBTreeModule - Initialize BTree Module Global(s).
100
Function: Initialize BTree code, if necessary
106
Result: noErr - success
107
!= noErr - can't happen
108
-------------------------------------------------------------------------------*/
110
OSStatus InitBTreeModule(void)
116
/*-------------------------------------------------------------------------------
117
Routine: BTInitialize - Initialize a fork for access as a B*Tree.
119
Function: Write Header node and create any map nodes necessary to map the fork
120
as a B*Tree. If the fork is not large enough for the header node, the
121
FS Agent is called to extend the LEOF. Additional map nodes will be
122
allocated if necessary to represent the size of the fork. This allows
123
the FS Agent to specify the initial size of B*Tree files.
126
Input: pathPtr - pointer to path control block
127
maxKeyLength - maximum length that will be used for any key in this B*Tree
128
nodeSize - node size for B*Tree (must be 2^n, 9 >= n >= 15)
129
btreeType - type of B*Tree
130
keyDescPtr - pointer to key descriptor (optional if key compare proc is used)
134
Result: noErr - success
135
paramErr - mandatory parameter was missing
136
E_NoGetBlockProc - FS Agent CB has no GetNodeProcPtr
137
E_NoReleaseBlockProc - FS Agent CB has no ReleaseNodeProcPtr
138
E_NoSetEndOfForkProc - FS Agent CB has no SetEndOfForkProcPtr
139
E_NoSetBlockSizeProc - FS Agent CB has no SetBlockSizeProcPtr
140
fsBTrFileAlreadyOpenErr - fork is already open as a B*Tree
141
fsBTInvalidKeyLengthErr - maximum key length is out of range
142
E_BadNodeType - node size is an illegal value
143
fsBTUnknownVersionErr - the B*Tree type is unknown by this module
144
memFullErr - not enough memory to initialize B*Tree
146
-------------------------------------------------------------------------------*/
148
OSStatus BTInitialize (FCB *filePtr,
152
KeyDescriptorPtr keyDescPtr )
155
FSForkControlBlockPtr forkPtr;
156
BTreeControlBlockPtr btreePtr;
157
BlockDescriptor headerNode;
160
FSSize minEOF, maxEOF;
161
SetEndOfForkProcPtr setEndOfForkProc;
162
SetBlockSizeProcPtr setBlockSizeProc;
164
////////////////////// Preliminary Error Checking ///////////////////////////
166
headerNode.buffer = nil;
168
if (pathPtr == nil) return paramErr;
170
setEndOfForkProc = pathPtr->agentPtr->agent.setEndOfForkProc;
171
setBlockSizeProc = pathPtr->agentPtr->agent.setBlockSizeProc;
173
if (pathPtr->agentPtr->agent.getBlockProc == nil) return E_NoGetBlockProc;
174
if (pathPtr->agentPtr->agent.releaseBlockProc == nil) return E_NoReleaseBlockProc;
175
if (setEndOfForkProc == nil) return E_NoSetEndOfForkProc;
176
if (setBlockSizeProc == nil) return E_NoSetBlockSizeProc;
178
forkPtr = pathPtr->path.forkPtr;
180
if (forkPtr->fork.btreePtr != nil) return fsBTrFileAlreadyOpenErr;
182
if ((maxKeyLength == 0) ||
183
(maxKeyLength > kMaxKeyLength)) return fsBTInvalidKeyLengthErr;
185
if ( M_IsEven (maxKeyLength)) ++maxKeyLength; // len byte + even bytes + pad byte
187
switch (nodeSize) // node size == 512*2^n
196
default: return E_BadNodeType;
203
case kReservedBTreeType: break;
205
default: return fsBTUnknownVersionErr; //�� right?
209
//////////////////////// Allocate Control Block /////////////////////////////
211
M_RESIDENT_ALLOCATE_FIXED_CLEAR( &btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType );
218
btreePtr->version = kBTreeVersion; //�� what is the version?
219
btreePtr->reserved1 = 0;
221
btreePtr->attributes = 0;
222
btreePtr->forkPtr = forkPtr;
223
btreePtr->keyCompareProc = nil;
224
btreePtr->keyDescPtr = keyDescPtr;
225
btreePtr->btreeType = btreeType;
226
btreePtr->treeDepth = 0;
227
btreePtr->rootNode = 0;
228
btreePtr->leafRecords = 0;
229
btreePtr->firstLeafNode = 0;
230
btreePtr->lastLeafNode = 0;
231
btreePtr->nodeSize = nodeSize;
232
btreePtr->maxKeyLength = maxKeyLength;
233
btreePtr->totalNodes = 1; // so ExtendBTree adds maps nodes properly
234
btreePtr->freeNodes = 0;
235
btreePtr->writeCount = 1; // <CS10>, for BTree scanner
237
// set block size = nodeSize
238
err = setBlockSizeProc (forkPtr, nodeSize);
241
////////////////////////////// Check LEOF ///////////////////////////////////
244
if ( forkPtr->fork.logicalEOF < minEOF )
246
// allocate more space if necessary
249
err = setEndOfForkProc (forkPtr, minEOF, maxEOF);
254
//////////////////////// Initialize Header Node /////////////////////////////
256
err = GetNewNode (btreePtr, kHeaderNodeNum, &headerNode);
259
header = headerNode.buffer;
261
header->node.type = kHeaderNode;
262
header->node.numRecords = 3; // header rec, key desc, map rec
264
header->nodeSize = nodeSize;
265
header->maxKeyLength = maxKeyLength;
266
header->btreeType = btreeType;
267
header->totalNodes = btreePtr->totalNodes;
268
header->freeNodes = btreePtr->totalNodes - 1;
269
// ignore header->clumpSize; //�� rename this field?
271
// mark header node allocated in map record
272
pos = ((Ptr)headerNode.buffer) + kHeaderMapRecOffset;
275
// set node offsets ( nodeSize-8, F8, 78, 0E)
276
pos = ((Ptr)headerNode.buffer) + nodeSize;
277
pos -= 2; *((UInt16 *)pos) = kHeaderRecOffset;
278
pos -= 2; *((UInt16 *)pos) = kKeyDescRecOffset;
279
pos -= 2; *((UInt16 *)pos) = kHeaderMapRecOffset;
280
pos -= 2; *((UInt16 *)pos) = nodeSize - 8;
283
///////////////////// Copy Key Descriptor To Header /////////////////////////
284
#if SupportsKeyDescriptors
285
if (keyDescPtr != nil)
287
err = CheckKeyDescriptor (keyDescPtr, maxKeyLength);
290
// copy to header node
291
pos = ((Ptr)headerNode.buffer) + kKeyDescRecOffset;
292
CopyMemory (keyDescPtr, pos, keyDescPtr->length + 1);
297
err = UpdateNode (btreePtr, &headerNode);
301
////////////////////////// Allocate Map Nodes ///////////////////////////////
303
err = ExtendBTree (btreePtr, forkPtr->fork.logicalEOF.lo / nodeSize); // sets totalNodes
307
////////////////////////////// Close BTree //////////////////////////////////
309
err = UpdateHeader (btreePtr);
312
pathPtr->path.forkPtr->fork.btreePtr = nil;
313
M_RESIDENT_DEALLOCATE_FIXED( btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType );
318
/////////////////////// Error - Clean up and Exit ///////////////////////////
322
(void) ReleaseNode (btreePtr, &headerNode);
324
M_RESIDENT_DEALLOCATE_FIXED( btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType );
331
/*-------------------------------------------------------------------------------
332
Routine: BTOpenPath - Open a file for access as a B*Tree.
334
Function: Create BTree control block for a file, if necessary. Validates the
335
file to be sure it looks like a BTree file.
338
Input: filePtr - pointer to file to open as a B-tree
339
keyCompareProc - pointer to client's KeyCompare function
340
getBlockProc - pointer to client's GetBlock function
341
releaseBlockProc - pointer to client's ReleaseBlock function
342
setEndOfForkProc - pointer to client's SetEOF function
344
Result: noErr - success
345
paramErr - required ptr was nil
349
-------------------------------------------------------------------------------*/
351
OSStatus BTOpenPath (SFCB *filePtr,
352
KeyCompareProcPtr keyCompareProc,
353
GetBlockProcPtr getBlockProc,
354
ReleaseBlockProcPtr releaseBlockProc,
355
SetEndOfForkProcPtr setEndOfForkProc,
356
SetBlockSizeProcPtr setBlockSizeProc )
359
BTreeControlBlockPtr btreePtr;
363
// LogStartTime(kTraceOpenBTree);
365
////////////////////// Preliminary Error Checking ///////////////////////////
367
if ( filePtr == nil ||
368
getBlockProc == nil ||
369
releaseBlockProc == nil ||
370
setEndOfForkProc == nil ||
371
setBlockSizeProc == nil )
376
if ( filePtr->fcbBtree != nil ) // already has a BTreeCB
379
// is file large enough to contain header node?
380
if ( filePtr->fcbLogicalSize < kMinNodeSize )
381
return fsBTInvalidFileErr; //�� or E_BadHeader?
384
//////////////////////// Allocate Control Block /////////////////////////////
386
btreePtr = (BTreeControlBlock*) AllocateClearMemory( sizeof( BTreeControlBlock ) );
389
Panic ("\pBTOpen: no memory for btreePtr.");
393
btreePtr->getBlockProc = getBlockProc;
394
btreePtr->releaseBlockProc = releaseBlockProc;
395
btreePtr->setEndOfForkProc = setEndOfForkProc;
396
btreePtr->keyCompareProc = keyCompareProc;
398
/////////////////////////// Read Header Node ////////////////////////////////
400
nodeRec.buffer = nil; // so we can call ReleaseNode
402
btreePtr->fcbPtr = filePtr;
403
filePtr->fcbBtree = (void *) btreePtr; // attach btree cb to file
405
// it is now safe to call M_ExitOnError (err)
407
err = setBlockSizeProc (btreePtr->fcbPtr, kMinNodeSize);
411
err = getBlockProc (btreePtr->fcbPtr,
416
PanicIf (err != noErr, "\pBTOpen: getNodeProc returned error getting header node.");
419
header = (BTHeaderRec*) (nodeRec.buffer + sizeof(BTNodeDescriptor));
422
///////////////////////////// verify header /////////////////////////////////
424
err = VerifyHeader (filePtr, header);
428
///////////////////// Initalize fields from header //////////////////////////
430
PanicIf ( (filePtr->fcbVolume->vcbSignature != 0x4244) && (btreePtr->nodeSize == 512), "\p BTOpenPath: wrong node size for HFS+ volume!");
432
btreePtr->treeDepth = header->treeDepth;
433
btreePtr->rootNode = header->rootNode;
434
btreePtr->leafRecords = header->leafRecords;
435
btreePtr->firstLeafNode = header->firstLeafNode;
436
btreePtr->lastLeafNode = header->lastLeafNode;
437
btreePtr->nodeSize = header->nodeSize;
438
btreePtr->maxKeyLength = header->maxKeyLength;
439
btreePtr->totalNodes = header->totalNodes;
440
btreePtr->freeNodes = header->freeNodes;
441
// ignore header->clumpSize; //�� rename this field?
442
btreePtr->btreeType = header->btreeType;
444
btreePtr->attributes = header->attributes;
446
if ( btreePtr->maxKeyLength > 40 )
447
btreePtr->attributes |= (kBTBigKeysMask + kBTVariableIndexKeysMask); //�� we need a way to save these attributes
449
/////////////////////// Initialize dynamic fields ///////////////////////////
451
btreePtr->version = kBTreeVersion;
453
btreePtr->writeCount = 1; // <CS10>, for BTree scanner
455
btreePtr->numGetNodes = 1; // for earlier call to getNodeProc
457
/////////////////////////// Check Header Node ///////////////////////////////
459
//�� set kBadClose attribute bit, and UpdateNode
462
* If the actual node size is different than the amount we read,
463
* then release and trash this block, and re-read with the correct
466
if ( btreePtr->nodeSize != kMinNodeSize )
468
err = setBlockSizeProc (btreePtr->fcbPtr, btreePtr->nodeSize);
473
* Need to use kTrashBlock option to force the
474
* buffer cache to re-read the entire node
476
err = releaseBlockProc(btreePtr->fcbPtr, &nodeRec, kTrashBlock);
478
err = ReleaseNode (btreePtr, &nodeRec);
481
err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec ); // calls CheckNode...
485
//�� total nodes * node size <= LEOF?
488
////////////////////////// Get Key Descriptor ///////////////////////////////
489
#if SupportsKeyDescriptors
490
if ( keyCompareProc == nil ) // if no key compare proc then get key descriptor
492
err = GetKeyDescriptor (btreePtr, nodeRec.buffer); //�� it should check amount of memory allocated...
495
err = CheckKeyDescriptor (btreePtr->keyDescPtr, btreePtr->maxKeyLength);
502
btreePtr->keyDescPtr = nil; // clear it so we don't dispose garbage later
505
err = ReleaseNode (btreePtr, &nodeRec);
511
* Under Mac OS, b-tree nodes can be non-contiguous on disk when the
512
* allocation block size is smaller than the b-tree node size.
514
if ( !NodesAreContiguous(filePtr, btreePtr->nodeSize) )
515
return fsBTInvalidNodeErr;
518
//////////////////////////////// Success ////////////////////////////////////
520
//�� align LEOF to multiple of node size? - just on close
522
// LogEndTime(kTraceOpenBTree, noErr);
527
/////////////////////// Error - Clean up and Exit ///////////////////////////
531
filePtr->fcbBtree = nil;
532
(void) ReleaseNode (btreePtr, &nodeRec);
533
DisposeMemory( btreePtr );
535
// LogEndTime(kTraceOpenBTree, err);
542
/*-------------------------------------------------------------------------------
543
Routine: BTClosePath - Flush BTree Header and Deallocate Memory for BTree.
545
Function: Flush the BTreeControlBlock fields to header node, and delete BTree control
546
block and key descriptor associated with the file if filePtr is last
547
path of type kBTreeType ('btre').
550
Input: filePtr - pointer to file to delete BTree control block for.
552
Result: noErr - success
555
-------------------------------------------------------------------------------*/
557
OSStatus BTClosePath (SFCB *filePtr)
560
BTreeControlBlockPtr btreePtr;
562
FSPathControlBlockPtr tempPath;
563
Boolean otherBTreePathsOpen;
566
// LogStartTime(kTraceCloseBTree);
568
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
571
return fsBTInvalidFileErr;
573
////////////////////// Check for other BTree Paths //////////////////////////
576
//�� Need replacement field for pathType
577
otherBTreePathsOpen = false;
578
tempPath = forkPtr->fork.pathList.head;
579
while ( (tempPath != (FSPathControlBlockPtr) &forkPtr->fork.pathList) &&
580
(otherBTreePathsOpen == false) )
582
if ((tempPath != pathPtr) && (tempPath->path.pathType == kBTreeType))
584
otherBTreePathsOpen = true;
585
break; // done with loop check
588
tempPath = tempPath->next;
591
////////////////////////// Update Header Node ///////////////////////////////
594
if (otherBTreePathsOpen == true)
596
err = UpdateHeader (btreePtr); // update header even if we aren't closing
597
return err; // we only clean up after the last user...
601
btreePtr->attributes &= ~kBTBadCloseMask; // clear "bad close" attribute bit
602
err = UpdateHeader (btreePtr);
605
#if SupportsKeyDescriptors
606
if (btreePtr->keyDescPtr != nil) // deallocate keyDescriptor, if any
608
DisposeMemory( btreePtr->keyDescPtr );
612
DisposeMemory( btreePtr );
613
filePtr->fcbBtree = nil;
615
// LogEndTime(kTraceCloseBTree, noErr);
619
/////////////////////// Error - Clean Up and Exit ///////////////////////////
623
// LogEndTime(kTraceCloseBTree, err);
630
/*-------------------------------------------------------------------------------
631
Routine: BTSearchRecord - Search BTree for a record with a matching key.
633
Function: Search for position in B*Tree indicated by searchKey. If a valid node hint
634
is provided, it will be searched first, then SearchTree will be called.
635
If a BTreeIterator is provided, it will be set to the position found as
636
a result of the search. If a record exists at that position, and a BufferDescriptor
637
is supplied, the record will be copied to the buffer (as much as will fit),
638
and recordLen will be set to the length of the record.
640
If an error other than fsBTRecordNotFoundErr occurs, the BTreeIterator, if any,
641
is invalidated, and recordLen is set to 0.
644
Input: pathPtr - pointer to path for BTree file.
645
searchKey - pointer to search key to match.
646
hintPtr - pointer to hint (may be nil)
648
Output: record - pointer to BufferDescriptor containing record
649
recordLen - length of data at recordPtr
650
iterator - pointer to BTreeIterator indicating position result of search
652
Result: noErr - success, record contains copy of record found
653
fsBTRecordNotFoundErr - record was not found, no data copied
654
fsBTInvalidFileErr - no BTreeControlBlock is allocated for the fork
655
fsBTInvalidKeyLengthErr -
657
-------------------------------------------------------------------------------*/
659
OSStatus BTSearchRecord (SFCB *filePtr,
660
BTreeIterator *searchIterator,
661
UInt32 heuristicHint,
662
FSBufferDescriptor *record,
664
BTreeIterator *resultIterator )
667
BTreeControlBlockPtr btreePtr;
668
TreePathTable treePathTable;
670
BlockDescriptor node;
679
// LogStartTime(kTraceSearchBTree);
681
if (filePtr == nil) return paramErr;
682
if (searchIterator == nil) return paramErr;
684
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
685
if (btreePtr == nil) return fsBTInvalidFileErr;
687
#if SupportsKeyDescriptors
688
if (btreePtr->keyCompareProc == nil) // CheckKey if we using Key Descriptor
690
err = CheckKey (&searchIterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
697
////////////////////////////// Take A Hint //////////////////////////////////
699
err = IsItAHint (btreePtr, searchIterator, &validHint);
704
nodeNum = searchIterator->hint.nodeNum;
706
err = GetNode (btreePtr, nodeNum, &node);
709
if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode &&
710
((BTNodeDescriptor*) node.buffer)->numRecords > 0 )
712
foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
714
//�� if !foundRecord, we could still skip tree search if ( 0 < index < numRecords )
717
if (foundRecord == false)
719
err = ReleaseNode (btreePtr, &node);
724
++btreePtr->numValidHints;
728
if( foundRecord == false )
729
(void) BTInvalidateHint( searchIterator );
732
////////////////////////////// Try the heuristicHint //////////////////////////////////
734
if ( (foundRecord == false) && (heuristicHint != kInvalidMRUCacheKey) && (nodeNum != heuristicHint) )
736
// LogStartTime(kHeuristicHint);
737
nodeNum = heuristicHint;
739
err = GetNode (btreePtr, nodeNum, &node);
742
if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode &&
743
((BTNodeDescriptor*) node.buffer)->numRecords > 0 )
745
foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
748
if (foundRecord == false)
750
err = ReleaseNode (btreePtr, &node);
754
// LogEndTime(kHeuristicHint, (foundRecord == false));
757
//////////////////////////// Search The Tree ////////////////////////////////
759
if (foundRecord == false)
761
err = SearchTree ( btreePtr, &searchIterator->key, treePathTable, &nodeNum, &node, &index);
764
case noErr: foundRecord = true; break;
765
case fsBTRecordNotFoundErr: break;
766
default: goto ErrorExit;
771
//////////////////////////// Get the Record /////////////////////////////////
773
if (foundRecord == true)
775
//�� Should check for errors! Or BlockMove could choke on recordPtr!!!
776
GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
778
if (recordLen != nil) *recordLen = len;
782
ByteCount recordSize;
784
recordSize = record->itemCount * record->itemSize;
786
PanicIf(len > recordSize, "\pBTSearchRecord: truncating record!");
788
if (len > recordSize) len = recordSize;
790
CopyMemory (recordPtr, record->bufferAddress, len);
795
/////////////////////// Success - Update Iterator ///////////////////////////
797
if (resultIterator != nil)
799
resultIterator->hint.writeCount = btreePtr->writeCount;
800
resultIterator->hint.nodeNum = nodeNum;
801
resultIterator->hint.index = index;
802
resultIterator->hint.reserved1 = 0;
803
resultIterator->hint.reserved2 = 0;
805
resultIterator->version = 0;
806
resultIterator->reserved = 0;
808
// copy the key in the BTree when found rather than searchIterator->key to get proper case/diacriticals
809
if (foundRecord == true)
810
CopyKey(btreePtr, keyPtr, &resultIterator->key);
812
CopyKey(btreePtr, &searchIterator->key, &resultIterator->key);
815
err = ReleaseNode (btreePtr, &node);
818
// LogEndTime(kTraceSearchBTree, (foundRecord == false));
820
if (foundRecord == false) return fsBTRecordNotFoundErr;
824
/////////////////////// Error - Clean Up and Exit ///////////////////////////
828
if (recordLen != nil)
831
if (resultIterator != nil)
833
resultIterator->hint.writeCount = 0;
834
resultIterator->hint.nodeNum = 0;
835
resultIterator->hint.index = 0;
836
resultIterator->hint.reserved1 = 0;
837
resultIterator->hint.reserved2 = 0;
839
resultIterator->version = 0;
840
resultIterator->reserved = 0;
841
resultIterator->key.length16 = 0; // zero out two bytes to cover both types of keys
844
if ( err == fsBTEmptyErr )
845
err = fsBTRecordNotFoundErr;
847
// LogEndTime(kTraceSearchBTree, err);
854
/*-------------------------------------------------------------------------------
855
Routine: BTIterateRecord - Find the first, next, previous, or last record.
857
Function: Find the first, next, previous, or last record in the BTree
859
Input: pathPtr - pointer to path iterate records for.
860
operation - iteration operation (first,next,prev,last)
861
iterator - pointer to iterator indicating start position
863
Output: iterator - iterator is updated to indicate new position
864
newKeyPtr - pointer to buffer to copy key found by iteration
865
record - pointer to buffer to copy record found by iteration
866
recordLen - length of record
868
Result: noErr - success
870
-------------------------------------------------------------------------------*/
872
OSStatus BTIterateRecord (SFCB *filePtr,
873
BTreeIterationOperation operation,
874
BTreeIterator *iterator,
875
FSBufferDescriptor *record,
879
BTreeControlBlockPtr btreePtr;
887
BlockDescriptor left, node, right;
891
// LogStartTime(kTraceGetBTreeRecord);
893
////////////////////////// Priliminary Checks ///////////////////////////////
905
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
908
return fsBTInvalidFileErr; //�� handle properly
911
if ((operation != kBTreeFirstRecord) &&
912
(operation != kBTreeNextRecord) &&
913
(operation != kBTreeCurrentRecord) &&
914
(operation != kBTreePrevRecord) &&
915
(operation != kBTreeLastRecord))
917
err = fsInvalidIterationMovmentErr;
921
/////////////////////// Find First or Last Record ///////////////////////////
923
if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
925
if (operation == kBTreeFirstRecord) nodeNum = btreePtr->firstLeafNode;
926
else nodeNum = btreePtr->lastLeafNode;
934
err = GetNode (btreePtr, nodeNum, &node);
937
if ( ((NodeDescPtr) node.buffer)->kind != kBTLeafNode ||
938
((NodeDescPtr) node.buffer)->numRecords <= 0 )
940
err = ReleaseNode (btreePtr, &node);
943
err = fsBTInvalidNodeErr;
947
if (operation == kBTreeFirstRecord) index = 0;
948
else index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1;
950
goto CopyData; //�� is there a cleaner way?
954
//////////////////////// Find Iterator Position /////////////////////////////
956
err = FindIteratorPosition (btreePtr, iterator,
957
&left, &node, &right, &nodeNum, &index, &foundRecord);
961
///////////////////// Find Next Or Previous Record //////////////////////////
963
if (operation == kBTreePrevRecord)
971
if (left.buffer == nil)
973
nodeNum = ((NodeDescPtr) node.buffer)->bLink;
976
err = GetNode (btreePtr, nodeNum, &left);
979
err = fsBTStartOfIterationErr;
983
// Before we stomp on "right", we'd better release it if needed
984
if (right.buffer != nil) {
985
err = ReleaseNode(btreePtr, &right);
991
index = ((NodeDescPtr) node.buffer)->numRecords -1;
994
else if (operation == kBTreeNextRecord)
996
if ((foundRecord != true) &&
997
(((NodeDescPtr) node.buffer)->fLink == 0) &&
998
(index == ((NodeDescPtr) node.buffer)->numRecords))
1000
err = fsBTEndOfIterationErr;
1004
// we did not find the record but the index is already positioned correctly
1005
if ((foundRecord == false) && (index != ((NodeDescPtr) node.buffer)->numRecords))
1008
// we found the record OR we have to look in the next node
1009
if (index < ((NodeDescPtr) node.buffer)->numRecords -1)
1015
if (right.buffer == nil)
1017
nodeNum = ((NodeDescPtr) node.buffer)->fLink;
1020
err = GetNode (btreePtr, nodeNum, &right);
1021
M_ExitOnError (err);
1023
err = fsBTEndOfIterationErr;
1027
// Before we stomp on "left", we'd better release it if needed
1028
if (left.buffer != nil) {
1029
err = ReleaseNode(btreePtr, &left);
1038
else // operation == kBTreeCurrentRecord
1040
// make sure we have something... <CS9>
1041
if ((foundRecord != true) &&
1042
(index >= ((NodeDescPtr) node.buffer)->numRecords))
1044
err = fsBTEndOfIterationErr;
1049
//////////////////// Copy Record And Update Iterator ////////////////////////
1053
// added check for errors <CS9>
1054
err = GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
1055
M_ExitOnError (err);
1057
if (recordLen != nil) *recordLen = len;
1061
ByteCount recordSize;
1063
recordSize = record->itemCount * record->itemSize;
1065
PanicIf(len > recordSize, "\pBTIterateRecord: truncating record!");
1067
if (len > recordSize) len = recordSize;
1069
CopyMemory (recordPtr, record->bufferAddress, len);
1072
if (iterator != nil) // first & last do not require iterator
1074
iterator->hint.writeCount = btreePtr->writeCount;
1075
iterator->hint.nodeNum = nodeNum;
1076
iterator->hint.index = index;
1077
iterator->hint.reserved1 = 0;
1078
iterator->hint.reserved2 = 0;
1080
iterator->version = 0;
1081
iterator->reserved = 0;
1083
CopyKey(btreePtr, keyPtr, &iterator->key);
1087
///////////////////////////// Release Nodes /////////////////////////////////
1089
err = ReleaseNode (btreePtr, &node);
1090
M_ExitOnError (err);
1092
if (left.buffer != nil)
1094
err = ReleaseNode (btreePtr, &left);
1095
M_ExitOnError (err);
1098
if (right.buffer != nil)
1100
err = ReleaseNode (btreePtr, &right);
1101
M_ExitOnError (err);
1104
// LogEndTime(kTraceGetBTreeRecord, noErr);
1108
/////////////////////// Error - Clean Up and Exit ///////////////////////////
1112
(void) ReleaseNode (btreePtr, &left);
1113
(void) ReleaseNode (btreePtr, &node);
1114
(void) ReleaseNode (btreePtr, &right);
1116
if (recordLen != nil)
1119
if (iterator != nil)
1121
iterator->hint.writeCount = 0;
1122
iterator->hint.nodeNum = 0;
1123
iterator->hint.index = 0;
1124
iterator->hint.reserved1 = 0;
1125
iterator->hint.reserved2 = 0;
1127
iterator->version = 0;
1128
iterator->reserved = 0;
1129
iterator->key.length16 = 0;
1132
if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
1133
err = fsBTRecordNotFoundErr;
1135
// LogEndTime(kTraceGetBTreeRecord, err);
1141
//////////////////////////////// BTInsertRecord /////////////////////////////////
1143
OSStatus BTInsertRecord (SFCB *filePtr,
1144
BTreeIterator *iterator,
1145
FSBufferDescriptor *record,
1149
BTreeControlBlockPtr btreePtr;
1150
TreePathTable treePathTable;
1152
BlockDescriptor nodeRec;
1153
UInt32 insertNodeNum;
1158
////////////////////////// Priliminary Checks ///////////////////////////////
1160
nodeRec.buffer = nil; // so we can call ReleaseNode
1162
err = CheckInsertParams (filePtr, iterator, record, recordLen);
1166
// LogStartTime(kTraceInsertBTreeRecord);
1168
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1170
///////////////////////// Find Insert Position //////////////////////////////
1172
// always call SearchTree for Insert
1173
err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1175
switch (err) // set/replace/insert decision point
1177
case noErr: err = fsBTDuplicateRecordErr;
1180
case fsBTRecordNotFoundErr: break;
1182
case fsBTEmptyErr: // if tree empty add 1st leaf node
1184
if (btreePtr->freeNodes == 0)
1186
err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
1187
M_ExitOnError (err);
1190
err = AllocateNode (btreePtr, &insertNodeNum);
1191
M_ExitOnError (err);
1193
err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
1194
M_ExitOnError (err);
1196
((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
1197
((NodeDescPtr)nodeRec.buffer)->height = 1;
1199
recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0,
1200
&iterator->key, KeyLength(btreePtr, &iterator->key),
1201
record->bufferAddress, recordLen );
1202
if (recordFit != true)
1204
err = fsBTRecordTooLargeErr;
1208
err = UpdateNode (btreePtr, &nodeRec);
1209
M_ExitOnError (err);
1211
// update BTreeControlBlock
1212
btreePtr->treeDepth = 1;
1213
btreePtr->rootNode = insertNodeNum;
1214
btreePtr->firstLeafNode = insertNodeNum;
1215
btreePtr->lastLeafNode = insertNodeNum;
1216
M_BTreeHeaderDirty (btreePtr);
1226
recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
1227
&iterator->key, KeyLength(btreePtr, &iterator->key),
1228
record->bufferAddress, recordLen);
1229
if (recordFit == true)
1231
err = UpdateNode (btreePtr, &nodeRec);
1232
M_ExitOnError (err);
1238
/////////////////////// Extend File If Necessary ////////////////////////////
1240
nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //�� math limit
1241
if (nodesNeeded > 0)
1243
nodesNeeded += btreePtr->totalNodes;
1244
if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
1247
err = ExtendBTree (btreePtr, nodesNeeded);
1248
M_ExitOnError (err);
1251
// no need to delete existing record
1253
err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1254
recordLen, &nodeRec, index, 1, kInsertRecord, &insertNodeNum);
1255
M_ExitOnError (err);
1258
//////////////////////////////// Success ////////////////////////////////////
1261
++btreePtr->writeCount; // <CS10>
1262
++btreePtr->leafRecords;
1263
M_BTreeHeaderDirty (btreePtr);
1266
iterator->hint.writeCount = btreePtr->writeCount; // unused until <CS10>
1267
iterator->hint.nodeNum = insertNodeNum;
1268
iterator->hint.index = 0; // unused
1269
iterator->hint.reserved1 = 0;
1270
iterator->hint.reserved2 = 0;
1272
// LogEndTime(kTraceInsertBTreeRecord, noErr);
1277
////////////////////////////// Error Exit ///////////////////////////////////
1280
(void) ReleaseNode (btreePtr, &nodeRec);
1282
iterator->hint.writeCount = 0;
1283
iterator->hint.nodeNum = 0;
1284
iterator->hint.index = 0;
1285
iterator->hint.reserved1 = 0;
1286
iterator->hint.reserved2 = 0;
1288
if (err == fsBTEmptyErr)
1289
err = fsBTRecordNotFoundErr;
1291
// LogEndTime(kTraceInsertBTreeRecord, err);
1298
////////////////////////////////// BTSetRecord //////////////////////////////////
1300
OSStatus BTSetRecord (SFCB *filePtr,
1301
BTreeIterator *iterator,
1302
FSBufferDescriptor *record,
1306
BTreeControlBlockPtr btreePtr;
1307
TreePathTable treePathTable;
1309
BlockDescriptor nodeRec;
1310
UInt32 insertNodeNum;
1312
Boolean recordFound = false;
1318
////////////////////////// Priliminary Checks ///////////////////////////////
1320
nodeRec.buffer = nil; // so we can call ReleaseNode
1322
err = CheckInsertParams (filePtr, iterator, record, recordLen);
1326
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1329
///////////////////////// Find Insert Position //////////////////////////////
1331
err = IsItAHint (btreePtr, iterator, &validHint);
1332
M_ExitOnError (err);
1336
insertNodeNum = iterator->hint.nodeNum;
1338
err = GetNode (btreePtr, insertNodeNum, &nodeRec);
1341
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1342
M_ExitOnError (err);
1346
err = UpdateNode (btreePtr, &nodeRec);
1347
M_ExitOnError (err);
1350
++btreePtr->numValidHints;
1355
(void) BTInvalidateHint( iterator );
1358
err = ReleaseNode (btreePtr, &nodeRec);
1359
M_ExitOnError (err);
1363
err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1365
switch (err) // set/replace/insert decision point
1367
case noErr: recordFound = true;
1370
case fsBTRecordNotFoundErr: break;
1372
case fsBTEmptyErr: // if tree empty add 1st leaf node
1374
if (btreePtr->freeNodes == 0)
1376
err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
1377
M_ExitOnError (err);
1380
err = AllocateNode (btreePtr, &insertNodeNum);
1381
M_ExitOnError (err);
1383
err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
1384
M_ExitOnError (err);
1386
((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
1387
((NodeDescPtr)nodeRec.buffer)->height = 1;
1389
recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0,
1390
&iterator->key, KeyLength(btreePtr, &iterator->key),
1391
record->bufferAddress, recordLen );
1392
if (recordFit != true)
1394
err = fsBTRecordTooLargeErr;
1398
err = UpdateNode (btreePtr, &nodeRec);
1399
M_ExitOnError (err);
1401
// update BTreeControlBlock
1402
btreePtr->rootNode = insertNodeNum;
1403
btreePtr->treeDepth = 1;
1404
btreePtr->flags |= kBTHeaderDirty;
1408
default: goto ErrorExit;
1412
if (recordFound == true) // Simple Replace - optimization avoids unecessary ExtendBTree
1414
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1415
M_ExitOnError (err);
1419
err = UpdateNode (btreePtr, &nodeRec);
1420
M_ExitOnError (err);
1427
/////////////////////// Extend File If Necessary ////////////////////////////
1429
nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //�� math limit
1430
if (nodesNeeded > 0)
1432
nodesNeeded += btreePtr->totalNodes;
1433
if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
1436
err = ExtendBTree (btreePtr, nodesNeeded);
1437
M_ExitOnError (err);
1441
if (recordFound == true) // Delete existing record
1443
DeleteRecord (btreePtr, nodeRec.buffer, index);
1444
operation = kReplaceRecord;
1446
operation = kInsertRecord;
1449
err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1450
recordLen, &nodeRec, index, 1, operation, &insertNodeNum);
1451
M_ExitOnError (err);
1453
++btreePtr->writeCount; // <CS10> writeCount changes only if the tree structure changed
1456
if (recordFound == false)
1458
++btreePtr->leafRecords;
1459
M_BTreeHeaderDirty (btreePtr);
1463
iterator->hint.writeCount = btreePtr->writeCount; // unused until <CS10>
1464
iterator->hint.nodeNum = insertNodeNum;
1465
iterator->hint.index = 0; // unused
1466
iterator->hint.reserved1 = 0;
1467
iterator->hint.reserved2 = 0;
1472
////////////////////////////// Error Exit ///////////////////////////////////
1476
(void) ReleaseNode (btreePtr, &nodeRec);
1478
iterator->hint.writeCount = 0;
1479
iterator->hint.nodeNum = 0;
1480
iterator->hint.index = 0;
1481
iterator->hint.reserved1 = 0;
1482
iterator->hint.reserved2 = 0;
1489
//////////////////////////////// BTReplaceRecord ////////////////////////////////
1491
OSStatus BTReplaceRecord (SFCB *filePtr,
1492
BTreeIterator *iterator,
1493
FSBufferDescriptor *record,
1497
BTreeControlBlockPtr btreePtr;
1498
TreePathTable treePathTable;
1500
BlockDescriptor nodeRec;
1501
UInt32 insertNodeNum;
1507
////////////////////////// Priliminary Checks ///////////////////////////////
1509
nodeRec.buffer = nil; // so we can call ReleaseNode
1511
err = CheckInsertParams (filePtr, iterator, record, recordLen);
1515
// LogStartTime(kTraceReplaceBTreeRecord);
1517
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1519
////////////////////////////// Take A Hint //////////////////////////////////
1521
err = IsItAHint (btreePtr, iterator, &validHint);
1522
M_ExitOnError (err);
1526
insertNodeNum = iterator->hint.nodeNum;
1528
err = GetNode (btreePtr, insertNodeNum, &nodeRec);
1531
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1532
M_ExitOnError (err);
1536
err = UpdateNode (btreePtr, &nodeRec);
1537
M_ExitOnError (err);
1539
++btreePtr->numValidHints;
1545
(void) BTInvalidateHint( iterator );
1548
err = ReleaseNode (btreePtr, &nodeRec);
1549
M_ExitOnError (err);
1553
(void) BTInvalidateHint( iterator );
1558
////////////////////////////// Get A Clue ///////////////////////////////////
1560
err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1561
M_ExitOnError (err); // record must exit for Replace
1563
// optimization - if simple replace will work then don't extend btree
1564
// �� if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
1566
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1567
M_ExitOnError (err);
1571
err = UpdateNode (btreePtr, &nodeRec);
1572
M_ExitOnError (err);
1578
//////////////////////////// Make Some Room /////////////////////////////////
1580
nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //�� math limit
1581
if (nodesNeeded > 0)
1583
nodesNeeded += btreePtr->totalNodes;
1584
if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
1587
err = ExtendBTree (btreePtr, nodesNeeded);
1588
M_ExitOnError (err);
1592
DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record
1594
err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1595
recordLen, &nodeRec, index, 1, kReplaceRecord, &insertNodeNum);
1596
M_ExitOnError (err);
1598
++btreePtr->writeCount; // <CS10> writeCount changes only if the tree structure changed
1602
iterator->hint.writeCount = btreePtr->writeCount; // unused until <CS10>
1603
iterator->hint.nodeNum = insertNodeNum;
1604
iterator->hint.index = 0; // unused
1605
iterator->hint.reserved1 = 0;
1606
iterator->hint.reserved2 = 0;
1608
// LogEndTime(kTraceReplaceBTreeRecord, noErr);
1613
////////////////////////////// Error Exit ///////////////////////////////////
1617
(void) ReleaseNode (btreePtr, &nodeRec);
1619
iterator->hint.writeCount = 0;
1620
iterator->hint.nodeNum = 0;
1621
iterator->hint.index = 0;
1622
iterator->hint.reserved1 = 0;
1623
iterator->hint.reserved2 = 0;
1625
// LogEndTime(kTraceReplaceBTreeRecord, err);
1632
//////////////////////////////// BTDeleteRecord /////////////////////////////////
1634
OSStatus BTDeleteRecord (SFCB *filePtr,
1635
BTreeIterator *iterator )
1638
BTreeControlBlockPtr btreePtr;
1639
TreePathTable treePathTable;
1640
BlockDescriptor nodeRec;
1644
// LogStartTime(kTraceDeleteBTreeRecord);
1646
////////////////////////// Priliminary Checks ///////////////////////////////
1648
nodeRec.buffer = nil; // so we can call ReleaseNode
1650
M_ReturnErrorIf (filePtr == nil, paramErr);
1651
M_ReturnErrorIf (iterator == nil, paramErr);
1653
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1654
if (btreePtr == nil)
1656
err = fsBTInvalidFileErr;
1660
#if SupportsKeyDescriptors
1661
if (btreePtr->keyDescPtr != nil)
1663
err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
1664
M_ExitOnError (err);
1668
/////////////////////////////// Find Key ////////////////////////////////////
1670
//�� check hint for simple delete case (index > 0, numRecords > 2)
1672
err = SearchTree (btreePtr, &iterator->key, treePathTable, &nodeNum, &nodeRec, &index);
1673
M_ExitOnError (err); // record must exit for Delete
1676
///////////////////////////// Delete Record /////////////////////////////////
1678
err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
1679
M_ExitOnError (err);
1682
++btreePtr->writeCount; // <CS10>
1683
--btreePtr->leafRecords;
1684
M_BTreeHeaderDirty (btreePtr);
1686
iterator->hint.nodeNum = 0;
1688
// LogEndTime(kTraceDeleteBTreeRecord, noErr);
1692
////////////////////////////// Error Exit ///////////////////////////////////
1695
(void) ReleaseNode (btreePtr, &nodeRec);
1697
// LogEndTime(kTraceDeleteBTreeRecord, err);
1704
OSStatus BTGetInformation (SFCB *filePtr,
1706
BTreeInfoRec *info )
1708
#pragma unused (version)
1710
BTreeControlBlockPtr btreePtr;
1713
M_ReturnErrorIf (filePtr == nil, paramErr);
1715
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1717
M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1718
M_ReturnErrorIf (info == nil, paramErr);
1722
info->nodeSize = btreePtr->nodeSize;
1723
info->maxKeyLength = btreePtr->maxKeyLength;
1724
info->treeDepth = btreePtr->treeDepth;
1725
info->numRecords = btreePtr->leafRecords;
1726
info->numNodes = btreePtr->totalNodes;
1727
info->numFreeNodes = btreePtr->freeNodes;
1728
info->keyDescriptor = btreePtr->keyDescPtr; //�� this won't do at all...
1731
if (btreePtr->keyDescPtr == nil)
1732
info->keyDescLength = 0;
1734
info->keyDescLength = (UInt32) btreePtr->keyDescPtr->length;
1741
/*-------------------------------------------------------------------------------
1742
Routine: BTFlushPath - Flush BTreeControlBlock to Header Node.
1744
Function: Brief_description_of_the_function_and_any_side_effects
1747
Input: pathPtr - pointer to path control block for B*Tree file to flush
1751
Result: noErr - success
1753
-------------------------------------------------------------------------------*/
1755
OSStatus BTFlushPath (SFCB *filePtr)
1758
BTreeControlBlockPtr btreePtr;
1761
// LogStartTime(kTraceFlushBTree);
1763
M_ReturnErrorIf (filePtr == nil, paramErr);
1765
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1767
M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1769
err = UpdateHeader (btreePtr);
1771
// LogEndTime(kTraceFlushBTree, err);
1778
/*-------------------------------------------------------------------------------
1779
Routine: BTInvalidateHint - Invalidates the hint within a BTreeInterator.
1781
Function: Invalidates the hint within a BTreeInterator.
1784
Input: iterator - pointer to BTreeIterator
1786
Output: iterator - iterator with the hint.nodeNum cleared
1788
Result: noErr - success
1789
paramErr - iterator == nil
1790
-------------------------------------------------------------------------------*/
1793
OSStatus BTInvalidateHint (BTreeIterator *iterator )
1795
if (iterator == nil)
1798
iterator->hint.nodeNum = 0;
added
removed
.pc/10-linux_specific_code.patch/fsck_hfs.tproj/dfalib/BTree.c
