New upstream version 1.63.0+dfsg1

[rustc.git] / library / alloc / src / collections / btree / append.rs

diff --git a/library/alloc/src/collections/btree/append.rs b/library/alloc/src/collections/btree/append.rs
index a30a21db5347f443da4eeb94dfead3d77475b0fa..b6989afb6255d81747e36b30302155a581051154 100644 (file)
--- a/library/alloc/src/collections/btree/append.rs
+++ b/library/alloc/src/collections/btree/append.rs
@@ -1,5 +1,6 @@
 use super::merge_iter::MergeIterInner;
 use super::node::{self, Root};
+use core::alloc::Allocator;
 use core::iter::FusedIterator;
 
 impl<K, V> Root<K, V> {
@@ -14,8 +15,13 @@ impl<K, V> Root<K, V> {
     /// a `BTreeMap`, both iterators should produce keys in strictly ascending
     /// order, each greater than all keys in the tree, including any keys
     /// already in the tree upon entry.
-    pub fn append_from_sorted_iters<I>(&mut self, left: I, right: I, length: &mut usize)
-    where
+    pub fn append_from_sorted_iters<I, A: Allocator + Clone>(
+        &mut self,
+        left: I,
+        right: I,
+        length: &mut usize,
+        alloc: A,
+    ) where
         K: Ord,
         I: Iterator<Item = (K, V)> + FusedIterator,
     {
@@ -23,13 +29,13 @@ impl<K, V> Root<K, V> {
         let iter = MergeIter(MergeIterInner::new(left, right));
 
         // Meanwhile, we build a tree from the sorted sequence in linear time.
-        self.bulk_push(iter, length)
+        self.bulk_push(iter, length, alloc)
     }
 
     /// Pushes all key-value pairs to the end of the tree, incrementing a
     /// `length` variable along the way. The latter makes it easier for the
     /// caller to avoid a leak when the iterator panicks.
-    pub fn bulk_push<I>(&mut self, iter: I, length: &mut usize)
+    pub fn bulk_push<I, A: Allocator + Clone>(&mut self, iter: I, length: &mut usize, alloc: A)
     where
         I: Iterator<Item = (K, V)>,
     {
@@ -58,7 +64,7 @@ impl<K, V> Root<K, V> {
                         }
                         Err(_) => {
                             // We are at the top, create a new root node and push there.
-                            open_node = self.push_internal_level();
+                            open_node = self.push_internal_level(alloc.clone());
                             break;
                         }
                     }
@@ -66,9 +72,9 @@ impl<K, V> Root<K, V> {
 
                 // Push key-value pair and new right subtree.
                 let tree_height = open_node.height() - 1;
-                let mut right_tree = Root::new();
+                let mut right_tree = Root::new(alloc.clone());
                 for _ in 0..tree_height {
-                    right_tree.push_internal_level();
+                    right_tree.push_internal_level(alloc.clone());
                 }
                 open_node.push(key, value, right_tree);