Rosetta Code

Doubly-linked list/Element definition: Difference between revisions

Page Discussion

Doubly-linked list/Element definition (view source)

Revision as of 21:09, 3 January 2017

267 bytes added ,  7 years ago
→‎The behind-the-scenes implementation: Updated
(→‎{{header|zkl}}: rewrite to suit other tasks)
Line 795:
Doubly linked lists present a problem in Rust due to its ownership model. There cannot be two mutable references to the same object, so what are we to do? Below are the relevant lines (with added comments) from the <code>std</code> implementation ([https://doc.rust-lang.org/std/collections/struct.LinkedList.html Documentation] [https://github.com/rust-lang/rust/blob/master/src/libcollections/linked_list.rs Source]).
 
The standard library uses the (currently) unstable `Shared<T>` type which indicates that the ownership of its contained type has shared ownership. It is guaranteed not to be null, is variant over <code>T</code> (meaning that an <code>&Shared<&'static T></code> may be used where a <code>&Shared<&'a T></code> is expected, indicates to the compiler that it may own a <code>T</code) and may be dereferenced to a mutable pointer (<code>*mut T</code>). All of the above may be accomplished in standard stable Rust, except for the non-null guarantee which allows the compiler to make a few extra optimizations.
In order to circumvent the multiple mutable references, raw C-like pointers are used. Note that these cannot be dereferenced with guaranteed safety and thus dereferencing is relegated to <code>unsafe {}</code> blocks.
 
<lang rust>pub struct LinkedList<T> { // User-facing implementation
head: Option<Shared<Node<T>>>,
length: usize,
list_headtail: LinkOption<Shared<Node<T>>>,
list_taillen: Rawlink<Node<T>>usize,
marker: PhantomData<Box<Node<T>>>, // Indicates that we logically own a boxed (owned pointer) Node<T>>
}
 
type Link<T> = Option<Box<Node<T>>>; // Type definition
 
struct Rawlink<T> { // Pointer is wrapped in struct so that Option-like methods can be added to it later (wrappers around NULL checks)
p: *mut T, // Raw mutable pointer
}
 
struct Node<T> {
next: LinkOption<Shared<Node<T>>>,
prev: RawlinkOption<Shared<Node<T>>>,
valueelement: T,
}</lang>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/30919"