资源描述：
《Linux内核链表及其在虚拟文件系统中的应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2011年3月西安邮电学院学报Mar.2011第16卷第2期JOURNALOFXIANUNIVERSITYOFPOSTSANDTELECOMMUNICATIONSVol16No2Linux内核链表及其在虚拟文件系统中的应用梁琛,陈莉君(西安邮电学院计算机学院,陕西西安710121)摘要:为了提高代码的重用性,Linux内核提供了一种抽象的双向循环链表结构。通过对这种双向循环链表及其在Linux虚拟文件系统中的应用进行分析,可以了解这种链表的巧妙之处。这种链表可以将不同结
2、构体类型的数据链接起来,并可以使用相同的链表操作,从而能有效地提高编程效率。关键词:Linux内核;链表;虚拟文件系统中图分类号:TP311.5文献标识码:B文章编号:10073264(2011)02002905[1]在C语言程序中经常用到双向循环链表来组数据。织数据,链表中每个结点的信息是定义在结构体类1.1双向循环链表的类型定义型中的,当使用的结构体类型不同时,需要创建不同传统的双向循环链表是将每个结点的基本信息的链表,并且需要为每一个链表编写插入、删除、查定义
3、在结构体类型中,并在结构体类型中增加指向找等基本操作函数,但是通常链表这些基本操作的本结构体类型的前向指针和后向指针,用来指示本[2]执行步骤是基本相同的,而只是由于结构体类型不结点的前驱结点和后继结点,从而将若干个结点同,就需要重写代码,花费程序员大量不必要的时有机的链接起来,若首尾结点也连接起来,就构成了[3]间。在Linux内核源代码中也大量用到了这种数据双向循环链表,其结构如图1所示,其中head为结构,如果需要为每一个链表都编写基本操作函数,头指针。结构体类型的定义如下:就会有大量的重复
4、性代码。在研究Linux的虚拟文structdlink{件系统时,发现其中使用的双向循环链表并不需要ElemTypedata;编写这样的冗余代码,而是提供了一种更好的使用structdlink*next,*prev;方式,使得不同结构体类型的结点都可以通过这种};链表链接起来,而且可以使用相同的链表操作,从而提高代码的重用性。本文将对Linux内核2.6版以后的源码中使用的双向循环链表进行分析,研究图1双向循环链表结构Linux内核中双向循环链表的构造、基本操作及其1.2双向循环链表的基本
5、操作在虚拟文件系统中的应用,以及如何在用户程序中通常在对结点类型不同的链表进行相同的操作利用这种巧妙的设计,提高编程效率。时,需要针对不同结构体类型编写不同的函数来完1传统的双向循环链表成。例如,对于插入操作,若找到了要插入结点p在链表中的位置,所需要做的工作就是:修改插入结点在C语言程序中若想根据需要动态地分配和的前后向指针,以及其前驱结点的后向指针和后继释放内存单元,通常可以使用链表结构来组织结点的前向指针,如图2所示。收稿日期:20110120基金项目:西安邮电学院中青年科研基金资助项
6、目(1030439)作者简介:梁琛(1978),女,讲师,硕士,研究方向:Linux操作系统、嵌入式系统,Email:mumulc@xupt.edu.cn;陈莉君(1964),女,教授,硕士,研究方向:Linux操作系统。30西安邮电学院学报2011年3月例如,对于结点类型为structdlink1和struct{&name,&name}dlink2这两个不同结构体类型的链表,需要提供两#defineLIST_HEAD(name)个插入函数,接
7、口形式如下:structlist_headname=LIST_HEAD_INITintinsert1(structdlink1*head1,structdlink1*P1);(name)intinsert2(structdlink2*head2,structdlink2*P2);通过这两个宏完成了链表的初始化,它们的作用相当于将链表的前后向指针指向了自己,如图3所示。图2双向循环链表的插入操作图3链表的初始化分别代表在head1所指示的dlink1类型的链在list.h中还提供了另外一个初始化
8、宏,同样表中插入结点P1,和在head2所指示的dlink2类型可以完成初始化的工作。的链表中插入结点P2。虽然都是向链表中插入一#defineINIT_LIST_HEAD(ptr)do{个结点,执行的操作是一样的,但是由于使用的链表(ptr)->next=(ptr);(ptr)->prev=结点类型不同,就需要编写不同的函数,造成了代码(ptr);冗余。}while(0)对于其它的基本操作,包括删除、查找等都存在(2)遍历链表宏同样的问题。#define__list_fo
