ext/File/Glob/bsd_glob.c

   1 /*
   2  * Copyright (c) 1989, 1993
   3  *      The Regents of the University of California.  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 /*
  38  * Clause 3 above should be considered "deleted in its entirety".
  39  * For the actual notice of withdrawal, see:
  40  *    ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
  41  */
  42
  43 #if defined(LIBC_SCCS) && !defined(lint)
  44 static char sccsid[] = "@(#)glob.c      8.3 (Berkeley) 10/13/93";
  45 #endif /* LIBC_SCCS and not lint */
  46
  47 /*
  48  * glob(3) -- a superset of the one defined in POSIX 1003.2.
  49  *
  50  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
  51  *
  52  * Optional extra services, controlled by flags not defined by POSIX:
  53  *
  54  * GLOB_QUOTE:
  55  *      Escaping convention: \ inhibits any special meaning the following
  56  *      character might have (except \ at end of string is retained).
  57  * GLOB_MAGCHAR:
  58  *      Set in gl_flags if pattern contained a globbing character.
  59  * GLOB_NOMAGIC:
  60  *      Same as GLOB_NOCHECK, but it will only append pattern if it did
  61  *      not contain any magic characters.  [Used in csh style globbing]
  62  * GLOB_ALTDIRFUNC:
  63  *      Use alternately specified directory access functions.
  64  * GLOB_TILDE:
  65  *      expand ~user/foo to the /home/dir/of/user/foo
  66  * GLOB_BRACE:
  67  *      expand {1,2}{a,b} to 1a 1b 2a 2b
  68  * gl_matchc:
  69  *      Number of matches in the current invocation of glob.
  70  */
  71
  72 #include <EXTERN.h>
  73 #include <perl.h>
  74 #include "bsd_glob.h"
  75 #ifdef I_PWD
  76 #       include <pwd.h>
  77 #else
  78 #ifdef HAS_PASSWD
  79         struct passwd *getpwnam(char *);
  80         struct passwd *getpwuid(Uid_t);
  81 #endif
  82 #endif
  83
  84 #ifndef MAXPATHLEN
  85 #  ifdef PATH_MAX
  86 #    define     MAXPATHLEN      PATH_MAX
  87 #  else
  88 #    define     MAXPATHLEN      1024
  89 #  endif
  90 #endif
  91
  92 #define DOLLAR          '$'
  93 #define DOT             '.'
  94 #define EOS             '\0'
  95 #define LBRACKET        '['
  96 #define NOT             '!'
  97 #define QUESTION        '?'
  98 #define QUOTE           '\\'
  99 #define RANGE           '-'
 100 #define RBRACKET        ']'
 101 #define SEP             '/'
 102 #define STAR            '*'
 103 #define TILDE           '~'
 104 #define UNDERSCORE      '_'
 105 #define LBRACE          '{'
 106 #define RBRACE          '}'
 107 #define SLASH           '/'
 108 #define COMMA           ','
 109
 110 #ifndef GLOB_DEBUG
 111
 112 #define M_QUOTE         0x8000
 113 #define M_PROTECT       0x4000
 114 #define M_MASK          0xffff
 115 #define M_ASCII         0x00ff
 116
 117 typedef U16 Char;
 118
 119 #else
 120
 121 #define M_QUOTE         0x80
 122 #define M_PROTECT       0x40
 123 #define M_MASK          0xff
 124 #define M_ASCII         0x7f
 125
 126 typedef U8 Char;
 127
 128 #endif /* !GLOB_DEBUG */
 129
 130
 131 #define CHAR(c)         ((Char)((c)&M_ASCII))
 132 #define META(c)         ((Char)((c)|M_QUOTE))
 133 #define M_ALL           META('*')
 134 #define M_END           META(']')
 135 #define M_NOT           META('!')
 136 #define M_ONE           META('?')
 137 #define M_RNG           META('-')
 138 #define M_SET           META('[')
 139 #define ismeta(c)       (((c)&M_QUOTE) != 0)
 140
 141
 142 static int       compare(const void *, const void *);
 143 static void      g_Ctoc(const Char *, char *);
 144 static int       g_lstat(Char *, Stat_t *, glob_t *);
 145 static DIR      *g_opendir(Char *, glob_t *);
 146 static Char     *g_strchr(Char *, int);
 147 #ifdef notdef
 148 static Char     *g_strcat(Char *, const Char *);
 149 #endif
 150 static int       g_stat(Char *, Stat_t *, glob_t *);
 151 static int       glob0(const Char *, glob_t *);
 152 static int       glob1(Char *, glob_t *);
 153 static int       glob2(Char *, Char *, Char *, glob_t *);
 154 static int       glob3(Char *, Char *, Char *, Char *, glob_t *);
 155 static int       globextend(const Char *, glob_t *);
 156 static const Char *      globtilde(const Char *, Char *, glob_t *);
 157 static int       globexp1(const Char *, glob_t *);
 158 static int       globexp2(const Char *, const Char *, glob_t *, int *);
 159 static int       match(Char *, Char *, Char *);
 160 #ifdef GLOB_DEBUG
 161 static void      qprintf(const char *, Char *);
 162 #endif /* GLOB_DEBUG */
 163
 164 int
 165 bsd_glob(const char *pattern, int flags,
 166          int (*errfunc)(const char *, int), glob_t *pglob)
 167 {
 168         const U8 *patnext;
 169         int c;
 170         Char *bufnext, *bufend, patbuf[MAXPATHLEN+1];
 171
 172         patnext = (U8 *) pattern;
 173         if (!(flags & GLOB_APPEND)) {
 174                 pglob->gl_pathc = 0;
 175                 pglob->gl_pathv = NULL;
 176                 if (!(flags & GLOB_DOOFFS))
 177                         pglob->gl_offs = 0;
 178         }
 179         pglob->gl_flags = flags & ~GLOB_MAGCHAR;
 180         pglob->gl_errfunc = errfunc;
 181         pglob->gl_matchc = 0;
 182
 183         bufnext = patbuf;
 184         bufend = bufnext + MAXPATHLEN;
 185         if (flags & GLOB_QUOTE) {
 186                 /* Protect the quoted characters. */
 187                 while (bufnext < bufend && (c = *patnext++) != EOS)
 188                         if (c == QUOTE) {
 189                                 if ((c = *patnext++) == EOS) {
 190                                         c = QUOTE;
 191                                         --patnext;
 192                                 }
 193                                 *bufnext++ = c | M_PROTECT;
 194                         }
 195                         else
 196                                 *bufnext++ = c;
 197         }
 198         else
 199             while (bufnext < bufend && (c = *patnext++) != EOS)
 200                     *bufnext++ = c;
 201         *bufnext = EOS;
 202
 203         if (flags & GLOB_BRACE)
 204             return globexp1(patbuf, pglob);
 205         else
 206             return glob0(patbuf, pglob);
 207 }
 208
 209 /*
 210  * Expand recursively a glob {} pattern. When there is no more expansion
 211  * invoke the standard globbing routine to glob the rest of the magic
 212  * characters
 213  */
 214 static int globexp1(const Char *pattern, glob_t *pglob)
 215 {
 216         const Char* ptr = pattern;
 217         int rv;
 218
 219         /* Protect a single {}, for find(1), like csh */
 220         if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS)
 221                 return glob0(pattern, pglob);
 222
 223         while ((ptr = (const Char *) g_strchr((Char *) ptr, LBRACE)) != NULL)
 224                 if (!globexp2(ptr, pattern, pglob, &rv))
 225                         return rv;
 226
 227         return glob0(pattern, pglob);
 228 }
 229
 230
 231 /*
 232  * Recursive brace globbing helper. Tries to expand a single brace.
 233  * If it succeeds then it invokes globexp1 with the new pattern.
 234  * If it fails then it tries to glob the rest of the pattern and returns.
 235  */
 236 static int globexp2(const Char *ptr, const Char *pattern,
 237                     glob_t *pglob, int *rv)
 238 {
 239         int     i;
 240         Char   *lm, *ls;
 241         const Char *pe, *pm, *pl;
 242         Char    patbuf[MAXPATHLEN + 1];
 243
 244         /* copy part up to the brace */
 245         for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++)
 246                 continue;
 247         ls = lm;
 248
 249         /* Find the balanced brace */
 250         for (i = 0, pe = ++ptr; *pe; pe++)
 251                 if (*pe == LBRACKET) {
 252                         /* Ignore everything between [] */
 253                         for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++)
 254                                 continue;
 255                         if (*pe == EOS) {
 256                                 /*
 257                                  * We could not find a matching RBRACKET.
 258                                  * Ignore and just look for RBRACE
 259                                  */
 260                                 pe = pm;
 261                         }
 262                 }
 263                 else if (*pe == LBRACE)
 264                         i++;
 265                 else if (*pe == RBRACE) {
 266                         if (i == 0)
 267                                 break;
 268                         i--;
 269                 }
 270
 271         /* Non matching braces; just glob the pattern */
 272         if (i != 0 || *pe == EOS) {
 273                 *rv = glob0(patbuf, pglob);
 274                 return 0;
 275         }
 276
 277         for (i = 0, pl = pm = ptr; pm <= pe; pm++)
 278                 switch (*pm) {
 279                 case LBRACKET:
 280                         /* Ignore everything between [] */
 281                         for (pl = pm++; *pm != RBRACKET && *pm != EOS; pm++)
 282                                 continue;
 283                         if (*pm == EOS) {
 284                                 /*
 285                                  * We could not find a matching RBRACKET.
 286                                  * Ignore and just look for RBRACE
 287                                  */
 288                                 pm = pl;
 289                         }
 290                         break;
 291
 292                 case LBRACE:
 293                         i++;
 294                         break;
 295
 296                 case RBRACE:
 297                         if (i) {
 298                             i--;
 299                             break;
 300                         }
 301                         /* FALLTHROUGH */
 302                 case COMMA:
 303                         if (i && *pm == COMMA)
 304                                 break;
 305                         else {
 306                                 /* Append the current string */
 307                                 for (lm = ls; (pl < pm); *lm++ = *pl++)
 308                                         continue;
 309                                 /*
 310                                  * Append the rest of the pattern after the
 311                                  * closing brace
 312                                  */
 313                                 for (pl = pe + 1; (*lm++ = *pl++) != EOS;)
 314                                         continue;
 315
 316                                 /* Expand the current pattern */
 317 #ifdef GLOB_DEBUG
 318                                 qprintf("globexp2:", patbuf);
 319 #endif /* GLOB_DEBUG */
 320                                 *rv = globexp1(patbuf, pglob);
 321
 322                                 /* move after the comma, to the next string */
 323                                 pl = pm + 1;
 324                         }
 325                         break;
 326
 327                 default:
 328                         break;
 329                 }
 330         *rv = 0;
 331         return 0;
 332 }
 333
 334
 335
 336 /*
 337  * expand tilde from the passwd file.
 338  */
 339 static const Char *
 340 globtilde(const Char *pattern, Char *patbuf, glob_t *pglob)
 341 {
 342         struct passwd *pwd;
 343         char *h;
 344         const Char *p;
 345         Char *b;
 346
 347         if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE))
 348                 return pattern;
 349
 350         /* Copy up to the end of the string or / */
 351         for (p = pattern + 1, h = (char *) patbuf; *p && *p != SLASH;
 352              *h++ = *p++)
 353                 continue;
 354
 355         *h = EOS;
 356
 357         if (((char *) patbuf)[0] == EOS) {
 358                 /*
 359                  * handle a plain ~ or ~/ by expanding $HOME
 360                  * first and then trying the password file
 361                  */
 362                 if ((h = getenv("HOME")) == NULL) {
 363 #ifdef HAS_PASSWD
 364                         if ((pwd = getpwuid(getuid())) == NULL)
 365                                 return pattern;
 366                         else
 367                                 h = pwd->pw_dir;
 368 #else
 369                         return pattern;
 370 #endif
 371                 }
 372         }
 373         else {
 374                 /*
 375                  * Expand a ~user
 376                  */
 377 #ifdef HAS_PASSWD
 378                 if ((pwd = getpwnam((char*) patbuf)) == NULL)
 379                         return pattern;
 380                 else
 381                         h = pwd->pw_dir;
 382 #else
 383                 return pattern;
 384 #endif
 385         }
 386
 387         /* Copy the home directory */
 388         for (b = patbuf; *h; *b++ = *h++)
 389                 continue;
 390
 391         /* Append the rest of the pattern */
 392         while ((*b++ = *p++) != EOS)
 393                 continue;
 394
 395         return patbuf;
 396 }
 397
 398
 399 /*
 400  * The main glob() routine: compiles the pattern (optionally processing
 401  * quotes), calls glob1() to do the real pattern matching, and finally
 402  * sorts the list (unless unsorted operation is requested).  Returns 0
 403  * if things went well, nonzero if errors occurred.  It is not an error
 404  * to find no matches.
 405  */
 406 static int
 407 glob0(const Char *pattern, glob_t *pglob)
 408 {
 409         const Char *qpat, *qpatnext;
 410         int c, err, oldflags, oldpathc;
 411         Char *bufnext, patbuf[MAXPATHLEN+1];
 412
 413         qpat = globtilde(pattern, patbuf, pglob);
 414         qpatnext = qpat;
 415         oldflags = pglob->gl_flags;
 416         oldpathc = pglob->gl_pathc;
 417         bufnext = patbuf;
 418
 419         /* We don't need to check for buffer overflow any more. */
 420         while ((c = *qpatnext++) != EOS) {
 421                 switch (c) {
 422                 case LBRACKET:
 423                         c = *qpatnext;
 424                         if (c == NOT)
 425                                 ++qpatnext;
 426                         if (*qpatnext == EOS ||
 427                             g_strchr((Char *) qpatnext+1, RBRACKET) == NULL) {
 428                                 *bufnext++ = LBRACKET;
 429                                 if (c == NOT)
 430                                         --qpatnext;
 431                                 break;
 432                         }
 433                         *bufnext++ = M_SET;
 434                         if (c == NOT)
 435                                 *bufnext++ = M_NOT;
 436                         c = *qpatnext++;
 437                         do {
 438                                 *bufnext++ = CHAR(c);
 439                                 if (*qpatnext == RANGE &&
 440                                     (c = qpatnext[1]) != RBRACKET) {
 441                                         *bufnext++ = M_RNG;
 442                                         *bufnext++ = CHAR(c);
 443                                         qpatnext += 2;
 444                                 }
 445                         } while ((c = *qpatnext++) != RBRACKET);
 446                         pglob->gl_flags |= GLOB_MAGCHAR;
 447                         *bufnext++ = M_END;
 448                         break;
 449                 case QUESTION:
 450                         pglob->gl_flags |= GLOB_MAGCHAR;
 451                         *bufnext++ = M_ONE;
 452                         break;
 453                 case STAR:
 454                         pglob->gl_flags |= GLOB_MAGCHAR;
 455                         /* collapse adjacent stars to one,
 456                          * to avoid exponential behavior
 457                          */
 458                         if (bufnext == patbuf || bufnext[-1] != M_ALL)
 459                             *bufnext++ = M_ALL;
 460                         break;
 461                 default:
 462                         *bufnext++ = CHAR(c);
 463                         break;
 464                 }
 465         }
 466         *bufnext = EOS;
 467 #ifdef GLOB_DEBUG
 468         qprintf("glob0:", patbuf);
 469 #endif /* GLOB_DEBUG */
 470
 471         if ((err = glob1(patbuf, pglob)) != 0) {
 472                 pglob->gl_flags = oldflags;
 473                 return(err);
 474         }
 475
 476         /*
 477          * If there was no match we are going to append the pattern
 478          * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
 479          * and the pattern did not contain any magic characters
 480          * GLOB_NOMAGIC is there just for compatibility with csh.
 481          */
 482         if (pglob->gl_pathc == oldpathc &&
 483             ((pglob->gl_flags & GLOB_NOCHECK) ||
 484               ((pglob->gl_flags & GLOB_NOMAGIC) &&
 485                !(pglob->gl_flags & GLOB_MAGCHAR))))
 486         {
 487 #ifdef GLOB_DEBUG
 488                 printf("calling globextend from glob0\n");
 489 #endif /* GLOB_DEBUG */
 490                 pglob->gl_flags = oldflags;
 491                 return(globextend(qpat, pglob));
 492         }
 493         else if (!(pglob->gl_flags & GLOB_NOSORT))
 494                 qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
 495                     pglob->gl_pathc - oldpathc, sizeof(char *), compare);
 496         pglob->gl_flags = oldflags;
 497         return(0);
 498 }
 499
 500 static int
 501 compare(const void *p, const void *q)
 502 {
 503         return(strcmp(*(char **)p, *(char **)q));
 504 }
 505
 506 static int
 507 glob1(Char *pattern, glob_t *pglob)
 508 {
 509         Char pathbuf[MAXPATHLEN+1];
 510
 511         /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
 512         if (*pattern == EOS)
 513                 return(0);
 514         return(glob2(pathbuf, pathbuf, pattern, pglob));
 515 }
 516
 517 /*
 518  * The functions glob2 and glob3 are mutually recursive; there is one level
 519  * of recursion for each segment in the pattern that contains one or more
 520  * meta characters.
 521  */
 522 static int
 523 glob2(Char *pathbuf, Char *pathend, Char *pattern, glob_t *pglob)
 524 {
 525         Stat_t sb;
 526         Char *p, *q;
 527         int anymeta;
 528
 529         /*
 530          * Loop over pattern segments until end of pattern or until
 531          * segment with meta character found.
 532          */
 533         for (anymeta = 0;;) {
 534                 if (*pattern == EOS) {          /* End of pattern? */
 535                         *pathend = EOS;
 536
 537 #ifdef HAS_LSTAT
 538                         if (g_lstat(pathbuf, &sb, pglob))
 539                                 return(0);
 540 #endif /* HAS_LSTAT */
 541
 542                         if (((pglob->gl_flags & GLOB_MARK) &&
 543                             pathend[-1] != SEP) && (S_ISDIR(sb.st_mode)
 544                             || (S_ISLNK(sb.st_mode) &&
 545                             (g_stat(pathbuf, &sb, pglob) == 0) &&
 546                             S_ISDIR(sb.st_mode)))) {
 547                                 *pathend++ = SEP;
 548                                 *pathend = EOS;
 549                         }
 550                         ++pglob->gl_matchc;
 551 #ifdef GLOB_DEBUG
 552                         printf("calling globextend from glob2\n");
 553 #endif /* GLOB_DEBUG */
 554                         return(globextend(pathbuf, pglob));
 555                 }
 556
 557                 /* Find end of next segment, copy tentatively to pathend. */
 558                 q = pathend;
 559                 p = pattern;
 560                 while (*p != EOS && *p != SEP) {
 561                         if (ismeta(*p))
 562                                 anymeta = 1;
 563                         *q++ = *p++;
 564                 }
 565
 566                 if (!anymeta) {         /* No expansion, do next segment. */
 567                         pathend = q;
 568                         pattern = p;
 569                         while (*pattern == SEP)
 570                                 *pathend++ = *pattern++;
 571                 } else                  /* Need expansion, recurse. */
 572                         return(glob3(pathbuf, pathend, pattern, p, pglob));
 573         }
 574         /* NOTREACHED */
 575 }
 576
 577 static int
 578 glob3(Char *pathbuf, Char *pathend, Char *pattern,
 579       Char *restpattern, glob_t *pglob)
 580 {
 581         register Direntry_t *dp;
 582         DIR *dirp;
 583         int err;
 584         char buf[MAXPATHLEN];
 585
 586         /*
 587          * The readdirfunc declaration can't be prototyped, because it is
 588          * assigned, below, to two functions which are prototyped in glob.h
 589          * and dirent.h as taking pointers to differently typed opaque
 590          * structures.
 591          */
 592         Direntry_t *(*readdirfunc)();
 593
 594         *pathend = EOS;
 595         errno = 0;
 596
 597         if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
 598                 /* TODO: don't call for ENOENT or ENOTDIR? */
 599                 if (pglob->gl_errfunc) {
 600                         g_Ctoc(pathbuf, buf);
 601                         if (pglob->gl_errfunc(buf, errno) ||
 602                             (pglob->gl_flags & GLOB_ERR))
 603                                 return (GLOB_ABEND);
 604                 }
 605                 return(0);
 606         }
 607
 608         err = 0;
 609
 610         /* Search directory for matching names. */
 611         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 612                 readdirfunc = pglob->gl_readdir;
 613         else
 614                 readdirfunc = readdir;
 615         while ((dp = (*readdirfunc)(dirp))) {
 616                 register U8 *sc;
 617                 register Char *dc;
 618
 619                 /* Initial DOT must be matched literally. */
 620                 if (dp->d_name[0] == DOT && *pattern != DOT)
 621                         continue;
 622                 for (sc = (U8 *) dp->d_name, dc = pathend;
 623                      (*dc++ = *sc++) != EOS;)
 624                         continue;
 625                 if (!match(pathend, pattern, restpattern)) {
 626                         *pathend = EOS;
 627                         continue;
 628                 }
 629                 err = glob2(pathbuf, --dc, restpattern, pglob);
 630                 if (err)
 631                         break;
 632         }
 633
 634         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 635                 (*pglob->gl_closedir)(dirp);
 636         else
 637                 closedir(dirp);
 638         return(err);
 639 }
 640
 641
 642 /*
 643  * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
 644  * add the new item, and update gl_pathc.
 645  *
 646  * This assumes the BSD realloc, which only copies the block when its size
 647  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
 648  * behavior.
 649  *
 650  * Return 0 if new item added, error code if memory couldn't be allocated.
 651  *
 652  * Invariant of the glob_t structure:
 653  *      Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
 654  *      gl_pathv points to (gl_offs + gl_pathc + 1) items.
 655  */
 656 static int
 657 globextend(const Char *path, glob_t *pglob)
 658 {
 659         register char **pathv;
 660         register int i;
 661         Size_t newsize;
 662         char *copy;
 663         const Char *p;
 664
 665 #ifdef GLOB_DEBUG
 666         printf("Adding ");
 667         for (p = path; *p; p++)
 668                 (void)printf("%c", CHAR(*p));
 669         printf("\n");
 670 #endif GLOB_DEBUG
 671
 672         newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
 673         pathv = pglob->gl_pathv ?
 674                     realloc((char *)pglob->gl_pathv, newsize) :
 675                     malloc(newsize);
 676         if (pathv == NULL)
 677                 return(GLOB_NOSPACE);
 678
 679         if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
 680                 /* first time around -- clear initial gl_offs items */
 681                 pathv += pglob->gl_offs;
 682                 for (i = pglob->gl_offs; --i >= 0; )
 683                         *--pathv = NULL;
 684         }
 685         pglob->gl_pathv = pathv;
 686
 687         for (p = path; *p++;)
 688                 continue;
 689         if ((copy = malloc(p - path)) != NULL) {
 690                 g_Ctoc(path, copy);
 691                 pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
 692         }
 693         pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
 694         return(copy == NULL ? GLOB_NOSPACE : 0);
 695 }
 696
 697
 698 /*
 699  * pattern matching function for filenames.  Each occurrence of the *
 700  * pattern causes a recursion level.
 701  */
 702 static int
 703 match(register Char *name, register Char *pat, register Char *patend)
 704 {
 705         int ok, negate_range;
 706         Char c, k;
 707
 708         while (pat < patend) {
 709                 c = *pat++;
 710                 switch (c & M_MASK) {
 711                 case M_ALL:
 712                         if (pat == patend)
 713                                 return(1);
 714                         do
 715                             if (match(name, pat, patend))
 716                                     return(1);
 717                         while (*name++ != EOS);
 718                         return(0);
 719                 case M_ONE:
 720                         if (*name++ == EOS)
 721                                 return(0);
 722                         break;
 723                 case M_SET:
 724                         ok = 0;
 725                         if ((k = *name++) == EOS)
 726                                 return(0);
 727                         if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
 728                                 ++pat;
 729                         while (((c = *pat++) & M_MASK) != M_END)
 730                                 if ((*pat & M_MASK) == M_RNG) {
 731                                         if (c <= k && k <= pat[1])
 732                                                 ok = 1;
 733                                         pat += 2;
 734                                 } else if (c == k)
 735                                         ok = 1;
 736                         if (ok == negate_range)
 737                                 return(0);
 738                         break;
 739                 default:
 740                         if (*name++ != c)
 741                                 return(0);
 742                         break;
 743                 }
 744         }
 745         return(*name == EOS);
 746 }
 747
 748 /* Free allocated data belonging to a glob_t structure. */
 749 void
 750 bsd_globfree(glob_t *pglob)
 751 {
 752         register int i;
 753         register char **pp;
 754
 755         if (pglob->gl_pathv != NULL) {
 756                 pp = pglob->gl_pathv + pglob->gl_offs;
 757                 for (i = pglob->gl_pathc; i--; ++pp)
 758                         if (*pp)
 759                                 free(*pp);
 760                 free(pglob->gl_pathv);
 761         }
 762 }
 763
 764 static DIR *
 765 g_opendir(register Char *str, glob_t *pglob)
 766 {
 767         char buf[MAXPATHLEN];
 768
 769         if (!*str)
 770                 strcpy(buf, ".");
 771         else
 772                 g_Ctoc(str, buf);
 773
 774         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 775                 return((*pglob->gl_opendir)(buf));
 776
 777         return(opendir(buf));
 778 }
 779
 780 #ifdef HAS_LSTAT
 781 static int
 782 g_lstat(register Char *fn, Stat_t *sb, glob_t *pglob)
 783 {
 784         char buf[MAXPATHLEN];
 785
 786         g_Ctoc(fn, buf);
 787         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 788                 return((*pglob->gl_lstat)(buf, sb));
 789         return(lstat(buf, sb));
 790 }
 791 #endif /* HAS_LSTAT */
 792
 793 static int
 794 g_stat(register Char *fn, Stat_t *sb, glob_t *pglob)
 795 {
 796         char buf[MAXPATHLEN];
 797
 798         g_Ctoc(fn, buf);
 799         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 800                 return((*pglob->gl_stat)(buf, sb));
 801         return(stat(buf, sb));
 802 }
 803
 804 static Char *
 805 g_strchr(Char *str, int ch)
 806 {
 807         do {
 808                 if (*str == ch)
 809                         return (str);
 810         } while (*str++);
 811         return (NULL);
 812 }
 813
 814 #ifdef notdef
 815 static Char *
 816 g_strcat(Char *dst, const Char *src)
 817 {
 818         Char *sdst = dst;
 819
 820         while (*dst++)
 821                 continue;
 822         --dst;
 823         while((*dst++ = *src++) != EOS)
 824             continue;
 825
 826         return (sdst);
 827 }
 828 #endif
 829
 830 static void
 831 g_Ctoc(register const Char *str, char *buf)
 832 {
 833         register char *dc;
 834
 835         for (dc = buf; (*dc++ = *str++) != EOS;)
 836                 continue;
 837 }
 838
 839 #ifdef GLOB_DEBUG
 840 static void
 841 qprintf(const char *str, register Char *s)
 842 {
 843         register Char *p;
 844
 845         (void)printf("%s:\n", str);
 846         for (p = s; *p; p++)
 847                 (void)printf("%c", CHAR(*p));
 848         (void)printf("\n");
 849         for (p = s; *p; p++)
 850                 (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
 851         (void)printf("\n");
 852         for (p = s; *p; p++)
 853                 (void)printf("%c", ismeta(*p) ? '_' : ' ');
 854         (void)printf("\n");
 855 }
 856 #endif /* GLOB_DEBUG */