State machines in C

Question

What is the best way to write a state machine in C?
I usually write a 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?

Solution 1

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.

Solution 2

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.

Solution 3

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.

Solution 4

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

Solution 5

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)

View more solutions

Comments

[Craig]

i did this with AI, very nice way

[squelart]

This method eliminates one level of switch or table lookup, as the state is a straight pointer to a function that you just call. However, as usual, you can only be sure of the actual speed increase by testing it! It should help with maintenance too, which can be important in large-enough project.

[ack]

Very nice, but could you turn these E_*'s into a typedef enum please? (see: stackoverflow.com/a/1102556/588561) This leverages what type-checking C has (admittedly, not much) to catch more errors. This is particularly important when mixing multiple state machines, where a simple reuse of an event name from one machine to the other can have very weird, hard to debug consequences.

[Multisync]

@ack: Unfortunately I don't yet understand, could you elaborate which benefit using typedef would have? How would errors be catched that wouldn't be catched otherwise?

[ack]

@Multisync: A correction on my part: rather than typedef you may wish to consider using structs with enums, see stackoverflow.com/q/8597426/588561 for explanation. Using struct A_state { enum A_state st; }; struct B_state { enum B_state st; } etc. helps when dealing with multiple state machines in the same application, This prevents you from accidentally mixing events of one state machine with those of another, because the structs are of different, incompatible type. Of course you can store other state variables related to a machine in the corresponding struct, too.