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

   1 use super::map::MIN_LEN;
   2 use super::node::{ForceResult::*, Root};
   3 use super::search::{search_node, SearchResult::*};
   4 use core::borrow::Borrow;
   5
   6 impl<K, V> Root<K, V> {
   7     pub fn split_off<Q: ?Sized + Ord>(&mut self, right_root: &mut Self, key: &Q)
   8     where
   9         K: Borrow<Q>,
  10     {
  11         debug_assert!(right_root.height() == 0);
  12         debug_assert!(right_root.len() == 0);
  13
  14         let left_root = self;
  15         for _ in 0..left_root.height() {
  16             right_root.push_internal_level();
  17         }
  18
  19         {
  20             let mut left_node = left_root.borrow_mut();
  21             let mut right_node = right_root.borrow_mut();
  22
  23             loop {
  24                 let mut split_edge = match search_node(left_node, key) {
  25                     // key is going to the right tree
  26                     Found(handle) => handle.left_edge(),
  27                     GoDown(handle) => handle,
  28                 };
  29
  30                 split_edge.move_suffix(&mut right_node);
  31
  32                 match (split_edge.force(), right_node.force()) {
  33                     (Internal(edge), Internal(node)) => {
  34                         left_node = edge.descend();
  35                         right_node = node.first_edge().descend();
  36                     }
  37                     (Leaf(_), Leaf(_)) => {
  38                         break;
  39                     }
  40                     _ => unreachable!(),
  41                 }
  42             }
  43         }
  44
  45         left_root.fix_right_border();
  46         right_root.fix_left_border();
  47     }
  48
  49     /// Removes empty levels on the top, but keeps an empty leaf if the entire tree is empty.
  50     fn fix_top(&mut self) {
  51         while self.height() > 0 && self.len() == 0 {
  52             self.pop_internal_level();
  53         }
  54     }
  55
  56     fn fix_right_border(&mut self) {
  57         self.fix_top();
  58
  59         {
  60             let mut cur_node = self.borrow_mut();
  61
  62             while let Internal(node) = cur_node.force() {
  63                 let mut last_kv = node.last_kv().consider_for_balancing();
  64
  65                 if last_kv.can_merge() {
  66                     cur_node = last_kv.merge(None).into_node();
  67                 } else {
  68                     let right_len = last_kv.right_child_len();
  69                     // `MIN_LEN + 1` to avoid readjust if merge happens on the next level.
  70                     if right_len < MIN_LEN + 1 {
  71                         last_kv.bulk_steal_left(MIN_LEN + 1 - right_len);
  72                     }
  73                     cur_node = last_kv.into_right_child();
  74                 }
  75             }
  76         }
  77
  78         self.fix_top();
  79     }
  80
  81     /// The symmetric clone of `fix_right_border`.
  82     fn fix_left_border(&mut self) {
  83         self.fix_top();
  84
  85         {
  86             let mut cur_node = self.borrow_mut();
  87
  88             while let Internal(node) = cur_node.force() {
  89                 let mut first_kv = node.first_kv().consider_for_balancing();
  90
  91                 if first_kv.can_merge() {
  92                     cur_node = first_kv.merge(None).into_node();
  93                 } else {
  94                     let left_len = first_kv.left_child_len();
  95                     // `MIN_LEN + 1` to avoid readjust if merge happens on the next level.
  96                     if left_len < MIN_LEN + 1 {
  97                         first_kv.bulk_steal_right(MIN_LEN + 1 - left_len);
  98                     }
  99                     cur_node = first_kv.into_left_child();
 100                 }
 101             }
 102         }
 103
 104         self.fix_top();
 105     }
 106 }