1 /* $NetBSD: look.c,v 1.2 2005/06/30 16:25:05 christos Exp $ */
2
3 /* derived from: OpenBSD: look.c,v 1.3 2003/06/03 02:56:16 millert Exp */
4
5 /*-
6 * Copyright (c) 1991, 1993
7 * The Regents of the University of California. All rights reserved.
8 *
9 * This code is derived from software contributed to Berkeley by
10 * David Hitz of Auspex Systems, Inc.
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 * 3. 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
38 #if 0
39 static const char sccsid[] = "@(#)look.c 8.2 (Berkeley) 5/4/95";
40 #endif
41 static const char rcsid[] = "$NetBSD: look.c,v 1.2 2005/06/30 16:25:05 christos Exp $";
42 #endif /* not lint */
43
44 #include <sys/types.h>
45 #include <ctype.h>
46 #include <stdio.h>
47 #include <stdlib.h>
48 #include <string.h>
49 #include <err.h>
50
51 #include "extern.h"
52
53 static u_char *binary_search(u_char *, u_char *, u_char *);
54 static u_char *linear_search(u_char *, u_char *, u_char *);
55 static int compare(u_char *, u_char *, u_char *);
56
57 int
look(u_char * string,u_char * front,u_char * back)58 look(u_char *string, u_char *front, u_char *back)
59 {
60 u_char *s;
61
62 /* Convert string to lower case before searching. */
63 for (s = string; *s; s++) {
64 if (isupper(*s))
65 *s = _tolower(*s);
66 }
67
68 front = binary_search(string, front, back);
69 front = linear_search(string, front, back);
70
71 return (front != NULL);
72 }
73
74 /*
75 * Binary search for "string" in memory between "front" and "back".
76 *
77 * This routine is expected to return a pointer to the start of a line at
78 * *or before* the first word matching "string". Relaxing the constraint
79 * this way simplifies the algorithm.
80 *
81 * Invariants:
82 * front points to the beginning of a line at or before the first
83 * matching string.
84 *
85 * back points to the beginning of a line at or after the first
86 * matching line.
87 *
88 * Base of the Invariants.
89 * front = NULL;
90 * back = EOF;
91 *
92 * Advancing the Invariants:
93 *
94 * p = first newline after halfway point from front to back.
95 *
96 * If the string at "p" is not greater than the string to match,
97 * p is the new front. Otherwise it is the new back.
98 *
99 * Termination:
100 *
101 * The definition of the routine allows it return at any point,
102 * since front is always at or before the line to print.
103 *
104 * In fact, it returns when the chosen "p" equals "back". This
105 * implies that there exists a string is least half as long as
106 * (back - front), which in turn implies that a linear search will
107 * be no more expensive than the cost of simply printing a string or two.
108 *
109 * Trying to continue with binary search at this point would be
110 * more trouble than it's worth.
111 */
112 #define SKIP_PAST_NEWLINE(p, back) \
113 while (p < back && *p++ != '\n') \
114 continue;
115
116 static u_char *
binary_search(u_char * string,u_char * front,u_char * back)117 binary_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 */
150 static u_char *
linear_search(u_char * string,u_char * front,u_char * back)151 linear_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
167 static int
compare(u_char * s1,u_char * s2,u_char * back)168 compare(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