This patchset contains the red-black tree abstractions needed by the Rust
implementation of the Binder driver.
Binder driver benefits from O(log n) search/insertion/deletion of
key/value mappings in various places, including `process.rs` and
`range_alloc.rs`. In `range_alloc.rs`, the ability to store and
search by a generic key type is also useful.
Please see the Rust Binder RFC for usage examples [1]. Note that
the `container_of` macro is currently used only by `rbtree` itself.
Users of "rust: rbtree: add red-black tree implementation backed by the C version"
[PATCH RFC 03/20] rust_binder: add threading support
[PATCH RFC 05/20] rust_binder: add nodes and context managers
[PATCH RFC 06/20] rust_binder: add oneway transactions
Users of "rust: rbtree: add `RBTreeIterator`"
[PATCH RFC 17/20] rust_binder: add oneway spam detection
Users of "rust: rbtree: add `RBTreeIteratorMut`"
[PATCH RFC 06/20] rust_binder: add oneway transactions
Users of "rust: rbtree: add `RBTreeCursor`"
[PATCH RFC 06/20] rust_binder: add oneway transactions
Users of "rust: rbtree: add RBTree::entry"
Not used in the original RFC, but introduced after further
code review. See: https://r.android.com/2849906
The Rust Binder RFC addresses the upstream deprecation of red-black
tree. Quoted here for convenience:
"This RFC uses the kernel's red-black tree for key/value mappings, but we
are aware that the red-black tree is deprecated. We did this to make the
performance comparison more fair, since C binder also uses rbtree for
this. We intend to replace these with XArrays instead. That said, we
don't think that XArray is a good fit for the range allocator, and we
propose to continue using the red-black tree for the range allocator."
Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [1]
Signed-off-by: Matt Gilbride <[email protected]>
---
Changes in v3:
- Address various feedback re: SAFETY and INVARIANT comments from v2.
- Update variable naming and add detailed comments for the `RBTree::insert` (later moved to
`RBTree::raw_entry`) implementation.
- Link to v2: https://lore.kernel.org/r/[email protected]
Changes in v2:
- Update documentation link to the C header file
- Use `core::convert::Infallible` in try_reserve_node
- Link to v1: https://lore.kernel.org/r/[email protected]
---
Alice Ryhl (1):
rust: rbtree: add `RBTree::entry`
Matt Gilbride (1):
rust: rbtree: add `RBTreeCursor`
Wedson Almeida Filho (3):
rust: rbtree: add red-black tree implementation backed by the C version
rust: rbtree: add `RBTreeIterator`
rust: rbtree: add `RBTreeIteratorMut`
rust/helpers.c | 7 +
rust/kernel/lib.rs | 1 +
rust/kernel/rbtree.rs | 1275 +++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 1283 insertions(+)
---
base-commit: 768409cff6cc89fe1194da880537a09857b6e4db
change-id: 20231205-b4-rbtree-abb1a016f0a0
Best regards,
--
Matt Gilbride <[email protected]>
From: Wedson Almeida Filho <[email protected]>
The rust rbtree exposes a map-like interface over keys and values,
backed by the kernel red-black tree implementation. Values can be
inserted, deleted, and retrieved from a `RBTree` by key.
This base abstraction is used by binder to store key/value
pairs and perform lookups, for example the patch
"[PATCH RFC 03/20] rust_binder: add threading support"
in the binder RFC [1].
Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [1]
Signed-off-by: Wedson Almeida Filho <[email protected]>
Reviewed-by: Alice Ryhl <[email protected]>
Tested-by: Alice Ryhl <[email protected]>
Signed-off-by: Matt Gilbride <[email protected]>
---
rust/helpers.c | 7 +
rust/kernel/lib.rs | 1 +
rust/kernel/rbtree.rs | 425 ++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 433 insertions(+)
diff --git a/rust/helpers.c b/rust/helpers.c
index 70e59efd92bc..56ec79e823df 100644
--- a/rust/helpers.c
+++ b/rust/helpers.c
@@ -157,6 +157,13 @@ void rust_helper_init_work_with_key(struct work_struct *work, work_func_t func,
}
EXPORT_SYMBOL_GPL(rust_helper_init_work_with_key);
+void rust_helper_rb_link_node(struct rb_node *node, struct rb_node *parent,
+ struct rb_node **rb_link)
+{
+ rb_link_node(node, parent, rb_link);
+}
+EXPORT_SYMBOL_GPL(rust_helper_rb_link_node);
+
/*
* `bindgen` binds the C `size_t` type as the Rust `usize` type, so we can
* use it in contexts where Rust expects a `usize` like slice (array) indices.
diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
index be68d5e567b1..297065a63684 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -41,6 +41,7 @@
pub mod net;
pub mod prelude;
pub mod print;
+pub mod rbtree;
mod static_assert;
#[doc(hidden)]
pub mod std_vendor;
diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
new file mode 100644
index 000000000000..ad406fc32d67
--- /dev/null
+++ b/rust/kernel/rbtree.rs
@@ -0,0 +1,425 @@
+// SPDX-License-Identifier: GPL-2.0
+
+//! Red-black trees.
+//!
+//! C header: [`include/linux/rbtree.h`](srctree/include/linux/rbtree.h)
+//!
+//! Reference: <https://www.kernel.org/doc/html/latest/core-api/rbtree.html>
+
+use crate::{bindings, container_of, error::Result, prelude::*};
+use alloc::boxed::Box;
+use core::{
+ cmp::{Ord, Ordering},
+ convert::Infallible,
+ marker::PhantomData,
+ mem::MaybeUninit,
+ ptr::{addr_of_mut, NonNull},
+};
+
+struct Node<K, V> {
+ links: bindings::rb_node,
+ key: K,
+ value: V,
+}
+
+/// A red-black tree with owned nodes.
+///
+/// It is backed by the kernel C red-black trees.
+///
+/// # Invariants
+///
+/// Non-null parent/children pointers stored in instances of the `rb_node` C struct are always
+/// valid, and pointing to a field of our internal representation of a node.
+///
+/// # Examples
+///
+/// In the example below we do several operations on a tree. We note that insertions may fail if
+/// the system is out of memory.
+///
+/// ```
+/// use kernel::rbtree::RBTree;
+///
+/// // Create a new tree.
+/// let mut tree = RBTree::new();
+///
+/// // Insert three elements.
+/// tree.try_create_and_insert(20, 200)?;
+/// tree.try_create_and_insert(10, 100)?;
+/// tree.try_create_and_insert(30, 300)?;
+///
+/// // Check the nodes we just inserted.
+/// {
+/// assert_eq!(tree.get(&10).unwrap(), &100);
+/// assert_eq!(tree.get(&20).unwrap(), &200);
+/// assert_eq!(tree.get(&30).unwrap(), &300);
+/// }
+///
+/// // Replace one of the elements.
+/// tree.try_create_and_insert(10, 1000)?;
+///
+/// // Check that the tree reflects the replacement.
+/// {
+/// assert_eq!(tree.get(&10).unwrap(), &1000);
+/// assert_eq!(tree.get(&20).unwrap(), &200);
+/// assert_eq!(tree.get(&30).unwrap(), &300);
+/// }
+///
+/// // Change the value of one of the elements.
+/// *tree.get_mut(&30).unwrap() = 3000;
+///
+/// // Check that the tree reflects the update.
+/// {
+/// assert_eq!(tree.get(&10).unwrap(), &1000);
+/// assert_eq!(tree.get(&20).unwrap(), &200);
+/// assert_eq!(tree.get(&30).unwrap(), &3000);
+/// }
+///
+/// // Remove an element.
+/// tree.remove(&10);
+///
+/// // Check that the tree reflects the removal.
+/// {
+/// assert_eq!(tree.get(&10), None);
+/// assert_eq!(tree.get(&20).unwrap(), &200);
+/// assert_eq!(tree.get(&30).unwrap(), &3000);
+/// }
+///
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// In the example below, we first allocate a node, acquire a spinlock, then insert the node into
+/// the tree. This is useful when the insertion context does not allow sleeping, for example, when
+/// holding a spinlock.
+///
+/// ```
+/// use kernel::{rbtree::RBTree, sync::SpinLock};
+///
+/// fn insert_test(tree: &SpinLock<RBTree<u32, u32>>) -> Result {
+/// // Pre-allocate node. This may fail (as it allocates memory).
+/// let node = RBTree::try_allocate_node(10, 100)?;
+///
+/// // Insert node while holding the lock. It is guaranteed to succeed with no allocation
+/// // attempts.
+/// let mut guard = tree.lock();
+/// guard.insert(node);
+/// Ok(())
+/// }
+/// ```
+///
+/// In the example below, we reuse an existing node allocation from an element we removed.
+///
+/// ```
+/// use kernel::rbtree::RBTree;
+///
+/// // Create a new tree.
+/// let mut tree = RBTree::new();
+///
+/// // Insert three elements.
+/// tree.try_create_and_insert(20, 200)?;
+/// tree.try_create_and_insert(10, 100)?;
+/// tree.try_create_and_insert(30, 300)?;
+///
+/// // Check the nodes we just inserted.
+/// {
+/// assert_eq!(tree.get(&10).unwrap(), &100);
+/// assert_eq!(tree.get(&20).unwrap(), &200);
+/// assert_eq!(tree.get(&30).unwrap(), &300);
+/// }
+///
+/// // Remove a node, getting back ownership of it.
+/// let existing = tree.remove(&30).unwrap();
+///
+/// // Check that the tree reflects the removal.
+/// {
+/// assert_eq!(tree.get(&10).unwrap(), &100);
+/// assert_eq!(tree.get(&20).unwrap(), &200);
+/// assert_eq!(tree.get(&30), None);
+/// }
+///
+/// // Create a preallocated reservation that we can re-use later.
+/// let reservation = RBTree::try_reserve_node()?;
+///
+/// // Insert a new node into the tree, reusing the previous allocation. This is guaranteed to
+/// // succeed (no memory allocations).
+/// tree.insert(reservation.into_node(15, 150));
+///
+/// // Check that the tree reflect the new insertion.
+/// {
+/// assert_eq!(tree.get(&10).unwrap(), &100);
+/// assert_eq!(tree.get(&15).unwrap(), &150);
+/// assert_eq!(tree.get(&20).unwrap(), &200);
+/// }
+///
+/// # Ok::<(), Error>(())
+/// ```
+pub struct RBTree<K, V> {
+ root: bindings::rb_root,
+ _p: PhantomData<Node<K, V>>,
+}
+
+// SAFETY: An [`RBTree`] allows the same kinds of access to its values that a struct allows to its
+// fields, so we use the same Send condition as would be used for a struct with K and V fields.
+unsafe impl<K: Send, V: Send> Send for RBTree<K, V> {}
+
+// SAFETY: An [`RBTree`] allows the same kinds of access to its values that a struct allows to its
+// fields, so we use the same Sync condition as would be used for a struct with K and V fields.
+unsafe impl<K: Sync, V: Sync> Sync for RBTree<K, V> {}
+
+impl<K, V> RBTree<K, V> {
+ /// Creates a new and empty tree.
+ pub fn new() -> Self {
+ Self {
+ // INVARIANT: There are no nodes in the tree, so the invariant holds vacuously.
+ root: bindings::rb_root::default(),
+ _p: PhantomData,
+ }
+ }
+
+ /// Allocates memory for a node to be eventually initialised and inserted into the tree via a
+ /// call to [`RBTree::insert`].
+ pub fn try_reserve_node() -> Result<RBTreeNodeReservation<K, V>> {
+ Ok(RBTreeNodeReservation {
+ node: Box::init::<Infallible>(crate::init::uninit())?,
+ })
+ }
+
+ /// Allocates and initialises a node that can be inserted into the tree via
+ /// [`RBTree::insert`].
+ pub fn try_allocate_node(key: K, value: V) -> Result<RBTreeNode<K, V>> {
+ Ok(Self::try_reserve_node()?.into_node(key, value))
+ }
+}
+
+impl<K, V> RBTree<K, V>
+where
+ K: Ord,
+{
+ /// Tries to insert a new value into the tree.
+ ///
+ /// It overwrites a node if one already exists with the same key and returns it (containing the
+ /// key/value pair). Returns [`None`] if a node with the same key didn't already exist.
+ ///
+ /// Returns an error if it cannot allocate memory for the new node.
+ pub fn try_create_and_insert(&mut self, key: K, value: V) -> Result<Option<RBTreeNode<K, V>>> {
+ Ok(self.insert(Self::try_allocate_node(key, value)?))
+ }
+
+ /// Inserts a new node into the tree.
+ ///
+ /// It overwrites a node if one already exists with the same key and returns it (containing the
+ /// key/value pair). Returns [`None`] if a node with the same key didn't already exist.
+ ///
+ /// This function always succeeds.
+ pub fn insert(&mut self, RBTreeNode { node }: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> {
+ let node = Box::into_raw(node);
+ // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when
+ // the node is removed or replaced.
+ let node_links = unsafe { addr_of_mut!((*node).links) };
+
+ // The parameters of `rb_link_node` are as follows:
+ // - `node`: A pointer to an uninitialized node being inserted.
+ // - `parent`: A pointer to an existing node in the tree. One of its child pointers must be
+ // null, and `node` will become a child of `parent` by replacing that child pointer
+ // with a pointer to `node`.
+ // - `rb_link`: A pointer to either the left-child or right-child field of `parent`. This
+ // specifies which child of `parent` should hold `node` after this call. The
+ // value of `*rb_link` must be null before the call to `rb_link_node`. If the
+ // red/black tree is empty, then it’s also possible for `parent` to be null. In
+ // this case, `rb_link` is a pointer to the `root` field of the red/black tree.
+ //
+ // We will traverse the tree looking for a node that has a null pointer as its child,
+ // representing an empty subtree where we can insert our new node. We need to make sure
+ // that we preserve the ordering of the nodes in the tree. In each iteration of the loop
+ // we store `parent` and `child_field_of_parent`, and the new `node` will go somewhere
+ // in the subtree of `parent` that `child_field_of_parent` points at. Once
+ // we find an empty subtree, we can insert the new node using `rb_link_node`.
+ let mut parent = core::ptr::null_mut();
+ let mut child_field_of_parent: &mut *mut bindings::rb_node = &mut self.root.rb_node;
+ while !child_field_of_parent.is_null() {
+ parent = *child_field_of_parent;
+
+ // We need to determine whether `node` should be the left or right child of `parent`,
+ // so we will compare with the `key` field of `parent` a.k.a. `this` below.
+ //
+ // 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!(parent, Node<K, V>, links) };
+
+ // SAFETY: `this` is a non-null node so it is valid by the type invariants. `node` is
+ // valid until the node is removed.
+ match unsafe { (*node).key.cmp(&(*this).key) } {
+ // We would like `node` to be the left child of `parent`. Move to this child to check
+ // whether we can use it, or continue searching, at the next iteration.
+ //
+ // SAFETY: `parent` is a non-null node so it is valid by the type invariants.
+ Ordering::Less => child_field_of_parent = unsafe { &mut (*parent).rb_left },
+ // We would like `node` to be the right child of `parent`. Move to this child to check
+ // whether we can use it, or continue searching, at the next iteration.
+ //
+ // SAFETY: `parent` is a non-null node so it is valid by the type invariants.
+ Ordering::Greater => child_field_of_parent = unsafe { &mut (*parent).rb_right },
+ Ordering::Equal => {
+ // There is an existing node in the tree with this key, and that node is
+ // parent. Thus, we are replacing parent with a new node.
+ //
+ // INVARIANT: We are replacing an existing node with a new one, which is valid.
+ // It remains valid because we "forgot" it with `Box::into_raw`.
+ // SAFETY: All pointers are non-null and valid.
+ unsafe { bindings::rb_replace_node(parent, node_links, &mut self.root) };
+
+ // INVARIANT: The node is being returned and the caller may free it, however,
+ // it was removed from the tree. So the invariants still hold.
+ return Some(RBTreeNode {
+ // SAFETY: `this` was a node in the tree, so it is valid.
+ node: unsafe { Box::from_raw(this.cast_mut()) },
+ });
+ }
+ }
+ }
+
+ // INVARIANT: We are linking in a new node, which is valid. It remains valid because we
+ // "forgot" it with `Box::into_raw`.
+ // SAFETY: All pointers are non-null and valid (`*next_child` is null, but `next_child` is a
+ // mutable reference).
+ unsafe { bindings::rb_link_node(node_links, parent, child_field_of_parent) };
+
+ // SAFETY: All pointers are valid. `node` has just been inserted into the tree.
+ unsafe { bindings::rb_insert_color(node_links, &mut self.root) };
+ None
+ }
+
+ /// Returns a node with the given key, if one exists.
+ fn find(&self, key: &K) -> Option<NonNull<Node<K, V>>> {
+ let mut node = self.root.rb_node;
+ 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.
+ node = match key.cmp(unsafe { &(*this).key }) {
+ // SAFETY: `node` is a non-null node so it is valid by the type invariants.
+ Ordering::Less => unsafe { (*node).rb_left },
+ // SAFETY: `node` is a non-null node so it is valid by the type invariants.
+ Ordering::Greater => unsafe { (*node).rb_right },
+ Ordering::Equal => return NonNull::new(this.cast_mut()),
+ }
+ }
+ None
+ }
+
+ /// Returns a reference to the value corresponding to the key.
+ pub fn get(&self, key: &K) -> Option<&V> {
+ // SAFETY: The `find` return value is a node in the tree, so it is valid.
+ self.find(key).map(|node| unsafe { &node.as_ref().value })
+ }
+
+ /// Returns a mutable reference to the value corresponding to the key.
+ pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
+ // SAFETY: The `find` return value is a node in the tree, so it is valid.
+ self.find(key)
+ .map(|mut node| unsafe { &mut node.as_mut().value })
+ }
+
+ /// Removes the node with the given key from the tree.
+ ///
+ /// It returns the node that was removed if one exists, or [`None`] otherwise.
+ fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> {
+ let mut node = self.find(key)?;
+
+ // SAFETY: The `find` return value is a node in the tree, so it is valid.
+ unsafe { bindings::rb_erase(&mut node.as_mut().links, &mut self.root) };
+
+ // INVARIANT: The node is being returned and the caller may free it, however, it was
+ // removed from the tree. So the invariants still hold.
+ Some(RBTreeNode {
+ // SAFETY: The `find` return value was a node in the tree, so it is valid.
+ node: unsafe { Box::from_raw(node.as_ptr()) },
+ })
+ }
+
+ /// Removes the node with the given key from the tree.
+ ///
+ /// It returns the value that was removed if one exists, or [`None`] otherwise.
+ pub fn remove(&mut self, key: &K) -> Option<V> {
+ self.remove_node(key).map(|node| node.node.value)
+ }
+}
+
+impl<K, V> Default for RBTree<K, V> {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl<K, V> Drop for RBTree<K, V> {
+ fn drop(&mut self) {
+ // SAFETY: `root` is valid as it's embedded in `self` and we have a valid `self`.
+ let mut next = unsafe { bindings::rb_first_postorder(&self.root) };
+
+ // INVARIANT: The loop invariant is that all tree nodes from `next` in postorder are valid.
+ while !next.is_null() {
+ // SAFETY: All links fields we create are in a `Node<K, V>`.
+ let this = unsafe { container_of!(next, Node<K, V>, links) };
+
+ // Find out what the next node is before disposing of the current one.
+ // SAFETY: `next` and all nodes in postorder are still valid.
+ next = unsafe { bindings::rb_next_postorder(next) };
+
+ // INVARIANT: This is the destructor, so we break the type invariant during clean-up,
+ // but it is not observable. The loop invariant is still maintained.
+ // SAFETY: `this` is valid per the loop invariant.
+ unsafe { drop(Box::from_raw(this.cast_mut())) };
+ }
+ }
+}
+
+/// A memory reservation for a red-black tree node.
+///
+/// It contains the memory needed to hold a node that can be inserted into a red-black tree. One
+/// can be obtained by directly allocating it ([`RBTree::try_reserve_node`]).
+pub struct RBTreeNodeReservation<K, V> {
+ node: Box<MaybeUninit<Node<K, V>>>,
+}
+
+// SAFETY: This doesn't actually contain K or V, and is just a memory allocation. Those can always
+// be moved across threads.
+unsafe impl<K, V> Send for RBTreeNodeReservation<K, V> {}
+
+// SAFETY: This doesn't actually contain K or V, and is just a memory allocation.
+unsafe impl<K, V> Sync for RBTreeNodeReservation<K, V> {}
+
+impl<K, V> RBTreeNodeReservation<K, V> {
+ /// Initialises a node reservation.
+ ///
+ /// It then becomes an [`RBTreeNode`] that can be inserted into a tree.
+ pub fn into_node(mut self, key: K, value: V) -> RBTreeNode<K, V> {
+ let node_ptr = self.node.as_mut_ptr();
+ // SAFETY: `node_ptr` is valid, and so are its fields.
+ unsafe { addr_of_mut!((*node_ptr).links).write(bindings::rb_node::default()) };
+ // SAFETY: `node_ptr` is valid, and so are its fields.
+ unsafe { addr_of_mut!((*node_ptr).key).write(key) };
+ // SAFETY: `node_ptr` is valid, and so are its fields.
+ unsafe { addr_of_mut!((*node_ptr).value).write(value) };
+ RBTreeNode {
+ // SAFETY: The pointer came from a `MaybeUninit<Node>` whose fields have all been
+ // initialised. Additionally, it has the same layout as `Node`.
+ node: unsafe { Box::<MaybeUninit<_>>::assume_init(self.node) },
+ }
+ }
+}
+
+/// A red-black tree node.
+///
+/// The node is fully initialised (with key and value) and can be inserted into a tree without any
+/// extra allocations or failure paths.
+pub struct RBTreeNode<K, V> {
+ node: Box<Node<K, V>>,
+}
+
+// SAFETY: If K and V can be sent across threads, then it's also okay to send [`RBTreeNode`] across
+// threads.
+unsafe impl<K: Send, V: Send> Send for RBTreeNode<K, V> {}
+
+// SAFETY: If K and V can be accessed without synchronization, then it's also okay to access
+// [`RBTreeNode`] without synchronization.
+unsafe impl<K: Sync, V: Sync> Sync for RBTreeNode<K, V> {}
--
2.44.0.769.g3c40516874-goog
From: Alice Ryhl <[email protected]>
This mirrors the entry API [1] from the Rust standard library on
`RBTree`. This API can be used to access the entry at a specific key and
make modifications depending on whether the key is vacant or occupied.
This API is useful because it can often be used to avoid traversing the
tree multiple times.
This is used by binder to look up and conditionally access or insert a
value, depending on whether it is there or not [2].
Link: https://doc.rust-lang.org/stable/std/collections/btree_map/enum.Entry.html [1]
Link: https://android-review.googlesource.com/c/kernel/common/+/2849906 [2]
Signed-off-by: Alice Ryhl <[email protected]>
Tested-by: Alice Ryhl <[email protected]>
Signed-off-by: Matt Gilbride <[email protected]>
---
rust/kernel/rbtree.rs | 304 +++++++++++++++++++++++++++++++++++++-------------
1 file changed, 229 insertions(+), 75 deletions(-)
diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
index 606ff2f8c8de..c9bdbc5fd509 100644
--- a/rust/kernel/rbtree.rs
+++ b/rust/kernel/rbtree.rs
@@ -309,12 +309,18 @@ pub fn try_create_and_insert(&mut self, key: K, value: V) -> Result<Option<RBTre
/// key/value pair). Returns [`None`] if a node with the same key didn't already exist.
///
/// This function always succeeds.
- pub fn insert(&mut self, RBTreeNode { node }: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> {
- let node = Box::into_raw(node);
- // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when
- // the node is removed or replaced.
- let node_links = unsafe { addr_of_mut!((*node).links) };
+ pub fn insert(&mut self, node: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> {
+ match self.raw_entry(&node.node.key) {
+ RawEntry::Occupied(entry) => Some(entry.replace(node)),
+ RawEntry::Vacant(entry) => {
+ entry.insert(node);
+ None
+ }
+ }
+ }
+ fn raw_entry(&mut self, key: &K) -> RawEntry<'_, K, V> {
+ // The returned `RawEntry` is used to call either `rb_link_node` or `rb_replace_node`.
// The parameters of `rb_link_node` are as follows:
// - `node`: A pointer to an uninitialized node being inserted.
// - `parent`: A pointer to an existing node in the tree. One of its child pointers must be
@@ -332,63 +338,54 @@ pub fn insert(&mut self, RBTreeNode { node }: RBTreeNode<K, V>) -> Option<RBTree
// we store `parent` and `child_field_of_parent`, and the new `node` will go somewhere
// in the subtree of `parent` that `child_field_of_parent` points at. Once
// we find an empty subtree, we can insert the new node using `rb_link_node`.
- let mut parent = core::ptr::null_mut();
let mut child_field_of_parent: &mut *mut bindings::rb_node = &mut self.root.rb_node;
- while !child_field_of_parent.is_null() {
- parent = *child_field_of_parent;
+ let mut parent = core::ptr::null_mut();
+ while !(*child_field_of_parent).is_null() {
+ let curr = *child_field_of_parent;
+ // SAFETY: All links fields we create are in a `Node<K, V>`.
+ let node = unsafe { container_of!(curr, Node<K, V>, links) };
- // We need to determine whether `node` should be the left or right child of `parent`,
- // so we will compare with the `key` field of `parent` a.k.a. `this` below.
- //
- // 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!(parent, Node<K, V>, links) };
-
- // SAFETY: `this` is a non-null node so it is valid by the type invariants. `node` is
- // valid until the node is removed.
- match unsafe { (*node).key.cmp(&(*this).key) } {
- // We would like `node` to be the left child of `parent`. Move to this child to check
- // whether we can use it, or continue searching, at the next iteration.
- //
- // SAFETY: `parent` is a non-null node so it is valid by the type invariants.
- Ordering::Less => child_field_of_parent = unsafe { &mut (*parent).rb_left },
- // We would like `node` to be the right child of `parent`. Move to this child to check
- // whether we can use it, or continue searching, at the next iteration.
- //
- // SAFETY: `parent` is a non-null node so it is valid by the type invariants.
- Ordering::Greater => child_field_of_parent = unsafe { &mut (*parent).rb_right },
+ // SAFETY: `node` is a non-null node so it is valid by the type invariants.
+ match key.cmp(unsafe { &(*node).key }) {
+ // SAFETY: `curr` is a non-null node so it is valid by the type invariants.
+ Ordering::Less => child_field_of_parent = unsafe { &mut (*curr).rb_left },
+ // SAFETY: `curr` is a non-null node so it is valid by the type invariants.
+ Ordering::Greater => child_field_of_parent = unsafe { &mut (*curr).rb_right },
Ordering::Equal => {
- // There is an existing node in the tree with this key, and that node is
- // parent. Thus, we are replacing parent with a new node.
- //
- // INVARIANT: We are replacing an existing node with a new one, which is valid.
- // It remains valid because we "forgot" it with `Box::into_raw`.
- // SAFETY: All pointers are non-null and valid.
- unsafe { bindings::rb_replace_node(parent, node_links, &mut self.root) };
-
- // INVARIANT: The node is being returned and the caller may free it, however,
- // it was removed from the tree. So the invariants still hold.
- return Some(RBTreeNode {
- // SAFETY: `this` was a node in the tree, so it is valid.
- node: unsafe { Box::from_raw(this.cast_mut()) },
- });
+ return RawEntry::Occupied(OccupiedEntry {
+ rbtree: self,
+ node_links: curr,
+ })
}
}
+ parent = curr;
}
- // INVARIANT: We are linking in a new node, which is valid. It remains valid because we
- // "forgot" it with `Box::into_raw`.
- // SAFETY: All pointers are non-null and valid (`*next_child` is null, but `next_child` is a
- // mutable reference).
- unsafe { bindings::rb_link_node(node_links, parent, child_field_of_parent) };
+ RawEntry::Vacant(RawVacantEntry {
+ parent,
+ child_field_of_parent,
+ rbtree: self,
+ })
+ }
- // SAFETY: All pointers are valid. `node` has just been inserted into the tree.
- unsafe { bindings::rb_insert_color(node_links, &mut self.root) };
- None
+ /// Gets the given key's corresponding entry in the map for in-place manipulation.
+ pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
+ match self.raw_entry(&key) {
+ RawEntry::Occupied(entry) => Entry::Occupied(entry),
+ RawEntry::Vacant(entry) => Entry::Vacant(VacantEntry { raw: entry, key }),
+ }
}
- /// Returns a node with the given key, if one exists.
- fn find(&self, key: &K) -> Option<NonNull<Node<K, V>>> {
+ /// Used for accessing the given node, if it exists.
+ pub fn find_mut(&mut self, key: &K) -> Option<OccupiedEntry<'_, K, V>> {
+ match self.raw_entry(key) {
+ RawEntry::Occupied(entry) => Some(entry),
+ RawEntry::Vacant(_entry) => None,
+ }
+ }
+
+ /// Returns a reference to the value corresponding to the key.
+ pub fn get(&self, key: &K) -> Option<&V> {
let mut node = self.root.rb_node;
while !node.is_null() {
// SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self`
@@ -400,47 +397,30 @@ fn find(&self, key: &K) -> Option<NonNull<Node<K, V>>> {
Ordering::Less => unsafe { (*node).rb_left },
// SAFETY: `node` is a non-null node so it is valid by the type invariants.
Ordering::Greater => unsafe { (*node).rb_right },
- Ordering::Equal => return NonNull::new(this.cast_mut()),
+ // SAFETY: `node` is a non-null node so it is valid by the type invariants.
+ Ordering::Equal => return Some(unsafe { &(*this).value }),
}
}
None
}
- /// Returns a reference to the value corresponding to the key.
- pub fn get(&self, key: &K) -> Option<&V> {
- // SAFETY: The `find` return value is a node in the tree, so it is valid.
- self.find(key).map(|node| unsafe { &node.as_ref().value })
- }
-
/// Returns a mutable reference to the value corresponding to the key.
pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
- // SAFETY: The `find` return value is a node in the tree, so it is valid.
- self.find(key)
- .map(|mut node| unsafe { &mut node.as_mut().value })
+ self.find_mut(key).map(|node| node.into_mut())
}
/// Removes the node with the given key from the tree.
///
/// It returns the node that was removed if one exists, or [`None`] otherwise.
- fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> {
- let mut node = self.find(key)?;
-
- // SAFETY: The `find` return value is a node in the tree, so it is valid.
- unsafe { bindings::rb_erase(&mut node.as_mut().links, &mut self.root) };
-
- // INVARIANT: The node is being returned and the caller may free it, however, it was
- // removed from the tree. So the invariants still hold.
- Some(RBTreeNode {
- // SAFETY: The `find` return value was a node in the tree, so it is valid.
- node: unsafe { Box::from_raw(node.as_ptr()) },
- })
+ pub fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> {
+ self.find_mut(key).map(OccupiedEntry::remove_node)
}
/// Removes the node with the given key from the tree.
///
/// It returns the value that was removed if one exists, or [`None`] otherwise.
pub fn remove(&mut self, key: &K) -> Option<V> {
- self.remove_node(key).map(|node| node.node.value)
+ self.find_mut(key).map(OccupiedEntry::remove)
}
/// Returns a cursor over the tree nodes based on the given key.
@@ -1119,3 +1099,177 @@ unsafe impl<K: Send, V: Send> Send for RBTreeNode<K, V> {}
// SAFETY: If K and V can be accessed without synchronization, then it's also okay to access
// [`RBTreeNode`] without synchronization.
unsafe impl<K: Sync, V: Sync> Sync for RBTreeNode<K, V> {}
+
+impl<K, V> RBTreeNode<K, V> {
+ /// Drop the key and value, but keep the allocation.
+ ///
+ /// It then becomes a reservation that can be re-initialised into a different node (i.e., with
+ /// a different key and/or value).
+ ///
+ /// The existing key and value are dropped in-place as part of this operation, that is, memory
+ /// may be freed (but only for the key/value; memory for the node itself is kept for reuse).
+ pub fn into_reservation(self) -> RBTreeNodeReservation<K, V> {
+ let raw = Box::into_raw(self.node);
+ let mut ret = RBTreeNodeReservation {
+ // SAFETY: The pointer came from a valid `Node`, which has the same layout as
+ // `MaybeUninit<Node>`.
+ node: unsafe { Box::from_raw(raw as _) },
+ };
+ // SAFETY: Although the type is `MaybeUninit<Node>`, we know it has been initialised
+ // because it came from a `Node`. So it is safe to drop it.
+ unsafe { core::ptr::drop_in_place::<Node<K, V>>(ret.node.as_mut_ptr()) };
+ ret
+ }
+}
+
+/// A view into a single entry in a map, which may either be vacant or occupied.
+///
+/// This enum is constructed from the [`entry`] method on [`RBTree`].
+///
+/// [`entry`]: fn@RBTree::entry
+pub enum Entry<'a, K, V> {
+ /// This [`RBTree`] does not have a node with this key.
+ Vacant(VacantEntry<'a, K, V>),
+ /// This [`RBTree`] already has a node with this key.
+ Occupied(OccupiedEntry<'a, K, V>),
+}
+
+/// Like [`Entry`], except that it doesn't have ownership of the key.
+enum RawEntry<'a, K, V> {
+ Vacant(RawVacantEntry<'a, K, V>),
+ Occupied(OccupiedEntry<'a, K, V>),
+}
+
+/// A view into a vacant entry in a [`RBTree`]. It is part of the [`Entry`] enum.
+pub struct VacantEntry<'a, K, V> {
+ key: K,
+ raw: RawVacantEntry<'a, K, V>,
+}
+
+/// Like [`VacantEntry`], but doesn't hold on to the key.a
+///
+/// # Invariants
+/// - `parent` may be null if the new node becomes the root.
+/// - `child_field_of_parent` is a valid pointer to the left-child or right-child of `parent`. If `parent` is
+/// null, it is a pointer to the root of the [`RBTree`].
+struct RawVacantEntry<'a, K, V> {
+ rbtree: &'a mut RBTree<K, V>,
+ /// The node that will become the parent of the new node if we insert one.
+ parent: *mut bindings::rb_node,
+ /// This points to the left-child or right-child field of `parent`, or `root` if `parent` is
+ /// null.
+ child_field_of_parent: *mut *mut bindings::rb_node,
+}
+
+impl<'a, K, V> RawVacantEntry<'a, K, V> {
+ /// Inserts the given node into the [`RBTree`] at this entry.
+ ///
+ /// The `node` must have a key such that inserting it here does not break the ordering of this
+ /// [`RBTree`].
+ fn insert(self, node: RBTreeNode<K, V>) -> &'a mut V {
+ let node = Box::into_raw(node.node);
+
+ // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when
+ // the node is removed or replaced.
+ let node_links = unsafe { addr_of_mut!((*node).links) };
+
+ // INVARIANT: We are linking in a new node, which is valid. It remains valid because we
+ // "forgot" it with `Box::into_raw`.
+ // SAFETY: All pointers are null or valid in an appropriate way.
+ unsafe { bindings::rb_link_node(node_links, self.parent, self.child_field_of_parent) };
+
+ // SAFETY: All pointers are valid. `node` has just been inserted into the tree.
+ unsafe { bindings::rb_insert_color(node_links, &mut self.rbtree.root) };
+
+ // SAFETY: The node is valid until we remove it from the tree.
+ unsafe { &mut (*node).value }
+ }
+}
+
+impl<'a, K, V> VacantEntry<'a, K, V> {
+ /// Inserts the given node into the [`RBTree`] at this entry.
+ pub fn insert(self, value: V, reservation: RBTreeNodeReservation<K, V>) -> &'a mut V {
+ self.raw.insert(reservation.into_node(self.key, value))
+ }
+}
+
+/// A view into an occupied entry in a [`RBTree`]. It is part of the [`Entry`] enum.
+///
+/// # Invariants
+/// - `node_links` is a valid, non-null pointer to a tree node.
+pub struct OccupiedEntry<'a, K, V> {
+ rbtree: &'a mut RBTree<K, V>,
+ /// The node that this entry corresponds to.
+ node_links: *mut bindings::rb_node,
+}
+
+impl<'a, K, V> OccupiedEntry<'a, K, V> {
+ fn node_ptr(&self) -> *mut Node<K, V> {
+ // SAFETY: By the type invariant of `Self`, all `node_links` pointers stored in `self`
+ // point to the links field of `Node<K, V>` objects.
+ unsafe { container_of!(self.node_links, Node<K, V>, links) }.cast_mut()
+ }
+
+ /// Gets a reference to the value in the entry.
+ pub fn get(&self) -> &V {
+ // SAFETY: `self.node_ptr` produces a valid pointer to a node in the tree.
+ unsafe { &(*self.node_ptr()).value }
+ }
+
+ /// Gets a mutable reference to the value in the entry.
+ pub fn get_mut(&mut self) -> &mut V {
+ // SAFETY: `self.node_ptr` produces a valid pointer to a node in the tree.
+ unsafe { &mut (*self.node_ptr()).value }
+ }
+
+ /// Converts the entry into a mutable reference to its value.
+ ///
+ /// If you need multiple references to the `OccupiedEntry`, see [`self#get_mut`].
+ pub fn into_mut(self) -> &'a mut V {
+ // SAFETY: `self.node_ptr` produces a valid pointer to a node in the tree.
+ unsafe { &mut (*self.node_ptr()).value }
+ }
+
+ /// Remove this entry from the [`RBTree`].
+ pub fn remove_node(self) -> RBTreeNode<K, V> {
+ // SAFETY: The node is a node in the tree, so it is valid.
+ unsafe { bindings::rb_erase(self.node_links, &mut self.rbtree.root) };
+
+ // INVARIANT: The node is being returned and the caller may free it, however, it was
+ // removed from the tree. So the invariants still hold.
+ RBTreeNode {
+ // SAFETY: The node was a node in the tree, but we removed it, so we can convert it
+ // back into a box.
+ node: unsafe { Box::from_raw(self.node_ptr()) },
+ }
+ }
+
+ /// Takes the value of the entry out of the map, and returns it.
+ pub fn remove(self) -> V {
+ self.remove_node().node.value
+ }
+
+ /// Swap the current node for the provided node.
+ ///
+ /// The key of both nodes must be equal.
+ fn replace(self, node: RBTreeNode<K, V>) -> RBTreeNode<K, V> {
+ let node = Box::into_raw(node.node);
+
+ // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when
+ // the node is removed or replaced.
+ let new_node_links = unsafe { addr_of_mut!((*node).links) };
+
+ // SAFETY: This updates the pointers so that `new_node_links` is in the tree where
+ // `self.node_links` used to be.
+ unsafe {
+ bindings::rb_replace_node(self.node_links, new_node_links, &mut self.rbtree.root)
+ };
+
+ // SAFETY:
+ // - `self.node_ptr` produces a valid pointer to a node in the tree.
+ // - Now that we removed this entry from the tree, we can convert the node to a box.
+ let old_node = unsafe { Box::from_raw(self.node_ptr()) };
+
+ RBTreeNode { node: old_node }
+ }
+}
--
2.44.0.769.g3c40516874-goog
Add a cursor interface to `RBTree`, supporting the following use cases:
- Inspect the current node pointed to by the cursor, inspect/move to
it's neighbors in sort order (bidirectionally).
- Mutate the tree itself by removing the current node pointed to by the
cursor, or one of its neighbors.
Add functions to obtain a cursor to the tree by key:
- The node with the smallest key
- The node with the largest key
- The node matching the given key, or the one with the next larger key
The cursor abstraction is needed by the binder driver to efficiently
search for nodes and (conditionally) modify them, as well as their
neighbors [1].
Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [1]
Co-developed-by: Alice Ryhl <[email protected]>
Signed-off-by: Alice Ryhl <[email protected]>
Reviewed-by: Alice Ryhl <[email protected]>
Tested-by: Alice Ryhl <[email protected]>
Signed-off-by: Matt Gilbride <[email protected]>
---
rust/kernel/rbtree.rs | 539 ++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 539 insertions(+)
diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
index 50d440c9926d..606ff2f8c8de 100644
--- a/rust/kernel/rbtree.rs
+++ b/rust/kernel/rbtree.rs
@@ -245,6 +245,48 @@ pub fn values(&self) -> impl Iterator<Item = &'_ V> {
pub fn values_mut(&mut self) -> impl Iterator<Item = &'_ mut V> {
self.iter_mut().map(|(_, v)| v)
}
+
+ /// Returns a cursor over the tree nodes, starting with the smallest key.
+ pub fn cursor_front(&mut self) -> Option<RBTreeCursor<'_, 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) };
+ if current.is_null() {
+ return None;
+ }
+ // INVARIANT:
+ // - `root` and `current` are valid pointers.
+ // - `root` is the root of an [`RBTree`].
+ // - `current` is a valid node in an [`RBTree`].
+ // - Due to the type signature of this function, the returned [`RBTreeCursor`]
+ // borrows from `self`.
+ Some(RBTreeCursor {
+ _tree: PhantomData,
+ root,
+ current,
+ })
+ }
+
+ /// Returns a cursor over the tree nodes, starting with the largest key.
+ pub fn cursor_back(&mut self) -> Option<RBTreeCursor<'_, 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) };
+ if current.is_null() {
+ return None;
+ }
+ // INVARIANT:
+ // - `root` and `current` are valid pointers.
+ // - `root` is the root of an [`RBTree`].
+ // - `current` is a valid node in an [`RBTree`].
+ // - Due to the type signature of this function, the returned [`RBTreeCursor`]
+ // borrows from `self`.
+ Some(RBTreeCursor {
+ _tree: PhantomData,
+ root,
+ current,
+ })
+ }
}
impl<K, V> RBTree<K, V>
@@ -400,6 +442,72 @@ fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> {
pub fn remove(&mut self, key: &K) -> Option<V> {
self.remove_node(key).map(|node| node.node.value)
}
+
+ /// 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(&mut self, key: &K) -> Option<RBTreeCursor<'_, 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) }.cast_mut();
+ // 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 };
+ if key == this_key {
+ // INVARIANT:
+ // - `self.root` and `node` are valid pointers.
+ // - `self.root` is the root of an [`RBTree`].
+ // - `node` is a valid node in an [`RBTree`].
+ // - Due to the type signature of this function, the returned [`RBTreeCursor`]
+ // borrows from `self`.
+ return Some(RBTreeCursor {
+ _tree: PhantomData,
+ root: addr_of_mut!(self.root),
+ current: node,
+ });
+ } else {
+ node = if key > this_key {
+ right_child
+ } else {
+ 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);
+ }
+ left_child
+ }
+ };
+ }
+ // INVARIANT:
+ // - `self.root` and `best` are valid pointers.
+ // - `self.root` is the root of an [`RBTree`].
+ // - `best` is a valid node in an [`RBTree`].
+ // - Due to the type signature of this function, the returned [`RBTreeCursor`]
+ // borrows from `self`.
+ best_match.map(|best| RBTreeCursor {
+ _tree: PhantomData,
+ root: addr_of_mut!(self.root),
+ // SAFETY: `best` is a non-null node so it is valid by the type invariants.
+ current: unsafe { addr_of_mut!((*best.as_ptr()).links) },
+ })
+ }
}
impl<K, V> Default for RBTree<K, V> {
@@ -430,6 +538,437 @@ fn drop(&mut self) {
}
}
+/// A bidirectional cursor over the tree nodes, sorted by key.
+///
+/// # 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::rbtree::RBTree;
+///
+/// // Create a new tree.
+/// let mut tree = RBTree::new();
+///
+/// // Insert three elements.
+/// tree.try_create_and_insert(10, 100)?;
+/// tree.try_create_and_insert(20, 200)?;
+/// tree.try_create_and_insert(30, 300)?;
+///
+/// // Get a cursor to the first element.
+/// let mut cursor = tree.cursor_front().unwrap();
+/// let mut current = cursor.current();
+/// assert_eq!(current, (&10, &100));
+///
+/// // Move the cursor, updating it to the 2nd element.
+/// cursor = cursor.move_next().unwrap();
+/// current = cursor.current();
+/// assert_eq!(current, (&20, &200));
+///
+/// // Peek at the next element without impacting the cursor.
+/// let next = cursor.peek_next().unwrap();
+/// assert_eq!(next, (&30, &300));
+/// current = cursor.current();
+/// assert_eq!(current, (&20, &200));
+///
+/// // Moving past the last element causes the cursor to return [`None`].
+/// cursor = cursor.move_next().unwrap();
+/// current = cursor.current();
+/// assert_eq!(current, (&30, &300));
+/// let cursor = cursor.move_next();
+/// assert!(cursor.is_none());
+///
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// A cursor can also be obtained at the last element in the tree.
+///
+/// ```
+/// use kernel::rbtree::RBTree;
+///
+/// // Create a new tree.
+/// let mut tree = RBTree::new();
+///
+/// // Insert three elements.
+/// tree.try_create_and_insert(10, 100)?;
+/// tree.try_create_and_insert(20, 200)?;
+/// tree.try_create_and_insert(30, 300)?;
+///
+/// let mut cursor = tree.cursor_back().unwrap();
+/// let current = cursor.current();
+/// assert_eq!(current, (&30, &300));
+///
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// Obtaining a cursor returns [`None`] if the tree is empty.
+///
+/// ```
+/// use kernel::rbtree::RBTree;
+///
+/// let mut tree: RBTree<u16, u16> = RBTree::new();
+/// assert!(tree.cursor_front().is_none());
+///
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// [`RBTree::cursor_lower_bound`] can be used to start at an arbitrary node in the tree.
+///
+/// ```
+/// use kernel::rbtree::RBTree;
+///
+/// // Create a new tree.
+/// let mut tree = RBTree::new();
+///
+/// // Insert five elements.
+/// tree.try_create_and_insert(10, 100)?;
+/// tree.try_create_and_insert(20, 200)?;
+/// tree.try_create_and_insert(30, 300)?;
+/// tree.try_create_and_insert(40, 400)?;
+/// tree.try_create_and_insert(50, 500)?;
+///
+/// // If the provided key exists, a cursor to that key is returned.
+/// let cursor = tree.cursor_lower_bound(&20).unwrap();
+/// let current = cursor.current();
+/// assert_eq!(current, (&20, &200));
+///
+/// // If the provided key doesn't exist, a cursor to the first larger element in sort order is returned.
+/// let cursor = tree.cursor_lower_bound(&25).unwrap();
+/// let current = cursor.current();
+/// assert_eq!(current, (&30, &300));
+///
+/// // If there is no larger key, [`None`] is returned.
+/// let cursor = tree.cursor_lower_bound(&55);
+/// assert!(cursor.is_none());
+///
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// The cursor allows mutation of values in the tree.
+///
+/// ```
+/// use kernel::rbtree::RBTree;
+///
+/// // Create a new tree.
+/// let mut tree = RBTree::new();
+///
+/// // Insert three elements.
+/// tree.try_create_and_insert(10, 100)?;
+/// tree.try_create_and_insert(20, 200)?;
+/// tree.try_create_and_insert(30, 300)?;
+///
+/// // Retrieve a cursor.
+/// let mut cursor = tree.cursor_front().unwrap();
+///
+/// // Get a mutable reference to the current value.
+/// let (k, v) = cursor.current_mut();
+/// *v = 1000;
+///
+/// // The updated value is reflected in the tree.
+/// let updated = tree.get(&10).unwrap();
+/// assert_eq!(updated, &1000);
+///
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// It also allows node removal. The following examples demonstrate the behavior of removing the current node.
+///
+/// ```
+/// use kernel::rbtree::RBTree;
+///
+/// // Create a new tree.
+/// let mut tree = RBTree::new();
+///
+/// // Insert three elements.
+/// tree.try_create_and_insert(10, 100)?;
+/// tree.try_create_and_insert(20, 200)?;
+/// tree.try_create_and_insert(30, 300)?;
+///
+/// // Remove the first element.
+/// let mut cursor = tree.cursor_front().unwrap();
+/// let mut current = cursor.current();
+/// assert_eq!(current, (&10, &100));
+/// cursor = cursor.remove_current().unwrap();
+///
+/// // If a node exists after the current element, it is returned.
+/// current = cursor.current();
+/// assert_eq!(current, (&20, &200));
+///
+/// // Get a cursor to the last element, and remove it.
+/// cursor = tree.cursor_back().unwrap();
+/// current = cursor.current();
+/// assert_eq!(current, (&30, &300));
+///
+/// // Since there is no next node, the previous node is returned.
+/// cursor = cursor.remove_current().unwrap();
+/// current = cursor.current();
+/// assert_eq!(current, (&20, &200));
+///
+/// // Removing the last element in the tree returns [`None`].
+/// assert!(cursor.remove_current().is_none());
+///
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// Nodes adjacent to the current node can also be removed.
+///
+/// ```
+/// use kernel::rbtree::RBTree;
+///
+/// // Create a new tree.
+/// let mut tree = RBTree::new();
+///
+/// // Insert three elements.
+/// tree.try_create_and_insert(10, 100)?;
+/// tree.try_create_and_insert(20, 200)?;
+/// tree.try_create_and_insert(30, 300)?;
+///
+/// // Get a cursor to the first element.
+/// let mut cursor = tree.cursor_front().unwrap();
+/// let mut current = cursor.current();
+/// assert_eq!(current, (&10, &100));
+///
+/// // Calling `remove_prev` from the first element returns [`None`].
+/// assert!(cursor.remove_prev().is_none());
+///
+/// // Get a cursor to the last element.
+/// cursor = tree.cursor_back().unwrap();
+/// current = cursor.current();
+/// assert_eq!(current, (&30, &300));
+///
+/// // Calling `remove_prev` removes and returns the middle element.
+/// assert_eq!(cursor.remove_prev().unwrap(), (20, 200));
+///
+/// // Calling `remove_next` from the last element returns [`None`].
+/// assert!(cursor.remove_next().is_none());
+///
+/// // Move to the first element
+/// cursor = cursor.move_prev().unwrap();
+/// current = cursor.current();
+/// assert_eq!(current, (&10, &100));
+///
+/// // Calling `remove_next` removes and returns the last element.
+/// assert_eq!(cursor.remove_next().unwrap(), (30, 300));
+///
+/// # Ok::<(), Error>(())
+/// ```
+/// # Invariants
+/// - `root` and `current` are valid pointers.
+/// - `root` points to the `root` node of an [`RBTree`].
+/// - `current` points to a node that is in the same [`RBTree`] that `root` is pointing to.
+/// - A cursor must borrow the [`RBTree`] containing `root` and `current` mutably.
+pub struct RBTreeCursor<'a, K, V> {
+ _tree: PhantomData<&'a RBTree<K, V>>,
+ root: *mut bindings::rb_root,
+ current: *mut bindings::rb_node,
+}
+
+// SAFETY: The [`RBTreeCursor`] 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: Send, V: Send> Send for RBTreeCursor<'a, K, V> {}
+
+// SAFETY: The [`RBTreeCursor`] 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 RBTreeCursor<'a, K, V> {}
+
+impl<'a, K, V> RBTreeCursor<'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:
+ // - `self.current` is a valid node by the type invariants.
+ // - We have an mutable reference by the function signature.
+ unsafe { Self::to_key_value_mut(self.current) }
+ }
+
+ /// Remove the current node from the tree.
+ ///
+ /// Returns a cursor to the next node, if it exists,
+ /// else the previous node. Returns [`None`] if the tree
+ /// becomes empty.
+ pub fn remove_current(self) -> Option<Self> {
+ let prev = self.get_neighbor_raw(Direction::Prev);
+ let next = self.get_neighbor_raw(Direction::Next);
+ // 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!(self.current, Node<K, V>, links) }.cast_mut();
+ // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so
+ // the tree cannot change. By the tree invariant, all nodes are valid.
+ unsafe { bindings::rb_erase(&mut (*this).links, self.root) };
+
+ let current = match (prev, next) {
+ (_, Some(next)) => next,
+ (Some(prev), None) => prev,
+ (None, None) => {
+ return None;
+ }
+ };
+
+ // INVARIANT:
+ // - `self.root` and `current` are valid pointers.
+ // - `self.root` is the root of an [`RBTree`].
+ // - `current` is a valid node in an [`RBTree`].
+ // - Due to the function signature, `self` is an owned [`RBTreeCursor`],
+ // and [`RBTreeCursor`]s are only created via functions with a mutable reference
+ // to an [`RBTree`].
+ Some(Self {
+ current,
+ _tree: self._tree,
+ root: self.root,
+ })
+ }
+
+ /// Remove the previous node, returning it if it exists.
+ pub fn remove_prev(&mut self) -> Option<(K, V)> {
+ self.remove_neighbor(Direction::Prev)
+ }
+
+ /// Remove the next node, returning it if it exists.
+ pub fn remove_next(&mut self) -> Option<(K, V)> {
+ self.remove_neighbor(Direction::Next)
+ }
+
+ fn remove_neighbor(&mut self, direction: Direction) -> Option<(K, V)> {
+ if let Some(neighbor) = self.get_neighbor_raw(direction) {
+ // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so
+ // the tree cannot change. By the tree invariant, all nodes are valid.
+ unsafe { bindings::rb_erase(neighbor, self.root) };
+ // 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!(neighbor, Node<K, V>, links) }.cast_mut();
+ // SAFETY: `this` is valid by the type invariants as described above.
+ let n = unsafe { Box::from_raw(this) };
+ return Some((n.key, n.value));
+ }
+ None
+ }
+
+ /// Move the cursor to the previous node, returning [`None`] if it doesn't exist.
+ pub fn move_prev(self) -> Option<Self> {
+ self.mv(Direction::Prev)
+ }
+
+ /// Move the cursor to the next node, returning [`None`] if it doesn't exist.
+ pub fn move_next(self) -> Option<Self> {
+ self.mv(Direction::Next)
+ }
+
+ fn mv(self, direction: Direction) -> Option<Self> {
+ // INVARIANT:
+ // - `self.root` and `neighbor` are valid pointers.
+ // - `self.root` is the root of an [`RBTree`].
+ // - `neighbor` is a valid node in an [`RBTree`].
+ // - Due to the function signature, `self` is an owned [`RBTreeCursor`],
+ // and [`RBTreeCursor`]s are only created via functions with a mutable reference
+ // to an [`RBTree`].
+ self.get_neighbor_raw(direction).map(|neighbor| Self {
+ _tree: self._tree,
+ root: self.root,
+ current: neighbor,
+ })
+ }
+
+ /// 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)
+ // SAFETY:
+ // - `neighbor` is a valid tree node.
+ // - By the function signature, we have an immutable reference to `self`.
+ .map(|neighbor| unsafe { Self::to_key_value(neighbor) })
+ }
+
+ /// Access the previous node mutably without moving the cursor.
+ pub fn peek_prev_mut(&mut self) -> Option<(&K, &mut V)> {
+ self.peek_mut(Direction::Prev)
+ }
+
+ /// Access the next node mutably without moving the cursor.
+ pub fn peek_next_mut(&mut self) -> Option<(&K, &mut V)> {
+ self.peek_mut(Direction::Next)
+ }
+
+ fn peek_mut(&mut self, direction: Direction) -> Option<(&K, &mut V)> {
+ self.get_neighbor_raw(direction)
+ // SAFETY:
+ // - `neighbor` is a valid tree node.
+ // - By the function signature, we have a mutable reference to `self`.
+ .map(|neighbor| unsafe { Self::to_key_value_mut(neighbor) })
+ }
+
+ fn get_neighbor_raw(&self, direction: Direction) -> Option<*mut bindings::rb_node> {
+ // SAFETY: `self.current` is valid by the type invariants.
+ let neighbor = unsafe {
+ match direction {
+ Direction::Prev => bindings::rb_prev(self.current),
+ Direction::Next => bindings::rb_next(self.current),
+ }
+ };
+
+ if neighbor.is_null() {
+ return None;
+ }
+
+ Some(neighbor)
+ }
+
+ /// SAFETY:
+ /// - `node` must be a valid pointer to a node in an [`RBTree`].
+ /// - The caller has immutable access to `node` for the duration of 'a.
+ unsafe fn to_key_value(node: *mut bindings::rb_node) -> (&'a K, &'a 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, 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 { &(*this).value };
+ (k, v)
+ }
+
+ /// SAFETY:
+ /// - `node` must be a valid pointer to a node in an [`RBTree`].
+ /// - The caller has mutable access to `node` for the duration of 'a.
+ unsafe fn to_key_value_mut(node: *mut bindings::rb_node) -> (&'a K, &'a 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, Node<K, V>, links) }.cast_mut();
+ // 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 { &mut (*this).value };
+ (k, v)
+ }
+}
+
+/// Direction for [`RBTreeCursor`] operations.
+enum Direction {
+ /// the node immediately before, in sort order
+ Prev,
+ /// the node immediately after, in sort order
+ Next,
+}
+
impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
type Item = (&'a K, &'a V);
type IntoIter = RBTreeIterator<'a, K, V>;
--
2.44.0.769.g3c40516874-goog
From: Wedson Almeida Filho <[email protected]>
- Add Iterator implementation (`RBTreeIterator`) for `RBTree`, allowing
iteration over (key, value) pairs in key order.
- Add individual `keys()` and `values()` functions to iterate over keys
or values alone.
- Update doctests to use iteration instead of explicitly getting items.
Iteration is needed by the binder driver to enumerate all values in a
tree for oneway spam detection [1].
Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [1]
Signed-off-by: Wedson Almeida Filho <[email protected]>
Reviewed-by: Alice Ryhl <[email protected]>
Tested-by: Alice Ryhl <[email protected]>
Signed-off-by: Matt Gilbride <[email protected]>
---
rust/kernel/rbtree.rs | 129 +++++++++++++++++++++++++++++++++++++++++++-------
1 file changed, 111 insertions(+), 18 deletions(-)
diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
index ad406fc32d67..2f836be7bdbe 100644
--- a/rust/kernel/rbtree.rs
+++ b/rust/kernel/rbtree.rs
@@ -54,14 +54,30 @@ struct Node<K, V> {
/// assert_eq!(tree.get(&30).unwrap(), &300);
/// }
///
+/// // Iterate over the nodes we just inserted.
+/// {
+/// let mut iter = tree.iter();
+/// assert_eq!(iter.next().unwrap(), (&10, &100));
+/// assert_eq!(iter.next().unwrap(), (&20, &200));
+/// assert_eq!(iter.next().unwrap(), (&30, &300));
+/// assert!(iter.next().is_none());
+/// }
+///
+/// // Print all elements.
+/// for (key, value) in &tree {
+/// pr_info!("{} = {}\n", key, value);
+/// }
+///
/// // Replace one of the elements.
/// tree.try_create_and_insert(10, 1000)?;
///
/// // Check that the tree reflects the replacement.
/// {
-/// assert_eq!(tree.get(&10).unwrap(), &1000);
-/// assert_eq!(tree.get(&20).unwrap(), &200);
-/// assert_eq!(tree.get(&30).unwrap(), &300);
+/// let mut iter = tree.iter();
+/// assert_eq!(iter.next().unwrap(), (&10, &1000));
+/// assert_eq!(iter.next().unwrap(), (&20, &200));
+/// assert_eq!(iter.next().unwrap(), (&30, &300));
+/// assert!(iter.next().is_none());
/// }
///
/// // Change the value of one of the elements.
@@ -69,9 +85,11 @@ struct Node<K, V> {
///
/// // Check that the tree reflects the update.
/// {
-/// assert_eq!(tree.get(&10).unwrap(), &1000);
-/// assert_eq!(tree.get(&20).unwrap(), &200);
-/// assert_eq!(tree.get(&30).unwrap(), &3000);
+/// let mut iter = tree.iter();
+/// assert_eq!(iter.next().unwrap(), (&10, &1000));
+/// assert_eq!(iter.next().unwrap(), (&20, &200));
+/// assert_eq!(iter.next().unwrap(), (&30, &3000));
+/// assert!(iter.next().is_none());
/// }
///
/// // Remove an element.
@@ -79,9 +97,10 @@ struct Node<K, V> {
///
/// // Check that the tree reflects the removal.
/// {
-/// assert_eq!(tree.get(&10), None);
-/// assert_eq!(tree.get(&20).unwrap(), &200);
-/// assert_eq!(tree.get(&30).unwrap(), &3000);
+/// let mut iter = tree.iter();
+/// assert_eq!(iter.next().unwrap(), (&20, &200));
+/// assert_eq!(iter.next().unwrap(), (&30, &3000));
+/// assert!(iter.next().is_none());
/// }
///
/// # Ok::<(), Error>(())
@@ -121,9 +140,11 @@ struct Node<K, V> {
///
/// // Check the nodes we just inserted.
/// {
-/// assert_eq!(tree.get(&10).unwrap(), &100);
-/// assert_eq!(tree.get(&20).unwrap(), &200);
-/// assert_eq!(tree.get(&30).unwrap(), &300);
+/// let mut iter = tree.iter();
+/// assert_eq!(iter.next().unwrap(), (&10, &100));
+/// assert_eq!(iter.next().unwrap(), (&20, &200));
+/// assert_eq!(iter.next().unwrap(), (&30, &300));
+/// assert!(iter.next().is_none());
/// }
///
/// // Remove a node, getting back ownership of it.
@@ -131,9 +152,10 @@ struct Node<K, V> {
///
/// // Check that the tree reflects the removal.
/// {
-/// assert_eq!(tree.get(&10).unwrap(), &100);
-/// assert_eq!(tree.get(&20).unwrap(), &200);
-/// assert_eq!(tree.get(&30), None);
+/// let mut iter = tree.iter();
+/// assert_eq!(iter.next().unwrap(), (&10, &100));
+/// assert_eq!(iter.next().unwrap(), (&20, &200));
+/// assert!(iter.next().is_none());
/// }
///
/// // Create a preallocated reservation that we can re-use later.
@@ -145,9 +167,11 @@ struct Node<K, V> {
///
/// // Check that the tree reflect the new insertion.
/// {
-/// assert_eq!(tree.get(&10).unwrap(), &100);
-/// assert_eq!(tree.get(&15).unwrap(), &150);
-/// assert_eq!(tree.get(&20).unwrap(), &200);
+/// let mut iter = tree.iter();
+/// assert_eq!(iter.next().unwrap(), (&10, &100));
+/// assert_eq!(iter.next().unwrap(), (&15, &150));
+/// assert_eq!(iter.next().unwrap(), (&20, &200));
+/// assert!(iter.next().is_none());
/// }
///
/// # Ok::<(), Error>(())
@@ -188,6 +212,25 @@ pub fn try_reserve_node() -> Result<RBTreeNodeReservation<K, V>> {
pub fn try_allocate_node(key: K, value: V) -> Result<RBTreeNode<K, V>> {
Ok(Self::try_reserve_node()?.into_node(key, value))
}
+
+ /// Returns an iterator over the tree nodes, sorted by key.
+ pub fn iter(&self) -> RBTreeIterator<'_, K, V> {
+ RBTreeIterator {
+ _tree: PhantomData,
+ // SAFETY: `root` is valid as it's embedded in `self` and we have a valid `self`.
+ next: unsafe { bindings::rb_first(&self.root) },
+ }
+ }
+
+ /// Returns an iterator over the keys of the nodes in the tree, in sorted order.
+ pub fn keys(&self) -> impl Iterator<Item = &'_ K> {
+ self.iter().map(|(k, _)| k)
+ }
+
+ /// Returns an iterator over the values of the nodes in the tree, sorted by key.
+ pub fn values(&self) -> impl Iterator<Item = &'_ V> {
+ self.iter().map(|(_, v)| v)
+ }
}
impl<K, V> RBTree<K, V>
@@ -373,6 +416,56 @@ fn drop(&mut self) {
}
}
+impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
+ type Item = (&'a K, &'a V);
+ type IntoIter = RBTreeIterator<'a, K, V>;
+
+ fn into_iter(self) -> Self::IntoIter {
+ self.iter()
+ }
+}
+
+/// An iterator over the nodes of a [`RBTree`].
+///
+/// Instances are created by calling [`RBTree::iter`].
+///
+/// # Invariants
+/// - `self.next` is a valid pointer.
+/// - `self.next` points to a node stored inside of a valid `RBTree`.
+pub struct RBTreeIterator<'a, K, V> {
+ _tree: PhantomData<&'a RBTree<K, V>>,
+ next: *mut bindings::rb_node,
+}
+
+// SAFETY: The [`RBTreeIterator`] gives out immutable references to K and V, so it has the same
+// thread safety requirements as immutable references.
+unsafe impl<'a, K: Sync, V: Sync> Send for RBTreeIterator<'a, K, V> {}
+
+// SAFETY: The [`RBTreeIterator`] gives out immutable references to K and V, so it has the same
+// thread safety requirements as immutable references.
+unsafe impl<'a, K: Sync, V: Sync> Sync for RBTreeIterator<'a, K, V> {}
+
+impl<'a, K, V> Iterator for RBTreeIterator<'a, K, V> {
+ type Item = (&'a K, &'a V);
+
+ fn next(&mut self) -> Option<Self::Item> {
+ if self.next.is_null() {
+ return None;
+ }
+
+ // 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 cur = unsafe { container_of!(self.next, Node<K, V>, links) };
+
+ // SAFETY: `self.next` is a valid tree node by the type invariants.
+ self.next = unsafe { bindings::rb_next(self.next) };
+
+ // SAFETY: By the same reasoning above, it is safe to dereference the node. Additionally,
+ // it is ok to return a reference to members because the iterator must outlive it.
+ Some(unsafe { (&(*cur).key, &(*cur).value) })
+ }
+}
+
/// A memory reservation for a red-black tree node.
///
/// It contains the memory needed to hold a node that can be inserted into a red-black tree. One
--
2.44.0.769.g3c40516874-goog
From: Wedson Almeida Filho <[email protected]>
Add mutable Iterator implementation (`RBTreeIteratorMut`) for `RBTree`,
allowing iteration over (key, value) pairs in key order. Only values are
mutable, as mutating keys implies modifying a node's position in the tree.
Mutable iteration is used by the binder driver during shutdown to
clean up the tree maintained by the "range allocator" [1].
Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [1]
Signed-off-by: Wedson Almeida Filho <[email protected]>
Signed-off-by: Matt Gilbride <[email protected]>
Reviewed-by: Alice Ryhl <[email protected]>
Tested-by: Alice Ryhl <[email protected]>
---
rust/kernel/rbtree.rs | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 64 insertions(+)
diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
index 2f836be7bdbe..50d440c9926d 100644
--- a/rust/kernel/rbtree.rs
+++ b/rust/kernel/rbtree.rs
@@ -222,6 +222,15 @@ pub fn iter(&self) -> RBTreeIterator<'_, K, V> {
}
}
+ /// Returns a mutable iterator over the tree nodes, sorted by key.
+ pub fn iter_mut(&mut self) -> RBTreeIteratorMut<'_, K, V> {
+ RBTreeIteratorMut {
+ _tree: PhantomData,
+ // SAFETY: `root` is valid as it's embedded in `self` and we have a valid `self`.
+ next: unsafe { bindings::rb_first(&self.root) },
+ }
+ }
+
/// Returns an iterator over the keys of the nodes in the tree, in sorted order.
pub fn keys(&self) -> impl Iterator<Item = &'_ K> {
self.iter().map(|(k, _)| k)
@@ -231,6 +240,11 @@ pub fn keys(&self) -> impl Iterator<Item = &'_ K> {
pub fn values(&self) -> impl Iterator<Item = &'_ V> {
self.iter().map(|(_, v)| v)
}
+
+ /// Returns a mutable iterator over the values of the nodes in the tree, sorted by key.
+ pub fn values_mut(&mut self) -> impl Iterator<Item = &'_ mut V> {
+ self.iter_mut().map(|(_, v)| v)
+ }
}
impl<K, V> RBTree<K, V>
@@ -466,6 +480,56 @@ fn next(&mut self) -> Option<Self::Item> {
}
}
+impl<'a, K, V> IntoIterator for &'a mut RBTree<K, V> {
+ type Item = (&'a K, &'a mut V);
+ type IntoIter = RBTreeIteratorMut<'a, K, V>;
+
+ fn into_iter(self) -> Self::IntoIter {
+ self.iter_mut()
+ }
+}
+
+/// A mutable iterator over the nodes of a [`RBTree`].
+///
+/// Instances are created by calling [`RBTree::iter_mut`].
+///
+/// # Invariants
+/// - `self.next` is a valid pointer.
+/// - `self.next` points to a node stored inside of a valid `RBTree`.
+pub struct RBTreeIteratorMut<'a, K, V> {
+ _tree: PhantomData<&'a RBTree<K, V>>,
+ next: *mut bindings::rb_node,
+}
+
+// SAFETY: The [`RBTreeIterator`] gives out mutable references to K and V, so it has the same
+// thread safety requirements as mutable references.
+unsafe impl<'a, K: Send, V: Send> Send for RBTreeIteratorMut<'a, K, V> {}
+
+// SAFETY: The [`RBTreeIterator`] gives out mutable references to K and V, so it has the same
+// thread safety requirements as mutable references.
+unsafe impl<'a, K: Sync, V: Sync> Sync for RBTreeIteratorMut<'a, K, V> {}
+
+impl<'a, K, V> Iterator for RBTreeIteratorMut<'a, K, V> {
+ type Item = (&'a K, &'a mut V);
+
+ fn next(&mut self) -> Option<Self::Item> {
+ if self.next.is_null() {
+ return None;
+ }
+
+ // 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 cur = unsafe { container_of!(self.next, Node<K, V>, links) }.cast_mut();
+
+ // SAFETY: `self.next` is a valid tree node by the type invariants.
+ self.next = unsafe { bindings::rb_next(self.next) };
+
+ // SAFETY: By the same reasoning above, it is safe to dereference the node. Additionally,
+ // it is ok to return a reference to members because the iterator must outlive it.
+ Some(unsafe { (&(*cur).key, &mut (*cur).value) })
+ }
+}
+
/// A memory reservation for a red-black tree node.
///
/// It contains the memory needed to hold a node that can be inserted into a red-black tree. One
--
2.44.0.769.g3c40516874-goog
On 18.04.24 16:15, Matt Gilbride wrote:
> diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
> new file mode 100644
> index 000000000000..ad406fc32d67
> --- /dev/null
> +++ b/rust/kernel/rbtree.rs
> @@ -0,0 +1,425 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +//! Red-black trees.
> +//!
> +//! C header: [`include/linux/rbtree.h`](srctree/include/linux/rbtree.h)
> +//!
> +//! Reference: <https://www.kernel.org/doc/html/latest/core-api/rbtree.html>
> +
> +use crate::{bindings, container_of, error::Result, prelude::*};
> +use alloc::boxed::Box;
> +use core::{
> + cmp::{Ord, Ordering},
> + convert::Infallible,
> + marker::PhantomData,
> + mem::MaybeUninit,
> + ptr::{addr_of_mut, NonNull},
> +};
> +
> +struct Node<K, V> {
> + links: bindings::rb_node,
> + key: K,
> + value: V,
> +}
Personal preference: I prefer putting items that give a high-level
overview of the module to the top. I don't feel like I gain anything
from seeing the definition of the `Node` type this early.
[...]
> +impl<K, V> RBTree<K, V> {
> + /// Creates a new and empty tree.
> + pub fn new() -> Self {
> + Self {
> + // INVARIANT: There are no nodes in the tree, so the invariant holds vacuously.
> + root: bindings::rb_root::default(),
> + _p: PhantomData,
> + }
> + }
> +
> + /// Allocates memory for a node to be eventually initialised and inserted into the tree via a
> + /// call to [`RBTree::insert`].
> + pub fn try_reserve_node() -> Result<RBTreeNodeReservation<K, V>> {
This function creates a `RBTreeNodeReservation`, I think it would make
sense to move it to that type and just name this function `new`.
> + Ok(RBTreeNodeReservation {
> + node: Box::init::<Infallible>(crate::init::uninit())?,
`Box::new_uninit()` probably makes more sense here. (what you did is not
wrong, but I think the intent is better captured by `new_uninit`)
> + })
> + }
> +
> + /// Allocates and initialises a node that can be inserted into the tree via
> + /// [`RBTree::insert`].
> + pub fn try_allocate_node(key: K, value: V) -> Result<RBTreeNode<K, V>> {
Same with this function, I would move it to `RBTreeNode` and call it
`new`.
> + Ok(Self::try_reserve_node()?.into_node(key, value))
> + }
> +}
> +
> +impl<K, V> RBTree<K, V>
> +where
> + K: Ord,
Citing the rust docs [1] on the requirements that implementations of the
`Ord` trait need to satsify:
"[...] Violating these requirements is a logic error. The behavior
resulting from a logic error is not specified, but users of the trait
must ensure that such logic errors do not result in undefined behavior.
This means that `unsafe` code **must not** rely on the correctness of
these methods."
I haven't yet fully checked this, since I would have to delve into the
C side. But I wanted to ask if you have given any thought to this issue.
In particular this means that you must not rely on `<` (or `cmp`) being
eg transitive in `unsafe` code.
From what I have seen in this patch, I think there are no issues with
the way you use `Ord`.
[1]: https://doc.rust-lang.org/core/cmp/trait.Ord.html
> +{
[...]
> +impl<K, V> RBTreeNodeReservation<K, V> {
> + /// Initialises a node reservation.
> + ///
> + /// It then becomes an [`RBTreeNode`] that can be inserted into a tree.
> + pub fn into_node(mut self, key: K, value: V) -> RBTreeNode<K, V> {
> + let node_ptr = self.node.as_mut_ptr();
> + // SAFETY: `node_ptr` is valid, and so are its fields.
> + unsafe { addr_of_mut!((*node_ptr).links).write(bindings::rb_node::default()) };
> + // SAFETY: `node_ptr` is valid, and so are its fields.
> + unsafe { addr_of_mut!((*node_ptr).key).write(key) };
> + // SAFETY: `node_ptr` is valid, and so are its fields.
> + unsafe { addr_of_mut!((*node_ptr).value).write(value) };
> + RBTreeNode {
> + // SAFETY: The pointer came from a `MaybeUninit<Node>` whose fields have all been
> + // initialised. Additionally, it has the same layout as `Node`.
> + node: unsafe { Box::<MaybeUninit<_>>::assume_init(self.node) },
> + }
I really dislike the verbosity of this function. Also what will ensure
that you really did initialize all fields? I think I have a way to
improve this using a new function on `Box`:
impl<T> Box<MaybeUninit<T>> {
fn re_init(self, init: impl Init<T, E>) -> Result<Box<T>, E>;
}
Then you could do this instead:
pub fn into_node(mut self, key: K, value: V) -> RBTreeNode<K, V> {
let node = init!(Node {
key,
value,
links: bindings::rb_node::default(),
});
RBTreeNode { node: self.node.re_init(node) }
}
All the `unsafe` vanishes!
I think this is useful in general, so I am going to send a patch with
the above mentioned method. In addition to that I am also going to
extend `Box` to allow converting `Box<T> -> Box<MaybeUninit<T>>` to
simplify `into_reservation` from patch 5.
--
Cheers,
Benno
> + }
> +}
> +
> +/// A red-black tree node.
> +///
> +/// The node is fully initialised (with key and value) and can be inserted into a tree without any
> +/// extra allocations or failure paths.
> +pub struct RBTreeNode<K, V> {
> + node: Box<Node<K, V>>,
> +}
> +
> +// SAFETY: If K and V can be sent across threads, then it's also okay to send [`RBTreeNode`] across
> +// threads.
> +unsafe impl<K: Send, V: Send> Send for RBTreeNode<K, V> {}
> +
> +// SAFETY: If K and V can be accessed without synchronization, then it's also okay to access
> +// [`RBTreeNode`] without synchronization.
> +unsafe impl<K: Sync, V: Sync> Sync for RBTreeNode<K, V> {}
>
> --
> 2.44.0.769.g3c40516874-goog
>
On 18.04.24 16:15, Matt Gilbride wrote:
> @@ -188,6 +212,25 @@ pub fn try_reserve_node() -> Result<RBTreeNodeReservation<K, V>> {
> pub fn try_allocate_node(key: K, value: V) -> Result<RBTreeNode<K, V>> {
> Ok(Self::try_reserve_node()?.into_node(key, value))
> }
> +
> + /// Returns an iterator over the tree nodes, sorted by key.
> + pub fn iter(&self) -> RBTreeIterator<'_, K, V> {
> + RBTreeIterator {
There is a missing `INVARIANT` comment here justifying the invariants of
`RBTreeIterator`.
> + _tree: PhantomData,
> + // SAFETY: `root` is valid as it's embedded in `self` and we have a valid `self`.
> + next: unsafe { bindings::rb_first(&self.root) },
> + }
> + }
> +
> + /// Returns an iterator over the keys of the nodes in the tree, in sorted order.
> + pub fn keys(&self) -> impl Iterator<Item = &'_ K> {
> + self.iter().map(|(k, _)| k)
> + }
> +
> + /// Returns an iterator over the values of the nodes in the tree, sorted by key.
> + pub fn values(&self) -> impl Iterator<Item = &'_ V> {
> + self.iter().map(|(_, v)| v)
> + }
> }
>
> impl<K, V> RBTree<K, V>
> @@ -373,6 +416,56 @@ fn drop(&mut self) {
> }
> }
>
> +impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
> + type Item = (&'a K, &'a V);
> + type IntoIter = RBTreeIterator<'a, K, V>;
> +
> + fn into_iter(self) -> Self::IntoIter {
> + self.iter()
> + }
> +}
> +
> +/// An iterator over the nodes of a [`RBTree`].
> +///
> +/// Instances are created by calling [`RBTree::iter`].
> +///
> +/// # Invariants
> +/// - `self.next` is a valid pointer.
> +/// - `self.next` points to a node stored inside of a valid `RBTree`.
> +pub struct RBTreeIterator<'a, K, V> {
> + _tree: PhantomData<&'a RBTree<K, V>>,
> + next: *mut bindings::rb_node,
> +}
> +
> +// SAFETY: The [`RBTreeIterator`] gives out immutable references to K and V, so it has the same
> +// thread safety requirements as immutable references.
> +unsafe impl<'a, K: Sync, V: Sync> Send for RBTreeIterator<'a, K, V> {}
The bounds on `K` and `V` look like typos to me. They should be `Send`
instead.
> +
> +// SAFETY: The [`RBTreeIterator`] gives out immutable references to K and V, so it has the same
> +// thread safety requirements as immutable references.
> +unsafe impl<'a, K: Sync, V: Sync> Sync for RBTreeIterator<'a, K, V> {}
> +
> +impl<'a, K, V> Iterator for RBTreeIterator<'a, K, V> {
> + type Item = (&'a K, &'a V);
> +
> + fn next(&mut self) -> Option<Self::Item> {
> + if self.next.is_null() {
> + return None;
> + }
> +
> + // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self`
This is not an invariant of `Self`, but rather `RBTree` and `self`
should be "`RBtree`s".
--
Cheers,
Benno
> + // point to the links field of `Node<K, V>` objects.
> + let cur = unsafe { container_of!(self.next, Node<K, V>, links) };
> +
> + // SAFETY: `self.next` is a valid tree node by the type invariants.
> + self.next = unsafe { bindings::rb_next(self.next) };
> +
> + // SAFETY: By the same reasoning above, it is safe to dereference the node. Additionally,
> + // it is ok to return a reference to members because the iterator must outlive it.
> + Some(unsafe { (&(*cur).key, &(*cur).value) })
> + }
> +}
> +
> /// A memory reservation for a red-black tree node.
> ///
> /// It contains the memory needed to hold a node that can be inserted into a red-black tree. One
>
> --
> 2.44.0.769.g3c40516874-goog
>
On 18.04.24 16:15, Matt Gilbride wrote:
> From: Wedson Almeida Filho <[email protected]>
>
> Add mutable Iterator implementation (`RBTreeIteratorMut`) for `RBTree`,
> allowing iteration over (key, value) pairs in key order. Only values are
> mutable, as mutating keys implies modifying a node's position in the tree.
>
> Mutable iteration is used by the binder driver during shutdown to
> clean up the tree maintained by the "range allocator" [1].
>
> Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [1]
> Signed-off-by: Wedson Almeida Filho <[email protected]>
> Signed-off-by: Matt Gilbride <[email protected]>
> Reviewed-by: Alice Ryhl <[email protected]>
> Tested-by: Alice Ryhl <[email protected]>
> ---
> rust/kernel/rbtree.rs | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 64 insertions(+)
>
> diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
> index 2f836be7bdbe..50d440c9926d 100644
> --- a/rust/kernel/rbtree.rs
> +++ b/rust/kernel/rbtree.rs
> @@ -222,6 +222,15 @@ pub fn iter(&self) -> RBTreeIterator<'_, K, V> {
> }
> }
>
> + /// Returns a mutable iterator over the tree nodes, sorted by key.
> + pub fn iter_mut(&mut self) -> RBTreeIteratorMut<'_, K, V> {
> + RBTreeIteratorMut {
This is missing an INVARIANT comment.
> + _tree: PhantomData,
> + // SAFETY: `root` is valid as it's embedded in `self` and we have a valid `self`.
> + next: unsafe { bindings::rb_first(&self.root) },
> + }
> + }
> +
> /// Returns an iterator over the keys of the nodes in the tree, in sorted order.
> pub fn keys(&self) -> impl Iterator<Item = &'_ K> {
> self.iter().map(|(k, _)| k)
> @@ -231,6 +240,11 @@ pub fn keys(&self) -> impl Iterator<Item = &'_ K> {
> pub fn values(&self) -> impl Iterator<Item = &'_ V> {
> self.iter().map(|(_, v)| v)
> }
> +
> + /// Returns a mutable iterator over the values of the nodes in the tree, sorted by key.
> + pub fn values_mut(&mut self) -> impl Iterator<Item = &'_ mut V> {
> + self.iter_mut().map(|(_, v)| v)
> + }
> }
>
> impl<K, V> RBTree<K, V>
> @@ -466,6 +480,56 @@ fn next(&mut self) -> Option<Self::Item> {
> }
> }
>
> +impl<'a, K, V> IntoIterator for &'a mut RBTree<K, V> {
> + type Item = (&'a K, &'a mut V);
> + type IntoIter = RBTreeIteratorMut<'a, K, V>;
> +
> + fn into_iter(self) -> Self::IntoIter {
> + self.iter_mut()
> + }
> +}
> +
> +/// A mutable iterator over the nodes of a [`RBTree`].
> +///
> +/// Instances are created by calling [`RBTree::iter_mut`].
> +///
> +/// # Invariants
> +/// - `self.next` is a valid pointer.
> +/// - `self.next` points to a node stored inside of a valid `RBTree`.
> +pub struct RBTreeIteratorMut<'a, K, V> {
I think the names `Iter` and `IterMut` are more natural. That is what
the collections in `std::collections` do. These are in the module
`rbtree`, so you can refer to them as `rbtree::Iter`.
> + _tree: PhantomData<&'a RBTree<K, V>>,
This should have the type `PhantomData<&'a mut RBTree<K, V>>`.
> + next: *mut bindings::rb_node,
> +}
You could create a common iterator type, since both `RBTreeIterator` and
`RBTreeIteratorMut` are very similar.
How about a (private) `RawIter`:
struct RawIter<K, V> {
next: *mut bindings::rb_node,
_phantom: PhantomData<fn() -> (K, V)>,
}
And implement `Iterator` with `Item = (*mut K, *mut V)` for `RawIter`.
Then you can change `Iter` to be:
pub struct Iter<'a, K, V> {
raw_iter: RawIter<K, V>,
_tree: PhantomData<&'a RBTree<K, V>>,
}
--
Cheers,
Benno
> +
> +// SAFETY: The [`RBTreeIterator`] gives out mutable references to K and V, so it has the same
> +// thread safety requirements as mutable references.
> +unsafe impl<'a, K: Send, V: Send> Send for RBTreeIteratorMut<'a, K, V> {}
> +
> +// SAFETY: The [`RBTreeIterator`] gives out mutable references to K and V, so it has the same
> +// thread safety requirements as mutable references.
> +unsafe impl<'a, K: Sync, V: Sync> Sync for RBTreeIteratorMut<'a, K, V> {}
> +
> +impl<'a, K, V> Iterator for RBTreeIteratorMut<'a, K, V> {
> + type Item = (&'a K, &'a mut V);
> +
> + fn next(&mut self) -> Option<Self::Item> {
> + if self.next.is_null() {
> + return None;
> + }
> +
> + // 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 cur = unsafe { container_of!(self.next, Node<K, V>, links) }.cast_mut();
> +
> + // SAFETY: `self.next` is a valid tree node by the type invariants.
> + self.next = unsafe { bindings::rb_next(self.next) };
> +
> + // SAFETY: By the same reasoning above, it is safe to dereference the node. Additionally,
> + // it is ok to return a reference to members because the iterator must outlive it.
> + Some(unsafe { (&(*cur).key, &mut (*cur).value) })
> + }
> +}
> +
> /// A memory reservation for a red-black tree node.
> ///
> /// It contains the memory needed to hold a node that can be inserted into a red-black tree. One
>
> --
> 2.44.0.769.g3c40516874-goog
>
On 18.04.24 16:15, Matt Gilbride wrote:
> @@ -400,6 +442,72 @@ fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> {
> pub fn remove(&mut self, key: &K) -> Option<V> {
> self.remove_node(key).map(|node| node.node.value)
> }
> +
> + /// 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(&mut self, key: &K) -> Option<RBTreeCursor<'_, 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) }.cast_mut();
> + // 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 };
Since you have this pattern multiple times, I think you could have a
single function that walks the tree and takes care of most of the
`unsafe` stuff. A good starting point might be this:
unsafe fn walk<F, R>(node: *mut bindings::rb_node, dir: F) -> R
where
/* this, key */
F: FnMut(*mut bindings::rb_node, &K) -> Either<Direction, R>;
> + if key == this_key {
> + // INVARIANT:
> + // - `self.root` and `node` are valid pointers.
> + // - `self.root` is the root of an [`RBTree`].
> + // - `node` is a valid node in an [`RBTree`].
> + // - Due to the type signature of this function, the returned [`RBTreeCursor`]
> + // borrows from `self`.
> + return Some(RBTreeCursor {
> + _tree: PhantomData,
> + root: addr_of_mut!(self.root),
> + current: node,
> + });
> + } else {
> + node = if key > this_key {
> + right_child
> + } else {
> + 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);
> + }
> + left_child
> + }
> + };
> + }
> + // INVARIANT:
> + // - `self.root` and `best` are valid pointers.
> + // - `self.root` is the root of an [`RBTree`].
> + // - `best` is a valid node in an [`RBTree`].
> + // - Due to the type signature of this function, the returned [`RBTreeCursor`]
> + // borrows from `self`.
> + best_match.map(|best| RBTreeCursor {
> + _tree: PhantomData,
> + root: addr_of_mut!(self.root),
> + // SAFETY: `best` is a non-null node so it is valid by the type invariants.
> + current: unsafe { addr_of_mut!((*best.as_ptr()).links) },
> + })
> + }
> }
>
> impl<K, V> Default for RBTree<K, V> {
[...]
> +/// # Invariants
> +/// - `root` and `current` are valid pointers.
> +/// - `root` points to the `root` node of an [`RBTree`].
> +/// - `current` points to a node that is in the same [`RBTree`] that `root` is pointing to.
> +/// - A cursor must borrow the [`RBTree`] containing `root` and `current` mutably.
> +pub struct RBTreeCursor<'a, K, V> {
> + _tree: PhantomData<&'a RBTree<K, V>>,
Why is this not `&'a mut RBTree<K, V>`?
> + root: *mut bindings::rb_root,
> + current: *mut bindings::rb_node,
> +}
> +
> +// SAFETY: The [`RBTreeCursor`] 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: Send, V: Send> Send for RBTreeCursor<'a, K, V> {}
> +
> +// SAFETY: The [`RBTreeCursor`] 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 RBTreeCursor<'a, K, V> {}
> +
> +impl<'a, K, V> RBTreeCursor<'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:
> + // - `self.current` is a valid node by the type invariants.
> + // - We have an mutable reference by the function signature.
> + unsafe { Self::to_key_value_mut(self.current) }
> + }
> +
> + /// Remove the current node from the tree.
> + ///
> + /// Returns a cursor to the next node, if it exists,
> + /// else the previous node. Returns [`None`] if the tree
> + /// becomes empty.
> + pub fn remove_current(self) -> Option<Self> {
> + let prev = self.get_neighbor_raw(Direction::Prev);
> + let next = self.get_neighbor_raw(Direction::Next);
> + // 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!(self.current, Node<K, V>, links) }.cast_mut();
> + // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so
> + // the tree cannot change. By the tree invariant, all nodes are valid.
> + unsafe { bindings::rb_erase(&mut (*this).links, self.root) };
> +
> + let current = match (prev, next) {
> + (_, Some(next)) => next,
> + (Some(prev), None) => prev,
> + (None, None) => {
> + return None;
> + }
> + };
> +
> + // INVARIANT:
> + // - `self.root` and `current` are valid pointers.
> + // - `self.root` is the root of an [`RBTree`].
> + // - `current` is a valid node in an [`RBTree`].
> + // - Due to the function signature, `self` is an owned [`RBTreeCursor`],
> + // and [`RBTreeCursor`]s are only created via functions with a mutable reference
> + // to an [`RBTree`].
> + Some(Self {
> + current,
> + _tree: self._tree,
> + root: self.root,
> + })
> + }
> +
> + /// Remove the previous node, returning it if it exists.
> + pub fn remove_prev(&mut self) -> Option<(K, V)> {
Why do these functions not return `Option<RBTreeNode<K, V>>`?
> + self.remove_neighbor(Direction::Prev)
> + }
> +
> + /// Remove the next node, returning it if it exists.
> + pub fn remove_next(&mut self) -> Option<(K, V)> {
> + self.remove_neighbor(Direction::Next)
> + }
> +
> + fn remove_neighbor(&mut self, direction: Direction) -> Option<(K, V)> {
> + if let Some(neighbor) = self.get_neighbor_raw(direction) {
> + // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so
> + // the tree cannot change. By the tree invariant, all nodes are valid.
> + unsafe { bindings::rb_erase(neighbor, self.root) };
> + // 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!(neighbor, Node<K, V>, links) }.cast_mut();
> + // SAFETY: `this` is valid by the type invariants as described above.
> + let n = unsafe { Box::from_raw(this) };
> + return Some((n.key, n.value));
> + }
> + None
> + }
> +
> + /// Move the cursor to the previous node, returning [`None`] if it doesn't exist.
> + pub fn move_prev(self) -> Option<Self> {
> + self.mv(Direction::Prev)
> + }
> +
> + /// Move the cursor to the next node, returning [`None`] if it doesn't exist.
> + pub fn move_next(self) -> Option<Self> {
> + self.mv(Direction::Next)
> + }
> +
> + fn mv(self, direction: Direction) -> Option<Self> {
Does it hurt to name this `move`?
> + // INVARIANT:
> + // - `self.root` and `neighbor` are valid pointers.
> + // - `self.root` is the root of an [`RBTree`].
> + // - `neighbor` is a valid node in an [`RBTree`].
> + // - Due to the function signature, `self` is an owned [`RBTreeCursor`],
> + // and [`RBTreeCursor`]s are only created via functions with a mutable reference
> + // to an [`RBTree`].
> + self.get_neighbor_raw(direction).map(|neighbor| Self {
> + _tree: self._tree,
> + root: self.root,
> + current: neighbor,
> + })
> + }
[...]
> + /// SAFETY:
> + /// - `node` must be a valid pointer to a node in an [`RBTree`].
> + /// - The caller has immutable access to `node` for the duration of 'a.
> + unsafe fn to_key_value(node: *mut bindings::rb_node) -> (&'a K, &'a 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, 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 { &(*this).value };
> + (k, v)
> + }
> +
> + /// SAFETY:
> + /// - `node` must be a valid pointer to a node in an [`RBTree`].
> + /// - The caller has mutable access to `node` for the duration of 'a.
> + unsafe fn to_key_value_mut(node: *mut bindings::rb_node) -> (&'a K, &'a 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, Node<K, V>, links) }.cast_mut();
> + // 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 { &mut (*this).value };
> + (k, v)
> + }
You can create a single function that does the `container_of!` stuff and
that returns `(*mut K, *mut V)` and implement these two in terms of that
one.
--
Cheers,
Benno
> +}
> +
> +/// Direction for [`RBTreeCursor`] operations.
> +enum Direction {
> + /// the node immediately before, in sort order
> + Prev,
> + /// the node immediately after, in sort order
> + Next,
> +}
> +
> impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
> type Item = (&'a K, &'a V);
> type IntoIter = RBTreeIterator<'a, K, V>;
>
> --
> 2.44.0.769.g3c40516874-goog
>
On 25.04.24 23:45, Benno Lossin wrote:
> On 18.04.24 16:15, Matt Gilbride wrote:
>> @@ -373,6 +416,56 @@ fn drop(&mut self) {
>> }
>> }
>>
>> +impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
>> + type Item = (&'a K, &'a V);
>> + type IntoIter = RBTreeIterator<'a, K, V>;
>> +
>> + fn into_iter(self) -> Self::IntoIter {
>> + self.iter()
>> + }
>> +}
>> +
>> +/// An iterator over the nodes of a [`RBTree`].
>> +///
>> +/// Instances are created by calling [`RBTree::iter`].
>> +///
>> +/// # Invariants
>> +/// - `self.next` is a valid pointer.
>> +/// - `self.next` points to a node stored inside of a valid `RBTree`.
>> +pub struct RBTreeIterator<'a, K, V> {
>> + _tree: PhantomData<&'a RBTree<K, V>>,
>> + next: *mut bindings::rb_node,
>> +}
>> +
>> +// SAFETY: The [`RBTreeIterator`] gives out immutable references to K and V, so it has the same
>> +// thread safety requirements as immutable references.
>> +unsafe impl<'a, K: Sync, V: Sync> Send for RBTreeIterator<'a, K, V> {}
>
> The bounds on `K` and `V` look like typos to me. They should be `Send`
> instead.
Oops, scratch this comment, what you wrote is correct, since we treat
`RBTreeIterator` as `(&K, &V)`.
--
Cheers,
Benno
On 18.04.24 16:15, Matt Gilbride wrote:
> @@ -332,63 +338,54 @@ pub fn insert(&mut self, RBTreeNode { node }: RBTreeNode<K, V>) -> Option<RBTree
> // we store `parent` and `child_field_of_parent`, and the new `node` will go somewhere
> // in the subtree of `parent` that `child_field_of_parent` points at. Once
> // we find an empty subtree, we can insert the new node using `rb_link_node`.
> - let mut parent = core::ptr::null_mut();
> let mut child_field_of_parent: &mut *mut bindings::rb_node = &mut self.root.rb_node;
> - while !child_field_of_parent.is_null() {
> - parent = *child_field_of_parent;
> + let mut parent = core::ptr::null_mut();
Nit: why are you moving this line below `child_field_of_parent`? Just an
artifact of rebasing?
> + while !(*child_field_of_parent).is_null() {
> + let curr = *child_field_of_parent;
> + // SAFETY: All links fields we create are in a `Node<K, V>`.
> + let node = unsafe { container_of!(curr, Node<K, V>, links) };
[...]
> @@ -1119,3 +1099,177 @@ unsafe impl<K: Send, V: Send> Send for RBTreeNode<K, V> {}
> // SAFETY: If K and V can be accessed without synchronization, then it's also okay to access
> // [`RBTreeNode`] without synchronization.
> unsafe impl<K: Sync, V: Sync> Sync for RBTreeNode<K, V> {}
> +
> +impl<K, V> RBTreeNode<K, V> {
> + /// Drop the key and value, but keep the allocation.
> + ///
> + /// It then becomes a reservation that can be re-initialised into a different node (i.e., with
> + /// a different key and/or value).
> + ///
> + /// The existing key and value are dropped in-place as part of this operation, that is, memory
> + /// may be freed (but only for the key/value; memory for the node itself is kept for reuse).
> + pub fn into_reservation(self) -> RBTreeNodeReservation<K, V> {
> + let raw = Box::into_raw(self.node);
> + let mut ret = RBTreeNodeReservation {
> + // SAFETY: The pointer came from a valid `Node`, which has the same layout as
> + // `MaybeUninit<Node>`.
> + node: unsafe { Box::from_raw(raw as _) },
> + };
> + // SAFETY: Although the type is `MaybeUninit<Node>`, we know it has been initialised
> + // because it came from a `Node`. So it is safe to drop it.
> + unsafe { core::ptr::drop_in_place::<Node<K, V>>(ret.node.as_mut_ptr()) };
> + ret
> + }
With my patch [1] this can be simplified.
[1]: https://lore.kernel.org/rust-for-linux/[email protected]/
> +}
> +
> +/// A view into a single entry in a map, which may either be vacant or occupied.
> +///
> +/// This enum is constructed from the [`entry`] method on [`RBTree`].
You could just write [`RBTree::entry`].
> +///
> +/// [`entry`]: fn@RBTree::entry
> +pub enum Entry<'a, K, V> {
> + /// This [`RBTree`] does not have a node with this key.
> + Vacant(VacantEntry<'a, K, V>),
> + /// This [`RBTree`] already has a node with this key.
> + Occupied(OccupiedEntry<'a, K, V>),
> +}
[...]
> +impl<'a, K, V> RawVacantEntry<'a, K, V> {
> + /// Inserts the given node into the [`RBTree`] at this entry.
> + ///
> + /// The `node` must have a key such that inserting it here does not break the ordering of this
> + /// [`RBTree`].
> + fn insert(self, node: RBTreeNode<K, V>) -> &'a mut V {
> + let node = Box::into_raw(node.node);
> +
> + // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when
> + // the node is removed or replaced.
> + let node_links = unsafe { addr_of_mut!((*node).links) };
> +
> + // INVARIANT: We are linking in a new node, which is valid. It remains valid because we
> + // "forgot" it with `Box::into_raw`.
> + // SAFETY: All pointers are null or valid in an appropriate way.
I don't like the formulation "valid in an appropriate way", since if you
don't know what the appropriate way is, this doesn't help you.
> + unsafe { bindings::rb_link_node(node_links, self.parent, self.child_field_of_parent) };
> +
> + // SAFETY: All pointers are valid. `node` has just been inserted into the tree.
> + unsafe { bindings::rb_insert_color(node_links, &mut self.rbtree.root) };
> +
> + // SAFETY: The node is valid until we remove it from the tree.
> + unsafe { &mut (*node).value }
> + }
> +}
> +
> +impl<'a, K, V> VacantEntry<'a, K, V> {
> + /// Inserts the given node into the [`RBTree`] at this entry.
> + pub fn insert(self, value: V, reservation: RBTreeNodeReservation<K, V>) -> &'a mut V {
> + self.raw.insert(reservation.into_node(self.key, value))
> + }
> +}
> +
> +/// A view into an occupied entry in a [`RBTree`]. It is part of the [`Entry`] enum.
> +///
> +/// # Invariants
> +/// - `node_links` is a valid, non-null pointer to a tree node.
It should be the same tree as `self.rbtree`, right? (I see you calling
`rb_replace_node` below with the rbtree root used)
--
Cheers,
Benno
> +pub struct OccupiedEntry<'a, K, V> {
> + rbtree: &'a mut RBTree<K, V>,
> + /// The node that this entry corresponds to.
> + node_links: *mut bindings::rb_node,
> +}