glob.c revision 74307 
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 * $FreeBSD: head/lib/libc/gen/glob.c 74307 2001-03-15 18:50:32Z jlemon $
37 */
38
39#if defined(LIBC_SCCS) && !defined(lint)
40static char sccsid[] = "@(#)glob.c	8.3 (Berkeley) 10/13/93";
41#endif /* LIBC_SCCS and not lint */
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 MAX_GLOBENTRIES	10000		/* limit number of entries */
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
110typedef 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
119typedef 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
135static int	 compare __P((const void *, const void *));
136static void	 g_Ctoc __P((const Char *, char *));
137static int	 g_lstat __P((Char *, struct stat *, glob_t *));
138static DIR	*g_opendir __P((Char *, glob_t *));
139static Char	*g_strchr __P((Char *, int));
140#ifdef notdef
141static Char	*g_strcat __P((Char *, const Char *));
142#endif
143static int	 g_stat __P((Char *, struct stat *, glob_t *));
144static int	 glob0 __P((const Char *, glob_t *));
145static int	 glob1 __P((Char *, glob_t *));
146static int	 glob2 __P((Char *, Char *, Char *, glob_t *));
147static int	 glob3 __P((Char *, Char *, Char *, Char *, glob_t *));
148static int	 globextend __P((const Char *, glob_t *));
149static const Char *	 globtilde __P((const Char *, Char *, size_t, glob_t *));
150static int	 globexp1 __P((const Char *, glob_t *));
151static int	 globexp2 __P((const Char *, const Char *, glob_t *, int *));
152static int	 match __P((Char *, Char *, Char *));
153#ifdef DEBUG
154static void	 qprintf __P((const char *, Char *));
155#endif
156
157int
158glob(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 */
209static 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 */
233static 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 */
338static const Char *
339globtilde(pattern, patbuf, patbuf_len, pglob)
340	const Char *pattern;
341	Char *patbuf;
342	size_t patbuf_len;
343	glob_t *pglob;
344{
345	struct passwd *pwd;
346	char *h;
347	const Char *p;
348	Char *b, *eb;
349
350	if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE))
351		return pattern;
352
353	/*
354	 * Copy up to the end of the string or /
355	 */
356	eb = &patbuf[patbuf_len - 1];
357	for (p = pattern + 1, h = (char *) patbuf;
358	    h < (char *)eb && *p && *p != SLASH; *h++ = *p++)
359		continue;
360
361	*h = EOS;
362
363	if (((char *) patbuf)[0] == EOS) {
364		/*
365		 * handle a plain ~ or ~/ by expanding $HOME first (iff
366		 * we're not running setuid or setgid) and then trying
367		 * the password file
368		 */
369		if (
370#ifndef	__NETBSD_SYSCALLS
371		    issetugid() != 0 ||
372#endif
373		    (h = getenv("HOME")) == NULL) {
374			if (((h = getlogin()) != NULL &&
375			     (pwd = getpwnam(h)) != NULL) ||
376			    (pwd = getpwuid(getuid())) != NULL)
377				h = pwd->pw_dir;
378			else
379				return pattern;
380		}
381	}
382	else {
383		/*
384		 * Expand a ~user
385		 */
386		if ((pwd = getpwnam((char*) patbuf)) == NULL)
387			return pattern;
388		else
389			h = pwd->pw_dir;
390	}
391
392	/* Copy the home directory */
393	for (b = patbuf; b < eb && *h; *b++ = *h++)
394		continue;
395
396	/* Append the rest of the pattern */
397	while (b < eb && (*b++ = *p++) != EOS)
398		continue;
399	*b = EOS;
400
401	return patbuf;
402}
403
404
405/*
406 * The main glob() routine: compiles the pattern (optionally processing
407 * quotes), calls glob1() to do the real pattern matching, and finally
408 * sorts the list (unless unsorted operation is requested).  Returns 0
409 * if things went well, nonzero if errors occurred.  It is not an error
410 * to find no matches.
411 */
412static int
413glob0(pattern, pglob)
414	const Char *pattern;
415	glob_t *pglob;
416{
417	const Char *qpatnext;
418	int c, err, oldpathc;
419	Char *bufnext, patbuf[MAXPATHLEN+1];
420
421	qpatnext = globtilde(pattern, patbuf, sizeof(patbuf) / sizeof(Char),
422	    pglob);
423	oldpathc = pglob->gl_pathc;
424	bufnext = patbuf;
425
426	/* We don't need to check for buffer overflow any more. */
427	while ((c = *qpatnext++) != EOS) {
428		switch (c) {
429		case LBRACKET:
430			c = *qpatnext;
431			if (c == NOT)
432				++qpatnext;
433			if (*qpatnext == EOS ||
434			    g_strchr((Char *) qpatnext+1, RBRACKET) == NULL) {
435				*bufnext++ = LBRACKET;
436				if (c == NOT)
437					--qpatnext;
438				break;
439			}
440			*bufnext++ = M_SET;
441			if (c == NOT)
442				*bufnext++ = M_NOT;
443			c = *qpatnext++;
444			do {
445				*bufnext++ = CHAR(c);
446				if (*qpatnext == RANGE &&
447				    (c = qpatnext[1]) != RBRACKET) {
448					*bufnext++ = M_RNG;
449					*bufnext++ = CHAR(c);
450					qpatnext += 2;
451				}
452			} while ((c = *qpatnext++) != RBRACKET);
453			pglob->gl_flags |= GLOB_MAGCHAR;
454			*bufnext++ = M_END;
455			break;
456		case QUESTION:
457			pglob->gl_flags |= GLOB_MAGCHAR;
458			*bufnext++ = M_ONE;
459			break;
460		case STAR:
461			pglob->gl_flags |= GLOB_MAGCHAR;
462			/* collapse adjacent stars to one,
463			 * to avoid exponential behavior
464			 */
465			if (bufnext == patbuf || bufnext[-1] != M_ALL)
466			    *bufnext++ = M_ALL;
467			break;
468		default:
469			*bufnext++ = CHAR(c);
470			break;
471		}
472	}
473	*bufnext = EOS;
474#ifdef DEBUG
475	qprintf("glob0:", patbuf);
476#endif
477
478	if ((err = glob1(patbuf, pglob)) != 0)
479		return(err);
480
481	/*
482	 * If there was no match we are going to append the pattern
483	 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
484	 * and the pattern did not contain any magic characters
485	 * GLOB_NOMAGIC is there just for compatibility with csh.
486	 */
487	if (pglob->gl_pathc == oldpathc &&
488	    ((pglob->gl_flags & GLOB_NOCHECK) ||
489	      ((pglob->gl_flags & GLOB_NOMAGIC) &&
490	       !(pglob->gl_flags & GLOB_MAGCHAR))))
491		return(globextend(pattern, pglob));
492	else if (!(pglob->gl_flags & GLOB_NOSORT))
493		qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
494		    pglob->gl_pathc - oldpathc, sizeof(char *), compare);
495	return(0);
496}
497
498static int
499compare(p, q)
500	const void *p, *q;
501{
502	return(strcmp(*(char **)p, *(char **)q));
503}
504
505static int
506glob1(pattern, pglob)
507	Char *pattern;
508	glob_t *pglob;
509{
510	Char pathbuf[MAXPATHLEN+1];
511
512	/* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
513	if (*pattern == EOS)
514		return(0);
515	return(glob2(pathbuf, pathbuf, pattern, pglob));
516}
517
518/*
519 * The functions glob2 and glob3 are mutually recursive; there is one level
520 * of recursion for each segment in the pattern that contains one or more
521 * meta characters.
522 */
523static int
524glob2(pathbuf, pathend, pattern, pglob)
525	Char *pathbuf, *pathend, *pattern;
526	glob_t *pglob;
527{
528	struct stat sb;
529	Char *p, *q;
530	int anymeta;
531
532	/*
533	 * Loop over pattern segments until end of pattern or until
534	 * segment with meta character found.
535	 */
536	for (anymeta = 0;;) {
537		if (*pattern == EOS) {		/* End of pattern? */
538			*pathend = EOS;
539			if (g_lstat(pathbuf, &sb, pglob))
540				return(0);
541
542			if (((pglob->gl_flags & GLOB_MARK) &&
543			    pathend[-1] != SEP) && (S_ISDIR(sb.st_mode)
544			    || (S_ISLNK(sb.st_mode) &&
545			    (g_stat(pathbuf, &sb, pglob) == 0) &&
546			    S_ISDIR(sb.st_mode)))) {
547				*pathend++ = SEP;
548				*pathend = EOS;
549			}
550			++pglob->gl_matchc;
551			return(globextend(pathbuf, pglob));
552		}
553
554		/* Find end of next segment, copy tentatively to pathend. */
555		q = pathend;
556		p = pattern;
557		while (*p != EOS && *p != SEP) {
558			if (ismeta(*p))
559				anymeta = 1;
560			*q++ = *p++;
561		}
562
563		if (!anymeta) {		/* No expansion, do next segment. */
564			pathend = q;
565			pattern = p;
566			while (*pattern == SEP)
567				*pathend++ = *pattern++;
568		} else			/* Need expansion, recurse. */
569			return(glob3(pathbuf, pathend, pattern, p, pglob));
570	}
571	/* NOTREACHED */
572}
573
574static int
575glob3(pathbuf, pathend, pattern, restpattern, pglob)
576	Char *pathbuf, *pathend, *pattern, *restpattern;
577	glob_t *pglob;
578{
579	register struct dirent *dp;
580	DIR *dirp;
581	int err;
582	char buf[MAXPATHLEN];
583
584	/*
585	 * The readdirfunc declaration can't be prototyped, because it is
586	 * assigned, below, to two functions which are prototyped in glob.h
587	 * and dirent.h as taking pointers to differently typed opaque
588	 * structures.
589	 */
590	struct dirent *(*readdirfunc)();
591
592	*pathend = EOS;
593	errno = 0;
594
595	if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
596		/* TODO: don't call for ENOENT or ENOTDIR? */
597		if (pglob->gl_errfunc) {
598			g_Ctoc(pathbuf, buf);
599			if (pglob->gl_errfunc(buf, errno) ||
600			    pglob->gl_flags & GLOB_ERR)
601				return (GLOB_ABEND);
602		}
603		return(0);
604	}
605
606	err = 0;
607
608	/* Search directory for matching names. */
609	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
610		readdirfunc = pglob->gl_readdir;
611	else
612		readdirfunc = readdir;
613	while ((dp = (*readdirfunc)(dirp))) {
614		register u_char *sc;
615		register Char *dc;
616
617		/* Initial DOT must be matched literally. */
618		if (dp->d_name[0] == DOT && *pattern != DOT)
619			continue;
620		for (sc = (u_char *) dp->d_name, dc = pathend;
621		     (*dc++ = *sc++) != EOS;)
622			continue;
623		if (!match(pathend, pattern, restpattern)) {
624			*pathend = EOS;
625			continue;
626		}
627		err = glob2(pathbuf, --dc, restpattern, pglob);
628		if (err)
629			break;
630	}
631
632	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
633		(*pglob->gl_closedir)(dirp);
634	else
635		closedir(dirp);
636	return(err);
637}
638
639
640/*
641 * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
642 * add the new item, and update gl_pathc.
643 *
644 * This assumes the BSD realloc, which only copies the block when its size
645 * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
646 * behavior.
647 *
648 * Return 0 if new item added, error code if memory couldn't be allocated.
649 *
650 * Invariant of the glob_t structure:
651 *	Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
652 *	gl_pathv points to (gl_offs + gl_pathc + 1) items.
653 */
654static int
655globextend(path, pglob)
656	const Char *path;
657	glob_t *pglob;
658{
659	register char **pathv;
660	register int i;
661	u_int newsize;
662	char *copy;
663	const Char *p;
664
665	if (pglob->gl_pathc > MAX_GLOBENTRIES)
666		return (GLOB_ABEND);
667
668	newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
669	pathv = pglob->gl_pathv ?
670		    realloc((char *)pglob->gl_pathv, newsize) :
671		    malloc(newsize);
672	if (pathv == NULL)
673		return(GLOB_NOSPACE);
674
675	if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
676		/* first time around -- clear initial gl_offs items */
677		pathv += pglob->gl_offs;
678		for (i = pglob->gl_offs; --i >= 0; )
679			*--pathv = NULL;
680	}
681	pglob->gl_pathv = pathv;
682
683	for (p = path; *p++;)
684		continue;
685	if ((copy = malloc(p - path)) != NULL) {
686		g_Ctoc(path, copy);
687		pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
688	}
689	pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
690	return(copy == NULL ? GLOB_NOSPACE : 0);
691}
692
693/*
694 * pattern matching function for filenames.  Each occurrence of the *
695 * pattern causes a recursion level.
696 */
697static int
698match(name, pat, patend)
699	register Char *name, *pat, *patend;
700{
701	int ok, negate_range;
702	Char c, k;
703
704	while (pat < patend) {
705		c = *pat++;
706		switch (c & M_MASK) {
707		case M_ALL:
708			if (pat == patend)
709				return(1);
710			do
711			    if (match(name, pat, patend))
712				    return(1);
713			while (*name++ != EOS);
714			return(0);
715		case M_ONE:
716			if (*name++ == EOS)
717				return(0);
718			break;
719		case M_SET:
720			ok = 0;
721			if ((k = *name++) == EOS)
722				return(0);
723			if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
724				++pat;
725			while (((c = *pat++) & M_MASK) != M_END)
726				if ((*pat & M_MASK) == M_RNG) {
727					if (__collate_load_error ?
728					    CHAR(c) <= CHAR(k) && CHAR(k) <= CHAR(pat[1]) :
729					       __collate_range_cmp(CHAR(c), CHAR(k)) <= 0
730					    && __collate_range_cmp(CHAR(k), CHAR(pat[1])) <= 0
731					   )
732						ok = 1;
733					pat += 2;
734				} else if (c == k)
735					ok = 1;
736			if (ok == negate_range)
737				return(0);
738			break;
739		default:
740			if (*name++ != c)
741				return(0);
742			break;
743		}
744	}
745	return(*name == EOS);
746}
747
748/* Free allocated data belonging to a glob_t structure. */
749void
750globfree(pglob)
751	glob_t *pglob;
752{
753	register int i;
754	register char **pp;
755
756	if (pglob->gl_pathv != NULL) {
757		pp = pglob->gl_pathv + pglob->gl_offs;
758		for (i = pglob->gl_pathc; i--; ++pp)
759			if (*pp)
760				free(*pp);
761		free(pglob->gl_pathv);
762	}
763}
764
765static DIR *
766g_opendir(str, pglob)
767	register Char *str;
768	glob_t *pglob;
769{
770	char buf[MAXPATHLEN];
771
772	if (!*str)
773		strcpy(buf, ".");
774	else
775		g_Ctoc(str, buf);
776
777	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
778		return((*pglob->gl_opendir)(buf));
779
780	return(opendir(buf));
781}
782
783static int
784g_lstat(fn, sb, pglob)
785	register Char *fn;
786	struct stat *sb;
787	glob_t *pglob;
788{
789	char buf[MAXPATHLEN];
790
791	g_Ctoc(fn, buf);
792	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
793		return((*pglob->gl_lstat)(buf, sb));
794	return(lstat(buf, sb));
795}
796
797static int
798g_stat(fn, sb, pglob)
799	register Char *fn;
800	struct stat *sb;
801	glob_t *pglob;
802{
803	char buf[MAXPATHLEN];
804
805	g_Ctoc(fn, buf);
806	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
807		return((*pglob->gl_stat)(buf, sb));
808	return(stat(buf, sb));
809}
810
811static Char *
812g_strchr(str, ch)
813	Char *str;
814	int ch;
815{
816	do {
817		if (*str == ch)
818			return (str);
819	} while (*str++);
820	return (NULL);
821}
822
823#ifdef notdef
824static Char *
825g_strcat(dst, src)
826	Char *dst;
827	const Char* src;
828{
829	Char *sdst = dst;
830
831	while (*dst++)
832		continue;
833	--dst;
834	while((*dst++ = *src++) != EOS)
835	    continue;
836
837	return (sdst);
838}
839#endif
840
841static void
842g_Ctoc(str, buf)
843	register const Char *str;
844	char *buf;
845{
846	register char *dc;
847
848	for (dc = buf; (*dc++ = *str++) != EOS;)
849		continue;
850}
851
852#ifdef DEBUG
853static void
854qprintf(str, s)
855	const char *str;
856	register Char *s;
857{
858	register Char *p;
859
860	(void)printf("%s:\n", str);
861	for (p = s; *p; p++)
862		(void)printf("%c", CHAR(*p));
863	(void)printf("\n");
864	for (p = s; *p; p++)
865		(void)printf("%c", *p & M_PROTECT ? '"' : ' ');
866	(void)printf("\n");
867	for (p = s; *p; p++)
868		(void)printf("%c", ismeta(*p) ? '_' : ' ');
869	(void)printf("\n");
870}
871#endif
872