Design C-máquina de estado
https://stackoverflow.com/questions/1647631
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Estou a elaboração de um projeto pequeno em C mista e C ++. Estou construindo um estado-máquina pequeno-ish no coração de um dos meu segmento de trabalho.
Eu queria saber se você gurus sobre SO iria partilhar as suas técnicas de design state-máquina.
NOTA:. Estou principalmente depois tentou e técnicas de implementação testados
ATUALIZADO: Com base em toda a grande entrada reunidos no SO, eu tenha resolvido nesta arquitetura:
Solução
As máquinas de estado que eu projetei antes (C, não C ++) têm todos vêm para baixo para uma matriz struct e um loop. A estrutura consiste basicamente de um estado e evento (por look-up) e uma função que retorna o novo estado, algo como:
typedef struct {
int st;
int ev;
int (*fn)(void);
} tTransition;
Em seguida, você define seus estados e eventos com define simples (aqueles 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
Em seguida, você define todas as funções que são chamadas pelas transições:
static int GotKey (void) { ... };
static int FsmError (void) { ... };
Todos estes função são escritos para tirar nenhuma variável e retornar o novo estado da máquina de estado. Neste exemplo variáveis ??globais são usados ??para passar qualquer informação sobre as funções do Estado onde for necessário.
Usando globals não é tão ruim quanto parece, desde o FSM é normalmente trancado dentro de uma única unidade de compilação e todas as variáveis ??são estáticas a essa unidade (que é por isso que eu usei aspas em torno de "global" acima - eles são mais compartilhado dentro do FSM, que verdadeiramente global). Tal como acontece com todos os globals, requer cuidados.
A matriz transições, em seguida, define todas as transições possíveis e as funções que são chamados para as transições (incluindo o catch-all último):
tTransition trans[] = {
{ ST_INIT, EV_KEYPRESS, &GotKey},
: :
{ ST_ANY, EV_ANY, &FsmError}
};
#define TRANS_COUNT (sizeof(trans)/sizeof(*trans))
O que isto significa é:. Se você está no estado ST_INIT e você receber o evento EV_KEYPRESS, fazer uma chamada para GotKey
O funcionamento do FSM, em seguida, tornar-se um ciclo 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 wild-cards, permitindo um evento para chamar uma função não importa o estado atual. EV_ANY também funciona de forma semelhante, permitindo que qualquer evento em um estado específico para chamar uma função.
Ele também pode garantir que, se você chegar ao final da matriz transições, você recebe um erro informando o seu FSM não foi construído corretamente (usando a combinação ST_ANY/EV_ANY.
Eu usei código semelhante para isso em um grande número de projetos de comunicação, tais como uma rápida implementação de pilhas e protocolos de comunicação para sistemas embarcados. A grande vantagem foi a sua simplicidade e relativa facilidade em mudar a matriz de transições.
Não tenho dúvida de que haverá abstrações de nível superior que podem ser mais adequadas hoje em dia, mas eu suspeito que todos eles se resumem a esse mesmo tipo de estrutura.
E, como afirma ldog em um comentário, você pode evitar os globals por completo, passando um ponteiro estrutura para todas as funções (e usando que no ciclo de eventos). Isso permitirá que várias máquinas de estado para executar lado a lado, sem interferências.
Apenas criar um tipo de estrutura que contém os dados específicos da máquina (estado em um mínimo) eo uso que em vez dos globals.
A razão eu raramente feito isso é simplesmente porque a maioria das máquinas de estado que eu escrevi foram Singleton tipos (one-off, pelo processo de arranque, leitura de arquivo de configuração, por exemplo), não precisando correr mais de uma instância. Mas tem valor se você precisa executar mais de um.
Outras dicas
As outras respostas são bons, mas uma implementação muito "leve" Eu usei quando a máquina de estado é parece muito simples como:
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 ... */
}
}
Gostaria de usar este quando a máquina de estado é simples o suficiente para que a abordagem tabela de transição função de ponteiro e Estado é um exagero. Isso é muitas vezes útil para caractere por caractere ou palavra por palavra de análise.
Pardon me para quebrar todas as regras em ciência da computação, mas uma máquina de estado é um dos poucos (eu posso contar apenas dois fora de mão) lugares onde uma declaração goto não só é mais eficiente, mas também faz seu código mais limpo e mais fácil ler. Porque declarações goto são baseados em etiquetas, você pode nomear seus estados, em vez de ter que manter o controle de uma confusão de números ou usar um enum. Ele também faz para um código mais limpo muito desde que você não precisa de toda a cruft extra de ponteiros de função ou grandes declarações switch e enquanto loops. Eu mencionei é mais eficiente também?
Aqui está o que 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 forma eficiente e um que é relativamente fácil de ler e grita com o leitor de 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 de atirar no próprio pé ao fazê-lo.
Você pode considerar o Compiler http://smc.sourceforge.net /
Este utilitário open source esplêndida aceita uma descrição de uma máquina de estado em uma linguagem simples e compila-lo 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 compilação.
A razão para fazer isso, em vez de codificação de mão usando o padrão Estado GoF ou qualquer outra abordagem, é que uma vez que sua máquina de estado é expresso como código, a estrutura subjacente tende a desaparecer sob o peso de clichê que precisa ser gerado para apoie isso. Usando essa abordagem dá-lhe uma excelente separação de interesses, e você manter a estrutura de sua máquina de estado 'visível'. O código gerado automaticamente entra em módulos que você não precisa tocar, de modo que você pode voltar e mexer com a estrutura da máquina do Estado, sem afetar o código de apoio que você escreveu.
Desculpe, estou sendo excesso de entusiasmo, e sem dúvida colocar todos fora. Mas é um utilitário de primeira qualidade, e bem documentada também.
Certifique-se de verificar o trabalho de Miro Samek (blog Estado Espaço , o site Estado Máquinas e Ferramentas ), cujos artigos nos em> Usuários
O site contém uma implementação completa (C / C ++), tanto de código aberto e licença comercial de um quadro estado da máquina (QP Framework) , um manipulador de eventos (QEP) , a ferramenta básica de modelagem (QM) e ferramenta de rastreio (QSpy) que permitem desenhar máquinas de estado, criar código e depuração-los.
O livro contém uma extensa explicação sobre o que / porque da implementação e como usá-lo e também é ótimo material para ganhar a compreensão dos fundamentos de máquinas de estados hierárquicas e finitos.
O site também contém links para vários pacotes de suporte bordo para uso do software com plataformas embarcadas.
Eu fiz algo semelhante ao que paxdiablo descreve, só que em vez de uma matriz de transições de estado / evento, eu configurar uma matriz 2-dimensional de ponteiros de função, com o valor do evento como o índice de um eixo e a corrente valor de estado como o outro. Então eu apenas chamar state = state_table[event][state](params) ea coisa certa acontece. Células representando inválidos combinações / eventos estaduais obter um ponteiro para uma função que diz isso, é claro.
Obviamente, isso só funciona se os valores de estado e de eventos são os dois intervalos contíguos e começam em 0 ou perto o suficiente.
A very nice C ++ máquina de estado "quadro" baseado em modelo é dada por Stefan Heinzmann em sua .
Uma vez que não há link para um download de código completo no artigo, eu tomei a liberdade de colar o código em um projeto e check-out. O material abaixo é testada e inclui os poucos menor, mas peças que faltam praticamente óbvias.
A grande inovação é que o compilador está gerando código muito eficiente. ações de entrada / saída vazias não têm nenhum custo. ações de entrada / saída não vazias são inlined. O compilador também está verificando a integridade do statechart. ações ausentes geram ligando erros. A única coisa que não está preso é o Top::init faltando.
Esta é uma alternativa muito agradável para a implementação de Miro Samek, se você pode viver sem o que está faltando - isto está longe de ser uma implementação completa UML Statechart, embora ele implementa corretamente a semântica da UML, enquanto código de Samek por design não controla ações saída / transição / entrada na ordem correta.
Se este código funciona para o que você precisa fazer, e você tem um compilador decente C ++ para o seu sistema, ele provavelmente irá executar melhor do que a implementação de Miro C / C ++. O compilador gera um achatada, a implementação da máquina O (1) estado de transição para si. Se a auditoria de confirma saída de montagem que as otimizações trabalham como desejado, você chegar perto de desempenho teórico. Melhor parte:. É relativamente pequena, 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 D, class B>
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<D*>(0))) == sizeof(Yes) ? 1 : 0 };
};
template<bool> class Bool {};
// Top State, Composite State and Leaf State
template <typename H>
struct TopState {
typedef H Host;
typedef void Base;
virtual void handler(Host&) const = 0;
virtual unsigned getId() const = 0;
};
template <typename H, unsigned id, typename B>
struct CompState;
template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct CompState : B {
typedef B Base;
typedef CompState<H, id, Base> This;
template <typename X> 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 <typename H>
struct CompState<H, 0, TopState<H> > : TopState<H> {
typedef TopState<H> Base;
typedef CompState<H, 0, Base> This;
template <typename X> void handle(H&, const X&) const {}
static void init(H&); // no implementation
static void entry(H&) {}
static void exit(H&) {}
};
template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct LeafState : B {
typedef H Host;
typedef B Base;
typedef LeafState<H, id, Base> This;
template <typename X> 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 <typename H, unsigned id, typename B>
const LeafState<H, id, B> LeafState<H, id, B>::obj;
// Transition Object
template <typename C, typename S, typename T>
// 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<TargetBase, CurrentBase>::Res,
eS_CB = IsDerivedFrom<S, CurrentBase>::Res,
eS_C = IsDerivedFrom<S, C>::Res,
eC_S = IsDerivedFrom<C, S>::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<true>) {}
static void exitActions(Host&h, Bool<false>) {
C::exit(h);
Tran<CurrentBase, S, T>::exitActions(h, Bool<exitStop>());
}
static void entryActions(Host&, Bool<true>) {}
static void entryActions(Host& h, Bool<false>) {
Tran<CurrentBase, S, T>::entryActions(h, Bool<entryStop>());
C::entry(h);
}
Tran(Host & h) : host_(h) {
exitActions(host_, Bool<false>());
}
~Tran() {
Tran<T, S, T>::entryActions(host_, Bool<false>());
T::init(host_);
}
Host& host_;
};
// Initializer for Compound States
template <typename T>
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 ensaio seguintes.
#include <cstdio>
#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<TestHSM,0> Top;
typedef CompState<TestHSM,1,Top> S0;
typedef CompState<TestHSM,2,S0> S1;
typedef LeafState<TestHSM,3,S1> S11;
typedef CompState<TestHSM,4,S0> S2;
typedef CompState<TestHSM,5,S2> S21;
typedef LeafState<TestHSM,6,S21> 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<TestHSM>& 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<TestHSM>* state_;
Signal sig_;
int foo_;
};
bool testDispatch(char c) {
static TestHSM test;
if (c<'a' || 'h'<c) {
return false;
}
printf("Signal<-%c", c);
test.dispatch((Signal)(c-'a'));
printf("\n");
return true;
}
int main(int, char**) {
testDispatch('a');
testDispatch('e');
testDispatch('e');
testDispatch('a');
testDispatch('h');
testDispatch('h');
return 0;
}
#define HSMHANDLER(State) \
template<> template<typename X> inline void State::handle(TestHSM& h, const X& x) const
HSMHANDLER(S0) {
switch (h.getSig()) {
case E_SIG: { Tran<X, This, S211> t(h);
printf("s0-E;");
return; }
default:
break;
}
return Base::handle(h, x);
}
HSMHANDLER(S1) {
switch (h.getSig()) {
case A_SIG: { Tran<X, This, S1> t(h);
printf("s1-A;"); return; }
case B_SIG: { Tran<X, This, S11> t(h);
printf("s1-B;"); return; }
case C_SIG: { Tran<X, This, S2> t(h);
printf("s1-C;"); return; }
case D_SIG: { Tran<X, This, S0> t(h);
printf("s1-D;"); return; }
case F_SIG: { Tran<X, This, S211> t(h);
printf("s1-F;"); return; }
default: break;
}
return Base::handle(h, x);
}
HSMHANDLER(S11) {
switch (h.getSig()) {
case G_SIG: { Tran<X, This, S211> 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<X, This, S1> t(h);
printf("s2-C"); return; }
case F_SIG: { Tran<X, This, S11> t(h);
printf("s2-F"); return; }
default: break;
}
return Base::handle(h, x);
}
HSMHANDLER(S21) {
switch (h.getSig()) {
case B_SIG: { Tran<X, This, S211> t(h);
printf("s21-B;"); return; }
case H_SIG: if (!h.foo()) {
Tran<X, This, S21> 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<X, This, S21> t(h);
printf("s211-D;"); return; }
case G_SIG: { Tran<X, This, S0> 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<InitState> 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 como para máquinas de estado (pelo menos aqueles para controle de programa) é usar ponteiros de função. Cada estado é representado por uma função diferente. A função recebe um símbolo de entrada e retorna o ponteiro de função para o próximo estado. Os monitores de loop de despacho centrais toma a entrada seguinte, que se alimenta ao estado actual, e processa o resultado.
A digitação nele fica um pouco estranho, já que C não tem uma maneira de indicar os tipos de ponteiros de função retornando-se, por isso, as funções estatais retornar void*. Mas você pode fazer algo como isto:
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, as funções de cada estado pode ligar o seu contributo para processo 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: Estado é privado, não só para a unidade de compilação, mas também para o event_handler. casos especiais pode ser tratado separadamente do interruptor principal usando qualquer constructo considerado necessário.
caso mais complexo
Quando o interruptor se torna maior do que um par de telas cheias, dividi-lo em funções que lidam com cada estado, utilizando uma tabela de estado para procurar a função diretamente. O estado ainda é privada para o manipulador de eventos. As funções de manipulador de estado retornar o próximo estado. Se necessário alguns eventos ainda pode receber um tratamento especial no manipulador de eventos principal. Eu gosto de jogar em pseudo-eventos para entrada de estado e de saída e talvez início 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);
}
}
Eu não tenho certeza se eu pregado a sintaxe, especialmente em relação a matriz de ponteiros de função. Eu não executar qualquer um dos isso através de um compilador. Após a revisão, eu notei que eu esqueci de descartar explicitamente o próximo estado ao manusear os eventos pseudo (o parêntese (void) antes da chamada para state_handler ()). Isso é algo que eu gosto de fazer, mesmo se compiladores aceitar a omissão silenciosamente. Ele diz aos leitores do código que "sim, eu de fato quero chamar a função sem usar o valor de retorno", e ele pode parar de ferramentas de análise estática de aviso sobre isso. Pode ser idiossincrática, porque eu não me lembro de ter visto ninguém fazer isso.
Pontos: adicionando um pouco de complexidade (verificando se o próximo estado é diferente do atual), pode evitar código duplicado em outro lugar, porque as funções do identificador de estado podem aproveitar os eventos pseudo que ocorrem quando um estado é inserido e à esquerda. Lembre-se que o estado não pode mudar ao manusear os eventos pseudo, porque o resultado do manipulador de estado é descartado após esses eventos. Você pode naturalmente escolher para modificar o comportamento.
manipulador de estado Uma 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 compilação ficar muito grande (o que você sente que é, eu diria cerca de 1000 linhas), colocar cada estado manipulador em um arquivo separado. Quando cada manipulador de Estado torna-se mais do que um par de telas, dividir cada evento em uma função separada, similar à maneira que o interruptor de Estado foi dividido. Você pode fazer isso em um número de maneiras, separadamente do estado ou usando uma tabela comum, ou combinar vários esquemas. Alguns deles foram abordados aqui por outros. Classificar suas tabelas e usar busca binária se a velocidade é uma exigência.
Programação genérica
Gostaria que o pré-processador para lidar com questões como a ordenação mesas ou até mesmo a geração de máquinas de estado a partir de descrições, permitindo-lhe "programas escrever sobre programas". Eu acredito que este é o que as pessoas estão explorando impulso C ++ modelos para, mas acho que a enigmática sintaxe.
tabelas bidimensionais
Eu tenho usado mesas estado / evento no passado, mas eu tenho que dizer que, para os casos mais simples eu não encontrá-los necessário e eu prefiro a clareza e legibilidade da instrução switch mesmo que não estender a tela de um passado cheio. Para os casos mais complexos as mesas rapidamente sair da mão como os outros. As expressões idiomáticas que apresento aqui permitem que você adicione uma série de eventos e estados quando você sentir como ele, sem ter que manter uma tabela de memória consome (mesmo que pode ser memória de programa).
Aviso
necessidades especiais podem tornar essas expressões menos útil, mas eu descobri que eles sejam muito clara e de fácil manutenção.
Extremamente testado, mas divertido de código, agora em uma versão mais refinada do que a minha resposta original; up-to-date versões 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 <stdio.h>
#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 resposta de paxdiable e decidiu implementar todos os recursos que faltam para a minha candidatura como variáveis ??de guarda e dados de máquina específicos estaduais.
Eu enviei o meu aplicação a este site para compartilhar com a comunidade. Ele foi testado usando IAR Embedded Workbench para ARM.
Outra ferramenta open source interessante é Yakindu Statechart Ferramentas na statecharts.org . Ele faz uso de diagrama de estados Harel e, assim, fornece estados hierárquicos e paralelas e gera C e C ++ (bem como Java) de código. Não faz uso de bibliotecas, mas segue uma abordagem 'código plain'. O código basicamente aplica estruturas switch-caso. Os geradores de código também pode ser personalizado. Além disso, a ferramenta fornece muitos outros recursos.
Vindo para esta tarde (como de costume), mas examinando as respostas até o momento I acha que algo importante está faltando;
Eu encontrei em meus próprios projetos que ele pode ser muito útil para não tem uma função para cada combinação de estado / evento válido. Eu gosto da idéia de ter efetivamente uma tabela 2D de estados / eventos. Mas eu como os elementos da tabela a ser mais do que um ponteiro de função simples. Em vez disso eu tento organizar meu projeto de modo a que o coração que compreende um grupo de elementos ou ações atômicas simples. Dessa forma eu posso listar os elementos atômicos simples em cada intersecção da minha tabela de estado / evento. A idéia é que você não tem que definir uma massa de N ao quadrado funções (tipicamente muito simples). Por que algo tão propenso a erros, demorado, difícil de escrever, difícil de ler, o nome dele?
Eu também incluir um novo estado opcional e um ponteiro de função opcional para cada célula na tabela. O ponteiro de função existe para casos excepcionais em que você não quer ao fogo apenas fora de uma lista de ações atômicas.
Você sabe que você está fazendo certo quando você pode expressar uma série de funcionalidades diferentes, apenas editando sua mesa, sem novo código para escrever.
Alrght, eu acho que o meu é apenas um pouco diferente de todos os demais. Um pouco mais separação de código e dados que eu vejo em outras respostas. Eu realmente ler sobre a teoria para escrever este, que implementa uma linguagem regular completa (sem expressões regulares, infelizmente). Ullman, Minsky, Chomsky. Não posso dizer que entendeu tudo, mas eu desenhei dos velhos mestres forma mais direta possível:. através de suas palavras
Eu uso um ponteiro de função a um predicado que determina a transição para um estado 'sim' ou um estado 'não'. Isso facilita a criação de um aceitante de estados finitos para uma linguagem regular que você programar de uma forma mais assembly-language-like. Por favor, não ser put-off por minhas escolhas de nomes bobos. 'Czek' == 'check'. 'Grok' == [ir procurá-lo na Hacker dicionário].
Assim, para cada iteração, czek chama uma função predicado com o caráter atual como argumento. Se os retornos de predicados verdade, o personagem é consumida (o ponteiro avançado) e seguimos a transição 'y' para selecionar o próximo estado. Se os retornos de predicados falsa, o personagem não é consumido e seguimos o 'n' transição. Assim, cada instrução é uma de duas vias ramo! Devo ter sido lendo a história de Mel no momento.
Este código vem direto meu intérprete PostScript , e evoluiu para sua forma atual com muita orientação dos companheiros na comp.lang.c. Desde PostScript basicamente não tem sintaxe (apenas exigindo suportes equilibradas), um accepter regular Idioma como este funciona como o analisador também.
/* 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<i; j++) {
a_put(st, proc, j, a[j]);
}
}
free(a);
return proc;
}
case '/': {
s[1] = (char)next(st,src);
puff(st, s+2, ns-2, src, next, back);
if (s[1] == '/') {
push(consname(st,s+2));
opexec(st, op_cuts.load);
return pop();
}
return cvlit(consname(st,s+1));
}
default: return consname(st,s);
}
return null; /* should be unreachable */
}
/*
Helper function for toke.
Read into buffer any regular characters.
If we read one too many characters, put it back
unless it's whitespace.
*/
int puff (state *st, char *buf, int nbuf,
object *src,
int (*next)(state *,object *),
void (*back)(state *,int, object *)) {
int c;
char *s = buf;
while (isreg(c=next(st,src))) {
if (s-buf >= 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 vem com 2 diferentes implementações gráfico estado:
Como sempre, boost vontade feixe no inferno modelo.
A primeira biblioteca é para mais máquinas de estado de desempenho crítico. A segunda biblioteca dá-lhe um caminho de transição direta de um UML Statechart ao código.
Aqui está a pergunta SO pedindo uma comparação entre os dois onde ambos da respondem autores.
Esta série de mensagens Ars OpenForum sobre um pouco um pouco complicado de lógica de controle inclui uma implementação de fácil acompanhamento muito como uma máquina de estado em C.
Vi isso em algum lugar
#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);
}
}
Uma vez que você significa que você pode usar C ++ e, portanto, código OO, gostaria de sugerir a avaliação da 'padrão GoF'state (GoF = Gang of Four, os caras que escreveram o livro padrões de projeto que trouxe padrões de design para a ribalta).
Não é particularmente complexo e é amplamente utilizado e discutido por isso é fácil ver exemplos e explicações na linha.
Ele também bastante provável ser reconhecível por qualquer outra pessoa manter seu código em uma data posterior.
Se a eficiência é a preocupação, que valeria a pena realmente o benchmarking para se certificar de que uma abordagem não OO é mais eficiente, pois muitos fatores afetam o desempenho e nem sempre é simplesmente mau OO, código funcional boa. Da mesma forma, se o uso de memória é um constrangimento para você é mais uma vez vale a pena fazer alguns testes ou cálculos para ver se isso vai realmente ser um problema para sua aplicação específica, se você usar o padrão do estado.
A seguir estão alguns links para o padrão de estado 'Gof', como Craig sugere:
A sua pergunta é bastante genérico,
Aqui estão dois artigos de referência que possa ser útil,
-
incorporado Implementação Máquina de Estado
Este artigo descreve uma abordagem simples para implementar uma máquina de estado para um sistema embarcado. Para os fins deste artigo, uma máquina de estado é definido como um algoritmo que pode estar em um de um pequeno número de estados. Um estado é uma condição que causa uma relação prescrita de entradas e saídas, e de insumos para a próxima estados.
Um leitor mais experiente vai rapidamente notar que as máquinas de estado descritos neste artigo são máquinas Mealy. Uma máquina Mealy é uma máquina de estado em que as saídas são uma função tanto da presente estado e de entrada, ao contrário de uma máquina de Moore, na qual as saídas são uma função única de estado.- Codificação Estado Machines em C e C ++
A minha preocupação neste artigo é com os fundamentos do Estado-máquina e algumas orientações de programação simples para codificação de máquinas de estado em C ou C ++. Espero que estas técnicas simples podem se tornar mais comuns, de modo que você (e outros) podem facilmente ver a estrutura certa state-máquina a partir do código fonte.
- Codificação Estado Machines em C e C ++
Eu tenho usado State Machine Compiler em projetos Java e Python para com sucesso.
Este é um post antigo, com muitas respostas, mas eu pensei que eu ia acrescentar a minha própria abordagem para a máquina de estado finito em C. Eu fiz um script Python para produzir o código C esqueleto para qualquer número de estados. Esse script está documentado no GituHub em FsmTemplateC
Este exemplo é baseado em outras abordagens que eu li sobre. Ele não usa Goto ou interruptor declarações mas tem funções de transição em uma matriz de ponteiro (tabela look-up). O código depende de uma grande multi-linha initializer (inicializadores designados e literais compostos) macro e C99 apresenta então se você não gosta dessas coisas, você pode não gostar desta abordagem.
Aqui está um script Python de um catraca exemplo que gera-código C esqueleto usando 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)
O cabeçalho de saída gerado contém os 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é usado para determinar se uma transição foi bloqueada comEFSM_TURNSTILE_TR_RETREAT, permitida a progressão comEFSM_TURNSTILE_TR_ADVANCE, ou a chamada de função não foi precedida de uma transição comEFSM_TURNSTILE_TR_CONTINUE. - enum
eFsmTurnstileStateé simplesmente a lista de estados. - enum
eFsmTurnstileInputé simplesmente a lista de entradas. - O struct
FsmTurnstileé o coração da máquina do Estado com o cheque de transição, tabela de pesquisa função, estado atual, estado ordenado, e um alias para a função principal que é executado na máquina. - Cada ponteiro de função (alias) em
FsmTurnstilesó deve ser chamado a partir do struct e tem que ter a sua primeira entrada como um ponteiro para si, de modo a manter um estado, estilo persistente orientada a objetos.
Agora, para as declarações de função no cabeçalho:
/* 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);
Nomes de funções são no {prefix}_{from}_{to} formato, onde {from} é o (atual) estado anterior e {to} é o próximo estado. Note-se que se a tabela de transição não permite certas transições, um ponteiro NULL em vez de um ponteiro de função será definido. Finalmente, a mágica acontece com uma macro. Aqui vamos construir a tabela de transição (matriz de enums estaduais) e as funções de transição de estado olhar para cima da tabela (uma matriz de ponteiros de função):
/* 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 \
}
Ao criar o FSM, o FSM_EXAMPLE_CREATE() macro tem que ser usado.
Agora, no código fonte cada função de transição de estado declarou acima devem ser preenchidos. A estrutura FsmTurnstileFopts pode ser usado para transmitir dados de / para a máquina de estado. Cada transição conjunto must fsm->check para ser igual, quer EFSM_EXAMPLE_TR_RETREAT para bloqueá-lo de transição ou EFSM_EXAMPLE_TR_ADVANCE para permitir a transição para o estado comandada.
Um exemplo de trabalho podem ser encontrados no (FsmTemplateC) [ https://github.com/ChisholmKyle/FsmTemplateC].
Aqui está o uso real muito simples em seu código:
/* 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);
}
Tudo o que negócio cabeçalho e todas essas funções apenas para ter uma interface rápida simples e vale a pena em minha mente.
Você pode usar a biblioteca de código aberto OpenFST .
OpenFst é uma biblioteca para a construção, combinando, otimização e busca ponderada transdutores de estado finito (STFC). Ponderadas transdutores de estado finito são autómatos onde cada transição possui uma etiqueta de entrada, um rótulo de saída, e um peso. O mais familiar aceitador de estado finito é representado como um transdutor com etiqueta entrada e saída de cada transição igual. aceitantes de estado finito são usados ??para representar conjuntos de cordas (especificamente, conjuntos regulares ou racionais); transdutores de estado finito são usados ??para representar as relações binárias entre pares de cordas (especificamente, transduções racionais). Os pesos podem ser utilizados para representar o custo de tomar uma transição particular.
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;
}
Eu pessoalmente uso auto referenciando estruturas em combinação com matrizes ponteiro. Fiz upload de um tutorial no github um tempo atrás, link:
https://github.com/mmelchger/polling_state_machine_c
Nota: Eu reconheço que esta discussão é bastante antiga, mas espero que para obter a entrada e pensamentos sobre a concepção do Estado-máquina, bem como ser capaz de fornecer um exemplo para um design state-máquina possível em C.
Aqui está um exemplo de uma máquina de estados finitos para Linux que usa filas de mensagens como os eventos. Os eventos são colocados em fila e tratadas em ordem. As mudanças de estado, dependendo do que acontece para cada evento.
Este é um exemplo de uma conexão de dados com estados como:
- Uninitialized
- Initialized
- Ligado
- MTU negociação
- autenticados
Um pouco recurso extra eu adicionei foi um timestamp para cada mensagem / evento. O manipulador de eventos irá ignorar eventos que são muito antigas (que tenham expirado). Isso pode acontecer muito no mundo real, onde você pode ficar preso em um estado de forma inesperada.
Este exemplo é executado em Linux, use a Makefile abaixo para compilá-lo e brincar com ele.
state_machine.c
#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <unistd.h> // sysconf()
#include <errno.h> // errno
#include <string.h> // strerror()
#include <sys/time.h> // gettimeofday()
#include <fcntl.h> // For O_* constants
#include <sys/stat.h> // For mode constants
#include <mqueue.h>
#include <poll.h>
//------------------------------------------------
// States
//------------------------------------------------
typedef enum
{
ST_UNKNOWN = 0,
ST_UNINIT,
ST_INIT,
ST_CONNECTED,
ST_MTU_NEGOTIATED,
ST_AUTHENTICATED,
ST_ERROR,
ST_DONT_CHANGE,
ST_TERM,
} fsmState_t;
//------------------------------------------------
// Events
//------------------------------------------------
typedef enum
{
EV_UNKNOWN = 0,
EV_INIT_SUCCESS,
EV_INIT_FAIL,
EV_MASTER_CMD_MSG,
EV_CONNECT_SUCCESS,
EV_CONNECT_FAIL,
EV_MTU_SUCCESS,
EV_MTU_FAIL,
EV_AUTH_SUCCESS,
EV_AUTH_FAIL,
EV_TX_SUCCESS,
EV_TX_FAIL,
EV_DISCONNECTED,
EV_DISCON_FAILED,
EV_LAST_ENTRY,
} fsmEvName_t;
typedef struct fsmEvent_type
{
fsmEvName_t name;
struct timeval genTime; // Time the event was generated.
// This allows us to see how old the event is.
} fsmEvent_t;
// Finite State Machine Data Members
typedef struct fsmData_type
{
int connectTries;
int MTUtries;
int authTries;
int txTries;
} fsmData_t;
// Each row of the state table
typedef struct stateTable_type {
fsmState_t st; // Current state
fsmEvName_t evName; // Got this event
int (*conditionfn)(void *); // If this condition func returns TRUE
fsmState_t nextState; // Change to this state and
void (*fn)(void *); // Run this function
} stateTable_t;
// Finite State Machine state structure
typedef struct fsm_type
{
const stateTable_t *pStateTable; // Pointer to state table
int numStates; // Number of entries in the table
fsmState_t currentState; // Current state
fsmEvent_t currentEvent; // Current event
fsmData_t *fsmData; // Pointer to the data attributes
mqd_t mqdes; // Message Queue descriptor
mqd_t master_cmd_mqdes; // Master command message queue
} fsm_t;
// Wildcard events and wildcard state
#define EV_ANY -1
#define ST_ANY -1
#define TRUE (1)
#define FALSE (0)
// Maximum priority for message queues (see "man mq_overview")
#define FSM_PRIO (sysconf(_SC_MQ_PRIO_MAX) - 1)
static void addev (fsm_t *fsm, fsmEvName_t ev);
static void doNothing (void *fsm) {addev(fsm, EV_MASTER_CMD_MSG);}
static void doInit (void *fsm) {addev(fsm, EV_INIT_SUCCESS);}
static void doConnect (void *fsm) {addev(fsm, EV_CONNECT_SUCCESS);}
static void doMTU (void *fsm) {addev(fsm, EV_MTU_SUCCESS);}
static void reportFailConnect (void *fsm) {addev(fsm, EV_ANY);}
static void doAuth (void *fsm) {addev(fsm, EV_AUTH_SUCCESS);}
static void reportDisConnect (void *fsm) {addev(fsm, EV_ANY);}
static void doDisconnect (void *fsm) {addev(fsm, EV_ANY);}
static void doTransaction (void *fsm) {addev(fsm, EV_TX_FAIL);}
static void fsmError (void *fsm) {addev(fsm, EV_ANY);}
static int currentlyLessThanMaxConnectTries (void *fsm) {
fsm_t *l = (fsm_t *)fsm;
return (l->fsmData->connectTries < 5 ? TRUE : FALSE);
}
static int isMoreThanMaxConnectTries (void *fsm) {return TRUE;}
static int currentlyLessThanMaxMTUtries (void *fsm) {return TRUE;}
static int isMoreThanMaxMTUtries (void *fsm) {return TRUE;}
static int currentyLessThanMaxAuthTries (void *fsm) {return TRUE;}
static int isMoreThanMaxAuthTries (void *fsm) {return TRUE;}
static int currentlyLessThanMaxTXtries (void *fsm) {return FALSE;}
static int isMoreThanMaxTXtries (void *fsm) {return TRUE;}
static int didNotSelfDisconnect (void *fsm) {return TRUE;}
static int waitForEvent (fsm_t *fsm);
static void runEvent (fsm_t *fsm);
static void runStateMachine(fsm_t *fsm);
static int newEventIsValid(fsmEvent_t *event);
static void getTime(struct timeval *time);
void printState(fsmState_t st);
void printEvent(fsmEvName_t ev);
// Global State Table
const stateTable_t GST[] = {
// Current state Got this event If this condition func returns TRUE Change to this state and Run this function
{ ST_UNINIT, EV_INIT_SUCCESS, NULL, ST_INIT, &doNothing },
{ ST_UNINIT, EV_INIT_FAIL, NULL, ST_UNINIT, &doInit },
{ ST_INIT, EV_MASTER_CMD_MSG, NULL, ST_INIT, &doConnect },
{ ST_INIT, EV_CONNECT_SUCCESS, NULL, ST_CONNECTED, &doMTU },
{ ST_INIT, EV_CONNECT_FAIL, ¤tlyLessThanMaxConnectTries, ST_INIT, &doConnect },
{ ST_INIT, EV_CONNECT_FAIL, &isMoreThanMaxConnectTries, ST_INIT, &reportFailConnect },
{ ST_CONNECTED, EV_MTU_SUCCESS, NULL, ST_MTU_NEGOTIATED, &doAuth },
{ ST_CONNECTED, EV_MTU_FAIL, ¤tlyLessThanMaxMTUtries, ST_CONNECTED, &doMTU },
{ ST_CONNECTED, EV_MTU_FAIL, &isMoreThanMaxMTUtries, ST_CONNECTED, &doDisconnect },
{ ST_CONNECTED, EV_DISCONNECTED, &didNotSelfDisconnect, ST_INIT, &reportDisConnect },
{ ST_MTU_NEGOTIATED, EV_AUTH_SUCCESS, NULL, ST_AUTHENTICATED, &doTransaction },
{ ST_MTU_NEGOTIATED, EV_AUTH_FAIL, ¤tyLessThanMaxAuthTries, ST_MTU_NEGOTIATED, &doAuth },
{ ST_MTU_NEGOTIATED, EV_AUTH_FAIL, &isMoreThanMaxAuthTries, ST_MTU_NEGOTIATED, &doDisconnect },
{ ST_MTU_NEGOTIATED, EV_DISCONNECTED, &didNotSelfDisconnect, ST_INIT, &reportDisConnect },
{ ST_AUTHENTICATED, EV_TX_SUCCESS, NULL, ST_AUTHENTICATED, &doDisconnect },
{ ST_AUTHENTICATED, EV_TX_FAIL, ¤tlyLessThanMaxTXtries, ST_AUTHENTICATED, &doTransaction },
{ ST_AUTHENTICATED, EV_TX_FAIL, &isMoreThanMaxTXtries, ST_AUTHENTICATED, &doDisconnect },
{ ST_AUTHENTICATED, EV_DISCONNECTED, &didNotSelfDisconnect, ST_INIT, &reportDisConnect },
{ ST_ANY, EV_DISCON_FAILED, NULL, ST_DONT_CHANGE, &doDisconnect },
{ ST_ANY, EV_ANY, NULL, ST_UNINIT, &fsmError } // Wildcard state for errors
};
#define GST_COUNT (sizeof(GST)/sizeof(stateTable_t))
int main()
{
int ret = 0;
fsmData_t dataAttr;
dataAttr.connectTries = 0;
dataAttr.MTUtries = 0;
dataAttr.authTries = 0;
dataAttr.txTries = 0;
fsm_t lfsm;
memset(&lfsm, 0, sizeof(fsm_t));
lfsm.pStateTable = GST;
lfsm.numStates = GST_COUNT;
lfsm.currentState = ST_UNINIT;
lfsm.currentEvent.name = EV_ANY;
lfsm.fsmData = &dataAttr;
struct mq_attr attr;
attr.mq_maxmsg = 30;
attr.mq_msgsize = sizeof(fsmEvent_t);
// Dev info
//printf("Size of fsmEvent_t [%ld]\n", sizeof(fsmEvent_t));
ret = mq_unlink("/abcmq");
if (ret == -1) {
fprintf(stderr, "Error on mq_unlink(), errno[%d] strerror[%s]\n",
errno, strerror(errno));
}
lfsm.mqdes = mq_open("/abcmq", O_CREAT | O_RDWR, S_IWUSR | S_IRUSR, &attr);
if (lfsm.mqdes == (mqd_t)-1) {
fprintf(stderr, "Error on mq_open(), errno[%d] strerror[%s]\n",
errno, strerror(errno));
return -1;
}
doInit(&lfsm); // This will generate the first event
runStateMachine(&lfsm);
return 0;
}
static void runStateMachine(fsm_t *fsm)
{
int ret = 0;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
// Cycle through the state machine
while (fsm->currentState != ST_TERM) {
printf("current state [");
printState(fsm->currentState);
printf("]\n");
ret = waitForEvent(fsm);
if (ret == 0) {
printf("got event [");
printEvent(fsm->currentEvent.name);
printf("]\n");
runEvent(fsm);
}
sleep(2);
}
}
static int waitForEvent(fsm_t *fsm)
{
//const int numFds = 2;
const int numFds = 1;
struct pollfd fds[numFds];
int timeout_msecs = -1; // -1 is forever
int ret = 0;
int i = 0;
ssize_t num = 0;
fsmEvent_t newEv;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return -1;
}
fsm->currentEvent.name = EV_ANY;
fds[0].fd = fsm->mqdes;
fds[0].events = POLLIN;
//fds[1].fd = fsm->master_cmd_mqdes;
//fds[1].events = POLLIN;
ret = poll(fds, numFds, timeout_msecs);
if (ret > 0) {
// An event on one of the fds has occurred
for (i = 0; i < numFds; i++) {
if (fds[i].revents & POLLIN) {
// Data may be read on device number i
num = mq_receive(fds[i].fd, (void *)(&newEv),
sizeof(fsmEvent_t), NULL);
if (num == -1) {
fprintf(stderr, "Error on mq_receive(), errno[%d] "
"strerror[%s]\n", errno, strerror(errno));
return -1;
}
if (newEventIsValid(&newEv)) {
fsm->currentEvent = newEv;
} else {
return -1;
}
}
}
} else {
fprintf(stderr, "Error on poll(), ret[%d] errno[%d] strerror[%s]\n",
ret, errno, strerror(errno));
return -1;
}
return 0;
}
static int newEventIsValid(fsmEvent_t *event)
{
if (event == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return FALSE;
}
printf("[%s]\n", __func__);
struct timeval now;
getTime(&now);
if ( (event->name < EV_LAST_ENTRY) &&
((now.tv_sec - event->genTime.tv_sec) < (60*5))
)
{
return TRUE;
} else {
return FALSE;
}
}
//------------------------------------------------
// Performs event handling on the FSM (finite state machine).
// Make sure there is a wildcard state at the end of
// your table, otherwise; the event will be ignored.
//------------------------------------------------
static void runEvent(fsm_t *fsm)
{
int i;
int condRet = 0;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
printf("[%s]\n", __func__);
// Find a relevant entry for this state and event
for (i = 0; i < fsm->numStates; i++) {
// Look in the table for our current state or ST_ANY
if ( (fsm->pStateTable[i].st == fsm->currentState) ||
(fsm->pStateTable[i].st == ST_ANY)
)
{
// Is this the event we are looking for?
if ( (fsm->pStateTable[i].evName == fsm->currentEvent.name) ||
(fsm->pStateTable[i].evName == EV_ANY)
)
{
if (fsm->pStateTable[i].conditionfn != NULL) {
condRet = fsm->pStateTable[i].conditionfn(fsm->fsmData);
}
// See if there is a condition associated
// or we are not looking for any condition
//
if ( (condRet != 0) || (fsm->pStateTable[i].conditionfn == NULL))
{
// Set the next state (if applicable)
if (fsm->pStateTable[i].nextState != ST_DONT_CHANGE) {
fsm->currentState = fsm->pStateTable[i].nextState;
printf("new state [");
printState(fsm->currentState);
printf("]\n");
}
// Call the state callback function
fsm->pStateTable[i].fn(fsm);
break;
}
}
}
}
}
//------------------------------------------------
// EVENT HANDLERS
//------------------------------------------------
static void getTime(struct timeval *time)
{
if (time == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
printf("[%s]\n", __func__);
int ret = gettimeofday(time, NULL);
if (ret != 0) {
fprintf(stderr, "gettimeofday() failed: errno [%d], strerror [%s]\n",
errno, strerror(errno));
memset(time, 0, sizeof(struct timeval));
}
}
static void addev (fsm_t *fsm, fsmEvName_t ev)
{
int ret = 0;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
printf("[%s] ev[%d]\n", __func__, ev);
if (ev == EV_ANY) {
// Don't generate a new event, just return...
return;
}
fsmEvent_t newev;
getTime(&(newev.genTime));
newev.name = ev;
ret = mq_send(fsm->mqdes, (void *)(&newev), sizeof(fsmEvent_t), FSM_PRIO);
if (ret == -1) {
fprintf(stderr, "[%s] mq_send() failed: errno [%d], strerror [%s]\n",
__func__, errno, strerror(errno));
}
}
//------------------------------------------------
// end EVENT HANDLERS
//------------------------------------------------
void printState(fsmState_t st)
{
switch(st) {
case ST_UNKNOWN:
printf("ST_UNKNOWN");
break;
case ST_UNINIT:
printf("ST_UNINIT");
break;
case ST_INIT:
printf("ST_INIT");
break;
case ST_CONNECTED:
printf("ST_CONNECTED");
break;
case ST_MTU_NEGOTIATED:
printf("ST_MTU_NEGOTIATED");
break;
case ST_AUTHENTICATED:
printf("ST_AUTHENTICATED");
break;
case ST_ERROR:
printf("ST_ERROR");
break;
case ST_TERM:
printf("ST_TERM");
break;
default:
printf("unknown state");
break;
}
}
void printEvent(fsmEvName_t ev)
{
switch (ev) {
case EV_UNKNOWN:
printf("EV_UNKNOWN");
break;
case EV_INIT_SUCCESS:
printf("EV_INIT_SUCCESS");
break;
case EV_INIT_FAIL:
printf("EV_INIT_FAIL");
break;
case EV_MASTER_CMD_MSG:
printf("EV_MASTER_CMD_MSG");
break;
case EV_CONNECT_SUCCESS:
printf("EV_CONNECT_SUCCESS");
break;
case EV_CONNECT_FAIL:
printf("EV_CONNECT_FAIL");
break;
case EV_MTU_SUCCESS:
printf("EV_MTU_SUCCESS");
break;
case EV_MTU_FAIL:
printf("EV_MTU_FAIL");
break;
case EV_AUTH_SUCCESS:
printf("EV_AUTH_SUCCESS");
break;
case EV_AUTH_FAIL:
printf("EV_AUTH_FAIL");
break;
case EV_TX_SUCCESS:
printf("EV_TX_SUCCESS");
break;
case EV_TX_FAIL:
printf("EV_TX_FAIL");
break;
case EV_DISCONNECTED:
printf("EV_DISCONNECTED");
break;
case EV_LAST_ENTRY:
printf("EV_LAST_ENTRY");
break;
default:
printf("unknown event");
break;
}
}
Makefile
CXX = gcc
COMPFLAGS = -c -Wall -g
state_machine: state_machine.o
$(CXX) -lrt state_machine.o -o state_machine
state_machine.o: state_machine.c
$(CXX) $(COMPFLAGS) state_machine.c
clean:
rm state_machine state_machine.o
