Linux Kernel: 強大又好用的list_head結構

程式設計者在設計一個doubly linked list時，通常會在所宣告的結構裡宣告兩個結構指標，如下所示：

struct student {
    char name[16];
    int id;
    struct student *next, *prev;
};

只要經由prev與next兩個結構指標，便能取得該doubly linked list所有資訊。

然而，Linux kernel並非引用此種作法。因此，Linux kernel定義一通用結構 (struct list_head， include/linux/list.h)，用以實作doubly linked list，此結構相當簡單，如下所示：

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

所以物件student宣告為如下：

struct student
{
    char name[16];
    int id;
    struct list_head list;
};

藉由list變數便能取得doubly linked list所有資訊。

list_head相關Marco與Function

這裡僅介紹較常用的macro與function，如欲進一步得知其它marco請參考include/linux/list.h

LIST_HEAD(name)
struct list_head name = { &(name), &(name) };
將next與prev指到自己，意味著此list為空的。

list_empty(const struct list_head *head)
retrun head->next == head;
檢查此list是否為空的。

list_add(struct list_head *new, struct list_head *head)
head->next->prev = new;
new->next = head->next;
new->prev = head;
head->next = new;
將資料加入至doubly linked list最前端。建議自己動手畫個圖，便可了解這幾個指標指到何處。

list_del(struct list_head *entry)
entry->next->prev = entry->prev;
entry->prev->next = entry->next;
將某一資料從中刪除。

list_entry(ptr,type,member)
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
透過此函式便能算出結構的起始位址，並做結構轉型便能取得結構的資料，此計算方式相當好用啊!!!
以struct student為例，如下所示：

1. (unsigned long)(&((struct student *)0)->member))) ==> 計算出list成員相對位址。通常看到這一個敘述，直覺地覺得應該會記憶體區段錯誤吧 (Segmentation Fault)!? 因為該敘述用NULL的pointer存取list成員，但在(struct student *)0)->member))前面加了&符號，就不會發生記憶體區段錯誤。因為&符號，只意味著存取list的位址，而不是資料，經由此敘述便能取得list的位移植。如下圖所示，該敘述所得之位移植值為20。
   
2. ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) ==> 取得位移植之後，再將list的位址減去位移植，便能取得該結構的起始位址，如下圖所示 (假設結構起始位址為x)，最後再做結構轉型變大功告成。
   
   

list_for_each(pos, head)
for (pos = (head)->next; pos != (head); pos = pos->next)
取得該doubly linked list所有資料。

範例程式
光看這些Macro跟函式可能比較無法有sense，因此小弟寫了一簡單的程式，有興趣的可以下載此範例程式玩玩看。XDD

[Reference]
Understanding the Linux Kernel, Third Edition
Linux Kernel Source Code Version 2.6.20-15