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