C语言实现有限状态机

时间：2024-11-13 15:58:18

1. 什么是有限状态机

有限状态机在百度百科上的解释为：
有限状态自动机（FSM “finite state machine” 或者FSA “finite state automaton” ）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。

2. 有限状态机的应用场景

在实际工作中，经常遇到状态机的应用，尤其在网络协议部分，最为经典的就是TCP协议的状态机：
在这里插入图片描述
实际上，很多网络协议都是有工作状态的，不同阶段所处不同的状态，例如DHCP协议，路由协议，SIP协议等等。这些协议在实现的时候多多少少会用到状态机的原理，可能在实现上有较大的差别。我原来只是听说过有这个原理，但只限于听说，但具体实现以及它的优点更是不知所以；
这几天在学习BFD协议的时候，BFD的内核部分就是使用状态机来实现的，这就使我花点时间好好了解下状态机实现的原理，这篇博客主要介绍状态机的最简单实现，因为网上没有找到想要的实现，所以决定自己写几个实例并记录下来。
这几个实例是参照/zqixiao_09/article/details/50239337的栗子做的，只是这篇文章全是使用的switch-case实现的，所以我做一个补充，使用另一种更符合状态机的实现。
不是说有些问题必须使用状态机，只是使用状态机可以简化问题，代码的逻辑也比较清晰

3.状态机的基本框架

3.1 定义状态

如果要使用状态机进行解决问题，首先要确定这个问题本事有几个状态，然后我们把所用的状态做一个枚举类型的定义，问什么是枚举类型呢？ 因为我们定义==状态的目的就是把状态当作索引值==，这可以说是状态机实现的精髓了，因为它就是根据当前的状态来确定下一步的行为。
例如：一个问题有三种状态，则可以使用这样的定义：

enum {
	STATE_0 = 0,   /* 数据下标从0开始，因此开始设置为0，后边逐渐递增*/
	STATE_1,
	STATE_2,
}FSM_STATE;

3.2定义事件

定义事件，这个不是必须的。 我是参照BFD内核源码的状态机实现来做实现的几个栗子，定义事件的好处就是可以统一处理各种情况，不需要再每个状态中再单独判断，这样需要花费更长的时间去实现每个状态中的函数。
事件是与状态相对应的，简单的说，从“状态0”切换到“状态1”是由某些特定事件导致的，同理从“状态1”切换到“状态2”是由另一个事件导致的。 我们把引起状态切换的条件称为事件。
再举个栗子：
TCP服务器再收到客户端发来的SYN报文后，做出SYN+Ack的应答，我们就可以把==“收到SYN”称作一个事件==。
确定好事件后，我们将也定义一个事件的枚举类型，因为事件的作用就是作为另一个索引。
例如：一个问题有三个事件，则可以使用这样的定义：

enum {
	EVENT_NOT_SPACE=0,  /*数据下标索引，从0开始*/
	EVENT_SPACE,
	EVENT_STR,
}FSM_EVENTS;

3.3定义状态机的结构体

因为我们已经知道状态机是有状态和事件构成的，因此状态机的结构体可以定义为 “动作”+“下一状态”。
例如：

struct FSM_node{
	void (*func)(char *); /*当前状态下，发生某个事件所采取的措施*/
	int next_state;		  /*这个事件发生后，要切换的状态*/
};

当然这只是个结构体，而真实的状态机一般定义为一个二维的数组，为什么是二维的？ 从上文已经知道“状态”+“事件”是同时作为索引值，因此这里定义为二维的变量也是可以理解的。
栗子中定义的状态机变量如下：

struct {
	int (*func)(char *);
	int next_state;
}FSM[STATE_NUM][EVENT_NUM]=
{
	{/*current state isNotSpace ： 状态0*/
		{isNotSpace_func1,STATE_0}, /*NOT_SPACE：状态0时遇到一个非空格，打印 + 下一状态为状态0*/
		{isNotSpace_func2,STATE_1}, /*IS_SPACE*：状态0时遇到一个空格，打印 + 下一状态为状态1 */
	},
	{/*current state isSpace ： 状态1*/
		{isSpace_func1, STATE_0},	  /*NOT_SPACE：状态1时遇到一个非空格，打印 + 下一状态为状态0*/
		{isSpace_func2, STATE_1},	  /*IS_SPACE：状态1时遇到一个空格，不打印 + 下一状态为状态1*/
	},
};

完整代码在第一个实例中。
FSM就是个二维数组，只不过它存储的是一个结构体；我们是在它定义的时候进行的初始化。
理论上，每一种状态下，所有的事件都有可能发生，所以每一种状态下，我们定义了（事件种类EVENT_NUM）个对象。

3.4 画状态变迁图

状态变迁图与流程图比较类似，只不过它突出是的状态和事件。画状态变迁图是为了开发方便，思路更加清晰。
画状态变迁图的好处是方便定义状态机：每一个状态下发生不同的事件分别该如何处理以及下一状态是什么。
我们再具体实例中说明。

4实例

4.1实例一

问题：除去一个字符串中连续的空格，只保留一个。
状态变迁图：
在这里插入图片描述
在这里插入图片描述
代码实现

#include <>
typedef enum{
	STATE_0 = 0,
	STATE_1,
}state;
typedef enum{
	NOT_SPACE= 0,
	IS_SPACE,
}events;

#define STATE_NUM 2
#define DEVENT_NUM 2
int isNotSpace_func1(char *str)
{
	putchar(*str);
}
int isNotSpace_func2(char *str)
{
	putchar(*str);
}
int isSpace_func1(char *str)
{
	putchar(*str);
}
int isSpace_func2(char *str)
{
	; /*do nothing*/
}
struct {
	int (*func)(char *);
	int next_state;
}FSM[STATE_NUM][DEVENT_NUM]=
{
	{/*current state isNotSpace*/
		{isNotSpace_func1,STATE_0}, /*NOT_SPACE*/
		{isNotSpace_func2,STATE_1}, /*IS_SPACE*/
	},
	{/*current state isSpace ： 状态1*/
		{isSpace_func1, STATE_0},	  /*NOT_SPACE*/
		{isSpace_func2, STATE_1},	  /*IS_SPACE*/
	},
};
/*根据当前状态和当前事件做索引，找到对应的处理情况；然后再获取下一状态*/
void demo1()
{
	char str[] = "h    e    l    l     o,                    w   o   r    l   d;";
	char *p = str;
	int state_now = STATE_0;
	int _event, ret;
	while(*p){
		if(*p==' ')
			_event = IS_SPACE;
		else 
			_event = NOT_SPACE;
		/* FSM[state_now][_event]: 节点对象*/
		/* (FSM[state_now][_event]).func : 该对象函数指针*/
		/* *((FSM[state_now][_event]).func) : 获取到函数指针指向的函数*/
		ret = (*((FSM[state_now][_event]).func))(p);    
		state_now = (FSM[state_now][_event]).next_state;
		p++;
	}	
}

结果：

root# ./a.out
root# h e l l o, w o r l d;

4.2实例二

问题：除去一个字符串中连续的空格，只保留一个，但保留双引号(“ ”)内的所有字符。
状态变迁图：
在这里插入图片描述
代码实现

#include <>
enum {
	STATE_0 = 0,
	STATE_1,
	STATE_2,
}FSM_STATE;
enum {
	EVENT_NOT_SPACE=0,
	EVENT_SPACE,
	EVENT_STR,
}FSM_EVENTS;
#define STATE_NUM 3
#define EVENT_NUM 3
void func1(char *str)
{
	putchar(*str);
}
void func2(char *str)
{
	putchar(*str);
}
void func3(char *str)
{
	putchar(*str);
}
void func4(char *str)
{
	putchar(*str);
}
void func5(char *str)
{
	;
}
void func6(char *str)
{
	putchar(*str);
}
void func7(char *str)
{
	putchar(*str);
}
void func8(char *str)
{
	putchar(*str);
}
void func9(char *str)
{
	putchar(*str);
}
struct {
	void (*func)(char *);
	int next_state;
}FSM_test2[STATE_NUM][EVENT_NUM]=
{
	{//state_0 not space
		{func1, STATE_0},
		{func2, STATE_1},
		{func3, STATE_2},
	},
	{//state_1 space
		{func4, STATE_0},
		{func5, STATE_1},
		{func6, STATE_2},

	},
	{//state_2 ""
		{func7, STATE_2},  /* when first " is reached, the state is always STATE_2, only when the next " reached, next state is STATE_0*/
		{func8, STATE_2},
		{func9, STATE_0},
	},
};

void demo2()
{
	char str[] = "h   e    l   l   o  ,\"today       is     friday   !!!\"   w  o  r  l  d  .";
	char *p = str;
	int ret;
	int state = STATE_0;
	int event;
	while(*p){
		if(*p==' ')
			event = EVENT_SPACE;
		else if(*p=='"')
			event = EVENT_STR;
		else
			event = EVENT_NOT_SPACE;
		//printf("\n-----state=%d-----event=%d------\n",state, event);
		(*(FSM_test2[state][event].func))(p);
		state = FSM_test2[state][event].next_state;
		p++;
	}
	putchar(10);
}

结果：

root# ./a.out
root# h e l l o ,"today       is     friday   !!!" w o r l d .

定义了很多同样的实现函数，只是为了说明每一种(状态，事件)都有各自的处理情景，这个栗子只是巧合

5结束

状态机的C语言基本实现框架就是这样，后续如果有经典的状态机实现，做更新处理。

相关文章