内嵌式双向链表

双向链表是常用的数据结构之一，通常被实现为容器，如C++的STL中的容器模板和glib中的双向链表，实际上，还有另外一种更加巧妙的实现方式，它就是Linux内核所采用的内嵌式的双向链表。

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

可以看到，它并不是一个容器，只是一个包含前向指针和后向指针的结构体。那么如何使用它呢？

首先，让我们来揭露一个C的小戏法：

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

通过宏的名字和参数，发扬望文生义的精神，也许你已经猜了个八九不离十了，不错，它就是用来求TYPE结构体中的MEMBER成员在结构体内的偏移量。其实代码也不难理解，就是把‘0’强制转换成数据结构TYPE的起始地址，那么其成员MEMBER的地址当然就是MEMBER的偏移量了。据说，百度今年也是用它来做笔试题的，是不是有些偏？至少不是中规中矩！

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

上面的宏container_of是通过结构体内的成员的地址求数据结构的地址，这个代码实际上丝毫不比上面的offsetof容易懂，尤其是它还用上了typeof和({ })这两个怪怪。typeof顾名思义就是取结构的类型名。({ })则比较好玩，我们知道C是不支持内联函数的，一般情况下可以用宏来实现内联编译的功能，但是当宏在需要返回值的时候就有些让人不爽了，有人将返回值放在参数列表中模拟C++中的引用参数，有些奇怪：

/* For spinlocks etc */
#define local_irq_save(x) __asm__ __volatile__("pushfl ; popl %0 ; cli":"=g" (x): /* no input */ :"memory")

所以，({ })这个扩展闪亮登场了。它返回程序块中最后一个表达式的值。明白了这两个东东，剩下的部分就由读者自行分析解决了，下面返回正题。

结构体list_head的使用是通过内嵌在其它结构体中来实现链表操作的，换句话说，它将作为需要链表操作的结构体的一个普通成员，当需要得到相应结构体的地址的时候，用container_of宏就可以了。

typedef struct test {
    char value;
    struct list_head list;
} test;
test test_val;

test * tmp;
tmp = container_of(&test_val.list, test, list);

比起glib中的双向链表它少了一个指向容器内部数据的指针，节省了内存空间。这点儿优势比起STL中的list来，并不明显，但是如果一个数据结构有可能属于几个单独的链表，或者是一个链表中的各个元素可能不属于一个数据类型的时候（尽量不要这样做），容器的做法就显得有些捉襟见肘了，而list_head的实现方式，对于前一种情况则只需要增加对应的list_head成员就搞定了，后一种情况的支持可以说是原生的。

Linux内核中list的实现，就像一根线一样贯穿了一个个数据结构，从针孔的位置还能轻易得到原始数据结构的地址，丝毫不影响可用性，这种高超的实现技巧不能不让人叹服。Linux内核中类似的内嵌式数据结构还有hash表和红黑树等，如果有兴趣可结合源码学习。有了它们，你就可以将你的数据结构同时按照几种方式就行组织而丝毫不影响其“美观度”。如果有这样的需求，请毫不犹豫地抛弃容器吧！