C 状态机设计

C state-machine design

提问by jldupont

I am crafting a small project in mixed C and C++. I am building one small-ish state-machine at the heart of one of my worker thread.

我正在用混合 C 和 C++ 制作一个小项目。我正在我的一个工作线程的核心构建一个小型状态机。

I was wondering if you gurus on SO would share your state-machine design techniques.

我想知道您是否会分享您的状态机设计技术。

NOTE:I am primarily after tried & tested implementation techniques.

注意：我主要是经过尝试和测试的实现技术。

UPDATED:Based on all the great input gathered on SO, I've settled on this architecture:

更新：基于在 SO 上收集的所有重要输入，我已经确定了这个架构：

采纳答案by paxdiablo

State machines that I've designed before (C, not C++) have all come down to a structarray and a loop. The structure basically consists of a state and event (for look-up) and a function that returns the new state, something like:

我之前设计的状态机（C，不是 C++）都归结为一个struct数组和一个循环。该结构基本上由一个状态和事件（用于查找）以及一个返回新状态的函数组成，例如：

typedef struct {
    int st;
    int ev;
    int (*fn)(void);
} tTransition;

Then you define your states and events with simple defines (the ANYones are special markers, see below):

然后你用简单的定义定义你的状态和事件（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

Then you define all the functions that are called by the transitions:

然后定义转换调用的所有函数：

static int GotKey (void) { ... };
static int FsmError (void) { ... };

All these function are written to take no variables and return the new state for the state machine. In this example global variables are used for passing any information into the state functions where necessary.

所有这些函数都被编写为不接受变量并返回状态机的新状态。在此示例中，全局变量用于在必要时将任何信息传递到状态函数中。

Using globals isn't as bad as it sounds since the FSM is usually locked up inside a single compilation unit and all variables are static to that unit (which is why I used quotes around "global" above - they're more shared within the FSM, than truly global). As with all globals, it requires care.

使用全局变量并不像听起来那么糟糕，因为 FSM 通常被锁定在单个编译单元内，并且所有变量对于该单元都是静态的（这就是我在上面的“全局”周围使用引号的原因 - 它们在FSM，而不是真正的全球性）。与所有全局变量一样，它需要小心。

The transitions array then defines all possible transitions and the functions that get called for those transitions (including the catch-all last one):

然后，转换数组定义了所有可能的转换以及为这些转换调用的函数（包括最后一个包罗万象的）：

tTransition trans[] = {
    { ST_INIT, EV_KEYPRESS, &GotKey},
    : :
    { ST_ANY, EV_ANY, &FsmError}
};
#define TRANS_COUNT (sizeof(trans)/sizeof(*trans))

What that means is: if you're in the ST_INITstate and you receive the EV_KEYPRESSevent, make a call to GotKey.

这意味着：如果您在该ST_INIT州并收到该EV_KEYPRESS事件，请拨打GotKey.

The workings of the FSM then become a relatively simple loop:

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;
            }
        }
    }
}

As alluded to above, note the use of ST_ANYas wild-cards, allowing an event to call a function no matter the current state. EV_ANYalso works similarly, allowing any event at a specific state to call a function.

如上所述，请注意ST_ANY通配符的使用，无论当前状态如何，都允许事件调用函数。EV_ANY也类似地工作，允许处于特定状态的任何事件调用函数。

It can also guarantee that, if you reach the end of the transitions array, you get an error stating your FSM hasn't been built correctly (by using the ST_ANY/EV_ANYcombination.

它还可以保证，如果您到达 transitions 数组的末尾，您会收到一条错误消息，指出您的 FSM 尚未正确构建（通过使用ST_ANY/EV_ANY组合。

I've used code similar for this on a great many communications projects, such as an early implementation of communications stacks and protocols for embedded systems. The big advantage was its simplicity and relative ease in changing the transitions array.

我已经在许多通信项目中使用了类似的代码，例如嵌入式系统的通信堆栈和协议的早期实现。最大的优势是它的简单性和更改转换数组的相对容易。

I've no doubt there will be higher-level abstractions which may be more suitable nowadays but I suspect they'll all boil down to this same sort of structure.

我毫不怀疑会有更高级别的抽象，它们现在可能更合适，但我怀疑它们都会归结为相同的结构。

---

---

And, as ldogstates in a comment, you can avoid the globals altogether by passing a structure pointer to all functions (and using that in the event loop). This will allow multiple state machines to run side-by-side without interference.

而且，正如ldog评论中的状态，您可以通过将结构指针传递给所有函数（并在事件循环中使用它）来完全避免全局变量。这将允许多个状态机在没有干扰的情况下并行运行。

Just create a structure type which holds the machine-specific data (state at a bare minimum) and use that instead of the globals.

只需创建一个结构类型来保存特定于机器的数据（最低限度的状态）并使用它而不是全局变量。

The reason I've rarely done that is simply because most of the state machines I've written have been singleton types (one-off, at-process-start, configuration file reading for example), not needing to run more than one instance. But it has value if you need to run more than one.

我很少这样做的原因很简单，因为我编写的大多数状态机都是单例类型（例如一次性、进程启动、配置文件读取），不需要运行多个实例. 但如果您需要运行多个，它就有价值。

回答by caf

The other answers are good, but a very "lightweight" implementation I've used when the state machine is very simple looks like:

其他答案很好，但是当状态机非常简单时，我使用的一个非常“轻量级”的实现看起来像：

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 ... */
    }
}

I would use this when the state machine is simple enough that the function pointer & state transition table approach is overkill. This is often useful for character-by-character or word-by-word parsing.

当状态机足够简单以至于函数指针和状态转换表方法是矫枉过正时，我会使用它。这对于逐字符或逐字解析通常很有用。

回答by Jason E

Pardon me for breaking every rule in computer science, but a state machine is one of the few (I can count only two off hand) places where a gotostatement is not only more efficient, but also makes your code cleaner and easier to read. Because gotostatements are based on labels, you can name your states instead of having to keep track of a mess of numbers or use an enum. It also makes for much cleaner code since you don't need all the extra cruft of function pointers or huge switch statements and while loops. Did I mention it's more efficient too?

请原谅我违反了计算机科学中的每条规则，但状态机是少数（我只能算两个）goto语句不仅更高效，而且使您的代码更清晰、更易于阅读的地方之一。因为goto语句基于标签，所以您可以命名您的状态，而不必跟踪一团糟的数字或使用枚举。它还可以使代码更简洁，因为您不需要所有多余的函数指针或庞大的 switch 语句和 while 循环。我有没有提到它也更有效？

Here's what a state machine might look like:

下面是状态机的样子：

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;
    }
}

You get the general idea. The point is that you can implement the state machine in an efficient way and one that is relatively easy to read and screams at the reader that they are looking at a state machine. Note that if you are using gotostatements, you must still be careful as it is very easy to shoot yourself in the foot while doing so.

你得到了一般的想法。关键是您可以以一种有效的方式实现状态机，并且相对容易阅读并且向读者尖叫他们正在查看状态机。请注意，如果您使用goto语句，您仍然必须小心，因为这样做时很容易射中自己的脚。

回答by willw

You might consider the State Machine Compiler http://smc.sourceforge.net/

您可能会考虑状态机编译器http://smc.sourceforge.net/

This splendid open source utility accepts a description of a state machine in a simple language and compiles it to any one of a dozen or so languages - including C and C++. The utility itself is written in Java, and can be included as part of a build.

这个出色的开源实用程序接受用简单语言描述的状态机，并将其编译为十几种语言中的任何一种——包括 C 和 C++。该实用程序本身是用 Java 编写的，可以作为构建的一部分包含在内。

The reason to do this, rather than hand coding using GoF State pattern or any other approach, is that once your state machine is expressed as code, the underlying structure tends to disappear under the weight of boilerplate that needs to be generated to support it. Using this approach gives you an excellent separation of concerns, and you keep the structure of your state machine 'visible'. The auto-generated code goes into modules that you don't need to touch, so that you can go back and fiddle with the state machine's structure without impacting the supporting code that you have written.

这样做的原因，而不是使用 GoF 状态模式或任何其他方法手动编码，是因为一旦您的状态机被表示为代码，底层结构往往会在需要生成以支持它的样板的重量下消失。使用这种方法可以很好地分离关注点，并使状态机的结构保持“可见”。自动生成的代码进入您不需要接触的模块中，这样您就可以返回并摆弄状态机的结构，而不会影响您编写的支持代码。

Sorry, I am being over-enthusiastic, and doubtless putting everyone off. But it is a top notch utility, and well-documented too.

抱歉，我太热情了，这无疑让所有人望而却步。但它是一流的实用程序，并且有据可查。

回答by Daniel Daranas

Be sure to check the work of Miro Samek (blog State Space, website State Machines & Tools), whose articles at the C/C++ Users Journalwere great.

请务必查看 Miro Samek 的作品（博客State Space，网站State Machines & Tools），他在C/C++ 用户杂志上发表的文章很棒。

The website contains a complete (C/C++) implementation in both open source and commercial license of a state machine framework (QP Framework), an event handler (QEP), a basic modeling tool (QM)and a tracing tool (QSpy)which allow to draw state machines, create code and debug them.

该网站包含在这两个开源和商业许可证的完整（C / C ++）实现状态机框架（QP框架），一个事件处理程序（QEP） ，一个基本的建模工具（QM）和跟踪工具（QSpy）这允许绘制状态机，创建代码并调试它们。

The book contains an extensive explanation on the what/why of the implementation and how to use it and is also great material to gain understanding of the fundamentals of hierachical and finite state machines.

这本书包含对实现的内容/原因以及如何使用它的广泛解释，也是了解分层和有限状态机基本原理的重要材料。

The website also contains links to several board support packages for use of the software with embedded platforms.

该网站还包含几个板级支持包的链接，以便在嵌入式平台上使用该软件。

回答by ceo

I've done something similar to what paxdiablo describes, only instead of an array of state/event transitions, I set up a 2-dimensional array of function pointers, with the event value as the index of one axis and the current state value as the other. Then I just call state = state_table[event][state](params)and the right thing happens. Cells representing invalid state/event combinations get a pointer to a function that says so, of course.

我做了一些类似于 paxdiablo 描述的事情，只是不是状态/事件转换数组，我设置了一个二维函数指针数组，事件值作为一个轴的索引，当前状态值作为另一个。然后我只是打电话state = state_table[event][state](params)，正确的事情就会发生。当然，表示无效状态/事件组合的单元格会获得一个指向函数的指针。

Obviously, this only works if the state and event values are both contiguous ranges and start at 0 or close enough.

显然，这仅在状态和事件值都是连续范围并且从 0 或足够接近开始时才有效。

回答by Reinstate Monica

A very nice template-based C++ state machine "framework" is given by Stefan Heinzmann in his article.

Stefan Heinzmann 在他的文章中给出了一个非常好的基于模板的 C++ 状态机“框架” 。

Since there's no link to a complete code download in the article, I've taken the liberty to paste the code into a project and check it out. The stuff below is tested and includes the few minor but pretty much obvious missing pieces.

由于文章中没有完整代码下载的链接，我冒昧地将代码粘贴到项目中并查看。下面的内容经过测试，包括一些次要但非常明显的缺失部分。

The major innovation here is that the compiler is generating very efficient code. Empty entry/exit actions have no cost. Non-empty entry/exit actions are inlined. The compiler is also verifying the completeness of the statechart. Missing actions generate linking errors. The only thing that is not caught is the missing Top::init.

这里的主要创新是编译器生成了非常高效的代码。空的进入/退出操作没有成本。非空的进入/退出操作是内联的。编译器也在验证状态图的完整性。缺少操作会产生链接错误。唯一没有被抓住的是失踪Top::init。

This is a very nice alternative to Miro Samek's implementation, if you can live without what's missing -- this is far from a complete UML Statechart implementation, although it correctly implements the UML semantics, whereas Samek's code by design doesn't handle exit/transition/entry actions in correct order.

这是 Miro Samek 实现的一个非常好的替代方案，如果您可以在没有缺失的情况下生活——这远非完整的 UML 状态图实现，尽管它正确实现了 UML 语义，而 Samek 的代码设计不处理退出/转换/entry 操作顺序正确。

If this code works for what you need to do, and you have a decent C++ compiler for your system, it will probably perform better than Miro's C/C++ implementation. The compiler generates a flattened, O(1) transition state machine implementation for you. If the audit of assembly output confirms that the optimizations work as desired, you get close to theoretical performance. Best part: it's relatively tiny, easy to understand code.

如果这段代码适用于您需要做的事情，并且您的系统有一个不错的 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

Test code follows.

测试代码如下。

#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)

回答by Michael Ekstrand

The technique I like for state machines (at least ones for program control) is to use function pointers. Each state is represented by a different function. The function takes an input symbol and returns the function pointer for the next state. The central dispatch loop monitors takes the next input, feeds it to the current state, and processes the result.

我喜欢状态机（至少是程序控制的）的技术是使用函数指针。每个状态由不同的函数表示。该函数接受一个输入符号并返回下一个状态的函数指针。中央调度循环监视器接受下一个输入，将其提供给当前状态，并处理结果。

The typing on it gets a little odd, since C doesn't have a way to indicate types of function pointers returning themselves, so the state functions return void*. But you can do something like this:

它的输入有点奇怪，因为 C 没有办法指示返回自身的函数指针的类型，所以状态函数 return void*。但是你可以做这样的事情：

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);
    }
 }

Then your individual state functions can switch on their input to process and return the appropriate value.

然后，您的各个状态函数可以打开它们的输入以进行处理并返回适当的值。

回答by Joe the Hamster

Simplest case

最简单的情况

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;
  }
}

Points: State is private, not only to the compilation unit but also to the event_handler. Special cases may be handled separately from the main switch using whatever construct deemed necessary.

要点：状态是私有的，不仅对编译单元而且对 event_handler 都是私有的。特殊情况可以使用任何认为必要的结构与主开关分开处理。

More complex case

更复杂的情况

When the switch gets bigger than a couple of screens full, split it into functions that handle each state, using a state table to look up the function directly. The state is still private to the event handler. The state handler functions return the next state. If needed some events can still receive special treatment in the main event handler. I like to throw in pseudo-events for state entry and exit and perhaps state machine start:

当 switch 变得大于几个屏幕满时，将其拆分为处理每个状态的函数，使用状态表直接查找函数。状态仍然是事件处理程序私有的。状态处理函数返回下一个状态。如果需要，某些事件仍然可以在主事件处理程序中接受特殊处理。我喜欢为状态进入和退出以及状态机启动添加伪事件：

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);
  }
}

I am not sure if I nailed the syntax, especially regarding the array of function pointers. I have not run any of this through a compiler. Upon review, I noticed that I forgot to explicitly discard the next state when handling the pseudo events (the (void) parenthesis before the call to state_handler()). This is something that I like to do even if compilers accept the omission silently. It tells readers of the code that "yes, I did indeed mean to call the function without using the return value", and it may stop static analysis tools from warning about it. It may be idiosyncratic because I do not recall having seen anybody else doing this.

我不确定我是否掌握了语法，尤其是关于函数指针数组。我没有通过编译器运行任何这些。经过，我注意到在处理伪事件（调用 state_handler() 之前的 (void) 括号）时忘记显式丢弃下一个状态。即使编译器默默地接受省略，这也是我喜欢做的事情。它告诉代码的读者“是的，我确实打算在不使用返回值的情况下调用该函数”，并且它可能会阻止静态分析工具对此发出警告。这可能是特殊的，因为我不记得见过其他人这样做。

Points: adding a tiny bit of complexity (checking if the next state is different from the current), can avoid duplicated code elsewhere, because the state handler functions can enjoy the pseudo events that occur when a state is entered and left. Remember that state cannot change when handling the pseudo events, because the result of the state handler is discarded after these events. You may of course choose to modify the behaviour.

要点：增加一点点复杂度（检查下一个状态是否与当前状态不同），可以避免在其他地方重复代码，因为状态处理函数可以享受进入和离开状态时发生的伪事件。请记住，处理伪事件时状态不能更改，因为在这些事件之后状态处理程序的结果将被丢弃。您当然可以选择修改行为。

A state handler would look like so:

状态处理程序如下所示：

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;
}

More complexity

更复杂

When the compilation unit becomes too large (whatever you feel that is, I should say around 1000 lines), put each state handler in a separate file. When each state handler becomes longer than a couple of screens, split each event out in a separate function, similar to the way that the state switch was split. You may do this in a number of ways, separately from the state or by using a common table, or combining various schemes. Some of them have been covered here by others. Sort your tables and use binary search if speed is a requirement.

当编译单元变得太大时（不管你觉得是什么，我应该说大约 1000 行），将每个状态处理程序放在一个单独的文件中。当每个状态处理程序变得比几个屏幕长时，将每个事件拆分到一个单独的函数中，类似于拆分状态切换的方式。您可以通过多种方式做到这一点，与状态分开或使用公共表，或组合各种方案。其中一些已被其他人在这里介绍。如果需要速度，请对您的表格进行排序并使用二分搜索。

Generic programming

通用编程

I should like the preprocessor to deal with issues such as sorting tables or even generating state machines from descriptions, allowing you to "write programs about programs". I believe this is what the Boost people are exploiting C++ templates for, but I find the syntax cryptic.

我希望预处理器能够处理诸如排序表甚至根据描述生成状态机之类的问题，让您可以“编写关于程序的程序”。我相信这就是 Boost 人利用 C++ 模板的目的，但我发现语法很神秘。

Two-dimensional tables

二维表

I have used state/event tables in the past but I have to say that for the simplest cases I do not find them necessary and I prefer the clarity and readability of the switch statement even if it does extend past one screen full. For more complex cases the tables quickly get out of hand as others have noted. The idioms I present here allow you to add a slew of events and states when you feel like it, without having to maintain a memory consuming table (even if it may be program memory).

我过去曾使用过状态/事件表，但我不得不说，对于最简单的情况，我认为它们没有必要，我更喜欢 switch 语句的清晰性和可读性，即使它确实扩展了一个屏幕。对于更复杂的情况，正如其他人所指出的那样，这些表格很快就会失控。我在这里介绍的习惯用法允许您根据需要添加大量事件和状态，而无需维护内存消耗表（即使它可能是程序内存）。

Disclaimer

免责声明

Special needs may render these idioms less useful, but I have found them to be very clear and maintainable.

特殊需要可能会使这些习语不太有用，但我发现它们非常清晰且易于维护。

回答by Christoph

Extremely untested, but fun to code, now in a more refined version than my original answer; up-to-date versions can be found at mercurial.intuxication.org:

非常未经测试，但编码很有趣，现在比我原来的答案更精致；最新版本可以在mercurial.intuxication.org找到：

sm.h

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

例子.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;
}