GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/look/look.c Lines: 0 75 0.0 %
Date: 2017-11-13 Branches: 0 86 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: look.c,v 1.21 2017/01/21 10:03:27 krw Exp $	*/
2
/*	$NetBSD: look.c,v 1.7 1995/08/31 22:41:02 jtc Exp $	*/
3
4
/*-
5
 * Copyright (c) 1991, 1993
6
 *	The Regents of the University of California.  All rights reserved.
7
 *
8
 * This code is derived from software contributed to Berkeley by
9
 * David Hitz of Auspex Systems, Inc.
10
 *
11
 * Redistribution and use in source and binary forms, with or without
12
 * modification, are permitted provided that the following conditions
13
 * are met:
14
 * 1. Redistributions of source code must retain the above copyright
15
 *    notice, this list of conditions and the following disclaimer.
16
 * 2. Redistributions in binary form must reproduce the above copyright
17
 *    notice, this list of conditions and the following disclaimer in the
18
 *    documentation and/or other materials provided with the distribution.
19
 * 3. Neither the name of the University nor the names of its contributors
20
 *    may be used to endorse or promote products derived from this software
21
 *    without specific prior written permission.
22
 *
23
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33
 * SUCH DAMAGE.
34
 */
35
36
/*
37
 * look -- find lines in a sorted list.
38
 *
39
 * The man page said that TABs and SPACEs participate in -d comparisons.
40
 * In fact, they were ignored.  This implements historic practice, not
41
 * the manual page.
42
 */
43
44
#include <sys/types.h>
45
#include <sys/mman.h>
46
#include <sys/stat.h>
47
48
#include <ctype.h>
49
#include <errno.h>
50
#include <fcntl.h>
51
#include <stdint.h>
52
#include <stdio.h>
53
#include <stdlib.h>
54
#include <string.h>
55
#include <unistd.h>
56
#include <err.h>
57
58
#include "pathnames.h"
59
60
#define	EQUAL		0
61
#define	GREATER		1
62
#define	LESS		(-1)
63
64
int dflag, fflag;
65
66
char	*binary_search(char *, char *, char *);
67
int	 compare(char *, char *, char *);
68
char	*linear_search(char *, char *, char *);
69
int	 look(char *, char *, char *);
70
void	 print_from(char *, char *, char *);
71
void	 usage(void);
72
73
int
74
main(int argc, char *argv[])
75
{
76
	struct stat sb;
77
	int ch, fd, termchar;
78
	char *back, *file, *front, *string, *p;
79
80
	if (pledge("stdio rpath flock cpath wpath", NULL) == -1)
81
		err(1, "pledge");
82
83
	file = _PATH_WORDS;
84
	termchar = '\0';
85
	while ((ch = getopt(argc, argv, "dft:")) != -1)
86
		switch(ch) {
87
		case 'd':
88
			dflag = 1;
89
			break;
90
		case 'f':
91
			fflag = 1;
92
			break;
93
		case 't':
94
			termchar = *optarg;
95
			break;
96
		case '?':
97
		default:
98
			usage();
99
		}
100
	argc -= optind;
101
	argv += optind;
102
103
	switch (argc) {
104
	case 2:				/* Don't set -df for user. */
105
		string = *argv++;
106
		file = *argv;
107
		break;
108
	case 1:				/* But set -df by default. */
109
		dflag = fflag = 1;
110
		string = *argv;
111
		break;
112
	default:
113
		usage();
114
	}
115
116
	if (termchar != '\0' && (p = strchr(string, termchar)) != NULL)
117
		*++p = '\0';
118
119
	if ((fd = open(file, O_RDONLY, 0)) < 0 || fstat(fd, &sb))
120
		err(2, "%s", file);
121
	if (sb.st_size > SIZE_MAX)
122
		errc(2, EFBIG, "%s", file);
123
	if ((front = mmap(NULL,
124
	    (size_t)sb.st_size, PROT_READ, MAP_PRIVATE, fd, (off_t)0)) == MAP_FAILED)
125
		err(2, "%s", file);
126
	back = front + sb.st_size;
127
	exit(look(string, front, back));
128
}
129
130
int
131
look(char *string, char *front, char *back)
132
{
133
	int ch;
134
	char *readp, *writep;
135
136
	/* Reformat string to avoid doing it multiple times later. */
137
	for (readp = writep = string; (ch = *readp++);) {
138
		if (fflag)
139
			ch = tolower((unsigned char)ch);
140
		if (!dflag || isalnum((unsigned char)ch))
141
			*(writep++) = ch;
142
	}
143
	*writep = '\0';
144
145
	front = binary_search(string, front, back);
146
	front = linear_search(string, front, back);
147
148
	if (front)
149
		print_from(string, front, back);
150
	return (front ? 0 : 1);
151
}
152
153
154
/*
155
 * Binary search for "string" in memory between "front" and "back".
156
 *
157
 * This routine is expected to return a pointer to the start of a line at
158
 * *or before* the first word matching "string".  Relaxing the constraint
159
 * this way simplifies the algorithm.
160
 *
161
 * Invariants:
162
 *	front points to the beginning of a line at or before the first
163
 *	matching string.
164
 *
165
 *	back points to the beginning of a line at or after the first
166
 *	matching line.
167
 *
168
 * Base of the Invariants.
169
 *	front = NULL;
170
 *	back = EOF;
171
 *
172
 * Advancing the Invariants:
173
 *
174
 *	p = first newline after halfway point from front to back.
175
 *
176
 *	If the string at "p" is not greater than the string to match,
177
 *	p is the new front.  Otherwise it is the new back.
178
 *
179
 * Termination:
180
 *
181
 *	The definition of the routine allows it return at any point,
182
 *	since front is always at or before the line to print.
183
 *
184
 *	In fact, it returns when the chosen "p" equals "back".  This
185
 *	implies that there exists a string is least half as long as
186
 *	(back - front), which in turn implies that a linear search will
187
 *	be no more expensive than the cost of simply printing a string or two.
188
 *
189
 *	Trying to continue with binary search at this point would be
190
 *	more trouble than it's worth.
191
 */
192
#define	SKIP_PAST_NEWLINE(p, back) \
193
	while (p < back && *p++ != '\n');
194
195
char *
196
binary_search(char *string, char *front, char *back)
197
{
198
	char *p;
199
200
	p = front + (back - front) / 2;
201
	SKIP_PAST_NEWLINE(p, back);
202
203
	/*
204
	 * If the file changes underneath us, make sure we don't
205
	 * infinitely loop.
206
	 */
207
	while (p < back && back > front) {
208
		if (compare(string, p, back) == GREATER)
209
			front = p;
210
		else
211
			back = p;
212
		p = front + (back - front) / 2;
213
		SKIP_PAST_NEWLINE(p, back);
214
	}
215
	return (front);
216
}
217
218
/*
219
 * Find the first line that starts with string, linearly searching from front
220
 * to back.
221
 *
222
 * Return NULL for no such line.
223
 *
224
 * This routine assumes:
225
 *
226
 *	o front points at the first character in a line.
227
 *	o front is before or at the first line to be printed.
228
 */
229
char *
230
linear_search(char *string, char *front, char *back)
231
{
232
	while (front < back) {
233
		switch (compare(string, front, back)) {
234
		case EQUAL:		/* Found it. */
235
			return (front);
236
			break;
237
		case LESS:		/* No such string. */
238
			return (NULL);
239
			break;
240
		case GREATER:		/* Keep going. */
241
			break;
242
		}
243
		SKIP_PAST_NEWLINE(front, back);
244
	}
245
	return (NULL);
246
}
247
248
/*
249
 * Print as many lines as match string, starting at front.
250
 */
251
void
252
print_from(char *string, char *front, char *back)
253
{
254
	for (; front < back && compare(string, front, back) == EQUAL; ++front) {
255
		for (; front < back && *front != '\n'; ++front)
256
			if (putchar(*front) == EOF)
257
				err(2, "stdout");
258
		if (putchar('\n') == EOF)
259
			err(2, "stdout");
260
	}
261
}
262
263
/*
264
 * Return LESS, GREATER, or EQUAL depending on how the string1 compares with
265
 * string2 (s1 ??? s2).
266
 *
267
 *	o Matches up to len(s1) are EQUAL.
268
 *	o Matches up to len(s2) are GREATER.
269
 *
270
 * Compare understands about the -f and -d flags, and treats comparisons
271
 * appropriately.
272
 *
273
 * The string "s1" is null terminated.  The string s2 is '\n' terminated (or
274
 * "back" terminated).
275
 */
276
int
277
compare(char *s1, char *s2, char *back)
278
{
279
	int ch;
280
281
	for (; *s1 && s2 < back && *s2 != '\n'; ++s1, ++s2) {
282
		ch = *s2;
283
		if (fflag)
284
			ch = tolower((unsigned char)ch);
285
		if (dflag && !isalnum((unsigned char)ch)) {
286
			++s2;		/* Ignore character in comparison. */
287
			continue;
288
		}
289
		if (*s1 != ch)
290
			return (*s1 < ch ? LESS : GREATER);
291
	}
292
	return (*s1 ? GREATER : EQUAL);
293
}
294
295
void
296
usage(void)
297
{
298
	(void)fprintf(stderr,
299
	    "usage: look [-df] [-t termchar] string [file]\n");
300
	exit(2);
301
}