C语言的通用链表
Zhenbo Li May 06, 2013C++ 里的 STL 能方便的定义一个 list 类，而 C 语言里，没有对模板的支持，想要写出通用的库，难度显然要大不少。但可以肯定的是，一定有一个 可靠 的解决办法的。
在 Google 上搜索时，找到了一篇文章 玩转C链表。这篇文章写的很好，但我第一眼看的时候，却没找到入手点。琢磨了一个下午，总算有了一点思路。
相比于传统的链表
{% highlight c %}
struct int_node {
int val;
struct int_node *next, *prev;
};
{% endhighlight %}
Linux Kernel 把两个指针拆了出来。
{% highlight c %}
struct list_head {
struct list_head *next, *prev;
};
struct int_node {
int val;
struct list_head list;
};
{% endhighlight %}
这样，对链表的操作，可以只针对于 struct list_head，而有了通用的写法。下一步的问题，就是由 struct list_head 来获得 struct int_node 中存储的数据 val。
因为结构体的数据在内存中是连续的，所以，可以用指针的偏移量来存取 val。内核中有这样的代码 {% highlight c %} /**
- 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) (type *)((char *)ptr -offsetof(type,member))
{% endhighlight %}
传入的三个参数是：指向当前的 struct list_head 的指针，整个容器的类型（本例中 struct int_node），和 list_head 的名称（本例中 list）。而这个宏所返回的，就是指向整个容器的指针（本例中 struct int_node *）。
现在，就要求偏移量 offsetof 了。kernel 中的实现很巧妙，但要实现这个功能方法不少（比如 sizeof(struct int_node) - sizeof(struct list_head)）。至于哪种方法更好。。。我觉得这个世界上能写出比 Linux Kernel 质量更好的代码的人为数不多吧。
解决了这些，插入和删除的操作就难度不大了（参数类型都是 struct list_head *）。略有不足的是，内存分配与回收的细节没有被隐藏起来。不过总的来说，通用链表的问题，算是比较优雅的解决了吧。