在开端写linux内核双向循环链表之前，我一直在想我要不要用长篇大论的文字来描绘linux内核双向循环链表呢?经过仔细的考虑之后，我否决了用单调的文字向读者描绘linux内核双向循环链表的主意，因为关于编程言语来说我信任大多数的读者都应该不喜爱面临单调的文字，更喜爱看到代码，一同那也是读者阅览文字后想要完结的东西，所以我决议在这儿选用代码加上恰当的文字描绘的办法来进行解说，这就使得我不行能用一篇的篇幅来解说完，所以会写两篇文章来解说这个知识点。期望读者能够坚持看完，学会今后在应用程序中写双向循环链表时，不必再自己去编写那些费事的操作函数，充分利用linux内核里现已供给的遍历链表的操作函数。
特此阐明：我会把我在文章中编写代码时分用到的头文件list.h上传到我的空间，免积分下载，有需求的读者能够自己去下载，当然也能够自己上网下载或许从自己装置的linux体系中得到。
懂了linux内核里双向循环链表的完结办法之后咱们不得不惊叹它的完结是如此的奇妙，为了读者能够顺畅的和我一同走完这次linux内核双向循环链表之旅，在此之前我特别为之写了一篇《C言语的那些小秘密之字节对齐》的文章，假如你发现在本篇文章中有些当地不明白的时分，你能够回过去看看《C言语的那些小秘密之字节对齐》再来接着持续往下持续全文的阅览。
因为咱们在linux内核中有很多的数据结构都需求用到双向循环链表。若再选用以往那种传统双向循环链表的完结办法，咱们不得不为这些数据结构保护各自的链表，而且为每个链表都要规划刺进、查找、删去等操作函数。这是因为咱们在惯例链表中用来保持链表的next和prev指针都是指向对应类型的目标，因而一种数据结构的链表操作函数不能用于操作其它数据结构的链表。为了处理这个问题，在Linux内核中选用了一种与类型无关的双向循环链表完结办法，它的完结使得咱们不必再为每个链表都要规划刺进、查找、删去等相关的操作函数。其完结办法便是将结构体中的指针prev和next从详细的数据结构中提取出来，构成一种通用的双向循环链表数据结构list_head。假如需求结构某类目标的特定链表，则只需求在其结构体中界说一个类型为list_head类型的成员，经过这个界说的list_head类型的成员将这类目标连接起来，构成所需的双向循环链表，然后经过通用链表函数对其进行操作。清楚明了是咱们只需编写通用链表函数，就可结构和操作不同目标的链表，而无需为每个创立的双向循环链表编写专用函数，然后大大的完结了代码的重用。
下面咱们就真实的开端咱们的linux内核双向循环链表之旅。读者能够从网上下载一个linux内核双向循环链表的list.h的头文件，值得留意的便是因为内核版别的不同或许下载的头文件有些差异，可是这个并不影响咱们关于它的解说。读者能够先看完全文后再着手也不迟，用list.h头文件来完结咱们的双向循环链表。为了便于解说，咱们就依照list.h头文件中代码的先后顺序进行解说。
弥补一点：(注：假如读者看不明白下面这段代码，能够持续往下看，不会影响接下来的学习，在接下来的部分还会有解说，这部分代码是我写完全文后添加的，因为一开端我运用的是#define list_entry(ptr, type, member) ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))而不是#define list_entry(ptr, type, member) container_of(ptr, type, member))
[cpp] view plaincopy#define container_of(ptr, type, member) ( { \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr – offsetof(type,member) ); } )
经过typeof( ((type *)0)->member )得到member成员的类型，将指向member的指针ptr赋值给__mptr，__mptr指针的类型为member数据成员的类型。经过(char *)__mptr将__mptr强制转换为char指针，之后再减去offsetof(type,member)，即可得到宿主结构体的指针。假如有对offsetof(type,member)不明白的能够参阅我之前写的一篇《C言语的那些小秘密之字节对齐》。
首要看看list_head结构的完结。
[html] view plaincopystruct list_head {
struct list_head *next, *prev;
};
在linux内核双向循环链表中咱们用以上list_head类型界说一个变量，将其作为一个成员嵌入到宿主结构内。什么是宿主结构体呢?便是咱们创立的双向循环链表的结构体。能够将链表结构放在宿主结构内的任何当地，当然也能够为链表结构取任何姓名，然后咱们就能够用list_head中的成员和相对应的处理函数来对链表进行遍历操作，假如想得到宿主结构的指针，运用咱们能够运用list_entry计算出来，先别急着想知道list_entry什么，咱们会在下面解说，接着往下看。
在宿主结构体中界说了list_head之后接下来当然是要对咱们界说的头结点进行初始化作业，初始化的完结办法能够有以下两种办法。
[html] view plaincopy#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
剖析上面的代码可知，咱们在代码中运用list_head界说了一个头结点之后，就要对界说的头结点进行初始化作业，能够运用INIT_LIST_HEAD(ptr)宏进行初始化，或许咱们无需自己界说直接运用LIST_HEAD(name)宏即可完结界说和初始化的作业。头结点的初始化作业完结了之后接下来的作业当然是要添加节点了。
[html] view plaincopystatic 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()的功用是在两个非空结点中刺进一个结点，值得留意的是new、prev、next均不能为空值。当然prev能够等于next，此刻表明在只含头节点的链表中刺进新节点。知道了__list_add()函数的完结咱们接下来当然也要看看list_add()和list_add_tail()的完结。
[html] view plaincopystatic inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
看了上面的完结办法咱们知道他们都是调用底层的__list_add()来完结的。看看在__list_add()函数里边传递不同的参数咱们就能完结不同的添加节点的办法。__list_add()函数前面的双划线一般表明这是一个底层函数，供其他的模块调用。
第一个list_add()传递的参数完结的是在head和head->next两指针所指向的结点之间刺进new所指向的结点。即便是在head指针的后边刺进一个new所指向的结点。Head并非一定为头结点。假如咱们的链表只含有一个头节点时，上面的__list_add(new, head, head->next)依然建立。
第二个list_add_tail()其功用是在结点指针head所指向结点的前面刺进new所指向的结点。当假如head指向的是头结点，那么就相当于在尾结点后边添加一个new所指向的结点。在这个函数里值得留意的是head->prev不能为空，假如head为头结点，那么head->prev要指向一个数值，一般为指向尾结点，构成循环链表。
提到这儿或许有的读者现已刻不容缓的想看看代码了，那咱们就用linux内核里的list.h在应用层来写出咱们的代码。
[html] view plaincopy#include
#include
#include "list.h"
typedef struct _stu
{
char name[20];
int num;
struct list_head list;
}stu;
int main()
{
stu *pstu;
stu *tmp_stu;
struct list_head stu_list;
struct list_head *pos;
int i = 0;
INIT_LIST_HEAD(&stu_list);
pstu = malloc(sizeof(stu)*5);
for(i=0;i<5;i++)
{
sprintf(pstu[i].name,"Stu%d",i+1);
pstu[i].num = i+1;
list_add( &(pstu[i].list), &stu_list);
}
list_for_each(pos,&stu_list)
{
tmp_stu = list_entry(pos, stu, list);
printf("student num: %d\tstudent name: %s\n",tmp_stu->num,tmp_stu->name);
}
free(pstu);
return 0;
}
运转成果为：
[html] view plaincopyroot@ubuntu:/home/paixu/dlist_node# ./a
student num: 5 student name: Stu5
student num: 4 student name: Stu4
student num: 3 student name: Stu3
student num: 2 student name: Stu2
student num: 1 student name: Stu1
看看上面的代码，咱们做的根本作业都有那些呢?
1、界说了一个宿主结构体stu，而且在宿主结构体中咱们界说了一个struct list_head 类型的list变量;
2、界说一个头结点而且对其进行初始化作业;
3、对界说的一个宿主结构体变量请求内存空间;
4、对请求的宿主结构体变量初始化和添加到以stu_list为头结点的链表中。
在上面值得留意的便是list_for_each()和list_entry()，咱们会在接下来的部分解说，读者在这儿只需求知道它们两个在此合在一同的效果便是打印出宿主结构stu中每个数据。sprintf()的运用就不在这儿解说了，很简单，信任读者猜都能够猜出它的功用。读者假如一开端对上面的文字描绘部分有什么疑问或许不解的现在看了代码的完结应该都懂了，list_add_tail()的运用和list_add()相似，读者能够自己修正代码完结。假如一开端关于list_add()不太了解的读者，现在关于list_add()的了解现在能够参阅运转成果和上面的文字描绘部分。
咱们接着往下看。
[html] view plaincopystatic inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
在prev和next指针所指向的结点之间，两者相互所指。其实也便是prev为待删去的结点的前面一个结点，next为待删去的结点的后边一个结点。
[html] view plaincopystatic inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
删去entry所指的结点，一同将entry所指向的结点指针域封死。在这儿值得留意的是LIST_POISON1、LIST_POISON2。它们在list.h中的宏界说如下：
#define LIST_POISON1 ((void *) 0x00100100)
#define LIST_POISON2 ((void *) 0x00200200)
对LIST_POISON1、LIST_POISON2的阐明，Linux 内核中有这么一句话：These are non-NULL pointers that will result in page faults under normal circumstances，used to verify that nobody uses non-initialized list entries。也便是说它们并不是空指针，可是拜访这样的指针在正常情况下是会导致犯错的。其实依照咱们一般的思路都是把entry->next 和entry->prev 赋值为NULL，使得不行以经过该节点进行拜访。可是在这儿运用了一种特别的办法。留意：我在linux环境下以上宏的值不必修正是不会犯错的，可是在vc下就会犯错，不允许运用那两个值，所以要修正为NULL。
[html] view plaincopystatic inline void list_del_init(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
INIT_LIST_HEAD(entry);
}
以上函数的功用为删去entry所指向的结点，一同调用LIST_INIT_HEAD()把被删去结点为作为链表头构建一个新的空双循环链表。
[html] view plaincopy#include
#include
#include "list.h"
typedef struct _stu
{
char name[20];
int num;
struct list_head list;
}stu;
int main()
{
stu *pstu;
stu *tmp_stu;
struct list_head stu_list;
struct list_head *pos;
int i = 0;
INIT_LIST_HEAD(&stu_list);
pstu = malloc(sizeof(stu)*5);
for(i=0;i<5;i++)
{
sprintf(pstu[i].name,"Stu%d",i+1);
pstu[i].num = i+1;
list_add( &(pstu[i].list), &stu_list);
}
list_del(&(pstu[3].list));
printf("运用list_del()删去pstu[3]\n");
list_for_each(pos,&stu_list)
{
tmp_stu = list_entry(pos, stu, list);
printf("student num: %d\tstudent name: %s\n",tmp_stu->num,tmp_stu->name);
}
list_del_init(&(pstu[2].list));
printf("运用list_del_init()删去pstu[2]\n");
list_for_each(pos,&stu_list)
{
tmp_stu = list_entry(pos, stu, list);
printf("student num: %d\tstudent name: %s\n",tmp_stu->num,tmp_stu->name);
}
free(pstu);
return 0;
}
运转成果为：
[cpp] view plaincopyroot@ubuntu:/home/paixu/dlist_node# ./a
运用list_del()删去pstu[3]
student num: 5 student name: Stu5
student num: 3 student name: Stu3
student num: 2 student name: Stu2
student num: 1 student name: Stu1
运用list_del_init()删去pstu[2]
student num: 5 student name: Stu5
student num: 2 student name: Stu2
student num: 1 student name: Stu1
看了代码的运用之后咱们再去了解之前的解说就要轻松多了。读者能够结合上面相应的文字描绘再剖析下代码，以加深形象。接着往下看，坚持看完本篇博客的最终两个函数。
[html] view plaincopystatic inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del(list->prev, list->next);
list_add(list, 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_move()和list_move_tail()，第一个list_move()函数的功用是把list移至head和head->next两个指针所指向的结点之间。而第二个list_move_tail()函数的功用是把list移至head和head->prev两个指针所指向的结点之间。假如读者觉得这样说不是太详细的话，那么咱们来看看下面的代码。
[cpp] view plaincopy#include
#include
#include "list.h"
typedef struct _stu
{
char name[20];
int num;
struct list_head list;
}stu;
int main()
{
stu *pstu;
stu *tmp_stu;
struct list_head stu_list;
struct list_head *pos;
int i = 0;
INIT_LIST_HEAD(&stu_list);
pstu = malloc(sizeof(stu)*5);
for(i=0;i<5;i++)
{
sprintf(pstu[i].name,"Stu%d",i+1);
pstu[i].num = i+1;
list_add( &(pstu[i].list), &stu_list);
}
list_move(&(pstu[3].list),&stu_list);
printf("把pstu[3]移至head和head->next两个指针所指向的结点之间\n");
list_for_each(pos,&stu_list)
{
tmp_stu = list_entry(pos, stu, list);
printf("student num: %d\tstudent name: %s\n",tmp_stu->num,tmp_stu->name);
}
list_move_tail(&(pstu[2].list),&stu_list);
printf("把pstu[2]移至head和head->prev两个指针所指向的结点之间\n");
list_for_each(pos,&stu_list)
{
tmp_stu = list_entry(pos, stu, list);
printf("student num: %d\tstudent name: %s\n",tmp_stu->num,tmp_stu->name);
}
free(pstu);
return 0;
}
运转成果为：
[cpp] view plaincopyroot@ubuntu:/home/paixu/dlist_node# ./a
把pstu[3]移至head和head->next两个指针所指向的结点之间
student num: 4 student name: Stu4
student num: 5 student name: Stu5
student num: 3 student name: Stu3
student num: 2 student name: Stu2
student num: 1 student name: Stu1
把pstu[2]移至head和head->prev两个指针所指向的结点之间
student num: 4 student name: Stu4
student num: 5 student name: Stu5
student num: 2 student name: Stu2
student num: 1 student name: Stu1
student num: 3 student name: Stu3
在此之前先说一个留意点，避免部分读者认为成果有误，pstu[]中的下标是从0开端的，所以pstu[3]对应的是stu4。
这篇先讲到这儿，余下的咱们在下面一篇《C言语的那些小秘密之链表(四)》中持续讲。因为自己水平有限，博客中的不当或过错之处在所难免，殷切期望读者批评指正。一同也欢迎读者一起讨论相关的内容，假如愿意沟通的话请留下你名贵的定见。
