Existe-t-il un modèle d'implémentation de machine à états typique?
https://stackoverflow.com/questions/133214
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Nous devons implémenter une machine à états simple dans C .
Une déclaration de commutateur standard est-elle la meilleure solution?
Nous avons un état actuel (état) et un déclencheur pour la transition.
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;
}
Existe-t-il une meilleure solution pour les machines à états simples
EDIT: Pour le C ++, je pense que le Boost est Statechart . pourrait être la voie à suivre. Cependant, pas l’aider avec C. permet de nous concentrer sur le cas d’utilisation de C.
La solution
Je préfère utiliser une approche basée sur les tables pour la plupart des machines d'état:
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
}
}
Cela peut bien sûr être étendu pour prendre en charge plusieurs machines d'état, etc. Les actions de transition peuvent également être prises en compte:
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'approche basée sur les tables est plus facile à maintenir et à étendre, et plus simple à mapper vers des diagrammes d'état.
Autres conseils
Vous avez peut-être vu ma réponse à une autre question C dans laquelle j'ai mentionné FSM! Voici comment je le fais:
FSM {
STATE(x) {
...
NEXTSTATE(y);
}
STATE(y) {
...
if (x == 0)
NEXTSTATE(y);
else
NEXTSTATE(x);
}
}
Avec les macros suivantes définies
#define FSM
#define STATE(x) s_##x :
#define NEXTSTATE(x) goto s_##x
Ceci peut être modifié en fonction du cas particulier. Par exemple, vous pouvez avoir un fichier FSMFILE que vous voulez gérer votre FSM, afin d’incorporer l’action de lecture du caractère suivant dans la macro elle-même:
#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
Vous avez maintenant deux types de transitions: l’une passe à un état et lit un nouveau caractère, l’autre passe à un état sans consommer aucune entrée.
Vous pouvez également automatiser le traitement de EOF avec quelque chose comme:
#define STATE(x) s_##x : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
goto sx_endfsm;\
sn_##x :
#define ENDFSM sx_endfsm:
L’avantage de cette approche est qu’il est possible de traduire directement un diagramme d’état dessiné en code de travail et, inversement, de dessiner facilement un diagramme d’état à partir du code.
Dans d’autres techniques de mise en œuvre de FSM, la structure des transitions est enterrée dans des structures de contrôle (tandis que, si, commutateur ...) et contrôlée par une valeur de variable (typiquement une variable état ) et peut être une tâche complexe pour relier le beau diagramme à un code compliqué.
J'ai appris cette technique grâce à un article paru dans l'excellent "Langage informatique". magazine qui, malheureusement, n'est plus publié.
J'ai également utilisé l'approche de la table. Cependant, il y a des frais généraux. Pourquoi stocker une deuxième liste de pointeurs? Une fonction en C sans le () est un pointeur const. Donc vous pouvez faire:
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
}
}
Bien sûr, en fonction de votre facteur de peur (sécurité vs vitesse), vous pouvez rechercher des indicateurs valides. Pour les machines d'état de plus de trois états environ, l'approche ci-dessus doit comporter moins d'instructions qu'une approche équivalente par commutateur ou par table. Vous pouvez même créer une macro en tant que:
#define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_))
De plus, je pense, à l'exemple du PO, qu'il faut simplifier la réflexion / la conception d'une machine à états. Je ne pense pas que l'état de transition devrait être utilisé pour la logique. Chaque fonction d’État devrait être en mesure de remplir son rôle sans connaître explicitement l’état ou les états passés. En gros, vous déterminez comment passer de l'état dans lequel vous vous trouvez à un autre.
Enfin, ne démarrez pas la conception d’une machine à états basée sur "fonctionnelle". limites, utilisez des sous-fonctions pour cela. Divisez plutôt les états en fonction du moment où vous devrez attendre que quelque chose se passe avant de pouvoir continuer. Cela vous aidera à réduire le nombre de fois que vous devez exécuter la machine à états avant d'obtenir un résultat. Cela peut être important lorsque vous écrivez des fonctions d’E / S ou des gestionnaires d’interruption.
De plus, quelques avantages et inconvénients de la déclaration classique de switch:
Avantages:
- c'est dans la langue, donc c'est documenté et clair les états
- sont définis à l'endroit où ils s'appellent
- peut exécuter plusieurs états en un seul appel de fonction
- le code commun à tous les états peut être exécuté avant et après l'instruction switch
Inconvénients:
- peut exécuter plusieurs états en un seul appel de fonction
- le code commun à tous les états peut être exécuté avant et après l'instruction switch
- l'implémentation du commutateur peut être lente
Notez les deux attributs à la fois pro et con. Je pense que le changement offre la possibilité de trop partager entre les États et que l'interdépendance entre les États peut devenir ingérable. Toutefois, pour un petit nombre d’États, il se peut que ce soit le plus lisible et le plus facile à gérer.
Pour une machine à états simple, utilisez simplement une instruction switch et un type enum pour votre état. Effectuez vos transitions à l'intérieur de l'instruction switch en fonction de votre saisie. Dans un programme réel, vous devez évidemment modifier l'option "Si (entrée)". pour vérifier vos points de transition. J'espère que cela vous aidera.
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;
}
...
}
il existe également la grille logique , à savoir plus maintenable à mesure que la machine à états grossit
Dans UML Distilled de Martin Fowler , il déclare (sans jeu de mots) dans le chapitre 10 State Machine Diagrammes (mon accentuation):
Un diagramme d'états peut être implémenté de trois manières principales: commutateur imbriqué , le modèle d'état et tables d'état .
Prenons un exemple simplifié des états de l'affichage d'un téléphone portable:
Commutateur imbriqué
Fowler a donné un exemple de code C #, mais je l’ai adapté à mon exemple.
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;
}
}
Modèle d'état
Voici une implémentation de mon exemple avec le modèle d'état GoF:
Tables d'état
S'inspirant de Fowler, voici un tableau pour mon exemple:
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
Comparaison
Le commutateur imbriqué conserve toute la logique au même endroit, mais le code peut être difficile à lire lorsqu'il y a beaucoup d'états et de transitions. C’est peut-être plus sûr et plus facile à valider que les autres approches (pas de polymorphisme ni d’interprétation).
L'implémentation du modèle d'état étend potentiellement la logique sur plusieurs classes distinctes, ce qui peut rendre problématique sa compréhension. Par contre, les petites classes sont faciles à comprendre séparément. La conception est particulièrement fragile si vous modifiez le comportement en ajoutant ou en supprimant des transitions, car ce sont des méthodes dans la hiérarchie et que le code pourrait subir de nombreuses modifications. Si vous respectez le principe de conception des petites interfaces, vous constaterez que ce modèle ne fait pas si bien. Toutefois, si la machine à états est stable, ces modifications ne seront pas nécessaires.
L’approche par tables d’état nécessite l’écriture d’un interprète pour le contenu (cela pourrait être plus facile si vous avez des réflexions dans le langage que vous utilisez), ce qui pourrait nécessiter beaucoup de travail. Comme le souligne Fowler, si votre table est distincte de votre code, vous pouvez modifier le comportement de votre logiciel sans recompiler. Cela a toutefois des conséquences sur la sécurité; le logiciel se comporte en fonction du contenu d'un fichier externe.
Modifier (pas vraiment pour le langage C)
Il existe également une approche d'interface fluide (également appelée langage interne spécifique au domaine), qui est probablement facilitée par les langues qui ont fonctions de première classe . La bibliothèque sans état existe et ce blog présente un exemple simple avec du code. Une l'implémentation de Java (avant Java8) est discutée . Un exemple Python sur GitHub a également été affiché.
Pour les cas simples, vous pouvez choisir votre méthode de changement de style. Ce que j’ai trouvé qui fonctionne bien dans le passé, c’est aussi de faire face aux transitions:
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
}
Je ne connais rien à la bibliothèque boost, mais ce type d'approche est extrêmement simple, ne nécessite aucune dépendance externe et est facile à mettre en œuvre.
switch () est un moyen puissant et standard d'implémenter des machines à états en C, mais il peut réduire la maintenabilité si vous avez un grand nombre d'états. Une autre méthode courante consiste à utiliser des pointeurs de fonction pour stocker le prochain état. Cet exemple simple implémente une bascule 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;
}
J'ai trouvé une implémentation en C vraiment épurée de Moore FSM dans le cours edx.org intitulé Embedded Systems - Shape the World. UTAustinX - UT.6.02x, chapitre 10, par Jonathan Valvano et 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];
}
}
Vous voudrez peut-être examiner le logiciel du générateur FSM libero . À partir d'un langage de description d'état et / ou d'un éditeur de diagramme d'état (Windows), vous pouvez générer du code pour C, C ++, Java et beaucoup d'autres ... plus une documentation et des diagrammes intéressants. Source et fichiers binaires de iMatix
Cet article convient bien au modèle d'état (bien qu'il est C ++, pas spécifiquement C).
Si vous pouvez mettre la main sur le livre " Les modèles de conception Head First ", l'explication et l'exemple sont très clairs.
L’un de mes modèles préférés est le modèle de conception d’état. Répondez ou agissez différemment pour le même ensemble d'entrées.
L’un des problèmes liés à l’utilisation des instructions switch / case pour les machines d’état est qu’au fur et à mesure que vous créez des états, le switch / case devient plus difficile à lire / maintenir, favorise le code spaghetti non organisé et devient de plus en plus difficile à modifier sans casser quelque chose. Je trouve que l'utilisation de modèles de conception m'aide à mieux organiser mes données.
Au lieu de concevoir votre code d'état en fonction de votre état d'origine, structurez-le de sorte qu'il enregistre l'état lorsque vous entrez un nouvel état. De cette façon, vous obtenez effectivement un enregistrement de votre état antérieur. J'aime la réponse de @ JoshPetit et ai poussé sa solution encore plus loin, directement dans le livre du 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;
}
Pour la plupart des machines d'état, en particulier Dans les machines à états finis, chaque état saura ce que devrait être son prochain état et les critères pour passer à son prochain état. Cela peut ne pas être le cas pour les conceptions d'états lâches, d'où la possibilité d'exposer l'API pour les états de transition. Si vous souhaitez davantage d'abstraction, chaque gestionnaire d'état peut être séparé dans son propre fichier, qui équivaut aux gestionnaires d'état concrets du livre GoF. Si votre conception est simple et ne comporte que quelques états, alors stateCtxt.c et statehandlers.c peuvent être combinés dans un seul fichier pour plus de simplicité.
D'après mon expérience, l'utilisation de l'instruction 'switch' est le moyen standard de gérer plusieurs états possibles. Bien que je sois surpris que vous transmettiez une valeur de transition au traitement par état. Je pensais que l’intérêt d’une machine à états était que chaque état exécutait une seule action. Ensuite, l'action / entrée suivante détermine le nouvel état dans lequel effectuer la transition. Je me serais donc attendu à ce que chaque fonction de traitement d'état exécute immédiatement tout ce qui est fixé pour entrer dans un état puis décide ensuite si une transition vers un autre état est nécessaire.
Il existe un livre intitulé Statistiques pratiques en C / C ++ . Cependant, il est trop bien trop lourd pour ce dont nous avons besoin.
Pour les compilateurs prenant en charge __ COUNTER __ , vous pouvez les utiliser pour des mashines d'état simples (mais volumineux).
#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;
}
}
L'avantage d'utiliser __ COUNTER __ au lieu de nombres codés en dur est que vous
peut ajouter des états au milieu d’autres états, sans tout renuméroter à chaque fois.
Si le compilateur ne prend pas en charge __ COUNTER __ , il est possible de l’utiliser avec précaution __ LINE __
En C ++, considérez le modèle d'état .
Votre question est similaire à "Existe-t-il un modèle d'implémentation de base de données typique"? La réponse dépend de ce que vous voulez réaliser? Si vous souhaitez implémenter une machine à états déterministe plus grande, vous pouvez utiliser un modèle et un générateur de machines à états. Des exemples peuvent être consultés sur www.StateSoft.org - SM Gallery. Janusz Dobrowolski
En C, pour les machines simples, c'est ce que je finis habituellement par utiliser.
Le FSM piloté par événement est décrit par des objets d'état (FsmState) associés à une action (FsmAction) et par des transitions (FsmEdge) définis par l'état et les événements en cours.
Il permet également de stocker et de transmettre les données FSM et utilisateur, afin de séparer les informations liées à FSM et liées à l'utilisateur et d'autoriser plusieurs instances du même FSM (c'est-à-dire en utilisant la même description mais en transmettant différentes données utilisateur).
Les événements sont représentés par un type entier (FsmEvent). Les valeurs négatives sont réservées par l'implémentation pour permettre des événements communs spéciaux (Réinitialiser, Aucun, Tout, Vide, Fin). Les événements non négatifs sont définis par l'utilisateur.
Par souci de simplicité, les transitions sont répertoriées dans un tableau et la correspondance est tentée dans l'ordre du tableau, fournissant essentiellement les priorités de transition. Ils ont des fonctions de garde optionnelles. L’état suivant peut être indiqué directement dans la liste de transition ou par une fonction de saut, offrant ainsi plus de flexibilité permettant un comportement dynamique du FSM.
Dans les descriptions de transitions, un état actuel NULL correspond à tout état et un événement générique (Any) correspond à tout événement. Dans tous les cas, la valeur réelle de l'événement qui a déclenché la transition sera transmise aux fonctions de saut et de garde.
Pour les FSM complexes, la solution de tableau de bord simple peut devenir trop inefficace. Dans ce cas, une fonction de saut appropriée pourrait être mise en œuvre à l'aide du tableau de bord et des entrées d'événement converties en une matrice de transition ou en listes de contiguïté d'état.
Les actions d'état sont censées être implémentées avec une fonction réentrante qui fait la distinction entre les opérations d'entrée à l'état (Entrée), de sortie d'état (Quitter) et en état (d'état). De cette manière, les informations d'état locales peuvent être encapsulées et préservées avec des variables de fonction statiques.
Normalement, les actions d'entrée et de sortie à l'état s'exécutent de manière non décente et ne renvoient aucun nouvel événement (Aucun). Sinon, le nouvel événement est intercepté et renvoyé immédiatement. Cela empêchera efficacement une transition si elle se produit lorsque vous quittez l'état actuel.
La fonction d'étape FSM (fsmStep) effectuera une étape unique du système FSM, en utilisant un nouvel événement pour déclencher une transition ou aucun événement (Aucun) pour exécuter l'action en état de l'état actuel. La fonction step renvoie un nouvel événement émis qui peut être géré ou réintroduit dans le FSM. ou None, Empty et End en cas d'absence d'événement, de transition introuvable ou d'état final atteint, respectivement.
#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_
Vous trouverez ci-dessous un test très simple pour vous faire une idée de la définition et de l’utilisation de la mise en œuvre FSM. Il n'y a pas d'événements définis par l'utilisateur, seulement des données FSM (chaînes), la même action d'état pour chaque état et une fonction de saut partagé:
#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 a la bibliothèque de statechart. http://www.boost.org/doc/ libs / 1_36_0 / libs / statechart / doc / index.html
Je ne peux pas en parler, cependant. Pas encore utilisé moi-même
