Linux内核数据结构之链表
之所以要写本文，主要是当我看到Linux内核中链表的设计，让我叹为观止。Linux实现的方式与众不同，它不是将数据结构塞入链表中，而是将链表节点塞入数据结构中。在Linux源码中，链表在头文件<linux/list.h>中声明。它的节点的原型如下：
struct list_head{ struct list_head *next; struct list_head *prev; };
如果让我使用这个数据结构构造链表，以我对C语言的理解，我会这样构造：
struct alants_list{
struct list_head node; int data1; int data2; };
这样当我得到一个struct list_head *p_list的指针时，要遍历它指向的节点的数据时，可以通过强制类型转换，得到一个struct alants_list *的指针。
((struct alants_list *)(p_list))->data1 = 1; ((struct alants_list *)(p_list))->data2 = 2;
原因是struct list_head node位于struct alants_list最开始的位置，指向struct list_head node的指针，其实也指向struct alants_list的起始位置。这样通过强制类型转换就可以达到目的。
这种方式显然是有前提的，就是struct list_head必须位于需要构造数据结构的开始位置。这显然非常的不方便，也不是很美观。
那内核是怎样实现链表的构造呢？在内核中，可以任意的放置struct list_head的位置，它通过一种特殊的技巧来计算由struct list_head*到struct alants_list*的转换。
在内核中，定义了一个名为container_of()的宏，就是通过它来计算的，该宏定义在<linux/kernel.h>中定义。该定义如下：
#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );})
要想看懂它需要花费一点时间，首先你要知道typeof()，它是一种求变量类型的运算。即：
int a = 1; typeof(a) b = 2;
定义了变量b，b与a的类型一样，都是int类型。
然后要了解另一个宏offsetof(),该宏定义在<linux/stddef.h>中定义。该定义如下：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
先将上述的offsetof()宏拆分开（要注意符号的优先级顺序），首先，令 (TYPE *)0，它将一个空指针转换为TYPE*的类型；然后是((TYPE *)0)->MEMBER,取出结构体中的成员；
然后是&((TYPE *)0)->MEMBER，取出成员MEMBER的地址；接着最后一步(size_t)&((TYPE *)0)->MEMBER，将其转化为size_t类型。这不难理解，当一个结构体的起始位置为0，
则它的成员的地址就是相对于起始位置的偏移量，而offsetof()宏的作用就是，在结构体TYPE中，计算成员MEMBER相对于起始位置的偏移量。
现在可以去理解container_of()宏的意义了，首先是const typeof( ((type *)0)->member ) *__mptr = (ptr)，定义一个指向member的指针__mptr并初始化为ptr，然后计算member相对于起始位置的偏移量，然后__mptr减去该偏移量就得到了指向结构体起始位置的指针，即指向结构体的指针。
而在<linux/list.h>，内核将container_of()宏定义了另一个名字list_entry()。
#define list_entry(ptr, type, member) \ container_of(ptr, type, member)
对于链表的添加，删除，查找，遍历等都是建立在list_entry()宏之上。具体就不多谈了，这些操作都定义在<linux/list.h>头文件中。
通过如此的实现，很方便的实现了泛型编程，对此只能说一句：车轮已造好，请使用。
(注：本文是自己的一些感想，要想理解，需要C语言以及数据结构方面的知识。)
优质内容筛选与推荐>>1、看来真不能直接将.so文件直接添加到Android的JAR包了
2、git submodule
3、SpringMVC 配置过滤器解决中文乱码问题
4、面试总结（YY一面）
5、VS2010测试解读-读懂那些文件们