为什么要叫做“十月往昔”呢,是为了纪念我的原博客。
不知道为什么,突然想来一个新的开始——而那个博客存活至今刚好十个月,也有十个月里的文档。
十月往昔,总有一些觉得珍贵的,所以搬迁到这里来。
而这篇文章是在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
等宏。
分享到:
相关推荐
高中同学三十周年聚会致辞:重话往昔同学情(范文)..doc
教师资格考试、教师招聘考试资料——细数往昔之教育法律法规时间考点.pdf
教育资料
jdk 1.8 压缩包内包含windows 和 linux 系统64位安装二进制程序及tar包,linux版下载解压配置环境变量即可,windows版直接执行安装
高中同学三十周年聚会致辞:重话往昔同学情.docx
3.2 网页基本搜索——寻找记忆中的网站36 3.2.1 网页基本搜索简介36 3.2.2 新建普通查询36 3.2.3 布尔逻辑搜索——更多关键字37 3.2.4 搜索百宝箱38 3.3 网页语法高级搜索——探寻“达芬奇密码”41 3.3.1 网页语法...
优秀校园演讲稿:忆往昔岁月.doc
从执行体程序库中的CLLogger类可知,通过缓存要写入文件中的数据,能够提高读写磁盘的性能。编写一个文件操作的封装类,调用该类的写操作接口时,数据要首先写到缓存,然后再根据策略写到文件中。调用该类的读操作...
非递归(层序,前序,中序,后序)遍历二叉树C语言实现所有源文件,包括:main.c、BinaryTree.h、BinaryTree.c、LinkStack.h、LinkStack.c、LinkQueue.h、LinkQueue.c。
忆往昔60年通信发展国人自豪看未来信息时代迎挑战再立新功.pdf
《[回首历史展望未来作文]回首往昔展望未来国庆周年演讲稿》.doc
房地产行业全景复盘深度报告:往昔峥嵘岁月、今朝何惧风流-37-申万宏源-6页.pdf
初中语文文学讨论美文荐读往昔岁月
序携来百侣曾游,忆往昔峥嵘岁月稠。--《沁园春·长沙》对于Android,我也算是老人了,所谓,有文有真想。正由于这段玩票经历,使得我在毕业后,鬼使神差的成为移动平台的一名码工,再次有机会放肆的拥抱Android。...
2015年高中语文优秀作文回忆往昔祝福友谊素材
#资源达人分享计划#
PDF文档;中国城市统计年鉴_二_地级以上城市统计资2014.p.pdf
中国光通信的发展历史充满曲折和激情。回想起来,可以用“峥嵘岁月稠”来形容。这是一个多少万人共同奋斗的事业,本文只是将笔者个人的经历和了解的情况,作为中国光通信事业前期发展的局部,作一回顾。