4)遍历
遍历是链表最经常的操作之一,为了方便核心应用遍历链表,Linux链表将遍历操作抽象成几个宏。
在介绍遍历宏之前,我们先看看如何从链表中访问到我们真正需要的数据项:
a)由链表结点到数据项变量
由上面的分析可知,内核链表中仅保存了数据项结构中list_head成员变量的地址,那么我们如何通过这个list_head成员访问到作为它的所有者的节点数据呢?在list.h文件中有一个list_entry(ptr,type,member)宏,其中ptr是指向该数据中list_head成员的指针,也就是存储在链表中的地址值,type是数据项的类型,member则是数据项类型定义中list_head成员的变量名。
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
该宏的作用是通过ptr指针获得类型为type的属主结点的地址,从而访问type结构的数据成员。该宏最终调用container_of(ptr,type,member)宏来实现,相比之下container_of(ptr,type,member)就比较复杂一点了。
//from include/linux/kernel.h
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
//from include/linux/stddef.h
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
size_t最终定义为unsigned int(i386)。
这里使用的是一个利用编译器技术的小技巧,即先求得结构成员在与结构中的偏移量,然后根据成员变量的地址反过来得出属主结构变量的地址。
第一:const typeof( ((type *)0)->member ) *__mptr = (ptr);
首先将0转化成type类型的指针变量(这个指针变量的地址为0×0),然后再引用member成员(对应就是((type *)0)->member ))。
注意这里的typeof(x)(住:typeof()是gcc的扩展,和sizeof()类似),是返回x的数据类型,那么 typeof( ((type *)0)->member )其实就是返回member成员的数据类型。那么这条语句整体就是将__mptr强制转换成member成员的数据类型,再将ptr的赋给它。
第二:在offsetof()中,这个member成员的地址实际上就是type数据结构中member成员相对于结构变量的偏移量。
((TYPE *)0)->MEMBER)这个其实就是提取type类型中的member成员,那么&((TYPE *)0)->MEMBER)得到member成员的地址,再强制转换成size_t类型(unsigned int)。但是这个地址很特别,因为TYPE类型是从0×0开始定义的,那么我们现在得到的这个地址就是member成员在TYPE数据类型中的偏移量
(type *)( (char *)__mptr - offsetof(type,member) );
结果就是属主结点的起始地址。
不过这里要注意__mptr被强制转换成了(char *),为何要这么做?因为如果member是非char型的变量,比如为int型,并且假设返回值为offset,那么这样直接减去偏移量,实际上__mptr会减去sizeof(int)*offset!这一点和指针加一减一的原理相同
b)遍历宏
上面分析清楚了,链表的遍历就很简单了
#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
它实际上是一个for循环,利用传入的pos作为循环变量,从表头head开始,逐项向后(next方向)移动pos,直至又回到head(prefetch()可以不考虑,用于预取以提高遍历速度)
大多数情况下,遍历链表的时候都需要获得链表节点数据项,也就是说list_for_each()和list_entry()总是同时使用。对此Linux给出了一个list_for_each_entry()宏:
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
与list_for_each()不同,这里的pos是数据项结构指针类型,而不是(struct list_head *)。利用这个宏可以使链表的遍历更简单。
某些应用需要反向遍历链表,Linux提供了list_for_each_prev()和list_for_each_entry_reverse()来完成这一操作,使用方法和上面介绍的list_for_each()、list_for_each_entry()完全相同。
如果遍历不是从链表头开始,而是从已知的某个节点pos开始,则可以使用list_for_each_entry_continue(pos,head,member)。有时还会出现这种需求,即经过一系列计算后,如果pos有值,则从pos开始遍历,如果没有,则从链表头开始,为此,Linux专门提供了一个list_prepare_entry(pos,head,member)宏,将它的返回值作为list_for_each_entry_continue()的pos参数,就可以满足这一要求。
诸如此类的宏很多,具体可以查看list.h文件
c)安全性考虑
前面介绍了用于链表遍历的几个宏,它们都是通过移动pos指针来达到遍历的目的。但如果遍历的操作中包含删除pos指针所指向的节点,pos指针的移动就会被中断,因为list_del(pos)将把pos的next、prev置成LIST_POSITION2和LIST_POSITION1的特殊值。
当然,调用者完全可以自己缓存next指针使遍历操作能够连贯起来,但为了编程的一致性,Linux链表仍然提供了两个对应于基本遍历操作的"_safe"接口:list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member),它们要求调用者另外提供一个与pos同类型的指针n,在for循环中暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
基本上list.h文件大部分内容就是这些,其他的关于hlist等内容暂不分析。
当然内核链表并不仅限于在内核使用,可以通过改写list.h文件使之可以应用在普通用户程序中。
参考资料:
IBM developerWorks:http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/index.html 深入分析linux内核链表
分享到:
相关推荐
linux内核链表源代码,是list.h是链表的实现,有兴趣的朋友可以下载分析。
将linux内核源码中list.h拿出来, 增删与遍历部分写了详细注释, 关于链表合并, 没用过所以没写. 源码版本是2.6.32, 不过链表的源码改动应该不是很大. 我的邮箱2253238252@qq.com, 代码有什么不对的欢迎发邮件给我
linux内核链表的实现,包括内核链表的定义,以及内核链表相关的操作
对linux内核的链表结构和对内核链表的操作进行超详细讲解
Linux内核链表移植和测试代码
一、linux内核链表 1、普通链表的数据区域的局限性 之前定义数据区域时直接int data,我们认为我们的链表中需要存储的是一个int类型的数。但是实际上现实编程中链接中的节点不可能这么简单,而是多种多样的。 一般...
剖析linux 内核 linux内核链表
博客详细讲解Linux内核链表,教你看懂Linux内核链表与普通链表有什么不一样,并且有测试代码
详细的介绍了Linux内核中使用的最频繁的双向链表
linux内核中有关于list 、kfifo等数据结构的实现,从源码中抽取出list部分,可以在linux应用编程中使用。有详细的抽取过程原理,ubunt12.04上完成
链表是一种常用的组织有序数据的数据结构,它通过指针将一系列数据节点连接成一条数据链,是线性表的一种重要实现方式。相对于数组,链表具有更好的动态性,建立链表时无需预先知道数据总量,可以随机分配空间,可以...
linux2.4.18版本源码 内核链表 用户态移植 vc6.0下测试
吐血奉献,忍痛共享! 【最强悍的链表】Linux 内核链表源码
内核链表的构造与操作: 在Linux内核中使用了大量的链表结构来组织数据。这些链表大多数采用了include。/linux/list.h中实现的一套精彩的链表数据结构。 内核的链表具备双链表功能,实际上,通常它都的组织成双向...
linux内核链表插入,排序函数库,库里面包含了一些宏。可以进行链表的插入,,删减。与一般链表不同的是,可以连接不同类型的数据。
linux 内核链表在用户态的应用的实例,实现常见的链表的操作,
Linux内核链表及其在虚拟文件系统中的应用.pdf
博客详细讲解Linux内核链表,教你看懂Linux内核链表与普通链表有什么不一样
贪吃蛇小游戏,用c语言和Linux内核链表实现,图行显示基于curses库,游戏界面有时钟计时器和当前分数、上一次游戏分数、历史最高分数显示。
使用linux内核链表做的demo