]>
git.ipfire.org Git - thirdparty/util-linux.git/blob - misc-utils/look.c
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
38 static char copyright
[] =
39 "@(#) Copyright (c) 1991, 1993\n\
40 The Regents of the University of California. All rights reserved.\n";
44 static char sccsid
[] = "@(#)look.c 8.1 (Berkeley) 6/14/93";
48 * look -- find lines in a sorted list.
50 * The man page said that TABs and SPACEs participate in -d comparisons.
51 * In fact, they were ignored. This implements historic practice, not
55 #include <sys/types.h>
67 #include "pathnames.h"
70 * FOLD and DICT convert characters to a normal form for comparison,
71 * according to the user specified flags.
73 * DICT expects integers because it uses a non-character value to
74 * indicate a character which should not participate in comparisons.
79 #define NO_COMPARE (-2)
81 #define FOLD(c) (isascii(c) && isupper(c) ? tolower(c) : (c))
82 #define DICT(c) (isascii(c) && isalnum(c) ? (c) : NO_COMPARE)
86 char *binary_search
__P((char *, char *, char *));
87 int compare
__P((char *, char *, char *));
88 void err
__P((const char *fmt
, ...));
89 char *linear_search
__P((char *, char *, char *));
90 int look
__P((char *, char *, char *));
91 void print_from
__P((char *, char *, char *));
93 static void usage
__P((void));
101 int ch
, fd
, termchar
;
102 char *back
, *file
, *front
, *string
, *p
;
106 string
= NULL
; /* just for gcc */
108 while ((ch
= getopt(argc
, argv
, "adft:")) != EOF
)
111 file
= _PATH_WORDS_ALT
;
130 case 2: /* Don't set -df for user. */
134 case 1: /* But set -df by default. */
142 if (termchar
!= '\0' && (p
= strchr(string
, termchar
)) != NULL
)
145 if ((fd
= open(file
, O_RDONLY
, 0)) < 0 || fstat(fd
, &sb
))
146 err("%s: %s", file
, strerror(errno
));
147 if ((void *)(front
= mmap(NULL
,
152 (off_t
)0)) <= (void *)0)
153 err("%s: %s", file
, strerror(errno
));
154 back
= front
+ sb
.st_size
;
155 exit(look(string
, front
, back
));
159 look(string
, front
, back
)
160 char *string
, *front
, *back
;
163 register char *readp
, *writep
;
165 /* Reformat string string to avoid doing it multiple times later. */
166 for (readp
= writep
= string
; (ch
= *readp
++) != 0;) {
171 if (ch
!= NO_COMPARE
)
176 front
= binary_search(string
, front
, back
);
177 front
= linear_search(string
, front
, back
);
180 print_from(string
, front
, back
);
181 return (front
? 0 : 1);
186 * Binary search for "string" in memory between "front" and "back".
188 * This routine is expected to return a pointer to the start of a line at
189 * *or before* the first word matching "string". Relaxing the constraint
190 * this way simplifies the algorithm.
193 * front points to the beginning of a line at or before the first
196 * back points to the beginning of a line at or after the first
199 * Base of the Invariants.
203 * Advancing the Invariants:
205 * p = first newline after halfway point from front to back.
207 * If the string at "p" is not greater than the string to match,
208 * p is the new front. Otherwise it is the new back.
212 * The definition of the routine allows it return at any point,
213 * since front is always at or before the line to print.
215 * In fact, it returns when the chosen "p" equals "back". This
216 * implies that there exists a string is least half as long as
217 * (back - front), which in turn implies that a linear search will
218 * be no more expensive than the cost of simply printing a string or two.
220 * Trying to continue with binary search at this point would be
221 * more trouble than it's worth.
223 #define SKIP_PAST_NEWLINE(p, back) \
224 while (p < back && *p++ != '\n');
227 binary_search(string
, front
, back
)
228 register char *string
, *front
, *back
;
232 p
= front
+ (back
- front
) / 2;
233 SKIP_PAST_NEWLINE(p
, back
);
236 * If the file changes underneath us, make sure we don't
239 while (p
< back
&& back
> front
) {
240 if (compare(string
, p
, back
) == GREATER
)
244 p
= front
+ (back
- front
) / 2;
245 SKIP_PAST_NEWLINE(p
, back
);
251 * Find the first line that starts with string, linearly searching from front
254 * Return NULL for no such line.
256 * This routine assumes:
258 * o front points at the first character in a line.
259 * o front is before or at the first line to be printed.
262 linear_search(string
, front
, back
)
263 char *string
, *front
, *back
;
265 while (front
< back
) {
266 switch (compare(string
, front
, back
)) {
267 case EQUAL
: /* Found it. */
270 case LESS
: /* No such string. */
273 case GREATER
: /* Keep going. */
276 SKIP_PAST_NEWLINE(front
, back
);
282 * Print as many lines as match string, starting at front.
285 print_from(string
, front
, back
)
286 register char *string
, *front
, *back
;
288 for (; front
< back
&& compare(string
, front
, back
) == EQUAL
; ++front
) {
289 for (; front
< back
&& *front
!= '\n'; ++front
)
290 if (putchar(*front
) == EOF
)
291 err("stdout: %s", strerror(errno
));
292 if (putchar('\n') == EOF
)
293 err("stdout: %s", strerror(errno
));
298 * Return LESS, GREATER, or EQUAL depending on how the string1 compares with
299 * string2 (s1 ??? s2).
301 * o Matches up to len(s1) are EQUAL.
302 * o Matches up to len(s2) are GREATER.
304 * Compare understands about the -f and -d flags, and treats comparisons
307 * The string "s1" is null terminated. The string s2 is '\n' terminated (or
308 * "back" terminated).
311 compare(s1
, s2
, back
)
312 register char *s1
, *s2
, *back
;
316 for (; *s1
&& s2
< back
&& *s2
!= '\n';) {
323 if (ch
== NO_COMPARE
) {
324 ++s2
; /* Ignore character in comparison. */
328 return (*s1
< ch
? LESS
: GREATER
);
332 return (*s1
? GREATER
: EQUAL
);
338 (void)fprintf(stderr
, "usage: look [-dfa] [-t char] string [file]\n");
350 err(const char *fmt
, ...)
363 (void)fprintf(stderr
, "look: ");
364 (void)vfprintf(stderr
, fmt
, ap
);
366 (void)fprintf(stderr
, "\n");