State Machine Design in C++

A typical scenario consists of an external event being generated, which, again, boils down to a function call into the class's public interface. Based upon the event being generated and the state machine's current state, a lookup is performed to determine if a transition is required. If so, the state machine transitions to the new state and the code for that state executes. At the end of the state function, a check is performed to determine whether an internal event was generated. If so, another transition is performed and the new state gets a chance to execute. This process continues until the state machine is no longer generating internal events, at which time the original external event function call returns. The external event and all internal events, if any, execute within the caller's thread of control.

Once the external event starts the state machine executing, it cannot be interrupted by another external event until the external event and all internal events have completed execution. This provides a multithread-safe environment for the state transitions. Semaphores or mutexes can be used in the state machine engine to block other threads that might be trying to be simultaneously access the same object.

Event Data

When an event is generated, it can optionally attach event data to be used by the state during execution. Once the state has completed execution, the event data is considered used up and must be deleted. Therefore, any event data sent to a state machine must be created on the heap, via operator new, so that the state machine can delete it once used. In addition, for our particular implementation the event data must inherit from the EventData base class (see Listing One). This gives the state machine engine a common base class for which to delete all event data.

Listing One: The EventData class

#ifndef EVENT_DATA_H
#define EVENT_DATA_H

class EventData 
{
public:
    virtual ~EventData() {};  
};
#endif //EVENT_DATA_H

Creating event data on the heap may seem like a needless step, but it allows a pointer to the event data to travel through operating system message queues until it arrives at its destination. At that point, the data will be used by the state machine and subsequently deleted. This eliminates the need to send the entire data structure through the queue when just a pointer will do. It's also another reason that event function calls do not return data, such as a status code. When the event finally arrives at its destination, the call being made may have been initiated from a different task, or even a different processor, such that a synchronous return code will have no meaning to the calling thread.

State Transitions

When an external event is generated, a lookup is performed to determine the state transition course of action. There are three possible outcomes to an event: new state, event ignored, or cannot happen. A new state causes a transition to a new state where it is allowed to execute. Transitions to the existing state are also possible, which means the current state is re-executed. For an ignored event, no state executes. However, the event data, if any, is deleted. The last possibility, cannot happen, is reserved for situations where the event is not valid given the current state of the state machine. If this occurs, the software faults.

In this implementation, internal events are not required to perform a validating transition lookup. The state transition is assumed to be valid. You could check for both valid internal and external event transitions, but in practice this just takes more storage space and generates busywork for very little benefit. The real need for validating transitions lies in the asynchronous, external events where a client can cause an event to occur at an inappropriate time. Once the state machine is executing, it cannot be interrupted. It is under the control of the class's private implementation, thereby making transition checks unnecessary. This gives the designer the freedom to change states, via internal events, without the burden of updating transition tables.

State Machine Implementation

Two base classes are necessary to use a state machine object: StateMachine and EventData. A class inherits from StateMachine to obtain the necessary mechanisms to support state transitions and event handling. The StateMachine class also contains various preprocessor macros to ease implementation of the state machine. To send data structures or classes to the state functions, the structure must inherit from the EventData base class.

I first present a look at the internals of the StateMachine class. Then I show how to use it correctly. StateMachine is the base class used for handling state transitions (see Listings Two and Three). Any class implemented as a state machine inherits from this class. The interface is contained within three functions:

void ExternalEvent(unsigned char, EventData* = NULL)
void InternalEvent(unsigned char, EventData* = NULL)
virtual const StateStruct* GetStateMap() = 0

Listing Two: Defines base class for state machines

#ifndef STATE_MACHINE_H
#define STATE_MACHINE_H
#include <stdio.h>
#include "EventData.h"

struct StateStruct;

// base class for state machines
class StateMachine 
{
public:
    StateMachine(int maxStates);
    virtual ~StateMachine() {}
protected:
    enum { EVENT_IGNORED = 0xFE, CANNOT_HAPPEN };
    unsigned char currentState;
    void ExternalEvent(unsigned char, EventData* = NULL);
    void InternalEvent(unsigned char, EventData* = NULL);
    virtual const StateStruct* GetStateMap() = 0;
private:
    const int _maxStates;
    bool _eventGenerated;
    EventData* _pEventData;
    void StateEngine(void);
};

typedef void (StateMachine::*StateFunc)(EventData *);
struct StateStruct 
{
    StateFunc pStateFunc;    
};

#define BEGIN_STATE_MAP \
public:\
const StateStruct* GetStateMap() {\
    static const StateStruct StateMap[] = { 

#define STATE_MAP_ENTRY(entry)\
    { reinterpret_cast<StateFunc>(entry) },

#define END_STATE_MAP \
    { reinterpret_cast<StateFunc>(NULL) }\
    }; \
    return &StateMap[0]; }

#define BEGIN_TRANSITION_MAP \
    static const unsigned char TRANSITIONS[] = {\

#define TRANSITION_MAP_ENTRY(entry)\
    entry,

#define END_TRANSITION_MAP(data) \
    0 };\
    ExternalEvent(TRANSITIONS[currentState], data);

#endif //STATE_MACHINE_H

Listing Three: Implements StateMachine class

#include <assert.h>
#include "StateMachine.h"

StateMachine::StateMachine(int maxStates) :
    _maxStates(maxStates),
    currentState(0),
    _eventGenerated(false),
    _pEventData(NULL)
{
}    

// generates an external event. called once per external event 
// to start the state machine executing
void StateMachine::ExternalEvent(unsigned char newState, 
                                 EventData* pData)
{
    // if we are supposed to ignore this event
    if (newState == EVENT_IGNORED) {
        // just delete the event data, if any
        if (pData)  
            delete pData;
    }
    else {
        // generate the event and execute the state engine
        InternalEvent(newState, pData); 
        StateEngine();                  
    }
}

// generates an internal event. called from within a state 
// function to transition to a new state
void StateMachine::InternalEvent(unsigned char newState, 
                                 EventData* pData)
{
    _pEventData = pData;
    _eventGenerated = true;
    currentState = newState;
}

// the state engine executes the state machine states
void StateMachine::StateEngine(void)
{
    EventData* pDataTemp = NULL;

    // TBD - lock semaphore here
    // while events are being generated keep executing states
    while (_eventGenerated) {         
        pDataTemp = _pEventData;  // copy of event data pointer
        _pEventData = NULL;       // event data used up, reset ptr
        _eventGenerated = false;  // event used up, reset flag

        assert(currentState < _maxStates);

        // execute the state passing in event data, if any
        const StateStruct* pStateMap = GetStateMap();
        (this->*pStateMap[currentState].pStateFunc)(pDataTemp);

        // if event data was used, then delete it
        if (pDataTemp) {
            delete pDataTemp;
            pDataTemp = NULL;
        }
    }
    // TBD - unlock semaphore here
}

ExternalEvent generates an external event to the state machine using as arguments the new state and a pointer to an EventData object, if any. The InternalEvent function generates internal events using the same set of arguments. The GetStateMap function returns an array of state-function pointers which will be retrieved by the state engine when appropriate. This function must be implemented by the inheriting class since it is pure virtual. However, macros are provided to implement this function for us, as I will demonstrate shortly.