关于内核中使用到的数据结构这一系列会有五篇文章，

分别介绍

   链表

   队列

   哈希

   映射

   红黑树

一、首先介绍内核中链表

        内核中定义的链表是双向链表，在上篇文章--libevent源代码分析--queue.h中关于TAILQ_QUEUE的理解中介绍了FreeBSD中如何定义链表队列，和linux内核中的定义还是有区别的，但同样经典。

        内核中关于链表定义的代码位于： include/linux/list.h。list.h文件中对每个函数都有注释，这里就不详细说了。其实刚开始只要先了解一个常用的链表操作（追加，删除，遍历）的实现方法，其他方法基本都是基于这些常用操作的。

       介绍内核中链表的定义之前，回想数据结构中定义链表的方式，两者是有区别的。

一般的双向链表一般是如下的结构，

• 有个单独的头结点(head)
• 每个节点(node)除了包含必要的数据之外，还有2个指针(pre,next)
• pre指针指向前一个节点(node)，next指针指向后一个节点(node)
• 头结点(head)的pre指针指向链表的最后一个节点
• 最后一个节点的next指针指向头结点(head)

（感谢原作者）

传统的链表有个最大的缺点就是不好共通化，因为每个node中的data1，data2等等都是不确定的(无论是个数还是类型)。

linux中的链表巧妙的解决了这个问题，linux的链表不是将用户数据保存在链表节点中，而是将链表节点保存在用户数据中。

linux的链表节点只有2个指针(pre和next)，这样的话，链表的节点将独立于用户数据之外，便于实现链表的共同操作。

如下图所示：

这个图画的非常的标准，好好揣摩。

在include/linxu/list.h中的定义也是非常简单：

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

在使用的时候，自己定义结构体，但是结构体中除了用户的数据就是这个结构体。这样便可构造自己定义的双向链表。

在了解了基本内容看具体实现，只知道数据成员list的地址，怎样去访问自身以及其他成员呢？

linux链表中的最大问题是怎样通过链表的节点来取得用户数据？

和传统的链表不同，linux的链表节点(node)中没有包含用户的用户data1，data2等。

下面进入正题：

在include/linux/list.h头文件中可以看到这段代码！

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

其中container_of这个宏在/include/linux/kernel.h的头文件中。

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

//这里面的type一般是个结构体，也就是包含用户数据和链表节点的结构体。

//ptr是指向type中链表节点的指针

//member则是type中定义链表节点是用的名字

关于这个宏解释有几点需要解释，

1、typeof(type)，这是一个宏，这个宏返回一个type的类型，例如：int a; typeof(a) b;等价于int b;

2、offsetof(type,member)宏  它定义在include/linx/stddef.h中，如下：
#define offsetof(TYPE, MEMBER)  ((size_t) &((TYPE *)0)->MEMBER)
这个宏返回member在type类型中的偏移量，type是一个结构，例如：
typeof(list_head,next);返回0，也就是返回相对于结构起始地址的偏移量。可能会有疑问为何将0强制转化为某一个类型的指针，然后这个指针指向这个类型中的某一个成员，指针所指成员的地址就是这个成员在这个类型中的偏移量。

       这种情况一般都使用在获取结构体中某一成员的偏移。因为首地址是从0开始，那么结构成员的地址从数值上看就是他的偏移量。可能还不怎么明白，那么指针是什么，是一个地址，指针的内容是某个变量的首地址，将0强转为指针类型，也就是说指针值为零，而这个值就是所指对象的首地址。（偏移量+首地址=成员地址，这里只不过将首地址变为0，那么成员地址就是偏移量。）

可以用一个简单的例子说明：

struct student
{
    int id;
    char* name;
    struct list_head list;
};
<ul><li>type是struct student</li><li>ptr是指向stuct list的指针，也就是指向member类型的指针</li><li>member就是 list
</li></ul>

下面的图以sturct student为例进行说明这个宏：

首先需要知道 ((TYPE *)0) 表示将地址0转换为 TYPE 类型的地址

由于TYPE的地址是0，所以((TYPE *)0)->MEMBER 也就是 MEMBER的地址和TYPE地址的差，如下图所示：

3、使用typeof(((type *)0)->member)来定义指针 __ptr，而不是这样：const typeof(member) *__ptr=ptr;？
    其实，这个很简单，因为member是结构的成员，只能通过结构来访问！

4、在这句话中(type *)( (char *)__mptr - offsetof(type,member) ); 减号前就是成员的地址，减号后是这个成员在结构中的偏移量，两者相减便是这个结构的首地址。

链表中数据的访问：

在文件include/linux/list.h中，有访问链表数据的代码

#define list_for_each_entry(pos, head, member)
    for(pos=list_entry((head)->next,typeof(*pos),member);...)

#define list_for_each_entry(pos, head, member)
    for(pos=list_entry((head)->next,typeof(*pos),member);...)
从上面的使用来看，替换list_entry宏以及container_of宏后，变成如下：
    pos=({const typeof(((typeof(*pos) *)0)->member) *__ptr=(head)->next;

pos=({const typeof(((typeof(*pos) *)0)->member) *__ptr=(head)->next;
            (typeof(*pos) *)((char *)__ptr - offsetof(typeof(typeof(*pos)),member));});

二、还有一种链表，作为双向链表使用

struct hlist_head{
    struct hlist_node *first;
};
struct hlist_node{
    struct hlist_node *next, **pprev;
};

这个双向链表不是真正的双向链表，因为表头只有一个first域，为什么这样设计？代码中的注释解释：为了节约内存，特别适合作为Hash表的冲突链，但Hash表很大时，那么表头节约下来的内存就相当客观了，虽然每个表头只节约一个指针。
    同时，表头的不一致性也会带来链表操作上的困难，显然就是在表头和首数据节点之间插入节点时需要特别处理，这也就是为什么会设计二级指针pprev的原因。看看代码

static inline void hlist_add_before(struct hlist_node *n,struct hlist_node *next)
{
    n->pprev=next->pprev;
    n->next=next;
    next->pprev=&n->next;
    *(n->pprev)=n;
}

解释：指针n指向新节点，指针next指向将要在它之前插入新节点的那个节点。
看上面的代码，就可以看到二级指针pprev的威力了！有没有看到，当next就是第一个数据节点时，这里的插入也就是在表头和首数据节点之间插入一个节点，但是并不需要特别处理！而是统一使用*(n->pprev)来访问前驱的指针域（在普通节点中是next，而在表头中是first）。看到这个和上篇文章中讲解的TAILQ_QUEUE是不是很相似！其实在FreeBSD中也讲解了这种数据结构！

精益求精的Linux链表设计者（因为list.h没有署名，所以很可能就是Linus Torvalds）认为双头（next、prev）的双链表对于HASH表来说"过于浪费"，因而另行设计了一套用于HASH表应用的hlist数据结构--单指针表头双循环链表，从上图可以看出，hlist的表头仅有一个指向首节点的指针，而没有指向尾节点的指针，这样在可能是海量的HASH表中存储的表头就能减少一半的空间消耗。

因为表头和节点的数据结构不同，插入操作如果发生在表头和首节点之间，以往的方法就行不通了：表头的first指针必须修改指向新插入的节点，却不能使用类似list_add()这样统一的描述。为此，hlist节点的prev不再是指向前一个节点的指针，而是指向前一个节点（可能是表头）中的next（对于表头则是first）指针（struct list_head **pprev），从而在表头插入的操作可以通过一致的"*(node->pprev)"访问和修改前驱节点的next（或first）指针。