65.9K
CodeProject 正在变化。 阅读更多。
Home

通用有限状态机 Revisited。

0xG00DC0FFEE
starIconstarIconstarIconstarIconstarIcon

5.00/5 (16投票s)

2017年5月20日

CPOL

7分钟阅读

viewsIcon

22437

downloadIcon

518

一个更好、更简单的 C++ 有限状态机库实现。

引言

在本文中，我将提供一个库，用于实现 FSM，该库实现方式快速且类似于 OOP，但可以避免你在 C++ 中实现 FSM 时发现的大量样板代码。该接口简单易用。该库已在 Visual Studio 2017 Community Edition、GCC 5.4.0 和 clang 3.8.0 上进行了测试。

背景

尽管 FSM 易于理解，但在 C 和 C++ 中实现起来并不容易。我一直希望能有一个简单的库来帮助我编写 FSM，同时又能避免样板代码和重复代码。几年前，我曾提供过一个类似的库，但它不遵循 C++ 标准，依赖于编译器，最终我放弃了使用它。话虽如此，我还是想在我的工具箱中拥有一个更好的该库的实现。

使用代码

使用状态机

我将从一个图开始，然后展示如何使用状态机对象，之后再解释如何设计状态机类：

这是一个非常简单的随机数生成器图，用于本教程的目的。在图中你可以看到

  1. 我们有两个状态： 开启 和 关闭。初始状态是 关闭 
  2. 我们有三个转换： 开始/停止/生成。很明显，我可以避免在“开启”状态下绘制“开始”转换，因为“开始”的整个想法就是将机器“开启”。但是，我还是决定画出来。
  3. 在图的某个地方会生成一个随机数，但并不清楚这个数字保存在哪里，所以我将把它弄清楚，它保存在状态机内部的一个数据上下文（用户提供的结构体）中。这个数据也可以被任何想观察状态机的人访问。

所以，现在我们都知道状态机是什么样的了，我们也知道定义状态机的三个关键特征。现在让我们来使用它！上面这个例子已经通过使用本文提供的库创建好了。请打开演示 fsm.zip 文件，并使用 CMake 为你喜欢的编译器或 IDE 生成项目。当程序员使用状态机时，他的代码应该看起来像这样：

 fsm<NumbersGeneratorTransitions> numbersGenerator;
 numbersGenerator.move_to_state<StateOff>();
 printf("\nData %X\n", numbersGenerator.state().number);  //Will show the uninitialized number
 numbersGenerator->Start();
 numbersGenerator->Generate();
 numbersGenerator->Stop();
 numbersGenerator->Generate();
 printf("\nData %d\n", numbersGenerator.state().number); //Will show generated random number

*注意： fsm.zip 中的演示与上面的例子类似，但稍显冗长，并且涵盖了其他几个案例。
正如所见，这里的想法是保持接口完全相同，而每个状态的实现是不同的，其中每个状态由一个类表示，而接口本身则正如预期，由一个接口（某种意义上的接口）类表示。

所以，要开始，只需包含

#include "fsm.h"

然后添加一个类来表示共享于所有其他状态/转换接口的状态

struct Data
{
    int number;
    Data() : number(0xdeadbeef) {} //that would be the value of uninitialized nubmer
};

一旦完成状态机（在源文件中也称为上下文）的数据，我们就应该添加状态机的接口

struct NumbersGeneratorTransitions : public impl_ctx<NumbersGeneratorTransitions, Data>
{
    virtual void Start() {}
    virtual void Stop() {}
    virtual void Generate() {}
};

从图中可以看出，不应该使用纯虚方法，因为我们想忽略所有不会改变状态机状态的转换。

使用 impl_ctx<NumbersGeneratorTransitions, Data> 是为了提供样板代码（巧合递归模板模式）来处理状态机，并引入 Data 结构体作为状态机的一部分（之后它会被状态处理程序使用、修改和共享）。

对于每个状态，我们将提供一组接口。这非常简单，只需编写以下声明

struct StateOff : public impl_state<StateOff, NumbersGeneratorTransitions>
{
    virtual void Start();
};

struct StateOn : public impl_state<StateOn, NumbersGeneratorTransitions>
{
    virtual void Stop();
    virtual void Generate();
};

正如你所见，实现与图是一一对应的。我们没有编写太多样板代码。没有太多的杂乱，代码也很容易调试。

void StateOff::Start()
{
    printf("\nEndtered StateOff::Start()\n");
    static bool first_seed = true;
    // init random number (with simplified seed)

    if (first_seed)
    {
        first_seed = false;
        std::srand((unsigned int)time(0));
    }
    // the next state:

    change_state<StateOn>();
}

void StateOn::Stop()
{
    printf("\nEndtered StateOn::Stop()\n");
    change_state<StateOff>();
    /* DO NOT ACCESS this (pointer) OR state()  function after calling  change_state<...>()*/
}

void StateOn::Generate()
{    //just generate random number and put it in data

    printf("\nEndtered StateOn::Generate()\n");
    state().number = std::rand() % 100; //Pick a number between 0-100

    //state is not changed
}

不过有一点，在使用 change_state<...>() 调用时，接口/对象将被销毁（包括所有本地数据）。在很多方面，你可以认为它等同于 delete this，尽管两者之间存在许多差异。

为了初始化，请确保调用 move_to_state<T>()，否则状态机将无法访问。

就这样！没有其他要补充的了，因为该库可以在没有任何实现知识的情况下使用。请运行测试和调试，看看代码是如何工作的。我只补充一点，这个状态机使用了优化的内存分配，其中每个状态都有分配的内存，该内存会在每个状态类的大小和使用过程中被回收。

为了运行/构建代码，用户可以使用 CMake 来为 gcc 或 clang 生成 Visual Studio 项目或 makefile。

更多详情

对于想了解幕后实现更多细节的人，我将专门为此部分提供说明。

  1. template <typename InterfaceT> class fsm - FSM 模板接口将要求你提供状态转换接口的基类（实际接口）。
  2. template<typename InterfaceT, typename StateT> class fsm_ctx - FSM Context 类将再次要求接口和状态类，但你永远不会访问该类。它仅仅充当 FSM 类的超级模板类标记。
  3. template <typename InterfaceT, typename StateT> class impl_ctx - 为转换接口提供基类。它为转换接口提供了几项服务，包括静态构造函数、某种代理类来处理状态以及其他样板代码。

内存管理

使用这个库，我试图避免不必要的内存分配，从而导致大量的内存碎片。基本上，每次状态更改时，都应该分配新状态的内存。不幸的是，如果我们只使用常规的 new operator 来完成此操作，我们将面临内存碎片化。为了避免这种情况，我们为第一个状态转换接口分配内存，一旦完成并进入下一个状态，相同的内存地址将用于下一个状态转换接口，除非下一个状态转换接口类比已分配内存中的类更大，在这种情况下，将为此分配新的内存空间。这样，内存分配在 FSM 的生命周期内保持静态，而不是每次状态更改时进行数千甚至数百万次内存分配。在大多数情况下（以及编译器），所有接口的大小预计是相同的，这导致内存使用非常优化（在这种情况下只分配了一块内存）。查看 static U *create_new_interface(U u, fsm_ctx_t *afsm_ctx) 来了解实现方式。

构造与析构

状态转换的构造和析构在状态更改时自动完成（对用户而言，对库开发者而言，这是一个非常手动过程）。这意味着用户可以使用每个转换接口的构造函数来执行一些操作，以及使用析构函数来清理一些东西。可以通过查看放置 new 运算符的构造函数调用以及虚拟析构函数的调用来了解，例如在函数 U *change_state() 中可以看到 this->~impl_ctx()。

异常

如果用户尝试在初始化之前使用 FSM，将抛出异常。当用户尝试通过 operator -> 或 state() 函数调用状态接口方法时（尽管我正在考虑放宽最后一个规则并避免异常），会出现 throw uninitialized 的情况，这些调用也是无效的。所以使用 move_to_state() 来初始化状态机！

备注

说实话，我不会认为这个库是典型的 C++11，因为它除了 auto、foreach 和 nullptr 之外，其他都可以用旧版本的 C++ 实现或转换，尽管我没有测试过。根据我使用模板元编程的经验，在编译器之间可能会遇到一些难题和不一致的行为。所以，我在实现这个库时，尽量遵循常识。有趣的是，它看起来比我过去为了实现类似 FSM 功能而进行的模板元编程更容易阅读，也更具线性。

希望这对其他开发者有所帮助。

© . All rights reserved.