]>
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 KZ |
68 | |
69 | int dflag, fflag; | |
5c36a0eb KZ |
70 | /* uglified the source a bit with globals, so that we only need |
71 | to allocate comparbuf once */ | |
72 | int stringlen; | |
73 | char *string; | |
74 | 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 *); | |
a35f7505 | 81 | static void __attribute__ ((__noreturn__)) usage(FILE * out); |
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); | |
c05a80ca | 103 | atexit(close_stdout); |
429ee997 | 104 | |
5c36a0eb | 105 | setlocale(LC_ALL, ""); |
6dbe3af9 KZ |
106 | |
107 | file = _PATH_WORDS; | |
108 | termchar = '\0'; | |
fd6b7a7f KZ |
109 | string = NULL; /* just for gcc */ |
110 | ||
a35f7505 | 111 | while ((ch = getopt_long(argc, argv, "adft:Vh", longopts, NULL)) != -1) |
6dbe3af9 KZ |
112 | switch(ch) { |
113 | case 'a': | |
a35f7505 SK |
114 | file = _PATH_WORDS_ALT; |
115 | break; | |
6dbe3af9 KZ |
116 | case 'd': |
117 | dflag = 1; | |
118 | break; | |
119 | case 'f': | |
120 | fflag = 1; | |
121 | break; | |
122 | case 't': | |
123 | termchar = *optarg; | |
124 | break; | |
a35f7505 | 125 | case 'V': |
e421313d | 126 | printf(UTIL_LINUX_VERSION); |
a35f7505 SK |
127 | return EXIT_SUCCESS; |
128 | case 'h': | |
129 | usage(stdout); | |
6dbe3af9 KZ |
130 | case '?': |
131 | default: | |
a35f7505 | 132 | usage(stderr); |
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: | |
a35f7505 | 147 | usage(stderr); |
6dbe3af9 KZ |
148 | } |
149 | ||
150 | if (termchar != '\0' && (p = strchr(string, termchar)) != NULL) | |
151 | *++p = '\0'; | |
152 | ||
153 | if ((fd = open(file, O_RDONLY, 0)) < 0 || fstat(fd, &sb)) | |
026ed2ce | 154 | err(EXIT_FAILURE, "%s", file); |
66ee8158 | 155 | front = mmap(NULL, (size_t) sb.st_size, PROT_READ, |
66ee8158 KZ |
156 | MAP_SHARED, fd, (off_t) 0); |
157 | if | |
158 | #ifdef MAP_FAILED | |
026ed2ce | 159 | (front == MAP_FAILED) |
66ee8158 | 160 | #else |
026ed2ce | 161 | ((void *)(front) <= (void *)0) |
66ee8158 | 162 | #endif |
026ed2ce | 163 | err(EXIT_FAILURE, "%s", file); |
6dbe3af9 | 164 | back = front + sb.st_size; |
5c36a0eb | 165 | return look(front, back); |
6dbe3af9 KZ |
166 | } |
167 | ||
fd6b7a7f | 168 | int |
5c36a0eb | 169 | look(char *front, char *back) |
6dbe3af9 | 170 | { |
5c36a0eb KZ |
171 | int ch; |
172 | char *readp, *writep; | |
6dbe3af9 KZ |
173 | |
174 | /* Reformat string string to avoid doing it multiple times later. */ | |
5c36a0eb KZ |
175 | if (dflag) { |
176 | for (readp = writep = string; (ch = *readp++) != 0;) { | |
177 | if (isalnum(ch)) | |
178 | *(writep++) = ch; | |
179 | } | |
180 | *writep = '\0'; | |
181 | stringlen = writep - string; | |
182 | } else | |
183 | stringlen = strlen(string); | |
184 | ||
026ed2ce | 185 | comparbuf = xmalloc(stringlen+1); |
6dbe3af9 | 186 | |
5c36a0eb KZ |
187 | front = binary_search(front, back); |
188 | front = linear_search(front, back); | |
6dbe3af9 KZ |
189 | |
190 | if (front) | |
5c36a0eb | 191 | print_from(front, back); |
6c91f5e3 DB |
192 | |
193 | free(comparbuf); | |
194 | ||
6dbe3af9 KZ |
195 | return (front ? 0 : 1); |
196 | } | |
197 | ||
198 | ||
199 | /* | |
200 | * Binary search for "string" in memory between "front" and "back". | |
429ee997 | 201 | * |
6dbe3af9 KZ |
202 | * This routine is expected to return a pointer to the start of a line at |
203 | * *or before* the first word matching "string". Relaxing the constraint | |
204 | * this way simplifies the algorithm. | |
429ee997 | 205 | * |
6dbe3af9 | 206 | * Invariants: |
429ee997 | 207 | * front points to the beginning of a line at or before the first |
6dbe3af9 | 208 | * matching string. |
429ee997 KZ |
209 | * |
210 | * back points to the beginning of a line at or after the first | |
6dbe3af9 | 211 | * matching line. |
429ee997 | 212 | * |
6dbe3af9 | 213 | * Advancing the Invariants: |
429ee997 | 214 | * |
6dbe3af9 | 215 | * p = first newline after halfway point from front to back. |
429ee997 KZ |
216 | * |
217 | * If the string at "p" is not greater than the string to match, | |
6dbe3af9 | 218 | * p is the new front. Otherwise it is the new back. |
429ee997 | 219 | * |
6dbe3af9 | 220 | * Termination: |
429ee997 KZ |
221 | * |
222 | * The definition of the routine allows it return at any point, | |
6dbe3af9 | 223 | * since front is always at or before the line to print. |
429ee997 KZ |
224 | * |
225 | * In fact, it returns when the chosen "p" equals "back". This | |
226 | * implies that there exists a string is least half as long as | |
227 | * (back - front), which in turn implies that a linear search will | |
6dbe3af9 | 228 | * be no more expensive than the cost of simply printing a string or two. |
429ee997 KZ |
229 | * |
230 | * Trying to continue with binary search at this point would be | |
6dbe3af9 KZ |
231 | * more trouble than it's worth. |
232 | */ | |
233 | #define SKIP_PAST_NEWLINE(p, back) \ | |
fad05c68 | 234 | while (p < back && *p++ != '\n') |
6dbe3af9 KZ |
235 | |
236 | char * | |
5c36a0eb | 237 | binary_search(char *front, char *back) |
6dbe3af9 | 238 | { |
5c36a0eb | 239 | char *p; |
6dbe3af9 KZ |
240 | |
241 | p = front + (back - front) / 2; | |
242 | SKIP_PAST_NEWLINE(p, back); | |
243 | ||
244 | /* | |
245 | * If the file changes underneath us, make sure we don't | |
246 | * infinitely loop. | |
247 | */ | |
248 | while (p < back && back > front) { | |
eb63b9b8 | 249 | if (compare(p, back) == GREATER) |
6dbe3af9 KZ |
250 | front = p; |
251 | else | |
252 | back = p; | |
253 | p = front + (back - front) / 2; | |
254 | SKIP_PAST_NEWLINE(p, back); | |
255 | } | |
256 | return (front); | |
257 | } | |
258 | ||
259 | /* | |
260 | * Find the first line that starts with string, linearly searching from front | |
261 | * to back. | |
429ee997 | 262 | * |
6dbe3af9 | 263 | * Return NULL for no such line. |
429ee997 | 264 | * |
6dbe3af9 | 265 | * This routine assumes: |
429ee997 KZ |
266 | * |
267 | * o front points at the first character in a line. | |
6dbe3af9 KZ |
268 | * o front is before or at the first line to be printed. |
269 | */ | |
270 | char * | |
5c36a0eb | 271 | linear_search(char *front, char *back) |
6dbe3af9 KZ |
272 | { |
273 | while (front < back) { | |
eb63b9b8 | 274 | switch (compare(front, back)) { |
6dbe3af9 KZ |
275 | case EQUAL: /* Found it. */ |
276 | return (front); | |
277 | break; | |
278 | case LESS: /* No such string. */ | |
279 | return (NULL); | |
280 | break; | |
281 | case GREATER: /* Keep going. */ | |
282 | break; | |
283 | } | |
284 | SKIP_PAST_NEWLINE(front, back); | |
285 | } | |
286 | return (NULL); | |
287 | } | |
288 | ||
289 | /* | |
290 | * Print as many lines as match string, starting at front. | |
291 | */ | |
429ee997 | 292 | void |
5c36a0eb | 293 | print_from(char *front, char *back) |
6dbe3af9 | 294 | { |
5c36a0eb KZ |
295 | int eol; |
296 | ||
eb63b9b8 KZ |
297 | while (front < back && compare(front, back) == EQUAL) { |
298 | if (compare(front, back) == EQUAL) { | |
5c36a0eb KZ |
299 | eol = 0; |
300 | while (front < back && !eol) { | |
301 | if (putchar(*front) == EOF) | |
026ed2ce | 302 | err(EXIT_FAILURE, "stdout"); |
5c36a0eb KZ |
303 | if (*front++ == '\n') |
304 | eol = 1; | |
305 | } | |
306 | } else | |
307 | SKIP_PAST_NEWLINE(front, back); | |
6dbe3af9 KZ |
308 | } |
309 | } | |
310 | ||
311 | /* | |
5c36a0eb | 312 | * Return LESS, GREATER, or EQUAL depending on how string compares with |
6dbe3af9 | 313 | * string2 (s1 ??? s2). |
429ee997 KZ |
314 | * |
315 | * o Matches up to len(s1) are EQUAL. | |
6dbe3af9 | 316 | * o Matches up to len(s2) are GREATER. |
429ee997 | 317 | * |
6dbe3af9 KZ |
318 | * Compare understands about the -f and -d flags, and treats comparisons |
319 | * appropriately. | |
429ee997 | 320 | * |
5c36a0eb KZ |
321 | * The string "string" is null terminated. The string "s2" is '\n' terminated |
322 | * (or "s2end" terminated). | |
323 | * | |
324 | * We use strcasecmp etc, since it knows how to ignore case also | |
325 | * in other locales. | |
6dbe3af9 KZ |
326 | */ |
327 | int | |
eb63b9b8 | 328 | compare(char *s2, char *s2end) { |
5c36a0eb KZ |
329 | int i; |
330 | char *p; | |
331 | ||
332 | /* copy, ignoring things that should be ignored */ | |
333 | p = comparbuf; | |
334 | i = stringlen; | |
dab737cc | 335 | while(s2 < s2end && *s2 != '\n' && i) { |
5c36a0eb | 336 | if (!dflag || isalnum(*s2)) |
dab737cc | 337 | { |
5c36a0eb | 338 | *p++ = *s2; |
dab737cc KZ |
339 | i--; |
340 | } | |
5c36a0eb | 341 | s2++; |
6dbe3af9 | 342 | } |
5c36a0eb KZ |
343 | *p = 0; |
344 | ||
345 | /* and compare */ | |
eb63b9b8 | 346 | if (fflag) |
5c36a0eb KZ |
347 | i = strncasecmp(comparbuf, string, stringlen); |
348 | else | |
349 | i = strncmp(comparbuf, string, stringlen); | |
350 | ||
351 | return ((i > 0) ? LESS : (i < 0) ? GREATER : EQUAL); | |
6dbe3af9 KZ |
352 | } |
353 | ||
a35f7505 | 354 | static void __attribute__ ((__noreturn__)) usage(FILE * out) |
6dbe3af9 | 355 | { |
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 BS |
363 | fputs(_(" -a, --alternative use the alternative dictionary\n"), out); |
364 | fputs(_(" -d, --alphanum compare only 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); | |
a35f7505 | 367 | |
dfe6a6d0 BS |
368 | fputs(USAGE_SEPARATOR, out); |
369 | fputs(USAGE_HELP, out); | |
370 | fputs(USAGE_VERSION, out); | |
a587cc55 | 371 | fprintf(out, USAGE_MAN_TAIL("look(1)")); |
dfe6a6d0 | 372 | |
a35f7505 | 373 | exit(out == stderr ? EXIT_FAILURE : EXIT_SUCCESS); |
6dbe3af9 | 374 | } |