我之前设计的状态机(使用C而不是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通常被锁定在单个编译单元中,并且所有变量对该单元是静态的(这就是我在上面加引号的原因-它们更多地在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
。
然后,有限状态机的工作变得相对简单,成为一个循环:
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
作为通配符,允许事件调用函数而不管当前状态。 EV_ANY
也可以类似地工作,允许在特定状态下调用任何事件。
它还可以保证,如果您到达转换数组的末尾,则会出现错误,指出您的FSM构建不正确(使用ST_ANY/EV_ANY
组合)。
我已经在许多通信项目中使用了类似的代码,例如嵌入式系统的通信协议和堆栈的早期实现。其最大优点是简单性和相对容易更改转换数组。
我毫不怀疑现在可能会有更适合的高级抽象,但我觉得它们都会归结于这种相同的结构。
并且,正如ldog
在注释中所述,您可以通过向所有函数传递结构指针(并在事件循环中使用该指针)来完全避免全局变量。这将允许多个状态机并行运行而互不干扰。
只需创建一个包含机器特定数据(至少是状态)的结构类型,并使用该结构类型代替全局变量。
我之所以很少这样做,只是因为我编写的大多数状态机都是单例类型(例如,一次性、在进程启动时读取配置文件等),不需要运行多个实例。但如果需要运行多个实例,则具有价值。
int (*fn)(void*)
,其中void*
是每个状态函数作为参数传入的数据指针。然后状态函数可以使用数据或忽略它们,这样会更加清晰简洁。 - 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
语句基于标签,所以您可以为状态命名,而不必跟踪一堆数字或使用枚举。这还可以让代码更加整洁,因为您不需要所有额外的函数指针、大型开关语句和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
语句,仍然必须小心,因为在这样做时很容易误操作。
您可以考虑使用状态机编译器http://smc.sourceforge.net/
这是一个很棒的开源工具,它接受用简单语言描述的状态机,并将其编译成十多种语言之一,包括C和C++。该工具本身是用Java编写的,并可作为构建的一部分进行包含。
采用这种方法的原因不是手工编码使用GoF State模式或任何其他方法,而是一旦将状态机表达为代码,底层结构往往会在支持它所需产生的样板代码的重量下消失。使用这种方法可以使你的关注点得到很好的分离,同时保持状态机的结构“可见”。自动生成的代码进入您无需操作的模块,因此您可以返回并调整状态机的结构,而不会影响您编写的支持代码。
抱歉,我有些过于热情了,可能有些人会望而却步。但这是一个顶级的实用程序,而且文档也非常好。
请务必查看Miro Samek的工作(博客State Space,网站状态机和工具),他在C/C++用户杂志上发表的文章非常棒。
该网站包含了一个完整的(C/C++)实现,其中包括一个状态机框架(QP Framework)、一个事件处理器(QEP)、一个基本建模工具(QM)和一个跟踪工具(QSpy),这些工具可以绘制状态机、创建代码并进行调试,同时提供开源和商业许可证两种授权方式。
该书详细解释了实现的原因和如何使用它,是理解层次结构和有限状态机基础的重要材料。
该网站还包含多个板级支持包的链接,可用于嵌入式平台上的软件使用。
我做了与paxdiablo描述相似的事情,只是没有使用状态/事件转换数组,而是设置了一个二维函数指针数组,其中事件值作为一维数组的索引,当前状态值作为另一维数组的索引。然后我只需调用state=state_table[event][state](params)
,就会发生正确的事情。当然,代表无效状态/事件组合的单元格得到一个指向指示其无效性的函数的指针。
显然,这仅在状态和事件值都是连续范围并从0或足够接近的位置开始时才适用。
#define STATE_LIST() \STATE_LIST_ENTRY(state1)\STATE_LIST_ENTRY(state2)\...
(每个\
后面都有一个隐含的换行符),当您使用STATE_LIST宏时,您需要重新定义入口宏。例如 - 制作状态名称数组:#define STATE_LIST_ENTRY(s) #s , \n const char *state_names[] = { STATE_LIST() };\n #undef STATE_LIST_ENTRY
。虽然需要一些设置工作,但这非常强大。添加新状态->保证不会漏掉任何一个。 - hlovdalStefan Heinzmann在他的文章中提供了一个非常好的基于模板的C++状态机“框架”。
由于文章中没有完整代码下载链接,我已经将代码粘贴到项目中并进行了测试。下面的内容经过测试,包括一些微小但相当明显的缺失部分。
这里的主要创新是编译器生成非常高效的代码。空的进入/退出动作没有成本。非空进入/退出动作被内联。编译器还验证了状态图的完整性。缺少的动作会生成链接错误。唯一未被捕获的是缺少的Top :: init
。
如果你可以忍受缺少的部分,这是一个非常好的Miro Samek实现的替代方案--尽管它远非完整的UML状态图实现,但正确地实现了UML语义,而Samek的代码则不处理正确顺序的退出/转换/进入动作。
如果这段代码适用于您需要执行的操作,并且您的系统有一个不错的C++编译器,那么它可能比Miro的C/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's GotW #71 -- depends on SFINAE
template<class D, class B>
class IsDerivedFrom {
class Yes { char a[1]; };
class No { char a[10]; };
static Yes Test(B*); // undefined
static No Test(...); // undefined
public:
enum { Res = sizeof(Test(static_cast<D*>(0))) == sizeof(Yes) ? 1 : 0 };
};
template<bool> class Bool {};
// Top State, Composite State and Leaf State
template <typename H>
struct TopState {
typedef H Host;
typedef void Base;
virtual void handler(Host&) const = 0;
virtual unsigned getId() const = 0;
};
template <typename H, unsigned id, typename B>
struct CompState;
template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct CompState : B {
typedef B Base;
typedef CompState<H, id, Base> This;
template <typename X> void handle(H& h, const X& x) const { Base::handle(h, x); }
static void init(H&); // no implementation
static void entry(H&) {}
static void exit(H&) {}
};
template <typename H>
struct CompState<H, 0, TopState<H> > : TopState<H> {
typedef TopState<H> Base;
typedef CompState<H, 0, Base> This;
template <typename X> void handle(H&, const X&) const {}
static void init(H&); // no implementation
static void entry(H&) {}
static void exit(H&) {}
};
template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct LeafState : B {
typedef H Host;
typedef B Base;
typedef LeafState<H, id, Base> This;
template <typename X> void handle(H& h, const X& x) const { Base::handle(h, x); }
virtual void handler(H& h) const { handle(h, *this); }
virtual unsigned getId() const { return id; }
static void init(H& h) { h.next(obj); } // don't specialize this
static void entry(H&) {}
static void exit(H&) {}
static const LeafState obj; // only the leaf states have instances
};
template <typename H, unsigned id, typename B>
const LeafState<H, id, B> LeafState<H, id, B>::obj;
// Transition Object
template <typename C, typename S, typename T>
// Current, Source, Target
struct Tran {
typedef typename C::Host Host;
typedef typename C::Base CurrentBase;
typedef typename S::Base SourceBase;
typedef typename T::Base TargetBase;
enum { // work out when to terminate template recursion
eTB_CB = IsDerivedFrom<TargetBase, CurrentBase>::Res,
eS_CB = IsDerivedFrom<S, CurrentBase>::Res,
eS_C = IsDerivedFrom<S, C>::Res,
eC_S = IsDerivedFrom<C, S>::Res,
exitStop = eTB_CB && eS_C,
entryStop = eS_C || eS_CB && !eC_S
};
// We use overloading to stop recursion.
// The more natural template specialization
// method would require to specialize the inner
// template without specializing the outer one,
// which is forbidden.
static void exitActions(Host&, Bool<true>) {}
static void exitActions(Host&h, Bool<false>) {
C::exit(h);
Tran<CurrentBase, S, T>::exitActions(h, Bool<exitStop>());
}
static void entryActions(Host&, Bool<true>) {}
static void entryActions(Host& h, Bool<false>) {
Tran<CurrentBase, S, T>::entryActions(h, Bool<entryStop>());
C::entry(h);
}
Tran(Host & h) : host_(h) {
exitActions(host_, Bool<false>());
}
~Tran() {
Tran<T, S, T>::entryActions(host_, Bool<false>());
T::init(host_);
}
Host& host_;
};
// Initializer for Compound States
template <typename T>
struct Init {
typedef typename T::Host Host;
Init(Host& h) : host_(h) {}
~Init() {
T::entry(host_);
T::init(host_);
}
Host& host_;
};
#endif // HSM_HPP
测试代码如下。
#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)
最简单的情况
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;
}
}
要点: 状态是私有的,不仅限于编译单元,也适用于事件处理程序。 可以使用任何构造来单独处理特殊情况,而不是在主开关中处理。
更复杂的情况
当开关变得比几个屏幕还大时,将其分成处理每个状态的函数,并使用状态表直接查找函数。状态仍然是私有的,只适用于事件处理程序。状态处理程序函数返回下一个状态。如果需要,在主事件处理程序中仍可以对某些事件进行特殊处理。我喜欢添加伪事件以表示状态进入、退出和状态机启动:
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);
}
}
我不确定语法是否正确,特别是函数指针数组方面。我没有通过编译器运行任何内容。回顾时,我注意到在处理伪事件时忘记明确丢弃下一个状态(在调用state_handler()之前的(void)括号)。即使编译器默默接受省略,我仍然喜欢这样做。它告诉代码读者“是的,我确实打算调用函数而不使用返回值”,并且可能会阻止静态分析工具发出警告。这可能是个人习惯,因为我不记得见过其他人这样做。
要点:增加一点复杂性(检查下一个状态是否与当前状态不同),可以避免在其他地方重复代码,因为状态处理程序函数可以享受进入和离开状态时发生的伪事件。请记住,在处理伪事件时,状态不能更改,因为这些事件后状态处理程序的结果被丢弃。当然,您可以选择修改行为。
状态处理程序应如下所示:
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 人员利用 C++ 模板做的事情,但我发现语法晦涩难懂。
二维表格
我以前使用过状态/事件表,但我必须说,对于最简单的情况,我不认为它们是必需的,即使它超出了一个屏幕的范围,我也更喜欢 switch 语句的清晰度和可读性。对于更复杂的情况,表格很快就会失控,正如其他人所指出的那样。我在这里介绍的习惯用法允许您随时添加大量事件和状态,而无需维护占用内存的表格(即使它可能是程序内存)。
免责声明
特殊需求可能会使这些习惯用法不太有用,但我发现它们非常清晰和可维护。
typedef void* (*state_handler)(input_symbol_t);
void dispatch_fsm()
{
state_handler current = initial_handler;
/* Let's assume returning null indicates end-of-machine */
while (current) {
current = current(get_input);
}
}
这段代码极为未经测试,但编码时很有趣。现在它的版本比我原始答案更加完善,最新版本可以在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;
}