1use super::map::MIN_LEN;
2use super::node::{marker, ForceResult::*, Handle, LeftOrRight::*, NodeRef};
3use core::alloc::Allocator;
4
5impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV> {
6 /// Removes a key-value pair from the tree, and returns that pair, as well as
7 /// the leaf edge corresponding to that former pair. It's possible this empties
8 /// a root node that is internal, which the caller should pop from the map
9 /// holding the tree. The caller should also decrement the map's length.
10 pub fn remove_kv_tracking<F: FnOnce(), A: Allocator + Clone>(
11 self,
12 handle_emptied_internal_root: F,
13 alloc: A,
14 ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
15 match self.force() {
16 Leaf(node: Handle, K, …, …>, …>) => node.remove_leaf_kv(handle_emptied_internal_root, alloc),
17 Internal(node: Handle, K, …, …>, …>) => node.remove_internal_kv(handle_emptied_internal_root, alloc),
18 }
19 }
20}
21
22impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
23 fn remove_leaf_kv<F: FnOnce(), A: Allocator + Clone>(
24 self,
25 handle_emptied_internal_root: F,
26 alloc: A,
27 ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
28 let (old_kv, mut pos) = self.remove();
29 let len = pos.reborrow().into_node().len();
30 if len < MIN_LEN {
31 let idx = pos.idx();
32 // We have to temporarily forget the child type, because there is no
33 // distinct node type for the immediate parents of a leaf.
34 let new_pos = match pos.into_node().forget_type().choose_parent_kv() {
35 Ok(Left(left_parent_kv)) => {
36 debug_assert!(left_parent_kv.right_child_len() == MIN_LEN - 1);
37 if left_parent_kv.can_merge() {
38 left_parent_kv.merge_tracking_child_edge(Right(idx), alloc.clone())
39 } else {
40 debug_assert!(left_parent_kv.left_child_len() > MIN_LEN);
41 left_parent_kv.steal_left(idx)
42 }
43 }
44 Ok(Right(right_parent_kv)) => {
45 debug_assert!(right_parent_kv.left_child_len() == MIN_LEN - 1);
46 if right_parent_kv.can_merge() {
47 right_parent_kv.merge_tracking_child_edge(Left(idx), alloc.clone())
48 } else {
49 debug_assert!(right_parent_kv.right_child_len() > MIN_LEN);
50 right_parent_kv.steal_right(idx)
51 }
52 }
53 Err(pos) => unsafe { Handle::new_edge(pos, idx) },
54 };
55 // SAFETY: `new_pos` is the leaf we started from or a sibling.
56 pos = unsafe { new_pos.cast_to_leaf_unchecked() };
57
58 // Only if we merged, the parent (if any) has shrunk, but skipping
59 // the following step otherwise does not pay off in benchmarks.
60 //
61 // SAFETY: We won't destroy or rearrange the leaf where `pos` is at
62 // by handling its parent recursively; at worst we will destroy or
63 // rearrange the parent through the grandparent, thus change the
64 // link to the parent inside the leaf.
65 if let Ok(parent) = unsafe { pos.reborrow_mut() }.into_node().ascend() {
66 if !parent.into_node().forget_type().fix_node_and_affected_ancestors(alloc) {
67 handle_emptied_internal_root();
68 }
69 }
70 }
71 (old_kv, pos)
72 }
73}
74
75impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
76 fn remove_internal_kv<F: FnOnce(), A: Allocator + Clone>(
77 self,
78 handle_emptied_internal_root: F,
79 alloc: A,
80 ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
81 // Remove an adjacent KV from its leaf and then put it back in place of
82 // the element we were asked to remove. Prefer the left adjacent KV,
83 // for the reasons listed in `choose_parent_kv`.
84 let left_leaf_kv: Result, …, …, …>, …>, …> = self.left_edge().descend().last_leaf_edge().left_kv();
85 let left_leaf_kv: Handle, K, …, …>, …> = unsafe { left_leaf_kv.ok().unwrap_unchecked() };
86 let (left_kv: (K, V), left_hole: Handle, K, …, …>, …>) = left_leaf_kv.remove_leaf_kv(handle_emptied_internal_root, alloc);
87
88 // The internal node may have been stolen from or merged. Go back right
89 // to find where the original KV ended up.
90 let mut internal: Handle, K, …, …>, …> = unsafe { left_hole.next_kv().ok().unwrap_unchecked() };
91 let old_kv: (K, V) = internal.replace_kv(k:left_kv.0, v:left_kv.1);
92 let pos: Handle, K, …, …>, …> = internal.next_leaf_edge();
93 (old_kv, pos)
94 }
95}
96