]>
git.proxmox.com Git - rustc.git/blob - library/alloc/src/collections/btree/split.rs
1 use super::node
::{ForceResult::*, Root}
;
2 use super::search
::SearchResult
::*;
3 use core
::alloc
::Allocator
;
4 use core
::borrow
::Borrow
;
6 impl<K
, V
> Root
<K
, V
> {
7 /// Calculates the length of both trees that result from splitting up
8 /// a given number of distinct key-value pairs.
9 pub fn calc_split_length(
14 let (length_a
, length_b
);
15 if root_a
.height() < root_b
.height() {
16 length_a
= root_a
.reborrow().calc_length();
17 length_b
= total_num
- length_a
;
18 debug_assert_eq
!(length_b
, root_b
.reborrow().calc_length());
20 length_b
= root_b
.reborrow().calc_length();
21 length_a
= total_num
- length_b
;
22 debug_assert_eq
!(length_a
, root_a
.reborrow().calc_length());
27 /// Split off a tree with key-value pairs at and after the given key.
28 /// The result is meaningful only if the tree is ordered by key,
29 /// and if the ordering of `Q` corresponds to that of `K`.
30 /// If `self` respects all `BTreeMap` tree invariants, then both
31 /// `self` and the returned tree will respect those invariants.
32 pub fn split_off
<Q
: ?Sized
+ Ord
, A
: Allocator
+ Clone
>(&mut self, key
: &Q
, alloc
: A
) -> Self
37 let mut right_root
= Root
::new_pillar(left_root
.height(), alloc
.clone());
38 let mut left_node
= left_root
.borrow_mut();
39 let mut right_node
= right_root
.borrow_mut();
42 let mut split_edge
= match left_node
.search_node(key
) {
43 // key is going to the right tree
44 Found(kv
) => kv
.left_edge(),
48 split_edge
.move_suffix(&mut right_node
);
50 match (split_edge
.force(), right_node
.force()) {
51 (Internal(edge
), Internal(node
)) => {
52 left_node
= edge
.descend();
53 right_node
= node
.first_edge().descend();
55 (Leaf(_
), Leaf(_
)) => break,
60 left_root
.fix_right_border(alloc
.clone());
61 right_root
.fix_left_border(alloc
);
65 /// Creates a tree consisting of empty nodes.
66 fn new_pillar
<A
: Allocator
+ Clone
>(height
: usize, alloc
: A
) -> Self {
67 let mut root
= Root
::new(alloc
.clone());
69 root
.push_internal_level(alloc
.clone());