#pragma ident "%Z%%M% %I% %E% SMI"

#include <stdio.h>

#include <ctype.h>

#define MAXSIZ 700

#define QSIZE 400

struct words {

char inp;

char out;

struct words *nst;

struct words *link;

struct words *fail;

}

*www, *smax, *q;

char buf[2*BUFSIZ];

int nsucc;

int need;

char *instr;

int inct;

int rflag;

int xargc;

char **xargv;

int numwords;

int nfound;

static int flag = 0;

extern void err();

extern void *zalloc();

static void cfail(void);

static void cgotofn(void);

static void execute(void);

static char gch(void);

static int new(struct words *x);

static void overflo(void);

fgrep(int argc, char **argv)

{

nsucc = need = inct = rflag = numwords = nfound = 0;

instr = 0;

flag = 0;

if (www == 0)

www = (struct words *)zalloc(MAXSIZ, sizeof (*www));

if (www == NULL)

err(gettext("Can't get space for machines"), 0);

for (q = www; q < www+MAXSIZ; q++) {

q->inp = 0; q->out = 0; q->nst = 0; q->link = 0; q->fail = 0;

}

xargc = argc-1;

xargv = argv+1;

while (xargc > 0 && xargv[0][0] == '-') {

switch (xargv[0][1]) {

case 'r': /* return value only */

rflag++;

break;

case 'n': /* number of answers needed */

need = (int)xargv[1];

xargv++; xargc--;

break;

case 'i':

instr = xargv[1];

inct = (int)xargv[2]+2;

#if D2

fprintf(stderr, "inct %d xargv.2. %o %d\n", inct, xargv[2], xargv[2]);

#endif

xargv += 2; xargc -= 2;

break;

}

xargv++; xargc--;

}

if (xargc <= 0) {

write(2, "bad fgrep call\n", 15);

exit(2);

}

#if D1

fprintf(stderr, "before cgoto\n");

#endif

cgotofn();

#if D1

fprintf(stderr, "before cfail\n");

#endif

cfail();

#if D1

fprintf(stderr, "before execute instr %.20s\n", instr? instr: "");

fprintf(stderr, "end of string %d %c %c %c\n", inct,

instr ? instr[inct-3] : '\0',

instr ? instr[inct-2] : '\0',

instr ? instr[inct-1] : '\0');

#endif

execute();

#if D1

fprintf(stderr, "returning nsucc %d\n", nsucc);

fprintf(stderr, "fgrep done www %o\n", www);

#endif

return (nsucc == 0);

}

static void

execute(void)

{

char *p;

struct words *c;

char ch;

int ccount;

int f;

char *nlp;

f = 0;

ccount = instr ? inct : 0;

nfound = 0;

p = instr ? instr : buf;

if (need == 0) need = numwords;

nlp = p;

c = www;

#if D2

fprintf(stderr, "in execute ccount %d inct %d\n", ccount, inct);

#endif

for (;;) {

#if D3

fprintf(stderr, "down ccount\n");

#endif

if (--ccount <= 0) {

#if D2

fprintf(stderr, "ex loop ccount %d instr %o\n", ccount, instr);

#endif

if (instr) break;

if (p == &buf[2*BUFSIZ]) p = buf;

if (p > &buf[BUFSIZ]) {

if ((ccount = read(f, p,

&buf[2*BUFSIZ] - p)) <= 0)

break;

} else if ((ccount = read(f, p, BUFSIZ)) <= 0) break;

#if D2

fprintf(stderr, " normal read %d bytres\n", ccount);

{

char xx[20];

sprintf(xx, "they are %%.%ds\n", ccount);

fprintf(stderr, xx, p);

}

#endif

}

nstate:

ch = *p;

#if D2

fprintf(stderr, "roaming along in ex ch %c c %o\n", ch, c);

#endif

if (isupper(ch)) ch |= 040;

if (c->inp == ch) {

c = c->nst;

} else if (c->link != 0) {

c = c->link;

goto nstate;

} else {

c = c->fail;

if (c == 0) {

c = www;

istate:

if (c->inp == ch) {

c = c->nst;

} else if (c->link != 0) {

c = c->link;

goto istate;

}

} else goto nstate;

}

if (c->out && new(c)) {

#if D2

fprintf(stderr, " found: nfound %d need %d\n", nfound, need);

#endif

if (++nfound >= need) {

#if D1

fprintf(stderr, "found, p %o nlp %o ccount %d buf %o buf[2*BUFSIZ] %o\n",

p, nlp, ccount, buf, buf+2*BUFSIZ);

#endif

if (instr == 0)

while (*p++ != '\n') {

#if D3

fprintf(stderr, "down ccount2\n");

#endif

if (--ccount <= 0) {

if (p == &buf[2*BUFSIZ])

p = buf;

if (p > &buf[BUFSIZ]) {

if ((ccount = read(f, p,

&buf[2*BUFSIZ] - p))

<= 0)

break;

} else if ((ccount = read(f, p,

BUFSIZ)) <= 0)

break;

#if D2

fprintf(stderr, " read %d bytes\n", ccount);

{ char xx[20]; sprintf(xx, "they are %%.%ds\n", ccount);

fprintf(stderr, xx, p);

}

#endif

}

}

nsucc = 1;

if (rflag == 0) {

#if D2

fprintf(stderr, "p %o nlp %o buf %o\n", p, nlp, buf);

if (p > nlp)

{write(2, "XX\n", 3); write(2, nlp, p-nlp); write(2, "XX\n", 3); }

#endif

if (p > nlp) write(1, nlp, p-nlp);

else {

write(1, nlp,

&buf[2*BUFSIZ] - nlp);

write(1, buf, p-&buf[0]);

}

if (p[-1] != '\n') write(1, "\n", 1);

}

if (instr == 0) {

nlp = p;

c = www;

nfound = 0;

}

} else

ccount++;

continue;

}

#if D2

fprintf(stderr, "nr end loop p %o\n", p);

#endif

if (instr)

p++;

else

if (*p++ == '\n')

{

nlp = p;

c = www;

nfound = 0;

}

}

if (instr == 0)

close(f);

}

static void

cgotofn(void)

{

char c;

struct words *s;

s = smax = www;

nword:

for (;;) {

#if D1

fprintf(stderr, " in for loop c now %o %c\n", c, c > ' ' ? c : ' ');

#endif

if ((c = gch()) == 0)

return;

else if (c == '\n') {

s->out = 1;

s = www;

} else {

loop:

if (s->inp == c) {

s = s->nst;

continue;

}

if (s->inp == 0) goto enter;

if (s->link == 0) {

if (smax >= &www[MAXSIZ - 1]) overflo();

s->link = ++smax;

s = smax;

goto enter;

}

s = s->link;

goto loop;

}

}

enter:

do {

s->inp = c;

if (smax >= &www[MAXSIZ - 1]) overflo();

s->nst = ++smax;

s = smax;

}

while ((c = gch()) != '\n')

;

smax->out = 1;

s = www;

numwords++;

goto nword;

}

static char

gch(void)

{

static char *s;

if (flag == 0) {

flag = 1;

s = *xargv++;

#if D1

fprintf(stderr, "next arg is %s xargc %d\n", xargc > 0 ? s : "", xargc);

#endif

if (xargc-- <= 0)

return (0);

}

if (*s)

return (*s++);

for (flag = 0; flag < 2*BUFSIZ; flag++)

buf[flag] = 0;

flag = 0;

return ('\n');

}

static void

overflo(void)

{

write(2, "wordlist too large\n", 19);

exit(2);

}

static void

cfail(void)

{

struct words *queue[QSIZE];

struct words **front, **rear;

struct words *state;

char c;

struct words *s;

s = www;

front = rear = queue;

init:

if ((s->inp) != 0) {

*rear++ = s->nst;

if (rear >= &queue[QSIZE - 1]) overflo();

}

if ((s = s->link) != 0) {

goto init;

}

while (rear != front) {

s = *front;

if (front == &queue[QSIZE-1])

front = queue;

else front++;

cloop:

if ((c = s->inp) != 0) {

*rear = (q = s->nst);

if (front < rear)

if (rear >= &queue[QSIZE-1])

if (front == queue) overflo();

else rear = queue;

else rear++;

else

if (++rear == front) overflo();

state = s->fail;

floop:

if (state == 0) state = www;

if (state->inp == c) {

q->fail = state->nst;

if ((state->nst)->out == 1) q->out = 1;

continue;

} else if ((state = state->link) != 0)

goto floop;

}

if ((s = s->link) != 0)

goto cloop;

}

}

static struct words *seen[50];

static int

new(struct words *x)

{

int i;

for (i = 0; i < nfound; i++)

if (seen[i] == x)

return (0);

seen[i] = x;

return (1);

}