list_head用法(一)

13970阅读　0评论2012-11-21　xiaoqiang_linux
分类：

list_head用法经常在Linux的kernel里面经常看见，所以记录用法以来备忘
(1)list.h文件在include/linux/list.h

点击(此处)折叠或打开

  1. #ifndef _LIST_H
  2. #define _LIST_H

  4. #define _INLINE_ static inline

  6. struct list_head {
  7.     struct list_head *next, *prev;
  8. };

  10. #define LIST_HEAD_INIT(name) {&(name), &(name)}

  12. #define LIST_HEAD(name) \ //定义并初始化头结点head
  13.     struct list_head name = LIST_HEAD_INIT(name)

  15. #define INIT_LIST_HEAD(ptr) do {\             //初始化头结点ptr,因此需要首先定义ptr
  16.     (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  17. } while (0)

  19. _INLINE_ void __list_add(struct list_head *add,
  20.         struct list_head *prev,
  21.         struct list_head *next)
  22. {
  23.     next->prev = add;
  24.     add->next = next;
  25.     add->prev = prev;
  26.     prev->next = add;
  27. }

  29. _INLINE_ void list_add(struct list_head *add, struct list_head *head)//每次添加节点到head之后，始终都是添加到头结点之后
  30. {
  31.     __list_add(add, head, head->next);
  32. }

  34. _INLINE_ void list_add_tail(struct list_head *add, struct list_head *head)//每次添加节点都是头结点之前，由于是循环链表，就是说添加到链表尾部
  35. {
  36.     __list_add(add, head->prev, head);
  37. }

  39. _INLINE_ void __list_del(struct list_head *prev, struct list_head *next)
  40. {
  41.     next->prev = prev;
  42.     prev->next = next;
  43. }

  45. _INLINE_ void list_del(struct list_head *entry)//删除节点
  46. {
  47.     __list_del(entry->prev, entry->next);
  48. }

  50. _INLINE_ void list_del_init(struct list_head *entry)
  51. //删除节点，并初始化被删除的结点（也就是使被删除的结点的prev和next都指向自己）
  52. {
  53.     __list_del(entry->prev, entry->next);
  54.     INIT_LIST_HEAD(entry);
  55. }

  57. _INLINE_ int list_empty(struct list_head *head)//判断链表是否为空
  58. {
  59.     return head->next == head;
  60. }

  62. _INLINE_ void list_splice(struct list_head *list, struct list_head *head)
  63. //通过两个链表的head，进行连接
  64. {
  65.     struct list_head *first = list->next;

  67.     if (first != list) {
  68.         struct list_head *last = list->prev;
  69.         struct list_head *at = head->next;

  71.         first->prev = head;
  72.         head->next = first;

  74.         last->next = at;
  75.         at->prev = last;
  76.     }
  77. }

  79. #define list_entry(ptr, type, member) \
  80.     ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))

  82. #define list_for_each(pos, head) \                                        
  83. //遍历链表，此时删除节点的操作可能会出错
  84.     for (pos = (head)->next; pos != (head); pos = pos->next) //新代码中出现prefetch() 可以不考虑，用于预取以提高遍历速度

  86. #define list_for_each_safe(pos, pnext, head) \      //遍历链表，可以同时有删除节点的操作
  87.     for (pos = (head)->next, pnext = pos->next; pos != (head); \
  88.             pos = pnext, pnext = pos->next)

  90. #undef _INLINE_
  91. #endif
(2)写一个测试程序,利用各个函数实现功能

点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include "list.h"

  5. struct int_node
  6. {
  7.     int val;
  8.     struct list_head list;
  9. };

  11. int main()
  12. {
  13.     struct list_head head,*plist;
  14.     struct int_node a,b,c;
  15.     
  16.     a.val = 1;
  17.     b.val = 2;
  18.     c.val = 3;
  19.     
  20.     INIT_LIST_HEAD(&head);            //初始化链表头
  21.     list_add_tail(&a.list,&head);     //添加节点
  22.     list_add_tail(&b.list,&head);
  23.     list_add_tail(&c.list,&head);

  25.     list_for_each(plist,&head)//遍历链表，打印结果
  26.     {
  27.         struct int_node *node = list_entry(plist,struct int_node,list);//然后取得数据项，因此一般来说和list_for_each配合使用
  28.         printf("val = %d\n",node->val);
  29.     }//print 1 2 3

  31.     printf("*******************************************\n");
  32.     list_del_init(&b.list);            //删除节点b
  33.     list_for_each(plist,&head)         //重新遍历链表，打印结果
  34.     {
  35.         struct int_node *node = list_entry(plist,struct int_node,list);
  36.         printf("val = %d\n",node->val);
  37.     }//print 1 3

  39.     printf("*******************************************\n");
  40.     struct int_node d,e;
  41.     struct list_head head1;
  42.     d.val = 4;
  43.     e.val = 5;
  44.     INIT_LIST_HEAD(&head1);            //重新建立链表，表头为head1
  45.     list_add_tail(&d.list,&head1);
  46.     list_add_tail(&e.list,&head1);

  48.     list_splice(&head1,&head);        //把两个链表进行连接
  49.     list_for_each(plist,&head)
  50.     {
  51.         struct int_node *node = list_entry(plist,struct int_node,list);
  52.         printf("val = %d\n",node->val);
  53.     }//print 4 5 1 3

  55.     printf("*******************************************\n");
  56.     if(!list_empty(&head))          //判断链表是否为空
  57.     {
  58.         printf("the list is not empty!\n");
  59.         
  60.     }

  62.     return 0;
  63. }

输出结果如下：
val = 1
val = 2
val = 3
*******************************************
val = 1
val = 3
*******************************************
val = 4
val = 5
val = 1
val = 3
*******************************************
the list is not empty!

(3)list_for_each()与list_for_each_safe()
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
由定义可知，list_del(pos)(将pos的前后指针指向undefined state)panic，list_del_init(pos)(将pos前后指针指向自身)导致死循环。

#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)

由定义可知，safe函数首先将pos的后指针缓存到n，处理一个流程后再赋回pos，避免了这种情况的发生。
因此只遍历链表不删除节点时可以使用前者，若有删除节点的操作，则要使用后者。

由safe的说明可知，是专门为删除节点时准备的：iterate over a list safe against removal of list entry。其他带safe的处理也基本源于这个原因。

参考资料：

http://blog.csdn.net/king_208/article/details/5524175
http://www.cnblogs.com/wwang/archive/2010/11/28/1889281.html




上一篇：list_head用法(一)
下一篇：list_head用法(二) 接口函数list_for_each_entry