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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CAH5fLgjmM8fMH6ibfGAeqRMf3LMm3uoq+x3jtk73MoUChYB9wg@mail.gmail.com>
Date: Tue, 21 Jan 2025 08:55:44 +0100
From: Alice Ryhl <aliceryhl@...gle.com>
To: Andreas Hindborg <a.hindborg@...nel.org>
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

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

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