2

例如，假设我有一个不允许删除节点的链表。

是否可以返回对已插入值的共享引用，同时仍允许更改节点的相对顺序或插入新节点？

只要一次只使用一个节点来改变列表，即使通过其中一个节点的突变也应该是安全的“在纸上”。是否可以在 rust 的所有权系统中表示这一点？

我特别有兴趣在没有运行时开销的情况下这样做（可能在实现中使用 unsafe，但不在接口中使用）。

编辑：根据要求，这是一个示例，概述了我的想法。

let list = MyLinkedList::<i32>::new()
let handle1 = list.insert(1); // Returns a handle to the inserted element.
let handle2 = list.insert(2);

let value1 : &i32 = handle1.get();
let value2 : &i32 = handle2.prev().get(); // Ok to have two immutable references to the same element.
list.insert(3); // Also ok to insert and swap nodes, while the references are held.
list.swap(handle1,handl2);
foo(value1,value2);

let exclusive_value: &mut i32 = handle1.get_mut(); // While this reference is held, no other handles can be used, but insertion and permutation are ok 
handle5 = list.insert(4);
list.swap(handle1, handle2);

换句话说，列表节点内包含的数据被视为可以共享/可变借用的一种资源，节点之间的链接是可以共享/可变借用的另一种资源。

4

1 回答 1

2

换句话说，列表节点内包含的数据被视为可以共享/可变借用的一种资源，节点之间的链接是可以共享/可变借用的另一种资源。

处理这种空间分区的想法是为每个分区引入不同的“键”；这很容易，因为它们是静态的。这被称为 PassKey 模式。

在没有brands的情况下，它仍然需要运行时检查：为了安全起见，验证elements-key 是否绑定到这个特定的列表实例是强制性的。但是，这是一个始终为 的只读比较true，因此性能与运行时检查一样好。

简而言之，这个想法：

let (handles, elements) = list.keys();
let h0 = handles.create(4);
handles.swap(h0, h1);
let e = elements.get(h0);

在您的用例中：

  • 始终可以更改链接，因此我们将为此使用内部可变性。
  • 对句柄内元素的借用检查将通过借用来执行elements。

完整的实现可以在这里找到。它大量使用unsafe，我不保证它是完全安全的，但希望它足以用于演示。

在这个实现中，我选择了哑句柄并实现了对键类型本身的操作。这限制了需要从主列表中借用的类型数量，并简化了借用。

那么核心思想：

struct LinkedList<T> {
    head: *mut Node<T>,
    tail: *mut Node<T>
}

struct Handles<'a, T> {
    list: ptr::NonNull<LinkedList<T>>,
    _marker: PhantomData<&'a mut LinkedList<T>>,
}

struct Elements<'a, T> {
    list: ptr::NonNull<LinkedList<T>>,
    _marker: PhantomData<&'a mut LinkedList<T>>,
}

LinkedList<T>将充当存储，但仅执行 3 个操作：

  • 建造，
  • 破坏，
  • 分发钥匙。

这两个键Handles和Elements都将可变地借用列表，保证一个（它们中的每一个）可以同时存在。如果它们的任何实例仍然存在于此列表中，则借用检查将阻止创建新的Handles或创建：Elements

  • list：授予对列表存储的访问权限；Elements只会将它用于检查（必要的）运行时不变量，并且永远不会取消引用它。
  • _marker: 是借用检查真正保证排他性的关键。

到目前为止听起来很酷吗？为了完成，最后两个结构：

struct Handle<'a, T> {
    node: ptr::NonNull<Node<T>>,
    list: ptr::NonNull<LinkedList<T>>,
    _marker: PhantomData<&'a LinkedList<T>>,
}

struct Node<T> {
    data: T,
    prev: *mut Node<T>,
    next: *mut Node<T>,
}

Node是双向链表有史以来最明显的表示，所以我们做对了。listin的Handle<T>目的与 in 完全相同Elements：验证Handle和Handles/Elements都在谈论list. 安全至关重要get_mut，否则有助于避免错误。

终生Handle<'a, T>与LinkedList. 我很想删除它，但是这将允许从列表中创建一个句柄，销毁该列表，然后在同一地址重新创建一个列表......handle.node现在会悬空！

而且，我们只需要在Handles和上实现我们需要的方法Elements。几个样本：

impl<'a, T> Handles<'a, T> {
    pub fn push_front(&self, data: T) -> Handle<'a, T> {
        let list = unsafe { &mut *self.list.as_ptr() };

        let node = Box::into_raw(Box::new(Node { data, prev: ptr::null_mut(), next: list.head }));
        unsafe { &mut *node }.set_neighbours();

        list.head = node;

        if list.tail.is_null() {
            list.tail = node;
        }

        Handle {
            node: unsafe { ptr::NonNull::new_unchecked(node) },
            list: self.list, _marker: PhantomData,
        }
    }

    pub fn prev(&self, handle: Handle<'a, T>) -> Option<Handle<'a, T>> {
        unsafe { handle.node.as_ref() }.prev().map(|node| Handle {
            node,
            list: self.list,
            _marker: PhantomData
        })
    }
}

和：

impl<'a, T> Elements<'a, T> {
    pub fn get<'b>(&'b self, handle: Handle<'a, T>) -> &'b T {
        assert_eq!(self.list, handle.list);

        let node = unsafe { &*handle.node.as_ptr() };
        &node.data
    }

    pub fn get_mut<'b>(&'b mut self, handle: Handle<'a, T>) -> &'b mut T {
        assert_eq!(self.list, handle.list);

        let node = unsafe { &mut *handle.node.as_ptr() };
        &mut node.data
    }
}

这应该是安全的，因为：

  • Handles，在创建新句柄后，只能访问其链接。
  • Elements只返回对 的引用data，并且在访问链接时不能修改链接。

使用示例：

fn main() {
    let mut linked_list = LinkedList::default();
    {
        let (handles, mut elements) = linked_list.access();
        let h0 = handles.push_front("Hello".to_string());

        assert!(handles.prev(h0).is_none());
        assert!(handles.next(h0).is_none());

        println!("{}", elements.get(h0));

        let h1 = {
            let first = elements.get_mut(h0);
            first.replace_range(.., "Hallo");

            let h1 = handles.push_front("World".to_string());
            assert!(handles.prev(h0).is_some());

            first.replace_range(.., "Goodbye");

            h1
        };

        println!("{} {}", elements.get(h0), elements.get(h1));

        handles.swap(h0, h1);

        println!("{} {}", elements.get(h0), elements.get(h1));
    }
    {
        let (handles, elements) = linked_list.access();

        let h0 = handles.front().unwrap();
        let h1 = handles.back().unwrap();
        let h2 = handles.push_back("And thanks for the fish!".to_string());

        println!("{} {}! {}", elements.get(h0), elements.get(h1), elements.get(h2));
    }
}
于 2019-01-10T20:04:44.667 回答