fsm [Theo's Wiki]

Definition

 
/*
 *
 * Very simple template based FSM without any virtualness at all.   Makes single use of
 * a static_cast which i'm not 100% happy with, but speed was the most important thing
 * along with code size (the real implementaion had 18 states and over 100 events).
 *
 * boost:statechart was far, far to complicated (and bloated) to use as a solution for the
 * problem i was tacking, so came up with this instead.
 *
 * Note that this FSM is not in any way re-entrant - there can only be one thread of control
 * in the FSM at any one point.  Not only that, but only one call can be made to process_event()
 * at a time - i.e, you can't call process_event again until is has returned.  this means that any
 * callbacks out of the FSM can not call process_event themselves.  Failure to adhere to these
 * requirements will result in an assert(false) witout NDEBUG defined, and undefined behviour
 * if NDEBUG is defined.
 *
 * I find it easier to visiualise a concerete FSM implementation by handling the actions for
 * states within the event implementation, rather than providing the actions for events within
 * the state implementation.  some may say this is bad design, but i prefer it - sorry :o)
 *
 * Note that i use auto_ptr<T> instead of boost:shared_ptr<T> for this example - you can just
 * as easily use boost::shared_ptr<T> or even a raw pointer.
 *
 * State storage can be accomplished by specialising the state template and adding the storage.
 *
 * If a state is terminated rather then moving to a new state, then the state machine
 * will reset itself.
 *
 * Theo P. Zourzouvillys <theo@voip.co.uk> - 30/05/06
 *
 */
 
#ifndef NDEBUG
#include <cassert>
#endif
 
#include <memory>
 
#include <boost/preprocessor/list/for_each.hpp>
#include <boost/preprocessor/tuple/to_list.hpp>
 
#define STATE_MACHINE_DEFINE_EVENTS(sm_name) \
  template<> template<typename EventTypeT> void sm_name::self_t::base_state::process_event(const EventTypeT & evt) { \
  typedef sm_name sm_t; switch (m_state)
 
#define STATE_CASE(R, _, T) case T: evt(static_cast< sm_t::self_t::state< T > & >(*this)); return;
#define STATE_MACHINE_DEFINITION(machine, states) \
  struct machine; \
  STATE_MACHINE_DEFINE_EVENTS(machine) { BOOST_PP_LIST_FOR_EACH(STATE_CASE, _, states) } }
 
/*
 * -------- State machine definition --------
 */
 
 
template<class DerivedT, typename StateTypeT, StateTypeT InitialStateT>
struct state_machine
{
  public:
 
    typedef state_machine< DerivedT, StateTypeT, InitialStateT > self_t;
 
  protected:
 
    state_machine();
 
  public:
 
    template<StateTypeT> struct state;
 
  protected:
 
    struct base_state
    {
      base_state(StateTypeT state_, DerivedT & fsm_);
 
      // The main worker for static_cast'ing - defined via STATE_MACHINE_DEFINITION()
 
      template<typename T>
      void process_event(const T & e);
 
      /*
       * Transition to a new state.
       */
 
      template<StateTypeT NewStateT>
      void transit();
 
      /*
       * Terminate this FSM.  This essentially resets the FSM to it's inital state.
       * ensure you do not use the state or state_machine after calling this function!
       */
 
      void terminate();
 
      private:
        StateTypeT m_state;
        DerivedT & m_fsm;
    };
 
 
  public:
 
    template<StateTypeT StateValueT>
    struct state : public base_state
    {
      state(DerivedT & fsm_) : base_state(StateValueT, fsm_) {}
    };
 
  private:
 
    void terminate();
 
    template<StateTypeT NewStateT>
    void transit();
 
  public:
 
  template<typename T>
  void
  process_event(const T & e);
 
  private:
 
    bool __processing;
    std::auto_ptr< base_state > m_fsm;
 
 
};

Implementation

 
/* -------- State machine implementation -------- */
 
template<class DerivedT, typename StateTypeT, StateTypeT InitialStateT>
state_machine<DerivedT, StateTypeT, InitialStateT>::state_machine()
 : __processing(false)
{
}
 
 
template<class DerivedT, typename StateTypeT, StateTypeT InitialStateT>
inline void
state_machine<DerivedT, StateTypeT, InitialStateT>::terminate()
{
  m_fsm.reset();
}
 
template<class DerivedT, typename StateTypeT, StateTypeT InitialStateT>
template<StateTypeT NewStateT>
inline void
state_machine<DerivedT, StateTypeT, InitialStateT>::transit()
{
  m_fsm = std::auto_ptr< base_state >(new state<NewStateT>(static_cast<DerivedT&>(*this)));
}
 
 
template<class DerivedT, typename StateTypeT, StateTypeT InitialStateT>
template<typename T>
inline void
state_machine<DerivedT, StateTypeT, InitialStateT>::process_event(const T & e)
{
  assert (__processing == false);
  __processing = true;
  try
  {
    if (m_fsm.get() == 0)
    {
      m_fsm = std::auto_ptr< base_state >(new state<InitialStateT>(static_cast<DerivedT&>(*this)));
    }
    m_fsm->process_event(e);
    __processing = false;
  }
  catch (...)
  {
    __processing = false;
    throw;
  }
}
 
template<class DerivedT, typename StateTypeT, StateTypeT InitialStateT>
state_machine<DerivedT, StateTypeT, InitialStateT>::base_state::base_state(StateTypeT state_, DerivedT & fsm_)
  : m_state(state_), m_fsm(fsm_)
{
}
 
template<class DerivedT, typename StateTypeT, StateTypeT InitialStateT>
template<StateTypeT NewStateT>
inline void
state_machine<DerivedT, StateTypeT, InitialStateT>::base_state::transit()
{
  m_fsm.transit<NewStateT>();
}
 
template<class DerivedT, typename StateTypeT, StateTypeT InitialStateT>
inline void
state_machine<DerivedT, StateTypeT, InitialStateT>::base_state::terminate()
{
  m_fsm.terminate();
}

Example Usage

 
/* -------- Start Declaration of Example FSM -------- */
 
/*
 * The states our FSM can be in.  In this example, we have 3.
 */
 
typedef enum { INITIAL, PROV_IN, PROV_OUT } fsm_states_t;
 
struct sig_fsm_machine : public state_machine<sig_fsm_machine, fsm_states_t, INITIAL>
{
};
 
/* State specialisations */
 
template<> template<> struct
sig_fsm_machine::self_t::state< PROV_IN > : public sig_fsm_machine::self_t::base_state
{
  state(sig_fsm_machine & fsm_) : base_state(PROV_IN, fsm_) {}
};
 
/*
 * Magic for static_cast.  First option is the name of your concrete FSM class (defined above), and the
 * second option is the states that the FSM can be in.  Make sure you update the first parameters
 * to BOOST_PP_TUPLE_TO_LIST (which is the number of states) when adding/removing state names.
 */
 
STATE_MACHINE_DEFINITION(
  sig_fsm_machine,
  BOOST_PP_TUPLE_TO_LIST(3, (INITIAL, PROV_IN, PROV_OUT))
)
 
/* -------- End Of Declaration -------- */
 
/*
 * Example Usage
 */
 
/*
 * Note that the event does not inherit from anything, so it is
 * possible for an event to traverse multiple FSM's.
 */
 
struct MyEvent
{
 
  void operator()(sig_fsm_machine::state<INITIAL> & sm) const
  {
    // Transition to a new state:
    sm.transit<PROV_IN>();
  }
 
  void operator()(sig_fsm_machine::state<PROV_IN>& sm) const
  {
    // Terminate the state.
    sm.terminate();
  }
 
  template<fsm_states_t StateT>
  void operator()(sig_fsm_machine::state<StateT> & /* sm */) const
  {
    assert(0);
  }
 
};
 
int main()
{
  sig_fsm_machine fsm;
  for (unsigned int i = 0 ; i < 1000000 ; i++) {
    // Here we post an event 'MyEvent()'.
    fsm.process_event(MyEvent());
  }
}