介绍了上面的几种基本宏后,对list_entry的理解就容易了。
----------------list_entry()--------------------
list_entry()宏,获取当前list_head链表节点所在的宿主结构项。第一个参数为当前list_head节点的指针,即指向宿主结构项的list_head成员。第二个参数是宿主数据结构的定义类型。第三个参数为宿主结构类型定义中list_head成员名。
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
扩展替换即为:
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
例如,我们要访问foo链表(链表头为head)中首个元素,则如此调用:
list_entry(head->next, struct foo, list);
经过C预处理的文字替换,这一行的内容就成为:
((struct foo *)((char *)(head->next) - (unsigned long)(&((struct foo *)0)->list)))
获取宿主对象指针的原理如上图所示。我们考虑list_head类型成员member相对于宿主结构(类型为type)起始地址的偏移量。对于所有该类型的宿主对象,这个偏移量是固定的。并且可以在假设宿主对象地址值为0,通过返回member成员的地址获得,即等于(unsigned long)(&((type *)0)->member)。这样,将当前宿主对象的"连接件"地址(ptr)减去这个偏移量,得到宿主对象地址,再将它转换为宿主数据结构类型的指针。
需要重申的是,链表头没有被嵌入到宿主对象中,因此对链表头执行宿主对象指针获取操作是没有意义的。
6、遍历
6.1 List-head链表遍历
遍历是双循环链表的基本操作,为此Linux定义了一些宏。
list_for_each对遍历链表中的所有list_head节点,不涉及到对宿主结构的处理。list_for_each实际是一个 for 循环,利用传入的指向list_head结构的指针作为循环变量,从链表头开始(并跳过链表头),逐项向后移动指针,直至又回到链表头。
----------------list_for_each()------------------
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
head为头节点,遍历过程中首先从(head)->next开始,当pos==head时退出,故head节点并没有访问,这和list结构设计有关,通常头节点就是纯粹的list结构,不含有其他有效信息,或者头节点含有其他信息,如内核PCB链表中的头节点为idle任务,但其不参予比较优先级,因此此时头节点只是作为双向链表遍历一遍的检测标志。
为提高遍历速度,还使用了预取。
-----asm-x86_64\processor.h---prefetch()---------
static inline void prefetch(void *x)
{
asm volatile("prefetcht0 %0" :: "m" (*(unsigned long *)x));
}
将x指针作强制类型转换为unsigned long *型,然后取出该内存操作数,送入高速缓存。
----------------__list_for_each()-----------------
#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
list_for_each()有prefetch()用于复杂的表的遍历,而__list_for_each()无prefetch()用于简单的表的遍历,此时表项比较少,无需缓存。
----------------list_for_each_prev()-------------
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
pos = pos->prev)
反向遍历节点
----------------list_for_each_safe()--------------
如果在遍历过程中,包含有删除或移动当前链接节点的操作,由于这些操作会修改遍历指针,这样会导致遍历的中断。这种情况下,必须使用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)
在for循环中n暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。也就是说你可以遍历完当前节点后将其删除,同时可以接着访问下一个节点,遍历完毕后就只剩下一个头节点。这就叫safe。十分精彩。典型用途是多个进程等待在同一个等待队列上,若事件发生时唤醒所有进程,则可以唤醒后将其依次从等待队列中删除。
6.2遍历宿主对象
如果只提供对list_head结构的遍历操作是远远不够的,我们希望实现的是对宿主结构的遍历,即在遍历时直接获得当前链表节点所在的宿主结构项,而不是每次要同时调用list_for_each和list_entry。对此,Linux提供了list_for_each_entry()宏,第一个参数为传入的遍历指针,指向宿主数据结构,第二个参数为链表头,为list_head结构,第三个参数为list_head结构在宿主结构中的成员名。
-------------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))
这是用于嵌套的结构体中的宏:
struct example_struct
{
struct list_head list;
int priority;
... //其他结构体成员
};
struct example_struct *node = list_entry(ptr,struct example_struct,list);
自己分析:对比list_entry(ptr,type,member)可知有以下结果:
其中list相当于member成员,struct example_struct相当于type成员,ptr相当于ptr成员。而list{}成员嵌套于example_struct{}里面。ptr指向example_struct{}中的list成员变量的。在list_entry()作用下,将ptr指针回转指向struct example_struct{}结构体的开始处。
pos当指向外层结构体,比如指向struct example_struct{}的结点,最开始时候,head指向链表结构体struct list_head{}的头结点,头节点不含有有效信息,(head)->next则指向第一个外层结点的内嵌的链表结点struct list_head{} list,由此得出的pos当指向第一个有效结点。member即是指出该 list为其内嵌的结点。
思路:用pos指向外层结构体的结点,用head指向内层嵌入的结构体的结点。用(head)->next,pos->member.next(即:ptr->list.next)来在内嵌的结构体结点链表中遍历。每遍历一个结点,就用list_entry()将内嵌的pos->member.next指针回转为指向该结点外层结构体起始处的指针,并将指针进行指针类型转换为外层结构体型pos。&pos->member! = (head)用pos外层指针引用member即:list成员,与内层嵌入的链表之头结点比较来为循环结束条件。
当遍历到头节点时,此时并没有pos这样一个type类型数据指针,而是以member域强制扩展了一个type类型的pos指针,此时其member域的地址就是head指针所指向的头节点,遍历结束,头节点的信息没有被访问。
-------------list_for_each_entry_reverse()-------
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), m+ember); \
prefetch(pos->member.prev), &pos->member != (head); \
pos = list_entry(pos->member.prev, typeof(*pos), member))
分析类似上面。
---------------list_prepare_entry()---------------
如果遍历不是从链表头开始,而是从已知的某个pos结点开始,则可以使用list_for_each_entry_continue(pos,head,member)。但为了确保pos的初始值有效,Linux专门提供了一个list_prepare_entry(pos,head,member)宏,如果pos有值,则其不变;如果没有,则从链表头强制扩展一个虚pos指针。将它的返回值作为list_for_each_entry_continue()的pos参数,就可以满足这一要求。
内核中的list_prepare_entry()的代码:
#define list_prepare_entry(pos, head, member) \
((pos) ? : list_entry(head, typeof(*pos), member))
分析:
:前面是个空值,即:若pos不为空,则pos为其自身。等效于:
(pos)? (pos): list_entry(head,typeof(*pos),member)
注意内核格式::前后都加了空格。
------------list_for_each_entry_continue()--------
内核中的list_for_each_entry_continue()的代码:
#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))
此时不是从头节点开始遍历的,但仍然是以头节点为结束点的,即没有遍历完整个链表。
要注意并不是从pos开始的,而是从其下一个节点开始的,因为第一个有效pos是从pos->member.next扩展得到的。
-------------list_for_each_entry_safe()-----------
它们要求调用者另外提供一个与pos同类型的指针n,在for循环中暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。
内核中的注释与源代码:
#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_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))
7、如何使用Linux中的双循环链表
本文例子来自,只是对其中注释部分作了翻译。
#include
#include
#include "list.h"
struct kool_list{
int to;
struct list_head list;
int from;
};
int main(int argc, char **argv){
struct kool_list *tmp;
struct list_head *pos, *q;
unsigned int i;
struct kool_list mylist;
INIT_LIST_HEAD(&mylist.list);
for(i=5; i!=0; --i){
tmp= (struct kool_list *)malloc(sizeof(struct kool_list));
printf("enter to and from:");
scanf("%d %d", &tmp->to, &tmp->from);
list_add(&(tmp->list), &(mylist.list));
}
printf("\n");
printf("traversing the list using list_for_each()\n");
list_for_each(pos, &mylist.list){
tmp= list_entry(pos, struct kool_list, list);
printf("to= %d from= %d\n", tmp->to, tmp->from);
}
printf("\n");
printf("traversing the list using list_for_each_entry()\n");
list_for_each_entry(tmp, &mylist.list, list)
printf("to= %d from= %d\n", tmp->to, tmp->from);
printf("\n");
printf("deleting the list using list_for_each_safe()\n");
list_for_each_safe(pos, q, &mylist.list){
tmp= list_entry(pos, struct kool_list, list);
printf("freeing item to= %d from= %d\n", tmp->to, tmp->from);
list_del(pos);
free(tmp);
}
return 0;
}
阅读(2129) | 评论(0) | 转发(1) |