Maszyny stanów na tablicach

Zastosowania tablic w C - wszystkie wpisy

• Tablice wskaźników na funkcje
• Maszyny stanów na tablicach
• Tablice przyspieszające wyszukiwanie elementów
• Jak korzystać z Lookup Table?

Po lookup table i wyszukiwaniu elementów pora na kolejne zastosowanie tablic – maszyny stanu. Podobnie jak w poprzednich przypadkach, logikę warunkową zastąpimy wyczytywaniem odpowiednich indeksów z tablicy. W przypadku maszyn stanu możemy dzięki temu nie tylko zwiększyć wydajność, ale również drastycznie poprawić utrzymywalność kodu.

Maszyny stanu na switch-case

Narzucającą się implementacją maszyn stanu w C jest wykorzystanie konstrukcji switch-case. Mamy jakąś definicję możliwych stanów:

typedef enum
{
    STATE_A,
    STATE_B,
    ...
    STATE_CNT,
} state_t;

A następnie każdy z tych stanów obsługujemy w switchu:

switch (state)
{
case STATE_A:
    ....
    break;
case STATE_B:
    ....
    break;
...
default:
    break;
}

W najprostszych zastosowaniach takie podejście się sprawdza, ale w bardziej skomplikowanych przypadkach dodajemy sobie dużo roboty – wszędzie musimy powielać tego switcha. Co więcej – zwykle stany zmieniają się na skutek jakiś eventów, których obsługa wymaga od nas kolejnych switchów i ifów. Bardziej zaawansowane implementacje mają też np. warunki wejścia do stanu. Próbując rozszerzać nasz prosty przykład ze switchem szybko dojdziemy do wniosku, że nie tędy droga.

Tablica przejść stanów

Jak wspomniałem wcześniej – przejścia między stanami są powodowane przez wystąpienie pewnych eventów. Możemy je również zapisać za pomocą enuma:

typedef enum
{
    EVENT_1,
    EVENT_2,
    EVENT_3,
    ...
    EVENT_CNT,
} event_t;

Dla danego aktualnego stanu wystąpienie eventa powinno spowodować przejście do stanu docelowego. Wszystkie możliwe przejścia stanów możemy zgromadzić w tablicy dwuwymiarowej, gdzie jednym indeksem jest stan początkowy, a drugim event:

state_t transition_table[STATE_CNT][EVENT_CNT] =
{
    /* STATE_A */
    {
        STATE_A,
        STATE_B,
	STATE_C,
        ....
    },
    /* STATE_B */
    {
        STATE_A,
        STATE_B,
        STATE_C,
        ....
    },
    ....
}

Mając taką tablicę możemy prosto napisać funkcję zwracającą nowy stan:

state_t get_new_state(state_t current_state, event_t event)
{
	//todo: input boundary checks
	return transition_table[current_state][event];
}

Dzięki zastosowaniu tabel do przejść stanów jesteśmy w stanie znacznie ograniczyć ilość logiki warunkowej. Edytowanie takiej tablicy moim zdaniem jest również bardziej czytelne. W prawdziwych zastosowaniach większość przejść dla poszczególnych eventów nie jest możliwa i trafiamy do docelowego stanu o nazwie np. STATE_ERROR. Poza tym taka tabela jest dużo łatwiejsza do wygenerowania z diagramu stanów UML niż instrukcje switch-case.

Dodawanie akcji

Jak wspominałem wcześniej, maszyny stanu mogą być również rozszerzone o pewne akcje wykonywane np. przy wejściu do/wyjściu z danego stanu. Innym rodzajem akcji może być dodatkowy warunek w momencie przyjścia eventu. Zarządzanie takimi akcjami dla każdego możliwego stanu czy eventa byłoby po prostu udręką. Możemy sobie tu pomóc wskaźnikami na funkcje. Na przykład jeżeli dla każdego stanu chcemy mieć akcje na wejściu, wyjściu i przy każdej iteracji, możemy stworzyć taką strukturę:

typedef void (*fun_entry_t)(void);
typedef void (*fun_exit_t)(void);
typedef void (*fun_tick_t)(void);

struct state_params_t
{
    fun_entry_t on_entry;
    fun_exit_t on_exit;
    fun_tick_t on_tick;
}

Następnie tworzymy tablicę z wartościami dla każdego stanu:

struct state_params_t state_params[STATE_CNT] =
{
    /* STATE_A */
    {
        state_a_entry,
        state_a_exit,
        state_a_tick,
    },
    ...
};

Dzięki temu możemy obsługiwać wszystkie stany za pomocą generycznego kodu posługującego się ID stanu do wywoływania wszystkich potrzebnych funkcji. Podobny zabieg możemy zrobić z eventami aby dodać na przykład warunki, które muszą być spełnione, żeby zmienić stan.

Gotowe rozwiązania

Więcej o maszynach stanu w C, ich rodzajach, implementacji i zastosowaniach w embedded dowiecie się od Miro Samka z jego strony Quantum Leaps.

Jeżeli natomiast korzystacie z C++, polecam korzystać z gotowych bibliotek napisanych z pomocą template metaprogramming np. Boost Meta State Machine.

Podsumowanie

W tym wpisie pokazałem jak tablice mogą zastąpić logikę warunkową przy implementacji maszyn stanu. Jeżeli wykorzystamy dodatkowo struktury z wskaźnikami na funkcje możemy uzyskać ogromną elastyczność. Docenimy to szczególnie podczas wprowadzania zmian. Oczywiście przedstawione przykłady kodu tylko obrazują jedynie ideę, która powinna zostać dostosowana do konkretnego projektu. Można ją również rozszerzać o dodatkowe elementy. Jednak nie ulega wątpliwości, że tablice w C są bardzo pomocne w implementacji wydajnych i czytelnych maszyn stanu.

Zastosowania tablic w C - Nawigacja