1 use super::map::MIN_LEN;
2 use super::node::{marker, ForceResult::*, Handle, LeftOrRight::*, NodeRef, Root};
4 impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
5 /// Stocks up a possibly underfull node by merging with or stealing from a
6 /// sibling. If succesful but at the cost of shrinking the parent node,
7 /// returns that shrunk parent node. Returns an `Err` if the node is
9 fn fix_node_through_parent(
11 ) -> Result<Option<NodeRef<marker::Mut<'a>, K, V, marker::Internal>>, Self> {
16 match self.choose_parent_kv() {
17 Ok(Left(mut left_parent_kv)) => {
18 if left_parent_kv.can_merge() {
19 let parent = left_parent_kv.merge_tracking_parent();
22 left_parent_kv.bulk_steal_left(MIN_LEN - len);
26 Ok(Right(mut right_parent_kv)) => {
27 if right_parent_kv.can_merge() {
28 let parent = right_parent_kv.merge_tracking_parent();
31 right_parent_kv.bulk_steal_right(MIN_LEN - len);
47 impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
48 /// Stocks up a possibly underfull node, and if that causes its parent node
49 /// to shrink, stocks up the parent, recursively.
50 /// Returns `true` if it fixed the tree, `false` if it couldn't because the
51 /// root node became empty.
53 /// This method does not expect ancestors to already be underfull upon entry
54 /// and panics if it encounters an empty ancestor.
55 pub fn fix_node_and_affected_ancestors(mut self) -> bool {
57 match self.fix_node_through_parent() {
58 Ok(Some(parent)) => self = parent.forget_type(),
59 Ok(None) => return true,
60 Err(_) => return false,
66 impl<K, V> Root<K, V> {
67 /// Removes empty levels on the top, but keeps an empty leaf if the entire tree is empty.
68 pub fn fix_top(&mut self) {
69 while self.height() > 0 && self.len() == 0 {
70 self.pop_internal_level();
74 /// Stocks up or merge away any underfull nodes on the right border of the
75 /// tree. The other nodes, those that are not the root nor a rightmost edge,
76 /// must already have at least MIN_LEN elements.
77 pub fn fix_right_border(&mut self) {
80 self.borrow_mut().last_kv().fix_right_border_of_right_edge();
85 /// The symmetric clone of `fix_right_border`.
86 pub fn fix_left_border(&mut self) {
89 self.borrow_mut().first_kv().fix_left_border_of_left_edge();
94 /// Stock up any underfull nodes on the right border of the tree.
95 /// The other nodes, those that are not the root nor a rightmost edge,
96 /// must be prepared to have up to MIN_LEN elements stolen.
97 pub fn fix_right_border_of_plentiful(&mut self) {
98 let mut cur_node = self.borrow_mut();
99 while let Internal(internal) = cur_node.force() {
100 // Check if right-most child is underfull.
101 let mut last_kv = internal.last_kv().consider_for_balancing();
102 debug_assert!(last_kv.left_child_len() >= MIN_LEN * 2);
103 let right_child_len = last_kv.right_child_len();
104 if right_child_len < MIN_LEN {
106 last_kv.bulk_steal_left(MIN_LEN - right_child_len);
110 cur_node = last_kv.into_right_child();
115 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV> {
116 fn fix_left_border_of_left_edge(mut self) {
117 while let Internal(internal_kv) = self.force() {
118 self = internal_kv.fix_left_child().first_kv();
119 debug_assert!(self.reborrow().into_node().len() > MIN_LEN);
123 fn fix_right_border_of_right_edge(mut self) {
124 while let Internal(internal_kv) = self.force() {
125 self = internal_kv.fix_right_child().last_kv();
126 debug_assert!(self.reborrow().into_node().len() > MIN_LEN);
131 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
132 /// Stocks up the left child, assuming the right child isn't underfull, and
133 /// provisions an extra element to allow merging its children in turn
134 /// without becoming underfull.
135 /// Returns the left child.
136 fn fix_left_child(self) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
137 let mut internal_kv = self.consider_for_balancing();
138 let left_len = internal_kv.left_child_len();
139 debug_assert!(internal_kv.right_child_len() >= MIN_LEN);
140 if internal_kv.can_merge() {
141 internal_kv.merge_tracking_child()
143 // `MIN_LEN + 1` to avoid readjust if merge happens on the next level.
144 let count = (MIN_LEN + 1).saturating_sub(left_len);
146 internal_kv.bulk_steal_right(count);
148 internal_kv.into_left_child()
152 /// Stocks up the right child, assuming the left child isn't underfull, and
153 /// provisions an extra element to allow merging its children in turn
154 /// without becoming underfull.
155 /// Returns wherever the right child ended up.
156 fn fix_right_child(self) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
157 let mut internal_kv = self.consider_for_balancing();
158 let right_len = internal_kv.right_child_len();
159 debug_assert!(internal_kv.left_child_len() >= MIN_LEN);
160 if internal_kv.can_merge() {
161 internal_kv.merge_tracking_child()
163 // `MIN_LEN + 1` to avoid readjust if merge happens on the next level.
164 let count = (MIN_LEN + 1).saturating_sub(right_len);
166 internal_kv.bulk_steal_left(count);
168 internal_kv.into_right_child()