当前位置: 首页 > Linux kernrl > 正文

[原]list.h 解析

                                           内核数据结构list.h 解析

首先这个数据结构不同于我们我们设计的链表结构。

其实链表这种结构的各种操作就是改变链表的指针域而已,所以可以发现内核的链表结构在设计的时候其实只有指针域。

我的内核版本: 4.0.8-200.fc21.x86_6  此篇博客所有的源码都来自这个版本的内核。

节点的定义在./include/types.h 中

 

 其实就是:

可以看到链表的核心其实就是指针域的改变。

下面是两个头结点的初始化宏。

这两句是源代码的头两个宏定义,作用是初始化一个链表节点的链接
例如申请一个变量head作为头结点
    LIST_HEAD(head) 等价于struct list_head head = {&(head),&(head)};
    就是对头节点的赋值了


同样有一个函数可以初始化

在已知的两个节点中插入一个节点,此处是已经知道这两个节点的情况:
有了这个添加一个节点的函数,我们基本可以添加元素到任意位置了
例如添加一个节点进头结点之后
添加一个节点到头指针之前

如果删除一个节点,其实本质上是两个节点之间的操作

如果需要删除一个具体存在的节点

删除一个节点并且给相应的节点处理

使用一个新的节点替换一个旧的节点

使用一个新的节点替换一个旧的节点并且将旧的节点置空


删除一个结点从链表中,并且重新初始化

删除一个节点并且在这个位置上增加一个其它的节点

//删除一个节点的前一个节点,并且插入一个新节点

/测试一个节点是不是其头节点


测试一个链表是不是空的


测试一个链表是否非空


反转一个节点


测试一个链表是不是仅仅只有一个节点


链表分割函数一共有三个参数,list :新的链表头结点;head:裁剪剩下的链表
entry:包含在链表head内并且是开始裁剪的结尾


一个分割链表的实际操作

合并操作,这里主要看下核心步骤,就是将list领头的这个链表插入到
prev 和 next 之间不包含list 节点


@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 链表的宏遍历再说这个之前,需要看几个必须的宏,不然,难以理解,

这是通过一个已经知道的指针地址,得到这个结构体的首地址,这样做封装性更好,适用范围更广。

这个宏的详细代码再下边


offsetof 的代码还在下边

这一句,就是声明一个type 的member 类型的指针 __mptr  并且赋值ptr.


这个宏可以得到member 相对于结构体首地址的相对地址。

这一句,就可以得到这个结构体的首地址了,就是地址相减,用member的地址减去它相对于首地址的偏移量就是这个结构体的首地址。


@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

这里ptr是一个链表的头结点,这个宏就是取得这个链表第一个元素的所指结构体的首地址


判断一个链表是否为空,且取首地址。

也可以根据变量的next与prev来确定结构体的地址

链表的遍历

遍历一遍链表,使用entry方法

pos 表示结构体变量,head 是头结点,member 是list_head 在结构体当中的名字,这个函数就是如果Pos 为非空,那么pos就是其本身,否则在链表头强制扩充一个虚指针,为了list_for_each_entry_continue()做准备

可以指定链表的任意一个节点开始遍历
同上从前边遍历 内核哈希链表:

这个链表和我们平时常见的链表有很大的不同,哈希表的结构设计和普通的链表有很大的区别

首先哈希表的头结点和其它节点有很大的不同。

这个链表首先使用的是hlist_head 节点做头结点,然后使用hlist_node 做其它节点,最后一个节点指向NULL
其中**prev 指向的是前一个节点的next.就是指向自己。


如果画成图就是这个样子的。




这一句也不理解,这个for循环还是在判断pos这个东西是不是为空值于后边的部分,其实就是一个赋值操作,但是它必须返回1,

这个样子了,这个部分始终返回1.

作者:zmrlinux 发表于2015/9/9 20:45:22 原文链接
阅读:42 评论:0 查看评论
]]>

本文固定链接: http://zmrlinux.com/2015/09/10/%e5%8e%9flist-h-%e8%a7%a3%e6%9e%90/ | Kernel & Me

该日志由 root 于2015年09月10日发表在 Linux kernrl 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: [原]list.h 解析 | Kernel & Me