1 | use super::map::MIN_LEN; |
2 | use super::node::{marker, ForceResult::*, Handle, LeftOrRight::*, NodeRef}; |
3 | use core::alloc::Allocator; |
4 | |
5 | impl<'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 | |
22 | impl<'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 | |
75 | impl<'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 | |