2 * Copyright (c) 1991, 1993
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
6 * David Hitz of Auspex Systems, Inc.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
37 /* 1999-02-22 Arkadiusz MiĆkiewicz <misiek@pld.ORG.PL>
38 * - added Native Language Support
42 * look -- find lines in a sorted list.
44 * The man page said that TABs and SPACEs participate in -d comparisons.
45 * In fact, they were ignored. This implements historic practice, not
62 #include "pathnames.h"
63 #include "closestream.h"
69 static int dflag
, fflag
;
70 /* uglified the source a bit with globals, so that we only need
71 to allocate comparbuf once */
74 static char *comparbuf
;
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);
84 main(int argc
, char *argv
[])
88 char *back
, *file
, *front
, *p
;
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'},
100 setlocale(LC_ALL
, "");
101 bindtextdomain(PACKAGE
, LOCALEDIR
);
103 close_stdout_atexit();
105 setlocale(LC_ALL
, "");
107 if ((file
= getenv("WORDLIST")) && !access(file
, R_OK
))
108 /* use the WORDLIST */;
113 string
= NULL
; /* just for gcc */
115 while ((ch
= getopt_long(argc
, argv
, "adft:Vh", longopts
, NULL
)) != -1)
118 file
= _PATH_WORDS_ALT
;
130 print_version(EXIT_SUCCESS
);
134 errtryhelp(EXIT_FAILURE
);
140 case 2: /* Don't set -df for user. */
144 case 1: /* But set -df by default. */
149 warnx(_("bad usage"));
150 errtryhelp(EXIT_FAILURE
);
153 if (termchar
!= '\0' && (p
= strchr(string
, termchar
)) != NULL
)
156 if ((fd
= open(file
, O_RDONLY
, 0)) < 0 || fstat(fd
, &sb
))
157 err(EXIT_FAILURE
, "%s", file
);
158 front
= mmap(NULL
, (size_t) sb
.st_size
, PROT_READ
,
159 MAP_SHARED
, fd
, (off_t
) 0);
162 (front
== MAP_FAILED
)
164 ((void *)(front
) <= (void *)0)
166 err(EXIT_FAILURE
, "%s", file
);
167 back
= front
+ sb
.st_size
;
168 return look(front
, back
);
172 look(char *front
, char *back
)
175 char *readp
, *writep
;
177 /* Reformat string to avoid doing it multiple times later. */
179 for (readp
= writep
= string
; (ch
= *readp
++) != 0;) {
180 if (isalnum(ch
) || isblank(ch
))
184 stringlen
= writep
- string
;
186 stringlen
= strlen(string
);
188 comparbuf
= xmalloc(stringlen
+1);
190 front
= binary_search(front
, back
);
191 front
= linear_search(front
, back
);
194 print_from(front
, back
);
198 return (front
? 0 : 1);
203 * Binary search for "string" in memory between "front" and "back".
205 * This routine is expected to return a pointer to the start of a line at
206 * *or before* the first word matching "string". Relaxing the constraint
207 * this way simplifies the algorithm.
210 * front points to the beginning of a line at or before the first
213 * back points to the beginning of a line at or after the first
216 * Advancing the Invariants:
218 * p = first newline after halfway point from front to back.
220 * If the string at "p" is not greater than the string to match,
221 * p is the new front. Otherwise it is the new back.
225 * The definition of the routine allows it return at any point,
226 * since front is always at or before the line to print.
228 * In fact, it returns when the chosen "p" equals "back". This
229 * implies that there exists a string is least half as long as
230 * (back - front), which in turn implies that a linear search will
231 * be no more expensive than the cost of simply printing a string or two.
233 * Trying to continue with binary search at this point would be
234 * more trouble than it's worth.
236 #define SKIP_PAST_NEWLINE(p, back) \
237 while (p < back && *p++ != '\n')
240 binary_search(char *front
, char *back
)
244 p
= front
+ (back
- front
) / 2;
245 SKIP_PAST_NEWLINE(p
, back
);
248 * If the file changes underneath us, make sure we don't
251 while (p
< back
&& back
> front
) {
252 if (compare(p
, back
) == GREATER
)
256 p
= front
+ (back
- front
) / 2;
257 SKIP_PAST_NEWLINE(p
, back
);
263 * Find the first line that starts with string, linearly searching from front
266 * Return NULL for no such line.
268 * This routine assumes:
270 * o front points at the first character in a line.
271 * o front is before or at the first line to be printed.
274 linear_search(char *front
, char *back
)
276 while (front
< back
) {
277 switch (compare(front
, back
)) {
278 case EQUAL
: /* Found it. */
280 case LESS
: /* No such string. */
282 case GREATER
: /* Keep going. */
285 SKIP_PAST_NEWLINE(front
, back
);
291 * Print as many lines as match string, starting at front.
294 print_from(char *front
, char *back
)
298 while (front
< back
&& compare(front
, back
) == EQUAL
) {
299 if (compare(front
, back
) == EQUAL
) {
301 while (front
< back
&& !eol
) {
302 if (putchar(*front
) == EOF
)
303 err(EXIT_FAILURE
, "stdout");
304 if (*front
++ == '\n')
308 SKIP_PAST_NEWLINE(front
, back
);
313 * Return LESS, GREATER, or EQUAL depending on how string compares with
314 * string2 (s1 ??? s2).
316 * o Matches up to len(s1) are EQUAL.
317 * o Matches up to len(s2) are GREATER.
319 * Compare understands about the -f and -d flags, and treats comparisons
322 * The string "string" is null terminated. The string "s2" is '\n' terminated
323 * (or "s2end" terminated).
325 * We use strcasecmp etc, since it knows how to ignore case also
329 compare(char *s2
, char *s2end
) {
333 /* copy, ignoring things that should be ignored */
336 while(s2
< s2end
&& *s2
!= '\n' && i
) {
337 if (!dflag
|| isalnum(*s2
) || isblank(*s2
))
348 i
= strncasecmp(comparbuf
, string
, stringlen
);
350 i
= strncmp(comparbuf
, string
, stringlen
);
352 return ((i
> 0) ? LESS
: (i
< 0) ? GREATER
: EQUAL
);
355 static void __attribute__((__noreturn__
)) usage(void)
358 fputs(USAGE_HEADER
, out
);
359 fprintf(out
, _(" %s [options] <string> [<file>...]\n"), program_invocation_short_name
);
361 fputs(USAGE_SEPARATOR
, out
);
362 fputs(_("Display lines beginning with a specified string.\n"), out
);
364 fputs(USAGE_OPTIONS
, out
);
365 fputs(_(" -a, --alternative use the alternative dictionary\n"), out
);
366 fputs(_(" -d, --alphanum compare only blanks and alphanumeric characters\n"), out
);
367 fputs(_(" -f, --ignore-case ignore case differences when comparing\n"), out
);
368 fputs(_(" -t, --terminate <char> define the string-termination character\n"), out
);
370 fputs(USAGE_SEPARATOR
, out
);
371 printf(USAGE_HELP_OPTIONS(26));
372 printf(USAGE_MAN_TAIL("look(1)"));