[apple/hfs.git] / fsck_hfs / dfalib / BTreeScanner.c

/*
 * Copyright (c) 1996-2002, 2005, 2012 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 *
 *	@(#)BTreeScanner.c
 */


#include "BTreeScanner.h"
#include "Scavenger.h"
#include "../cache.h"
#include "../fsck_hfs.h"

static int FindNextLeafNode(	BTScanState *scanState );
static int ReadMultipleNodes( 	BTScanState *scanState );


//_________________________________________________________________________________
//
//	Routine:	BTScanNextRecord
//
//	Purpose:	Return the next leaf record in a scan.
//
//	Inputs:
//		scanState		Scanner's current state
//
//	Outputs:
//		key				Key of found record (points into buffer)
//		data			Data of found record (points into buffer)
//		dataSize		Size of data in found record
//
//	Result:
//		noErr			Found a valid record
//		btNotFound		No more records
//
//	Notes:
//		This routine returns pointers to the found record's key and data.  It
//		does not copy the key or data to a caller-supplied buffer (like
//		GetBTreeRecord would).  The caller must not modify the key or data.
//_________________________________________________________________________________

int BTScanNextRecord(	BTScanState *	scanState,
						void * *		key,
						void * *		data,
						u_int32_t *		dataSize  )
{
	int				err;
	u_int16_t		dataSizeShort;
	int64_t			maxLeafRecs;
	
	err = noErr;

	//
	//	If this is the first call, there won't be any nodes in the buffer, so go
	//	find the first first leaf node (if any).
	//	
	if ( scanState->nodesLeftInBuffer <= 0 )
		err = FindNextLeafNode( scanState );

	// btcb->leafRecords may be fragile (the B-Tree header could be damaged)
	// so in order to do a sanity check on the max number of leaf records we 
	// could have we use the catalog file's physical size divided by the smallest
	// leaf node record size to get our ceiling.
	maxLeafRecs = scanState->btcb->fcbPtr->fcbPhysicalSize / sizeof( HFSCatalogThread );

	while ( err == noErr ) 
	{ 
		//	See if we have a record in the current node
		err = GetRecordByIndex( scanState->btcb, scanState->currentNodePtr, 
								scanState->recordNum, (KeyPtr *) key, 
								(UInt8 **) data, &dataSizeShort  );
		if ( err == noErr )
		{
			++scanState->recordsFound;
			++scanState->recordNum;
			if (dataSize != NULL)
				*dataSize = dataSizeShort;
			return noErr;
		}
		
		//	We're done with the current node.  See if we've returned all the records
		if ( scanState->recordsFound >= maxLeafRecs )
			return btNotFound;

		//	Move to the first record of the next leaf node
		scanState->recordNum = 0; 
		err = FindNextLeafNode( scanState );
	}
	
	//
	//	If we got an EOF error from FindNextLeafNode, then there are no more leaf
	//	records to be found.
	//
	if ( err == fsEndOfIterationErr )
		err = btNotFound;
	
	return err;
	
} /* BTScanNextRecord */


//_________________________________________________________________________________
//
//	Routine:	FindNextLeafNode
//
//	Purpose:	Point to the next leaf node in the buffer.  Read more nodes
//				into the buffer if needed (and allowed).
//
//	Inputs:
//		scanState		Scanner's current state
//
//	Result:
//		noErr			Found a valid record
//		fsEndOfIterationErr	No more nodes in file
//_________________________________________________________________________________

static int FindNextLeafNode(	BTScanState *scanState )
{
	int					err;
    BlockDescriptor		myBlockDescriptor;
	
	err = noErr;		// Assume everything will be OK
	
	while ( 1 ) 
	{
		++scanState->nodeNum;
		--scanState->nodesLeftInBuffer;
		if ( scanState->nodesLeftInBuffer <= 0 ) 
		{
			//	read some more nodes into buffer
			err = ReadMultipleNodes( scanState );
			if ( err != noErr ) 
				break;
		}
		else 
		{
			//	Adjust to point to the next node in the buffer
			
			//	If we've looked at all nodes in the tree, then we're done
			if ( scanState->nodeNum >= scanState->btcb->totalNodes )
				return fsEndOfIterationErr;

			scanState->currentNodePtr = (BTNodeDescriptor *)((UInt8 *)scanState->currentNodePtr + scanState->btcb->nodeSize);
		}
		
        // need to manufacture a BlockDescriptor since hfs_swap_BTNode expects one as input
        myBlockDescriptor.buffer = (void *) scanState->currentNodePtr;
        myBlockDescriptor.blockHeader = NULL;
        myBlockDescriptor.blockNum = scanState->nodeNum;
        myBlockDescriptor.blockSize = scanState->btcb->nodeSize;
        myBlockDescriptor.blockReadFromDisk = false;
        myBlockDescriptor.fragmented = false;
        err = hfs_swap_BTNode(&myBlockDescriptor, scanState->btcb->fcbPtr, kSwapBTNodeBigToHost);
		if ( err != noErr )
		{
			err = noErr;
			continue;
		}
		
		// NOTE - todo - add less lame sanity check to allow leaf nodes that
		// only have damaged kind. 
		if ( scanState->currentNodePtr->kind == kBTLeafNode )
			break;
	}
	
	return err;
	
} /* FindNextLeafNode */


//_________________________________________________________________________________
//
//	Routine:	ReadMultipleNodes
//
//	Purpose:	Read one or more nodes into the buffer.
//
//	Inputs:
//		theScanStatePtr		Scanner's current state
//
//	Result:
//		noErr				One or nodes were read
//		fsEndOfIterationErr		No nodes left in file, none in buffer
//_________________________________________________________________________________

int CacheRawRead (Cache_t *cache, uint64_t off, uint32_t len, void *buf);

static int ReadMultipleNodes( BTScanState *theScanStatePtr )
{
	int						myErr = noErr;
	BTreeControlBlockPtr  	myBTreeCBPtr;
	UInt64					myPhyBlockNum;
	SInt64  				myPhyOffset;
	UInt64					mySectorOffset; // offset within file (in 512-byte sectors)
	UInt32					myContiguousBytes;
	
	myBTreeCBPtr = theScanStatePtr->btcb;
			
	// map logical block in catalog btree file to physical block on volume
	mySectorOffset = 
		(((UInt64)theScanStatePtr->nodeNum * (UInt64)myBTreeCBPtr->fcbPtr->fcbBlockSize) >> kSectorShift);
	myErr = MapFileBlockC( myBTreeCBPtr->fcbPtr->fcbVolume, myBTreeCBPtr->fcbPtr,
						   theScanStatePtr->bufferSize, mySectorOffset, 
						   &myPhyBlockNum, &myContiguousBytes );
	if ( myErr != noErr )
	{
		myErr = fsEndOfIterationErr;
		goto ExitThisRoutine;
	}
	
	// now read blocks from the device 
	myPhyOffset = (SInt64) ( ( (UInt64) myPhyBlockNum ) << kSectorShift );

	// Go through the cache, so we can get any locked-in journal changes
	Buf_t *tmpbuf = NULL;

	myErr = CacheRead( myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache,
			   myPhyOffset, myContiguousBytes, &tmpbuf );

	if ( myErr == noErr )
	{
		if (tmpbuf)
		{
			if (tmpbuf->Length < myContiguousBytes)
				abort();
			memcpy(theScanStatePtr->bufferPtr, tmpbuf->Buffer, myContiguousBytes);
			CacheRelease(myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache, tmpbuf, 0);
		} else
			abort();
#if DEBUG_BTREE
		/*
		 * This code was written to help debug a cache problem, where CacheRead()
		 * was returning different results than CacheRawRead().  I am leaving it
		 * around because I fear that will happen again, so it can be used for
		 * reference, rather than rewrite it then.
		 */
		size_t tempBufferSize = myContiguousBytes;
		int tempError;
		unsigned char *tempBuffer = malloc(myContiguousBytes);
		if (tempBuffer == NULL)
			abort();
		tempError = CacheRawRead( myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache, 
				      myPhyOffset, myContiguousBytes, tempBuffer);
		if (memcmp(tempBuffer, theScanStatePtr->bufferPtr, myContiguousBytes) != 0)
		{
			uint8_t *raw, *cached;
			fprintf(stderr, "CacheRead and CacheRawRead returned different values\n");
			fprintf(stderr, "\tmyPhyOffset = %llu, myContiguousBytes = %u\n", myPhyOffset, myContiguousBytes);
			size_t i = 0;
			for (i = 0; i < myContiguousBytes; i++)
			{
				cached = ((uint8_t*)theScanStatePtr->bufferPtr)[i];
				raw = tempBuffer[i];
				if (cached != raw)
				{
					fprintf(stderr, "\tOffset %zu:  cached value = 0x%02x, raw value = 0x%02x\n", i, cached, raw);
					break;
				}
			}
			extern void dumpCache(void*);
			dumpCache(myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache);
			abort();
		}
		free(tempBuffer);
#endif
	}


	if ( myErr != noErr )
	{
		myErr = fsEndOfIterationErr;
		goto ExitThisRoutine;
	}

	theScanStatePtr->nodesLeftInBuffer = myContiguousBytes /
		theScanStatePtr->btcb->nodeSize;
	theScanStatePtr->currentNodePtr = (BTNodeDescriptor *) theScanStatePtr->bufferPtr;

ExitThisRoutine:
	return myErr;
	
} /* ReadMultipleNodes */


//_________________________________________________________________________________
//
//	Routine:	BTScanInitialize
//
//	Purpose:	Prepare to start a new BTree scan.
//
//	Inputs:
//		btreeFile		The B-Tree's file control block
//
//	Outputs:
//		scanState		Scanner's current state; pass to other scanner calls
//
//_________________________________________________________________________________

int		BTScanInitialize(	const SFCB *	btreeFile,
							BTScanState	*	scanState     )
{
	BTreeControlBlock	*btcb;
	u_int32_t			bufferSize;
	
	//
	//	Make sure this is a valid B-Tree file
	//
	btcb = (BTreeControlBlock *) btreeFile->fcbBtree;
	if (btcb == NULL)
		return R_RdErr;
	
	//
	//	Make sure buffer size is big enough, and a multiple of the
	//	B-Tree node size
	//
	bufferSize = (kCatScanBufferSize / btcb->nodeSize) * btcb->nodeSize;

	//
	//	Set up the scanner's state
	//
	scanState->bufferSize			= bufferSize;
	scanState->bufferPtr = (void *) AllocateMemory( bufferSize );
	if ( scanState->bufferPtr == NULL )
		return( R_NoMem );

	scanState->btcb					= btcb;
	scanState->nodeNum				= 0;
	scanState->recordNum			= 0;
	scanState->currentNodePtr		= NULL;
	scanState->nodesLeftInBuffer	= 0;		// no nodes currently in buffer
	scanState->recordsFound			= 0;
		
	return noErr;
	
} /* BTScanInitialize */


//_________________________________________________________________________________
//
//	Routine:	BTScanTerminate
//
//	Purpose:	Return state information about a scan so that it can be resumed
//				later via BTScanInitialize.
//
//	Inputs:
//		scanState		Scanner's current state
//
//	Outputs:
//		nextNode		Node number to resume a scan (pass to BTScanInitialize)
//		nextRecord		Record number to resume a scan (pass to BTScanInitialize)
//		recordsFound	Valid records seen so far (pass to BTScanInitialize)
//_________________________________________________________________________________

int	 BTScanTerminate(	BTScanState *		scanState	)
{
	if ( scanState->bufferPtr != NULL )
	{
		DisposeMemory( scanState->bufferPtr );
		scanState->bufferPtr = NULL;
		scanState->currentNodePtr = NULL;
	}
	
	return noErr;
	
} /* BTScanTerminate */
Commit	Line	Data
51e135ce A	1	/*
	2	* Copyright (c) 1996-2002, 2005, 2012 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. Please obtain a copy of the License at
	10	* http://www.opensource.apple.com/apsl/ and read it before using this
	11	* file.
	12	*
	13	* The Original Code and all software distributed under the License are
	14	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	15	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	16	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	17	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	18	* Please see the License for the specific language governing rights and
	19	* limitations under the License.
	20	*
	21	* @APPLE_LICENSE_HEADER_END@
	22	*
	23	* @(#)BTreeScanner.c
	24	*/
	25
	26
	27	#include "BTreeScanner.h"
	28	#include "Scavenger.h"
	29	#include "../cache.h"
	30	#include "../fsck_hfs.h"
	31
	32	static int FindNextLeafNode( BTScanState *scanState );
	33	static int ReadMultipleNodes( BTScanState *scanState );
	34
	35
	36	//_________________________________________________________________________________
	37	//
	38	// Routine: BTScanNextRecord
	39	//
	40	// Purpose: Return the next leaf record in a scan.
	41	//
	42	// Inputs:
	43	// scanState Scanner's current state
	44	//
	45	// Outputs:
	46	// key Key of found record (points into buffer)
	47	// data Data of found record (points into buffer)
	48	// dataSize Size of data in found record
	49	//
	50	// Result:
	51	// noErr Found a valid record
	52	// btNotFound No more records
	53	//
	54	// Notes:
	55	// This routine returns pointers to the found record's key and data. It
	56	// does not copy the key or data to a caller-supplied buffer (like
	57	// GetBTreeRecord would). The caller must not modify the key or data.
	58	//_________________________________________________________________________________
	59
	60	int BTScanNextRecord( BTScanState * scanState,
	61	void * * key,
	62	void * * data,
	63	u_int32_t * dataSize )
	64	{
65	int err;
66	u_int16_t dataSizeShort;
67	int64_t maxLeafRecs;
68
69	err = noErr;
70
71	//
72	// If this is the first call, there won't be any nodes in the buffer, so go
73	// find the first first leaf node (if any).
74	//
75	if ( scanState->nodesLeftInBuffer <= 0 )
76	err = FindNextLeafNode( scanState );
77
78	// btcb->leafRecords may be fragile (the B-Tree header could be damaged)
79	// so in order to do a sanity check on the max number of leaf records we
80	// could have we use the catalog file's physical size divided by the smallest
81	// leaf node record size to get our ceiling.
82	maxLeafRecs = scanState->btcb->fcbPtr->fcbPhysicalSize / sizeof( HFSCatalogThread );
83
84	while ( err == noErr )
85	{
86	// See if we have a record in the current node
87	err = GetRecordByIndex( scanState->btcb, scanState->currentNodePtr,
88	scanState->recordNum, (KeyPtr *) key,
89	(UInt8 **) data, &dataSizeShort );
90	if ( err == noErr )
91	{
92	++scanState->recordsFound;
93	++scanState->recordNum;
94	if (dataSize != NULL)
95	*dataSize = dataSizeShort;
96	return noErr;
97	}
98
99	// We're done with the current node. See if we've returned all the records
100	if ( scanState->recordsFound >= maxLeafRecs )
101	return btNotFound;
102
103	// Move to the first record of the next leaf node
104	scanState->recordNum = 0;
105	err = FindNextLeafNode( scanState );
106	}
107
108	//
109	// If we got an EOF error from FindNextLeafNode, then there are no more leaf
110	// records to be found.
111	//
112	if ( err == fsEndOfIterationErr )
113	err = btNotFound;
114
115	return err;
116
117	} /* BTScanNextRecord */
118
119
120	//_________________________________________________________________________________
121	//
122	// Routine: FindNextLeafNode
123	//
124	// Purpose: Point to the next leaf node in the buffer. Read more nodes
125	// into the buffer if needed (and allowed).
126	//
127	// Inputs:
128	// scanState Scanner's current state
129	//
130	// Result:
131	// noErr Found a valid record
132	// fsEndOfIterationErr No more nodes in file
133	//_________________________________________________________________________________
134
135	static int FindNextLeafNode( BTScanState *scanState )
136	{
137	int err;
138	BlockDescriptor myBlockDescriptor;
139
140	err = noErr; // Assume everything will be OK
141
142	while ( 1 )
143	{
144	++scanState->nodeNum;
145	--scanState->nodesLeftInBuffer;
146	if ( scanState->nodesLeftInBuffer <= 0 )
147	{
148	// read some more nodes into buffer
149	err = ReadMultipleNodes( scanState );
150	if ( err != noErr )
151	break;
152	}
153	else
154	{
155	// Adjust to point to the next node in the buffer
156
157	// If we've looked at all nodes in the tree, then we're done
158	if ( scanState->nodeNum >= scanState->btcb->totalNodes )
159	return fsEndOfIterationErr;
160
161	scanState->currentNodePtr = (BTNodeDescriptor )((UInt8 )scanState->currentNodePtr + scanState->btcb->nodeSize);
162	}
163
164	// need to manufacture a BlockDescriptor since hfs_swap_BTNode expects one as input
165	myBlockDescriptor.buffer = (void *) scanState->currentNodePtr;
166	myBlockDescriptor.blockHeader = NULL;
167	myBlockDescriptor.blockNum = scanState->nodeNum;
168	myBlockDescriptor.blockSize = scanState->btcb->nodeSize;
169	myBlockDescriptor.blockReadFromDisk = false;
170	myBlockDescriptor.fragmented = false;
171	err = hfs_swap_BTNode(&myBlockDescriptor, scanState->btcb->fcbPtr, kSwapBTNodeBigToHost);
172	if ( err != noErr )
173	{
174	err = noErr;
175	continue;
176	}
177
178	// NOTE - todo - add less lame sanity check to allow leaf nodes that
179	// only have damaged kind.
180	if ( scanState->currentNodePtr->kind == kBTLeafNode )
181	break;
182	}
183
184	return err;
185
186	} /* FindNextLeafNode */
187
188
189	//_________________________________________________________________________________
190	//
191	// Routine: ReadMultipleNodes
192	//
193	// Purpose: Read one or more nodes into the buffer.
194	//
195	// Inputs:
196	// theScanStatePtr Scanner's current state
197	//
198	// Result:
199	// noErr One or nodes were read
200	// fsEndOfIterationErr No nodes left in file, none in buffer
201	//_________________________________________________________________________________
202
203	int CacheRawRead (Cache_t cache, uint64_t off, uint32_t len, void buf);
204
205	static int ReadMultipleNodes( BTScanState *theScanStatePtr )
206	{
207	int myErr = noErr;
208	BTreeControlBlockPtr myBTreeCBPtr;
209	UInt64 myPhyBlockNum;
210	SInt64 myPhyOffset;
211	UInt64 mySectorOffset; // offset within file (in 512-byte sectors)
212	UInt32 myContiguousBytes;
213
214	myBTreeCBPtr = theScanStatePtr->btcb;
215
216	// map logical block in catalog btree file to physical block on volume
217	mySectorOffset =
218	(((UInt64)theScanStatePtr->nodeNum * (UInt64)myBTreeCBPtr->fcbPtr->fcbBlockSize) >> kSectorShift);
219	myErr = MapFileBlockC( myBTreeCBPtr->fcbPtr->fcbVolume, myBTreeCBPtr->fcbPtr,
220	theScanStatePtr->bufferSize, mySectorOffset,
221	&myPhyBlockNum, &myContiguousBytes );
222	if ( myErr != noErr )
223	{
224	myErr = fsEndOfIterationErr;
225	goto ExitThisRoutine;
226	}
227
228	// now read blocks from the device
229	myPhyOffset = (SInt64) ( ( (UInt64) myPhyBlockNum ) << kSectorShift );
230
231	// Go through the cache, so we can get any locked-in journal changes
232	Buf_t *tmpbuf = NULL;
233
234	myErr = CacheRead( myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache,
235	myPhyOffset, myContiguousBytes, &tmpbuf );
236
237	if ( myErr == noErr )
238	{
239	if (tmpbuf)
240	{
241	if (tmpbuf->Length < myContiguousBytes)
242	abort();
243	memcpy(theScanStatePtr->bufferPtr, tmpbuf->Buffer, myContiguousBytes);
244	CacheRelease(myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache, tmpbuf, 0);
245	} else
246	abort();
247	#if DEBUG_BTREE
248	/*
249	* This code was written to help debug a cache problem, where CacheRead()
250	* was returning different results than CacheRawRead(). I am leaving it
251	* around because I fear that will happen again, so it can be used for
252	* reference, rather than rewrite it then.
253	*/
254	size_t tempBufferSize = myContiguousBytes;
255	int tempError;
256	unsigned char *tempBuffer = malloc(myContiguousBytes);
257	if (tempBuffer == NULL)
258	abort();
259	tempError = CacheRawRead( myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache,
260	myPhyOffset, myContiguousBytes, tempBuffer);
261	if (memcmp(tempBuffer, theScanStatePtr->bufferPtr, myContiguousBytes) != 0)
262	{
263	uint8_t raw, cached;
264	fprintf(stderr, "CacheRead and CacheRawRead returned different values\n");
265	fprintf(stderr, "\tmyPhyOffset = %llu, myContiguousBytes = %u\n", myPhyOffset, myContiguousBytes);
266	size_t i = 0;
267	for (i = 0; i < myContiguousBytes; i++)
268	{
269	cached = ((uint8_t*)theScanStatePtr->bufferPtr)[i];
270	raw = tempBuffer[i];
271	if (cached != raw)
272	{
273	fprintf(stderr, "\tOffset %zu: cached value = 0x%02x, raw value = 0x%02x\n", i, cached, raw);
274	break;
275	}
276	}
277	extern void dumpCache(void*);
278	dumpCache(myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache);
279	abort();
280	}
281	free(tempBuffer);
282	#endif
283	}
284
285
286
287	if ( myErr != noErr )
288	{
289	myErr = fsEndOfIterationErr;
290	goto ExitThisRoutine;
291	}
292
293	theScanStatePtr->nodesLeftInBuffer = myContiguousBytes /
294	theScanStatePtr->btcb->nodeSize;
295	theScanStatePtr->currentNodePtr = (BTNodeDescriptor *) theScanStatePtr->bufferPtr;
296
297	ExitThisRoutine:
298	return myErr;
299
300	} /* ReadMultipleNodes */
301
302
303	//_________________________________________________________________________________
304	//
305	// Routine: BTScanInitialize
306	//
307	// Purpose: Prepare to start a new BTree scan.
308	//
309	// Inputs:
310	// btreeFile The B-Tree's file control block
311	//
312	// Outputs:
313	// scanState Scanner's current state; pass to other scanner calls
314	//
315	//_________________________________________________________________________________
316
317	int BTScanInitialize( const SFCB * btreeFile,
318	BTScanState * scanState )
319	{
320	BTreeControlBlock *btcb;
321	u_int32_t bufferSize;
322
323	//
324	// Make sure this is a valid B-Tree file
325	//
326	btcb = (BTreeControlBlock *) btreeFile->fcbBtree;
327	if (btcb == NULL)
328	return R_RdErr;
329
330	//
331	// Make sure buffer size is big enough, and a multiple of the
332	// B-Tree node size
333	//
334	bufferSize = (kCatScanBufferSize / btcb->nodeSize) * btcb->nodeSize;
335
336	//
337	// Set up the scanner's state
338	//
339	scanState->bufferSize = bufferSize;
340	scanState->bufferPtr = (void *) AllocateMemory( bufferSize );
341	if ( scanState->bufferPtr == NULL )
342	return( R_NoMem );
343
344	scanState->btcb = btcb;
345	scanState->nodeNum = 0;
346	scanState->recordNum = 0;
347	scanState->currentNodePtr = NULL;
348	scanState->nodesLeftInBuffer = 0; // no nodes currently in buffer
349	scanState->recordsFound = 0;
350
351	return noErr;
352
353	} /* BTScanInitialize */
354
355
356	//_________________________________________________________________________________
357	//
358	// Routine: BTScanTerminate
359	//
360	// Purpose: Return state information about a scan so that it can be resumed
361	// later via BTScanInitialize.
362	//
363	// Inputs:
364	// scanState Scanner's current state
365	//
366	// Outputs:
367	// nextNode Node number to resume a scan (pass to BTScanInitialize)
368	// nextRecord Record number to resume a scan (pass to BTScanInitialize)
369	// recordsFound Valid records seen so far (pass to BTScanInitialize)
370	//_________________________________________________________________________________
371
372	int BTScanTerminate( BTScanState * scanState )
373	{
374	if ( scanState->bufferPtr != NULL )
375	{
376	DisposeMemory( scanState->bufferPtr );
377	scanState->bufferPtr = NULL;
378	scanState->currentNodePtr = NULL;
379	}
380
381	return noErr;
382
383	} /* BTScanTerminate */
384
385