Struct SinglyLinkedList 

pub struct SinglyLinkedList<P, Tag = DefaultObjectTag, S = NonTrackingSize>
where
    P: PtrTraits,
    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
    S: SizeTracker,
{ /* private fields */ }

A singly linked list that supports intrusive nodes and different ownership semantics.

SinglyLinkedList is a layout-compatible analog to fbl::SinglyLinkedList in C++. It allows managing singly linked lists of objects where the bookkeeping storage (the node state) exists on the objects themselves, eliminating the need for runtime allocation/deallocation to add or remove members.

The list stores pointers to the objects, and is parametrized by the pointer type P. Supported pointer types are:

1. *mut T : Raw unmanaged pointers.
2. [UniquePtr<T>] : Unique managed pointers.
3. [RefPtr<T>] : Managed pointers to ref-counted objects.

Ownership

• Lists of managed pointer types ([UniquePtr], [RefPtr]) hold references to objects and follow the rules of the particular managed pointer patterns. Destroying or clearing a list of managed pointers will release the references to the objects.
• Lists of unmanaged pointer types (*mut T) perform no lifecycle management. It is up to the user to make sure that lifecycles are managed properly. As an added safety, a list of unmanaged pointers will assert if it is destroyed with elements still in it.

Multiple Lists

Objects may exist in multiple lists simultaneously through the use of custom trait tags. See SinglyLinkedListContainable for more details.

Examples

Example 1: A simple list of unmanaged pointers to Foo objects

use fbl::{SinglyLinkedList, SinglyLinkedListNode, SinglyLinkedListContainable};

#[derive(SinglyLinkedListContainable)]
struct Foo {
    value: i32,
    #[sll_node]
    node: SinglyLinkedListNode<Foo>,
}

impl Foo {
    fn new(value: i32) -> Self {
        Self { value, node: SinglyLinkedListNode::new() }
    }
}

fn test() {
    let mut list = SinglyLinkedList::<*mut Foo>::new();

    let mut foo1 = Foo::new(1);
    let mut foo2 = Foo::new(2);

    unsafe {
        list.push_front_raw(&mut foo1);
        list.push_front_raw(&mut foo2);
    }

    for foo in list.iter() {
        println!("Value: {}", foo.value);
    }

    list.clear(); // Must clear before going out of scope if using raw pointers!
}

Example 2: A simple list of unique pointers to Foo objects

use fbl::{SinglyLinkedList, SinglyLinkedListNode, SinglyLinkedListContainable, UniquePtr};

#[derive(fbl::Recyclable, SinglyLinkedListContainable)]
struct Foo {
    value: i32,
    #[sll_node]
    node: SinglyLinkedListNode<Foo>,
}

impl Foo {
    fn new(value: i32) -> Self {
        Self { value, node: SinglyLinkedListNode::new() }
    }
}

fn test() {
    let mut list = SinglyLinkedList::<UniquePtr<Foo>>::new();

    let foo1 = UniquePtr::try_new(Foo::new(1)).unwrap();
    let foo2 = UniquePtr::try_new(Foo::new(2)).unwrap();

    list.push_front(foo1);
    list.push_front(foo2);

    for foo in list.iter() {
        println!("Value: {}", foo.value);
    }

    // List drops here and cleans up objects automatically!
}

Example 3: An object in multiple lists

use fbl::{SinglyLinkedList, SinglyLinkedListNode, SinglyLinkedListContainable};

struct Tag2;

#[derive(SinglyLinkedListContainable)]
struct Foo {
    value: i32,
    #[sll_node]
    node1: SinglyLinkedListNode<Foo>,
    #[sll_node(tag = Tag2)]
    node2: SinglyLinkedListNode<Foo>,
}

fn test() {
    let mut list1 = SinglyLinkedList::<*mut Foo>::new();
    let mut list2 = SinglyLinkedList::<*mut Foo, Tag2>::new();

    let mut foo = Foo {
        value: 42,
        node1: SinglyLinkedListNode::new(),
        node2: SinglyLinkedListNode::new(),
    };

    unsafe {
        list1.push_front_raw(&mut foo);
        list2.push_front_raw(&mut foo);
    }

    // ... access via both lists ...

    list1.clear();
    list2.clear();
}

Implementations

impl<P, Tag, S> SinglyLinkedList<P, Tag, S>

where P: PtrTraits, P::Target: SinglyLinkedListContainable<P::Target, Tag>, S: SizeTracker,

pub const fn new() -> Self

Creates a new, empty list.

pub fn is_empty(&self) -> bool

Returns true if the list is empty.

pub fn front(&self) -> Option<&P::Target>

Returns a reference to the first element of the list, or None if it is empty.

pub fn front_mut(&mut self) -> Option<&mut P::Target>

Returns a mutable reference to the first element of the list, or None if it is empty.

pub fn push_front(&mut self, ptr: P)

where P: ManagedPtr,

Pushes an element to the front of the list.

Panics

Panics if the object is already in a container.

pub unsafe fn push_front_raw(&mut self, ptr: P)

Pushes an element to the front of the list.

For managed pointers, use the safe [push_front] instead.

Panics

Panics if the object is already in a container.

Safety

The caller must ensure that ptr is a valid pointer to a T and that the object outlives the reference from the list.

pub fn pop_front(&mut self) -> Option<P>

Removes and returns the first element of the list, or None if it is empty.

pub fn clear(&mut self)

Removes all elements from the list.

pub unsafe fn insert_after_raw(&mut self, pos: *mut P::Target, ptr: P)

Inserts an element after the specified position.

For managed pointers, consider using [CursorMut::insert_after] for a safer alternative.

Safety

The caller must ensure that pos is a valid pointer to an element in this list, and that ptr is a valid pointer to an element not currently in any container.

pub unsafe fn erase_next_raw(&mut self, pos: *mut P::Target) -> Option<P>

Erases the element after the specified position.

For managed pointers, consider using [CursorMut::erase_next] for a safer alternative.

Safety

The caller must ensure that pos is a valid pointer to an element in this list.

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

Swaps the contents of this list with another list.

pub fn erase_if<F>(&mut self, f: F) -> Option<P>

where F: FnMut(&P::Target) -> bool,

Finds the first element matching the predicate, removes it from the list, and returns it. Returns None if no element matches.

pub fn replace_if<F>(&mut self, f: F, value: P) -> Option<P>

where F: FnMut(&P::Target) -> bool, P: ManagedPtr,

Replaces the first element matching the predicate with value. Returns the replaced element.

Panics

Panics if the object is already in a container.

pub unsafe fn replace_if_raw<F>(&mut self, f: F, value: P) -> Option<P>

where F: FnMut(&P::Target) -> bool,

Replaces the first element matching the predicate with value. Returns the replaced element.

Panics

Panics if the object is already in a container.

Safety

The caller must ensure that value is a valid pointer to a T and that the object outlives the reference from the list.

pub unsafe fn split_after_raw(&mut self, pos: *mut P::Target) -> Self

Splits the list after the specified position, returning a new list containing the elements that followed pos.

Safety

The caller must ensure that pos is a valid pointer to an element in this list.

pub fn retain<F>(&mut self, f: F)

where F: FnMut(&P::Target) -> bool,

Retains only the elements specified by the predicate.

pub fn cursor_mut(&mut self) -> CursorMut<'_, P, Tag, S>

Returns a cursor positioned at the front of the list.

pub fn size_slow(&self) -> usize

Calculates the size of the list by iterating through all elements. O(N) time complexity.

pub fn find_if<F>(&self, f: F) -> Option<&P::Target>

where F: FnMut(&P::Target) -> bool,

Finds the first element matching the predicate.

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

Returns an iterator over the elements of the list.

impl<P, Tag> SinglyLinkedList<P, Tag, TrackingSize>

where P: PtrTraits, P::Target: SinglyLinkedListContainable<P::Target, Tag>,

pub fn size(&self) -> usize

Returns the size of the list. O(1) time complexity.

Trait Implementations

impl<P, Tag, S> Debug for SinglyLinkedList<P, Tag, S>

where P: PtrTraits, P::Target: SinglyLinkedListContainable<P::Target, Tag> + Debug, S: SizeTracker,

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

Formats the value using the given formatter.

impl<P, Tag, S> Drop for SinglyLinkedList<P, Tag, S>

where P: PtrTraits, P::Target: SinglyLinkedListContainable<P::Target, Tag>, S: SizeTracker,

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

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

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.