Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

State machines in C

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?

like image 804
Maurizio Reginelli Avatar asked Feb 16 '10 06:02

Maurizio Reginelli


People also ask

What is state machine with example?

It consists of a finite number of states and is therefore also called finite-state machine (FSM). Based on the current state and a given input the machine performs state transitions and produces outputs. There are basic types like Mealy and Moore machines and more complex types like Harel and UML statecharts.

What is meant by a state machine?

A state machine is a mathematical abstraction used to design algorithms. A state machine reads a set of inputs and changes to a different state based on those inputs. A state is a description of the status of a system waiting to execute a transition.

Why state machines are used?

State machines are useful if you can define a clear number of states and events that will trigger transitions to them. They might be good for user interfaces or communications protocols. However, when building complex systems, implementation of state machines is not the best option.

What is meant by state machine model?

A state machine model is a mathematical model that groups all possible system occurrences, called states. Every possible state of a system is evaluated, showing all possible interactions between subjects and objects. If every state is proven to be secure, the system is proven to be secure.


2 Answers

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.

like image 76
squelart Avatar answered Oct 12 '22 15:10

squelart


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.

like image 22
bobbymcr Avatar answered Oct 12 '22 17:10

bobbymcr