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

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

0 голосов
/ 04 марта 2019

Я знаю, что в Rust компилятор не гарантирует, что вы получите ваши данные структуры в том порядке, в котором вы их объявляете, чтобы сэкономить память (я также считаю, что некоторые оптимизаторы кода C делают то же самое).Предположим, теперь у меня есть двоичное дерево и я хочу преобразовать его в двойной связанный список.В CI объявляются две структуры: 

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

Но как мне теперь эффективно конвертировать их на месте?

1 Ответ

0 голосов
/ 04 марта 2019

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

Чтобы сделать то же самое напрямую , вам нужно будет использовать небезопасный код.Функция 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,
         }
     }
}

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

...