Struct DoublyLinkedList 

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

An intrusive doubly linked list container supporting custom ownership semantics, constant-time operations, and circular-like node layout.

Bookkeeping & Memory Storage

The bookkeeping storage (DoublyLinkedListNode) required to link elements exists directly on the objects themselves. This intrusive pattern eliminates the need for runtime bookkeeping allocations/deallocations when adding or removing members to/from the container.

The list stores pointers to the objects, not the objects themselves, and is parameterized based on the specific pointer wrapper to be stored (P). Supported pointer wrappers are:

• *mut T : Raw unmanaged pointers.
• UniquePtr<T> : Unique managed pointers.
• RefPtr<T> : Shared managed pointers to reference-counted objects.

Lifecycle Management

• Managed Pointers (UniquePtr/RefPtr): The list holds ownership references of elements and follows the rules of the respective smart pointer. Clearing the list or dropping it out of scope automatically releases references, which may destruct the elements if it was their last reference.

• Unmanaged Pointers (*mut T): The list performs no lifecycle management. It is up to the caller to ensure elements outlive the list and are freed correctly. As a safety check, a list of unmanaged pointers will panic/debug-assert if it is dropped with elements still inside.

Ring Layout & Sentinel

Nodes are arranged in a circular-like ring structure:

• head stores a sentinel value (a pointer to the container itself) when the list is empty.
• For non-empty lists, the next pointer of the tail node points to the sentinel, and the prev pointer of the head node points to the tail node. This allows constant-time O(1) tail lookup and bidirectionality.
• Because the sentinel points back to the container’s own memory address, the DoublyLinkedList container must be pinned in memory (typically via pin_init::stack_pin_init!) and cannot be safely moved after initialization.

Additional Functionality over SinglyLinkedList

• O(1) push_back, pop_back, and back operations.
• The ability to insert (before an element) in addition to insert_after.
• The ability to erase (by reference or iterator) in addition to erase_next.
• Bidirectional iteration support.

Multiple List Participation

Objects may exist on multiple lists simultaneously through the use of custom Tag classes implementing DoublyLinkedListContainable multiple times.

---

Example: Simple list of unmanaged raw pointers

#[derive(fbl::DoublyLinkedListContainable)]
struct Foo {
    value: i32,
    #[dll_node]
    node: DoublyLinkedListNode<Foo>,
}

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

unsafe {
    stack_pin_init!(let mut list = DoublyLinkedList::<*mut Foo>::new());
    let list = list.get_unchecked_mut();

    list.push_front(Box::into_raw(Box::new(Foo::new(1))));
    list.push_back(Box::into_raw(Box::new(Foo::new(2))));

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

    while let Some(foo_ptr) = list.pop_front() {
        let _ = Box::from_raw(foo_ptr);
    }
}

Example: Simple list of unique managed pointers

use fbl::{DoublyLinkedList, DoublyLinkedListNode, UniquePtr, stack_pin_init};

#[derive(fbl::DoublyLinkedListContainable, fbl::Recyclable)]
struct Foo {
    value: i32,
    #[dll_node]
    node: DoublyLinkedListNode<Foo>,
}

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

stack_pin_init!(let mut list = DoublyLinkedList::<UniquePtr<Foo>>::new());
let list = list.get_unchecked_mut();

list.push_front(UniquePtr::try_new(Foo::new(1)).unwrap());
list.push_back(UniquePtr::try_new(Foo::new(2)).unwrap());

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

// Clearing the list automatically drops unique pointers and reclaims their memory!
list.clear();

Example: Shared objects in multiple lists simultaneously using Tags

use fbl::{DoublyLinkedList, DoublyLinkedListNode, RefPtr, stack_pin_init};

struct TagA;
struct TagB;

#[fbl::ref_counted]
#[derive(fbl::DoublyLinkedListContainable)]
struct Foo {
    value: i32,
    #[dll_node(TagA)]
    node_a: DoublyLinkedListNode<Foo>,
    #[dll_node(TagA)]
    node_b: DoublyLinkedListNode<Foo>,
}

stack_pin_init!(let mut list_a = DoublyLinkedList::<RefPtr<Foo>, TagA>::new());
stack_pin_init!(let mut list_b = DoublyLinkedList::<RefPtr<Foo>, TagB>::new());
let list_a = list_a.get_unchecked_mut();
let list_b = list_b.get_unchecked_mut();

let foo = fbl::make_ref_counted!(Foo {
    value: 42,
    node_a: DoublyLinkedListNode::new(),
    node_b: DoublyLinkedListNode::new(),
}).unwrap();

list_a.push_back(foo.clone());
list_b.push_back(foo);

Implementations

impl<P, Tag, S> DoublyLinkedList<P, Tag, S>

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

pub fn project<'__pin>( self: Pin<&'__pin mut Self>, ) -> DoublyLinkedListProjection<'__pin, P, Tag, S>

Pin-projects all fields of Self.

These fields are structurally pinned:

• _pin

These fields are not structurally pinned:

• head
• size
• _phantom

impl<P, Tag, S> DoublyLinkedList<P, Tag, S>

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

pub fn new() -> impl PinInit<Self, Infallible>

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 back(&self) -> Option<&P::Target>

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

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 push_back(&mut self, ptr: P)

where P: ManagedPtr,

Pushes an element to the back of the list.

Panics

Panics if the object is already in a container.

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

Pushes an element to the back of the list.

Panics

Panics if the object is already in a container.

Safety

The caller must ensure that ptr is a valid pointer to an object that is not currently in any 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 pop_back(&mut self) -> Option<P>

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

pub fn clear(&mut self)

Removes all elements from the list.

pub unsafe fn erase(&mut self, obj: &P::Target) -> Option<P>

Erases the given element from the list. Returns the erased element.

Safety

The caller must ensure that obj is a valid reference to an object that is currently in this list instance.

pub unsafe fn replace_raw( &mut self, obj: &P::Target, replacement: P, ) -> Option<P>

Replaces the given element with replacement. Returns the replaced element.

Safety

The caller must ensure that obj is a valid reference to an object that is currently in this list instance, and replacement is not in any 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 find_if<F>(&self, f: F) -> Option<&P::Target>

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

Finds the first element that satisfies the predicate.

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

Returns a cursor positioned at the front of the list.

pub unsafe fn cursor_at(&mut self, obj: &P::Target) -> CursorMut<'_, P, Tag, S>

Returns a cursor positioned at the given element.

Safety

The caller must ensure that obj is a member of this list. It is undefined behavior to use the returned cursor if obj is not in the list, or if it is in a different list.

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

pub fn forward_iter(&self) -> ForwardIterator<'_, P, Tag>

Returns a unidirectional forward iterator over the elements of the list.

pub fn reverse_iter(&self) -> ReverseIterator<'_, P, Tag>

Returns a unidirectional reverse iterator over the elements of the list.

impl<P, Tag> DoublyLinkedList<P, Tag, TrackingSize>

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

pub fn len(&self) -> usize

Returns the number of elements in the list.

Trait Implementations

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

where P: PtrTraits, P::Target: DoublyLinkedListContainable<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 DoublyLinkedList<P, Tag, S>

where P: PtrTraits, P::Target: DoublyLinkedListContainable<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.

impl<P, Tag, S> HasPinData for DoublyLinkedList<P, Tag, S>

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

type PinData = __ThePinData<P, Tag, S>

unsafe fn __pin_data() -> Self::PinData

impl<P, Tag, S> PinnedDrop for DoublyLinkedList<P, Tag, S>

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

fn drop(self: Pin<&mut Self>, _: OnlyCallFromDrop)

Executes the pinned destructor of this type.