diff options
| -rw-r--r-- | compiler/rustc_macros/src/query.rs | 4 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/query/mod.rs | 1 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/query/mod.rs | 1 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/query/plumbing.rs | 4 | ||||
| -rw-r--r-- | compiler/rustc_query_system/src/query/config.rs | 3 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/map.rs | 24 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/split.rs | 85 |
7 files changed, 72 insertions, 50 deletions
diff --git a/compiler/rustc_macros/src/query.rs b/compiler/rustc_macros/src/query.rs index cff8e983318..bd20c7689ea 100644 --- a/compiler/rustc_macros/src/query.rs +++ b/compiler/rustc_macros/src/query.rs @@ -417,8 +417,8 @@ fn add_query_description_impl( fn describe( #tcx: TyCtxt<'tcx>, #key: #arg, - ) -> Cow<'static, str> { - ::rustc_middle::ty::print::with_no_trimmed_paths(|| format!(#desc).into()) + ) -> String { + ::rustc_middle::ty::print::with_no_trimmed_paths(|| format!(#desc)) } }; diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs index a3040f498ce..f0166ec2167 100644 --- a/compiler/rustc_middle/src/query/mod.rs +++ b/compiler/rustc_middle/src/query/mod.rs @@ -13,7 +13,6 @@ use rustc_hir::def_id::{CrateNum, DefId, LocalDefId}; use rustc_query_system::query::QueryDescription; use rustc_span::symbol::Symbol; -use std::borrow::Cow; fn describe_as_module(def_id: LocalDefId, tcx: TyCtxt<'_>) -> String { if def_id.is_top_level_module() { diff --git a/compiler/rustc_middle/src/ty/query/mod.rs b/compiler/rustc_middle/src/ty/query/mod.rs index f580cb14dc9..804c045a690 100644 --- a/compiler/rustc_middle/src/ty/query/mod.rs +++ b/compiler/rustc_middle/src/ty/query/mod.rs @@ -53,7 +53,6 @@ use rustc_ast as ast; use rustc_attr as attr; use rustc_span::symbol::Symbol; use rustc_span::{Span, DUMMY_SP}; -use std::borrow::Cow; use std::collections::BTreeMap; use std::ops::Deref; use std::path::PathBuf; diff --git a/compiler/rustc_middle/src/ty/query/plumbing.rs b/compiler/rustc_middle/src/ty/query/plumbing.rs index d0730bd121c..46addcdaead 100644 --- a/compiler/rustc_middle/src/ty/query/plumbing.rs +++ b/compiler/rustc_middle/src/ty/query/plumbing.rs @@ -277,14 +277,14 @@ macro_rules! define_queries { } } - pub fn describe(&self, tcx: TyCtxt<$tcx>) -> Cow<'static, str> { + pub fn describe(&self, tcx: TyCtxt<$tcx>) -> String { let (r, name) = match *self { $(Query::$name(key) => { (queries::$name::describe(tcx, key), stringify!($name)) })* }; if tcx.sess.verbose() { - format!("{} [{}]", r, name).into() + format!("{} [{}]", r, name) } else { r } diff --git a/compiler/rustc_query_system/src/query/config.rs b/compiler/rustc_query_system/src/query/config.rs index 0f0684b3547..94e906fc433 100644 --- a/compiler/rustc_query_system/src/query/config.rs +++ b/compiler/rustc_query_system/src/query/config.rs @@ -7,7 +7,6 @@ use crate::query::plumbing::CycleError; use crate::query::{QueryContext, QueryState}; use rustc_data_structures::fingerprint::Fingerprint; -use std::borrow::Cow; use std::fmt::Debug; use std::hash::Hash; @@ -95,7 +94,7 @@ pub trait QueryAccessors<CTX: QueryContext>: QueryConfig { } pub trait QueryDescription<CTX: QueryContext>: QueryAccessors<CTX> { - fn describe(tcx: CTX, key: Self::Key) -> Cow<'static, str>; + fn describe(tcx: CTX, key: Self::Key) -> String; #[inline] fn cache_on_disk(_: CTX, _: &Self::Key, _: Option<&Self::Value>) -> bool { diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index c26388a1db1..dc109875726 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -20,6 +20,14 @@ use Entry::*; /// We might temporarily have fewer elements during methods. pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT; +// A tree in a `BTreeMap` is a tree in the `node` module with addtional invariants: +// - Keys must appear in ascending order (according to the key's type). +// - If the root node is internal, it must contain at least 1 element. +// - Every non-root node contains at least MIN_LEN elements. +// +// An empty map may be represented both by the absense of a root node or by a +// root node that is an empty leaf. + /// A map based on a B-Tree. /// /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing @@ -1131,20 +1139,12 @@ impl<K, V> BTreeMap<K, V> { let total_num = self.len(); let left_root = self.root.as_mut().unwrap(); // unwrap succeeds because not empty - let mut right = Self::new(); - let right_root = Self::ensure_is_owned(&mut right.root); - - left_root.split_off(right_root, key); + let right_root = left_root.split_off(key); - if left_root.height() < right_root.height() { - self.length = left_root.reborrow().calc_length(); - right.length = total_num - self.len(); - } else { - right.length = right_root.reborrow().calc_length(); - self.length = total_num - right.len(); - } + let (new_left_len, right_len) = Root::calc_split_length(total_num, &left_root, &right_root); + self.length = new_left_len; - right + BTreeMap { root: Some(right_root), length: right_len } } /// Creates an iterator that visits all elements (key-value pairs) in diff --git a/library/alloc/src/collections/btree/split.rs b/library/alloc/src/collections/btree/split.rs index 62c5e3a46d7..1921982464a 100644 --- a/library/alloc/src/collections/btree/split.rs +++ b/library/alloc/src/collections/btree/split.rs @@ -4,46 +4,71 @@ 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) + /// Calculates the length of both trees that result from splitting up + /// a given number of distinct key-value pairs. + pub fn calc_split_length( + total_num: usize, + root_a: &Root<K, V>, + root_b: &Root<K, V>, + ) -> (usize, usize) { + let (length_a, length_b); + if root_a.height() < root_b.height() { + length_a = root_a.reborrow().calc_length(); + length_b = total_num - length_a; + debug_assert_eq!(length_b, root_b.reborrow().calc_length()); + } else { + length_b = root_b.reborrow().calc_length(); + length_a = total_num - length_b; + debug_assert_eq!(length_a, root_a.reborrow().calc_length()); + } + (length_a, length_b) + } + + /// Split off a tree with key-value pairs at and after the given key. + /// The result is meaningful only if the tree is ordered by key, + /// and if the ordering of `Q` corresponds to that of `K`. + /// If `self` respects all `BTreeMap` tree invariants, then both + /// `self` and the returned tree will respect those invariants. + pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self 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!(), + let mut right_root = Root::new_pillar(left_root.height()); + 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(); + right_root + } + + /// Creates a tree consisting of empty nodes. + fn new_pillar(height: usize) -> Self { + let mut root = Root::new(); + for _ in 0..height { + root.push_internal_level(); + } + root } /// Removes empty levels on the top, but keeps an empty leaf if the entire tree is empty. |