嵌入式

【嵌入式Linux学习七步曲之第五篇 Linux内核及驱动编程】详解Linux内核之双向循环链表

2019-07-13 08:58发布

站内文章 / 嵌入式Linux
10381 0 1419
  详解Linux内核之双向循环链表 Sailor_forever  sailing_9806@163.com 转载请注明 http://blog.csdn.net/sailor_8318/archive/2008/05/23/2471129.aspx     【摘要】本文详解了内核中面向对象的list结构的原理，以及如何以list为内嵌对象来构造自己的链表结构，如何从内嵌list对象获得自定义的对象指针；探讨了各种宏或者函数的详细使用方法及怎样以通用list结构来操作自定义对象。 【关键字】双向循环链表，list，list_entry，typeof，containerof，list_for_each, list_for_each_entry   1、双循环链表传统实现... 1 2、Linux内核中双循环链表实现... 2 3、定义和初始化... 3 4、通用链表操作接口... 4 4.1添加节点... 4 4.2删除节点... 5 4.3移动节点... 6 4.4链表判空... 6 4.5链表合并... 7 5、获取宿主对象指针... 8 6、遍历... 11 6.1 List-head链表遍历... 11 6.2遍历宿主对象... 12 7、如何使用Linux中的双循环链表... 14  

1、双循环链表传统实现

在传统的双循环链表实现中，如果创建某种数据结构的双循环链表，通常采用的办法是在这个数据结构的类型定义中加入两个（指向该类型对象的）指针next和prev。例如： typedef struct foo {     …     struct foo *prev;     struct foo *next;     … } foo_t; 这里给出了对应的节点结构、空的双循环链表和非空的双循环链表示意图。    

2、Linux内核中双循环链表实现

在linux内核中，有大量的数据结构需要用到双循环链表，例如进程、文件、模块、页面等。若采用双循环链表的传统实现方式，需要为这些数据结构维护各自的链表，并且为每个链表都要设计插入、删除等操作函数。因为用来维持链表的next和prev指针指向对应类型的对象，因此一种数据结构的链表操作函数不能用于操作其它数据结构的链表。   在Linux源代码树的include/linux/list.h文件中，采用了一种类型无关的双循环链表实现方式。其思想是将指针prev和next从具体的数据结构中提取出来构成一种通用的"双链表"数据结构list_head。如果需要构造某类对象的特定链表，则在其结构（被称为宿主数据结构）中定义一个类型为list_head类型的成员，通过这个成员将这类对象连接起来，形成所需链表，并通过通用链表函数对其进行操作。其优点是只需编写通用链表函数，即可构造和操作不同对象的链表，而无需为每类对象的每种列表编写专用函数，实现了代码的重用。   list_head结构 -----------struct list_head{}及初始化宏--------- struct list_head {        struct list_head *next, *prev; }; 当用此类型定义一个独立的变量时，其为头结点。当其为某个结构体的一个成员时，其为普通结点。尽管形式一样，但表达的意义不同，是否应该定义为两个类型list_head和list_node？？？无法分开，空链表时指向了自己   list_head成员作为"连接件"，把宿主数据结构链接起来。如下图所示：   在Linux内核中的双循环链表实现方式下： 1. list_head类型的变量作为一个成员嵌入到宿主数据结构内； 2. 可以将链表结构放在宿主结构内的任何地方； 3. 可以为链表结构取任何名字； 4. 宿主结构可以有多个链表结构； 5. 用list_head中的成员和相对应的处理函数来对链表进行遍历； 6. 如果想得到宿主结构的指针，使用list_entry可以算出来。  

3、定义和初始化

--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内核中内联函数版本如下： static inline void INIT_LIST_HEAD(struct list_head *list) {        list->next = list;        list->prev = list; } 此时的参数有明确的类型信息struct list_head，同时可以看出其为指针，list无须象宏中那样（），即使参数为表达式，其也是求值后再作为参数传入的。内联函数有严格的参数类型检查，同时不会出现宏函数扩展带来的异常问题，但是运行效率和空间效率与宏函数一致。  

4、通用链表操作接口

4.1添加节点

在上面的设计下，所有链表（包括添加、删除、移动和拼接等）操作都是针对数据结构list_head进行的。提供给用户的的添加链表的操作有两种：表头添加和表尾添加。注意到，Linux双循环链表中有一个链表头，表头添加是指添加到链表头之后，而表尾添加则是添加到链表头的prev所指链表节点之后。   ------------__list_add()------list_add()------list_add_tail()------- static inline void __list_add(struct list_head *new, struct list_head *prev,  struct list_head *next) {        next->prev = new;        new->next = next;        new->prev = prev;        prev->next = new; } 普通的在两个非空结点中插入一个结点，注意new、prev、next都不能是空值。 Prev可以等于next，此时在只含头节点的链表中插入新节点。   static inline void list_add(struct list_head *new, struct  list_head *head) {        __list_add(new, head, head->next); } 在head和head->next两指针所指向的结点之间插入new所指向的结点。 即：在head指针后面插入new所指向的结点。Head并非一定为头结点。 当现有链表只含有一个头节点时，上述__list_add(new, head, head->next)仍然成立。   static inline void list_add_tail(struct list_head *new, struct list_head *head) {        __list_add(new, head->prev, head); } 在结点指针head所指向结点的前面插入new所指向的结点。当head指向头节点时，也相当于在尾结点后面增加一个new所指向的结点。 注意： head->prev不能为空，即若head为头结点，其head->prev当指向一个数值，一般为指向尾结点，构成循环链表。   上述三个函数实现了添加一个节点的任务，其中__list_add()为底层函数，“__”通常表示该函数是底层函数，供其他模块调用，此处实现了较好的代码复用，list_add和list_add_tail虽然原型一样，但调用底层函数__list_add时传递了不同的参数，从而实现了在head指向节点之前或之后添加新的对象。  

4.2删除节点

如果要从链表中删除某个链表节点，则可以调用list_del或list_del_init。 需要注意的是，上述操作均仅仅是把节点从双循环链表中拿掉，用户需要自己负责释放该节点对应的数据结构所占用的空间，而这个空间本来就是用户分配的。   -----------__list_del()---list_del()-----list_del_init()---------- static inline void __list_del(struct list_head * prev, struct list_head * next) {        next->prev = prev;        prev->next = next; } 在prev和next指针所指向的结点之间，两者互相所指。在后面会看到：prev为待删除的结点的前面一个结点，next为待删除的结点的后面一个结点。   static inline void list_del(struct list_head *entry) {        __list_del(entry->prev, entry->next);        entry->next = LIST_POISON1;        entry->prev = LIST_POISON2; } 删除entry所指的结点，同时将entry所指向的结点指针域封死。 对LIST_POISON1,LIST_POISON2的解释说明： Linux 内核中解释：These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses  non-initialized list entries. #define LIST_POISON1  ((void *) 0x00100100) #define LIST_POISON2  ((void *) 0x00200200) 常规思想是：entry->next = NULL; entry->prev = NULL; 保证不可通过该节点进行访问。   ---------------list_del_init()-------------------- static inline void list_del_init(struct list_head *entry) {        __list_del(entry->prev, entry->next);        INIT_LIST_HEAD(entry); } 删除entry所指向的结点，同时调用LIST_INIT_HEAD()把被删除节点为作为链表头构建一个新的空双循环链表。  

4.3移动节点

Linux还提供了两个移动操作：list_move和list_move_tail。 -----------list_move()--list_move_tail()---------- static inline void list_move(struct list_head *list, struct list_head *head) {         __list_del(list->prev, list->next);         list_add(list, head); } 将list结点前后两个结点互相指向彼此，删除list

热门文章