C++ 中的状态机设计

• 下载 StateMachine.zip
• 下载 StateMachineCompact.zip

引言

2000年，我为《C/C++ Users Journal》(R.I.P.)撰写了一篇题为“C++ 状态机设计”的文章。有趣的是，那篇旧文章仍然可用，并且（在撰写本文时）在谷歌搜索 C++ 状态机时排名第一。这篇文章写于 15 年前，但我仍然在许多项目中使用它的基本思想。它紧凑、易于理解，并且在大多数情况下，功能足够完成我需要的工作。

本文提供了一个具有更新功能的新实现，但代码量略有增加。我还会纠正原始实现中的错误，因为如果您对存储空间要求非常严格，它仍然是一个可行的解决方案。这两种设计都是表驱动的，适用于任何平台（嵌入式或 PC），以及任何 C++ 编译器。

为什么还要有一个状态机设计？当然，现在应该已经有一个可以使用的现有实现了，对吧？也许。偶尔，我会尝试一个新的状态机，但会发现它由于某种原因不适合我的需求。对我来说，问题通常归结为以下一个或多个原因：

1. 代码过大 – 结果实现占用的代码空间太大，无法在嵌入式平台上使用
2. 过于复杂 – 过多的模板或需要采用完整的框架才能使用状态机
3. 无编译器支持 – 依赖于编译器不支持的新 C++ 语言特性
4. 学习曲线陡峭 – 有些需要在这方面付出很多努力
5. 语法困难 – 非直观的状态机表达式，并且编译器错误难以诊断
6. 外部库 – 依赖于外部库，这些库会增加体积或在平台上不受支持
7. 功能过多 – 不需要完整的 UML 符合性，因此超出了当前问题的基本需求
8. 无事件数据 – 无法将唯一的事件数据发送到状态函数
9. 集中事件处理程序 – 单个事件处理函数和 `switch` 语句处理每个类的事件
10. 无类型安全 – 需要基于枚举手动强制类型转换事件数据
11. 有限的转换规则 – 不支持事件忽略和不可能发生的事件转换
12. 非线程安全 – 代码不是线程安全的

请不要误解我的意思，有些实现非常令人印象深刻，适用于许多不同的项目。每种设计都有其权衡，这个设计也不例外。只有您自己才能决定它是否满足您的需求。我将通过本文和示例代码，尽快帮助您入门。这个状态机具有以下特点：

1. 紧凑 – `StateMachine` 类不是模板 – 在 Windows 上只有 448 字节的代码。模板使用得很少。
2. 转换表 – 转换表精确控制状态转换行为。
3. 事件 – 每个事件都是一个简单的公共实例成员函数，可以接受任何参数类型。
4. 状态操作 – 每个状态操作都是一个独立的实例成员函数，如果需要，可以接受单个、唯一的事件数据参数。
5. 守卫/进入/退出操作 – 可选地，状态机可以使用守卫条件和每个状态的独立进入/退出操作函数。
6. 状态机继承 – 支持从基状态机类继承状态。
7. 状态函数继承 – 支持在派生类中覆盖状态函数。
8. 宏 – 可选的多行宏支持通过自动化代码“机制”来简化使用。
9. 类型安全 – 编译时检查可以尽早发现错误。运行时检查其他情况。
10. 线程安全 – 添加软件锁使代码线程安全很容易。

此状态机设计不追求完整的 UML 功能集。它也不是一个层次状态机 (HSM)。相反，它的目标是成为一个相对紧凑、可移植且易于使用的传统有限状态机 (FSM)，并包含足够独特的功能来解决许多不同的问题。

本文不是关于软件状态机的最佳设计分解实践的教程。我将专注于状态机代码和简单的示例，其复杂性足以方便理解其功能和用法。

使用 CMake 创建构建文件。CMake 是免费开源软件。支持 Windows、Linux 和其他工具链。有关更多信息，请参阅 **CMakeLists.txt** 文件。

查看 GitHub 以获取最新源代码

• C++ 状态机设计 - 作者：David Lafreniere

查看其他相关的 GitHub 存储库

• C 语言状态机设计 - 作者：David Lafreniere
• 带线程的 C++ 状态机 - 作者：David Lafreniere
• 带异步多播委托的 C++ 状态机 - 作者：David Lafreniere
• 带现代异步多播委托的 C++ 状态机 - 作者：David Lafreniere

背景

有限状态机 (FSM) 是大多数程序员工具箱中的一种常见设计技术。设计师使用这种编程构造将复杂问题分解为可管理的 States 和 State Transitions。实现状态机的方法不计其数。

`switch` 语句提供了一种最易于实现且最常见的状态机形式。在这里，`switch` 语句中的每个 `case` 都成为一个状态，实现方式如下：

switch (currentState) {
   case ST_IDLE:
       // do something in the idle state
       break;
    case ST_STOP:
       // do something in the stop state
       break;
    // etc...
}

这种方法当然适用于解决许多不同的设计问题。然而，当将其应用于事件驱动、多线程项目时，这种形式的状态机会受到很多限制。

第一个问题是控制哪些状态转换是有效的，哪些是无效的。没有办法强制执行状态转换规则。任何转换都可以随时发生，这并不可取。对于大多数设计，只有少数转换模式是有效的。理想情况下，软件设计应该强制执行这些预定义的 State 顺序并阻止不必要的转换。当尝试将数据发送到特定状态时，会出现另一个问题。由于整个状态机位于单个函数中，因此向任何给定状态发送额外数据非常困难。最后，这些设计很少适用于多线程系统。设计者必须确保状态机是从单个控制线程调用的。

为什么要使用状态机？

使用状态机实现代码是一种解决复杂工程问题的极其有用的设计技术。状态机将设计分解为一系列步骤，或者在状态机术语中称为“状态”。每个状态执行一些定义明确的任务。另一方面，事件是刺激状态机在状态之间移动或转换的刺激。

以一个我将在本文中一直使用的简单例子来说，假设我们正在设计电机控制软件。我们想要启动和停止电机，以及改变电机的速度。很简单。需要向客户端软件公开的电机控制事件如下：

1. 设置速度 – 以特定速度启动电机
2. 停止 – 停止电机

这些事件提供了以任意所需速度启动电机的能力，这也意味着改变已运行电机的速度。或者，我们可以完全停止电机。对于电机控制类来说，这两个事件或函数被认为是外部事件。然而，对于使用我们代码的客户端来说，它们只是类中的普通函数。

这些事件不是状态机状态。处理这两个事件所需的步骤是不同的。在这种情况下，状态是：

1. 空闲 – 电机未旋转，处于静止状态
   • 什么都不做
2. 启动 – 从完全停止开始启动电机
   • 打开电机电源
   • 设置电机速度
3. 改变速度 – 调整已运行电机的速度
   • 改变电机速度
4. 停止 – 停止运行中的电机
   • 关闭电机电源
   • 转到空闲状态

可以看到，将电机控制分解为离散的状态，而不是一个整体函数，我们可以更容易地管理操作电机的规则。

每个状态机都有一个“当前状态”的概念。这是状态机当前所处的状态。在任何给定时间点，状态机只能处于一个状态。特定状态机类的每个实例可以在构造期间设置初始状态。然而，该初始状态在对象创建期间不会执行。只有发送到状态机的事件才会导致状态函数执行。

为了图形化说明状态和事件，我们使用状态图。下图 1 显示了电机控制类的状态转换。一个框表示一个状态，连接的箭头表示事件转换。标有事件名称的箭头是外部事件，而未加装饰的线条被认为是内部事件。（我将在文章后面介绍内部事件和外部事件的区别。）

正如您所看到的，当事件传入时，发生的转换取决于状态机的当前状态。例如，当 `SetSpeed` 事件传入且电机处于 `Idle` 状态时，它会转换为 `Start` 状态。然而，当当前状态是 `Start` 时生成的相同 `SetSpeed` 事件会转换为 `ChangeSpeed` 状态。您还可以看到并非所有状态转换都是有效的。例如，电机不能在不先经过 `Stop` 状态的情况下从 `ChangeSpeed` 转换为 `Idle`。

总之，使用状态机可以捕获和强制执行复杂的交互，否则这些交互可能难以传达和实现。

内部事件和外部事件

正如我之前提到的，事件是导致状态机在状态之间转换的刺激。例如，按下按钮可能是一个事件。`Event` 可以分为两类：外部事件和内部事件。外部事件，在其最基本级别上，是进入状态机对象的函数调用。这些函数是 `public` 的，并且从外部或状态机对象之外的代码调用。系统内的任何线程或任务都可以生成外部事件。如果外部事件函数调用导致状态转换发生，则状态将在调用者的控制线程中同步执行。另一方面，内部事件由状态机自身在状态执行期间生成。

典型的场景包括生成外部事件，这再次归结为进入类 `public` 接口的函数调用。根据生成的事件和状态机的当前状态，执行查找以确定是否需要转换。如果需要，状态机会转换到新状态，并且该状态的代码将执行。在 `state` 函数结束时，会执行一个检查，以确定是否生成了内部事件。如果是，则执行另一个转换，并且新状态有机会执行。此过程继续进行，直到状态机不再生成内部事件，此时原始外部事件函数调用返回。外部事件和任何内部事件（如果有）都在调用者的控制线程中执行。

一旦外部事件启动状态机执行，在没有锁的情况下，它就不能被另一个外部事件中断，直到外部事件和所有内部事件执行完毕。这种“运行到完成”模型为状态转换提供了多线程安全环境。信号量或互斥锁可用于状态机引擎，以阻止可能试图同时访问同一对象的其他线程。有关锁的位置，请参阅源代码函数 `ExternalEvent()` 的注释。

事件数据

当生成事件时，可以选择附加事件数据供状态函数在执行期间使用。一旦状态完成执行，事件数据将被视为已使用，并且必须被删除。因此，发送到状态机的任何事件数据都必须在堆上创建，通过 `operator new`，以便状态机可以使用它。此外，对于我们的特定实现，事件数据必须继承自 `EventData` 基类。这为状态机引擎提供了一个通用的基类，用于删除所有事件数据。

class EventData 
{
public:
    virtual ~EventData() {}
};

状态机实现现在有一个构建选项，可以消除在堆上创建外部事件数据的要求。有关详细信息，请参阅“**外部事件无堆数据**”部分。

状态转换

当生成外部事件时，会执行查找以确定状态转换的行动方案。事件有三种可能的结局：新状态、事件被忽略或不可能发生。新状态会导致转换到允许执行的新状态。也可以转换到现有状态，这意味着当前状态将被重新执行。对于被忽略的事件，不执行任何状态。但是，事件数据（如果有）将被删除。最后一种可能性，“不可能发生”，保留给给定状态机的当前状态下事件无效的情况。如果发生这种情况，软件将发生故障。

在此实现中，不需要内部事件来进行验证性转换查找。假定状态转换是有效的。您可以检查内部和外部事件的有效转换，但在实践中，这只会占用更多存储空间并产生无用功，收益却很少。验证转换的真正需求在于异步外部事件，其中客户端可能会在不适当的时间触发事件。一旦状态机开始执行，就不能中断它。它处于类 `private` 实现的控制之下，因此无需进行转换检查。这使得设计者可以自由地通过内部事件更改状态，而无需更新转换表的负担。

StateMachine 类

创建自己的状态机需要两个基本的基类：`StateMachine` 和 `EventData`。一个类继承自 `StateMachine` 以获得支持状态转换和事件处理的必要机制。`StateMachine` 头文件还包含各种预处理器多行宏，以简化状态机的实现（稍后在文章中解释）。要将唯一数据发送到状态函数，结构必须继承自 `EventData` 基类。

状态机源代码包含在 *StateMachine.cpp* 和 *StateMachine.h* 文件中（请参阅附加的 *StateMachine.zip*）。下面的代码显示了类声明。

class StateMachine 
{
public:
    enum { EVENT_IGNORED = 0xFE, CANNOT_HAPPEN };

    StateMachine(BYTE maxStates, BYTE initialState = 0);
    virtual ~StateMachine() {}

    BYTE GetCurrentState() { return m_currentState; }
    
protected:
    void ExternalEvent(BYTE newState, const EventData* pData = NULL);
    void InternalEvent(BYTE newState, const EventData* pData = NULL);
    
private:
    const BYTE MAX_STATES;
    BYTE m_currentState;
    BYTE m_newState;
    BOOL m_eventGenerated;
    const EventData* m_pEventData;

    virtual const StateMapRow* GetStateMap() = 0;
    virtual const StateMapRowEx* GetStateMapEx() = 0;
    
    void SetCurrentState(BYTE newState) { m_currentState = newState; }

    void StateEngine(void);     
    void StateEngine(const StateMapRow* const pStateMap);
    void StateEngine(const StateMapRowEx* const pStateMapEx);
};

`StateMachine` 是用于处理事件和状态转换的基类。接口包含在四个函数中：

void ExternalEvent(BYTE newState, const EventData* pData = NULL);
void InternalEvent(BYTE newState, const EventData* pData = NULL);
virtual const StateMapRow* GetStateMap() = 0;
virtual const StateMapRowEx* GetStateMapEx() = 0;

`ExternalEvent()` 使用新状态和指向 `EventData` 对象的指针（如果有）作为参数，生成一个外部事件到状态机。`InternalEvent()` 函数使用相同的参数集生成内部事件。

`GetStateMap()` 和 `GetStateMapEx()` 函数返回 `StateMapRow` 或 `StateMapRowEx` 实例的数组，这些实例将在适当的时候被状态引擎检索。继承类必须返回一个包含其中一个函数的数组。如果状态机只有状态函数，则使用 `GetStateMap()`。如果需要守卫/进入/退出功能，则使用 `GetStateMapEx()`。其他未使用的版本必须返回 `NULL`。但是，提供了多行宏来为我们实现这些函数，我将在稍后演示。

电机示例

`Motor` 和 `MotorNM` 类是使用 `StateMachine` 的示例。`MotorNM`（无宏）精确匹配 `Motor` 设计，而不依赖于宏。这使得查看所有宏展开的代码以便于理解。但是，一旦掌握了窍门，我发现宏通过隐藏所需的源代码机制大大简化了使用。

下面显示的 `MotorNM` 类声明不包含任何宏。

class MotorNMData : public EventData
{
public:
    INT speed;
};

// Motor class with no macros
class MotorNM : public StateMachine
{
public:
    MotorNM();

    // External events taken by this state machine
    void SetSpeed(MotorNMData* data);
    void Halt();

private:
    INT m_currentSpeed; 

    // State enumeration order must match the order of state method entries
    // in the state map.
    enum States
    {
        ST_IDLE,
        ST_STOP,
        ST_START,
        ST_CHANGE_SPEED,
        ST_MAX_STATES
    };

    // Define the state machine state functions with event data type
    void ST_Idle(const NoEventData*);
    StateAction<MotorNM, NoEventData, &MotorNM::ST_Idle> Idle;

    void ST_Stop(const NoEventData*);
    StateAction<MotorNM, NoEventData, &MotorNM::ST_Stop> Stop;

    void ST_Start(const MotorNMData*);
    StateAction<MotorNM, MotorNMData, &MotorNM::ST_Start> Start;

    void ST_ChangeSpeed(const MotorNMData*);
    StateAction<MotorNM, MotorNMData, &MotorNM::ST_ChangeSpeed> ChangeSpeed;

    // State map to define state object order. Each state map entry defines a
    // state object.
private:
    virtual const StateMapRowEx* GetStateMapEx() { return NULL; }
    virtual const StateMapRow* GetStateMap() {
        static const StateMapRow STATE_MAP[] = { 
            &Idle,
            &Stop,
            &Start,
            &ChangeSpeed,
        }; 
        C_ASSERT((sizeof(STATE_MAP)/sizeof(StateMapRow)) == ST_MAX_STATES); 
        return &STATE_MAP[0]; }
};

`Motor` 类使用宏进行比较。

class MotorData : public EventData
{
public:
    INT speed;
};

// Motor class using macro support
class Motor : public StateMachine
{
public:
    Motor();

    // External events taken by this state machine
    void SetSpeed(MotorData* data);
    void Halt();

private:
    INT m_currentSpeed; 

    // State enumeration order must match the order of state method entries
    // in the state map.
    enum States
    {
        ST_IDLE,
        ST_STOP,
        ST_START,
        ST_CHANGE_SPEED,
        ST_MAX_STATES
    };

    // Define the state machine state functions with event data type
    STATE_DECLARE(Motor,     Idle,            NoEventData)
    STATE_DECLARE(Motor,     Stop,            NoEventData)
    STATE_DECLARE(Motor,     Start,           MotorData)
    STATE_DECLARE(Motor,     ChangeSpeed,     MotorData)

    // State map to define state object order. Each state map entry defines a
    // state object.
    BEGIN_STATE_MAP
        STATE_MAP_ENTRY(&Idle)
        STATE_MAP_ENTRY(&Stop)
        STATE_MAP_ENTRY(&Start)
        STATE_MAP_ENTRY(&ChangeSpeed)
    END_STATE_MAP    
};

`Motor` 类实现了我们假设的电机控制状态机，客户端可以启动电机（以特定速度）和停止电机。`SetSpeed()` 和 `Halt()` 公共函数被视为进入 `Motor` 状态机的外部事件。`SetSpeed()` 接收包含电机速度的事件数据。该数据结构将在状态处理完成后被删除，因此该结构必须继承自 `EventData` 并在调用函数之前使用 `operator new` 创建。

当创建 `Motor` 类时，其初始状态是 `Idle`。第一次调用 `SetSpeed()` 会将状态机转换为 `Start` 状态，电机在此状态下开始启动。后续的 `SetSpeed()` 事件会转换为 `ChangeSpeed` 状态，在此状态下调整已运行电机的速度。`Halt()` 事件会转换为 `Stop` 状态，在此状态下，在状态执行期间，会生成一个内部事件以转换回 `Idle` 状态。

创建新的状态机需要几个基本的、高级的步骤：

1. 继承自 `StateMachine` 基类
2. 创建一个 `States` 枚举，每个状态函数对应一个条目
3. 使用 `STATE` 宏创建状态函数
4. 可选地，使用 `GUARD`、`ENTRY` 和 `EXIT` 宏为每个状态创建守卫/进入/退出函数
5. 创建一个状态查找表，使用 `STATE_MAP` 宏
6. 为每个外部事件创建一个转换查找表，使用 `TRANSITION_MAP` 宏

状态函数

状态函数实现每个状态——每个状态机状态一个状态函数。在此实现中，所有状态函数都必须遵循以下状态函数签名：

void <class>::<func>(const EventData*)

`<class>` 和 `<func>` 不是模板参数，只是特定类和函数名的占位符。例如，您可以选择一个签名，如 `void Motor::ST_Start(const MotorData*)`。重要的是函数不返回任何数据（返回类型为 `void`），并且它有一个类型为 `EventData*`（或其派生类）的输入参数。

使用 `STATE_DECLARE` 宏声明 `state` 函数。宏参数是状态机类名、状态函数名和事件数据类型。

STATE_DECLARE(Motor,     Idle,            NoEventData)
STATE_DECLARE(Motor,     Stop,            NoEventData)
STATE_DECLARE(Motor,     Start,           MotorData)
STATE_DECLARE(Motor,     ChangeSpeed,     MotorData)

展开上面的宏会得到：

void ST_Idle(const NoEventData*);
StateAction<Motor, NoEventData, &Motor::ST_Idle> Idle;

void ST_Stop(const NoEventData*);
StateAction<Motor, NoEventData, &Motor::ST_Stop> Stop;

void ST_Start(const MotorData*);
StateAction<MotorNM, MotorData, &Motor::ST_Start> Start;

void ST_ChangeSpeed(const MotorData*);
StateAction<Motor, MotorData, &Motor::ST_ChangeSpeed> ChangeSpeed;

请注意，多行宏会自动在每个状态函数名称前加上“ST_”。宏会自动在每个状态/守卫/进入/退出函数名称前添加三个字符。例如，如果使用 `STATE_DEFINE(Motor, Idle, NoEventData)` 声明一个函数，实际的状态函数将被调用为 `ST_Idle()`。

1. ST_ - 状态函数前缀字符
2. GD_ - 守卫函数前缀字符
3. EN_ - 进入函数前缀字符
4. EX_ - 退出函数前缀字符

在声明 `state` 函数后，使用 `STATE_DEFINE` 宏定义 `state` 函数实现。参数是状态机类名、状态函数名和事件数据类型。实现状态行为的代码放在 `state` 函数内部。请注意，任何 `state` 函数都可以调用 `InternalEvent()` 来切换到另一个状态。守卫/进入/退出函数不能调用 `InternalEvent()`，否则会导致运行时错误。

STATE_DEFINE(Motor, Stop, NoEventData)
{
    cout << "Motor::ST_Stop" << endl;
    m_currentSpeed = 0; 

    // perform the stop motor processing here
    // transition to Idle via an internal event
    InternalEvent(ST_IDLE);
}

展开宏会得到此状态函数定义。

void Motor::ST_Stop(const NoEventData* data)
{
    cout << "Motor::ST_Stop" << endl;
    m_currentSpeed = 0; 

    // perform the stop motor processing here
    // transition to Idle via an internal event
    InternalEvent(ST_IDLE);
}

每个状态函数都必须有一个相关的枚举。这些枚举用于存储状态机的当前状态。在 `Motor` 中，`States` 提供了这些枚举，它们稍后用于索引转换映射表和状态映射表。

enum States
{
    ST_IDLE,
    ST_STOP,
    ST_START,
    ST_CHANGE_SPEED,
    ST_MAX_STATES
};

重要的是枚举的顺序要与状态映射中提供的顺序匹配。这样，状态枚举就与特定的状态函数调用绑定在一起。`EVENT_IGNORED` 和 `CANNOT_HAPPEN` 是与这些状态枚举一起使用的另外两个常量。`EVENT_IGNORED` 告诉状态引擎不执行任何状态，只返回并什么都不做。`CANNOT_HAPPEN` 告诉状态引擎发生故障。这种异常的灾难性故障条件永远不应该发生。

状态映射

状态机引擎通过使用状态映射来知道调用哪个状态函数。状态映射将 `m_currentState` 变量映射到特定的状态函数。例如，如果 `m_currentState` 是 2，那么将调用第三个状态映射函数指针条目（从零开始计数）。使用以下三个宏创建状态映射表：

BEGIN_STATE_MAP
STATE_MAP_ENTRY
END_STATE_MAP

`BEGIN_STATE_MAP` 开始状态映射序列。每个 `STATE_MAP_ENTRY` 都有一个状态函数名称参数。`END_STATE_MAP` 终止映射。下面显示了 `Motor` 的状态映射。

BEGIN_STATE_MAP
    STATE_MAP_ENTRY(&Idle)
    STATE_MAP_ENTRY(&Stop)
    STATE_MAP_ENTRY(&Start)
    STATE_MAP_ENTRY(&ChangeSpeed)
END_STATE_MAP    

完成的状态映射只是实现了 `StateMachine` 基类中定义的纯 `virtual` 函数 `GetStateMap()`。现在 `StateMachine` 基类可以通过此调用获取所有 `StateMapRow` 对象。下面显示了宏展开的代码：

private:
    virtual const StateMapRowEx* GetStateMapEx() { return NULL; }
    virtual const StateMapRow* GetStateMap() {
        static const StateMapRow STATE_MAP[] = { 
            &Idle,
            &Stop,
            &Start,
            &ChangeSpeed,
        }; 
        C_ASSERT((sizeof(STATE_MAP)/sizeof(StateMapRow)) == ST_MAX_STATES); 
        return &STATE_MAP[0]; }

请注意 `C_ASSERT` 宏。它在编译时保护状态映射条目数量不正确。Visual Studio 会给出“error C2118: negative subscript”的错误。您的编译器可能会给出不同的错误消息。

或者，守卫/进入/退出功能需要利用宏的 `_EX`（扩展）版本。

BEGIN_STATE_MAP_EX
STATE_MAP_ENTRY_EX or STATE_MAP_ENTRY_ALL_EX 
END_STATE_MAP_EX

`STATE_MAP_ENTRY_ALL_EX` 宏按顺序包含状态操作、守卫条件、进入操作和退出操作四个参数。状态操作是必需的，但其他操作是可选的。如果状态没有操作，则对参数使用 `0`。如果状态没有任何守卫/进入/退出选项，`STATE_MAP_ENTRY_EX` 宏会将所有未使用的选项默认设置为 `0`。下面的宏片段是后面文章中一个高级示例的。

BEGIN_STATE_MAP_EX
    STATE_MAP_ENTRY_ALL_EX(&Idle, 0, &EntryIdle, 0)
    STATE_MAP_ENTRY_EX(&Completed)
    STATE_MAP_ENTRY_EX(&Failed)
    STATE_MAP_ENTRY_ALL_EX(&StartTest, &GuardStartTest, 0, 0)
    STATE_MAP_ENTRY_EX(&Acceleration)
    STATE_MAP_ENTRY_ALL_EX(&WaitForAcceleration, 0, 0, &ExitWaitForAcceleration)
    STATE_MAP_ENTRY_EX(&Deceleration)
    STATE_MAP_ENTRY_ALL_EX(&WaitForDeceleration, 0, 0, &ExitWaitForDeceleration)
END_STATE_MAP_EX

转换映射中的每个条目都是一个 `StateMapRow`。

struct StateMapRow
{
    const StateBase* const State;
};

`StateBase` 指针有一个由 `StateEngine()` 调用纯 `virtual` 接口。

class StateBase
{
public:
    virtual void InvokeStateAction(StateMachine* sm, const EventData* data) const = 0;
};

`StateAction` 继承自 `StateBase`，其唯一职责是实现 `InvokeStateAction()` 并将 `StateMachine` 和 `EventData` 指针强制类型转换为正确的派生类类型，然后调用状态成员函数。因此，状态引擎调用每个状态函数的开销是调用一次虚函数，一次 `static_cast<>` 和一次 `dynamic_cast<>`。

template <class SM, class Data, void (SM::*Func)(const Data*)>
class StateAction : public StateBase
{
public:
    virtual void InvokeStateAction(StateMachine* sm, const EventData* data) const 
    {
        // Downcast the state machine and event data to the correct derived type
        SM* derivedSM = static_cast<SM*>(sm);

        // Dynamic cast the data to the correct derived type        
        const Data* derivedData = dynamic_cast<const Data*>(data);
        ASSERT_TRUE(derivedData != NULL);

        // Call the state function
        (derivedSM->*Func)(derivedData);
    }
};

`StateAction<>` 的模板参数是状态机类（`SM`）、事件数据类型（`Data`）和指向状态函数的成员函数指针（`Func`）。

还存在 `GuardCondition<>`、`EntryAction<>` 和 `ExitAction<>` 类，它们的作用相同——对状态机和事件数据进行类型转换，然后调用操作成员函数。模板参数存在细微差异。`GuardCondition<>` 类的 `Func` 模板参数略有不同，并返回一个 `BOOL`。`ExitAction<>` 没有 `Data` 模板参数。

转换映射

需要处理的最后一个细节是状态转换规则。状态机如何知道应该发生哪些转换？答案是转换映射。转换映射是一个查找表，它将 `m_currentState` 变量映射到一个状态枚举常量。每个外部事件都有一个使用三个宏创建的转换映射表：

BEGIN_TRANSITION_MAP
TRANSITION_MAP_ENTRY
END_TRANSITION_MAP

`Motor` 中的 `Halt()` 事件函数定义了转换映射如下：

void Motor::Halt()
{
    BEGIN_TRANSITION_MAP                                      // - Current State -
        TRANSITION_MAP_ENTRY (EVENT_IGNORED)                  // ST_IDLE
        TRANSITION_MAP_ENTRY (CANNOT_HAPPEN)                  // ST_STOP
        TRANSITION_MAP_ENTRY (ST_STOP)                        // ST_START
        TRANSITION_MAP_ENTRY (ST_STOP)                        // ST_CHANGE_SPEED
    END_TRANSITION_MAP(NULL)
}

下面是 `Halt()` 的宏展开代码。同样，请注意 `C_ASSERT` 宏提供了编译时保护，防止转换映射条目数量不正确。

void Motor::Halt()
{
    static const BYTE TRANSITIONS[] = {
        EVENT_IGNORED,                    // ST_IDLE
        CANNOT_HAPPEN,                    // ST_STOP
        ST_STOP,                          // ST_START
        ST_STOP,                          // ST_CHANGE_SPEED
    };
    ExternalEvent(TRANSITIONS[GetCurrentState()], NULL); 
    C_ASSERT((sizeof(TRANSITIONS)/sizeof(BYTE)) == ST_MAX_STATES);     
}

`BEGIN_TRANSITION_MAP` 开始映射。后面的每个 `TRANSITION_MAP_ENTRY` 都指示状态机应该根据当前状态做什么。每个转换映射表中的条目数必须与状态函数的数量完全匹配。在我们的示例中，我们有四个状态函数，所以我们需要四个条目。每个条目的位置与状态映射中定义的状态函数的顺序相匹配。因此，`Halt()` 函数中的第一个条目表示 `EVENT_IGNORED`，如下所示：

TRANSITION_MAP_ENTRY (EVENT_IGNORED)    // ST_IDLE

这被解释为“如果当前状态是 Idle 状态时发生 Halt 事件，则忽略该事件。”

同样，映射中的第三个条目是：

TRANSITION_MAP_ENTRY (ST_STOP)         // ST_START

这表示“如果当前状态是 Start 状态时发生 Halt 事件，则转换到 Stop 状态。”

`END_TRANSITION_MAP` 终止映射。此结束宏的参数是事件数据（如果有）。`Halt()` 没有事件数据，所以参数是 `NULL`，但 `ChangeSpeed()` 有数据，所以它被传递在这里。

状态引擎

状态引擎根据生成的事件来执行状态函数。转换映射是 `StateMapRow` 实例的数组，由 `m_currentState` 变量索引。当 `StateEngine()` 函数执行时，它通过调用 `GetStateMap()` 或 `GetStateMapEx()` 来查找 `StateMapRow` 或 `StateMapRowEx` 数组。

void StateMachine::StateEngine(void)
{
    const StateMapRow* pStateMap = GetStateMap();
    if (pStateMap != NULL)
        StateEngine(pStateMap);
    else
    {
        const StateMapRowEx* pStateMapEx = GetStateMapEx();
        if (pStateMapEx != NULL)
            StateEngine(pStateMapEx);
        else
            ASSERT();
    }
}

通过使用新的状态值索引 `StateMapRow` 表来执行状态函数，方法是调用 `InvokeStateAction()`。

const StateBase* state = pStateMap[m_newState].State;
state->InvokeStateAction(this, pDataTemp);

在状态函数有机会执行后，它会删除事件数据（如果有），然后检查是否生成了任何内部事件。下面显示了一个完整的状态引擎函数。另一个重载的状态引擎函数（请参阅附加的源代码）处理具有 `StateMapRowEx` 表的状态机，该表包含额外的守卫/进入/退出功能。

void StateMachine::StateEngine(const StateMapRow* const pStateMap)
{
    const EventData* pDataTemp = NULL;    
    
    // While events are being generated keep executing states
    while (m_eventGenerated)
    {
        // Error check that the new state is valid before proceeding
        ASSERT_TRUE(m_newState < MAX_STATES);
    
        // Get the pointer from the state map
        const StateBase* state = pStateMap[m_newState].State;
            
        // Copy of event data pointer
        pDataTemp = m_pEventData;

        // Event data used up, reset the pointer
        m_pEventData = NULL;

        // Event used up, reset the flag
        m_eventGenerated = FALSE;

        // Switch to the new current state
        SetCurrentState(m_newState);

        // Execute the state action passing in event data
        ASSERT_TRUE(state != NULL);
        state->InvokeStateAction(this, pDataTemp);

        // If event data was used, then delete it
        if (pDataTemp)
        {
             delete pDataTemp;
             pDataTemp = NULL;
        }
    }
}

守卫、进入、状态和退出操作的状态引擎逻辑由以下顺序表示。`StateMapRow` 引擎仅实现以下 #1 和 #5。扩展的 `StateMapRowEx` 引擎使用整个逻辑顺序。

1. 评估状态转换表。如果为 `EVENT_IGNORED`，则忽略事件，不执行转换。如果为 `CANNOT_HAPPEN`，则软件发生故障。否则，继续下一步。
2. 如果定义了守卫条件，则执行守卫条件函数。如果守卫条件返回 `FALSE`，则忽略状态转换，并且不调用状态函数。如果守卫返回 `TRUE`，或者如果不存在守卫条件，则将执行状态函数。
3. 如果转换到新状态并且当前状态定义了退出操作，则调用当前状态的退出操作函数。
4. 如果转换到新状态并且新状态定义了进入操作，则调用新状态的进入操作函数。
5. 调用新状态的状态操作函数。新状态现在是当前状态。

生成事件

此时，我们已经有了一个可用的状态机。让我们看看如何向其生成事件。通过使用 new 在堆上创建事件数据结构，分配结构成员变量，并调用外部事件函数来生成外部事件。下面的代码片段显示了如何进行同步调用。

MotorData* data = new MotorData();
data->speed = 50;
motor.SetSpeed(data);

要从状态函数内部生成内部事件，请调用 `InternalEvent()`。如果目标不接受事件数据，则只用要转换到的状态调用该函数。

InternalEvent(ST_IDLE);

在上面的示例中，一旦状态函数完成执行，状态机将转换到 `Idle` 状态。另一方面，如果需要将事件数据发送到目标状态，则需要创建数据结构并在堆上传递它作为参数。

MotorData* data = new MotorData();
data->speed = 100;
InternalEvent(ST_CHANGE_SPEED, data);

外部事件无堆数据

状态机具有 `EXTERNAL_EVENT_NO_HEAP_DATA` 构建选项，该选项会更改 `ExternalEvent()` 的行为。定义后，只需在堆栈上传递数据，而不是在堆上创建外部事件数据，如下所示。此选项减轻了调用者记住动态创建事件数据结构的负担。

MotorData data;
data.speed = 100;
motor.SetSpeed(&data);

该选项不影响内部事件。`InternalEvent()` 数据（如果有）仍必须在堆上创建。

MotorData* data = new MotorData();
data->speed = 100;
InternalEvent(ST_CHANGE_SPEED, data);

隐藏和消除堆使用

`SetSpeed()` 函数接受一个 `MotorData` 参数，客户端必须在堆上创建。或者，类可以向调用者隐藏堆使用。更改很简单，只需在 `SetSpeed()` 函数内部创建 `MotorData` 实例。这样，调用者就不需要创建动态实例了。

void Motor::SetSpeed(INT speed)
{
    MotorData* data = new MotorData;
    pData->speed = speed;

    BEGIN_TRANSITION_MAP                             // - Current State -
        TRANSITION_MAP_ENTRY (ST_START)              // ST_IDLE
        TRANSITION_MAP_ENTRY (CANNOT_HAPPEN)         // ST_STOP
        TRANSITION_MAP_ENTRY (ST_CHANGE_SPEED)       // ST_START
        TRANSITION_MAP_ENTRY (ST_CHANGE_SPEED)       // ST_CHANGE_SPEED
    END_TRANSITION_MAP(data)
}

或者，使用 `EXTERNAL_EVENT_NO_HEAP_DATA` 构建选项，调用者就不需要创建堆上的外部事件数据了。

在某些系统上，使用堆是不希望的。对于这些系统，我在附加的源代码中包含了 `xallocator` 固定块分配器。它是可选的，但使用时，它会从静态内存或先前回收的堆内存创建内存块。`EventData` 基类中的单个 `XALLOCATOR` 宏为所有 `EventData` 及派生类提供固定块分配。

#include "xallocator.h"
class EventData
{
public:
    virtual ~EventData() {}
    XALLOCATOR
};

有关 xallocator 的更多信息，请参阅文章“**用快速固定块内存分配器替换 malloc/free**”。

状态机继承

继承状态允许公共状态驻留在基类中，以便与继承的类共享。`StateMachine` 轻松支持状态机继承。我将用一个例子来说明。

有些系统具有内置的自检模式，其中软件执行一系列测试步骤以确定系统是否正常运行。在此示例中，每个自检都有常见的状态来处理 `Idle`、`Completed` 和 `Failed` 状态。通过继承，基类包含共享状态。`SelfTest` 和 `CentrifugeTest` 类演示了此概念。状态图如下所示。

`SelfTest` 定义了以下状态：

0. 空闲
1. Completed
2. 失败

`CentrifugeTest` 继承了这些状态并创建了新的状态：

3. 开始测试
4. 加速
5. 等待加速
6. 减速
7. 等待减速

`SeftTest` 基类定义了 `States` 枚举和状态，但没有定义状态映射。只有层次结构中最派生的状态机类才定义状态映射。

enum States
{
    ST_IDLE,
    ST_COMPLETED,
    ST_FAILED,
    ST_MAX_STATES
};

// Define the state machine states
STATE_DECLARE(SelfTest,     Idle,            NoEventData)
ENTRY_DECLARE(SelfTest,     EntryIdle,       NoEventData)
STATE_DECLARE(SelfTest,     Completed,       NoEventData)
STATE_DECLARE(SelfTest,     Failed,          NoEventData)

`CentrifugeTest` 类在其下方定义了其状态机。请注意“`ST_START_TEST = SelfTest::ST_MAX_STATES`”枚举条目。派生类必须从基类结束的地方继续对状态进行编号，这一点至关重要。

enum States
{
    // Continue state numbering using the last SelfTest::States enum value
    ST_START_TEST = SelfTest::ST_MAX_STATES,    
    ST_ACCELERATION,
    ST_WAIT_FOR_ACCELERATION,
    ST_DECELERATION,
    ST_WAIT_FOR_DECELERATION,
    ST_MAX_STATES
};

// Define the state machine state functions with event data type
STATE_DECLARE(CentrifugeTest,     Idle,                        NoEventData)
STATE_DECLARE(CentrifugeTest,     StartTest,                   NoEventData)
GUARD_DECLARE(CentrifugeTest,     GuardStartTest,              NoEventData)
STATE_DECLARE(CentrifugeTest,     Acceleration,                NoEventData)
STATE_DECLARE(CentrifugeTest,     WaitForAcceleration,         NoEventData)
EXIT_DECLARE(CentrifugeTest,      ExitWaitForAcceleration)
STATE_DECLARE(CentrifugeTest,     Deceleration,                NoEventData)
STATE_DECLARE(CentrifugeTest,     WaitForDeceleration,         NoEventData)
EXIT_DECLARE(CentrifugeTest,      ExitWaitForDeceleration)

// State map to define state object order. Each state map entry defines a
// state object.
BEGIN_STATE_MAP_EX
    STATE_MAP_ENTRY_ALL_EX(&Idle, 0, &EntryIdle, 0)
    STATE_MAP_ENTRY_EX(&Completed)
    STATE_MAP_ENTRY_EX(&Failed)
    STATE_MAP_ENTRY_ALL_EX(&StartTest, &GuardStartTest, 0, 0)
    STATE_MAP_ENTRY_EX(&Acceleration)
    STATE_MAP_ENTRY_ALL_EX(&WaitForAcceleration, 0, 0, &ExitWaitForAcceleration)
    STATE_MAP_ENTRY_EX(&Deceleration)
    STATE_MAP_ENTRY_ALL_EX(&WaitForDeceleration, 0, 0, &ExitWaitForDeceleration)
END_STATE_MAP_EX    

状态映射包含层次结构中所有状态的条目，在本例中是 `SelfTest` 和 `CentrifugeTest`。请注意使用 `_EX` 扩展状态映射宏，以便支持守卫/进入/退出功能。例如，`StartState` 的守卫条件声明如下：

GUARD_DECLARE(CentrifugeTest, GuardStartTest, NoEventData)

守卫条件函数返回 `TRUE` 表示执行状态函数，否则返回 `FALSE`。

GUARD_DEFINE(CentrifugeTest, GuardStartTest, NoEventData)
{
    cout << "CentrifugeTest::GuardStartTest" << endl;
    if (m_speed == 0)
        return TRUE;    // Centrifuge stopped. OK to start test.
    else
        return FALSE;   // Centrifuge spinning. Can't start test.
}

基类外部事件函数

在使用状态机继承时，不仅最派生的类可以定义外部事件函数。基类和中间类也可以使用转换映射。父状态机不了解子类。可能存在一个或多个子类状态机层次结构，每个子类都添加了更多状态。因此，最派生状态机的父类使用一个*部分*转换映射，即，状态转换映射仅处理父类已知的状态。在当前状态超出最大父状态枚举范围时生成的任何事件都必须由 `PARENT_TRANSITION` 宏处理，该宏直接放在转换映射之上，如下所示。

void SelfTest::Cancel()
{
    PARENT_TRANSITION (ST_FAILED)

    BEGIN_TRANSITION_MAP                                    // - Current State -
        TRANSITION_MAP_ENTRY (EVENT_IGNORED)                // ST_IDLE
        TRANSITION_MAP_ENTRY (CANNOT_HAPPEN)                // ST_COMPLETED
        TRANSITION_MAP_ENTRY (CANNOT_HAPPEN)                // ST_FAILED
    END_TRANSITION_MAP(NULL)
}

上面的 `PARENT_TRANSITION` 示例的含义是“如果当状态机*不*处于 `ST_IDLE`、`ST_COMPLETE` 或 `ST_FAILED` 状态时生成 `Cancel` 事件，则转换到 `ST_FAILED` 状态”。放在转换映射之前的宏是当当前状态超出当前状态机所知道的范围时的“捕获所有”宏。上面示例的展开的 `PARENT_TRANSITION` 宏如下所示：

if (GetCurrentState() >= ST_MAX_STATES && 
    GetCurrentState() < GetMaxStates()) { 
     ExternalEvent(ST_FAILED); 
     return; }

`GetCurrentState()` 返回状态机的当前状态。`ST_MAX_STATES` 是父类 `State` 枚举的最大值。`GetMaxStates()` 返回整个状态机直到最派生类的最大状态值。展开的代码显示，如果当前状态高于最大父类状态值（即 `SelfTest::ST_MAX_STATES`），但低于整个状态机的最大状态值（即 `CentrifugeTest::ST_MAX_STATES`），则转换到 `Failed` 状态。这样，如果状态超出了父类部分转换映射处理的范围，转换就会被统一处理。否则，部分转换映射会处理状态转换。`EVENT_IGNORED` 和 `CANNOT_HAPPEN` 也是有效的 `PARENT_TRANSITION` 参数。

假设父类 `SelfTest::Cancel()` 对于某些子类来说是不可接受的。只需重写或将外部事件函数设为 `virtual`，并在派生类的 `Cancel()` 函数中使用完整的转换映射。

作为部分转换映射的替代方案，父类可以手动生成外部事件，而无需任何宏支持。要在父类层次结构级别中拥有外部事件函数，请使用 `GetCurrentState()` 和 `ExternalEvent()`。`SelfTest` 类有一个外部事件函数：`Cancel()`。如下面的代码所示，如果当前状态不是 Idle，状态机将转换到 Failed 状态。

void SelfTest::Cancel()
{
    if (GetCurrentState() != ST_IDLE)
        ExternalEvent(ST_FAILED);
}

这里表达的状态机继承技术不实现层次状态机 (HSM)。HSM 具有不同的语义和行为，其中包括分层的事件处理模型。这里解释的功能通过将通用状态提取到基类中来实现代码重用，但状态机仍被视为传统的 FSM。

状态函数继承

状态函数可以在派生类中被覆盖。如果需要，派生类可以调用基类实现。在这种情况下，`SelfTest` 声明并定义了一个 `Idle` 状态。

STATE_DECLARE(SelfTest, Idle, NoEventData)

STATE_DEFINE(SelfTest,  Idle, NoEventData)
{
    cout << "SelfTest::ST_Idle" << endl;
}

`CentrifugeTest` 也声明并定义了相同的 `Idle` 状态，并使用相同的事件数据类型。

STATE_DECLARE(CentrifugeTest,  Idle, NoEventData)

STATE_DEFINE(CentrifugeTest,   Idle, NoEventData)
{
    cout << "CentrifugeTest::ST_Idle" << endl;

    // Call base class Idle state
    SelfTest::ST_Idle(data);    
    StopPoll();
}

`CentrifugeTest::ST_Idle()` 函数调用基类实现 `SelfTest::ST_Idle()`。状态函数继承是一种强大的机制，允许层次结构中的每个级别处理相同的事件。

与覆盖状态函数相同，派生类也可以覆盖守卫/进入/退出函数。在覆盖中，您需要根据具体情况决定是否调用基类实现。

StateMachine 精简类

如果 `StateMachine` 实现由于 `virtual` 函数和类型转换而太大或太慢，那么精简版本是可用的，但代价是成员函数指针没有类型检查。精简版本仅占 68 字节（在 Windows release build 上），而非精简版本占 448 字节。请参阅 *StateMachineCompact.zip* 获取源文件。

请注意，我们必须在 `STATE_MAP_ENTRY` 宏中使用 `reinterpret_cast<>` 运算符将派生类成员函数指针转换为 `StateMachine` 成员函数指针。

reinterpret_cast<StateFunc>(stateFunc)

进行此上溯是必要的，因为 `StateMachine` 基类不知道派生类是什么。因此，至关重要的是提供给 `STATE_MAP_ENTRY` 的条目实际上是继承类的成员函数，并且它们符合前面讨论的状态函数签名（请参阅“状态函数”部分）。否则，将会发生糟糕的事情。

在大多数项目中，我不会计算状态执行的 CPU 指令，并且额外的几个字节存储空间也不是关键的。我项目中的状态机部分从未成为瓶颈。因此，我更喜欢非精简版本的增强错误检查。

多线程安全

为了防止在状态机执行过程中被另一个线程抢占，`StateMachine` 类可以在 `ExternalEvent()` 函数中使用锁。在允许外部事件执行之前，可以锁定一个信号量。当外部事件和所有内部事件都处理完毕后，软件锁将被释放，从而允许另一个外部事件进入状态机实例。

注释标示了如果应用程序是多线程的，应该在哪里放置锁和解锁。如果使用锁，每个 `StateMachine` 对象都应该有自己的软件锁实例。这可以防止单个实例锁定并阻止所有其他 `StateMachine` 对象执行。请注意，只有当 `StateMachine` 实例被多个控制线程调用时，才需要软件锁。如果不是，则不需要锁。

有关使用此处介绍的状态机的完整多线程示例，请参阅文章“**带线程的 C++ 状态机**”。

替代方案

有时，您需要更强大的功能来捕获系统使用事件和状态的行为。这里介绍的版本是传统 FSM 的一种变体。而真正的层次状态机 (HSM) 可以大大简化某些类型问题的解决方案。有许多优秀的 HSM 项目可供您探索。但有时一个简单的 FSM 就足够了。

优点

与旧的 `switch` 语句风格相比，使用此方法实现状态机可能需要额外的努力。然而，其回报是一个更健壮的设计，可以uniformly 地应用于整个多线程系统。让每个状态都有自己的函数比一个巨大的 switch 语句更容易阅读，并且允许将唯一的事件数据发送到每个状态。此外，验证状态转换通过消除不需要的状态转换造成的副作用来防止客户端误用。

我曾将此代码的变体用于自检引擎、手势识别库、用户界面向导和机器自动化等项目。此实现为继承类提供了易用性。通过宏，您可以轻松地“转动曲柄”，而无需过多考虑状态引擎底层运行机制。这让您有更多时间专注于更重要的事情，例如状态转换的设计和状态函数的实现。

参考文献

• C 语言状态机设计 - 作者：David Lafreniere
• 带线程的 C++ 状态机 - 作者：David Lafreniere
• 带异步多播委托的 C++ 状态机 - 作者：David Lafreniere
• 用快速固定块内存分配器替换 malloc/free - 作者：David Lafreniere
• 高效的 C++ 固定块内存分配器 - 作者：David Lafreniere

历史

• 2016年3月23日
  • 首次发布
• 2016年3月28日
  • 更新了附加的 *StateMachine.zip* 以便移植
• 2016年4月3日
  • 修正了图 1 中的一个错误
• 2016年4月17日
  • 更新了附加的 *StateMachine.zip* 源代码，包含 xallocator 错误修复
• 2016年10月26日
  • 在 *StateMachine.zip* 中修复了 `STATE_DECLARE` 中的预处理器错误
  • 在 *StateMachineCompact.zip* 中修复了 `END_STATE_MAP` 中的宏错误
  • 进行了少量修复，以便更容易将代码移植到其他平台
  • 使用错误修复更新了附加的 *StateMachine.zip* 和 *StateMachineCompact.zip* 源代码
• 2016年11月19日
  • 添加了**参考文献**部分
• 2017年1月16日
  • 添加了 `EXTERNAL_EVENT_NO_HEAP_DATA` 构建选项
  • 更新了文章和附加的 *StateMachine.zip* 源代码
• 2017年1月17日
  • 添加了部分转换映射功能
  • 更新了文章和附加的 StateMachine.zip 源代码。
• 2019年2月20日
  • 添加了对 C 语言状态机文章的引用。
  • 文章小幅修正。 
  • 使用小的包含修复更新了源代码，该修复位于 **xallocator.cpp** 中。