kernel list_head 双向链表

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

#define LIST_HEAD_INIT(name) { &(name), &(name) }
//初始化next , prev 指向自己
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

需要注意的一点是，头结点head是不使用的，这点需要注意。

没有数据域！所以看到这个结构的人第一反应就是我们怎么访问数据？

其实list_head不是拿来单独用的，它一般被嵌到其它结构中，如：

struct file_node{
　　char c;
　　struct list_head node;
};

此时list_head就作为它的父结构中的一个成员了，当我们知道list_head的地址（指针）时，我们可以通过list.c提供的宏 list_entry 来获得它的父结构的地址。下面我们来看看list_entry的实现:

list_entry

#define list_entry(ptr,type,member)\
　　container_of(ptr,type,member)
 
#define offsetof(TYPE,MEMBER) ((size_t)&((TYPE *)0)->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 )

这里用到一个取址运算符
(TYPE *)0 它表示将 0地址强制转换为TYPE类型，((TYPE *)0）-> MEMBER 也就是从0址址找到TYPE 的成员MEMBER 。

将实参代入

offset( struct file_node, node )；
( (size_t) & ((struct file_node*)0）-> node )；

struct file_node *p = NULL;
&p->node;

即求 p 的成员 node的地址，只不过p 为0地址，从0地址开始算成员node的地址，也就是 成员 node 在结构体 struct file_node中的偏移量。offset宏就是算MEMBER在TYPE中的偏移量的。

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

这个宏是由两个语句组成，最后container_of返回的结果就是第二个表达式的值。

这里__mptr为中间变量，这就是list_head指针类型，它被初始化为ptr的值，而ptr就是当前所求的结构体中list_head节点的地址。为什么要用中间变量，这是考虑到安全性因素，如果传进来一个ptr++，所有ptr++放在一个表达式中会有副作用，像 (p++)+(p++)之类。
(char*)__mptr 之所以要强制类型转化为char是因为地址是以字节为单位的，而char的长度就是一个字节。

container_of的值是两个地址相减，
刚说了__mptr是结构体中list_head节点的地址，offset宏求的是list_head节点MEMBER在结构体TYPE中的偏移量，那么__mptr减去它所在结构体中的偏移量，就是结构体的地址。
所以list_entry(ptr,type,member)宏的功能就是，由结构体成员地址求结构体地址。其中ptr 是所求结构体中list_head成员指针，type是所求结构体类型，member是结构体list_head成员名。

双向链表操作

list_add()

双向链表的插入操作 --

__list_add这个函数, 只能是用于知道前后结点, 插入在这两个中间.

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;
}

list_add() 这个就是将新添加的链表放在new这里. 要注意的是, new必须是list_head的结构, head是头部, head->next就是下一个, 那么这个函数的用法就是, 将新元素, 放到了链表的头端.

static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

添加到尾部, 就是使用head->prev, 然后head作为下一个.

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

list_del()

从list中删除结点——

static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    next->prev = prev;
    prev->next = next;
}

删除一个链表的尸体, 只要把前和后相连接起来就好了. 这里也是只用于知道内部的结点的时候才能用

static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = (void *) 0;
    entry->prev = (void *) 0;
}

list_empty()

判断链表是否为空（如果双向链表head为空则返回真，否则为假）—

list_for_each()

list_for_each_safe()

因此之遍历链表不删除结点时，可以使用list_for_each()，而当由删除结点操作时，则要使用list_for_each_safe()。

#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
        pos = n, n = pos->next)

你能够在循环结构里面安全的删除所遍历的元素

链表是在你的数据项里面的一个成员.
你可以将struct list_head 这个结构体放在任何地方
你可以将struct list_head 变量命名为任意的名字
你可以有多个list

struct file_node{
　　char c;
　　struct list_head node;
};

struct file_node mylist;
INIT_LIST_HEAD(&mylist.node);

tmp= (struct file_node *)malloc(sizeof(struct file_node));

list_add(&(tmp->node), &(mylist.node));


list_for_each(pos, &mylist.node){
    tmp= list_entry(pos, struct file_node, node);
    
     printf("c= %d \n", tmp->c);

    }

clipboard.png clipboard1.png clipboard2.png