Existe um padrão típico de implementação de máquinas de estado?

Precisamos implementar uma máquina de estado simples em C.
É uma declaração de switch padrão o melhor caminho a percorrer?
Nós 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 ++, acho que a biblioteca Boost Statechart pode ser o caminho a percorrer. No entanto, isso não ajuda com C. Vamos nos concentrar no caso de uso C.

Eu prefiro usar uma abordagem baseada em tabela 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 } } 

É claro que isso pode ser estendido para suportar várias máquinas de estado, etc. Ações de transição também podem ser acomodadas:

 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 por tabelas é mais fácil de manter e estender e mais simples de mapear para diagramas de estados.

Você pode ter visto a minha resposta para outra questão C onde mencionei FSM! Aqui está como eu faço:

 FSM { STATE(x) { ... NEXTSTATE(y); } STATE(y) { ... if (x == 0) NEXTSTATE(y); else NEXTSTATE(x); } } 

Com as seguintes macros definidas

 #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 arquivo FSMFILE que deseja direcionar seu FSM, para poder incorporar a ação de ler o próximo caractere na própria macro:

 #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 lê um novo caractere, o outro vai para um estado sem consumir nenhuma input.

Você também pode automatizar o manuseio de EOF com algo como:

 #define STATE(x) s_##x : if ((FSMCHR = fgetc(FSMFILE) == EOF)\ goto sx_endfsm;\ sn_##x : #define ENDFSM sx_endfsm: 

O bom desta abordagem é que você pode traduzir diretamente um diagrama de estados desenhado para o código de trabalho e, ao contrário, pode facilmente desenhar um diagrama de estado a partir do código.

Em outras técnicas para implementar FSM, a estrutura das transições é enterrada em estruturas de controle (while, if, switch …) e controlada pelo valor de variables ​​(tipicamente uma variável de state ) e pode ser uma tarefa complexa relacionar o diagrama agradável a um código complicado.

Eu aprendi essa técnica a partir de um artigo publicado na grande revista “Computer Language” que, infelizmente, não é mais publicada.

Eu também usei a abordagem de tabela. No entanto, há sobrecarga. Por que armazenar uma segunda lista de pointers? Uma function 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 seu fator de medo (ou seja, segurança vs velocidade) você pode querer verificar se há pointers válidos. Para máquinas de estado com mais de três ou mais estados, a abordagem acima deve ser menos instruções do que uma abordagem equivalente de comutador ou tabela. Você pode até mesmo macroizar:

 #define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_)) 

Além disso, sinto no exemplo do OP, que há uma simplificação que deve ser feita quando se pensa em projetar uma máquina de estado. Eu não sei que o estado de transição deve ser usado para lógica. Cada function de estado deve ser capaz de desempenhar sua function sem conhecimento explícito de estado (s) passado (s). Basicamente, você projeta como fazer a transição do estado em que está para outro estado.

Por fim, não inicie o projeto de uma máquina de estados com base em limites “funcionais”, use subfunções para isso. Em vez disso, divida os estados com base em quando você terá que esperar que algo aconteça antes de continuar. Isso ajudará a minimizar o número de vezes que você precisa executar a máquina de estado antes de obter um resultado. Isso pode ser importante ao escrever funções de E / S ou interromper manipuladores.

Além disso, alguns prós e contras da declaração switch clássico:

Prós:

  • está na linguagem, por isso está documentado e claro
  • estados são definidos onde são chamados
  • pode executar múltiplos estados em uma chamada de function
  • código comum a todos os estados pode ser executado antes e depois da instrução switch

Contras:

  • pode executar múltiplos estados em uma chamada de function
  • código comum a todos os estados pode ser executado antes e depois da instrução switch
  • A implementação do switch pode ser lenta

Observe os dois atributos que são pro e con. Eu acho que a opção permite a oportunidade de compartilhar muito entre os estados, e a interdependência entre os estados pode se tornar incontrolável. No entanto, para um pequeno número de estados, pode ser o mais legível e sustentável.

há também a grade lógica que é mais sustentável à medida que a máquina de estado se torna maior

Para uma máquina de estado simples, basta usar uma instrução switch e um tipo enum para seu estado. Faça suas transições dentro da instrução switch com base em sua input. Em um programa real, você obviamente mudaria o “if (input)” para checar seus pontos de transição. Espero que isto 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; } ... } 

switch () é uma maneira poderosa e padrão de implementar máquinas de estado em C, mas pode diminuir a capacidade de manutenção se você tiver um grande número de estados. Outro método comum é usar pointers de function para armazenar o próximo estado. Este exemplo simples implementa um 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; } 

Para casos simples, você pode usar seu método de mudança de estilo. O que eu descobri que funciona bem no passado é lidar com as transições também:

 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 reforço, mas esse tipo de abordagem é simples, não requer dependencies externas e é fácil de implementar.

Eu encontrei uma implementação C bem bacana do Moore FSM no curso edx.org Embedded Systems – Forma do 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 software do gerador libero FSM. A partir de uma linguagem de descrição de estado e / ou de um editor de diagrama de estado (windows) você pode gerar código para C, C ++, java e muitos outros … além de documentação e diagramas agradáveis. Origem e binários do iMatix

Este artigo é bom para o padrão de estado (embora seja C ++, não especificamente C).

Se você pode colocar suas mãos no livro ” Head First Design Patterns “, a explicação e o exemplo são muito claros.

Um dos meus padrões favoritos é o padrão de design do estado. Responda ou se comporte de maneira diferente ao mesmo conjunto de inputs.
Um dos problemas com o uso de instruções switch / case para máquinas de estado é que à medida que você cria mais estados, o switch / casos fica mais difícil / difícil de ler / manter, promove código desorganizado de espaguete e é cada vez mais difícil mudar sem quebrar algo. Eu acho que usar padrões de design me ajuda a organizar melhor meus dados, que é o ponto de abstração. Em vez de projetar seu código de estado em torno do estado de onde você veio, em vez disso, estruture seu código para que ele registre o estado quando você entrar em um novo estado. Dessa forma, você obtém efetivamente um registro do seu estado anterior. Eu gosto da resposta do @ JoshPetit, e levei sua solução um passo adiante, tirada direto do livro do 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 estatais, esp. Máquinas de estados finitos, cada estado saberá qual deve ser seu próximo estado e os critérios para a transição para o próximo estado. Para projetos de estado frouxo, isso pode não ser o caso, daí a opção de expor a API para estados de transição. Se você deseja mais abstração, cada manipulador de estado pode ser separado em seu próprio arquivo, que são equivalentes aos manipuladores de estado concreto no livro do GoF. Se seu design é simples com apenas alguns estados, tanto stateCtxt.c quanto statehandlers.c podem ser combinados em um único arquivo para simplificar.

Em UML Distilled , de Martin Fowler , ele afirma (sem trocadilhos) no Capítulo 10 Diagramas de Máquina de Estado (ênfase minha):

Um diagrama de estado pode ser implementado de três maneiras principais: comutador nested , o padrão de estado e tabelas de estado .

Vamos usar um exemplo simplificado dos estados do display de um celular:

insira a descrição da imagem aqui

Interruptor nested

Fowler deu um exemplo de código C #, mas eu o adaptei ao 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; } } 

Padrão de estado

Aqui está uma implementação do meu exemplo com o padrão GoF State:

insira a descrição da imagem aqui

Tabelas de Estado

Inspirando-se em Fowler, aqui está uma tabela para o meu exemplo:

 Ação de guarda de evento de estado de destino de estado de origem
 -------------------------------------------------- ------------------------------------
 ScreenOff ScreenOff pressButton powerLow displayLowPowerMessage  
 ScreenOff ScreenOn pressButton! PowerLow
 ScreenOn ScreenOff pressButton
 ScreenOff ScreenCharging plugPower
 ScreenOn ScreenCharging plugPower
 ScreenCharging ScreenOff unplugPower

Comparação

O switch nested mantém toda a lógica em um ponto, mas o código pode ser difícil de ler quando há muitos estados e transições. É possivelmente mais seguro e mais fácil de validar do que as outras abordagens (sem polymorphism ou interpretação).

A implementação do padrão de estado potencialmente distribui a lógica em várias classs separadas, o que pode fazer com que a compreensão como um todo seja um problema. Por outro lado, as turmas pequenas são fáceis de entender separadamente. O design é particularmente frágil se você alterar o comportamento adicionando ou removendo transições, pois eles são methods na hierarquia e pode haver muitas alterações no código. Se você viver de acordo com o princípio do design de pequenas interfaces, verá que esse padrão não se sai muito bem. No entanto, se a máquina de estado estiver estável, essas mudanças não serão necessárias.

A abordagem de tabelas de estado requer a escrita de algum tipo de intérprete para o conteúdo (isso pode ser mais fácil se você tiver reflexo na linguagem que está usando), o que pode ser muito trabalhoso fazer de antemão. Como Fowler aponta, se a sua tabela é separada do seu código, você poderia modificar o comportamento do seu software sem recompilar. Isso 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)

Existe também uma abordagem de interface fluente (também chamada de Domain Specific Language), que é provavelmente facilitada por linguagens que possuem funções de primeira class . A biblioteca Stateless existe e esse blog mostra um exemplo simples com código. Uma implementação Java (pré Java8) é discutida. Eu também recebi um exemplo do Python no GitHub .

Na minha experiência, usar a instrução ‘switch’ é a maneira padrão de lidar com vários estados possíveis. Embora eu esteja surpreso que você está passando um valor de transição para o processamento por estado. Eu pensei que o ponto principal de uma máquina de estado era que cada estado realizasse uma única ação. Em seguida, a próxima ação / input determina em qual novo estado fazer a transição. Então eu teria esperado que cada function de processamento de estado executasse imediatamente o que quer que fosse fixo para entrar no estado e depois decidir se a transição é necessária para outro estado.

Existe um livro intitulado Practical Statecharts in C / C ++ . No entanto, é muito pesado para o que precisamos.

Para o compilador que suporta __COUNTER__ , você pode usá-los para mashines de estado simples (mas grandes).

  #define START 0 #define END 1000 int run = 1; state = START; while(run) { switch (state) { case __COUNTER__: //do something state++; break; case __COUNTER__: //do something if (input) state = END; else state++; break; . . . case __COUNTER__: //do something if (input) state = START; else state++; break; case __COUNTER__: //do something state++; break; case END: //do something run = 0; state = START; break; default: state++; break; } } 

A vantagem de usar __COUNTER__ vez de números codificados é que você pode adicionar estados no meio de outros estados, sem renumerar toda vez tudo. Se o compilador não suporta __COUNTER__ , de um modo limitado, é possível usá-lo com precaução __LINE__

Em C ++, considere o padrão de estado .

Sua pergunta é semelhante a “há um padrão típico de implementação da Base de Dados”? A resposta depende do que você deseja alcançar? Se você quiser implementar uma máquina de estados determinística maior, você pode usar um modelo e um gerador de máquina de estado. Exemplos podem ser vistos em http://www.StateSoft.org – SM Gallery. Janusz Dobrowolski

Em C, para máquinas simples, algo assim é o que geralmente acabo usando.

O FSM orientado a events é descrito por objects de estado (FsmState) associados a uma ação (FsmAction) e transições (FsmEdge) definidas pelo estado atual e por events.

Ele também fornece armazenamento e transmissão de dados de FSM e de usuário para separar informações vinculadas a FSM e vinculadas a usuários e permitir várias instâncias do mesmo FSM (ou seja, usando a mesma descrição, mas transmitindo dados de usuário diferentes).

Eventos são representados por um tipo inteiro (FsmEvent). Valores negativos são reservados pela implementação para permitir events comuns especiais (Reset, None, Any, Empty, End). Eventos não negativos são definidos pelo usuário.

Para simplificar, as transições são listadas em uma matriz e a correspondência é tentada na ordem da matriz, essencialmente fornecendo 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 function de salto, fornecendo assim mais flexibilidade, permitindo o comportamento dynamic do FSM.

Nas descrições de transições, o estado atual A NULL corresponderá a qualquer estado e um evento curinga (Qualquer) corresponderá a qualquer evento. De qualquer forma, o valor real do evento que desencadeou a transição será passado para as funções jump e guard.

Para FSMs complexos, a solução de matriz de borda simples pode se tornar muito ineficiente. Nesse caso, uma function de salto apropriada poderia ser implementada usando o array de arestas e inputs de events convertidas em uma matriz de transição ou listas de adjacências de estado.

As ações de estado devem ser implementadas com uma function reentrante que discrimina entre operações de input de estado (Enter), saída de estado (Leave) e de estado (Estado). Desta forma, informações de estado local podem ser encapsuladas e preservadas com variables ​​de function estática.

Normalmente, as ações de input e saída de estado serão executadas de forma não notável e não retornarão nenhum novo evento (Nenhum). Caso contrário, o novo evento é preso e retornado imediatamente. Isso impedirá efetivamente uma transição caso isso aconteça ao sair do estado atual.

A function de etapa FSM (fsmStep) executará uma única etapa do FSM, usando um novo evento para acionar uma transição ou nenhum evento (Nenhum) para executar a ação no estado atual. A function step retorna um novo evento emitido que pode ser manipulado ou realimentado para o FSM; ou None, Empty e End em caso de nenhum evento, transição não encontrada ou estado final atingido, respectivamente.

 #ifndef FSM_H_ #define FSM_H_ #include  #include  /** 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_ 

Abaixo, há um teste muito simples para obter a ideia de como definir e usar a implementação do FSM. Não há events definidos pelo usuário, apenas dados FSM (strings), a mesma ação de estado para cada estado e uma function de salto compartilhada:

 #include  #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 has the statechart library. http://www.boost.org/doc/libs/1_36_0/libs/statechart/doc/index.html

I can’t speak to the use of it, though. Not used it myself (yet)