Minimizing Stack Require- ments When Searching the NetWare File System
Articles and Tips: tip
Software Engineer
Novell India Development Center
kvenkatram@novell.com
01 Apr 2003
Algorithms for searching and sorting recursively- defined data structures (like trees) nearly always use recursion. The problem with recursive algorithms is that the stack requirements are limited only by the size of the data structure to be searched, which cannot be known until runtime. It is not uncommon for a search of a large directory tree to consume large amounts of memory to the point of affecting system performance or to cause a stack overflow.
The example source code shown below illustrates an algorithm for searching the NetWare file system that minimizes stack requirements. This algorithm has the properties that there is no function level recursion, hence the only stack usage is to pass parameters to functions one level deep. The algorithm stores the handle/DTA for each subdirectory as it proceeds deeper into the tree, so as it returns it can continue from where it left off.
However, the algorithm does not store the complete subdirectory listing of each subdirectory along the way. This means a given directory can have as many subdirectories as it wants, and the search algorithm will handle them. This approach comes, however, at some cost of speed, as each directory is scanned twice (once to count subdirectories, and once to display each subdirectory) and the second scanning will probably not use sequential reads.
The algorithm can handle as many subdirectories deep as there is memory to store the subdirinfo structures. Each structure is potentially MAX_DIR_PATH + sizeof(long) + sizeof(DIRHANDLE) bytes. The actual implementation has a depth limit defined by the maximum path length. This can handle any number of files in a directory. If filenames are displayed when each subdirectory is first entered (thus there is only a single additional search of the directory for showing files), the directory is searched and all files matching the search attribute criteria are shown.
Note: A faster approach would be to add all the subdirectories in a given directory when we first process it, then pop the top one off, display it and possibly its files, then repeat the process of scanning for subdirectories and adding any found. However, this limits the recursion to the number of subdirectory names that can be stored in memory. A directory with many subdirectories would take up a lot of space, reducing maximum depth.
The code below is one file in a complete, compilable NLM example program. Other files in the project implement stack handling functions and the program's main routine. You can download the complete source for the program inscan.zip from http://www.novell.com/coolsolutions/tools/15535.html.
#include <string.h> #include <stdio.h> #include <stdlib.h> #include <nwthread.h> #include <dirent.h> #include <nwfile.h> #include "stack.h"
// Type-defs and other definitions #define DEBUG 1 #define FILEEXT_OTHER 10 #define FILEEXT_EXE 12 #define FILEEXT_DLL 13 #define FALSE 0 #define TRUE 1 #define MAX_DIR_PATH 512 //Nesting Depth
typedef void *DIRHANDLE ;
typedef struct tagsubdirinfo {
char currentPath[MAX_DIR_PATH] ;
long subdircnt ;
DIRHANDLE findnexthnd ;
} SUBDIRINFO ;
int exitFlag ;
// Forward declarations intRetrieveFileExtension ( char * pszFileName ) ;
unsigned int getSubDirCount ( char * currentPath )
{
unsigned int
count = 0 ;
DIR *psFind = NULL ,
*pDir = NULL ;
char szFileName[MAX_DIR_PATH] ;
char szCurrentPath[MAX_DIR_PATH] ;
if ( currentPath == NULL )
return 0 ;
strcpy ( szCurrentPath, currentPath ) ;
strcat ( szCurrentPath, "\\*.*" ) ;
pDir = opendir( szCurrentPath );
if ( pDir != NULL ) {
// readdir count for directory only
while ( (psFind = readdir(pDir)) != NULL && !exitFlag ) {
ThreadSwitch() ;
strcpy ( szFileName, currentPath ) ;
strcat ( szFileName, "\\" ) ;
strcat ( szFileName, psFind->d_name );
// Check if file is a directory. If not '.' or '..' continue
if( psFind->d_attr & _A_SUBDIR ) {
if( strcmp( psFind->d_name,".") && strcmp( psFind->d_name,".." ) )
{
#ifdef DEBUG
printf ("Directory %s.\n", szFileName ) ;
#endif
count++ ;
}
}
}
closedir(pDir) ;
}
return count ;
}
DIRHANDLE findFirstSubDir( char *currentPath, char *newcurrentPath )
{
DIRHANDLE handle = NULL ;
DIR *psFind = NULL ,
*pDir = NULL ;
SBOOLEAN findFirst = FALSE ;
char szFileName[MAX_DIR_PATH] ;
char szCurrentPath[MAX_DIR_PATH] ;
strcpy ( szCurrentPath, currentPath ) ;
strcat ( szCurrentPath, "\\*.*" ) ;
pDir = opendir( szCurrentPath );
if ( pDir != NULL ) {
// Set readdir attributes for directory only
while ( (psFind = readdir(pDir)) != NULL ) {
strcpy ( szFileName, currentPath ) ;
strcat ( szFileName, "\\" ) ;
strcat ( szFileName, psFind->d_name );
// Check if file is a directory. If not '.' or '..' continue
if( psFind->d_attr & _A_SUBDIR ) {
if( strcmp( psFind->d_name,".") && strcmp( psFind->d_name,".." ) )
{
strcpy ( newcurrentPath, szFileName ) ;
handle = (DIRHANDLE) pDir ;
findFirst = TRUE ;
break ;
}
}
}
}
return handle ;
}
SBOOLEAN findNextSubDir ( DIRHANDLE findnexthnd, char *currentPath, char
*newcurrentPath )
{
DIR *psFind = NULL ,
*pDir = NULL ;
char szFileName[MAX_DIR_PATH] ;
SBOOLEAN findNext = FALSE ;
if ( findnexthnd != NULL && newcurrentPath != NULL ) {
pDir = (DIR *) findnexthnd ;
if ( pDir != NULL ) {
// Set readdir attributes for directory only
while ( (psFind = readdir(pDir)) != NULL ) {
strcpy ( szFileName, currentPath ) ;
strcat ( szFileName, "\\" ) ;
strcat ( szFileName, psFind->d_name );
// Check if file is a directory.
// If not '.' or '..' continue
if( psFind->d_attr & _A_SUBDIR ) {
if( strcmp( psFind->d_name,".") && strcmp( psFind->d_name,".." ) )
{
strcpy(newcurrentPath, szFileName);
findNext = TRUE ;
break ;
}
}
}
}
}
return findNext ;
}
SBOOLEAN findCloseDir ( DIRHANDLE findnexthnd )
{
SBOOLEAN close = TRUE ;
DIR *pDir = NULL ;
if ( findnexthnd == NULL )
return FALSE ;
pDir = (DIR *) findnexthnd ;
closedir(pDir) ;
return close ;
}
SUBDIRINFO *newSubDirInfo ( char * currentPath )
{
SUBDIRINFO *temp = NULL ;
if ( currentPath != NULL ) {
temp = ( SUBDIRINFO *) malloc ( sizeof(SUBDIRINFO ) ) ;
if ( temp != NULL ) {
strcpy(temp->currentPath, currentPath ) ;
temp->subdircnt = getSubDirCount ( currentPath ) ;
temp->findnexthnd = NULL ;
#ifdef DEBUG
printf ( "Path=%s, Count=%d\n", temp->currentPath, temp->subdircnt ) ;
#endif
}
}
return temp ;
}
SBOOLEAN enumFilesNonRecurse ( char *currentPath )
{
int fileExt = 0 ;
SBOOLEAN enumFiles = TRUE ;
DIR *psFind = NULL ,
*pDir = NULL ;
char szFileName[MAX_DIR_PATH] ;
char szCurrentPath[MAX_DIR_PATH] ;
strcpy ( szCurrentPath, currentPath ) ;
strcat ( szCurrentPath, "\\*.*" ) ;
pDir = opendir( szCurrentPath );
if ( pDir != NULL ) {
while ( (psFind = readdir(pDir)) != NULL ) {
strcpy ( szFileName, currentPath ) ;
strcat ( szFileName, "\\" ) ;
strcat ( szFileName, psFind->d_name );
// Check if file is a not directory, not '.' or '..'
if( !(psFind->d_attr & _A_SUBDIR) )
{
if( strcmp( psFind->d_name,".") &&
strcmp( psFind->d_name,".." ) )
{
// Retrieve file extension
fileExt = RetrieveFileExtension(psFind->d_name);
#ifdef DEBUG
printf ("%s\n", szFileName ) ;
#endif
}
}
}
closedir(pDir) ;
}
else
enumFiles = FALSE ;
return enumFiles ;
}
SBOOLEAN enumDirNonRecurse ( int volume, char * initialPath , SBOOLEAN showFiles )
{
STACK s ;
SUBDIRINFO *initialSdi = NULL ,
*sdi = NULL ,
*sdiNew = NULL ;
char *ptr = NULL ;
char newcurrentPath[MAX_DIR_PATH] ;
SBOOLEAN enumDir = FALSE ;
// typically increment a counter such as WorkThreadCounter++ ;
Empty(&s) ;
initialSdi = newSubDirInfo ( initialPath ) ;
if ( initialSdi == NULL )
return FALSE ;
enumDir = Push(&s,(ELEMENT)initialSdi) ;
do {
sdi = (SUBDIRINFO *) Pop(&s) ;
if ( sdi != NULL )
{
// Conditional check
if ( sdi->findnexthnd == NULL ) {
// First time
if ( showFiles ) {
printf("%s\n", sdi->currentPath);
enumFilesNonRecurse (sdi->currentPath);
}
}
if ( sdi->subdircnt > 0 ) {
sdi->subdircnt-- ;
newcurrentPath[0] = '\0' ;
if ( sdi->findnexthnd == NULL ) {
if ( !exitFlag )
sdi->findnexthnd =
findFirstSubDir(sdi->currentPath,newcurrentPath ) ;
else
break ;
}
else {
if ( !exitFlag ) {
enumDir =
findNextSubDir(sdi->findnexthnd,
sdi->currentPath, newcurrentPath );
if ( enumDir == FALSE )
continue ;
}
else
break ;
}
enumDir = Push (&s, sdi) ;
// Process error
if ( enumDir == FALSE )
goto EXIT_ENUMDIR ;
sdiNew = newSubDirInfo ( newcurrentPath ) ;
if ( sdiNew != NULL )
{
enumDir = Push(&s, (ELEMENT) sdiNew) ;
// Process error
if ( enumDir == FALSE )
goto EXIT_ENUMDIR ;
}
}
else
{
strcpy ( newcurrentPath, sdi->currentPath ) ;
findCloseDir ( sdi->findnexthnd ) ;
free ( sdi ) ;
}
}
} while ( IsEmpty(&s) == FALSE && !exitFlag ) ;
EXIT_ENUMDIR :
if ( exitFlag )
{
// Do the necessary cleanUp
while ( IsEmpty(&s) == FALSE )
{
sdi = (SUBDIRINFO *) Pop(&s) ;
if ( sdi != NULL )
{
// Conditional check
if ( sdi->findnexthnd != NULL )
{
findCloseDir(sdi->findnexthnd) ;
}
free ( sdi ) ;
}
}
}
//typically decrement counter such as WorkThreadCounter-- ;
return TRUE ;
}
int RetrieveFileExtension ( char * pszFileName )
{
int fileExt = FILEEXT_OTHER ;
char szFileName[256] ,
szFileExt[12] ;
char *ptr = NULL ;
strcpy ( szFileName, pszFileName ) ;
ptr = strrchr ( szFileName, '.' ) ;
if ( ptr )
{
ptr++ ;
strcpy ( szFileExt, ptr ) ;
if ( !stricmp ( szFileExt, "EXE" ) )
fileExt = FILEEXT_EXE ;
else
if ( !stricmp ( szFileExt, "DLL" ) )
fileExt = FILEEXT_DLL ;
}
return fileExt ;
}
* Originally published in Novell AppNotes
Disclaimer
The origin of this information may be internal or external to Novell. While Novell makes all reasonable efforts to verify this information, Novell does not make explicit or implied claims to its validity.