沒有容量的容器——linux核心的連結清單（sina部落格移入）

在看linux核心源代碼的時候，經常在一些結構裡看見struct list_head結構。找了一下源代碼，在list.h中，有對這個結構的定義，這個就是linux核心中的連結清單結構。

仔細看看這個結構，就可以發現它和以前在講資料結構的時候的連結清單有很大的差别——沒有資料。list_head結構中僅僅包含了兩個自己結構的指針，用來組建雙向循環連結清單。最大的疑問就是，這個連結清單結構如何儲存資料呢？

在list.h中，定義了list_entry宏。這個宏就是用來提取包含連結清單項的結構的指針。從list_entry宏的定義可以看到，它僅僅調用了kernel.h中的container_of()宏。後者真正實作了通過連結清單結構來擷取包含連結清單的結構的位址（指針）。

container_of(ptr, type, member)宏需要三個參數。ptr：指向連結清單的指針；type：包含連結清單項結構的類型；member：連結清單項在結構中的名稱。

其中的實作有兩句語句：

const typeof( ((type *)0)->member ) *__mptr = (ptr); //聲明臨時變量__mptr，儲存連結清單的指針。這個變量的類型由gcc擴充函數typeof從結構的成員變量member中擷取

//((type *)0)->member将位址0強制轉換為結構的指針，并擷取連結清單的對象

(type *)((char*) __mptr – offsetof(type, member)); //将上句擷取到的位址減去連結清單項在結構中的偏移量，得到結構的真實位址，并将這個位址轉換成所需類型結構的指針

//offsetof(type, member)函數定義在stddef.h中，它傳回member在結構type中的偏移量，傳回值為size_t

通過這宏，就傳回了包含連結清單項的結構的指針，然後就可以通過這個指針來通路結構中的資料了。這樣定義的連結清單，對于沒有模闆的c語言來說，可以有效的避免重複寫很多包含不同資料類型的結構，不用在為每種不同的資料類型寫一個連結清單節點項了。

(參考文章：http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/index.html)

轉載自：https://coolex.info/blog/75.html