侵入式链表

普通链表：

就是我们了解的最传统的链表，数据和一个链表指针 next 封装成一个节点，链表指针 next 指向下一个节点的头部。

缺点是数据和链表指针强耦合，整条链上的节点都是一样的类型，换个类型就要重新封装一套节点和方法，泛化能力差。

优点是高效，方便。

struct Node {
    int val;
    Node *next;
};

侵入式链表：

就是链表节点是独立的，包含在数据所在的节点中，链表节点内的的指针 next 指向其它节点中的链表节点。

优点就是只要数据所在的节点中包含链表信息，就都可以被链接到一条链上，链上数据类型无需一致，泛化能力强。

缺点是通过链表节点访问节点元素不够高效。

struct ListObj {
    int next;
};
struct Node {
    int val;
    ListObj list;
};

访问节点元素需要用到两个宏：

• container_of

• offsetof

offsetof

定义在 stddef.h 中，

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

• type 是结构体类型
• member 是结构体成员

这个依赖于编译器，和字节对齐有关系，原理其实就是：

偏移 = 成员地址 - 结构体地址

假定结构体地址为 0，成员地址就等于偏移了。

所以，这里是假定了一个指针，地址是 0，将其转换为指定类型的指针，然后访问它的指定成员，再取这个成员的地址，由于假定的指针是 0，所以成员的地址和 0 的偏移，和它在结构体中的偏移是一样的，将其再转换成 size_t 类型即可。

C++ 不允许给 0 解引用，所以有另一种实现方法，但用法和 C 这个一致。

container_of

定义在 kernal.h 中，

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

• ptr 是结构体成员的地址
• type 是结构体类型
• member 是结构体成员

原理是：

结构体地址 = 成员地址 - 成员偏移

从定义可以看到，成员地址就是通过 offsetof 获取的。

这里，先是随便用一个 0 转换成结构体类型的指针，获取它的成员，使用 typeof 得到成员的类型，加一个 * 成为成员类型的指针，用 ptr 来初始它。（这一步应该是处于安全考虑，类型转换不兼容可能会报警告，如果直接用 ptr 去减偏移，不会有这个警告，可能得到错误的结果。）

然后将它转换成 char * 类型以方便按 1 字节单位做地址偏移，用它减去成员在结构体类型中的偏移，就得到了结构体的地址，转成对应类型指针即可。