Make the Rust linked list cursor point between elements
Alice Ryhl
reviewerv2 cover Make the Rust linked list cursor point between elements
Please see the commit message of the last patch for more details and motivation.
---
Changes in v2:
- Extract insert_inner refactor to separate patch.
- Make move_next/move_prev not wrap around.
- Add some examples.
- Link to v1: https://lore.kernel.org/r/[email protected]
---
Alice Ryhl (2):
rust: list: extract common code for insertion
rust: list: make the cursor point between elements
rust/kernel/list.rs | 401 ++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 308 insertions(+), 93 deletions(-)
---
base-commit: ceff0757f5dafb5be5205988171809c877b1d3e3
change-id: 20241016-cursor-between-154bed859e27
Best regards,
Signature · 1 line
Alice Ryhl <[email protected]>
Alice Ryhl
reviewerPATCH v2 1/2 rust: list: extract common code for insertion
To prepare for a new cursor API that has the ability to insert elements into the list, extract the common code needed for this operation into a new insert_inner method.
Both push_back and push_front are updated to use the new function.
--- rust/kernel/list.rs | 70 ++++++++++++++++++++++++----------------------------- 1 file changed, 32 insertions(+), 38 deletions(-)
rust/kernel/list.rs +32 -38
@@ -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,27 @@ 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) }; +// * `self.first` is null or in the list. +// * `self.first` is only null if the list is empty. +let new_elem =unsafe { self.insert_inner (item, self.first) }; -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; +// INVARIANT: `new_elem` is in the list because we just inserted it. + self.first = new_elem; }/// Removes the last item from this list.
Signature · 1 line
2.48.0.rc2.279.g1de40edade-goog
Re: [PATCH v2 1/2] rust: list: extract common code for insertion
Quoted 7 lines · Alice Ryhl
To prepare for a new cursor API that has the ability to insert elements into the list, extract the common code needed for this operation into a new
insert_innermethod.Both
push_backandpush_frontare updated to use the new function.Signed-off-by Alice Ryhl <[email protected]>
Best regards,
Andreas Hindborg
Alice Ryhl
reviewerPATCH v2 2/2 rust: list: make the cursor point between elements
In reply to Alice RyhlI'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_next method 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.
For many of the methods, this will reduce how many we need since they now just need a prev/next method, instead of the current state where you may end up needing all of curr/prev/next. Also, if we decide to add a function for splitting a list into two lists at the cursor, then a cursor that points between elements is exactly what makes the most sense.
Another advantage is that this means you can now have a cursor into an empty list.
--- rust/kernel/list.rs | 331 +++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 276 insertions(+), 55 deletions(-)
rust/kernel/list.rs +276 -55
@@ -483,17 +483,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, } }
@@ -573,69 +577,286 @@ 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. +/// +/// # Examples +/// +/// ``` +/// use kernel::list::{List, ListArc, ListLinks}; +/// +/// #[pin_data] +/// struct ListItem { +/// value: u32, +/// #[pin] +/// links: ListLinks, +/// } +/// +/// 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); +/// } +/// } +/// ``` +/// /// # 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 > { -/// 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) } +/// 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 } } -/// 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 }; +/// 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 one element forward. +/// +/// If the cursor is after the last element, then this call does nothing. This call returns +/// `true` if the cursor's position was changed. +pub fn move_next (&mut self) ->bool { +if self.next.is_null () { +return false ; + } + +// 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 { -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, - }) + next = core::ptr::null_mut (); } + +// INVARIANT: `next` is either null or the next element after an element in the list. + self.next = next; +true } -/// 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 }; +/// Move the cursor one element backwards. +/// +/// If the cursor is before the first element, then this call does nothing. This call returns +/// `true` if the cursor's position was changed. +pub fn move_prev (&mut self) ->bool { +if self.next == self.list.first { +return false ; + } -if self.current == self.list.first { -None +// INVARIANT: `prev_ptr()` always returns a pointer that is null or in the list. + self.next = self.prev_ptr (); +true + } + +/// 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 { -// INVARIANT: Since `self.current` is in the `list`, its `prev` pointer is also in the -// `list`. -Some (Cursor { - current: prev, - list: self.list, - }) - } + 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. +/// 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 > { -// SAFETY: The `current` pointer always points at a member of the list. -unsafe { self.list.remove_internal (self.current) } +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 } } }
Signature · 1 line
2.48.0.rc2.279.g1de40edade-goog
Re: [PATCH v2 2/2] rust: list: make the cursor point between elements
Quoted 21 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_nextmethod 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.For many of the methods, this will reduce how many we need since they now just need a prev/next method, instead of the current state where you may end up needing all of curr/prev/next. Also, if we decide to add a function for splitting a list into two lists at the cursor, then a cursor that points between elements is exactly what makes the most sense.
Quoted 5 lines
Another advantage is that this means you can now have a cursor into an empty list.
If you for some reason find yourself sending a new version, it would be cool if the example actually executed the functions and made some asserts.
Best regards,
Andreas Hindborg
Re: [PATCH v2 2/2] rust: list: make the cursor point between elements
In reply to Alice RyhlOn Tue, Jan 21, 2025 at 10:14:24AM +0000, Alice Ryhl wrote:
[...]
Quoted 43 lines
rust/kernel/list.rs +40
-2+/// 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 > { -// SAFETY: The `current` pointer always points at a member of the list. -unsafe { self.list.remove_internal (self.current) } +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.
rust/kernel/list.rs fn next(&mut self) -> Option<ArcBorrow<'a, T>> { · line 846
Quoted 10 lines
rust/kernel/list.rs +10
-0+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>`.
I'm not sure whether we want to mention ArcBorrow<'a, T> here, because ArcBorrow<'a, T> is a (smart) pointer type, which should never be used as a Deref::Target, otherwise CursorPeek::deref() would return a &ArcBorrow<'a, T>, which doesn't make sense, and a bit challenging to implement I think?
rust/kernel/list.rs fn next(&mut self) -> Option<ArcBorrow<'a, T>> { · line 851
Quoted 5 lines
rust/kernel/list.rs +5
-0+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)) };
Shouldn't this be self.ptr instead of self.cursor.next?
Regards,
Boqun
Quoted 15 lines
rust/kernel/list.rs +8
-0+ +// 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 } } }Signature · 2 lines
-- 2.48.0.rc2.279.g1de40edade-goog
Alice Ryhl
reviewerRe: [PATCH v2 2/2] rust: list: make the cursor point between elements
Quoted 54 lines · Boqun Feng
On Tue, Jan 21, 2025 at 10:14:24AM +0000, Alice Ryhl wrote:
[...]Quoted 51 lines
rust/kernel/list.rs +48
-2+/// 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 > { -// SAFETY: The `current` pointer always points at a member of the list. -unsafe { self.list.remove_internal (self.current) } +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
Quoted 8 lines
rust/kernel/list.rs fn next(&mut self) -> Option<ArcBorrow<'a, T>> { · line 846
Quoted 2 lines
rust/kernel/list.rs +2
-0+// you obtain an `ArcBorrow<'a, T>` and then call `CursorPeek::remove` without giving up the +// `ArcBorrow<'a, T>`. I'm not sure whether we want to mention
ArcBorrow<'a, T>here, becauseArcBorrow<'a, T>is a (smart) pointer type, which should never be used as aDeref::Target, otherwiseCursorPeek::deref()would return a &ArcBorrow<'a, T>, which doesn't make sense, and a bit challenging to implement I think?
A previous implementation of this struct used ArcBorrow as the type of self.ptr, but I had to abandon that because it wasn't helpful. I wrote this comment to document that I couldn't get it to work. I can remove it if you don't think it's useful.
Quoted 7 lines
rust/kernel/list.rs fn next(&mut self) -> Option<ArcBorrow<'a, T>> { · line 851
Quoted 5 lines
rust/kernel/list.rs +5
-0+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)) };Shouldn't this be
self.ptrinstead ofself.cursor.next?
Excellent point, thanks.
Alice