TencentOS-tiny中双向循环链表的实现及使用
原创TencentOS-tiny中双向循环链表的实现及使用
原创
1. 什么是双向循环链表
双向链表也是链表的一种，区别在于每个节点除了后继指针外，还有一个前驱指针，双向链表的节点长下面这样：
由这种节点构成的双向链表有两种分类：按照是否有头结点可以分为两种，按照是否循环可以分为两种。
本文讨论的是不带头节点的双向循环链表，如下图：
2. 双向循环链表的实现
TencentOS-tiny中的双向链表实现在tos_list.h中。
2.1. 节点实现
节点数据结构的实现如下：
typedef struct k_list_node_st {
struct k_list_node_st *next;
struct k_list_node_st *prev;
} k_list_t;2.2. 双向链表初始化
链表初始化的实现如下：
void tos_list_init(k_list_t *list)
{
list->next = list;
list->prev = list;
}其中传入的list参数是指向双向链表的头指针，初始化之后，如图：
2.3. 插入节点
向双向链表中插入一个节点非常简单：
void _list_add(k_list_t *node, k_list_t *prev, k_list_t *next)
{
next->prev = node;
node->next = next;
node->prev = prev;
prev->next = node;
}其中node是待插入的节点，prev是插入节点位置的前一个节点，next是插入节点位置的后一个节点，插入过程如下。
插入前的双向循环链表如下：
插入后的双向循环链表如下：
图中的四个插入过程分别对应代码中的四行代码。
除了这个基本的API之外，tencentOS-tiny还提供了两个插入的API，分别是头部插入和尾部插入：
void tos_list_add(k_list_t *node, k_list_t *list)
{
_list_add(node, list, list->next);
}
void tos_list_add_tail(k_list_t *node, k_list_t *list)
{
_list_add(node, list->prev, list);
}因为是双向循环链表，所以尾部插入是在第一个节点和最后一个节点之间插入。
2.4. 删除节点
同样，删除节点的操作也比较简单，把钩子断开即可：
void _list_del(k_list_t *prev, k_list_t *next)
{
next->prev = prev;
prev->next = next;
}
void _list_del_node(k_list_t *node)
{
_list_del(node->prev, node->next);
}删除过程如图所示，同样，编号对应源码中的两行代码：
2.6. 判断链表是否为空
判断链表第一个节点是否指向自己即可：
int tos_list_empty(const k_list_t *list)
{
return list->next == list;
}3. 双向链表使用示例
3.1. 实验内容
本实验会创建一个带有10个静态结点的双向链表，每个新的自定义节点中有一个数据域，存放一个uint8_t类型的值，有一个双向链表节点，用于构成双向链表。
3.2. 实验代码
首先包含内核头文件：
/**
* @brief TencentOS-tiny双向链表测试
* @author Mculover666
* @date 2020/6/2
*/
#include <tos_k.h>创建一个自己的新节点：
typedef struct node
{
uint8_t data;
k_list_t list;
}node_t;
新建一个任务用来测试，编写如下的任务入口函数：
#define LIST_LEN 10
void double_list_test(void *args)
{
int i;
/* 用于挂载自定义节点中的双向节点 */
k_list_t list;
/* 创建10个链表节点 */
node_t node_pool[LIST_LEN];
/* 遍历，初始化自定义节点的数据域和双向节点 */
tos_list_init(&list);
for(i = 0;i < LIST_LEN;i++)
{
tos_list_init(&node_pool[i].list);
node_pool[i].data = i;
}
/* 构建一条具有LIST_LEN个节点的双向链表 */
for(i = 0; i < LIST_LEN;i++)
{
tos_list_add_tail(&node_pool[i].list, &list);
}
/* 遍历打印所有节点 */
k_list_t *cur;
node_t *n;
//for(cur = list.next;cur != &list;cur = cur->next)
TOS_LIST_FOR_EACH(cur, &list)
{
n = TOS_LIST_ENTRY(cur, node_t, list);
printf("n = %d\n", n->data);
}
return;
}构建完成之后链表如图（只画了3个有数据的节点）：
遍历整条链表的时候，使用了tencentOS-tiny中提供的宏定义 TOS_LIST_FOR_EACH，它的定义如下：
#define TOS_LIST_FOR_EACH(curr, list) \
for (curr = (list)->next; curr != (list); curr = curr->next)注意，此宏定义是从传入地址的下一个节点开始遍历！
还有最后一个使用问题，我们都是对整条链表进行操作（比如可以轻松的遍历整条链表），操作的时候得到的地址都是node_t类型节点中k_list_t类型成员的地址，那么如何访问到data成员呢？
TencentOS-tiny中依然提供了两个宏定义来解决这一问题，在tos_klib.h中。
① 计算某一个成员在结构体基地址中的偏移地址：
#define TOS_OFFSET_OF_FIELD(type, field) \
((uint32_t)&(((type *)0)->field))② 已知某一个成员的地址，计算结构体的基地址：
#define TOS_CONTAINER_OF_FIELD(ptr, type, field) \
((type *)((uint8_t *)(ptr) - TOS_OFFSET_OF_FIELD(type, field)))这两个宏定义的实现属实有点骚，其中的巧妙之处可以再写一篇文章讲解了哈哈，此处我们先了解其使用即可（此处要感谢戴大神的解答）。
有了这两个宏定义，就有了实验中所使用的宏定义，用来获取结构体（node_t类型节点）的基地址：
#define TOS_LIST_ENTRY(node, type, field) \
TOS_CONTAINER_OF_FIELD(node, type, field)获取到结构体的基地址，还愁访问不到其中的任何一个成员吗？
最后的实验结果，你应该能猜到了，上图：
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。