131 	fa *f;  in mkdfa()  local
141 	if ((f = (fa *)calloc(1, sizeof (fa) + poscnt * sizeof (rrow))) == NULL)  in mkdfa()
144 	f->accept = poscnt-1;  in mkdfa()
145 	cfoll(f, p1);	/* set up follow sets */  in mkdfa()
147 	if ((f->posns[0] =  in mkdfa()
148 	    (int *)calloc(1, *(f->re[0].lfollow) * sizeof (int))) == NULL) {  in mkdfa()
151 	if ((f->posns[1] = (int *)calloc(1, sizeof (int))) == NULL)  in mkdfa()
153 	*f->posns[1] = 0;  in mkdfa()
154 	f->initstat = makeinit(f, anchor);  in mkdfa()
155 	f->anchor = anchor;  in mkdfa()
156 	f->restr = tostring(s);  in mkdfa()
157 	return (f);  in mkdfa()
161 makeinit(fa *f, int anchor)  in makeinit()  argument
165 	f->curstat = 2;  in makeinit()
166 	f->out[2] = 0;  in makeinit()
167 	f->reset = 0;  in makeinit()
168 	k = *(f->re[0].lfollow);  in makeinit()
169 	xfree(f->posns[2]);  in makeinit()
170 	if ((f->posns[2] = (int *)calloc(1, (k+1) * sizeof (int))) == NULL)  in makeinit()
173 		(f->posns[2])[i] = (f->re[0].lfollow)[i];  in makeinit()
175 	if ((f->posns[2])[1] == f->accept)  in makeinit()
176 		f->out[2] = 1;  in makeinit()
178 		f->gototab[2][i] = 0;  in makeinit()
179 	f->curstat = cgoto(f, 2, HAT);  in makeinit()
181 		*f->posns[2] = k-1;	/* leave out position 0 */  in makeinit()
183 			(f->posns[0])[i] = (f->posns[2])[i];  in makeinit()
186 		f->out[0] = f->out[2];  in makeinit()
187 		if (f->curstat != 2)  in makeinit()
188 			--(*f->posns[f->curstat]);  in makeinit()
190 	return (f->curstat);  in makeinit()
305 cfoll(fa *f, Node *v)  in cfoll()  argument
312 		f->re[(int)left(v)].ltype = type(v);  in cfoll()
313 		f->re[(int)left(v)].lval = (int)right(v);  in cfoll()
314 		for (i = 0; i <= f->accept; i++)  in cfoll()
320 		f->re[(int)left(v)].lfollow = p;  in cfoll()
322 		for (i = f->accept; i >= 0; i--) {  in cfoll()
328 		cfoll(f, left(v));  in cfoll()
332 		cfoll(f, left(v));  in cfoll()
333 		cfoll(f, right(v));  in cfoll()
428 match(fa *f, uchar *p)  in match()  argument
432 	s = f->reset ? makeinit(f, 0) : f->initstat;  in match()
433 	if (f->out[s])  in match()
436 		if ((ns = f->gototab[s][*p]) != 0)  in match()
439 			s = cgoto(f, s, *p);  in match()
440 		if (f->out[s])  in match()
447 pmatch(fa *f, uchar *p)  in pmatch()  argument
453 	if (f->reset) {  in pmatch()
454 		f->initstat = s = makeinit(f, 1);  in pmatch()
456 		s = f->initstat;  in pmatch()
463 			if (f->out[s])		/* final state */  in pmatch()
465 			if ((ns = f->gototab[s][*q]) != 0)  in pmatch()
468 				s = cgoto(f, s, *q);  in pmatch()
477 		if (f->out[s])  in pmatch()
485 		if (f->reset) {  in pmatch()
486 			for (i = 2; i <= f->curstat; i++)  in pmatch()
487 				xfree(f->posns[i]);  in pmatch()
488 			k = *f->posns[0];  in pmatch()
489 			if ((f->posns[2] =  in pmatch()
494 				(f->posns[2])[i] = (f->posns[0])[i];  in pmatch()
495 			f->initstat = f->curstat = 2;  in pmatch()
496 			f->out[2] = f->out[0];  in pmatch()
498 				f->gototab[2][i] = 0;  in pmatch()
505 nematch(fa *f, uchar *p)  in nematch()  argument
511 	if (f->reset) {  in nematch()
512 		f->initstat = s = makeinit(f, 1);  in nematch()
514 		s = f->initstat;  in nematch()
520 			if (f->out[s])		/* final state */  in nematch()
522 			if ((ns = f->gototab[s][*q]) != 0)  in nematch()
525 				s = cgoto(f, s, *q);  in nematch()
534 		if (f->out[s])  in nematch()
542 		if (f->reset) {  in nematch()
543 			for (i = 2; i <= f->curstat; i++)  in nematch()
544 				xfree(f->posns[i]);  in nematch()
545 			k = *f->posns[0];  in nematch()
546 			if ((f->posns[2] =  in nematch()
551 				(f->posns[2])[i] = (f->posns[0])[i];  in nematch()
552 			f->initstat = f->curstat = 2;  in nematch()
553 			f->out[2] = f->out[0];  in nematch()
555 				f->gototab[2][i] = 0;  in nematch()
774 cgoto(fa *f, int s, int c)  in cgoto()  argument
779 	for (i = 0; i <= f->accept; i++)  in cgoto()
783 	p = f->posns[s];  in cgoto()
785 		if ((k = f->re[p[i]].ltype) != FINAL) {  in cgoto()
786 			if (k == CHAR && c == f->re[p[i]].lval ||  in cgoto()
790 			    member(c, (uchar *)f->re[p[i]].lval) ||  in cgoto()
792 			    !member(c, (uchar *)f->re[p[i]].lval) &&  in cgoto()
794 				q = f->re[p[i]].lfollow;  in cgoto()
807 	for (i = f->accept; i >= 0; i--)  in cgoto()
812 	for (i = 1; i <= f->curstat; i++) {  in cgoto()
813 		p = f->posns[i];  in cgoto()
820 		f->gototab[s][c] = i;  in cgoto()
826 	if (f->curstat >= NSTATES-1) {  in cgoto()
827 		f->curstat = 2;  in cgoto()
828 		f->reset = 1;  in cgoto()
830 			xfree(f->posns[i]);  in cgoto()
832 		++(f->curstat);  in cgoto()
834 		f->gototab[f->curstat][i] = 0;  in cgoto()
835 	xfree(f->posns[f->curstat]);  in cgoto()
839 	f->posns[f->curstat] = p;  in cgoto()
840 	f->gototab[s][c] = f->curstat;  in cgoto()
843 	if (setvec[f->accept])  in cgoto()
844 		f->out[f->curstat] = 1;  in cgoto()
846 		f->out[f->curstat] = 0;  in cgoto()
847 	return (f->curstat);  in cgoto()
851 freefa(fa *f)  in freefa()  argument
856 	if (f == NULL)  in freefa()
858 	for (i = 0; i <= f->curstat; i++)  in freefa()
859 		xfree(f->posns[i]);  in freefa()
860 	for (i = 0; i <= f->accept; i++)  in freefa()
861 		xfree(f->re[i].lfollow);  in freefa()
862 	xfree(f->restr);  in freefa()
863 	xfree(f);  in freefa()