(译)状态机的实现探讨

原文链接地址：http://drdobbs.com/cpp/184401236?pgno=1

         实现一个状态机很容易，但是实现一个好的状态机却不简单。一般实现状态机的时候会有如下的实现代码：

switch (state_)

         case A:

                   do_A();

         case B:

                   do_B();

end switch

         当状态量少并且各个状态之间变化的逻辑比较简单时，这种方法无可厚非，但是它有如下缺点：

l  逻辑代码较混乱；如状态A到状态B的切换，如果需要验证有效性，那么代码会变得臃肿，不再那么直观；示例：

case A:

         if (current_state != C)

                   return -1;

         else

                   current_state = A;

                   return 0;

case ....:

         ....

l  难扩展；大部分状态的处理是相似的，而某些特殊的状态则要特殊处理，比如需要提供附加数据，比如在Task中设定一个状态为suspend，那么需要传递一个要挂起的时间。这种情况类似于GUI程序中的事件通知接口，如：

handle_event(EventId event_, Long ext,...)

ext实际上可以传递任何东西。比如触发了一个文件拖动到图标的事件dropOpen，那么可以将要open的文件路径的地址通过ext传入。这种方式挺万金油的，所以在实现状态机的时候，完全可以借鉴一下。

Context：

         假设场景如下：实现任务Task，它是一个状态机，其状态变化如图：

l  Task被创建后假设获取了必须资源，进入Ready状态

l  Ready状态可以被任务队列执行run， 那么Task进入Running状态

l  Ready状态时可以被suspend挂起，挂起时需要标识挂起的时间

l  Running状态时可以被挂起

l  Suspended状态可以通过润使Task进入running状态

l  Running、Ready、Suspended状态都可以通过cancel，直接进入ended状态

Question:

n  合理实现各个状态之间的切换

n  方便扩展，任务状态有可能会增加，任务的触发时间可能会改变等，状态机的实现必须能够快速适应逻辑的变化

Solution：

         下面探讨如下的实现方案：

u  设计基类：

• 首先是用于传递扩展数据的万金油虚类

#ifndef EVENT_DATA_H

#define EVENT_DATA_H

class EventData

{

public:

    virtual ~EventData() {}; 

    void*   data() = 0;

};

#endif //EVENT_DATA_H

• 状态的通用接口类StateMachine 接口, 此类不但定义了接口,其实其规定了状态机实现的模板,任何状态机的实现都可以按照此模板按部就班的实现.

#ifndef STATE_MACHINE_H

#define STATE_MACHINE_H

#include <stdio.h>

#include "EventData.h"

struct StateStruct;

// base class for state machines

class StateMachine

{

public:

    StateMachine(int maxStates);

    virtual ~StateMachine() {}

protected:

    enum { EVENT_IGNORED = 0xFE, CANNOT_HAPPEN };

    unsigned char currentState;

    void ExternalEvent(unsigned char, EventData* = NULL);

    void InternalEvent(unsigned char, EventData* = NULL);

    virtual const StateStruct* GetStateMap() = 0;

private:

    const int _maxStates;

    bool _eventGenerated;

    EventData* _pEventData;

    void StateEngine(void);

};

typedef void (StateMachine::*StateFunc)(EventData *);

struct StateStruct

{

    StateFunc pStateFunc;   

};

#define BEGIN_STATE_MAP \

public:\

const StateStruct* GetStateMap() {\

    static const StateStruct StateMap[] = {

#define STATE_MAP_ENTRY(entry)\

    { reinterpret_cast<StateFunc>(entry) },

#define END_STATE_MAP \

    { reinterpret_cast<StateFunc>(NULL) }\

    }; \

    return &StateMap[0]; }

#define BEGIN_TRANSITION_MAP \

    static const unsigned char TRANSITIONS[] = {\

#define TRANSITION_MAP_ENTRY(entry)\

    entry,

#define END_TRANSITION_MAP(data) \

    0 };\

    ExternalEvent(TRANSITIONS[currentState], data);

#endif //STATE_MACHINE_H

ExternalEvent接口是带有效性验证的接口,他首先判断状态的有效性,如果有效则调用InternalEvent, InternalEvent是没有验证的内部接口,它直接的修改状态。

• StateMachine 的实现；此实现为通用的逻辑模板，任何状态机的实现都可以套用此模板。

#include <assert.h>

#include "StateMachine.h"

StateMachine::StateMachine(int maxStates) :

    _maxStates(maxStates),

    currentState(0),

    _eventGenerated(false),

    _pEventData(NULL)

{

}   

// generates an external event. called once per external event

// to start the state machine executing

void StateMachine::ExternalEvent(unsigned char newState,

                                 EventData* pData)

{

    // if we are supposed to ignore this event

    if (newState == EVENT_IGNORED) {

        // just delete the event data, if any

        if (pData) 

            delete pData;

    }

    else if (newState == CANNOT_HAPPEN) {

        //! throw exception("xxx");

        //! or

        //! logerror("....");

    }

    else {

        // generate the event and execute the state engine

        InternalEvent(newState, pData);

        StateEngine();                 

    }

}

// generates an internal event. called from within a state

// function to transition to a new state

void StateMachine::InternalEvent(unsigned char newState,

                                 EventData* pData)

{

    _pEventData = pData;

    _eventGenerated = true;

    currentState = newState;

}

// the state engine executes the state machine states

void StateMachine::StateEngine(void)

{

    EventData* pDataTemp = NULL;

    if (_eventGenerated) {        

        pDataTemp = _pEventData;  // copy of event data pointer

        _pEventData = NULL;       // event data used up, reset ptr

        _eventGenerated = false;  // event used up, reset flag

        assert(currentState < _maxStates);

        // execute the state passing in event data, if any

        const StateStruct* pStateMap = GetStateMap();

        (this->*pStateMap[currentState].pStateFunc)(pDataTemp);

        // if event data was used, then delete it

        if (pDataTemp) {

            delete pDataTemp;

            pDataTemp = NULL;

        }

    }

}

在这里ExternalEvent判断该状态是否是有效的，如果是EVENT_IGNORED，那么可以直接忽略此操作，如果是CANNOT_HAPPEN，说明出现了逻辑错误。

l  具体task的实现如下：

#ifndef TASK_H

#define TASK_H

#include "StateMachine.h"

struct TaskData : public EventData

{

    int xxx;

};

class Task : public StateMachine

{

public:

    Task() : StateMachine(ST_MAX_STATES) {}

    // external events taken by this state machine

    void Suspend();

    void Run();

    void Cancel();

private:

    // state machine state functions

    void ST_Ready();

    void ST_Running();

    void ST_Suspended(TaskData* pData);

    void ST_Ended();

    // state map to define state function order

    BEGIN_STATE_MAP

        STATE_MAP_ENTRY(ST_READY)

        STATE_MAP_ENTRY(ST_RUNNING)

        STATE_MAP_ENTRY(ST_SUSPENDED)

        STATE_MAP_ENTRY(ST_ENDED)

    END_STATE_MAP

    // state enumeration order must match the order of state

    // method entries in the state map

    enum E_States {

        ST_READY = 0,

        ST_RUNNING,

        ST_SUSPENDED,

        ST_ENDED,

        ST_MAX_STATES

    };

};

#endif //MOTOR_H

BEGIN_STATE_MAP 宏将自定义的状态函数注册到StateMap中，这样可以直接通过state值索引得到其对应的状态函数。

l  Task的实现代码

#include <assert.h>

#include "task.h"

void Task::Suspend(MotorData* pData)

{

    BEGIN_TRANSITION_MAP                      // - Current State -

        TRANSITION_MAP_ENTRY (ST_Suspended)   // ST_READY

        TRANSITION_MAP_ENTRY (ST_Suspended)   // ST_RUNNING

        TRANSITION_MAP_ENTRY (EVENT_IGNORED)  // ST_SUSPENDED

        TRANSITION_MAP_ENTRY (CANNOT_HAPPEN)  // ST_ENDED

    END_TRANSITION_MAP(pData)

}

void Task::Run(void)

{

    BEGIN_TRANSITION_MAP                      // - Current State -

        TRANSITION_MAP_ENTRY (ST_RUNNING)     // ST_READY

        TRANSITION_MAP_ENTRY (EVENT_IGNORED)  // ST_RUNNING

        TRANSITION_MAP_ENTRY (ST_RUNNING)     // ST_SUSPENDED

        TRANSITION_MAP_ENTRY (CANNOT_HAPPEN)  // ST_ENDED

    END_TRANSITION_MAP(NULL)

}

void Task::Cancel(void)

{

    BEGIN_TRANSITION_MAP                      // - Current State -

        TRANSITION_MAP_ENTRY (ST_ENDED)       // ST_READY

        TRANSITION_MAP_ENTRY (ST_ENDED)       // ST_RUNNING

        TRANSITION_MAP_ENTRY (ST_ENDED)       // ST_SUSPENDED

        TRANSITION_MAP_ENTRY (EVENT_IGNORED)        // ST_ENDED

    END_TRANSITION_MAP(NULL)

}

void Task::ST_Ready()

{

    InternalEvent(ST_READY);

}

void Task::ST_Running()

{

    InternalEvent(ST_RUNNING);

}

void Task::ST_Suspended(MotorData* pData)

{

    InternalEvent(ST_SUSPENDED, pData);

}

void Task::ST_Ended()

{

    InternalEvent(ST_ENDED);

}

在状态的处理上思路是：状态要么是有效的、要么是可以忽略的、要么是根本不会发生的。