[十月往昔]——Linux内核中的list.h浅谈
为什么要叫做“十月往昔”呢,是为了纪念我的原博客。
不知道为什么,突然想来一个新的开始——而那个博客存活至今刚好十个月,也有十个月里的文档。
十月往昔,总有一些觉得珍贵的,所以搬迁到这里来。
而这篇文章是在09.04.10里写的。
Jason Lee
————————————–cut-line
/*-------------------------------
include/linux/list.h -2.6.29
*/
该文件包含:
链表的初始化
19-21 行定义了一个list_head 结构,只有两个指向list_head 结构的指针,一个next
,一个prev ,作用显而易见。
23 行的宏LIST_HEAD_INIT(name) 与25 行的宏LIST_HEAD(name)
组合进行链表的初始化,即next 和prev 都指向自身。
25 行的静态内联函数INIT_LIST_HEAD(struct list_head *list) 同样是用来初始化链表,效果同上述一点。GNU
下的C 语言对C 进行了扩充,不再是ANSI C ,它里面增添了很多C++ 的特性,所以对内核进行编译只能选用相应的GCC
。
INIT_LIST_HEAD 在有的文献中是以宏的形式出现:
链表的插入
这段程序在两个已知的节点中间插入一个新节点。这里选择的是条件编译,如果没有对CONFIG_DEBUG_LIST
进行宏定义,则定义了__list_add
这个静态内联函数,便于以下两个函数使用。
该函数在指定的head 节点后面插入一个新节点new 。
该函数将一个节点new 插在指定的节点head 之前。
链表的删除
该函数通过设置prev 和next 指针指向彼此,实现了删除二者之间节点的功能。但是这里我有个疑惑,删除的指针的释放在哪里实现。
该函数通过调用上面的内联函数实现节点的删除,这里的LIST_POISON1
和LIST_POISON2
是在linux
/ poison
. h
定义的。此处仍然是条件编译。
链表节点的置换
静态内联函数list_replace 接受两个参数:old 和new ,并通过new
替换old 。而list_replace_init 函数则是通过调用list_replace 进行替换,之后调用INIT_LIST_HEAD
对被替换的old 进行链表初始化。
链表的移动
List_move 函数接受两个参数,第一个参数list 为想要移动的节点指针,第二个参数为目的地节点指针。该函数通过调用__list_del
函数实现list 节点的prev 和next 两个指针互指实现删除list 节点的效果,并且调用list_add
将list 节点插入到head 之后。
List_move_tail 函数将指定节点移到指定链表的尾部,成为尾节点。并且由于链表是循环的,所以移动的节点指向该链表head 节点。具体实现是通过目标节点的prev
和next 互指实现从原始链表中删除list 节点,之后通过调用list_add_tail 将list
节点插入到以head 为表首的链表尾部。
判断节点是否为链表的最后一个
通过判断节点的next 指向是否为表首来确定是否为last 。
判断链表是否为空
通过判断head 节点是否指向自身来判断链表是否为空。
此处函数的作用并不十分理解,对于绿色注释说明部分的Description 和NOTE 部分也是一知半解。单纯地翻一下NOTE 部分:如果没有经过同步化处理,那么如果要达到安全地使用list_empty_careful
这个函数必须限定当前能对指定节点发生的操作仅仅为list_del_init() ,比如当一个CPU 对它进行add 操作的时候不能使用该函数。
该函数能达到的效果是检查链表是否为空,并且检测是否有CPU 在修改当前指定节点的prev 和next 指针。
这里引用一段解释,来自杨沙洲:
“
Linux
链表另行提供了一个
list_empty_careful()
宏,它同时判断头指针的
next
和
prev
,仅当两者都指向自己时才返回真。这主要是为了应付另一个
cpu
正在处理同一个链表而造成
next
、
prev
不一致的情况。但代码注释也承认,这一安全保障能力有限:除非其他
cpu
的链表操作只有
list_del_init()
,否则仍然不能保证安全,也就是说,还是需要加锁保护。
”
判断链表是否只有唯一的一个节点
空表并不是一个节点都没有,唯一的节点也不是指只有一个节点,具体看函数代码我们便可以了解。当一个节点指针被执行LIST_HEAD 了以后,它的prev 和next
指针都指向自身,这便称为空表;而如果它的prev 和next 指针都指向仅有的第二个节点,那么它便称为仅有一个节点。
链表的切割
这里有三个参数,list,head,entry 。
假设原先有链表:head <-> node1 <-> node2 <-> node3 <-> entry <-> node4 <-> head
那么最后会得到链表1 :head <-> node4 <-> head
和链表2 :list <-> node1 <-> node2 <-> node3 <-> entry <-> list 。
这里最好自己画图模拟一下。
链表的合并
假设有两条链表:head <-> node1 <-> node2 <-> node3 <-> head
和:last <-> list <-> first
那么合并的结果是取代了head :last <-> list <-> first <-> node1 <-> node2 <-> node3 <-> last
以下的合并函数都是调用第一个合并内联函数__list_splice ,区别只在于合并取代的位置以及是否对空出来的head 进行初始化,即调用INIT_LIST_HEAD
等宏。
分享到:
相关推荐
本文档是从GiHup上linux/include/linux/list.h复制过来的,有完整版的list.h,但其中含包含Linux的其它头文件的函数,但基本不影响阅读
Linux内核中链表源码 list.h。是内核的/include/linux/list.h文件。
内核链表
ARM Linux内核源码剖析.pdfARM Linux内核源码剖析.pdfARM Linux内核源码剖析.pdfARM Linux内核源码剖析.pdf 完整书签
一份完整的linux内核链表头文件list.h,使用双向循环列表。
Linux内核中文手册.rarLinux内核中文手册.rar
深入分析Linux内核源码 陈莉君.pdf 人民邮电出版社出版
[Linux内核源码].linux-2.6.16.18.tar.bz2.part2.rar [Linux内核源码].linux-2.6.16.18.tar.bz2.part2.rar [Linux内核源码].linux-2.6.16.18.tar.bz2.part2.rar [Linux内核源码].linux-2.6.16.18.tar.bz2.part2.rar
ARM Linux内核源码剖析.pdf是中文版,内容清晰,目录标签全。 对嵌入式计算有很大帮助。(分成2个压缩包:ARM Linux内核源码剖析.pdf.7z.001,ARM Linux内核源码剖析.pdf.7z.002)
[Linux内核源码].linux-2.6.16.18.tar.bz2.part3.rar [Linux内核源码].linux-2.6.16.18.tar.bz2.part3.rar [Linux内核源码].linux-2.6.16.18.tar.bz2.part3.rar [Linux内核源码].linux-2.6.16.18.tar.bz2.part3.rar
深入浅出linux内核源代码之双向链表list_head(list.h).pdf
Linux内核通用链表linuxlist.h阅读.pdf
Linux内核情景分析.pdf Linux内核情景分析.pdf
[Linux内核源码].linux-2.6.16.18.tar.bz2.part1.rar [Linux内核源码].linux-2.6.16.18.tar.bz2.part1.rar [Linux内核源码].linux-2.6.16.18.tar.bz2.part1.rar [Linux内核源码].linux-2.6.16.18.tar.bz2.part1.rar
linux 内核完全注释.rar
linux内核版本, 海思3559A指定版本 59A使用该内核的方式 打补丁 1)将下载的 linux-4.9.37.tar.gz 存放到 osdrv的opensource/kernel目录中 2)在linux服务器中进入 osdrv 的根目录,执行如下命令: cd opensource/...
linux内核完全注释.pdflinux内核完全注释.pdflinux内核完全注释.pdf
详细分析linux 内核启动的过程,值得一看
ARM Linux内核源码剖析.pdf是中文版,内容清晰,目录标签全。 对嵌入式计算有很大帮助。(分成2个压缩包:ARM Linux内核源码剖析.pdf.7z.001,ARM Linux内核源码剖析.pdf.7z.002)