C State-Machine-Design [geschlossen]

Ich bastle ein kleines Projekt in gemischtem C und C ++. Ich baue eine kleine Zustandsmaschine im Herzen eines meiner Arbeitsthreads.

Ich habe mich gefragt, ob Sie Gurus auf SO Ihre State-Machine-Design-Techniken teilen würden.

HINWEIS: Ich bin in erster Linie nach bewährten Implementierungstechniken.

AKTUALISIERT: Aufgrund all der großartigen Beiträge, die auf SO gesammelt wurden, habe ich mich für diese Architektur entschieden:

Zustandsmaschinen, die ich zuvor entworfen habe (C, nicht C ++), sind alle auf ein structArray und eine Schleife zurückzuführen. Die Struktur besteht im Wesentlichen aus einem Status und einem Ereignis (zum Nachschlagen) und einer Funktion, die den neuen Status zurückgibt, etwa:

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

Dann definieren Sie Ihre Zustände und Ereignisse mit einfachen Definitionen (diese ANYsind spezielle Markierungen, siehe unten):

#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

Dann definieren Sie alle Funktionen, die von den Übergängen aufgerufen werden:

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

Alle diese Funktionen sind so geschrieben, dass sie keine Variablen annehmen und den neuen Status für die Zustandsmaschine zurückgeben. In diesem Beispiel werden globale Variablen verwendet, um bei Bedarf Informationen an die Statusfunktionen zu übergeben.

Die Verwendung von Globals ist nicht so schlecht, wie es sich anhört, da der FSM normalerweise in einer einzelnen Kompilierungseinheit eingeschlossen ist und alle Variablen für diese Einheit statisch sind (weshalb ich oben Anführungszeichen um "global" verwendet habe - sie werden innerhalb der Einheit mehr geteilt FSM, als wirklich global). Wie bei allen Globalen erfordert es Sorgfalt.

Das Transitions-Array definiert dann alle möglichen Übergänge und die Funktionen, die für diese Übergänge aufgerufen werden (einschließlich des letzten Catch-All):

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

Das bedeutet: Wenn Sie sich im ST_INITStatus befinden und die EV_KEYPRESSVeranstaltung erhalten, rufen Sie an GotKey.

Die Arbeitsweise des FSM wird dann zu einer relativ einfachen Schleife:

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

Beachten Sie, wie oben erwähnt, die Verwendung ST_ANYals Platzhalter, damit ein Ereignis eine Funktion aufrufen kann, unabhängig vom aktuellen Status.EV_ANYfunktioniert auch ähnlich, sodass jedes Ereignis in einem bestimmten Status eine Funktion aufrufen kann.

Es kann auch garantiert werden, dass am Ende des Übergangsarrays eine Fehlermeldung angezeigt wird, dass Ihr FSM nicht korrekt erstellt wurde (mithilfe der ST_ANY/EV_ANYKombination).

Ich habe ähnlichen Code für viele Kommunikationsprojekte verwendet, z. B. für die frühzeitige Implementierung von Kommunikationsstapeln und -protokollen für eingebettete Systeme. Der große Vorteil war seine Einfachheit und relative Leichtigkeit beim Ändern des Übergangsarrays.

Ich habe keinen Zweifel, dass es Abstraktionen auf höherer Ebene geben wird, die heutzutage vielleicht besser geeignet sind, aber ich vermute, dass sie alle auf dieselbe Art von Struktur hinauslaufen werden.

Und wie ldog in einem Kommentar angegeben, können Sie die Globalen insgesamt vermeiden, indem Sie einen Strukturzeiger an alle Funktionen übergeben (und diesen in der Ereignisschleife verwenden). Auf diese Weise können mehrere Zustandsautomaten störungsfrei nebeneinander ausgeführt werden.

Erstellen Sie einfach einen Strukturtyp, der die maschinenspezifischen Daten enthält (Status mindestens), und verwenden Sie diese anstelle der globalen Daten.

Der Grund, warum ich das selten getan habe, ist einfach, dass die meisten von mir geschriebenen Zustandsautomaten Singleton-Typen waren (einmalig, beim Start des Prozesses, Lesen von Konfigurationsdateien zum Beispiel), die nicht mehr als eine Instanz ausführen müssen . Aber es hat Wert, wenn Sie mehr als eine ausführen müssen.

Die anderen Antworten sind gut, aber eine sehr "leichte" Implementierung, die ich verwendet habe, wenn die Zustandsmaschine sehr einfach ist, sieht aus wie:

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

Ich würde dies verwenden, wenn die Zustandsmaschine so einfach ist, dass der Ansatz des Funktionszeigers und der Zustandsübergangstabelle übertrieben ist. Dies ist häufig nützlich, um Zeichen für Zeichen oder Wort für Wort zu analysieren.

Verzeihen Sie mir, dass ich gegen jede Regel in der Informatik verstoßen habe, aber eine Zustandsmaschine ist eine der wenigen Stellen (ich kann nur zwei gotoohne weiteres zählen), an denen eine Aussage nicht nur effizienter ist, sondern auch Ihren Code sauberer und leichter lesbar macht. weilgoto Anweisungen auf Beschriftungen basieren, können Sie Ihre Zustände benennen, anstatt ein Durcheinander von Zahlen verfolgen oder eine Aufzählung verwenden zu müssen. Es sorgt auch für viel saubereren Code, da Sie nicht alle zusätzlichen Funktionszeiger oder riesigen switch-Anweisungen und while-Schleifen benötigen. Habe ich schon erwähnt, dass es auch effizienter ist?

So könnte eine Zustandsmaschine aussehen:

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

Sie bekommen die allgemeine Idee. Der Punkt ist, dass Sie die Zustandsmaschine auf eine effiziente Art und Weise implementieren können, die relativ einfach zu lesen ist und den Leser anschreit, dass er eine Zustandsmaschine betrachtet. Beachten Sie, dass Sie bei der Verwendung von gotoAnweisungen dennoch vorsichtig sein müssen, da es sehr einfach ist, sich dabei in den Fuß zu schießen.

Sie könnten den State Machine Compiler http://smc.sourceforge.net/ in Betracht ziehen.

Dieses großartige Open Source-Dienstprogramm akzeptiert eine Beschreibung einer Zustandsmaschine in einer einfachen Sprache und kompiliert sie in eine von etwa einem Dutzend Sprachen - einschließlich C und C ++. Das Dienstprogramm selbst ist in Java geschrieben und kann als Teil eines Builds enthalten sein.

Der Grund dafür ist, dass die zugrunde liegende Struktur, sobald Ihre Zustandsmaschine als Code ausgedrückt wird, dazu neigt, unter dem Gewicht der Kesselplatte zu verschwinden, die generiert werden muss, um sie zu unterstützen, anstatt sie mit dem GoF-Statusmuster oder einem anderen Ansatz von Hand zu codieren. Wenn Sie diesen Ansatz verwenden, erhalten Sie eine hervorragende Trennung von Bedenken und halten die Struktur Ihrer Zustandsmaschine "sichtbar". Der automatisch generierte Code wird in Module eingeteilt, die Sie nicht berühren müssen, damit Sie zurückgehen und an der Struktur der Zustandsmaschine herumspielen können, ohne den von Ihnen geschriebenen unterstützenden Code zu beeinträchtigen.

Tut mir leid, ich bin überbegeistert und schrecken zweifellos alle ab. Aber es ist ein erstklassiges Dienstprogramm und auch gut dokumentiert.

Überprüfen Sie unbedingt die Arbeit von Miro Samek (Blog State Space , Website State Machines & Tools ) an, dessen Artikel im C / C ++ Users Journal großartig waren.

Die Website enthält eine vollständige (C / C ++) Implementierung eines State Machine Frameworks (QP Framework) , eines Event Handlers (QEP) in Open Source und kommerzieller Lizenz. , ein Grundmodellierungswerkzeug (QM) und Tracing - Tool (QSpy) die Erlauben Sie das Zeichnen von Zustandsautomaten, das Erstellen von Code und das Debuggen dieser.

Das Buch enthält eine ausführliche Erklärung zum Was / Warum der Implementierung und deren Verwendung und ist auch ein großartiges Material, um die Grundlagen hierachischer und endlicher Zustandsmaschinen zu verstehen.

Die Website enthält auch Links zu verschiedenen Board-Support-Paketen für die Verwendung der Software mit eingebetteten Plattformen.

Ich habe etwas Ähnliches getan, wie es paxdiablo beschreibt, nur dass ich anstelle eines Arrays von Zustands- / Ereignisübergängen ein zweidimensionales Array von Funktionszeigern eingerichtet habe, wobei der Ereigniswert als Index einer Achse und der aktuelle Statuswert als das andere. Dann rufe ich einfach anstate = state_table[event][state](params) und das Richtige passiert. Zellen, die ungültige Zustands- / Ereigniskombinationen darstellen, erhalten natürlich einen Zeiger auf eine Funktion, die dies sagt.

Dies funktioniert natürlich nur, wenn die Status- und Ereigniswerte beide zusammenhängende Bereiche sind und bei 0 beginnen oder nahe genug sind.

Ein sehr schönes vorlagenbasiertes C ++ - Zustandsmaschinen- "Framework" gibt Stefan Heinzmann in seinem Artikel .

Da der Artikel keinen Link zu einem vollständigen Code-Download enthält, habe ich mir erlaubt, den Code in ein Projekt einzufügen und auszuchecken. Das Zeug unten ist getestet und enthält die wenigen kleinen, aber ziemlich offensichtlichen fehlenden Teile.

Die wichtigste Neuerung dabei ist, dass der Compiler sehr effizienten Code generiert. Leere Ein- / Ausstiegsaktionen sind kostenlos. Nicht leere Ein- / Ausstiegsaktionen sind inline. Der Compiler überprüft auch die Vollständigkeit des Zustandsdiagramms. Fehlende Aktionen erzeugen Verknüpfungsfehler. Das einzige, was nicht gefangen wird, ist das VermissteTop::init .

Dies ist eine sehr schöne Alternative zur Implementierung von Miro Samek, wenn Sie ohne das, was fehlt, leben können - dies ist weit entfernt von einer vollständigen UML-Statechart-Implementierung, obwohl die UML-Semantik korrekt implementiert wird, während der Code von Samek vom Design her nicht das Beenden / Übergehen behandelt / Eingabeaktionen in der richtigen Reihenfolge.

Wenn dieser Code genau das tut, was Sie tun müssen, und Sie einen anständigen C ++ - Compiler für Ihr System haben, ist er wahrscheinlich leistungsfähiger als die C / C ++ - Implementierung von Miro. Der Compiler generiert für Sie eine abgeflachte O (1) -Übergangszustandsmaschinenimplementierung. Wenn die Prüfung der Baugruppenausgabe bestätigt, dass die Optimierungen wie gewünscht funktionieren, nähern Sie sich der theoretischen Leistung. Das Beste daran: Es ist relativ kleiner, leicht verständlicher Code.

#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

Testcode folgt.

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

Die Technik, die ich für Zustandsautomaten mag (zumindest für die Programmsteuerung), besteht darin, Funktionszeiger zu verwenden. Jeder Zustand wird durch eine andere Funktion dargestellt. Die Funktion nimmt ein Eingabesymbol und gibt den Funktionszeiger für den nächsten Status zurück. Die zentralen Dispatch-Loop-Monitore nehmen die nächste Eingabe auf, führen sie in den aktuellen Status ein und verarbeiten das Ergebnis.

Die Eingabe darauf wird etwas seltsam, da C keine Möglichkeit hat, Typen von Funktionszeigern anzugeben, die sich selbst zurückgeben, sodass die Statusfunktionen zurückkehren void*. Aber Sie können so etwas tun:

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

Dann können Ihre einzelnen Statusfunktionen ihre Eingabe einschalten, um den entsprechenden Wert zu verarbeiten und zurückzugeben.

Einfachster Fall

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

Punkte: Der Status ist privat, nicht nur für die Kompilierungseinheit, sondern auch für den event_handler. Sonderfälle können getrennt vom Hauptschalter unter Verwendung eines als notwendig erachteten Konstrukts behandelt werden.

Komplexerer Fall

Wenn der Schalter größer als ein paar Bildschirme ist, teilen Sie ihn in Funktionen auf, die jeden Status behandeln, und verwenden Sie eine Statustabelle, um die Funktion direkt nachzuschlagen. Der Staat ist für den Event-Handler weiterhin privat. Die Statushandlerfunktionen geben den nächsten Status zurück. Bei Bedarf können einige Ereignisse im Hauptereignishandler noch eine Sonderbehandlung erhalten. Ich mag es, Pseudo-Ereignisse für den Ein- und Ausgang des Zustands und vielleicht für den Start der Zustandsmaschine einzuwerfen:

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

Ich bin mir nicht sicher, ob ich die Syntax festgelegt habe, insbesondere in Bezug auf das Array von Funktionszeigern. Ich habe nichts davon durch einen Compiler ausgeführt. Bei der Überprüfung habe ich festgestellt, dass ich vergessen habe, den nächsten Status beim Behandeln der Pseudoereignisse (die (leere) Klammer vor dem Aufruf von state_handler ()) explizit zu verwerfen. Dies ist etwas, das ich gerne mache, auch wenn Compiler die Auslassung stillschweigend akzeptieren. Es teilt den Lesern des Codes mit, dass "Ja, ich wollte die Funktion tatsächlich aufrufen, ohne den Rückgabewert zu verwenden", und es kann statische Analysewerkzeuge daran hindern, davor zu warnen. Es mag eigenwillig sein, weil ich mich nicht daran erinnere, dass jemand anderes dies getan hat.

Punkte: Durch Hinzufügen eines kleinen Teils der Komplexität (Überprüfen, ob der nächste Status vom aktuellen Status abweicht) können Sie doppelten Code an anderer Stelle vermeiden, da die Statusbehandlungsfunktionen die Pseudoereignisse genießen können, die auftreten, wenn ein Status eingegeben und verlassen wird. Denken Sie daran, dass sich der Status beim Behandeln der Pseudoereignisse nicht ändern kann, da das Ergebnis des Statushandlers nach diesen Ereignissen verworfen wird. Sie können das Verhalten natürlich ändern.

Ein State Handler würde so aussehen:

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

Mehr Komplexität

Wenn die Kompilierungseinheit zu groß wird (was auch immer Sie denken, ich sollte ungefähr 1000 Zeilen sagen), legen Sie jeden Statushandler in einer separaten Datei ab. Wenn jeder Statushandler länger als ein paar Bildschirme ist, teilen Sie jedes Ereignis in einer separaten Funktion auf, ähnlich wie der Statusschalter aufgeteilt wurde. Sie können dies auf verschiedene Arten tun, getrennt vom Status oder mithilfe einer gemeinsamen Tabelle oder durch Kombinieren verschiedener Schemata. Einige von ihnen wurden hier von anderen behandelt. Sortieren Sie Ihre Tabellen und verwenden Sie die binäre Suche, wenn Geschwindigkeit erforderlich ist.

Generische Programmierung

Ich möchte, dass der Präprozessor Probleme wie das Sortieren von Tabellen oder sogar das Generieren von Zustandsautomaten aus Beschreibungen behandelt, damit Sie "Programme über Programme schreiben" können. Ich glaube, dafür nutzen die Boost-Leute C ++ - Vorlagen, aber ich finde die Syntax kryptisch.

Zweidimensionale Tabellen

Ich habe in der Vergangenheit Status- / Ereignistabellen verwendet, aber ich muss sagen, dass ich sie für die einfachsten Fälle nicht für notwendig halte und die Klarheit und Lesbarkeit der switch-Anweisung bevorzuge, auch wenn sie sich über einen vollen Bildschirm hinaus erstreckt. In komplexeren Fällen geraten die Tabellen schnell außer Kontrolle, wie andere angemerkt haben. Mit den hier vorgestellten Redewendungen können Sie eine Reihe von Ereignissen und Zuständen hinzufügen, wenn Sie Lust dazu haben, ohne eine speicherintensive Tabelle verwalten zu müssen (auch wenn es sich möglicherweise um Programmspeicher handelt).

Haftungsausschluss

Spezielle Bedürfnisse mögen diese Redewendungen weniger nützlich machen, aber ich habe festgestellt, dass sie sehr klar und wartbar sind.

Extrem ungetestet, aber es macht Spaß, Code zu schreiben, jetzt in einer verfeinerten Version als meine ursprüngliche Antwort; Aktuelle Versionen finden Sie unter 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

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

Die Antwort von paxdiable hat mir sehr gut gefallen und ich habe beschlossen, alle fehlenden Funktionen für meine Anwendung wie Schutzvariablen und zustandsmaschinenspezifische Daten zu implementieren.

Ich habe meine Implementierung auf diese Site hochgeladen, um sie mit der Community zu teilen. Es wurde mit IAR Embedded Workbench für ARM getestet.

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

Ein weiteres interessantes Open Source Tool ist Yakindu Statechart Tools auf statecharts.org . Es verwendet Harel-Zustandsdiagramme und stellt somit hierarchische und parallele Zustände bereit und generiert C- und C ++ - (sowie Java-) Code. Es werden keine Bibliotheken verwendet, sondern es wird ein "einfacher Code" -Ansatz verfolgt. Der Code wendet grundsätzlich Switch-Case-Strukturen an. Die Codegeneratoren können auch angepasst werden. Zusätzlich bietet das Tool viele weitere Funktionen.

Ich komme zu spät (wie üblich), scanne aber die bisherigen Antworten und denke, dass etwas Wichtiges fehlt.

Ich habe in meinen eigenen Projekten festgestellt, dass es sehr hilfreich sein kann, nicht für jede gültige Kombination aus Status und Ereignis eine Funktion zu haben. Ich mag die Idee, effektiv eine 2D-Tabelle mit Zuständen / Ereignissen zu haben. Aber ich mag es, wenn die Tabellenelemente mehr als ein einfacher Funktionszeiger sind. Stattdessen versuche ich, mein Design so zu organisieren, dass es im Kern eine Reihe einfacher atomarer Elemente oder Aktionen enthält. Auf diese Weise kann ich diese einfachen atomaren Elemente an jedem Schnittpunkt meiner Status- / Ereignistabelle auflisten. Die Idee ist, dass Sie nicht Masse von N quadratischen (normalerweise sehr einfachen) Funktionen definieren müssen. Warum etwas so fehleranfällig, zeitaufwändig, schwer zu schreiben, schwer zu lesen, wie Sie es nennen?

Ich füge auch einen optionalen neuen Status und einen optionalen Funktionszeiger für jede Zelle in der Tabelle hinzu. Der Funktionszeiger ist für Ausnahmefälle vorgesehen, in denen Sie nicht nur eine Liste atomarer Aktionen auslösen möchten.

Sie wissen, dass Sie es richtig machen, wenn Sie viele verschiedene Funktionen ausdrücken können, indem Sie einfach Ihre Tabelle bearbeiten und keinen neuen Code schreiben müssen.

Alrght, ich denke, meine ist nur ein bisschen anders als die aller anderen. Etwas mehr Trennung von Code und Daten als ich in den anderen Antworten sehe. Ich habe mich wirklich über die Theorie informiert, um dies zu schreiben, die eine vollständige reguläre Sprache implementiert (leider ohne reguläre Ausdrücke). Ullman, Minsky, Chomsky. Ich kann nicht sagen, dass ich alles verstanden habe, aber ich habe mich so direkt wie möglich an die alten Meister gewandt: durch ihre Worte.

Ich verwende einen Funktionszeiger auf ein Prädikat, das den Übergang in einen "Ja" -Zustand oder einen "Nein" -Zustand bestimmt. Dies erleichtert die Erstellung eines Endlichzustandsakzeptors für eine reguläre Sprache, die Sie in einer Assemblersprachen-ähnlichen Weise programmieren. Bitte lassen Sie sich nicht von meinen dummen Namenswahlen abschrecken. 'czek' == 'check'. 'grok' == [schau im Hacker Dictionary nach].

Daher ruft czek für jede Iteration eine Prädikatfunktion mit dem aktuellen Zeichen als Argument auf. Wenn das Prädikat true zurückgibt, wird das Zeichen verbraucht (der Zeiger ist vorgerückt) und wir folgen dem Übergang 'y', um den nächsten Status auszuwählen. Wenn das Prädikat false zurückgibt, wird das Zeichen NICHT verbraucht und wir folgen dem Übergang 'n'. Jeder Befehl ist also ein Zwei-Wege-Zweig! Ich muss damals The Story of Mel gelesen haben.

Dieser Code stammt direkt von meinem Postscript-Interpreter und hat sich mit viel Anleitung der Kollegen auf comp.lang.c. zu seiner aktuellen Form entwickelt. Da Postscript im Grunde keine Syntax hat (nur ausgeglichene Klammern erforderlich), fungiert ein solcher regulärer Sprachakzeptor auch als 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 wird mit 2 verschiedenen Zustandsdiagrammimplementierungen geliefert:

• Meta State Machine
• Staatsdiagramm

Wie immer bringt Sie Boost in die Hölle der Vorlagen.

Die erste Bibliothek ist für leistungskritischere Zustandsautomaten vorgesehen. Die zweite Bibliothek bietet Ihnen einen direkten Übergangspfad von einem UML-Zustandsdiagramm zum Code.

Hier ist die SO-Frage, die nach einem Vergleich zwischen den beiden fragt, auf die beide Autoren antworten.

Diese Reihe von Ars OpenForum-Beiträgen zu einem etwas komplizierten Teil der Steuerlogik enthält eine sehr einfach zu verfolgende Implementierung als Zustandsmaschine in C.

Hab das irgendwo gesehen

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

Angesichts der Tatsache, dass Sie implizieren, dass Sie C ++ und damit OO-Code verwenden können, würde ich vorschlagen, das 'GoF'-Zustandsmuster zu bewerten (GoF = Gang of Four, die Leute, die das Designmusterbuch geschrieben haben, das Designmuster ins Rampenlicht gerückt hat).

Es ist nicht besonders komplex und wird häufig verwendet und diskutiert, sodass Beispiele und Erklärungen online leicht zu sehen sind.

Es wird wahrscheinlich auch von anderen Personen erkannt werden, die Ihren Code zu einem späteren Zeitpunkt pflegen.

Wenn Effizienz die Sorge ist, lohnt es sich, tatsächlich ein Benchmarking durchzuführen, um sicherzustellen, dass ein Nicht-OO-Ansatz effizienter ist, da viele Faktoren die Leistung beeinflussen und es nicht immer einfach OO-schlechter, funktionaler Code gut ist. Wenn die Speichernutzung für Sie eine Einschränkung darstellt, lohnt es sich erneut, einige Tests oder Berechnungen durchzuführen, um festzustellen, ob dies tatsächlich ein Problem für Ihre spezielle Anwendung darstellt, wenn Sie das Statusmuster verwenden.

Das Folgende sind einige Links zum 'Gof'-Zustandsmuster, wie Craig vorschlägt:

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

Hier ist ein Beispiel für eine Finite State Machine für Linux, die Nachrichtenwarteschlangen als Ereignisse verwendet. Die Ereignisse werden in die Warteschlange gestellt und der Reihe nach behandelt. Der Status ändert sich je nachdem, was für jedes Ereignis passiert.

Dies ist ein Beispiel für eine Datenverbindung mit Zuständen wie:

• Nicht initialisiert
• Initialisiert
• In Verbindung gebracht
• MTU verhandelt
• Authentifiziert

Eine kleine zusätzliche Funktion, die ich hinzugefügt habe, war ein Zeitstempel für jede Nachricht / jedes Ereignis. Der Ereignishandler ignoriert Ereignisse, die zu alt sind (sie sind abgelaufen). Dies kann in der realen Welt häufig vorkommen, wenn Sie unerwartet in einem Zustand stecken bleiben.

Dieses Beispiel läuft unter Linux. Verwenden Sie das folgende Makefile, um es zu kompilieren und damit herumzuspielen.

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