CppExplore

一切像雾像雨又像风

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  29 随笔 :: 0 文章 :: 280 评论 :: 0 Trackbacks

作者:CppExplore 网址:http://www.cppblog.com/CppExplore/
上接《系统设计之 状态机(一)》
三、状态机实现
(2)面向过程方式
2、层次状态机模块实现。

与常规状态机相比,它的FSM_STATE结构没有default_func,多了 FSM_STATE_ID parent; FSM_STATE_ID default_child;两个结构。状态机初始化的时候可以指定默认状态,为了防止指定的状态非叶结点,增加fsm_init方法。该状态机的事件处理算法简单描述如下:(1)首先在当前状态以及其祖先状态的状态事件表中搜索匹配事件,如果搜索到,保存操作以及目的状态标识;(2)在old栈中保存当前状态到根节点的路径,在new栈中保存目的状态到根节点的路径;(3)将old栈中的顶层元素依次与new栈的顶层元素匹配,如果匹配则都出栈,不匹配,停止;(4)当前的old栈中节点即为该事件导致的退出状态,从栈低扫描到栈顶,依次执行exit_func;(5)执行以前保存的操作;(6)扫描new栈,从栈顶到栈低依次执行enter_func;(7)最后检测目的状态是否是叶节点状态,否,则依次进入default_child节点,并执行enter_func。模块实现代码如下:
#define SINGLE_STATE_MAX_EVENT 10
#define STATE_TREE_DEPTH 
10
typedef  
int FSM_EVENT_ID;
typedef struct event_param_st
{
    FSM_EVENT_ID id;
    union
{
        
int i;
    }
data;
}
FSM_EVENT;
typedef  
int FSM_STATE_ID;
typedef 
void (*FSM_FUNC)(FSM_EVENT *);
typedef struct state_event_st
{
    FSM_FUNC func;
    FSM_EVENT_ID event;
    FSM_STATE_ID state;
}
FSM_STATE_EVENT;
typedef struct state_st
{
    FSM_STATE_ID id;
    
char *name;
    FSM_STATE_ID parent;
    FSM_STATE_ID default_child;
    FSM_FUNC enter_func;
    FSM_FUNC exit_func;
    FSM_STATE_EVENT event_table[SINGLE_STATE_MAX_EVENT]; 
}
FSM_STATE;
typedef FSM_STATE STATE_TABLE[];
typedef FSM_STATE 
* PTR_STATE_TABLE;

#define END_EVENT_ID 
-1
#define END_STATE_ID 
-1
#define BEGIN_FSM_STATE_TABLE(state_stable) 
static STATE_TABLE state_stable={
#define BEGIN_STATE(id,name,parent,default_child,enter_func,exit_func) 
{id,name,parent,default_child,enter_func,exit_func,{
#define STATE_EVENT_ITEM(func,event,state) 
{func,event,state},
#define END_STATE(id) 
{NULL,END_EVENT_ID,END_STATE_ID}}
}
,
#define END_FSM_STATE_TABLE(state_stable) 
{END_STATE_ID,NULL,END_STATE_ID,END_STATE_ID,NULL,NULL,NULL}}
;

typedef struct fsm_st
{
    FSM_STATE_ID state_id;
    FSM_FUNC default_func;
    PTR_STATE_TABLE state_tables;
}
FSM;

void fsm_init(FSM &fsm)
{
    FSM_STATE 
*state=&(fsm.state_tables[fsm.state_id]);
    
while(state->default_child!=END_STATE_ID)
    
{
        state
=&(fsm.state_tables[state->default_child]);
        
if(state->enter_func)
            state
->enter_func(NULL);
    }

    fsm.state_id
=state->id;
}

void fsm_do_event(FSM &fsm, FSM_EVENT &event)
{
    FSM_STATE 
*state;
    FSM_STATE_ID state_id,old_state_id,new_state_id;
    FSM_STATE_ID oldStack[STATE_TREE_DEPTH],newStack[STATE_TREE_DEPTH];
    
int old_cur=0,new_cur=0;
    
    bool isMatch
=false;
    FSM_FUNC match_func
=NULL;
    
int i=0;
    state_id
=old_state_id=fsm.state_id;
    
do
    
{
        i
=0;
        state
=&(fsm.state_tables[state_id]);
        
while(state->event_table[i].event!=END_EVENT_ID)
        
{
            
if(state->event_table[i].event==event.id)
            
{
                isMatch
=true;
                match_func
=state->event_table[i].func;
                new_state_id
=state->event_table[i].state;
                
break;
            }

            i
++;
        }

        
if(isMatch==false)
            state_id
=state->parent;
        
else
            
break;
    }
while(state->parent!=END_STATE_ID);
    
if(isMatch==false)
    
{
        
if(fsm.default_func)
            fsm.default_func(
&event);
        
return;
    }

    
if(new_state_id==old_state_id)
    
{
        
if(match_func)
            match_func(
&event);
        
return;
    }

    state_id
=old_state_id;
    
do
    
{
        oldStack[old_cur
++]=state_id;
        state
=&(fsm.state_tables[state_id]);
        state_id
=state->parent;
    }
while(state->parent!=END_STATE_ID);
    state_id
=new_state_id;
    
do
    
{
        newStack[new_cur
++]=state_id;
        state
=&(fsm.state_tables[state_id]);
        state_id
=state->parent;
    }
while(state->parent!=END_STATE_ID);
    
while(oldStack[old_cur-1]==newStack[new_cur-1])
    
{
        old_cur
--;
        new_cur
--;
    }

    
for(i=0;i<old_cur;i++)
    
{
        
if(fsm.state_tables[oldStack[i]].exit_func)
            fsm.state_tables[oldStack[i]].exit_func(
&event);
    }

    
if(match_func)
        match_func(
&event);
    
for(i=new_cur;i>0;i--)
    
{
        
if(fsm.state_tables[newStack[i-1]].enter_func)
            fsm.state_tables[newStack[i
-1]].enter_func(&event);
    }

    state
=&(fsm.state_tables[new_state_id]);
    
while(state->default_child!=END_STATE_ID)
    
{
        state
=&(fsm.state_tables[state->default_child]);
        
if(state->enter_func)
            state
->enter_func(&event);
    }

    fsm.state_id
=state->id;
}
使用举例,仅仅列举一个状态表和简单的状态机初始化,状态和事件应该为enum,当前使用数字,仅为了举例,操作的实现不在写出。
BEGIN_FSM_STATE_TABLE(my_state_table)
    BEGIN_STATE(
0,"first",END_STATE_ID,2,enter_fsm,exit_fsm)
        STATE_EVENT_ITEM(func_fsm,
1,1)
        STATE_EVENT_ITEM(func_fsm,
2,2)
    END_STATE(
0)
    
    BEGIN_STATE(
1,"second",0,END_STATE_ID,enter_fsm,exit_fsm)
        STATE_EVENT_ITEM(func_fsm,
1,3)
        STATE_EVENT_ITEM(func_fsm,
2,0)
    END_STATE(
1)
    
    BEGIN_STATE(
2,"third",0,3,enter_fsm,exit_fsm)
        STATE_EVENT_ITEM(func_fsm,
1,0)
        STATE_EVENT_ITEM(func_fsm,
2,1)
    END_STATE(
2)
    BEGIN_STATE(
3,"third",2,END_STATE_ID,enter_fsm,exit_fsm)
        STATE_EVENT_ITEM(func_fsm,
1,4)
        STATE_EVENT_ITEM(func_fsm,
2,1)
    END_STATE(
3)
    BEGIN_STATE(
4,"third",2,END_STATE_ID,enter_fsm,exit_fsm)
        STATE_EVENT_ITEM(func_fsm,
1,2)
        STATE_EVENT_ITEM(func_fsm,
2,1)
    END_STATE(
4)
END_FSM_STATE_TABLE(my_state_table)

FSM fsm={0,default_fsm,my_state_table};
fsm_init(fsm);
FSM_EVENT event;
event.id
=1;
event.data.i
=1;
fsm_do_event(fsm,event);



后续提纲:
三、状态机实现
(3)面向对象方式 常规&层次

四、状态机分析
五、状态机回路检测
六、状态机使用
另介绍boost中同步异步状态机

posted on 2008-01-30 12:41 cppexplore 阅读(5894) 评论(10)  编辑 收藏 引用

评论

# re: 【原创】技术系列之 状态机(二) 2009-03-26 16:10 yu
写得很好!
为什么不继续写下去啊?  回复  更多评论
  

# re: 【原创】技术系列之 状态机(二) 2009-07-06 15:46 大华
这部分内容本身就上人头大,能不能加上几张状态机的图,这样和程序结合才好吗  回复  更多评论
  

# re: 【原创】技术系列之 状态机(二)[未登录] 2009-07-06 20:33 cppexplore
@大华
莫非是浙江大华的朋友,呵呵  回复  更多评论
  

# re: 【原创】技术系列之 状态机(二) 2010-04-11 11:52 zhaojx
楼主,希望你能继续写下去啊,大牛,膜拜一下  回复  更多评论
  

# re: 【原创】技术系列之 状态机(二) 2010-05-25 13:53 种花得花
这段代码有个问题:
您在event_table中为每个event id绑定了一个回调fun,
如果该event已经产生了state的切换,那么接下来先执行了old state的exit fun,接下来才是执行该状态的fun。
也就是说执行fun的时候该状态的exit fun,甚至其parent的exit其实已经被执行了,或多或少会让使用者感到迷惑。

这样使用会否不便,或者是否有改进意见呢?  回复  更多评论
  

# re: 【原创】技术系列之 状态机(二) 2010-05-25 17:50 cppexplore
@种花得花
兄弟看的仔细啊.
如果event产生了state切换,也应该先执行对应的func, 再执行exit func啊.

不太明白你的意思. 不过我实际用的状态机的确和文章中的都差异很大,呵呵, 除了整理调试代码外,最大的修改 就是状态切换时, 不马上切换, 先将状态入队列,等func执行完, 再做实际的state切换,不知道你说的是不是这里的问题.
  回复  更多评论
  

# re: 【原创】技术系列之 状态机(二) 2010-05-25 19:18 种花得花
@cppexplore
我主要是针对这几行
for(i=0;i<old_cur;i++)
{
if(fsm.state_tables[oldStack[i]].exit_func)
fsm.state_tables[oldStack[i]].exit_func(&event); // 首先 执行exit func
}

if(match_func)
match_func(&event); // 再执行切换的event func,这里感觉有点晚了

for(i=new_cur;i>0;i--)
{
if(fsm.state_tables[newStack[i-1]].enter_func)
fsm.state_tables[newStack[i-1]].enter_func(&event); // 最后执行enter func,这个没有异义
}

我现在也在思考状态机的使用需求,如何才能让使用者使用、书写的时候更加便捷。
对于你这段代码我最拿不定的是:是否需要为每个event单独配置一个event func,我觉得为每个状态,配置一个事件回调处理函数就可以了。不知哪个在实际使用时更加方便。  回复  更多评论
  

# re: 【原创】技术系列之 状态机(二)[未登录] 2010-05-26 09:36 cppexplore
@种花得花
是错了. 应该先执行func,再执行状态迁移引起的func.

需要为每个event单独配置一个event func, 当然是这个状态对这个event感兴趣的时候, 对不感兴趣的event, 使用改状态的default_func就可以了.

如果每个状态只要一个事件回调, 那说明这个状态只对一个event感兴趣吧(或者你的多个event应该合并成一个), 这个时候基本不需要状态机,保存一个玫举的状态变量就好了, 这是我的一点看法.  回复  更多评论
  

# re: 【原创】技术系列之 状态机(二) 2014-11-01 02:31 sohu
CppExplore您好

小弟拜读了你的文章:状态机(二)
http://www.cppblog.com/CppExplore/archive/2008/01/30/42205.html

实在想不明白,忍不住给你发邮件,想请教一下

你说的这个“层次状态机”理论来自哪里呢,我仔细看了下,发现不是大多数理解的层次状态机,因为你状态机只有一个,并没有状态机和状态机间的层次切换的动作

感觉你里面的层次,是体现在”状态“的层次存储上,带来的效果应该只是enter_func和exit_func链的调用而已,对简化状态机貌似起不了太多的作用,对么

请指正

谢谢  回复  更多评论
  

# re: 【原创】技术系列之 状态机(二)[未登录] 2014-11-05 10:15 cppexplore
@sohu 你好!你说的不错,是“状态”的层次,对同一个状态机,更容易符合人的正常思维。
这个理论来自于实践吧,先考虑最终需要,再进行实现。

你提出的基于状态机的层次很不错,既然想到了这扇门,打开只是实现上的问题,这比“状态”层面的有更高抽象,简单想想,非常不错  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理