6.10 实现游标

11 分钟阅读

原文链接: https://rust-unofficial.github.io/too-many-lists/sixth-cursors-impl.html

好，我们只搞 std 的 CursorMut，不可变版其实没意思。和最初设计一样，有个 “ghost” 元素用 None 表示链表头尾，可以「走过去」绕到另一侧。实现需要：

指向当前节点的指针
指向链表的指针
当前 index

等等，指向 “ghost” 时 index 是什么？

皱眉 … 查 std … 不喜欢 std 的答案

合理地说，Cursor 的 index 返回 Option<usize>。std 实现搞一堆 junk 避免存成 Option 但……我们是链表，没事。std 还有 cursor_front/cursor_back，从 front/back 元素开始，直觉，但链表空时得做怪事。

想要可以自己实现，但我砍掉重复 gunk 和 corner case，只做 bare cursor_mut 从 ghost 开始，用户用 move_next/move_prev 走到想要的（真想的话再包成 cursor_front）。

开干：

1
2
3
4
5
pub struct CursorMut<'a, T> {
    cur: Link<T>,
    list: &'a mut LinkedList<T>,
    index: Option<usize>,
}

很 straight-forward，bullet 每项一个字段！现在 cursor_mut：

1
2
3
4
5
6
7
8
9
impl<T> LinkedList<T> {
    pub fn cursor_mut(&mut self) -> CursorMut<T> {
        CursorMut { 
            list: self, 
            cur: None, 
            index: None,
        }
    }
}

从 ghost 开始，一切 None 就行，nice and simple！接下来移动：

 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
impl<'a, T> CursorMut<'a, T> {
    pub fn index(&self) -> Option<usize> {
        self.index
    }

    pub fn move_next(&mut self) {
        if let Some(cur) = self.cur {
            unsafe {
                // 我们在真实元素上，走向它的 next（back）
                self.cur = (*cur.as_ptr()).back;
                if self.cur.is_some() {
                    *self.index.as_mut().unwrap() += 1;
                } else {
                    // 刚走到 ghost，没有 index 了
                    self.index = None;
                }
            }
        } else if !self.list.is_empty() {
            // 在 ghost 上，有真实 front，移过去！
            self.cur = self.list.front;
            self.index = Some(0)
        } else {
            // 在 ghost 上，但那是唯一元素……什么都不做。
        }
    }
}

有 4 种有趣情况：

正常情况
正常情况, but we reach the ghost
ghost 情况，走向链表 front
ghost 情况，链表空，什么都不做

move_prev 逻辑完全一样，只是 front/back 和 index 变化反过来：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
pub fn move_prev(&mut self) {
    if let Some(cur) = self.cur {
        unsafe {
            // 我们在真实元素上，走向它的 previous（front）
            self.cur = (*cur.as_ptr()).front;
            if self.cur.is_some() {
                *self.index.as_mut().unwrap() -= 1;
            } else {
                // 刚走到 ghost，没有 index 了
                self.index = None;
            }
        }
    } else if !self.list.is_empty() {
        // 在 ghost 上，有真实 back，移过去！
        self.cur = self.list.back;
        self.index = Some(self.list.len - 1)
    } else {
        // 在 ghost 上，但那是唯一元素……什么都不做。
    }
}

接下来加看 cursor 周围元素的方法：current、peek_next、peek_prev。**非常重要：**这些方法必须 &mut self 借用 cursor，结果必须绑在该借用上。不能让用户拿多份可变引用，也不能在持有这种引用时用 insert/remove/split/splice API！

好在 lifetime elision 下 Rust 默认就是这样，我们默认就做对！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
pub fn current(&mut self) -> Option<&mut T> {
    unsafe {
        self.cur.map(|node| &mut (*node.as_ptr()).elem)
    }
}

pub fn peek_next(&mut self) -> Option<&mut T> {
    unsafe {
        self.cur
            .and_then(|node| (*node.as_ptr()).back)
            .map(|node| &mut (*node.as_ptr()).elem)
    }
}

pub fn peek_prev(&mut self) -> Option<&mut T> {
    unsafe {
        self.cur
            .and_then(|node| (*node.as_ptr()).front)
            .map(|node| &mut (*node.as_ptr()).elem)
    }
}

脑子放空，Option 方法和（省略的）编译器错误代劳思考。我对 Option<NonNull> 持怀疑态度，但真该死，它真让我可以 autopilot。写基于数组的集合太久从不用 Option，哇，真舒服！（(*node.as_ptr()) 仍然很痛苦，Rust 裸指针嘛……）

接下来有个选择：直接上 split 和 splice——这些 API 的全部意义所在——还是先 baby-step 做单元素 insert/remove。感觉 insert/remove 会用 split/splice 实现……先做 split/splice，看牌怎么落（打字时真心不知道）。

Split

先 split_before 和 split_after，返回当前元素前/后的所有东西为 LinkedList（在 ghost 处停，除非你在 ghost 上，那时返回整链表、cursor 指向空链表）：

眯眼这个其实不简单，得一步步讲。

split_before 有 4 种可能有趣的情况：

正常情况
正常情况，但 prev 是 ghost
ghost 情况：返回整链表并变空
ghost 情况，链表为空：什么都不做，返回空链表

从 corner case 开始。第三种我相信就是

1
mem::replace(self.list, LinkedList::new())

对吧？我们变空，返回整链表，字段已是 None，不用更新。好。嘿，第四种也做对了！

正常情况……需要 ASCII 图。最一般的情况：

1
2
3
list.front -> A <-> B <-> C <-> D <- list.back
                          ^
                         cur

目标：

1
2
3
4
5
list.front -> C <-> D <- list.back
              ^
             cur

return.front -> A <-> B <- return.back

要断开 cur 和 prev 的链接，天哪好多要改。拆成步骤说服自己。有点啰嗦，但至少说得通：

 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
42
43
44
45
pub fn split_before(&mut self) -> LinkedList<T> {
    if let Some(cur) = self.cur {
        // 指向真实元素，链表非空。
        unsafe {
            // 当前状态
            let old_len = self.list.len;
            let old_idx = self.index.unwrap();
            let prev = (*cur.as_ptr()).front;
            
            // self 将变成
            let new_len = old_len - old_idx;
            let new_front = self.cur;
            let new_back = self.list.back;
            let new_idx = Some(0);

            // 输出将变成
            let output_len = old_len - new_len;
            let output_front = self.list.front;
            let output_back = prev;

            // 断开 cur 与 prev 的链接
            if let Some(prev) = prev {
                (*cur.as_ptr()).front = None;
                (*prev.as_ptr()).back = None;
            }

            // 产生结果：
            self.list.len = new_len;
            self.list.front = new_front;
            self.list.back = new_back;
            self.index = new_idx;

            LinkedList {
                front: output_front,
                back: output_back,
                len: output_len,
                _boo: PhantomData,
            }
        }
    } else {
        // 在 ghost 上，用空链表替换我们的链表。
        // 无需改变其他状态。
        std::mem::replace(self.list, LinkedList::new())
    }
}

注意 if-let 处理「正常情况但 prev 是 ghost」：

1
2
3
4
if let Some(prev) = prev {
    (*cur.as_ptr()).front = None;
    (*prev.as_ptr()).back = None;
}

若你想，可以合并并优化：

把两次访问 (*cur.as_ptr()).front 合并成 (*cur.as_ptr()).front.take()
注意 new_back 是空操作，直接删掉

据我所知其余情况碰巧都做对了。写测试见分晓！（复制粘贴做 split_after）

我不再犯错了，尽量写最不容易出错的代码。我实际上写集合就这样：拆成琐碎步骤和分支，直到能放进脑子、看起来不会出错。然后大量测试，直到确信没搞砸。

我做的大多数集合工作极其 unsafe，一般不能靠编译器抓错，当年 miri 还不存在！只能盯到头疼，永远永远永远不要犯错。

别写 Unsafe Rust！Safe Rust 好太多！！！！

Splice

最后一个 boss：splice_before 和 splice_after，expect corner-casiest。接收 LinkedList 把内容 graft 进 ours。我们空、他们空、ghost……* sigh* splice_before 一步步来。

他们空，不用做。
我们空，就变成他们的链表。
指向 ghost，append 到 back（改 list.back）
指向第一个元素 (0)，append 到 front（改 list.front）
一般情况，大量 pointer fuckery。

一般情况：

1
2
3
4
5
input.front -> 1 <-> 2 <- input.back

 list.front -> A <-> B <-> C <- list.back
                     ^
                    cur

Becoming this:

1
list.front -> A <-> 1 <-> 2 <-> B <-> C <- list.back

Ok？Ok。写……深吸一口气冲：

 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
42
43
44
45
46
47
48
    pub fn splice_before(&mut self, mut input: LinkedList<T>) {
        unsafe {
            if input.is_empty() {
                // input 为空，什么都不做。
            } else if let Some(cur) = self.cur {
                if let Some(0) = self.index {
                    // We're appending to the front, see append to back
                    (*cur.as_ptr()).front = input.back.take();
                    (*input.back.unwrap().as_ptr()).back = Some(cur);
                    self.list.front = input.front.take();

                    // index 前移 input 长度
                    *self.index.as_mut().unwrap() += input.len;
                    self.list.len += input.len;
                    input.len = 0;
                } else {
                    // 一般情况，无边界，只做内部修复
                    let prev = (*cur.as_ptr()).front.unwrap();
                    let in_front = input.front.take().unwrap();
                    let in_back = input.back.take().unwrap();

                    (*prev.as_ptr()).back = Some(in_front);
                    (*in_front.as_ptr()).front = Some(prev);
                    (*cur.as_ptr()).front = Some(in_back);
                    (*in_back.as_ptr()).back = Some(cur);

                    // index 前移 input 长度
                    *self.index.as_mut().unwrap() += input.len;
                    self.list.len += input.len;
                    input.len = 0;
                }
            } else if let Some(back) = self.list.back {
                // 在 ghost 上但非空，追加到 back
                // 可以 `take` input 的指针或 `mem::forget`
                // it. Using take is more responsible in case we do custom
                // 分配器之类也需要清理！
                (*back.as_ptr()).back = input.front.take();
                (*input.front.unwrap().as_ptr()).front = Some(back);
                self.list.back = input.back.take();
                self.list.len += input.len;
                // 非必须但礼貌起见
                input.len = 0;
            } else {
                // 我们为空，变成 input，留在 ghost 上
                *self.list = input;
            }
        }
    }

这个 genuinely horrendous，真感到 Option<NonNull> pain。但能 cleanup。比如拉到末尾，因为总要执行。我不love（有时 noop，设 input.len 更多是对未来扩展的 paranoia）：

1
2
self.list.len += input.len;
input.len = 0;

Use of moved value: input

啊对，「我们空」时 move 链表。换成 swap：

1
2
// 我们为空，变成 input，留在 ghost 上
std::mem::swap(self.list, &mut input);

这时 writes pointless，但仍 work（也许 early-return appease 编译器）。

unwrap 是我 backward 想 case 的后果，改 if-let 问对问题可修：

1
2
3
4
5
if let Some(0) = self.index {

} else {
    let prev = (*cur.as_ptr()).front.unwrap();
}

调整 index 在分支里重复，可 hoist：

1
*self.index.as_mut().unwrap() += input.len;

Ok，合在一起：

 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
if input.is_empty() {
    // input 为空，什么都不做。
} else if let Some(cur) = self.cur {
    // 两个链表都非空
    if let Some(prev) = (*cur.as_ptr()).front {
        // 一般情况，无边界，只做内部修复
        let in_front = input.front.take().unwrap();
        let in_back = input.back.take().unwrap();

        (*prev.as_ptr()).back = Some(in_front);
        (*in_front.as_ptr()).front = Some(prev);
        (*cur.as_ptr()).front = Some(in_back);
        (*in_back.as_ptr()).back = Some(cur);
    } else {
        // We're appending to the front, see append to back below
        (*cur.as_ptr()).front = input.back.take();
        (*input.back.unwrap().as_ptr()).back = Some(cur);
        self.list.front = input.front.take();
    }
    // index 前移 input 长度
    *self.index.as_mut().unwrap() += input.len;
} else if let Some(back) = self.list.back {
    // 在 ghost 上但非空，追加到 back
    // 可以 `take` input 的指针或 `mem::forget`
    // it. Using take is more responsible in case we do custom
    // 分配器之类也需要清理！
    (*back.as_ptr()).back = input.front.take();
    (*input.front.unwrap().as_ptr()).front = Some(back);
    self.list.back = input.back.take();

} else {
    // 我们为空，变成 input，留在 ghost 上
    std::mem::swap(self.list, &mut input);
}

self.list.len += input.len;
// 非必须但礼貌起见
input.len = 0;

// input 在这里 drop

Alright 仍 sucks，但 mostly——不对刚发现 bug：

1
2
    (*back.as_ptr()).back = input.front.take();
    (*input.front.unwrap().as_ptr()).front = Some(back);

我们 take input.front 下一行又 unwrap！* sigh* 镜像 case 也一样。测试会 instantly 抓到，但我们 trying to be Perfect，live 写，就这一刻看到。不 usual tedious、分 phase 的报应。More explicit！

 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
42
// 可以 `take` input 的指针或 `mem::forget`
// input。用 `take` 更负责，以防将来做自定义
// 分配器之类也需要清理！
if input.is_empty() {
    // input 为空，什么都不做。
} else if let Some(cur) = self.cur {
    // 两个链表都非空
    let in_front = input.front.take().unwrap();
    let in_back = input.back.take().unwrap();

    if let Some(prev) = (*cur.as_ptr()).front {
        // 一般情况，无边界，只做内部修复
        (*prev.as_ptr()).back = Some(in_front);
        (*in_front.as_ptr()).front = Some(prev);
        (*cur.as_ptr()).front = Some(in_back);
        (*in_back.as_ptr()).back = Some(cur);
    } else {
        // 没有 prev，追加到 front
        (*cur.as_ptr()).front = Some(in_back);
        (*in_back.as_ptr()).back = Some(cur);
        self.list.front = Some(in_front);
    }
    // index 前移 input 长度
    *self.index.as_mut().unwrap() += input.len;
} else if let Some(back) = self.list.back {
    // 在 ghost 上但非空，追加到 back
    let in_front = input.front.take().unwrap();
    let in_back = input.back.take().unwrap();

    (*back.as_ptr()).back = Some(in_front);
    (*in_front.as_ptr()).front = Some(back);
    self.list.back = Some(in_back);
} else {
    // 我们为空，变成 input，留在 ghost 上
    std::mem::swap(self.list, &mut input);
}

self.list.len += input.len;
// 非必须但礼貌起见
input.len = 0;

// input 在这里 drop

Alright 这个我能 tolerate。唯一抱怨没 dedupe in_front/in_back（也许 rejig conditions 但 eh）。 basically C 里会写的，加 Option<NonNull> gunk tedious。能 live。Well 应该让裸指针更好，但 out of scope。

Anyway 累死了，insert、remove 等 API 留给读者 exercise。

Cursor 最终代码，我 copy-paste combinatorics 的尝试。对吗？下一章测试这 monstrosity 才知道！

  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
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
pub struct CursorMut<'a, T> {
    list: &'a mut LinkedList<T>,
    cur: Link<T>,
    index: Option<usize>,
}

impl<T> LinkedList<T> {
    pub fn cursor_mut(&mut self) -> CursorMut<T> {
        CursorMut { 
            list: self, 
            cur: None, 
            index: None,
        }
    }
}

impl<'a, T> CursorMut<'a, T> {
    pub fn index(&self) -> Option<usize> {
        self.index
    }

    pub fn move_next(&mut self) {
        if let Some(cur) = self.cur {
            unsafe {
                // 我们在真实元素上，走向它的 next（back）
                self.cur = (*cur.as_ptr()).back;
                if self.cur.is_some() {
                    *self.index.as_mut().unwrap() += 1;
                } else {
                    // 刚走到 ghost，没有 index 了
                    self.index = None;
                }
            }
        } else if !self.list.is_empty() {
            // 在 ghost 上，有真实 front，移过去！
            self.cur = self.list.front;
            self.index = Some(0)
        } else {
            // 在 ghost 上，但那是唯一元素……什么都不做。
        }
    }

    pub fn move_prev(&mut self) {
        if let Some(cur) = self.cur {
            unsafe {
                // 我们在真实元素上，走向它的 previous（front）
                self.cur = (*cur.as_ptr()).front;
                if self.cur.is_some() {
                    *self.index.as_mut().unwrap() -= 1;
                } else {
                    // 刚走到 ghost，没有 index 了
                    self.index = None;
                }
            }
        } else if !self.list.is_empty() {
            // 在 ghost 上，有真实 back，移过去！
            self.cur = self.list.back;
            self.index = Some(self.list.len - 1)
        } else {
            // 在 ghost 上，但那是唯一元素……什么都不做。
        }
    }

    pub fn current(&mut self) -> Option<&mut T> {
        unsafe {
            self.cur.map(|node| &mut (*node.as_ptr()).elem)
        }
    }

    pub fn peek_next(&mut self) -> Option<&mut T> {
        unsafe {
            self.cur
                .and_then(|node| (*node.as_ptr()).back)
                .map(|node| &mut (*node.as_ptr()).elem)
        }
    }

    pub fn peek_prev(&mut self) -> Option<&mut T> {
        unsafe {
            self.cur
                .and_then(|node| (*node.as_ptr()).front)
                .map(|node| &mut (*node.as_ptr()).elem)
        }
    }

    pub fn split_before(&mut self) -> LinkedList<T> {
        // 当前：
        //
        //     list.front -> A <-> B <-> C <-> D <- list.back
        //                               ^
        //                              cur
        // 
        //
        // 目标：
        // 
        //     list.front -> C <-> D <- list.back
        //                   ^
        //                  cur
        //
        // 
        //    return.front -> A <-> B <- return.back
        //
        if let Some(cur) = self.cur {
            // 指向真实元素，链表非空。
            unsafe {
                // 当前状态
                let old_len = self.list.len;
                let old_idx = self.index.unwrap();
                let prev = (*cur.as_ptr()).front;
                
                // self 将变成
                let new_len = old_len - old_idx;
                let new_front = self.cur;
                let new_back = self.list.back;
                let new_idx = Some(0);

                // 输出将变成
                let output_len = old_len - new_len;
                let output_front = self.list.front;
                let output_back = prev;

                // 断开 cur 与 prev 的链接
                if let Some(prev) = prev {
                    (*cur.as_ptr()).front = None;
                    (*prev.as_ptr()).back = None;
                }

                // 产生结果：
                self.list.len = new_len;
                self.list.front = new_front;
                self.list.back = new_back;
                self.index = new_idx;

                LinkedList {
                    front: output_front,
                    back: output_back,
                    len: output_len,
                    _boo: PhantomData,
                }
            }
        } else {
            // 在 ghost 上，用空链表替换我们的链表。
            // 无需改变其他状态。
            std::mem::replace(self.list, LinkedList::new())
        }
    }

    pub fn split_after(&mut self) -> LinkedList<T> {
        // 当前：
        //
        //     list.front -> A <-> B <-> C <-> D <- list.back
        //                         ^
        //                        cur
        // 
        //
        // 目标：
        // 
        //     list.front -> A <-> B <- list.back
        //                         ^
        //                        cur
        //
        // 
        //    return.front -> C <-> D <- return.back
        //
        if let Some(cur) = self.cur {
            // 指向真实元素，链表非空。
            unsafe {
                // 当前状态
                let old_len = self.list.len;
                let old_idx = self.index.unwrap();
                let next = (*cur.as_ptr()).back;
                
                // self 将变成
                let new_len = old_idx + 1;
                let new_back = self.cur;
                let new_front = self.list.front;
                let new_idx = Some(old_idx);

                // 输出将变成
                let output_len = old_len - new_len;
                let output_front = next;
                let output_back = self.list.back;

                // 断开 cur 与 next 的链接
                if let Some(next) = next {
                    (*cur.as_ptr()).back = None;
                    (*next.as_ptr()).front = None;
                }

                // 产生结果：
                self.list.len = new_len;
                self.list.front = new_front;
                self.list.back = new_back;
                self.index = new_idx;

                LinkedList {
                    front: output_front,
                    back: output_back,
                    len: output_len,
                    _boo: PhantomData,
                }
            }
        } else {
            // 在 ghost 上，用空链表替换我们的链表。
            // 无需改变其他状态。
            std::mem::replace(self.list, LinkedList::new())
        }
    }

    pub fn splice_before(&mut self, mut input: LinkedList<T>) {
        // 当前：
        //
        // input.front -> 1 <-> 2 <- input.back
        //
        // list.front -> A <-> B <-> C <- list.back
        //                     ^
        //                    cur
        //
        //
        // 变成：
        //
        // list.front -> A <-> 1 <-> 2 <-> B <-> C <- list.back
        //                                 ^
        //                                cur
        //
        unsafe {
            // 可以 `take` input 的指针或 `mem::forget`
            // input。用 `take` 更负责，以防将来做自定义
            // 分配器之类也需要清理！
            if input.is_empty() {
                // input 为空，什么都不做。
            } else if let Some(cur) = self.cur {
                // 两个链表都非空
                let in_front = input.front.take().unwrap();
                let in_back = input.back.take().unwrap();

                if let Some(prev) = (*cur.as_ptr()).front {
                    // 一般情况，无边界，只做内部修复
                    (*prev.as_ptr()).back = Some(in_front);
                    (*in_front.as_ptr()).front = Some(prev);
                    (*cur.as_ptr()).front = Some(in_back);
                    (*in_back.as_ptr()).back = Some(cur);
                } else {
                    // 没有 prev，追加到 front
                    (*cur.as_ptr()).front = Some(in_back);
                    (*in_back.as_ptr()).back = Some(cur);
                    self.list.front = Some(in_front);
                }
                // index 前移 input 长度
                *self.index.as_mut().unwrap() += input.len;
            } else if let Some(back) = self.list.back {
                // 在 ghost 上但非空，追加到 back
                let in_front = input.front.take().unwrap();
                let in_back = input.back.take().unwrap();

                (*back.as_ptr()).back = Some(in_front);
                (*in_front.as_ptr()).front = Some(back);
                self.list.back = Some(in_back);
            } else {
                // 我们为空，变成 input，留在 ghost 上
                std::mem::swap(self.list, &mut input);
            }

            self.list.len += input.len;
            // 非必须但礼貌起见
            input.len = 0;
            
            // input 在这里 drop
        }        
    }

    pub fn splice_after(&mut self, mut input: LinkedList<T>) {
        // 当前：
        //
        // input.front -> 1 <-> 2 <- input.back
        //
        // list.front -> A <-> B <-> C <- list.back
        //                     ^
        //                    cur
        //
        //
        // 变成：
        //
        // list.front -> A <-> B <-> 1 <-> 2 <-> C <- list.back
        //                     ^
        //                    cur
        //
        unsafe {
            // 可以 `take` input 的指针或 `mem::forget`
            // input。用 `take` 更负责，以防将来做自定义
            // 分配器之类也需要清理！
            if input.is_empty() {
                // input 为空，什么都不做。
            } else if let Some(cur) = self.cur {
                // 两个链表都非空
                let in_front = input.front.take().unwrap();
                let in_back = input.back.take().unwrap();

                if let Some(next) = (*cur.as_ptr()).back {
                    // 一般情况，无边界，只做内部修复
                    (*next.as_ptr()).front = Some(in_back);
                    (*in_back.as_ptr()).back = Some(next);
                    (*cur.as_ptr()).back = Some(in_front);
                    (*in_front.as_ptr()).front = Some(cur);
                } else {
                    // 没有 next，追加到 back
                    (*cur.as_ptr()).back = Some(in_front);
                    (*in_front.as_ptr()).front = Some(cur);
                    self.list.back = Some(in_back);
                }
                // index 不变
            } else if let Some(front) = self.list.front {
                // 在 ghost 上但非空，追加到 front
                let in_front = input.front.take().unwrap();
                let in_back = input.back.take().unwrap();

                (*front.as_ptr()).front = Some(in_back);
                (*in_back.as_ptr()).back = Some(front);
                self.list.front = Some(in_front);
            } else {
                // 我们为空，变成 input，留在 ghost 上
                std::mem::swap(self.list, &mut input);
            }

            self.list.len += input.len;
            // 非必须但礼貌起见
            input.len = 0;
            
            // input 在这里 drop
        }        
    }
}

最后修改 August 23, 2026: 更新 (499855b16)