Commit | Line | Data |
---|---|---|
3c4adc3c | 1 | /*- |
08fc9b74 | 2 | * Copyright (c) 1991 The Regents of the University of California. |
3c4adc3c KB |
3 | * All rights reserved. |
4 | * | |
08fc9b74 KB |
5 | * This code is derived from software contributed to Berkeley by |
6 | * David Hitz of Auspex Systems, Inc. | |
7 | * | |
8 | * %sccs.include.redist.c% | |
c47cd113 KB |
9 | */ |
10 | ||
11 | #ifndef lint | |
12 | char copyright[] = | |
08fc9b74 | 13 | "@(#) Copyright (c) 1991 The Regents of the University of California.\n\ |
c47cd113 | 14 | All rights reserved.\n"; |
3c4adc3c | 15 | #endif /* not lint */ |
c47cd113 KB |
16 | |
17 | #ifndef lint | |
08fc9b74 | 18 | static char sccsid[] = "@(#)look.c 5.1 (Berkeley) %G%"; |
3c4adc3c | 19 | #endif /* not lint */ |
c47cd113 | 20 | |
08fc9b74 KB |
21 | /* |
22 | * look -- find lines in a sorted list. | |
23 | * | |
24 | * The man page said that TABs and SPACEs participate in -d comparisons. | |
25 | * In fact, they were ignored. This implements historic practice, not | |
26 | * the manual page. | |
27 | */ | |
28 | ||
c47cd113 | 29 | #include <sys/types.h> |
08fc9b74 | 30 | #include <sys/mman.h> |
c47cd113 | 31 | #include <sys/stat.h> |
08fc9b74 KB |
32 | #include <errno.h> |
33 | #include <fcntl.h> | |
027304e0 | 34 | #include <stdio.h> |
08fc9b74 KB |
35 | #include <stdlib.h> |
36 | #include <string.h> | |
027304e0 | 37 | #include <ctype.h> |
435e8dff | 38 | #include "pathnames.h" |
027304e0 | 39 | |
08fc9b74 KB |
40 | /* |
41 | * FOLD and DICT convert characters to a normal form for comparison, | |
42 | * according to the user specified flags. | |
43 | * | |
44 | * DICT expects integers because it uses a non-character value to | |
45 | * indicate a character which should not participate in comparisons. | |
46 | */ | |
47 | #define EQUAL 0 | |
48 | #define GREATER 1 | |
49 | #define LESS (-1) | |
50 | #define NO_COMPARE (-2) | |
51 | ||
52 | #define FOLD(c) (isascii(c) && isupper(c) ? tolower(c) : (c)) | |
53 | #define DICT(c) (isascii(c) && isalnum(c) ? (c) : NO_COMPARE) | |
54 | ||
55 | int dflag, fflag; | |
027304e0 | 56 | |
08fc9b74 KB |
57 | char *binary_search __P((char *, char *, char *)); |
58 | int compare __P((char *, char *, char *)); | |
59 | void err __P((const char *fmt, ...)); | |
60 | char *linear_search __P((char *, char *, char *)); | |
61 | int look __P((char *, char *, char *)); | |
62 | void print_from __P((char *, char *, char *)); | |
63 | void usage __P((void)); | |
027304e0 | 64 | |
c47cd113 | 65 | main(argc, argv) |
08fc9b74 KB |
66 | int argc; |
67 | char *argv[]; | |
027304e0 | 68 | { |
08fc9b74 KB |
69 | struct stat sb; |
70 | int ch, fd; | |
71 | char *back, *file, *front, *string; | |
72 | ||
73 | file = _PATH_WORDS; | |
74 | while ((ch = getopt(argc, argv, "df")) != EOF) | |
75 | switch(ch) { | |
c47cd113 | 76 | case 'd': |
08fc9b74 | 77 | dflag = 1; |
027304e0 | 78 | break; |
c47cd113 | 79 | case 'f': |
08fc9b74 | 80 | fflag = 1; |
c47cd113 KB |
81 | break; |
82 | case '?': | |
83 | default: | |
84 | usage(); | |
027304e0 | 85 | } |
c47cd113 | 86 | argc -= optind; |
08fc9b74 | 87 | argv += optind; |
c47cd113 | 88 | |
08fc9b74 KB |
89 | switch (argc) { |
90 | case 2: /* Don't set -df for user. */ | |
91 | string = *argv++; | |
92 | file = *argv; | |
c47cd113 | 93 | break; |
08fc9b74 KB |
94 | case 1: /* But set -df by default. */ |
95 | dflag = fflag = 1; | |
96 | string = *argv; | |
c47cd113 KB |
97 | break; |
98 | default: | |
99 | usage(); | |
027304e0 | 100 | } |
c47cd113 | 101 | |
08fc9b74 KB |
102 | if ((fd = open(file, O_RDONLY, 0)) < 0 || fstat(fd, &sb) || |
103 | (front = mmap(NULL, sb.st_size, PROT_READ, MAP_FILE, fd, | |
104 | (off_t)0)) == NULL) | |
105 | err("%s: %s", file, strerror(errno)); | |
106 | back = front + sb.st_size; | |
107 | exit(look(string, front, back)); | |
108 | } | |
109 | ||
110 | look(string, front, back) | |
111 | char *string, *front, *back; | |
112 | { | |
113 | register int ch; | |
114 | register char *readp, *writep; | |
c47cd113 | 115 | |
08fc9b74 KB |
116 | /* Reformat string string to avoid doing it multiple times later. */ |
117 | for (readp = writep = string; ch = *readp++;) { | |
118 | if (fflag) | |
119 | ch = FOLD(ch); | |
120 | if (dflag) | |
121 | ch = DICT(ch); | |
122 | if (ch != NO_COMPARE) | |
123 | *(writep++) = ch; | |
c47cd113 | 124 | } |
08fc9b74 | 125 | *writep = '\0'; |
c47cd113 | 126 | |
08fc9b74 KB |
127 | front = binary_search(string, front, back); |
128 | front = linear_search(string, front, back); | |
c47cd113 | 129 | |
08fc9b74 KB |
130 | if (front) |
131 | print_from(string, front, back); | |
132 | return (front ? 0 : 1); | |
133 | } | |
134 | ||
135 | ||
136 | /* | |
137 | * Binary search for "string" in memory between "front" and "back". | |
138 | * | |
139 | * This routine is expected to return a pointer to the start of a line at | |
140 | * *or before* the first word matching "string". Relaxing the constraint | |
141 | * this way simplifies the algorithm. | |
142 | * | |
143 | * Invariants: | |
144 | * front points to the beginning of a line at or before the first | |
145 | * matching string. | |
146 | * | |
147 | * back points to the beginning of a line at or after the first | |
148 | * matching line. | |
149 | * | |
150 | * Base of the Invariants. | |
151 | * front = NULL; | |
152 | * back = EOF; | |
153 | * | |
154 | * Advancing the Invariants: | |
155 | * | |
156 | * p = first newline after halfway point from front to back. | |
157 | * | |
158 | * If the string at "p" is not greater than the string to match, | |
159 | * p is the new front. Otherwise it is the new back. | |
160 | * | |
161 | * Termination: | |
162 | * | |
163 | * The definition of the routine allows it return at any point, | |
164 | * since front is always at or before the line to print. | |
165 | * | |
166 | * In fact, it returns when the chosen "p" equals "back". This | |
167 | * implies that there exists a string is least half as long as | |
168 | * (back - front), which in turn implies that a linear search will | |
169 | * be no more expensive than the cost of simply printing a string or two. | |
170 | * | |
171 | * Trying to continue with binary search at this point would be | |
172 | * more trouble than it's worth. | |
173 | */ | |
174 | #define SKIP_PAST_NEWLINE(p, back) \ | |
175 | while (p < back && *p++ != '\n'); | |
176 | ||
177 | char * | |
178 | binary_search(string, front, back) | |
179 | register char *string, *front, *back; | |
180 | { | |
181 | register char *p; | |
182 | ||
183 | p = front + (back - front) / 2; | |
184 | SKIP_PAST_NEWLINE(p, back); | |
185 | ||
186 | while (p != back) { | |
187 | if (compare(string, p, back) == GREATER) | |
188 | front = p; | |
c47cd113 | 189 | else |
08fc9b74 KB |
190 | back = p; |
191 | p = front + (back - front) / 2; | |
192 | SKIP_PAST_NEWLINE(p, back); | |
027304e0 | 193 | } |
08fc9b74 KB |
194 | return (front); |
195 | } | |
196 | ||
197 | /* | |
198 | * Find the first line that starts with string, linearly searching from front | |
199 | * to back. | |
200 | * | |
201 | * Return NULL for no such line. | |
202 | * | |
203 | * This routine assumes: | |
204 | * | |
205 | * o front points at the first character in a line. | |
206 | * o front is before or at the first line to be printed. | |
207 | */ | |
208 | char * | |
209 | linear_search(string, front, back) | |
210 | char *string, *front, *back; | |
211 | { | |
212 | while (front < back) { | |
213 | switch (compare(string, front, back)) { | |
214 | case EQUAL: /* Found it. */ | |
215 | return (front); | |
027304e0 | 216 | break; |
08fc9b74 KB |
217 | case LESS: /* No such string. */ |
218 | return (NULL); | |
219 | break; | |
220 | case GREATER: /* Keep going. */ | |
c47cd113 | 221 | break; |
08fc9b74 KB |
222 | } |
223 | SKIP_PAST_NEWLINE(front, back); | |
027304e0 | 224 | } |
08fc9b74 | 225 | return (NULL); |
027304e0 BJ |
226 | } |
227 | ||
c47cd113 | 228 | /* |
08fc9b74 | 229 | * Print as many lines as match string, starting at front. |
c47cd113 | 230 | */ |
08fc9b74 KB |
231 | void |
232 | print_from(string, front, back) | |
233 | register char *string, *front, *back; | |
027304e0 | 234 | { |
08fc9b74 KB |
235 | for (; front < back && compare(string, front, back) == EQUAL; ++front) { |
236 | for (; front < back && *front != '\n'; ++front) | |
237 | if (putchar(*front) == EOF) | |
238 | err("stdout: %s", strerror(errno)); | |
239 | if (putchar('\n') == EOF) | |
240 | err("stdout: %s", strerror(errno)); | |
027304e0 | 241 | } |
027304e0 BJ |
242 | } |
243 | ||
c47cd113 | 244 | /* |
08fc9b74 KB |
245 | * Return LESS, GREATER, or EQUAL depending on how the string1 compares with |
246 | * string2 (s1 ??? s2). | |
247 | * | |
248 | * o Matches up to len(s1) are EQUAL. | |
249 | * o Matches up to len(s2) are GREATER. | |
250 | * | |
251 | * Compare understands about the -f and -d flags, and treats comparisons | |
252 | * appropriately. | |
253 | * | |
254 | * The string "s1" is null terminated. The string s2 is '\n' terminated (or | |
255 | * "back" terminated). | |
c47cd113 | 256 | */ |
08fc9b74 KB |
257 | int |
258 | compare(s1, s2, back) | |
259 | register char *s1, *s2, *back; | |
027304e0 | 260 | { |
08fc9b74 KB |
261 | register int ch; |
262 | ||
263 | for (; *s1 && s2 < back && *s2 != '\n'; ++s1, ++s2) { | |
264 | ch = *s2; | |
265 | if (fflag) | |
266 | ch = FOLD(ch); | |
267 | if (dflag) | |
268 | ch = DICT(ch); | |
c47cd113 | 269 | |
08fc9b74 KB |
270 | if (ch == NO_COMPARE) { |
271 | ++s2; /* Ignore character in comparison. */ | |
272 | continue; | |
273 | } | |
274 | if (*s1 != ch) | |
275 | return (*s1 < ch ? LESS : GREATER); | |
276 | } | |
277 | return (*s1 ? GREATER : EQUAL); | |
c47cd113 KB |
278 | } |
279 | ||
08fc9b74 | 280 | static void |
c47cd113 KB |
281 | usage() |
282 | { | |
bc0c28c1 | 283 | (void)fprintf(stderr, "usage: look [-df] string [file]\n"); |
08fc9b74 KB |
284 | exit(2); |
285 | } | |
286 | ||
287 | #if __STDC__ | |
288 | #include <stdarg.h> | |
289 | #else | |
290 | #include <varargs.h> | |
291 | #endif | |
292 | ||
293 | void | |
294 | #if __STDC__ | |
295 | err(const char *fmt, ...) | |
296 | #else | |
297 | err(fmt, va_alist) | |
298 | char *fmt; | |
299 | va_dcl | |
300 | #endif | |
301 | { | |
302 | va_list ap; | |
303 | #if __STDC__ | |
304 | va_start(ap, fmt); | |
305 | #else | |
306 | va_start(ap); | |
307 | #endif | |
308 | (void)fprintf(stderr, "look: "); | |
309 | (void)vfprintf(stderr, fmt, ap); | |
310 | va_end(ap); | |
311 | (void)fprintf(stderr, "\n"); | |
312 | exit(2); | |
313 | /* NOTREACHED */ | |
027304e0 | 314 | } |