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, dropping all of its elements if the pointer type `P` owns them.
160    #[inline]
161    pub fn clear(&mut self) {
162        // By repeatedly popping from the front, we drop each element.
163        // If P is an owned pointer (like Box), the element is dropped.
164        // If P is a raw pointer, it's a no-op, but the list is still emptied.
165        while self.pop_front().is_some() {}
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        let ptr = item.into_raw();
192        if self.tail.is_null() {
193            // List is empty
194            self.head = ptr;
195        } else {
196            // List is not empty, update current tail's next
197            unsafe {
198                (*self.tail).get_node().next = ptr;
199            }
200        }
201        self.tail = ptr;
202        self.length += 1;
203    }
204
205    /// Pushes an element to the front of the list.
206    #[inline]
207    pub fn push_front(&mut self, item: P) {
208        let ptr = item.into_raw();
209        let node = unsafe { (*ptr).get_node() };
210        node.next = self.head;
211        if self.head.is_null() {
212            // List was empty
213            self.tail = ptr;
214        }
215        self.head = ptr;
216        self.length += 1;
217    }
218
219    /// Removes the first element and returns it (FIFO: dequeue).
220    pub fn pop_front(&mut self) -> Option<P> {
221        if self.head.is_null() {
222            None
223        } else {
224            let head_ptr = self.head;
225            let node = unsafe { (*head_ptr).get_node() };
226            let next_ptr = node.next;
227
228            // Update head to next
229            self.head = next_ptr;
230
231            // If head became null (list empty), update tail to null too
232            if self.head.is_null() {
233                self.tail = null();
234            }
235
236            // Clean up the removed node's next pointer
237            node.next = null();
238            self.length -= 1;
239
240            Some(unsafe { P::from_raw(head_ptr) })
241        }
242    }
243
244    /// Returns a reference to the front element.
245    #[inline]
246    pub fn get_front(&self) -> Option<&P::Target> {
247        if self.head.is_null() { None } else { unsafe { Some(&(*self.head)) } }
248    }
249
250    /// Returns a reference to the back element.
251    #[inline]
252    pub fn get_back(&self) -> Option<&P::Target> {
253        if self.tail.is_null() { None } else { unsafe { Some(&(*self.tail)) } }
254    }
255
256    /// Checks if the given node is the head of the list.
257    #[inline(always)]
258    pub fn is_front(&self, node: &P::Target) -> bool {
259        if self.head.is_null() { false } else { self.head == node as *const P::Target }
260    }
261
262    /// Returns an iterator over the list (borrowed).
263    ///
264    /// # NOTE
265    ///
266    /// If you plan on turn the raw pointer to owned, use drain instead
267    ///
268    /// # Safety
269    ///
270    /// The caller must ensure that the list is not modified in a way that can
271    /// invalidate internal pointers (such as removing elements or dropping
272    /// items) for the duration of the iterator's use.
273    #[inline(always)]
274    pub fn iter<'a>(&'a self) -> SLinkedListIterator<'a, P, Tag> {
275        SLinkedListIterator { list: self, cur: null() }
276    }
277
278    /// Returns a draining iterator that removes items from the list.
279    #[inline(always)]
280    pub fn drain<'a>(&'a mut self) -> SLinkedListDrainer<'a, P, Tag> {
281        SLinkedListDrainer { list: self }
282    }
283}
284
285impl<P, Tag> Drop for SLinkedList<P, Tag>
286where
287    P: Pointer,
288    P::Target: SListItem<Tag>,
289{
290    fn drop(&mut self) {
291        if mem::needs_drop::<P>() {
292            self.drain().for_each(drop);
293        }
294    }
295}
296
297pub struct SLinkedListIterator<'a, P, Tag>
298where
299    P: Pointer,
300    P::Target: SListItem<Tag>,
301{
302    list: &'a SLinkedList<P, Tag>,
303    cur: *const P::Target,
304}
305
306unsafe impl<'a, P, Tag> Send for SLinkedListIterator<'a, P, Tag>
307where
308    P: Pointer,
309    P::Target: SListItem<Tag>,
310{
311}
312
313impl<'a, P, Tag> Iterator for SLinkedListIterator<'a, P, Tag>
314where
315    P: Pointer,
316    P::Target: SListItem<Tag>,
317{
318    type Item = &'a P::Target;
319
320    fn next(&mut self) -> Option<Self::Item> {
321        if self.cur.is_null() {
322            if self.list.head.is_null() {
323                return None;
324            } else {
325                self.cur = self.list.head;
326            }
327        } else {
328            let next = unsafe { (*self.cur).get_node().next };
329            if next.is_null() {
330                return None;
331            } else {
332                self.cur = next;
333            }
334        }
335        unsafe { Some(&(*self.cur)) }
336    }
337}
338
339pub struct SLinkedListDrainer<'a, P, Tag>
340where
341    P: Pointer,
342    P::Target: SListItem<Tag>,
343{
344    list: &'a mut SLinkedList<P, Tag>,
345}
346
347unsafe impl<'a, P, Tag> Send for SLinkedListDrainer<'a, P, Tag>
348where
349    P: Pointer,
350    P::Target: SListItem<Tag>,
351{
352}
353
354impl<'a, P, Tag> Iterator for SLinkedListDrainer<'a, P, Tag>
355where
356    P: Pointer,
357    P::Target: SListItem<Tag>,
358{
359    type Item = P;
360
361    #[inline]
362    fn next(&mut self) -> Option<P> {
363        self.list.pop_front()
364    }
365}
366
367#[cfg(test)]
368mod tests {
369    use super::*;
370    use std::cell::UnsafeCell;
371    use std::sync::atomic::{AtomicUsize, Ordering};
372
373    pub struct TestTag;
374
375    #[derive(Debug)]
376    pub struct TestNode {
377        pub value: i64,
378        pub node: UnsafeCell<SListNode<Self, TestTag>>,
379    }
380
381    static ACTIVE_NODE_COUNT: AtomicUsize = AtomicUsize::new(0);
382
383    impl Drop for TestNode {
384        fn drop(&mut self) {
385            ACTIVE_NODE_COUNT.fetch_sub(1, Ordering::SeqCst);
386        }
387    }
388
389    unsafe impl Send for TestNode {}
390
391    unsafe impl SListItem<TestTag> for TestNode {
392        fn get_node(&self) -> &mut SListNode<Self, TestTag> {
393            unsafe { &mut *self.node.get() }
394        }
395    }
396
397    fn new_node(v: i64) -> TestNode {
398        ACTIVE_NODE_COUNT.fetch_add(1, Ordering::SeqCst);
399        TestNode { value: v, node: UnsafeCell::new(SListNode::default()) }
400    }
401
402    #[test]
403    fn test_push_back_pop_front_box() {
404        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
405        let mut l = SLinkedList::<Box<TestNode>, TestTag>::new();
406
407        let node1 = Box::new(new_node(1));
408        l.push_back(node1);
409
410        let node2 = Box::new(new_node(2));
411        l.push_back(node2);
412
413        let node3 = Box::new(new_node(3));
414        l.push_back(node3);
415
416        assert_eq!(3, l.get_length());
417        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 3);
418
419        // Test iterator
420        let mut iter = l.iter();
421        assert_eq!(iter.next().unwrap().value, 1);
422        assert_eq!(iter.next().unwrap().value, 2);
423        assert_eq!(iter.next().unwrap().value, 3);
424        assert!(iter.next().is_none());
425
426        // Test pop_front (FIFO)
427        let n1 = l.pop_front();
428        assert!(n1.is_some());
429        assert_eq!(n1.unwrap().value, 1);
430        assert_eq!(l.get_length(), 2);
431
432        let n2 = l.pop_front();
433        assert!(n2.is_some());
434        assert_eq!(n2.unwrap().value, 2);
435        assert_eq!(l.get_length(), 1);
436
437        let n3 = l.pop_front();
438        assert!(n3.is_some());
439        assert_eq!(n3.unwrap().value, 3);
440        assert_eq!(l.get_length(), 0);
441
442        assert!(l.pop_front().is_none());
443        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
444    }
445
446    #[test]
447    fn test_push_front_box() {
448        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
449        let mut l = SLinkedList::<Box<TestNode>, TestTag>::new();
450
451        let node1 = Box::new(new_node(1));
452        l.push_front(node1); // List: [1]
453
454        let node2 = Box::new(new_node(2));
455        l.push_front(node2); // List: [2, 1]
456
457        let node3 = Box::new(new_node(3));
458        l.push_front(node3); // List: [3, 2, 1]
459
460        assert_eq!(3, l.get_length());
461        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 3);
462
463        // Test iterator (should be 3, 2, 1)
464        let mut iter = l.iter();
465        assert_eq!(iter.next().unwrap().value, 3);
466        assert_eq!(iter.next().unwrap().value, 2);
467        assert_eq!(iter.next().unwrap().value, 1);
468        assert!(iter.next().is_none());
469
470        // Test pop_front (FIFO)
471        let n1 = l.pop_front();
472        assert!(n1.is_some());
473        assert_eq!(n1.unwrap().value, 3);
474        assert_eq!(l.get_length(), 2);
475
476        let n2 = l.pop_front();
477        assert!(n2.is_some());
478        assert_eq!(n2.unwrap().value, 2);
479        assert_eq!(l.get_length(), 1);
480
481        let n3 = l.pop_front();
482        assert!(n3.is_some());
483        assert_eq!(n3.unwrap().value, 1);
484        assert_eq!(l.get_length(), 0);
485
486        assert!(l.pop_front().is_none());
487        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
488    }
489
490    #[test]
491    fn test_drain() {
492        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
493        let mut l = SLinkedList::<Box<TestNode>, TestTag>::new();
494
495        l.push_back(Box::new(new_node(10)));
496        l.push_back(Box::new(new_node(20)));
497        l.push_back(Box::new(new_node(30)));
498
499        assert_eq!(l.get_length(), 3);
500        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 3);
501
502        {
503            let mut drain = l.drain();
504            assert_eq!(drain.next().unwrap().value, 10);
505            assert_eq!(drain.next().unwrap().value, 20);
506            assert_eq!(drain.next().unwrap().value, 30);
507            assert!(drain.next().is_none());
508        }
509
510        assert_eq!(l.get_length(), 0);
511        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
512    }
513
514    #[test]
515    fn test_clear() {
516        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
517        let mut l = SLinkedList::<Box<TestNode>, TestTag>::new();
518
519        l.push_back(Box::new(new_node(1)));
520        l.push_back(Box::new(new_node(2)));
521        assert_eq!(l.len(), 2);
522        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
523
524        l.clear();
525
526        assert!(l.is_empty());
527        assert_eq!(l.len(), 0);
528        assert!(l.get_front().is_none());
529        assert!(l.get_back().is_none());
530        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
531
532        // Can still push to the list
533        l.push_back(Box::new(new_node(3)));
534        assert_eq!(l.len(), 1);
535        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 1);
536    }
537}
embed_collections/slist.rs

embed_collections/
slist.rs
