Konstrukcja maszyny państwowej C [zamknięty]

Tworzę mały projekt w mieszanym C i C ++. Buduję jedną małą maszynę państwową w sercu jednego z moich wątków roboczych.

Zastanawiałem się, czy guru z SO podzieliliby się swoimi technikami projektowania automatu stanów.

UWAGA: Jestem przede wszystkim po wypróbowanych i przetestowanych technikach wdrażania.

ZAKTUALIZOWANO: W oparciu o wszystkie wspaniałe informacje zebrane w SO, zdecydowałem się na tę architekturę:

Maszyny stanowe, które wcześniej projektowałem (C, nie C ++) sprowadzają się do structtablicy i pętli. Struktura składa się zasadniczo ze stanu i zdarzenia (do wyszukiwania) oraz funkcji, która zwraca nowy stan, na przykład:

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

Następnie definiujesz swoje stany i zdarzenia za pomocą prostych definicji ( ANYte są specjalnymi znacznikami, patrz poniżej):

#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

Następnie definiujesz wszystkie funkcje wywoływane przez przejścia:

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

Wszystkie te funkcje są napisane, aby nie pobierać zmiennych i zwracać nowy stan dla automatu stanów. W tym przykładzie zmienne globalne są używane do przekazywania dowolnych informacji do funkcji stanu w razie potrzeby.

Używanie globałów nie jest tak złe, jak się wydaje, ponieważ FSM jest zwykle zamknięty w jednej jednostce kompilacji, a wszystkie zmienne są statyczne dla tej jednostki (dlatego użyłem cudzysłowów wokół „globalnej” powyżej - są one bardziej wspólne w obrębie FSM, niż prawdziwie globalny). Jak w przypadku wszystkich globaliów, wymaga opieki.

Tablica przejść definiuje następnie wszystkie możliwe przejścia i funkcje, które są wywoływane dla tych przejść (w tym ostatnia opcja catch-all):

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

Oznacza to, że jeśli jesteś w ST_INITstanie i odbierasz EV_KEYPRESSwydarzenie, zadzwoń pod numer GotKey.

Działanie FSM staje się wówczas względnie prostą pętlą:

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;
            }
        }
    }
}

Jak wspomniano powyżej, zwróć uwagę na użycie ST_ANYjako symboli wieloznacznych, pozwalających zdarzeniu na wywołanie funkcji bez względu na aktualny stan. EV_ANYdziała również podobnie, pozwalając dowolnemu zdarzeniu w określonym stanie wywołać funkcję.

Może także zagwarantować, że po osiągnięciu końca tablicy przejść pojawi się błąd informujący, że FSM nie został poprawnie zbudowany (za pomocą ST_ANY/EV_ANYkombinacji.

Użyłem podobnego kodu w wielu projektach komunikacyjnych, takich jak wczesna implementacja stosów komunikacyjnych i protokołów dla systemów wbudowanych. Dużą zaletą była jego prostota i względna łatwość zmiany tablicy przejść.

Nie mam wątpliwości, że będą abstrakcje wyższego poziomu, które mogą być bardziej odpowiednie w dzisiejszych czasach, ale podejrzewam, że wszystkie sprowadzą się do tego samego rodzaju struktury.

I, jak ldogstwierdzono w komentarzu, można całkowicie uniknąć globałów, przekazując wskaźnik struktury do wszystkich funkcji (i używając go w pętli zdarzeń). Umożliwi to uruchamianie wielu maszyn stanowych obok siebie bez zakłóceń.

Wystarczy utworzyć typ struktury, który przechowuje dane specyficzne dla maszyny (stan na absolutnym minimum) i użyć tego zamiast globali.

Powodem, dla którego rzadko to robię, jest po prostu dlatego, że większość automatów stanowych, które napisałem, były typami singletonowymi (na przykład jednorazowe uruchomienie na początku procesu, odczyt plików konfiguracyjnych) i nie trzeba uruchamiać więcej niż jednej instancji . Ale ma wartość, jeśli chcesz uruchomić więcej niż jeden.

Inne odpowiedzi są dobre, ale bardzo „lekka” implementacja, której użyłem, gdy automat stanowy jest bardzo prosty, wygląda następująco:

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 ... */
    }
}

Użyłbym tego, gdy automat stanowy jest na tyle prosty, że wskaźnik funkcji i podejście do tabeli przejścia stanu jest nadmierne. Jest to często przydatne do analizowania znak po znaku lub słowo po słowie.

Wybaczcie mi, że złamałem każdą zasadę w informatyce, ale automat stanowy jest jednym z niewielu (mogę policzyć tylko dwa z ręki) miejsc, w których gotoinstrukcja jest nie tylko bardziej wydajna, ale także sprawia, że ​​kod jest czystszy i łatwiejszy do odczytania. Ponieważ gotooświadczenia oparte są na etykietach, możesz nazwać swoje stany zamiast śledzić bałagan liczb lub użyć wyliczenia. Powoduje to również, że kod jest znacznie bardziej przejrzysty, ponieważ nie potrzebujesz wszystkich dodatkowych wskaźników wskaźników funkcji lub dużych instrukcji switch i pętli while. Czy wspominałem, że jest też bardziej wydajny?

Oto jak może wyglądać automat stanowy:

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;
    }
}

Masz ogólny pomysł. Chodzi o to, że można efektywnie zaimplementować maszynę stanu, która jest stosunkowo łatwa do odczytania i krzyczy do czytelnika, że ​​patrzą na maszynę stanu. Pamiętaj, że jeśli używasz gotoinstrukcji, musisz zachować ostrożność, ponieważ bardzo łatwo jest w ten sposób zastrzelić się w stopę.

Możesz rozważyć State Machine Compiler http://smc.sourceforge.net/

To wspaniałe narzędzie typu open source akceptuje opis automatu stanowego w prostym języku i kompiluje go do jednego z kilkunastu języków - w tym C i C ++. Samo narzędzie jest napisane w Javie i może być włączone jako część kompilacji.

Powodem tego jest, zamiast ręcznego kodowania przy użyciu wzorca stanu GoF lub innego podejścia, że ​​po wyrażeniu maszyny stanu jako kodu, podstawowa struktura ma tendencję do znikania pod ciężarem płyty kotłowej, którą należy wygenerować w celu jej obsługi. Korzystanie z tego podejścia zapewnia doskonały rozdział problemów, a struktura maszyny stanowej jest „widoczna”. Automatycznie wygenerowany kod przechodzi do modułów, których nie trzeba dotykać, dzięki czemu można cofać się i bawić ze strukturą automatu stanów bez wpływu na napisany kod pomocniczy.

Przepraszam, jestem zbyt entuzjastyczny i niewątpliwie odkładam wszystkich na później. Jest to jednak narzędzie na najwyższym poziomie i dobrze udokumentowane.

Koniecznie sprawdź pracę Miro Samka (blog State Space , witryna State Machines & Tools ), której artykuły w C / C ++ Users Journal były świetne.

Witryna zawiera pełną implementację (C / C ++) zarówno w licencji open source, jak i komercyjnej frameworka stanowego (QP Framework) , procedury obsługi zdarzeń (QEP) , podstawowego narzędzia do modelowania (QM) i narzędzia śledzenia (QSpy), które pozwalają rysować maszyny stanów, tworzyć kod i debugować je.

Książka zawiera obszerne wyjaśnienie co / dlaczego implementacji i jak z niej korzystać, a także jest świetnym materiałem do zrozumienia podstaw hierachicznych i skończonych maszyn stanów.

Witryna zawiera również łącza do kilku pakietów obsługi płyt głównych do użytku z oprogramowaniem z wbudowanymi platformami.

Zrobiłem coś podobnego do tego, co opisuje paxdiablo, ale zamiast tablicy przejść stanu / zdarzenia ustawiłem dwuwymiarową tablicę wskaźników funkcji, z wartością zdarzenia jako indeksem jednej osi, a bieżącą wartością stanu jako inny. Potem dzwonięstate = state_table[event][state](params) i dzieje się właściwa rzecz. Komórki reprezentujące nieprawidłowe kombinacje stanu / zdarzenia otrzymują oczywiście wskaźnik do funkcji, która tak mówi.

Oczywiście działa to tylko wtedy, gdy wartości stanu i zdarzenia są ciągłymi zakresami i zaczynają się od 0 lub wystarczająco blisko.

Stefan Heinzmann w swoim artykule podał bardzo ładny „szkielet” maszyny stanu C ++ oparty na szablonie .

Ponieważ w artykule nie ma linku do pełnego pobrania kodu, mogłem wkleić kod do projektu i sprawdzić go. Poniższe rzeczy są testowane i obejmują kilka drobnych, ale prawie oczywistych brakujących elementów.

Główną innowacją jest to, że kompilator generuje bardzo wydajny kod. Puste działania wejścia / wyjścia nie wiążą się z żadnymi kosztami. Wstawiane są niepuste operacje wejścia / wyjścia. Kompilator sprawdza również kompletność wykresu statystycznego. Brakujące działania generują błędy łączenia. Jedyne, czego nie złapano, to brakTop::init .

Jest to bardzo fajna alternatywa dla implementacji Miro Samka, jeśli możesz żyć bez tego, czego brakuje - jest to dalekie od pełnej implementacji Statechart UML, chociaż poprawnie implementuje semantykę UML, podczas gdy kod Samka według projektu nie obsługuje wyjścia / przejścia / działania wejściowe we właściwej kolejności.

Jeśli ten kod działa zgodnie z tym, co musisz zrobić, i masz przyzwoity kompilator C ++ dla swojego systemu, prawdopodobnie będzie on działał lepiej niż implementacja Miro C / C ++. Kompilator generuje dla Ciebie spłaszczoną implementację maszyny stanu przejściowego O (1). Jeśli audyt danych wyjściowych zespołu potwierdzi, że optymalizacje działają zgodnie z oczekiwaniami, zbliżasz się do wydajności teoretycznej. Najlepsza część: to stosunkowo niewielki, łatwy do zrozumienia kod.

#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

Kod testowy następuje.

#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)

Techniką, którą lubię dla maszyn stanów (przynajmniej tych do sterowania programem) jest używanie wskaźników funkcji. Każdy stan jest reprezentowany przez inną funkcję. Funkcja przyjmuje symbol wejściowy i zwraca wskaźnik funkcji do następnego stanu. Centralne monitory pętli dyspozytorskiej pobierają kolejne dane wejściowe, przekazują je do bieżącego stanu i przetwarzają wynik.

Pisanie na nim staje się trochę dziwne, ponieważ C nie ma sposobu na wskazanie typów wskaźników funkcji, które same się zwracają, więc funkcje stanu wracają void*. Ale możesz zrobić coś takiego:

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);
    }
 }

Następnie poszczególne funkcje stanu mogą włączyć dane wejściowe do przetworzenia i zwrócić odpowiednią wartość.

Najprostszy przypadek

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;
  }
}

Punkty: stan jest prywatny, nie tylko dla jednostki kompilującej, ale także dla modułu obsługi zdarzeń. Przypadki specjalne mogą być obsługiwane oddzielnie od głównego przełącznika przy użyciu dowolnej konstrukcji uznanej za niezbędną.

Bardziej złożona sprawa

Gdy przełącznik zapełni się więcej niż kilka ekranów, podziel go na funkcje obsługujące każdy stan, używając tabeli stanów do bezpośredniego wyszukiwania funkcji. Stan jest nadal prywatny dla modułu obsługi zdarzeń. Funkcje modułu obsługi stanu zwracają następny stan. W razie potrzeby niektóre zdarzenia mogą być nadal traktowane w głównym module obsługi zdarzeń. Lubię wrzucać pseudo-zdarzenia dla wejścia i wyjścia ze stanu i być może uruchomienie automatu stanów:

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);
  }
}

Nie jestem pewien, czy skompilowałem składnię, zwłaszcza jeśli chodzi o tablicę wskaźników funkcji. Nie uruchomiłem nic z tego przez kompilator. Po przejrzeniu zauważyłem, że zapomniałem jawnie odrzucić następny stan podczas obsługi pseudo zdarzeń (nawias (void) przed wywołaniem funkcji state_handler ()). To jest coś, co lubię robić, nawet jeśli kompilatory po cichu akceptują pominięcie. Mówi czytelnikom kodu, że „tak, naprawdę chciałem wywołać tę funkcję bez użycia wartości zwracanej”, i może powstrzymać ostrzeżenia przed narzędziami analizy statycznej. Może to być idiosynkratyczne, ponieważ nie przypominam sobie, by widział to ktoś inny.

Punkty: dodanie odrobiny złożoności (sprawdzenie, czy następny stan różni się od bieżącego), może uniknąć powielania kodu w innym miejscu, ponieważ funkcje obsługi stanu mogą cieszyć się pseudo zdarzeniami, które występują, gdy stan jest wprowadzany i opuszczany. Pamiętaj, że stan nie może się zmienić podczas obsługi pseudo zdarzeń, ponieważ wynik procedury obsługi stanu jest odrzucany po tych zdarzeniach. Możesz oczywiście zmodyfikować zachowanie.

Procedura obsługi stanu wyglądałaby tak:

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;
}

Większa złożoność

Kiedy jednostka kompilacji staje się zbyt duża (cokolwiek ci się wydaje, powinienem powiedzieć około 1000 wierszy), umieść każdy moduł obsługi stanu w osobnym pliku. Gdy każdy moduł obsługi stanu będzie dłuższy niż kilka ekranów, podziel każde zdarzenie na osobną funkcję, podobnie do sposobu, w jaki przełącznik stanu został podzielony. Możesz to zrobić na wiele sposobów, niezależnie od stanu, używając wspólnej tabeli lub łącząc różne schematy. Niektóre z nich zostały tutaj objęte innymi. Posortuj tabele i użyj wyszukiwania binarnego, jeśli wymagana jest szybkość.

Programowanie ogólne

Chciałbym, aby preprocesor zajął się takimi problemami, jak sortowanie tabel, a nawet generowanie automatów stanów z opisów, umożliwiając „pisanie programów o programach”. Wierzę, że do tego ludzie Boost wykorzystują szablony C ++, ale uważam, że składnia jest tajemnicza.

Stoły dwuwymiarowe

W przeszłości używałem tabel stanu / zdarzeń, ale muszę powiedzieć, że w najprostszych przypadkach nie uważam ich za konieczne i wolę przejrzystość i czytelność instrukcji przełączania, nawet jeśli przekracza ona jeden ekran. W bardziej skomplikowanych przypadkach tabele szybko wymykają się spod kontroli, jak zauważyli inni. Idiomy, które tu przedstawiam, pozwalają dodawać mnóstwo zdarzeń i stanów, kiedy masz na to ochotę, bez konieczności utrzymywania tabeli zajmującej pamięć (nawet jeśli może to być pamięć programu).

Zrzeczenie się

Specjalne potrzeby mogą sprawić, że te idiomy będą mniej przydatne, ale uważam je za bardzo jasne i łatwe do utrzymania.

Niezwykle niesprawdzony, ale przyjemny w kodowaniu, teraz w bardziej dopracowanej wersji niż moja pierwotna odpowiedź; aktualne wersje można znaleźć na stronie 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

przyklad.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;
}

Naprawdę podobała mi się odpowiedź paxdiable i postanowiłem zaimplementować wszystkie brakujące funkcje mojej aplikacji, takie jak zmienne ochronne i dane specyficzne dla maszyny stanów.

Przesłałem moją implementację do tej witryny, aby udostępnić ją społeczności. Został przetestowany przy użyciu IAR Embedded Workbench dla ARM.

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

Innym interesującym narzędziem typu open source jest Yakindu Statechart Tools na statecharts.org . Wykorzystuje wykresy statyczne Harela, a tym samym zapewnia stany hierarchiczne i równoległe oraz generuje kod C i C ++ (a także Java). Nie korzysta z bibliotek, ale stosuje podejście „zwykłego kodu”. Kod zasadniczo stosuje struktury skrzynek rozdzielczych. Generatory kodu można również dostosować. Dodatkowo narzędzie zapewnia wiele innych funkcji.

Przybywając tak późno (jak zwykle), ale skanując dotychczasowe odpowiedzi, myślę, że czegoś ważnego brakuje;

W moich własnych projektach stwierdziłem, że bardzo pomocne może być nie posiadanie funkcji dla każdej prawidłowej kombinacji stanu / zdarzenia. Podoba mi się pomysł efektywnego posiadania dwuwymiarowej tabeli stanów / zdarzeń. Ale podoba mi się, że elementy tabeli są czymś więcej niż prostym wskaźnikiem funkcji. Zamiast tego staram się uporządkować mój projekt, tak aby w jego sercu było kilka prostych atomowych elementów lub akcji. W ten sposób mogę wymienić te proste elementy atomowe na każdym przecięciu mojej tabeli stanów / zdarzeń. Chodzi o to, że nie musisz definiować masy N kwadratowych (zwykle bardzo prostych) funkcji. Po co mieć coś tak podatnego na błędy, czasochłonne, trudne do napisania, trudne do odczytania?

Podaję także opcjonalny nowy stan i opcjonalny wskaźnik funkcji dla każdej komórki w tabeli. Wskaźnik funkcji występuje w tych wyjątkowych przypadkach, w których nie chcesz po prostu odpalać listy działań atomowych.

Wiesz, że robisz to dobrze, gdy możesz wyrazić wiele różnych funkcji, po prostu edytując tabelę, bez nowego kodu do napisania.

Alrght, myślę, że moje trochę różnią się od wszystkich innych. Nieco więcej separacji kodu i danych niż widzę w innych odpowiedziach. Naprawdę czytam teorię, aby to napisać, która implementuje pełny język regularny (niestety, bez wyrażeń regularnych). Ullman, Minsky, Chomsky. Nie mogę powiedzieć, że wszystko zrozumiałem, ale czerpałem ze starych mistrzów tak bezpośrednio, jak to możliwe: poprzez ich słowa.

Używam wskaźnika funkcji do predykatu, który określa przejście do stanu „tak” lub „nie”. Ułatwia to utworzenie akceptora stanu skończonego dla zwykłego języka, który programujesz w sposób bardziej podobny do języka asemblera. Proszę, nie zniechęcaj się moim głupim wyborem. „czek” == „czek”. 'grok' == [przejdź do słownika hakera].

Tak więc dla każdej iteracji czek wywołuje funkcję predykatu z argumentem bieżącego znaku. Jeśli predykat zwróci wartość true, znak zostanie zużyty (wskaźnik przesunie się) i wykonamy przejście „y”, aby wybrać następny stan. Jeśli predykat zwróci false, znak NIE zostanie zużyty, a my przejdziemy przez przejście „n”. Tak więc każda instrukcja jest dwukierunkową gałęzią! Musiałem wtedy czytać Historię Mela.

Ten kod pochodzi prosto z mojego interpretera postscriptowego i ewoluował do swojej obecnej postaci z dużą ilością wskazówek od kolegów na comp.lang.c. Ponieważ PostScript w zasadzie nie ma składni (wymaga tylko zrównoważonych nawiasów kwadratowych), taki parser działa również jako parser.

/* 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 zawiera 2 różne implementacje wykresów stanu:

• Meta State Machine
• Statechart

Jak zawsze, boost przeniesie Cię do piekła szablonu.

Pierwsza biblioteka jest przeznaczona dla bardziej krytycznych pod względem wydajności maszyn stanów. Druga biblioteka zapewnia bezpośrednią ścieżkę przejścia z wykresu statycznego UML do kodu.

Oto pytanie SO z prośbą o porównanie dwóch, w których obaj autorzy odpowiadają.

Ta seria postów Ars OpenForum o nieco skomplikowanej logice sterowania zawiera bardzo łatwą do wykonania implementację jako maszyna stanu w C.

Widziałem to gdzieś

#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);
  }
}

Biorąc pod uwagę, że sugerujesz, że możesz używać C ++, a zatem i kodu OO, sugerowałbym ocenę wzorca stanu „GoF” (GoF = Gang of Four, faceci, którzy napisali książkę wzorców projektowych, która wprowadziła wzorce projektowe do centrum uwagi).

Nie jest to szczególnie skomplikowane i jest szeroko stosowane i omawiane, więc łatwo jest zobaczyć przykłady i wyjaśnienia w Internecie.

Prawdopodobnie będzie także rozpoznawalny przez każdego, kto utrzyma Twój kod w późniejszym terminie.

Jeśli zmartwieniem jest wydajność, warto faktycznie przeprowadzić analizę porównawczą, aby upewnić się, że podejście inne niż OO jest bardziej wydajne, ponieważ wiele czynników wpływa na wydajność i nie zawsze jest to po prostu zły OO, funkcjonalny kod dobry. Podobnie, jeśli użycie pamięci jest dla ciebie ograniczeniem, ponownie warto wykonać kilka testów lub obliczeń, aby sprawdzić, czy rzeczywiście będzie to problem dla konkretnej aplikacji, jeśli użyjesz wzorca stanu.

Oto niektóre linki do wzorca stanu „Gof”, jak sugeruje Craig:

• http://en.wikipedia.org/wiki/State_pattern
• http://www.vincehuston.org/dp/state.html

Oto przykład maszyny stanu skończonego dla systemu Linux, która wykorzystuje zdarzenia jako kolejki komunikatów. Zdarzenia są umieszczane w kolejce i porządkowane. Stan zmienia się w zależności od tego, co dzieje się dla każdego zdarzenia.

To jest przykład połączenia danych ze stanami takimi jak:

• Niezainicjowany
• Zainicjowano
• Połączony
• MTU wynegocjowane
• Zalegalizowany

Jedną dodatkową funkcją, którą dodałem, był znacznik czasu dla każdej wiadomości / zdarzenia. Program obsługi zdarzeń zignoruje zdarzenia, które są zbyt stare (wygasły). Może się to zdarzyć często w prawdziwym świecie, w którym możesz nieoczekiwanie utknąć w stanie.

Ten przykład działa na systemie Linux, użyj poniższego pliku Makefile, aby go skompilować i bawić się nim.

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,        &currentlyLessThanMaxConnectTries,      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,            &currentlyLessThanMaxMTUtries,          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,           &currentyLessThanMaxAuthTries,          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,             &currentlyLessThanMaxTXtries,           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;
    }
}