State machine implementation

Question

I have a state machine as described below.

We can start in one of two starting states, but we must hit all 4 states of the handshake. From there, we can either transfer a payload of data or receive a payload of data. Then, we return to our original starting state.

Handshake:

-> StartingState1 -> FinalState1 -> StartingState2 -> FinalState2

-> StartingState2 -> FinalState2 -> StartingState1 -> FinalState1

Payload Transfer:

-> SendPayload -> SendEnd -> StartingState?

-> ReceivePayload -> ReceiveEnd -> StartingState?

The code below represents my current architecture. Unfortunately, at the end of each process, I don't have enough information from within the states to know what the next state is I should hit.

Does anybody have any suggestions on how to improve this architecture based on my requirements?

Thanks, PaulH

class MyMachine;
class Payload;

class IState
{
    MyMachine* context_;

    IState( MyMachine* context ) : context_( context) {};

    virtual void Consume( byte data );

    void ChangeState( IState* state )
    {
        context_->SetState( state );
    }
}

class FinalState1 : IState
{
    void Consume( byte data )
    {
        // Either go to StartingState1, SendPayload, or ReceivePayload.
        // How can I tell from within the context of this state where I 
        // should go?
    }
}

class StartingState1 : IState
{
    void Consume( byte data )
    {
        if ( /*some condition*/ )
        {
            ChangeState( new FinalState1( context_ ) );
        } 
    }
}

class MyMachine
{
    IState* state_;
    Payload* payload_;

    void Start1( Mode mode )
    {
        state_ = new StartingState1( this );
    }

    void Start2( Mode mode )
    {
        state_ = new StartingState2( this );
    }

    void Consume( byte data )
    {
        state_->Consume( data );
    }

    void SetPayload( const Payload* payload )
    {
        payload_ = payload;
    }

    const Payload* GetPayload()
    {
        return payload_;
    }

    void SetState( State* state )
    {
        delete state_;
        state_ = state;
    }
}

// get a byte of data from some source
byte GetData();

void main()
{
    MyMachine machine;
    Payload payload;
    machine.SetPayload( payload );
    machine.Start1( Mode::SendPayload );

    // could also call:
    // machine.Start1( Mode::ReceivePayload );
    // machine.Start2( Mode::SendPayload );
    // machine.Start2( Mode::ReceivePayload );

    for(;;)
    {
        machine.Consume( GetData() );
    }
}

Answer 1

Did you look at boost::statechart library?

Answer 2

What you have doesn't represent the possible states of your system completely, but it's easy to transform it so that it does. You need additional states to represent the difference between being in state 1 and not having been in state 2, and being in state 1, whilst having been in state 2 (and the same for state 2). So you need:

S1 S2 F1 F2 S12 F12 S21 F21
SP SE
RP RE

with transitions

S1 --> F1
F1 --> S12
S12 --> F12
F12 --> SP or F12 --> RP

S2 --> F2
F2 --> S21
S21 --> F21
F21 --> SP or F21 --> RP

SP --> SE
RP --> RE
SE --> S1 or SE --> S2
RE --> S1 or RE --> S2

The key difference is the introduction of new states S12, F12, S21 and F21. In terms of implementation you could almost certainly just derive S12 from S2, F12 from F2, S21 from S1 and F21 from F2 and override the transition function to go to the correct state.

(Apologies for acronymising all your states).

Answer 3

I suggest designing from the point of view of function object or function pointers.

A simple state machine can be implemented using an array or std::map. Use the current state as an index and retrieve either the new state or a pointer to the state function.

More complex state machines travel from one state to another based on a transition or event. Simply implemented, this requires a 'nested' array. A container of transition containers. The first access gives you the transition table for a state. Use the current transition as an index into the transition table to return a function pointer of the function that handles this transition.

There different data structures that can be used, all depending on the complexity of your state machine.

A nice idea is to have a table driven state machine. This allows the engine to be coded and tested once. Changing the state machine involves changing the data in the table. The table may be able to exist outside of the executable, which means that the executable doesn't have to change. This concept can be expanded by using dynamic libraries, reducing the need to change the executable.

This is just my suggestion, I could be wrong (paraphrased from Dennis Miller).

Answer 4

Here is an example using the method suggested by Thomas:

#include <cassert>
#include <iostream>
#include <map>

class Machine;

typedef void (*StateFunctionPtr)(Machine& context);

// State "do" functions
void starting1(Machine& context)        {std::cout << "S1 ";}
void final1(Machine& context)           {std::cout << "F1 ";}
void starting2(Machine& context)        {std::cout << "S2 ";}
void final2(Machine& context)           {std::cout << "F2 ";}
void sendPayload(Machine& context)      {std::cout << "SP ";}
void sendEnd(Machine& context)          {std::cout << "SE ";}
void receivePayload(Machine& context)   {std::cout << "RP ";}
void receiveEnd(Machine& context)       {std::cout << "RE ";}

namespace State
{
    enum Type {start, handshake1, handshake2, handshake3,
        handshake4, xferPayload, endPayload};
};

// Aggregate of state, "mode" variables, and events.
struct StateKey
{
    // Needed for use as map key
    bool operator<(const StateKey& rhs) const
    {
        return
              (state < rhs.state)
        ||  ( (state == rhs.state) && (isReceiving < rhs.isReceiving) )
        ||  ( (state == rhs.state) && (isReceiving == rhs.isReceiving)
                && (startsAt2 < rhs.startsAt2) );
    }

    bool startsAt2;
    bool isReceiving;
    State::Type state;
};

struct StateEffect
{
    StateFunctionPtr function;  // "do" function
    State::Type newState;       // state to transition to
};

struct StatePair
{
    StateKey key;
    StateEffect effect;
};

const StatePair stateTable[] =
{
    {{0, 0, State::start},       {&starting1,       State::handshake1}},
    {{0, 0, State::handshake1},  {&final1,          State::handshake2}},
    {{0, 0, State::handshake2},  {&starting2,       State::handshake3}},
    {{0, 0, State::handshake3},  {&final2,          State::handshake4}},
    {{0, 0, State::handshake4},  {&sendPayload,     State::xferPayload}},
    {{0, 0, State::xferPayload}, {&sendEnd,         State::endPayload}},
    {{0, 0, State::endPayload},  {&starting1,       State::handshake1}},

    {{0, 1, State::start},       {&starting1,       State::handshake1}},
    {{0, 1, State::handshake1},  {&final1,          State::handshake2}},
    {{0, 1, State::handshake2},  {&starting2,       State::handshake3}},
    {{0, 1, State::handshake3},  {&final2,          State::handshake4}},
    {{0, 1, State::handshake4},  {&receivePayload,  State::xferPayload}},
    {{0, 1, State::xferPayload}, {&receiveEnd,      State::endPayload}},
    {{0, 1, State::endPayload},  {&starting1,       State::handshake1}},

    {{1, 0, State::start},       {&starting2,       State::handshake1}},
    {{1, 0, State::handshake1},  {&final2,          State::handshake2}},
    {{1, 0, State::handshake2},  {&starting1,       State::handshake3}},
    {{1, 0, State::handshake3},  {&final1,          State::handshake4}},
    {{1, 0, State::handshake4},  {&sendPayload,     State::xferPayload}},
    {{1, 0, State::xferPayload}, {&sendEnd,         State::endPayload}},
    {{1, 0, State::endPayload},  {&starting2,       State::handshake1}},

    {{1, 1, State::start},       {&starting2,       State::handshake1}},
    {{1, 1, State::handshake1},  {&final2,          State::handshake2}},
    {{1, 1, State::handshake2},  {&starting1,       State::handshake3}},
    {{1, 1, State::handshake3},  {&final1,          State::handshake4}},
    {{1, 1, State::handshake4},  {&receivePayload,  State::xferPayload}},
    {{1, 1, State::xferPayload}, {&receiveEnd,      State::endPayload}},
    {{1, 1, State::endPayload},  {&starting2,       State::handshake1}}
};


class Machine
{
public:
    Machine()
    {
        // Initialize state chart map from constant state table
        const size_t tableSize = sizeof(stateTable) / sizeof(stateTable[0]);
        for (size_t row=0; row<tableSize; ++row)
        {
            stateChart_[stateTable[row].key] = stateTable[row].effect;
        }
    }

    // If startsAt2==true, then FSM will start with starting2 handshake function
    void reset(bool startsAt2, bool isReceiving)
    {
        stateKey_.startsAt2 = startsAt2;
        stateKey_.isReceiving = isReceiving;
        stateKey_.state = State::start;
    }

    void step()
    {
        StateChart::const_iterator iter = stateChart_.find(stateKey_);
        assert(iter != stateChart_.end());
        const StateEffect& effect = iter->second;
        effect.function(*this);
        stateKey_.state = effect.newState;
    }

private:
    typedef std::map<StateKey, StateEffect> StateChart;
    StateChart stateChart_;
    StateKey stateKey_;
};

int main()
{
    Machine machine;
    machine.reset(true, false);
    for (int i=0; i<20; ++i)
    {
        machine.step();
    }
}

It compiles and works on my machine. You might want to add the following features:

• Entry/exit functions in StateEffect
• Event "triggers" in StateKey
• Generalize into a template.

Add enough generic features to it, and it will start resembling a Boost.StateChart wannabe. ;-)