path: root/rust/kernel/list.rs

// SPDX-License-Identifier: GPL-2.0

// Copyright (C) 2024 Google LLC.

//! A linked list implementation.

use crate::sync::ArcBorrow;
use crate::types::Opaque;
use core::iter::{DoubleEndedIterator, FusedIterator};
use core::marker::PhantomData;
use core::ptr;
use pin_init::PinInit;

mod impl_list_item_mod;
#[doc(inline)]
pub use self::impl_list_item_mod::{
    impl_has_list_links,
    impl_has_list_links_self_ptr,
    impl_list_item,
    HasListLinks,
    HasSelfPtr, //
};

mod arc;
#[doc(inline)]
pub use self::arc::{
    impl_list_arc_safe,
    AtomicTracker,
    ListArc,
    ListArcSafe,
    TryNewListArc, //
};

mod arc_field;
#[doc(inline)]
pub use self::arc_field::{
    define_list_arc_field_getter,
    ListArcField, //
};

/// A linked list.
///
/// All elements in this linked list will be [`ListArc`] references to the value. Since a value can
/// only have one `ListArc` (for each pair of prev/next pointers), this ensures that the same
/// prev/next pointers are not used for several linked lists.
///
/// # Invariants
///
/// * If the list is empty, then `first` is null. Otherwise, `first` points at the `ListLinks`
///   field of the first element in the list.
/// * All prev/next pointers in `ListLinks` fields of items in the list are valid and form a cycle.
/// * For every item in the list, the list owns the associated [`ListArc`] reference and has
///   exclusive access to the `ListLinks` field.
///
/// # Examples
///
/// Use [`ListLinks`] as the type of the intrusive field.
///
/// ```
/// use kernel::list::*;
///
/// #[pin_data]
/// struct BasicItem {
///     value: i32,
///     #[pin]
///     links: ListLinks,
/// }
///
/// impl BasicItem {
///     fn new(value: i32) -> Result<ListArc<Self>> {
///         ListArc::pin_init(try_pin_init!(Self {
///             value,
///             links <- ListLinks::new(),
///         }), GFP_KERNEL)
///     }
/// }
///
/// impl_list_arc_safe! {
///     impl ListArcSafe<0> for BasicItem { untracked; }
/// }
/// impl_list_item! {
///     impl ListItem<0> for BasicItem { using ListLinks { self.links }; }
/// }
///
/// // Create a new empty list.
/// let mut list = List::new();
/// {
///     assert!(list.is_empty());
/// }
///
/// // Insert 3 elements using `push_back()`.
/// list.push_back(BasicItem::new(15)?);
/// list.push_back(BasicItem::new(10)?);
/// list.push_back(BasicItem::new(30)?);
///
/// // Iterate over the list to verify the nodes were inserted correctly.
/// // [15, 10, 30]
/// {
///     let mut iter = list.iter();
///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);
///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 10);
///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 30);
///     assert!(iter.next().is_none());
///
///     // Verify the length of the list.
///     assert_eq!(list.iter().count(), 3);
/// }
///
/// // Pop the items from the list using `pop_back()` and verify the content.
/// {
///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 30);
///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 10);
///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 15);
/// }
///
/// // Insert 3 elements using `push_front()`.
/// list.push_front(BasicItem::new(15)?);
/// list.push_front(BasicItem::new(10)?);
/// list.push_front(BasicItem::new(30)?);
///
/// // Iterate over the list to verify the nodes were inserted correctly.
/// // [30, 10, 15]
/// {
///     let mut iter = list.iter();
///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 30);
///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 10);
///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);
///     assert!(iter.next().is_none());
///
///     // Verify the length of the list.
///     assert_eq!(list.iter().count(), 3);
/// }
///
/// // Pop the items from the list using `pop_front()` and verify the content.
/// {
///     assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 30);
///     assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 10);
/// }
///
/// // Push `list2` to `list` through `push_all_back()`.
/// // list: [15]
/// // list2: [25, 35]
/// {
///     let mut list2 = List::new();
///     list2.push_back(BasicItem::new(25)?);
///     list2.push_back(BasicItem::new(35)?);
///
///     list.push_all_back(&mut list2);
///
///     // list: [15, 25, 35]
///     // list2: []
///     let mut iter = list.iter();
///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);
///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 25);
///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 35);
///     assert!(iter.next().is_none());
///     assert!(list2.is_empty());
/// }
/// # Result::<(), Error>::Ok(())
/// ```
///
/// Use [`ListLinksSelfPtr`] as the type of the intrusive field. This allows a list of trait object
/// type.
///
/// ```
/// use kernel::list::*;
///
/// trait Foo {
///     fn foo(&self) -> (&'static str, i32);
/// }
///
/// #[pin_data]
/// struct DTWrap<T: ?Sized> {
///     #[pin]
///     links: ListLinksSelfPtr<DTWrap<dyn Foo>>,
///     value: T,
/// }
///
/// impl<T> DTWrap<T> {
///     fn new(value: T) -> Result<ListArc<Self>> {
///         ListArc::pin_init(try_pin_init!(Self {
///             value,
///             links <- ListLinksSelfPtr::new(),
///         }), GFP_KERNEL)
///     }
/// }
///
/// impl_list_arc_safe! {
///     impl{T: ?Sized} ListArcSafe<0> for DTWrap<T> { untracked; }
/// }
/// impl_list_item! {
///     impl ListItem<0> for DTWrap<dyn Foo> { using ListLinksSelfPtr { self.links }; }
/// }
///
/// // Create a new empty list.
/// let mut list = List::<DTWrap<dyn Foo>>::new();
/// {
///     assert!(list.is_empty());
/// }
///
/// struct A(i32);
/// // `A` returns the inner value for `foo`.
/// impl Foo for A { fn foo(&self) -> (&'static str, i32) { ("a", self.0) } }
///
/// struct B;
/// // `B` always returns 42.
/// impl Foo for B { fn foo(&self) -> (&'static str, i32) { ("b", 42) } }
///
/// // Insert 3 element using `push_back()`.
/// list.push_back(DTWrap::new(A(15))?);
/// list.push_back(DTWrap::new(A(32))?);
/// list.push_back(DTWrap::new(B)?);
///
/// // Iterate over the list to verify the nodes were inserted correctly.
/// // [A(15), A(32), B]
/// {
///     let mut iter = list.iter();
///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 15));
///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 32));
///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));
///     assert!(iter.next().is_none());
///
///     // Verify the length of the list.
///     assert_eq!(list.iter().count(), 3);
/// }
///