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