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 data structure can also be used as a stack or doubly-linked list by using the List::pop_front and List::push_back methods.

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

Returns everything after the given index (including the node at that index).

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

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 compute in O(n) time.

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

source

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

Remove an item from the head of the list.

This operation should compute in O(n) time.

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

source

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

Appends an item to the tail of the list.

This operation should compute in O(n) 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 compute in O(n) 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 a reference to the first 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.

source

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

Returns a mutable reference to the first 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.

source

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

Returns a 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.

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.

source

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

Remove an arbitrary node from the list.

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

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>ⓘNotable traits for CursorMut<'list, T>`impl<'list, T: Linked<Links<T>> + ?Sized> Iterator for CursorMut<'list, T> type Item = Pin<&'list mut 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>ⓘNotable traits for CursorMut<'list, T>`impl<'list, T: Linked<Links<T>> + ?Sized> Iterator for CursorMut<'list, T> type Item = Pin<&'list mut T>;`

Returns a CursorMut s+tarting 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>ⓘNotable traits for Cursor<'list, T>`impl<'list, T: Linked<Links<T>> + ?Sized> Iterator for Cursor<'list, T> type Item = Pin<&'list 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>ⓘNotable traits for Cursor<'list, T>`impl<'list, T: Linked<Links<T>> + ?Sized> Iterator for Cursor<'list, T> type Item = Pin<&'list T>;`

Returns a CursorMut s+tarting 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>ⓘNotable traits for Iter<'list, T>`impl<'list, T: Linked<Links<T>> + ?Sized> Iterator for Iter<'list, T> type Item = &'list T;`

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

source

pub fn iter_mut(&mut self) -> IterMut<'_, T>ⓘNotable traits for IterMut<'list, T>`impl<'list, T: Linked<Links<T>> + ?Sized> Iterator for IterMut<'list, T> type Item = Pin<&'list mut 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>ⓘNotable traits for DrainFilter<'_, T, F>`impl<T, F> Iterator for DrainFilter<'_, T, F>where F: FnMut(&T) -> bool, T: Linked<Links<T>> + ?Sized, type Item = T::Handle;`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.