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