* [PATCH] rust: rbtree: add immutable cursor
@ 2025-09-04 14:25 Vitaly Wool
2025-09-04 16:32 ` Onur Özkan
` (2 more replies)
0 siblings, 3 replies; 7+ messages in thread
From: Vitaly Wool @ 2025-09-04 14:25 UTC (permalink / raw)
To: rust-for-linux
Cc: linux-kernel, Danilo Krummrich, Alice Ryhl, Alex Gaynor,
Boqun Feng, Gary Guo, Bjorn Roy Baron, Benno Lossin,
Andreas Hindborg, Trevor Gross, Onur Özkan, Vitaly Wool
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>
---
rust/kernel/rbtree.rs | 241 +++++++++++++++++++++++++++++++++++++-----
1 file changed, 217 insertions(+), 24 deletions(-)
diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
index b8fe6be6fcc4..3b96d4a24217 100644
--- a/rust/kernel/rbtree.rs
+++ b/rust/kernel/rbtree.rs
@@ -11,7 +11,7 @@
cmp::{Ord, Ordering},
marker::PhantomData,
mem::MaybeUninit,
- ptr::{addr_of_mut, from_mut, NonNull},
+ ptr::{addr_of, addr_of_mut, from_mut, NonNull},
};
/// A red-black tree with owned nodes.
@@ -243,34 +243,64 @@ pub fn values_mut(&mut self) -> impl Iterator<Item = &'_ mut V> {
}
/// Returns a cursor over the tree nodes, starting with the smallest key.
- pub fn cursor_front(&mut self) -> Option<Cursor<'_, K, V>> {
+ pub fn cursor_front_mut(&mut self) -> Option<CursorMut<'_, K, V>> {
let root = addr_of_mut!(self.root);
// SAFETY: `self.root` is always a valid root node
let current = unsafe { bindings::rb_first(root) };
NonNull::new(current).map(|current| {
// INVARIANT:
// - `current` is a valid node in the [`RBTree`] pointed to by `self`.
- Cursor {
+ CursorMut {
current,
tree: self,
}
})
}
+ /// Returns an unmutable cursor over the tree nodes, starting with the smallest key.
+ pub fn cursor_front(&self) -> Option<Cursor<'_, K, V>> {
+ let root = addr_of!(self.root);
+ // SAFETY: `self.root` is always a valid root node
+ let current = unsafe { bindings::rb_first(root) };
+ NonNull::new(current).map(|current| {
+ // INVARIANT:
+ // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
+ Cursor {
+ current,
+ _tree: PhantomData,
+ }
+ })
+ }
+
/// Returns a cursor over the tree nodes, starting with the largest key.
- pub fn cursor_back(&mut self) -> Option<Cursor<'_, K, V>> {
+ pub fn cursor_back_mut(&mut self) -> Option<CursorMut<'_, K, V>> {
let root = addr_of_mut!(self.root);
// SAFETY: `self.root` is always a valid root node
let current = unsafe { bindings::rb_last(root) };
NonNull::new(current).map(|current| {
// INVARIANT:
// - `current` is a valid node in the [`RBTree`] pointed to by `self`.
- Cursor {
+ CursorMut {
current,
tree: self,
}
})
}
+
+ /// Returns a cursor over the tree nodes, starting with the largest key.
+ pub fn cursor_back(&self) -> Option<Cursor<'_, K, V>> {
+ let root = addr_of!(self.root);
+ // SAFETY: `self.root` is always a valid root node
+ let current = unsafe { bindings::rb_last(root) };
+ NonNull::new(current).map(|current| {
+ // INVARIANT:
+ // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
+ Cursor {
+ current,
+ _tree: PhantomData,
+ }
+ })
+ }
}
impl<K, V> RBTree<K, V>
@@ -421,7 +451,7 @@ pub fn remove(&mut self, key: &K) -> Option<V> {
/// If the given key exists, the cursor starts there.
/// Otherwise it starts with the first larger key in sort order.
/// If there is no larger key, it returns [`None`].
- pub fn cursor_lower_bound(&mut self, key: &K) -> Option<Cursor<'_, K, V>>
+ pub fn cursor_lower_bound_mut(&mut self, key: &K) -> Option<CursorMut<'_, K, V>>
where
K: Ord,
{
@@ -470,12 +500,74 @@ pub fn cursor_lower_bound(&mut self, key: &K) -> Option<Cursor<'_, K, V>>
NonNull::new(links).map(|current| {
// INVARIANT:
// - `current` is a valid node in the [`RBTree`] pointed to by `self`.
- Cursor {
+ CursorMut {
current,
tree: self,
}
})
}
+
+ /// Returns a cursor over the tree nodes based on the given key.
+ ///
+ /// If the given key exists, the cursor starts there.
+ /// Otherwise it starts with the first larger key in sort order.
+ /// If there is no larger key, it returns [`None`].
+ pub fn cursor_lower_bound(&self, key: &K) -> Option<Cursor<'_, K, V>>
+ where
+ K: Ord,
+ {
+ let mut node = self.root.rb_node;
+ let mut best_match: Option<NonNull<Node<K, V>>> = None;
+ while !node.is_null() {
+ // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in
+ // `self` point to the links field of `Node<K, V>` objects.
+ let this = unsafe { container_of!(node, Node<K, V>, links) };
+ // SAFETY: `this` is a non-null node so it is valid by the type invariants.
+ let this_key = unsafe { &(*this).key };
+ // SAFETY: `node` is a non-null node so it is valid by the type invariants.
+ let left_child = unsafe { (*node).rb_left };
+ // SAFETY: `node` is a non-null node so it is valid by the type invariants.
+ let right_child = unsafe { (*node).rb_right };
+ match key.cmp(this_key) {
+ Ordering::Equal => {
+ best_match = NonNull::new(this);
+ break;
+ }
+ Ordering::Greater => {
+ node = right_child;
+ }
+ Ordering::Less => {
+ let is_better_match = match best_match {
+ None => true,
+ Some(best) => {
+ // SAFETY: `best` is a non-null node so it is valid by the type
+ // invariants.
+ let best_key = unsafe { &(*best.as_ptr()).key };
+ best_key > this_key
+ }
+ };
+ if is_better_match {
+ best_match = NonNull::new(this);
+ }
+ node = left_child;
+ }
+ };
+ }
+
+ let best = best_match?;
+
+ // SAFETY: `best` is a non-null node so it is valid by the type invariants.
+ let links = unsafe { addr_of_mut!((*best.as_ptr()).links) };
+
+ NonNull::new(links).map(|current| {
+ // INVARIANT:
+ // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
+ Cursor {
+ current,
+ _tree: PhantomData,
+ }
+ })
+ }
}
impl<K, V> Default for RBTree<K, V> {
@@ -507,7 +599,7 @@ fn drop(&mut self) {
}
}
-/// A bidirectional cursor over the tree nodes, sorted by key.
+/// A bidirectional mutable cursor over the tree nodes, sorted by key.
///
/// # Examples
///
@@ -526,7 +618,7 @@ fn drop(&mut self) {
/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
///
/// // Get a cursor to the first element.
-/// let mut cursor = tree.cursor_front().unwrap();
+/// let mut cursor = tree.cursor_front_mut().unwrap();
/// let mut current = cursor.current();
/// assert_eq!(current, (&10, &100));
///
@@ -564,7 +656,7 @@ fn drop(&mut self) {
/// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
///
-/// let mut cursor = tree.cursor_back().unwrap();
+/// let mut cursor = tree.cursor_back_mut().unwrap();
/// let current = cursor.current();
/// assert_eq!(current, (&30, &300));
///
@@ -577,7 +669,7 @@ fn drop(&mut self) {
/// use kernel::rbtree::RBTree;
///
/// let mut tree: RBTree<u16, u16> = RBTree::new();
-/// assert!(tree.cursor_front().is_none());
+/// assert!(tree.cursor_front_mut().is_none());
///
/// # Ok::<(), Error>(())
/// ```
@@ -628,7 +720,7 @@ fn drop(&mut self) {
/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
///
/// // Retrieve a cursor.
-/// let mut cursor = tree.cursor_front().unwrap();
+/// let mut cursor = tree.cursor_front_mut().unwrap();
///
/// // Get a mutable reference to the current value.
/// let (k, v) = cursor.current_mut();
@@ -655,7 +747,7 @@ fn drop(&mut self) {
/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
///
/// // Remove the first element.
-/// let mut cursor = tree.cursor_front().unwrap();
+/// let mut cursor = tree.cursor_front_mut().unwrap();
/// let mut current = cursor.current();
/// assert_eq!(current, (&10, &100));
/// cursor = cursor.remove_current().0.unwrap();
@@ -665,7 +757,7 @@ fn drop(&mut self) {
/// assert_eq!(current, (&20, &200));
///
/// // Get a cursor to the last element, and remove it.
-/// cursor = tree.cursor_back().unwrap();
+/// cursor = tree.cursor_back_mut().unwrap();
/// current = cursor.current();
/// assert_eq!(current, (&30, &300));
///
@@ -694,7 +786,7 @@ fn drop(&mut self) {
/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
///
/// // Get a cursor to the first element.
-/// let mut cursor = tree.cursor_front().unwrap();
+/// let mut cursor = tree.cursor_front_mut().unwrap();
/// let mut current = cursor.current();
/// assert_eq!(current, (&10, &100));
///
@@ -702,7 +794,7 @@ fn drop(&mut self) {
/// assert!(cursor.remove_prev().is_none());
///
/// // Get a cursor to the last element.
-/// cursor = tree.cursor_back().unwrap();
+/// cursor = tree.cursor_back_mut().unwrap();
/// current = cursor.current();
/// assert_eq!(current, (&30, &300));
///
@@ -726,19 +818,51 @@ fn drop(&mut self) {
///
/// # Invariants
/// - `current` points to a node that is in the same [`RBTree`] as `tree`.
-pub struct Cursor<'a, K, V> {
+pub struct CursorMut<'a, K, V> {
tree: &'a mut RBTree<K, V>,
current: NonNull<bindings::rb_node>,
}
-// 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> {}
+/// A bidirectional unmutable cursor over the tree nodes, sorted by key. This is a simpler
+/// variant of CursorMut that is basically providing read only access.
+///
+/// # Examples
+///
+/// In the following example, we obtain a cursor to the first element in the tree.
+/// The cursor allows us to iterate bidirectionally over key/value pairs in the tree.
+///
+/// ```
+/// use kernel::{alloc::flags, rbtree::RBTree};
+///
+/// // Create a new tree.
+/// let mut tree = RBTree::new();
+///
+/// // Insert three 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)?;
+///
+/// // Get a cursor to the first element.
+/// let cursor = tree.cursor_front().unwrap();
+/// let current = cursor.current();
+/// assert_eq!(current, (&10, &100));
+///
+/// # Ok::<(), Error>(())
+pub struct Cursor<'a, K, V> {
+ _tree: PhantomData<&'a RBTree<K, V>>,
+ current: NonNull<bindings::rb_node>,
+}
+
+// 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> {}
impl<'a, K, V> Cursor<'a, K, V> {
/// The current node
@@ -749,6 +873,75 @@ pub fn current(&self) -> (&K, &V) {
unsafe { Self::to_key_value(self.current) }
}
+ /// # 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) {
+ // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self`
+ // point to the links field of `Node<K, V>` objects.
+ let this = unsafe { container_of!(node.as_ptr(), Node<K, V>, links) };
+ // SAFETY: The passed `node` is the current node or a non-null neighbor,
+ // thus `this` is valid by the type invariants.
+ let k = unsafe { &(*this).key };
+ // SAFETY: The passed `node` is the current node or a non-null neighbor,
+ // thus `this` is valid by the type invariants.
+ let v = unsafe { addr_of_mut!((*this).value) };
+ (k, v)
+ }
+
+ /// Access the previous node without moving the cursor.
+ pub fn peek_prev(&self) -> Option<(&K, &V)> {
+ self.peek(Direction::Prev)
+ }
+
+ /// Access the previous node without moving the cursor.
+ pub fn peek_next(&self) -> Option<(&K, &V)> {
+ self.peek(Direction::Next)
+ }
+
+ fn peek(&self, direction: Direction) -> Option<(&K, &V)> {
+ self.get_neighbor_raw(direction).map(|neighbor| {
+ // SAFETY:
+ // - `neighbor` is a valid tree node.
+ // - By the function signature, we have an immutable reference to `self`.
+ unsafe { Self::to_key_value(neighbor) }
+ })
+ }
+
+ fn get_neighbor_raw(&self, direction: Direction) -> Option<NonNull<bindings::rb_node>> {
+ // SAFETY: `self.current` is valid by the type invariants.
+ let neighbor = unsafe {
+ match direction {
+ Direction::Prev => bindings::rb_prev(self.current.as_ptr()),
+ Direction::Next => bindings::rb_next(self.current.as_ptr()),
+ }
+ };
+
+ NonNull::new(neighbor)
+ }
+}
+
+impl<'a, K, V> CursorMut<'a, K, V> {
+ /// The current node
+ pub fn current(&self) -> (&K, &V) {
+ // SAFETY:
+ // - `self.current` is a valid node by the type invariants.
+ // - We have an immutable reference by the function signature.
+ unsafe { Self::to_key_value(self.current) }
+ }
+
/// The current node, with a mutable value
pub fn current_mut(&mut self) -> (&K, &mut V) {
// SAFETY:
@@ -920,7 +1113,7 @@ unsafe fn to_key_value_raw<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, *mut
}
}
-/// Direction for [`Cursor`] operations.
+/// Direction for [`Cursor`] and [`CursorMut`] operations.
enum Direction {
/// the node immediately before, in sort order
Prev,
--
2.39.2
^ permalink raw reply related [flat|nested] 7+ messages in thread* Re: [PATCH] rust: rbtree: add immutable cursor
2025-09-04 14:25 [PATCH] rust: rbtree: add immutable cursor Vitaly Wool
@ 2025-09-04 16:32 ` Onur Özkan
2025-09-05 14:32 ` Vitaly Wool
2025-09-05 9:00 ` Alice Ryhl
2025-09-05 17:11 ` Boqun Feng
2 siblings, 1 reply; 7+ messages in thread
From: Onur Özkan @ 2025-09-04 16:32 UTC (permalink / raw)
To: Vitaly Wool
Cc: rust-for-linux, linux-kernel, Danilo Krummrich, Alice Ryhl,
Alex Gaynor, Boqun Feng, Gary Guo, Bjorn Roy Baron, Benno Lossin,
Andreas Hindborg, Trevor Gross
On Thu, 4 Sep 2025 16:25:52 +0200
Vitaly Wool <vitaly.wool@konsulko.se> 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>
> ---
> rust/kernel/rbtree.rs | 241
> +++++++++++++++++++++++++++++++++++++----- 1 file changed, 217
> insertions(+), 24 deletions(-)
>
> diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
> index b8fe6be6fcc4..3b96d4a24217 100644
> --- a/rust/kernel/rbtree.rs
> +++ b/rust/kernel/rbtree.rs
> @@ -11,7 +11,7 @@
> cmp::{Ord, Ordering},
> marker::PhantomData,
> mem::MaybeUninit,
> - ptr::{addr_of_mut, from_mut, NonNull},
> + ptr::{addr_of, addr_of_mut, from_mut, NonNull},
> };
>
> /// A red-black tree with owned nodes.
> @@ -243,34 +243,64 @@ pub fn values_mut(&mut self) -> impl
> Iterator<Item = &'_ mut V> { }
>
> /// Returns a cursor over the tree nodes, starting with the
> smallest key.
> - pub fn cursor_front(&mut self) -> Option<Cursor<'_, K, V>> {
> + pub fn cursor_front_mut(&mut self) -> Option<CursorMut<'_, K,
> V>> { let root = addr_of_mut!(self.root);
> // SAFETY: `self.root` is always a valid root node
> let current = unsafe { bindings::rb_first(root) };
> NonNull::new(current).map(|current| {
> // INVARIANT:
> // - `current` is a valid node in the [`RBTree`] pointed
> to by `self`.
> - Cursor {
> + CursorMut {
> current,
> tree: self,
> }
> })
> }
>
> + /// Returns an unmutable cursor over the tree nodes, starting
This should be "Returns an immutable...".
> with the smallest key.
> + pub fn cursor_front(&self) -> Option<Cursor<'_, K, V>> {
> + let root = addr_of!(self.root);
> + // SAFETY: `self.root` is always a valid root node
> + let current = unsafe { bindings::rb_first(root) };
> + NonNull::new(current).map(|current| {
> + // INVARIANT:
> + // - `current` is a valid node in the [`RBTree`] pointed
> to by `self`.
> + Cursor {
> + current,
> + _tree: PhantomData,
> + }
> + })
> + }
> +
> /// Returns a cursor over the tree nodes, starting with the
> largest key.
> - pub fn cursor_back(&mut self) -> Option<Cursor<'_, K, V>> {
> + pub fn cursor_back_mut(&mut self) -> Option<CursorMut<'_, K, V>>
> { let root = addr_of_mut!(self.root);
> // SAFETY: `self.root` is always a valid root node
> let current = unsafe { bindings::rb_last(root) };
> NonNull::new(current).map(|current| {
> // INVARIANT:
> // - `current` is a valid node in the [`RBTree`] pointed
> to by `self`.
> - Cursor {
> + CursorMut {
> current,
> tree: self,
> }
> })
> }
> +
> + /// Returns a cursor over the tree nodes, starting with the
> largest key.
> + pub fn cursor_back(&self) -> Option<Cursor<'_, K, V>> {
> + let root = addr_of!(self.root);
> + // SAFETY: `self.root` is always a valid root node
> + let current = unsafe { bindings::rb_last(root) };
> + NonNull::new(current).map(|current| {
> + // INVARIANT:
> + // - `current` is a valid node in the [`RBTree`] pointed
> to by `self`.
> + Cursor {
> + current,
> + _tree: PhantomData,
> + }
> + })
> + }
> }
>
> impl<K, V> RBTree<K, V>
> @@ -421,7 +451,7 @@ pub fn remove(&mut self, key: &K) -> Option<V> {
> /// If the given key exists, the cursor starts there.
> /// Otherwise it starts with the first larger key in sort order.
> /// If there is no larger key, it returns [`None`].
> - pub fn cursor_lower_bound(&mut self, key: &K) ->
> Option<Cursor<'_, K, V>>
> + pub fn cursor_lower_bound_mut(&mut self, key: &K) ->
> Option<CursorMut<'_, K, V>> where
> K: Ord,
> {
> @@ -470,12 +500,74 @@ pub fn cursor_lower_bound(&mut self, key: &K)
> -> Option<Cursor<'_, K, V>> NonNull::new(links).map(|current| {
> // INVARIANT:
> // - `current` is a valid node in the [`RBTree`] pointed
> to by `self`.
> - Cursor {
> + CursorMut {
> current,
> tree: self,
> }
> })
> }
> +
> + /// Returns a cursor over the tree nodes based on the given key.
> + ///
> + /// If the given key exists, the cursor starts there.
> + /// Otherwise it starts with the first larger key in sort order.
> + /// If there is no larger key, it returns [`None`].
> + pub fn cursor_lower_bound(&self, key: &K) -> Option<Cursor<'_,
> K, V>>
> + where
> + K: Ord,
> + {
> + let mut node = self.root.rb_node;
> + let mut best_match: Option<NonNull<Node<K, V>>> = None;
> + while !node.is_null() {
> + // SAFETY: By the type invariant of `Self`, all non-null
> `rb_node` pointers stored in
> + // `self` point to the links field of `Node<K, V>`
> objects.
> + let this = unsafe { container_of!(node, Node<K, V>,
> links) };
> + // SAFETY: `this` is a non-null node so it is valid by
> the type invariants.
> + let this_key = unsafe { &(*this).key };
> + // SAFETY: `node` is a non-null node so it is valid by
> the type invariants.
> + let left_child = unsafe { (*node).rb_left };
> + // SAFETY: `node` is a non-null node so it is valid by
> the type invariants.
> + let right_child = unsafe { (*node).rb_right };
> + match key.cmp(this_key) {
> + Ordering::Equal => {
> + best_match = NonNull::new(this);
> + break;
> + }
> + Ordering::Greater => {
> + node = right_child;
> + }
> + Ordering::Less => {
> + let is_better_match = match best_match {
> + None => true,
> + Some(best) => {
> + // SAFETY: `best` is a non-null node so
> it is valid by the type
> + // invariants.
> + let best_key = unsafe {
> &(*best.as_ptr()).key };
> + best_key > this_key
> + }
> + };
> + if is_better_match {
> + best_match = NonNull::new(this);
> + }
> + node = left_child;
> + }
> + };
> + }
> +
> + let best = best_match?;
> +
> + // SAFETY: `best` is a non-null node so it is valid by the
> type invariants.
> + let links = unsafe { addr_of_mut!((*best.as_ptr()).links) };
Shouldn't we use `addr_of!` here?
> +
> + NonNull::new(links).map(|current| {
> + // INVARIANT:
> + // - `current` is a valid node in the [`RBTree`] pointed
> to by `self`.
> + Cursor {
> + current,
> + _tree: PhantomData,
> + }
> + })
> + }
> }
>
> impl<K, V> Default for RBTree<K, V> {
> @@ -507,7 +599,7 @@ fn drop(&mut self) {
> }
> }
>
> -/// A bidirectional cursor over the tree nodes, sorted by key.
> +/// A bidirectional mutable cursor over the tree nodes, sorted by
> key. ///
> /// # Examples
> ///
> @@ -526,7 +618,7 @@ fn drop(&mut self) {
> /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
> ///
> /// // Get a cursor to the first element.
> -/// let mut cursor = tree.cursor_front().unwrap();
> +/// let mut cursor = tree.cursor_front_mut().unwrap();
> /// let mut current = cursor.current();
> /// assert_eq!(current, (&10, &100));
> ///
> @@ -564,7 +656,7 @@ fn drop(&mut self) {
> /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
> /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
> ///
> -/// let mut cursor = tree.cursor_back().unwrap();
> +/// let mut cursor = tree.cursor_back_mut().unwrap();
> /// let current = cursor.current();
> /// assert_eq!(current, (&30, &300));
> ///
> @@ -577,7 +669,7 @@ fn drop(&mut self) {
> /// use kernel::rbtree::RBTree;
> ///
> /// let mut tree: RBTree<u16, u16> = RBTree::new();
> -/// assert!(tree.cursor_front().is_none());
> +/// assert!(tree.cursor_front_mut().is_none());
> ///
> /// # Ok::<(), Error>(())
> /// ```
> @@ -628,7 +720,7 @@ fn drop(&mut self) {
> /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
> ///
> /// // Retrieve a cursor.
> -/// let mut cursor = tree.cursor_front().unwrap();
> +/// let mut cursor = tree.cursor_front_mut().unwrap();
> ///
> /// // Get a mutable reference to the current value.
> /// let (k, v) = cursor.current_mut();
> @@ -655,7 +747,7 @@ fn drop(&mut self) {
> /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
> ///
> /// // Remove the first element.
> -/// let mut cursor = tree.cursor_front().unwrap();
> +/// let mut cursor = tree.cursor_front_mut().unwrap();
> /// let mut current = cursor.current();
> /// assert_eq!(current, (&10, &100));
> /// cursor = cursor.remove_current().0.unwrap();
> @@ -665,7 +757,7 @@ fn drop(&mut self) {
> /// assert_eq!(current, (&20, &200));
> ///
> /// // Get a cursor to the last element, and remove it.
> -/// cursor = tree.cursor_back().unwrap();
> +/// cursor = tree.cursor_back_mut().unwrap();
> /// current = cursor.current();
> /// assert_eq!(current, (&30, &300));
> ///
> @@ -694,7 +786,7 @@ fn drop(&mut self) {
> /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
> ///
> /// // Get a cursor to the first element.
> -/// let mut cursor = tree.cursor_front().unwrap();
> +/// let mut cursor = tree.cursor_front_mut().unwrap();
> /// let mut current = cursor.current();
> /// assert_eq!(current, (&10, &100));
> ///
> @@ -702,7 +794,7 @@ fn drop(&mut self) {
> /// assert!(cursor.remove_prev().is_none());
> ///
> /// // Get a cursor to the last element.
> -/// cursor = tree.cursor_back().unwrap();
> +/// cursor = tree.cursor_back_mut().unwrap();
> /// current = cursor.current();
> /// assert_eq!(current, (&30, &300));
> ///
> @@ -726,19 +818,51 @@ fn drop(&mut self) {
> ///
> /// # Invariants
> /// - `current` points to a node that is in the same [`RBTree`] as
> `tree`. -pub struct Cursor<'a, K, V> {
> +pub struct CursorMut<'a, K, V> {
> tree: &'a mut RBTree<K, V>,
> current: NonNull<bindings::rb_node>,
> }
>
> -// 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> {} +/// A bidirectional
> unmutable cursor over the tree nodes, sorted by key. This is a
Same here, should be "A bidirectional immutable...".
--
Regards,
Onur
> simpler +/// variant of CursorMut that is basically providing read
> only access. +/// +/// # Examples +///
> +/// In the following example, we obtain a cursor to the first
> element in the tree. +/// The cursor allows us to iterate
> bidirectionally over key/value pairs in the tree. +///
> +/// ```
> +/// use kernel::{alloc::flags, rbtree::RBTree};
> +///
> +/// // Create a new tree.
> +/// let mut tree = RBTree::new();
> +///
> +/// // Insert three 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)?;
> +///
> +/// // Get a cursor to the first element.
> +/// let cursor = tree.cursor_front().unwrap();
> +/// let current = cursor.current();
> +/// assert_eq!(current, (&10, &100));
> +///
> +/// # Ok::<(), Error>(())
> +pub struct Cursor<'a, K, V> {
> + _tree: PhantomData<&'a RBTree<K, V>>,
> + current: NonNull<bindings::rb_node>,
> +}
> +
> +// 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> {}
> impl<'a, K, V> Cursor<'a, K, V> {
> /// The current node
> @@ -749,6 +873,75 @@ pub fn current(&self) -> (&K, &V) {
> unsafe { Self::to_key_value(self.current) }
> }
>
> + /// # 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) {
> + // SAFETY: By the type invariant of `Self`, all non-null
> `rb_node` pointers stored in `self`
> + // point to the links field of `Node<K, V>` objects.
> + let this = unsafe { container_of!(node.as_ptr(), Node<K, V>,
> links) };
> + // SAFETY: The passed `node` is the current node or a
> non-null neighbor,
> + // thus `this` is valid by the type invariants.
> + let k = unsafe { &(*this).key };
> + // SAFETY: The passed `node` is the current node or a
> non-null neighbor,
> + // thus `this` is valid by the type invariants.
> + let v = unsafe { addr_of_mut!((*this).value) };
> + (k, v)
> + }
> +
> + /// Access the previous node without moving the cursor.
> + pub fn peek_prev(&self) -> Option<(&K, &V)> {
> + self.peek(Direction::Prev)
> + }
> +
> + /// Access the previous node without moving the cursor.
> + pub fn peek_next(&self) -> Option<(&K, &V)> {
> + self.peek(Direction::Next)
> + }
> +
> + fn peek(&self, direction: Direction) -> Option<(&K, &V)> {
> + self.get_neighbor_raw(direction).map(|neighbor| {
> + // SAFETY:
> + // - `neighbor` is a valid tree node.
> + // - By the function signature, we have an immutable
> reference to `self`.
> + unsafe { Self::to_key_value(neighbor) }
> + })
> + }
> +
> + fn get_neighbor_raw(&self, direction: Direction) ->
> Option<NonNull<bindings::rb_node>> {
> + // SAFETY: `self.current` is valid by the type invariants.
> + let neighbor = unsafe {
> + match direction {
> + Direction::Prev =>
> bindings::rb_prev(self.current.as_ptr()),
> + Direction::Next =>
> bindings::rb_next(self.current.as_ptr()),
> + }
> + };
> +
> + NonNull::new(neighbor)
> + }
> +}
> +
> +impl<'a, K, V> CursorMut<'a, K, V> {
> + /// The current node
> + pub fn current(&self) -> (&K, &V) {
> + // SAFETY:
> + // - `self.current` is a valid node by the type invariants.
> + // - We have an immutable reference by the function
> signature.
> + unsafe { Self::to_key_value(self.current) }
> + }
> +
> /// The current node, with a mutable value
> pub fn current_mut(&mut self) -> (&K, &mut V) {
> // SAFETY:
> @@ -920,7 +1113,7 @@ unsafe fn to_key_value_raw<'b>(node:
> NonNull<bindings::rb_node>) -> (&'b K, *mut }
> }
>
> -/// Direction for [`Cursor`] operations.
> +/// Direction for [`Cursor`] and [`CursorMut`] operations.
> enum Direction {
> /// the node immediately before, in sort order
> Prev,
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH] rust: rbtree: add immutable cursor
2025-09-04 16:32 ` Onur Özkan
@ 2025-09-05 14:32 ` Vitaly Wool
0 siblings, 0 replies; 7+ messages in thread
From: Vitaly Wool @ 2025-09-05 14:32 UTC (permalink / raw)
To: Onur Özkan
Cc: rust-for-linux, LKML, Danilo Krummrich, Alice Ryhl, Alex Gaynor,
Boqun Feng, Gary Guo, Bjorn Roy Baron, Benno Lossin,
Andreas Hindborg, Trevor Gross
> On Sep 4, 2025, at 6:32 PM, Onur Özkan <work@onurozkan.dev> wrote:
>
> On Thu, 4 Sep 2025 16:25:52 +0200
> Vitaly Wool <vitaly.wool@konsulko.se> 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>
>> ---
>> rust/kernel/rbtree.rs | 241
>> +++++++++++++++++++++++++++++++++++++----- 1 file changed, 217
>> insertions(+), 24 deletions(-)
>>
>> diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
>> index b8fe6be6fcc4..3b96d4a24217 100644
>> --- a/rust/kernel/rbtree.rs
>> +++ b/rust/kernel/rbtree.rs
>> @@ -11,7 +11,7 @@
>> cmp::{Ord, Ordering},
>> marker::PhantomData,
>> mem::MaybeUninit,
>> - ptr::{addr_of_mut, from_mut, NonNull},
>> + ptr::{addr_of, addr_of_mut, from_mut, NonNull},
>> };
>>
>> /// A red-black tree with owned nodes.
>> @@ -243,34 +243,64 @@ pub fn values_mut(&mut self) -> impl
>> Iterator<Item = &'_ mut V> { }
>>
>> /// Returns a cursor over the tree nodes, starting with the
>> smallest key.
>> - pub fn cursor_front(&mut self) -> Option<Cursor<'_, K, V>> {
>> + pub fn cursor_front_mut(&mut self) -> Option<CursorMut<'_, K,
>> V>> { let root = addr_of_mut!(self.root);
>> // SAFETY: `self.root` is always a valid root node
>> let current = unsafe { bindings::rb_first(root) };
>> NonNull::new(current).map(|current| {
>> // INVARIANT:
>> // - `current` is a valid node in the [`RBTree`] pointed
>> to by `self`.
>> - Cursor {
>> + CursorMut {
>> current,
>> tree: self,
>> }
>> })
>> }
>>
>> + /// Returns an unmutable cursor over the tree nodes, starting
>
> This should be "Returns an immutable...".
Thanks, will fix here and in the other place.
>
>> with the smallest key.
>> + pub fn cursor_front(&self) -> Option<Cursor<'_, K, V>> {
>> + let root = addr_of!(self.root);
>> + // SAFETY: `self.root` is always a valid root node
>> + let current = unsafe { bindings::rb_first(root) };
>> + NonNull::new(current).map(|current| {
>> + // INVARIANT:
>> + // - `current` is a valid node in the [`RBTree`] pointed
>> to by `self`.
>> + Cursor {
>> + current,
>> + _tree: PhantomData,
>> + }
>> + })
>> + }
>> +
>> /// Returns a cursor over the tree nodes, starting with the
>> largest key.
>> - pub fn cursor_back(&mut self) -> Option<Cursor<'_, K, V>> {
>> + pub fn cursor_back_mut(&mut self) -> Option<CursorMut<'_, K, V>>
>> { let root = addr_of_mut!(self.root);
>> // SAFETY: `self.root` is always a valid root node
>> let current = unsafe { bindings::rb_last(root) };
>> NonNull::new(current).map(|current| {
>> // INVARIANT:
>> // - `current` is a valid node in the [`RBTree`] pointed
>> to by `self`.
>> - Cursor {
>> + CursorMut {
>> current,
>> tree: self,
>> }
>> })
>> }
>> +
>> + /// Returns a cursor over the tree nodes, starting with the
>> largest key.
>> + pub fn cursor_back(&self) -> Option<Cursor<'_, K, V>> {
>> + let root = addr_of!(self.root);
>> + // SAFETY: `self.root` is always a valid root node
>> + let current = unsafe { bindings::rb_last(root) };
>> + NonNull::new(current).map(|current| {
>> + // INVARIANT:
>> + // - `current` is a valid node in the [`RBTree`] pointed
>> to by `self`.
>> + Cursor {
>> + current,
>> + _tree: PhantomData,
>> + }
>> + })
>> + }
>> }
>>
>> impl<K, V> RBTree<K, V>
>> @@ -421,7 +451,7 @@ pub fn remove(&mut self, key: &K) -> Option<V> {
>> /// If the given key exists, the cursor starts there.
>> /// Otherwise it starts with the first larger key in sort order.
>> /// If there is no larger key, it returns [`None`].
>> - pub fn cursor_lower_bound(&mut self, key: &K) ->
>> Option<Cursor<'_, K, V>>
>> + pub fn cursor_lower_bound_mut(&mut self, key: &K) ->
>> Option<CursorMut<'_, K, V>> where
>> K: Ord,
>> {
>> @@ -470,12 +500,74 @@ pub fn cursor_lower_bound(&mut self, key: &K)
>> -> Option<Cursor<'_, K, V>> NonNull::new(links).map(|current| {
>> // INVARIANT:
>> // - `current` is a valid node in the [`RBTree`] pointed
>> to by `self`.
>> - Cursor {
>> + CursorMut {
>> current,
>> tree: self,
>> }
>> })
>> }
>> +
>> + /// Returns a cursor over the tree nodes based on the given key.
>> + ///
>> + /// If the given key exists, the cursor starts there.
>> + /// Otherwise it starts with the first larger key in sort order.
>> + /// If there is no larger key, it returns [`None`].
>> + pub fn cursor_lower_bound(&self, key: &K) -> Option<Cursor<'_,
>> K, V>>
>> + where
>> + K: Ord,
>> + {
>> + let mut node = self.root.rb_node;
>> + let mut best_match: Option<NonNull<Node<K, V>>> = None;
>> + while !node.is_null() {
>> + // SAFETY: By the type invariant of `Self`, all non-null
>> `rb_node` pointers stored in
>> + // `self` point to the links field of `Node<K, V>`
>> objects.
>> + let this = unsafe { container_of!(node, Node<K, V>,
>> links) };
>> + // SAFETY: `this` is a non-null node so it is valid by
>> the type invariants.
>> + let this_key = unsafe { &(*this).key };
>> + // SAFETY: `node` is a non-null node so it is valid by
>> the type invariants.
>> + let left_child = unsafe { (*node).rb_left };
>> + // SAFETY: `node` is a non-null node so it is valid by
>> the type invariants.
>> + let right_child = unsafe { (*node).rb_right };
>> + match key.cmp(this_key) {
>> + Ordering::Equal => {
>> + best_match = NonNull::new(this);
>> + break;
>> + }
>> + Ordering::Greater => {
>> + node = right_child;
>> + }
>> + Ordering::Less => {
>> + let is_better_match = match best_match {
>> + None => true,
>> + Some(best) => {
>> + // SAFETY: `best` is a non-null node so
>> it is valid by the type
>> + // invariants.
>> + let best_key = unsafe {
>> &(*best.as_ptr()).key };
>> + best_key > this_key
>> + }
>> + };
>> + if is_better_match {
>> + best_match = NonNull::new(this);
>> + }
>> + node = left_child;
>> + }
>> + };
>> + }
>> +
>> + let best = best_match?;
>> +
>> + // SAFETY: `best` is a non-null node so it is valid by the
>> type invariants.
>> + let links = unsafe { addr_of_mut!((*best.as_ptr()).links) };
>
> Shouldn't we use `addr_of!` here?
NonNull::new() expects a mutable reference, so I would argue that the existing variant is correct.
Best regards,
Vitaly
>
>> +
>> + NonNull::new(links).map(|current| {
>> + // INVARIANT:
>> + // - `current` is a valid node in the [`RBTree`] pointed
>> to by `self`.
>> + Cursor {
>> + current,
>> + _tree: PhantomData,
>> + }
>> + })
>> + }
>> }
>>
>> impl<K, V> Default for RBTree<K, V> {
>> @@ -507,7 +599,7 @@ fn drop(&mut self) {
>> }
>> }
>>
>> -/// A bidirectional cursor over the tree nodes, sorted by key.
>> +/// A bidirectional mutable cursor over the tree nodes, sorted by
>> key. ///
>> /// # Examples
>> ///
>> @@ -526,7 +618,7 @@ fn drop(&mut self) {
>> /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
>> ///
>> /// // Get a cursor to the first element.
>> -/// let mut cursor = tree.cursor_front().unwrap();
>> +/// let mut cursor = tree.cursor_front_mut().unwrap();
>> /// let mut current = cursor.current();
>> /// assert_eq!(current, (&10, &100));
>> ///
>> @@ -564,7 +656,7 @@ fn drop(&mut self) {
>> /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
>> /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
>> ///
>> -/// let mut cursor = tree.cursor_back().unwrap();
>> +/// let mut cursor = tree.cursor_back_mut().unwrap();
>> /// let current = cursor.current();
>> /// assert_eq!(current, (&30, &300));
>> ///
>> @@ -577,7 +669,7 @@ fn drop(&mut self) {
>> /// use kernel::rbtree::RBTree;
>> ///
>> /// let mut tree: RBTree<u16, u16> = RBTree::new();
>> -/// assert!(tree.cursor_front().is_none());
>> +/// assert!(tree.cursor_front_mut().is_none());
>> ///
>> /// # Ok::<(), Error>(())
>> /// ```
>> @@ -628,7 +720,7 @@ fn drop(&mut self) {
>> /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
>> ///
>> /// // Retrieve a cursor.
>> -/// let mut cursor = tree.cursor_front().unwrap();
>> +/// let mut cursor = tree.cursor_front_mut().unwrap();
>> ///
>> /// // Get a mutable reference to the current value.
>> /// let (k, v) = cursor.current_mut();
>> @@ -655,7 +747,7 @@ fn drop(&mut self) {
>> /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
>> ///
>> /// // Remove the first element.
>> -/// let mut cursor = tree.cursor_front().unwrap();
>> +/// let mut cursor = tree.cursor_front_mut().unwrap();
>> /// let mut current = cursor.current();
>> /// assert_eq!(current, (&10, &100));
>> /// cursor = cursor.remove_current().0.unwrap();
>> @@ -665,7 +757,7 @@ fn drop(&mut self) {
>> /// assert_eq!(current, (&20, &200));
>> ///
>> /// // Get a cursor to the last element, and remove it.
>> -/// cursor = tree.cursor_back().unwrap();
>> +/// cursor = tree.cursor_back_mut().unwrap();
>> /// current = cursor.current();
>> /// assert_eq!(current, (&30, &300));
>> ///
>> @@ -694,7 +786,7 @@ fn drop(&mut self) {
>> /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
>> ///
>> /// // Get a cursor to the first element.
>> -/// let mut cursor = tree.cursor_front().unwrap();
>> +/// let mut cursor = tree.cursor_front_mut().unwrap();
>> /// let mut current = cursor.current();
>> /// assert_eq!(current, (&10, &100));
>> ///
>> @@ -702,7 +794,7 @@ fn drop(&mut self) {
>> /// assert!(cursor.remove_prev().is_none());
>> ///
>> /// // Get a cursor to the last element.
>> -/// cursor = tree.cursor_back().unwrap();
>> +/// cursor = tree.cursor_back_mut().unwrap();
>> /// current = cursor.current();
>> /// assert_eq!(current, (&30, &300));
>> ///
>> @@ -726,19 +818,51 @@ fn drop(&mut self) {
>> ///
>> /// # Invariants
>> /// - `current` points to a node that is in the same [`RBTree`] as
>> `tree`. -pub struct Cursor<'a, K, V> {
>> +pub struct CursorMut<'a, K, V> {
>> tree: &'a mut RBTree<K, V>,
>> current: NonNull<bindings::rb_node>,
>> }
>>
>> -// 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> {} +/// A bidirectional
>> unmutable cursor over the tree nodes, sorted by key. This is a
>
> Same here, should be "A bidirectional immutable...".
>
> --
>
> Regards,
> Onur
>
>> simpler +/// variant of CursorMut that is basically providing read
>> only access. +/// +/// # Examples +///
>> +/// In the following example, we obtain a cursor to the first
>> element in the tree. +/// The cursor allows us to iterate
>> bidirectionally over key/value pairs in the tree. +///
>> +/// ```
>> +/// use kernel::{alloc::flags, rbtree::RBTree};
>> +///
>> +/// // Create a new tree.
>> +/// let mut tree = RBTree::new();
>> +///
>> +/// // Insert three 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)?;
>> +///
>> +/// // Get a cursor to the first element.
>> +/// let cursor = tree.cursor_front().unwrap();
>> +/// let current = cursor.current();
>> +/// assert_eq!(current, (&10, &100));
>> +///
>> +/// # Ok::<(), Error>(())
>> +pub struct Cursor<'a, K, V> {
>> + _tree: PhantomData<&'a RBTree<K, V>>,
>> + current: NonNull<bindings::rb_node>,
>> +}
>> +
>> +// 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> {}
>> impl<'a, K, V> Cursor<'a, K, V> {
>> /// The current node
>> @@ -749,6 +873,75 @@ pub fn current(&self) -> (&K, &V) {
>> unsafe { Self::to_key_value(self.current) }
>> }
>>
>> + /// # 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) {
>> + // SAFETY: By the type invariant of `Self`, all non-null
>> `rb_node` pointers stored in `self`
>> + // point to the links field of `Node<K, V>` objects.
>> + let this = unsafe { container_of!(node.as_ptr(), Node<K, V>,
>> links) };
>> + // SAFETY: The passed `node` is the current node or a
>> non-null neighbor,
>> + // thus `this` is valid by the type invariants.
>> + let k = unsafe { &(*this).key };
>> + // SAFETY: The passed `node` is the current node or a
>> non-null neighbor,
>> + // thus `this` is valid by the type invariants.
>> + let v = unsafe { addr_of_mut!((*this).value) };
>> + (k, v)
>> + }
>> +
>> + /// Access the previous node without moving the cursor.
>> + pub fn peek_prev(&self) -> Option<(&K, &V)> {
>> + self.peek(Direction::Prev)
>> + }
>> +
>> + /// Access the previous node without moving the cursor.
>> + pub fn peek_next(&self) -> Option<(&K, &V)> {
>> + self.peek(Direction::Next)
>> + }
>> +
>> + fn peek(&self, direction: Direction) -> Option<(&K, &V)> {
>> + self.get_neighbor_raw(direction).map(|neighbor| {
>> + // SAFETY:
>> + // - `neighbor` is a valid tree node.
>> + // - By the function signature, we have an immutable
>> reference to `self`.
>> + unsafe { Self::to_key_value(neighbor) }
>> + })
>> + }
>> +
>> + fn get_neighbor_raw(&self, direction: Direction) ->
>> Option<NonNull<bindings::rb_node>> {
>> + // SAFETY: `self.current` is valid by the type invariants.
>> + let neighbor = unsafe {
>> + match direction {
>> + Direction::Prev =>
>> bindings::rb_prev(self.current.as_ptr()),
>> + Direction::Next =>
>> bindings::rb_next(self.current.as_ptr()),
>> + }
>> + };
>> +
>> + NonNull::new(neighbor)
>> + }
>> +}
>> +
>> +impl<'a, K, V> CursorMut<'a, K, V> {
>> + /// The current node
>> + pub fn current(&self) -> (&K, &V) {
>> + // SAFETY:
>> + // - `self.current` is a valid node by the type invariants.
>> + // - We have an immutable reference by the function
>> signature.
>> + unsafe { Self::to_key_value(self.current) }
>> + }
>> +
>> /// The current node, with a mutable value
>> pub fn current_mut(&mut self) -> (&K, &mut V) {
>> // SAFETY:
>> @@ -920,7 +1113,7 @@ unsafe fn to_key_value_raw<'b>(node:
>> NonNull<bindings::rb_node>) -> (&'b K, *mut }
>> }
>>
>> -/// Direction for [`Cursor`] operations.
>> +/// Direction for [`Cursor`] and [`CursorMut`] operations.
>> enum Direction {
>> /// the node immediately before, in sort order
>> Prev,
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] rust: rbtree: add immutable cursor
2025-09-04 14:25 [PATCH] rust: rbtree: add immutable cursor Vitaly Wool
2025-09-04 16:32 ` Onur Özkan
@ 2025-09-05 9:00 ` Alice Ryhl
2025-09-05 17:30 ` Vitaly Wool
2025-09-05 17:11 ` Boqun Feng
2 siblings, 1 reply; 7+ messages in thread
From: Alice Ryhl @ 2025-09-05 9:00 UTC (permalink / raw)
To: Vitaly Wool
Cc: rust-for-linux, linux-kernel, Danilo Krummrich, Alex Gaynor,
Boqun Feng, Gary Guo, Bjorn Roy Baron, Benno Lossin,
Andreas Hindborg, Trevor Gross, Onur Özkan
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
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH] rust: rbtree: add immutable cursor
2025-09-05 9:00 ` Alice Ryhl
@ 2025-09-05 17:30 ` Vitaly Wool
2025-09-05 19:43 ` Alice Ryhl
0 siblings, 1 reply; 7+ messages in thread
From: Vitaly Wool @ 2025-09-05 17:30 UTC (permalink / raw)
To: Alice Ryhl
Cc: rust-for-linux, LKML, Danilo Krummrich, Alex Gaynor, Boqun Feng,
Gary Guo, Bjorn Roy Baron, Benno Lossin, Andreas Hindborg,
Trevor Gross, Onur Özkan
> On Sep 5, 2025, at 11:00 AM, Alice Ryhl <aliceryhl@google.com> wrote:
>
> 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.
>
I was thinking about doing some paste macro magic, but maybe it’s better to go the way Boqun is suggesting in another reply and introduce a helper function returning Option<NonNull<..>>. What would you prefer?
Best regards,
Vitaly
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH] rust: rbtree: add immutable cursor
2025-09-05 17:30 ` Vitaly Wool
@ 2025-09-05 19:43 ` Alice Ryhl
0 siblings, 0 replies; 7+ messages in thread
From: Alice Ryhl @ 2025-09-05 19:43 UTC (permalink / raw)
To: Vitaly Wool
Cc: rust-for-linux, LKML, Danilo Krummrich, Alex Gaynor, Boqun Feng,
Gary Guo, Bjorn Roy Baron, Benno Lossin, Andreas Hindborg,
Trevor Gross, Onur Özkan
On Fri, Sep 5, 2025 at 7:30 PM Vitaly Wool <vitaly.wool@konsulko.se> wrote:
>
>
>
> > On Sep 5, 2025, at 11:00 AM, Alice Ryhl <aliceryhl@google.com> wrote:
> >
> > 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.
> >
>
> I was thinking about doing some paste macro magic, but maybe it’s better to go the way Boqun is suggesting in another reply and introduce a helper function returning Option<NonNull<..>>. What would you prefer?
I would prefer a helper function.
Alice
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] rust: rbtree: add immutable cursor
2025-09-04 14:25 [PATCH] rust: rbtree: add immutable cursor Vitaly Wool
2025-09-04 16:32 ` Onur Özkan
2025-09-05 9:00 ` Alice Ryhl
@ 2025-09-05 17:11 ` Boqun Feng
2 siblings, 0 replies; 7+ messages in thread
From: Boqun Feng @ 2025-09-05 17:11 UTC (permalink / raw)
To: Vitaly Wool
Cc: rust-for-linux, linux-kernel, Danilo Krummrich, Alice Ryhl,
Alex Gaynor, Gary Guo, Bjorn Roy Baron, Benno Lossin,
Andreas Hindborg, Trevor Gross, Onur Özkan
On Thu, Sep 04, 2025 at 04:25:52PM +0200, Vitaly Wool wrote:
[...]
> +
> + /// Returns a cursor over the tree nodes based on the given key.
> + ///
> + /// If the given key exists, the cursor starts there.
> + /// Otherwise it starts with the first larger key in sort order.
> + /// If there is no larger key, it returns [`None`].
> + pub fn cursor_lower_bound(&self, key: &K) -> Option<Cursor<'_, K, V>>
I think you can make a helper function that returns a
`Option<NonNull<..>>` and `cursor_lower_bound()` and
`cursor_lower_bound_mut()` could share the searching logic in the helper
function.
> + where
> + K: Ord,
> + {
> + let mut node = self.root.rb_node;
> + let mut best_match: Option<NonNull<Node<K, V>>> = None;
> + while !node.is_null() {
> + // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in
> + // `self` point to the links field of `Node<K, V>` objects.
> + let this = unsafe { container_of!(node, Node<K, V>, links) };
> + // SAFETY: `this` is a non-null node so it is valid by the type invariants.
> + let this_key = unsafe { &(*this).key };
> + // SAFETY: `node` is a non-null node so it is valid by the type invariants.
> + let left_child = unsafe { (*node).rb_left };
> + // SAFETY: `node` is a non-null node so it is valid by the type invariants.
> + let right_child = unsafe { (*node).rb_right };
> + match key.cmp(this_key) {
> + Ordering::Equal => {
> + best_match = NonNull::new(this);
> + break;
> + }
> + Ordering::Greater => {
> + node = right_child;
> + }
> + Ordering::Less => {
> + let is_better_match = match best_match {
> + None => true,
> + Some(best) => {
> + // SAFETY: `best` is a non-null node so it is valid by the type
> + // invariants.
> + let best_key = unsafe { &(*best.as_ptr()).key };
> + best_key > this_key
> + }
> + };
> + if is_better_match {
> + best_match = NonNull::new(this);
> + }
> + node = left_child;
> + }
> + };
> + }
> +
> + let best = best_match?;
> +
> + // SAFETY: `best` is a non-null node so it is valid by the type invariants.
> + let links = unsafe { addr_of_mut!((*best.as_ptr()).links) };
> +
> + NonNull::new(links).map(|current| {
> + // INVARIANT:
> + // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
> + Cursor {
> + current,
> + _tree: PhantomData,
> + }
> + })
> + }
> }
>
[...]
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2025-09-05 19:44 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-09-04 14:25 [PATCH] rust: rbtree: add immutable cursor Vitaly Wool
2025-09-04 16:32 ` Onur Özkan
2025-09-05 14:32 ` Vitaly Wool
2025-09-05 9:00 ` Alice Ryhl
2025-09-05 17:30 ` Vitaly Wool
2025-09-05 19:43 ` Alice Ryhl
2025-09-05 17:11 ` Boqun Feng
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox