一个循环队列帧完整性匹配算法

2014年4月27日 由 Creater 留言 »

今天早上思考了下关于循环队列中帧匹配的问题,以前在其他项目中,都是用了两个线程的单生产者-单消费者模式,但是有一定的弊端,那就是效率相对来说不是太高,而且线程同步也相对复杂。以下是今天早上思考的结论,算法时间复杂度O(n),而且上锁,解锁的次数大幅度降低。

看似一段简单的代码,个人觉得还是比较有技巧的,重点在于每次读取两个字节,而只处理一个字节。以帧头FB,FD,帧尾为FC,FE(都为16进制)为例,通过调整参数door,越大则及时性不足,越小则消耗更多时间。




const int FRAME_LENGTH = 11;
const char HEAD_FIRST = 0xfb;
const char HEAD_SECOND = 0xfd;
const char TAIL_FIRST = 0xfc;
const char TAIL_SECOND = 0xfe;
const int DOOR = FRAME_LENGTH ;
void run()
{
	bool bstart;
	int cnt;
	char tmp[9];
	char buff[2];
	while(true)
	{
		mutex.lock();
		while(cir.size() <= DOOR )
			con.wait(&mutex);

		if(!bstart)
		{
			while(true)
			{
				if(cir.size() < 2) continue;
				cir.get(buff, 2);
				if(!(buff[0] ^ HEAD_FIRST) && !(buff[1] ^ HEAD_SECOND))
				{
					bstart = true;
					cnt = 0;
					cir.remove(2);
					break;
				}
				else					
					cir.remove(1);
			}
		}
		else
		{
			while(true)
			{
				if(cir.size() < 2) continue;
				cir.get(buff,2);
				if(!(buff[0] ^ TAIL_FIRST) && !(buff[1] ^ TAIL_SECOND))
				{
					/*至此,检索到一个完整的有效数据序列,并保存在tmp中*/
					bstart = false;
					cnt = 0;
					cir.remove(2);
					break;
				}
				else
				{
					cir.remove(1);
					tmp[cnt++] = buff[0];
				}

			}
		}
		mutex.unlock();
				
	}


}
广告位

评论已关闭.