Novell is now a part of Micro Focus

Minimizing Stack Require- ments When Searching the NetWare File System

Articles and Tips: tip

Venkatram K
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.

© Micro Focus