Developing a better state pattern in C

Question

I have created a state diagram to show the different transitions and states. I could not find many examples of the state pattern in C, so I have taken an example from a Java state pattern and tried to convert it to C.

Is there a way to create the state pattern in C? I'd like some tips or tricks in doing this better using the state pattern.

This is compiled under gcc (GCC) 4.7.2.

watch_state.h (interface)

#ifndef WATCH_STATE_H_INCLUDED
#define WATCH_STATE_H_INCLUDED

/* An incomplete type for the state representation itself */
typedef struct tag_watch_state watch_state_t;

/* Function pointer to the implementation of the interface */
typedef void (*event_start_func_f)(watch_state_t *sw);
typedef void (*event_stop_func_f)(watch_state_t *sw);
typedef void (*event_split_func_f)(watch_state_t *sw);

typedef enum states_tag states_e;
enum states_tag { STOPPED, STARTED, SPLIT };

struct tag_watch_state {
    /* Events */
    event_start_func_f start;
    event_split_func_f split;
    event_stop_func_f stop;

    /* States */
    states_e current_state;

    int time;
};

void initialize(watch_state_t *state);
char* state_to_string(states_e state);

#endif /* WATCH_STATE_H_INCLUDED */

watch_state.c (implementation of interface)

#include <stdio.h>
#include "watch_state.h"
#include "started_state.h"
#include "stopped_state.h"
#include "split_state.h"

static void default_start(watch_state_t *state);
static void default_split(watch_state_t *state);
static void default_stop(watch_state_t *state);

void initialize(watch_state_t *state)
{
    state->start = default_start;
    state->split = default_split;
    state->stop = default_stop;
    state->current_state = STOPPED;
    state->time = 0;
}

char* state_to_string(states_e state)
{
    switch(state) {
    case STOPPED:
        return "STOPPED";

    case STARTED:
        return "STARTED";

    case SPLIT:
        return "SPLIT";

    default:
        return "UNKNOWN";
    }
}

static void default_start(watch_state_t *state)
{
    printf("[ %s ] State [ %s ] time [ %d ] start event isn't supported in the concrete state\n",
           __func__, state_to_string(state->current_state), state->time);
}

static void default_split(watch_state_t *state)
{
    printf("[ %s ] State [ %s ] time [ %d ] split event isn't supported in the concrete state\n",
           __func__, state_to_string(state->current_state), state->time);
}

static void default_stop(watch_state_t *state)
{
    printf("[ %s ] State [ %s ] time [ %d ] stop event isn't supported in the concrete state\n",
           __func__, state_to_string(state->current_state), state->time);
}

started_state.h

#ifndef STARTED_STATE_H_INCLUDED
#define STARTED_STATE_H_INCLUDED

#include "watch_state.h"

void start(watch_state_t *state);

#endif /* STARTED_STATE_H_INCLUDED */

started_state.c

#include <stdio.h>
#include <string.h>
#include <unistd.h>

#include "started_state.h"
#include "stopped_state.h"
#include "split_state.h"

void start(watch_state_t *state)
{
    unsigned int secs = 5;
    unsigned int i = 0;

    /* Do some work here to simulate stop*/
    for(i = 0; i < secs; i++) {    
        sleep(1);
        printf("Starting the stopwatch ...%u\n", i);
    }

    /* Initialize with default implementation */
    initialize(state);

    /* Update state */
    state->current_state = STARTED;
    state->time = 0;

    /* Next transition states */
    state->stop = stop;
    state->split = split;

    printf("[ %s ] state [ %s ] time [ %d ]\n", __func__, state_to_string(state->current_state), state->time);
}

stopped_state.h

#ifndef STOPPED_STATE_H_INCLUDED
#define STOPPED_STATE_H_INCLUDED

#include "watch_state.h"

void stop(watch_state_t *state);
void start(watch_state_t *state);
void split(watch_state_t *state);

#endif /* STOPPED_STATE_H_INCLUDED */

stopped_state.c

#include <stdio.h>
#include <string.h>
#include <unistd.h>

#include "stopped_state.h"
#include "started_state.h"

void stop(watch_state_t *state)
{
    unsigned int secs = 3;
    unsigned int i = 0;

    /* Do some work here to stop*/
    for(i = 0; i < secs; i++) {    
        sleep(1);
        printf("Stopping the stopwatch ...%u\n", i);
    }

    /* Initialize with default implementation */
    initialize(state);

    /* update current state */
    state->current_state = STOPPED;
    state->time = 0;

    /* Next transition state */
    state->start = start;

    printf("[ %s ] state [ %s ] time [ %d ]\n", __func__, state_to_string(state->current_state), state->time);
}

split_state.h

#ifndef SPLIT_STATE_H_INCLUDED
#define SPLIT_STATE_H_INCLUDED

#include "watch_state.h"

void split(watch_state_t *state);

#endif /* SPLIT_STATE_H_INCLUDED */

split_state.c

#include <stdio.h>
#include <string.h>
#include <unistd.h>

#include "split_state.h"
#include "stopped_state.h"

void split(watch_state_t *state)
{
    unsigned int secs = 5;
    unsigned int i = 0;

    /* Do some work here to stop*/
    for(i = 0; i < secs; i++) {    
        sleep(1);
        printf("Splitting the stopwatch ...%u\n", i);
    }

    /* Initialize with default implementation */
    initialize(state);

    state->current_state = SPLIT;
    state->time = secs;

    /* Next transition states */
    state->stop = stop;
    state->split = split;

    printf("[ %s ] state [ %s ] time [ %d ]\n", __func__, state_to_string(state->current_state), state->time);
}

For context, I have this for testing the states:

client_sw.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "watch_state.h"
#include "started_state.h"

typedef struct tag_client_sw client_sw_t;
struct tag_client_sw {
    watch_state_t state;
};

client_sw_t* sw_create(void)
{
    client_sw_t *sw = malloc(sizeof *sw);

    memset(sw, 0, sizeof *sw);

    initialize(&sw->state);

    /* Next transition */
    sw->state.start = start;

    return sw;
}

void sw_destroy(client_sw_t *sw)
{
    free(sw);
}

void start_watch(client_sw_t *sw)
{
    sw->state.start(&sw->state);
}

void stop_watch(client_sw_t *sw)
{
    sw->state.stop(&sw->state);
}

void split_watch(client_sw_t *sw)
{
    sw->state.split(&sw->state);
}

int main(void)
{
    client_sw_t *sw = NULL;

    printf("Start your stop watch, extended version\n");

    sw = sw_create();

    stop_watch(sw);
    stop_watch(sw);
    split_watch(sw);

    start_watch(sw);
    start_watch(sw);

    split_watch(sw);
    split_watch(sw);

    stop_watch(sw);

    split_watch(sw);
    start_watch(sw);
    stop_watch(sw);

    sw_destroy(sw);

    printf("Terminate your stop watch\n");

    return 0;
}

Answer 1

Looking at the State Pattern on Wikipedia I'd say it's more normal to replace the entire function table at once, rather than write individual function pointers.

To this end, I would do this:

struct watch_state {
    event_start_func_f start;
    event_split_func_f split;
    event_stop_func_f stop;

    const char *name;
};

struct watch_state started  = {default_start, split, stop, "Started"};
struct watch_state stopped  = {start, split, default_stop, "Stopped"};
struct watch_state splitted = {default_start, split, stop, "Splitted"};

And then this:

struct tag_watch_state {
    /* State */
    struct watch_state *state;

    int time;
};

And implement your state switches like this:

static void start(watch_state_t *state)
{
    unsigned int secs = 5;
    unsigned int i = 0;

    /* Do some work here to simulate stop*/
    for(i = 0; i < secs; i++) {    
        sleep(1);
        printf("Starting the stopwatch ...%u\n", i);
    }

    /* Update state */
    state->state = &started;
    state->time = 0;

    printf("[ %s ] state [ %s ] time [ %d ]\n", __func__, state->name, state->time);
}

You can then delete initialize and state_to_string (but make sure you set your initial state in the watch constructor).

Finally, and this is just advice for C code in general, I would consolidate all the functions that really form one module into one .c file, define the private types inside that, and only expose the public facing types, perhaps as abstract structs, in a corresponding header.

In this case I would expect you to have client_sw.c, sw.c and sw.h that exports only the constructor, sw_create, the methods stop_watch, start_watch, and split_watch (each of which I would rename according to the sw_* theme), and the destructor sw_destroy. You would also need to expose the abstract type struct tag_watch_state, but not the internal definition.

My header would look like:

// sw.h

typedef struct tag_watch_state sw;

sw *sw_create();
void sw_start(sw *);
void sw_split(sw *);
void sw_stop(sw *);
void sw_destroy(sw *);

However, if you have a big program, with a lot of states, each requiring a non-trivial amount of code, it would make sense to have one .c file for each state. Even then though, I would endeavour to present only one abstract header to the external callers.

Answer 2

Here are some observations that may help you improve your code. This list starts with some of the picky details and then moves to more substantive issues.

Turn on all compiler warnings

Your compiler can provide a useful opinion on the quality of your code, especially if you turn on all of the warnings. When I compile your code using gcc, it says:

watch_state.h:12:14: warning: ISO C forbids forward references to ‘enum’ types [-Wpedantic]

What it's complaining about is that the typedef is ahead of the enum states_tag. Simply swapping those two lines fixes the error.

Use const where practical

The state_to_string() routine returns a char * which points to a constant string. It should therefore have this function prototype:

const char* state_to_string(states_e state)

Omit return 0 from the end of main

When a C (or C++) program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.

Use calloc instead of malloc and memset

The current code contains this:

client_sw_t *sw = malloc(sizeof *sw);
memset(sw, 0, sizeof *sw);

However, that could be more simply written as:

client_sw_t *sw = calloc(1, sizeof *sw);

Don't double-initialize objects

Contrary to the previous point, the better solution for that particular case would instead be to omit memset because the initialize() initializes all members of the struct. For that reason, there is no reason to write to that memory space before calling initialize.
Along the same lines, the stop() routine calls initialize but then explicitly sets several of the state members to the exact same values that were just set in initialize.

Combine typedef and struct declaration

The code currently contains these lines:

typedef struct tag_client_sw client_sw_t;
struct tag_client_sw {
    watch_state_t state;
};

There's technically nothing wrong with that construction but a more idiomatic way to express that would be to combine them:

typedef struct tag_client_sw {
    watch_state_t state;
} client_sw_t;

Better still, see the next suggestion.

Avoid pointless wrappers

The way the client_sw_t structure is created, it's just a wrapper around a watch_state_t type and nothing more. This makes the syntax more complex with no real benefit. I'd recommend simply using a watch_state_t and further, creating it on the stack as an automatic variable rather than allocating it on the heap with malloc.

Avoid defining type names ending with _t

Types ending with _t are reserved for use by POSIX, so for portability, you should avoid defining your own types that end with _t.

Clearly differentiate between states and events

There is a good representation of states in the code, but it's not as explicit for the events. I would recommend creating an enum and a set of names for the events.

typedef enum events_tag { STOP, START, SPLIT, EVENTS_COUNT } events_e;

Note that this also defines EVENTS_COUNT which will automatically be set to the number of events. This is handy to be able to write code like this:

static const char *events_name[] = { "STOP", "START", "SPLIT", "UNKNOWN" };
static const char* event_to_string(events_e event)
{
    return (event < EVENTS_COUNT) ? events_name[event] : events_name[EVENTS_COUNT];
}

Don't Repeat Yourself (DRY)

There three functions default_start, default_split and default_stop are really all error handlers and are nearly identical. Replace all three with a better named function:

static void sm_error(watch_state_t *state, events_e evt)
{
    printf("[time: %d]: event %s is not allowed in state %s\n", 
       state->time, 
       event_to_string(evt),
       state_to_string(state->current_state) 
    );
}

Avoid messy linkage among headers

A user of this state machine should only have to #include "watch_state.h" and not other files. Further, if each state needs to know about the other ones, there's not much point in making them separate files in the first place. In this case, it would make more sense to have just a single watch_state.h header and all of the required functions in watch_state.c.

Drive a state machine via data, not code

Generally speaking, a state machine can be implemented in C (or most other languages) via a set of generic functions that operate on a data structure representing the state transitions. If you find yourself writing code to handle the state transitions, question whether it's really necessary. With all state machines there are states and allowed transitions. There are also often actions (code) associated with either the states or the transitions or both. For a robust design, I like to make sure that all possible combinations of states and transitions are enumerated, even the ones that are "illegal". Here is the generic code to handle an event:

void handle_event(watch_state_s *state, events_e evt)
{
    if (evt >= EVENTS_COUNT || state->current_state >= STATES_COUNT) {
        sm_error(state, evt);
    }
    sm[state->current_state].action[evt](state, evt);
}

The sm_error() function and sm structure are defined like this:

static void sm_error(watch_state_s *state, events_e evt)
{
    printf("[time: %d]: event %s is not allowed in state %s\n", 
       state->time, 
       event_to_string(evt),
       state_to_string(state->current_state) 
    );
}

static state_s sm[] = {
    // state      ->STOP    ->START   ->SPLIT  
    { STOPPED,  { sm_error, sm_start, sm_error }},
    { STARTED,  { sm_stop,  sm_error, sm_split }},
    { SPLITTED, { sm_stop,  sm_error, sm_error }}
};

The state_s type is this:

typedef void (*action_fn)(watch_state_s *state, events_e evt);

typedef struct state {
    states_e tag;
    action_fn action[EVENTS_COUNT];
} state_s;

Here's how I translated your existing start routine into sm_start:

static void sm_start(watch_state_s *state, events_e evt)
{
    const unsigned int secs = 5;

    /* Do some work here to simulate stop*/
    for(unsigned i = 0; i < secs; i++) {    
        sleep(1);
        printf("Starting the stopwatch ...%u\n", i);
    }

    /* Update state */
    state->current_state = STARTED;
    state->time = 0;

    printf("[time: %d]: event %s moved us to state %s\n", 
        state->time, 
        event_to_string(evt),
        state_to_string(state->current_state)
    );
}

Finally, here's the translation of main():

int main(void)
{
    watch_state_s sw;

    printf("Start your stop watch, extended version\n");
    initialize(&sw);

    handle_event(&sw, STOP);
    handle_event(&sw, STOP);
    handle_event(&sw, SPLIT);

    handle_event(&sw, START);
    handle_event(&sw, START);

    handle_event(&sw, SPLIT);
    handle_event(&sw, SPLIT);

    handle_event(&sw, STOP);

    handle_event(&sw, SPLIT);
    handle_event(&sw, START);
    handle_event(&sw, STOP);

    printf("Terminate your stop watch\n");
}

It should be easy to see how to fill in the missing pieces.