没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
本文详细分析了 内核中链表结构的实现,并通过实例对每个链表操作接口进行了详尽的讲解。
一、 链表数据结构简介
链表是一种常用的组织有序数据的数据结构,它通过指针将一系列数据节点连接成一条数据链,是线性表
的一种重要实现方式。相对于数组,链表具有更好的动态性,建立链表时无需预先知道数据总量,可以随
机分配空间,可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组
织链的空间损失。
通常链表数据结构至少应包含两个域:数据域和指针域,数据域用于存储数据,指针域用于建立与下一个
节点的联系。按照指针域的组织以及各个节点之间的联系形式,链表又可以分为单链表、双链表、循环链
表等多种类型,下面分别给出这几类常见链表类型的示意图:
1. 单链表
图 1 单链表
单链表是最简单的一类链表,它的特点是仅有一个指针域指向后继节点(),因此,对单链表的遍
历只能从头至尾(通常是 空指针)顺序进行。
2. 双链表
图 2 双链表
通过设计前驱和后继两个指针域,双链表可以从两个方向遍历,这是它区别于单链表的地方。如果打乱前
驱、后继的依赖关系,就可以构成二叉树;如果再让首节点的前驱指向链表尾节点、尾节点的后继指向
首节点(如图 中虚线部分),就构成了循环链表;如果设计更多的指针域,就可以构成各种复杂的树状
数据结构。
3. 循环链表
循环链表的特点是尾节点的后继指向首节点。前面已经给出了双循环链表的示意图,它的特点是从任意一
个节点出发,沿两个方向的任何一个,都能找到链表中的任意一个数据。如果去掉前驱指针,就是单循环
链表。
在 内核中使用了大量的链表结构来组织数据,包括设备列表以及各种功能模块中的数据组织。这些
链表大多采用在实现的一个相当精彩的链表数据结构。本文的后继部分就将通过示
例详细介绍这一数据结构的组织和使用。
二、 内核链表数据结构的实现
尽管这里使用 内核作为讲解的基础,但实际上 内核中的链表结构和 并没有什么区别。不同之
处在于 扩充了两种链表数据结构:链表的读拷贝更新()和 链表()。这两种扩展都
是基于最基本的 结构,因此,本文主要介绍基本链表结构,然后再简要介绍一下 和 。
链表数据结构的定义很简单(节选自[include/linux/list.h],以下所有代码,除非加以说明,
其余均取自该文件):
!"#
$#
结构包含两个指向 结构的指针 !" 和 ,由此可见,内核的链表具备双链表功
能,实际上,通常它都组织成双循环链表。
和第一节介绍的双链表结构模型不同,这里的 没有数据域。在 内核链表中,不是在链表
结构中包含数据,而是在数据结构中包含链表节点。
在数据结构课本中,链表的经典定义方式通常是这样的(以单链表为例):
%
%#
&'()! #
$#
因为 &'()! 的缘故,对每一种数据项类型都需要定义各自的链表结构。有经验的 *++程序员应该知
道,标准模板库中的,-采用的是 *++('!,利用模板抽象出和数据项类型无关的链表操作接
口。
在 内核链表中,需要用链表组织起来的数据通常会包含一个 成员,例如在
.中定义了一个 /%0%!%! 结构来描述 . 为某一协议族准备的
1%0%!%0%! 接口,其中就有一个()成员,各个协议族的
/%0%!%! 结构都通过这个 成员组织在一个链表中,表头是定义在%.中的
/%0%!()。从下图中我们可以看到,这种通用的链表结构避免了为每个数据项
类型定义自己的链表的麻烦。 的简捷实用、不求完美和标准的风格,在这里体现得相当充分。
图 3 nf_sockopts 链表示意图
2
三、 链表操作接口
1. 声明和初始化
实际上 Linux 只定义了链表节点,并没有专门定义链表头,那么一个链表结构是如何建立
起来的呢?让我们来看看 LIST_HEAD()这个宏:
3.4(&544(6'786'7 86'7$
3.4(&56'7'9
4(&544(6'7
剩余10页未读,继续阅读
资源评论
wz0704010201
- 粉丝: 11
- 资源: 21
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功