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 let Some(_) = self.pop_front() {}
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            if f(head_ref) {
399                return self.pop_front();
400            }
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            if f(head_ref) {
451                let old_head = self.pop_front().unwrap();
452                // SAFETY: `value` is a valid pointer that will outlive its reference from this
453                // list.
454                unsafe { self.push_front_raw(value) };
455                return Some(old_head);
456            }
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
572/// An iterator over the elements of a `SinglyLinkedList`.
573pub struct Iterator<'a, P, Tag = DefaultObjectTag>
574where
575    P: PtrTraits,
576    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
577{
578    current: *mut P::Target,
579    _phantom: core::marker::PhantomData<&'a (P, Tag)>,
580}
581
582impl<'a, P, Tag> Iterator<'a, P, Tag>
583where
584    P: PtrTraits,
585    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
586{
587    fn new(current: *mut P::Target) -> Self {
588        Self { current, _phantom: core::marker::PhantomData }
589    }
590}
591
592impl<'a, P, Tag> core::iter::Iterator for Iterator<'a, P, Tag>
593where
594    P: PtrTraits,
595    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
596{
597    type Item = &'a P::Target;
598
599    fn next(&mut self) -> Option<Self::Item> {
600        if crate::is_sentinel_ptr(self.current) {
601            None
602        } else {
603            // SAFETY: `self.current` is not a sentinel, so it is a valid, aligned pointer to an element.
604            // The list is guaranteed to be immutable for the lifetime `'a` of the iterator.
605            let current = unsafe { &*self.current };
606            // SAFETY: `current` is a valid reference, so we can safely read `next` from its node.
607            self.current = unsafe { *current.get_node().next.get() };
608            Some(current)
609        }
610    }
611}
612
613impl<'a, P, Tag> Iterator<'a, P, Tag>
614where
615    P: PtrTraits,
616    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
617{
618    /// Creates an iterator starting from a specific element.
619    ///
620    /// # Panics
621    ///
622    /// Panics if the object is not in a container.
623    pub fn from_element(obj: &'a P::Target) -> Self {
624        assert!(obj.get_node().in_container(), "Object must be in a container");
625        Self { current: obj as *const _ as *mut _, _phantom: core::marker::PhantomData }
626    }
627}
628
629/// A cursor that can be used to iterate and modify a `SinglyLinkedList`.
630pub struct CursorMut<'a, P, Tag = DefaultObjectTag, S = NonTrackingSize>
631where
632    P: PtrTraits,
633    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
634    S: SizeTracker,
635{
636    list: &'a mut SinglyLinkedList<P, Tag, S>,
637    current: *mut P::Target,
638}
639
640impl<'a, P, Tag, S> CursorMut<'a, P, Tag, S>
641where
642    P: PtrTraits,
643    P::Target: SinglyLinkedListContainable<P::Target, Tag>,
644    S: SizeTracker,
645{
646    /// Returns a reference to the element at the current position.
647    pub fn get(&self) -> Option<&P::Target> {
648        if crate::is_sentinel_ptr(self.current) {
649            None
650        } else {
651            // SAFETY: `self.current` is not a sentinel, so it is a valid pointer to an element.
652            Some(unsafe { &*self.current })
653        }
654    }
655
656    /// Moves the cursor to the next element. Returns true if the cursor is now at a valid element.
657    pub fn move_next(&mut self) -> bool {
658        if crate::is_sentinel_ptr(self.current) {
659            return false;
660        }
661        // SAFETY: `self.current` is valid.
662        let node = unsafe { self.list.get_node_ref(self.current) };
663        self.current = node.get_next();
664        !crate::is_sentinel_ptr(self.current)
665    }
666
667    /// Returns a reference to the element after the current position.
668    pub fn get_next(&self) -> Option<&P::Target> {
669        if crate::is_sentinel_ptr(self.current) {
670            return None;
671        }
672        // SAFETY: `self.current` is valid.
673        let node = unsafe { self.list.get_node_ref(self.current) };
674        let next_ptr = node.get_next();
675        if crate::is_sentinel_ptr(next_ptr) {
676            None
677        } else {
678            // SAFETY: `next_ptr` is not sentinel, so it is a valid pointer.
679            unsafe { Some(&*next_ptr) }
680        }
681    }
682
683    /// Inserts a new element after the current position.
684    pub fn insert_after(&mut self, ptr: P)
685    where
686        P: ManagedPtr,
687    {
688        assert!(!crate::is_sentinel_ptr(self.current), "Cannot insert after end sentinel");
689        // SAFETY: `self.current` is a valid pointer to an element in the list, and `ptr` is managed.
690        unsafe { self.list.insert_after_raw(self.current, ptr) }
691    }
692
693    /// Erases the element after the current position. Returns the erased element.
694    pub fn erase_next(&mut self) -> Option<P> {
695        assert!(!crate::is_sentinel_ptr(self.current), "Cannot erase next of end sentinel");
696        // SAFETY: `self.current` is a valid pointer to an element in the list.
697        unsafe { self.list.erase_next_raw(self.current) }
698    }
699
700    /// Replaces the element after the current position. Returns the replaced element.
701    ///
702    /// # Panics
703    ///
704    /// Panics if the object is already in a container.
705    ///
706    /// # Safety
707    ///
708    /// The caller must ensure that `value` is a valid pointer to a `T` and that the object outlives
709    /// the reference from the list.
710    pub unsafe fn replace_next_raw(&mut self, value: P) -> Option<P> {
711        debug_assert!(!crate::is_sentinel_ptr(self.current), "Cannot replace next of end sentinel");
712
713        // SAFETY: `self.current` is valid.
714        let current_node = unsafe { self.list.get_node_ref(self.current) };
715        let next_ptr = current_node.get_next();
716        if crate::is_sentinel_ptr(next_ptr) {
717            return None;
718        }
719
720        let value_raw = P::into_raw(value);
721        // SAFETY: `value_raw` is valid.
722        let value_node = unsafe { self.list.get_node_ref(value_raw) };
723        assert!(!value_node.in_container());
724
725        // SAFETY: `next_ptr` is valid.
726        let next_node = unsafe { self.list.get_node_ref(next_ptr) };
727
728        value_node.set_next(next_node.get_next());
729        current_node.set_next(value_raw);
730        next_node.set_next(core::ptr::null_mut());
731
732        // SAFETY: `next_ptr` was replaced, safe to reconstruct.
733        Some(unsafe { P::from_raw(next_ptr) })
734    }
735}
736
737impl<P, Tag, S> core::fmt::Debug for SinglyLinkedList<P, Tag, S>
738where
739    P: PtrTraits,
740    P::Target: SinglyLinkedListContainable<P::Target, Tag> + core::fmt::Debug,
741    S: SizeTracker,
742{
743    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
744        f.debug_list().entries(self.iter()).finish()
745    }
746}
747
748#[cfg(test)]
749mod tests {
750    extern crate alloc;
751    use super::*;
752    use crate::intrusive_container_test_support::*;
753    use crate::ref_ptr::RefPtr;
754    use crate::unique_ptr::UniquePtr;
755    use alloc::sync::Arc;
756    use core::ffi::c_void;
757    use core::sync::atomic::{AtomicBool, Ordering};
758
759    // Dummy type to satisfy trait bounds for static asserts.
760    struct DummyTarget;
761    impl SinglyLinkedListContainable<DummyTarget, DefaultObjectTag> for DummyTarget {
762        fn get_node(&self) -> &SinglyLinkedListNode<DummyTarget> {
763            unreachable!()
764        }
765    }
766
767    zr::static_assert!(
768        core::mem::size_of::<SinglyLinkedListNode<()>>() == core::mem::size_of::<*mut ()>()
769    );
770    zr::static_assert!(
771        core::mem::align_of::<SinglyLinkedListNode<()>>() == core::mem::align_of::<*mut ()>()
772    );
773
774    zr::static_assert!(
775        core::mem::size_of::<SinglyLinkedList<*mut DummyTarget>>()
776            == core::mem::size_of::<*mut DummyTarget>()
777    );
778    zr::static_assert!(
779        core::mem::align_of::<SinglyLinkedList<*mut DummyTarget>>()
780            == core::mem::align_of::<*mut DummyTarget>()
781    );
782
783    zr::static_assert!(
784        core::mem::size_of::<SinglyLinkedList<*mut DummyTarget, DefaultObjectTag, TrackingSize>>()
785            == 2 * core::mem::size_of::<*mut DummyTarget>()
786    );
787    zr::static_assert!(
788        core::mem::align_of::<SinglyLinkedList<*mut DummyTarget, DefaultObjectTag, TrackingSize>>()
789            == core::mem::align_of::<*mut DummyTarget>()
790    );
791
792    zr::static_assert!(
793        core::mem::size_of::<Iterator<'_, *mut DummyTarget>>()
794            == core::mem::size_of::<*mut DummyTarget>()
795    );
796    zr::static_assert!(
797        core::mem::align_of::<Iterator<'_, *mut DummyTarget>>()
798            == core::mem::align_of::<*mut DummyTarget>()
799    );
800
801    macro_rules! generate_list_tests {
802        ($mod_name:ident, $ptr_type:ty, $factory_type:ty, $get_val:expr, $push:expr) => {
803            mod $mod_name {
804                use super::*;
805
806                #[test]
807                fn test_basic_ops() {
808                    let mut factory = <$factory_type>::new();
809                    let mut list = SinglyLinkedList::<$ptr_type>::new();
810                    assert!(list.is_empty());
811
812                    let obj1 = factory.create(1);
813                    let obj2 = factory.create(2);
814                    let obj3 = factory.create(3);
815
816                    $push(&mut list, obj1);
817                    $push(&mut list, obj2);
818                    $push(&mut list, obj3);
819
820                    assert!(!list.is_empty());
821
822                    let mut iter = list.iter();
823                    assert_eq!(iter.next().unwrap().value, 3);
824                    assert_eq!(iter.next().unwrap().value, 2);
825                    assert_eq!(iter.next().unwrap().value, 1);
826                    assert!(iter.next().is_none());
827
828                    assert_eq!($get_val(list.pop_front().unwrap().get_ref()), 3);
829                    assert_eq!($get_val(list.pop_front().unwrap().get_ref()), 2);
830                    assert_eq!($get_val(list.pop_front().unwrap().get_ref()), 1);
831
832                    assert!(list.is_empty());
833                }
834
835                #[test]
836                fn test_insert_after() {
837                    let mut factory = <$factory_type>::new();
838                    let mut list = SinglyLinkedList::<$ptr_type>::new();
839
840                    let obj1 = factory.create(1);
841                    let raw1 = <$ptr_type as PtrTraits>::into_raw(obj1);
842                    $push(&mut list, unsafe { <$ptr_type as PtrTraits>::from_raw(raw1) });
843
844                    let obj2 = factory.create(2);
845                    let raw2 = <$ptr_type as PtrTraits>::into_raw(obj2);
846                    unsafe {
847                        list.insert_after_raw(raw1, <$ptr_type as PtrTraits>::from_raw(raw2));
848                    }
849
850                    let obj3 = factory.create(3);
851                    unsafe {
852                        list.insert_after_raw(raw2, obj3);
853                    }
854
855                    let mut iter = list.iter();
856                    assert_eq!(iter.next().unwrap().value, 1);
857                    assert_eq!(iter.next().unwrap().value, 2);
858                    assert_eq!(iter.next().unwrap().value, 3);
859                    assert!(iter.next().is_none());
860
861                    // Cleanup
862                    list.clear();
863                }
864
865                #[test]
866                fn test_clear() {
867                    let mut factory = <$factory_type>::new();
868                    let mut list = SinglyLinkedList::<$ptr_type>::new();
869                    let obj1 = factory.create(1);
870                    let obj2 = factory.create(2);
871
872                    $push(&mut list, obj1);
873                    $push(&mut list, obj2);
874
875                    assert!(!list.is_empty());
876                    list.clear();
877                    assert!(list.is_empty());
878                }
879
880                #[test]
881                fn test_erase_next() {
882                    let mut factory = <$factory_type>::new();
883                    let mut list = SinglyLinkedList::<$ptr_type>::new();
884
885                    let obj1 = factory.create(1);
886                    let raw1 = <$ptr_type as PtrTraits>::into_raw(obj1);
887                    $push(&mut list, unsafe { <$ptr_type as PtrTraits>::from_raw(raw1) });
888
889                    let obj2 = factory.create(2);
890                    let raw2 = <$ptr_type as PtrTraits>::into_raw(obj2);
891                    unsafe {
892                        list.insert_after_raw(raw1, <$ptr_type as PtrTraits>::from_raw(raw2));
893                    }
894
895                    let obj3 = factory.create(3);
896                    unsafe {
897                        list.insert_after_raw(raw2, obj3);
898                    }
899
900                    let erased = unsafe { list.erase_next_raw(raw1) };
901                    assert_eq!($get_val(erased.unwrap().get_ref()), 2);
902
903                    let mut iter = list.iter();
904                    assert_eq!(iter.next().unwrap().value, 1);
905                    assert_eq!(iter.next().unwrap().value, 3);
906                    assert!(iter.next().is_none());
907
908                    // Cleanup
909                    list.clear();
910                }
911
912                #[test]
913                fn test_swap() {
914                    let mut factory = <$factory_type>::new();
915                    let mut list1 = SinglyLinkedList::<$ptr_type>::new();
916                    let mut list2 = SinglyLinkedList::<$ptr_type>::new();
917
918                    let obj1 = factory.create(1);
919                    let obj2 = factory.create(2);
920
921                    $push(&mut list1, obj1);
922                    $push(&mut list2, obj2);
923
924                    list1.swap(&mut list2);
925
926                    assert_eq!($get_val(list1.pop_front().unwrap().get_ref()), 2);
927                    assert_eq!($get_val(list2.pop_front().unwrap().get_ref()), 1);
928                }
929
930                #[test]
931                fn test_size_slow() {
932                    let mut factory = <$factory_type>::new();
933                    let mut list = SinglyLinkedList::<$ptr_type>::new();
934                    let obj1 = factory.create(1);
935                    let obj2 = factory.create(2);
936
937                    assert_eq!(list.size_slow(), 0);
938
939                    $push(&mut list, obj1);
940                    assert_eq!(list.size_slow(), 1);
941                    $push(&mut list, obj2);
942                    assert_eq!(list.size_slow(), 2);
943
944                    list.pop_front();
945                    assert_eq!(list.size_slow(), 1);
946
947                    list.pop_front();
948                    assert_eq!(list.size_slow(), 0);
949                }
950
951                #[test]
952                fn test_find_if() {
953                    let mut factory = <$factory_type>::new();
954                    let mut list = SinglyLinkedList::<$ptr_type>::new();
955                    let obj1 = factory.create(1);
956                    let obj2 = factory.create(2);
957
958                    $push(&mut list, obj1);
959                    $push(&mut list, obj2);
960
961                    let found = list.find_if(|o| o.value == 1);
962                    assert!(found.is_some());
963                    assert_eq!(found.unwrap().value, 1);
964
965                    let found = list.find_if(|o| o.value == 3);
966                    assert!(found.is_none());
967
968                    // Cleanup
969                    list.clear();
970                }
971
972                #[test]
973                fn test_erase_if() {
974                    let mut factory = <$factory_type>::new();
975                    let mut list = SinglyLinkedList::<$ptr_type>::new();
976                    let obj1 = factory.create(1);
977                    let obj2 = factory.create(2);
978                    let obj3 = factory.create(3);
979
980                    $push(&mut list, obj1);
981                    $push(&mut list, obj2);
982                    $push(&mut list, obj3);
983
984                    // list: 3 -> 2 -> 1
985
986                    let erased = list.erase_if(|o| o.value == 2);
987                    assert!(erased.is_some());
988                    assert_eq!($get_val(erased.unwrap().get_ref()), 2);
989
990                    let mut iter = list.iter();
991                    assert_eq!(iter.next().unwrap().value, 3);
992                    assert_eq!(iter.next().unwrap().value, 1);
993                    assert!(iter.next().is_none());
994
995                    // Cleanup
996                    list.clear();
997                }
998
999                #[test]
1000                fn test_replace_if() {
1001                    let mut factory = <$factory_type>::new();
1002                    let mut list = SinglyLinkedList::<$ptr_type>::new();
1003                    let obj1 = factory.create(1);
1004                    let obj2 = factory.create(2);
1005                    let obj3 = factory.create(3);
1006
1007                    $push(&mut list, obj1);
1008                    $push(&mut list, obj2);
1009
1010                    // list: 2 -> 1
1011
1012                    let replaced = unsafe { list.replace_if_raw(|o| o.value == 2, obj3) };
1013                    assert_eq!($get_val(replaced.unwrap().get_ref()), 2);
1014
1015                    let mut iter = list.iter();
1016                    assert_eq!(iter.next().unwrap().value, 3);
1017                    assert_eq!(iter.next().unwrap().value, 1);
1018                    assert!(iter.next().is_none());
1019
1020                    // Cleanup
1021                    list.clear();
1022                }
1023
1024                #[test]
1025                fn test_split_after() {
1026                    let mut factory = <$factory_type>::new();
1027                    let mut list = SinglyLinkedList::<$ptr_type>::new();
1028                    let obj1 = factory.create(1);
1029                    let obj2 = factory.create(2);
1030                    let obj3 = factory.create(3);
1031
1032                    $push(&mut list, obj1);
1033                    $push(&mut list, obj2);
1034                    $push(&mut list, obj3);
1035
1036                    // list: 3 -> 2 -> 1
1037
1038                    let raw_pos = {
1039                        let found = list.find_if(|o| o.value == 2).unwrap();
1040                        found as *const <$ptr_type as PtrTraits>::Target
1041                            as *mut <$ptr_type as PtrTraits>::Target
1042                    };
1043
1044                    let mut other = unsafe { list.split_after_raw(raw_pos) };
1045
1046                    // list should be 3 -> 2
1047                    // other should be 1
1048
1049                    assert_eq!(list.size_slow(), 2);
1050                    assert_eq!(other.size_slow(), 1);
1051
1052                    let mut iter = list.iter();
1053                    assert_eq!(iter.next().unwrap().value, 3);
1054                    assert_eq!(iter.next().unwrap().value, 2);
1055                    assert!(iter.next().is_none());
1056
1057                    let mut iter = other.iter();
1058                    assert_eq!(iter.next().unwrap().value, 1);
1059                    assert!(iter.next().is_none());
1060
1061                    // Cleanup
1062                    list.clear();
1063                    other.clear();
1064                }
1065            }
1066        };
1067    }
1068
1069    #[derive(fbl::Recyclable, crate::SinglyLinkedListContainable)]
1070    struct TestObject {
1071        value: i32,
1072        #[sll_node]
1073        node: SinglyLinkedListNode<TestObject>,
1074    }
1075
1076    impl TestObject {
1077        fn new(value: i32) -> Self {
1078            Self { value, node: SinglyLinkedListNode::new() }
1079        }
1080    }
1081
1082    impl TestValue for TestObject {
1083        fn new(value: i32) -> Self {
1084            Self::new(value)
1085        }
1086    }
1087
1088    generate_list_tests!(
1089        raw_ptr_tests,
1090        *mut TestObject,
1091        RawFactory<TestObject>,
1092        |p: &TestObject| p.value,
1093        |list: &mut SinglyLinkedList<*mut TestObject>, obj| unsafe {
1094            list.push_front_raw(obj);
1095        }
1096    );
1097
1098    #[derive(fbl::Recyclable, crate::SinglyLinkedListContainable)]
1099    struct UniqueTestObject {
1100        value: i32,
1101        #[sll_node]
1102        node: SinglyLinkedListNode<UniqueTestObject>,
1103    }
1104
1105    impl UniqueTestObject {
1106        fn new(value: i32) -> Self {
1107            Self { value, node: SinglyLinkedListNode::new() }
1108        }
1109    }
1110
1111    impl TestValue for UniqueTestObject {
1112        fn new(value: i32) -> Self {
1113            Self::new(value)
1114        }
1115    }
1116
1117    generate_list_tests!(
1118        unique_ptr_tests,
1119        UniquePtr<UniqueTestObject>,
1120        UniqueFactory<UniqueTestObject>,
1121        |p: &UniqueTestObject| p.value,
1122        |list: &mut SinglyLinkedList<UniquePtr<UniqueTestObject>>, obj| list.push_front(obj)
1123    );
1124
1125    #[fbl::ref_counted]
1126    #[derive(crate::SinglyLinkedListContainable, crate::Recyclable)]
1127    #[repr(C)]
1128    pub struct RefTestObject {
1129        value: i32,
1130        #[sll_node]
1131        node: SinglyLinkedListNode<RefTestObject>,
1132    }
1133
1134    impl TestValue for RefTestObject {
1135        fn new_ref_counted(value: i32) -> RefPtr<Self> {
1136            crate::make_ref_counted!(RefTestObject {
1137                value: value,
1138                node: SinglyLinkedListNode::new()
1139            })
1140            .unwrap()
1141        }
1142    }
1143
1144    generate_list_tests!(
1145        ref_ptr_tests,
1146        RefPtr<RefTestObject>,
1147        RefFactory<RefTestObject>,
1148        |p: &RefTestObject| p.value,
1149        |list: &mut SinglyLinkedList<RefPtr<RefTestObject>>, obj| list.push_front(obj)
1150    );
1151
1152    #[test]
1153    fn test_ref_ptr_identity() {
1154        let mut list = SinglyLinkedList::<RefPtr<RefTestObject>>::new();
1155        let obj =
1156            crate::make_ref_counted!(RefTestObject { value: 1, node: SinglyLinkedListNode::new() })
1157                .unwrap();
1158        list.push_front(obj.clone());
1159        let popped = list.pop_front().unwrap();
1160        assert!(RefPtr::ptr_eq(&popped, &obj));
1161    }
1162
1163    #[derive(crate::SinglyLinkedListContainable)]
1164    #[repr(C)]
1165    pub struct BaseItem {
1166        #[sll_node]
1167        node: SinglyLinkedListNode<BaseItem>,
1168    }
1169
1170    #[repr(C)]
1171    pub struct RustItem {
1172        base: BaseItem,
1173        value: i32,
1174    }
1175
1176    unsafe extern "C" {
1177        fn create_cpp_list() -> *mut c_void;
1178        fn destroy_cpp_list(list_ptr: *mut c_void);
1179        fn create_cpp_item(value: i32) -> *mut c_void;
1180        fn destroy_cpp_item(item_ptr: *mut c_void);
1181        fn list_push_front(list_ptr: *mut c_void, item_ptr: *mut c_void);
1182        fn list_pop_front(list_ptr: *mut c_void) -> *mut c_void;
1183        fn list_is_empty(list_ptr: *mut c_void) -> bool;
1184        fn get_cpp_item_value(item_ptr: *mut c_void) -> i32;
1185    }
1186
1187    #[test]
1188    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1189    fn test_cross_lang_list() {
1190        use core::ffi::c_void;
1191
1192        unsafe {
1193            let list_ptr = create_cpp_list();
1194            assert!(list_is_empty(list_ptr));
1195
1196            let cpp_item1 = create_cpp_item(10);
1197            let cpp_item2 = create_cpp_item(20);
1198
1199            let mut rust_item =
1200                RustItem { base: BaseItem { node: SinglyLinkedListNode::new() }, value: 30 };
1201
1202            // Push C++ item 1
1203            list_push_front(list_ptr, cpp_item1);
1204            assert!(!list_is_empty(list_ptr));
1205
1206            // Push Rust item
1207            list_push_front(list_ptr, &mut rust_item.base as *mut BaseItem as *mut c_void);
1208
1209            // Push C++ item 2
1210            list_push_front(list_ptr, cpp_item2);
1211
1212            // Now list should have: CppItem(20) -> RustItem(30) -> CppItem(10)
1213
1214            // Pop C++ item 2
1215            let popped = list_pop_front(list_ptr);
1216            assert_eq!(get_cpp_item_value(popped), 20);
1217            destroy_cpp_item(popped);
1218
1219            // Pop Rust item
1220            let popped = list_pop_front(list_ptr);
1221            let popped_rust_item = popped as *mut RustItem; // Safe because we know it's a RustItem
1222            assert_eq!((*popped_rust_item).value, 30);
1223
1224            // Pop C++ item 1
1225            let popped = list_pop_front(list_ptr);
1226            assert_eq!(get_cpp_item_value(popped), 10);
1227            destroy_cpp_item(popped);
1228
1229            assert!(list_is_empty(list_ptr));
1230            destroy_cpp_list(list_ptr);
1231        }
1232    }
1233
1234    struct Tag2;
1235
1236    #[fbl::ref_counted]
1237    #[derive(crate::SinglyLinkedListContainable, crate::Recyclable)]
1238    #[repr(C)]
1239    struct MultiListObject {
1240        value: i32,
1241        #[sll_node]
1242        node1: SinglyLinkedListNode<MultiListObject>,
1243        node2: SinglyLinkedListNode<MultiListObject>,
1244    }
1245
1246    impl SinglyLinkedListContainable<MultiListObject, Tag2> for MultiListObject {
1247        fn get_node(&self) -> &SinglyLinkedListNode<MultiListObject> {
1248            &self.node2
1249        }
1250    }
1251
1252    #[test]
1253    fn test_multiple_lists() {
1254        let mut list1 = SinglyLinkedList::<RefPtr<MultiListObject>, DefaultObjectTag>::new();
1255        let mut list2 = SinglyLinkedList::<RefPtr<MultiListObject>, Tag2>::new();
1256
1257        let obj1 = fbl::make_ref_counted!(MultiListObject {
1258            value: 1,
1259            node1: SinglyLinkedListNode::new(),
1260            node2: SinglyLinkedListNode::new(),
1261        })
1262        .unwrap();
1263
1264        let obj2 = fbl::make_ref_counted!(MultiListObject {
1265            value: 2,
1266            node1: SinglyLinkedListNode::new(),
1267            node2: SinglyLinkedListNode::new(),
1268        })
1269        .unwrap();
1270
1271        list1.push_front(obj1.clone());
1272        list1.push_front(obj2.clone());
1273
1274        list2.push_front(obj1.clone());
1275
1276        let mut iter1 = list1.iter();
1277        assert_eq!(iter1.next().unwrap().value, 2);
1278        assert_eq!(iter1.next().unwrap().value, 1);
1279        assert!(iter1.next().is_none());
1280
1281        let mut iter2 = list2.iter();
1282        assert_eq!(iter2.next().unwrap().value, 1);
1283        assert!(iter2.next().is_none());
1284
1285        assert_eq!(list1.pop_front().unwrap().value, 2);
1286        assert_eq!(list2.pop_front().unwrap().value, 1);
1287
1288        assert!(!list1.is_empty());
1289        assert!(list2.is_empty());
1290
1291        assert_eq!(list1.pop_front().unwrap().value, 1);
1292        assert!(list1.is_empty());
1293    }
1294
1295    #[test]
1296    fn test_size_tracking() {
1297        let mut list =
1298            SinglyLinkedList::<UniquePtr<UniqueTestObject>, DefaultObjectTag, TrackingSize>::new();
1299
1300        assert_eq!(list.size(), 0);
1301        list.push_front(UniquePtr::try_new(UniqueTestObject::new(1)).unwrap());
1302        assert_eq!(list.size(), 1);
1303        list.push_front(UniquePtr::try_new(UniqueTestObject::new(2)).unwrap());
1304        assert_eq!(list.size(), 2);
1305
1306        list.pop_front();
1307        assert_eq!(list.size(), 1);
1308        list.clear();
1309    }
1310
1311    #[test]
1312    fn test_split_after_size_tracking() {
1313        let mut list = SinglyLinkedList::<*mut TestObject, DefaultObjectTag, TrackingSize>::new();
1314        let mut obj1 = TestObject::new(1);
1315        let mut obj2 = TestObject::new(2);
1316        let mut obj3 = TestObject::new(3);
1317
1318        unsafe {
1319            list.push_front_raw(&mut obj1);
1320            list.push_front_raw(&mut obj2);
1321            list.push_front_raw(&mut obj3);
1322        }
1323
1324        assert_eq!(list.size(), 3);
1325
1326        let raw_pos = {
1327            let found = list.find_if(|o| o.value == 2).unwrap();
1328            found as *const TestObject as *mut TestObject
1329        };
1330
1331        let mut other = unsafe { list.split_after_raw(raw_pos) };
1332
1333        assert_eq!(list.size(), 2);
1334        assert_eq!(other.size(), 1);
1335
1336        list.clear();
1337        other.clear();
1338    }
1339
1340    #[test]
1341    fn test_lifecycle_on_drop() {
1342        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1343        let obj1 = UniquePtr::try_new(UniqueTestObject::new(1)).unwrap();
1344        let obj2 = UniquePtr::try_new(UniqueTestObject::new(2)).unwrap();
1345
1346        list.push_front(obj1);
1347        list.push_front(obj2);
1348
1349        drop(list);
1350    }
1351
1352    #[derive(crate::SinglyLinkedListContainable)]
1353    struct DerivedObject {
1354        value: i32,
1355        #[sll_node]
1356        node: SinglyLinkedListNode<DerivedObject>,
1357    }
1358
1359    impl DerivedObject {
1360        fn new(value: i32) -> Self {
1361            Self { value, node: SinglyLinkedListNode::new() }
1362        }
1363    }
1364
1365    #[test]
1366    fn test_derive_containable() {
1367        let mut list = SinglyLinkedList::<*mut DerivedObject>::new();
1368        let mut obj1 = DerivedObject::new(1);
1369        let mut obj2 = DerivedObject::new(2);
1370
1371        unsafe {
1372            list.push_front_raw(&mut obj1);
1373            list.push_front_raw(&mut obj2);
1374        }
1375
1376        let mut iter = list.iter();
1377        assert_eq!(iter.next().unwrap().value, 2);
1378        assert_eq!(iter.next().unwrap().value, 1);
1379        assert!(iter.next().is_none());
1380        list.clear();
1381    }
1382
1383    struct Tag3;
1384
1385    #[derive(crate::SinglyLinkedListContainable)]
1386    struct MultiDerivedObject {
1387        value: i32,
1388        #[sll_node]
1389        node1: SinglyLinkedListNode<MultiDerivedObject>,
1390        #[sll_node(tag = Tag3)]
1391        node2: SinglyLinkedListNode<MultiDerivedObject>,
1392    }
1393
1394    impl MultiDerivedObject {
1395        fn new(value: i32) -> Self {
1396            Self { value, node1: SinglyLinkedListNode::new(), node2: SinglyLinkedListNode::new() }
1397        }
1398    }
1399
1400    #[test]
1401    fn test_derive_containable_multi() {
1402        let mut list1 = SinglyLinkedList::<*mut MultiDerivedObject, DefaultObjectTag>::new();
1403        let mut list2 = SinglyLinkedList::<*mut MultiDerivedObject, Tag3>::new();
1404
1405        let mut obj1 = MultiDerivedObject::new(1);
1406        let mut obj2 = MultiDerivedObject::new(2);
1407
1408        unsafe {
1409            list1.push_front_raw(core::ptr::addr_of_mut!(obj1));
1410            list1.push_front_raw(core::ptr::addr_of_mut!(obj2));
1411
1412            list2.push_front_raw(core::ptr::addr_of_mut!(obj1));
1413        }
1414
1415        let mut iter1 = list1.iter();
1416        assert_eq!(iter1.next().unwrap().value, 2);
1417        assert_eq!(iter1.next().unwrap().value, 1);
1418
1419        let mut iter2 = list2.iter();
1420        assert_eq!(iter2.next().unwrap().value, 1);
1421
1422        list1.clear();
1423        list2.clear();
1424    }
1425
1426    #[test]
1427    fn test_retain() {
1428        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1429        list.push_front(UniquePtr::try_new(UniqueTestObject::new(3)).unwrap());
1430        list.push_front(UniquePtr::try_new(UniqueTestObject::new(2)).unwrap());
1431        list.push_front(UniquePtr::try_new(UniqueTestObject::new(1)).unwrap());
1432
1433        list.retain(|o| o.value % 2 != 0);
1434
1435        let mut iter = list.iter();
1436        assert_eq!(iter.next().unwrap().value, 1);
1437        assert_eq!(iter.next().unwrap().value, 3);
1438        assert!(iter.next().is_none());
1439        list.clear();
1440    }
1441
1442    #[test]
1443    fn test_cursor_mut() {
1444        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1445        let obj1 = UniquePtr::try_new(UniqueTestObject::new(1)).unwrap();
1446        let obj2 = UniquePtr::try_new(UniqueTestObject::new(2)).unwrap();
1447        let obj3 = UniquePtr::try_new(UniqueTestObject::new(3)).unwrap();
1448
1449        list.push_front(obj1);
1450        list.push_front(obj2);
1451
1452        let mut cursor = list.cursor_mut();
1453        assert_eq!(cursor.get().unwrap().value, 2);
1454
1455        cursor.insert_after(obj3);
1456
1457        assert!(cursor.move_next());
1458        assert_eq!(cursor.get().unwrap().value, 3);
1459
1460        assert!(cursor.move_next());
1461        assert_eq!(cursor.get().unwrap().value, 1);
1462
1463        assert!(!cursor.move_next());
1464
1465        // Reset cursor
1466        let mut cursor = list.cursor_mut();
1467        assert_eq!(cursor.get().unwrap().value, 2);
1468
1469        let erased = cursor.erase_next().unwrap();
1470        assert_eq!(erased.value, 3);
1471
1472        assert!(cursor.move_next());
1473        assert_eq!(cursor.get().unwrap().value, 1);
1474
1475        assert!(!cursor.move_next());
1476    }
1477
1478    #[test]
1479    fn test_iterator_from_element() {
1480        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1481        list.push_front(UniquePtr::try_new(UniqueTestObject::new(3)).unwrap());
1482        list.push_front(UniquePtr::try_new(UniqueTestObject::new(2)).unwrap());
1483        list.push_front(UniquePtr::try_new(UniqueTestObject::new(1)).unwrap());
1484
1485        let mut iter = list.iter();
1486        iter.next(); // obj1
1487        let obj2_ref = iter.next().unwrap();
1488
1489        let mut from_element_iter: Iterator<'_, UniquePtr<UniqueTestObject>> =
1490            Iterator::from_element(obj2_ref);
1491        assert_eq!(from_element_iter.next().unwrap().value, 2);
1492        assert_eq!(from_element_iter.next().unwrap().value, 3);
1493        assert!(from_element_iter.next().is_none());
1494
1495        list.clear();
1496    }
1497
1498    #[test]
1499    fn test_front_ops() {
1500        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1501        assert!(list.front().is_none());
1502
1503        list.push_front(UniquePtr::try_new(UniqueTestObject::new(1)).unwrap());
1504        assert_eq!(list.front().unwrap().value, 1);
1505
1506        list.push_front(UniquePtr::try_new(UniqueTestObject::new(2)).unwrap());
1507        assert_eq!(list.front().unwrap().value, 2);
1508
1509        list.clear();
1510    }
1511
1512    // SLL FFI Declarations
1513    unsafe extern "C" {
1514        // UniqueList Helpers
1515        fn cpp_sll_create_unique_list() -> *mut c_void;
1516        fn cpp_sll_destroy_unique_list(list: *mut c_void);
1517        fn cpp_sll_unique_list_push_front(list: *mut c_void, item: *mut c_void);
1518        fn cpp_sll_unique_list_pop_front(list: *mut c_void) -> *mut c_void;
1519        fn cpp_sll_unique_list_is_empty(list: *mut c_void) -> bool;
1520
1521        // RefList Helpers
1522        fn cpp_sll_create_ref_list() -> *mut c_void;
1523        fn cpp_sll_destroy_ref_list(list: *mut c_void);
1524        fn cpp_sll_ref_list_push_front(list: *mut c_void, item: *mut c_void);
1525        fn cpp_sll_ref_list_pop_front(list: *mut c_void) -> *mut c_void;
1526        fn cpp_sll_ref_list_is_empty(list: *mut c_void) -> bool;
1527
1528        // SharedUniqueObject Helpers (Defined in DLL tests C++ file)
1529        fn cpp_create_unique_object(value: i32, destruction_flag: *mut bool) -> *mut c_void;
1530        fn cpp_get_unique_object_value(obj: *mut c_void) -> i32;
1531
1532        // SharedRefObject Helpers (Defined in DLL tests C++ file)
1533        fn cpp_create_ref_object(value: i32, destruction_flag: *mut bool) -> *mut c_void;
1534        fn cpp_get_ref_object_value(obj: *mut c_void) -> i32;
1535    }
1536
1537    #[test]
1538    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1539    fn test_interop_rust_list_cpp_unique_objects() {
1540        let destroyed1 = AtomicBool::new(false);
1541        let destroyed2 = AtomicBool::new(false);
1542
1543        unsafe {
1544            let mut list = SinglyLinkedList::<UniquePtr<SharedUniqueObject>>::new();
1545
1546            let cpp_raw1 = cpp_create_unique_object(1, destroyed1.as_ptr() as *mut bool);
1547            let cpp_raw2 = cpp_create_unique_object(2, destroyed2.as_ptr() as *mut bool);
1548
1549            let obj1 = UniquePtr::from_raw(cpp_raw1 as *mut SharedUniqueObject);
1550            let obj2 = UniquePtr::from_raw(cpp_raw2 as *mut SharedUniqueObject);
1551
1552            list.push_front(obj1);
1553            list.push_front(obj2);
1554
1555            assert!(!destroyed1.load(Ordering::Relaxed));
1556            assert!(!destroyed2.load(Ordering::Relaxed));
1557
1558            // Pop one
1559            let popped = list.pop_front();
1560            assert!(popped.is_some());
1561            assert_eq!(popped.as_ref().unwrap().value, 2);
1562
1563            // Drop popped -> should destroy in C++!
1564            drop(popped);
1565            assert!(!destroyed1.load(Ordering::Relaxed));
1566            assert!(destroyed2.load(Ordering::Relaxed));
1567
1568            // Drop list -> should destroy remaining in C++!
1569        }
1570        assert!(destroyed1.load(Ordering::Relaxed));
1571    }
1572
1573    #[test]
1574    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1575    fn test_interop_cpp_list_rust_unique_objects() {
1576        let destroyed1 = Arc::new(AtomicBool::new(false));
1577        let destroyed2 = Arc::new(AtomicBool::new(false));
1578
1579        unsafe {
1580            let cpp_list = cpp_sll_create_unique_list();
1581            assert!(cpp_sll_unique_list_is_empty(cpp_list));
1582
1583            let obj1 = UniquePtr::try_new(SharedUniqueObject::new(1)).unwrap();
1584            let obj2 = UniquePtr::try_new(SharedUniqueObject::new(2)).unwrap();
1585
1586            // Set destruction flags
1587            let raw1 = UniquePtr::as_ptr(&obj1) as *mut SharedUniqueObject;
1588            (*raw1).destruction_flag = destroyed1.as_ptr() as *mut bool;
1589            let raw2 = UniquePtr::as_ptr(&obj2) as *mut SharedUniqueObject;
1590            (*raw2).destruction_flag = destroyed2.as_ptr() as *mut bool;
1591
1592            // Push to C++ list (transfers ownership)
1593            cpp_sll_unique_list_push_front(cpp_list, UniquePtr::into_raw(obj1) as *mut c_void);
1594            cpp_sll_unique_list_push_front(cpp_list, UniquePtr::into_raw(obj2) as *mut c_void);
1595
1596            assert!(!destroyed1.load(Ordering::Relaxed));
1597            assert!(!destroyed2.load(Ordering::Relaxed));
1598
1599            // Pop one from C++
1600            let popped = cpp_sll_unique_list_pop_front(cpp_list);
1601            assert!(!popped.is_null());
1602            assert_eq!(cpp_get_unique_object_value(popped), 2);
1603
1604            // Convert back to Rust UniquePtr and drop -> should free in Rust!
1605            let popped_rust = UniquePtr::from_raw(popped as *mut SharedUniqueObject);
1606            drop(popped_rust);
1607            assert!(!destroyed1.load(Ordering::Relaxed));
1608            assert!(destroyed2.load(Ordering::Relaxed));
1609
1610            // Destroy C++ list -> should destroy remaining in Rust!
1611            cpp_sll_destroy_unique_list(cpp_list);
1612        }
1613        assert!(destroyed1.load(Ordering::Relaxed));
1614    }
1615
1616    #[test]
1617    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1618    fn test_interop_rust_list_cpp_ref_objects() {
1619        let destroyed1 = AtomicBool::new(false);
1620        let destroyed2 = AtomicBool::new(false);
1621
1622        unsafe {
1623            let mut list = SinglyLinkedList::<RefPtr<SharedRefObject>>::new();
1624
1625            let cpp_raw1 = cpp_create_ref_object(1, destroyed1.as_ptr() as *mut bool);
1626            let cpp_raw2 = cpp_create_ref_object(2, destroyed2.as_ptr() as *mut bool);
1627
1628            let obj1 = RefPtr::from_raw(cpp_raw1 as *mut SharedRefObject);
1629            let obj2 = RefPtr::from_raw(cpp_raw2 as *mut SharedRefObject);
1630
1631            list.push_front(obj1);
1632            list.push_front(obj2);
1633
1634            assert!(!destroyed1.load(Ordering::Relaxed));
1635            assert!(!destroyed2.load(Ordering::Relaxed));
1636
1637            // Pop one
1638            let popped = list.pop_front();
1639            assert!(popped.is_some());
1640            assert_eq!(popped.as_ref().unwrap().value, 2);
1641
1642            // Drop popped -> should destroy in C++!
1643            drop(popped);
1644            assert!(!destroyed1.load(Ordering::Relaxed));
1645            assert!(destroyed2.load(Ordering::Relaxed));
1646
1647            // Drop list -> should destroy remaining in C++!
1648        }
1649        assert!(destroyed1.load(Ordering::Relaxed));
1650    }
1651
1652    #[test]
1653    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1654    fn test_interop_cpp_list_rust_ref_objects() {
1655        let destroyed1 = Arc::new(AtomicBool::new(false));
1656        let destroyed2 = Arc::new(AtomicBool::new(false));
1657
1658        unsafe {
1659            let cpp_list = cpp_sll_create_ref_list();
1660            assert!(cpp_sll_ref_list_is_empty(cpp_list));
1661
1662            let obj1 = SharedRefObject::new_ref_counted(1);
1663            let obj2 = SharedRefObject::new_ref_counted(2);
1664
1665            // Set destruction flags
1666            let raw1 = RefPtr::as_ptr(&obj1) as *mut SharedRefObject;
1667            (*raw1).destruction_flag = destroyed1.as_ptr() as *mut bool;
1668            let raw2 = RefPtr::as_ptr(&obj2) as *mut SharedRefObject;
1669            (*raw2).destruction_flag = destroyed2.as_ptr() as *mut bool;
1670
1671            // Push to C++ list (transfers ownership)
1672            cpp_sll_ref_list_push_front(
1673                cpp_list,
1674                RefPtr::into_raw(obj1) as *mut SharedRefObject as *mut c_void,
1675            );
1676            cpp_sll_ref_list_push_front(
1677                cpp_list,
1678                RefPtr::into_raw(obj2) as *mut SharedRefObject as *mut c_void,
1679            );
1680
1681            assert!(!destroyed1.load(Ordering::Relaxed));
1682            assert!(!destroyed2.load(Ordering::Relaxed));
1683
1684            // Pop one from C++
1685            let popped = cpp_sll_ref_list_pop_front(cpp_list);
1686            assert!(!popped.is_null());
1687            assert_eq!(cpp_get_ref_object_value(popped), 2);
1688
1689            // Convert back to Rust RefPtr and drop -> should free in Rust!
1690            let popped_rust = RefPtr::from_raw(popped as *mut SharedRefObject);
1691            drop(popped_rust);
1692            assert!(!destroyed1.load(Ordering::Relaxed));
1693            assert!(destroyed2.load(Ordering::Relaxed));
1694
1695            // Destroy C++ list -> should destroy remaining in Rust!
1696            cpp_sll_destroy_ref_list(cpp_list);
1697        }
1698        assert!(destroyed1.load(Ordering::Relaxed));
1699    }
1700}
fbl/singly_linked_list.rs

fbl/
singly_linked_list.rs
