Hierarchical State Machines
Hierarchical State Machines (D. Harel) [4] are a common way to model behaviour of a software modul. Bran Selic [5] has extended the ideas towards real time modeling, introducing actors, ports and other components. GoF [2] have first proposed an implementation. M. Samek [1] has elaborated on the implementation. Here, I propose an idea to implement the change of states using the placement new operator. Nico Manske has made experiments with this idea in his Bachelorthesis [3].
Motivation
Software may be decomposed in modules which are characterized by their input-output behaviour. These modules are commonly modelled by a hierarchical state machine. Typically such modules (so-called context-classes) consist of a set of public functions (signals) which represent their input, and a set of actions, which represent the output. States my be contained in one another in a hierarchical way for easier modeling. State machines with this property are called hierarchical state machines (HSM). Extended state variables may be read and written by the state machine. HSMs with this property are called HSM with extended state variables. A typical beginners implementation would consist of nested switch-case statements. However, this implementation leeds to confusion when extending or verifying code. The GoF (Gang of Four: Gamma, Vlissides, Helm, Johnson: design pattern) state pattern uses a separate class for each state. The state hierarchy in the HSM is implemented with means of a derivation/generalisation hierarchy which resembles the hierarchy of the states. Change of state is done by using the placement new operator in the proposed minimalistic implementation. It´s fast, clear, and has minimal memory footprint.
Figure 1: State diagram with two internal states and a superstate. For clarity there is only one signalA. There is one choice (decision) point. The code sample implements this state machine.
Implementation
This minimalistic state machine consists of three states (State, StateA, StateB), whereas StateA and StateB are contained in State. For clarity there is just a single signal called signalA. The classes which represent the states are inner classes. Change of states is done by placement operator new.
Implementation with extended state variables
This example shows, how an external data class may be accessed through the state machine. In this examples I put the data physically inside the context class. This allows the context class to be copyable without having to define copy constructor and assignment operator. This may be useful if the objects are kept inside an std container, e.g. a vector (a vectors push_back will copy the object).
Figure 2: Class diagram of the state machine. The context class contains data and state as values (composition). State also has a pointer to data (aggregation) to be able to manipulate it. The code shows how the placement new operator is used to exchange the state object inside the context class.
References
[1] Miro Samek: Practical Statecharts in C/C++. CMP Books, imprint of CMP Media LLC, 2002 [2] E.Gamma, R.Johnson, R.Helm, J.Vlissides; Design Pattern; Prentice Hall 1994 [3] Nico Manske; Eine einfache, schnelle und speicherschonende Technologie zur Implementation des Zustands-Entwurfsmusters; Bachelorarbeit HAW Hamburg 2006 [4] David Harel; Statecharts: A visual formalism for complex systems; Science of computer programming 8; 1987 [5] Bran Selic, Garth Gullekson, Paul T. Ward: Real-Time Object-Oriented Modeling, New York, John Wiley & Sons Inc, 1994