/*
 * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
/*	  All Rights Reserved  	*/

/*
 * Copyright (c) 1980 Regents of the University of California.
 * All rights reserved. The Berkeley software License Agreement
 * specifies the terms and conditions for redistribution.
 */

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


#include <stdio.h>
#include <ctype.h>
/*
 * fgrep -- print all lines containing any of a set of keywords
 *
 *	status returns:
 *		0 - ok, and some matches
 *		1 - ok, but no matches
 *		2 - some error
 */
#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);

int
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);
}