home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / usr.bin / locate / code / locate.code.c next >
Encoding:
C/C++ Source or Header  |  1991-04-17  |  5.4 KB  |  166 lines
  1. /*
  2.  * Copyright (c) 1989 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * James A. Woods.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #ifndef lint
  38. char copyright[] =
  39. "@(#) Copyright (c) 1989 The Regents of the University of California.\n\
  40.  All rights reserved.\n";
  41. #endif /* not lint */
  42.  
  43. #ifndef lint
  44. static char sccsid[] = "@(#)locate.code.c    4.8 (Berkeley) 6/1/90";
  45. #endif /* not lint */
  46.  
  47. /*
  48.  * PURPOSE:    sorted list compressor (works with a modified 'find'
  49.  *        to encode/decode a filename database)
  50.  *
  51.  * USAGE:    bigram < list > bigrams
  52.  *        process bigrams (see updatedb) > common_bigrams
  53.  *        code common_bigrams < list > squozen_list
  54.  *
  55.  * METHOD:    Uses 'front compression' (see ";login:", Volume 8, Number 1
  56.  *        February/March 1983, p. 8 ).  Output format is, per line, an
  57.  *        offset differential count byte followed by a partially bigram-
  58.  *        encoded ascii residue.  A bigram is a two-character sequence,
  59.  *        the first 128 most common of which are encoded in one byte.
  60.  *
  61.  * EXAMPLE:    For simple front compression with no bigram encoding,
  62.  *        if the input is...        then the output is...
  63.  *
  64.  *        /usr/src             0 /usr/src
  65.  *        /usr/src/cmd/aardvark.c         8 /cmd/aardvark.c
  66.  *        /usr/src/cmd/armadillo.c    14 armadillo.c
  67.  *        /usr/tmp/zoo             5 tmp/zoo
  68.  *
  69.  *      The codes are:
  70.  *
  71.  *    0-28    likeliest differential counts + offset to make nonnegative 
  72.  *    30    switch code for out-of-range count to follow in next word
  73.  *    128-255 bigram codes (128 most common, as determined by 'updatedb')
  74.  *    32-127  single character (printable) ascii residue (ie, literal)
  75.  *
  76.  * SEE ALSO:    updatedb.csh, bigram.c, find.c
  77.  * 
  78.  * AUTHOR:    James A. Woods, Informatics General Corp.,
  79.  *        NASA Ames Research Center, 10/82
  80.  */
  81.  
  82. #include <sys/param.h>
  83. #include <stdio.h>
  84. #include "locate.h"
  85.  
  86. #define BGBUFSIZE    (NBG * 2)    /* size of bigram buffer */
  87.  
  88. char buf1[MAXPATHLEN] = " ";    
  89. char buf2[MAXPATHLEN];
  90. char bigrams[BGBUFSIZE + 1] = { 0 };
  91.  
  92. main ( argc, argv )
  93.     int argc; char *argv[];
  94. {
  95.     register char *cp, *oldpath = buf1, *path = buf2;
  96.       int code, count, diffcount, oldcount = 0;
  97.     FILE *fp;
  98.  
  99.     if ((fp = fopen(argv[1], "r")) == NULL) {
  100.         printf("Usage: code common_bigrams < list > squozen_list\n");
  101.         exit(1);
  102.     }
  103.     /* first copy bigram array to stdout */
  104.     fgets ( bigrams, BGBUFSIZE + 1, fp );
  105.     fwrite ( bigrams, 1, BGBUFSIZE, stdout );
  106.     fclose( fp );
  107.  
  108.          while ( fgets ( path, sizeof(buf2), stdin ) != NULL ) {
  109.         /* truncate newline */
  110.         cp = path + strlen(path) - 1;
  111.         if (cp > path && *cp == '\n')
  112.             *cp = '\0';
  113.         /* squelch characters that would botch the decoding */
  114.         for ( cp = path; *cp != NULL; cp++ ) {
  115.             if ( (unsigned char)*cp >= PARITY )
  116.                 *cp &= PARITY-1;
  117.             else if ( *cp <= SWITCH )
  118.                 *cp = '?';
  119.         }
  120.         /* skip longest common prefix */
  121.         for ( cp = path; *cp == *oldpath; cp++, oldpath++ )
  122.             if ( *oldpath == NULL )
  123.                 break;
  124.         count = cp - path;
  125.         diffcount = count - oldcount + OFFSET;
  126.         oldcount = count;
  127.         if ( diffcount < 0 || diffcount > 2*OFFSET ) {
  128.             putc ( SWITCH, stdout );
  129.             putw ( diffcount, stdout );
  130.         }
  131.         else
  132.             putc ( diffcount, stdout );    
  133.  
  134.         while ( *cp != NULL ) {
  135.             if ( *(cp + 1) == NULL ) {
  136.                 putchar ( *cp );
  137.                 break;
  138.             }
  139.             if ( (code = bgindex ( cp )) < 0 ) {
  140.                 putchar ( *cp++ );
  141.                 putchar ( *cp++ );
  142.             }
  143.             else {    /* found, so mark byte with parity bit */
  144.                 putchar ( (code / 2) | PARITY );
  145.                 cp += 2;
  146.             }
  147.         }
  148.         if ( path == buf1 )        /* swap pointers */
  149.             path = buf2, oldpath = buf1;
  150.         else
  151.             path = buf1, oldpath = buf2;
  152.     }
  153. }
  154.  
  155. bgindex ( bg )            /* return location of bg in bigrams or -1 */
  156.     char *bg;
  157. {
  158.     register char *p;
  159.     register char bg0 = bg[0], bg1 = bg[1];
  160.  
  161.     for ( p = bigrams; *p != NULL; p++ )
  162.         if ( *p++ == bg0 && *p == bg1 )
  163.             break;
  164.     return ( *p == NULL ? -1 : --p - bigrams );
  165. }
  166.