C State-Machine Design

C state-machine design

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.

Is there a typical state machine implementation pattern?

I prefer to use a table driven approach for most state machines:

typedef enum { STATE_INITIAL, STATE_FOO, STATE_BAR, NUM_STATES } state_t;
typedef struct instance_data instance_data_t;
typedef state_t state_func_t( instance_data_t *data );

state_t do_state_initial( instance_data_t *data );
state_t do_state_foo( instance_data_t *data );
state_t do_state_bar( instance_data_t *data );

state_func_t* const state_table[ NUM_STATES ] = {
do_state_initial, do_state_foo, do_state_bar
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
return state_table[ cur_state ]( data );
};

int main( void ) {
state_t cur_state = STATE_INITIAL;
instance_data_t data;

while ( 1 ) {
cur_state = run_state( cur_state, &data );

// do other program logic, run other state machines, etc
}
}

This can of course be extended to support multiple state machines, etc. Transition actions can be accommodated as well:

typedef void transition_func_t( instance_data_t *data );

void do_initial_to_foo( instance_data_t *data );
void do_foo_to_bar( instance_data_t *data );
void do_bar_to_initial( instance_data_t *data );
void do_bar_to_foo( instance_data_t *data );
void do_bar_to_bar( instance_data_t *data );

transition_func_t * const transition_table[ NUM_STATES ][ NUM_STATES ] = {
{ NULL, do_initial_to_foo, NULL },
{ NULL, NULL, do_foo_to_bar },
{ do_bar_to_initial, do_bar_to_foo, do_bar_to_bar }
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
state_t new_state = state_table[ cur_state ]( data );
transition_func_t *transition =
transition_table[ cur_state ][ new_state ];

if ( transition ) {
transition( data );
}

return new_state;
};

The table driven approach is easier to maintain and extend and simpler to map to state diagrams.

state machines tutorials

State machines are very simple in C if you use function pointers.

Basically you need 2 arrays - one for state function pointers and one for state transition rules. Every state function returns the code, you lookup state transition table by state and return code to find the next state and then just execute it.

int entry_state(void);
int foo_state(void);
int bar_state(void);
int exit_state(void);

/* array and enum below must be in sync! */
int (* state[])(void) = { entry_state, foo_state, bar_state, exit_state};
enum state_codes { entry, foo, bar, end};

enum ret_codes { ok, fail, repeat};
struct transition {
enum state_codes src_state;
enum ret_codes ret_code;
enum state_codes dst_state;
};
/* transitions from end state aren't needed */
struct transition state_transitions[] = {
{entry, ok, foo},
{entry, fail, end},
{foo, ok, bar},
{foo, fail, end},
{foo, repeat, foo},
{bar, ok, end},
{bar, fail, end},
{bar, repeat, foo}};

#define EXIT_STATE end
#define ENTRY_STATE entry

int main(int argc, char *argv[]) {
enum state_codes cur_state = ENTRY_STATE;
enum ret_codes rc;
int (* state_fun)(void);

for (;;) {
state_fun = state[cur_state];
rc = state_fun();
if (EXIT_STATE == cur_state)
break;
cur_state = lookup_transitions(cur_state, rc);
}

return EXIT_SUCCESS;
}

I don't put lookup_transitions() function as it is trivial.

That's the way I do state machines for years.

State machines in C

I like the Quantum Leaps approach.

The current state is a pointer to a function that takes an event object as argument. When an event happens, just call the state function with that event; The function can then do its work and transition to another state by just setting the state to another function.

E.g.:

// State type and variable, notice that it's a function pointer.
typedef void (*State)(int);
State state;

// A couple of state functions.
void state_xyz(int event) { /*...*/ }
void state_init(int event) {
if (event == E_GO_TO_xyz) {
// State transition done simply by changing the state to another function.
state = state_xyz;
}
}

// main contains the event loop here:
int main() {
int e;
// Initial state.
state = state_init;
// Receive event, dispatch it, repeat... No 'switch'!
while ((e = wait_for_event()) != E_END) {
state(e);
}
return 0;
}

The QL frameworks provides helpers for extra things like entry/exit/init actions, hierarchical state machines, etc. I highly recommend the book for a deeper explanation and good implementation of this.

State Machine Designing

According to the "gang of four", the State design pattern is applicable when an object's behaviour depends on its state and it must change behaviour at run time, depending on that state.

The description of your state machine, which changes state based on an event, seems to match this description.

class StateMachine {    // state machine that processes events received
State *s;
public:
StateMachine(); // constructor: here you shall set initial state
void process (Event* e); // processes the event and sets the next state
bool isReady (); // example of other requests
};

The principle of this pattern is to have an abstract base class, defining all the potential states dependent "actions" that StateMachine may delegate to a state.

class State {
public:
virtual void process (StateMachine *m, Event* e)=0; // called by state machine / pure virtual MUST be implemented in concrete state
virtual bool isReady(StateMachine *m); // example
... // other "actions"
};

The interface between your state and the state machine would then be easy to define. For example:

void StateMachine::Process (Event *e) {
s->Process (this, e); // calls the Process() of the current state
}

Derived concrete states shall then implement the different behaviours. As this *pattern works with virtual functions in C++, all the actions must be defined for each concrete state (either in base class or in the derived). This is a direct consequence of defining virtual functions.

But for actions that are not relevant for all the states, you may have a default action, either doing nothing, or triggering an error (error message, exception, ...). It depends on your general design, whether you prevent such situations to happen or not.

For example:

bool State::isReady(StateMachine *m) {  // if this request is only relevant for a couple of states
throw std::exception ("unauthorized request"); // trigger an exception if it happens
return false;
} // this is done by default, except for concrete state that defines somtehing else

According to your description, I would really go for the state pattern.



Related Topics



Leave a reply



Submit