Существует ли типичный шаблон реализации конечного автомата?
https://stackoverflow.com/questions/133214
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Нам нужно реализовать простой конечный автомат в С.
Является ли стандартный оператор переключения лучшим способом?
У нас есть текущее состояние (состояние) и триггер перехода.
switch(state)
{
case STATE_1:
state = DoState1(transition);
break;
case STATE_2:
state = DoState2(transition);
break;
}
...
DoState2(int transition)
{
// Do State Work
...
if(transition == FROM_STATE_2) {
// New state when doing STATE 2 -> STATE 2
}
if(transition == FROM_STATE_1) {
// New State when moving STATE 1 -> STATE 2
}
return new_state;
}
Есть ли способ лучше для простых конечных автоматов
РЕДАКТИРОВАТЬ:Я думаю, что для C++ Boost Диаграмма состояний библиотека может быть подходящим вариантом.Тем не менее, это делает нет помогите с С.Давайте сосредоточимся на варианте использования C.
Решение
Я предпочитаю использовать табличный подход для большинства конечных автоматов:
typedef enum { STATE_INITIAL, STATE_FOO, STATE_BAR, NUM_STATES } state_t;
typedef struct instance_data instance_data_t;
typedef state_t state_func_t( instance_data_t *data );
state_t do_state_initial( instance_data_t *data );
state_t do_state_foo( instance_data_t *data );
state_t do_state_bar( instance_data_t *data );
state_func_t* const state_table[ NUM_STATES ] = {
do_state_initial, do_state_foo, do_state_bar
};
state_t run_state( state_t cur_state, instance_data_t *data ) {
return state_table[ cur_state ]( data );
};
int main( void ) {
state_t cur_state = STATE_INITIAL;
instance_data_t data;
while ( 1 ) {
cur_state = run_state( cur_state, &data );
// do other program logic, run other state machines, etc
}
}
Конечно, это можно расширить для поддержки нескольких конечных автоматов и т. д.Также могут быть реализованы переходные действия:
typedef void transition_func_t( instance_data_t *data );
void do_initial_to_foo( instance_data_t *data );
void do_foo_to_bar( instance_data_t *data );
void do_bar_to_initial( instance_data_t *data );
void do_bar_to_foo( instance_data_t *data );
void do_bar_to_bar( instance_data_t *data );
transition_func_t * const transition_table[ NUM_STATES ][ NUM_STATES ] = {
{ NULL, do_initial_to_foo, NULL },
{ NULL, NULL, do_foo_to_bar },
{ do_bar_to_initial, do_bar_to_foo, do_bar_to_bar }
};
state_t run_state( state_t cur_state, instance_data_t *data ) {
state_t new_state = state_table[ cur_state ]( data );
transition_func_t *transition =
transition_table[ cur_state ][ new_state ];
if ( transition ) {
transition( data );
}
return new_state;
};
Табличный подход легче поддерживать и расширять, а также его проще отображать в диаграммах состояний.
Другие советы
Возможно, вы видели мой ответ на другой вопрос C, где я упомянул FSM!Вот как я это делаю:
FSM {
STATE(x) {
...
NEXTSTATE(y);
}
STATE(y) {
...
if (x == 0)
NEXTSTATE(y);
else
NEXTSTATE(x);
}
}
Со следующими определенными макросами
#define FSM
#define STATE(x) s_##x :
#define NEXTSTATE(x) goto s_##x
Это можно изменить в зависимости от конкретного случая.Например, у вас может быть файл FSMFILE что вы хотите управлять своим FSM, чтобы вы могли включить действие чтения следующего символа в сам макрос:
#define FSM
#define STATE(x) s_##x : FSMCHR = fgetc(FSMFILE); sn_##x :
#define NEXTSTATE(x) goto s_##x
#define NEXTSTATE_NR(x) goto sn_##x
теперь у вас есть два типа переходов:один переходит в состояние и читает новый символ, другой переходит в состояние, не потребляя никаких входных данных.
Вы также можете автоматизировать обработку EOF с помощью чего-то вроде:
#define STATE(x) s_##x : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
goto sx_endfsm;\
sn_##x :
#define ENDFSM sx_endfsm:
Преимущество этого подхода в том, что вы можете напрямую преобразовать диаграмму состояний, которую вы рисуете, в рабочий код и, наоборот, легко нарисовать диаграмму состояний из кода.
В других методах реализации автомата структура переходов скрыта в управляющих структурах (пока, если, переключатель...) и контролируется значением переменных (обычно state переменная), и связать красивую диаграмму со сложным кодом может оказаться сложной задачей.
Я узнал об этой технике из статьи, опубликованной в замечательном журнале «Компьютерный язык», который, к сожалению, больше не издается.
Я также использовал табличный подход.Однако есть накладные расходы.Зачем хранить второй список указателей?Функция в C без () является константным указателем.Итак, вы можете сделать:
struct state;
typedef void (*state_func_t)( struct state* );
typedef struct state
{
state_func_t function;
// other stateful data
} state_t;
void do_state_initial( state_t* );
void do_state_foo( state_t* );
void do_state_bar( state_t* );
void run_state( state_t* i ) {
i->function(i);
};
int main( void ) {
state_t state = { do_state_initial };
while ( 1 ) {
run_state( state );
// do other program logic, run other state machines, etc
}
}
Конечно, в зависимости от вашего фактора страха (т.безопасность против скорости), вы можете проверить наличие действительных указателей.Для конечных автоматов с числом состояний более трех или около того, описанный выше подход должен содержать меньше инструкций, чем эквивалентный подход с переключателями или таблицами.Вы даже можете макро-изменить как:
#define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_))
Кроме того, на примере ОП я чувствую, что существует упрощение, которое следует сделать при обдумывании/проектировании конечного автомата.Я не считаю, что переходное состояние следует использовать для логики.Каждая функция состояния должна иметь возможность выполнять заданную роль без явного знания прошлого состояния(й).По сути, вы проектируете, как перейти из состояния, в котором вы находитесь, в другое состояние.
Наконец, не начинайте проектировать конечный автомат на основе «функциональных» границ, используйте для этого подфункции.Вместо этого разделите состояния в зависимости от того, когда вам придется ждать, пока что-то произойдет, прежде чем вы сможете продолжить.Это поможет свести к минимуму количество запусков конечного автомата, прежде чем вы получите результат.Это может быть важно при написании функций ввода-вывода или обработчиков прерываний.
Также несколько плюсов и минусов классического оператора switch:
Плюсы:
- это на языке, поэтому документировано и понятно
- состояния определяются там, где они называются
- может выполнять несколько состояний за один вызов функции
- код, общий для всех состояний, может выполняться до и после оператора переключения
Минусы:
- может выполнять несколько состояний за один вызов функции
- код, общий для всех состояний, может выполняться до и после оператора переключения
- реализация переключателя может быть медленной
Обратите внимание на два атрибута, которые одновременно являются плюсами и минусами.Я думаю, что этот переход дает возможность слишком большого разделения между государствами, и взаимозависимость между государствами может стать неуправляемой.Однако для небольшого числа состояний он может быть наиболее читабельным и удобным в сопровождении.
Для простого конечного автомата просто используйте оператор переключения и тип перечисления для вашего состояния.Выполняйте переходы внутри оператора switch на основе введенных вами данных.В реальной программе вы, очевидно, измените «if(input)», чтобы проверить точки перехода.Надеюсь это поможет.
typedef enum
{
STATE_1 = 0,
STATE_2,
STATE_3
} my_state_t;
my_state_t state = STATE_1;
void foo(char input)
{
...
switch(state)
{
case STATE_1:
if(input)
state = STATE_2;
break;
case STATE_2:
if(input)
state = STATE_3;
else
state = STATE_1;
break;
case STATE_3:
...
break;
}
...
}
есть также логическая сетка который более удобен в обслуживании по мере того, как конечный автомат становится больше
В Дистиллированный UML Мартина Фаулера, он заявляет (без каламбура) в главе 10 «Диаграммы конечных автоматов» (выделено мной):
Диаграмму состояний можно реализовать тремя основными способами: вложенный переключатель, Образец состояния, и таблицы состояний.
Давайте воспользуемся упрощенным примером состояний дисплея мобильного телефона:
Вложенный переключатель
Фаулер привел пример кода C#, но я адаптировал его к своему примеру.
public void HandleEvent(PhoneEvent anEvent) {
switch (CurrentState) {
case PhoneState.ScreenOff:
switch (anEvent) {
case PhoneEvent.PressButton:
if (powerLow) { // guard condition
DisplayLowPowerMessage(); // action
// CurrentState = PhoneState.ScreenOff;
} else {
CurrentState = PhoneState.ScreenOn;
}
break;
case PhoneEvent.PlugPower:
CurrentState = PhoneState.ScreenCharging;
break;
}
break;
case PhoneState.ScreenOn:
switch (anEvent) {
case PhoneEvent.PressButton:
CurrentState = PhoneState.ScreenOff;
break;
case PhoneEvent.PlugPower:
CurrentState = PhoneState.ScreenCharging;
break;
}
break;
case PhoneState.ScreenCharging:
switch (anEvent) {
case PhoneEvent.UnplugPower:
CurrentState = PhoneState.ScreenOff;
break;
}
break;
}
}
Образец состояния
Вот реализация моего примера с шаблоном состояния GoF:
Таблицы состояний
Вдохновляясь примером Фаулера, вот таблица для моего примера:
Source State Target State Event Guard Action -------------------------------------------------------------------------------------- ScreenOff ScreenOff pressButton powerLow displayLowPowerMessage ScreenOff ScreenOn pressButton !powerLow ScreenOn ScreenOff pressButton ScreenOff ScreenCharging plugPower ScreenOn ScreenCharging plugPower ScreenCharging ScreenOff unplugPower
Сравнение
Вложенный переключатель хранит всю логику в одном месте, но код может быть трудно читать, если состояний и переходов много.Возможно, он более безопасен и его легче проверить, чем другие подходы (без полиморфизма или интерпретации).
Реализация шаблона State потенциально распределяет логику по нескольким отдельным классам, что может затруднить понимание ее в целом.С другой стороны, небольшие классы легко понять отдельно.Проект становится особенно хрупким, если вы меняете поведение, добавляя или удаляя переходы, поскольку они являются методами в иерархии, и в коде может быть много изменений.Если вы придерживаетесь принципа проектирования небольших интерфейсов, вы увидите, что этот шаблон на самом деле не так уж хорош.Однако если конечный автомат стабилен, такие изменения не потребуются.
Подход с таблицами состояний требует написания какого-то интерпретатора для контента (это может быть проще, если у вас есть отражение на используемом языке), что может потребовать большой работы заранее.Как отмечает Фаулер, если ваша таблица отделена от вашего кода, вы можете изменить поведение своего программного обеспечения без перекомпиляции.Однако это имеет некоторые последствия для безопасности;программное обеспечение ведет себя в зависимости от содержимого внешнего файла.
Изменить (не совсем для языка C)
Существует также подход с использованием свободного интерфейса (он же внутренний предметно-ориентированный язык), которому, вероятно, способствуют языки, которые имеют первоклассные функции.А Библиотека без гражданства существует, и в этом блоге показан простой пример с кодом.А Реализация Java (до Java8) обсуждается.мне показали Пример Python на GitHub также.
В простых случаях вы можете использовать свой метод стиля переключения.В прошлом я обнаружил, что хорошо работает и с переходами:
static int current_state; // should always hold current state -- and probably be an enum or something
void state_leave(int new_state) {
// do processing on what it means to enter the new state
// which might be dependent on the current state
}
void state_enter(int new_state) {
// do processing on what is means to leave the current atate
// might be dependent on the new state
current_state = new_state;
}
void state_process() {
// switch statement to handle current state
}
Я ничего не знаю о библиотеке boost, но этот подход предельно прост, не требует каких-либо внешних зависимостей и легко реализуется.
Switch() — это мощный и стандартный способ реализации конечных автоматов в C, но он может снизить удобство сопровождения, если у вас большое количество состояний.Другой распространенный метод — использование указателей на функции для хранения следующего состояния.Этот простой пример реализует триггер установки/сброса:
/* Implement each state as a function with the same prototype */
void state_one(int set, int reset);
void state_two(int set, int reset);
/* Store a pointer to the next state */
void (*next_state)(int set, int reset) = state_one;
/* Users should call next_state(set, reset). This could
also be wrapped by a real function that validated input
and dealt with output rather than calling the function
pointer directly. */
/* State one transitions to state one if set is true */
void state_one(int set, int reset) {
if(set)
next_state = state_two;
}
/* State two transitions to state one if reset is true */
void state_two(int set, int reset) {
if(reset)
next_state = state_one;
}
Я нашел действительно отличную реализацию Moore FSM на языке C в курсе edx.org «Встроенные системы — Формируем мир UTAustinX — UT.6.02x», глава 10, Джонатана Вальвано и Рамеша Йеррабалли....
struct State {
unsigned long Out; // 6-bit pattern to output
unsigned long Time; // delay in 10ms units
unsigned long Next[4]; // next state for inputs 0,1,2,3
};
typedef const struct State STyp;
//this example has 4 states, defining constants/symbols using #define
#define goN 0
#define waitN 1
#define goE 2
#define waitE 3
//this is the full FSM logic coded into one large array of output values, delays,
//and next states (indexed by values of the inputs)
STyp FSM[4]={
{0x21,3000,{goN,waitN,goN,waitN}},
{0x22, 500,{goE,goE,goE,goE}},
{0x0C,3000,{goE,goE,waitE,waitE}},
{0x14, 500,{goN,goN,goN,goN}}};
unsigned long currentState; // index to the current state
//super simple controller follows
int main(void){ volatile unsigned long delay;
//embedded micro-controller configuration omitteed [...]
currentState = goN;
while(1){
LIGHTS = FSM[currentState].Out; // set outputs lines (from FSM table)
SysTick_Wait10ms(FSM[currentState].Time);
currentState = FSM[currentState].Next[INPUT_SENSORS];
}
}
Возможно, вы захотите изучить либеро Программа-генератор FSM.С помощью языка описания состояний и/или редактора диаграмм состояний (Windows) вы можете генерировать код для C, C++, Java и многих других...плюс хорошая документация и диаграммы.Исходный код и двоичные файлы из iMatix
Эта статья хорошо подходит для шаблона состояния (хотя это C++, а не C).
Если сможешь положить руки на книгу»Шаблоны проектирования с головой вперед", объяснение и пример очень ясны.
Один из моих любимых шаблонов — шаблон проектирования состояний.Реагировать или вести себя по-разному на один и тот же набор входных данных.
Одна из проблем с использованием операторов switch/case для конечных автоматов заключается в том, что по мере создания большего количества состояний переключатель/кейс становится сложнее/громоздким для чтения/поддержки, приводит к появлению неорганизованного спагетти-кода, и его становится все труднее изменить, не нарушив что-либо.Я считаю, что использование шаблонов проектирования помогает мне лучше организовывать данные, в этом и состоит весь смысл абстракции.Вместо того, чтобы разрабатывать код штата с учетом того, из какого штата вы пришли, вместо этого структурируйте свой код так, чтобы он записывал состояние, когда вы входите в новое состояние.Таким образом, вы фактически получите запись своего предыдущего состояния.Мне нравится ответ @JoshPetit, и я сделал еще один шаг вперед в своем решении, взятом прямо из книги GoF:
состояниеCtxt.h:
#define STATE (void *)
typedef enum fsmSignal
{
eEnter =0,
eNormal,
eExit
}FsmSignalT;
typedef struct fsm
{
FsmSignalT signal;
// StateT is an enum that you can define any which way you want
StateT currentState;
}FsmT;
extern int STATECTXT_Init(void);
/* optionally allow client context to set the target state */
extern STATECTXT_Set(StateT stateID);
extern void STATECTXT_Handle(void *pvEvent);
состояниеCtxt.c:
#include "stateCtxt.h"
#include "statehandlers.h"
typedef STATE (*pfnStateT)(FsmSignalT signal, void *pvEvent);
static FsmT fsm;
static pfnStateT UsbState ;
int STATECTXT_Init(void)
{
UsbState = State1;
fsm.signal = eEnter;
// use an enum for better maintainability
fsm.currentState = '1';
(*UsbState)( &fsm, pvEvent);
return 0;
}
static void ChangeState( FsmT *pFsm, pfnStateT targetState )
{
// Check to see if the state has changed
if (targetState != NULL)
{
// Call current state's exit event
pFsm->signal = eExit;
STATE dummyState = (*UsbState)( pFsm, pvEvent);
// Update the State Machine structure
UsbState = targetState ;
// Call the new state's enter event
pFsm->signal = eEnter;
dummyState = (*UsbState)( pFsm, pvEvent);
}
}
void STATECTXT_Handle(void *pvEvent)
{
pfnStateT newState;
if (UsbState != NULL)
{
fsm.signal = eNormal;
newState = (*UsbState)( &fsm, pvEvent );
ChangeState( &fsm, newState );
}
}
void STATECTXT_Set(StateT stateID)
{
prevState = UsbState;
switch (stateID)
{
case '1':
ChangeState( State1 );
break;
case '2':
ChangeState( State2);
break;
case '3':
ChangeState( State3);
break;
}
}
statehandlers.h:
/* define state handlers */
extern STATE State1(void);
extern STATE State2(void);
extern STATE State3(void);
statehandlers.c:
#include "stateCtxt.h:"
/* Define behaviour to given set of inputs */
STATE State1(FsmT *fsm, void *pvEvent)
{
STATE nextState;
/* do some state specific behaviours
* here
*/
/* fsm->currentState currently contains the previous state
* just before it gets updated, so you can implement behaviours
* which depend on previous state here
*/
fsm->currentState = '1';
/* Now, specify the next state
* to transition to, or return null if you're still waiting for
* more stuff to process.
*/
switch (fsm->signal)
{
case eEnter:
nextState = State2;
break;
case eNormal:
nextState = null;
break;
case eExit:
nextState = State2;
break;
}
return nextState;
}
STATE State3(FsmT *fsm, void *pvEvent)
{
/* do some state specific behaviours
* here
*/
fsm->currentState = '2';
/* Now, specify the next state
* to transition to
*/
return State1;
}
STATE State2(FsmT *fsm, void *pvEvent)
{
/* do some state specific behaviours
* here
*/
fsm->currentState = '3';
/* Now, specify the next state
* to transition to
*/
return State3;
}
Для большинства государственных машин, особенно.Конечные автоматы, каждое состояние будет знать, каким должно быть его следующее состояние, и критерии перехода в следующее состояние.Для проектов со свободным состоянием это может быть не так, поэтому существует возможность предоставить API для переходных состояний.Если вы хотите большей абстракции, каждый обработчик состояния можно выделить в отдельный файл, который эквивалентен конкретным обработчикам состояний в книге GoF.Если ваш проект прост и содержит всего несколько состояний, то для простоты и stateCtxt.c, и statehandlers.c можно объединить в один файл.
По моему опыту, использование оператора «switch» — это стандартный способ обработки нескольких возможных состояний.Хотя я удивлен, что вы передаете значение перехода для обработки каждого состояния.Я думал, что весь смысл машины состояний заключается в том, что каждое состояние выполняет одно действие.Затем следующее действие/ввод определяет, в какое новое состояние перейти.Поэтому я ожидал, что каждая функция обработки состояния немедленно выполнит все, что зафиксировано для входа в состояние, а затем решит, нужен ли переход в другое состояние.
Есть книга под названием Практические диаграммы состояний на C/C++.Однако это способ слишком тяжеловес для того, что нам нужно.
Для компилятора, поддерживающего __COUNTER__ , вы можете использовать их для простых (но больших) государственных машин.
#define START 0
#define END 1000
int run = 1;
state = START;
while(run)
{
switch (state)
{
case __COUNTER__:
//do something
state++;
break;
case __COUNTER__:
//do something
if (input)
state = END;
else
state++;
break;
.
.
.
case __COUNTER__:
//do something
if (input)
state = START;
else
state++;
break;
case __COUNTER__:
//do something
state++;
break;
case END:
//do something
run = 0;
state = START;
break;
default:
state++;
break;
}
}
Преимущество использования __COUNTER__ вместо жестко закодированных чисел заключается в том, что вы
Может добавлять состояния в середине других состояний, не перенумеровывая каждый раз все.Если компилятор не поддерживает __COUNTER__, в ограниченном виде его можно использовать с осторожностью __LINE__
В C++ рассмотрим Образец состояния.
Ваш вопрос похож на «существует ли типичный шаблон реализации базы данных»?Ответ зависит от того, чего вы хотите достичь?Если вы хотите реализовать более крупный детерминированный конечный автомат, вы можете использовать модель и генератор конечных автоматов.Примеры можно просмотреть на сайте www.StateSoft.org – SM Gallery.Януш Добровольский
В C для простых машин я обычно использую что-то подобное.
Управляемый событиями FSM описывается объектами состояния (FsmState), связанными с действием (FsmAction), и переходами (FsmEdge), определяемыми текущим состоянием и событиями.
Он также обеспечивает хранение и передачу как FSM, так и пользовательских данных, для разделения информации, связанной с FSM и пользователем, и позволяет использовать несколько экземпляров одного и того же FSM (т. е.используя то же описание, но передавая разные пользовательские данные).
События представлены целочисленным типом (FsmEvent).Отрицательные значения зарезервированы реализацией для разрешения особых общих событий (Reset, None, Any, Empty, End).Неотрицательные события определяются пользователем.
Для простоты переходы перечислены в массиве, и попытки сопоставления выполняются в порядке массива, что, по сути, обеспечивает приоритеты перехода.Они имеют дополнительные охранные функции.Следующее состояние может быть указано либо непосредственно в списке переходов, либо с помощью функции перехода, что обеспечивает большую гибкость и обеспечивает динамическое поведение конечного автомата.
В описаниях переходов текущее состояние NULL будет соответствовать любому состоянию, а событие с подстановочным знаком (Любой) будет соответствовать любому событию.В любом случае фактическое значение события, вызвавшего переход, будет передано функциям перехода и защиты.
Для сложных конечных автоматов решение с простым массивом ребер может оказаться слишком неэффективным.В этом случае правильную функцию перехода можно реализовать с использованием массива ребер и записей событий, преобразованных в матрицу перехода или списки смежности состояний.
Действия состояния должны быть реализованы с помощью функции повторного входа, которая различает вход в состояние (Enter), выход из состояния (Leave) и операции в состоянии (State).Таким образом, информация о локальном состоянии может быть инкапсулирована и сохранена с помощью статических функциональных переменных.
Обычно действия входа и выхода из состояния выполняются нормально и не возвращают новых событий (Нет).В противном случае новое событие перехватывается и немедленно возвращается.Это эффективно предотвратит переход, если он произойдет при выходе из текущего состояния.
Функция шага FSM (fsmStep) выполнит один шаг FSM, используя новое событие для запуска перехода или отсутствие события (None) для выполнения действия в текущем состоянии.Функция шага возвращает новое созданное событие, которое можно обработать или повторно передать в FSM;или None, Empty и End в случае отсутствия события, перехода не найден или достижения конечного состояния соответственно.
#ifndef FSM_H_
#define FSM_H_
#include <stdbool.h>
#include <stdint.h>
/** FSM enum type */
typedef enum
{
// Events and return values
fsm_User = 0, ///< User events start with this id
fsm_Reset = -1, ///< Reset event
fsm_None = -2, ///< No event
fsm_Any = -3, ///< Any event, used as a wildcard
fsm_Empty = -4, ///< No transition found for event
fsm_End = -5, ///< Final state event generated when FSM reaches end state, or stop processing when used in transition
// Action types
fsm_Enter = 0, ///< Entry action
fsm_State, ///< In-state action
fsm_Leave ///< Exit action
} fsm_e;
typedef int FsmEvent; ///< Type for events
typedef struct FsmState FsmState; ///< Type for states
typedef struct FsmEdge FsmEdge; ///< Type for edges (transitions)
/** State action functor
@param state Pointer to this state
@param type Action type (Enter/State/Leave)
@param frto Pointer to from(Enter)/to(Leave) state, NULL otherwise
@param data User data
@return Event id in case of a new triggered event, fsm_None otherwise
*/
typedef FsmEvent (*FsmAction)(FsmState *state, fsm_e type, FsmState *frto, void *data);
/** FSM state object */
struct FsmState
{
FsmAction action; ///< Per-state action
void *data; ///< Per-state data
};
/** State jump functor
@param edge Pointer to this edge
@param state Pointer to the actual current state
@param event Event id that triggered the transition
@param data User data
@return Pointer to the next state and NULL for end state
*/
typedef FsmState *(*FsmJump)(FsmEdge *edge, FsmState *state, FsmEvent event, void *data);
/** Guard function
@param edge Pointer to this edge
@param state Pointer to the actual current state
@param event Event id that triggered the transition
@param data User data
@return Guard result
*/
typedef bool (*FsmGuard)(FsmEdge *edge, FsmState *state, FsmEvent event, void *data);
/** FSM edge transition */
struct FsmEdge
{
FsmState *state; ///< Matching current state pointer, or NULL to match any state
FsmEvent event; ///< Matching event id or fsm_Any for wildcard
void *next; ///< Next state pointer (FsmState *) or jump function (FsmJump)
FsmGuard guard; ///< Transition guard function
void *data; ///< Per-edge data
};
typedef struct Fsm Fsm;
struct Fsm
{
FsmState *state; ///< Pointer to the state array
size_t states; ///< Number of states
void **stateData; ///< Pointer to user state data array
FsmEdge *edge; ///< Pointer to the edge transitions array
size_t edges; ///< Number of edges
void **edgeData; ///< Pointer to user edge data array
FsmEvent event; ///< Current/last event
fsm_e type; ///< Current/last action type
FsmState *current; ///< Pointer to the current state
void *data; ///< Per-fsm data
};
#define fsm_INIT { 0 }
static inline FsmEvent
fsmStep(Fsm *f, FsmEvent e)
{
FsmState *cp = f->current; // Store current state
FsmEvent ne = fsm_None; // Next event
// User state data
void *us = (f->stateData && cp) ? f->stateData[cp - f->state] : NULL;
if (!cp && e == fsm_None)
e = fsm_Reset; // Inject reset into uninitialized FSM
f->event = e;
switch (e)
{
case fsm_Reset:
{
// Exit current state
if (cp && cp->action)
{
f->type = fsm_Leave, ne = cp->action(cp, fsm_Leave, f->state, us);
if (ne != fsm_None)
return ne; // Leave action emitted event
}
FsmState *ps = cp;
cp = f->current = f->state; // First state in array is entry state
if (!cp)
return fsm_End; // Null state machine
if (cp->action)
{
us = f->stateData ? f->stateData[0] : NULL;
f->type = fsm_Enter, ne = cp->action(cp, fsm_Enter, ps, us);
}
}
break;
case fsm_None: // No event, run in-state action
if (cp->action)
f->type = fsm_State, ne = cp->action(cp, fsm_State, NULL, us);
break;
default: // Process user transition event
ne = fsm_Empty; // Default return in case no transition is found
// Search transition in listing order
for (size_t i = 0; i < f->edges; ++i)
{
FsmEdge *ep = &f->edge[i];
// Check for state match (null edge state matches any state)
if (ep->state && ep->state != cp)
continue; // Not a match
// Check for stop processing filter
if (ep->event == fsm_End)
break;
ne = fsm_None; // Default return for a transition
// Check for event match
if (ep->event == e || ep->event == fsm_Any)
{
// User edge data
void *ue = f->edgeData ? f->edgeData[i] : NULL;
// Check transition guard
if (!ep->guard || ep->guard(ep, cp, e, ue))
{
// Resolve next state pointer (NULL, new state pointer or jump function)
FsmState *np = (!ep->next) ? NULL
: ((FsmState *)(ep->next) >= f->state && (FsmState *)(ep->next) < (f->state + f->states)) ? (FsmState *)(ep->next)
: ((FsmJump)(ep->next))(ep, cp, e, ue);
if (cp->action)
{
f->type = fsm_Leave, ne = cp->action(cp, fsm_Leave, np, us);
if (ne != fsm_None)
return ne; // Leave action emitted event
}
if (!np) // Final state reached if next state is NULL
ne = fsm_End;
else if (np->action)
{
us = f->stateData ? f->stateData[np - f->state] : NULL;
f->type = fsm_Enter, ne = np->action(np, fsm_Enter, cp, us);
}
cp = np; // New state value
// Transition executed, stop
break;
}
}
}
}
f->current = cp; // Commit current state
return ne; // Last event value
}
static inline FsmEvent
fsmReset(Fsm *f)
{
return fsmStep(f, fsm_Reset);
}
#endif // FSM_H_
Ниже приведен очень простой тест, который поможет понять, как определить и использовать реализацию FSM.Здесь нет определяемых пользователем событий, только данные FSM (строки), одно и то же действие для каждого состояния и общая функция перехода:
#include <stdio.h>
#include "fsm.h"
// State action example
static FsmEvent
state_action(FsmState *s, fsm_e t, FsmState *ft, void *us)
{
FsmEvent e = fsm_None; // State event
const char *q = "?";
switch (t)
{
case fsm_Enter:
q = "enter";
break;
case fsm_Leave:
q = "leave";
break;
default /* fsm_State */:
q = "state";
}
printf("%s %s\n", (const char *)s->data, q);
return e;
}
// States
FsmState fs[] =
{
{ state_action, "S0" },
{ state_action, "S1" },
{ state_action, "S2" },
};
// Transition jump example
static FsmState *
state_jump(FsmEdge *t, FsmState *s, FsmEvent e, void *ue)
{
if (s == &fs[0])
return &fs[1];
if (s == &fs[2])
return NULL; // End state
return NULL; // Trap
}
// Transition guard example
static bool
count_attempt(FsmEdge *t, FsmState *s, FsmEvent e, void *ue)
{
static int c = 0;
++c;
bool b = c == 3;
printf("guard is %s\n", b ? "true" : "false");
return b;
}
// Transitions
FsmEdge fe[] =
{
{ &fs[0], fsm_Any, state_jump }, // Using jump function, no guard
{ &fs[1], fsm_Any, &fs[2], count_attempt }, // Using direct state and guard
{ &fs[2], fsm_Any, state_jump }, // Using jump function, no guard
};
int
main(int argc, char **argv)
{
Fsm f = { fs, 3, NULL, fe, 3, NULL, };
fsmReset(&f);
do
{
fsmStep(&f, fsm_None);
} while (fsmStep(&f, fsm_Any) != fsm_End);
return 0;
}
Boost имеет библиотеку состояний. http://www.boost.org/doc/libs/1_36_0/libs/statechart/doc/index.html
Однако я не могу говорить о его использовании.Сам не пользовался (пока)
