A state machine is a way of structuring a program to structure it around a set of states and the events that can cause it to change state.

This can be useful in sufficiently small programs as it allows you to reason about all your inputs and all your states such that you can verify that you have accounted for every eventuality.

This can be handy when writing C programs that aren't just a single thread calling blocking system calls as the gods of UNIX intended.

This article will discuss a couple of ways of writing state machines using a necessarily trivial example.

A good start is to enumerate the set of states your program may be in, and the set of events that your program accepts.

enum states {
    START,
    LOOP,
    END,
} state;

enum events {
    START_LOOPING,
    PRINT_HELLO,
    STOP_LOOPING,
};

This program has the states START, LOOP and END, and accepts the events START_LOOPING, PRINT_HELLO and STOP_LOOPING.

Our program will enter the LOOP state after the START_LOOPING event while in START state, print hello when it gets the PRINT_HELLO event in the LOOP state, and enter the END state after getting a STOP_LOOPING event.

We are going to drive this state machine by repeatedly passing it our events, though for a real program you are more likely to have an event loop.

int main(void) {
    step_state(START_LOOPING);
    step_state(PRINT_HELLO);
    step_state(PRINT_HELLO);
    step_state(STOP_LOOPING);
    return 0;
}

Now there are a couple of ways of doing the state machine handling.

Handling states with case statements

If you're familiar with C, you may find it obvious to use nested switch statements.

That would look something like this:

void step_state(enum events event) {
    switch(state) {
    case START:
        switch(event) {
        case START_LOOPING:
            state = LOOP;
            break;
        default:
            exit(1);
            break;
        }       
        break;
    case LOOP:
        switch(event) {
        case PRINT_HELLO:
            printf("Hello World!\n");
            break;
        case STOP_LOOPING:
            state = END;
            break;
        default:
            exit(1);
            break;
        }
        break;
    case END:
        exit(1);
        break;
    }
}

This defines cases to jump into the code that handles each state and event.

This can be a bit verbose, and produce long functions, especially if you have a lot of events to handle.

Conveniently if you are using gcc, you can use the -Werror=switch compiler flag to make it refuse to compile the code if you forgot to handle every state and event.

Example code of doing it this way can be found at switch.c.

Handling states with a table

This approach has a table of event handlers, that return the subsequent state, so the step_state() function can look up the handler based on the current state and the event.

This requires defining a function for each event handler and then creating the table of function pointers, which can seem a little verbose, but is good for state machines where there is a small fraction of valid state and event combinations, and can be considered to be good style anyway.

It looks something like this:

typedef enum states (*event_handler)(enum states, enum events);

enum states start_looping(enum states state, enum events event) {
    return LOOP;
}

enum states print_hello(enum states state, enum events event) {
    printf("Hello World!\n");
    return LOOP;
}

enum states stop_looping(enum states state, enum events event) {
    return END;
}

event_handler transitions[STOP_LOOPING+1][END+1] = {
    [START] = { [START_LOOPING] = start_looping, },
    [LOOP] = { [PRINT_HELLO] = print_hello,
               [STOP_LOOPING] = stop_looping, },
};

void step_state(enum events event) {
    event_handler handler = transitions[event][state];
    if (!handler)
        exit(1);
    state = handler(state, event);
}

This typedefs the function pointer type for convenience, since the function pointer syntax is arcane and gnarly, and not something you want to combine with the array syntax.

This example uses the GCC designated initializer syntax to make the table more self-documenting, and uses arithmetic on an enum value to determine the size of the table.

This is a 3 by 3 matrix of function pointers, and using the fact that any not explicitly initialised entry is initialised with the NULL pointer we can use that as the marker for invalid combination.

Example code of doing it this way can be found at table.c.