list.h分析（1）

  链表是Linux内核中醉简单、最常用的一种数据结构。而对双向链表的所有操作都存储在list.h头文件中，list.h在include/linux目录下，这两天我仔细分析了一下该文件，把我对它的理解记录下来，和大家分享一下。

 1， 双向链表的结构：

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

   这是个不含数据域的链表，只是做一个相互连接的作用，定义了一个指向后一元素的指针next和指向前一元素的指针prev。定义这样一个没有存储数据的数据结构，我觉得好处是可以广泛嵌套使用，把它当做一座桥，只是连接，然后再配合上其他变量来存储数据，一起形成一个结构体。嵌入到任何结构中.例如：

struct list_head{
char name[20];
struct list_head list;
};

2.链表的声明和初始化

#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)
{
    list->prev=list;
    list->next=list;
}

    前两个是宏定义的的方法，最后一个是函数方法。第二个宏定义是一个结构体的赋初值，调用了第一个宏，再看第一个宏定义，就是说把name这个list_head类型的结构体的第一个元素赋值为name的地址，第二个元素也赋值为name的地址，再结合上面的结构体的定义，就是说把name->next和name->prev都赋值为name自己，也就是指向自身，这样就是初始化好了一个双向链表的结点。而第三个用函数的方法就是直接形成了一个空链表，和前两个宏定义的功能一样。

3.链表的添加

static inline void list_add(struct list_head *new, struct list_head *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);
        }

     前一个函数在头结点后添加，实现了栈的添加元素，即“先进后出”。后一个函数在头结点前添加，实现了队列的添加元素，即“先进先出”。它们同时调用了__list_add(new,head->prev,head),下面来看一下这个函数：

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

    一般函数的前面加“__”表示只有系统程序才可以调用该函数，用户级的程序是不可以直接对其进行操作的。static加在函数前，表示这个函数是静态函数（指该函数的作用域仅局限于本文件），inline说明这个函数对编译程序是可见的，也就是说，编译程序在调用这个函数时就立即展开该函数。这个函数用了一个基本的双向链表的添加功能。

4.链表元素的删除

    list.h有如下代码：

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)
{
    __list_del(entry->prev,entry->next);
    INIT_LIST_HEAD(entry);
}

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

  这也是一个调用关系，第二个函数将变量entry的前后两个结点prev和next传递给第一个函数，实现了元素的删除。第一个函数的意思其实很好懂，用传进去的结点prev和next分别首尾连接起来，将中间的结点断开。但是光把前后结点相连还没有彻底完成删除，还要对待删除结点进行一些操作，后面的两个函数的不同点就是处理这个待删除节点的操作时不一样的。

   第二个函数是删除的结点指向自己，调用了初始化那个函数，不让他们乱指，这是一种安全的删除方式。

   第三个函数是让删除结点的next和prev赋值为LIST_POISON1和LIST_POISON2，这两个是宏定义的常量，确切的说就是把他们指向一个常人不用的地址，也就是其屏蔽掉。不能切入到链表中。但是这属于不安全的删除方式。

  这两个常量在在include/linux/poison.h中定义的，源代码如下：

#ifdef CONFIG_ILLEGAL_POINTER_VALUE
#define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE,UL)
#else
#define POISON_POINTER_DELTA 0
#endif

#define LIST_POISON1 ((void *) 0x00100100   POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x00200200   POISON_POINTER_DELTA)

5.链表的遍历

  链表的宏也用到调用，如下代码：

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

    该宏定义是让定义了一个struct list_head 的指针pos,让其不断往后移动。可是只是遍历链表的指针根本就无法得到链表中的其他元素，下面我们来看下面的定义：

#define list_entry(ptr,type,member)\
  container_of(ptr,type,member)

这个定义调用了三个参数，其中ptr指针获取type结构的地址，也就是指向type的指针。其中ptr是指向member成员的指针。这个list_entry宏就是再调用container_of宏，,我们来看看container_of:

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

    这个看起来有点抓狂，别急，我们来一点点分析它。首先我们看到一个比较陌生的函数offsetof,我们再来看看offsetof.

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

    现在我们一点点往上推，（（TYPE *）0）->MEMBER现将0强制转化成为一个指向TYPE的指针。然后就是提取type类型中的member成员，那么&((TYPE *)0)->MEMBER)得到member成员的地址，再强制转换成size_t类型（unsigned int）。但是这个地址很特别，因为TYPE类型是从0×0开始定义的，那么我们现在得到的这个地址就是member成员在TYPE数据类型中的偏移量。

    再往上推，第一句：const typeof( ((type *)0)->member ) *__mptr = (ptr);首先将0转化成type类型的指针变量（这个指针变量的地址为0×0），然后再引用member成员（对应就是((type *)0)->member )）。注意这里的typeof（x），是返回x的数据类型，那么 typeof( ((type *)0)->member )其实就是返回member成员的数据类型。那么这条语句整体就是将__mptr强制转换成member成员的数据类型，再将ptr的赋给它(ptr本身就是指向member的指针)。

    第二句： (type *)( (char *)__mptr  –  offsetof(type,member) ), 把上面得到的__mptr减去成员member的偏移量，然后强制类型转化成指向type型空间的指针，也就是地址，也就是得到了type类型的首地址，也就得到了一个指针，可以用它做“->”运算，得到其结构体中的任意一个值.

   所以container_of的作用就是得到这个type类型的结构体的指针，然后通过它获取其中的元素.

   下面的就迎刃而解了：

#define list_first_entry(ptr,type,member)\
  container_of((ptr))->next,type,member)

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

   这个是便利宏的安全版，我们看它安全在那里？它多了一个与pos同类型的n，每次将下一个结点的指针暂存起来，防止pos被释放时引起的链表断裂。

   今天就先记到这儿吧，后面我将会将其用于到用户态进行更加一步的解释。