Skip to content

Instantly share code, notes, and snippets.

@arrieta
Created November 2, 2021 16:38
Show Gist options
  • Save arrieta/e8094e77954df353fb47b186af34a40a to your computer and use it in GitHub Desktop.
Save arrieta/e8094e77954df353fb47b186af34a40a to your computer and use it in GitHub Desktop.
Basic Table-Driven State Machine in C++
// clang-format off
/*
Basic example showing how could one implement a table-driven state machine in
C++.
Suppose one has a lamp which can be in one of three states: "Off", "On",
"Blink". At any time and via some mechanism, the lamp can trigger two events:
"Switch Off" or "Switch On".
The possible transitions (encoded as [State] --[Event]--> [New State]) are:
[Off ] --[Switch Off]--> [Off ]
[Off ] --[Switch On ]--> [On ]
[On ] --[Switch Off]--> [Off ]
[On ] --[Switch On ]--> [Blink]
[Blink] --[Switch Off]--> [Off ]
[Blink] --[Switch On ]--> [On ]
They are better captured in a State Transition Table:
+-------------+------------+-----------+
| State/Event | Switch Off | Switch On |
+-------------+------------+-----------+
| Off | Off | On |
+-------------+------------+-----------+
| On | Off | Blink |
+-------------+------------+-----------+
| Blink | Off | On |
+-------------+------------+-----------+
There are ways to implement state machines in C++, including enterprise-grade
libraries. The implementation below shows the absolute minimum set of features
I believe are needed.
Something to think about: Instead of adding States to the State Transition
Table, you can add functions that directly handle the transition. For example:
entries could be of type std::function<State(Args)>, where Args are any
arguments needed by your application. A function that throws an exception or
returns a State::Error (a value we don't include in the example below) can be
used to handle invalid transitions. Parsers can be implemented using this
technique (though that's not necessarily the best idea).
(C) 2021 Juan Arrieta, Nabla Zero Labs
Sample Run:
$ clang++ fsm.cpp -std=c++20
$ ./a.out
./a.out
current state: Off; trigger event (off=0/on=1): 0
[Off] --[Switch Off]--> [Off]
current state: Off; trigger event (off=0/on=1): 1
[Off] --[Switch On]--> [On]
current state: On; trigger event (off=0/on=1): 1
[On] --[Switch On]--> [Blink]
current state: Blink; trigger event (off=0/on=1): 1
[Blink] --[Switch On]--> [On]
current state: On; trigger event (off=0/on=1): 0
[On] --[Switch Off]--> [Off]
current state: Off; trigger event (off=0/on=1): 0
[Off] --[Switch Off]--> [Off]
current state: Off; trigger event (off=0/on=1): 1
[Off] --[Switch On]--> [On]
current state: On; trigger event (off=0/on=1): ^D
*/
// clang-format on
#include <array>
#include <iostream>
// enumeration of possible states
enum class State {
Off,
On,
Blink,
Count, // useful to obtain total number of states
};
// write a state to an output stream
std::ostream& operator<<(std::ostream& os, const State& s) {
static const char* const names[]{"Off", "On", "Blink"};
return os << names[static_cast<int>(s)];
}
// enumeration of possible events
enum class Event {
SwitchOff,
SwitchOn,
Count, // useful to obtain total number of events
};
// write an event to an output stream
std::ostream& operator<<(std::ostream& os, const Event& e) {
static const char* const names[]{"Switch Off", "Switch On"};
return os << names[static_cast<int>(e)];
}
// return new state after state `s` transitions due to event `e`
constexpr State transition(State s, Event e) noexcept {
// clang-format off
// state transition table has as many rows as states and as many columns as
// events; entry at (i, j) contains the new state resulting from state i
// transitioning due to event j; order matters (rows must be in order of State
// enumeration; cols must be in order of Event enumeration)
constexpr const std::array<
std::array<State, static_cast<int>(Event::Count)>,
static_cast<int>(State::Count)> stt = {{
// Switch Off | Switch On | (new events add columns)
{ State::Off, State::On }, // State::Off
{ State::Off, State::Blink }, // State::On
{ State::Off, State::On }, // State::Blink
// (new states add rows)
}};
// clang-format on
// real-world implementation would avoid segfault by ensuring that s and e are
// within the range of defined enums
const auto row = static_cast<int>(s);
const auto col = static_cast<int>(e);
return stt[row][col];
}
int main() {
auto current_state = State::Off;
int input = 0;
while (true) {
std::cout << "current state: " << current_state
<< "; trigger event (off=0/on=1): ";
if (!(std::cin >> input)) {
break;
}
const auto event = Event{input};
const auto new_state = transition(current_state, event);
std::cout << "[" << current_state << "] --[" << event << "]--> ["
<< new_state << "]\n";
current_state = new_state;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment