嵌入式学习-驱动开发前奏-lesson3-linux内核链表

2024-05-27 09:48

本文主要是介绍嵌入式学习-驱动开发前奏-lesson3-linux内核链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1)链表简介

链表是一种常用的数据结构,它通过指针将一系列数据节点连接成一条数据链。相对于数组,链表具有更好的动态性,建立链表时无需预先知道数据总量,可以随机分配空间,可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。

2)链表的分类和组成

链表的最基本组成元素,节点每一个节点都是由数据域和指针域组成。
根据其不同,可以将链表分为单向链表、双向链表、双向循环链表。

注意:linux内核链表属于双向循环链表。

3)链表对比

传统链表与Linux内核链表有一定的区别。
传统链表,指针域的指针是指向节点的开始
而内核链表,并没有指向节点的开始,而是指向指针域,至于再指向指针域后,如何获取数据域的数据,在后面的list_entry函数中会有详细的说明。

4)linux内核链表结构

如下:

struct list_head
{struct list_head *next, *prev;
};

list_head结构包含两个指向list_head结构的指针prev和next,由此可见,内核的链表具备双链表功能,实际上,通常它都组织成双向循环链表。

以下是内核链表中相关的函数:
- INIT_LIST_HEAD:创建链表
- list_add:在链表头插入节点
- list_add_tail:在链表尾插入节点
- list_del:删除节点
- list_entry:取出节点(访问节点里面的内容)
- list_for_each:遍历链表
理解:以上所有的函数需要内核的支持,已经在内核中定义好了

  • 1.INIT_LIST_HEAD
static inline void INIT_LIST_HEAD(struct list_head *list)
{list->next = list;list->prev = list;
}

让其前向指针和后项指针都指向自己,这样就创建了一个空的链表

-2. list_add

在链表头插入节点,其函数原型为:

/*** list_add - add a new entry* @new: new entry to be added* @head: list head to add it after** Insert a new entry after the specified head.* This is good for implementing stacks.*/
static inline void list_add(struct list_head *new, struct list_head *head)
{__list_add(new, head, head->next);
}

上面struct list_head *new 为要加进链表的数据结构,struct list_head *head为链表头,
这个函数的作用就是在链表头和链表头的下一个数据结构之间插入一个新的链表。
__list_add函数的原型为:

/** Insert a new entry between two known consecutive entries.** This is only for internal list manipulation where we know* the prev/next entries already!*/
#ifndef CONFIG_DEBUG_LIST
static inline void __list_add(struct list_head *new,struct list_head *prev, struct list_head *next)
{next->prev = new;new->next = next;new->prev = prev;prev->next = new;
}
#else

将上面的每一步画成图,如下所示:
这里写图片描述

  • 3.list_add_tail

在链表尾插入节点,其原型如下所示:

/*** list_add_tail - add a new entry* @new: new entry to be added* @head: list head to add it before** Insert a new entry before the specified head.* This is useful for implementing queues.*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{__list_add(new, head->prev, head);
}

和上面的list_add函数有些类似,同样是再次调用__list_add函数,但是参数的顺序不同,在结点指针head所指向结点的前面插入new所指向的结点。当head指向头节点时,也相当于在尾结点后面增加一个new所指向的结点

  • 4.list_del

删除节点,其原型如下:(注意:不同的cpu,其内核代码可能有所不同)

/*** list_del - deletes entry from list.* @entry: the element to delete from the list.* Note: list_empty() on entry does not return true after this, the entry is* in an undefined state.*/
#ifndef CONFIG_DEBUG_LIST
static inline void list_del(struct list_head *entry)
{__list_del(entry->prev, entry->next);entry->next = (void *)0xDEADBEEF;entry->prev = (void *)0xBEEFDEAD;
}
#else

__list_del的原型为:

/** Delete a list entry by making the prev/next entries* point to each other.** This is only for internal list manipulation where we know* the prev/next entries already!*/
static inline void __list_del(struct list_head *prev, struct list_head *next)
{next->prev = prev;prev->next = next;
}

画图如下:
这里写图片描述

  • 5list_entry

取出节点里面的内容

/*** list_entry - get the struct for this entry* @ptr:    the &struct list_head pointer.* @type:   the type of the struct this is embedded in.* @member: the name of the list_struct within the struct.*/
#define list_entry(ptr, type, member) \container_of(ptr, type, member)#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
/*** container_of - cast a member of a structure out to the containing structure* @ptr:    the pointer to the member.* @type:   the type of the container struct this is embedded in.* @member: the name of the member within the struct.*  */
#define container_of(ptr, type, member) ({          \const typeof(((type *)0)->member)*__mptr = (ptr);    \(type *)((char *)__mptr - offsetof(type, member)); })
  • 6list_for_each

遍历链表其源代码为:

/*** list_for_each    -   iterate over a list* @pos:    the &struct list_head to use as a loop cursor.* @head:   the head for your list.*/
#define list_for_each(pos, head) \for (pos = (head)->next; prefetch(pos->next), pos != (head); \pos = pos->next)

4)内核链表编程实验

mylist.c

#include<linux/module.h>
#include<linux/init.h>
#include<linux/list.h>struct score
{int num;int english;int math;struct list_head list; /*节点*/
};struct list_head score_head; /*链表头*/
struct score stu1,stu2,stu3;
struct list_head *pos; //指针 相当于光标
struct score *tmp;int mylist_init()
{/*创建链表*/INIT_LIST_HEAD(&score_head);stu1.num = 1;stu1.english = 90;stu1.math = 98;list_add_tail(&(stu1.list),&score_head); /*在链表尾插入节点*/stu2.num = 2;stu2.english = 92;stu2.math = 91;list_add_tail(&(stu2.list),&score_head);stu3.num = 3;stu3.english = 94;stu3.math = 95;list_add_tail(&(stu3.list),&score_head);/*遍历链表*/list_for_each(pos,&score_head){tmp = list_entry(pos,struct score,list);/*取出节点*/printk(KERN_WARNING"NO %d, english is %d, math is %d\n",tmp->num,tmp->english,tmp->math);   }return 0;   
}void mylist_exit()
{/*删除节点*/list_del(&(stu1.list));list_del(&(stu2.list));
}module_init(mylist_init);
module_exit(mylist_exit);
MODULE_LICENSE("GPL");

根据上面的程序,将其编译,运行,便可以看到结果,这里就不再贴图了。

菜鸟一枚,如有错误,多多指教。。。

这篇关于嵌入式学习-驱动开发前奏-lesson3-linux内核链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1007135

相关文章

Linux samba共享慢的原因及解决方案

《Linuxsamba共享慢的原因及解决方案》:本文主要介绍Linuxsamba共享慢的原因及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux samba共享慢原因及解决问题表现原因解决办法总结Linandroidux samba共享慢原因及解决

新特性抢先看! Ubuntu 25.04 Beta 发布:Linux 6.14 内核

《新特性抢先看!Ubuntu25.04Beta发布:Linux6.14内核》Canonical公司近日发布了Ubuntu25.04Beta版,这一版本被赋予了一个活泼的代号——“Plu... Canonical 昨日(3 月 27 日)放出了 Beta 版 Ubuntu 25.04 系统镜像,代号“Pluc

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

Linux安装MySQL的教程

《Linux安装MySQL的教程》:本文主要介绍Linux安装MySQL的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux安装mysql1.Mysql官网2.我的存放路径3.解压mysql文件到当前目录4.重命名一下5.创建mysql用户组和用户并修

Linux上设置Ollama服务配置(常用环境变量)

《Linux上设置Ollama服务配置(常用环境变量)》本文主要介绍了Linux上设置Ollama服务配置(常用环境变量),Ollama提供了多种环境变量供配置,如调试模式、模型目录等,下面就来介绍一... 目录在 linux 上设置环境变量配置 OllamPOgxSRJfa手动安装安装特定版本查看日志在

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》:本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用

Linux系统之dns域名解析全过程

《Linux系统之dns域名解析全过程》:本文主要介绍Linux系统之dns域名解析全过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、dns域名解析介绍1、DNS核心概念1.1 区域 zone1.2 记录 record二、DNS服务的配置1、正向解析的配置

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Linux修改pip临时目录方法的详解

《Linux修改pip临时目录方法的详解》在Linux系统中,pip在安装Python包时会使用临时目录(TMPDIR),但默认的临时目录可能会受到存储空间不足或权限问题的影响,所以本文将详细介绍如何... 目录引言一、为什么要修改 pip 的临时目录?1. 解决存储空间不足的问题2. 解决权限问题3. 提