Struct cordyceps::List

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

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§

source§

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

source

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

Returns a new empty list.

source

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.

source

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()
source

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().

source

pub fn is_empty(&self) -> bool

Returns true if this list is empty.

source

pub fn len(&self) -> usize

Returns the number of elements in the list.

source

pub fn assert_valid(&self)

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

source

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.
source

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.
source

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.

source

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.

source

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.
source

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.
source

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.
source

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.
source

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.

source

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.

source

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.

source

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.

source

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.

source

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

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

source

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

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

source

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 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§

source§

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

source§

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

Formats the value using the given formatter. Read more
source§

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

source§

fn drop(&mut self)

Executes the destructor for this type. Read more
source§

impl<T> Extend<<T as Linked<Links<T>>>::Handle> for List<T>
where T: Linked<Links<T>> + ?Sized,

source§

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

Extends a collection with the contents of an iterator. Read more
source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
source§

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. Read more
source§

impl<T> FromIterator<<T as Linked<Links<T>>>::Handle> for List<T>
where T: Linked<Links<T>> + ?Sized,

source§

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

Creates a value from an iterator. Read more
source§

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?
source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
source§

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?
source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
source§

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?
source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
source§

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

source§

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

Auto Trait Implementations§

§

impl<T> Freeze for List<T>
where T: ?Sized,

§

impl<T> RefUnwindSafe for List<T>
where T: RefUnwindSafe + ?Sized,

§

impl<T> Unpin for List<T>
where T: ?Sized,

§

impl<T> UnwindSafe for List<T>
where T: RefUnwindSafe + ?Sized,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.