[RFC PATCH v2] rust: list: Add examples for linked list

[RFC PATCH v2] rust: list: Add examples for linked list

[I Hsin Cheng]

Add basic examples for the structure "List", also serve as the unit
tests for basic list methods. Including the following manipulations:
* List creation
* List emptiness check
* List insertion through push_front(), push_back()
* List item removal through pop_front(), pop_back()
* Push one list to another through push_all_back()

The method "remove()" doesn't have an example here because insertion
with push_front() or push_back() will take the ownership of the item,
which means we can't keep any valid reference to the node we want to
remove, unless Cursor is used. The remove example through Cursor is
already demonstrate with 'commit 52ae96f5187c ("rust: list: make the
cursor point between elements")' .

Link: https://github.com/Rust-for-Linux/linux/issues/1121
Signed-off-by: I Hsin Cheng <richard120310@gmail.com>
---
Changelog:

v1 -> v2:
    - Abandon new implementation of method to create a new "ListLink"
      instance
    - Rephrase the examples' comment
    - Increase the coverity of the examples

Tests was performed on ubuntu 24.04 with x86_64 architecture.

$ ./tools/testing/kunit/kunit.py run --make_options LLVM=1 --arch x86_64 --kconfig_add CONFIG_RUST=y
...
[21:13:11] Testing complete. Ran 615 tests: passed: 563, skipped: 52
[21:13:11] Elapsed time: 23.020s total, 0.001s configuring, 10.985s building, 12.020s running

Rust related unit tests are all passed.

Best regards,
I Hsin Cheng
---
 rust/kernel/list.rs | 117 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 117 insertions(+)

diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index c0ed227b8a4f..b88b63432e02 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -35,6 +35,123 @@
 /// * 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 kernel::prelude::*;
+/// 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_has_list_links! {
+///     impl HasListLinks<0> for BasicItem { self.links }
+/// }
+/// impl_list_arc_safe! {
+///     impl ListArcSafe<0> for BasicItem { untracked; }
+/// }
+/// impl_list_item! {
+///     impl ListItem<0> for BasicItem { using ListLinks; }
+/// }
+///
+/// // 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().unwrap().value, 15);
+///     assert_eq!(iter.next().unwrap().value, 10);
+///     assert_eq!(iter.next().unwrap().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().unwrap().value, 30);
+///     assert_eq!(list.pop_back().unwrap().value, 10);
+///     assert_eq!(list.pop_back().unwrap().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().unwrap().value, 30);
+///     assert_eq!(iter.next().unwrap().value, 10);
+///     assert_eq!(iter.next().unwrap().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().unwrap().value, 30);
+///     assert_eq!(list.pop_front().unwrap().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().unwrap().value, 15);
+///     assert_eq!(iter.next().unwrap().value, 25);
+///     assert_eq!(iter.next().unwrap().value, 35);
+///     assert!(iter.next().is_none());
+///     assert!(list2.is_empty());
+///
+/// }
+///
+/// # Result::<(), Error>::Ok(())
+/// ```
+///
 pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
     first: *mut ListLinksFields,
     _ty: PhantomData<ListArc<T, ID>>,
-- 
2.43.0

Re: [RFC PATCH v2] rust: list: Add examples for linked list

[Miguel Ojeda]

On Tue, 11 Mar 2025 21:33:57 +0800 I Hsin Cheng <richard120310@gmail.com> wrote:
>
> Add basic examples for the structure "List", also serve as the unit
> tests for basic list methods. Including the following manipulations:
> * List creation
> * List emptiness check
> * List insertion through push_front(), push_back()
> * List item removal through pop_front(), pop_back()
> * Push one list to another through push_all_back()
>
> The method "remove()" doesn't have an example here because insertion
> with push_front() or push_back() will take the ownership of the item,
> which means we can't keep any valid reference to the node we want to
> remove, unless Cursor is used. The remove example through Cursor is
> already demonstrate with 'commit 52ae96f5187c ("rust: list: make the
> cursor point between elements")' .
>
> Link: https://github.com/Rust-for-Linux/linux/issues/1121
> Signed-off-by: I Hsin Cheng <richard120310@gmail.com>

It would be nice to pick this one up, even if it is similar to the
cursor one -- some methods shown here are not in the other example.

Any reviews Reviewed-bys/Tested-bys, anyone? (I can clean a few nits on
my side when applying).

By the way, similarly to the other one, your email did not reach my
inbox for some reason.

Thanks!

Cheers,
Miguel

Re: [RFC PATCH v2] rust: list: Add examples for linked list

[Alice Ryhl]

On Tue, Mar 11, 2025 at 09:33:57PM +0800, I Hsin Cheng wrote:
> Add basic examples for the structure "List", also serve as the unit
> tests for basic list methods. Including the following manipulations:
> * List creation
> * List emptiness check
> * List insertion through push_front(), push_back()
> * List item removal through pop_front(), pop_back()
> * Push one list to another through push_all_back()
> 
> The method "remove()" doesn't have an example here because insertion
> with push_front() or push_back() will take the ownership of the item,
> which means we can't keep any valid reference to the node we want to
> remove, unless Cursor is used. The remove example through Cursor is
> already demonstrate with 'commit 52ae96f5187c ("rust: list: make the
> cursor point between elements")' .
> 
> Link: https://github.com/Rust-for-Linux/linux/issues/1121
> Signed-off-by: I Hsin Cheng <richard120310@gmail.com>

LGTM.

Reviewed-by: Alice Ryhl <aliceryhl@google.com>

Re: [RFC PATCH v2] rust: list: Add examples for linked list

[Miguel Ojeda]

On Tue, 11 Mar 2025 21:33:57 +0800 I Hsin Cheng <richard120310@gmail.com> wrote:
>
> Add basic examples for the structure "List", also serve as the unit
> tests for basic list methods. Including the following manipulations:
> * List creation
> * List emptiness check
> * List insertion through push_front(), push_back()
> * List item removal through pop_front(), pop_back()
> * Push one list to another through push_all_back()
>
> The method "remove()" doesn't have an example here because insertion
> with push_front() or push_back() will take the ownership of the item,
> which means we can't keep any valid reference to the node we want to
> remove, unless Cursor is used. The remove example through Cursor is
> already demonstrate with 'commit 52ae96f5187c ("rust: list: make the
> cursor point between elements")' .
>
> Link: https://github.com/Rust-for-Linux/linux/issues/1121
> Signed-off-by: I Hsin Cheng <richard120310@gmail.com>

Applied to `rust-next` -- thanks everyone!

    [ Removed prelude import and spurious newlines. Formatted comments
      with the usual style. Reworded slightly. - Miguel ]

Cheers,
Miguel

Re: [RFC PATCH v2] rust: list: Add examples for linked list

[Benno Lossin]

On Tue Mar 11, 2025 at 2:33 PM CET, I Hsin Cheng wrote:
> Add basic examples for the structure "List", also serve as the unit
> tests for basic list methods. Including the following manipulations:
> * List creation
> * List emptiness check
> * List insertion through push_front(), push_back()
> * List item removal through pop_front(), pop_back()
> * Push one list to another through push_all_back()
>
> The method "remove()" doesn't have an example here because insertion
> with push_front() or push_back() will take the ownership of the item,
> which means we can't keep any valid reference to the node we want to
> remove, unless Cursor is used. The remove example through Cursor is
> already demonstrate with 'commit 52ae96f5187c ("rust: list: make the
> cursor point between elements")' .
>
> Link: https://github.com/Rust-for-Linux/linux/issues/1121
> Signed-off-by: I Hsin Cheng <richard120310@gmail.com>
> ---
> Changelog:
>
> v1 -> v2:
>     - Abandon new implementation of method to create a new "ListLink"
>       instance
>     - Rephrase the examples' comment
>     - Increase the coverity of the examples
>
> Tests was performed on ubuntu 24.04 with x86_64 architecture.
>
> $ ./tools/testing/kunit/kunit.py run --make_options LLVM=1 --arch x86_64 --kconfig_add CONFIG_RUST=y
> ...
> [21:13:11] Testing complete. Ran 615 tests: passed: 563, skipped: 52
> [21:13:11] Elapsed time: 23.020s total, 0.001s configuring, 10.985s building, 12.020s running
>
> Rust related unit tests are all passed.
>
> Best regards,
> I Hsin Cheng
> ---
>  rust/kernel/list.rs | 117 ++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 117 insertions(+)

This is a nice example, so

Reviewed-by: Benno Lossin <lossin@kernel.org>

It uses `unwrap` a lot, which might confuse newcomers that that is ok in
normal code. I'm wondering if we can do something about that though...

---
Cheers,
Benno

Re: [RFC PATCH v2] rust: list: Add examples for linked list

[Miguel Ojeda]

On Thu, May 22, 2025 at 11:52 AM Benno Lossin <lossin@kernel.org> wrote:
>
> This is a nice example, so
>
> Reviewed-by: Benno Lossin <lossin@kernel.org>
>
> It uses `unwrap` a lot, which might confuse newcomers that that is ok in
> normal code. I'm wondering if we can do something about that though...

Yeah, Danilo et al. mentioned this yesterday in the call.

I think it is not a big deal here since they are inside the
`assert*!`s (which one should not use anyway in normal code) -- the
other lines use `?`, which is good.

But as we discussed, I created a good first issue to tackle this for
both examples (since this one followed the cursor one):

    https://github.com/Rust-for-Linux/linux/issues/1164

I added your tag, by the way.

Cheers,
Miguel