专栏首页嵌入式开发圈Linux内核链表的使用

Linux内核链表的使用

/********************

* 内核中链表的应用

********************/

(1)介绍

在Linux内核中使用了大量的链表结构来组织数据,包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在include/linux/list.h实现的一个相当精彩的链表数据结构。

链表数据结构的定义很简单:

struct list_head {

struct list_head *next, *prev;

};

list_head结构包含两个指向list_head结构的指针prev和next,内核的数据结构通常组织成双循环链表。

和以前介绍的双链表结构模型不同,这里的list_head没有数据域。在Linux内核链表中,不是在链表结构中包含数据,而是在数据结构中包含链表节点。

如:

struct my_struct{

struct list_head list;

unsigned long dog;

void *cat;

};

linux中的链表没有固定的表头,从任何元素开始访问都可以。遍历链表仅仅需要从某个节点开始,沿指针访问下一个节点,直到又重新回到最初这个节点就可以了。每个独立的节点都可以被称作是链表头。

(2)链表的初始化

a.静态

如果在编译时静态创建链表,并且直接引用它,如下:

struct my_struct mine={

.lost = LIST_HEAD_INIT(mine.list);

.dog = 0,

.cat = NULL

};

static LIST_HEAD(fox);

/*等于struct list_head fox = LIST_HEAD_INIT(fox); */

b.动态

struct my_struct *p;

p = kmalloc(GFP_KERNEL, sizeof(my_struct));

p->dog = 0;

p->cat = NULL;

INIT_LIST_HEAD(&p->list);

(3)操作链表

内核提供了一组函数来操作链表。

注意!这些函数都使用一个或多个list_head结构体指针作参数。定义在<linux/list.h>

a.增加节点

list_add(struct list_head *new,

struct list_head *head);

向指定链表的head节点后面插入new节点

b.把节点增加到链表尾

list_add_tail(struct list_head *new,

struct list_head *head);

向指定链表的head节点前面插入new节点

c.从链表删除一个节点

list_del(struct list_head *entry);

将entry从链表中移走

d.把节点从一个链表移到另一个链表

list_move(struct list_head *list,

struct list_head *head);

从一个链表中摘除list项,然后将其插入head的后面

e.list_empty(struct list_head *head);

链表为空返回非0值,否则返回0

f.合并链表

list_splice(struct list_head *list,

struct list_head *head);

注意!新的链表不包括list节点

(4)遍历链表

链表本身不重要,访问到那个包含链表的结构体才重要

a.从链表指针获得包含该链表的结构体的指针

list_entry(struct list_head *ptr,

type_of_struct,

field_name);

ptr: list_head指针

type_of_struct: 包含ptr的结构体类型

field_name: 结构体中链表字段的名字

如:

my_struct *p = (list_head *ptr, my_struct, list);

b.遍历链表

list_for_each(struct list_head *cursor,

struct list_head *list);

常常和list_entry配套使用

注意!用list_for_each遍历时,不包括头节点

c.遍历的同时获得大结构体指针

list_for_each_entry(type *cursor,

struct list_head *list,

member);

d.遍历链表的同时释放每个被遍历到的节点

list_for_each_entry_safe(type *cursor,

type *tmp;

struct list_head *list,

member);

本文分享自微信公众号 - 嵌入式开发圈(gh_d6ff851b4069),作者:杨源鑫

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于小熊派SD卡+Fatfs+移植开源iniparse解析库并使用

    等等其它关键的参数,最常用的存储方法是基于xxx.ini的文件形式来进行存储,ini文件是什么在以往的文章中也有相应的介绍。

    morixinguan
  • Keil MDK的一些推荐功能(编码格式、自动保存、代码提示、动态语法检查、多核编译)

    一直在用Keil MDK开发,很多时候并没有仔细去研究它强大的功能,最近在做一些开源项目的同时也在想办法提高自己的工作效率,所谓时间就是金钱,看到世伟兄分享的这...

    morixinguan
  • 一些不可不知的计算机网络基础

    其中,OSI的七层协议体系结构理论虽然完整,但它既复杂又不实用。广泛应用的是TCP/IP四层体系结构。

    morixinguan
  • Linux 内核通用链表学习小结

    在linux内核中封装了一个通用的双向链表库,这个通用的链表库有很好的扩展性和封装性,它给我们提供了一个固定的指针域结构体,我们在使用的时候,只需要在我们定义的...

    砸漏
  • linux内核源码 -- list链表

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

    扫帚的影子
  • linux通用链表

    链表的主要意义就是将分散地址的数据域通过指针排列成有序的队列。因此数据域是链表不可或缺的一部分,但是在实际使用中需要不同类型的数据域,因此也就限制了链表的通用。...

    开源519
  • 3分钟学个算法:链表反转

    初拿到这题,很容易联想到反转系列用java的api中提供了几个类似的api如Collections.reverse()和StringBuilder.revers...

    艾小仙
  • C 链表 - linux 如何实现

    链表是基本数据结构, 一开始学习数据结构时, 我一般这么定义, 对应实现从头或尾插入的处理函数,

    orientlu
  • Python:列表操作命令

    示例:三个函数:min(),max()sum()分别取列表中最小值,最大值,数值总和

    py3study
  • python---爬取拉勾网

    在过几个月又是一年一度的毕业生求职时间了,这时候都需要往各个网站各个平台投递简历,这时候一份好的简历很重要,找对方向也很重要。这里我爬取了拉勾网30页关键字为...

    sjw1998

扫码关注云+社区

领取腾讯云代金券