В C для простых машин я обычно использую нечто подобное:
Управляемый событиями FSM описывается объектами состояния (FsmState), связанными с действием (FsmAction), и переходами (FsmEdge), определяемыми текущим состоянием и событиями.
Он также обеспечивает хранение и передачу как FSM, так и пользовательских данных, чтобы отделить информацию, связанную с FSM и от пользователя, и разрешить множественные экземпляры одного и того же FSM (т.е. используя одно и то же описание, но передавая разные пользовательские данные).
События представлены целочисленным типом (FsmEvent). Отрицательные значения зарезервированы реализацией для разрешения специальных общих событий (Сброс, Нет, Любой, Пустой, Конец). Неотрицательные события определяются пользователем.
Для простоты переходы перечислены в массиве, и попытка сопоставления предпринята в порядке массива, по существу обеспечивая приоритеты перехода. У них есть дополнительные функции охраны. Следующее состояние может быть указано либо непосредственно в списке переходов, либо с помощью функции перехода, что обеспечивает большую гибкость, позволяющую динамическое поведение FSM.
В описаниях переходов текущее состояние NULL будет соответствовать любому состоянию, а подстановочное событие (Any) будет соответствовать любому событию. В любом случае, фактическое значение события, которое инициировало переход, будет передано в функции перехода и защиты.
Для сложных FSM решение с простым реберным массивом может стать слишком неэффективным. В этом случае правильная функция перехода может быть реализована с использованием массива ребер и записей событий, преобразованных в матрицу переходов или списки смежности состояний.
Действия состояния предназначены для реализации с помощью функции повторного входа, которая различает операции входа в состояние (Ввод), выхода из состояния (Выйти) и операции в состоянии (Состояние). Таким образом, информация о локальном состоянии может быть инкапсулирована и сохранена со статическими переменными функции.
Обычно действия по входу и выходу из состояния выполняются без замечаний и не возвращают никаких новых событий (Нет). Если нет, новое событие перехватывается и сразу возвращается. Это эффективно предотвратит переход, если он произойдет при выходе из текущего состояния.
Шаговая функция FSM (fsmStep) будет выполнять один шаг FSM, используя новое событие для запуска перехода или отсутствие события (Нет) для выполнения действия в текущем состоянии в состоянии. Функция шага возвращает новое испущенное событие, которое может быть обработано или повторно передано в FSM; или Нет, Пусто и Конец в случае отсутствия события, переход не найден или конечное состояние достигнуто, соответственно.
#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;
}