本书github链接:
inside-rust-std-library
本文摘自以上链接的书籍，如果对本文中涉及的若干知识想进一步了解，请阅读此书。
LinkedList<T>代码分析
因为数据结构本身都是非常熟悉的内容，重点是了解RUST与其他语言的不同，本书将只分析LinkedList一个通常意义的数据结构，理解清楚RUST的独特点，其他的数据结构也就不是问题:
LinkedList<T>结构定义如下：
//注意，此时只能支持固定长度的T类型
pub struct LinkedList<T> {
//等同于直接用裸指针，使得代码最方便及简化，但安全性需要依靠程序员了
//这个实际上与C语言相同，只是用Option增加了安全措施
head: Option<NonNull<Node<T>>>,
tail: Option<NonNull<Node<T>>>,
len: usize,
//以下说明本结构有一个Box<Node<T>>的所有权，并会负责调用其的drop
//编译器应做好drop check
//marker体现了RUST的独特点
marker: PhantomData<Box<Node<T>>>,
}
struct Node<T> {
next: Option<NonNull<Node<T>>>,
prev: Option<NonNull<Node<T>>>,
element: T,
}
Node方法代码：
impl<T> Node<T> {
fn new(element: T) -> Self {
Node { next: None, prev: None, element }
}
fn into_element(self: Box<Self>) -> T {
//消费了Box，堆内存被释放并将element拷贝到栈
self.element
}
}
LinkedList的创建及简单的增减方法：
impl<T> LinkedList<T> {
//创建一个空的LinkedList
pub const fn new() -> Self {
LinkedList { head: None, tail: None, len: 0, marker: PhantomData }
}
在头部增加一个成员及删除一个成员：
//在首部增加一个节点
pub fn push_front(&mut self, elt: T) {
//用box从堆内存申请一个节点，push_front_node见后面函数
self.push_front_node(box Node::new(elt));
}
fn push_front_node(&mut self, mut node: Box<Node<T>>) {
// 整体全是不安全代码
unsafe {
node.next = self.head;
node.prev = None;
//需要将Box的堆内存leak出来使用。此块内存后继如果还在链表，需要由LinkedList负责drop.
//如果pop出链表，那会重新用这里leak出来的NonNull<Node<T>>重新生成Box
let node = Some(Box::leak(node).into());
match self.head {
None => self.tail = node,
// 注意下面，不能使直接用head.prev，因为会复制一个head，导致逻辑错误
// 此处是RUST语法带来的极易出错的陷阱。
Some(head) => (*head.as_ptr()).prev = node,
}
self.head = node;
self.len += 1;
}
}
//从链表头部删除一个节点
pub fn pop_front(&mut self) -> Option<T> {
//Option<T>::map，此函数后，节点的堆内存已经被释放
//变量被拷贝到栈内存
self.pop_front_node().map(Node::into_element)
}
fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
//整体是unsafe
self.head.map(|node| unsafe {
//重新生成Box，以便后继可以释放堆内存
let node = Box::from_raw(node.as_ptr());
//更换head指针
self.head = node.next;
match self.head {
None => self.tail = None,
// push_front_node() 已经分析过
Some(head) => (*head.as_ptr()).prev = None,
}
self.len -= 1;
node
})
}
在尾部增加一个成员及删除一个成员
//从尾部增加一个节点
pub fn push_back(&mut self, elt: T) {
//用box从堆内存申请一个节点
self.push_back_node(box Node::new(elt));
}
fn push_back_node(&mut self, mut node: Box<Node<T>>) {
// 整体不安全
unsafe {
node.next = None;
node.prev = self.tail;
//需要将Box的堆内存leak出来使用。此块内存后继如果还在链表，需要由LinkedList负责drop.
//如果pop出链表，那会重新用这里leak出来的NonNull<Node<T>>重新生成Box
let node = Some(Box::leak(node).into());
match self.tail {
None => self.head = node,
//前面代码已经有分析
Some(tail) => (*tail.as_ptr()).next = node,
}
self.tail = node;
self.len += 1;
}
}
//从尾端删除节点
pub fn pop_back(&mut self) -> Option<T> {
self.pop_back_node().map(Node::into_element)
}
fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
self.tail.map(|node| unsafe {
//重新创建Box以便删除堆内存
let node = Box::from_raw(node.as_ptr());
self.tail = node.prev;
match self.tail {
None => self.head = None,
Some(tail) => (*tail.as_ptr()).next = None,
}
self.len -= 1;
node
})
}
...
}
//Drop
unsafe impl<#[may_dangle] T> Drop for LinkedList<T> {
fn drop(&mut self) {
struct DropGuard<'a, T>(&'a mut LinkedList<T>);
impl<'a, T> Drop for DropGuard<'a, T> {
fn drop(&mut self) {
//为了在下面的循环中出现panic，这里可以继续做释放
//感觉此处做这个有些不自信
while self.0.pop_front_node().is_some() {}
}
}
while let Some(node) = self.pop_front_node() {
let guard = DropGuard(self);
//显式的drop 获取的Box<Node<T>>
drop(node);
//执行到此处，guard认为已经完成，不能再调用guard的drop
mem::forget(guard);
}
}
}
以上基本上说明了RUST的LinkedList的设计及代码的一些关键点。
用Iterator来对List进行访问，Iterator的相关结构代码如下：
into_iter()相关结构及方法：
//变量本身的Iterator的类型
pub struct IntoIter<T> {
list: LinkedList<T>,
}
impl<T> IntoIterator for LinkedList<T> {
type Item = T;
type IntoIter = IntoIter<T>;
/// 对LinkedList<T> 做消费
fn into_iter(self) -> IntoIter<T> {
IntoIter { list: self }
}
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
//从头部获取变量
self.list.pop_front()
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.list.len, Some(self.list.len))
}
}
iter_mut()调用相关结构及方法
//可变引用的Iterator的类型
pub struct IterMut<'a, T: 'a> {
head: Option<NonNull<Node<T>>>,
tail: Option<NonNull<Node<T>>>,
len: usize,
//这个marker也标示了IterMut对LinkedList有一个可变引用
//创建IterMut后，与之相关的LinkerList不能在被其他安全的代码修改
marker: PhantomData<&'a mut Node<T>>,
}
impl <T> LinkedList<T> {
...
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
IterMut { head: self.head, tail: self.tail, len: self.len, marker: PhantomData }
}
...
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<&'a mut T> {
if self.len == 0 {
None
} else {
self.head.map(|node| unsafe {
// 注意，下面代码执行后堆内存已经没有所有权的载体,
// 此函数的调用代码必须在后继对返回的引用做Box重组
// 或者直接drop，否则会造成内存泄漏
let node = &mut *node.as_ptr();
self.len -= 1;
self.head = node.next;
&mut node.element
})
}
}
...
}
//不可变引用的Iterator的类型
pub struct Iter<'a, T: 'a> {
head: Option<NonNull<Node<T>>>,
tail: Option<NonNull<Node<T>>>,
len: usize,
//对生命周期做标识，也标识了一个对LinkedList的不可变引用
marker: PhantomData<&'a Node<T>>,
}
impl<T> Clone for Iter<'_, T> {
fn clone(&self) -> Self {
//本书中第一次出现这个表述
Iter { ..*self }
}
}
//Iterator trait for Iter略
LinkedList其他的代码略。
