6.6.8　链表的遍历

接下来看实现遍历双向循环链表基本操作的宏。

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（）宏已经不再感到陌生了。上面三个遍历链表的宏都类似，接下来看另外一种遍历宏的实现方法。

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结点被释放而造成的断链，这也就体现了该宏的安全机制。也就是说，可以遍历完当前结点后将其删除，同时接着访问下一个结点，遍历完毕后，就只剩下一个头结点。一个最典型的应用是，在多进程编程时候，多个进程在同一个等待队列中，若事件发生时唤醒所有进程，则可以在唤醒后将其依次从等待队列中删除。下面通过一段代码来看这种安全机制的使用。

include＜stdio.h＞

include＜stdlib.h＞

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_headpos，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；

}

运行结果：

root@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（）宏，该宏的代码如下：

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结构在宿主结构中的成员名。接下来通过下面的一段代码来看该宏的具体使用。

include＜stdio.h＞

include＜stdlib.h＞

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_headpos，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；

}

运行结果：

root@ubuntu:/home/paixu/dlist_node#./a

student num：3 student name：Stu3

student num：2 student name：Stu2

student num：1 student name：Stu1

接下来看list.h中与双向循环链表操作有关的最后几个宏的实现。

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结点被释放而造成断链。