Linux内核链表及其在虚拟文件系统中的应用
32
西 安 邮 电 学 院 学 报 2011年3月
三个list_head指针,使用这些指针可以建立三个链表,分别为哈希链表、索引节点链表以及目录项链表。以目录项链表为例,链表的结构如图5

所示。
structlist_headlist;};
首先,初始化链表。structlist_headhead;
LIST_HEAD(head);
或INIT_LIST_HEAD(&head);
其次,以插入结点new为例,可以通过list_add(&new.list,&head);将new结点插入到head所指示的链表当中。
接下来若要遍历链表,提取链表中的每个元素,可以如下方式来操作[10]:
list_for_each(pos,&head)
newdata=list_entry(pos,structdlink,list);其中,pos是(structlist_head*)的指针变量,它是遍历过程中的向后移动的指针,newdata用来获取链表上每个结点的首地址。
其余的操作基本思想大致相同,在此不做分析。
图5 索引节点中目录项链表结构
(1)初始化链表structlist_headhead;
LIST_HEAD(head);
创建了一个空链表,链表表头是head[9]。也可以下面的形式初始化:
INIT_LIST_HEAD(&head);(2)插入
假设有一个新的索引节点new_inode需要添加到链表头,可以这样操作:
list_add(&new_inode.i_dentry,&head);
由此看出,目录项链表中记录的并不是新插入索引节点new_inode的地址,而是其中的i_dentry成员的地址。
(3)删除
当需要删除目录项链表中的索引节点new_in ode时,可以这样操作:
list_del(&new_inode.i_dentry);
(4)遍历
定义一个(structlist_head*)指针变量pos,然后调用
list_for_each(pos,&head)就可以对目
录项链表进行遍历。
(5)通过链表指针获取结点首地址
要访问目录项链表中第一个索引节点,可以这样调用:
list_entry(&head.next,structinode,i_den try);
5 结论
本文研究分析了Linux内核中常用的双向循环链表结构,并对其在虚拟文件系统中的应用进行了分析。分析表明Linux内核中使用的双向循环链表结构是一种能有效提高代码重用性,提高编码效率的数据组织方式,若将这种链表结构用于用户程序,也可以提高程序员的编码效率,值得借鉴。
参 考 文 献
[1] 谭浩强.C语言程序设计[M].北京:清华大学出版
社,2005.
[2] 刘宾礼,孙俊忠,周智勇,等.链表浅析[J].电脑学习,
2010,(1):141 142.
[3] 严蔚敏,吴伟民.数据结构[M].北京:清华大学出版
社,2004.
[4] 余旭.Linux源码分析 链表代码分析[EB/OL].
(2005 11 17)[2011 01 04].doc.guandang.net[5] 陈莉君.Linux内核代码赏析与应用(二)-链表之实
现[EB/OL].(2008 12 18)[2011 01 04].doc.guandang.net
[6] 任桥伟.Linux内核修炼之道[M].北京:人民邮电出
版社,2010.
[7] 毛德操.Linux内核源代码情景分析[M].杭州:浙江
大学出版社,2001.
[8] 陈莉君.Linux操作系统原理与应用[M].北京:清华
大学出版社,2006.
[9] 杨沙洲.深入分析Linux内核链表[EB/OL].(2004
08 [ /w4 在用户程序中的应用
如果把双向循环链表用于用户程序,也能大大提高代码的重用性。可以在用户程序自定义的结构
体类型中定义一个或多个list_head指针,用于链接不同的链表。例如,将传统的循环双向链表使用的结构体进行改写,其中只有一个list_head指针,结构体类型定义如下:
structdlink{
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内核中使用了大量的链表结构来组 ...
热门文档