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
42u_char	*binary_search(u_char *, u_char *, u_char *);
43u_char	*linear_search(u_char *, u_char *, u_char *);
44int	 compare(u_char *, u_char *, u_char *);
45int	 look(u_char *, u_char *, u_char *);
46
47int
48look(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
105u_char *
106binary_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 */
139u_char *
140linear_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
156int
157compare(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