1 /*- 2 * Copyright (c) 1991 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * David Hitz of Auspex Systems, Inc. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #ifndef lint 12 char copyright[] = 13 "@(#) Copyright (c) 1991 The Regents of the University of California.\n\ 14 All rights reserved.\n"; 15 #endif /* not lint */ 16 17 #ifndef lint 18 static char sccsid[] = "@(#)look.c 5.3 (Berkeley) 10/24/92"; 19 #endif /* not lint */ 20 21 /* 22 * look -- find lines in a sorted list. 23 * 24 * The man page said that TABs and SPACEs participate in -d comparisons. 25 * In fact, they were ignored. This implements historic practice, not 26 * the manual page. 27 */ 28 29 #include <sys/types.h> 30 #include <sys/mman.h> 31 #include <sys/stat.h> 32 33 #include <limits.h> 34 #include <errno.h> 35 #include <fcntl.h> 36 #include <stdio.h> 37 #include <stdlib.h> 38 #include <string.h> 39 #include <ctype.h> 40 #include "pathnames.h" 41 42 /* 43 * FOLD and DICT convert characters to a normal form for comparison, 44 * according to the user specified flags. 45 * 46 * DICT expects integers because it uses a non-character value to 47 * indicate a character which should not participate in comparisons. 48 */ 49 #define EQUAL 0 50 #define GREATER 1 51 #define LESS (-1) 52 #define NO_COMPARE (-2) 53 54 #define FOLD(c) (isascii(c) && isupper(c) ? tolower(c) : (c)) 55 #define DICT(c) (isascii(c) && isalnum(c) ? (c) : NO_COMPARE) 56 57 int dflag, fflag; 58 59 char *binary_search __P((char *, char *, char *)); 60 int compare __P((char *, char *, char *)); 61 void err __P((const char *fmt, ...)); 62 char *linear_search __P((char *, char *, char *)); 63 int look __P((char *, char *, char *)); 64 void print_from __P((char *, char *, char *)); 65 66 static void usage __P((void)); 67 68 main(argc, argv) 69 int argc; 70 char *argv[]; 71 { 72 struct stat sb; 73 int ch, fd; 74 char *back, *file, *front, *string; 75 76 file = _PATH_WORDS; 77 while ((ch = getopt(argc, argv, "df")) != EOF) 78 switch(ch) { 79 case 'd': 80 dflag = 1; 81 break; 82 case 'f': 83 fflag = 1; 84 break; 85 case '?': 86 default: 87 usage(); 88 } 89 argc -= optind; 90 argv += optind; 91 92 switch (argc) { 93 case 2: /* Don't set -df for user. */ 94 string = *argv++; 95 file = *argv; 96 break; 97 case 1: /* But set -df by default. */ 98 dflag = fflag = 1; 99 string = *argv; 100 break; 101 default: 102 usage(); 103 } 104 105 if ((fd = open(file, O_RDONLY, 0)) < 0 || fstat(fd, &sb)) 106 err("%s: %s", file, strerror(errno)); 107 if (sb.st_size > SIZE_T_MAX) 108 err("%s: %s", file, strerror(EFBIG)); 109 if ((front = mmap(NULL, 110 (size_t)sb.st_size, PROT_READ, 0, fd, (off_t)0)) == NULL) 111 err("%s: %s", file, strerror(errno)); 112 back = front + sb.st_size; 113 exit(look(string, front, back)); 114 } 115 116 look(string, front, back) 117 char *string, *front, *back; 118 { 119 register int ch; 120 register char *readp, *writep; 121 122 /* Reformat string string to avoid doing it multiple times later. */ 123 for (readp = writep = string; ch = *readp++;) { 124 if (fflag) 125 ch = FOLD(ch); 126 if (dflag) 127 ch = DICT(ch); 128 if (ch != NO_COMPARE) 129 *(writep++) = ch; 130 } 131 *writep = '\0'; 132 133 front = binary_search(string, front, back); 134 front = linear_search(string, front, back); 135 136 if (front) 137 print_from(string, front, back); 138 return (front ? 0 : 1); 139 } 140 141 142 /* 143 * Binary search for "string" in memory between "front" and "back". 144 * 145 * This routine is expected to return a pointer to the start of a line at 146 * *or before* the first word matching "string". Relaxing the constraint 147 * this way simplifies the algorithm. 148 * 149 * Invariants: 150 * front points to the beginning of a line at or before the first 151 * matching string. 152 * 153 * back points to the beginning of a line at or after the first 154 * matching line. 155 * 156 * Base of the Invariants. 157 * front = NULL; 158 * back = EOF; 159 * 160 * Advancing the Invariants: 161 * 162 * p = first newline after halfway point from front to back. 163 * 164 * If the string at "p" is not greater than the string to match, 165 * p is the new front. Otherwise it is the new back. 166 * 167 * Termination: 168 * 169 * The definition of the routine allows it return at any point, 170 * since front is always at or before the line to print. 171 * 172 * In fact, it returns when the chosen "p" equals "back". This 173 * implies that there exists a string is least half as long as 174 * (back - front), which in turn implies that a linear search will 175 * be no more expensive than the cost of simply printing a string or two. 176 * 177 * Trying to continue with binary search at this point would be 178 * more trouble than it's worth. 179 */ 180 #define SKIP_PAST_NEWLINE(p, back) \ 181 while (p < back && *p++ != '\n'); 182 183 char * 184 binary_search(string, front, back) 185 register char *string, *front, *back; 186 { 187 register char *p; 188 189 p = front + (back - front) / 2; 190 SKIP_PAST_NEWLINE(p, back); 191 192 while (p != back) { 193 if (compare(string, p, back) == GREATER) 194 front = p; 195 else 196 back = p; 197 p = front + (back - front) / 2; 198 SKIP_PAST_NEWLINE(p, back); 199 } 200 return (front); 201 } 202 203 /* 204 * Find the first line that starts with string, linearly searching from front 205 * to back. 206 * 207 * Return NULL for no such line. 208 * 209 * This routine assumes: 210 * 211 * o front points at the first character in a line. 212 * o front is before or at the first line to be printed. 213 */ 214 char * 215 linear_search(string, front, back) 216 char *string, *front, *back; 217 { 218 while (front < back) { 219 switch (compare(string, front, back)) { 220 case EQUAL: /* Found it. */ 221 return (front); 222 break; 223 case LESS: /* No such string. */ 224 return (NULL); 225 break; 226 case GREATER: /* Keep going. */ 227 break; 228 } 229 SKIP_PAST_NEWLINE(front, back); 230 } 231 return (NULL); 232 } 233 234 /* 235 * Print as many lines as match string, starting at front. 236 */ 237 void 238 print_from(string, front, back) 239 register char *string, *front, *back; 240 { 241 for (; front < back && compare(string, front, back) == EQUAL; ++front) { 242 for (; front < back && *front != '\n'; ++front) 243 if (putchar(*front) == EOF) 244 err("stdout: %s", strerror(errno)); 245 if (putchar('\n') == EOF) 246 err("stdout: %s", strerror(errno)); 247 } 248 } 249 250 /* 251 * Return LESS, GREATER, or EQUAL depending on how the string1 compares with 252 * string2 (s1 ??? s2). 253 * 254 * o Matches up to len(s1) are EQUAL. 255 * o Matches up to len(s2) are GREATER. 256 * 257 * Compare understands about the -f and -d flags, and treats comparisons 258 * appropriately. 259 * 260 * The string "s1" is null terminated. The string s2 is '\n' terminated (or 261 * "back" terminated). 262 */ 263 int 264 compare(s1, s2, back) 265 register char *s1, *s2, *back; 266 { 267 register int ch; 268 269 for (; *s1 && s2 < back && *s2 != '\n'; ++s1, ++s2) { 270 ch = *s2; 271 if (fflag) 272 ch = FOLD(ch); 273 if (dflag) 274 ch = DICT(ch); 275 276 if (ch == NO_COMPARE) { 277 ++s2; /* Ignore character in comparison. */ 278 continue; 279 } 280 if (*s1 != ch) 281 return (*s1 < ch ? LESS : GREATER); 282 } 283 return (*s1 ? GREATER : EQUAL); 284 } 285 286 static void 287 usage() 288 { 289 (void)fprintf(stderr, "usage: look [-df] string [file]\n"); 290 exit(2); 291 } 292 293 #if __STDC__ 294 #include <stdarg.h> 295 #else 296 #include <varargs.h> 297 #endif 298 299 void 300 #if __STDC__ 301 err(const char *fmt, ...) 302 #else 303 err(fmt, va_alist) 304 char *fmt; 305 va_dcl 306 #endif 307 { 308 va_list ap; 309 #if __STDC__ 310 va_start(ap, fmt); 311 #else 312 va_start(ap); 313 #endif 314 (void)fprintf(stderr, "look: "); 315 (void)vfprintf(stderr, fmt, ap); 316 va_end(ap); 317 (void)fprintf(stderr, "\n"); 318 exit(2); 319 /* NOTREACHED */ 320 } 321