C state-machine design

Question

I am crafting a small project in mixed C and C++. I am building one small-ish state-machine at the heart of one of my worker thread.

I was wondering if you gurus on SO would share your state-machine design techniques.

NOTE: I am primarily after tried & tested implementation techniques.

UPDATED: Based on all the great input gathered on SO, I've settled on this architecture:

Answer 1

Your question is quite generic,
Here are two reference articles that might be useful,

1. Embedded State Machine Implementation

   This article describes a simple approach to implementing a state machine for an embedded system. For purposes of this article, a state machine is defined as an algorithm that can be in one of a small number of states. A state is a condition that causes a prescribed relationship of inputs to outputs, and of inputs to next states.
   A savvy reader will quickly note that the state machines described in this article are Mealy machines. A Mealy machine is a state machine where the outputs are a function of both present state and input, as opposed to a Moore machine, in which the outputs are a function only of state.

   • Coding State Machines in C and C++

     My preoccupation in this article is with state-machine fundamentals and some straightforward programming guidelines for coding state machines in C or C++. I hope that these simple techniques can become more common, so that you (and others) can readily see the state-machine structure right from the source code.

Answer 2

Given that you imply you can use C++ and hence OO code, I would suggest evaluating the 'GoF'state pattern (GoF = Gang of Four, the guys who wrote the design patterns book which brought design patterns into the limelight).

It is not particularly complex and it is widely used and discussed so it is easy to see examples and explanations on line.

It will also quite likely be recognizable by anyone else maintaining your code at a later date.

If efficiency is the worry, it would be worth actually benchmarking to make sure that a non OO approach is more efficient as lots of factors affect performance and it is not always simply OO bad, functional code good. Similarly, if memory usage is a constraint for you it is again worth doing some tests or calculations to see if this will actually be an issue for your particular application if you use the state pattern.

The following are some links to the 'Gof' state pattern, as Craig suggests:

• http://en.wikipedia.org/wiki/State_pattern
• http://www.vincehuston.org/dp/state.html

Answer 3

State machines that I've designed before (C, not C++) have all come down to a struct array and a loop. The structure basically consists of a state and event (for look-up) and a function that returns the new state, something like:

typedef struct {
    int st;
    int ev;
    int (*fn)(void);
} tTransition;

Then you define your states and events with simple defines (the ANY ones are special markers, see below):

#define ST_ANY              -1
#define ST_INIT              0
#define ST_ERROR             1
#define ST_TERM              2
: :
#define EV_ANY              -1
#define EV_KEYPRESS       5000
#define EV_MOUSEMOVE      5001

Then you define all the functions that are called by the transitions:

static int GotKey (void) { ... };
static int FsmError (void) { ... };

All these function are written to take no variables and return the new state for the state machine. In this example global variables are used for passing any information into the state functions where necessary.

Using globals isn't as bad as it sounds since the FSM is usually locked up inside a single compilation unit and all variables are static to that unit (which is why I used quotes around "global" above - they're more shared within the FSM, than truly global). As with all globals, it requires care.

The transitions array then defines all possible transitions and the functions that get called for those transitions (including the catch-all last one):

tTransition trans[] = {
    { ST_INIT, EV_KEYPRESS, &GotKey},
    : :
    { ST_ANY, EV_ANY, &FsmError}
};
#define TRANS_COUNT (sizeof(trans)/sizeof(*trans))

What that means is: if you're in the ST_INIT state and you receive the EV_KEYPRESS event, make a call to GotKey.

The workings of the FSM then become a relatively simple loop:

state = ST_INIT;
while (state != ST_TERM) {
    event = GetNextEvent();
    for (i = 0; i < TRANS_COUNT; i++) {
        if ((state == trans[i].st) || (ST_ANY == trans[i].st)) {
            if ((event == trans[i].ev) || (EV_ANY == trans[i].ev)) {
                state = (trans[i].fn)();
                break;
            }
        }
    }
}

As alluded to above, note the use of ST_ANY as wild-cards, allowing an event to call a function no matter the current state. EV_ANY also works similarly, allowing any event at a specific state to call a function.

It can also guarantee that, if you reach the end of the transitions array, you get an error stating your FSM hasn't been built correctly (by using the ST_ANY/EV_ANY combination.

I've used code similar for this on a great many communications projects, such as an early implementation of communications stacks and protocols for embedded systems. The big advantage was its simplicity and relative ease in changing the transitions array.

I've no doubt there will be higher-level abstractions which may be more suitable nowadays but I suspect they'll all boil down to this same sort of structure.

---

And, as ldog states in a comment, you can avoid the globals altogether by passing a structure pointer to all functions (and using that in the event loop). This will allow multiple state machines to run side-by-side without interference.

Just create a structure type which holds the machine-specific data (state at a bare minimum) and use that instead of the globals.

The reason I've rarely done that is simply because most of the state machines I've written have been singleton types (one-off, at-process-start, configuration file reading for example), not needing to run more than one instance. But it has value if you need to run more than one.

Answer 4

I've done something similar to what paxdiablo describes, only instead of an array of state/event transitions, I set up a 2-dimensional array of function pointers, with the event value as the index of one axis and the current state value as the other. Then I just call state = state_table[event][state](params) and the right thing happens. Cells representing invalid state/event combinations get a pointer to a function that says so, of course.

Obviously, this only works if the state and event values are both contiguous ranges and start at 0 or close enough.

Answer 5

boost.org comes with 2 different state chart implementations:

• Meta State Machine
• Statechart

As always, boost will beam you into template hell.

The first library is for more performance-critical state machines. The second library gives you a direct transition path from a UML Statechart to code.

Here's the SO question asking for a comparison between the two where both of the authors respond.

Answer 6

This series of Ars OpenForum posts about a somewhat complicated bit of control logic includes a very easy-to-follow implementation as a state machine in C.