linux内核中的list.h文件中线性链表的分析（一）

我会带着你远行 2022-09-26 08:44 181阅读 0赞

一、背景

初次接触linux内核，从最简单的数据结构，线性表结构开始学习。使用cd命令进入/usr/src/kernel/3.10.0-229.el7.x86\_64/include/linux中，找到其中的list.h文件并分析它。

二、分析过程

1、初始化链表头

![20160921141238000][]

我们可以看到这里有两个宏定义。第一个是带有变量的宏定义。第二个宏定义使用了第一个宏定义LIST\_HEAD\_INIT(name)。

这样，当要申明并初始化自己的链表头如head时，就可以直接调用宏，LIST\_HEAD(head)。

如此就有初始化struct list\_head head = \{&(head),&(head)\}。

那么结构体类型struct list\_head是在哪里定义的呢？

往回翻我们可以看到头文件

![20160921172541186][]

这里一看就会发现头文件types.h很像是定义struct list\_head的文件。

进入这个文件里会找到这样一行：

![20160921172938047][]

看到这个定义我们也就知道了，head的前趋与后继指针都指向了head自己(prev and next 与head同为struct list\_head结构)。

现在考虑函数，关键字static表明该函数是一个内部函数，限制了函数的作用域，使函数只能在文件内部被调用。

关键字inline告诉编译程序这是一个内联函数，当然此修饰符可以不加，但为了减少内存的占用，还是加入为好。

该函数的作用与宏定义的函数是相同的。均是初始化链表头。

2、添加新结点

![20160921202104297][]

![20160921202107402][]

![20160921202110532][]

后面两个函数通过调用第一个函数实现new结点插入head结点之前或之后。

首先来看第一个调用函数的实现过程：将指向结构体类型struct list\_head的指针new与head传入函数中。

现在我假设head结点后跟着的是data结点。

那么

1.next->prev = new

这一步会将head的下一个结点data的prev指针的地址更改为new的地址。

这样data的上一个结点变为了new。

2.new->next = next

这一步会将new的next指针的地址设置成head的本来的下一个结点的地址，即data的地址。

这样new的下一个结点变为了data。

3.new->prev = prev

这一步会将new的prev指针设置成head的地址。

4.prev->next = new

这一步会将head的next指针的地址更改为new的地址。

好了，通过这四步，成功的将new结点插入到了head结点之后的位置。

接下来看第二个调用函数的实现过程：

现在我假设head结点前跟着的是data结点。

那么

1.next->prev = new

这一步会将head结点的prev更改为new的地址。

这样head的前趋结点变为了new。

2.new->next = next

这一步会将new的next指针的地址设置为head的地址。

这样new的后继结点变为了head。

3.new->prev = prev

这一步会将new的prev指针地址设置为head的原来的前趋data的地址。

这样new的前趋结点就是data。

4.prev->next = new

这一步会将data的next指针更改为new的地址。

这样new就成了data的后继结点。

通过这四步，成功的将new结点插入到了head结点之前的位置。

3.删除结点

![20160921210926612][]

![20160921210930285][]

类似上面添加结点，这里删除结点也是有两个函数来调用另一个函数来实现。

由于两个调用函数功能类似，其中第二个调用函数比第一个调用函数功能上更加完善，

所以这里只就第二个调用函数进行分析。

假设有三个结点data\_1，entry，data\_2，entry为data\_1的后继结点，data\_2为entry的后继结点。

将entry的地址传入函数后，entry->prev表示的是data\_1的地址，entry->next表示的是data\_2的地址。

这两个实参在传入函数\_\_list\_del后，就有

data\_2->prev = &data\_1

data\_1->next = &data\_2

这就显而易见了，data\_1的next指针不再指向entry，而是指向data\_2，

并且data\_2的prev指针也不再指向entry，而是指向data\_1。

接下来的两个赋值语句是将entry的next指针指向变为LIST\_POISON1;

将entry的prev指针指向变为LIST\_POISON2。这两个均为宏定义，在头文件poison中被定义。

4.结点的替换

![20160921213253185][]

以上这两个函数都可以对old结点与new结点进行替换。

但是第二个函数功能更完善，它除了替换外还将old的prev指针与next指针改为了old结点自己。

现进行分析：

假设有结点data\_1,old,data\_2，且old结点是data\_1的后继结点，data\_2是old的后继结点。

那么将old替换为new结点的方法很显然是将new的prev指针改为data\_1的地址。next指针改为data\_2的地址。

并且将data\_1的next指针改为new的地址，将data\_2的prev指针改为new的地址。

第一个被调用的函数即为如此算法。这里不再赘述。

三、总结

这里先分析了几种线性链表的操作，往下还有许多线性链表的操作值得去分析，但分析方法大致相同。

并且有许多函数是调用其它函数进行操作。

linux内核中源代码的营养价值很高，一是代码的写作思路十分清晰，值得我们学习与借鉴。二是代码的写作可读性非常高，

每个变量与函数的定义都是经过数次推敲写出的，写作习惯值得我们学习与借鉴。三是从linux内核的源代码中我们可以对

许多的基础知识进行检验与实践。

[20160921141238000]: /images/20220717/e3af861b5ba74b9cbb2a353add019836.png
[20160921172541186]: /images/20220717/8fb329cc829d466baf0d813d9a3ddffe.png
[20160921172938047]: /images/20220717/c97daf146db94d05badad8e3cd6cad8d.png
[20160921202104297]: /images/20220717/a11b2c1d3a4d449bbb00a93b8134ee0c.png
[20160921202107402]: /images/20220717/d130fd09397c4161b966fda44e386cbc.png
[20160921202110532]: /images/20220717/00a01ef270a7435499bb12e64ef60d96.png
[20160921210926612]: /images/20220717/9b98800e879647f78f439aa5b449267d.png
[20160921210930285]: /images/20220717/56db81d162e4423eb11e8207d93942d5.png
[20160921213253185]: /images/20220717/bbf795558e134ae4b4e09e000f500ce6.png