Basic explaination of a state machine

A Simple State Machine

To demonstrate the core functionality of the State Machine library, let's look at a small example: A state machine with three states, S_1, S_2 and S_3. The state machine is controlled by a single event (event_1); when the event occures, the machine transitions to another state. Initially, the state machine is in state S_1. The statechart for this machine is as follows:

State Machine 1

The following snippet shows the code needed to create such a state machine:

First, we create the state machine and states:

     int event_1 = 0;
     StateMachine *stateMachine = allocStateMachine(NULL, NULL);
     State *S_1 = allocateState(stateMachine, NULL, stateMachine);
     State *S_2 = allocateState(stateMachine, NULL, stateMachine);
     State *S_3 = allocateState(stateMachine, NULL, stateMachine);

Note:: Don't care about NULL pointers you can see, they are only usefull for debug and we will see that later.

Then, we create the transitions by using the addTransition function:
```
     addTransition(S_1, S_2, event_1, 0);
     addTransition(S_2, S_3, event_1, 0);
     addTransition(S_3, S_1, event_1, 0);
```
Note:
You can test if the transition has really been done by testing the return value.
The last parameter of this function will be explained later.
Next, we set the machine's initial state:
```
     makeDefault(S_1);
```
Note:
There is always a default node even if you do not precise which one should be the default. The first node that have been created is the default one. In other terms, here, S_1 was already the default state for the state machine but it's better to precise it.
Finally, we start the state machine:
```
     startStateMachine(stateMachine);
```

Now we are done. The state machine is ready to work and you can send event to it using the following function.

    sendEvent(stateMachine, 1);

Doing Useful Work on State Entry and Exit.

The above state machine merely transitions from one state to another, it doesn't perform any operations. The setEntryWork and setExitWork functions can be used to have a state set a funtion to execute when the state is entered or exited. The funtion that can be assigned must be typed as void myFuntion(void) for example:

    //Function that should be executed when S_1 is entered
    void S1Entered()
    {
        printf("S_1 is entered\n");
    }
    //Function that should be executed when S_2 is exited
    void S2Exited()
    {
        printf("S_2 is exited\n");
    }
    //Function that should be executed when S_3 is entered
    void S3Entered()
    {
        printf("S_3 is entered\n");
    }

Now lets assign the functions to the states:

    setEntryWork(S_1, &S1Entered);
    setExitWork(S_2, &S2Exited);
    setEntryWork(S_3, &S3Entered);

Sharing Transitions By Grouping States.

Assume we wanted the user to be able to quit the application at any time by sending event_2. In order to achieve this, we need to create another state that will be considered as the final state and make it the target of a transition associated with the event_2. We could add a transition from each of S_1, S_2 and S_3; however, this seems redundant, and one would also have to remember to add such a transition from every new state that is added in the future.

We can achieve the same behavior (namely that sending event_2 quits the state machine, regardless of which state the state machine is in) by grouping states S_1, S_2 and S_3. This is done by creating a new top-level state and making the three original states children of the new state. The following diagram shows the new state machine.

State Machine 2

The three original states have been renamed S_1_1, S_1_2 and S_1_3 to reflect that they are now children of the new top-level state, MS_1. Child states implicitly inherit the transitions of their parent state. This means it is now sufficient to add a single transition from MS_1 to the final state S_2. New states added to MS_1 will also automatically inherit this transition.

Note:: MS stand for Meta State.

All that's needed to group states is to specify the proper parent when the states are created. You also need to specify which of the child states is the initial one (i.e. which child state the state machine should enter when the parent state is the target of a transition). One more time, if you don't precise which state should be the default, the state machine will choose the first created.

    int event_1 = 0;
    int event_2 = 1;
    StateMachine *stateMachine = allocStateMachine(NULL, NULL);
    State *MS_1 = allocateState(stateMachine, NULL, stateMachine);
    State *S_2 = allocateState(stateMachine, NULL, stateMachine);
    State *S_1_1 = allocateState(MS_1, NULL, stateMachine);
    State *S_1_2 = allocateState(MS_1, NULL, stateMachine);
    State *S_1_3 = allocateState(MS_1, NULL, stateMachine);
    makeDefault(MS_1);
    makeDefault(S_1_1);
    addTransition(S_1_1, S_1_2, event_1, 0);
    addTransition(S_1_2, S_1_3, event_1, 0);
    addTransition(S_1_3, S_1_1, event_1, 0);
    addTransition(MS_1, S_2, event_2, 0);

At this time you just have to set a funtion to be executed when S_2 is entered to make the state machine end.

Using History States to Save and Restore the Current State

Imagine that we wanted to add an "interrupt" mechanism to the example discussed in the previous section; the user should be able to send an event to have the state machine perform some non-related task, after which the state machine should resume whatever it was doing before (i.e. return to the old state, which is one of S_1_1, S_1_2 and S_1_3 in this case).

Such behavior can easily be modeled using history states. A history state is a property that can be attached to a state and save the child state that the parent state was in the last time the parent state was exited.

A transition to the history state of a state is in fact a transition to the child state that the state machine had previously saved; the state machine automatically "forwards" the transition to the real child state.

The following diagram shows the state machine after the interrupt mechanism has been added.

State Machine 3

    int event_3 = 2;
    State *S_3 = allocateState(stateMachine, NULL, stateMachine);
    addTransition(MS_1, S_3, event_3, 0);
    addTransition(S_3, MS_1, event_3, 1);

You can notice that this time we have used 1 as the last parameter for the transition from S_3 to MS_1 indicating that thes real target is not MS_1 but its history state. Doing so automatically activate the history property of the state MS_1. Another way to do this is to target MS_1 and to tell MS_1 to always use its history child as default state. There IS a difference, this way history state will be used even when MS_1 is enetered the first time when the state machine start. Imagine that MS_1 is itself a child state of another state, when the parent state enter MS_1, once again, the history state will be used.

    int event_3 = 2;
    State *S_3 = allocateState(stateMachine, NULL, stateMachine);
    makeHistoryStateDefault(MS_1, S_1_1);
    addTransition(MS_1, S_3, event_3, 0);
    addTransition(S_3, MS_1, event_3, 0);

How to free ressources.

The only real way to free ressources is to call the approptiate function with a pointer on the state machine to free. This will take care of any allocated ressources for the state machine meaning that after this call any pointer on a state or an history state that belongs to the state machine is not valid any more.

    freeStateMachine(stateMachine);

Conclusion.

To conclude here is a full code corresponding to the last state chart "State Machine 3"

#include <stdio.h>
#include <unistd.h>
#include "StateMachine.h"
int main(int argc, char** argv)
{
    int i;
    int event_1 = 0;
    int event_2 = 1;
    int event_3 = 2;
    StateMachine *stateMachine = allocStateMachine("SM", "[SM]");
    State *MS_1 = allocateState(stateMachine, "MS_1", stateMachine);
    State *S_2 = allocateState(stateMachine, "S_2", stateMachine);
    State *S_3 = allocateState(stateMachine, "S_3", stateMachine);
    State *S_1_1 = allocateState(MS_1, "S_1_1", stateMachine);
    State *S_1_2 = allocateState(MS_1, "S_1_2", stateMachine);
    State *S_1_3 = allocateState(MS_1, "S_1_3", stateMachine);
    makeDefault(MS_1);
    makeDefault(S_1_1);
    addTransition(S_1_1, S_1_2, event_1, 0);
    addTransition(S_1_2, S_1_3, event_1, 0);
    addTransition(S_1_3, S_1_1, event_1, 0);
    addTransition(MS_1, S_2, event_2, 0);
    addTransition(MS_1, S_3, event_3, 0);
    addTransition(S_3, HS_1, event_3, 1);
    setDbgParam(stateMachine, STATE_WORK_DBG);
    startStateMachine(stateMachine);
    
    do
    {
        printf("[Test program] Next event : ");
        scanf("%d", &i);
        sendEvent(stateMachine, i);
    }while(i >= 0 && i <= 2);
    
    freeStateMachine(stateMachine);
    return 0;
}

Next: Using Parallel States to Avoid a Combinatorial Explosion of States

Previous: mainpage