1 static char *sccsid = "@(#)find.c 4.1 (Berkeley) 10/01/80"; 2 /* find COMPILE: cc -o find -s -O -i find.c -lS */ 3 #include <stdio.h> 4 #include <sys/types.h> 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(); 44 main(argc, argv) char *argv[]; 45 { 46 struct anode *exlist; 47 int paths; 48 register char *cp, *sp = 0; 49 FILE *pwd, *popen(); 50 51 time(&Now); 52 pwd = popen("pwd", "r"); 53 fgets(Home, 128, pwd); 54 pclose(pwd); 55 Home[strlen(Home) - 1] = '\0'; 56 Argc = argc; Argv = argv; 57 if(argc<3) { 58 usage: fprintf(stderr, "Usage: find path-list predicate-list\n"); 59 exit(1); 60 } 61 for(Ai = paths = 1; Ai < (argc-1); ++Ai, ++paths) 62 if(*Argv[Ai] == '-' || EQ(Argv[Ai], "(") || EQ(Argv[Ai], "!")) 63 break; 64 if(paths == 1) /* no path-list */ 65 goto usage; 66 if(!(exlist = exp())) { /* parse and compile the arguments */ 67 fprintf(stderr, "find: parsing error\n"); 68 exit(1); 69 } 70 if(Ai<argc) { 71 fprintf(stderr, "find: missing conjunction\n"); 72 exit(1); 73 } 74 for(Pi = 1; Pi < paths; ++Pi) { 75 sp = 0; 76 chdir(Home); 77 strcpy(Pathname, Argv[Pi]); 78 if(cp = rindex(Pathname, '/')) { 79 sp = cp + 1; 80 *cp = '\0'; 81 if(chdir(*Pathname? Pathname: "/") == -1) { 82 fprintf(stderr, "find: bad starting directory\n"); 83 exit(2); 84 } 85 *cp = '/'; 86 } 87 Fname = sp? sp: Pathname; 88 descend(Pathname, Fname, exlist); /* to find files that match */ 89 } 90 if(Cpio) { 91 strcpy(Pathname, "TRAILER!!!"); 92 Statb.st_size = 0; 93 cpio(); 94 printf("%D blocks\n", Blocks*10); 95 } 96 exit(0); 97 } 98 99 /* compile time functions: priority is exp()<e1()<e2()<e3() */ 100 101 struct anode *exp() { /* parse ALTERNATION (-o) */ 102 int or(); 103 register struct anode * p1; 104 105 p1 = e1() /* get left operand */ ; 106 if(EQ(nxtarg(), "-o")) { 107 Randlast--; 108 return(mk(or, p1, exp())); 109 } 110 else if(Ai <= Argc) --Ai; 111 return(p1); 112 } 113 struct anode *e1() { /* parse CONCATENATION (formerly -a) */ 114 int and(); 115 register struct anode * p1; 116 register char *a; 117 118 p1 = e2(); 119 a = nxtarg(); 120 if(EQ(a, "-a")) { 121 And: 122 Randlast--; 123 return(mk(and, p1, e1())); 124 } else if(EQ(a, "(") || EQ(a, "!") || (*a=='-' && !EQ(a, "-o"))) { 125 --Ai; 126 goto And; 127 } else if(Ai <= Argc) --Ai; 128 return(p1); 129 } 130 struct anode *e2() { /* parse NOT (!) */ 131 int not(); 132 133 if(Randlast) { 134 fprintf(stderr, "find: operand follows operand\n"); 135 exit(1); 136 } 137 Randlast++; 138 if(EQ(nxtarg(), "!")) 139 return(mk(not, e3(), (struct anode *)0)); 140 else if(Ai <= Argc) --Ai; 141 return(e3()); 142 } 143 struct anode *e3() { /* parse parens and predicates */ 144 int exeq(), ok(), glob(), mtime(), atime(), user(), 145 group(), size(), perm(), links(), print(), 146 type(), ino(), cpio(), newer(); 147 struct anode *p1; 148 int i; 149 register char *a, *b, s; 150 151 a = nxtarg(); 152 if(EQ(a, "(")) { 153 Randlast--; 154 p1 = exp(); 155 a = nxtarg(); 156 if(!EQ(a, ")")) goto err; 157 return(p1); 158 } 159 else if(EQ(a, "-print")) { 160 return(mk(print, (struct anode *)0, (struct anode *)0)); 161 } 162 b = nxtarg(); 163 s = *b; 164 if(s=='+') b++; 165 if(EQ(a, "-name")) 166 return(mk(glob, (struct anode *)b, (struct anode *)0)); 167 else if(EQ(a, "-mtime")) 168 return(mk(mtime, (struct anode *)atoi(b), (struct anode *)s)); 169 else if(EQ(a, "-atime")) 170 return(mk(atime, (struct anode *)atoi(b), (struct anode *)s)); 171 else if(EQ(a, "-user")) { 172 if((i=getunum("/etc/passwd", b)) == -1) { 173 if(gmatch(b, "[0-9][0-9]*")) 174 return mk(user, (struct anode *)atoi(b), (struct anode *)s); 175 fprintf(stderr, "find: cannot find -user name\n"); 176 exit(1); 177 } 178 return(mk(user, (struct anode *)i, (struct anode *)s)); 179 } 180 else if(EQ(a, "-inum")) 181 return(mk(ino, (struct anode *)atoi(b), (struct anode *)s)); 182 else if(EQ(a, "-group")) { 183 if((i=getunum("/etc/group", b)) == -1) { 184 if(gmatch(b, "[0-9][0-9]*")) 185 return mk(group, (struct anode *)atoi(b), (struct anode *)s); 186 fprintf(stderr, "find: cannot find -group name\n"); 187 exit(1); 188 } 189 return(mk(group, (struct anode *)i, (struct anode *)s)); 190 } else if(EQ(a, "-size")) 191 return(mk(size, (struct anode *)atoi(b), (struct anode *)s)); 192 else if(EQ(a, "-links")) 193 return(mk(links, (struct anode *)atoi(b), (struct anode *)s)); 194 else if(EQ(a, "-perm")) { 195 for(i=0; *b ; ++b) { 196 if(*b=='-') continue; 197 i <<= 3; 198 i = i + (*b - '0'); 199 } 200 return(mk(perm, (struct anode *)i, (struct anode *)s)); 201 } 202 else if(EQ(a, "-type")) { 203 i = s=='d' ? S_IFDIR : 204 s=='b' ? S_IFBLK : 205 s=='c' ? S_IFCHR : 206 s=='f' ? 0100000 : 207 0; 208 return(mk(type, (struct anode *)i, (struct anode *)0)); 209 } 210 else if (EQ(a, "-exec")) { 211 i = Ai - 1; 212 while(!EQ(nxtarg(), ";")); 213 return(mk(exeq, (struct anode *)i, (struct anode *)0)); 214 } 215 else if (EQ(a, "-ok")) { 216 i = Ai - 1; 217 while(!EQ(nxtarg(), ";")); 218 return(mk(ok, (struct anode *)i, (struct anode *)0)); 219 } 220 else if(EQ(a, "-cpio")) { 221 if((Cpio = creat(b, 0666)) < 0) { 222 fprintf(stderr, "find: cannot create < %s >\n", s); 223 exit(1); 224 } 225 Buf = (short *)sbrk(512); 226 Wp = Dbuf = (short *)sbrk(5120); 227 return(mk(cpio, (struct anode *)0, (struct anode *)0)); 228 } 229 else if(EQ(a, "-newer")) { 230 if(stat(b, &Statb) < 0) { 231 fprintf(stderr, "find: cannot access < %s >\n", b); 232 exit(1); 233 } 234 Newer = Statb.st_mtime; 235 return mk(newer, (struct anode *)0, (struct anode *)0); 236 } 237 err: fprintf(stderr, "find: bad option < %s >\n", a); 238 exit(1); 239 } 240 struct anode *mk(f, l, r) 241 int (*f)(); 242 struct anode *l, *r; 243 { 244 Node[Nn].F = f; 245 Node[Nn].L = l; 246 Node[Nn].R = r; 247 return(&(Node[Nn++])); 248 } 249 250 char *nxtarg() { /* get next arg from command line */ 251 static strikes = 0; 252 253 if(strikes==3) { 254 fprintf(stderr, "find: incomplete statement\n"); 255 exit(1); 256 } 257 if(Ai>=Argc) { 258 strikes++; 259 Ai = Argc + 1; 260 return(""); 261 } 262 return(Argv[Ai++]); 263 } 264 265 /* execution time functions */ 266 and(p) 267 register struct anode *p; 268 { 269 return(((*p->L->F)(p->L)) && ((*p->R->F)(p->R))?1:0); 270 } 271 or(p) 272 register struct anode *p; 273 { 274 return(((*p->L->F)(p->L)) || ((*p->R->F)(p->R))?1:0); 275 } 276 not(p) 277 register struct anode *p; 278 { 279 return( !((*p->L->F)(p->L))); 280 } 281 glob(p) 282 register struct { int f; char *pat; } *p; 283 { 284 return(gmatch(Fname, p->pat)); 285 } 286 print() 287 { 288 puts(Pathname); 289 return(1); 290 } 291 mtime(p) 292 register struct { int f, t, s; } *p; 293 { 294 return(scomp((int)((Now - Statb.st_mtime) / A_DAY), p->t, p->s)); 295 } 296 atime(p) 297 register struct { int f, t, s; } *p; 298 { 299 return(scomp((int)((Now - Statb.st_atime) / A_DAY), p->t, p->s)); 300 } 301 user(p) 302 register struct { int f, u, s; } *p; 303 { 304 return(scomp(Statb.st_uid, p->u, p->s)); 305 } 306 ino(p) 307 register struct { int f, u, s; } *p; 308 { 309 return(scomp((int)Statb.st_ino, p->u, p->s)); 310 } 311 group(p) 312 register struct { int f, u; } *p; 313 { 314 return(p->u == Statb.st_gid); 315 } 316 links(p) 317 register struct { int f, link, s; } *p; 318 { 319 return(scomp(Statb.st_nlink, p->link, p->s)); 320 } 321 size(p) 322 register struct { int f, sz, s; } *p; 323 { 324 return(scomp((int)((Statb.st_size+511)>>9), p->sz, p->s)); 325 } 326 perm(p) 327 register struct { int f, per, s; } *p; 328 { 329 register i; 330 i = (p->s=='-') ? p->per : 07777; /* '-' means only arg bits */ 331 return((Statb.st_mode & i & 07777) == p->per); 332 } 333 type(p) 334 register struct { int f, per, s; } *p; 335 { 336 return((Statb.st_mode&S_IFMT)==p->per); 337 } 338 exeq(p) 339 register struct { int f, com; } *p; 340 { 341 fflush(stdout); /* to flush possible `-print' */ 342 return(doex(p->com)); 343 } 344 ok(p) 345 struct { int f, com; } *p; 346 { 347 char c; int yes; 348 yes = 0; 349 fflush(stdout); /* to flush possible `-print' */ 350 fprintf(stderr, "< %s ... %s > ? ", Argv[p->com], Pathname); 351 fflush(stderr); 352 if((c=getchar())=='y') yes = 1; 353 while(c!='\n') c = getchar(); 354 if(yes) return(doex(p->com)); 355 return(0); 356 } 357 358 #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];} 359 union { long l; short s[2]; char c[4]; } U; 360 long mklong(v) 361 short v[]; 362 { 363 U.l = 1; 364 if(U.c[0] /* VAX */) 365 U.s[0] = v[1], U.s[1] = v[0]; 366 else 367 U.s[0] = v[0], U.s[1] = v[1]; 368 return U.l; 369 } 370 cpio() 371 { 372 #define MAGIC 070707 373 struct header { 374 short h_magic, 375 h_dev, 376 h_ino, 377 h_mode, 378 h_uid, 379 h_gid, 380 h_nlink, 381 h_rdev; 382 short h_mtime[2]; 383 short h_namesize; 384 short h_filesize[2]; 385 char h_name[256]; 386 } hdr; 387 register ifile, ct; 388 static long fsz; 389 register i; 390 391 hdr.h_magic = MAGIC; 392 strcpy(hdr.h_name, !strncmp(Pathname, "./", 2)? Pathname+2: Pathname); 393 hdr.h_namesize = strlen(hdr.h_name) + 1; 394 hdr.h_uid = Statb.st_uid; 395 hdr.h_gid = Statb.st_gid; 396 hdr.h_dev = Statb.st_dev; 397 hdr.h_ino = Statb.st_ino; 398 hdr.h_mode = Statb.st_mode; 399 MKSHORT(hdr.h_mtime, Statb.st_mtime); 400 hdr.h_nlink = Statb.st_nlink; 401 fsz = hdr.h_mode & S_IFREG? Statb.st_size: 0L; 402 MKSHORT(hdr.h_filesize, fsz); 403 hdr.h_rdev = Statb.st_rdev; 404 if(EQ(hdr.h_name, "TRAILER!!!")) { 405 bwrite((short *)&hdr, (sizeof hdr-256)+hdr.h_namesize); 406 for(i = 0; i < 10; ++i) 407 bwrite(Buf, 512); 408 return; 409 } 410 if(!mklong(hdr.h_filesize)) 411 return; 412 if((ifile = open(Fname, 0)) < 0) { 413 cerror: 414 fprintf(stderr, "find: cannot copy < %s >\n", hdr.h_name); 415 return; 416 } 417 bwrite((short *)&hdr, (sizeof hdr-256)+hdr.h_namesize); 418 for(fsz = mklong(hdr.h_filesize); fsz > 0; fsz -= 512) { 419 ct = fsz>512? 512: fsz; 420 if(read(ifile, (char *)Buf, ct) < 0) 421 goto cerror; 422 bwrite(Buf, ct); 423 } 424 close(ifile); 425 return; 426 } 427 newer() 428 { 429 return Statb.st_mtime > Newer; 430 } 431 432 /* support functions */ 433 scomp(a, b, s) /* funny signed compare */ 434 register a, b; 435 register char s; 436 { 437 if(s == '+') 438 return(a > b); 439 if(s == '-') 440 return(a < (b * -1)); 441 return(a == b); 442 } 443 444 doex(com) 445 { 446 register np; 447 register char *na; 448 static char *nargv[50]; 449 static ccode; 450 451 ccode = np = 0; 452 while (na=Argv[com++]) { 453 if(strcmp(na, ";")==0) break; 454 if(strcmp(na, "{}")==0) nargv[np++] = Pathname; 455 else nargv[np++] = na; 456 } 457 nargv[np] = 0; 458 if (np==0) return(9); 459 if(fork()) /*parent*/ wait(&ccode); 460 else { /*child*/ 461 chdir(Home); 462 execvp(nargv[0], nargv, np); 463 exit(1); 464 } 465 return(ccode ? 0:1); 466 } 467 468 getunum(f, s) char *f, *s; { /* find user/group name and return number */ 469 register i; 470 register char *sp; 471 register c; 472 char str[20]; 473 FILE *pin; 474 475 i = -1; 476 pin = fopen(f, "r"); 477 c = '\n'; /* prime with a CR */ 478 do { 479 if(c=='\n') { 480 sp = str; 481 while((c = *sp++ = getc(pin)) != ':') 482 if(c == EOF) goto RET; 483 *--sp = '\0'; 484 if(EQ(str, s)) { 485 while((c=getc(pin)) != ':') 486 if(c == EOF) goto RET; 487 sp = str; 488 while((*sp = getc(pin)) != ':') sp++; 489 *sp = '\0'; 490 i = atoi(str); 491 goto RET; 492 } 493 } 494 } while((c = getc(pin)) != EOF); 495 RET: 496 fclose(pin); 497 return(i); 498 } 499 500 descend(name, fname, exlist) 501 struct anode *exlist; 502 char *name, *fname; 503 { 504 int dir = 0, /* open directory */ 505 offset, 506 dsize, 507 entries, 508 dirsize; 509 struct direct dentry[BUFSIZ / sizeof (struct direct)]; 510 register struct direct *dp; 511 register char *c1, *c2; 512 int i; 513 int rv = 0; 514 char *endofname; 515 516 if(stat(fname, &Statb)<0) { 517 fprintf(stderr, "find: bad status < %s >\n", name); 518 return(0); 519 } 520 (*exlist->F)(exlist); 521 if((Statb.st_mode&S_IFMT)!=S_IFDIR) 522 return(1); 523 524 for(c1 = name; *c1; ++c1); 525 if(*(c1-1) == '/') 526 --c1; 527 endofname = c1; 528 dirsize = Statb.st_size; 529 530 if(chdir(fname) == -1) 531 return(0); 532 for(offset=0 ; offset < dirsize ; offset += BUFSIZ) { /* each block */ 533 dsize = BUFSIZ<(dirsize-offset)? BUFSIZ: (dirsize-offset); 534 if(!dir) { 535 if((dir=open(".", 0))<0) { 536 fprintf(stderr, "find: cannot open < %s >\n", 537 name); 538 rv = 0; 539 goto ret; 540 } 541 if(offset) lseek(dir, (long)offset, 0); 542 if(read(dir, (char *)dentry, dsize)<0) { 543 fprintf(stderr, "find: cannot read < %s >\n", 544 name); 545 rv = 0; 546 goto ret; 547 } 548 if(dir > 10) { 549 close(dir); 550 dir = 0; 551 } 552 } else 553 if(read(dir, (char *)dentry, dsize)<0) { 554 fprintf(stderr, "find: cannot read < %s >\n", 555 name); 556 rv = 0; 557 goto ret; 558 } 559 for(dp=dentry, entries=dsize>>4; entries; --entries, ++dp) { /* each directory entry */ 560 if(dp->d_ino==0 561 || (dp->d_name[0]=='.' && dp->d_name[1]=='\0') 562 || (dp->d_name[0]=='.' && dp->d_name[1]=='.' && dp->d_name[2]=='\0')) 563 continue; 564 c1 = endofname; 565 *c1++ = '/'; 566 c2 = dp->d_name; 567 for(i=0; i<14; ++i) 568 if(*c2) 569 *c1++ = *c2++; 570 else 571 break; 572 *c1 = '\0'; 573 if(c1 == endofname) { /* ?? */ 574 rv = 0; 575 goto ret; 576 } 577 Fname = endofname+1; 578 if(!descend(name, Fname, exlist)) { 579 *endofname = '\0'; 580 chdir(Home); 581 if(chdir(Pathname) == -1) { 582 fprintf(stderr, "find: bad directory tree\n"); 583 exit(1); 584 } 585 } 586 } 587 } 588 rv = 1; 589 ret: 590 if(dir) 591 close(dir); 592 if(chdir("..") == -1) { 593 *endofname = '\0'; 594 fprintf(stderr, "find: bad directory <%s>\n", name); 595 rv = 1; 596 } 597 return(rv); 598 } 599 600 gmatch(s, p) /* string match as in glob */ 601 register char *s, *p; 602 { 603 if (*s=='.' && *p!='.') return(0); 604 return amatch(s, p); 605 } 606 607 amatch(s, p) 608 register char *s, *p; 609 { 610 register cc; 611 int scc, k; 612 int c, lc; 613 614 scc = *s; 615 lc = 077777; 616 switch (c = *p) { 617 618 case '[': 619 k = 0; 620 while (cc = *++p) { 621 switch (cc) { 622 623 case ']': 624 if (k) 625 return(amatch(++s, ++p)); 626 else 627 return(0); 628 629 case '-': 630 k |= lc <= scc & scc <= (cc=p[1]); 631 } 632 if (scc==(lc=cc)) k++; 633 } 634 return(0); 635 636 case '?': 637 caseq: 638 if(scc) return(amatch(++s, ++p)); 639 return(0); 640 case '*': 641 return(umatch(s, ++p)); 642 case 0: 643 return(!scc); 644 } 645 if (c==scc) goto caseq; 646 return(0); 647 } 648 649 umatch(s, p) 650 register char *s, *p; 651 { 652 if(*p==0) return(1); 653 while(*s) 654 if (amatch(s++, p)) return(1); 655 return(0); 656 } 657 658 bwrite(rp, c) 659 register short *rp; 660 register c; 661 { 662 register short *wp = Wp; 663 664 c = (c+1) >> 1; 665 while(c--) { 666 if(!Wct) { 667 again: 668 if(write(Cpio, (char *)Dbuf, Bufsize)<0) { 669 Cpio = chgreel(1, Cpio); 670 goto again; 671 } 672 Wct = Bufsize >> 1; 673 wp = Dbuf; 674 ++Blocks; 675 } 676 *wp++ = *rp++; 677 --Wct; 678 } 679 Wp = wp; 680 } 681 chgreel(x, fl) 682 { 683 register f; 684 char str[22]; 685 FILE *devtty; 686 struct stat statb; 687 extern errno; 688 689 fprintf(stderr, "find: errno: %d, ", errno); 690 fprintf(stderr, "find: can't %s\n", x? "write output": "read input"); 691 fstat(fl, &statb); 692 if((statb.st_mode&S_IFMT) != S_IFCHR) 693 exit(1); 694 again: 695 fprintf(stderr, "If you want to go on, type device/file name %s\n", 696 "when ready"); 697 devtty = fopen("/dev/tty", "r"); 698 fgets(str, 20, devtty); 699 str[strlen(str) - 1] = '\0'; 700 if(!*str) 701 exit(1); 702 close(fl); 703 if((f = open(str, x? 1: 0)) < 0) { 704 fprintf(stderr, "That didn't work"); 705 fclose(devtty); 706 goto again; 707 } 708 return f; 709 } 710