Linux 核心風格泛型鏈表在 C 語言中的實現原理與完整實作

編輯：關於C語言

前言：為什麼 C 語言需要泛型鏈表？

C 語言缺乏模板與泛型機制，但 Linux 核心巧妙利用 struct list_head 實現了型別無關的鏈表容器。近期閱讀核心原始碼時發現大量使用此結構，決定自行實作一個雙向循環泛型鏈表以深入理解其設計精髓。

核心設計：`list_head` 嵌入式節點

傳統鏈表節點包含資料與指標：

struct Node { int data; struct Node *next; };

Linux 核心反轉設計：**鏈表節點嵌入資料結構中**，而非資料嵌入節點：

struct dclist_head {          // 純粹的鏈表節點，無業務資料
    struct dclist_head *prev;
    struct dclist_head *next;
} dclist_head_t;

struct Student {              // 使用者自定義資料結構
    int id;
    dclist_head_t entry;      // 嵌入鏈表節點
};

泛型鏈表結構示意圖

關鍵技術 1：`list_entry` 宏 — 從節點反推資料結構位址

鏈表操作僅涉及 dclist_head_t*，但使用者需要存取完整的 Student 結構。解決方案：計算資料結構起始位址。

#define list_entry(ptr, type, member) \
    ((type *)((char *)(ptr) - (char *)(&((type *)0)->member)))

位址計算原理圖

**原理**：(type *)0 建立虛擬基址 0，->member 取得成員在結構中的偏移量，& 取該偏移位址。實際節點位址減去偏移量即得結構起始位址。強轉 char* 以進行位元組級運算，最後轉回 type*。

關鍵技術 2：函式指標回呼 — 型別無關的操作

鏈表核心不處理具體資料，僅提供遍歷、插入、刪除等結構性操作。資料相關邏輯（列印、釋放、比較）由使用者透過函式指標注入：

void treaverse(dclist_head_t *head, void (*pfun)(dclist_head_t *node));
void dc_remove(dclist_head_t *head, void (*pfun)(dclist_head_t *node));

完整實作程式碼

頭檔：dclist_head.h

#ifndef DLIST_HEAD
#define DLIST_HEAD

#define list_entry(ptr, type, member) \
    ((type *)((char *)(ptr) - (char *)(&((type *)0)->member)))

typedef struct dclist_head {
    struct dclist_head *prev;
    struct dclist_head *next;
} dclist_head_t;

void init(dclist_head_t *head);
void append(dclist_head_t *head, dclist_head_t *node);
void treaverse(dclist_head_t *head, void (*pfun)(dclist_head_t *node));
void dc_remove(dclist_head_t *head, void (*pfun)(dclist_head_t *node));

#endif

實作：dclist_head.c

#include 
#include 
#include "dclist_head.h"

void init(dclist_head_t *head) {
    if (head) { head->prev = NULL; head->next = NULL; }
}

void append(dclist_head_t *head, dclist_head_t *node) {
    if (!head) { printf("error\n"); exit(1); }
    if (!head->prev && !head->next) {  // 空鏈表
        head->prev = head->next = node;
        node->prev = node->next = head;
    } else {                           // 尾插（頭節點前）
        dclist_head_t *tmp = head->prev;
        tmp->next = node;
        node->prev = tmp;
        node->next = head;
        head->prev = node;
    }
}

void treaverse(dclist_head_t *head, void (*pfun)(dclist_head_t *node)) {
    if (!head || !head->next) return;
    dclist_head_t *tmp = head->next;
    while (tmp != head) { pfun(tmp); tmp = tmp->next; }
}

void dc_remove(dclist_head_t *head, void (*pfun)(dclist_head_t *node)) {
    treaverse(head, pfun);  // 僅呼叫使用者提供的釋放函式
}

測試程式：main.c

#include 
#include 
#include "dclist_head.h"

typedef struct {
    int id;
    dclist_head_t entry;
} student_t;

void print(dclist_head_t *ptr) {
    student_t *stu = list_entry(ptr, student_t, entry);
    if (stu) printf("student id = %d\n", stu->id);
}

void free_node(dclist_head_t *ptr) {
    if (!ptr) return;
    student_t *node = list_entry(ptr, student_t, entry);
    free(node);
}

student_t* make_node(int id) {
    student_t *stu = malloc(sizeof(student_t));
    if (stu) stu->id = id;
    return stu;
}

int main(void) {
    dclist_head_t list;
    init(&list);

    for (int i = 0; i < 5; i++) {
        student_t *stu = make_node(i);
        if (stu) append(&list, &stu->entry);
    }

    treaverse(&list, print);
    dc_remove(&list, free_node);
    return 0;
}