本書github鏈接:
inside-rust-std-library
本文摘自以上鏈接的書籍而线，如果對本文中涉及的若干知識想進(jìn)一步了解铭污，請閱讀此書。
LinkedList<T>代碼分析
因?yàn)閿?shù)據(jù)結(jié)構(gòu)本身都是非常熟悉的內(nèi)容膀篮，重點(diǎn)是了解RUST與其他語言的不同嘹狞，本書將只分析LinkedList一個(gè)通常意義的數(shù)據(jù)結(jié)構(gòu)，理解清楚RUST的獨(dú)特點(diǎn)各拷，其他的數(shù)據(jù)結(jié)構(gòu)也就不是問題:
LinkedList<T>結(jié)構(gòu)定義如下：
//注意刁绒，此時(shí)只能支持固定長度的T類型
pub struct LinkedList<T> {
//等同于直接用裸指針，使得代碼最方便及簡化烤黍，但安全性需要依靠程序員了
//這個(gè)實(shí)際上與C語言相同知市，只是用Option增加了安全措施
head: Option<NonNull<Node<T>>>,
tail: Option<NonNull<Node<T>>>,
len: usize,
//以下說明本結(jié)構(gòu)有一個(gè)Box<Node<T>>的所有權(quán)，并會負(fù)責(zé)調(diào)用其的drop
//編譯器應(yīng)做好drop check
//marker體現(xiàn)了RUST的獨(dú)特點(diǎn)
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 {
//消費(fèi)了Box速蕊，堆內(nèi)存被釋放并將element拷貝到棧
self.element
}
}
LinkedList的創(chuàng)建及簡單的增減方法：
impl<T> LinkedList<T> {
//創(chuàng)建一個(gè)空的LinkedList
pub const fn new() -> Self {
LinkedList { head: None, tail: None, len: 0, marker: PhantomData }
}
在頭部增加一個(gè)成員及刪除一個(gè)成員：
//在首部增加一個(gè)節(jié)點(diǎn)
pub fn push_front(&mut self, elt: T) {
//用box從堆內(nèi)存申請一個(gè)節(jié)點(diǎn)嫂丙，push_front_node見后面函數(shù)
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的堆內(nèi)存leak出來使用。此塊內(nèi)存后繼如果還在鏈表规哲，需要由LinkedList負(fù)責(zé)drop.
//如果pop出鏈表跟啤，那會重新用這里leak出來的NonNull<Node<T>>重新生成Box
let node = Some(Box::leak(node).into());
match self.head {
None => self.tail = node,
// 注意下面，不能使直接用head.prev唉锌，因?yàn)闀?fù)制一個(gè)head隅肥，導(dǎo)致邏輯錯(cuò)誤
// 此處是RUST語法帶來的極易出錯(cuò)的陷阱。
Some(head) => (*head.as_ptr()).prev = node,
}
self.head = node;
self.len += 1;
}
}
//從鏈表頭部刪除一個(gè)節(jié)點(diǎn)
pub fn pop_front(&mut self) -> Option<T> {
//Option<T>::map袄简，此函數(shù)后腥放，節(jié)點(diǎn)的堆內(nèi)存已經(jīng)被釋放
//變量被拷貝到棧內(nèi)存
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，以便后繼可以釋放堆內(nèi)存
let node = Box::from_raw(node.as_ptr());
//更換head指針
self.head = node.next;
match self.head {
None => self.tail = None,
// push_front_node() 已經(jīng)分析過
Some(head) => (*head.as_ptr()).prev = None,
}
self.len -= 1;
node
})
}
在尾部增加一個(gè)成員及刪除一個(gè)成員
//從尾部增加一個(gè)節(jié)點(diǎn)
pub fn push_back(&mut self, elt: T) {
//用box從堆內(nèi)存申請一個(gè)節(jié)點(diǎn)
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的堆內(nèi)存leak出來使用绿语。此塊內(nèi)存后繼如果還在鏈表秃症，需要由LinkedList負(fù)責(zé)drop.
//如果pop出鏈表候址，那會重新用這里leak出來的NonNull<Node<T>>重新生成Box
let node = Some(Box::leak(node).into());
match self.tail {
None => self.head = node,
//前面代碼已經(jīng)有分析
Some(tail) => (*tail.as_ptr()).next = node,
}
self.tail = node;
self.len += 1;
}
}
//從尾端刪除節(jié)點(diǎn)
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 {
//重新創(chuàng)建Box以便刪除堆內(nèi)存
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) {
//為了在下面的循環(huán)中出現(xiàn)panic，這里可以繼續(xù)做釋放
//感覺此處做這個(gè)有些不自信
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);
//執(zhí)行到此處种柑，guard認(rèn)為已經(jīng)完成岗仑，不能再調(diào)用guard的drop
mem::forget(guard);
}
}
}
以上基本上說明了RUST的LinkedList的設(shè)計(jì)及代碼的一些關(guān)鍵點(diǎn)。
用Iterator來對List進(jìn)行訪問聚请，Iterator的相關(guān)結(jié)構(gòu)代碼如下：
into_iter()相關(guān)結(jié)構(gòu)及方法：
//變量本身的Iterator的類型
pub struct IntoIter<T> {
list: LinkedList<T>,
}
impl<T> IntoIterator for LinkedList<T> {
type Item = T;
type IntoIter = IntoIter<T>;
/// 對LinkedList<T> 做消費(fèi)
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()調(diào)用相關(guān)結(jié)構(gòu)及方法
//可變引用的Iterator的類型
pub struct IterMut<'a, T: 'a> {
head: Option<NonNull<Node<T>>>,
tail: Option<NonNull<Node<T>>>,
len: usize,
//這個(gè)marker也標(biāo)示了IterMut對LinkedList有一個(gè)可變引用
//創(chuàng)建IterMut后荠雕，與之相關(guān)的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 {
// 注意，下面代碼執(zhí)行后堆內(nèi)存已經(jīng)沒有所有權(quán)的載體,
// 此函數(shù)的調(diào)用代碼必須在后繼對返回的引用做Box重組
// 或者直接drop良漱，否則會造成內(nèi)存泄漏
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,
//對生命周期做標(biāo)識舞虱，也標(biāo)識了一個(gè)對LinkedList的不可變引用
marker: PhantomData<&'a Node<T>>,
}
impl<T> Clone for Iter<'_, T> {
fn clone(&self) -> Self {
//本書中第一次出現(xiàn)這個(gè)表述
Iter { ..*self }
}
}
//Iterator trait for Iter略
LinkedList其他的代碼略欢际。
