Coffee Space


C State Machines

Preview Image

I recently read an article by Stephen Friederichs on Implementing State Machines, from all the way back in 2014 (which feels like yesterday at the time of writing). It’s a great read and I suggest for people to go and read it. I have kept with his state machine model as best I could, so please see the below image I copied from the site:

Image source:

This got me thinking about my preferred design for state machine, which is to use transition functions. Conceptually I think the idea is quite clean, as the decision for each transaction is abstracted away into their own functions. Better yet, somebody can’t sneak a goto or continue, so the order of operations is always clean.

I would also argue that runtime speed is also greatly improved for larger state machines, as we don’t have to check each case in a switch statement, but instead simply go straight to desired function.

The following is a breakdown of my alternative code…


0001 /* gcc -Wall -std=c99 state.c -o state */
0003 #include <stdio.h> // Only for debugging
0005 typedef enum{
0006   INIT = 0,
0007   GET_DISH,
0008   SCRUB,
0009   RINSE,
0010   DRY,
0011   CLEANUP,
0012   END
0013 } t_state_machine;
0014 #define t_state_machine_len (END - INIT + 1)

The define statement is a neat trick to calculate the length of the enumerator at compile time, so that it can also be used to define the length of an array.

0015 typedef t_state_machine (*trans)(void);
0017 trans transitions[t_state_machine_len];

This is where we will store our transition variables. This will be incredibly quick to look-up as you’ll see.

0018 t_state_machine state_init(void){
0019   // get_towels();
0020   // full_sink();
0021   // stack_dishes();
0022   return GET_DISH;
0023 }
0025 t_state_machine state_get_dish(void){
0026   // dish = pick_up_dish();
0027   // if(!dish)
0028   //   return CLEANUP;
0029   // else
0030   return SCRUB;
0031 }
0033 t_state_machine state_scrub(void){
0034   // if(*dish == DIRTY)
0035   //   scrub(&dish);
0036   // else
0037   return RINSE;
0038 }
0040 t_state_machine state_rinse(void){
0041   // if(*dish == SOAPY)
0042   //   rinse(&dish);
0043   // else
0044   return DRY;
0045 }
0047 t_state_machine state_dry(void){
0048   // if(*dish == WET)
0049   //   dry(&dish);
0050   // else
0051   //   put_away_dish(&dish);
0052   return GET_DISH;
0053 }
0055 t_state_machine state_cleanup(void){
0056   /* Do some clean-up. */
0057   return END;
0058 }
0060 t_state_machine state_end(void){
0061   /* NOTE: If we ever run this, we transitioned in from an error. */
0062   return END;
0063 }

There we just defined all the transition code, each nicely abstracted away into their own little functions. I believe this code would scale quite nicely as each block would only be responsible for their exit transitions.

0064 t_state_machine service(t_state_machine state){
0065   if(state < INIT || state >= END) state = END;
0066   /* We could check for bathroom break here */
0067   return transitions[state]();
0068 }

service() is a small abstraction that allows us to check for anything abnormal. In this case we check whether state enters into an invalid value and transition straight into END. Here you could have some ‘watchdog’ for example to see whether a state has failed to transition out after some time, or transitions into an invalid state give the previous state.

The real clever thing here though is that the current state is used to immediately jump to the correct piece of code to run that state. In the switch statement in the original article you potentially introduce tonnes of branching, which is quite bad for performance on modern CPUs. For embedded systems, you still pay heavily for all these additional comparisons that need to be performed, especially if you had for example many more possible states.

0069 int main(){
0070   /* Setup */
0071   transitions[INIT] = state_init;
0072   transitions[GET_DISH] = state_get_dish;
0073   transitions[SCRUB] = state_scrub;
0074   transitions[RINSE] = state_rinse;
0075   transitions[DRY] = state_dry;
0076   transitions[CLEANUP] = state_cleanup;
0077   transitions[END] = state_end;
0078   t_state_machine state = INIT;
0079   /* Run */
0080   while(state != END){
0081     printf("state %i", state - INIT); // Debugging only
0082     state = service(state);
0083     printf(" -> state %i\n", state - INIT); // Debugging only
0084   }
0085   return 0;
0086 }

Here we setup the relevant transition states, which could even be done at compile time if we were so inclined to do so. Running the state machine is then very trivial, we just set an entry and exit condition, and loop as required.


I’m not aware of any, but for embedded systems (which the article relates to) there may be arguments against using pointers. For example, the function pointers would be stored in variable space rather than program space, meaning that it could be possible for rogue code to override the function offsets and cause some crazy behaviour. That said, if you’ve got rogue code, it may be the least of your worries.