home *** CD-ROM | disk | FTP | other *** search
/ Mega Top 1 / os2_top1.zip / os2_top1 / APPS / UTILS / H-O / LESS177 / GLOB.C < prev    next >
C/C++ Source or Header  |  1993-01-18  |  15KB  |  596 lines
  1. /*
  2.  * Copyright (c) 1989 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Guido van Rossum.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)glob.c    5.12 (Berkeley) 6/24/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  * glob(3) -- a superset of the one defined in POSIX 1003.2.
  43.  *
  44.  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
  45.  *
  46.  * Optional extra services, controlled by flags not defined by POSIX:
  47.  *
  48.  * GLOB_QUOTE:
  49.  *    Escaping convention: \ inhibits any special meaning the following
  50.  *    character might have (except \ at end of string is retained).
  51.  * GLOB_MAGCHAR:
  52.  *    Set in gl_flags if pattern contained a globbing character.
  53.  * gl_matchc:
  54.  *    Number of matches in the current invocation of glob.
  55.  */
  56.  
  57. /*#include <sys/cdefs.h>*/
  58.  
  59. #include <ctype.h>
  60.  
  61.  
  62. #include <sys/types.h>
  63. #include <sys/param.h>
  64. #include <sys/stat.h>
  65. #include <dirent.h>
  66. #include "glob.h"
  67. #include <ctype.h>
  68. #include <errno.h>
  69. #include <string.h>
  70. #include <stdio.h>
  71. #include <stdlib.h>
  72.  
  73.  
  74. #define    DOLLAR        '$'
  75. #define    DOT        '.'
  76. #define    EOS        '\0'
  77. #define    LBRACKET    '['
  78. #define    NOT        '!'
  79. #define    QUESTION    '?'
  80. #define    QUOTE        '^'
  81. #define    RANGE        '-'
  82. #define    RBRACKET    ']'
  83. #define    SEP        '/'
  84. #define    STAR        '*'
  85. #define    TILDE        '~'
  86. #define    UNDERSCORE    '_'
  87.  
  88. #define    M_QUOTE        0x8000
  89. #define    M_PROTECT    0x4000
  90. #define    M_MASK        0xffff
  91. #define    M_ASCII        0x00ff
  92.  
  93. #define    CHAR(c)        ((c)&M_ASCII)
  94. #define    META(c)        ((c)|M_QUOTE)
  95. #define    M_ALL        META('*')
  96. #define    M_END        META(']')
  97. #define    M_NOT        META('!')
  98. #define    M_ONE        META('?')
  99. #define    M_RNG        META('-')
  100. #define    M_SET        META('[')
  101. #define    ismeta(c)    (((c)&M_QUOTE) != 0)
  102.  
  103. extern int globnocase;
  104.  
  105. typedef unsigned short Char;
  106.  
  107. static int     compare (const void *, const void *);
  108. static void     g_Ctoc (Char *, char *);
  109. /*static int     g_lstat (Char *, struct stat *);*/
  110. static DIR    *g_opendir (Char *);
  111. static Char    *g_strchr (Char *, int);
  112. static int     g_stat (Char *, struct stat *);
  113. static int     glob1 (Char *, glob_t *);
  114. static int     glob2 (Char *, Char *, Char *, glob_t *);
  115. static int     glob3 (Char *, Char *, Char *, Char *, glob_t *);
  116. static int     globextend (Char *, glob_t *);
  117. static int     match (Char *, Char *, Char *);
  118. #ifdef DEBUG
  119. static void     qprintf (Char *);
  120. #endif
  121.  
  122. /*
  123.  * The main glob() routine: compiles the pattern (optionally processing
  124.  * quotes), calls glob1() to do the real pattern matching, and finally
  125.  * sorts the list (unless unsorted operation is requested).  Returns 0
  126.  * if things went well, nonzero if errors occurred.  It is not an error
  127.  * to find no matches.
  128.  */
  129. oglob(pattern, flags, errfunc, pglob)
  130.     const char *pattern;
  131.     int flags, (*errfunc) (char *, int);
  132.     glob_t *pglob;
  133. {
  134.     const unsigned char *compilepat, *patnext;
  135.     int c, err, oldpathc;
  136.     Char *bufnext, *bufend, *compilebuf, *qpatnext, patbuf[MAXPATHLEN+1];
  137.  
  138.     patnext = (unsigned char *) pattern;
  139.     if (!(flags & GLOB_APPEND)) {
  140.         pglob->gl_pathc = 0;
  141.         pglob->gl_pathv = NULL;
  142.         if (!(flags & GLOB_DOOFFS))
  143.             pglob->gl_offs = 0;
  144.     }
  145.     pglob->gl_flags = flags & ~GLOB_MAGCHAR;
  146.     pglob->gl_errfunc = errfunc;
  147.     oldpathc = pglob->gl_pathc;
  148.     pglob->gl_matchc = 0;
  149.  
  150.     bufnext = patbuf;
  151.     bufend = bufnext + MAXPATHLEN;
  152.     compilebuf = bufnext;
  153.     compilepat = patnext;
  154.     if (flags & GLOB_QUOTE) {
  155.         /* Protect the quoted characters. */
  156.         while (bufnext < bufend && (c = *patnext++) != EOS) 
  157.             if (c == QUOTE) {
  158.                 if ((c = *patnext++) == EOS) {
  159.                     c = QUOTE;
  160.                     --patnext;
  161.                 }
  162.                 *bufnext++ = c | M_PROTECT;
  163.             }
  164.             else
  165.                 *bufnext++ = c;
  166.     }
  167.     else 
  168.         while (bufnext < bufend && (c = *patnext++) != EOS) 
  169.             *bufnext++ = c;
  170.     *bufnext = EOS;
  171.  
  172.     bufnext = patbuf;
  173.     qpatnext = patbuf;
  174.     /* We don't need to check for buffer overflow any more. */
  175.     while ((c = *qpatnext++) != EOS) {
  176.         switch (c) {
  177.         case LBRACKET:
  178.             pglob->gl_flags |= GLOB_MAGCHAR;
  179.             c = *qpatnext;
  180.             if (c == NOT)
  181.                 ++qpatnext;
  182.             if (*qpatnext == EOS ||
  183.                 g_strchr(qpatnext+1, RBRACKET) == NULL) {
  184.                 *bufnext++ = LBRACKET;
  185.                 if (c == NOT)
  186.                     --qpatnext;
  187.                 break;
  188.             }
  189.             *bufnext++ = M_SET;
  190.             if (c == NOT)
  191.                 *bufnext++ = M_NOT;
  192.             c = *qpatnext++;
  193.             do {
  194.                 *bufnext++ = CHAR(c);
  195.                 if (*qpatnext == RANGE &&
  196.                     (c = qpatnext[1]) != RBRACKET) {
  197.                     *bufnext++ = M_RNG;
  198.                     *bufnext++ = CHAR(c);
  199.                     qpatnext += 2;
  200.                 }
  201.             } while ((c = *qpatnext++) != RBRACKET);
  202.             *bufnext++ = M_END;
  203.             break;
  204.         case QUESTION:
  205.             pglob->gl_flags |= GLOB_MAGCHAR;
  206.             *bufnext++ = M_ONE;
  207.             break;
  208.         case STAR:
  209.             pglob->gl_flags |= GLOB_MAGCHAR;
  210.             *bufnext++ = M_ALL;
  211.             break;
  212.         default:
  213.             *bufnext++ = CHAR(c);
  214.             break;
  215.         }
  216.     }
  217.     *bufnext = EOS;
  218. #ifdef DEBUG
  219.     qprintf(patbuf);
  220. #endif
  221.  
  222.     if ((err = glob1(patbuf, pglob)) != 0)
  223.         return(err);
  224.  
  225.     if (pglob->gl_pathc == oldpathc && flags & GLOB_NOCHECK) {
  226.         if (!(flags & GLOB_QUOTE)) {
  227.             Char *dp = compilebuf;
  228.             const unsigned char *sp = compilepat;
  229.             while (*dp++ = *sp++);
  230.         }
  231.         else {
  232.             /*
  233.              * Copy pattern, interpreting quotes; this is slightly
  234.              * different than the interpretation of quotes above
  235.              * -- which should prevail?
  236.              */
  237.             while (*compilepat != EOS) {
  238.                 if (*compilepat == QUOTE) {
  239.                     if (*++compilepat == EOS)
  240.                         --compilepat;
  241.                 }
  242.                 *compilebuf++ = (unsigned char)*compilepat++;
  243.             }
  244.             *compilebuf = EOS;
  245.         }
  246.         return(globextend(patbuf, pglob));
  247.     } else if (!(flags & GLOB_NOSORT)) 
  248.         qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
  249.             pglob->gl_pathc - oldpathc, sizeof(char *), compare);
  250.     return(0);
  251. }
  252.  
  253. static int
  254. compare(p, q)
  255.     const void *p, *q;
  256. {
  257.     return(strcmp(*(char **)p, *(char **)q));
  258. }
  259.  
  260. static
  261. glob1(pattern, pglob)
  262.     Char *pattern;
  263.     glob_t *pglob;
  264. {
  265.     Char pathbuf[MAXPATHLEN+1];
  266.  
  267.     /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
  268.     if (*pattern == EOS)
  269.         return(0);
  270.     return(glob2(pathbuf, pathbuf, pattern, pglob));
  271. }
  272.  
  273. /*
  274.  * The functions glob2 and glob3 are mutually recursive; there is one level
  275.  * of recursion for each segment in the pattern that contains one or more
  276.  * meta characters.
  277.  */
  278. static
  279. glob2(pathbuf, pathend, pattern, pglob)
  280.     Char *pathbuf, *pathend, *pattern;
  281.     glob_t *pglob;
  282. {
  283.     struct stat sb;
  284.     Char *p, *q;
  285.     int anymeta;
  286.  
  287.     /*
  288.      * Loop over pattern segments until end of pattern or until
  289.      * segment with meta character found.
  290.      */
  291.     for (anymeta = 0;;) {
  292.         if (*pattern == EOS) {        /* End of pattern? */
  293.             *pathend = EOS;
  294.             if (g_stat(pathbuf, &sb))
  295.                 return(0);
  296.         
  297.             if (((pglob->gl_flags & GLOB_MARK) &&
  298.                 pathend[-1] != SEP) && /*(S_ISDIR(sb.st_mode)
  299.                 || (S_ISLNK(sb.st_mode) &&*/
  300.                 (g_stat(pathbuf, &sb) == 0) &&
  301.                 S_ISDIR(sb.st_mode)) {
  302.                 *pathend++ = SEP;
  303.                 *pathend = EOS;
  304.             }
  305.             ++pglob->gl_matchc;
  306.             return(globextend(pathbuf, pglob));
  307.         }
  308.  
  309.         /* Find end of next segment, copy tentatively to pathend. */
  310.         q = pathend;
  311.         p = pattern;
  312.         while (*p != EOS && *p != SEP && *p != '\\' && *p != ':') {
  313.             if (ismeta(*p))
  314.                 anymeta = 1;
  315.             *q++ = *p++;
  316.         }
  317.  
  318.         if (!anymeta) {        /* No expansion, do next segment. */
  319.             pathend = q;
  320.             pattern = p;
  321.             while (*pattern == SEP || *pattern == '\\' || *pattern == ':')
  322.                 *pathend++ = *pattern++;
  323.         } else            /* Need expansion, recurse. */
  324.             return(glob3(pathbuf, pathend, pattern, p, pglob));
  325.     }
  326.     /* NOTREACHED */
  327. }
  328.  
  329. static
  330. glob3(pathbuf, pathend, pattern, restpattern, pglob)
  331.     Char *pathbuf, *pathend, *pattern, *restpattern;
  332.     glob_t *pglob;
  333. {
  334.     register struct dirent *dp;
  335.     DIR *dirp;
  336.     int len, err;
  337.  
  338.     *pathend = EOS;
  339.     errno = 0;
  340.     if (!(dirp = g_opendir(pathbuf)))
  341.         /* TODO: don't call for ENOENT or ENOTDIR? */
  342.         if (pglob->gl_errfunc &&
  343.             (*pglob->gl_errfunc)(pathbuf, errno) ||
  344.             (pglob->gl_flags & GLOB_ERR))
  345.             return(GLOB_ABEND);
  346.         else
  347.             return(0);
  348.  
  349.     err = 0;
  350.  
  351.     /* Search directory for matching names. */
  352.     while ((dp = readdir(dirp))) {
  353.         register unsigned char *sc;
  354.         register Char *dc;
  355.  
  356.         /* Initial DOT must be matched literally. */
  357.         if (dp->d_name[0] == DOT && *pattern != DOT)
  358.             continue;
  359.  
  360.         for (sc = (unsigned char *) dp->d_name, dc = pathend; 
  361.              *dc++ = *sc++;);
  362.         if (!match(pathend, pattern, restpattern)) {
  363.             *pathend = EOS;
  364.             continue;
  365.         }
  366.         err = glob2(pathbuf, --dc, restpattern, pglob);
  367.         if (err)
  368.             break;
  369.     }
  370.  
  371.     /* TODO: check error from readdir? */
  372.     (void)closedir(dirp);
  373.     return(err);
  374. }
  375.  
  376.  
  377. /*
  378.  * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
  379.  * add the new item, and update gl_pathc.
  380.  *
  381.  * This assumes the BSD realloc, which only copies the block when its size
  382.  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
  383.  * behavior.
  384.  *
  385.  * Return 0 if new item added, error code if memory couldn't be allocated.
  386.  *
  387.  * Invariant of the glob_t structure:
  388.  *    Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
  389.  *    gl_pathv points to (gl_offs + gl_pathc + 1) items.
  390.  */
  391. static int
  392. globextend(path, pglob)
  393.     Char *path;
  394.     glob_t *pglob;
  395. {
  396.     register char **pathv;
  397.     register int i;
  398.     unsigned int newsize;
  399.     char *copy;
  400.     Char *p;
  401.  
  402.     newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
  403.     pathv = (char **)realloc((char *)pglob->gl_pathv, newsize);
  404.     if (pathv == NULL)
  405.         return(GLOB_NOSPACE);
  406.  
  407.     if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
  408.         /* first time around -- clear initial gl_offs items */
  409.         pathv += pglob->gl_offs;
  410.         for (i = pglob->gl_offs; --i >= 0; )
  411.             *--pathv = NULL;
  412.     }
  413.     pglob->gl_pathv = pathv;
  414.  
  415.     for (p = path; *p++;);
  416.     if ((copy = malloc(p - path)) != NULL) {
  417.         g_Ctoc(path, copy);
  418.         pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
  419.     }
  420.     pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
  421.     return(copy == NULL ? GLOB_NOSPACE : 0);
  422. }
  423.  
  424.  
  425. /*
  426.  * pattern matching function for filenames.  Each occurrence of the *
  427.  * pattern causes a recursion level.
  428.  */
  429. static
  430. match(name, pat, patend)
  431.     register Char *name, *pat, *patend;
  432. {
  433.     int ok, negate_range;
  434.     Char c, k;
  435.  
  436.     while (pat < patend) {
  437.         c = *pat++;
  438.         switch (c & M_MASK) {
  439.         case M_ALL:
  440.             if (pat == patend)
  441.                 return(1);
  442.             for (; *name != EOS; ++name)
  443.                 if (match(name, pat, patend))
  444.                     return(1);
  445.             return(0);
  446.         case M_ONE:
  447.             if (*name++ == EOS)
  448.                 return(0);
  449.             break;
  450.         case M_SET:
  451.             ok = 0;
  452.             k = *name++;
  453.             if (negate_range = ((*pat & M_MASK) == M_NOT))
  454.                 ++pat;
  455.             while (((c = *pat++) & M_MASK) != M_END)
  456.               if ((*pat & M_MASK) == M_RNG) {
  457.                 if (c <= k && k <= pat[1])
  458.                   ok = 1;
  459.                 pat += 2;
  460.               } else if (!globnocase) {
  461.                 if (c == k)
  462.                   ok = 1;
  463.               } else {
  464.                 if (isascii(k) && isascii(c)) {
  465.                   if (islower((int)k) && isupper((int)c)) {
  466.                 if (k == c + 'a' - 'A')
  467.                   ok = 1;
  468.                   } else if (isupper((int)k) && islower((int)c)) {
  469.                 if (k + 'a' -'A' == c)
  470.                   ok = 1;
  471.                   } else if (k == c)
  472.                 ok = 1;
  473.                 } else if (k == c)
  474.                   ok = 1;
  475.               }
  476.             
  477.  
  478.             if (ok == negate_range)
  479.                 return(0);
  480.             break;
  481.         default:
  482.             if (!globnocase) {
  483.               if (*name != c)
  484.                 return(0);
  485.             } else {
  486.               if (isascii(*name) && isascii(c)) {
  487.                 if (islower((int)*name) && isupper((int)c)) {
  488.                   if (*name != c +'a' - 'A')
  489.                 return(0);
  490.                 } else if (isupper((int)*name) && islower((int)c)) {
  491.                   if (*name + 'a' -'A' != c)
  492.                 return(0);
  493.                 } else if (*name != c) {
  494.                   return(0);
  495.                 }
  496.               } else if (*name != c)
  497.                 return(0);
  498.             }
  499.             name++;
  500.             break;
  501.         }
  502.     }
  503.     return(*name == EOS);
  504. }
  505.  
  506. /* Free allocated data belonging to a glob_t structure. */
  507. void
  508. globfree(pglob)
  509.     glob_t *pglob;
  510. {
  511.     register int i;
  512.     register char **pp;
  513.  
  514.     if (pglob->gl_pathv != NULL) {
  515.         pp = pglob->gl_pathv + pglob->gl_offs;
  516.         for (i = pglob->gl_pathc; i--; ++pp)
  517.             if (*pp)
  518.                 free(*pp);
  519.         free(pglob->gl_pathv);
  520.     }
  521. }
  522.  
  523. static DIR *
  524. g_opendir(str)
  525.     register Char *str;
  526. {
  527.     char buf[MAXPATHLEN];
  528.  
  529.     if (!*str)
  530.         return(opendir("."));
  531.     g_Ctoc(str, buf);
  532.     return(opendir(buf));
  533. }
  534.  
  535. /*static int
  536. g_lstat(fn, sb)
  537.     register Char *fn;
  538.     struct stat *sb;
  539. {
  540.     char buf[MAXPATHLEN];
  541.  
  542.     g_Ctoc(fn, buf);
  543.     return(lstat(buf, sb));
  544. }*/
  545.  
  546. static int
  547. g_stat(fn, sb)
  548.     register Char *fn;
  549.     struct stat *sb;
  550. {
  551.     char buf[MAXPATHLEN];
  552.     g_Ctoc(fn, buf);
  553.     return(stat(buf, sb));
  554. }
  555.  
  556. static Char *
  557. g_strchr(str, ch)
  558.     Char *str;
  559.     int ch;
  560. {
  561.     do {
  562.         if (*str == ch)
  563.             return (str);
  564.     } while (*str++);
  565.     return (NULL);
  566. }
  567.  
  568. static void
  569. g_Ctoc(str, buf)
  570.     register Char *str;
  571.     char *buf;
  572. {
  573.     register char *dc;
  574.  
  575.     for (dc = buf; *dc++ = *str++;);
  576. }
  577.  
  578. #ifdef DEBUG
  579. static void 
  580. qprintf(s)
  581.     register Char *s;
  582. {
  583.     register Char *p;
  584.  
  585.     for (p = s; *p; p++)
  586.         (void)printf("%c", *p & 0xff);
  587.     (void)printf("\n");
  588.     for (p = s; *p; p++)
  589.         (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
  590.     (void)printf("\n");
  591.     for (p = s; *p; p++)
  592.         (void)printf("%c", *p & M_META ? '_' : ' ');
  593.     (void)printf("\n");
  594. }
  595. #endif
  596.