高效的、省内存的、任意格式的队列

关注「嵌入式大杂烩」，选择「星标公众号」一起进步！

1

队列类比通信

最近开启了一个新的项目，与以往的产品有点差异，存在一些技术盲区和难点，所以大部分时间都在查阅资料、仿真、交流等等，有时候吃饭都在思考设计上的一些问题~对于研发人员而言，能够接手一个新的综合性项目，不仅仅能够在其中吸收到新的技术和思路，也可以反过来思考老项目的方案和设计，最终达到技术上的整体提升。所以一个字"忙",今天好不容易抽出了一些时间,跟大家分享一个好玩的东西-“ 队列 ”~队列还要讲吗？不就是一种FIFO的数据结构吗？你说得很对，不过今天不单单讲队列，如下图所示：可以看出队列主要有两个功能: 1）用来转移数据；2）进行数据缓存。类比平时的通信过程，也主要是进行数据转移，当通信的双方可能存在处理速度、响应上的较大差异时，就需要我们构建软件上的数据缓存或者其他同步机制，当然目前一些高性能的外设都存在硬件上的FIFO。这样类比下来，平时实现的串口通信，IIC通信的等等通信过程，在软件里面进行抽象与虚拟用队列这样的数据结构就再合适不过了，玩过OS的朋友都知道，OS中一般都会提供消息队列等等这样的通信服务，也是类似的道理~2

思路

既然我们把通信与队列统一起来了,那么你还会选择一个包一个包的直接数据处理吗？类似于你直接拿着一帧串口来规定其每个bit的含义一样~有些朋友可能会说，那我把数据包定义大一点，队列的元素以struct_pack来作为整包入队，确实这样也是可行的，一般大家也是这么做的。但是如果你所传递的数据包格式、大小等等差异较大，是不是就会存在传递小数据包而浪费内存，并且降低队列传递效率的问题呢？为了设计一个队列支持多种格式的数据传递，并且能够达到较大的节省内存和提高效率，那么核心思想就是"化时间为空间"。思路回到通信上来~

不管什么通信过程，其实对于大多数的情况都是一个个的字节传递即字节流，让通信过程变得更加有意义，无非就是承载了各种各样的通信协议，那么不同的通信协议就展现出了不同的效果~

3

设计

我们来大致实现这个过程~
在资源紧张的MCU中一般会这样做，使用队列主要涉及到3个函数：入队列、出队列以及队列当前大小 :

1//入队列
2uint8_t QueueIn(uint8_t uByte);  
3
4//出队列
5uint8_t QueueOut(void);
6
7//当前队列大小
8uint8_t QueueSize(void);


指定通信协议,非常的简洁，不需要考虑丢包和重发机制。数据格式定义如下 :1数据长度1   数据区1   ... 数据长度N   数据区N
2
3byte1   |  byte2 ~ byteX | ... |byteY | byte(Y 1) ~ byteZ


参考伪代码：

1/*********************************************
2 * 队列数据包定义
3 ********************************************/
4typedef struct _tag_pack
5{
6    uint8_t len;
7    uint8_t dataBuff[MAX_DATA_LEN];
8}QueuePack;
9
10/*********************************************
11 * Function: SendPack
12 * Description:用于发送数据包的打包入队过程
13 * Author: bug菌
14 ********************************************/
15uint8_t SendPack(QueuePack * pQueuePack)
16{
17    uint8_t Cnt = 0;
18
19    //进入临界区--对于多任务系统
20    if(QueueIn(pQueuePack->len))
21    {
22        return false; //queue overflow
23    }
24
25    for(Cnt = 0;Cnt < pQueuePack->len;Cnt )
26    {
27        if(QueueIn(pQueuePack->dataBuff[Cnt]))
28        {
29            return false; //queue overflow
30        }
31    }
32    //出临界区--对于多任务系统
33    return return; //queue success
34}
35/*********************************************
36 * Function: RevPack
37 * Description:由于接受队列数据包解析过程
38 * Author: bug菌
39 ********************************************/
40uint8_t RevPack(QueuePack * pQueuePack)
41{
42    uint8_t Cnt = 0;
43
44    //进入临界区--对于多任务系统
45    if(QueueSize() < MIN_LEN) return false;
46        pQueuePack->len = QueueOut();
47
48    for(Cnt = 0;Cnt < pQueuePack->len;Cnt )
49    {
50        if(QueueSize() < MIN_LEN)return false; //queue empty
51        pQueuePack->dataBuff[Cnt] = QueueOut();
52    }
53    //出临界区--对于多任务系统
54    return return; //queue success
55}


这样我们就可以发送不同格式的数据包，并且在接收端进行解析获得最终的数据区。接受到数据区域以后，比如数据区的第一个字节表示数据包类型，接受端即可识别对应的数据类型来使用~其实还有很多软件上的处理都是类比的处理办法，一旦你把它们统一起来就非常容易了~
最后再小提一下临界区的事，对于多任务系统，由于不同任务的出入队需要对打包过程进行互斥，这样每个包才具有完整性~最后

    如果觉得本文不错的话，一定要记得跟bug菌点个赞再走哦~

往期干货：

往期推荐

实用 | 10分钟教你搭建一个嵌入式web服务器

RT-Thread和Freertos的区别？

程序如何运行？编译、链接、装入？

串口通信 | 简单明了的基础知识

一种无OS的MCU实用软件框架