Conception de la machine à états C [fermé]

Je crée un petit projet en C et C ++ mixtes. Je construis une petite machine d'état au cœur d'un de mes fils de travail.

Je me demandais si vous, gourous du SO, partageriez vos techniques de conception de machines à états.

REMARQUE: je recherche principalement des techniques d'implémentation éprouvées.

MISE À JOUR: Sur la base de toutes les grandes contributions recueillies sur SO, je me suis installé sur cette architecture:

Les machines à états que j'ai conçues auparavant (C, pas C ++) se résument toutes à un structtableau et à une boucle. La structure se compose essentiellement d'un état et d'un événement (pour la recherche) et d'une fonction qui renvoie le nouvel état, quelque chose comme:

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

Ensuite, vous définissez vos états et événements avec des définitions simples ( ANYcelles-ci sont des marqueurs spéciaux, voir ci-dessous):

#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

Ensuite, vous définissez toutes les fonctions appelées par les transitions:

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

Toutes ces fonctions sont écrites pour ne prendre aucune variable et retourner le nouvel état de la machine d'état. Dans cet exemple, des variables globales sont utilisées pour transmettre toute information dans les fonctions d'état lorsque cela est nécessaire.

L'utilisation de globaux n'est pas aussi mauvaise qu'il y paraît car le FSM est généralement enfermé dans une seule unité de compilation et toutes les variables sont statiques à cette unité (c'est pourquoi j'ai utilisé des guillemets autour de "global" ci-dessus - ils sont plus partagés dans le FSM, que vraiment mondiale). Comme pour tous les pays du monde, cela nécessite des soins.

Le tableau de transitions définit ensuite toutes les transitions possibles et les fonctions qui sont appelées pour ces transitions (y compris la dernière fourre-tout):

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

Cela signifie: si vous êtes dans l' ST_INITétat et que vous recevez l' EV_KEYPRESSévénement, appelez GotKey.

Le fonctionnement du FSM devient alors une boucle relativement simple:

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

Comme mentionné ci-dessus, notez l'utilisation de caractères ST_ANYgénériques, permettant à un événement d'appeler une fonction quel que soit l'état actuel. EV_ANYfonctionne également de façon similaire, permettant à tout événement à un état spécifique d'appeler une fonction.

Il peut également garantir que si vous atteignez la fin du tableau de transitions, vous obtenez une erreur indiquant que votre FSM n'a pas été construit correctement (en utilisant la ST_ANY/EV_ANYcombinaison.

J'ai utilisé un code similaire pour cela sur de nombreux projets de communication, comme une mise en œuvre précoce de piles de communications et de protocoles pour les systèmes embarqués. Le gros avantage était sa simplicité et sa relative facilité à changer le tableau de transitions.

Je ne doute pas qu'il y aura des abstractions de niveau supérieur qui peuvent être plus adaptées de nos jours, mais je pense qu'elles se résumeront toutes à ce même type de structure.

Et, comme l' ldogindique un commentaire, vous pouvez éviter les globaux en passant un pointeur de structure à toutes les fonctions (et en l'utilisant dans la boucle d'événement). Cela permettra à plusieurs machines d'état de fonctionner côte à côte sans interférence.

Créez simplement un type de structure qui contient les données spécifiques à la machine (état au strict minimum) et utilisez-les à la place des globales.

La raison pour laquelle je l'ai rarement fait est simplement parce que la plupart des machines d'état que j'ai écrites sont de type singleton (one-off, at-process-start, lecture de fichier de configuration par exemple), n'ayant pas besoin d'exécuter plus d'une instance . Mais il a de la valeur si vous devez en exécuter plusieurs.

Les autres réponses sont bonnes, mais une implémentation très "légère" que j'ai utilisée lorsque la machine d'état est très simple ressemble à:

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

J'utiliserais cela lorsque la machine à états est suffisamment simple pour que l'approche du pointeur de fonction et de la table de transition d'état soit exagérée. Ceci est souvent utile pour l'analyse syntaxique caractère par caractère ou mot par mot.

Excusez-moi d'avoir enfreint toutes les règles de l'informatique, mais une machine d'état est l'un des rares endroits (je ne peux en compter que deux à la main) où une gotodéclaration est non seulement plus efficace, mais rend également votre code plus propre et plus facile à lire. Étant donné que les gotoinstructions sont basées sur des étiquettes, vous pouvez nommer vos états au lieu d'avoir à suivre un désordre de nombres ou à utiliser une énumération. Cela rend également le code beaucoup plus propre, car vous n'avez pas besoin de toute la cruauté supplémentaire des pointeurs de fonction ou des énormes instructions de commutateur et des boucles while. Ai-je mentionné que c'est aussi plus efficace?

Voici à quoi pourrait ressembler une machine d'état:

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

Vous avez l'idée générale. Le fait est que vous pouvez implémenter la machine d'état d'une manière efficace et qui est relativement facile à lire et qui crie au lecteur qu'il regarde une machine d'état. Notez que si vous utilisez des gotoinstructions, vous devez toujours être prudent car il est très facile de se tirer une balle dans le pied.

Vous pourriez envisager le compilateur State Machine http://smc.sourceforge.net/

Ce splendide utilitaire open source accepte la description d'une machine à états dans un langage simple et la compile dans n'importe laquelle d'une douzaine de langages - y compris C et C ++. L'utilitaire lui-même est écrit en Java et peut être inclus dans le cadre d'une build.

La raison de cela, plutôt que de coder manuellement à l'aide du modèle d'état GoF ou de toute autre approche, est qu'une fois que votre machine d'état est exprimée sous forme de code, la structure sous-jacente a tendance à disparaître sous le poids du passe-partout qui doit être généré pour le prendre en charge. L'utilisation de cette approche vous offre une excellente séparation des préoccupations et vous gardez la structure de votre machine d'état «visible». Le code généré automatiquement va dans des modules que vous n'avez pas besoin de toucher, de sorte que vous pouvez revenir en arrière et jouer avec la structure de la machine d'état sans impact sur le code de support que vous avez écrit.

Désolé, je suis trop enthousiaste, et sans doute rebute tout le monde. Mais c'est un utilitaire de premier ordre, et bien documenté aussi.

N'oubliez pas de vérifier le travail de Miro Samek (blog State Space , site Web State Machines & Tools ), dont les articles du C / C ++ Users Journal étaient excellents.

Le site Web contient une implémentation complète (C / C ++) en licence open source et commerciale d'une infrastructure de machine à états (QP Framework) , d'un gestionnaire d'événements (QEP) , d'un outil de modélisation de base (QM) et d'un outil de traçage (QSpy) qui permettent de dessiner des machines à états, de créer du code et de les déboguer.

Le livre contient une explication détaillée sur le quoi / pourquoi de la mise en œuvre et comment l'utiliser et est également un excellent matériel pour acquérir une compréhension des principes fondamentaux des machines à états hiérarchiques et finis.

Le site Web contient également des liens vers plusieurs packages de support de carte pour l'utilisation du logiciel avec des plates-formes intégrées.

J'ai fait quelque chose de similaire à ce que décrit paxdiablo, mais au lieu d'un tableau de transitions état / événement, j'ai mis en place un tableau bidimensionnel de pointeurs de fonction, avec la valeur d'événement comme index d'un axe et la valeur d'état actuelle comme L'autre. Ensuite, j'appelle state = state_table[event][state](params)et la bonne chose se produit. Les cellules représentant des combinaisons état / événement invalides obtiennent un pointeur sur une fonction qui le dit, bien sûr.

Évidemment, cela ne fonctionne que si les valeurs d'état et d'événement sont toutes les deux des plages contiguës et commencent à 0 ou assez près.

Un très joli "framework" de machine d'état C ++ basé sur un modèle est donné par Stefan Heinzmann dans son article .

Puisqu'il n'y a pas de lien vers un téléchargement de code complet dans l'article, j'ai pris la liberté de coller le code dans un projet et de le vérifier. Le matériel ci-dessous est testé et comprend les quelques pièces manquantes mineures mais à peu près évidentes.

L'innovation majeure ici est que le compilateur génère du code très efficace. Les actions d'entrée / sortie vides sont gratuites. Les actions d'entrée / sortie non vides sont intégrées. Le compilateur vérifie également l'exhaustivité du diagramme d'états. Les actions manquantes génèrent des erreurs de liaison. La seule chose qui n'est pas capturée, ce sont les disparusTop::init .

C'est une très belle alternative à l'implémentation de Miro Samek, si vous pouvez vivre sans ce qui manque - c'est loin d'être une implémentation UML Statechart complète, bien qu'elle implémente correctement la sémantique UML, alors que le code de Samek par conception ne gère pas la sortie / transition / actions de saisie dans l'ordre correct.

Si ce code fonctionne pour ce que vous devez faire et que vous avez un compilateur C ++ décent pour votre système, il fonctionnera probablement mieux que l'implémentation C / C ++ de Miro. Le compilateur génère pour vous une implémentation de la machine à états de transition O (1) aplatie. Si l'audit des sorties d'assemblage confirme que les optimisations fonctionnent comme vous le souhaitez, vous vous rapprochez des performances théoriques. La meilleure partie: c'est un code relativement petit et facile à comprendre.

#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

Le code de test suit.

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

La technique que j'aime pour les machines à états (au moins celles pour le contrôle de programme) est d'utiliser des pointeurs de fonction. Chaque état est représenté par une fonction différente. La fonction prend un symbole d'entrée et renvoie le pointeur de fonction pour l'état suivant. Le moniteur de boucle de répartition centrale prend l'entrée suivante, la transmet à l'état actuel et traite le résultat.

Le fait de taper dessus devient un peu étrange, car C n'a pas de moyen d'indiquer les types de pointeurs de fonction qui se retournent, donc les fonctions d'état reviennent void*. Mais vous pouvez faire quelque chose comme ça:

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

Ensuite, vos fonctions d'état individuelles peuvent activer leur entrée pour traiter et renvoyer la valeur appropriée.

Cas le plus simple

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

Points: l'état est privé, non seulement pour l'unité de compilation mais aussi pour le gestionnaire d'événements. Les cas spéciaux peuvent être traités séparément de l'interrupteur principal en utilisant la construction jugée nécessaire.

Cas plus complexe

Lorsque le commutateur est plus grand que deux écrans pleins, divisez-le en fonctions qui gèrent chaque état, en utilisant une table d'états pour rechercher directement la fonction. L'État est toujours privé du gestionnaire d'événements. Les fonctions du gestionnaire d'état renvoient l'état suivant. Si nécessaire, certains événements peuvent toujours recevoir un traitement spécial dans le gestionnaire d'événements principal. J'aime lancer des pseudo-événements pour l'entrée et la sortie d'état et peut-être le démarrage de la machine d'état:

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

Je ne sais pas si j'ai cloué la syntaxe, en particulier en ce qui concerne le tableau des pointeurs de fonction. Je n'ai exécuté rien de tout cela via un compilateur. Après examen, j'ai remarqué que j'avais oublié de supprimer explicitement l'état suivant lors de la gestion des pseudo-événements (la parenthèse (void) avant l'appel à state_handler ()). C'est quelque chose que j'aime faire même si les compilateurs acceptent l'omission en silence. Il indique aux lecteurs du code que "oui, je voulais en effet appeler la fonction sans utiliser la valeur de retour", et cela peut empêcher les outils d'analyse statique de l'avertir. C'est peut-être idiosyncratique parce que je ne me souviens pas avoir vu quelqu'un d'autre faire cela.

Points: ajouter un tout petit peu de complexité (vérifier si l'état suivant est différent de l'état actuel), peut éviter le code dupliqué ailleurs, car les fonctions du gestionnaire d'état peuvent profiter des pseudo-événements qui se produisent lorsqu'un état est entré et quitté. N'oubliez pas que l'état ne peut pas changer lors de la gestion des pseudo-événements, car le résultat du gestionnaire d'état est ignoré après ces événements. Vous pouvez bien sûr choisir de modifier le comportement.

Un gestionnaire d'état ressemblerait à ceci:

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

Plus de complexité

Lorsque l'unité de compilation devient trop grande (quelle que soit votre impression, je devrais dire environ 1 000 lignes), placez chaque gestionnaire d'état dans un fichier distinct. Lorsque chaque gestionnaire d'état devient plus long que quelques écrans, divisez chaque événement dans une fonction distincte, similaire à la façon dont le commutateur d'état a été divisé. Vous pouvez le faire de différentes manières, indépendamment de l'état ou en utilisant une table commune ou en combinant différents schémas. Certains d'entre eux ont été couverts ici par d'autres. Triez vos tableaux et utilisez la recherche binaire si la vitesse est une exigence.

Programmation générique

Je voudrais que le préprocesseur traite des problèmes tels que le tri des tables ou même la génération de machines à états à partir de descriptions, vous permettant "d'écrire des programmes sur des programmes". Je crois que c'est pour cela que les gens de Boost exploitent les modèles C ++, mais je trouve la syntaxe cryptique.

Tables bidimensionnelles

J'ai utilisé des tables d'état / d'événements dans le passé, mais je dois dire que pour les cas les plus simples, je ne les trouve pas nécessaires et je préfère la clarté et la lisibilité de l'instruction switch même si elle s'étend au-delà d'un écran complet. Pour les cas plus complexes, les tableaux deviennent rapidement incontrôlables comme d'autres l'ont noté. Les idiomes que je présente ici vous permettent d'ajouter une multitude d'événements et d'états quand vous en avez envie, sans avoir à maintenir une table consommatrice de mémoire (même s'il peut s'agir de mémoire de programme).

Avertissement

Des besoins spéciaux peuvent rendre ces idiomes moins utiles, mais je les ai trouvés très clairs et maintenables.

Extrêmement non testé, mais amusant à coder, maintenant dans une version plus raffinée que ma réponse originale; des versions à jour peuvent être trouvées sur 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

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

J'ai vraiment aimé la réponse de paxdiable et j'ai décidé d'implémenter toutes les fonctionnalités manquantes pour mon application comme les variables de garde et les données spécifiques à la machine d'état.

J'ai téléchargé mon implémentation sur ce site pour la partager avec la communauté. Il a été testé à l'aide de IAR Embedded Workbench for ARM.

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

Un autre outil open source intéressant est Yakindu Statechart Tools sur statecharts.org . Il utilise les diagrammes d'état Harel et fournit ainsi des états hiérarchiques et parallèles et génère du code C et C ++ (ainsi que Java). Il n'utilise pas de bibliothèques mais suit une approche de «code simple». Le code applique essentiellement des structures de cas de commutation. Les générateurs de code peuvent également être personnalisés. De plus, l'outil offre de nombreuses autres fonctionnalités.

J'arrive tard (comme d'habitude) mais en parcourant les réponses à ce jour, je pense qu'il manque quelque chose d'important;

J'ai trouvé dans mes propres projets qu'il peut être très utile de ne pas avoir de fonction pour chaque combinaison état / événement valide. J'aime l'idée d'avoir effectivement une table 2D d'états / événements. Mais j'aime que les éléments du tableau soient plus qu'un simple pointeur de fonction. Au lieu de cela, j'essaie d'organiser ma conception, donc en son cœur, elle comprend un tas d'éléments ou d'actions atomiques simples. De cette façon, je peux lister ces éléments atomiques simples à chaque intersection de ma table d'état / événement. L'idée est que vous ne le faites pas à définir une masse de N fonctions au carré (généralement très simples). Pourquoi avoir quelque chose d'aussi sujet aux erreurs, de temps, difficile à écrire, difficile à lire, vous l'appelez?

J'inclus également un nouvel état facultatif et un pointeur de fonction facultatif pour chaque cellule du tableau. Le pointeur de fonction est là pour les cas exceptionnels où vous ne voulez pas simplement déclencher une liste d'actions atomiques.

Vous savez que vous le faites correctement lorsque vous pouvez exprimer de nombreuses fonctionnalités différentes, simplement en modifiant votre table, sans nouveau code à écrire.

Bon, je pense que le mien est juste un peu différent de tout le monde. Un peu plus de séparation du code et des données que je ne le vois dans les autres réponses. J'ai vraiment lu la théorie pour écrire ceci, qui implémente un langage régulier complet (sans expressions régulières, malheureusement). Ullman, Minsky, Chomsky. Je ne peux pas dire que j'ai tout compris, mais je me suis inspiré des anciens maîtres aussi directement que possible: à travers leurs mots.

J'utilise un pointeur de fonction vers un prédicat qui détermine la transition vers un état «oui» ou un état «non». Cela facilite la création d'un accepteur à états finis pour un langage normal que vous programmez d'une manière plus proche du langage d'assemblage. S'il vous plaît ne soyez pas rebuté par mes choix de noms stupides. 'czek' == 'vérifier'. 'grok' == [allez le chercher dans le dictionnaire Hacker].

Donc, pour chaque itération, czek appelle une fonction de prédicat avec le caractère courant comme argument. Si le prédicat retourne vrai, le caractère est consommé (le pointeur avancé) et nous suivons la transition «y» pour sélectionner l'état suivant. Si le prédicat renvoie faux, le caractère n'est PAS consommé et nous suivons la transition 'n'. Donc, chaque instruction est une branche à double sens! Je devais lire l'histoire de Mel à l'époque.

Ce code vient directement de mon interprète postscript , et a évolué dans sa forme actuelle avec beaucoup de conseils des boursiers sur comp.lang.c. Étant donné que postscript n'a fondamentalement pas de syntaxe (ne nécessitant que des crochets équilibrés), un accepteur de langage régulier comme celui-ci fonctionne également comme analyseur.

/* 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 est livré avec 2 implémentations de diagrammes d'état différents:

• Meta State Machine
• Statechart

Comme toujours, le boost vous transportera dans l'enfer des modèles.

La première bibliothèque est destinée aux machines d'état plus critiques pour les performances. La deuxième bibliothèque vous donne un chemin de transition direct d'un diagramme d'états UML au code.

Voici la question SO demandant une comparaison entre les deux où les deux auteurs répondent.

Cette série d'articles Ars OpenForum sur un peu compliqué de logique de contrôle comprend une implémentation très facile à suivre comme machine d'état en C.

J'ai vu ça quelque part

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

Étant donné que vous impliquez que vous pouvez utiliser le code C ++ et donc OO, je suggère d'évaluer le modèle d'état `` GoF '' (GoF = Gang of Four, les gars qui ont écrit le livre sur les modèles de conception qui a mis les modèles de conception sous les projecteurs).

Ce n'est pas particulièrement complexe et il est largement utilisé et discuté, il est donc facile de voir des exemples et des explications en ligne.

Il sera également très probablement reconnaissable par toute autre personne conservant votre code à une date ultérieure.

Si l'efficacité est le souci, il vaudrait la peine de faire une analyse comparative pour s'assurer qu'une approche non OO est plus efficace car de nombreux facteurs affectent les performances et ce n'est pas toujours simplement OO mauvais, le code fonctionnel est bon. De même, si l'utilisation de la mémoire est une contrainte pour vous, cela vaut encore la peine de faire des tests ou des calculs pour voir si cela sera réellement un problème pour votre application particulière si vous utilisez le modèle d'état.

Voici quelques liens vers le modèle d'état «Gof», comme le suggère Craig:

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

Voici un exemple de machine à états finis pour Linux qui utilise les files d'attente de messages comme événements. Les événements sont placés dans la file d'attente et traités dans l'ordre. L'état change en fonction de ce qui se passe pour chaque événement.

Ceci est un exemple de connexion de données avec des états tels que:

• Non initialisé
• Initialisé
• Lié
• MTU négocié
• Authentifié

Une petite fonctionnalité supplémentaire que j'ai ajoutée était un horodatage pour chaque message / événement. Le gestionnaire d'événements ignorera les événements trop anciens (ils ont expiré). Cela peut se produire beaucoup dans le monde réel où vous pourriez vous retrouver dans un état inattendu.

Cet exemple fonctionne sous Linux, utilisez le Makefile ci-dessous pour le compiler et jouer avec.

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