+/* $Revision: 4.0.1.1 $
+**
+** Do shell-style pattern matching for ?, \, [], and * characters.
+** Might not be robust in face of malformed patterns; e.g., "foo[a-"
+** could cause a segmentation violation. It is 8bit clean.
+**
+** Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
+** Rich $alz is now <rsalz@bbn.com>.
+** April, 1991: Replaced mutually-recursive calls with in-line code
+** for the star character.
+**
+** Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
+** This can greatly speed up failing wildcard patterns. For example:
+** pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
+** text 1: -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
+** text 2: -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
+** Text 1 matches with 51 calls, while text 2 fails with 54 calls. Without
+** the ABORT, then it takes 22310 calls to fail. Ugh. The following
+** explanation is from Lars:
+** The precondition that must be fulfilled is that DoMatch will consume
+** at least one character in text. This is true if *p is neither '*' nor
+** '\0'.) The last return has ABORT instead of FALSE to avoid quadratic
+** behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx". With
+** FALSE, each star-loop has to run to the end of the text; with ABORT
+** only the last one does.
+**
+** Once the control of one instance of DoMatch enters the star-loop, that
+** instance will return either TRUE or ABORT, and any calling instance
+** will therefore return immediately after (without calling recursively
+** again). In effect, only one star-loop is ever active. It would be
+** possible to modify the code to maintain this context explicitly,
+** eliminating all recursive calls at the cost of some complication and
+** loss of clarity (and the ABORT stuff seems to be unclear enough by
+** itself). I think it would be unwise to try to get this into a
+** released version unless you have a good test data base to try it out
+** on.
+*/
+
+#define TRUE 1
+#define FALSE 0
+#define ABORT -1
+
+
+ /* What character marks an inverted character class? */
+#define NEGATE_CLASS '^'
+ /* Is "*" a common pattern? */
+#define OPTIMIZE_JUST_STAR
+ /* Do tar(1) matching rules, which ignore a trailing slash? */
+#undef MATCH_TAR_PATTERN
+
+
+/*
+** Match text and p, return TRUE, FALSE, or ABORT.
+*/
+static int
+DoMatch(text, p)
+ char *text;
+ char *p;
+{
+ int last;
+ int matched;
+ int reverse;
+
+ for ( ; *p; text++, p++) {
+ if (*text == '\0' && *p != '*')
+ return ABORT;
+ switch (*p) {
+ case '\\':
+ /* Literal match with following character. */
+ p++;
+ /* FALLTHROUGH */
+ default:
+ if (*text != *p)
+ return FALSE;
+ continue;
+ case '?':
+ /* Match anything. */
+ continue;
+ case '*':
+ while (*++p == '*')
+ /* Consecutive stars act just like one. */
+ continue;
+ if (*p == '\0')
+ /* Trailing star matches everything. */
+ return TRUE;
+ while (*text)
+ if ((matched = DoMatch(text++, p)) != FALSE)
+ return matched;
+ return ABORT;
+ case '[':
+ reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
+ if (reverse)
+ /* Inverted character class. */
+ p++;
+ for (last = 0400, matched = FALSE; *++p && *p != ']'; last = *p)
+ /* This next line requires a good C compiler. */
+ if (*p == '-' ? *text <= *++p && *text >= last : *text == *p)
+ matched = TRUE;
+ if (matched == reverse)
+ return FALSE;
+ continue;
+ }
+ }
+
+#ifdef MATCH_TAR_PATTERN
+ if (*text == '/')
+ return TRUE;
+#endif /* MATCH_TAR_ATTERN */
+ return *text == '\0';
+}
+
+
+/*
+** User-level routine. Returns TRUE or FALSE.
+*/
+int
+wildmat(text, p)
+ char *text;
+ char *p;
+{
+#ifdef OPTIMIZE_JUST_STAR
+ if (p[0] == '*' && p[1] == '\0')
+ return TRUE;
+#endif /* OPTIMIZE_JUST_STAR */
+ return DoMatch(text, p) == TRUE;
+}
+
+#include <stdio.h>
+#include <sys/types.h>
+#include <dirent.h>
+#include <sys/stat.h>
+#if __STDC__
+#ifdef unix
+#define _SIZE_T /* unix defines size_t in sys/types.h */
+#endif
+#ifndef _COMPILER_H
+# include <compiler.h>
+#endif
+#include <stddef.h>
+#include <stdlib.h>
+#else
+extern char *malloc(), *realloc();
+extern char *rindex(), *strdup();
+#define __PROTO(x) ()
+#endif
+#include <string.h>
+
+#define MAX_DIR 32 /* max depth of dir recursion */
+static struct {
+ char *dir, *patt;
+} dir_stack[MAX_DIR];
+static int stack_p;
+static char **matches;
+static int nmatches;
+
+static void *ck_memalloc __PROTO((void *));
+#define ck_strdup(p) ck_memalloc(strdup(p))
+#define ck_malloc(s) ck_memalloc(malloc(s))
+#define ck_realloc(p, s) ck_memalloc(realloc(p, s))
+
+
+#define DEBUGX(x)
+
+/*
+ * return true if patt contains a wildcard char
+ */
+int contains_wild(patt)
+char *patt;
+{
+ char c;
+ char *p;
+
+ /* only check for wilds in the basename part of the pathname only */
+ if((p = rindex(patt, '/')) == NULL)
+ p = rindex(patt, '\\');
+ if(!p)
+ p = patt;
+
+ while((c = *p++))
+ if((c == '*') || (c == '?') || (c == '['))
+ return 1;
+ return 0;
+}
+
+#ifndef ZOO
+void free_all()
+{
+ char **p;
+
+ if(!matches)
+ return;
+
+ for(p = matches; *p; p++)
+ free(*p);
+ free(matches);
+ matches = NULL;
+}
+#endif
+
+static void push(dir, patt)
+char *dir;
+char *patt;
+{
+ if(stack_p < (MAX_DIR - 2))
+ stack_p++;
+ else
+ {
+ fprintf(stderr,"directory stack overflow\n");
+ exit(99);
+ }
+ dir_stack[stack_p].dir = dir;
+ dir_stack[stack_p].patt = patt;
+}
+
+/*
+ * glob patt
+ * if decend_dir is true, recursively decend any directories encountered.
+ * returns pointer to all matches encountered.
+ * if the initial patt is a directory, and decend_dir is true, it is
+ * equivalent to specifying the pattern "patt\*"
+ *
+ * Restrictions:
+ * - handles wildcards only in the base part of a pathname
+ * ie: will not handle \foo\*\bar\ (wildcard in the middle of pathname)
+ *
+ * - max dir recursion is MAX_DIR
+ *
+ * - on certain failures it will just skip potential matches as if they
+ * were not present.
+ *
+ * ++jrb bammi@cadence.com
+ */
+static char **do_match __PROTO((int decend_dir));
+
+char **glob(patt, decend_dir)
+char *patt;
+int decend_dir;
+{
+ char *dir, *basepatt, *p;
+ struct stat s;
+
+ DEBUGX((fprintf(stderr,"glob(%s, %d)\n", patt, decend_dir)));
+ matches = NULL;
+ nmatches = 0;
+ stack_p = -1;
+
+ /* first check for wildcards */
+ if(contains_wild(patt))
+ {
+ /* break it up into dir and base patt, do_matches and return */
+ p = ck_strdup(patt);
+ if((basepatt = rindex(p, '/')) == NULL)
+ basepatt = rindex(p, '\\');
+ if(basepatt)
+ {
+ dir = p;
+ *basepatt++ = '\0';
+ basepatt = ck_strdup(basepatt);
+ }
+ else
+ {
+ dir = ck_strdup(".");
+ basepatt = p;
+ }
+
+ if(strcmp(basepatt, "*.*") == 0)
+ {
+ /* the desktop, and other braindead shells strike again */
+ basepatt[1] = '\0';
+ }
+ push(dir, basepatt);
+ DEBUGX((fprintf(stderr, "calling %s, %s\n", dir, basepatt)));
+ return do_match(decend_dir);
+ }
+
+ /* if no wilds, check for dir */
+ if(decend_dir && (!stat(patt, &s)))
+ {
+ if((s.st_mode & S_IFMT) == S_IFDIR)
+ { /* is a dir */
+ size_t len = strlen(patt);
+
+ dir = ck_strdup(patt);
+ --len;
+ if(len && ((dir[len] == '/')
+#ifdef atarist
+ || (dir[len] == '\\')
+#endif
+ ))
+ dir[len] = '\0';
+ basepatt = ck_strdup("*");
+ push(dir, basepatt);
+ DEBUGX((fprintf(stderr, "calling %s, %s\n", dir, basepatt)));
+ return do_match(decend_dir);
+ }
+ }
+ return NULL;
+}
+
+static char **do_match(decend_dir)
+int decend_dir;
+{
+ DIR *dirp;
+ struct dirent *d;
+ struct stat s;
+ char *dir, *basepatt;
+
+ while(stack_p >= 0)
+ {
+ dir = ck_strdup(dir_stack[stack_p].dir);
+ free(dir_stack[stack_p].dir);
+ basepatt = ck_strdup(dir_stack[stack_p].patt);
+ free(dir_stack[stack_p--].patt);
+
+ DEBUGX((fprintf(stderr,"dir %s patt %s stack %d\n", dir, basepatt, stack_p)));
+
+ dirp = opendir(dir);
+ if(!dirp)
+ {
+ free(dir);
+ DEBUGX((fprintf(stderr,"no dir\n")));
+ continue;
+ }
+
+ while((d = readdir(dirp)))
+ {
+ char *p = ck_malloc(strlen(dir) + strlen(d->d_name) + 2L);
+ if(strcmp(dir, "."))
+ /* If we have a full pathname then */
+ { /* let's append the directory info */
+ strcpy(p, dir);
+#ifndef unix
+ strcat(p, "\\");
+#else
+ strcat(p, "/");
+#endif
+ strcat(p, d->d_name);
+ }
+ else /* Otherwise, the name is just fine, */
+ strcpy(p, d->d_name); /* there's no need for './' -- bjsjr */
+
+ DEBUGX((fprintf(stderr, "Testing %s\n", p)));
+ if(!stat(p, &s)) /* if stat fails, ignore it */
+ {
+ if( ((s.st_mode & S_IFMT) == S_IFREG) ||
+ ((s.st_mode & S_IFMT) == S_IFLNK) )
+ { /* it is a file/symbolic link */
+ if(wildmat(d->d_name, basepatt))
+ { /* it matches pattern */
+ DEBUGX((fprintf(stderr,"File Matched\n")));
+ if(matches == NULL)
+ matches = (char **)ck_malloc(sizeof(char *));
+ else
+ matches = (char **)
+ ck_realloc(matches, (nmatches+1)*sizeof(char *));
+ matches[nmatches++] = p;
+ } /* no match */
+ else
+ {
+ DEBUGX((fprintf(stderr,"No File Match\n")));
+ free(p);
+ }
+ } else if(decend_dir && ((s.st_mode & S_IFMT) == S_IFDIR))
+ {
+ if(!((!strcmp(d->d_name,".")) || (!strcmp(d->d_name, "..")
+#ifdef atarist
+ || (!strcmp(d->d_name, ".dir"))
+#endif
+ )))
+ {
+ char *push_p = ck_strdup("*");
+ push(p, push_p);
+ DEBUGX((fprintf(stderr,"Dir pushed\n")));
+ }
+ else
+ {
+ DEBUGX((fprintf(stderr, "DIR skipped\n")));
+ free(p);
+ }
+ }
+ else
+ {
+ DEBUGX((fprintf(stderr, "Not a dir/no decend\n")));
+ free(p);
+ }
+ } /* stat */
+ else
+ {
+ DEBUGX((fprintf(stderr, "Stat failed\n")));
+ free(p);
+ }
+ } /* while readdir */
+ closedir(dirp);
+ free(basepatt);
+ free(dir);
+ DEBUGX((fprintf(stderr, "Dir done\n\n")));
+ } /* while dirs in stack */
+
+ if(!nmatches)
+ {
+ DEBUGX((fprintf(stderr, "No matches\n")));
+ return NULL;
+ }
+
+ matches = (char **)realloc(matches, (nmatches+1)*sizeof(char *));
+ if(!matches)
+ { return NULL; }
+ matches[nmatches] = NULL;
+ DEBUGX((fprintf(stderr, "%d matches\n", nmatches)));
+ return matches;
+}
+
+#ifdef ZOO
+#include "errors.i"
+#endif
+
+static void *ck_memalloc(p)
+void *p;
+{
+ if(!p)
+ {
+#ifndef ZOO
+ fprintf(stderr, "Out of memory\n");
+ exit(98);
+#else
+ prterror('f', no_memory);
+#endif
+ }
+ return p;
+}
+
+#ifdef TEST_GLOB
+void test(path, dec)
+char *path;
+int dec;
+{
+ char **m;
+ char **matches;
+
+ printf("Testing %s %d\n", path, dec);
+ matches = glob(path, dec);
+ if(!matches)
+ {
+ printf("No matches\n");
+ }
+ else
+ {
+ for(m = matches; *m; m++)
+ printf("%s\n", *m);
+ putchar('\n');
+ free_all();
+ }
+}
+
+int main()
+{
+#ifndef unix
+ test("e:\\lib\\*.olb", 0);
+ test("e:\\lib", 0);
+ test("e:\\lib\\", 1);
+#else
+ test("/net/acae127/home/bammi/News/comp.sources.misc/*.c", 0);
+ test("/net/acae127/home/bammi/News/comp.sources.misc", 0);
+ test("/net/acae127/home/bammi/News/comp.sources.misc", 1);
+ test("/net/acae127/home/bammi/atari/cross-gcc", 1);
+#endif
+
+ return 0;
+}
+
+#endif
+
+#ifdef TEST_WILDMAT
+#include <stdio.h>
+
+/* Yes, we use gets not fgets. Sue me. */
+extern char *gets();
+
+
+main()
+{
+ char pattern[80];
+ char text[80];
+
+ printf("Wildmat tester. Enter pattern, then strings to test.\n");
+ printf("A blank line gets prompts for a new pattern; a blank pattern\n");
+ printf("exits the program.\n\n");
+
+ for ( ; ; ) {
+ printf("Enter pattern: ");
+ if (gets(pattern) == NULL)
+ break;
+ for ( ; ; ) {
+ printf("Enter text: ");
+ if (gets(text) == NULL)
+ exit(0);
+ if (text[0] == '\0')
+ /* Blank line; go back and get a new pattern. */
+ break;
+ printf(" %s\n", wildmat(text, pattern) ? "YES" : "NO");
+ }
+ }
+
+ exit(0);
+ /* NOTREACHED */
+}
+#endif /* TEST_WILDMAT */