+
+#ifdef AMES
+/*
+ * '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%.
+ * The codes are:
+ *
+ * 0-28 likeliest differential counts + offset to make nonnegative
+ * 30 escape 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
+ *
+ * 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'.
+ */
+
+#define FCODES "/usr/lib/find/find.codes"
+#define YES 1
+#define NO 0
+#define OFFSET 14
+#define ESCCODE 30
+
+fastfind ( pathpart )
+ char pathpart[];
+{
+ register char *p, *s;
+ register int c;
+ char *q, *index(), *patprep();
+ int i, count = 0, globflag;
+ FILE *fp, *fopen();
+ char *patend, *cutoff;
+ char path[1024];
+ char bigram1[128], bigram2[128];
+ int found = NO;
+
+ if ( (fp = fopen ( FCODES, "r" )) == NULL ) {
+ fprintf ( stderr, "find: can't open %s\n", FCODES );
+ exit ( 1 );
+ }
+ for ( i = 0; i < 128; i++ )
+ bigram1[i] = getc ( fp ), bigram2[i] = getc ( fp );
+
+ if ( index ( pathpart, '*' ) || index ( pathpart, '?' ) || index ( pathpart, '[' ) )
+ globflag = YES;
+ patend = patprep ( pathpart );
+
+ c = getc ( fp );
+ for ( ; ; ) {
+
+ count += ( (c == ESCCODE) ? getw ( fp ) : c ) - OFFSET;
+
+ for ( p = path + count; (c = getc ( fp )) > ESCCODE; ) /* overlay old path */
+ if ( c < 0200 )
+ *p++ = c;
+ else /* bigrams are parity-marked */
+ *p++ = bigram1[c & 0177], *p++ = bigram2[c & 0177];
+ if ( c == EOF )
+ break;
+ *p-- = NULL;
+ 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 ( *q != *p )
+ break;
+ if ( *p == NULL ) { /* success on fast match */
+ found = YES;
+ if ( globflag == NO || amatch ( path, pathpart ) )
+ puts ( path );
+ break;
+ }
+ }
+ }
+}
+
+/*
+ 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];
+
+char *
+patprep ( name )
+ char *name;
+{
+ register char *p, *endmark;
+ register char *subp = globfree;
+
+ *subp++ = '\0';
+ p = name + strlen ( name ) - 1;
+ /*
+ skip trailing metacharacters (and [] ranges)
+ */
+ for ( ; p >= name; p-- )
+ if ( index ( "*?", *p ) == 0 )
+ break;
+ if ( p < name )
+ p = name;
+ if ( *p == ']' )
+ for ( p--; p >= name; p-- )
+ if ( *p == '[' ) {
+ p--;
+ break;
+ }
+ if ( p < name )
+ p = name;
+ /*
+ if pattern has only metacharacters,
+ check every path (force '/' search)
+ */
+ if ( (p == name) && index ( "?*[]", *p ) != 0 )
+ *subp++ = '/';
+ else {
+ for ( endmark = p; p >= name; p-- )
+ if ( index ( "]*?", *p ) != 0 )
+ break;
+ for ( ++p; (p <= endmark) && subp < (globfree + sizeof ( globfree )); )
+ *subp++ = *p++;
+ }
+ *subp = '\0';
+ return ( --subp );
+}
+#endif
+
+/* rest should be done with nameserver or database */
+
+#include <pwd.h>
+#include <grp.h>
+#include <utmp.h>
+
+struct utmp utmp;
+#define NMAX (sizeof (utmp.ut_name))
+#define SCPYN(a, b) strncpy(a, b, NMAX)
+
+#define NUID 64
+#define NGID 300
+
+struct ncache {
+ int uid;
+ char name[NMAX+1];
+} nc[NUID];
+char outrangename[NMAX+1];
+int outrangeuid = -1;
+char groups[NGID][NMAX+1];
+char outrangegroup[NMAX+1];
+int outrangegid = -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().
+ */
+char *
+getname(uid)
+{
+ register struct passwd *pw;
+ struct passwd *getpwent();
+ register int cp;
+ extern int _pw_stayopen;
+
+ _pw_stayopen = 1;
+
+#if (((NUID) & ((NUID) - 1)) != 0)
+ cp = uid % (NUID);
+#else
+ cp = uid & ((NUID) - 1);
+#endif
+ if (uid >= 0 && nc[cp].uid == uid && nc[cp].name[0])
+ return (nc[cp].name);
+ pw = getpwuid(uid);
+ if (!pw)
+ return (0);
+ nc[cp].uid = uid;
+ SCPYN(nc[cp].name, pw->pw_name);
+ return (nc[cp].name);
+}
+
+char *
+getgroup(gid)
+{
+ register struct group *gr;
+ static init;
+ struct group *getgrent();
+
+ if (gid >= 0 && gid < NGID && groups[gid][0])
+ return (&groups[gid][0]);
+ if (gid >= 0 && gid == outrangegid)
+ return (outrangegroup);
+rescan:
+ if (init == 2) {
+ if (gid < NGID)
+ return (0);
+ setgrent();
+ while (gr = getgrent()) {
+ if (gr->gr_gid != gid)
+ continue;
+ outrangegid = gr->gr_gid;
+ SCPYN(outrangegroup, gr->gr_name);
+ endgrent();
+ return (outrangegroup);
+ }
+ endgrent();
+ return (0);
+ }
+ if (init == 0)
+ setgrent(), init = 1;
+ while (gr = getgrent()) {
+ if (gr->gr_gid < 0 || gr->gr_gid >= NGID) {
+ if (gr->gr_gid == gid) {
+ outrangegid = gr->gr_gid;
+ SCPYN(outrangegroup, gr->gr_name);
+ return (outrangegroup);
+ }
+ continue;
+ }
+ if (groups[gr->gr_gid][0])
+ continue;
+ SCPYN(groups[gr->gr_gid], gr->gr_name);
+ if (gr->gr_gid == gid)
+ return (&groups[gid][0]);
+ }
+ init = 2;
+ goto rescan;
+}
+
+int
+getuid(username)
+ char *username;
+{
+ register struct passwd *pw;
+ struct passwd *getpwnam();
+#ifndef NO_PW_STAYOPEN
+ extern int _pw_stayopen;
+
+ _pw_stayopen = 1;
+#endif
+
+ pw = getpwnam(username);
+ if (pw != NULL)
+ return (pw->pw_uid);
+ else
+ return (-1);
+}
+
+int
+getgid(groupname)
+ char *groupname;
+{
+ register struct group *gr;
+ struct group *getgrnam();
+
+ gr = getgrnam(groupname);
+ if (gr != NULL)
+ return (gr->gr_gid);
+ else
+ return (-1);
+}
+
+#define permoffset(who) ((who) * 3)
+#define permission(who, type) ((type) >> permoffset(who))
+#define kbytes(bytes) (((bytes) + 1023) / 1024)
+
+list(file, stp)
+ char *file;
+ 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;
+#ifdef S_IFLNK
+ char flink[MAXPATHLEN + 1];
+#endif
+ register int who;
+ register char *cp;
+ time_t now;
+
+ if (file == NULL || stp == NULL)
+ return (-1);
+
+ time(&now);
+ if (sixmonthsago == -1)
+ sixmonthsago = now - 6L*30L*24L*60L*60L;
+
+ switch (stp->st_mode & S_IFMT) {
+#ifdef S_IFDIR
+ case S_IFDIR: /* directory */
+ pmode[0] = 'd';
+ break;
+#endif
+#ifdef S_IFCHR
+ case S_IFCHR: /* character special */
+ pmode[0] = 'c';
+ break;
+#endif
+#ifdef S_IFBLK
+ case S_IFBLK: /* block special */
+ pmode[0] = 'b';
+ break;
+#endif
+#ifdef S_IFLNK
+ case S_IFLNK: /* symbolic link */
+ pmode[0] = 'l';
+ break;
+#endif
+#ifdef S_IFSOCK
+ case S_IFSOCK: /* socket */
+ pmode[0] = 's';
+ break;
+#endif
+#ifdef S_IFREG
+ case S_IFREG: /* regular */
+#endif
+ default:
+ pmode[0] = '-';
+ break;
+ }
+
+ for (who = 0; who < 3; who++) {
+ if (stp->st_mode & permission(who, S_IREAD))
+ pmode[permoffset(who) + 1] = 'r';
+ else
+ pmode[permoffset(who) + 1] = '-';
+
+ if (stp->st_mode & permission(who, S_IWRITE))
+ pmode[permoffset(who) + 2] = 'w';
+ else
+ 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';
+ else
+ pmode[permoffset(who) + 3] = '-';
+ }
+ pmode[permoffset(who) + 1] = '\0';
+
+ cp = getname(stp->st_uid);
+ if (cp != NULL)
+ sprintf(uname, "%-9.9s", cp);
+ else
+ sprintf(uname, "%-9d", stp->st_uid);
+
+ cp = getgroup(stp->st_gid);
+ if (cp != NULL)
+ sprintf(gname, "%-9.9s", cp);
+ else
+ 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));
+ else {
+ sprintf(fsize, "%8ld", stp->st_size);
+#ifdef S_IFLNK
+ if (pmode[0] == 'l') {
+ /*
+ * Need to get the tail of the file name, since we have
+ * already chdir()ed into the directory of the file
+ */
+ cp = rindex(file, '/');
+ if (cp == NULL)
+ cp = file;
+ else
+ cp++;
+ who = readlink(cp, flink, sizeof flink - 1);
+ if (who >= 0)
+ flink[who] = '\0';
+ else
+ flink[0] = '\0';
+ }
+#endif
+ }
+
+ cp = ctime(&stp->st_mtime);
+ if (stp->st_mtime < sixmonthsago || stp->st_mtime > now)
+ sprintf(ftime, "%-7.7s %-4.4s", cp + 4, cp + 20);
+ else
+ sprintf(ftime, "%-12.12s", cp + 4);
+
+ printf("%5lu %4ld %s %2d %s%s%s %s %s%s%s\n",
+ stp->st_ino, /* inode # */
+#ifdef S_IFSOCK
+ (long) kbytes(dbtob(stp->st_blocks)), /* kbytes */
+#else
+ (long) kbytes(stp->st_size), /* kbytes */
+#endif
+ pmode, /* protection */
+ stp->st_nlink, /* # of links */
+ uname, /* owner */
+ gname, /* group */
+ fsize, /* # of bytes */
+ ftime, /* modify time */
+ file, /* name */
+#ifdef S_IFLNK
+ (pmode[0] == 'l') ? " -> " : "",
+ (pmode[0] == 'l') ? flink : "" /* symlink */
+#else
+ "",
+ ""
+#endif
+ );
+
+ return (0);
+}
projects / unix-history / blobdiff