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