contrib/tcsh-6/glob.c

   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. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32 #if defined(LIBC_SCCS) && !defined(lint)
  33 static char sccsid[] = "@(#)glob.c      5.12 (Berkeley) 6/24/91";
  34 #endif /* LIBC_SCCS and not lint */
  35 /*
  36  * Glob: the interface is a superset of the one defined in POSIX 1003.2,
  37  * draft 9.
  38  *
  39  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
  40  *
  41  * Optional extra services, controlled by flags not defined by POSIX:
  42  *
  43  * GLOB_QUOTE:
  44  *      Escaping convention: \ inhibits any special meaning the following
  45  *      character might have (except \ at end of string is retained).
  46  * GLOB_MAGCHAR:
  47  *      Set in gl_flags if pattern contained a globbing character.
  48  * GLOB_ALTNOT:
  49  *      Use ^ instead of ! for "not".
  50  * gl_matchc:
  51  *      Number of matches in the current invocation of glob.
  52  */
  53
  54 #ifdef WINNT_NATIVE
  55         #pragma warning(disable:4244)
  56 #endif /* WINNT_NATIVE */
  57
  58 #define Char __Char
  59 #include "sh.h"
  60 #include "glob.h"
  61
  62 #undef Char
  63 #undef QUOTE
  64 #undef TILDE
  65 #undef META
  66 #undef ismeta
  67 #undef Strchr
  68
  69 #ifndef S_ISDIR
  70 #define S_ISDIR(a)      (((a) & S_IFMT) == S_IFDIR)
  71 #endif
  72
  73 #if !defined(S_ISLNK) && defined(S_IFLNK)
  74 #define S_ISLNK(a)      (((a) & S_IFMT) == S_IFLNK)
  75 #endif
  76
  77 #if !defined(S_ISLNK) && !defined(lstat)
  78 #define lstat stat
  79 #endif
  80
  81 typedef unsigned short Char;
  82
  83 static  int      glob1          (Char *, glob_t *, int);
  84 static  int      glob2          (struct strbuf *, const Char *, glob_t *, int);
  85 static  int      glob3          (struct strbuf *, const Char *, const Char *,
  86                                  const Char *, glob_t *, int);
  87 static  void     globextend     (const char *, glob_t *);
  88 static  int      match          (const char *, const Char *, const Char *,
  89                                  int);
  90 static  int      compare        (const void *, const void *);
  91 static  DIR     *Opendir        (const char *);
  92 #ifdef S_IFLNK
  93 static  int      Lstat          (const char *, struct stat *);
  94 #endif
  95 static  int      Stat           (const char *, struct stat *sb);
  96 static  Char    *Strchr         (Char *, int);
  97 #ifdef DEBUG
  98 static  void     qprintf        (const Char *);
  99 #endif
 100
 101 #define DOLLAR          '$'
 102 #define DOT             '.'
 103 #define EOS             '\0'
 104 #define LBRACKET        '['
 105 #define NOT             '!'
 106 #define ALTNOT          '^'
 107 #define QUESTION        '?'
 108 #define QUOTE           '\\'
 109 #define RANGE           '-'
 110 #define RBRACKET        ']'
 111 #define SEP             '/'
 112 #define STAR            '*'
 113 #define TILDE           '~'
 114 #define UNDERSCORE      '_'
 115
 116 #define M_META          0x8000
 117 #define M_PROTECT       0x4000
 118 #define M_MASK          0xffff
 119 #define M_ASCII         0x00ff
 120
 121 #define LCHAR(c)        ((c)&M_ASCII)
 122 #define META(c)         ((c)|M_META)
 123 #define M_ALL           META('*')
 124 #define M_END           META(']')
 125 #define M_NOT           META('!')
 126 #define M_ALTNOT        META('^')
 127 #define M_ONE           META('?')
 128 #define M_RNG           META('-')
 129 #define M_SET           META('[')
 130 #define ismeta(c)       (((c)&M_META) != 0)
 131
 132 int
 133 globcharcoll(__Char c1, __Char c2, int cs)
 134 {
 135 #if defined(NLS) && defined(LC_COLLATE) && defined(HAVE_STRCOLL)
 136 # if defined(WIDE_STRINGS)
 137     wchar_t s1[2], s2[2];
 138
 139     if (c1 == c2)
 140         return (0);
 141     if (cs) {
 142         c1 = towlower(c1);
 143         c2 = towlower(c2);
 144     } else {
 145         /* This should not be here, but I'll rather leave it in than engage in
 146            a LC_COLLATE flamewar about a shell I don't use... */
 147         if (iswlower(c1) && iswupper(c2))
 148             return (1);
 149         if (iswupper(c1) && iswlower(c2))
 150             return (-1);
 151     }
 152     s1[0] = c1;
 153     s2[0] = c2;
 154     s1[1] = s2[1] = '\0';
 155     return wcscoll(s1, s2);
 156 # else /* not WIDE_STRINGS */
 157     char s1[2], s2[2];
 158
 159     if (c1 == c2)
 160         return (0);
 161     /*
 162      * From kevin lyda <kevin@suberic.net>:
 163      * strcoll does not guarantee case sorting, so we pre-process now:
 164      */
 165     if (cs) {
 166         c1 = islower(c1) ? c1 : tolower(c1);
 167         c2 = islower(c2) ? c2 : tolower(c2);
 168     } else {
 169         if (islower(c1) && isupper(c2))
 170             return (1);
 171         if (isupper(c1) && islower(c2))
 172             return (-1);
 173     }
 174     s1[0] = c1;
 175     s2[0] = c2;
 176     s1[1] = s2[1] = '\0';
 177     return strcoll(s1, s2);
 178 # endif
 179 #else
 180     return (c1 - c2);
 181 #endif
 182 }
 183
 184 /*
 185  * Need to dodge two kernel bugs:
 186  * opendir("") != opendir(".")
 187  * NAMEI_BUG: on plain files trailing slashes are ignored in some kernels.
 188  *            POSIX specifies that they should be ignored in directories.
 189  */
 190
 191 static DIR *
 192 Opendir(const char *str)
 193 {
 194 #if defined(hpux) || defined(__hpux)
 195     struct stat st;
 196 #endif
 197
 198     if (!*str)
 199         return (opendir("."));
 200 #if defined(hpux) || defined(__hpux)
 201     /*
 202      * Opendir on some device files hangs, so avoid it
 203      */
 204     if (stat(str, &st) == -1 || !S_ISDIR(st.st_mode))
 205         return NULL;
 206 #endif
 207     return opendir(str);
 208 }
 209
 210 #ifdef S_IFLNK
 211 static int
 212 Lstat(const char *fn, struct stat *sb)
 213 {
 214     int st;
 215
 216     st = lstat(fn, sb);
 217 # ifdef NAMEI_BUG
 218     if (*fn != 0 && strend(fn)[-1] == '/' && !S_ISDIR(sb->st_mode))
 219         st = -1;
 220 # endif /* NAMEI_BUG */
 221     return st;
 222 }
 223 #else
 224 #define Lstat Stat
 225 #endif /* S_IFLNK */
 226
 227 static int
 228 Stat(const char *fn, struct stat *sb)
 229 {
 230     int st;
 231
 232     st = stat(fn, sb);
 233 #ifdef NAMEI_BUG
 234     if (*fn != 0 && strend(fn)[-1] == '/' && !S_ISDIR(sb->st_mode))
 235         st = -1;
 236 #endif /* NAMEI_BUG */
 237     return st;
 238 }
 239
 240 static Char *
 241 Strchr(Char *str, int ch)
 242 {
 243     do
 244         if (*str == ch)
 245             return (str);
 246     while (*str++);
 247     return (NULL);
 248 }
 249
 250 #ifdef DEBUG
 251 static void
 252 qprintf(const Char *s)
 253 {
 254     const Char *p;
 255
 256     for (p = s; *p; p++)
 257         printf("%c", *p & 0xff);
 258     printf("\n");
 259     for (p = s; *p; p++)
 260         printf("%c", *p & M_PROTECT ? '"' : ' ');
 261     printf("\n");
 262     for (p = s; *p; p++)
 263         printf("%c", *p & M_META ? '_' : ' ');
 264     printf("\n");
 265 }
 266 #endif /* DEBUG */
 267
 268 static int
 269 compare(const void *p, const void *q)
 270 {
 271 #if defined(NLS) && defined(HAVE_STRCOLL)
 272     return (strcoll(*(char *const *) p, *(char *const *) q));
 273 #else
 274     return (strcmp(*(char *const *) p, *(char *const *) q));
 275 #endif /* NLS && HAVE_STRCOLL */
 276 }
 277
 278 /*
 279  * The main glob() routine: compiles the pattern (optionally processing
 280  * quotes), calls glob1() to do the real pattern matching, and finally
 281  * sorts the list (unless unsorted operation is requested).  Returns 0
 282  * if things went well, nonzero if errors occurred.  It is not an error
 283  * to find no matches.
 284  */
 285 int
 286 glob(const char *pattern, int flags, int (*errfunc) (const char *, int),
 287      glob_t *pglob)
 288 {
 289     int     err, oldpathc;
 290     Char *bufnext, m_not;
 291     const unsigned char *patnext;
 292     int     c, not;
 293     Char *qpatnext, *patbuf;
 294     int     no_match;
 295
 296     patnext = (const unsigned char *) pattern;
 297     if (!(flags & GLOB_APPEND)) {
 298         pglob->gl_pathc = 0;
 299         pglob->gl_pathv = NULL;
 300         if (!(flags & GLOB_DOOFFS))
 301             pglob->gl_offs = 0;
 302     }
 303     pglob->gl_flags = flags & ~GLOB_MAGCHAR;
 304     pglob->gl_errfunc = errfunc;
 305     oldpathc = pglob->gl_pathc;
 306     pglob->gl_matchc = 0;
 307
 308     if (pglob->gl_flags & GLOB_ALTNOT) {
 309         not = ALTNOT;
 310         m_not = M_ALTNOT;
 311     }
 312     else {
 313         not = NOT;
 314         m_not = M_NOT;
 315     }
 316
 317     patbuf = xmalloc((strlen(pattern) + 1) * sizeof(*patbuf));
 318     bufnext = patbuf;
 319
 320     no_match = *patnext == not;
 321     if (no_match)
 322         patnext++;
 323
 324     if (flags & GLOB_QUOTE) {
 325         /* Protect the quoted characters */
 326         while ((c = *patnext++) != EOS) {
 327 #ifdef WIDE_STRINGS
 328             int len;
 329
 330             len = mblen((const char *)(patnext - 1), MB_LEN_MAX);
 331             if (len == -1)
 332                 TCSH_IGNORE(mblen(NULL, 0));
 333             else if (len > 1) {
 334                 *bufnext++ = (Char) c;
 335                 while (--len != 0)
 336                     *bufnext++ = (Char) (*patnext++ | M_PROTECT);
 337             } else
 338 #endif /* WIDE_STRINGS */
 339             if (c == QUOTE) {
 340                 if ((c = *patnext++) == EOS) {
 341                     c = QUOTE;
 342                     --patnext;
 343                 }
 344                 *bufnext++ = (Char) (c | M_PROTECT);
 345             }
 346             else
 347                 *bufnext++ = (Char) c;
 348         }
 349     }
 350     else
 351         while ((c = *patnext++) != EOS)
 352             *bufnext++ = (Char) c;
 353     *bufnext = EOS;
 354
 355     bufnext = patbuf;
 356     qpatnext = patbuf;
 357     while ((c = *qpatnext++) != EOS) {
 358         switch (c) {
 359         case LBRACKET:
 360             c = *qpatnext;
 361             if (c == not)
 362                 ++qpatnext;
 363             if (*qpatnext == EOS ||
 364                 Strchr(qpatnext + 1, RBRACKET) == NULL) {
 365                 *bufnext++ = LBRACKET;
 366                 if (c == not)
 367                     --qpatnext;
 368                 break;
 369             }
 370             pglob->gl_flags |= GLOB_MAGCHAR;
 371             *bufnext++ = M_SET;
 372             if (c == not)
 373                 *bufnext++ = m_not;
 374             c = *qpatnext++;
 375             do {
 376                 *bufnext++ = LCHAR(c);
 377                 if (*qpatnext == RANGE &&
 378                     (c = qpatnext[1]) != RBRACKET) {
 379                     *bufnext++ = M_RNG;
 380                     *bufnext++ = LCHAR(c);
 381                     qpatnext += 2;
 382                 }
 383             } while ((c = *qpatnext++) != RBRACKET);
 384             *bufnext++ = M_END;
 385             break;
 386         case QUESTION:
 387             pglob->gl_flags |= GLOB_MAGCHAR;
 388             *bufnext++ = M_ONE;
 389             break;
 390         case STAR:
 391             pglob->gl_flags |= GLOB_MAGCHAR;
 392             /* collapse adjacent stars to one [or three if globstar],
 393              * to avoid exponential behavior
 394              */
 395             if (bufnext == patbuf || bufnext[-1] != M_ALL ||
 396                ((flags & GLOB_STAR) != 0 &&
 397                  (bufnext - 1 == patbuf || bufnext[-2] != M_ALL ||
 398                  bufnext - 2 == patbuf || bufnext[-3] != M_ALL)))
 399                 *bufnext++ = M_ALL;
 400             break;
 401         default:
 402             *bufnext++ = LCHAR(c);
 403             break;
 404         }
 405     }
 406     *bufnext = EOS;
 407 #ifdef DEBUG
 408     qprintf(patbuf);
 409 #endif
 410
 411     if ((err = glob1(patbuf, pglob, no_match)) != 0) {
 412         xfree(patbuf);
 413         return (err);
 414     }
 415
 416     /*
 417      * If there was no match we are going to append the pattern
 418      * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
 419      * and the pattern did not contain any magic characters
 420      * GLOB_NOMAGIC is there just for compatibility with csh.
 421      */
 422     if (pglob->gl_pathc == oldpathc &&
 423         ((flags & GLOB_NOCHECK) ||
 424          ((flags & GLOB_NOMAGIC) && !(pglob->gl_flags & GLOB_MAGCHAR)))) {
 425         if (!(flags & GLOB_QUOTE))
 426             globextend(pattern, pglob);
 427         else {
 428             char *copy, *dest;
 429             const char *src;
 430
 431             /* copy pattern, interpreting quotes */
 432             copy = xmalloc(strlen(pattern) + 1);
 433             dest = copy;
 434             src = pattern;
 435             while (*src != EOS) {
 436                 /* Don't interpret quotes. The spec does not say we should do */
 437                 if (*src == QUOTE) {
 438                     if (*++src == EOS)
 439                         --src;
 440                 }
 441                 *dest++ = *src++;
 442             }
 443             *dest = EOS;
 444             globextend(copy, pglob);
 445             xfree(copy);
 446         }
 447         xfree(patbuf);
 448         return 0;
 449     }
 450     else if (!(flags & GLOB_NOSORT) && (pglob->gl_pathc != oldpathc))
 451         qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
 452               pglob->gl_pathc - oldpathc, sizeof(char *), compare);
 453     xfree(patbuf);
 454     return (0);
 455 }
 456
 457 static int
 458 glob1(Char *pattern, glob_t *pglob, int no_match)
 459 {
 460     struct strbuf pathbuf = strbuf_INIT;
 461     int err;
 462
 463     /*
 464      * a null pathname is invalid -- POSIX 1003.1 sect. 2.4.
 465      */
 466     if (*pattern == EOS)
 467         return (0);
 468     err = glob2(&pathbuf, pattern, pglob, no_match);
 469     xfree(pathbuf.s);
 470     return err;
 471 }
 472
 473 /*
 474  * functions glob2 and glob3 are mutually recursive; there is one level
 475  * of recursion for each segment in the pattern that contains one or
 476  * more meta characters.
 477  */
 478 static int
 479 glob2(struct strbuf *pathbuf, const Char *pattern, glob_t *pglob, int no_match)
 480 {
 481     struct stat sbuf;
 482     int anymeta;
 483     const Char *p;
 484     size_t orig_len;
 485
 486     /*
 487      * loop over pattern segments until end of pattern or until segment with
 488      * meta character found.
 489      */
 490     anymeta = 0;
 491     for (;;) {
 492         if (*pattern == EOS) {  /* end of pattern? */
 493             strbuf_terminate(pathbuf);
 494
 495             if (Lstat(pathbuf->s, &sbuf))
 496                 return (0);
 497
 498             if (((pglob->gl_flags & GLOB_MARK) &&
 499                  pathbuf->s[pathbuf->len - 1] != SEP) &&
 500                 (S_ISDIR(sbuf.st_mode)
 501 #ifdef S_IFLNK
 502                  || (S_ISLNK(sbuf.st_mode) &&
 503                      (Stat(pathbuf->s, &sbuf) == 0) &&
 504                      S_ISDIR(sbuf.st_mode))
 505 #endif
 506                  )) {
 507                 strbuf_append1(pathbuf, SEP);
 508                 strbuf_terminate(pathbuf);
 509             }
 510             ++pglob->gl_matchc;
 511             globextend(pathbuf->s, pglob);
 512             return 0;
 513         }
 514
 515         /* find end of next segment, tentatively copy to pathbuf */
 516         p = pattern;
 517         orig_len = pathbuf->len;
 518         while (*p != EOS && *p != SEP) {
 519             if (ismeta(*p))
 520                 anymeta = 1;
 521             strbuf_append1(pathbuf, *p++);
 522         }
 523
 524         if (!anymeta) {         /* no expansion, do next segment */
 525             pattern = p;
 526             while (*pattern == SEP)
 527                 strbuf_append1(pathbuf, *pattern++);
 528         }
 529         else {                  /* need expansion, recurse */
 530             pathbuf->len = orig_len;
 531             return (glob3(pathbuf, pattern, p, pattern, pglob, no_match));
 532         }
 533     }
 534     /* NOTREACHED */
 535 }
 536
 537 static size_t
 538 One_Char_mbtowc(__Char *pwc, const Char *s, size_t n)
 539 {
 540 #ifdef WIDE_STRINGS
 541     char buf[MB_LEN_MAX], *p;
 542
 543     if (n > MB_LEN_MAX)
 544         n = MB_LEN_MAX;
 545     p = buf;
 546     while (p < buf + n && (*p++ = LCHAR(*s++)) != 0)
 547         ;
 548     return one_mbtowc(pwc, buf, n);
 549 #else
 550     *pwc = *s & CHAR;
 551     return 1;
 552 #endif
 553 }
 554
 555 static int
 556 glob3(struct strbuf *pathbuf, const Char *pattern, const Char *restpattern,
 557       const Char *pglobstar, glob_t *pglob, int no_match)
 558 {
 559     DIR    *dirp;
 560     struct dirent *dp;
 561     struct stat sbuf;
 562     int     err;
 563     Char m_not = (pglob->gl_flags & GLOB_ALTNOT) ? M_ALTNOT : M_NOT;
 564     size_t orig_len;
 565     int globstar = 0;
 566     int chase_symlinks = 0;
 567     const Char *termstar = NULL;
 568
 569     strbuf_terminate(pathbuf);
 570     orig_len = pathbuf->len;
 571     errno = err = 0;
 572
 573     while (pglobstar < restpattern) {
 574         __Char wc;
 575         size_t width = One_Char_mbtowc(&wc, pglobstar, MB_LEN_MAX);
 576         if ((pglobstar[0] & M_MASK) == M_ALL &&
 577             (pglobstar[width] & M_MASK) == M_ALL) {
 578             globstar = 1;
 579             chase_symlinks = (pglobstar[2 * width] & M_MASK) == M_ALL;
 580             termstar = pglobstar + (2 + chase_symlinks) * width;
 581             break;
 582         }
 583         pglobstar += width;
 584     }
 585
 586     if (globstar) {
 587         err = pglobstar==pattern && termstar==restpattern ?
 588                 *restpattern == EOS ?
 589                 glob2(pathbuf, restpattern - 1, pglob, no_match) :
 590                 glob2(pathbuf, restpattern + 1, pglob, no_match) :
 591                 glob3(pathbuf, pattern, restpattern, termstar, pglob, no_match);
 592         if (err)
 593             return err;
 594         pathbuf->len = orig_len;
 595         strbuf_terminate(pathbuf);
 596     }
 597
 598     if (*pathbuf->s && (Lstat(pathbuf->s, &sbuf) || !S_ISDIR(sbuf.st_mode)
 599 #ifdef S_IFLINK
 600              && ((globstar && !chase_symlinks) || !S_ISLNK(sbuf.st_mode))
 601 #endif
 602         ))
 603         return 0;
 604
 605     if (!(dirp = Opendir(pathbuf->s))) {
 606         /* todo: don't call for ENOENT or ENOTDIR? */
 607         if ((pglob->gl_errfunc && (*pglob->gl_errfunc) (pathbuf->s, errno)) ||
 608             (pglob->gl_flags & GLOB_ERR))
 609             return (GLOB_ABEND);
 610         else
 611             return (0);
 612     }
 613
 614     /* search directory for matching names */
 615     while ((dp = readdir(dirp)) != NULL) {
 616         /* initial DOT must be matched literally */
 617         if (dp->d_name[0] == DOT && *pattern != DOT)
 618             if (!(pglob->gl_flags & GLOB_DOT) || !dp->d_name[1] ||
 619                 (dp->d_name[1] == DOT && !dp->d_name[2]))
 620                 continue; /*unless globdot and not . or .. */
 621         pathbuf->len = orig_len;
 622         strbuf_append(pathbuf, dp->d_name);
 623         strbuf_terminate(pathbuf);
 624
 625         if (globstar) {
 626 #ifdef S_IFLNK
 627             if (!chase_symlinks &&
 628                 (Lstat(pathbuf->s, &sbuf) || S_ISLNK(sbuf.st_mode)))
 629                     continue;
 630 #endif
 631             if (match(pathbuf->s + orig_len, pattern, termstar,
 632                 (int)m_not) == no_match)
 633                     continue;
 634             strbuf_append1(pathbuf, SEP);
 635             strbuf_terminate(pathbuf);
 636             if ((err = glob2(pathbuf, pglobstar, pglob, no_match)) != 0)
 637                 break;
 638         } else {
 639             if (match(pathbuf->s + orig_len, pattern, restpattern,
 640                 (int) m_not) == no_match)
 641                 continue;
 642             if ((err = glob2(pathbuf, restpattern, pglob, no_match)) != 0)
 643                 break;
 644         }
 645     }
 646     /* todo: check error from readdir? */
 647     closedir(dirp);
 648     return (err);
 649 }
 650
 651
 652 /*
 653  * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
 654  * add the new item, and update gl_pathc.
 655  *
 656  * This assumes the BSD realloc, which only copies the block when its size
 657  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
 658  * behavior.
 659  *
 660  * Return 0 if new item added, error code if memory couldn't be allocated.
 661  *
 662  * Invariant of the glob_t structure:
 663  *      Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
 664  *       gl_pathv points to (gl_offs + gl_pathc + 1) items.
 665  */
 666 static void
 667 globextend(const char *path, glob_t *pglob)
 668 {
 669     char **pathv;
 670     int i;
 671     size_t newsize;
 672
 673     newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
 674     pathv = xrealloc(pglob->gl_pathv, newsize);
 675
 676     if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
 677         /* first time around -- clear initial gl_offs items */
 678         pathv += pglob->gl_offs;
 679         for (i = pglob->gl_offs; --i >= 0;)
 680             *--pathv = NULL;
 681     }
 682     pglob->gl_pathv = pathv;
 683
 684     pathv[pglob->gl_offs + pglob->gl_pathc++] = strsave(path);
 685     pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
 686 }
 687
 688 /*
 689  * pattern matching function for filenames.  Each occurrence of the *
 690  * pattern causes a recursion level.
 691  */
 692 static  int
 693 match(const char *name, const Char *pat, const Char *patend, int m_not)
 694 {
 695     int ok, negate_range;
 696     Char c;
 697
 698     while (pat < patend) {
 699         size_t lwk;
 700         __Char wc, wk;
 701
 702         c = *pat; /* Only for M_MASK bits */
 703         pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
 704         lwk = one_mbtowc(&wk, name, MB_LEN_MAX);
 705         switch (c & M_MASK) {
 706         case M_ALL:
 707             while (pat < patend && (*pat & M_MASK) == M_ALL)  /* eat consecutive '*' */
 708                 pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
 709             if (pat == patend)
 710                 return (1);
 711             while (!match(name, pat, patend, m_not)) {
 712                 if (*name == EOS)
 713                     return (0);
 714                 name += lwk;
 715                 lwk = one_mbtowc(&wk, name, MB_LEN_MAX);
 716             }
 717             return (1);
 718         case M_ONE:
 719             if (*name == EOS)
 720                 return (0);
 721             name += lwk;
 722             break;
 723         case M_SET:
 724             ok = 0;
 725             if (*name == EOS)
 726                 return (0);
 727             name += lwk;
 728             if ((negate_range = ((*pat & M_MASK) == m_not)) != 0)
 729                 ++pat;
 730             while ((*pat & M_MASK) != M_END) {
 731                 pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
 732                 if ((*pat & M_MASK) == M_RNG) {
 733                     __Char wc2;
 734
 735                     pat++;
 736                     pat += One_Char_mbtowc(&wc2, pat, MB_LEN_MAX);
 737                     if (globcharcoll(wc, wk, 0) <= 0 &&
 738                         globcharcoll(wk, wc2, 0) <= 0)
 739                         ok = 1;
 740                 } else if (wc == wk)
 741                     ok = 1;
 742             }
 743             pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
 744             if (ok == negate_range)
 745                 return (0);
 746             break;
 747         default:
 748             if (*name == EOS || samecase(wk) != samecase(wc))
 749                 return (0);
 750             name += lwk;
 751             break;
 752         }
 753     }
 754     return (*name == EOS);
 755 }
 756
 757 /* free allocated data belonging to a glob_t structure */
 758 void
 759 globfree(glob_t *pglob)
 760 {
 761     int i;
 762     char **pp;
 763
 764     if (pglob->gl_pathv != NULL) {
 765         pp = pglob->gl_pathv + pglob->gl_offs;
 766         for (i = pglob->gl_pathc; i--; ++pp)
 767             if (*pp)
 768                 xfree(*pp), *pp = NULL;
 769         xfree(pglob->gl_pathv), pglob->gl_pathv = NULL;
 770     }
 771 }