C语言面向对象编程

1.内核通用链表

一、什么是 list_head？

list_head 是 Linux 内核中自己实现的一种 双向循环链表 的结构，定义在 <linux/list.h> 中。它设计得非常轻巧、灵活，广泛用于内核模块、驱动、进程调度、网络协议栈等。

它的关键思想是：

将链表结构嵌入到你的数据结构中，从而实现通用链表操作。

 二、结构定义

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

每一个 list_head 实际就是两个指针：指向下一个节点和上一个节点。

 三、如何使用

假设你有一个自定义结构体：

struct student {
    char name[20];
    int age;
    struct list_head list;  // 嵌入 list_head
};

这样，每个 student 节点就能通过 list 成员串联成一个链表。

四、常用操作宏（定义在 list.h）

五、链表是循环的

链表头的 next 指向第一个节点，prev 指向最后一个节点；尾节点的 next 又指向头部。这是一种 循环双向链表。

七、完整例子

不依赖内核的用户态实现（适合你直接编译）

用户空间简化版 list.h

先把这段保存为 list.h：

#ifndef _USER_LIST_H
#define _USER_LIST_H

#include <stddef.h>

struct list_head {
    struct list_head *next, *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)
{
    list->next = list;
    list->prev = list;
}

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(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

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

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    prev->next = next;
}

static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = entry->prev = NULL;
}

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

#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) );})

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

#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))

#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, typeof(*n), member))

#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

struct student {
    char name[20];
    int age;
    struct list_head list;
};

LIST_HEAD(student_list);

void add_student(const char *name, int age) {
    struct student *stu = malloc(sizeof(*stu));
    strcpy(stu->name, name);
    stu->age = age;
    INIT_LIST_HEAD(&stu->list);
    list_add_tail(&stu->list, &student_list);
}

void show_students() {
    struct student *stu;
    list_for_each_entry(stu, &student_list, list) {
        printf("Name: %s, Age: %d\n", stu->name, stu->age);
    }
}

void cleanup() {
    struct student *stu, *tmp;
    list_for_each_entry_safe(stu, tmp, &student_list, list) {
        list_del(&stu->list);
        free(stu);
    }
}

int main() {
    add_student("Tom", 18);
    add_student("Jerry", 19);
    add_student("Alice", 20);

    printf("Student list:\n");
    show_students();

    cleanup();
    return 0;
}

分别介绍.h中的几个宏定义：

① offsetof宏

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

是 C 语言中非常经典的技巧，用来 计算结构体中某个成员变量相对于结构体起始地址的偏移量（以字节为单位）。

假设你有一个结构体：

struct student {
    int id;             // 偏移 0
    char name[20];      // 偏移 4
    double gpa;         // 偏移 24（视平台对齐规则）
};

现在你想知道 gpa 在结构体中的偏移是多少，可以这样写：

size_t offset = offsetof(struct student, gpa);

宏展开：

((size_t) &((struct student *)0)->gpa)

拆解：

1. (struct student *)0：构造一个指向地址 0 的结构体指针（不会真的访问地址 0，只是为了类型推导）。

2. ((struct student *)0)->gpa：假装在地址 0 上有一个结构体，访问其成员 gpa，结果是一个 地址偏移表达式（例如 0 + 24，实际上就是 24 字节偏移）。

3. &((struct student *)0)->gpa：取这个成员的地址（是个偏移地址，不是真地址）。

4. (size_t)：强制转换为整数类型，得到偏移量。

例子

#include <stdio.h>
#include <stddef.h>

struct my_struct {
    char a;         // offset 0
    int b;          // offset 4 (由于对齐)
    double c;       // offset 8
};

int main() {
    printf("offset of a = %zu\n", offsetof(struct my_struct, a)); // 0
    printf("offset of b = %zu\n", offsetof(struct my_struct, b)); // 4
    printf("offset of c = %zu\n", offsetof(struct my_struct, c)); // 8
}

offsetof(TYPE, MEMBER) 返回成员 MEMBER 在结构体 TYPE 中的字节偏移量，用于高级结构体操作的基础工具之一。 

• offsetof 是由 C 标准定义的宏（在 <stddef.h> 中）。

• 它是完全 编译期计算的，不访问内存，也不会有运行时开销。

• 在结构体操作、容器设计、内核链表、序列化、手动内存布局等场景中非常有用。

② container_of 宏：

#define container_of(ptr, type, member) ({                      \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);        \
    (type *)( (char *)__mptr - offsetof(type, member) );})

从结构体的某个成员指针（ptr），反推出这个成员所属的整个结构体的地址。

struct student {
    int id;
    struct list_head list;
};

struct list_head *p = &stu->list;
struct student *stu_ptr = container_of(p, struct student, list);

这个宏干的事情就是：你只知道结构体中某个成员变量的地址 ptr，你想获得这个变量所在的整个结构体 type *，它会帮你算出来。

• offsetof(type, member)：得到成员在结构体中的偏移。

• (char *)__mptr - offset：从成员地址减去偏移就得到结构体地址。

③ list_entry 宏

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

通过链表指针 ptr 得到包含它的结构体 type *。

这个宏就是对 container_of 的封装，用在链表中，ptr 是 struct list_head * 类型。

④ 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))

遍历链表中的每一个结构体元素（不是链表节点 list_head，而是包含它的那个结构体）。

• pos：用于遍历的结构体指针。

• head：链表头（struct list_head *）。

• member：结构体中的链表成员名字。

⑤ list_for_each_entry_safe宏

#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, typeof(*n), member))

是 Linux 内核链表中非常常用的一个 “安全遍历”宏，用于在 遍历过程中可能会删除当前节点 的情况。它是对 list_for_each_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))

这个宏用于普通的链表遍历，pos 是当前元素指针。

但是 不能在遍历中删除当前元素，因为 pos = pos->next 是在遍历尾部执行的，一旦 pos 被删除了，就找不到下一个节点了，会导致访问野指针。

struct my_struct *pos;
list_for_each_entry(pos, &head, list) {
    if (should_delete(pos)) {
        list_del(&pos->list);  // ❌危险：pos下一次访问就无效了
        kfree(pos);
    }
}

安全版本 list_for_each_entry_safe

#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, typeof(*n), member))

多了一个变量 n（next）：

• 在遍历当前节点时，预先保存好下一个节点 n。

• 即使你在中间 free(pos) 或 list_del(&pos->member)，也不会影响后续访问 n，避免野指针。

struct my_struct *pos, *n;
list_for_each_entry_safe(pos, n, &head, list) {
    if (should_delete(pos)) {
        list_del(&pos->list);  // ✅可以安全删除
        kfree(pos);
    }
}

为什么要用用户空间简化版不依赖内核的用户态实现？

1. 用户态无需加载内核模块，更安全方便

• 在用户态编写和运行程序不需要 root 权限，也不涉及内核模块的编译、加载、卸载。

• 避免由于错误操作导致内核崩溃（例如 oops、panic）。

2. 无需依赖 Linux 内核头文件

• 内核中的 list_head 定义在 <linux/list.h>，不能直接在用户空间中使用，因为它依赖于很多内核结构（如 container_of、prefetch、内存屏障等）。

• 简化版中只保留核心逻辑，移除内核复杂依赖，更适合教学和用户态程序调试。

3. 易于学习和调试

• 用户态程序可以用 gdb、printf 等方式方便地调试，学习 list_head 的插入、删除、遍历操作。

• 可以专注理解链表逻辑，而不必关心底层硬件资源或内核调度等复杂因素。

4. 跨平台兼容性更好

• 简化版不依赖内核，在不同平台和系统（如 macOS、Windows 下的 WSL）中也能运行和调试。

5. 利于单元测试或快速原型

• 在开发内核模块之前，可以在用户空间用简化版 list_head 提前验证算法逻辑。

用户空间简化版特点：

• 和内核的一样，提供双向循环链表的基本结构。

• 用 list_add、list_del、list_for_each 等函数模拟内核链表操作。

• 通常会配套实现一个 container_of 宏，简化结构体成员查找。

八、内核链表与普通链表的区别

从编写代码的角度看：

内核链表：

嵌入在结构体内部，相当于在结构体内部的链表

struct student {
    char name[20];
    int age;
    struct list_head list;
};

普通链表：

创建一个专门的链表节点，在链表内部的结构体

typedef struct ListNode {
    int data;               // 数据域（可根据需求修改类型）
    struct ListNode *next;  // 指针域，指向下一个节点
} ListNode;

1. 通用性：

• 你可以把 list_head 内嵌到任何结构体中，只要结构体里有 struct list_head 成员，就能挂进链表。

• 所以它特别适合模块化/插件化开发，广泛用于内核、驱动、队列系统等。

2. 性能：

• 插入和删除操作 不需要遍历链表，也不需要特判头尾节点，始终是 O(1)。

• 它用的是双向循环链表结构（不是 NULL 结尾，而是指向自身），这让很多操作逻辑更简洁。

3. 安全性：

• 它会自动维护前后指针，避免你手动操作 next/prev 出错。

• Linux 内核中还引入了调试辅助机制，能检测非法访问、双重删除等行为。

4. 反向查找能力：

• 通过 list_entry() 或 container_of() 宏，可以轻松从 list_head 节点获取其宿主结构体的地址，实现灵活的对象管理。

 普通链表存在的问题

• 每次写都要重新定义结构体。

• 插入/删除时容易出现各种 bug。

• 遍历复杂，容易出现内存泄漏或悬挂指针。

• 不支持从节点反查宿主结构体，缺乏灵活性。

• 没法通用于多个模块，需要复制粘贴逻辑。

list_head 是一个“通用、可嵌入、性能高、安全”的链表实现，它解决的不是“如何实现链表”，而是“如何设计一套所有模块都能复用、零成本维护的链表管理机制”。

你可以把它理解为 链表机制中的“操作系统级标准库”，比自己写一个链表强得多。