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

Line Branch Exec Source
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
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 *
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 *
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
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
}