Linux内核链表及其在虚拟文件系统中的应用
2011年3月
第16卷第2期西 安 邮 电 学 院 学 报
JOURNALOFXI ANUNIVERSITYOFPOSTSANDTELECOMMUNICATIONSMar.2011Vol 16No 2
Linux内核链表及其在虚拟文件系统中的应用
梁 琛,陈莉君
(西安邮电学院计算机学院,陕西西安 710121)
摘要:为了提高代码的重用性,Linux内核提供了一种抽象的双向循环链表结构。通过对这种双向循环链表及其在Linux虚拟文件系统中的应用进行分析,可以了解这种链表的巧妙之处。这种链表可以将不同结构体类型的数据链接起来,并可以使用相同的链表操作,从而能有效地提高编程效率。关键词:Linux内核;链表;虚拟文件系统
中图分类号:TP311.5 文献标识码:B 文章编号:1007 3264(2011)02 0029 05
在C语言程序中经常用到双向循环链表来组织数据,链表中每个结点的信息是定义在结构体类
型中的,当使用的结构体类型不同时,需要创建不同的链表,并且需要为每一个链表编写插入、删除、查找等基本操作函数,但是通常链表这些基本操作的执行步骤是基本相同的,而只是由于结构体类型不同,就需要重写代码,花费程序员大量不必要的时间。在Linux内核源代码中也大量用到了这种数据结构,如果需要为每一个链表都编写基本操作函数,就会有大量的重复性代码。在研究Linux的虚拟文件系统时,发现其中使用的双向循环链表并不需要编写这样的冗余代码,而是提供了一种更好的使用方式,使得不同结构体类型的结点都可以通过这种链表链接起来,而且可以使用相同的链表操作,从而提高代码的重用性。本文将对Linux内核2.6版以后的源码中使用的双向循环链表进行分析,研究Linux内核中双向循环链表的构造、基本操作及其在虚拟文件系统中的应用,以及如何在用户程序中利用这种巧妙的设计,提高编程效率。
数据[1]。
1.1 双向循环链表的类型定义
传统的双向循环链表是将每个结点的基本信息定义在结构体类型中,并在结构体类型中增加指向本结构体类型的前向指针和后向指针,用来指示本结点的前驱结点和后继结点,从而将若干个结点有机的链接起来,若首尾结点也连接起来,就构成了双向循环链表[3],其结构如图1所示,其中head为头指针。结构体类型的定义如下:
structdlink{
ElemTypedata;
structdlink*next,*prev;}

;
[2]
图1 双向循环链表结构
1.2 双向循环链表的基本操作
通常在对结点类型不同的链表进行相同的操作时,需要针对不同结构体类型编写不同的函数来完成。例如,对于插入操作,若找到了要插入结点p在链表中的位置,所需要做的工作就是:修改插入结点的前后向指针,以及其前驱结点的后向指针和后继结点的前向指针,如图2所示。
1 传统的双向循环链表
在C语言程序中若想根据需要动态地分配和释放内存单元,通常可以使用链表结构来组织
收稿日期:2011 01 20
基金项目:西安邮电学院中青年科研基金资助项目(103 0439)
作者简介:梁琛(1978 ),女,讲师,硕士,研究方向:Linux操作系统、嵌入式系统,E mail:mumulc@xupt.edu.cn;陈莉君
(1964 ),女,教授,硕士,研究方向:Linux操作系统。
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内核中使用了大量的链表结构来组 ...
热门文档