look.c revision 21786 
1/*-
2 * Copyright (c) 1991, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * David Hitz of Auspex Systems, Inc.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
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.
23 *
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
34 * SUCH DAMAGE.
35 */
36
37#ifndef lint
38static char copyright[] =
39"@(#) Copyright (c) 1991, 1993\n\
40	The Regents of the University of California.  All rights reserved.\n";
41#endif /* not lint */
42
43#ifndef lint
44static char sccsid[] = "@(#)look.c	8.1 (Berkeley) 6/14/93";
45#endif /* not lint */
46
47/*
48 * look -- find lines in a sorted list.
49 *
50 * The man page said that TABs and SPACEs participate in -d comparisons.
51 * In fact, they were ignored.  This implements historic practice, not
52 * the manual page.
53 */
54
55#include <sys/types.h>
56#include <sys/mman.h>
57#include <sys/stat.h>
58
59#include <limits.h>
60#include <locale.h>
61#include <errno.h>
62#include <fcntl.h>
63#include <stdio.h>
64#include <stdlib.h>
65#include <string.h>
66#include <ctype.h>
67#include "pathnames.h"
68
69/*
70 * FOLD and DICT convert characters to a normal form for comparison,
71 * according to the user specified flags.
72 *
73 * DICT expects integers because it uses a non-character value to
74 * indicate a character which should not participate in comparisons.
75 */
76#define	EQUAL		0
77#define	GREATER		1
78#define	LESS		(-1)
79#define NO_COMPARE	(-2)
80
81#define FOLD(c) (isupper(c) ? tolower(c) : (unsigned char) (c))
82#define DICT(c) (isalnum(c) ? (c) & 0xFF /* int */ : NO_COMPARE)
83
84int dflag, fflag;
85
86char    *binary_search __P((unsigned char *, unsigned char *, unsigned char *));
87int      compare __P((unsigned char *, unsigned char *, unsigned char *));
88void	 err __P((const char *fmt, ...));
89char    *linear_search __P((unsigned char *, unsigned char *, unsigned char *));
90int      look __P((unsigned char *, unsigned char *, unsigned char *));
91void     print_from __P((unsigned char *, unsigned char *, unsigned char *));
92
93static void usage __P((void));
94
95main(argc, argv)
96	int argc;
97	char *argv[];
98{
99	struct stat sb;
100	int ch, fd, termchar;
101	unsigned char *back, *file, *front, *string, *p;
102
103	(void) setlocale(LC_CTYPE, "");
104
105	file = _PATH_WORDS;
106	termchar = '\0';
107	while ((ch = getopt(argc, argv, "dft:")) != EOF)
108		switch(ch) {
109		case 'd':
110			dflag = 1;
111			break;
112		case 'f':
113			fflag = 1;
114			break;
115		case 't':
116			termchar = *optarg;
117			break;
118		case '?':
119		default:
120			usage();
121		}
122	argc -= optind;
123	argv += optind;
124
125	switch (argc) {
126	case 2:				/* Don't set -df for user. */
127		string = *argv++;
128		file = *argv;
129		break;
130	case 1:				/* But set -df by default. */
131		dflag = fflag = 1;
132		string = *argv;
133		break;
134	default:
135		usage();
136	}
137
138	if (termchar != '\0' && (p = strchr(string, termchar)) != NULL)
139		*++p = '\0';
140
141	if ((fd = open(file, O_RDONLY, 0)) < 0 || fstat(fd, &sb))
142		err("%s: %s", file, strerror(errno));
143	if (sb.st_size > SIZE_T_MAX)
144		err("%s: %s", file, strerror(EFBIG));
145	if ((front = mmap(NULL,
146	    (size_t)sb.st_size, PROT_READ, MAP_SHARED, fd, (off_t)0)) == MAP_FAILED)
147		err("%s: %s", file, strerror(errno));
148	back = front + sb.st_size;
149	exit(look(string, front, back));
150}
151
152look(string, front, back)
153	unsigned char *string, *front, *back;
154{
155	register int ch;
156	register unsigned char *readp, *writep;
157
158	/* Reformat string string to avoid doing it multiple times later. */
159	for (readp = writep = string; ch = *readp++;) {
160		if (fflag)
161			ch = FOLD(ch);
162		if (dflag)
163			ch = DICT(ch);
164		if (ch != NO_COMPARE)
165			*(writep++) = ch;
166	}
167	*writep = '\0';
168
169	front = binary_search(string, front, back);
170	front = linear_search(string, front, back);
171
172	if (front)
173		print_from(string, front, back);
174	return (front ? 0 : 1);
175}
176
177
178/*
179 * Binary search for "string" in memory between "front" and "back".
180 *
181 * This routine is expected to return a pointer to the start of a line at
182 * *or before* the first word matching "string".  Relaxing the constraint
183 * this way simplifies the algorithm.
184 *
185 * Invariants:
186 * 	front points to the beginning of a line at or before the first
187 *	matching string.
188 *
189 * 	back points to the beginning of a line at or after the first
190 *	matching line.
191 *
192 * Base of the Invariants.
193 * 	front = NULL;
194 *	back = EOF;
195 *
196 * Advancing the Invariants:
197 *
198 * 	p = first newline after halfway point from front to back.
199 *
200 * 	If the string at "p" is not greater than the string to match,
201 *	p is the new front.  Otherwise it is the new back.
202 *
203 * Termination:
204 *
205 * 	The definition of the routine allows it return at any point,
206 *	since front is always at or before the line to print.
207 *
208 * 	In fact, it returns when the chosen "p" equals "back".  This
209 *	implies that there exists a string is least half as long as
210 *	(back - front), which in turn implies that a linear search will
211 *	be no more expensive than the cost of simply printing a string or two.
212 *
213 * 	Trying to continue with binary search at this point would be
214 *	more trouble than it's worth.
215 */
216#define	SKIP_PAST_NEWLINE(p, back) \
217	while (p < back && *p++ != '\n');
218
219char *
220binary_search(string, front, back)
221	register unsigned char *string, *front, *back;
222{
223	register unsigned char *p;
224
225	p = front + (back - front) / 2;
226	SKIP_PAST_NEWLINE(p, back);
227
228	/*
229	 * If the file changes underneath us, make sure we don't
230	 * infinitely loop.
231	 */
232	while (p < back && back > front) {
233		if (compare(string, p, back) == GREATER)
234			front = p;
235		else
236			back = p;
237		p = front + (back - front) / 2;
238		SKIP_PAST_NEWLINE(p, back);
239	}
240	return (front);
241}
242
243/*
244 * Find the first line that starts with string, linearly searching from front
245 * to back.
246 *
247 * Return NULL for no such line.
248 *
249 * This routine assumes:
250 *
251 * 	o front points at the first character in a line.
252 *	o front is before or at the first line to be printed.
253 */
254char *
255linear_search(string, front, back)
256	unsigned char *string, *front, *back;
257{
258	while (front < back) {
259		switch (compare(string, front, back)) {
260		case EQUAL:		/* Found it. */
261			return (front);
262			break;
263		case LESS:		/* No such string. */
264			return (NULL);
265			break;
266		case GREATER:		/* Keep going. */
267			break;
268		}
269		SKIP_PAST_NEWLINE(front, back);
270	}
271	return (NULL);
272}
273
274/*
275 * Print as many lines as match string, starting at front.
276 */
277void
278print_from(string, front, back)
279	register unsigned char *string, *front, *back;
280{
281	for (; front < back && compare(string, front, back) == EQUAL; ++front) {
282		for (; front < back && *front != '\n'; ++front)
283			if (putchar(*front) == EOF)
284				err("stdout: %s", strerror(errno));
285		if (putchar('\n') == EOF)
286			err("stdout: %s", strerror(errno));
287	}
288}
289
290/*
291 * Return LESS, GREATER, or EQUAL depending on how the string1 compares with
292 * string2 (s1 ??? s2).
293 *
294 * 	o Matches up to len(s1) are EQUAL.
295 *	o Matches up to len(s2) are GREATER.
296 *
297 * Compare understands about the -f and -d flags, and treats comparisons
298 * appropriately.
299 *
300 * The string "s1" is null terminated.  The string s2 is '\n' terminated (or
301 * "back" terminated).
302 */
303int
304compare(s1, s2, back)
305	register unsigned char *s1, *s2, *back;
306{
307	register int ch;
308
309	for (; *s1 && s2 < back && *s2 != '\n'; ++s1, ++s2) {
310		ch = *s2;
311		if (fflag)
312			ch = FOLD(ch);
313		if (dflag)
314			ch = DICT(ch);
315
316		if (ch == NO_COMPARE) {
317			++s2;		/* Ignore character in comparison. */
318			continue;
319		}
320		if (*s1 != ch)
321			return (*s1 < ch ? LESS : GREATER);
322	}
323	return (*s1 ? GREATER : EQUAL);
324}
325
326static void
327usage()
328{
329	(void)fprintf(stderr, "usage: look [-df] [-t char] string [file]\n");
330	exit(2);
331}
332
333#if __STDC__
334#include <stdarg.h>
335#else
336#include <varargs.h>
337#endif
338
339void
340#if __STDC__
341err(const char *fmt, ...)
342#else
343err(fmt, va_alist)
344	char *fmt;
345	va_dcl
346#endif
347{
348	va_list ap;
349#if __STDC__
350	va_start(ap, fmt);
351#else
352	va_start(ap);
353#endif
354	(void)fprintf(stderr, "look: ");
355	(void)vfprintf(stderr, fmt, ap);
356	va_end(ap);
357	(void)fprintf(stderr, "\n");
358	exit(2);
359	/* NOTREACHED */
360}
361