]>
Commit | Line | Data |
---|---|---|
6dbe3af9 KZ |
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 | ||
b50945d4 | 37 | /* 1999-02-22 Arkadiusz MiĆkiewicz <misiek@pld.ORG.PL> |
7eda085c KZ |
38 | * - added Native Language Support |
39 | */ | |
40 | ||
6dbe3af9 KZ |
41 | /* |
42 | * look -- find lines in a sorted list. | |
429ee997 | 43 | * |
6dbe3af9 KZ |
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 | ||
6dbe3af9 KZ |
49 | #include <sys/mman.h> |
50 | #include <sys/stat.h> | |
6dbe3af9 KZ |
51 | #include <errno.h> |
52 | #include <fcntl.h> | |
53 | #include <stdio.h> | |
54 | #include <stdlib.h> | |
a35f7505 | 55 | #include <stddef.h> |
6dbe3af9 KZ |
56 | #include <string.h> |
57 | #include <ctype.h> | |
58 | #include <getopt.h> | |
026ed2ce | 59 | |
7eda085c | 60 | #include "nls.h" |
026ed2ce DB |
61 | #include "xalloc.h" |
62 | #include "pathnames.h" | |
c05a80ca | 63 | #include "closestream.h" |
6dbe3af9 | 64 | |
6dbe3af9 KZ |
65 | #define EQUAL 0 |
66 | #define GREATER 1 | |
67 | #define LESS (-1) | |
6dbe3af9 | 68 | |
2ba641e5 | 69 | static int dflag, fflag; |
5c36a0eb KZ |
70 | /* uglified the source a bit with globals, so that we only need |
71 | to allocate comparbuf once */ | |
2ba641e5 SK |
72 | static int stringlen; |
73 | static char *string; | |
74 | static char *comparbuf; | |
6dbe3af9 | 75 | |
5c36a0eb | 76 | static char *binary_search (char *, char *); |
eb63b9b8 | 77 | static int compare (char *, char *); |
5c36a0eb KZ |
78 | static char *linear_search (char *, char *); |
79 | static int look (char *, char *); | |
80 | static void print_from (char *, char *); | |
6e1eda6f | 81 | static void __attribute__((__noreturn__)) usage(void); |
6dbe3af9 | 82 | |
5c36a0eb KZ |
83 | int |
84 | main(int argc, char *argv[]) | |
6dbe3af9 KZ |
85 | { |
86 | struct stat sb; | |
87 | int ch, fd, termchar; | |
5c36a0eb KZ |
88 | char *back, *file, *front, *p; |
89 | ||
a35f7505 SK |
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 | ||
7eda085c KZ |
100 | setlocale(LC_ALL, ""); |
101 | bindtextdomain(PACKAGE, LOCALEDIR); | |
102 | textdomain(PACKAGE); | |
2c308875 | 103 | close_stdout_atexit(); |
429ee997 | 104 | |
a653878c SK |
105 | if ((file = getenv("WORDLIST")) && !access(file, R_OK)) |
106 | /* use the WORDLIST */; | |
107 | else | |
108 | file = _PATH_WORDS; | |
109 | ||
6dbe3af9 | 110 | termchar = '\0'; |
fd6b7a7f KZ |
111 | string = NULL; /* just for gcc */ |
112 | ||
a35f7505 | 113 | while ((ch = getopt_long(argc, argv, "adft:Vh", longopts, NULL)) != -1) |
6dbe3af9 KZ |
114 | switch(ch) { |
115 | case 'a': | |
a35f7505 SK |
116 | file = _PATH_WORDS_ALT; |
117 | break; | |
6dbe3af9 KZ |
118 | case 'd': |
119 | dflag = 1; | |
120 | break; | |
121 | case 'f': | |
122 | fflag = 1; | |
123 | break; | |
124 | case 't': | |
125 | termchar = *optarg; | |
126 | break; | |
a35f7505 | 127 | case 'V': |
2c308875 | 128 | print_version(EXIT_SUCCESS); |
a35f7505 | 129 | case 'h': |
6e1eda6f | 130 | usage(); |
6dbe3af9 | 131 | default: |
677ec86c | 132 | errtryhelp(EXIT_FAILURE); |
6dbe3af9 KZ |
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: | |
6e1eda6f RM |
147 | warnx(_("bad usage")); |
148 | errtryhelp(EXIT_FAILURE); | |
6dbe3af9 KZ |
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)) | |
026ed2ce | 155 | err(EXIT_FAILURE, "%s", file); |
66ee8158 | 156 | front = mmap(NULL, (size_t) sb.st_size, PROT_READ, |
66ee8158 KZ |
157 | MAP_SHARED, fd, (off_t) 0); |
158 | if | |
159 | #ifdef MAP_FAILED | |
026ed2ce | 160 | (front == MAP_FAILED) |
66ee8158 | 161 | #else |
026ed2ce | 162 | ((void *)(front) <= (void *)0) |
66ee8158 | 163 | #endif |
026ed2ce | 164 | err(EXIT_FAILURE, "%s", file); |
6dbe3af9 | 165 | back = front + sb.st_size; |
5c36a0eb | 166 | return look(front, back); |
6dbe3af9 KZ |
167 | } |
168 | ||
2ba641e5 | 169 | static int |
5c36a0eb | 170 | look(char *front, char *back) |
6dbe3af9 | 171 | { |
5c36a0eb KZ |
172 | int ch; |
173 | char *readp, *writep; | |
6dbe3af9 | 174 | |
a7349ee3 | 175 | /* Reformat string to avoid doing it multiple times later. */ |
5c36a0eb KZ |
176 | if (dflag) { |
177 | for (readp = writep = string; (ch = *readp++) != 0;) { | |
9b480fe6 | 178 | if (isalnum(ch) || isblank(ch)) |
5c36a0eb KZ |
179 | *(writep++) = ch; |
180 | } | |
181 | *writep = '\0'; | |
182 | stringlen = writep - string; | |
183 | } else | |
184 | stringlen = strlen(string); | |
185 | ||
026ed2ce | 186 | comparbuf = xmalloc(stringlen+1); |
6dbe3af9 | 187 | |
5c36a0eb KZ |
188 | front = binary_search(front, back); |
189 | front = linear_search(front, back); | |
6dbe3af9 KZ |
190 | |
191 | if (front) | |
5c36a0eb | 192 | print_from(front, back); |
6c91f5e3 DB |
193 | |
194 | free(comparbuf); | |
195 | ||
6dbe3af9 KZ |
196 | return (front ? 0 : 1); |
197 | } | |
198 | ||
199 | ||
200 | /* | |
201 | * Binary search for "string" in memory between "front" and "back". | |
429ee997 | 202 | * |
6dbe3af9 KZ |
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. | |
429ee997 | 206 | * |
6dbe3af9 | 207 | * Invariants: |
429ee997 | 208 | * front points to the beginning of a line at or before the first |
6dbe3af9 | 209 | * matching string. |
429ee997 KZ |
210 | * |
211 | * back points to the beginning of a line at or after the first | |
6dbe3af9 | 212 | * matching line. |
429ee997 | 213 | * |
6dbe3af9 | 214 | * Advancing the Invariants: |
429ee997 | 215 | * |
6dbe3af9 | 216 | * p = first newline after halfway point from front to back. |
429ee997 KZ |
217 | * |
218 | * If the string at "p" is not greater than the string to match, | |
6dbe3af9 | 219 | * p is the new front. Otherwise it is the new back. |
429ee997 | 220 | * |
6dbe3af9 | 221 | * Termination: |
429ee997 KZ |
222 | * |
223 | * The definition of the routine allows it return at any point, | |
6dbe3af9 | 224 | * since front is always at or before the line to print. |
429ee997 KZ |
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 | |
6dbe3af9 | 229 | * be no more expensive than the cost of simply printing a string or two. |
429ee997 KZ |
230 | * |
231 | * Trying to continue with binary search at this point would be | |
6dbe3af9 KZ |
232 | * more trouble than it's worth. |
233 | */ | |
234 | #define SKIP_PAST_NEWLINE(p, back) \ | |
fad05c68 | 235 | while (p < back && *p++ != '\n') |
6dbe3af9 | 236 | |
2ba641e5 | 237 | static char * |
5c36a0eb | 238 | binary_search(char *front, char *back) |
6dbe3af9 | 239 | { |
5c36a0eb | 240 | char *p; |
6dbe3af9 KZ |
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) { | |
eb63b9b8 | 250 | if (compare(p, back) == GREATER) |
6dbe3af9 KZ |
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. | |
429ee997 | 263 | * |
6dbe3af9 | 264 | * Return NULL for no such line. |
429ee997 | 265 | * |
6dbe3af9 | 266 | * This routine assumes: |
429ee997 KZ |
267 | * |
268 | * o front points at the first character in a line. | |
6dbe3af9 KZ |
269 | * o front is before or at the first line to be printed. |
270 | */ | |
2ba641e5 | 271 | static char * |
5c36a0eb | 272 | linear_search(char *front, char *back) |
6dbe3af9 KZ |
273 | { |
274 | while (front < back) { | |
eb63b9b8 | 275 | switch (compare(front, back)) { |
6dbe3af9 KZ |
276 | case EQUAL: /* Found it. */ |
277 | return (front); | |
6dbe3af9 KZ |
278 | case LESS: /* No such string. */ |
279 | return (NULL); | |
6dbe3af9 KZ |
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 | */ | |
2ba641e5 | 291 | static void |
5c36a0eb | 292 | print_from(char *front, char *back) |
6dbe3af9 | 293 | { |
5c36a0eb KZ |
294 | int eol; |
295 | ||
eb63b9b8 KZ |
296 | while (front < back && compare(front, back) == EQUAL) { |
297 | if (compare(front, back) == EQUAL) { | |
5c36a0eb KZ |
298 | eol = 0; |
299 | while (front < back && !eol) { | |
300 | if (putchar(*front) == EOF) | |
026ed2ce | 301 | err(EXIT_FAILURE, "stdout"); |
5c36a0eb KZ |
302 | if (*front++ == '\n') |
303 | eol = 1; | |
304 | } | |
305 | } else | |
306 | SKIP_PAST_NEWLINE(front, back); | |
6dbe3af9 KZ |
307 | } |
308 | } | |
309 | ||
310 | /* | |
5c36a0eb | 311 | * Return LESS, GREATER, or EQUAL depending on how string compares with |
6dbe3af9 | 312 | * string2 (s1 ??? s2). |
429ee997 KZ |
313 | * |
314 | * o Matches up to len(s1) are EQUAL. | |
6dbe3af9 | 315 | * o Matches up to len(s2) are GREATER. |
429ee997 | 316 | * |
6dbe3af9 KZ |
317 | * Compare understands about the -f and -d flags, and treats comparisons |
318 | * appropriately. | |
429ee997 | 319 | * |
5c36a0eb KZ |
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. | |
6dbe3af9 | 325 | */ |
2ba641e5 | 326 | static int |
eb63b9b8 | 327 | compare(char *s2, char *s2end) { |
5c36a0eb KZ |
328 | int i; |
329 | char *p; | |
330 | ||
331 | /* copy, ignoring things that should be ignored */ | |
332 | p = comparbuf; | |
333 | i = stringlen; | |
dab737cc | 334 | while(s2 < s2end && *s2 != '\n' && i) { |
9b480fe6 | 335 | if (!dflag || isalnum(*s2) || isblank(*s2)) |
dab737cc | 336 | { |
5c36a0eb | 337 | *p++ = *s2; |
dab737cc KZ |
338 | i--; |
339 | } | |
5c36a0eb | 340 | s2++; |
6dbe3af9 | 341 | } |
5c36a0eb KZ |
342 | *p = 0; |
343 | ||
344 | /* and compare */ | |
eb63b9b8 | 345 | if (fflag) |
5c36a0eb KZ |
346 | i = strncasecmp(comparbuf, string, stringlen); |
347 | else | |
348 | i = strncmp(comparbuf, string, stringlen); | |
349 | ||
350 | return ((i > 0) ? LESS : (i < 0) ? GREATER : EQUAL); | |
6dbe3af9 KZ |
351 | } |
352 | ||
6e1eda6f | 353 | static void __attribute__((__noreturn__)) usage(void) |
6dbe3af9 | 354 | { |
6e1eda6f | 355 | FILE *out = stdout; |
db433bf7 | 356 | fputs(USAGE_HEADER, out); |
dfe6a6d0 | 357 | fprintf(out, _(" %s [options] <string> [<file>...]\n"), program_invocation_short_name); |
451dbcfa BS |
358 | |
359 | fputs(USAGE_SEPARATOR, out); | |
360 | fputs(_("Display lines beginning with a specified string.\n"), out); | |
361 | ||
db433bf7 | 362 | fputs(USAGE_OPTIONS, out); |
dfe6a6d0 | 363 | fputs(_(" -a, --alternative use the alternative dictionary\n"), out); |
9b480fe6 | 364 | fputs(_(" -d, --alphanum compare only blanks and alphanumeric characters\n"), out); |
dfe6a6d0 BS |
365 | fputs(_(" -f, --ignore-case ignore case differences when comparing\n"), out); |
366 | fputs(_(" -t, --terminate <char> define the string-termination character\n"), out); | |
a35f7505 | 367 | |
dfe6a6d0 | 368 | fputs(USAGE_SEPARATOR, out); |
bad4c729 MY |
369 | fprintf(out, USAGE_HELP_OPTIONS(26)); |
370 | fprintf(out, USAGE_MAN_TAIL("look(1)")); | |
dfe6a6d0 | 371 | |
6e1eda6f | 372 | exit(EXIT_SUCCESS); |
6dbe3af9 | 373 | } |