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