Message-ID: <CAH5fLgjZEoHheUYfcb4QkgRMyy5MLz=60YrQd_Fa6O0LH1-Rgw@mail.gmail.com>
Date: Mon, 27 Jan 2025 11:35:29 +0100
From: Alice Ryhl <aliceryhl@...gle.com>
To: Boqun Feng <boqun.feng@...il.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 10:46 PM Boqun Feng <boqun.feng@...il.com> wrote:
>
> 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>

Done, thanks!

Alice

Powered by blists - more mailing lists