文章目录
- 一、list_head介绍
- 1、list_head简介
- 2、list_head结构
- 二、list_head实现
- 1、list_head数据结构
- 1）struct list_head
- 三、list_head使用
- 1、API函数
- 1）创建链表
- 2）添加节点
- a. __list_add
- b. list_add
- c. list_add_tail
- 3）删除节点
- a. list_del
- ...
- 附录
- 1、list_head疑问
- 2、参考资料
一、list_head介绍
1、list_head简介
list_head是linux内核中最经典的数据结构之一，被广泛应用于各类数据结构的管理和维护中。list_head本质上是一个双向链表。
2、list_head结构
以下是工作队列中struct work_struct采用list_head的结构示意图：
二、list_head实现
list_head相关的代码实现主要在kernel/include/linux/list.h中。
1、list_head数据结构
1）struct list_head
该结构体本质上就是一个双向链表。（kernel/include/linux/types.h）
复制代码
1
2
3
4struct list_head { struct list_head *next, *prev; };
三、list_head使用
1、API函数
| 函数 | 功能 |
|---|---|
LIST_HEAD | 声明并初始化双向链表。 |
INIT_LIST_HEAD | 初始化双向链表。 |
list_add | 在链表头@head节点后面插入一个新的节点@new。 |
list_add_tail | 在链表末尾@tail节点后面插入一个新的节点@new。 |
list_del | 删除链表中指定的节点，并对删除节点成员置NULL。 |
list_del_init | 删除链表中指定的节点，并对删除节点重新初始化。 |
list_for_each | 正向遍历链表中每个成员。 |
list_for_each_prev | 反向遍历链表中每个成员。 |
list_entry | 通过type结构体成员member的地址ptr得到member所在type结构体的首地址。 |
list_for_each_entry | 通过遍历链表得到member所在的type结构体的首地址。 |
list_replace_init | 将链表中@old节点替换为@new节点，并对@old节点重新初始化。 |
list_move | 将一个节点从一个链表中移动到另一个链表头@head节点后面。 |
list_move_tail | 将一个节点从一个链表中移动到另一个链表末尾@tail节点后面 |
list_empty | 测试某个节点所在的链表是否为空。 |
| … | … |
1）创建链表
内核提供了以下API来初始化list_head：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12/* 方法1.使用宏进行list_head的声明和初始化操作。 */ #define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name) /* 方法2.使用函数对已声明的list_head进行初始化操作。 */ static inline void INIT_LIST_HEAD(struct list_head *list) { WRITE_ONCE(list->next, list); list->prev = list; }
问题1： WRITE_ONCE的作用是什么？为什么只在list->next赋值的时候使用，而没有在list->prev赋值的时候同时使用？？？（参见附录）
2）添加节点
a. __list_add
该函数用于在@prev和@next之间插入新的节点@new。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { /* * @__list_add_valid: menuconfig配置了CONFIG_DEBUG_LIST后会启动该项检查 * 1.检查 @prev和 @next节点是否互为前后节点关系。 * 2.检查新插入的节点 @new是否就是 @prev或 @next成员，避免重复插入。 */ if (!__list_add_valid(new, prev, next)) return; next->prev = new; new->next = next; new->prev = prev; WRITE_ONCE(prev->next, new); }
b. list_add
该函数用于在链表头@head节点后面插入一个新的节点@new。
复制代码
1
2
3
4
5static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); }
c. list_add_tail
该函数用于在链表末尾@tail节点后面插入一个新的节点@new。
复制代码
1
2
3
4
5static inline void list_add_tail(struct list_head *new, struct list_head *head) { __list_add(new, head->prev, head); }
3）删除节点
a. list_del
该函数用于删除位于链表中的指定的节点。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26static inline void __list_del(struct list_head * prev, struct list_head * next) { next->prev = prev; WRITE_ONCE(prev->next, next); } static inline void __list_del_entry(struct list_head *entry) { /* * @__list_del_entry_valid: menuconfig配置了CONFIG_DEBUG_LIST后会启动该项检查 * 1.检查待删除节点指向的 @prev和 @next是否为NULL。 * 2.检查待删除节点的 @prev->next和 @netx->prev是否指向待删除节点。 */ if (!__list_del_entry_valid(entry)) return; __list_del(entry->prev, entry->next); } static inline void list_del(struct list_head *entry) { __list_del_entry(entry); entry->next = LIST_POISON1; // NULL entry->prev = LIST_POISON2; // NULL }
…
PS： 其它API原理和上述一致，不再具体分析。
附录
1、list_head疑问
Q1： WRITE_ONCE的作用是什么？为什么只在list->next赋值的时候使用，而没有在list->prev赋值的时候同时使用？？
A1: WRITE_ONCE功能是实现对变量的一次性写入。
复制代码
1
2
3
4
5
6
7
8#define WRITE_ONCE(x, val) ({ union { typeof(x) __val; char __c[1]; } __u = { .__val = (__force typeof(x)) (val) }; __write_once_size(&(x), __u.__c, sizeof(x)); __u.__val; })
2、参考资料
- 以上源码内容参考自：Linux-4.15.18
最后
以上就是鲤鱼发卡最近收集整理的关于list_head一、list_head介绍二、list_head实现三、list_head使用附录的全部内容，更多相关list_head一、list_head介绍二、list_head实现三、list_head使用附录内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复