1、介绍

在数据结构和算法一文中经常就信手拈来一些基本数据结构和算法，如链表、队列、栈、二叉树等等，但是在C的标准库中并没有自带这些，C++通过STL、类程序库等等会带这些，那么在嵌入式开发里面怎么快速方便使用这些数据结构和算法咧？答案就是从Linux内核或者模块程序里去学习这些算法，Linux里面的实现是经过了千锤百炼的，在标准化、复杂度和效率上应该比一般人写的好得多，所以先去学习下大神们的代码，再通过总结来实现自己的一套，后面在一些非Linux系统的程序中就可以直接使用这些轮子了。本文总结记录嵌入式C里面经常要用到的数据结构和算法。这些算法的参考链接为：

https://linux.cn/article-2317-1.html        各种算法链接

内核队列实现：https://blog.csdn.net/yusiguyuan/article/details/19905427 

环形队列的ABA问题：https://www.cnblogs.com/shines77/p/4200127.html

无锁环形队列实现：https://www.cnblogs.com/lvdongjie/p/9679265.html，https://github.com/dodng/fast_ring_queue

ringbuffer实现：https://github.com/XinLiGH/RingBuffer/tree/master/RingBuffer/RingBuffer

CAS：https://blog.csdn.net/stpeace/article/details/81150393

锁与共享变量：https://blog.csdn.net/yanluandai1985/article/details/82686486

       要建立一个真正无锁的数据结构来操作需要借助于系统的CAS操作， CAS是compare and swap,   简单来说就是，在写入新值之前， 读出旧值， 当且仅当旧值与存储中的当前值一致时，才把新值写入存储。__sync_bool_compare_and_swap是可供程序员调用的接口。

      加锁是一种悲观的策略，它总是认为每次访问共享资源的时候，总会发生冲突，所以宁愿牺牲性能（时间）来保证数据安全。无锁是一种乐观的策略，它假设线程访问共享资源不会发生冲突，所以不需要加锁，因此线程将不断执行，不需要停止。一旦碰到冲突，就重试当前操作直到没有冲突为止。无锁的策略使用一种叫做比较交换的技术（CAS Compare And Swap）来鉴别线程冲突，一旦检测到冲突产生，就重试当前操作直到没有冲突为止。

CAS核心算法：执行函数：CAS(V，E，N)   

V表示准备要被更新的变量       

E表示我们提供的 期望的值

N表示新值 ，准备更新V的值

由于CAS操作属于乐观派，它总是认为自己能够操作成功，所以操作失败的线程将会再次发起操作，而不是被OS挂起。所以说，即使CAS操作没有使用同步锁，其它线程也能够知道对共享变量的影响。

        因为其它线程没有被挂起，并且将会再次发起修改尝试，所以无锁操作即CAS操作天生免疫死锁。

        另外一点需要知道的是，CAS是系统原语，CAS操作是一条CPU的原子指令，所以不会有线程安全问题。
 

2、无锁环形队列

内核中关于队列定义的头文件位于：<linux/kfifo.h> include/linux/kfifo.h，头文件中定义的函数的实现位于：kernel/kfifo.c，

内核队列编程需要注意的是：

• 队列的size在初始化时，始终设定为2的n次方
• 使用队列之前将队列结构体中的锁(spinlock)释放

kfifo 是内核里面的一个First In First Out数据结构，它采用环形循环队列的数据结构来实现；它提供一个无边界的字节流服务，最重要的一点是，它使用并行无锁编程技术，即当它用于只有一个入队线程和一个出队线程的场情时，两个线程可以并发操作，而不需要任何加锁行为，就可以保证kfifo的线程安全。

采用数组实现无锁环形队列没有ABA问题，用链表实现会有ABA问题。

2.1 环形队列适用场景

一般应用于需要高效且频繁进行多线程通信传递数据的场景，例如：linux捕包、发包等等，（linux系统中对PACKET_RX_RING和PACKET_TX_RING的支持实质就是内核实现的一种环形队列）。

2.2 ringbuffer原理

链表和线性表都是可以的，但几乎都用线性表实现，比链表快很多，原因也是显而易见的，因为访问链表需要挨个遍历。

　上面定义的是一个容量(Capacity)为8的RingBuffer，一般RingBuffer的容量取为2的N次幂，这样计算索引时可以使用 index = sequence & mask; (其中mask = capacity - 1;) 以提高代码效率。其中索引表示数组的下标，数组中保存的数据是A, B, C, D, Empty等。Head 表示队列的头指针（即首个可以压入数据的位置），Tail 表示队列的尾指针（即首个可以弹出数据的位置），Head、Tail都是以序号的形式存在，且是单调递增的，且可以大于等于Capacity(8)，如果Head = 8 时表示数组的第一个元素（因为回转回来了，即 index = 8 & (8 - 1) = 8 & 7 = 0;），Head = 9 表示的其实是存储在数组的第二个元素。

队列内元素的实际长度为：Length = Head - Tail，其中 (Head - Tail) 必须 <= Capacity(最大容量)，因为这个时候表示队列已经满了，如果(Head - Tail) = 0，则代表队列为空。为什么叫 RingBuffer，就是因为它是一个环，游标到了数组的尾部又回转到数组的头部。

判断队列是否已满的逻辑为：队列实际长度 >= 队列最大容量，即：if ((head - tail) >= capacity) return -1; 由于 mask = capacity - 1，还可以简化为：if ((head - tail) > mask) return -1; 。

2.3 代码实现

3、栈