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