内核链表

总体结构

内核链表的优点在于：链表节点可以是不同类型的结构体
内核链表是双向链表：

注：

1. 链表节点结构体的类型可以不同，但必须要有 struct list_head 类型的成员
2. 需要由单独的头节点，头节点并不存储内容

太长不看

涉及到的所有操作有：

// 重要的宏定义
#define offsetof(type, member) ...
#define container_of(ptr, type, member) ...
// 链表头的定义
struct list_head { struct list_head *next, *prev; };
// 链表头初始化的三种方式
#define LIST_HEAD_INIT(name) ...
#define LIST_HEAD(name) ...
static inline void INIT_LIST_HEAD(struct list_head *list);
// 访问某个节点
#define list_entry(ptr, type, member) ...
#define list_first_entry(ptr, type, member) ...
// 判断链表为空
static inline int list_empty(const struct list_head *head);
// 遍历的三种方法
#define list_for_each(pos, head) ...
#define list_for_each_prev(pos, head) ...
#define list_for_each_entry(pos, head, member) ...
#define list_for_each_entry_safe(pos, n, head, member) ...
// 添加节点
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next);
static inline void list_add(strcut list_head *new, struct list_head *head);
static inline void list_add_tail(struct list *new, struct list_head *head);
// 删除节点
static inline void __list_del(struct list_head *prev, struct list_head *next);
static inline void list_del(struct list_head *entry);
static inline void list_del_init(struct list_head *entry);

基本操作

内核链表的宏定义

内核链表能够连接不同类型节点的特性，是由这两个宏来实现的：

// 取得结构体的成员偏移
#define offsetof(type, member) ((size_t)&((type *)0)->member)
// 已知成员地址，取得结构体地址
#define container_of(ptr, type, member) ({\
    const typeof(((type *)0)->member) *__mptr = (ptr); \
    (type *)((char *)__mptr - offsetof(type, member));})
// 注：type是指结构体的类型；member是指结构体成员的名称

链节的定义

// 链表头的定义
struct list_head {
    struct list_head *next, *prev;
};

链表节点需要包含 struct list_head 类型的成员

初始化链表头

相关定义：（位于 linux 源码的 include/linux/list.h ）

// 链表头的初始化
#define LIST_HEAD_INIT(name) {&(name), &(name)}
// 链表头的定义和初始化一起进行
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)
// 初始化链表头节点
// 注意和宏定义 LIST_HEAD_INIT 的写法区分开
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

初始化链表头节点的三种方法：

// 方法1
struct list_head head1 = LIST_HEAD_INIT(head1);
// 方法2
struct list_head head2;
INIT_LIST_HEAD(head2);
// 方法3
LIST_HEAD(head3);

访问某个节点

已知节点的 struct list_head 成员的地址，访问该节点
相关定义：

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
// 已知链表头，访问第一个节点
#define list_first_entry(ptr, type, member) \
    list_entry((ptr)->next, type, member)

判断节点是否为空

static inline int list_empty(const struct list_head *head)
{
    return head->next == head;
}

遍历

不同类型节点组成的链表也可以遍历，只要节点中的 struct list_head 成员的名称相同即可。

1. 遍历的第一种方法

// 向后遍历
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)
// 向前遍历
#define list_for_each_prev(pos, head) \
    for (pos = (head)->prev; post != (head); post = pos->prev)

注： pos 是一个 struct list_head * 类型的循环变量，需要额外提供

使用方法：

// 链表节点的定义
struct Node {
    struct list_head link;
    char name[256];
};
list_head *pos = NULL;        // 循环变量
LIST_HEAD(head);            // 链表头
// 遍历链表
list_for_each(pos, head) {
    printf("name is %s\n", list_entry(pos, struct Node, link));
}

2. 遍历的第二种方法

#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 是 struct list_head * 类型的；而第二种的循环变量 pos 是节点类型的。

使用方法：

// 链表节点的定义
struct Node {
    struct list_head link;
    char name[256];
};
struct Node *pos = NULL;    // 循环变量
LIST_HEAD(head);            // 链表头
// 遍历链表
list_for_each_entry(pos, head, link) {
    printf("name is %s\n", pos->name);
}

3. 第三种遍历方法

支持在遍历的过程中删除节点
定义：

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

使用：

// 链表节点的定义
struct Node {
    struct list_head link;
    char name[256];
};
struct Node *pos = NULL;    // 循环变量
struct Node *n = NULL;        // 循环变量
LIST_HEAD(head);            // 链表头
// 遍历链表
list_for_each_entry_safe(pos, n, head, link) {
    printf("name is %s\n", pos->name);
    list_del(pos->link);
    free(pos);
}

添加节点

定义：

// 在两个节点之间添加一个节点
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;
}
// 在链表开头添加一个节点
static inline void list_add(strcut list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}
// 在链表末尾添加一个节点
static inline void list_add_tail(struct list *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

关于 __list_add 函数的示意图：

删除节点

注：删除节点仅仅是从链表上摘除，并不涉及内存管理。该释放的内存还是要手动手动释放

定义：

static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    next->prev = prev;
    prev->next = next;
}
// 从链表中摘下一个节点
// 节点的 prev 和 next 都是 NULL
static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->entry);
    entry->next = entry->pre = NULL;
}
// 从链表中摘下一个节点
// 节点的 prev 和 next 指向自身
static inline void list_del_init(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    INIT_LIST_HEAD(entry);
}

函数 __list_del 的示意图：

资源文件

内核链表.drawio