Re: [PATCH v2] rust: rbtree: document peek_next() on the immutable cursor

[Gary Guo]

On Wed Jul 29, 2026 at 3:34 AM BST, Juan Patricio Marchetto wrote:
> The immutable Cursor has a single example, covering cursor_front() and
> current(). Its peek_next() has none: the only worked example of peeking
> belongs to CursorMut.
>
> That leaves the most common reason to hold an immutable cursor
> undocumented. cursor_lower_bound() stops on an exact match, so a caller
> looking for the first key strictly greater than the one it supplied has
> to peek past it. When the key was absent the cursor already holds the
> answer, and peeking there returns its successor instead, skipping an
> element.
>
> Document both branches, and the case where the looked-up key is the
> largest in the tree and has no successor.
>
> Assisted-by: Claude:claude-opus-5
> Signed-off-by: Juan Patricio Marchetto <juanpatriciomarchetto@xxxxxxxxx>
> ---
>
> Notes:
>     v2: v1 documented only the exact-match branch, so the idiom as written
>     skipped an element whenever the looked-up key was absent. The example now
>     covers both branches and uses a four-element tree so the skipped element
>     is visible. Reported by the Sashiko review of v1.
>     
>     Verified with rust_doctests_kernel under ARCH=um: 321/321.
>     
>     v1:
>     https://lore.kernel.org/r/20260729014344.1244809-1-juanpatriciomarchetto@xxxxxxxxx
>
>  rust/kernel/rbtree.rs | 36 ++++++++++++++++++++++++++++++++++++
>  1 file changed, 36 insertions(+)
>
> diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
> index 6fbd579d4a4..ea8df886df8 100644
> --- a/rust/kernel/rbtree.rs
> +++ b/rust/kernel/rbtree.rs
> @@ -811,6 +811,42 @@ pub struct CursorMut<'a, K, V> {
>  ///
>  /// # Ok::<(), Error>(())
>  /// ```
> +///
> +/// [`Cursor::peek_next`] completes a lookup for the first key strictly greater than a
> +/// given one. [`RBTree::cursor_lower_bound`] stops on an exact match, so the peek is
> +/// needed only when the key was present: when it was absent the cursor already holds
> +/// the answer, and peeking there skips an element instead.

I am failing to see why this should be a type documentation.

Best,
Gary

> +///
> +/// ```
> +/// use kernel::{alloc::flags, rbtree::RBTree};
> +///
> +/// // Create a new tree.
> +/// let mut tree = RBTree::new();
> +///
> +/// // Insert four elements.
> +/// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
> +/// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
> +/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
> +/// tree.try_create_and_insert(40, 400, flags::GFP_KERNEL)?;
> +///
> +/// // 20 is present, so the cursor stops on the key the caller already has and the
> +/// // successor is one peek away.
> +/// let cursor = tree.cursor_lower_bound(&20).unwrap();
> +/// assert_eq!(cursor.current(), (&20, &200));
> +/// assert_eq!(cursor.peek_next().unwrap(), (&30, &300));
> +///
> +/// // 25 is absent, so the cursor already sits on the answer. Peeking from here
> +/// // returns 40 and skips 30.
> +/// let cursor = tree.cursor_lower_bound(&25).unwrap();
> +/// assert_eq!(cursor.current(), (&30, &300));
> +/// assert_eq!(cursor.peek_next().unwrap(), (&40, &400));
> +///
> +/// // The largest key has no successor.
> +/// let cursor = tree.cursor_lower_bound(&40).unwrap();
> +/// assert!(cursor.peek_next().is_none());
> +///
> +/// # Ok::<(), Error>(())
> +/// ```
>  pub struct Cursor<'a, K, V> {
>      _tree: PhantomData<&'a RBTree<K, V>>,
>      current: NonNull<bindings::rb_node>,