home *** CD-ROM | disk | FTP | other *** search
/ Chip 1995 March / CHIP3.mdf / slackwar / a / util / util-lin.2 / util-lin / util-linux-2.2 / misc-utils / look.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-22  |  9.0 KB  |  366 lines
  1. /*-
  2.  * Copyright (c) 1991, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * David Hitz of Auspex Systems, Inc.
  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. static char copyright[] =
  39. "@(#) Copyright (c) 1991, 1993\n\
  40.     The Regents of the University of California.  All rights reserved.\n";
  41. #endif /* not lint */
  42.  
  43. #ifndef lint
  44. static char sccsid[] = "@(#)look.c    8.1 (Berkeley) 6/14/93";
  45. #endif /* not lint */
  46.  
  47. /*
  48.  * look -- find lines in a sorted list.
  49.  * 
  50.  * The man page said that TABs and SPACEs participate in -d comparisons.
  51.  * In fact, they were ignored.  This implements historic practice, not
  52.  * the manual page.
  53.  */
  54.  
  55. #include <sys/types.h>
  56. #include <sys/mman.h>
  57. #include <sys/stat.h>
  58.  
  59. #include <limits.h>
  60. #include <errno.h>
  61. #include <fcntl.h>
  62. #include <stdio.h>
  63. #include <stdlib.h>
  64. #include <string.h>
  65. #include <ctype.h>
  66. #include <getopt.h>
  67. #include "pathnames.h"
  68.  
  69. /*
  70.  * FOLD and DICT convert characters to a normal form for comparison,
  71.  * according to the user specified flags.
  72.  * 
  73.  * DICT expects integers because it uses a non-character value to
  74.  * indicate a character which should not participate in comparisons.
  75.  */
  76. #define    EQUAL        0
  77. #define    GREATER        1
  78. #define    LESS        (-1)
  79. #define NO_COMPARE    (-2)
  80.  
  81. #define    FOLD(c)    (isascii(c) && isupper(c) ? tolower(c) : (c))
  82. #define    DICT(c)    (isascii(c) && isalnum(c) ? (c) : NO_COMPARE)
  83.  
  84. int dflag, fflag;
  85.  
  86. char    *binary_search __P((char *, char *, char *));
  87. int     compare __P((char *, char *, char *));
  88. void     err __P((const char *fmt, ...));
  89. char    *linear_search __P((char *, char *, char *));
  90. int     look __P((char *, char *, char *));
  91. void     print_from __P((char *, char *, char *));
  92.  
  93. static void usage __P((void));
  94.  
  95. main(argc, argv)
  96.     int argc;
  97.     char *argv[];
  98. {
  99.     struct stat sb;
  100.     int ch, fd, termchar;
  101.     char *back, *file, *front, *string, *p;
  102.  
  103.     file = _PATH_WORDS;
  104.     termchar = '\0';
  105.     while ((ch = getopt(argc, argv, "adft:")) != EOF)
  106.         switch(ch) {
  107.         case 'a':
  108.                    file = _PATH_WORDS_ALT;
  109.                 break;
  110.         case 'd':
  111.             dflag = 1;
  112.             break;
  113.         case 'f':
  114.             fflag = 1;
  115.             break;
  116.         case 't':
  117.             termchar = *optarg;
  118.             break;
  119.         case '?':
  120.         default:
  121.             usage();
  122.         }
  123.     argc -= optind;
  124.     argv += optind;
  125.  
  126.     switch (argc) {
  127.     case 2:                /* Don't set -df for user. */
  128.         string = *argv++;
  129.         file = *argv;
  130.         break;
  131.     case 1:                /* But set -df by default. */
  132.         dflag = fflag = 1;
  133.         string = *argv;
  134.         break;
  135.     default:
  136.         usage();
  137.     }
  138.  
  139.     if (termchar != '\0' && (p = strchr(string, termchar)) != NULL)
  140.         *++p = '\0';
  141.  
  142.     if ((fd = open(file, O_RDONLY, 0)) < 0 || fstat(fd, &sb))
  143.         err("%s: %s", file, strerror(errno));
  144.     if ((void *)(front = mmap(NULL,
  145.                   (size_t)sb.st_size,
  146.                   PROT_READ,
  147.                   MAP_FILE|MAP_SHARED,
  148.                   fd,
  149.                   (off_t)0)) <= (void *)0)
  150.         err("%s: %s", file, strerror(errno));
  151.     back = front + sb.st_size;
  152.     exit(look(string, front, back));
  153. }
  154.  
  155. look(string, front, back)
  156.     char *string, *front, *back;
  157. {
  158.     register int ch;
  159.     register char *readp, *writep;
  160.  
  161.     /* Reformat string string to avoid doing it multiple times later. */
  162.     for (readp = writep = string; ch = *readp++;) {
  163.         if (fflag)
  164.             ch = FOLD(ch);
  165.         if (dflag)
  166.             ch = DICT(ch);
  167.         if (ch != NO_COMPARE)
  168.             *(writep++) = ch;
  169.     }
  170.     *writep = '\0';
  171.  
  172.     front = binary_search(string, front, back);
  173.     front = linear_search(string, front, back);
  174.  
  175.     if (front)
  176.         print_from(string, front, back);
  177.     return (front ? 0 : 1);
  178. }
  179.  
  180.  
  181. /*
  182.  * Binary search for "string" in memory between "front" and "back".
  183.  * 
  184.  * This routine is expected to return a pointer to the start of a line at
  185.  * *or before* the first word matching "string".  Relaxing the constraint
  186.  * this way simplifies the algorithm.
  187.  * 
  188.  * Invariants:
  189.  *     front points to the beginning of a line at or before the first 
  190.  *    matching string.
  191.  * 
  192.  *     back points to the beginning of a line at or after the first 
  193.  *    matching line.
  194.  * 
  195.  * Base of the Invariants.
  196.  *     front = NULL; 
  197.  *    back = EOF;
  198.  * 
  199.  * Advancing the Invariants:
  200.  * 
  201.  *     p = first newline after halfway point from front to back.
  202.  * 
  203.  *     If the string at "p" is not greater than the string to match, 
  204.  *    p is the new front.  Otherwise it is the new back.
  205.  * 
  206.  * Termination:
  207.  * 
  208.  *     The definition of the routine allows it return at any point, 
  209.  *    since front is always at or before the line to print.
  210.  * 
  211.  *     In fact, it returns when the chosen "p" equals "back".  This 
  212.  *    implies that there exists a string is least half as long as 
  213.  *    (back - front), which in turn implies that a linear search will 
  214.  *    be no more expensive than the cost of simply printing a string or two.
  215.  * 
  216.  *     Trying to continue with binary search at this point would be 
  217.  *    more trouble than it's worth.
  218.  */
  219. #define    SKIP_PAST_NEWLINE(p, back) \
  220.     while (p < back && *p++ != '\n');
  221.  
  222. char *
  223. binary_search(string, front, back)
  224.     register char *string, *front, *back;
  225. {
  226.     register char *p;
  227.  
  228.     p = front + (back - front) / 2;
  229.     SKIP_PAST_NEWLINE(p, back);
  230.  
  231.     /*
  232.      * If the file changes underneath us, make sure we don't
  233.      * infinitely loop.
  234.      */
  235.     while (p < back && back > front) {
  236.         if (compare(string, p, back) == GREATER)
  237.             front = p;
  238.         else
  239.             back = p;
  240.         p = front + (back - front) / 2;
  241.         SKIP_PAST_NEWLINE(p, back);
  242.     }
  243.     return (front);
  244. }
  245.  
  246. /*
  247.  * Find the first line that starts with string, linearly searching from front
  248.  * to back.
  249.  * 
  250.  * Return NULL for no such line.
  251.  * 
  252.  * This routine assumes:
  253.  * 
  254.  *     o front points at the first character in a line. 
  255.  *    o front is before or at the first line to be printed.
  256.  */
  257. char *
  258. linear_search(string, front, back)
  259.     char *string, *front, *back;
  260. {
  261.     while (front < back) {
  262.         switch (compare(string, front, back)) {
  263.         case EQUAL:        /* Found it. */
  264.             return (front);
  265.             break;
  266.         case LESS:        /* No such string. */
  267.             return (NULL);
  268.             break;
  269.         case GREATER:        /* Keep going. */
  270.             break;
  271.         }
  272.         SKIP_PAST_NEWLINE(front, back);
  273.     }
  274.     return (NULL);
  275. }
  276.  
  277. /*
  278.  * Print as many lines as match string, starting at front.
  279.  */
  280. void 
  281. print_from(string, front, back)
  282.     register char *string, *front, *back;
  283. {
  284.     for (; front < back && compare(string, front, back) == EQUAL; ++front) {
  285.         for (; front < back && *front != '\n'; ++front)
  286.             if (putchar(*front) == EOF)
  287.                 err("stdout: %s", strerror(errno));
  288.         if (putchar('\n') == EOF)
  289.             err("stdout: %s", strerror(errno));
  290.     }
  291. }
  292.  
  293. /*
  294.  * Return LESS, GREATER, or EQUAL depending on how the string1 compares with
  295.  * string2 (s1 ??? s2).
  296.  * 
  297.  *     o Matches up to len(s1) are EQUAL. 
  298.  *    o Matches up to len(s2) are GREATER.
  299.  * 
  300.  * Compare understands about the -f and -d flags, and treats comparisons
  301.  * appropriately.
  302.  * 
  303.  * The string "s1" is null terminated.  The string s2 is '\n' terminated (or
  304.  * "back" terminated).
  305.  */
  306. int
  307. compare(s1, s2, back)
  308.     register char *s1, *s2, *back;
  309. {
  310.     register int ch;
  311.  
  312.     for (; *s1 && s2 < back && *s2 != '\n';) {
  313.         ch = *s2;
  314.         if (fflag)
  315.             ch = FOLD(ch);
  316.         if (dflag)
  317.             ch = DICT(ch);
  318.  
  319.         if (ch == NO_COMPARE) {
  320.             ++s2;        /* Ignore character in comparison. */
  321.             continue;
  322.         }
  323.         if (*s1 != ch)
  324.             return (*s1 < ch ? LESS : GREATER);
  325.         ++s1;
  326.         ++s2;
  327.     }
  328.     return (*s1 ? GREATER : EQUAL);
  329. }
  330.  
  331. static void
  332. usage()
  333. {
  334.     (void)fprintf(stderr, "usage: look [-dfa] [-t char] string [file]\n");
  335.     exit(2);
  336. }
  337.  
  338. #if __STDC__
  339. #include <stdarg.h>
  340. #else
  341. #include <varargs.h>
  342. #endif
  343.  
  344. void
  345. #if __STDC__
  346. err(const char *fmt, ...)
  347. #else
  348. err(fmt, va_alist)
  349.     char *fmt;
  350.     va_dcl
  351. #endif
  352. {
  353.     va_list ap;
  354. #if __STDC__
  355.     va_start(ap, fmt);
  356. #else
  357.     va_start(ap);
  358. #endif
  359.     (void)fprintf(stderr, "look: ");
  360.     (void)vfprintf(stderr, fmt, ap);
  361.     va_end(ap);
  362.     (void)fprintf(stderr, "\n");
  363.     exit(2);
  364.     /* NOTREACHED */
  365. }
  366.