Linux教程

linux内核源码 -- list链表

本文主要是介绍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的定义:

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

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

 

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

 

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

3

list提供的操作方法

初始化

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

插入操作

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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

删除操作 

删除两个元素之间的元素

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

删除一个已知元素entry

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

替换操作

都是指针的变换

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

移动操作

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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

拆分操作

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

 

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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

合并操作

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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

list_entry宏

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

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

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

4

注意事项

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

5

使用实例

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 

这篇关于linux内核源码 -- list链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!