Esiste un tipico modello di implementazione della macchina a stati?
https://stackoverflow.com/questions/133214
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Dobbiamo implementare una semplice macchina a stati in C .
Un'istruzione switch standard è il modo migliore per procedere?
Abbiamo uno stato (stato) corrente e un trigger per la transizione.
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;
}
Esiste un modo migliore per macchine a stati semplici
EDIT: Per C ++, penso che la libreria Boost Statechart potrebbe essere la strada da percorrere. Tuttavia, non aiuta con C. Consente di concentrarsi sul caso d'uso C.
Soluzione
Preferisco usare un approccio basato su tabelle per la maggior parte delle macchine a stati:
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
}
}
Questo può ovviamente essere esteso per supportare più macchine a stati, ecc. Anche le azioni di transizione possono essere sistemate:
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;
};
L'approccio guidato dalla tabella è più facile da mantenere ed estendere e più semplice da mappare ai diagrammi di stato.
Altri suggerimenti
Potresti aver visto la mia risposta a un'altra domanda C in cui ho menzionato FSM! Ecco come lo faccio:
FSM {
STATE(x) {
...
NEXTSTATE(y);
}
STATE(y) {
...
if (x == 0)
NEXTSTATE(y);
else
NEXTSTATE(x);
}
}
Con le seguenti macro definite
#define FSM
#define STATE(x) s_##x :
#define NEXTSTATE(x) goto s_##x
Questo può essere modificato per adattarsi al caso specifico. Ad esempio, potresti avere un file FSMFILE che vuoi guidare il tuo FSM, quindi potresti incorporare l'azione di lettura del prossimo carattere nella macro stessa:
#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
ora hai due tipi di transizioni: una va in uno stato e legge un nuovo personaggio, l'altra va in uno stato senza consumare alcun input.
Puoi anche automatizzare la gestione di EOF con qualcosa del tipo:
#define STATE(x) s_##x : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
goto sx_endfsm;\
sn_##x :
#define ENDFSM sx_endfsm:
La cosa buona di questo approccio è che puoi tradurre direttamente un diagramma di stato che disegni in un codice funzionante e, al contrario, puoi facilmente disegnare un diagramma di stato dal codice.
In altre tecniche per implementare FSM la struttura delle transizioni è sepolta nelle strutture di controllo (mentre, se, commuta ...) e controllata dal valore delle variabili (tipicamente una variabile state ) e può essere un compito complesso per mettere in relazione il bel diagramma con un codice contorto.
Ho imparato questa tecnica da un articolo apparso sul grande "Linguaggio informatico" rivista che, sfortunatamente, non è più pubblicata.
Ho anche usato l'approccio table. Tuttavia, c'è un sovraccarico. Perché memorizzare un secondo elenco di puntatori? Una funzione in C senza () è un puntatore const. Quindi puoi fare:
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
}
}
Ovviamente, in base al fattore di paura (ovvero sicurezza e velocità), potresti voler verificare la presenza di puntatori validi. Per le macchine a stati di dimensioni superiori a tre o più, l'approccio sopra dovrebbe essere meno istruzioni di un equivalente switch o approccio a tabella. Potresti anche macronizzare come:
#define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_))
Dall'esempio del PO, inoltre, sento che esiste una semplificazione che dovrebbe essere fatta quando si pensa / si progetta una macchina a stati. Non credo che lo stato di transizione debba essere usato per la logica. Ciascuna funzione statale dovrebbe essere in grado di svolgere il proprio ruolo assegnato senza una conoscenza esplicita degli stati passati. Fondamentalmente progettate come passare dallo stato in cui vi trovate in un altro stato.
Infine, non avviare la progettazione di una macchina a stati basata su " funzionale " i confini, utilizzare le sotto-funzioni per quello. Invece dividi gli stati in base a quando dovrai aspettare che accada qualcosa prima di poter continuare. Ciò consentirà di ridurre al minimo il numero di volte in cui è necessario eseguire la macchina a stati prima di ottenere un risultato. Questo può essere importante quando si scrivono funzioni I / O o si interrompono i gestori.
Inoltre, alcuni pro e contro della classica istruzione switch:
Pro:
- è nella lingua, quindi è documentato e chiaro
- gli stati sono definiti dove vengono chiamati
- può eseguire più stati in una chiamata di funzione
- il codice comune a tutti gli stati può essere eseguito prima e dopo l'istruzione switch
Contro:
- può eseguire più stati in una chiamata di funzione
- il codice comune a tutti gli stati può essere eseguito prima e dopo l'istruzione switch
- passare all'implementazione può essere lento
Nota i due attributi che sono sia pro che con. Penso che il passaggio offra l'opportunità di una condivisione eccessiva tra Stati e che l'interdipendenza tra Stati possa diventare ingestibile. Tuttavia, per un numero limitato di stati, può essere il più leggibile e gestibile.
Per una semplice macchina a stati basta usare un'istruzione switch e un tipo enum per il proprio stato. Effettua le tue transizioni all'interno dell'istruzione switch in base al tuo input. In un vero programma, ovviamente, cambieresti " if (input) " per verificare i punti di transizione. Spero che questo aiuti.
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;
}
...
}
esiste anche la griglia logica che è più gestibile man mano che la macchina statale si ingrandisce
In UML Distilled di Martin Fowler , egli afferma (nessun gioco di parole previsto) nel capitolo 10 State Machine Diagrammi (sottolineatura mia):
Un diagramma di stato può essere implementato in tre modi principali: interruttore nidificato , il modello di stato e tabelle di stato .
Usiamo un esempio semplificato degli stati del display di un telefono cellulare:
Switch nidificato
Fowler ha fornito un esempio di codice C #, ma l'ho adattato al mio esempio.
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;
}
}
Pattern di stato
Ecco un'implementazione del mio esempio con il modello di stato GoF:
Tabelle di stato
Prendendo ispirazione da Fowler, ecco una tabella per il mio esempio:
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
Confronto
Lo switch nidificato mantiene tutta la logica in un punto, ma il codice può essere difficile da leggere quando ci sono molti stati e transizioni. È probabilmente più sicuro e più facile da convalidare rispetto agli altri approcci (nessun polimorfismo o interpretazione).
L'implementazione del modello di stato potenzialmente diffonde la logica su diverse classi separate, il che può rendere la comprensione nel suo insieme un problema. D'altra parte, le piccole classi sono facili da capire separatamente. Il design è particolarmente fragile se si modifica il comportamento aggiungendo o rimuovendo le transizioni, poiché sono metodi nella gerarchia e potrebbero esserci molte modifiche al codice. Se rispetti il ??principio di progettazione di piccole interfacce, vedrai che questo modello non funziona molto bene. Tuttavia, se la macchina a stati è stabile, tali modifiche non saranno necessarie.
L'approccio delle tabelle di stato richiede la scrittura di una sorta di interprete per il contenuto (questo potrebbe essere più semplice se si ha una riflessione sulla lingua che si sta utilizzando), che potrebbe essere molto lavoro da svolgere in anticipo. Come sottolinea Fowler, se la tabella è separata dal codice, è possibile modificare il comportamento del software senza ricompilare. Ciò ha alcune implicazioni per la sicurezza, tuttavia; il software si sta comportando in base al contenuto di un file esterno.
Modifica (non proprio per il linguaggio C)
Esiste anche un approccio di interfaccia fluente (noto anche come linguaggio specifico del dominio interno), che è probabilmente facilitato da lingue che hanno funzioni di prima classe . La Biblioteca stateless esiste e quel blog mostra un semplice esempio con il codice. Viene discussa un'implementazione Java (pre Java8) . Mi è stato mostrato anche un esempio di Python su GitHub .
Per casi semplici, puoi scegliere il tuo metodo di cambio stile. Quello che ho scoperto che funziona bene in passato è gestire anche le transizioni:
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
}
Non so nulla della libreria boost, ma questo tipo di approccio è semplicissimo, non richiede dipendenze esterne ed è facile da implementare.
switch () è un modo potente e standard di implementare macchine a stati in C, ma può diminuire la manutenibilità se hai un gran numero di stati. Un altro metodo comune è utilizzare i puntatori a funzione per memorizzare lo stato successivo. Questo semplice esempio 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;
}
Ho trovato un'implementazione in C molto semplice di Moore FSM sul corso edx.org Embedded Systems - Shape the World UTAustinX - UT.6.02x, capitolo 10, di Jonathan Valvano e 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];
}
}
Potresti voler esaminare il libero software generatore di FSM. Da un linguaggio di descrizione dello stato e / o un editor di diagrammi di stato (windows) puoi generare codice per C, C ++, java e molti altri ... oltre a una bella documentazione e diagrammi. Fonte e file binari da iMatix
Questo articolo è valido per il modello di stato (sebbene è C ++, non specificamente C).
Se riesci a mettere le mani sul libro " Head First Design Patterns " ;, la spiegazione e l'esempio sono molto chiari.
Uno dei miei modelli preferiti è il modello di progettazione dello stato. Rispondi o comportati in modo diverso allo stesso set di input fornito.
Uno dei problemi con l'utilizzo delle istruzioni switch / case per macchine a stati è che quando si creano più stati, lo switch / case diventa più difficile / ingombrante da leggere / mantenere, promuove il codice spaghetti non organizzato e diventa sempre più difficile cambiare senza rompere qualcosa. Trovo che l'utilizzo dei modelli di progettazione mi aiuti a organizzare meglio i miei dati, che è l'intero punto di astrazione.
Invece di progettare il codice dello stato in base allo stato da cui provieni, invece strutturare il codice in modo che registri lo stato quando si immette un nuovo stato. In questo modo, ottieni effettivamente una registrazione del tuo stato precedente. Mi piace la risposta di @JoshPetit e ho preso la sua soluzione un passo avanti, presa direttamente dal 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;
}
Per la maggior parte delle macchine statali, esp. Macchine a stati finiti, ogni stato saprà quale dovrebbe essere il suo prossimo stato e i criteri per passare al suo prossimo stato. Per i progetti a stati allentati, questo potrebbe non essere il caso, quindi l'opzione per esporre l'API per gli stati in transizione. Se desideri maggiore astrazione, ogni gestore di stato può essere separato nel suo file, che sono equivalenti ai gestori di stato concreti nel libro GoF. Se il tuo design è semplice con solo pochi stati, allora stateCtxt.c e statehandlers.c possono essere combinati in un singolo file per semplicità.
Nella mia esperienza l'uso dell'istruzione 'switch' è il modo standard di gestire più stati possibili. Anche se sono sorpreso che tu stia passando un valore di transizione all'elaborazione per stato. Pensavo che il punto centrale di una macchina a stati fosse che ogni stato eseguiva una singola azione. Quindi l'azione / input successivo determina in quale nuovo stato passare. Quindi mi sarei aspettato che ogni funzione di elaborazione dello stato eseguisse immediatamente tutto ciò che è fisso per entrare nello stato e poi decidere se è necessaria la transizione verso un altro stato.
Esiste un libro intitolato Statecharts pratici in C / C ++ . Tuttavia, è modo troppo pesante per ciò di cui abbiamo bisogno.
Per il compilatore che supporta __COUNTER__ , puoi usarli per mashine di stato semplici (ma grandi).
#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;
}
}
Il vantaggio di usare __COUNTER__ invece di numeri con codice fisso è che tu
può aggiungere stati nel mezzo di altri stati, senza rinumerare ogni volta tutto.
Se il compilatore non supporta __COUNTER__ , è possibile utilizzarlo con precauzione __LINE__
In C ++, considera il Pattern di stato .
La tua domanda è simile a " esiste un tipico modello di implementazione della base di dati " ;? La risposta dipende da cosa vuoi ottenere? Se si desidera implementare una macchina a stati deterministici più grande, è possibile utilizzare un modello e un generatore di macchine a stati. Esempi sono disponibili su www.StateSoft.org - SM Gallery. Janusz Dobrowolski
In C, per macchine semplici qualcosa di simile è quello che di solito finisco per usare.
L'FSM guidato dagli eventi è descritto da oggetti di stato (FsmState) associati a un'azione (FsmAction) e transizioni (FsmEdge) definiti dallo stato e dagli eventi correnti.
Fornisce inoltre l'archiviazione e il passaggio di dati FSM e utente, per separare le informazioni relative a FSM e associate all'utente e consentire più istanze dello stesso FSM (ovvero utilizzando la stessa descrizione ma passando dati utente diversi).
Gli eventi sono rappresentati da un tipo intero (FsmEvent). I valori negativi sono riservati dall'implementazione per consentire eventi comuni speciali (Reset, Nessuno, Qualsiasi, Vuoto, Fine). Gli eventi non negativi sono definiti dall'utente.
Per semplicità, le transizioni sono elencate in una matrice e la corrispondenza viene tentata nell'ordine della matrice, fornendo essenzialmente priorità di transizione. Hanno funzioni di protezione opzionali. Lo stato successivo può essere indicato direttamente nell'elenco di transizione o mediante una funzione di salto, in questo modo fornendo una maggiore flessibilità che consente il comportamento dinamico di FSM.
Nelle descrizioni delle transizioni, uno stato corrente NULL corrisponderà a qualsiasi stato e un evento jolly (Qualsiasi) corrisponderà a qualsiasi evento. Ad ogni modo, il valore effettivo dell'evento che ha innescato la transizione verrà passato alle funzioni di salto e guardia.
Per FSM complessi, la soluzione edge array semplice potrebbe diventare troppo inefficiente. In tal caso, una funzione di salto appropriata potrebbe essere implementata utilizzando l'array edge e le voci di evento convertite in una matrice di transizione o in elenchi di adiacenza dello stato.
Le azioni statali sono pensate per essere implementate con una funzione rientrante che discrimina tra operazioni di entrata di stato (Invio), uscita di stato (Uscita) e stato (Stato). In questo modo le informazioni sullo stato locale possono essere incapsulate e conservate con variabili di funzione statiche.
Normalmente, le azioni di entrata e uscita dello stato verranno eseguite in modo non significativo e non restituiranno nuovi eventi (nessuno). In caso contrario, il nuovo evento viene intercettato e restituito immediatamente. Ciò impedirà efficacemente una transizione nel caso in cui si verifichi quando si esce dallo stato corrente.
La funzione di passaggio FSM (fsmStep) eseguirà un singolo passaggio di FSM, utilizzando un nuovo evento per attivare una transizione o nessun evento (Nessuno) per eseguire l'azione nello stato dello stato corrente. La funzione step restituisce un nuovo evento emesso che può essere gestito o reimmesso in FSM; oppure Nessuno, Vuoto e Fine in caso di nessun evento, transizione non trovata o stato finale raggiunto, rispettivamente.
#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_
Di seguito è riportato un test molto semplice per avere un'idea su come definire e utilizzare l'implementazione di FSM. Non ci sono eventi definiti dall'utente, solo dati FSM (stringhe), la stessa azione di stato per ogni stato e una funzione di salto condivisa:
#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 ha la libreria statechart. http://www.boost.org/doc/ libs / 1_36_0 / librerie / statechart / doc / index.html
Tuttavia, non posso parlarne. Non l'ho usato da solo (ancora)
