图解C语言侵入式双向循环链表与 container_of 宏底层原理

一、侵入式链表在了解侵入式链表之前先回顾之前的非侵入式链表形式如下structNode{intdata;// 数据structNode*next;};在非侵入式链表的这种设计中拿到一个Node顺便也就拿到了它的data。而在 Linux 内核中ListNode本身纯粹只是一个“串联工具”存放在业务结构体中。例如下面代码中的ListNode node嵌入在MyTimer业务结构体中typedefstructMyTimer{uint32_ttimeout;void(*cb)(void);// ... 业务数据 ...structListNodenode;// 链表节点侵入在对象内部}MyTimer;下面将结合具体的代码探讨下侵入式链表。二、如何实现侵入式链表需要注意本文使用双向循环链表实现侵入式链表。在开启内容之前先说明该链表的一般结构梳理下重要节点之间的关系head.nextnode1 head.prevnode3即链表尾节点 head.prev2.1 定义句柄与节点#includestdint.h#includestdbool.h#includestddef.h// 1. 定义节点 (Node)// 仅包含前驱、后继指针不包含数据 datatypedefstructListNode{structListNode*prev;structListNode*next;}ListNode;// 2. 定义链表管理器 (List)typedefstruct{ListNode head;// 可加 size 用以记录数量}List;// 定义句柄typedefList*ListHandle;typedefListNode*ListNodeHandle;使用句柄抽象指针提升可读性便于后期拓展。需要注意的是在上面这段代码中链表管理器List中包含了一个实体头节点head用于表示链表的入口。此时链表结构如下List └──head(哨兵节点)↓ node1 ↔ node2 ↔ node32.2 操作函数2.2.1 初始化头节点的prev和next都指向自己代表空voidList_Init(ListHandle list){list-head.nextlist-head;list-head.prevlist-head;}需要注意此处的list-head是一个实实在在的结构体变量对象本身它占用着 8 字节或 16 字节的内存空间。为正确理解上述代码给出一个简单版本的示例inta5;int*p;pa;上面简单代码中可分为以下3步创建一个 整型变量a实体在内存中占有一定空间可类比list-head创建一个 指针变量p指针可类比list-head.next和list-head.prev将a的地址存入p指向该实体即最后的 头节点的prev和next都指向自己2.2.2 插入节点该函数是我们后续插入操作的核心函数该函数把new_node插入到prev和next两个节点之间// 插入节点插在 prev 和 next 中间staticvoid__List_Add(ListNodeHandle new_node,ListNodeHandle prev,ListNodeHandle next){next-prevnew_node;new_node-nextnext;new_node-prevprev;prev-nextnew_node;}可以参考之前文章中的“先连新后断旧”图示2.2.3 尾插直接调用我们已经写好的插入API函数// 尾部插入通常用于通过 Event 队列voidList_AddTail(ListHandle list,ListNodeHandle new_node){__List_Add(new_node,list-head.prev,list-head);}重点理解下__List_Add(new_node, list-head.prev, list-head);首先明确下__List_Add的作用把new_node插入到prev和next两个节点之间;在尾插法当中待插入的节点new_node的前驱节点为原链表中的尾节点后继节点为头节点head(可以想象这是个环状结构)list为我们的链表管理器其内部存放头节点。在双向循环链表结构中list-head.prev指向尾节点如下图中的node3可视化下尾插法的操作逻辑假设此时的链表结构如下未插入前的链表结构2. 尾部插入将new_node插入在原链表的尾节点node3和 头节点head中 3. 最终链表结构2.2.4 删除节点// 删除节点// 注意: 这体现了侵入式的优势删除不需要 ListHandle只要有 NodeHandle 即可voidList_Del(ListNodeHandle node){node-next-prevnode-prev;node-prev-nextnode-next;// 将 node 的指针清空防止野指针node-nextNULL;node-prevNULL;}图示2.2.5 链表是否为空// 检查链表是否为空boolList_IsEmpty(ListHandle list){returnlist-head.nextlist-head;}检查“头节点的下一个节点是不是头节点本身”注意下空链表的初始形态头节点的next和prev指针都指向它自己。三、核心宏container_of// 计算成员 member 在结构体 type 中的字节偏移量// 标准库 stddef.h 已包含 offsetof这里为了理解列出原理// #define offsetof(type, member) ((size_t)((type *)0)-member)// ★★★ 核心宏 ★★★// ptr: 指向结构体成员的指针即 timer-node// type: 外层结构体的类型即 struct MyTimer// member: 结构体中该成员的名字即 node#definecontainer_of(ptr,type,member)\((type*)((char*)(ptr)-offsetof(type,member)))// 为了方便我们可以封装遍历宏#defineList_ForEach(pos,list)\for(pos(list)-head.next;pos!(list)-head;pospos-next)明确container_of的作用 “已知结构体里某个成员的指针反推出整个结构体的首地址。”结构体首地址 成员的当前内存地址 - 成员在结构体内部的相对偏移量假设存在下面的业务结构体该结构体嵌套了ListNode node;typedefstruct{intid;// 偏移量假设为 0charname[20];// 偏移量假设为 4ListNode node;// 偏移量假设为 16}Student;内存简图如下内存地址 Student 结构体内部0x1000---[intid](占4字节)0x1004---[charname[20]](占20字节)0x1024---[ListNode node](占16字节包含 prev 和 next)此处的0x1000是整个Student结构体的起始地址。而0x1024是内部成员node的起始地址。它们之间相差了 24 个字节的偏移量。当遍历链表时得到的其实是指向node的指针假设地址是0x1024。但需要的是Student这个结构体的地址这样才能读出学生的id和name。怎么从 0x1024 退回到 Student 的起始地址 0x1000 呢此时就需要这个宏#definecontainer_of(ptr,type,member)\((type*)((char*)(ptr)-offsetof(type,member)))ptr指向结构体成员的指针例如 指向 node 的指针type:外层结构体的类型例如Studentmember结构体中该成员的名字例如nodeoffsetof(type, member)通过这个宏计算node这个成员在Student结构体里距离开头有多远假设是 24 个字节。这个值在编译时就确定.(char *)(ptr)将node指针强转成char *字符指针。在C语言中指针加减的单位是它所指向的数据类型的大小。转为char *大小为1字节保证了后面减去的偏移量24均按字节计算的而不是减去 24 个node的大小。((char *)(ptr) - offsetof(type, member))当前地址0x1024减去偏移量24刚好等于结构体的起始首地址0x1000。四、实例演示结构体定义typedefstruct{intid;// 业务数据任务IDconstchar*name;// 业务数据任务名称// 【关键】嵌入链表节点ListNode node;// “挂钩”}MyTask;初始化并挂载List taskList;// 全局任务链表MyTask task1,task2;voidSystem_Init(){// 1. 初始化空链表List_Init(taskList);// 2. 初始化任务数据task1.id1;task1.nameSensor;task2.id2;task2.nameMotor;// 3. 【关键】把衣服的挂钩挂到绳子上List_AddTail(taskList,task1.node);List_AddTail(taskList,task2.node);}遍历通过宏进行遍历pos可以类比于我们之前设定的“起跑线”#defineList_ForEach(pos,list)\for(pos(list)-head.next;pos!(list)-head;pospos-next)voidSystem_Process(){ListNodeHandle pos;MyTask*task;// 遍历链表的宏底层就是一个 for 循环List_ForEach(pos,taskList){// 【关键】从 node 指针还原出 MyTask 指针taskcontainer_of(pos,MyTask,node);printf(Processing Task: %s\n,task-name);}}