在 Rust 中，是否可能将一个结构体的内存与另一个结构体关联起来？

Question

我知道在Rust中，编译器不能保证按照声明顺序获取结构体数据，以节省内存（我也相信一些C代码优化器正在做同样的事情）。现在假设我有一个二叉树，并想将其转换为双向链表。在C语言中，我会声明两个结构体：

typedef struct tree{
    void* left_child;
    void* right_child;
    void* data;
}tree_t;

对于树形结构，需要：

typedef struct list{
    void* before;
    void* after;
    void* data;
}list_t;

对于链表而言，如果我现在想把树转换成一个列表，我可以直接在原地进行操作，将树的内存与列表结构相连，并改变指针：

tree_t mytree;
/*fill tree*/
list_t *list_p;
list_p = (list_t)&mytree;
/*change pointers accordingly*/

但是在Rust中如何做到这一点呢？没有使用unsafe代码，这是否可能？ 现在我有了我的树：

struct TreeNode<'a, T> {
    left_child: BinaryTreeLink<'a, T>,
    right_child: BinaryTreeLink<'a, T>,
    data : &'a T,
}

type BinaryTreeLink<'a, T> = Option<Box<TreeNode<'a, T>>>;

列表如下：

struct ListNode<'a, T> {
    before: ListLink<'a, T>,
    after: ListLink<'a, T>,
    data : &'a T,
}

type ListLink<'a, T> = Option<Box<ListNode<'a, T>>>;

但是我如何现在有效地将它们转换？

- Benji Z.

---

听起来像是 mem::transmute 的工作，但正如你所怀疑的那样，这是极其不安全的。 - jonny

我不太熟悉这个模式，你能详细解释一下你试图用它实现什么吗？std::mem::transmute可以完成你试图实现的功能，但它是不安全的，因此提供一下你试图做什么的解释可能会揭示出更好的实现方法。 - Optimistic Peach

我正在尝试将二叉树原地转换为链表，这意味着不消耗额外的内存来构建链表。 - Benji Z.

Answer 1

但是怎样在Rust中做到这一点呢？是否有可能不使用unsafe代码来实现？目前为止，我有我自己的树。

要直接做同样的事情，你需要使用unsafe代码。函数std::mem::transmute正好可以满足你的需求。问题在于，在Rust中，结构体的布局不是保证的，所以下面的做法通常会存在未定义行为：

use std::mem;
let list_link: Option<Box<ListNode<_>>> = unsafe { mem::transmute(tree_node) };

然而，你可以通过强制结构体的布局可预测性来使其安全，使用 C 表示：

#[repr(C)]
struct TreeNode<'a, T> {
    left_child: BinaryTreeLink<'a, T>,
    right_child: BinaryTreeLink<'a, T>,
    data : &'a T,
}

#[repr(C)]
struct ListNode<'a, T> {
    before: ListLink<'a, T>,
    after: ListLink<'a, T>,
    data : &'a T,
}

你还需要在内部类型的定义中应用#[repr(C)]，包括ListLink和BinaryTreeLink。

---

但是如果避免使用不安全的代码呢？如果你编写的转换函数消耗原始数据，那么优化器应该能够将其转换为空操作，因为它知道没有其他代码会引用该内存。

<'a, T> impl From<ListNode<'a, T>> for TreeNode<'a, T> {
     fn from(other: ListNode<'a, T>) -> ListNode<'a, T>> {
         ListNode {
             before: other.left_child,
             after: other.right_child,
             data: other.data,
         }
     }
}

你绝对需要对此进行基准测试，但是优化器拥有将其转变为无操作所需的所有信息，而且很可能会这样做。

- Peter Hall