1 递归地定义链表

  • 链表：堆上的一组数据，每个数据依次指向下一个数据。
  • 函数式程序员会这样递归地定义链表：
  1. List a = Empty | Elem a (List a)
  • 这种递归的定义表达了一种 和类型(sum type)：可以含有不同类型值的类型。

  • 关于和类型、积类型等，可参考：http://www.sohu.com/a/320887508_473282

    2 错误的链表定义

  • Rust用enum定义和类型。

  1. pub enum List {
  2.     Empty,
  3.     Elem(i32, List),
  4. }
  • 上述代码无法通过编译：递归类型List具有无限大小，建议加入Box、Rc、&之类的间接引用机制。

    3 Box

  1. pub struct Box<T>(_) where T: ?Sized;
  • Box<T>是一种用于堆分配的指针类型，通常被称作box，是Rust中最简单的堆分配形式。
  • Box<T>会拥有分配的值的所有权，在超出作用域时释放分配的值。
  1. #[derive(Debug)]
  2. enum List<T> {
  3.     // 递归定义必须装箱，这样写不可以：Cons(T, List<T>)
  4.     // 因为这样写的时候，List的大小取决于有多少个元素，无法知道需要为Cons分配多大内存
  5.     // 使用具有确定大小的Box<List<T>>，则Cons大小确定，可以为其分配内存。
  6.     Cons(T, Box<List<T>>),
  7.     Nil,
  8. }
  10. fn main() {
  11.     let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
  12.     println!("{:?}", list);// Cons(1, Box(Cons(2, Box(Nil))))
  13. }

4 正确的链表定义

  1. pub enum List {
  2.     Empty,
  3.     Elem(i32, Box<List>),
  4. }

4.1 第一种内存布局

  • 一个有两个元素的链表：
  1. [] = Stack
  2. () = Heap
  3. [Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)
  • 两个问题：
    1. 最后一个节点仅用于表示”这不是一个节点“
    2. 第一个节点没有分配在堆上

      4.2 第二种内存布局

  1. [ptr] -> (Elem A, ptr) -> (Elem B, *null*)
  • 每个节点都在堆上分配
  • 两种内存布局的差别在于：如何表示空节点
    • 第一种内存布局：用枚举值Empty表示空节点。然而，Empty这个枚举值的大小，等于Elem的大小：每个枚举值的大小相等，等于最大的变体的大小！这是一种空间浪费。
    • 第二种内存布局：用Elem(i32,Box<List>)中的Box<List>为空指针来表示空节点，而不用一个额外的空节点，少占用一点内存。
  • 为理解第一种内存布局中的垃圾节点，需要了解枚举类型的内存布局。

    4.3 enum的内存布局

  1. enum Foo {
  2.     D1(T1),
  3.     D2(T2),
  4.     ...
  5.     Dn(Tn),
  6. }
  • Foo类型需要一个整数表示枚举类型值所属的变体类型（D1、D2、…Dn），这就是枚举的标签(tag)
  • 此外还需要足够的空间来存储T1、T2、…Tn中最大的类型（此外可能还需要一些额外空间以满足内存对齐要求）。

4.4 两种内存布局的比较

  • 第一种内存布局中，Empty仅仅是单个比特的信息，但也要消耗一个指针加一个元素的空间（等同于Elem），因为Empty需要随时准备好变成Elem，从而使得第一种内存布局比第二种占用的空间要多一点。
  • 第一种内存布局中，第一个节点没有分配在堆上，这不如把所有节点分配在堆上的第二种内存布局：因为这采用了不一致的节点布局（第一个节点在栈上，其他节点在堆上）。这种不一致对push/pop操作没什么影响，但对切分和合并链表操作有明显的影响。
  • 此外，链表的一大优点是可以在节点本身中构建元素，从而使得在不移动元素的情况下进行洗牌（shuffle)成为可能：调整指针就可以达到“移动”元素的效果。但是，第一种布局不支持这种操作。
  • 显然，第一种内存布局不好。如何改写上述链表定义？
  1. pub enum List {
  2.     Empty,
  3.     ElemThenEmpty(i32),
  4.     ElemThenNotEmpty(i32, Box<List>),
  5. }
  • 这种写法更差劲。最明显的是：逻辑变复杂了，不仅元素布局不一致，而且多了一种完全无效的状态：ElemThenNotEmpty(i32, Box<Empty>)。
  • 这种写法完全避免了分配Empty的情况，相对于第一种内存布局，减少了堆分配次数，却会浪费更多空间。因为先前的布局可应用空指针优化。

    5 空指针优化

  1. enum Foo {
  2.     A,
  3.     B(ContainsANonNullPtr),
  4. }
  • 上面的枚举定义将使用空指针优化：枚举值是A时，整个枚举被设置成零；否则，设置成B。不需要额外的tag来表示枚举当前使用哪种变体（A或者B）。
  • 很多其他枚举和类型可以应用这种空指针优化。
  • Rust会对枚举进行各种优化，但空指针优化是最重要的：&、&mut、Box、Rc、Arc和Vec放入Option中时没有开销！

6 最终版本

  • 如何达到没有额外的垃圾节点、分配方式一致、节点内存布局一致，同时可使用空指针优化的目标？
  • 需要区分链表元素和链表！需要像C那样来考虑问题：结构体！
  • 枚举是一种可以有多种不同类型值的类型（但任何时刻只有一种确定类型的值），而结构体可以同时包含多个不同类型的值（积类型？）。
  • 需要将链表切分成两个类型：链表、节点。
  1. struct Node {
  2.     elem: i32,
  3.     next: List,
  4. }
  6. pub enum List {
  7.     Empty,
  8.     More(Box<Node>),
  9. }
  • 目标检查
    • 从不分配额外的垃圾节点：达成（用next字段值为Empty来表示没有下一个空节点；如果整个列表为空，则直接使用Empty值）
    • 枚举采用了空指针优化：达成
    • 所有元素的分配方式一致：达成（只会在堆上分配Node）
  • 但是编译通不过：公有类型List引用了私有类型Node。可以把Node标记成公有的，但通常应该隐藏实现细节，Node应该保持为私有。
  • 解决方案：让List成为结构体：
  1. struct Node {
  2.     elem: i32,
  3.     next: Link,
  4. }
  6. enum Link {// 原来的List
  7.     Empty,
  8.     More(Box<Node>),
  9. }
  11. pub struct List {// 新的List采用结构体类型
  12.     head: Link,
  13. }
  • 编译还是出警告，因为各个类型还没有被使用。下一节才会使用上面代码定义的类型。