rust: list: make the cursor point between elements
Alice Ryhl
reviewerPATCH 1/1 rust: list: make the cursor point between elements
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.
--- rust/kernel/list.rs | 325 +++++++++++++++++++++++++++++++------------- 1 file changed, 231 insertions(+), 94 deletions(-)
rust/kernel/list.rs +244 -107
@@ -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: &'amut 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: &'amut 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,
Signature · 1 line
Alice Ryhl <[email protected]>
Andreas Hindborg
reviewerHi Alice,
This looks like a nice improvement!
Quoted 120 lines · 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.
Signed-off-by Alice Ryhl <[email protected]>--- rust/kernel/list.rs | 325 +++++++++++++++++++++++++++++++------------- 1 file changed, 231 insertions(+), 94 deletions(-)rust/kernel/list.rs +27
-37@@ -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;
rust/kernel/list.rs pub fn push_back(&mut self, item: ListArc<T, ID>) { · line 317
Quoted 10 lines
rust/kernel/list.rs +4
-3- } - } - 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?
Quoted 21 lines
rust/kernel/list.rs +4
-13@@ -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 {
rust/kernel/list.rs pub fn push_all_back(&mut self, other: &mut List<T, ID>) { · line 496
Quoted 10 lines
rust/kernel/list.rs +10
-0+ 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?
Quoted 6 lines
rust/kernel/list.rs +3
-0+ list: self, + } + }@@ -579,69 +574,211 @@ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
rust/kernel/list.rs fn next(&mut self) -> Option<ArcBorrow<'a, T>> { · line 583
Quoted 10 lines
rust/kernel/list.rs +5
-1/// 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
Alice Ryhl
reviewerQuoted 4 lines · Andreas Hindborg
Hi Alice,
This looks like a nice improvement!
Thanks!
Quoted 3 lines
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.
Quoted 28 lines
Quoted 28 lines
rust/kernel/list.rs +11
-13@@ -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 > {
Quoted 8 lines
rust/kernel/list.rs pub fn push_all_back(&mut self, other: &mut List<T, ID>) { · line 496
Quoted 3 lines
rust/kernel/list.rs +3
-0+// 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.
Quoted 19 lines
Quoted 6 lines
rust/kernel/list.rs +3
-0+ list: self, + } + }@@ -579,69 +574,211 @@ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {rust/kernel/list.rs fn next(&mut self) -> Option<ArcBorrow<'a, T>> { · line 583
Quoted 10 lines
rust/kernel/list.rs +5
-1/// 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?
Quoted 2 lines
Unrelated, but since you are at it, could you update the safety comment on first line in the
List::removefunction?
Okay, will look at this.
Alice
Andreas Hindborg
reviewerQuoted 8 lines · Alice Ryhl
Quoted 4 lines · Andreas Hindborg
Hi Alice,
This looks like a nice improvement!
Thanks!
Quoted 8 lines
Quoted 3 lines
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_innerout in a separate patch.
I think that would make sense.
Quoted 38 lines
Quoted 29 lines
Quoted 29 lines
(quoted diff) +11
-13@@ -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> {Quoted 8 lines
Review pub fn push_all_back(&mut self, other: &mut List<T, ID>) { · line 496
Quoted 3 lines
(quoted diff) +3
-0+ // 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?
Quoted 9 lines
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_nextuntilnextreturnsNone. That also makes sense. If the cursor becomes circular, then you iterate by callingnextuntil 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?
rust/kernel/list.rs +4 -32
@@ -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
Alice Ryhl
reviewerQuoted 70 lines · Andreas Hindborg
Quoted 8 lines · Alice Ryhl
Quoted 4 lines · Andreas Hindborg
Hi Alice,
This looks like a nice improvement!
Thanks!
Quoted 8 lines
Quoted 3 lines
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_innerout in a separate patch.I think that would make sense.
Quoted 38 lines
Quoted 29 lines
Quoted 29 lines
(quoted diff) +11
-13@@ -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> {Quoted 8 lines
Review pub fn push_all_back(&mut self, other: &mut List<T, ID>) { · line 496
Quoted 3 lines
(quoted diff) +3
-0+ // 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?
Quoted 9 lines
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_nextuntilnextreturnsNone. That also makes sense. If the cursor becomes circular, then you iterate by callingnextuntil the next element is the first element? Seems confusing to me.
Quoted 8 lines
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_nextwill wrap to the front? If the cursor is circular, maybemove_nextandmove_prevshould 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.
Quoted 27 lines
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 stuffif el == last { break;}
}For a non-circular cursor
let mut c =
list.cursor_front();
loop {
let el =c.peek_next();
ifel.is_none(){
break
}
// Do stuff
c.move_next();
}
Quoted 1 line
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