look.c revision 132394
11590Srgrimes/*- 21590Srgrimes * Copyright (c) 1991, 1993 31590Srgrimes * The Regents of the University of California. All rights reserved. 41590Srgrimes * 51590Srgrimes * This code is derived from software contributed to Berkeley by 61590Srgrimes * David Hitz of Auspex Systems, Inc. 71590Srgrimes * 81590Srgrimes * Redistribution and use in source and binary forms, with or without 91590Srgrimes * modification, are permitted provided that the following conditions 101590Srgrimes * are met: 111590Srgrimes * 1. Redistributions of source code must retain the above copyright 121590Srgrimes * notice, this list of conditions and the following disclaimer. 131590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141590Srgrimes * notice, this list of conditions and the following disclaimer in the 151590Srgrimes * documentation and/or other materials provided with the distribution. 161590Srgrimes * 3. All advertising materials mentioning features or use of this software 171590Srgrimes * must display the following acknowledgement: 181590Srgrimes * This product includes software developed by the University of 191590Srgrimes * California, Berkeley and its contributors. 201590Srgrimes * 4. Neither the name of the University nor the names of its contributors 211590Srgrimes * may be used to endorse or promote products derived from this software 221590Srgrimes * without specific prior written permission. 231590Srgrimes * 241590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 251590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 261590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 271590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 281590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 291590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 301590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 311590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 321590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 331590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 341590Srgrimes * SUCH DAMAGE. 351590Srgrimes */ 361590Srgrimes 371590Srgrimes#ifndef lint 3827623Scharnierstatic const char copyright[] = 391590Srgrimes"@(#) Copyright (c) 1991, 1993\n\ 401590Srgrimes The Regents of the University of California. All rights reserved.\n"; 411590Srgrimes#endif /* not lint */ 421590Srgrimes 431590Srgrimes#ifndef lint 4427623Scharnier#if 0 4523693Speterstatic char sccsid[] = "@(#)look.c 8.2 (Berkeley) 5/4/95"; 4627623Scharnier#endif 471590Srgrimes#endif /* not lint */ 4899112Sobrien#include <sys/cdefs.h> 4999112Sobrien__FBSDID("$FreeBSD: head/usr.bin/look/look.c 132394 2004-07-19 11:12:02Z tjr $"); 501590Srgrimes 511590Srgrimes/* 521590Srgrimes * look -- find lines in a sorted list. 538874Srgrimes * 541590Srgrimes * The man page said that TABs and SPACEs participate in -d comparisons. 551590Srgrimes * In fact, they were ignored. This implements historic practice, not 561590Srgrimes * the manual page. 571590Srgrimes */ 581590Srgrimes 591590Srgrimes#include <sys/types.h> 601590Srgrimes#include <sys/mman.h> 611590Srgrimes#include <sys/stat.h> 621590Srgrimes 6327623Scharnier#include <err.h> 641590Srgrimes#include <errno.h> 651590Srgrimes#include <fcntl.h> 6623693Speter#include <limits.h> 6727623Scharnier#include <locale.h> 681590Srgrimes#include <stdio.h> 691590Srgrimes#include <stdlib.h> 701590Srgrimes#include <string.h> 7123693Speter#include <unistd.h> 72132394Stjr#include <wchar.h> 73132394Stjr#include <wctype.h> 7423693Speter 751590Srgrimes#include "pathnames.h" 761590Srgrimes 7795646Smarkmstatic char _path_words[] = _PATH_WORDS; 7895646Smarkm 791590Srgrimes#define EQUAL 0 801590Srgrimes#define GREATER 1 811590Srgrimes#define LESS (-1) 821590Srgrimes 831590Srgrimesint dflag, fflag; 841590Srgrimes 85132394Stjrchar *binary_search(wchar_t *, unsigned char *, unsigned char *); 86132394Stjrint compare(wchar_t *, unsigned char *, unsigned char *); 87132394Stjrchar *linear_search(wchar_t *, unsigned char *, unsigned char *); 88132394Stjrint look(wchar_t *, unsigned char *, unsigned char *); 89132394Stjrwchar_t *prepkey(const char *, wchar_t); 90132394Stjrvoid print_from(wchar_t *, unsigned char *, unsigned char *); 911590Srgrimes 9292920Simpstatic void usage(void); 931590Srgrimes 9427623Scharnierint 95102944Sdwmalonemain(int argc, char *argv[]) 961590Srgrimes{ 971590Srgrimes struct stat sb; 98132394Stjr int ch, fd, match; 99132394Stjr wchar_t termchar; 100132394Stjr unsigned char *back, *front; 10187288Sdwmalone unsigned const char *file; 102132394Stjr wchar_t *key; 1031590Srgrimes 10411900Sache (void) setlocale(LC_CTYPE, ""); 10511900Sache 10695646Smarkm file = _path_words; 107132394Stjr termchar = L'\0'; 10824360Simp while ((ch = getopt(argc, argv, "dft:")) != -1) 1091590Srgrimes switch(ch) { 1101590Srgrimes case 'd': 1111590Srgrimes dflag = 1; 1121590Srgrimes break; 1131590Srgrimes case 'f': 1141590Srgrimes fflag = 1; 1151590Srgrimes break; 1161590Srgrimes case 't': 117132394Stjr if (mbrtowc(&termchar, optarg, MB_LEN_MAX, NULL) != 118132394Stjr strlen(optarg)) 119132394Stjr errx(2, "invalid termination character"); 1201590Srgrimes break; 1211590Srgrimes case '?': 1221590Srgrimes default: 1231590Srgrimes usage(); 1241590Srgrimes } 1251590Srgrimes argc -= optind; 1261590Srgrimes argv += optind; 1271590Srgrimes 12838701Swosch if (argc == 0) 12938701Swosch usage(); 13038701Swosch if (argc == 1) /* But set -df by default. */ 1311590Srgrimes dflag = fflag = 1; 132132394Stjr key = prepkey(*argv++, termchar); 13338701Swosch if (argc >= 2) 13438701Swosch file = *argv++; 1351590Srgrimes 13638701Swosch match = 1; 1371590Srgrimes 13838701Swosch do { 13938701Swosch if ((fd = open(file, O_RDONLY, 0)) < 0 || fstat(fd, &sb)) 14038701Swosch err(2, "%s", file); 14138701Swosch if (sb.st_size > SIZE_T_MAX) 14238701Swosch errx(2, "%s: %s", file, strerror(EFBIG)); 14338701Swosch if ((front = mmap(NULL, (size_t)sb.st_size, PROT_READ, MAP_SHARED, fd, (off_t)0)) == MAP_FAILED) 14438701Swosch err(2, "%s", file); 14538701Swosch back = front + sb.st_size; 146132394Stjr match *= (look(key, front, back)); 14738701Swosch close(fd); 14838701Swosch } while (argc-- > 2 && (file = *argv++)); 14938701Swosch 15038701Swosch exit(match); 1511590Srgrimes} 1521590Srgrimes 153132394Stjrwchar_t * 154132394Stjrprepkey(const char *string, wchar_t termchar) 1551590Srgrimes{ 156132394Stjr const char *readp; 157132394Stjr wchar_t *key, *writep; 158132394Stjr wchar_t ch; 159132394Stjr size_t clen; 1601590Srgrimes 161132394Stjr /* 162132394Stjr * Reformat search string and convert to wide character representation 163132394Stjr * to avoid doing it multiple times later. 164132394Stjr */ 165132394Stjr if ((key = malloc(sizeof(wchar_t) * (strlen(string) + 1))) == NULL) 166132394Stjr err(2, NULL); 167132394Stjr readp = string; 168132394Stjr writep = key; 169132394Stjr while ((clen = mbrtowc(&ch, readp, MB_LEN_MAX, NULL)) != 0) { 170132394Stjr if (clen == (size_t)-1 || clen == (size_t)-2) 171132394Stjr errc(2, EILSEQ, NULL); 1721590Srgrimes if (fflag) 173132394Stjr ch = towlower(ch); 174132394Stjr if (!dflag || iswalnum(ch)) 175132394Stjr *writep++ = ch; 176132394Stjr readp += clen; 1771590Srgrimes } 178132394Stjr *writep = L'\0'; 179132394Stjr if (termchar != L'\0' && (writep = wcschr(key, termchar)) != NULL) 180132394Stjr *++writep = L'\0'; 181132394Stjr return (key); 182132394Stjr} 1831590Srgrimes 184132394Stjrint 185132394Stjrlook(wchar_t *string, unsigned char *front, unsigned char *back) 186132394Stjr{ 187132394Stjr 1881590Srgrimes front = binary_search(string, front, back); 1891590Srgrimes front = linear_search(string, front, back); 1901590Srgrimes 1911590Srgrimes if (front) 1921590Srgrimes print_from(string, front, back); 1931590Srgrimes return (front ? 0 : 1); 1941590Srgrimes} 1951590Srgrimes 1961590Srgrimes 1971590Srgrimes/* 1981590Srgrimes * Binary search for "string" in memory between "front" and "back". 1998874Srgrimes * 2001590Srgrimes * This routine is expected to return a pointer to the start of a line at 2011590Srgrimes * *or before* the first word matching "string". Relaxing the constraint 2021590Srgrimes * this way simplifies the algorithm. 2038874Srgrimes * 2041590Srgrimes * Invariants: 2058874Srgrimes * front points to the beginning of a line at or before the first 2061590Srgrimes * matching string. 2078874Srgrimes * 2088874Srgrimes * back points to the beginning of a line at or after the first 2091590Srgrimes * matching line. 2108874Srgrimes * 2111590Srgrimes * Base of the Invariants. 2128874Srgrimes * front = NULL; 2131590Srgrimes * back = EOF; 2148874Srgrimes * 2151590Srgrimes * Advancing the Invariants: 2168874Srgrimes * 2171590Srgrimes * p = first newline after halfway point from front to back. 2188874Srgrimes * 2198874Srgrimes * If the string at "p" is not greater than the string to match, 2201590Srgrimes * p is the new front. Otherwise it is the new back. 2218874Srgrimes * 2221590Srgrimes * Termination: 2238874Srgrimes * 2248874Srgrimes * The definition of the routine allows it return at any point, 2251590Srgrimes * since front is always at or before the line to print. 2268874Srgrimes * 2278874Srgrimes * In fact, it returns when the chosen "p" equals "back". This 2288874Srgrimes * implies that there exists a string is least half as long as 2298874Srgrimes * (back - front), which in turn implies that a linear search will 2301590Srgrimes * be no more expensive than the cost of simply printing a string or two. 2318874Srgrimes * 2328874Srgrimes * Trying to continue with binary search at this point would be 2331590Srgrimes * more trouble than it's worth. 2341590Srgrimes */ 2351590Srgrimes#define SKIP_PAST_NEWLINE(p, back) \ 2361590Srgrimes while (p < back && *p++ != '\n'); 2371590Srgrimes 2381590Srgrimeschar * 239132394Stjrbinary_search(wchar_t *string, unsigned char *front, unsigned char *back) 2401590Srgrimes{ 241102944Sdwmalone unsigned char *p; 2421590Srgrimes 2431590Srgrimes p = front + (back - front) / 2; 2441590Srgrimes SKIP_PAST_NEWLINE(p, back); 2451590Srgrimes 2461590Srgrimes /* 2471590Srgrimes * If the file changes underneath us, make sure we don't 2481590Srgrimes * infinitely loop. 2491590Srgrimes */ 2501590Srgrimes while (p < back && back > front) { 2511590Srgrimes if (compare(string, p, back) == GREATER) 2521590Srgrimes front = p; 2531590Srgrimes else 2541590Srgrimes back = p; 2551590Srgrimes p = front + (back - front) / 2; 2561590Srgrimes SKIP_PAST_NEWLINE(p, back); 2571590Srgrimes } 2581590Srgrimes return (front); 2591590Srgrimes} 2601590Srgrimes 2611590Srgrimes/* 2621590Srgrimes * Find the first line that starts with string, linearly searching from front 2631590Srgrimes * to back. 2648874Srgrimes * 2651590Srgrimes * Return NULL for no such line. 2668874Srgrimes * 2671590Srgrimes * This routine assumes: 2688874Srgrimes * 2698874Srgrimes * o front points at the first character in a line. 2701590Srgrimes * o front is before or at the first line to be printed. 2711590Srgrimes */ 2721590Srgrimeschar * 273132394Stjrlinear_search(wchar_t *string, unsigned char *front, unsigned char *back) 2741590Srgrimes{ 2751590Srgrimes while (front < back) { 2761590Srgrimes switch (compare(string, front, back)) { 2771590Srgrimes case EQUAL: /* Found it. */ 2781590Srgrimes return (front); 2791590Srgrimes break; 2801590Srgrimes case LESS: /* No such string. */ 2811590Srgrimes return (NULL); 2821590Srgrimes break; 2831590Srgrimes case GREATER: /* Keep going. */ 2841590Srgrimes break; 2851590Srgrimes } 2861590Srgrimes SKIP_PAST_NEWLINE(front, back); 2871590Srgrimes } 2881590Srgrimes return (NULL); 2891590Srgrimes} 2901590Srgrimes 2911590Srgrimes/* 2921590Srgrimes * Print as many lines as match string, starting at front. 2931590Srgrimes */ 2948874Srgrimesvoid 295132394Stjrprint_from(wchar_t *string, unsigned char *front, unsigned char *back) 2961590Srgrimes{ 2971590Srgrimes for (; front < back && compare(string, front, back) == EQUAL; ++front) { 2981590Srgrimes for (; front < back && *front != '\n'; ++front) 2991590Srgrimes if (putchar(*front) == EOF) 30027623Scharnier err(2, "stdout"); 3011590Srgrimes if (putchar('\n') == EOF) 30227623Scharnier err(2, "stdout"); 3031590Srgrimes } 3041590Srgrimes} 3051590Srgrimes 3061590Srgrimes/* 3071590Srgrimes * Return LESS, GREATER, or EQUAL depending on how the string1 compares with 3081590Srgrimes * string2 (s1 ??? s2). 3098874Srgrimes * 3108874Srgrimes * o Matches up to len(s1) are EQUAL. 3111590Srgrimes * o Matches up to len(s2) are GREATER. 3128874Srgrimes * 3131590Srgrimes * Compare understands about the -f and -d flags, and treats comparisons 3141590Srgrimes * appropriately. 3158874Srgrimes * 3161590Srgrimes * The string "s1" is null terminated. The string s2 is '\n' terminated (or 3171590Srgrimes * "back" terminated). 3181590Srgrimes */ 3191590Srgrimesint 320132394Stjrcompare(wchar_t *s1, unsigned char *s2, unsigned char *back) 3211590Srgrimes{ 322132394Stjr wchar_t ch1, ch2; 323132394Stjr size_t len2; 3241590Srgrimes 325132394Stjr for (; *s1 && s2 < back && *s2 != '\n'; ++s1, s2 += len2) { 326132394Stjr ch1 = *s1; 327132394Stjr len2 = mbrtowc(&ch2, s2, back - s2, NULL); 328132394Stjr if (len2 == (size_t)-1 || len2 == (size_t)-2) { 329132394Stjr ch2 = *s2; 330132394Stjr len2 = 1; 331132394Stjr } 3321590Srgrimes if (fflag) 333132394Stjr ch2 = towlower(ch2); 334132394Stjr if (dflag && !iswalnum(ch2)) { 335132394Stjr /* Ignore character in comparison. */ 336132394Stjr --s1; 3371590Srgrimes continue; 3381590Srgrimes } 339132394Stjr if (ch1 != ch2) 340132394Stjr return (ch1 < ch2 ? LESS : GREATER); 3411590Srgrimes } 3421590Srgrimes return (*s1 ? GREATER : EQUAL); 3431590Srgrimes} 3441590Srgrimes 3451590Srgrimesstatic void 346102944Sdwmaloneusage(void) 3471590Srgrimes{ 34838701Swosch (void)fprintf(stderr, "usage: look [-df] [-t char] string [file ...]\n"); 3491590Srgrimes exit(2); 3501590Srgrimes} 351