alloc/collections/btree/
append.rs

1use core::alloc::AllocatorClone;
2
3use super::node::{self, Root};
4
5impl<K, V> Root<K, V> {
6    /// Pushes all key-value pairs to the end of the tree, incrementing a
7    /// `length` variable along the way. The latter makes it easier for the
8    /// caller to avoid a leak when the iterator panicks.
9    pub(super) fn bulk_push<I, A: AllocatorClone>(&mut self, iter: I, length: &mut usize, alloc: A)
10    where
11        I: Iterator<Item = (K, V)>,
12    {
13        let mut cur_node = self.borrow_mut().last_leaf_edge().into_node();
14        // Iterate through all key-value pairs, pushing them into nodes at the right level.
15        for (key, value) in iter {
16            // Try to push key-value pair into the current leaf node.
17            if cur_node.len() < node::CAPACITY {
18                cur_node.push(key, value);
19            } else {
20                // No space left, go up and push there.
21                let mut open_node;
22                let mut test_node = cur_node.forget_type();
23                loop {
24                    match test_node.ascend() {
25                        Ok(parent) => {
26                            let parent = parent.into_node();
27                            if parent.len() < node::CAPACITY {
28                                // Found a node with space left, push here.
29                                open_node = parent;
30                                break;
31                            } else {
32                                // Go up again.
33                                test_node = parent.forget_type();
34                            }
35                        }
36                        Err(_) => {
37                            // We are at the top, create a new root node and push there.
38                            open_node = self.push_internal_level(alloc.clone());
39                            break;
40                        }
41                    }
42                }
43
44                // Push key-value pair and new right subtree.
45                let tree_height = open_node.height() - 1;
46                let mut right_tree = Root::new(alloc.clone());
47                for _ in 0..tree_height {
48                    right_tree.push_internal_level(alloc.clone());
49                }
50                open_node.push(key, value, right_tree);
51
52                // Go down to the rightmost leaf again.
53                cur_node = open_node.forget_type().last_leaf_edge().into_node();
54            }
55
56            // Increment length every iteration, to make sure the map drops
57            // the appended elements even if advancing the iterator panicks.
58            *length += 1;
59        }
60        self.fix_right_border_of_plentiful();
61    }
62}
alloc/collections/btree/append.rs

alloc/collections/btree/
append.rs
