+
+#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, 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 ( "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 first glob-free subpattern for fast pre-match;
+ prepend NULL for backwards match; return end of pattern
+*/
+static char globfree[100];
+
+char *
+patprep ( p )
+ register char *p;
+{
+ register char *subp = globfree;
+
+ while ( *p == '*' || *p == '?' )
+ p++;
+ if ( *p == '[' ) {
+ while ( *p != ']' && *p != NULL )
+ p++;
+ p++;
+ }
+ *subp++ = NULL;
+ if ( *p != NULL ) /* copy first noglob string */
+ while ( *p != '*' && *p != '?' && *p != '[' && *p != NULL &&
+ subp < (globfree + sizeof(globfree)) )
+ *subp++ = *p++;
+ else /* pattern has noglob chars only */
+ *subp++ = '/'; /* ... check every path */
+ *subp = NULL;
+ return ( --subp );
+}
+#endif
projects / unix-history / blobdiff