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