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"
70 /* uglified the source a bit with globals, so that we only need
71 to allocate comparbuf once */
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
);
138 case 2: /* Don't set -df for user. */
142 case 1: /* But set -df by default. */
150 if (termchar
!= '\0' && (p
= strchr(string
, termchar
)) != NULL
)
153 if ((fd
= open(file
, O_RDONLY
, 0)) < 0 || fstat(fd
, &sb
))
154 err(EXIT_FAILURE
, "%s", file
);
155 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
);
169 /* workaround for mmap problem (rmiller@duskglow.com) */
170 if (front
== (void *)0)
174 back
= front
+ sb
.st_size
;
175 return look(front
, back
);
179 look(char *front
, char *back
)
182 char *readp
, *writep
;
184 /* Reformat string string to avoid doing it multiple times later. */
186 for (readp
= writep
= string
; (ch
= *readp
++) != 0;) {
191 stringlen
= writep
- string
;
193 stringlen
= strlen(string
);
195 comparbuf
= xmalloc(stringlen
+1);
197 front
= binary_search(front
, back
);
198 front
= linear_search(front
, back
);
201 print_from(front
, back
);
205 return (front
? 0 : 1);
210 * Binary search for "string" in memory between "front" and "back".
212 * This routine is expected to return a pointer to the start of a line at
213 * *or before* the first word matching "string". Relaxing the constraint
214 * this way simplifies the algorithm.
217 * front points to the beginning of a line at or before the first
220 * back points to the beginning of a line at or after the first
223 * Advancing the Invariants:
225 * p = first newline after halfway point from front to back.
227 * If the string at "p" is not greater than the string to match,
228 * p is the new front. Otherwise it is the new back.
232 * The definition of the routine allows it return at any point,
233 * since front is always at or before the line to print.
235 * In fact, it returns when the chosen "p" equals "back". This
236 * implies that there exists a string is least half as long as
237 * (back - front), which in turn implies that a linear search will
238 * be no more expensive than the cost of simply printing a string or two.
240 * Trying to continue with binary search at this point would be
241 * more trouble than it's worth.
243 #define SKIP_PAST_NEWLINE(p, back) \
244 while (p < back && *p++ != '\n')
247 binary_search(char *front
, char *back
)
251 p
= front
+ (back
- front
) / 2;
252 SKIP_PAST_NEWLINE(p
, back
);
255 * If the file changes underneath us, make sure we don't
258 while (p
< back
&& back
> front
) {
259 if (compare(p
, back
) == GREATER
)
263 p
= front
+ (back
- front
) / 2;
264 SKIP_PAST_NEWLINE(p
, back
);
270 * Find the first line that starts with string, linearly searching from front
273 * Return NULL for no such line.
275 * This routine assumes:
277 * o front points at the first character in a line.
278 * o front is before or at the first line to be printed.
281 linear_search(char *front
, char *back
)
283 while (front
< back
) {
284 switch (compare(front
, back
)) {
285 case EQUAL
: /* Found it. */
288 case LESS
: /* No such string. */
291 case GREATER
: /* Keep going. */
294 SKIP_PAST_NEWLINE(front
, back
);
300 * Print as many lines as match string, starting at front.
303 print_from(char *front
, char *back
)
307 while (front
< back
&& compare(front
, back
) == EQUAL
) {
308 if (compare(front
, back
) == EQUAL
) {
310 while (front
< back
&& !eol
) {
311 if (putchar(*front
) == EOF
)
312 err(EXIT_FAILURE
, "stdout");
313 if (*front
++ == '\n')
317 SKIP_PAST_NEWLINE(front
, back
);
322 * Return LESS, GREATER, or EQUAL depending on how string compares with
323 * string2 (s1 ??? s2).
325 * o Matches up to len(s1) are EQUAL.
326 * o Matches up to len(s2) are GREATER.
328 * Compare understands about the -f and -d flags, and treats comparisons
331 * The string "string" is null terminated. The string "s2" is '\n' terminated
332 * (or "s2end" terminated).
334 * We use strcasecmp etc, since it knows how to ignore case also
338 compare(char *s2
, char *s2end
) {
342 /* copy, ignoring things that should be ignored */
345 while(s2
< s2end
&& *s2
!= '\n' && i
) {
346 if (!dflag
|| isalnum(*s2
))
357 i
= strncasecmp(comparbuf
, string
, stringlen
);
359 i
= strncmp(comparbuf
, string
, stringlen
);
361 return ((i
> 0) ? LESS
: (i
< 0) ? GREATER
: EQUAL
);
364 static void __attribute__ ((__noreturn__
)) usage(FILE * out
)
366 fputs(_("\nUsage:\n"), out
),
368 _(" %s [options] string [file]\n"), program_invocation_short_name
);
370 fputs(_("\nOptions:\n"), out
);
371 fputs(_(" -a, --alternative use alternative dictionary\n"
372 " -d, --alphanum compare only alphanumeric characters\n"
373 " -f, --ignore-case ignore case differences when comparing\n"
374 " -t, --terminate <char> define string termination character\n"
375 " -V, --version output version information and exit\n"
376 " -h, --help display this help and exit\n\n"), out
);
378 exit(out
== stderr
? EXIT_FAILURE
: EXIT_SUCCESS
);