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.
Reviewed-by: Andreas Hindborg <a.hindborg@kernel.org>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
rust/kernel/list.rs | 70 ++++++++++++++++++++++++-----------------------------
1 file changed, 32 insertions(+), 38 deletions(-)
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index fb93330f4af4..97b3599b7207 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,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.
--
2.48.0.rc2.279.g1de40edade-googOn Wed, Jan 22, 2025 at 03:00:17PM +0000, Alice Ryhl wrote:
> 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.
>
> Reviewed-by: Andreas Hindborg <a.hindborg@kernel.org>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Boqun Feng <boqun.feng@gmail.com>
Regards,
Boqun
> ---
> rust/kernel/list.rs | 70 ++++++++++++++++++++++++-----------------------------
> 1 file changed, 32 insertions(+), 38 deletions(-)
>
> diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
> index fb93330f4af4..97b3599b7207 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,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.
>
> --
> 2.48.0.rc2.279.g1de40edade-goog
>
© 2016 - 2025 Red Hat, Inc.