rune_alloc/btree/
fix.rs

Help
1use crate::alloc::Allocator;
2
3use super::map::MIN_LEN;
4use super::node::{marker, ForceResult::*, Handle, LeftOrRight::*, NodeRef, Root};
5
6impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
7    /// Stocks up a possibly underfull node by merging with or stealing from a
8    /// sibling. If successful but at the cost of shrinking the parent node,
9    /// returns that shrunk parent node. Returns an `Err` if the node is
10    /// an empty root.
11    fn fix_node_through_parent<A: Allocator>(
12        self,
13        alloc: &A,
14    ) -> Result<Option<NodeRef<marker::Mut<'a>, K, V, marker::Internal>>, Self> {
15        let len = self.len();
16        if len >= MIN_LEN {
17            Ok(None)
18        } else {
19            match self.choose_parent_kv() {
20                Ok(Left(mut left_parent_kv)) => {
21                    if left_parent_kv.can_merge() {
22                        let parent = left_parent_kv.merge_tracking_parent(alloc);
23                        Ok(Some(parent))
24                    } else {
25                        left_parent_kv.bulk_steal_left(MIN_LEN - len);
26                        Ok(None)
27                    }
28                }
29                Ok(Right(mut right_parent_kv)) => {
30                    if right_parent_kv.can_merge() {
31                        let parent = right_parent_kv.merge_tracking_parent(alloc);
32                        Ok(Some(parent))
33                    } else {
34                        right_parent_kv.bulk_steal_right(MIN_LEN - len);
35                        Ok(None)
36                    }
37                }
38                Err(root) => {
39                    if len > 0 {
40                        Ok(None)
41                    } else {
42                        Err(root)
43                    }
44                }
45            }
46        }
47    }
48}
49
50impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
51    /// Stocks up a possibly underfull node, and if that causes its parent node
52    /// to shrink, stocks up the parent, recursively.
53    /// Returns `true` if it fixed the tree, `false` if it couldn't because the
54    /// root node became empty.
55    ///
56    /// This method does not expect ancestors to already be underfull upon entry
57    /// and panics if it encounters an empty ancestor.
58    pub(crate) fn fix_node_and_affected_ancestors<A: Allocator>(mut self, alloc: &A) -> bool {
59        loop {
60            match self.fix_node_through_parent(alloc) {
61                Ok(Some(parent)) => self = parent.forget_type(),
62                Ok(None) => return true,
63                Err(_) => return false,
64            }
65        }
66    }
67}
68
69impl<K, V> Root<K, V> {
70    /// Removes empty levels on the top, but keeps an empty leaf if the entire tree is empty.
71    pub(crate) fn fix_top<A: Allocator>(&mut self, alloc: &A) {
72        while self.height() > 0 && self.len() == 0 {
73            self.pop_internal_level(alloc);
74        }
75    }
76
77    /// Stocks up or merge away any underfull nodes on the right border of the
78    /// tree. The other nodes, those that are not the root nor a rightmost edge,
79    /// must already have at least MIN_LEN elements.
80    pub(crate) fn fix_right_border<A: Allocator>(&mut self, alloc: &A) {
81        self.fix_top(alloc);
82        if self.len() > 0 {
83            self.borrow_mut()
84                .last_kv()
85                .fix_right_border_of_right_edge(alloc);
86            self.fix_top(alloc);
87        }
88    }
89
90    /// The symmetric clone of `fix_right_border`.
91    pub(crate) fn fix_left_border<A: Allocator>(&mut self, alloc: &A) {
92        self.fix_top(alloc);
93        if self.len() > 0 {
94            self.borrow_mut()
95                .first_kv()
96                .fix_left_border_of_left_edge(alloc);
97            self.fix_top(alloc);
98        }
99    }
100
101    /// Stocks up any underfull nodes on the right border of the tree.
102    /// The other nodes, those that are neither the root nor a rightmost edge,
103    /// must be prepared to have up to MIN_LEN elements stolen.
104    pub(crate) fn fix_right_border_of_plentiful(&mut self) {
105        let mut cur_node = self.borrow_mut();
106        while let Internal(internal) = cur_node.force() {
107            // Check if right-most child is underfull.
108            let mut last_kv = internal.last_kv().consider_for_balancing();
109            debug_assert!(last_kv.left_child_len() >= MIN_LEN * 2);
110            let right_child_len = last_kv.right_child_len();
111            if right_child_len < MIN_LEN {
112                // We need to steal.
113                last_kv.bulk_steal_left(MIN_LEN - right_child_len);
114            }
115
116            // Go further down.
117            cur_node = last_kv.into_right_child();
118        }
119    }
120}
121
122impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV> {
123    fn fix_left_border_of_left_edge<A: Allocator>(mut self, alloc: &A) {
124        while let Internal(internal_kv) = self.force() {
125            self = internal_kv.fix_left_child(alloc).first_kv();
126            debug_assert!(self.reborrow().into_node().len() > MIN_LEN);
127        }
128    }
129
130    fn fix_right_border_of_right_edge<A: Allocator>(mut self, alloc: &A) {
131        while let Internal(internal_kv) = self.force() {
132            self = internal_kv.fix_right_child(alloc).last_kv();
133            debug_assert!(self.reborrow().into_node().len() > MIN_LEN);
134        }
135    }
136}
137
138impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
139    /// Stocks up the left child, assuming the right child isn't underfull, and
140    /// provisions an extra element to allow merging its children in turn
141    /// without becoming underfull.
142    /// Returns the left child.
143    fn fix_left_child<A: Allocator>(
144        self,
145        alloc: &A,
146    ) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
147        let mut internal_kv = self.consider_for_balancing();
148        let left_len = internal_kv.left_child_len();
149        debug_assert!(internal_kv.right_child_len() >= MIN_LEN);
150        if internal_kv.can_merge() {
151            internal_kv.merge_tracking_child(alloc)
152        } else {
153            // `MIN_LEN + 1` to avoid readjust if merge happens on the next level.
154            let count = (MIN_LEN + 1).saturating_sub(left_len);
155            if count > 0 {
156                internal_kv.bulk_steal_right(count);
157            }
158            internal_kv.into_left_child()
159        }
160    }
161
162    /// Stocks up the right child, assuming the left child isn't underfull, and
163    /// provisions an extra element to allow merging its children in turn
164    /// without becoming underfull.
165    /// Returns wherever the right child ended up.
166    fn fix_right_child<A: Allocator>(
167        self,
168        alloc: &A,
169    ) -> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
170        let mut internal_kv = self.consider_for_balancing();
171        let right_len = internal_kv.right_child_len();
172        debug_assert!(internal_kv.left_child_len() >= MIN_LEN);
173        if internal_kv.can_merge() {
174            internal_kv.merge_tracking_child(alloc)
175        } else {
176            // `MIN_LEN + 1` to avoid readjust if merge happens on the next level.
177            let count = (MIN_LEN + 1).saturating_sub(right_len);
178            if count > 0 {
179                internal_kv.bulk_steal_left(count);
180            }
181            internal_kv.into_right_child()
182        }
183    }
184}
rune_alloc/btree/fix.rs

rune_alloc/btree/
fix.rs
