[unix-history] / usr / src / usr.bin / find / find.c

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.
 *
 * REVISIONS: 	James A. Woods, Informatics General Corporation,
 *		NASA Ames Research Center, 6/81.
 *
 *		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
 */
#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);
}

#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;

	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;
}

/* 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);
}

doex(com)
{
	register np;
	register char *na;
	static char *nargv[50];
	static ccode;

	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);
}

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;

	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;
			}
		}
	} 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);
			}
		}
	}
	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);
}

amatch(s, p)
register char *s, *p;
{
	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);

			case '-':
				k |= lc <= scc & scc <= (cc=p[1]);
			}
			if (scc==(lc=cc)) k++;
		}
		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;
		}
		*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
/*
 * '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'.
 */

#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 );
	}
	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 )
			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 )
			break;
	if ( p < name )
		p = name;
	if ( *p == ']' )
		for ( p--; p >= name; p-- )
			if ( *p == '[' ) {
				p--;
				break;
			}
	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++;
	}
	*subp = '\0';
	return ( --subp );
}
#endif
Commit	Line	Data
084103a7	1	static char *sccsid = "@(#)find.c 4.11 (Berkeley) %G%";
46b257b1	2
c08d5d47	3	#include <stdio.h>
365a571b	4	#include <sys/param.h>
c08d5d47 BJ	5	#include <sys/dir.h>
	6	#include <sys/stat.h>
	7	#define A_DAY 86400L /* a day full of seconds */
	8	#define EQ(x, y) (strcmp(x, y)==0)
	9
	10	int Randlast;
e8e4232e	11	char Pathname[MAXPATHLEN+1];
c08d5d47 BJ	12
	13	struct anode {
	14	int (*F)();
	15	struct anode L, R;
	16	} Node[100];
	17	int Nn; /* number of nodes */
	18	char *Fname;
	19	long Now;
	20	int Argc,
	21	Ai,
	22	Pi;
	23	char **Argv;
	24	/* cpio stuff */
	25	int Cpio;
	26	short Buf, Dbuf, *Wp;
	27	int Bufsize = 5120;
	28	int Wct = 2560;
	29
	30	long Newer;
	31
	32	struct stat Statb;
	33
	34	struct anode *exp(),
	35	*e1(),
	36	*e2(),
	37	*e3(),
	38	*mk();
	39	char *nxtarg();
	40	char Home[128];
	41	long Blocks;
	42	char *rindex();
	43	char *sbrk();
46b257b1 KM	44
46b257b1 KM	45	/*
9f796964	46	* SEE ALSO: updatedb, bigram.c, code.c
46b257b1 KM	47	* Usenix ;login:, February/March, 1983, p. 8.
	48	*
	49	* REVISIONS: James A. Woods, Informatics General Corporation,
	50	* NASA Ames Research Center, 6/81.
	51	*
	52	* The second form searches a pre-computed filelist
	53	* (constructed nightly by /usr/lib/crontab) which is
9f796964	54	* compressed by updatedb (v.i.z.) The effect of
46b257b1 KM	55	* find <name>
	56	* is similar to
	57	* find / +0 -name "<name>" -print
	58	* but much faster.
	59	*
	60	* 8/82 faster yet + incorporation of bigram coding -- jaw
	61	*
	62	* 1/83 incorporate glob-style matching -- jaw
	63	*/
	64	#define AMES 1
	65
	66	main(argc, argv)
	67	int argc;
	68	char *argv[];
c08d5d47 BJ	69	{
	70	struct anode *exlist;
	71	int paths;
	72	register char cp, sp = 0;
	73	FILE pwd, popen();
	74
46b257b1 KM	75	#ifdef AMES
	76	if (argc < 2) {
	77	fprintf(stderr,
	78	"Usage: find name, or find path-list predicate-list\n");
	79	exit(1);
	80	}
	81	if (argc == 2) {
	82	fastfind(argv[1]);
	83	exit(0);
	84	}
	85	#endif
c08d5d47 BJ	86	time(&Now);
	87	pwd = popen("pwd", "r");
	88	fgets(Home, 128, pwd);
	89	pclose(pwd);
	90	Home[strlen(Home) - 1] = '\0';
	91	Argc = argc; Argv = argv;
	92	if(argc<3) {
	93	usage: fprintf(stderr, "Usage: find path-list predicate-list\n");
	94	exit(1);
	95	}
	96	for(Ai = paths = 1; Ai < (argc-1); ++Ai, ++paths)
	97	if(*Argv[Ai] == '-' \|\| EQ(Argv[Ai], "(") \|\| EQ(Argv[Ai], "!"))
	98	break;
	99	if(paths == 1) /* no path-list */
	100	goto usage;
	101	if(!(exlist = exp())) { /* parse and compile the arguments */
	102	fprintf(stderr, "find: parsing error\n");
	103	exit(1);
	104	}
	105	if(Ai<argc) {
	106	fprintf(stderr, "find: missing conjunction\n");
	107	exit(1);
	108	}
	109	for(Pi = 1; Pi < paths; ++Pi) {
	110	sp = 0;
	111	chdir(Home);
	112	strcpy(Pathname, Argv[Pi]);
	113	if(cp = rindex(Pathname, '/')) {
	114	sp = cp + 1;
	115	*cp = '\0';
	116	if(chdir(*Pathname? Pathname: "/") == -1) {
	117	fprintf(stderr, "find: bad starting directory\n");
	118	exit(2);
	119	}
	120	*cp = '/';
	121	}
	122	Fname = sp? sp: Pathname;
	123	descend(Pathname, Fname, exlist); /* to find files that match */
	124	}
	125	if(Cpio) {
	126	strcpy(Pathname, "TRAILER!!!");
	127	Statb.st_size = 0;
	128	cpio();
	129	printf("%D blocks\n", Blocks*10);
	130	}
	131	exit(0);
	132	}
	133
	134	/* compile time functions: priority is exp()<e1()<e2()<e3() */
	135
	136	struct anode exp() { / parse ALTERNATION (-o) */
	137	int or();
	138	register struct anode * p1;
	139
	140	p1 = e1() /* get left operand */ ;
	141	if(EQ(nxtarg(), "-o")) {
	142	Randlast--;
	143	return(mk(or, p1, exp()));
	144	}
	145	else if(Ai <= Argc) --Ai;
	146	return(p1);
	147	}
	148	struct anode e1() { / parse CONCATENATION (formerly -a) */
	149	int and();
150	register struct anode * p1;
151	register char *a;
152
153	p1 = e2();
154	a = nxtarg();
155	if(EQ(a, "-a")) {
156	And:
157	Randlast--;
158	return(mk(and, p1, e1()));
159	} else if(EQ(a, "(") \|\| EQ(a, "!") \|\| (*a=='-' && !EQ(a, "-o"))) {
160	--Ai;
161	goto And;
162	} else if(Ai <= Argc) --Ai;
163	return(p1);
164	}
165	struct anode e2() { / parse NOT (!) */
166	int not();
167
168	if(Randlast) {
169	fprintf(stderr, "find: operand follows operand\n");
170	exit(1);
171	}
172	Randlast++;
173	if(EQ(nxtarg(), "!"))
174	return(mk(not, e3(), (struct anode *)0));
175	else if(Ai <= Argc) --Ai;
176	return(e3());
177	}
178	struct anode e3() { / parse parens and predicates */
179	int exeq(), ok(), glob(), mtime(), atime(), user(),
180	group(), size(), perm(), links(), print(),
181	type(), ino(), cpio(), newer();
182	struct anode *p1;
183	int i;
184	register char a, b, s;
185
186	a = nxtarg();
187	if(EQ(a, "(")) {
188	Randlast--;
189	p1 = exp();
190	a = nxtarg();
191	if(!EQ(a, ")")) goto err;
192	return(p1);
193	}
194	else if(EQ(a, "-print")) {
195	return(mk(print, (struct anode )0, (struct anode )0));
196	}
197	b = nxtarg();
198	s = *b;
199	if(s=='+') b++;
200	if(EQ(a, "-name"))
201	return(mk(glob, (struct anode )b, (struct anode )0));
202	else if(EQ(a, "-mtime"))
203	return(mk(mtime, (struct anode )atoi(b), (struct anode )s));
204	else if(EQ(a, "-atime"))
205	return(mk(atime, (struct anode )atoi(b), (struct anode )s));
206	else if(EQ(a, "-user")) {
207	if((i=getunum("/etc/passwd", b)) == -1) {
68791ee2	208	if(gmatch(b, "[0-9]*"))
c08d5d47 BJ	209	return mk(user, (struct anode )atoi(b), (struct anode )s);
	210	fprintf(stderr, "find: cannot find -user name\n");
	211	exit(1);
	212	}
	213	return(mk(user, (struct anode )i, (struct anode )s));
	214	}
	215	else if(EQ(a, "-inum"))
	216	return(mk(ino, (struct anode )atoi(b), (struct anode )s));
	217	else if(EQ(a, "-group")) {
	218	if((i=getunum("/etc/group", b)) == -1) {
85e30eca	219	if(gmatch(b, "[0-9]*"))
c08d5d47 BJ	220	return mk(group, (struct anode )atoi(b), (struct anode )s);
	221	fprintf(stderr, "find: cannot find -group name\n");
	222	exit(1);
	223	}
	224	return(mk(group, (struct anode )i, (struct anode )s));
	225	} else if(EQ(a, "-size"))
	226	return(mk(size, (struct anode )atoi(b), (struct anode )s));
	227	else if(EQ(a, "-links"))
	228	return(mk(links, (struct anode )atoi(b), (struct anode )s));
	229	else if(EQ(a, "-perm")) {
	230	for(i=0; *b ; ++b) {
	231	if(*b=='-') continue;
	232	i <<= 3;
	233	i = i + (*b - '0');
	234	}
	235	return(mk(perm, (struct anode )i, (struct anode )s));
	236	}
	237	else if(EQ(a, "-type")) {
	238	i = s=='d' ? S_IFDIR :
	239	s=='b' ? S_IFBLK :
	240	s=='c' ? S_IFCHR :
773a4280 KM	241	s=='f' ? S_IFREG :
773a4280 KM	242	s=='l' ? S_IFLNK :
e8e4232e	243	s=='s' ? S_IFSOCK :
c08d5d47 BJ	244	0;
	245	return(mk(type, (struct anode )i, (struct anode )0));
	246	}
	247	else if (EQ(a, "-exec")) {
	248	i = Ai - 1;
	249	while(!EQ(nxtarg(), ";"));
	250	return(mk(exeq, (struct anode )i, (struct anode )0));
	251	}
	252	else if (EQ(a, "-ok")) {
	253	i = Ai - 1;
	254	while(!EQ(nxtarg(), ";"));
	255	return(mk(ok, (struct anode )i, (struct anode )0));
	256	}
	257	else if(EQ(a, "-cpio")) {
	258	if((Cpio = creat(b, 0666)) < 0) {
	259	fprintf(stderr, "find: cannot create < %s >\n", s);
	260	exit(1);
	261	}
	262	Buf = (short *)sbrk(512);
	263	Wp = Dbuf = (short *)sbrk(5120);
	264	return(mk(cpio, (struct anode )0, (struct anode )0));
	265	}
	266	else if(EQ(a, "-newer")) {
	267	if(stat(b, &Statb) < 0) {
	268	fprintf(stderr, "find: cannot access < %s >\n", b);
	269	exit(1);
	270	}
	271	Newer = Statb.st_mtime;
	272	return mk(newer, (struct anode )0, (struct anode )0);
	273	}
	274	err: fprintf(stderr, "find: bad option < %s >\n", a);
	275	exit(1);
	276	}
	277	struct anode *mk(f, l, r)
	278	int (*f)();
	279	struct anode l, r;
	280	{
	281	Node[Nn].F = f;
	282	Node[Nn].L = l;
	283	Node[Nn].R = r;
	284	return(&(Node[Nn++]));
	285	}
	286
	287	char nxtarg() { / get next arg from command line */
	288	static strikes = 0;
	289
	290	if(strikes==3) {
	291	fprintf(stderr, "find: incomplete statement\n");
	292	exit(1);
	293	}
	294	if(Ai>=Argc) {
	295	strikes++;
	296	Ai = Argc + 1;
	297	return("");
	298	}
	299	return(Argv[Ai++]);
	300	}
	301
	302	/* execution time functions */
	303	and(p)
	304	register struct anode *p;
	305	{
	306	return(((p->L->F)(p->L)) && ((p->R->F)(p->R))?1:0);
	307	}
308	or(p)
309	register struct anode *p;
310	{
311	return(((p->L->F)(p->L)) \|\| ((p->R->F)(p->R))?1:0);
312	}
313	not(p)
314	register struct anode *p;
315	{
316	return( !((*p->L->F)(p->L)));
317	}
318	glob(p)
319	register struct { int f; char pat; } p;
320	{
321	return(gmatch(Fname, p->pat));
322	}
323	print()
324	{
325	puts(Pathname);
326	return(1);
327	}
328	mtime(p)
329	register struct { int f, t, s; } *p;
330	{
331	return(scomp((int)((Now - Statb.st_mtime) / A_DAY), p->t, p->s));
332	}
333	atime(p)
334	register struct { int f, t, s; } *p;
335	{
336	return(scomp((int)((Now - Statb.st_atime) / A_DAY), p->t, p->s));
337	}
338	user(p)
339	register struct { int f, u, s; } *p;
340	{
341	return(scomp(Statb.st_uid, p->u, p->s));
342	}
343	ino(p)
344	register struct { int f, u, s; } *p;
345	{
346	return(scomp((int)Statb.st_ino, p->u, p->s));
347	}
348	group(p)
349	register struct { int f, u; } *p;
350	{
351	return(p->u == Statb.st_gid);
352	}
353	links(p)
354	register struct { int f, link, s; } *p;
355	{
356	return(scomp(Statb.st_nlink, p->link, p->s));
357	}
358	size(p)
359	register struct { int f, sz, s; } *p;
360	{
361	return(scomp((int)((Statb.st_size+511)>>9), p->sz, p->s));
362	}
363	perm(p)
364	register struct { int f, per, s; } *p;
365	{
366	register i;
367	i = (p->s=='-') ? p->per : 07777; /* '-' means only arg bits */
368	return((Statb.st_mode & i & 07777) == p->per);
369	}
370	type(p)
371	register struct { int f, per, s; } *p;
372	{
373	return((Statb.st_mode&S_IFMT)==p->per);
374	}
375	exeq(p)
376	register struct { int f, com; } *p;
377	{
378	fflush(stdout); /* to flush possible `-print' */
379	return(doex(p->com));
380	}
381	ok(p)
382	struct { int f, com; } *p;
383	{
384	char c; int yes;
385	yes = 0;
386	fflush(stdout); /* to flush possible `-print' */
387	fprintf(stderr, "< %s ... %s > ? ", Argv[p->com], Pathname);
388	fflush(stderr);
389	if((c=getchar())=='y') yes = 1;
390	while(c!='\n') c = getchar();
391	if(yes) return(doex(p->com));
392	return(0);
393	}
394
395	#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];}
396	union { long l; short s[2]; char c[4]; } U;
397	long mklong(v)
398	short v[];
399	{
400	U.l = 1;
401	if(U.c[0] /* VAX */)
402	U.s[0] = v[1], U.s[1] = v[0];
403	else
404	U.s[0] = v[0], U.s[1] = v[1];
405	return U.l;
406	}
407	cpio()
408	{
409	#define MAGIC 070707
410	struct header {
411	short h_magic,
412	h_dev,
413	h_ino,
414	h_mode,
415	h_uid,
416	h_gid,
417	h_nlink,
418	h_rdev;
419	short h_mtime[2];
420	short h_namesize;
421	short h_filesize[2];
422	char h_name[256];
423	} hdr;
424	register ifile, ct;
425	static long fsz;
426	register i;
427
428	hdr.h_magic = MAGIC;
429	strcpy(hdr.h_name, !strncmp(Pathname, "./", 2)? Pathname+2: Pathname);
430	hdr.h_namesize = strlen(hdr.h_name) + 1;
431	hdr.h_uid = Statb.st_uid;
432	hdr.h_gid = Statb.st_gid;
433	hdr.h_dev = Statb.st_dev;
434	hdr.h_ino = Statb.st_ino;
435	hdr.h_mode = Statb.st_mode;
436	MKSHORT(hdr.h_mtime, Statb.st_mtime);
437	hdr.h_nlink = Statb.st_nlink;
438	fsz = hdr.h_mode & S_IFREG? Statb.st_size: 0L;
439	MKSHORT(hdr.h_filesize, fsz);
440	hdr.h_rdev = Statb.st_rdev;
441	if(EQ(hdr.h_name, "TRAILER!!!")) {
442	bwrite((short *)&hdr, (sizeof hdr-256)+hdr.h_namesize);
443	for(i = 0; i < 10; ++i)
444	bwrite(Buf, 512);
445	return;
446	}
447	if(!mklong(hdr.h_filesize))
448	return;
449	if((ifile = open(Fname, 0)) < 0) {
450	cerror:
451	fprintf(stderr, "find: cannot copy < %s >\n", hdr.h_name);
452	return;
453	}
454	bwrite((short *)&hdr, (sizeof hdr-256)+hdr.h_namesize);
455	for(fsz = mklong(hdr.h_filesize); fsz > 0; fsz -= 512) {
456	ct = fsz>512? 512: fsz;
457	if(read(ifile, (char *)Buf, ct) < 0)
458	goto cerror;
459	bwrite(Buf, ct);
460	}
461	close(ifile);
462	return;
463	}
464	newer()
465	{
466	return Statb.st_mtime > Newer;
467	}
468
469	/* support functions */
470	scomp(a, b, s) /* funny signed compare */
471	register a, b;
472	register char s;
473	{
474	if(s == '+')
475	return(a > b);
476	if(s == '-')
477	return(a < (b * -1));
478	return(a == b);
479	}
480
481	doex(com)
482	{
483	register np;
484	register char *na;
485	static char *nargv[50];
486	static ccode;
487
488	ccode = np = 0;
489	while (na=Argv[com++]) {
490	if(strcmp(na, ";")==0) break;
491	if(strcmp(na, "{}")==0) nargv[np++] = Pathname;
492	else nargv[np++] = na;
493	}
494	nargv[np] = 0;
495	if (np==0) return(9);
7f2b31d9 BJ	496	if(fork()) /parent/ {
	497	#include <signal.h>
	498	int (*old)() = signal(SIGINT, SIG_IGN);
	499	int (*oldq)() = signal(SIGQUIT, SIG_IGN);
	500	wait(&ccode);
	501	signal(SIGINT, old);
	502	signal(SIGQUIT, oldq);
	503	} else { /child/
c08d5d47 BJ	504	chdir(Home);
	505	execvp(nargv[0], nargv, np);
	506	exit(1);
	507	}
	508	return(ccode ? 0:1);
	509	}
	510
	511	getunum(f, s) char f, s; { /* find user/group name and return number */
	512	register i;
	513	register char *sp;
	514	register c;
	515	char str[20];
	516	FILE *pin;
	517
	518	i = -1;
	519	pin = fopen(f, "r");
	520	c = '\n'; /* prime with a CR */
	521	do {
	522	if(c=='\n') {
	523	sp = str;
	524	while((c = *sp++ = getc(pin)) != ':')
	525	if(c == EOF) goto RET;
	526	*--sp = '\0';
	527	if(EQ(str, s)) {
	528	while((c=getc(pin)) != ':')
	529	if(c == EOF) goto RET;
	530	sp = str;
	531	while((*sp = getc(pin)) != ':') sp++;
	532	*sp = '\0';
	533	i = atoi(str);
	534	goto RET;
	535	}
	536	}
	537	} while((c = getc(pin)) != EOF);
	538	RET:
	539	fclose(pin);
	540	return(i);
	541	}
	542
	543	descend(name, fname, exlist)
365a571b KM	544	struct anode *exlist;
365a571b KM	545	char name, fname;
c08d5d47	546	{
365a571b	547	DIR *dir = NULL;
c08d5d47	548	register struct direct *dp;
365a571b	549	register char *c1;
c08d5d47 BJ	550	int rv = 0;
	551	char *endofname;
	552
365a571b	553	if (lstat(fname, &Statb)<0) {
c08d5d47 BJ	554	fprintf(stderr, "find: bad status < %s >\n", name);
	555	return(0);
	556	}
	557	(*exlist->F)(exlist);
	558	if((Statb.st_mode&S_IFMT)!=S_IFDIR)
	559	return(1);
	560
365a571b KM	561	for (c1 = name; *c1; ++c1);
365a571b KM	562	if (*(c1-1) == '/')
c08d5d47 BJ	563	--c1;
c08d5d47 BJ	564	endofname = c1;
c08d5d47	565
365a571b	566	if (chdir(fname) == -1)
c08d5d47	567	return(0);
365a571b KM	568	if ((dir = opendir(".")) == NULL) {
	569	fprintf(stderr, "find: cannot open < %s >\n", name);
	570	rv = 0;
	571	goto ret;
	572	}
	573	for (dp = readdir(dir); dp != NULL; dp = readdir(dir)) {
	574	if ((dp->d_name[0]=='.' && dp->d_name[1]=='\0') \|\|
	575	(dp->d_name[0]=='.' && dp->d_name[1]=='.' && dp->d_name[2]=='\0'))
	576	continue;
	577	c1 = endofname;
	578	*c1++ = '/';
	579	strcpy(c1, dp->d_name);
	580	Fname = endofname+1;
	581	if(!descend(name, Fname, exlist)) {
	582	*endofname = '\0';
	583	chdir(Home);
	584	if(chdir(Pathname) == -1) {
	585	fprintf(stderr, "find: bad directory tree\n");
	586	exit(1);
c08d5d47 BJ	587	}
	588	}
	589	}
	590	rv = 1;
	591	ret:
	592	if(dir)
365a571b	593	closedir(dir);
c08d5d47 BJ	594	if(chdir("..") == -1) {
	595	*endofname = '\0';
	596	fprintf(stderr, "find: bad directory <%s>\n", name);
	597	rv = 1;
	598	}
	599	return(rv);
	600	}
	601
	602	gmatch(s, p) /* string match as in glob */
	603	register char s, p;
	604	{
	605	if (s=='.' && p!='.') return(0);
	606	return amatch(s, p);
	607	}
	608
	609	amatch(s, p)
	610	register char s, p;
	611	{
	612	register cc;
	613	int scc, k;
	614	int c, lc;
	615
	616	scc = *s;
	617	lc = 077777;
	618	switch (c = *p) {
	619
	620	case '[':
	621	k = 0;
	622	while (cc = *++p) {
	623	switch (cc) {
	624
	625	case ']':
	626	if (k)
	627	return(amatch(++s, ++p));
	628	else
	629	return(0);
	630
	631	case '-':
	632	k \|= lc <= scc & scc <= (cc=p[1]);
	633	}
	634	if (scc==(lc=cc)) k++;
	635	}
	636	return(0);
	637
	638	case '?':
	639	caseq:
	640	if(scc) return(amatch(++s, ++p));
	641	return(0);
	642	case '*':
	643	return(umatch(s, ++p));
	644	case 0:
	645	return(!scc);
	646	}
	647	if (c==scc) goto caseq;
	648	return(0);
	649	}
	650
	651	umatch(s, p)
	652	register char s, p;
	653	{
	654	if(*p==0) return(1);
	655	while(*s)
	656	if (amatch(s++, p)) return(1);
	657	return(0);
658	}
659
660	bwrite(rp, c)
661	register short *rp;
662	register c;
663	{
664	register short *wp = Wp;
665
666	c = (c+1) >> 1;
667	while(c--) {
668	if(!Wct) {
669	again:
670	if(write(Cpio, (char *)Dbuf, Bufsize)<0) {
671	Cpio = chgreel(1, Cpio);
672	goto again;
673	}
674	Wct = Bufsize >> 1;
675	wp = Dbuf;
676	++Blocks;
677	}
678	wp++ = rp++;
679	--Wct;
680	}
681	Wp = wp;
682	}
683	chgreel(x, fl)
684	{
685	register f;
686	char str[22];
687	FILE *devtty;
688	struct stat statb;
689	extern errno;
690
691	fprintf(stderr, "find: errno: %d, ", errno);
692	fprintf(stderr, "find: can't %s\n", x? "write output": "read input");
693	fstat(fl, &statb);
694	if((statb.st_mode&S_IFMT) != S_IFCHR)
695	exit(1);
696	again:
697	fprintf(stderr, "If you want to go on, type device/file name %s\n",
698	"when ready");
699	devtty = fopen("/dev/tty", "r");
700	fgets(str, 20, devtty);
701	str[strlen(str) - 1] = '\0';
702	if(!*str)
703	exit(1);
704	close(fl);
705	if((f = open(str, x? 1: 0)) < 0) {
706	fprintf(stderr, "That didn't work");
707	fclose(devtty);
708	goto again;
709	}
710	return f;
711	}
46b257b1 KM	712
	713	#ifdef AMES
	714	/*
	715	* 'fastfind' scans a file list for the full pathname of a file
	716	* given only a piece of the name. The list has been processed with
	717	* with "front-compression" and bigram coding. Front compression reduces
	718	* space by a factor of 4-5, bigram coding by a further 20-25%.
	719	* The codes are:
	720	*
	721	* 0-28 likeliest differential counts + offset to make nonnegative
	722	* 30 escape code for out-of-range count to follow in next word
9f796964	723	* 128-255 bigram codes, (128 most common, as determined by 'updatedb')
46b257b1 KM	724	* 32-127 single character (printable) ascii residue
	725	*
	726	* A novel two-tiered string search technique is employed:
	727	*
	728	* First, a metacharacter-free subpattern and partial pathname is
	729	* matched BACKWARDS to avoid full expansion of the pathname list.
	730	* The time savings is 40-50% over forward matching, which cannot efficiently
	731	* handle overlapped search patterns and compressed path residue.
	732	*
	733	* Then, the actual shell glob-style regular expression (if in this form)
	734	* is matched against the candidate pathnames using the slower routines
	735	* provided in the standard 'find'.
	736	*/
	737
9f796964	738	#define FCODES "/usr/lib/find/find.codes"
46b257b1 KM	739	#define YES 1
	740	#define NO 0
	741	#define OFFSET 14
	742	#define ESCCODE 30
	743
	744	fastfind ( pathpart )
	745	char pathpart[];
	746	{
	747	register char p, s;
	748	register int c;
	749	char q, index(), *patprep();
	750	int i, count, globflag;
	751	FILE fp, fopen();
	752	char patend, cutoff;
	753	char path[1024];
	754	char bigram1[128], bigram2[128];
	755	int found = NO;
	756
	757	if ( (fp = fopen ( FCODES, "r" )) == NULL ) {
	758	fprintf ( "find: can't open %s\n", FCODES );
	759	exit ( 1 );
	760	}
	761	for ( i = 0; i < 128; i++ )
	762	bigram1[i] = getc ( fp ), bigram2[i] = getc ( fp );
	763
	764	if ( index ( pathpart, '*' ) \|\| index ( pathpart, '?' ) \|\| index ( pathpart, '[' ) )
	765	globflag = YES;
	766	patend = patprep ( pathpart );
	767
	768	c = getc ( fp );
	769	for ( ; ; ) {
	770
	771	count += ( (c == ESCCODE) ? getw ( fp ) : c ) - OFFSET;
	772
	773	for ( p = path + count; (c = getc ( fp )) > ESCCODE; ) /* overlay old path */
	774	if ( c < 0200 )
	775	*p++ = c;
	776	else /* bigrams are parity-marked */
	777	p++ = bigram1[c & 0177], p++ = bigram2[c & 0177];
	778	if ( c == EOF )
	779	break;
	780	*p-- = NULL;
	781	cutoff = ( found ? path : path + count);
	782
	783	for ( found = NO, s = p; s >= cutoff; s-- )
	784	if ( s == patend ) { /* fast first char check */
	785	for ( p = patend - 1, q = s - 1; *p != NULL; p--, q-- )
	786	if ( q != p )
	787	break;
	788	if ( p == NULL ) { / success on fast match */
	789	found = YES;
	790	if ( globflag == NO \|\| amatch ( path, pathpart ) )
	791	puts ( path );
	792	break;
	793	}
	794	}
	795	}
	796	}
	797
	798	/*
084103a7 KM	799	extract last glob-free subpattern in name for fast pre-match;
084103a7 KM	800	prepend '\0' for backwards match; return end of new pattern
46b257b1 KM	801	*/
	802	static char globfree[100];
	803
	804	char *
084103a7 KM	805	patprep ( name )
084103a7 KM	806	char *name;
46b257b1	807	{
084103a7	808	register char p, endmark;
46b257b1 KM	809	register char *subp = globfree;
46b257b1 KM	810
084103a7 KM	811	*subp++ = '\0';
	812	p = name + strlen ( name ) - 1;
	813	/*
	814	skip trailing metacharacters (and [] ranges)
	815	*/
	816	for ( ; p >= name; p-- )
	817	if ( index ( "?", p ) == 0 )
	818	break;
	819	if ( p < name )
	820	p = name;
	821	if ( *p == ']' )
	822	for ( p--; p >= name; p-- )
	823	if ( *p == '[' ) {
	824	p--;
	825	break;
	826	}
	827	if ( p < name )
	828	p = name;
	829	/*
	830	if pattern has only metacharacters,
	831	check every path (force '/' search)
	832	*/
	833	if ( (p == name) && index ( "?[]", p ) != 0 )
	834	*subp++ = '/';
	835	else {
	836	for ( endmark = p; p >= name; p-- )
	837	if ( index ( "]?", p ) != 0 )
	838	break;
	839	for ( ++p; (p <= endmark) && subp < (globfree + sizeof ( globfree )); )
46b257b1	840	subp++ = p++;
084103a7 KM	841	}
084103a7 KM	842	*subp = '\0';
46b257b1 KM	843	return ( --subp );
	844	}
	845	#endif