home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / gnu / find-3.8-src.lha / src / amiga / find-3.8 / locate / locate.c < prev    next >
C/C++ Source or Header  |  1994-02-23  |  6KB  |  255 lines
  1. /* locate -- list files in databases that match a pattern
  2.  
  3.    Usage: locate pattern...
  4.    Searches a pre-computed file list constructed nightly by cron.
  5.    Its effect is similar to, but much faster than,
  6.    find / -mtime +0 \( -name "*pattern1*" -o -name "*pattern2*" ... \) -print
  7.  
  8.    `locate' scans a file list for the full pathname of a file
  9.    given only a piece of the name.  The list has been processed with
  10.    "front-compression" and bigram coding.  Front compression reduces
  11.    space by a factor of 4-5, bigram coding by a further 20-25%.
  12.  
  13.    The codes are:
  14.  
  15.    0-28        likeliest differential counts + offset to make nonnegative
  16.    30        escape code for out-of-range count to follow in next word
  17.    128-255     bigram codes (128 most common, as determined by 'updatedb')
  18.    32-127      single character (printable) ASCII residue
  19.  
  20.    A novel two-tiered string search technique is employed:
  21.  
  22.    First, a metacharacter-free subpattern and partial pathname is
  23.    matched BACKWARDS to avoid full expansion of the pathname list.
  24.    The time savings is 40-50% over forward matching, which cannot efficiently
  25.    handle overlapped search patterns and compressed path residue.
  26.  
  27.    Then, the actual shell glob-style regular expression (if in this form)
  28.    is matched against the candidate pathnames using the slower standard
  29.    shell filename matching routines.
  30.  
  31.    Author: James A. Woods (jaw@riacs.edu)
  32.    Modified by David MacKenzie (djm@gnu.ai.mit.edu)
  33.    Public domain. */
  34.  
  35. #include <stdio.h>
  36. #include <fnmatch.h>
  37. #include <getopt.h>
  38. #if defined(HAVE_STRING_H) || defined(STDC_HEADERS)
  39. #include <string.h>
  40. #define index strchr
  41. #else
  42. #include <strings.h>
  43. #endif
  44.  
  45. #ifdef STDC_HEADERS
  46. #include <stdlib.h>
  47. #else
  48. char *getenv ();
  49. #endif
  50.  
  51. #ifdef STDC_HEADERS
  52. #include <errno.h>
  53. #include <stdlib.h>
  54. #else
  55. extern int errno;
  56. #endif
  57. #include <sys/types.h>
  58. #include "pathmax.h"
  59.  
  60. #define    TRUE    1
  61. #define    FALSE    0
  62.  
  63. #define    OFFSET    14
  64.  
  65. #define    ESCCODE    30
  66.  
  67. char *next_element ();
  68. char *xmalloc ();
  69. void error ();
  70.  
  71. static char *patprep ();
  72.  
  73. /* Print the entries in DBFILE that match PATHPART.
  74.    Return the number of entries printed.  */
  75.  
  76. static int
  77. locate (pathpart, dbfile)
  78.      char *pathpart, *dbfile;
  79. {
  80.   register char *p, *s;
  81.   register int c;
  82.   char *q;
  83.   int i, count = 0, globflag;
  84.   FILE *fp;
  85.   char *patend, *cutoff;
  86.   char *path;
  87.   int path_max;
  88.   char bigram1[128], bigram2[128];
  89.   int found = FALSE;
  90.   int printed = 0;
  91.  
  92.   fp = fopen (dbfile, "r");
  93.   if (fp == NULL)
  94.     {
  95.       error (0, errno, "%s", dbfile);
  96.       return 0;
  97.     }
  98.  
  99.   path_max = PATH_MAX;
  100.   path = xmalloc (path_max + 2);
  101.  
  102.   for (i = 0; i < 128; i++)
  103.     {
  104.       bigram1[i] = getc (fp);
  105.       bigram2[i] = getc (fp);
  106.     }
  107.  
  108.   globflag = index (pathpart, '*') || index (pathpart, '?')
  109.     || index (pathpart, '[');
  110.   patend = patprep (pathpart);
  111.  
  112.   c = getc (fp);
  113.   while (c != EOF)
  114.     {
  115.       count += ((c == ESCCODE) ? getw (fp) : c) - OFFSET;
  116.  
  117.       for (p = path + count; (c = getc (fp)) > ESCCODE;)
  118.     /* Overlay old path. */
  119.     if (c < 0200)
  120.       *p++ = c;
  121.     else
  122.       {
  123.         /* Bigrams are parity-marked. */
  124.         *p++ = bigram1[c & 0177];
  125.         *p++ = bigram2[c & 0177];
  126.       }
  127.       *p-- = '\0';
  128.       cutoff = path;
  129.       if (!found)
  130.     cutoff += count;
  131.  
  132.       for (found = FALSE, s = p; s >= cutoff; s--)
  133.     if (*s == *patend)
  134.       {
  135.         /* Fast first char check. */
  136.         for (p = patend - 1, q = s - 1; *p != '\0'; p--, q--)
  137.           if (*q != *p)
  138.         break;
  139.         if (*p == '\0')
  140.           {
  141.         /* Success on fast match. */
  142.         found = TRUE;
  143.         if (globflag == FALSE || fnmatch (pathpart, path, 0) == 0)
  144.           {
  145.             puts (path);
  146.             ++printed;
  147.           }
  148.         break;
  149.           }
  150.       }
  151.     }
  152.   return printed;
  153. }
  154.  
  155. /* Extract the last glob-free subpattern in NAME for fast pre-match;
  156.    prepend '\0' for backwards match; return the end of the new pattern. */
  157.  
  158. static char *
  159. patprep (name)
  160.      char *name;
  161. {
  162.   static char globfree[100];
  163.   register char *subp = globfree;
  164.   register char *p, *endmark;
  165.  
  166.   *subp++ = '\0';
  167.   p = name + strlen (name) - 1;
  168.   /* Skip trailing metacharacters (and [] ranges). */
  169.   for (; p >= name; p--)
  170.     if (index ("*?", *p) == 0)
  171.       break;
  172.   if (p < name)
  173.     p = name;
  174.   if (*p == ']')
  175.     for (p--; p >= name; p--)
  176.       if (*p == '[')
  177.     {
  178.       p--;
  179.       break;
  180.     }
  181.   if (p < name)
  182.     p = name;
  183.  
  184.   /* If pattern has only metacharacters,
  185.      check every path (force '/' search). */
  186.   if (p == name && index ("?*[]", *p) != 0)
  187.     *subp++ = '/';
  188.   else
  189.     {
  190.       for (endmark = p; p >= name; p--)
  191.     if (index ("]*?", *p) != 0)
  192.       break;
  193.       for (++p; p <= endmark && subp < (globfree + sizeof (globfree));)
  194.     *subp++ = *p++;
  195.     }
  196.   *subp-- = '\0';
  197.  
  198.   return subp;
  199. }
  200.  
  201. /* The name this program was run with. */
  202. char *program_name;
  203.  
  204. static void
  205. usage ()
  206. {
  207.   fprintf (stderr, "Usage: %s [-d path] [--database=path] pattern...\n",
  208.        program_name);
  209.   exit (1);
  210. }
  211.  
  212. static struct option const longopts[] =
  213. {
  214.   {"database", required_argument, NULL, 'd'},
  215.   {NULL, 0, NULL, 0}
  216. };
  217.  
  218. int
  219. main (argc, argv)
  220.      int argc;
  221.      char **argv;
  222. {
  223.   char *dbpath, *e;
  224.   int found = 0, optc;
  225.  
  226.   program_name = argv[0];
  227.  
  228.   dbpath = getenv ("LOCATE_PATH");
  229.   if (dbpath == NULL)
  230.     dbpath = LOCATE_DB;
  231.  
  232.   while ((optc = getopt_long (argc, argv, "d:", longopts, (int *) 0)) != -1)
  233.     switch (optc)
  234.       {
  235.       case 'd':
  236.     dbpath = optarg;
  237.     break;
  238.  
  239.       default:
  240.     usage ();
  241.       }
  242.  
  243.   if (optind == argc)
  244.     usage ();
  245.  
  246.   for (; optind < argc; optind++)
  247.     {
  248.       next_element (dbpath);    /* Initialize.  */
  249.       while ((e = next_element ((char *) NULL)) != NULL)
  250.     found |= locate (argv[optind], e);
  251.     }
  252.  
  253.   exit (!found);
  254. }
  255.