大多数的读者在学习编程言语的时分都不喜爱那些单调的文字描绘，包含我自己在开端学习编程的时分也是这样，关于代码的热心远远高于文字，所以我在我写东西的时分也不喜爱用单调的文字描绘来向读者解说，更喜爱用代码加上恰当的文字描绘的办法进行解说，因为有些东西或许用单调的文字描绘半响还不如实实在在的给读者呈现出一段简略的代码，让读者了解得愈加的透彻些。可是并不是说文字描绘就没用，文字描绘也很重要，仅仅绝大部分读者都愈加的期望直接到达终究的效果，都想越过那些中心的过程。接下来咱们接着上一篇博客《C言语的那些小秘密之链表(三)》的内容持续解说linux内核双向循环链表。[cpp] view plaincopystatic inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
static inline int list_empty_careful(const struct list_head *head)
{
struct list_head *next = head->next;
return (next == head) && (next == head->prev);
}
list_empty()函数和list_empty_careful()函数都是用来检测链表是否为空的。可是稍有差异的便是第一个链表运用的检测办法是判别表头的结点的下一个结点是否为其自身，假如是则回来为true，不然回来false。第二个函数运用的检测办法是判别表头的前一个结点和后一个结点是否为其自身，假如一起满意则回来false，不然回来值为true。说多了或许读者就会没耐性了，那么接下来我来看看下面的代码。
[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);
}
if(list_empty(&stu_list))
printf("运用list_empty()检测，链表为空\n");
else
printf("运用list_empty()检测，链表非空\n");
if(list_empty_careful(&stu_list))
printf("运用list_empty_careful()检测，链表为空\n");
else
printf("运用list_empty_careful()检测，链表非空\n");
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
运用list_empty()检测，链表非空
运用list_empty_careful()检测，链表非空
看看代码就知道怎么运用了，接下来看看链表的组成。
[html] view plaincopystatic inline void __list_splice(struct list_head *list,
struct list_head *head)
{
struct list_head *first = list->next;
struct list_head *last = list->prev;
struct list_head *at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;
}
这个当地我觉得最好的办法便是运用图示来进行解说，直观易懂，假如用文字描绘半响还不如读者看一眼图。
将一个链表刺进到别的一个链表中。不作链表是否为空的查看，由调用者默许确保。因为每个链表只需一个头节点，将空链表刺进到别的一个链表中是没有意义的。但被刺进的链表可所以空的。
[cpp] view plaincopystatic inline void list_splice(struct list_head *list, struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head);
}
在这种情况下会丢掉list所指向的头结点，因为两个链表有两个头结点，所以咱们有必要要去掉其间一个头结点。只需list非空链，head无任何约束，该函数就能完成链表的兼并。
[cpp] view plaincopystatic inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list)) {
__list_splice(list, head);
INIT_LIST_HEAD(list);
}
}
以上函数的功用是将一个链表list的有用信息兼并到别的一个链表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,*pstu2;
stu *tmp_stu;
struct list_head stu_list,stu_list2;
struct list_head *pos;
int i = 0;
INIT_LIST_HEAD(&stu_list);
INIT_LIST_HEAD(&stu_list2);
pstu = malloc(sizeof(stu)*3);
pstu2 = malloc(sizeof(stu)*3);
for(i=0;i<3;i++)
{
sprintf(pstu[i].name,"Stu%d",i+1);
sprintf(pstu2[i].name,"Stu%d",i+4);
pstu[i].num = i+1;
pstu2[i].num = i+4;
list_add( &(pstu[i].list), &stu_list);
list_add( &(pstu2[i].list), &stu_list2);
}
printf("stu_list 链表\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);
}
printf("stu_list2 链表\n");
list_for_each(pos,&stu_list2)
{
tmp_stu = list_entry(pos, stu, list);
printf("student num: %d\tstudent name: %s\n",tmp_stu->num,tmp_stu->name);
}
printf("stu_list链表和stu_list2 链表兼并今后\n");
list_splice(&stu_list2,&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
stu_list 链表
student num: 3 student name: Stu3
student num: 2 student name: Stu2
student num: 1 student name: Stu1
stu_list2 链表
student num: 6 student name: Stu6
student num: 5 student name: Stu5
student num: 4 student name: Stu4
stu_list链表和stu_list2 链表兼并今后
student num: 6 student name: Stu6
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
有了直观的代码和运转成果，了解起来也愈加的简单了。
有了上面的这些操作，可是咱们还一向没有讲到咱们终究所关怀的宿主结构，那么接下来咱们一起来看看咱们该怎么取出宿主结构的指针呢?这也是我以为linux内核双向循环链表完成最为奇妙的当地了。
[cpp] view plaincopy#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
看看上面的代码，发现一个很熟悉的身影(unsigned long)(&((type *)0)->member))，这个我在前一篇博客《C言语的那些小秘密之字节对齐》中现已解说过了，多以在此就不再做过多的解说，假如有不理解的读者能够回过去看看解说再回过来阅览。经过(unsigned long)(&((type *)0)->member))咱们得出了成员变量member的偏移量，而ptr为指向member的指针，因为指针类型不同的原因，所以咱们再非有必要先进行(char*)的转化之后再进行核算。所以咱们用ptr减去member的偏移量就得到了宿主结构体的指针，这便是一个十分奇妙的当地，这也就使得linux内核双向循环链表能够差异于传统链表的关键地点。或许看到这儿的时分读者现已感觉十分的单调了，可是别抛弃，坚持看完，因为尽管这样的解说单调了点，可是十分有用。所以坚持坚持吧!
[cpp] view plaincopy#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
pos = pos->prev)
遍历是双循环链表的根本操作，head为头节点，遍历过程中首先从(head)->next开端，当pos==head时退出，故head节点并没有拜访，这和链表的结构设计有关，一般头节点都不含有其它有用信息，因而能够把头节点作为双向链表遍历一遍的检测标志来运用。在list_for_each宏中读者或许发现一个比较生疏的面孔，咱们在此就不将prefetch展开了解说了，有爱好的读者能够自己查看下它的完成，其功用是预取内存的内容，也便是程序告知CPU哪些内容或许立刻用到，CPU预先其取出内存操作数，然后将其送入高速缓存，用于优化，是的履行速度更快。接下来的__list_for_each()宏和list_for_each_prev()宏就不在此做逐个的解说了，和list_for_each()宏相似。 便是遍历的方向有所改动或许不运用预取。
经过上面的解说和前面那么多的代码，信任读者这个时分关于list_for_each()现已不再感到生疏了。上面的但三个遍历链表的宏都相似，持续往下看。
[cpp] view plaincopy#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_safe()宏也同样是用于遍历的，不同的是里面多出了一个n暂存pos下一个节点的地址，防止了因为pos节点被开释而形成的断链，这也就表现出了safe。也便是说你能够遍历完当时节点后将其删去，一起能够接着拜访下一个节点，遍历完毕后就只剩余一个头节点。当然这有一个最为典型的运用，那便是咱们在多进程编程时分，多个进程等候在同一个等候行列上，若事情产生时唤醒一切进程，则能够唤醒后将其顺次从等候行列中删去。
[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,*n;
int i = 0;
INIT_LIST_HEAD(&stu_list);
pstu = malloc(sizeof(stu)*3);
for(i=0;i<3;i++)
{
sprintf(pstu[i].name,"Stu%d",i+1);
pstu[i].num = i+1;
list_add( &(pstu[i].list), &stu_list);
}
printf("经过list_for_each_safe()遍历运用list_del(pos)删去结点前\n");
list_for_each_safe(pos, n, &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(pos);
}
printf("经过list_for_each()遍历运用list_del(pos)删去结点后\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;
}
运转成果为：
[html] view plaincopyroot@ubuntu:/home/paixu/dlist_node# ./a
经过list_for_each_safe()遍历运用list_del(pos)删去结点前
student num: 3 student name: Stu3
student num: 2 student name: Stu2
student num: 1 student name: Stu1
经过list_for_each()遍历运用list_del(pos)删去结点后
读者能够结合运转成果再去阅览上面的文字描绘部分。
假如只供给对list_head结构的遍历操作是远远不够的，咱们期望完成的是对宿主结构的遍历，即在遍历时直接取得当时链表节点地点的宿主结构项，而不是每非有必要一起调用list_for_each()和list_entry()。为此Linux特别供给了list_for_each_entry()宏来完成
[cpp] view plaincopy#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
第一个参数为传入的遍历指针，指向宿主数据结构，第二个参数为链表头，为list_head结构，第三个参数为list_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,*n;
int i = 0;
INIT_LIST_HEAD(&stu_list);
pstu = malloc(sizeof(stu)*3);
for(i=0;i<3;i++)
{
sprintf(pstu[i].name,"Stu%d",i+1);
pstu[i].num = i+1;
list_add( &(pstu[i].list), &stu_list);
}
list_for_each_entry(tmp_stu, &stu_list, 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: 3 student name: Stu3
student num: 2 student name: Stu2
student num: 1 student name: Stu1
假如读者一开端关于文字描绘感到生疏的话，那么就再次结合代码去阅览。
接下来再来看看最终几个。
[html] view plaincopy#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member); \
prefetch(pos->member.prev), &pos->member != (head); \
pos = list_entry(pos->member.prev, typeof(*pos), member))
#define list_prepare_entry(pos, head, member) \
((pos) ? : list_entry(head, typeof(*pos), member))
#define list_for_each_entry_continue(pos, head, member) \
for (pos = list_entry(pos->member.next, typeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
#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相似，仅仅其间略有不同，list_prepare_entry()中含有prefetch()，它的效果在上面现已解说，有什么疑问能够回来去阅览下，在此不再做过多的解说;list_for_each_entry_continue()和list_for_each_entry()的差异主要是list_for_each_entry_continue()能够不从链表头开端遍历，而是从已知的某个pos结点的下一个结点开端遍历。在某些时分假如不是从头结点开端遍历，那么为了确保pos的初始值有用，有必要运用list_prepare_entry()。其意义便是假如pos非空，那么pos的值就为其自身，假如pos为空，那么就从链表头强制扩展一个虚pos指针，读者自己剖析list_prepare_entry()的完成就理解了。list_for_each_entry_safe()要求调用者别的供给一个与pos同类型的指针n，在for循环中暂存pos下一个节点的宿主结构体的地址，防止因pos节点被开释而形成的断链。
到此咱们linux内核双向循环链表的旅程就完毕了，下一篇咱们将开端一个新的旅程。因为自己水平有限，博客中的不当或过错之处在所难免，殷切期望读者批评指正。一起也欢迎读者一起讨论相关的内容，假如愿意沟通的话请留下你名贵的定见。
