state machines tutorials [closed]
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 entryint 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.
I prefer using function pointers over gigantic switch statements, but in contrast to qrdl's answer I normally don't use explicit return codes or transition tables.
Also, in most cases you'll want a mechanism to pass along additional data. Here's an example state machine:
#include <stdio.h>struct state;typedef void state_fn(struct state *);struct state{ state_fn * next; int i; // data};state_fn foo, bar;void foo(struct state * state){ printf("%s %i\n", __func__, ++state->i); state->next = bar;}void bar(struct state * state){ printf("%s %i\n", __func__, ++state->i); state->next = state->i < 10 ? foo : 0;}int main(void){ struct state state = { foo, 0 }; while(state.next) state.next(&state);}
Unfortunately, most of the articles on state machines are written for C++ or other languages that have direct support for polymorphism as it's nice to model the states in an FSM implementation as classes that derive from an abstract state class.
However, it's pretty easy to implement state machines in C using either switch statements to dispatch events to states (for simple FSMs, they pretty much code right up) or using tables to map events to state transitions.
There are a couple of simple, but decent articles on a basic framework for state machines in C here:
- http://www.gedan.net/2008/09/08/finite-state-machine-matrix-style-c-implementation/
- http://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-implementation-function-pointers-addon/
Edit: Site "under maintenance", web archive links:
- http://web.archive.org/web/20160517005245/http://www.gedan.net/2008/09/08/finite-state-machine-matrix-style-c-implementation
- http://web.archive.org/web/20160808120758/http://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-implementation-function-pointers-addon/
switch statement-based state machines often use a set of macros to 'hide' the mechanics of the switch statement (or use a set of if/then/else statements instead of a switch) and make what amounts to a "FSM language" for describing the state machine in C source. I personally prefer the table-based approach, but these certainly have merit, are widely used, and can be effective especially for simpler FSMs.
One such framework is outlined by Steve Rabin in "Game Programming Gems" Chapter 3.0 (Designing a General Robust AI Engine).
A similar set of macros is discussed here:
If you're also interested in C++ state machine implementations there's a lot more that can be found. I'll post pointers if you're interested.