glob.c revision 304276 
1/*
2 * Copyright (c) 1989 The Regents of the University of California.
3 * 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#if defined(LIBC_SCCS) && !defined(lint)
33static char sccsid[] = "@(#)glob.c	5.12 (Berkeley) 6/24/91";
34#endif /* LIBC_SCCS and not lint */
35/*
36 * Glob: the interface is a superset of the one defined in POSIX 1003.2,
37 * draft 9.
38 *
39 * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
40 *
41 * Optional extra services, controlled by flags not defined by POSIX:
42 *
43 * GLOB_QUOTE:
44 *	Escaping convention: \ inhibits any special meaning the following
45 *	character might have (except \ at end of string is retained).
46 * GLOB_MAGCHAR:
47 *	Set in gl_flags if pattern contained a globbing character.
48 * GLOB_ALTNOT:
49 *	Use ^ instead of ! for "not".
50 * gl_matchc:
51 *	Number of matches in the current invocation of glob.
52 */
53
54#ifdef WINNT_NATIVE
55	#pragma warning(disable:4244)
56#endif /* WINNT_NATIVE */
57
58#define Char __Char
59#include "sh.h"
60#include "glob.h"
61
62#undef Char
63#undef QUOTE
64#undef TILDE
65#undef META
66#undef ismeta
67#undef Strchr
68
69#ifndef S_ISDIR
70#define S_ISDIR(a)	(((a) & S_IFMT) == S_IFDIR)
71#endif
72
73#if !defined(S_ISLNK) && defined(S_IFLNK)
74#define S_ISLNK(a)	(((a) & S_IFMT) == S_IFLNK)
75#endif
76
77#if !defined(S_ISLNK) && !defined(lstat)
78#define lstat stat
79#endif
80
81typedef unsigned short Char;
82
83static	int	 glob1 		(Char *, glob_t *, int);
84static	int	 glob2		(struct strbuf *, const Char *, glob_t *, int);
85static	int	 glob3		(struct strbuf *, const Char *, const Char *,
86				 const Char *, glob_t *, int);
87static	void	 globextend	(const char *, glob_t *);
88static	int	 match		(const char *, const Char *, const Char *,
89				 int);
90static	int	 compare	(const void *, const void *);
91static 	DIR	*Opendir	(const char *);
92#ifdef S_IFLNK
93static	int	 Lstat		(const char *, struct stat *);
94#endif
95static	int	 Stat		(const char *, struct stat *sb);
96static 	Char 	*Strchr		(Char *, int);
97#ifdef DEBUG
98static	void	 qprintf	(const Char *);
99#endif
100
101#define	DOLLAR		'$'
102#define	DOT		'.'
103#define	EOS		'\0'
104#define	LBRACKET	'['
105#define	NOT		'!'
106#define ALTNOT		'^'
107#define	QUESTION	'?'
108#define	QUOTE		'\\'
109#define	RANGE		'-'
110#define	RBRACKET	']'
111#define	SEP		'/'
112#define	STAR		'*'
113#define	TILDE		'~'
114#define	UNDERSCORE	'_'
115
116#define	M_META		0x8000
117#define M_PROTECT	0x4000
118#define	M_MASK		0xffff
119#define	M_ASCII		0x00ff
120
121#define	LCHAR(c)	((c)&M_ASCII)
122#define	META(c)		((c)|M_META)
123#define	M_ALL		META('*')
124#define	M_END		META(']')
125#define	M_NOT		META('!')
126#define	M_ALTNOT	META('^')
127#define	M_ONE		META('?')
128#define	M_RNG		META('-')
129#define	M_SET		META('[')
130#define	ismeta(c)	(((c)&M_META) != 0)
131
132int
133globcharcoll(__Char c1, __Char c2, int cs)
134{
135#if defined(NLS) && defined(LC_COLLATE) && defined(HAVE_STRCOLL)
136# if defined(WIDE_STRINGS)
137    wchar_t s1[2], s2[2];
138
139    if (c1 == c2)
140	return (0);
141    if (cs) {
142	c1 = towlower(c1);
143	c2 = towlower(c2);
144    } else {
145#ifndef __FreeBSD__
146	/* This should not be here, but I'll rather leave it in than engage in
147	   a LC_COLLATE flamewar about a shell I don't use... */
148	if (iswlower(c1) && iswupper(c2))
149	    return (1);
150	if (iswupper(c1) && iswlower(c2))
151	    return (-1);
152#endif
153    }
154    s1[0] = c1;
155    s2[0] = c2;
156    s1[1] = s2[1] = '\0';
157    return wcscoll(s1, s2);
158# else /* not WIDE_STRINGS */
159    char s1[2], s2[2];
160
161    if (c1 == c2)
162	return (0);
163    /*
164     * From kevin lyda <kevin@suberic.net>:
165     * strcoll does not guarantee case sorting, so we pre-process now:
166     */
167    if (cs) {
168	c1 = islower(c1) ? c1 : tolower(c1);
169	c2 = islower(c2) ? c2 : tolower(c2);
170    } else {
171	if (islower(c1) && isupper(c2))
172	    return (1);
173	if (isupper(c1) && islower(c2))
174	    return (-1);
175    }
176    s1[0] = c1;
177    s2[0] = c2;
178    s1[1] = s2[1] = '\0';
179    return strcoll(s1, s2);
180# endif
181#else
182    return (c1 - c2);
183#endif
184}
185
186/*
187 * Need to dodge two kernel bugs:
188 * opendir("") != opendir(".")
189 * NAMEI_BUG: on plain files trailing slashes are ignored in some kernels.
190 *            POSIX specifies that they should be ignored in directories.
191 */
192
193static DIR *
194Opendir(const char *str)
195{
196#if defined(hpux) || defined(__hpux)
197    struct stat st;
198#endif
199
200    if (!*str)
201	return (opendir("."));
202#if defined(hpux) || defined(__hpux)
203    /*
204     * Opendir on some device files hangs, so avoid it
205     */
206    if (stat(str, &st) == -1 || !S_ISDIR(st.st_mode))
207	return NULL;
208#endif
209    return opendir(str);
210}
211
212#ifdef S_IFLNK
213static int
214Lstat(const char *fn, struct stat *sb)
215{
216    int st;
217
218    st = lstat(fn, sb);
219# ifdef NAMEI_BUG
220    if (*fn != 0 && strend(fn)[-1] == '/' && !S_ISDIR(sb->st_mode))
221	st = -1;
222# endif	/* NAMEI_BUG */
223    return st;
224}
225#else
226#define Lstat Stat
227#endif /* S_IFLNK */
228
229static int
230Stat(const char *fn, struct stat *sb)
231{
232    int st;
233
234    st = stat(fn, sb);
235#ifdef NAMEI_BUG
236    if (*fn != 0 && strend(fn)[-1] == '/' && !S_ISDIR(sb->st_mode))
237	st = -1;
238#endif /* NAMEI_BUG */
239    return st;
240}
241
242static Char *
243Strchr(Char *str, int ch)
244{
245    do
246	if (*str == ch)
247	    return (str);
248    while (*str++);
249    return (NULL);
250}
251
252#ifdef DEBUG
253static void
254qprintf(const Char *s)
255{
256    const Char *p;
257
258    for (p = s; *p; p++)
259	printf("%c", *p & 0xff);
260    printf("\n");
261    for (p = s; *p; p++)
262	printf("%c", *p & M_PROTECT ? '"' : ' ');
263    printf("\n");
264    for (p = s; *p; p++)
265	printf("%c", *p & M_META ? '_' : ' ');
266    printf("\n");
267}
268#endif /* DEBUG */
269
270static int
271compare(const void *p, const void *q)
272{
273#if defined(NLS) && defined(HAVE_STRCOLL)
274    return (strcoll(*(char *const *) p, *(char *const *) q));
275#else
276    return (strcmp(*(char *const *) p, *(char *const *) q));
277#endif /* NLS && HAVE_STRCOLL */
278}
279
280/*
281 * The main glob() routine: compiles the pattern (optionally processing
282 * quotes), calls glob1() to do the real pattern matching, and finally
283 * sorts the list (unless unsorted operation is requested).  Returns 0
284 * if things went well, nonzero if errors occurred.  It is not an error
285 * to find no matches.
286 */
287int
288glob(const char *pattern, int flags, int (*errfunc) (const char *, int),
289     glob_t *pglob)
290{
291    int     err, oldpathc;
292    Char *bufnext, m_not;
293    const unsigned char *patnext;
294    int     c, not;
295    Char *qpatnext, *patbuf;
296    int     no_match;
297
298    patnext = (const unsigned char *) pattern;
299    if (!(flags & GLOB_APPEND)) {
300	pglob->gl_pathc = 0;
301	pglob->gl_pathv = NULL;
302	if (!(flags & GLOB_DOOFFS))
303	    pglob->gl_offs = 0;
304    }
305    pglob->gl_flags = flags & ~GLOB_MAGCHAR;
306    pglob->gl_errfunc = errfunc;
307    oldpathc = pglob->gl_pathc;
308    pglob->gl_matchc = 0;
309
310    if (pglob->gl_flags & GLOB_ALTNOT) {
311	not = ALTNOT;
312	m_not = M_ALTNOT;
313    }
314    else {
315	not = NOT;
316	m_not = M_NOT;
317    }
318
319    patbuf = xmalloc((strlen(pattern) + 1) * sizeof(*patbuf));
320    bufnext = patbuf;
321
322    no_match = *patnext == not;
323    if (no_match)
324	patnext++;
325
326    if (flags & GLOB_QUOTE) {
327	/* Protect the quoted characters */
328	while ((c = *patnext++) != EOS) {
329#ifdef WIDE_STRINGS
330	    int len;
331
332	    len = mblen((const char *)(patnext - 1), MB_LEN_MAX);
333	    if (len == -1)
334		TCSH_IGNORE(mblen(NULL, 0));
335	    else if (len > 1) {
336		*bufnext++ = (Char) c;
337		while (--len != 0)
338		    *bufnext++ = (Char) (*patnext++ | M_PROTECT);
339	    } else
340#endif /* WIDE_STRINGS */
341	    if (c == QUOTE) {
342		if ((c = *patnext++) == EOS) {
343		    c = QUOTE;
344		    --patnext;
345		}
346		*bufnext++ = (Char) (c | M_PROTECT);
347	    }
348	    else
349		*bufnext++ = (Char) c;
350	}
351    }
352    else
353	while ((c = *patnext++) != EOS)
354	    *bufnext++ = (Char) c;
355    *bufnext = EOS;
356
357    bufnext = patbuf;
358    qpatnext = patbuf;
359    while ((c = *qpatnext++) != EOS) {
360	switch (c) {
361	case LBRACKET:
362	    c = *qpatnext;
363	    if (c == not)
364		++qpatnext;
365	    if (*qpatnext == EOS ||
366		Strchr(qpatnext + 1, RBRACKET) == NULL) {
367		*bufnext++ = LBRACKET;
368		if (c == not)
369		    --qpatnext;
370		break;
371	    }
372	    pglob->gl_flags |= GLOB_MAGCHAR;
373	    *bufnext++ = M_SET;
374	    if (c == not)
375		*bufnext++ = m_not;
376	    c = *qpatnext++;
377	    do {
378		*bufnext++ = LCHAR(c);
379		if (*qpatnext == RANGE &&
380		    (c = qpatnext[1]) != RBRACKET) {
381		    *bufnext++ = M_RNG;
382		    *bufnext++ = LCHAR(c);
383		    qpatnext += 2;
384		}
385	    } while ((c = *qpatnext++) != RBRACKET);
386	    *bufnext++ = M_END;
387	    break;
388	case QUESTION:
389	    pglob->gl_flags |= GLOB_MAGCHAR;
390	    *bufnext++ = M_ONE;
391	    break;
392	case STAR:
393	    pglob->gl_flags |= GLOB_MAGCHAR;
394	    /* collapse adjacent stars to one [or three if globstar],
395	     * to avoid exponential behavior
396	     */
397	    if (bufnext == patbuf || bufnext[-1] != M_ALL ||
398	       ((flags & GLOB_STAR) != 0 &&
399		 (bufnext - 1 == patbuf || bufnext[-2] != M_ALL ||
400		 bufnext - 2 == patbuf || bufnext[-3] != M_ALL)))
401		*bufnext++ = M_ALL;
402	    break;
403	default:
404	    *bufnext++ = LCHAR(c);
405	    break;
406	}
407    }
408    *bufnext = EOS;
409#ifdef DEBUG
410    qprintf(patbuf);
411#endif
412
413    if ((err = glob1(patbuf, pglob, no_match)) != 0) {
414	xfree(patbuf);
415	return (err);
416    }
417
418    /*
419     * If there was no match we are going to append the pattern
420     * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
421     * and the pattern did not contain any magic characters
422     * GLOB_NOMAGIC is there just for compatibility with csh.
423     */
424    if (pglob->gl_pathc == oldpathc &&
425	((flags & GLOB_NOCHECK) ||
426	 ((flags & GLOB_NOMAGIC) && !(pglob->gl_flags & GLOB_MAGCHAR)))) {
427	if (!(flags & GLOB_QUOTE))
428	    globextend(pattern, pglob);
429	else {
430	    char *copy, *dest;
431	    const char *src;
432
433	    /* copy pattern, interpreting quotes */
434	    copy = xmalloc(strlen(pattern) + 1);
435	    dest = copy;
436	    src = pattern;
437	    while (*src != EOS) {
438		if (*src == QUOTE) {
439		    if (*++src == EOS)
440			--src;
441		}
442		*dest++ = *src++;
443	    }
444	    *dest = EOS;
445	    globextend(copy, pglob);
446	    xfree(copy);
447	}
448	xfree(patbuf);
449	return 0;
450    }
451    else if (!(flags & GLOB_NOSORT) && (pglob->gl_pathc != oldpathc))
452	qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
453	      pglob->gl_pathc - oldpathc, sizeof(char *), compare);
454    xfree(patbuf);
455    return (0);
456}
457
458static int
459glob1(Char *pattern, glob_t *pglob, int no_match)
460{
461    struct strbuf pathbuf = strbuf_INIT;
462    int err;
463
464    /*
465     * a null pathname is invalid -- POSIX 1003.1 sect. 2.4.
466     */
467    if (*pattern == EOS)
468	return (0);
469    err = glob2(&pathbuf, pattern, pglob, no_match);
470    xfree(pathbuf.s);
471    return err;
472}
473
474/*
475 * functions glob2 and glob3 are mutually recursive; there is one level
476 * of recursion for each segment in the pattern that contains one or
477 * more meta characters.
478 */
479static int
480glob2(struct strbuf *pathbuf, const Char *pattern, glob_t *pglob, int no_match)
481{
482    struct stat sbuf;
483    int anymeta;
484    const Char *p;
485    size_t orig_len;
486
487    /*
488     * loop over pattern segments until end of pattern or until segment with
489     * meta character found.
490     */
491    anymeta = 0;
492    for (;;) {
493	if (*pattern == EOS) {	/* end of pattern? */
494	    strbuf_terminate(pathbuf);
495
496	    if (Lstat(pathbuf->s, &sbuf))
497		return (0);
498
499	    if (((pglob->gl_flags & GLOB_MARK) &&
500		 pathbuf->s[pathbuf->len - 1] != SEP) &&
501		(S_ISDIR(sbuf.st_mode)
502#ifdef S_IFLNK
503		 || (S_ISLNK(sbuf.st_mode) &&
504		     (Stat(pathbuf->s, &sbuf) == 0) &&
505		     S_ISDIR(sbuf.st_mode))
506#endif
507		 )) {
508		strbuf_append1(pathbuf, SEP);
509		strbuf_terminate(pathbuf);
510	    }
511	    ++pglob->gl_matchc;
512	    globextend(pathbuf->s, pglob);
513	    return 0;
514	}
515
516	/* find end of next segment, tentatively copy to pathbuf */
517	p = pattern;
518	orig_len = pathbuf->len;
519	while (*p != EOS && *p != SEP) {
520	    if (ismeta(*p))
521		anymeta = 1;
522	    strbuf_append1(pathbuf, *p++);
523	}
524
525	if (!anymeta) {		/* no expansion, do next segment */
526	    pattern = p;
527	    while (*pattern == SEP)
528		strbuf_append1(pathbuf, *pattern++);
529	}
530	else {			/* need expansion, recurse */
531	    pathbuf->len = orig_len;
532	    return (glob3(pathbuf, pattern, p, pattern, pglob, no_match));
533	}
534    }
535    /* NOTREACHED */
536}
537
538static size_t
539One_Char_mbtowc(__Char *pwc, const Char *s, size_t n)
540{
541#ifdef WIDE_STRINGS
542    char buf[MB_LEN_MAX], *p;
543
544    if (n > MB_LEN_MAX)
545	n = MB_LEN_MAX;
546    p = buf;
547    while (p < buf + n && (*p++ = LCHAR(*s++)) != 0)
548	;
549    return one_mbtowc(pwc, buf, n);
550#else
551    *pwc = *s & CHAR;
552    return 1;
553#endif
554}
555
556static int
557glob3(struct strbuf *pathbuf, const Char *pattern, const Char *restpattern,
558      const Char *pglobstar, glob_t *pglob, int no_match)
559{
560    DIR    *dirp;
561    struct dirent *dp;
562    struct stat sbuf;
563    int     err;
564    Char m_not = (pglob->gl_flags & GLOB_ALTNOT) ? M_ALTNOT : M_NOT;
565    size_t orig_len;
566    int globstar = 0;
567    int chase_symlinks = 0;
568    const Char *termstar = NULL;
569
570    strbuf_terminate(pathbuf);
571    orig_len = pathbuf->len;
572    errno = err = 0;
573
574    while (pglobstar < restpattern) {
575	__Char wc;
576	size_t width = One_Char_mbtowc(&wc, pglobstar, MB_LEN_MAX);
577	if ((pglobstar[0] & M_MASK) == M_ALL &&
578	    (pglobstar[width] & M_MASK) == M_ALL) {
579	    globstar = 1;
580	    chase_symlinks = (pglobstar[2 * width] & M_MASK) == M_ALL;
581	    termstar = pglobstar + (2 + chase_symlinks) * width;
582	    break;
583	}
584        pglobstar += width;
585    }
586
587    if (globstar) {
588	err = pglobstar==pattern && termstar==restpattern ?
589		*restpattern == EOS ?
590		glob2(pathbuf, restpattern - 1, pglob, no_match) :
591		glob2(pathbuf, restpattern + 1, pglob, no_match) :
592		glob3(pathbuf, pattern, restpattern, termstar, pglob, no_match);
593	if (err)
594	    return err;
595	pathbuf->len = orig_len;
596	strbuf_terminate(pathbuf);
597    }
598
599    if (*pathbuf->s && (Lstat(pathbuf->s, &sbuf) || !S_ISDIR(sbuf.st_mode)
600#ifdef S_IFLINK
601	     && ((globstar && !chase_symlinks) || !S_ISLNK(sbuf.st_mode))
602#endif
603	))
604	return 0;
605
606    if (!(dirp = Opendir(pathbuf->s))) {
607	/* todo: don't call for ENOENT or ENOTDIR? */
608	if ((pglob->gl_errfunc && (*pglob->gl_errfunc) (pathbuf->s, errno)) ||
609	    (pglob->gl_flags & GLOB_ERR))
610	    return (GLOB_ABEND);
611	else
612	    return (0);
613    }
614
615    /* search directory for matching names */
616    while ((dp = readdir(dirp)) != NULL) {
617	/* initial DOT must be matched literally */
618	if (dp->d_name[0] == DOT && *pattern != DOT)
619	    if (!(pglob->gl_flags & GLOB_DOT) || !dp->d_name[1] ||
620		(dp->d_name[1] == DOT && !dp->d_name[2]))
621		continue; /*unless globdot and not . or .. */
622	pathbuf->len = orig_len;
623	strbuf_append(pathbuf, dp->d_name);
624	strbuf_terminate(pathbuf);
625
626	if (globstar) {
627#ifdef S_IFLNK
628	    if (!chase_symlinks &&
629		(Lstat(pathbuf->s, &sbuf) || S_ISLNK(sbuf.st_mode)))
630		    continue;
631#endif
632	    if (match(pathbuf->s + orig_len, pattern, termstar,
633		(int)m_not) == no_match)
634		    continue;
635	    strbuf_append1(pathbuf, SEP);
636	    strbuf_terminate(pathbuf);
637	    if ((err = glob2(pathbuf, pglobstar, pglob, no_match)) != 0)
638		break;
639	} else {
640	    if (match(pathbuf->s + orig_len, pattern, restpattern,
641		(int) m_not) == no_match)
642		continue;
643	    if ((err = glob2(pathbuf, restpattern, pglob, no_match)) != 0)
644		break;
645	}
646    }
647    /* todo: check error from readdir? */
648    closedir(dirp);
649    return (err);
650}
651
652
653/*
654 * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
655 * add the new item, and update gl_pathc.
656 *
657 * This assumes the BSD realloc, which only copies the block when its size
658 * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
659 * behavior.
660 *
661 * Return 0 if new item added, error code if memory couldn't be allocated.
662 *
663 * Invariant of the glob_t structure:
664 *	Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
665 *	 gl_pathv points to (gl_offs + gl_pathc + 1) items.
666 */
667static void
668globextend(const char *path, glob_t *pglob)
669{
670    char **pathv;
671    int i;
672    size_t newsize;
673
674    newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
675    pathv = xrealloc(pglob->gl_pathv, newsize);
676
677    if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
678	/* first time around -- clear initial gl_offs items */
679	pathv += pglob->gl_offs;
680	for (i = pglob->gl_offs; --i >= 0;)
681	    *--pathv = NULL;
682    }
683    pglob->gl_pathv = pathv;
684
685    pathv[pglob->gl_offs + pglob->gl_pathc++] = strsave(path);
686    pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
687}
688
689/*
690 * pattern matching function for filenames.  Each occurrence of the *
691 * pattern causes a recursion level.
692 */
693static  int
694match(const char *name, const Char *pat, const Char *patend, int m_not)
695{
696    int ok, negate_range;
697    Char c;
698
699    while (pat < patend) {
700	size_t lwk;
701	__Char wc, wk;
702
703	c = *pat; /* Only for M_MASK bits */
704	pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
705	lwk = one_mbtowc(&wk, name, MB_LEN_MAX);
706	switch (c & M_MASK) {
707	case M_ALL:
708	    while (pat < patend && (*pat & M_MASK) == M_ALL)  /* eat consecutive '*' */
709		pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
710	    if (pat == patend)
711	        return (1);
712	    while (!match(name, pat, patend, m_not)) {
713		if (*name == EOS)
714		    return (0);
715		name += lwk;
716		lwk = one_mbtowc(&wk, name, MB_LEN_MAX);
717	    }
718	    return (1);
719	case M_ONE:
720	    if (*name == EOS)
721		return (0);
722	    name += lwk;
723	    break;
724	case M_SET:
725	    ok = 0;
726	    if (*name == EOS)
727		return (0);
728	    name += lwk;
729	    if ((negate_range = ((*pat & M_MASK) == m_not)) != 0)
730		++pat;
731	    while ((*pat & M_MASK) != M_END) {
732		pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
733		if ((*pat & M_MASK) == M_RNG) {
734		    __Char wc2;
735
736		    pat++;
737		    pat += One_Char_mbtowc(&wc2, pat, MB_LEN_MAX);
738		    if (globcharcoll(wc, wk, 0) <= 0 &&
739			globcharcoll(wk, wc2, 0) <= 0)
740			ok = 1;
741		} else if (wc == wk)
742		    ok = 1;
743	    }
744	    pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
745	    if (ok == negate_range)
746		return (0);
747	    break;
748	default:
749	    if (*name == EOS || samecase(wk) != samecase(wc))
750		return (0);
751	    name += lwk;
752	    break;
753	}
754    }
755    return (*name == EOS);
756}
757
758/* free allocated data belonging to a glob_t structure */
759void
760globfree(glob_t *pglob)
761{
762    int i;
763    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		xfree(*pp), *pp = NULL;
770	xfree(pglob->gl_pathv), pglob->gl_pathv = NULL;
771    }
772}
773