Message-ID: <877c6pchqi.fsf@kernel.org>
Date: Mon, 20 Jan 2025 22:12:21 +0100
From: Andreas Hindborg <a.hindborg@...nel.org>
To: "Alice Ryhl" <aliceryhl@...gle.com>
Cc: "Miguel Ojeda" <ojeda@...nel.org>,  "Alex Gaynor"
 <alex.gaynor@...il.com>,  "Boqun Feng" <boqun.feng@...il.com>,  "Gary Guo"
 <gary@...yguo.net>,  Björn Roy Baron
 <bjorn3_gh@...tonmail.com>,  "Benno
 Lossin" <benno.lossin@...ton.me>,  "Trevor Gross" <tmgross@...ch.edu>,
  <rust-for-linux@...r.kernel.org>,  <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] rust: list: make the cursor point between elements

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

> On Mon, Jan 20, 2025 at 12:55 PM Andreas Hindborg <a.hindborg@...nel.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

Powered by blists - more mailing lists