home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / f / find12as.zip / FASTFIND.C < prev    next >
C/C++ Source or Header  |  1992-02-22  |  5KB  |  215 lines
  1. /* fastfind.c -- list files in database matching a pattern
  2.  
  3.    'fastfind' scans a file list for the full pathname of a file
  4.    given only a piece of the name.  The list has been processed with
  5.    "front-compression" and bigram coding.  Front compression reduces
  6.    space by a factor of 4-5, bigram coding by a further 20-25%.
  7.  
  8.    The codes are:
  9.  
  10.    0-28        likeliest differential counts + offset to make nonnegative
  11.    30        escape code for out-of-range count to follow in next word
  12.    128-255     bigram codes (128 most common, as determined by 'updatedb')
  13.    32-127      single character (printable) ASCII residue
  14.  
  15.    A novel two-tiered string search technique is employed:
  16.  
  17.    First, a metacharacter-free subpattern and partial pathname is
  18.    matched BACKWARDS to avoid full expansion of the pathname list.
  19.    The time savings is 40-50% over forward matching, which cannot efficiently
  20.    handle overlapped search patterns and compressed path residue.
  21.  
  22.    Then, the actual shell glob-style regular expression (if in this form)
  23.    is matched against the candidate pathnames using the slower routines
  24.    provided in the standard 'find'.
  25.  
  26.    Author: James A. Woods (jaw@riacs.edu)
  27.    Modified by David MacKenzie (djm@ai.mit.edu)
  28.    MS-DOS mods: Thorsten Ohl (ohl@gnu.ai.mit.edu)
  29.    Public domain. */
  30.  
  31. #include <stdio.h>
  32. #ifndef USG
  33. #include <strings.h>
  34. #else
  35. #include <string.h>
  36. #define index strchr
  37. #define rindex strrchr
  38. #endif
  39. #include <sys/types.h>
  40. #ifndef MSDOS
  41. #include <sys/param.h>
  42. #endif /* MSDOS */
  43.  
  44. #ifndef MAXPATHLEN
  45. #define MAXPATHLEN 1024
  46. #endif
  47.  
  48. #define    YES    1
  49. #define    NO    0
  50.  
  51. #define    OFFSET    14
  52.  
  53. #define    ESCCODE    30
  54.  
  55. #ifdef MSDOS
  56.  
  57. #include <stdlib.h>
  58.  
  59. #include <gnulib.h>
  60. char *patprep (char *name);
  61. void fastfind (char *pathpart);
  62.  
  63. #else /* not MSDOS */
  64.  
  65. extern int errno;
  66.  
  67. char *index ();
  68. char *patprep ();
  69. void error ();
  70.  
  71. #endif /* not MSDOS */
  72.  
  73. void
  74. fastfind (pathpart)
  75.      char *pathpart;
  76. {
  77.   register char *p, *s;
  78.   register int c;
  79.   char *q;
  80.   int i, count = 0, globflag;
  81.   FILE *fp;
  82.   char *patend, *cutoff;
  83.   char path[MAXPATHLEN];
  84.   char bigram1[128], bigram2[128];
  85.   int found = NO;
  86.  
  87.   fp = fopen (FCODES, "r");
  88.   if (fp == NULL)
  89.     error (1, errno, "%s", FCODES);
  90.  
  91.   for (i = 0; i < 128; i++)
  92.     {
  93.       bigram1[i] = getc (fp);
  94.       bigram2[i] = getc (fp);
  95.     }
  96.  
  97.   globflag = glob_pattern_p (pathpart);
  98.   patend = patprep (pathpart);
  99.  
  100.   c = getc (fp);
  101.   for (;;)
  102.     {
  103.       count += ((c == ESCCODE) ? getw (fp) : c) - OFFSET;
  104.  
  105.       for (p = path + count; (c = getc (fp)) > ESCCODE;)
  106.     /* Overlay old path. */
  107.     if (c < 0200)
  108.       *p++ = c;
  109.     else
  110.       {
  111.         /* Bigrams are parity-marked. */
  112.         *p++ = bigram1[c & 0177];
  113.         *p++ = bigram2[c & 0177];
  114.       }
  115.       if (c == EOF)
  116.     break;
  117.       *p-- = '\0';
  118.       cutoff = path;
  119.       if (!found)
  120.     cutoff += count;
  121.  
  122.       for (found = NO, s = p; s >= cutoff; s--)
  123.     if (*s == *patend)
  124.       {
  125.         /* Fast first char check. */
  126.         for (p = patend - 1, q = s - 1; *p != '\0'; p--, q--)
  127.           if (*q != *p)
  128.         break;
  129.         if (*p == '\0')
  130.           {
  131.         /* Success on fast match. */
  132.         found = YES;
  133.         if (globflag == NO || glob_match (pathpart, path, 1))
  134.           puts (path);
  135.         break;
  136.           }
  137.       }
  138.     }
  139. }
  140.  
  141. static char globfree[100];
  142.  
  143. /* Extract the last glob-free subpattern in NAME for fast pre-match;
  144.    prepend '\0' for backwards match; return the end of the new pattern. */
  145.  
  146. char *
  147. patprep (name)
  148.      char *name;
  149. {
  150.   register char *p, *endmark;
  151.   register char *subp = globfree;
  152.  
  153.   *subp++ = '\0';
  154.   p = name + strlen (name) - 1;
  155.   /* Skip trailing metacharacters (and [] ranges). */
  156.   for (; p >= name; p--)
  157.     if (index ("*?", *p) == 0)
  158.       break;
  159.   if (p < name)
  160.     p = name;
  161.   if (*p == ']')
  162.     for (p--; p >= name; p--)
  163.       if (*p == '[')
  164.     {
  165.       p--;
  166.       break;
  167.     }
  168.   if (p < name)
  169.     p = name;
  170.   /* If pattern has only metacharacters,
  171.      check every path (force '/' search). */
  172.   if (p == name && index ("?*[]", *p) != 0)
  173.     *subp++ = '/';
  174.   else
  175.     {
  176.       for (endmark = p; p >= name; p--)
  177.     if (index ("]*?", *p) != 0)
  178.       break;
  179.       for (++p; p <= endmark && subp < (globfree + sizeof (globfree));)
  180.     *subp++ = *p++;
  181.     }
  182.   *subp-- = '\0';
  183.   return subp;
  184. }
  185.  
  186. /* The name this program was run with. */
  187. char *program_name;
  188.  
  189. /* Usage: find pattern
  190.    Searches a pre-computed file list constructed nightly by cron.
  191.    Its effect is similar to, but much faster than,
  192.    find / -mtime +0 -name "*pattern*" -print */
  193.  
  194. void
  195. main (argc, argv)
  196.      int argc;
  197.      char **argv;
  198. {
  199.   int optind;
  200.  
  201.   program_name = argv[0];
  202. #ifdef MSDOS            /* cosmetics  */
  203.   strlwr (program_name);
  204. #endif
  205.  
  206.   if (argc == 1)
  207.     {
  208.       fprintf (stderr, "Usage: %s pattern...\n", argv[0]);
  209.       exit (1);
  210.     }
  211.   for (optind = 1; optind < argc; ++optind)
  212.     fastfind (argv[optind]);
  213.   exit (0);
  214. }
  215.