library/alloc/src/collections/btree/fix.rs

   1 use super::map::MIN_LEN;
   2 use super::node::{marker, ForceResult::*, Handle, LeftOrRight::*, NodeRef, Root};
   3
   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 successful but at the cost of shrinking the parent node,
   7     /// returns that shrunk parent node. Returns an `Err` if the node is
   8     /// an empty root.
   9     fn fix_node_through_parent(
  10         self,
  11     ) -> Result<Option<NodeRef<marker::Mut<'a>, K, V, marker::Internal>>, Self> {
  12         let len = self.len();
  13         if len >= MIN_LEN {
  14             Ok(None)
  15         } else {
  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();
  20                         Ok(Some(parent))
  21                     } else {
  22                         left_parent_kv.bulk_steal_left(MIN_LEN - len);
  23                         Ok(None)
  24                     }
  25                 }
  26                 Ok(Right(mut right_parent_kv)) => {
  27                     if right_parent_kv.can_merge() {
  28                         let parent = right_parent_kv.merge_tracking_parent();
  29                         Ok(Some(parent))
  30                     } else {
  31                         right_parent_kv.bulk_steal_right(MIN_LEN - len);
  32                         Ok(None)
  33                     }
  34                 }
  35                 Err(root) => {
  36                     if len > 0 {
  37                         Ok(None)
  38                     } else {
  39                         Err(root)
  40                     }
  41                 }
  42             }
  43         }
  44     }
  45 }
  46
  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.
  52     ///
  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 {
  56         loop {
  57             match self.fix_node_through_parent() {
  58                 Ok(Some(parent)) => self = parent.forget_type(),
  59                 Ok(None) => return true,
  60                 Err(_) => return false,
  61             }
  62         }
  63     }
  64 }
  65
  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();
  71         }
  72     }
  73
  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) {
  78         self.fix_top();
  79         if self.len() > 0 {
  80             self.borrow_mut().last_kv().fix_right_border_of_right_edge();
  81             self.fix_top();
  82         }
  83     }
  84
  85     /// The symmetric clone of `fix_right_border`.
  86     pub fn fix_left_border(&mut self) {
  87         self.fix_top();
  88         if self.len() > 0 {
  89             self.borrow_mut().first_kv().fix_left_border_of_left_edge();
  90             self.fix_top();
  91         }
  92     }
  93
  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 {
 105                 // We need to steal.
 106                 last_kv.bulk_steal_left(MIN_LEN - right_child_len);
 107             }
 108
 109             // Go further down.
 110             cur_node = last_kv.into_right_child();
 111         }
 112     }
 113 }
 114
 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);
 120         }
 121     }
 122
 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);
 127         }
 128     }
 129 }
 130
 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()
 142         } else {
 143             // `MIN_LEN + 1` to avoid readjust if merge happens on the next level.
 144             let count = (MIN_LEN + 1).saturating_sub(left_len);
 145             if count > 0 {
 146                 internal_kv.bulk_steal_right(count);
 147             }
 148             internal_kv.into_left_child()
 149         }
 150     }
 151
 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()
 162         } else {
 163             // `MIN_LEN + 1` to avoid readjust if merge happens on the next level.
 164             let count = (MIN_LEN + 1).saturating_sub(right_len);
 165             if count > 0 {
 166                 internal_kv.bulk_steal_left(count);
 167             }
 168             internal_kv.into_right_child()
 169         }
 170     }
 171 }