Message-ID: <Z5K4fPgPBNOJaJGl@boqun-archlinux>
Date: Thu, 23 Jan 2025 13:45:32 -0800
From: Boqun Feng <boqun.feng@...il.com>
To: Alice Ryhl <aliceryhl@...gle.com>
Cc: Miguel Ojeda <ojeda@...nel.org>, Alex Gaynor <alex.gaynor@...il.com>,
	Gary Guo <gary@...yguo.net>,
	Björn Roy Baron <bjorn3_gh@...tonmail.com>,
	Benno Lossin <benno.lossin@...ton.me>,
	Andreas Hindborg <a.hindborg@...nel.org>,
	Trevor Gross <tmgross@...ch.edu>, rust-for-linux@...r.kernel.org,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH v4 2/2] rust: list: make the cursor point between elements

On Thu, Jan 23, 2025 at 11:01:09AM +0000, Alice Ryhl wrote:
[...]
>  
>  /// A cursor into a [`List`].
>  ///
> +/// A cursor always rests between two elements in the list. This means that a cursor has a previous
> +/// and next element, but no current element. It also means that it's possible to have a cursor
> +/// into an empty list.
> +///
> +/// # Examples
> +///
> +/// ```
> +/// use kernel::prelude::*;
> +/// use kernel::list::{List, ListArc, ListLinks};
> +///
> +/// #[pin_data]
> +/// struct ListItem {
> +///     value: u32,
> +///     #[pin]
> +///     links: ListLinks,
> +/// }
> +///
> +/// impl ListItem {
> +///     fn new(value: u32) -> Result<ListArc<Self>> {
> +///         ListArc::pin_init(try_pin_init!(Self {
> +///             value,
> +///             links <- ListLinks::new(),
> +///         }), GFP_KERNEL)
> +///     }
> +/// }
> +///
> +/// kernel::list::impl_has_list_links! {
> +///     impl HasListLinks<0> for ListItem { self.links }
> +/// }
> +/// kernel::list::impl_list_arc_safe! {
> +///     impl ListArcSafe<0> for ListItem { untracked; }
> +/// }
> +/// kernel::list::impl_list_item! {
> +///     impl ListItem<0> for ListItem { using ListLinks; }
> +/// }
> +///
> +/// // Use a cursor to remove the first element with the given value.
> +/// fn remove_first(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
> +///     let mut cursor = list.cursor_front();
> +///     while let Some(next) = cursor.peek_next() {
> +///         if next.value == value {
> +///             return Some(next.remove());
> +///         }
> +///         cursor.move_next();
> +///     }
> +///     None
> +/// }
> +///
> +/// // Use a cursor to remove all elements with the given value. The removed elements are moved to
> +/// // a new list.
> +/// fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> {
> +///     let mut out = List::new();
> +///     let mut cursor = list.cursor_front();
> +///     while let Some(next) = cursor.peek_next() {
> +///         if next.value == value {
> +///             out.push_back(next.remove());
> +///         } else {
> +///             cursor.move_next();
> +///         }
> +///     }
> +///     out
> +/// }
> +///
> +/// // Use a cursor to insert a value at a specific index. Returns an error if the index is out of
> +/// // bounds.
> +/// fn insert_at(list: &mut List<ListItem>, new: ListArc<ListItem>, idx: usize) -> Result {
> +///     let mut cursor = list.cursor_front();
> +///     for _ in 0..idx {
> +///         if !cursor.move_next() {
> +///             return Err(EINVAL);
> +///         }
> +///     }
> +///     cursor.insert_next(new);
> +///     Ok(())
> +/// }
> +///
> +/// // Merge two sorted lists into a single sorted list.
> +/// fn merge_sorted(list: &mut List<ListItem>, merge: List<ListItem>) {
> +///     let mut cursor = list.cursor_front();
> +///     for to_insert in merge {
> +///         while let Some(next) = cursor.peek_next() {
> +///             if to_insert.value < next.value {
> +///                 break;
> +///             }
> +///             cursor.move_next();
> +///         }
> +///         cursor.insert_prev(to_insert);
> +///     }
> +/// }
> +///
> +/// let mut list = List::new();
> +/// list.push_back(ListItem::new(14)?);
> +/// list.push_back(ListItem::new(12)?);
> +/// list.push_back(ListItem::new(10)?);
> +/// list.push_back(ListItem::new(12)?);
> +/// list.push_back(ListItem::new(14)?);
> +/// assert_eq!(remove_all(&mut list, 12).iter().count(), 2);
> +/// // [14, 10, 14]
> +/// assert!(remove_first(&mut list, 14).is_some());
> +/// // [10, 14]
> +/// insert_at(&mut list, ListItem::new(12)?, 1)?;
> +/// // [10, 12, 14]
> +///
> +/// let mut list2 = List::new();
> +/// list.push_back(ListItem::new(11)?);
> +/// list.push_back(ListItem::new(13)?);

These need to be `list2` instead of `list`, otherwise the doctest will
fail.

> +/// merge_sorted(&mut list, list2);
> +///
> +/// let mut items = list.into_iter();
> +/// assert_eq!(items.next().unwrap().value, 10);
> +/// assert_eq!(items.next().unwrap().value, 11);
> +/// assert_eq!(items.next().unwrap().value, 12);
> +/// assert_eq!(items.next().unwrap().value, 13);
> +/// assert_eq!(items.next().unwrap().value, 14);
> +/// assert!(items.next().is_none());
> +/// # Result::<(), Error>::Ok(())
> +/// ```
> +///
>  /// # Invariants
>  ///
> -/// The `current` pointer points a value in `list`.
> +/// The `next` pointer is null or points a value in `list`.
>  pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
> -    current: *mut ListLinksFields,
>      list: &'a mut List<T, ID>,
> +    /// Points at the element after this cursor, or null if the cursor is after the last element.
> +    next: *mut ListLinksFields,
>  }
>  
[...]

While we are at it, could you also add a doc test that uses
`cursor_back()` and `move_prev()`? Something like below, that would
show (and at least test a bit on) the API for another direction.

With all these, feel free to add:

Reviewed-by: Boqun Feng <boqun.feng@...il.com>

Regards,
Boqun

------>8
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index b83016e5bcd9..2d38fbaf94e3 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -625,6 +625,18 @@ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
 ///     None
 /// }
 ///
+/// // Use a cursor to remove the last element with the given value.
+/// fn remove_last(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
+///     let mut cursor = list.cursor_back();
+///     while let Some(prev) = cursor.peek_prev() {
+///         if prev.value == value {
+///             return Some(prev.remove());
+///         }
+///         cursor.move_prev();
+///     }
+///     None
+/// }
+///
 /// // Use a cursor to remove all elements with the given value. The removed elements are moved to
 /// // a new list.
 /// fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> {
@@ -672,12 +684,15 @@ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
 /// list.push_back(ListItem::new(12)?);
 /// list.push_back(ListItem::new(10)?);
 /// list.push_back(ListItem::new(12)?);
+/// list.push_back(ListItem::new(15)?);
 /// list.push_back(ListItem::new(14)?);
 /// assert_eq!(remove_all(&mut list, 12).iter().count(), 2);
-/// // [14, 10, 14]
+/// // [14, 10, 15, 14]
 /// assert!(remove_first(&mut list, 14).is_some());
+/// // [10, 15, 14]
+/// assert!(remove_last(&mut list, 15).is_some());
 /// // [10, 14]
 /// insert_at(&mut list, ListItem::new(12)?, 1)?;
 /// // [10, 12, 14]
 ///
 /// let mut list2 = List::new();

Powered by blists - more mailing lists