您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

Linux 內核風格通用鏈表在 C 語言中的實現原理與實戰

編輯：關於C

前言：為什麼需要「內核式」通用鏈表？

C 語言無泛型，傳統鏈表要么在節點內固化數據類型（導致代碼重複），要么用 void* 攜帶數據（需頻繁強轉、分配額外內存）。Linux 內核採用反向嵌入設計：鏈表節點嵌入數據結構，而非數據嵌入節點，實現零開銷、類型安全的通用容器。

一、核心數據結構

/* 內核 list_head 精簡版 */
struct list_head {
    struct list_head *next, *prev;
};

/* 業務數據結構：鏈表節點作為首個成員嵌入 */
struct IntNode {
    struct list_head list;  // 必須是第一個成員
    int data;
};

二、關鍵宏：`offsetof` 與 `container_of`

如何從 list_head* 反推包含它的結構體地址？

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

#ifndef container_of
#define container_of(ptr, TYPE, MEMBER) ({ \
    const typeof(((TYPE *)0)->MEMBER) *__mptr = (ptr); \
    (TYPE *)((char *)__mptr - offsetof(TYPE, MEMBER)); \
})
#endif

offsetof：利用零地址結構體計算成員偏移，編譯期常量
container_of：用指針減去偏移，得到外層結構體起始地址
關鍵前提：list_head 必須是結構體第一個成員，此時偏移為 0，container_of 退化為直接類型轉換，效率最高

三、基本操作 API

/***** 初始化 *****/
#define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr)->prev = (ptr); } while (0)

/***** 插入：在 head 之後添加 new *****/
static inline void list_add(struct list_head *new, struct list_head *head) {
    new->next = head->next;
    new->prev = head;
    head->next->prev = new;
    head->next = new;
}

/***** 刪除 *****/
static inline void list_del(struct list_head *entry) {
    entry->next->prev = entry->prev;
    entry->prev->next = entry->next;
    entry->next = entry->prev = NULL;  // 防止懸空指針
}

/***** 遍歷宏 *****/
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

#define list_entry(ptr, TYPE, MEMBER) container_of(ptr, TYPE, MEMBER)

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

四、完整使用示例

#include 
#include 

/* 假設上述結構與宏已定義 */

int main() {
    struct list_head head;
    INIT_LIST_HEAD(&head);

    /* 創建 3 個節點 */
    for (int i = 1; i <= 3; i++) {
        struct IntNode *node = malloc(sizeof(*node));
        node->data = i * 10;
        list_add(&node->list, &head);  // 頭插法，順序為 30,20,10
    }

    /* 遍歷打印 */
    struct IntNode *cur;
    list_for_each_entry(cur, &head, list) {
        printf("data = %d\n", cur->data);
    }

    /* 刪除並釋放 */
    struct list_head *pos, *n;
    list_for_each_safe(pos, n, &head) {
        cur = list_entry(pos, struct IntNode, list);
        list_del(pos);
        free(cur);
    }
    return 0;
}

五、優勢總結

特性	傳統 void* 方案	內核式嵌入方案
類型安全	編譯期不檢查，運行期崩潰	編譯期類型檢查
內存分配	兩次 malloc（節點+數據）	一次 malloc（整體）
緩存局部性	差（數據分離）	優（數據緊湊）
代碼復用	需強轉，易出錯	宏封裝，零開銷