find.c

操作系统源代码

/* find - look for files satisfying a predicate       Author: E. Baalbergen */

/* Original author: Erik Baalbergen; POSIX compliant version: Bert Laverman */

#include <sys/types.h>
#include <sys/stat.h>
#include <sys/wait.h>
#include <fcntl.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>
#include <pwd.h>
#include <grp.h>
#include <dirent.h>
#include <limits.h>
#include <stdio.h>

/*######################## DEFINITIONS ##############################*/

#ifdef S_IFLNK
#define LSTAT lstat
#else
#define LSTAT stat
#endif

#define SHELL "/bin/sh"
#define MAXARG          256	/* maximum length for an argv for -exec  */
#define BSIZE           512	/* POSIX wants 512 byte blocks           */
#define SECS_PER_DAY    (24L*60L*60L)	/* check your planet             */

#define OP_NAME          1	/* match name                            */
#define OP_PERM          2	/* check file permission bits            */
#define OP_TYPE          3	/* check file type bits                  */
#define OP_LINKS         4	/* check link count                      */
#define OP_USER          5	/* check owner                           */
#define OP_GROUP         6	/* check group ownership                 */
#define OP_SIZE          7	/* check size, blocks or bytes           */
#define OP_SIZEC         8	/* this is a fake for -size with 'c'     */
#define OP_INUM          9	/* compare inode number                  */
#define OP_ATIME        10	/* check last access time                */
#define OP_CTIME        11	/* check creation time                   */
#define OP_MTIME        12	/* check last modification time          */
#define OP_EXEC         13	/* execute command                       */
#define OP_OK           14	/* execute with confirmation             */
#define OP_PRINT        15	/* print name                            */
#define OP_PRINT0       16	/* print name null terminated            */
#define OP_NEWER        17	/* compare modification times            */
#define OP_AND          18	/* logical and (short circuit)           */
#define OP_OR           19	/* logical or (short circuit)            */
#define OP_XDEV         20	/* do not cross file-system boundaries   */
#define OP_DEPTH        21	/* descend directory before testing      */
#define OP_PRUNE        22	/* don't descend into current directory  */
#define OP_NOUSER       23	/* check validity of user id             */
#define OP_NOGROUP      24	/* check validity of group id            */
#define LPAR            25	/* left parenthesis                      */
#define RPAR            26	/* right parenthesis                     */
#define NOT             27	/* logical not                           */

/* Some return values: */
#define EOI             -1	/* end of expression                     */
#define NONE             0	/* not a valid predicate                 */

/* For -perm with symbolic modes: */
#define ISWHO(c)        ((c == 'u') || (c == 'g') || (c == 'o') || (c == 'a'))
#define ISOPER(c)       ((c == '-') || (c == '=') || (c == '+'))
#define ISMODE(c)       ((c == 'r') || (c == 'w') || (c == 'x') || \
			 (c == 's') || (c == 't'))
#define MUSER           1
#define MGROUP          2
#define MOTHERS         4


struct exec {
  int e_cnt;
  char *e_vec[MAXARG];
};

struct node {
  int n_type;			/* any OP_ or NOT */
  union {
	char *n_str;
	struct {
		long n_val;
		int n_sign;
	} n_int;
	struct exec *n_exec;
	struct {
		struct node *n_left, *n_right;
	} n_opnd;
  } n_info;
};

struct oper {
  char *op_str;
  int op_val;
} ops[] = {

  {
	"name", OP_NAME
  },
  {
	"perm", OP_PERM
  },
  {
	"type", OP_TYPE
  },
  {
	"links", OP_LINKS
  },
  {
	"user", OP_USER
  },
  {
	"group", OP_GROUP
  },
  {
	"size", OP_SIZE
  },
  {
	"inum", OP_INUM
  },
  {
	"atime", OP_ATIME
  },
  {
	"ctime", OP_CTIME
  },
  {
	"mtime", OP_MTIME
  },
  {
	"exec", OP_EXEC
  },
  {
	"ok", OP_OK
  },
  {
	"print", OP_PRINT
  },
  {
	"print0", OP_PRINT0
  },
  {
	"newer", OP_NEWER
  },
  {
	"a", OP_AND
  },
  {
	"o", OP_OR
  },
  {
	"xdev", OP_XDEV
  },
  {
	"depth", OP_DEPTH
  },
  {
	"prune", OP_PRUNE
  },
  {
	"nouser", OP_NOUSER
  },
  {
	"nogroup", OP_NOGROUP
  },
  {
	0, 0
  }
};


char **ipp;			/* pointer to next argument during parsing       */
char *prog;			/* program name (== argv [0])                    */
char *epath;			/* value of PATH environment string              */
long current_time;		/* for computing age                             */
int tty;			/* fd for /dev/tty when using -ok                */
int xdev_flag = 0;		/* cross device boundaries?                      */
int devnr;			/* device nr of first inode                      */
int depth_flag = 0;		/* descend before check?                         */
int prune_here;			/* This is Baaaad! Don't ever do this again!     */
int um;				/* current umask()                               */
int needprint = 1;		/* implicit -print needed?                       */


/* The prototypes: */
_PROTOTYPE(int main, (int argc, char **argv));
_PROTOTYPE(char *Malloc, (int n));
_PROTOTYPE(char *Salloc, (char *s));
_PROTOTYPE(void find, (char *path, struct node * pred, char *last));
_PROTOTYPE(int check, (char *path, struct stat * st, struct node * n, char *last));
_PROTOTYPE(int ichk, (long val, struct node * n));
_PROTOTYPE(int lex, (char *str));
_PROTOTYPE(struct node * newnode, (int t));
_PROTOTYPE(int isnumber, (char *str, int base, int sign));
_PROTOTYPE(void number, (char *str, int base, long *pl, int *ps));
_PROTOTYPE(void fmode, (char *str, long *pl, int *ps));
_PROTOTYPE(struct node * expr, (int t));
_PROTOTYPE(struct node * primary, (int t));
_PROTOTYPE(struct node * secondary, (int t));
_PROTOTYPE(void checkarg, (char *arg));
_PROTOTYPE(struct node * simple, (int t));
_PROTOTYPE(void nonfatal, (char *s1, char *s2));
_PROTOTYPE(void fatal, (char *s1, char *s2));
_PROTOTYPE(int smatch, (char *s, char *t));
_PROTOTYPE(char *find_bin, (char *s));
_PROTOTYPE(int execute, (int op, struct exec * e, char *path));
_PROTOTYPE(void domode, (int op, int *mode, int bits));


/* Malloc: a certified malloc */
char *Malloc(n)
int n;
{
  char *m;

  if ((m = (char *) malloc(n)) == (char *) NULL) fatal("out of memory", "");
  return m;
}

/* Salloc: allocate space for a string */
char *Salloc(s)
char *s;
{
  return strcpy(Malloc(strlen(s) + 1), s);
}


/* Main: the main body */
int main(argc, argv)
int argc;
char *argv[];
{
  char **pathlist, *path, *last;
  int pathcnt = 0, i;
  struct node *pred;

  prog = *argv++;		/* set program name (for diagnostics)    */
  if ((epath = getenv("PATH")) == (char *) NULL)
	fatal("Can't get path from environment", "");
  (void) umask(um = umask(0));	/* non-destructive get-umask :-)         */
  time(&current_time);		/* get current time                      */

  pathlist= argv;
  while (--argc > 0 && lex(*argv) == NONE) {	/* find paths            */
	pathcnt++;
	argv++;
  }
  if (pathcnt == 0)		/* there must be at least one path       */
	fatal("Usage: path-list [predicate-list]", "");

  ipp = argv;			/* prepare for parsing                   */
  if (argc != 0) {		/* If there is anything to parse,        */
	pred = expr(lex(*ipp));	/* then do so                            */
	if (lex(*++ipp) != EOI)	/* Make sure there's nothing left        */
		fatal("syntax error: garbage at end of predicate", "");
  } else			/* No predicate list                     */
	pred = (struct node *) NULL;

  for (i = 0; i < pathcnt; i++) {
	if (xdev_flag) xdev_flag = 2;
	path = pathlist[i];
	if ((last = strrchr(path, '/')) == NULL) last = path; else last++;
	find(path, pred, last);
  }
  return 0;
}

void find(path, pred, last)
char *path, *last;
struct node *pred;
{
  char spath[PATH_MAX];
  register char *send = spath, *p;
  struct stat st;
  DIR *dp;
  struct dirent *de;

  if (path[1] == '\0' && *path == '/') {
	*send++ = '/';
	*send = '\0';
  } else
	while (*send++ = *path++) {
	}

  if (LSTAT(spath, &st) == -1)
	nonfatal("can't get status of ", spath);
  else {
	switch (xdev_flag) {
	  case 0:
		break;
	  case 1:
		if (st.st_dev != devnr) return;
		break;
	  case 2:		/* set current device number */
		xdev_flag = 1;
		devnr = st.st_dev;
		break;
	}

	prune_here = 0;
	if (!depth_flag && check(spath, &st, pred, last) && needprint)
		printf("%s\n", spath);
	if (!prune_here && (st.st_mode & S_IFMT) == S_IFDIR) {
		if ((dp = opendir(spath)) == NULL) {
			nonfatal("can't read directory ", spath);
			return;
		}
		send[-1] = '/';
		while ((de = readdir(dp)) != NULL) {
			p = de->d_name;
			if ((de->d_name[0] != '.') || ((de->d_name[1])
					  && ((de->d_name[1] != '.')
					      || (de->d_name[2])))) {
				strcpy(send, de->d_name);
				find(spath, pred, send);
			}
		}
		closedir(dp);
	}
	if (depth_flag) {
		send[-1] = '\0';
		if (check(spath, &st, pred, last) && needprint)
			printf("%s\n", spath);
	}
  }
}

int check(path, st, n, last)
char *path, *last;
register struct stat *st;
register struct node *n;
{
  if (n == (struct node *) NULL) return 1;
  switch (n->n_type) {
    case OP_AND:
	return check(path, st, n->n_info.n_opnd.n_left, last) &&
		check(path, st, n->n_info.n_opnd.n_right, last);
    case OP_OR:
	return check(path, st, n->n_info.n_opnd.n_left, last) ||
		check(path, st, n->n_info.n_opnd.n_right, last);
    case NOT:
	return !check(path, st, n->n_info.n_opnd.n_left, last);
    case OP_NAME:
	return smatch(last, n->n_info.n_str);
    case OP_PERM:
	if (n->n_info.n_int.n_sign < 0)
		return(st->st_mode & (int) n->n_info.n_int.n_val) ==
			(int) n->n_info.n_int.n_val;
	return(st->st_mode & 07777) == (int) n->n_info.n_int.n_val;
    case OP_NEWER:
	return st->st_mtime > n->n_info.n_int.n_val;
    case OP_TYPE:
	return(st->st_mode & S_IFMT) == (mode_t) n->n_info.n_int.n_val;
    case OP_LINKS:
	return ichk((long) (st->st_nlink), n);
    case OP_USER:
	return st->st_uid == n->n_info.n_int.n_val;
    case OP_GROUP:
	return st->st_gid == n->n_info.n_int.n_val;
    case OP_SIZE:
	return ichk((st->st_size == 0) ? 0L :
		    (long) ((st->st_size - 1) / BSIZE + 1), n);
    case OP_SIZEC:
	return ichk((long) st->st_size, n);
    case OP_INUM:
	return ichk((long) (st->st_ino), n);
    case OP_ATIME:
	return ichk(st->st_atime, n);
    case OP_CTIME:
	return ichk(st->st_ctime, n);
    case OP_MTIME:
	return ichk(st->st_mtime, n);
    case OP_EXEC:
    case OP_OK:
	return execute(n->n_type, n->n_info.n_exec, path);
    case OP_PRINT:
	printf("%s\n", path);
	return 1;
    case OP_PRINT0:
	printf("%s", path); putchar(0);
	return 1;
    case OP_XDEV:
    case OP_DEPTH:
	return 1;
    case OP_PRUNE:
	prune_here = 1;
	return 1;
    case OP_NOUSER:
	return(getpwuid(st->st_uid) == (struct passwd *) NULL);
    case OP_NOGROUP:
	return(getgrgid(st->st_gid) == (struct group *) NULL);
  }
  fatal("ILLEGAL NODE", "");
  return 0;			/* Never reached */
}

int ichk(val, n)
long val;
struct node *n;
{
  switch (n->n_info.n_int.n_sign) {
    case 0:
	return val == n->n_info.n_int.n_val;
    case 1:
	return val > n->n_info.n_int.n_val;
    case -1:	return val < n->n_info.n_int.n_val;
}
  fatal("internal: bad n_sign", "");
  return 0;			/* Never reached */
}

int lex(str)
char *str;
{
  if (str == (char *) NULL) return EOI;
  if (*str == '-') {
	register struct oper *op;

	str++;
	for (op = ops; op->op_str; op++)
		if (strcmp(str, op->op_str) == 0) break;
	return op->op_val;
  }
  if (str[1] == 0) {
	switch (*str) {
	  case '(':
		return LPAR;
	  case ')':
		return RPAR;
	  case '!':	return NOT;
	}
  }
  return NONE;
}

struct node *
 newnode(t)
int t;
{
  struct node *n = (struct node *) Malloc(sizeof(struct node));

  n->n_type = t;
  return n;
}

/*########################### PARSER ###################################*/
/* Grammar:
 * expr        : primary | primary OR expr;
 * primary     : secondary | secondary AND primary | secondary primary;
 * secondary   : NOT secondary | LPAR expr RPAR | simple;
 * simple      : -OP args...
 */

/* Isnumber checks correct number syntax. A sign is allowed, but the '+'
 * only if the number is to be in decimal.