Rollup merge of #71523 - Mark-Simulacrum:alloc-inline-dup, r=Amanieu

Take a single root node in range_search

The unsafe code can be justified within range_search, as it makes sure to not
overlap the returned references, but from the callers perspective it's an
entirely safe algorithm and there's no need for the caller to know about the
duplication.

cc @ssomers
r? @Amanieu

1 files changed, 7 insertions, 10 deletions

diff --git a/src/liballoc/collections/btree/map.rs b/src/liballoc/collections/btree/map.rs
index 91d93a1be1c..8d0cd191c2a 100644
--- a/src/liballoc/collections/btree/map.rs
+++ b/src/liballoc/collections/btree/map.rs
@@ -1034,9 +1034,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
         R: RangeBounds<T>,
     {
         if let Some(root) = &self.root {
-            let root1 = root.as_ref();
-            let root2 = root.as_ref();
-            let (f, b) = range_search(root1, root2, range);
+            let (f, b) = range_search(root.as_ref(), range);
 
             Range { front: Some(f), back: Some(b) }
         } else {
@@ -1082,9 +1080,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
         R: RangeBounds<T>,
     {
         if let Some(root) = &mut self.root {
-            let root1 = root.as_mut();
-            let root2 = unsafe { ptr::read(&root1) };
-            let (f, b) = range_search(root1, root2, range);
+            let (f, b) = range_search(root.as_mut(), range);
 
             RangeMut { front: Some(f), back: Some(b), _marker: PhantomData }
         } else {
@@ -2043,8 +2039,7 @@ where
 }
 
 fn range_search<BorrowType, K, V, Q: ?Sized, R: RangeBounds<Q>>(
-    root1: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
-    root2: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
+    root: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
     range: R,
 ) -> (
     Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>,
@@ -2064,8 +2059,10 @@ where
         _ => {}
     };
 
-    let mut min_node = root1;
-    let mut max_node = root2;
+    // We duplicate the root NodeRef here -- we will never access it in a way
+    // that overlaps references obtained from the root.
+    let mut min_node = unsafe { ptr::read(&root) };
+    let mut max_node = root;
     let mut min_found = false;
     let mut max_found = false;