¿Hay un patrón de implementación de máquina de estado típico?
https://stackoverflow.com/questions/133214
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Necesitamos implementar una máquina de estado simple en C .
¿Es una declaración de cambio estándar la mejor manera de hacerlo?
Tenemos un estado actual (estado) y un desencadenante para la transición.
switch(state)
{
case STATE_1:
state = DoState1(transition);
break;
case STATE_2:
state = DoState2(transition);
break;
}
...
DoState2(int transition)
{
// Do State Work
...
if(transition == FROM_STATE_2) {
// New state when doing STATE 2 -> STATE 2
}
if(transition == FROM_STATE_1) {
// New State when moving STATE 1 -> STATE 2
}
return new_state;
}
¿Hay una mejor manera para máquinas de estado simples
EDITAR: Para C ++, creo que la Statechart de Boost Podría ser el camino a seguir. Sin embargo, no ayuda con C. Vamos a concentrarnos en el caso de uso de C.
Solución
Prefiero utilizar un enfoque basado en tablas para la mayoría de las máquinas de estado:
typedef enum { STATE_INITIAL, STATE_FOO, STATE_BAR, NUM_STATES } state_t;
typedef struct instance_data instance_data_t;
typedef state_t state_func_t( instance_data_t *data );
state_t do_state_initial( instance_data_t *data );
state_t do_state_foo( instance_data_t *data );
state_t do_state_bar( instance_data_t *data );
state_func_t* const state_table[ NUM_STATES ] = {
do_state_initial, do_state_foo, do_state_bar
};
state_t run_state( state_t cur_state, instance_data_t *data ) {
return state_table[ cur_state ]( data );
};
int main( void ) {
state_t cur_state = STATE_INITIAL;
instance_data_t data;
while ( 1 ) {
cur_state = run_state( cur_state, &data );
// do other program logic, run other state machines, etc
}
}
Por supuesto, esto puede extenderse para admitir múltiples máquinas de estado, etc. Las acciones de transición también se pueden adaptar:
typedef void transition_func_t( instance_data_t *data );
void do_initial_to_foo( instance_data_t *data );
void do_foo_to_bar( instance_data_t *data );
void do_bar_to_initial( instance_data_t *data );
void do_bar_to_foo( instance_data_t *data );
void do_bar_to_bar( instance_data_t *data );
transition_func_t * const transition_table[ NUM_STATES ][ NUM_STATES ] = {
{ NULL, do_initial_to_foo, NULL },
{ NULL, NULL, do_foo_to_bar },
{ do_bar_to_initial, do_bar_to_foo, do_bar_to_bar }
};
state_t run_state( state_t cur_state, instance_data_t *data ) {
state_t new_state = state_table[ cur_state ]( data );
transition_func_t *transition =
transition_table[ cur_state ][ new_state ];
if ( transition ) {
transition( data );
}
return new_state;
};
El enfoque basado en tablas es más fácil de mantener y extender y más simple de asignar a los diagramas de estado.
Otros consejos
¡Es posible que haya visto mi respuesta a otra pregunta C donde mencioné FSM! Así es como lo hago:
FSM {
STATE(x) {
...
NEXTSTATE(y);
}
STATE(y) {
...
if (x == 0)
NEXTSTATE(y);
else
NEXTSTATE(x);
}
}
Con las siguientes macros definidas
#define FSM
#define STATE(x) s_##x :
#define NEXTSTATE(x) goto s_##x
Esto puede ser modificado para adaptarse al caso específico. Por ejemplo, puede tener un archivo FSMFILE en el que desea controlar su FSM, por lo que podría incorporar la acción de leer el siguiente carácter en la macro en sí:
#define FSM
#define STATE(x) s_##x : FSMCHR = fgetc(FSMFILE); sn_##x :
#define NEXTSTATE(x) goto s_##x
#define NEXTSTATE_NR(x) goto sn_##x
ahora tienes dos tipos de transiciones: una va a un estado y lee un nuevo carácter, la otra va a un estado sin consumir ninguna entrada.
También puede automatizar el manejo de EOF con algo como:
#define STATE(x) s_##x : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
goto sx_endfsm;\
sn_##x :
#define ENDFSM sx_endfsm:
Lo bueno de este enfoque es que puede traducir directamente un diagrama de estado que dibuje en código de trabajo y, a la inversa, puede dibujar fácilmente un diagrama de estado a partir del código.
En otras técnicas para implementar FSM, la estructura de las transiciones está enterrada en estructuras de control (mientras que, si, cambia ...) y se controla mediante el valor de las variables (típicamente una variable state ) y puede ser una tarea compleja para relacionar el diagrama agradable con un código complicado.
Aprendí esta técnica de un artículo publicado en el gran " Lenguaje informático " revista que, lamentablemente, ya no se publica.
También he usado el enfoque de tabla. Sin embargo, hay gastos generales. ¿Por qué almacenar una segunda lista de punteros? Una función en C sin el () es un puntero constante. Así que puedes hacer:
struct state;
typedef void (*state_func_t)( struct state* );
typedef struct state
{
state_func_t function;
// other stateful data
} state_t;
void do_state_initial( state_t* );
void do_state_foo( state_t* );
void do_state_bar( state_t* );
void run_state( state_t* i ) {
i->function(i);
};
int main( void ) {
state_t state = { do_state_initial };
while ( 1 ) {
run_state( state );
// do other program logic, run other state machines, etc
}
}
Por supuesto, dependiendo de su factor de miedo (es decir, seguridad frente a velocidad), es posible que desee verificar los indicadores válidos. Para máquinas de estado mayores de tres o más estados, el enfoque anterior debe ser menos instrucciones que un interruptor equivalente o un enfoque de tabla. Incluso podría macro-ize como:
#define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_))
También, siento por el ejemplo del OP, que hay una simplificación que debe hacerse al pensar / diseñar una máquina de estados. No creo que el estado de transición deba usarse para la lógica. Cada función de estado debe ser capaz de desempeñar su rol dado sin un conocimiento explícito de los estados pasados. Básicamente diseñas cómo hacer la transición del estado en el que te encuentras a otro estado.
Finalmente, no comience el diseño de una máquina de estado basada en funcional límites, use subfunciones para eso. En su lugar, divida los estados en función de cuándo tendrá que esperar a que ocurra algo antes de poder continuar. Esto ayudará a minimizar la cantidad de veces que tiene que ejecutar la máquina de estado antes de obtener un resultado. Esto puede ser importante al escribir funciones de E / S o interrumpir manejadores.
También, algunas ventajas y desventajas de la clásica declaración de cambio:
Pros:
- está en el idioma, por lo que está documentado y claro
- los estados se definen donde se llaman
- puede ejecutar múltiples estados en una llamada de función
- el código común a todos los estados se puede ejecutar antes y después de la instrucción de cambio
Contras:
- puede ejecutar múltiples estados en una llamada de función El código
- común a todos los estados se puede ejecutar antes y después de la declaración de cambio
- la implementación del interruptor puede ser lenta
Tenga en cuenta los dos atributos que son pro y con. Creo que el cambio permite la oportunidad de compartir demasiado entre los estados, y la interdependencia entre los estados puede volverse inmanejable. Sin embargo, para un pequeño número de estados, puede ser el más legible y fácil de mantener.
Para una máquina de estado simple, solo use una instrucción de cambio y un tipo de enumeración para su estado. Realice sus transiciones dentro de la instrucción switch en función de su entrada. En un programa real, obviamente cambiarías el " si (entrada) " para comprobar sus puntos de transición. Espero que esto ayude.
typedef enum
{
STATE_1 = 0,
STATE_2,
STATE_3
} my_state_t;
my_state_t state = STATE_1;
void foo(char input)
{
...
switch(state)
{
case STATE_1:
if(input)
state = STATE_2;
break;
case STATE_2:
if(input)
state = STATE_3;
else
state = STATE_1;
break;
case STATE_3:
...
break;
}
...
}
también está la cuadrícula lógica que es más mantenible a medida que la máquina de estados se hace más grande
En UML de Martin Fowler destilado , afirma (sin juego de palabras) en el Capítulo 10 State Machine Diagramas (énfasis mío):
Un diagrama de estado se puede implementar de tres formas principales: interruptor anidado , el patrón de estado y tablas de estado .
Usemos un ejemplo simplificado de los estados de la pantalla de un teléfono móvil:
interruptor anidado
Fowler dio un ejemplo de código C #, pero lo he adaptado a mi ejemplo.
public void HandleEvent(PhoneEvent anEvent) {
switch (CurrentState) {
case PhoneState.ScreenOff:
switch (anEvent) {
case PhoneEvent.PressButton:
if (powerLow) { // guard condition
DisplayLowPowerMessage(); // action
// CurrentState = PhoneState.ScreenOff;
} else {
CurrentState = PhoneState.ScreenOn;
}
break;
case PhoneEvent.PlugPower:
CurrentState = PhoneState.ScreenCharging;
break;
}
break;
case PhoneState.ScreenOn:
switch (anEvent) {
case PhoneEvent.PressButton:
CurrentState = PhoneState.ScreenOff;
break;
case PhoneEvent.PlugPower:
CurrentState = PhoneState.ScreenCharging;
break;
}
break;
case PhoneState.ScreenCharging:
switch (anEvent) {
case PhoneEvent.UnplugPower:
CurrentState = PhoneState.ScreenOff;
break;
}
break;
}
}
Patrón de estado
Aquí hay una implementación de mi ejemplo con el patrón de estado de GoF:
Tablas de estado
Tomando inspiración de Fowler, aquí hay una tabla para mi ejemplo:
Source State Target State Event Guard Action -------------------------------------------------------------------------------------- ScreenOff ScreenOff pressButton powerLow displayLowPowerMessage ScreenOff ScreenOn pressButton !powerLow ScreenOn ScreenOff pressButton ScreenOff ScreenCharging plugPower ScreenOn ScreenCharging plugPower ScreenCharging ScreenOff unplugPower
Comparación
El interruptor anidado mantiene toda la lógica en un solo lugar, pero el código puede ser difícil de leer cuando hay muchos estados y transiciones. Posiblemente sea más seguro y más fácil de validar que los otros enfoques (sin polimorfismo ni interpretación).
La implementación del patrón de estado potencialmente extiende la lógica a varias clases separadas, lo que puede hacer que la comprensión en su totalidad sea un problema. Por otro lado, las clases pequeñas son fáciles de entender por separado. El diseño es particularmente frágil si cambia el comportamiento agregando o eliminando transiciones, ya que son métodos en la jerarquía y podría haber muchos cambios en el código. Si vive según el principio de diseño de las interfaces pequeñas, verá que este patrón realmente no funciona tan bien. Sin embargo, si la máquina de estado es estable, dichos cambios no serán necesarios.
El enfoque de tablas de estado requiere escribir algún tipo de intérprete para el contenido (esto podría ser más fácil si tiene reflejo en el lenguaje que está usando), lo que podría ser mucho trabajo por adelantado. Como señala Fowler, si su tabla está separada de su código, puede modificar el comportamiento de su software sin recompilar. Sin embargo, esto tiene algunas implicaciones de seguridad; el software se comporta en función del contenido de un archivo externo.
Editar (no realmente para lenguaje C)
También hay un enfoque de interfaz fluida (también conocido como Lenguaje Específico del Dominio interno), que probablemente sea facilitado por lenguajes que tienen funciones de primera clase . La biblioteca Stateless existe y ese blog muestra un ejemplo sencillo con código. Se discute una implementación de Java (antes de Java8) . También me mostraron un ejemplo de Python en GitHub .
Para casos simples, puede cambiar su método de estilo. Lo que he encontrado que funciona bien en el pasado es lidiar con las transiciones también:
static int current_state; // should always hold current state -- and probably be an enum or something
void state_leave(int new_state) {
// do processing on what it means to enter the new state
// which might be dependent on the current state
}
void state_enter(int new_state) {
// do processing on what is means to leave the current atate
// might be dependent on the new state
current_state = new_state;
}
void state_process() {
// switch statement to handle current state
}
No sé nada acerca de la biblioteca boost, pero este tipo de enfoque es muy simple, no requiere ninguna dependencia externa y es fácil de implementar.
switch () es una forma potente y estándar de implementar máquinas de estado en C, pero puede disminuir la capacidad de mantenimiento si tiene una gran cantidad de estados. Otro método común es utilizar punteros de función para almacenar el siguiente estado. Este sencillo ejemplo implementa un flip-flop set / reset:
/* Implement each state as a function with the same prototype */
void state_one(int set, int reset);
void state_two(int set, int reset);
/* Store a pointer to the next state */
void (*next_state)(int set, int reset) = state_one;
/* Users should call next_state(set, reset). This could
also be wrapped by a real function that validated input
and dealt with output rather than calling the function
pointer directly. */
/* State one transitions to state one if set is true */
void state_one(int set, int reset) {
if(set)
next_state = state_two;
}
/* State two transitions to state one if reset is true */
void state_two(int set, int reset) {
if(reset)
next_state = state_one;
}
Encontré una implementación C muy suave de Moore FSM en el curso de sistemas embebidos edx.org - Shape the World UTAustinX - UT.6.02x, capítulo 10, por Jonathan Valvano y Ramesh Yerraballi ...
struct State {
unsigned long Out; // 6-bit pattern to output
unsigned long Time; // delay in 10ms units
unsigned long Next[4]; // next state for inputs 0,1,2,3
};
typedef const struct State STyp;
//this example has 4 states, defining constants/symbols using #define
#define goN 0
#define waitN 1
#define goE 2
#define waitE 3
//this is the full FSM logic coded into one large array of output values, delays,
//and next states (indexed by values of the inputs)
STyp FSM[4]={
{0x21,3000,{goN,waitN,goN,waitN}},
{0x22, 500,{goE,goE,goE,goE}},
{0x0C,3000,{goE,goE,waitE,waitE}},
{0x14, 500,{goN,goN,goN,goN}}};
unsigned long currentState; // index to the current state
//super simple controller follows
int main(void){ volatile unsigned long delay;
//embedded micro-controller configuration omitteed [...]
currentState = goN;
while(1){
LIGHTS = FSM[currentState].Out; // set outputs lines (from FSM table)
SysTick_Wait10ms(FSM[currentState].Time);
currentState = FSM[currentState].Next[INPUT_SENSORS];
}
}
Es posible que desee ver el software del generador FSM libero . Desde un lenguaje de descripción de estado y / o un editor de diagramas de estado (Windows) puede generar código para C, C ++, Java y muchos otros ... además de buena documentación y diagramas. Fuente y binarios de iMatix
Este artículo es bueno para el patrón de estado (aunque es C ++, no específicamente C).
Si puede poner sus manos en el libro " Head First Design Patterns " ;, la explicación y el ejemplo son muy claros.
Uno de mis patrones favoritos es el patrón de diseño de estado. Responda o se comporte de manera diferente al mismo conjunto de entradas dado.
Uno de los problemas con el uso de declaraciones de cambio / caso para máquinas de estado es que a medida que crea más estados, el cambio / casos se vuelve más difícil / difícil de leer / mantener, promueve el código de espagueti no organizado y cada vez más difícil de cambiar sin romper algo. Me parece que el uso de patrones de diseño me ayuda a organizar mejor mis datos, que es el punto central de la abstracción.
En lugar de diseñar su código de estado en torno al estado del que proviene, en su lugar, estructure su código para que registre el estado cuando ingrese un nuevo estado. De esa manera, efectivamente obtiene un registro de su estado anterior. Me gusta la respuesta de @ JoshPetit, y he llevado su solución un paso más allá, tomada directamente del libro GoF:
stateCtxt.h:
#define STATE (void *)
typedef enum fsmSignal
{
eEnter =0,
eNormal,
eExit
}FsmSignalT;
typedef struct fsm
{
FsmSignalT signal;
// StateT is an enum that you can define any which way you want
StateT currentState;
}FsmT;
extern int STATECTXT_Init(void);
/* optionally allow client context to set the target state */
extern STATECTXT_Set(StateT stateID);
extern void STATECTXT_Handle(void *pvEvent);
stateCtxt.c:
#include "stateCtxt.h"
#include "statehandlers.h"
typedef STATE (*pfnStateT)(FsmSignalT signal, void *pvEvent);
static FsmT fsm;
static pfnStateT UsbState ;
int STATECTXT_Init(void)
{
UsbState = State1;
fsm.signal = eEnter;
// use an enum for better maintainability
fsm.currentState = '1';
(*UsbState)( &fsm, pvEvent);
return 0;
}
static void ChangeState( FsmT *pFsm, pfnStateT targetState )
{
// Check to see if the state has changed
if (targetState != NULL)
{
// Call current state's exit event
pFsm->signal = eExit;
STATE dummyState = (*UsbState)( pFsm, pvEvent);
// Update the State Machine structure
UsbState = targetState ;
// Call the new state's enter event
pFsm->signal = eEnter;
dummyState = (*UsbState)( pFsm, pvEvent);
}
}
void STATECTXT_Handle(void *pvEvent)
{
pfnStateT newState;
if (UsbState != NULL)
{
fsm.signal = eNormal;
newState = (*UsbState)( &fsm, pvEvent );
ChangeState( &fsm, newState );
}
}
void STATECTXT_Set(StateT stateID)
{
prevState = UsbState;
switch (stateID)
{
case '1':
ChangeState( State1 );
break;
case '2':
ChangeState( State2);
break;
case '3':
ChangeState( State3);
break;
}
}
statehandlers.h:
/* define state handlers */
extern STATE State1(void);
extern STATE State2(void);
extern STATE State3(void);
statehandlers.c:
#include "stateCtxt.h:"
/* Define behaviour to given set of inputs */
STATE State1(FsmT *fsm, void *pvEvent)
{
STATE nextState;
/* do some state specific behaviours
* here
*/
/* fsm->currentState currently contains the previous state
* just before it gets updated, so you can implement behaviours
* which depend on previous state here
*/
fsm->currentState = '1';
/* Now, specify the next state
* to transition to, or return null if you're still waiting for
* more stuff to process.
*/
switch (fsm->signal)
{
case eEnter:
nextState = State2;
break;
case eNormal:
nextState = null;
break;
case eExit:
nextState = State2;
break;
}
return nextState;
}
STATE State3(FsmT *fsm, void *pvEvent)
{
/* do some state specific behaviours
* here
*/
fsm->currentState = '2';
/* Now, specify the next state
* to transition to
*/
return State1;
}
STATE State2(FsmT *fsm, void *pvEvent)
{
/* do some state specific behaviours
* here
*/
fsm->currentState = '3';
/* Now, specify the next state
* to transition to
*/
return State3;
}
Para la mayoría de las máquinas de estado, esp. Máquinas de estado finito, cada estado sabrá cuál debería ser su próximo estado y los criterios para la transición a su próximo estado. Para diseños de estado suelto, este puede no ser el caso, de ahí la opción de exponer la API para estados en transición. Si desea más abstracción, cada controlador de estado se puede separar en su propio archivo, que es equivalente a los controladores de estado concretos en el libro de GoF. Si su diseño es simple con solo unos pocos estados, entonces stateCtxt.c y statehandlers.c se pueden combinar en un solo archivo para simplificar.
En mi experiencia, usar la instrucción 'switch' es la forma estándar de manejar múltiples estados posibles. Aunque estoy seguro de que está pasando un valor de transición al procesamiento por estado. Pensé que el punto central de una máquina de estados era que cada estado realizaba una sola acción. Luego, la siguiente acción / entrada determina en qué nuevo estado se realizará la transición. Por lo tanto, hubiera esperado que cada función de procesamiento de estado realizara inmediatamente lo que sea fijo para ingresar al estado y luego decidir si se necesita la transición a otro estado.
Hay un libro titulado Gráficos de estado prácticos en C / C ++ . Sin embargo, es manera demasiado pesado para lo que necesitamos.
Para el compilador que admite __COUNTER__ , puede usarlos para mashines de estado simples (pero grandes).
#define START 0
#define END 1000
int run = 1;
state = START;
while(run)
{
switch (state)
{
case __COUNTER__:
//do something
state++;
break;
case __COUNTER__:
//do something
if (input)
state = END;
else
state++;
break;
.
.
.
case __COUNTER__:
//do something
if (input)
state = START;
else
state++;
break;
case __COUNTER__:
//do something
state++;
break;
case END:
//do something
run = 0;
state = START;
break;
default:
state++;
break;
}
}
La ventaja de usar __COUNTER__ en lugar de números codificados es que usted
puede agregar estados en el medio de otros estados, sin renumerar cada vez que todo.
Si el compilador no admite __COUNTER__ , de forma limitada es posible usar con precaución __LINE__
En C ++, considere el patrón de estado .
Su pregunta es similar a " ¿hay un patrón de implementación de base de datos típico " ;? La respuesta depende de que quieres lograr? Si desea implementar una máquina de estado determinista más grande, puede utilizar un modelo y un generador de máquina de estado. Se pueden ver ejemplos en www.StateSoft.org - SM Gallery. Janusz Dobrowolski
En C, para máquinas simples, algo como esto es lo que suelo usar.
El FSM controlado por eventos se describe mediante objetos de estado (FsmState) asociados con una acción (FsmAction) y transiciones (FsmEdge) definidas por el estado actual y los eventos.
También proporciona almacenamiento y transmisión de datos de FSM y de usuario, para separar la información de enlace de FSM y de usuario y permitir múltiples instancias del mismo FSM (es decir, usar la misma descripción pero pasar datos de usuario diferentes).
Los eventos están representados por un tipo entero (FsmEvent). Los valores negativos están reservados por la implementación para permitir eventos especiales comunes (Restablecer, Ninguno, Cualquiera, Vacío, Fin). Los eventos no negativos son definidos por el usuario.
Por simplicidad, las transiciones se enumeran en una matriz y se intenta la coincidencia en el orden de la matriz, esencialmente proporcionando prioridades de transición. Tienen funciones de guardia opcionales. El siguiente estado puede indicarse directamente en la lista de transición o mediante una función de salto, de esta forma se proporciona más flexibilidad y permite un comportamiento dinámico de FSM.
En las descripciones de las transiciones, un estado actual NULL coincidirá con cualquier estado y un evento comodín (Cualquiera) coincidirá con cualquier evento. De todos modos, el valor real del evento que activó la transición pasará a las funciones de salto y guardia.
Para las FSM complejas, la solución de matriz de borde simple puede volverse demasiado ineficiente. En ese caso, se podría implementar una función de salto adecuada utilizando la matriz de bordes y las entradas de eventos convertidas en una matriz de transición o listas de adyacencia de estado.
Las acciones de estado deben implementarse con una función de reentrada que discrimina entre la entrada de estado (Enter), la salida de estado (Leave) y las operaciones dentro del estado (State). De esta manera, la información del estado local se puede encapsular y conservar con variables de función estáticas.
Normalmente, las acciones de entrada y salida de estado se ejecutarán de manera no notable y no devolverán nuevos eventos (Ninguno). Si no, el nuevo evento queda atrapado y se devuelve de inmediato. Esto evitará efectivamente una transición en caso de que ocurra al salir del estado actual.
La función de paso FSM (fsmStep) realizará un solo paso del FSM, utilizando un nuevo evento para activar una transición, o ningún evento (Ninguno) para ejecutar la acción de estado del estado actual. La función de paso devuelve un nuevo evento emitido que puede ser manejado o re-alimentado al FSM; o Ninguno, Vacío y Fin en caso de que no haya eventos, no se haya encontrado la transición o se haya alcanzado el estado final, respectivamente.
#ifndef FSM_H_
#define FSM_H_
#include <stdbool.h>
#include <stdint.h>
/** FSM enum type */
typedef enum
{
// Events and return values
fsm_User = 0, ///< User events start with this id
fsm_Reset = -1, ///< Reset event
fsm_None = -2, ///< No event
fsm_Any = -3, ///< Any event, used as a wildcard
fsm_Empty = -4, ///< No transition found for event
fsm_End = -5, ///< Final state event generated when FSM reaches end state, or stop processing when used in transition
// Action types
fsm_Enter = 0, ///< Entry action
fsm_State, ///< In-state action
fsm_Leave ///< Exit action
} fsm_e;
typedef int FsmEvent; ///< Type for events
typedef struct FsmState FsmState; ///< Type for states
typedef struct FsmEdge FsmEdge; ///< Type for edges (transitions)
/** State action functor
@param state Pointer to this state
@param type Action type (Enter/State/Leave)
@param frto Pointer to from(Enter)/to(Leave) state, NULL otherwise
@param data User data
@return Event id in case of a new triggered event, fsm_None otherwise
*/
typedef FsmEvent (*FsmAction)(FsmState *state, fsm_e type, FsmState *frto, void *data);
/** FSM state object */
struct FsmState
{
FsmAction action; ///< Per-state action
void *data; ///< Per-state data
};
/** State jump functor
@param edge Pointer to this edge
@param state Pointer to the actual current state
@param event Event id that triggered the transition
@param data User data
@return Pointer to the next state and NULL for end state
*/
typedef FsmState *(*FsmJump)(FsmEdge *edge, FsmState *state, FsmEvent event, void *data);
/** Guard function
@param edge Pointer to this edge
@param state Pointer to the actual current state
@param event Event id that triggered the transition
@param data User data
@return Guard result
*/
typedef bool (*FsmGuard)(FsmEdge *edge, FsmState *state, FsmEvent event, void *data);
/** FSM edge transition */
struct FsmEdge
{
FsmState *state; ///< Matching current state pointer, or NULL to match any state
FsmEvent event; ///< Matching event id or fsm_Any for wildcard
void *next; ///< Next state pointer (FsmState *) or jump function (FsmJump)
FsmGuard guard; ///< Transition guard function
void *data; ///< Per-edge data
};
typedef struct Fsm Fsm;
struct Fsm
{
FsmState *state; ///< Pointer to the state array
size_t states; ///< Number of states
void **stateData; ///< Pointer to user state data array
FsmEdge *edge; ///< Pointer to the edge transitions array
size_t edges; ///< Number of edges
void **edgeData; ///< Pointer to user edge data array
FsmEvent event; ///< Current/last event
fsm_e type; ///< Current/last action type
FsmState *current; ///< Pointer to the current state
void *data; ///< Per-fsm data
};
#define fsm_INIT { 0 }
static inline FsmEvent
fsmStep(Fsm *f, FsmEvent e)
{
FsmState *cp = f->current; // Store current state
FsmEvent ne = fsm_None; // Next event
// User state data
void *us = (f->stateData && cp) ? f->stateData[cp - f->state] : NULL;
if (!cp && e == fsm_None)
e = fsm_Reset; // Inject reset into uninitialized FSM
f->event = e;
switch (e)
{
case fsm_Reset:
{
// Exit current state
if (cp && cp->action)
{
f->type = fsm_Leave, ne = cp->action(cp, fsm_Leave, f->state, us);
if (ne != fsm_None)
return ne; // Leave action emitted event
}
FsmState *ps = cp;
cp = f->current = f->state; // First state in array is entry state
if (!cp)
return fsm_End; // Null state machine
if (cp->action)
{
us = f->stateData ? f->stateData[0] : NULL;
f->type = fsm_Enter, ne = cp->action(cp, fsm_Enter, ps, us);
}
}
break;
case fsm_None: // No event, run in-state action
if (cp->action)
f->type = fsm_State, ne = cp->action(cp, fsm_State, NULL, us);
break;
default: // Process user transition event
ne = fsm_Empty; // Default return in case no transition is found
// Search transition in listing order
for (size_t i = 0; i < f->edges; ++i)
{
FsmEdge *ep = &f->edge[i];
// Check for state match (null edge state matches any state)
if (ep->state && ep->state != cp)
continue; // Not a match
// Check for stop processing filter
if (ep->event == fsm_End)
break;
ne = fsm_None; // Default return for a transition
// Check for event match
if (ep->event == e || ep->event == fsm_Any)
{
// User edge data
void *ue = f->edgeData ? f->edgeData[i] : NULL;
// Check transition guard
if (!ep->guard || ep->guard(ep, cp, e, ue))
{
// Resolve next state pointer (NULL, new state pointer or jump function)
FsmState *np = (!ep->next) ? NULL
: ((FsmState *)(ep->next) >= f->state && (FsmState *)(ep->next) < (f->state + f->states)) ? (FsmState *)(ep->next)
: ((FsmJump)(ep->next))(ep, cp, e, ue);
if (cp->action)
{
f->type = fsm_Leave, ne = cp->action(cp, fsm_Leave, np, us);
if (ne != fsm_None)
return ne; // Leave action emitted event
}
if (!np) // Final state reached if next state is NULL
ne = fsm_End;
else if (np->action)
{
us = f->stateData ? f->stateData[np - f->state] : NULL;
f->type = fsm_Enter, ne = np->action(np, fsm_Enter, cp, us);
}
cp = np; // New state value
// Transition executed, stop
break;
}
}
}
}
f->current = cp; // Commit current state
return ne; // Last event value
}
static inline FsmEvent
fsmReset(Fsm *f)
{
return fsmStep(f, fsm_Reset);
}
#endif // FSM_H_
A continuación hay una prueba muy simple para tener una idea de cómo definir y usar la implementación de FSM. No hay eventos definidos por el usuario, solo datos FSM (cadenas), la misma acción de estado para cada estado y una función de salto compartida:
#include <stdio.h>
#include "fsm.h"
// State action example
static FsmEvent
state_action(FsmState *s, fsm_e t, FsmState *ft, void *us)
{
FsmEvent e = fsm_None; // State event
const char *q = "?";
switch (t)
{
case fsm_Enter:
q = "enter";
break;
case fsm_Leave:
q = "leave";
break;
default /* fsm_State */:
q = "state";
}
printf("%s %s\n", (const char *)s->data, q);
return e;
}
// States
FsmState fs[] =
{
{ state_action, "S0" },
{ state_action, "S1" },
{ state_action, "S2" },
};
// Transition jump example
static FsmState *
state_jump(FsmEdge *t, FsmState *s, FsmEvent e, void *ue)
{
if (s == &fs[0])
return &fs[1];
if (s == &fs[2])
return NULL; // End state
return NULL; // Trap
}
// Transition guard example
static bool
count_attempt(FsmEdge *t, FsmState *s, FsmEvent e, void *ue)
{
static int c = 0;
++c;
bool b = c == 3;
printf("guard is %s\n", b ? "true" : "false");
return b;
}
// Transitions
FsmEdge fe[] =
{
{ &fs[0], fsm_Any, state_jump }, // Using jump function, no guard
{ &fs[1], fsm_Any, &fs[2], count_attempt }, // Using direct state and guard
{ &fs[2], fsm_Any, state_jump }, // Using jump function, no guard
};
int
main(int argc, char **argv)
{
Fsm f = { fs, 3, NULL, fe, 3, NULL, };
fsmReset(&f);
do
{
fsmStep(&f, fsm_None);
} while (fsmStep(&f, fsm_Any) != fsm_End);
return 0;
}
Boost tiene la biblioteca de gráficos de estado. http://www.boost.org/doc/ libs / 1_36_0 / libs / statechart / doc / index.html
Sin embargo, no puedo hablar de su uso. No lo usé yo mismo (todavía)
