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