One-dimensional state transition table

Question

I am looking for some implementation (ideas) of the one-dimensional state table in C. The transition are kind of objects (struct) that contain:

Pointer to the guard function
Next state
List of pointers to action functions.

I am looking at C state-machine design but in my case I have multiple conditions to form an event. Is there any generic approach or simple FSM sw processor suitable for embedded system?

Suggestion: might want to edit your tags - I'd suggest removing "state" and "machine", and using "statemachine" instead. — Dan, Mar 25 '11 at 16:15
What exactly do you mean by "multiple conditions to form an event"? — Michael Burr, Mar 25 '11 at 17:50

score 0 · Answer 1 · answered Mar 25 '11 at 16:21

0

StateMachine tables usually have 2 dimensions (where I am), (what symbol/token/source I have), and the intersection of both are cells (where I'll go, from where I am, when what symbol/token/source I have)

answered Mar 25 '11 at 16:21

umlcat

4,091
3
19
29

score 0 · Accepted Answer · answered Apr 01 '11 at 08:11

The usual approach is to store pointer to a conditional function. You implement the set of conditions as separate functions, and attach a pointer to the right condition in the table. Each function tests for given set of conditions. You iterate through the list till one of pointed functions returns true. Of course "current state" can be used as part of conditions, which removes the need for 2d array.

  struct {
       bool(*test)();           //the condition
       void(*onsuccess)();      //event
  } condition;

This may be inefficient if the conditions repeat a lot in a chain like:

  ev1: (a && b && c)
  ev2: (a && !b && c)
  ev3: (a && b && d)
  ev4: (a && !b && !c)
  ev5: (!a)

(most events tests for a separately, if testing for a is computationally expensive it will take much more CPU time than necessary).

In this case you'd have to remap the condition_set -> event list into a single decision tree - much harder to maintain but more CPU-efficient:

   a:
       b:
           c: ev1
           d: ev3
      !b:
           c: ev2
          !c: ev4
  !a: ev5

This of course cannot be a simple 1-dimensional list any more, but requires a tree-like structure instead, say, branched linked list:

  struct {
       bool(*test)();           //the condition
       void(*onsuccess)();      //event (if any)
       condition* next_sibling; //other conditions dependent on parent but independent from this one,
       condition* first_child;  //other conditions dependent on this one,
  } condition;

NULL on any of the pointers means "no such item" (except on "test" which can't be null). And of course recursion required to traverse the list.

One-dimensional state transition table

2 Answers2