embed_collections/
slist.rs

1//! An intrusive singly linked list implementation.
2//!
3//! This module provides `SLinkedList`, a singly linked list optimized for FIFO (First-In, First-Out)
4//! queue-like behavior. Elements embed the list nodes themselves, offering memory efficiency
5//! and explicit control over allocation.
6//!
7//! # Features
8//! - O(1) push to back and pop from front.
9//! - Generic over pointer types (`Box`, `Arc`, `NonNull`, raw pointers).
10//!
11//! # Example
12//! ```rust
13//! use embed_collections::{slist::{SLinkedList, SListItem, SListNode}, Pointer};
14//! use std::cell::UnsafeCell;
15//!
16//! struct MyTask {
17//!     priority: u8,
18//!     description: String,
19//!     node: UnsafeCell<SListNode<MyTask, ()>>, // Node embedded directly
20//! }
21//!
22//! impl MyTask {
23//!     fn new(priority: u8, desc: &str) -> Self {
24//!         MyTask {
25//!             priority,
26//!             description: desc.to_string(),
27//!             node: UnsafeCell::new(SListNode::default()),
28//!         }
29//!     }
30//! }
31//!
32//! // Safety: Implementors must ensure `get_node` returns a valid reference
33//! // to the embedded `SListNode`. `UnsafeCell` is used for interior mutability.
34//! unsafe impl SListItem<()> for MyTask {
35//!     fn get_node(&self) -> &mut SListNode<Self, ()> {
36//!         unsafe { &mut *self.node.get() }
37//!     }
38//! }
39//!
40//! let mut task_queue = SLinkedList::<Box<MyTask>, ()>::new();
41//!
42//! task_queue.push_back(Box::new(MyTask::new(1, "Handle user login")));
43//! task_queue.push_back(Box::new(MyTask::new(2, "Process analytics data")));
44//! task_queue.push_back(Box::new(MyTask::new(1, "Send welcome email")));
45//!
46//! assert_eq!(task_queue.len(), 3);
47//!
48//! // Process tasks in FIFO order
49//! assert_eq!(task_queue.pop_front().unwrap().description, "Handle user login");
50//! assert_eq!(task_queue.pop_front().unwrap().description, "Process analytics data");
51//! assert_eq!(task_queue.pop_front().unwrap().description, "Send welcome email");
52//! assert!(task_queue.is_empty());
53//! ```
54
55use crate::Pointer;
56use core::fmt;
57use core::marker::PhantomData;
58use core::mem;
59use core::ptr::null;
60
61/// A trait to return internal mutable SListNode for specified list.
62///
63/// The tag is used to distinguish different SListNodes within the same item.
64/// For only one ownership, you can use `()`.
65///
66/// # Safety
67/// Implementors must ensure `get_node` returns a valid reference to the `SListNode`
68/// embedded within `Self`. Users must use `UnsafeCell` to hold `SListNode` to support
69/// interior mutability required by list operations.
70pub unsafe trait SListItem<Tag>: Sized {
71    fn get_node(&self) -> &mut SListNode<Self, Tag>;
72}
73
74/// The node structure that must be embedded in items to be stored in a `SLinkedList`.
75///
76#[repr(C)]
77pub struct SListNode<T: Sized, Tag> {
78    next: *const T,
79    _phan: PhantomData<fn(&Tag)>,
80}
81
82unsafe impl<T, Tag> Send for SListNode<T, Tag> {}
83
84impl<T: SListItem<Tag>, Tag> SListNode<T, Tag> {}
85
86impl<T, Tag> Default for SListNode<T, Tag> {
87    #[inline(always)]
88    fn default() -> Self {
89        Self { next: null(), _phan: Default::default() }
90    }
91}
92
93impl<T: SListItem<Tag> + fmt::Debug, Tag> fmt::Debug for SListNode<T, Tag> {
94    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
95        write!(f, "(")?;
96        if !self.next.is_null() {
97            write!(f, "next: {:p} ", self.next)?;
98        } else {
99            write!(f, "next: none ")?;
100        }
101        write!(f, ")")
102    }
103}
104
105/// A singly linked list with head and tail pointers (FIFO queue).
106///
107/// Supports O(1) push to back and pop from front.
108#[repr(C)]
109pub struct SLinkedList<P, Tag>
110where
111    P: Pointer,
112    P::Target: SListItem<Tag>,
113{
114    length: u64,
115    head: *const P::Target,
116    tail: *const P::Target,
117    _phan: PhantomData<fn(&Tag)>,
118}
119
120unsafe impl<P, Tag> Send for SLinkedList<P, Tag>
121where
122    P: Pointer,
123    P::Target: SListItem<Tag>,
124{
125}
126
127impl<P: fmt::Debug, Tag> fmt::Debug for SLinkedList<P, Tag>
128where
129    P: Pointer,
130    P::Target: SListItem<Tag>,
131{
132    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
133        write!(f, "{{ length: {} ", self.length)?;
134        if !self.head.is_null() {
135            write!(f, "head: {:?} ", self.head)?;
136        } else {
137            write!(f, "head: none ")?;
138        }
139        if !self.tail.is_null() {
140            write!(f, "tail: {:?} ", self.tail)?;
141        } else {
142            write!(f, "tail: none ")?;
143        }
144        write!(f, "}}")
145    }
146}
147
148impl<P, Tag> SLinkedList<P, Tag>
149where
150    P: Pointer,
151    P::Target: SListItem<Tag>,
152{
153    /// Creates a new, empty singly linked list.
154    #[inline(always)]
155    pub fn new() -> Self {
156        SLinkedList { length: 0, head: null(), tail: null(), _phan: Default::default() }
157    }
158
159    /// Clears the list pointers. Note: This does NOT drop the elements.
160    /// Use `drain` or `drop` if you need to release owned resources.
161    #[inline]
162    pub fn clear(&mut self) {
163        self.length = 0;
164        self.head = null();
165        self.tail = null();
166    }
167
168    /// Returns the length of the list.
169    #[inline(always)]
170    pub fn get_length(&self) -> u64 {
171        return self.length;
172    }
173
174    /// Returns the length of the list as `usize`.
175    #[inline(always)]
176    pub fn len(&self) -> usize {
177        return self.length as usize;
178    }
179
180    /// Returns `true` if the list contains no elements.
181    #[inline(always)]
182    pub fn is_empty(&self) -> bool {
183        self.length == 0
184    }
185
186    /// Appends an element to the back of the list (FIFO: enqueue).
187    #[inline]
188    pub fn push_back(&mut self, item: P) {
189        let node = item.as_ref().get_node();
190        node.next = null();
191
192        let ptr = item.into_raw();
193
194        if self.tail.is_null() {
195            // List is empty
196            self.head = ptr;
197        } else {
198            // List is not empty, update current tail's next
199            unsafe {
200                (*self.tail).get_node().next = ptr;
201            }
202        }
203        self.tail = ptr;
204        self.length += 1;
205    }
206
207    /// Removes the first element and returns it (FIFO: dequeue).
208    pub fn pop_front(&mut self) -> Option<P> {
209        if self.head.is_null() {
210            None
211        } else {
212            let head_ptr = self.head;
213            let node = unsafe { (*head_ptr).get_node() };
214            let next_ptr = node.next;
215
216            // Update head to next
217            self.head = next_ptr;
218
219            // If head became null (list empty), update tail to null too
220            if self.head.is_null() {
221                self.tail = null();
222            }
223
224            // Clean up the removed node's next pointer
225            node.next = null();
226            self.length -= 1;
227
228            Some(unsafe { P::from_raw(head_ptr) })
229        }
230    }
231
232    /// Returns a reference to the front element.
233    #[inline]
234    pub fn get_front(&self) -> Option<&P::Target> {
235        if self.head.is_null() { None } else { unsafe { Some(&(*self.head)) } }
236    }
237
238    /// Returns a reference to the back element.
239    #[inline]
240    pub fn get_back(&self) -> Option<&P::Target> {
241        if self.tail.is_null() { None } else { unsafe { Some(&(*self.tail)) } }
242    }
243
244    /// Checks if the given node is the head of the list.
245    #[inline(always)]
246    pub fn is_front(&self, node: &P::Target) -> bool {
247        if self.head.is_null() { false } else { self.head == node as *const P::Target }
248    }
249
250    /// Returns an iterator over the list (borrowed).
251    ///
252    /// # NOTE
253    ///
254    /// If you plan on turn the raw pointer to owned, use drain instead
255    ///
256    /// # Safety
257    ///
258    /// The caller must ensure that the list is not modified in a way that can
259    /// invalidate internal pointers (such as removing elements or dropping
260    /// items) for the duration of the iterator's use.
261    #[inline(always)]
262    pub fn iter<'a>(&'a self) -> SLinkedListIterator<'a, P, Tag> {
263        SLinkedListIterator { list: self, cur: null() }
264    }
265
266    /// Returns a draining iterator that removes items from the list.
267    #[inline(always)]
268    pub fn drain<'a>(&'a mut self) -> SLinkedListDrainer<'a, P, Tag> {
269        SLinkedListDrainer { list: self }
270    }
271}
272
273impl<P, Tag> Drop for SLinkedList<P, Tag>
274where
275    P: Pointer,
276    P::Target: SListItem<Tag>,
277{
278    fn drop(&mut self) {
279        if mem::needs_drop::<P>() {
280            self.drain().for_each(drop);
281        }
282    }
283}
284
285pub struct SLinkedListIterator<'a, P, Tag>
286where
287    P: Pointer,
288    P::Target: SListItem<Tag>,
289{
290    list: &'a SLinkedList<P, Tag>,
291    cur: *const P::Target,
292}
293
294unsafe impl<'a, P, Tag> Send for SLinkedListIterator<'a, P, Tag>
295where
296    P: Pointer,
297    P::Target: SListItem<Tag>,
298{
299}
300
301impl<'a, P, Tag> Iterator for SLinkedListIterator<'a, P, Tag>
302where
303    P: Pointer,
304    P::Target: SListItem<Tag>,
305{
306    type Item = &'a P::Target;
307
308    fn next(&mut self) -> Option<Self::Item> {
309        if self.cur.is_null() {
310            if self.list.head.is_null() {
311                return None;
312            } else {
313                self.cur = self.list.head;
314            }
315        } else {
316            let next = unsafe { (*self.cur).get_node().next };
317            if next.is_null() {
318                return None;
319            } else {
320                self.cur = next;
321            }
322        }
323        unsafe { Some(&(*self.cur)) }
324    }
325}
326
327pub struct SLinkedListDrainer<'a, P, Tag>
328where
329    P: Pointer,
330    P::Target: SListItem<Tag>,
331{
332    list: &'a mut SLinkedList<P, Tag>,
333}
334
335unsafe impl<'a, P, Tag> Send for SLinkedListDrainer<'a, P, Tag>
336where
337    P: Pointer,
338    P::Target: SListItem<Tag>,
339{
340}
341
342impl<'a, P, Tag> Iterator for SLinkedListDrainer<'a, P, Tag>
343where
344    P: Pointer,
345    P::Target: SListItem<Tag>,
346{
347    type Item = P;
348
349    #[inline]
350    fn next(&mut self) -> Option<P> {
351        self.list.pop_front()
352    }
353}
354
355#[cfg(test)]
356mod tests {
357    use super::*;
358    use std::cell::UnsafeCell;
359    use std::sync::atomic::{AtomicUsize, Ordering};
360
361    pub struct TestTag;
362
363    #[derive(Debug)]
364    pub struct TestNode {
365        pub value: i64,
366        pub node: UnsafeCell<SListNode<Self, TestTag>>,
367    }
368
369    static ACTIVE_NODE_COUNT: AtomicUsize = AtomicUsize::new(0);
370
371    impl Drop for TestNode {
372        fn drop(&mut self) {
373            ACTIVE_NODE_COUNT.fetch_sub(1, Ordering::SeqCst);
374        }
375    }
376
377    unsafe impl Send for TestNode {}
378
379    unsafe impl SListItem<TestTag> for TestNode {
380        fn get_node(&self) -> &mut SListNode<Self, TestTag> {
381            unsafe { &mut *self.node.get() }
382        }
383    }
384
385    fn new_node(v: i64) -> TestNode {
386        ACTIVE_NODE_COUNT.fetch_add(1, Ordering::SeqCst);
387        TestNode { value: v, node: UnsafeCell::new(SListNode::default()) }
388    }
389
390    #[test]
391    fn test_push_back_pop_front_box() {
392        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
393        let mut l = SLinkedList::<Box<TestNode>, TestTag>::new();
394
395        let node1 = Box::new(new_node(1));
396        l.push_back(node1);
397
398        let node2 = Box::new(new_node(2));
399        l.push_back(node2);
400
401        let node3 = Box::new(new_node(3));
402        l.push_back(node3);
403
404        assert_eq!(3, l.get_length());
405        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 3);
406
407        // Test iterator
408        let mut iter = l.iter();
409        assert_eq!(iter.next().unwrap().value, 1);
410        assert_eq!(iter.next().unwrap().value, 2);
411        assert_eq!(iter.next().unwrap().value, 3);
412        assert!(iter.next().is_none());
413
414        // Test pop_front (FIFO)
415        let n1 = l.pop_front();
416        assert!(n1.is_some());
417        assert_eq!(n1.unwrap().value, 1);
418        assert_eq!(l.get_length(), 2);
419
420        let n2 = l.pop_front();
421        assert!(n2.is_some());
422        assert_eq!(n2.unwrap().value, 2);
423        assert_eq!(l.get_length(), 1);
424
425        let n3 = l.pop_front();
426        assert!(n3.is_some());
427        assert_eq!(n3.unwrap().value, 3);
428        assert_eq!(l.get_length(), 0);
429
430        assert!(l.pop_front().is_none());
431        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
432    }
433
434    #[test]
435    fn test_drain() {
436        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
437        let mut l = SLinkedList::<Box<TestNode>, TestTag>::new();
438
439        l.push_back(Box::new(new_node(10)));
440        l.push_back(Box::new(new_node(20)));
441        l.push_back(Box::new(new_node(30)));
442
443        assert_eq!(l.get_length(), 3);
444        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 3);
445
446        {
447            let mut drain = l.drain();
448            assert_eq!(drain.next().unwrap().value, 10);
449            assert_eq!(drain.next().unwrap().value, 20);
450            assert_eq!(drain.next().unwrap().value, 30);
451            assert!(drain.next().is_none());
452        }
453
454        assert_eq!(l.get_length(), 0);
455        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
456    }
457}
embed_collections/slist.rs

embed_collections/
slist.rs
