前言

侵入式链表和之前研究的链表有所不同，以前普通的链表想要获取到节点的数据，只需要拿到指向节点的指针就可以访问结构体内存放的数据，但是侵入式链表不同，指针也是结构体的成员，我们没法通过指针去直接访问节点的数据，因为他存放的地址不是结构体的地址，我找了不少的资料，说什么container_of，说是Linux内核实现的。

container_of

这个玩意网上面的说法其实有一定的误导性，我刚开始看以为是类似windows API提供的函数接口，直接调着用就行了，经过研究，我想多了，他最多只提供了offsetof内存偏移算法，这玩意只是一个宏名，还是自己要定义实现的。。。。

为什么只能是宏

为什么是宏，而不是我定义一个函数调着用。这是因为在c/c++中是不能将类型作为参数的，他是需要传入形参（这个说法好像也不是很标准，大致这么个意思，函数要传入某个类型的变量），而宏替换就可以达到。

实现

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

这一实现是不是很新奇，我很少用宏，也可能是我孤陋寡闻，来一起见识下宏的多行写法。这里的\其实就是上一行没写完，拼接一下，和下面的等价

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

比如说有以下结构体：

struct Student {
    int id;
    char name[32];
    IntrusiveNode by_id;     // 按 id 排序的链表
    IntrusiveNode by_name;   // 按名字排序的链表
};

// 同一个学生可以同时在两个链表里，不冲突！

他的内部包含的节点，我们可以看到在物理内存上，他是在结构体的最后面，我们如果想要通过节点去访问数据，就需要做内存偏移，拿到结构体的地址

64位

struct Student {
    int id;                // 4 字节   [0 ~ 3]
    char name[32];         // 32 字节  [4 ~ 35]
    // ↑ 到 35 号字节结束，36 不是 8 的倍数，所以填充对齐
    // 填充                // 4 字节   [36 ~ 39]  ← 为了对齐补上的
    IntrusiveNode by_id;   // 16 字节  [40 ~ 55]  ← 偏移量 = 40
    IntrusiveNode by_name; // 16 字节  [56 ~ 71]  ← 偏移量 = 56
};

结构体地址 = 节点地址 - 偏移地址

使用方法

Student stu{100, "Tom", {}, {}};

// 拿 by_id 的偏移地址算回去：
IntrusiveNode* p1 = &stu.by_id;     // p1 = 0x...28  (stu + 40)
Student* s1 = container_of(p1, Student, by_id);
// → (Student*)( (char*)p1 - offsetof(Student, by_id) )
// → (Student*)( (char*)p1 - 40 )   // 减 40，回到 stu 首地址

// 拿 by_name 的偏移地址算回去：
IntrusiveNode* p2 = &stu.by_name;   // p2 = 0x...38  (stu + 56)
Student* s2 = container_of(p2, Student, by_name);
// → (Student*)( (char*)p2 - 56 )   // 减 56，回到 stu 首地址

侵入式链表

侵入式链表可以理解为就是一根绳子，结构体就是一个带钩子的衣架，他有一个哨兵节点，不存任何的值，链表初始化的时候自己的next指向自己的prev，自循环

head <───┐
 ↑       │
 └───────┘
prev ←→ next 自环

void InsertBetween(intrusivelist* prev,intrusivelist* next,intrusivelist* newnode){
    newnode->next = next;
    newnode->prev = prev;
    next->prev=prev->next = newnode;
}

通用插入函数

我们的链表设计的每个节点都有两个指针，一个指向前面，一个指向后面，在这里操作和普通链表的差不多，原理就是我们要将节点插入到两个节点之间，要先断开他们彼此指向的指针，然后将新节点和胶水一样将链表链接起来。这个实现在后面的连接环节都会用到。

void InsertBetween(intrusivelist* prev,intrusivelist* next,intrusivelist* newnode){
    newnode->next = next;
    newnode->prev = prev;
    next->prev=prev->next = newnode;
}

头插法

这个我刚开始理解偏了，以为是插入到哨兵节点的前面，实际上正确的理解方式应该是哨兵节点的后面，原来头一个接在哨兵节点的节点的前面。

理解了这个就很好实现了

bool InsertHead(intrusivelist* head,intrusivelist* newnode){
    InsertBetween(head,head->next,newnode);
    return true;
}

尾插法

尾插法同理，找到尾节点，逻辑上是在head的前面，尾节点的后面的位置插入。

bool InsertTail(intrusivelist* head,intrusivelist* newnode){
    InsertBetween(head->prev,head,newnode);
    return true;
}

删除一个节点

到删除的环节了，这个位置需要格外的注意，没有处理好会内存泄漏，在链表上的结构体对象是在堆上创建的，我们删除一个节点的时候不是删除他内部的节点，那么比如结构体有id、姓名之类的参数就直接内存泄漏了，我们在处理好前后节点的指针以后需要通过container_of去偏移找到结构体地址，释放整个结构体，这里是最关键的地方。

这个选择删除节点的依据是学生ID，前面拿到结构体指针后可以访问结构体的ID一项进行比对

bool IntrasiveDeleteOneNode(intrusivelist* node){
    node->prev->next=node->next;
    node->next->prev=node->prev;
    student_node* stu = container_of(node,student_node,student_node);
    delete stu;
    return true;
}

调用者:   [head]  [target]  (用完就扔了)
                                 ↑ 不需要改
函数:    改了前节点和后节点的指针 ✅

删除整个链表

这个删除逻辑哨兵节点必须是最后删除的，有两个临时指针操作，一个负责删除当前指针，一个负责指向下一个指针，因为当前节点释放以后，操作删除的指针会悬空，需要给他重新赋值。还有一个需要注意的是这回删除的传参是二级指针，因为要把哨兵节点也删掉，相当于拆楼了

bool IntrasiveDeleteAll(intrusivelist** head){
    if(!head||!*head){
        printf("传入的头节点不存在\n");
        return false;
    }
    printf("开始删除节点\n");
    intrusivelist* cur =(*head)->next;
    while(cur != *head){
        intrusivelist* next = cur->next;
        student_node* stu = container_of(cur, student_node, student_node);
        delete stu;
        cur = next;
    }
    delete *head;
    *head = nullptr;
    printf("删除完毕\n");
    return true;
}

调用者:   [head]  ← 这个变量必须被置空
              ↑
函数:    必须改到这里
         一级指针改不了 → 必须二级指针

场景	比喻	参数
删单个节点	你从书架上拿一本书扔掉，书架位置不用管	一级指针
删整个链表	你把整个书架拆了，得告诉别人"这里没书架了"	二级指针

剩下的操作基本都是复用上面的逻辑，这里就不过多赘述了，关于之前实现的普通链表以及侵入式链表功能实现我将他们都做好也测试过了，感兴趣的可以自己下载跑着看看，免费开源，但我不保证平台有没有动手脚，注意编码utf-8 with bom，不然会报一些奇怪的错误