From df76cf89add1454f2ec2f11810120b90367b6921 Mon Sep 17 00:00:00 2001 From: Stein Somers Date: Sun, 9 Aug 2020 12:25:20 +0200 Subject: BTreeMap: admit the existence of leaf edges in comments --- library/alloc/src/collections/btree/node.rs | 34 ++++++++++------------------- 1 file changed, 12 insertions(+), 22 deletions(-) (limited to 'library/alloc') diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index c3f27c10599..b39a1b6fd6a 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -9,11 +9,8 @@ // struct Node { // keys: [K; 2 * B - 1], // vals: [V; 2 * B - 1], -// edges: if height > 0 { -// [Box>; 2 * B] -// } else { () }, -// parent: Option>>, -// parent_idx: u16, +// edges: [if height > 0 { Box> } else { () }; 2 * B], +// parent: Option<(NonNull>, u16)>, // len: u16, // } // ``` @@ -28,8 +25,8 @@ // // - Trees must have uniform depth/height. This means that every path down to a leaf from a // given node has exactly the same length. -// - A node of length `n` has `n` keys, `n` values, and (in an internal node) `n + 1` edges. -// This implies that even an empty internal node has at least one edge. +// - A node of length `n` has `n` keys, `n` values, and `n + 1` edges. +// This implies that even an empty node has at least one edge. use core::cmp::Ordering; use core::marker::PhantomData; @@ -298,9 +295,8 @@ impl<'a, K, V> NodeRef, K, V, marker::Internal> { } impl NodeRef { - /// Finds the length of the node. This is the number of keys or values. In an - /// internal node, the number of edges is `len() + 1`. - /// For any node, the number of possible edge handles is also `len() + 1`. + /// Finds the length of the node. This is the number of keys or values. + /// The number of edges is `len() + 1`. /// Note that, despite being safe, calling this function can have the side effect /// of invalidating mutable references that unsafe code has created. pub fn len(&self) -> usize { @@ -321,9 +317,6 @@ impl NodeRef { } /// Exposes the leaf portion of any leaf or internal node. - /// If the node is a leaf, this function simply opens up its data. - /// If the node is an internal node, so not a leaf, it does have all the data a leaf has - /// (header, keys and values), and this function exposes that. /// /// Returns a raw ptr to avoid invalidating other references to this node, /// which is possible when BorrowType is marker::ValMut. @@ -471,9 +464,6 @@ impl<'a, K, V, Type> NodeRef, K, V, Type> { } /// Exposes the leaf portion of any leaf or internal node for writing. - /// If the node is a leaf, this function simply opens up its data. - /// If the node is an internal node, so not a leaf, it does have all the data a leaf has - /// (header, keys and values), and this function exposes that. /// /// We don't need to return a raw ptr because we have unique access to the entire node. fn as_leaf_mut(&mut self) -> &'a mut LeafNode { @@ -679,9 +669,9 @@ impl<'a, K: 'a, V: 'a> NodeRef, K, V, marker::Internal> { } impl<'a, K: 'a, V: 'a> NodeRef, K, V, marker::LeafOrInternal> { - /// Removes a key/value pair from the end of this node and returns the pair. - /// If this is an internal node, also removes the edge that was to the right - /// of that pair and returns the orphaned node that this edge owned. + /// Removes a key/value pair from the end of the node and returns the pair. + /// Also removes the edge that was to the right of that pair and, if the node + /// is internal, returns the orphaned subtree that this edge owned. fn pop(&mut self) -> (K, V, Option>) { debug_assert!(self.len() > 0); @@ -705,9 +695,9 @@ impl<'a, K: 'a, V: 'a> NodeRef, K, V, marker::LeafOrInternal> { } } - /// Removes a key/value pair from the beginning of this node and returns the pair. - /// If this is an internal node, also removes the edge that was to the left - /// of that pair and returns the orphaned node that this edge owned. + /// Removes a key/value pair from the beginning of the node and returns the pair. + /// Also removes the edge that was to the left of that pair and, if the node is + /// internal, returns the orphaned subtree that this edge owned. fn pop_front(&mut self) -> (K, V, Option>) { debug_assert!(self.len() > 0); -- cgit 1.4.1-3-g733a5 From d71d13e82d5a7cb3037a70d2ac18453db6dacca7 Mon Sep 17 00:00:00 2001 From: Stein Somers Date: Sat, 26 Sep 2020 20:46:44 +0200 Subject: BTreeMap: refactoring around edges, missed spots --- library/alloc/src/collections/btree/node.rs | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'library/alloc') diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index c3f27c10599..9c8ba72e8e6 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -484,7 +484,7 @@ impl<'a, K, V, Type> NodeRef, K, V, Type> { /// /// # Safety /// The node has more than `idx` initialized elements. - pub unsafe fn key_mut_at(&mut self, idx: usize) -> &mut K { + unsafe fn key_mut_at(&mut self, idx: usize) -> &mut K { unsafe { self.reborrow_mut().into_key_mut_at(idx) } } @@ -492,7 +492,7 @@ impl<'a, K, V, Type> NodeRef, K, V, Type> { /// /// # Safety /// The node has more than `idx` initialized elements. - pub unsafe fn val_mut_at(&mut self, idx: usize) -> &mut V { + unsafe fn val_mut_at(&mut self, idx: usize) -> &mut V { unsafe { self.reborrow_mut().into_val_mut_at(idx) } } @@ -655,7 +655,7 @@ impl<'a, K: 'a, V: 'a> NodeRef, K, V, marker::Internal> { /// Adds a key/value pair, and an edge to go to the left of that pair, /// to the beginning of the node. - pub fn push_front(&mut self, key: K, val: V, edge: Root) { + fn push_front(&mut self, key: K, val: V, edge: Root) { assert!(edge.height == self.height - 1); assert!(self.len() < CAPACITY); @@ -1011,18 +1011,18 @@ impl<'a, K: 'a, V: 'a> Handle, K, V, marker::Internal>, let (middle_kv_idx, insertion) = splitpoint(self.idx); let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) }; let (mut left, k, v, mut right) = middle.split(); - match insertion { + let mut insertion_edge = match insertion { InsertionPlace::Left(insert_idx) => unsafe { - Handle::new_edge(left.reborrow_mut(), insert_idx).insert_fit(key, val, edge); + Handle::new_edge(left.reborrow_mut(), insert_idx) }, InsertionPlace::Right(insert_idx) => unsafe { Handle::new_edge( right.node_as_mut().cast_unchecked::(), insert_idx, ) - .insert_fit(key, val, edge); }, - } + }; + insertion_edge.insert_fit(key, val, edge); InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }) } } -- cgit 1.4.1-3-g733a5 From d74b8e0505b83c72761987c48f3aa3fbb2656573 Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Sat, 3 Oct 2020 16:51:43 -0700 Subject: Replace some once(x).chain(once(y)) with [x, y] IntoIter Now that we have by-value array iterators... --- compiler/rustc_hir/src/def.rs | 4 +--- compiler/rustc_trait_selection/src/lib.rs | 1 + compiler/rustc_trait_selection/src/traits/object_safety.rs | 4 ++-- compiler/rustc_typeck/src/astconv/mod.rs | 4 ++-- compiler/rustc_typeck/src/lib.rs | 1 + library/alloc/src/collections/vec_deque.rs | 5 +++-- library/alloc/src/lib.rs | 1 + 7 files changed, 11 insertions(+), 9 deletions(-) (limited to 'library/alloc') diff --git a/compiler/rustc_hir/src/def.rs b/compiler/rustc_hir/src/def.rs index 96fde48d96c..62b12542877 100644 --- a/compiler/rustc_hir/src/def.rs +++ b/compiler/rustc_hir/src/def.rs @@ -341,9 +341,7 @@ impl PerNS> { /// Returns an iterator over the items which are `Some`. pub fn present_items(self) -> impl Iterator { - use std::iter::once; - - once(self.type_ns).chain(once(self.value_ns)).chain(once(self.macro_ns)).filter_map(|it| it) + IntoIter::new([self.type_ns, self.value_ns, self.macro_ns]).filter_map(|it| it) } } diff --git a/compiler/rustc_trait_selection/src/lib.rs b/compiler/rustc_trait_selection/src/lib.rs index ddeab340f38..406e8936e6e 100644 --- a/compiler/rustc_trait_selection/src/lib.rs +++ b/compiler/rustc_trait_selection/src/lib.rs @@ -11,6 +11,7 @@ //! This API is completely unstable and subject to change. #![doc(html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/")] +#![feature(array_value_iter)] #![feature(bool_to_option)] #![feature(box_patterns)] #![feature(drain_filter)] diff --git a/compiler/rustc_trait_selection/src/traits/object_safety.rs b/compiler/rustc_trait_selection/src/traits/object_safety.rs index 2f2ac9f094d..8fc14cb2997 100644 --- a/compiler/rustc_trait_selection/src/traits/object_safety.rs +++ b/compiler/rustc_trait_selection/src/traits/object_safety.rs @@ -24,6 +24,7 @@ use rustc_span::symbol::Symbol; use rustc_span::Span; use smallvec::SmallVec; +use std::array; use std::iter; pub use crate::traits::{MethodViolationCode, ObjectSafetyViolation}; @@ -652,8 +653,7 @@ fn receiver_is_dispatchable<'tcx>( let caller_bounds: Vec> = param_env .caller_bounds() .iter() - .chain(iter::once(unsize_predicate)) - .chain(iter::once(trait_predicate)) + .chain(array::IntoIter::new([unsize_predicate, trait_predicate])) .collect(); ty::ParamEnv::new(tcx.intern_predicates(&caller_bounds), param_env.reveal()) diff --git a/compiler/rustc_typeck/src/astconv/mod.rs b/compiler/rustc_typeck/src/astconv/mod.rs index 46b8b2e14c7..170ca2ce744 100644 --- a/compiler/rustc_typeck/src/astconv/mod.rs +++ b/compiler/rustc_typeck/src/astconv/mod.rs @@ -35,8 +35,8 @@ use rustc_trait_selection::traits::error_reporting::report_object_safety_error; use rustc_trait_selection::traits::wf::object_region_bounds; use smallvec::SmallVec; +use std::array; use std::collections::BTreeSet; -use std::iter; use std::slice; #[derive(Debug)] @@ -1346,7 +1346,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o { debug!("one_bound_for_assoc_type: bound2 = {:?}", bound2); let is_equality = is_equality(); - let bounds = iter::once(bound).chain(iter::once(bound2)).chain(matching_candidates); + let bounds = array::IntoIter::new([bound, bound2]).chain(matching_candidates); let mut err = if is_equality.is_some() { // More specific Error Index entry. struct_span_err!( diff --git a/compiler/rustc_typeck/src/lib.rs b/compiler/rustc_typeck/src/lib.rs index 21fb92ec889..7efda54fbe0 100644 --- a/compiler/rustc_typeck/src/lib.rs +++ b/compiler/rustc_typeck/src/lib.rs @@ -56,6 +56,7 @@ This API is completely unstable and subject to change. */ #![doc(html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/")] +#![feature(array_value_iter)] #![feature(bool_to_option)] #![feature(box_syntax)] #![feature(crate_visibility_modifier)] diff --git a/library/alloc/src/collections/vec_deque.rs b/library/alloc/src/collections/vec_deque.rs index 8e9acc42d9a..adb08543334 100644 --- a/library/alloc/src/collections/vec_deque.rs +++ b/library/alloc/src/collections/vec_deque.rs @@ -9,10 +9,11 @@ // ignore-tidy-filelength +use core::array; use core::cmp::{self, Ordering}; use core::fmt; use core::hash::{Hash, Hasher}; -use core::iter::{once, repeat_with, FromIterator, FusedIterator}; +use core::iter::{repeat_with, FromIterator, FusedIterator}; use core::mem::{self, replace, ManuallyDrop}; use core::ops::{Index, IndexMut, Range, RangeBounds, Try}; use core::ptr::{self, NonNull}; @@ -99,7 +100,7 @@ impl<'a, 'b, T> PairSlices<'a, 'b, T> { } fn remainder(self) -> impl Iterator { - once(self.b0).chain(once(self.b1)) + array::IntoIter::new([self.b0, self.b1]) } } diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs index b33cb3ad8e8..046c3867d84 100644 --- a/library/alloc/src/lib.rs +++ b/library/alloc/src/lib.rs @@ -77,6 +77,7 @@ #![cfg_attr(test, feature(new_uninit))] #![feature(allocator_api)] #![feature(array_chunks)] +#![feature(array_value_iter)] #![feature(array_windows)] #![feature(allow_internal_unstable)] #![feature(arbitrary_self_types)] -- cgit 1.4.1-3-g733a5