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)

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

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

正文完