【数据结构】链表（3）：Linux 的内核链表

丝 · 2025-1-3 11:45:03

Linux 内核链表是一种高效、灵活的双向循环链表实现，广泛用于内核开辟中（如进程调理、设备驱动、文件体系等）。它基于 C 语言的宏和结构体嵌套实现，并提供了一组通用的接口函数，使得链表操纵高效且安全。
内核链表

vim /usr/src/linux-headers-5.4.0-150-generic/include/linux/list.h
vim /usr/src/linux-headers-5.4.0-150-generic/include/linux/types.h
本质：就是双向循环链表
struct list_head{
struct list_head *next,*prev;
};

复制代码

这是Linux 内核链表的核心设计，由一个大结构体嵌套着一个小的结构体。拆解：

核心数据结构：list_head

Linux 内核链表的基础是一个通用结构体 list_head，用于表现节点之间的链接关系。

struct list_head {
struct list_head *next; // 指向下一个节点
struct list_head *prev; // 指向前一个节点
};
// 每个链表节点都有一个 list_head 类型的成员，用于链接前后节点。
// 通过这种方式实现了双向循环链表。

复制代码

链表头

链表的头节点也是一个 list_head 结构体，但它不存储数据，仅用于标志链表的起点和止境。

假如链表为空，head->next 和 head->prev 都指向自己。

1> 内核链表的初始化操纵

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
1>第一种初始化
struct list_head name = LIST_HEAD_INIT(name)
struct list_head name = { &(name), &(name) }
/*自己指向自己*/
struct list_head *next = &(name);
struct list_head *prev = &(name);
2>第二种初始化
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
/*inline ：内联函数，可以写在头文件，当调用时，直接将函数中的内容拷贝过去
简单特性，如果你的函数中有复杂的运算和循环结构，inline修饰的函数会退化成普通函数
*/
WRITE_ONCE ：本质与volatile一致
1>声明这个变量很重要，不要把它当成普通变量处理，做出错误的优化
2>保证cpu每次都从内存中读取数据，而不是直接向寄存器取值

复制代码

2> 内核链表的插入操纵

static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
解说：
汤姆(prev) 杰瑞(new) 白猫(next)
new会插在prev和next之间
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
解说： new会插在head和head->next之间，实现头插
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
解说：new会插在head->prev和head之间，实现尾插

复制代码

3> 内核链表的删除操纵

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
解说：使prev和next连接起来
static inline void __list_del_entry(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
}
解说：entry->prev和entry->next连接起来了
entry剪切出去了
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
#define LIST_POISON1 ((void *) 0x00100100 + 0)
#define LIST_POISON2 ((void *) 0x00200200 + 0)
NULL ===》 0x00000000 ~ 0x08048000
解说：将entry剪切出去，为了安全使两个指针域指向NULL
static inline void list_del_init(struct list_head *entry)
{
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
}
解说：将entry剪切出去，为了安全使两个指针域指向自己

复制代码

4> 内核链表的更换操纵

static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
解说：new结点取代old结点
static inline void list_replace_init(struct list_head *old,
struct list_head *new)
{
list_replace(old, new);
INIT_LIST_HEAD(old); //初始化，自己指向自己
}
解说：new结点取代old结点，让old结点的prev和next指向自己

复制代码

5> 内核链表的移动操纵

static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del_entry(list);
list_add(list, head);
}
解说：将list剪切出来
进行头插
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
{
__list_del_entry(list);
list_add_tail(list, head);
}
解说：将list剪切出来
进行尾插

复制代码

6> 内核链表的遍历操纵

/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
分析：
功能：通过小结构体的地址得到大结构体的地址
ptr : 小结构体的地址
type : 大结构体的类型
member: 大结构体中小结构体的名字
container_of(ptr, type, member)
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
container_of做以下两个操作：
操作一：//(保存小结构体的地址)
1> ((type *)0)->member ==》list(指向大结构体的小结构体成员)
2>typeof() --> 取类型
例子: typeof(10) --> int
3>typeof( ((type *)0)->member ) ==> typeof( list )
===>struct list_head
const struct list_head *__mptr = (ptr);
操作二://(求出大结构体的地址)
(type *)( (char *)__mptr - offsetof(type,member) );
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
( (char *)__mptr - ((size_t) &((TYPE *)0)->MEMBER );
(char *)__mptr ：对小结构体的地址进行char *转，让其地址偏移量为1字节
((size_t) &((TYPE *)0)->MEMBER ：//计算小结构体到大结构体的偏移量
(size_t) == int
&((TYPE *)0)->MEMBER ：
(TYPE *)0 ：指向大结构体的地址0x00000000
((TYPE *)0)->MEMBER ： list
&list //偏移量的体现

复制代码

#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
解说：
pos：用于循环的中间变量，类似与for循环中i(小结构指针)
head ：头结点的小结构指针类型
正序遍历
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
解说：
pos：用于循环的中间变量，类似与for循环中i(小结构指针)
head ：头结点的小结构指针类型
逆序遍历
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
解说：
pos：用于循环的中间变量，类似于for的i(大结构指针)
head：头结点的小结构体指针类型
member：大结构体中小结构体的名字
正序遍历
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.prev, typeof(*pos), member))
解说：
pos：用于循环的中间变量，类似于for的i(大结构指针)
head：头结点的小结构体指针类型
member：大结构体中小结构体的名字
逆序遍历

复制代码

7> 内核链表的删除函数

void link_del(link_t *p,datatype data)
{
link_t *pos = NULL; //类似for循环的i
link_t *node = NULL;
//1>遍历链表
/*#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))*/
list_for_each_entry(pos, &p->list, list)
{
//数据对比
if(pos->data == data)
{
//中间变量
node = pos;
//超秀操作获得要删除结点前一个结点的地址
pos = list_entry(pos->list.prev, typeof(*pos), list);
//删除与释放
list_del_init(&node->list);
free(node);
}
}
}

复制代码

8> 内核链表的更换操纵

void link_replace(link_t *p,datatype old,datatype new)
{
link_t *pos = NULL; //类似for循环的i
link_t *new_node = NULL; //类似for循环的i
//1>遍历
list_for_each_entry(pos, &p->list, list)
{
//数据对比
if(pos->data == old)
{
//新创建一个结点
new_node = create_node(new);
if(NULL == new_node)
{
perror("create_node");
return;
}
//替换结点
list_replace_init(&pos->list,&new_node->list);
//释放旧结点
free(pos);
//将pos指向新的替换结点的地址
pos = new_node;
}
}
}

复制代码

Linux 内核链表的使用方法

界说链表和节点：

界说链表头：

LIST_HEAD(my_list);

复制代码

界说节点结构体：

struct my_struct {
int data;
struct list_head list; // 嵌入链表节点
};

复制代码

添加节点：

#include <stdio.h>#include <stdlib.h>#include "list.h" // 假设链表宏界说和函数在list.h中struct my_struct { int data; struct list_head list;};int main() { LIST_HEAD(my_list);
// 初始化链表头 // 创建并添加节点 for (int i = 0; i < 5; i++) { struct my_struct *new_node = (struct my_struct *)malloc(sizeof(struct my_struct)); new_node->data = i; list_add_tail(&new_node->list, &my_list); // 添加到链表尾部 } // 遍历链表 struct list_head *pos; struct my_struct *entry; list_for_each(pos, &my_list) { entry = list_entry(pos, struct my_struct, list); printf("Data: %d\n", entry->data); } return 0;}

复制代码

删除节点：

// 删除所有节点
struct list_head *pos, *n;
list_for_each_safe(pos, n, &my_list) {
struct my_struct *entry = list_entry(pos, struct my_struct, list);
list_del(pos); // 从链表中删除
free(entry); // 释放内存
}

复制代码

适配更多场景：

通过 list_for_each_entry 宏直接遍历包含链表节点的结构体：

#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))

复制代码

Linux 内核链表的长处

内核链表具有通用性：list_head 和相关宏界说可以适配任何结构体，无需额外界说链表节点结构。高效性：插入、删除操纵时间复杂度为 O(1)。灵活性：支持双向、循环、动态扩展等多种操纵。内存安全：提供了防止悬空指针和错误访问的机制。
我们以一个模拟的任务调理体系为例，演示如何利用Linux 内核链表管理多个任务。这个例子演示了链表更为直观的实际应用场景：
任务调理场景形貌

假设我们须要管理多个任务，每个任务有以下信息：

任务 ID：唯一标识任务。
任务优先级：用于决定任务的执行顺序（高优先级任务优先执行）。
任务状态：表现任务是运行中、等候中照旧完成。

通过内核链表，我们可以实现如下功能：

动态插入新任务。
根据条件删除任务（例如任务完成）。
按优先级遍历任务列表。
模拟任务的调理行为。

1> 数据结构界说

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 内核链表头文件（假设 `list.h` 中定义了 Linux 链表的相关宏和函数）
#include "list.h"
// 定义任务结构体
struct task {
int task_id; // 任务 ID
int priority; // 任务优先级
char status[20]; // 任务状态（running, waiting, completed）
struct list_head list; // 链表节点，用于将任务加入链表
};

复制代码

2> 初始化链表

// 定义链表头，用于管理任务列表
LIST_HEAD(task_list);

复制代码

3> 添加任务

我们将任务按优先级插入链表中，确保链表始终按优先级从高到低分列。

// 添加任务到链表，按优先级插入
void add_task(int task_id, int priority, const char *status) {
// 创建新任务节点
struct task *new_task = (struct task *)malloc(sizeof(struct task));
new_task->task_id = task_id;
new_task->priority = priority;
strcpy(new_task->status, status);
// 遍历链表，找到插入位置
struct list_head *pos;
struct task *entry;
list_for_each(pos, &task_list) {
entry = list_entry(pos, struct task, list);
if (priority > entry->priority) {
// 在优先级较低的任务之前插入
list_add_tail(&new_task->list, pos->prev);
return;
}
}
// 如果链表为空或优先级最低，插入到链表末尾
list_add_tail(&new_task->list, &task_list);
}

复制代码

4> 删除任务

我们可以根据任务 ID 或任务状态删除任务，例如删除全部状态为 “completed” 的任务。

// 根据任务 ID 删除任务
void delete_task_by_id(int task_id) {
struct list_head *pos, *n;
struct task *entry;
// 遍历链表找到目标任务
list_for_each_safe(pos, n, &task_list) {
entry = list_entry(pos, struct task, list);
if (entry->task_id == task_id) {
list_del(pos); // 从链表中删除节点
free(entry); // 释放内存
printf("Task %d deleted.\n", task_id);
return;
}
}
printf("Task %d not found.\n", task_id);
}
// 删除所有完成的任务
void delete_completed_tasks() {
struct list_head *pos, *n;
struct task *entry;
list_for_each_safe(pos, n, &task_list) {
entry = list_entry(pos, struct task, list);
if (strcmp(entry->status, "completed") == 0) {
list_del(pos);
free(entry);
printf("Completed task deleted.\n");
}
}
}

复制代码

5> 遍历任务

我们可以按链表顺序（即优先级顺序）遍历全部任务，并打印任务信息。

// 打印任务列表
void print_tasks() {
struct list_head *pos;
struct task *entry;
printf("Task List:\n");
printf("ID Priority Status\n");
printf("=============================\n");
list_for_each(pos, &task_list) {
entry = list_entry(pos, struct task, list);
printf("%-5d %-10d %-10s\n", entry->task_id, entry->priority, entry->status);
}
printf("\n");
}

复制代码

6> 模拟任务调理

我们可以通过修改任务状态来模拟任务的调理行为。

// 模拟任务调度
void simulate_task_execution() {
struct list_head *pos;
struct task *entry;
list_for_each(pos, &task_list) {
entry = list_entry(pos, struct task, list);
if (strcmp(entry->status, "waiting") == 0) {
// 将第一个等待中的任务标记为运行中
strcpy(entry->status, "running");
printf("Task %d is now running.\n", entry->task_id);
break;
}
}
}

复制代码

7> 主函数（main.c）

int main() {
// 初始化任务列表
add_task(1, 10, "waiting");
add_task(2, 20, "waiting");
add_task(3, 15, "waiting");
add_task(4, 5, "waiting");
print_tasks(); // 打印初始任务列表
// 模拟任务调度
printf("Simulating task execution:\n");
simulate_task_execution();
print_tasks();
// 删除完成的任务（目前没有完成任务）
delete_completed_tasks();
// 删除任务 ID 为 3 的任务
printf("Deleting task with ID 3:\n");
delete_task_by_id(3);
print_tasks();
// 添加新任务
printf("Adding new task:\n");
add_task(5, 25, "waiting");
print_tasks();
return 0;
}

复制代码

运行效果示例

Task List:
ID Priority Status
=============================
2 20 waiting
3 15 waiting
1 10 waiting
4 5 waiting
Simulating task execution:
Task 2 is now running.
Task List:
ID Priority Status
=============================
2 20 running
3 15 waiting
1 10 waiting
4 5 waiting
Deleting task with ID 3:
Task 3 deleted.
Task List:
ID Priority Status
=============================
2 20 running
1 10 waiting
4 5 waiting
Adding new task:
Task List:
ID Priority Status
=============================
5 25 waiting
2 20 running
1 10 waiting
4 5 waiting

复制代码

代码拆解分析：

动态优先级插入：任务根据优先级动态插入到链表的适当位置，确保链表始终按优先级从高到低排序。
链表操纵灵活性：
- 使用 list_add_tail() 和 list_del() 等操纵，轻松实现插入、删除等功能。
- list_for_each_safe() 确保在遍历过程中安全删除节点。
模拟调理：通过修改任务状态（如将 waiting 改为 running），模拟任务的执行。
代码扩展性：可以轻松扩展其他功能，如暂停任务、重新调解优先级等。

这里先为各人介绍了Linux中内核链表的完备写法，然后用例子展示了 Linux 内核链表在动态任务管理中的应用，在实际开辟中，Linux 内核链表广泛用于管理类似的动态数据结构，例如网络数据包队列、设备驱动哀求队列等场景。内核链表具有很多利益：

动态优先级插入和排序。
高效的插入、删除、遍历操纵。
扩展性强，得当复杂任务调理场景。

综上。Linux 内核链表利用 C 语言的灵活性和宏界说实现了简便、高效的双向循环链表。它的核心设计特点包罗：

基于 list_head 实现通用双向循环链表。
提供了一组操纵宏和辅助函数，简化链表操纵。
通过结构体嵌套和 container_of 实现灵活的节点管理。

把握 Linux 内核链表的原理和使用方法，不但有助于理解内核开辟，还能在其他 C 语言项目中鉴戒实现高效的数据结构。
综上。希望该内容能对你有帮助，感谢！
以上。仅供学习与分享交换，请勿用于商业用途！转载需提前说明。
我是一个非常热爱技术的程序员，希望这篇文章可以或许对您有帮助，也希望认识更多热爱程序开辟的小同伴。
感谢！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

【数据结构】链表（3）：Linux 的内核链表

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云