linuxlist详解
在linux内核中list的使⽤很频繁，使⽤管理对象，下⾯来详细说明其⽤法。
1链表结构定义
⾸先看链表的定义，位于：include\linux\types.h
1struct list_head {
2struct list_head *next, *prev;
3 };
⼀般将该数据结构嵌⼊到其他的数据结构中，从⽽使得内核可以通过链表的⽅式管理新的数据结构，⽐如struct device中：
1struct device {
2struct device        *parent;
3
4struct device_private    *p;
5
6struct kobject kobj;
7    ...
8struct list_head    devres_head;//嵌⼊的链表
9
10struct klist_node    knode_class;
11struct class        *class;
12const struct attribute_group **groups;    /* optional groups */
13
14void    (*release)(struct device *dev);
15struct iommu_group    *iommu_group;
16 }
2 链表的定义和初始化
有两种⽅式来定义和初始化链表头：
（1）利⽤宏LIST_HEAD
（2）利⽤宏LIST_HEAD_INIT
例如定义链表mylist：
⽅法1：定义并初始化链表
LIST_HEAD(mylist);
⽅法2：先定义再初始化链表
struct list_head mylist;  // 定义⼀个链表
INIT_LIST_HEAD(&mylist); // ⽤INIT_LIST_HEAD函数初始化链表。
看宏LIST_HEAD就知道就是⽤宏INIT_LIST_HEAD
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
再看宏INIT_LIST_HEAD的定义：
#define LIST_HEAD_INIT(name) { &(name), &(name) }
定义的mylist链表，宏展开就是
struct list_head mylist = { &(mylist), &(mylist) };
链表list_head结构只有两个成员：next和prev。next和prev都被赋值为链表mylist的地址，也就是说，链表初始化后next和prev都是指向⾃⼰的。
对于struct device 中嵌⼊的list成员devres_head的初始化如下这样：
struct device mydevice;
INIT_LIST_HEAD(&mydevice.list); //该函数简单地将list成员的prev和next指针指向⾃⼰。
所以链表结点在初始化时，就是将prev和next指向⾃⼰。对链表的初始化⾮常重要，因为如果使⽤⼀个未被初始化的链表结点，很有可能会导致内核异常。
3 list的操作：
对链表常⽤的操作，⼀般就是添加、删除、遍历等。内核还会有其他的操作，⽐如替换、移动等，但这些的操作⼀般都是以添加、删除等操
作为基础完成的。
3.1 链表的添加
添加有两种：
（1）list_add 将⼀个新链表结点插⼊到⼀个已知结点的后⾯；
（2）list_add_tail 将⼀个新链表结点插⼊到⼀个已知结点的前⾯
看他们的定义：
1/**
2 * list_add - add a new entry
3 * @new: new entry to be added
4 * @head: list head to add it after
5 *
6 * Insert a new entry after the specified head.
7 * This is good for implementing stacks.
8*/
9static inline void list_add(struct list_head *new, struct list_head *head)
10 {
11    __list_add(new, head, head->next);
12 }
13
14/**
15 * list_add_tail - add a new entry
16 * @new: new entry to be added
17 * @head: list head to add it before
18 *
19 * Insert a new entry before the specified head.
20 * This is useful for implementing queues.
21*/
22static inline void list_add_tail(struct list_head *new, struct list_head *head)
23 {
24    __list_add(new, head->prev, head);
25 }
上⾯链表添加的两种⽅式是以不同的参数调⽤_list_add，看_list_add的定义
1static inline void __list_add(struct list_head *new,
2struct list_head *prev,
3struct list_head *next)
4 {
5    next->prev = new;
6new->next = next;
7new->prev = prev;
8    prev->next = new;
9 }
_list_add函数将new结点插⼊到prev结点和next之间。
（1）list_add函数中以new、head、head->next为参数调⽤__list_add，将new结点插⼊到head和head->next之间，即是把new结点插⼊到已知结点head的后⾯。
（2）list_add_tail函数则以new、head->prev、head为参数调⽤__list_add，将new结点插⼊到head->prev和head之间，即是把new结点插⼊到已知结点head的前⾯。
3.2 链表的删除
删除也是有两种⽅式：
（1）list_del 删除链表中的⼀个结点。
（2）list_del_init 删除链表中的⼀个结点，并初始化被删除的结点（使被删除的结点的prev和next都指向⾃⼰）；
分别看它们的定义：
1static inline void list_del(struct list_head *entry)
2 {
3    __list_del(entry->prev, entry->next);
4    entry->next = LIST_POISON1;
5    entry->prev = LIST_POISON2;
6 }
7
8/**
9 * list_del_init - deletes entry from list and reinitialize it.
10 * @entry: the element to delete from the list.
11*/
12static inline void list_del_init(struct list_head *entry)
13 {
14    __list_del_entry(entry);
15    INIT_LIST_HEAD(entry);
16 }
_list_del_entry
1static inline void __list_del_entry(struct list_head *entry)
2 {
3    __list_del(entry->prev, entry->next);
4 }
所以两者都是调⽤了_list_del，让prev结点和next结点互相指向。
1/*
2 * Delete a list entry by making the prev/next entries
3 * point to each other.
4 *
5 * This is only for internal list manipulation where we know
typeof的用法6 * the prev/next entries already!
7*/
8static inline void __list_del(struct list_head * prev, struct list_head * next)
9 {
10    next->prev = prev;
11    prev->next = next;
12 }
（1）list_del函数中以entry->prev和entry->next为参数调⽤__list_del函数，使得entry结点的前、后结点绕过entry直接互相指向，然后将entry结点的前后指针指向LIST_POISON1和LIST_POISON2，从⽽完成对entry结点的删除。此函数中的LIST_POISON1和LIST_POISON2是内核的处理定义如下。⼀般删除entry后，应该让entry的prev和next指向NULL的。
1/*
2 * These are non-NULL pointers that will result in page faults
3 * under normal circumstances, used to verify that nobody uses
4 * non-initialized list entries.
5*/
6#define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
7#define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)
（2）list_del_init函数将entry结点删除后，与_list_del不同的是：还会对entry结点初始化，使entry结点的prev和next都指向其⾃⼰。
4 链表在内核中的应⽤
list_for_each_entry
⾸先看定义，位于：include\linux\list.h
1/**
2 * list_for_each_entry    -    iterate over list of given type
3 * @pos:    the type * to use as a loop cursor.
4 * @head:    the head for your list.
5 * @member:    the name of the list_struct within the struct.
6*/
7#define list_for_each_entry(pos, head, member)                \
8for (pos = list_entry((head)->next, typeof(*pos), member);    \
9          &pos->member != (head);    \
10          pos = list_entry(pos-&, typeof(*pos), member))
实际上是⼀个 for 循环，⽤传⼊的 pos 作为循环变量，从表头 head 开始，逐项向后（next ⽅向）移动 pos，⼀直到回到head.。
（1）变量的初始化：pos = list_entry((head)->next, typeof(*pos), member)，每次pos拿到的都是链表中⼀个成员，注意这个成员实际上是⼀个结构体
（2）执⾏条件  &pos->member != (head)，确定拿到的成员不是head，是head的话，表⽰list已遍历完。
（3）每循环⼀次执⾏ pos = list_entry(pos-&, typeof(*pos), member))，是pos指定链表中下⼀个成员，注意其实际上还是结构体
以上中⽤到typeof()，它是取变量的类型，这⾥是取指针pos所指向数据的类型。
4.1 看宏list_entry的定义：
1/**
2 * list_entry - get the struct for this entry
3 * @ptr:    the &struct list_head pointer.
4 * @type:    the type of the struct this is embedded in.
5 * @member:    the name of the list_struct within the struct.
6*/
7#define list_entry(ptr, type, member) \
8    container_of(ptr, type, member)
4.2 调⽤了container_of。
1/**
2 * container_of - cast a member of a structure out to the containing structure
3 * @ptr:    the pointer to the member.
4 * @type:    the type of the container struct this is embedded in.
5 * @member:    the name of the member within the struct.
6 *
7*/
8#define container_of(ptr, type, member) ({            \
9const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
10    (type *)( (char *)__mptr - offsetof(type,member) );})
container_of是根据⼀个结构体变量中的⼀个成员变量指针ptr，来获取指向这个结构体变量type的指针。member是结构体type中成员ptr的变量名。下⾯分解⼀步⼀步分析：
4.2.1 先分析第⼀句：const typeof( ((type *)0)->member ) *__mptr = (ptr);
（1）(type *)0) 将0强转为⼀个地址，这个地址(0x0000)指向的是类型type的数据，就是指向结构体。当然，这只是个技巧，并不是真的在地址0x0000存放了数据。
（2）((type *)0)->member ：‘->’是指针指取结构体成员的操作。指针就是刚才通过0强转的地址，即结构体指针。相当于地址0x0000 是结构体类型type的⾸地址，通过->’取其中的成员变量member。
（3）typeof( ((type *)0)->member ) *__mptr = (ptr)：拿到了member成员的类型，然后定义⼀个指针变量__mptr，指向的类型就是结构体成员member的类型，初始化值为ptr。
4.2.2 再分析第⼆句：(type *)( (char *)__mptr - offsetof(type,member) );
（1）offsetof(type,member) ：定义如下：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
((TYPE *)0) ：将整型常量0强制转换为TYPE型的指针，即结构体类型。且这个指针指向的地址为0，也就是将地址0开始的⼀块存储空间映射为TYPE型的对象。
((TYPE *)0)->MEMBER ：指向结构体中MEMBER成员。
&((TYPE *)0)->MEMBER)：对结构体中MEMBER成员进⾏取址，⽽整个TYPE结构体的⾸地址是0，这⾥获得的地址就是MEMBER成员在TYPE中的相对偏移量。
(size_t) &((TYPE *)0)->MEMBER：最后将这个偏移量强制转换成size_t型数据也就是⽆符号整型。
所以offsetof的作⽤就是求出结构体成员变量member在结构体中的偏移量。
（2）(char *)__mptr - offsetof(type,member)：member类型的指针减去member在结构体中的偏移量，就是结构体的起始位置，即指向结构体。
⾄此综上所述，list_entry 也就是container_of的作⽤就是：根据结构体中的成员变量和此变量的指针，拿到结构体的指针。
4.3 再回到list_for_each_entry
1#define list_for_each_entry(pos, head, member)                \
2for (pos = list_entry((head)->next, typeof(*pos), member);    \//链表中的成员也是结构体，根据结构体成员head->next获取此链表成员
3          &pos->member != (head);    \                            //确认此时拿到的链表成员不是链表的头成员
4          pos = list_entry(pos-&, typeof(*pos), member))//获取链表中下⼀个成员结构体
list_for_each_entry在内核中的应⽤也很常见，通常⽤于遍历某⼀个链表。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。