linux list_fc linux list命令 - CSDN
精华内容
参与话题
  • Linux内核中经典链表 list_head 常见使用方法解析

    万次阅读 多人点赞 2018-07-03 17:49:07
    做内核驱动开发经常会使用linux内核最经典的双向链表 list_head, 以及它的拓展接口(或者宏定义): list_add , list_add_tail, list_del , list_entry ,list_for_each , list_for_each_entry ...... 每次看到这些...

          做内核驱动开发经常会使用linux内核最经典的双向链表 list_head, 以及它的拓展接口(或者宏定义): list_add , list_add_tail, list_del , list_entry ,list_for_each , list_for_each_entry ...... 

          每次看到这些接口,感觉都很像,今天专门研究了一下内核,对它们做一些总结,希望为后续开发提供方便。

    首先找到list_head 结构体定义,kernel/inclue/linux/types.h  如下:  

    struct list_head {
    	struct list_head *next, *prev;
    };

           然后就开始围绕这个结构开始构建链表,然后插入、删除节点 ,遍历整个链表等等,其实内核已经提供好了现成的接口,接下来就让我们进入 kernel/include/linux/list.h中:

    一. 创建链表

        内核提供了下面的这些接口来初始化链表:

    #define LIST_HEAD_INIT(name) { &(name), &(name) }
    
    #define LIST_HEAD(name) \
    	struct list_head name = LIST_HEAD_INIT(name)
    
    static inline void INIT_LIST_HEAD(struct list_head *list)
    {
    	WRITE_ONCE(list->next, list);
    	list->prev = list;
    }

    如:  可以通过 LIST_HEAD(mylist) 进行初始化一个链表,mylist的prev 和 next 指针都是指向自己。


       struct list_head mylist = {&mylist,  &mylist} ;   

           但是如果只是利用mylist这样的结构体实现链表就没有什么实际意义了,因为正常的链表都是为了遍历结构体中的其它有意义的字段而创建的,而我们mylist中只有 prev和next指针,却没有实际有意义的字段数据,所以毫无意义。

          综上,我们可以创建一个宿主结构,然后在此结构中再嵌套mylist字段,宿主结构又有其它的字段(进程描述符 task_struct,页面管理的page结构,等就是采用这种方法创建链表的)。为简便理解,定义如下:

    struct  my_task_list {
        int val ;
        struct list_head mylist;
    }

    创建第一个节点

    struct my_task_list first_task = 
    { .val = 1,
      .mylist = LIST_HEAD_INIT(first_task.mylist)
    };

    这样mylist 就prev 和 next指针分别指向mylist自己了,如下图:



    二. 添加节点

    内核已经提供了添加节点的接口了

    1.  list_add 

        如下所示。 根据注释可知,是在链表头head后方插入一个新节点new。

        并且还说了一句:这个接口利用实现堆栈  (why? 稍后再做分析)

    /**
     * list_add - add a new entry
     * @new: new entry to be added
     * @head: list head to add it after
     *
     * Insert a new entry after the specified head.
     * This is good for implementing stacks.
     */
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head, head->next);
    }

    list_add再调用__list_add接口

    /*
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_add(struct list_head *new,
    			      struct list_head *prev,
    			      struct list_head *next)
    {
    	if (!__list_add_valid(new, prev, next))
    		return;
    
    	next->prev = new;
    	new->next = next;
    	new->prev = prev;
    	WRITE_ONCE(prev->next, new);
    }

    其实就是在head 链表头后和链表头后第一个节点之间插入一个新节点。然后这个新的节点就变成了链表头后的第一个节点了。

    依然用上面的my_task_list结构体举例子

    首先我们创建一个链表头   header_task 

     LIST_HEAD(header_task);

       

    然后再创建实际的第一个节点

    struct my_task_list my_first_task = 
    { .val = 1,
      .mylist = LIST_HEAD_INIT(my_first_task.mylist)
    };

    接着把这个节点插入到header_task之后

    list_add(&my_first_task.mylist,  &header_task);



    然后在创建第二个节点,同样把它插入到header_task之后

    struct my_task_list my_second_task = 
    { .val = 2,
      .mylist = LIST_HEAD_INIT(my_second_task.mylist)
    };
    其实还可以用另外一个接口 INIT_LIST_HEAD 进行初始化(参数为指针变量), 如下:
    struct my_task_list my_second_task;
    my_second_task.val = 2;
    INIT_LIST_HEAD(&my_second_task.mylist);

    list_add(&my_second_task.mylist, &header_task)


    以此类推,每次插入一个新节点,都是紧靠着header节点,而之前插入的节点依次排序靠后,那最后一个节点则是第一次插入header后的那个节点。最终可得出:先来的节点靠后,而后来的节点靠前,“先进后出,后进先出”。所以此种结构类似于 stack“堆栈”, 而 header_task就类似于内核stack中的栈顶指针esp, 它都是紧靠着最后push到栈的元素。

    2. list_add_tail 接口 

    上面所讲的list_add接口是从链表头header后添加的节点。 同样,内核也提供了从链表尾处向前添加节点的接口list_add_tail. 让我们来看一下它的具体实现。

    /**
     * list_add_tail - add a new entry
     * @new: new entry to be added
     * @head: list head to add it before
     *
     * Insert a new entry before the specified head.
     * This is useful for implementing queues.
     */
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head->prev, head);
    }

    从注释可得出:(1)在一个特定的链表头前面插入一个节点

    (2)这个方法很适用于队列的实现 (why?)

    进一步把__list_add ()展开如下:

    /*
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_add(struct list_head *new,
    			      struct list_head *prev,
    			      struct list_head *next)
    {
    	if (!__list_add_valid(new, prev, next))
    		return;
    
    	next->prev = new;
    	new->next = next;
    	new->prev = prev;
    	WRITE_ONCE(prev->next, new);
    }

        所以,很清楚明了, list_add_tail就相当于在链表头前方依次插入新的节点(也可理解为在链表尾部开始插入节点,此时,header节点既是为节点,保持不变)

        利用上面分析list_add接口的方法可画出数据结构图形如下。

    (1)创建一个 链表头(实际上应该是表尾), 同样可调用 LIST_HEAD(header_task);

        


    (2)插入第一个节点 my_first_task.mylist , 调用 list_add_tail(& my_first_task.mylist,  & header_task);

        

    (3) 插入第二个节点my_second_task.mylist,调用list_add_tail(& my_second_task.mylist,  &header_task);



    依此类推,每次插入的新节点都是紧挨着 header_task表尾,而插入的第一个节点my_first_task排在了第一位,my_second_task排在了第二位,可得出:先插入的节点排在前面,后插入的节点排在后面,“先进先出,后进后出”,这不正是队列的特点吗(First in First out)!

    三. 删除节点

          内核同样在list.h文件中提供了删除节点的接口 list_del(), 让我们看一下它的实现流程

    static inline void list_del(struct list_head *entry)
    {
    	__list_del_entry(entry);
    	entry->next = LIST_POISON1;
    	entry->prev = LIST_POISON2;
    }
    /*
     * Delete a list entry by making the prev/next entries
     * point to each other.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_del(struct list_head * prev, struct list_head * next)
    {
    	next->prev = prev;
    	WRITE_ONCE(prev->next, next);
    }
    
    /**
     * list_del - deletes entry from list.
     * @entry: the element to delete from the list.
     * Note: list_empty() on entry does not return true after this, the entry is
     * in an undefined state.
     */
    static inline void __list_del_entry(struct list_head *entry)
    {
    	if (!__list_del_entry_valid(entry))
    		return;
    
    	__list_del(entry->prev, entry->next);
    }
        利用list_del(struct list_head *entry) 接口就可以删除链表中的任意节点了,但需注意,前提条件是这个节点是已知的,既在链表中真实存在,切prev,next指针都不为NULL。

        

    四. 链表遍历

         内核是同过下面这个宏定义来完成对list_head链表进行遍历的,如下 :

    /**
     * list_for_each	-	iterate over a list
     * @pos:	the &struct list_head to use as a loop cursor.
     * @head:	the head for your list.
     */
    #define list_for_each(pos, head) \
    	for (pos = (head)->next; pos != (head); pos = pos->next)
        上面这种方式是从前向后遍历的,同样也可以使用下面的宏反向遍历:
    /**
     * list_for_each_prev	-	iterate over a list backwards
     * @pos:	the &struct list_head to use as a loop cursor.
     * @head:	the head for your list.
     */
    #define list_for_each_prev(pos, head) \
    	for (pos = (head)->prev; pos != (head); pos = pos->prev)

       而且,list.h 中也提供了list_replace( 节点替换)  list_move(节点移位)  ,翻转,查找等接口,这里就不在一一分析了。

    五. 宿主结构

    1.找出宿主结构  list_entry(ptr, type, member)

        上面的所有操作都是基于list_head这个链表进行的,涉及的结构体也都是:

    struct list_head {
    	struct list_head *next, *prev;
    };

            其实,正如文章一开始所说,我们真正更关心的是包含list_head这个结构体字段的宿主结构体,因为只有定位到了宿主结构体的起始地址,我们才能对对宿主结构体中的其它有意义的字段进行操作。

    struct  my_task_list {
        int val ;
        struct list_head mylist;
    }
          那我们如何根据mylist这个字段的地址而找到宿主结构my_task_list的位置呢???

          做linux驱动开发的同学是不是想到了LDD3这本书中经常使用的一个非常经典的宏定义呢!那就是:

    container_of(ptr, type, member)

        没错就是它,在LDD3这本书中的第三章字符设备驱动,以及第十四章驱动设备模型中多次提到,所以我觉得这个宏应该是内核最经典的宏之一。 那list.h中使用什么接口实现的这个转换功能呢?

    /**
     * list_entry - get the struct for this entry
     * @ptr:	the &struct list_head pointer.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_head within the struct.
     */
    #define list_entry(ptr, type, member) \
    	container_of(ptr, type, member)
        list.h中提供了list_entry宏来实现对应地址的转换,但最终还是调用了container_of宏,所以container_of宏的伟大之处不言而喻。 那接下来让我们揭开她的面纱:

        此宏在内核代码 kernel/include/linux/kernel.h中定义(此处kernel版本为3.10;新版本4.13之后此宏定义改变,但实现思想保持一致)

    /** 
     * 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) );})  

    而offsetof定义在 kernel/include/linux/stddef.h ,如下:

    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

    看下container_of宏的注释:

    (1)根据结构体重的一个成员变量地址导出包含这个成员变量mem的struct地址。

    (2)参数解释:

             ptr  : 成员变量mem的地址    

            type: 包含成员变量mem的宿主结构体的类型

            member: 在宿主结构中的mem成员变量的名称

            如果用我们之前定义的结构体struct my_task_list举例

    struct  my_task_list {
        int val ;
        struct list_head mylist;
    }
    struct my_task_list first_task = 
    { .val = 1,
      .mylist = LIST_HEAD_INIT(first_task.mylist)
    };

        ptr   :    &first_task.mylist

        type  :  struct my_task_list

        member :  mylist

    而container_of宏的功能就是根据 first_task.mylist字段的地址得出first_task结构的其实地址。

    把上面offsetof的宏定义代入container_of宏中,可得到下面定义:

    #define container_of(ptr, type, member) ({          \  
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \  
        (type *)( (char *)__mptr - ((size_t) &((type *)0)->member) );})  

    再把宏中对应的参数替换成实参:

       const typeof( ((struct my_task_list *)0)->mylist ) *__mptr = (&first_task.mylist); \  
        (struct my_task_list *)( (char *)__mptr - ((size_t) &((struct my_task_list *)0)->mylist) );})  

    typeof 是 GNU对C新增的一个扩展关键字,用于获取一个对象的类型 ,比如这里((struct my_task_list *)0)->mylist 是把0地址强制转换成struct my_task_list 指针类型,然后取出mylist元素。 然后再对mylist元素做typeof操作,其实就是获取 my_task_list结构中mylist字段的数据类型struct list_head,所以这行语句最后转化为:

    const struct list_head *__mptr  = (&first_task.mylist);

    第二条语句中在用 __mptr这个指针 减去 mylist字段在 my_task_list中的偏移(把0地址强制转换成struct my_task_list指针类型,然后取出mylist的地址,此时mylist的地址也是相对于0地址的偏移,所以就是mylist字段相对于宿主结构类型struct my_task_list的偏移) 正好就是宿主结构的起始地址。C语言的灵活性得到了很好的展示!!!


    2. 宿主结构的遍历

            我们可以根据结构体中成员变量的地址找到宿主结构的地址, 并且我们可以对成员变量所建立的链表进行遍历,那我们是不是也可以通过某种方法对宿主结构进行遍历呢?    

            答案肯定是可以的,内核在list.h中提供了下面的宏:

    /**
     * list_for_each_entry	-	iterate over list of given type
     * @pos:	the type * to use as a loop cursor.
     * @head:	the head for your list.
     * @member:	the name of the list_head within the struct.
     */
    #define list_for_each_entry(pos, head, member)				\
    	for (pos = list_first_entry(head, typeof(*pos), member);	\
    	     &pos->member != (head);					\
    	     pos = list_next_entry(pos, member))

     其中,list_first_entry 和  list_next_entry宏都定义在list.h中,分别代表:获取第一个真正的宿主结构的地址; 获取下一个宿主结构的地址。它们的实现都是利用list_entry宏。

    /**
     * list_first_entry - get the first element from a list
     * @ptr:	the list head to take the element from.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_head within the struct.
     *
     * Note, that list is expected to be not empty.
     */
    #define list_first_entry(ptr, type, member) \
    	list_entry((ptr)->next, type, member)
    
    /**
     * list_next_entry - get the next element in list
     * @pos:	the type * to cursor
     * @member:	the name of the list_head within the struct.
     */
    #define list_next_entry(pos, member) \
    	list_entry((pos)->member.next, typeof(*(pos)), member)

    最终实现了宿主结构的遍历

    #define list_for_each_entry(pos, head, member)				\
    	for (pos = list_first_entry(head, typeof(*pos), member);	\
    	     &pos->member != (head);					\
    	     pos = list_next_entry(pos, member))
     首先pos定位到第一个宿主结构地址,然后循环获取下一个宿主结构地址,如果查到宿主结构中的member成员变量(宿主结构中struct list_head定义的字段)地址为head,则退出,从而实现了宿主结构的遍历。如果要循环对宿主结构中的其它成员变量进行操作,这个遍历操作就显得特别有意义了。

            我们用上面的 my_task_list结构举个例子:

    struct my_task_list *pos_ptr = NULL ; 
    list_for_each_entry (pos_ptr, & header_task, mylist ) 
        { 
             printk ("val =  %d\n" , pos_ptr->val); 
        }

        

    参考文档:https://kernelnewbies.org/FAQ/LinkedLists

                    《Understanding linux kernel》

                    《Linux device drivers》

    展开全文
  • linux kernel list详解

    千次阅读 2018-07-14 17:15:49
    linux kernel list详解

    因为很多的原因,我们在实际项目的代码中,很多地方都用到了源自linux kernel的list。也因为一些使用习惯、团队风格等问题,我们在移植的过程中对其进行了一定的改进。但基本框架和基本功能都没有做任何的改变。正好书中很多地方也是用到了linux kernel list,所以我们有必要对其进行系统而详细的介绍,正巧我也觉得这一章可以单独的拿出来,所以就有了这篇文章。


    因为我们面面俱到的讲解了list,所以相对来说文章很长。希望大家能有耐心。


    linux kernel list,linux内核的链表结构,它使用了最简洁的方式实现了一个几乎是万能的链表。

    说起链表,一共有3种:单向链表、双向链表、循环链表。


    单向链表是链表中最简单的一种形式,它只有一个后继指针(一般代码中是next)来维护结构。所以,单向链表只能沿着后继指针做向后操作,不能向前操作。单向链表也不能从中间插入或者删除一个元素,因为没有前向指针,所以无法获取前一个元素,从中间删除链表元素会引起断链。单向链表示意图如下:


    640?wx_fmt=png&wxfrom=5&wx_lazy=1


    双向链表:双向链表比单向链表复杂一些,它除了有一个后续指针next指向下一个元素之外还有一个前驱指针prev指向前一个元素。所以,双向链表不仅能向后遍历,还能向前遍历。同时,双向链表也能对链表中的任一元素进行操作,并且在任何位置都可以进行增加和删除操作,因为它不会断链。双向链表的示意图如下:


    0?wx_fmt=png


    循环链表:循环链表是双向链表的升级版。相比双向链表,循环列表首尾相连。示意图如下:


    0?wx_fmt=png


    本节所要讨论的kernel list是一个循环链表结构。我注意并且运用linux kernel list是从2.6内核开始的。linux内核的链表和我们一般定义的链表最大的差别有2个:

    1. 结构定义。linux内核的链表定义非常简单明了,并且严格遵守了自定义结构不定义数据的规则。在list.h文件中定义如下:

      1. struct list_node  {
      2.    struct list_node  *prev;
      3.    struct list_node  *next;
      4. };

      在linux的kernel中结构体的名称是list_head,只是因为习惯问题,我们团队觉得list_head使用起来不太顺手,而list_node比较习惯,所以我们在移植的时候统一改了一下结构体的名称。list_node的定义相当清晰:前驱指针和后继指针。list_node的定义和我们通常对于链表结构的定义最大的不同是list_node链表结构没有数据域。通常我们要实现双向链表结构会将本身的链表关系结构和实体数据属性合并到一起。比如有一个学生结构体,属性为学号(id),姓名(name),年龄(age)。那么这样的一个链表定义如下:

      1. struct student {
      2.    int id;
      3.    char *name;
      4.    int age;
      5.    struct student *prev;
      6.    struct student *next;
      7. };

      这个结构体正确,并且可用,但是并不通用。

    2. linux kernel list使用的时候需要一个表头。因为它的通用化设计和追求更简单的算法实现,list必须要一个简单而通用的方法通过自身来判断链表是否存在数据、链表是否已经遍历到最后等等。所以linux kernel list不能像我们通常的定义一样来区分,而是通过在使用链表之前置一个链表头来实现。链表头是在链表初始化的时候确定的,所以链表可以通过前驱和后继指针都指向自己来确定链表目前的状态是空的。

    linux kernel list使用起来也很简单。当我们使用它来表示链表的时候,需要使用数据包含结构的方式而不是我们上面的结构和数据混合方式。比如同样的定义一个student结构,使用linux kernel list的代码如下:

    1.    struct student {
    2.        struct list_node chain;
    3.        int id;
    4.        char *name;
    5.        int age;
    6.   };

    随后,在使用链表操作之前一定要先初始化链表头,再使用linux kernel list提供的API进行增加、删除、遍历等操作。

    初始化

    linux kernel list提供了3种初始化链表的方式,前面2种其实是一样的,属于创建型,API如下:

    1. #define LIST_HEAD_INIT(name) { &(name), &(name) }
    2. #define LIST_HEAD(name) \
    3.    struct list_node  name = LIST_HEAD_INIT(name)

    第3种是初始化模式,这对于结构体内嵌链表头比较适合,比如我们上面内存池中的slot_chain、larger_chain和cleanup_chain。

    1.    static inline void INIT_LIST_HEAD(struct list_node  *list) {
    2.        list->next = list;
    3.        list->prev = list;
    4.    }

    不管是那个API初始化链表,初始化的时候始终只在做一件事情:就是把head的prev指针和next指针都指向head本身。初始化后的链表结构如下图:

    0?wx_fmt=png

    添加链表项

    linux kernel list提供了2个添加链表项的API,分别是在链表的头部添加一个链表项和在链表的尾部添加一个列表项。因为linux kernel list定义链表结构的时候只定义了前向和后继两个指针,添加链表项也只是指针指向的变动;又因为从开始设计linux kernel list的时候就设定链表头是肯定存在的,所以也没有了链表是否为空之类的繁琐判断,整个代码显得非常的简洁。linux kernel list提供的代码如下:

    1.     /*
    2.     * 在两个已知连续的实体间插入一个新实体
    3.     * 这个方法仅使用在我们知道实体的prev/next指针的内部链表操作
    4.    */
    5.    static inline void __list_add(struct list_node  *new,
    6.            struct list_node  *prev,
    7.            struct list_node  *next) {
    8.        next->prev = new;
    9.        new->next = next;
    10.        new->prev = prev;
    11.        prev->next = new;
    12.    }

    注意:这是一个私有函数。在linux kernel list定义中,形如"__XXXX()"的函数,也就是双下划线开始的函数,被内定为内部函数,外部不许调用(下同,不在累述)。 在私有函数中,一般只会进行最简单的操作,而对于边界问题、特殊值等检查和校验都会在对外的接口函数中完成。

    1.    /**
    2.     * list_add - 添加一个实体
    3.     * @new: 被添加的新实体
    4.     * @head: 链表头部,新实体被添加在这个head后面
    5.     *
    6.     * 在指定的链表头部后面添加一个新实体。
    7.     * 这有利于实现栈。
    8.     */
    9.    static inline void list_add(struct list_node  *new, struct list_node  *head) {
    10.        __list_add(new, head, head->next);
    11.    }

    这是一个链表的添加函数,将实体添加到链表的head后面,也就是next指针处。比如初始化链表头后的示意图如上图所示,那么添加实体后的整个链表示意图如下所示:

    0?wx_fmt=png

    1.    /**
    2.     * list_add_tail - 添加一个新实体
    3.     * @new: 被添加的新实体
    4.     * @head: 链表头部,新实体加被添加在这个head之前
    5.     *
    6.     * 在指定的链表头部之前添加一个新实体。
    7.     * 这对于实现队列有用。
    8.     */
    9.    static inline void list_add_tail(struct list_node  *new, struct list_node  *head) {
    10.        __list_add(new, head->prev, head);
    11.    }

    这也是一个链表的添加函数,和上面的函数不同的是此函数将实体添加到链表的末尾,也就是head的prev指针指向处。如果在上图的基础上将实体添加到链表的末尾,添加后的链表示意图如下所示:

    0?wx_fmt=png

    删除链表项

    删除链表项和添加链表项如出一辙,也是简单的指针操作。相比添加链表项,因为双向链表中的项每个都有前向和后继两个指针,所以删除链表项只需要明确单个链表项即可,并不存在从头部删除或者是从尾部删除的区别。所以,linux kernel list的代码如下:

    1.    /*
    2.    * 通过实体的prev/next指针相互指向对方删除实体
    3.     *
    4.     * 这个方法仅使用在我们知道实体的prev/next指针的内部链表操作
    5.    */
    6.   static inline void __list_del(struct list_node  * prev, struct list_node  * next) {
    7.        next->prev = prev;
    8.        prev->next = next;
    9.    }
    10.    static inline void __list_del_entry(struct list_node  *entry) {
    11.        __list_del(entry->prev, entry->next);
    12.    }

    同上,这2个函数是链表删除的真正操作,因为是"__"双下划线开头,故是一个私有函数。

    1.    /**
    2.     * list_del - 从链表中删除一个实体.
    3.     * @entry: 从链表中欲删除的实体.
    4.     * Note:  在entry上执行list_del操作后,对entry执行list_empty操作将不返回true。
    5.     *              因为entry属于未定义状态。
    6.     */
    7.    static inline void list_del(struct list_node  *entry) {
    8.        __list_del(entry->prev, entry->next);
    9.        entry->next = NULL;
    10.        entry->prev = NULL;
    11.    }

    上面的函数是删除链表项的对外API。如有原始链表如下图:

    0?wx_fmt=png

    执行list_del操作,删除实体2后,链表图示如下:

    0?wx_fmt=png

    对于这个函数,我们在移植的过程中进行了更改,原本的代码是这样的:

    1.    static inline void list_del(struct list_head *entry) {
    2.        __list_del(entry->prev, entry->next);
    3.        entry->next = LIST_POISON1; //注意这里的不同
    4.        entry->prev = LIST_POISON2;
    5.    }

    我们更改的是将prev和next指针指向了NULL,而linux kernel是指向了LIST_POISON1和LIST_POISON2两个宏。查看一下这两个宏定义:

    1.    #define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
    2.    #define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)

    有点莫名其妙的定义,在往下查,POISON_POINTER_DELTA的宏定义如下:

    1.    #ifdef CONFIG_ILLEGAL_POINTER_VALUE
    2.        #define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)
    3.    #else
    4.        #define POISON_POINTER_DELTA 0
    5.    #endif

    还是没看懂。没看懂也不重要,查了一下linux的官方解析,LIST_POISON是一段内核内的无效的地址区,当开发者误用这个地址时,会发出页错误。我们为了简单起见,将其改成了NULL,也无伤大雅。

    linux还提供了一个删除链表项实体的API,如下:

    1.      /**
    2.     * list_del_init - 从链表中删除一个实体,并且重新将该实体初始化为另一链表的head.
    3.     * @entry: 从链表中欲删除的实体.
    4.     */
    5.    static inline void list_del_init(struct list_node  *entry) {
    6.        __list_del_entry(entry);
    7.        INIT_LIST_HEAD(entry);
    8.    }

    这个API和上面的删除链表项API的不同是:会将被删除的实体初始化为另一个链表的head。同上一样删除实体2,本API会将实体2初始化为head。示意图如下:

    0?wx_fmt=png

    替换操作

    linux kernel list定义了2个替换API。第一个API操作仅仅只是替换而已,第二个API在替换的基础上还增加了初始化被替换实体的操作。linux kernel list代码如下:

    1.    /**
    2.     * list_replace - 将old实体替换成new实体
    3.     * @old : 被替换掉的实体
    4.     * @new : 替换的实体
    5.     *
    6.     * 如果old是一个空的(并不是NULL,空的是指prev/next都指向自己,比如head),
    7.     *  old将会被重写.
    8.     */
    9.    static inline void list_replace(struct list_node  *old,
    10.            struct list_node  *new) {
    11.        new->next = old->next;
    12.        new->next->prev = new;
    13.        new->prev = old->prev;
    14.        new->prev->next = new;
    15.    }

    此API是直接将old的实体替换成了new,比如有一个new的实体,链表示意图如下:

    0?wx_fmt=png

    将new替换成实体2后,链表示意图如下:

    0?wx_fmt=png

    注意,这里有个问题:替换后的元素原来的prev和next指针指向并没有发生改变,还是保持原来的指向,所以这是一个bug的温床,大家要注意处理。最简单的办法就是把替换下来的元素prev、next指针都设置成NULL就可以了。

    1.    /**
    2.     * list_replace_init - 将old实体替换成new实体,并且重新将old初始化为另一链表的head
    3.     * @old : 被替换掉的实体
    4.     * @new : 替换的实体
    5.     *
    6.     * 如果old是一个空的(并不是NULL,空的是指prev/next都指向自己,比如head),
    7.     *  old将会被重写.
    8.     */
    9.    static inline void list_replace_init(struct list_node  *old,
    10.            struct list_node  *new) {
    11.        list_replace(old, new);
    12.        INIT_LIST_HEAD(old);
    13.    }

    此API将会在替换掉old以后,将old初始化为另一个链表的head。和list_del_init异曲同工。替换后链表示意图如下:

    0?wx_fmt=png

    对于替换操作,有一个特例是当链表为空的时候,也就是只有head一个元素的时候,示意图如下:

    0?wx_fmt=png

    如果将head替换掉,将会形成如下的链表形式:

    0?wx_fmt=png

    移动操作

    linux kernel list定义了两个移动操作的API。移动操作是将原本属于链表A中的实体移动到链表B中,相当于将元素从链表A中删除再加入到链表B中。linux kernel list的代码如下:

    1.    /**
    2.     * list_move - 将list从一个链表移动到另一个链表中
    3.     * @list: 欲移动的实体
    4.     * @head: 欲加入的新链表的head
    5.     */
    6.    static inline void list_move(struct list_node  *list, struct list_node  *head) {
    7.        __list_del_entry(list);
    8.        list_add(list, head);
    9.    }

    有两个链表,如下图所示:

    0?wx_fmt=png

    假设移动实体2,将实体2从左边的链表移动到右边的链表,即自行list_move(实体2,右边链表的head),则两个链表的示意图如下所示:

    0?wx_fmt=png

    从示意图中可以看出,list_move函数是将元素移植到链表的头部,其实不仅仅是头部,只要是list_node元素,都可以满足要求,确切来说,移动到参数head元素的next指针指向的位置才是正确的。

    有移动到next位置,就会有移动到prev指针指向位置的,所以代码如下:

    1.    /**
    2.     * list_move_tail -  将list从一个链表移动到另一个链表尾部
    3.     * @list: 欲移动的实体
    4.     * @head:  欲加入的新链表的head
    5.     */
    6.    static inline void list_move_tail(struct list_node  *list,
    7.            struct list_node  *head) {
    8.        __list_del_entry(list);
    9.        list_add_tail(list, head);
    10.    }

    同样的道理,将实体2移动到右边链表的tail位置,示意图如下:

    0?wx_fmt=png

    和list_move函数一样,确切的意义是将元素移动到参数head的prev指针指向的位置。

    1.    /**
    2.     * list_rotate_left - 左向移动节点,把第一个元素移动到最后一个
    3.     * @head: 链表的head节点
    4.     */
    5.    static inline void list_rotate_left(struct list_node  *head) {
    6.        struct list_node  *first;
    7.        if (!list_empty(head)) {
    8.            first = head->next;
    9.            list_move_tail(first, head);
    10.        }
    11.    }

    该函数是将head元素的next指针指向的实体向后移动到head元素prev指针指向的位置。链表移动示意图如下所示:

    0?wx_fmt=png

    如果这个函数执行多次,将会把整个链表的顺序正好做一个180度的翻转。

    判断操作

    linux kernel list为链表增加了判断特殊状态的API。判断链表的状态并没有特别大的难度,linux kernel list需要注意的地方就是:链表为empty的时候,链表并不是NULL,也不是一个元素没有。链表至少有一个元素,就是它本身的head元素。

    1.    /**
    2.     * list_is_last - 判断list节点是不是head链表的最后一个节点
    3.     * @list: 欲测试的节点
    4.     * @head: 链表的head节点
    5.     */
    6.    static inline int list_is_last(const struct list_node  *list,
    7.            const struct list_node  *head) {
    8.        return list->next == head;
    9.    }
    10.    /**
    11.     * list_empty - 判断链表是否是空,即一个节点都不存在
    12.     * @head: 欲测试的链表
    13.     */
    14.    static inline int list_empty(const struct list_node  *head) {
    15.        return head->next == head;
    16.    }
    17.    /**
    18.     * list_empty_careful - 测试链表是都为空且未被修改
    19.     * @head: 欲测试的链表
    20.     *
    21.     *
    22.     * 说明:
    23.     * 测试链表是否为空的,并且检查没有另外的CPU正在更改成员(next或者是prev指针)
    24.     *
    25.     * 注意:如果在没有同步的情况下使用list_empty_careful函数,
    26.     * 除非其他cpu的链表操作只有list_del_init(),否则仍然不能保证线程安全。
    27.     *
    28.     */
    29.    static inline int list_empty_careful(const struct list_node  *head) {
    30.        struct list_node  *next = head->next;
    31.        return (next == head) && (next == head->prev);
    32.    }
    33.     /**
    34.     * list_is_singular - 判断链表是否只有一个节点(除head节点外)
    35.     * @head: 欲测试的链表.
    36.     */
    37.    static inline int list_is_singular(const struct list_node  *head) {
    38.        return !list_empty(head) && (head->next == head->prev);
    39.    }

    切分

    linux kernel list为链表定义了切分操作。切分操作发生在两个链表中,所以相对比较复杂,同时会修改两个链表的指针指向。linux kernel list的代码定义如下:

    1.    /**
    2.    *  __list_cut_position - 将一个列表切分成两个链表
    3.    *           从head节点开始(不包括head)到entry节点结束(包括entry)的节点
    4.    *           全部切割到list链表
    5.    *  @list : 一个新的链表,将切分的节点全部加入到这个链表
    6.    *  @head : 待切分链表的开始节点
    7.    *  @entry : 待切分链表的结束节点,必须和head在一个链表内
    8.    *  注意:list必须是一个空链表,或者是无所谓丢失原有节点的链表,
    9.    *           切分操作将会替换掉list链表原有的元素
    10.    */
    11.    static inline void __list_cut_position(struct list_node  *list,
    12.            struct list_node  *head,
    13.            struct list_node  *entry) {
    14.        struct list_node  *new_first = entry->next;
    15.        list->next = head->next;
    16.        list->next->prev = list;
    17.        list->prev = entry;
    18.        entry->next = list;
    19.        head->next = new_first;
    20.        new_first->prev = head;
    21.    }
    22.    /**
    23.     * list_cut_position - 将一个链表切分成2个
    24.    *  @list : 一个新的链表,将切分的节点全部加入到这个链表
    25.    *  @head : 待切分链表的开始节点
    26.    *  @entry : 待切分链表的结束节点,必须和head在一个链表内
    27.    *
    28.     */
    29.    static inline void list_cut_position(struct list_node  *list,
    30.            struct list_node  *head, struct list_node  *entry) {
    31.        if (list_empty(head))
    32.            return;
    33.        if (list_is_singular(head) &&
    34.                (head->next != entry && head != entry))
    35.            return;
    36.        if (entry == head)
    37.            INIT_LIST_HEAD(list);
    38.        else
    39.            __list_cut_position(list, head, entry);
    40.    }

    严格按照linux kernel的规则书写代码,双下划綫开头的函数是内部函数,没有加任何的参数验证,而对外开放的API则增加了参数校验。切分链表的操作和list_move比较相像,也是从一个链表中将一堆元素删除,再加到另外一个链表中。和list_move的差别可能只是移动的元素数量不同了。
    因为链表切分函数一次操作的元素变多了,所以形成了一个区间。对于参数head和entry来说,切分的区间在head上是开区间,切分的时候不会包含head自身;而在entry上是闭区间,切分的时候包含entry自身。

    设有两个链表,如下图:

    0?wx_fmt=png

    假设,我们需要将元素2-元素4区间的全部元素切分到另外一个链表中,执行list_cut_position后,链表的状态如下图所示:

    0?wx_fmt=png

    注意:另外一个链表中的元素6和元素7已经被替换掉了。这种替换容易引起野指针,一定要引起注意和重视。

    1.    /**
    2.    * list_clear - 清除以head为头部的链表,将其所有元素挂载到list链表上
    3.    * @head : 欲清除节点的链表head节点
    4.    *  @list : 一个新的链表,原链表上的所有节点都将挂载到该链表上
    5.    *  
    6.    */
    7.    static inline void  list_clear(struct list_node  *head,struct list_node  *list){
    8.        if(list_empty(head)) return;
    9.        list_cut_position(list,head,head->next);
    10.    }

    list_clear函数是list_cut_position函数的更彻底版本,它将一个完整的链表给切分到了另外一个链表中,同样是上图的两个链表初始图,经过调用list_clear函数后,两个链表将会总体调个个,图示如下:

    0?wx_fmt=png

    合并

    合并操作和上一节的切分操作很类似。两者的基本区分在于对于原有list的处理:如有list1和list2两个链表,如果是合并操作,将list1上的元素合并到list2的时候,并不会删除掉list2上原有的元素,而切分操作会将list2上的元素替换掉。

    1.    /**
    2.    * __list_splice - 合并链表,将list链表合并到prev和next指向的节点中间
    3.    * @list : 一个要被合并掉的链表
    4.    * @prev : 一个要合并其它链表的前驱指针
    5.    * @next : 一个要合并其它链表的后继指针
    6.    */
    7.    static inline void __list_splice(const struct list_node  *list,
    8.            struct list_node  *prev,
    9.            struct list_node  *next) {
    10.        struct list_node  *first = list->next;
    11.        struct list_node  *last = list->prev;
    12.        first->prev = prev;
    13.        prev->next = first;
    14.        last->next = next;
    15.        next->prev = last;
    16.    }

    私有的合并函数和list通常的私有函数一样没有参数校验,只是做了最基本的指针操作。

    1.    /**
    2.     * list_splice - 合并两个链表,将list合并到以head为头链表的前面,这是为了栈设计的
    3.     * @list: 要被合并的list
    4.     * @head:  添加到第一个链表中的位置
    5.     */
    6.    static inline void list_splice(const struct list_node  *list,
    7.            struct list_node  *head) {
    8.        if (!list_empty(list))
    9.            __list_splice(list, head, head->next);
    10.    }

    这是合并两个list,假设我们又list1和list2,分别如下图:

    0?wx_fmt=png

    执行list_splice函数,将list2合并到list1后,会将list2中的元素合并到list1的head指针后面,效果图如下:

    0?wx_fmt=png

    1.    /**
    2.     * list_splice_tail - 将list合并到head为头链表的尾部,这两个链表都是队列
    3.     * @list: 要被合并的list
    4.     * @head: 添加到一个列表中的位置.
    5.     */
    6.    static inline void list_splice_tail(struct list_node  *list,
    7.            struct list_node  *head) {
    8.        if (!list_empty(list))
    9.            __list_splice(list, head->prev, head);
    10.    }

    此函数和上面的list_splice函数一样,只是合并的位置不同。将list2合并到了list1的尾部,也就是list1的head指针prev指向处。效果图如下:

    0?wx_fmt=png

    上面两个API只是合并了链表,但是对于被合并的list2链表head元素的prev和next指针都没有进行处理,还是指向原来的元素。这样的操作可能会引起bug,所以linux kernel list增加了2个重置list2链表head的API,如下:

    1.    /**
    2.     * list_splice_init - 合并两个链表,并且重新初始化list为空链表
    3.     * @list: 要被合并的list
    4.     * @head:  添加到第一个链表中的位置
    5.     *
    6.    */
    7.    static inline void list_splice_init(struct list_node  *list,
    8.            struct list_node  *head) {
    9.        if (!list_empty(list)) {
    10.            __list_splice(list, head, head->next);
    11.            INIT_LIST_HEAD(list);
    12.        }
    13.    }

    同list_splice,只是会将list2链表head重新初始化。效果图如下:

    0?wx_fmt=png

    1.    /**
    2.     * list_splice_tail_init - 合并两个链表,并且重新初始化list为空链表
    3.     * @list: 要被合并的list
    4.     * @head: 添加到一个列表中的位置
    5.     *
    6.     */
    7.    static inline void list_splice_tail_init(struct list_node  *list,
    8.            struct list_node  *head) {
    9.        if (!list_empty(list)) {
    10.            __list_splice(list, head->prev, head);
    11.            INIT_LIST_HEAD(list);
    12.        }
    13.    }

    同list_splice_tail,只是会将list2链表head重新初始化。效果图如下:

    0?wx_fmt=png

    宏定义

    linux kernel list除了定义了一些函数API之外,还定义了一些宏。这些宏主要是为了方便链表的内部操作和给开发者更方便的使用链表。

    指针位置计算

    list_entry是linux kernel list提供的一个根据list_node元素在链表元素结构体类型中的指针和结构体自身来计算出该结构体实体的首地址。list_entry其实就是container_of的重定义。container_of在前面的章节已经有过介绍,如有不清楚的,可以参照前面的章节。

    1.    /**
    2.     * list_entry - 得到实体首地址
    3.     * @ptr:    list_node在实体中的指针.
    4.     * @type:    list_node所在的结构体类型
    5.     * @member:    list_node类型的元素在结构体中的名称.
    6.     */    
    7.    #define list_entry(ptr, type, member)  container_of(ptr,type,member)

    根据位置得到实体

    linux kernel list为了自身和第三方开发者的方便,也定义了根据位置信息获取实体的API。linux kernel list的代码定义如下:

    1.    /**
    2.     * list_first_entry - 得到链表中的第一个实体,即head的next指针指向的实体
    3.     * @ptr:    链表的head指针.
    4.     * @type:    链表实体的结构体类型.
    5.     * @member:    list_node的元素在结构体中的名称.
    6.     *
    7.     * 注意:链表不能为空。
    8.     */
    9.    #define list_first_entry(ptr, type, member) \
    10.            list_entry((ptr)->next, type, member)
    11.    /**
    12.     * list_last_entry - 得到链表中最后一个实体,即head的prev指针指向的实体
    13.     * @ptr:    链表的head指针.
    14.     * @type:    链表实体的结构体类型.
    15.     * @member:    list_node的元素在结构体中的名称.
    16.     *
    17.     * 注意:链表不能为空。
    18.     */
    19.    #define list_last_entry(ptr, type, member) \
    20.            list_entry((ptr)->prev, type, member)
    21.    /**
    22.     * list_first_entry_or_null - 得到链表中的第一个实体,即head的next指针指向的实体
    23.     *                                          如果链表为空,即返回空
    24.    * @ptr:    链表的head指针.
    25.     * @type:    链表实体的结构体类型.
    26.     * @member:    list_node的元素在结构体中的名称    
    27.     *
    28.     * 注意:该API是list_first_entry的一个扩展
    29.     */
    30.    #define list_first_entry_or_null(ptr, type, member) \
    31.            (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
    32.    /**
    33.     * list_next_entry - 得到当前链表中pos的下一个实体
    34.     * @pos:    list_node所在结构体的实体指针
    35.     * @member:    list_node在结构体中的名称
    36.     *
    37.    */
    38.    #define list_next_entry(pos,type, member) \
    39.            list_entry((pos)->member.next, type, member)
    40.    /**
    41.     * list_prev_entry - 得到当前链表中pos的前一个实体
    42.     * @pos:    list_node所在结构体的实体指针
    43.     * @member:    list_node在结构体中的名称
    44.     */
    45.    #define list_prev_entry(pos, type, member) \
    46.            list_entry((pos)->member.prev, type, member)

    遍历操作

    对链表的操作,最常用的应该就是遍历了吧。每当需要对所有的元素做一些操作的时候,遍历是必不可少的。linux kernel list也不例外。linux kernel list定义的代码如下:

    1.    /**
    2.     * list_for_each    -    往后遍历链表
    3.     * @pos:     list_node结构体的指针,用来作为遍历链表的游标.
    4.     * @head:    链表的head指针.
    5.     */
    6.    #define list_for_each(pos, head) \
    7.            for (pos = (head)->next; pos != (head); pos = pos->next)
    8.    /**
    9.     * list_for_each_prev - 前向遍历链表
    10.     * @pos:     list_node结构体的指针,用来作为遍历链表的游标
    11.     * @head:    链表的head指针.
    12.     */
    13.    #define list_for_each_prev(pos, head) \
    14.            for (pos = (head)->prev; pos != (head); pos = pos->prev)
    15.    /**
    16.     * list_for_each_safe -  安全的后向遍历链表,适用于在遍历的过程中需要删除实体的情况
    17.     * @pos:          list_node结构体的指针,用来作为遍历链表的游标
    18.     * @n:           另外一个list_node结构体的指针,临时存储当前遍历的游标
    19.     * @head:    链表的head指针.
    20.     */
    21.    #define list_for_each_safe(pos, n, head) \
    22.            for (pos = (head)->next, n = pos->next; pos != (head); \
    23.                    pos = n, n = pos->next)
    24.    /**
    25.     * list_for_each_prev_safe - 安全的前向遍历链表,适用于在遍历的过程中需要删除实体的情况    
    26.     * @pos:          list_node结构体的指针,用来作为遍历链表的游标
    27.     * @n:           另外一个list_node结构体的指针,临时存储当前遍历的游标
    28.     * @head:    链表的head指针.
    29.     */
    30.    #define list_for_each_prev_safe(pos, n, head) \
    31.            for (pos = (head)->prev, n = pos->prev; \
    32.                    pos != (head); \
    33.                    pos = n, n = pos->prev)
    34.    /**
    35.     * list_for_each_entry    -    顺序遍历链表中的实体元素
    36.     * @pos:     链表中实体元素的指针.
    37.     * @type : 链表中实体元素的结构体类型
    38.     * @head:    lise_node类型的链表头.
    39.     * @member:    list_node元素在实体结构式类型中的名称.
    40.     */
    41.    #define list_for_each_entry(pos,type, head, member) \
    42.            for (pos = list_first_entry(head, type, member) \
    43.                    &pos->member != (head); \
    44.                    pos = list_next_entry(pos, member))
    45.    /**
    46.     * list_for_each_entry_reverse - 倒序遍历链表中的实体元素.
    47.     * @pos:     链表中实体元素的指针.
    48.     * @type : 链表中实体元素的结构体类型
    49.     * @head:    lise_node类型的链表头.
    50.     * @member:    list_node元素在实体结构式类型中的名称
    51.     */
    52.    #define list_for_each_entry_reverse(pos, type,head, member) \
    53.            for (pos = list_last_entry(head, type, member); \
    54.                    &pos->member != (head);  \
    55.                    pos = list_prev_entry(pos, member))
    56.    /**
    57.     * list_prepare_entry - 准备一个实体指针,为list_for_each_entry_continue()中的pos
    58.    * @pos:     链表中实体元素的指针.
    59.     * @type : 链表中实体元素的结构体类型
    60.    * @member:    list_node元素在实体结构式类型中的名称.
    61.     *
    62.     * 准备一个实体指针来作为函数list_for_each_entry_continue()中的开始节点
    63.     */
    64.    #define list_prepare_entry(pos, type,head, member) \
    65.            ((pos) ? : list_entry(head, type, member))
    66.    /**
    67.     * list_for_each_entry_continue - 以链表中的任何一个元素(不包括当前元素)作为起始点遍历链表
    68.    * @pos:     链表中实体元素的指针,通常来自于list_prepare_entry.
    69.     * @head:    lise_node类型的链表头.
    70.     * @member:    list_node元素在实体结构式类型中的名称    
    71.     *
    72.     * 从当前pos所属的位置遍历链表
    73.     */
    74.    #define list_for_each_entry_continue(pos, head, member)  \
    75.            for (pos = list_next_entry(pos, member); \
    76.                    &pos->member != (head); \
    77.                    pos = list_next_entry(pos, member))
    78.    /**
    79.     * list_for_each_entry_continue_reverse - 以链表中的任何一个元素(不包括当前元素)作为起始点反向遍历链表
    80.    * @pos:     链表中实体元素的指针,通常来自于list_prepare_entry.
    81.     * @head:    lise_node类型的链表头.
    82.     * @member:    list_node元素在实体结构式类型中的名称
    83.     *
    84.     * 从当前pos所属的位置反向遍历链表.
    85.     */
    86.    #define list_for_each_entry_continue_reverse(pos, head, member) \
    87.            for (pos = list_prev_entry(pos, member); \
    88.                    &pos->member != (head); \
    89.                    pos = list_prev_entry(pos, member))
    90.    /**
    91.     * list_for_each_entry_from - 以当前元素位置遍历链表,便利中包括当前元素
    92.     * @pos:     链表中实体元素的指针
    93.     * @head:    lise_node类型的链表头.
    94.     * @member:    list_node元素在实体结构式类型中的名称
    95.     *
    96.     *
    97.     */
    98.    #define list_for_each_entry_from(pos, head, member)  \
    99.            for (; &pos->member != (head); \
    100.                    pos = list_next_entry(pos, member))
    101.    /**
    102.     * list_for_each_entry_safe - 安全的遍历链表中每一个元素,适用于在遍历的过程中需要删除实体的情况
    103.     * @pos:     遍历链表过程中的实体指针.
    104.     * @n:        遍历过程中临时存储下一个实体的指针
    105.     * @head:    链表中list_node类型的head指针.
    106.     * @member:    链表中list_node类型的原书名.
    107.     */
    108.    #define list_for_each_entry_safe(pos, n,type, head, member) \
    109.            for (pos = list_first_entry(head, type, member), \
    110.                    n = list_next_entry(pos, member); \
    111.                    &pos->member != (head);  \
    112.                    pos = n, n = list_next_entry(n, member))
    113.    /**
    114.     * list_for_each_entry_safe_continue - 安全的遍历链表中的每一个元素,不包括pos指向的当前元素,适用于在遍历的过程中需要删除实体的情况
    115.     * @pos:       遍历链表过程中的实体指针.
    116.     * @n:        遍历过程中临时存储下一个实体的指针
    117.     * @head:    链表中list_node类型的head指针.
    118.     * @member:    链表中list_node类型的原书名.
    119.     *
    120.     */
    121.    #define list_for_each_entry_safe_continue(pos, n, head, member)  \
    122.            for (pos = list_next_entry(pos, member),  \
    123.                    n = list_next_entry(pos, member); \
    124.                    &pos->member != (head); \
    125.                    pos = n, n = list_next_entry(n, member))
    126.    /**
    127.     * list_for_each_entry_safe_from - 安全的遍历链表中的每一个元素,包括pos指向的当前元素,适用于在遍历的过程中需要删除实体的情况
    128.     * @pos:       遍历链表过程中的实体指针.
    129.     * @n:        遍历过程中临时存储下一个实体的指针
    130.     * @head:    链表中list_node类型的head指针.
    131.     * @member:    链表中list_node类型的原书名.
    132.     *
    133.     */
    134.    #define list_for_each_entry_safe_from(pos, n, head, member)  \
    135.            for (n = list_next_entry(pos, member); \
    136.                    &pos->member != (head); \
    137.                    pos = n, n = list_next_entry(n, member))
    138.    /**
    139.     * list_for_each_entry_safe_reverse - 安全的反向遍历链表中的每一个元素,适用于在遍历的过程中需要删除实体的情况
    140.     * @pos:       遍历链表过程中的实体指针.
    141.     * @n:        遍历过程中临时存储下一个实体的指针
    142.     * @head:    链表中list_node类型的head指针.
    143.     * @member:    链表中list_node类型的元素名.
    144.     *
    145.     */
    146.    #define list_for_each_entry_safe_reverse(pos, n,type, head, member) \
    147.            for (pos = list_last_entry(head, type, member),  \
    148.                    n = list_prev_entry(pos, member);  \
    149.                    &pos->member != (head);  \
    150.                    pos = n, n = list_prev_entry(n, member))
    151.    /**
    152.     * list_safe_reset_next - 在list_for_each_entry_safe循环中重置next指针
    153.     * @pos :       list_for_each_entry_safe遍历链表过程中的实体指针
    154.     * @n:        遍历过程中临时存储下一个实体的指针
    155.     * @member:    链表中list_node类型的元素名
    156.     *
    157.     * 通常情况下,连边会被同时的更改,所以list_safe_reset_next是线程不安全的
    158.     * 例如:在循环体内锁被释放
    159.     * 如果pos游标指向的实体被固定在链表中,并且list_safe_reset_next不在被锁的循环体内调用,则出现异常。
    160.     * 调用list_safe_reset_next请一定要自行注意线程安全问题
    161.    */
    162.    #define list_safe_reset_next(pos, n, member) \
    163.            n = list_next_entry(pos, member)

    曾经看到过一句话,大概意思就是:最好的算法只维护结构,不操作实际数据。虽然已经忘记了看到的原话,也忘记了具体在哪里看到的。但唯一还能清楚的记起的就是这句话的意思。看到这句话的时候一直到很久远的以前,也就是在没有看到linux kernel list的实现之前,我一直不太明白这句话的含义,也不太明白到底应该怎么样才能优雅的去解决结构和数据之间的问题。诚然,那个时候是很小白的。但是自从看到了linux kernel list的设计和实现后,一切又豁然开朗了。从接触计算机开始,到大学的各种语言课程、数据结构课程、算法课程,双向列表几乎是必有的。但它们的实现却千篇一律而又统一,可以说,linux kernel list的设计和实现从某些程度上颠覆了很多人对于数据结构和算法的重新认知。

    linux kernel list,确实是一个不可多得的简洁而又优雅的设计和实现。

    原文地址: https://blog.csdn.net/Msy3TU4dFuUZ4/article/details/78930020

    展开全文
  • 很久之前研读过Linux的内核源码(后来终止了,水太深,吾辈驾驭不了),看到其中的内核数据结构,对链表的实现叹为观止,是迄今为止我见过的最为经典的链表实现(不是数据内嵌到链表中,而是把链表内嵌到数据对象中...

    很久之前研读过Linux的内核源码,看到其中的内核数据结构,对链表的实现叹为观止,是迄今为止我见过的最为经典的链表实现(不是数据内嵌到链表中,而是把链表内嵌到数据对象中)。现在再来回顾这个经典的数据结构。

    链表代码在头文件<linux/list.h>中声明(推荐Source Insight,源码版本:Linux-2.6.32.61,早期版本并没有引进这个list),其数据结构很简单有木有,直接就一个前后链表指针,前篇STL中list也有这么个结构

    1、链表的初始化

    struct list_head {
    	struct list_head *next, *prev;
    };
    初始化是一个双向链表,还是环状的,这和stl中的list是一样的。下面是形成一个空链表,list作为头指针(不是头节点)
    static inline void INIT_LIST_HEAD(struct list_head *list)
    {
    	list->next = list;
    	list->prev = list;
    }
    看看下面的宏生成一个头指针name
    #define LIST_HEAD_INIT(name) { &(name), &(name) }
    
    #define LIST_HEAD(name) \
    	struct list_head name = LIST_HEAD_INIT(name)
    两者合一实际就是下面这个样子
    struct list_head name = { &(name), &(name) }

    2、访问数据

    这恐怕就是Linux内核数据结构链表的最难理解的地方了吧,前面说了,内核链表不同于普通链表的是,它是内嵌到数据对象中,这么说来,就是同类型的对象内部都嵌有这个链表,并且是通过这个链表穿针引线在一起,我们关心的是对象中的数据内容,那么究竟是如何通过对象内部的链表来访问其中的数据内容的呢?

    #define list_entry(ptr, type, member) \
    	container_of(ptr, type, member)
    宏定义转到:

    #define container_of(ptr, type, member) ({          \
    	const typeof(((type *)0)->member)*__mptr = (ptr);    \
    	(type *)((char *)__mptr - offsetof(type, member));})
    咋呼了一下,还有个:

    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    这一大串的指针操作,别急,从后往前一步步分析:
    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    将0x0地址强制转换为TYPE*类型,然后取TYPE中的成员MEMBER地址,因为起始地址为0,得到的MEMBER的地址就直接是该成员相对于TYPE对象的偏移地址了。

    所以该语句的功能是:得到TYPE类型对象中MEMBER成员的地址偏移量。

    #define container_of(ptr, type, member) ({          \
    	const typeof(((type *)0)->member)*__mptr = (ptr);    \
    	(type *)((char *)__mptr - offsetof(type, member));})
    这个‘怪物’,先看第一条:const typeof(((type *)0)->member)*__mptr = (ptr); 首先将0x0转换为TYPE类型的指针变量,再引用member成员,typeof(x)返回的是x的数据类型,所以typeof(((type *)0)->member)返回的就是member成员的数据类型,该语句就是将__mptr强制转换为member成员的数据类型,然后再将ptr赋给它。ptr本来就是指向member的指针;
    说白了,就是定义一个member成员类型的指针变量,然后将ptr赋给它。

    好,来看下一条语句:
    先将__mptr强制转换为char*类型(因为char* 类型进行加减的话,加减量为sizeof(char)*offset,char占一个字节空间,这样指针加减的步长就是1个字节,实现加一减一。)实现地址的精确定位,如果不这样的话,假如原始数据类型是int,那么这减去offset,实际上就是减去sizeof(int *)*offset 的大小了。
    所以整体意思就是:得到指向type的指针,已知成员的地址,然后减去这个成员相对于整个结构对象的地址偏移量,不就得到这个数据对象的地址么

    最后看

    #define list_entry(ptr, type, member) \
    	container_of(ptr, type, member)
    有了前面的剖析,好理解了,该宏定义作为右值,返回type类型对象的地址。

    type->member,表明member是type中的成员,所以可以得知member是内嵌的链表,type则是对象指针,那么ptr是链表类型指针,并且是属于那个穿针引线的链表中的某一个链表节点,所有的对象结构都挂在ptr所在的链表上。

    该宏定义可以返回ptr对应链表节点的对象的地址。关键是对应,找到的对象的地址是ptr这个链表所对应的那个对象的地址。ptr和member之间的关系就是,ptr是member类型的指针。

    其实上面就是地址的强制转换,然后得到偏移量之类的,就是指针,而且上面有个特点,那就是跟结构体中的内存对齐无关。

    这里额外补充一个关于指针方面的:

    (*(void(*)())0)();
    对于这类,从里往外分析,谁叫人家优先级高呢。

    先看最里面void(*)(),定义一个函数指针,无参无返回值,

    (void(*)())0,将0强制转换为函数指针,这样0成了一个地址,而且是函数地址,就是说有个函数存在首地址为0 的一段区域内。

    (*(void(*)())0),取0地址开始的一段内存里面的内容,其内容就是保存在该区域内的函数。

    (*(void(*)())0)(); 调用该函数。

    所以整个代码的意思就是:调用保存在0地址处的函数(初始化)。扯远了,论指针的重要性。
    3、遍历链表(实际是得到指定链表节点对应的数据对象结构)
    有了前面的定位某个结构地址,遍历就好办了。

    得到第一个节点元素地址

    #define list_first_entry(ptr, type, member) \
    	list_entry((ptr)->next, type, member)
    上面传入的ptr是将各个type对象串起来的链表的头指针,ptr->next 就是该链表的第一个节点。上面返回值就是挂载在第一个节点上的对象地址。

    对象结构就是像下面这样挂载在链表上:


    访问第一个对象就是:

    type *type_first_ptr = list_first_entry(type_list, type, list);
    /*
    	type_list为链表头指针,type为对象结构,list为type结构内的链表
    */
    遍历所有数据对象就是:
    #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))
    /*
    实际上就是一个for循环,循环内部由用户自己根据需要定义
    初始条件:pos = list_entry((head)->next, typeof(*pos), member); pos为第一个对象地址
    终止条件:&pos->member != (head);pos的链表成员不为头指针,环状指针的遍历终止判断
    递增状态:pos = list_entry(pos->member.next, typeof(*pos), member) pos为下一个对象地址
    所以pos就把挂载在链表上的所有对象都给遍历完了。至于访问对象内的数据成员,有多少个,用来干嘛用,则由用户
    根据自己需求来定义了。
    */
    4、添加元素
    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的前面。
    //head是头指针
    //头节点后添加元素,相当于添加头节点,可实现栈的添加元素
    //new添加到head之后,head->next之前
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head, head->next);
    }
    
    //头节点前添加元素,因为是环状链表所以相当于添加尾节点,可实现队列的添加元素
    //new添加到head->prev之后,head之前
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head->prev, head);
    }
    5、删除元素
    //prev和next两个链表指针构成双向链表关系
    static inline void __list_del(struct list_head * prev, struct list_head * next)
    {
    	next->prev = prev;
    	prev->next = next;
    }
    
    //删除指定元素,这是一种安全删除方法,最后添加了初始化
    static inline void list_del_init(struct list_head *entry)
    {
    	//删除entry节点
    	__list_del(entry->prev, entry->next);
    	//entry节点初始化,是该节点形成一个只有entry元素的双向链表
    	INIT_LIST_HEAD(entry);
    }
    6、替换元素
    //调整指针,使new的前后指针指向old的前后,反过来old的前后指针也指向new
    //就是双向链表的指针调整
    static inline void list_replace(struct list_head *old,
                                    struct list_head *new)
    {
    	new->next = old->next;
    	new->next->prev = new;
    	new->prev = old->prev;
    	new->prev->next = new;
    }
    
    //替换元素,最后将old初始化一下,不然old还是指向原来的两个前后节点(虽然人家不指向他)
    static inline void list_replace_init(struct list_head *old,
                                         struct list_head *new)
    {
    	list_replace(old, new);
    	INIT_LIST_HEAD(old);
    }
    7、移动元素
    //移动指定元素list到链表的头部
    static inline void list_move(struct list_head *list, struct list_head *head)
    {
    	__list_del(list->prev, list->next);//删除list元素
    	list_add(list, head);//将list节点添加到head头节点
    }
    
    /**
    * list_move_tail - delete from one list and add as another's tail
    * @list: the entry to move
    * @head: the head that will follow our entry
    */
    //移动指定元素list到链表的尾部
    static inline void list_move_tail(struct list_head *list,
                                      struct list_head *head)
    {
    	__list_del(list->prev, list->next);
    	list_add_tail(list, head);
    }
    在实际应用编程时,我们添加和删除链表操作,中间的待处理链表都是对象结构中的链表。举个小例子,使用内核数据结构list来编程的时候,添加元素应该是这样:
    list_add(&(newobj.list), &(type_list.list));
    清楚前面那个对象结构挂载在链表上的那个图就好办了。









    展开全文
  • linuxlist 的使用

    2019-06-14 13:48:07
    2019独角兽企业重金招聘Python工程师标准>>> ...

      Linux 内核使用的 list 在这里 http://isis.poly.edu/kulesh/stuff/src/klist/

     

    #include <stdio.h>
    #include <stdlib.h>
    #include "ss.h"
    
    struct mylist
    {
        struct list_head list;
        int a;
    };
    
    int main()
    {
        struct mylist test_list;
        struct mylist *l;
        struct list_head *t, *p;
        INIT_LIST_HEAD(&test_list.list); //初始化。。
    
        l = malloc(sizeof(struct mylist));  //添加元素 注意要malloc
        l->a = 1;
        list_add(&l->list, &test_list.list);
        l = malloc(sizeof(struct mylist));
        l->a = 2;
        list_add(&l->list, &test_list.list);
        l = malloc(sizeof(struct mylist));
        l->a = 3;
        list_add(&l->list, &test_list.list);
    
        l = malloc(sizeof(struct mylist));
        l->a = 4;
        list_add(&l->list, &test_list.list);
    
        //删除一个元素 注意不能用 list_for_each 
        list_for_each_safe(t, p, &test_list.list)
        {
            int a = list_entry(t, struct mylist, list)->a;
            //printf("%d\n", a);
            list_del_init(t);
            break; //跳出循环
        }
    
        //遍历  输出是反向的 也就是说 最后加入的 最先被打印出来
        list_for_each(t, &test_list.list)
        {
            int a = list_entry(t, struct mylist, list)->a;
            printf("%d\n", a);
        }
    
        // delete list
    
        list_for_each_safe(t, p, &test_list.list)
        {
            struct mylist *tmp = list_entry(t, struct mylist, list);
            list_del(t);
            free(tmp);
        }
        return 0;
    }

    转载于:https://my.oschina.net/sincoder/blog/135139

    展开全文
  • linux/list.h

    千次阅读 2013-01-06 17:38:31
    linux/list.h中,双向循环链表的结构体定义: struct list_head {  struct list_head *next, *prev; }; 可以看到,这个结构中不包括数据域。也就是说,这个结点本身并不保存什么数据...
  • linux内核中list用法

    千次阅读 2018-08-16 14:42:08
    &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;...
  • linux——list.h

    千次阅读 2020-05-07 10:01:21
    *linux中的头文件list.h 在Linux的源码中有一个自己为建立链表而写的链表头文件,以后可以直接调用里面的函数来使用链表。 list.h在linux中的路径为/usr/src/kernels/include/linux。不同的版本可能不一样。 list...
  • 常用linux命令list总结(一)

    千次阅读 2018-02-26 10:44:33
    1. 文件和目录1.1 cd 进入到某一特定目录常用如下:cd/home 进入 '/ home' 目录' cd .. 返回上一级目录 cd ../.. 返回上两级目录cd 进入个人的主目录(/root /home/user)cd ~ 进入个人的主目录 cd - 返回上次所在的...
  • linux内核中的list

    千次阅读 2017-01-06 19:01:41
    本文详细分析了 3.4.112 内核中链表结构的实现,并通过图像和实例进行了详尽的讲解。
  • Linux如何创建用户并配置FTP权限

    万次阅读 2016-07-26 17:36:38
    Linux下创建用户是很easy的事情了,只不过不经常去做这些操作,时间久了就容易忘记,顺便配置一下FTP。声明:使用Linux版本release 5.6,并以超级管理员root身份运行。  1.创建用户,并指定分组和主目录 useradd ...
  • Linux系统下yum命令查看安装了哪些软件包: $yum list installed //列出所有已安装的软件包 yum针对软件包操作常用命令: 1.使用YUM查找软件包 命令:yum search 2.列出所有可安装的软件包 命令:yum list 3....
  • linux Argument list too long错误解决方法

    万次阅读 2014-11-27 23:38:05
    linux Argument list too long错误解决方法 今日需要删除/tmp目录下的所有文件,文件数量比较多。 ls -lt /tmp | wc -l 385412 使用 rm * 后,系统提示错误 Argument list too long 原因是在linux下,试图传太...
  • Linux系统源文件sources.list

    千次阅读 2017-11-20 21:57:12
    APT的软件源定义来自/etc/apt/sources.list文件(源文件),记录了Linux系统下所有软件包的来源。 /etc/apt/sources.list   修改后,执行以下命令使sources.list的发动生效。 source /etc/apt/sources.list   ...
  • Linux中“Argument list too long”解决方法
  • error: expected specifier-qualifier-list before ‘uint8_t’and error: expected specifier-qualifier-list before ‘uint16_t’
  • 查询linux的ftp的用户名和密码

    万次阅读 2017-12-12 09:36:05
    默认vsftpd路径是/etc/vsftpd/,那么[root@bj ~]# cd /etc/vsftpd/[root@bj vsftpd]# lschroot_list ftpusers user_conf user_list vsftpd.conf vsftpd_conf_migrate.sh vsftp.tar.gz vuser_passwd.db vuser_passwd.
  • linux中安装字体

    万次阅读 2018-07-25 19:00:41
    要查看系统中已经安装的字体,我们可以使用fc-list命令进行查看。如果系统中没有该命令的话,我们需要先安装相关的软件包。 在centos上,使用如下命令进行安装: yum install -y fontconfig mkfontscale 在...
  • linux中下载并安装FTP服务器

    万次阅读 2018-07-24 23:40:38
    企业中linux搭建ftp服务器还是很实用的,所以本文针对centoos7和centoos6搭建服务器教程做个总结。 二、具体 1、显示如下图则表示已安装 vsftp软件。如果未显示则需要安装vsftpd软件。 如果没有则通过yarm源...
  • Linux中的ftp基本使用

    万次阅读 2018-11-03 01:22:40
    什么是ftp? 安装和配置环境 服务端 启动并查看ftp服务 查看ftp的配置文件 客户端 安装lftp软件 vsftpd服务的配置参数 配置文件:/etc/vsftpd/vsftpd.conf 报错id解析: ...anonymous_...
  • linux安装中文字体

    万次阅读 2016-12-16 18:45:28
    要查看系统中已经安装的字体,我们可以使用fc-list命令进行查看。如果系统中没有该命令的话,我们需要先安装相关的软件包。 在centos上,使用如下命令进行安装: yum install -y fontconfig mkfontscale 在...
1 2 3 4 5 ... 20
收藏数 589,662
精华内容 235,864
关键字:

linux list