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