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) -> Option<P>

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

• Return Some if the item is in the list.
• Return None if the item is not in any list.

NOTE： Due to avoid miri stack borrow rule error, item is a raw pointer.

Safety

item should point the a valid item. Do not remove item from other 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<()>>,
}

unsafe impl Send for TestNode {}

unsafe impl DListItem<()> for TestNode {
    fn get_node(&self) -> &mut DListNode<()> {
        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).unwrap() };
assert_eq!(l.len(), 2);
assert_eq!(node2.value, 2);

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

Remove the item from the list if it’s in the list, but do not recover the removed ptr to P.

Safety

You have to make sure the returned item ref counter be dropped manually

If the item was in the list, return item back; otherwise return null()

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

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

NOTE： Due to avoid miri stack borrow rule error, item is a raw pointer.

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_ptr(&self) -> *const P::Target

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

Returns a reference to the front element.

pub fn get_back_ptr(&self) -> *const P::Target

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 iter<'a>(&'a self) -> DLinkedListIter<'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<'a, P, Tag> IntoIterator for &'a DLinkedList<P, Tag>

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

type Item = &'a P

The type of the elements being iterated over.

type IntoIter = DLinkedListIter<'a, P, Tag>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

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

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

type Item = P

The type of the elements being iterated over.

type IntoIter = Drainer<DLinkedList<P, Tag>, P, Tag>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

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

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