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