Is there a typical state machine implementation pattern

Question

We need to implement a simple state machine in C  Is a standard switch statement the best way to go  We have a current state  state  and a trigger for the transition    switch state      case STATE 1       state   DoState1 transition        break    case STATE 2       state   DoState2 transition        break        DoState2 int transition          Do State Work           if transition    FROM STATE 2            New state when doing STATE 2 -  STATE 2         if transition    FROM STATE 1           New State when moving STATE 1 -  STATE 2         return new state      Is there a better way for simple state machines  EDIT    For C    I think the Boost Statechart library might be the way to go   However  it does not help with C   Lets concentrate on the C use case

User · Answer

For a simple state machine just use a switch statement and an enum type for your state  Do your transitions inside the switch statement based on your input  In a real program you would obviously change the  if input   to check for your transition points   Hope this helps   typedef enum       STATE 1   0      STATE 2      STATE 3   my state t   my state t state   STATE 1   void foo char input                switch state                case STATE 1              if input                  state   STATE 2              break          case STATE 2              if input                  state   STATE 3              else                 state   STATE 1              break          case STATE 3                              break

User · Answer

You can use minimalist UML state machine framework in c  https   github com kiishor UML-State-Machine-in-C  It supports both finite and hierarchical state machine  It has only 3 API s  2 structures and 1 enumeration   The State machine is represented by state machine t structure  It is an abstract structure that can be inherited to create a state machine       Abstract state machine structure struct state machine t      uint32 t Event               lt  Pending Event for state machine    const state t  State         lt  State of state machine       State is represented by pointer to state t structure in the framework   If framework is configured for finite state machine then state t contains   typedef struct finite state t state t      finite state structure typedef struct finite state t    state handler Handler             lt  State handler function  function pointer    state handler Entry               lt  Entry action for state  function pointer    state handler Exit                lt  Exit action for state  function pointer   finite state t    The framework provides an API dispatch event to dispatch the event to the state machine and two API s for the state traversal   state machine result t dispatch event state machine t  const pState Machine    uint32 t quantity     state machine result t switch state state machine t  const  const state t     state machine result t traverse state state machine t  const  const state t      For further details on how to implement hierarchical state machine refer the GitHub repository   code examples https   github com kiishor UML-State-Machine-in-C blob master demo simple state machine readme md https   github com kiishor UML-State-Machine-in-C blob master demo simple state machine enhanced readme md

User · Answer

Your question is similar to  is there a typical Data Base implementation pattern   The answer depends upon what do you want to achieve  If you want to implement a larger deterministic state machine you may use a model and a state machine generator  Examples can be viewed at www StateSoft org - SM Gallery  Janusz Dobrowolski

User · Answer

I found a really slick C implementation of Moore FSM on the edx org course Embedded Systems - Shape the World UTAustinX -  UT 6 02x  chapter 10  by Jonathan Valvano and Ramesh Yerraballi      struct State     unsigned long Out      6-bit pattern to output   unsigned long Time     delay in 10ms units    unsigned long Next 4      next state for inputs 0 1 2 3      typedef const struct State STyp     this example has 4 states  defining constants symbols using  define  define goN   0  define waitN 1  define goE   2  define waitE 3     this is the full FSM logic coded into one large array of output values  delays     and next states  indexed by values of the inputs  STyp FSM 4      0x21 3000  goN waitN goN waitN       0x22  500  goE goE goE goE      0x0C 3000  goE goE waitE waitE      0x14  500  goN goN goN goN     unsigned long currentState      index to the current state     super simple controller follows int main void   volatile unsigned long delay    embedded micro-controller configuration omitteed         currentState   goN      while 1       LIGHTS   FSM currentState  Out      set outputs lines  from FSM table      SysTick Wait10ms FSM currentState  Time       currentState   FSM currentState  Next INPUT SENSORS

User · Answer

For simple cases  you can you your switch style method   What I have found that works well in the past is to deal with transitions too   static int current state        should always hold current state -- and probably be an enum or something  void state leave int new state           do processing on what it means to enter the new state        which might be dependent on the current state    void state enter int new state           do processing on what is means to leave the current atate        might be dependent on the new state      current state   new state     void state process            switch statement to handle current state     I don t know anything about the boost library  but this type of approach is dead simple  doesn t require any external dependencies  and is easy to implement

User · Answer

there is also the logic grid which is more maintainable as the state machine gets bigger

User · Answer

In my experience using the  switch  statement is the standard way to handle multiple possible states  Although I am surpirsed that you are passing in a transition value to the per-state processing  I thought the whole point of a state machine was that each state performed a single action  Then the next action input determines which new state to transition into  So I would have expected each state processing function to immediately perform whatever is fixed for entering state and then afterwards decide if transition is needed to another state

User · Answer

switch   is a powerful and standard way of implementing state machines in C  but it can decrease maintainability down if you have a large number of states  Another common method is to use function pointers to store the next state  This simple example implements a set reset flip-flop      Implement each state as a function with the same prototype    void state one int set  int reset   void state two int set  int reset       Store a pointer to the next state    void   next state  int set  int reset    state one      Users should call next state set  reset   This could    also be wrapped by a real function that validated input    and dealt with output rather than calling the function    pointer directly         State one transitions to state one if set is true    void state one int set  int reset        if set          next state   state two        State two transitions to state one if reset is true    void state two int set  int reset        if reset          next state   state one

User · Answer

This article is a good one for the state pattern  though it is C    not specifically C    If you can put your hands on the book  Head First Design Patterns   the explanation and example are very clear

User · Answer

You might want to look into the libero FSM generator software   From a state description language and or a  windows  state diagram editor you may generate code for C  C    java and many others     plus nice documentation and diagrams  Source and binaries from iMatix

User · Answer

I prefer to use a table driven approach for most state machines   typedef enum   STATE INITIAL  STATE FOO  STATE BAR  NUM STATES   state t  typedef struct instance data instance data t  typedef state t state func t  instance data t  data     state t do state initial  instance data t  data    state t do state foo  instance data t  data    state t do state bar  instance data t  data     state func t  const state table  NUM STATES           do state initial  do state foo  do state bar     state t run state  state t cur state  instance data t  data         return state table  cur state    data        int main  void         state t cur state   STATE INITIAL      instance data t data       while   1             cur state   run state  cur state   amp data                do other program logic  run other state machines  etc           This can of course be extended to support multiple state machines  etc  Transition actions can be accommodated as well   typedef void transition func t  instance data t  data     void do initial to foo  instance data t  data    void do foo to bar  instance data t  data    void do bar to initial  instance data t  data    void do bar to foo  instance data t  data    void do bar to bar  instance data t  data     transition func t   const transition table  NUM STATES    NUM STATES             NULL               do initial to foo  NULL          NULL               NULL               do foo to bar          do bar to initial  do bar to foo      do bar to bar       state t run state  state t cur state  instance data t  data         state t new state   state table  cur state    data        transition func t  transition                  transition table  cur state    new state         if   transition             transition  data               return new state       The table driven approach is easier to maintain and extend and simpler to map to state diagrams

User · Answer

In C    consider the State pattern

User · Answer

Boost has the statechart library  http   www boost org doc libs 1 36 0 libs statechart doc index html  I can t speak to the use of it  though  Not used it myself  yet

User · Answer

One of my favourite patterns is the state design pattern  Respond or behave differently to the same given set of inputs  One of the problems with using switch case statements for state machines is that as you create more states  the switch cases becomes harder unwieldy to read maintain  promotes unorganized spaghetti code  and increasingly difficult to change without breaking something   I find using design patterns helps me to organize my data better  which is the whole point of abstraction  Instead of designing your state code around what state you came from  instead structure your code so that it records the state when you enter a new state   That way  you effectively get a record of your previous state   I like  JoshPetit s answer  and have taken his solution one step further  taken straight from the GoF book   stateCtxt h    define STATE  void    typedef enum fsmSignal      eEnter  0     eNormal     eExit  FsmSignalT   typedef struct fsm       FsmSignalT signal        StateT is an enum that you can define any which way you want    StateT currentState   FsmT  extern int STATECTXT Init void      optionally allow client context to set the target state    extern STATECTXT Set StateT  stateID   extern void STATECTXT Handle void  pvEvent     stateCtxt c    include  stateCtxt h   include  statehandlers h   typedef STATE   pfnStateT  FsmSignalT signal  void  pvEvent    static FsmT      fsm  static pfnStateT UsbState    int STATECTXT Init void            UsbState   State1      fsm signal   eEnter         use an enum for better maintainability     fsm currentState    1         UsbState    amp fsm  pvEvent       return 0     static void ChangeState  FsmT  pFsm  pfnStateT targetState            Check to see if the state has changed     if  targetState     NULL                   Call current state s exit event         pFsm- gt signal   eExit          STATE dummyState     UsbState   pFsm  pvEvent               Update the State Machine structure         UsbState   targetState               Call the new state s enter event         pFsm- gt signal   eEnter                      dummyState     UsbState   pFsm  pvEvent            void STATECTXT Handle void  pvEvent        pfnStateT newState       if  UsbState    NULL                 fsm signal   eNormal           newState     UsbState    amp fsm  pvEvent             ChangeState   amp fsm  newState                      void STATECTXT Set StateT  stateID         prevState   UsbState       switch  stateID                   case  1                              ChangeState  State1                break            case  2               ChangeState  State2               break            case  3               ChangeState  State3               break             statehandlers h      define state handlers    extern STATE State1 void   extern STATE State2 void   extern STATE State3 void     statehandlers c    include  stateCtxt h       Define behaviour to given set of inputs    STATE State1 FsmT  fsm  void  pvEvent           STATE nextState         do some state specific behaviours         here                fsm- gt currentState currently contains the previous state        just before it gets updated  so you can implement behaviours         which depend on previous state here             fsm- gt currentState    1          Now  specify the next state        to transition to  or return null if you re still waiting for         more stuff to process                switch  fsm- gt signal                case eEnter              nextState   State2              break          case eNormal              nextState   null              break          case eExit              nextState   State2              break             return nextState     STATE  State3 FsmT  fsm  void  pvEvent           do some state specific behaviours         here             fsm- gt currentState    2          Now  specify the next state        to transition to              return State1     STATE   State2 FsmT  fsm  void  pvEvent              do some state specific behaviours         here             fsm- gt currentState    3          Now  specify the next state        to transition to              return State3      For most State Machines  esp  Finite state machines  each state will know what its next state should be  and the criteria for transitioning to its next state   For loose state designs  this may not be the case  hence the option to expose the API for transitioning states   If you desire more abstraction  each state handler can be separated out into its own file  which are equivalent to the concrete state handlers in the GoF book   If your design is simple with only a few states  then both stateCtxt c and statehandlers c can be combined into a single file for simplicity

User · Answer

For compiler which support   COUNTER     you can use them for simple  but large  state mashines      define START 0          define END 1000    int run   1    state   START        while run          switch  state                case   COUNTER                  do something             state                break          case   COUNTER                  do something             if  input                 state   END              else                state                break                                                    case   COUNTER                  do something             if  input                 state   START              else                state                break          case   COUNTER                  do something             state                break          case END                do something             run   0              state   START              break          default              state                break                 The advantage of using   COUNTER   instead of hard coded numbers is that you can add states in the middle of other states  without renumbering everytime everything   If the compiler doesnt support   COUNTER    in a limited way its posible to use with precaution   LINE

User · Answer

I also have used the table approach   However  there is overhead   Why store a second list of pointers   A function in C without the    is a const pointer   So you can do   struct state  typedef void   state func t   struct state      typedef struct state     state func t function        other stateful data    state t   void do state initial  state t     void do state foo  state t     void do state bar  state t      void run state  state t  i         i- gt function i       int main  void         state t state     do state initial         while   1             run state  state                do other program logic  run other state machines  etc           Of course depending on your fear factor  i e  safety vs speed  you may want to check for valid pointers   For state machines larger than three or so states  the approach above should be less instructions than an equivalent switch or table approach   You could even macro-ize as    define RUN STATE state ptr     state ptr  - gt function state ptr      Also  I feel from the OP s example  that there is a simplification that should be done when thinking about   designing a state machine   I don t thing the transitioning state should be used for logic   Each state function should be able to perform its given role without explicit knowledge of past state s    Basically you design for how to transition from the state you are in to another state   Finally  don t start the design of a state machine based on  functional  boundaries  use sub-functions for that   Instead divide the states based on when you will have to wait for something to happen before you can continue   This will help minimize the number of times you have to run the state machine before you get a result   This can be important when writing I O functions  or interrupt handlers   Also  a few pros and cons of the classic switch statement   Pros    it is in the language  so it is documented and clear states are defined where they are called can execute multiple states in one function call code common to all states can be executed before and after the switch statement   Cons    can execute multiple states in one function call code common to all states can be executed before and after the switch statement switch implementation can be slow   Note the two attributes that are both pro and con   I think the switch allows the opportunity for too much sharing between states  and the interdependency between states can become unmanageable   However for a small number of states  it may be the most readable and maintainable

User · Answer

You might have seen my answer to another C question where I mentioned FSM  Here is how I do it   FSM     STATE x                NEXTSTATE y          STATE y                if  x    0         NEXTSTATE y       else        NEXTSTATE x           With the following macros defined   define FSM  define STATE x       s   x    define NEXTSTATE x   goto s   x   This can be modified to suit the specific case  For example  you may have a file FSMFILE that you want to drive your FSM  so you could incorporate the action of reading next char into the the macro itself    define FSM  define STATE x          s   x   FSMCHR   fgetc FSMFILE   sn   x    define NEXTSTATE x      goto s   x  define NEXTSTATE NR x   goto sn   x   now you have two types of transitions  one goes to a state and read a new character  the other goes to a state without consuming any input   You can also automate the handling of EOF with something like    define STATE x   s   x    if   FSMCHR   fgetc FSMFILE     EOF                                goto sx endfsm                     sn   x     define ENDFSM    sx endfsm    The good thing of this approach is that you can directly translate a state diagram you draw into working code and  conversely  you can easily draw a state diagram from the code   In other techniques for implementing FSM the structure of the transitions is buried in control structures  while  if  switch      and controlled by variables value  tipically a state variable  and it may be a complex task to relate the nice diagram to a convoluted code   I learned this technique from an article appeared on the great  Computer Language  magazine that  unfortunately  is no longer published

User · Answer

In Martin Fowler s UML Distilled  he states  no pun intended  in Chapter 10 State Machine Diagrams  emphasis mine       A state diagram can be implemented in three main ways  nested switch  the State pattern  and   state tables     Let s use a simplified example of the states of a mobile phone s display     Nested switch  Fowler gave an example of C  code  but I ve adapted it to my example   public void HandleEvent PhoneEvent anEvent        switch  CurrentState        case PhoneState ScreenOff          switch  anEvent            case PhoneEvent PressButton              if  powerLow       guard condition                 DisplayLowPowerMessage       action                    CurrentState   PhoneState ScreenOff                else                   CurrentState   PhoneState ScreenOn                            break          case PhoneEvent PlugPower              CurrentState   PhoneState ScreenCharging              break                    break      case PhoneState ScreenOn          switch  anEvent            case PhoneEvent PressButton              CurrentState   PhoneState ScreenOff              break          case PhoneEvent PlugPower              CurrentState   PhoneState ScreenCharging              break                    break      case PhoneState ScreenCharging          switch  anEvent            case PhoneEvent UnplugPower              CurrentState   PhoneState ScreenOff              break                    break            State pattern  Here s an implementation of my example with the GoF State pattern     State Tables  Taking inspiration from Fowler  here s a table for my example    Source State    Target State    Event         Guard        Action -------------------------------------------------------------------------------------- ScreenOff       ScreenOff       pressButton   powerLow     displayLowPowerMessage   ScreenOff       ScreenOn        pressButton    powerLow ScreenOn        ScreenOff       pressButton ScreenOff       ScreenCharging  plugPower ScreenOn        ScreenCharging  plugPower ScreenCharging  ScreenOff       unplugPower   Comparison  Nested switch keeps all the logic in one spot  but the code can be hard to read when there are a lot of states and transitions  It s possibly more secure and easier to validate than the other approaches  no polymorphism or interpreting    The State pattern implementation potentially spreads the logic over several separate classes  which may make understanding it as a whole a problem  On the other hand  the small classes are easy to understand separately  The design is particularly fragile if you change the behavior by adding or removing transitions  as they re methods in the hierarchy and there could be lots of changes to the code  If you live by the design principle of small interfaces  you ll see this pattern doesn t really do so well  However  if the state machine is stable  then such changes won t be needed   The state tables approach requires writing some kind of interpreter for the content  this might be easier if you have reflection in the language you re using   which could be a lot of work to do up front  As Fowler points out  if your table is separate from your code  you could modify the behavior of your software without recompiling  This has some security implications  however  the software is behaving based on the contents of an external file    Edit  not really for C language   There is a fluent interface  aka internal Domain Specific Language  approach  too  which is probably facilitated by languages that have first-class functions  The Stateless library exists and that blog shows a simple example with code  A Java implementation  pre Java8  is discussed  I was shown a Python example on GitHub as well

User · Answer

There is a book titled Practical Statecharts in C C    However  it is way too heavyweight for what we need

[c] Is there a typical state machine implementation pattern?

Examples related to c

Examples related to design-patterns

Examples related to finite-automata