近期在Linux内核中使用了很多的链表操作，发现Linux设计的链表工具很精妙，因此总结一下，以备今后查看。

Linux内核使用的链表

  Linux内核中有大量的地方需要链表操作，但是内核仅用一套工具函数和宏就完成了任何数据结构在所有情况下的链表操作。这个实在是很值得学习和借鉴！

结构体定义和使用

  Linux内核中使用的这个链表是双向循环链表，结构体很简单只含有一个next指针和prev指针。

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

  它的使用方式就是包含进需要串成链表的数据结构中, 比如：

struct example {
    char *name;
    int age;
    struct list_head *list;
}

  才开始看的时候可能会有疑问，既然list_head只是结构体的一个成员，那么用它串成的双向循环链表怎么访问结构体的其它成员呢。这个正是该链表工具最屌的地方，它通过一个宏，用计算偏移量的方式来完成从 list_head 成员地址获取结构体地址！下面慢慢来说。

相关的操作函数和宏

一、list_entry(link, type, member)
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

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

#ifndef container_of
/**
  * 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)); })
#endif

  这个宏通过list_head成员地址获取结构体地址。其中，link为指向结构体list_head成员的指针，type为结构体类型，member为结构体中list_head类型的变量名，下面用一个例子说明：

//假设有一个example类型的emp指针,它已经指向了某个地址,但是我们不知道它的地址
//假设我们只知道pos，也就是emp中list成员的地址，然后我们通过宏来获取结构体也就是emp的地址。
//struct example * emp;
//struct list_head *pos=emp->list;
struct example * entry = list_entry(pos,struct example,list);
//这样就搞定了。
//宏中的三个参数代指的东西也就清楚了。

  我们来分析以下这个宏的原理，((type *)0)->member，将0地址强制转换为 type 结构的指针，然后访问type结构中的member成员。offsetof 取得 list_head 成员相对于结构体的偏移量。然后用当前结构体中 list_head 成员的地址减去偏移量，就得到了结构体地址，再将它转成指向节点结构类型的指针。非常妙啊！

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

  初始化链表，这个就很简单了，因为是双向循环链表，所以第一个链表节点直接next和prev都指向自己就行了。

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

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 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_for_each 宏
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

  遍历链表，这个宏就是一个没加“;”的for循环，其中pos是一个临时指针，类型是struct list_head，这个配合list_entry使用，就达到了遍历链表中结构体并做相应操作的目的了。

五、list_empty
static inline int list_empty(const struct list_head *head)
{
    return head->next == head;
}

  链表判空，只要head->next指向自己, 说明链表中没有其它节点了。
  基本在使用过程中采用这些操作就OK了，在内核中使用链表，借助这些工具函数又方便又好用！