Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

C/C++

A Finite State Machine Framework


In many software-design methodologies, we use state transition diagrams to model the behavior of subsystems (processes) or objects with a set of finite states and transitions. In some cases, it becomes obvious that these translate into software implementations beyond the model. The state transition diagram, better known as a finite state machine (FSM) in software implementation, is one of the most popular methods for invoking control-oriented systems. This is particularly true in real-time software applications.

There are a number of techniques for developing finite state machines in software, with one of the more popular being the use of nested switch-case statements [1]. The drawback to this approach is that as the state machine grows, so does the logic — and in C++ this is not an attractive approach to true object-oriented development. There are many methods that have been discussed in development state machines in C++, but none of them has truly drawn a conclusive framework that can be ported from implementation to implementation. Many state machines are written in software straight from their state pattern(s) modeled in some design methodology, such as UML.

In the past, I developed FSMs using basic ANSI C. Listing One is the traditional C-style approach, which avoids the overuse of the switch-case construct. Recently, with embedded real time moving into C++ as a target language, I have ported this scheme to a simple, yet reusable, framework. Even though the target of such a framework implies embedded real time, it is not limited to it. Think of all those GUI-based applications that pass messages from one window to the next. These are highly qualified state machine candidates.

Listing One: C-style FSM.

// C-style method of doing a simple Finite State Machine
#define INVALID_EVENT       -1
#define INVALID_STATE       -1

typedef int event_t;
typedef int state_t;
typedef void (*FPAction)(void*);

typedef struct State_ State;

// State Machine components
typedef struct Transition_
{
    const event_t event; 
    FPAction action;
    const State* state;
} Transition;
struct State_
{
    const Transition* table;
    FPAction entry;
    FPAction exit;
};
// Create the State Transition Table
#define DEFINE_TRANSITION_TABLE(name) \
    Transition name##_TransitionTable[] = {
#define ADD_TRANSITION(ev,ac,st) \
    { ev, ac, st },
#define END_TRANSITION_TABLE \
    { INVALID_EVENT, NULL, INVALID_STATE } }
// DEFINE_STATE_TABLE
#define DEFINE_STATE_TABLE(name) \
    State name##_StateTable[] = {
#define ADD_STATE(name,entry,exit) \
    { name##_TransitionTable, entry, exit },
#define END_STATE_TABLE \
    { NULL, NULL, NULL } }
// Access  operations
#define GET_STATE_TABLE_ENTRY(name,st) \
    name##_StateTable[st]
#define GET_STATE_TRANSITION_TABLE(name,st) \
    (name##_StateTable[st]).table
#define GET_STATE_ENTRY_CRITERIA(name,st) \
    (name##_StateTable[st]).entry
#define GET_STATE_EXIT_CRITERIA(name,st) \
    (name##_StateTable[st]).exit
</pre
<P>

<h3>The Framework</h3>
<p>The new framework must provide a lightweight and portable approach to implementing finite state machines in C++. Traditionally, from what I have read, most take the approach as follows: Given a state machine, a class, <code>T</code>, extends the base state machine class. In this approach, <code>T</code> implies an is-a relationship to the state machine. While there is nothing wrong with this scheme and in itself provides a solid framework, it suffers from exposing the public nature of <code>T</code>. Therefore, <code>T</code> can either be invoked via its own public implementation or via its parent class, the state machine. </p>
<P>
<p>Since state machines are applied in situations where control dictates the operation of a piece of software, it would seem best to hide <code>T</code> behind the state machine. In other words, you have a state machine of <code>T</code> instead of the other way around. Not only does it hide details about <code>T</code>, but provides communication to <code>T</code> only through the state machine, thus implying the control logic driven by events or messages.</p>
<P>
<p>I have taken two paths, via a compile-time option, of how <code>T</code> is implemented as a state machine. The first extends <code>T</code> privately (that is, private inheritance). This approach guarantees that an instance of <code>StateMachine<></code> hides the implementation of <code>T</code> at the constructor and the state machine cannot be cast as a T-pointer except by its own members and friends [2]. The downside is that a <code>T</code> will always require a default constructor and force the developer to initialize <code>T</code> with default parameters or obtain them through some other means, which could be an issue for multiple state machine instances of <code>T</code>.</p>
<P>
<p>The second approach is to contain <code>T</code> as an aggregate association; that is, a private member of <code>StateMachine<></code>. This allows an instance of <code>T</code> to be constructed prior to the state machine creation with the necessary parameters required to initialize it. The drawback to this method is that although <code>T</code> is a hidden member of the state machine, its creation could have been done prior to state machine creation. This provides a dilemma as to whether you allow the state machine to destroy <code>T</code> on its destruction, or whether it is the responsibility of the original creator? I have decided that the state machine will destroy the instance of <code>T</code> upon its destructor being invoked. One way to easily work around who owns <code>T</code> at its creation is solved:</p>
<P>
<pre class="brush: cpp; html: collapse;" style="font-family: Andale Mono,Lucida Console,Monaco,fixed,monospace; color: rgb(0, 0, 0); background-color: rgb(238, 238, 238); font-size: 12px; border: 1px dashed rgb(153, 153, 153); line-height: 14px; padding: 5px; overflow: auto; width: 100%;">
StateMachine<T,EV,CMP> myStateMachine ( new T(_), initState );

For this article, I use T through inheritance for the sake of illustration and example. In either case, the state machine plays the surrogate to dispatching control to T. Listing Two presents the base state machine classes.

Listing Two: Base state machine classes.

#ifdef DERIVE_STATE_MACHINE 

#define THIS            (*this)

template <class T, class EV, class CMP = std::less<EV> >
class StateMachine : private T
{
public: 
    explicit StateMachine( State<T,EV,CMP>* const stStart ) : 
        T(), m_stStart(stStart), m_stCurrent(stStart), m_stThis(eStopped) {}
// Aggregated Version of State Machine
#else
#define THIS            (*m_T)
template <class T, class EV, class CMP = std::less<EV> >
class StateMachine
{
private:
    T* m_T;
public: 
    explicit StateMachine( T* _T, State<T,EV,CMP>* const stStart ) : 
      m_T(_T), m_stStart(stStart), m_stCurrent(stStart), m_stThis(eStopped) {}
    ~StateMachine() { delete m_T; }

#endif      // DERIVE_STATE_MACHINE
    ... // other API functions not shown
private: 
    State<T,EV,CMP>* const m_stStart;
    State<T,EV,CMP>* m_stCurrent;
};

The Event

There are four parts to the state-machine framework:

  • Event.
  • State.
  • Transition.
  • Action.

Event (EV) is the catalyst that causes the state machine to run; in other words, transition from state to state. Events can also be messages, as they are commonly called in GUI-based applications. Events are internal or external to the system in which the state machine is running. The origin of the event is not of concern to the state machine, at least from this framework's point of view. Pre- and postprocessing of events are not the responsibility of the state machine, since this detracts from the generalization of the framework, which makes it portable.

The state machine I present offers one API for processing events, PostEvent. Notice I did not say "handling," because in this framework the state machine does not handle the event. How could it and still be reusable, since events are handled specifically to the environment in which they are invoked? The state machine knows nothing about its environment. So as far as it is concerned, the event is only a key that is used to help the state machine transition from one state to the next. The actual handling of the event, which may require system interaction prior to and/or after the event, has been passed to the state machine.

Figure 1 shows how you might integrate FSMs into their solution. I have purposely put an event handler as the interface to the system and not the state machine. Again, the FSM is not responsible for system-level interactions, so it knows nothing about handling of events — which is why the framework is portable. In this scenario, it is the responsibility of end developers to do the pre- and postprocessing of the events when calling the state machine as well as provide all synchronization.

Figure 1: Integrating FSMs into applications.

Input/output data to/from events may be encapsulated within event wrappers. For example:

class MyEvent {
   int hEvent;
   CRITICAL_SECTION hLock;
   ... // Other specific information to Event Wrappers
public:
   MyEvent( const int ev ) : hEvent(ev) {...}
   ... // Other initialization and member functions
public:
   char* inbuffer;
   mutable char* outbuffer;
   ... // other member functions and constructors not shown
};

Since the event is passed as a const reference, any data to be manipulated by event handlers should be a mutable type. In this example, only the output buffer has this attribute.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.