State machines in C

What is the best way to write a state machine in C?

I usually write a开发者_StackOverflow社区 big switch-case statement in a for(;;), with callbacks to re-enter the state machine when an external operation is finished.

Do you know a more efficient way?

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.

The best way is largely subjective, but a common way is to use a "table-based" approach where you map state codes (enums or some other integral type) to function pointers. The function returns your next state and other associated data and you loop through this until the terminal state is reached. This might in fact be what you are describing as your approach above.

That's pretty much the standard approach. If you're interested in studying a well considered library and comparing specifics, take a look at Ragel:

Ragel compiles executable finite state machines from regular languages. Ragel targets C, C++, Objective-C, D, Java and Ruby. Ragel state machines can not only recognize byte sequences as regular expression machines do, but can also execute code at arbitrary points in the recognition of a regular language. Code embedding is done using inline operators that do not disrupt the regular language syntax.

Switch statements are a good way to get started, but they tend to get unwieldy when the FSM gets larger.

A couple related (or duplicate) SO questions with great information and ideas:

• state machines tutorials
• C state-machine design

I used this pattern. Is there a typical state machine implementation pattern? (check best answer).

But i also add some features
1. Information about previous state.
2. Parameter passing
3. Adding external events like global timeout and "resseting SM"

I found state machines little less cryptic and maintainable.
Anyway, I still think state machines are most difficult and annoying programming task.(I got so far)

An alternative approach is a 2D array that describes for each state/event combination the actions to execute and the next state to go to. This can get trickier to manage when you need to transition to different states depending on 'circumstances', but it can be made to work well. You have an event recognizer function which returns the next event; you have the table where each entry in the table identifies the function to call on receiving the event and the next state to go to - unless the called function overrides that state.

Actually generating such code is fiddlier - it depends on how the FSM is described in the first place. Spotting duplicate actions is often important. Often, you can rely on 'sparse matrix' techniques that do not record error handling explicitly: if the entry logically exists in the sparse matrix, you act on that event/state information, but if the entry does not exist you fall back onto appropriate error reporting and resynchronization code.

A 2D array of pointers to structures can be passed into a generic FSM function; the fact that you write a triple-pointer is enough to make you cautious about what is going on. (I wrote one of those back in March 1986 - I don't have the source for that on disk any more, though I do still have a printout of the document that described it.)

Have a look here: http://code.google.com/p/fwprofile/

It's an open source version (GNU GPLv3) of the state machine implemented in C. The concept and implementation is well-suited for use in mission-critical applications. There are deployments in industrial applications.

I use function pointers and a 2d look-up table where I use the state for one parameter and the event as the other.

I use excel (or any spreadsheet tool) to map a function to every state/event combination.

When an event occurs, I que it up, so then I have something that looks like this

int main(void)
{
    StateList currentState = start_up;
    EventList currentEvent;

    uint8_t stateArray[STATE_COUNT][EVENT_COUNT];

    InitializeStateArray(stateArray);
    InitializeEventQue();

    while(1)
    {
        currentEvent = GetPriorityEvent();
        currentState = (StateList)(*(stateArray[currentState][currentEvent]))();
    }
    return 1;  //should never get here
}

This method essentially forces the developer to consider all possible events in each state, and in my experience makes debugging a little easier.

You can use minimalist uml-state-machine framework implemented in c. It supports both finite and hierarchical state machine. The framework is very minimalist. 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;

If framework is configured to support hierarchical state machine. It contains additional three members to represent the hierarchical relation between the states.

typedef struct hierarchical_state_t state_t;

//! Hierarchical state structure
typedef struct hierarchical_state_t
{
  state_handler Handler;      //!< State handler function
  state_handler Entry;        //!< Entry action for state
  state_handler Exit;         //!< Exit action for state.

  const state_t* const Parent;    //!< Parent state of the current state.
  const state_t* const Node;      //!< Child states of the current state.
  uint32_t Level;                 //!< Hierarchy level from the top state.
}hierarchical_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 pState_Machine, const state_t* pTarget_State);

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

For more details refer to GitHub project.

check this out "https://github.com/knor12/NKFSMCompiler" it helps generate C Language code for a state machine defined in an scxml or csv file. an example is provided.