X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=library%2Falloc%2Fsrc%2Fcollections%2Fbtree%2Fmap.rs;h=c8b944d90a4eb0cec47382f6bc79f3e26491461a;hb=8668e5b29e78732cb4f4bb84e838fdace70fa3c0;hp=6184051316ef801584398bd5083d8d2b02229967;hpb=f042d749b0fc212bff6bdc44b84e134b878bff64;p=rust.git diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 6184051316e..c8b944d90a4 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -1,13 +1,13 @@ use core::borrow::Borrow; use core::cmp::Ordering; -use core::fmt::Debug; +use core::fmt::{self, Debug}; use core::hash::{Hash, Hasher}; use core::iter::{FromIterator, FusedIterator, Peekable}; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop}; use core::ops::Bound::{Excluded, Included, Unbounded}; use core::ops::{Index, RangeBounds}; -use core::{fmt, ptr}; +use core::ptr; use super::node::{self, marker, ForceResult::*, Handle, InsertResult::*, NodeRef}; use super::search::{self, SearchResult::*}; @@ -152,7 +152,7 @@ fn clone_subtree<'a, K: Clone, V: Clone>( { let root = out_tree.root.as_mut().unwrap(); // unwrap succeeds because we just wrapped - let mut out_node = match root.as_mut().force() { + let mut out_node = match root.node_as_mut().force() { Leaf(leaf) => leaf, Internal(_) => unreachable!(), }; @@ -208,7 +208,7 @@ fn clone_subtree<'a, K: Clone, V: Clone>( // Ord` constraint, which this method lacks. BTreeMap { root: None, length: 0 } } else { - clone_subtree(self.root.as_ref().unwrap().as_ref()) // unwrap succeeds because not empty + clone_subtree(self.root.as_ref().unwrap().node_as_ref()) // unwrap succeeds because not empty } } } @@ -221,14 +221,16 @@ impl super::Recover for BTreeMap type Key = K; fn get(&self, key: &Q) -> Option<&K> { - match search::search_tree(self.root.as_ref()?.as_ref(), key) { + let root_node = self.root.as_ref()?.node_as_ref(); + match search::search_tree(root_node, key) { Found(handle) => Some(handle.into_kv().0), GoDown(_) => None, } } fn take(&mut self, key: &Q) -> Option { - match search::search_tree(self.root.as_mut()?.as_mut(), key) { + let root_node = self.root.as_mut()?.node_as_mut(); + match search::search_tree(root_node, key) { Found(handle) => Some( OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData } .remove_kv() @@ -240,7 +242,7 @@ fn take(&mut self, key: &Q) -> Option { fn replace(&mut self, key: K) -> Option { let root = Self::ensure_is_owned(&mut self.root); - match search::search_tree::, K, (), K>(root.as_mut(), &key) { + match search::search_tree::, K, (), K>(root.node_as_mut(), &key) { Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)), GoDown(handle) => { VacantEntry { key, handle, length: &mut self.length, _marker: PhantomData } @@ -355,6 +357,30 @@ pub struct ValuesMut<'a, K: 'a, V: 'a> { inner: IterMut<'a, K, V>, } +/// An owning iterator over the keys of a `BTreeMap`. +/// +/// This `struct` is created by the [`into_keys`] method on [`BTreeMap`]. +/// See its documentation for more. +/// +/// [`into_keys`]: BTreeMap::into_keys +#[unstable(feature = "map_into_keys_values", issue = "75294")] +#[derive(Debug)] +pub struct IntoKeys { + inner: IntoIter, +} + +/// An owning iterator over the values of a `BTreeMap`. +/// +/// This `struct` is created by the [`into_values`] method on [`BTreeMap`]. +/// See its documentation for more. +/// +/// [`into_values`]: BTreeMap::into_values +#[unstable(feature = "map_into_keys_values", issue = "75294")] +#[derive(Debug)] +pub struct IntoValues { + inner: IntoIter, +} + /// An iterator over a sub-range of entries in a `BTreeMap`. /// /// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its @@ -539,7 +565,8 @@ pub fn get(&self, key: &Q) -> Option<&V> K: Borrow, Q: Ord, { - match search::search_tree(self.root.as_ref()?.as_ref(), key) { + let root_node = self.root.as_ref()?.node_as_ref(); + match search::search_tree(root_node, key) { Found(handle) => Some(handle.into_kv().1), GoDown(_) => None, } @@ -566,7 +593,8 @@ pub fn get_key_value(&self, k: &Q) -> Option<(&K, &V)> K: Borrow, Q: Ord, { - match search::search_tree(self.root.as_ref()?.as_ref(), k) { + let root_node = self.root.as_ref()?.node_as_ref(); + match search::search_tree(root_node, k) { Found(handle) => Some(handle.into_kv()), GoDown(_) => None, } @@ -591,8 +619,8 @@ pub fn get_key_value(&self, k: &Q) -> Option<(&K, &V)> /// ``` #[unstable(feature = "map_first_last", issue = "62924")] pub fn first_key_value(&self) -> Option<(&K, &V)> { - let front = self.root.as_ref()?.as_ref().first_leaf_edge(); - front.right_kv().ok().map(Handle::into_kv) + let root_node = self.root.as_ref()?.node_as_ref(); + root_node.first_leaf_edge().right_kv().ok().map(Handle::into_kv) } /// Returns the first entry in the map for in-place manipulation. @@ -617,8 +645,8 @@ pub fn first_key_value(&self) -> Option<(&K, &V)> { /// ``` #[unstable(feature = "map_first_last", issue = "62924")] pub fn first_entry(&mut self) -> Option> { - let front = self.root.as_mut()?.as_mut().first_leaf_edge(); - let kv = front.right_kv().ok()?; + let root_node = self.root.as_mut()?.node_as_mut(); + let kv = root_node.first_leaf_edge().right_kv().ok()?; Some(OccupiedEntry { handle: kv.forget_node_type(), length: &mut self.length, @@ -668,8 +696,8 @@ pub fn pop_first(&mut self) -> Option<(K, V)> { /// ``` #[unstable(feature = "map_first_last", issue = "62924")] pub fn last_key_value(&self) -> Option<(&K, &V)> { - let back = self.root.as_ref()?.as_ref().last_leaf_edge(); - back.left_kv().ok().map(Handle::into_kv) + let root_node = self.root.as_ref()?.node_as_ref(); + root_node.last_leaf_edge().left_kv().ok().map(Handle::into_kv) } /// Returns the last entry in the map for in-place manipulation. @@ -694,8 +722,8 @@ pub fn last_key_value(&self) -> Option<(&K, &V)> { /// ``` #[unstable(feature = "map_first_last", issue = "62924")] pub fn last_entry(&mut self) -> Option> { - let back = self.root.as_mut()?.as_mut().last_leaf_edge(); - let kv = back.left_kv().ok()?; + let root_node = self.root.as_mut()?.node_as_mut(); + let kv = root_node.last_leaf_edge().left_kv().ok()?; Some(OccupiedEntry { handle: kv.forget_node_type(), length: &mut self.length, @@ -779,7 +807,8 @@ pub fn get_mut(&mut self, key: &Q) -> Option<&mut V> K: Borrow, Q: Ord, { - match search::search_tree(self.root.as_mut()?.as_mut(), key) { + let root_node = self.root.as_mut()?.node_as_mut(); + match search::search_tree(root_node, key) { Found(handle) => Some(handle.into_kv_mut().1), GoDown(_) => None, } @@ -873,7 +902,8 @@ pub fn remove_entry(&mut self, key: &Q) -> Option<(K, V)> K: Borrow, Q: Ord, { - match search::search_tree(self.root.as_mut()?.as_mut(), key) { + let root_node = self.root.as_mut()?.node_as_mut(); + match search::search_tree(root_node, key) { Found(handle) => Some( OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData } .remove_entry(), @@ -969,7 +999,7 @@ pub fn range(&self, range: R) -> Range<'_, K, V> R: RangeBounds, { if let Some(root) = &self.root { - let (f, b) = range_search(root.as_ref(), range); + let (f, b) = range_search(root.node_as_ref(), range); Range { front: Some(f), back: Some(b) } } else { @@ -1015,7 +1045,7 @@ pub fn range_mut(&mut self, range: R) -> RangeMut<'_, K, V> R: RangeBounds, { if let Some(root) = &mut self.root { - let (f, b) = range_search(root.as_mut(), range); + let (f, b) = range_search(root.node_as_mut(), range); RangeMut { front: Some(f), back: Some(b), _marker: PhantomData } } else { @@ -1045,7 +1075,7 @@ pub fn range_mut(&mut self, range: R) -> RangeMut<'_, K, V> pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { // FIXME(@porglezomp) Avoid allocating if we don't insert let root = Self::ensure_is_owned(&mut self.root); - match search::search_tree(root.as_mut(), &key) { + match search::search_tree(root.node_as_mut(), &key) { Found(handle) => { Occupied(OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData }) } @@ -1057,7 +1087,7 @@ pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { fn from_sorted_iter>(&mut self, iter: I) { let root = Self::ensure_is_owned(&mut self.root); - let mut cur_node = root.as_mut().last_leaf_edge().into_node(); + let mut cur_node = root.node_as_mut().last_leaf_edge().into_node(); // Iterate through all key-value pairs, pushing them into nodes at the right level. for (key, value) in iter { // Try to push key-value pair into the current leaf node. @@ -1107,7 +1137,7 @@ fn from_sorted_iter>(&mut self, iter: I) { fn fix_right_edge(root: &mut node::Root) { // Handle underfull nodes, start from the top. - let mut cur_node = root.as_mut(); + let mut cur_node = root.node_as_mut(); while let Internal(internal) = cur_node.force() { // Check if right-most child is underfull. let mut last_edge = internal.last_edge(); @@ -1175,8 +1205,8 @@ pub fn split_off(&mut self, key: &Q) -> Self } { - let mut left_node = left_root.as_mut(); - let mut right_node = right_root.as_mut(); + let mut left_node = left_root.node_as_mut(); + let mut right_node = right_root.node_as_mut(); loop { let mut split_edge = match search::search_node(left_node, key) { @@ -1254,12 +1284,9 @@ pub fn drain_filter(&mut self, pred: F) -> DrainFilter<'_, K, V, F> DrainFilter { pred, inner: self.drain_filter_inner() } } pub(super) fn drain_filter_inner(&mut self) -> DrainFilterInner<'_, K, V> { - let front = self.root.as_mut().map(|r| r.as_mut().first_leaf_edge()); - DrainFilterInner { - length: &mut self.length, - cur_leaf_edge: front, - emptied_internal_root: false, - } + let root_node = self.root.as_mut().map(|r| r.node_as_mut()); + let front = root_node.map(|rn| rn.first_leaf_edge()); + DrainFilterInner { length: &mut self.length, cur_leaf_edge: front } } /// Calculates the number of elements if it is incorrect. @@ -1289,12 +1316,58 @@ fn dfs<'a, K, V>(node: NodeRef, K, V, marker::LeafOrInternal>) res } - self.length = dfs(self.root.as_ref().unwrap().as_ref()); + self.length = dfs(self.root.as_ref().unwrap().node_as_ref()); + } + + /// Creates a consuming iterator visiting all the keys, in sorted order. + /// The map cannot be used after calling this. + /// The iterator element type is `K`. + /// + /// # Examples + /// + /// ``` + /// #![feature(map_into_keys_values)] + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(2, "b"); + /// a.insert(1, "a"); + /// + /// let keys: Vec = a.into_keys().collect(); + /// assert_eq!(keys, [1, 2]); + /// ``` + #[inline] + #[unstable(feature = "map_into_keys_values", issue = "75294")] + pub fn into_keys(self) -> IntoKeys { + IntoKeys { inner: self.into_iter() } + } + + /// Creates a consuming iterator visiting all the values, in order by key. + /// The map cannot be used after calling this. + /// The iterator element type is `V`. + /// + /// # Examples + /// + /// ``` + /// #![feature(map_into_keys_values)] + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "hello"); + /// a.insert(2, "goodbye"); + /// + /// let values: Vec<&str> = a.into_values().collect(); + /// assert_eq!(values, ["hello", "goodbye"]); + /// ``` + #[inline] + #[unstable(feature = "map_into_keys_values", issue = "75294")] + pub fn into_values(self) -> IntoValues { + IntoValues { inner: self.into_iter() } } } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap { +impl<'a, K, V> IntoIterator for &'a BTreeMap { type Item = (&'a K, &'a V); type IntoIter = Iter<'a, K, V>; @@ -1363,7 +1436,7 @@ fn clone(&self) -> Self { } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap { +impl<'a, K, V> IntoIterator for &'a mut BTreeMap { type Item = (&'a K, &'a mut V); type IntoIter = IterMut<'a, K, V>; @@ -1629,7 +1702,6 @@ pub struct DrainFilter<'a, K, V, F> pub(super) struct DrainFilterInner<'a, K: 'a, V: 'a> { length: &'a mut usize, cur_leaf_edge: Option, K, V, marker::Leaf>, marker::Edge>>, - emptied_internal_root: bool, } #[unstable(feature = "btree_drain_filter", issue = "70530")] @@ -1670,17 +1742,6 @@ fn size_hint(&self) -> (usize, Option) { } } -impl Drop for DrainFilterInner<'_, K, V> { - fn drop(&mut self) { - if self.emptied_internal_root { - if let Some(handle) = self.cur_leaf_edge.take() { - let root = handle.into_node().into_root_mut(); - root.pop_internal_level(); - } - } - } -} - impl<'a, K: 'a, V: 'a> DrainFilterInner<'a, K, V> { /// Allow Debug implementations to predict the next element. pub(super) fn peek(&self) -> Option<(&K, &V)> { @@ -1697,10 +1758,9 @@ pub(super) fn next(&mut self, pred: &mut F) -> Option<(K, V)> let (k, v) = kv.kv_mut(); if pred(k, v) { *self.length -= 1; - let RemoveResult { old_kv, pos, emptied_internal_root } = kv.remove_kv_tracking(); + let (kv, pos) = kv.remove_kv_tracking(); self.cur_leaf_edge = Some(pos); - self.emptied_internal_root |= emptied_internal_root; - return Some(old_kv); + return Some(kv); } self.cur_leaf_edge = Some(kv.next_leaf_edge()); } @@ -1781,6 +1841,82 @@ unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) { } } +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl Iterator for IntoKeys { + type Item = K; + + fn next(&mut self) -> Option { + self.inner.next().map(|(k, _)| k) + } + + fn size_hint(&self) -> (usize, Option) { + self.inner.size_hint() + } + + fn last(mut self) -> Option { + self.next_back() + } + + fn min(mut self) -> Option { + self.next() + } + + fn max(mut self) -> Option { + self.next_back() + } +} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl DoubleEndedIterator for IntoKeys { + fn next_back(&mut self) -> Option { + self.inner.next_back().map(|(k, _)| k) + } +} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl ExactSizeIterator for IntoKeys { + fn len(&self) -> usize { + self.inner.len() + } +} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl FusedIterator for IntoKeys {} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl Iterator for IntoValues { + type Item = V; + + fn next(&mut self) -> Option { + self.inner.next().map(|(_, v)| v) + } + + fn size_hint(&self) -> (usize, Option) { + self.inner.size_hint() + } + + fn last(mut self) -> Option { + self.next_back() + } +} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl DoubleEndedIterator for IntoValues { + fn next_back(&mut self) -> Option { + self.inner.next_back().map(|(_, v)| v) + } +} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl ExactSizeIterator for IntoValues { + fn len(&self) -> usize { + self.inner.len() + } +} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl FusedIterator for IntoValues {} + #[stable(feature = "btree_range", since = "1.17.0")] impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> { fn next_back(&mut self) -> Option<(&'a K, &'a V)> { @@ -2104,7 +2240,7 @@ impl BTreeMap { #[stable(feature = "rust1", since = "1.0.0")] pub fn iter(&self) -> Iter<'_, K, V> { if let Some(root) = &self.root { - let (f, b) = full_range_search(root.as_ref()); + let (f, b) = full_range_search(root.node_as_ref()); Iter { range: Range { front: Some(f), back: Some(b) }, length: self.length } } else { @@ -2136,7 +2272,7 @@ pub fn iter(&self) -> Iter<'_, K, V> { #[stable(feature = "rust1", since = "1.0.0")] pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { if let Some(root) = &mut self.root { - let (f, b) = full_range_search(root.as_mut()); + let (f, b) = full_range_search(root.node_as_mut()); IterMut { range: RangeMut { front: Some(f), back: Some(b), _marker: PhantomData }, @@ -2465,40 +2601,17 @@ pub fn into_key(self) -> K { pub fn insert(self, value: V) -> &'a mut V { *self.length += 1; - let out_ptr; - - let mut ins_k; - let mut ins_v; - let mut ins_edge; - - let mut cur_parent = match self.handle.insert(self.key, value) { - (Fit(handle), _) => return handle.into_kv_mut().1, - (Split(left, k, v, right), ptr) => { - ins_k = k; - ins_v = v; - ins_edge = right; - out_ptr = ptr; - left.ascend().map_err(|n| n.into_root_mut()) + let out_ptr = match self.handle.insert_recursing(self.key, value) { + (Fit(_), val_ptr) => val_ptr, + (Split(ins), val_ptr) => { + let root = ins.left.into_root_mut(); + root.push_internal_level().push(ins.k, ins.v, ins.right); + val_ptr } }; - - loop { - match cur_parent { - Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) { - Fit(_) => return unsafe { &mut *out_ptr }, - Split(left, k, v, right) => { - ins_k = k; - ins_v = v; - ins_edge = right; - cur_parent = left.ascend().map_err(|n| n.into_root_mut()); - } - }, - Err(root) => { - root.push_internal_level().push(ins_k, ins_v, ins_edge); - return unsafe { &mut *out_ptr }; - } - } - } + // Now that we have finished growing the tree using borrowed references, + // dereference the pointer to a part of it, that we picked up along the way. + unsafe { &mut *out_ptr } } } @@ -2668,60 +2781,45 @@ pub fn remove(self) -> V { fn remove_kv(self) -> (K, V) { *self.length -= 1; - let RemoveResult { old_kv, pos, emptied_internal_root } = self.handle.remove_kv_tracking(); - let root = pos.into_node().into_root_mut(); - if emptied_internal_root { - root.pop_internal_level(); - } + let (old_kv, _) = self.handle.remove_kv_tracking(); old_kv } } -struct RemoveResult<'a, K, V> { - // Key and value removed. - old_kv: (K, V), - // Unique location at the leaf level that the removed KV lopgically collapsed into. - pos: Handle, K, V, marker::Leaf>, marker::Edge>, - // Whether the remove left behind and empty internal root node, that should be removed - // using `pop_internal_level`. - emptied_internal_root: bool, -} - impl<'a, K: 'a, V: 'a> Handle, K, V, marker::LeafOrInternal>, marker::KV> { - /// Removes a key/value-pair from the tree, and returns that pair, as well as - /// the leaf edge corresponding to that former pair. It's possible this leaves - /// an empty internal root node, which the caller should subsequently pop from - /// the map holding the tree. The caller should also decrement the map's length. - fn remove_kv_tracking(self) -> RemoveResult<'a, K, V> { - let (mut pos, old_key, old_val, was_internal) = match self.force() { + /// Removes a key/value-pair from the map, and returns that pair, as well as + /// the leaf edge corresponding to that former pair. + fn remove_kv_tracking( + self, + ) -> ((K, V), Handle, K, V, marker::Leaf>, marker::Edge>) { + let (old_kv, mut pos, was_internal) = match self.force() { Leaf(leaf) => { - let (hole, old_key, old_val) = leaf.remove(); - (hole, old_key, old_val, false) + let (old_kv, pos) = leaf.remove(); + (old_kv, pos, false) } Internal(mut internal) => { - // Replace the location freed in the internal node with the next KV, - // and remove that next KV from its leaf. + // Replace the location freed in the internal node with an + // adjacent KV, and remove that adjacent KV from its leaf. + // Always choose the adjacent KV on the left side because + // it is typically faster to pop an element from the end + // of the KV arrays without needing to shift other elements. let key_loc = internal.kv_mut().0 as *mut K; let val_loc = internal.kv_mut().1 as *mut V; - // Deleting from the left side is typically faster since we can - // just pop an element from the end of the KV array without - // needing to shift the other values. let to_remove = internal.left_edge().descend().last_leaf_edge().left_kv().ok(); let to_remove = unsafe { unwrap_unchecked(to_remove) }; - let (hole, key, val) = to_remove.remove(); + let (kv, pos) = to_remove.remove(); - let old_key = unsafe { mem::replace(&mut *key_loc, key) }; - let old_val = unsafe { mem::replace(&mut *val_loc, val) }; + let old_key = unsafe { mem::replace(&mut *key_loc, kv.0) }; + let old_val = unsafe { mem::replace(&mut *val_loc, kv.1) }; - (hole, old_key, old_val, true) + ((old_key, old_val), pos, true) } }; // Handle underflow - let mut emptied_internal_root = false; let mut cur_node = unsafe { ptr::read(&pos).into_node().forget_type() }; let mut at_leaf = true; while cur_node.len() < node::MIN_LEN { @@ -2742,8 +2840,10 @@ fn remove_kv_tracking(self) -> RemoveResult<'a, K, V> { let parent = edge.into_node(); if parent.len() == 0 { - // This empty parent must be the root, and should be popped off the tree. - emptied_internal_root = true; + // The parent that was just emptied must be the root, + // because nodes on a lower level would not have been + // left with a single child. + parent.into_root_mut().pop_internal_level(); break; } else { cur_node = parent.forget_type(); @@ -2770,14 +2870,14 @@ fn remove_kv_tracking(self) -> RemoveResult<'a, K, V> { pos = unsafe { unwrap_unchecked(pos.next_kv().ok()).next_leaf_edge() }; } - RemoveResult { old_kv: (old_key, old_val), pos, emptied_internal_root } + (old_kv, pos) } } impl node::Root { /// Removes empty levels on the top, but keep an empty leaf if the entire tree is empty. fn fix_top(&mut self) { - while self.height() > 0 && self.as_ref().len() == 0 { + while self.height() > 0 && self.node_as_ref().len() == 0 { self.pop_internal_level(); } } @@ -2786,7 +2886,7 @@ fn fix_right_border(&mut self) { self.fix_top(); { - let mut cur_node = self.as_mut(); + let mut cur_node = self.node_as_mut(); while let Internal(node) = cur_node.force() { let mut last_kv = node.last_kv(); @@ -2812,7 +2912,7 @@ fn fix_left_border(&mut self) { self.fix_top(); { - let mut cur_node = self.as_mut(); + let mut cur_node = self.node_as_mut(); while let Internal(node) = cur_node.force() { let mut first_kv = node.first_kv(); @@ -2847,19 +2947,15 @@ fn handle_underfull_node( Err(_) => return AtRoot, }; + // Prefer the left KV if it exists. Merging with the left side is faster, + // since merging happens towards the left and `node` has fewer elements. + // Stealing from the left side is faster, since we can pop from the end of + // the KV arrays. let (is_left, mut handle) = match parent.left_kv() { Ok(left) => (true, left), Err(parent) => { - match parent.right_kv() { - Ok(right) => (false, right), - Err(_) => { - // The underfull node has an empty parent, so it is the only child - // of an empty root. It is destined to become the new root, thus - // allowed to be underfull. The empty parent should be removed later - // by `pop_internal_level`. - return AtRoot; - } - } + let right = unsafe { unwrap_unchecked(parent.right_kv().ok()) }; + (false, right) } };