Skip to contentSkip to conversation

rust: add fast path to `RBTree::find_mut` for empty tree

PATCH In review Onur Özkan 2 participants 2 messages Jun 25, 2025 1 message not in the archive Rust

lore
Share & tools
lore

Onur Özkan

author reviewer
#0 lore raw

PATCH 1/1 rust: add fast path to `RBTree::find_mut` for empty tree

Adds a fast path to RBTree::find_mut that immediately returns None when the tree is empty.

This should also benefit RBTree::get_mut, RBTree::remove_node and RBTree::remove functions as they rely on find_mut internally.

---
 rust/kernel/rbtree.rs | 5 +++++
 1 file changed, 5 insertions(+)
rust/kernel/rbtree.rs +5 -0
index 8d978c896747..a9b79b22ea32 100644
@@ -365,6 +365,11 @@ pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
 
     /// Used for accessing the given node, if it exists.
     pub fn find_mut(&mut self, key: &K) -> Option<OccupiedEntry<'_, K, V>> {
+        // Fast path: return `None` when tree is empty.
+        if self.root.rb_node.is_null() {
+            return None;
+        }
+
         match self.raw_entry(key) {
             RawEntry::Occupied(entry) => Some(entry),
             RawEntry::Vacant(_entry) => None,

--
2.50.0

A message that is not in the archive (sent off-list or not yet received): [email protected]

#2 lore raw
Quoted 2 lines · Onur Özkan

Oops, I didn't realize that rb_node was a pointer. Please don't take the patch seriously. :)

I think this reply didn't reach the lists because it uses HTML.

Cheers,
Miguel