無處不在的container_of
linux 內核中定義了一個非常精煉的雙向循環鏈表及它的相關操作。如下所示：
struct list_head {struct list_head* next, * prev;
};
ubuntu 12.04 中這個結構定義在 /usr/src/linux-headers-3.2.0-24-generic/include/linux/types.h 中，各種操作定義在 list.h 中。可以通過 grep “struct list_head {” 來查找到，也可以使用 ctags 在 include 目錄下生成 tags 文件，然后在 tags 里面查找到。
這個鏈表只有指針域，沒有數據域，所以我們不能直接拿來使用。而是需要把這個結構體嵌在我們自己定義的結構體里，可以放在任意位置，開頭，中間或結尾。比如：
struct book {int sn;char name[NAMESIZE];int price;struct list_head node; //內核鏈表結構體放在最后
};
我們使用內核提供的鏈表操作函數或宏來快速地建立一個雙向鏈表，如下所示：
int main()
{struct book* bp;int i;LIST_HEAD(head); //宏，建立頭結點for(i = 0 ; i < 3; i++){bp = (struct book*)malloc(sizeof(struct book)); /*if error*/bp->sn = i;snprintf(bp->name, NAMESIZE, "book%d", i);bp->price = rand()%60 + 20;/*insert*/list_add(&bp->node, &head); //將該結點插入鏈表}/*TODO: travel*/return 0;
}
注意， LIST_HEAD(head) 不是函數，而是宏，所以不要對它傳了一個沒有定義的變量感到疑惑。這個宏的定義如下：
#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \struct list_head name = LIST_HEAD_INIT(name)
它的作用是生成了一個變量名為 name 的頭結點，并把指針域的值都初始化為指向自身。
list_add 函數實現把節點插入到以 head 為頭結點的鏈表中。
上述一段簡短的代碼，快速地生成了一個可供自己使用的雙向循環鏈表，其結構如下圖所示：
從圖中可以看到，每個節點中的 next 和 pre 指針指向的都是另一個結點中的 node 成員的地址，而不是整個節點的首地址，所以，問題就來了，我們要訪問節點中的其它成員怎么辦？那我們就必須通過 node 成員的地址，獲取它所在的節點的首地址。方法很簡單，用 node 成員的地址減去它相對首地址的偏移量即可，假設某個節點的 node 成員的地址是 ptr，偏移量暫時先用 offset(node, struct book) 來表示，則公式如下：
(struct book*) ( (char*)ptr - offset(node, struct book) )
~~~~~~~~~~~~~~~ ~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~類型轉換 轉成指向 char 的指針 node 成員在結構體中的偏移量
那偏移量又該如何來計算呢，假想 struct book 這個結構體的首地址為 0，那么 node 節點的地址不就是偏移量嗎？因此我們可以把地址 0 先轉換成指向 struct book 的指針，再從這個指針取它的成員 node 的地址，就可以計算得偏移量，公式如下：
((size_t) &((struct book*)0)->node)~~~~~~~~ ~ ~~~~~~~~~~~~~~~~~
轉成無符號整數 取址
也許不少人和我一樣，有一個疑惑，地址 0 轉換成指針，不是 NULL 嗎，用它去訪問成員，不是非法的嗎？我一開始也百思不得其解，后來明白了，取成員的地址，并不等于訪問該成員。我們可以用下面一段程序來驗證一下：
#include <stdio.h>struct st
{int a; //0char b; //4int c; //8
};int main()
{printf("c addr : %d\n", &((struct st*)0)->c);printf("c value : %d\n", ((struct st*)0)->c);return 0;
}
在 ubuntu 12.04 32bit 上用 GCC 4.6.3 編譯后運行的結果：
believe@ubuntu:~$ ./a.out
c addr : 8
段錯誤 (核心已轉儲)
我是這么來理解的，地址 0 開始的這一段內存空間，就像是透明的充滿機關的盒子，當里面放著結構體時，即使我們不打開這個盒子，從外面也可以知道里面的某個成員的位置(即地址)，但你想打開盒子取出某個成員看看它的具體的值是多少時，卻是萬萬不可的，會中箭而亡！
通過上面的步驟，我們就取到了節點的首地址，內核它也是這么做的，把上面表達式里的 struct book 換成 TYPE/type，把 node 換成 MEMBER/member，就是內核定義的樣子：
// 定義在 include/linux/list.h 中
#define list_entry(ptr, type, member) \container_of(ptr, type, member)// 定義在 include/linux/kernel.h 中
#define container_of(ptr, type, member) ({ \(type*)( (char*)ptr - offsetof(type,member) );})// 定義在 include/linux/stddef.h 中
// 巧妙之處在于將地址0強制轉換為type類型的指針，從而定位到member在結構體中偏移位置。編譯器認為0是一個有效的地址，從而認為0是type指針的起始地址。
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE*)0)->MEMBER)
上面 container_of 為了便于理解，進行了簡化，實際完整的定義是這樣的：
/*** container_of - cast a member of a structure out to the containing structure* @ptr: the pointer to the member.* @type: the type of the container struct this is embedded in.* @member: the name of the member within the struct.**/
#define container_of(ptr, type, member) ({ \const typeof( ((type *)0)->member ) * __mptr = (ptr); \(type *)( (char *)__mptr - offsetof(type,member) );})
container_of 宏分為兩部分，
第一部分：const typeof( ((type *)0)->member ) *__mptr = (ptr);
通過 typeof 定義一個member指針類型的指針變量 __mptr，（即 __mptr 是指向 member 類型的指針），并將 __mptr 賦值為 ptr。
第二部分： (type * )( (char * )__mptr - offsetof(type,member) ) ，通過 offsetof 宏計算出 member 在 type 中的偏移，然后用 member 的實際地址 __mptr 減去偏移，得到 type 的起始地址，即指向 type 類型的指針。
第一部分的目的是為了將統一轉換為 member 類型指針。
它增加了一句，作用是通過 GCC 特有的類型運算符 typeof，取得 member 成員的類型，定義了一個此類型的指針 __mptr，并使它的值等于 ptr，后面就用 __mptr 替代 ptr 操作。這句話我想其實是多余的，可能是為了做最大的保護吧，可以通過下面這個例子來理解為什么要重新定義一個變量。
用 define 定義一個最簡陋 MAX(a,b) 宏，像下面這樣：
#define MAX(a,b) a > b ? a : b
這樣的定義不堪一擊，MAX(a+1, b) 的調用就會讓它出錯。
在 windows 下，最嚴謹的定義也不過如此了：
#define MAX(a,b) ((a)>(b)?(a):(b))
可是這樣的定義，在面對這樣的調用時，依然無能為力：MAX(++a, ++b)，大家可以實驗一下，其中的較大值會被加 2。
但在 linux 下，使用 typeof 運算符，可以解決這個問題：
#define MAX(a,b) ({typeof(a) A=a,B=b; A > B ? A : B;})
不過這種在 () 里包含 {} 的定義方法并不被標準 C 支持。
對于上面的這種定義，或許還是有人會有這樣的疑問，假如調用 MAX(++a, ++b)，a 還是會被加兩次啊，typeof(++a) 時會加一次，A=++a 時又加一次。其實不會，因為 typeof 并不是一個運行時的函數或運算符，它和 sizeof 一樣，是在編譯的時候就確定了。下面這個例子可以驗證：
int main()
{int a = 5;typeof(++a) b = 3; //等同于 int b = 3;printf("a = %d, b = %d\n", a, b);return 0;
}---------------
運行結果：
a = 5, b = 3
如果我們把內核鏈表結構體放在我們自己的結構體的開頭，其實就不需要這兩個宏了，只需要進行類型轉換即可。
另外，在 windows 內核中也有類似的宏，由于 windows 沒有 typeof 運算符，所以就顯得簡單了一些，定義如下：
#define CONTAININT_RECORD(address, type, field) \((type*)((PCHAR)(address) - (PCHAR)(&((type*)0)->field)))
下面的程序將完整地展示如何使用 container_of 實現遍歷。
int main()
{struct list_head *cur;struct book* bp;int i;LIST_HEAD(head); //宏，建立頭結點for(i = 0 ; i < 3; i++){bp = (struct book*)malloc(sizeof(struct book)); /*if error*/bp->sn = i;snprintf(bp->name, NAMESIZE, "book%d", i);bp->price = rand()%60 + 20;/*insert*/list_add(&bp->node, &head); //將該結點插入鏈表}/*travel*/__list_for_each(cur, &head)//這也是一個宏，展開后是這樣：for (cur = (&head)->next; cur != &head; cur = (&head)->next){bp = list_entry(cur, struct book, node);//list_entry 與 container_of 等價printf("sn = %d, name = %s, price = %d\n", bp->sn, bp->name, bp->price);}return 0;
}
;std::cin.tie(nullptr);）)
