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