Re: [PATCH] rust: rbtree: add immutable cursor

[Alice Ryhl <aliceryhl@google.com>]

On Thu, Sep 04, 2025 at 04:25:52PM +0200, Vitaly Wool wrote:
> 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.
> 
> Signed-off-by: Vitaly Wool <vitaly.wool@konsulko.se>

Overall looks good to me!

A few comments below:

> -// SAFETY: The [`Cursor`] has exclusive access to both `K` and `V`, so it is sufficient to require them to be `Send`.
> -// The cursor only gives out immutable references to the keys, but since it has excusive access to those same
> -// keys, `Send` is sufficient. `Sync` would be okay, but it is more restrictive to the user.
> -unsafe impl<'a, K: Send, V: Send> Send for Cursor<'a, K, V> {}
> +// SAFETY: The [`CursorMut`] has exclusive access to both `K` and `V`, so it is sufficient to
> +// require them to be `Send`.
> +// The cursor only gives out immutable references to the keys, but since it has excusive access to
> +// those same keys, `Send` is sufficient. `Sync` would be okay, but it is more restrictive to the
> +// user.
> +unsafe impl<'a, K: Send, V: Send> Send for CursorMut<'a, K, V> {}
>  
> -// SAFETY: The [`Cursor`] gives out immutable references to K and mutable references to V,
> +// SAFETY: The [`CursorMut`] gives out immutable references to K and mutable references to V,
>  // so it has the same thread safety requirements as mutable references.
> -unsafe impl<'a, K: Sync, V: Sync> Sync for Cursor<'a, K, V> {}
> +unsafe impl<'a, K: Sync, V: Sync> Sync for CursorMut<'a, K, V> {}

We should also have Send/Sync impls for the new immutable Cursor type.
They need to look like this since the immutable cursor only has shared
access and not exclusive access.

unsafe impl<'a, K: Sync, V: Sync> Send for Cursor<'a, K, V> {}
unsafe impl<'a, K: Sync, V: Sync> Sync for Cursor<'a, K, V> {}

> +    /// # Safety
> +    ///
> +    /// - `node` must be a valid pointer to a node in an [`RBTree`].
> +    /// - The caller has immutable access to `node` for the duration of `'b`.
> +    unsafe fn to_key_value<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b V) {
> +        // SAFETY: the caller guarantees that `node` is a valid pointer in an `RBTree`.
> +        let (k, v) = unsafe { Self::to_key_value_raw(node) };
> +        // SAFETY: the caller guarantees immutable access to `node`.
> +        (k, unsafe { &*v })
> +    }
> +
> +    /// # Safety
> +    ///
> +    /// - `node` must be a valid pointer to a node in an [`RBTree`].
> +    /// - The caller has immutable access to the key for the duration of `'b`.
> +    unsafe fn to_key_value_raw<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, *mut V) {

The mutable cursor has `to_key_value_raw` because it needs both a &V and
`&mut V` version, but the immutable Cursor doesn't have that so it
doesn't need a raw version either.

That said, perhaps we could share this logic between the two cursor
types? We can make these methods standalone instead of being part of the
cursor so that both cursors can use the same helper methods instead of
duplicating them.

Alice