Existe um padrão de implementação de máquina de estado típico?
https://stackoverflow.com/questions/133214
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Precisamos implementar uma máquina de estado simples em C .
É uma instrução switch padrão a melhor maneira de ir?
Temos um estado atual (estado) e um gatilho para a transição.
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 uma maneira melhor para máquinas de estado simples
EDIT: Para C ++, eu acho que o impulso Statechart biblioteca pode ser o caminho a percorrer. No entanto, ele não ajuda com C. Deixa concentrado no caso de uso C.
Solução
Eu prefiro usar uma abordagem orientada mesa para a maioria das 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
}
}
Esta pode, naturalmente, ser estendido para suportar múltiplas máquinas de estado, etc. acções de transição podem ser acomodados assim:
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;
};
A abordagem orientada a tabela é mais fácil de manter e ampliar e mais simples para mapear para diagramas de estado.
Outras dicas
Você pode ter visto a minha resposta a outra pergunta C onde eu mencionei FSM! Aqui está como eu faço isso:
FSM {
STATE(x) {
...
NEXTSTATE(y);
}
STATE(y) {
...
if (x == 0)
NEXTSTATE(y);
else
NEXTSTATE(x);
}
}
Com as seguintes macros definidos
#define FSM
#define STATE(x) s_##x :
#define NEXTSTATE(x) goto s_##x
Isso pode ser modificado para se adequar ao caso específico. Por exemplo, você pode ter um FSMFILE arquivo que você quer dirigir seu FSM, assim que você poderia incorporar a ação de leitura próxima de char para o macro-se:
#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
Agora você tem dois tipos de transições: um vai para um estado e ler um novo personagem, o outro vai para um estado sem consumir qualquer entrada
.Você também pode automatizar a manipulação de EOF com algo como:
#define STATE(x) s_##x : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
goto sx_endfsm;\
sn_##x :
#define ENDFSM sx_endfsm:
A coisa boa desta abordagem é que você pode traduzir diretamente um diagrama de estado que você desenhar em código de trabalho e, por outro lado, você pode facilmente desenhar um diagrama de estado a partir do código.
Em outras técnicas para implementar FSM a estrutura das transições é enterrado em estruturas de controle (quando, se, interruptor ...) e controlado pelo valor de variáveis ??(tipicamente uma variável state) e pode ser uma tarefa complexa para relacionar o agradável diagrama para um código complicado.
Eu aprendi esta técnica a partir de um artigo apareceu na grande revista "Computer Language" que, infelizmente, já não está publicada.
Eu usei também a abordagem mesa. No entanto, não há sobrecarga. Por armazenar uma segunda lista de ponteiros? Uma função em C sem o () é um ponteiro const. Então você pode fazer:
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
}
}
É claro que, dependendo do fator medo (ou seja, a segurança vs velocidade), você pode querer verificar para ponteiros válidos. Para máquinas de estados maiores do que três ou mais estados, a abordagem acima deve ser menos instruções do que um interruptor equivalente ou abordagem mesa. Você poderia até mesmo macro-ize como:
#define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_))
Além disso, sinto-me com o exemplo do OP, que há uma simplificação que deve ser feito quando se pensa em / projetar uma máquina de estado. Eu não coisa que o estado transição deve ser usado para a lógica. Cada função de estado deve ser capaz de desempenhar o seu papel dado sem conhecimento explícito de estado passado (s). Basicamente você projeta para a forma de transição do estado você está em para outro estado.
Finalmente, não começar o desenho de uma máquina de estados baseada nas fronteiras "funcionais", o uso sub-funções para isso. Em vez disso dividir os estados com base em quando você vai ter que esperar que algo aconteça antes que você possa continuar. Isso ajudará a minimizar o número de vezes que você tem que executar a máquina de estado antes de obter um resultado. Isso pode ser importante quando se escreve I / O funções, ou manipuladores de interrupção.
Além disso, alguns prós e contras da instrução switch clássico:
Pros:
- é na língua, por isso está documentado e clara
- estados são definidos onde são chamados
- pode executar vários estados em uma chamada de função
- código comum a todos os estados podem ser executadas antes e depois da instrução switch
Contras:
- pode executar vários estados em uma chamada de função
- código comum a todos os estados podem ser executadas antes e depois da instrução switch
- implementação switch pode ser lento
Observe os dois atributos que são tanto prós e contras. Eu acho que o interruptor permite a oportunidade para muita partilha entre os estados, ea interdependência entre os estados podem tornar-se incontrolável. No entanto, para um pequeno número de estados, pode ser o mais legível e de fácil manutenção.
Para uma máquina de estado simples, basta usar uma instrução switch e um tipo de enumeração para seu estado. Fazer suas transições dentro da instrução switch com base em sua entrada. Em um programa real, você, obviamente, alterar o "se (entrada)" para verificar seus pontos de transição. Espero que isso ajude.
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;
}
...
}
Na de Martin Fowler UML destilada , ele afirma (sem trocadilhos) no capítulo 10 State Machine diagramas (grifo meu):
Um diagrama de estado pode ser implementado em três formas principais: interruptor aninhada , o padrão de Estado , e tabelas de estado .
Vamos usar um exemplo simplificado dos estados de exibição de um telefone celular:
Nested interruptor
Fowler deu um exemplo de código C #, mas eu adaptei-lo para o meu exemplo.
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;
}
}
Estado padrão
Aqui está uma implementação do meu exemplo com o padrão Estado GoF:
tabelas de estado
Inspirando-se Fowler, aqui está uma tabela para o meu exemplo:
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
Comparação
interruptor Nested mantém toda a lógica em um ponto, mas o código pode ser difícil de ler quando há um grande número de estados e transições. É possivelmente mais seguro e mais fácil de validar que as outras abordagens (sem polimorfismo ou interpretação).
A implementação padrão de Estado potencialmente espalha a lógica ao longo de várias classes separadas, que podem tornar entendendo-a como um problema um todo. Por outro lado, as classes pequenas são fáceis de entender separadamente. O design é particularmente frágil, se você alterar o comportamento, adicionando ou removendo transições, como eles são métodos na hierarquia e pode haver muitas mudanças no código. Se você vive pelo princípio da concepção de pequenas interfaces, você verá esse padrão realmente não faz tão bem. No entanto, se a máquina de estado é estável, então não será necessário tais mudanças.
A abordagem mesas estado requer escrever algum tipo de intérprete para o conteúdo (isso pode ser mais fácil se você tem reflexo na língua que você está usando), o que poderia ser um monte de trabalho a fazer na frente. Como aponta Fowler fora, se sua mesa é separado do seu código, você pode modificar o comportamento do seu software sem recompilar. Isto tem algumas implicações de segurança, no entanto; o software está se comportando com base no conteúdo de um arquivo externo.
Editar (não é realmente para a linguagem C)
Há uma abordagem interface fluente (aka interna Domínio Específico de Linguagem), também, o que provavelmente é facilitada pela idiomas que têm funções de primeira classe . A Stateless biblioteca existe e que o blog mostra um exemplo simples com o código. A Java implementação (pré Java8) é discutido . I foi mostrado um Python exemplo no GitHub bem.
Para casos simples, pode-lhe o seu método de estilo switch. O que eu encontrei que funciona bem no passado é lidar com transições demasiado:
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
}
Eu não sei nada sobre a biblioteca de impulso, mas este tipo de abordagem é simples morto, não requer quaisquer dependências externas, e é fácil de implementar.
switch () é uma maneira poderosa e padrão de implementação de máquinas de estado em C, mas pode diminuir a capacidade de manutenção para baixo se você tem um grande número de estados. Outro método comum é usar ponteiros de função para armazenar o próximo estado. Este exemplo simples implementa um conjunto / reset flip-flop:
/* 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;
}
Eu encontrei uma implementação C realmente liso de Moore FSM na edx.org curso de Sistemas Embarcados - moldar o mundo UTAustinX - UT.6.02x, capítulo 10, por 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];
}
}
Você pode querer olhar para o libero software gerador FSM. A partir de uma linguagem de descrição de estado e / ou um (windows) editor de diagrama de estado pode gerar código para C, C ++, Java e muitos outros ... mais agradável de documentação e diagramas. Fonte e binários de iMatix
Este artigo é uma boa para o padrão do estado (embora é C ++, não especificamente C).
Se você pode colocar suas mãos sobre o livro " Head First Design Patterns ", a explicação e exemplo são muito claras.
Um dos meus modelos preferidos é o padrão de projeto Estado. Responder ou se comportar de forma diferente para o mesmo conjunto determinado de entradas.
Um dos problemas com o uso do interruptor declarações / argumento para máquinas de estado é que, como você criar mais estados, o parâmetro / casos torna-se mais difícil / pesado para ler / manter, promove código espaguete desorganizada, e cada vez mais difícil a mudança sem quebrar alguma coisa. Acho usando padrões de design me ajuda a organizar os meus dados melhor, que é o ponto inteiro de abstração.
Em vez de projetar o seu código de estado em torno de qual estado você veio, em vez estruturar o seu código para que ele registra o estado quando você entra em um novo estado. Dessa forma, você efetivamente obter um registro de seu estado anterior. Eu como @ resposta de JoshPetit, e tomaram a sua solução mais um passo, levado diretamente a partir do livro 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 a maioria das Máquinas de Estado, esp. máquinas de estados finitos, cada estado vai saber o que seu próximo estado deve ser, e os critérios para a transição para o próximo estado. Para projetos do estado soltas, isso pode não ser o caso, portanto, a opção para expor a API para a transição estados. Se você desejar mais abstração, cada manipulador de estado pode ser separada em seu próprio arquivo, que são equivalentes aos manipuladores estaduais concretas no livro GoF. Se o seu design é simples, com apenas alguns estados, em seguida, ambos stateCtxt.c e statehandlers.c podem ser combinados em um único arquivo para simplificar.
Em minha experiência usando a instrução 'switch' é a maneira padrão de lidar com vários estados possíveis. Embora eu estou surpirsed que você está passando um valor de transição ao tratamento por estado. Eu pensei que todo o ponto de uma máquina de estado era que cada estado realizada uma única ação. Em seguida, a próxima ação / entrada determina que novo estado de transição para. Então, eu teria esperado que cada função de processamento de estado para executar imediatamente o que está fixo para entrar no estado e, em seguida, depois decidir se a transição é necessário para outro estado.
Há um livro intitulado Statecharts práticas em C / C ++ . No entanto, é modo demasiado pesado para o que precisamos.
Para compilador que suporte __COUNTER__, você pode usá-los para simples (mas grandes) mashines estado.
#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;
}
}
A vantagem de usar __COUNTER__ em vez de números codificados difícil é que você
pode adicionar estados no meio de outros estados, sem renumeração toda tudo.
Se o apoio __COUNTER__ compilador não faz, de forma limitada a sua posible para usar com precaução __LINE__
Em C ++, considere o Estado padrão .
A sua pergunta é semelhante ao "existe um padrão típico implementação base de dados"? A resposta depende do que você quer alcançar? Se você deseja implementar uma máquina de estado determinístico maior você pode usar um modelo e um gerador de máquina de estado. Exemplos podem ser vistos em www.StateSoft.org - SM Gallery. Janusz Dobrowolski
Em C, para máquinas simples algo como isto é o que eu geralmente acabam usando.
O EFM é descrito por objectos estado accionado por evento (FsmState) associado com uma acção (FsmAction), e as transições (FsmEdge) definido por estado e acontecimentos actuais.
Ele também fornece o armazenamento e passando os dois dados FSM e de utilizador, a informação ligada-EFM e ligado fácil de separar e permitir múltiplas instâncias do mesmo EFM (isto é, utilizando a mesma descrição, mas passando dados de utilizador diferente).
Os eventos são representados por um tipo inteiro (FsmEvent). Os valores negativos são reservados pela implementação para permitir comuns eventos especiais (Reset, None, Qualquer, Vazio, End). eventos não-negativos são definidos pelo usuário.
Para simplicidade, as transições são listados em uma matriz correspondente e é tentada na ordem matriz, fornecendo essencialmente prioridades de transição. Eles têm funções de guarda opcionais. O próximo estado pode ser indicado diretamente na lista de transição ou por uma função de salto, desta forma proporcionando mais flexibilidade que permita comportamento dinâmico EFM.
No descrições transições, A NULL estado atual irá corresponder a qualquer estado e um evento curinga (Qualquer) irá corresponder a qualquer evento. De qualquer forma, o valor real do evento que desencadeou a transição será passado para as funções de salto e de guarda.
Para REFs complexas, a solução de matriz de aresta simples pode tornar-se demasiado ineficiente. Nesse caso, uma função salto adequada poderia ser implementado usando a borda entradas de matriz e eventos convertidos em uma matriz de transição ou estaduais listas de adjacência.
açõesEstado são destinadas a ser implementado com uma função reentrante que discrimina entre entrada de estado (Enter), saída de estado (Leave) e no estado operações (Estado). Desta forma, informações de estado local pode ser encapsulado e preservado com variáveis ??função estática.
Normalmente, as ações de entrada e saída do estado executará unremarkably e voltar há novos eventos (Nenhum). Se não, o novo evento está preso e voltou imediatamente. Isto irá prevenir eficazmente uma transição no caso de isso acontece quando sair do estado atual.
A função passo EFM (fsmStep) vai realizar uma única etapa do EFM, utilizando um novo evento de desencadear uma transição, ou nenhum evento (Nenhum) para executar a acção no estado do estado actual. A função passo retorna um novo evento emitida que pode ser tratado ou re-alimentadas para o EFM; ou Nenhum, vazios e, no caso de nenhum evento, a transição não foi encontrado ou estado final alcançado, 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 seguir há um teste muito simples para obter a idéia sobre como definir e usar a implementação FSM. Não há eventos definidos pelo usuário, apenas FSM dados (strings), a mesma ação do estado para cada estado e uma função salto compartilhada:
#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;
}
Impulso tem a biblioteca de estados. http://www.boost.org/doc/ libs / 1_36_0 / libs / statechart / doc / index.html
Eu não posso falar para o uso do mesmo, no entanto. Não usei-me (ainda)
