問題

上一章使用 Rust 語言最后實現(xiàn)的樹結(jié)構(gòu)存在著空間浪費，主要體現(xiàn)在使用 Vec<T> 容器存儲一個結(jié)點的子結(jié)點，以容器中含有 0 個元素表征一個結(jié)點沒有子結(jié)點。含有 0 個元素的容器，它本身也要占用微量但可觀的內(nèi)存空間。

類似問題也存在于上一章的 C 程序——為了對 Rust 程序進(jìn)行模擬，使用了 GLib 庫的 GPtrArray 容器，然而 C 語言為指針提供了值 NULL，可代替含有 0 個元素的 GPtrArray 容器，從而達(dá)到節(jié)約空間的目的。對于 Rust 語言，在目前我熟悉的知識范圍內(nèi)，只能使用 Option<T> 對 Vec<T> 進(jìn)行封裝，以 None 表達(dá)一個結(jié)點沒有子結(jié)點，此舉也能夠節(jié)省空間，但是在構(gòu)建樹結(jié)構(gòu)的過程中，需要頻繁使用 match 語句解除 Option<T> 封裝。不過，我知道在引用、智能指針等重重封裝之下，Rust 語言依然別有洞天——原始指針，本章嘗試探索和施展它的力量。

unsafe

Rust 語言的原始指針分為兩種類型，一種是 *const T，另一種是 *mut T，T 為變量類型。*const T 相當(dāng)于 C 語言里的常量指針——指針指向一個常量，即指針?biāo)笇ο螅〝?shù)據(jù)）不可修改。*mut T 相當(dāng)于 C 語言里的普通指針。

以下代碼創(chuàng)建了一個指向 i64 類型的變量的常量指針：

fn main() {
    let a: i64 = 42;
    let p = &a as *const i64;
    unsafe {
        println!("{}", *p);
    }
}

上述代碼，使用 Rust 語言的類型轉(zhuǎn)換語法 as ... 將 a 的引用轉(zhuǎn)換為常量指針類型，使得指針 p 指向變量 a。與引用相似，稱某個指針指向了某個變量，其意為該指針的值是變量所綁定的值的地址。此外，上述代碼出現(xiàn)了 unsafe 塊。在 Rust 語言中，創(chuàng)建原始指針是安全的，但是對指針進(jìn)行解引用——訪問指針?biāo)笇ο?，是不安全的，必須將相?yīng)代碼包含在 unsafe 塊內(nèi)。與上述代碼等價的 C 代碼為

#include <stdint.h>
#include <stdio.h>

int main(void) {
        int64_t a = 42;
        const int64_t *p = &a;
        printf("%ld\n", *p);
        return 0;
}

在上述代碼中，無論是 Rust 還是 C，以解引用的方式修改 p 所指對象，例如

*p = 3;

會導(dǎo)致編譯器報錯。

以下代碼演示了 *mut T 指針的基本用法：

fn main() {
    let mut a: i64 = 42;
    let p = &mut a as *mut i64;
    unsafe {
        *p = 3;
    }
    println!("{}", a);
}

輸出為 3。

與上述代碼等價的 C 代碼如下：

#include <stdint.h>
#include <stdio.h>

int main(void) {
        int64_t a = 42;
        int64_t *p = &a;
        *p = 3;
        printf("%ld\n", a);
        return 0;
}

擁抱原始指針

基于原始指針，TreeNode 可以定義為

#[derive(Debug)]
struct TreeNode {
    data: *const str,
    children: *mut Vec<*mut TreeNode>
}

與上一章的 TreeNode 相比，上述結(jié)構(gòu)體定義不再需要壽命標(biāo)注，因為 data 是一個原始指針，不再是引用。引用的安全性由 Rust 編譯器負(fù)責(zé)，故而限制非常多，而原始指針的安全性由編程者負(fù)責(zé)，近乎零限制。

以下代碼可構(gòu)造樹結(jié)點的實例：

let mut root = TreeNode {data: "Root node", children: std::ptr::null_mut()};
println!("{:?}", root);

輸出為

TreeNode { data: 0x556836ca1000, children: 0x0 }

由于 data 和 children 皆為原始指針。Rust 標(biāo)準(zhǔn)庫為原始指針類型實現(xiàn)的 Debug 特性輸出的是指針的值，即指針?biāo)缸兞康膬?nèi)存地址。再次強調(diào)，變量的內(nèi)存地址，其含意是變量所綁定的值的內(nèi)存地址。另外，需要注意，上述代碼使用了 Rust 標(biāo)準(zhǔn)庫函數(shù) std::ptr::null_mut 為指針構(gòu)造空值。對于常量指針，可使用 std::ptr::null 構(gòu)造空值。

由于 root.data 的類型現(xiàn)在是 *const str，即該指針指向類型為 str 的值。該指針類型能否像 &str 那樣可通過 println! 輸出嗎？動手一試：

unsafe {
    println!("{}", root.data);
}

編譯器報錯，稱 *const str 未實現(xiàn) std::fmt::Display 特性。

下面試驗一下指針解引用的方式：

unsafe {
    println!("{}", *root.data);
}

編譯器依然報錯，稱 str 的長度在編譯期未知。這個報錯信息，意味著 *root.data 的類型為 str，那么再其之前再加上 & 是否構(gòu)成 &str 類型呢？

unsafe {
    println!("{}", &*root.data);
}

問題得以解決，輸出為

Root node

現(xiàn)在的 root.children 是空指針。要為 root 結(jié)點構(gòu)造子結(jié)點，需要令 root.children 指向一個 Vec<*mut TreeNode> 實例：

let mut root_children = vec![];
root.children = &mut root_children as *mut Vec<*mut TreeNode>;

然后按照以下代碼所述方式為 root 構(gòu)造子結(jié)點：

let mut first = TreeNode {data: "First child node", 
                          children: std::ptr::null_mut()};
let child_1 = &mut first as *mut TreeNode;
unsafe {
    (*root.children).push(child_1);
}

以下代碼可打印 root 的子結(jié)點信息：

unsafe {
    println!("{:?}", *((*root.children)[0]));
}

輸出為

TreeNode { data: 0x55e47fa200c2, children: 0x0 }

使用原始指針之后，樹結(jié)點的部分信息以內(nèi)存地址形式呈現(xiàn)，若想查看該地址存儲的數(shù)據(jù)，如上述代碼所示，需要對數(shù)據(jù)結(jié)構(gòu)中的指針解引用。若是遇到多重指針，需要逐級解引用。

鏈表

對于樹結(jié)點而言，使用 Vec<T> 容器存儲其子結(jié)點并非必須。本質(zhì)上，將樹的結(jié)構(gòu)表示為鏈?zhǔn)浇Y(jié)構(gòu)更為自然。在已初步掌握原始指針的情況下，應(yīng)當(dāng)運用原始指針對樹結(jié)點的定義給出更為本質(zhì)的表達(dá)，例如

#[derive(Debug)]
struct TreeNode {
    data: *const str,
    upper: *mut TreeNode, // 上層結(jié)點
    prev : *mut TreeNode, // 同層前一個結(jié)點
    next : *mut TreeNode, // 同層后一個結(jié)點
    lower: *mut TreeNode  // 下層結(jié)點
}

基于上述樹結(jié)點定義構(gòu)建的樹結(jié)構(gòu)，其根結(jié)點的 upper 域為空值，葉結(jié)點的 lower 域為空值。樹中任意一個結(jié)點，與之有共同父結(jié)點的同層結(jié)點可構(gòu)成一個雙向鏈表。

以下代碼構(gòu)造了樹的三個結(jié)點：

let mut root = TreeNode {data: "Root",
                         upper: std::ptr::null_mut(),
                         prev:  std::ptr::null_mut(),
                         next:  std::ptr::null_mut(),
                         lower: std::ptr::null_mut()};
let mut a = TreeNode {data: "A",
                      upper: std::ptr::null_mut(),
                      prev:  std::ptr::null_mut(),
                      next:  std::ptr::null_mut(),
                      lower: std::ptr::null_mut()};
let mut b = TreeNode {data: "B",
                      upper: std::ptr::null_mut(),
                      prev:  std::ptr::null_mut(),
                      next:  std::ptr::null_mut(),
                      lower: std::ptr::null_mut()};

現(xiàn)在，讓 a 和 b 作為 root 的子結(jié)點：

a.upper = &mut root as *mut TreeNode;
a.next = &mut b as *mut TreeNode;
b.upper = &mut root as *mut TreeNode;
b.prev = &mut a as *mut TreeNode;
root.lower = &mut a as *mut TreeNode;

可以通過打印各個結(jié)點的結(jié)構(gòu)及其地址確定上述代碼構(gòu)造的樹結(jié)構(gòu)是否符合預(yù)期：

// 打印結(jié)點結(jié)構(gòu)信息
println!("root: {:?}\na: {:?}\nb: {:?}", root, a, b);
// 打印結(jié)點的內(nèi)存地址
println!("root: {:p}, a: {:p}, b: {:p}", &root, &a, &b);

結(jié)構(gòu)體的方法

上一節(jié)構(gòu)建樹結(jié)點的代碼有較多重復(fù)。由于 TreeNode 是結(jié)構(gòu)體類型，可為其定義一個關(guān)聯(lián)函數(shù)，例如 new，用于簡化結(jié)構(gòu)體實例的構(gòu)建過程。像這樣的關(guān)聯(lián)函數(shù)，在 Rust 語言里稱為結(jié)構(gòu)體的方法。

以下代碼為 TreeNode 類型定義了 new 方法：

impl TreeNode {
    fn new(a: &str) -> TreeNode {
        return TreeNode {data: a,
                         upper: std::ptr::null_mut(),
                         prev:  std::ptr::null_mut(),
                         next:  std::ptr::null_mut(),
                         lower: std::ptr::null_mut()};
    }
}

以下代碼基于 TreeNode::new 方法構(gòu)造三個樹結(jié)點：

let mut root = TreeNode::new("Root");
let mut a = TreeNode::new("A");
let mut b = TreeNode::new("B");

定義結(jié)構(gòu)體的方法與定義普通函數(shù)大致相同，形式皆為

fn 函數(shù)名(參數(shù)表) -> 返回類型 {
    函數(shù)體;
}

二者的主要區(qū)別是，前者需要在結(jié)構(gòu)體類型的 impl 塊內(nèi)定義。

結(jié)構(gòu)體方法有兩種，一種是靜態(tài)方法，另一種是實例方法。上述代碼定義的 new 方法即為靜態(tài)方法，需要通過結(jié)構(gòu)體類型調(diào)用該類方法。至于實例方法的定義，見以下示例

impl TreeNode {
    fn display(&self) {
        println!("{:p}: {:?}", self, self);
    }
}

TreeNode 的 display 方法可通過TreeNode 的實例調(diào)用，例如

let mut root = TreeNode::new("Root");
root.display();

結(jié)構(gòu)體類型的實例方法定義中，&self 實際上是 Rust 語法糖，它是 self: &Self 的簡寫，而 Self 是結(jié)構(gòu)體類型的代稱。對于 TreeNode 類型而言，self: &Self 即 self: &TreeNode。

堆空間指針

上述示例構(gòu)造的原始指針?biāo)缸兞康闹到晕挥跅？臻g。事實上，原始指針也能以智能指針為中介指向堆空間中的值。例如

let root = Box::into_raw(Box::new(TreeNode::new("Root")));
unsafe {
    (*root).display();
}

上述代碼中的 root 的類型為 *mut TreeNode，因為 Box::into_raw 方法可將一個 Box<T> 指針轉(zhuǎn)化為原始指針類型。

需要注意的是，在上述代碼中，堆空間中的值所占用的內(nèi)存區(qū)域是由智能指針分配，但是 Box::into_raw 會將 Box<T> 指針消耗掉，并將其分配的內(nèi)存區(qū)域所有權(quán)移交于原始指針。這塊區(qū)域的釋放，需由原始指針的使用者負(fù)責(zé)，因此上述代碼實際上存在著內(nèi)存泄漏，因為 root 指向的內(nèi)存區(qū)域并未被釋放。

釋放 root 所指內(nèi)存區(qū)域的最簡單的方法是，將其所指內(nèi)存區(qū)域歸還于智能指針，由該智能指針負(fù)責(zé)釋放。例如

let root = Box::into_raw(Box::new(TreeNode::new("Root")));
unsafe {
     let x = Box::from_raw(root);
}

也可以手動釋放原始指針?biāo)竷?nèi)存區(qū)域，例如

unsafe {
    std::ptr::drop_in_place(root);
    std::alloc::dealloc(root as *mut u8, std::alloc::Layout::new::<TreeNode>());
}

然而現(xiàn)在我并不甚清楚上述代碼的內(nèi)在機(jī)理，簡記于此，待日后細(xì)究。

C 版本

Rust 的原始指針本質(zhì)上與 C 指針是等價的。下面是基于 C 指針定義的樹結(jié)點：

typedef struct TreeNode {
        char *data;
        struct TreeNode *upper;
        struct TreeNode *prev;
        struct TreeNode *next;
        struct TreeNode *lower;
} TreeNode;

以下代碼定義了樹結(jié)點的構(gòu)造函數(shù)：

TreeNode *tree_node_new(char *a) {
        TreeNode *x = malloc(sizeof(TreeNode));
        x->data = a;
        x->upper = NULL;
        x->prev = NULL;
        x->next = NULL;
        x->lower = NULL;
}

構(gòu)造三個樹結(jié)點并建立它們之間的聯(lián)系：

TreeNode *root = tree_node_new("Root");
TreeNode *a = tree_node_new("A");
TreeNode *b = tree_node_new("B");

root->lower = a;
a->upper = root;
a->next = b;
b->upper = root;
b->prev = a;

也可以模仿 Rust 的樹結(jié)構(gòu) Debug 特性輸出結(jié)果，為樹結(jié)點定義一個打印函數(shù)：

void tree_node_display(TreeNode *x) {
        printf("%p: ", (void *)x);
        printf("TreeNode { data: %p, upper: %p, prev: %p, next: %p, lower: %p }\n",
               (void *)x->data, (void *)x->upper, (void *)x->prev,
               (void *)x->next, (void *)x->lower);
}

小結(jié)

目前多數(shù) Rust 教程吝嗇于對原始指針及其用法給出全面且深入的介紹，甚至將原始指針歸于 Rust 語言高級進(jìn)階知識，我認(rèn)為這是非常不明智的做法。原始指針不僅應(yīng)當(dāng)盡早介紹，甚至應(yīng)當(dāng)鼓勵初學(xué)者多加使用。特別在構(gòu)造鏈表（包括棧、堆、隊列等結(jié)構(gòu)）、樹、圖等形式的數(shù)據(jù)結(jié)構(gòu)時，不應(yīng)該讓所謂的程序安全性凌駕于數(shù)據(jù)結(jié)構(gòu)的易用性（易于訪問和修改）之上。

對于 Rust 語言初學(xué)者而言，引用、智能指針和原始指針這三者的學(xué)習(xí)次序，我的建議是原始指針 -> 智能指針 -> 引用，而非多數(shù) Rust 教程建議的引用 -> 智能指針 -> 原始指針。至于這三種指針的用法，我也是推薦先使用原始指針，在遇到難以克服的安全性問題時，再考慮使用智能指針或引用對代碼進(jìn)行重構(gòu)，否則初學(xué)者何以知悉智能指針和引用出現(xiàn)和存在的原因呢？

以上就是Rust 原始指針功能探索的詳細(xì)內(nèi)容，更多關(guān)于Rust 原始指針的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論