* Copyright (c) 1991 The Regents of the University of California.
* This code is derived from software contributed to Berkeley by
* David Hitz of Auspex Systems, Inc.
* %sccs.include.redist.c%
"@(#) Copyright (c) 1991 The Regents of the University of California.\n\
static char sccsid
[] = "@(#)look.c 5.1 (Berkeley) %G%";
* look -- find lines in a sorted list.
* The man page said that TABs and SPACEs participate in -d comparisons.
* In fact, they were ignored. This implements historic practice, not
* FOLD and DICT convert characters to a normal form for comparison,
* according to the user specified flags.
* DICT expects integers because it uses a non-character value to
* indicate a character which should not participate in comparisons.
#define FOLD(c) (isascii(c) && isupper(c) ? tolower(c) : (c))
#define DICT(c) (isascii(c) && isalnum(c) ? (c) : NO_COMPARE)
char *binary_search
__P((char *, char *, char *));
int compare
__P((char *, char *, char *));
void err
__P((const char *fmt
, ...));
char *linear_search
__P((char *, char *, char *));
int look
__P((char *, char *, char *));
void print_from
__P((char *, char *, char *));
char *back
, *file
, *front
, *string
;
while ((ch
= getopt(argc
, argv
, "df")) != EOF
)
case 2: /* Don't set -df for user. */
case 1: /* But set -df by default. */
if ((fd
= open(file
, O_RDONLY
, 0)) < 0 || fstat(fd
, &sb
) ||
(front
= mmap(NULL
, sb
.st_size
, PROT_READ
, MAP_FILE
, fd
,
err("%s: %s", file
, strerror(errno
));
back
= front
+ sb
.st_size
;
exit(look(string
, front
, back
));
look(string
, front
, back
)
char *string
, *front
, *back
;
register char *readp
, *writep
;
/* Reformat string string to avoid doing it multiple times later. */
for (readp
= writep
= string
; ch
= *readp
++;) {
front
= binary_search(string
, front
, back
);
front
= linear_search(string
, front
, back
);
print_from(string
, front
, back
);
* Binary search for "string" in memory between "front" and "back".
* This routine is expected to return a pointer to the start of a line at
* *or before* the first word matching "string". Relaxing the constraint
* this way simplifies the algorithm.
* front points to the beginning of a line at or before the first
* back points to the beginning of a line at or after the first
* Base of the Invariants.
* Advancing the Invariants:
* p = first newline after halfway point from front to back.
* If the string at "p" is not greater than the string to match,
* p is the new front. Otherwise it is the new back.
* The definition of the routine allows it return at any point,
* since front is always at or before the line to print.
* In fact, it returns when the chosen "p" equals "back". This
* implies that there exists a string is least half as long as
* (back - front), which in turn implies that a linear search will
* be no more expensive than the cost of simply printing a string or two.
* Trying to continue with binary search at this point would be
* more trouble than it's worth.
#define SKIP_PAST_NEWLINE(p, back) \
while (p < back && *p++ != '\n');
binary_search(string
, front
, back
)
register char *string
, *front
, *back
;
p
= front
+ (back
- front
) / 2;
SKIP_PAST_NEWLINE(p
, back
);
if (compare(string
, p
, back
) == GREATER
)
p
= front
+ (back
- front
) / 2;
SKIP_PAST_NEWLINE(p
, back
);
* Find the first line that starts with string, linearly searching from front
* Return NULL for no such line.
* o front points at the first character in a line.
* o front is before or at the first line to be printed.
linear_search(string
, front
, back
)
char *string
, *front
, *back
;
switch (compare(string
, front
, back
)) {
case EQUAL
: /* Found it. */
case LESS
: /* No such string. */
case GREATER
: /* Keep going. */
SKIP_PAST_NEWLINE(front
, back
);
* Print as many lines as match string, starting at front.
print_from(string
, front
, back
)
register char *string
, *front
, *back
;
for (; front
< back
&& compare(string
, front
, back
) == EQUAL
; ++front
) {
for (; front
< back
&& *front
!= '\n'; ++front
)
if (putchar(*front
) == EOF
)
err("stdout: %s", strerror(errno
));
if (putchar('\n') == EOF
)
err("stdout: %s", strerror(errno
));
* Return LESS, GREATER, or EQUAL depending on how the string1 compares with
* o Matches up to len(s1) are EQUAL.
* o Matches up to len(s2) are GREATER.
* Compare understands about the -f and -d flags, and treats comparisons
* The string "s1" is null terminated. The string s2 is '\n' terminated (or
register char *s1
, *s2
, *back
;
for (; *s1
&& s2
< back
&& *s2
!= '\n'; ++s1
, ++s2
) {
++s2
; /* Ignore character in comparison. */
return (*s1
< ch
? LESS
: GREATER
);
return (*s1
? GREATER
: EQUAL
);
(void)fprintf(stderr
, "usage: look [-df] string [file]\n");
err(const char *fmt
, ...)
(void)fprintf(stderr
, "look: ");
(void)vfprintf(stderr
, fmt
, ap
);
(void)fprintf(stderr
, "\n");