Linux内核链表及其在虚拟文件系统中的应用
30
西 安 邮 电 学 院 学 报 2011年3月
例如,对于结点类型为structdlink1和structdlink2这两个不同结构体类型的链表,需要提供两个插入函数,接口形式如下:
intinsert1(structdlink1*head1,structdlink1*P1);intinsert2(structdlink2*head2,structdlink2*

P2);
{&name,&name}
#defineLIST_HEAD(name)\
structlist_headname=LIST_HEAD_INIT(name)
通过这两个宏完成了链表的初始化,它们的作用相当于将链表的前后向指针指向了自己,如图3所示。
图2 双向循环链表的插入操作
分别代表在head1所指示的dlink1类型的链表中插入结点P1,和在head2所指示的dlink2类型的链表中插入结点P2。虽然都是向链表中插入一个结点,执行的操作是一样的,但是由于使用的链表结点类型不同,就需要编写不同的函数,造成了代码冗余。
对于其它的基本操作,包括删除、查找等都存在同样的问题。
图3 链表的初始化
在list.h中还提供了另外一个初始化宏,同样
可以完成初始化的工作。
#defineINIT_LIST_HEAD(ptr)do{\ (ptr)->next=(ptr);(ptr)->prev=(ptr);\
}while(0)(2)遍历链表宏
#define__list_for_each(pos,head)\
for(pos=(head)->next;pos!=(head);pos=pos->next)
head是指向整个链表的头指针,pos是指向每个结点中后向指针成员的指针,通过pos指针不停的向后移动,可以达到遍历整个链表的目的[5]。
(3)获取整个结构体变量的地址宏
通过遍历链表,获得的是所需结点中后向指针成员的地址,而非结点自身的地址,那么,如何通过这个地址来获取整个结点的地址呢?这就引入了list_entry宏。这个宏可以通过结构体中某个成员的地址来获取整个结构体的地址,这是设计非常巧妙的一个宏,也是比较难理解的一个关键宏。
#definelist_entry(ptr,type,member)\ container_of(ptr,type,member)
这个宏的作用是获取指针ptr指向的member成员所在结点的首地址,这个结点类型是type结构体类型。其中ptr是指向member的指针,member是type结构体类型的成员。关系如图4所示。
[6]
2 Linux内核中的双向循环链表
Linux内核源代码中有很多地方都需要用双向循环链表来组织数据,比如进程、文件、模块等,若使用传统的链表结构会造成大量的冗余代码,降低代码的重用性,因此,Linux内核源码在include/linux/list.h中提供了双向循环链表。2.1 结构体类型定义
区别于传统的双向循环链表,在list.h中定义了这样一个结构体类型
structlist_head{
structlist_head*next,*prev;};
在这个结构体类型定义中,并没有数据成员,而只有两个指向本结构体类型的指针,分别指向其前驱结点和后继结点,因此,这个结构体的主要作用就是嵌套在其它结构体类型的定义中起到链接作用。如果需要构造某种结构体类型的链表,只需要在该结构体类型中定义一个list_head指针成员即可,通过这个指针成员就可以将这种结构体类型的结点链接起来,形成链表。
2.2 几个重要的宏
不同结构体类型的结点怎样链接起来呢?以下几个重要的宏起关键作用。
(1)初始化链表


)
[4]
:
图4 链表中结点首地址的获取
Linux内核链表及其在虚拟文件系统中的应用_专业资料。为了提高代码的重用性,Linux内核提供了一种抽象的双向循环链表结构。通过对这种双向循环链表及其在Linux虚拟文件...
Linux系统中虚拟文件系统... 4页 免费 Linux内核链表及其在虚拟... 5页 ... VFS对象及其数据结构 面向对象的思想在文件系统设计中的应用(面向对象 的设计和...
Linux内核具体体系结构之虚拟文件系统_IT/计算机_...主机和外设通信一般使用三种方式:轮询、DMA 和中断。...所有被打开的文件都 保存到一个双向链表中(其首地...
linux内核之文件系统_计算机软件及应用_IT/计算机_专业资料。介绍了linux中文件...所有已注册的文件系统的 file_system_type 结构形成一个链表, 我们把这个链表称...
? 应用程序使用操作系统的加锁机制,比如 线程锁,信号量来进行保护。 内核链表 ? 定义在 linux/list.h.全部的定义和实现在这一 个头文件里。 ? 内核链表用一...
深入分析 Linux 内核链表_IT/计算机_专业资料。本文详细分析了 2.6.x 内核...2014 Baidu 使用百度前必读
Linux内核链表介绍及例子Linux内核链表介绍及例子隐藏>> www.shapoo.net Linux 内核链表 在 Linux 内核中使用了大量的链表结构来组织数据。这些链表大多采用了 ...
在 Linux 内核中使用了大量的链表结构来组织数据, ... 其余均取自该文件): struct list_head { struct ...我们知道,系统中数据读取操作远多于写操作,而 rwlock...
Linux使用的文件系统:ext2、ext3、ReiserFS ? Unix家族的文件系统:SYSV文件系统...所有超级块链表:super_blocks :s_list域 ? 文件系统特有信息:s_fs_info域 ?...
16 Linux进程控制 18 Linux系统调用 19 Proc文件系统1/2 相关文档推荐...等多种类型 单向链表 双向链表 内核链表在Linux内核中使用了大量的链表结构来组 ...
热门文档