TencentOS-tiny中双向循环链表的实现及使用

1. 什么是双向循环链表

双向链表也是链表的一种，区别在于每个节点除了后继指针外，还有一个前驱指针，双向链表的节点长下面这样：

由这种节点构成的双向链表有两种分类：按照是否有头结点可以分为两种，按照是否循环可以分为两种。

本文讨论的是不带头节点的双向循环链表，如下图：

2. 双向循环链表的实现

TencentOS-tiny中的双向链表实现在tos_list.h中。

2.1. 节点实现

节点数据结构的实现如下：

2.2. 双向链表初始化

链表初始化的实现如下：

其中传入的list参数是指向双向链表的头指针，初始化之后，如图：

2.3. 插入节点

向双向链表中插入一个节点非常简单：

其中node是待插入的节点，prev是插入节点位置的前一个节点，next是插入节点位置的后一个节点，插入过程如下。

插入前的双向循环链表如下：

插入后的双向循环链表如下：

图中的四个插入过程分别对应代码中的四行代码。

除了这个基本的API之外，tencentOS-tiny还提供了两个插入的API，分别是头部插入和尾部插入：

因为是双向循环链表，所以尾部插入是在第一个节点和最后一个节点之间插入。

2.4. 删除节点

同样，删除节点的操作也比较简单，把钩子断开即可：

删除过程如图所示，同样，编号对应源码中的两行代码：

2.6. 判断链表是否为空

判断链表第一个节点是否指向自己即可：

3. 双向链表使用示例

3.1. 实验内容

本实验会创建一个带有10个静态结点的双向链表，每个新的自定义节点中有一个数据域，存放一个uint8_t类型的值，有一个双向链表节点，用于构成双向链表。

3.2. 实验代码

首先包含内核头文件：

创建一个自己的新节点：

新建一个任务用来测试，编写如下的任务入口函数：

构建完成之后链表如图（只画了3个有数据的节点）：

遍历整条链表的时候，使用了tencentOS-tiny中提供的宏定义 TOS_LIST_FOR_EACH，它的定义如下：

注意，此宏定义是从传入地址的下一个节点开始遍历！

还有最后一个使用问题，我们都是对整条链表进行操作（比如可以轻松的遍历整条链表），操作的时候得到的地址都是node_t类型节点中k_list_t类型成员的地址，那么如何访问到data成员呢？

TencentOS-tiny中依然提供了两个宏定义来解决这一问题，在tos_klib.h中。

① 计算某一个成员在结构体基地址中的偏移地址：

② 已知某一个成员的地址，计算结构体的基地址：

这两个宏定义的实现属实有点骚，其中的巧妙之处可以再写一篇文章讲解了哈哈，此处我们先了解其使用即可（此处要感谢戴大神的解答）。

有了这两个宏定义，就有了实验中所使用的宏定义，用来获取结构体（node_t类型节点）的基地址：

获取到结构体的基地址，还愁访问不到其中的任何一个成员吗？

最后的实验结果，你应该能猜到了，上图：