home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume8 / hier / sftw.c < prev   
Encoding:
C/C++ Source or Header  |  1987-02-11  |  14.0 KB  |  536 lines
  1. /*
  2.  * Sorted file tree walk (library routine).
  3.  *
  4.  * Identical (in theory) to ftw(3), except:
  5.  *
  6.  * - Calls user's fn() with the files sorted alphabetically (per strcmp(3))
  7.  *   in two groups:  All non-directories first, followed by directories (with
  8.  *   the descendents of each directory after the directory).  Non-stat'able
  9.  *   files and non-readable directories are included in the second group.
  10.  *
  11.  * - Doesn't keep one file open for each level of recursion, so it doesn't
  12.  *   need a depth argument (which actually affects file opens/closes, NOT
  13.  *   maximum search depth).
  14.  *
  15.  * - Uses a lot more malloc space.
  16.  *
  17.  * - Supports an additional argument which tells it to include all files
  18.  *   and directories, including those whose names start with "." (except that
  19.  *   the given filename is always included, regardless of the flag, like
  20.  *   ls(1)).  The caller could implement this, but not very efficiently.
  21.  *
  22.  * Like ftw(), it ignores "." and ".." files, even with the all flag.
  23.  *
  24.  * For convenience, form of call is:
  25.  *
  26.  *    #include <ftw.h>
  27.  *
  28.  *    int sftw (path, fn, allfiles)
  29.  *        char    *path;
  30.  *        int    (*fn)();
  31.  *        int    allfiles;
  32.  *
  33.  * Form of fn() is:
  34.  *
  35.  *    int fn (name, statp, type)
  36.  *        char    *name;
  37.  *        struct    stat *statp;
  38.  *        int    type;
  39.  *
  40.  * See ftw(3) for more information.
  41.  *
  42.  * Compile with -DTEST to get a runnable test version that walks from "."
  43.  * and tells types, permissions, and filenames passed to fn().
  44.  */
  45.  
  46. #include <sys/types.h>
  47. #include <sys/stat.h>
  48. #include <ftw.h>
  49. #ifdef    BSD
  50. #include <sys/dir.h>
  51. #else
  52. #include <ndir.h>
  53. #endif    /* BSD */
  54.  
  55. static char *malloc(), *strcpy();
  56. static void free();
  57.  
  58.  
  59. /*********************************************************************
  60.  * MISCELLANEOUS GLOBAL VALUES:
  61.  */
  62.  
  63. #define    PROC                /* null; easy to find procs */
  64. #define    FALSE    0
  65. #define    TRUE    1
  66. #define    CHNULL    ('\0')
  67. #define    CPNULL    ((char *) NULL)
  68. #define    REG    register
  69.  
  70. /* built-up filename for passing to the user program; hope it's big enough */
  71. static    char filename [1000];
  72.  
  73. static    unsigned short euid, egid;    /* only get them once */
  74.  
  75.  
  76.  
  77. /************************************************************************
  78.  * FILE DATA STRUCTURE:
  79.  *
  80.  * A contiguous array of pointers is used for sorting, built after knowing
  81.  * how many directory entries there are to sort.  Each entry points to a
  82.  * struct filedata which holds information for one directory entry.
  83.  */
  84.  
  85. typedef    struct filedata *fdpt;
  86. typedef    struct filedata **fdppt;
  87.  
  88. struct filedata {
  89.     char    *name;        /* in malloc'd space    */
  90.     int    type;        /* see ftw.h        */
  91.     struct    stat statbuf;    /* from stat(2)        */
  92. };
  93.  
  94.  
  95. /************************************************************************
  96.  * FILE AND STRING DATA BLOCKS:
  97.  *
  98.  * Since a directory may grow arbitrarily as it's read, there's no way to
  99.  * know in advance how big it is.  And it's necessary to return all malloc'd
  100.  * memory.  To make this possible, and to save malloc space and time, directory
  101.  * entry data and filenames are stored in buffers allocated a chunk a time.
  102.  */
  103.  
  104. #define    DBENTRIES    20    /* file entries per datablock */
  105. #define    STRINGENTRIES 1008    /* chars per string buffer    */
  106.  
  107. typedef    struct datablock *dbpt;
  108. typedef    struct datablock **dbppt;
  109.  
  110. struct datablock {
  111.     dbpt    next;                /* next block if any */
  112.     struct    filedata fd [DBENTRIES];    /* the data itself   */
  113. };
  114.  
  115. #define    DBNULL  ((dbpt) NULL)
  116. #define    DBSIZE  (sizeof (struct datablock))
  117.  
  118.  
  119. typedef struct stringblock *sbpt;
  120. typedef struct stringblock **sbppt;
  121.  
  122. struct stringblock {
  123.     sbpt    next;                /* next block if any */
  124.     char    buf [STRINGENTRIES];        /* the data itself   */
  125. };
  126.  
  127. #define    SBNULL  ((sbpt) NULL)
  128. #define    SBSIZE  (sizeof (struct stringblock))
  129.  
  130.  
  131. /************************************************************************
  132.  * S F T W
  133.  *
  134.  * Handle the filename given by the user.  Since sftw() must stat() each
  135.  * file before sorting, the first (top level) file must be handled specially,
  136.  * not as part of re-entrant code.  (Think about it...)
  137.  */
  138.  
  139. PROC int sftw (path, UserFunc, allfiles)
  140.     char    *path;
  141.     int    (*UserFunc)();
  142.     int    allfiles;
  143. {
  144.     struct    stat statbuf;        /* from first file    */
  145.     int    type;            /* of first file    */
  146.     int    retval;            /* return by UserFunc()    */
  147.     unsigned short geteuid(), getegid();
  148.  
  149.     euid = geteuid();    /* initialize values */
  150.     egid = getegid();
  151.  
  152. /*
  153.  * HANDLE INITIAL FILE:
  154.  */
  155.  
  156.     type = GetType (path, & statbuf);
  157.  
  158.     if (retval = UserFunc (path, & statbuf, type))    /* it's unhappy */
  159.         return (retval);
  160.  
  161.     if (type != FTW_D)            /* we're done */
  162.         return (0);
  163.  
  164. /*
  165.  * WORK ON A READABLE DIRECTORY:
  166.  */
  167.  
  168.     strcpy (filename, path);        /* now we can append to it */
  169.     strcat (filename, "/");            /* prepare for additions   */
  170.  
  171.     return (DoDirectory (UserFunc, allfiles));
  172.  
  173. } /* sftw */
  174.  
  175.  
  176. /************************************************************************
  177.  * D O   D I R E C T O R Y
  178.  *
  179.  * Given UserFunc(), all files flag, and global filename (directory path) where
  180.  * to start and on which to build complete pathnames, read the directory, sort
  181.  * filenames, and call UserFunc() for each file in the directory.  This routine
  182.  * calls itself to recurse, after each directory name is passed to UserFunc().
  183.  * Because it reads and saves a directory's contents in order to sort them, it
  184.  * does not keep any files open while recursing, just lots of memory.
  185.  *
  186.  * Free all memory from this level before returning, even in case of error.
  187.  * Return -1 in case of error, or the value from UserFunc() if non-zero.
  188.  */
  189.  
  190. PROC static int DoDirectory (UserFunc, allfiles)
  191.     int    (*UserFunc)();
  192.     int    allfiles;        /* include ".*" files?      */
  193. {
  194.     dbpt    dbhead = DBNULL;    /* first datablock ptr      */
  195.     sbpt    sbhead = SBNULL;    /* first stringblock ptr  */
  196.  
  197.     fdppt    fdphead;        /* filedata list to sort  */
  198. REG    fdppt    fdpcurr;        /* current list pointer      */
  199. REG    fdpt    fdcurr;            /* current entry pointer  */
  200. REG    int    files;            /* number in directory      */
  201.  
  202.     int    retval;            /* copy of return value      */
  203.  
  204. /* pointer into filename where to append basenames */
  205. REG    char    *basename = filename + strlen (filename);
  206.  
  207.     int    FDCmp();
  208.     void    qsort();
  209.  
  210. #define    RETURN(value) { FreeBlocks (dbhead, sbhead); return (value); }
  211.  
  212. /*
  213.  * READ DIRECTORY:
  214.  */
  215.  
  216.     if ((files = ReadDirectory (& dbhead, & sbhead, allfiles)) < 0)
  217.         RETURN (-1);
  218.  
  219. /*
  220.  * BUILD AND SORT POINTERS TO FILES:
  221.  *
  222.  * Get a big chunk of contiguous memory for the pointers, then set them up.
  223.  * Afterwards, filedata entries will be accessed via the pointers.
  224.  */
  225.  
  226.     if ((fdphead = (fdppt) malloc (files * sizeof (fdpt))) == (fdppt) NULL)
  227.         RETURN (-1);
  228.  
  229. #undef    RETURN
  230. #define    RETURN(value) { FreeBlocks (dbhead, sbhead); \
  231.             free ((char *) fdphead); return (value); }
  232.  
  233.     SetFDList (fdphead, fdphead + files, dbhead);
  234.     qsort ((char *) fdphead, (unsigned) files, sizeof (fdpt), FDCmp);
  235.  
  236. /*
  237.  * TRAVERSE FILES USING SORTED POINTERS:
  238.  *
  239.  * Append each file's basename to the current path in global filename,
  240.  * overlaying whatever basename was there before, and pass it to UserFunc().
  241.  */
  242.  
  243.     fdpcurr = fdphead;
  244.  
  245.     while (files-- > 0)
  246.     {
  247.         strcpy (basename, (fdcurr = (*fdpcurr++)) -> name);
  248.  
  249.         if (retval = UserFunc (filename, & (fdcurr -> statbuf),
  250.                    fdcurr -> type))  /* it's unhappy */
  251.         {
  252.         RETURN (retval);
  253.         }
  254.  
  255. /*
  256.  * RECURSE FOR A DIRECTORY:
  257.  */
  258.  
  259.         if ((fdcurr -> type) == FTW_D)
  260.         {
  261.         strcat (basename, "/");        /* for next level */
  262.  
  263.         if (retval = DoDirectory (UserFunc, allfiles))
  264.             RETURN (retval);
  265.         }
  266.     }
  267.  
  268.     RETURN (0);
  269.  
  270. } /* DoDirectory */
  271.  
  272.  
  273. /************************************************************************
  274.  * R E A D   D I R E C T O R Y
  275.  *
  276.  * Given pointers to datablock and stringblock chain head pointers, all files
  277.  * flag, and global filename (name of a readable directory) on which to build
  278.  * complete pathnames, open, read, and close a directory, saving name, stat,
  279.  * and type information on each file in a chain of datablocks and stringblocks,
  280.  * and setting the chain head pointers.  Return the number of filenames read
  281.  * and saved (>= 0), or -1 in case of error, but always close the directory.
  282.  */
  283.  
  284. PROC static int ReadDirectory (dbheadp, sbheadp, allfiles)
  285.     dbppt    dbheadp;        /* start of chain    */
  286.     sbppt    sbheadp;        /* start of chain    */
  287.     int    allfiles;        /* include ".*" files?    */
  288. {
  289. REG    DIR    *dirp;            /* for reading directory  */
  290. REG    struct    direct *entp;        /* directory entry      */
  291. REG    char    *name;            /* fast copy of filename  */
  292.  
  293. REG    dbpt    dbcurr;            /* current datablock ptr  */
  294.     dbppt    dbnextp = dbheadp;    /* next datablock ptr ptr */
  295. REG    int    dbentry = DBENTRIES;    /* current entry in block */
  296.  
  297. REG    fdpt    fdcurr;            /* current filedata entry */
  298.  
  299. REG    sbpt    sbcurr;            /* current stringblock ptr  */
  300.     sbppt    sbnextp = sbheadp;    /* next stringblock ptr ptr */
  301. REG    char    *end   = "";        /* last + 1 of block        */
  302. REG    char    *start = end;        /* next free place        */
  303.  
  304. /* pointer into filename where to append basenames */
  305. REG    char    *basename = filename + strlen (filename);
  306. REG    int    files      = 0;        /* files read and saved      */
  307.  
  308. #undef    RETURN
  309. #define    RETURN(value) { closedir (dirp); return (value); }
  310.  
  311. /*
  312.  * OPEN AND READ DIRECTORY:
  313.  */
  314.  
  315.     if ((dirp = opendir (filename)) == (DIR *) NULL)
  316.         return (-1);        /* hope errno is set */
  317.  
  318.     /* now be sure to use the RETURN() macro */
  319.  
  320.     while ((entp = readdir (dirp)) != (struct direct *) NULL)
  321.     {
  322.  
  323. /*
  324.  * OPTIONALLY SKIP ".*" FILES:
  325.  *
  326.  * Always skip "." and ".." files, like ftw().
  327.  */
  328.  
  329.         if ((* (name = entp -> d_name) == '.')    /* fast check */
  330.          && ((! allfiles)
  331.           ||  (name [1] == CHNULL)
  332.           || ((name [1] == '.') && (name [2] == CHNULL))))
  333.         {
  334.         continue;
  335.         }
  336.  
  337.         files++;
  338.  
  339. /*
  340.  * GET A NEW DATABLOCK; APPEND TO CHAIN:
  341.  */
  342.  
  343.         if (dbentry >= DBENTRIES)        /* block is full */
  344.         {
  345.         if ((dbcurr = *dbnextp = (dbpt) malloc (DBSIZE)) == DBNULL)
  346.             RETURN (-1);
  347.  
  348.         * (dbnextp = & (dbcurr -> next)) = DBNULL;
  349.         dbentry = 0;
  350.         }
  351.  
  352. /*
  353.  * GET A NEW STRINGBLOCK; APPEND TO CHAIN:
  354.  *
  355.  * Yes, we may abandon some unused space in the previous block...  Hope that
  356.  * STRINGENTRIES is much larger than the average directory entry name size.
  357.  */
  358.  
  359.         if ((entp -> d_namlen) + 1 > (end - start))
  360.         {
  361.         if ((sbcurr = *sbnextp = (sbpt) malloc (SBSIZE)) == SBNULL)
  362.             RETURN (-1);
  363.  
  364.         * (sbnextp = & (sbcurr -> next)) = SBNULL;
  365.         end = (start = (sbcurr -> buf)) + STRINGENTRIES;
  366.         }
  367.  
  368. /*
  369.  * SAVE INFORMATION ON ONE FILE:
  370.  *
  371.  * Append each file's basename to the current path in global filename,
  372.  * overlaying whatever basename was there before, and pass it to GetType().
  373.  */
  374.  
  375.         fdcurr = (dbcurr -> fd) + (dbentry++);    /* quick pointer */
  376.  
  377.         strcpy (((fdcurr -> name) = start), name);
  378.         start += (entp -> d_namlen) + 1;
  379.  
  380.         strcpy (basename, name);
  381.         (fdcurr -> type) = GetType (filename, & (fdcurr -> statbuf));
  382.  
  383.     } /* while */
  384.  
  385.     RETURN (files);
  386.  
  387. } /* ReadDirectory */
  388.  
  389.  
  390. /************************************************************************
  391.  * G E T   T Y P E
  392.  *
  393.  * Given a filename and a pointer to a stat structure, stat() the file into the
  394.  * structure and return an appropriate ftw() type.  Since directories are not
  395.  * opened for reading until much later, after sorting, determine readability
  396.  * now using euid, egid, and st_mode.  Can't use access(2) because it checks
  397.  * real ids, not effective (sigh).
  398.  */
  399.  
  400. PROC static int GetType (name, statp)
  401.     char    *name;
  402.     struct    stat *statp;
  403. {
  404. #define    UREAD (S_IREAD)         /* read permission bits for user, group, other */
  405. #define    GREAD (S_IREAD >> 3)
  406. #define    OREAD (S_IREAD >> 6)
  407.  
  408.     if (stat (name, statp) < 0)
  409.         return (FTW_NS);            /* not stat'able */
  410.  
  411.     if (((statp -> st_mode) & S_IFMT) != S_IFDIR)
  412.         return (FTW_F);            /* not directory */
  413.  
  414.     /* pick appropriate permission bit, then see if it's set */
  415.  
  416.     return (
  417.         ( ((statp -> st_uid) == euid) ? ((statp -> st_mode) & UREAD) :
  418.           ((statp -> st_gid) == egid) ? ((statp -> st_mode) & GREAD) :
  419.                         ((statp -> st_mode) & OREAD) ) ?
  420.         FTW_D : FTW_DNR);
  421.  
  422. } /* GetType */
  423.  
  424.  
  425. /************************************************************************
  426.  * S E T   F D   L I S T
  427.  *
  428.  * Given pointers to the current (head) and end + 1 of an array of
  429.  * uninitialized struct filedata pointers, and a current (head) struct
  430.  * datablock pointer, fill in the pointers in the array to point to the
  431.  * filedata entries in the datablock chain.
  432.  */
  433.  
  434. PROC static SetFDList (fdpcurr, fdpend, dbcurr)
  435. REG    fdppt    fdpcurr;    /* start at head */
  436. REG    fdppt    fdpend;        /* last + 1     */
  437. REG    dbpt    dbcurr;        /* start at head */
  438. {
  439. REG    int    dbentry;    /* current index */
  440.  
  441.     while (TRUE)                /* until return */
  442.     {
  443.         for (dbentry = 0; dbentry < DBENTRIES; dbentry++)    /* one block */
  444.         {
  445.         if (fdpcurr >= fdpend)        /* no more */
  446.             return;
  447.  
  448.         *fdpcurr++ = (dbcurr -> fd) + dbentry;
  449.         }
  450.  
  451.         dbcurr = dbcurr -> next;
  452.     }
  453.  
  454.     /* never get here */
  455.  
  456. } /* SetFDList */
  457.  
  458.  
  459. /************************************************************************
  460.  * F D   C M P
  461.  *
  462.  * Given two pointers to pointers to filedata entries, compare the entries
  463.  * and return -1, 0, or 1 for how they relate.  "Normal" files (FTW_F)
  464.  * are always lower than other types, then names are compared with strcmp().
  465.  */
  466.  
  467. PROC static int FDCmp (fdpp1, fdpp2)
  468.     fdppt    fdpp1, fdpp2;
  469. {
  470. REG    int    type1 = (*fdpp1) -> type;
  471. REG    int    type2 = (*fdpp2) -> type;
  472.  
  473.     return (((type1 == FTW_F) && (type2 != FTW_F)) ? -1 :
  474.         ((type1 != FTW_F) && (type2 == FTW_F)) ?  1 :
  475.         strcmp ((*fdpp1) -> name, (*fdpp2) -> name));
  476.  
  477. } /* FDCmp */
  478.  
  479.  
  480. /************************************************************************
  481.  * F R E E   B L O C K S
  482.  *
  483.  * Given pointers to heads of datablock and stringblock chains, free the
  484.  * malloc'd memory in the chains.
  485.  */
  486.  
  487. PROC static FreeBlocks (dbhead, sbhead)
  488. REG    dbpt    dbhead;
  489. REG    sbpt    sbhead;
  490. {
  491. REG    dbpt    dbtemp;
  492. REG    sbpt    sbtemp;
  493.  
  494.     while (dbhead != DBNULL)
  495.     {
  496.         dbtemp = dbhead -> next;
  497.         free ((char *) dbhead);
  498.         dbhead = dbtemp;
  499.     }
  500.  
  501.     while (sbhead != SBNULL)
  502.     {
  503.         sbtemp = sbhead -> next;
  504.         free ((char *) sbhead);
  505.         sbhead = sbtemp;
  506.     }
  507.  
  508. } /* FreeBlocks */
  509.  
  510.  
  511. #ifdef TEST
  512.  
  513. /************************************************************************
  514.  * TEST HARNESS:
  515.  */
  516.  
  517. PROC int fn (name, statp, type)
  518.     char    *name;
  519.     struct    stat *statp;
  520.     int    type;
  521. {
  522.     printf ("%-3s %06o \"%s\"\n",
  523.         (type == FTW_F)   ? "F"   : (type == FTW_D)  ? "D"  :
  524.         (type == FTW_DNR) ? "DNR" : (type == FTW_NS) ? "NS" : "?",
  525.         statp -> st_mode, name);
  526.  
  527.     return (0);
  528. }
  529.  
  530. PROC main()
  531. {
  532.     printf ("sftw returns %d\n", sftw (".", fn));
  533. }
  534.  
  535. #endif TEST
  536.