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

embed_collections/
slist.rs
