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