C++ 里的 STL 能方便的定义一个 list 类,而 C 语言里,没有对模板的支持,想要写出通用的库,难度显然要大不少。但可以肯定的是,一定有一个 可靠 的解决办法的。

在 Google 上搜索时,找到了一篇文章 玩转C链表。这篇文章写的很好,但我第一眼看的时候,却没找到入手点。琢磨了一个下午,总算有了一点思路。

相比于传统的链表

struct int_node {
        int val;
        struct int_node *next, *prev;
};

Linux Kernel 把两个指针拆了出来。

struct list_head {
    struct list_head *next, *prev;
};
struct int_node {
        int val;
        struct list_head list;
};

这样,对链表的操作,可以只针对于 struct list_head,而有了通用的写法。下一步的问题,就是由 struct list_head 来获得 struct int_node 中存储的数据 val

因为结构体的数据在内存中是连续的,所以,可以用指针的偏移量来存取 val。内核中有这样的代码

/**
 * 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))

传入的三个参数是:指向当前的 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 *)。略有不足的是,内存分配与回收的细节没有被隐藏起来。不过总的来说,通用链表的问题,算是比较优雅的解决了吧。