purecpp - a cool open source modern c++ community

统一的侵入式链表

编辑时间：2024-10-20 13:38:21 作者：TypeCombinator 3条评论

出自：purecpp.cn

转载请注明出处！

# 统一的侵入式链表
## 前言

几年前我实现了一个侵入式链表库，是用C写的，它一直躺在我的私人仓库里，这个库与众不同之处在于将4种不同的链表实现统一了起来，最近尝试了用C++改写，并开放出来（仓库是[uit](https://github.com/TypeCombinator/uit)），里面用到的一种核心的技巧我称之为**mock_head**。

为简单说明这一技巧，我用最简单的C的单链表作为示例。首先定义一个单链表节点类型`struct node`，并实现`push_front`，代码如下：

```c
#include <stddef.h>

struct node {
    int sn;
    struct node *next;
};

static struct node *head = NULL;

void push_front(struct node *n) {
    n->next = head;
    head = n;
}
```

传统实现中，如果我们想从链表中删除一个节点，我们需要借助二级指针，这样可以少一些判断，代码如下：

```c
struct node *remove_with_secondary_pointer(struct node *n) {
    struct node **prev = &head;
    for (struct node *cur = *prev; cur != NULL;) {
        if (cur == n) {
            *prev = cur->next;
            return cur;
        }
        prev = &cur->next;
        cur = *prev;
    }
    return NULL;
}
```

为什么需要二级指针呢？是因为头节点和数据节点的类型不一样，二级指针将二者统一了起来。如果我们将头节点定义为`static struct node head = {0, NULL};`，二级指针也不再需要，但这样会存在空间浪费，示例中的成员`int sn;`是多余的，因为头节点只需要用到`struct node next;`成员。由此可见只要我们能通过统一的方式访问头节点和数据节点，那么代码就可以简化。

那么能否不用二级指针也没有空间浪费呢，这就是本文要介绍的**mock_head**，通过`container_of`将头节点模拟成数据节点，这样也能实现访问上的统一，代码如下：

```c
#define container_of(_field_, _type_, _member_)                                                    \
    ((_type_ *) ((size_t) (_field_) -offsetof(_type_, _member_)))

#define MOCK_HEAD(_field_, _type_, _member_) container_of(_field_, _type_, _member_)

struct node *remove_with_mock_head(struct node *n) {
    struct node *prev = MOCK_HEAD(&head, struct node, next);
    for (struct node *cur = prev->next; cur != NULL;) {
        if (cur == n) {
            prev->next = cur->next;
            return cur;
        }
        prev = cur;
        cur = prev->next;
    }
    return NULL;
}
```

如你所见，**mock_head**仅仅是`container_of`的别名，他统一了头节点和数据节点，正如二级指针一样。一旦明白了这一点，你就会发现二级指针不再被需要。linux中的hlist数据节点的前驱需要使用二级指针，借助这一技巧也可以消除。

## 实现

链表的头节点和数据节点可以是双指针或单指针，做个排列组合即`2*2=4`种链表实现，这4种实现分别都有各种的适用场景。

| 类型           | 头节点指针个数 | 数据节点指针个数 | 数据         | 说明                                                 |
| -------------- | -------------- | ---------------- | ------------ | ---------------------------------------------------- |
| `uit::islist`  | single         | single           | LIFO         | 单链表                                               |
| `uit::isdlist` | single         | double           | LIFO         | 等价于linux中的hlist，用于实现hash表                 |
| `uit::idslist` | double         | single           | LIFO or FIFO | 主要用于实现队列，相比双链表，数据节点空间利用率更高 |
| `uit::idlist`  | double         | double           | LIFO or FIFO | 双链表                                               |

不管是头节点还是数据节点，只有2种节点类型，即single和double，定义如下：

```c++
template <typename T>
struct isnode {
    T *right;
};

template <typename T>
struct idnode : public isnode<T> {
    T *left;
};
```

可以看到`idnode`继承了`isnode`，这是为了二者能够做类型转换。前文提到，**mock_head**仅仅是`container_of`的别名，`container_of`实现如下：

```c++
template <typename M, typename T>
constexpr size_t offset_of(M T::*field) noexcept {
    return reinterpret_cast<size_t>(&(static_cast<T *>(nullptr)->*field));
}

template <typename M, typename T>
T *container_of(M T::*field, M *m) noexcept {
    return reinterpret_cast<T *>(reinterpret_cast<unsigned char *>(m) - offset_of(field));
}
```

与C语言实现的原理相同，通过成员指针算偏移得到”container“，因为有4个链表实现，我只抽取一个典型来讲解，其他原理是相通的，以`idlist`为例，定义如下：

```c++
template <auto M>
class idlist;

template <typename T, idnode<T>(T::*M)>
class idlist<M> {
   public:
    idlist() noexcept {
        head.left = head.right = mock_head();
    }
   private:
    [[nodiscard]]
    inline T *mock_head() noexcept {
        return container_of(M, &head);
    }
    idnode<T> head;
};
```

以上代码中头节点的前驱和后继并没有赋值为`nullptr`，而是赋值为**mock_head**，这样头节点在维护链接关系时和数据节点是一致的，代码会得到极大简化，不用在头尾边界情形去做空指针的判断，这消除了分支，代码如下：

```c++
static void insert(T *node, T *left, T *right) noexcept {
    (node->*M).right = right;
    (node->*M).left = left;

(left->*M).right = node;
    (right->*M).left = node;
}

static void remove(T *left, T *right) noexcept {
    (left->*M).right = right;
    (right->*M).left = left;
}

static void remove(T *node) noexcept {
    remove((node->*M).left, (node->*M).right);
}

void push_front(T *node) noexcept {
    T *mhead = mock_head();
    insert(node, mhead, (mhead->*M).right);
}

void push_back(T *node) noexcept {
    T *mhead = mock_head();
    insert(node, (mhead->*M).left, mhead);
}
```

可以看到代码形式上和linux的侵入式链表是完全一致的，而且还有一个优点是，我们不再需要像linux那样，每次在访问数据节点时还要做一次`container_of`，示例如下：

```c++
#include <uit/idlist.hpp>

struct apple {
    apple(uint64_t weight, int sn)
        : weight(weight)
        , sn(sn) {
    }

uint64_t weight;
    uit::idnode<apple> node;
    int sn;
};

int main(int argc, char *argv[]) {
    uit::idlist<&apple::node> list{};

apple a0{500, 0};
    apple a1{501, 1};
    apple a2{502, 2};
    apple a3{503, 3};

list.push_front(&a3);
    list.push_front(&a2);
    list.push_front(&a1);
    list.push_front(&a0);

for (const auto &i: list) {
        std::cout << "sn: " << i.sn << ", weight: " << i.weight << std::endl;
    }
    return 0;
}
```

另外的3种链表也借助**mock_head**简化了代码实现，特别是`idslist`的`push_back`实现，没有任何条件分支，代码如下：

```c++
template <auto M>
class idslist;

template <typename T, isnode<T>(T::*M)>
class idslist<M> {
   public:
    idslist() noexcept {
        head.right = nullptr;
        head.left = mock_head();
    }
    void push_back(T *node) noexcept {
        (node->*M).right = nullptr;
        (head.left->*M).right = node;
        head.left = node;
    }
   private:
    [[nodiscard]]
    T *mock_head() noexcept {
        return container_of(M, static_cast<isnode<T> *>(&head));
    }
    idnode<T> head;
};
```

`idslist`实现的关键在于`head.left = mock_head();`这行代码，即将前驱指向了**mock_head**，这样头节点和尾部节点的后继访问被统一了，也就消除了分支。

## 问题

`container_of`是UB，即便如此，我还是将代码继续写了下去，是因为我看到了形式上的统一，代码的简化，当然结果也符合预期，高优化等级下，有**部分测试不能通过**。

## 后记

我想了如下几种解决办法：

- 组合和继承在某些地方是相通的，一旦我们需要用`container_of`实现的代码也可以用继承的方式去实现，但是，毫无疑问，代码会变得复杂许多，也违背了这个库的设计初衷.
- 不使用**mock_head**，这需要增加许多空指针的判断，代码变得复杂，性能也有损失
- 借助编译屏障和邪恶的`volatile`阻止一些别名分析的优化

最后，还是希望能有标准定义吧！本文出现的代码详见仓库[uit](https://github.com/TypeCombinator/uit)，当前这个项目仅用于实验探索，无法用于实际项目。

**补个尾巴(2024年10月15日)**：文章写完了又尝试了下，之前想复杂了，用继承去实现也不麻烦，继承方式的实现后续将放在分支里进行，另外仓库里更新了帮助理解的[图片](https://github.com/TypeCombinator/uit)。

## 总结(2024年10月18日)
还是放在文章里吧，评论可能会不被注意，经过知乎提问，得到了ykiko的指正（非常感谢），继承和static_cast的方案还是存在UB，因为idslist的mock_head是这样来的：idnode--->isnode--->T，最初的类型idnode和最终类型T无关，违反严格别名，详情见[知乎](https://www.zhihu.com/question/1247137402/answer/8504919161)，实验探索到此结束，谢谢大家！

来说两句吧