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