提起linux内核链表，首先一定得弄清楚的两个linux内核常用宏offsetof && container_of offsetof宏
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)宏解析： 1、size_t在系统中一般指unsigned int，无符号整型 2、(TYPE *)0，把0地址强制转换成type结构体类型的指针，此时0就成了type结构体的首地址，就是结构体指针，那么就可以通过结构体指针来引用该结构体的成员，所以(TYPE *)0)->MEMBER的整体意义便是引用type类型结构体的成员member。 3、&((TYPE *)0)->MEMBER的意义便是去member成员相对于0地址的偏移量 举个例子：
#include <stdio.h>
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
struct example_struct {
int a;
int b;
char c;
};
int main() {
size_t offset = offsetof(struct example_struct, b);
printf("Offset of 'b' member: %zu\n", offset);
return 0;
}
运行结果如下：
container_of宏
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member)*__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })
宏解析：
1、typeof 是一个在 C 语言中的编译器扩展，用于获取表达式的类型
2、const typeof(((type *)0)->member)*__mptr = (ptr); 是将ptr复制给mptr，mptr是struct中member的指针
3、(type *)((char *)__mptr - offsetof(type, member)); 是将mptr指针减去offsetof的值，那么就是返回这个struct的指针值，将 mptr 转换为 char * 是为了进行指针运算和偏移量计算
使用demo：
#include <stdio.h>
#define offsetof(type, memb) (unsigned long)(&((type *)0)->memb)
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member)*__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })
struct test_str {
int a;
int b;
int c;
};
int main(void)
{
struct test_str test;
printf("test ptr: 0x%p, test.b ptr: 0x%p\n", &test, &test.b);
printf("offsetof val: 0x%lx\n", offsetof(struct test_str, b));
//通过test_str中的b指针，来返回test_str结构体指针
printf("container_of: 0x%p\n", container_of(&test.b, struct test_str, b));
return 0;
}
运行结果如下：
linux内核双向链表
在leetcode刷题一般使用的都是下面的链表使用方式：
struct node {
unsigned int data;
struct node *next;
struct node *prev;
};
linux内核链表结构体如下：
struct list_head {
struct list_head *next, *prev;
}
具体到实际使用时候的差异：
//做一个person的管理系统，person包含了age和name
//方式1：
struct person_list {
int age;
char *name;
struct person_list *next, *prev;
};
//方式2：
struct list_head {
struct list_head *next, *prev;
};
struct person {
int age;
char *name;
struct list_head list;
};
linux内核这种将链表抽象出来的实现方式，是由于Linux内核需要管理非常多的硬件设计，方式1的使用是和业务强相关的。
在linux内核中，则可以通过list来访问person的数据，使用上面提到的offsetof和container_of宏
linux内核链表使用API:
链表初始化：
static inline void
INIT_LIST_HEAD(struct list_head *list)
{
list->next = list->prev = list;
}
// 链表静态初始化
#define LIST_HEAD_INIT(name) { &(name), &(name) }
// 链表动态初始化
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
添加链表节点：
static inline void
__list_add(struct list_head *entry,
struct list_head *prev, struct list_head *next)
{
next->prev = entry;
entry->next = next;
entry->prev = prev;
prev->next = entry;
}
-->
void __list_add(struct list_head *new,
struct list_head *a,
struct list_head *b)
{
if (!__list_add_valid(new, prev, next))
return;
b->prev = new;
new->next = b;
new->prev = a;
a->next = new;
}
// 添加链表节点
static inline void
list_add(struct list_head *entry, struct list_head *head)
{
__list_add(entry, head, head->next);
}
static inline void
list_add_tail(struct list_head *entry, struct list_head *head)
{
__list_add(entry, head->prev, head);
}
__list_add(new, a, b)过程示意图如下：
删除链表节点：
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
prev->next = next;
next->prev = prev;
}
// 链表node节点删除操作，在调用 list_del() 后，要手动释放该节点的内存
void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = NULL;
entry->prev = NULL;
}
链表遍历：
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_entry(pos, head, member) \
for (pos = container_of((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = container_of(pos->member.next, typeof(*pos), member))
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
list_for_each() 和 list_for_each_safe() 的使用区别：
- 遍历链表时若不删除链表节点，两者都可以使用，效果没有差别;
- 遍历链表时若需要删除链表节点，则必须使用list_for_each_safe()，否则会出错
#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/list.h>
#include <linux/slab.h>
struct my_struct {
int data;
struct list_head list;
};
static struct list_head my_list;
static int my_init(void)
{
struct my_struct *obj;
int i;
// 初始化链表
INIT_LIST_HEAD(&my_list);
// 向链表中添加节点
for (i = 0; i < 5; i++) {
obj = kmalloc(sizeof(struct my_struct), GFP_KERNEL);
obj->data = i;
list_add_tail(&obj->list, &my_list);
}
// 遍历链表并打印节点数据
struct list_head *pos;
struct my_struct *entry;
list_for_each(pos, &my_list) {
entry = list_entry(pos, struct my_struct, list);
printk(KERN_INFO "Data: %d\n", entry->data);
}
return 0;
}
static void my_exit(void)
{
struct list_head *pos, *q;
struct my_struct *entry;
// 删除链表中的所有节点并释放内存
list_for_each_safe(pos, q, &my_list) {
entry = list_entry(pos, struct my_struct, list);
list_del(pos);
kfree(entry);
}
}
module_init(my_init);
module_exit(my_exit);
参考博客： https://blog.csdn.net/BigElt/article/details/131851307#comments_30341818 https://blog.csdn.net/weixin_37620587/article/details/129893469? 标签：head,struct,--,list,20240225,next,链表,pos From： https://www.cnblogs.com/lethe1203/p/18032772