[PATCH] rust: list: make the cursor point between elements

[PATCH] rust: list: make the cursor point between elements

[Alice Ryhl]

I've been using the linked list cursor for a few different things, and I
find it inconvenient to use because all of the functions have signatures
along the lines of `Self -> Option<Self>`. The root cause of these
signatures is that the cursor points *at* an element, rather than
*between* two elements.

Thus, change the cursor API to point between two elements. This is
inspired by the stdlib linked list (well, really by this guy [1]), which
also uses cursors that point between elements.

The `peek_*` methods returns a helper that lets you look at and
optionally remove the element, as one common use-case of cursors is to
iterate a list to look for an element, then remove that element.

Another advantage is that this means you can now have a cursor into an
empty list.

Link: https://rust-unofficial.github.io/too-many-lists/sixth-cursors-intro.html [1]
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/list.rs | 325 +++++++++++++++++++++++++++++++-------------
 1 file changed, 231 insertions(+), 94 deletions(-)

diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index fb93330f4af4..328d3e369d57 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -245,8 +245,20 @@ pub fn is_empty(&self) -> bool {
         self.first.is_null()
     }
 
-    /// Add the provided item to the back of the list.
-    pub fn push_back(&mut self, item: ListArc<T, ID>) {
+    /// Inserts `item` before `next` in the cycle.
+    ///
+    /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list
+    /// is empty.
+    ///
+    /// # Safety
+    ///
+    /// * `next` must be an element in this list or null.
+    /// * if `next` is null, then the list must be empty.
+    unsafe fn insert_inner(
+        &mut self,
+        item: ListArc<T, ID>,
+        next: *mut ListLinksFields,
+    ) -> *mut ListLinksFields {
         let raw_item = ListArc::into_raw(item);
         // SAFETY:
         // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
@@ -259,16 +271,16 @@ pub fn push_back(&mut self, item: ListArc<T, ID>) {
         // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
         let item = unsafe { ListLinks::fields(list_links) };
 
-        if self.first.is_null() {
-            self.first = item;
+        // Check if the list is empty.
+        if next.is_null() {
             // SAFETY: The caller just gave us ownership of these fields.
             // INVARIANT: A linked list with one item should be cyclic.
             unsafe {
                 (*item).next = item;
                 (*item).prev = item;
             }
+            self.first = item;
         } else {
-            let next = self.first;
             // SAFETY: By the type invariant, this pointer is valid or null. We just checked that
             // it's not null, so it must be valid.
             let prev = unsafe { (*next).prev };
@@ -282,45 +294,24 @@ pub fn push_back(&mut self, item: ListArc<T, ID>) {
                 (*next).prev = item;
             }
         }
+
+        item
     }
 
+    /// Add the provided item to the back of the list.
+    pub fn push_back(&mut self, item: ListArc<T, ID>) {
+        // SAFETY:
+        // * `self.first` is null or in the list.
+        // * `self.first` is only null if the list is empty.
+        unsafe { self.insert_inner(item, self.first) };
+    }
+
     /// Add the provided item to the front of the list.
     pub fn push_front(&mut self, item: ListArc<T, ID>) {
-        let raw_item = ListArc::into_raw(item);
-        // SAFETY:
-        // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
-        // * If this requirement is violated, then the previous caller of `prepare_to_insert`
-        //   violated the safety requirement that they can't give up ownership of the `ListArc`
-        //   until they call `post_remove`.
-        // * We own the `ListArc`.
-        // * Removing items] from this list is always done using `remove_internal_inner`, which
-        //   calls `post_remove` before giving up ownership.
-        let list_links = unsafe { T::prepare_to_insert(raw_item) };
-        // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
-        let item = unsafe { ListLinks::fields(list_links) };
-
-        if self.first.is_null() {
-            // SAFETY: The caller just gave us ownership of these fields.
-            // INVARIANT: A linked list with one item should be cyclic.
-            unsafe {
-                (*item).next = item;
-                (*item).prev = item;
-            }
-        } else {
-            let next = self.first;
-            // SAFETY: We just checked that `next` is non-null.
-            let prev = unsafe { (*next).prev };
-            // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
-            // ownership of the fields on `item`.
-            // INVARIANT: This correctly inserts `item` between `prev` and `next`.
-            unsafe {
-                (*item).next = next;
-                (*item).prev = prev;
-                (*prev).next = item;
-                (*next).prev = item;
-            }
-        }
-        self.first = item;
+        // SAFETY:
+        // * `self.first` is null or in the list.
+        // * `self.first` is only null if the list is empty.
+        self.first = unsafe { self.insert_inner(item, self.first) };
     }
 
     /// Removes the last item from this list.
@@ -489,17 +480,21 @@ pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
         other.first = ptr::null_mut();
     }
 
-    /// Returns a cursor to the first element of the list.
-    ///
-    /// If the list is empty, this returns `None`.
-    pub fn cursor_front(&mut self) -> Option<Cursor<'_, T, ID>> {
-        if self.first.is_null() {
-            None
-        } else {
-            Some(Cursor {
-                current: self.first,
-                list: self,
-            })
-        }
-    }
+    /// Returns a cursor that points before the first element of the list.
+    pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> {
+        // INVARIANT: `self.first` is in this list.
+        Cursor {
+            next: self.first,
+            list: self,
+        }
+    }
+
+    /// Returns a cursor that points after the last element in the list.
+    pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> {
+        // INVARIANT: `next` is allowed to be null.
+        Cursor {
+            next: core::ptr::null_mut(),
+            list: self,
+        }
+    }
 
@@ -579,69 +574,211 @@ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
 
 /// 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.
+///
 /// # 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,
 }
 
 impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Cursor<'a, T, ID> {
+    /// Returns a pointer to the element before the cursor.
+    ///
+    /// Returns null if there is no element before the cursor.
+    fn prev_ptr(&self) -> *mut ListLinksFields {
+        let mut next = self.next;
+        let first = self.list.first;
+        if next == first {
+            // We are before the first element.
+            return core::ptr::null_mut();
+        }
+
+        if next.is_null() {
+            // We are after the last element, so we need a pointer to the last element, which is
+            // the same as `(*first).prev`.
+            next = first;
+        }
+
+        // SAFETY: `next` can't be null, because then `first` must also be null, but in that case
+        // we would have exited at the `next == first` check. Thus, `next` is an element in the
+        // list, so we can access its `prev` pointer.
+        unsafe { (*next).prev }
+    }
+
-    /// Access the current element of this cursor.
-    pub fn current(&self) -> ArcBorrow<'_, T> {
-        // SAFETY: The `current` pointer points a value in the list.
-        let me = unsafe { T::view_value(ListLinks::from_fields(self.current)) };
-        // SAFETY:
-        // * All values in a list are stored in an `Arc`.
-        // * The value cannot be removed from the list for the duration of the lifetime annotated
-        //   on the returned `ArcBorrow`, because removing it from the list would require mutable
-        //   access to the cursor or the list. However, the `ArcBorrow` holds an immutable borrow
-        //   on the cursor, which in turn holds a mutable borrow on the list, so any such
-        //   mutable access requires first releasing the immutable borrow on the cursor.
-        // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc`
-        //   reference, and `UniqueArc` references must be unique.
-        unsafe { ArcBorrow::from_raw(me) }
-    }
+    /// Access the element after this cursor.
+    pub fn peek_next(&mut self) -> Option<CursorPeek<'_, 'a, T, true, ID>> {
+        if self.next.is_null() {
+            return None;
+        }
+
+        // INVARIANT:
+        // * We just checked that `self.next` is non-null, so it must be in `self.list`.
+        // * `ptr` is equal to `self.next`.
+        Some(CursorPeek {
+            ptr: self.next,
+            cursor: self,
+        })
+    }
+
+    /// Access the element before this cursor.
+    pub fn peek_prev(&mut self) -> Option<CursorPeek<'_, 'a, T, false, ID>> {
+        let prev = self.prev_ptr();
+
+        if prev.is_null() {
+            return None;
+        }
+
+        // INVARIANT:
+        // * We just checked that `prev` is non-null, so it must be in `self.list`.
+        // * `self.prev_ptr()` never returns `self.next`.
+        Some(CursorPeek {
+            ptr: prev,
+            cursor: self,
+        })
+    }
 
-    /// Move the cursor to the next element.
-    pub fn next(self) -> Option<Cursor<'a, T, ID>> {
-        // SAFETY: The `current` field is always in a list.
-        let next = unsafe { (*self.current).next };
-
-        if next == self.list.first {
-            None
-        } else {
-            // INVARIANT: Since `self.current` is in the `list`, its `next` pointer is also in the
-            // `list`.
-            Some(Cursor {
-                current: next,
-                list: self.list,
-            })
-        }
-    }
+    /// Move the cursor one element forward.
+    ///
+    /// If the cursor is after the last element, then the cursor will move back to the beginning.
+    pub fn move_next(&mut self) {
+        if self.next.is_null() {
+            // INVARIANT: `list.first` is in the list or null.
+            self.next = self.list.first;
+            return;
+        }
+
+        // SAFETY: `self.next` is an element in the list and we borrow the list mutably, so we can
+        // access the `next` field.
+        let mut next = unsafe { (*self.next).next };
+
+        if next == self.list.first {
+            next = core::ptr::null_mut();
+        }
+
+        // INVARIANT: `next` is either null or the next element after an element in the list.
+        self.next = next;
+    }
 
-    /// Move the cursor to the previous element.
-    pub fn prev(self) -> Option<Cursor<'a, T, ID>> {
-        // SAFETY: The `current` field is always in a list.
-        let prev = unsafe { (*self.current).prev };
-
-        if self.current == self.list.first {
-            None
-        } else {
-            // INVARIANT: Since `self.current` is in the `list`, its `prev` pointer is also in the
-            // `list`.
-            Some(Cursor {
-                current: prev,
-                list: self.list,
-            })
-        }
-    }
+    /// Move the cursor one element backwards.
+    ///
+    /// If the cursor is before the first element, then the cursor will move to the end of the
+    /// list.
+    pub fn move_prev(&mut self) {
+        if self.next == self.list.first {
+            // We are before the first element, so move the cursor after the last element.
+            // INVARIANT: `next` can be a null pointer.
+            self.next = core::ptr::null_mut();
+            return;
+        }
+
+        // INVARIANT: `prev_ptr()` always returns a pointer that is null or in the list.
+        self.next = self.prev_ptr();
+    }
+
+    /// Inserts an element where the cursor is pointing and get a pointer to the new element.
+    fn insert_inner(&mut self, item: ListArc<T, ID>) -> *mut ListLinksFields {
+        let ptr = if self.next.is_null() {
+            self.list.first
+        } else {
+            self.next
+        };
+        // SAFETY:
+        // * `ptr` is an element in the list or null.
+        // * if `ptr` is null, then `self.list.first` is null so the list is empty.
+        unsafe { self.list.insert_inner(item, ptr) }
+    }
+
+    /// Inserts an element after this cursor.
+    pub fn insert_next(&mut self, item: ListArc<T, ID>) {
+        self.next = self.insert_inner(item);
+    }
+
+    /// Inserts an element before this cursor.
+    pub fn insert_prev(&mut self, item: ListArc<T, ID>) {
+        self.insert_inner(item);
+    }
 
-    /// Remove the current element from the list.
-    pub fn remove(self) -> ListArc<T, ID> {
-        // SAFETY: The `current` pointer always points at a member of the list.
-        unsafe { self.list.remove_internal(self.current) }
-    }
+    /// Remove the next element from the list.
+    pub fn remove_next(&mut self) -> Option<ListArc<T, ID>> {
+        self.peek_next().map(|v| v.remove())
+    }
+
+    /// Remove the previous element from the list.
+    pub fn remove_prev(&mut self) -> Option<ListArc<T, ID>> {
+        self.peek_prev().map(|v| v.remove())
+    }
 }
+
+/// References the element in the list next to the cursor.
+///
+/// # Invariants
+///
+/// * `ptr` is an element in `self.cursor.list`.
+/// * `ISNEXT == (self.ptr == self.cursor.next)`.
+pub struct CursorPeek<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> {
+    cursor: &'a mut Cursor<'b, T, ID>,
+    ptr: *mut ListLinksFields,
+}
+
+impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64>
+    CursorPeek<'a, 'b, T, ISNEXT, ID>
+{
+    /// Remove the element from the list.
+    pub fn remove(self) -> ListArc<T, ID> {
+        if ISNEXT {
+            self.cursor.move_next();
+        }
+
+        // INVARIANT: `self.ptr` is not equal to `self.cursor.next` due to the above `move_next`
+        // call.
+        // SAFETY: By the type invariants of `Self`, `next` is not null, so `next` is an element of
+        // `self.cursor.list` by the type invariants of `Cursor`.
+        unsafe { self.cursor.list.remove_internal(self.ptr) }
+    }
+
+    /// Access this value as an [`ArcBorrow`].
+    pub fn arc(&self) -> ArcBorrow<'_, T> {
+        // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
+        let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) };
+        // SAFETY:
+        // * All values in a list are stored in an `Arc`.
+        // * The value cannot be removed from the list for the duration of the lifetime annotated
+        //   on the returned `ArcBorrow`, because removing it from the list would require mutable
+        //   access to the `CursorPeek`, the `Cursor` or the `List`. However, the `ArcBorrow` holds
+        //   an immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the
+        //   `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable
+        //   access requires first releasing the immutable borrow on the `CursorPeek`.
+        // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc`
+        //   reference, and `UniqueArc` references must be unique.
+        unsafe { ArcBorrow::from_raw(me) }
+    }
+}
+
+impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> core::ops::Deref
+    for CursorPeek<'a, 'b, T, ISNEXT, ID>
+{
+    // This can't use `ArcBorrow<'a, T>` as the target type because 'a is too long. It would let
+    // you obtain an `ArcBorrow<'a, T>` and then call `CursorPeek::remove` without giving up the
+    // `ArcBorrow<'a, T>`.
+    type Target = T;
+
+    fn deref(&self) -> &T {
+        // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
+        let me = unsafe { T::view_value(ListLinks::from_fields(self.cursor.next)) };
+
+        // SAFETY: The value cannot be removed from the list for the duration of the lifetime
+        // annotated on the returned `&T`, because removing it from the list would require mutable
+        // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `&T` holds an
+        // immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the
+        // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable access
+        // requires first releasing the immutable borrow on the `CursorPeek`.
+        unsafe { &*me }
+    }
+}
 
---
base-commit: 6ce162a002657910104c7a07fb50017681bc476c
change-id: 20241016-cursor-between-154bed859e27

Best regards,
-- 
Alice Ryhl <aliceryhl@google.com>

Re: [PATCH] rust: list: make the cursor point between elements

[Andreas Hindborg]

Hi Alice,

This looks like a nice improvement!

"Alice Ryhl" <aliceryhl@google.com> writes:

> I've been using the linked list cursor for a few different things, and I
> find it inconvenient to use because all of the functions have signatures
> along the lines of `Self -> Option<Self>`. The root cause of these
> signatures is that the cursor points *at* an element, rather than
> *between* two elements.
>
> Thus, change the cursor API to point between two elements. This is
> inspired by the stdlib linked list (well, really by this guy [1]), which
> also uses cursors that point between elements.
>
> The `peek_*` methods returns a helper that lets you look at and
> optionally remove the element, as one common use-case of cursors is to
> iterate a list to look for an element, then remove that element.
>
> Another advantage is that this means you can now have a cursor into an
> empty list.
>
> Link: https://rust-unofficial.github.io/too-many-lists/sixth-cursors-intro.html [1]
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  rust/kernel/list.rs | 325 +++++++++++++++++++++++++++++++-------------
>  1 file changed, 231 insertions(+), 94 deletions(-)
>
> diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
> index fb93330f4af4..328d3e369d57 100644
> --- a/rust/kernel/list.rs
> +++ b/rust/kernel/list.rs
> @@ -245,8 +245,20 @@ pub fn is_empty(&self) -> bool {
>          self.first.is_null()
>      }
>
> -    /// Add the provided item to the back of the list.
> -    pub fn push_back(&mut self, item: ListArc<T, ID>) {
> +    /// Inserts `item` before `next` in the cycle.
> +    ///
> +    /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list
> +    /// is empty.
> +    ///
> +    /// # Safety
> +    ///
> +    /// * `next` must be an element in this list or null.
> +    /// * if `next` is null, then the list must be empty.
> +    unsafe fn insert_inner(
> +        &mut self,
> +        item: ListArc<T, ID>,
> +        next: *mut ListLinksFields,
> +    ) -> *mut ListLinksFields {
>          let raw_item = ListArc::into_raw(item);
>          // SAFETY:
>          // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
> @@ -259,16 +271,16 @@ pub fn push_back(&mut self, item: ListArc<T, ID>) {
>          // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
>          let item = unsafe { ListLinks::fields(list_links) };
>
> -        if self.first.is_null() {
> -            self.first = item;
> +        // Check if the list is empty.
> +        if next.is_null() {
>              // SAFETY: The caller just gave us ownership of these fields.
>              // INVARIANT: A linked list with one item should be cyclic.
>              unsafe {
>                  (*item).next = item;
>                  (*item).prev = item;
>              }
> +            self.first = item;
>          } else {
> -            let next = self.first;
>              // SAFETY: By the type invariant, this pointer is valid or null. We just checked that
>              // it's not null, so it must be valid.
>              let prev = unsafe { (*next).prev };
> @@ -282,45 +294,24 @@ pub fn push_back(&mut self, item: ListArc<T, ID>) {
>                  (*next).prev = item;
>              }
>          }
> +
> +        item
>      }
>
> +    /// Add the provided item to the back of the list.
> +    pub fn push_back(&mut self, item: ListArc<T, ID>) {
> +        // SAFETY:
> +        // * `self.first` is null or in the list.
> +        // * `self.first` is only null if the list is empty.
> +        unsafe { self.insert_inner(item, self.first) };
> +    }
> +
>      /// Add the provided item to the front of the list.
>      pub fn push_front(&mut self, item: ListArc<T, ID>) {
> -        let raw_item = ListArc::into_raw(item);
> -        // SAFETY:
> -        // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
> -        // * If this requirement is violated, then the previous caller of `prepare_to_insert`
> -        //   violated the safety requirement that they can't give up ownership of the `ListArc`
> -        //   until they call `post_remove`.
> -        // * We own the `ListArc`.
> -        // * Removing items] from this list is always done using `remove_internal_inner`, which
> -        //   calls `post_remove` before giving up ownership.
> -        let list_links = unsafe { T::prepare_to_insert(raw_item) };
> -        // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
> -        let item = unsafe { ListLinks::fields(list_links) };
> -
> -        if self.first.is_null() {
> -            // SAFETY: The caller just gave us ownership of these fields.
> -            // INVARIANT: A linked list with one item should be cyclic.
> -            unsafe {
> -                (*item).next = item;
> -                (*item).prev = item;
> -            }
> -        } else {
> -            let next = self.first;
> -            // SAFETY: We just checked that `next` is non-null.
> -            let prev = unsafe { (*next).prev };
> -            // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
> -            // ownership of the fields on `item`.
> -            // INVARIANT: This correctly inserts `item` between `prev` and `next`.
> -            unsafe {
> -                (*item).next = next;
> -                (*item).prev = prev;
> -                (*prev).next = item;
> -                (*next).prev = item;
> -            }
> -        }
> -        self.first = item;
> +        // SAFETY:
> +        // * `self.first` is null or in the list.
> +        // * `self.first` is only null if the list is empty.
> +        self.first = unsafe { self.insert_inner(item, self.first) };
>      }
>
>      /// Removes the last item from this list.

This looks like a refactor of `push_front`, `push_back`. It looks like
it is unrelated to the cursor change. Can you split this out into a
separate patch?


> @@ -489,17 +480,21 @@ pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
>          other.first = ptr::null_mut();
>      }
>
> -    /// Returns a cursor to the first element of the list.
> -    ///
> -    /// If the list is empty, this returns `None`.
> -    pub fn cursor_front(&mut self) -> Option<Cursor<'_, T, ID>> {
> -        if self.first.is_null() {
> -            None
> -        } else {
> -            Some(Cursor {
> -                current: self.first,
> -                list: self,
> -            })
> -        }
> -    }
> +    /// Returns a cursor that points before the first element of the list.
> +    pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> {
> +        // INVARIANT: `self.first` is in this list.
> +        Cursor {
> +            next: self.first,
> +            list: self,
> +        }
> +    }
> +
> +    /// Returns a cursor that points after the last element in the list.
> +    pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> {
> +        // INVARIANT: `next` is allowed to be null.
> +        Cursor {
> +            next: core::ptr::null_mut(),

I am slightly confused about why you need to track the beginning and end
of the list. The cursor movement operations circle have wrapping
semantics and the lists are circular. Could you remove some code by
using this property?

> +            list: self,
> +        }
> +    }
>
> @@ -579,69 +574,211 @@ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
>
>  /// 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.
> +///
>  /// # Invariants
>  ///
> -/// The `current` pointer points a value in `list`.
> +/// The `next` pointer is null or points a value in `list`.

Could you add an example of how to use this struct?

Unrelated, but since you are at it, could you update the safety comment
on first line in the `List::remove` function?


Best regards,
Andreas Hindborg

Re: [PATCH] rust: list: make the cursor point between elements

[Alice Ryhl]

On Mon, Jan 20, 2025 at 12:55 PM Andreas Hindborg <a.hindborg@kernel.org> wrote:
>
> Hi Alice,
>
> This looks like a nice improvement!

Thanks!

> This looks like a refactor of `push_front`, `push_back`. It looks like
> it is unrelated to the cursor change. Can you split this out into a
> separate patch?

I don't think it's unrelated. It extracts out common code that
previously only push_front/push_back have, but that the cursor now
also needs. Of course, it could still make sense to extract
insert_inner out in a separate patch.

> > @@ -489,17 +480,21 @@ pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
> >          other.first = ptr::null_mut();
> >      }
> >
> > -    /// Returns a cursor to the first element of the list.
> > -    ///
> > -    /// If the list is empty, this returns `None`.
> > -    pub fn cursor_front(&mut self) -> Option<Cursor<'_, T, ID>> {
> > -        if self.first.is_null() {
> > -            None
> > -        } else {
> > -            Some(Cursor {
> > -                current: self.first,
> > -                list: self,
> > -            })
> > -        }
> > -    }
> > +    /// Returns a cursor that points before the first element of the list.
> > +    pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> {
> > +        // INVARIANT: `self.first` is in this list.
> > +        Cursor {
> > +            next: self.first,
> > +            list: self,
> > +        }
> > +    }
> > +
> > +    /// Returns a cursor that points after the last element in the list.
> > +    pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> {
> > +        // INVARIANT: `next` is allowed to be null.
> > +        Cursor {
> > +            next: core::ptr::null_mut(),
>
> I am slightly confused about why you need to track the beginning and end
> of the list. The cursor movement operations circle have wrapping
> semantics and the lists are circular. Could you remove some code by
> using this property?

I think the current API is much more intuitive. Yes, the list is
implemented in a circular manner, but you're not intended to think of
it that way. The linked list is a list of elements. With elements ABC
and cursors pointing between them, it makes sense that the cursor can
be |ABC, A|BC, AB|C, ABC|. In each case, you can add an element before
or after the cursor. To iterate the list, you keep calling `move_next`
until `next` returns `None`. That also makes sense. If the cursor
becomes circular, then you iterate by calling `next` until the next
element is the first element? Seems confusing to me.

I also don't think it's much less code. You still need to handle null
pointers because the list might be empty.

> > +            list: self,
> > +        }
> > +    }
> >
> > @@ -579,69 +574,211 @@ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
> >
> >  /// 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.
> > +///
> >  /// # Invariants
> >  ///
> > -/// The `current` pointer points a value in `list`.
> > +/// The `next` pointer is null or points a value in `list`.
>
> Could you add an example of how to use this struct?
>
> Unrelated, but since you are at it, could you update the safety comment
> on first line in the `List::remove` function?

Okay, will look at this.

Alice

Re: [PATCH] rust: list: make the cursor point between elements

[Andreas Hindborg]

"Alice Ryhl" <aliceryhl@google.com> writes:

> On Mon, Jan 20, 2025 at 12:55 PM Andreas Hindborg <a.hindborg@kernel.org> wrote:
>>
>> Hi Alice,
>>
>> This looks like a nice improvement!
>
> Thanks!
>
>> This looks like a refactor of `push_front`, `push_back`. It looks like
>> it is unrelated to the cursor change. Can you split this out into a
>> separate patch?
>
> I don't think it's unrelated. It extracts out common code that
> previously only push_front/push_back have, but that the cursor now
> also needs. Of course, it could still make sense to extract
> insert_inner out in a separate patch.

I think that would make sense.

>
>> > @@ -489,17 +480,21 @@ pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
>> >          other.first = ptr::null_mut();
>> >      }
>> >
>> > -    /// Returns a cursor to the first element of the list.
>> > -    ///
>> > -    /// If the list is empty, this returns `None`.
>> > -    pub fn cursor_front(&mut self) -> Option<Cursor<'_, T, ID>> {
>> > -        if self.first.is_null() {
>> > -            None
>> > -        } else {
>> > -            Some(Cursor {
>> > -                current: self.first,
>> > -                list: self,
>> > -            })
>> > -        }
>> > -    }
>> > +    /// Returns a cursor that points before the first element of the list.
>> > +    pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> {
>> > +        // INVARIANT: `self.first` is in this list.
>> > +        Cursor {
>> > +            next: self.first,
>> > +            list: self,
>> > +        }
>> > +    }
>> > +
>> > +    /// Returns a cursor that points after the last element in the list.
>> > +    pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> {
>> > +        // INVARIANT: `next` is allowed to be null.
>> > +        Cursor {
>> > +            next: core::ptr::null_mut(),
>>
>> I am slightly confused about why you need to track the beginning and end
>> of the list. The cursor movement operations circle have wrapping
>> semantics and the lists are circular. Could you remove some code by
>> using this property?
>
> I think the current API is much more intuitive. Yes, the list is
> implemented in a circular manner, but you're not intended to think of
> it that way. The linked list is a list of elements. With elements ABC
> and cursors pointing between them, it makes sense that the cursor can
> be |ABC, A|BC, AB|C, ABC|. In each case, you can add an element before
> or after the cursor. To iterate the list, you keep calling `move_next`
> until `next` returns `None`. That also makes sense. If the cursor
> becomes circular, then you iterate by calling `next` until the next
> element is the first element? Seems confusing to me.

You might be right. But then again, in your patch the cursor _does_ wrap to the front
when it is at the end. If we did not treat beginning and end as two
separate states, we could remove a lot of edge case checks, see below.

In your experience using the API, did you use the feature that
`move_next` will wrap to the front? If the cursor is circular, maybe
`move_next` and `move_prev` should should be no-ops when the cursor is
in edge positions?

With a circular cursor, you would need to compare to first or last as to
break an iteration loop. I think that is how the C API works.

With a circular cursor it would be something like this

let mut c = list.cursor_front();
let last = c.peek_prev();
loop {
  let el = c.peek_next();
  // Do stuff
  if el == last {
    break;
  }
}

For a non-circular cursor

let mut c = list.cursor_front();
loop {
  let el = c.peek_next();
  if el.is_none() {
    break
  }
  // Do stuff
  c.move_next();
}

Not too much difference?


diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index 328d3e369d571..e1d0608e66dc8 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -589,26 +589,15 @@ pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
 
 impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Cursor<'a, T, ID> {
     /// Returns a pointer to the element before the cursor.
-    ///
-    /// Returns null if there is no element before the cursor.
     fn prev_ptr(&self) -> *mut ListLinksFields {
-        let mut next = self.next;
-        let first = self.list.first;
-        if next == first {
-            // We are before the first element.
-            return core::ptr::null_mut();
-        }
-
-        if next.is_null() {
-            // We are after the last element, so we need a pointer to the last element, which is
-            // the same as `(*first).prev`.
-            next = first;
+        if self.next.is_null() {
+            return self.next;
         }
 
         // SAFETY: `next` can't be null, because then `first` must also be null, but in that case
         // we would have exited at the `next == first` check. Thus, `next` is an element in the
         // list, so we can access its `prev` pointer.
-        unsafe { (*next).prev }
+        unsafe { (*self.next).prev }
     }
 
     /// Access the element after this cursor.
@@ -648,8 +637,6 @@ pub fn peek_prev(&mut self) -> Option<CursorPeek<'_, 'a, T, false, ID>> {
     /// If the cursor is after the last element, then the cursor will move back to the beginning.
     pub fn move_next(&mut self) {
         if self.next.is_null() {
-            // INVARIANT: `list.first` is in the list or null.
-            self.next = self.list.first;
             return;
         }
 
@@ -657,10 +644,6 @@ pub fn move_next(&mut self) {
         // access the `next` field.
         let mut next = unsafe { (*self.next).next };
 
-        if next == self.list.first {
-            next = core::ptr::null_mut();
-        }
-
         // INVARIANT: `next` is either null or the next element after an element in the list.
         self.next = next;
     }
@@ -670,24 +653,13 @@ pub fn move_next(&mut self) {
     /// If the cursor is before the first element, then the cursor will move to the end of the
     /// list.
     pub fn move_prev(&mut self) {
-        if self.next == self.list.first {
-            // We are before the first element, so move the cursor after the last element.
-            // INVARIANT: `next` can be a null pointer.
-            self.next = core::ptr::null_mut();
-            return;
-        }
-
         // INVARIANT: `prev_ptr()` always returns a pointer that is null or in the list.
         self.next = self.prev_ptr();
     }
 
     /// Inserts an element where the cursor is pointing and get a pointer to the new element.
     fn insert_inner(&mut self, item: ListArc<T, ID>) -> *mut ListLinksFields {
-        let ptr = if self.next.is_null() {
-            self.list.first
-        } else {
-            self.next
-        };
+        let ptr = self.next;
         // SAFETY:
         // * `ptr` is an element in the list or null.
         // * if `ptr` is null, then `self.list.first` is null so the list is empty.




Best regards,
Andreas Hindborg

Re: [PATCH] rust: list: make the cursor point between elements

[Alice Ryhl]

On Mon, Jan 20, 2025 at 10:12 PM Andreas Hindborg <a.hindborg@kernel.org> wrote:
>
> "Alice Ryhl" <aliceryhl@google.com> writes:
>
> > On Mon, Jan 20, 2025 at 12:55 PM Andreas Hindborg <a.hindborg@kernel.org> wrote:
> >>
> >> Hi Alice,
> >>
> >> This looks like a nice improvement!
> >
> > Thanks!
> >
> >> This looks like a refactor of `push_front`, `push_back`. It looks like
> >> it is unrelated to the cursor change. Can you split this out into a
> >> separate patch?
> >
> > I don't think it's unrelated. It extracts out common code that
> > previously only push_front/push_back have, but that the cursor now
> > also needs. Of course, it could still make sense to extract
> > insert_inner out in a separate patch.
>
> I think that would make sense.
>
> >
> >> > @@ -489,17 +480,21 @@ pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
> >> >          other.first = ptr::null_mut();
> >> >      }
> >> >
> >> > -    /// Returns a cursor to the first element of the list.
> >> > -    ///
> >> > -    /// If the list is empty, this returns `None`.
> >> > -    pub fn cursor_front(&mut self) -> Option<Cursor<'_, T, ID>> {
> >> > -        if self.first.is_null() {
> >> > -            None
> >> > -        } else {
> >> > -            Some(Cursor {
> >> > -                current: self.first,
> >> > -                list: self,
> >> > -            })
> >> > -        }
> >> > -    }
> >> > +    /// Returns a cursor that points before the first element of the list.
> >> > +    pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> {
> >> > +        // INVARIANT: `self.first` is in this list.
> >> > +        Cursor {
> >> > +            next: self.first,
> >> > +            list: self,
> >> > +        }
> >> > +    }
> >> > +
> >> > +    /// Returns a cursor that points after the last element in the list.
> >> > +    pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> {
> >> > +        // INVARIANT: `next` is allowed to be null.
> >> > +        Cursor {
> >> > +            next: core::ptr::null_mut(),
> >>
> >> I am slightly confused about why you need to track the beginning and end
> >> of the list. The cursor movement operations circle have wrapping
> >> semantics and the lists are circular. Could you remove some code by
> >> using this property?
> >
> > I think the current API is much more intuitive. Yes, the list is
> > implemented in a circular manner, but you're not intended to think of
> > it that way. The linked list is a list of elements. With elements ABC
> > and cursors pointing between them, it makes sense that the cursor can
> > be |ABC, A|BC, AB|C, ABC|. In each case, you can add an element before
> > or after the cursor. To iterate the list, you keep calling `move_next`
> > until `next` returns `None`. That also makes sense. If the cursor
> > becomes circular, then you iterate by calling `next` until the next
> > element is the first element? Seems confusing to me.
>
> You might be right. But then again, in your patch the cursor _does_ wrap to the front
> when it is at the end. If we did not treat beginning and end as two
> separate states, we could remove a lot of edge case checks, see below.
>
> In your experience using the API, did you use the feature that
> `move_next` will wrap to the front? If the cursor is circular, maybe
> `move_next` and `move_prev` should should be no-ops when the cursor is
> in edge positions?

That's fair. I will update move_next/move_prev to be no-ops at the edge.

> With a circular cursor, you would need to compare to first or last as to
> break an iteration loop. I think that is how the C API works.
>
> With a circular cursor it would be something like this
>
> let mut c = list.cursor_front();
> let last = c.peek_prev();
> loop {
>   let el = c.peek_next();
>   // Do stuff
>   if el == last {
>     break;
>   }
> }
>
> For a non-circular cursor
>
> let mut c = list.cursor_front();
> loop {
>   let el = c.peek_next();
>   if el.is_none() {
>     break
>   }
>   // Do stuff
>   c.move_next();
> }
>
> Not too much difference?

It can be nicer than either of those if you use a while let loop. See
the examples in my next version.

I don't want to make the API circular because I think it's a worse
user-experience.

Alice