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 if ((file
= getenv("WORDLIST")) && !access(file
, R_OK
))
106 /* use the WORDLIST */;
111 string
= NULL
; /* just for gcc */
113 while ((ch
= getopt_long(argc
, argv
, "adft:Vh", longopts
, NULL
)) != -1)
116 file
= _PATH_WORDS_ALT
;
128 print_version(EXIT_SUCCESS
);
132 errtryhelp(EXIT_FAILURE
);
138 case 2: /* Don't set -df for user. */
142 case 1: /* But set -df by default. */
147 warnx(_("bad usage"));
148 errtryhelp(EXIT_FAILURE
);
151 if (termchar
!= '\0' && (p
= strchr(string
, termchar
)) != NULL
)
154 if ((fd
= open(file
, O_RDONLY
, 0)) < 0 || fstat(fd
, &sb
))
155 err(EXIT_FAILURE
, "%s", file
);
156 front
= mmap(NULL
, (size_t) sb
.st_size
, PROT_READ
,
157 MAP_SHARED
, fd
, (off_t
) 0);
160 (front
== MAP_FAILED
)
162 ((void *)(front
) <= (void *)0)
164 err(EXIT_FAILURE
, "%s", file
);
165 back
= front
+ sb
.st_size
;
166 return look(front
, back
);
170 look(char *front
, char *back
)
173 char *readp
, *writep
;
175 /* Reformat string to avoid doing it multiple times later. */
177 for (readp
= writep
= string
; (ch
= *readp
++) != 0;) {
178 if (isalnum(ch
) || isblank(ch
))
182 stringlen
= writep
- string
;
184 stringlen
= strlen(string
);
186 comparbuf
= xmalloc(stringlen
+1);
188 front
= binary_search(front
, back
);
189 front
= linear_search(front
, back
);
192 print_from(front
, back
);
196 return (front
? 0 : 1);
201 * Binary search for "string" in memory between "front" and "back".
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.
208 * front points to the beginning of a line at or before the first
211 * back points to the beginning of a line at or after the first
214 * Advancing the Invariants:
216 * p = first newline after halfway point from front to back.
218 * If the string at "p" is not greater than the string to match,
219 * p is the new front. Otherwise it is the new back.
223 * The definition of the routine allows it return at any point,
224 * since front is always at or before the line to print.
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
229 * be no more expensive than the cost of simply printing a string or two.
231 * Trying to continue with binary search at this point would be
232 * more trouble than it's worth.
234 #define SKIP_PAST_NEWLINE(p, back) \
235 while (p < back && *p++ != '\n')
238 binary_search(char *front
, char *back
)
242 p
= front
+ (back
- front
) / 2;
243 SKIP_PAST_NEWLINE(p
, back
);
246 * If the file changes underneath us, make sure we don't
249 while (p
< back
&& back
> front
) {
250 if (compare(p
, back
) == GREATER
)
254 p
= front
+ (back
- front
) / 2;
255 SKIP_PAST_NEWLINE(p
, back
);
261 * Find the first line that starts with string, linearly searching from front
264 * Return NULL for no such line.
266 * This routine assumes:
268 * o front points at the first character in a line.
269 * o front is before or at the first line to be printed.
272 linear_search(char *front
, char *back
)
274 while (front
< back
) {
275 switch (compare(front
, back
)) {
276 case EQUAL
: /* Found it. */
278 case LESS
: /* No such string. */
280 case GREATER
: /* Keep going. */
283 SKIP_PAST_NEWLINE(front
, back
);
289 * Print as many lines as match string, starting at front.
292 print_from(char *front
, char *back
)
296 while (front
< back
&& compare(front
, back
) == EQUAL
) {
297 if (compare(front
, back
) == EQUAL
) {
299 while (front
< back
&& !eol
) {
300 if (putchar(*front
) == EOF
)
301 err(EXIT_FAILURE
, "stdout");
302 if (*front
++ == '\n')
306 SKIP_PAST_NEWLINE(front
, back
);
311 * Return LESS, GREATER, or EQUAL depending on how string compares with
312 * string2 (s1 ??? s2).
314 * o Matches up to len(s1) are EQUAL.
315 * o Matches up to len(s2) are GREATER.
317 * Compare understands about the -f and -d flags, and treats comparisons
320 * The string "string" is null terminated. The string "s2" is '\n' terminated
321 * (or "s2end" terminated).
323 * We use strcasecmp etc, since it knows how to ignore case also
327 compare(char *s2
, char *s2end
) {
331 /* copy, ignoring things that should be ignored */
334 while(s2
< s2end
&& *s2
!= '\n' && i
) {
335 if (!dflag
|| isalnum(*s2
) || isblank(*s2
))
346 i
= strncasecmp(comparbuf
, string
, stringlen
);
348 i
= strncmp(comparbuf
, string
, stringlen
);
350 return ((i
> 0) ? LESS
: (i
< 0) ? GREATER
: EQUAL
);
353 static void __attribute__((__noreturn__
)) usage(void)
356 fputs(USAGE_HEADER
, out
);
357 fprintf(out
, _(" %s [options] <string> [<file>...]\n"), program_invocation_short_name
);
359 fputs(USAGE_SEPARATOR
, out
);
360 fputs(_("Display lines beginning with a specified string.\n"), out
);
362 fputs(USAGE_OPTIONS
, out
);
363 fputs(_(" -a, --alternative use the alternative dictionary\n"), out
);
364 fputs(_(" -d, --alphanum compare only blanks and 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
);
368 fputs(USAGE_SEPARATOR
, out
);
369 printf(USAGE_HELP_OPTIONS(26));
370 printf(USAGE_MAN_TAIL("look(1)"));