一、侵入式链表

在了解侵入式链表之前，先回顾之前的非侵入式链表，形式如下：

struct Node {
    int data;          // 数据
    struct Node* next; 
};

在非侵入式链表的这种设计中，拿到一个 Node，顺便也就拿到了它的 data。
而在 Linux 内核中，ListNode 本身纯粹只是一个“串联工具”，存放在业务结构体中。例如下面代码中的 ListNode node 嵌入在 MyTimer 业务结构体中：

typedef struct MyTimer
{
    uint32_t timeout;
    void (*cb)(void);
    // ... 业务数据 ...

    struct ListNode node;   // 链表节点侵入在对象内部
} MyTimer;

下面将结合具体的代码探讨下侵入式链表。

二、如何实现侵入式链表

需要注意，本文使用双向循环链表实现侵入式链表。在开启内容之前，先说明该链表的一般结构：

梳理下重要节点之间的关系

head.next = node1
head.prev = node3

即：
链表尾节点 = head.prev

2.1 定义句柄与节点

#include <stdint.h>
#include <stdbool.h>
#include <stddef.h> 

// 1. 定义节点 (Node)
// 仅包含前驱、后继指针，不包含数据 data
typedef struct ListNode {
    struct ListNode* prev;
    struct ListNode* next;
} ListNode;

// 2. 定义链表管理器 (List)
typedef struct {
    ListNode head;
    // 可加 size 用以记录数量
} List;

// 定义句柄
typedef List* ListHandle;
typedef ListNode* ListNodeHandle;

使用句柄抽象指针，提升可读性，便于后期拓展。

需要注意的是，在上面这段代码中，链表管理器 List 中包含了一个实体头节点 head，用于表示链表的入口。此时链表结构如下：

List
 └── head (哨兵节点)
        ↓
   node1 ↔ node2 ↔ node3

2.2 操作函数

2.2.1 初始化

头节点的 prev 和 next 都指向自己，代表空

void List_Init(ListHandle list) 
{
    list->head.next = &list->head;
    list->head.prev = &list->head;
}

需要注意，此处的 list->head 是一个实实在在的结构体变量（对象本身），它占用着 8 字节或 16 字节的内存空间。
为正确理解上述代码，给出一个简单版本的示例：

int a = 5;  
int *p;  
p = &a;

上面简单代码中可分为以下3步：

1. 创建一个 整型变量 a（实体，在内存中占有一定空间，可类比 list->head）
2. 创建一个 指针变量 p（指针，可类比 list->head.next 和 list->head.prev）
3. 将 a 的地址存入 p（指向该实体，即最后的 头节点的 prev 和 next 都指向自己）

2.2.2 插入节点

该函数是我们后续插入操作的核心函数，该函数把 new_node 插入到 prev 和 next 两个节点之间

// 插入节点（插在 prev 和 next 中间）
static void __List_Add(ListNodeHandle new_node, ListNodeHandle prev, ListNodeHandle next) 
{
    next->prev = new_node;
    new_node->next = next;
    new_node->prev = prev;
    prev->next = new_node;
}

可以参考之前文章中的“先连新，后断旧”

图示：

2.2.3 尾插

直接调用我们已经写好的插入API函数：

// 尾部插入（通常用于通过 Event 队列）
void List_AddTail(ListHandle list, ListNodeHandle new_node) 
{
    __List_Add(new_node, list->head.prev, &list->head);
}

重点理解下__List_Add(new_node, list->head.prev, &list->head);

1. 首先明确下 __List_Add 的作用：把 new_node 插入到 prev 和 next 两个节点之间;
2. 在尾插法当中，待插入的节点（new_node）的前驱节点为原链表中的尾节点，后继节点为头节点（head）(可以想象这是个环状结构)
3. list为我们的链表管理器，其内部存放头节点。在双向循环链表结构中，list->head.prev 指向尾节点（如下图中的 node3）

可视化下尾插法的操作逻辑：

1. 假设此时的链表结构如下（未插入前的链表结构）2. 尾部插入（将 new_node 插入在原链表的尾节点 node3 和 头节点 head中 ）3. 最终链表结构

2.2.4 删除节点

// 删除节点
// 注意: 这体现了侵入式的优势，删除不需要 ListHandle，只要有 NodeHandle 即可
void List_Del(ListNodeHandle node) 
{
    node->next->prev = node->prev;
    node->prev->next = node->next;
    // 将 node 的指针清空，防止野指针
    node->next = NULL;
    node->prev = NULL;
}

图示：

2.2.5 链表是否为空

// 检查链表是否为空
bool List_IsEmpty(ListHandle list) 
{
    return list->head.next == &list->head;
}

检查“头节点的下一个节点，是不是头节点本身”

注意下空链表的初始形态：头节点的 next 和 prev 指针都指向它自己。

三、核心宏：container_of

// 计算成员 member 在结构体 type 中的字节偏移量
// 标准库 stddef.h 已包含 offsetof，这里为了理解列出原理
// #define offsetof(type, member) ((size_t)&((type *)0)->member)

// ★★★ 核心宏 ★★★
// ptr:    指向结构体成员的指针（即 &timer->node）
// type:   外层结构体的类型（即 struct MyTimer）
// member: 结构体中该成员的名字（即 node）
#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

// 为了方便，我们可以封装遍历宏
#define List_ForEach(pos, list) \
    for (pos = (list)->head.next; pos != &(list)->head; pos = pos->next)

明确 container_of 的作用： “已知结构体里某个成员的指针，反推出整个结构体的首地址。”

结构体首地址 = 成员的当前内存地址 - 成员在结构体内部的相对偏移量

1. 假设存在下面的业务结构体：该结构体嵌套了 ListNode node;

   typedef struct {
   	int id;               // 偏移量假设为 0
   	char name[20];        // 偏移量假设为 4
   	ListNode node;        // 偏移量假设为 16
   } Student;
   

   内存简图如下：

   内存地址         Student 结构体内部
   ===========================================
   0x1000  --->  [ int id              ] (占 4 字节)
   0x1004  --->  [ char name[20]       ] (占 20 字节)
   0x1024  --->  [ ListNode node       ] (占 16 字节，包含 prev 和 next)
   

   此处的 0x1000 是整个 Student 结构体的起始地址。
   而 0x1024 是内部成员 node 的起始地址。（它们之间相差了 24 个字节的偏移量）。
   当遍历链表时，得到的其实是指向 node 的指针（假设地址是 0x1024）。
   但需要的是 Student 这个结构体的地址，这样才能读出学生的 id 和 name。怎么从 0x1024 退回到 Student 的起始地址 0x1000 呢？

2. 此时就需要这个宏：

   #define container_of(ptr, type, member) \
   ((type *)((char *)(ptr) - offsetof(type, member)))
   

   • ptr：指向结构体成员的指针（例如 指向 node 的指针）
   • type:外层结构体的类型（例如 Student）
   • member：结构体中该成员的名字（例如 node）

3. offsetof(type, member)：通过这个宏计算 node 这个成员在 Student 结构体里距离开头有多远（假设是 24 个字节）。这个值在编译时就确定.

4. (char *)(ptr)：
   将 node 指针强转成 char *（字符指针）。在C语言中，指针加减的单位是它所指向的数据类型的大小。转为 char *（大小为1字节），保证了后面减去的偏移量（24）均按字节计算的，而不是减去 24 个 node 的大小。

5. ((char *)(ptr) - offsetof(type, member))：
   当前地址（0x1024）减去偏移量（24），刚好等于结构体的起始首地址（0x1000）。

四、实例演示

1. 结构体定义

   typedef struct {
   	int id;             // 业务数据：任务ID
   	const char* name;   // 业务数据：任务名称
   
   	 // 【关键】嵌入链表节点
   	ListNode node;      // “挂钩”
   } MyTask;
   

2. 初始化并挂载

   List taskList; // 全局任务链表
   MyTask task1, task2;
   
   void System_Init()
   {
   	// 1. 初始化空链表
   	List_Init(&taskList); 
   
   	// 2. 初始化任务数据
   	task1.id = 1; task1.name = "Sensor";
   	task2.id = 2; task2.name = "Motor";
   
   	// 3. 【关键】把衣服的挂钩挂到绳子上
   	List_AddTail(&taskList, &task1.node);
   	List_AddTail(&taskList, &task2.node);
   }
   

3. 遍历
   通过宏进行遍历：pos可以类比于我们之前设定的“起跑线”

   #define List_ForEach(pos, list) \
   for (pos = (list)->head.next; pos != &(list)->head; pos = pos->next)
   

   void System_Process() 
   {
   	ListNodeHandle pos;
   	MyTask* task;
   
   	// 遍历链表的宏（底层就是一个 for 循环）
   	List_ForEach(pos, &taskList) {
       
       	// 【关键】从 node 指针还原出 MyTask 指针
       	task = container_of(pos, MyTask, node);
   
       	printf("Processing Task: %s\n", task->name);
   	}
   }