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