一、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）

struct list_head {
	struct list_head *next, *prev;
};

三、list_head使用

1、API函数

1）创建链表

内核提供了以下API来初始化list_head：

/* 方法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。

static 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。

static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

c. list_add_tail

该函数用于在链表末尾@tail节点后面插入一个新的节点@new。

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

3）删除节点

a. list_del

该函数用于删除位于链表中的指定的节点。

static 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功能是实现对变量的一次性写入。

#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、参考资料

1. 以上源码内容参考自：Linux-4.15.18

最后

以上就是鲤鱼发卡为你收集整理的list_head一、list_head介绍二、list_head实现三、list_head使用附录的全部内容，希望文章能够帮你解决list_head一、list_head介绍二、list_head实现三、list_head使用附录所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。