X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=library%2Falloc%2Fsrc%2Fcollections%2Fbtree%2Fmap.rs;h=c8b944d90a4eb0cec47382f6bc79f3e26491461a;hb=8668e5b29e78732cb4f4bb84e838fdace70fa3c0;hp=7e27aeb85392c05c813c7d63e9eb26294e2785fc;hpb=3038ecb07b8e549abcc6c7fe1d83faa21fdafb99;p=rust.git diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 7e27aeb8539..c8b944d90a4 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -1,15 +1,13 @@ -// ignore-tidy-filelength - 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::*}; @@ -154,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!(), }; @@ -210,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 } } } @@ -223,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() @@ -242,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 } @@ -565,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, } @@ -592,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, } @@ -617,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. @@ -643,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, @@ -694,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. @@ -720,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, @@ -805,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, } @@ -899,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(), @@ -995,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 { @@ -1041,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 { @@ -1071,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 }) } @@ -1083,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. @@ -1133,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(); @@ -1201,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) { @@ -1280,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. @@ -1315,7 +1316,7 @@ 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. @@ -1701,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")] @@ -1742,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)> { @@ -1769,7 +1758,7 @@ 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 (kv, pos) = kv.remove_kv_tracking(|_| self.emptied_internal_root = true); + let (kv, pos) = kv.remove_kv_tracking(); self.cur_leaf_edge = Some(pos); return Some(kv); } @@ -2251,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 { @@ -2283,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 }, @@ -2792,39 +2781,32 @@ pub fn remove(self) -> V { fn remove_kv(self) -> (K, V) { *self.length -= 1; - let (old_kv, _) = - self.handle.remove_kv_tracking(|root| root.into_root_mut().pop_internal_level()); + let (old_kv, _) = self.handle.remove_kv_tracking(); old_kv } } 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( + /// 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, - handle_emptied_internal_root: F, - ) -> ((K, V), Handle, K, V, marker::Leaf>, marker::Edge>) - where - F: FnOnce(NodeRef, K, V, marker::Internal>), - { + ) -> ((K, V), Handle, K, V, marker::Leaf>, marker::Edge>) { let (old_kv, mut pos, was_internal) = match self.force() { Leaf(leaf) => { 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) }; @@ -2860,8 +2842,8 @@ fn remove_kv_tracking( if parent.len() == 0 { // The parent that was just emptied must be the root, // because nodes on a lower level would not have been - // left underfull. It has to be popped off the tree soon. - handle_emptied_internal_root(parent); + // left with a single child. + parent.into_root_mut().pop_internal_level(); break; } else { cur_node = parent.forget_type(); @@ -2895,7 +2877,7 @@ fn remove_kv_tracking( 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(); } } @@ -2904,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(); @@ -2930,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(); @@ -2965,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) } };