分类： C/C++
2012-11-21 23:18:15
一、list_for_each
1.list_for_each原型
#define list_for_each(pos, head) \
for (pos = (head)->next, prefetch(pos->next); pos !=
(head); \
pos = pos->next, prefetch(pos->next))
它实际上是一个 for 循环，利用传入的pos 作为循环变量，从表头 head开始，逐项向后（next方向）移动 pos ，直至又回到 head （prefetch()
可以不考虑，用于预取以提高遍历速度）。
注意：此宏必要把list_head放在数据结构第一项成员，至此，它的地址也就是结构变量的地址。如果不要list_head放在数据结构第一项成员，一般就要配合list_entry使用。
二、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_for_each_entry遍历head 下面挂接的类型为typeof(*pos)的childs结构体们,当然每个child结构体包含struct list_head node之类相似的双向链表list_head类型项,就这样通过循环pos将依次指向双向链表上的各个child.(member就是child类型中 被定义的变量名)
#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))
说白了define list_for_each_entry 就是一个for循环。。。。
在 [net/core/netfilter.c] 的
nf_register_sockopt() 函数中有这么一段话：
…… struct list_head *i; …… list_for_each(i, &nf_sockopts) { struct
nf_sockopt_ops *ops = (struct nf_sockopt_ops *)i; …… } ……
函 数首先定义一个
(struct list_head *) 指针变量i，然后调用 list_for_each(i,&nf_sockopts) 进行遍历。在
[include/linux/list.h] 中， list_for_each() 宏是这么定义的：
#define list_for_each(pos, head) \ for (pos = (head)->next,
prefetch(pos->next); pos != (head); \ pos = pos->next,
prefetch(pos->next))
它实际上是一个 for 循环，利用传入的 pos 作为循环变量，从表头 head 开始，逐项向后（next 方向）移动 pos，直至又回到 head（prefetch() 可以不考虑，用于预取以提高遍历速度
）。
那 么在
nf_register_sockopt() 中实际上就是遍历 nf_sockopts 链表。为什么能直接将获得的 list_head 成员变量地址当成 struct nf_sockopt_ops 数据项变量的地址呢？我们注意到在
struct nf_sockopt_ops 结构中，list是其中的第一项成员，因此，它的地址也就是结构变量的地址。更规范的获得数据变量地址的用法应该是：
struct nf_sockopt_ops *ops = list_entry(i, struct nf_sockopt_ops, list);
大多数情况下，遍历链表的时候都需要获得链表节点数据项，也就是说 list_for_each()和list_entry() 总是同时使用。对此 Linux 给出了一个 list_for_each_entry() 宏：
#define list_for_each_entry(pos, head, member) ……
与 list_for_each() 不同，这里的pos是数据项结构指针类型，而不是 (struct list_head *)。nf_register_sockopt() 函数可以利用这个宏而设计得更简单：
…… struct nf_sockopt_ops *ops; list_for_each_entry(ops,&nf_sockopts,list){
…… } ……
某 些应用需要反向遍历链表，Linux
提供了 list_for_each_prev() 和 list_for_each_entry_reverse() 来完成这一操作，使用方法和上面介绍的
list_for_each()、list_for_each_entry() 完全相同。
如果遍历不是从链表头开始，而是从已
知的某个节点 pos 开始，则可以使用 list_for_each_entry_continue(pos,head,member)。有时还会出现这种需求，即经过一系列计算后，如果 pos 有值，则从 pos 开始遍历，如果没有，则从链表头开始，为此，Linux 专门提供了一个 list_prepare_entry(pos,head,member) 宏，将它的返回值作为
list_for_each_entry_continue() 的 pos 参数，就可以满足这一要求。
4. 安全性考虑
在并发执行的环境下，链表操作通常都应该考虑同步安全性问题，为了方便，Linux 将这一操作留给应用自己处理。Linux 链表自己考虑的安全性主要有两个方面：
a) list_empty() 判断
基 本的
list_empty() 仅以头指针的 next 是否指向自己来判断链表是否为空，Linux 链表另行提供了一个 list_empty_careful() 宏，它同时判断头指针的 next 和 prev，仅当两者都指向自己时才返回真。这主要是为了应付另一个 cpu 正在处理同一个链表而造成 next、prev 不一致的情况。但代码注释也承认，这一安全保障能力有限：除非其他 cpu 的链表操作只有 list_del_init()，否则仍然不能保证安全，也就是说，还是需要加锁保护。
b) 遍历时节点删除
前面介 绍了用于链表遍历的几个宏，它们都是通过移动 pos 指针来达到遍历的目的。但如果遍历的操作中包含删除 pos 指针所指向的节点，pos 指针的移动就会被中断，因为 list_del(pos) 将把 pos 的 next、prev 置成 LIST_POSITION2 和 LIST_POSITION1 的特殊值。
当然，调用者完全可以自己缓存 next 指针使遍历操作能够连贯起来，但为了编程的一致性，Linux 链表仍然提供了两个对应于基本遍历操作的 "_safe" 接口：list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos,
n, head, member)，它们要求调用者另外提供一个与 pos 同类型的指针n，在 for 循环中暂存 pos 下一个节点的地址，避免因 pos 节点被释放而造成的断链。
参考资料：
http://blog.163.com/kmustchenb@126/blog/static/1109057652011112221829306/
Normal 0 7.8 磅 0 2 false false false EN-US ZH-CN X-NONE /* Style Definitions */ table.MsoNormalTable {mso-style-name:普通表格; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.5pt; mso-bidi-font-size:11.0pt; font-family:"Calibri","sans-serif"; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi; mso-font-kerning:1.0pt;}
