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

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

// SAFETY: The objects are freshly allocated and are freed only after being removed.
unsafe {
    list.as_mut().push_front_raw(Box::into_raw(Box::new(Foo::new(1))));
    list.as_mut().push_back_raw(Box::into_raw(Box::new(Foo::new(2))));
}

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

while let Some(foo_ptr) = list.as_mut().pop_front() {
    // SAFETY: `foo_ptr` was created by `Box::into_raw` and is no longer in the list.
    let _ = unsafe { 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 list = DoublyLinkedList::<UniquePtr<Foo>>::new());

list.as_mut().push_front(UniquePtr::try_new(Foo::new(1)).unwrap());
list.as_mut().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.as_mut().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(TagB)]
    node_b: DoublyLinkedListNode<Foo>,
}

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

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

list_a.as_mut().push_back(foo.clone());
list_b.as_mut().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 front_mut(self: Pin<&mut Self>) -> Option<Pin<&mut P::Target>>

where P: MutPtr,

Returns a pinned mutable 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 back_mut(self: Pin<&mut Self>) -> Option<Pin<&mut P::Target>>

where P: MutPtr,

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

pub fn push_front(self: Pin<&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(self: Pin<&mut Self>, ptr: P)

Pushes an element to the front of the list.

Panics

Panics in debug builds if the object is already in a container.

Safety

The caller must ensure that ptr is a valid pointer to a T that is not currently in any list, and that the object outlives the reference from the list. If mutable element accessors (front_mut, back_mut, iter_mut, CursorMut::get_mut, etc.) are used on a raw-pointer list, the caller must also ensure that no other references to the element are accessed while it is mutably borrowed through the list, and that the element satisfies Pin’s drop guarantee (it is not moved out of its memory location before being dropped, unless P::Target: Unpin).

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

Pushes an element to the back of the list.

Panics

Panics in debug builds 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. If mutable element accessors (front_mut, back_mut, iter_mut, CursorMut::get_mut, etc.) are used on a raw-pointer list, the caller must also ensure that no other references to the element are accessed while it is mutably borrowed through the list, and that the element satisfies Pin’s drop guarantee (it is not moved out of its memory location before being dropped, unless P::Target: Unpin).

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

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

pub fn pop_back(self: Pin<&mut Self>) -> Option<P>

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

pub fn clear(self: Pin<&mut Self>)

Removes all elements from the list.

pub unsafe fn erase(self: Pin<&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( self: Pin<&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. If mutable element accessors (front_mut, back_mut, iter_mut, CursorMut::get_mut, etc.) are used on a raw-pointer list, the caller must also ensure that no other references to replacement are accessed while it is mutably borrowed through the list, and that replacement satisfies Pin’s drop guarantee (it is not moved out of its memory location before being dropped, unless P::Target: Unpin).

pub fn erase_if<F>(self: Pin<&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_front_mut(self: Pin<&mut Self>) -> CursorMut<'_, P, Tag, S>

Returns a cursor positioned at the front of the list.

pub fn cursor_back_mut(self: Pin<&mut Self>) -> CursorMut<'_, P, Tag, S>

Returns a cursor positioned at the back (end sentinel) of the list.

pub unsafe fn cursor_at( self: Pin<&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 splice( self: Pin<&mut Self>, other: Pin<&mut DoublyLinkedList<P, Tag, S>>, )

Splices all elements from other onto the end of self.

Upon completion, other is left empty.

This operation is O(1).

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

pub fn iter_mut(self: Pin<&mut Self>) -> IteratorMut<'_, P, Tag>

where P: MutPtr,

Returns a mutable bidirectional iterator over the elements of the list.

Elements are yielded as Pin<&mut P::Target> since they must not be moved while linked.

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

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

pub fn forward_iter_mut(self: Pin<&mut Self>) -> ForwardIteratorMut<'_, P, Tag>

where P: MutPtr,

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

Elements are yielded as Pin<&mut P::Target> since they must not be moved while linked.

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

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

pub fn reverse_iter_mut(self: Pin<&mut Self>) -> ReverseIteratorMut<'_, P, Tag>

where P: MutPtr,

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

Elements are yielded as Pin<&mut P::Target> since they must not be moved while linked.

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> HashTableBucket<P> for DoublyLinkedList<P, Tag, S>

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

type Iter<'a> = ForwardIterator<'a, P, Tag> where Self: 'a, P: 'a

An iterator over the elements of a bucket.

fn try_new_buckets(count: usize) -> Result<Pin<Array<Self>>, AllocError>

Allocates the storage for count empty buckets.

fn is_empty(&self) -> bool

Returns true if the bucket is empty.

unsafe fn push_front_raw(self: Pin<&mut Self>, ptr: P)

Pushes an element to the front of the bucket.

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

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

Finds the first element of the bucket which satisfies the predicate.

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

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

Finds the first element of the bucket which satisfies the predicate, erases it from the bucket, and returns it.

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

Erases obj from the bucket, returning it. Returns None if obj is not in any container.

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

Replaces obj with replacement in the bucket, returning the replaced element.

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

Removes all elements from the bucket.

fn iter<'a>(&'a self) -> Self::Iter<'a>

where P: 'a,

Returns an iterator over the elements of the bucket.

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.