home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / f / find37.zip / find-3.7 / locate / code.c < prev    next >
C/C++ Source or Header  |  1992-07-14  |  4KB  |  180 lines
  1. /* code -- code filenames for locate
  2.  
  3.    Compress a sorted list.
  4.    Works with 'find' to encode a filename database.
  5.  
  6.    Usage:
  7.  
  8.    bigram < list > bigrams
  9.    process-bigrams > common_bigrams
  10.    code common_bigrams < list > squeezed_list
  11.  
  12.    Uses 'front compression' (see ";login:", March 1983, p. 8).
  13.    Output format is, per line, an offset differential count byte
  14.    followed by a partially bigram-encoded ASCII residue.
  15.    
  16.    The codes are:
  17.    
  18.    0-28        likeliest differential counts + offset to make nonnegative
  19.    30        escape code for out-of-range count to follow in next word
  20.    128-255     bigram codes (128 most common, as determined by 'updatedb')
  21.    32-127      single character (printable) ASCII residue
  22.  
  23.    Author: James A. Woods (jaw@riacs.edu)
  24.    Modified by David MacKenzie (djm@ai.mit.edu)
  25.    Public domain. */
  26.  
  27. #include <stdio.h>
  28. #if defined(USG) || defined(STDC_HEADERS)
  29. #include <string.h>
  30. #else
  31. #include <strings.h>
  32. #endif
  33.  
  34. #ifdef STDC_HEADERS
  35. #include <stdlib.h>
  36. #endif
  37. #include <sys/types.h>
  38. #include "pathmax.h"
  39.  
  40. char *xmalloc ();
  41. int prefix_length ();
  42. int strindex ();
  43.  
  44. /* Switch code. */
  45. #define    RESET    30
  46.  
  47. /* The name this program was run with.  */
  48. char *program_name;
  49.  
  50. char *path;
  51.  
  52. char *oldpath;
  53.  
  54. char bigrams[257] = {0};
  55.  
  56. void
  57. main (argc, argv)
  58.      int argc;
  59.      char *argv[];
  60. {
  61.   int count, oldcount, diffcount;
  62.   int j, code;
  63.   char bigram[3];
  64.   FILE *fp;
  65.   unsigned line_length;
  66.   int path_max;
  67.  
  68.   program_name = argv[0];
  69.   oldcount = 0;
  70.   bigram[2] = '\0';
  71.  
  72.   if (argc != 2)
  73.     {
  74.       fprintf (stderr, "Usage: %s common_bigrams < list > coded_list\n",
  75.            argv[0]);
  76.       exit (2);
  77.     }
  78.  
  79.   fp = fopen (argv[1], "r");
  80.   if (fp == NULL)
  81.     {
  82.       fprintf (stderr, "%s: ", argv[0]);
  83.       perror (argv[1]);
  84.       exit (1);
  85.     }
  86.  
  87.   path_max = PATH_MAX;
  88.   path = xmalloc (path_max + 2);
  89.   oldpath = xmalloc (path_max + 2);
  90.   path[path_max] = '\0';
  91.   strcpy (oldpath, " ");
  92.  
  93.   fgets (bigrams, 257, fp);
  94.   fwrite (bigrams, 1, 256, stdout);
  95.  
  96.   while (fgets (path, path_max, stdin) != NULL)
  97.     {
  98.       line_length = strlen (path);
  99.       if (line_length == 0)
  100.     fprintf (stderr, "%s: null line in input\n", argv[0]);
  101.       else if (path[line_length - 1] != '\n')
  102.     fprintf (stderr, "%s: long line in input; truncating to `%s'\n",
  103.          argv[0], path);
  104.       else
  105.     path[line_length - 1] = '\0'; /* Remove newline. */
  106.  
  107.       /* Squelch unprintable chars so as not to botch decoding. */
  108.       for (j = 0; path[j] != '\0'; j++)
  109.     {
  110.       path[j] &= 0177;
  111.       if (path[j] < 040 || path[j] == 0177)
  112.         path[j] = '?';
  113.     }
  114.       count = prefix_length (oldpath, path);
  115.       diffcount = count - oldcount;
  116.       if (diffcount < -14 || diffcount > 14)
  117.     {
  118.       putc (RESET, stdout);
  119.       putw (diffcount + 14, stdout);
  120.     }
  121.       else
  122.     putc (diffcount + 14, stdout);
  123.  
  124.       for (j = count; path[j] != '\0'; j += 2)
  125.     {
  126.       if (path[j + 1] == '\0')
  127.         {
  128.           putchar (path[j]);
  129.           break;
  130.         }
  131.       bigram[0] = path[j];
  132.       bigram[1] = path[j + 1];
  133.       /* Linear search for specific bigram in string table. */
  134.       code = strindex (bigrams, bigram);
  135.       if (code % 2 == 0)
  136.         putchar ((code / 2) | 0200);
  137.       else
  138.         fputs (bigram, stdout);
  139.     }
  140.       strcpy (oldpath, path);
  141.       oldcount = count;
  142.     }
  143.   exit (0);
  144. }
  145.  
  146. /* Return location of PATTERN in STRING or -1. */
  147.  
  148. int
  149. strindex (string, pattern)
  150.      char *string, *pattern;
  151. {
  152.   register char *s, *p, *q;
  153.  
  154.   for (s = string; *s != '\0'; s++)
  155.     if (*s == *pattern)
  156.       {
  157.     /* Fast first char check. */
  158.     for (p = pattern + 1, q = s + 1; *p != '\0'; p++, q++)
  159.       if (*q != *p)
  160.         break;
  161.     if (*p == '\0')
  162.       return q - strlen (pattern) - string;
  163.       }
  164.   return -1;
  165. }
  166.  
  167. /* Return length of longest common prefix of strings S1 and S2. */
  168.  
  169. int
  170. prefix_length (s1, s2)
  171.      char *s1, *s2;
  172. {
  173.   register char *start;
  174.  
  175.   for (start = s1; *s1 == *s2; s1++, s2++)
  176.     if (*s1 == '\0')
  177.       break;
  178.   return s1 - start;
  179. }
  180.