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.

You might have seen my answer to another C question where I mentioned FSM! Here is how I do it:

FSM {
  STATE(x) {
    ...
    NEXTSTATE(y);
  }

  STATE(y) {
    ...
    if (x == 0) 
      NEXTSTATE(y);
    else 
      NEXTSTATE(x);
  }
}

With the following macros defined

#define FSM
#define STATE(x)      s_##x :
#define NEXTSTATE(x)  goto s_##x

This can be modified to suit the specific case. For example, you may have a file FSMFILE that you want to drive your FSM, so you could incorporate the action of reading next char into the the macro itself:

#define FSM
#define STATE(x)         s_##x : FSMCHR = fgetc(FSMFILE); sn_##x :
#define NEXTSTATE(x)     goto s_##x
#define NEXTSTATE_NR(x)  goto sn_##x

now you have two types of transitions: one goes to a state and read a new character, the other goes to a state without consuming any input.

You can also automate the handling of EOF with something like:

#define STATE(x)  s_##x  : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
                             goto sx_endfsm;\
                  sn_##x :

#define ENDFSM    sx_endfsm:

The good thing of this approach is that you can directly translate a state diagram you draw into working code and, conversely, you can easily draw a state diagram from the code.

In other techniques for implementing FSM the structure of the transitions is buried in control structures (while, if, switch ...) and controlled by variables value (tipically a state variable) and it may be a complex task to relate the nice diagram to a convoluted code.

I learned this technique from an article appeared on the great "Computer Language" magazine that, unfortunately, is no longer published.

there is also the logic grid which is more maintainable as the state machine gets bigger

For a simple state machine just use a switch statement and an enum type for your state. Do your transitions inside the switch statement based on your input. In a real program you would obviously change the "if(input)" to check for your transition points. Hope this helps.

typedef enum
{
    STATE_1 = 0,
    STATE_2,
    STATE_3
} my_state_t;

my_state_t state = STATE_1;

void foo(char input)
{
    ...
    switch(state)
    {
        case STATE_1:
            if(input)
                state = STATE_2;
            break;
        case STATE_2:
            if(input)
                state = STATE_3;
            else
                state = STATE_1;
            break;
        case STATE_3:
            ...
            break;
    }
    ...
}

For simple cases, you can use your switch style method. What I have found that works well in the past is to deal with transitions too:

static int current_state;    // should always hold current state -- and probably be an enum or something

void state_leave(int new_state) {
    // do processing on what it means to enter the new state
    // which might be dependent on the current state
}

void state_enter(int new_state) {
    // do processing on what is means to leave the current state
    // might be dependent on the new state

    current_state = new_state;
}

void state_process() {
    // switch statement to handle current state
}
   

I don't know anything about the boost library, but this type of approach is dead simple, doesn't require any external dependencies, and is easy to implement.

switch() is a powerful and standard way of implementing state machines in C, but it can decrease maintainability down if you have a large number of states. Another common method is to use function pointers to store the next state. This simple example implements a set/reset flip-flop:

/* Implement each state as a function with the same prototype */
void state_one(int set, int reset);
void state_two(int set, int reset);

/* Store a pointer to the next state */
void (*next_state)(int set, int reset) = state_one;

/* Users should call next_state(set, reset). This could
   also be wrapped by a real function that validated input
   and dealt with output rather than calling the function
   pointer directly. */

/* State one transitions to state one if set is true */
void state_one(int set, int reset) {
    if(set)
        next_state = state_two;
}

/* State two transitions to state one if reset is true */
void state_two(int set, int reset) {
    if(reset)
        next_state = state_one;
}

This article is a good one for the state pattern (though it is C++, not specifically C).

If you can put your hands on the book "Head First Design Patterns", the explanation and example are very clear.

You might want to look into the libero FSM generator software. From a state description language and/or a (windows) state diagram editor you may generate code for C, C++, java and many others ... plus nice documentation and diagrams. Source and binaries from iMatix

In my experience using the 'switch' statement is the standard way to handle multiple possible states. Although I am surpirsed that you are passing in a transition value to the per-state processing. I thought the whole point of a state machine was that each state performed a single action. Then the next action/input determines which new state to transition into. So I would have expected each state processing function to immediately perform whatever is fixed for entering state and then afterwards decide if transition is needed to another state.

There is a book titled Practical Statecharts in C/C++. However, it is way too heavyweight for what we need.

You can use minimalist UML state machine framework in c. https://github.com/kiishor/UML-State-Machine-in-C

It supports both finite and hierarchical state machine. It has only 3 API's, 2 structures and 1 enumeration.

The State machine is represented by state_machine_t structure. It is an abstract structure that can be inherited to create a state machine.

//! Abstract state machine structure
struct state_machine_t
{
   uint32_t Event;          //!< Pending Event for state machine
   const state_t* State;    //!< State of state machine.
};

State is represented by pointer to state_t structure in the framework.

If framework is configured for finite state machine then state_t contains,

typedef struct finite_state_t state_t;

// finite state structure
typedef struct finite_state_t{
  state_handler Handler;        //!< State handler function (function pointer)
  state_handler Entry;          //!< Entry action for state (function pointer)
  state_handler Exit;           //!< Exit action for state (function pointer)
}finite_state_t;

The framework provides an API dispatch_event to dispatch the event to the state machine and two API's for the state traversal.

state_machine_result_t dispatch_event(state_machine_t* const pState_Machine[], uint32_t quantity);

state_machine_result_t switch_state(state_machine_t* const, const state_t*);

state_machine_result_t traverse_state(state_machine_t* const, const state_t*);

For further details on how to implement hierarchical state machine refer the GitHub repository.

code examples
https://github.com/kiishor/UML-State-Machine-in-C/blob/master/demo/simple_state_machine/readme.md
https://github.com/kiishor/UML-State-Machine-in-C/blob/master/demo/simple_state_machine_enhanced/readme.md

In C++, consider the State pattern.

Your question is similar to "is there a typical Data Base implementation pattern"? The answer depends upon what do you want to achieve? If you want to implement a larger deterministic state machine you may use a model and a state machine generator. Examples can be viewed at www.StateSoft.org - SM Gallery. Janusz Dobrowolski

I would also prefer a table driven approach. I have used switch statements in the past. The main problem I have encountered is debugging transitions and ensuring that the designed state machine has been implemented properly. This occurred in cases where there was a large number of states and events.

With the table driven approach are the states and transitions are summarized in one place.

Below is a demo of this approach.

/*Demo implementations of State Machines
 *
 * This demo leverages a table driven approach and function pointers
 *
 * Example state machine to be implemented
 *
 *          +-----+      Event1        +-----+      Event2        +-----+
 *    O---->|  A  +------------------->|  B  +------------------->|  C  |
 *          +-----+                    +-----+                    +-----+
 *             ^                                                     |
 *             |                       Event3                        |
 *             +-----------------------------------------------------+
 *
 * States: A, B, C
 * Events: NoEvent (not shown, holding current state), Event1, Event2, Event3
 *
 * Partly leveraged the example here: http://web.archive.org/web/20160808120758/http://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-implementation-function-pointers-addon/
 *
 * This sample code can be compiled and run using GCC.
 * >> gcc -o demo_state_machine demo_state_machine.c
 * >> ./demo_state_machine
 */

#include <stdio.h>
#include <assert.h>

// Definitions of state id's, event id's, and function pointer
#define N_STATES  3
#define N_EVENTS  4

typedef enum {
  STATE_A,
  STATE_B,
  STATE_C,
} StateId;

typedef enum {
  NOEVENT,
  EVENT1,
  EVENT2,
  EVENT3,
} Event;
typedef void (*StateRoutine)();

// Assert on number of states and events defined
static_assert(STATE_C==N_STATES-1,
  "Number of states does not match defined number of states");
static_assert(EVENT3==N_EVENTS-1,
  "Number of events does not match defined number of events");

// Defining State, holds both state id and state routine
typedef struct {
    StateId id;
    StateRoutine routine;
}  State;

// General functions
void evaluate_state(Event e);

// State routines to be executed at each state
void state_routine_a(void);
void state_routine_b(void);
void state_routine_c(void);

// Defining each state with associated state routine
const State state_a = {STATE_A, state_routine_a};
const State state_b = {STATE_B, state_routine_b};
const State state_c = {STATE_C, state_routine_c};

// Defning state transition matrix as visualized in the header (events not
// defined, result in mainting the same state)
State state_transition_mat[N_STATES][N_EVENTS] = {
   { state_a, state_b, state_a, state_a},
   { state_b, state_b, state_c, state_b},
   { state_c, state_c, state_c, state_a}};

// Define current state and initialize
State current_state = state_a;

int main()
{
    while(1) {
    // Event to receive from user
    int ev;

    printf("----------------\n");
    printf("Current state: %c\n", current_state.id + 65);
    printf("Event to occur: ");
    // Receive event from user
    scanf("%u", &ev);
    evaluate_state((Event) ev); // typecast to event enumeration type
    printf("-----------------\n");
    };
    return (0);
}

/*
 * Determine state based on event and perform state routine
 */
void evaluate_state(Event ev)
{
    //Determine state based on event
  current_state = state_transition_mat[current_state.id][ev];
  printf("Transitioned to state: %c\n", current_state.id + 65);
    // Run state routine
    (*current_state.routine)();
}

/*
 * State routines
 */
void state_routine_a() {
  printf("State A routine ran. \n");

}
void state_routine_b() {
  printf("State B routine ran. \n");
}
void state_routine_c() {
  printf("State C routine ran. \n");
}

Boost has the statechart library. http://www.boost.org/doc/libs/1_36_0/libs/statechart/doc/index.html

I can't speak to the use of it, though. Not used it myself (yet)