Commit | Line | Data |
---|---|---|
9f796964 | 1 | static char *sccsid = "@(#)find.c 4.9 (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; | |
11 | char Pathname[200]; | |
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 | |
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 : |
242 | s=='l' ? S_IFLNK : | |
c08d5d47 BJ |
243 | 0; |
244 | return(mk(type, (struct anode *)i, (struct anode *)0)); | |
245 | } | |
246 | else if (EQ(a, "-exec")) { | |
247 | i = Ai - 1; | |
248 | while(!EQ(nxtarg(), ";")); | |
249 | return(mk(exeq, (struct anode *)i, (struct anode *)0)); | |
250 | } | |
251 | else if (EQ(a, "-ok")) { | |
252 | i = Ai - 1; | |
253 | while(!EQ(nxtarg(), ";")); | |
254 | return(mk(ok, (struct anode *)i, (struct anode *)0)); | |
255 | } | |
256 | else if(EQ(a, "-cpio")) { | |
257 | if((Cpio = creat(b, 0666)) < 0) { | |
258 | fprintf(stderr, "find: cannot create < %s >\n", s); | |
259 | exit(1); | |
260 | } | |
261 | Buf = (short *)sbrk(512); | |
262 | Wp = Dbuf = (short *)sbrk(5120); | |
263 | return(mk(cpio, (struct anode *)0, (struct anode *)0)); | |
264 | } | |
265 | else if(EQ(a, "-newer")) { | |
266 | if(stat(b, &Statb) < 0) { | |
267 | fprintf(stderr, "find: cannot access < %s >\n", b); | |
268 | exit(1); | |
269 | } | |
270 | Newer = Statb.st_mtime; | |
271 | return mk(newer, (struct anode *)0, (struct anode *)0); | |
272 | } | |
273 | err: fprintf(stderr, "find: bad option < %s >\n", a); | |
274 | exit(1); | |
275 | } | |
276 | struct anode *mk(f, l, r) | |
277 | int (*f)(); | |
278 | struct anode *l, *r; | |
279 | { | |
280 | Node[Nn].F = f; | |
281 | Node[Nn].L = l; | |
282 | Node[Nn].R = r; | |
283 | return(&(Node[Nn++])); | |
284 | } | |
285 | ||
286 | char *nxtarg() { /* get next arg from command line */ | |
287 | static strikes = 0; | |
288 | ||
289 | if(strikes==3) { | |
290 | fprintf(stderr, "find: incomplete statement\n"); | |
291 | exit(1); | |
292 | } | |
293 | if(Ai>=Argc) { | |
294 | strikes++; | |
295 | Ai = Argc + 1; | |
296 | return(""); | |
297 | } | |
298 | return(Argv[Ai++]); | |
299 | } | |
300 | ||
301 | /* execution time functions */ | |
302 | and(p) | |
303 | register struct anode *p; | |
304 | { | |
305 | return(((*p->L->F)(p->L)) && ((*p->R->F)(p->R))?1:0); | |
306 | } | |
307 | or(p) | |
308 | register struct anode *p; | |
309 | { | |
310 | return(((*p->L->F)(p->L)) || ((*p->R->F)(p->R))?1:0); | |
311 | } | |
312 | not(p) | |
313 | register struct anode *p; | |
314 | { | |
315 | return( !((*p->L->F)(p->L))); | |
316 | } | |
317 | glob(p) | |
318 | register struct { int f; char *pat; } *p; | |
319 | { | |
320 | return(gmatch(Fname, p->pat)); | |
321 | } | |
322 | print() | |
323 | { | |
324 | puts(Pathname); | |
325 | return(1); | |
326 | } | |
327 | mtime(p) | |
328 | register struct { int f, t, s; } *p; | |
329 | { | |
330 | return(scomp((int)((Now - Statb.st_mtime) / A_DAY), p->t, p->s)); | |
331 | } | |
332 | atime(p) | |
333 | register struct { int f, t, s; } *p; | |
334 | { | |
335 | return(scomp((int)((Now - Statb.st_atime) / A_DAY), p->t, p->s)); | |
336 | } | |
337 | user(p) | |
338 | register struct { int f, u, s; } *p; | |
339 | { | |
340 | return(scomp(Statb.st_uid, p->u, p->s)); | |
341 | } | |
342 | ino(p) | |
343 | register struct { int f, u, s; } *p; | |
344 | { | |
345 | return(scomp((int)Statb.st_ino, p->u, p->s)); | |
346 | } | |
347 | group(p) | |
348 | register struct { int f, u; } *p; | |
349 | { | |
350 | return(p->u == Statb.st_gid); | |
351 | } | |
352 | links(p) | |
353 | register struct { int f, link, s; } *p; | |
354 | { | |
355 | return(scomp(Statb.st_nlink, p->link, p->s)); | |
356 | } | |
357 | size(p) | |
358 | register struct { int f, sz, s; } *p; | |
359 | { | |
360 | return(scomp((int)((Statb.st_size+511)>>9), p->sz, p->s)); | |
361 | } | |
362 | perm(p) | |
363 | register struct { int f, per, s; } *p; | |
364 | { | |
365 | register i; | |
366 | i = (p->s=='-') ? p->per : 07777; /* '-' means only arg bits */ | |
367 | return((Statb.st_mode & i & 07777) == p->per); | |
368 | } | |
369 | type(p) | |
370 | register struct { int f, per, s; } *p; | |
371 | { | |
372 | return((Statb.st_mode&S_IFMT)==p->per); | |
373 | } | |
374 | exeq(p) | |
375 | register struct { int f, com; } *p; | |
376 | { | |
377 | fflush(stdout); /* to flush possible `-print' */ | |
378 | return(doex(p->com)); | |
379 | } | |
380 | ok(p) | |
381 | struct { int f, com; } *p; | |
382 | { | |
383 | char c; int yes; | |
384 | yes = 0; | |
385 | fflush(stdout); /* to flush possible `-print' */ | |
386 | fprintf(stderr, "< %s ... %s > ? ", Argv[p->com], Pathname); | |
387 | fflush(stderr); | |
388 | if((c=getchar())=='y') yes = 1; | |
389 | while(c!='\n') c = getchar(); | |
390 | if(yes) return(doex(p->com)); | |
391 | return(0); | |
392 | } | |
393 | ||
394 | #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];} | |
395 | union { long l; short s[2]; char c[4]; } U; | |
396 | long mklong(v) | |
397 | short v[]; | |
398 | { | |
399 | U.l = 1; | |
400 | if(U.c[0] /* VAX */) | |
401 | U.s[0] = v[1], U.s[1] = v[0]; | |
402 | else | |
403 | U.s[0] = v[0], U.s[1] = v[1]; | |
404 | return U.l; | |
405 | } | |
406 | cpio() | |
407 | { | |
408 | #define MAGIC 070707 | |
409 | struct header { | |
410 | short h_magic, | |
411 | h_dev, | |
412 | h_ino, | |
413 | h_mode, | |
414 | h_uid, | |
415 | h_gid, | |
416 | h_nlink, | |
417 | h_rdev; | |
418 | short h_mtime[2]; | |
419 | short h_namesize; | |
420 | short h_filesize[2]; | |
421 | char h_name[256]; | |
422 | } hdr; | |
423 | register ifile, ct; | |
424 | static long fsz; | |
425 | register i; | |
426 | ||
427 | hdr.h_magic = MAGIC; | |
428 | strcpy(hdr.h_name, !strncmp(Pathname, "./", 2)? Pathname+2: Pathname); | |
429 | hdr.h_namesize = strlen(hdr.h_name) + 1; | |
430 | hdr.h_uid = Statb.st_uid; | |
431 | hdr.h_gid = Statb.st_gid; | |
432 | hdr.h_dev = Statb.st_dev; | |
433 | hdr.h_ino = Statb.st_ino; | |
434 | hdr.h_mode = Statb.st_mode; | |
435 | MKSHORT(hdr.h_mtime, Statb.st_mtime); | |
436 | hdr.h_nlink = Statb.st_nlink; | |
437 | fsz = hdr.h_mode & S_IFREG? Statb.st_size: 0L; | |
438 | MKSHORT(hdr.h_filesize, fsz); | |
439 | hdr.h_rdev = Statb.st_rdev; | |
440 | if(EQ(hdr.h_name, "TRAILER!!!")) { | |
441 | bwrite((short *)&hdr, (sizeof hdr-256)+hdr.h_namesize); | |
442 | for(i = 0; i < 10; ++i) | |
443 | bwrite(Buf, 512); | |
444 | return; | |
445 | } | |
446 | if(!mklong(hdr.h_filesize)) | |
447 | return; | |
448 | if((ifile = open(Fname, 0)) < 0) { | |
449 | cerror: | |
450 | fprintf(stderr, "find: cannot copy < %s >\n", hdr.h_name); | |
451 | return; | |
452 | } | |
453 | bwrite((short *)&hdr, (sizeof hdr-256)+hdr.h_namesize); | |
454 | for(fsz = mklong(hdr.h_filesize); fsz > 0; fsz -= 512) { | |
455 | ct = fsz>512? 512: fsz; | |
456 | if(read(ifile, (char *)Buf, ct) < 0) | |
457 | goto cerror; | |
458 | bwrite(Buf, ct); | |
459 | } | |
460 | close(ifile); | |
461 | return; | |
462 | } | |
463 | newer() | |
464 | { | |
465 | return Statb.st_mtime > Newer; | |
466 | } | |
467 | ||
468 | /* support functions */ | |
469 | scomp(a, b, s) /* funny signed compare */ | |
470 | register a, b; | |
471 | register char s; | |
472 | { | |
473 | if(s == '+') | |
474 | return(a > b); | |
475 | if(s == '-') | |
476 | return(a < (b * -1)); | |
477 | return(a == b); | |
478 | } | |
479 | ||
480 | doex(com) | |
481 | { | |
482 | register np; | |
483 | register char *na; | |
484 | static char *nargv[50]; | |
485 | static ccode; | |
486 | ||
487 | ccode = np = 0; | |
488 | while (na=Argv[com++]) { | |
489 | if(strcmp(na, ";")==0) break; | |
490 | if(strcmp(na, "{}")==0) nargv[np++] = Pathname; | |
491 | else nargv[np++] = na; | |
492 | } | |
493 | nargv[np] = 0; | |
494 | if (np==0) return(9); | |
7f2b31d9 BJ |
495 | if(fork()) /*parent*/ { |
496 | #include <signal.h> | |
497 | int (*old)() = signal(SIGINT, SIG_IGN); | |
498 | int (*oldq)() = signal(SIGQUIT, SIG_IGN); | |
499 | wait(&ccode); | |
500 | signal(SIGINT, old); | |
501 | signal(SIGQUIT, oldq); | |
502 | } else { /*child*/ | |
c08d5d47 BJ |
503 | chdir(Home); |
504 | execvp(nargv[0], nargv, np); | |
505 | exit(1); | |
506 | } | |
507 | return(ccode ? 0:1); | |
508 | } | |
509 | ||
510 | getunum(f, s) char *f, *s; { /* find user/group name and return number */ | |
511 | register i; | |
512 | register char *sp; | |
513 | register c; | |
514 | char str[20]; | |
515 | FILE *pin; | |
516 | ||
517 | i = -1; | |
518 | pin = fopen(f, "r"); | |
519 | c = '\n'; /* prime with a CR */ | |
520 | do { | |
521 | if(c=='\n') { | |
522 | sp = str; | |
523 | while((c = *sp++ = getc(pin)) != ':') | |
524 | if(c == EOF) goto RET; | |
525 | *--sp = '\0'; | |
526 | if(EQ(str, s)) { | |
527 | while((c=getc(pin)) != ':') | |
528 | if(c == EOF) goto RET; | |
529 | sp = str; | |
530 | while((*sp = getc(pin)) != ':') sp++; | |
531 | *sp = '\0'; | |
532 | i = atoi(str); | |
533 | goto RET; | |
534 | } | |
535 | } | |
536 | } while((c = getc(pin)) != EOF); | |
537 | RET: | |
538 | fclose(pin); | |
539 | return(i); | |
540 | } | |
541 | ||
542 | descend(name, fname, exlist) | |
365a571b KM |
543 | struct anode *exlist; |
544 | char *name, *fname; | |
c08d5d47 | 545 | { |
365a571b | 546 | DIR *dir = NULL; |
c08d5d47 | 547 | register struct direct *dp; |
365a571b | 548 | register char *c1; |
c08d5d47 BJ |
549 | int rv = 0; |
550 | char *endofname; | |
551 | ||
365a571b | 552 | if (lstat(fname, &Statb)<0) { |
c08d5d47 BJ |
553 | fprintf(stderr, "find: bad status < %s >\n", name); |
554 | return(0); | |
555 | } | |
556 | (*exlist->F)(exlist); | |
557 | if((Statb.st_mode&S_IFMT)!=S_IFDIR) | |
558 | return(1); | |
559 | ||
365a571b KM |
560 | for (c1 = name; *c1; ++c1); |
561 | if (*(c1-1) == '/') | |
c08d5d47 BJ |
562 | --c1; |
563 | endofname = c1; | |
c08d5d47 | 564 | |
365a571b | 565 | if (chdir(fname) == -1) |
c08d5d47 | 566 | return(0); |
365a571b KM |
567 | if ((dir = opendir(".")) == NULL) { |
568 | fprintf(stderr, "find: cannot open < %s >\n", name); | |
569 | rv = 0; | |
570 | goto ret; | |
571 | } | |
572 | for (dp = readdir(dir); dp != NULL; dp = readdir(dir)) { | |
573 | if ((dp->d_name[0]=='.' && dp->d_name[1]=='\0') || | |
574 | (dp->d_name[0]=='.' && dp->d_name[1]=='.' && dp->d_name[2]=='\0')) | |
575 | continue; | |
576 | c1 = endofname; | |
577 | *c1++ = '/'; | |
578 | strcpy(c1, dp->d_name); | |
579 | Fname = endofname+1; | |
580 | if(!descend(name, Fname, exlist)) { | |
581 | *endofname = '\0'; | |
582 | chdir(Home); | |
583 | if(chdir(Pathname) == -1) { | |
584 | fprintf(stderr, "find: bad directory tree\n"); | |
585 | exit(1); | |
c08d5d47 BJ |
586 | } |
587 | } | |
588 | } | |
589 | rv = 1; | |
590 | ret: | |
591 | if(dir) | |
365a571b | 592 | closedir(dir); |
c08d5d47 BJ |
593 | if(chdir("..") == -1) { |
594 | *endofname = '\0'; | |
595 | fprintf(stderr, "find: bad directory <%s>\n", name); | |
596 | rv = 1; | |
597 | } | |
598 | return(rv); | |
599 | } | |
600 | ||
601 | gmatch(s, p) /* string match as in glob */ | |
602 | register char *s, *p; | |
603 | { | |
604 | if (*s=='.' && *p!='.') return(0); | |
605 | return amatch(s, p); | |
606 | } | |
607 | ||
608 | amatch(s, p) | |
609 | register char *s, *p; | |
610 | { | |
611 | register cc; | |
612 | int scc, k; | |
613 | int c, lc; | |
614 | ||
615 | scc = *s; | |
616 | lc = 077777; | |
617 | switch (c = *p) { | |
618 | ||
619 | case '[': | |
620 | k = 0; | |
621 | while (cc = *++p) { | |
622 | switch (cc) { | |
623 | ||
624 | case ']': | |
625 | if (k) | |
626 | return(amatch(++s, ++p)); | |
627 | else | |
628 | return(0); | |
629 | ||
630 | case '-': | |
631 | k |= lc <= scc & scc <= (cc=p[1]); | |
632 | } | |
633 | if (scc==(lc=cc)) k++; | |
634 | } | |
635 | return(0); | |
636 | ||
637 | case '?': | |
638 | caseq: | |
639 | if(scc) return(amatch(++s, ++p)); | |
640 | return(0); | |
641 | case '*': | |
642 | return(umatch(s, ++p)); | |
643 | case 0: | |
644 | return(!scc); | |
645 | } | |
646 | if (c==scc) goto caseq; | |
647 | return(0); | |
648 | } | |
649 | ||
650 | umatch(s, p) | |
651 | register char *s, *p; | |
652 | { | |
653 | if(*p==0) return(1); | |
654 | while(*s) | |
655 | if (amatch(s++, p)) return(1); | |
656 | return(0); | |
657 | } | |
658 | ||
659 | bwrite(rp, c) | |
660 | register short *rp; | |
661 | register c; | |
662 | { | |
663 | register short *wp = Wp; | |
664 | ||
665 | c = (c+1) >> 1; | |
666 | while(c--) { | |
667 | if(!Wct) { | |
668 | again: | |
669 | if(write(Cpio, (char *)Dbuf, Bufsize)<0) { | |
670 | Cpio = chgreel(1, Cpio); | |
671 | goto again; | |
672 | } | |
673 | Wct = Bufsize >> 1; | |
674 | wp = Dbuf; | |
675 | ++Blocks; | |
676 | } | |
677 | *wp++ = *rp++; | |
678 | --Wct; | |
679 | } | |
680 | Wp = wp; | |
681 | } | |
682 | chgreel(x, fl) | |
683 | { | |
684 | register f; | |
685 | char str[22]; | |
686 | FILE *devtty; | |
687 | struct stat statb; | |
688 | extern errno; | |
689 | ||
690 | fprintf(stderr, "find: errno: %d, ", errno); | |
691 | fprintf(stderr, "find: can't %s\n", x? "write output": "read input"); | |
692 | fstat(fl, &statb); | |
693 | if((statb.st_mode&S_IFMT) != S_IFCHR) | |
694 | exit(1); | |
695 | again: | |
696 | fprintf(stderr, "If you want to go on, type device/file name %s\n", | |
697 | "when ready"); | |
698 | devtty = fopen("/dev/tty", "r"); | |
699 | fgets(str, 20, devtty); | |
700 | str[strlen(str) - 1] = '\0'; | |
701 | if(!*str) | |
702 | exit(1); | |
703 | close(fl); | |
704 | if((f = open(str, x? 1: 0)) < 0) { | |
705 | fprintf(stderr, "That didn't work"); | |
706 | fclose(devtty); | |
707 | goto again; | |
708 | } | |
709 | return f; | |
710 | } | |
46b257b1 KM |
711 | |
712 | #ifdef AMES | |
713 | /* | |
714 | * 'fastfind' scans a file list for the full pathname of a file | |
715 | * given only a piece of the name. The list has been processed with | |
716 | * with "front-compression" and bigram coding. Front compression reduces | |
717 | * space by a factor of 4-5, bigram coding by a further 20-25%. | |
718 | * The codes are: | |
719 | * | |
720 | * 0-28 likeliest differential counts + offset to make nonnegative | |
721 | * 30 escape code for out-of-range count to follow in next word | |
9f796964 | 722 | * 128-255 bigram codes, (128 most common, as determined by 'updatedb') |
46b257b1 KM |
723 | * 32-127 single character (printable) ascii residue |
724 | * | |
725 | * A novel two-tiered string search technique is employed: | |
726 | * | |
727 | * First, a metacharacter-free subpattern and partial pathname is | |
728 | * matched BACKWARDS to avoid full expansion of the pathname list. | |
729 | * The time savings is 40-50% over forward matching, which cannot efficiently | |
730 | * handle overlapped search patterns and compressed path residue. | |
731 | * | |
732 | * Then, the actual shell glob-style regular expression (if in this form) | |
733 | * is matched against the candidate pathnames using the slower routines | |
734 | * provided in the standard 'find'. | |
735 | */ | |
736 | ||
9f796964 | 737 | #define FCODES "/usr/lib/find/find.codes" |
46b257b1 KM |
738 | #define YES 1 |
739 | #define NO 0 | |
740 | #define OFFSET 14 | |
741 | #define ESCCODE 30 | |
742 | ||
743 | fastfind ( pathpart ) | |
744 | char pathpart[]; | |
745 | { | |
746 | register char *p, *s; | |
747 | register int c; | |
748 | char *q, *index(), *patprep(); | |
749 | int i, count, globflag; | |
750 | FILE *fp, *fopen(); | |
751 | char *patend, *cutoff; | |
752 | char path[1024]; | |
753 | char bigram1[128], bigram2[128]; | |
754 | int found = NO; | |
755 | ||
756 | if ( (fp = fopen ( FCODES, "r" )) == NULL ) { | |
757 | fprintf ( "find: can't open %s\n", FCODES ); | |
758 | exit ( 1 ); | |
759 | } | |
760 | for ( i = 0; i < 128; i++ ) | |
761 | bigram1[i] = getc ( fp ), bigram2[i] = getc ( fp ); | |
762 | ||
763 | if ( index ( pathpart, '*' ) || index ( pathpart, '?' ) || index ( pathpart, '[' ) ) | |
764 | globflag = YES; | |
765 | patend = patprep ( pathpart ); | |
766 | ||
767 | c = getc ( fp ); | |
768 | for ( ; ; ) { | |
769 | ||
770 | count += ( (c == ESCCODE) ? getw ( fp ) : c ) - OFFSET; | |
771 | ||
772 | for ( p = path + count; (c = getc ( fp )) > ESCCODE; ) /* overlay old path */ | |
773 | if ( c < 0200 ) | |
774 | *p++ = c; | |
775 | else /* bigrams are parity-marked */ | |
776 | *p++ = bigram1[c & 0177], *p++ = bigram2[c & 0177]; | |
777 | if ( c == EOF ) | |
778 | break; | |
779 | *p-- = NULL; | |
780 | cutoff = ( found ? path : path + count); | |
781 | ||
782 | for ( found = NO, s = p; s >= cutoff; s-- ) | |
783 | if ( *s == *patend ) { /* fast first char check */ | |
784 | for ( p = patend - 1, q = s - 1; *p != NULL; p--, q-- ) | |
785 | if ( *q != *p ) | |
786 | break; | |
787 | if ( *p == NULL ) { /* success on fast match */ | |
788 | found = YES; | |
789 | if ( globflag == NO || amatch ( path, pathpart ) ) | |
790 | puts ( path ); | |
791 | break; | |
792 | } | |
793 | } | |
794 | } | |
795 | } | |
796 | ||
797 | /* | |
798 | extract first glob-free subpattern for fast pre-match; | |
799 | prepend NULL for backwards match; return end of pattern | |
800 | */ | |
801 | static char globfree[100]; | |
802 | ||
803 | char * | |
804 | patprep ( p ) | |
805 | register char *p; | |
806 | { | |
807 | register char *subp = globfree; | |
808 | ||
809 | while ( *p == '*' || *p == '?' ) | |
810 | p++; | |
811 | if ( *p == '[' ) { | |
812 | while ( *p != ']' && *p != NULL ) | |
813 | p++; | |
814 | p++; | |
815 | } | |
816 | *subp++ = NULL; | |
817 | if ( *p != NULL ) /* copy first noglob string */ | |
818 | while ( *p != '*' && *p != '?' && *p != '[' && *p != NULL && | |
819 | subp < (globfree + sizeof(globfree)) ) | |
820 | *subp++ = *p++; | |
821 | else /* pattern has noglob chars only */ | |
822 | *subp++ = '/'; /* ... check every path */ | |
823 | *subp = NULL; | |
824 | return ( --subp ); | |
825 | } | |
826 | #endif |