回上级页面

原始指针

2023 年 07 月 01 日

问题

上一章使用 Rust 语言最后实现的树结构存在着空间浪费，主要体现在使用 Vec<T> 容器存储一个结点的子结点，以容器中含有 0 个元素表征一个结点没有子结点。含有 0 个元素的容器，它本身也要占用微量但可观的内存空间。

类似问题也存在于上一章的 C 程序——为了对 Rust 程序进行模拟，使用了 GLib 库的 GPtrArray 容器，然而 C 语言为指针提供了值 NULL，可代替含有 0 个元素的 GPtrArray 容器，从而达到节约空间的目的。对于 Rust 语言，在目前我熟悉的知识范围内，只能使用 Option<T> 对 Vec<T> 进行封装，以 None 表达一个结点没有子结点，此举也能够节省空间，但是在构建树结构的过程中，需要频繁使用 match 语句解除 Option<T> 封装。不过，我知道在引用、智能指针等重重封装之下，Rust 语言依然别有洞天——原始指针，本章尝试探索和施展它的力量。

unsafe

Rust 语言的原始指针分为两种类型，一种是 *const T，另一种是 *mut T，T 为变量类型。*const T 相当于 C 语言里的常量指针——指针指向一个常量，即指针所指对象（数据）不可修改。*mut T 相当于 C 语言里的普通指针。

以下代码创建了一个指向 i64 类型的变量的常量指针：

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

上述代码，使用 Rust 语言的类型转换语法 as ... 将 a 的引用转换为常量指针类型，使得指针 p 指向变量 a。与引用相似，称某个指针指向了某个变量，其意为该指针的值是变量所绑定的值的地址。此外，上述代码出现了 unsafe 块。在 Rust 语言中，创建原始指针是安全的，但是对指针进行解引用——访问指针所指对象，是不安全的，必须将相应代码包含在 unsafe 块内。与上述代码等价的 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;

会导致编译器报错。

以下代码演示了 *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 相比，上述结构体定义不再需要寿命标注，因为 data 是一个原始指针，不再是引用。引用的安全性由 Rust 编译器负责，故而限制非常多，而原始指针的安全性由编程者负责，近乎零限制。

以下代码可构造树结点的实例：

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

输出为

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

由于 data 和 children 皆为原始指针。Rust 标准库为原始指针类型实现的 Debug 特性输出的是指针的值，即指针所指变量的内存地址。再次强调，变量的内存地址，其含意是变量所绑定的值的内存地址。另外，需要注意，上述代码使用了 Rust 标准库函数 std::ptr::null_mut 为指针构造空值。对于常量指针，可使用 std::ptr::null 构造空值。

由于 root.data 的类型现在是 *const str，即该指针指向类型为 str 的值。该指针类型能否像 &str 那样可通过 println! 输出吗？动手一试：

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

编译器报错，称 *const str 未实现 std::fmt::Display 特性。

下面试验一下指针解引用的方式：

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

编译器依然报错，称 str 的长度在编译期未知。这个报错信息，意味着 *root.data 的类型为 str，那么再其之前再加上 & 是否构成 &str 类型呢？

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

问题得以解决，输出为

Root node

现在的 root.children 是空指针。要为 root 结点构造子结点，需要令 root.children 指向一个 Vec<*mut TreeNode> 实例：

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

然后按照以下代码所述方式为 root 构造子结点：

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 的子结点信息：

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

输出为

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

使用原始指针之后，树结点的部分信息以内存地址形式呈现，若想查看该地址存储的数据，如上述代码所示，需要对数据结构中的指针解引用。若是遇到多重指针，需要逐级解引用。

链表

对于树结点而言，使用 Vec<T> 容器存储其子结点并非必须。本质上，将树的结构表示为链式结构更为自然。在已初步掌握原始指针的情况下，应当运用原始指针对树结点的定义给出更为本质的表达，例如

#[derive(Debug)]
struct TreeNode {
    data: *const str,
    upper: *mut TreeNode, // 上层结点
    prev : *mut TreeNode, // 同层前一个结点
    next : *mut TreeNode, // 同层后一个结点
    lower: *mut TreeNode  // 下层结点
}

基于上述树结点定义构建的树结构，其根结点的 upper 域为空值，叶结点的 lower 域为空值。树中任意一个结点，与之有共同父结点的同层结点可构成一个双向链表。

以下代码构造了树的三个结点：

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()};

现在，让 a 和 b 作为 root 的子结点：

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;

可以通过打印各个结点的结构及其地址确定上述代码构造的树结构是否符合预期：

// 打印结点结构信息
println!("root: {:?}\na: {:?}\nb: {:?}", root, a, b);
// 打印结点的内存地址
println!("root: {:p}, a: {:p}, b: {:p}", &root, &a, &b);

结构体的方法

上一节构建树结点的代码有较多重复。由于 TreeNode 是结构体类型，可为其定义一个关联函数，例如 new，用于简化结构体实例的构建过程。像这样的关联函数，在 Rust 语言里称为结构体的方法。

以下代码为 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 方法构造三个树结点：

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

定义结构体的方法与定义普通函数大致相同，形式皆为

fn 函数名(参数表) -> 返回类型 {
    函数体;
}

二者的主要区别是，前者需要在结构体类型的 impl 块内定义。

结构体方法有两种，一种是静态方法，另一种是实例方法。上述代码定义的 new 方法即为静态方法，需要通过结构体类型调用该类方法。至于实例方法的定义，见以下示例

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

TreeNode 的 display 方法可通过TreeNode 的实例调用，例如

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

结构体类型的实例方法定义中，&self 实际上是 Rust 语法糖，它是 self: &Self 的简写，而 Self 是结构体类型的代称。对于 TreeNode 类型而言，self: &Self 即 self: &TreeNode。

堆空间指针

上述示例构造的原始指针所指变量的值皆位于栈空间。事实上，原始指针也能以智能指针为中介指向堆空间中的值。例如

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

上述代码中的 root 的类型为 *mut TreeNode，因为 Box::into_raw 方法可将一个 Box<T> 指针转化为原始指针类型。

需要注意的是，在上述代码中，堆空间中的值所占用的内存区域是由智能指针分配，但是 Box::into_raw 会将 Box<T> 指针消耗掉，并将其分配的内存区域所有权移交于原始指针。这块区域的释放，需由原始指针的使用者负责，因此上述代码实际上存在着内存泄漏，因为 root 指向的内存区域并未被释放。

释放 root 所指内存区域的最简单的方法是，将其所指内存区域归还于智能指针，由该智能指针负责释放。例如

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

也可以手动释放原始指针所指内存区域，例如

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

然而现在我并不甚清楚上述代码的内在机理，简记于此，待日后细究。

C 版本

Rust 的原始指针本质上与 C 指针是等价的。下面是基于 C 指针定义的树结点：

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

以下代码定义了树结点的构造函数：

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;
}

构造三个树结点并建立它们之间的联系：

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 的树结构 Debug 特性输出结果，为树结点定义一个打印函数：

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);
}

小结

目前多数 Rust 教程吝啬于对原始指针及其用法给出全面且深入的介绍，甚至将原始指针归于 Rust 语言高级进阶知识，我认为这是非常不明智的做法。原始指针不仅应当尽早介绍，甚至应当鼓励初学者多加使用。特别在构造链表（包括栈、堆、队列等结构）、树、图等形式的数据结构时，不应该让所谓的程序安全性凌驾于数据结构的易用性（易于访问和修改）之上。

对于 Rust 语言初学者而言，引用、智能指针和原始指针这三者的学习次序，我的建议是原始指针 -> 智能指针 -> 引用，而非多数 Rust 教程建议的引用 -> 智能指针 -> 原始指针。至于这三种指针的用法，我也是推荐先使用原始指针，在遇到难以克服的安全性问题时，再考虑使用智能指针或引用对代码进行重构，否则初学者何以知悉智能指针和引用出现和存在的原因呢？

我的联系方式：lyr.m2@live.cn 或在讨论区提问。