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）

宏 / 函數	作用
`LIST_HEAD(name)`	定義并初始化鏈表頭
`INIT_LIST_HEAD(ptr)`	初始化某個節點（通常用于結構體內嵌）
`list_add(new, head)`	添加到鏈表頭部
`list_add_tail(new, head)`	添加到鏈表尾部
`list_del(entry)`	刪除節點
`list_empty(head)`	判斷鏈表是否為空
`list_for_each(pos, head)`	遍歷鏈表（不獲取結構體）
`list_for_each_entry(ptr, head, member)`	遍歷鏈表（獲取結構體指針）
`list_for_each_entry_safe(...)`	安全遍歷（可刪除）

五、鏈表是循環的

鏈表頭的 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;             // 偏移 0char name[20];      // 偏移 4double gpa;         // 偏移 24（視平臺對齊規則）
};

現在你想知道 gpa 在結構體中的偏移是多少，可以這樣寫：

size_t offset = offsetof(struct student, gpa);

宏展開：

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

拆解：

(struct student *)0：構造一個指向地址 0 的結構體指針（不會真的訪問地址 0，只是為了類型推導）。
((struct student *)0)->gpa：假裝在地址 0 上有一個結構體，訪問其成員 gpa，結果是一個 地址偏移表達式（例如 0 + 24，實際上就是 24 字節偏移）。
&((struct student *)0)->gpa：取這個成員的地址（是個偏移地址，不是真地址）。
(size_t)：強制轉換為整數類型，得到偏移量。

例子

#include <stdio.h>
#include <stddef.h>struct my_struct {char a;         // offset 0int b;          // offset 4 (由于對齊)double c;       // offset 8
};int main() {printf("offset of a = %zu\n", offsetof(struct my_struct, a)); // 0printf("offset of b = %zu\n", offsetof(struct my_struct, b)); // 4printf("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);}
}

宏名	作用
`container_of`	從成員指針推導出結構體指針
`list_entry`	從 `list_head*` 拿到結構體指針
`list_for_each_entry`	遍歷鏈表中包含 `list_head` 的結構體元素
`list_for_each_entry_safe`	安全遍歷鏈表中包含 `list_head` 的結構體元素

為什么要用用戶空間簡化版不依賴內核的用戶態實現？

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;

特性	優勢
通用性	可嵌入任何結構體，實現任意鏈表類型。
內核標準	幾乎所有內核鏈表都是用它做的

特性	`list_head`（內核鏈表）	普通鏈表（如學生手寫的）
?支持雙向鏈表	默認支持	需自己實現
節點結構通用	通用結構體嵌入	每種鏈表都得重新設計
插入/刪除效率高	O(1)，不需要額外判斷	需特判頭/尾/空鏈表等情況
安全性高	通過宏屏蔽指針錯誤	易出現野指針、空指針
支持遍歷宏	`list_for_each` 等宏方便遍歷	手寫 `while (node)` 不易維護
支持從節點找回宿主結構體	`container_of()` 宏可找回宿主結構體	需要自己手動維護映射關系
易于模塊化封裝	一套鏈表機制通用于所有模塊	每個模塊都得造輪子