【Linux 】Kernel如何實現泛型Linked List

一直以為Linked List是最簡單最基礎的資料結構之一，寫法就是很標準的struct裡面塞data跟指向下個節點的指標。

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

但這個作法有個小問題，就是直接把data的型別寫死在struct裡面，不能動態替換，如果哪天data要換型別，就要寫一個新的struct來處理，很顯然這是不太好的設計。但我也一直都認為這就是C的特性，沒有高階語言的泛型，就只能乖乖接受。

直到學習Linux後才發現，他們用了一個超聰明的方法來實現類似泛型的功能，就是把包裝的順序反過來，Node的struct裡不再包含data欄位，只留下很單純的下個節點的指標，然後將Node本身嵌入進原本data的struct裡面當作一個欄位。

struct list_head {
    struct list_head *next;
};

struct my_data {
    int data;
    struct list_head list;
};

更厲害的操作還在後面，就是當我們loop through List找到目標節點的時候，要如何才能拿到真正的data呢？Linux Kernel首先透過offsetof這個macro找出Node在data struct中的offset，再用container_of macro去把node的記憶體位址扣掉offset回推出實際data的指標，從而拿到真正的資料。

#define offsetof(type, member)          ((size_t) &((type *)0)->member)
#define container_of(ptr, type, member) ((type *)( (char *)(ptr) - offsetof(type, member) ))

struct my_data instance1 = { .data = 42, .list = { .next = NULL } };

struct list_head *target_node = &instance1.list;

struct my_data *real_data = container_of(target_node, struct my_data, list);

printf("Data: %d", real_data->data);