在实际的工作中，我们可能会经常使用链表结构来存储数据，特别是嵌入式开发，经常会使用 linux 内核最经典的双向链表 list_head。

本篇文章详细介绍了 Linux 内核的通用链表是如何实现的，对于经常使用的函数都给出了详细的说明和测试用例，并且移植了 Linux 内核的链表结构，在任意平台都可以方便的调用内核已经写好的函数。建议收藏，以备不时之需！

1. 链表简介

链表是一种常用的组织有序数据的数据结构，它通过指针将一系列数据节点连接成一条数据链，是线性表的一种重要实现方式。

相对于数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。

通常链表数据结构至少应包含两个域：数据域和指针域，数据域用于存储数据，指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式，链表又可以分为单链表、双链表、循环链表等多种类型。

下面分别给出这几类常见链表类型的示意图：

1.1 单链表

单链表是最简单的一类链表，它的特点是仅有一个指针域指向后继节点（next）。因此，对单链表的遍历只能从头至尾（通常是 NULL 空指针）顺序进行。如何移植并使用Linux内核的通用链表（附完整代码实现） - 图1

1.2 双链表

通过设计前驱和后继两个指针域，双链表可以从两个方向遍历，这是它区别于单链表的地方。

如果打乱前驱、后继的依赖关系，就可以构成 “二叉树“；如果再让首节点的前驱指向链表尾节点、尾节点的后继指向首节点，就构成了循环链表；如果设计更多的指针域，就可以构成各种复杂的树状数据结构。

如何移植并使用Linux内核的通用链表（附完整代码实现） - 图2

双链表

1.3 循环链表

循环链表的特点是尾节点的后继指向首节点。前面已经给出了双链表的示意图，它的特点是从任意一个节点出发，沿两个方向的任何一个，都能找到链表中的任意一个数据。如果去掉前驱指针，就是单循环链表。

如何移植并使用Linux内核的通用链表（附完整代码实现） - 图3

循环链表

2. Linux 内核中的链表

上面介绍了普通链表的实现方式，可以看到数据域都是包裹在节点指针中的，通过节点指针访问下一组数据。

但是 Linux 内核的链表实现可以说比较特殊，只有前驱和后继指针，而没有数据域。链表的头文件是在 include/list.h（Linux2.6 内核）下。在实际工作中，也可以将内核中的链表拷贝出来供我们使用，就需不要造轮子了。

2.1 链表的定义

内核链表只有前驱和后继指针，并不包含数据域，这个链表具备通用性，使用非常方便。因此可以很容易的将内核链表结构体包含在任意数据的结构体中，非常容易扩展。我们只需要将链表结构体包括在数据结构体中就可以。下面看具体的代码。

如何移植并使用Linux内核的通用链表（附完整代码实现） - 图4

内核中的链表

内核链表的结构

  1. `//链表结构  
  2. struct list_head  
  3. {  
  4.     struct list_head *prev;  
  5.     struct list_head *next;  
  6. };  
  7. `

当需要用内核的链表结构时，只需要在数据结构体中定义一个struct list_head{}类型的结构体成员对象就可以。这样，我们就可以很方便地使用内核提供给我们的一组标准接口来对链表进行各种操作。我们定义一个学生结构体，里面包含学号和数学成绩。结构体如下：

  1. ` struct student  
  2. {  
  3.     struct list_head list;//暂且将链表放在结构体的第一位  
  4.     int ID;  
  5.     int math;     
  6. };  
  7. `

2.2 链表的初始化

2.2.1 内核实现

  1. `#define LIST_HEAD_INIT(name) { &(name), &(name) }
  3. #define LIST_HEAD(name) \  
  4.  struct list_head name = LIST_HEAD_INIT(name)
  6.     static inline void INIT_LIST_HEAD(struct list_head *list)  
  7. {  
  8.  list->next = list;  
  9.  list->prev = list;  
  10. }
  12. `

2.2.2 说明

INIT_LIST_HEAD 和LIST_HEAD都可以初始化链表，二者的区别如下：   LIST_HEAD（stu_list） 初始化链表时会顺便创建链表对象。

  1. `//LIST_HEAD（stu_list）展开如下  
  2. struct list_head stu_list= { &(stu_list), &(stu_list) };  
  3. `

INIT_LIST_HEAD(&stu1.stu_list) 初始化链表时需要我们已经有了一个链表对象stu1_list。

我们可以看到链表的初始化其实非常简单，就是让链表的前驱和后继都指向了自己。

2.2.3 举例

  1. `INIT_LIST_HEAD(&stu1.stu_list);  
  2. `

2.3 链表增加节点

2.3.1 内核实现

  1. `  
  2. /*  
  3.  * Insert a new entry between two known consecutive entries.  
  4.  *  
  5.  * This is only for internal list manipulation where we know  
  6.  * the prev/next entries already!  
  7.  */  
  8. #ifndef CONFIG_DEBUG_LIST  
  9. static inline void __list_add(struct list_head *new,  
  10.          struct list_head *prev,  
  11.          struct list_head *next)  
  12. {  
  13.  next->prev = new;  
  14.  new->next = next;  
  15.  new->prev = prev;  
  16.  prev->next = new;  
  17. }  
  18. #else  
  19. extern void __list_add(struct list_head *new,  
  20.          struct list_head *prev,  
  21.          struct list_head *next);  
  22. #endif
  24. /**  
  25.  * list_add - add a new entry  
  26.  * @new: new entry to be added  
  27.  * @head: list head to add it after  
  28.  *  
  29.  * Insert a new entry after the specified head.  
  30.  * This is good for implementing stacks.  
  31.  */  
  32. #ifndef CONFIG_DEBUG_LIST  
  33. static inline void list_add(struct list_head *new, struct list_head *head)  
  34. {  
  35.  __list_add(new, head, head->next);  
  36. }  
  37. #else  
  38. extern void list_add(struct list_head *new, struct list_head *head);  
  39. #endif
  41. /**  
  42.  * list_add_tail - add a new entry  
  43.  * @new: new entry to be added  
  44.  * @head: list head to add it before  
  45.  *  
  46.  * Insert a new entry before the specified head.  
  47.  * This is useful for implementing queues.  
  48.  */  
  49. static inline void list_add_tail(struct list_head *new, struct list_head *head)  
  50. {  
  51.  __list_add(new, head->prev, head);  
  52. }
  54. `

2.3.2 说明

list_add为头插法，即在链表头部（head 节点）前插入节点。最后打印的时候，先插入的先打印，后插入的后打印。

例如原链表为 1->2->3, 使用list_add插入 4 后变为，4->1->2->3。因为链表时循环的，而且通常没有首尾节点的概念，所以可以把任何一个节点当成 head。

同理，list_add_tail为尾插法，即在链表尾部（head 节点）插入节点。最后打印的时候，先插入的后打印，后插入的先打印。

例如原链表为 1->2->3, 使用list_add_tail插入 4 后变为，1->2->3->4。

2.3.3 举例

  1. `#include "mylist.h"  
  2. #include <stdio.h>  
  3. #include <stdlib.h>  
  4. struct student  
  5. {  
  6.     struct list_head stu_list;  
  7.     int ID;  
  8.     int math;     
  9. };
  11. int main()  
  12. {  
  13.     struct student *p;  
  14.     struct student *q;  
  15.     struct student stu1;  
  16.     struct student stu2;    
  17.     struct list_head *pos;  
  18.     //链表的初始化  
  19.     INIT_LIST_HEAD(&stu1.stu_list);  
  20.     INIT_LIST_HEAD(&stu2.stu_list);  
  21.     //头插法创建stu stu1链表  
  22.      for (int i = 0;i < 6;i++) {  
  23.          p = (struct student *)malloc(sizeof(struct student));  
  24.          p->ID=i;  
  25.          p->math = i+80;  
  26.          //头插法  
  27.          list_add(&p->stu_list,&stu1.stu_list);  
  28.          //尾插法  
  29.          //list_add_tail(&p->list,&stu.list);  
  30.      }
  32.          printf("list_add: \r\n");  
  33.     list_for_each(pos, &stu1.stu_list) {  
  34.         printf("ID = %d,math = %d\n",((struct student*)pos)->ID,((struct student*)pos)->math);  
  35.     }
  37.         //尾插法创建stu stu1链表  
  38.      for (int i = 0;i < 6;i++) {  
  39.          p = (struct student *)malloc(sizeof(struct student));  
  40.          p->ID=i;  
  41.          p->math = i+80;  
  42.          //头插法  
  43.          //list_add(&p->stu_list,&stu1.stu_list);  
  44.          //尾插法  
  45.          list_add_tail(&p->stu_list,&stu2.stu_list);  
  46.      }
  48.          printf("list_add_tail: \r\n");  
  49.     list_for_each(pos, &stu2.stu_list) {  
  50.         printf("ID = %d,math = %d\n",((struct student*)pos)->ID,((struct student*)pos)->math);  
  51.     }  
  52.     return 0;   
  53. }
  55. `

如何移植并使用Linux内核的通用链表（附完整代码实现） - 图5

测试结果

2.4 链表删除节点

2.4.1 内核实现

  1. `//原来内核设置的删除链表后的指向位置  
  2. // # define POISON_POINTER_DELTA 0  
  3. // #define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)  
  4. // #define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)
  6. //这里我们设置为NULL 内核中定义NULL 为0  
  7. #define NULL ((void *)0)  
  8. #define LIST_POISON1  NULL  
  9. #define LIST_POISON2  NULL  
  10. /*  
  11.  * Delete a list entry by making the prev/next entries  
  12.  * point to each other.  
  13.  *  
  14.  * This is only for internal list manipulation where we know  
  15.  * the prev/next entries already!  
  16.  */  
  17. static inline void __list_del(struct list_head * prev, struct list_head * next)  
  18. {  
  19.  next->prev = prev;  
  20.  prev->next = next;  
  21. }
  23. /**  
  24.  * list_del - deletes entry from list.  
  25.  * @entry: the element to delete from the list.  
  26.  * Note: list_empty() on entry does not return true after this, the entry is  
  27.  * in an undefined state.  
  28.  */  
  29. #ifndef CONFIG_DEBUG_LIST  
  30. static inline void list_del(struct list_head *entry)  
  31. {  
  32.  __list_del(entry->prev, entry->next);  
  33.  entry->next = LIST_POISON1;  
  34.  entry->prev = LIST_POISON2;  
  35. }  
  36. #else  
  37. extern void list_del(struct list_head *entry);  
  38. #endif
  40. `

2.4.2 说明

链表删除之后，entry 的前驱和后继会分别指向LIST_POISON1和LIST_POISON2，这个是内核设置的一个区域，但是在本例中将其置为了NULL。

2.4.3 举例

  1. `#include "mylist.h"  
  2. #include <stdio.h>  
  3. #include <stdlib.h>  
  4. struct student  
  5. {  
  6.     struct list_head stu_list;  
  7.     int ID;  
  8.     int math;     
  9. };  
  10. int main()  
  11. {  
  12.     struct student *p;  
  13.     struct student *q;  
  14.     struct student stu1;  
  15.     struct student stu2;    
  16.     struct list_head *pos1;  
  17.     //注意这里的pos2，后面会解释为什么定义为  
  18.     struct student *pos2;  
  19.     //stu = (struct student*)malloc(sizeof(struct student));  
  20.     //链表的初始化  
  21.     INIT_LIST_HEAD(&stu1.stu_list);  
  22.     INIT_LIST_HEAD(&stu2.stu_list);  
  23.     LIST_HEAD(stu);  
  24.     //头插法创建stu stu1链表  
  25.      for (int i = 0;i < 6;i++) {  
  26.          p = (struct student *)malloc(sizeof(struct student));  
  27.          p->ID=i;  
  28.          p->math = i+80;  
  29.          //头插法  
  30.          list_add(&p->stu_list,&stu1.stu_list);  
  31.          //尾插法  
  32.          //list_add_tail(&p->list,&stu.list);  
  33.      }
  35.          printf("list_add: \r\n");  
  36.     list_for_each(pos1, &stu1.stu_list) {  
  37.         printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);  
  38.     }
  40.         //删除  
  41.     list_for_each_entry(pos2,&stu1.stu_list,stu_list) {  
  42.         if (pos2->ID == 4) {  
  43.             list_del(&pos2->stu_list);  
  44.             break;  
  45.         }  
  46.     }
  48.         printf("list_del\r\n");  
  49.     list_for_each_entry(pos2,&stu1.stu_list,stu_list) {  
  50.         printf("ID = %d,math = %d\n",pos2->ID,pos2->math);  
  51.     }  
  52.     return 0; 
  54. }
  56. `

如何移植并使用Linux内核的通用链表（附完整代码实现） - 图6

测试结果

2.5 链表替换节点

2.5.1 内核实现

  1. `/**  
  2.  * list_replace - replace old entry by new one  
  3.  * @old : the element to be replaced  
  4.  * @new : the new element to insert  
  5.  *  
  6.  * If @old was empty, it will be overwritten.  
  7.  */  
  8. static inline void list_replace(struct list_head *old,  
  9.     struct list_head *new)  
  10. {  
  11.  new->next = old->next;  
  12.  new->next->prev = new;  
  13.  new->prev = old->prev;  
  14.  new->prev->next = new;  
  15. }
  17. static inline void list_replace_init(struct list_head *old,  
  18.      struct list_head *new)  
  19. {  
  20.  list_replace(old, new);  
  21.  INIT_LIST_HEAD(old);//重新初始化  
  22. }
  24. `

2.5.2 说明

list_replace使用新的节点替换旧的节点。

list_replace_init与list_replace不同之处在于，list_replace_init会将旧的节点重新初始化，让前驱和后继指向自己。

2.5.3 举例

  1. `#include "mylist.h"  
  2. #include <stdio.h>  
  3. #include <stdlib.h>  
  4. struct student  
  5. {  
  6.     struct list_head stu_list;  
  7.     int ID;  
  8.     int math;     
  9. };  
  10. int main()  
  11. {  
  12.     struct student *p;  
  13.     struct student *q;  
  14.     struct student stu1;  
  15.     struct student stu2;    
  16.     struct list_head *pos1;  
  17.     struct student *pos2;  
  18.     struct student new_obj={.ID=100,.math=100};   
  19.     //stu = (struct student*)malloc(sizeof(struct student));  
  20.     //链表的初始化  
  21.     INIT_LIST_HEAD(&stu1.stu_list);  
  22.     INIT_LIST_HEAD(&stu2.stu_list);  
  23.     LIST_HEAD(stu);  
  24.     //头插法创建stu stu1链表  
  25.      for (int i = 0;i < 6;i++) {  
  26.          p = (struct student *)malloc(sizeof(struct student));  
  27.          p->ID=i;  
  28.          p->math = i+80;  
  29.          //头插法  
  30.          list_add(&p->stu_list,&stu1.stu_list);  
  31.          //尾插法  
  32.          //list_add_tail(&p->list,&stu.list);  
  33.      }  
  34.     printf("list_add: \r\n");  
  35.     list_for_each(pos1, &stu1.stu_list) {  
  36.         printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);  
  37.     }
  39.      //替换  
  40.     list_for_each_entry(pos2,&stu1.stu_list,stu_list) {  
  41.         if (pos2->ID == 4) {  
  42.             list_replace(&pos2->stu_list,&new_obj.stu_list);  
  43.             break;  
  44.         }  
  45.     }  
  46.     printf("list_replace\r\n");  
  47.     list_for_each_entry(pos2,&stu1.stu_list,stu_list) {  
  48.         printf("ID = %d,math = %d\n",pos2->ID,pos2->math);  
  49.     }  
  50.     return 0;   
  51. }
  53. `

如何移植并使用Linux内核的通用链表（附完整代码实现） - 图7

测试结果

2.6 链表删除并插入节点

2.6.1 内核实现

  1. `/**  
  2.  * list_move - delete from one list and add as another's head  
  3.  * @list: the entry to move  
  4.  * @head: the head that will precede our entry  
  5.  */  
  6. static inline void list_move(struct list_head *list, struct list_head *head)  
  7. {  
  8.  __list_del(list->prev, list->next);  
  9.  list_add(list, head);  
  10. }
  12. /**  
  13.  * list_move_tail - delete from one list and add as another's tail  
  14.  * @list: the entry to move  
  15.  * @head: the head that will follow our entry  
  16.  */  
  17. static inline void list_move_tail(struct list_head *list,  
  18.       struct list_head *head)  
  19. {  
  20.  __list_del(list->prev, list->next);  
  21.  list_add_tail(list, head);  
  22. }
  24. `

2.6.2 说明

list_move函数实现的功能是删除 list 指向的节点，同时将其以头插法插入到 head 中。list_move_tail和list_move功能类似，只不过是将 list 节点插入到了head 的尾部。

2.6.3 举例

  1. `#include "mylist.h"  
  2. #include <stdio.h>  
  3. #include <stdlib.h>  
  4. struct student  
  5. {  
  6.     struct list_head stu_list;  
  7.     int ID;  
  8.     int math;     
  9. };  
  10. int main()  
  11. {  
  12.     struct student *p;  
  13.     struct student *q;  
  14.     struct student stu1;  
  15.     struct student stu2;    
  16.     struct list_head *pos1;  
  17.     struct student *pos2;  
  18.     struct student new_obj={.ID=100,.math=100};   
  19.     //stu = (struct student*)malloc(sizeof(struct student));  
  20.     //链表的初始化  
  21.     INIT_LIST_HEAD(&stu1.stu_list);  
  22.     INIT_LIST_HEAD(&stu2.stu_list);  
  23.     LIST_HEAD(stu);  
  24.     //头插法创建stu stu1链表  
  25.      for (int i = 0;i < 6;i++) {  
  26.          p = (struct student *)malloc(sizeof(struct student));  
  27.          p->ID=i;  
  28.          p->math = i+80;  
  29.          //头插法  
  30.          list_add(&p->stu_list,&stu1.stu_list);  
  31.          //尾插法  
  32.          //list_add_tail(&p->list,&stu.list);  
  33.      }  
  34.     printf("list_add: \r\n");  
  35.     list_for_each(pos1, &stu1.stu_list) {  
  36.         printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);  
  37.     }
  39.      //移位替换  
  40.     list_for_each_entry(pos2,&stu1.stu_list,stu_list) {  
  41.         if (pos2->ID == 0) {  
  42.             list_move(&pos2->stu_list,&stu1.stu_list);  
  43.             break;  
  44.         }  
  45.     }  
  46.     printf("list_move\r\n");  
  47.     list_for_each_entry(pos2,&stu1.stu_list,stu_list) {  
  48.         printf("ID = %d,math = %d\n",pos2->ID,pos2->math);  
  49.     }  
  50.     return 0;   
  51. }
  53. `

如何移植并使用Linux内核的通用链表（附完整代码实现） - 图8

测试结果

2.7 链表的合并

2.7.1 内核实现

  1. `static inline void __list_splice(struct list_head *list,  
  2.      struct list_head *head)  
  3. {  
  4.  struct list_head *first = list->next;  
  5.  struct list_head *last = list->prev;  
  6.  struct list_head *at = head->next;
  8.  first->prev = head;  
  9.  head->next = first;
  11.  last->next = at;  
  12.  at->prev = last;  
  13. }
  15. /**  
  16.  * list_splice - join two lists  
  17.  * @list: the new list to add.  
  18.  * @head: the place to add it in the first list.  
  19.  */  
  20. static inline void list_splice(struct list_head *list, struct list_head *head)  
  21. {  
  22.  if (!list_empty(list))  
  23.   __list_splice(list, head);  
  24. }
  26. /**  
  27.  * list_splice_init - join two lists and reinitialise the emptied list.  
  28.  * @list: the new list to add.  
  29.  * @head: the place to add it in the first list.  
  30.  *  
  31.  * The list at @list is reinitialised  
  32.  */  
  33. static inline void list_splice_init(struct list_head *list,  
  34.         struct list_head *head)  
  35. {  
  36.  if (!list_empty(list)) {  
  37.   __list_splice(list, head);  
  38.   INIT_LIST_HEAD(list);//置空  
  39.  }  
  40. }
  42. `

2.7.2 说明

list_splice完成的功能是合并两个链表。

假设当前有两个链表，表头分别是stu_list1和stu_list2（都是struct list_head变量），当调用list_splice(&stu_list1,&stu_list2)时，只要stu_list1非空，stu_list1链表的内容将被挂接在stu_list2链表上，位于stu_list2和stu_list2.next（原stu_list2表的第一个节点）之间。新stu_list2链表将以原stu_list1表的第一个节点为首节点，而尾节点不变。

如何移植并使用Linux内核的通用链表（附完整代码实现） - 图9

合并两个链表

list_splice_init和list_splice类似，只不过在合并完之后，调用INIT_LIST_HEAD(list)将 list 设置为空链。

2.7.3 用例

  1. `#include "mylist.h"  
  2. #include <stdio.h>  
  3. #include <stdlib.h>  
  4. struct student  
  5. {  
  6.     struct list_head stu_list;  
  7.     int ID;  
  8.     int math;     
  9. };  
  10. int main()  
  11. {  
  12.     struct student *p;  
  13.     struct student *q;  
  14.     struct student stu1;  
  15.     struct student stu2;    
  16.     struct list_head *pos1;  
  17.     struct student *pos2;  
  18.     struct student new_obj={.ID=100,.math=100};   
  19.     //stu = (struct student*)malloc(sizeof(struct student));  
  20.     //链表的初始化  
  21.     INIT_LIST_HEAD(&stu1.stu_list);  
  22.     INIT_LIST_HEAD(&stu2.stu_list);  
  23.     LIST_HEAD(stu);  
  24.     //头插法创建stu1 list链表  
  25.      for (int i = 0;i < 6;i++) {  
  26.          p = (struct student *)malloc(sizeof(struct student));  
  27.          p->ID=i;  
  28.          p->math = i+80;  
  29.          //头插法  
  30.          list_add(&p->stu_list,&stu1.stu_list);  
  31.          //尾插法  
  32.          //list_add_tail(&p->list,&stu.list);  
  33.      }  
  34.     printf("stu1: \r\n");  
  35.     list_for_each(pos1, &stu1.stu_list) {  
  36.         printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);  
  37.     }  
  38.     //头插法创建stu2 list 链表  
  39.      for (int i = 0;i < 3;i++) {  
  40.          q = (struct student *)malloc(sizeof(struct student));  
  41.          q->ID=i;  
  42.          q->math = i+80;  
  43.          //头插法  
  44.          list_add(&q->stu_list,&stu2.stu_list);  
  45.          //尾插法  
  46.          //list_add_tail(&p->list,&stu.list);  
  47.      }  
  48.     printf("stu2: \r\n");  
  49.     list_for_each(pos1, &stu2.stu_list) {  
  50.         printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);  
  51.     }
  53.     //合并  
  54.     list_splice(&stu1.stu_list,&stu2.stu_list);  
  55.     printf("list_splice\r\n");  
  56.     list_for_each(pos1, &stu2.stu_list) {  
  57.         printf("stu2 ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);  
  58.     }
  60.         return 0;   
  61. }
  63. `

如何移植并使用Linux内核的通用链表（附完整代码实现） - 图10

测试结果

2.8 链表的遍历

2.8.1 内核实现

  1. `//计算member在type中的位置  
  2. #define offsetof(type, member)  (size_t)(&((type*)0)->member)  
  3. //根据member的地址获取type的起始地址
  5. #define container_of(ptr, type, member) ({          \  
  6.         const typeof(((type *)0)->member)*__mptr = (ptr);    \  
  7.     (type *)((char *)__mptr - offsetof(type, member)); })
  9.     /**  
  10.  * list_entry - get the struct for this entry  
  11.  * @ptr: the &struct list_head pointer.  
  12.  * @type: the type of the struct this is embedded in.  
  13.  * @member: the name of the list_struct within the struct.  
  14.  */  
  15. #define list_entry(ptr, type, member) \  
  16.  container_of(ptr, type, member)
  18. /**  
  19.  * list_first_entry - get the first element from a list  
  20.  * @ptr: the list head to take the element from.  
  21.  * @type: the type of the struct this is embedded in.  
  22.  * @member: the name of the list_struct within the struct.  
  23.  *  
  24.  * Note, that list is expected to be not empty.  
  25.  */  
  26. #define list_first_entry(ptr, type, member) \  
  27.  list_entry((ptr)->next, type, member)
  29. /**  
  30.  * list_for_each - iterate over a list  
  31.  * @pos: the &struct list_head to use as a loop cursor.  
  32.  * @head: the head for your list.  
  33.  */  
  34. #define list_for_each(pos, head) \  
  35.  for (pos = (head)->next; prefetch(pos->next), pos != (head); \  
  36.          pos = pos->next)
  38. /**  
  39.  * __list_for_each - iterate over a list  
  40.  * @pos: the &struct list_head to use as a loop cursor.  
  41.  * @head: the head for your list.  
  42.  *  
  43.  * This variant differs from list_for_each() in that it's the  
  44.  * simplest possible list iteration code, no prefetching is done.  
  45.  * Use this for code that knows the list to be very short (empty  
  46.  * or 1 entry) most of the time.  
  47.  */  
  48. #define __list_for_each(pos, head) \  
  49.  for (pos = (head)->next; pos != (head); pos = pos->next)
  51. /**  
  52.  * list_for_each_prev - iterate over a list backwards  
  53.  * @pos: the &struct list_head to use as a loop cursor.  
  54.  * @head: the head for your list.  
  55.  */  
  56. #define list_for_each_prev(pos, head) \  
  57.  for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \  
  58.          pos = pos->prev)
  60. /**  
  61.  * list_for_each_safe - iterate over a list safe against removal of list entry  
  62.  * @pos: the &struct list_head to use as a loop cursor.  
  63.  * @n:  another &struct list_head to use as temporary storage  
  64.  * @head: the head for your list.  
  65.  */  
  66. #define list_for_each_safe(pos, n, head) \  
  67.  for (pos = (head)->next, n = pos->next; pos != (head); \  
  68.   pos = n, n = pos->next)
  70. /**  
  71.  * list_for_each_entry - iterate over list of given type  
  72.  * @pos: the type * to use as a loop cursor.  
  73.  * @head: the head for your list.  
  74.  * @member: the name of the list_struct within the struct.  
  75.  */  
  76. #define list_for_each_entry(pos, head, member)    \  
  77.  for (pos = list_entry((head)->next, typeof(*pos), member); \  
  78.       prefetch(pos->member.next), &pos->member != (head);  \  
  79.       pos = list_entry(pos->member.next, typeof(*pos), member))
  81. /**  
  82.  * list_for_each_entry_reverse - iterate backwards over list of given type.  
  83.  * @pos: the type * to use as a loop cursor.  
  84.  * @head: the head for your list.  
  85.  * @member: the name of the list_struct within the struct.  
  86.  */  
  87. #define list_for_each_entry_reverse(pos, head, member)   \  
  88.  for (pos = list_entry((head)->prev, typeof(*pos), member); \  
  89.       prefetch(pos->member.prev), &pos->member != (head);  \  
  90.       pos = list_entry(pos->member.prev, typeof(*pos), member))
  92. /**  
  93.  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()  
  94.  * @pos: the type * to use as a start point  
  95.  * @head: the head of the list  
  96.  * @member: the name of the list_struct within the struct.  
  97.  *  
  98.  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().  
  99.  */  
  100. #define list_prepare_entry(pos, head, member) \  
  101.  ((pos) ? : list_entry(head, typeof(*pos), member))
  103. /**  
  104.  * list_for_each_entry_continue - continue iteration over list of given type  
  105.  * @pos: the type * to use as a loop cursor.  
  106.  * @head: the head for your list.  
  107.  * @member: the name of the list_struct within the struct.  
  108.  *  
  109.  * Continue to iterate over list of given type, continuing after  
  110.  * the current position.  
  111.  */  
  112. #define list_for_each_entry_continue(pos, head, member)   \  
  113.  for (pos = list_entry(pos->member.next, typeof(*pos), member); \  
  114.       prefetch(pos->member.next), &pos->member != (head); \  
  115.       pos = list_entry(pos->member.next, typeof(*pos), member))
  117. /**  
  118.  * list_for_each_entry_from - iterate over list of given type from the current point  
  119.  * @pos: the type * to use as a loop cursor.  
  120.  * @head: the head for your list.  
  121.  * @member: the name of the list_struct within the struct.  
  122.  *  
  123.  * Iterate over list of given type, continuing from current position.  
  124.  */  
  125. #define list_for_each_entry_from(pos, head, member)    \  
  126.  for (; prefetch(pos->member.next), &pos->member != (head); \  
  127.       pos = list_entry(pos->member.next, typeof(*pos), member))
  129. /**  
  130.  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry  
  131.  * @pos: the type * to use as a loop cursor.  
  132.  * @n:  another type * to use as temporary storage  
  133.  * @head: the head for your list.  
  134.  * @member: the name of the list_struct within the struct.  
  135.  */  
  136. #define list_for_each_entry_safe(pos, n, head, member)   \  
  137.  for (pos = list_entry((head)->next, typeof(*pos), member), \  
  138.   n = list_entry(pos->member.next, typeof(*pos), member); \  
  139.       &pos->member != (head);      \  
  140.       pos = n, n = list_entry(n->member.next, typeof(*n), member))
  142. /**  
  143.  * list_for_each_entry_safe_continue  
  144.  * @pos: the type * to use as a loop cursor.  
  145.  * @n:  another type * to use as temporary storage  
  146.  * @head: the head for your list.  
  147.  * @member: the name of the list_struct within the struct.  
  148.  *  
  149.  * Iterate over list of given type, continuing after current point,  
  150.  * safe against removal of list entry.  
  151.  */  
  152. #define list_for_each_entry_safe_continue(pos, n, head, member)   \  
  153.  for (pos = list_entry(pos->member.next, typeof(*pos), member),   \  
  154.   n = list_entry(pos->member.next, typeof(*pos), member);  \  
  155.       &pos->member != (head);      \  
  156.       pos = n, n = list_entry(n->member.next, typeof(*n), member))
  158. /**  
  159.  * list_for_each_entry_safe_from  
  160.  * @pos: the type * to use as a loop cursor.  
  161.  * @n:  another type * to use as temporary storage  
  162.  * @head: the head for your list.  
  163.  * @member: the name of the list_struct within the struct.  
  164.  *  
  165.  * Iterate over list of given type from current point, safe against  
  166.  * removal of list entry.  
  167.  */  
  168. #define list_for_each_entry_safe_from(pos, n, head, member)    \  
  169.  for (n = list_entry(pos->member.next, typeof(*pos), member);  \  
  170.       &pos->member != (head);      \  
  171.       pos = n, n = list_entry(n->member.next, typeof(*n), member))
  173. /**  
  174.  * list_for_each_entry_safe_reverse  
  175.  * @pos: the type * to use as a loop cursor.  
  176.  * @n:  another type * to use as temporary storage  
  177.  * @head: the head for your list.  
  178.  * @member: the name of the list_struct within the struct.  
  179.  *  
  180.  * Iterate backwards over list of given type, safe against removal  
  181.  * of list entry.  
  182.  */  
  183. #define list_for_each_entry_safe_reverse(pos, n, head, member)  \  
  184.  for (pos = list_entry((head)->prev, typeof(*pos), member), \  
  185.   n = list_entry(pos->member.prev, typeof(*pos), member); \  
  186.       &pos->member != (head);      \  
  187.       pos = n, n = list_entry(n->member.prev, typeof(*n), member))
  189. `

2.8.2 说明

list_entry(ptr, type, member)可以得到节点结构体的地址，得到地址后就可以对结构体中的元素进行操作了。依靠list_entry(ptr, type, member)函数，内核链表的增删查改都不需要知道list_head结构体所嵌入式的对象，就可以完成各种操作。

为什么这里使用container_of来定义list_entry(ptr, type, member)结构体呢，下面会详细解释。

list_first_entry(ptr, type, member)得到的是结构体中第一个元素的地址。

list_for_each(pos, head)是用来正向遍历链表的，pos 相当于一个临时的节点，用来不断指向下一个节点。

list_for_each_prev(pos, head)和list_for_each_entry_reverse(pos, head, member)是用来倒着遍历链表的。

list_for_each_safe(pos, n, head)和list_for_each_entry_safe(pos, n, head, member)，这两个函数是为了避免在遍历链表的过程中因 pos 节点被释放而造成的断链。这个时候就要求我们另外提供一个与 pos 同类型的指针 n，在 for 循环中暂存 pos 下一个节点的地址。（内核的设计者考虑的真是全面！）

list_prepare_entry(pos, head, member)用于准备一个结构体的首地址，用在list_for_each_entry_contine()中。

list_for_each_entry_continue(pos, head, member)从当前 pos 的下一个节点开始继续遍历剩余的链表，不包括 pos. 如果我们将 pos、head、member 传入list_for_each_entry，此宏将会从链表的头节点开始遍历。

list_for_each_entry_continue_reverse(pos, head, member)从当前的 pos 的前一个节点开始继续反向遍历剩余的链表，不包括 pos。

list_for_each_entry_from(pos, head, member)从 pos 开始遍历剩余的链表。

list_for_each_entry_safe_continue(pos, n, head, member)从 pos 节点的下一个节点开始遍历剩余的链表，并防止因删除链表节点而导致的遍历出错。

list_for_each_entry_safe_from(pos, n, head, member)从 pos 节点开始继续遍历剩余的链表，并防止因删除链表节点而导致的遍历出错。其与list_for_each_entry_safe_continue(pos, n, head, member)的不同在于在第一次遍历时，pos 没有指向它的下一个节点，而是从 pos 开始遍历。

list_for_each_entry_safe_reverse(pos, n, head, member)从 pos 的前一个节点开始反向遍历一个链表，并防止因删除链表节点而导致的遍历出错。

list_safe_reset_next(pos, n, member)返回当前 pos 节点的下一个节点的 type 结构体首地址。

2.8.3 举例

  1. `#include "mylist.h"  
  2. #include <stdio.h>  
  3. #include <stdlib.h>  
  4. struct student  
  5. {  
  6.     struct list_head stu_list;  
  7.     int ID;  
  8.     int math;     
  9. };  
  10. int main()  
  11. {  
  12.     struct student *p;  
  13.     struct student *q;  
  14.     struct student stu1;  
  15.     struct student stu2;    
  16.     struct list_head *pos1;  
  17.     struct student *pos2;  
  18.     struct student new_obj={.ID=100,.math=100};   
  19.     //stu = (struct student*)malloc(sizeof(struct student));  
  20.     //链表的初始化  
  21.     INIT_LIST_HEAD(&stu1.stu_list);  
  22.     INIT_LIST_HEAD(&stu2.stu_list);  
  23.     LIST_HEAD(stu);  
  24.     //头插法创建stu stu1链表  
  25.      for (int i = 0;i < 6;i++) {  
  26.          p = (struct student *)malloc(sizeof(struct student));  
  27.          p->ID=i;  
  28.          p->math = i+80;  
  29.          //头插法  
  30.          list_add(&p->stu_list,&stu1.stu_list);  
  31.          //尾插法  
  32.          //list_add_tail(&p->list,&stu.list);  
  33.      }  
  34.     printf("stu1: \r\n");  
  35.     list_for_each(pos1, &stu1.stu_list) {  
  36.         printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);  
  37.     }
  39.     printf("list_for_each_prev\r\n");  
  40.     list_for_each_prev(pos1, &stu1.stu_list){  
  41.         printf("stu2 ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);  
  42.     }
  44.     return 0;   
  45. }
  47. `

如何移植并使用Linux内核的通用链表（附完整代码实现） - 图11

测试结果

例子就不都写出来了，感兴趣的可以自己试试。

3. 疑惑解答

之前我们定义结构体的时候是把 struct list_head放在首位的，当使用list_for_each遍历的时候，pos 获取的位置就是结构体的位置，也就是链表的位置。如下所示。

  1. ` struct student  
  2. {  
  3.     struct list_head list;//暂且将链表放在结构体的第一位  
  4.     int ID;  
  5.     int math;     
  6. };  
  7. `
  1. `    list_for_each(pos, &stu1.stu_list) {  
  2.         printf("ID = %d,math = %d\n",((struct student*)pos)->ID,((struct student*)pos)->math);  
  3.     }  
  4. `

但是当我们把struct list_head list;放在最后时，pos 获取的显然就已经不是链表的位置了，那么当我们再次调用list_for_each时就会出错。

  1. struct student  
  2. {    
  3.     int ID;  
  4.     int math;     
  5.     struct list_head list;//暂且将链表放在结构体的第一位  
  6. };

list_for_each_entry这个函数表示在遍历的时候获取 entry，该宏中的 pos 类型为容器结构类型的指针，这与前面list_for_each中的使用的类型不再相同（这也就是为什么我们上面会分别定义 pos1 和 pos2 的原因了）。

不过这也是情理之中的事，毕竟现在的 pos，我要使用该指针去访问数据域的成员 age 了；head 是你使用INIT_LIST_HEAD初始化的那个对象，即头指针，注意，不是头结点；member 就是容器结构中的链表元素对象。使用该宏替代前面的方法。这个时候就要用到container_of这个宏了。（再一次感叹内核设计者的伟大）。

关于container_of宏将在下一篇文章详细介绍，这里先知道如何使用就可以。

4. list.h 移植源码

这里需要注意一点，如果是在 GNU 中使用 GCC 进行程序开发，可以不做更改，直接使用上面的函数即可；但如果你想把其移植到 Windows 环境中进行使用，可以直接将 prefetch 语句删除即可，因为 prefetch 函数它通过对数据手工预取的方法，减少了读取延迟，从而提高了性能，也就是prefetch 是 GCC 用来提高效率的函数，如果要移植到非 GNU 环境，可以换成相应环境的预取函数或者直接删除也可，它并不影响链表的功能。

  1. #ifndef _MYLIST_H  
  2. #define _MYLIST_H  
  3.  //原来链表删除后指向的位置，这里我们修改成 0  
  4. // # define POISON_POINTER_DELTA 0  
  5. // #define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)  
  6. // #define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)  
  7. #define NULL ((void *)0)  
  8. #define LIST_POISON1  NULL  
  9. #define LIST_POISON2  NULL
  11. //计算member在type中的位置  
  12. #define offsetof(type, member)  (size_t)(&((type*)0)->member)  
  13. //根据member的地址获取type的起始地址  
  14. #define container_of(ptr, type, member) ({          \  
  15.         const typeof(((type *)0)->member)*__mptr = (ptr);    \  
  16.     (type *)((char *)__mptr - offsetof(type, member)); })
  18. //链表结构  
  19. struct list_head  
  20. {  
  21.     struct list_head *prev;  
  22.     struct list_head *next;  
  23. };  
  24. #define LIST_HEAD_INIT(name) { &(name), &(name) }
  26. #define LIST_HEAD(name) \  
  27.  struct list_head name = LIST_HEAD_INIT(name)
  29.     static inline void INIT_LIST_HEAD(struct list_head *list)  
  30. {  
  31.  list->next = list;  
  32.  list->prev = list;  
  33. }
  35. static inline void init_list_head(struct list_head *list)  
  36. {  
  37.     list->prev = list;  
  38.     list->next = list;  
  39. }
  41. #ifndef CONFIG_DEBUG_LIST  
  42. static inline void __list_add(struct list_head *new,  
  43.          struct list_head *prev,  
  44.          struct list_head *next)  
  45. {  
  46.  next->prev = new;  
  47.  new->next = next;  
  48.  new->prev = prev;  
  49.  prev->next = new;  
  50. }  
  51. #else  
  52. extern void __list_add(struct list_head *new,  
  53.          struct list_head *prev,  
  54.          struct list_head *next);  
  55. #endif
  57. //从头部添加  
  58. /**  
  59.  * list_add - add a new entry  
  60.  * @new: new entry to be added  
  61.  * @head: list head to add it after  
  62.  *  
  63.  * Insert a new entry after the specified head.  
  64.  * This is good for implementing stacks.  
  65.  */  
  66. #ifndef CONFIG_DEBUG_LIST  
  67. static inline void list_add(struct list_head *new, struct list_head *head)  
  68. {  
  69.  __list_add(new, head, head->next);  
  70. }  
  71. #else  
  72. extern void list_add(struct list_head *new, struct list_head *head);  
  73. #endif  
  74. //从尾部添加  
  75. static inline void list_add_tail(struct list_head *new, struct list_head *head)  
  76. {  
  77.     __list_add(new, head->prev, head);  
  78. }
  80. static inline  void __list_del(struct list_head *prev, struct list_head *next)  
  81. {  
  82.     prev->next = next;  
  83.     next->prev = prev;  
  84. }
  86. static inline void list_del(struct list_head *entry)  
  87. {  
  88.     __list_del(entry->prev, entry->next);  
  89.     entry->next = LIST_POISON1;  
  90.     entry->prev = LIST_POISON2;  
  91. }
  93. static inline void __list_splice(struct list_head *list,  
  94.      struct list_head *head)  
  95. {  
  96.  struct list_head *first = list->next;  
  97.  struct list_head *last = list->prev;  
  98.  struct list_head *at = head->next;
  100.  first->prev = head;  
  101.  head->next = first;
  103.  last->next = at;  
  104.  at->prev = last;  
  105. }  
  106. /**  
  107.  * list_empty - tests whether a list is empty  
  108.  * @head: the list to test.  
  109.  */  
  110. static inline int list_empty(const struct list_head *head)  
  111. {  
  112.  return head->next == head;  
  113. }  
  114. /**  
  115.  * list_splice - join two lists  
  116.  * @list: the new list to add.  
  117.  * @head: the place to add it in the first list.  
  118.  */  
  119. static inline void list_splice(struct list_head *list, struct list_head *head)  
  120. {  
  121.  if (!list_empty(list))  
  122.   __list_splice(list, head);  
  123. }  
  124. /**  
  125.  * list_replace - replace old entry by new one  
  126.  * @old : the element to be replaced  
  127.  * @new : the new element to insert  
  128.  *  
  129.  * If @old was empty, it will be overwritten.  
  130.  */  
  131. static inline void list_replace(struct list_head *old,  
  132.     struct list_head *new)  
  133. {  
  134.  new->next = old->next;  
  135.  new->next->prev = new;  
  136.  new->prev = old->prev;  
  137.  new->prev->next = new;  
  138. }
  140. static inline void list_replace_init(struct list_head *old,  
  141.      struct list_head *new)  
  142. {  
  143.  list_replace(old, new);  
  144.  INIT_LIST_HEAD(old);  
  145. }  
  146. /**  
  147.  * list_move - delete from one list and add as another's head  
  148.  * @list: the entry to move  
  149.  * @head: the head that will precede our entry  
  150.  */  
  151. static inline void list_move(struct list_head *list, struct list_head *head)  
  152. {  
  153.  __list_del(list->prev, list->next);  
  154.  list_add(list, head);  
  155. }
  157. /**  
  158.  * list_move_tail - delete from one list and add as another's tail  
  159.  * @list: the entry to move  
  160.  * @head: the head that will follow our entry  
  161.  */  
  162. static inline void list_move_tail(struct list_head *list,  
  163.       struct list_head *head)  
  164. {  
  165.  __list_del(list->prev, list->next);  
  166.  list_add_tail(list, head);  
  167. }  
  168. #define list_entry(ptr, type, member) \  
  169.     container_of(ptr, type, member)
  171. #define list_first_entry(ptr, type, member) \  
  172.     list_entry((ptr)->next, type, member)
  174. #define list_for_each(pos, head) \  
  175.     for (pos = (head)->next; pos != (head); pos = pos->next)  
  176. /**  
  177.  * list_for_each_entry - iterate over list of given type  
  178.  * @pos: the type * to use as a loop cursor.  
  179.  * @head: the head for your list.  
  180.  * @member: the name of the list_struct within the struct.  
  181.  */  
  182. #define list_for_each_entry(pos, head, member)      \  
  183.  for (pos = list_entry((head)->next, typeof(*pos), member); \  
  184.       &pos->member != (head);  \  
  185.       pos = list_entry(pos->member.next, typeof(*pos), member))  
  186. /**  
  187.  * list_for_each_prev - iterate over a list backwards  
  188.  * @pos: the &struct list_head to use as a loop cursor.  
  189.  * @head: the head for your list.  
  190.  */  
  191. #define list_for_each_prev(pos, head) \  
  192.  for (pos = (head)->prev;  pos != (head); \  
  193.          pos = pos->prev)