本文共 5449 字，大约阅读时间需要 18 分钟。

kernel 链表

代码参考 ：https://www.cnblogs.com/Anker/p/3475643.html

链表结构参考 ：

在linux 中，链表是一种双向的循环链表，linux 中，链表的结构是什么样子的呢？ 首先，在kernel中，链表的结构体的定义是： 每一个链表的成员有一个 next 指针，指向下一个链表成员 有一个 prev 指针，指向前一个链表的成员

struct list_head {	struct list_head *next, *prev;    };

1. 当链表中只有一个head的时候，经过初始化的链表如下图所示：
   这时候，链表头的next 指针和prev 指针都指向自己
   
2. 当在此再添加一个成员，那么整个链表将变成如下图所示：
   下图中，head 的next 与prev 指针都指向节点1，而节点1的next 和prev 指针都指向head。
   
3. 当添加第二个列表的成员后（链表成员依次向后添加），结构如下图所示：
   head的next->node1, node1的next 指向node2, node2 的next 指向head.
   head 的prev 指向的是整个链表的尾部，也就是node2,node2的prev 执行node1, node1的prev 指向 head.
   自此，内核中链表的结构以及添加节点的过程已经清除了，但是内核链表中是没有数据成员的，那么应该怎么添加数据成员，怎么使用呢？

其实要完全搞懂链表如何使用，需要明白 contain of 的用法才行，但是要仅仅会用，则不需要去深入理解 contain of 的用法。 其实，内核中的链表是在list_head 和数据成员一起封装成为一个新的结构体，list_head 这是这个结构体的lable,通过寻找结构体中的list_head 成员，便可以找到这个结构体中的数据 成员。

下面用代码来说明这个用法：

如下是定义一个包含有 链表节点的结构体。

//定义app_info链表结构typedef struct application_info{    int  app_id;    int  up_flow;    int  down_flow;    struct    list_head app_info_node;//链表节点}app_info;

下面这是通过链表节点获取整个结构体的宏

在kernel 中，通过list_entry 获取含有节点的结构体的起始地址，也就获取了使用的结构体

//计算member在type中的位置#define offsetof(type, member)  (size_t)(&((type*)0)->member)//根据member的地址获取type的起始地址#define container_of(ptr, type, member) ({          \        const typeof(((type *)0)->member)*__mptr = (ptr);    \    (type *)((char *)__mptr - offsetof(type, member)); })#define list_entry(ptr, type, member) \    container_of(ptr, type, member)

在main 函数中，

app_info * app_info_list = 	(app_info *) malloc(sizeof(app_info));	app_info *app1,*app2,*app3;	struct list_head *head = &app_info_list->app_info_node;	INIT_LIST_HEAD(head);	//插入三个app_info		app1 = get_app_info(100,10,20);	list_add_tail(&app1->app_info_node, head);	app2 = get_app_info(200,20,40);	list_add_tail(&app2->app_info_node, head);	app3 = get_app_info(400,40,80);	list_add_tail(&app3->app_info_node, head);		/* 获取含有app3 结构体的值*/	temp_app = list_entry(&app3->app_info_node,app_info,app_info_node);

至此，链表的基本上已经理解，下面具体研究一下 contain of 的使用。 参考https://www.cnblogs.com/Anker/p/3472271.html 其实参考文献中，作者已经写的很清楚，我在此在稍微写一下 container_of　的宏如下：这个宏主要分为两部分：下面分开解析一下： 注意　：　编译器认为0是一个有效的地址，从而认为0是type指针的起始地址

//计算member在type中的位置#define offsetof(type, member)  (size_t)(&((type*)0)->member)//根据member的地址获取type的起始地址#define container_of(ptr, type, member) ({          \        const typeof(((type *)0)->member)*__mptr = (ptr);    \    (type *)((char *)__mptr - offsetof(type, member)); })

第一部分：

const typeof(((type )0)->member)__mptr = (ptr); 第一部分其实定义了一个__mptr，这个指针将被强制转化，并且指向ptr。结合上述使用的例子： list_entry(&app3->app_info_node,app_info,app_info_node); type就是app_info， ptr则是app3->app_info_node中的地址。 member　是　app_info_node

因此宏的第一部分则是定义了一个０指针，指针类型是app_info，则在程序运行时，会开辟出一段内存，内存大小就是app_info结构体的大小，在这个结构体中，有一个成员的类型是app_info_node，因此所定义的__mptr的类型便是app_info_node，而这个指针指向的是app3->app_info_node中的地址。

第二部分：

　　(type *)((char *)__mptr - offsetof(type, member)); 　　便是用刚刚获得的地址减去app_info_node在结构体中的偏移值。如下图所示：　是offsetof(type, member)　的含义，也就是member距离结构体开始的偏差。当知识实际的member地址以后，用实际的地址减去偏差的大小，就可以得到整个结构体的实际的地址。 　　 　　@[TOC](４. 测试代码以及分析)

#include 
   
    #include 
    
     //计算member在type中的位置#define offsetof(type, member)  (size_t)(&((type*)0)->member)//根据member的地址获取type的起始地址#define container_of(ptr, type, member) ({          \        const typeof(((type *)0)->member)*__mptr = (ptr);    \    (type *)((char *)__mptr - offsetof(type, member)); })#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \	struct list_head name = LIST_HEAD_INIT(name)struct list_head {	struct list_head *next, *prev;    };// name = { &(name), &(name) }static inline void INIT_LIST_HEAD(struct list_head *list){	list->next = list;	list->prev = list;}static inline void __list_add(struct list_head *new,			      struct list_head *prev,			      struct list_head *next){	next->prev = new;	new->next = next;	new->prev = prev;	prev->next = new;}/** * list_add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */static inline void list_add(struct list_head *new, struct list_head *head){	__list_add(new, head, head->next);}/** * list_add_tail - add a new entry * @new: new entry to be added * @head: list head to add it before * * Insert a new entry before the specified head. * This is useful for implementing queues. */static inline void list_add_tail(struct list_head *new, struct list_head *head){	__list_add(new, head->prev, head);}//定义app_info链表结构typedef struct application_info{    int  app_id;    int  up_flow;    int  down_flow;    struct    list_head app_info_node;//链表节点}app_info;#define list_entry(ptr, type, member)    container_of(ptr, type, member)static app_info * get_app_info (int app_id, int up_flow, int down_flow){	app_info * temp = (app_info *)malloc(sizeof(app_info));	temp->app_id = app_id;	temp->up_flow = up_flow;	temp->down_flow = down_flow;	return temp;}int main(void){	app_info * app_info_list = 	(app_info *) malloc(sizeof(app_info));	app_info *app1,*app2,*app3,*temp_app;	struct list_head *head = &app_info_list->app_info_node;	INIT_LIST_HEAD(head);	//插入三个app_info		app1 = get_app_info(100,10,20);	list_add_tail(&app1->app_info_node, head);	app2 = get_app_info(200,20,40);	list_add_tail(&app2->app_info_node, head);	app3 = get_app_info(400,40,80);	list_add_tail(&app3->app_info_node, head);	/* 获取含有app3 结构体的值*/	temp_app = list_entry(&app3->app_info_node,app_info,app_info_node);	return 0;}