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 /* 1999-02-22 Arkadiusz Miśkiewicz <misiek@pld.ORG.PL>
38 * - added Native Language Support
39 */
40
41 /*
42 * look -- find lines in a sorted list.
43 *
44 * The man page said that TABs and SPACEs participate in -d comparisons.
45 * In fact, they were ignored. This implements historic practice, not
46 * the manual page.
47 */
48
49 #include <sys/mman.h>
50 #include <sys/stat.h>
51 #include <errno.h>
52 #include <fcntl.h>
53 #include <stdio.h>
54 #include <stdlib.h>
55 #include <stddef.h>
56 #include <string.h>
57 #include <ctype.h>
58 #include <getopt.h>
59
60 #include "nls.h"
61 #include "xalloc.h"
62 #include "pathnames.h"
63 #include "closestream.h"
64
65 #define EQUAL 0
66 #define GREATER 1
67 #define LESS (-1)
68
69 static int dflag, fflag;
70 /* uglified the source a bit with globals, so that we only need
71 to allocate comparbuf once */
72 static int stringlen;
73 static char *string;
74 static char *comparbuf;
75
76 static char *binary_search (char *, char *);
77 static int compare (char *, char *);
78 static char *linear_search (char *, char *);
79 static int look (char *, char *);
80 static void print_from (char *, char *);
81 static void __attribute__((__noreturn__)) usage(void);
82
83 int
84 main(int argc, char *argv[])
85 {
86 struct stat sb;
87 int ch, fd, termchar;
88 char *back, *file, *front, *p;
89
90 static const struct option longopts[] = {
91 {"alternative", no_argument, NULL, 'a'},
92 {"alphanum", no_argument, NULL, 'd'},
93 {"ignore-case", no_argument, NULL, 'f'},
94 {"terminate", required_argument, NULL, 't'},
95 {"version", no_argument, NULL, 'V'},
96 {"help", no_argument, NULL, 'h'},
97 {NULL, 0, NULL, 0}
98 };
99
100 setlocale(LC_ALL, "");
101 bindtextdomain(PACKAGE, LOCALEDIR);
102 textdomain(PACKAGE);
103 close_stdout_atexit();
104
105 if ((file = getenv("WORDLIST")) && !access(file, R_OK))
106 /* use the WORDLIST */;
107 else
108 file = _PATH_WORDS;
109
110 termchar = '\0';
111 string = NULL; /* just for gcc */
112
113 while ((ch = getopt_long(argc, argv, "adft:Vh", longopts, NULL)) != -1)
114 switch(ch) {
115 case 'a':
116 file = _PATH_WORDS_ALT;
117 break;
118 case 'd':
119 dflag = 1;
120 break;
121 case 'f':
122 fflag = 1;
123 break;
124 case 't':
125 termchar = *optarg;
126 break;
127 case 'V':
128 print_version(EXIT_SUCCESS);
129 case 'h':
130 usage();
131 default:
132 errtryhelp(EXIT_FAILURE);
133 }
134 argc -= optind;
135 argv += optind;
136
137 switch (argc) {
138 case 2: /* Don't set -df for user. */
139 string = *argv++;
140 file = *argv;
141 break;
142 case 1: /* But set -df by default. */
143 dflag = fflag = 1;
144 string = *argv;
145 break;
146 default:
147 warnx(_("bad usage"));
148 errtryhelp(EXIT_FAILURE);
149 }
150
151 if (termchar != '\0' && (p = strchr(string, termchar)) != NULL)
152 *++p = '\0';
153
154 if ((fd = open(file, O_RDONLY, 0)) < 0 || fstat(fd, &sb))
155 err(EXIT_FAILURE, "%s", file);
156 front = mmap(NULL, (size_t) sb.st_size, PROT_READ,
157 MAP_SHARED, fd, (off_t) 0);
158 if
159 #ifdef MAP_FAILED
160 (front == MAP_FAILED)
161 #else
162 ((void *)(front) <= (void *)0)
163 #endif
164 err(EXIT_FAILURE, "%s", file);
165 back = front + sb.st_size;
166 return look(front, back);
167 }
168
169 static int
170 look(char *front, char *back)
171 {
172 int ch;
173 char *readp, *writep;
174
175 /* Reformat string to avoid doing it multiple times later. */
176 if (dflag) {
177 for (readp = writep = string; (ch = *readp++) != 0;) {
178 if (isalnum(ch) || isblank(ch))
179 *(writep++) = ch;
180 }
181 *writep = '\0';
182 stringlen = writep - string;
183 } else
184 stringlen = strlen(string);
185
186 comparbuf = xmalloc(stringlen+1);
187
188 front = binary_search(front, back);
189 front = linear_search(front, back);
190
191 if (front)
192 print_from(front, back);
193
194 free(comparbuf);
195
196 return (front ? 0 : 1);
197 }
198
199
200 /*
201 * Binary search for "string" in memory between "front" and "back".
202 *
203 * This routine is expected to return a pointer to the start of a line at
204 * *or before* the first word matching "string". Relaxing the constraint
205 * this way simplifies the algorithm.
206 *
207 * Invariants:
208 * front points to the beginning of a line at or before the first
209 * matching string.
210 *
211 * back points to the beginning of a line at or after the first
212 * matching line.
213 *
214 * Advancing the Invariants:
215 *
216 * p = first newline after halfway point from front to back.
217 *
218 * If the string at "p" is not greater than the string to match,
219 * p is the new front. Otherwise it is the new back.
220 *
221 * Termination:
222 *
223 * The definition of the routine allows it return at any point,
224 * since front is always at or before the line to print.
225 *
226 * In fact, it returns when the chosen "p" equals "back". This
227 * implies that there exists a string is least half as long as
228 * (back - front), which in turn implies that a linear search will
229 * be no more expensive than the cost of simply printing a string or two.
230 *
231 * Trying to continue with binary search at this point would be
232 * more trouble than it's worth.
233 */
234 #define SKIP_PAST_NEWLINE(p, back) \
235 while (p < back && *p++ != '\n')
236
237 static char *
238 binary_search(char *front, char *back)
239 {
240 char *p;
241
242 p = front + (back - front) / 2;
243 SKIP_PAST_NEWLINE(p, back);
244
245 /*
246 * If the file changes underneath us, make sure we don't
247 * infinitely loop.
248 */
249 while (p < back && back > front) {
250 if (compare(p, back) == GREATER)
251 front = p;
252 else
253 back = p;
254 p = front + (back - front) / 2;
255 SKIP_PAST_NEWLINE(p, back);
256 }
257 return (front);
258 }
259
260 /*
261 * Find the first line that starts with string, linearly searching from front
262 * to back.
263 *
264 * Return NULL for no such line.
265 *
266 * This routine assumes:
267 *
268 * o front points at the first character in a line.
269 * o front is before or at the first line to be printed.
270 */
271 static char *
272 linear_search(char *front, char *back)
273 {
274 while (front < back) {
275 switch (compare(front, back)) {
276 case EQUAL: /* Found it. */
277 return (front);
278 case LESS: /* No such string. */
279 return (NULL);
280 case GREATER: /* Keep going. */
281 break;
282 }
283 SKIP_PAST_NEWLINE(front, back);
284 }
285 return (NULL);
286 }
287
288 /*
289 * Print as many lines as match string, starting at front.
290 */
291 static void
292 print_from(char *front, char *back)
293 {
294 int eol;
295
296 while (front < back && compare(front, back) == EQUAL) {
297 if (compare(front, back) == EQUAL) {
298 eol = 0;
299 while (front < back && !eol) {
300 if (putchar(*front) == EOF)
301 err(EXIT_FAILURE, "stdout");
302 if (*front++ == '\n')
303 eol = 1;
304 }
305 } else
306 SKIP_PAST_NEWLINE(front, back);
307 }
308 }
309
310 /*
311 * Return LESS, GREATER, or EQUAL depending on how string compares with
312 * string2 (s1 ??? s2).
313 *
314 * o Matches up to len(s1) are EQUAL.
315 * o Matches up to len(s2) are GREATER.
316 *
317 * Compare understands about the -f and -d flags, and treats comparisons
318 * appropriately.
319 *
320 * The string "string" is null terminated. The string "s2" is '\n' terminated
321 * (or "s2end" terminated).
322 *
323 * We use strcasecmp etc, since it knows how to ignore case also
324 * in other locales.
325 */
326 static int
327 compare(char *s2, char *s2end) {
328 int i;
329 char *p;
330
331 /* copy, ignoring things that should be ignored */
332 p = comparbuf;
333 i = stringlen;
334 while(s2 < s2end && *s2 != '\n' && i) {
335 if (!dflag || isalnum(*s2) || isblank(*s2))
336 {
337 *p++ = *s2;
338 i--;
339 }
340 s2++;
341 }
342 *p = 0;
343
344 /* and compare */
345 if (fflag)
346 i = strncasecmp(comparbuf, string, stringlen);
347 else
348 i = strncmp(comparbuf, string, stringlen);
349
350 return ((i > 0) ? LESS : (i < 0) ? GREATER : EQUAL);
351 }
352
353 static void __attribute__((__noreturn__)) usage(void)
354 {
355 FILE *out = stdout;
356 fputs(USAGE_HEADER, out);
357 fprintf(out, _(" %s [options] <string> [<file>...]\n"), program_invocation_short_name);
358
359 fputs(USAGE_SEPARATOR, out);
360 fputs(_("Display lines beginning with a specified string.\n"), out);
361
362 fputs(USAGE_OPTIONS, out);
363 fputs(_(" -a, --alternative use the alternative dictionary\n"), out);
364 fputs(_(" -d, --alphanum compare only blanks and alphanumeric characters\n"), out);
365 fputs(_(" -f, --ignore-case ignore case differences when comparing\n"), out);
366 fputs(_(" -t, --terminate <char> define the string-termination character\n"), out);
367
368 fputs(USAGE_SEPARATOR, out);
369 printf(USAGE_HELP_OPTIONS(26));
370 printf(USAGE_MAN_TAIL("look(1)"));
371
372 exit(EXIT_SUCCESS);
373 }