1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
use super::map::MIN_LEN;
use super::node::{ForceResult::*, Root};
use super::search::SearchResult::*;
use core::borrow::Borrow;

impl<K, V> Root<K, V> {
    pub fn split_off<Q: ?Sized + Ord>(&mut self, right_root: &mut Self, key: &Q)
    where
        K: Borrow<Q>,
    {
        debug_assert!(right_root.height() == 0);
        debug_assert!(right_root.len() == 0);

        let left_root = self;
        for _ in 0..left_root.height() {
            right_root.push_internal_level();
        }

        {
            let mut left_node = left_root.borrow_mut();
            let mut right_node = right_root.borrow_mut();

            loop {
                let mut split_edge = match left_node.search_node(key) {
                    // key is going to the right tree
                    Found(kv) => kv.left_edge(),
                    GoDown(edge) => edge,
                };

                split_edge.move_suffix(&mut right_node);

                match (split_edge.force(), right_node.force()) {
                    (Internal(edge), Internal(node)) => {
                        left_node = edge.descend();
                        right_node = node.first_edge().descend();
                    }
                    (Leaf(_), Leaf(_)) => {
                        break;
                    }
                    _ => unreachable!(),
                }
            }
        }

        left_root.fix_right_border();
        right_root.fix_left_border();
    }

    /// Removes empty levels on the top, but keeps an empty leaf if the entire tree is empty.
    fn fix_top(&mut self) {
        while self.height() > 0 && self.len() == 0 {
            self.pop_internal_level();
        }
    }

    /// Stock up or merge away any underfull nodes on the right border of the
    /// tree. The other nodes, those that are not the root nor a rightmost edge,
    /// must already have at least MIN_LEN elements.
    fn fix_right_border(&mut self) {
        self.fix_top();

        {
            let mut cur_node = self.borrow_mut();

            while let Internal(node) = cur_node.force() {
                let mut last_kv = node.last_kv().consider_for_balancing();

                if last_kv.can_merge() {
                    cur_node = last_kv.merge_tracking_child();
                } else {
                    let right_len = last_kv.right_child_len();
                    // `MIN_LEN + 1` to avoid readjust if merge happens on the next level.
                    if right_len < MIN_LEN + 1 {
                        last_kv.bulk_steal_left(MIN_LEN + 1 - right_len);
                    }
                    cur_node = last_kv.into_right_child();
                }
                debug_assert!(cur_node.len() > MIN_LEN);
            }
        }

        self.fix_top();
    }

    /// The symmetric clone of `fix_right_border`.
    fn fix_left_border(&mut self) {
        self.fix_top();

        {
            let mut cur_node = self.borrow_mut();

            while let Internal(node) = cur_node.force() {
                let mut first_kv = node.first_kv().consider_for_balancing();

                if first_kv.can_merge() {
                    cur_node = first_kv.merge_tracking_child();
                } else {
                    let left_len = first_kv.left_child_len();
                    // `MIN_LEN + 1` to avoid readjust if merge happens on the next level.
                    if left_len < MIN_LEN + 1 {
                        first_kv.bulk_steal_right(MIN_LEN + 1 - left_len);
                    }
                    cur_node = first_kv.into_left_child();
                }
                debug_assert!(cur_node.len() > MIN_LEN);
            }
        }

        self.fix_top();
    }
}