1*11a8fa6cSceastha /*
2*11a8fa6cSceastha * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
3*11a8fa6cSceastha * Use is subject to license terms.
4*11a8fa6cSceastha */
5*11a8fa6cSceastha
67c478bd9Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
77c478bd9Sstevel@tonic-gate /* All Rights Reserved */
87c478bd9Sstevel@tonic-gate
97c478bd9Sstevel@tonic-gate /*
107c478bd9Sstevel@tonic-gate * Copyright (c) 1980 Regents of the University of California.
117c478bd9Sstevel@tonic-gate * All rights reserved. The Berkeley software License Agreement
127c478bd9Sstevel@tonic-gate * specifies the terms and conditions for redistribution.
137c478bd9Sstevel@tonic-gate */
147c478bd9Sstevel@tonic-gate
157c478bd9Sstevel@tonic-gate #include <stdio.h>
167c478bd9Sstevel@tonic-gate #include <ctype.h>
177c478bd9Sstevel@tonic-gate /*
187c478bd9Sstevel@tonic-gate * fgrep -- print all lines containing any of a set of keywords
197c478bd9Sstevel@tonic-gate *
207c478bd9Sstevel@tonic-gate * status returns:
217c478bd9Sstevel@tonic-gate * 0 - ok, and some matches
227c478bd9Sstevel@tonic-gate * 1 - ok, but no matches
237c478bd9Sstevel@tonic-gate * 2 - some error
247c478bd9Sstevel@tonic-gate */
257c478bd9Sstevel@tonic-gate #define MAXSIZ 700
26*11a8fa6cSceastha #define QSIZE 400
277c478bd9Sstevel@tonic-gate struct words {
287c478bd9Sstevel@tonic-gate char inp;
297c478bd9Sstevel@tonic-gate char out;
307c478bd9Sstevel@tonic-gate struct words *nst;
317c478bd9Sstevel@tonic-gate struct words *link;
327c478bd9Sstevel@tonic-gate struct words *fail;
33*11a8fa6cSceastha }
347c478bd9Sstevel@tonic-gate *www, *smax, *q;
357c478bd9Sstevel@tonic-gate
367c478bd9Sstevel@tonic-gate char buf[2*BUFSIZ];
377c478bd9Sstevel@tonic-gate int nsucc;
387c478bd9Sstevel@tonic-gate int need;
397c478bd9Sstevel@tonic-gate char *instr;
407c478bd9Sstevel@tonic-gate int inct;
417c478bd9Sstevel@tonic-gate int rflag;
427c478bd9Sstevel@tonic-gate int xargc;
437c478bd9Sstevel@tonic-gate char **xargv;
447c478bd9Sstevel@tonic-gate int numwords;
457c478bd9Sstevel@tonic-gate int nfound;
467c478bd9Sstevel@tonic-gate static int flag = 0;
477c478bd9Sstevel@tonic-gate
48*11a8fa6cSceastha extern void err();
49*11a8fa6cSceastha extern void *zalloc();
50*11a8fa6cSceastha
51*11a8fa6cSceastha static void cfail(void);
52*11a8fa6cSceastha static void cgotofn(void);
53*11a8fa6cSceastha static void execute(void);
54*11a8fa6cSceastha static char gch(void);
55*11a8fa6cSceastha static int new(struct words *x);
56*11a8fa6cSceastha static void overflo(void);
57*11a8fa6cSceastha
58*11a8fa6cSceastha int
fgrep(int argc,char ** argv)59*11a8fa6cSceastha fgrep(int argc, char **argv)
607c478bd9Sstevel@tonic-gate {
617c478bd9Sstevel@tonic-gate nsucc = need = inct = rflag = numwords = nfound = 0;
627c478bd9Sstevel@tonic-gate instr = 0;
637c478bd9Sstevel@tonic-gate flag = 0;
64*11a8fa6cSceastha if (www == 0)
65*11a8fa6cSceastha www = (struct words *)zalloc(MAXSIZ, sizeof (*www));
66*11a8fa6cSceastha if (www == NULL)
677c478bd9Sstevel@tonic-gate err(gettext("Can't get space for machines"), 0);
68*11a8fa6cSceastha for (q = www; q < www+MAXSIZ; q++) {
69*11a8fa6cSceastha q->inp = 0; q->out = 0; q->nst = 0; q->link = 0; q->fail = 0;
707c478bd9Sstevel@tonic-gate }
717c478bd9Sstevel@tonic-gate xargc = argc-1;
727c478bd9Sstevel@tonic-gate xargv = argv+1;
73*11a8fa6cSceastha while (xargc > 0 && xargv[0][0] == '-') {
74*11a8fa6cSceastha switch (xargv[0][1]) {
757c478bd9Sstevel@tonic-gate case 'r': /* return value only */
767c478bd9Sstevel@tonic-gate rflag++;
777c478bd9Sstevel@tonic-gate break;
787c478bd9Sstevel@tonic-gate case 'n': /* number of answers needed */
79*11a8fa6cSceastha need = (int)xargv[1];
807c478bd9Sstevel@tonic-gate xargv++; xargc--;
817c478bd9Sstevel@tonic-gate break;
827c478bd9Sstevel@tonic-gate case 'i':
837c478bd9Sstevel@tonic-gate instr = xargv[1];
84*11a8fa6cSceastha inct = (int)xargv[2]+2;
85*11a8fa6cSceastha #if D2
86*11a8fa6cSceastha fprintf(stderr, "inct %d xargv.2. %o %d\n", inct, xargv[2], xargv[2]);
87*11a8fa6cSceastha #endif
887c478bd9Sstevel@tonic-gate xargv += 2; xargc -= 2;
897c478bd9Sstevel@tonic-gate break;
907c478bd9Sstevel@tonic-gate }
91*11a8fa6cSceastha xargv++; xargc--;
92*11a8fa6cSceastha }
93*11a8fa6cSceastha if (xargc <= 0) {
94*11a8fa6cSceastha write(2, "bad fgrep call\n", 15);
957c478bd9Sstevel@tonic-gate exit(2);
96*11a8fa6cSceastha }
97*11a8fa6cSceastha #if D1
987c478bd9Sstevel@tonic-gate fprintf(stderr, "before cgoto\n");
99*11a8fa6cSceastha #endif
1007c478bd9Sstevel@tonic-gate cgotofn();
101*11a8fa6cSceastha #if D1
1027c478bd9Sstevel@tonic-gate fprintf(stderr, "before cfail\n");
103*11a8fa6cSceastha #endif
1047c478bd9Sstevel@tonic-gate cfail();
105*11a8fa6cSceastha #if D1
1067c478bd9Sstevel@tonic-gate fprintf(stderr, "before execute instr %.20s\n", instr? instr: "");
1077c478bd9Sstevel@tonic-gate fprintf(stderr, "end of string %d %c %c %c\n", inct,
108*11a8fa6cSceastha instr ? instr[inct-3] : '\0',
109*11a8fa6cSceastha instr ? instr[inct-2] : '\0',
110*11a8fa6cSceastha instr ? instr[inct-1] : '\0');
111*11a8fa6cSceastha #endif
1127c478bd9Sstevel@tonic-gate execute();
113*11a8fa6cSceastha #if D1
1147c478bd9Sstevel@tonic-gate fprintf(stderr, "returning nsucc %d\n", nsucc);
115*11a8fa6cSceastha fprintf(stderr, "fgrep done www %o\n", www);
116*11a8fa6cSceastha #endif
117*11a8fa6cSceastha return (nsucc == 0);
1187c478bd9Sstevel@tonic-gate }
1197c478bd9Sstevel@tonic-gate
120*11a8fa6cSceastha static void
execute(void)121*11a8fa6cSceastha execute(void)
1227c478bd9Sstevel@tonic-gate {
123*11a8fa6cSceastha char *p;
124*11a8fa6cSceastha struct words *c;
125*11a8fa6cSceastha char ch;
126*11a8fa6cSceastha int ccount;
1277c478bd9Sstevel@tonic-gate int f;
1287c478bd9Sstevel@tonic-gate char *nlp;
129*11a8fa6cSceastha f = 0;
1307c478bd9Sstevel@tonic-gate ccount = instr ? inct : 0;
131*11a8fa6cSceastha nfound = 0;
1327c478bd9Sstevel@tonic-gate p = instr ? instr : buf;
1337c478bd9Sstevel@tonic-gate if (need == 0) need = numwords;
1347c478bd9Sstevel@tonic-gate nlp = p;
1357c478bd9Sstevel@tonic-gate c = www;
136*11a8fa6cSceastha #if D2
137*11a8fa6cSceastha fprintf(stderr, "in execute ccount %d inct %d\n", ccount, inct);
138*11a8fa6cSceastha #endif
1397c478bd9Sstevel@tonic-gate for (;;) {
140*11a8fa6cSceastha #if D3
1417c478bd9Sstevel@tonic-gate fprintf(stderr, "down ccount\n");
142*11a8fa6cSceastha #endif
1437c478bd9Sstevel@tonic-gate if (--ccount <= 0) {
144*11a8fa6cSceastha #if D2
145*11a8fa6cSceastha fprintf(stderr, "ex loop ccount %d instr %o\n", ccount, instr);
146*11a8fa6cSceastha #endif
1477c478bd9Sstevel@tonic-gate if (instr) break;
1487c478bd9Sstevel@tonic-gate if (p == &buf[2*BUFSIZ]) p = buf;
1497c478bd9Sstevel@tonic-gate if (p > &buf[BUFSIZ]) {
150*11a8fa6cSceastha if ((ccount = read(f, p,
151*11a8fa6cSceastha &buf[2*BUFSIZ] - p)) <= 0)
152*11a8fa6cSceastha break;
153*11a8fa6cSceastha } else if ((ccount = read(f, p, BUFSIZ)) <= 0) break;
154*11a8fa6cSceastha #if D2
1557c478bd9Sstevel@tonic-gate fprintf(stderr, " normal read %d bytres\n", ccount);
156*11a8fa6cSceastha {
157*11a8fa6cSceastha char xx[20];
158*11a8fa6cSceastha sprintf(xx, "they are %%.%ds\n", ccount);
159*11a8fa6cSceastha fprintf(stderr, xx, p);
1607c478bd9Sstevel@tonic-gate }
161*11a8fa6cSceastha #endif
1627c478bd9Sstevel@tonic-gate }
1637c478bd9Sstevel@tonic-gate nstate:
1647c478bd9Sstevel@tonic-gate ch = *p;
165*11a8fa6cSceastha #if D2
166*11a8fa6cSceastha fprintf(stderr, "roaming along in ex ch %c c %o\n", ch, c);
167*11a8fa6cSceastha #endif
1687c478bd9Sstevel@tonic-gate if (isupper(ch)) ch |= 040;
1697c478bd9Sstevel@tonic-gate if (c->inp == ch) {
1707c478bd9Sstevel@tonic-gate c = c->nst;
171*11a8fa6cSceastha } else if (c->link != 0) {
1727c478bd9Sstevel@tonic-gate c = c->link;
1737c478bd9Sstevel@tonic-gate goto nstate;
174*11a8fa6cSceastha } else {
1757c478bd9Sstevel@tonic-gate c = c->fail;
176*11a8fa6cSceastha if (c == 0) {
1777c478bd9Sstevel@tonic-gate c = www;
1787c478bd9Sstevel@tonic-gate istate:
1797c478bd9Sstevel@tonic-gate if (c->inp == ch) {
1807c478bd9Sstevel@tonic-gate c = c->nst;
181*11a8fa6cSceastha } else if (c->link != 0) {
1827c478bd9Sstevel@tonic-gate c = c->link;
1837c478bd9Sstevel@tonic-gate goto istate;
1847c478bd9Sstevel@tonic-gate }
185*11a8fa6cSceastha } else goto nstate;
1867c478bd9Sstevel@tonic-gate }
187*11a8fa6cSceastha if (c->out && new(c)) {
188*11a8fa6cSceastha #if D2
189*11a8fa6cSceastha fprintf(stderr, " found: nfound %d need %d\n", nfound, need);
190*11a8fa6cSceastha #endif
191*11a8fa6cSceastha if (++nfound >= need) {
192*11a8fa6cSceastha #if D1
193*11a8fa6cSceastha fprintf(stderr, "found, p %o nlp %o ccount %d buf %o buf[2*BUFSIZ] %o\n",
194*11a8fa6cSceastha p, nlp, ccount, buf, buf+2*BUFSIZ);
195*11a8fa6cSceastha #endif
196*11a8fa6cSceastha if (instr == 0)
1977c478bd9Sstevel@tonic-gate while (*p++ != '\n') {
198*11a8fa6cSceastha #if D3
1997c478bd9Sstevel@tonic-gate fprintf(stderr, "down ccount2\n");
200*11a8fa6cSceastha #endif
2017c478bd9Sstevel@tonic-gate if (--ccount <= 0) {
202*11a8fa6cSceastha if (p == &buf[2*BUFSIZ])
203*11a8fa6cSceastha p = buf;
2047c478bd9Sstevel@tonic-gate if (p > &buf[BUFSIZ]) {
205*11a8fa6cSceastha if ((ccount = read(f, p,
206*11a8fa6cSceastha &buf[2*BUFSIZ] - p))
207*11a8fa6cSceastha <= 0)
208*11a8fa6cSceastha break;
209*11a8fa6cSceastha } else if ((ccount = read(f, p,
210*11a8fa6cSceastha BUFSIZ)) <= 0)
211*11a8fa6cSceastha break;
212*11a8fa6cSceastha #if D2
213*11a8fa6cSceastha fprintf(stderr, " read %d bytes\n", ccount);
2147c478bd9Sstevel@tonic-gate { char xx[20]; sprintf(xx, "they are %%.%ds\n", ccount);
2157c478bd9Sstevel@tonic-gate fprintf(stderr, xx, p);
2167c478bd9Sstevel@tonic-gate }
217*11a8fa6cSceastha #endif
2187c478bd9Sstevel@tonic-gate }
2197c478bd9Sstevel@tonic-gate }
2207c478bd9Sstevel@tonic-gate nsucc = 1;
221*11a8fa6cSceastha if (rflag == 0) {
222*11a8fa6cSceastha #if D2
223*11a8fa6cSceastha fprintf(stderr, "p %o nlp %o buf %o\n", p, nlp, buf);
224*11a8fa6cSceastha if (p > nlp)
225*11a8fa6cSceastha {write(2, "XX\n", 3); write(2, nlp, p-nlp); write(2, "XX\n", 3); }
226*11a8fa6cSceastha #endif
2277c478bd9Sstevel@tonic-gate if (p > nlp) write(1, nlp, p-nlp);
2287c478bd9Sstevel@tonic-gate else {
229*11a8fa6cSceastha write(1, nlp,
230*11a8fa6cSceastha &buf[2*BUFSIZ] - nlp);
2317c478bd9Sstevel@tonic-gate write(1, buf, p-&buf[0]);
2327c478bd9Sstevel@tonic-gate }
233*11a8fa6cSceastha if (p[-1] != '\n') write(1, "\n", 1);
234*11a8fa6cSceastha }
235*11a8fa6cSceastha if (instr == 0) {
2367c478bd9Sstevel@tonic-gate nlp = p;
2377c478bd9Sstevel@tonic-gate c = www;
238*11a8fa6cSceastha nfound = 0;
239*11a8fa6cSceastha }
240*11a8fa6cSceastha } else
2417c478bd9Sstevel@tonic-gate ccount++;
2427c478bd9Sstevel@tonic-gate continue;
2437c478bd9Sstevel@tonic-gate }
244*11a8fa6cSceastha #if D2
245*11a8fa6cSceastha fprintf(stderr, "nr end loop p %o\n", p);
246*11a8fa6cSceastha #endif
2477c478bd9Sstevel@tonic-gate if (instr)
2487c478bd9Sstevel@tonic-gate p++;
2497c478bd9Sstevel@tonic-gate else
2507c478bd9Sstevel@tonic-gate if (*p++ == '\n')
2517c478bd9Sstevel@tonic-gate {
2527c478bd9Sstevel@tonic-gate nlp = p;
2537c478bd9Sstevel@tonic-gate c = www;
254*11a8fa6cSceastha nfound = 0;
2557c478bd9Sstevel@tonic-gate }
2567c478bd9Sstevel@tonic-gate }
257*11a8fa6cSceastha if (instr == 0)
2587c478bd9Sstevel@tonic-gate close(f);
2597c478bd9Sstevel@tonic-gate }
2607c478bd9Sstevel@tonic-gate
261*11a8fa6cSceastha static void
cgotofn(void)262*11a8fa6cSceastha cgotofn(void)
263*11a8fa6cSceastha {
264*11a8fa6cSceastha char c;
265*11a8fa6cSceastha struct words *s;
2667c478bd9Sstevel@tonic-gate s = smax = www;
267*11a8fa6cSceastha nword:
268*11a8fa6cSceastha for (;;) {
269*11a8fa6cSceastha #if D1
270*11a8fa6cSceastha fprintf(stderr, " in for loop c now %o %c\n", c, c > ' ' ? c : ' ');
271*11a8fa6cSceastha #endif
272*11a8fa6cSceastha if ((c = gch()) == 0)
273*11a8fa6cSceastha return;
2747c478bd9Sstevel@tonic-gate else if (c == '\n') {
2757c478bd9Sstevel@tonic-gate s->out = 1;
2767c478bd9Sstevel@tonic-gate s = www;
277*11a8fa6cSceastha } else {
278*11a8fa6cSceastha loop:
2797c478bd9Sstevel@tonic-gate if (s->inp == c) {
2807c478bd9Sstevel@tonic-gate s = s->nst;
2817c478bd9Sstevel@tonic-gate continue;
2827c478bd9Sstevel@tonic-gate }
2837c478bd9Sstevel@tonic-gate if (s->inp == 0) goto enter;
2847c478bd9Sstevel@tonic-gate if (s->link == 0) {
2857c478bd9Sstevel@tonic-gate if (smax >= &www[MAXSIZ - 1]) overflo();
2867c478bd9Sstevel@tonic-gate s->link = ++smax;
2877c478bd9Sstevel@tonic-gate s = smax;
2887c478bd9Sstevel@tonic-gate goto enter;
2897c478bd9Sstevel@tonic-gate }
2907c478bd9Sstevel@tonic-gate s = s->link;
2917c478bd9Sstevel@tonic-gate goto loop;
2927c478bd9Sstevel@tonic-gate }
2937c478bd9Sstevel@tonic-gate }
2947c478bd9Sstevel@tonic-gate
2957c478bd9Sstevel@tonic-gate enter:
2967c478bd9Sstevel@tonic-gate do {
2977c478bd9Sstevel@tonic-gate s->inp = c;
2987c478bd9Sstevel@tonic-gate if (smax >= &www[MAXSIZ - 1]) overflo();
2997c478bd9Sstevel@tonic-gate s->nst = ++smax;
3007c478bd9Sstevel@tonic-gate s = smax;
301*11a8fa6cSceastha }
302*11a8fa6cSceastha while ((c = gch()) != '\n')
303*11a8fa6cSceastha ;
3047c478bd9Sstevel@tonic-gate smax->out = 1;
3057c478bd9Sstevel@tonic-gate s = www;
3067c478bd9Sstevel@tonic-gate numwords++;
3077c478bd9Sstevel@tonic-gate goto nword;
3087c478bd9Sstevel@tonic-gate
3097c478bd9Sstevel@tonic-gate }
3107c478bd9Sstevel@tonic-gate
311*11a8fa6cSceastha static char
gch(void)312*11a8fa6cSceastha gch(void)
3137c478bd9Sstevel@tonic-gate {
3147c478bd9Sstevel@tonic-gate static char *s;
315*11a8fa6cSceastha if (flag == 0) {
316*11a8fa6cSceastha flag = 1;
3177c478bd9Sstevel@tonic-gate s = *xargv++;
318*11a8fa6cSceastha #if D1
3197c478bd9Sstevel@tonic-gate fprintf(stderr, "next arg is %s xargc %d\n", xargc > 0 ? s : "", xargc);
320*11a8fa6cSceastha #endif
321*11a8fa6cSceastha if (xargc-- <= 0)
322*11a8fa6cSceastha return (0);
3237c478bd9Sstevel@tonic-gate }
324*11a8fa6cSceastha if (*s)
325*11a8fa6cSceastha return (*s++);
326*11a8fa6cSceastha for (flag = 0; flag < 2*BUFSIZ; flag++)
327*11a8fa6cSceastha buf[flag] = 0;
328*11a8fa6cSceastha flag = 0;
329*11a8fa6cSceastha return ('\n');
3307c478bd9Sstevel@tonic-gate }
3317c478bd9Sstevel@tonic-gate
332*11a8fa6cSceastha static void
overflo(void)333*11a8fa6cSceastha overflo(void)
334*11a8fa6cSceastha {
335*11a8fa6cSceastha write(2, "wordlist too large\n", 19);
3367c478bd9Sstevel@tonic-gate exit(2);
3377c478bd9Sstevel@tonic-gate }
338*11a8fa6cSceastha
339*11a8fa6cSceastha static void
cfail(void)340*11a8fa6cSceastha cfail(void)
341*11a8fa6cSceastha {
3427c478bd9Sstevel@tonic-gate struct words *queue[QSIZE];
3437c478bd9Sstevel@tonic-gate struct words **front, **rear;
3447c478bd9Sstevel@tonic-gate struct words *state;
345*11a8fa6cSceastha char c;
346*11a8fa6cSceastha struct words *s;
3477c478bd9Sstevel@tonic-gate s = www;
3487c478bd9Sstevel@tonic-gate front = rear = queue;
349*11a8fa6cSceastha init:
3507c478bd9Sstevel@tonic-gate if ((s->inp) != 0) {
3517c478bd9Sstevel@tonic-gate *rear++ = s->nst;
3527c478bd9Sstevel@tonic-gate if (rear >= &queue[QSIZE - 1]) overflo();
3537c478bd9Sstevel@tonic-gate }
3547c478bd9Sstevel@tonic-gate if ((s = s->link) != 0) {
3557c478bd9Sstevel@tonic-gate goto init;
3567c478bd9Sstevel@tonic-gate }
3577c478bd9Sstevel@tonic-gate
358*11a8fa6cSceastha while (rear != front) {
3597c478bd9Sstevel@tonic-gate s = *front;
3607c478bd9Sstevel@tonic-gate if (front == &queue[QSIZE-1])
3617c478bd9Sstevel@tonic-gate front = queue;
3627c478bd9Sstevel@tonic-gate else front++;
363*11a8fa6cSceastha cloop:
3647c478bd9Sstevel@tonic-gate if ((c = s->inp) != 0) {
3657c478bd9Sstevel@tonic-gate *rear = (q = s->nst);
3667c478bd9Sstevel@tonic-gate if (front < rear)
3677c478bd9Sstevel@tonic-gate if (rear >= &queue[QSIZE-1])
3687c478bd9Sstevel@tonic-gate if (front == queue) overflo();
3697c478bd9Sstevel@tonic-gate else rear = queue;
3707c478bd9Sstevel@tonic-gate else rear++;
3717c478bd9Sstevel@tonic-gate else
3727c478bd9Sstevel@tonic-gate if (++rear == front) overflo();
3737c478bd9Sstevel@tonic-gate state = s->fail;
374*11a8fa6cSceastha floop:
3757c478bd9Sstevel@tonic-gate if (state == 0) state = www;
3767c478bd9Sstevel@tonic-gate if (state->inp == c) {
3777c478bd9Sstevel@tonic-gate q->fail = state->nst;
3787c478bd9Sstevel@tonic-gate if ((state->nst)->out == 1) q->out = 1;
3797c478bd9Sstevel@tonic-gate continue;
380*11a8fa6cSceastha } else if ((state = state->link) != 0)
3817c478bd9Sstevel@tonic-gate goto floop;
3827c478bd9Sstevel@tonic-gate }
3837c478bd9Sstevel@tonic-gate if ((s = s->link) != 0)
3847c478bd9Sstevel@tonic-gate goto cloop;
3857c478bd9Sstevel@tonic-gate }
3867c478bd9Sstevel@tonic-gate }
3877c478bd9Sstevel@tonic-gate
388*11a8fa6cSceastha static struct words *seen[50];
389*11a8fa6cSceastha
390*11a8fa6cSceastha static int
new(struct words * x)391*11a8fa6cSceastha new(struct words *x)
3927c478bd9Sstevel@tonic-gate {
3937c478bd9Sstevel@tonic-gate int i;
394*11a8fa6cSceastha for (i = 0; i < nfound; i++)
395*11a8fa6cSceastha if (seen[i] == x)
396*11a8fa6cSceastha return (0);
397*11a8fa6cSceastha seen[i] = x;
398*11a8fa6cSceastha return (1);
3997c478bd9Sstevel@tonic-gate }
400