Crate embed_slist

Expand description

An intrusive singly linked list implementation.

This module provides SLinkedList, a singly linked list optimized for FIFO (First-In, First-Out) queue-like behavior. Elements embed the list nodes themselves, offering memory efficiency and explicit control over allocation.

§Features

O(1) push to back and pop from front.
Generic over pointer types (Box, Arc, NonNull, raw pointers).

§Example

use embed_slist::{SLinkedList, SListItem, SListNode};
use core::cell::UnsafeCell;
use std::sync::Arc;
use core::ptr::NonNull;

struct MyTask {
    priority: u8,
    description: String,
    node: UnsafeCell<SListNode<()>>,
}

impl MyTask {
    fn new(priority: u8, desc: &str) -> Self {
        MyTask {
            priority,
            description: desc.to_string(),
            node: UnsafeCell::new(SListNode::default()),
        }
    }
}

unsafe impl SListItem<()> for MyTask {
    fn get_node(&self) -> &mut SListNode<()> {
        unsafe { &mut *self.node.get() }
    }
}

// Using Box<T> (owned pointers)
{
    let mut task_queue = SLinkedList::<Box<MyTask>, ()>::new();
    task_queue.push_back(Box::new(MyTask::new(1, "Handle user login")));
    task_queue.push_back(Box::new(MyTask::new(2, "Process analytics data")));
    task_queue.push_back(Box::new(MyTask::new(1, "Send welcome email")));
    assert_eq!(task_queue.len(), 3);
    assert_eq!(task_queue.pop_front().unwrap().description, "Handle user login");
    assert_eq!(task_queue.pop_front().unwrap().description, "Process analytics data");
    assert_eq!(task_queue.pop_front().unwrap().description, "Send welcome email");
    assert!(task_queue.is_empty());
}

// Using Arc<T> (shared ownership)
{
    let mut task_queue = SLinkedList::<Arc<MyTask>, ()>::new();
    task_queue.push_back(Arc::new(MyTask::new(1, "Handle user login")));
    task_queue.push_back(Arc::new(MyTask::new(2, "Process analytics data")));
    task_queue.push_back(Arc::new(MyTask::new(1, "Send welcome email")));
    assert_eq!(task_queue.len(), 3);
    assert_eq!(task_queue.pop_front().unwrap().description, "Handle user login");
    assert_eq!(task_queue.pop_front().unwrap().description, "Process analytics data");
    assert_eq!(task_queue.pop_front().unwrap().description, "Send welcome email");
    assert!(task_queue.is_empty());
}

// Using NonNull<T> (raw pointers without ownership)
{
    let mut task_queue = SLinkedList::<NonNull<MyTask>, ()>::new();
    let task1 = Box::into_raw(Box::new(MyTask::new(1, "Handle user login")));
    let task2 = Box::into_raw(Box::new(MyTask::new(2, "Process analytics data")));
    let task3 = Box::into_raw(Box::new(MyTask::new(1, "Send welcome email")));
    task_queue.push_back(unsafe{NonNull::new_unchecked(task1)});
    task_queue.push_back(unsafe{NonNull::new_unchecked(task2)});
    task_queue.push_back(unsafe{NonNull::new_unchecked(task3)});
    assert_eq!(task_queue.len(), 3);
    assert_eq!(unsafe { &task_queue.pop_front().unwrap().as_ref().description }, "Handle user login");
    assert_eq!(unsafe { &task_queue.pop_front().unwrap().as_ref().description }, "Process analytics data");
    assert_eq!(unsafe { &task_queue.pop_front().unwrap().as_ref().description }, "Send welcome email");
    assert!(task_queue.is_empty());
    unsafe{
        let _ = Box::from_raw(task1);
        let _ = Box::from_raw(task2);
        let _ = Box::from_raw(task3);
    }
}

§Mixed Types

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

use embed_slist::{SLinkedList, SListItem, SListNode};
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<SListNode<()>>,
    v: usize,
}

struct BoxNode {
    _node: UnsafeCell<SListNode<()>>,
    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 SLinkedList");
    }

    /// # 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 SListItem<()> for MixedAddr {
     
    fn get_node(&self) -> &mut SListNode<()> {
        unreachable!();
    }

    unsafe fn get_node_from_ptr<'a>(p: *mut u8) -> &'a mut SListNode<()>
    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 = SLinkedList::<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§

Drainer
SLinkedList: A singly linked list with head and tail pointers (FIFO queue).
SLinkedListIter
SListNode: The node structure that must be embedded in items to be stored in a SLinkedList.

Traits§

SListItem: A trait to return internal mutable SListNode for specified list.

Type Aliases§

SLinkedListDrainer
SLinkedListIntoIter

Crate embed_slist

Crate embed_slist Copy item path

§Features

§Example

§Mixed Types

Structs§

Traits§

Type Aliases§

Crate embed_slist