Konstrukcja maszyny państwowej C [zamknięty]

193

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

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

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

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

Pompa zdarzeń wskazuje na integrator zdarzeń, który wskazuje na dyspozytora.  Dyspozytor wskazuje od 1 do n akcji, które wskazują na integrator zdarzeń.  Tabela przejścia z symbolami wieloznacznymi wskazuje dyspozytora.

Jldupont
źródło
4
Odpowiedzi tutaj są bardzo dobre. Spójrz także na to zduplikowane pytanie, które ma również kilka dobrych odpowiedzi: stackoverflow.com/questions/1371460/state-machines-tutorials
Michael Burr
2
Jest to również interesujące: stackoverflow.com/questions/133214/…
Daniel Daranas
Zobacz także to pytanie .
Daniel Daranas,

Odpowiedzi:

170

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

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

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

#define ST_ANY              -1
#define ST_INIT              0
#define ST_ERROR             1
#define ST_TERM              2
: :
#define EV_ANY              -1
#define EV_KEYPRESS       5000
#define EV_MOUSEMOVE      5001

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

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

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

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

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

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

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

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

state = ST_INIT;
while (state != ST_TERM) {
    event = GetNextEvent();
    for (i = 0; i < TRANS_COUNT; i++) {
        if ((state == trans[i].st) || (ST_ANY == trans[i].st)) {
            if ((event == trans[i].ev) || (EV_ANY == trans[i].ev)) {
                state = (trans[i].fn)();
                break;
            }
        }
    }
}

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

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

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

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


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

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

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

paxdiablo
źródło
24
Gigantyczny przełącznik miesza kod z FSM. Nawet jeśli istnieje tylko wywołanie funkcji na przejście, wciąż jest trochę kodu i łatwo jest kogoś nadużyć, po prostu dodając małe 4-liniowe przejście w linii. jeden dziesięcioliniowy. Potem wymyka się spod kontroli. Dzięki tablicy struct FSM pozostaje czysty - widać każde przejście i efekt (funkcję). Zacząłem, gdy wyliczenia były błyskiem w oku ISO, pisząc kod dla platform osadzonych 6809 z kompilatorami, które, powiedzmy, były mniej niż idealne :-)
paxdiablo
5
Masz rację, wyliczenia byłyby lepsze, ale nadal wolę mieć FSM jako tablicę strukturalną. Potem wszystko jest obsługiwane przez dane, a nie kod (cóż, jest trochę kodu, ale szansa na wypełnienie pętli FSM, którą podałem, jest niewielka).
paxdiablo
2
Jest to dobre, ponieważ dla maszyn stanu z kontrolą procesu zawsze dodawałem trzy (ewentualnie puste) podstacje dla każdego stanu, tak aby wywołanie funkcji stanu zmieniało się w GotKey (podstate), gdzie podstacją byłoby: - ​​SS_ENTRY - SS_RUN - SS_EXIT Zasadniczo funkcja stanu jest wywoływana z podstacją SS_ENTRY przy wejściu, aby stan mógł zrekonstruować status (np. Pozycje siłowników). Chociaż nie ma przejścia, wartość podstacji SS_RUN zostaje przekazana. Po przejściu funkcja stanu jest wywoływana z podstacją SS_EXIT, dzięki czemu może wykonywać wszelkie porządki (np. Zwalnia zasoby).
Metiu
13
Wspomniałeś, że udostępnianie danych za pomocą globalnych, ale prawdopodobnie byłoby czystsze jeśli definiować funkcje państwowe być int (*fn)(void*);tam gdzie void*jest wskaźnik do danych, że każda funkcja państwo pobiera jako parametr. Następnie funkcje stanu mogą albo użyć danych, albo je zignorować.
ldog
13
Używam tej samej separacji danych / kodów do pisania FSM, tyle że nigdy nie przyszło mi do głowy, aby wprowadzić stany „wieloznaczne”. Ciekawy pomysł! Jednak iteracja tablicy przejść może stać się kosztowna, jeśli masz wiele stanów (tak było w moim przypadku, ponieważ kod C został wygenerowany automatycznie). W takich sytuacjach bardziej efektywne byłoby posiadanie jednej tablicy przejść na stan. Zatem stan nie jest już wartością wyliczoną, lecz tabelą przejściową. W ten sposób nie musisz powtarzać wszystkich przejść w maszynie, a tylko te, które są istotne dla bieżącego stanu.
Frerich Raabe
78

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

enum state { ST_NEW, ST_OPEN, ST_SHIFT, ST_END };

enum state current_state = ST_NEW;

while (current_state != ST_END)
{
    input = get_input();

    switch (current_state)
    {
        case ST_NEW:
        /* Do something with input and set current_state */
        break;

        case ST_OPEN:
        /* Do something different and set current_state */
        break;

        /* ... etc ... */
    }
}

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

caf
źródło
37

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

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

void state_machine() {
first_state:
    // Do some stuff here
    switch(some_var) {
    case 0:
        goto first_state;
    case 1:
        goto second_state;
    default:
        return;
    }

second_state:
    // Do some stuff here
    switch(some_var) {
    case 0:
        goto first_state;
    case 1:
        goto second_state;
    default:
        return;
    }
}

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

Jason E.
źródło
4
Działa to tylko wtedy, gdy automat stanów znajduje się w obiekcie najwyższego poziomu. W chwili, gdy jakiś inny obiekt, do którego od czasu do czasu odpytywane / wysyłane są wiadomości, musi mieć stan, utknąłeś w tym podejściu (to lub musisz go skomplikować)
skrebbel
1
To naprawdę zmusza cię do zastosowania zapobiegawczego wielozadaniowości we wszystkich, z wyjątkiem najprostszych przypadków.
Craig McQueen,
1
Te gotos można zastąpić wywołaniami funkcji. A jeśli profiler powie ci, że twój program tonie z powodu narzutu wywołania funkcji, możesz w razie potrzeby zastąpić wywołania gotos.
Abtin Forouzandeh
7
@AbtinForouzandeh zwykłe zastąpienie gotos wywołaniami funkcji spowodowałoby przepełnienie stosu, ponieważ stos wywołań jest usuwany tylko w przypadku błędu.
JustMaximumPower
Zgadzam się z metodą goto. Oto zestaw makr, które to ilustrują. Makra tworzą strukturę kodu tak, jakbyś go kodował tak, jak zwykle. Działa również na poziomie przerwań, które zwykle są potrzebne tam,
eddyq
30

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

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

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

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

wierzba
źródło
20

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

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

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

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

Daniel Daranas
źródło
Zmodyfikowałem tytuł pytania zgodnie z twoją kalamburem.
jldupont
@jldupont: Chciałem tylko powiedzieć, że lepiej to wyjaśnić. Usunąłem teraz nieistotne części mojej odpowiedzi.
Daniel Daranas
1
Dodałem, czego mogę się spodziewać na stronie internetowej / książce, ponieważ sam z powodzeniem korzystałem z oprogramowania; to najlepsza książka na mojej półce.
Adriaan
@Adriann, świetne wyjaśnienie! Właśnie zmodyfikowałem stronę główną witryny, poprzedni link przestał działać.
Daniel Daranas,
2
Linki są martwe lub wskazują na stronę główną witryny, która prawdopodobnie zmieniła kierunek na oprogramowanie wbudowane. Nadal możesz zobaczyć niektóre treści na state-machine.com/resources/articles.php , ale nawet tam większość linków związanych z automatami stanowymi jest martwa. Jest to jeden z niewielu
Tatiana Racheva
11

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

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

prezes
źródło
1
Wydaje się, że to rozwiązanie nie daje się dobrze skalować: zbyt duże zapełnianie tabel, prawda?
jldupont
2
+1. Problemem skalowania jest tutaj pamięć - moje własne rozwiązanie ma problem z czasem skalowania, tj. Czas potrzebny na przeskanowanie tabeli przejść (chociaż można ręcznie zoptymalizować pod kątem najczęściej występujących przejść). Ten poświęca pamięć dla szybkości - to tylko kompromis. Prawdopodobnie będziesz potrzebować kontroli granic, ale to nie jest złe rozwiązanie.
paxdiablo
Faceci - Mój komentarz nie wyszedł zgodnie z zamierzeniami: miałem na myśli, że jest o wiele bardziej pracochłonny i podatny na błędy. Jeśli dodasz stan / zdarzenie, trzeba wykonać wiele edycji.
jldupont
3
Nikt nie powiedział, że tablica 2D została zainicjowana ręcznie. Może jest coś, co czyta plik konfiguracyjny i tworzy go (a przynajmniej na pewno może być).
John Zwinck,
Jednym ze sposobów inicjowania takich tablic jest wykorzystanie preprocesora jako spóźnionego spoiwa (w przeciwieństwie do wczesnego wiązania). Definiujesz listę wszystkich stanów #define STATE_LIST() \STATE_LIST_ENTRY(state1)\STATE_LIST_ENTRY(state2)\...(implikowany nowy wiersz po każdym \ ), w którym (ponownie) definiujesz makro wprowadzania, gdy używasz makra STATE_LIST. Przykład - co tablicę stanu nazwy: #define STATE_LIST_ENTRY(s) #s , \n const char *state_names[] = { STATE_LIST() };\n #undef STATE_LIST_ENTRY. Niektóre pracują, aby skonfigurować jako pierwsze, ale jest to niezwykle potężne. Dodaj nowy stan -> gwarantowane bez błędów.
hlovdal
9

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

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

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

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

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

#ifndef HSM_HPP
#define HSM_HPP

// This code is from:
// Yet Another Hierarchical State Machine
// by Stefan Heinzmann
// Overload issue 64 december 2004
// http://accu.org/index.php/journals/252

/* This is a basic implementation of UML Statecharts.
 * The key observation is that the machine can only
 * be in a leaf state at any given time. The composite
 * states are only traversed, never final.
 * Only the leaf states are ever instantiated. The composite
 * states are only mechanisms used to generate code. They are
 * never instantiated.
 */

// Helpers

// A gadget from Herb Sutter's GotW #71 -- depends on SFINAE
template<class D, class B>
class IsDerivedFrom {
    class Yes { char a[1]; };
    class No  { char a[10]; };
    static Yes Test(B*); // undefined
    static No Test(...); // undefined
public:
    enum { Res = sizeof(Test(static_cast<D*>(0))) == sizeof(Yes) ? 1 : 0 };
};

template<bool> class Bool {};

// Top State, Composite State and Leaf State

template <typename H>
struct TopState {
    typedef H Host;
    typedef void Base;
    virtual void handler(Host&) const = 0;
    virtual unsigned getId() const = 0;
};

template <typename H, unsigned id, typename B>
struct CompState;

template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct CompState : B {
    typedef B Base;
    typedef CompState<H, id, Base> This;
    template <typename X> void handle(H& h, const X& x) const { Base::handle(h, x); }
    static void init(H&); // no implementation
    static void entry(H&) {}
    static void exit(H&) {}
};

template <typename H>
struct CompState<H, 0, TopState<H> > : TopState<H> {
    typedef TopState<H> Base;
    typedef CompState<H, 0, Base> This;
    template <typename X> void handle(H&, const X&) const {}
    static void init(H&); // no implementation
    static void entry(H&) {}
    static void exit(H&) {}
};

template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct LeafState : B {
    typedef H Host;
    typedef B Base;
    typedef LeafState<H, id, Base> This;
    template <typename X> void handle(H& h, const X& x) const { Base::handle(h, x); }
    virtual void handler(H& h) const { handle(h, *this); }
    virtual unsigned getId() const { return id; }
    static void init(H& h) { h.next(obj); } // don't specialize this
    static void entry(H&) {}
    static void exit(H&) {}
    static const LeafState obj; // only the leaf states have instances
};

template <typename H, unsigned id, typename B>
const LeafState<H, id, B> LeafState<H, id, B>::obj;

// Transition Object

template <typename C, typename S, typename T>
// Current, Source, Target
struct Tran {
    typedef typename C::Host Host;
    typedef typename C::Base CurrentBase;
    typedef typename S::Base SourceBase;
    typedef typename T::Base TargetBase;
    enum { // work out when to terminate template recursion
        eTB_CB = IsDerivedFrom<TargetBase, CurrentBase>::Res,
        eS_CB = IsDerivedFrom<S, CurrentBase>::Res,
        eS_C = IsDerivedFrom<S, C>::Res,
        eC_S = IsDerivedFrom<C, S>::Res,
        exitStop = eTB_CB && eS_C,
        entryStop = eS_C || eS_CB && !eC_S
    };
    // We use overloading to stop recursion.
    // The more natural template specialization
    // method would require to specialize the inner
    // template without specializing the outer one,
    // which is forbidden.
    static void exitActions(Host&, Bool<true>) {}
    static void exitActions(Host&h, Bool<false>) {
        C::exit(h);
        Tran<CurrentBase, S, T>::exitActions(h, Bool<exitStop>());
    }
    static void entryActions(Host&, Bool<true>) {}
    static void entryActions(Host& h, Bool<false>) {
        Tran<CurrentBase, S, T>::entryActions(h, Bool<entryStop>());
        C::entry(h);
    }
    Tran(Host & h) : host_(h) {
        exitActions(host_, Bool<false>());
    }
    ~Tran() {
        Tran<T, S, T>::entryActions(host_, Bool<false>());
        T::init(host_);
    }
    Host& host_;
};

// Initializer for Compound States

template <typename T>
struct Init {
    typedef typename T::Host Host;
    Init(Host& h) : host_(h) {}
    ~Init() {
        T::entry(host_);
        T::init(host_);
    }
    Host& host_;
};

#endif // HSM_HPP

Kod testowy następuje.

#include <cstdio>
#include "hsm.hpp"
#include "hsmtest.hpp"

/* Implements the following state machine from Miro Samek's
 * Practical Statecharts in C/C++
 *
 * |-init-----------------------------------------------------|
 * |                           s0                             |
 * |----------------------------------------------------------|
 * |                                                          |
 * |    |-init-----------|        |-------------------------| |
 * |    |       s1       |---c--->|            s2           | |
 * |    |----------------|<--c----|-------------------------| |
 * |    |                |        |                         | |
 * |<-d-| |-init-------| |        | |-init----------------| | |
 * |    | |     s11    |<----f----| |          s21        | | |
 * | /--| |------------| |        | |---------------------| | |
 * | a  | |            | |        | |                     | | |
 * | \->| |            |------g--------->|-init------|    | | |
 * |    | |____________| |        | |-b->|    s211   |---g--->|
 * |    |----b---^       |------f------->|           |    | | |
 * |    |________________|        | |<-d-|___________|<--e----|
 * |                              | |_____________________| | |
 * |                              |_________________________| |
 * |__________________________________________________________|
 */

class TestHSM;

typedef CompState<TestHSM,0>     Top;
typedef CompState<TestHSM,1,Top>   S0;
typedef CompState<TestHSM,2,S0>      S1;
typedef LeafState<TestHSM,3,S1>        S11;
typedef CompState<TestHSM,4,S0>      S2;
typedef CompState<TestHSM,5,S2>        S21;
typedef LeafState<TestHSM,6,S21>         S211;

enum Signal { A_SIG, B_SIG, C_SIG, D_SIG, E_SIG, F_SIG, G_SIG, H_SIG };

class TestHSM {
public:
    TestHSM() { Top::init(*this); }
    ~TestHSM() {}
    void next(const TopState<TestHSM>& state) {
        state_ = &state;
    }
    Signal getSig() const { return sig_; }
    void dispatch(Signal sig) {
        sig_ = sig;
        state_->handler(*this);
    }
    void foo(int i) {
        foo_ = i;
    }
    int foo() const {
        return foo_;
    }
private:
    const TopState<TestHSM>* state_;
    Signal sig_;
    int foo_;
};

bool testDispatch(char c) {
    static TestHSM test;
    if (c<'a' || 'h'<c) {
        return false;
    }
    printf("Signal<-%c", c);
    test.dispatch((Signal)(c-'a'));
    printf("\n");
    return true;
}

int main(int, char**) {
    testDispatch('a');
    testDispatch('e');
    testDispatch('e');
    testDispatch('a');
    testDispatch('h');
    testDispatch('h');
    return 0;
}

#define HSMHANDLER(State) \
    template<> template<typename X> inline void State::handle(TestHSM& h, const X& x) const

HSMHANDLER(S0) {
    switch (h.getSig()) {
    case E_SIG: { Tran<X, This, S211> t(h);
        printf("s0-E;");
        return; }
    default:
        break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S1) {
    switch (h.getSig()) {
    case A_SIG: { Tran<X, This, S1> t(h);
        printf("s1-A;"); return; }
    case B_SIG: { Tran<X, This, S11> t(h);
        printf("s1-B;"); return; }
    case C_SIG: { Tran<X, This, S2> t(h);
        printf("s1-C;"); return; }
    case D_SIG: { Tran<X, This, S0> t(h);
        printf("s1-D;"); return; }
    case F_SIG: { Tran<X, This, S211> t(h);
        printf("s1-F;"); return; }
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S11) {
    switch (h.getSig()) {
    case G_SIG: { Tran<X, This, S211> t(h);
        printf("s11-G;"); return; }
    case H_SIG: if (h.foo()) {
            printf("s11-H");
            h.foo(0); return;
        } break;
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S2) {
    switch (h.getSig()) {
    case C_SIG: { Tran<X, This, S1> t(h);
        printf("s2-C"); return; }
    case F_SIG: { Tran<X, This, S11> t(h);
        printf("s2-F"); return; }
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S21) {
    switch (h.getSig()) {
    case B_SIG: { Tran<X, This, S211> t(h);
        printf("s21-B;"); return; }
    case H_SIG: if (!h.foo()) {
            Tran<X, This, S21> t(h);
            printf("s21-H;"); h.foo(1);
            return;
        } break;
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S211) {
    switch (h.getSig()) {
    case D_SIG: { Tran<X, This, S21> t(h);
        printf("s211-D;"); return; }
    case G_SIG: { Tran<X, This, S0> t(h);
        printf("s211-G;"); return; }
    }
    return Base::handle(h, x);
}

#define HSMENTRY(State) \
    template<> inline void State::entry(TestHSM&) { \
        printf(#State "-ENTRY;"); \
    }

HSMENTRY(S0)
HSMENTRY(S1)
HSMENTRY(S11)
HSMENTRY(S2)
HSMENTRY(S21)
HSMENTRY(S211)

#define HSMEXIT(State) \
    template<> inline void State::exit(TestHSM&) { \
        printf(#State "-EXIT;"); \
    }

HSMEXIT(S0)
HSMEXIT(S1)
HSMEXIT(S11)
HSMEXIT(S2)
HSMEXIT(S21)
HSMEXIT(S211)

#define HSMINIT(State, InitState) \
    template<> inline void State::init(TestHSM& h) { \
       Init<InitState> i(h); \
       printf(#State "-INIT;"); \
    }

HSMINIT(Top, S0)
HSMINIT(S0, S1)
HSMINIT(S1, S11)
HSMINIT(S2, S21)
HSMINIT(S21, S211)
Kuba Ober
źródło
Hmm ... brakuje czegoś w twoim kodzie. Przede wszystkim dołączasz dwa nagłówki, ale podajesz tylko pierwszy. Kiedy po prostu komentuję instrukcję „włącz”, pojawia się ten błąd podczas kompilacji: d: \ 1 \ hsm> g ++ test.cpp test.cpp: 195: 1: błąd: specjalizacja „static void CompState <H, id, B> :: init (H &) [z H = TestHSM; unsigned int id = 0u; B = CompState <TestHSM, 0u, TopState <TestHSM>>] 'po utworzeniu instancji
Freddie Chopin
Musiałem przenieść definicje wszystkich HSMINIT (), aby były powyżej klasy TestHSM, a to kompiluje się i działa dobrze (; Jedyne, co jest nie tak, to fakt, że wszystkie przejścia są „zewnętrzne”, podczas gdy powinny być „wewnętrzne” - było trochę dyskusji na ten temat w artykule, a autor uznał, że „nadnercza” ma rację, ale użyte strzałki sugerują „wewnętrzny”
Freddie Chopin
5

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

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

typedef void* (*state_handler)(input_symbol_t);
void dispatch_fsm()
{
    state_handler current = initial_handler;
    /* Let's assume returning null indicates end-of-machine */
    while (current) {
        current = current(get_input);
    }
 }

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

Michael Ekstrand
źródło
+1, które jest naprawdę miłe i zapewnia ładne miejsca do obsługi funkcji wewnątrz funkcji przejścia
Fire Crow
5

Najprostszy przypadek

enum event_type { ET_THIS, ET_THAT };
union event_parm { uint8_t this; uint16_t that; }
static void handle_event(enum event_type event, union event_parm parm)
{
  static enum { THIS, THAT } state;
  switch (state)
  {
    case THIS:
    switch (event)
    {
      case ET_THIS:
      // Handle event.
      break;

      default:
      // Unhandled events in this state.
      break;
    }
    break;

    case THAT:
    // Handle state.
    break;
  }
}

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

Bardziej złożona sprawa

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

enum state_type { THIS, THAT, FOO, NA };
enum event_type { ET_START, ET_ENTER, ET_EXIT, ET_THIS, ET_THAT, ET_WHATEVER, ET_TIMEOUT };
union event_parm { uint8_t this; uint16_t that; };
static void handle_event(enum event_type event, union event_parm parm)
{
  static enum state_type state;
  static void (* const state_handler[])(enum event_type event, union event_parm parm) = { handle_this, handle_that };
  enum state_type next_state = state_handler[state](event, parm);
  if (NA != next_state && state != next_state)
  {
    (void)state_handler[state](ET_EXIT, 0);
    state = next_state;
    (void)state_handler[state](ET_ENTER, 0);
  }
}

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

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

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

static enum state_type handle_this(enum event_type event, union event_parm parm)
{
  enum state_type next_state = NA;
  switch (event)
  {
    case ET_ENTER:
    // Start a timer to do whatever.
    // Do other stuff necessary when entering this state.
    break;

    case ET_WHATEVER:
    // Switch state.
    next_state = THAT;
    break;

    case ET_TIMEOUT:
    // Switch state.
    next_state = FOO;
    break;

    case ET_EXIT:
    // Stop the timer.
    // Generally clean up this state.
    break;
  }
  return next_state;
}

Większa złożoność

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

Programowanie ogólne

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

Stoły dwuwymiarowe

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

Zrzeczenie się

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

Joe Chomik
źródło
Unikałbym tego jako nazwy zmiennej lub symbolu tylko dla skojarzenia, nawet jeśli tak naprawdę nie jest to słowo zastrzeżone.
XTL
4

Niezwykle niesprawdzony, ale przyjemny w kodowaniu, teraz w bardziej dopracowanej wersji niż moja pierwotna odpowiedź; aktualne wersje można znaleźć na stronie mercurial.intuxication.org :

sm.h

#ifndef SM_ARGS
#error "SM_ARGS undefined: " \
    "use '#define SM_ARGS (void)' to get an empty argument list"
#endif

#ifndef SM_STATES
#error "SM_STATES undefined: " \
    "you must provide a list of comma-separated states"
#endif

typedef void (*sm_state) SM_ARGS;
static const sm_state SM_STATES;

#define sm_transit(STATE) ((sm_state (*) SM_ARGS)STATE)

#define sm_def(NAME) \
    static sm_state NAME ## _fn SM_ARGS; \
    static const sm_state NAME = (sm_state)NAME ## _fn; \
    static sm_state NAME ## _fn SM_ARGS

przyklad.c

#include <stdio.h>

#define SM_ARGS (int i)
#define SM_STATES EVEN, ODD
#include "sm.h"

sm_def(EVEN)
{
    printf("even %i\n", i);
    return ODD;
}

sm_def(ODD)
{
    printf("odd  %i\n", i);
    return EVEN;
}

int main(void)
{
    int i = 0;
    sm_state state = EVEN;

    for(; i < 10; ++i)
        state = sm_transit(state)(i);

    return 0;
}
Christoph
źródło
14
Uwielbiam komentarz „bardzo nieprzetestowany”. Wydaje się wskazywać, że istnieją stopnie nie przetestowania i że włożyłeś sporo wysiłku w nie testowanie :-)
paxdiablo,
@Christoph link w tej odpowiedzi jest uszkodzony. Ponadto przetestowałeś ten kod, czy nie? Jeśli został przetestowany i działa, należy usunąć go z odpowiedzi. Może także pokazać przykład kodu, który powoduje to po rozwinięciu makr. Podoba mi się ogólny pomysł.
Joakim
4

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

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

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

użytkownik108570
źródło
Znalezienie tego w 2018 r. I nadal obowiązuje. Czytałem odpowiedź @paxdiablo i już wcześniej z powodzeniem korzystałem z tego typu implementacji w systemach wbudowanych. W tym rozwiązaniu brakuje brakujących odpowiedzi z odpowiedzi na paxdiablos :)
Kristoffer
4

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

Axel T.
źródło
3

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

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

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

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

Bill Forster
źródło
2
Może przykład byłby miły, nie?
jldupont
1
Realistyczny przykład, który można przedstawić w oderwaniu, jest trudnym zadaniem, które wymagałoby więcej czasu, niż jestem gotów dać w tej chwili. Czy w moim poście jest coś szczególnie trudnego do zrozumienia? Może mogę to wyrazić jaśniej. Pomysł jest bardzo prosty; Nie definiuj mechanizmu stanu, który wymaga osobnej funkcji dla każdej kombinacji zdarzeń / stanów, w ten sposób otrzymujesz zbyt wiele funkcji. Zamiast tego znajdź inny sposób na opisanie pożądanej funkcjonalności dla tej kombinacji zdarzenia / stanu, przynajmniej w większości przypadków.
Bill Forster,
2
Zrozumiano: przykład pseudokodu byłby dobry, ale twój punkt widzenia jest jasny.
jldupont
3

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

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

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

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

/* currentstr is set to the start of string by czek
   and used by setrad (called by israd) to set currentrad
   which is used by israddig to determine if the character
   in question is valid for the specified radix
   --
   a little semantic checking in the syntax!
 */
char *currentstr;
int currentrad;
void setrad(void) {
    char *end;
    currentrad = strtol(currentstr, &end, 10);
    if (*end != '#' /* just a sanity check,
                       the automaton should already have determined this */
    ||  currentrad > 36
    ||  currentrad < 2)
        fatal("bad radix"); /* should probably be a simple syntaxerror */
}

/*
   character classes
   used as tests by automatons under control of czek
 */
char *alpha = "0123456789" "ABCDE" "FGHIJ" "KLMNO" "PQRST" "UVWXYZ";
#define EQ(a,b) a==b
#define WITHIN(a,b) strchr(a,b)!=NULL
int israd  (int c) {
    if (EQ('#',c)) { setrad(); return true; }
    return false;
}
int israddig(int c) {
    return strchrnul(alpha,toupper(c))-alpha <= currentrad;
}
int isdot  (int c) {return EQ('.',c);}
int ise    (int c) {return WITHIN("eE",c);}
int issign (int c) {return WITHIN("+-",c);}
int isdel  (int c) {return WITHIN("()<>[]{}/%",c);}
int isreg  (int c) {return c!=EOF && !isspace(c) && !isdel(c);}
#undef WITHIN
#undef EQ

/*
   the automaton type
 */
typedef struct { int (*pred)(int); int y, n; } test;

/*
   automaton to match a simple decimal number
 */
/* /^[+-]?[0-9]+$/ */
test fsm_dec[] = {
/* 0*/ { issign,  1,  1 },
/* 1*/ { isdigit, 2, -1 },
/* 2*/ { isdigit, 2, -1 },
};
int acc_dec(int i) { return i==2; }

/*
   automaton to match a radix number
 */
/* /^[0-9]+[#][a-Z0-9]+$/ */
test fsm_rad[] = {
/* 0*/ { isdigit,  1, -1 },
/* 1*/ { isdigit,  1,  2 },
/* 2*/ { israd,    3, -1 },
/* 3*/ { israddig, 4, -1 },
/* 4*/ { israddig, 4, -1 },
};
int acc_rad(int i) { return i==4; }

/*
   automaton to match a real number
 */
/* /^[+-]?(d+(.d*)?)|(d*.d+)([eE][+-]?d+)?$/ */
/* represents the merge of these (simpler) expressions
   [+-]?[0-9]+\.[0-9]*([eE][+-]?[0-9]+)?
   [+-]?[0-9]*\.[0-9]+([eE][+-]?[0-9]+)?
   The complexity comes from ensuring at least one
   digit in the integer or the fraction with optional
   sign and optional optionally-signed exponent.
   So passing isdot in state 3 means at least one integer digit has been found
   but passing isdot in state 4 means we must find at least one fraction digit
   via state 5 or the whole thing is a bust.
 */
test fsm_real[] = {
/* 0*/ { issign,  1,   1 },
/* 1*/ { isdigit, 2,   4 },
/* 2*/ { isdigit, 2,   3 },
/* 3*/ { isdot,   6,   7 },
/* 4*/ { isdot,   5,  -1 },
/* 5*/ { isdigit, 6,  -1 },
/* 6*/ { isdigit, 6,   7 },
/* 7*/ { ise,     8,  -1 },
/* 8*/ { issign,  9,   9 },
/* 9*/ { isdigit, 10, -1 },
/*10*/ { isdigit, 10, -1 },
};
int acc_real(int i) {
    switch(i) {
        case 2: /* integer */
        case 6: /* real */
        case 10: /* real with exponent */
            return true;
    }
    return false;
}

/*
   Helper function for grok.
   Execute automaton against the buffer,
   applying test to each character:
       on success, consume character and follow 'y' transition.
       on failure, do not consume but follow 'n' transition.
   Call yes function to determine if the ending state
   is considered an acceptable final state.
   A transition to -1 represents rejection by the automaton
 */
int czek (char *s, test *fsm, int (*yes)(int)) {
    int sta = 0;
    currentstr = s;
    while (sta!=-1 && *s) {
        if (fsm[sta].pred((int)*s)) {
            sta=fsm[sta].y;
            s++;
        } else {
            sta=fsm[sta].n;
        }
    }
    return yes(sta);
}

/*
   Helper function for toke.
   Interpret the contents of the buffer,
   trying automatons to match number formats;
   and falling through to a switch for special characters.
   Any token consisting of all regular characters
   that cannot be interpreted as a number is an executable name
 */
object grok (state *st, char *s, int ns,
    object *src,
    int (*next)(state *,object *),
    void (*back)(state *,int, object *)) {

    if (czek(s, fsm_dec, acc_dec)) {
        long num;
        num = strtol(s,NULL,10);
        if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) {
            error(st,limitcheck);
/*       } else if (num > INT_MAX || num < INT_MIN) { */
/*           error(limitcheck, OP_token); */
        } else {
            return consint(num);
        }
    }

    else if (czek(s, fsm_rad, acc_rad)) {
        long ra,num;
        ra = (int)strtol(s,NULL,10);
        if (ra > 36 || ra < 2) {
            error(st,limitcheck);
        }
        num = strtol(strchr(s,'#')+1, NULL, (int)ra);
        if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) {
            error(st,limitcheck);
/*       } else if (num > INT_MAX || num < INT_MAX) { */
/*           error(limitcheck, OP_token); */
        } else {
            return consint(num);
        }
    }

    else if (czek(s, fsm_real, acc_real)) {
        double num;
        num = strtod(s,NULL);
        if ((num==HUGE_VAL || num==-HUGE_VAL) && errno==ERANGE) {
            error(st,limitcheck);
        } else {
            return consreal(num);
        }
    }

    else switch(*s) {
        case '(': {
            int c, defer=1;
            char *sp = s;

            while (defer && (c=next(st,src)) != EOF ) {
                switch(c) {
                    case '(': defer++; break;
                    case ')': defer--;
                        if (!defer) goto endstring;
                        break;
                    case '\\': c=next(st,src);
                        switch(c) {
                            case '\n': continue;
                            case 'a': c = '\a'; break;
                            case 'b': c = '\b'; break;
                            case 'f': c = '\f'; break;
                            case 'n': c = '\n'; break;
                            case 'r': c = '\r'; break;
                            case 't': c = '\t'; break;
                            case 'v': c = '\v'; break;
                            case '\'': case '\"':
                            case '(': case ')':
                            default: break;
                        }
                }
                if (sp-s>ns) error(st,limitcheck);
                else *sp++ = c;
            }
endstring:  *sp=0;
            return cvlit(consstring(st,s,sp-s));
        }

        case '<': {
            int c;
            char d, *x = "0123456789abcdef", *sp = s;
            while (c=next(st,src), c!='>' && c!=EOF) {
                if (isspace(c)) continue;
                if (isxdigit(c)) c = strchr(x,tolower(c)) - x;
                else error(st,syntaxerror);
                d = (char)c << 4;
                while (isspace(c=next(st,src))) /*loop*/;
                if (isxdigit(c)) c = strchr(x,tolower(c)) - x;
                else error(st,syntaxerror);
                d |= (char)c;
                if (sp-s>ns) error(st,limitcheck);
                *sp++ = d;
            }
            *sp = 0;
            return cvlit(consstring(st,s,sp-s));
        }

        case '{': {
            object *a;
            size_t na = 100;
            size_t i;
            object proc;
            object fin;

            fin = consname(st,"}");
            (a = malloc(na * sizeof(object))) || (fatal("failure to malloc"),0);
            for (i=0 ; objcmp(st,a[i]=toke(st,src,next,back),fin) != 0; i++) {
                if (i == na-1)
                (a = realloc(a, (na+=100) * sizeof(object))) || (fatal("failure to malloc"),0);
            }
            proc = consarray(st,i);
            { size_t j;
                for (j=0; j<i; j++) {
                    a_put(st, proc, j, a[j]);
                }
            }
            free(a);
            return proc;
        }

        case '/': {
            s[1] = (char)next(st,src);
            puff(st, s+2, ns-2, src, next, back);
            if (s[1] == '/') {
                push(consname(st,s+2));
                opexec(st, op_cuts.load);
                return pop();
            }
            return cvlit(consname(st,s+1));
        }

        default: return consname(st,s);
    }
    return null; /* should be unreachable */
}

/*
   Helper function for toke.
   Read into buffer any regular characters.
   If we read one too many characters, put it back
   unless it's whitespace.
 */
int puff (state *st, char *buf, int nbuf,
    object *src,
    int (*next)(state *,object *),
    void (*back)(state *,int, object *)) {
    int c;
    char *s = buf;
    while (isreg(c=next(st,src))) {
        if (s-buf >= nbuf-1) return false;
        *s++ = c;
    }
    *s = 0;
    if (!isspace(c) && c != EOF) back(st,c,src); /* eat interstice */
    return true;
}

/*
   Helper function for Stoken Ftoken.
   Read a token from src using next and back.
   Loop until having read a bona-fide non-whitespace non-comment character.
   Call puff to read into buffer up to next delimiter or space.
   Call grok to figure out what it is.
 */
#define NBUF MAXLINE
object toke (state *st, object *src,
        int (*next)(state *, object *),
        void (*back)(state *, int, object *)) {
    char buf[NBUF] = "", *s=buf;
    int c,sta = 1;
    object o;

    do {
        c=next(st,src);
        //if (c==EOF) return null;
        if (c=='%') {
            if (DUMPCOMMENTS) fputc(c, stdout);
            do {
                c=next(st,src);
                if (DUMPCOMMENTS) fputc(c, stdout);
            } while (c!='\n' && c!='\f' && c!=EOF);
        }
    } while (c!=EOF && isspace(c));
    if (c==EOF) return null;
    *s++ = c;
    *s = 0;
    if (!isdel(c)) sta=puff(st, s,NBUF-1,src,next,back);

    if (sta) {
        o=grok(st,buf,NBUF-1,src,next,back);
        return o;
    } else {
        return null;
    }
}
luser droog
źródło
2
Właśnie to chętnie wyemituje dla ciebie dowolny parser lub generator leksykalny. Tak niecodziennie. To, czy chcesz ręcznie go zakodować, jest wątpliwe. Ma oczywiście zalety pedagogiczne.
Przywróć Monikę
3

boost.org zawiera 2 różne implementacje wykresów stanu:

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

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

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

Roland Wolf
źródło
2

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

Steven Huwig
źródło
2

Widziałem to gdzieś

#define FSM
#define STATE(x)      s_##x :
#define NEXTSTATE(x)  goto s_##x

FSM {
  STATE(x) {
    ...
    NEXTSTATE(y);
  }

  STATE(y) {
    ...
    if (x == 0)
      NEXTSTATE(y);
    else
      NEXTSTATE(x);
  }
}
pixelbeat
źródło
1
Jest to interesujące, ale nie głosuj, dopóki nie podasz przykładu lub dwóch (i być może rezultatu pozbawionego makr) lub dyskusji, dlaczego może to być bardziej praktyczne niż inne. Ciekawe zastosowanie osieroconych nawiasów i makr. Wyobrażam sobie, że coś podobnego można by zrobić w języku, który dokonuje pewnego rodzaju optymalizacji rekurencji ogona; możesz użyć prostych wywołań funkcji i nie martwić się o przeładowanie przestrzeni stosu śmieciami wywołań funkcji (myślę, że to właśnie makra są w zasadzie przezwyciężane tutaj)
Ape-inago
2
Zaletami tej metody są ...? Widzę kilka wad, takich jak zaciemnianie makr, a korzystanie z nich gotostwarza zależność od systemu operacyjnego z wielozadaniowością.
Craig McQueen,
2

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

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

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

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

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

Mick
źródło
wygląda bardziej jak komentarz: czy mógłbym zasugerować, aby traktować to jako takie? tzn. nie umieszczaj go w sekcji „odpowiedz”.
jldupont
Byłoby dobrze, gdybyś mógł podać dobry link URL do „wzorca stanu GoF” dla tych, którzy go nie znają.
Craig McQueen,
1
@jldupont - uczciwy komentarz. Zmieniłem tekst, aby był właściwą odpowiedzią, ponieważ uważam, że w oparciu o osobiste doświadczenia, o ile nie występują szczególne problemy z wydajnością, podejście GoF działa dobrze i będzie mieć stosunkowo dużą „bazę użytkowników”
Mick
@Craig - dodano kilka linków. Oba wyglądały dokładnie i wyraźnie w momencie ich dodawania.
Mick
2

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

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

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

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

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

state_machine.c

#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <unistd.h>   // sysconf()
#include <errno.h>    // errno
#include <string.h>   // strerror()
#include <sys/time.h> // gettimeofday()
#include <fcntl.h>    // For O_* constants
#include <sys/stat.h> // For mode constants

#include <mqueue.h>
#include <poll.h>

//------------------------------------------------
// States
//------------------------------------------------
typedef enum
{
    ST_UNKNOWN = 0,
    ST_UNINIT,
    ST_INIT,
    ST_CONNECTED,
    ST_MTU_NEGOTIATED,
    ST_AUTHENTICATED,
    ST_ERROR,
    ST_DONT_CHANGE,
    ST_TERM,
} fsmState_t;

//------------------------------------------------
// Events
//------------------------------------------------
typedef enum
{
    EV_UNKNOWN = 0,
    EV_INIT_SUCCESS,
    EV_INIT_FAIL,
    EV_MASTER_CMD_MSG,
    EV_CONNECT_SUCCESS,
    EV_CONNECT_FAIL,
    EV_MTU_SUCCESS,
    EV_MTU_FAIL,
    EV_AUTH_SUCCESS,
    EV_AUTH_FAIL,
    EV_TX_SUCCESS,
    EV_TX_FAIL,
    EV_DISCONNECTED,
    EV_DISCON_FAILED,
    EV_LAST_ENTRY,
} fsmEvName_t;

typedef struct fsmEvent_type
{
    fsmEvName_t name;
    struct timeval genTime; // Time the event was generated.
                            // This allows us to see how old the event is.
} fsmEvent_t;

// Finite State Machine Data Members
typedef struct fsmData_type
{
    int  connectTries;
    int  MTUtries;
    int  authTries;
    int  txTries;
} fsmData_t;

// Each row of the state table
typedef struct stateTable_type {
    fsmState_t  st;             // Current state
    fsmEvName_t evName;         // Got this event
    int (*conditionfn)(void *);  // If this condition func returns TRUE
    fsmState_t nextState;       // Change to this state and
    void (*fn)(void *);          // Run this function
} stateTable_t;

// Finite State Machine state structure
typedef struct fsm_type
{
    const stateTable_t *pStateTable; // Pointer to state table
    int        numStates;            // Number of entries in the table
    fsmState_t currentState;         // Current state
    fsmEvent_t currentEvent;         // Current event
    fsmData_t *fsmData;              // Pointer to the data attributes
    mqd_t      mqdes;                // Message Queue descriptor
    mqd_t      master_cmd_mqdes;     // Master command message queue
} fsm_t;

// Wildcard events and wildcard state
#define   EV_ANY    -1
#define   ST_ANY    -1
#define   TRUE     (1)
#define   FALSE    (0)

// Maximum priority for message queues (see "man mq_overview")
#define FSM_PRIO  (sysconf(_SC_MQ_PRIO_MAX) - 1)

static void addev                              (fsm_t *fsm, fsmEvName_t ev);
static void doNothing                          (void *fsm) {addev(fsm, EV_MASTER_CMD_MSG);}
static void doInit                             (void *fsm) {addev(fsm, EV_INIT_SUCCESS);}
static void doConnect                          (void *fsm) {addev(fsm, EV_CONNECT_SUCCESS);}
static void doMTU                              (void *fsm) {addev(fsm, EV_MTU_SUCCESS);}
static void reportFailConnect                  (void *fsm) {addev(fsm, EV_ANY);}
static void doAuth                             (void *fsm) {addev(fsm, EV_AUTH_SUCCESS);}
static void reportDisConnect                   (void *fsm) {addev(fsm, EV_ANY);}
static void doDisconnect                       (void *fsm) {addev(fsm, EV_ANY);}
static void doTransaction                      (void *fsm) {addev(fsm, EV_TX_FAIL);}
static void fsmError                           (void *fsm) {addev(fsm, EV_ANY);}

static int currentlyLessThanMaxConnectTries    (void *fsm) {
    fsm_t *l = (fsm_t *)fsm;
    return (l->fsmData->connectTries < 5 ? TRUE : FALSE);
}
static int        isMoreThanMaxConnectTries    (void *fsm) {return TRUE;}
static int currentlyLessThanMaxMTUtries        (void *fsm) {return TRUE;}
static int        isMoreThanMaxMTUtries        (void *fsm) {return TRUE;}
static int currentyLessThanMaxAuthTries        (void *fsm) {return TRUE;}
static int       isMoreThanMaxAuthTries        (void *fsm) {return TRUE;}
static int currentlyLessThanMaxTXtries         (void *fsm) {return FALSE;}
static int        isMoreThanMaxTXtries         (void *fsm) {return TRUE;}
static int didNotSelfDisconnect                (void *fsm) {return TRUE;}

static int  waitForEvent                       (fsm_t *fsm);
static void runEvent                           (fsm_t *fsm);
static void runStateMachine(fsm_t *fsm);
static int newEventIsValid(fsmEvent_t *event);
static void getTime(struct timeval *time);
void printState(fsmState_t st);
void printEvent(fsmEvName_t ev);

// Global State Table
const stateTable_t GST[] = {
    // Current state         Got this event          If this condition func returns TRUE     Change to this state and    Run this function
    { ST_UNINIT,             EV_INIT_SUCCESS,        NULL,                                   ST_INIT,                    &doNothing              },
    { ST_UNINIT,             EV_INIT_FAIL,           NULL,                                   ST_UNINIT,                  &doInit                 },
    { ST_INIT,               EV_MASTER_CMD_MSG,      NULL,                                   ST_INIT,                    &doConnect              },
    { ST_INIT,               EV_CONNECT_SUCCESS,     NULL,                                   ST_CONNECTED,               &doMTU                  },
    { ST_INIT,               EV_CONNECT_FAIL,        &currentlyLessThanMaxConnectTries,      ST_INIT,                    &doConnect              },
    { ST_INIT,               EV_CONNECT_FAIL,        &isMoreThanMaxConnectTries,             ST_INIT,                    &reportFailConnect      },
    { ST_CONNECTED,          EV_MTU_SUCCESS,         NULL,                                   ST_MTU_NEGOTIATED,          &doAuth                 },
    { ST_CONNECTED,          EV_MTU_FAIL,            &currentlyLessThanMaxMTUtries,          ST_CONNECTED,               &doMTU                  },
    { ST_CONNECTED,          EV_MTU_FAIL,            &isMoreThanMaxMTUtries,                 ST_CONNECTED,               &doDisconnect           },
    { ST_CONNECTED,          EV_DISCONNECTED,        &didNotSelfDisconnect,                  ST_INIT,                    &reportDisConnect       },
    { ST_MTU_NEGOTIATED,     EV_AUTH_SUCCESS,        NULL,                                   ST_AUTHENTICATED,           &doTransaction          },
    { ST_MTU_NEGOTIATED,     EV_AUTH_FAIL,           &currentyLessThanMaxAuthTries,          ST_MTU_NEGOTIATED,          &doAuth                 },
    { ST_MTU_NEGOTIATED,     EV_AUTH_FAIL,           &isMoreThanMaxAuthTries,                ST_MTU_NEGOTIATED,          &doDisconnect           },
    { ST_MTU_NEGOTIATED,     EV_DISCONNECTED,        &didNotSelfDisconnect,                  ST_INIT,                    &reportDisConnect       },
    { ST_AUTHENTICATED,      EV_TX_SUCCESS,          NULL,                                   ST_AUTHENTICATED,           &doDisconnect           },
    { ST_AUTHENTICATED,      EV_TX_FAIL,             &currentlyLessThanMaxTXtries,           ST_AUTHENTICATED,           &doTransaction          },
    { ST_AUTHENTICATED,      EV_TX_FAIL,             &isMoreThanMaxTXtries,                  ST_AUTHENTICATED,           &doDisconnect           },
    { ST_AUTHENTICATED,      EV_DISCONNECTED,        &didNotSelfDisconnect,                  ST_INIT,                    &reportDisConnect       },
    { ST_ANY,                EV_DISCON_FAILED,       NULL,                                   ST_DONT_CHANGE,             &doDisconnect           },
    { ST_ANY,                EV_ANY,                 NULL,                                   ST_UNINIT,                  &fsmError               }    // Wildcard state for errors
};

#define GST_COUNT (sizeof(GST)/sizeof(stateTable_t))

int main()
{
    int ret = 0;
    fsmData_t dataAttr;
    dataAttr.connectTries = 0;
    dataAttr.MTUtries     = 0;
    dataAttr.authTries    = 0;
    dataAttr.txTries      = 0;

    fsm_t lfsm;
    memset(&lfsm, 0, sizeof(fsm_t));
    lfsm.pStateTable       = GST;
    lfsm.numStates         = GST_COUNT;
    lfsm.currentState      = ST_UNINIT;
    lfsm.currentEvent.name = EV_ANY;
    lfsm.fsmData           = &dataAttr;

    struct mq_attr attr;
    attr.mq_maxmsg = 30;
    attr.mq_msgsize = sizeof(fsmEvent_t);

    // Dev info
    //printf("Size of fsmEvent_t [%ld]\n", sizeof(fsmEvent_t));

    ret = mq_unlink("/abcmq");
    if (ret == -1) {
        fprintf(stderr, "Error on mq_unlink(), errno[%d] strerror[%s]\n",
                errno, strerror(errno));
    }

    lfsm.mqdes = mq_open("/abcmq", O_CREAT | O_RDWR, S_IWUSR | S_IRUSR, &attr);
    if (lfsm.mqdes == (mqd_t)-1) {
        fprintf(stderr, "Error on mq_open(), errno[%d] strerror[%s]\n",
                errno, strerror(errno));
        return -1;
    }

    doInit(&lfsm);  // This will generate the first event
    runStateMachine(&lfsm);

    return 0;
}


static void runStateMachine(fsm_t *fsm)
{
    int ret = 0;

    if (fsm == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return;
    }

    // Cycle through the state machine
    while (fsm->currentState != ST_TERM) {
        printf("current state [");
        printState(fsm->currentState);
        printf("]\n");

        ret = waitForEvent(fsm);
        if (ret == 0) {
            printf("got event [");
            printEvent(fsm->currentEvent.name);
            printf("]\n");

            runEvent(fsm);
        }
        sleep(2);
    }
}


static int waitForEvent(fsm_t *fsm)
{
    //const int numFds = 2;
    const int numFds = 1;
    struct pollfd fds[numFds];
    int timeout_msecs = -1; // -1 is forever
    int ret = 0;
    int i = 0;
    ssize_t num = 0;
    fsmEvent_t newEv;

    if (fsm == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return -1;
    }

    fsm->currentEvent.name = EV_ANY;

    fds[0].fd     = fsm->mqdes;
    fds[0].events = POLLIN;
    //fds[1].fd     = fsm->master_cmd_mqdes;
    //fds[1].events = POLLIN;
    ret = poll(fds, numFds, timeout_msecs);

    if (ret > 0) {
        // An event on one of the fds has occurred
        for (i = 0; i < numFds; i++) {
            if (fds[i].revents & POLLIN) {
                // Data may be read on device number i
                num = mq_receive(fds[i].fd, (void *)(&newEv),
                                 sizeof(fsmEvent_t), NULL);
                if (num == -1) {
                    fprintf(stderr, "Error on mq_receive(), errno[%d] "
                            "strerror[%s]\n", errno, strerror(errno));
                    return -1;
                }

                if (newEventIsValid(&newEv)) {
                    fsm->currentEvent = newEv;
                } else {
                    return -1;
                }
            }
        }
    } else {
        fprintf(stderr, "Error on poll(), ret[%d] errno[%d] strerror[%s]\n",
                ret, errno, strerror(errno));
        return -1;
    }

    return 0;
}


static int newEventIsValid(fsmEvent_t *event)
{
    if (event == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return FALSE;
    }

    printf("[%s]\n", __func__);

    struct timeval now;
    getTime(&now);

    if ( (event->name < EV_LAST_ENTRY) &&
         ((now.tv_sec - event->genTime.tv_sec) < (60*5))
       )
    {
        return TRUE;
    } else {
        return FALSE;
    }
}


//------------------------------------------------
// Performs event handling on the FSM (finite state machine).
// Make sure there is a wildcard state at the end of
// your table, otherwise; the event will be ignored.
//------------------------------------------------
static void runEvent(fsm_t *fsm)
{
    int i;
    int condRet = 0;

    if (fsm == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return;
    }

    printf("[%s]\n", __func__);

    // Find a relevant entry for this state and event
    for (i = 0; i < fsm->numStates; i++) {
        // Look in the table for our current state or ST_ANY
        if (  (fsm->pStateTable[i].st == fsm->currentState) ||
              (fsm->pStateTable[i].st == ST_ANY)
           )
        {
            // Is this the event we are looking for?
            if ( (fsm->pStateTable[i].evName == fsm->currentEvent.name) ||
                 (fsm->pStateTable[i].evName == EV_ANY)
               )
            {
                if (fsm->pStateTable[i].conditionfn != NULL) {
                    condRet = fsm->pStateTable[i].conditionfn(fsm->fsmData);
                }

                // See if there is a condition associated
                // or we are not looking for any condition
                //
                if ( (condRet != 0) || (fsm->pStateTable[i].conditionfn == NULL))
                {
                    // Set the next state (if applicable)
                    if (fsm->pStateTable[i].nextState != ST_DONT_CHANGE) {
                        fsm->currentState = fsm->pStateTable[i].nextState;
                        printf("new state [");
                        printState(fsm->currentState);
                        printf("]\n");
                    }

                    // Call the state callback function
                    fsm->pStateTable[i].fn(fsm);
                    break;
                }
            }
        }
    }
}


//------------------------------------------------
//               EVENT HANDLERS
//------------------------------------------------
static void getTime(struct timeval *time)
{
    if (time == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return;
    }

    printf("[%s]\n", __func__);

    int ret = gettimeofday(time, NULL);
    if (ret != 0) {
        fprintf(stderr, "gettimeofday() failed: errno [%d], strerror [%s]\n",
                errno, strerror(errno));
        memset(time, 0, sizeof(struct timeval));
    }
}


static void addev (fsm_t *fsm, fsmEvName_t ev)
{
    int ret = 0;

    if (fsm == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return;
    }

    printf("[%s] ev[%d]\n", __func__, ev);

    if (ev == EV_ANY) {
        // Don't generate a new event, just return...
        return;
    }

    fsmEvent_t newev;
    getTime(&(newev.genTime));
    newev.name = ev;

    ret = mq_send(fsm->mqdes, (void *)(&newev), sizeof(fsmEvent_t), FSM_PRIO);
    if (ret == -1) {
        fprintf(stderr, "[%s] mq_send() failed: errno [%d], strerror [%s]\n",
                __func__, errno, strerror(errno));
    }
}
//------------------------------------------------
//           end EVENT HANDLERS
//------------------------------------------------

void printState(fsmState_t st)
{
    switch(st) {
        case    ST_UNKNOWN:
        printf("ST_UNKNOWN");
            break;
        case    ST_UNINIT:
        printf("ST_UNINIT");
            break;
        case    ST_INIT:
        printf("ST_INIT");
            break;
        case    ST_CONNECTED:
        printf("ST_CONNECTED");
            break;
        case    ST_MTU_NEGOTIATED:
        printf("ST_MTU_NEGOTIATED");
            break;
        case    ST_AUTHENTICATED:
        printf("ST_AUTHENTICATED");
            break;
        case    ST_ERROR:
        printf("ST_ERROR");
            break;
        case    ST_TERM:
        printf("ST_TERM");
            break;
        default:
        printf("unknown state");
            break;
    }
}

void printEvent(fsmEvName_t ev)
{
    switch (ev) {
        case    EV_UNKNOWN:
        printf("EV_UNKNOWN");
            break;
        case    EV_INIT_SUCCESS:
        printf("EV_INIT_SUCCESS");
            break;
        case    EV_INIT_FAIL:
        printf("EV_INIT_FAIL");
            break;
        case    EV_MASTER_CMD_MSG:
        printf("EV_MASTER_CMD_MSG");
            break;
        case    EV_CONNECT_SUCCESS:
        printf("EV_CONNECT_SUCCESS");
            break;
        case    EV_CONNECT_FAIL:
        printf("EV_CONNECT_FAIL");
            break;
        case    EV_MTU_SUCCESS:
        printf("EV_MTU_SUCCESS");
            break;
        case    EV_MTU_FAIL:
        printf("EV_MTU_FAIL");
            break;
        case    EV_AUTH_SUCCESS:
        printf("EV_AUTH_SUCCESS");
            break;
        case    EV_AUTH_FAIL:
        printf("EV_AUTH_FAIL");
            break;
        case    EV_TX_SUCCESS:
        printf("EV_TX_SUCCESS");
            break;
        case    EV_TX_FAIL:
        printf("EV_TX_FAIL");
            break;
        case    EV_DISCONNECTED:
        printf("EV_DISCONNECTED");
            break;
        case    EV_LAST_ENTRY:
        printf("EV_LAST_ENTRY");
            break;
        default:
        printf("unknown event");
            break;
    }
}

Makefile

CXX = gcc
COMPFLAGS = -c -Wall -g

state_machine: state_machine.o
    $(CXX) -lrt state_machine.o -o state_machine

state_machine.o: state_machine.c
    $(CXX) $(COMPFLAGS) state_machine.c

clean:
    rm state_machine state_machine.o
Brad Grissom
źródło
1

Twoje pytanie jest dość ogólne.
Oto dwa artykuły referencyjne, które mogą być przydatne,

  1. Implementacja wbudowanej maszyny stanu

    W tym artykule opisano proste podejście do implementacji automatu stanów dla systemu osadzonego. Na potrzeby tego artykułu automat stanowy jest zdefiniowany jako algorytm, który może znajdować się w jednym z niewielkiej liczby stanów. Stan to warunek, który powoduje ustaloną relację wejść do wyjść i danych wejściowych do następnych stanów.
    Zręczny czytelnik szybko zauważy, że maszyny stanu opisane w tym artykule są maszynami Mealy. Maszyna Mealy jest maszyną stanu, w której wyjścia są funkcją stanu obecnego i wejścia, w przeciwieństwie do maszyny Moore'a, w której wyjścia są funkcją tylko stanu.

    • Kodowanie automatów stanowych w C i C ++

      W tym artykule zajmuję się podstawami maszyny stanów i kilkoma prostymi wytycznymi programistycznymi do kodowania maszyn stanu w C lub C ++. Mam nadzieję, że te proste techniki mogą stać się bardziej powszechne, abyś (i inni) mogli łatwo zobaczyć strukturę maszyny stanów bezpośrednio z kodu źródłowego.

nik
źródło
1

To jest stary post z wieloma odpowiedziami, ale pomyślałem, że dodam własne podejście do skończonej maszyny stanów w C. Stworzyłem skrypt Pythona, aby wygenerować szkieletowy kod C dla dowolnej liczby stanów. Ten skrypt jest udokumentowany na GituHub na FsmTemplateC

Ten przykład opiera się na innych podejściach, o których czytałem. Nie używa instrukcji goto ani switch, ale zamiast tego ma funkcje przejścia w macierzy wskaźników (tablica przeglądowa). Kod opiera się na dużym wieloliniowym makrze inicjalizacyjnej i funkcjach C99 (wyznaczone inicjalizatory i literały złożone), więc jeśli nie lubisz tych rzeczy, może ci się to nie podobać.

Oto skrypt w Pythonie na przykładzie kołowrotu, który generuje szkielet C-code przy użyciu FsmTemplateC :

# dict parameter for generating FSM
fsm_param = {
    # main FSM struct type string
    'type': 'FsmTurnstile',
    # struct type and name for passing data to state machine functions
    # by pointer (these custom names are optional)
    'fopts': {
        'type': 'FsmTurnstileFopts',
        'name': 'fopts'
    },
    # list of states
    'states': ['locked', 'unlocked'],
    # list of inputs (can be any length > 0)
    'inputs': ['coin', 'push'],
    # map inputs to commands (next desired state) using a transition table
    # index of array corresponds to 'inputs' array
    # for this example, index 0 is 'coin', index 1 is 'push'
    'transitiontable': {
        # current state |  'coin'  |  'push'  |
        'locked':       ['unlocked',        ''],
        'unlocked':     [        '',  'locked']
    }
}

# folder to contain generated code
folder = 'turnstile_example'
# function prefix
prefix = 'fsm_turnstile'

# generate FSM code
code = fsm.Fsm(fsm_param).genccode(folder, prefix)

Wygenerowany nagłówek wyjściowy zawiera typedefs:

/* function options (EDIT) */
typedef struct FsmTurnstileFopts {
    /* define your options struct here */
} FsmTurnstileFopts;

/* transition check */
typedef enum eFsmTurnstileCheck {
    EFSM_TURNSTILE_TR_RETREAT,
    EFSM_TURNSTILE_TR_ADVANCE,
    EFSM_TURNSTILE_TR_CONTINUE,
    EFSM_TURNSTILE_TR_BADINPUT
} eFsmTurnstileCheck;

/* states (enum) */
typedef enum eFsmTurnstileState {
    EFSM_TURNSTILE_ST_LOCKED,
    EFSM_TURNSTILE_ST_UNLOCKED,
    EFSM_TURNSTILE_NUM_STATES
} eFsmTurnstileState;

/* inputs (enum) */
typedef enum eFsmTurnstileInput {
    EFSM_TURNSTILE_IN_COIN,
    EFSM_TURNSTILE_IN_PUSH,
    EFSM_TURNSTILE_NUM_INPUTS,
    EFSM_TURNSTILE_NOINPUT
} eFsmTurnstileInput;

/* finite state machine struct */
typedef struct FsmTurnstile {
    eFsmTurnstileInput input;
    eFsmTurnstileCheck check;
    eFsmTurnstileState cur;
    eFsmTurnstileState cmd;
    eFsmTurnstileState **transition_table;
    void (***state_transitions)(struct FsmTurnstile *, FsmTurnstileFopts *);
    void (*run)(struct FsmTurnstile *, FsmTurnstileFopts *, const eFsmTurnstileInput);
} FsmTurnstile;

/* transition functions */
typedef void (*pFsmTurnstileStateTransitions)(struct FsmTurnstile *, FsmTurnstileFopts *);
  • Wyliczenie eFsmTurnstileChecksłuży do określenia, czy przejście zostało zablokowane EFSM_TURNSTILE_TR_RETREAT, dozwolone postępy EFSM_TURNSTILE_TR_ADVANCE, czy wywołanie funkcji nie było poprzedzone przejściem zEFSM_TURNSTILE_TR_CONTINUE .
  • wyliczanie eFsmTurnstileState to po prostu lista stanów.
  • wyliczanie eFsmTurnstileInput to po prostu lista danych wejściowych.
  • The FsmTurnstile jest sercem automatu stanów z kontrolą przejścia, tabelą wyszukiwania funkcji, stanem bieżącym, stanem polecenia i aliasem do podstawowej funkcji, która uruchamia maszynę.
  • Każdy wskaźnik funkcji (alias) FsmTurnstilepowinien być wywoływany tylko ze struktury i musi mieć swoje pierwsze wejście jako wskaźnik do siebie, aby utrzymać trwały stan, styl obiektowy.

Teraz deklaracje funkcji w nagłówku:

/* fsm declarations */
void fsm_turnstile_locked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_locked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_unlocked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_unlocked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_run (FsmTurnstile *fsm, FsmTurnstileFopts *fopts, const eFsmTurnstileInput input);

Nazwy funkcji mają format {prefix}_{from}_{to}, w którym {from}jest poprzedni (bieżący) stan i {to}następny. Zauważ, że jeśli tabela przejść nie zezwala na pewne przejścia, zamiast wskaźnika funkcji zostanie ustawiony wskaźnik NULL. Wreszcie magia dzieje się z makrem. Tutaj budujemy tabelę przejściową (macierz wyliczeń stanu) i tabelę wyszukiwania funkcji przejścia stanu (macierz wskaźników funkcji):

/* creation macro */
#define FSM_TURNSTILE_CREATE() \
{ \
    .input = EFSM_TURNSTILE_NOINPUT, \
    .check = EFSM_TURNSTILE_TR_CONTINUE, \
    .cur = EFSM_TURNSTILE_ST_LOCKED, \
    .cmd = EFSM_TURNSTILE_ST_LOCKED, \
    .transition_table = (eFsmTurnstileState * [EFSM_TURNSTILE_NUM_STATES]) { \
        (eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \
            EFSM_TURNSTILE_ST_UNLOCKED, \
            EFSM_TURNSTILE_ST_LOCKED \
        }, \
        (eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \
            EFSM_TURNSTILE_ST_UNLOCKED, \
            EFSM_TURNSTILE_ST_LOCKED \
        } \
    }, \
    .state_transitions = (pFsmTurnstileStateTransitions * [EFSM_TURNSTILE_NUM_STATES]) { \
        (pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \
            fsm_turnstile_locked_locked, \
            fsm_turnstile_locked_unlocked \
        }, \
        (pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \
            fsm_turnstile_unlocked_locked, \
            fsm_turnstile_unlocked_unlocked \
        } \
    }, \
    .run = fsm_turnstile_run \
}

Podczas tworzenia FSM makro FSM_EXAMPLE_CREATE() należy użyć .

Teraz w kodzie źródłowym należy zapełnić każdą zadeklarowaną powyżej funkcję zmiany stanu. Strukturę FsmTurnstileFoptsmożna wykorzystać do przekazywania danych do / z automatu stanów. Każde przejście musi fsm->checkbyć równe, aby albo EFSM_EXAMPLE_TR_RETREATzablokować przejście, albo EFSM_EXAMPLE_TR_ADVANCEpozwolić mu przejść do stanu nakazanego. Działający przykład można znaleźć na stronie (FsmTemplateC) [ https://github.com/ChisholmKyle/FsmTemplateC] .

Oto bardzo proste rzeczywiste użycie w kodzie:

/* create fsm */
FsmTurnstile fsm = FSM_TURNSTILE_CREATE();
/* create fopts */
FsmTurnstileFopts fopts = {
    .msg = ""
};
/* initialize input */
eFsmTurnstileInput input = EFSM_TURNSTILE_NOINPUT;

/* main loop */
for (;;) {
    /* wait for timer signal, inputs, interrupts, whatever */
    /* optionally set the input (my_input = EFSM_TURNSTILE_IN_PUSH for example) */
    /* run state machine */
    my_fsm.run(&my_fsm, &my_fopts, my_input);
}

Cały ten biznes nagłówkowy i wszystkie te funkcje, aby mieć prosty i szybki interfejs, są tego warte.

ChisholmKyle
źródło
0

Możesz użyć biblioteki Open Source OpenFST .

OpenFst to biblioteka do konstruowania, łączenia, optymalizacji i wyszukiwania ważonych przetworników skończonych (FST). Ważone przetworniki stanu skończonego są automatami, w których każde przejście ma etykietę wejściową, etykietę wyjściową i wagę. Bardziej znany akceptor stanu skończonego jest reprezentowany jako przetwornik z etykietą wejścia i wyjścia każdego przejścia równą. Akceptory stanów skończonych są używane do reprezentowania zestawów ciągów (w szczególności zestawów regularnych lub wymiernych); Przetworniki stanu skończonego są używane do reprezentowania relacji binarnych między parami łańcuchów (konkretnie racjonalnych transdukcji). Wagi mogą być wykorzystane do przedstawienia kosztu wykonania określonego przejścia.

Vicky Chijwani
źródło
0
void (* StateController)(void); 
void state1(void);
void state2(void);

void main()
{
 StateController=&state1;
 while(1)
 {
  (* StateController)();
 }
}

void state1(void)
{
 //do something in state1
 StateController=&state2;
}

void state2(void)
{
 //do something in state2
 //Keep changing function direction based on state transition
 StateController=&state1;
}
AlphaGoku
źródło
Możesz dodatkowo zoptymalizować go pod kątem bezpieczeństwa, stosując tablicę stałych wskaźników funkcji do funkcji
AlphaGoku
0

Osobiście używam struktur odwołujących się do siebie w połączeniu z tablicami wskaźników. Jakiś czas temu przesłałem tutorial na github, link:

https://github.com/mmelchger/polling_state_machine_c

Uwaga: Zdaję sobie sprawę, że ten wątek jest dość stary, ale mam nadzieję, że uzyskam informacje i przemyślenia na temat konstrukcji maszyny stanów, a także będę w stanie podać przykład możliwego projektu maszyny stanu w C.

mmoment
źródło
0

Możesz rozważyć UML-state-machine-in-c , „lekką” strukturę maszyny stanów w C. Napisałem tę platformę do obsługi zarówno maszyny stanów skończonych, jak i maszyny stanów hierarchicznych . W porównaniu z tabelami stanów lub prostymi przypadkami przełączników, podejście ramowe jest bardziej skalowalne. Może być stosowany do prostych skończonych maszyn stanów do złożonych hierarchicznych maszyn stanów.

Maszyna stanowa jest reprezentowana przez state_machine_tstrukturę. Zawiera tylko dwóch członków „Event” i wskaźnik do „state_t”.

struct state_machine_t
{
   uint32_t Event;          //!< Pending Event for state machine
   const state_t* State;    //!< State of state machine.
};

state_machine_tmusi być pierwszym członkiem struktury maszyny stanów. na przykład

struct user_state_machine
{
  state_machine_t Machine;    // Base state machine. Must be the first member of user derived state machine.

  // User specific state machine members
  uint32_t param1;
  uint32_t param2;
  ...
};

state_t zawiera moduł obsługi stanu, a także opcjonalny moduł obsługi wejścia i wyjścia.

//! finite state structure
struct finite_state{
  state_handler Handler;      //!< State handler to handle event of the state
  state_handler Entry;        //!< Entry action for state
  state_handler Exit;          //!< Exit action for state.
};

Jeśli struktura jest skonfigurowana dla hierarchicznej maszyny stanów, to state_t zawiera wskaźnik do stanu nadrzędnego i podrzędnego.

Framework udostępnia interfejs API dispatch_eventdo wysyłania zdarzenia do automatu stanów iswitch_state wyzwalania przejścia stanu.

Aby uzyskać więcej informacji na temat implementowania hierarchicznej maszyny stanów, zobacz GitHub repozytorium .

przykłady kodu,

https://github.com/kiishor/UML-State-Machine-in-C/blob/master/demo/simple_state_machine/readme.md https://github.com/kiishor/UML-State-Machine-in-C /blob/master/demo/simple_state_machine_enhanced/readme.md

Nandkishor Biradar
źródło
-1

Oto metoda dla automatu stanów, który używa makr, dzięki czemu każda funkcja może mieć swój własny zestaw stanów: https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code -w

Jest zatytułowany „symuluj wielozadaniowość”, ale to nie jedyne zastosowanie.

Ta metoda wykorzystuje wywołania zwrotne do odebrania w każdej funkcji, w której została przerwana. Każda funkcja zawiera listę stanów unikalnych dla każdej funkcji. Centralna „bezczynna pętla” służy do uruchamiania automatów stanów. „Bezczynna pętla” nie ma pojęcia, jak działają maszyny stanów, to poszczególne funkcje „wiedzą, co robić”. Aby napisać kod dla funkcji, wystarczy utworzyć listę stanów i użyć makr do „zawieszenia” i „wznowienia”. Użyłem tych makr w Cisco, kiedy napisałem Bibliotekę Transceiver dla przełącznika Nexus 7000.

eddyq
źródło