嵌入式现代C++教程——侵入式容器设计

你记得普通容器对数据做什么吗？拷贝指针、分配节点、维护额外的内存布局，然后在某个时刻默默地吃掉你的缓存局部性。侵入式容器则更直白：数据对象自己把手伸出来当链表节点——谁要付额外内存和间接访问？不是我。

---

什么是侵入式容器，为什么在嵌入式特别香

侵入式（intrusive）容器的关键点：节点信息（next/prev/…）直接放在用户对象内部，而不是另外分配一个 node 包裹对象指针。优点显而易见：

• 零额外分配 —— 不需要每次 push 都 malloc/new 一个 wrapper（非常重要）。
• 更佳缓存局部性 —— 对象和元信息在一起，遍历更快。
• 更小的内存占用与确定性 —— 对于内存受限或实时系统非常友好。

缺点也很直接：

• 对象被耦合到容器接口（侵入），源码要修改对象结构。
• 一个对象要同时在多个链表中，需要多个"hook"成员或多继承。
• 使用不当会出现悬挂指针/重复插入等问题，需要更谨慎的生命周期管理。

适用场景：任务调度器、空闲块链表、驱动链表、内核/RTOS 数据结构、内存池的 free-list 等。

---

两种常见实现策略

1. 基类 hook（inheritance）：对象继承一个包含 next/prev 的 hook 基类。类型安全，转换容易。
2. 成员 hook（member hook）：对象包含一个 hook 成员（更灵活，可同时有多个 hook 实例），但是需要 container_of 技巧把 hook 指针转换回对象指针。

下面我们先实现一个干净的、可直接使用的"基类 hook"双向链表（适合教程和嵌入式），再说 member-hook 的思路与注意点。

---

代码：简单、类型安全的侵入式双向链表（继承式）

下面的实现目标：小而清晰，C++11 可用，适合嵌入式编译器。

// intrusive_list.h
#pragma once
#include <cassert>
#include <iterator>

// Intrusive list node base — 继承它即可成为链表节点
template<typename T>
struct IntrusiveListNode {
    T* prev = nullptr;
    T* next = nullptr;
};

// Intrusive doubly linked list
template<typename T>
class IntrusiveList {
public:
    IntrusiveList() : head(nullptr), tail(nullptr) {}

    bool empty() const { return head == nullptr; }

    void push_front(T* node) {
        assert(node && node->prev == nullptr && node->next == nullptr && "节点必须处于未链接状态");
        node->next = head;
        if (head) head->prev = node;
        head = node;
        if (!tail) tail = node;
    }

    void push_back(T* node) {
        assert(node && node->prev == nullptr && node->next == nullptr && "节点必须处于未链接状态");
        node->prev = tail;
        if (tail) tail->next = node;
        tail = node;
        if (!head) head = node;
    }

    T* pop_front() {
        if (!head) return nullptr;
        T* n = head;
        head = head->next;
        if (head) head->prev = nullptr;
        else tail = nullptr;
        n->next = n->prev = nullptr;
        return n;
    }

    void erase(T* node) {
        assert(node && "erase null");
        if (node->prev) node->prev->next = node->next;
        else head = node->next;

        if (node->next) node->next->prev = node->prev;
        else tail = node->prev;

        node->prev = node->next = nullptr;
    }

    void clear() {
        T* cur = head;
        while (cur) {
            T* nxt = cur->next;
            cur->prev = cur->next = nullptr;
            cur = nxt;
        }
        head = tail = nullptr;
    }

    // 简单迭代器（只读/可写）
    struct iterator {
        using iterator_category = std::forward_iterator_tag;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        explicit iterator(T* p) : p(p) {}
        reference operator*() const { return *p; }
        pointer operator->() const { return p; }
        iterator& operator++() { p = p->next; return *this; }
        iterator operator++(int) { iterator tmp = *this; ++*this; return tmp; }
        bool operator==(const iterator& o) const { return p == o.p; }
        bool operator!=(const iterator& o) const { return p != o.p; }
    private:
        T* p;
    };

    iterator begin() { return iterator(head); }
    iterator end() { return iterator(nullptr); }

private:
    T* head;
    T* tail;
};

如何使用：

// example.cpp
#include "intrusive_list.h"
#include <iostream>

struct Task : IntrusiveListNode<Task> {
    int id;
    Task(int i): id(i) {}
};

int main() {
    IntrusiveList<Task> runq;
    Task a(1), b(2), c(3);

    runq.push_back(&a);
    runq.push_back(&b);
    runq.push_front(&c); // 链表顺序： c, a, b

    for (auto &t : runq) {
        std::cout << "Task " << t.id << "\n";
    }

    runq.erase(&a);

    if (auto p = runq.pop_front()) {
        std::cout << "pop " << p->id << "\n";
    }
}

这段代码可以直接编译到嵌入式支持的 C++ 编译器（只要支持基础模板与 nullptr）。

---

成员 hook：当对象需要在多个链表中出现时

继承式简单，但如果一个对象需要同时属于多个链表（例如同时在 ready_list 和 wait_list），你需要多个 hook 成员或使用成员 hook 的方式。

成员 hook 的关键是 container_of —— 给定指向 hook 成员的指针，计算回包含它的对象指针（Linux 内核常用宏）。

简单的宏版实现（清晰且常用）：

#include <cstddef> // offsetof
#define CONTAINER_OF(ptr, type, member) \
    ((type*) ( (char*)(ptr) - offsetof(type, member) ))

示例结构：

struct MyObject {
    IntrusiveListNode<MyObject> ready_hook;   // for ready list
    IntrusiveListNode<MyObject> wait_hook;    // for wait list
    int data;
};

// 操作 ready list 时，将传入 &obj->ready_hook，然后用 CONTAINER_OF 转回 MyObject*

成员 hook 比较灵活，但使用时需特别注意：offsetof 要与实际成员名一致；并且强烈要求插入前检查该 hook 是否已经链接（避免重复插入）。

---

设计建议与防坑指南

1. 对象生命周期必须明确：链表中的节点在被销毁前必须先从所有链表中移除。否则会出现野指针，后果通常是难以定位的崩溃。
2. 插入前检查状态：给 hook 加一个 bool linked 字段或断言，防止重复插入。测试代码里多用 assert。
3. 多 hook 需求优先使用成员 hook：若对象在多个容器间切换频繁，成员 hook 更灵活。
4. 并发场景小心内存屏障/原子性：如果要在 ISR 或多核中操作链表，必须采用锁、原子 CAS 或者专门的 lock-free 算法（超出本篇范畴）。
5. 提供 RAII wrapper：考虑提供一个小的 IntrusiveListGuard 或 ScopedUnlink 来保证异常或早返回时对象能安全注销。嵌入式代码也许没有异常，但 RAII 有助于写出更安全的释放代码。
6. 调试信息：在开发阶段，把节点状态打印出来（id/地址/prev/next）能快速定位错误。
7. 不要滥用：侵入式容器并非万能工具。若你不在乎每次分配开销或者对象不可修改（第三方库），就别侵入对象，普通 std::list/vector 更简单、安全、易维护。

---

何时该选择侵入式容器

在嵌入式 / 内核 / 实时系统，资源与延迟是第一要务，侵入式数据结构在这些场景是非常自然的选择。特别适合：

• 要求确定性、避免堆分配的系统（bootloader、RTOS kernel）。
• 需要高性能的 free-list、task queue、timer wheel 等。
• 想要最小内存占用的场景。

如果你做的是普通应用层业务逻辑，或者对象来自第三方库（无法改结构），侵入式方案的维护成本可能高于收益。

---

结语

侵入式容器的思想不复杂：让数据自己负责"站位"。但这要求你对对象的责任更清晰——谁插它、谁删它、什么时候删它。把责任写成代码，再把代码写成规范。对嵌入式系统而言，这是一种非常"实在"的工程哲学：省一分内存，多一分确定性。

查看完整可编译示例

// intrusive_list.h - 简单、类型安全的侵入式双向链表（继承式）
#pragma once
#include <cassert>
#include <iterator>

// Intrusive list node base — 继承它即可成为链表节点
template<typename T>
struct IntrusiveListNode {
    T* prev = nullptr;
    T* next = nullptr;
};

// Intrusive doubly linked list
template<typename T>
class IntrusiveList {
public:
    IntrusiveList() : head(nullptr), tail(nullptr) {}

    bool empty() const { return head == nullptr; }

    void push_front(T* node) {
        assert(node && node->prev == nullptr && node->next == nullptr && "节点必须处于未链接状态");
        node->next = head;
        if (head) head->prev = node;
        head = node;
        if (!tail) tail = node;
    }

    void push_back(T* node) {
        assert(node && node->prev == nullptr && node->next == nullptr && "节点必须处于未链接状态");
        node->prev = tail;
        if (tail) tail->next = node;
        tail = node;
        if (!head) head = node;
    }

    T* pop_front() {
        if (!head) return nullptr;
        T* n = head;
        head = head->next;
        if (head) head->prev = nullptr;
        else tail = nullptr;
        n->next = n->prev = nullptr;
        return n;
    }

    void erase(T* node) {
        assert(node && "erase null");
        if (node->prev) node->prev->next = node->next;
        else head = node->next;

        if (node->next) node->next->prev = node->prev;
        else tail = node->prev;

        node->prev = node->next = nullptr;
    }

    void clear() {
        T* cur = head;
        while (cur) {
            T* nxt = cur->next;
            cur->prev = cur->next = nullptr;
            cur = nxt;
        }
        head = tail = nullptr;
    }

    // 简单迭代器（只读/可写）
    struct iterator {
        using iterator_category = std::forward_iterator_tag;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        explicit iterator(T* p) : p(p) {}
        reference operator*() const { return *p; }
        pointer operator->() const { return p; }
        iterator& operator++() { p = p->next; return *this; }
        iterator operator++(int) { iterator tmp = *this; ++*this; return tmp; }
        bool operator==(const iterator& o) const { return p == o.p; }
        bool operator!=(const iterator& o) const { return p != o.p; }
    private:
        T* p;
    };

    iterator begin() { return iterator(head); }
    iterator end() { return iterator(nullptr); }

private:
    T* head;
    T* tail;
};

// inheritance_example.cpp - 继承式侵入链表示例
#include "intrusive_list.h"
#include <iostream>

struct Task : IntrusiveListNode<Task> {
    int id;
    const char* name;

    Task(int i, const char* n) : id(i), name(n) {}
};

int main() {
    IntrusiveList<Task> runq;

    // 创建任务对象
    Task task1(1, "Task A");
    Task task2(2, "Task B");
    Task task3(3, "Task C");

    std::cout << "=== Pushing tasks to queue ===\n";

    // 添加到队列
    runq.push_back(&task1);
    runq.push_back(&task2);
    runq.push_front(&task3);  // 链表顺序： task3, task1, task2

    std::cout << "\nQueue contents:\n";
    for (auto& t : runq) {
        std::cout << "  Task " << t.id << ": " << t.name << '\n';
    }

    std::cout << "\n=== Removing task1 ===\n";
    runq.erase(&task1);

    std::cout << "Queue contents after erase:\n";
    for (auto& t : runq) {
        std::cout << "  Task " << t.id << ": " << t.name << '\n';
    }

    std::cout << "\n=== Popping from front ===\n";
    while (auto p = runq.pop_front()) {
        std::cout << "  Popped: Task " << p->id << ": " << p->name << '\n';
    }

    std::cout << "\nQueue empty: " << (runq.empty() ? "yes" : "no") << '\n';

    // 演示错误检查（断言会触发）
    std::cout << "\n=== Error handling demo ===\n";
    Task task4(4, "Task D");
    runq.push_back(&task4);

    std::cout << "Attempting to push already-linked node (should assert):\n";
    std::cout << "(Commented out to prevent crash)\n";
    // runq.push_back(&task4);  // 这会触发断言

    return 0;
}

查看更多示例：成员 hook、任务调度器

// member_hook.h - 成员 hook 方式的侵入式链表
#pragma once
#include <cstddef>
#include <cassert>

// container_of 宏 - 给定成员指针，获取包含对象指针
#define CONTAINER_OF(ptr, type, member) \
    reinterpret_cast<type*>(reinterpret_cast<char*>(ptr) - offsetof(type, member))

// 简单的通用链表节点
struct IntrusiveNode {
    IntrusiveNode* prev = nullptr;
    IntrusiveNode* next = nullptr;
};

// 通用侵入式双向链表
class IntrusiveListGeneric {
public:
    IntrusiveListGeneric() : head(nullptr), tail(nullptr) {}

    bool empty() const { return head == nullptr; }

    void push_back(IntrusiveNode* node) {
        assert(node && node->prev == nullptr && node->next == nullptr);
        node->prev = tail;
        if (tail) tail->next = node;
        tail = node;
        if (!head) head = node;
    }

    void push_front(IntrusiveNode* node) {
        assert(node && node->prev == nullptr && node->next == nullptr);
        node->next = head;
        if (head) head->prev = node;
        head = node;
        if (!tail) tail = node;
    }

    void erase(IntrusiveNode* node) {
        if (node->prev) node->prev->next = node->next;
        else head = node->next;

        if (node->next) node->next->prev = node->prev;
        else tail = node->prev;

        node->prev = node->next = nullptr;
    }

    IntrusiveNode* pop_front() {
        if (!head) return nullptr;
        IntrusiveNode* n = head;
        head = head->next;
        if (head) head->prev = nullptr;
        else tail = nullptr;
        n->next = n->prev = nullptr;
        return n;
    }

    IntrusiveNode* front() { return head; }
    const IntrusiveNode* front() const { return head; }

private:
    IntrusiveNode* head;
    IntrusiveNode* tail;
};

// member_hook_example.cpp - 成员 hook 方式示例
#include "member_hook.h"
#include <iostream>

// 可以同时属于多个链表的对象
struct MyObject {
    int id;
    IntrusiveNode ready_hook;   // for ready list
    IntrusiveNode wait_hook;    // for wait list

    MyObject(int i) : id(i) {}
};

int main() {
    IntrusiveListGeneric ready_list;
    IntrusiveListGeneric wait_list;

    // 创建对象
    MyObject obj1(1);
    MyObject obj2(2);
    MyObject obj3(3);

    std::cout << "=== Member Hook Demo ===\n\n";

    // 添加到 ready_list
    ready_list.push_back(&obj1.ready_hook);
    ready_list.push_back(&obj2.ready_hook);

    // 添加到 wait_list
    wait_list.push_back(&obj3.wait_hook);

    std::cout << "Ready list:\n";
    for (IntrusiveNode* node = ready_list.front(); node; node = node->next) {
        MyObject* obj = CONTAINER_OF(node, MyObject, ready_hook);
        std::cout << "  Object " << obj->id << '\n';
    }

    std::cout << "\nWait list:\n";
    for (IntrusiveNode* node = wait_list.front(); node; node = node->next) {
        MyObject* obj = CONTAINER_OF(node, MyObject, wait_hook);
        std::cout << "  Object " << obj->id << '\n';
    }

    // 演示移动：从 wait_list 移到 ready_list
    std::cout << "\n=== Moving obj3 from wait to ready ===\n";
    wait_list.erase(&obj3.wait_hook);
    ready_list.push_back(&obj3.ready_hook);

    std::cout << "Ready list after move:\n";
    for (IntrusiveNode* node = ready_list.front(); node; node = node->next) {
        MyObject* obj = CONTAINER_OF(node, MyObject, ready_hook);
        std::cout << "  Object " << obj->id << '\n';
    }

    std::cout << "\nWait list after move:\n";
    std::cout << "  " << (wait_list.empty() ? "(empty)" : "not empty") << '\n';

    return 0;
}

// task_scheduler_example.cpp - 使用侵入式链表的任务调度器
#include "intrusive_list.h"
#include <iostream>
#include <queue>
#include <vector>

// 任务状态枚举
enum class TaskState {
    Ready,
    Running,
    Waiting,
    Done
};

// 任务类 - 侵入式设计
struct Task : IntrusiveListNode<Task> {
    int id;
    const char* name;
    TaskState state;
    int priority;

    Task(int i, const char* n, int p = 0)
        : id(i), name(n), state(TaskState::Ready), priority(p) {}

    void run() {
        std::cout << "  Running Task " << id << ": " << name << '\n';
        state = TaskState::Running;
        // 模拟任务执行
        state = TaskState::Done;
    }
};

// 任务比较器（用于优先队列）
struct TaskCompare {
    bool operator()(const Task* a, const Task* b) const {
        return a->priority < b->priority;
    }
};

// 简单的任务调度器
class TaskScheduler {
public:
    void add_task(Task* task) {
        ready_list.push_back(task);
    }

    Task* get_next_task() {
        return ready_list.pop_front();
    }

    void run_all() {
        std::cout << "\n=== Running all tasks ===\n";
        while (auto task = get_next_task()) {
            if (task->state == TaskState::Ready) {
                task->run();
            }
        }
    }

    bool empty() const {
        return ready_list.empty();
    }

private:
    IntrusiveList<Task> ready_list;
};

int main() {
    TaskScheduler scheduler;

    std::cout << "=== Intrusive Container Task Scheduler Demo ===\n\n";

    // 创建任务（栈上分配，无堆操作）
    Task task1(1, "Initialize Hardware", 10);
    Task task2(2, "Read Sensors", 5);
    Task task3(3, "Process Data", 8);
    Task task4(4, "Send Report", 3);

    // 添加任务到调度器
    scheduler.add_task(&task1);
    scheduler.add_task(&task2);
    scheduler.add_task(&task3);
    scheduler.add_task(&task4);

    std::cout << "Tasks added to scheduler (no memory allocation!)\n";
    std::cout << "Scheduler empty: " << (scheduler.empty() ? "yes" : "no") << '\n';

    // 运行所有任务
    scheduler.run_all();

    std::cout << "\nScheduler empty: " << (scheduler.empty() ? "yes" : "no") << '\n';

    std::cout << "\n=== Benefits demonstrated ===\n";
    std::cout << "- No heap allocation for task nodes\n";
    std::cout << "- Tasks can be on stack or in static memory\n";
    std::cout << "- Zero overhead abstraction\n";
    std::cout << "- Deterministic memory usage\n";

    return 0;
}