你好,游客 登录 注册 搜索
背景:
阅读新闻

Linux内核链表的研究与应用

[日期:2013-01-17] 来源:CSDN  作者:tigerjb [字体: ]

六链表遍历
1.list_for_each(pos,head)
1>function:
实际上就是一个for循环,以顺时针方向遍历双向循环链表,由于是双向循环链表,所以循环终止条件是pos!=head.在遍历过程中,不能删除pos(必须保证pos->next有效),否则会造成SIGSEGV错误。

2>接口:
list_for_each(pos,head)
pos:pos是一个辅助指针(即链表类型),用于链表遍历
head:链表的头指针(即结构体中成员struct list_head)

3>list_for_each实现
#define list_for_each(pos,head)  \

              for(pos= (head->next);prefetch(pos->next),pos !=(head);  \

                      pos = pos->head)

Ø  pos是辅助指针,pos是从第一个结点开始的,并没有访问结点,直到pos到达结点指针head的时候结束

Ø  遍历是双循环链表的基本操作,head为头节点,遍历过程中首先从(head)->next开始,当pos==head时退出,故head节点并没有访问,这和链表的结构设计有关,通常头节点都不含有其它有效信息,因此可以把头节点作为双向链表遍历一遍的检测标志来使用。在list_for_each宏中读者可能发现一个比较陌生的面孔,我们在此就不将prefetch展开了讲解了,有兴趣的读者可以自己查看下它的实现,其功能是预取内存的内容,也就是程序告诉CPU哪些内容可能马上用到,CPU预先其取出内存操作数,然后将其送入高速缓存,用于优化,是的执行速度更快。

2.__list_for_each
1>function:
功能和list_for_each相同,即以顺时针方向遍历双向循环链表,只不过去掉了prefetch(pos->next)。在遍历过程中,不能删除pos(必须保证pos->next有效),否则会造成SIGSEGV错误。

2> __list_for_each(pos,head)
pos:pos是一个辅助指针(即链表类型),用于链表遍历
head:链表的头指针。

3>实现:
#define __list_for_each(pos,head)  \
  for (pos =(head)->next;pos!=(head);pos = pos->next)
区别:__list_for_each没有采用pretetch来进行预取。

3.list_for_each_prev
1>function:
逆向遍历链表。在遍历过程中,不能删除pos(必须保证pos->next有效),否则会造成SIGSEGV错误。

2>接口:
 list_for_each_prev(pos,head) 

3>实现
#define list_for_each_prev(pos,head)  \
    for(pos = (head)->prev;prefetch(pos->prev),pos !=(head);  \
            pos = pos->prev)
注:实现方法与list_for_each相同,不同的是用head的前趋结点进行遍历。实现链表的逆向遍历。

4.list_for_each_safe
1>function:
以顺时针方向遍历链表,与list_for_each不同的是使用list_head结构体变量n作为临时存储变量。主要用于链表删除时操作。

2>接口
list_for_each_safe(pos,n,head)
pos:pos是一个辅助指针(即链表类型),用于链表遍历
head:链表的头指针
n:临时指针用于占时存储pos的下一个指针

3>list_for_each_safe实现
#define  list_for_each_safe(pos,n,head)    \
    for (pos = (head)->next,n = pos->next; pos != (head);  \
                    pos = n, n = pos->next)
前面介绍了用于链表遍历的几个宏,它们都是通过移动pos指针来达到遍历的目的。但如果遍历的操作中包含删除pos指针所指向的节点,pos指针的移动就会被中断,因为list_del(pos)将把pos的next、prev置成LIST_POSITION2和LIST_POSITION1的特殊值。当然,调用者完全可以自己缓存next指针使遍历操作能够连贯起来,但为了编程的一致性,Linxu内核链表要求调用者另外提供一个与pos同类型的指针n,在for循环中暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。

5.list_for_each_prev_safe
1>function:
功能与list_for_each_prev相同,用于逆向遍历链表。不同的是使用list_head结构体变量n作为临时存储变量。主要用于链表删除时操作。

2>接口:
list_for_each_prev_safe(pos,n,head)
list_for_each_safe(pos,n,head)
 pos:pos是一个辅助指针(即链表类型struct list_head),用于链表遍历
 head:链表的头指针
 n:临时指针用于占时存储pos的下一个指针

3>list_for_each_prev_safe实现
#define  list_for_each_safe(pos,n,head)    \
    for (pos = (head)->prev,n = pos->prev;  \
            prefecth(pos->prev),pos!=(head);    \
            pos = n, n = pos->prev)

linux
相关资讯       Linux内核链表  内核链表  Linux链表 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款