Я занимаюсь созданием небольшого проекта в смешанных C и C++. Я строю один маленький конечный автомат в основе одного из моих рабочих потоков.
Мне было интересно, если бы вы, гуру из SO, поделились своими методами проектирования конечных автоматов.
ПРИМЕЧАНИЕ: я в первую очередь после проверенных и проверенных методов реализации.
ОБНОВЛЕНО: Основываясь на всех замечательных материалах, собранных на SO, я остановился на этой архитектуре:
Государственные машины, которые я разработал ранее (C, а не С++), все сводились к массиву struct и циклу. Структура в основном состоит из состояния и события (для поиска) и функции, которая возвращает новое состояние, например:
typedef struct {
int st;
int ev;
int (*fn)(void);
} tTransition;
Затем вы определяете свои состояния и события с помощью простых определений (тегами ANY являются специальные маркеры, см. ниже):
#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
Затем вы определяете все функции, вызываемые переходами:
static int GotKey (void) { ... };
static int FsmError (void) { ... };
Все эти функции записываются так, чтобы не принимать никаких переменных и возвращать новое состояние для конечного автомата. В этом примере глобальные переменные используются для передачи любой информации в функции состояния, где это необходимо.
Использование глобальных переменных не так плохо, как кажется, поскольку FSM обычно заперт внутри одного блока компиляции, и все переменные являются статическими для этого устройства (именно поэтому я использовал кавычки вокруг "global" выше - они больше разделяемых в рамках FSM, чем по-настоящему глобальный). Как и во всех глобальных переменных, это требует осторожности.
Затем массив переходов определяет все возможные переходы и функции, вызываемые для этих переходов (включая последнюю последнюю):
tTransition trans[] = {
{ ST_INIT, EV_KEYPRESS, &GotKey},
: :
{ ST_ANY, EV_ANY, &FsmError}
};
#define TRANS_COUNT (sizeof(trans)/sizeof(*trans))
Что это значит: если вы находитесь в состоянии ST_INIT и получаете событие EV_KEYPRESS, сделайте вызов GotKey.
Затем работа FSM становится относительно простой:
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;
}
}
}
}
Как упоминалось выше, обратите внимание на использование ST_ANY в качестве wild-cards, позволяя событию вызывать функцию независимо от текущего состояния. EV_ANY также работает аналогично, позволяя любому событию в конкретном состоянии вызывать функцию.
Это также может гарантировать, что, если вы достигнете конца массива переходов, вы получите сообщение об ошибке, когда ваш FSM не был построен правильно (используя комбинацию ST_ANY/EV_ANY.
Я использовал код, похожий на этот код, на большое количество коммуникационных проектов, таких как ранняя реализация стеков сообщений и протоколов для встроенных систем. Большим преимуществом была его простота и относительная легкость в изменении массива переходов.
Я не сомневаюсь, что будут абстракции более высокого уровня, которые могут быть более подходящими в наши дни, но я подозреваю, что они все сводятся к такой же структуре.
И, как говорится в ldog в комментарии, вы можете вообще избегать глобальных переменных, передав указатель структуры ко всем функциям (и используя это в цикле событий). Это позволит нескольким конечным машинам работать бок о бок без помех.
Просто создайте тип структуры, который содержит данные, специфичные для машины (состояние минимально), и используйте это вместо глобальных.
Причина, по которой я редко делал это, - это просто потому, что большинство состояний, которые я написал, были однотипными (одноразовый, в процессе запуска, чтение файла конфигурации, например), не нужно запускать больше чем один экземпляр. Но это имеет значение, если вам нужно запустить более одного.
Другие ответы хороши, но очень "легкая" реализация, которую я использовал, когда машина состояния очень проста выглядит:
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 ... */
}
}
Я бы использовал это, когда конечный автомат достаточно прост, что подход таблицы указателей функций и состояний переполнен. Это часто полезно для поэтапного или поэтапного разбора.
Извините за нарушение всех правил в области компьютерных наук, но конечный автомат - одно из немногих (я могу считать только два) мест, где goto не только более эффективен, но также делает ваш код чище и легче для чтения. Поскольку goto основаны на метках, вы можете называть свои состояния вместо того, чтобы отслеживать беспорядочные числа или использовать enum. Это также делает код намного чище, так как вам не нужны все лишние указатели функций или огромные операторы switch и while. Я упоминал, что это более эффективно?
Вот как может выглядеть конечный автомат:
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;
}
}
Вы получите общую идею. Дело в том, что вы можете реализовать конечный автомат эффективным способом, который относительно легко читается и кричит читателю, что он смотрит на конечный автомат. Обратите внимание, что если вы используете goto, вы все равно должны быть осторожны, так как при этом очень легко выстрелить себе в ногу.
Вы можете рассмотреть компилятор State Machine http://smc.sourceforge.net/
Эта великолепная утилита с открытым исходным кодом принимает описание конечного автомата на простом языке и компилирует его на любой из десятков языков, включая C и С++. Сама утилита написана на Java и может быть включена как часть сборки.
Причина этого, а не ручное кодирование с использованием шаблона состояния GoF или любого другого подхода, заключается в том, что, как только ваш конечный автомат выражается в виде кода, базовая структура имеет тенденцию исчезать под весом шаблона, который должен быть сгенерирован для поддержите его. Использование этого подхода дает вам отличное разделение проблем, и вы сохраняете структуру своего государственного аппарата "видимой". Автоматически сгенерированный код переходит в модули, которые вам не нужно трогать, так что вы можете вернуться и сфокусироваться на структуре государственного аппарата, не оказывая влияния на поддерживаемый код, который вы написали.
Извините, я испытываю чрезмерную энтузиазм и, несомненно, увольняю всех. Но это первоклассная утилита и хорошо документирована.
Обязательно проверьте работу Miro Samek (блог State Space, веб-сайт Государственные машины и инструменты), чьи статьи в журнале пользователей C/С++ были замечательными.
Веб-сайт содержит полную (C/С++) реализацию как с открытым исходным кодом, так и с коммерческой лицензией системы государственных машин (QP Framework), обработчика событий (QEP), базовый инструмент моделирования (QM) и инструмент трассировки (QSpy), который позволяет рисовать конечные машины, создавать код и отлаживать их.
Книга содержит обширное объяснение того, что/почему реализации и как ее использовать, а также является отличным материалом для понимания основ иерархических и конечных автоматов.
На веб-сайте также содержатся ссылки на несколько пакетов поддержки плат для использования программного обеспечения со встроенными платформами.
Я сделал что-то похожее на то, что описывает paxdiablo, только вместо массива переходов состояний/событий я настроил двумерный массив указателей на функции, значение события как индекс одной оси и текущего как другое. Тогда я просто звоню state = state_table[event][state](params), и правильная вещь случается. Ячейки, представляющие недействительные комбинации состояний/событий, получают указатель на функцию, которая это говорит, конечно.
Очевидно, что это работает только в том случае, если значения состояния и события являются смежными диапазонами и начинаются с 0 или достаточно близко.
Очень симпатичная основанная на шаблонах "фреймворк" состояния языка С++ дается Стефаном Хайнцманом в статье .
Поскольку в статье нет ссылки на полную загрузку кода, я позволил вставить код в проект и проверить его. Материал ниже тестируется и включает в себя несколько незначительных, но довольно очевидных недостающих фрагментов.
Основное нововведение заключается в том, что компилятор генерирует очень эффективный код. Пустые действия входа/выхода не требуют затрат. Непустые действия входа/выхода включены. Компилятор также проверяет полноту государственной диаграммы. Отсутствующие действия генерируют ошибки связывания. Единственное, что не удалось поймать, это отсутствие Top::init.
Это очень хорошая альтернатива реализации Miro Samek, если вы можете жить без того, что отсутствует - это далеко не полная реализация UML Statechart, хотя она правильно реализует семантику UML, тогда как код Samek по дизайну не обрабатывает выхода/перехода/ввода в правильном порядке.
Если этот код работает для того, что вам нужно сделать, и у вас есть достойный компилятор С++ для вашей системы, он, вероятно, будет работать лучше, чем реализация Miro C/С++. Компилятор генерирует для вас сжатую, O (1) переходную машину. Если проверка сборки сборок подтверждает, что оптимизация работает по желанию, вы приближаетесь к теоретической производительности. Лучшая часть: это относительно крошечный, понятный код.
#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 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
Далее следует тестовый код.
#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)
Метод, который мне нравится для состояний машин (по крайней мере, для управления программой), заключается в использовании указателей функций. Каждое состояние представлено другой функцией. Функция принимает входной символ и возвращает указатель на функцию для следующего состояния. Центральные диспетчерские мониторы отправляют следующий вход, подают его в текущее состояние и обрабатывают результат.
Впечатывание на нем становится немного странным, так как C не имеет способа указывать типы возвращающих себя указателей функций, поэтому функции состояния возвращают void*. Но вы можете сделать что-то вроде этого:
typedef void* (*state_handler)(input_symbol_t);
void dispatch_fsm()
{
state_handler current = initial_handler;
/* Let assume returning null indicates end-of-machine */
while (current) {
current = current(get_input);
}
}
Затем ваши индивидуальные функции состояния могут включать свой вход для обработки и возвращать соответствующее значение.
Простейший случай
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;
}
}
Очки: Состояние является закрытым не только для компиляции, но и для event_handler. Специальные случаи могут обрабатываться отдельно от основного коммутатора, используя любую конструкцию, которая считается необходимой.
Более сложный случай
Когда коммутатор становится больше, чем на пару экранов, разделите его на функции, которые обрабатывают каждое состояние, используя таблицу состояний для непосредственного поиска функции. Состояние по-прежнему является приватным для обработчика событий. Функции обработчика состояния возвращают следующее состояние. При необходимости некоторые события могут по-прежнему получать специальное лечение в главном обработчике событий. Мне нравится бросать псевдо-события для входа и выхода из состояния и, возможно, запуска автомата:
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);
}
}
Я не уверен, что я прибил синтаксис, особенно в отношении массива указателей функций. Я не запускал ни одно из этого через компилятор. После обзора я заметил, что я забыл явно отказаться от следующего состояния при обработке псевдо-событий (скобки (void) перед вызовом state_handler()). Это то, что мне нравится делать, даже если компиляторы молча принимают молчание. Он сообщает читателям кода, что "да, я действительно имел в виду вызывать функцию без использования возвращаемого значения", и она может остановить инструменты статического анализа от предупреждения об этом. Это может быть особенным, потому что я не помню, чтобы кто-то другой это делал.
Баллы: добавление крошечной части сложности (проверка, если следующее состояние отличается от текущего), может избежать дублирования кода в другом месте, поскольку функции обработчика состояния могут пользоваться псевдо-событиями, которые возникают, когда состояние введено и осталось. Помните, что состояние не может измениться при обработке псевдо-событий, потому что результат обработчика состояния отбрасывается после этих событий. Разумеется, вы можете изменить поведение.
Обработчик состояния будет выглядеть так:
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;
}
Более сложная
Когда блок компиляции становится слишком большим (независимо от того, что вы чувствуете, я должен сказать около 1000 строк), поместите каждый обработчик состояния в отдельный файл. Когда каждый обработчик состояния становится длиннее, чем несколько экранов, разделяйте каждое событие в отдельной функции, подобно тому, как разделялся переключатель состояния. Вы можете сделать это несколькими способами, отдельно от состояния или с помощью общей таблицы или объединения различных схем. Некоторые из них были охвачены другими. Сортируйте свои таблицы и используйте бинарный поиск, если требуется скорость.
Общее программирование
Мне бы хотелось, чтобы препроцессор справлялся с такими проблемами, как сортировка таблиц или даже генерация состояний машин из описаний, позволяющая "писать программы о программах". Я считаю, что это то, что люди Boost используют шаблоны С++, но я нахожу синтаксис загадочным.
Двумерные таблицы
Я использовал таблицы состояния/событий в прошлом, но я должен сказать, что для простейших случаев я не считаю их необходимыми, и я предпочитаю ясность и удобочитаемость оператора switch, даже если он распространяется за один полный экран. Для более сложных случаев таблицы быстро выходят из-под контроля, как отмечали другие. Идиомы, которые я здесь представляю, позволяют добавлять множество событий и состояний, когда вам это нравится, без необходимости поддерживать таблицу потребления памяти (даже если это может быть программная память).
Отказ
Особые потребности могут сделать эти идиомы менее полезными, но я нашел их очень четкими и поддерживаемыми.
Чрезвычайно непроверенный, но забавный код, теперь в более изысканной версии, чем мой оригинальный ответ; обновленные версии можно найти на 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
example.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;
}
Мне действительно понравился paxdisable ответ и решил реализовать все недостающие функции для моего приложения, такие как защитные переменные и данные, зависящие от конечного автомата.
Я загрузил свою реализацию на этот сайт, чтобы поделиться с сообществом. Он был протестирован с использованием IAR Embedded Workbench для ARM.
Другим интересным инструментом с открытым исходным кодом является Якинду. Инструменты Statechart на statecharts.org. Он использует диаграммы состояния Harel и, таким образом, обеспечивает иерархические и параллельные состояния и генерирует код C и С++ (а также Java). Он не использует библиотеки, но следует подходом "простого кода". Код в основном применяет структуры коммутационных шкафов. Генераторы кода также могут быть настроены. Кроме того, инструмент предоставляет множество других функций.
Придя к этому поздно (как обычно), но просматривая ответы на сегодняшний день, я думаю, что что-то важное отсутствует,
Я нашел в своих проектах, что очень полезно не иметь функции для каждой допустимой комбинации состояний/событий. Мне нравится идея эффективно иметь 2D-таблицу состояний/событий. Но мне нравится, что элементы таблицы являются более чем простым указателем на функцию. Вместо этого я пытаюсь организовать свой проект, поэтому в нем он содержит кучу простых атомных элементов или действий. Таким образом, я могу перечислить эти простые атомные элементы на каждом пересечении таблицы состояния/события. Идея состоит в том, что вам не нужно определять массу N квадратов (обычно очень простых) функций. Почему у кого-то такое склонное к ошибкам, трудоемкое, трудное для записи, трудно читаемое, вы называете его?
Я также включаю необязательное новое состояние и необязательный указатель функции для каждой ячейки в таблице. Указатель функции существует для тех исключительных случаев, когда вы не хотите просто запускать список атомных действий.
Вы знаете, что делаете это правильно, когда можете выразить много разных функций, просто отредактировав таблицу, без нового кода для записи.
Alrght, я думаю, что я немного отличаюсь от всех остальных. Немного больше разделения кода и данных, чем я вижу в других ответах. Я действительно прочитал теорию, чтобы написать это, в котором реализуется полный регулярный язык (без регулярных выражений, к сожалению). Ульман, Минский, Хомский. Не могу сказать, что я все это понял, но я сделал из старых мастеров максимально возможное: через их слова.
Я использую указатель функции на предикат, который определяет переход в состояние "да" или состояние "нет". Это облегчает создание акцептора конечного состояния для обычного языка, который вы программируете более похожим на ассемблере образом. Пожалуйста, не путайте мои глупые имена. 'czek' == 'check'. 'grok' == [искать его в Hacker Dictionary].
Итак, для каждой итерации czek вызывает предикатную функцию с текущим символом в качестве аргумента. Если предикат возвращает true, символ потребляется (указатель продвинут), и мы следуем "y", чтобы выбрать следующее состояние. Если предикат возвращает false, символ НЕ потребляется, и мы следуем "n". Поэтому каждая инструкция - это двусторонняя ветка! Должно быть, я читал "Историю Мела" в то время.
Этот код поступает прямо из моего интерпретатора постскриптума и превратился в его текущую форму с большим руководством от стипендиатов на comp.lang.c. Поскольку postcript в принципе не имеет синтаксиса (требуется только сбалансированные скобки), такой же как и синтаксический анализатор, является обычным языком Accepter.
/* 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 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 поставляется с двумя различными реализациями графиков состояний:
Как всегда, boost запустит вас в шаблонный ад.
Первая библиотека предназначена для более критически важных состояний. Вторая библиотека дает вам прямой путь перехода из UML Statechart в код.
Здесь SO вопрос, требующий сравнения между ними, где оба автора отвечают.
Эта серия статей Ars OpenForum о несколько сложной бит логики управления включает в себя очень простую в использовании реализацию в качестве конечного автомата в C.
Пила это где-то
#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);
}
}
Учитывая, что вы подразумеваете, что можете использовать С++ и, следовательно, OO-код, я бы предложил оценить шаблон GoF'state (GoF = Gang of Four, ребята, написавшие книгу шаблонов дизайна, которая привнесла шаблоны дизайна в центр внимания).
Это не особенно сложно и широко используется и обсуждается, поэтому легко увидеть примеры и объяснения на линии.
Это также вполне вероятно будет узнано любым другим, поддерживающим ваш код позднее.
Если эффективность - это беспокойство, стоило бы фактически сравнить бенчмаркинг, чтобы убедиться в том, что подход, отличный от OO, более эффективен, так как многие факторы влияют на производительность, и это не всегда просто плохой код, хороший функциональный код. Точно так же, если использование памяти является для вас ограничением, вам стоит сделать несколько тестов или вычислений, чтобы увидеть, действительно ли это будет проблемой для вашего конкретного приложения, если вы используете шаблон состояния.
Ниже приведены некоторые ссылки на шаблон состояния Gof, как предлагает Крейг:
Ваш вопрос довольно общий,
Вот два справочных статьи, которые могут быть полезны,
Внедрение встроенного государственного устройства
В этой статье описывается простой подход к реализации конечного автомата для встроенной системы. Для целей этой статьи конечный автомат определяется как алгоритм, который может находиться в одном из небольшого числа состояний. Состояние - это условие, которое вызывает предписанную взаимосвязь входов и выходов и входов в следующие состояния. Разумный читатель быстро заметит, что государственные машины, описанные в этой статье, являются машинами Мили. Машина "Мили" - это машина состояний, где выходы являются функцией как текущего состояния, так и входа, в отличие от машины Мура, в которой выходы являются функцией только состояния.
Моя озабоченность в этой статье связана с основными состояниями машины и некоторыми простыми правилами программирования для кодирования состояний машин на C или С++. Я надеюсь, что эти простые методы могут стать более распространенными, так что вы (и другие) можете легко увидеть структуру состояния-машины прямо из исходного кода.
Я успешно использовал State Machine Compiler в проектах Java и Python.
Это старое сообщение с большим количеством ответов, но я подумал, что добавлю свой подход к машине конечного состояния в C. Я создал Python script для создания скелетного кода C для любого количества состояний. Этот script документирован на GituHub по адресу FsmTemplateC
Этот пример основан на других подходах, о которых я читал. Он не использует операторы goto или switch, а вместо этого имеет функции перехода в матрицу указателя (справочная таблица). Код опирается на большой многострочный макрос инициализатора и функции C99 (назначенные инициализаторы и сложные литералы), поэтому, если вам не нравятся эти вещи, вам может не понравиться этот подход.
Вот пример Python script пример турникета, который генерирует скелет C-кода, используя 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)
Сгенерированный выходной заголовок содержит 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 *);
eFsmTurnstileCheck используется для определения того, был ли заблокирован переход с EFSM_TURNSTILE_TR_RETREAT, разрешен для выполнения с помощью EFSM_TURNSTILE_TR_ADVANCE или вызову функции не предшествовал переход с EFSM_TURNSTILE_TR_CONTINUE.eFsmTurnstileState - это просто список состояний.eFsmTurnstileInput - это просто список входов.FsmTurnstile является основой конечного автомата с проверкой перехода, таблицей поиска функций, текущим состоянием, командным состоянием и псевдонимом основной функции, которая запускает машину.FsmTurnstile должен вызываться только из структуры и должен иметь свой первый вход как указатель на себя, чтобы поддерживать постоянное состояние, объектно-ориентированный стиль.Теперь для объявлений функций в заголовке:
/* 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);
Имена функций находятся в формате {prefix}_{from}_{to}, где {from} - это предыдущее (текущее) состояние, а {to} - следующее состояние. Обратите внимание, что если таблица переходов не допускает определенных переходов, будет установлен указатель NULL вместо указателя функции. Наконец, магия происходит с макросом. Здесь мы строим таблицу переходов (матрицу перечислений состояний) и таблицу переходов состояний (таблица матриц указателей функций):
/* 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 \
}
При создании FSM необходимо использовать макрос FSM_EXAMPLE_CREATE().
Теперь в исходном коде должна быть заполнена каждая заявленная выше функция перехода состояния. Структуру FsmTurnstileFopts можно использовать для передачи данных в/из конечного автомата. Каждый переход должен установить fsm->check равным либо EFSM_EXAMPLE_TR_RETREAT, чтобы заблокировать его от перехода, или EFSM_EXAMPLE_TR_ADVANCE, чтобы он мог перейти в командное состояние.
Рабочий пример можно найти на (FsmTemplateC) [https://github.com/ChisholmKyle/FsmTemplateC].
Вот очень простое фактическое использование в вашем коде:
/* 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);
}
Все, что заголовок бизнес и все эти функции просто иметь простой и быстрый интерфейс стоит в моем сознании.
Вы можете использовать библиотеку с открытым исходным кодом OpenFST.
OpenFst - это библиотека для построения, комбинирования, оптимизации и поиска взвешенных конечных преобразователей (FST). Взвешенные конечные преобразователи - это автоматы, в которых каждый переход имеет входную метку, выходную метку и вес. Более знакомый конечный акцептор представлен как преобразователь, каждый из которых соответствует входному и выходному меткам перехода. Акцепторы конечного состояния используются для представления наборов строк (в частности, регулярных или рациональных множеств); преобразователи конечного состояния используются для представления двоичных отношений между парами строк (в частности, рациональных трансдукций). Веса могут использоваться для представления стоимости принятия конкретного перехода.
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;
}
Я лично использую самореляционные структуры в сочетании с массивами указателей. Я загрузил учебник по github некоторое время назад, ссылка:
https://github.com/mmelchger/polling_state_machine_c
Примечание. Я понимаю, что эта ветка довольно старая, но я надеюсь получить представление и мысли о дизайне государственной машины, а также предоставить пример возможного проектирования состояний в C.
Вот пример конечного автомата для Linux, который использует очереди сообщений в качестве событий. События помещаются в очередь и обрабатываются по порядку. Состояние меняется в зависимости от того, что происходит для каждого события.
Это пример подключения к данным с такими состояниями, как:
Одна небольшая дополнительная функция, которую я добавил, была timestamp для каждого сообщения/события. Обработчик событий будет игнорировать слишком старые события (срок их действия истек). Это может случиться много в реальном мире, где вы можете неожиданно застрять в состоянии.
Этот пример работает на Linux, используйте Makefile ниже, чтобы скомпилировать его и поэкспериментировать с ним.
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, ¤tlyLessThanMaxConnectTries, 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, ¤tlyLessThanMaxMTUtries, 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, ¤tyLessThanMaxAuthTries, 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, ¤tlyLessThanMaxTXtries, 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