第零章：扯扯淡

　　出一個有意思的題目：用一個宏定義FIND求一個結構體struct里某個變量相對struc的編移量，如

struct student{    int a;    //FIND(struct student,a) 等于0     char b;    //FIND(struct student,b）等于4    double c;};

參考答案：#define FIND(type,member) ((size_t)&((type*)0)->member)

我這樣理解（可能不太正確）：

(type*)0，0在編譯過程中會用一個int臨時變量裝一下，現在把這個臨時變量轉化成了指針，指向假想的在地址0處存在的結構體，其實是沒有的。

((type*)0)->member就訪問這個結構體的變量了，

&((type*)0)->member就取得了這個變量的地址了，因為假想這個結構體放在0地址處嘛，所以這個變量的地址就是相對于結構體的偏移，

(size_t)&((type*)0)->member再把這個地址轉化成size_t類型（typedef unsigned int size_t），因為地址是0x00000004這樣形式的，轉化成無符號整形，即得偏移。

測試如下：

#include <iostream>#define FIND(type,member) ((size_t)&((type*)0)->member)struct student{    int a;    //FIND(struct student,a) 等于0     char b;    //FIND(struct student,b）等于4    double c;};using namespace std;int main(void){    cout << sizeof(size_t) << endl;    cout << FIND(struct student, a) << endl << FIND(struct student, b)<<endl<< FIND(struct student, c) << endl;    cin.get();}

輸出為 4 0 4 8

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

　　第一章：普通鏈表

　　正常的的鏈表不是這樣嘛：

/*表示書的結構體*/struct Book{    int bkId;    string bkName;    struct Book *PRev;    //指向鏈表中前一個節點    struct Book *next;    //指向鏈表中后一個節點};

然后再具體寫對struct Book結構體的具體操作，如添加一個節點啊，刪除一個啊等等。設想：如果有幾十個甚至上百個鏈表，那不是搞死了嘛！要為每一個特定類型的鏈表寫一個具體的操作，程序員怎么會做這么愚蠢的事情呢？于是就有了帥帥的Linux內核鏈表管理法。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

　　第二章：Linux內核鏈表

　　Linux內核鏈表數據結構如下：（在我的M:/linux-3.14.5/include/linux下types.h文件中）

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

正常的鏈表是把指向前后節點的指針放到鏈表節點中，但Linux內核不是這么干的，它把上面的struct list_head塞到數據結構中，這樣每一個struct list_head就成為了鏈表節點，其中next指向下一個struct list_hand，prev指向前一個struct list_hand，這樣是不是很帥？但關鍵是要看它怎么使用。現在來看我的struct Book，如果要弄一個它的鏈表，只要這樣：

struct list_head {    struct list_head *next, *prev;};/*表示書的結構體*/struct Book{    int bkId;    string bkName;    struct list_head list;        //所有的Book結構體形成鏈表};

我這是在抄襲哈！最關鍵的是要看到底怎么才能組成鏈表以及到底怎么樣才能操作鏈表。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

　　第三章：Linux內核鏈表創建與初始化

　　創建一個鏈表也就是創建一個鏈表頭，這個頭也是一個struct list_head，源代碼有些宏就省去了。（在我的M:/linux-3.14.5/include/linux下list.h文件中）

/*初始化鏈表*/static inline void INIT_LIST_HEAD(struct list_head *list){    list->next = list;    list->prev = list;}

其實就是讓頭的前后指針都指向自己啦。目前我的代碼如下：

#include <string>using std::string;/*鏈表節點*/struct list_head {    struct list_head *next, *prev;};/*表示書的結構體*/struct Book{    int bkId;    string bkName;    struct list_head list;        //所有的Book結構體形成鏈表};/*初始化鏈表*/static inline void INIT_LIST_HEAD(struct list_head *list){    list->next = list;    list->prev = list;}

#include <iostream>#include "myList.h"using namespace std;int main(void){    struct list_head MyBkList;    //創建我的鏈表頭    INIT_LIST_HEAD(&MyBkList);   //初始化這個鏈表    cin.get();}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

　　第四章：Linux內核鏈表插入

　　（1）插入節點

　　上面只是建立了一個空鏈表，現在要插入數據了。

　　內核提供了把一個新structlist_head節點插入到兩個節點之間的方法：

/** Insert a new entry between two known consecutive entries.** This is only for internal list manipulation where we know* the prev/next entries already!*/static inline void __list_add(struct list_head *new1,struct list_head * prev,struct list_head * next){    next->prev = new1;    new1->next = next;    new1->prev = prev;    prev->next = new1;}

這里很抱歉啊，我的是C++項目，new是語言的關鍵詞，所以把new換成了new1，內核源代碼中上面的都是new。這個函數是其他插入函數都要調用的，其實就是提取了前插、后插的共同點啦，這個真美！

　　（2）尾插節點

/** * list_add_tail - add a new entry * @new: new entry to be added * @head: list head to add it before * * Insert a new entry before the specified head. * This is useful for implementing queues. */static inline void list_add_tail(struct list_head *new, struct list_head *head){    __list_add(new, head->prev, head);}

尾插這個方法其實就是在head節點之前插入一個節點啦，最終調用__list_add(new, head->prev, head);表明是在head前一個節點和head節點之間插入一個節點。

　　設想：剛開始只有一個鏈表頭結點structlist_headhead，head的前后都是指向自己的，現在調用list_add_tail(struct list_head *new, struct list_head *head)，即__list_add(new, head->prev, head);鏈表成了兩個節點，并且都是各自的相互指向對方：

因為這是個雙向鏈表，可以看做new1加到了head后面。再調用一個這個函數list_add_tail(struct list_head *new, struct list_head *head)：

所以可以看做：把head當隊頭，每次修改的都是head的prev指針，每次都在隊尾添加，相當于隊列啦！現在代碼是：

#include <iostream>#include "myList.h"using namespace std;int main(void){    struct list_head MyBkList;    //創建我的鏈表頭    INIT_LIST_HEAD(&MyBkList);   //初始化這個鏈表    /*創建新書結構體*/    struct Book bk1;    bk1.bkId = 1;    bk1.bkName = "book1";    list_add_tail(&bk1.list, &MyBkList);        //把新書1加到頭結點MyBkList后面    struct Book bk2;    bk2.bkId = 2;    bk2.bkName = "book2";    list_add_tail(&bk2.list,&MyBkList);    //把書2加到bk1與MyBkList之間，把MyBkList看做頭，則為MyBkList->bk1->bk2(按照節點next指針，MyBkList的next指針是沒有變的，MyBkList的prev指針變了)    cin.get();}

　　（3）頭插

　　內核還有個頭插，相當于每次都插在了head的后面了，即每次都修改了head的next指針，每次都在前面插，相當于棧啦！和上面的基本差不多，不多寫了。

/** * list_add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */static inline void list_add(struct list_head *new, struct list_head *head){    __list_add(new, head, head->next);}

其實這個更好理解，每次都在head節點和head節點后面一個節點之前插入一個節點。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

　　第四章：從list_head結構體到包含它的給定數據結構

　　上面的都是針對struct list_head操作的，插入也只是把給定結構體的的struct list_head成員傳遞給函數，但如何才能獲得包含struct list_head的結構體呢？畢竟真正要訪問的時候我們想訪問到我們真正關心的數據。好了，下面一步一步來

　　container_of（）（在我的M:/linux-3.14.5/include/linux下kernel.h文件中）

/** * 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) );})

它已經描述很清楚，由結構體包含的成員獲得包含這個成員的結構體，ptr是指向結構體成員的指針，type是包含給定成員的結構體名稱，member是結構體所含指定成員的的在結構體中的名字。

typeof：是g++對c / c++語法的一個擴展，用來靜態獲取參數類型，在windows下面一直報錯，我就遷徙到linux，用g++就ok比如：

int a = 3;

typeof(a) b = 4; // 相當于 int b = 4;

offsetof：如下，是內核源代碼定義的宏(在我的M:/linux-3.14.5/include/linux下stddef.h文件中)

#undef offsetof#ifdef __compiler_offsetof#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)#else#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)#endif

offsetoff(struct_t, member)宏的作用就是獲得成員member在類型struct_t中的偏移量。是不是第零章扯扯淡差不多？？？

好了，其實理解了第零章的扯扯淡就大概知道怎么做了：獲得member相對于type的偏移，再拿給定的member地址減去這個便宜不就是這個結構體的地址嗎？這里主要注意一些參數類型，因為這個宏針對各種結構體類型都可以的：

typeof(((type *)0)->member)：獲得type結構體中member成員名所對應的具體類型，是int呢還是struct list_head呢等等，如果對應我的程序，type是structBook，member是struct list_head類型的list，則這里獲得的是struct list_head；

const typeof(((type *)0)->member) *__mptr = (ptr);看看對應我的程序就懂了，即 const struct list_head *__mptr = ptr ,就是定義了一個結構體中member所對應的類型的指針，并把ptr賦給它，因為在使用這個宏的時候傳遞的ptr只是一個大概0xffffffff形式的member的地址，不知道具體類型，member也只是自己起的名字。現在 __mptr是有身份的地址啦！

(type *)((char *)__mptr - offsetof(type, member))：對應我的程序就是那structBook里面的list變量地址減去structBook里面list的偏移，得到的就是這個結構體的地址，再強制轉換成struct Book類型。搞定！但還是不明白為什么要進行ptr到__mptr的轉換......

這里利用編譯器技術的小技巧，即先求得結構成員在與結構中的偏移量，然后根據成員變量的地址反過來得出屬主結構變量的地址。

下接：Linux 內核 鏈表 的簡單模擬（2）