<span id='cvdxd'></span>
    <i id='cvdxd'><div id='cvdxd'><ins id='cvdxd'></ins></div></i>

    <code id='cvdxd'><strong id='cvdxd'></strong></code>
  1. <i id='cvdxd'></i>
    <acronym id='cvdxd'><em id='cvdxd'></em><td id='cvdxd'><div id='cvdxd'></div></td></acronym><address id='cvdxd'><big id='cvdxd'><big id='cvdxd'></big><legend id='cvdxd'></legend></big></address>
    1. <dl id='cvdxd'></dl>
      <ins id='cvdxd'></ins>
    2. <tr id='cvdxd'><strong id='cvdxd'></strong><small id='cvdxd'></small><button id='cvdxd'></button><li id='cvdxd'><noscript id='cvdxd'><big id='cvdxd'></big><dt id='cvdxd'></dt></noscript></li></tr><ol id='cvdxd'><table id='cvdxd'><blockquote id='cvdxd'><tbody id='cvdxd'></tbody></blockquote></table></ol><u id='cvdxd'></u><kbd id='cvdxd'><kbd id='cvdxd'></kbd></kbd>

      <fieldset id='cvdxd'></fieldset>

          详解Linux内核之双向循环链表

          • 时间:
          • 浏览:5
          • 来源:124软件资讯网

            1、双循环链表传统实现:

            在传统的双循环链表实现中  ,若是建立某种数据结构的双循环链表  ,通常接纳的措施是在这个数据结构的类型界说中加入两个(指向该类型工具的)指针next和prev  。例如:

            QUOTE:

            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结构

            QUOTE:

            -----------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、界说和初始化

            QUOTE:

            --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结构体变量的始地址将该结构体变量举行初始化  。

            QUOTE:

            #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内核中内联函数版本如下:

            QUOTE:

            static inline void INIT_LIST_HEAD(struct list_head *list)

            {

            list->next = list;

            list->prev = list;

            }


            此时的参数有明确的类型信息struct list_head ,同时可以看出其为指针  ,list无须象宏中那样() ,纵然参数为表达式  ,其也是求值后再作为参数传入的  。内联函数有严酷的参数类型检查 ,同时不会泛起宏函数扩展带来的异常问题  ,可是运行效率和空间效率与宏函数一致