static char *sccsid
= "@(#)find.c 4.22 (Berkeley) %G%";
#define A_DAY 86400L /* a day full of seconds */
#define EQ(x, y) (strcmp(x, y)==0)
char Pathname
[MAXPATHLEN
+1];
int Nn
; /* number of nodes */
int Xdev
= 1; /* true if SHOULD cross devices (file systems) */
int follow
; /* true if SHOULD descend symlinked directories */
struct stat Devstat
; /* stats of each argument path's file system */
char Home
[MAXPATHLEN
+ 1];
* SEE ALSO: code.c, updatedb, bigram.c
* Usenix ;login:, Vol 8, No 1, 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 / +0 -name "*<name>*" -print
* 8/82 faster yet + incorporation of bigram coding -- jaw
* 1/83 incorporate glob-style matching -- jaw
register char *cp
, *sp
= 0;
"Usage: find name, or find path-list predicate-list\n");
fgets(Home
, sizeof Home
, pwd
);
Home
[strlen(Home
) - 1] = '\0';
if (getwd(Home
) == NULL
) {
fprintf(stderr
, "find: Can't get current working directory\n");
Argc
= argc
; Argv
= argv
;
usage
: fprintf(stderr
, "Usage: find path-list predicate-list\n");
for(Ai
= paths
= 1; Ai
< (argc
-1); ++Ai
, ++paths
)
if(*Argv
[Ai
] == '-' || EQ(Argv
[Ai
], "(") || EQ(Argv
[Ai
], "!"))
if(paths
== 1) /* no path-list */
if(!(exlist
= exp())) { /* parse and compile the arguments */
fprintf(stderr
, "find: parsing error\n");
fprintf(stderr
, "find: missing conjunction\n");
for(Pi
= 1; Pi
< paths
; ++Pi
) {
strcpy(Pathname
, Argv
[Pi
]);
if(cp
= rindex(Pathname
, '/')) {
if(chdir(*Pathname
? Pathname
: "/") == -1) {
fprintf(stderr
, "find: bad starting directory\n");
Fname
= sp
? sp
: Pathname
;
stat(Pathname
, &Devstat
);
descend(Pathname
, Fname
, exlist
); /* to find files that match */
strcpy(Pathname
, "TRAILER!!!");
printf("%D blocks\n", Blocks
*10);
/* compile time functions: priority is exp()<e1()<e2()<e3() */
struct anode
*exp() { /* parse ALTERNATION (-o) */
register struct anode
* p1
;
p1
= e1() /* get left operand */ ;
return(mk(or, p1
, exp()));
else if(Ai
<= Argc
) --Ai
;
struct anode
*e1() { /* parse CONCATENATION (formerly -a) */
register struct anode
* p1
;
return(mk(and, p1
, e1()));
} else if(EQ(a
, "(") || EQ(a
, "!") || (*a
=='-' && !EQ(a
, "-o"))) {
} else if(Ai
<= Argc
) --Ai
;
struct anode
*e2() { /* parse NOT (!) */
fprintf(stderr
, "find: operand follows operand\n");
return(mk(not, e3(), (struct anode
*)0));
else if(Ai
<= Argc
) --Ai
;
struct anode
*e3() { /* parse parens and predicates */
int exeq(), ok(), glob(), mtime(), atime(), user(),
group(), size(), perm(), links(), print(),
type(), ino(), cpio(), newer(),
nouser(), nogroup(), ls(), dummy();
if(!EQ(a
, ")")) goto err
;
else if(EQ(a
, "-print")) {
return(mk(print
, (struct anode
*)0, (struct anode
*)0));
else if (EQ(a
, "-nouser")) {
return (mk(nouser
, (struct anode
*)0, (struct anode
*)0));
else if (EQ(a
, "-nogroup")) {
return (mk(nogroup
, (struct anode
*)0, (struct anode
*)0));
return (mk(ls
, (struct anode
*)0, (struct anode
*)0));
else if (EQ(a
, "-xdev")) {
return (mk(dummy
, (struct anode
*)0, (struct anode
*)0));
else if (EQ(a
, "-follow")) {
return mk(dummy
, (struct anode
*)0, (struct anode
*)0);
return(mk(glob
, (struct anode
*)b
, (struct anode
*)0));
return(mk(mtime
, (struct anode
*)atoi(b
), (struct anode
*)s
));
return(mk(atime
, (struct anode
*)atoi(b
), (struct anode
*)s
));
else if(EQ(a
, "-user")) {
if((i
=getuid(b
)) == -1) {
return mk(user
, (struct anode
*)atoi(b
), (struct anode
*)s
);
fprintf(stderr
, "find: cannot find -user name\n");
return(mk(user
, (struct anode
*)i
, (struct anode
*)s
));
return(mk(ino
, (struct anode
*)atoi(b
), (struct anode
*)s
));
else if(EQ(a
, "-group")) {
if((i
=getgid(b
)) == -1) {
return mk(group
, (struct anode
*)atoi(b
), (struct anode
*)s
);
fprintf(stderr
, "find: cannot find -group name\n");
return(mk(group
, (struct anode
*)i
, (struct anode
*)s
));
} else if(EQ(a
, "-size"))
return(mk(size
, (struct anode
*)atoi(b
), (struct anode
*)s
));
return(mk(links
, (struct anode
*)atoi(b
), (struct anode
*)s
));
else if(EQ(a
, "-perm")) {
return(mk(perm
, (struct anode
*)i
, (struct anode
*)s
));
else if(EQ(a
, "-type")) {
return(mk(type
, (struct anode
*)i
, (struct anode
*)0));
else if (EQ(a
, "-exec")) {
while(!EQ(nxtarg(), ";"));
return(mk(exeq
, (struct anode
*)i
, (struct anode
*)0));
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
);
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
);
return mk(newer
, (struct anode
*)0, (struct anode
*)0);
err
: fprintf(stderr
, "find: bad option < %s >\n", a
);
struct anode
*mk(f
, l
, r
)
fprintf(stderr
, "find: Too many options\n");
char *nxtarg() { /* get next arg from command line */
fprintf(stderr
, "find: incomplete statement\n");
/* execution time functions */
register struct anode
*p
;
return(((*p
->L
->F
)(p
->L
)) && ((*p
->R
->F
)(p
->R
))?1:0);
register struct anode
*p
;
return(((*p
->L
->F
)(p
->L
)) || ((*p
->R
->F
)(p
->R
))?1:0);
register struct anode
*p
;
return( !((*p
->L
->F
)(p
->L
)));
register struct { int f
; char *pat
; } *p
;
return(gmatch(Fname
, p
->pat
));
register struct { int f
, t
, s
; } *p
;
return(scomp((int)((Now
- Statb
.st_mtime
) / A_DAY
), p
->t
, p
->s
));
register struct { int f
, t
, s
; } *p
;
return(scomp((int)((Now
- Statb
.st_atime
) / A_DAY
), p
->t
, p
->s
));
register struct { int f
, u
, s
; } *p
;
return(scomp(Statb
.st_uid
, p
->u
, p
->s
));
return (getname(Statb
.st_uid
) == NULL
);
register struct { int f
, u
, s
; } *p
;
return(scomp((int)Statb
.st_ino
, p
->u
, p
->s
));
register struct { int f
, u
; } *p
;
return(p
->u
== Statb
.st_gid
);
return (getgroup(Statb
.st_gid
) == NULL
);
register struct { int f
, link
, s
; } *p
;
return(scomp(Statb
.st_nlink
, p
->link
, p
->s
));
register struct { int f
, sz
, s
; } *p
;
return(scomp((int)((Statb
.st_size
+511)>>9), p
->sz
, p
->s
));
register struct { int f
, per
, s
; } *p
;
i
= (p
->s
=='-') ? p
->per
: 07777; /* '-' means only arg bits */
return((Statb
.st_mode
& i
& 07777) == p
->per
);
register struct { int f
, per
, s
; } *p
;
return((Statb
.st_mode
&S_IFMT
)==p
->per
);
register struct { int f
, com
; } *p
;
fflush(stdout
); /* to flush possible `-print' */
struct { int f
, com
; } *p
;
fflush(stdout
); /* to flush possible `-print' */
fprintf(stderr
, "< %s ... %s > ? ", Argv
[p
->com
], Pathname
);
if((c
=getchar())=='y') yes
= 1;
while(c
!='\n') c
= getchar();
if(yes
) return(doex(p
->com
));
#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
;
U
.s
[0] = v
[1], U
.s
[1] = v
[0];
U
.s
[0] = v
[0], U
.s
[1] = v
[1];
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
);
if(!mklong(hdr
.h_filesize
))
if((ifile
= open(Fname
, 0)) < 0) {
fprintf(stderr
, "find: cannot copy < %s >\n", hdr
.h_name
);
bwrite((short *)&hdr
, (sizeof hdr
-256)+hdr
.h_namesize
);
for(fsz
= mklong(hdr
.h_filesize
); fsz
> 0; fsz
-= 512) {
if(read(ifile
, (char *)Buf
, ct
) < 0)
return Statb
.st_mtime
> Newer
;
scomp(a
, b
, s
) /* funny signed compare */
register int w
, pid
, omask
;
if(np
>= sizeof nargv
/ sizeof *nargv
- 1) break;
if(strcmp(na
, ";")==0) break;
if(strcmp(na
, "{}")==0) nargv
[np
++] = Pathname
;
perror("find: Can't fork");
execvp(nargv
[0], nargv
, np
);
write(2, "find: Can't execute ", 20);
* Kill ourselves; our exit status will be a suicide
* note indicating we couldn't do the "exec".
omask
= sigblock(sigmask(SIGINT
)|sigmask(SIGQUIT
));
while ((w
= wait(&ccode
)) != pid
&& w
!= -1)
(void) sigsetmask(omask
);
if ((ccode
& 0177) == SIGUSR1
)
return (ccode
!= 0 ? 0 : 1);
getunum(f
, s
) char *f
, *s
; { /* find user/group name and return number */
c
= '\n'; /* prime with a CR */
while((c
= *sp
++ = getc(pin
)) != ':')
while((c
=getc(pin
)) != ':')
while((*sp
= getc(pin
)) != ':') sp
++;
} while((c
= getc(pin
)) != EOF
);
descend(name
, fname
, exlist
)
register struct direct
*dp
;
if ((follow
?stat(fname
, &Statb
):lstat(fname
, &Statb
))<0) {
fprintf(stderr
, "find: bad status < %s >\n", name
);
if((Statb
.st_mode
&S_IFMT
)!=S_IFDIR
||
!Xdev
&& Devstat
.st_dev
!= Statb
.st_dev
)
if (Statb
.st_nlink
== 2 && exlist
->F
== and &&
exlist
->L
->F
== type
&& ((int) (exlist
->L
->L
)) == S_IFDIR
)
for (c1
= name
; *c1
; ++c1
);
if ((dir
= opendir(".")) == NULL
) {
fprintf(stderr
, "find: cannot open < %s >\n", name
);
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'))
if(!descend(name
, Fname
, exlist
)) {
if(chdir(Pathname
) == -1) {
fprintf(stderr
, "find: bad directory tree\n");
fprintf(stderr
, "find: bad directory <%s>\n", name
);
gmatch(s
, p
) /* string match as in glob */
if (*s
=='.' && *p
!='.') return(0);
return(amatch(++s
, ++p
));
k
|= lc
<= scc
&& scc
<= cc
;
if(scc
) return(amatch(++s
, ++p
));
if (amatch(s
++, p
)) return(1);
if(write(Cpio
, (char *)Dbuf
, Bufsize
)<0) {
fprintf(stderr
, "find: errno: %d, ", errno
);
fprintf(stderr
, "find: can't %s\n", x
? "write output": "read input");
if((statb
.st_mode
&S_IFMT
) != S_IFCHR
)
fprintf(stderr
, "If you want to go on, type device/file name %s\n",
devtty
= fopen(_PATH_TTY
, "r");
str
[strlen(str
) - 1] = '\0';
if((f
= open(str
, x
? 1: 0)) < 0) {
fprintf(stderr
, "That didn't work");
* '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%.
* 0-28 likeliest differential counts + offset to make nonnegative
* 30 switch 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 (ie, literal)
* 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'.
char *q
, *index(), *patprep();
int count
= 0, found
= NO
, globflag
;
char bigram1
[NBG
], bigram2
[NBG
];
if ( (fp
= fopen ( _PATH_FCODES
, "r" )) == NULL
) {
for ( c
= 0, p
= bigram1
, s
= bigram2
; c
< NBG
; c
++ )
p
[c
] = getc ( fp
), s
[c
] = getc ( fp
);
globflag
= index ( p
, '*' ) || index ( p
, '?' ) || index ( p
, '[' );
for ( c
= getc ( fp
); ; ) {
count
+= ( (c
== SWITCH
) ? getw ( fp
) : c
) - OFFSET
;
for ( p
= path
+ count
; (c
= getc ( fp
)) > SWITCH
; ) /* overlay old path */
else { /* bigrams are parity-marked */
*p
++ = bigram1
[c
], *p
++ = bigram2
[c
];
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 ( *p
== NULL
) { /* success on fast match */
if ( globflag
== NO
|| amatch ( path
, pathpart
) )
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];
register char *p
, *endmark
;
register char *subp
= globfree
;
p
= name
+ strlen ( name
) - 1;
skip trailing metacharacters (and [] ranges)
if ( index ( "*?", *p
) == 0 )
for ( p
--; p
>= name
; p
-- )
if pattern has only metacharacters,
check every path (force '/' search)
if ( (p
== name
) && index ( "?*[]", *p
) != 0 )
for ( endmark
= p
; p
>= name
; p
-- )
if ( index ( "]*?", *p
) != 0 )
for ( ++p
; (p
<= endmark
) && subp
< (globfree
+ sizeof ( globfree
)); )
/* rest should be done with nameserver or database */
#define NMAX (sizeof (utmp.ut_name))
#define SCPYN(a, b) strncpy(a, b, NMAX)
char outrangename
[NMAX
+1];
char groups
[NGID
][NMAX
+1];
char outrangegroup
[NMAX
+1];
* This function assumes that the password file is hashed
* (or some such) to allow fast access based on a name key.
* If this isn't true, duplicate the code for getgroup().
register struct passwd
*pw
;
struct passwd
*getpwent();
#if (((NUID) & ((NUID) - 1)) != 0)
if (uid
>= 0 && nc
[cp
].uid
== uid
&& nc
[cp
].name
[0])
SCPYN(nc
[cp
].name
, pw
->pw_name
);
register struct group
*gr
;
struct group
*getgrent();
if (gid
>= 0 && gid
< NGID
&& groups
[gid
][0])
return (&groups
[gid
][0]);
if (gid
>= 0 && gid
== outrangegid
)
while (gr
= getgrent()) {
outrangegid
= gr
->gr_gid
;
SCPYN(outrangegroup
, gr
->gr_name
);
while (gr
= getgrent()) {
if (gr
->gr_gid
< 0 || gr
->gr_gid
>= NGID
) {
outrangegid
= gr
->gr_gid
;
SCPYN(outrangegroup
, gr
->gr_name
);
if (groups
[gr
->gr_gid
][0])
SCPYN(groups
[gr
->gr_gid
], gr
->gr_name
);
return (&groups
[gid
][0]);
register struct passwd
*pw
;
struct passwd
*getpwnam();
register struct group
*gr
;
struct group
*getgrnam();
gr
= getgrnam(groupname
);
#define permoffset(who) ((who) * 3)
#define permission(who, type) ((type) >> permoffset(who))
#define kbytes(bytes) (((bytes) + 1023) / 1024)
register struct stat
*stp
;
char pmode
[32], uname
[32], gname
[32], fsize
[32], ftime
[32];
char *getname(), *getgroup(), *ctime();
static long special
[] = { S_ISUID
, 's', S_ISGID
, 's', S_ISVTX
, 't' };
static time_t sixmonthsago
= -1;
char flink
[MAXPATHLEN
+ 1];
if (file
== NULL
|| stp
== NULL
)
sixmonthsago
= now
- 6L*30L*24L*60L*60L;
switch (stp
->st_mode
& S_IFMT
) {
case S_IFDIR
: /* directory */
case S_IFCHR
: /* character special */
case S_IFBLK
: /* block special */
case S_IFLNK
: /* symbolic link */
case S_IFSOCK
: /* socket */
case S_IFREG
: /* regular */
for (who
= 0; who
< 3; who
++) {
if (stp
->st_mode
& permission(who
, S_IREAD
))
pmode
[permoffset(who
) + 1] = 'r';
pmode
[permoffset(who
) + 1] = '-';
if (stp
->st_mode
& permission(who
, S_IWRITE
))
pmode
[permoffset(who
) + 2] = 'w';
pmode
[permoffset(who
) + 2] = '-';
if (stp
->st_mode
& special
[who
* 2])
pmode
[permoffset(who
) + 3] = special
[who
* 2 + 1];
else if (stp
->st_mode
& permission(who
, S_IEXEC
))
pmode
[permoffset(who
) + 3] = 'x';
pmode
[permoffset(who
) + 3] = '-';
pmode
[permoffset(who
) + 1] = '\0';
cp
= getname(stp
->st_uid
);
sprintf(uname
, "%-9.9s", cp
);
sprintf(uname
, "%-9d", stp
->st_uid
);
cp
= getgroup(stp
->st_gid
);
sprintf(gname
, "%-9.9s", cp
);
sprintf(gname
, "%-9d", stp
->st_gid
);
if (pmode
[0] == 'b' || pmode
[0] == 'c')
sprintf(fsize
, "%3d,%4d",
major(stp
->st_rdev
), minor(stp
->st_rdev
));
sprintf(fsize
, "%8ld", stp
->st_size
);
* Need to get the tail of the file name, since we have
* already chdir()ed into the directory of the file
who
= readlink(cp
, flink
, sizeof flink
- 1);
cp
= ctime(&stp
->st_mtime
);
if (stp
->st_mtime
< sixmonthsago
|| stp
->st_mtime
> now
)
sprintf(ftime
, "%-7.7s %-4.4s", cp
+ 4, cp
+ 20);
sprintf(ftime
, "%-12.12s", cp
+ 4);
printf("%5lu %4ld %s %2d %s%s%s %s %s%s%s\n",
stp
->st_ino
, /* inode # */
(long) kbytes(dbtob(stp
->st_blocks
)), /* kbytes */
(long) kbytes(stp
->st_size
), /* kbytes */
stp
->st_nlink
, /* # of links */
(pmode
[0] == 'l') ? " -> " : "",
(pmode
[0] == 'l') ? flink
: "" /* symlink */