前言

昨天我们实现了一个不安全但是还行的单向队列，今天我们来挑战最终boss：实现一个面向生产环境的双链队列！

一个可用于生产环境的unsafe 双链队列（A Production-Quality Unsafe Doubly-Linked Deque）

该来的还是得来，这一步我们还是要跨！

我们的目标是： std::collections::LinkedList，（张emo：是不是很大胆.jpg）

下面有一大段作者的《左右互搏》，感兴趣的可自行查看：A Production Unsafe Deque - Learning Rust With Entirely Too Many Linked Lists (rust-unofficial.github.io)

结构

双向意味着双倍的痛苦！

要实现双向链表，我们还是需要两个指针。

这里有两种方案到达我们的要求：

• 犹典中典之《自古以来便是我们的领土》：传统保存双指针，很好的传统，使我的链表旋转。不过这个方案有双倍的边缘场景需要处理。
• 《我们意念合一》：使用一假节点拼接头尾，好处是不需要处理边缘场景，不用担心尾节点往上找不到或者头节点往下找不到的问题。

这么一看自然是选择假节点的方案了。

然而，这个方案实践起来有一些问题：

1. 额外的内存占用（allocation）和委婉（indirection，就是变得复杂了些），尤其是对于空链表来说，居然还带有节点（dummy），在这自我矛盾，对于这一点，有以下三个解决方案：
   • 先不分配内存直到有东西插入♂，简单且高效，但是把我们前面试图解决的边缘问题又带了回来（需要判断是否是空的问题）
   • 谁说我们非得一开始就搞一个空节点在里面的，我们可以想一个法子在需要的时候再插入一静态单例（singletom）空节点嘛（copy-on-write），但是我们目前做不到，有需要可见：ThinVec's sourcecode
   • 把空姐点放到栈上存储，能做到，但是危险，暂时不考虑
2. 要放什么值到空节点里面？我们这里可不是Copy类型，而是泛型，所以我们的数据得包裹在Box里，那咋整？针对这点，我们也有解决思路：
   • 自然是Option<T>，空节点直接None完事。简单高效，但是比较臃肿（bloated）
   • 是时候展示好康的东西了： MaybeUninit，可以用来表示为初始化，但是有些畸形。。
   • 找不到解决方案我们就堵死源头，找个法子把这个字段去掉不就完事了？（js:我都不敢这么big胆）。太大胆了，先不考虑，如果你感兴趣，可见： BTreeMap's source

简单的说，我们不能在rust中考虑兼具优雅和高效（指仅使用这篇文章的知识下），所以我们不得不选择传统方案。

那我们的结构和上一章差不多，多了个尾巴

变体（Variance）和子类型（Subtyping）

对于unsafe集合来说，我们有五个难点需要解决：

1. 抠皮子：Variance
2. 挂马子：Drop Check
3. 追疯子：NonNull Optimizations
4. 操傻子：The isize::MAX Allocation Rule
5. 买瓜子~：Zero-Sized Types

其中第四和第五点我们并不需要考虑。

第三点我们可以解决，但是比较麻烦，因为这就意味着我们放弃了内存利用率。

第二个是我曾经坚持认为非常重要的东西，std 搞砸了，但默认值是安全的，搞砸它的方式不稳定，你需要非常努力地注意到默认值的局限性，所以，不要担心。

那么我们实际要处理的是第一点。老实说，我们完全可以不考虑，但是本着来都来了的精神，还是得尽善尽美。

其实rust有子类型，比如&'big T实际上是&' small T的子类型（subtype）。为什么？因为如果某些代码需要一个针对程序的某个特定区域的引用，那么通常给它一个存在更长时间的引用是完全可以的。就像，直觉上这是真的，对吧？

比如：

这是完全可以的！

然后我们来改变下，使用std::cell::Cell，

这个时候就不行了，为啥？我们压根没动生命周期？我们再来看下使用Vec包裹：

可以？！

这就是我们要解决的问题： ✨Variance✨

subtyping也不总是safe的，万一一个可变引用搭配上std::mem::swap这种骚操作，直接变成一个悬浮引用。

这就是原因，Cell直接把T变成&mut T，那么就是一invariant了。

如果你想要知道真相的细节，可见： nomicon's chapter on subtyping 。

所以要支持subtyping的前提就是不可变。

与非变体（invairant）相对的基本就是协变（covariant）的，这只是意味着子类型“通过(passes through)”它并继续正常工作（也有逆变类型使子类型倒退，但它们真的很少见，没有人喜欢它们，所以我不会再提到它们）。

集合大概都有一个可变指针指向它们的数据，所以你可能会想它们得是invariant的。然而实际上并不是，因为所有权系统， Vec<T>语义上（semantically）相当于T，并且这意味着它协变是安全的。

不过对于我们的链表来说，不行，它是invariant的：

为啥呢？rust又是怎么决定这些变体的呢？那还得回到很久以前，在1.0之前，直接放开，允许人们指定他们想要的变体，然后变的乱七八糟，并且造成连锁反应。

子类型和变体真的很难理解，核心开发人员在基本术语上确实存在分歧！因此，我们转向了“示例变体”方法：编译器只查看您的字段并复制它们的变体。如果有任何分歧，那么不变性总是获胜，因为这是安全的。

那么回到我们的类型中，为什么我们的链表有问题？

因为我们使用了原始指针*mut。

原始指针可以让我们做任何事，但是它们也需要遵守一个安全的特性：因为大多数人（我就是。。。）并不知道变体和子类型这两种东西，并且不正确协变会让一切变得非常危险，所以*mut T是invariant的，因为它可以通过as变成&mut T。

与 *mut T 不同，NonNull 被选为 T 的协变。这使得在生成协变类型时可以使用 NonNull，但实际上如果在不应该是协变的类型中使用，则会带来不健全的风险。

来看下NonNull<T>：

其实就是封装的*const T，选择*const T是因为它是协变的，然后它的一些api让它看起来是*mut T而已。

这就是为什么集合在rust中是协变的。

所以我们应该也用上NonNull<T>，那么理论上我们要上实现我们的链表就不存在难点了。

那么我们的类型就是：

注意这里的PhantomData，每次操作原始指针的时候都需要有一个Ghost来保护它。

Zero-sized type used to mark things that “act like” they own a T.

Adding a PhantomData<T> field to your type tells the compiler that your type acts as though it stores a value of type T, even though it doesn’t really. This information is used when computing certain safety properties.

前面好像说过了？它是我们为编译器提供额外“示例”字段的一种方式，该字段在概念上存在于您的类型中，但由于各种原因（间接、类型擦除等）而不存在。在本例中，我们使用 NonNull，因为我们声称我们的类型的行为“好像”它存储了一个值 T，因此我们添加了一个 PhantomData 来显式显示它。

简单的说就是标记某个类型，让它可以表现得像它保存的T。

基础方法

ok，经过上面一大段晦涩难懂的理论分析，我们确定下来了我们的类型结构，接下来我们来实现它的方法。

首先是犯下傲慢罪的new：

没什么好说的，PhantomData是一个特殊的类型，它可以没有字段！。

然后是push_front，这货我们轻车熟路：

然后报错了：

NonNull并不能自动解引用，我们得手动使用std::ptr::NonNull::as_ptr。

这回没问题了，我们再来实现pop_front，这个更简单

如果有，出并且指针指向下一个节点，然后还得判断边缘场景。

ok，组合拳搞完，来写测试用例：

Drop and Panic Safety

上面的代码有个点其实没介绍：debug_assert!，这是个声明宏，用在runtime断言是否是true，否则panic。

我们在几处地方都用到了这个，为什么呢？

因为我们是unsafe，编译器帮不了忙，所以我们得自己注意点，对于调用方来说，有问题直接停止执行才是正确的。

相关可见：exception safety (或者叫 panic safety, unwind safety, ...)。

panic是一种释放(unwinding)，这意味着所有的函数都会立即的返回。

但是程序并不会立即终止！

比如unwind是可以被捕获的，另外解构器（destructors）在函数返回时执行。不要相信panic的时机！它总是隐式的提前返回！

所以我们的panic位置也需要考虑，比如pop_front函数中

在执行到debug_assert!(self.len == 1)这一行的时候，我们的节点在栈中，我们从它里面把元素拿了出来，如果这里panic返回了，这个Box就会被释放，然后这个节点也会被释放！

然而我们的指针还指着这个节点！

然后回到我们的代码中：

这一行其实有类似的问题，但是它更安全些，只需要我们不去信任len就什么问题都没有......

其实编译器会在编译阶段判断这货会不会溢出（上溢和下溢），所以安全很多。

在实现过程中，只要我们确保在别人注意到之前修复它们，我们可以临时性的破坏invariants。这实际上是 Rust 的集合所有权和借用系统的 "杀手级应用 "之一：如果一个操作需要一个 &mut Self，那么我们就能保证对我们的集合拥有独占访问权，而且我们可以暂时破坏invariants，因为我们知道没有人能偷偷摸摸地破坏它。

最好的例子：Vec::drain，允许我们破坏Vec核心的invariant，然后将袁术从他里面搬出来。我们drain拿到的是&mut的，所以保证了invariant。直到这个数据被释放。

这看起来貌似很完美，然而并不是（It's not perfect）。实际上我们不能依赖与析构器（can't rely on destructors in code you don't control to run），这货不是我们能控制的。不过我们还有别的方案： we just set the Vec's len to 0 at the start（约等于手动释放，属于是同归于尽，You leak me? I leak you! An eye for an eye! True justice!）。

实际上我们还是有场景可以这么做的：BinaryHeap::sift_up case study。

扯大远，我们有两种方法可以让我们的代码更健壮：

• 更积极地使用 Option::take 这样的操作，因为它们更 "事务性（transactional）"，更倾向于保留invariants。
• 放弃 debug_asserts，相信自己能写出更好的测试，并使用专用的 "完整性检查 "函数，而这些函数永远不会在用户代码中运行。

其实第一种理论上更好，但是实战碍手碍脚。所以我们还是使用第二种方案。

那么目前的代码就是：

剩余部分

我们来实现剩余的部分。

首先是drop：

没差

然后是front的peek俩兄弟

接下来是iterator仨兄弟，也就是前面坑惨我们的，因为是双向链表，所以我们还是使用DoubleEndedIterator。不同的是因为这次是面向生产环境的，所以我们还得实现 ExactSizeIterator 。那么我们就得实现next、size_hint、next_back和len。

IntoIter：

iter：

基本是之前那一套，IterMut和Iter差不多就不写了。

整套代码：

额外功能

既然是面向生产环境的，那还得搞一些好用实用的方法。

比如集合常见的is_empty和clear：

还有一些常见的trait，比如Debug之类的：

这里并不适合使用#[derive()]的方式，那适用于简单的类型。

这里需要额外提一下的就是Hash, 我们先是对len进行hash，如果我们不这么做，那么它们可能会意外地使自己容易受到前缀冲突的影响(they can accidentally make themselves vulnerable to prefix collisions)，比如："he", "llo"和"hello"我们怎么区分？所以我们这里以长度作为区分。

Testing

我们前面把断言去掉的时候就意味着我们需要更多的测试用例用来测试我们的链表是否正确、安全。

记得也过一遍miri。

Send, Sync, and Compile 测试

我们这个链表是面向生产环境的，所以我们还需要测试多线程部分。

Send和Sync前面说过，是marker trait，用来标记这个数据是线程间安全的，一般我们不需要手动标记，会自动实现。前面说过的使用内部可变性会选择移除这俩标记。

那么我们的这个链表是线程安全的么？

我们来测试下：

编译失败了，这意味着我们的链表不是线程安全的。

其实*const T和*mut T也是选择退出了线程安全。

不过我们可以手动实现（一般不建议这么做）

需要注意，unsafe的前缀是必须的。

我们不需要实现任何方法，只要自己保证是线程安全的即可。

另外我们并不需要给IntoIter实现，因为它自己能自动实现。

这里还有主动退出的实现：

我们重新编译下：

ok!

不过这是相当危险的行为，尤其是对IterMut，这货表现的像&mut T，理论上应该是invariant的，我们应该更慎重一点，需要测试多次相关场景。

我们可以使用rustdoc，如果我们的文档注释中带有代码块，那么编译器在编译的时候就会尝试去运行：

ok，这回证明这货确实是invariant的。文档代码带有解释性，所以编译的结果支持失败，这样就可以搭配上注释，更好的说明api的注意事项。

使用compile_fail，另外我们还可以带上错误码，比如：

简单介绍下Cursors

现在我们的链表已经实现了，但是完全不能没用，因为性能有很大的问题，且没有多少api可以使用。

如果要做到可用，我们至少还得做以下几点：

• 🚫 支持奇怪的侵入性东西（ weird intrusive stuff）
• 🚫 支持奇怪的无锁东西（ weird lockfree stuff）
• 🚫 支持动态大小的类型（ Dynamically Sized Types）
• 🌟 O(1)时间复杂度的push和pop，不需要平摊（ amortization ）（如果你愿意相信内存分配（malloc）是O(1)）
• 🚫 O(1) 时间复杂度的split
• 🚫 O(1) 时间复杂度的splice

前面几个我们就不考虑了，但是最后这俩我们现在可以做。

按理说链表是做不到的，它的优势在于push和pop或者移除中间某个节点并不影响链表自身，集合则会更新自己的索引，相对带来的缺点自然是索引这块完全无优势。我们需要O(k)的时间才能去到第k个元素的位置，根本做不到O(1)。

集合有它们的方法split(index)，可以通过下标去分割，那么我们是否也可以想一个类似的方案？

按常规方案是做不到的。

RFC in 2018 to add Cursors to Rust's LinkedList

???这是要上天

我们的主角：Cursor in std::io - Rust (rust-lang.org)

顾名思义，它的功能和光标一样，可以在我们的序列中穿梭。并且可以根据我们的预期直接去到某一个地方。

不过（2018文章中的）对链表实现的光标有一点区别，原本光标是两个元素之间，而文中实现的cursor是指向当前元素。

不过这里还有篇文章：2022, and Rust 1.60 still has Cursor marked as unstable里面又提到了光标总是在两个元素之间，为了实现这一点，他们往里搞了个ghost元素（听起来怪眼熟的）

是更新还是前后矛盾？？？

然后作者又整理了下：

Cursor 就像一个迭代器，只不过它可以自由地来回搜索，并且可以在迭代过程中安全地改变列表。这是因为其生成的引用的生存期与其自身的生存期相关联，而不仅仅是基础列表。这意味着游标不能同时生成多个元素。

游标始终位于列表中的两个元素之间，并以逻辑循环方式编制索引。为了适应这一点，在列表的头部和尾部之间有一个“幽灵”非元素，它产生 None。

创建后，光标从幻影和列表前面开始。也就是说，next 将产生列表的前面，而 prev 将产生 None。再次调用 prev 将产生尾部。

那么回到我们的问题，我们要实现光标，我们需要做到下面几点：

• 指向两个元素中间
• 跟踪谁是下一个index
• 更新列表本身以修改 front/back/len。

实现Cursors

不过在开始实现之前，我们这里有个难点是关于CursorMut的，因为不可变比较无趣。

我们先总结下，光标是一个ghost元素，值为None，指向链表的start或者end，然后这个光标可以在链表中穿梭，为了实现这几点，我们需要光标保存：

• 一个指针指向当前节点
• 一个指针指向链表
• 当前索引

等等，那么指向ghost的指引又是啥？

怎么和前面说的又不一样了。。

其实原因是Cursor返回一个Option<usize>，std做了一堆额外的操作去优化掉这个Option<T>，然而我们是一个链表，这是ok的。另外std还有一个cursor_front/cursor_back的东西，可以将光标指向头尾，当然，还是要考虑边缘场景。

你可以参照std的那么做，但是作者并不想处理边缘场景以及写一堆代码处理Option<T>：

这里有四个有趣的情况：

• 正常情况
• 正常情况，但我们移动到了幽灵节点
• 幽灵节点开始，向列表头部节点移动
• 幽灵节点开始，列表是空的，所以什么都不做

move_prev逻辑一样，但是前后颠倒

接下来，让我们添加一些方法来查看游标周围的元素：current、peek_next 和 peek_prev。 一个非常重要的注意事项：这些方法必须通过 &mut self 借用我们的游标，并且结果必须与借用绑定。我们不能让用户获得可变引用的多个副本，也不能让他们在持有该引用的情况下使用我们的 insert/remove/split/splice API！

值得庆幸的是，这是 rust 在使用生命周期省略规则时的默认设置，因此我们将默认做正确的事情！

然后我们就可以在这的基础上去splice、split等。

Split

split_front/split_back需要返回分割点前后俩链表，那这每个方法又有四种情况（split_front）：

• 正常情况
• 正常情况，但 prev 是幽灵节点
• 幽灵节点情况，我们返回整个列表，然后变成空列表
• 幽灵节点情况，但列表是空的，所以什么也不做，返回空列表

我们先从极端的第三种场景处理：

返回一整个列表，然后自己空了。

然后我们来处理一般情况：

我们需要把下面这个：

切割成下面这个

那这个还是比较麻烦的，我们要断开链表，然后调整链表自身的字段：

其中：

处理了第二种场景。

我们还可以做一下优化：

• 把(*cur.as_ptr()).front变成(*cur.as_ptr()).front.take
• 请注意，new_back 是一个 noop，只需删除两者即可

split_back/after直接复制粘贴。

Splice

还剩下splice_before以及split_after俩，这货的边缘场景挺多，比如俩空链表拼接，还是先分析splice_before：

• 如果他们的列表是空的，我们就什么都不用做。
• 如果我们的列表是空的，那么我们的列表就变成了他们的列表。
• 如果我们指向的是幽灵节点，则追加到后面（更改 list.back）
• 如果我们指向的是第一个元素（0），则追加到前面（更改 list.front）
• 一般情况下，我们会进行大量的指针操作

我们预期把下面这个

变成：

好吧，这个程序真的很可怕，现在真的感觉到 Option 的痛苦了。但我们可以做很多清理工作。首先，我们可以把这段代码拖到最后。

好了，现在在分支 "we're empty" 中有以下错误。所以我们应该使用 swap:

Use of moved value: input

在我反向思考下面这种情况时，我发现了这个 unwrap 有问题(因为 cur 的 front 在前面已经被设置为其它值了)：

这行也是重复的，可以提升:

好了，把上面的问题修改后得到这些：

还是不对，下面的代码存在bug：

我们使用 take 拿走了 input.front 的值，然后在下一行将其 unwrap！boom，panic！

总之，我已经筋疲力尽了，所以 insert 和 remove 以及所有其他应用程序接口就留给读者练习。 下面是 Cursor 的最终代码，我做对了吗？我只有在写下一章并测试这个怪东西时才能知道！

测试光标

开搞

错俩，我们先来看下第一个的问题

搞错，如果self.cur是None，我们并不能直接返回None，我们还需要检查self.list.front，因为我们处在ghost的位置：

然而还是错了

那我们单独处理这两种情况：

你有没有注意到前面注释掉了一些用于测试remove_current的代码的部分？是的，这个测试是有状态的。让我们创建一个新列表，其中包含remove_current部分将留给我们的状态

这回没问题了，不过稳妥点，我们再搞一个检测下：

完成！！！

总结

最终整合的代码放下期，因为超出知乎输入上限了！

。。。。。。是不是脑子要炸了，其实是我的问题，建议这段是看原文，尤其是光标那一块的知识。