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