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::<SinglyLinkedList<*mut DummyTarget>>()
769            == core::mem::size_of::<*mut DummyTarget>()
770    );
771    zr::static_assert!(
772        core::mem::align_of::<SinglyLinkedList<*mut DummyTarget>>()
773            == core::mem::align_of::<*mut DummyTarget>()
774    );
775
776    zr::static_assert!(
777        core::mem::size_of::<SinglyLinkedList<*mut DummyTarget, DefaultObjectTag, TrackingSize>>()
778            == 2 * core::mem::size_of::<*mut DummyTarget>()
779    );
780    zr::static_assert!(
781        core::mem::align_of::<SinglyLinkedList<*mut DummyTarget, DefaultObjectTag, TrackingSize>>()
782            == core::mem::align_of::<*mut DummyTarget>()
783    );
784
785    zr::static_assert!(
786        core::mem::size_of::<Iterator<'_, *mut DummyTarget>>()
787            == core::mem::size_of::<*mut DummyTarget>()
788    );
789    zr::static_assert!(
790        core::mem::align_of::<Iterator<'_, *mut DummyTarget>>()
791            == core::mem::align_of::<*mut DummyTarget>()
792    );
793
794    macro_rules! generate_list_tests {
795        ($mod_name:ident, $ptr_type:ty, $factory_type:ty, $get_val:expr, $push:expr) => {
796            mod $mod_name {
797                use super::*;
798
799                #[test]
800                fn test_basic_ops() {
801                    let mut factory = <$factory_type>::new();
802                    let mut list = SinglyLinkedList::<$ptr_type>::new();
803                    assert!(list.is_empty());
804
805                    let obj1 = factory.create(1);
806                    let obj2 = factory.create(2);
807                    let obj3 = factory.create(3);
808
809                    $push(&mut list, obj1);
810                    $push(&mut list, obj2);
811                    $push(&mut list, obj3);
812
813                    assert!(!list.is_empty());
814
815                    let mut iter = list.iter();
816                    assert_eq!(iter.next().unwrap().value, 3);
817                    assert_eq!(iter.next().unwrap().value, 2);
818                    assert_eq!(iter.next().unwrap().value, 1);
819                    assert!(iter.next().is_none());
820
821                    assert_eq!($get_val(list.pop_front().unwrap().get_ref()), 3);
822                    assert_eq!($get_val(list.pop_front().unwrap().get_ref()), 2);
823                    assert_eq!($get_val(list.pop_front().unwrap().get_ref()), 1);
824
825                    assert!(list.is_empty());
826                }
827
828                #[test]
829                fn test_insert_after() {
830                    let mut factory = <$factory_type>::new();
831                    let mut list = SinglyLinkedList::<$ptr_type>::new();
832
833                    let obj1 = factory.create(1);
834                    let raw1 = <$ptr_type as PtrTraits>::into_raw(obj1);
835                    $push(&mut list, unsafe { <$ptr_type as PtrTraits>::from_raw(raw1) });
836
837                    let obj2 = factory.create(2);
838                    let raw2 = <$ptr_type as PtrTraits>::into_raw(obj2);
839                    unsafe {
840                        list.insert_after_raw(raw1, <$ptr_type as PtrTraits>::from_raw(raw2));
841                    }
842
843                    let obj3 = factory.create(3);
844                    unsafe {
845                        list.insert_after_raw(raw2, obj3);
846                    }
847
848                    let mut iter = list.iter();
849                    assert_eq!(iter.next().unwrap().value, 1);
850                    assert_eq!(iter.next().unwrap().value, 2);
851                    assert_eq!(iter.next().unwrap().value, 3);
852                    assert!(iter.next().is_none());
853
854                    // Cleanup
855                    list.clear();
856                }
857
858                #[test]
859                fn test_clear() {
860                    let mut factory = <$factory_type>::new();
861                    let mut list = SinglyLinkedList::<$ptr_type>::new();
862                    let obj1 = factory.create(1);
863                    let obj2 = factory.create(2);
864
865                    $push(&mut list, obj1);
866                    $push(&mut list, obj2);
867
868                    assert!(!list.is_empty());
869                    list.clear();
870                    assert!(list.is_empty());
871                }
872
873                #[test]
874                fn test_erase_next() {
875                    let mut factory = <$factory_type>::new();
876                    let mut list = SinglyLinkedList::<$ptr_type>::new();
877
878                    let obj1 = factory.create(1);
879                    let raw1 = <$ptr_type as PtrTraits>::into_raw(obj1);
880                    $push(&mut list, unsafe { <$ptr_type as PtrTraits>::from_raw(raw1) });
881
882                    let obj2 = factory.create(2);
883                    let raw2 = <$ptr_type as PtrTraits>::into_raw(obj2);
884                    unsafe {
885                        list.insert_after_raw(raw1, <$ptr_type as PtrTraits>::from_raw(raw2));
886                    }
887
888                    let obj3 = factory.create(3);
889                    unsafe {
890                        list.insert_after_raw(raw2, obj3);
891                    }
892
893                    let erased = unsafe { list.erase_next_raw(raw1) };
894                    assert_eq!($get_val(erased.unwrap().get_ref()), 2);
895
896                    let mut iter = list.iter();
897                    assert_eq!(iter.next().unwrap().value, 1);
898                    assert_eq!(iter.next().unwrap().value, 3);
899                    assert!(iter.next().is_none());
900
901                    // Cleanup
902                    list.clear();
903                }
904
905                #[test]
906                fn test_swap() {
907                    let mut factory = <$factory_type>::new();
908                    let mut list1 = SinglyLinkedList::<$ptr_type>::new();
909                    let mut list2 = SinglyLinkedList::<$ptr_type>::new();
910
911                    let obj1 = factory.create(1);
912                    let obj2 = factory.create(2);
913
914                    $push(&mut list1, obj1);
915                    $push(&mut list2, obj2);
916
917                    list1.swap(&mut list2);
918
919                    assert_eq!($get_val(list1.pop_front().unwrap().get_ref()), 2);
920                    assert_eq!($get_val(list2.pop_front().unwrap().get_ref()), 1);
921                }
922
923                #[test]
924                fn test_size_slow() {
925                    let mut factory = <$factory_type>::new();
926                    let mut list = SinglyLinkedList::<$ptr_type>::new();
927                    let obj1 = factory.create(1);
928                    let obj2 = factory.create(2);
929
930                    assert_eq!(list.size_slow(), 0);
931
932                    $push(&mut list, obj1);
933                    assert_eq!(list.size_slow(), 1);
934                    $push(&mut list, obj2);
935                    assert_eq!(list.size_slow(), 2);
936
937                    list.pop_front();
938                    assert_eq!(list.size_slow(), 1);
939
940                    list.pop_front();
941                    assert_eq!(list.size_slow(), 0);
942                }
943
944                #[test]
945                fn test_find_if() {
946                    let mut factory = <$factory_type>::new();
947                    let mut list = SinglyLinkedList::<$ptr_type>::new();
948                    let obj1 = factory.create(1);
949                    let obj2 = factory.create(2);
950
951                    $push(&mut list, obj1);
952                    $push(&mut list, obj2);
953
954                    let found = list.find_if(|o| o.value == 1);
955                    assert!(found.is_some());
956                    assert_eq!(found.unwrap().value, 1);
957
958                    let found = list.find_if(|o| o.value == 3);
959                    assert!(found.is_none());
960
961                    // Cleanup
962                    list.clear();
963                }
964
965                #[test]
966                fn test_erase_if() {
967                    let mut factory = <$factory_type>::new();
968                    let mut list = SinglyLinkedList::<$ptr_type>::new();
969                    let obj1 = factory.create(1);
970                    let obj2 = factory.create(2);
971                    let obj3 = factory.create(3);
972
973                    $push(&mut list, obj1);
974                    $push(&mut list, obj2);
975                    $push(&mut list, obj3);
976
977                    // list: 3 -> 2 -> 1
978
979                    let erased = list.erase_if(|o| o.value == 2);
980                    assert!(erased.is_some());
981                    assert_eq!($get_val(erased.unwrap().get_ref()), 2);
982
983                    let mut iter = list.iter();
984                    assert_eq!(iter.next().unwrap().value, 3);
985                    assert_eq!(iter.next().unwrap().value, 1);
986                    assert!(iter.next().is_none());
987
988                    // Cleanup
989                    list.clear();
990                }
991
992                #[test]
993                fn test_replace_if() {
994                    let mut factory = <$factory_type>::new();
995                    let mut list = SinglyLinkedList::<$ptr_type>::new();
996                    let obj1 = factory.create(1);
997                    let obj2 = factory.create(2);
998                    let obj3 = factory.create(3);
999
1000                    $push(&mut list, obj1);
1001                    $push(&mut list, obj2);
1002
1003                    // list: 2 -> 1
1004
1005                    let replaced = unsafe { list.replace_if_raw(|o| o.value == 2, obj3) };
1006                    assert_eq!($get_val(replaced.unwrap().get_ref()), 2);
1007
1008                    let mut iter = list.iter();
1009                    assert_eq!(iter.next().unwrap().value, 3);
1010                    assert_eq!(iter.next().unwrap().value, 1);
1011                    assert!(iter.next().is_none());
1012
1013                    // Cleanup
1014                    list.clear();
1015                }
1016
1017                #[test]
1018                fn test_split_after() {
1019                    let mut factory = <$factory_type>::new();
1020                    let mut list = SinglyLinkedList::<$ptr_type>::new();
1021                    let obj1 = factory.create(1);
1022                    let obj2 = factory.create(2);
1023                    let obj3 = factory.create(3);
1024
1025                    $push(&mut list, obj1);
1026                    $push(&mut list, obj2);
1027                    $push(&mut list, obj3);
1028
1029                    // list: 3 -> 2 -> 1
1030
1031                    let raw_pos = {
1032                        let found = list.find_if(|o| o.value == 2).unwrap();
1033                        found as *const <$ptr_type as PtrTraits>::Target
1034                            as *mut <$ptr_type as PtrTraits>::Target
1035                    };
1036
1037                    let mut other = unsafe { list.split_after_raw(raw_pos) };
1038
1039                    // list should be 3 -> 2
1040                    // other should be 1
1041
1042                    assert_eq!(list.size_slow(), 2);
1043                    assert_eq!(other.size_slow(), 1);
1044
1045                    let mut iter = list.iter();
1046                    assert_eq!(iter.next().unwrap().value, 3);
1047                    assert_eq!(iter.next().unwrap().value, 2);
1048                    assert!(iter.next().is_none());
1049
1050                    let mut iter = other.iter();
1051                    assert_eq!(iter.next().unwrap().value, 1);
1052                    assert!(iter.next().is_none());
1053
1054                    // Cleanup
1055                    list.clear();
1056                    other.clear();
1057                }
1058            }
1059        };
1060    }
1061
1062    #[derive(fbl::Recyclable, crate::SinglyLinkedListContainable)]
1063    struct TestObject {
1064        value: i32,
1065        #[sll_node]
1066        node: SinglyLinkedListNode<TestObject>,
1067    }
1068
1069    impl TestObject {
1070        fn new(value: i32) -> Self {
1071            Self { value, node: SinglyLinkedListNode::new() }
1072        }
1073    }
1074
1075    impl TestValue for TestObject {
1076        fn new(value: i32) -> Self {
1077            Self::new(value)
1078        }
1079    }
1080
1081    generate_list_tests!(
1082        raw_ptr_tests,
1083        *mut TestObject,
1084        RawFactory<TestObject>,
1085        |p: &TestObject| p.value,
1086        |list: &mut SinglyLinkedList<*mut TestObject>, obj| unsafe {
1087            list.push_front_raw(obj);
1088        }
1089    );
1090
1091    #[derive(fbl::Recyclable, crate::SinglyLinkedListContainable)]
1092    struct UniqueTestObject {
1093        value: i32,
1094        #[sll_node]
1095        node: SinglyLinkedListNode<UniqueTestObject>,
1096    }
1097
1098    impl UniqueTestObject {
1099        fn new(value: i32) -> Self {
1100            Self { value, node: SinglyLinkedListNode::new() }
1101        }
1102    }
1103
1104    impl TestValue for UniqueTestObject {
1105        fn new(value: i32) -> Self {
1106            Self::new(value)
1107        }
1108    }
1109
1110    generate_list_tests!(
1111        unique_ptr_tests,
1112        UniquePtr<UniqueTestObject>,
1113        UniqueFactory<UniqueTestObject>,
1114        |p: &UniqueTestObject| p.value,
1115        |list: &mut SinglyLinkedList<UniquePtr<UniqueTestObject>>, obj| list.push_front(obj)
1116    );
1117
1118    #[fbl::ref_counted]
1119    #[derive(crate::SinglyLinkedListContainable, crate::Recyclable)]
1120    #[repr(C)]
1121    pub struct RefTestObject {
1122        value: i32,
1123        #[sll_node]
1124        node: SinglyLinkedListNode<RefTestObject>,
1125    }
1126
1127    impl TestValue for RefTestObject {
1128        fn new_ref_counted(value: i32) -> RefPtr<Self> {
1129            crate::make_ref_counted!(RefTestObject {
1130                value: value,
1131                node: SinglyLinkedListNode::new()
1132            })
1133            .unwrap()
1134        }
1135    }
1136
1137    generate_list_tests!(
1138        ref_ptr_tests,
1139        RefPtr<RefTestObject>,
1140        RefFactory<RefTestObject>,
1141        |p: &RefTestObject| p.value,
1142        |list: &mut SinglyLinkedList<RefPtr<RefTestObject>>, obj| list.push_front(obj)
1143    );
1144
1145    #[test]
1146    fn test_ref_ptr_identity() {
1147        let mut list = SinglyLinkedList::<RefPtr<RefTestObject>>::new();
1148        let obj =
1149            crate::make_ref_counted!(RefTestObject { value: 1, node: SinglyLinkedListNode::new() })
1150                .unwrap();
1151        list.push_front(obj.clone());
1152        let popped = list.pop_front().unwrap();
1153        assert!(RefPtr::ptr_eq(&popped, &obj));
1154    }
1155
1156    #[derive(crate::SinglyLinkedListContainable)]
1157    #[repr(C)]
1158    pub struct BaseItem {
1159        #[sll_node]
1160        node: SinglyLinkedListNode<BaseItem>,
1161    }
1162
1163    #[repr(C)]
1164    pub struct RustItem {
1165        base: BaseItem,
1166        value: i32,
1167    }
1168
1169    unsafe extern "C" {
1170        fn create_cpp_list() -> *mut c_void;
1171        fn destroy_cpp_list(list_ptr: *mut c_void);
1172        fn create_cpp_item(value: i32) -> *mut c_void;
1173        fn destroy_cpp_item(item_ptr: *mut c_void);
1174        fn list_push_front(list_ptr: *mut c_void, item_ptr: *mut c_void);
1175        fn list_pop_front(list_ptr: *mut c_void) -> *mut c_void;
1176        fn list_is_empty(list_ptr: *mut c_void) -> bool;
1177        fn get_cpp_item_value(item_ptr: *mut c_void) -> i32;
1178    }
1179
1180    #[test]
1181    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1182    fn test_cross_lang_list() {
1183        use core::ffi::c_void;
1184
1185        unsafe {
1186            let list_ptr = create_cpp_list();
1187            assert!(list_is_empty(list_ptr));
1188
1189            let cpp_item1 = create_cpp_item(10);
1190            let cpp_item2 = create_cpp_item(20);
1191
1192            let mut rust_item =
1193                RustItem { base: BaseItem { node: SinglyLinkedListNode::new() }, value: 30 };
1194
1195            // Push C++ item 1
1196            list_push_front(list_ptr, cpp_item1);
1197            assert!(!list_is_empty(list_ptr));
1198
1199            // Push Rust item
1200            list_push_front(list_ptr, &mut rust_item.base as *mut BaseItem as *mut c_void);
1201
1202            // Push C++ item 2
1203            list_push_front(list_ptr, cpp_item2);
1204
1205            // Now list should have: CppItem(20) -> RustItem(30) -> CppItem(10)
1206
1207            // Pop C++ item 2
1208            let popped = list_pop_front(list_ptr);
1209            assert_eq!(get_cpp_item_value(popped), 20);
1210            destroy_cpp_item(popped);
1211
1212            // Pop Rust item
1213            let popped = list_pop_front(list_ptr);
1214            let popped_rust_item = popped as *mut RustItem; // Safe because we know it's a RustItem
1215            assert_eq!((*popped_rust_item).value, 30);
1216
1217            // Pop C++ item 1
1218            let popped = list_pop_front(list_ptr);
1219            assert_eq!(get_cpp_item_value(popped), 10);
1220            destroy_cpp_item(popped);
1221
1222            assert!(list_is_empty(list_ptr));
1223            destroy_cpp_list(list_ptr);
1224        }
1225    }
1226
1227    struct Tag2;
1228
1229    #[fbl::ref_counted]
1230    #[derive(crate::SinglyLinkedListContainable, crate::Recyclable)]
1231    #[repr(C)]
1232    struct MultiListObject {
1233        value: i32,
1234        #[sll_node]
1235        node1: SinglyLinkedListNode<MultiListObject>,
1236        node2: SinglyLinkedListNode<MultiListObject>,
1237    }
1238
1239    impl SinglyLinkedListContainable<MultiListObject, Tag2> for MultiListObject {
1240        fn get_node(&self) -> &SinglyLinkedListNode<MultiListObject> {
1241            &self.node2
1242        }
1243    }
1244
1245    #[test]
1246    fn test_multiple_lists() {
1247        let mut list1 = SinglyLinkedList::<RefPtr<MultiListObject>, DefaultObjectTag>::new();
1248        let mut list2 = SinglyLinkedList::<RefPtr<MultiListObject>, Tag2>::new();
1249
1250        let obj1 = fbl::make_ref_counted!(MultiListObject {
1251            value: 1,
1252            node1: SinglyLinkedListNode::new(),
1253            node2: SinglyLinkedListNode::new(),
1254        })
1255        .unwrap();
1256
1257        let obj2 = fbl::make_ref_counted!(MultiListObject {
1258            value: 2,
1259            node1: SinglyLinkedListNode::new(),
1260            node2: SinglyLinkedListNode::new(),
1261        })
1262        .unwrap();
1263
1264        list1.push_front(obj1.clone());
1265        list1.push_front(obj2.clone());
1266
1267        list2.push_front(obj1.clone());
1268
1269        let mut iter1 = list1.iter();
1270        assert_eq!(iter1.next().unwrap().value, 2);
1271        assert_eq!(iter1.next().unwrap().value, 1);
1272        assert!(iter1.next().is_none());
1273
1274        let mut iter2 = list2.iter();
1275        assert_eq!(iter2.next().unwrap().value, 1);
1276        assert!(iter2.next().is_none());
1277
1278        assert_eq!(list1.pop_front().unwrap().value, 2);
1279        assert_eq!(list2.pop_front().unwrap().value, 1);
1280
1281        assert!(!list1.is_empty());
1282        assert!(list2.is_empty());
1283
1284        assert_eq!(list1.pop_front().unwrap().value, 1);
1285        assert!(list1.is_empty());
1286    }
1287
1288    #[test]
1289    fn test_size_tracking() {
1290        let mut list =
1291            SinglyLinkedList::<UniquePtr<UniqueTestObject>, DefaultObjectTag, TrackingSize>::new();
1292
1293        assert_eq!(list.size(), 0);
1294        list.push_front(UniquePtr::try_new(UniqueTestObject::new(1)).unwrap());
1295        assert_eq!(list.size(), 1);
1296        list.push_front(UniquePtr::try_new(UniqueTestObject::new(2)).unwrap());
1297        assert_eq!(list.size(), 2);
1298
1299        list.pop_front();
1300        assert_eq!(list.size(), 1);
1301        list.clear();
1302    }
1303
1304    #[test]
1305    fn test_split_after_size_tracking() {
1306        let mut list = SinglyLinkedList::<*mut TestObject, DefaultObjectTag, TrackingSize>::new();
1307        let mut obj1 = TestObject::new(1);
1308        let mut obj2 = TestObject::new(2);
1309        let mut obj3 = TestObject::new(3);
1310
1311        unsafe {
1312            list.push_front_raw(&mut obj1);
1313            list.push_front_raw(&mut obj2);
1314            list.push_front_raw(&mut obj3);
1315        }
1316
1317        assert_eq!(list.size(), 3);
1318
1319        let raw_pos = {
1320            let found = list.find_if(|o| o.value == 2).unwrap();
1321            found as *const TestObject as *mut TestObject
1322        };
1323
1324        let mut other = unsafe { list.split_after_raw(raw_pos) };
1325
1326        assert_eq!(list.size(), 2);
1327        assert_eq!(other.size(), 1);
1328
1329        list.clear();
1330        other.clear();
1331    }
1332
1333    #[test]
1334    fn test_lifecycle_on_drop() {
1335        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1336        let obj1 = UniquePtr::try_new(UniqueTestObject::new(1)).unwrap();
1337        let obj2 = UniquePtr::try_new(UniqueTestObject::new(2)).unwrap();
1338
1339        list.push_front(obj1);
1340        list.push_front(obj2);
1341
1342        drop(list);
1343    }
1344
1345    #[derive(crate::SinglyLinkedListContainable)]
1346    struct DerivedObject {
1347        value: i32,
1348        #[sll_node]
1349        node: SinglyLinkedListNode<DerivedObject>,
1350    }
1351
1352    impl DerivedObject {
1353        fn new(value: i32) -> Self {
1354            Self { value, node: SinglyLinkedListNode::new() }
1355        }
1356    }
1357
1358    #[test]
1359    fn test_derive_containable() {
1360        let mut list = SinglyLinkedList::<*mut DerivedObject>::new();
1361        let mut obj1 = DerivedObject::new(1);
1362        let mut obj2 = DerivedObject::new(2);
1363
1364        unsafe {
1365            list.push_front_raw(&mut obj1);
1366            list.push_front_raw(&mut obj2);
1367        }
1368
1369        let mut iter = list.iter();
1370        assert_eq!(iter.next().unwrap().value, 2);
1371        assert_eq!(iter.next().unwrap().value, 1);
1372        assert!(iter.next().is_none());
1373        list.clear();
1374    }
1375
1376    struct Tag3;
1377
1378    #[derive(crate::SinglyLinkedListContainable)]
1379    struct MultiDerivedObject {
1380        value: i32,
1381        #[sll_node]
1382        node1: SinglyLinkedListNode<MultiDerivedObject>,
1383        #[sll_node(tag = Tag3)]
1384        node2: SinglyLinkedListNode<MultiDerivedObject>,
1385    }
1386
1387    impl MultiDerivedObject {
1388        fn new(value: i32) -> Self {
1389            Self { value, node1: SinglyLinkedListNode::new(), node2: SinglyLinkedListNode::new() }
1390        }
1391    }
1392
1393    #[test]
1394    fn test_derive_containable_multi() {
1395        let mut list1 = SinglyLinkedList::<*mut MultiDerivedObject, DefaultObjectTag>::new();
1396        let mut list2 = SinglyLinkedList::<*mut MultiDerivedObject, Tag3>::new();
1397
1398        let mut obj1 = MultiDerivedObject::new(1);
1399        let mut obj2 = MultiDerivedObject::new(2);
1400
1401        unsafe {
1402            list1.push_front_raw(core::ptr::addr_of_mut!(obj1));
1403            list1.push_front_raw(core::ptr::addr_of_mut!(obj2));
1404
1405            list2.push_front_raw(core::ptr::addr_of_mut!(obj1));
1406        }
1407
1408        let mut iter1 = list1.iter();
1409        assert_eq!(iter1.next().unwrap().value, 2);
1410        assert_eq!(iter1.next().unwrap().value, 1);
1411
1412        let mut iter2 = list2.iter();
1413        assert_eq!(iter2.next().unwrap().value, 1);
1414
1415        list1.clear();
1416        list2.clear();
1417    }
1418
1419    #[test]
1420    fn test_retain() {
1421        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1422        list.push_front(UniquePtr::try_new(UniqueTestObject::new(3)).unwrap());
1423        list.push_front(UniquePtr::try_new(UniqueTestObject::new(2)).unwrap());
1424        list.push_front(UniquePtr::try_new(UniqueTestObject::new(1)).unwrap());
1425
1426        list.retain(|o| o.value % 2 != 0);
1427
1428        let mut iter = list.iter();
1429        assert_eq!(iter.next().unwrap().value, 1);
1430        assert_eq!(iter.next().unwrap().value, 3);
1431        assert!(iter.next().is_none());
1432        list.clear();
1433    }
1434
1435    #[test]
1436    fn test_cursor_mut() {
1437        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1438        let obj1 = UniquePtr::try_new(UniqueTestObject::new(1)).unwrap();
1439        let obj2 = UniquePtr::try_new(UniqueTestObject::new(2)).unwrap();
1440        let obj3 = UniquePtr::try_new(UniqueTestObject::new(3)).unwrap();
1441
1442        list.push_front(obj1);
1443        list.push_front(obj2);
1444
1445        let mut cursor = list.cursor_mut();
1446        assert_eq!(cursor.get().unwrap().value, 2);
1447
1448        cursor.insert_after(obj3);
1449
1450        assert!(cursor.move_next());
1451        assert_eq!(cursor.get().unwrap().value, 3);
1452
1453        assert!(cursor.move_next());
1454        assert_eq!(cursor.get().unwrap().value, 1);
1455
1456        assert!(!cursor.move_next());
1457
1458        // Reset cursor
1459        let mut cursor = list.cursor_mut();
1460        assert_eq!(cursor.get().unwrap().value, 2);
1461
1462        let erased = cursor.erase_next().unwrap();
1463        assert_eq!(erased.value, 3);
1464
1465        assert!(cursor.move_next());
1466        assert_eq!(cursor.get().unwrap().value, 1);
1467
1468        assert!(!cursor.move_next());
1469    }
1470
1471    #[test]
1472    fn test_iterator_from_element() {
1473        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1474        list.push_front(UniquePtr::try_new(UniqueTestObject::new(3)).unwrap());
1475        list.push_front(UniquePtr::try_new(UniqueTestObject::new(2)).unwrap());
1476        list.push_front(UniquePtr::try_new(UniqueTestObject::new(1)).unwrap());
1477
1478        let mut iter = list.iter();
1479        iter.next(); // obj1
1480        let obj2_ref = iter.next().unwrap();
1481
1482        let mut from_element_iter: Iterator<'_, UniquePtr<UniqueTestObject>> =
1483            Iterator::from_element(obj2_ref);
1484        assert_eq!(from_element_iter.next().unwrap().value, 2);
1485        assert_eq!(from_element_iter.next().unwrap().value, 3);
1486        assert!(from_element_iter.next().is_none());
1487
1488        list.clear();
1489    }
1490
1491    #[test]
1492    fn test_front_ops() {
1493        let mut list = SinglyLinkedList::<UniquePtr<UniqueTestObject>>::new();
1494        assert!(list.front().is_none());
1495
1496        list.push_front(UniquePtr::try_new(UniqueTestObject::new(1)).unwrap());
1497        assert_eq!(list.front().unwrap().value, 1);
1498
1499        list.push_front(UniquePtr::try_new(UniqueTestObject::new(2)).unwrap());
1500        assert_eq!(list.front().unwrap().value, 2);
1501
1502        list.clear();
1503    }
1504
1505    // SLL FFI Declarations
1506    unsafe extern "C" {
1507        // UniqueList Helpers
1508        fn cpp_sll_create_unique_list() -> *mut c_void;
1509        fn cpp_sll_destroy_unique_list(list: *mut c_void);
1510        fn cpp_sll_unique_list_push_front(list: *mut c_void, item: *mut c_void);
1511        fn cpp_sll_unique_list_pop_front(list: *mut c_void) -> *mut c_void;
1512        fn cpp_sll_unique_list_is_empty(list: *mut c_void) -> bool;
1513
1514        // RefList Helpers
1515        fn cpp_sll_create_ref_list() -> *mut c_void;
1516        fn cpp_sll_destroy_ref_list(list: *mut c_void);
1517        fn cpp_sll_ref_list_push_front(list: *mut c_void, item: *mut c_void);
1518        fn cpp_sll_ref_list_pop_front(list: *mut c_void) -> *mut c_void;
1519        fn cpp_sll_ref_list_is_empty(list: *mut c_void) -> bool;
1520
1521        // SharedUniqueObject Helpers (Defined in DLL tests C++ file)
1522        fn cpp_create_unique_object(value: i32, destruction_flag: *mut bool) -> *mut c_void;
1523        fn cpp_get_unique_object_value(obj: *mut c_void) -> i32;
1524
1525        // SharedRefObject Helpers (Defined in DLL tests C++ file)
1526        fn cpp_create_ref_object(value: i32, destruction_flag: *mut bool) -> *mut c_void;
1527        fn cpp_get_ref_object_value(obj: *mut c_void) -> i32;
1528    }
1529
1530    #[test]
1531    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1532    fn test_interop_rust_list_cpp_unique_objects() {
1533        let destroyed1 = AtomicBool::new(false);
1534        let destroyed2 = AtomicBool::new(false);
1535
1536        unsafe {
1537            let mut list = SinglyLinkedList::<UniquePtr<SharedUniqueObject>>::new();
1538
1539            let cpp_raw1 = cpp_create_unique_object(1, destroyed1.as_ptr() as *mut bool);
1540            let cpp_raw2 = cpp_create_unique_object(2, destroyed2.as_ptr() as *mut bool);
1541
1542            let obj1 = UniquePtr::from_raw(cpp_raw1 as *mut SharedUniqueObject);
1543            let obj2 = UniquePtr::from_raw(cpp_raw2 as *mut SharedUniqueObject);
1544
1545            list.push_front(obj1);
1546            list.push_front(obj2);
1547
1548            assert!(!destroyed1.load(Ordering::Relaxed));
1549            assert!(!destroyed2.load(Ordering::Relaxed));
1550
1551            // Pop one
1552            let popped = list.pop_front();
1553            assert!(popped.is_some());
1554            assert_eq!(popped.as_ref().unwrap().value, 2);
1555
1556            // Drop popped -> should destroy in C++!
1557            drop(popped);
1558            assert!(!destroyed1.load(Ordering::Relaxed));
1559            assert!(destroyed2.load(Ordering::Relaxed));
1560
1561            // Drop list -> should destroy remaining in C++!
1562        }
1563        assert!(destroyed1.load(Ordering::Relaxed));
1564    }
1565
1566    #[test]
1567    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1568    fn test_interop_cpp_list_rust_unique_objects() {
1569        let destroyed1 = Arc::new(AtomicBool::new(false));
1570        let destroyed2 = Arc::new(AtomicBool::new(false));
1571
1572        unsafe {
1573            let cpp_list = cpp_sll_create_unique_list();
1574            assert!(cpp_sll_unique_list_is_empty(cpp_list));
1575
1576            let obj1 = UniquePtr::try_new(SharedUniqueObject::new(1)).unwrap();
1577            let obj2 = UniquePtr::try_new(SharedUniqueObject::new(2)).unwrap();
1578
1579            // Set destruction flags
1580            let raw1 = UniquePtr::as_ptr(&obj1) as *mut SharedUniqueObject;
1581            (*raw1).destruction_flag = destroyed1.as_ptr() as *mut bool;
1582            let raw2 = UniquePtr::as_ptr(&obj2) as *mut SharedUniqueObject;
1583            (*raw2).destruction_flag = destroyed2.as_ptr() as *mut bool;
1584
1585            // Push to C++ list (transfers ownership)
1586            cpp_sll_unique_list_push_front(cpp_list, UniquePtr::into_raw(obj1) as *mut c_void);
1587            cpp_sll_unique_list_push_front(cpp_list, UniquePtr::into_raw(obj2) as *mut c_void);
1588
1589            assert!(!destroyed1.load(Ordering::Relaxed));
1590            assert!(!destroyed2.load(Ordering::Relaxed));
1591
1592            // Pop one from C++
1593            let popped = cpp_sll_unique_list_pop_front(cpp_list);
1594            assert!(!popped.is_null());
1595            assert_eq!(cpp_get_unique_object_value(popped), 2);
1596
1597            // Convert back to Rust UniquePtr and drop -> should free in Rust!
1598            let popped_rust = UniquePtr::from_raw(popped as *mut SharedUniqueObject);
1599            drop(popped_rust);
1600            assert!(!destroyed1.load(Ordering::Relaxed));
1601            assert!(destroyed2.load(Ordering::Relaxed));
1602
1603            // Destroy C++ list -> should destroy remaining in Rust!
1604            cpp_sll_destroy_unique_list(cpp_list);
1605        }
1606        assert!(destroyed1.load(Ordering::Relaxed));
1607    }
1608
1609    #[test]
1610    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1611    fn test_interop_rust_list_cpp_ref_objects() {
1612        let destroyed1 = AtomicBool::new(false);
1613        let destroyed2 = AtomicBool::new(false);
1614
1615        unsafe {
1616            let mut list = SinglyLinkedList::<RefPtr<SharedRefObject>>::new();
1617
1618            let cpp_raw1 = cpp_create_ref_object(1, destroyed1.as_ptr() as *mut bool);
1619            let cpp_raw2 = cpp_create_ref_object(2, destroyed2.as_ptr() as *mut bool);
1620
1621            let obj1 = RefPtr::from_raw(cpp_raw1 as *mut SharedRefObject);
1622            let obj2 = RefPtr::from_raw(cpp_raw2 as *mut SharedRefObject);
1623
1624            list.push_front(obj1);
1625            list.push_front(obj2);
1626
1627            assert!(!destroyed1.load(Ordering::Relaxed));
1628            assert!(!destroyed2.load(Ordering::Relaxed));
1629
1630            // Pop one
1631            let popped = list.pop_front();
1632            assert!(popped.is_some());
1633            assert_eq!(popped.as_ref().unwrap().value, 2);
1634
1635            // Drop popped -> should destroy in C++!
1636            drop(popped);
1637            assert!(!destroyed1.load(Ordering::Relaxed));
1638            assert!(destroyed2.load(Ordering::Relaxed));
1639
1640            // Drop list -> should destroy remaining in C++!
1641        }
1642        assert!(destroyed1.load(Ordering::Relaxed));
1643    }
1644
1645    #[test]
1646    #[cfg_attr(miri, ignore = "miri does not support calling foreign functions")]
1647    fn test_interop_cpp_list_rust_ref_objects() {
1648        let destroyed1 = Arc::new(AtomicBool::new(false));
1649        let destroyed2 = Arc::new(AtomicBool::new(false));
1650
1651        unsafe {
1652            let cpp_list = cpp_sll_create_ref_list();
1653            assert!(cpp_sll_ref_list_is_empty(cpp_list));
1654
1655            let obj1 = SharedRefObject::new_ref_counted(1);
1656            let obj2 = SharedRefObject::new_ref_counted(2);
1657
1658            // Set destruction flags
1659            let raw1 = RefPtr::as_ptr(&obj1) as *mut SharedRefObject;
1660            (*raw1).destruction_flag = destroyed1.as_ptr() as *mut bool;
1661            let raw2 = RefPtr::as_ptr(&obj2) as *mut SharedRefObject;
1662            (*raw2).destruction_flag = destroyed2.as_ptr() as *mut bool;
1663
1664            // Push to C++ list (transfers ownership)
1665            cpp_sll_ref_list_push_front(
1666                cpp_list,
1667                RefPtr::into_raw(obj1) as *mut SharedRefObject as *mut c_void,
1668            );
1669            cpp_sll_ref_list_push_front(
1670                cpp_list,
1671                RefPtr::into_raw(obj2) as *mut SharedRefObject as *mut c_void,
1672            );
1673
1674            assert!(!destroyed1.load(Ordering::Relaxed));
1675            assert!(!destroyed2.load(Ordering::Relaxed));
1676
1677            // Pop one from C++
1678            let popped = cpp_sll_ref_list_pop_front(cpp_list);
1679            assert!(!popped.is_null());
1680            assert_eq!(cpp_get_ref_object_value(popped), 2);
1681
1682            // Convert back to Rust RefPtr and drop -> should free in Rust!
1683            let popped_rust = RefPtr::from_raw(popped as *mut SharedRefObject);
1684            drop(popped_rust);
1685            assert!(!destroyed1.load(Ordering::Relaxed));
1686            assert!(destroyed2.load(Ordering::Relaxed));
1687
1688            // Destroy C++ list -> should destroy remaining in Rust!
1689            cpp_sll_destroy_ref_list(cpp_list);
1690        }
1691        assert!(destroyed1.load(Ordering::Relaxed));
1692    }
1693}
fbl/singly_linked_list.rs

fbl/
singly_linked_list.rs
