Struct DLinkedList 

pub struct DLinkedList<P, Tag>
where
    P: Pointer,
    P::Target: DListItem<Tag>,
{ /* private fields */ }

An intrusive doubly linked list.

Supports O(1) insertion and removal at both ends.

Implementations

impl<P, Tag> DLinkedList<P, Tag>

where P: Pointer, P::Target: DListItem<Tag>,

pub fn new() -> Self

Creates a new, empty doubly linked list.

pub fn clear(&mut self)

Clears the list, dropping all of its elements if the pointer type P owns them.

pub fn len(&self) -> usize

Returns the length of the list as usize.

pub fn is_empty(&self) -> bool

Returns true if the list contains no elements.

pub unsafe fn remove_node(&mut self, item: *const P::Target) -> P

Remove a node by raw pointer from the middle of the list, and recover P from item

NOTE： Due to we need to support Arc, item should be immutable reference.

Safety

item should point the a valid item, which must be already in the list, otherwise will lead to UB.

Example

use embed_dlist::{DLinkedList, DListItem, DListNode};
use core::cell::UnsafeCell;
extern crate alloc;
use alloc::boxed::Box;

#[derive(Debug)]
pub struct TestNode {
    pub value: i64,
    pub node: UnsafeCell<DListNode<Self, ()>>,
}

unsafe impl Send for TestNode {}

unsafe impl DListItem<()> for TestNode {
    fn get_node(&self) -> &mut DListNode<Self, ()> {
        unsafe { &mut *self.node.get() }
    }
}

fn new_node(v: i64) -> TestNode {
    TestNode { value: v, node: UnsafeCell::new(DListNode::default()) }
}

let mut l = DLinkedList::<Box<TestNode>, ()>::new();

let node1 = Box::new(new_node(1));
l.push_back(node1);
let node2 = Box::new(new_node(2));

// NOTE: use `node_p = node2.as_ptr()`  will trigger miri stack borrow rule.
// we use into_raw and then from_raw
let node2_p = Box::into_raw(node2);
l.push_back(unsafe{Box::from_raw(node2_p)});

let node3 = Box::new(new_node(3));
l.push_back(node3);
assert_eq!(l.len(), 3);

let node2 = unsafe { l.remove_node(node2_p) };
assert_eq!(l.len(), 2);
assert_eq!(node2.value, 2);

pub unsafe fn peak(&mut self, item: &P::Target)

Moves a node to the front of the list (e.g., for LRU updates).

NOTE： Due to we need to support Arc, item should be immutable reference.

Safety

The item must be in the list, otherwise will lead to UB.

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

Pushes an element to the front of the list.

pub fn push_back(&mut self, item: P)

Pushes an element to the back of the list.

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

Removes and returns the element at the front of the list.

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

Removes and returns the element at the back of the list.

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

Returns a reference to the front element.

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

Returns a reference to the back element.

pub fn is_front(&self, node: &P::Target) -> bool

Checks if the given node is the head of the list.

pub fn print<U: Debug>(&self)

Available on crate feature std only.

pub fn iter<'a>(&'a self) -> DLinkedListIterator<'a, P, Tag>

Returns an iterator over the list (borrowed).

NOTE

If you plan on turn the raw pointer to owned, use drain instead

Safety

The caller must ensure that the list is not modified in a way that can invalidate internal pointers (such as removing elements or dropping items) for the duration of the iterator’s use.

pub fn drain<'a>(&'a mut self) -> DLinkedListDrainer<'a, P, Tag>

Returns a draining iterator that removes items from the list. Crucial for cleaning up lists containing owned pointers (like Box).

Note

The iterator removes elements from the front of the list (FIFO order),

Trait Implementations

impl<P, Tag> Debug for DLinkedList<P, Tag>

where P: Pointer + Debug, P::Target: DListItem<Tag>,

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

Formats the value using the given formatter.

impl<P, Tag> Drop for DLinkedList<P, Tag>

where P: Pointer, P::Target: DListItem<Tag>,

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> Send for DLinkedList<P, Tag>

where P: Pointer, P::Target: DListItem<Tag>,