朝花夕拾-链表（一）

"Writing in C or C++ is like running a chain saw with all the safety guards removed. " - Bob Gray

“用C或C++写代码就像是在挥舞一把卸掉所有安全防护装置的链锯。” —— 鲍勃·格雷

0x00 大纲

0x01 前言

学生管理系统、学生成绩管理系统、教师管理系统、图书管理系统、通讯录管理系统、进销存管理系统……这一个个耳熟能详的名字，正是无数C语言练习生除了唱、跳、RAP和篮球之外，必须迈过去的一道坎，无论是作为课程设计，还是期末作业，都坑倒了一大批新手。照着书上的例程修修改改就是跑不通，网上查到的代码比自己写的还不靠谱……毕竟老夫也是渡过此劫的魔鬼。

其中很大一部分原因就是因为XXX管理系统的核心数据结构——链表，没有int、long和char这些基础数据类型长得那么可爱单纯，让人学起来一脸辛酸。

简单的链表大家都会，这边文章要讲的其实是Linux的内核链表，拿个旧瓶装点新酒。

0x02 链表

定义

链表是线性表的一种。它通过指针将一系列数据节点连接成一条数据链，相对于静态数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中插入数据。

链表的分类

单链表

单链表是最简单的一类链表，它的特点是仅有一个指针域指向后继节点，因此，对单链表的遍历只能从头至尾顺序进行。尾节点指针域通常指向NULL空指针。

双链表

双链表在单链表的基础上增加了一个指向前驱节点的指针域，可以实现双向遍历。

循环链表

循环链表的尾节点指针域指向首节点。它的特点是从任意节点出发，都可以访问到整个链表。如果在双链表的基础上实现循环链表，则可以实现从任意节点双向访问整个链表。

普通链表的局限

链表的节点通常由数据域和指针域构成，以喜闻乐见的学生管理系统为例：

struct student
{
    char id[48];
    char name[64];
    char clazz[24];
}
struct list_node
{
    struct student data;   // 数据域
    struct list_node *next;// 指针域
}
void list_init(struct list_node *list);
void list_add(struct list_node *list, struct student *stu);
void list_del(struct list_node *list, struct student *stu);
......

可以看到，这样的链表对于维护单一数据来说，比如上面的struct student，没有任何问题，但如果在另一个程序上下文中，我们的数据域不是struct student，而是struct teacher或者struct any_thing，显然，我们必须为这些不同的数据类型重新定义一套链表的操作接口，我们的代码没办法完全复用（Ctrl+C，Ctrl+V）。简而言之，我们需要一个通用的链表。

0x03 通用链表

结构与数据解耦

要实现一个通用的链表，我们首先要将数据和结构解耦，这也是实现任意一种抽象数据类型的基础。很遗憾，C语言既没有C++的模板，也没有C#和Java的泛型。但是我们可以考虑这样的结构：

struct list_node
{
    void *data;            // 数据域
    struct list_node *next;// 指针域
}
void list_init(struct list_node *list);
void list_add(struct list_node *list, void *data);
void list_del(struct list_node *list, void *data);
......

无类型的指针，可以实现某种程度上的抽象数据类型，但是这意味着我们代码会到处充斥强制转换和回调函数，必须时刻注意自行检查数据类型，一个不小心就会发生内存错误。

显然，这不是我们想要的。我们向Linux内核的链表实现取下经，既然是一个与数据解耦的链表，那这个链表的节点不应该包含数据域本身，像这样：

struct list_node
{
    struct list_node *next, *prev;// 仅有指针域
}

节点里面仅包含了指向前驱节点和后继节点的指针，那么我们的数据存放在哪里呢？

还是以学生管理系统为例，我们把代码调整一下，将链表的节点放在数据结构体内，这样，抽象（链表结构）不再依赖于细节（数据类型），细节（数据类型）依赖于抽象（链表结构），利用依赖倒置的思想，完成了数据与结构的解耦。如下：

struct list_node
{
    struct list_node *next, *prev;
}
struct student {
    char id[48];
    char name[64];
    char clazz[24];
    struct list_node list;// 链表节点反置于数据结构体内
}
void list_init(struct list_node *list);
void list_add(struct list_node *new_node, struct list_node *head);
void list_del(struct list_node *node);
......

可以发现，对比之前的代码，进行调整之后，我们的链表操作函数中不再关心数据结构体struct student的具体细节，所有的操作都基于struct list_node链表节点，也就是说，我们可以轻松的将struct student替换成struct teacher，而不用修改链表操作的任何代码。

更直观的对比

用一张普通链表和通用链表的节点对比图可以更直观的看出两者在结构上的差异，对于普通链表来说，节点本身包含了数据，对节点的操作是对数据域和指针域整体的操作；对于通用链表来说，则是数据本身包含了节点，对节点的操作只与局部的指针域有关，与数据域无关。

内存地址偏移

经过上面的调整，我们确立了通用链表的实现方向，但是随之而来的是新的问题：如何通过链表节点list_node取得对应的数据成员struct student？我们的标题提出了解决方法，答案就是利用地址偏移。

如图，我们知道结构体的指针指向的是该结构体在内存中的起始地址，不妨假设结构体类型（type）为struct student的数据存储在内存的 0x00000000 到 0x00000090 单元， 0x00000088 到 0x00000090 单元存储的是类型为struct list_node的结构体成员（member）list，注意编址从下往上逐渐增大，如果已知成员的起始地址，那么该成员相对于结构体的偏移量（offset）为 0x00000088 - 0x00000000 = 136。显然，我们可以得出以下公式：

结构体起始地址 = 成员起始地址 - 成员在结构体的偏移量

offsetof

有了上面的公式，还需要知道如何获取成员在结构体的偏移量。offsetof 是定义在C标准库头文件<stddef.h>中的一个宏，它会生成一个类型为size_t的无符号整型，代表一个结构成员相对于结构体起始的字节偏移量（offset）。一种可能的写法为：

#define offsetof(type, member) ((size_t) &((type *)0)->member)

其中member表示的是结构体成员的名称，type表示的是结构体的类型，这里我们以struct student为例，如果要得到成员list相对于结构体struct student的偏移量：

// 注意list必须与在结构体中定义的变量名称一致
int offset = offsetof(struct student, list);
// 将宏展开得到
int offset = ((size_t) &((struct student *)0)->list);

把表达式分解一下，可以得到：

（1）(struct student *)0，将0强制转换为struct student结构体指针类型，可以理解为将该结构体指针偏移到0地址

（2）((struct student *)0)->list)，通过指针访问结构体成员list

（3）&((struct student *)0)->list)，对结构体成员member进行取地址运算，获得结构体成员的地址

（4）(size_t) &((struct student *)0)->list，将结构体地址强制转换为无符号整型表示的数值

由于我们将结构体起始地址偏移到了0地址，所以成员list的地址数值上就等于list相对于结构体起始地址的偏移量，这是一个常量，它在编译期间就可以被替换为具体的数值，而不用在运行时动态计算，因此，在某些编译器中，它会被定义为编译器内建实现，比如GCC编译器<stddef.h>中offsetof宏的定义如下：

#define offsetof(TYPE, MEMBER) __builtin_offsetof (TYPE, MEMBER)

它们得到的结果是一致的，这不会影响我们对原理的理解。

container_of

我们将求取成员偏移量的offsetof宏代入上面的公式，得到另一个宏cotainer_of：

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type,member)))

cotainer_of返回的是结构体成员所在结构体的起始地址（指针），其中ptr为指向结构体成员的指针（相当于成员的起始地址），type表示的是结构体的类型，member表示的是结构体成员的名称。老规矩，继续以struct student为例，便于理解：

......
struct student *ptr_of_stu;
// 通过成员list的指针ptr_of_list_node获取结构体指针ptr_of_stu
ptr_of_stu = container_of(ptr_of_list_node, struct student, list);
// 将宏展开后得到（offsetof前面已经分析过，这里就不赘述了）
ptr_of_stu = ((struct student *)((char *)(ptr_of_list_node) - offsetof(struct student,list)));
......
ptr_of_stu->id = "996";
......

把表达式分解一下，可以得到：

（1）offsetof(struct student,list)，获得成员list在结构体struct student中的偏移量

（2）(char *)(ptr_of_list_node)，将节点指针强制转换为字符型指针，保证计算结果正确，当指针变量进行运算时，会前进或后移相应类型数据的宽度，之所以进行转换是要确保我们的偏移量都是按字节计算的偏移量

（3）(char *)(ptr_of_list_node) - offsetof(struct student,list))，用成员变量指针（起始地址）减去成员的结构体偏移量，得到结构体的指针（起始地址），也即是公式的体现

（4）(struct student *)((char *)(ptr_of_list_node) - offsetof(struct student,list))，将计算得到的指针强制转换为struct student类型指针

到这里，我们就解决了如何通过链表节点list_node取得对应的数据成员struct student的问题。接下来只需要将链表的常用操作封装起来，就能够得到一个与具体数据类型无关的通用链表。

小结

我们似乎花了很大的功夫去调整链表的节点，不禁要问，why? 像教科书例程一样简单粗暴地定义结构体类型和指针不好吗？好，但是也不好。好的地方是，代码直观，容易理解和操作。不好的地方呢？假设我们要写一个“教务管理系统”，它需要同时维护两种信息：学生信息和教师信息。我们用链表存储他们的所有数据，那么以插入数据为例：

struct student
{
    char id[48];
}
struct teacher
{
    char id[48];
}
struct student_node
{
    struct student *data;// 普通链表，数据放在节点内
    struct student_node *prev;
    struct student_node *next;
}
struct teacher_node
{
    struct teacher *data;// 普通链表，数据放在节点内
    struct teacher_node *prev;
    struct teacher_node *next;
}
// 普通链表插入一个节点
void list_add_student(struct student_node *head, struct student *data)
{
    struct student_node *entry = (struct student_node *)malloc(sizeof(struct student_node));
    entry->data = data;
    head->next->prev = entry;
    entry->next = head->next;
    entry->prev = head;
    head->next = entry;
}
// 普通链表插入一个节点
void list_add_teacher(struct teacher_node *head, struct teacher *data)
{
    // 为节点申请内存
    struct teacher_node *entry = (struct teacher_node *)malloc(sizeof(struct teacher_node));
    entry->data = data;
    head->next->prev = entry;
    entry->next = head->next;
    entry->prev = head;
    head->next = entry;
}
// 插入操作
struct student_node *student_head; // 假设链表已经初始化
struct teacher_node *teacher_head; // 假设链表已经初始化
struct student new_student; // 省略结构体成员赋值
struct teacher new_teacher; // 省略结构体成员赋值
list_add_student(student_head, &new_student);
list_add_teacher(teacher_head, &new_teacher);

看到了吗，每增加一种数据类型，就必须多定义一套操作函数，代码成倍增加不说，还必须注意类型不能混用，否则分分钟一个大大的内存错误扔给你。我们看看通用链表可以怎么做：

struct list_node
{
    struct list_node *next, *prev;
}
struct student
{
    char id[48];
    struct list_node; // 通用链表，节点放置在数据结构体内
}
struct teacher
{
    char id[48];
    struct list_node; // 通用链表，节点放置在数据结构体内
}
// 通用链表插入一个节点
void list_add(struct list_node *new_node, struct list_node *head)
{
    // 由于节点随着数据结构体一起被分配，这里不需要再动态申请内存
    head->next->prev = entry;
    entry->next = head->next;
    entry->prev = head;
    head->next = entry;
}
// 插入操作
struct list_node *student_head; // 假设链表已经初始化
struct list_node *teacher_head; // 假设链表已经初始化
struct student new_student; // 省略结构体成员赋值
struct student new_teacher; // 省略结构体成员赋值
list_add(student_head, &new_student.list_node);
list_add(teacher_head, &new_teacher.list_node);

注意，上述的代码只是为了对比和说明普通链表与通用链表的泛用性，省略了很多初始化和检查代码，不能直接使用。从代码可以知道，通用链表的list_add函数只需要被定义一次，就可以被用于任意数据类型，只需要在数据结构体内包含list_node结构体，该结构体类型便可以作为链表节点进行管理。

对于通用链表的各种基本操作和代码示例，将在下一篇文章中进行展开和说明。期待与你下次再见。