19b50d902SRodney W. Grimes /*- 28a16b7a1SPedro F. Giffuni * SPDX-License-Identifier: BSD-3-Clause 38a16b7a1SPedro F. Giffuni * 49b50d902SRodney W. Grimes * Copyright (c) 1991, 1993 59b50d902SRodney W. Grimes * The Regents of the University of California. All rights reserved. 69b50d902SRodney W. Grimes * 79b50d902SRodney W. Grimes * This code is derived from software contributed to Berkeley by 89b50d902SRodney W. Grimes * David Hitz of Auspex Systems, Inc. 99b50d902SRodney W. Grimes * 109b50d902SRodney W. Grimes * Redistribution and use in source and binary forms, with or without 119b50d902SRodney W. Grimes * modification, are permitted provided that the following conditions 129b50d902SRodney W. Grimes * are met: 139b50d902SRodney W. Grimes * 1. Redistributions of source code must retain the above copyright 149b50d902SRodney W. Grimes * notice, this list of conditions and the following disclaimer. 159b50d902SRodney W. Grimes * 2. Redistributions in binary form must reproduce the above copyright 169b50d902SRodney W. Grimes * notice, this list of conditions and the following disclaimer in the 179b50d902SRodney W. Grimes * documentation and/or other materials provided with the distribution. 18fbbd9655SWarner Losh * 3. Neither the name of the University nor the names of its contributors 199b50d902SRodney W. Grimes * may be used to endorse or promote products derived from this software 209b50d902SRodney W. Grimes * without specific prior written permission. 219b50d902SRodney W. Grimes * 229b50d902SRodney W. Grimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 239b50d902SRodney W. Grimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 249b50d902SRodney W. Grimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 259b50d902SRodney W. Grimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 269b50d902SRodney W. Grimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 279b50d902SRodney W. Grimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 289b50d902SRodney W. Grimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 299b50d902SRodney W. Grimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 309b50d902SRodney W. Grimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 319b50d902SRodney W. Grimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 329b50d902SRodney W. Grimes * SUCH DAMAGE. 339b50d902SRodney W. Grimes */ 349b50d902SRodney W. Grimes 359b50d902SRodney W. Grimes #ifndef lint 369baefe4aSPhilippe Charnier static const char copyright[] = 379b50d902SRodney W. Grimes "@(#) Copyright (c) 1991, 1993\n\ 389b50d902SRodney W. Grimes The Regents of the University of California. All rights reserved.\n"; 399b50d902SRodney W. Grimes #endif /* not lint */ 409b50d902SRodney W. Grimes 419b50d902SRodney W. Grimes #ifndef lint 429baefe4aSPhilippe Charnier #if 0 43df3f5d9dSPeter Wemm static char sccsid[] = "@(#)look.c 8.2 (Berkeley) 5/4/95"; 449baefe4aSPhilippe Charnier #endif 459b50d902SRodney W. Grimes #endif /* not lint */ 46e026a48cSDavid E. O'Brien #include <sys/cdefs.h> 47e026a48cSDavid E. O'Brien __FBSDID("$FreeBSD$"); 489b50d902SRodney W. Grimes 499b50d902SRodney W. Grimes /* 509b50d902SRodney W. Grimes * look -- find lines in a sorted list. 519b50d902SRodney W. Grimes * 529b50d902SRodney W. Grimes * The man page said that TABs and SPACEs participate in -d comparisons. 539b50d902SRodney W. Grimes * In fact, they were ignored. This implements historic practice, not 549b50d902SRodney W. Grimes * the manual page. 559b50d902SRodney W. Grimes */ 569b50d902SRodney W. Grimes 579b50d902SRodney W. Grimes #include <sys/types.h> 589b50d902SRodney W. Grimes #include <sys/mman.h> 599b50d902SRodney W. Grimes #include <sys/stat.h> 609b50d902SRodney W. Grimes 619baefe4aSPhilippe Charnier #include <err.h> 629b50d902SRodney W. Grimes #include <errno.h> 639b50d902SRodney W. Grimes #include <fcntl.h> 64b5bb9538SEitan Adler #include <getopt.h> 65df3f5d9dSPeter Wemm #include <limits.h> 669baefe4aSPhilippe Charnier #include <locale.h> 67d13b008dSEd Schouten #include <stdint.h> 682a5e51faSEd Schouten #include <stdio.h> 699b50d902SRodney W. Grimes #include <stdlib.h> 709b50d902SRodney W. Grimes #include <string.h> 71df3f5d9dSPeter Wemm #include <unistd.h> 72d67148e4STim J. Robbins #include <wchar.h> 73d67148e4STim J. Robbins #include <wctype.h> 74df3f5d9dSPeter Wemm 759b50d902SRodney W. Grimes #include "pathnames.h" 769b50d902SRodney W. Grimes 779e5ff032SMark Murray static char _path_words[] = _PATH_WORDS; 789e5ff032SMark Murray 799b50d902SRodney W. Grimes #define EQUAL 0 809b50d902SRodney W. Grimes #define GREATER 1 819b50d902SRodney W. Grimes #define LESS (-1) 829b50d902SRodney W. Grimes 8376de4396SEd Schouten static int dflag, fflag; 849b50d902SRodney W. Grimes 8576de4396SEd Schouten static char *binary_search(wchar_t *, unsigned char *, unsigned char *); 8676de4396SEd Schouten static int compare(wchar_t *, unsigned char *, unsigned char *); 8776de4396SEd Schouten static char *linear_search(wchar_t *, unsigned char *, unsigned char *); 8876de4396SEd Schouten static int look(wchar_t *, unsigned char *, unsigned char *); 8976de4396SEd Schouten static wchar_t *prepkey(const char *, wchar_t); 9076de4396SEd Schouten static void print_from(wchar_t *, unsigned char *, unsigned char *); 919b50d902SRodney W. Grimes 92*a1b6427aSAlfonso Gregory static void usage(void) __dead2; 939b50d902SRodney W. Grimes 94b5bb9538SEitan Adler static struct option longopts[] = { 95b5bb9538SEitan Adler { "alternative",no_argument, NULL, 'a' }, 96b5bb9538SEitan Adler { "alphanum", no_argument, NULL, 'd' }, 97b5bb9538SEitan Adler { "ignore-case",no_argument, NULL, 'i' }, 98b5bb9538SEitan Adler { "terminate", required_argument, NULL, 't'}, 99b5bb9538SEitan Adler { NULL, 0, NULL, 0 }, 100b5bb9538SEitan Adler }; 101b5bb9538SEitan Adler 1029baefe4aSPhilippe Charnier int 103f4ac32deSDavid Malone main(int argc, char *argv[]) 1049b50d902SRodney W. Grimes { 1059b50d902SRodney W. Grimes struct stat sb; 106d67148e4STim J. Robbins int ch, fd, match; 107d67148e4STim J. Robbins wchar_t termchar; 108d67148e4STim J. Robbins unsigned char *back, *front; 109106b1a8cSDavid Malone unsigned const char *file; 110d67148e4STim J. Robbins wchar_t *key; 111ac7154f5SAndrey A. Chernov 112ac7154f5SAndrey A. Chernov (void) setlocale(LC_CTYPE, ""); 1139b50d902SRodney W. Grimes 1149e5ff032SMark Murray file = _path_words; 115d67148e4STim J. Robbins termchar = L'\0'; 116b5bb9538SEitan Adler while ((ch = getopt_long(argc, argv, "+adft:", longopts, NULL)) != -1) 1179b50d902SRodney W. Grimes switch(ch) { 118b245fc98SEitan Adler case 'a': 119b245fc98SEitan Adler /* COMPATIBILITY */ 120b245fc98SEitan Adler break; 1219b50d902SRodney W. Grimes case 'd': 1229b50d902SRodney W. Grimes dflag = 1; 1239b50d902SRodney W. Grimes break; 1249b50d902SRodney W. Grimes case 'f': 1259b50d902SRodney W. Grimes fflag = 1; 1269b50d902SRodney W. Grimes break; 1279b50d902SRodney W. Grimes case 't': 128d67148e4STim J. Robbins if (mbrtowc(&termchar, optarg, MB_LEN_MAX, NULL) != 129d67148e4STim J. Robbins strlen(optarg)) 130d67148e4STim J. Robbins errx(2, "invalid termination character"); 1319b50d902SRodney W. Grimes break; 1329b50d902SRodney W. Grimes case '?': 1339b50d902SRodney W. Grimes default: 1349b50d902SRodney W. Grimes usage(); 1359b50d902SRodney W. Grimes } 1369b50d902SRodney W. Grimes argc -= optind; 1379b50d902SRodney W. Grimes argv += optind; 1389b50d902SRodney W. Grimes 1394d3ee609SWolfram Schneider if (argc == 0) 1409b50d902SRodney W. Grimes usage(); 1414d3ee609SWolfram Schneider if (argc == 1) /* But set -df by default. */ 1424d3ee609SWolfram Schneider dflag = fflag = 1; 143d67148e4STim J. Robbins key = prepkey(*argv++, termchar); 1444d3ee609SWolfram Schneider if (argc >= 2) 1454d3ee609SWolfram Schneider file = *argv++; 1469b50d902SRodney W. Grimes 1474d3ee609SWolfram Schneider match = 1; 1489b50d902SRodney W. Grimes 1494d3ee609SWolfram Schneider do { 1509b50d902SRodney W. Grimes if ((fd = open(file, O_RDONLY, 0)) < 0 || fstat(fd, &sb)) 1519baefe4aSPhilippe Charnier err(2, "%s", file); 152d2ea3bedSEd Schouten if ((uintmax_t)sb.st_size > (uintmax_t)SIZE_T_MAX) 1539baefe4aSPhilippe Charnier errx(2, "%s: %s", file, strerror(EFBIG)); 154f9f23184SColin Percival if (sb.st_size == 0) { 155f9f23184SColin Percival close(fd); 156f9f23184SColin Percival continue; 157f9f23184SColin Percival } 1584d3ee609SWolfram Schneider if ((front = mmap(NULL, (size_t)sb.st_size, PROT_READ, MAP_SHARED, fd, (off_t)0)) == MAP_FAILED) 1599baefe4aSPhilippe Charnier err(2, "%s", file); 1609b50d902SRodney W. Grimes back = front + sb.st_size; 161d67148e4STim J. Robbins match *= (look(key, front, back)); 1624d3ee609SWolfram Schneider close(fd); 1634d3ee609SWolfram Schneider } while (argc-- > 2 && (file = *argv++)); 1644d3ee609SWolfram Schneider 1654d3ee609SWolfram Schneider exit(match); 1669b50d902SRodney W. Grimes } 1679b50d902SRodney W. Grimes 16876de4396SEd Schouten static wchar_t * 169d67148e4STim J. Robbins prepkey(const char *string, wchar_t termchar) 1709b50d902SRodney W. Grimes { 171d67148e4STim J. Robbins const char *readp; 172d67148e4STim J. Robbins wchar_t *key, *writep; 173d67148e4STim J. Robbins wchar_t ch; 174d67148e4STim J. Robbins size_t clen; 1759b50d902SRodney W. Grimes 176d67148e4STim J. Robbins /* 177d67148e4STim J. Robbins * Reformat search string and convert to wide character representation 178d67148e4STim J. Robbins * to avoid doing it multiple times later. 179d67148e4STim J. Robbins */ 180d67148e4STim J. Robbins if ((key = malloc(sizeof(wchar_t) * (strlen(string) + 1))) == NULL) 181d67148e4STim J. Robbins err(2, NULL); 182d67148e4STim J. Robbins readp = string; 183d67148e4STim J. Robbins writep = key; 184d67148e4STim J. Robbins while ((clen = mbrtowc(&ch, readp, MB_LEN_MAX, NULL)) != 0) { 185d67148e4STim J. Robbins if (clen == (size_t)-1 || clen == (size_t)-2) 186d67148e4STim J. Robbins errc(2, EILSEQ, NULL); 1879b50d902SRodney W. Grimes if (fflag) 188d67148e4STim J. Robbins ch = towlower(ch); 189d67148e4STim J. Robbins if (!dflag || iswalnum(ch)) 190d67148e4STim J. Robbins *writep++ = ch; 191d67148e4STim J. Robbins readp += clen; 1929b50d902SRodney W. Grimes } 193d67148e4STim J. Robbins *writep = L'\0'; 194d67148e4STim J. Robbins if (termchar != L'\0' && (writep = wcschr(key, termchar)) != NULL) 195d67148e4STim J. Robbins *++writep = L'\0'; 196d67148e4STim J. Robbins return (key); 197d67148e4STim J. Robbins } 198d67148e4STim J. Robbins 19976de4396SEd Schouten static int 200d67148e4STim J. Robbins look(wchar_t *string, unsigned char *front, unsigned char *back) 201d67148e4STim J. Robbins { 2029b50d902SRodney W. Grimes 2039b50d902SRodney W. Grimes front = binary_search(string, front, back); 2049b50d902SRodney W. Grimes front = linear_search(string, front, back); 2059b50d902SRodney W. Grimes 2069b50d902SRodney W. Grimes if (front) 2079b50d902SRodney W. Grimes print_from(string, front, back); 2089b50d902SRodney W. Grimes return (front ? 0 : 1); 2099b50d902SRodney W. Grimes } 2109b50d902SRodney W. Grimes 2119b50d902SRodney W. Grimes 2129b50d902SRodney W. Grimes /* 2139b50d902SRodney W. Grimes * Binary search for "string" in memory between "front" and "back". 2149b50d902SRodney W. Grimes * 2159b50d902SRodney W. Grimes * This routine is expected to return a pointer to the start of a line at 2169b50d902SRodney W. Grimes * *or before* the first word matching "string". Relaxing the constraint 2179b50d902SRodney W. Grimes * this way simplifies the algorithm. 2189b50d902SRodney W. Grimes * 2199b50d902SRodney W. Grimes * Invariants: 2209b50d902SRodney W. Grimes * front points to the beginning of a line at or before the first 2219b50d902SRodney W. Grimes * matching string. 2229b50d902SRodney W. Grimes * 2239b50d902SRodney W. Grimes * back points to the beginning of a line at or after the first 2249b50d902SRodney W. Grimes * matching line. 2259b50d902SRodney W. Grimes * 2269b50d902SRodney W. Grimes * Base of the Invariants. 2279b50d902SRodney W. Grimes * front = NULL; 2289b50d902SRodney W. Grimes * back = EOF; 2299b50d902SRodney W. Grimes * 2309b50d902SRodney W. Grimes * Advancing the Invariants: 2319b50d902SRodney W. Grimes * 2329b50d902SRodney W. Grimes * p = first newline after halfway point from front to back. 2339b50d902SRodney W. Grimes * 2349b50d902SRodney W. Grimes * If the string at "p" is not greater than the string to match, 2359b50d902SRodney W. Grimes * p is the new front. Otherwise it is the new back. 2369b50d902SRodney W. Grimes * 2379b50d902SRodney W. Grimes * Termination: 2389b50d902SRodney W. Grimes * 2399b50d902SRodney W. Grimes * The definition of the routine allows it return at any point, 2409b50d902SRodney W. Grimes * since front is always at or before the line to print. 2419b50d902SRodney W. Grimes * 2429b50d902SRodney W. Grimes * In fact, it returns when the chosen "p" equals "back". This 2439b50d902SRodney W. Grimes * implies that there exists a string is least half as long as 2449b50d902SRodney W. Grimes * (back - front), which in turn implies that a linear search will 2459b50d902SRodney W. Grimes * be no more expensive than the cost of simply printing a string or two. 2469b50d902SRodney W. Grimes * 2479b50d902SRodney W. Grimes * Trying to continue with binary search at this point would be 2489b50d902SRodney W. Grimes * more trouble than it's worth. 2499b50d902SRodney W. Grimes */ 2509b50d902SRodney W. Grimes #define SKIP_PAST_NEWLINE(p, back) \ 2519b50d902SRodney W. Grimes while (p < back && *p++ != '\n'); 2529b50d902SRodney W. Grimes 25376de4396SEd Schouten static char * 254d67148e4STim J. Robbins binary_search(wchar_t *string, unsigned char *front, unsigned char *back) 2559b50d902SRodney W. Grimes { 256f4ac32deSDavid Malone unsigned char *p; 2579b50d902SRodney W. Grimes 2589b50d902SRodney W. Grimes p = front + (back - front) / 2; 2599b50d902SRodney W. Grimes SKIP_PAST_NEWLINE(p, back); 2609b50d902SRodney W. Grimes 2619b50d902SRodney W. Grimes /* 2629b50d902SRodney W. Grimes * If the file changes underneath us, make sure we don't 2639b50d902SRodney W. Grimes * infinitely loop. 2649b50d902SRodney W. Grimes */ 2659b50d902SRodney W. Grimes while (p < back && back > front) { 2669b50d902SRodney W. Grimes if (compare(string, p, back) == GREATER) 2679b50d902SRodney W. Grimes front = p; 2689b50d902SRodney W. Grimes else 2699b50d902SRodney W. Grimes back = p; 2709b50d902SRodney W. Grimes p = front + (back - front) / 2; 2719b50d902SRodney W. Grimes SKIP_PAST_NEWLINE(p, back); 2729b50d902SRodney W. Grimes } 2739b50d902SRodney W. Grimes return (front); 2749b50d902SRodney W. Grimes } 2759b50d902SRodney W. Grimes 2769b50d902SRodney W. Grimes /* 2779b50d902SRodney W. Grimes * Find the first line that starts with string, linearly searching from front 2789b50d902SRodney W. Grimes * to back. 2799b50d902SRodney W. Grimes * 2809b50d902SRodney W. Grimes * Return NULL for no such line. 2819b50d902SRodney W. Grimes * 2829b50d902SRodney W. Grimes * This routine assumes: 2839b50d902SRodney W. Grimes * 2849b50d902SRodney W. Grimes * o front points at the first character in a line. 2859b50d902SRodney W. Grimes * o front is before or at the first line to be printed. 2869b50d902SRodney W. Grimes */ 28776de4396SEd Schouten static char * 288d67148e4STim J. Robbins linear_search(wchar_t *string, unsigned char *front, unsigned char *back) 2899b50d902SRodney W. Grimes { 2909b50d902SRodney W. Grimes while (front < back) { 2919b50d902SRodney W. Grimes switch (compare(string, front, back)) { 2929b50d902SRodney W. Grimes case EQUAL: /* Found it. */ 2939b50d902SRodney W. Grimes return (front); 2949b50d902SRodney W. Grimes case LESS: /* No such string. */ 2959b50d902SRodney W. Grimes return (NULL); 2969b50d902SRodney W. Grimes case GREATER: /* Keep going. */ 2979b50d902SRodney W. Grimes break; 2989b50d902SRodney W. Grimes } 2999b50d902SRodney W. Grimes SKIP_PAST_NEWLINE(front, back); 3009b50d902SRodney W. Grimes } 3019b50d902SRodney W. Grimes return (NULL); 3029b50d902SRodney W. Grimes } 3039b50d902SRodney W. Grimes 3049b50d902SRodney W. Grimes /* 3059b50d902SRodney W. Grimes * Print as many lines as match string, starting at front. 3069b50d902SRodney W. Grimes */ 30776de4396SEd Schouten static void 308d67148e4STim J. Robbins print_from(wchar_t *string, unsigned char *front, unsigned char *back) 3099b50d902SRodney W. Grimes { 3109b50d902SRodney W. Grimes for (; front < back && compare(string, front, back) == EQUAL; ++front) { 3119b50d902SRodney W. Grimes for (; front < back && *front != '\n'; ++front) 3129b50d902SRodney W. Grimes if (putchar(*front) == EOF) 3139baefe4aSPhilippe Charnier err(2, "stdout"); 3149b50d902SRodney W. Grimes if (putchar('\n') == EOF) 3159baefe4aSPhilippe Charnier err(2, "stdout"); 3169b50d902SRodney W. Grimes } 3179b50d902SRodney W. Grimes } 3189b50d902SRodney W. Grimes 3199b50d902SRodney W. Grimes /* 3209b50d902SRodney W. Grimes * Return LESS, GREATER, or EQUAL depending on how the string1 compares with 3219b50d902SRodney W. Grimes * string2 (s1 ??? s2). 3229b50d902SRodney W. Grimes * 3239b50d902SRodney W. Grimes * o Matches up to len(s1) are EQUAL. 3249b50d902SRodney W. Grimes * o Matches up to len(s2) are GREATER. 3259b50d902SRodney W. Grimes * 3269b50d902SRodney W. Grimes * Compare understands about the -f and -d flags, and treats comparisons 3279b50d902SRodney W. Grimes * appropriately. 3289b50d902SRodney W. Grimes * 3299b50d902SRodney W. Grimes * The string "s1" is null terminated. The string s2 is '\n' terminated (or 3309b50d902SRodney W. Grimes * "back" terminated). 3319b50d902SRodney W. Grimes */ 33276de4396SEd Schouten static int 333d67148e4STim J. Robbins compare(wchar_t *s1, unsigned char *s2, unsigned char *back) 3349b50d902SRodney W. Grimes { 335d67148e4STim J. Robbins wchar_t ch1, ch2; 336d67148e4STim J. Robbins size_t len2; 3379b50d902SRodney W. Grimes 338d67148e4STim J. Robbins for (; *s1 && s2 < back && *s2 != '\n'; ++s1, s2 += len2) { 339d67148e4STim J. Robbins ch1 = *s1; 340d67148e4STim J. Robbins len2 = mbrtowc(&ch2, s2, back - s2, NULL); 341d67148e4STim J. Robbins if (len2 == (size_t)-1 || len2 == (size_t)-2) { 342d67148e4STim J. Robbins ch2 = *s2; 343d67148e4STim J. Robbins len2 = 1; 344d67148e4STim J. Robbins } 3459b50d902SRodney W. Grimes if (fflag) 346d67148e4STim J. Robbins ch2 = towlower(ch2); 347d67148e4STim J. Robbins if (dflag && !iswalnum(ch2)) { 348d67148e4STim J. Robbins /* Ignore character in comparison. */ 349d67148e4STim J. Robbins --s1; 3509b50d902SRodney W. Grimes continue; 3519b50d902SRodney W. Grimes } 352d67148e4STim J. Robbins if (ch1 != ch2) 353d67148e4STim J. Robbins return (ch1 < ch2 ? LESS : GREATER); 3549b50d902SRodney W. Grimes } 3559b50d902SRodney W. Grimes return (*s1 ? GREATER : EQUAL); 3569b50d902SRodney W. Grimes } 3579b50d902SRodney W. Grimes 3589b50d902SRodney W. Grimes static void 359f4ac32deSDavid Malone usage(void) 3609b50d902SRodney W. Grimes { 3614d3ee609SWolfram Schneider (void)fprintf(stderr, "usage: look [-df] [-t char] string [file ...]\n"); 3629b50d902SRodney W. Grimes exit(2); 3639b50d902SRodney W. Grimes } 364