Linux内核链表及其在虚拟文件系统中的应用_论文

21 0 1年 3月   第1 6卷 第 2期  西 安 邮 电 学 院 学 报  J R OU NA     IAN  L OF X ’ UNI RSTY O  0S   N   L C MMUNI T1 NS VE I   F P TS A D TE E O CA 0   Ma.2 1  r 01 V0 6No 2 L1  .  L n x内核 链 表 及 其 在 虚 拟 文 件 系统 中 的 应 用  iu 梁 琛, 陈莉 君  702) 1 1 1  ( 西安 邮 电 学 院 计 算 机 学 院 , 西 西安 陕 摘 要 : 了提 高代 码 的 重 用性 , iu 为 Ln x内核 提 供 了一 种 抽 象 的 双 向循 环 链 表 结 构 。 通 过 对 这 种 双 向循 环 链 表 及 其 在  Ln x 拟文件 系统 中的应 用进行 分析 , iu 虚 可以 了解这种链袁 的巧妙之 处。这种链表 可以将不 同结 构体 类型 的数据  链 接 起 来 , 可 以使 用相 同 的 链 表 操 作 , 而 能 有 效 地 提 高 编程 效 率 。 并 从   关 键 词 i iu 内核 ;链 表 ;虚 拟 文 件 系统   Ln x 中 图分 类号 : P 1.   T 315 文献标识码 :  B 文 章 编 号 :0 7 2 4 2 1 )2 0 9 5 10 —3 6 (0 10 —0 2 —0  在 C语 言 程 序 中经 常 用 到 双 向循 环 链 表来 组  数 据[    。 1 1 双 向循环 链表 的类型 定 义  . 织数 据 , 链表 中每个 结 点 的信 息 是 定 义 在 结 构 体 类  型中的, 当使 用 的结 构体 类 型不 同时 , 需要 创 建不 同  的链 表 , 并且 需 要 为 每一 个 链 表 编 写 插 人 、 除 、 删 查  传 统 的双 向循环链 表 是将 每个 结点 的基本 信息  定 义在 结 构体类 型 中, 在 结 构体 类 型 中增 加 指 向  并 找 等基 本操 作 函数 , 是 通 常 链 表 这 些 基 本 操 作 的  但 执行 步 骤是 基本 相 同 的 , 只 是 由于 结 构 体 类 型 不  而 同, 就需 要 重 写 代 码 , 费 程 序 员 大 量 不 必 要 的 时  花 问 。在 L n x内核 源代码 中也大 量用 到 了这 种数 据  iu 结构 , 如果需 要 为每 一个 链表 都 编写基 本 操作 函数 ,   就会 有 大量 的重 复性 代码 。在研究 Ln x的虚拟 文  iu 件 系统 时 , 现 其 中使 用 的双 向循 环链 表 并 不 需 要  发 本 结构 体 类型 的前 向指针 和后 向指 针 , 来 指示 本  用 结 点 的前 驱结 点 和后 继 结 点[ 从 而将 若 干 个 结点   , 有 机 的链 接起来 , 首尾结 点 也连接 起来 , 若 就构 成 了  双 向循 环链 表[ 其 结 构 如 图 1所 示 , 中 h a 引, 其 ed为  头指针 。结构体 类 型的定 义如 下 :   sr c dik  tu t l {   n ElmTy e d t ; e p   aa  s r c  l k *n x . t u td i n e t *p e ; r v  编 写这样 的冗 余 代 码 , 是 提 供 了一 种 更 好 的使 用  而 方式 , 得不 同结构 体 类 型 的结 点 都 可 以通 过 这 种  使 链表 链 接起来 , 而且 可 以使用 相 同 的链 表 操作 , 而  从 提 高代 码 的重用 性 。本文 将对 Ln x内核 2 6 以  iu .版 后 的源 码 中 使 用 的双 向 循 环 链 表 进 行 分 析 , 究  研 ) ;   h  叵 叵 叵   固 匡 巨 仁 … 圃   鲥   I= = = = 二 = = 二 二 二 = =     = = =二 == =二 二== = 图 1 双 向循 环 链 表 结 构  l   Ln x内核 中双 向循 环 链 表 的构 造 、 本 操 作 及 其  iu 基 在虚 拟 文件 系统 中 的应用 , 以及 如 何 在 用 户 程 序 中  利用 这种 巧 妙 的设计 , 高编 程效 率 。 提   1 2 双 向循环链 表 的基本 操 作  . 通 常 在对结 点类 型不 同 的链 表 进行相 同的操作  时 , 要针 对不 同结 构 体 类 型 编 写不 同的 函 数来 完  需 成 。例 如 , 对于插 入操 作 , 若找 到 了要插入 结 点 P在  1 传 统 的双 向循 环 链 表  在 C语 言程 序 中若 想 根 据 需 要 动 态 地 分 配 和  释 放 内 存 单 元 , 常 可 以 使 用 链 表 结 构 来 组 织  通 收 稿 日期 : 0 1 1 0 2 1 —0 —2   链 表 中 的位置 , 需要 做 的工作 就是 : 所 修改 插入 结点  的前后 向指针 , 以及 其 前 驱 结 点 的后 向指 针 和后 继  结 点 的前 向指针 , 图 2 示 。 如 所   基 金 项 目 : 安 邮 电 学 院 中青 年 科 研 基 金 资 助 项 目(0 —4 9  西 1 30 3 ) 作者简介 :  ̄ ( 9 8) 女 , 师 , 士 , 究 方 向:Ln x操 作 系统 、 入式 系 统 ,Emalmu l@ x p. d . n 陈莉 君  17一, 讲 硕 研 iu 嵌 - i : muc u te u c ; (9 4) 女 , 授 , 土 , 究 方 向 : iu 操 作 系 统 。 1 6 一, 教 硕 研 Ln x   ?3 ? O   西 安 邮 电  学 院 学

相关文档

Linux虚拟文件系统内核机制研究与改进策略
基于Linux内核虚拟主机监控系统的研究与实现
新版本的Linux内核支持Ceph文件系统功能
Linux虚拟文件系统对物理文件的管理
Linux内核模块与/proc文件系统
Linux操作系统中通用双向循环链表的实现分析
Linux文件系统的模拟实现
带Xen虚拟化技术支持的Linux内核定制编译
虚拟嵌入式开发环境中的Linux内核移植与裁剪
虚拟网络转发设备在Linux内核中的设计与实现
电脑版