1918_Linux内核中的链表操作-CSDN博客

背景概述

这是一个非常常用的数据结构，也有很多可以直接借用的操作实现方式。我最初接触到的是CDA中的设计，CDA中给出来的是框架，而整个设计实现则是我自己实现的。不过，这部分实现并没有得到很好的重用。现在回忆下来，主要的原因还是因为当时的设计不够独立，引用了不少其他的内容。

后来接触了几套其他的设计，有专门在嵌入式平台上应用的。我逐行阅读代码并尝试分析使用这些操作的一套设计是FreeRTOS中的相关设计。很遗憾的是，这个设计也没有在我自己的工程中得到重复运用。

在大学学习数据结构的时候，我当时的老师参考的是清华严蔚敏教授的书籍。里面有一个通过数组来实现链表的设计，比较容易理解也很容易实现。这个是我在很多软件设计中反复应用的一套设计。

然而综合看来，上面的这些用法在实现上还是跟通用或者是广泛应用差距很远。在看别人的作品的时候，发现有人直接借用linux内核设计中的list.h，这个文件提供了链表操作的大部分基础操作设计。我查阅代码之后发现，其实文件中有很多个名称叫做这个的文件，但是看看内容有一个很容易作为首选，因为我选做首选的没有对其他文件的依赖。

从代码的内容看，实现的是比较实用的双向链表。

代码

源代码参考： c_units: 我搜集的一些C语言复用模块

代码阅读

初始化

这里主要还是2个“接口”，提供的都是偏初始化的功能。其中，LIST_HEAD提供的是定义并且同时进行初始化，而INIT_LIST_HEAD从设计上来看更多的应该是运行时中的初始化。

节点插入

节点的插入，本质上来说是同一个接口。使用的时候应该是使用第二个，名称简洁一些的，这个隐藏了一部分不必要的信息。但是应该注意的是，这个插入的位置是默认在链表头的位置做插入的。因为，链表头部做插入，前驱刚好是链表头，而后继则是链表头之前的后继。

节点删除

从定义上来说，前面两个接口都是库函数，不对外开放。因此，提供的功能当前看来是针对节点的删除功能。删除的时候，会把前驱和后继设定为两个特殊值。一般来说会设置为不可访问的存储地址，错误访问的时候直接触发错误。

根据成员指针信息获取结构体指针

为了理解后面的内容，先来理解一下这里的两个宏定义。这两宏定义的设计是非常巧妙的。

第一个offsetof其实是取了一个结构体数据的成员的地址，之后转换成了整型。然而，这个结构体数据比较特殊，是存储于地址0的地方，因此这里获取到的数值也就刚好是这个数据成员的偏移。

第二个container_of则有几分反向操作的意味了。首先，通过typeof获取数据成员的数据类型，之后定义一个成员数据类型的指针。之后，通过char *转换了数据类型之后确保指针的操作是按照字节来处理。通过这个成员的指针数值，减去本身的偏移量也就是结构体数据的存储位置。通过数据类型转换，这样就可以获取结构体的指针了。

获取当前节点的结构体指针

遍历迭代结构

安全遍历迭代-防止迭代中有元素删除

尾部追加

这个功能是很适合实现队列机制的。

需要注意的是，这个队列机制以及整个链表的功能是不能够重复存放相同的entry的，因此如果有类似的需求最好还是结合堆栈来实现多个副本。

首、尾、头、空的判断

上面的判断比较简单。

使用测试

以上是测试代码。

测试记录如下：

1. test for list.

2. test_head: 0x0000000000404010

3. display test_elements information:

test_elements[0] -> 0x00000000004089A0

test_elements[0] -> id: 0

test_elements[0] -> list_node: 0x00000000004089A0

test_elements[1] -> 0x00000000004089B8

test_elements[1] -> id: 1

test_elements[1] -> list_node: 0x00000000004089B8

test_elements[2] -> 0x00000000004089D0

test_elements[2] -> id: 2

test_elements[2] -> list_node: 0x00000000004089D0

test_elements[3] -> 0x00000000004089E8

test_elements[3] -> id: 3

test_elements[3] -> list_node: 0x00000000004089E8

test_elements[4] -> 0x0000000000408A00

test_elements[4] -> id: 4

test_elements[4] -> list_node: 0x0000000000408A00

test_elements[5] -> 0x0000000000408A18

test_elements[5] -> id: 5

test_elements[5] -> list_node: 0x0000000000408A18

test_elements[6] -> 0x0000000000408A30

test_elements[6] -> id: 6

test_elements[6] -> list_node: 0x0000000000408A30

test_elements[7] -> 0x0000000000408A48

test_elements[7] -> id: 7

test_elements[7] -> list_node: 0x0000000000408A48

test_elements[8] -> 0x0000000000408A60

test_elements[8] -> id: 8

test_elements[8] -> list_node: 0x0000000000408A60

test_elements[9] -> 0x0000000000408A78

test_elements[9] -> id: 9

test_elements[9] -> list_node: 0x0000000000408A78

4. test for list_add.

5. test for list_for_each_entry.

pos[9] -> id: 9

pos[8] -> id: 8

pos[7] -> id: 7

pos[6] -> id: 6

pos[5] -> id: 5

pos[4] -> id: 4

pos[3] -> id: 3

pos[2] -> id: 2

pos[1] -> id: 1

pos[0] -> id: 0

6. test for list_for_each_entry_safe.

pos[9] -> id: 9

pos[8] -> id: 8

pos[7] -> id: 7

pos[6] -> id: 6

pos[5] -> id: 5

pos[4] -> id: 4

pos[3] -> id: 3

pos[2] -> id: 2

pos[1] -> id: 1

pos[0] -> id: 0

7. test for list_for_each_entry_reverse.

pos[0] -> id: 0

pos[1] -> id: 1

pos[2] -> id: 2

pos[3] -> id: 3

pos[4] -> id: 4

pos[5] -> id: 5

pos[6] -> id: 6

pos[7] -> id: 7

pos[8] -> id: 8

pos[9] -> id: 9

8. test for list_del and list_empty.

list is empty.

9. test for list_add_tail.

pos[0] -> id: 0

pos[1] -> id: 1

pos[2] -> id: 2

pos[3] -> id: 3

pos[4] -> id: 4

pos[5] -> id: 5

pos[6] -> id: 6

pos[7] -> id: 7

pos[8] -> id: 8

pos[9] -> id: 9

pos[9] is last.

10. test for list_move_tail.

pos[0] -> id: 0

pos[1] -> id: 1

pos[2] -> id: 2

pos[3] -> id: 3

pos[4] -> id: 4

pos[5] -> id: 5

pos[6] -> id: 6

pos[8] -> id: 8

pos[9] -> id: 9

pos[7] -> id: 7

pos[7] is last.