Linux内核数据结构 散列表
1、散列表数据结构
-
在Linux内核中,散列表(哈希表)使用非常广泛。本文将对其数据结构和核心函数进行分析。和散列表相关的数据结构有两个:
hlist_head
和hlist_node
//hash桶的头结点 struct hlist_head {struct hlist_node *first;//指向每一个hash桶的第一个结点的指针 }; //hash桶的普通结点 struct hlist_node {struct hlist_node *next;//指向下一个结点的指针struct hlist_node **pprev;//指向上一个结点的next指针的地址 };
-
对应的结构如下
hash_table
为散列表(数组),其中的元素类型为struct hlist_head
。以hlist_head
为链表头的链表,其中的节点hash
值是相同的(也叫冲突)。first
指针指向链表中的节点①,然后节点①的pprev
指针指向hlist_head
中 的first
,节点①的next
指针指向节点②,以此类推。hash_table
的列表头仅存放一个指针,也就是first
指针,指向的是对应链表的头结点,没有tail指针,也就是指向链表尾节点的指针,这样的考虑是为了节省空间——尤其在hash bucket
(数组size
)很大的情况下可以节省一半的指针空间。pprev
是一个二级指针, 它指向前一个节点的next
指针的地址 。为什么我们需要这样一个指针呢?它的好处是什么?- 哈希表的目的是为了方便快速的查找,所以哈希表中
hash
桶的数量通常比较大,否则“冲突”的概率会非常大,这样也就失去了哈希表的意义。如何做到既能维护一张大表,又能不使用过多的内存呢?就只能从数据结构上下功夫了。所以对于哈希表的每个hash
桶,它的结构体中只存放一个指针,解决了占用空间的问题。现在又出现了另一个问题:数据结构不一致。显然,如果hlist_node
采用传统的next
,prev
指针,对于第一个节点和后面其他节点的处理会不一致。hlist_node
巧妙地将pprev
指向上一个节点的next
指针的地址,由于hlist_head
的first
域指向的结点类型和hlist_node
指向的下一个结点的结点类型相同,这样就解决了通用性! - 下面讲解结点相关操作的时候会有更详细的解释。
- 哈希表的目的是为了方便快速的查找,所以哈希表中
2、散列表删除结点
-
如果要删除hash桶对应链表中的第一个普通结点
对应的程序代码如下:static inline void __hlist_del(struct hlist_node *n) { struct hlist_node *next = n->next;//获取指向第二个普通结点的指针 struct hlist_node **pprev = n->pprev;//保留待删除的第一个结点的pprev域(即头结点first域的地址),此时 pprev = &first *pprev = next; /*因为pprev = &first,所以*pprev = next,相当于 first = next即将hash桶的头结点指针指向原来的第二个结点,如上图中的黑线1*/if (next) //如果第二个结点不为空next->pprev = pprev;//将第二个结点的pprev域设置为头结点first域的地址,如上图中的黑线2 }
-
如果要删除hash桶对应链表中的非第一个结点
对应的程序代码如下:static inline void __hlist_del(struct hlist_node *n) { struct hlist_node *next = n->next;//获取指向待删除结点的下一个普通结点的指针 struct hlist_node **pprev = n->pprev;//获取待删除结点的pprev域 *pprev = next; //修改待删除结点的pprev域,逻辑上使待删除结点的前驱结点指向待删除结点的后继结点,如上图中的黑线1if (next) //如果待删除结点的下一个普通结点不为空next->pprev = pprev;//设置下一个结点的pprev域,如上图中的黑线2,保持hlist的结构 }
可以看到删除第一个普通结点和删除非第一个普通结点的代码是一样的。
-
下面再来看看如果
hlist_node
中包含两个分别指向前驱结点和后继结点的指针。
很明显删除hash
桶对应链表中的非第一个普通结点,只需要如下两行代码:n->next->prev = n->prev; n->prev->next = n->next;
可是,如果是删除的
hash
桶对应链表中的第一个普通结点:此时n->prev->next = n->next
就会出问题,因为hash
桶的表头结点没有next
域,所以,明显在这种情况下删除hash
桶对应链表的第一个普通结点和非第一个普通结点的代码是不一样的。 同理结点插入操作也存在同样的问题。
相关文章:
Linux内核数据结构 散列表
1、散列表数据结构 在Linux内核中,散列表(哈希表)使用非常广泛。本文将对其数据结构和核心函数进行分析。和散列表相关的数据结构有两个:hlist_head 和 hlist_node //hash桶的头结点 struct hlist_head {struct hlist_node *first…...
数据库系统课设——基于python+pyqt5+mysql的酒店管理系统(可直接运行)--GUI编程
几个月之前写的一个项目,通过这个项目,你能学到关于数据库的触发器知识,python的基本语法,python一些第三方库的使用,包括python如何将前后端连接起来(界面和数据),还有界面的设计等…...
《C和指针》笔记9: typedef
C语言支持一种叫作typedef的机制,它允许你为各种数据类型定义新名字。typedef声明的写法和普通的声明基本相同,只是把typedef这个关键字出现在声明的前面。例如,下面这个声明: char *ptr_to_char;把变量ptr_to_char声明为一个指向…...
《C和指针》笔记6:gets/puts/scanf/printf/getchar函数用法
本博客可以了解一些gets/puts/scanf/printf/getchar函数的基本用法。 文章目录 1. gets函数2. puts函数3. scanf函数4. printf函数5. getchar函数6. putchar函数 1. gets函数 gets函数从标准输入读取一行文本并把它存储于作为参数传递给它的数组中。一行输入由一串字符组成&a…...
智慧课堂学生行为检测评估算法
智慧课堂学生行为检测评估算法通过yolov5系列图像识别和行为分析,智慧课堂学生行为检测评估算法评估学生的表情、是否交头接耳行为、课堂参与度以及互动质量,并提供相应的反馈和建议。智慧课堂学生行为检测评估算法能够实时监测学生的上课行为࿰…...
rainbond云原生应用管理平台部署
rainbond简介 rainbond 是 一个 开源的Kubernetes 云原生应用管理平台。 Rainbond 核心100%开源,Serverless体验,不需要懂K8s也能轻松管理容器化应用,平滑无缝过渡到K8s,是国内首个支持国产化信创、适合私有部署的一体化应用管理…...
jemter连接数据json断言
文章目录 一、jmeter连接数据库1、加载JDBC驱动2、连接数据3、SQL Query的Query Type使用方法:4、Variable Name使用方法:5、Result variable name使用方法: 二、Json响应断言1、添加 》 断言 》 JSON断言2、JSON断言界面参数说明:…...
JavaFX 加载 fxml 文件
JavaFX 加载 fxml 文件主要有两种方式,第一种方式通过 FXMLLoader 类直接加载 fxml 文件,简单直接,但是有些控件目前还不知道该如何获取,所以只能显示,目前无法处理。第二种方式较为复杂,但是可以使用与 fx…...
(三)Redis——Set
SADD key value SMEMBERS 127.0.0.1:6379> SADD set aaa 1 127.0.0.1:6379> SMEMBERS set aaa 127.0.0.1:6379> SADD set aaa 0 127.0.0.1:6379> SMEMBERS set aaaSISMEMBER 判断 aaa 是否在 set 中 127.0.0.1:6379> SISMEMBER set aaa 1 127.0.0.1:6379>…...
Vue组件通信方式详解(全面版)
在Vue应用开发中,组件通信是一个重要的话题。不同的组件可能需要在不同的情况下进行数据传递和交互。Vue提供了多种方式来实现组件通信,每种方式都有其适用的场景。本文将详细介绍Vue中实现组件通信的各种方式,并为每种方式提供通俗易懂的代码…...
什么是Promise对象?它的状态有哪些?如何使用Promise处理异步操作?以及 async、await
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ Promise对象⭐ 创建Promise对象⭐ 使用Promise处理异步操作⭐ async、await⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅…...
Android 之自定义绘制一
绘制的基本要素 onDraw(Canvas) 绘制方法 Canvas 绘制工具 Paint 调整风格 粗细等 坐标系: x y ,3D 会有z轴,x 左到右,y 上至下,与数学中y颠倒 尺寸单位: 布局中 dp ,sp ,代码中 px;dp 为了适配不同的尺寸 绘制的关键: draw(Canvas )......(关键类:Paint) Paint.ANTI_A…...
vue3 计算两个表单得到第三个表单数据
<el-formref"ruleFormRef"label-width"150px"label-suffix":":rules"rules":disabled"drawerProps.isView":model"drawerProps.rowData"><el-form-item label"云平台名称" prop"cloudId&…...
Premiere Pro软件安装包分享(附安装教程)
目录 一、软件简介 二、软件下载 一、软件简介 Adobe Premiere Pro,简称PR,是Adobe公司开发的一款非线性视频编辑软件,被广泛应用于电影、电视剧、广告、纪录片、独立电影和音乐会等影视制作领域。它被公认为是行业内的标准工具,…...
springboot设置文件上传大小,默认是1mb
问题排查和解决过程 之前做了个项目,需要用到文件上传,启动项目正常,正常上传图片也正常,但这里图片刚好都小于1M,在代码配置文件里面也写了配置,限制大小为500M,想着就没问题(测试…...
Unity 之transform.LookAt() 调整一个物体的旋转,使其朝向指定的位置
文章目录 总的介绍补充(用于摄像机跟随的场景) 总的介绍 transform.LookAt 是 Unity 引擎中 Transform 组件的一个方法,用于调整一个物体的旋转,使其朝向指定的位置。通常情况下,它被用来使一个物体(如摄像…...
linux————haproxy
一、概述 HAProxy是一个免费的负载均衡软件,可以运行于大部分主流的Linux操作系统上(CentOS、Ubuntu、Debian、OpenSUSE、Fedora、麒麟、欧拉、UOS)。 HAProxy提供了L4(TCP)和L7(HTTP)两种负载均衡能力,具备丰富的功能。HAProxy具…...
【80天学习完《深入理解计算机系统》】第十天 3.3 条件码寄存器【CF ZF SF OF】【set】
专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客,如有问题交流,欢迎评论区留言,一定尽快回复!(大家可以去看我的专栏,是所有文章的目录) 文章字体风格: 红色文字表示&#…...
使用WSL修改docker文件存储位置
按照以下说明将其重新定位到其他驱动器/目录,并保留所有现有的Docker数据。 首先,右键单击Docker Desktop图标关闭Docker桌面,然后选择退出Docker桌面,然后,打开命令提示符: wsl --list -v您应该能够看到&a…...
软件设计师学习笔记6-存储系统
1.层次化存储体系 1.1层次化存储结构 局部性原理是层次化存储结构的支持 时空局部性:刚被访问的内容,立即又被访问(eg: 循环体 ) 空间局部性:刚被访问的内容,临近的空间很快被访问(eg:数组) 1.2层次化存储结构的分类 DRAM&…...
【TI毫米波雷达笔记】CCS雷达工程内存RAM指定(DATA_SECTION,以IWR6843AOP为例)
【TI毫米波雷达笔记】CCS雷达工程内存RAM指定(DATA_SECTION,以IWR6843AOP为例) 工程建立好以后会有一个cmd文件 此文件描述的是内存map /*----------------------------------------------------------------------------*/ /* r4f_linker…...
安卓移动应用开发实训室建设方案
一 、系统概述 安卓移动应用开发作为新一代信息技术的重点和促进信息消费的核心产业,已成为我国转变信息服务业的发展新热点:成为信息通信领域发展最快、市场潜力最大的业务领域。互联网尤其是移动互联网,以其巨大的信息交换能力和快速渗透能…...
我的编程学习过程
自信与经验 在毕业的时候就觉得繁体字很难。大陆都在使用简体字,戴季陶说这是在亡国,没有这么严 重。繁体字会意,简体字简单,中国文盲很多,为了加快经济建设的步伐,不得不牺牲很多 东西。为了解决温饱&…...
亚马逊云科技 云技能孵化营 初识机器学习
目录 前言 一、课程介绍 二、什么是机器学习 三、机器学习算法进阶过程 四、亚马逊云科技能给我们什么 总结 前言 近期参加了“亚马逊云科技 云技能孵化营”,该孵化营的亚马逊云科技培训与认证团队为开发者准备了云从业者的精要知识及入门课程,帮助…...
多种编程语言运行速度排名-10亿次除7求余数为0的数量
最佳方式是运行10次,取平均数,用时秒数显示3位小数。 因为第一次打开,可能CPU还没优化好,多次取平均,比较准确 第1次共10次,用时3秒,平均3秒 第2次共10次,用时4秒,平均3.…...
Web 应用框架 Express 构建 RESTful API
Express框架 Express 是 Node.js 平台上最常用的 Web 应用框架之一,它简洁、灵活且易于使用。Express 提供了一组强大的功能和工具,可以帮助开发者快速构建 Web 应用程序和 RESTful API。 以下是 Express 框架的一些主要特点和功能: 轻量级…...
Orchestrator介绍一 简介安装与web端管理
目录 一 Orchestrator简介 二 Orchestrator功能 1 Discovery(发现复制拓扑) 2 Refactoring(重构复制拓扑) 3 Recovery(恢复主库故障) 三 orchestrator支持的操作方式 四 部署要求 五 下载 六 安装 1 下载软件包 2 解压软件包 3 创建账号 第一种是 orc后端MySQL数据…...
【C++心愿便利店】No.3---内联函数、auto、范围for、nullptr
文章目录 前言🌟一、内联函数🌏1.1.面试题🌏1.2.内联函数概念🌏1.3.内联函数特性 🌟二、auto关键字🌏2.1.类型别名思考🌏2.2.auto简介🌏2.3.auto的使用细节🌏2.4.auto不能…...
CV:边缘检测的算法包含 Prewitt、Sobel、Laplacian 和 Canny。
目录 1. 边缘检测(Prewitt) 2. 边缘检测(Sobel) 3. 边缘检测(Laplacian) 3. 边缘检测(Canny) 边缘检测的算法包含 Prewitt、Sobel、Laplacian 和 Canny。 人在图像识别上具有难…...
【算法系列篇】前缀和
文章目录 前言什么是前缀和算法1.【模板】前缀和1.1 题目要求1.2 做题思路1.3 Java代码实现 2. 【模板】二维前缀和2.1 题目要求2.2 做题思路2.3 Java代码实现 3. 寻找数组的中心下标3.1 题目要求3.2 做题思路3.3 Java代码实现 4. 除自身以外的数组的乘积4.1 题目要求4.2 做题思…...
若依移动端Ruoyi-App 项目的后端项目入门
后端项目运行 运行报错 Error creating bean with name sysConfigServiceImpl: Invocation of init method failed 数据库创建了。 代码连接数据库地方了也匹配上了。但是还是报错。 分析 : 想起来我电脑从来没有安装过redis 下载安装redis到windows 链接&…...
(学习笔记-调度算法)内存页面置换算法
在了解内存页面置换算法前,我们得先了解 缺页异常(缺页中断)。 当 CPU 访问的页面不在物理内存中时,便会产生一个缺页中断,请求操作系统将缺页调入到物理内存。那它与一般的中断主要区别在于: 缺页中断在指令执行 [期…...
行为型模式-观察者模式
1.观察者设计模式* 定义:当对象间存在一对多关系时,则使用观察者模式(Observer Pattern)。比如,当一个对象被修改时,则会自动通知依赖它的对象。观察者模式属于行为型模式。 意图:定义对象间的…...
前端面试:【新技术与趋势】WebAssembly、Serverless、GraphQL
在不断演进的技术领域中,WebAssembly、Serverless和GraphQL都是备受关注的新技术和趋势。它们改变了软件开发、部署和数据传输的方式,为开发者提供了更多的选择和灵活性。 1. WebAssembly(Wasm): 简介: Web…...
【ubuntu】 20.04 网络连接器图标不显示、有线未托管、设置界面中没有“网络”选项等问题解决方案
问题 在工作中 Ubuntu 20.04 桌面版因挂机或不当操作,意外导致如下问题 1、 Ubuntu 网络连接图标消失 2、 有线未托管 上图中展示的是 有线 已连接 ,故障的显示 有限 未托管 或其他字符 3、 ”设置“ 中缺少”网络“选项 上图是设置界面,…...
SpringCloud/SpringBoot多模块项目中配置公共AOP模块实现打印子模块Controller所有请求参数与日志
项目中遇到多个模块需要打印Controller请求日志,在每个模块里面加AOP并且配置单独的切面笔者认为代码冗余,于是乎就打算把AOP日志打印抽离成一个公共模块,谁想用就引入Maven坐标就行。 定义公共AOP模块 并编写AOP工具 AOP模块pom.xml如下 &…...
【GeoDa实用技巧100例】022:geoda生成空间权重矩阵(邻接矩阵、距离矩阵)
geoda生成空间权重矩阵(邻接矩阵、距离矩阵),车式矩阵、后式矩阵、K邻接矩阵。 文章目录 一、概述二、“车式”邻接的gal文档生成三、“后式”邻接gal文档生成四、k最近邻居gat文档生成五、查看gal和gat文档一、概述 空间权重矩阵(或相应的表格形式)一般需要用计算机软件生…...
基于web的鲜花商城系统java jsp网上购物超市mysql源代码
本项目为前几天收费帮学妹做的一个项目,Java EE JSP项目,在工作环境中基本使用不到,但是很多学校把这个当作编程入门的项目来做,故分享出本项目供初学者参考。 一、项目描述 基于web的鲜花商城系统 系统有2权限:前台…...
意外发现Cortex-M内核带的64bit时间戳,比32bit的DWT时钟周期计数器更方便,再也不用担心溢出问题了
视频: https://www.bilibili.com/video/BV1Bw411D7F5 意外发现Cortex-M内核带的64bit时间戳,比32bit的DWT时钟周期计数器更方便,再也不用担心溢出问题了 介绍: 看参数手册的Debug章节,System ROM Table里面带Timestam…...
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
文章目录 前言一、单源最短路径1、单源最短路径问题2、Dijkstra 初始化a、参数b、初始化参数c、算法步骤 3、Dijkstra 算法详细步骤a、第一轮算法执行b、第二轮算法执行c、第三轮算法执行d、第四轮算法执行e、第五轮算法执行f、第六轮算法执行 4、java算法实现 二、多源最短路径…...
改进YOLO系列:6.添加ECA注意力机制
添加ECA注意力机制 1. ECA注意力机制论文2. ECA注意力机制原理3. ECA注意力机制的配置3.1common.py配置3.2yolo.py配置3.3yaml文件配置1. ECA注意力机制论文 论文题目:ECA-Net: Efficient Channel Attention for Deep Convolutional Neural Networks 论文链接:ECA-N…...
软件测试知识点总结(一)
文章目录 前言一. 什么是软件测试二. 软件测试和软件调试的区别三. 软件测试和研发的区别四. 优秀的测试人员所应该具备的素质总结 前言 在现实生活中的很多场景下,我们都会进行测试。 比如买件衣服,我们需要看衣服是不是穿着好看,衣服材质如…...
持续集成与持续交付:现代软件测试的变革之路
引言 在数字化时代,软件开发的速度和复杂性都在不断增加。为了满足市场的需求,企业需要更快、更高效地交付高质量的软件产品。在这样的背景下,持续集成与持续交付(CI/CD)成为了软件开发和测试的核心实践。 软件开发的…...
深度学习基本理论下篇:(梯度下降/卷积/池化/归一化/AlexNet/归一化/Dropout/卷积核)、深度学习面试
深度学习基本理论上篇:(MLP/激活函数/softmax/损失函数/梯度/梯度下降/学习率/反向传播) 深度学习基本理论上篇:(MLP/激活函数/softmax/损失函数/梯度/梯度下降/学习率/反向传播)、深度学习面试_会害羞的杨…...
[Ubuntu 20.04] 通过udev规则修改网卡名称(例如eth0)
在 Ubuntu 20.04 操作系统中,默认情况下,网卡接口名称采用了一种较为复杂的命名方式(如 enp0s3、eth0 等)。然而,有时候我们可能更希望使用更简洁和易于识别的名称来标识不同的网络接口。那么如何在 Ubuntu 20.04 中修改网卡接口的名称,以满足个性化需求。 步骤一:查看当…...
Java“牵手”根据关键词搜索(分类搜索)lazada商品列表页面数据获取方法,lazadaAPI实现批量商品数据抓取示例
lazada商城是一个网上购物平台,售卖各类商品,包括服装、鞋类、家居用品、美妆产品、电子产品等。要获取lazada商品列表和商品详情页面数据,您可以通过开放平台的接口或者直接访问lazada商城的网页来获取商品详情信息。以下是两种常用方法的介…...
Java—实现多线程程序 | 入门
目录 一、前言 二、基本概念 进程 线程 三、Java多线程实现 java.lang.Thread类 获取线程名字及对象 获取main进程名 Thread currentThread() 四、线程优先级 设置优先级 一、前言 前期入门学习的代码中,全部都是单线的程序,也就是从头到尾…...
8.5 【C语言】指向函数的指针
8.5.1 什么是函数的指针 每次调用函数时都从该地址入口开始执行此段函数代码。函数名代表函数的起始地址。 8.5.2 用函数指针变量调用函数 例8.22 用函数求整数a和b中的大者 解题思路:在主函数调用max函数,除了可以通过函数名调用外,还可…...
C++实现字符串的逆置
目录 C和C的区别 【1】C对C的扩充 【2】C对C的兼容 第一个C程序 【1】hello world 【2】cout标准输出流对象 i)介绍 ii)运算 iii)cout的使用 iv)使用cout指定格式的输出 练习:1、输出斐波那契的前10项。 【3】…...
论Spring或Spring Boot的花式扩展
文章目录 引言扩展点讲述花式扩展之自动配置类花式扩展之实现接口实现方式样例 花式扩展之自定义starterImport方式SpringFactories方式 总结鸣谢 引言 Spring Boot是一个高度可定制的框架,旨在帮助开发者快速创建、配置和管理他们的应用程序 扩展点讲述 Spring Bo…...