#include <u.h>#include <libc.h>#include <bio.h> char 	*defargv[] = {".", 0};char	*fmt = "%q\n";int	flag[256];uint	dev ;uint	type;int	errors;Biobuf	out; voidwarn(char *s){	if(flag['f'] == 0)		fprint(2, "find: %s: %r\n", s);	errors = 1;} voidusage(void){	fprint(2, "usage: find [-1dfq] [path ...]\n");	exits("usage");} /*  if you think this scales you'd be wrong.  this is is 1/128th of a linear search.  */ enum{	Ncache		= 128,		/* must be power of two */	Cachebits	= Ncache-1,}; typedef struct{	vlong	qpath;	uint	dev;	uchar	type;} Fsig; typedef	struct	Cache	Cache;struct Cache{	Fsig	*cache;	int	n;	int	nalloc;} cache[Ncache]; voidclearcache(void){	int i; 	for(i = 0; i < nelem(cache); i++)		free(cache[i].cache);	memset(cache, 0, nelem(cache)*sizeof cache[0]);} intseen(Dir *dir){	int i;	Fsig *f;	Cache *c; 	c = &cache[dir->qid.path&Cachebits];	f = c->cache;	for(i = 0; i < c->n; i++)		if(dir->qid.path == f[i].qpath			&& dir->type == f[i].type			&& dir->dev == f[i].dev)			return 1;	if(i == c->nalloc){		c->nalloc += 20;		f = c->cache = realloc(c->cache, c->nalloc*sizeof *f);	}	f[c->n].qpath = dir->qid.path;	f[c->n].type = dir->type;	f[c->n].dev = dir->dev;	c->n++;	return 0;} intdskip(Dir *d){	if(flag['1']){		if(dev == 0 && type == 0){			dev = d->dev;			type = d->type;		}		if(d->dev != dev || d->type != type)			return 0;	}	return 1;} intskip(Dir *d){	if(strcmp(d->name, ".") == 0|| strcmp(d->name, "..") == 0 || seen(d))		return 1;	return 0;} voidfind(char *name){	int fd, n;	Dir *buf, *p, *e;	char file[256]; 	if((fd = open(name, OREAD)) < 0) {		warn(name);		return;	}	if(!flag['D'])		Bprint(&out, fmt, name);	for(; (n = dirread(fd, &buf)) > 0; free(buf))		for(p = buf, e = p+n; p < e; p++){			snprint(file, sizeof file, "%s/%s", name, p->name);			if((p->qid.type&QTDIR) == 0 || !dskip(p)){				if(!flag['d'])					Bprint(&out, fmt, file);			}else if(!skip(p))				find(file);		}	close(fd);} voidmain(int argc, char *argv[]){	doquote = needsrcquote;	quotefmtinstall(); 	ARGBEGIN{	case 'D':	case 'd':	case 'f':	case '1':		flag[ARGC()] = 1;		break;	case 'q':		fmt = "%s\n";		break;	default:		usage();	}ARGEND 	Binit(&out, 1, OWRITE);	if(argc == 0)		argv = defargv;	for(; *argv; argv++){		find(*argv);		clearcache();	}	Bterm(&out);	if(errors)		exits("errors");	exits("");}