7. Coding Hierarchical State Machines

This QP-nano Tutorial is adapted from Chapter 1 of Practical UML Statecharts in C/C++, Second Edition
by Miro Samek, the founder and president of Quantum Leaps, LLC.

Prev: 6. Signals, Events, and Active Objects
Next: 8. Using the Built-in Real-Time Kernels

Contrary to widespread misconceptions, you don't need big design automation tools to translate hierarchical state machines (UML statecharts) into efficient and highly maintainable C or C++. This section explains how to hand-code the Ship state machine from Figure 5-2 with QP-nano. Once you know how to code this state machine, you know how to code them all.

The source code for the Ship state machine is found in the file ship.c located either in the DOS version or the ARM-Cortex version of the "Fly 'n' Shoot" game. I break the explanation of this file into three steps.

7.1 Step 1: Defining the Ship Structure

In the first step you define the Ship data structure. Just like in case of events, you use inheritance to derive the Ship structure from the framework structure QActive (see the sidebar Encapsulation and Single Inheritance in C). Creating this inheritance relationship ties the Ship structure to the QF framework. The main responsibility of the QActive base structure is to store the information about the current active state of the state machine, as well as the event queue and priority level of the Ship active object. In fact, QActive itself derives from a simpler QEP structure QHsm that represents just the current active state of a hierarchical state machine. On top of that information, almost every state machine must also store other "extended-state" information. For example, the Ship object is responsible for maintaining the Ship position as well as the score accumulated in the game. You supply this additional information by means of data members enlisted after the base structure member super, as shown in Listing 7-1.

Listing 7-1 Deriving the Ship structure in file ship.c.

 (1) #include "qpn_port.h"
 (2) #include "bsp.h"
 (3) #include "game.h"

     /* local objects -----------------------------------------------------------*/
 (4) typedef struct ShipTag {
 (5)     QActive super;                              /* extend the QActive class */
         uint8_t x;
         uint8_t y;
         uint8_t exp_ctr;
         uint16_t score;
     } Ship;                                           /* the Ship active object */

 (6) static QState Ship_initial  (Ship *me);
 (7) static QState Ship_active   (Ship *me);
     static QState Ship_parked   (Ship *me);
     static QState Ship_flying   (Ship *me);
     static QState Ship_exploding(Ship *me);

     /* global objects ----------------------------------------------------------*/
 (8) Ship AO_Ship;

(1) Every application-level C-file that uses the QP platform must include the qp_port.h header file.

(2) The bsp.h header file contains the interface to the Board Support Package.

(3) The game.h header file contains the declarations of events and other facilities shared among the components of the application
(see Listing 6-1).

(4) This structure defines the Ship active object.

(5) The Ship active object structure derives from the framework structure QActive, as described in Section .

(6) The Ship_initial() function defines the top-most initial transition in the Ship state machine. The initial pseudostate handler has signature identical to the regular state handler function.

(7) The state-handler functions in QP-nano also don't take the event parameter. (In QP-nano, the current event is embedded in the state machine.) As in the full-version QP, a state handler function in QP-nano returns a pointer the superstate handler function.

Note:: I use a simple naming convention to strengthen the association between the structures and the functions designed to operate on these structures. First, I name the functions by combining the typedef'ed structure name with the name of the operation (e.g., Ship_active). Second, I always place the pointer to the structure as the first argument of the associated function and I always name this argument me (e.g., Ship_active(Ship *me, ...)).

(8) In this line I allocate the global AO_Ship active object. Please note that actual structure definition for the Ship active object is accessible only locally at the file scope of the ship.c file.

Note:: QP-nano assumes that all global or static variables without explicit initialization value are initialized to zero upon the system startup, which is a requirement of the ANSI-C standard. You should make sure that your startup code clears the static variables data section (a.k.a. Block Started by Symbol section or BSS) before calling main().

7.2 Step 2: Initializing the State Machine

The state machine initialization is divided into the following two steps for increased flexibility and better control of the initialization timeline:

The state machine "constructor"; and
The top-most initial transition.

The state machine "constructor", such as Ship_ctor(), intentionally does not execute the top-most initial transition defined in the initial pseudostate because at that time some vital objects can be missing and critical hardware might not be properly initialized yet3. Instead, the state machine "constructor" merely puts the state machine in the initial pseudostate. Later, the user code must trigger the top-most initial transition explicitly, which happens actually inside the function QActive_start() (see Listing 3-11(18-20)). Listing 7-2 shows the instantiation (the "constructor" function) and initialization (the initial pseudostate) of the Ship active object.

Listing 7-2 Instantiation and Initialization of the Ship active object in ship.c.

 (1) void Ship_ctor(void) {
 (2)     Ship *me = &AO_Ship;
 (3)     QActive_ctor(&me->super, (QStateHandler)&Ship_initial);
 (4)     me->x = GAME_SHIP_X;
 (5)     me->y = GAME_SHIP_Y;
     }

     /* HSM definition ----------------------------------------------------------*/
 (6) QState Ship_initial(Ship *me) {
 (7)     return Q_TRAN(&Ship_active);             /* top-most initial transition */
     }

(1) The global function Ship_ctor() is prototyped in game.h and called at the beginning of main().

(2) The "me" pointer points to the statically allocated Ship object (see Listing 7-1(6)).

(3) Every derived structure is responsible for initializing the part inherited from the base structure. The "constructor" QActive_ctor() puts the state machine in the initial pseudostate &Ship_initial. (see Listing 6-1(5)).

(4-5) The Ship position is initialized.

(6) The Ship_initial() function defines the top-most initial transition in the Ship state machine (see Figure 5-2(1)).

(7) The initial state "active" is specified by invoking the QEP-nano macro Q_TRAN().

7.3 Step 3: Defining State Handler Functions

In the last step, you actually code the Ship state machine by implementing one state at a time as a state handler function. To determine what elements belong the any given state handler function, you follow around the state's boundary in the diagram (Figure 5-2). You need to implement all transitions originating at the boundary, any entry and exit actions defined in the state, as well as all internal transitions enlisted directly in the state. Additionally, if there is an initial transition embedded directly in the state, you need to implement it as well.

Take for example the state "flying" shown in Figure 5-2. This state has an entry action and two transitions originating at its boundary: HIT_WALL and HIT_MINE(type), as well as three internal transitions TIME_TICK, PLAYER_TRIGGER, and DESTROYED_MINE(score). The "flying" state nests inside the "active" superstate. Listing 7-3 shows two state handler functions of the Ship state machine from Figure 5-2. The state handler functions correspond to the states "active" and "flying", respectively. The explanation section immediately following the listing highlights the important implementation techniques.

Listing 7-3 State handler functions for states "active" and "flying" in ship.c.

     QState Ship_active(Ship *me) {
 (1)     switch (Q_SIG(me)) {
             case Q_INIT_SIG: {                     /* nested initial transition */
 (2)             return Q_TRAN(&Ship_parked);
             }
             case PLAYER_SHIP_MOVE_SIG: {
 (3)             me->x = (uint8_t)Q_PAR(me);
 (4)             me->y = (uint8_t)(Q_PAR(me) >> 8);
 (5)             return Q_HANDLED();
             }
         }
 (6)     return Q_SUPER(&QHsm_top);
     }
     /*..........................................................................*/
     QState Ship_flying(Ship *me) {
         switch (Q_SIG(me)) {
             case Q_ENTRY_SIG: {
                 me->score = 0;                               /* reset the score */
 (7)             QActive_post((QActive *)&AO_Tunnel, SCORE_SIG, me->score);
                 return Q_HANDLED();
             }
             case TIME_TICK_SIG: {
                 /* tell the Tunnel to draw the Ship and test for hits */
 (8)             QActive_post((QActive *)&AO_Tunnel, SHIP_IMG_SIG,
                              ((QParam)SHIP_BMP << 16)
                              | (QParam)me->x
                              | ((QParam)me->y << 8));

                 ++me->score;  /* increment the score for surviving another tick */
                 if ((me->score % 10) == 0) {           /* is the score "round"? */
                     QActive_post((QActive *)&AO_Tunnel, SCORE_SIG, me->score);
                 }
                 return Q_HANDLED();
             }
             case PLAYER_TRIGGER_SIG: {                   /* trigger the Missile */
                 QActive_post((QActive *)&AO_Missile, MISSILE_FIRE_SIG,
                              (QParam)me->x
                              | (((QParam)me->y + SHIP_HEIGHT - 1) << 8));
                 return Q_HANDLED();
             }
             case DESTROYED_MINE_SIG: {
                 me->score += Q_PAR(me);
                 /* the score will be sent to the Tunnel by the next TIME_TICK */
                 return Q_HANDLED();
             }
             case HIT_WALL_SIG:
             case HIT_MINE_SIG: {
 (9)             return Q_TRAN(&Ship_exploding);
             }
         }
(10)     return Q_SUPER(&Ship_active);
     }

(1) Every state handler is structured as a switch statement that discriminates based on the signal of the event, which in QP-nano is obtained by the macro Q_SIG(me).

(2) You designate the target of a nested initial transition with the Q_TRAN() macro.

Note:: The macro Q_TRAN() must always follow the return statement.

(3-4) You access the data members of the Ship state machine via the "me" parameter of the state handler function. You access the event parameters via the Q_PAR(me) macro. Please note that in this case actually two logical event parameters are e from the scalar QP-nano parameter. The x coordinate of the Ship is sent in the least-significant byte, and the y coordinate in the next byte.

Note:: Each event can have as many event parameters as you can squeeze into the available bits.

(5) You terminate the case statement with return Q_HANDLED(), which informs QEP-nano that the initial transition has been handled.

(6) The final return from a state handler function designates the superstate of that state, which is exactly the same as in the full-version QP. QEP-nano provides the "top" state as a state handler function QHsm_top(), and therefore the Ship_active() state handler returns the pointer &QHsm_top. (see the Ship state diagram in Figure 5-2)

(7) The function QActive_post() posts the specified event signal and parameter directly to the recipient active object. Direct event posting is the only event delivery mechanism supported in QP-nano.

Note:: You use QActive_post() function at the task-level. You should never call QActive_postISR() from the task-level.

(8) The event posting demonstrates how to combine several logical event parameters into the single scalar parameter managed by QP-nano. Of course, you must be careful not to overflow the dynamic range of the QP-nano parameter configured with the Q_PARAM_SIZE macro (see Listing 3-2(1)).

(9) You designate the target of a transition with the Q_TRAN() macro.

(10) The state "flying" (see Figure 5-2) nests in the state "active", so the state handler Ship_flying() returns the pointer &Ship_active.

When implementing state handler functions you need to keep in mind that the QEP-nano event processor is in charge here rather than your code. QEP-nano will invoke a state handler function for various reasons: for hierarchical event processing, for execution of entry and exit actions, for triggering initial transitions, or even just to elicit the superstate of a given state handler. Therefore, you should not assume that a state handler would be invoked only for processing signals enlisted in the case statements. You should avoid any code outside the switch statement, especially code that would have side effects.

Prev: 6. Signals, Events, and Active Objects
Next: 8. Using the Built-in Real-Time Kernels