【数据结构】详解Linux内核之双向循环链表
【摘要】: 本文详解了内核中面向对象的list结构的原理,以及如何以list为内嵌对象来构造自己的链表结构,如何从内嵌list对象获得自定义的对象指针;探讨了各种宏或者函数的详细使用方法及怎样以通用list结构来操作自定义对象。 【关键字】:双向循环链表,list,list_entry,typeof,containerof,list_for_each,list_for_each_entry 1、双循环链表传统实现 1、双循环链表传统实现 2、Linux内核中双循环链表实现 list_head结构 在Linux内核中的双循环链表实现方式下: 1. list_head类型的变量作为一个成员嵌入到宿主数据结构内; 2. 可以将链表结构放在宿主结构内的任何地方; 3. 可以为链表结构取任何名字; 4. 宿主结构可以有多个链表结构; 5. 用list_head中的成员和相对应的处理函数来对链表进行遍历; 6. 如果想得到宿主结构的指针,使用list_entry可以算出来。
--LIST_HEAD_INIT()--LIST_HEAD()--INIT_LIST_HEAD()------ #define LIST_HEAD_INIT(name) { &(name),&(name) } #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name) 需要注意的是,Linux 的每个双循环链表都有一个链表头,链表头也是一个节点,只不过它不嵌入到宿主数据结构中,即不能利用链表头定位到对应的宿主结构,但可以由之获得虚拟的宿主结构指针。 LIST_HEAD()宏可以同时完成定义链表头,并初始化这个双循环链表为空。 静态定义一个list_head 类型变量,该变量一定为头节点。name为struct list_head{}类型的一个变量,&(name)为该结构体变量的地址。用name结构体变量的始地址将该结构体变量进行初始化。 #define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr); (ptr)->prev = (ptr); } while (0) 动态初始化一个已经存在的list_head对象,ptr为一个结构体的指针,这样可以初始化堆栈以及全局区定义的list_head对象。ptr使用时候,当用括号,(ptr),避免ptr为表达式时宏扩展带来的异常问题。此宏很少用于动态初始化内嵌的list对象,主要是链表合并或者删除后重新初始化头部。若是在堆中申请了这个链表头,调用INIT_LIST_HEAD()宏初始化链表节点,将next和prev指针都指向其自身,我们就构造了一个空的双循环链表。 2.6内核中内联函数版本如下: 4、通用链表操作接口 上述三个函数实现了添加一个节点的任务,其中__list_add()为底层函数,“__”通常表示该函数是底层函数,供其他模块调用,此处实现了较好的代码复用,list_add和list_add_tail虽然原型一样,但调用底层函数__list_add时传递了不同的参数,从而实现了在head指向节点之前或之后添加新的对象。 4.2删除节点 删除entry所指的结点,同时将entry所指向的结点指针域封死。 4.3移动节点 删除了list所指向的结点,将其插入到head所指向的结点的前面,如果head->prev指向链表的尾结点的话,就是将list所指向的结点插入到链表的结尾。 4.4链表判空 分析: 2.有两个结点,head指向头结点,head->next,head->prev均指向后面那个结点,即:head->next==head->prev,而head!=head->next,head!=head->prev.所以函数将返回0 3.有三个及三个以上的结点,这是一般的情况,自己容易分析了。 注意:这里empty list是指只有一个空的头结点,而不是毫无任何结点。并且该头结点必须其head->next==head->prev==head 4.5链表合并 Linux还支持两个链表的拼接,提供给用户的具体函数是list_splice和list_splice_init: } 将一个非空链表插入到另外一个链表中。不作链表是否为空的检查,由调用者默认保证。因为每个链表只有一个头节点,将空链表插入到另外一个链表中是没有意义的。但被插入的链表可以是空的。 static inline void list_splice(struct list_head *list,struct list_head *head) 这种情况会丢弃list所指向的头结点,这是特意设计的,因为两个链表有两个头结点,要去掉一个头结点。只要list非空链,head无任何限制,该程序都可以实现链表合并。 struct list_head *head) 5、获取宿主对象指针 如果需要有某种数据结构的队列,就在这种数据结构定义内部放上一个list_head数据结构。例如,建立数据结构foo链表的方式是,在foo的定义中,嵌入了一个list_head成员list。这里foo就是所指的"宿主"。 typedef struct foo { 但是,如何通过list_head成员访问到宿主结构项呢?毕竟list_head不过是个连接件,而我们需要的是一个"特定"的数据结构链表。 先介绍几个基本宏:offsetof、typeof、containerof 一共4步 char i; int j; char k; }Test; int main() { Test *p = 0; printf("%pn",&(p->k)); } 这里使用的是一个利用编译器技术的小技巧(编译器自动算出成员的偏移量),即先求得结构成员变量在结构体中的相对于结构体的首地址的偏移地址,然后根据结构体的首地址为0,从而得出该偏移地址就是该结构体变量在该结构体中的偏移,即:该结构体成员变量距离结构体首的距离。在offsetof()中,这个member成员的地址实际上就是type数据结构中member成员相对于结构变量的偏移量。对于给定一个结构,offsetof(type,member)是一个常量,list_entry()正是利用这个不变的偏移量来求得链表数据项的变量地址。 ---------------------typeof()-------------------- unsigned int i; typeof(i) x; x=100; printf("x:%dn",x); typeof() 是 gcc 的扩展,和 sizeof() 类似。 ------------------------ 在 container_of 宏中,它用来给 typeof() 提供参数,以获得 member 成员的数据类型; ---------------container_of()-------------------- container_of() 来自linuxkernel.h 内核中的注释:container_of - cast a member of a structure out to the containing structure。 ptr: the pointer to the member. type: the type of the container struct this is embedded in. member:the name of the member within the struct. #define container_of(ptr,type,member) ({ const typeof( ((type *)0)->member ) *__mptr = (ptr); (type *)( (char *)__mptr - offsetof(type,member) );}) 自己分析: 1.(type *)0->member为设计一个type类型的结构体,起始地址为0,编译器将结构体的起始的地址加上此结构体成员变量的偏移得到此结构体成员变量的地址,由于结构体起始地址为0,所以此结构体成员变量的偏移地址就等于其成员变量在结构体内距离结构体开始部分的偏移量。即:&(type *)0->member就是取出其成员变量的偏移地址。而其等于其在结构体内的偏移量:即为:(size_t)(& ((type *)0)->member)经过size_t的强制类型转换后,其数值为结构体内的偏移量。该偏移量这里由offsetof()求出。 2.typeof( ( (type *)0)->member )为取出member成员的变量类型。用其定义__mptr指针.ptr为指向该成员变量的指针。__mptr为member数据类型的常量指针,其指向ptr所指向的变量处。 3.(char *)__mptr转换为字节型指针。(char *)__mptr - offsetof(type,member) )用来求出结构体起始地址(为char *型指针),然后(type *)( (char *)__mptr - offsetof(type,member) )在(type *)作用下进行将字节型的结构体起始指针转换为type *型的结构体起始指针。 这就是从结构体某成员变量指针来求出该结构体的首指针。指针类型从结构体某成员变量类型转换为该结构体类型。 介绍了上面的几种基本宏后,对list_entry的理解就容易了。 ----------------list_entry()-------------------- list_entry()宏,获取当前list_head链表节点所在的宿主结构项。第一个参数为当前list_head节点的指针,即指向宿主结构项的list_head成员。第二个参数是宿主数据结构的定义类型。第三个参数为宿主结构类型定义中list_head成员名。 #define list_entry(ptr,member) container_of(ptr,member) 扩展替换即为: #define list_entry(ptr,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)减去这个偏移量,得到宿主对象地址,再将它转换为宿主数据结构类型的指针。 需要重申的是,链表头没有被嵌入到宿主对象中,因此对链表头执行宿主对象指针获取操作是没有意义的。
遍历是双循环链表的基本操作,为此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_64processor.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。十分精彩。典型用途是多个进程等待在同一个等待队列上,若事件发生时唤醒所有进程,则可以唤醒后将其依次从等待队列中删除。
如果只提供对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,member) for (pos = list_entry((head)->next,typeof(*pos),member); prefetch(pos->member.next),&pos->member != (head); pos = list_entry(pos->member.next,member)) 这是用于嵌套的结构体中的宏: struct example_struct { struct list_head list; int priority; ... //其他结构体成员 }; struct example_struct *node = list_entry(ptr,struct example_struct,list); 自己分析:对比list_entry(ptr,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,member) for (pos = list_entry((head)->prev,m+ember); prefetch(pos->member.prev),&pos->member != (head); pos = list_entry(pos->member.prev,member)) 分析类似上面。 ---------------list_prepare_entry()--------------- 如果遍历不是从链表头开始,而是从已知的某个pos结点开始,则可以使用list_for_each_entry_continue(pos,member)。但为了确保pos的初始值有效,Linux专门提供了一个list_prepare_entry(pos,member)宏,如果pos有值,则其不变;如果没有,则从链表头强制扩展一个虚pos指针。将它的返回值作为list_for_each_entry_continue()的pos参数,就可以满足这一要求。 内核中的list_prepare_entry()的代码: #define list_prepare_entry(pos,member) ((pos) ? : list_entry(head,member)) 分析: :前面是个空值,即:若pos不为空,则pos为其自身。等效于: (pos)? (pos): list_entry(head,member) 注意内核格式::前后都加了空格。 ------------list_for_each_entry_continue()-------- 内核中的list_for_each_entry_continue()的代码: #define list_for_each_entry_continue(pos,member) for (pos = list_entry(pos->member.next,member)) 此时不是从头节点开始遍历的,但仍然是以头节点为结束点的,即没有遍历完整个链表。 要注意并不是从pos开始的,而是从其下一个节点开始的,因为第一个有效pos是从pos->member.next扩展得到的。 -------------list_for_each_entry_safe()----------- 它们要求调用者另外提供一个与pos同类型的指针n,在for循环中暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。 内核中的注释与源代码: #define list_for_each_entry_safe(pos,member), n = list_entry(pos->member.next,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,member))
本文例子来自http://isis.poly.edu/kulesh/stuff/src/klist/,只是对其中注释部分作了翻译。 #include <stdio.h> #include <stdlib.h> #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= %dn",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= %dn",tmp->from); printf("n"); printf("deleting the list using list_for_each_safe()n"); list_for_each_safe(pos,q,list); printf("freeing item to= %d from= %dn",tmp->from); list_del(pos); free(tmp); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |