Desain mesin-negara C [ditutup]

Saya membuat proyek kecil dalam campuran C dan C ++. Saya sedang membangun satu mesin negara-ish kecil di jantung salah satu utas pekerja saya.

Saya bertanya-tanya apakah Anda ahli di SO akan berbagi teknik desain mesin negara Anda.

CATATAN: Saya terutama setelah mencoba & menguji teknik implementasi.

DIPERBARUI: Berdasarkan semua input hebat yang dikumpulkan pada SO, saya telah menetapkan arsitektur ini:

Mesin negara yang saya rancang sebelumnya (C, bukan C ++) semuanya turun ke structarray dan loop. Struktur pada dasarnya terdiri dari keadaan dan peristiwa (untuk pencarian) dan fungsi yang mengembalikan keadaan baru, seperti:

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

Kemudian Anda mendefinisikan negara dan acara Anda dengan definisi sederhana ( ANYyang merupakan penanda khusus, lihat di bawah):

#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

Kemudian Anda mendefinisikan semua fungsi yang dipanggil oleh transisi:

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

Semua fungsi ini ditulis untuk tidak mengambil variabel dan mengembalikan negara baru untuk mesin negara. Dalam contoh ini variabel global digunakan untuk meneruskan informasi apa pun ke fungsi negara jika perlu.

Menggunakan global tidak seburuk kedengarannya karena FSM biasanya dikunci di dalam satu unit kompilasi dan semua variabel statis untuk unit itu (itulah sebabnya saya menggunakan tanda kutip di sekitar "global" di atas - mereka lebih dibagi dalam FSM, daripada benar-benar global). Seperti halnya semua global, ini membutuhkan perhatian.

Array transisi kemudian mendefinisikan semua transisi yang mungkin dan fungsi yang dipanggil untuk transisi tersebut (termasuk catch-all last):

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

Artinya adalah: jika Anda berada di ST_INITnegara bagian dan menerima EV_KEYPRESSacara tersebut, lakukan panggilan ke GotKey.

Cara kerja FSM kemudian menjadi loop yang relatif sederhana:

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

Seperti disinggung di atas, perhatikan penggunaan ST_ANYsebagai wild-card, yang memungkinkan suatu peristiwa untuk memanggil fungsi tidak peduli keadaan saat ini.EV_ANYjuga bekerja dengan cara yang sama, memungkinkan acara apa pun di negara bagian tertentu untuk memanggil fungsi.

Ini juga dapat menjamin bahwa, jika Anda mencapai akhir array transisi, Anda mendapatkan kesalahan yang menyatakan FSM Anda belum dibangun dengan benar (dengan menggunakan ST_ANY/EV_ANYkombinasi.

Saya telah menggunakan kode yang serupa untuk ini pada banyak proyek komunikasi, seperti implementasi awal tumpukan komunikasi dan protokol untuk sistem embedded. Keuntungan besar adalah kesederhanaan dan kemudahan relatif dalam mengubah susunan transisi.

Saya tidak ragu akan ada abstraksi tingkat yang lebih tinggi yang mungkin lebih cocok saat ini tetapi saya curiga mereka semua akan menjadi seperti ini.

Dan, sebagai ldogpernyataan dalam komentar, Anda dapat menghindari global secara keseluruhan dengan melewatkan pointer struktur ke semua fungsi (dan menggunakannya dalam event loop). Ini akan memungkinkan beberapa mesin negara berjalan berdampingan tanpa gangguan.

Cukup buat tipe struktur yang menyimpan data spesifik mesin (sebutkan minimal) dan gunakan itu sebagai ganti global.

Alasan saya jarang melakukan itu adalah hanya karena sebagian besar mesin negara yang saya tulis adalah tipe tunggal (satu kali, di-proses-mulai, membaca file konfigurasi misalnya), tidak perlu menjalankan lebih dari satu contoh . Tetapi memiliki nilai jika Anda perlu menjalankan lebih dari satu.

Jawaban lain baik, tetapi implementasi yang sangat "ringan" yang saya gunakan ketika mesin negara sangat sederhana terlihat seperti:

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

Saya akan menggunakan ini ketika mesin negara cukup sederhana sehingga penunjuk fungsi & pendekatan tabel transisi terlalu berlebihan. Ini sering berguna untuk penguraian karakter per karakter atau kata per kata.

Maafkan saya karena melanggar setiap aturan dalam ilmu komputer, tetapi mesin negara adalah salah satu dari sedikit (saya dapat menghitung hanya dua) tempat gotopernyataan tidak hanya lebih efisien, tetapi juga membuat kode Anda lebih bersih dan lebih mudah dibaca. Karena gotopernyataan didasarkan pada label, Anda dapat memberi nama negara bagian Anda daripada harus melacak kekacauan angka atau menggunakan enum. Itu juga membuat kode lebih bersih karena Anda tidak memerlukan semua tambahan fungsi pointer fungsi atau pernyataan switch besar dan sementara loop. Apakah saya menyebutkan itu lebih efisien juga?

Seperti apa bentuk mesin negara:

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

Anda mendapatkan ide umum. Intinya adalah bahwa Anda dapat mengimplementasikan mesin negara dengan cara yang efisien dan yang relatif mudah dibaca dan berteriak pada pembaca bahwa mereka melihat mesin negara. Perhatikan bahwa jika Anda menggunakan gotopernyataan, Anda harus tetap berhati-hati karena sangat mudah untuk menembak diri sendiri saat melakukannya.

Anda dapat mempertimbangkan State Machine Compiler http://smc.sourceforge.net/

Utilitas open source yang luar biasa ini menerima deskripsi mesin negara dalam bahasa yang sederhana dan mengkompilasinya ke salah satu dari selusin bahasa - termasuk C dan C ++. Utilitas itu sendiri ditulis dalam Java, dan dapat dimasukkan sebagai bagian dari build.

Alasan untuk melakukan ini, alih-alih pengkodean tangan menggunakan pola GoF State atau pendekatan lainnya, adalah bahwa begitu mesin negara Anda dinyatakan sebagai kode, struktur yang mendasarinya cenderung menghilang di bawah beban pelat ketel yang perlu dihasilkan untuk mendukungnya. Menggunakan pendekatan ini memberi Anda pemisahan keprihatinan yang sangat baik, dan Anda menjaga struktur mesin negara Anda 'terlihat'. Kode yang dibuat secara otomatis masuk ke modul yang tidak perlu Anda sentuh, sehingga Anda dapat kembali dan bermain-main dengan struktur mesin negara tanpa memengaruhi kode pendukung yang telah Anda tulis.

Maaf, saya terlalu antusias, dan tidak diragukan lagi menunda semua orang. Tapi itu adalah utilitas kedudukan tertinggi, dan juga terdokumentasi dengan baik.

Pastikan untuk memeriksa karya Miro Samek (blog State Space , situs web State Machines & Tools ), yang artikel-artikelnya di C / C ++ Users Journal sangat bagus.

Situs web ini berisi implementasi (C / C ++) yang lengkap dalam sumber terbuka dan lisensi komersial kerangka mesin negara (QP Framework) , pengendali event (QEP) , alat pemodelan dasar (QM) dan alat tracing (QSpy) yang memungkinkan untuk menggambar mesin negara, membuat kode dan men-debug mereka.

Buku ini berisi penjelasan yang luas tentang apa / mengapa implementasi dan bagaimana menggunakannya dan juga bahan yang bagus untuk mendapatkan pemahaman tentang dasar-dasar mesin negara yang hirarki dan terbatas.

Situs web ini juga berisi tautan ke beberapa paket dukungan papan untuk penggunaan perangkat lunak dengan platform tertanam.

Saya telah melakukan sesuatu yang mirip dengan apa yang dijelaskan paxdiablo, hanya alih-alih susunan transisi keadaan / peristiwa, saya mengatur array fungsi 2-dimensi pointer, dengan nilai peristiwa sebagai indeks satu sumbu dan nilai kondisi saat ini sebagai yang lain. Kemudian saya hanya menelepon state = state_table[event][state](params)dan hal yang benar terjadi. Sel yang mewakili kombinasi keadaan / peristiwa tidak valid mendapatkan pointer ke fungsi yang mengatakannya, tentu saja.

Jelas, ini hanya berfungsi jika nilai kondisi dan acara keduanya rentang yang berdekatan dan mulai dari 0 atau cukup dekat.

"Kerangka kerja" mesin negara C ++ berbasis template yang sangat bagus diberikan oleh Stefan Heinzmann dalam artikelnya .

Karena tidak ada tautan ke unduhan kode lengkap di artikel, saya telah mengambil kebebasan untuk menempelkan kode ke dalam proyek dan memeriksanya. Barang-barang di bawah ini diuji dan mencakup beberapa bagian kecil yang hilang tetapi cukup jelas.

Inovasi utama di sini adalah bahwa kompiler menghasilkan kode yang sangat efisien. Tindakan masuk / keluar kosong tidak ada biaya. Tindakan masuk / keluar yang tidak kosong diuraikan. Kompiler juga memverifikasi kelengkapan statechart. Tindakan yang hilang menghasilkan kesalahan tautan. Satu-satunya hal yang tidak tertangkap adalah yang hilang Top::init.

Ini adalah alternatif yang sangat bagus untuk implementasi Miro Samek, jika Anda dapat hidup tanpa yang hilang - ini jauh dari implementasi UML Statechart yang lengkap, meskipun mengimplementasikan semantik UML dengan benar, sedangkan kode Samek dengan desain tidak menangani keluar / transisi / entri tindakan dalam urutan yang benar.

Jika kode ini berfungsi untuk apa yang perlu Anda lakukan, dan Anda memiliki kompiler C ++ yang layak untuk sistem Anda, itu mungkin akan berkinerja lebih baik daripada implementasi C / C ++ Miro. Kompiler menghasilkan implementasi mesin transisi, O (1) yang diratakan untuk Anda. Jika audit hasil rakitan mengonfirmasi bahwa optimisasi berfungsi seperti yang diinginkan, Anda mendekati kinerja teoritis. Bagian terbaik: ini relatif kecil, kode mudah dimengerti.

#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

Kode tes berikut.

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

Teknik yang saya suka untuk mesin negara (setidaknya yang untuk kontrol program) adalah dengan menggunakan pointer fungsi. Setiap negara diwakili oleh fungsi yang berbeda. Fungsi mengambil simbol input dan mengembalikan penunjuk fungsi untuk status berikutnya. Monitor loop pengiriman pusat mengambil input berikutnya, mengumpankannya ke kondisi saat ini, dan memproses hasilnya.

Mengetiknya menjadi sedikit aneh, karena C tidak memiliki cara untuk menunjukkan jenis pointer fungsi mengembalikan diri mereka sendiri, sehingga fungsi negara kembali void*. Tetapi Anda dapat melakukan sesuatu seperti ini:

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

Kemudian fungsi status individual Anda dapat mengaktifkan input mereka untuk memproses dan mengembalikan nilai yang sesuai.

Kasing paling sederhana

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

Poin: State bersifat privat, tidak hanya untuk unit kompilasi tetapi juga untuk event_handler. Kasing khusus dapat ditangani secara terpisah dari sakelar utama menggunakan konstruksi apa pun yang dianggap perlu.

Kasus yang lebih kompleks

Saat sakelar menjadi lebih besar dari beberapa layar penuh, pisahkan menjadi fungsi yang menangani masing-masing negara, menggunakan tabel keadaan untuk mencari fungsi secara langsung. Negara masih pribadi untuk pengendali acara. Fungsi state handler mengembalikan status berikutnya. Jika diperlukan beberapa acara masih dapat menerima perawatan khusus di pengendali acara utama. Saya suka melempar kejadian pseudo untuk masuk dan keluar negara dan mungkin memulai mesin negara:

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

Saya tidak yakin jika saya memakukan sintaks, terutama mengenai array pointer fungsi. Saya belum menjalankan semua ini melalui kompiler. Setelah ditinjau, saya perhatikan bahwa saya lupa untuk secara eksplisit membuang status berikutnya saat menangani kejadian pseudo (kurung (kosong) sebelum panggilan ke state_handler ()). Ini adalah sesuatu yang saya suka lakukan bahkan jika kompiler menerima kelalaian dalam diam. Ini memberitahu pembaca kode bahwa "ya, saya memang bermaksud memanggil fungsi tanpa menggunakan nilai kembali", dan mungkin menghentikan alat analisis statis dari peringatan tentang hal itu. Mungkin istimewa karena saya tidak ingat pernah melihat orang lain melakukan ini.

Poin: menambahkan sedikit kerumitan (memeriksa apakah keadaan berikutnya berbeda dari saat ini), dapat menghindari kode duplikat di tempat lain, karena fungsi penangan keadaan dapat menikmati peristiwa pseudo yang terjadi ketika keadaan dimasukkan dan dibiarkan. Ingatlah bahwa keadaan tidak dapat berubah ketika menangani peristiwa pseudo, karena hasil dari penangan keadaan dibuang setelah peristiwa ini. Anda tentu saja dapat memilih untuk mengubah perilaku.

Seorang penangan keadaan akan terlihat seperti ini:

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

Lebih rumit

Ketika unit kompilasi menjadi terlalu besar (apa pun yang Anda rasakan, saya harus mengatakan sekitar 1000 baris), letakkan masing-masing state handler dalam file terpisah. Ketika masing-masing pengendali keadaan menjadi lebih dari beberapa layar, pisahkan setiap acara dalam fungsi yang terpisah, mirip dengan cara sakelar keadaan dibagi. Anda dapat melakukan ini dalam beberapa cara, secara terpisah dari negara atau dengan menggunakan tabel bersama, atau menggabungkan berbagai skema. Beberapa dari mereka telah dibahas di sini oleh yang lain. Urutkan tabel Anda dan gunakan pencarian biner jika kecepatan merupakan persyaratan.

Pemrograman generik

Saya harus menyukai preprocessor untuk menangani masalah seperti menyortir tabel atau bahkan membuat mesin negara dari deskripsi, memungkinkan Anda untuk "menulis program tentang program". Saya percaya ini adalah apa yang orang Boost mengeksploitasi templat C ++, tapi saya menemukan sintaksis samar.

Tabel dua dimensi

Saya telah menggunakan tabel state / event di masa lalu, tetapi saya harus mengatakan bahwa untuk kasus yang paling sederhana, saya tidak menganggapnya perlu dan saya lebih suka kejelasan dan keterbacaan pernyataan switch bahkan jika itu melampaui satu layar penuh. Untuk kasus-kasus yang lebih kompleks, tabel-tabel dengan cepat lepas kendali seperti yang telah dicatat orang lain. Ungkapan-ungkapan yang saya sajikan di sini memungkinkan Anda untuk menambahkan banyak peristiwa dan menyatakan ketika Anda menginginkannya, tanpa harus mempertahankan tabel yang menggunakan memori (bahkan jika itu mungkin program memori).

Penolakan

Kebutuhan khusus dapat membuat idiom-idiom ini kurang berguna, tetapi saya merasa idiom-idiom ini sangat jelas dan dapat dipertahankan.

Sangat tidak teruji, tetapi menyenangkan untuk dikodekan, sekarang dalam versi yang lebih halus daripada jawaban asli saya; versi terbaru dapat ditemukan di 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

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

Saya sangat menyukai jawaban paxdiable dan memutuskan untuk mengimplementasikan semua fitur yang hilang untuk aplikasi saya seperti variabel penjaga dan data spesifik mesin negara.

Saya mengunggah implementasi saya ke situs ini untuk berbagi dengan komunitas. Ini telah diuji menggunakan IAR Embedded Workbench untuk ARM.

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

Alat open source lain yang menarik adalah Yakindu Statechart Tools di statecharts.org . Itu menggunakan statecharts Harel dan dengan demikian menyediakan status hierarkis dan paralel dan menghasilkan kode C dan C ++ (serta Jawa). Itu tidak menggunakan perpustakaan tetapi mengikuti pendekatan 'kode biasa'. Kode ini pada dasarnya menerapkan struktur switch-case. Generator kode juga dapat dikustomisasi. Selain itu alat ini menyediakan banyak fitur lainnya.

Datang ke ini terlambat (seperti biasa) tetapi memindai jawaban sampai saat ini saya pikir ada sesuatu yang penting hilang;

Saya telah menemukan dalam proyek saya sendiri bahwa akan sangat membantu jika tidak memiliki fungsi untuk setiap kombinasi keadaan / acara yang valid. Saya sangat menyukai ide memiliki tabel 2D keadaan / peristiwa secara efektif. Tapi saya suka elemen tabel lebih dari sekedar fungsi pointer sederhana. Alih-alih saya mencoba mengatur desain saya sehingga pada dasarnya itu terdiri dari sekelompok elemen atau tindakan atom sederhana. Dengan begitu saya bisa membuat daftar unsur-unsur atom sederhana di setiap persimpangan negara / tabel acara saya. Idenya adalah bahwa Anda tidak perlu mendefinisikan massa fungsi N kuadrat (biasanya sangat sederhana). Mengapa ada sesuatu yang begitu rawan kesalahan, memakan waktu, sulit untuk ditulis, sulit dibaca, apa saja?

Saya juga menyertakan status baru opsional, dan penunjuk fungsi opsional untuk setiap sel dalam tabel. Pointer fungsi ada untuk kasus-kasus luar biasa di mana Anda tidak ingin hanya memecat daftar aksi atom.

Anda tahu Anda melakukannya dengan benar ketika Anda dapat mengekspresikan banyak fungsi yang berbeda, hanya dengan mengedit tabel Anda, tanpa kode baru untuk ditulis.

Alrght, saya pikir milik saya hanya sedikit berbeda dari milik orang lain. Sedikit lebih banyak pemisahan kode dan data daripada yang saya lihat di jawaban lainnya. Saya benar-benar membaca teori untuk menulis ini, yang mengimplementasikan bahasa Reguler penuh (tanpa ekspresi reguler, dengan sedih). Ullman, Minsky, Chomsky. Tidak bisa mengatakan saya mengerti semuanya, tetapi saya telah mengambil langsung dari para majikan lama: melalui kata-kata mereka.

Saya menggunakan pointer fungsi ke predikat yang menentukan transisi ke keadaan 'ya' atau keadaan 'tidak'. Ini memfasilitasi pembuatan akseptor keadaan terbatas untuk bahasa reguler yang Anda program dengan cara yang lebih mirip bahasa assembly. Tolong jangan diganggu oleh pilihan nama konyol saya. 'czek' == 'centang'. 'grok' == [lihatlah di Kamus Peretas].

Jadi untuk setiap iterasi, czek memanggil fungsi predikat dengan karakter saat ini sebagai argumen. Jika predikat mengembalikan true, karakter dikonsumsi (penunjuk maju) dan kami mengikuti transisi 'y' untuk memilih status berikutnya. Jika predikat mengembalikan false, karakter TIDAK dikonsumsi dan kami mengikuti transisi 'n'. Jadi setiap instruksi adalah cabang dua arah! Saya pasti sudah membaca The Story of Mel pada saat itu.

Kode ini datang langsung dari penerjemah postscript saya , dan berkembang menjadi bentuk saat ini dengan banyak bimbingan dari rekan-rekan di comp.lang.c. Karena postscript pada dasarnya tidak memiliki sintaks (hanya membutuhkan tanda kurung seimbang), Penerima Bahasa Reguler menyukai fungsi ini sebagai pengurai juga.

/* 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 hadir dengan 2 implementasi bagan negara yang berbeda:

• Mesin Status Meta
• Statechart

Seperti biasa, boost akan mengarahkan Anda ke neraka templat.

Perpustakaan pertama adalah untuk lebih banyak mesin keadaan kritis-kinerja. Pustaka kedua memberi Anda jalur transisi langsung dari UML Statechart ke kode.

Inilah pertanyaan SO yang meminta perbandingan antara keduanya di mana kedua penulis merespons.

Ini seri Ars OpenForum posting tentang sedikit agak rumit logika kontrol meliputi implementasi yang sangat mudah tindak sebagai mesin negara di C.

Melihat ini di suatu tempat

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

Mengingat bahwa Anda menyiratkan Anda dapat menggunakan C ++ dan karenanya kode OO, saya akan menyarankan mengevaluasi pola 'GoF'state (GoF = Gang of Four, orang-orang yang menulis buku pola desain yang membawa pola desain menjadi pusat perhatian).

Ini tidak terlalu rumit dan banyak digunakan dan dibahas sehingga mudah untuk melihat contoh dan penjelasan secara online.

Kemungkinan besar juga akan dikenali oleh siapa pun yang menjaga kode Anda di kemudian hari.

Jika efisiensi adalah kekuatiran, perlu dilakukan benchmarking untuk memastikan bahwa pendekatan non-OO lebih efisien karena banyak faktor yang mempengaruhi kinerja dan tidak selalu hanya buruk, kode fungsional baik. Demikian pula, jika penggunaan memori merupakan kendala bagi Anda, maka perlu dilakukan lagi beberapa pengujian atau perhitungan untuk melihat apakah ini benar-benar akan menjadi masalah bagi aplikasi khusus Anda jika Anda menggunakan pola keadaan.

Berikut ini adalah beberapa tautan ke pola status 'Gof', seperti yang disarankan Craig:

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

Berikut adalah contoh Mesin Status Hingga untuk Linux yang menggunakan antrian pesan sebagai acara. Acara diletakkan di antrian dan ditangani secara berurutan. Keadaan berubah tergantung pada apa yang terjadi untuk setiap acara.

Ini adalah contoh untuk koneksi data dengan status seperti:

• Belum diinisialisasi
• Diinisialisasi
• Terhubung
• MTU dinegosiasikan
• Dikonfirmasi

Satu fitur tambahan kecil yang saya tambahkan adalah cap waktu untuk setiap pesan / acara. Penangan acara akan mengabaikan acara yang terlalu lama (sudah kedaluwarsa). Ini bisa terjadi banyak di dunia nyata di mana Anda mungkin terjebak dalam kondisi yang tidak terduga.

Contoh ini berjalan di Linux, gunakan Makefile di bawah ini untuk mengkompilasi dan bermain-main dengannya.

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