linux 内核源码 -- list 链表

阅读数:194 2019 年 11 月 20 日 16:38

linux内核源码 -- list链表

linux kernel 里的很多数据结构都很经典, list 链表就是其中之一, 本文将从以下几方面介绍 list 链表:list 的定义、list 提供的操作方法、注意事项、使用实例

前言

linux kernel 里的很多数据结构都很经典, list 链表就是其中之一

本篇要介绍的内容:

1.list 的定义
2.list 提供的操作方法
3. 注意事项
4. 使用实例

list 链表

1 List 所在文件

List 的所有操作可以在 include/linux/list.h 找到 ;
List head 的定义可以在 include/linux/types.h 找到 ;

2 定义

实际上这就是一个双向循环链表, 且有一个头指针

list head 的定义:

linux内核源码 -- list链表

这个定义中只有前向和后向指针, 没任何的数据部分, 那我们基本上就知道了, 它不是被单独使用的, 而是把它嵌入到用户定义的 struct 中, 将用户定义的数据结构串起来, 作成 list;

思想很巧妙, 对用户定义的数据结构侵入性很小, 实现了 c++ 中 std::List 模板的功能 ;

虽然这个定义是叫 head, 但其实嵌入到用户定义的数据结构中的也是这个.

3 list 提供的操作方法

初始化

linux内核源码 -- list链表

插入操作

将一个元素插入到两个元素之间, 即将 new 插入到 prev 和 next 中, 这个函数是下面在头部和尾部插入的实现基础

linux内核源码 -- list链表

在头部插入, 在头指针和第一个元素间插入

linux内核源码 -- list链表

在尾部插入, 在最后一个元素间和头指针间插入, 因为是循环链表嘛~

linux内核源码 -- list链表

删除操作

删除两个元素之间的元素

linux内核源码 -- list链表

删除一个已知元素 entry

linux内核源码 -- list链表

替换操作

都是指针的变换

linux内核源码 -- list链表

移动操作

将一个元素移动到另一个 list 的头部

linux内核源码 -- list链表

将一个元素移动到另一个 list 的队尾

linux内核源码 -- list链表

拆分操作

将一个队列由指定的位置拆成两个队列

list 是新队列的 head 指针, 包括的元素从原 head 队列的第一个元素到 entry, head 队列仅包括余下的元素

linux内核源码 -- list链表

合并操作

将 list 列表中除了 list 本身插入到 prev 和 next 之间

linux内核源码 -- list链表

将一个列表插入到另一个列表的头部

linux内核源码 -- list链表

将一个列表插入到另一个列表的尾部

linux内核源码 -- list链表

list_entry 宏

按之前说的, 这个 list_head 都有要嵌入到用户定义的 struct 中, 这个宏就是由这个 list_head ptr 来获取当前所处的 struct 对象的指针, 用了 linux 的经典宏定义 container_of

linux内核源码 -- list链表

一堆宏定义, 用来各种遍历, 获取 entry

4 注意事项

只说一个, 就是多线程操作同一个 list, 还是需要加锁

5 使用实例

linux内核源码 -- list链表

本文转载自公众号 360 云计算(ID:hulktalk)。

原文链接:

https://mp.weixin.qq.com/s/yFbCE3qu7IEKeAhpEoiUPw

评论

发布