Другими словами, данные, содержащиеся в узлах списка, обрабатываются как один ресурс, который может быть заимствован совместно / изменчиво, а ссылки между узлами являются другим ресурсом, который может быть заимствован совместно / изменчиво.
Идея иметь дело с таким пространственным разделением состоит в том, чтобы ввести разные «ключи» для каждого раздела; это легко, так как они статичны. Это было названо шаблоном PassKey.
При отсутствии брендов все равно потребуется проверка во время выполнения: проверка того, что ключ-элемент привязан к этому конкретному экземпляру списка, является обязательной для обеспечения безопасности. Это, однако, сравнение только для чтения, которое всегда будет 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 - самое очевидное представление двусвязного списка, поэтому мы все делаем правильно. list в Handle<T> существует с той же самой целью, что и в 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));
}
}