Email: BuddyZhang1 buddy.zhang@aliyun.com
目录
链表
链表是 Linux 内核中最简单、最普通的数据结构。链表是一种存放和操作可变数量元素(常称为节点) 的数据结构。链表和静态数组的不同之处在于，它所包含的元素都是动态创建并插入链表的，在编译时 不必知道具体需要创建多少个元素。另外也因为链表中每个元素的创建时间各不相同，所以它们在内存 中无须占用连续内存区。正是因为元素不连续地存放，所以各元素需要通过某种方式被连接在一起。 由于链接的方式不同，链表又分为单链表、双链表、环形链表等。
单链表
正是因为元素不连续地存放，所以各元素需要通过某种方式被连接在一起，于是每个元素都包含一个 指向下一个元素的指针，当有元素加入链表或从链表中删除元素时，简单的调整指向下一个节点的指针 就可以，这样简单的链表称为单链表。单链表可以简单定义如下：
struct list_elem {
struct list_elem *next;
};单链表中只包含一个指向下一个节点的指针，单链表组织如下图：
双链表
正是因为元素不连续地存放，所以各元素需要通过某种方式被连接在一起，于是每个元素都包含一个 指向下一个元素的指针，以及一个指向前一个节点的指针，因为他们可以同时向前或向后相互链接， 所以这种链表被称为双链表。当有元素加入链表或从链表中删除元素时，需要对链表的前一个节点和后 一个节点都需要进行修改。双链表可以简单定义如下：
struct list_elem {
struct list_elem *next;
struct list_elem *prev;
};双链表中包含一个指向下一个节点的指针和一个指向前一个节点的指针，双链表组织如下图：
内核双链表
Linux 内核提供了一种双链表的实现方式，以此双链表为众多数据结构提供了链表支持，其定义如下：
include/linux/list.h
struct list_head {
struct list_head *next;
struct list_head *prev;
};内核使用 struct list_head 结构定义了双链表的基础元数据，结构只包含了两个指针，用于 之前前一个节点和后一个节点。内核将这个结构嵌入多众多数据结构中，以此构造复杂的功能。
内核双链表最小实践
内核提供了 struct list_head 作为双链表的元数据，并提供了一整套的链表操作函数，开发者 可以将双链表内嵌到私有数据结构中，然后使用内核提供的接口在私有数据结构中使用双链表。本节 的最小实践基于 Linux 5.0，如果还未搭建 Linux 5.0 开发环境，请参考文档：
准备好开发环境后，开发者编写一个独立的驱动，以此实践内核双链表。驱动源码如下：
/*
* bindirect-list
*
* (C) 20179.04.25 <buddy.zhang@aliyun.com>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation.
*/
/*
* bidirect-list
*
* +-----------+<--o +-----------+<--o +-----------+<--o +-----------+
* | | | | | | | | | | |
* | prev | o----| prev | o----| prev | o----| prev |
* | list_head | | list_head | | list_head | | list_head |
* | next |---o | next |---o | next |---o | next |
* | | | | | | | | | | |
* +-----------+ o--->+-----------+ o--->+-----------+ o--->+-----------+
*
*/
#include <linux/kernel.h>
#include <linux/init.h>
/* header of list */
#include <linux/list.h>
/* private structure */
struct node {
const char *name;
struct list_head list;
};
/* Initialize a group node structure */
static struct node node0 = { .name = "BiscuitOS_node0", };
static struct node node1 = { .name = "BiscuitOS_node1", };
static struct node node2 = { .name = "BiscuitOS_node2", };
static struct node node3 = { .name = "BiscuitOS_node3", };
static struct node node4 = { .name = "BiscuitOS_node4", };
static struct node node5 = { .name = "BiscuitOS_node5", };
static struct node node6 = { .name = "BiscuitOS_node6", };
/* Declaration and implement a bindirect-list */
LIST_HEAD(BiscuitOS_list);
static __init int bindirect_demo_init(void)
{
struct node *np;
/* add a new entry on special entry */
list_add(&node0.list, &BiscuitOS_list);
list_add(&node1.list, &BiscuitOS_list);
list_add(&node2.list, &BiscuitOS_list);
list_add(&node3.list, &BiscuitOS_list);
list_add(&node4.list, &BiscuitOS_list);
list_add(&node5.list, &BiscuitOS_list);
list_add(&node6.list, &BiscuitOS_list);
/* Traverser all node on bindirect-list */
list_for_each_entry(np, &BiscuitOS_list, list)
printk("%s\n", np->name);
return 0;
}
device_initcall(bindirect_demo_init);驱动中，创建了一个私有数据结构 struct node, 该结构中内嵌了一个双链表 struct list_head 实例，接着创建了一个双链表的表头 BiscuitOS_list, 以及初始化了 7 个 struct node 实例。 最后调用 list_add() 函数将私有 node 实例添加到双链表中，并使用 list_for_each_entry() 函数遍历所有的节点。
编写好驱动之后，进行驱动的安装。驱动的安装很简单，首先将驱动放到源码的 drivers/BiscuitOS/ 目录下，命名为 list.c，然后修改 Kconfig 文件，添加内容参考如下：
diff --git a/drivers/BiscuitOS/Kconfig b/drivers/BiscuitOS/Kconfig
index 4edc5a5..1a9abee 100644
--- a/drivers/BiscuitOS/Kconfig
+++ b/drivers/BiscuitOS/Kconfig
@@ -6,4 +6,14 @@ if BISCUITOS_DRV
config BISCUITOS_MISC
bool "BiscuitOS misc driver"
+config BISCUITOS_LIST
+ bool "Bindirect-list"
+
+if BISCUITOS_LIST
+
+config DEBUG_BISCUITOS_LIST
+ bool "list mini practice"
+
+endif # BISCUITOS_LIST
+
endif # BISCUITOS_DRV接着修改 Makefile，请参考如下修改：
diff --git a/drivers/BiscuitOS/Makefile b/drivers/BiscuitOS/Makefile
index 82004c9..9909149 100644
--- a/drivers/BiscuitOS/Makefile
+++ b/drivers/BiscuitOS/Makefile
@@ -1 +1,2 @@
obj-$(CONFIG_BISCUITOS_MISC) += BiscuitOS_drv.o
+obj-$(CONFIG_BISCUITOS_LIST) += list.o
--安装完驱动之后，进行驱动配置，以此将驱动编译进内核。驱动配置请参考下面文章中关于驱动配置一节。 在配置中，勾选如下选项，如下：
Device Driver--->
[*]BiscuitOS Driver--->
[*]Bindirect-list
[*]list mini practice具体过程请参考：
配置完驱动之后，进行驱动编译。驱动编译也请参考下面文章关于驱动编译一节：
驱动编译完之后就是驱动运行。驱动的运行，请参考下面文章中关于驱动运行一节：
启动内核，并打印如下信息：
usbcore: registered new interface driver usbhid
usbhid: USB HID core driver
BiscuitOS_node6
BiscuitOS_node5
BiscuitOS_node4
BiscuitOS_node3
BiscuitOS_node2
BiscuitOS_node1
BiscuitOS_node0
aaci-pl041 10004000.aaci: ARM AC'97 Interface PL041 rev0 at 0x10004000, irq 24
aaci-pl041 10004000.aaci: FIFO 512 entries通过上面的步骤，就可以完成内核双链表的最小实践。在实践中，创建一个
内核双链表基本操作
Linux 内核为双链表提供了丰富的接口函数，以满足不同的使用需求。双链表的操作基本分为以下几类：
双链表表头相关操作
在使用双链表之前，内核需要建立一个双链表表头，内核提供了多种接口用于表头的声明、定义，以及 初始化，具体接口如下：
双链表状态检查操作
在使用双链表过程中，需要获得双链表的状态信息，内核提供了很多接口用于获得双链表的状态信息， 具体接口如下：
双链表的节点增加操作
内核提供一系列的接口用于向双链表中添加节点，具体接口如下：
双链表的节点删除操作
内核提供了一系列接口用于从双链表中删除节点，具体接口如下：
双链表的节点修改操作
内核提供了链表节点的修改操作，包括移动链表中的节点，替换节点等操作，具体如下：
双链表的合并操作
内核也提供了链表合并操作，具体接口如下：
双链表的遍历操作
内核提供了多种方式的遍历链表的接口，(嵌套节点的数据结构称为入口)具体如下：
内核双链表进阶研究
list_for_each_entry_continue_reverse
list_for_each_entry_from_reverse
list_for_each_entry_safe_continue
附录
赞赏一下吧 🙂
