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

embed_collections/
slist.rs
