Annotation of src/usr.bin/spell/look.c, Revision 1.5
1.5 ! millert 1: /* $OpenBSD: look.c,v 1.4 2009/10/27 23:59:43 deraadt 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: #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))
1.5 ! millert 55: *s = tolower(*s);
1.1 millert 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)
1.2 kjell 147: return (front); /* found it */
1.1 millert 148: if (result < 0)
1.2 kjell 149: return (NULL); /* not there */
1.1 millert 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 if (isupper(*s2))
166: ch = _tolower(*s2);
167: else
168: ch = *s2;
169: if (*s1 != ch)
1.2 kjell 170: return (*s1 - ch);
1.1 millert 171: if (ch == '\0')
1.2 kjell 172: return (0);
1.1 millert 173: }
174: }
![[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