kernel/
list.rs

1// SPDX-License-Identifier: GPL-2.0
2
3// Copyright (C) 2024 Google LLC.
4
5//! A linked list implementation.
6
7use crate::sync::ArcBorrow;
8use crate::types::Opaque;
9use core::iter::{DoubleEndedIterator, FusedIterator};
10use core::marker::PhantomData;
11use core::ptr;
12use pin_init::PinInit;
13
14mod impl_list_item_mod;
15pub use self::impl_list_item_mod::{
16    impl_has_list_links, impl_has_list_links_self_ptr, impl_list_item, HasListLinks, HasSelfPtr,
17};
18
19mod arc;
20pub use self::arc::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSafe, TryNewListArc};
21
22mod arc_field;
23pub use self::arc_field::{define_list_arc_field_getter, ListArcField};
24
25/// A linked list.
26///
27/// All elements in this linked list will be [`ListArc`] references to the value. Since a value can
28/// only have one `ListArc` (for each pair of prev/next pointers), this ensures that the same
29/// prev/next pointers are not used for several linked lists.
30///
31/// # Invariants
32///
33/// * If the list is empty, then `first` is null. Otherwise, `first` points at the `ListLinks`
34///   field of the first element in the list.
35/// * All prev/next pointers in `ListLinks` fields of items in the list are valid and form a cycle.
36/// * For every item in the list, the list owns the associated [`ListArc`] reference and has
37///   exclusive access to the `ListLinks` field.
38///
39/// # Examples
40///
41/// ```
42/// use kernel::list::*;
43///
44/// #[pin_data]
45/// struct BasicItem {
46///     value: i32,
47///     #[pin]
48///     links: ListLinks,
49/// }
50///
51/// impl BasicItem {
52///     fn new(value: i32) -> Result<ListArc<Self>> {
53///         ListArc::pin_init(try_pin_init!(Self {
54///             value,
55///             links <- ListLinks::new(),
56///         }), GFP_KERNEL)
57///     }
58/// }
59///
60/// impl_list_arc_safe! {
61///     impl ListArcSafe<0> for BasicItem { untracked; }
62/// }
63/// impl_list_item! {
64///     impl ListItem<0> for BasicItem { using ListLinks { self.links }; }
65/// }
66///
67/// // Create a new empty list.
68/// let mut list = List::new();
69/// {
70///     assert!(list.is_empty());
71/// }
72///
73/// // Insert 3 elements using `push_back()`.
74/// list.push_back(BasicItem::new(15)?);
75/// list.push_back(BasicItem::new(10)?);
76/// list.push_back(BasicItem::new(30)?);
77///
78/// // Iterate over the list to verify the nodes were inserted correctly.
79/// // [15, 10, 30]
80/// {
81///     let mut iter = list.iter();
82///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);
83///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 10);
84///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 30);
85///     assert!(iter.next().is_none());
86///
87///     // Verify the length of the list.
88///     assert_eq!(list.iter().count(), 3);
89/// }
90///
91/// // Pop the items from the list using `pop_back()` and verify the content.
92/// {
93///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 30);
94///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 10);
95///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 15);
96/// }
97///
98/// // Insert 3 elements using `push_front()`.
99/// list.push_front(BasicItem::new(15)?);
100/// list.push_front(BasicItem::new(10)?);
101/// list.push_front(BasicItem::new(30)?);
102///
103/// // Iterate over the list to verify the nodes were inserted correctly.
104/// // [30, 10, 15]
105/// {
106///     let mut iter = list.iter();
107///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 30);
108///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 10);
109///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);
110///     assert!(iter.next().is_none());
111///
112///     // Verify the length of the list.
113///     assert_eq!(list.iter().count(), 3);
114/// }
115///
116/// // Pop the items from the list using `pop_front()` and verify the content.
117/// {
118///     assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 30);
119///     assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 10);
120/// }
121///
122/// // Push `list2` to `list` through `push_all_back()`.
123/// // list: [15]
124/// // list2: [25, 35]
125/// {
126///     let mut list2 = List::new();
127///     list2.push_back(BasicItem::new(25)?);
128///     list2.push_back(BasicItem::new(35)?);
129///
130///     list.push_all_back(&mut list2);
131///
132///     // list: [15, 25, 35]
133///     // list2: []
134///     let mut iter = list.iter();
135///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);
136///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 25);
137///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 35);
138///     assert!(iter.next().is_none());
139///     assert!(list2.is_empty());
140/// }
141/// # Result::<(), Error>::Ok(())
142/// ```
143pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
144    first: *mut ListLinksFields,
145    _ty: PhantomData<ListArc<T, ID>>,
146}
147
148// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
149// type of access to the `ListArc<T, ID>` elements.
150unsafe impl<T, const ID: u64> Send for List<T, ID>
151where
152    ListArc<T, ID>: Send,
153    T: ?Sized + ListItem<ID>,
154{
155}
156// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
157// type of access to the `ListArc<T, ID>` elements.
158unsafe impl<T, const ID: u64> Sync for List<T, ID>
159where
160    ListArc<T, ID>: Sync,
161    T: ?Sized + ListItem<ID>,
162{
163}
164
165/// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].
166///
167/// # Safety
168///
169/// Implementers must ensure that they provide the guarantees documented on methods provided by
170/// this trait.
171///
172/// [`ListArc<Self>`]: ListArc
173pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
174    /// Views the [`ListLinks`] for this value.
175    ///
176    /// # Guarantees
177    ///
178    /// If there is a previous call to `prepare_to_insert` and there is no call to `post_remove`
179    /// since the most recent such call, then this returns the same pointer as the one returned by
180    /// the most recent call to `prepare_to_insert`.
181    ///
182    /// Otherwise, the returned pointer points at a read-only [`ListLinks`] with two null pointers.
183    ///
184    /// # Safety
185    ///
186    /// The provided pointer must point at a valid value. (It need not be in an `Arc`.)
187    unsafe fn view_links(me: *const Self) -> *mut ListLinks<ID>;
188
189    /// View the full value given its [`ListLinks`] field.
190    ///
191    /// Can only be used when the value is in a list.
192    ///
193    /// # Guarantees
194    ///
195    /// * Returns the same pointer as the one passed to the most recent call to `prepare_to_insert`.
196    /// * The returned pointer is valid until the next call to `post_remove`.
197    ///
198    /// # Safety
199    ///
200    /// * The provided pointer must originate from the most recent call to `prepare_to_insert`, or
201    ///   from a call to `view_links` that happened after the most recent call to
202    ///   `prepare_to_insert`.
203    /// * Since the most recent call to `prepare_to_insert`, the `post_remove` method must not have
204    ///   been called.
205    unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self;
206
207    /// This is called when an item is inserted into a [`List`].
208    ///
209    /// # Guarantees
210    ///
211    /// The caller is granted exclusive access to the returned [`ListLinks`] until `post_remove` is
212    /// called.
213    ///
214    /// # Safety
215    ///
216    /// * The provided pointer must point at a valid value in an [`Arc`].
217    /// * Calls to `prepare_to_insert` and `post_remove` on the same value must alternate.
218    /// * The caller must own the [`ListArc`] for this value.
219    /// * The caller must not give up ownership of the [`ListArc`] unless `post_remove` has been
220    ///   called after this call to `prepare_to_insert`.
221    ///
222    /// [`Arc`]: crate::sync::Arc
223    unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<ID>;
224
225    /// This undoes a previous call to `prepare_to_insert`.
226    ///
227    /// # Guarantees
228    ///
229    /// The returned pointer is the pointer that was originally passed to `prepare_to_insert`.
230    ///
231    /// # Safety
232    ///
233    /// The provided pointer must be the pointer returned by the most recent call to
234    /// `prepare_to_insert`.
235    unsafe fn post_remove(me: *mut ListLinks<ID>) -> *const Self;
236}
237
238#[repr(C)]
239#[derive(Copy, Clone)]
240struct ListLinksFields {
241    next: *mut ListLinksFields,
242    prev: *mut ListLinksFields,
243}
244
245/// The prev/next pointers for an item in a linked list.
246///
247/// # Invariants
248///
249/// The fields are null if and only if this item is not in a list.
250#[repr(transparent)]
251pub struct ListLinks<const ID: u64 = 0> {
252    // This type is `!Unpin` for aliasing reasons as the pointers are part of an intrusive linked
253    // list.
254    inner: Opaque<ListLinksFields>,
255}
256
257// SAFETY: The only way to access/modify the pointers inside of `ListLinks<ID>` is via holding the
258// associated `ListArc<T, ID>`. Since that type correctly implements `Send`, it is impossible to
259// move this an instance of this type to a different thread if the pointees are `!Send`.
260unsafe impl<const ID: u64> Send for ListLinks<ID> {}
261// SAFETY: The type is opaque so immutable references to a ListLinks are useless. Therefore, it's
262// okay to have immutable access to a ListLinks from several threads at once.
263unsafe impl<const ID: u64> Sync for ListLinks<ID> {}
264
265impl<const ID: u64> ListLinks<ID> {
266    /// Creates a new initializer for this type.
267    pub fn new() -> impl PinInit<Self> {
268        // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
269        // not be constructed in an `Arc` that already has a `ListArc`.
270        ListLinks {
271            inner: Opaque::new(ListLinksFields {
272                prev: ptr::null_mut(),
273                next: ptr::null_mut(),
274            }),
275        }
276    }
277
278    /// # Safety
279    ///
280    /// `me` must be dereferenceable.
281    #[inline]
282    unsafe fn fields(me: *mut Self) -> *mut ListLinksFields {
283        // SAFETY: The caller promises that the pointer is valid.
284        unsafe { Opaque::cast_into(ptr::addr_of!((*me).inner)) }
285    }
286
287    /// # Safety
288    ///
289    /// `me` must be dereferenceable.
290    #[inline]
291    unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self {
292        me.cast()
293    }
294}
295
296/// Similar to [`ListLinks`], but also contains a pointer to the full value.
297///
298/// This type can be used instead of [`ListLinks`] to support lists with trait objects.
299#[repr(C)]
300pub struct ListLinksSelfPtr<T: ?Sized, const ID: u64 = 0> {
301    /// The `ListLinks` field inside this value.
302    ///
303    /// This is public so that it can be used with `impl_has_list_links!`.
304    pub inner: ListLinks<ID>,
305    // UnsafeCell is not enough here because we use `Opaque::uninit` as a dummy value, and
306    // `ptr::null()` doesn't work for `T: ?Sized`.
307    self_ptr: Opaque<*const T>,
308}
309
310// SAFETY: The fields of a ListLinksSelfPtr can be moved across thread boundaries.
311unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {}
312// SAFETY: The type is opaque so immutable references to a ListLinksSelfPtr are useless. Therefore,
313// it's okay to have immutable access to a ListLinks from several threads at once.
314//
315// Note that `inner` being a public field does not prevent this type from being opaque, since
316// `inner` is a opaque type.
317unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {}
318
319impl<T: ?Sized, const ID: u64> ListLinksSelfPtr<T, ID> {
320    /// Creates a new initializer for this type.
321    pub fn new() -> impl PinInit<Self> {
322        // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
323        // not be constructed in an `Arc` that already has a `ListArc`.
324        Self {
325            inner: ListLinks {
326                inner: Opaque::new(ListLinksFields {
327                    prev: ptr::null_mut(),
328                    next: ptr::null_mut(),
329                }),
330            },
331            self_ptr: Opaque::uninit(),
332        }
333    }
334
335    /// Returns a pointer to the self pointer.
336    ///
337    /// # Safety
338    ///
339    /// The provided pointer must point at a valid struct of type `Self`.
340    pub unsafe fn raw_get_self_ptr(me: *const Self) -> *const Opaque<*const T> {
341        // SAFETY: The caller promises that the pointer is valid.
342        unsafe { ptr::addr_of!((*me).self_ptr) }
343    }
344}
345
346impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {
347    /// Creates a new empty list.
348    pub const fn new() -> Self {
349        Self {
350            first: ptr::null_mut(),
351            _ty: PhantomData,
352        }
353    }
354
355    /// Returns whether this list is empty.
356    pub fn is_empty(&self) -> bool {
357        self.first.is_null()
358    }
359
360    /// Inserts `item` before `next` in the cycle.
361    ///
362    /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list
363    /// is empty.
364    ///
365    /// # Safety
366    ///
367    /// * `next` must be an element in this list or null.
368    /// * if `next` is null, then the list must be empty.
369    unsafe fn insert_inner(
370        &mut self,
371        item: ListArc<T, ID>,
372        next: *mut ListLinksFields,
373    ) -> *mut ListLinksFields {
374        let raw_item = ListArc::into_raw(item);
375        // SAFETY:
376        // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
377        // * Since we have ownership of the `ListArc`, `post_remove` must have been called after
378        //   the most recent call to `prepare_to_insert`, if any.
379        // * We own the `ListArc`.
380        // * Removing items from this list is always done using `remove_internal_inner`, which
381        //   calls `post_remove` before giving up ownership.
382        let list_links = unsafe { T::prepare_to_insert(raw_item) };
383        // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
384        let item = unsafe { ListLinks::fields(list_links) };
385
386        // Check if the list is empty.
387        if next.is_null() {
388            // SAFETY: The caller just gave us ownership of these fields.
389            // INVARIANT: A linked list with one item should be cyclic.
390            unsafe {
391                (*item).next = item;
392                (*item).prev = item;
393            }
394            self.first = item;
395        } else {
396            // SAFETY: By the type invariant, this pointer is valid or null. We just checked that
397            // it's not null, so it must be valid.
398            let prev = unsafe { (*next).prev };
399            // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
400            // ownership of the fields on `item`.
401            // INVARIANT: This correctly inserts `item` between `prev` and `next`.
402            unsafe {
403                (*item).next = next;
404                (*item).prev = prev;
405                (*prev).next = item;
406                (*next).prev = item;
407            }
408        }
409
410        item
411    }
412
413    /// Add the provided item to the back of the list.
414    pub fn push_back(&mut self, item: ListArc<T, ID>) {
415        // SAFETY:
416        // * `self.first` is null or in the list.
417        // * `self.first` is only null if the list is empty.
418        unsafe { self.insert_inner(item, self.first) };
419    }
420
421    /// Add the provided item to the front of the list.
422    pub fn push_front(&mut self, item: ListArc<T, ID>) {
423        // SAFETY:
424        // * `self.first` is null or in the list.
425        // * `self.first` is only null if the list is empty.
426        let new_elem = unsafe { self.insert_inner(item, self.first) };
427
428        // INVARIANT: `new_elem` is in the list because we just inserted it.
429        self.first = new_elem;
430    }
431
432    /// Removes the last item from this list.
433    pub fn pop_back(&mut self) -> Option<ListArc<T, ID>> {
434        if self.is_empty() {
435            return None;
436        }
437
438        // SAFETY: We just checked that the list is not empty.
439        let last = unsafe { (*self.first).prev };
440        // SAFETY: The last item of this list is in this list.
441        Some(unsafe { self.remove_internal(last) })
442    }
443
444    /// Removes the first item from this list.
445    pub fn pop_front(&mut self) -> Option<ListArc<T, ID>> {
446        if self.is_empty() {
447            return None;
448        }
449
450        // SAFETY: The first item of this list is in this list.
451        Some(unsafe { self.remove_internal(self.first) })
452    }
453
454    /// Removes the provided item from this list and returns it.
455    ///
456    /// This returns `None` if the item is not in the list. (Note that by the safety requirements,
457    /// this means that the item is not in any list.)
458    ///
459    /// # Safety
460    ///
461    /// `item` must not be in a different linked list (with the same id).
462    pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> {
463        // SAFETY: TODO.
464        let mut item = unsafe { ListLinks::fields(T::view_links(item)) };
465        // SAFETY: The user provided a reference, and reference are never dangling.
466        //
467        // As for why this is not a data race, there are two cases:
468        //
469        //  * If `item` is not in any list, then these fields are read-only and null.
470        //  * If `item` is in this list, then we have exclusive access to these fields since we
471        //    have a mutable reference to the list.
472        //
473        // In either case, there's no race.
474        let ListLinksFields { next, prev } = unsafe { *item };
475
476        debug_assert_eq!(next.is_null(), prev.is_null());
477        if !next.is_null() {
478            // This is really a no-op, but this ensures that `item` is a raw pointer that was
479            // obtained without going through a pointer->reference->pointer conversion roundtrip.
480            // This ensures that the list is valid under the more restrictive strict provenance
481            // ruleset.
482            //
483            // SAFETY: We just checked that `next` is not null, and it's not dangling by the
484            // list invariants.
485            unsafe {
486                debug_assert_eq!(item, (*next).prev);
487                item = (*next).prev;
488            }
489
490            // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it
491            // is in this list. The pointers are in the right order.
492            Some(unsafe { self.remove_internal_inner(item, next, prev) })
493        } else {
494            None
495        }
496    }
497
498    /// Removes the provided item from the list.
499    ///
500    /// # Safety
501    ///
502    /// `item` must point at an item in this list.
503    unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> {
504        // SAFETY: The caller promises that this pointer is not dangling, and there's no data race
505        // since we have a mutable reference to the list containing `item`.
506        let ListLinksFields { next, prev } = unsafe { *item };
507        // SAFETY: The pointers are ok and in the right order.
508        unsafe { self.remove_internal_inner(item, next, prev) }
509    }
510
511    /// Removes the provided item from the list.
512    ///
513    /// # Safety
514    ///
515    /// The `item` pointer must point at an item in this list, and we must have `(*item).next ==
516    /// next` and `(*item).prev == prev`.
517    unsafe fn remove_internal_inner(
518        &mut self,
519        item: *mut ListLinksFields,
520        next: *mut ListLinksFields,
521        prev: *mut ListLinksFields,
522    ) -> ListArc<T, ID> {
523        // SAFETY: We have exclusive access to the pointers of items in the list, and the prev/next
524        // pointers are always valid for items in a list.
525        //
526        // INVARIANT: There are three cases:
527        //  * If the list has at least three items, then after removing the item, `prev` and `next`
528        //    will be next to each other.
529        //  * If the list has two items, then the remaining item will point at itself.
530        //  * If the list has one item, then `next == prev == item`, so these writes have no
531        //    effect. The list remains unchanged and `item` is still in the list for now.
532        unsafe {
533            (*next).prev = prev;
534            (*prev).next = next;
535        }
536        // SAFETY: We have exclusive access to items in the list.
537        // INVARIANT: `item` is being removed, so the pointers should be null.
538        unsafe {
539            (*item).prev = ptr::null_mut();
540            (*item).next = ptr::null_mut();
541        }
542        // INVARIANT: There are three cases:
543        //  * If `item` was not the first item, then `self.first` should remain unchanged.
544        //  * If `item` was the first item and there is another item, then we just updated
545        //    `prev->next` to `next`, which is the new first item, and setting `item->next` to null
546        //    did not modify `prev->next`.
547        //  * If `item` was the only item in the list, then `prev == item`, and we just set
548        //    `item->next` to null, so this correctly sets `first` to null now that the list is
549        //    empty.
550        if self.first == item {
551            // SAFETY: The `prev` pointer is the value that `item->prev` had when it was in this
552            // list, so it must be valid. There is no race since `prev` is still in the list and we
553            // still have exclusive access to the list.
554            self.first = unsafe { (*prev).next };
555        }
556
557        // SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants
558        // of `List`.
559        let list_links = unsafe { ListLinks::from_fields(item) };
560        // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call.
561        let raw_item = unsafe { T::post_remove(list_links) };
562        // SAFETY: The above call to `post_remove` guarantees that we can recreate the `ListArc`.
563        unsafe { ListArc::from_raw(raw_item) }
564    }
565
566    /// Moves all items from `other` into `self`.
567    ///
568    /// The items of `other` are added to the back of `self`, so the last item of `other` becomes
569    /// the last item of `self`.
570    pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
571        // First, we insert the elements into `self`. At the end, we make `other` empty.
572        if self.is_empty() {
573            // INVARIANT: All of the elements in `other` become elements of `self`.
574            self.first = other.first;
575        } else if !other.is_empty() {
576            let other_first = other.first;
577            // SAFETY: The other list is not empty, so this pointer is valid.
578            let other_last = unsafe { (*other_first).prev };
579            let self_first = self.first;
580            // SAFETY: The self list is not empty, so this pointer is valid.
581            let self_last = unsafe { (*self_first).prev };
582
583            // SAFETY: We have exclusive access to both lists, so we can update the pointers.
584            // INVARIANT: This correctly sets the pointers to merge both lists. We do not need to
585            // update `self.first` because the first element of `self` does not change.
586            unsafe {
587                (*self_first).prev = other_last;
588                (*other_last).next = self_first;
589                (*self_last).next = other_first;
590                (*other_first).prev = self_last;
591            }
592        }
593
594        // INVARIANT: The other list is now empty, so update its pointer.
595        other.first = ptr::null_mut();
596    }
597
598    /// Returns a cursor that points before the first element of the list.
599    pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> {
600        // INVARIANT: `self.first` is in this list.
601        Cursor {
602            next: self.first,
603            list: self,
604        }
605    }
606
607    /// Returns a cursor that points after the last element in the list.
608    pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> {
609        // INVARIANT: `next` is allowed to be null.
610        Cursor {
611            next: core::ptr::null_mut(),
612            list: self,
613        }
614    }
615
616    /// Creates an iterator over the list.
617    pub fn iter(&self) -> Iter<'_, T, ID> {
618        // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point
619        // at the first element of the same list.
620        Iter {
621            current: self.first,
622            stop: self.first,
623            _ty: PhantomData,
624        }
625    }
626}
627
628impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> {
629    fn default() -> Self {
630        List::new()
631    }
632}
633
634impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> {
635    fn drop(&mut self) {
636        while let Some(item) = self.pop_front() {
637            drop(item);
638        }
639    }
640}
641
642/// An iterator over a [`List`].
643///
644/// # Invariants
645///
646/// * There must be a [`List`] that is immutably borrowed for the duration of `'a`.
647/// * The `current` pointer is null or points at a value in that [`List`].
648/// * The `stop` pointer is equal to the `first` field of that [`List`].
649#[derive(Clone)]
650pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
651    current: *mut ListLinksFields,
652    stop: *mut ListLinksFields,
653    _ty: PhantomData<&'a ListArc<T, ID>>,
654}
655
656impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> {
657    type Item = ArcBorrow<'a, T>;
658
659    fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
660        if self.current.is_null() {
661            return None;
662        }
663
664        let current = self.current;
665
666        // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not
667        // dangling. There's no race because the iterator holds an immutable borrow to the list.
668        let next = unsafe { (*current).next };
669        // INVARIANT: If `current` was the last element of the list, then this updates it to null.
670        // Otherwise, we update it to the next element.
671        self.current = if next != self.stop {
672            next
673        } else {
674            ptr::null_mut()
675        };
676
677        // SAFETY: The `current` pointer points at a value in the list.
678        let item = unsafe { T::view_value(ListLinks::from_fields(current)) };
679        // SAFETY:
680        // * All values in a list are stored in an `Arc`.
681        // * The value cannot be removed from the list for the duration of the lifetime annotated
682        //   on the returned `ArcBorrow`, because removing it from the list would require mutable
683        //   access to the list. However, the `ArcBorrow` is annotated with the iterator's
684        //   lifetime, and the list is immutably borrowed for that lifetime.
685        // * Values in a list never have a `UniqueArc` reference.
686        Some(unsafe { ArcBorrow::from_raw(item) })
687    }
688}
689
690/// A cursor into a [`List`].
691///
692/// A cursor always rests between two elements in the list. This means that a cursor has a previous
693/// and next element, but no current element. It also means that it's possible to have a cursor
694/// into an empty list.
695///
696/// # Examples
697///
698/// ```
699/// use kernel::prelude::*;
700/// use kernel::list::{List, ListArc, ListLinks};
701///
702/// #[pin_data]
703/// struct ListItem {
704///     value: u32,
705///     #[pin]
706///     links: ListLinks,
707/// }
708///
709/// impl ListItem {
710///     fn new(value: u32) -> Result<ListArc<Self>> {
711///         ListArc::pin_init(try_pin_init!(Self {
712///             value,
713///             links <- ListLinks::new(),
714///         }), GFP_KERNEL)
715///     }
716/// }
717///
718/// kernel::list::impl_list_arc_safe! {
719///     impl ListArcSafe<0> for ListItem { untracked; }
720/// }
721/// kernel::list::impl_list_item! {
722///     impl ListItem<0> for ListItem { using ListLinks { self.links }; }
723/// }
724///
725/// // Use a cursor to remove the first element with the given value.
726/// fn remove_first(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
727///     let mut cursor = list.cursor_front();
728///     while let Some(next) = cursor.peek_next() {
729///         if next.value == value {
730///             return Some(next.remove());
731///         }
732///         cursor.move_next();
733///     }
734///     None
735/// }
736///
737/// // Use a cursor to remove the last element with the given value.
738/// fn remove_last(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
739///     let mut cursor = list.cursor_back();
740///     while let Some(prev) = cursor.peek_prev() {
741///         if prev.value == value {
742///             return Some(prev.remove());
743///         }
744///         cursor.move_prev();
745///     }
746///     None
747/// }
748///
749/// // Use a cursor to remove all elements with the given value. The removed elements are moved to
750/// // a new list.
751/// fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> {
752///     let mut out = List::new();
753///     let mut cursor = list.cursor_front();
754///     while let Some(next) = cursor.peek_next() {
755///         if next.value == value {
756///             out.push_back(next.remove());
757///         } else {
758///             cursor.move_next();
759///         }
760///     }
761///     out
762/// }
763///
764/// // Use a cursor to insert a value at a specific index. Returns an error if the index is out of
765/// // bounds.
766/// fn insert_at(list: &mut List<ListItem>, new: ListArc<ListItem>, idx: usize) -> Result {
767///     let mut cursor = list.cursor_front();
768///     for _ in 0..idx {
769///         if !cursor.move_next() {
770///             return Err(EINVAL);
771///         }
772///     }
773///     cursor.insert_next(new);
774///     Ok(())
775/// }
776///
777/// // Merge two sorted lists into a single sorted list.
778/// fn merge_sorted(list: &mut List<ListItem>, merge: List<ListItem>) {
779///     let mut cursor = list.cursor_front();
780///     for to_insert in merge {
781///         while let Some(next) = cursor.peek_next() {
782///             if to_insert.value < next.value {
783///                 break;
784///             }
785///             cursor.move_next();
786///         }
787///         cursor.insert_prev(to_insert);
788///     }
789/// }
790///
791/// let mut list = List::new();
792/// list.push_back(ListItem::new(14)?);
793/// list.push_back(ListItem::new(12)?);
794/// list.push_back(ListItem::new(10)?);
795/// list.push_back(ListItem::new(12)?);
796/// list.push_back(ListItem::new(15)?);
797/// list.push_back(ListItem::new(14)?);
798/// assert_eq!(remove_all(&mut list, 12).iter().count(), 2);
799/// // [14, 10, 15, 14]
800/// assert!(remove_first(&mut list, 14).is_some());
801/// // [10, 15, 14]
802/// insert_at(&mut list, ListItem::new(12)?, 2)?;
803/// // [10, 15, 12, 14]
804/// assert!(remove_last(&mut list, 15).is_some());
805/// // [10, 12, 14]
806///
807/// let mut list2 = List::new();
808/// list2.push_back(ListItem::new(11)?);
809/// list2.push_back(ListItem::new(13)?);
810/// merge_sorted(&mut list, list2);
811///
812/// let mut items = list.into_iter();
813/// assert_eq!(items.next().ok_or(EINVAL)?.value, 10);
814/// assert_eq!(items.next().ok_or(EINVAL)?.value, 11);
815/// assert_eq!(items.next().ok_or(EINVAL)?.value, 12);
816/// assert_eq!(items.next().ok_or(EINVAL)?.value, 13);
817/// assert_eq!(items.next().ok_or(EINVAL)?.value, 14);
818/// assert!(items.next().is_none());
819/// # Result::<(), Error>::Ok(())
820/// ```
821///
822/// # Invariants
823///
824/// The `next` pointer is null or points a value in `list`.
825pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
826    list: &'a mut List<T, ID>,
827    /// Points at the element after this cursor, or null if the cursor is after the last element.
828    next: *mut ListLinksFields,
829}
830
831impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Cursor<'a, T, ID> {
832    /// Returns a pointer to the element before the cursor.
833    ///
834    /// Returns null if there is no element before the cursor.
835    fn prev_ptr(&self) -> *mut ListLinksFields {
836        let mut next = self.next;
837        let first = self.list.first;
838        if next == first {
839            // We are before the first element.
840            return core::ptr::null_mut();
841        }
842
843        if next.is_null() {
844            // We are after the last element, so we need a pointer to the last element, which is
845            // the same as `(*first).prev`.
846            next = first;
847        }
848
849        // SAFETY: `next` can't be null, because then `first` must also be null, but in that case
850        // we would have exited at the `next == first` check. Thus, `next` is an element in the
851        // list, so we can access its `prev` pointer.
852        unsafe { (*next).prev }
853    }
854
855    /// Access the element after this cursor.
856    pub fn peek_next(&mut self) -> Option<CursorPeek<'_, 'a, T, true, ID>> {
857        if self.next.is_null() {
858            return None;
859        }
860
861        // INVARIANT:
862        // * We just checked that `self.next` is non-null, so it must be in `self.list`.
863        // * `ptr` is equal to `self.next`.
864        Some(CursorPeek {
865            ptr: self.next,
866            cursor: self,
867        })
868    }
869
870    /// Access the element before this cursor.
871    pub fn peek_prev(&mut self) -> Option<CursorPeek<'_, 'a, T, false, ID>> {
872        let prev = self.prev_ptr();
873
874        if prev.is_null() {
875            return None;
876        }
877
878        // INVARIANT:
879        // * We just checked that `prev` is non-null, so it must be in `self.list`.
880        // * `self.prev_ptr()` never returns `self.next`.
881        Some(CursorPeek {
882            ptr: prev,
883            cursor: self,
884        })
885    }
886
887    /// Move the cursor one element forward.
888    ///
889    /// If the cursor is after the last element, then this call does nothing. This call returns
890    /// `true` if the cursor's position was changed.
891    pub fn move_next(&mut self) -> bool {
892        if self.next.is_null() {
893            return false;
894        }
895
896        // SAFETY: `self.next` is an element in the list and we borrow the list mutably, so we can
897        // access the `next` field.
898        let mut next = unsafe { (*self.next).next };
899
900        if next == self.list.first {
901            next = core::ptr::null_mut();
902        }
903
904        // INVARIANT: `next` is either null or the next element after an element in the list.
905        self.next = next;
906        true
907    }
908
909    /// Move the cursor one element backwards.
910    ///
911    /// If the cursor is before the first element, then this call does nothing. This call returns
912    /// `true` if the cursor's position was changed.
913    pub fn move_prev(&mut self) -> bool {
914        if self.next == self.list.first {
915            return false;
916        }
917
918        // INVARIANT: `prev_ptr()` always returns a pointer that is null or in the list.
919        self.next = self.prev_ptr();
920        true
921    }
922
923    /// Inserts an element where the cursor is pointing and get a pointer to the new element.
924    fn insert_inner(&mut self, item: ListArc<T, ID>) -> *mut ListLinksFields {
925        let ptr = if self.next.is_null() {
926            self.list.first
927        } else {
928            self.next
929        };
930        // SAFETY:
931        // * `ptr` is an element in the list or null.
932        // * if `ptr` is null, then `self.list.first` is null so the list is empty.
933        let item = unsafe { self.list.insert_inner(item, ptr) };
934        if self.next == self.list.first {
935            // INVARIANT: We just inserted `item`, so it's a member of list.
936            self.list.first = item;
937        }
938        item
939    }
940
941    /// Insert an element at this cursor's location.
942    pub fn insert(mut self, item: ListArc<T, ID>) {
943        // This is identical to `insert_prev`, but consumes the cursor. This is helpful because it
944        // reduces confusion when the last operation on the cursor is an insertion; in that case,
945        // you just want to insert the element at the cursor, and it is confusing that the call
946        // involves the word prev or next.
947        self.insert_inner(item);
948    }
949
950    /// Inserts an element after this cursor.
951    ///
952    /// After insertion, the new element will be after the cursor.
953    pub fn insert_next(&mut self, item: ListArc<T, ID>) {
954        self.next = self.insert_inner(item);
955    }
956
957    /// Inserts an element before this cursor.
958    ///
959    /// After insertion, the new element will be before the cursor.
960    pub fn insert_prev(&mut self, item: ListArc<T, ID>) {
961        self.insert_inner(item);
962    }
963
964    /// Remove the next element from the list.
965    pub fn remove_next(&mut self) -> Option<ListArc<T, ID>> {
966        self.peek_next().map(|v| v.remove())
967    }
968
969    /// Remove the previous element from the list.
970    pub fn remove_prev(&mut self) -> Option<ListArc<T, ID>> {
971        self.peek_prev().map(|v| v.remove())
972    }
973}
974
975/// References the element in the list next to the cursor.
976///
977/// # Invariants
978///
979/// * `ptr` is an element in `self.cursor.list`.
980/// * `ISNEXT == (self.ptr == self.cursor.next)`.
981pub struct CursorPeek<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> {
982    cursor: &'a mut Cursor<'b, T, ID>,
983    ptr: *mut ListLinksFields,
984}
985
986impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64>
987    CursorPeek<'a, 'b, T, ISNEXT, ID>
988{
989    /// Remove the element from the list.
990    pub fn remove(self) -> ListArc<T, ID> {
991        if ISNEXT {
992            self.cursor.move_next();
993        }
994
995        // INVARIANT: `self.ptr` is not equal to `self.cursor.next` due to the above `move_next`
996        // call.
997        // SAFETY: By the type invariants of `Self`, `next` is not null, so `next` is an element of
998        // `self.cursor.list` by the type invariants of `Cursor`.
999        unsafe { self.cursor.list.remove_internal(self.ptr) }
1000    }
1001
1002    /// Access this value as an [`ArcBorrow`].
1003    pub fn arc(&self) -> ArcBorrow<'_, T> {
1004        // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
1005        let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) };
1006        // SAFETY:
1007        // * All values in a list are stored in an `Arc`.
1008        // * The value cannot be removed from the list for the duration of the lifetime annotated
1009        //   on the returned `ArcBorrow`, because removing it from the list would require mutable
1010        //   access to the `CursorPeek`, the `Cursor` or the `List`. However, the `ArcBorrow` holds
1011        //   an immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the
1012        //   `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable
1013        //   access requires first releasing the immutable borrow on the `CursorPeek`.
1014        // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc`
1015        //   reference, and `UniqueArc` references must be unique.
1016        unsafe { ArcBorrow::from_raw(me) }
1017    }
1018}
1019
1020impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> core::ops::Deref
1021    for CursorPeek<'a, 'b, T, ISNEXT, ID>
1022{
1023    // If you change the `ptr` field to have type `ArcBorrow<'a, T>`, it might seem like you could
1024    // get rid of the `CursorPeek::arc` method and change the deref target to `ArcBorrow<'a, T>`.
1025    // However, that doesn't work because 'a is too long. You could obtain an `ArcBorrow<'a, T>`
1026    // and then call `CursorPeek::remove` without giving up the `ArcBorrow<'a, T>`, which would be
1027    // unsound.
1028    type Target = T;
1029
1030    fn deref(&self) -> &T {
1031        // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
1032        let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) };
1033
1034        // SAFETY: The value cannot be removed from the list for the duration of the lifetime
1035        // annotated on the returned `&T`, because removing it from the list would require mutable
1036        // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `&T` holds an
1037        // immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the
1038        // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable access
1039        // requires first releasing the immutable borrow on the `CursorPeek`.
1040        unsafe { &*me }
1041    }
1042}
1043
1044impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for Iter<'a, T, ID> {}
1045
1046impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> {
1047    type IntoIter = Iter<'a, T, ID>;
1048    type Item = ArcBorrow<'a, T>;
1049
1050    fn into_iter(self) -> Iter<'a, T, ID> {
1051        self.iter()
1052    }
1053}
1054
1055/// An owning iterator into a [`List`].
1056pub struct IntoIter<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
1057    list: List<T, ID>,
1058}
1059
1060impl<T: ?Sized + ListItem<ID>, const ID: u64> Iterator for IntoIter<T, ID> {
1061    type Item = ListArc<T, ID>;
1062
1063    fn next(&mut self) -> Option<ListArc<T, ID>> {
1064        self.list.pop_front()
1065    }
1066}
1067
1068impl<T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for IntoIter<T, ID> {}
1069
1070impl<T: ?Sized + ListItem<ID>, const ID: u64> DoubleEndedIterator for IntoIter<T, ID> {
1071    fn next_back(&mut self) -> Option<ListArc<T, ID>> {
1072        self.list.pop_back()
1073    }
1074}
1075
1076impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> {
1077    type IntoIter = IntoIter<T, ID>;
1078    type Item = ListArc<T, ID>;
1079
1080    fn into_iter(self) -> IntoIter<T, ID> {
1081        IntoIter { list: self }
1082    }
1083}