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