Linux 内核中的侵入式双向链表。对比了传统链表与自包含链表，阐述了侵入式链表内存紧凑、性能高、支持多链表管理的优势。介绍了核心数据结构 list_head、初始化宏及增删遍历操作函数。重点解析了 container_of 宏原理，通过偏移量计算获取结构体指针。提供了基本使用、多链表管理及队列栈实现的示例代码，适用于系统编程、内核开发及高性能场景。
**侵入式链表（Intrusive Linked List）**是一种特殊的链表实现方式，它的特点是：链表节点直接嵌入到数据结构内部，而不是通过指针指向独立的数据节点。
在侵入式链表中，链表节点（list_head）是数据结构的一个成员，而不是独立存在的。这种设计使得链表操作更加高效，并且不需要额外的内存分配。
数据结构包含 list_head 成员，list_head 嵌入在数据中，通过 container_of 获取完整数据。
传统链表通常采用以下结构：
* data;
};
特点：
说明： list_node中的 data字段是一个指针，指向实际的数据对象，数据对象和链表节点在内存中是分离的。
还有一种常见的链表实现方式，数据直接嵌入在链表节点中：
// 自包含链表节点结构
struct list_node {
int a; // 数据直接嵌入在节点中
struct list_node* next; // 指向下一个节点
struct list_node* prev; // 指向前一个节点
};
特点：
说明： 数据字段（如 int a）直接嵌入在链表节点结构体中，链表节点本身就是数据容器。
适用场景：
侵入式链表的结构：
// 侵入式链表节点结构
struct list_head {
struct list_head* next; // 指向下一个节点
struct list_head* prev; // 指向前一个节点
};
// 数据结构中包含 list_head
struct my_data {
int value;
char name[32];
struct list_head list; // 链表节点嵌入在数据结构中
};
特点：
container_of宏从节点指针获取完整数据结构说明： list_head直接嵌入在 my_data结构体中，数据对象和链表节点在内存中是连续的，通过 list成员连接。
| 特性 | 传统链表 | 自包含链表 | 侵入式链表 |
|---|---|---|---|
| 数据存储 | 外部对象（通过指针） | 节点内部 | 数据结构内部 |
| 灵活性 | 高（可存储任意类型） | 低（固定类型） | 高（任意类型） |
| 内存开销 | 中等（需要指针） | 低 | 最低 |
| 适用场景 | 通用场景 | 简单固定类型 | 系统编程、高性能场景 |
list_head成员Linux 内核在 include/linux/list.h中实现了完整的侵入式双向链表。这是经过多年优化的工业级实现。
linux-4.14.7/include/linux/list.h
struct list_head {
struct list_head* next; // 指向下一个节点
struct list_head* prev; // 指向前一个节点
};
这是侵入式链表的核心数据结构，只包含两个指针，非常简洁。
// 初始化宏定义
#define LIST_HEAD_INIT(name) { &(name), &(name) }
// 声明并初始化链表头
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
// 初始化函数
static inline void INIT_LIST_HEAD(struct list_head *list) {
WRITE_ONCE(list->next, list);
list->prev = list;
}
初始化后的状态：
next和 prev都指向自身/**
* list_add - 在链表头部添加新节点
* @new: 要添加的新节点
* @head: 链表头
*
* 在 head 之后插入 new 节点，适合实现栈（LIFO）
*/
static inline void list_add(struct list_head *new, struct list_head *head) {
__list_add(new, head, head->next);
}
/**
* list_add_tail - 在链表尾部添加新节点
* @new: 要添加的新节点
* @head: 链表头
*
* 在 head 之前插入 new 节点，适合实现队列（FIFO）
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head) {
__list_add(new, head->prev, head);
}
/**
* __list_add - 在两个已知节点之间插入新节点
* @new: 新节点
* @prev: 前一个节点
* @next: 后一个节点
*/
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) {
if (!__list_add_valid(new, prev, next)) return;
next->prev = new;
new->next = next;
new->prev = prev;
WRITE_ONCE(prev->next, new);
}
/**
* list_del - 从链表中删除节点
* @entry: 要删除的节点
*
* 注意：删除后节点处于未定义状态
*/
static inline void list_del(struct list_head *entry) {
__list_del_entry(entry);
entry->next = LIST_POISON1; // 设置为毒药指针，便于调试
entry->prev = LIST_POISON2;
}
static inline void __list_del_entry(struct list_head *entry) {
if (!__list_del_entry_valid(entry)) return;
__list_del(entry->prev, entry->next);
}
static inline void __list_del(struct list_head *prev, struct list_head *next) {
next->prev = prev;
WRITE_ONCE(prev->next, next);
}
/**
* list_del_init - 删除节点并重新初始化
* @entry: 要删除的节点
*
* 删除后节点可以重新使用
*/
static inline void list_del_init(struct list_head *entry) {
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
}
/**
* list_for_each - 遍历链表
* @pos: 用作循环游标的 list_head 指针
* @head: 链表头
*/
#define list_for_each(pos, head) \
for(pos = (head)->next; pos != (head); pos = pos->next)
/**
* list_for_each_entry - 遍历链表中的数据项
* @pos: 用作循环游标的数据结构指针
* @head: 链表头
* @member: list_head 在数据结构中的成员名
*/
#define list_for_each_entry(pos, head, member) \
for(pos = list_first_entry(head, typeof(*pos), member); \
&pos->member != (head); \
pos = list_next_entry(pos, member))
/**
* list_for_each_entry_safe - 安全遍历，允许在遍历时删除节点
* @pos: 用作循环游标的数据结构指针
* @n: 另一个数据结构指针，用作临时存储
* @head: 链表头
* @member: list_head 在数据结构中的成员名
*/
#define list_for_each_entry_safe(pos, n, head, member) \
for(pos = list_first_entry(head, typeof(*pos), member), \
n = list_next_entry(pos, member); \
&pos->member != (head); \
pos = n, n = list_next_entry(n, member))
/**
* list_empty - 判断链表是否为空
* @head: 链表头
*/
static inline int list_empty(const struct list_head *head) {
return READ_ONCE(head->next) == head;
}
/**
* list_move - 将节点从一个链表移动到另一个链表头部
* @list: 要移动的节点
* @head: 目标链表头
*/
static inline void list_move(struct list_head *list, struct list_head *head) {
__list_del_entry(list);
list_add(list, head);
}
container_of宏是侵入式链表的灵魂，它能够从结构体成员的指针获取整个结构体的指针。
/**
* 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)
原理：
0强制转换为 TYPE*类型MEMBER成员，得到成员相对于结构体起始地址的偏移量&((TYPE *)0)->MEMBER就是偏移量示例：
struct my_data {
int value; // 偏移量：0
char name[32]; // 偏移量：4
struct list_head list; // 偏移量：36 (假设)
};
// offsetof(struct my_data, list) = 36
假设我们有：
struct my_data {
int value;
struct list_head list;
};
struct my_data* data;
struct list_head* list_ptr = &data->list;
现在要从 list_ptr获取 data：
// 步骤 1: 获取 list 成员的类型并验证
const typeof(((struct my_data*)0)->list) *__mptr = list_ptr;
// 步骤 2: 将指针转换为 char*以便进行字节级运算
char *__mptr_char = (char*)__mptr;
// 步骤 3: 减去偏移量得到结构体起始地址
struct my_data* result = (struct my_data*)(__mptr_char - offsetof(struct my_data, list));
内存布局示意：
地址：0x1000 0x1024 [my_data] [list]
^ ^
| |
data list_ptr
offsetof = 0x1024 - 0x1000 = 0x24
从 list_ptr 获取 data: data = list_ptr - offsetof = 0x1024 - 0x24 = 0x1000 ✓
typeof用于类型检查，确保传入的 ptr确实是 member类型的指针，提高代码安全性。
#include <stdio.h>
#include <stdlib.h>
#include "list.h" // 假设包含了 list.h
// 定义数据结构
struct student {
int id;
char name[32];
int age;
struct list_head list; // 链表节点
};
int main(void) {
// 初始化链表头
LIST_HEAD(student_list);
// 创建学生数据
struct student* s1 = malloc(sizeof(struct student));
s1->id = 1;
strcpy(s1->name, "Alice");
s1->age = 20;
INIT_LIST_HEAD(&s1->list);
struct student* s2 = malloc(sizeof(struct student));
s2->id = 2;
strcpy(s2->name, "Bob");
s2->age = 21;
INIT_LIST_HEAD(&s2->list);
// 添加到链表
list_add(&s1->list, &student_list);
list_add(&s2->list, &student_list);
// 遍历链表
struct student* pos;
list_for_each_entry(pos, &student_list, list) {
printf("ID: %d, Name: %s, Age: %d\n", pos->id, pos->name, pos->age);
}
// 清理
struct student* n;
list_for_each_entry_safe(pos, n, &student_list, list) {
list_del(&pos->list);
free(pos);
}
return 0;
}
// 一个对象可以同时属于多个链表
struct task {
int pid;
char name[32];
struct list_head run_list; // 运行队列
struct list_head wait_list; // 等待队列
struct list_head all_tasks; // 所有任务列表
};
// 初始化
struct task* t = malloc(sizeof(struct task));
INIT_LIST_HEAD(&t->run_list);
INIT_LIST_HEAD(&t->wait_list);
INIT_LIST_HEAD(&t->all_tasks);
// 添加到不同链表
list_add(&t->run_list, &run_queue);
list_add(&t->all_tasks, &task_list);
// 使用 list_add_tail 实现 FIFO 队列
LIST_HEAD(queue);
void enqueue(struct list_head* item) {
list_add_tail(item, &queue);
}
struct list_head* dequeue(void) {
if (list_empty(&queue)) return NULL;
struct list_head* item = queue.next;
list_del(item);
return item;
}
// 使用 list_add 实现 LIFO 栈
LIST_HEAD(stack);
void push(struct list_head* item) {
list_add(item, &stack);
}
struct list_head* pop(void) {
if (list_empty(&stack)) return NULL;
struct list_head* item = stack.next;
list_del(item);
return item;
}
Linux 内核中广泛使用侵入式链表：
当一个对象需要同时属于多个链表时，侵入式链表特别有用：
struct process {
int pid;
struct list_head runq; // 运行队列
struct list_head waitq; // 等待队列
struct list_head children; // 子进程列表
struct list_head siblings; // 兄弟进程列表
};
list_head成员container_of宏的理解需要一定时间container_of宏：这是侵入式链表的精髓
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online