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
fgrep(int argc,char ** argv)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
execute(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
cgotofn(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
gch(void)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
overflo(void)336 overflo(void)
337 {
338 write(2, "wordlist too large\n", 19);
339 exit(2);
340 }
341
342 static void
cfail(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
new(struct words * x)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