fbl/
singly_linked_list.rs

1// Copyright 2026 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use crate::ptr_traits::{ManagedPtr, PtrTraits};
6use crate::size_tracker::{NonTrackingSize, SizeTracker, TrackingSize};
7use crate::tag::DefaultObjectTag;
8use core::cell::UnsafeCell;
9
10/// A node in a singly linked list.
11#[repr(C)]
12pub struct SinglyLinkedListNode<T> {
13    /// The next element in the list.
14    /// This is null if the node is not in a container.
15    /// This is a sentinel value (1) if the node is the last element of the list.
16    pub next: UnsafeCell<*mut T>,
17}
18
19impl<T> SinglyLinkedListNode<T> {
20    /// Creates a new, unlinked node.
21    pub const fn new() -> Self {
22        Self { next: UnsafeCell::new(core::ptr::null_mut()) }
23    }
24
25    /// Returns true if the node is currently in a list.
26    pub fn in_container(&self) -> bool {
27        // SAFETY: `self.next.get()` returns a valid pointer to the inner field of `self.next`
28        // which is a validly allocated UnsafeCell inside `self`.
29        !unsafe { *self.next.get() }.is_null()
30    }
31
32    fn get_next(&self) -> *mut T {
33        // SAFETY: `self.next.get()` is a valid pointer to `self.next` which is owned by `self`.
34        unsafe { *self.next.get() }
35    }
36
37    fn set_next(&self, next: *mut T) {
38        // SAFETY: `self.next.get()` is a valid, writable pointer to `self.next` owned by `self`.
39        // UnsafeCell allows interior mutability through a shared reference.
40        unsafe {
41            *self.next.get() = next;
42        }
43    }
44}
45
46impl<T> core::fmt::Debug for SinglyLinkedListNode<T> {
47    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
48        f.debug_struct("SinglyLinkedListNode").field("in_container", &self.in_container()).finish()
49    }
50}
51
52impl<T> Default for SinglyLinkedListNode<T> {
53    fn default() -> Self {
54        Self::new()
55    }
56}
57
58impl<T> Drop for SinglyLinkedListNode<T> {
59    fn drop(&mut self) {
60        debug_assert!(!self.in_container(), "Object destroyed while still in container");
61    }
62}
63
64/// Trait that types must implement to be contained in a `SinglyLinkedList`.
65///
66/// The `Tag` parameter is used to support objects participating in multiple
67/// lists simultaneously. By implementing this trait multiple times with different
68/// tags, an object can provide different `SinglyLinkedListNode` instances for
69/// each list it belongs to.
70pub trait SinglyLinkedListContainable<T, Tag = DefaultObjectTag> {
71    /// Returns a reference to the list node.
72    fn get_node(&self) -> &SinglyLinkedListNode<T>;
73}
74
75/// A singly linked list that supports intrusive nodes and different ownership semantics.
76///
77/// `SinglyLinkedList` is a layout-compatible analog to `fbl::SinglyLinkedList` in C++.
78/// It allows managing singly linked lists of objects where the bookkeeping storage
79/// (the node state) exists on the objects themselves, eliminating the need for
80/// runtime allocation/deallocation to add or remove members.
81///
82/// The list stores pointers to the objects, and is parametrized by the pointer type `P`.
83/// Supported pointer types are:
84/// 1. `*mut T` : Raw unmanaged pointers.
85/// 2. [`UniquePtr<T>`] : Unique managed pointers.
86/// 3. [`RefPtr<T>`] : Managed pointers to ref-counted objects.
87///
88/// ### Ownership
89/// - Lists of managed pointer types ([`UniquePtr`], [`RefPtr`]) hold references to objects
90///   and follow the rules of the particular managed pointer patterns. Destroying or
91///   clearing a list of managed pointers will release the references to the objects.
92/// - Lists of unmanaged pointer types (`*mut T`) perform no lifecycle management.
93///   It is up to the user to make sure that lifecycles are managed properly.
94///   As an added safety, a list of unmanaged pointers will assert if it is
95///   destroyed with elements still in it.
96///
97/// ### Multiple Lists
98/// Objects may exist in multiple lists simultaneously through the use of custom
99/// trait tags. See [`SinglyLinkedListContainable`] for more details.
100///
101/// ### Examples
102///
103/// #### Example 1: A simple list of unmanaged pointers to Foo objects
104///
105/// ```rust
106/// use fbl::{SinglyLinkedList, SinglyLinkedListNode, SinglyLinkedListContainable};
107///
108/// #[derive(SinglyLinkedListContainable)]
109/// struct Foo {
110///     value: i32,
111///     #[sll_node]
112///     node: SinglyLinkedListNode<Foo>,
113/// }
114///
115/// impl Foo {
116///     fn new(value: i32) -> Self {
117///         Self { value, node: SinglyLinkedListNode::new() }
118///     }
119/// }
120///
121/// fn test() {
122///     let mut list = SinglyLinkedList::<*mut Foo>::new();
123///
124///     let mut foo1 = Foo::new(1);
125///     let mut foo2 = Foo::new(2);
126///
127///     unsafe {
128///         list.push_front_raw(&mut foo1);
129///         list.push_front_raw(&mut foo2);
130///     }
131///
132///     for foo in list.iter() {
133///         println!("Value: {}", foo.value);
134///     }
135///
136///     list.clear(); // Must clear before going out of scope if using raw pointers!
137/// }
138/// ```
139///
140/// #### Example 2: A simple list of unique pointers to Foo objects
141///
142/// ```rust
143/// use fbl::{SinglyLinkedList, SinglyLinkedListNode, SinglyLinkedListContainable, UniquePtr};
144///
145/// #[derive(fbl::Recyclable, SinglyLinkedListContainable)]
146/// struct Foo {
147///     value: i32,
148///     #[sll_node]
149///     node: SinglyLinkedListNode<Foo>,
150/// }
151///
152/// impl Foo {
153///     fn new(value: i32) -> Self {
154///         Self { value, node: SinglyLinkedListNode::new() }
155///     }
156/// }
157///
158/// fn test() {
159///     let mut list = SinglyLinkedList::<UniquePtr<Foo>>::new();
160///
161///     let foo1 = UniquePtr::try_new(Foo::new(1)).unwrap();
162///     let foo2 = UniquePtr::try_new(Foo::new(2)).unwrap();
163///
164///     list.push_front(foo1);
165///     list.push_front(foo2);
166///
167///     for foo in list.iter() {
168///         println!("Value: {}", foo.value);
169///     }
170///
171///     // List drops here and cleans up objects automatically!
172/// }
173/// ```
174///
175/// #### Example 3: An object in multiple lists
176///
177/// ```rust
178/// use fbl::{SinglyLinkedList, SinglyLinkedListNode, SinglyLinkedListContainable};
179///
180/// struct Tag2;
181///
182/// #[derive(SinglyLinkedListContainable)]
183/// struct Foo {
184///     value: i32,
185///     #[sll_node]
186///     node1: SinglyLinkedListNode<Foo>,
187///     #[sll_node(tag = Tag2)]
188///     node2: SinglyLinkedListNode<Foo>,
189/// }
190///
191/// fn test() {
192///     let mut list1 = SinglyLinkedList::<*mut Foo>::new();
193///     let mut list2 = SinglyLinkedList::<*mut Foo, Tag2>::new();
194///
195///     let mut foo = Foo {
196///         value: 42,
197///         node1: SinglyLinkedListNode::new(),
198///         node2: SinglyLinkedListNode::new(),
199///     };
200///
201///     unsafe {
202///         list1.push_front_raw(&mut foo);
203///         list2.push_front_raw(&mut foo);
204///     }
205///
206///     // ... access via both lists ...
207///
208///     list1.clear();
209///     list2.clear();
210/// }
211/// ```
212#[repr(C)]
213pub struct SinglyLinkedList<P, Tag = DefaultObjectTag, S = NonTrackingSize>
214where
215    P: PtrTraits,
216    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
217    S: SizeTracker,
218{
219    head: *mut P::Target,
220    size: S,
221    _phantom: core::marker::PhantomData<(P, Tag)>,
222}
223
224impl<P, Tag, S> SinglyLinkedList<P, Tag, S>
225where
226    P: PtrTraits,
227    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
228    S: SizeTracker,
229{
230    /// Creates a new, empty list.
231    pub const fn new() -> Self {
232        Self {
233            head: crate::make_sentinel_null(),
234            size: S::INIT,
235            _phantom: core::marker::PhantomData,
236        }
237    }
238
239    /// # Safety
240    ///
241    /// The caller must ensure that `ptr` is a valid, aligned, and dereferenceable pointer
242    /// to an initialized `P::Target` object that is alive for `'a`.
243    unsafe fn get_node_ref<'a>(&self, ptr: *mut P::Target) -> &'a SinglyLinkedListNode<P::Target> {
244        let _ = self;
245        // SAFETY: The caller guarantees `ptr` is valid, aligned, and dereferenceable.
246        unsafe { &(*ptr) }.get_node()
247    }
248
249    /// Returns true if the list is empty.
250    pub fn is_empty(&self) -> bool {
251        crate::is_sentinel_ptr(self.head)
252    }
253
254    /// Returns a reference to the first element of the list, or `None` if it is empty.
255    pub fn front(&self) -> Option<&P::Target> {
256        if self.is_empty() {
257            None
258        } else {
259            // SAFETY: The list is not empty, so `self.head` is a valid pointer to an element.
260            unsafe { Some(&*self.head) }
261        }
262    }
263
264    /// Returns a mutable reference to the first element of the list, or `None` if it is empty.
265    pub fn front_mut(&mut self) -> Option<&mut P::Target> {
266        if self.is_empty() {
267            None
268        } else {
269            // SAFETY: The list is not empty, so `self.head` is a valid pointer to an element.
270            // We have `&mut self`, ensuring exclusive access.
271            unsafe { Some(&mut *self.head) }
272        }
273    }
274
275    /// Pushes an element to the front of the list.
276    ///
277    /// # Panics
278    ///
279    /// Panics if the object is already in a container.
280    pub fn push_front(&mut self, ptr: P)
281    where
282        P: ManagedPtr,
283    {
284        // SAFETY: `P` is a `ManagedPtr`, which guarantees that the pointer is valid and that the
285        // object will outlive its reference from this list.
286        unsafe { self.push_front_raw(ptr) }
287    }
288
289    /// Pushes an element to the front of the list.
290    ///
291    /// For managed pointers, use the safe [`push_front`] instead.
292    ///
293    /// # Panics
294    ///
295    /// Panics if the object is already in a container.
296    ///
297    /// # Safety
298    ///
299    /// The caller must ensure that `ptr` is a valid pointer to a `T` and that the object outlives
300    /// the reference from the list.
301    pub unsafe fn push_front_raw(&mut self, ptr: P) {
302        let raw = P::into_raw(ptr);
303        debug_assert!(!raw.is_null());
304        // SAFETY: `raw` is a valid pointer provided by caller.
305        let node = unsafe { self.get_node_ref(raw) };
306        assert!(!node.in_container());
307
308        node.set_next(self.head);
309        self.head = raw;
310        self.size.increment();
311    }
312
313    /// Removes and returns the first element of the list, or `None` if it is empty.
314    pub fn pop_front(&mut self) -> Option<P> {
315        if self.is_empty() {
316            return None;
317        }
318
319        let ptr = self.head;
320        self.size.decrement();
321
322        // SAFETY: `ptr` was `self.head` which is valid since list is not empty.
323        let node = unsafe { self.get_node_ref(ptr) };
324
325        self.head = node.get_next();
326        node.set_next(core::ptr::null_mut());
327
328        // SAFETY: `ptr` was popped, safe to reconstruct.
329        Some(unsafe { P::from_raw(ptr) })
330    }
331
332    /// Removes all elements from the list.
333    pub fn clear(&mut self) {
334        while self.pop_front().is_some() {}
335    }
336
337    /// Inserts an element after the specified position.
338    ///
339    /// For managed pointers, consider using [`CursorMut::insert_after`] for a safer alternative.
340    ///
341    /// # Safety
342    ///
343    /// The caller must ensure that `pos` is a valid pointer to an element in this list,
344    /// and that `ptr` is a valid pointer to an element not currently in any container.
345    pub unsafe fn insert_after_raw(&mut self, pos: *mut P::Target, ptr: P) {
346        debug_assert!(!pos.is_null());
347        let raw = P::into_raw(ptr);
348        debug_assert!(!raw.is_null());
349        // SAFETY: `raw` is valid.
350        let node = unsafe { self.get_node_ref(raw) };
351        debug_assert!(!node.in_container());
352
353        // SAFETY: `pos` is valid.
354        let pos_node = unsafe { self.get_node_ref(pos) };
355        node.set_next(pos_node.get_next());
356        pos_node.set_next(raw);
357        self.size.increment();
358    }
359
360    /// Erases the element after the specified position.
361    ///
362    /// For managed pointers, consider using [`CursorMut::erase_next`] for a safer alternative.
363    ///
364    /// # Safety
365    ///
366    /// The caller must ensure that `pos` is a valid pointer to an element in this list.
367    pub unsafe fn erase_next_raw(&mut self, pos: *mut P::Target) -> Option<P> {
368        debug_assert!(!pos.is_null());
369        // SAFETY: `pos` is valid.
370        let pos_node = unsafe { self.get_node_ref(pos) };
371        let next_ptr = pos_node.get_next();
372        if crate::is_sentinel_ptr(next_ptr) {
373            return None;
374        }
375        // SAFETY: `next_ptr` is valid.
376        let next_node = unsafe { self.get_node_ref(next_ptr) };
377        pos_node.set_next(next_node.get_next());
378        next_node.set_next(core::ptr::null_mut());
379        self.size.decrement();
380        // SAFETY: `next_ptr` was erased, safe to reconstruct.
381        Some(unsafe { P::from_raw(next_ptr) })
382    }
383
384    /// Swaps the contents of this list with another list.
385    pub fn swap(&mut self, other: &mut Self) {
386        core::mem::swap(&mut self.head, &mut other.head);
387        self.size.swap(&mut other.size);
388    }
389
390    /// Finds the first element matching the predicate, removes it from the list,
391    /// and returns it. Returns `None` if no element matches.
392    pub fn erase_if<F>(&mut self, mut f: F) -> Option<P>
393    where
394        F: FnMut(&P::Target) -> bool,
395    {
396        // Step 1: Check if head matches.
397        if let Some(head_ref) = self.front()
398            && f(head_ref)
399        {
400            return self.pop_front();
401        }
402
403        if self.is_empty() {
404            return None;
405        }
406
407        // Step 2: Use a cursor to check subsequent elements.
408        let mut cursor = self.cursor_mut();
409        while let Some(next_ref) = cursor.get_next() {
410            if f(next_ref) {
411                return cursor.erase_next();
412            }
413            cursor.move_next();
414        }
415
416        None
417    }
418
419    /// Replaces the first element matching the predicate with `value`. Returns the replaced
420    /// element.
421    ///
422    /// # Panics
423    ///
424    /// Panics if the object is already in a container.
425    pub fn replace_if<F>(&mut self, f: F, value: P) -> Option<P>
426    where
427        F: FnMut(&P::Target) -> bool,
428        P: ManagedPtr,
429    {
430        unsafe { self.replace_if_raw(f, value) }
431    }
432
433    /// Replaces the first element matching the predicate with `value`. Returns the replaced
434    /// element.
435    ///
436    /// # Panics
437    ///
438    /// Panics if the object is already in a container.
439    ///
440    /// # Safety
441    ///
442    /// The caller must ensure that `value` is a valid pointer to a `T` and that the object outlives
443    /// the reference from the list.
444    pub unsafe fn replace_if_raw<F>(&mut self, mut f: F, value: P) -> Option<P>
445    where
446        F: FnMut(&P::Target) -> bool,
447    {
448        // Step 1: Handle matching elements at the head.
449        if let Some(head_ref) = self.front()
450            && f(head_ref)
451        {
452            let old_head = self.pop_front().unwrap();
453            // SAFETY: `value` is a valid pointer that will outlive its reference from this
454            // list.
455            unsafe { self.push_front_raw(value) };
456            return Some(old_head);
457        }
458
459        // Step 2: Head does not match. Use a cursor to check subsequent elements.
460        let mut cursor = self.cursor_mut();
461        while let Some(next_ref) = cursor.get_next() {
462            if f(next_ref) {
463                // SAFETY: `value` is a valid pointer that will outlive its reference from this
464                // list.
465                unsafe {
466                    return cursor.replace_next_raw(value);
467                }
468            }
469            cursor.move_next();
470        }
471
472        None
473    }
474
475    /// Splits the list after the specified position, returning a new list
476    /// containing the elements that followed `pos`.
477    ///
478    /// # Safety
479    ///
480    /// The caller must ensure that `pos` is a valid pointer to an element in this list.
481    pub unsafe fn split_after_raw(&mut self, pos: *mut P::Target) -> Self {
482        debug_assert!(!pos.is_null());
483        // SAFETY: The caller must ensure that `pos` is a valid pointer to an element in this list.
484        let pos_node = unsafe { &(*pos) }.get_node();
485        let next_ptr = unsafe { *pos_node.next.get() };
486
487        unsafe { *pos_node.next.get() = crate::make_sentinel_null() };
488
489        let mut new_list =
490            Self { head: next_ptr, size: S::INIT, _phantom: core::marker::PhantomData };
491
492        if S::IS_TRACKING {
493            let new_size = new_list.size_slow();
494            new_list.size.set(new_size);
495            self.size.set(self.size.get() - new_size);
496        }
497
498        new_list
499    }
500
501    /// Retains only the elements specified by the predicate.
502    pub fn retain<F>(&mut self, mut f: F)
503    where
504        F: FnMut(&P::Target) -> bool,
505    {
506        self.erase_if(|x| !f(x));
507    }
508
509    /// Returns a cursor positioned at the front of the list.
510    pub fn cursor_mut(&mut self) -> CursorMut<'_, P, Tag, S> {
511        let head = self.head;
512        CursorMut { list: self, current: head }
513    }
514
515    /// Calculates the size of the list by iterating through all elements. O(N) time complexity.
516    pub fn size_slow(&self) -> usize {
517        if let Some(head) = self.front() {
518            let iter = Iterator::<'_, P, Tag>::from_element(head);
519            let mut count = 0;
520            for _ in iter {
521                count += 1;
522            }
523            count
524        } else {
525            0
526        }
527    }
528
529    /// Finds the first element matching the predicate.
530    pub fn find_if<F>(&self, mut f: F) -> Option<&P::Target>
531    where
532        F: FnMut(&P::Target) -> bool,
533    {
534        self.iter().find(|&x| f(x))
535    }
536
537    /// Returns an iterator over the elements of the list.
538    pub fn iter(&self) -> Iterator<'_, P, Tag> {
539        Iterator::new(self.head)
540    }
541}
542
543impl<P, Tag> SinglyLinkedList<P, Tag, TrackingSize>
544where
545    P: PtrTraits,
546    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
547{
548    /// Returns the size of the list. O(1) time complexity.
549    pub fn size(&self) -> usize {
550        self.size.get()
551    }
552}
553
554impl<P, Tag, S> Drop for SinglyLinkedList<P, Tag, S>
555where
556    P: PtrTraits,
557    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
558    S: SizeTracker,
559{
560    fn drop(&mut self) {
561        if P::IS_MANAGED {
562            self.clear();
563        } else {
564            debug_assert!(self.is_empty(), "List must be empty on destruction");
565            if S::IS_TRACKING {
566                debug_assert_eq!(self.size.get(), 0, "Size must be zero on destruction");
567            }
568        }
569    }
570}
571
572impl<P, Tag, S> Default for SinglyLinkedList<P, Tag, S>
573where
574    P: PtrTraits,
575    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
576    S: SizeTracker,
577{
578    fn default() -> Self {
579        Self::new()
580    }
581}
582
583/// An iterator over the elements of a `SinglyLinkedList`.
584pub struct Iterator<'a, P, Tag = DefaultObjectTag>
585where
586    P: PtrTraits,
587    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
588{
589    current: *mut P::Target,
590    _phantom: core::marker::PhantomData<&'a (P, Tag)>,
591}
592
593impl<'a, P, Tag> Iterator<'a, P, Tag>
594where
595    P: PtrTraits,
596    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
597{
598    fn new(current: *mut P::Target) -> Self {
599        Self { current, _phantom: core::marker::PhantomData }
600    }
601}
602
603impl<'a, P, Tag> core::iter::Iterator for Iterator<'a, P, Tag>
604where
605    P: PtrTraits,
606    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
607{
608    type Item = &'a P::Target;
609
610    fn next(&mut self) -> Option<Self::Item> {
611        if crate::is_sentinel_ptr(self.current) {
612            None
613        } else {
614            // SAFETY: `self.current` is not a sentinel, so it is a valid, aligned pointer to an element.
615            // The list is guaranteed to be immutable for the lifetime `'a` of the iterator.
616            let current = unsafe { &*self.current };
617            // SAFETY: `current` is a valid reference, so we can safely read `next` from its node.
618            self.current = unsafe { *current.get_node().next.get() };
619            Some(current)
620        }
621    }
622}
623
624impl<'a, P, Tag> Iterator<'a, P, Tag>
625where
626    P: PtrTraits,
627    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
628{
629    /// Creates an iterator starting from a specific element.
630    ///
631    /// # Panics
632    ///
633    /// Panics if the object is not in a container.
634    pub fn from_element(obj: &'a P::Target) -> Self {
635        assert!(obj.get_node().in_container(), "Object must be in a container");
636        Self { current: obj as *const _ as *mut _, _phantom: core::marker::PhantomData }
637    }
638}
639
640/// A cursor that can be used to iterate and modify a `SinglyLinkedList`.
641pub struct CursorMut<'a, P, Tag = DefaultObjectTag, S = NonTrackingSize>
642where
643    P: PtrTraits,
644    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
645    S: SizeTracker,
646{
647    list: &'a mut SinglyLinkedList<P, Tag, S>,
648    current: *mut P::Target,
649}
650
651impl<'a, P, Tag, S> CursorMut<'a, P, Tag, S>
652where
653    P: PtrTraits,
654    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
655    S: SizeTracker,
656{
657    /// Returns a reference to the element at the current position.
658    pub fn get(&self) -> Option<&P::Target> {
659        if crate::is_sentinel_ptr(self.current) {
660            None
661        } else {
662            // SAFETY: `self.current` is not a sentinel, so it is a valid pointer to an element.
663            Some(unsafe { &*self.current })
664        }
665    }
666
667    /// Moves the cursor to the next element. Returns true if the cursor is now at a valid element.
668    pub fn move_next(&mut self) -> bool {
669        if crate::is_sentinel_ptr(self.current) {
670            return false;
671        }
672        // SAFETY: `self.current` is valid.
673        let node = unsafe { self.list.get_node_ref(self.current) };
674        self.current = node.get_next();
675        !crate::is_sentinel_ptr(self.current)
676    }
677
678    /// Returns a reference to the element after the current position.
679    pub fn get_next(&self) -> Option<&P::Target> {
680        if crate::is_sentinel_ptr(self.current) {
681            return None;
682        }
683        // SAFETY: `self.current` is valid.
684        let node = unsafe { self.list.get_node_ref(self.current) };
685        let next_ptr = node.get_next();
686        if crate::is_sentinel_ptr(next_ptr) {
687            None
688        } else {
689            // SAFETY: `next_ptr` is not sentinel, so it is a valid pointer.
690            unsafe { Some(&*next_ptr) }
691        }
692    }
693
694    /// Inserts a new element after the current position.
695    pub fn insert_after(&mut self, ptr: P)
696    where
697        P: ManagedPtr,
698    {
699        assert!(!crate::is_sentinel_ptr(self.current), "Cannot insert after end sentinel");
700        // SAFETY: `self.current` is a valid pointer to an element in the list, and `ptr` is managed.
701        unsafe { self.list.insert_after_raw(self.current, ptr) }
702    }
703
704    /// Erases the element after the current position. Returns the erased element.
705    pub fn erase_next(&mut self) -> Option<P> {
706        assert!(!crate::is_sentinel_ptr(self.current), "Cannot erase next of end sentinel");
707        // SAFETY: `self.current` is a valid pointer to an element in the list.
708        unsafe { self.list.erase_next_raw(self.current) }
709    }
710
711    /// Replaces the element after the current position. Returns the replaced element.
712    ///
713    /// # Panics
714    ///
715    /// Panics if the object is already in a container.
716    ///
717    /// # Safety
718    ///
719    /// The caller must ensure that `value` is a valid pointer to a `T` and that the object outlives
720    /// the reference from the list.
721    pub unsafe fn replace_next_raw(&mut self, value: P) -> Option<P> {
722        debug_assert!(!crate::is_sentinel_ptr(self.current), "Cannot replace next of end sentinel");
723
724        // SAFETY: `self.current` is valid.
725        let current_node = unsafe { self.list.get_node_ref(self.current) };
726        let next_ptr = current_node.get_next();
727        if crate::is_sentinel_ptr(next_ptr) {
728            return None;
729        }
730
731        let value_raw = P::into_raw(value);
732        // SAFETY: `value_raw` is valid.
733        let value_node = unsafe { self.list.get_node_ref(value_raw) };
734        assert!(!value_node.in_container());
735
736        // SAFETY: `next_ptr` is valid.
737        let next_node = unsafe { self.list.get_node_ref(next_ptr) };
738
739        value_node.set_next(next_node.get_next());
740        current_node.set_next(value_raw);
741        next_node.set_next(core::ptr::null_mut());
742
743        // SAFETY: `next_ptr` was replaced, safe to reconstruct.
744        Some(unsafe { P::from_raw(next_ptr) })
745    }
746}
747
748impl<P, Tag, S> core::fmt::Debug for SinglyLinkedList<P, Tag, S>
749where
750    P: PtrTraits,
751    P::Target: SinglyLinkedListContainable<P::Target, Tag> + core::fmt::Debug,
752    S: SizeTracker,
753{
754    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
755        f.debug_list().entries(self.iter()).finish()
756    }
757}
758
759#[cfg(test)]
760mod tests {
761    extern crate alloc;
762    use super::*;
763    use crate::intrusive_container_test_support::*;
764    use crate::ref_ptr::RefPtr;
765    use crate::unique_ptr::UniquePtr;
766    use alloc::sync::Arc;
767    use core::ffi::c_void;
768    use core::sync::atomic::{AtomicBool, Ordering};
769
770    // Dummy type to satisfy trait bounds for static asserts.
771    struct DummyTarget;
772    impl SinglyLinkedListContainable<DummyTarget, DefaultObjectTag> for DummyTarget {
773        fn get_node(&self) -> &SinglyLinkedListNode<DummyTarget> {
774            unreachable!()
775        }
776    }
777
778    zr::static_assert!(
779        core::mem::size_of::<SinglyLinkedList<*mut DummyTarget>>()
780            == core::mem::size_of::<*mut DummyTarget>()
781    );
782    zr::static_assert!(
783        core::mem::align_of::<SinglyLinkedList<*mut DummyTarget>>()
784            == core::mem::align_of::<*mut DummyTarget>()
785    );
786
787    zr::static_assert!(
788        core::mem::size_of::<SinglyLinkedList<*mut DummyTarget, DefaultObjectTag, TrackingSize>>()
789            == 2 * core::mem::size_of::<*mut DummyTarget>()
790    );
791    zr::static_assert!(
792        core::mem::align_of::<SinglyLinkedList<*mut DummyTarget, DefaultObjectTag, TrackingSize>>()
793            == core::mem::align_of::<*mut DummyTarget>()
794    );
795
796    zr::static_assert!(
797        core::mem::size_of::<Iterator<'_, *mut DummyTarget>>()
798            == core::mem::size_of::<*mut DummyTarget>()
799    );
800    zr::static_assert!(
801        core::mem::align_of::<Iterator<'_, *mut DummyTarget>>()
802            == core::mem::align_of::<*mut DummyTarget>()
803    );
804
805    macro_rules! generate_list_tests {
806        ($mod_name:ident, $ptr_type:ty, $factory_type:ty, $get_val:expr, $push:expr) => {
807            mod $mod_name {
808                use super::*;
809
810                #[test]
811                fn test_basic_ops() {
812                    let mut factory = <$factory_type>::new();
813                    let mut list = SinglyLinkedList::<$ptr_type>::new();
814                    assert!(list.is_empty());
815
816                    let obj1 = factory.create(1);
817                    let obj2 = factory.create(2);
818                    let obj3 = factory.create(3);
819
820                    $push(&mut list, obj1);
821                    $push(&mut list, obj2);
822                    $push(&mut list, obj3);
823
824                    assert!(!list.is_empty());
825
826                    let mut iter = list.iter();
827                    assert_eq!(iter.next().unwrap().value, 3);
828                    assert_eq!(iter.next().unwrap().value, 2);
829                    assert_eq!(iter.next().unwrap().value, 1);
830                    assert!(iter.next().is_none());
831
832                    assert_eq!($get_val(list.pop_front().unwrap().get_ref()), 3);
833                    assert_eq!($get_val(list.pop_front().unwrap().get_ref()), 2);
834                    assert_eq!($get_val(list.pop_front().unwrap().get_ref()), 1);
835
836                    assert!(list.is_empty());
837                }
838
839                #[test]
840                fn test_insert_after() {
841                    let mut factory = <$factory_type>::new();
842                    let mut list = SinglyLinkedList::<$ptr_type>::new();
843
844                    let obj1 = factory.create(1);
845                    let raw1 = <$ptr_type as PtrTraits>::into_raw(obj1);
846                    $push(&mut list, unsafe { <$ptr_type as PtrTraits>::from_raw(raw1) });
847
848                    let obj2 = factory.create(2);
849                    let raw2 = <$ptr_type as PtrTraits>::into_raw(obj2);
850                    unsafe {
851                        list.insert_after_raw(raw1, <$ptr_type as PtrTraits>::from_raw(raw2));
852                    }
853
854                    let obj3 = factory.create(3);
855                    unsafe {
856                        list.insert_after_raw(raw2, obj3);
857                    }
858
859                    let mut iter = list.iter();
860                    assert_eq!(iter.next().unwrap().value, 1);
861                    assert_eq!(iter.next().unwrap().value, 2);
862                    assert_eq!(iter.next().unwrap().value, 3);
863                    assert!(iter.next().is_none());
864
865                    // Cleanup
866                    list.clear();
867                }
868
869                #[test]
870                fn test_clear() {
871                    let mut factory = <$factory_type>::new();
872                    let mut list = SinglyLinkedList::<$ptr_type>::new();
873                    let obj1 = factory.create(1);
874                    let obj2 = factory.create(2);
875
876                    $push(&mut list, obj1);
877                    $push(&mut list, obj2);
878
879                    assert!(!list.is_empty());
880                    list.clear();
881                    assert!(list.is_empty());
882                }
883
884                #[test]
885                fn test_erase_next() {
886                    let mut factory = <$factory_type>::new();
887                    let mut list = SinglyLinkedList::<$ptr_type>::new();
888
889                    let obj1 = factory.create(1);
890                    let raw1 = <$ptr_type as PtrTraits>::into_raw(obj1);
891                    $push(&mut list, unsafe { <$ptr_type as PtrTraits>::from_raw(raw1) });
892
893                    let obj2 = factory.create(2);
894                    let raw2 = <$ptr_type as PtrTraits>::into_raw(obj2);
895                    unsafe {
896                        list.insert_after_raw(raw1, <$ptr_type as PtrTraits>::from_raw(raw2));
897                    }
898
899                    let obj3 = factory.create(3);
900                    unsafe {
901                        list.insert_after_raw(raw2, obj3);
902                    }
903
904                    let erased = unsafe { list.erase_next_raw(raw1) };
905                    assert_eq!($get_val(erased.unwrap().get_ref()), 2);
906
907                    let mut iter = list.iter();
908                    assert_eq!(iter.next().unwrap().value, 1);
909                    assert_eq!(iter.next().unwrap().value, 3);
910                    assert!(iter.next().is_none());
911
912                    // Cleanup
913                    list.clear();
914                }
915
916                #[test]
917                fn test_swap() {
918                    let mut factory = <$factory_type>::new();
919                    let mut list1 = SinglyLinkedList::<$ptr_type>::new();
920                    let mut list2 = SinglyLinkedList::<$ptr_type>::new();
921
922                    let obj1 = factory.create(1);
923                    let obj2 = factory.create(2);
924
925                    $push(&mut list1, obj1);
926                    $push(&mut list2, obj2);
927
928                    list1.swap(&mut list2);
929
930                    assert_eq!($get_val(list1.pop_front().unwrap().get_ref()), 2);
931                    assert_eq!($get_val(list2.pop_front().unwrap().get_ref()), 1);
932                }
933
934                #[test]
935                fn test_size_slow() {
936                    let mut factory = <$factory_type>::new();
937                    let mut list = SinglyLinkedList::<$ptr_type>::new();
938                    let obj1 = factory.create(1);
939                    let obj2 = factory.create(2);
940
941                    assert_eq!(list.size_slow(), 0);
942
943                    $push(&mut list, obj1);
944                    assert_eq!(list.size_slow(), 1);
945                    $push(&mut list, obj2);
946                    assert_eq!(list.size_slow(), 2);
947
948                    list.pop_front();
949                    assert_eq!(list.size_slow(), 1);
950
951                    list.pop_front();
952                    assert_eq!(list.size_slow(), 0);
953                }
954
955                #[test]
956                fn test_find_if() {
957                    let mut factory = <$factory_type>::new();
958                    let mut list = SinglyLinkedList::<$ptr_type>::new();
959                    let obj1 = factory.create(1);
960                    let obj2 = factory.create(2);
961
962                    $push(&mut list, obj1);
963                    $push(&mut list, obj2);
964
965                    let found = list.find_if(|o| o.value == 1);
966                    assert!(found.is_some());
967                    assert_eq!(found.unwrap().value, 1);
968
969                    let found = list.find_if(|o| o.value == 3);
970                    assert!(found.is_none());
971
972                    // Cleanup
973                    list.clear();
974                }
975
976                #[test]
977                fn test_erase_if() {
978                    let mut factory = <$factory_type>::new();
979                    let mut list = SinglyLinkedList::<$ptr_type>::new();
980                    let obj1 = factory.create(1);
981                    let obj2 = factory.create(2);
982                    let obj3 = factory.create(3);
983
984                    $push(&mut list, obj1);
985                    $push(&mut list, obj2);
986                    $push(&mut list, obj3);
987
988                    // list: 3 -> 2 -> 1
989
990                    let erased = list.erase_if(|o| o.value == 2);
991                    assert!(erased.is_some());
992                    assert_eq!($get_val(erased.unwrap().get_ref()), 2);
993
994                    let mut iter = list.iter();
995                    assert_eq!(iter.next().unwrap().value, 3);
996                    assert_eq!(iter.next().unwrap().value, 1);
997                    assert!(iter.next().is_none());
998
999                    // Cleanup
1000                    list.clear();
1001                }
1002
1003                #[test]
1004                fn test_replace_if() {
1005                    let mut factory = <$factory_type>::new();
1006                    let mut list = SinglyLinkedList::<$ptr_type>::new();
1007                    let obj1 = factory.create(1);
1008                    let obj2 = factory.create(2);
1009                    let obj3 = factory.create(3);
1010
1011                    $push(&mut list, obj1);
1012                    $push(&mut list, obj2);
1013
1014                    // list: 2 -> 1
1015
1016                    let replaced = unsafe { list.replace_if_raw(|o| o.value == 2, obj3) };
1017                    assert_eq!($get_val(replaced.unwrap().get_ref()), 2);
1018
1019                    let mut iter = list.iter();
1020                    assert_eq!(iter.next().unwrap().value, 3);
1021                    assert_eq!(iter.next().unwrap().value, 1);
1022                    assert!(iter.next().is_none());
1023
1024                    // Cleanup
1025                    list.clear();
1026                }
1027
1028                #[test]
1029                fn test_split_after() {
1030                    let mut factory = <$factory_type>::new();
1031                    let mut list = SinglyLinkedList::<$ptr_type>::new();
1032                    let obj1 = factory.create(1);
1033                    let obj2 = factory.create(2);
1034                    let obj3 = factory.create(3);
1035
1036                    $push(&mut list, obj1);
1037                    $push(&mut list, obj2);
1038                    $push(&mut list, obj3);
1039
1040                    // list: 3 -> 2 -> 1
1041
1042                    let raw_pos = {
1043                        let found = list.find_if(|o| o.value == 2).unwrap();
1044                        found as *const <$ptr_type as PtrTraits>::Target
1045                            as *mut <$ptr_type as PtrTraits>::Target
1046                    };
1047
1048                    let mut other = unsafe { list.split_after_raw(raw_pos) };
1049
1050                    // list should be 3 -> 2
1051                    // other should be 1
1052
1053                    assert_eq!(list.size_slow(), 2);
1054                    assert_eq!(other.size_slow(), 1);
1055
1056                    let mut iter = list.iter();
1057                    assert_eq!(iter.next().unwrap().value, 3);
1058                    assert_eq!(iter.next().unwrap().value, 2);
1059                    assert!(iter.next().is_none());
1060
1061                    let mut iter = other.iter();
1062                    assert_eq!(iter.next().unwrap().value, 1);
1063                    assert!(iter.next().is_none());
1064
1065                    // Cleanup
1066                    list.clear();
1067                    other.clear();
1068                }
1069            }
1070        };
1071    }
1072
1073    #[derive(fbl::Recyclable, crate::SinglyLinkedListContainable)]
1074    struct TestObject {
1075        value: i32,
1076        #[sll_node]
1077        node: SinglyLinkedListNode<TestObject>,
1078    }
1079
1080    impl TestObject {
1081        fn new(value: i32) -> Self {
1082            Self { value, node: SinglyLinkedListNode::new() }
1083        }
1084    }
1085
1086    impl TestValue for TestObject {
1087        fn new(value: i32) -> Self {
1088            Self::new(value)
1089        }
1090    }
1091
1092    generate_list_tests!(
1093        raw_ptr_tests,
1094        *mut TestObject,
1095        RawFactory<TestObject>,
1096        |p: &TestObject| p.value,
1097        |list: &mut SinglyLinkedList<*mut TestObject>, obj| unsafe {
1098            list.push_front_raw(obj);
1099        }
1100    );
1101
1102    #[derive(fbl::Recyclable, crate::SinglyLinkedListContainable)]
1103    struct UniqueTestObject {
1104        value: i32,
1105        #[sll_node]
1106        node: SinglyLinkedListNode<UniqueTestObject>,
1107    }
1108
1109    impl UniqueTestObject {
1110        fn new(value: i32) -> Self {
1111            Self { value, node: SinglyLinkedListNode::new() }
1112        }
1113    }
1114
1115    impl TestValue for UniqueTestObject {
1116        fn new(value: i32) -> Self {
1117            Self::new(value)
1118        }
1119    }
1120
1121    generate_list_tests!(
1122        unique_ptr_tests,
1123        UniquePtr<UniqueTestObject>,
1124        UniqueFactory<UniqueTestObject>,
1125        |p: &UniqueTestObject| p.value,
1126        |list: &mut SinglyLinkedList<UniquePtr<UniqueTestObject>>, obj| list.push_front(obj)
1127    );
1128
1129    #[fbl::ref_counted]
1130    #[derive(crate::SinglyLinkedListContainable, crate::Recyclable)]
1131    #[repr(C)]
1132    pub struct RefTestObject {
1133        value: i32,
1134        #[sll_node]
1135        node: SinglyLinkedListNode<RefTestObject>,
1136    }
1137
1138    impl TestValue for RefTestObject {
1139        fn new_ref_counted(value: i32) -> RefPtr<Self> {
1140            crate::make_ref_counted!(RefTestObject {
1141                value: value,
1142                node: SinglyLinkedListNode::new()
1143            })
1144            .unwrap()
1145        }
1146    }
1147
1148    generate_list_tests!(
1149        ref_ptr_tests,
1150        RefPtr<RefTestObject>,
1151        RefFactory<RefTestObject>,
1152        |p: &RefTestObject| p.value,
1153        |list: &mut SinglyLinkedList<RefPtr<RefTestObject>>, obj| list.push_front(obj)
1154    );
1155
1156    #[test]
1157    fn test_ref_ptr_identity() {
1158        let mut list = SinglyLinkedList::<RefPtr<RefTestObject>>::new();
1159        let obj =
1160            crate::make_ref_counted!(RefTestObject { value: 1, node: SinglyLinkedListNode::new() })
1161                .unwrap();
1162        list.push_front(obj.clone());
1163        let popped = list.pop_front().unwrap();
1164        assert!(RefPtr::ptr_eq(&popped, &obj));
1165    }
1166
1167    #[derive(crate::SinglyLinkedListContainable)]
1168    #[repr(C)]
1169    pub struct BaseItem {
1170        #[sll_node]
1171        node: SinglyLinkedListNode<BaseItem>,
1172    }
1173
1174    #[repr(C)]
1175    pub struct RustItem {
1176        base: BaseItem,
1177        value: i32,
1178    }
1179
1180    unsafe extern "C" {
1181        fn create_cpp_list() -> *mut c_void;
1182        fn destroy_cpp_list(list_ptr: *mut c_void);
1183        fn create_cpp_item(value: i32) -> *mut c_void;
1184        fn destroy_cpp_item(item_ptr: *mut c_void);
1185        fn list_push_front(list_ptr: *mut c_void, item_ptr: *mut c_void);
1186        fn list_pop_front(list_ptr: *mut c_void) -> *mut c_void;
1187        fn list_is_empty(list_ptr: *mut c_void) -> bool;
1188        fn get_cpp_item_value(item_ptr: *mut c_void) -> i32;
1189    }
1190
1191    #[test]
1192    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1193    fn test_cross_lang_list() {
1194        use core::ffi::c_void;
1195
1196        unsafe {
1197            let list_ptr = create_cpp_list();
1198            assert!(list_is_empty(list_ptr));
1199
1200            let cpp_item1 = create_cpp_item(10);
1201            let cpp_item2 = create_cpp_item(20);
1202
1203            let mut rust_item =
1204                RustItem { base: BaseItem { node: SinglyLinkedListNode::new() }, value: 30 };
1205
1206            // Push C++ item 1
1207            list_push_front(list_ptr, cpp_item1);
1208            assert!(!list_is_empty(list_ptr));
1209
1210            // Push Rust item
1211            list_push_front(list_ptr, &mut rust_item.base as *mut BaseItem as *mut c_void);
1212
1213            // Push C++ item 2
1214            list_push_front(list_ptr, cpp_item2);
1215
1216            // Now list should have: CppItem(20) -> RustItem(30) -> CppItem(10)
1217
1218            // Pop C++ item 2
1219            let popped = list_pop_front(list_ptr);
1220            assert_eq!(get_cpp_item_value(popped), 20);
1221            destroy_cpp_item(popped);
1222
1223            // Pop Rust item
1224            let popped = list_pop_front(list_ptr);
1225            let popped_rust_item = popped as *mut RustItem; // Safe because we know it's a RustItem
1226            assert_eq!((*popped_rust_item).value, 30);
1227
1228            // Pop C++ item 1
1229            let popped = list_pop_front(list_ptr);
1230            assert_eq!(get_cpp_item_value(popped), 10);
1231            destroy_cpp_item(popped);
1232
1233            assert!(list_is_empty(list_ptr));
1234            destroy_cpp_list(list_ptr);
1235        }
1236    }
1237
1238    struct Tag2;
1239
1240    #[fbl::ref_counted]
1241    #[derive(crate::SinglyLinkedListContainable, crate::Recyclable)]
1242    #[repr(C)]
1243    struct MultiListObject {
1244        value: i32,
1245        #[sll_node]
1246        node1: SinglyLinkedListNode<MultiListObject>,
1247        node2: SinglyLinkedListNode<MultiListObject>,
1248    }
1249
1250    impl SinglyLinkedListContainable<MultiListObject, Tag2> for MultiListObject {
1251        fn get_node(&self) -> &SinglyLinkedListNode<MultiListObject> {
1252            &self.node2
1253        }
1254    }
1255
1256    #[test]
1257    fn test_multiple_lists() {
1258        let mut list1 = SinglyLinkedList::<RefPtr<MultiListObject>, DefaultObjectTag>::new();
1259        let mut list2 = SinglyLinkedList::<RefPtr<MultiListObject>, Tag2>::new();
1260
1261        let obj1 = fbl::make_ref_counted!(MultiListObject {
1262            value: 1,
1263            node1: SinglyLinkedListNode::new(),
1264            node2: SinglyLinkedListNode::new(),
1265        })
1266        .unwrap();
1267
1268        let obj2 = fbl::make_ref_counted!(MultiListObject {
1269            value: 2,
1270            node1: SinglyLinkedListNode::new(),
1271            node2: SinglyLinkedListNode::new(),
1272        })
1273        .unwrap();
1274
1275        list1.push_front(obj1.clone());
1276        list1.push_front(obj2.clone());
1277
1278        list2.push_front(obj1.clone());
1279
1280        let mut iter1 = list1.iter();
1281        assert_eq!(iter1.next().unwrap().value, 2);
1282        assert_eq!(iter1.next().unwrap().value, 1);
1283        assert!(iter1.next().is_none());
1284
1285        let mut iter2 = list2.iter();
1286        assert_eq!(iter2.next().unwrap().value, 1);
1287        assert!(iter2.next().is_none());
1288
1289        assert_eq!(list1.pop_front().unwrap().value, 2);
1290        assert_eq!(list2.pop_front().unwrap().value, 1);
1291
1292        assert!(!list1.is_empty());
1293        assert!(list2.is_empty());
1294
1295        assert_eq!(list1.pop_front().unwrap().value, 1);
1296        assert!(list1.is_empty());
1297    }
1298
1299    #[test]
1300    fn test_size_tracking() {
1301        let mut list =
1302            SinglyLinkedList::<UniquePtr<UniqueTestObject>, DefaultObjectTag, TrackingSize>::new();
1303
1304        assert_eq!(list.size(), 0);
1305        list.push_front(UniquePtr::try_new(UniqueTestObject::new(1)).unwrap());
1306        assert_eq!(list.size(), 1);
1307        list.push_front(UniquePtr::try_new(UniqueTestObject::new(2)).unwrap());
1308        assert_eq!(list.size(), 2);
1309
1310        list.pop_front();
1311        assert_eq!(list.size(), 1);
1312        list.clear();
1313    }
1314
1315    #[test]
1316    fn test_split_after_size_tracking() {
1317        let mut list = SinglyLinkedList::<*mut TestObject, DefaultObjectTag, TrackingSize>::new();
1318        let mut obj1 = TestObject::new(1);
1319        let mut obj2 = TestObject::new(2);
1320        let mut obj3 = TestObject::new(3);
1321
1322        unsafe {
1323            list.push_front_raw(&mut obj1);
1324            list.push_front_raw(&mut obj2);
1325            list.push_front_raw(&mut obj3);
1326        }
1327
1328        assert_eq!(list.size(), 3);
1329
1330        let raw_pos = {
1331            let found = list.find_if(|o| o.value == 2).unwrap();
1332            found as *const TestObject as *mut TestObject
1333        };
1334
1335        let mut other = unsafe { list.split_after_raw(raw_pos) };
1336
1337        assert_eq!(list.size(), 2);
1338        assert_eq!(other.size(), 1);
1339
1340        list.clear();
1341        other.clear();
1342    }
1343
1344    #[test]
1345    fn test_lifecycle_on_drop() {
1346        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1347        let obj1 = UniquePtr::try_new(UniqueTestObject::new(1)).unwrap();
1348        let obj2 = UniquePtr::try_new(UniqueTestObject::new(2)).unwrap();
1349
1350        list.push_front(obj1);
1351        list.push_front(obj2);
1352
1353        drop(list);
1354    }
1355
1356    #[derive(crate::SinglyLinkedListContainable)]
1357    struct DerivedObject {
1358        value: i32,
1359        #[sll_node]
1360        node: SinglyLinkedListNode<DerivedObject>,
1361    }
1362
1363    impl DerivedObject {
1364        fn new(value: i32) -> Self {
1365            Self { value, node: SinglyLinkedListNode::new() }
1366        }
1367    }
1368
1369    #[test]
1370    fn test_derive_containable() {
1371        let mut list = SinglyLinkedList::<*mut DerivedObject>::new();
1372        let mut obj1 = DerivedObject::new(1);
1373        let mut obj2 = DerivedObject::new(2);
1374
1375        unsafe {
1376            list.push_front_raw(&mut obj1);
1377            list.push_front_raw(&mut obj2);
1378        }
1379
1380        let mut iter = list.iter();
1381        assert_eq!(iter.next().unwrap().value, 2);
1382        assert_eq!(iter.next().unwrap().value, 1);
1383        assert!(iter.next().is_none());
1384        list.clear();
1385    }
1386
1387    struct Tag3;
1388
1389    #[derive(crate::SinglyLinkedListContainable)]
1390    struct MultiDerivedObject {
1391        value: i32,
1392        #[sll_node]
1393        node1: SinglyLinkedListNode<MultiDerivedObject>,
1394        #[sll_node(tag = Tag3)]
1395        node2: SinglyLinkedListNode<MultiDerivedObject>,
1396    }
1397
1398    impl MultiDerivedObject {
1399        fn new(value: i32) -> Self {
1400            Self { value, node1: SinglyLinkedListNode::new(), node2: SinglyLinkedListNode::new() }
1401        }
1402    }
1403
1404    #[test]
1405    fn test_derive_containable_multi() {
1406        let mut list1 = SinglyLinkedList::<*mut MultiDerivedObject, DefaultObjectTag>::new();
1407        let mut list2 = SinglyLinkedList::<*mut MultiDerivedObject, Tag3>::new();
1408
1409        let mut obj1 = MultiDerivedObject::new(1);
1410        let mut obj2 = MultiDerivedObject::new(2);
1411
1412        unsafe {
1413            list1.push_front_raw(core::ptr::addr_of_mut!(obj1));
1414            list1.push_front_raw(core::ptr::addr_of_mut!(obj2));
1415
1416            list2.push_front_raw(core::ptr::addr_of_mut!(obj1));
1417        }
1418
1419        let mut iter1 = list1.iter();
1420        assert_eq!(iter1.next().unwrap().value, 2);
1421        assert_eq!(iter1.next().unwrap().value, 1);
1422
1423        let mut iter2 = list2.iter();
1424        assert_eq!(iter2.next().unwrap().value, 1);
1425
1426        list1.clear();
1427        list2.clear();
1428    }
1429
1430    #[test]
1431    fn test_retain() {
1432        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1433        list.push_front(UniquePtr::try_new(UniqueTestObject::new(3)).unwrap());
1434        list.push_front(UniquePtr::try_new(UniqueTestObject::new(2)).unwrap());
1435        list.push_front(UniquePtr::try_new(UniqueTestObject::new(1)).unwrap());
1436
1437        list.retain(|o| o.value % 2 != 0);
1438
1439        let mut iter = list.iter();
1440        assert_eq!(iter.next().unwrap().value, 1);
1441        assert_eq!(iter.next().unwrap().value, 3);
1442        assert!(iter.next().is_none());
1443        list.clear();
1444    }
1445
1446    #[test]
1447    fn test_cursor_mut() {
1448        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1449        let obj1 = UniquePtr::try_new(UniqueTestObject::new(1)).unwrap();
1450        let obj2 = UniquePtr::try_new(UniqueTestObject::new(2)).unwrap();
1451        let obj3 = UniquePtr::try_new(UniqueTestObject::new(3)).unwrap();
1452
1453        list.push_front(obj1);
1454        list.push_front(obj2);
1455
1456        let mut cursor = list.cursor_mut();
1457        assert_eq!(cursor.get().unwrap().value, 2);
1458
1459        cursor.insert_after(obj3);
1460
1461        assert!(cursor.move_next());
1462        assert_eq!(cursor.get().unwrap().value, 3);
1463
1464        assert!(cursor.move_next());
1465        assert_eq!(cursor.get().unwrap().value, 1);
1466
1467        assert!(!cursor.move_next());
1468
1469        // Reset cursor
1470        let mut cursor = list.cursor_mut();
1471        assert_eq!(cursor.get().unwrap().value, 2);
1472
1473        let erased = cursor.erase_next().unwrap();
1474        assert_eq!(erased.value, 3);
1475
1476        assert!(cursor.move_next());
1477        assert_eq!(cursor.get().unwrap().value, 1);
1478
1479        assert!(!cursor.move_next());
1480    }
1481
1482    #[test]
1483    fn test_iterator_from_element() {
1484        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1485        list.push_front(UniquePtr::try_new(UniqueTestObject::new(3)).unwrap());
1486        list.push_front(UniquePtr::try_new(UniqueTestObject::new(2)).unwrap());
1487        list.push_front(UniquePtr::try_new(UniqueTestObject::new(1)).unwrap());
1488
1489        let mut iter = list.iter();
1490        iter.next(); // obj1
1491        let obj2_ref = iter.next().unwrap();
1492
1493        let mut from_element_iter: Iterator<'_, UniquePtr<UniqueTestObject>> =
1494            Iterator::from_element(obj2_ref);
1495        assert_eq!(from_element_iter.next().unwrap().value, 2);
1496        assert_eq!(from_element_iter.next().unwrap().value, 3);
1497        assert!(from_element_iter.next().is_none());
1498
1499        list.clear();
1500    }
1501
1502    #[test]
1503    fn test_front_ops() {
1504        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1505        assert!(list.front().is_none());
1506
1507        list.push_front(UniquePtr::try_new(UniqueTestObject::new(1)).unwrap());
1508        assert_eq!(list.front().unwrap().value, 1);
1509
1510        list.push_front(UniquePtr::try_new(UniqueTestObject::new(2)).unwrap());
1511        assert_eq!(list.front().unwrap().value, 2);
1512
1513        list.clear();
1514    }
1515
1516    // SLL FFI Declarations
1517    unsafe extern "C" {
1518        // UniqueList Helpers
1519        fn cpp_sll_create_unique_list() -> *mut c_void;
1520        fn cpp_sll_destroy_unique_list(list: *mut c_void);
1521        fn cpp_sll_unique_list_push_front(list: *mut c_void, item: *mut c_void);
1522        fn cpp_sll_unique_list_pop_front(list: *mut c_void) -> *mut c_void;
1523        fn cpp_sll_unique_list_is_empty(list: *mut c_void) -> bool;
1524
1525        // RefList Helpers
1526        fn cpp_sll_create_ref_list() -> *mut c_void;
1527        fn cpp_sll_destroy_ref_list(list: *mut c_void);
1528        fn cpp_sll_ref_list_push_front(list: *mut c_void, item: *mut c_void);
1529        fn cpp_sll_ref_list_pop_front(list: *mut c_void) -> *mut c_void;
1530        fn cpp_sll_ref_list_is_empty(list: *mut c_void) -> bool;
1531
1532        // SharedUniqueObject Helpers (Defined in DLL tests C++ file)
1533        fn cpp_create_unique_object(value: i32, destruction_flag: *mut bool) -> *mut c_void;
1534        fn cpp_get_unique_object_value(obj: *mut c_void) -> i32;
1535
1536        // SharedRefObject Helpers (Defined in DLL tests C++ file)
1537        fn cpp_create_ref_object(value: i32, destruction_flag: *mut bool) -> *mut c_void;
1538        fn cpp_get_ref_object_value(obj: *mut c_void) -> i32;
1539    }
1540
1541    #[test]
1542    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1543    fn test_interop_rust_list_cpp_unique_objects() {
1544        let destroyed1 = AtomicBool::new(false);
1545        let destroyed2 = AtomicBool::new(false);
1546
1547        unsafe {
1548            let mut list = SinglyLinkedList::<UniquePtr<SharedUniqueObject>>::new();
1549
1550            let cpp_raw1 = cpp_create_unique_object(1, destroyed1.as_ptr() as *mut bool);
1551            let cpp_raw2 = cpp_create_unique_object(2, destroyed2.as_ptr() as *mut bool);
1552
1553            let obj1 = UniquePtr::from_raw(cpp_raw1 as *mut SharedUniqueObject);
1554            let obj2 = UniquePtr::from_raw(cpp_raw2 as *mut SharedUniqueObject);
1555
1556            list.push_front(obj1);
1557            list.push_front(obj2);
1558
1559            assert!(!destroyed1.load(Ordering::Relaxed));
1560            assert!(!destroyed2.load(Ordering::Relaxed));
1561
1562            // Pop one
1563            let popped = list.pop_front();
1564            assert!(popped.is_some());
1565            assert_eq!(popped.as_ref().unwrap().value, 2);
1566
1567            // Drop popped -> should destroy in C++!
1568            drop(popped);
1569            assert!(!destroyed1.load(Ordering::Relaxed));
1570            assert!(destroyed2.load(Ordering::Relaxed));
1571
1572            // Drop list -> should destroy remaining in C++!
1573        }
1574        assert!(destroyed1.load(Ordering::Relaxed));
1575    }
1576
1577    #[test]
1578    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1579    fn test_interop_cpp_list_rust_unique_objects() {
1580        let destroyed1 = Arc::new(AtomicBool::new(false));
1581        let destroyed2 = Arc::new(AtomicBool::new(false));
1582
1583        unsafe {
1584            let cpp_list = cpp_sll_create_unique_list();
1585            assert!(cpp_sll_unique_list_is_empty(cpp_list));
1586
1587            let obj1 = UniquePtr::try_new(SharedUniqueObject::new(1)).unwrap();
1588            let obj2 = UniquePtr::try_new(SharedUniqueObject::new(2)).unwrap();
1589
1590            // Set destruction flags
1591            let raw1 = UniquePtr::as_ptr(&obj1) as *mut SharedUniqueObject;
1592            (*raw1).destruction_flag = destroyed1.as_ptr() as *mut bool;
1593            let raw2 = UniquePtr::as_ptr(&obj2) as *mut SharedUniqueObject;
1594            (*raw2).destruction_flag = destroyed2.as_ptr() as *mut bool;
1595
1596            // Push to C++ list (transfers ownership)
1597            cpp_sll_unique_list_push_front(cpp_list, UniquePtr::into_raw(obj1) as *mut c_void);
1598            cpp_sll_unique_list_push_front(cpp_list, UniquePtr::into_raw(obj2) as *mut c_void);
1599
1600            assert!(!destroyed1.load(Ordering::Relaxed));
1601            assert!(!destroyed2.load(Ordering::Relaxed));
1602
1603            // Pop one from C++
1604            let popped = cpp_sll_unique_list_pop_front(cpp_list);
1605            assert!(!popped.is_null());
1606            assert_eq!(cpp_get_unique_object_value(popped), 2);
1607
1608            // Convert back to Rust UniquePtr and drop -> should free in Rust!
1609            let popped_rust = UniquePtr::from_raw(popped as *mut SharedUniqueObject);
1610            drop(popped_rust);
1611            assert!(!destroyed1.load(Ordering::Relaxed));
1612            assert!(destroyed2.load(Ordering::Relaxed));
1613
1614            // Destroy C++ list -> should destroy remaining in Rust!
1615            cpp_sll_destroy_unique_list(cpp_list);
1616        }
1617        assert!(destroyed1.load(Ordering::Relaxed));
1618    }
1619
1620    #[test]
1621    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1622    fn test_interop_rust_list_cpp_ref_objects() {
1623        let destroyed1 = AtomicBool::new(false);
1624        let destroyed2 = AtomicBool::new(false);
1625
1626        unsafe {
1627            let mut list = SinglyLinkedList::<RefPtr<SharedRefObject>>::new();
1628
1629            let cpp_raw1 = cpp_create_ref_object(1, destroyed1.as_ptr() as *mut bool);
1630            let cpp_raw2 = cpp_create_ref_object(2, destroyed2.as_ptr() as *mut bool);
1631
1632            let obj1 = RefPtr::from_raw(cpp_raw1 as *mut SharedRefObject);
1633            let obj2 = RefPtr::from_raw(cpp_raw2 as *mut SharedRefObject);
1634
1635            list.push_front(obj1);
1636            list.push_front(obj2);
1637
1638            assert!(!destroyed1.load(Ordering::Relaxed));
1639            assert!(!destroyed2.load(Ordering::Relaxed));
1640
1641            // Pop one
1642            let popped = list.pop_front();
1643            assert!(popped.is_some());
1644            assert_eq!(popped.as_ref().unwrap().value, 2);
1645
1646            // Drop popped -> should destroy in C++!
1647            drop(popped);
1648            assert!(!destroyed1.load(Ordering::Relaxed));
1649            assert!(destroyed2.load(Ordering::Relaxed));
1650
1651            // Drop list -> should destroy remaining in C++!
1652        }
1653        assert!(destroyed1.load(Ordering::Relaxed));
1654    }
1655
1656    #[test]
1657    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1658    fn test_interop_cpp_list_rust_ref_objects() {
1659        let destroyed1 = Arc::new(AtomicBool::new(false));
1660        let destroyed2 = Arc::new(AtomicBool::new(false));
1661
1662        unsafe {
1663            let cpp_list = cpp_sll_create_ref_list();
1664            assert!(cpp_sll_ref_list_is_empty(cpp_list));
1665
1666            let obj1 = SharedRefObject::new_ref_counted(1);
1667            let obj2 = SharedRefObject::new_ref_counted(2);
1668
1669            // Set destruction flags
1670            let raw1 = RefPtr::as_ptr(&obj1) as *mut SharedRefObject;
1671            (*raw1).destruction_flag = destroyed1.as_ptr() as *mut bool;
1672            let raw2 = RefPtr::as_ptr(&obj2) as *mut SharedRefObject;
1673            (*raw2).destruction_flag = destroyed2.as_ptr() as *mut bool;
1674
1675            // Push to C++ list (transfers ownership)
1676            cpp_sll_ref_list_push_front(
1677                cpp_list,
1678                RefPtr::into_raw(obj1) as *mut SharedRefObject as *mut c_void,
1679            );
1680            cpp_sll_ref_list_push_front(
1681                cpp_list,
1682                RefPtr::into_raw(obj2) as *mut SharedRefObject as *mut c_void,
1683            );
1684
1685            assert!(!destroyed1.load(Ordering::Relaxed));
1686            assert!(!destroyed2.load(Ordering::Relaxed));
1687
1688            // Pop one from C++
1689            let popped = cpp_sll_ref_list_pop_front(cpp_list);
1690            assert!(!popped.is_null());
1691            assert_eq!(cpp_get_ref_object_value(popped), 2);
1692
1693            // Convert back to Rust RefPtr and drop -> should free in Rust!
1694            let popped_rust = RefPtr::from_raw(popped as *mut SharedRefObject);
1695            drop(popped_rust);
1696            assert!(!destroyed1.load(Ordering::Relaxed));
1697            assert!(destroyed2.load(Ordering::Relaxed));
1698
1699            // Destroy C++ list -> should destroy remaining in Rust!
1700            cpp_sll_destroy_ref_list(cpp_list);
1701        }
1702        assert!(destroyed1.load(Ordering::Relaxed));
1703    }
1704}
fbl/singly_linked_list.rs

fbl/
singly_linked_list.rs
