home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume20 / rc / part03 / glob.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-05-22  |  6.0 KB  |  276 lines
  1. /* glob.c: rc's (ugly) globber. This code is not elegant, but it works */
  2.  
  3. #include <sys/types.h>
  4. #include "rc.h"
  5. #include "glob.h"
  6. #include "glom.h"
  7. #include "nalloc.h"
  8. #include "utils.h"
  9. #include "match.h"
  10. #include "footobar.h"
  11. #include "list.h"
  12. #ifdef NODIRENT
  13. #include <sys/dir.h>
  14. #define dirent direct /* need to get the struct declaraction right */
  15. #else
  16. #include <dirent.h>
  17. #endif
  18.  
  19. static List *dmatch(char *, char *, char *);
  20. static List *doglob(char *, char *);
  21. static List *lglob(List *, char *, char *, SIZE_T);
  22. static List *sort(List *);
  23.  
  24. /*
  25.    matches a list of words s against a list of patterns p. Returns true iff
  26.    a pattern in p matches a word in s. null matches null, but otherwise null
  27.    patterns match nothing.
  28. */
  29.  
  30. boolean lmatch(List *s, List *p) {
  31.     List *q;
  32.     int i;
  33.     boolean okay;
  34.  
  35.     if (s == NULL) {
  36.         if (p == NULL) /* null matches null */
  37.             return TRUE;
  38.         for (; p != NULL; p = p->n) { /* one or more stars match null */
  39.             if (*p->w != '\0') { /* the null string is a special case; it does *not* match () */
  40.                 okay = TRUE;
  41.                 for (i = 0; p->w[i] != '\0'; i++)
  42.                     if (p->w[i] != '*' || p->m[i] != 1) {
  43.                         okay = FALSE;
  44.                         break;
  45.                     }
  46.                 if (okay)
  47.                     return TRUE;
  48.             }
  49.         }
  50.         return FALSE;
  51.     }
  52.  
  53.     for (; s != NULL; s = s->n)
  54.         for (q = p; q != NULL; q = q->n)
  55.             if (match(q->w, q->m, s->w))
  56.                 return TRUE;
  57.     return FALSE;
  58. }
  59.  
  60. /* Matches a pattern p against the contents of directory d */
  61.  
  62. static List *dmatch(char *d, char *p, char *m) {
  63.     boolean matched = FALSE;
  64.     List *top, *r;
  65.     DIR *dirp;
  66.     struct dirent *dp;
  67.     /* prototypes for XXXdir functions. comment out if necessary */
  68.     extern DIR *opendir(const char *);
  69.     extern struct dirent *readdir(DIR *);
  70.     extern int closedir(DIR *);
  71.  
  72.     if ((dirp = opendir(d)) == NULL)
  73.         return NULL;
  74.  
  75.     top = r = NULL;
  76.  
  77.     while ((dp = readdir(dirp)) != NULL)
  78.         if ((*dp->d_name != '.' || *p == '.') && match(p, m, dp->d_name)) { /* match ^. explicitly */
  79.             matched = TRUE;
  80.             if (top == NULL) {
  81.                 top = r = nnew(List);
  82.             } else {
  83.                 r->n = nnew(List);
  84.                 r = r->n;
  85.             }
  86.             r->w = ncpy(dp->d_name);
  87.             r->m = NULL;
  88.         }
  89.  
  90.     closedir(dirp);
  91.  
  92.     if (!matched)
  93.         return NULL;
  94.  
  95.     r->n = NULL;
  96.     return top;
  97. }
  98.  
  99. /*
  100.    lglob() globs a pattern agains a list of directory roots. e.g., (/tmp /usr /bin) "*"
  101.    will return a list with all the files in /tmp, /usr, and /bin. NULL on no match.
  102.    slashcount indicates the number of slashes to stick between the directory and the
  103.    matched name. e.g., for matching ////tmp/////foo*
  104. */
  105.  
  106. static List *lglob(List *s, char *p, char *m, SIZE_T slashcount) {
  107.     List *q, *r, *top, foo;
  108.     static List slash;
  109.     static SIZE_T slashsize = 0;
  110.  
  111.     if (slashcount + 1 > slashsize) {
  112.         slash.w = ealloc(slashcount + 1);
  113.         slashsize = slashcount;
  114.     }
  115.     slash.w[slashcount] = '\0';
  116.     while (slashcount > 0)
  117.         slash.w[--slashcount] = '/';
  118.  
  119.     for (top = r = NULL; s != NULL; s = s->n) {
  120.         q = dmatch(s->w, p, m);
  121.         if (q != NULL) {
  122.             foo.w = s->w;
  123.             foo.m = NULL;
  124.             foo.n = NULL;
  125.             if (!(s->w[0] == '/' && s->w[1] == '\0')) /* need to separate */
  126.                 q = concat(&slash, q);          /* dir/name with slash */
  127.             q = concat(&foo, q);
  128.             if (r == NULL)
  129.                 top = r = q;
  130.             else
  131.                 r->n = q;
  132.             while (r->n != NULL)
  133.                 r = r->n;
  134.         }
  135.     }
  136.     return top;
  137. }
  138.  
  139. /*
  140.    Doglob globs a pathname in pattern form against a unix path. Returns the original
  141.    pattern (cleaned of metacharacters) on failure, or the globbed string(s).
  142. */
  143.  
  144. static List *doglob(char *w, char *m) {
  145.     static char *dir = NULL, *pattern = NULL, *metadir = NULL, *metapattern = NULL;
  146.     static SIZE_T dsize = 0;
  147.     char *d, *p, *md, *mp;
  148.     SIZE_T psize;
  149.     char *s = w;
  150.     List firstdir;
  151.     List *matched;
  152.     int slashcount;
  153.  
  154.     if ((psize = strlen(w) + 1) > dsize || dir == NULL) {
  155.         efree(dir); efree(pattern); efree(metadir); efree(metapattern);
  156.         dir = ealloc(psize);
  157.         pattern = ealloc(psize);
  158.         metadir = ealloc(psize);
  159.         metapattern = ealloc(psize);
  160.         dsize = psize;
  161.     }
  162.  
  163.     d = dir;
  164.     p = pattern;
  165.     md = metadir;
  166.     mp = metapattern;
  167.  
  168.     if (*s == '/') {
  169.         while (*s == '/')
  170.             *d++ = *s++, *md++ = *m++;
  171.     } else {
  172.         while (*s != '/' && *s != '\0')
  173.             *d++ = *s++, *md++ = *m++; /* get first directory component */
  174.     }
  175.     *d = '\0';
  176.  
  177.     /*
  178.        Special case: no slashes in the pattern, i.e., open the current directory.
  179.        Remember that w cannot consist of slashes alone (the other way *s could be
  180.        zero) since doglob gets called iff there's a metacharacter to be matched
  181.     */
  182.     if (*s == '\0') {
  183.         matched = dmatch(".", dir, metadir);
  184.         goto end;
  185.     }
  186.  
  187.     if (*w == '/') {
  188.         firstdir.w = dir;
  189.         firstdir.m = metadir;
  190.         firstdir.n = NULL;
  191.         matched = &firstdir;
  192.     } else {
  193.         /*
  194.            we must glob against current directory,
  195.            since the first character is not a slash.
  196.         */
  197.         matched = dmatch(".", dir, metadir);
  198.     }
  199.  
  200.     do {
  201.         for (slashcount = 0; *s == '/'; s++, m++)
  202.             slashcount++; /* skip slashes */
  203.  
  204.         while (*s != '/' && *s != '\0')
  205.             *p++ = *s++, *mp++ = *m++; /* get pattern */
  206.         *p = '\0';
  207.  
  208.         matched = lglob(matched, pattern, metapattern, slashcount);
  209.  
  210.         p = pattern, mp = metapattern;
  211.     } while (*s != '\0');
  212.  
  213. end:    if (matched == NULL) {
  214.         matched = nnew(List);
  215.         matched->w = w;
  216.         matched->m = NULL;
  217.         matched->n = NULL;
  218.     }
  219.     return matched;
  220. }
  221.  
  222. /*
  223.    Globs a list; checks to see if each element in the list has a metacharacter. If it
  224.    does, it is globbed, and the output is sorted.
  225. */
  226.  
  227. List *glob(List *s) {
  228.     List *top, *r;
  229.     boolean meta;
  230.  
  231.     for (r = s, meta = FALSE; r != NULL; r = r->n)
  232.         if (r->m != NULL)
  233.             meta = TRUE;
  234.  
  235.     if (!meta)
  236.         return s; /* don't copy lists with no metacharacters in them */
  237.  
  238.     for (top = r = NULL; s != NULL; s = s->n) {
  239.         if (s->m == NULL) { /* no metacharacters; just tack on to the return list */
  240.             if (top == NULL) {
  241.                 top = r = nnew(List);
  242.             } else {
  243.                 r->n = nnew(List);
  244.                 r = r->n;
  245.             }
  246.             r->w = s->w;
  247.         } else {
  248.             if (top == NULL)
  249.                 top = r = sort(doglob(s->w, s->m));
  250.             else
  251.                 r->n = sort(doglob(s->w, s->m));
  252.             while (r->n != NULL)
  253.                 r = r->n;
  254.         }
  255.     }
  256.  
  257.     r->n = NULL;
  258.     return top;
  259. }
  260.  
  261. static List *sort(List *s) {
  262.     SIZE_T nel = listnel(s);
  263.  
  264.     if (nel > 1) {
  265.         char **a;
  266.         List *t;
  267.  
  268.         qsort(a = list2array(s, FALSE), nel, sizeof(char *), starstrcmp);
  269.  
  270.         for (t = s; t != NULL; t = t->n)
  271.             t->w = *a++;
  272.     }
  273.  
  274.     return s;
  275. }
  276.