[PATCH v6 1/2] rust: list: extract common code for insertion

Alice Ryhl
2025-01-31T20:16:07Z

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>
Reviewed-by: Boqun Feng <boqun.feng@gmail.com>
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.1.362.g079036d154-goog