源码阅读之旅,Linux内核链表妙在哪?

原创 typedef 2024-12-31 08:22

一、导读

自从上次刷了一题LeetCode两数之和后,我就去研读了uthash的源码,对其链表的使用方法感到非常震撼。

随后,我又发现Linux内核链表的实现也采用了类似的思想。

接下来,我将和大家分享传统链表与Linux内核链表实现之间的差异。

二、传统链表结构

在C语言中,传统链表的实现通常如下所示:

/**
 * @Author:typedef公众号
 */

typedef struct Node {
  int data;              // 数据域
  struct Nodeprev;     // 指向前一个节点的指针
  struct Nodenext;     // 指向后一个节点的指针
} Node;

每个节点包含数据和指向上一个以及下一个节点的指针,还有一些用户数据。如下图所示:

常用链表结构

从上述代码和结构可以看出,传统链表的缺点十分显著。其数据结构紧密依赖于特定的用户自定义结构体,缺乏通用性。

因为指针指向的用户区域结构体变化多样,所以链表的操作函数难以被重复利用,在不同的项目或模块中需要重复编写类似的操作逻辑,这极大地降低了开发效率。

三、Linux 内核链表结构

Linux 的链表结构设计为链表的指针直接指向用户结构体中的链表节点。例如:

/**
 * @Author:typedef公众号
 */

struct list {// 定义双向链表节点结构
struct list *prev;
struct list *next;
};

typedefstruct {// 定义包含链表节点的结构体
int data;
struct list node;
} my_struct;

它将链表节点抽象出来,定义在一个通用的结构体struct list中,数据结构如下图所示:

Linux 内核链表结构

那么问题来了,因为链表存放的都是struct list类型对象,而用户数据是my_struct类型对象,这样我不是获取不到用户对象了嘛?

而其中的精髓也就在此处,Linux 是通过container_of 宏实现的,原型如下。

/**
 * 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.
 *
 * WARNING: any const qualifier of @ptr is lost.
 */

#define container_of(ptr, type, member) ({    \
 void *__mptr = (void *)(ptr);     \
 static_assert(__same_type(*(ptr), ((type *)0)->member) || \
        __same_type(*(ptr), void),   \
        "pointer type mismatch in container_of()"); \
 ((type *)(__mptr - offsetof(type, member))); })

参数介绍:

  • ptr:指向结构体成员的指针。
  • type:包含该成员的结构体的类型。
  • member:结构体中的成员名称。

这个宏的目的是根据结构体成员的地址获取该结构体的起始地址。实现的核心原理是利用指针运算和结构体成员的偏移量来获得结构体的起始地址。

假如有一个类型为my_structuser对象,则container_of(&user.node, my_struct, node)返回的对象就是user

我们再来看下内部是如何实现的。

void *__mptr = (void *)(ptr);

第一行是将ptr转换为void *,后面再进行减法运算时,实际上是将指针当作char *类型来处理(因为void *在进行算术运算时会被转换为char *类型),这样就可以按照字节为单位准确地减去成员在结构体中的偏移量,而不受原始成员指针类型的影响。

static_assert(__same_type(*(ptr), ((type )0)->member) ||
__same_type(
(ptr), void),
"pointer type mismatch in container_of()");

第二行是一个静态断言,用于检查ptr所指向的成员的类型是否与type结构体中member成员的类型相同,或者ptr是否为void *类型。如果不满足条件,编译时会产生错误提示 “pointer type mismatch in container_of ()”。

((type *)(__mptr - offsetof(type, member)));

第三行通过offsetof(type, member)获取成员member在结构体type中的偏移量。然后将__mptr转换为char *类型指针,以便按字节进行减法运算,从成员的地址__mptr中减去成员相对于结构体起始位置的偏移量,从而计算出整个结构体的首地址。最后,将结果转换为type *类型的指针,表示整个结构体的首地址。

其中,offsetof宏用于计算结构体成员相对于结构体起始地址的偏移量,其定义如下:

#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER) 

它的工作原理是:首先将0强制转换为type *类型的结构体指针(表示结构体起始地址为0),然后通过->MEMBER访问该假设结构体的MEMBER成员,此时MEMBER的地址就是其相对于结构体开头的偏移量。

感觉这些代码写的好哦,大为震撼,哈哈...

Linux内核链表结构提供了更高的通用性和操作复用性。通过将数据和节点解耦,我们可以在不同的数据结构中重用相同的链表操作,简化了代码的复杂度。

四、链接

  • https://github.com/torvalds/linux/blob/master/include/linux/container_of.h
  • https://github.com/troydhanson/uthash

五、最后

我把uthash 下载并保存到了网盘,如果您也想阅读源码但没有梯子,可以后台回复关键字688 获取链接,然后从02-代码目录中查找,只要看example.c 以及uthash.h 文件就行了。

我鼓励大家积极阅读源码,尽管过程中可能会遇到一些挑战和困难,但这也是锻炼思维和提升技能的宝贵机会。欢迎交流...

END

点赞、转发加关注,一键三连,好运年年

关注公众号后台回复数字688或668可获取嵌入式相关资料

往期推荐

为什么推荐大家去考软考高级,因为政府补贴已到账

程序员必看:浮点数精度问题全解析

C语言编程新手:如何判断结构体(struct)相等?

揭秘难以复现Bug的解决之道:堆栈分析实战

typedef 主要用于记录个人学习、总结、分享的一个平台。 教学相长,共同进步。同时并建立技术交流群,欢迎加入。期待您的关注。
评论
  • 在科技飞速发展的今天,机器人已经逐渐深入到我们生活和工作的各个领域。从工业生产线上不知疲倦的机械臂,到探索未知环境的智能探测机器人,再到贴心陪伴的家用服务机器人,它们的身影无处不在。而在这些机器人的背后,C 语言作为一种强大且高效的编程语言,发挥着至关重要的作用。C 语言为何适合机器人编程C 语言诞生于 20 世纪 70 年代,凭借其简洁高效、可移植性强以及对硬件的直接操控能力,成为机器人编程领域的宠儿。机器人的运行环境往往对资源有着严格的限制,需要程序占用较少的内存和运行空间。C 语言具有出色
    Jeffreyzhang123 2025-01-02 16:26 82浏览
  •  近年来,消费电子行业难言景气,长期处于萎靡不振的状态。其中,作为明星品类的智能手机同样被寒意所笼罩,出货量持续下跌。据IDC发布的报告显示,2023年全年,中国智能手机市场出货量约2.71亿台,同比下降5.0%,创近10年以来最低出货量。不过,在智能手机行业整体低迷之际,折叠屏手机却表现亮眼,成为智能手机市场唯一实现增长的品类。据IDC发布的跟踪报告显示,2023年,中国折叠屏手机市场出货量约700.7万台,同比增长114.5%。而这也是自2019年首款产品上市以来,出货量连续4年同
    刘旷 2025-01-02 11:27 37浏览
  • 随着全球汽车行业向更加清洁、可持续的能源转型,燃料电池汽车(FCV)作为一种具有广阔前景的技术,正逐渐受到业界的广泛关注。这类氢能源车辆通过燃料电池中的电化学反应,将氢气转化为电能,并仅产生水作为副产品,展现出显著的环境效益。然而,氢气的易燃性也为燃料电池汽车的安全带来了挑战,因此,高效的氢气泄漏检测系统和残氢排放监控技术对于确保车辆的安全性和可靠性至关重要。 ‌一、氢能源车氢气泄漏检测技术‌为了确保燃料电池汽车的安全性,氢气传感器被广泛应用于氢气泄漏检测中。这些传感器能够集成到车辆的
    锂电小助手 2025-01-02 10:05 51浏览
  • 2层PCB设计时候回路的寄生电感计算方式。由两个平面构成电流路径的回路电感,取决于每个平面路径的局部自感和它们之间的局部互感。平面越宽,电流分布就越扩散开,平面的局部自感就越小,从而回路电感也就越小。平面越长,局部自感就越大,从而回路电感也就越大。平面间距越小,平面之间的互感就越大,从而回路电感也就越小。当该区域为正方形,即长度等于宽度时,无论边长是多少,长和宽之比始终等于1。令人惊奇的是,一对平面上的边长为100mil的正方形区域和边长为1in的正方形区域的回路电感相同。平面对上的任一正方形区
    tao180539_524066311 2025-01-02 13:51 41浏览
  • 早期概念与探索阶段(19 世纪以前):在古代,人类就对自动机械充满了想象,如古希腊时期的希罗发明的自动门、水钟等自动装置,中国古代的指南车、木牛流马等,虽然这些装置不能称之为真正的机器人,但为后来机器人的发展奠定了思想基础。从概念走向实践阶段(19 世纪~20 世纪初):随着工业革命的到来,自动机概念开始与实际机械设计结合,出现了具有实际功能的自动机械,例如雅卡尔提花机等,可通过穿孔卡片控制编织图案,为后续可编程控制的机器人发展提供了灵感。现代机器人产业萌芽期(1920 年代~1950 年代):
    Jeffreyzhang123 2025-01-02 14:53 81浏览
  • 前言近年来,随着汽车工业的快速发展,尤其是新能源汽车与智能汽车领域的崛起,汽车安全标准和认证要求日益严格,应用范围愈加广泛。ISO 26262和ISO 21448作为两个重要的汽车安全标准,它们在“系统安全”中扮演的角色各自不同,但又有一定交集。在智能网联汽车的高级辅助驾驶系统(ADAS)应用中,理解这两个标准的区别及其相互关系,对于保障车辆的安全性至关重要。ISO 26262:汽车功能安全的基石如图2.1所示,ISO 26262对“功能安全”的定义解释为:不存在由于电子/电气系统失效引起的危害
    广电计量 2025-01-02 17:18 89浏览
  •  在这个日新月异的科技时代,智能家居正以前所未有的速度融入我们的日常生活,从智能灯光到温控系统,从安防监控到语音助手,每一处细节都透露着科技的温度与智慧。而在这场智能化浪潮中,一个看似不起眼却至关重要的组件——晶体管光耦,正扮演着连接物理世界与数字世界的隐形桥梁角色,默默推动着智能家居行业的发展与革新。 晶体管光耦——智能家居的“神经递质”晶体管光耦,作为一种能够将电信号转换为光信号,再通过光信号控制另一侧电路开关的电子元器件,其独特的工作原理使得它在隔离传输、抗干扰及保护电
    晶台光耦 2025-01-02 16:19 59浏览
  • 【工程师故事】+半年的经历依然忧伤,带着焦虑和绝望  对于一个企业来说,赚钱才是第一位的,对于一个人来说,赚钱也是第一位的。因为企业要活下去,因为个人也要活下去。企业打不了倒闭。个人还是要吃饭的。企业倒闭了,打不了从头再来。个人失业了,面对的不仅是房贷车贷和教育,还有找工作的焦虑。企业说,一个公司倒闭了,说明不了什么,这是正常的一个现象。个人说,一个中年男人失业了,面对的压力太大了,焦虑会摧毁你的一切。企业说,是个公司倒闭了,也不是什么大的问题,只不过是这些公司经营有问题吧。
    curton 2025-01-02 23:08 62浏览
  • 起源与诞生:AI 技术的起源可以追溯到 20 世纪 40 年代,随着计算机技术的兴起,科学家们开始思考如何让机器具备类似人类的智能。1950 年,英国数学家艾伦・图灵提出了著名的 “图灵测试”,为 AI 技术的发展奠定了理论基础。1956 年,美国达特茅斯学院举行了一次人工智能研讨会,标志着 AI 作为一门独立学科的诞生。符号主义阶段(20 世纪 50 年代 - 70 年代):研究人员主要关注如何使用符号逻辑和推理规则来模拟人类思维,试图通过构建复杂的逻辑系统来解决各种问题。然而,由于这种方法的
    Jeffreyzhang123 2025-01-02 15:15 78浏览
  • 常见通信标准无线通信标准蜂窝移动通信标准:如 2G(GSM)、3G(WCDMA、CDMA2000、TD - SCDMA)、4G(LTE)以及 5G 等。以 5G 为例,其具有高速率、低时延、大容量等特点,为智能交通、工业互联网和物联网等领域提供支持。无线局域网标准:主要是 IEEE802.11 标准,也就是我们常说的 Wi - Fi。例如 IEEE802.11ac 和 IEEE802.11ax(Wi-Fi 6)等标准,不断提升无线局域网的传输速度和稳定性。短距离无线通信标准:包括蓝牙(Bluet
    Jeffreyzhang123 2025-01-02 14:33 43浏览
  • 国际标准IPC 标准:IPC-A-600:规定了印刷电路板制造过程中的质量要求和验收标准,涵盖材料、外观、尺寸、焊接、表面处理等方面。IPC-2221/2222:IPC-2221 提供了用于设计印刷电路板的一般原则和要求,IPC-2222 则针对高可靠性电子产品的设计提供了进一步的指导。IPC-6012:详细定义了刚性基板和柔性基板的要求,包括材料、工艺、尺寸、层次结构、特征等。IPC-4101:定义了印刷电路板的基板材料的物理和电气特性。IPC-7351:提供了元件封装的设计规范,包括封装尺寸
    Jeffreyzhang123 2025-01-02 16:50 96浏览
  • 在科技飞速发展的今天,5G 通信技术无疑是最耀眼的明星之一。它如同一场数字革命的风暴,以其前所未有的速度、极低的延迟和强大的连接能力,为我们的生活、经济和社会带来了翻天覆地的变化,开启了一个万物互联的崭新时代。5G 技术的卓越特性5G,即第五代移动通信技术,相比其前辈们,有着诸多令人瞩目的特性。首先是超高速率。5G 网络的理论峰值下载速度可达 10Gbps,这意味着下载一部高清电影只需短短几秒钟,而 4G 网络可能需要几分钟甚至更长时间。这种高速率让高清视频流、云游戏等对带宽要求极高的应用变得流
    Jeffreyzhang123 2025-01-02 14:18 60浏览
  • 从无到有:智能手机的早期探索无线电话装置的诞生:1902 年,美国人内森・斯塔布菲尔德在肯塔基州制成了第一个无线电话装置,这是人类对 “手机” 技术最早的探索。第一部移动手机问世:1938 年,美国贝尔实验室为美国军方制成了世界上第一部 “移动” 手机。民用手机的出现:1973 年 4 月 3 日,摩托罗拉工程师马丁・库珀在纽约曼哈顿街头手持世界上第一台民用手机摩托罗拉 DynaTAC 8000X 的原型机,给竞争对手 AT&T 公司的朋友打了一个电话。这款手机重 2 磅,通话时间仅能支持半小时
    Jeffreyzhang123 2025-01-02 16:41 86浏览
我要评论
0
点击右上角,分享到朋友圈 我知道啦
请使用浏览器分享功能 我知道啦