接上一篇Linux 內核 鏈表 的簡單模擬（1）

　　第五章：Linux內核鏈表的遍歷

/*** list_for_each    -    iterate over a list* @pos:    the &struct list_head to use as a loop cursor.* @head:    the head for your list.*/#define list_for_each(pos, head) /for (pos = (head)->next; pos != (head); pos = pos->next)

這是遍歷鏈表的一個方法，其實就是一個for循環的宏啦！寫得很清楚。但是這些操作的還是struct list_head，跟我要的結構體沒有半毛錢關系，怎么辦？繼續看：

/*** list_entry - get the struct for this entry* @ptr:    the &struct list_head pointer.* @type:    the type of the struct this is embedded in.* @member:    the name of the list_struct within the struct.*/#define list_entry(ptr, type, member) /    container_of(ptr, type, member)

這個就是由我們自定義的結構體中包含的struct list_head獲得結構體的方式，其實就是上一篇博客的container_of的第二個名字啦！container_of到了這山溝里就換了一個很土的名字啦！

好了，下面看代碼就一清二楚了：

    struct list_head *p;    //pointer to each struct list_head    struct Book *pb;        //pointer to struct Book        list_for_each(p,&MyBkList)    {        pb = list_entry(p, struct Book,list);        cout << pb->bkId << "  " << pb->bkName << endl;    }

輸出：

#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;}/** 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;}/*** 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 *new1, struct list_head *head){    __list_add(new1, head->prev, head);}/*** 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 *new1, struct list_head *head){    __list_add(new1, head, head->next);}/*** 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)); })/*** list_for_each    -    iterate over a list* @pos:    the &struct list_head to use as a loop cursor.* @head:    the head for your list.*/#define list_for_each(pos, head) /for (pos = (head)->next; pos != (head); pos = pos->next)/*** list_entry - get the struct for this entry* @ptr:    the &struct list_head pointer.* @type:    the type of the struct this is embedded in.* @member:    the name of the list_struct within the struct.*/#define list_entry(ptr, type, member) /    container_of(ptr, type, member)/*** list_first_entry - get the first element from a list* @ptr:    the list head to take the element from.* @type:    the type of the struct this is embedded in.* @member:    the name of the list_struct within the struct.** Note, that list is expected to be not empty.*/#define list_first_entry(ptr, type, member) /    list_entry((ptr)->next, type, member)/*** list_next_entry - get the next element in list* @pos:    the type * to cursor* @member:    the name of the list_struct within the struct.*/#define list_next_entry(pos, member) /    list_entry((pos)->member.next, typeof(*(pos)), member)/*** list_for_each_entry    -    iterate over list of given type* @pos:    the type * to use as a loop cursor.* @head:    the head for your list.* @member:    the name of the list_struct within the struct.*/#define list_for_each_entry(pos, head, member)                /for (pos = list_first_entry(head, typeof(*pos), member);    /    &pos->member != (head);                    /    pos = list_next_entry(pos, member))#undef offsetof#ifdef __compiler_offsetof#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)#else#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)#endif

#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Ö?Õë±äÁË)    struct Book bk3 = { 3, "book3" };    list_add(&bk3.list, &MyBkList);        //°ÑÊé3ŒÓµœheadÖ®ºó£¬Œ?headµÄnextÖ?Õë    struct list_head *p;    //pointer to each struct list_head    struct Book *pb;        //pointer to struct Book        list_for_each(p,&MyBkList)    {        pb = list_entry(p, struct Book,list);        cout << pb->bkId << "  " << pb->bkName << endl;    }   /*    list_for_each_entry(pb, &MyBkList, list)    {        cout << pb->bkId << "  " << pb->bkName << endl;    }*/    cin.get();}

還有一個人更漂亮的遍歷函數list_for_each_entry：

/*** list_first_entry - get the first element from a list* @ptr:    the list head to take the element from.* @type:    the type of the struct this is embedded in.* @member:    the name of the list_struct within the struct.** Note, that list is expected to be not empty.*/#define list_first_entry(ptr, type, member) /    list_entry((ptr)->next, type, member)/*** list_next_entry - get the next element in list* @pos:    the type * to cursor* @member:    the name of the list_struct within the struct.*/#define list_next_entry(pos, member) /    list_entry((pos)->member.next, typeof(*(pos)), member)/*** list_for_each_entry    -    iterate over list of given type* @pos:    the type * to use as a loop cursor.* @head:    the head for your list.* @member:    the name of the list_struct within the struct.*/#define list_for_each_entry(pos, head, member)                /for (pos = list_first_entry(head, typeof(*pos), member);    /    &pos->member != (head);                    /    pos = list_next_entry(pos, member))

使用起來更好看：

　　struct Book *pb;        //pointer to struct Book    list_for_each_entry(pb, &MyBkList, list)    {        cout << pb->bkId << "  " << pb->bkName << endl;    }

當然還有反向遍歷等，就不多贅述了。

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

　　第六章：Linux內核鏈表刪除

　　先來看看這個基本的刪除節點的函數，這是其他刪除函數的基礎。其實這個刪除函數和添加節點到鏈表的函數是對應的，添加的基本函數不也是以前后指針為參數并把節點添加到中間嗎？Linux內核就是帥！

/* * Delete a list entry by making the prev/next entries * point to each other. * * This is only for internal list manipulation where we know * the prev/next entries already! */static inline void __list_del(struct list_head * prev, struct list_head * next){    next->prev = prev;    prev->next = next;}

下面看調用上面函數的函數，其實list_del()是最常用的函數了，其他函數也只是鋪墊：

/** * list_del - deletes entry from list. * @entry: the element to delete from the list. * Note: list_empty() on entry does not return true after this, the entry is * in an undefined state. */#ifndef CONFIG_DEBUG_LISTstatic inline void __list_del_entry(struct list_head *entry){    __list_del(entry->prev, entry->next);}static inline void list_del(struct list_head *entry){    __list_del(entry->prev, entry->next);    entry->next = LIST_POISON1;    entry->prev = LIST_POISON2;}#elseextern void __list_del_entry(struct list_head *entry);extern void list_del(struct list_head *entry);#endif

其中，LIST_POISON1、LIST_POISON2 在我的M:/linux-3.14.5/include/linux下poison.h文件中:

/* * These are non-NULL pointers that will result in page faults * under normal circumstances, used to verify that nobody uses * non-initialized list entries. */#define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)#define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)

/* * Architectures might want to move the poison pointer offset * into some well-recognized area such as 0xdead000000000000, * that is also not mappable by user-space exploits: */#ifdef CONFIG_ILLEGAL_POINTER_VALUE# define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)#else# define POISON_POINTER_DELTA 0#endif

上面的一些宏定義作用是：調用 __list_del_entry(struct list_head *entry)刪除一個給定節點，這個函數會調用__list_del(struct list_head * prev, struct list_head * next)，這樣使得待刪除的節點的前后節點因為正確連到鏈表里面而沒有了問題了，但是待刪除節點還是的結構體還是在的，其實并沒有刪除它，只是把它從鏈表里面踢出去了。為了防止意外訪問到這個節點的前后節點（因為它已經不在鏈表中了）而出錯，就給它的前后指針賦了一個非空但訪問會引起頁面錯誤的指針，表明小心中毒哦！

目前為止代碼如下：

#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Ö?Õë±äÁË)    struct Book bk3 = { 3, "book3" };    list_add(&bk3.list, &MyBkList);        //°ÑÊé3ŒÓµœheadÖ®ºó£¬Œ?headµÄnextÖ?Õë    struct list_head *p;    //pointer to each struct list_head        /*    list_for_each(p,&MyBkList)    {        pb = list_entry(p, struct Book,list);        cout << pb->bkId << "  " << pb->bkName << endl;    }*/   struct Book *pb;        //pointer to struct Book    list_for_each_entry(pb, &MyBkList, list)    {        cout << pb->bkId << "  " << pb->bkName << endl;    }      cout<<"------------------------------------"<<endl;      struct Book bk4={4,"book4"};   list_add_tail(&bk4.list,&MyBkList);      list_del(&bk3.list);      list_for_each_entry(pb, &MyBkList, list)    {        cout << pb->bkId << "  " << pb->bkName << endl;    }        cin.get();}

#include <string>/* * Architectures might want to move the poison pointer offset * into some well-recognized area such as 0xdead000000000000, * that is also not mappable by user-space exploits: */#ifdef CONFIG_ILLEGAL_POINTER_VALUE# define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)#else# define POISON_POINTER_DELTA 0#endif/* * These are non-NULL pointers that will result in page faults * under normal circumstances, used to verify that nobody uses * non-initialized list entries. */#define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)#define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)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;}/** 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;}/*** 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 *new1, struct list_head *head){    __list_add(new1, head->prev, head);}/*** 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 *new1, struct list_head *head){    __list_add(new1, head, head->next);}/*** 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)); })/*** list_for_each    -    iterate over a list* @pos:    the &struct list_head to use as a loop cursor.* @head:    the head for your list.*/#define list_for_each(pos, head) /for (pos = (head)->next; pos != (head); pos = pos->next)/*** list_entry - get the struct for this entry* @ptr:    the &struct list_head pointer.* @type:    the type of the struct this is embedded in.* @member:    the name of the list_struct within the struct.*/#define list_entry(ptr, type, member) /    container_of(ptr, type, member)/*** list_first_entry - get the first element from a list* @ptr:    the list head to take the element from.* @type:    the type of the struct this is embedded in.* @member:    the name of the list_struct within the struct.** Note, that list is expected to be not empty.*/#define list_first_entry(ptr, type, member) /    list_entry((ptr)->next, type, member)/*** list_next_entry - get the next element in list* @pos:    the type * to cursor* @member:    the name of the list_struct within the struct.*/#define list_next_entry(pos, member) /    list_entry((pos)->member.next, typeof(*(pos)), member)/*** list_for_each_entry    -    iterate over list of given type* @pos:    the type * to use as a loop cursor.* @head:    the head for your list.* @member:    the name of the list_struct within the struct.*/#define list_for_each_entry(pos, head, member)                /for (pos = list_first_entry(head, typeof(*pos), member);    /    &pos->member != (head);                    /    pos = list_next_entry(pos, member))/* * Delete a list entry by making the prev/next entries * point to each other. * * This is only for internal list manipulation where we know * the prev/next entries already! */static inline void __list_del(struct list_head * prev, struct list_head * next){    next->prev = prev;    prev->next = next;}/** * list_del - deletes entry from list. * @entry: the element to delete from the list. * Note: list_empty() on entry does not return true after this, the entry is * in an undefined state. */static inline void __list_del_entry(struct list_head *entry){    __list_del(entry->prev, entry->next);}static inline void list_del(struct list_head *entry){    __list_del(entry->prev, entry->next);    entry->next = (struct list_head *)LIST_POISON1;    //Linux kernel source does not have (struct list_head *)    entry->prev = (struct list_head *)LIST_POISON2;}#undef offsetof#ifdef __compiler_offsetof#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)#else#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)#endif

到這里已經簡單模擬實現了Linux內核鏈表最最基本的功能，還有其他功能，有興趣的直接上源代碼！