CODEWITHSUNDEEP
c++state-machine
Igal Spector
Igal Spector

Reputation: 83

Implementing a State Machine in C++

I'm new to C++.

How can I implement a State Machine in C++?

I'm getting only the messages and should know the next state.

What is the proper structure I need to use?

Upvotes: 3

Views: 16274

Answers (12)

kasperjj
kasperjj

Reputation: 3664

Unless you are implementing a state machine for the sake of implementing one, I would highly recommend that you use a state machine generator instead. Ragel is one very good and robust solution.

https://github.com/bnoordhuis/ragel

Upvotes: 4

Patrick
Patrick

Reputation: 23619

typedef std::pair<State,Message> StateMessagePair;
typedef std::map<StateMessagePair,State> StateDiagram;
StateDiagram sd;
// add logic to diagram
...
State currentState = getInitialState();
...
// process message
Message m = getMessage();
StateDiagram::iterator it=sd.find(std::make_pair(currentState,m)));
if (it==sd.end()) exit("incorrect message");
currentState = it->second;

EDIT: Building up the state diagram is done like this (example is for a cola-vending machine):

StateDiagram.insert(std::make_pair(State::Idle           ,Message::MakeChoice   ),State::WaitingForMoney);
StateDiagram.insert(std::make_pair(State::WaitingForMoney,Message::Cancel       ),State::Idle);
StateDiagram.insert(std::make_pair(State::WaitingForMoney,Message::MoneyEntered ),State::FindCan);
StateDiagram.insert(std::make_pair(State::FindCan        ,Message::CanSentToUser),State::Idle);

Default actions can be implemented using a second map, where the key is only the State, like this:

typedef std::map<State,State> StateDiagramForDefaults;

Instead of printing "incorrect message", the logic can perform a lookup in the StateDiagramForDefaults.

If actions needs to be added to the state diagram, the value of the map should be a pair consisting of an action, and a new state, like this:

typedef std::pair<State,Message> StateMessagePair;
typedef std::pair<State,IAction *> StateActionPair;
typedef std::map<StateMessagePair,StateActionPair> StateDiagram;

The logic that builds up the diagram should then "new" an instance of a class that implements IAction, and put that in the StateDiagram.

The executing logic then just executes the IAction implementation via a virtual method (e.g. execute() or the ()-operator).

Upvotes: 7

Chris Dennett
Chris Dennett

Reputation: 22721

You can use the Ragel state machine compiler: http://www.complang.org/ragel/

Ragel compiles executable finite state machines from regular languages. Ragel targets C, C++ and ASM. Ragel state machines can not only recognize byte sequences as regular expression machines do, but can also execute code at arbitrary points in the recognition of a regular language. Code embedding is done using inline operators that do not disrupt the regular language syntax.

The core language consists of standard regular expression operators (such as union, concatenation and Kleene star) and action embedding operators. The user’s regular expressions are compiled to a deterministic state machine and the embedded actions are associated with the transitions of the machine. Understanding the formal relationship between regular expressions and deterministic finite automata is key to using Ragel effectively.

Ragel also provides operators that let you control any non-determinism that you create, construct scanners, and build state machines using a statechart model. It is also possible to influence the execution of a state machine from inside an embedded action by jumping or calling to other parts of the machine, or reprocessing input.

Ragel provides a very flexible interface to the host language that attempts to place minimal restrictions on how the generated code is integrated into the application. The generated code has no dependencies.

Ragel code looks like:

action dgt      { printf("DGT: %c\n", fc); }
action dec      { printf("DEC: .\n"); }
action exp      { printf("EXP: %c\n", fc); }
action exp_sign { printf("SGN: %c\n", fc); }
action number   { /*NUMBER*/ }

number = (
    [0-9]+ $dgt ( '.' @dec [0-9]+ $dgt )?
    ( [eE] ( [+\-] $exp_sign )? [0-9]+ $exp )?
) %number;

main := ( number '\n' )*;

.. and it compiles to:

st0:
    if ( ++p == pe )
        goto out0;
    if ( 48 <= (*p) && (*p) <= 57 )
        goto tr0;
    goto st_err;
tr0:
    { printf("DGT: %c\n", (*p)); }
st1:
    if ( ++p == pe )
        goto out1;
    switch ( (*p) ) {
        case 10: goto tr5;
        case 46: goto tr7;
        case 69: goto st4;
        case 101: goto st4;
    }
    if ( 48 <= (*p) && (*p) <= 57 )
        goto tr0;
    goto st_err;

Upvotes: 0

jopa
jopa

Reputation: 1139

Of course, boost has something in store for you: Boost Statechart library. You can also find some nice tutorials there.

Upvotes: 1

lurscher
lurscher

Reputation: 26943

The one i am using is based on this one: Machine Objects.

It seems to be well optimized and is a hell of a lot less complex to use than Boost Statechart.

Upvotes: 1

Larry Morell
Larry Morell

Reputation: 502

See Implementing Finite Automata in a Program for several different ways of building finite state machines.

Upvotes: 2

Sandeep
Sandeep

Reputation: 658

Checkout the hierarchical state machine article. Modeling of states as classes is described with an example.

Upvotes: 1

ravenspoint
ravenspoint

Reputation: 20457

Gosh, it isn’t as complicated as it seems. State machine code is very simple and short.

Coding a state machines is just about trivial. The hard part is designing a state machine that behaves correctly in all possible cases.

But let us assume that you have the correct design. How do you code it?

  1. Store the state in an attribute, myState perhaps.

  2. Whenever you receive a message switch on the myState attribute to execute the code for that state.

3 In each state, switch on the message to execute the code for that state AND that message

So you need a nested switch statement

cStateMachine::HandleMessage( msg_t msg )
{
  switch( myState ) {

     case A:

        switch( msg ) {

           case M:

           // here is the code to handle message M when in state A

...

Once you have this up and running, it is fun and easy to add more states and messages.

Upvotes: 2

Miro Samek
Miro Samek

Reputation: 1975

The standard state machine implementation techniques are:

  1. the nested switch statement (some previous posts show examples of this technique)
  2. state-table
  3. the GoF State design pattern
  4. combination of the above

If you are new to state machines and implementation in C or C++, I would recommend my Dr.Dobbs article "Back to Basics" available at http://www.ddj.com/184401737 (you need to click on the Print link at the top to conveniently read the text.)

None of the standard techniques is suitable for the hierarchical state machines (such as UML statecharts). If you are interested in the modern UML state machines, I'd recommend my 3-part Embedded.com article "A crash course in UML state machines" (http://www.embedded.com/design/testissue/215801043).

Upvotes: 6

ChrisW
ChrisW

Reputation: 56083

One way is to use a class like this (rough example code ahead):

class State
{
  //pass a new Message into the current State
  //current State does (state-specific) processing of
  //the message, and returns a pointer to the new State
  //if there's a state change
  virtual State* getNewState(const Message&) = 0;
};

class ExampleState
{
  virtual State* getNewState(const Message& message)
  {
    switch (message.type)
    {
      case MessageType.Stop:
        //change state to stopped
        return new StoppedState();
    }
    //no state change
    return 0;
  }
};

On of the complications is whether states should be static flyweights, or whether they carry instance data and should therefore be newed and deleted.

Upvotes: 2

Shaihi
Shaihi

Reputation: 3974

switch(currentState) {
    state1:
         currentState = NEXT_STATE2;
         break;
    ....
}

Upvotes: 0

Paul R
Paul R

Reputation: 212929

For simple state machines you can just use a switch statement inside a loop, e.g.

for (;;)
{
    switch (state)
    {

    case STATE_1:
        // do stuff
        // maybe change state
        break;

    case STATE_2:
        // do stuff
        // maybe change state
        break;

    case STATE_3:
        // do stuff
        // maybe change state
        break;

    // ...

    }
}

Upvotes: 19

Related Questions