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