当前位置: 首页 > news >正文

Linux 内核学习笔记: hlist 的理解

前言

  • 最近阅读 Linux 内核时,遇到了 hlist,这个 hlist 用起来像是普通的链表,但是为何使用 hlist,hlist 是怎么工作的?

在这里插入图片描述

  • 相关代码 hlist_add_head(&clk->clks_node, &core->clks);
/*** clk_core_link_consumer - Add a clk consumer to the list of consumers in a clk_core* @core: clk to add consumer to* @clk: consumer to link to a clk*/
static void clk_core_link_consumer(struct clk_core *core, struct clk *clk)
{clk_prepare_lock();hlist_add_head(&clk->clks_node, &core->clks);clk_prepare_unlock();
}
  • 越来越感到 Linux 内核真的是一个宝藏库,学习软件开发,阅读 Linux 内核代码,会受益匪浅。

hlist 定义

  • hlist 结构体定义所在的文件 `include\linux\types.h
struct hlist_head {struct hlist_node *first;
};struct hlist_node {struct hlist_node *next, **pprev;
};
  • 有的人理解 hlist 是 hash list 的简写,也就是 哈希链表,我不敢苟同,但 hlist 用在哈希桶上时,会由于 struct hlist_head 只有一个指针,比普通的 struct list_head 节省空间

  • 哈希表,由于哈希碰撞,即使哈希桶再大,都有可能多个数据拥有同一个哈希值,此时引入了链表,哈希值相同的元素,挂在链表上,此时由于 哈希桶的数量极大,比如 100万个,使用 struct hlist_head 会比 struct list_head 节省很大的【内存空间】

  • 由于 struct hlist_head 特殊的结构,造成 struct hlist_head 不能成为 【双向循环】链表,但是由于 struct hlist_node 有两个指针,因此可以享受 链表节点快速【插入】与【删除】的有点,这部分有点像 普通链表 struct list_head

  • struct hlist_head 只用于定义 链表的头部,链表的节点使用 struct hlist_node 定义。

  • 【重点理解】 struct hlist_node 中的 pprev 是二级指针,用于指向前一个 节点的 next,也就是前一个节点成员 next 指针的指针。这里不是 pprev = prev->next,而是 pprev= &prev->next ,一定要理解清楚,否则 pprev = prev->next 就是自身指针了,因为上一个节点的 next 就是指向下一个节点,这样获取不到上一个节点的指针。

hlist 的定义与初始化

  • 可以通过阅读 Linux 经典链表操作头文件 include\linux\list.h ,详细了解 链表的操作,比如 定义、 初始化、插入、删除、遍历等操作。

  • 如果链表嵌入在一个较大的数据结构中,双向链表的各个节点一般都是采用经典的前驱与后继相连,而通过链表成员,获取结构体的指针(地址),可以使用 container_of,比如 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)

在这里插入图片描述

  • 初始化与定义,可以直接查看 include\linux\list.h ,一般定义方法为

  • 定义 hlist 头部 struct hlist_head children;

  • 定义 hlist 节点 struct hlist_node clks_node;

  • hlist head 定义后需要初始化,可以定义时初始化,也可以手动初始化

  • 定义并初始化 static HLIST_HEAD(clk_root_list);

  • 手动在初始化函数中初始化 INIT_HLIST_HEAD(&core->clks);

hlist 插入操作

  • 由于 hlist 特殊的结构,造成 hlist 插入操作分为两种: 头部的插入 hlist_add_head ,节点的插入 hlist_add_before hlist_add_behind 两种

  • hlist_add_head 操作: 知道 hlist 头部,插入到头部后面,新插入的节点,成为第一个hlist 节点

在这里插入图片描述

  • hlist_add_before ,两个 hlist_node 节点,前面插入节点

在这里插入图片描述

  • hlist_add_behind 两个 hlist_node 节点,插入到后面,类似于 after

在这里插入图片描述

删除节点 __hlist_del

  • 由于 hlist node 节点是双向的,双重指针 pprev 可以获取到前一个节点,而 next 可以获取到后一个节点,因此像常规双向链表一样,删除操作不依赖 链表头部

在这里插入图片描述

小结

  • 深入熟悉 hlist 的操作,感觉 Linux 代码阅读起来,更熟悉了,后面抽时间自己写驱动时用起来。

  • hlist 设计很巧妙,但使用起来由于区分 链表头与链表节点,没有 list_head 操作那么简单,但是用于哈希桶结构,可以用于节省空间(链表头部节点多、链表节点少的场合)

相关文章:

Linux 内核学习笔记: hlist 的理解

前言 最近阅读 Linux 内核时,遇到了 hlist,这个 hlist 用起来像是普通的链表,但是为何使用 hlist,hlist 是怎么工作的? 相关代码 hlist_add_head(&clk->clks_node, &core->clks); /*** clk_core_link_…...

几种设计模式介绍

前言 设计模式是一种用于解决软件开发中常见问题的通用解决方案,它可以提高代码的可读性、可维护性和可复用性。前端开发中也有很多应用设计模式的场景,比如处理异步操作、优化性能、封装复杂逻辑等。 前端开发中常见的设计模式有以下几种: …...

拓展操作(三) jenkins迁移到另一个机器

让清单成为一种习惯 互联网时代的变革,不再是简单的开发部署上线,持续,正确,安全地把事情做好尤其重要;把事情做好的前提是做一个可量化可执行的清单,让工程师就可以操作的清单而不是专家才能操作: 设定检查点 根据节点执行检查程序操作确认或边读边做 二者选其一不要太…...

重定向和转发的区别

重定向 1、定义 用户通过浏览器发送一个请求,Tomcat服务器接收这个请求,会给浏览器发送一个状态码302,并设置一个重定向的路径,浏览器如果接收到了这个302的状态码以后,就会去自动加载服务器设置的路径 一个页面跳转…...

基于ElementUI二次封装弹窗组件

效果&#xff1a; 一、自定义内容类型弹窗 <!-- title&#xff1a;对话框的标题confirmLoading&#xff1a;当前是否处于提交中titleCenter&#xff1a;对话框标题居中方式footerCenter&#xff1a;底部按钮的对其方式visible&#xff1a;是否显示弹窗width&#xff1a;设置…...

linux cat命令改变功能显示当前文件行号

linux的cat命令使用-n显示多个文件行号时&#xff0c;行号是累加的&#xff0c;不是到了新文件就重新计数。这样满足不了我的需求。如果到了新文件能够重新计数&#xff0c;就能使用-nf&#xff08;在上一篇-f显示文件名功能的基础上&#xff09;加| grep xxx&#xff0c;既能直…...

Django-REST-Framework 如何快速生成Swagger, ReDoc格式的 REST API 文档

1、API 接口文档的几种规范格式 前后端分离项目中&#xff0c;使用规范、便捷的API接口文档工具&#xff0c;可以有效提高团队工作效率。 标准化的API文档的益处&#xff1a; 允许开发人员以交互式的方式查看、测试API接口&#xff0c;以方便使用将所有可暴露的API接口进行分…...

SpringBoot当中的Singleton和Prototype详解

在Spring Boot中&#xff0c;Singleton和Prototype是两种Bean的作用域。这两种作用域决定了Spring容器如何创建和管理Bean的实例。 Singleton&#xff08;单例&#xff09;&#xff1a; 当一个Bean被配置为Singleton作用域时&#xff0c;Spring容器在启动时只会创建该Bean的一个…...

LeetCode第1题 - 两数之和

题目 给定一个整数数组 nums 和一个目标值 target&#xff0c;请你在该数组中找出和为目标值的那 两个 整数&#xff0c;并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是&#xff0c;你不能重复利用这个数组中同样的元素。 示例 给定 nums [2, 7, 11, 15], …...

(14)Linux 地址空间的理解

前言&#xff1a;本章核心主题为 "进程地址空间"。 一、Linux 进程地址空间 程序地址空间是内存吗&#xff1f;不是&#xff01;程序地址空间不是内存&#xff01; 其实&#xff0c;我们称之为程序地址空间都不准确&#xff0c;应该叫 进程地址空间&#xff0c;这…...

Java中的设计模式

设计模式是软件开发中常见问题的可重用解决方案。在Java中&#xff0c;设计模式有助于提高代码的可维护性、可读性和可扩展性。以下是一篇关于Java中设计模式的文章&#xff0c;以帮助您更好地理解这些模式。 一、设计模式简介 设计模式是经过验证的解决方案&#xff0c;用于…...

Hadoop(2):常见的MapReduce[在Ubuntu中运行!]

1 以词频统计为例子介绍 mapreduce怎么写出来的 弄清楚MapReduce的各个过程&#xff1a; 将文件输入后&#xff0c;返回的<k1,v1>代表的含义是&#xff1a;k1表示偏移量&#xff0c;即v1的第一个字母在文件中的索引&#xff08;从0开始数的&#xff09;&#xff1b;v1表…...

Unity | 快速修复Animation missing错误

目录 一、背景 二、效果 三、解决办法 一、背景 最近在做2D 骨骼动画相关的Demo&#xff0c;我自己使用Unity引擎进行骨骼绑定并创建了anim后&#xff0c;一切正常&#xff0c;anim也能播放。但是昨天我修改Obj及子物体的名称&#xff08;由中文改为英文&#xff0c;如&…...

ssm基于web的志愿者管理系统的设计与实现+vue论文

摘 要 使用旧方法对志愿者管理系统的信息进行系统化管理已经不再让人们信赖了&#xff0c;把现在的网络信息技术运用在志愿者管理系统的管理上面可以解决许多信息管理上面的难题&#xff0c;比如处理数据时间很长&#xff0c;数据存在错误不能及时纠正等问题。这次开发的志愿者…...

C++运算符重载(插入and提取)

介绍 本文主要介绍 插入(>>) and 提取(<<)的运算符重载 1.插入(>>) 提取(<<)只能是友元函数 2.插入关键词istream 例子&#xff1a;istream& operator>>(istream& in, sumber&Left) 3.提取关键词ostream 例子&#xff1a;ostream&a…...

C#高级 08Json操作

1.概念 Json是存储和交换文本信息的语法。类似于XML。Json比XML更小、更快、更易解析。Json与XML一样是一种数据格式。Json是一种轻量级的数据交换格式。它基于ECMAScript的一个子集。Json采取完全独立于语言的文本格式&#xff0c; 但是也使用了类似于C语言的习惯。这些特性使…...

封装uniapp签字板

新开发的业务涉及到签字功能&#xff0c;由于是动态的表单&#xff0c;无法确定它会出现在哪里&#xff0c;不得已封装模块。 其中涉及到一个难点就是this的指向性问题&#xff0c; 第二个是微信小程序写法&#xff0c; 我这个写法里用了u-view的写法&#xff0c;可以自己修改组…...

Mybatis行为配置之Ⅳ—日志

专栏精选 引入Mybatis Mybatis的快速入门 Mybatis的增删改查扩展功能说明 mapper映射的参数和结果 Mybatis复杂类型的结果映射 Mybatis基于注解的结果映射 Mybatis枚举类型处理和类型处理器 再谈动态SQL Mybatis配置入门 Mybatis行为配置之Ⅰ—缓存 Mybatis行为配置…...

Java设计模式-外观模式

目录 一、影院管理项目 二、外观模式 &#xff08;一&#xff09;基本介绍 &#xff08;二&#xff09;原理类图 &#xff08;三&#xff09;解决影院管理 &#xff08;四&#xff09;注意事项和细节 &#xff08;五&#xff09;外观模式在MyBatis框架应用的源码分析 一…...

js+css实现颜色选择器

<!DOCTYPE html> <html> <head><meta charset"UTF-8"><title>颜色选择器</title><style>.color-box {width: 50px;height: 50px;border: 1px solid #000;cursor: pointer;}</style> </head> <body><…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”

案例&#xff1a; 某医药分销企业&#xff0c;主要经营各类药品的批发与零售。由于药品的特殊性&#xff0c;效期管理至关重要&#xff0c;但该企业一直面临效期问题的困扰。在未使用WMS系统之前&#xff0c;其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...