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}