Struct List

pub struct List<T: Linked<Links<T>> + ?Sized> { /* private fields */ }

An intrusive doubly-linked list.

This data structure may be used as a first-in, first-out queue by using the List::push_front and List::pop_back methods. It also supports random-access removals using the List::remove method. This makes the List type suitable for use in cases where elements must be able to drop themselves while linked into a list.

This data structure can also be used as a stack or doubly-linked list by using the List::pop_front and List::push_back methods.

The List type is not a lock-free data structure, and can only be modified through &mut references.

In order to be part of a List, a type T must implement Linked for list::Links<T>.

Examples

Implementing the Linked trait for an entry type:

use cordyceps::{
    Linked,
    list::{self, List},
};

// This example uses the Rust standard library for convenience, but
// the doubly-linked list itself does not require std.
use std::{pin::Pin, ptr::{self, NonNull}, thread, sync::Arc};

/// A simple queue entry that stores an `i32`.
#[derive(Debug, Default)]
struct Entry {
   links: list::Links<Entry>,
   val: i32,
}

// Implement the `Linked` trait for our entry type so that it can be used
// as a queue entry.
unsafe impl Linked<list::Links<Entry>> for Entry {
    // In this example, our entries will be "owned" by a `Box`, but any
    // heap-allocated type that owns an element may be used.
    //
    // An element *must not* move while part of an intrusive data
    // structure. In many cases, `Pin` may be used to enforce this.
    type Handle = Pin<Box<Self>>;

    /// Convert an owned `Handle` into a raw pointer
    fn into_ptr(handle: Pin<Box<Entry>>) -> NonNull<Entry> {
       unsafe { NonNull::from(Box::leak(Pin::into_inner_unchecked(handle))) }
    }

    /// Convert a raw pointer back into an owned `Handle`.
    unsafe fn from_ptr(ptr: NonNull<Entry>) -> Pin<Box<Entry>> {
        // Safety: if this function is only called by the linked list
        // implementation (and it is not intended for external use), we can
        // expect that the `NonNull` was constructed from a reference which
        // was pinned.
        //
        // If other callers besides `List`'s internals were to call this on
        // some random `NonNull<Entry>`, this would not be the case, and
        // this could be constructing an erroneous `Pin` from a referent
        // that may not be pinned!
        Pin::new_unchecked(Box::from_raw(ptr.as_ptr()))
    }

    /// Access an element's `Links`.
    unsafe fn links(target: NonNull<Entry>) -> NonNull<list::Links<Entry>> {
        // Using `ptr::addr_of_mut!` permits us to avoid creating a temporary
        // reference without using layout-dependent casts.
        let links = ptr::addr_of_mut!((*target.as_ptr()).links);

        // `NonNull::new_unchecked` is safe to use here, because the pointer that
        // we offset was not null, implying that the pointer produced by offsetting
        // it will also not be null.
        NonNull::new_unchecked(links)
    }
}

impl Entry {
    fn new(val: i32) -> Self {
        Self {
            val,
            ..Self::default()
        }
    }
}

Using a List as a first-in, first-out (FIFO) queue with List::push_back and List::pop_front:

// Now that we've implemented the `Linked` trait for our `Entry` type, we can
// create a `List` of entries:
let mut list = List::<Entry>::new();

// Push some entries to the list:
for i in 0..5 {
    list.push_back(Box::pin(Entry::new(i)));
}

// The list is a doubly-ended queue. We can use the `pop_front` method with
// `push_back` to dequeue elements in FIFO order:
for i in 0..5 {
    let entry = list.pop_front()
        .expect("the list should have 5 entries in it");
    assert_eq!(entry.val, i, "entries are dequeued in FIFO order");
}

assert!(list.is_empty());

Using a List as a last-in, first-out (LIFO) stack with List::push_back and List::pop_back:

let mut list = List::<Entry>::new();

// Push some entries to the list:
for i in 0..5 {
    list.push_back(Box::pin(Entry::new(i)));
}

// Note that we have reversed the direction of the iterator, since
// we are popping from the *back* of the list:
for i in (0..5).into_iter().rev() {
    let entry = list.pop_back()
        .expect("the list should have 5 entries in it");
    assert_eq!(entry.val, i, "entries are dequeued in LIFO order");
}

assert!(list.is_empty());

Implementations

impl<T: Linked<Links<T>> + ?Sized> List<T>

pub const fn new() -> List<T>

Returns a new empty list.

pub fn append(&mut self, other: &mut Self)

Moves all elements from other to the end of the list.

This reuses all the nodes from other and moves them into self. After this operation, other becomes empty.

This operation should complete in O(1) time and O(1) memory.

pub fn try_split_off(&mut self, at: usize) -> Option<Self>

Attempts to split the list into two at the given index (inclusive).

Returns everything after the given index (including the node at that index), or None if the index is greater than the list’s length.

This operation should complete in O(n) time.

Returns

• Some(List<T>) with a new list containing every element after at, if at <= self.len()
• None if at > self.len()

pub fn split_off(&mut self, at: usize) -> Self

Split the list into two at the given index (inclusive).

Every element after the given index, including the node at that index, is removed from this list, and returned as a new list.

This operation should complete in O(n) time.

Returns

A new List<T> containing every element after the index at in this list.

Panics

If at > self.len().

pub fn is_empty(&self) -> bool

Returns true if this list is empty.

pub fn len(&self) -> usize

Returns the number of elements in the list.

pub fn assert_valid(&self)

Asserts as many of the linked list’s invariants as possible.

pub fn pop_back(&mut self) -> Option<T::Handle>

Removes an item from the tail of the list.

This operation should complete in O(1) time.

This returns a Handle that owns the popped element. Dropping the Handle will drop the element.

Returns

• Some(T::Handle) containing the last element of this list, if the list was not empty.
• None if this list is empty.

pub fn pop_front(&mut self) -> Option<T::Handle>

Removes an item from the head of the list.

This operation should complete in O(1) time.

This returns a Handle that owns the popped element. Dropping the Handle will drop the element.

Returns

• Some(T::Handle) containing the last element of this list, if the list was not empty.
• None if this list is empty.

pub fn push_back(&mut self, item: T::Handle)

Appends an item to the tail of the list.

This operation should complete in O(1) time.

This takes a Handle that owns the appended item. While the element is in the list, it is owned by the list, and will be dropped when the list is dropped. If the element is removed or otherwise unlinked from the list, ownership is assigned back to the Handle.

pub fn push_front(&mut self, item: T::Handle)

Appends an item to the head of the list.

This operation should complete in O(1) time.

This takes a Handle that owns the appended item. While the element is in the list, it is owned by the list, and will be dropped when the list is dropped. If the element is removed or otherwise unlinked from the list, ownership is assigned back to the Handle.

pub fn front(&self) -> Option<Pin<&T>>

Returns an immutable reference to the first element in the list.

This operation should complete in O(1) time.

The node is Pinned in memory, as moving it to a different memory location while it is in the list would corrupt the links pointing to that node.

Returns

• Some(Pin<&mut T>) containing a pinned immutable reference to the first element of the list, if the list is non-empty.
• None if the list is empty.

pub fn front_mut(&mut self) -> Option<Pin<&mut T>>

Returns a mutable reference to the first element in the list.

The node is Pinned in memory, as moving it to a different memory location while it is in the list would corrupt the links pointing to that node.

This operation should complete in O(1) time.

Returns

• Some(Pin<&mut T>) containing a pinned mutable reference to the first element of the list, if the list is non-empty.
• None if the list is empty.

pub fn back(&self) -> Option<Pin<&T>>

Returns a reference to the last element in the list/

The node is Pinned in memory, as moving it to a different memory location while it is in the list would corrupt the links pointing to that node.

This operation should complete in O(1) time.

Returns

• Some(Pin<&T>) containing a pinned immutable reference to the last element of the list, if the list is non-empty.
• None if the list is empty.

pub fn back_mut(&mut self) -> Option<Pin<&mut T>>

Returns a mutable reference to the last element in the list, or None if the list is empty.

The node is Pinned in memory, as moving it to a different memory location while it is in the list would corrupt the links pointing to that node.

This operation should complete in O(1) time.

Returns

• Some(Pin<&T>) containing a pinned mutable reference to the last element of the list, if the list is non-empty.
• None if the list is empty.

pub unsafe fn remove(&mut self, item: NonNull<T>) -> Option<T::Handle>

Remove an arbitrary node from the list.

This operation should complete in O(1) time.

This returns a Handle that owns the popped element. Dropping the Handle will drop the element.

Returns

• Some(T::Handle) containing a Handle that owns item, if item is currently linked into this list.
• None if item is not an element of this list.

Safety

The caller must ensure that the removed node is an element of this linked list, and not any other linked list.

pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T>

Returns a CursorMut starting at the first element.

The CursorMut type can be used as a mutable Iterator. In addition, however, it also permits modifying the structure of the list by inserting or removing elements at the cursor’s current position.

pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T>

Returns a CursorMut starting at the last element.

The CursorMut type can be used as a mutable Iterator. In addition, however, it also permits modifying the structure of the list by inserting or removing elements at the cursor’s current position.

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

Returns a Cursor starting at the first element.

The Cursor type can be used as Iterator over this list. In addition, it may be seeked back and forth to an arbitrary position in the list.

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

Returns a Cursor starting at the last element.

The Cursor type can be used as Iterator over this list. In addition, it may be seeked back and forth to an arbitrary position in the list.

pub fn iter(&self) -> Iter<'_, T>

Returns an iterator over the items in this list, by reference.

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Returns an iterator over the items in this list, by mutable reference.

pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, T, F>

where F: FnMut(&T) -> bool,

Returns an iterator which uses a closure to determine if an element should be removed from the list.

If the closure returns true, then the element is removed and yielded. If the closure returns false, the element will remain in the list and will not be yielded by the iterator.

Note that unlike the drain_filter method on [std::collections::LinkedList], the closure is not permitted to mutate the elements of the list, as a mutable reference could be used to improperly unlink list nodes.

Trait Implementations

impl<T: Linked<Links<T>> + ?Sized> Debug for List<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Linked<Links<T>> + ?Sized> Drop for List<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T> Extend<<T as Linked<Links<T>>>::Handle> for List<T>

where T: Linked<Links<T>> + ?Sized,

fn extend<I: IntoIterator<Item = T::Handle>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> FromIterator<<T as Linked<Links<T>>>::Handle> for List<T>

where T: Linked<Links<T>> + ?Sized,

fn from_iter<I: IntoIterator<Item = T::Handle>>(iter: I) -> Self

Creates a value from an iterator.

impl<'list, T: Linked<Links<T>> + ?Sized> IntoIterator for &'list List<T>

type Item = &'list T

The type of the elements being iterated over.

type IntoIter = Iter<'list, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'list, T: Linked<Links<T>> + ?Sized> IntoIterator for &'list mut List<T>

type Item = Pin<&'list mut T>

The type of the elements being iterated over.

type IntoIter = IterMut<'list, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Linked<Links<T>> + ?Sized> IntoIterator for List<T>

type Item = <T as Linked<Links<T>>>::Handle

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> Send for List<T>

where T: Send + Linked<Links<T>> + ?Sized,

impl<T> Sync for List<T>

where T: Sync + Linked<Links<T>> + ?Sized,