Projeto da máquina de estado C

Eu estou criando um pequeno projeto em C e C ++. Eu estou construindo uma pequena máquina de estado no coração de um dos meus threads de trabalho.

Eu queria saber se você gurus em SO iria compartilhar suas técnicas de design de máquina de estado.

NOTA: Eu estou principalmente após as técnicas de implementação experimentadas e testadas.

ATUALIZADO: Com base em todas as excelentes informações coletadas sobre o SO, estabeleci essa arquitetura:

insira a descrição da imagem aqui

Máquinas de estado que eu projetei antes (C, não C ++) desceram para uma matriz de struct e um loop. A estrutura consiste basicamente em um estado e evento (para pesquisa) e uma function que retorna o novo estado, algo como:

 typedef struct { int st; int ev; int (*fn)(void); } tTransition; 

Então você define seus estados e events com simples define (os ANY são marcadores especiais, veja abaixo):

 #define ST_ANY -1 #define ST_INIT 0 #define ST_ERROR 1 #define ST_TERM 2 : : #define EV_ANY -1 #define EV_KEYPRESS 5000 #define EV_MOUSEMOVE 5001 

Então você define todas as funções que são chamadas pelas transições:

 static int GotKey (void) { ... }; static int FsmError (void) { ... }; 

Todas essas funções são escritas para não usar variables ​​e retornar o novo estado para a máquina de estados. Neste exemplo, as variables ​​globais são usadas para passar qualquer informação para as funções de estado, quando necessário.

Usar globals não é tão ruim quanto parece, já que o FSM é geralmente trancado dentro de uma única unidade de compilation e todas as variables ​​são estáticas para aquela unidade (é por isso que usei aspas em torno de “global” acima – elas são mais compartilhadas dentro da FSM, do que verdadeiramente global). Tal como acontece com todos os globals, requer cuidados.

A matriz de transições define todas as transições possíveis e as funções que são chamadas para essas transições (incluindo a última captura):

 tTransition trans[] = { { ST_INIT, EV_KEYPRESS, &GotKey}, : : { ST_ANY, EV_ANY, &FsmError} }; #define TRANS_COUNT (sizeof(trans)/sizeof(*trans)) 

O que isso significa é: se você estiver no estado ST_INIT e receber o evento EV_KEYPRESS , faça uma chamada para GotKey .

O funcionamento do FSM torna-se um loop relativamente simples:

 state = ST_INIT; while (state != ST_TERM) { event = GetNextEvent(); for (i = 0; i < TRANS_COUNT; i++) { if ((state == trans[i].st) || (ST_ANY == trans[i].st)) { if ((event == trans[i].ev) || (EV_ANY == trans[i].ev)) { state = (trans[i].fn)(); break; } } } } 

Como mencionado acima, observe o uso de ST_ANY como curingas, permitindo que um evento chame uma function não importando o estado atual. EV_ANY também funciona de forma semelhante, permitindo que qualquer evento em um estado específico chame uma function.

Ele também pode garantir que, se você chegar ao final da matriz de transições, você receberá um erro informando que seu FSM não foi construído corretamente (usando a combinação ST_ANY/EV_ANY .

Eu usei código semelhante para isso em muitos projetos de comunicação, como uma implementação inicial de pilhas de comunicação e protocolos para sistemas embarcados. A grande vantagem foi sua simplicidade e relativa facilidade em mudar o array de transições.

Não tenho dúvidas de que haverá abstrações de alto nível que podem ser mais adequadas hoje em dia, mas suspeito que todas elas se resumem a esse mesmo tipo de estrutura.


E, como afirma ldog em um comentário, você pode evitar os globals ao passar um ponteiro de estrutura para todas as funções (e usar isso no loop de events). Isso permitirá que várias máquinas de estado sejam executadas lado a lado sem interferência.

Basta criar um tipo de estrutura que contenha os dados específicos da máquina (estado no mínimo) e usá-los em vez dos globais.

A razão pela qual eu raramente fiz isso é simplesmente porque a maioria das máquinas de estado que escrevi eram tipos singleton (one-off, at-process-start, leitura de arquivo de configuração, por exemplo), não precisando executar mais de uma instância. . Mas tem valor se você precisar executar mais de um.

As outras respostas são boas, mas uma implementação muito “leve” que usei quando a máquina de estado é muito simples se parece com:

 enum state { ST_NEW, ST_OPEN, ST_SHIFT, ST_END }; enum state current_state = ST_NEW; while (current_state != ST_END) { input = get_input(); switch (current_state) { case ST_NEW: /* Do something with input and set current_state */ break; case ST_OPEN: /* Do something different and set current_state */ break; /* ... etc ... */ } } 

Eu usaria isso quando a máquina de estado fosse simples o suficiente para que o ponteiro de function e a abordagem da tabela de transição de estado fossem exagerados. Isso geralmente é útil para análise de caractere por caractere ou palavra por palavra.

Perdoe-me por quebrar todas as regras da ciência da computação, mas uma máquina de estado é um dos poucos lugares em que uma declaração goto não é apenas mais eficiente, mas também torna seu código mais limpo e mais fácil de ler. Como as instruções goto são baseadas em lables, você pode nomear seus estados em vez de ter que controlar uma confusão de números ou usar um enum. Ele também faz com que o código seja muito mais limpo, já que você não precisa de todo o excesso de pointers de function ou de instruções de troca e loops while. Eu mencionei que é mais eficiente também?

Aqui está como uma máquina de estado pode parecer:

 void state_machine() { first_state: // Do some stuff here switch(some_var) { case 0: goto first_state; case 1: goto second_state; default: return; } second_state: // Do some stuff here switch(some_var) { case 0: goto first_state; case 1: goto second_state; default: return; } } 

Você começa a idéia geral. O ponto é que você pode implementar a máquina de estado de uma maneira eficiente e que é relativamente fácil de ler e grita ao leitor que eles estão olhando para uma máquina de estado. Note que se você estiver usando instruções goto , você ainda deve ter cuidado, pois é muito fácil atirar no próprio pé enquanto faz isso.

Você pode considerar o compilador de máquinas de estado http://smc.sourceforge.net/

Este esplêndido utilitário de código aberto aceita uma descrição de uma máquina de estado em um idioma simples e a compila para qualquer um de uma dúzia de idiomas – incluindo C e C ++. O utilitário em si é escrito em Java e pode ser incluído como parte de uma construção.

A razão para fazer isso, em vez de codificar manualmente usando o padrão GoF State ou qualquer outra abordagem, é que uma vez que sua máquina de estado é expressa como código, a estrutura subjacente tende a desaparecer sob o peso do texto padrão que precisa ser gerado para suportá-la. O uso dessa abordagem proporciona uma excelente separação de interesses e mantém a estrutura da sua máquina de estado ‘visível’. O código gerado automaticamente vai para os módulos que você não precisa tocar, para que você possa voltar e mexer com a estrutura da máquina de estado sem afetar o código de suporte que você escreveu.

Desculpe, estou sendo muito entusiasmado e, sem dúvida, afastando todo mundo. Mas é um utilitário de alto nível e bem documentado também.

Não deixe de conferir o trabalho de Miro Samek (blog State Space , site State Machines & Tools ), cujos artigos no C / C ++ Users Journal foram ótimos.

O site contém uma implementação completa (C / C ++) tanto de licença aberta quanto comercial de uma estrutura de máquina de estado (QP Framework) , um manipulador de events (QEP) , uma ferramenta de modelagem básica (QM) e uma ferramenta de rastreamento (QSpy). permite desenhar máquinas de estado, criar código e depurá-los.

O livro contém uma extensa explanação sobre o quê / porquê da implementação e como usá-la e também é um ótimo material para entender os fundamentos das máquinas de estados hieráticos e finitos.

O site também contém links para vários pacotes de suporte do conselho para uso do software com plataformas incorporadas.

Eu fiz algo semelhante ao que paxdiablo descreve, apenas em vez de uma matriz de transições de estado / evento, eu configurei uma matriz bidimensional de pointers de function, com o valor do evento como o índice de um eixo e o valor do estado atual como o outro. Então eu apenas chamo state = state_table[event][state](params) e a coisa certa acontece. Células que representam combinações de estado / evento inválidas obtêm um ponteiro para uma function que diz isso, é claro.

Obviamente, isso só funciona se os valores de estado e evento forem ambos intervalos contíguos e começarem em 0 ou próximos o suficiente.

Uma “estrutura” de máquina de estado C ++ baseada em modelo muito boa é dada por Stefan Heinzmann em seu artigo .

Como não há link para um download de código completo no artigo, tomei a liberdade de colar o código em um projeto e verificá-lo. O material abaixo é testado e inclui as poucas peças menores, mas muito óbvias.

A principal inovação aqui é que o compilador está gerando código muito eficiente. Ações de input / saída vazias não têm custo. As ações de input / saída não vazias estão alinhadas. O compilador também está verificando a integridade do gráfico de estado. As ações ausentes geram erros de vinculação. A única coisa que não é detectada é a falta do Top::init .

Esta é uma alternativa muito legal à implementação de Miro Samek, se você pode viver sem o que está faltando – isso está longe de ser uma implementação completa do UML Statechart, embora implemente corretamente a semântica UML, enquanto o código de Samek não manipula saída / transição / ações de input na ordem correta.

Se este código funcionar para o que você precisa fazer, e você tiver um compilador C ++ decente para o seu sistema, ele provavelmente terá um desempenho melhor do que a implementação C / C ++ de Miro. O compilador gera uma implementação de máquina de estado de transição O (1) achatada para você. Se a auditoria de saída de assembly confirmar que as otimizações funcionam como desejado, você chegará perto do desempenho teórico. Melhor parte: é relativamente pequeno, fácil de entender o código.

 #ifndef HSM_HPP #define HSM_HPP // This code is from: // Yet Another Hierarchical State Machine // by Stefan Heinzmann // Overload issue 64 december 2004 // http://accu.org/index.php/journals/252 /* This is a basic implementation of UML Statecharts. * The key observation is that the machine can only * be in a leaf state at any given time. The composite * states are only traversed, never final. * Only the leaf states are ever instantiated. The composite * states are only mechanisms used to generate code. They are * never instantiated. */ // Helpers // A gadget from Herb Sutter's GotW #71 -- depends on SFINAE template class IsDerivedFrom { class Yes { char a[1]; }; class No { char a[10]; }; static Yes Test(B*); // undefined static No Test(...); // undefined public: enum { Res = sizeof(Test(static_cast(0))) == sizeof(Yes) ? 1 : 0 }; }; template class Bool {}; // Top State, Composite State and Leaf State template  struct TopState { typedef H Host; typedef void Base; virtual void handler(Host&) const = 0; virtual unsigned getId() const = 0; }; template  struct CompState; template  > > struct CompState : B { typedef B Base; typedef CompState This; template  void handle(H& h, const X& x) const { Base::handle(h, x); } static void init(H&); // no implementation static void entry(H&) {} static void exit(H&) {} }; template  struct CompState > : TopState { typedef TopState Base; typedef CompState This; template  void handle(H&, const X&) const {} static void init(H&); // no implementation static void entry(H&) {} static void exit(H&) {} }; template  > > struct LeafState : B { typedef H Host; typedef B Base; typedef LeafState This; template  void handle(H& h, const X& x) const { Base::handle(h, x); } virtual void handler(H& h) const { handle(h, *this); } virtual unsigned getId() const { return id; } static void init(H& h) { h.next(obj); } // don't specialize this static void entry(H&) {} static void exit(H&) {} static const LeafState obj; // only the leaf states have instances }; template  const LeafState LeafState::obj; // Transition Object template  // Current, Source, Target struct Tran { typedef typename C::Host Host; typedef typename C::Base CurrentBase; typedef typename S::Base SourceBase; typedef typename T::Base TargetBase; enum { // work out when to terminate template recursion eTB_CB = IsDerivedFrom::Res, eS_CB = IsDerivedFrom::Res, eS_C = IsDerivedFrom::Res, eC_S = IsDerivedFrom::Res, exitStop = eTB_CB && eS_C, entryStop = eS_C || eS_CB && !eC_S }; // We use overloading to stop recursion. // The more natural template specialization // method would require to specialize the inner // template without specializing the outer one, // which is forbidden. static void exitActions(Host&, Bool) {} static void exitActions(Host&h, Bool) { C::exit(h); Tran::exitActions(h, Bool()); } static void entryActions(Host&, Bool) {} static void entryActions(Host& h, Bool) { Tran::entryActions(h, Bool()); C::entry(h); } Tran(Host & h) : host_(h) { exitActions(host_, Bool()); } ~Tran() { Tran::entryActions(host_, Bool()); T::init(host_); } Host& host_; }; // Initializer for Compound States template  struct Init { typedef typename T::Host Host; Init(Host& h) : host_(h) {} ~Init() { T::entry(host_); T::init(host_); } Host& host_; }; #endif // HSM_HPP 

Código de teste segue.

 #include  #include "hsm.hpp" #include "hsmtest.hpp" /* Implements the following state machine from Miro Samek's * Practical Statecharts in C/C++ * * |-init-----------------------------------------------------| * | s0 | * |----------------------------------------------------------| * | | * | |-init-----------| |-------------------------| | * | | s1 |---c--->| s2 | | * | |----------------|< --c----|-------------------------| | * | | | | | | * |<-d-| |-init-------| | | |-init----------------| | | * | | | s11 |<----f----| | s21 | | | * | /--| |------------| | | |---------------------| | | * | a | | | | | | | | | * | \->| | |------g--------->|-init------| | | | * | | |____________| | | |-b->| s211 |---g--->| * | |----b---^ |------f------->| | | | | * | |________________| | |< -d-|___________|<--e----| * | | |_____________________| | | * | |_________________________| | * |__________________________________________________________| */ class TestHSM; typedef CompState Top; typedef CompState S0; typedef CompState S1; typedef LeafState S11; typedef CompState S2; typedef CompState S21; typedef LeafState S211; enum Signal { A_SIG, B_SIG, C_SIG, D_SIG, E_SIG, F_SIG, G_SIG, H_SIG }; class TestHSM { public: TestHSM() { Top::init(*this); } ~TestHSM() {} void next(const TopState& state) { state_ = &state; } Signal getSig() const { return sig_; } void dispatch(Signal sig) { sig_ = sig; state_->handler(*this); } void foo(int i) { foo_ = i; } int foo() const { return foo_; } private: const TopState* state_; Signal sig_; int foo_; }; bool testDispatch(char c) { static TestHSM test; if (c< 'a' || 'h' template inline void State::handle(TestHSM& h, const X& x) const HSMHANDLER(S0) { switch (h.getSig()) { case E_SIG: { Tran t(h); printf("s0-E;"); return; } default: break; } return Base::handle(h, x); } HSMHANDLER(S1) { switch (h.getSig()) { case A_SIG: { Tran t(h); printf("s1-A;"); return; } case B_SIG: { Tran t(h); printf("s1-B;"); return; } case C_SIG: { Tran t(h); printf("s1-C;"); return; } case D_SIG: { Tran t(h); printf("s1-D;"); return; } case F_SIG: { Tran t(h); printf("s1-F;"); return; } default: break; } return Base::handle(h, x); } HSMHANDLER(S11) { switch (h.getSig()) { case G_SIG: { Tran t(h); printf("s11-G;"); return; } case H_SIG: if (h.foo()) { printf("s11-H"); h.foo(0); return; } break; default: break; } return Base::handle(h, x); } HSMHANDLER(S2) { switch (h.getSig()) { case C_SIG: { Tran t(h); printf("s2-C"); return; } case F_SIG: { Tran t(h); printf("s2-F"); return; } default: break; } return Base::handle(h, x); } HSMHANDLER(S21) { switch (h.getSig()) { case B_SIG: { Tran t(h); printf("s21-B;"); return; } case H_SIG: if (!h.foo()) { Tran t(h); printf("s21-H;"); h.foo(1); return; } break; default: break; } return Base::handle(h, x); } HSMHANDLER(S211) { switch (h.getSig()) { case D_SIG: { Tran t(h); printf("s211-D;"); return; } case G_SIG: { Tran t(h); printf("s211-G;"); return; } } return Base::handle(h, x); } #define HSMENTRY(State) \ template<> inline void State::entry(TestHSM&) { \ printf(#State "-ENTRY;"); \ } HSMENTRY(S0) HSMENTRY(S1) HSMENTRY(S11) HSMENTRY(S2) HSMENTRY(S21) HSMENTRY(S211) #define HSMEXIT(State) \ template<> inline void State::exit(TestHSM&) { \ printf(#State "-EXIT;"); \ } HSMEXIT(S0) HSMEXIT(S1) HSMEXIT(S11) HSMEXIT(S2) HSMEXIT(S21) HSMEXIT(S211) #define HSMINIT(State, InitState) \ template<> inline void State::init(TestHSM& h) { \ Init i(h); \ printf(#State "-INIT;"); \ } HSMINIT(Top, S0) HSMINIT(S0, S1) HSMINIT(S1, S11) HSMINIT(S2, S21) HSMINIT(S21, S211) 

A técnica que eu gosto para máquinas de estado (pelo menos para controle de programa) é usar pointers de function. Cada estado é representado por uma function diferente. A function recebe um símbolo de input e retorna o ponteiro de function para o próximo estado. O monitor central de despacho toma a próxima input, alimenta-a para o estado atual e processa o resultado.

A digitação torna-se um pouco estranha, uma vez que C não tem uma maneira de indicar os tipos de pointers de function retornando, então as funções de estado retornam void* . Mas você pode fazer algo assim:

 typedef void* (*state_handler)(input_symbol_t); void dispatch_fsm() { state_handler current = initial_handler; /* Let's assume returning null indicates end-of-machine */ while (current) { current = current(get_input); } } 

Em seguida, suas funções de estado individuais podem ativar sua input para processar e retornar o valor apropriado.

Caso mais simples

 enum event_type { ET_THIS, ET_THAT }; union event_parm { uint8_t this; uint16_t that; } static void handle_event(enum event_type event, union event_parm parm) { static enum { THIS, THAT } state; switch (state) { case THIS: switch (event) { case ET_THIS: // Handle event. break; default: // Unhandled events in this state. break; } break; case THAT: // Handle state. break; } } 

Pontos: O estado é privado, não apenas para a unidade de compilation, mas também para o event_handler. Casos especiais podem ser tratados separadamente do interruptor principal usando qualquer construção considerada necessária.

Caso mais complexo

Quando o switch fica maior que algumas canvass cheias, divida-o em funções que lidam com cada estado, usando uma tabela de estados para procurar a function diretamente. O estado ainda é privado para o manipulador de events. As funções do manipulador de estado retornam o próximo estado. Se necessário, alguns events ainda podem receber tratamento especial no manipulador de events principal. Eu gosto de jogar em pseudo-events para a input e saída do estado e, talvez, o estado da máquina de estado:

 enum state_type { THIS, THAT, FOO, NA }; enum event_type { ET_START, ET_ENTER, ET_EXIT, ET_THIS, ET_THAT, ET_WHATEVER, ET_TIMEOUT }; union event_parm { uint8_t this; uint16_t that; }; static void handle_event(enum event_type event, union event_parm parm) { static enum state_type state; static void (* const state_handler[])(enum event_type event, union event_parm parm) = { handle_this, handle_that }; enum state_type next_state = state_handler[state](event, parm); if (NA != next_state && state != next_state) { (void)state_handler[state](ET_EXIT, 0); state = next_state; (void)state_handler[state](ET_ENTER, 0); } } 

Não tenho certeza se acertei a syntax, especialmente em relação à matriz de pointers de function. Eu não executei nada disso através de um compilador. Após a revisão, notei que esqueci de descartar explicitamente o próximo estado ao manipular os pseudoevents (o parêntese (vazio) antes da chamada para state_handler ()). Isso é algo que eu gosto de fazer, mesmo se os compiladores aceitarem a omissão silenciosamente. Ele informa aos leitores do código que “sim, eu realmente quis chamar a function sem usar o valor de retorno”, e pode impedir que as ferramentas de análise estática avisem sobre isso. Pode ser idiossincrático porque não me lembro de ter visto mais ninguém fazendo isso.

Pontos: adicionando um pequeno pedaço de complexidade (verificando se o próximo estado é diferente do atual), pode evitar código duplicado em outro lugar, porque as funções do manipulador de estado podem aproveitar os pseudoevents que ocorrem quando um estado é typescript e deixado. Lembre-se de que o estado não pode mudar ao manipular os pseudoevents, porque o resultado do manipulador de estado é descartado após esses events. Você pode, obviamente, optar por modificar o comportamento.

Um manipulador de estado ficaria assim:

 static enum state_type handle_this(enum event_type event, union event_parm parm) { enum state_type next_state = NA; switch (event) { case ET_ENTER: // Start a timer to do whatever. // Do other stuff necessary when entering this state. break; case ET_WHATEVER: // Switch state. next_state = THAT; break; case ET_TIMEOUT: // Switch state. next_state = FOO; break; case ET_EXIT: // Stop the timer. // Generally clean up this state. break; } return next_state; } 

Mais complexidade

Quando a unidade de compilation se torna muito grande (o que você acha que é, devo dizer em torno de 1000 linhas), coloque cada manipulador de estado em um arquivo separado. Quando cada manipulador de estado se torna mais longo que algumas canvass, divida cada evento em uma function separada, semelhante à maneira que a chave de estado foi dividida. Você pode fazer isso de várias maneiras, separadamente do estado ou usando uma tabela comum, ou combinando vários esquemas. Alguns deles foram cobertos aqui por outros. Ordene suas tabelas e use a pesquisa binária se a velocidade for um requisito.

Programação genérica

Eu gostaria que o pré-processador lidasse com problemas como classificar tabelas ou até mesmo gerar máquinas de estado a partir de descrições, permitindo que você “escrevesse programas sobre programas”. Eu acredito que isso é o que as pessoas Boost estão explorando modelos C ++, mas eu acho a syntax enigmática.

Mesas bidimensionais

Eu usei tabelas de estado / evento no passado, mas devo dizer que, nos casos mais simples, não os considero necessários e prefiro a clareza e legibilidade da instrução switch, mesmo que ela ultrapasse uma canvas cheia. Para casos mais complexos, as tabelas rapidamente saem do controle, como outros notaram. Os idiomas que apresento aqui permitem que você adicione uma série de events e estados quando quiser, sem ter que manter uma tabela que consome memory (mesmo que possa ser uma memory de programa).

aviso Legal

Necessidades especiais podem tornar esses idiomas menos úteis, mas eu os achei muito claros e sustentáveis.

Extremamente não testado, mas divertido de codificar, agora em uma versão mais refinada do que a minha resposta original; versões atualizadas podem ser encontradas em mercurial.intuxication.org :

sm.h

 #ifndef SM_ARGS #error "SM_ARGS undefined: " \ "use '#define SM_ARGS (void)' to get an empty argument list" #endif #ifndef SM_STATES #error "SM_STATES undefined: " \ "you must provide a list of comma-separated states" #endif typedef void (*sm_state) SM_ARGS; static const sm_state SM_STATES; #define sm_transit(STATE) ((sm_state (*) SM_ARGS)STATE) #define sm_def(NAME) \ static sm_state NAME ## _fn SM_ARGS; \ static const sm_state NAME = (sm_state)NAME ## _fn; \ static sm_state NAME ## _fn SM_ARGS 

example.c

 #include  #define SM_ARGS (int i) #define SM_STATES EVEN, ODD #include "sm.h" sm_def(EVEN) { printf("even %i\n", i); return ODD; } sm_def(ODD) { printf("odd %i\n", i); return EVEN; } int main(void) { int i = 0; sm_state state = EVEN; for(; i < 10; ++i) state = sm_transit(state)(i); return 0; } 

Eu realmente gostei da resposta do paxdiable e decidi implementar todos os resources que faltavam para o meu aplicativo, como variables ​​de guarda e dados específicos da máquina de estado.

Enviei minha implementação para este site para compartilhar com a comunidade. Foi testado usando o IAR Embedded Workbench for ARM.

https://sourceforge.net/projects/compactfsm/

Another interesting open source tool is Yakindu Statechart Tools on statecharts.org . It makes use of Harel statecharts and thus provides hierarchical and parallel states and generates C and C++ (as well as Java) code. It does not make use of libraries but follows a ‘plain code’ approach. The code basically applies switch-case structures. The code generators can also be customized. Additionally the tool provides many other features.

Coming to this late (as usual) but scanning the answers to date I thinks something important is missing;

I have found in my own projects that it can be very helpful to not have a function for every valid state/event combination. I do like the idea of effectively having a 2D table of states/events. But I like the table elements to be more than a simple function pointer. Instead I try to organize my design so at it’s heart it comprises a bunch of simple atomic elements or actions. That way I can list those simple atomic elements at each intersection of my state/event table. The idea is that you don’t have to define a mass of N squared (typically very simple) functions. Why have something so error-prone, time consuming, hard to write, hard to read, you name it ?

I also include an optional new state, and an optional function pointer for each cell in the table. The function pointer is there for those exceptional cases where you don’t want to just fire off a list of atomic actions.

You know you are doing it right when you can express a lot of different functionality, just by editing your table, with no new code to write.

Alrght, I think mine’s just a little different from everybody else’s. A little more separation of code and data than I see in the other answers. I really read up on the theory to write this, which implements a full Regular-language (without regular expressions, sadly). Ullman, Minsky, Chomsky. Can’t say I understood it all, but I’ve drawn from the old masters as directly as possible: through their words.

I use a function pointer to a predicate that determines the transition to a ‘yes’ state or a ‘no’ state. This facilitates the creation of a finite state acceptor for a regular language that you program in a more assembly-language-like manner. Please don’t be put-off by my silly name choices. ‘czek’ == ‘check’. ‘grok’ == [go look it up in the Hacker Dictionary].

So for each iteration, czek calls a predicate function with the current character as argument. If the predicate returns true, the character is consumed (the pointer advanced) and we follow the ‘y’ transition to select the next state. If the predicate returns false, the character is NOT consumed and we follow the ‘n’ transition. So every instruction is a two-way branch! I must have been reading The Story of Mel at the time.

This code comes straight from my postscript interpreter , and evolved into its current form with much guidance from the fellows on comp.lang.c. Since postscript basically has no syntax (only requiring balanced brackets), a Regular Language Accepter like this functions as the parser as well.

 /* currentstr is set to the start of string by czek and used by setrad (called by israd) to set currentrad which is used by israddig to determine if the character in question is valid for the specified radix -- a little semantic checking in the syntax! */ char *currentstr; int currentrad; void setrad(void) { char *end; currentrad = strtol(currentstr, &end, 10); if (*end != '#' /* just a sanity check, the automaton should already have determined this */ || currentrad > 36 || currentrad < 2) fatal("bad radix"); /* should probably be a simple syntaxerror */ } /* character classes used as tests by automatons under control of czek */ char *alpha = "0123456789" "ABCDE" "FGHIJ" "KLMNO" "PQRST" "UVWXYZ"; #define EQ(a,b) a==b #define WITHIN(a,b) strchr(a,b)!=NULL int israd (int c) { if (EQ('#',c)) { setrad(); return true; } return false; } int israddig(int c) { return strchrnul(alpha,toupper(c))-alpha <= currentrad; } int isdot (int c) {return EQ('.',c);} int ise (int c) {return WITHIN("eE",c);} int issign (int c) {return WITHIN("+-",c);} int isdel (int c) {return WITHIN("()<>[]{}/%",c);} int isreg (int c) {return c!=EOF && !isspace(c) && !isdel(c);} #undef WITHIN #undef EQ /* the automaton type */ typedef struct { int (*pred)(int); int y, n; } test; /* automaton to match a simple decimal number */ /* /^[+-]?[0-9]+$/ */ test fsm_dec[] = { /* 0*/ { issign, 1, 1 }, /* 1*/ { isdigit, 2, -1 }, /* 2*/ { isdigit, 2, -1 }, }; int acc_dec(int i) { return i==2; } /* automaton to match a radix number */ /* /^[0-9]+[#][a-Z0-9]+$/ */ test fsm_rad[] = { /* 0*/ { isdigit, 1, -1 }, /* 1*/ { isdigit, 1, 2 }, /* 2*/ { israd, 3, -1 }, /* 3*/ { israddig, 4, -1 }, /* 4*/ { israddig, 4, -1 }, }; int acc_rad(int i) { return i==4; } /* automaton to match a real number */ /* /^[+-]?(d+(.d*)?)|(d*.d+)([eE][+-]?d+)?$/ */ /* represents the merge of these (simpler) expressions [+-]?[0-9]+\.[0-9]*([eE][+-]?[0-9]+)? [+-]?[0-9]*\.[0-9]+([eE][+-]?[0-9]+)? The complexity comes from ensuring at least one digit in the integer or the fraction with optional sign and optional optionally-signed exponent. So passing isdot in state 3 means at least one integer digit has been found but passing isdot in state 4 means we must find at least one fraction digit via state 5 or the whole thing is a bust. */ test fsm_real[] = { /* 0*/ { issign, 1, 1 }, /* 1*/ { isdigit, 2, 4 }, /* 2*/ { isdigit, 2, 3 }, /* 3*/ { isdot, 6, 7 }, /* 4*/ { isdot, 5, -1 }, /* 5*/ { isdigit, 6, -1 }, /* 6*/ { isdigit, 6, 7 }, /* 7*/ { ise, 8, -1 }, /* 8*/ { issign, 9, 9 }, /* 9*/ { isdigit, 10, -1 }, /*10*/ { isdigit, 10, -1 }, }; int acc_real(int i) { switch(i) { case 2: /* integer */ case 6: /* real */ case 10: /* real with exponent */ return true; } return false; } /* Helper function for grok. Execute automaton against the buffer, applying test to each character: on success, consume character and follow 'y' transition. on failure, do not consume but follow 'n' transition. Call yes function to determine if the ending state is considered an acceptable final state. A transition to -1 represents rejection by the automaton */ int czek (char *s, test *fsm, int (*yes)(int)) { int sta = 0; currentstr = s; while (sta!=-1 && *s) { if (fsm[sta].pred((int)*s)) { sta=fsm[sta].y; s++; } else { sta=fsm[sta].n; } } return yes(sta); } /* Helper function for toke. Interpret the contents of the buffer, trying automatons to match number formats; and falling through to a switch for special characters. Any token consisting of all regular characters that cannot be interpreted as a number is an executable name */ object grok (state *st, char *s, int ns, object *src, int (*next)(state *,object *), void (*back)(state *,int, object *)) { if (czek(s, fsm_dec, acc_dec)) { long num; num = strtol(s,NULL,10); if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) { error(st,limitcheck); /* } else if (num > INT_MAX || num < INT_MIN) { */ /* error(limitcheck, OP_token); */ } else { return consint(num); } } else if (czek(s, fsm_rad, acc_rad)) { long ra,num; ra = (int)strtol(s,NULL,10); if (ra > 36 || ra < 2) { error(st,limitcheck); } num = strtol(strchr(s,'#')+1, NULL, (int)ra); if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) { error(st,limitcheck); /* } else if (num > INT_MAX || num < INT_MAX) { */ /* error(limitcheck, OP_token); */ } else { return consint(num); } } else if (czek(s, fsm_real, acc_real)) { double num; num = strtod(s,NULL); if ((num==HUGE_VAL || num==-HUGE_VAL) && errno==ERANGE) { error(st,limitcheck); } else { return consreal(num); } } else switch(*s) { case '(': { int c, defer=1; char *sp = s; while (defer && (c=next(st,src)) != EOF ) { switch(c) { case '(': defer++; break; case ')': defer--; if (!defer) goto endstring; break; case '\\': c=next(st,src); switch(c) { case '\n': continue; case 'a': c = '\a'; break; case 'b': c = '\b'; break; case 'f': c = '\f'; break; case 'n': c = '\n'; break; case 'r': c = '\r'; break; case 't': c = '\t'; break; case 'v': c = '\v'; break; case '\'': case '\"': case '(': case ')': default: break; } } if (sp-s>ns) error(st,limitcheck); else *sp++ = c; } endstring: *sp=0; return cvlit(consstring(st,s,sp-s)); } case '< ': { int c; char d, *x = "0123456789abcdef", *sp = s; while (c=next(st,src), c!='>' && c!=EOF) { if (isspace(c)) continue; if (isxdigit(c)) c = strchr(x,tolower(c)) - x; else error(st,syntaxerror); d = (char)c < < 4; while (isspace(c=next(st,src))) /*loop*/; if (isxdigit(c)) c = strchr(x,tolower(c)) - x; else error(st,syntaxerror); d |= (char)c; if (sp-s>ns) error(st,limitcheck); *sp++ = d; } *sp = 0; return cvlit(consstring(st,s,sp-s)); } case '{': { object *a; size_t na = 100; size_t i; object proc; object fin; fin = consname(st,"}"); (a = malloc(na * sizeof(object))) || (fatal("failure to malloc"),0); for (i=0 ; objcmp(st,a[i]=toke(st,src,next,back),fin) != 0; i++) { if (i == na-1) (a = realloc(a, (na+=100) * sizeof(object))) || (fatal("failure to malloc"),0); } proc = consarray(st,i); { size_t j; for (j=0; j= nbuf-1) return false; *s++ = c; } *s = 0; if (!isspace(c) && c != EOF) back(st,c,src); /* eat interstice */ return true; } /* Helper function for Stoken Ftoken. Read a token from src using next and back. Loop until having read a bona-fide non-whitespace non-comment character. Call puff to read into buffer up to next delimiter or space. Call grok to figure out what it is. */ #define NBUF MAXLINE object toke (state *st, object *src, int (*next)(state *, object *), void (*back)(state *, int, object *)) { char buf[NBUF] = "", *s=buf; int c,sta = 1; object o; do { c=next(st,src); //if (c==EOF) return null; if (c=='%') { if (DUMPCOMMENTS) fputc(c, stdout); do { c=next(st,src); if (DUMPCOMMENTS) fputc(c, stdout); } while (c!='\n' && c!='\f' && c!=EOF); } } while (c!=EOF && isspace(c)); if (c==EOF) return null; *s++ = c; *s = 0; if (!isdel(c)) sta=puff(st, s,NBUF-1,src,next,back); if (sta) { o=grok(st,buf,NBUF-1,src,next,back); return o; } else { return null; } } 

boost.org comes with 2 different state chart implementations:

  • Meta State Machine
  • Statechart

As always, boost will beam you into template hell.

The first library is for more performance-critical state machines. The second library gives you a direct transition path from a UML Statechart to code.

Here’s the SO question asking for a comparison between the two where both of the authors respond.

This series of Ars OpenForum posts about a somewhat complicated bit of control logic includes a very easy-to-follow implementation as a state machine in C.

Saw this somewhere

 #define FSM #define STATE(x) s_##x : #define NEXTSTATE(x) goto s_##x FSM { STATE(x) { ... NEXTSTATE(y); } STATE(y) { ... if (x == 0) NEXTSTATE(y); else NEXTSTATE(x); } } 

Given that you imply you can use C++ and hence OO code, I would suggest evaluating the ‘GoF’state pattern (GoF = Gang of Four, the guys who wrote the design patterns book which brought design patterns into the limelight).

It is not particularly complex and it is widely used and discussed so it is easy to see examples and explanations on line.

It will also quite likely be recognizable by anyone else maintaining your code at a later date.

If efficiency is the worry, it would be worth actually benchmarking to make sure that a non OO approach is more efficient as lots of factors affect performance and it is not always simply OO bad, functional code good. Similarly, if memory usage is a constraint for you it is again worth doing some tests or calculations to see if this will actually be an issue for your particular application if you use the state pattern.

The following are some links to the ‘Gof’ state pattern, as Craig suggests:

Your question is quite generic,
Here are two reference articles that might be useful,

  1. Embedded State Machine Implementation

    This article describes a simple approach to implementing a state machine for an embedded system. For purposes of this article, a state machine is defined as an algorithm that can be in one of a small number of states. A state is a condition that causes a prescribed relationship of inputs to outputs, and of inputs to next states.
    A savvy reader will quickly note that the state machines described in this article are Mealy machines. A Mealy machine is a state machine where the outputs are a function of both present state and input, as opposed to a Moore machine, in which the outputs are a function only of state.

    • Coding State Machines in C and C++

      My preoccupation in this article is with state-machine fundamentals and some straightforward programming guidelines for coding state machines in C or C++. I hope that these simple techniques can become more common, so that you (and others) can readily see the state-machine structure right from the source code.

I have used State Machine Compiler in Java and Python projects to with success.

This is an old post with lots of answers, but I thought I’d add my own approach to the finite state machine in C. I made a Python script to produce the skeleton C code for any number of states. That script is documented on GituHub at FsmTemplateC

This example is based on other approaches I’ve read about. It doesn’t use goto or switch statements but instead has transition functions in a pointer matrix (look-up table). The code relies on a big multi-line initializer macro and C99 features (designated initializers and compound literals) so if you don’t like these things, you might not like this approach.

Here is a Python script of a turnstile example which generates skeleton C-code using FsmTemplateC :

 # dict parameter for generating FSM fsm_param = { # main FSM struct type string 'type': 'FsmTurnstile', # struct type and name for passing data to state machine functions # by pointer (these custom names are optional) 'fopts': { 'type': 'FsmTurnstileFopts', 'name': 'fopts' }, # list of states 'states': ['locked', 'unlocked'], # list of inputs (can be any length > 0) 'inputs': ['coin', 'push'], # map inputs to commands (next desired state) using a transition table # index of array corresponds to 'inputs' array # for this example, index 0 is 'coin', index 1 is 'push' 'transitiontable': { # current state | 'coin' | 'push' | 'locked': ['unlocked', ''], 'unlocked': [ '', 'locked'] } } # folder to contain generated code folder = 'turnstile_example' # function prefix prefix = 'fsm_turnstile' # generate FSM code code = fsm.Fsm(fsm_param).genccode(folder, prefix) 

The generated output header contains the typedefs:

 /* function options (EDIT) */ typedef struct FsmTurnstileFopts { /* define your options struct here */ } FsmTurnstileFopts; /* transition check */ typedef enum eFsmTurnstileCheck { EFSM_TURNSTILE_TR_RETREAT, EFSM_TURNSTILE_TR_ADVANCE, EFSM_TURNSTILE_TR_CONTINUE, EFSM_TURNSTILE_TR_BADINPUT } eFsmTurnstileCheck; /* states (enum) */ typedef enum eFsmTurnstileState { EFSM_TURNSTILE_ST_LOCKED, EFSM_TURNSTILE_ST_UNLOCKED, EFSM_TURNSTILE_NUM_STATES } eFsmTurnstileState; /* inputs (enum) */ typedef enum eFsmTurnstileInput { EFSM_TURNSTILE_IN_COIN, EFSM_TURNSTILE_IN_PUSH, EFSM_TURNSTILE_NUM_INPUTS, EFSM_TURNSTILE_NOINPUT } eFsmTurnstileInput; /* finite state machine struct */ typedef struct FsmTurnstile { eFsmTurnstileInput input; eFsmTurnstileCheck check; eFsmTurnstileState cur; eFsmTurnstileState cmd; eFsmTurnstileState **transition_table; void (***state_transitions)(struct FsmTurnstile *, FsmTurnstileFopts *); void (*run)(struct FsmTurnstile *, FsmTurnstileFopts *, const eFsmTurnstileInput); } FsmTurnstile; /* transition functions */ typedef void (*pFsmTurnstileStateTransitions)(struct FsmTurnstile *, FsmTurnstileFopts *); 
  • enum eFsmTurnstileCheck is used to determine whether a transition was blocked with EFSM_TURNSTILE_TR_RETREAT , allowed to progress with EFSM_TURNSTILE_TR_ADVANCE , or the function call was not preceded by a transition with EFSM_TURNSTILE_TR_CONTINUE .
  • enum eFsmTurnstileState is simply the list of states.
  • enum eFsmTurnstileInput is simply the list of inputs.
  • The FsmTurnstile struct is the heart of the state machine with the transition check, function lookup table, current state, commanded state, and an alias to the primary function that runs the machine.
  • Every function pointer (alias) in FsmTurnstile should only be called from the struct and has to have its first input as a pointer to itself so as to maintain a persistent state, object-oriented style.

Now for the function declarations in the header:

 /* fsm declarations */ void fsm_turnstile_locked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts); void fsm_turnstile_locked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts); void fsm_turnstile_unlocked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts); void fsm_turnstile_unlocked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts); void fsm_turnstile_run (FsmTurnstile *fsm, FsmTurnstileFopts *fopts, const eFsmTurnstileInput input); 

Function names are in the format {prefix}_{from}_{to} , where {from} is the previous (current) state and {to} is the next state. Note that if the transition table does not allow for certain transitions, a NULL pointer instead of a function pointer will be set. Finally, the magic happens with a macro. Here we build the transition table (matrix of state enums) and the state transition functions look up table (a matrix of function pointers):

 /* creation macro */ #define FSM_TURNSTILE_CREATE() \ { \ .input = EFSM_TURNSTILE_NOINPUT, \ .check = EFSM_TURNSTILE_TR_CONTINUE, \ .cur = EFSM_TURNSTILE_ST_LOCKED, \ .cmd = EFSM_TURNSTILE_ST_LOCKED, \ .transition_table = (eFsmTurnstileState * [EFSM_TURNSTILE_NUM_STATES]) { \ (eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \ EFSM_TURNSTILE_ST_UNLOCKED, \ EFSM_TURNSTILE_ST_LOCKED \ }, \ (eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \ EFSM_TURNSTILE_ST_UNLOCKED, \ EFSM_TURNSTILE_ST_LOCKED \ } \ }, \ .state_transitions = (pFsmTurnstileStateTransitions * [EFSM_TURNSTILE_NUM_STATES]) { \ (pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \ fsm_turnstile_locked_locked, \ fsm_turnstile_locked_unlocked \ }, \ (pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \ fsm_turnstile_unlocked_locked, \ fsm_turnstile_unlocked_unlocked \ } \ }, \ .run = fsm_turnstile_run \ } 

When creating the FSM, the macro FSM_EXAMPLE_CREATE() has to be used.

Now, in the source code every state transition function declared above should be populated. The FsmTurnstileFopts struct can be used to pass data to/from the state machine. Every transition must set fsm->check to be equal to either EFSM_EXAMPLE_TR_RETREAT to block it from transitioning or EFSM_EXAMPLE_TR_ADVANCE to allow it to transition to the commanded state. A working example can be found at (FsmTemplateC)[ https://github.com/ChisholmKyle/FsmTemplateC%5D .

Here is the very simple actual usage in your code:

 /* create fsm */ FsmTurnstile fsm = FSM_TURNSTILE_CREATE(); /* create fopts */ FsmTurnstileFopts fopts = { .msg = "" }; /* initialize input */ eFsmTurnstileInput input = EFSM_TURNSTILE_NOINPUT; /* main loop */ for (;;) { /* wait for timer signal, inputs, interrupts, whatever */ /* optionally set the input (my_input = EFSM_TURNSTILE_IN_PUSH for example) */ /* run state machine */ my_fsm.run(&my_fsm, &my_fopts, my_input); } 

All that header business and all those functions just to have a simple and fast interface is worth it in my mind.

You could use the open source library OpenFST .

OpenFst is a library for constructing, combining, optimizing, and searching weighted finite-state transducers (FSTs). Weighted finite-state transducers are automata where each transition has an input label, an output label, and a weight. The more familiar finite-state acceptor is represented as a transducer with each transition’s input and output label equal. Finite-state acceptors are used to represent sets of strings (specifically, regular or rational sets); finite-state transducers are used to represent binary relations between pairs of strings (specifically, rational transductions). The weights can be used to represent the cost of taking a particular transition.

 void (* StateController)(void); void state1(void); void state2(void); void main() { StateController=&state1; while(1) { (* StateController)(); } } void state1(void) { //do something in state1 StateController=&state2; } void state2(void) { //do something in state2 //Keep changing function direction based on state transition StateController=&state1; } 

I personally use self referencing structs in combination with pointer arrays. I uploaded a tutorial on github a while back, link:

https://github.com/mmelchger/polling_state_machine_c

Note: I do realise that this thread is quite old, but I hope to get input and thoughts on the design of the state-machine as well as being able to provide an example for a possible state-machine design in C.