自从上次刷了一题LeetCode两数之和
后,我就去研读了uthash的源码,对其链表的使用方法感到非常震撼。
随后,我又发现Linux内核链表的实现也采用了类似的思想。
接下来,我将和大家分享传统链表与Linux内核链表实现之间的差异。
在C语言中,传统链表的实现通常如下所示:
/**
* @Author:typedef公众号
*/
typedef struct Node {
int data; // 数据域
struct Node* prev; // 指向前一个节点的指针
struct Node* next; // 指向后一个节点的指针
} Node;
每个节点包含数据和指向上一个以及下一个节点的指针,还有一些用户数据。如下图所示:
从上述代码和结构可以看出,传统链表的缺点十分显著。其数据结构紧密依赖于特定的用户自定义结构体,缺乏通用性。
因为指针指向的用户区域结构体变化多样,所以链表的操作函数难以被重复利用,在不同的项目或模块中需要重复编写类似的操作逻辑,这极大地降低了开发效率。
Linux 的链表结构设计为链表的指针直接指向用户结构体中的链表节点。例如:
/**
* @Author:typedef公众号
*/
struct list {// 定义双向链表节点结构
struct list *prev;
struct list *next;
};
typedefstruct {// 定义包含链表节点的结构体
int data;
struct list node;
} my_struct;
它将链表节点抽象出来,定义在一个通用的结构体struct list
中,数据结构如下图所示:
那么问题来了,因为链表存放的都是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))); })
参数介绍:
这个宏的目的是根据结构体成员的地址获取该结构体的起始地址。实现的核心原理是利用指针运算和结构体成员的偏移量来获得结构体的起始地址。
假如有一个类型为my_struct
的user
对象,则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的解决之道:堆栈分析实战