Annotation of src/usr.bin/spell/look.c, Revision 1.3
1.3 ! millert 1: /* $OpenBSD: look.c,v 1.2 2002/06/03 17:53:32 kjell Exp $ */
1.1 millert 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.
1.3 ! millert 18: * 3. Neither the name of the University nor the names of its contributors
1.1 millert 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: #ifndef lint
36: #if 0
37: static const char sccsid[] = "@(#)look.c 8.2 (Berkeley) 5/4/95";
38: #endif
1.3 ! millert 39: static const char rcsid[] = "$OpenBSD: look.c,v 1.2 2002/06/03 17:53:32 kjell Exp $";
1.1 millert 40: #endif /* not lint */
41:
42: #include <sys/types.h>
43: #include <ctype.h>
44: #include <stdio.h>
45: #include <stdlib.h>
46: #include <string.h>
47: #include <err.h>
48:
49: u_char *binary_search(u_char *, u_char *, u_char *);
50: u_char *linear_search(u_char *, u_char *, u_char *);
51: int compare(u_char *, u_char *, u_char *);
52: int look(u_char *, u_char *, u_char *);
53:
54: int
55: look(u_char *string, u_char *front, u_char *back)
56: {
57: u_char *s;
58:
59: /* Convert string to lower case before searching. */
60: for (s = string; *s; s++) {
61: if (isupper(*s))
62: *s = _tolower(*s);
63: }
64:
65: front = binary_search(string, front, back);
66: front = linear_search(string, front, back);
67:
68: return (front != NULL);
69: }
70:
71: /*
72: * Binary search for "string" in memory between "front" and "back".
73: *
74: * This routine is expected to return a pointer to the start of a line at
75: * *or before* the first word matching "string". Relaxing the constraint
76: * this way simplifies the algorithm.
77: *
78: * Invariants:
79: * front points to the beginning of a line at or before the first
80: * matching string.
81: *
82: * back points to the beginning of a line at or after the first
83: * matching line.
84: *
85: * Base of the Invariants.
86: * front = NULL;
87: * back = EOF;
88: *
89: * Advancing the Invariants:
90: *
91: * p = first newline after halfway point from front to back.
92: *
93: * If the string at "p" is not greater than the string to match,
94: * p is the new front. Otherwise it is the new back.
95: *
96: * Termination:
97: *
98: * The definition of the routine allows it return at any point,
99: * since front is always at or before the line to print.
100: *
101: * In fact, it returns when the chosen "p" equals "back". This
102: * implies that there exists a string is least half as long as
103: * (back - front), which in turn implies that a linear search will
104: * be no more expensive than the cost of simply printing a string or two.
105: *
106: * Trying to continue with binary search at this point would be
107: * more trouble than it's worth.
108: */
109: #define SKIP_PAST_NEWLINE(p, back) \
110: while (p < back && *p++ != '\n');
111:
112: u_char *
113: binary_search(u_char *string, u_char *front, u_char *back)
114: {
115: u_char *p;
116:
117: p = front + (back - front) / 2;
118: SKIP_PAST_NEWLINE(p, back);
119:
120: /*
121: * If the file changes underneath us, make sure we don't
122: * infinitely loop.
123: */
124: while (p < back && back > front) {
125: if (compare(string, p, back) > 0)
126: front = p;
127: else
128: back = p;
129: p = front + (back - front) / 2;
130: SKIP_PAST_NEWLINE(p, back);
131: }
132: return (front);
133: }
134:
135: /*
136: * Find the first line that matches string, linearly searching from front
137: * to back.
138: *
139: * Return NULL for no such line.
140: *
141: * This routine assumes:
142: *
143: * o front points at the first character in a line.
144: * o front is before or at the first line to be printed.
145: */
146: u_char *
147: linear_search(u_char *string, u_char *front, u_char *back)
148: {
149: int result;
150:
151: while (front < back) {
152: result = compare(string, front, back);
153: if (result == 0)
1.2 kjell 154: return (front); /* found it */
1.1 millert 155: if (result < 0)
1.2 kjell 156: return (NULL); /* not there */
1.1 millert 157:
158: SKIP_PAST_NEWLINE(front, back);
159: }
160: return (NULL);
161: }
162:
163: int
164: compare(u_char *s1, u_char *s2, u_char *back)
165: {
166: int ch;
167:
168: /* Note that s1 is already upper case. */
169: for (;; ++s1, ++s2) {
170: if (*s2 == '\n' || s2 == back)
171: ch = '\0';
172: else if (isupper(*s2))
173: ch = _tolower(*s2);
174: else
175: ch = *s2;
176: if (*s1 != ch)
1.2 kjell 177: return (*s1 - ch);
1.1 millert 178: if (ch == '\0')
1.2 kjell 179: return (0);
1.1 millert 180: }
181: }
![[BACK]](/icons/back.gif){kind=icon}
Return to look.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / spell