Можно ли связать память одной структуры с другой в Rust?

Я знаю, что в 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>>>;

Но как я могу теперь эффективно преобразовать их на месте?


rust linked-list type-punning binary-tree
person Benji Z.    schedule 03.03.2019    source источник
comment
Звучит как работа для mem::transmute, что, однако, вы подозревали, дико небезопасно.   -  person jonny    schedule 04.03.2019
comment
Я не совсем знаком с этим шаблоном, не могли бы вы уточнить, чего вы пытаетесь достичь с помощью этого? std::mem::transmute будет делать то, что вы пытаетесь достичь, но это небезопасно, поэтому, возможно, объяснение того, что вы пытаетесь сделать, потенциально покажет лучший способ достижения этого.   -  person Optimistic Peach    schedule 04.03.2019
comment
Я пытаюсь преобразовать двоичное дерево в связанный список на месте, что означает без использования дополнительной памяти для создания связанного списка.   -  person Benji Z.    schedule 06.03.2019

Ответы (1)


arrow_upward
7
arrow_downward

Но как я могу сделать такое в Rust? Возможно ли это вообще без использования небезопасного кода? До сих пор у меня есть свое дерево

Чтобы сделать то же самое напрямую, вам потребуется использовать небезопасный код. Функция std::mem::transmute делает именно то, что вы хотите. Проблема в том, что макет структуры в Rust не гарантируется, поэтому следующее обычно будет Undefined Behavior:

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

Вы обязательно должны протестировать это, чтобы убедиться, но у оптимизатора есть вся информация, которая ему нужна, чтобы сделать это бездействующим, и очень вероятно, что он это сделает.

person Peter Hall    schedule 04.03.2019