home *** CD-ROM | disk | FTP | other *** search
/ Il CD di internet / CD.iso / SOURCE / A / FIND / FINDUTIL.1 / FINDUTIL / findutils-4.1 / locate / frcode.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-26  |  4.5 KB  |  171 lines
  1. /* frcode -- front-compress a sorted list
  2.    Copyright (C) 1994 Free Software Foundation, Inc.
  3.  
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2, or (at your option)
  7.    any later version.
  8.  
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.  
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17.  
  18. /* Usage: frcode < sorted-list > compressed-list
  19.  
  20.    Uses front compression (also known as incremental encoding);
  21.    see ";login:", March 1983, p. 8.
  22.  
  23.    The input is a sorted list of NUL-terminated strings.
  24.    (FIXME newline-terminated, until we figure out how to sort
  25.    NUL-terminated strings.)
  26.  
  27.    The output entries are in the same order as the input;
  28.    each entry consists of an offset-differential count byte
  29.    (the additional number of characters of prefix of the preceding entry to
  30.    use beyond the number that the preceding entry is using of its predecessor),
  31.    followed by a null-terminated ASCII remainder.
  32.  
  33.    If the offset-differential count is larger than can be stored
  34.    in a byte (+/-127), the byte has the value LOCATEDB_ESCAPE
  35.    and the count follows in a 2-byte word, with the high byte first
  36.    (network byte order).
  37.  
  38.    Example:
  39.  
  40.    Input, with NULs changed to newlines:
  41.    /usr/src
  42.    /usr/src/cmd/aardvark.c
  43.    /usr/src/cmd/armadillo.c
  44.    /usr/tmp/zoo
  45.  
  46.    Length of the longest prefix of the preceding entry to share:
  47.    0 /usr/src
  48.    8 /cmd/aardvark.c
  49.    14 rmadillo.c
  50.    5 tmp/zoo
  51.  
  52.    Output, with NULs changed to newlines and count bytes made printable:
  53.    0 LOCATE02
  54.    0 /usr/src
  55.    8 /cmd/aardvark.c
  56.    6 rmadillo.c
  57.    -9 tmp/zoo
  58.  
  59.    (6 = 14 - 8, and -9 = 5 - 14)
  60.  
  61.    Written by James A. Woods <jwoods@adobe.com>.
  62.    Modified by David MacKenzie <djm@gnu.ai.mit.edu>.  */
  63.  
  64. #include <config.h>
  65. #include <stdio.h>
  66. #include <sys/types.h>
  67.  
  68. #if defined(HAVE_STRING_H) || defined(STDC_HEADERS)
  69. #include <string.h>
  70. #else
  71. #include <strings.h>
  72. #endif
  73.  
  74. #ifdef STDC_HEADERS
  75. #include <stdlib.h>
  76. #endif
  77.  
  78. #include "locatedb.h"
  79.  
  80. char *xmalloc ();
  81.  
  82. /* The name this program was run with.  */
  83. char *program_name;
  84.  
  85. /* Write out a 16-bit int, high byte first (network byte order).  */
  86.  
  87. static void
  88. put_short (c, fp)
  89.      int c;
  90.      FILE *fp;
  91. {
  92.   putc (c >> 8, fp);
  93.   putc (c, fp); 
  94. }
  95.  
  96. /* Return the length of the longest common prefix of strings S1 and S2. */
  97.  
  98. static int
  99. prefix_length (s1, s2)
  100.      char *s1, *s2;
  101. {
  102.   register char *start;
  103.  
  104.   for (start = s1; *s1 == *s2 && *s1 != '\0'; s1++, s2++)
  105.     ;
  106.   return s1 - start;
  107. }
  108.  
  109. void
  110. main (argc, argv)
  111.      int argc;
  112.      char **argv;
  113. {
  114.   char *path;            /* The current input entry.  */
  115.   char *oldpath;        /* The previous input entry.  */
  116.   size_t pathsize, oldpathsize;    /* Amounts allocated for them.  */
  117.   int count, oldcount, diffcount; /* Their prefix lengths & the difference. */
  118.   int line_len;            /* Length of input line.  */
  119.  
  120.   program_name = argv[0];
  121.  
  122.   pathsize = oldpathsize = 1026; /* Increased as necessary by getstr.  */
  123.   path = xmalloc (pathsize);
  124.   oldpath = xmalloc (oldpathsize);
  125.  
  126.   /* Set to anything not starting with a slash, to force the first
  127.      prefix count to 0.  */
  128.   strcpy (oldpath, " ");
  129.   oldcount = 0;
  130.  
  131.   fwrite (LOCATEDB_MAGIC, sizeof (LOCATEDB_MAGIC), 1, stdout);
  132.  
  133.   /* FIXME temporary: change the \n to \0 when we figure out how to sort
  134.      null-terminated strings.  */
  135.   while ((line_len = getstr (&path, &pathsize, stdin, '\n', 0)) > 0)
  136.     {
  137.       path[line_len - 1] = '\0'; /* FIXME temporary: nuke the newline.  */
  138.  
  139.       count = prefix_length (oldpath, path);
  140.       diffcount = count - oldcount;
  141.       oldcount = count;
  142.       /* If the difference is small, it fits in one byte;
  143.      otherwise, two bytes plus a marker noting that fact.  */
  144.       if (diffcount < -127 || diffcount > 127)
  145.     {
  146.       putc (LOCATEDB_ESCAPE, stdout);
  147.       put_short (diffcount, stdout);
  148.     }
  149.       else
  150.     putc (diffcount, stdout);
  151.  
  152.       fputs (path + count, stdout);
  153.       putc ('\0', stdout);
  154.  
  155.       {
  156.     /* Swap path and oldpath and their sizes.  */
  157.     char *tmppath = oldpath;
  158.     size_t tmppathsize = oldpathsize;
  159.     oldpath = path;
  160.     oldpathsize = pathsize;
  161.     path = tmppath;
  162.     pathsize = tmppathsize;
  163.       }
  164.     }
  165.  
  166.   free (path);
  167.   free (oldpath);
  168.  
  169.   exit (0);
  170. }
  171.