alloc/collections/btree/
append.rs

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

alloc/collections/btree/
append.rs
