summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorbors <bors@rust-lang.org>2020-08-15 05:43:00 +0000
committerbors <bors@rust-lang.org>2020-08-15 05:43:00 +0000
commitf7aac25850b68ead13831e7c4605dcc7d07e4e9b (patch)
treed4bc36a2011171aa47796b7622e623aabf44347f
parentAuto merge of #75549 - tmandry:rollup-sxjwa0w, r=tmandry (diff)
parentReverts the fundamental changes in #74762 and #75257 (diff)
downloadrust-master.tar.gz
rust-master.tar.bz2
rust-master.tar.xz
Auto merge of #75488 - ssomers:btree_revert_75257, r=Mark-SimulacrumHEADmaster
Revert the fundamental changes in #74762 and #75257 Before possibly going over to #75487. Also contains some added and fixed comments. r? @Mark-Simulacrum
-rw-r--r--library/alloc/src/collections/btree/map.rs69
1 files changed, 20 insertions, 49 deletions
diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs
index b22eb1f..c6b5584 100644
--- a/library/alloc/src/collections/btree/map.rs
+++ b/library/alloc/src/collections/btree/map.rs
@@ -1,5 +1,3 @@
1// ignore-tidy-filelength
2
3use core::borrow::Borrow; 1use core::borrow::Borrow;
4use core::cmp::Ordering; 2use core::cmp::Ordering;
5use core::fmt::{self, Debug}; 3use core::fmt::{self, Debug};
@@ -1288,11 +1286,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
1288 pub(super) fn drain_filter_inner(&mut self) -> DrainFilterInner<'_, K, V> { 1286 pub(super) fn drain_filter_inner(&mut self) -> DrainFilterInner<'_, K, V> {
1289 let root_node = self.root.as_mut().map(|r| r.node_as_mut()); 1287 let root_node = self.root.as_mut().map(|r| r.node_as_mut());
1290 let front = root_node.map(|rn| rn.first_leaf_edge()); 1288 let front = root_node.map(|rn| rn.first_leaf_edge());
1291 DrainFilterInner { 1289 DrainFilterInner { length: &mut self.length, cur_leaf_edge: front }
1292 length: &mut self.length,
1293 cur_leaf_edge: front,
1294 emptied_internal_root: false,
1295 }
1296 } 1290 }
1297 1291
1298 /// Calculates the number of elements if it is incorrect. 1292 /// Calculates the number of elements if it is incorrect.
@@ -1708,7 +1702,6 @@ where
1708pub(super) struct DrainFilterInner<'a, K: 'a, V: 'a> { 1702pub(super) struct DrainFilterInner<'a, K: 'a, V: 'a> {
1709 length: &'a mut usize, 1703 length: &'a mut usize,
1710 cur_leaf_edge: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>, 1704 cur_leaf_edge: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
1711 emptied_internal_root: bool,
1712} 1705}
1713 1706
1714#[unstable(feature = "btree_drain_filter", issue = "70530")] 1707#[unstable(feature = "btree_drain_filter", issue = "70530")]
@@ -1749,17 +1742,6 @@ where
1749 } 1742 }
1750} 1743}
1751 1744
1752impl<K, V> Drop for DrainFilterInner<'_, K, V> {
1753 fn drop(&mut self) {
1754 if self.emptied_internal_root {
1755 if let Some(handle) = self.cur_leaf_edge.take() {
1756 let root = handle.into_node().into_root_mut();
1757 root.pop_internal_level();
1758 }
1759 }
1760 }
1761}
1762
1763impl<'a, K: 'a, V: 'a> DrainFilterInner<'a, K, V> { 1745impl<'a, K: 'a, V: 'a> DrainFilterInner<'a, K, V> {
1764 /// Allow Debug implementations to predict the next element. 1746 /// Allow Debug implementations to predict the next element.
1765 pub(super) fn peek(&self) -> Option<(&K, &V)> { 1747 pub(super) fn peek(&self) -> Option<(&K, &V)> {
@@ -1776,7 +1758,7 @@ impl<'a, K: 'a, V: 'a> DrainFilterInner<'a, K, V> {
1776 let (k, v) = kv.kv_mut(); 1758 let (k, v) = kv.kv_mut();
1777 if pred(k, v) { 1759 if pred(k, v) {
1778 *self.length -= 1; 1760 *self.length -= 1;
1779 let (kv, pos) = kv.remove_kv_tracking(|_| self.emptied_internal_root = true); 1761 let (kv, pos) = kv.remove_kv_tracking();
1780 self.cur_leaf_edge = Some(pos); 1762 self.cur_leaf_edge = Some(pos);
1781 return Some(kv); 1763 return Some(kv);
1782 } 1764 }
@@ -2799,39 +2781,32 @@ impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
2799 fn remove_kv(self) -> (K, V) { 2781 fn remove_kv(self) -> (K, V) {
2800 *self.length -= 1; 2782 *self.length -= 1;
2801 2783
2802 let (old_kv, _) = 2784 let (old_kv, _) = self.handle.remove_kv_tracking();
2803 self.handle.remove_kv_tracking(|root| root.into_root_mut().pop_internal_level());
2804 old_kv 2785 old_kv
2805 } 2786 }
2806} 2787}
2807 2788
2808impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV> { 2789impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV> {
2809 /// Removes a key/value-pair from the tree, and returns that pair, as well as 2790 /// Removes a key/value-pair from the map, and returns that pair, as well as
2810 /// the leaf edge corresponding to that former pair. It's possible this leaves 2791 /// the leaf edge corresponding to that former pair.
2811 /// an empty internal root node, which the caller should subsequently pop from 2792 fn remove_kv_tracking(
2812 /// the map holding the tree. The caller should also decrement the map's length.
2813 fn remove_kv_tracking<F>(
2814 self, 2793 self,
2815 handle_emptied_internal_root: F, 2794 ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
2816 ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>)
2817 where
2818 F: FnOnce(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
2819 {
2820 let (old_kv, mut pos, was_internal) = match self.force() { 2795 let (old_kv, mut pos, was_internal) = match self.force() {
2821 Leaf(leaf) => { 2796 Leaf(leaf) => {
2822 let (old_kv, pos) = leaf.remove(); 2797 let (old_kv, pos) = leaf.remove();
2823 (old_kv, pos, false) 2798 (old_kv, pos, false)
2824 } 2799 }
2825 Internal(mut internal) => { 2800 Internal(mut internal) => {
2826 // Replace the location freed in the internal node with the next KV, 2801 // Replace the location freed in the internal node with an
2827 // and remove that next KV from its leaf. 2802 // adjacent KV, and remove that adjacent KV from its leaf.
2803 // Always choose the adjacent KV on the left side because
2804 // it is typically faster to pop an element from the end
2805 // of the KV arrays without needing to shift other elements.
2828 2806
2829 let key_loc = internal.kv_mut().0 as *mut K; 2807 let key_loc = internal.kv_mut().0 as *mut K;
2830 let val_loc = internal.kv_mut().1 as *mut V; 2808 let val_loc = internal.kv_mut().1 as *mut V;
2831 2809
2832 // Deleting from the left side is typically faster since we can
2833 // just pop an element from the end of the KV array without
2834 // needing to shift the other values.
2835 let to_remove = internal.left_edge().descend().last_leaf_edge().left_kv().ok(); 2810 let to_remove = internal.left_edge().descend().last_leaf_edge().left_kv().ok();
2836 let to_remove = unsafe { unwrap_unchecked(to_remove) }; 2811 let to_remove = unsafe { unwrap_unchecked(to_remove) };
2837 2812
@@ -2867,8 +2842,8 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInter
2867 if parent.len() == 0 { 2842 if parent.len() == 0 {
2868 // The parent that was just emptied must be the root, 2843 // The parent that was just emptied must be the root,
2869 // because nodes on a lower level would not have been 2844 // because nodes on a lower level would not have been
2870 // left underfull. It has to be popped off the tree soon. 2845 // left with a single child.
2871 handle_emptied_internal_root(parent); 2846 parent.into_root_mut().pop_internal_level();
2872 break; 2847 break;
2873 } else { 2848 } else {
2874 cur_node = parent.forget_type(); 2849 cur_node = parent.forget_type();
@@ -2972,19 +2947,15 @@ fn handle_underfull_node<K, V>(
2972 Err(_) => return AtRoot, 2947 Err(_) => return AtRoot,
2973 }; 2948 };
2974 2949
2950 // Prefer the left KV if it exists. Merging with the left side is faster,
2951 // since merging happens towards the left and `node` has fewer elements.
2952 // Stealing from the left side is faster, since we can pop from the end of
2953 // the KV arrays.
2975 let (is_left, mut handle) = match parent.left_kv() { 2954 let (is_left, mut handle) = match parent.left_kv() {
2976 Ok(left) => (true, left), 2955 Ok(left) => (true, left),
2977 Err(parent) => { 2956 Err(parent) => {
2978 match parent.right_kv() { 2957 let right = unsafe { unwrap_unchecked(parent.right_kv().ok()) };
2979 Ok(right) => (false, right), 2958 (false, right)
2980 Err(_) => {
2981 // The underfull node has an empty parent, so it is the only child
2982 // of an empty root. It is destined to become the new root, thus
2983 // allowed to be underfull. The empty parent should be removed later
2984 // by `pop_internal_level`.
2985 return AtRoot;
2986 }
2987 }
2988 } 2959 }
2989 }; 2960 };
2990 2961