Crate embed_dlist 

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_dlist::{DLinkedList, DListItem, DListNode};
use core::cell::UnsafeCell;
use std::sync::Arc;
use core::ptr::NonNull;

struct MyTag ();

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

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

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

// Using Box<T> (owned pointers)
{
    let mut list = DLinkedList::<Box<MyItem>, MyTag>::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>, MyTag>::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> (ignore ownership)
{
    let mut list = DLinkedList::<NonNull<MyItem>, MyTag>::new();
    let item1 = Box::into_raw(Box::new(MyItem::new(1, "First")));
    let item2 = Box::into_raw(Box::new(MyItem::new(2, "Second")));
    let item3 = Box::into_raw(Box::new(MyItem::new(3, "Third")));
    list.push_back(unsafe{NonNull::new_unchecked(item1)});
    list.push_front(unsafe{NonNull::new_unchecked(item2)});
    list.push_back(unsafe{NonNull::new_unchecked(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());
    unsafe{
        let _ = Box::from_raw(item1);
        let _ = Box::from_raw(item2);
        let _ = Box::from_raw(item3);
    }
}

Mixed Types

This example show mixed multiple types (which have the same DListNode field) in one list, with custom pointer type.

use embed_dlist::{DLinkedList, DListItem, DListNode};
use pointers::Pointer;
use core::cell::UnsafeCell;
use std::sync::Arc;

enum MixedPointer {
    Multi(Arc<ArcNode>),
    One(Box<BoxNode>),
}

impl MixedPointer {

    fn as_multi(&self) -> &Arc<ArcNode> {
        if let Self::Multi(inner) = self {
            inner
        } else {
            panic!("not Multi")
        }
    }

    fn as_one(&self) -> &Box<BoxNode> {
        if let Self::One(inner) = self {
            inner
        } else {
            panic!("not One")
        }
    }
}

const IS_ARC: usize = 0x1;
const TYPE_MASK: usize = IS_ARC;

struct ArcNode {
    _node: UnsafeCell<DListNode<()>>,
    v: usize,
}

struct BoxNode {
    _node: UnsafeCell<DListNode<()>>,
    v: String,
}

impl ArcNode {
    fn new(v: usize) -> Arc<Self> {
        Arc::new(Self{
            _node: Default::default(),
            v,
        })
    }
}

impl BoxNode {
    fn new(v: String) -> Box<Self> {
        Box::new(Self{
            _node: Default::default(),
            v,
        })
    }
}

struct MixedAddr (usize);

impl Pointer for MixedPointer {
    type Target = MixedAddr;

    fn as_ref(&self) -> &MixedAddr {
        unreachable!("we don't call as_ref in DLinkedList");
    }

    /// # Safety
    ///
    /// just a mock
    unsafe fn from_raw(p: *const MixedAddr) -> Self {
        let real_p = (p as usize) & (!TYPE_MASK);
        debug_assert!(real_p != 0);
        let type_flag = (p as usize) & TYPE_MASK;
        if type_flag == IS_ARC {
            Self::Multi(unsafe{Arc::from_raw(real_p as *mut ArcNode)})
        } else {
            Self::One(unsafe{Box::from_raw(real_p as *mut BoxNode)})
        }
    }

    /// # Safety
    /// the address into_raw cannot be defer directly
    fn into_raw(self) -> *const MixedAddr {
        let addr: usize = match self {
            MixedPointer::Multi(item)=>{Arc::into_raw(item) as usize | IS_ARC},
            MixedPointer::One(item)=>{Box::into_raw(item) as usize},
        };
        addr as *const MixedAddr
    }
}

unsafe impl DListItem<()> for MixedAddr {
     
    fn get_node(&self) -> &mut DListNode<()> {
        unreachable!();
    }

    unsafe fn get_node_from_ptr<'a>(p: *mut u8) -> &'a mut DListNode<()>
    where
        Self: 'a,
    {
        let real_p = (p as usize) & (!TYPE_MASK);
        debug_assert!(real_p != 0);
        let type_flag = (p as usize) & TYPE_MASK;
        if type_flag == IS_ARC {
            unsafe{&mut *(*(real_p as *const ArcNode))._node.get()}
        } else {
            unsafe{&mut *(*(real_p as *const BoxNode))._node.get()}
        }
    }
}

// list operation
let mut l = DLinkedList::<MixedPointer, ()>::new();
l.push_back(MixedPointer::Multi(ArcNode::new(1)));
l.push_back(MixedPointer::One(BoxNode::new("box1".to_string())));
l.push_back(MixedPointer::One(BoxNode::new("box2".to_string())));
l.push_back(MixedPointer::Multi(ArcNode::new(2)));

let mut iter = l.iter();
assert_eq!(iter.next().unwrap().as_multi().v, 1);
assert_eq!(iter.next().unwrap().as_one().v.as_str(), "box1");
assert_eq!(iter.next().unwrap().as_one().v.as_str(), "box2");
assert_eq!(iter.next().unwrap().as_multi().v, 2);
assert!(iter.next().is_none());

let mut iter = l.drain();
assert_eq!(iter.next().unwrap().as_multi().v, 1);
assert_eq!(iter.next().unwrap().as_one().v.as_str(), "box1");
assert_eq!(iter.next().unwrap().as_one().v.as_str(), "box2");
assert_eq!(iter.next().unwrap().as_multi().v, 2);
assert!(iter.next().is_none());

Structs

DLinkedList

An intrusive doubly linked list.

DLinkedListIter

DListNode

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

Drainer

Traits

DListItem

A trait to return internal mutable DListNode for specified list.

Type Aliases

DLinkedListDrainer

DLinkedListIntoIter