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 <vitaly.wool@konsulko.se>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
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 <ojeda@kernel.org>
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 <aliceryhl@google.com>
Reviewed-by: Benno Lossin <lossin@kernel.org>
Link: https://lore.kernel.org/r/20250616-rbtree-is-empty-v1-1-61f7cfb012e3@google.com
[ Adjusted title. - Miguel ]
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
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 0c5928dead ("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 <yutaro.ono.418@gmail.com>
Cc: stable@vger.kernel.org # Needed in 6.12.y and 6.13.y only (Rust is pinned in older LTSs).
Fixes: a335e95914 ("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 <aliceryhl@google.com>
Reviewed-by: Yutaro Ohno <yutaro.ono.418@gmail.com>
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 <ojeda@kernel.org>
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 <daniel@sedlak.dev>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Link: https://lore.kernel.org/r/20241123095033.41240-3-daniel@sedlak.dev
[ Reworded title slightly. - Miguel ]
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
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: 98c14e40e0 ("rust: rbtree: add cursor")
Reviewed-by: Trevor Gross <tmgross@umich.edu>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Tested-by: Gary Guo <gary@garyguo.net>
Reviewed-by: Gary Guo <gary@garyguo.net>
Link: https://lore.kernel.org/r/20240904204347.168520-14-ojeda@kernel.org
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
