linux-toradex.git/rust/kernel/rbtree.rs, branch v6.19-rc2

rust: rbtree: add immutable cursor

2025-11-16T20:56:57+00:00

Sometimes we may need to iterate over, or find an element in a read
only (or read mostly) red-black tree, and in that case we don't need a
mutable reference to the tree, which we'll however have to take to be
able to use the current (mutable) cursor implementation.

This patch adds a simple immutable cursor implementation to RBTree,
which enables us to use an immutable tree reference. The existing
(fully featured) cursor implementation is renamed to CursorMut,
while retaining its functionality.

The only existing user of the [mutable] cursor for RBTrees (binder) is
updated to match the changes.

Signed-off-by: Vitaly Wool 
Reviewed-by: Alice Ryhl 
Link: https://patch.msgid.link/20251014123339.2492210-1-vitaly.wool@konsulko.se
[ Applied `rustfmt`. Added intra-doc link. Fixed unclosed example.
  Fixed docs description. Fixed typo and other formatting nits.
    - Miguel ]
Signed-off-by: Miguel Ojeda

rust: rbtree: simplify finding `current` in `remove_current`

2025-07-14T21:53:35+00:00

The previous version used a verbose `match` to get
`current`, which may be slightly confusing at first
glance.

This change makes it shorter and more clearly expresses
the intent: prefer `next` if available, otherwise fall
back to `prev`.

Signed-off-by: Onur Özkan 
Reviewed-by: Alice Ryhl 
Reviewed-by: Alexandre Courbot 
Link: https://lore.kernel.org/r/20250708075850.25789-1-work@onurozkan.dev
Signed-off-by: Miguel Ojeda

rust: rbtree: add RBTree::is_empty

2025-06-29T16:52:41+00:00

In Rust Binder I need to be able to determine whether a red/black tree
is empty. Thus, add a method for that operation to replace

	rbtree.iter().next().is_none()

This is terrible, so add a method for this purpose. We do not add a
RBTree::len method because computing the number of elements requires
iterating the entire tree, but checking whether it is empty can be done
cheaply.

Signed-off-by: Alice Ryhl 
Reviewed-by: Benno Lossin 
Link: https://lore.kernel.org/r/20250616-rbtree-is-empty-v1-1-61f7cfb012e3@google.com
[ Adjusted title. - Miguel ]
Signed-off-by: Miguel Ojeda

rust: retain pointer mut-ness in `container_of!`

2025-05-28T16:54:09+00:00

Avoid casting the input pointer to `*const _`, allowing the output
pointer to be `*mut` if the input is `*mut`. This allows a number of
`*const` to `*mut` conversions to be removed at the cost of slightly
worse ergonomics when the macro is used with a reference rather than a
pointer; the only example of this was in the macro's own doctest.

Reviewed-by: Benno Lossin 
Reviewed-by: Alice Ryhl 
Signed-off-by: Tamir Duberstein 
Reviewed-by: Andreas Hindborg 
Link: https://lore.kernel.org/r/20250409-container-of-mutness-v1-1-64f472b94534@gmail.com
Signed-off-by: Miguel Ojeda

rust: rbtree: fix comments referring to Box instead of KBox

2025-03-23T18:43:02+00:00

Several safety comments in the RBTree implementation still refer to
"Box::from_raw" and "Box::into_raw", but the code actually uses KBox.
These comments were not updated when the implementation transitioned
from using Box to KBox.

Fixes: 8373147ce496 ("rust: treewide: switch to our kernel `Box` type")
Signed-off-by: Charalampos Mitrodimas 
Reviewed-by: Benno Lossin 
Reviewed-by: Alice Ryhl 
Link: https://lore.kernel.org/r/20250315-rbtree-comment-fixes-v1-1-51f72c420ff0@posteo.net
Signed-off-by: Miguel Ojeda

rust: improve lifetimes markup

2025-03-08T22:04:38+00:00

Improve lifetimes markup; e.g. from:

    /// ... 'a ...

to:

    /// ... `'a` ...

This will make lifetimes display as code span with Markdown and make it
more consistent with rest of the docs.

Link: https://github.com/Rust-for-Linux/linux/issues/1138
Signed-off-by: Borys Tyran 
Link: https://lore.kernel.org/r/20250207142437.112435-1-borys.tyran@protonmail.com
[ Reworded and changed Closes tag to Link. - Miguel ]
Signed-off-by: Miguel Ojeda

rust: rbtree: fix overindented list item

2025-02-12T22:26:55+00:00

Starting with Rust 1.86.0 (to be released 2025-04-03), Clippy will have
a new lint, `doc_overindented_list_items` [1], which catches cases of
overindented list items.

The lint has been added by Yutaro Ohno, based on feedback from the kernel
[2] on a patch that fixed a similar case -- commit 0c5928deada1 ("rust:
block: fix formatting in GenDisk doc").

Clippy reports a few cases in the kernel, apart from the one already
fixed in the commit above. One is this one:

    error: doc list item overindented
        --> rust/kernel/rbtree.rs:1152:5
         |
    1152 | ///     null, it is a pointer to the root of the [`RBTree`].
         |     ^^^^ help: try using `  ` (2 spaces)
         |
         = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#doc_overindented_list_items
         = note: `-D clippy::doc-overindented-list-items` implied by `-D warnings`
         = help: to override `-D warnings` add `#[allow(clippy::doc_overindented_list_items)]`

Thus clean it up.

Cc: Yutaro Ohno 
Cc: stable@vger.kernel.org # Needed in 6.12.y and 6.13.y only (Rust is pinned in older LTSs).
Fixes: a335e9591404 ("rust: rbtree: add `RBTree::entry`")
Link: https://github.com/rust-lang/rust-clippy/pull/13711 [1]
Link: https://github.com/rust-lang/rust-clippy/issues/13601 [2]
Reviewed-by: Alice Ryhl 
Reviewed-by: Yutaro Ohno 
Link: https://lore.kernel.org/r/20250206232022.599998-1-ojeda@kernel.org
[ There are a few other cases, so updated message. - Miguel ]
Signed-off-by: Miguel Ojeda

rust: rbtree: remove unwrap in asserts

2025-01-13T22:44:29+00:00

Remove `unwrap` in asserts and replace it with `Option::Some`
matching. By doing it this way, the examples are more
descriptive, so it disambiguates the return type of
the `get(...)` and `next(...)`, because the `unwrap(...)`
can also be called on `Result`.

Signed-off-by: Daniel Sedlak 
Reviewed-by: Alice Ryhl 
Link: https://lore.kernel.org/r/20241123095033.41240-3-daniel@sedlak.dev
[ Reworded title slightly. - Miguel ]
Signed-off-by: Miguel Ojeda

rust: treewide: switch to our kernel `Box` type

2024-10-15T20:56:59+00:00

Now that we got the kernel `Box` type in place, convert all existing
`Box` users to make use of it.

Reviewed-by: Alice Ryhl 
Reviewed-by: Benno Lossin 
Reviewed-by: Gary Guo 
Signed-off-by: Danilo Krummrich 
Link: https://lore.kernel.org/r/20241004154149.93856-13-dakr@kernel.org
Signed-off-by: Miguel Ojeda

rust: rbtree: fix `SAFETY` comments that should be `# Safety` sections

2024-10-07T19:39:05+00:00

The tag `SAFETY` is used for safety comments, i.e. `// SAFETY`, while a
`Safety` section is used for safety preconditions in code documentation,
i.e. `/// # Safety`.

Fix the three instances recently added in `rbtree` that Clippy would
have normally caught in a public item, so that we can enable checking
of private items in one of the following commits.

Fixes: 98c14e40e07a ("rust: rbtree: add cursor")
Reviewed-by: Trevor Gross 
Reviewed-by: Alice Ryhl 
Tested-by: Gary Guo 
Reviewed-by: Gary Guo 
Link: https://lore.kernel.org/r/20240904204347.168520-14-ojeda@kernel.org
Signed-off-by: Miguel Ojeda