This chapter discusses standard state machine implementation techniques, which you can find in the literature or in the working code. They are mostly applicable to the traditional nonhierarchical extended finite state machines (FSMs) because hardly any standard implementations of hierarchical state machines (HSMs) are intended for manual coding.1 Design automation tools often use standard state machine implementation techniques to generate code for hierarchical state machines. The resulting code, however, is typically intended not for manual maintenance but rather to be regenerated every time you change the state diagram inside the tool.
Typical implementations of state machines in high-level programming languages, such as C or C++, include:
To focus the discussion and allow meaningful comparisons, in all following state machine implementation techniques I'll use the same time-bomb example. As shown Figure 3.1, the time bomb has a control panel with an LCD that shows the current value of the timeout and three buttons: UP, DOWN, and ARM. The user begins with setting up the time bomb using the UP and DOWN buttons to adjust the timeout in one-second steps. Once the desired timeout is selected, the user can arm the bomb by pressing the ARM button. When armed, the bomb starts decrementing the timeout every second and explodes when the timeout reaches zero. An additional safety feature is the option to defuse an armed bomb by entering a secret code. The secret defuse code is a certain combination of the UP and DOWN buttons terminated with the ARM button press. Of course, the defuse code must be correctly entered before the bomb times out.
Figure 3.2 shows FSM that models the time-bomb behavior. The following explanation section illuminates the interesting points.
(1) The initial transition initializes the me->timeout
extended state variable and enters the “setting” state.
(2) If the timeout is below the 60-second limit, the internal transition UP in state “setting” increments the me->timeout
variable and displays it on the LCD.
(3) If the timeout is above the 1 second limit, the internal transition DOWN in state “setting” decrements the me->timeout
variable and displays it on the LCD.
(4) The transition ARM to state “timing” clears the me->code
extended state variable to make sure that the code for defusing the bomb is wiped clean before entering the “timing” state.
(5) The internal transition UP in state “timing” shifts the me->code
variable and inserts the 1-bit into the least-significant-bit position.
(6) The internal transition DOWN in state “timing” just shifts the me->code
variable and leaves the least-significant-bit at zero.
(7) If the entered defuse code me->code
matches exactly the secret code me->defuse
given to the bomb in the constructor, the transition ARM to state “setting” disarms the ticking bomb. Note that the “setting” state does not handle the TICK event, which means that TICK is ignored in this state.
(8) The handling of the most important TICK event in state “timing” is the most complex. To make the time-bomb example a little more interesting, I decided to generate the TICK event 10 times per second and to include an event parameter fine_time
with the TICK event. The fine_time
parameter contains the fractional part of a second in 1/10 s increments, so it cycles through 0, 1, .., 9 and back to 0. The guard [e->fine_time == 0]
checks for the full-second rollover condition, at which time the me->timeout
variable is decremented and displayed on the LCD.
(9) The choice pseudostate is evaluated only if the first segment of the TICK transition fires. If the me->timeout
variable is zero, the transition segment is executed that calls the BSP_boom()
function to trigger the destruction of the bomb (transition to the final state).
(10) Otherwise the choice pseudostate selects the transition back to “timing.”
Every state machine implementation technique described in this chapter comes with the complete source code for the time-bomb example and the precompiled executable program. The C version of the code is located in the directory <qp>qpcexamples80x86dos cpp101omb
, whereas the C++ version is found in <qp>qpcppexamples80x86dos cpp101omb
.
The executable program for each coding technique is a simple console application compiled with the free Turbo C++ 1.01 compiler (see Section 1.1 in Chapter 1). The Turbo C++ project files are included with the application source code. Figure 3.3 shows an example run of the time-bomb application.
Note
Because all the examples in this chapter are simple console applications, they can easily be compiled with just about any C/C++ compiler for your favorite desktop workstation, including Linux.2 The Linux platform requires slightly different techniques for interacting with the console, but the state machine code can be exactly the same. The code accompanying this book provides the project files for the legacy Turbo C++ 1.01 compiler — the same one that I've used in Chapter 1. You can run the generated executables in any variant of Windows.
You generate events by pressing appropriate keys on the keyboard (see the legend of recognized keypresses at the top of the output window in Figure 3.3.). The time bomb responds by printing every event it receives (the TICK event is represented as T) as well as every update to the LCD, which is shown in square brackets. The application terminates automatically when the bomb explodes. You can also quit the program at any time by pressing the Esc
key.
The majority of published state machine code presents state machines intimately intertwined with a specific concurrency model and a particular event-passing method. For example, embedded systems engineers3 Judging by 20 years of articles (1988–2008) published on the subject in Embedded Systems Design magazine (formerly Embedded Systems Programming). often present their state machines inside polling loops or interrupt service routines (ISRs) that extract events and event parameters directly from hardware registers or global variables. GUI programmers are typically more disciplined in this respect because the GUI system already provides a consistent interface, but then again GUI programmers seldom use state machines, as demonstrated in the Visual Basic Calculator example in Chapter 2.
However, it is far better to separate the state machine code from a particular concurrency model and to provide a flexible and uniform way of passing events with arbitrary parameters. Therefore, implementations in this chapter use a simple and generally applicable interface to a state machine.4 Because of the special nature, the object-oriented State design pattern uses a different interface for dispatching events. The interface I propose consists of just two functions: init()
, to trigger the top-level initial transition in a state machine, and dispatch()
, to dispatch an event to the state machine. In this simple model, a state machine is externally driven by invoking init()
once and dispatch()
repetitively, for each event.
To nail down the signature of the dispatch()
function, we need a uniform representation of events. Again, this is where the standard approaches vary the most. For example, the GUI systems, such as Microsoft Windows, provide only events with fixed sets of event parameters that are passed to the WinMain()
function and thus are not generally applicable outside the GUI domain (after all, the most complex event parameters that a GUI needs to handle are the parameters of the mouse-click event).
As described in Chapter 2, events consist really of two parts: the signal of the event conveys the type of the occurrence (such as arrival of the time tick), and event parameters convey the quantitative information about the occurrence (such as the fractional part of a second in the time tick event). In event-driven systems, event instances are frequently passed around, placed in event queues, and eventually consumed by state machines. Consequently, it is very convenient to represent events as event objects that combine the signal and the event parameters into one entity.
The following Event
structure represents event objects. The scalar data member sig
contains the signal information, which is an integer number that identifies the event, such as UP, DOWN, ARM, or TICK:
Note
Throughout this book I use the following standard exact-width integer types (WG14/N843 C99 Standard, Section 7.18.1.1) [ISO/IEC 9899:TC2]:
Exact Size Unsigned Signed 8 bits uint8_t
int8_t
16 bits uint16_t
int16_t
32 bits uint32_t
int32_t
If your (prestandard) compiler does not provide the
<stdint.h>
header file, you can alwaystypedef
the exact-width integer types using the standard C data types such assigned/unsigned char, short, int
andlong
.
You can add arbitrary event parameters to an event in the process of “derivation of structures” described in the sidebar “Single Inheritance in C” (Chapter 1, Section 1.6). For example, the following TickEvt
structure declares an event with the parameter fine_time
used in the TICK(fine_time)
event (see Figure 3.2(8)).
As shown in Figure 3.4, such nesting of structures always aligns the data member super
at the beginning of every instance of the derived structure. In particular, this alignment lets you treat a pointer to the derived TickEvt
structure as a pointer to the Event
base structure. Consequently, you can always safely pass a pointer to TickEvt
to any C function that expects a pointer to Event
.
With this representation of events, the signature of the dispatch()
function looks as follows:
The first argument ‘StateMachine *me
’ is the pointer to the state machine object. Different state machine implementation techniques will define the StateMachine
structure differently. The second argument ‘Event const *e
’ is the pointer to the event object, which might point to a structure derived from Event and thus might contain arbitrary event parameters (see Figure 3.4(B)). This interface becomes clearer when you see how it is used in the concrete implementation techniques.
Perhaps the most popular and straightforward technique of implementing state machines is the nested switch
statement, with a scalar state variable used as the discriminator in the first level of the switch
and the signal of the event used in the second level.
Listing 3.1 shows a typical implementation of the time bomb FSM from Figure 3.2. The explanation section immediately following the listing illuminates the interesting points.
Listing 3.1. Time bomb state machine implemented using the nested switch statement technique (see file bomb1.c)
(1)
enum BombSignals { /* all signals for the Bomb FSM */
(1)
/*....................................................................*/
(2)
enum BombStates { /* all states for the Bomb FSM */
(2)
/*.....................................................................*/
(4)
uint16_t sig; /* signal of the event */
(4)
/* add event parameters by derivation from the Event structure... */
(7)
uint8_t fine_time; /* the fine 1/10 s counter */
(7)
/*.....................................................................*/
(10)
uint8_t timeout; /* number of seconds till explosion */
(11)
uint8_t code; /* currently entered code to disarm the bomb */
(12)
uint8_t defuse; /* secret defuse code to disarm the bomb */
(13)
#define TRAN(target_) (me->state = (uint8_t)(target_))
(13)
/*....................................................................*/
(14)
void Bomb1_ctor(Bomb1 *me, uint8_t defuse) { /* the "constructor" */
(15)
me->defuse = defuse; /* the defuse code is assigned at instantiation */
(15)
/*.....................................................................*/
(17)
"/>me->timeout = INIT_TIMEOUT;/* timeout is initialized in initial tran. */
(18)
/*.....................................................................*/
(19)
void Bomb1_dispatch(Bomb1 *me, Event const *e) { /* dispatching */
(1) Event signals are typically represented as an enumeration.
(2) States are also typically represented as an enumeration.
(3) The Event
structure represents signal events without parameters.
(4) The scalar data member sig
holds the signal. Here it's declared as the C99-standard 16-bit unsigned integer with the dynamic range of 64K signals.
(5) The TickEvt
structure represents TICK events with the fine_time
parameter described in the explanation to Figure 3.2(8).
(6) The TickEvt
structure derives from Event
structure, as described in the Sidebar “Single Inheritance in C” in Chapter 1. By convention, I name the base structure member super
.
(7) The event parameter(s) are added after the member super
.
(8) The Bomb1
structure represents the time-bomb state machine implemented with the nested switch
statement technique.
(9) The data member state
is the scalar state variable in this implementation. Here it's declared as the C99-standard 8-bit unsigned integer with the dynamic range of 256 states. You can adjust it to suit your needs.
(10-12) The data members timeout, defuse
, and code
are the extended state variables used in the state diagram shown in Figure 3.2.
(13) The TRAN()
macro encapsulates the transition, which in this method consists of reassigning the state variable state
.
(14) The state machine “constructor” performs just a basic initialization but does not trigger the initial transition. In C, you need to call the “constructor” explicitly at the beginning of main()
.
(15) Here, the “constructor” initializes the secret defuse code, which is assigned to the bomb at instantiation.
(16) This is the init()
function of the generic state machine interface. Calling this function triggers the initial transition in the state machine.
(17) The initial transition initializes the me->timeout
extended state variable, as prescribed in the diagram in Figure 3.2(1).
(18) The initial transition changes the state to the “setting” state by means of the TRAN()
macro.
(19) This is the dispatch()
function of the generic state machine interface. Calling this function dispatches one event to the state machine.
(20) The first level of switch
statement discriminates based on the scalar state variable me->state
.
(21) Each state corresponds to one case
statement in the first level of the switch
.
(22) Within each state the second level of switch
discriminates based on the event signal e->sig
.
(23) For example, the internal transition UP is coded as a nested case
statement.
(24) The guard condition (see Figure 3.2(2)) is coded by means of the if
statement.
(25,26) The actions associated with the transition are coded directly.
(27) Handling of each event case must be terminated with the break
statement.
(28) A state transition is coded by reassigning the state variable, here achieved by the TRAN()
macro.
(29) Handling of each state case must be terminated with the break
statement.
(30,31) A regular transition with a guard is coded with an if
statement and TRAN()
macro.
(32) Events with parameters, such as the TICK event, require explicit casting from the generic base structure Event
to the specific derived structure TickEvt
, in this case.
(33) The choice pseudostate is coded as an if
statement that tests all the outgoing guards of the choice point.
The nested switch
statement implementation has the following consequences:
• It has a small memory footprint, since only one small scalar state variable is necessary to represent the current state of a state machine.
• It does not promote code reuse because all elements of a state machine must be coded specifically for the problem at hand.
• The whole state machine is coded as one monolithic function, which easily can grow too large.
• Event dispatching time is not constant but depends on the performance of the two levels of switch
statements, which degrade with increasing number of cases (typically as O(log n), where n is the number of cases).
• The implementation is not hierarchical. You could manually code entry/exit actions directly in every transition, but this would be prone to error and difficult to maintain in view of changes in the state machine topology. This is mainly because the code pertaining to one state (e.g., an entry action) would become distributed and repeated in many places (on every transition leading to this state).
• The latter property is not a problem for code-synthesizing tools, which often use a nested switch
statement type of implementation.
The variations of this method include eliminating the second level of the switch
, if the state machine handles only one type of event. For example, parser state machines often receive identical characters from the input stream. In addition, signal-processing state machines often receive identical time samples of the signal under control. The “Fly ‘n’ Shoot” game introduced in Chapter 1 provides an example of a simple switch-debouncing state machine coded with the switch
statement technique (see file <qp>qpcexamplescortex-m3dosiargamesp.c
).
Another common approach to implementing state machines is based on state table representation of a state machine. The most popular is the two-dimensional state table that lists events along the horizontal dimension and states along the vertical dimension. The contents of the cells are transitions represented as {action, next-state}
pairs. For example, Table 3.1
One of the most interesting aspects of the state-table approach is that it represents a state machine as a very regular data structure (the table). This allows writing a simple and generic piece of software called an event processor that can execute any state machine specified in the tabular form.
As shown in Figure 3.5, the generic event processor consists of the StateTable
structure that manages an external array of transitions and the Event
structure for derivation of events with parameters or is used as is for events without parameters. Additionally, the StateTable
structure has two functions associated with it. The init()
function triggers the initial transition, and dispatch()
dispatches an event to the state machine. The StateTable
structure is abstract, meaning that it is not intended for direct instantiation but rather only for derivation of concrete5 Concrete class is an OOP term and denotes a class that can be instantiated because it has no abstract (partially defined) operations or protected constructors. state machine structures, such as Bomb2
.
In this implementation variant, the state table contains just pointers to transition functions instead of {action, next-state}
pairs. This pushes the responsibility of changing the state to the transition function, but in the end is much more flexible because the transition function can evaluate guard conditions and change state only conditionally. Listing 3.2 shows the header file; Listing 3.3 shows the implementation of the generic event processor depicted in Figure 3.5.
Listing 3.2. Generic state-table event processor interface (file statetbl.h)
(1)
uint16_t sig; /* signal of the event */
(1)
/* add event parameters by derivation from the Event structure */
(3) typedef void (*Tran)(struct StateTableTag *me, Event const *e);
(10)
void StateTable_ctor(StateTable *me,
(10)
Tran const *table, uint8_t n_states, uint8_t n_signals,
(12)
void StateTable_dispatch(StateTable *me, Event const *e);/* dispatch method */
(13)
void StateTable_empty(StateTable *me, Event const *e); /* empty action */
(13)
/* macro for taking a state transition inside a transition function */
(14)
#define TRAN(target_) (((StateTable *)me)->state = (uint8_t)(target_))
Listing 3.3. Generic state-table event processor implementation (file statetbl.c)
(1)
/*......................................................................*/
(2)
void StateTable_ctor(StateTable *me,
(2)
Tran const *table, uint8_t n_states, uint8_t n_signals,
(3)
me->state = n_states; /* initialize state out of range */
(3)
/*......................................................................*/
(4)
(*me->initial)(me, (Event *)0); /* top-most initial transition */
(5)
assert(me->state < me->n_states); /* the initial tran. must change state */
(5)
/*......................................................................*/
(5)
void StateTable_dispatch(StateTable *me, Event const *e) {
(6)
assert(e->sig < me->n_signals); /* require the signal in range */
(9)
assert(me->state < me->n_states); /* ensure that state stays in range */
(9)
/*......................................................................*/
(9)
void StateTable_empty(StateTable *me, Event const *e) {
(9)
(void)me; /* void compiler warning about unused parameter */
(9)
(void)e; /* void compiler warning about unused parameter */
(1) The Event
structure represents signal events (see also Listing 3.1(3-4)).
(2) This forward declaration is used in the following definition of a pointer-to-function type.
(3) This typedef
defines Tran
type as a pointer to transition function that takes the pointer to the StateTable
struct and a pointer to the Event
struct as arguments and returns uint8_t
. The value returned from the transition function represents the next state for the state machine after executing the transition. The pivotal aspect of this design is that the transition functions can be used with respect to structures derived (inheriting) from the StateTable
.
(4-7) The StateTable
structure does not physically contain the state table but rather manages an arbitrary table state_table
of transitions with an arbitrary number of states n_states
and signals n_signals
.
(8) The data member state
is the scalar state variable in this implementation.
(9) The StateTable
structure also contains a pointer to the initial transition.
(10) The state table “constructor” performs just a basic initialization but does not trigger the initial transition. In C, you need to call the “constructor” explicitly at the beginning of main()
.
(11) This is the init()
function of the generic state machine interface. Calling this function triggers the initial transition in the state machine.
(12) This is the dispatch()
function of the generic state machine interface. Calling this function dispatches one event to the state machine.
(13) The StateTable_empty()
function is the default empty action useful for initializing the empty cells of the state table.
(14) The TRAN()
macro encapsulates the transition, which in this method consist of re-assigning the state-variable state
. Note the explicit cast (upcast) of the me
pointer, which typically points to a structure derived from StateTable
, rather than StateTable
directly.
(1) The event processor implementation uses assertions to prevent incorrect execution of the externally defined state machine. Here the standard assertions are used. See Section 6.7.3 in Chapter 6 for the implementation of customizable assertions in C and C++.
(2) The state table “constructor” initializes the state_table
pointer, the table geometry, and the initial transition.
(3) The state variable is initially set outside the valid range.
(4) The init()
function calls the initial transition via the pointer to transition function.
(5) The state variable must be in range after the initial transition (see also (3)).
(6) The signal of the event dispatched to the state machine must be in range.
(7) The transition function pointer corresponding to the current state and current event is obtained by indexing into the external state table array.
(8) The transition function is invoked via the pointer to transition function obtained in the previous step.
(9) The state variable must be in range after the transition.
The application-specific part of the implementation provides (1) enumerated signals and states, (2) the state machine structure derived from StateTable
that includes all the extended state variables, (3) all the transition functions, and (4) the state table initialized with the pointers to the transition functions. Listing 3.4 shows all these elements.
Listing 3.4. Time bomb state machine implemented using the state-table technique (file bomb2.c)
#include "statetbl.h" /* the generic state table event processor */
(9)
StateTable super; /* derive from the StateTable structure */
(10)
uint8_t timeout; /* number of seconds till explosion */
(11)
uint8_t defuse; /* secret defuse code to disarm the bomb */
(12)
uint8_t code; /* currently entered code to disarm the bomb */
(13)
void Bomb2_ctor(Bomb2 *me, uint8_t defuse); /* the "constructor" */
(14)
void Bomb2_initial (Bomb2 *me); /* the initial transition function */
(15)
void Bomb2_setting_UP (Bomb2 *me, Event const *e); /* transition function */
(15)
void Bomb2_setting_DOWN(Bomb2 *me, Event const *e);/* transition function */
(15)
void Bomb2_setting_ARM (Bomb2 *me, Event const *e); /* transition function */
(15)
void Bomb2_timing_UP (Bomb2 *me, Event const *e); /* transition function */
(15)
void Bomb2_timing_DOWN (Bomb2 *me, Event const *e); /* transition function */
(15)
void Bomb2_timing_ARM (Bomb2 *me, Event const *e); /* transition function */
(15)
void Bomb2_timing_TICK (Bomb2 *me, Event const *e); /* transition function */
(15)
/* the initial value of the timeout */
(15)
/*.................................................................*/
(16) static const Tran bomb2_state_table[MAX_STATE][MAX_SIG] = {
(16)
{ (Tran)&Bomb2_setting_UP, (Tran) &Bomb2_setting_DOWN,
(16)
(Tran)&Bomb2_setting_ARM, &StateTable_empty },
(16)
{ (Tran)&Bomb2_timing_UP, (Tran)&Bomb2_timing_DOWN,
(17)
StateTable_ctor(&me->super,
(18)
me->defuse = defuse; /* set the secret defuse code */
(18)
/*.................................................................*/
(20)
/*.................................................................*/
(20)
void Bomb2_setting_UP(Bomb2 *me, Event const *e) {
(20)
(void)e; /* avoid compiler warning about unused parameter */
(21)
BSP_display(me->timeout);
(21)
/*.................................................................*/
(21)
void Bomb2_setting_DOWN(Bomb2 *me, Event const *e) {
(21)
(void)e; /* avoid compiler warning about unused parameter */
(21)
BSP_display(me->timeout);
(21)
/*.................................................................*/
(21)
void Bomb2_setting_ARM(Bomb2 *me, Event const *e) {
(21)
(void)e; /* avoid compiler warning about unused parameter */
(22)
TRAN(TIMING_STATE); /* transition to "timing" */
(22)
/*.................................................................*/
(22)
void Bomb2_timing_UP(Bomb2 *me, Event const *e) {
(22)
(void)e; /* avoid compiler warning about unused parameter */
(22)
/*.................................................................*/
(22)
void Bomb2_timing_DOWN(Bomb2 *me, Event const *e) {
(22)
(void)e; /* avoid compiler warning about unused parameter */
(22)
/*.................................................................*/
(22)
void Bomb2_timing_ARM(Bomb2 *me, Event const *e) {
(22)
(void)e; /* avoid compiler warning about unused parameter */
(22)
if (me->code == me->defuse) {
(22)
TRAN(SETTING_STATE); /* transition to "setting" */
(22)
/*.................................................................*/
(1) Event signals are typically represented as an enumeration.
(2) The extra enumeration added at the end corresponds to the total number of signals, which you need to know to size the state table array.
(3) States are also typically represented as an enumeration.
(4) The extra enumeration added at the end corresponds to the total number of signals, which you need to know to size the state table array.
(5) The TickEvt
structure represents TICK events with the fine_time
parameter described in the explanation to Figure 3.2(8).
(6) The TickEvt
structure derives from Event
structure, as described in the Sidebar “Single Inheritance in C” in Chapter 1. By convention, I always name the base structure member super
.
(7) The event parameter(s) are added after the member super
.
(8) The Bomb2
structure represents the time-bomb state machine implemented with the state table technique.
(9) The Bomb2
structure derives from StateTable
structure, as described in the Sidebar “Single Inheritance in C” in Chapter 1. By convention, I always name the base structure member super
.
(10-12) The data members timeout, defuse
, and code
are the extended state variables used in the state diagram shown in Figure 3.2.
(13) The state machine “constructor” performs just the basic initialization, but does not trigger the initial transition. In C, you need to call the “constructor” explicitly at the beginning of main()
.
(14) The initial transition function performs the actions of the initial transition (see Figure 3.2(1)), and initializes the state variable to the default state.
(15) The transition functions are specified for each implemented state-signal combination. For example, Bomb2_setting_UP()
corresponds to transition UP in state “setting.”
(16) The state table array specifies the structure of the state machine. The table is known and initialized at compile time, so it can be declared const
. The table is initialized with the pointers to the Bomb2
transition functions. Typically, you need to explicitly cast these pointers to function on the Tran
type because they refer to Bomb2
subclass of StateTable
rather than directly to StateTable
.
(17) The sate table is passed to the StateTable
event processor constructor, along with the dimensions of the table and the initial transition.
(18) The Bomb “constructor” also initializes the secret defuse code, which is assigned to the bomb at instantiation.
(19) The initial transition initializes the me->timeout
extended state variable, as prescribed in the diagram in Figure 3.2(1).
(20) The initial transition changes the state to the “setting” state by means of the TRAN()
macro defined in the event processor interface (file statetbl.h
).
(21) The transition functions are responsible for testing the guards, which are implemented as if
statements.
(22) The transition functions are responsible for changing the current active state by means of the TRAN()
macro.
(23) Events with parameters, such as the TICK event, require explicit casting from the generic base structure Event
to the specific derived structure TickEvt
, in this case.
(24) The choice pseudostate is coded as an if
statement that tests all the outgoing guards of the choice point.
The state table implementation technique has the following consequences.
1 It maps directly to the highly regular state table representation of a state machine.
2 It requires the enumeration of states and signals that are used as indexes into the state table.
3 Because states and signals are used as indexes into an array, they must both be contiguous and start with zero.
4 It provides relatively good and deterministic performance for event dispatching (O(const), not taking into account action execution).
5 It promotes code reuse of the generic event processor, which is typically small.
6 It requires a large state table, which is typically sparse. However, because the state table is constant, it often can be stored in ROM rather than RAM.
7 It requires a complicated initialization of the state table that must implicitly match the enumerated states and signals. Manual maintenance of this initialization, in view of changes in the state machine topology, is tedious and prone to error. For instance, adding a new state requires adding and initializing a whole row in the state table.
Note
Because of the complex initialization and rapid growth of the state table, programmers often perceive adding new states or events as expensive. This perception often discourages programmers from evolving the state machine. Instead, they tend to misuse extended state variables and guard conditions.
8 It requires a large number of fine-granularity functions representing actions.
9 It typically relies heavily on pointers to functions when implemented in C/C++ (see Section 3.7.1) because state tables typically contain large numbers of such pointers to functions.
10 It is not hierarchical. Although the state table can be extended to implement state nesting, entry/exit actions, and transition guards, these extensions require hardcoding whole transition chains into transition action functions, which is prone to error and inflexible.
There seem to be two main variations on state table implementation in C/C++. Concrete state machines can either derive from the generic state table event processor (inheritance) or contain a state table processor (aggregation). The technique presented here falls into the inheritance category. However, the aggregation approach seems to be quite popular as well (e.g., see [Douglass 99, 01]). Aggregation introduces the indirection layer of a context class—that is, a structure containing the extended state variables on behalf of which the aggregated state table event processor executes actions. Inheritance eliminates this indirection because the StateTable
class plays the role of the context class (state machine class) simultaneously. In other words, by virtue of inheritance, every derived state machine (like Bomb2
) also simultaneously “is a” StateTable
.
The main shortcoming of the two-dimensional state-table representation is the difficulty of showing guard conditions and transitions leading to different states based on different guards, as indicated by the notes added to Table 3.1. Therefore, some authors use a one-dimensional state transition table, shown in Table 3.2
Table 3.2. One-dimensional state transition table for the time bomb
Current State | Event (Parameters) | [Guard] | Next State | Actions |
---|---|---|---|---|
setting | UP | [me->timeout < 60] | setting | ++me->timeout; BSP_display(me->timeout); |
DOWN | [me->timeout > 1] | setting | --me->timeout; BSP_display(me->timeout); | |
ARM | timing | me->code = 0; | ||
TICK | setting | |||
timing | UP | timing | me->code <<=1; me->code |= 1; | |
DOWN | timing | me->code <<= 1; | ||
ARM | [me->code == me->defuse] | setting | ||
TICK(fine_time) | [e->fine_time == 0] | choice | --me->timeout; BSP_display(me->timeout); | |
[me->timeout == 0] | final | BSP_boom(); | ||
[else] | timing |
In the direct implementation of the one-dimensional state table, the transitions are more complex objects that contain:
The object-oriented approach to implementing state machines is known as the State design pattern [Gamma+ 95]. The intent of the pattern is to make a state machine object appear to change its class at runtime as it transitions from state to state. An instance of the State pattern applied to the time-bomb state machine is shown as a UML class diagram6 Appendix B contains a quick summary of the UML notation, which includes class diagrams. in Figure 3.6.
The key idea in this pattern is to introduce an abstract class BombState
to represent the states of the time bomb. The BombState
declares an interface common to all states, where each operation corresponds to an event. Subclasses of BombState
, such as SettingState
and TimingState
, implement state-specific behavior by overriding the operations inherited from BombState
. For example, SettingState
handles the UP event in its own specific way by defining the SettingState::onUP()
operation. Adding new events requires adding new operations to the abstract BombState
class, and adding new states requires adding new subclasses of BombState
.
The context class Bomb3
maintains the state as a pointer to a subclass of BombState
(see the state
data member). Bomb3
also contains all the extended state variables that the time bomb uses, such as timeout, code,
and defuse
. The class Bomb3
provides an interface identical to the BombState
, that is, each handled event corresponds to an operation. The event-handler operations in Bomb3
delegate all state-specific requests to the current state object via the state
pointer. In this technique change of state corresponds to changing the current state object, which is accomplished in the context class operation tran()
.
Listing 3.5 shows a C++ implementation of the time-bomb state with the object-oriented State pattern. The C implementation is not provided because the pattern very heavily relies on polymorphism, which is not quite trivial to implement in C.
Listing 3.5. Time-bomb state machine implemented using the State design pattern (file bomb3.cpp)
(3)
virtual void onUP (Bomb3 *) const {}
(5)
class SettingState : public BombState {
(5)
virtual void onUP (Bomb3 *context) const;
(5)
virtual void onDOWN(Bomb3 *context) const;
(6)
class TimingState : public BombState {
(6)
virtual void onUP (Bomb3 *context) const;
(6)
virtual void onDOWN(Bomb3 *context) const;
(6)
virtual void onARM (Bomb3 *context) const;
(6)
virtual void onTICK(Bomb3 *context, uint8_t fine_time) const;
(10)
void onUP () { m_state->onUP (this); }
(11)
void onTICK(uint8_t fine_time) { m_state->onTICK (this, fine_time); }
(12)
void tran(BombState const *target) { m_state = target; }
(14)
uint8_t m_timeout; // number of seconds till explosion
(14)
uint8_t m_code; // currently entered code to disarm the bomb
(14)
uint8_t m_defuse; // secret defuse code to disarm the bomb
(18)
friend class TimingState;
(18)
//.................................................................
(22)
//.................................................................
(23)
if (context->m_timeout < 60) {
(23)
BSP_display(context->m_timeout);
(23)
void SettingState::onDOWN(Bomb3 *context) const {
(23)
if (context->m_timeout > 1) {
(23)
BSP_display(context->m_timeout);
(24)
context->tran(&Bomb3::timing); // transition to "timing"
(24)
//.................................................................
(24)
void TimingState::onUP(Bomb3 *context) const {
(24)
void TimingState::onDOWN(Bomb3 *context) const {
(24)
void TimingState::onARM(Bomb3 *context) const {
(24)
if (context->m_code == context->m_defuse) {
(24)
context->tran(&Bomb3::setting); // transition to "setting"
(24)
void TimingState::onTICK(Bomb3 *context, uint8_t fine_time) const {
(26)
if (context->m_timeout == 0) {
(1) The context class Bomb3
needs to be forward-declared because it is used in the signatures of the operations inside the state classes.
(2) The BombState
abstract class declares an interface common to all time-bomb states, where each operation corresponds to an event. The class provides default empty implementations for all event handlers.
(3) The onUP()
operation handles the UP event without parameters.
(4) The onTICK()
operation handles the TICK(fine_time)
event with a parameter. Note that the signature of the event operation contains strongly typed event parameters.
(5) The class SettingState
derives from the abstract BombState
and overrides all events handled in the “setting” state. Note that this state does not handle the TICK
event, so the SettingState
class defaults to the empty implementation inherited from the BombState
superclass.
(6) The class TimingState
derives from the abstract BombState
and overrides all events handled in the “timing” state.
(7) The context class Bomb3
keeps track of the current state and contains all extended state variables.
(8) The constructor initializes selected extended-state variables but does not take the initial transition.
(9) This is the init()
function of the generic state machine interface. Calling this function triggers the initial transition in the state machine.
(10) The context class Bomb3
duplicates the event interface from the abstract state class BombState
. All state-dependent behavior is delegated to the current state object.
Note
The standard State design pattern does not use the
dispatch()
method for dispatching events to the state machine. Instead, for every signal event, the context class provides a specific (type-safe) event handler operation.
(11) The signatures of event operations contain strongly typed event parameters.
(12) The private tran()
operation changes the state by reassigning the state variable.
(13) The state variable in this technique is a pointer to the subclass of the abstract state class BombState
.
(14) The context class Bomb3
contains also all extended-state variables.
(15,16) The state objects are static and constant members of the context class Bomb3
. Note that the state objects contain only operations but no data and therefore can be safely shared among all instances of the context class.
(17,18) The context class Bomb3
declares friendship with all state classes because the event-handler operations in the state classes must be able to access the private members of the context class.
(21) The initial transition performs the actions specified in the state diagram in Figure 3.2(1).
(22) The default state is specified by means of the tran()
operation.
(23) The guard condition is coded as an if
statement. Note that the state class must access the extended-state variables via the context
argument.
(24) The transition is achieved by calling the tran()
operation on behalf of the context state machine object.
(25) The event parameters are available directly to state classes because they are arguments of the event operations.
The object-oriented State design pattern has the following consequences:
• It relies heavily on polymorphism and requires an object-oriented language like C++.
• It partitions state-specific behavior and localizes it in separate classes.
• It makes state transitions efficient (reassigning one pointer).
• It provides very good performance for event dispatching through the late binding mechanism (O(const), not taking into account action execution). This performance is generally better than indexing into a state table plus invoking a method via a function pointer, as used in the state table technique. However, such performance is only possible because the selection of the appropriate event handler is not taken into account. Indeed, clients typically will use a switch
statement to perform such selections. (See the main()
function in bomb3.cpp.
)
• It allows you to customize the signature of each event handler. Event parameters are explicit, and the typing system of the language verifies the appropriate type of all parameters at compile time (e.g., onTICK()
takes a parameter of type uint8_t
).
• The implementation is memory efficient. If the concrete state objects don't have attributes (only operations), they can be shared (as in the Bomb3
example).
• It compromises the encapsulation of the context class, which typically requires granting friendship to all state classes.
• It enforces indirect access to the context's parameters from the methods of the concrete state subclasses (via the context
pointer).
• Adding states requires subclassing the abstract state class.
• Handling new events requires adding event handlers to the abstract state class interface.
• The event handlers are typically of fine granularity, as in the state table approach.
The State pattern can be augmented to support entry and exit actions to states. As shown in Figure 3.7, the changes include adding operations onEntry()
and onExit()
to the abstract state class BombState
. Additionally, as shown in the note to operation onTick(fine_time)
, each event handler in the context class must detect the state change and invoke the onExit()
operation to exit the source state and onEntry()
to enter the target state.
The standard State design pattern can also be simplified to provide the standard state machine interface consisting of operations init()
and dispatch()
with the event representation described in Section 3.2.1. A generic dispatch()
operation of the abstract state class handles all events in a state and thus becomes a generic state-handler operation. As shown in Figure 3.8, the abstract state class then also becomes generic since it no longer depends on specific event signatures. Additionally, each state handler must perform explicit demultiplexing of events (based on the signal), which typically involves one level of switch
statement, as shown in the note to the SettingState::dispatch()
operation.
In previous sections, I presented the three most popular techniques for implementing FSMs. From my experience, though, none of these techniques in its pure form is truly optimal. However, one particular combination of these techniques repeatedly proved to be the most succinct and efficient implementation of the traditional nonhierarchical FSMs. This technique is part of the QEP event processor that I introduced in Chapter 1. The QEP FSM implementation is object-based, but unlike the State pattern, does not depend on polymorphism and is easy to implement in C.
The QEP support for the basic FSMs combines elements from the nested switch
statement, state table, and the simplified State design pattern, but it also adds some original ideas. The design is based on a generic event processor (the QEP), similar in functionality to the state-table event processor discussed in Section 3.4.1. The novelty of the QEP design comes from mapping states directly to state-handler functions that handle all events in the state they represent. As shown in Figure 3.9, the central element of the QEP event processor is the QFsm
structure that keeps track of the current state by means of a pointer to a state-handler function. The QFsm
structure also provides the standard state machine interface functions init()
and dispatch()
. The QFsm
structure is abstract, meaning that it is not intended for direct instantiation but rather only for derivation of concrete state machine structures, such as Bomb4
. The derived state machine structure adds its own extended state variables such as timeout, code
, and defuse
, as well as all state-handler functions.
The QEP event processor supports both simple FSMs and hierarchical state machines (HSMs), which I will discuss in Chapter 4. Even though the basic FSMs are a strict subset of HSMs, the QEP provides a separate FSM implementation as an optimization compared to the full-featured HSM. You can use this optimization for performance-critical portions of your code, such as inside interrupt service routines or device drivers. Furthermore, you can use FSMs in extremely resource-constrained embedded systems that simply cannot fit the full-featured HSMs. The QEP support for FSMs requires typically about 120 bytes of code (ROM). For comparison, the support for HSMs requires about 600 bytes of code space for the hierarchical event processor on ARM Cortex-M3. Both FSM and HSM require just one pointer to function in RAM per state machine.
Listings 3.6 and 3.7 show fragments of the QEP files that pertain to the FSM implementation. The header files are located in the directory <qp>qpcinclude
, and the implementation files are found in the directory <qp>qpcqepsource
.
(1) The structure QEvent
represents events in QEP. Arbitrary event parameters can be added in the process of derivation of structures (see also Section 3.2.1).
(2) The scalar data member sig
holds the signal on an event. The data type QSignal
is an unsigned integer that can be configured to be 1 byte, 2 bytes, or 4 bytes wide.
(3) The byte-wide member dynamic_
is used by the QF real-time framework to manage dynamically allocated events. The QEP event processor does not use this data member and you can ignore it for now. I'll explain dynamic event allocation in Chapters 6 and 7.
(4) This typedef
defines QState
as a byte that conveys the status of the event handling to the event processor (see also lines (11–13)).
(5) This typedef
defines QStateHandler
type as a pointer to state-handler function that takes the pointer to a generic state machine and a pointer to QEvent
as arguments and returns QState
. The pivotal aspect of this design is that the state-handler functions signature can be used with respect to structures derived (inheriting) from QFsm
.
(6) The structure QFsm
is the base for derivation of state machine structures.
(7) The data member state
is a pointer to a state-handler function. This is the state variable in this implementation.
(8) The “constructor” function-like macro initializes the state variable to the initial-pseudostate function that defines the initial transition. Note that the initial transition is not actually executed at this point.
(9) This is the init()
function of the generic state machine interface. Calling this function triggers the initial transition in the state machine.
(10) This is the dispatch()
function of the generic state machine interface. Calling this function dispatches one event to the state machine.
(11-13) These constants define the status returned from state-handler functions to the event processor.
(14) A state-handler function returns the macro Q_HANDLED()
whenever it handles the current event.
(15) A state-handler function returns the macro Q_IGNORED()
whenever it ignores (does not handle) the current event.
(16) The Q_TRAN()
macro encapsulates the transition, which in this state machine implementation technique consist of reassigning the state variable state
. The Q_TRAN()
macro is defined using the comma expression. A comma expression is evaluated from left to right, whereas the type and value of the whole expression is the right-most operand. The right-most operand is in this case the status of the operation (transition), which is returned from the state-handler function. The pivotal aspect of this design is that the Q_TRAN()
macro can be used with respect to structures derived (inheriting) from QFsm
, which in C requires explicit casting (upcasting) to the QFsm
base structure (see the sidebar “Single Inheritance in C” in Chapter 1).
(17) The QEP event processor reserves these few lowest signals for internal use.
(18) The signal Q_USER_SIG
is the first signal available for the users. In other words, the user signals must necessarily be offset from zero by Q_USER_SIG
to avoid overlapping the reserved QEP signals.
Note
QEP maintains internally a constant array of reserved events
QEP_reservedEvt_[]
. This array is indexed by the reserved signals enumerated in Listing 3.6(17).
(3) The QFsm_dispatch()
function saves the current state in a temporary stack variable s
.
(4) The current state-handler function is invoked via the pointer to function.
(5) If the status returned from the state-handler function indicates that a transition has been taken (via the Q_TRAN()
macro), then . . .
(6) The source of the transition is exited by sending the reserved signal Q_EXIT_SIG
to the source state handler.
(7) The target of the transition (the new current state) is entered by sending the reserved signal Q_ENTRY_SIG
to its state handler.
The application-specific part of the implementation provides the elements shown below the dashed line in Figure 3.9. These elements are (1) events with parameters derived from the QEvent
structure, (2) the state machine structure derived from QFsm
that includes all the extended state variables, and (3) all the state-handler functions. Listing 3.8 shows the application-level code.
Listing 3.8. Time-bomb state machine implemented using the optimal FSM technique (file bomb4.c)
(1)
#include "qep_port.h" /* the port of the QEP event processor */
(10)
uint8_t timeout; /* number of seconds till explosion */
(11)
uint8_t code; /* currently entered code to disarm the bomb */
(12)
uint8_t defuse; /* secret defuse code to disarm the bomb */
(16) QState Bomb4_timing (Bomb4 *me, QEvent const *e);
(16)
/*-----------------------------------------------------------------------*/
(16)
/* the initial value of the timeout */
(16)
/*....................................................................*/
(18)
me->defuse = defuse; /* the defuse code is assigned at instantiation */
(18)
/*....................................................................*/
(20) return Q_TRAN(&Bomb4_setting);
(20)
/*....................................................................*/
(26) return Q_TRAN(&Bomb4_timing); /* transition to "timing" */
(27)
/*....................................................................*/
(30)
if (me->code == me->defuse) {
(30) return Q_TRAN(&Bomb4_setting);
(30)
if (((TickEvt const *)e)->fine_time == 0) {
(30)
BSP_display(me->timeout);
Note
The time-bomb state machine from Figure 3.2 has been slightly modified for the QEP FSM implementation to demonstrate the usage of entry actions. The action of clearing of the defuse code (
me->code = 0
) has been moved from the transition ARM in state “setting,” to entry action in state “timing.”
(1) Every application C file that uses the QP framework must include the qp_port.h
header file. This header file contains the specific adaptation of QP to the given processor, operating system, and compiler, which is called a port—in this case, the “qp_port.h
” header file, located in the directory <qp>qpcports80x86dos cpp101l
.
(2) The application also includes the board support package.
(4) The user signals must be offset by Q_USER_SIG
, to avoid overlapping the reserved signals.
(5) The TickEvt
structure represents TICK events with the fine_time
parameter described in the explanation to Figure 3.2(8).
(6) The TickEvt
structure derives from QEvent
structure, as described in the sidebar “Single Inheritance in C” in Chapter 1. By convention, I name the base structure member super
.
(7) The event parameter(s) are added after the member super
.
(8) The Bomb4
structure represents the time bomb state machine implemented with the QEP event processor.
(9) The Bomb4
structure derives from QFsm
structure, as described in the sidebar “Single Inheritance in C” in Chapter 1. By convention, I always name the base structure member super
.
(10-12) The data members timeout, defuse
, and code
are the extended state variables used in the state diagram shown in Figure 3.2.
(13) The state machine “constructor” performs just the basic initialization but does not trigger the initial transition. In C, you need to call the “constructor” explicitly at the beginning of main()
.
(14) The initial transition function performs the actions of the initial transition (see Figure 3.1(1)), and initializes the state variable to the default state.
(15,16) The state-handler functions are specified for each state.
(17) The constructor of the Bomb4
state machine is responsible for invoking the constructor of the base structure QFsm_ctor()
, which requires the initial pseudostate handler.
(18) The Bomb4
constructor can also initialize any extended state variables.
(19) The initial transition initializes the me->timeout
extended state variable, as prescribed in the diagram in Figure 3.2(1).
(20) The initial transition designates “setting” as the default state by means of the Q_TRAN()
macro returned to the event processor (file qep.h
).
(21) This state-handler function corresponds to the state “setting.”
(22) Each state-handler function is typically structured as a switch
statement that discriminates based on the signal of the event.
(23) Each event is handled in a separate case
labeled with the enumerated signal of the event.
(25) After handling of an event, the state-handler function returns Q_HANDLED()
to the event processor.
(26) A state transition is coded by means of the Q_TRAN()
macro (see Listing 3.6(16)).
(27) The final return statement is reached only when no case statements have handled the event. The state-handler function returns Q_IGNORED()
to the event processor.
Note
The
QFsm_dispatch()
function shown in Listing 3.7 cares only whether a state transition has been taken but does not check to see whether the event has been handled or ignored. However, Listing 3.7 does not show the software tracing instrumentation built into the QEP event processor, which indeed makes use of each status value reported by state-handler functions. I discuss the software-tracing instrumentation in Chapter 11.
(28) The entry action is coded as a response to the reserved event Q_ENTRY_SIG
, which the event processor dispatches to the state-handler function when the state needs to be entered (see Listing 3.6(17)).
(30) As all other case statements, entry actions are terminated with “return Q_HANDLED()
” macro.
The QEP FSM implementation has the following consequences:
• It partitions state-specific behavior and localizes it in separate state-handler functions. These functions have just about the right granularity—neither too fine (as the action functions in the state table or event operations in the State pattern) nor monolithic (as in the nested switch
statement technique).
• It provides direct and efficient access to extended state variables from state-handler functions (via the “me
” pointer) and does not require compromising the encapsulation of the state machine structure.
• It has a small footprint in RAM because only one state variable (a pointer to function) is necessary to represent a state machine instance (see Listing 3.6(7)). No data space is required for states.
• It promotes code reuse of a small and generic QEP event processor that takes typically around 120 bytes of code space (ROM) for the non-hierarchical FSM implementation on ARM Cortex-M3.
• It makes state transitions efficient (the Q_TRAN()
macro reassigns just one pointer to function).
• It provides good performance for event dispatching by eliminating one level of switch
from the nested switch
statement technique and replacing it with a very efficient pointer to function dereferencing. In typical implementations, state handlers still need one level of a switch
statement to discriminate events based on the signal, which has performance dependent on the number of cases (typically O(log n), where n is the number of cases). The switch
statement can be replaced by a one-dimensional lookup table in selected (time-critical) state handlers.
• It is scalable, flexible, maintainable, and traceable. It is easy to add both states and events, as well as to change state machine topology, even late in the development cycle, because every state machine element is represented in the code exactly once.
• It is not hierarchical, but can be extended to include state hierarchy without sacrificing its good characteristics, as described in Chapter 4.
Except for the nested switch
statement, all other state machine implementation techniques in C/C++ rely heavily on pointers to functions. I also intentionally include here the object-oriented State pattern because it too ultimately resolves event-handler operations via virtual tables that are nothing else than call tables of pointers to functions.
To understand why pointers to functions are so popular in implementing state machines, it is very instructive to step down to the machine code level. Listing 3.9 shows disassembled instructions of a state-handler function called via a pointer in the QEP event processor (see Listing 3.7(4)).
Listing 3.9. Disassembled machine code for a function call via a pointer to function (x86 instruction set, 16-bit real mode, Turbo C++ compiler)
As shown in boldface in Listing 3.9, the actual function call via a pointer takes just one machine instruction! The four preceding instructions push the function arguments to the stack (the “me
” pointer and the event pointer “e
”) and are needed no matter what technique you use. As it turns out, a pointer to function maps directly to the architecture of most CPUs and results in unbeatably small and fast code.
The point to remember from this discussion is that pointers to functions are the fastest mechanism for implementing state machines in C/C++. State machines are the “killer applications” for pointers to functions.
Throwing and catching exceptions in C++ is fundamentally incompatible with the run-to-completion (RTC) semantics of state machines. An exception thrown somewhere in the middle of an RTC step typically corrupts a state machine by leaving the extended-state variables inconsistent with the main state variable or with each other. Therefore, in general, an RTC step of a state machine must be considered as one indivisible transaction that either atomically succeeds or entirely fails.
Note that the stack-unwinding process occurring when a thrown exception propagates up the call stack has much less value in the event-driven systems than traditional data-processing programs. As described in Chapter 2, event-driven systems rely much less on representing the context in the call tree and stack variables and instead capture the context in nonstack variables. The problem with exceptions is that they are specialized for cleaning up the stack but know nothing about the static data.
Therefore, you should be wary of the C++ exception handling in state machines, or more generally, in event-driven systems. If you cannot avoid the mechanism altogether (e.g., you rely on a library that throws exceptions), you should be careful to catch all exceptions in the same RTC step and before a thrown exception can cause any inconsistencies. This rule, of course, largely defeats the benefits of throwing exceptions in the first place.
However, state machines offer a better, language-independent way of handling exceptions. A state machine associated with an event-driven subsystem can represent all conditions of the subsystem, including fault conditions. Instead of throwing an exception, an action should generate an exception event, which then triggers a state-based exception handling. Section 6.7.4 in Chapter 6 describes the state-based exception handling in more detail.
As described in Chapter 2, guard conditions and choice pseudostates are elements of flowcharts that the UML statecharts simply reuse. As such, these elements are not specific to hierarchical state machines and can be applied equally well in classical flat-state machines.
If you know how to code a flowchart, you already know how to implement guards and choice pseudostates. Flowcharts map easily to plain structured code and are therefore straightforward to implement in those techniques that give you explicit choice of the target of a state transition, such as the nested switch
statement, the State design pattern, and the QP FSM implementation. Conditional execution is harder to use in the traditional state-table representation because the rigidly structured state table explicitly specifies the targets of state transitions. The solution presented in Section 3.4.1 solves this problem by removing the “next-state” from the table and pushing the responsibility for changing states into the action functions.
A guard specified in the UML expression [guard]/action
… maps simply to the if
statement if (guard()) { action(); …}
. A choice pseudostate has one incoming transition segment and many outgoing segments guarded by nonoverlapping guard expressions. This construct maps simply to chained if–else
statements: if (guard1()) { action1(); } else if (guard2()) { action2(); }
and so on.
The traditional nonhierarchical FSMs can also reap the benefits of a guaranteed initialization of the state context through entry actions and a guaranteed cleanup in the exit actions. The lack of hierarchy vastly simplifies the problem, but at the same time it makes the feature much less powerful.
One way of implementing entry and exit actions is to dispatch reserved signals (e.g., Q_ENTRY_SIG
and Q_EXIT_SIG
) to the state machine. As shown in Listing 3.7, upon detecting a state transition, the state machine dispatch()
operation sends the Q_EXIT_SIG
signal to the source state and then sends the Q_ENTRY_SIG
signal to the target state.
The standard implementation techniques and their variations discussed in this chapter can be freely mixed and matched to provide a continuum of possible trade-offs. Indeed, most of the implementations of state machines that you can find in the literature seem to be variations or combinations of the three fundamental techniques: the nested switch
statement, the state table, and the object-oriented State design pattern. In this chapter, I provided concrete, executable code, and for each fundamental technique, I discussed the consequences of its use as well as some of the most common variations.
One particular combination of techniques, which is part of the QP framework, deserves special attention because it offers an optimal combination of good performance and a small memory footprint. As you will see in Chapter 4, it can be extended to hierarchical state machines (HSMs).
In all techniques, state machines tend to eliminate many conditional statements from your code. By crisply defining the state of the system at any given time, state machines require that you test only one variable (the state variable) instead of many variables to determine the mode of operation (recall the Visual Basic calculator example from Chapter 2). In all but the most basic approach of the nested switch
statement, even this explicit test of the state variable disappears as a conditional statement. This coding aspect is similar to the effect of polymorphism in OOP, which eliminates many tests based on the type of the object and replaces them with more efficient (and extensible) late binding.
3.16.162.198