未加星标

Linux 内核源码:list 链表

字体大小 | |
[系统(linux) 所属分类 系统(linux) | 发布者 店小二05 | 时间 2018 | 作者 红领巾 ] 0人收藏点击收藏
女主宣言

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

PS:丰富的一线技术、多元化的表现形式,尽在“ HULK一线技术杂谈 ”,点关注哦!

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

本篇要介绍的内容:

list的定义

list提供的操作方法

注意事项

使用实例

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

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

4

注意事项

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

5

使用实例
Linux 内核源码:list 链表

HULK一线技术杂谈

由360云平台团队打造的技术分享公众号,内容涉及 云计算 、 数据库 、 大数据 、 监控 、 泛前端 、 自动化测试 等众多技术领域,通过夯实的技术积累和丰富的一线实战经验,为你带来最有料的技术分享


Linux 内核源码:list 链表

本文系统(linux)相关术语:linux系统 鸟哥的linux私房菜 linux命令大全 linux操作系统

tags: list,head,定义,插入,链表,元素,linux,指针,操作,List,entry,数据结构,队列,列表,struct
分页:12
转载请注明
本文标题:Linux 内核源码:list 链表
本站链接:https://www.codesec.net/view/597112.html


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 系统(linux) | 评论(0) | 阅读(25)