Linux 设备驱动系列 (16) —— 链表 Linked List
![Linux设备驱动系列(16) —— 链表Linked List](https://static001.geekbang.org/infoq/54/5432dd9d3831c9366f45f3d9c52da79f.png)
关注微信公众号:Linux 内核拾遗
链表是一种数据结构,由一系列节点组成,每个节点包含数据部分和指向下一个节点的指针。链表可以动态增长或缩小,适合频繁插入和删除操作。常见的类型有单向链表、双向链表和循环链表。虽然访问速度较慢,但灵活性和操作效率使其在许多应用中非常有用。
本文将介绍 Linux 内核中提供的链表数据结构。
1 Linux 中的链表
链表作为一种非常重要的数据结构,允许高效地存储和操作大量数据,在内核代码中链表的使用随处可见。
在 Linux 内核中,开发者无需自己实现链表或使用第三方库,内核内置了双向链表的实现struct list_head
,定义在 linux/list.h 头文件中。
2 Linux 链表使用
下面将详细介绍 Linux 内核链表的常用接口和使用方式。
2.1 链表头初始化
Linux 内核链表用链表头 list_head 来表示,因此链表的初始化其实就是初始化一个链表头。
LIST_HEAD 宏将创建一个名为 linked_list 的链表,它是一个双向链表,即在没有插入任何节点之前,它的首尾指针都指向自身(也可以认为首尾指针指向自身时表示链表是空的)。
LIST_HEAD 的内部实现如下:
因此上面的初始化展开后是下面这个样子:
2.2 创建链表节点
Linux 内核的链表节点也使用struct list_head
来表示,它通常内嵌在自定义的数据结构中:
链表节点在插入链表之前也需要进行初始化,使用 INIT_LIST_HEAD 宏,例如:
2.3 添加节点到链表中
链表节点初始化完成后,就可以往链表中添加节点:
其中 head 表示链表头,new 是要添加的节点。list_add 将 new 添加到链表头部,而 list_add_tail 添加到链表尾部。
2.4 从链表中删除节点
从链表中删除节点实际上就是修改了一下节点及其相邻节点的 prev 和 next 指针指向,它不会释放节点的内存:
其中 list_del_init 在删除节点后还对该节点重新进行初始化操作。
2.5 从链表中替换节点
和删除节点同理,替换节点也只是修改了 prev 和 next 指针指向,并且 list_replace_init 还会对替换出来的节点(old)进行重新初始化操作:
2.6 移动链表中的节点
下面的函数中,list 表示要移动的节点,list_move 将其移动到链表首部,list_move_tail 将其移动到链表尾部:
2.7 旋转链表节点
list_rotate_left
是 Linux 内核中用于双向链表操作的一个函数,它用于将链表的第一个节点移动到最后一个位置。这个操作可以看作是将链表左旋一次。
2.8 检查链表
Linux 内核还提供了检查链表的相关函数,例如:
list_is_last:检查节点是否是链表最后一个节点。
list_empty:链表是否为空。
list_is_singular:链表是否只有一个节点。
2.9 链表分割
list_cut_position 函数用于将一个双向链表从指定位置剪切出来,形成一个新的链表段,其中:
list 是新链表头指针。
head 是原链表头指针。
entry 指向原链表中某个节点的指针,从这个节点开始分割链表。
2.10 链表连接
list_splice
是 Linux 内核中用于将一个链表合并到另一个链表中的函数。它可以将整个链表 list
插入到 head
链表中,或者更具体地,将list
链表插入到head
链表首部。
2.11 链表遍历
Linux 内核提供了一系列的函数来遍历和操作链表中的元素:
list_entry(ptr, type, member):通过链表节点的指针获取包含该节点的结构体指针。
list_for_each(pos, head):遍历链表中的每个节点。
list_for_each_entry(pos, head, member):遍历链表中的每个结构体实例。
list_for_each_entry_safe ( pos, n, head, member):安全地遍历链表中的每个结构体实例,可以在遍历过程中安全地删除节点。
list_for_each_prev(pos, head):逆向遍历链表中的每个节点。
list_for_each_entry_reverse(pos, head, member):逆向遍历链表中的每个结构体实例。
3 Linux 链表代码演示
kernel_driver.c
代码编译运行,运行结果如下:
![](https://static001.geekbang.org/infoq/7d/7d8274f1bad84fb69a97692d2c75bd99.png)
![](https://static001.geekbang.org/infoq/d3/d3cff5fa2cc692f5f72ca8549b60c9d7.png)
关注微信公众号:Linux 内核拾遗
版权声明: 本文为 InfoQ 作者【Linux内核拾遗】的原创文章。
原文链接:【http://xie.infoq.cn/article/8b82fe1e4ab66a8c8ce7012c3】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论