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->timeoutextended 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->timeoutvariable 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->timeoutvariable and displays it on the LCD.(4) The transition ARM to state “timing” clears the
me->codeextended 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->codevariable and inserts the 1-bit into the least-significant-bit position.(6) The internal transition DOWN in state “timing” just shifts the
me->codevariable and leaves the least-significant-bit at zero.(7) If the entered defuse code
me->codematches exactly the secret codeme->defusegiven 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_timewith the TICK event. Thefine_timeparameter 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 theme->timeoutvariable 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->timeoutvariable is zero, the transition segment is executed that calls theBSP_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_tint8_t16 bits uint16_tint16_t32 bits uint32_tint32_tIf your (prestandard) compiler does not provide the
<stdint.h>header file, you can alwaystypedefthe exact-width integer types using the standard C data types such assigned/unsigned char, short, intandlong.
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
Eventstructure represents signal events without parameters.(4) The scalar data member
sigholds the signal. Here it's declared as the C99-standard 16-bit unsigned integer with the dynamic range of 64K signals.(5) The
TickEvtstructure represents TICK events with thefine_timeparameter described in the explanation to Figure 3.2(8).(6) The
TickEvtstructure derives fromEventstructure, as described in the Sidebar “Single Inheritance in C” in Chapter 1. By convention, I name the base structure membersuper.(7) The event parameter(s) are added after the member
super.(8) The
Bomb1structure represents the time-bomb state machine implemented with the nestedswitchstatement technique.(9) The data member
stateis 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, andcodeare 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 variablestate.(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->timeoutextended 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
switchstatement discriminates based on the scalar state variableme->state.(21) Each state corresponds to one
casestatement in the first level of theswitch.(22) Within each state the second level of
switchdiscriminates based on the event signale->sig.(23) For example, the internal transition UP is coded as a nested
casestatement.(24) The guard condition (see Figure 3.2(2)) is coded by means of the
ifstatement.(25,26) The actions associated with the transition are coded directly.
(27) Handling of each event case must be terminated with the
breakstatement.(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
breakstatement.(30,31) A regular transition with a guard is coded with an
ifstatement andTRAN()macro.(32) Events with parameters, such as the TICK event, require explicit casting from the generic base structure
Eventto the specific derived structureTickEvt, in this case.(33) The choice pseudostate is coded as an
ifstatement 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
switchstatements, 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
switchstatement 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
Eventstructure 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
typedefdefinesTrantype as a pointer to transition function that takes the pointer to theStateTablestruct and a pointer to theEventstruct as arguments and returnsuint8_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 theStateTable.(4-7) The
StateTablestructure does not physically contain the state table but rather manages an arbitrary tablestate_tableof transitions with an arbitrary number of statesn_statesand signalsn_signals.(8) The data member
stateis the scalar state variable in this implementation.(9) The
StateTablestructure 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-variablestate. Note the explicit cast (upcast) of themepointer, which typically points to a structure derived fromStateTable, rather thanStateTabledirectly.
(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_tablepointer, 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
TickEvtstructure represents TICK events with thefine_timeparameter described in the explanation to Figure 3.2(8).(6) The
TickEvtstructure derives fromEventstructure, as described in the Sidebar “Single Inheritance in C” in Chapter 1. By convention, I always name the base structure membersuper.(7) The event parameter(s) are added after the member
super.(8) The
Bomb2structure represents the time-bomb state machine implemented with the state table technique.(9) The
Bomb2structure derives fromStateTablestructure, as described in the Sidebar “Single Inheritance in C” in Chapter 1. By convention, I always name the base structure membersuper.(10-12) The data members
timeout, defuse, andcodeare 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 theBomb2transition functions. Typically, you need to explicitly cast these pointers to function on theTrantype because they refer toBomb2subclass ofStateTablerather than directly toStateTable.(17) The sate table is passed to the
StateTableevent 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->timeoutextended 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 (filestatetbl.h).(21) The transition functions are responsible for testing the guards, which are implemented as
ifstatements.(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
Eventto the specific derived structureTickEvt, in this case.(24) The choice pseudostate is coded as an
ifstatement 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.
![Object-oriented State design pattern applied to the time-bomb state machine [Gamma+ 95].](http://imgdetail.ebookreading.net/system_admin/2/9780750687065/9780750687065__practical-uml-statecharts__9780750687065__graphics__B9780750687065000039_gr6.jpg)
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
Bomb3needs to be forward-declared because it is used in the signatures of the operations inside the state classes.(2) The
BombStateabstract 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 theTICK(fine_time)event with a parameter. Note that the signature of the event operation contains strongly typed event parameters.(5) The class
SettingStatederives from the abstractBombStateand overrides all events handled in the “setting” state. Note that this state does not handle theTICKevent, so theSettingStateclass defaults to the empty implementation inherited from theBombStatesuperclass.(6) The class
TimingStatederives from the abstractBombStateand overrides all events handled in the “timing” state.(7) The context class
Bomb3keeps 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
Bomb3duplicates the event interface from the abstract state classBombState. 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
Bomb3contains 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
Bomb3declares 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
ifstatement. Note that the state class must access the extended-state variables via thecontextargument.(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
switchstatement to perform such selections. (See themain()function inbomb3.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 typeuint8_t).• The implementation is memory efficient. If the concrete state objects don't have attributes (only operations), they can be shared (as in the
Bomb3example).• 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
contextpointer).• 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
QEventrepresents 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
sigholds the signal on an event. The data typeQSignalis 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
typedefdefinesQStateas a byte that conveys the status of the event handling to the event processor (see also lines (11–13)).(5) This
typedefdefinesQStateHandlertype as a pointer to state-handler function that takes the pointer to a generic state machine and a pointer toQEventas arguments and returnsQState. The pivotal aspect of this design is that the state-handler functions signature can be used with respect to structures derived (inheriting) fromQFsm.(6) The structure
QFsmis the base for derivation of state machine structures.(7) The data member
stateis 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 variablestate. TheQ_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 theQ_TRAN()macro can be used with respect to structures derived (inheriting) fromQFsm, which in C requires explicit casting (upcasting) to theQFsmbase 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_SIGis the first signal available for the users. In other words, the user signals must necessarily be offset from zero byQ_USER_SIGto 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 variables.(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_SIGto the source state handler.(7) The target of the transition (the new current state) is entered by sending the reserved signal
Q_ENTRY_SIGto 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.hheader 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
TickEvtstructure represents TICK events with thefine_timeparameter described in the explanation to Figure 3.2(8).(6) The
TickEvtstructure derives fromQEventstructure, as described in the sidebar “Single Inheritance in C” in Chapter 1. By convention, I name the base structure membersuper.(7) The event parameter(s) are added after the member
super.(8) The
Bomb4structure represents the time bomb state machine implemented with the QEP event processor.(9) The
Bomb4structure derives fromQFsmstructure, as described in the sidebar “Single Inheritance in C” in Chapter 1. By convention, I always name the base structure membersuper.(10-12) The data members
timeout, defuse, andcodeare 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
Bomb4state machine is responsible for invoking the constructor of the base structureQFsm_ctor(), which requires the initial pseudostate handler.(18) The
Bomb4constructor can also initialize any extended state variables.(19) The initial transition initializes the
me->timeoutextended 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 (fileqep.h).(21) This state-handler function corresponds to the state “setting.”
(22) Each state-handler function is typically structured as a
switchstatement that discriminates based on the signal of the event.(23) Each event is handled in a separate
caselabeled 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
switchstatement 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
switchfrom the nestedswitchstatement technique and replacing it with a very efficient pointer to function dereferencing. In typical implementations, state handlers still need one level of aswitchstatement 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). Theswitchstatement 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.