1 /* 2 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 */ 5 6 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 7 /* All Rights Reserved */ 8 9 /* 10 * Copyright (c) 1980 Regents of the University of California. 11 * All rights reserved. The Berkeley software License Agreement 12 * specifies the terms and conditions for redistribution. 13 */ 14 15 #include <stdio.h> 16 #include <ctype.h> 17 /* 18 * fgrep -- print all lines containing any of a set of keywords 19 * 20 * status returns: 21 * 0 - ok, and some matches 22 * 1 - ok, but no matches 23 * 2 - some error 24 */ 25 #define MAXSIZ 700 26 #define QSIZE 400 27 struct words { 28 char inp; 29 char out; 30 struct words *nst; 31 struct words *link; 32 struct words *fail; 33 } 34 *www, *smax, *q; 35 36 char buf[2*BUFSIZ]; 37 int nsucc; 38 int need; 39 char *instr; 40 int inct; 41 int rflag; 42 int xargc; 43 char **xargv; 44 int numwords; 45 int nfound; 46 static int flag = 0; 47 48 extern void err(); 49 extern void *zalloc(); 50 51 static void cfail(void); 52 static void cgotofn(void); 53 static void execute(void); 54 static char gch(void); 55 static int new(struct words *x); 56 static void overflo(void); 57 58 int 59 fgrep(int argc, char **argv) 60 { 61 nsucc = need = inct = rflag = numwords = nfound = 0; 62 instr = 0; 63 flag = 0; 64 if (www == 0) 65 www = (struct words *)zalloc(MAXSIZ, sizeof (*www)); 66 if (www == NULL) 67 err(gettext("Can't get space for machines"), 0); 68 for (q = www; q < www+MAXSIZ; q++) { 69 q->inp = 0; q->out = 0; q->nst = 0; q->link = 0; q->fail = 0; 70 } 71 xargc = argc-1; 72 xargv = argv+1; 73 while (xargc > 0 && xargv[0][0] == '-') { 74 switch (xargv[0][1]) { 75 case 'r': /* return value only */ 76 rflag++; 77 break; 78 case 'n': /* number of answers needed */ 79 need = (int)xargv[1]; 80 xargv++; xargc--; 81 break; 82 case 'i': 83 instr = xargv[1]; 84 inct = (int)xargv[2]+2; 85 #if D2 86 fprintf(stderr, "inct %d xargv.2. %o %d\n", inct, xargv[2], xargv[2]); 87 #endif 88 xargv += 2; xargc -= 2; 89 break; 90 } 91 xargv++; xargc--; 92 } 93 if (xargc <= 0) { 94 write(2, "bad fgrep call\n", 15); 95 exit(2); 96 } 97 #if D1 98 fprintf(stderr, "before cgoto\n"); 99 #endif 100 cgotofn(); 101 #if D1 102 fprintf(stderr, "before cfail\n"); 103 #endif 104 cfail(); 105 #if D1 106 fprintf(stderr, "before execute instr %.20s\n", instr? instr: ""); 107 fprintf(stderr, "end of string %d %c %c %c\n", inct, 108 instr ? instr[inct-3] : '\0', 109 instr ? instr[inct-2] : '\0', 110 instr ? instr[inct-1] : '\0'); 111 #endif 112 execute(); 113 #if D1 114 fprintf(stderr, "returning nsucc %d\n", nsucc); 115 fprintf(stderr, "fgrep done www %o\n", www); 116 #endif 117 return (nsucc == 0); 118 } 119 120 static void 121 execute(void) 122 { 123 char *p; 124 struct words *c; 125 char ch; 126 int ccount; 127 int f; 128 char *nlp; 129 f = 0; 130 ccount = instr ? inct : 0; 131 nfound = 0; 132 p = instr ? instr : buf; 133 if (need == 0) need = numwords; 134 nlp = p; 135 c = www; 136 #if D2 137 fprintf(stderr, "in execute ccount %d inct %d\n", ccount, inct); 138 #endif 139 for (;;) { 140 #if D3 141 fprintf(stderr, "down ccount\n"); 142 #endif 143 if (--ccount <= 0) { 144 #if D2 145 fprintf(stderr, "ex loop ccount %d instr %o\n", ccount, instr); 146 #endif 147 if (instr) break; 148 if (p == &buf[2*BUFSIZ]) p = buf; 149 if (p > &buf[BUFSIZ]) { 150 if ((ccount = read(f, p, 151 &buf[2*BUFSIZ] - p)) <= 0) 152 break; 153 } else if ((ccount = read(f, p, BUFSIZ)) <= 0) break; 154 #if D2 155 fprintf(stderr, " normal read %d bytres\n", ccount); 156 { 157 char xx[20]; 158 sprintf(xx, "they are %%.%ds\n", ccount); 159 fprintf(stderr, xx, p); 160 } 161 #endif 162 } 163 nstate: 164 ch = *p; 165 #if D2 166 fprintf(stderr, "roaming along in ex ch %c c %o\n", ch, c); 167 #endif 168 if (isupper(ch)) ch |= 040; 169 if (c->inp == ch) { 170 c = c->nst; 171 } else if (c->link != 0) { 172 c = c->link; 173 goto nstate; 174 } else { 175 c = c->fail; 176 if (c == 0) { 177 c = www; 178 istate: 179 if (c->inp == ch) { 180 c = c->nst; 181 } else if (c->link != 0) { 182 c = c->link; 183 goto istate; 184 } 185 } else goto nstate; 186 } 187 if (c->out && new(c)) { 188 #if D2 189 fprintf(stderr, " found: nfound %d need %d\n", nfound, need); 190 #endif 191 if (++nfound >= need) { 192 #if D1 193 fprintf(stderr, "found, p %o nlp %o ccount %d buf %o buf[2*BUFSIZ] %o\n", 194 p, nlp, ccount, buf, buf+2*BUFSIZ); 195 #endif 196 if (instr == 0) 197 while (*p++ != '\n') { 198 #if D3 199 fprintf(stderr, "down ccount2\n"); 200 #endif 201 if (--ccount <= 0) { 202 if (p == &buf[2*BUFSIZ]) 203 p = buf; 204 if (p > &buf[BUFSIZ]) { 205 if ((ccount = read(f, p, 206 &buf[2*BUFSIZ] - p)) 207 <= 0) 208 break; 209 } else if ((ccount = read(f, p, 210 BUFSIZ)) <= 0) 211 break; 212 #if D2 213 fprintf(stderr, " read %d bytes\n", ccount); 214 { char xx[20]; sprintf(xx, "they are %%.%ds\n", ccount); 215 fprintf(stderr, xx, p); 216 } 217 #endif 218 } 219 } 220 nsucc = 1; 221 if (rflag == 0) { 222 #if D2 223 fprintf(stderr, "p %o nlp %o buf %o\n", p, nlp, buf); 224 if (p > nlp) 225 {write(2, "XX\n", 3); write(2, nlp, p-nlp); write(2, "XX\n", 3); } 226 #endif 227 if (p > nlp) write(1, nlp, p-nlp); 228 else { 229 write(1, nlp, 230 &buf[2*BUFSIZ] - nlp); 231 write(1, buf, p-&buf[0]); 232 } 233 if (p[-1] != '\n') write(1, "\n", 1); 234 } 235 if (instr == 0) { 236 nlp = p; 237 c = www; 238 nfound = 0; 239 } 240 } else 241 ccount++; 242 continue; 243 } 244 #if D2 245 fprintf(stderr, "nr end loop p %o\n", p); 246 #endif 247 if (instr) 248 p++; 249 else 250 if (*p++ == '\n') 251 { 252 nlp = p; 253 c = www; 254 nfound = 0; 255 } 256 } 257 if (instr == 0) 258 close(f); 259 } 260 261 static void 262 cgotofn(void) 263 { 264 char c; 265 struct words *s; 266 s = smax = www; 267 nword: 268 for (;;) { 269 #if D1 270 fprintf(stderr, " in for loop c now %o %c\n", c, c > ' ' ? c : ' '); 271 #endif 272 if ((c = gch()) == 0) 273 return; 274 else if (c == '\n') { 275 s->out = 1; 276 s = www; 277 } else { 278 loop: 279 if (s->inp == c) { 280 s = s->nst; 281 continue; 282 } 283 if (s->inp == 0) goto enter; 284 if (s->link == 0) { 285 if (smax >= &www[MAXSIZ - 1]) overflo(); 286 s->link = ++smax; 287 s = smax; 288 goto enter; 289 } 290 s = s->link; 291 goto loop; 292 } 293 } 294 295 enter: 296 do { 297 s->inp = c; 298 if (smax >= &www[MAXSIZ - 1]) overflo(); 299 s->nst = ++smax; 300 s = smax; 301 } 302 while ((c = gch()) != '\n') 303 ; 304 smax->out = 1; 305 s = www; 306 numwords++; 307 goto nword; 308 309 } 310 311 static char 312 gch(void) 313 { 314 static char *s; 315 if (flag == 0) { 316 flag = 1; 317 s = *xargv++; 318 #if D1 319 fprintf(stderr, "next arg is %s xargc %d\n", xargc > 0 ? s : "", xargc); 320 #endif 321 if (xargc-- <= 0) 322 return (0); 323 } 324 if (*s) 325 return (*s++); 326 for (flag = 0; flag < 2*BUFSIZ; flag++) 327 buf[flag] = 0; 328 flag = 0; 329 return ('\n'); 330 } 331 332 static void 333 overflo(void) 334 { 335 write(2, "wordlist too large\n", 19); 336 exit(2); 337 } 338 339 static void 340 cfail(void) 341 { 342 struct words *queue[QSIZE]; 343 struct words **front, **rear; 344 struct words *state; 345 char c; 346 struct words *s; 347 s = www; 348 front = rear = queue; 349 init: 350 if ((s->inp) != 0) { 351 *rear++ = s->nst; 352 if (rear >= &queue[QSIZE - 1]) overflo(); 353 } 354 if ((s = s->link) != 0) { 355 goto init; 356 } 357 358 while (rear != front) { 359 s = *front; 360 if (front == &queue[QSIZE-1]) 361 front = queue; 362 else front++; 363 cloop: 364 if ((c = s->inp) != 0) { 365 *rear = (q = s->nst); 366 if (front < rear) 367 if (rear >= &queue[QSIZE-1]) 368 if (front == queue) overflo(); 369 else rear = queue; 370 else rear++; 371 else 372 if (++rear == front) overflo(); 373 state = s->fail; 374 floop: 375 if (state == 0) state = www; 376 if (state->inp == c) { 377 q->fail = state->nst; 378 if ((state->nst)->out == 1) q->out = 1; 379 continue; 380 } else if ((state = state->link) != 0) 381 goto floop; 382 } 383 if ((s = s->link) != 0) 384 goto cloop; 385 } 386 } 387 388 static struct words *seen[50]; 389 390 static int 391 new(struct words *x) 392 { 393 int i; 394 for (i = 0; i < nfound; i++) 395 if (seen[i] == x) 396 return (0); 397 seen[i] = x; 398 return (1); 399 } 400