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(FILE * out
);
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 atexit(close_stdout
);
105 setlocale(LC_ALL
, "");
109 string
= NULL
; /* just for gcc */
111 while ((ch
= getopt_long(argc
, argv
, "adft:Vh", longopts
, NULL
)) != -1)
114 file
= _PATH_WORDS_ALT
;
126 printf(UTIL_LINUX_VERSION
);
131 errtryhelp(EXIT_FAILURE
);
137 case 2: /* Don't set -df for user. */
141 case 1: /* But set -df by default. */
149 if (termchar
!= '\0' && (p
= strchr(string
, termchar
)) != NULL
)
152 if ((fd
= open(file
, O_RDONLY
, 0)) < 0 || fstat(fd
, &sb
))
153 err(EXIT_FAILURE
, "%s", file
);
154 front
= mmap(NULL
, (size_t) sb
.st_size
, PROT_READ
,
155 MAP_SHARED
, fd
, (off_t
) 0);
158 (front
== MAP_FAILED
)
160 ((void *)(front
) <= (void *)0)
162 err(EXIT_FAILURE
, "%s", file
);
163 back
= front
+ sb
.st_size
;
164 return look(front
, back
);
168 look(char *front
, char *back
)
171 char *readp
, *writep
;
173 /* Reformat string to avoid doing it multiple times later. */
175 for (readp
= writep
= string
; (ch
= *readp
++) != 0;) {
176 if (isalnum(ch
) || isblank(ch
))
180 stringlen
= writep
- string
;
182 stringlen
= strlen(string
);
184 comparbuf
= xmalloc(stringlen
+1);
186 front
= binary_search(front
, back
);
187 front
= linear_search(front
, back
);
190 print_from(front
, back
);
194 return (front
? 0 : 1);
199 * Binary search for "string" in memory between "front" and "back".
201 * This routine is expected to return a pointer to the start of a line at
202 * *or before* the first word matching "string". Relaxing the constraint
203 * this way simplifies the algorithm.
206 * front points to the beginning of a line at or before the first
209 * back points to the beginning of a line at or after the first
212 * Advancing the Invariants:
214 * p = first newline after halfway point from front to back.
216 * If the string at "p" is not greater than the string to match,
217 * p is the new front. Otherwise it is the new back.
221 * The definition of the routine allows it return at any point,
222 * since front is always at or before the line to print.
224 * In fact, it returns when the chosen "p" equals "back". This
225 * implies that there exists a string is least half as long as
226 * (back - front), which in turn implies that a linear search will
227 * be no more expensive than the cost of simply printing a string or two.
229 * Trying to continue with binary search at this point would be
230 * more trouble than it's worth.
232 #define SKIP_PAST_NEWLINE(p, back) \
233 while (p < back && *p++ != '\n')
236 binary_search(char *front
, char *back
)
240 p
= front
+ (back
- front
) / 2;
241 SKIP_PAST_NEWLINE(p
, back
);
244 * If the file changes underneath us, make sure we don't
247 while (p
< back
&& back
> front
) {
248 if (compare(p
, back
) == GREATER
)
252 p
= front
+ (back
- front
) / 2;
253 SKIP_PAST_NEWLINE(p
, back
);
259 * Find the first line that starts with string, linearly searching from front
262 * Return NULL for no such line.
264 * This routine assumes:
266 * o front points at the first character in a line.
267 * o front is before or at the first line to be printed.
270 linear_search(char *front
, char *back
)
272 while (front
< back
) {
273 switch (compare(front
, back
)) {
274 case EQUAL
: /* Found it. */
276 case LESS
: /* No such string. */
278 case GREATER
: /* Keep going. */
281 SKIP_PAST_NEWLINE(front
, back
);
287 * Print as many lines as match string, starting at front.
290 print_from(char *front
, char *back
)
294 while (front
< back
&& compare(front
, back
) == EQUAL
) {
295 if (compare(front
, back
) == EQUAL
) {
297 while (front
< back
&& !eol
) {
298 if (putchar(*front
) == EOF
)
299 err(EXIT_FAILURE
, "stdout");
300 if (*front
++ == '\n')
304 SKIP_PAST_NEWLINE(front
, back
);
309 * Return LESS, GREATER, or EQUAL depending on how string compares with
310 * string2 (s1 ??? s2).
312 * o Matches up to len(s1) are EQUAL.
313 * o Matches up to len(s2) are GREATER.
315 * Compare understands about the -f and -d flags, and treats comparisons
318 * The string "string" is null terminated. The string "s2" is '\n' terminated
319 * (or "s2end" terminated).
321 * We use strcasecmp etc, since it knows how to ignore case also
325 compare(char *s2
, char *s2end
) {
329 /* copy, ignoring things that should be ignored */
332 while(s2
< s2end
&& *s2
!= '\n' && i
) {
333 if (!dflag
|| isalnum(*s2
) || isblank(*s2
))
344 i
= strncasecmp(comparbuf
, string
, stringlen
);
346 i
= strncmp(comparbuf
, string
, stringlen
);
348 return ((i
> 0) ? LESS
: (i
< 0) ? GREATER
: EQUAL
);
351 static void __attribute__ ((__noreturn__
)) usage(FILE * out
)
353 fputs(USAGE_HEADER
, out
);
354 fprintf(out
, _(" %s [options] <string> [<file>...]\n"), program_invocation_short_name
);
356 fputs(USAGE_SEPARATOR
, out
);
357 fputs(_("Display lines beginning with a specified string.\n"), out
);
359 fputs(USAGE_OPTIONS
, out
);
360 fputs(_(" -a, --alternative use the alternative dictionary\n"), out
);
361 fputs(_(" -d, --alphanum compare only blanks and alphanumeric characters\n"), out
);
362 fputs(_(" -f, --ignore-case ignore case differences when comparing\n"), out
);
363 fputs(_(" -t, --terminate <char> define the string-termination character\n"), out
);
365 fputs(USAGE_SEPARATOR
, out
);
366 fputs(USAGE_HELP
, out
);
367 fputs(USAGE_VERSION
, out
);
368 fprintf(out
, USAGE_MAN_TAIL("look(1)"));
370 exit(out
== stderr
? EXIT_FAILURE
: EXIT_SUCCESS
);