Struct linked_list::unsafe_list::List

pub struct List<A: Adapter + ?Sized> { /* private fields */ }

An intrusive circular doubly-linked list.

Membership of elements of the list must be tracked by the owner of the list.

While elements of the list must remain pinned while in the list, the list itself does not require pinning. In other words, users are allowed to move instances of List.

Invariants

The links of an entry are wrapped in UnsafeCell and they are acessible when the list itself is. For example, when a thread has a mutable reference to a list, it may also safely get mutable references to the links of the elements in the list.

The links of an entry are also wrapped in MaybeUninit and they are initialised when they are present in a list. Otherwise they are uninitialised.

Examples

struct Example {
    v: usize,
    links: Links<Example>,
}

// SAFETY: This adapter is the only one that uses `Example::links`.
unsafe impl Adapter for Example {
    type EntryType = Self;
    fn to_links(obj: &Self) -> &Links<Self> {
        &obj.links
    }
}

let a = Example {
    v: 0,
    links: Links::new(),
};
let b = Example {
    v: 1,
    links: Links::new(),
};

let mut list = List::<Example>::new();
assert!(list.is_empty());

// SAFETY: `a` was declared above, it's not in any lists yet, is never moved, and outlives the
// list.
unsafe { list.push_back(&a) };

// SAFETY: `b` was declared above, it's not in any lists yet, is never moved, and outlives the
// list.
unsafe { list.push_back(&b) };

assert!(core::ptr::eq(&a, list.front().unwrap().as_ptr()));
assert!(core::ptr::eq(&b, list.back().unwrap().as_ptr()));

for (i, e) in list.iter().enumerate() {
    assert_eq!(i, e.v);
}

for e in &list {
    println!("{}", e.v);
}

// SAFETY: `b` was added to the list above and wasn't removed yet.
unsafe { list.remove(&b) };

assert!(core::ptr::eq(&a, list.front().unwrap().as_ptr()));
assert!(core::ptr::eq(&a, list.back().unwrap().as_ptr()));

Implementations

impl<A: Adapter + ?Sized> List<A>

pub const fn new() -> Self

Constructs a new empty list.

pub const fn is_empty(&self) -> bool

Determines if the list is empty.

pub fn insert_only_entry(&mut self, obj: &A::EntryType)

Inserts the only entry to a list.

This must only be called when the list is empty.

pub unsafe fn push_back(&mut self, obj: &A::EntryType)

Adds the given object to the end of the list.

Safety

Callers must ensure that:

• The object is not currently in any lists.
• The object remains alive until it is removed from the list.
• The object is not moved until it is removed from the list.

pub unsafe fn push_front(&mut self, obj: &A::EntryType)

Adds the given object to the beginning of the list.

Safety

Callers must ensure that:

• The object is not currently in any lists.
• The object remains alive until it is removed from the list.
• The object is not moved until it is removed from the list.

pub unsafe fn remove(&mut self, entry: &A::EntryType)

Removes the given object from the list.

Safety

The object must be in the list. In other words, the object must have previously been inserted into this list and not removed yet.

pub unsafe fn insert_after( &mut self, existing: NonNull<A::EntryType>, new: &A::EntryType )

Adds the given object after another object already in the list.

Safety

Callers must ensure that:

• The existing object is currently in the list.
• The new object is not currently in any lists.
• The new object remains alive until it is removed from the list.
• The new object is not moved until it is removed from the list.

pub unsafe fn insert_before( &mut self, existing: NonNull<A::EntryType>, new: &A::EntryType )

Adds the given object before another object already in the list.

Safety

Callers must ensure that:

• The existing object is currently in the list.
• The new object is not currently in any lists.
• The new object remains alive until it is removed from the list.
• The new object is not moved until it is removed from the list.

pub fn front(&self) -> Option<NonNull<A::EntryType>>

Returns the first element of the list, if one exists.

pub fn back(&self) -> Option<NonNull<A::EntryType>>

Returns the last element of the list, if one exists.

pub fn iter(&self) -> Iterator<'_, A>

Returns an iterator for the list starting at the first entry.

pub fn iter_back(&self) -> impl DoubleEndedIterator<Item = &A::EntryType>

Returns an iterator for the list starting at the last entry.

pub fn cursor_front(&self) -> Cursor<'_, A>

Returns a cursor starting on the first (front) element of the list.

pub fn cursor_back(&self) -> Cursor<'_, A>

Returns a cursor starting on the last (back) element of the list.

Trait Implementations

impl<'a, A: Adapter + ?Sized> IntoIterator for &'a List<A>

type Item = &'a <A as Adapter>::EntryType

The type of the elements being iterated over.

type IntoIter = Iterator<'a, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<A: Adapter + ?Sized> Send for List<A>

where A::EntryType: Send,

impl<A: Adapter + ?Sized> Sync for List<A>

where A::EntryType: Sync,