Updating algorithm for directory scanning.

1 files changed, 250 insertions, 147 deletions

diff --git a/src/recurse.c b/src/recurse.c
index 8a1c0cc..959a141 100644
--- a/src/recurse.c
+++ b/src/recurse.c
@@ -1,7 +1,54 @@
 /*
- *   Recursively list files in a directory.
+ *
+ *  DMS Tools and Utilities
+ *  Copyright (C) 2008 David M. Syzdek <david@syzdek.net>.
+ *
+ *  @SYZDEK_LICENSE_HEADER_START@
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License Version 2 as
+ *  published by the Free Software Foundation.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ *  @SYZDEK_LICENSE_HEADER_END@
  */
+/**
+ *  @file src/recurse.c  simple recursive directory listing utility
+ */
+/*
+ *  Simple Build:
+ *     gcc -W -Wall -O2 -c recurse.c
+ *     gcc -W -Wall -O2 -o recurse   recurse.o
+ *
+ *  GNU Libtool Build:
+ *     libtool --mode=compile gcc -W -Wall -g -O2 -c recurse.c
+ *     libtool --mode=link    gcc -W -Wall -g -O2 -o recurse recurse.lo
+ *
+ *  GNU Libtool Install:
+ *     libtool --mode=install install -c recurse /usr/local/bin/recurse
+ *
+ *  GNU Libtool Clean:
+ *     libtool --mode=clean rm -f recurse.lo recurse
+ */
+#define _DMSTOOLS_SRC_RECURSE_C 1
 
+///////////////
+//           //
+//  Headers  //
+//           //
+///////////////
+
+#ifdef HAVE_COMMON_H
+#include "common.h"
+#endif
 
 #include <stdio.h>
 #include <stdlib.h>
@@ -11,6 +58,15 @@
 #include <sys/stat.h>
 #include <dirent.h>
 
+///////////////////
+//               //
+//  Definitions  //
+//               //
+///////////////////
+
+#ifndef PACKAGE_BUGREPORT
+#define PACKAGE_BUGREPORT "david@syzdek.net"
+#endif
 #ifndef PACKAGE_NAME
 #define PACKAGE_NAME "Directory Recusring Tool"
 #endif
@@ -29,34 +85,48 @@
 #define MY_OPT_LINKS       0x20
 #define MY_OPT_QUIET       0x40
 
-//typedef struct recurse_data Recurse;
-//struct recurse_data
-//{
-//   char ** 
-//};
 
+//////////////////
+//              //
+//  Prototypes  //
+//              //
+//////////////////
 
 int main(int argc, char * argv[]);
+
 void my_version(void);
+
 void my_usage(void);
-int recurse_directory(int * lenp, char *** listp, int opts);
-int recurse_list(const char * src, int opts);
 
+int my_work(const char * file, void * data);
 
+int recurse_directory(char * origin, int opts, void * data,
+   int (*func)(const char * file, int opts, void * data));
+
+int recurse_file(const char * file, int opts, void * data,
+   int (*func)(const char * file, int opts, void * data), unsigned * countp,
+   char *** queuep, unsigned * sizep);
+
+
+/////////////////
+//             //
+//  Functions  //
+//             //
+/////////////////
 
 int main(int argc, char * argv[])
 {
    int        c;
    int        i;
-   int        err;
+   //int        err;
    int        opts;
    int        option_index;
    int        len;
-   void     * ptr;
+   //void     * ptr;
    char    ** list;
 
-   static char   short_options[] = "achLqrvV";
-   static struct option long_options[] = 
+   static char   short_options[] = "acfhLqrvV";
+   static struct option long_options[] =
    {
       {"help",          no_argument, 0, 'h'},
       {"quiet",         no_argument, 0, 'q'},
@@ -123,42 +193,20 @@ int main(int argc, char * argv[])
    };
 
    for(i = optind; i < argc; i++)
-   {
-/*
-      len++;
-      if (!(ptr = realloc(list, (sizeof(char *)*len))))
-      {
-         fprintf(stderr, "out of virtual memory\n");
-         for(i = 0; i < (len-1); i++)
-            free(list[0]);
-         free(list);
-         return(1);
-      };
-      list = ptr;
-      if (!(list[len-1] = strdup(argv[i])))
+      switch (recurse_directory(argv[i], opts, NULL, NULL))
       {
-         fprintf(stderr, "out of virtual memory\n");
-         for(i = 0; i < (len-1); i++)
-            free(list[0]);
-         free(list);
-         return(1);
+         case -1: return(1);
+         case 0:  break;
+         default:
+            if (!(opts & MY_OPT_CONTINUE))
+               return(1);
+            break;
       };
-*/
-      if ((recurse_list(argv[i], opts)))
-         return(1);
-   };
-
-   err = recurse_list(&len, &list, opts);
-
-   for(i = 0; i < len; i++)
-      free(list[i]);
-   free(list);
-
-   return(err);
+   return(0);
 }
 
 
-/* displays usage */
+// displays usage
 void my_usage(void)
 {
    printf("Usage: %s [OPTIONS] file1 file2 ... fileN\n", PROGRAM_NAME);
@@ -194,137 +242,192 @@ void my_version(void)
 }
 
 
-int recurse_directory(int * lenp, char *** listp, int opts)
+int recurse_directory(char * origin, int opts, void * data,
+   int (*func)(const char * file, int opts, void * data))
 {
    int             err;
    DIR           * d;
-   void          * ptr;
-   char          * dir;
    char          * file;
-   size_t          dir_len;
-   size_t          file_len;
-   struct stat     sb;
+   char         ** queue;
+   void          * ptr;
+   size_t          len_dir;
+   size_t          len_file;
+   unsigned        size;
+   unsigned        count;
    struct dirent * dp;
 
-   // points to directory name
-   if (!(dir = (*listp)[(*lenp)-1]))
-      return(0);
-   //(*listp)[(*lenp)-1] = NULL;
-   //(*lenp)--;
-   
-   // opens directory for reading
-   if (!(d = opendir(dir)))
-   {
-      if (opts & MY_OPT_QUIET)
-         fprintf(stderr, "%s: %s, %s\n", PROGRAM_NAME, dir, strerror(errno) );
-      free(dir);
-      (*listp)[(*lenp)-1] = NULL;
-      if (!(opts & MY_OPT_CONTINUE))
-         return(0);
-   };
+   size  = 0;
+   count = 0;
+   ptr   = NULL;
+   queue = NULL;
+
+   // seeds queue with first file/directory
+   if ((err = recurse_file(origin, opts, data, func, &count, &queue, &size)))
+      return(err);
 
-   // loops through directory
-   for(dp = readdir(d); dp; dp = readdir(d))
+   if (!(opts & MY_OPT_RECURSE))
    {
-      // skips hidden files, current directory, and parent
-      if (dp->d_name[0] == '.')
+      if (queue)
       {
-         if (dp->d_name[1] == '\0')
-            continue;
-         if ( (dp->d_name[1] == '.') && (dp->d_name[2] == '\0') )
-            continue;
-         if (!(opts & MY_OPT_HIDDEN))
-            continue;
+         free(queue[0]);
+         free(queue);
       };
+      return(0);
+   };
 
-      // builds file name
-      dir_len  = strlen(dir);
-      file_len = strlen(dp->d_name);
-      if (!(file = malloc(sizeof(char) * (dir_len + file_len + 2))))
+   while(count)
+   {
+      if (opts & MY_OPT_VERBOSE)
+         printf("%s\n", queue[count-1]);
+
+      // opens directory for processing
+      if (!(d = opendir(queue[count-1])))
       {
-         fprintf(stderr, "%s: out of virtual memory\n", PROGRAM_NAME);
-         free(dir);
-         return(1);
+         if ( ((!(opts & MY_OPT_QUIET))&&(opts & MY_OPT_CONTINUE)) || (!(opts & MY_OPT_CONTINUE)) )
+            fprintf(stderr, "%s: %s: %s\n", PROGRAM_NAME, queue[count-1], strerror(errno));
+         if (!(opts & MY_OPT_CONTINUE))
+            return(1);
       };
-      strcpy(&file[0],         dir);
-      strcpy(&file[dir_len],   "/");
-      strcpy(&file[dir_len+1], dp->d_name);
-      file[dir_len+file_len+1] = '\0';
-
-      // retrieves file information
-      if ((opts & MY_OPT_LINKS))
-         err = stat(file, &sb);
-      else
-         err = lstat(file, &sb);
-      if (err == -1)
-         if (opts & MY_OPT_QUIET)
-            fprintf(stderr, "%s: %s, %s\n", PROGRAM_NAME, file, strerror(errno) );
-
-      // checks file type
-      switch(sb.st_mode & (S_IFDIR|S_IFREG|S_IFLNK))
+
+      len_dir = strlen(queue[count-1]);
+
+      for(dp = readdir(d); dp; dp = readdir(d))
       {
-         case S_IFDIR:
-            if (!(ptr = realloc(*listp, sizeof(char *) * ((*lenp)+1))))
+         len_file = strlen(dp->d_name);
+         if (!(file = malloc(sizeof(char) * (len_dir + len_file + 2))))
+         {
+            fprintf(stderr, "%s: out of virtual memory\n", PROGRAM_NAME);
+            return(-1);
+         };
+         sprintf(file, "%s/%s", queue[count-1], dp->d_name);
+
+         if ( (dp->d_name[0] == '.') && (opts & MY_OPT_HIDDEN) )
+         {
+            if ( (dp->d_name[1] != '/') &&
+                 (dp->d_name[1] != '\0') &&
+                 (dp->d_name[1] != '.') )
             {
-               fprintf(stderr, "%s: out of virtual memory\n", PROGRAM_NAME);
-               free(dir);
-               free(file);
-               closedir(d);
-               return(1);
+               switch (err = recurse_file(file, opts, data, func, &count, &queue, &size))
+               {
+                  case -1:
+                     free(file);
+                     closedir(d);
+                     return(1);
+                  case 0:
+                     free(file);
+                     break;
+                  default:
+                     free(file);
+                     if (!(opts & MY_OPT_CONTINUE))
+                     {
+                        closedir(d);
+                        return(1);
+                     };
+                     break;
+               };
             };
-            *listp = ptr;
-            (*listp)[(*lenp)] = file;
-            (*lenp)++;
-            printf("%s\n", file);
-            break;
-         case S_IFREG:
-            //if (!(opts & MY_OPT_QUIET))
-               printf("%s\n", file);
-            free(file);
-            break;
-         //case S_IFLNK:
-         //   free(file);
-         //   break;
-         default:
-            //if (!( (opts & MY_OPT_QUIET) && (opts & MY_OPT_CONTINUE) ))
-            //   fprintf(stderr, "%s: %s: invalid file type\n", PROGRAM_NAME, file);
-            free(file);
-            //if (!(opts & MY_OPT_CONTINUE))
-            //{
-            //   closedir(d);
-            //   return(1);
-            //};
-            break;
+         }
+         else if (dp->d_name[0] != '.')
+         {
+            switch (err = recurse_file(file, opts, data, func, &count, &queue, &size))
+            {
+               case -1:
+                  free(file);
+                  closedir(d);
+                  return(1);
+               case 0:
+                  free(file);
+                  break;
+               default:
+                  free(file);
+                  if (!(opts & MY_OPT_CONTINUE))
+                  {
+                     closedir(d);
+                     return(1);
+                  };
+                  break;
+            };
+         };
       };
-   };
 
-   closedir(d);
+      // closes directory and removes from queue
+      closedir(d);
+      count--;
+      free(queue[count]);
+   };
 
-   free(dir);
+   free(queue);
 
    return(0);
 }
 
 
-int recurse_list(const char * src, int opts)
+int recurse_file(const char * file, int opts, void * data,
+   int (*func)(const char * file, int opts, void * data), unsigned * countp,
+   char *** queuep, unsigned * sizep)
 {
-   int     len;
-   char ** list;
-   
-   len  = 0;
-   list = NULL;
-   
-   while(len > 0)
+   int             err;
+   void          * ptr;
+   unsigned        u;
+   struct stat     sb;
+
+   if (opts & MY_OPT_LINKS)
+      err = stat(file, &sb);
+   else
+      err = lstat(file, &sb);
+   if (err == -1)
+   {
+      if ( ((!(opts & MY_OPT_QUIET))&&(opts & MY_OPT_CONTINUE)) || (!(opts & MY_OPT_CONTINUE)) )
+         fprintf(stderr, "%s: %s: %s\n", PROGRAM_NAME, file, strerror(errno));
+      return(1);
+   };
+   switch(sb.st_mode & (S_IFDIR|S_IFREG|S_IFLNK))
    {
-      printf("%s\n", list[len-1]);
-      //if ((recurse_directory(lenp, listp, opts)))
-      //   return(1);
-      len--;
-      if (list[len])
-         free(list[len]);
-      list[len] = NULL;
+      case S_IFDIR:
+         // adjust size of array
+         if (*countp >= *sizep)
+         {
+            *sizep += 20;
+            if (!(ptr = realloc(*queuep, sizeof(char *) * (*sizep))))
+            {
+               fprintf(stderr, "%s: out of virtual memory\n", PROGRAM_NAME);
+               return(-1);
+            };
+            *queuep = ptr;
+         };
+
+         // copy path name
+         if (!(ptr = strdup(file)))
+         {
+            fprintf(stderr, "%s: out of virtual memory\n", PROGRAM_NAME);
+            return(-1);
+         };
+
+         // insert path name at head of array
+         for(u = (*countp); u > 0; u--)
+            (*queuep)[u] = (*queuep)[u-1];
+         (*queuep)[0] = ptr;
+         (*countp)++;
+         break;
+
+      case S_IFLNK:  // ignore symbolic links
+         break;
+
+      case S_IFREG:
+         if (opts & MY_OPT_VERBOSE)
+            printf("%s\n", file);
+         if (func)
+            return(func(file, opts, data));
+         break;
+
+      default:
+         if ( ((!(opts & MY_OPT_QUIET))&&(opts & MY_OPT_CONTINUE)) || (!(opts & MY_OPT_CONTINUE)) )
+            fprintf(stderr, "%s: %s: unknown file type\n", PROGRAM_NAME, file);
+         return(1);
+         break;
    };
+
    return(0);
 }
 
-/* end of source file */
+// end of source code