1/* Copyright (c) 1985 Ceriel J.H. Jacobs */
  2
  3#include <ctype.h>
  4#include "in_all.h"
  5#include "machine.h"
  6#include "getline.h"
  7#include "assert.h"
  8
  9/*
 10 * Add part of finite state machine to recognize the string s.
 11 */
 12
 13static int
 14addtomach(char *s, int cnt, struct state **list)
 15{
 16
 17	struct state *l;
 18	int i = FSM_OKE; /* Return value */
 19	int j;
 20
 21	for (;;) {
 22		l = *list;
 23		if (!l) {
 24			/*
 25			 * Create new list element
 26			 */
 27			*list = l = (struct state *)alloc(sizeof(*l));
 28			l->s_char = *s;
 29			l->s_endstate = 0;
 30			l->s_match = 0;
 31			l->s_next = 0;
 32		}
 33		if (l->s_char == *s) {
 34			/*
 35			 * Continue with next character
 36			 */
 37			if (!*++s) {
 38				/*
 39				 * No next character
 40				 */
 41				j = l->s_endstate;
 42				l->s_endstate = 1;
 43				if (l->s_match || j) {
 44					/*
 45					 * If the state already was an endstate,
 46					 * or has a successor, the currently
 47					 * added string is a prefix of an
 48					 * already recognized string
 49					 */
 50					return FSM_ISPREFIX;
 51				}
 52				l->s_cnt = cnt;
 53				return i;
 54			}
 55			if (l->s_endstate) {
 56				/*
 57				 * In this case, the currently added string has
 58				 * a prefix that is an already recognized
 59				 * string.
 60				 */
 61				i = FSM_HASPREFIX;
 62			}
 63			list = &(l->s_match);
 64			continue;
 65		}
 66		list = &(l->s_next);
 67	}
 68	/* NOTREACHED */
 69}
 70
 71/*
 72 * Add a string to the FSM.
 73 */
 74
 75int
 76addstring(char *s, int cnt, struct state **machine)
 77{
 78
 79	if (!s || !*s) {
 80		return FSM_ISPREFIX;
 81	}
 82	return addtomach(s, cnt, machine);
 83}
 84
 85/*
 86 * Match string s with the finite state machine.
 87 * If it matches, the number of characters actually matched is returned,
 88 * and the count is put in the word pointed to by i.
 89 * If the string is a prefix of a string that could be matched,
 90 * FSM_ISPREFIX is returned. Otherwise, 0 is returned.
 91 */
 92
 93int
 94match(char *s, int *i, struct state *mach)
 95{
 96
 97	char *s1 = s; /* Walk through string */
 98	struct state *mach1 = 0;
 99	/* Keep track of previous state */
100
101	while (mach && *s1) {
102		if (mach->s_char == *s1) {
103			/*
104			 * Current character matches. Carry on with next
105			 * character and next state
106			 */
107			mach1 = mach;
108			mach = mach->s_match;
109			s1++;
110			continue;
111		}
112		mach = mach->s_next;
113	}
114	if (!mach1) {
115		/*
116		 * No characters matched
117		 */
118		return 0;
119	}
120	if (mach1->s_endstate) {
121		/*
122		 * The string matched
123		 */
124		*i = mach1->s_cnt;
125		return s1 - s;
126	}
127	if (!*s1) {
128		/*
129		 * The string matched a prefix
130		 */
131		return FSM_ISPREFIX;
132	}
133	return 0;
134}