home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 11 Util / 11-Util.zip / LESS177.ZIP / src / glob.c < prev    next >
C/C++ Source or Header  |  1992-07-18  |  14KB  |  557 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. #include <sys/types.h>
  59. #include <sys/param.h>
  60. #include <sys/stat.h>
  61. #include <dirent.h>
  62. #include "glob.h"
  63. #include <ctype.h>
  64. #include <errno.h>
  65. #include <string.h>
  66. #include <stdio.h>
  67. #include <stdlib.h>
  68.  
  69.  
  70. #define    DOLLAR        '$'
  71. #define    DOT        '.'
  72. #define    EOS        '\0'
  73. #define    LBRACKET    '['
  74. #define    NOT        '!'
  75. #define    QUESTION    '?'
  76. #define    QUOTE        '\\'
  77. #define    RANGE        '-'
  78. #define    RBRACKET    ']'
  79. #define    SEP        '/'
  80. #define    STAR        '*'
  81. #define    TILDE        '~'
  82. #define    UNDERSCORE    '_'
  83.  
  84. #define    M_QUOTE        0x8000
  85. #define    M_PROTECT    0x4000
  86. #define    M_MASK        0xffff
  87. #define    M_ASCII        0x00ff
  88.  
  89. #define    CHAR(c)        ((c)&M_ASCII)
  90. #define    META(c)        ((c)|M_QUOTE)
  91. #define    M_ALL        META('*')
  92. #define    M_END        META(']')
  93. #define    M_NOT        META('!')
  94. #define    M_ONE        META('?')
  95. #define    M_RNG        META('-')
  96. #define    M_SET        META('[')
  97. #define    ismeta(c)    (((c)&M_QUOTE) != 0)
  98.  
  99. typedef unsigned short Char;
  100.  
  101. static int     compare (const void *, const void *);
  102. static void     g_Ctoc (Char *, char *);
  103. /*static int     g_lstat (Char *, struct stat *);*/
  104. static DIR    *g_opendir (Char *);
  105. static Char    *g_strchr (Char *, int);
  106. static int     g_stat (Char *, struct stat *);
  107. static int     glob1 (Char *, glob_t *);
  108. static int     glob2 (Char *, Char *, Char *, glob_t *);
  109. static int     glob3 (Char *, Char *, Char *, Char *, glob_t *);
  110. static int     globextend (Char *, glob_t *);
  111. static int     match (Char *, Char *, Char *);
  112. #ifdef DEBUG
  113. static void     qprintf (Char *);
  114. #endif
  115.  
  116. /*
  117.  * The main glob() routine: compiles the pattern (optionally processing
  118.  * quotes), calls glob1() to do the real pattern matching, and finally
  119.  * sorts the list (unless unsorted operation is requested).  Returns 0
  120.  * if things went well, nonzero if errors occurred.  It is not an error
  121.  * to find no matches.
  122.  */
  123. oglob(pattern, flags, errfunc, pglob)
  124.     const char *pattern;
  125.     int flags, (*errfunc) (char *, int);
  126.     glob_t *pglob;
  127. {
  128.     const unsigned char *compilepat, *patnext;
  129.     int c, err, oldpathc;
  130.     Char *bufnext, *bufend, *compilebuf, *qpatnext, patbuf[MAXPATHLEN+1];
  131.  
  132.     patnext = (unsigned char *) pattern;
  133.     if (!(flags & GLOB_APPEND)) {
  134.         pglob->gl_pathc = 0;
  135.         pglob->gl_pathv = NULL;
  136.         if (!(flags & GLOB_DOOFFS))
  137.             pglob->gl_offs = 0;
  138.     }
  139.     pglob->gl_flags = flags & ~GLOB_MAGCHAR;
  140.     pglob->gl_errfunc = errfunc;
  141.     oldpathc = pglob->gl_pathc;
  142.     pglob->gl_matchc = 0;
  143.  
  144.     bufnext = patbuf;
  145.     bufend = bufnext + MAXPATHLEN;
  146.     compilebuf = bufnext;
  147.     compilepat = patnext;
  148.     if (flags & GLOB_QUOTE) {
  149.         /* Protect the quoted characters. */
  150.         while (bufnext < bufend && (c = *patnext++) != EOS) 
  151.             if (c == QUOTE) {
  152.                 if ((c = *patnext++) == EOS) {
  153.                     c = QUOTE;
  154.                     --patnext;
  155.                 }
  156.                 *bufnext++ = c | M_PROTECT;
  157.             }
  158.             else
  159.                 *bufnext++ = c;
  160.     }
  161.     else 
  162.         while (bufnext < bufend && (c = *patnext++) != EOS) 
  163.             *bufnext++ = c;
  164.     *bufnext = EOS;
  165.  
  166.     bufnext = patbuf;
  167.     qpatnext = patbuf;
  168.     /* We don't need to check for buffer overflow any more. */
  169.     while ((c = *qpatnext++) != EOS) {
  170.         switch (c) {
  171.         case LBRACKET:
  172.             pglob->gl_flags |= GLOB_MAGCHAR;
  173.             c = *qpatnext;
  174.             if (c == NOT)
  175.                 ++qpatnext;
  176.             if (*qpatnext == EOS ||
  177.                 g_strchr(qpatnext+1, RBRACKET) == NULL) {
  178.                 *bufnext++ = LBRACKET;
  179.                 if (c == NOT)
  180.                     --qpatnext;
  181.                 break;
  182.             }
  183.             *bufnext++ = M_SET;
  184.             if (c == NOT)
  185.                 *bufnext++ = M_NOT;
  186.             c = *qpatnext++;
  187.             do {
  188.                 *bufnext++ = CHAR(c);
  189.                 if (*qpatnext == RANGE &&
  190.                     (c = qpatnext[1]) != RBRACKET) {
  191.                     *bufnext++ = M_RNG;
  192.                     *bufnext++ = CHAR(c);
  193.                     qpatnext += 2;
  194.                 }
  195.             } while ((c = *qpatnext++) != RBRACKET);
  196.             *bufnext++ = M_END;
  197.             break;
  198.         case QUESTION:
  199.             pglob->gl_flags |= GLOB_MAGCHAR;
  200.             *bufnext++ = M_ONE;
  201.             break;
  202.         case STAR:
  203.             pglob->gl_flags |= GLOB_MAGCHAR;
  204.             *bufnext++ = M_ALL;
  205.             break;
  206.         default:
  207.             *bufnext++ = CHAR(c);
  208.             break;
  209.         }
  210.     }
  211.     *bufnext = EOS;
  212. #ifdef DEBUG
  213.     qprintf(patbuf);
  214. #endif
  215.  
  216.     if ((err = glob1(patbuf, pglob)) != 0)
  217.         return(err);
  218.  
  219.     if (pglob->gl_pathc == oldpathc && flags & GLOB_NOCHECK) {
  220.         if (!(flags & GLOB_QUOTE)) {
  221.             Char *dp = compilebuf;
  222.             const unsigned char *sp = compilepat;
  223.             while (*dp++ = *sp++);
  224.         }
  225.         else {
  226.             /*
  227.              * Copy pattern, interpreting quotes; this is slightly
  228.              * different than the interpretation of quotes above
  229.              * -- which should prevail?
  230.              */
  231.             while (*compilepat != EOS) {
  232.                 if (*compilepat == QUOTE) {
  233.                     if (*++compilepat == EOS)
  234.                         --compilepat;
  235.                 }
  236.                 *compilebuf++ = (unsigned char)*compilepat++;
  237.             }
  238.             *compilebuf = EOS;
  239.         }
  240.         return(globextend(patbuf, pglob));
  241.     } else if (!(flags & GLOB_NOSORT)) 
  242.         qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
  243.             pglob->gl_pathc - oldpathc, sizeof(char *), compare);
  244.     return(0);
  245. }
  246.  
  247. static int
  248. compare(p, q)
  249.     const void *p, *q;
  250. {
  251.     return(strcmp(*(char **)p, *(char **)q));
  252. }
  253.  
  254. static
  255. glob1(pattern, pglob)
  256.     Char *pattern;
  257.     glob_t *pglob;
  258. {
  259.     Char pathbuf[MAXPATHLEN+1];
  260.  
  261.     /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
  262.     if (*pattern == EOS)
  263.         return(0);
  264.     return(glob2(pathbuf, pathbuf, pattern, pglob));
  265. }
  266.  
  267. /*
  268.  * The functions glob2 and glob3 are mutually recursive; there is one level
  269.  * of recursion for each segment in the pattern that contains one or more
  270.  * meta characters.
  271.  */
  272. static
  273. glob2(pathbuf, pathend, pattern, pglob)
  274.     Char *pathbuf, *pathend, *pattern;
  275.     glob_t *pglob;
  276. {
  277.     struct stat sb;
  278.     Char *p, *q;
  279.     int anymeta;
  280.  
  281.     /*
  282.      * Loop over pattern segments until end of pattern or until
  283.      * segment with meta character found.
  284.      */
  285.     for (anymeta = 0;;) {
  286.         if (*pattern == EOS) {        /* End of pattern? */
  287.             *pathend = EOS;
  288.             if (g_stat(pathbuf, &sb))
  289.                 return(0);
  290.         
  291.             if (((pglob->gl_flags & GLOB_MARK) &&
  292.                 pathend[-1] != SEP) && /*(S_ISDIR(sb.st_mode)
  293.                 || (S_ISLNK(sb.st_mode) &&*/
  294.                 (g_stat(pathbuf, &sb) == 0)/* &&
  295.                 S_ISDIR(sb.st_mode)))*/) {
  296.                 *pathend++ = SEP;
  297.                 *pathend = EOS;
  298.             }
  299.             ++pglob->gl_matchc;
  300.             return(globextend(pathbuf, pglob));
  301.         }
  302.  
  303.         /* Find end of next segment, copy tentatively to pathend. */
  304.         q = pathend;
  305.         p = pattern;
  306.         while (*p != EOS && *p != SEP && *p != '\\' && *p != ':') {
  307.             if (ismeta(*p))
  308.                 anymeta = 1;
  309.             *q++ = *p++;
  310.         }
  311.  
  312.         if (!anymeta) {        /* No expansion, do next segment. */
  313.             pathend = q;
  314.             pattern = p;
  315.             while (*pattern == SEP || *pattern == '\\' || *pattern == ':')
  316.                 *pathend++ = *pattern++;
  317.         } else            /* Need expansion, recurse. */
  318.             return(glob3(pathbuf, pathend, pattern, p, pglob));
  319.     }
  320.     /* NOTREACHED */
  321. }
  322.  
  323. static
  324. glob3(pathbuf, pathend, pattern, restpattern, pglob)
  325.     Char *pathbuf, *pathend, *pattern, *restpattern;
  326.     glob_t *pglob;
  327. {
  328.     register struct dirent *dp;
  329.     DIR *dirp;
  330.     int len, err;
  331.  
  332.     *pathend = EOS;
  333.     errno = 0;
  334.     if (!(dirp = g_opendir(pathbuf)))
  335.         /* TODO: don't call for ENOENT or ENOTDIR? */
  336.         if (pglob->gl_errfunc &&
  337.             (*pglob->gl_errfunc)(pathbuf, errno) ||
  338.             (pglob->gl_flags & GLOB_ERR))
  339.             return(GLOB_ABEND);
  340.         else
  341.             return(0);
  342.  
  343.     err = 0;
  344.  
  345.     /* Search directory for matching names. */
  346.     while ((dp = readdir(dirp))) {
  347.         register unsigned char *sc;
  348.         register Char *dc;
  349.  
  350.         /* Initial DOT must be matched literally. */
  351.         if (dp->d_name[0] == DOT && *pattern != DOT)
  352.             continue;
  353.         for (sc = (unsigned char *) dp->d_name, dc = pathend; 
  354.              *dc++ = *sc++;);
  355.         if (!match(pathend, pattern, restpattern)) {
  356.             *pathend = EOS;
  357.             continue;
  358.         }
  359.         err = glob2(pathbuf, --dc, restpattern, pglob);
  360.         if (err)
  361.             break;
  362.     }
  363.  
  364.     /* TODO: check error from readdir? */
  365.     (void)closedir(dirp);
  366.     return(err);
  367. }
  368.  
  369.  
  370. /*
  371.  * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
  372.  * add the new item, and update gl_pathc.
  373.  *
  374.  * This assumes the BSD realloc, which only copies the block when its size
  375.  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
  376.  * behavior.
  377.  *
  378.  * Return 0 if new item added, error code if memory couldn't be allocated.
  379.  *
  380.  * Invariant of the glob_t structure:
  381.  *    Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
  382.  *    gl_pathv points to (gl_offs + gl_pathc + 1) items.
  383.  */
  384. static int
  385. globextend(path, pglob)
  386.     Char *path;
  387.     glob_t *pglob;
  388. {
  389.     register char **pathv;
  390.     register int i;
  391.     unsigned int newsize;
  392.     char *copy;
  393.     Char *p;
  394.  
  395.     newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
  396.     pathv = (char **)realloc((char *)pglob->gl_pathv, newsize);
  397.     if (pathv == NULL)
  398.         return(GLOB_NOSPACE);
  399.  
  400.     if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
  401.         /* first time around -- clear initial gl_offs items */
  402.         pathv += pglob->gl_offs;
  403.         for (i = pglob->gl_offs; --i >= 0; )
  404.             *--pathv = NULL;
  405.     }
  406.     pglob->gl_pathv = pathv;
  407.  
  408.     for (p = path; *p++;);
  409.     if ((copy = malloc(p - path)) != NULL) {
  410.         g_Ctoc(path, copy);
  411.         pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
  412.     }
  413.     pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
  414.     return(copy == NULL ? GLOB_NOSPACE : 0);
  415. }
  416.  
  417.  
  418. /*
  419.  * pattern matching function for filenames.  Each occurrence of the *
  420.  * pattern causes a recursion level.
  421.  */
  422. static
  423. match(name, pat, patend)
  424.     register Char *name, *pat, *patend;
  425. {
  426.     int ok, negate_range;
  427.     Char c, k;
  428.  
  429.     while (pat < patend) {
  430.         c = *pat++;
  431.         switch (c & M_MASK) {
  432.         case M_ALL:
  433.             if (pat == patend)
  434.                 return(1);
  435.             for (; *name != EOS; ++name)
  436.                 if (match(name, pat, patend))
  437.                     return(1);
  438.             return(0);
  439.         case M_ONE:
  440.             if (*name++ == EOS)
  441.                 return(0);
  442.             break;
  443.         case M_SET:
  444.             ok = 0;
  445.             k = *name++;
  446.             if (negate_range = ((*pat & M_MASK) == M_NOT))
  447.                 ++pat;
  448.             while (((c = *pat++) & M_MASK) != M_END)
  449.                 if ((*pat & M_MASK) == M_RNG) {
  450.                     if (c <= k && k <= pat[1])
  451.                         ok = 1;
  452.                     pat += 2;
  453.                 } else if (c == k)
  454.                     ok = 1;
  455.             if (ok == negate_range)
  456.                 return(0);
  457.             break;
  458.         default:
  459.             if (*name++ != c)
  460.                 return(0);
  461.             break;
  462.         }
  463.     }
  464.     return(*name == EOS);
  465. }
  466.  
  467. /* Free allocated data belonging to a glob_t structure. */
  468. void
  469. globfree(pglob)
  470.     glob_t *pglob;
  471. {
  472.     register int i;
  473.     register char **pp;
  474.  
  475.     if (pglob->gl_pathv != NULL) {
  476.         pp = pglob->gl_pathv + pglob->gl_offs;
  477.         for (i = pglob->gl_pathc; i--; ++pp)
  478.             if (*pp)
  479.                 free(*pp);
  480.         free(pglob->gl_pathv);
  481.     }
  482. }
  483.  
  484. static DIR *
  485. g_opendir(str)
  486.     register Char *str;
  487. {
  488.     char buf[MAXPATHLEN];
  489.  
  490.     if (!*str)
  491.         return(opendir("."));
  492.     g_Ctoc(str, buf);
  493.     return(opendir(buf));
  494. }
  495.  
  496. /*static int
  497. g_lstat(fn, sb)
  498.     register Char *fn;
  499.     struct stat *sb;
  500. {
  501.     char buf[MAXPATHLEN];
  502.  
  503.     g_Ctoc(fn, buf);
  504.     return(lstat(buf, sb));
  505. }*/
  506.  
  507. static int
  508. g_stat(fn, sb)
  509.     register Char *fn;
  510.     struct stat *sb;
  511. {
  512.     char buf[MAXPATHLEN];
  513.     g_Ctoc(fn, buf);
  514.     return(stat(buf, sb));
  515. }
  516.  
  517. static Char *
  518. g_strchr(str, ch)
  519.     Char *str;
  520.     int ch;
  521. {
  522.     do {
  523.         if (*str == ch)
  524.             return (str);
  525.     } while (*str++);
  526.     return (NULL);
  527. }
  528.  
  529. static void
  530. g_Ctoc(str, buf)
  531.     register Char *str;
  532.     char *buf;
  533. {
  534.     register char *dc;
  535.  
  536.     for (dc = buf; *dc++ = *str++;);
  537. }
  538.  
  539. #ifdef DEBUG
  540. static void 
  541. qprintf(s)
  542.     register Char *s;
  543. {
  544.     register Char *p;
  545.  
  546.     for (p = s; *p; p++)
  547.         (void)printf("%c", *p & 0xff);
  548.     (void)printf("\n");
  549.     for (p = s; *p; p++)
  550.         (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
  551.     (void)printf("\n");
  552.     for (p = s; *p; p++)
  553.         (void)printf("%c", *p & M_META ? '_' : ' ');
  554.     (void)printf("\n");
  555. }
  556. #endif
  557.