Reference Manual For QP/C++ 8.1.5
Reference Manual For QP/C++ 8.1.5
Design Viewpoint: Algorithms.
Purpose
The Algorithm Viewpoint addresses the design concerns related to computational logic, control flow, data transformations, and decision-making mechanisms within the QP/C++ framework component. It provides a precise, implementation-oriented description of how the software operates, ensuring that the logic is correct, efficient, deterministic, analyzable, and traceable to requirements.
Design Concerns
The Algorithm Viewpoint frames the following concerns:
The QP::QHsm class (see Figure SDS-CLS [13]) implements the state machine strategy optimized for "manual coding", but it is also supported by the QM modeling tool↑. This section describes the internal design of the QP::QHsm class, with the particular focus on the algorithms used for dispatching events to hierarchical state machines.
Design view: QHsm event dispatching
Description
Dispatching events to a hierarchical state machine requires implementing the UML state nesting semantics, that is, propagating the event through all the levels of state nesting until it is handled or reaches the top state. To explain this process, it is convenient to represent the state nesting in a tree-structure, which is illustrated in SDS-SM-TRAN.
To understand the general transition processing steps, consider the transition TRIG from state s1 to s2 in SDS-SM-TRAN while state s11 is active. The QHsm dispatch() operation must then perform the following steps:
Step [1] scan the state hierarchy, starting from the current state (s11), and check which state handles the current event (TRIG)
Step [2] if regular transition, exit the current state configuration to the transition source. This is the implicit transition segment labeled A in SDS-SM-TRAN.
Step [3] take the transition by exiting the source state configuration and entering the target state configuration. This is the implicit transition segment labeled B in SDS-SM-TRAN and its complexity depends on the transition topology.
Step [4] enter the target (s2) by recursively executing any nested initial transitions, if present (e.g., s2->s22). This is the transition segment labeled C in SDS-SM-TRAN.
Algorithm Step [1]
This portion is implemented as a loop, which calls the state-handler functions as long as they return the "superstate" status. The series of visited states is stored in an automatic array path[], as shown in SDS-SM-XPATH. NOTE: the depth of the path[] array limits the number of state nesting levels in QHsm-type state machines. This maximum nesting is also the natural limit for testing such state machines.
Algorithm Step [2]
This portion is implemented as a loop that over the path[] array to exit all states from the current state to transition source.
Algorithm Step [3]
This portion requires detecting the transition topology. The optimization criterion used in the transition algorithm is to minimize the number of invocations of state-handler functions, in particular the invocations with the reserved "empty" event, which serve only for eliciting the superstate of a given state handler. The strategy is to order the possible source-target state combinations in such a way that the information about the state hierarchy gained from earlier steps can be used in later states.
Algorithm Step [3a]
First, the algorithm attempts to identify one of the simple transitions depicted in Figure SDS-SM-STRAN. These also happen to be the most frequently used kinds of transitions. NOTE: this step is implemented as a separate QHsm operation tran_simple_() to reduce the cyclomatic complexity of the already complex dispatch() operation required for systematic capability (see [SDS_QP_MOD_01]).
Decision/truth table [3a]
The following decision/truth table specifies the criteria for selecting the simple transition type A-D. The notation used in the table is as follows:
| s==t | s==sup(t) | sup(s)==sup(t) | sup(s)==t | transition type |
|---|---|---|---|---|
| TRUE | x | x | x | A |
| FALSE | TRUE | x | x | B |
| FALSE | FALSE | TRUE | x | C |
| FALSE | FALSE | FALSE | TRUE | D |
| FALSE | FALSE | FALSE | FALSE | Step [3b] |
Algorithm Step [3b]
If the transition turns out to be not simple, the algorithm attempts one of the complex transitions depicted in Figure SDS-SM-CTRAN. Unlike the simple transitions, complex transitions require iterative checking the state hierarchy (indicated by ... in the diagram). NOTE: this step is implemented as a separate QHsm operation tran_complex_() to reduce the cyclomatic complexity of the already complex dispatch() operation required for systematic capability (see [SDS_QP_MOD_01]).
Decision/truth table [3b]
The following decision/truth table specifies the criteria for selecting the simple transition type A-D. The notation used in the table is as follows:
| s==sup...(t) | sup(s)==sup...(t) | sup...(s)==sup...(t) | transition type |
|---|---|---|---|
| TRUE | x | x | E |
| FALSE | TRUE | x | F |
| FALSE | FALSE | TRUE | G, H |
| FALSE | FALSE | FALSE | FAULT (see NOTE) |
Algorithm Step [4]
Per the UML semantics, recursive entry to the target state configuration requires executing state entry actions into the target state configuration in the opposite order to the natural navigability through the QHsm state hierarchy. The applied algorithm reuses the path[] array to first store the sequence of target superstates in the natural order, and then "play it back" in the reverse order, as shown in Figure SDS-SM-EPATH. NOTE: this step is implemented as a separate QHsm operation enter_target_() to reduce the cyclomatic complexity of the already complex dispatch() operation required for systematic capability (see [SDS_QP_MOD_01]).
Backward Traceability
Forward Traceability
The QP::QMsm class (see Figure SDS-CLS [14]) implements the state machine strategy optimized for "automatic code generation" (see SRS_QP_REQ_221), which requires the QM modeling tool↑. This section describes the internal design of the QP::QMsm class, with the particular focus on the algorithms used for dispatching events to hierarchical state machines.
Design view: QMsm Event Dispatching
Description
Dispatching events to QMsm-style state machines can be more efficient than the QHsm dispatching because the determination of the transition chains (exit from source and entry to the target state configuration) can be performed at code-generation time rather than runtime. To store such information, QMsm-style state machine add new data structures that are initialized at the code-generation time (see also QMsm Design View).
State representation
A QMsm-style state machine represents each state as a conglomerate of following elements:
Transition-action tables
Additionally, each state transition is associated with a transition-action table that stores:
Algorithm Steps
The QMsm dispatch() operation must then perform the following steps:
Step [1] scan the state hierarchy, starting from the current state, and check which state handles the current event
Step [2] if regular transition, exit the current state configuration to the transition source. This is the implicit transition segment labeled A in SDS-SM-TRAN.
Step [3] take the transition by executing the transition-action table associated with the transition. This is the implicit transition segment labeled B in SDS-SM-TRAN.
Step [4] if transition to history, enter the recorded history state dynamically (the history state is not known at code generation time, so a static transition-action table cannot be generated).
Backward Traceability
Forward Traceability