内核经典数据结构list 剖析

前言：

linux内核中有很多经典的数据结构，list(也称list_head)为其中之一，这些数据结构都是使用C语言实，并且定义和实现都在单独的头文件list.h中。可以随时拿出来使用。

list.h的定义不同linux发行版本路径不同,我们可以在/usr/include目录下find。

虽然list_head是基于C语言实现，但其设计初衷是使用在linux内核中，所以其中用了许多GUN的方法而并非C标准，如typeof，该宏的作用是获取变量类型。所以list_head

存在一定的平台相关性，如果要做跨平台需要进行改造。现我们只对内核原始list_head进行详细说明及实例演示。

原理：

list_head属于一个双向循环链表，表头只是一个指针。当链表为空时，表头的前驱和后继分别指向自己。

list_head的特点：

不包含数据，链表中只有prev和next，这样使得我们的链表使用起来就比较灵活，使用时只需要将其包含进使用的对象即可，有一种面向对象的感觉。例如：在使用时只需要在宿主结构中嵌入list_head类型节点，并将节点插入到list_head表头中。

这样多个宿主结构体内容就通过链表关联了起来。使用时只需要使用宿主结构中的list_head节点反推宿主结构体的首地址就可以访问宿主结构体。

相对于传统链表的包含数据，解决了链表结构冗余，通用性差，不方便移植等问题。

该链表不包含互斥锁，所以在多线程使用下需要加互斥锁进行同步，如下：

struct list_item

{

list_head list;

pthread_mutex_t lmutex;

}

struct list_item g_list_item;//包含了链表头及互斥锁。

链表定义：

struct list_head {

struct list_head *next, *prev;

};

实现方法：

函数说明：

作用	接口类型	函数原型	参数说明	函数说明	备注
增加	内部接口	static inline void __list_add(struct list_head *xnew, struct list_head *prev,struct list_head *next) { next->prev = xnew; xnew->next = next; xnew->prev = prev; prev->next = xnew; }	xnew:新增节点 prev:插入位置的前一个节点 next:插入位置的后一个节点	双向循环链表的插入。 对于双向循环链表，节点插入时我们一般需要考虑4个元素：插入节点前驱；插入节点后继；插入位置前的一个节点后继；插入位置后的一个点解前驱； 所以这里的prev我们可以理解为插入位置前的一个节点，next则为插入位置后的一个节点；
增加	对外接口	static inline void list_add(struct list_head *xnew, struct list_head *head) { __list_add(xnew, head, head->next); }	xnew:新增节点 head:链表头	头插法的方式插入链表。	尾插与头插不同，从这里调用__list_add函数时传参进行区分。
增加	对外接口	static inline void list_add_tail(struct list_head *xnew, struct list_head *head) { __list_add(xnew, head->prev, head); }	xnew:新增节点 head:链表头	尾插法的方式插入链表。
删除	内部接口	static inline void __list_del(struct list_head * prev, struct list_head * next) { next->prev = prev; prev->next = next; }	prev:要删除节点的前驱。 next:要删除节点的后继。	将要删除节点的前驱作为下一个节点的前驱；将后继作为前一个节点的后继；这样要删除的节点就与原链表断开。 同时该节点删除后，该节点原先的前驱和后继连了起来，保证了链表不产生断点。
删除	对外接口	static inline void list_del(struct list_head *entry) { __list_del(entry->prev, entry->next); entry->next = LIST_POISON1; entry->prev = LIST_POISON2; }	entry:要删除的节点	删除节点，并将节点的next,prev分别指向LIST_POISON1，LIST_POISON2。	两个函数都调用了__list_del函数，但是list_del最后将prev,next分别指向了LIST_POSTION2和LIST_POSTION1两个特殊位置，对这两个位置的访问会引起页故障。属于不安全函数；而list_del_init最后调用INIT_LIST_HEAD将next,prev都指向了自己，属于安全函数。一般建议使用list_del_init。 注意：如果链表中的节点是通过malloc或new申请的看空间，这里调用删除接口后需要取手动释放空间
删除	对外接口	static inline void list_del_init(struct list_head *entry) { __list_del(entry->prev, entry->next); INIT_LIST_HEAD(entry); }	entry:要删除的节点	删除节点，并将节点的next,prev指向自己，即初始化。
替换	对外接口	static inline void list_replace(struct list_head *old, struct list_head *xnew) { xnew->next = old->next; xnew->next->prev = xnew; xnew->prev = old->prev; xnew->prev->next = xnew; }	old：被替换的节点 new：替换节点	使用新的节点替换原有的旧节点。	通过实现可以看出list_replace函数替换后old节点与new节点指向的前驱和后继都一样，属于不安全函数；而list_replace_init则会将old的前驱和后继分开，属于安全函数；一般建议使用list_replace_init。
替换	对外接口	static inline void list_replace_init(struct list_head *old, struct list_head *xnew) { list_replace(old, xnew); INIT_LIST_HEAD(old); }	old：被替换的节点 new：替换节点	使用新的节点替换原有的旧节点。
移动	对外接口	static inline void list_move(struct list_head *list, struct list_head *head) { __list_del(list->prev, list->next); list_add(list, head); }	list：要移动的节点 head：表头	移动节点到head之后	移动接口如果的操作的是非链表内部元素，则相当于增加接口的作用。
移动	对外接口	static inline void list_move_tail(struct list_head *list,struct list_head *head) { __list_del(list->prev, list->next); list_add_tail(list, head); }	list：要移动的节点 head：表头	移动节点到head之前
判空	对外接口	static inline int list_empty(const struct list_head *head) { return head->next == head; }	head：表头	判断链表是否为空，返回1表示链表为空，0表示非空。
判空	对外接口	static inline int list_empty_careful(const struct list_head *head) { struct list_head *next = head->next; return (next == head) && (next == head->prev); }	head：表头	判断链表是否为空，返回1表示链表为空，0表示非空。	因为内核在运行时候可能有多个进程同时修改内存，判断链表是否为空需要判断他的前一个节点和后一个节点是否为空。但是注释也承认了这种判断方法的不安全性，要是保证安全操作，还需要加锁保护。
判断是否为最后一个节点	对外接口	static inline int list_is_last(const struct list_head *list, const struct list_head *head) { return list->next == head; }	list：当前节点 head：链表表头	判断当前节点是否为链表的最后一个节点。
链表合并	内部接口	static inline void __list_splice(const struct list_head *list, struct list_head *prev,struct list_head *next) { struct list_head *first = list->next; struct list_head *last = list->prev; first->prev = prev; prev->next = first; last->next = next; next->prev = last; }	list：被合并的链表 prev：合并位置的前一个节点 next：合并位置的后一个节点	ist作为被合并链表的表头，合并相当于将一个链表作为一个整体插入到另一个链表的某一个位置。 first作为表头list的后继，last作为表头list的前驱；表头list的后继的前驱(first→prev)指向合并位置的前一个节点；表头list的前驱的后继(last→next)指向合并位置的后一个节点。 注意：合并后的方要保持一致，还是一个环形。
链表合并	对外接口	static inline void list_splice(struct list_head *list, struct list_head *head) { if (!list_empty(list)) __list_splice(list, head, head->next); }	list：被合并的链表 head：将list合并到head链表	将list链表合并到head链表，合并方式为头插法合入，即将list加入到head之后。 该函数内部实现调用了__list_splice，合并原理见__list_splice详细说明	list_splice于list_splice_init的区别是list_splice_init在合并后将list进行了初始化，属于安全函数。 建议使用list_splice_init
链表合并	对外接口	static inline void list_splice_init(struct list_head *list, struct list_head *head) { if (!list_empty(list)) { __list_splice(list, head, head->next); INIT_LIST_HEAD(list); } }
链表合并	对外接口	static inline void list_splice_tail(struct list_head *list,struct list_head *head) { if (!list_empty(list)) __list_splice(list, head->prev, head); }	list：被合并的链表 head：将list合并到head链表	将list链表合并到head链表，合并方式为尾插法合入，即将list加入到head之前。	list_splice_tail于list_splice_tail_init的区别是list_splice_tail_init在合并后将list进行了初始化，属于安全函数。 建议使用list_splice_tail_init
链表合并	对外接口	static inline void list_splice_tail_init(struct list_head *list,struct list_head *head) { if (!list_empty(list)) { __list_splice(list, head->prev, head); INIT_LIST_HEAD(list); } }

部分宏说明：（附demo）

宏定义	实现	说明	备注
offsetof	#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)	获取变量在宿主结构中的偏移量	（TYPE*）0 这个是欺骗编译器，有一个TYPE类型的指针，它的地址是0；然后对这个指针的MEMBER取地址，因为基地址是0，所以对MEMBER取地址后就是MEMBER在TYPE中的偏移量了。 欺骗编译器的用法类似如下： int *p = (int *)0; 打印p的地址是nil
container_of	#define container_of(ptr, type, member) (\ {const typeof( ((type *)0)->member ) *__mptr = (ptr);\ (type *)( (char *)__mptr - offsetof(type,member) );})	根据结构中某个成员的地址获取宿主结构的地址 ptr：成员地址。 type：宿主结构类型。 member：宿主结构中定义的成员。与ptr同类型。 使用与list_entry相同。	由于type是类型，member是成员，所以这里还是使用(type *)0)->member则表示type类型指针的member成员，然后用typeof取member的类型，这样__mptr就与member成员类型是一样的，最终目的还是为了定义一个与ptr类型相同的中间变量，并且将ptr赋值给它。 (type *)( (char *)__mptr - offsetof(type,member) ); 这一步骤是通过成员现地址减去成员偏移量计算宿主结构体首地址，这里必须对mptr强转成(char*)类型指针，原因是指针加减操作不同于我们int变量的加减， 比如指针的+1操作是指针当前地址+1*N(指针类型大小)。强转成char*后，+n就是指针当前地址+n。如果不强转，直接偏移会越界。 其实定于中间变量这一步我们可以省略，因为我们是通过成员prt的地址来计算宿主结构体的首地址，所以我们可以直接使用ptr，现对container_of改造如下： #define container_of(ptr, type, member) (\ {(type*)((char *)ptr - offsetof(type,member));})
list_entry	#define list_entry(ptr, type, member) \ container_of(ptr, type, member)	根据成员ptr的地址获取宿主结构体的首地址。 type：宿主结构体的类型。 member：ptr在宿主结构体中的成员变量名。	struct student { char name[32]; int age; struct list_head list; }; ptr则表示一个一个list_head类型的指针，type则是struct student类型，member则是成员变量list。
list_first_entry	#define list_first_entry(ptr, type, member) \ list_entry((ptr)->next, type, member)	根据成员ptr的地址获取ptr下一个节点的宿主结构体首地址。 type：宿主结构体的类型 member：ptr在宿主结构体中的成员变量名。	同list_entry
list_for_each	#define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); \ pos = pos->next)	从head之后的一个节点开始向后循环，一般与list_entry或其它方法配合使用。循环时节点无法操作。 pos：list_head类型的指针。 head：链表头。	void Data_list_for_each() { struct list_head *postion = NULL; struct student *p = NULL; /* 参数1:struct list_head结构体指针 参数2:头指针 */ //list_for_each_prev(postion,&g_list) list_for_each(postion,&g_list) { /* 参数1：struct list_head结构体指针 参数2：链表容器结构体类型，这里即struct student 参数3：链表容器中链表的成员变量 */ //二选一，list_entry的实现内部其实调用了container_of p = list_entry(postion,struct student,list); //p = container_of(postion,struct student,list); printf("%s-%d\n",p->name,p->age); } return; }
list_for_each_prev	#define list_for_each_prev(pos, head) \ for (pos = (head)->prev; pos != (head); \ pos = pos→prev)	从head之后的一个节点开始向前循环，一般与list_entry或其它方法配合使用。 pos：list_head类型的指针。 head：链表头。
list_for_each_safe	#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多了一个临时变量n	void Data_list_del_1() { struct list_head *postion = NULL; struct list_head *tmp = NULL; struct student *p = NULL; list_for_each_safe(postion,tmp,&g_list) { p = list_entry(postion,struct student,list); list_del(&p->list); //list_del_init(&p->list); free(p); } return; }
list_for_each_entry	#define list_for_each_entry(pos, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member); \ &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member))	与list_for_each功能相似，只是参数不同，这里的pos是宿主结构体类型，我们可以理解为这个就是list_for_each与list_entry的使用结合体。 比如我们要使用list_for_each对链表进行遍历，并且遍历宿主结构体时就需要与list_entry进行配合。list_for_each_entry刚好实现了这个功能。 pos：宿主结构体类型指针。 head：链表头。 member：宿主结构中链表的成员变量。	void Data_list_for_each_entry() { struct student *p = NULL; /* 参数1：链表容器结构体指针 参数2：头指针 参数3：链表容器中链表的成员变量 */ list_for_each_entry(p,&g_list,list) { printf("%s-%d\n",p->name,p->age); } return; }
list_for_each_entry_reverse	#define list_for_each_entry_reverse(pos, head, member) \ for (pos = list_entry((head)->prev, typeof(*pos), member); \ &pos->member != (head); \ pos = list_entry(pos->member.prev, typeof(*pos), member))	反向遍历，list_for_each_entry为正向遍历	void Data_list_for_each_entry_reverse() { struct student head; struct student *p = NULL; //参数定义同Data_list_for_each_entry函数 list_for_each_entry_reverse(p,&g_list,list) { printf("%s-%d\n",p->name,p->age); } return; }
list_for_each_entry_continue	#define list_for_each_entry_continue(pos, head, member) \ for (pos = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member))	从某个节点开始遍历。 需要与list_prepare_entry(pos,head,member) 配合使用，list_prepare_entry的返回值作为list_for_each_entry_continue的pos。 list_for_each_entry_safe_continue与list_for_each_entry_continue一样，只不过list_for_each_entry_safe_continue遍历后可以直接操作节点，比如删除。因此带safe的函数多了一个中间的临时变量。 pos：宿主结构体类型指针。 head：链表头。 member：宿主结构中链表的成员变量。	void Data_list_for_each_entry_continue() { struct student *pos = NULL; struct student *n = NULL; n = list_prepare_entry(pos,&g_list,list); /* list_for_each_entry_safe_continue与list_for_each_entry_continue一样，只不过 list_for_each_entry_safe_continue遍历后可以直接操作节点，比如删除。因此带safe的 函数多了一个中间的临时变量。 */ list_for_each_entry_continue(n,&g_list,list) { printf("%s-%d\n",n->name,n->age); } return; }
list_for_each_entry_safe	#define list_for_each_entry_safe(pos, n, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member), \ n = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.next, typeof(*n), member))	list_for_each_entry的安全版本，即在遍历的时候可以操作节点。属于正向遍历。 这里我们看到用临时节点n保存了pos的下一个节点地址，这样我们就可以进项删除操作了，删除pos之后，再将n赋值给pos， 整个链表结构是完整的。 pos：宿主结构体类型指针。 n：宿主结构体临时指针。 head：链表头。 member：宿主结构中链表的成员变量。	void Data_list_del_2() { //删除链表中元素 struct student *n = NULL; struct student *pos = NULL; list_for_each_entry_safe(pos,n,&g_list,list) { /*list_del与list_del_init都是删除节点，但是list_del_init属于安全删除*/ //list_del(&pos->list); list_del_init(&pos->list); free(pos); } return; }
list_for_each_entry_safe_continue	#define list_for_each_entry_safe_continue(pos, n, head, member) \ for (pos = list_entry(pos->member.next, typeof(*pos), member), \ n = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.next, typeof(*n), member))	同list_for_each_entry_continue，属于安全函数，遍历的时候节点看可以进行操作，例如删除。
list_for_each_entry_safe_reverse	#define list_for_each_entry_safe_reverse(pos, n, head, member) \ for (pos = list_entry((head)->prev, typeof(*pos), member), \ n = list_entry(pos->member.prev, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.prev, typeof(*n), member))	功能与list_for_each_entry_safe类似，属于反向遍历。

平台通用性及移植

通用性

list_head虽然时使用C语言实现的，但是其设置的初衷是使用在linux内核，所以引入了GUN的一些方法，如typeof，该宏是用于获取参数的类型。typeof在windows，freeRtos等平台是不支持，所以在不同平台使用需要做平台适配。

例如在win32下我们可以如下定义：

#define list_for_each_entry(pos, head, member, type) \

for (pos = list_entry((head)->next, type, member); \

&pos->member != (head); \

pos = list_entry(pos->member.next, type, member))

跨平台移植

跨平台移植时list_head的实现只保留C标注，其余GUN的方法我们需要完全使用C标准的方式进行替换。

示例代码
#include "list.h"
#include <string.h>
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>struct list_head g_list;/*头指针*/struct student
{char name[32];int age;struct list_head list;
};int Data_Add(char *name,int age,int len)
{if(name == NULL){printf("NULL......\n");return -1;}struct student *st = malloc(sizeof(struct student));if(st == NULL){printf("malloc failed,reason:%d-%s\n",errno,strerror(errno));return -1;}memcpy(st->name,name,len);st->age = age;INIT_LIST_HEAD(&(st->list));//二选一//头插法//list_add(&(st->list),&g_list);//尾插法list_add_tail(&(st->list),&g_list);return 0;
}//方法1遍历
void Data_list_for_each()
{struct list_head *postion = NULL;struct student *p = NULL;/*参数1:struct list_head结构体指针参数2:头指针*/list_for_each(postion,&g_list){/*参数1：struct list_head结构体指针参数2：链表容器结构体类型，这里即struct student参数3：链表容器中链表的成员变量*///二选一，list_entry的实现内部其实调用了container_ofp = list_entry(postion,struct student,list);//p = container_of(postion,struct student,list);printf("%s-%d\n",p->name,p->age);}return;
}//方法2遍历
void Data_list_for_each_entry()
{struct student *p = NULL;/*参数1：链表容器结构体指针参数2：头指针参数3：链表容器中链表的成员变量*/list_for_each_entry(p,&g_list,list){printf("%s-%d\n",p->name,p->age);}return;
}//从某个节点开始遍历
/*需要与list_prepare_entry(pos,head,member) 配合使用，list_prepare_entry的返回值作为list_for_each_entry_continue的pos
*/
void Data_list_for_each_entry_continue()
{struct student *pos = NULL;struct student *n = NULL;n = list_prepare_entry(pos,&g_list,list);/*list_for_each_entry_safe_continue与list_for_each_entry_continue一样，只不过list_for_each_entry_safe_continue遍历后可以直接操作节点，比如删除。因此带safe的函数多了一个中间的临时变量。*/list_for_each_entry_continue(n,&g_list,list){printf("%s-%d\n",n->name,n->age);}return;
}//方法1反向遍历
void Data_list_for_each_prev()
{struct list_head *postion = NULL;struct student *p = NULL;//参数定义同Data_list_for_each函数list_for_each_prev(postion,&g_list){p = list_entry(postion,struct student,list);printf("%s-%d\n",p->name,p->age);}return;
}//方法2反向遍历
void Data_list_for_each_entry_reverse()
{struct student head;struct student *p = NULL;//参数定义同Data_list_for_each_entry函数list_for_each_entry_reverse(p,&g_list,list){printf("%s-%d\n",p->name,p->age);}return;
}//数据替换1
void Data_list_replace()
{//用liangchaowei替换zhouxingxingstruct student head;struct student *pos = NULL;struct student *data = malloc(sizeof(struct student));if(data == NULL){return ;}memcpy(data->name,"liangchaowei",sizeof("liangchaowei"));data->age = 57;list_for_each_entry(pos,&g_list,list){if(memcmp(pos->name,"zhouxingxing",sizeof("zhouxingxing")) == 0){/*list_replace没有将pos的前驱和后继分开，所以建议使用list_replace_init*///list_replace(&pos->list,&data->list);list_replace_init(&pos->list,&data->list);free(pos);break;}}return;
}//方法1删除
//使用与Data_list_for_each类似的方法进行遍历删除
void Data_list_del_1()
{struct list_head *postion = NULL;struct list_head *tmp = NULL;struct student *p = NULL;list_for_each_safe(postion,tmp,&g_list){p = list_entry(postion,struct student,list);if(memcmp(p->name,"liangchaowei",sizeof("liangchaowei")) == 0){list_del(&p->list);//list_del_init(&p->list);free(p);}}return;
}//方法2删除
//删除节点名为liangchaowei的节点
void Data_list_del_2()
{//删除链表中元素struct student *n = NULL;struct student *pos = NULL;list_for_each_entry_safe(pos,n,&g_list,list){if(memcmp(pos->name,"zhangguorong",sizeof("zhangguorong")) == 0){/*list_del与list_del_init都是删除节点，但是list_del_init属于安全删除*///list_del(&pos->list);list_del_init(&pos->list);free(pos);}}return;
}/*移动节点，将某个第三方节点添加到当前链表上，功能与新增节点相似*/
int Data_list_move(char *name,int age,int len)
{if(name == NULL){printf("NULL......\n");return -1;}struct student *st = malloc(sizeof(struct student));if(st == NULL){printf("malloc failed,reason:%d-%s\n",errno,strerror(errno));return -1;}memcpy(st->name,name,len);st->age = age;INIT_LIST_HEAD(&(st->list));/*相当于将节点进行头部插入到链表*///list_move(&(st->list),&g_list);/*相当于将节点进行尾部插入到链表*/list_move_tail(&(st->list),&g_list);return 0;
}int main()
{int res = -1;INIT_LIST_HEAD(&g_list);//数据添加res =  Data_Add("liudehua",50,sizeof("liudehua"));res &=  Data_Add("zhangxueyou",51,sizeof("zhangxueyou"));res &=  Data_Add("zhourunfa",52,sizeof("zhourunfa"));res &=  Data_Add("zhangxueyou",55,sizeof("zhangxueyou"));res &=  Data_Add("zhouxingxing",56,sizeof("zhouxingxing"));res &=  Data_Add("zhangguorong",60,sizeof("zhangguorong"));if(res != 0){return -1;}//方法1遍历printf("------------list for each-------------------\n\n");Data_list_for_each();//方法2遍历printf("------------list for each entry-------------------\n\n");Data_list_for_each_entry();//方法1反向遍历printf("------------------list for each prev-------------\n\n");Data_list_for_each_prev();//方法2反向遍历printf("---------------list for each entry reverse----------------\n\n");Data_list_for_each_entry_reverse();//从某个节点开始遍历printf("----------------list for each entry continue---------------\n\n");Data_list_for_each_entry_continue();//数据替换printf("-----------------replace--------------\n\n");Data_list_replace();Data_list_for_each_entry();//数据删除printf("-----------------del 1--------------\n\n");Data_list_del_1();Data_list_for_each_entry();//数据删除printf("-----------------del 2--------------\n\n");Data_list_del_2();Data_list_for_each();//节点移动printf("-----------------move--------------\n\n");Data_list_move("linqingxia",61,sizeof("linqingxia"));Data_list_move("gutianle",62,sizeof("gutianle"));Data_list_for_each();return 0;
}