5.7 数据布局与基本操作回顾
原文链接: https://rust-unofficial.github.io/too-many-lists/fifth-layout-basics-redux.html
前三节 TL;DR：随机混合 &、&mut、Box 等安全指针与 *mut、*const 等不安全指针是未定义行为的配方，因为安全指针引入了我们在裸指针上没有遵守的额外约束。
天哪我又得写链表了。好吧。好吧。没事。我们没事。
这节会很快搞定很多，因为我们在第一次尝试时已经讨论过设计，我们做的一切基本上正确，除了如何混合安全和 unsafe 指针。
布局
所以在新布局里我们只使用裸指针，一切都会完美，我们再也不会犯错。
这是我们旧的坏布局：
1
2
3
4
5
6
7
8
9
10
11
| pub struct List<T> {
head: Link<T>,
tail: *mut Node<T>, // 无辜且善良
}
type Link<T> = Option<Box<Node<T>>>; // 真正的邪恶
struct Node<T> {
elem: T,
next: Link<T>,
}
|
这是新布局：
1
2
3
4
5
6
7
8
9
10
11
| pub struct List<T> {
head: Link<T>,
tail: *mut Node<T>,
}
type Link<T> = *mut Node<T>; // 好多了
struct Node<T> {
elem: T,
next: Link<T>,
}
|
记住：用裸指针时 Option 没那么好用，所以我们不再用它。后面章节会看 NonNull 类型，现在别担心。
基础
List::new 基本上一样。
1
2
3
4
5
6
7
| use ptr;
impl<T> List<T> {
pub fn new() -> Self {
List { head: ptr::null_mut(), tail: ptr::null_mut() }
}
}
|
Push 基本上是 s-
1
2
| pub fn push(&mut self, elem: T) {
let mut new_tail = Box::new(
|
等等我们不用 Box 了。没有 Box 怎么分配内存？
嗯，我们可以用 std::alloc::alloc，但那像把武士刀带进厨房。能干活但有点杀鸡用牛刀且笨拙。
我们想要有 box，但不要。一个完全疯狂但也许可行的选项是做这样的事：
1
2
3
4
5
| struct Node<T> {
elem: T,
real_next: Option<Box<Node<T>>>,
next: *mut Node<T>,
}
|
想法是我们创建 Box 存在节点里，然后取裸指针进去，在用完节点想销毁之前只用裸指针。然后可以从 real_next take 出 Box 并 drop。我想那符合我们非常简化的 stacked borrows 模型？
如果你想试试，祝"乐"，但那看起来太糟了吧？这不是 Rc 和 RefCell 那章，我们不再玩这个游戏了。我们要做简单干净的东西。
所以我们用非常好的 Box::into_raw 函数：
1
| pub fn into_raw(b: Box<T>) -> *mut T
|
Consumes the Box, returning a wrapped raw pointer.
The pointer will be properly aligned and non-null.
After calling this function, the caller is responsible for the memory previously managed by the Box. In particular, the caller should properly destroy T and release the memory, taking into account the memory layout used by Box. The easiest way to do this is to convert the raw pointer back into a Box with the Box::from_raw function, allowing the Box destructor to perform the cleanup.
Note: this is an associated function, which means that you have to call it as Box::into_raw(b) instead of b.into_raw(). This is so that there is no conflict with a method on the inner type.
Examples
Converting the raw pointer back into a Box with Box::from_raw for automatic cleanup:
1
2
3
| let x = Box::new(String::from("Hello"));
let ptr = Box::into_raw(x);
let x = unsafe { Box::from_raw(ptr) };
|
好，看起来* literally* 为我们的用例设计的。也符合我们试图遵循的规则：从安全的东西开始，转成裸指针，然后只在最后（想 Drop 时）转回安全的东西。
这基本上就像做奇怪的 real_next 事，但不必费心存储 Box，反正和裸指针是完全相同的指针。
既然到处都用裸指针了，别担心把 unsafe 块弄窄：现在全是 unsafe 了。（一直都是，但有时候骗骗自己挺好。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| pub fn push(&mut self, elem: T) {
unsafe {
// 立刻把 Box 转成裸指针
let new_tail = Box::into_raw(Box::new(Node {
elem: elem,
next: ptr::null_mut(),
}));
if !self.tail.is_null() {
(*self.tail).next = new_tail;
} else {
self.head = new_tail;
}
self.tail = new_tail;
}
}
|
嘿，坚持裸指针后代码实际上看起来干净多了！
继续 pop，也和我们离开时 pretty 相似，不过得记得用 Box::from_raw 清理分配：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| pub fn pop(&mut self) -> Option<T> {
unsafe {
if self.head.is_null() {
None
} else {
// 从坟墓中崛起
let head = Box::from_raw(self.head);
self.head = head.next;
if self.head.is_null() {
self.tail = ptr::null_mut();
}
Some(head.elem)
}
}
}
|
我们可爱的 take 和 map 死了，现在得手动检查和设置 null。
趁我们在这里，加上析构函数。这次实现成反复 pop，因为可爱又简单：
1
2
3
4
5
| impl<T> Drop for List<T> {
fn drop(&mut self) {
while let Some(_) = self.pop() { }
}
}
|
现在，真相时刻：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
// 检查空链表行为正确
assert_eq!(list.pop(), None);
// 填充链表
list.push(1);
list.push(2);
list.push(3);
// 检查正常移除
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), Some(2));
// 再压入一些，确保没有损坏
list.push(4);
list.push(5);
// 检查正常移除
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(4));
// 检查耗尽
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), None);
// 检查耗尽情况正确修复了指针
list.push(6);
list.push(7);
// 检查正常移除
assert_eq!(list.pop(), Some(6));
assert_eq!(list.pop(), Some(7));
assert_eq!(list.pop(), None);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| cargo test
running 12 tests
test fifth::test::basics ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test second::test::basics ... ok
test fourth::test::into_iter ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test result: ok. 12 passed; 0 failed; 0 ignored; 0 measured
|
好，但 miri 同意吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri test
running 12 tests
test fifth::test::basics ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test second::test::basics ... ok
test fourth::test::into_iter ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test result: ok. 12 passed; 0 failed; 0 ignored; 0 measured
|
耶！！！！！
真的他妈成功了！
大概！
未能发现未定义行为并不能证明它不在那里等着制造问题，但对于一本关于链表的笑话书我愿意严谨到什么程度是有限度的，所以我们把这称为 100% 机器验证的证明，任何反对的人可以去 suck my COQ！
∴ QED □