X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/084103a70453b137fbdec39735aca05be81993e2..9dd52de3fb4cfab4a8536c531f9590a5d1f96253:/usr/src/usr.bin/find/find.c

diff --git a/usr/src/usr.bin/find/find.c b/usr/src/usr.bin/find/find.c
index da8b567835..36f0de64f1 100644
--- a/usr/src/usr.bin/find/find.c
+++ b/usr/src/usr.bin/find/find.c
@@ -1,845 +1,222 @@
-static char *sccsid = "@(#)find.c	4.11 (Berkeley) %G%";
-
-#include <stdio.h>
-#include <sys/param.h>
-#include <sys/dir.h>
-#include <sys/stat.h>
-#define A_DAY	86400L /* a day full of seconds */
-#define EQ(x, y)	(strcmp(x, y)==0)
-
-int	Randlast;
-char	Pathname[MAXPATHLEN+1];
-
-struct anode {
-	int (*F)();
-	struct anode *L, *R;
-} Node[100];
-int Nn;  /* number of nodes */
-char	*Fname;
-long	Now;
-int	Argc,
-	Ai,
-	Pi;
-char	**Argv;
-/* cpio stuff */
-int	Cpio;
-short	*Buf, *Dbuf, *Wp;
-int	Bufsize = 5120;
-int	Wct = 2560;
-
-long	Newer;
-
-struct stat Statb;
-
-struct	anode	*exp(),
-		*e1(),
-		*e2(),
-		*e3(),
-		*mk();
-char	*nxtarg();
-char	Home[128];
-long	Blocks;
-char *rindex();
-char *sbrk();
-
-/*
- * SEE ALSO:	updatedb, bigram.c, code.c
- *		Usenix ;login:, February/March, 1983, p. 8.
+/*-
+ * Copyright (c) 1990 The Regents of the University of California.
+ * All rights reserved.
  *
- * REVISIONS: 	James A. Woods, Informatics General Corporation,
- *		NASA Ames Research Center, 6/81.
+ * This code is derived from software contributed to Berkeley by
+ * Cimarron D. Taylor of the University of California, Berkeley.
  *
- *		The second form searches a pre-computed filelist
- *		(constructed nightly by /usr/lib/crontab) which is
- *		compressed by updatedb (v.i.z.)  The effect of
- *			find <name>
- *		is similar to
- *			find / +0 -name "*<name>*" -print
- *		but much faster.
- *
- *		8/82 faster yet + incorporation of bigram coding -- jaw
- *
- *		1/83 incorporate glob-style matching -- jaw
+ * %sccs.include.redist.c%
  */
-#define	AMES	1
 
-main(argc, argv)
-	int argc;
-	char *argv[];
-{
-	struct anode *exlist;
-	int paths;
-	register char *cp, *sp = 0;
-	FILE *pwd, *popen();
-
-#ifdef  AMES
-	if (argc < 2) {
-		fprintf(stderr,
-			"Usage: find name, or find path-list predicate-list\n");
-		exit(1);
-	}
-	if (argc == 2) {
-		fastfind(argv[1]);
-		exit(0);
-	}
-#endif
-	time(&Now);
-	pwd = popen("pwd", "r");
-	fgets(Home, 128, pwd);
-	pclose(pwd);
-	Home[strlen(Home) - 1] = '\0';
-	Argc = argc; Argv = argv;
-	if(argc<3) {
-usage:		fprintf(stderr, "Usage: find path-list predicate-list\n");
-		exit(1);
-	}
-	for(Ai = paths = 1; Ai < (argc-1); ++Ai, ++paths)
-		if(*Argv[Ai] == '-' || EQ(Argv[Ai], "(") || EQ(Argv[Ai], "!"))
-			break;
-	if(paths == 1) /* no path-list */
-		goto usage;
-	if(!(exlist = exp())) { /* parse and compile the arguments */
-		fprintf(stderr, "find: parsing error\n");
-		exit(1);
-	}
-	if(Ai<argc) {
-		fprintf(stderr, "find: missing conjunction\n");
-		exit(1);
-	}
-	for(Pi = 1; Pi < paths; ++Pi) {
-		sp = 0;
-		chdir(Home);
-		strcpy(Pathname, Argv[Pi]);
-		if(cp = rindex(Pathname, '/')) {
-			sp = cp + 1;
-			*cp = '\0';
-			if(chdir(*Pathname? Pathname: "/") == -1) {
-				fprintf(stderr, "find: bad starting directory\n");
-				exit(2);
-			}
-			*cp = '/';
-		}
-		Fname = sp? sp: Pathname;
-		descend(Pathname, Fname, exlist); /* to find files that match  */
-	}
-	if(Cpio) {
-		strcpy(Pathname, "TRAILER!!!");
-		Statb.st_size = 0;
-		cpio();
-		printf("%D blocks\n", Blocks*10);
-	}
-	exit(0);
-}
-
-/* compile time functions:  priority is  exp()<e1()<e2()<e3()  */
-
-struct anode *exp() { /* parse ALTERNATION (-o)  */
-	int or();
-	register struct anode * p1;
-
-	p1 = e1() /* get left operand */ ;
-	if(EQ(nxtarg(), "-o")) {
-		Randlast--;
-		return(mk(or, p1, exp()));
-	}
-	else if(Ai <= Argc) --Ai;
-	return(p1);
-}
-struct anode *e1() { /* parse CONCATENATION (formerly -a) */
-	int and();
-	register struct anode * p1;
-	register char *a;
-
-	p1 = e2();
-	a = nxtarg();
-	if(EQ(a, "-a")) {
-And:
-		Randlast--;
-		return(mk(and, p1, e1()));
-	} else if(EQ(a, "(") || EQ(a, "!") || (*a=='-' && !EQ(a, "-o"))) {
-		--Ai;
-		goto And;
-	} else if(Ai <= Argc) --Ai;
-	return(p1);
-}
-struct anode *e2() { /* parse NOT (!) */
-	int not();
-
-	if(Randlast) {
-		fprintf(stderr, "find: operand follows operand\n");
-		exit(1);
-	}
-	Randlast++;
-	if(EQ(nxtarg(), "!"))
-		return(mk(not, e3(), (struct anode *)0));
-	else if(Ai <= Argc) --Ai;
-	return(e3());
-}
-struct anode *e3() { /* parse parens and predicates */
-	int exeq(), ok(), glob(),  mtime(), atime(), user(),
-		group(), size(), perm(), links(), print(),
-		type(), ino(), cpio(), newer();
-	struct anode *p1;
-	int i;
-	register char *a, *b, s;
-
-	a = nxtarg();
-	if(EQ(a, "(")) {
-		Randlast--;
-		p1 = exp();
-		a = nxtarg();
-		if(!EQ(a, ")")) goto err;
-		return(p1);
-	}
-	else if(EQ(a, "-print")) {
-		return(mk(print, (struct anode *)0, (struct anode *)0));
-	}
-	b = nxtarg();
-	s = *b;
-	if(s=='+') b++;
-	if(EQ(a, "-name"))
-		return(mk(glob, (struct anode *)b, (struct anode *)0));
-	else if(EQ(a, "-mtime"))
-		return(mk(mtime, (struct anode *)atoi(b), (struct anode *)s));
-	else if(EQ(a, "-atime"))
-		return(mk(atime, (struct anode *)atoi(b), (struct anode *)s));
-	else if(EQ(a, "-user")) {
-		if((i=getunum("/etc/passwd", b)) == -1) {
-			if(gmatch(b, "[0-9]*"))
-				return mk(user, (struct anode *)atoi(b), (struct anode *)s);
-			fprintf(stderr, "find: cannot find -user name\n");
-			exit(1);
-		}
-		return(mk(user, (struct anode *)i, (struct anode *)s));
-	}
-	else if(EQ(a, "-inum"))
-		return(mk(ino, (struct anode *)atoi(b), (struct anode *)s));
-	else if(EQ(a, "-group")) {
-		if((i=getunum("/etc/group", b)) == -1) {
-			if(gmatch(b, "[0-9]*"))
-				return mk(group, (struct anode *)atoi(b), (struct anode *)s);
-			fprintf(stderr, "find: cannot find -group name\n");
-			exit(1);
-		}
-		return(mk(group, (struct anode *)i, (struct anode *)s));
-	} else if(EQ(a, "-size"))
-		return(mk(size, (struct anode *)atoi(b), (struct anode *)s));
-	else if(EQ(a, "-links"))
-		return(mk(links, (struct anode *)atoi(b), (struct anode *)s));
-	else if(EQ(a, "-perm")) {
-		for(i=0; *b ; ++b) {
-			if(*b=='-') continue;
-			i <<= 3;
-			i = i + (*b - '0');
-		}
-		return(mk(perm, (struct anode *)i, (struct anode *)s));
-	}
-	else if(EQ(a, "-type")) {
-		i = s=='d' ? S_IFDIR :
-		    s=='b' ? S_IFBLK :
-		    s=='c' ? S_IFCHR :
-		    s=='f' ? S_IFREG :
-		    s=='l' ? S_IFLNK :
-		    s=='s' ? S_IFSOCK :
-		    0;
-		return(mk(type, (struct anode *)i, (struct anode *)0));
-	}
-	else if (EQ(a, "-exec")) {
-		i = Ai - 1;
-		while(!EQ(nxtarg(), ";"));
-		return(mk(exeq, (struct anode *)i, (struct anode *)0));
-	}
-	else if (EQ(a, "-ok")) {
-		i = Ai - 1;
-		while(!EQ(nxtarg(), ";"));
-		return(mk(ok, (struct anode *)i, (struct anode *)0));
-	}
-	else if(EQ(a, "-cpio")) {
-		if((Cpio = creat(b, 0666)) < 0) {
-			fprintf(stderr, "find: cannot create < %s >\n", s);
-			exit(1);
-		}
-		Buf = (short *)sbrk(512);
-		Wp = Dbuf = (short *)sbrk(5120);
-		return(mk(cpio, (struct anode *)0, (struct anode *)0));
-	}
-	else if(EQ(a, "-newer")) {
-		if(stat(b, &Statb) < 0) {
-			fprintf(stderr, "find: cannot access < %s >\n", b);
-			exit(1);
-		}
-		Newer = Statb.st_mtime;
-		return mk(newer, (struct anode *)0, (struct anode *)0);
-	}
-err:	fprintf(stderr, "find: bad option < %s >\n", a);
-	exit(1);
-}
-struct anode *mk(f, l, r)
-int (*f)();
-struct anode *l, *r;
-{
-	Node[Nn].F = f;
-	Node[Nn].L = l;
-	Node[Nn].R = r;
-	return(&(Node[Nn++]));
-}
-
-char *nxtarg() { /* get next arg from command line */
-	static strikes = 0;
-
-	if(strikes==3) {
-		fprintf(stderr, "find: incomplete statement\n");
-		exit(1);
-	}
-	if(Ai>=Argc) {
-		strikes++;
-		Ai = Argc + 1;
-		return("");
-	}
-	return(Argv[Ai++]);
-}
-
-/* execution time functions */
-and(p)
-register struct anode *p;
-{
-	return(((*p->L->F)(p->L)) && ((*p->R->F)(p->R))?1:0);
-}
-or(p)
-register struct anode *p;
-{
-	 return(((*p->L->F)(p->L)) || ((*p->R->F)(p->R))?1:0);
-}
-not(p)
-register struct anode *p;
-{
-	return( !((*p->L->F)(p->L)));
-}
-glob(p)
-register struct { int f; char *pat; } *p; 
-{
-	return(gmatch(Fname, p->pat));
-}
-print()
-{
-	puts(Pathname);
-	return(1);
-}
-mtime(p)
-register struct { int f, t, s; } *p; 
-{
-	return(scomp((int)((Now - Statb.st_mtime) / A_DAY), p->t, p->s));
-}
-atime(p)
-register struct { int f, t, s; } *p; 
-{
-	return(scomp((int)((Now - Statb.st_atime) / A_DAY), p->t, p->s));
-}
-user(p)
-register struct { int f, u, s; } *p; 
-{
-	return(scomp(Statb.st_uid, p->u, p->s));
-}
-ino(p)
-register struct { int f, u, s; } *p;
-{
-	return(scomp((int)Statb.st_ino, p->u, p->s));
-}
-group(p)
-register struct { int f, u; } *p; 
-{
-	return(p->u == Statb.st_gid);
-}
-links(p)
-register struct { int f, link, s; } *p; 
-{
-	return(scomp(Statb.st_nlink, p->link, p->s));
-}
-size(p)
-register struct { int f, sz, s; } *p; 
-{
-	return(scomp((int)((Statb.st_size+511)>>9), p->sz, p->s));
-}
-perm(p)
-register struct { int f, per, s; } *p; 
-{
-	register i;
-	i = (p->s=='-') ? p->per : 07777; /* '-' means only arg bits */
-	return((Statb.st_mode & i & 07777) == p->per);
-}
-type(p)
-register struct { int f, per, s; } *p;
-{
-	return((Statb.st_mode&S_IFMT)==p->per);
-}
-exeq(p)
-register struct { int f, com; } *p;
-{
-	fflush(stdout); /* to flush possible `-print' */
-	return(doex(p->com));
-}
-ok(p)
-struct { int f, com; } *p;
-{
-	char c;  int yes;
-	yes = 0;
-	fflush(stdout); /* to flush possible `-print' */
-	fprintf(stderr, "< %s ... %s > ?   ", Argv[p->com], Pathname);
-	fflush(stderr);
-	if((c=getchar())=='y') yes = 1;
-	while(c!='\n') c = getchar();
-	if(yes) return(doex(p->com));
-	return(0);
-}
+#ifndef lint
+char copyright[] =
+"@(#) Copyright (c) 1990 The Regents of the University of California.\n\
+ All rights reserved.\n";
+#endif /* not lint */
 
-#define MKSHORT(v, lv) {U.l=1L;if(U.c[0]) U.l=lv, v[0]=U.s[1], v[1]=U.s[0]; else U.l=lv, v[0]=U.s[0], v[1]=U.s[1];}
-union { long l; short s[2]; char c[4]; } U;
-long mklong(v)
-short v[];
-{
-	U.l = 1;
-	if(U.c[0] /* VAX */)
-		U.s[0] = v[1], U.s[1] = v[0];
-	else
-		U.s[0] = v[0], U.s[1] = v[1];
-	return U.l;
-}
-cpio()
-{
-#define MAGIC 070707
-	struct header {
-		short	h_magic,
-			h_dev,
-			h_ino,
-			h_mode,
-			h_uid,
-			h_gid,
-			h_nlink,
-			h_rdev;
-		short	h_mtime[2];
-		short	h_namesize;
-		short	h_filesize[2];
-		char	h_name[256];
-	} hdr;
-	register ifile, ct;
-	static long fsz;
-	register i;
+#ifndef lint
+static char sccsid[] = "@(#)find.c	4.33 (Berkeley) %G%";
+#endif /* not lint */
 
-	hdr.h_magic = MAGIC;
-	strcpy(hdr.h_name, !strncmp(Pathname, "./", 2)? Pathname+2: Pathname);
-	hdr.h_namesize = strlen(hdr.h_name) + 1;
-	hdr.h_uid = Statb.st_uid;
-	hdr.h_gid = Statb.st_gid;
-	hdr.h_dev = Statb.st_dev;
-	hdr.h_ino = Statb.st_ino;
-	hdr.h_mode = Statb.st_mode;
-	MKSHORT(hdr.h_mtime, Statb.st_mtime);
-	hdr.h_nlink = Statb.st_nlink;
-	fsz = hdr.h_mode & S_IFREG? Statb.st_size: 0L;
-	MKSHORT(hdr.h_filesize, fsz);
-	hdr.h_rdev = Statb.st_rdev;
-	if(EQ(hdr.h_name, "TRAILER!!!")) {
-		bwrite((short *)&hdr, (sizeof hdr-256)+hdr.h_namesize);
-		for(i = 0; i < 10; ++i)
-			bwrite(Buf, 512);
-		return;
-	}
-	if(!mklong(hdr.h_filesize))
-		return;
-	if((ifile = open(Fname, 0)) < 0) {
-cerror:
-		fprintf(stderr, "find: cannot copy < %s >\n", hdr.h_name);
-		return;
-	}
-	bwrite((short *)&hdr, (sizeof hdr-256)+hdr.h_namesize);
-	for(fsz = mklong(hdr.h_filesize); fsz > 0; fsz -= 512) {
-		ct = fsz>512? 512: fsz;
-		if(read(ifile, (char *)Buf, ct) < 0)
-			goto cerror;
-		bwrite(Buf, ct);
-	}
-	close(ifile);
-	return;
-}
-newer()
-{
-	return Statb.st_mtime > Newer;
-}
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fts.h>
+#include <stdio.h>
+#include <string.h>
+#include <errno.h>
+#include "find.h"
 
-/* support functions */
-scomp(a, b, s) /* funny signed compare */
-register a, b;
-register char s;
-{
-	if(s == '+')
-		return(a > b);
-	if(s == '-')
-		return(a < (b * -1));
-	return(a == b);
-}
+FTS *tree;			/* pointer to top of FTS hierarchy */
+time_t now;			/* time find was run */
+int ftsoptions;			/* options passed to ftsopen() */
+int deprecated;			/* old or new syntax */
+int depth;			/* set by -depth option */
+int output_specified;		/* one of -print, -ok or -exec was specified */
 
-doex(com)
+main(argc, argv)
+	int argc;
+	char **argv;
 {
-	register np;
-	register char *na;
-	static char *nargv[50];
-	static ccode;
+	PLAN *plan;
+	char **p, **paths;
+	PLAN *find_formplan();
+	time_t time();
+    
+	(void)time(&now);			/* initialize the time-of-day */
 
-	ccode = np = 0;
-	while (na=Argv[com++]) {
-		if(strcmp(na, ";")==0) break;
-		if(strcmp(na, "{}")==0) nargv[np++] = Pathname;
-		else nargv[np++] = na;
-	}
-	nargv[np] = 0;
-	if (np==0) return(9);
-	if(fork()) /*parent*/ {
-#include <signal.h>
-		int (*old)() = signal(SIGINT, SIG_IGN);
-		int (*oldq)() = signal(SIGQUIT, SIG_IGN);
-		wait(&ccode);
-		signal(SIGINT, old);
-		signal(SIGQUIT, oldq);
-	} else { /*child*/
-		chdir(Home);
-		execvp(nargv[0], nargv, np);
-		exit(1);
-	}
-	return(ccode ? 0:1);
-}
+	if (argc < 2)
+		usage();
 
-getunum(f, s) char *f, *s; { /* find user/group name and return number */
-	register i;
-	register char *sp;
-	register c;
-	char str[20];
-	FILE *pin;
+	paths = argv;
+	ftsoptions = FTS_NOSTAT|FTS_PHYSICAL;
 
-	i = -1;
-	pin = fopen(f, "r");
-	c = '\n'; /* prime with a CR */
-	do {
-		if(c=='\n') {
-			sp = str;
-			while((c = *sp++ = getc(pin)) != ':')
-				if(c == EOF) goto RET;
-			*--sp = '\0';
-			if(EQ(str, s)) {
-				while((c=getc(pin)) != ':')
-					if(c == EOF) goto RET;
-				sp = str;
-				while((*sp = getc(pin)) != ':') sp++;
-				*sp = '\0';
-				i = atoi(str);
-				goto RET;
+	/*
+	 * if arguments start with an option, treat it like new syntax;
+	 * otherwise, if has a "-option" anywhere (which isn't an argument
+	 * to another command) treat it as old syntax.
+	 */
+	if (argv[1][0] != '-')
+		for (p = argv + 1; *p; ++p) {
+			if (!strcmp(*p, "exec") || !strcmp(*p, "ok")) {
+				while (p[1] && strcmp(*++p, ";"));
+				continue;
 			}
-		}
-	} while((c = getc(pin)) != EOF);
- RET:
-	fclose(pin);
-	return(i);
-}
-
-descend(name, fname, exlist)
-	struct anode *exlist;
-	char *name, *fname;
-{
-	DIR	*dir = NULL;
-	register struct direct	*dp;
-	register char *c1;
-	int rv = 0;
-	char *endofname;
-
-	if (lstat(fname, &Statb)<0) {
-		fprintf(stderr, "find: bad status < %s >\n", name);
-		return(0);
-	}
-	(*exlist->F)(exlist);
-	if((Statb.st_mode&S_IFMT)!=S_IFDIR)
-		return(1);
-
-	for (c1 = name; *c1; ++c1);
-	if (*(c1-1) == '/')
-		--c1;
-	endofname = c1;
-
-	if (chdir(fname) == -1)
-		return(0);
-	if ((dir = opendir(".")) == NULL) {
-		fprintf(stderr, "find: cannot open < %s >\n", name);
-		rv = 0;
-		goto ret;
-	}
-	for (dp = readdir(dir); dp != NULL; dp = readdir(dir)) {
-		if ((dp->d_name[0]=='.' && dp->d_name[1]=='\0') ||
-		    (dp->d_name[0]=='.' && dp->d_name[1]=='.' && dp->d_name[2]=='\0'))
-			continue;
-		c1 = endofname;
-		*c1++ = '/';
-		strcpy(c1, dp->d_name);
-		Fname = endofname+1;
-		if(!descend(name, Fname, exlist)) {
-			*endofname = '\0';
-			chdir(Home);
-			if(chdir(Pathname) == -1) {
-				fprintf(stderr, "find: bad directory tree\n");
-				exit(1);
+			if (**p == '-') {
+				deprecated = 1;
+				oldsyntax(&argv);
+				break;
 			}
 		}
-	}
-	rv = 1;
-ret:
-	if(dir)
-		closedir(dir);
-	if(chdir("..") == -1) {
-		*endofname = '\0';
-		fprintf(stderr, "find: bad directory <%s>\n", name);
-		rv = 1;
-	}
-	return(rv);
-}
-
-gmatch(s, p) /* string match as in glob */
-register char *s, *p;
-{
-	if (*s=='.' && *p!='.') return(0);
-	return amatch(s, p);
+	if (!deprecated)
+		newsyntax(argc, &argv);
+    
+	plan = find_formplan(argv);		/* execution plan */
+	find_execute(plan, paths);
 }
 
-amatch(s, p)
-register char *s, *p;
+/*
+ * find_formplan --
+ *	process the command line and create a "plan" corresponding to the
+ *	command arguments.
+ */
+PLAN *
+find_formplan(argv)
+	char **argv;
 {
-	register cc;
-	int scc, k;
-	int c, lc;
-
-	scc = *s;
-	lc = 077777;
-	switch (c = *p) {
-
-	case '[':
-		k = 0;
-		while (cc = *++p) {
-			switch (cc) {
-
-			case ']':
-				if (k)
-					return(amatch(++s, ++p));
-				else
-					return(0);
+	PLAN *plan, *tail, *new;
+	PLAN *c_print(), *find_create(), *find_squish_not(), *find_squish_or();
+	PLAN *find_squish_paren();
 
-			case '-':
-				k |= lc <= scc & scc <= (cc=p[1]);
-			}
-			if (scc==(lc=cc)) k++;
+	/*
+	 * for each argument in the command line, determine what kind of node
+	 * it is, create the appropriate node type and add the new plan node
+	 * to the end of the existing plan.  The resulting plan is a linked
+	 * list of plan nodes.  For example, the string:
+	 *
+	 *	% find . -name foo -newer bar -print
+	 *
+	 * results in the plan:
+	 *
+	 *	[-name foo]--> [-newer bar]--> [-print]
+	 *
+	 * in this diagram, `[-name foo]' represents the plan node generated
+	 * by c_name() with an argument of foo and `-->' represents the
+	 * plan->next pointer.
+	 */
+	for (plan = NULL; *argv;) {
+		if (!(new = find_create(&argv)))
+			continue;
+		if (plan == NULL)
+			tail = plan = new;
+		else {
+			tail->next = new;
+			tail = new;
 		}
-		return(0);
-
-	case '?':
-	caseq:
-		if(scc) return(amatch(++s, ++p));
-		return(0);
-	case '*':
-		return(umatch(s, ++p));
-	case 0:
-		return(!scc);
 	}
-	if (c==scc) goto caseq;
-	return(0);
-}
-
-umatch(s, p)
-register char *s, *p;
-{
-	if(*p==0) return(1);
-	while(*s)
-		if (amatch(s++, p)) return(1);
-	return(0);
-}
-
-bwrite(rp, c)
-register short *rp;
-register c;
-{
-	register short *wp = Wp;
-
-	c = (c+1) >> 1;
-	while(c--) {
-		if(!Wct) {
-again:
-			if(write(Cpio, (char *)Dbuf, Bufsize)<0) {
-				Cpio = chgreel(1, Cpio);
-				goto again;
-			}
-			Wct = Bufsize >> 1;
-			wp = Dbuf;
-			++Blocks;
+    
+	/*
+	 * if the user didn't specify one of -print, -ok or -exec, then -print
+	 * is assumed so we add a -print node on the end.  It is possible that
+	 * the user might want the -print someplace else on the command line,
+	 * but there's no way to know that.
+	 */
+	if (!output_specified) {
+		new = c_print();
+		if (plan == NULL)
+			tail = plan = new;
+		else {
+			tail->next = new;
+			tail = new;
 		}
-		*wp++ = *rp++;
-		--Wct;
-	}
-	Wp = wp;
-}
-chgreel(x, fl)
-{
-	register f;
-	char str[22];
-	FILE *devtty;
-	struct stat statb;
-	extern errno;
-
-	fprintf(stderr, "find: errno: %d, ", errno);
-	fprintf(stderr, "find: can't %s\n", x? "write output": "read input");
-	fstat(fl, &statb);
-	if((statb.st_mode&S_IFMT) != S_IFCHR)
-		exit(1);
-again:
-	fprintf(stderr, "If you want to go on, type device/file name %s\n",
-		"when ready");
-	devtty = fopen("/dev/tty", "r");
-	fgets(str, 20, devtty);
-	str[strlen(str) - 1] = '\0';
-	if(!*str)
-		exit(1);
-	close(fl);
-	if((f = open(str, x? 1: 0)) < 0) {
-		fprintf(stderr, "That didn't work");
-		fclose(devtty);
-		goto again;
 	}
-	return f;
-}
-
-#ifdef	AMES
+    
+	/*
+	 * the command line has been completely processed into a search plan
+	 * except for the (, ), !, and -o operators.  Rearrange the plan so
+	 * that the portions of the plan which are affected by the operators
+	 * are moved into operator nodes themselves.  For example:
+	 *
+	 *	[!]--> [-name foo]--> [-print]
+	 *
+	 * becomes
+	 *
+	 *	[! [-name foo] ]--> [-print]
+	 *
+	 * and
+	 *
+	 *	[(]--> [-depth]--> [-name foo]--> [)]--> [-print]
+	 *
+	 * becomes
+	 *
+	 *	[expr [-depth]-->[-name foo] ]--> [-print]
+	 *
+	 * operators are handled in order of precedence.
+	 */
+
+	plan = find_squish_paren(plan);		/* ()'s */
+	plan = find_squish_not(plan);		/* !'s */
+	plan = find_squish_or(plan);		/* -o's */
+	return(plan);
+}
+ 
 /*
- * 'fastfind' scans a file list for the full pathname of a file
- * given only a piece of the name.  The list has been processed with
- * with "front-compression" and bigram coding.  Front compression reduces
- * space by a factor of 4-5, bigram coding by a further 20-25%.
- * The codes are:
- *
- *	0-28	likeliest differential counts + offset to make nonnegative 
- *	30	escape code for out-of-range count to follow in next word
- *	128-255 bigram codes, (128 most common, as determined by 'updatedb')
- *	32-127  single character (printable) ascii residue
- *
- * A novel two-tiered string search technique is employed: 
- *
- * First, a metacharacter-free subpattern and partial pathname is
- * matched BACKWARDS to avoid full expansion of the pathname list.
- * The time savings is 40-50% over forward matching, which cannot efficiently
- * handle overlapped search patterns and compressed path residue.
- *
- * Then, the actual shell glob-style regular expression (if in this form)
- * is matched against the candidate pathnames using the slower routines
- * provided in the standard 'find'.
+ * find_execute --
+ *	take a search plan and an array of search paths and executes the plan
+ *	over all FTSENT's returned for the given search paths.
  */
-
-#define	FCODES 	"/usr/lib/find/find.codes"
-#define	YES	1
-#define	NO	0
-#define	OFFSET	14
-#define	ESCCODE	30
-
-fastfind ( pathpart )	
-	char pathpart[];
-{
-	register char *p, *s;
-	register int c; 
-	char *q, *index(), *patprep();
-	int i, count, globflag;
-	FILE *fp, *fopen();
-	char *patend, *cutoff;
-	char path[1024];
-	char bigram1[128], bigram2[128];
-	int found = NO;
-
-	if ( (fp = fopen ( FCODES, "r" )) == NULL ) {
-		fprintf ( "find: can't open %s\n", FCODES );
-		exit ( 1 );
+find_execute(plan, paths)
+	PLAN *plan;		/* search plan */
+	char **paths;		/* array of pathnames to traverse */
+{
+	FTSENT *entry;		/* current fts entry */
+	PLAN *p;
+    
+	if (!(tree = ftsopen(paths, ftsoptions, NULL))) {
+		(void)fprintf(stderr, "find: ftsopen: %s.\n", strerror(errno));
+		exit(1);
 	}
-	for ( i = 0; i < 128; i++ ) 
-		bigram1[i] = getc ( fp ),  bigram2[i] = getc ( fp );
-	
-	if ( index ( pathpart, '*' ) || index ( pathpart, '?' ) || index ( pathpart, '[' ) )
-		globflag = YES;
-	patend = patprep ( pathpart );
-
-	c = getc ( fp );
-	for ( ; ; ) {
-
-		count += ( (c == ESCCODE) ? getw ( fp ) : c ) - OFFSET;
-
-		for ( p = path + count; (c = getc ( fp )) > ESCCODE; )	/* overlay old path */
-			if ( c < 0200 )	
-				*p++ = c;
-			else		/* bigrams are parity-marked */
-				*p++ = bigram1[c & 0177],  *p++ = bigram2[c & 0177];
-		if ( c == EOF )
+	while (entry = ftsread(tree)) {
+		switch(entry->fts_info) {
+		case FTS_DNR:
+			(void)fprintf(stderr,
+			    "find: %s: unable to read.\n", entry->fts_path);
+			continue;
+		case FTS_DNX:
+			(void)fprintf(stderr,
+			    "find: %s: unable to search.\n", entry->fts_path);
+			continue;
+		case FTS_ERR:
+			(void)fprintf(stderr,
+			    "find: %s: %s.\n", entry->fts_path,
+			    strerror(errno));
+			continue;
+		case FTS_D:
+			if (depth)
+				continue;
 			break;
-		*p-- = NULL;
-		cutoff = ( found ? path : path + count);
-
-		for ( found = NO, s = p; s >= cutoff; s-- ) 
-			if ( *s == *patend ) {		/* fast first char check */
-				for ( p = patend - 1, q = s - 1; *p != NULL; p--, q-- )
-					if ( *q != *p )
-						break;
-				if ( *p == NULL ) {	/* success on fast match */
-					found = YES;
-					if ( globflag == NO || amatch ( path, pathpart ) )
-						puts ( path );
-					break;
-				}
-			}
-	}
-}
-
-/*
-    extract last glob-free subpattern in name for fast pre-match;
-    prepend '\0' for backwards match; return end of new pattern
-*/
-static char globfree[100];
-
-char *
-patprep ( name )
-	char *name;
-{
-	register char *p, *endmark;
-	register char *subp = globfree;
-
-	*subp++ = '\0';
-	p = name + strlen ( name ) - 1;
-	/*
-	   skip trailing metacharacters (and [] ranges)
-	*/
-	for ( ; p >= name; p-- )
-		if ( index ( "*?", *p ) == 0 )
+		case FTS_DC:
+			(void)fprintf(stderr,
+			    "find: directory cycle: %s.\n", entry->fts_path);
+			continue;
+		case FTS_DP:
+			if (!depth)
+				continue;
 			break;
-	if ( p < name )
-		p = name;
-	if ( *p == ']' )
-		for ( p--; p >= name; p-- )
-			if ( *p == '[' ) {
-				p--;
-				break;
+		case FTS_NS:
+			if (!(ftsoptions & FTS_NOSTAT)) {
+				(void)fprintf(stderr,
+				    "find: can't stat: %s.\n", entry->fts_path);
+				continue;
 			}
-	if ( p < name )
-		p = name;
-	/*
-	   if pattern has only metacharacters,
-	   check every path (force '/' search)
-	*/
-	if ( (p == name) && index ( "?*[]", *p ) != 0 )
-		*subp++ = '/';					
-	else {				
-		for ( endmark = p; p >= name; p-- )
-			if ( index ( "]*?", *p ) != 0 )
-				break;
-		for ( ++p; (p <= endmark) && subp < (globfree + sizeof ( globfree )); )
-			*subp++ = *p++;
+			break;
+		}
+
+		/*
+		 * call all the functions in the execution plan until one is
+		 * false or all have been executed.  This is where we do all
+		 * the work specified by the user on the command line.
+		 */
+		for (p = plan; p && (p->eval)(p, entry); p = p->next);
 	}
-	*subp = '\0';
-	return ( --subp );
+	(void)ftsclose(tree);
 }
-#endif