look.c revision 1.1 
1/*	$OpenBSD: look.c,v 1.1 2002/03/01 22:01:11 millert Exp $	*/
2
3/*-
4 * Copyright (c) 1991, 1993
5 *	The Regents of the University of California.  All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * David Hitz of Auspex Systems, Inc.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 * 3. All advertising materials mentioning features or use of this software
19 *    must display the following acknowledgement:
20 *	This product includes software developed by the University of
21 *	California, Berkeley and its contributors.
22 * 4. Neither the name of the University nor the names of its contributors
23 *    may be used to endorse or promote products derived from this software
24 *    without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * SUCH DAMAGE.
37 */
38
39#ifndef lint
40#if 0
41static const char sccsid[] = "@(#)look.c	8.2 (Berkeley) 5/4/95";
42#endif
43static const char rcsid[] = "$OpenBSD: look.c,v 1.1 2002/03/01 22:01:11 millert Exp $";
44#endif /* not lint */
45
46#include <sys/types.h>
47#include <ctype.h>
48#include <stdio.h>
49#include <stdlib.h>
50#include <string.h>
51#include <err.h>
52
53u_char	*binary_search(u_char *, u_char *, u_char *);
54u_char	*linear_search(u_char *, u_char *, u_char *);
55int	 compare(u_char *, u_char *, u_char *);
56int	 look(u_char *, u_char *, u_char *);
57
58int
59look(u_char *string, u_char *front, u_char *back)
60{
61	u_char *s;
62
63	/* Convert string to lower case before searching. */
64	for (s = string; *s; s++) {
65		if (isupper(*s))
66			*s = _tolower(*s);
67	}
68
69	front = binary_search(string, front, back);
70	front = linear_search(string, front, back);
71
72	return (front != NULL);
73}
74
75/*
76 * Binary search for "string" in memory between "front" and "back".
77 *
78 * This routine is expected to return a pointer to the start of a line at
79 * *or before* the first word matching "string".  Relaxing the constraint
80 * this way simplifies the algorithm.
81 *
82 * Invariants:
83 * 	front points to the beginning of a line at or before the first
84 *	matching string.
85 *
86 * 	back points to the beginning of a line at or after the first
87 *	matching line.
88 *
89 * Base of the Invariants.
90 * 	front = NULL;
91 *	back = EOF;
92 *
93 * Advancing the Invariants:
94 *
95 * 	p = first newline after halfway point from front to back.
96 *
97 * 	If the string at "p" is not greater than the string to match,
98 *	p is the new front.  Otherwise it is the new back.
99 *
100 * Termination:
101 *
102 * 	The definition of the routine allows it return at any point,
103 *	since front is always at or before the line to print.
104 *
105 * 	In fact, it returns when the chosen "p" equals "back".  This
106 *	implies that there exists a string is least half as long as
107 *	(back - front), which in turn implies that a linear search will
108 *	be no more expensive than the cost of simply printing a string or two.
109 *
110 * 	Trying to continue with binary search at this point would be
111 *	more trouble than it's worth.
112 */
113#define	SKIP_PAST_NEWLINE(p, back) \
114	while (p < back && *p++ != '\n');
115
116u_char *
117binary_search(u_char *string, u_char *front, u_char *back)
118{
119	u_char *p;
120
121	p = front + (back - front) / 2;
122	SKIP_PAST_NEWLINE(p, back);
123
124	/*
125	 * If the file changes underneath us, make sure we don't
126	 * infinitely loop.
127	 */
128	while (p < back && back > front) {
129		if (compare(string, p, back) > 0)
130			front = p;
131		else
132			back = p;
133		p = front + (back - front) / 2;
134		SKIP_PAST_NEWLINE(p, back);
135	}
136	return (front);
137}
138
139/*
140 * Find the first line that matches string, linearly searching from front
141 * to back.
142 *
143 * Return NULL for no such line.
144 *
145 * This routine assumes:
146 *
147 * 	o front points at the first character in a line.
148 *	o front is before or at the first line to be printed.
149 */
150u_char *
151linear_search(u_char *string, u_char *front, u_char *back)
152{
153	int result;
154
155	while (front < back) {
156		result = compare(string, front, back);
157		if (result == 0)
158			return(front);	/* found it */
159		if (result < 0)
160			return(NULL);	/* not there */
161
162		SKIP_PAST_NEWLINE(front, back);
163	}
164	return (NULL);
165}
166
167int
168compare(u_char *s1, u_char *s2, u_char *back)
169{
170	int ch;
171
172	/* Note that s1 is already upper case. */
173	for (;; ++s1, ++s2) {
174		if (*s2 == '\n' || s2 == back)
175			ch = '\0';
176		else if (isupper(*s2))
177			ch = _tolower(*s2);
178		else
179			ch = *s2;
180		if (*s1 != ch)
181			return(*s1 - ch);
182		if (ch == '\0')
183			return(0);
184	}
185}
186