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