linux内核链表结构

    最近在看一些内核方面的书籍，之前也有看过，但是由于功力尚浅所以没能看的太明白。今天看到内核的链表结构，觉得理解了其中的要点，故而卖弄一下，见笑了，:)
    内核中很多地方都使用到了链表，所以作为实现必定是一个通用的，而内核是用c实现的，没有c 的模板辅助，这样的通用性就实现起来有些难度。但是linux采用了比较有技巧的方式，即容器的概念。

// 首先是链表中的节点结构，注意是双向链表

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

// 其次是链表要连接的真正对象

struct Object
{
    datatype data_1;
    ...
    list_head member;
    ...
    datatype data_n;
};

    注意到，list_head的对象被嵌入到了object中。结构如下图所示：
-----------------                  -----------------
|  data_1     |                  |   data_1   |
-----------------                  |----------------
|  member  | <--------> | member  |
-----------------                  -----------------
|  data_n     |                  |  data_n    |
-----------------                  -----------------
对链表来说就是遍历的问题了，而遍历的过程就是顺着 member 走。
最主要的问题就是如何从一个 Obejetc实例中解析出 member(即list_head实例)，内核提供了一些宏，其中最主要的几个如下：
// kernel.h

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

对上面两个宏作一点解释：
1. 第一个宏返回TYPE类型中 MEMBER成员的位置偏移量，这个量是更具编译和cpu定的。
2. 第二个宏的作用是返回type实例中的member实例，其中参数memner是list_head的变量名。
3. 第二个宏的第一句，看似多余，实则有用。由于这是一个宏，所以在展开后ptr是一个表达式，有可能会和自己的表达式混淆，所以定义自己的变量__mptr接受这个表达式的值。其中typeof关键字是GNU C的扩展。
4. 第二个宏的第二句，计算出member的位置，并转型成为 type 类型返回，这也就说明了，其实member的prev和next指针所指的就是object对象。

实际的例子解释上面宏的展开：

struct test
{
    int a;
    struct list_head member;
    int b;
};

// 解析后
const typeof(((struct test*)0)->member) __mptr = (ptr);
(struct test*) ((char*)__mptr - offset); // 注，offsetof的具体计算省略

有了这个模型和提取list_head的宏，其余的链表操作就迎刃而解，当然其实现也有很多的精妙之处，有待好好的品味。