BTreeScanner.c   [plain text]


/*
 * Copyright (c) 1996-2002 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (the
 * "License").  You may not use this file except in compliance with the
 * License.  Please obtain a copy of the License at
 * http://www.apple.com/publicsource and read it before using this file.
 * 
 * This 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 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"

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;
	
	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;

			(u_int8_t *) scanState->currentNodePtr += scanState->btcb->nodeSize;
		}
		
		// Make sure this is a valid node
		err = CheckNode( scanState->btcb, scanState->currentNodePtr );
		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 );
	myErr = CacheRawRead( myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache, 
						  myPhyOffset, myContiguousBytes, theScanStatePtr->bufferPtr );
	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 */