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 * 4. Neither the name of the University nor the names of its contributors 171590Srgrimes * may be used to endorse or promote products derived from this software 181590Srgrimes * without specific prior written permission. 191590Srgrimes * 201590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301590Srgrimes * SUCH DAMAGE. 311590Srgrimes */ 321590Srgrimes 331590Srgrimes#ifndef lint 3427623Scharnierstatic const char copyright[] = 351590Srgrimes"@(#) Copyright (c) 1991, 1993\n\ 361590Srgrimes The Regents of the University of California. All rights reserved.\n"; 371590Srgrimes#endif /* not lint */ 381590Srgrimes 391590Srgrimes#ifndef lint 4027623Scharnier#if 0 4123693Speterstatic char sccsid[] = "@(#)look.c 8.2 (Berkeley) 5/4/95"; 4227623Scharnier#endif 431590Srgrimes#endif /* not lint */ 4499112Sobrien#include <sys/cdefs.h> 4599112Sobrien__FBSDID("$FreeBSD$"); 461590Srgrimes 471590Srgrimes/* 481590Srgrimes * look -- find lines in a sorted list. 498874Srgrimes * 501590Srgrimes * The man page said that TABs and SPACEs participate in -d comparisons. 511590Srgrimes * In fact, they were ignored. This implements historic practice, not 521590Srgrimes * the manual page. 531590Srgrimes */ 541590Srgrimes 551590Srgrimes#include <sys/types.h> 561590Srgrimes#include <sys/mman.h> 571590Srgrimes#include <sys/stat.h> 581590Srgrimes 5927623Scharnier#include <err.h> 601590Srgrimes#include <errno.h> 611590Srgrimes#include <fcntl.h> 6223693Speter#include <limits.h> 6327623Scharnier#include <locale.h> 641590Srgrimes#include <stdio.h> 651590Srgrimes#include <stdlib.h> 661590Srgrimes#include <string.h> 6723693Speter#include <unistd.h> 68132394Stjr#include <wchar.h> 69132394Stjr#include <wctype.h> 7023693Speter 711590Srgrimes#include "pathnames.h" 721590Srgrimes 7395646Smarkmstatic char _path_words[] = _PATH_WORDS; 7495646Smarkm 751590Srgrimes#define EQUAL 0 761590Srgrimes#define GREATER 1 771590Srgrimes#define LESS (-1) 781590Srgrimes 791590Srgrimesint dflag, fflag; 801590Srgrimes 81132394Stjrchar *binary_search(wchar_t *, unsigned char *, unsigned char *); 82132394Stjrint compare(wchar_t *, unsigned char *, unsigned char *); 83132394Stjrchar *linear_search(wchar_t *, unsigned char *, unsigned char *); 84132394Stjrint look(wchar_t *, unsigned char *, unsigned char *); 85132394Stjrwchar_t *prepkey(const char *, wchar_t); 86132394Stjrvoid print_from(wchar_t *, unsigned char *, unsigned char *); 871590Srgrimes 8892920Simpstatic void usage(void); 891590Srgrimes 9027623Scharnierint 91102944Sdwmalonemain(int argc, char *argv[]) 921590Srgrimes{ 931590Srgrimes struct stat sb; 94132394Stjr int ch, fd, match; 95132394Stjr wchar_t termchar; 96132394Stjr unsigned char *back, *front; 9787288Sdwmalone unsigned const char *file; 98132394Stjr wchar_t *key; 991590Srgrimes 10011900Sache (void) setlocale(LC_CTYPE, ""); 10111900Sache 10295646Smarkm file = _path_words; 103132394Stjr termchar = L'\0'; 10424360Simp while ((ch = getopt(argc, argv, "dft:")) != -1) 1051590Srgrimes switch(ch) { 1061590Srgrimes case 'd': 1071590Srgrimes dflag = 1; 1081590Srgrimes break; 1091590Srgrimes case 'f': 1101590Srgrimes fflag = 1; 1111590Srgrimes break; 1121590Srgrimes case 't': 113132394Stjr if (mbrtowc(&termchar, optarg, MB_LEN_MAX, NULL) != 114132394Stjr strlen(optarg)) 115132394Stjr errx(2, "invalid termination character"); 1161590Srgrimes break; 1171590Srgrimes case '?': 1181590Srgrimes default: 1191590Srgrimes usage(); 1201590Srgrimes } 1211590Srgrimes argc -= optind; 1221590Srgrimes argv += optind; 1231590Srgrimes 12438701Swosch if (argc == 0) 12538701Swosch usage(); 12638701Swosch if (argc == 1) /* But set -df by default. */ 1271590Srgrimes dflag = fflag = 1; 128132394Stjr key = prepkey(*argv++, termchar); 12938701Swosch if (argc >= 2) 13038701Swosch file = *argv++; 1311590Srgrimes 13238701Swosch match = 1; 1331590Srgrimes 13438701Swosch do { 13538701Swosch if ((fd = open(file, O_RDONLY, 0)) < 0 || fstat(fd, &sb)) 13638701Swosch err(2, "%s", file); 13738701Swosch if (sb.st_size > SIZE_T_MAX) 13838701Swosch errx(2, "%s: %s", file, strerror(EFBIG)); 139196558Scperciva if (sb.st_size == 0) { 140196558Scperciva close(fd); 141196558Scperciva continue; 142196558Scperciva } 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 case LESS: /* No such string. */ 2801590Srgrimes return (NULL); 2811590Srgrimes case GREATER: /* Keep going. */ 2821590Srgrimes break; 2831590Srgrimes } 2841590Srgrimes SKIP_PAST_NEWLINE(front, back); 2851590Srgrimes } 2861590Srgrimes return (NULL); 2871590Srgrimes} 2881590Srgrimes 2891590Srgrimes/* 2901590Srgrimes * Print as many lines as match string, starting at front. 2911590Srgrimes */ 2928874Srgrimesvoid 293132394Stjrprint_from(wchar_t *string, unsigned char *front, unsigned char *back) 2941590Srgrimes{ 2951590Srgrimes for (; front < back && compare(string, front, back) == EQUAL; ++front) { 2961590Srgrimes for (; front < back && *front != '\n'; ++front) 2971590Srgrimes if (putchar(*front) == EOF) 29827623Scharnier err(2, "stdout"); 2991590Srgrimes if (putchar('\n') == EOF) 30027623Scharnier err(2, "stdout"); 3011590Srgrimes } 3021590Srgrimes} 3031590Srgrimes 3041590Srgrimes/* 3051590Srgrimes * Return LESS, GREATER, or EQUAL depending on how the string1 compares with 3061590Srgrimes * string2 (s1 ??? s2). 3078874Srgrimes * 3088874Srgrimes * o Matches up to len(s1) are EQUAL. 3091590Srgrimes * o Matches up to len(s2) are GREATER. 3108874Srgrimes * 3111590Srgrimes * Compare understands about the -f and -d flags, and treats comparisons 3121590Srgrimes * appropriately. 3138874Srgrimes * 3141590Srgrimes * The string "s1" is null terminated. The string s2 is '\n' terminated (or 3151590Srgrimes * "back" terminated). 3161590Srgrimes */ 3171590Srgrimesint 318132394Stjrcompare(wchar_t *s1, unsigned char *s2, unsigned char *back) 3191590Srgrimes{ 320132394Stjr wchar_t ch1, ch2; 321132394Stjr size_t len2; 3221590Srgrimes 323132394Stjr for (; *s1 && s2 < back && *s2 != '\n'; ++s1, s2 += len2) { 324132394Stjr ch1 = *s1; 325132394Stjr len2 = mbrtowc(&ch2, s2, back - s2, NULL); 326132394Stjr if (len2 == (size_t)-1 || len2 == (size_t)-2) { 327132394Stjr ch2 = *s2; 328132394Stjr len2 = 1; 329132394Stjr } 3301590Srgrimes if (fflag) 331132394Stjr ch2 = towlower(ch2); 332132394Stjr if (dflag && !iswalnum(ch2)) { 333132394Stjr /* Ignore character in comparison. */ 334132394Stjr --s1; 3351590Srgrimes continue; 3361590Srgrimes } 337132394Stjr if (ch1 != ch2) 338132394Stjr return (ch1 < ch2 ? LESS : GREATER); 3391590Srgrimes } 3401590Srgrimes return (*s1 ? GREATER : EQUAL); 3411590Srgrimes} 3421590Srgrimes 3431590Srgrimesstatic void 344102944Sdwmaloneusage(void) 3451590Srgrimes{ 34638701Swosch (void)fprintf(stderr, "usage: look [-df] [-t char] string [file ...]\n"); 3471590Srgrimes exit(2); 3481590Srgrimes} 349