embed_collections/
slist_owned.rs

1//! An owned intrusive singly linked list.
2
3//!
4//! This module provides `SLinkedListOwned`, a singly linked list for owned data (`Box<T>`).
5//! Elements are responsible for storing their own `next` pointer.
6//!
7//! It's optimized for FIFO (First-In, First-Out) queue-like behavior.
8//!
9//! # Features
10//! - O(1) push to back and pop from front.
11//! - Owned elements (`Box<T>`).
12//! - **Direct operation via SListItemOwned trait** (this feature is not in [crate::slist])
13//!
14//! # Example
15//! ```rust
16//! use embed_collections::slist_owned::{SLinkedListOwned, SListItemOwned};
17//! use core::ptr::NonNull;
18//!
19//! struct MyTask {
20//!     priority: u8,
21//!     description: String,
22//!     next: Option<NonNull<MyTask>>, // `next` pointer embedded directly
23//! }
24//! // because MyTask has a raw pointer
25//! unsafe impl Send for MyTask {}
26//!
27//! impl MyTask {
28//!     fn new(priority: u8, desc: &str) -> Self {
29//!         MyTask {
30//!             priority,
31//!             description: desc.to_string(),
32//!             next: None,
33//!         }
34//!     }
35//! }
36//!
37//! // Implement SListItemOwned to provide access to the `next` pointer.
38//! pub struct MyTaskTag;
39//! impl SListItemOwned<MyTaskTag> for MyTask {
40//!     fn get_node(&mut self) -> &mut Option<NonNull<Self>> {
41//!         &mut self.next
42//!     }
43//! }
44//!
45//! let mut task_queue = SLinkedListOwned::<MyTask, MyTaskTag>::new();
46//!
47//! task_queue.push_back(Box::new(MyTask::new(1, "Handle user login")));
48//! task_queue.push_back(Box::new(MyTask::new(2, "Process analytics data")));
49//! task_queue.push_back(Box::new(MyTask::new(1, "Send welcome email")));
50//!
51//! assert_eq!(task_queue.len(), 3);
52//!
53//! // Process tasks in FIFO order
54//! assert_eq!(task_queue.pop_front().unwrap().description, "Handle user login");
55//! assert_eq!(task_queue.pop_front().unwrap().description, "Process analytics data");
56//! assert_eq!(task_queue.pop_front().unwrap().description, "Send welcome email");
57//! assert!(task_queue.is_empty());
58//! ```
59//!
60//! # Using `SListItemOwned` Methods
61//!
62//! The `SListItemOwned` trait provides default methods like `append`, `pop`, and `consume_all`
63//! that allow direct manipulation of list nodes.
64//!
65//! The `Drop` implementation on an item should call `consume_all` to ensure that if a node
66//! is dropped, all subsequent nodes in the chain are also safely dropped, preventing memory leaks.
67//!
68//! ```rust
69//! use embed_collections::slist_owned::{SListItemOwned, SLinkedListOwned};
70//! use core::ptr::NonNull;
71//!
72//! // Define an item that can be part of the list
73//! struct MyTask {
74//!     description: String,
75//!     next: Option<NonNull<MyTask>>,
76//! }
77//!
78//! // because MyTask has a raw pointer
79//! unsafe impl Send for MyTask {}
80//!
81//! impl MyTask {
82//!     fn new(desc: &str) -> Self {
83//!         MyTask {
84//!             description: desc.to_string(),
85//!             next: None,
86//!         }
87//!     }
88//! }
89//!
90//! impl Drop for MyTask {
91//!     fn drop(&mut self) {
92//!         // Ensure subsequent nodes are dropped to prevent memory leaks.
93//!         SListItemOwned::consume_all(self);
94//!     }
95//! }
96//!
97//! impl SListItemOwned<()> for MyTask {
98//!     fn get_node(&mut self) -> &mut Option<NonNull<Self>> {
99//!         &mut self.next
100//!     }
101//! }
102//!
103//! // Create a base task node, which can act as the head of its own list.
104//! let mut base_task = Box::new(MyTask::new("Base task"));
105//!
106//! // Create another list to append.
107//! let mut sub_queue = SLinkedListOwned::<MyTask, ()>::new();
108//! sub_queue.push_back(Box::new(MyTask::new("Sub task 1")));
109//! sub_queue.push_back(Box::new(MyTask::new("Sub task 2")));
110//!
111//! // Use `append` to attach `sub_queue` after `base_task`.
112//!
113//! base_task.append(sub_queue);
114//!
115//! // The list is now: "Base task" -> "Sub task 1" -> "Sub task 2"
116//! let popped_task = base_task.pop();
117//! assert_eq!(popped_task.unwrap().description, "Sub task 1");
118//! let popped_task = base_task.pop();
119//! assert_eq!(popped_task.unwrap().description, "Sub task 2");
120//! assert!(base_task.pop().is_none());
121//! ```
122
123use alloc::boxed::Box;
124use core::marker::PhantomData;
125use core::ptr::NonNull;
126
127/// A trait for items that can be stored in an `SLinkedListOwned`.
128///
129/// The item must contain a field that stores an `Option<NonNull<Self>>`, which will be
130/// used as the `next` pointer in the linked list.
131///
132/// The tag is used to distinguish different list memberships within the same item.
133/// For a single list, you can use `()`.
134///
135/// # Safety
136/// Implementors must ensure `get_node` returns a mutable reference to the `Option<NonNull<Self>>`
137/// field that is designated for this linked list.
138pub trait SListItemOwned<Tag>: Sized {
139    /// Returns a mutable reference to the next-pointer field.
140    fn get_node(&mut self) -> &mut Option<NonNull<Self>>;
141
142    /// Appends a list after the current node. `self` must be a tail node.
143    /// The list `l` is consumed. The caller is responsible for updating the length
144    /// and tail of the list that contains `self`.
145    fn append(&mut self, mut l: SLinkedListOwned<Self, Tag>) {
146        let node = self.get_node();
147        assert!(node.is_none(), "can only append to a tail node");
148
149        *node = l.head.take();
150
151        // The list `l` is now empty, and we prevent its Drop implementation
152        // from deallocating the nodes we've just moved.
153        l.length = 0;
154        l.tail = None;
155    }
156
157    /// Pops the item immediately after this one.
158    ///
159    /// The list's length and tail must be updated manually if the popped item was the tail.
160    fn pop(&mut self) -> Option<Box<Self>> {
161        let node = self.get_node();
162        if let Some(next_ptr) = node {
163            let mut popped_box: Box<Self> = unsafe { Box::from_raw(next_ptr.as_ptr()) };
164            *node = popped_box.get_node().take(); // Ensure popped node's next is None
165            Some(popped_box)
166        } else {
167            None
168        }
169    }
170
171    /// Consumes and drops all nodes that follow the current one.
172    fn consume_all(&mut self) {
173        let mut current = self.get_node().take();
174        while let Some(node_ptr) = current {
175            let mut node_box: Box<Self> = unsafe { Box::from_raw(node_ptr.as_ptr()) };
176            current = node_box.get_node().take();
177            // node_box is dropped here.
178        }
179    }
180}
181
182/// An owned, intrusive singly linked list optimized for FIFO queues.
183///
184/// This list works with `Box<T>` and requires items to implement `SListItemOwned`.
185/// It provides O(1) push to back and pop from front.
186#[repr(C)]
187pub struct SLinkedListOwned<T, Tag>
188where
189    T: SListItemOwned<Tag>,
190{
191    length: usize,
192    head: Option<NonNull<T>>,
193    tail: Option<NonNull<T>>,
194    _phan: PhantomData<fn(&Tag)>,
195}
196
197unsafe impl<T, Tag> Send for SLinkedListOwned<T, Tag> where T: SListItemOwned<Tag> {}
198
199impl<T, Tag> SLinkedListOwned<T, Tag>
200where
201    T: SListItemOwned<Tag>,
202{
203    /// Creates a new, empty singly linked list.
204    #[inline(always)]
205    pub const fn new() -> Self {
206        SLinkedListOwned { length: 0, head: None, tail: None, _phan: PhantomData }
207    }
208
209    /// Clears the list, dropping all elements.
210    pub fn clear(&mut self) {
211        while self.pop_front().is_some() {}
212    }
213
214    /// Returns the length of the list as `usize`.
215    #[inline(always)]
216    pub fn len(&self) -> usize {
217        self.length
218    }
219
220    /// Returns `true` if the list contains no elements.
221    #[inline(always)]
222    pub fn is_empty(&self) -> bool {
223        self.length == 0
224    }
225
226    /// Prepends an element to the front of the list.
227    #[inline]
228    pub fn push_front(&mut self, mut item: Box<T>) {
229        debug_assert!(item.get_node().is_none(), "Node is already in a list");
230        // The new item's next pointer should point to the current head
231        *item.get_node() = self.head;
232        let ptr = NonNull::from(Box::leak(item));
233        self.head = Some(ptr); // New item becomes the head
234        if self.tail.is_none() {
235            // If the list was empty, the new item is also the tail
236            self.tail = Some(ptr);
237        }
238        self.length += 1;
239    }
240
241    /// Appends an element to the back of the list (FIFO: enqueue).
242    #[inline]
243    pub fn push_back(&mut self, mut item: Box<T>) {
244        // NOTE: it's owned list, should not reuse item.
245        // pop and drain should responsible to clear the item.pointer
246        debug_assert!(item.get_node().is_none(), "Node is already in a list");
247        let ptr = NonNull::from(Box::leak(item));
248        // The new ptr is the new tail.
249        // `replace` gives us the previous tail and updates it to the new one.
250        let old_tail = self.tail.replace(ptr);
251        match old_tail {
252            Some(mut old_tail_ptr) => {
253                // List was not empty, link old tail to new tail
254                unsafe {
255                    *old_tail_ptr.as_mut().get_node() = Some(ptr);
256                }
257            }
258            None => {
259                debug_assert!(self.head.is_none());
260                // List was empty, new node is also the head
261                self.head = Some(ptr);
262            }
263        }
264        self.length += 1;
265    }
266
267    /// Removes the first element and returns it (FIFO: dequeue).
268    pub fn pop_front(&mut self) -> Option<Box<T>> {
269        if let Some(head_ptr) = self.head {
270            let mut head_box: Box<T> = unsafe { Box::from_raw(head_ptr.as_ptr()) };
271            self.head = *head_box.get_node();
272
273            if self.head.is_none() {
274                self.tail = None;
275            }
276
277            self.length -= 1;
278
279            *head_box.get_node() = None;
280
281            Some(head_box)
282        } else {
283            None
284        }
285    }
286
287    /// Returns a reference to the front element.
288    #[inline]
289    pub fn get_front(&self) -> Option<&T> {
290        self.head.map(|ptr| unsafe { ptr.as_ref() })
291    }
292
293    /// Returns a mutable reference to the front element.
294    #[inline]
295    pub fn get_front_mut(&mut self) -> Option<&mut T> {
296        self.head.map(|mut ptr| unsafe { ptr.as_mut() })
297    }
298
299    /// Returns a reference to the back element.
300    #[inline]
301    pub fn get_back(&self) -> Option<&T> {
302        self.tail.map(|ptr| unsafe { ptr.as_ref() })
303    }
304
305    /// Returns a mutable reference to the back element.
306    #[inline]
307    pub fn get_back_mut(&mut self) -> Option<&mut T> {
308        self.tail.map(|mut ptr| unsafe { ptr.as_mut() })
309    }
310
311    /// Checks if the given node is the head of the list.
312    #[inline(always)]
313    pub fn is_front(&self, node: &T) -> bool {
314        self.head.is_some_and(|head| core::ptr::eq(head.as_ptr(), node))
315    }
316
317    /// Returns a draining iterator that removes items from the list.
318    #[inline(always)]
319    pub fn drain(&mut self) -> SLinkedListOwnedDrainer<'_, T, Tag> {
320        SLinkedListOwnedDrainer { list: self }
321    }
322
323    /// Returns a mutable iterator over the list.
324    #[inline(always)]
325    pub fn iter_mut(&mut self) -> SLinkedListOwnedIterMut<'_, T, Tag> {
326        SLinkedListOwnedIterMut { cur: self.head, _phan: PhantomData }
327    }
328}
329
330impl<T, Tag> Default for SLinkedListOwned<T, Tag>
331where
332    T: SListItemOwned<Tag>,
333{
334    fn default() -> Self {
335        Self::new()
336    }
337}
338
339impl<T, Tag> Drop for SLinkedListOwned<T, Tag>
340where
341    T: SListItemOwned<Tag>,
342{
343    fn drop(&mut self) {
344        // Drain the list to drop all elements.
345        self.drain().for_each(drop);
346    }
347}
348
349/// A draining iterator for `SLinkedListOwned`.
350pub struct SLinkedListOwnedDrainer<'a, T, Tag>
351where
352    T: SListItemOwned<Tag>,
353{
354    list: &'a mut SLinkedListOwned<T, Tag>,
355}
356
357impl<'a, T, Tag> Iterator for SLinkedListOwnedDrainer<'a, T, Tag>
358where
359    T: SListItemOwned<Tag>,
360{
361    type Item = Box<T>;
362
363    #[inline]
364    fn next(&mut self) -> Option<Box<T>> {
365        self.list.pop_front()
366    }
367}
368
369/// A mutable iterator for `SLinkedListOwned`.
370pub struct SLinkedListOwnedIterMut<'a, T, Tag>
371where
372    T: SListItemOwned<Tag>,
373{
374    cur: Option<NonNull<T>>,
375    _phan: PhantomData<(&'a mut T, fn(&Tag))>,
376}
377
378impl<'a, T, Tag> Iterator for SLinkedListOwnedIterMut<'a, T, Tag>
379where
380    T: SListItemOwned<Tag> + 'a,
381{
382    type Item = &'a mut T;
383
384    fn next(&mut self) -> Option<Self::Item> {
385        if let Some(mut cur_ptr) = self.cur {
386            let cur_mut = unsafe { cur_ptr.as_mut() };
387            self.cur = *cur_mut.get_node();
388            Some(cur_mut)
389        } else {
390            None
391        }
392    }
393}
394
395#[cfg(test)]
396mod tests {
397    use super::*;
398    use core::sync::atomic::{AtomicUsize, Ordering};
399
400    pub struct TestTag;
401
402    #[derive(Debug)]
403    pub struct TestNode {
404        pub value: i64,
405        pub next: Option<NonNull<TestNode>>,
406    }
407
408    static ACTIVE_NODE_COUNT: AtomicUsize = AtomicUsize::new(0);
409
410    impl Drop for TestNode {
411        fn drop(&mut self) {
412            ACTIVE_NODE_COUNT.fetch_sub(1, Ordering::SeqCst);
413        }
414    }
415
416    impl SListItemOwned<TestTag> for TestNode {
417        fn get_node(&mut self) -> &mut Option<NonNull<Self>> {
418            &mut self.next
419        }
420    }
421
422    fn new_node(v: i64) -> TestNode {
423        ACTIVE_NODE_COUNT.fetch_add(1, Ordering::SeqCst);
424        TestNode { value: v, next: None }
425    }
426
427    #[test]
428    fn test_push_back_pop_front() {
429        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
430        let mut l = SLinkedListOwned::<TestNode, TestTag>::new();
431
432        l.push_back(Box::new(new_node(1)));
433        l.push_back(Box::new(new_node(2)));
434        l.push_back(Box::new(new_node(3)));
435
436        assert_eq!(3, l.len());
437        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 3);
438        assert!(!l.is_empty());
439
440        assert_eq!(l.get_front().unwrap().value, 1);
441        assert_eq!(l.get_back().unwrap().value, 3);
442
443        let n1 = l.pop_front();
444        assert!(n1.is_some());
445        assert_eq!(n1.unwrap().value, 1);
446        assert_eq!(l.len(), 2);
447
448        let n2 = l.pop_front();
449        assert!(n2.is_some());
450        assert_eq!(n2.unwrap().value, 2);
451        assert_eq!(l.len(), 1);
452
453        let n3 = l.pop_front();
454        assert!(n3.is_some());
455        assert_eq!(n3.unwrap().value, 3);
456        assert_eq!(l.len(), 0);
457
458        assert!(l.pop_front().is_none());
459        assert!(l.is_empty());
460        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
461    }
462
463    #[test]
464    fn test_push_front() {
465        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
466        let mut l = SLinkedListOwned::<TestNode, TestTag>::new();
467
468        l.push_front(Box::new(new_node(1))); // List: [1]
469        assert_eq!(l.len(), 1);
470        assert_eq!(l.get_front().unwrap().value, 1);
471        assert_eq!(l.get_back().unwrap().value, 1);
472
473        l.push_front(Box::new(new_node(2))); // List: [2, 1]
474        assert_eq!(l.len(), 2);
475        assert_eq!(l.get_front().unwrap().value, 2);
476        assert_eq!(l.get_back().unwrap().value, 1);
477
478        l.push_front(Box::new(new_node(3))); // List: [3, 2, 1]
479        assert_eq!(l.len(), 3);
480        assert_eq!(l.get_front().unwrap().value, 3);
481        assert_eq!(l.get_back().unwrap().value, 1);
482
483        // Check order after pops
484        assert_eq!(l.pop_front().unwrap().value, 3);
485        assert_eq!(l.pop_front().unwrap().value, 2);
486        assert_eq!(l.pop_front().unwrap().value, 1);
487        assert!(l.is_empty());
488        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
489    }
490
491    #[test]
492    fn test_drain() {
493        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
494        let mut l = SLinkedListOwned::<TestNode, TestTag>::new();
495
496        l.push_back(Box::new(new_node(10)));
497        l.push_back(Box::new(new_node(20)));
498        l.push_back(Box::new(new_node(30)));
499
500        assert_eq!(l.len(), 3);
501        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 3);
502
503        {
504            let mut drain = l.drain();
505            assert_eq!(drain.next().unwrap().value, 10);
506            assert_eq!(drain.next().unwrap().value, 20);
507            assert_eq!(drain.next().unwrap().value, 30);
508            assert!(drain.next().is_none());
509        }
510
511        assert_eq!(l.len(), 0);
512        assert!(l.is_empty());
513        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
514    }
515
516    #[test]
517    fn test_iter_mut() {
518        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
519        let mut l = SLinkedListOwned::<TestNode, TestTag>::new();
520
521        l.push_back(Box::new(new_node(100)));
522        l.push_back(Box::new(new_node(200)));
523        l.push_back(Box::new(new_node(300)));
524
525        let mut iter = l.iter_mut();
526        let n1 = iter.next().unwrap();
527        assert_eq!(n1.value, 100);
528        n1.value = 101;
529
530        let n2 = iter.next().unwrap();
531        assert_eq!(n2.value, 200);
532        n2.value = 201;
533
534        let n3 = iter.next().unwrap();
535        assert_eq!(n3.value, 300);
536        n3.value = 301;
537
538        assert!(iter.next().is_none());
539
540        assert_eq!(l.pop_front().unwrap().value, 101);
541        assert_eq!(l.pop_front().unwrap().value, 201);
542        assert_eq!(l.pop_front().unwrap().value, 301);
543
544        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
545    }
546
547    #[test]
548    fn test_clear() {
549        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
550        let mut l = SLinkedListOwned::<TestNode, TestTag>::new();
551
552        l.push_back(Box::new(new_node(1)));
553        l.push_back(Box::new(new_node(2)));
554
555        assert_eq!(l.len(), 2);
556        l.clear();
557        assert!(l.is_empty());
558        assert_eq!(l.len(), 0);
559        assert!(l.get_front().is_none());
560        assert!(l.get_back().is_none());
561        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
562    }
563
564    #[test]
565    fn test_drop() {
566        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
567        {
568            let mut l = SLinkedListOwned::<TestNode, TestTag>::new();
569            l.push_back(Box::new(new_node(1)));
570            l.push_back(Box::new(new_node(2)));
571            assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
572        }
573        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
574    }
575}
embed_collections/slist_owned.rs

embed_collections/
slist_owned.rs
