cdesign-patternsfinite-automata

Is there a typical state machine implementation pattern?


We need to implement a simple state machine in C.
Is a standard switch statement the best way to go?
We have a current state (state) and a trigger for the transition.


switch(state)
{
  case STATE_1:
     state = DoState1(transition);
     break;
  case STATE_2:
     state = DoState2(transition);
     break;
}
...
DoState2(int transition)
{
   // Do State Work
   ...
   if(transition == FROM_STATE_2) {
     // New state when doing STATE 2 -> STATE 2
   }
   if(transition == FROM_STATE_1) {
    // New State when moving STATE 1 -> STATE 2
   }
   return new_state;
}

Is there a better way for simple state machines

EDIT: For C++, I think the Boost Statechart library might be the way to go. However, it does not help with C. Lets concentrate on the C use case.


Solution

  • 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.