Module dlist 

Available on crate feature dlist only.

An intrusive doubly linked list implementation.

This module provides DLinkedList, a doubly linked list where elements embed the list nodes themselves. This design offers memory efficiency and explicit control over allocation, suitable for scenarios like building LRU caches directly within data structures.

Features

• O(1) push and pop from both front and back.
• Generic over pointer types (Box, Arc, NonNull, raw pointers).
• Supports multiple lists for the same item via Tag.

Example

use embed_collections::{dlist::{DLinkedList, DListItem, DListNode}, Pointer};
use core::cell::UnsafeCell;
use std::sync::Arc;
use core::ptr::NonNull;

struct MyItem {
    id: u32,
    data: String,
    node: UnsafeCell<DListNode<MyItem, ()>>,
}

impl MyItem {
    fn new(id: u32, data: &str) -> Self {
        MyItem {
            id,
            data: data.to_string(),
            node: UnsafeCell::new(DListNode::default()),
        }
    }
}

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

// Using Box<T> (owned pointers)
{
    let mut list = DLinkedList::<Box<MyItem>, ()>::new();
    list.push_back(Box::new(MyItem::new(1, "First")));
    list.push_front(Box::new(MyItem::new(2, "Second")));
    list.push_back(Box::new(MyItem::new(3, "Third")));
    assert_eq!(list.len(), 3);
    assert_eq!(list.pop_front().unwrap().id, 2);
    assert_eq!(list.pop_back().unwrap().id, 3);
    assert_eq!(list.pop_front().unwrap().id, 1);
    assert!(list.is_empty());
}

// Using Arc<T> (shared ownership)
{
    let mut list = DLinkedList::<Arc<MyItem>, ()>::new();
    list.push_back(Arc::new(MyItem::new(1, "First")));
    list.push_front(Arc::new(MyItem::new(2, "Second")));
    list.push_back(Arc::new(MyItem::new(3, "Third")));
    assert_eq!(list.len(), 3);
    assert_eq!(list.pop_front().unwrap().id, 2);
    assert_eq!(list.pop_back().unwrap().id, 3);
    assert_eq!(list.pop_front().unwrap().id, 1);
    assert!(list.is_empty());
}

// Using NonNull<T> (raw pointers without ownership)
{
    let mut list = DLinkedList::<NonNull<MyItem>, ()>::new();
    let item1 = Box::leak(Box::new(MyItem::new(1, "First")));
    let item2 = Box::leak(Box::new(MyItem::new(2, "Second")));
    let item3 = Box::leak(Box::new(MyItem::new(3, "Third")));
    list.push_back(NonNull::from(item1));
    list.push_front(NonNull::from(item2));
    list.push_back(NonNull::from(item3));
    assert_eq!(list.len(), 3);
    assert_eq!(unsafe { list.pop_front().unwrap().as_ref().id }, 2);
    assert_eq!(unsafe { list.pop_back().unwrap().as_ref().id }, 3);
    assert_eq!(unsafe { list.pop_front().unwrap().as_ref().id }, 1);
    assert!(list.is_empty());
}

Structs

DLinkedList

An intrusive doubly linked list.

DLinkedListDrainer

DLinkedListIterator

DListNode

The node structure that must be embedded in items to be stored in a DLinkedList.

Traits

DListItem

A trait to return internal mutable DListNode for specified list.