Annotation of src/usr.bin/spell/look.c, Revision 1.2
1.2 ! kjell 1: /* $OpenBSD: look.c,v 1.1 2002/03/01 22:01:11 millert 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.
18: * 3. All advertising materials mentioning features or use of this software
19: * must display the following acknowledgement:
20: * This product includes software developed by the University of
21: * California, Berkeley and its contributors.
22: * 4. Neither the name of the University nor the names of its contributors
23: * may be used to endorse or promote products derived from this software
24: * without specific prior written permission.
25: *
26: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36: * SUCH DAMAGE.
37: */
38:
39: #ifndef lint
40: #if 0
41: static const char sccsid[] = "@(#)look.c 8.2 (Berkeley) 5/4/95";
42: #endif
1.2 ! kjell 43: static const char rcsid[] = "$OpenBSD: look.c,v 1.1 2002/03/01 22:01:11 millert Exp $";
1.1 millert 44: #endif /* not lint */
45:
46: #include <sys/types.h>
47: #include <ctype.h>
48: #include <stdio.h>
49: #include <stdlib.h>
50: #include <string.h>
51: #include <err.h>
52:
53: u_char *binary_search(u_char *, u_char *, u_char *);
54: u_char *linear_search(u_char *, u_char *, u_char *);
55: int compare(u_char *, u_char *, u_char *);
56: int look(u_char *, u_char *, u_char *);
57:
58: int
59: look(u_char *string, u_char *front, u_char *back)
60: {
61: u_char *s;
62:
63: /* Convert string to lower case before searching. */
64: for (s = string; *s; s++) {
65: if (isupper(*s))
66: *s = _tolower(*s);
67: }
68:
69: front = binary_search(string, front, back);
70: front = linear_search(string, front, back);
71:
72: return (front != NULL);
73: }
74:
75: /*
76: * Binary search for "string" in memory between "front" and "back".
77: *
78: * This routine is expected to return a pointer to the start of a line at
79: * *or before* the first word matching "string". Relaxing the constraint
80: * this way simplifies the algorithm.
81: *
82: * Invariants:
83: * front points to the beginning of a line at or before the first
84: * matching string.
85: *
86: * back points to the beginning of a line at or after the first
87: * matching line.
88: *
89: * Base of the Invariants.
90: * front = NULL;
91: * back = EOF;
92: *
93: * Advancing the Invariants:
94: *
95: * p = first newline after halfway point from front to back.
96: *
97: * If the string at "p" is not greater than the string to match,
98: * p is the new front. Otherwise it is the new back.
99: *
100: * Termination:
101: *
102: * The definition of the routine allows it return at any point,
103: * since front is always at or before the line to print.
104: *
105: * In fact, it returns when the chosen "p" equals "back". This
106: * implies that there exists a string is least half as long as
107: * (back - front), which in turn implies that a linear search will
108: * be no more expensive than the cost of simply printing a string or two.
109: *
110: * Trying to continue with binary search at this point would be
111: * more trouble than it's worth.
112: */
113: #define SKIP_PAST_NEWLINE(p, back) \
114: while (p < back && *p++ != '\n');
115:
116: u_char *
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: u_char *
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)
1.2 ! kjell 158: return (front); /* found it */
1.1 millert 159: if (result < 0)
1.2 ! kjell 160: return (NULL); /* not there */
1.1 millert 161:
162: SKIP_PAST_NEWLINE(front, back);
163: }
164: return (NULL);
165: }
166:
167: int
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)
1.2 ! kjell 181: return (*s1 - ch);
1.1 millert 182: if (ch == '\0')
1.2 ! kjell 183: return (0);
1.1 millert 184: }
185: }
![[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