From: aep@world.std.com (Andrew E Page)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Directory Scan Revisited dirscan.c (C Code)
Date: 2 Sep 92 19:04:54 GMT
Organization: The World Public Access UNIX, Brookline, MA

Here is the directory scanning code.  Written under MPW 3.2.

--------CUT HERE------------------------------------------------CUT HERE------

#ifdef USE_PRECOMPILE
#pragma load ":Headers:dirscanh.hpc"
#endif

#ifndef __ERRORS__
#include <Errors.h>
#endif
#ifndef __FILES__
#include <Files.h>
#endif
#ifndef __MEMORY__
#include <Memory.h>
#endif
#ifndef __TOOLUTILS__
#include <ToolUtils.h>
#endif
#ifndef __DIRSCAN__
#include <dirscanh.h>
#endif

#ifdef PRECOMPILE
#undef PRECOMPILE
#pragma dump ":Headers:dirscanh.hpc"
#endif

/*

  dirscan.c by Andrew E. Page.    Macintosh Directory Scanning Code
  The code operates as follows. 

  At the start of the scan StartScan accepts the directory in
  which to start.  It initializes all the structures, starting
  the scan in the directory at index 1, which is the first file
  in the given directory.  For each call to GetNextScanFile the
  file information for the current index is fetched, and the index
  is incremented by one.  The entry is checked to see if it is
  a directory.	If so the current state of the scan, the current
  directory being scanned and the index for the next file, is pushed
  onto a 'stack', and a recursive call to GetNextScanFile is made.	


  If PBGetCatInfo returns a "File Not Found" error (-43 fnfErr) 
  occurs during the scan the state of the stack is checked.  If
  the stack is 'empty' (n_stackEntries == 0) then the scan is
  at the top of the directory tree and has accessed the last
  file, and the tree is exhasted.  Any other error should cause
  the termination of the scan (this depends on how the code is
  being used at a higher level however).
  If the stack is not empty then the last entry is 'popped' off
  of the stack and scanning resumes at that level.


Example:

Consider the following directory tree.	With the vRefNum for <startdir>
passed to StartScan, the files would be returned in the following
order.	

file1a file1b file3a file3b file2a file2b file1c file4a

					 <startdir>
						 |
						 |
						 |
  file1a	file1b	 <dir1a>   file1c	<dir1b>
						|				   |
						|				   |
						|				   |
			  <dir2a> file2a file2b 	   |
				 |						   |
				 |						   |
				 |						   |
		   file3a file3b				   |
										   |
										   |
										file4a
					


*/


typedef struct {
  long	dirID ; // the reference for the directory
  short index ;  // what index it stopped scanning at
  } StackEntry_t ;

typedef struct {
  /*
  * these fields provide
  * control over the 'stack'.  Which
  * saves the state of the scan from one
  * level to the next.	
  */
  StackEntry_t	**entries ; 	  // container for the entries
  long			n_stackEntries ;  // number of entries currently in stack
  long			maxStackEntries ; // maximum entries stack can hold
  long			level ; 		  // directory level we've decended to

  /*
  * Storage space for the Parameter Block record.  This allows
  * us to recycle certain fields without having to constantely
  * reinitialize them.	
  */
  CInfoPBRec	F ; 			  // CInfo Rec ref IM IV-125

  /*
  * filtering parameters
  */
  short 	  doFiltering ; 	  // is filtering necessary?
  int		  numTypes ;		  // number of OSTypes to check for
  OSType	  *TypeList ;		  // List of the types to check

  pascal Boolean (*filter)(FileParam *f) ; // filter function to be called for each file

  } ScanControl_t ;

/*
*  We start off with a stack with a capacity for 32 entries.  Allowing
*  us to descend 32 levels without having to reallocate any more memory.
*  That should be sufficient for most applications.  However, more
*  memory will be allocated if need be.  Each allocation will only
*  require 192 additional bytes.
*
*  Season to taste here, just so long as STACK_BLOCK_INCREMENT >= 1
*/
#define STACK_BLOCK_INCREMENT 32

/*
* This is an internal function, hence the static qualifier. 
* This provides the "push" or store function of a standard LIFO(Last In First Out)
* queue.  Otherwise called a 'stack'.
*
*	Each time that it is called it stores the entry, in our case the directory
* ID where the scan is 'branching' from, and the index in that directory where the
* branch is taken, stores them in the container, and then increments the stack
* pointer by one to make room for the next entry.  This differs slightly from the
* nature of the 68XXX stack in as much as for a 68XXX stack the pointer is
* predecremented to make space for the new entry.
*
*	 Entries are retrieved from this stack with the PopFromStack function.	
*/
static PushToStack(ScanControl_t *SC, long dirID, short index)
{

  if( SC->n_stackEntries == SC->maxStackEntries )
	{
	/*
	* Make room for more entries
	*/
	SC->maxStackEntries += STACK_BLOCK_INCREMENT ;
	SetHandleSize((Handle)SC->entries, sizeof(StackEntry_t) * SC->maxStackEntries) ;
	}
	
  /*
  * put the entry on the stack
  */

  (*(SC->entries))[SC->n_stackEntries].dirID = dirID ;
  (*(SC->entries))[SC->n_stackEntries].index = index ;

  SC->n_stackEntries += 1 ;
  SC->level += 1 ;

} /* end of PushToStack */

/*
* This is an internal function, hence the static qualifier. 
* This provides the "pop" or retrieve function of a standard LIFO(Last In First Out)
* queue.  Otherwise called a 'stack'.
*
*  Each time that it is called it restores the state of the scan from where
* it had 'branched' in descending to another directory level.  It starts by
* decrementing the 'stack pointer' so that it points at the last entry that was
* placed on the stack by the PushToStack function.	
*/
static PopFromStack(ScanControl_t *SC, long *dirID, short *index)
{

  SC->n_stackEntries -= 1 ; 
  SC->level -= 1 ;

  *index = (*(SC->entries))[SC->n_stackEntries].index ;
  *dirID = (*(SC->entries))[SC->n_stackEntries].dirID ;

} /* end of PopFromStack */

#ifndef FALSE
#define FALSE 0
#define TRUE 1
#endif

/*
* This internal function determines whether or not this is a type
* of file that we are looking for.	It first checks the files 'type'
* against the list of types provided by the user, or simply passes it
* on if the numTypes was specified as -1.
*  If it succeeds in passing that check it then executes the 'filter' function
* if supplied by the caller.
*/
static Boolean doFilter(ScanControl_t *SC, FileParam *f)
{
int i ;
short isType = FALSE ;

  /*
  * check against types
  */

  if( SC->numTypes != -1 )
	{
	for( i = 0 ; i < SC->numTypes ; i++ )
	  {
	  if( SC->TypeList[i] == f->ioFlFndrInfo.fdType )
		{
		isType = TRUE ;
		break ;
		}
	  }
	/*
	* Is this one of the file types that we are looking for?
	* if not then exclude it from the list. 
	*/
	if( !isType )
	  return TRUE ;
	}

  /*
  * Perform any additional filtering with the
  * filter proc specified by the caller.
  */
  if( SC->filter )
	return (*SC->filter)(f) ;


  /*
  * Otherwise if we've reached this point
  * we do not want this filtered from the list
  */
  return FALSE ;

}


/*
*  This is essentially the core starting routine.  It will also be used
* when starting a scan with a WDVRef instead of a ioDirID.	
*
*  Initializes all the fields necessary, setting up the Parameter
* block for subsequent calls to GetNextDirScanFile. 
*
*  Sets up the Stack's controlling data structures, initializing the stack
* pointer to 0 and allocating an initial block of entries.	
*
*  Does some pre-filter checks to optimize for the case where no filtering
* is required.	It copies the TypeList to ensure that the data remains
* valid if this function is being called from a routine where the TypeList
* may reside in the stack frame that may be deallocated before calls to
* GetNextScanFile.	
*
*/
Ptr StartDirScanDirID(short volRef, long dirID, int numTypes, OSType *TypeList, pascal Boolean (*filter)(FileParam *f))
{
ScanControl_t *SC ;
StackEntry_t **entries ;
OSType *theTypes ;
long len ;

  /*
  * Setup the control structure(s)
  * At each allocation check to ensure that we
  * got the space asked for.  If not, deallocate any
  * previous allocated memory and return a 0L, indictating
  * that the setup failed.	
  */

  /*
  * Check to see if the caller has provided a type list.
  * This will be the case if numTypes is > 0.
  * If so copy the list to ensure that it remains valid.
  */
  if( numTypes > 0 )
	{
	/*
	* Make space for the copy of the TypeList.	
	*/
	theTypes = (OSType *)NewPtr(len = numTypes * sizeof(OSType)) ; // ref IM I-75
	if( theTypes == 0L )
	  return 0L ;
	/*
	* copy the scan types	
	*/
	BlockMove(TypeList, theTypes, len) ; // ref IM II-44
	}
  else
	theTypes = 0L ;
	
  /*
  * Allocate space for the stack.  Start off with STACK_BLOCK_INCREMENT
  * entries.  More can be added later if necessary. 
  */
  entries = (StackEntry_t **)NewHandle(sizeof(StackEntry_t) * STACK_BLOCK_INCREMENT) ; // ref IM I-76
  if( entries == 0L )
	{
	DisposPtr((Ptr)theTypes) ; // ref IM I-75
	return 0L ;
	}

  /*
  * Allocate space for the overal control structure that
  * will be passed back to the caller.	
  */
  SC = (ScanControl_t *)NewPtr(sizeof(ScanControl_t)) ; // ref IM I-75
  if( SC == 0L )
	{
	DisposPtr((Ptr)theTypes) ; // ref IM I-75
	DisposHandle((Handle)entries) ;
	return 0L ;
	}
	
  /*
  * Setup the filtering
  */

  if( (numTypes > 0) || (filter != 0L) )
	{
	SC->doFiltering = TRUE ;
	SC->numTypes = numTypes ;
	SC->TypeList = theTypes ;
	SC->filter = filter ;
	}
  else
	{
	SC->TypeList = 0L ;
	SC->doFiltering = FALSE ;
	}
	
  /*
  * initialize the current
  * state of the scan
  */

  SC->entries = entries ;
  SC->n_stackEntries = 0 ;
  SC->maxStackEntries = STACK_BLOCK_INCREMENT ;
  SC->level = 0 ;

  /*
  * Setup the initial PB Rec  ref IM IV-125
  */

  SC->F.hFileInfo.ioCompletion = 0L ; // always initialize this field!
  SC->F.hFileInfo.ioFlParID = dirID ; // Parent dirtory to start scan in.
  SC->F.hFileInfo.ioVRefNum = volRef ;// true volume reference number
  SC->F.hFileInfo.ioFDirIndex = 0 ;   // initial scanning index.  (will be incremented for each call)

  return (Ptr)SC ;

} /* end of StartDirScanDirID */

/*
*  This call allows us to start off with a WDVRef that may have been
* returned from SFGetFile.	It returns in volRef the true volume
* reference for the volume where the working directory passed in
* vRef resides. 
*/
Ptr StartDirScanWDVRef(short vRef, short *volRef, int numTypes, OSType *TypeList, pascal Boolean (*filter)(FileParam *f))
{
OSErr err ;
WDPBRec wd ;

  /*
  * Setup the the wd parameter block
  */

  wd.ioCompletion = 0L ;
  wd.ioNamePtr = 0L ;
  wd.ioVRefNum = vRef ;
  wd.ioWDIndex = 0 ;

  /*
  * obtain the WD info
  */

  err = PBGetWDInfo(&wd, FALSE) ;
  if( err )
	return 0L ;
	
  *volRef = wd.ioWDVRefNum ; /* the true volume reference number */

  /*
  * use StartDirScanDirID to initialize the scan.
  */
  return StartDirScanDirID(wd.ioWDVRefNum, wd.ioWDDirID, numTypes, TypeList, filter) ;
	
} /* end of StartDirScan */


/*
* This function is essentially the core of the system.	Each call to this function
* will produce a file, or an fnfErr when the scan is completed.  Any other error is 
* an indication of something else being terribly wrong.
*
*  At each call the function will do the following:
*
*	 1.  Increment the index of the file that is currently pointing at.
*
*	 2.  Get the file's catalog information with PBGetCatInfo.
*
*	 3.  If the file is a directory it will save the state of the scan on the
*		 internal stack, and make a recursive call to itself to the next level. 
*
*	 4.  If PBGetCatInfo returns with a File Not Find Error (fnfErr -43), it pops
*		 the last entry off of the stack, restoring the state of the scan and makes
*		 a recursive call to itself to return to the previous level.  If the stack
*		 at this point is empty it returns the fnfErr to the caller indicating that
*		 the scan has completed.
*
*	 5.  If the file entry is not a directory it checks it against the types and
*		 filter function specified by the caller.  If it is rejected by the filter, 
*		 (when it returns TRUE) GetNextDirScanFile repeats steps 1 through 4.
*/
OSErr GetNextDirScanFile(Ptr scanPtr, char *fName, long *dirID, long *level)
{
ScanControl_t *SC = (ScanControl_t *)scanPtr ;
OSErr err ;
short flag = FALSE ;
long parID = SC->F.hFileInfo.ioFlParID ;

  SC->F.hFileInfo.ioNamePtr = fName ;

  do {
	SC->F.hFileInfo.ioFDirIndex++ ;
	SC->F.hFileInfo.ioDirID = parID ;
	err = PBGetCatInfo(&SC->F, FALSE) ;
	if( err )
	  {
	  /*
	  * Anything other than a fnfErr, or a noErr is an inidcation
	  * of some catastrophic failure and that the scan cannot procede.
	  */
	  if( err != fnfErr )
		return err ;
		
	  /*
	  * if there is an fnfErr and there are no more stack entries, this means
	  * that the tree that is being searched has been exhausted.  Returning
	  * the fnfErr at this point should terminate the scan by the caller.
	  */
	  if( SC->n_stackEntries == 0 )
		return err ;
	
	  /*
	  * if it is a fnfErr, and entries remain in the stack, we have exhausted
	  * the file entries at this level and need to return to the previous level
	  * and resuming scanning where  we left off.  To do this we Pop the previous
	  * state of the scan  off of the stack, and make a recursive call to GetNextDirScanFile.
	  */
	  PopFromStack(SC, &SC->F.hFileInfo.ioFlParID, &SC->F.hFileInfo.ioFDirIndex) ;
			
	  return GetNextDirScanFile((Ptr)SC, fName, dirID, level) ;
	  }

	if( SC->F.hFileInfo.ioFlAttrib & 0x10 ) // check for directory flag
	  {
	  /*
	  * Save the state of the scan
	  * at the current level.
	  */
	  PushToStack(SC, SC->F.dirInfo.ioDrParID, SC->F.hFileInfo.ioFDirIndex) ;
	
	  /*
	  * Setup the the state of the next level to be
	  * the directory that we just found.  Starting at the
	  * first file index.
	  */
	  SC->F.hFileInfo.ioFlParID = SC->F.dirInfo.ioDrDirID ;
	  SC->F.hFileInfo.ioFDirIndex = 0 ;
	
	  return GetNextDirScanFile((Ptr)SC, fName, dirID, level) ;
	  }

	/*
	* if necessary check to see if we should filter
	* out this file entry.	
	*/
	
	if( SC->doFiltering )
	  flag = doFilter(SC, (FileParam *)&SC->F) ;
	} while( flag ) ; // if file is to be filtered, try another one.
	
  /*
  * Set the directory ID parameter
  */
  *dirID = SC->F.hFileInfo.ioFlParID ;

  /*
  * if the caller wants the level of this file set it.
  */
  if( level )
	*level = SC->level ;
	
  return err ;

} /* end of GetNextDirScanFile */


/*
* This terminates the scan.  What is actually does is release
* all the memory that was allocated.  Since no new working
* directories were created there is no need to call PBCloseWD.
*/
OSErr StopDirScan(Ptr scanPtr)
{
ScanControl_t *SC = (ScanControl_t *)scanPtr ;

  if( SC->TypeList )
	DisposPtr((Ptr)SC->TypeList) ;

  DisposHandle((Handle)SC->entries) ;
  DisposPtr(scanPtr) ;

  /*
  * Although it is unlikely that we will have comitted
  * any errors provide this check to the caller.
  */
  return MemError() ;
}

/*
*
* This function will generate a full pathname to
* the file identified by its name, volume, and directory ID.
* The result is a handle that contains the full pathname of the
* file and is sized to fit that pathname exactly.  It contains
* No length byte or null terminator.  The length of the string can
* be determined with GetHandleSize. 
*
*
* The function operates as a loop.	At each interation through the
* the loop it gets the catalog name for the entry.	Each time
* making the parent directory for that entry the target for the
* next cycle.  This proceeds until it hits the root directory
* is reached, which has no logical parent, and thus PBGetCatInfo
* returned a file not found error(-43 fnfErr).
*
*	 We use a handle since this allows us to use the
* Munger string manipulator.
*
*/

Handle FullPathNameID(char *fName, int vRef, long dirID)
{
Handle theString = NewHandle(0) ; /* container for the string */
CInfoPBRec F ;
short err ;
char colon = ':' ; /* just in case you want to put it into a stand alone code resource */
char string[64] ;

  /*
  * For safety sake(to ensure that our string contains enough space for 
  * subsequent entries found, and to make sure that we don't overwrite
  * the input string, we copy the input fileName to our own storage.
  */

  BlockMove(fName, string, fName[0]+1) ; // ref IM II-44

  /*
  * Initialize the PB fields
  */

  F.hFileInfo.ioNamePtr = string ;	/* pascal string for the name, and also subsequent storage on calls */
  F.hFileInfo.ioVRefNum = vRef ;  /* volume reference (Gotten from SFGetFile perhaps */
  F.hFileInfo.ioCompletion = 0L ; /* initialize this field or get a Serious BOMB */
  F.hFileInfo.ioFDirIndex = 0 ;   /* for the first call only.  Get CatInfo based on ioNamePtr, ioVRefNum, and dirID */
  F.hFileInfo.ioDirID = dirID ;   /* directory containing this file */

  while( !(err = PBGetCatInfo(&F,0)) )
	{
	/*
	* Insert the directory level into the front of the string
	*/
	Munger(theString, 0, 0L, 0, &string[1], string[0]) ; // ref IM I-468

	/*
	* Insert a colon in front of the Directory Entry
	*/
	Munger(theString, 0, 0L, 0, &colon, 1) ; // ref IM I-468

	/*
	* We now wish to get the information about
	* the directory that contains this file/directory.
	* in short we are moving one level UP in the heirarchy
	*/
	F.dirInfo.ioDrDirID = F.dirInfo.ioDrParID ; /* get the ioDrDirID of the PARENT directory (the next level up) */
	
	/*
	* Setting this field to < 0 will
	* cause PBGetCatInfo to get the catalog
	* information based on the VRef and dirID
	* that we've placed in F.dirInfo.ioDrDirID,
	* and return the name of the entry in the
	* pointer to the string in ioNamePtr.
	*/
	F.hFileInfo.ioFDirIndex = -1 ;
	}
	
  /*
  * The last entry will be the Volume name which should not have a colon in front of it
  */
	
  Munger(theString, 0, 0L, 1, string, 0) ;

  return theString ;
}


-- 
Andrew E. Page CTO(Warrior Poet)|   Decision and Effort The Archer and Arrow
DSP Ironworks                   |     The difference between what we are
Macintosh and DSP Technology    |           and what we want to be.