list_head用法经常在Linux的kernel里面经常看见,所以记录用法以来备忘
(1)list.h文件在include/linux/list.h
- #ifndef _LIST_H
- #define _LIST_H
- #define _INLINE_ static inline
- struct list_head {
- struct list_head *next, *prev;
- };
- #define LIST_HEAD_INIT(name) {&(name), &(name)}
- #define LIST_HEAD(name) \ //定义并初始化头结点head
- struct list_head name = LIST_HEAD_INIT(name)
- #define INIT_LIST_HEAD(ptr) do {\ //初始化头结点ptr,因此需要首先定义ptr
- (ptr)->next = (ptr); (ptr)->prev = (ptr); \
- } while (0)
- _INLINE_ void __list_add(struct list_head *add,
- struct list_head *prev,
- struct list_head *next)
- {
- next->prev = add;
- add->next = next;
- add->prev = prev;
- prev->next = add;
- }
- _INLINE_ void list_add(struct list_head *add, struct list_head *head)//每次添加节点到head之后,始终都是添加到头结点之后
- {
- __list_add(add, head, head->next);
- }
- _INLINE_ void list_add_tail(struct list_head *add, struct list_head *head)//每次添加节点都是头结点之前,由于是循环链表,就是说添加到链表尾部
- {
- __list_add(add, head->prev, head);
- }
- _INLINE_ void __list_del(struct list_head *prev, struct list_head *next)
- {
- next->prev = prev;
- prev->next = next;
- }
- _INLINE_ void list_del(struct list_head *entry)//删除节点
- {
- __list_del(entry->prev, entry->next);
- }
- _INLINE_ void list_del_init(struct list_head *entry)
- //删除节点,并初始化被删除的结点(也就是使被删除的结点的prev和next都指向自己)
- {
- __list_del(entry->prev, entry->next);
- INIT_LIST_HEAD(entry);
- }
- _INLINE_ int list_empty(struct list_head *head)//判断链表是否为空
- {
- return head->next == head;
- }
- _INLINE_ void list_splice(struct list_head *list, struct list_head *head)
- //通过两个链表的head,进行连接
- {
- struct list_head *first = list->next;
- if (first != list) {
- struct list_head *last = list->prev;
- struct list_head *at = head->next;
- first->prev = head;
- head->next = first;
- last->next = at;
- at->prev = last;
- }
- }
- #define list_entry(ptr, type, member) \
- ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
- #define list_for_each(pos, head) \
- //遍历链表,此时删除节点的操作可能会出错
- for (pos = (head)->next; pos != (head); pos = pos->next) //新代码中出现prefetch() 可以不考虑,用于预取以提高遍历速度
- #define list_for_each_safe(pos, pnext, head) \ //遍历链表,可以同时有删除节点的操作
- for (pos = (head)->next, pnext = pos->next; pos != (head); \
- pos = pnext, pnext = pos->next)
- #undef _INLINE_
- #endif
(2)写一个测试程序,利用各个函数实现功能
- #include<stdio.h>
- #include<stdlib.h>
- #include "list.h"
- struct int_node
- {
- int val;
- struct list_head list;
- };
- int main()
- {
- struct list_head head,*plist;
- struct int_node a,b,c;
-
- a.val = 1;
- b.val = 2;
- c.val = 3;
-
- INIT_LIST_HEAD(&head); //初始化链表头
- list_add_tail(&a.list,&head); //添加节点
- list_add_tail(&b.list,&head);
- list_add_tail(&c.list,&head);
- list_for_each(plist,&head)//遍历链表,打印结果
- {
- struct int_node *node = list_entry(plist,struct int_node,list);//然后取得数据项,因此一般来说和list_for_each配合使用
- printf("val = %d\n",node->val);
- }//print 1 2 3
- printf("*******************************************\n");
- list_del_init(&b.list); //删除节点b
- list_for_each(plist,&head) //重新遍历链表,打印结果
- {
- struct int_node *node = list_entry(plist,struct int_node,list);
- printf("val = %d\n",node->val);
- }//print 1 3
- printf("*******************************************\n");
- struct int_node d,e;
- struct list_head head1;
- d.val = 4;
- e.val = 5;
- INIT_LIST_HEAD(&head1); //重新建立链表,表头为head1
- list_add_tail(&d.list,&head1);
- list_add_tail(&e.list,&head1);
- list_splice(&head1,&head); //把两个链表进行连接
- list_for_each(plist,&head)
- {
- struct int_node *node = list_entry(plist,struct int_node,list);
- printf("val = %d\n",node->val);
- }//print 4 5 1 3
- printf("*******************************************\n");
- if(!list_empty(&head)) //判断链表是否为空
- {
- printf("the list is not empty!\n");
-
- }
- return 0;
- }
输出结果如下:
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
阅读(14000) | 评论(0) | 转发(0) |