diff options
Diffstat (limited to 'library/alloc/src/collections')
-rw-r--r-- | library/alloc/src/collections/binary_heap/mod.rs | 91 | ||||
-rw-r--r-- | library/alloc/src/collections/btree/map.rs | 128 | ||||
-rw-r--r-- | library/alloc/src/collections/btree/map/tests.rs | 67 | ||||
-rw-r--r-- | library/alloc/src/collections/btree/mod.rs | 1 | ||||
-rw-r--r-- | library/alloc/src/collections/btree/navigate.rs | 12 | ||||
-rw-r--r-- | library/alloc/src/collections/btree/set.rs | 55 | ||||
-rw-r--r-- | library/alloc/src/collections/btree/set/tests.rs | 1 | ||||
-rw-r--r-- | library/alloc/src/collections/linked_list.rs | 38 | ||||
-rw-r--r-- | library/alloc/src/collections/vec_deque/drain.rs | 40 | ||||
-rw-r--r-- | library/alloc/src/collections/vec_deque/into_iter.rs | 30 | ||||
-rw-r--r-- | library/alloc/src/collections/vec_deque/iter.rs | 33 | ||||
-rw-r--r-- | library/alloc/src/collections/vec_deque/iter_mut.rs | 32 | ||||
-rw-r--r-- | library/alloc/src/collections/vec_deque/mod.rs | 49 |
13 files changed, 412 insertions, 165 deletions
diff --git a/library/alloc/src/collections/binary_heap/mod.rs b/library/alloc/src/collections/binary_heap/mod.rs index f1d0a305d..2c089bb31 100644 --- a/library/alloc/src/collections/binary_heap/mod.rs +++ b/library/alloc/src/collections/binary_heap/mod.rs @@ -144,7 +144,7 @@ #![stable(feature = "rust1", since = "1.0.0")] use core::fmt; -use core::iter::{FromIterator, FusedIterator, InPlaceIterable, SourceIter, TrustedLen}; +use core::iter::{FusedIterator, InPlaceIterable, SourceIter, TrustedLen}; use core::mem::{self, swap, ManuallyDrop}; use core::num::NonZeroUsize; use core::ops::{Deref, DerefMut}; @@ -154,8 +154,6 @@ use crate::collections::TryReserveError; use crate::slice; use crate::vec::{self, AsVecIntoIter, Vec}; -use super::SpecExtend; - #[cfg(test)] mod tests; @@ -265,7 +263,6 @@ mod tests; /// more detailed analysis. /// /// [`core::cmp::Reverse`]: core::cmp::Reverse -/// [`Ord`]: core::cmp::Ord /// [`Cell`]: core::cell::Cell /// [`RefCell`]: core::cell::RefCell /// [push]: BinaryHeap::push @@ -400,6 +397,17 @@ impl<T: fmt::Debug> fmt::Debug for BinaryHeap<T> { } } +struct RebuildOnDrop<'a, T: Ord> { + heap: &'a mut BinaryHeap<T>, + rebuild_from: usize, +} + +impl<'a, T: Ord> Drop for RebuildOnDrop<'a, T> { + fn drop(&mut self) { + self.heap.rebuild_tail(self.rebuild_from); + } +} + impl<T: Ord> BinaryHeap<T> { /// Creates an empty `BinaryHeap` as a max-heap. /// @@ -837,7 +845,6 @@ impl<T: Ord> BinaryHeap<T> { /// Basic usage: /// /// ``` - /// #![feature(binary_heap_retain)] /// use std::collections::BinaryHeap; /// /// let mut heap = BinaryHeap::from([-10, -5, 1, 2, 4, 13]); @@ -846,35 +853,24 @@ impl<T: Ord> BinaryHeap<T> { /// /// assert_eq!(heap.into_sorted_vec(), [-10, 2, 4]) /// ``` - #[unstable(feature = "binary_heap_retain", issue = "71503")] + #[stable(feature = "binary_heap_retain", since = "1.70.0")] pub fn retain<F>(&mut self, mut f: F) where F: FnMut(&T) -> bool, { - struct RebuildOnDrop<'a, T: Ord> { - heap: &'a mut BinaryHeap<T>, - first_removed: usize, - } - - let mut guard = RebuildOnDrop { first_removed: self.len(), heap: self }; - + // rebuild_start will be updated to the first touched element below, and the rebuild will + // only be done for the tail. + let mut guard = RebuildOnDrop { rebuild_from: self.len(), heap: self }; let mut i = 0; + guard.heap.data.retain(|e| { let keep = f(e); - if !keep && i < guard.first_removed { - guard.first_removed = i; + if !keep && i < guard.rebuild_from { + guard.rebuild_from = i; } i += 1; keep }); - - impl<'a, T: Ord> Drop for RebuildOnDrop<'a, T> { - fn drop(&mut self) { - // data[..first_removed] is untouched, so we only need to - // rebuild the tail: - self.heap.rebuild_tail(self.first_removed); - } - } } } @@ -1421,7 +1417,6 @@ impl<T> FusedIterator for Iter<'_, T> {} /// (provided by the [`IntoIterator`] trait). See its documentation for more. /// /// [`into_iter`]: BinaryHeap::into_iter -/// [`IntoIterator`]: core::iter::IntoIterator #[stable(feature = "rust1", since = "1.0.0")] #[derive(Clone)] pub struct IntoIter<T> { @@ -1468,6 +1463,20 @@ impl<T> ExactSizeIterator for IntoIter<T> { #[stable(feature = "fused", since = "1.26.0")] impl<T> FusedIterator for IntoIter<T> {} +#[stable(feature = "default_iters", since = "1.70.0")] +impl<T> Default for IntoIter<T> { + /// Creates an empty `binary_heap::IntoIter`. + /// + /// ``` + /// # use std::collections::binary_heap; + /// let iter: binary_heap::IntoIter<u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + IntoIter { iter: Default::default() } + } +} + // In addition to the SAFETY invariants of the following three unsafe traits // also refer to the vec::in_place_collect module documentation to get an overview #[unstable(issue = "none", feature = "inplace_iteration")] @@ -1715,7 +1724,8 @@ impl<'a, T> IntoIterator for &'a BinaryHeap<T> { impl<T: Ord> Extend<T> for BinaryHeap<T> { #[inline] fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { - <Self as SpecExtend<I>>::spec_extend(self, iter); + let guard = RebuildOnDrop { rebuild_from: self.len(), heap: self }; + guard.heap.data.extend(iter); } #[inline] @@ -1729,37 +1739,6 @@ impl<T: Ord> Extend<T> for BinaryHeap<T> { } } -impl<T: Ord, I: IntoIterator<Item = T>> SpecExtend<I> for BinaryHeap<T> { - default fn spec_extend(&mut self, iter: I) { - self.extend_desugared(iter.into_iter()); - } -} - -impl<T: Ord> SpecExtend<Vec<T>> for BinaryHeap<T> { - fn spec_extend(&mut self, ref mut other: Vec<T>) { - let start = self.data.len(); - self.data.append(other); - self.rebuild_tail(start); - } -} - -impl<T: Ord> SpecExtend<BinaryHeap<T>> for BinaryHeap<T> { - fn spec_extend(&mut self, ref mut other: BinaryHeap<T>) { - self.append(other); - } -} - -impl<T: Ord> BinaryHeap<T> { - fn extend_desugared<I: IntoIterator<Item = T>>(&mut self, iter: I) { - let iterator = iter.into_iter(); - let (lower, _) = iterator.size_hint(); - - self.reserve(lower); - - iterator.for_each(move |elem| self.push(elem)); - } -} - #[stable(feature = "extend_ref", since = "1.2.0")] impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BinaryHeap<T> { fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 386cd1a16..afdc99817 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -3,7 +3,7 @@ use core::borrow::Borrow; use core::cmp::Ordering; use core::fmt::{self, Debug}; use core::hash::{Hash, Hasher}; -use core::iter::{FromIterator, FusedIterator}; +use core::iter::FusedIterator; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop}; use core::ops::{Bound, Index, RangeBounds}; @@ -362,6 +362,20 @@ impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> { } } +#[stable(feature = "default_iters", since = "1.70.0")] +impl<'a, K: 'a, V: 'a> Default for Iter<'a, K, V> { + /// Creates an empty `btree_map::Iter`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::Iter<'_, u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + Iter { range: Default::default(), length: 0 } + } +} + /// A mutable iterator over the entries of a `BTreeMap`. /// /// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its @@ -386,13 +400,26 @@ impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> { } } +#[stable(feature = "default_iters", since = "1.70.0")] +impl<'a, K: 'a, V: 'a> Default for IterMut<'a, K, V> { + /// Creates an empty `btree_map::IterMut`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::IterMut<'_, u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + IterMut { range: Default::default(), length: 0, _marker: PhantomData {} } + } +} + /// An owning iterator over the entries of a `BTreeMap`. /// /// This `struct` is created by the [`into_iter`] method on [`BTreeMap`] /// (provided by the [`IntoIterator`] trait). See its documentation for more. /// /// [`into_iter`]: IntoIterator::into_iter -/// [`IntoIterator`]: core::iter::IntoIterator #[stable(feature = "rust1", since = "1.0.0")] #[rustc_insignificant_dtor] pub struct IntoIter< @@ -421,6 +448,23 @@ impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for IntoIter<K, V, A> { } } +#[stable(feature = "default_iters", since = "1.70.0")] +impl<K, V, A> Default for IntoIter<K, V, A> +where + A: Allocator + Default + Clone, +{ + /// Creates an empty `btree_map::IntoIter`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::IntoIter<u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + IntoIter { range: Default::default(), length: 0, alloc: Default::default() } + } +} + /// An iterator over the keys of a `BTreeMap`. /// /// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its @@ -605,7 +649,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { #[stable(feature = "rust1", since = "1.0.0")] pub fn clear(&mut self) { // avoid moving the allocator - mem::drop(BTreeMap { + drop(BTreeMap { root: mem::replace(&mut self.root, None), length: mem::replace(&mut self.length, 0), alloc: self.alloc.clone(), @@ -1768,6 +1812,20 @@ impl<K, V> Clone for Keys<'_, K, V> { } } +#[stable(feature = "default_iters", since = "1.70.0")] +impl<K, V> Default for Keys<'_, K, V> { + /// Creates an empty `btree_map::Keys`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::Keys<'_, u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + Keys { inner: Default::default() } + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K, V> Iterator for Values<'a, K, V> { type Item = &'a V; @@ -1809,6 +1867,20 @@ impl<K, V> Clone for Values<'_, K, V> { } } +#[stable(feature = "default_iters", since = "1.70.0")] +impl<K, V> Default for Values<'_, K, V> { + /// Creates an empty `btree_map::Values`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::Values<'_, u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + Values { inner: Default::default() } + } +} + /// An iterator produced by calling `drain_filter` on BTreeMap. #[unstable(feature = "btree_drain_filter", issue = "70530")] pub struct DrainFilter< @@ -1945,6 +2017,20 @@ impl<'a, K, V> Iterator for Range<'a, K, V> { } } +#[stable(feature = "default_iters", since = "1.70.0")] +impl<K, V> Default for Range<'_, K, V> { + /// Creates an empty `btree_map::Range`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::Range<'_, u8, u8> = Default::default(); + /// assert_eq!(iter.count(), 0); + /// ``` + fn default() -> Self { + Range { inner: Default::default() } + } +} + #[stable(feature = "map_values_mut", since = "1.10.0")] impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { type Item = &'a mut V; @@ -2021,6 +2107,23 @@ impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoKeys<K, V, A> { #[stable(feature = "map_into_keys_values", since = "1.54.0")] impl<K, V, A: Allocator + Clone> FusedIterator for IntoKeys<K, V, A> {} +#[stable(feature = "default_iters", since = "1.70.0")] +impl<K, V, A> Default for IntoKeys<K, V, A> +where + A: Allocator + Default + Clone, +{ + /// Creates an empty `btree_map::IntoKeys`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::IntoKeys<u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + IntoKeys { inner: Default::default() } + } +} + #[stable(feature = "map_into_keys_values", since = "1.54.0")] impl<K, V, A: Allocator + Clone> Iterator for IntoValues<K, V, A> { type Item = V; @@ -2055,6 +2158,23 @@ impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoValues<K, V, A> { #[stable(feature = "map_into_keys_values", since = "1.54.0")] impl<K, V, A: Allocator + Clone> FusedIterator for IntoValues<K, V, A> {} +#[stable(feature = "default_iters", since = "1.70.0")] +impl<K, V, A> Default for IntoValues<K, V, A> +where + A: Allocator + Default + Clone, +{ + /// Creates an empty `btree_map::IntoValues`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::IntoValues<u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + IntoValues { inner: Default::default() } + } +} + #[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)> { @@ -3062,7 +3182,7 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { panic!("key must be ordered above the current element"); } } - if let Some((next, _)) = self.peek_prev() { + if let Some((next, _)) = self.peek_next() { if &key >= next { panic!("key must be ordered below the next element"); } diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index 76c2f27b4..da00d83bd 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -9,8 +9,7 @@ use crate::testing::ord_chaos::{Cyclic3, Governed, Governor}; use crate::testing::rng::DeterministicRng; use crate::vec::Vec; use std::cmp::Ordering; -use std::convert::TryFrom; -use std::iter::{self, FromIterator}; +use std::iter; use std::mem; use std::ops::Bound::{self, Excluded, Included, Unbounded}; use std::ops::RangeBounds; @@ -2385,3 +2384,67 @@ fn test_cursor_mut() { assert_eq!(cur.key(), Some(&4)); assert_eq!(map, BTreeMap::from([(0, '?'), (1, 'a'), (3, 'c'), (4, 'd')])); } + +#[should_panic(expected = "key must be ordered above the previous element")] +#[test] +fn test_cursor_mut_insert_before_1() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_before(0, 'd'); +} + +#[should_panic(expected = "key must be ordered above the previous element")] +#[test] +fn test_cursor_mut_insert_before_2() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_before(1, 'd'); +} + +#[should_panic(expected = "key must be ordered below the current element")] +#[test] +fn test_cursor_mut_insert_before_3() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_before(2, 'd'); +} + +#[should_panic(expected = "key must be ordered below the current element")] +#[test] +fn test_cursor_mut_insert_before_4() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_before(3, 'd'); +} + +#[should_panic(expected = "key must be ordered above the current element")] +#[test] +fn test_cursor_mut_insert_after_1() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_after(1, 'd'); +} + +#[should_panic(expected = "key must be ordered above the current element")] +#[test] +fn test_cursor_mut_insert_after_2() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_after(2, 'd'); +} + +#[should_panic(expected = "key must be ordered below the next element")] +#[test] +fn test_cursor_mut_insert_after_3() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_after(3, 'd'); +} + +#[should_panic(expected = "key must be ordered below the next element")] +#[test] +fn test_cursor_mut_insert_after_4() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_after(4, 'd'); +} diff --git a/library/alloc/src/collections/btree/mod.rs b/library/alloc/src/collections/btree/mod.rs index 7552f2fc0..c7d0144de 100644 --- a/library/alloc/src/collections/btree/mod.rs +++ b/library/alloc/src/collections/btree/mod.rs @@ -13,7 +13,6 @@ pub mod set; mod set_val; mod split; -#[doc(hidden)] trait Recover<Q: ?Sized> { type Key; diff --git a/library/alloc/src/collections/btree/navigate.rs b/library/alloc/src/collections/btree/navigate.rs index b890717e5..a85a31624 100644 --- a/library/alloc/src/collections/btree/navigate.rs +++ b/library/alloc/src/collections/btree/navigate.rs @@ -19,6 +19,12 @@ impl<'a, K: 'a, V: 'a> Clone for LeafRange<marker::Immut<'a>, K, V> { } } +impl<B, K, V> Default for LeafRange<B, K, V> { + fn default() -> Self { + LeafRange { front: None, back: None } + } +} + impl<BorrowType, K, V> LeafRange<BorrowType, K, V> { pub fn none() -> Self { LeafRange { front: None, back: None } @@ -124,6 +130,12 @@ pub struct LazyLeafRange<BorrowType, K, V> { back: Option<LazyLeafHandle<BorrowType, K, V>>, } +impl<B, K, V> Default for LazyLeafRange<B, K, V> { + fn default() -> Self { + LazyLeafRange { front: None, back: None } + } +} + impl<'a, K: 'a, V: 'a> Clone for LazyLeafRange<marker::Immut<'a>, K, V> { fn clone(&self) -> Self { LazyLeafRange { front: self.front.clone(), back: self.back.clone() } diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs index 4ddb21192..da952a13f 100644 --- a/library/alloc/src/collections/btree/set.rs +++ b/library/alloc/src/collections/btree/set.rs @@ -1,13 +1,10 @@ -// This is pretty much entirely stolen from TreeSet, since BTreeMap has an identical interface -// to TreeMap - use crate::vec::Vec; use core::borrow::Borrow; use core::cmp::Ordering::{self, Equal, Greater, Less}; use core::cmp::{max, min}; use core::fmt::{self, Debug}; use core::hash::{Hash, Hasher}; -use core::iter::{FromIterator, FusedIterator, Peekable}; +use core::iter::{FusedIterator, Peekable}; use core::mem::ManuallyDrop; use core::ops::{BitAnd, BitOr, BitXor, RangeBounds, Sub}; @@ -18,8 +15,6 @@ use super::Recover; use crate::alloc::{Allocator, Global}; -// FIXME(conventions): implement bounded iterators - /// An ordered set based on a B-Tree. /// /// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance @@ -35,7 +30,6 @@ use crate::alloc::{Allocator, Global}; /// Iterators returned by [`BTreeSet::iter`] produce their items in order, and take worst-case /// logarithmic and amortized constant time per item returned. /// -/// [`Ord`]: core::cmp::Ord /// [`Cell`]: core::cell::Cell /// [`RefCell`]: core::cell::RefCell /// @@ -152,7 +146,6 @@ impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { /// (provided by the [`IntoIterator`] trait). See its documentation for more. /// /// [`into_iter`]: BTreeSet#method.into_iter -/// [`IntoIterator`]: core::iter::IntoIterator #[stable(feature = "rust1", since = "1.0.0")] #[derive(Debug)] pub struct IntoIter< @@ -1544,6 +1537,21 @@ impl<T, A: Allocator + Clone> Iterator for IntoIter<T, A> { self.iter.size_hint() } } + +#[stable(feature = "default_iters", since = "1.70.0")] +impl<T> Default for Iter<'_, T> { + /// Creates an empty `btree_set::Iter`. + /// + /// ``` + /// # use std::collections::btree_set; + /// let iter: btree_set::Iter<'_, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + Iter { iter: Default::default() } + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<T, A: Allocator + Clone> DoubleEndedIterator for IntoIter<T, A> { fn next_back(&mut self) -> Option<T> { @@ -1560,6 +1568,23 @@ impl<T, A: Allocator + Clone> ExactSizeIterator for IntoIter<T, A> { #[stable(feature = "fused", since = "1.26.0")] impl<T, A: Allocator + Clone> FusedIterator for IntoIter<T, A> {} +#[stable(feature = "default_iters", since = "1.70.0")] +impl<T, A> Default for IntoIter<T, A> +where + A: Allocator + Default + Clone, +{ + /// Creates an empty `btree_set::IntoIter`. + /// + /// ``` + /// # use std::collections::btree_set; + /// let iter: btree_set::IntoIter<u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + IntoIter { iter: Default::default() } + } +} + #[stable(feature = "btree_range", since = "1.17.0")] impl<T> Clone for Range<'_, T> { fn clone(&self) -> Self { @@ -1598,6 +1623,20 @@ impl<'a, T> DoubleEndedIterator for Range<'a, T> { #[stable(feature = "fused", since = "1.26.0")] impl<T> FusedIterator for Range<'_, T> {} +#[stable(feature = "default_iters", since = "1.70.0")] +impl<T> Default for Range<'_, T> { + /// Creates an empty `btree_set::Range`. + /// + /// ``` + /// # use std::collections::btree_set; + /// let iter: btree_set::Range<'_, u8> = Default::default(); + /// assert_eq!(iter.count(), 0); + /// ``` + fn default() -> Self { + Range { iter: Default::default() } + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<T, A: Allocator + Clone> Clone for Difference<'_, T, A> { fn clone(&self) -> Self { diff --git a/library/alloc/src/collections/btree/set/tests.rs b/library/alloc/src/collections/btree/set/tests.rs index 7b8d41a60..a7c839d77 100644 --- a/library/alloc/src/collections/btree/set/tests.rs +++ b/library/alloc/src/collections/btree/set/tests.rs @@ -4,7 +4,6 @@ use crate::testing::rng::DeterministicRng; use crate::vec::Vec; use std::cmp::Ordering; use std::hash::{Hash, Hasher}; -use std::iter::FromIterator; use std::ops::Bound::{Excluded, Included}; use std::panic::{catch_unwind, AssertUnwindSafe}; diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs index f2f5dffc2..106d05c57 100644 --- a/library/alloc/src/collections/linked_list.rs +++ b/library/alloc/src/collections/linked_list.rs @@ -15,7 +15,7 @@ use core::cmp::Ordering; use core::fmt; use core::hash::{Hash, Hasher}; -use core::iter::{FromIterator, FusedIterator}; +use core::iter::FusedIterator; use core::marker::PhantomData; use core::mem; use core::ptr::NonNull; @@ -130,7 +130,6 @@ impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> { /// (provided by the [`IntoIterator`] trait). See its documentation for more. /// /// [`into_iter`]: LinkedList::into_iter -/// [`IntoIterator`]: core::iter::IntoIterator #[derive(Clone)] #[stable(feature = "rust1", since = "1.0.0")] pub struct IntoIter<T> { @@ -1075,6 +1074,20 @@ impl<T> ExactSizeIterator for Iter<'_, T> {} #[stable(feature = "fused", since = "1.26.0")] impl<T> FusedIterator for Iter<'_, T> {} +#[stable(feature = "default_iters", since = "1.70.0")] +impl<T> Default for Iter<'_, T> { + /// Creates an empty `linked_list::Iter`. + /// + /// ``` + /// # use std::collections::linked_list; + /// let iter: linked_list::Iter<'_, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + Iter { head: None, tail: None, len: 0, marker: Default::default() } + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; @@ -1129,6 +1142,13 @@ impl<T> ExactSizeIterator for IterMut<'_, T> {} #[stable(feature = "fused", since = "1.26.0")] impl<T> FusedIterator for IterMut<'_, T> {} +#[stable(feature = "default_iters", since = "1.70.0")] +impl<T> Default for IterMut<'_, T> { + fn default() -> Self { + IterMut { head: None, tail: None, len: 0, marker: Default::default() } + } +} + /// A cursor over a `LinkedList`. /// /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth. @@ -1808,6 +1828,20 @@ impl<T> ExactSizeIterator for IntoIter<T> {} #[stable(feature = "fused", since = "1.26.0")] impl<T> FusedIterator for IntoIter<T> {} +#[stable(feature = "default_iters", since = "1.70.0")] +impl<T> Default for IntoIter<T> { + /// Creates an empty `linked_list::IntoIter`. + /// + /// ``` + /// # use std::collections::linked_list; + /// let iter: linked_list::IntoIter<u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + LinkedList::new().into_iter() + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<T> FromIterator<T> for LinkedList<T> { fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { diff --git a/library/alloc/src/collections/vec_deque/drain.rs b/library/alloc/src/collections/vec_deque/drain.rs index 89feb361d..0be274a38 100644 --- a/library/alloc/src/collections/vec_deque/drain.rs +++ b/library/alloc/src/collections/vec_deque/drain.rs @@ -52,36 +52,22 @@ impl<'a, T, A: Allocator> Drain<'a, T, A> { } } - // Only returns pointers to the slices, as that's - // all we need to drop them. May only be called if `self.remaining != 0`. + // Only returns pointers to the slices, as that's all we need + // to drop them. May only be called if `self.remaining != 0`. unsafe fn as_slices(&self) -> (*mut [T], *mut [T]) { unsafe { let deque = self.deque.as_ref(); - // FIXME: This is doing almost exactly the same thing as the else branch in `VecDeque::slice_ranges`. - // Unfortunately, we can't just call `slice_ranges` here, as the deque's `len` is currently - // just `drain_start`, so the range check would (almost) always panic. Between temporarily - // adjusting the deques `len` to call `slice_ranges`, and just copy pasting the `slice_ranges` - // implementation, this seemed like the less hacky solution, though it might be good to - // find a better one in the future. - - // because `self.remaining != 0`, we know that `self.idx < deque.original_len`, so it's a valid - // logical index. - let wrapped_start = deque.to_physical_idx(self.idx); - - let head_len = deque.capacity() - wrapped_start; - - let (a_range, b_range) = if head_len >= self.remaining { - (wrapped_start..wrapped_start + self.remaining, 0..0) - } else { - let tail_len = self.remaining - head_len; - (wrapped_start..deque.capacity(), 0..tail_len) - }; - - // SAFETY: the range `self.idx..self.idx+self.remaining` lies strictly inside - // the range `0..deque.original_len`. because of this, and because of the fact - // that we acquire `a_range` and `b_range` exactly like `slice_ranges` would, - // it's guaranteed that `a_range` and `b_range` represent valid ranges into - // the deques buffer. + + // We know that `self.idx + self.remaining <= deque.len <= usize::MAX`, so this won't overflow. + let logical_remaining_range = self.idx..self.idx + self.remaining; + + // SAFETY: `logical_remaining_range` represents the + // range into the logical buffer of elements that + // haven't been drained yet, so they're all initialized, + // and `slice::range(start..end, end) == start..end`, + // so the preconditions for `slice_ranges` are met. + let (a_range, b_range) = + deque.slice_ranges(logical_remaining_range.clone(), logical_remaining_range.end); (deque.buffer_range(a_range), deque.buffer_range(b_range)) } } diff --git a/library/alloc/src/collections/vec_deque/into_iter.rs b/library/alloc/src/collections/vec_deque/into_iter.rs index 34bc0ce91..d9e274df0 100644 --- a/library/alloc/src/collections/vec_deque/into_iter.rs +++ b/library/alloc/src/collections/vec_deque/into_iter.rs @@ -1,4 +1,5 @@ use core::iter::{FusedIterator, TrustedLen}; +use core::num::NonZeroUsize; use core::{array, fmt, mem::MaybeUninit, ops::Try, ptr}; use crate::alloc::{Allocator, Global}; @@ -11,7 +12,6 @@ use super::VecDeque; /// (provided by the [`IntoIterator`] trait). See its documentation for more. /// /// [`into_iter`]: VecDeque::into_iter -/// [`IntoIterator`]: core::iter::IntoIterator #[derive(Clone)] #[stable(feature = "rust1", since = "1.0.0")] pub struct IntoIter< @@ -54,15 +54,16 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { } #[inline] - fn advance_by(&mut self, n: usize) -> Result<(), usize> { - if self.inner.len < n { - let len = self.inner.len; + fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { + let len = self.inner.len; + let rem = if len < n { self.inner.clear(); - Err(len) + n - len } else { self.inner.drain(..n); - Ok(()) - } + 0 + }; + NonZeroUsize::new(rem).map_or(Ok(()), Err) } #[inline] @@ -182,15 +183,16 @@ impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> { } #[inline] - fn advance_back_by(&mut self, n: usize) -> Result<(), usize> { + fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { let len = self.inner.len; - if len >= n { - self.inner.truncate(len - n); - Ok(()) - } else { + let rem = if len < n { self.inner.clear(); - Err(len) - } + n - len + } else { + self.inner.truncate(len - n); + 0 + }; + NonZeroUsize::new(rem).map_or(Ok(()), Err) } fn try_rfold<B, F, R>(&mut self, mut init: B, mut f: F) -> R diff --git a/library/alloc/src/collections/vec_deque/iter.rs b/library/alloc/src/collections/vec_deque/iter.rs index d9f393714..646a2a991 100644 --- a/library/alloc/src/collections/vec_deque/iter.rs +++ b/library/alloc/src/collections/vec_deque/iter.rs @@ -1,4 +1,5 @@ use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce}; +use core::num::NonZeroUsize; use core::ops::Try; use core::{fmt, mem, slice}; @@ -55,13 +56,15 @@ impl<'a, T> Iterator for Iter<'a, T> { } } - fn advance_by(&mut self, n: usize) -> Result<(), usize> { - let m = match self.i1.advance_by(n) { - Ok(_) => return Ok(()), - Err(m) => m, - }; - mem::swap(&mut self.i1, &mut self.i2); - self.i1.advance_by(n - m).map_err(|o| o + m) + fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { + let remaining = self.i1.advance_by(n); + match remaining { + Ok(()) => return Ok(()), + Err(n) => { + mem::swap(&mut self.i1, &mut self.i2); + self.i1.advance_by(n.get()) + } + } } #[inline] @@ -125,14 +128,14 @@ impl<'a, T> DoubleEndedIterator for Iter<'a, T> { } } - fn advance_back_by(&mut self, n: usize) -> Result<(), usize> { - let m = match self.i2.advance_back_by(n) { - Ok(_) => return Ok(()), - Err(m) => m, - }; - - mem::swap(&mut self.i1, &mut self.i2); - self.i2.advance_back_by(n - m).map_err(|o| m + o) + fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { + match self.i2.advance_back_by(n) { + Ok(()) => return Ok(()), + Err(n) => { + mem::swap(&mut self.i1, &mut self.i2); + self.i2.advance_back_by(n.get()) + } + } } fn rfold<Acc, F>(self, accum: Acc, mut f: F) -> Acc diff --git a/library/alloc/src/collections/vec_deque/iter_mut.rs b/library/alloc/src/collections/vec_deque/iter_mut.rs index 2c59d95cd..7defbb109 100644 --- a/library/alloc/src/collections/vec_deque/iter_mut.rs +++ b/library/alloc/src/collections/vec_deque/iter_mut.rs @@ -1,4 +1,5 @@ use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce}; +use core::num::NonZeroUsize; use core::ops::Try; use core::{fmt, mem, slice}; @@ -47,13 +48,14 @@ impl<'a, T> Iterator for IterMut<'a, T> { } } - fn advance_by(&mut self, n: usize) -> Result<(), usize> { - let m = match self.i1.advance_by(n) { - Ok(_) => return Ok(()), - Err(m) => m, - }; - mem::swap(&mut self.i1, &mut self.i2); - self.i1.advance_by(n - m).map_err(|o| o + m) + fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { + match self.i1.advance_by(n) { + Ok(()) => return Ok(()), + Err(remaining) => { + mem::swap(&mut self.i1, &mut self.i2); + self.i1.advance_by(remaining.get()) + } + } } #[inline] @@ -117,14 +119,14 @@ impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { } } - fn advance_back_by(&mut self, n: usize) -> Result<(), usize> { - let m = match self.i2.advance_back_by(n) { - Ok(_) => return Ok(()), - Err(m) => m, - }; - - mem::swap(&mut self.i1, &mut self.i2); - self.i2.advance_back_by(n - m).map_err(|o| m + o) + fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { + match self.i2.advance_back_by(n) { + Ok(()) => return Ok(()), + Err(remaining) => { + mem::swap(&mut self.i1, &mut self.i2); + self.i2.advance_back_by(remaining.get()) + } + } } fn rfold<Acc, F>(self, accum: Acc, mut f: F) -> Acc diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs index 8317ac431..8916b42ed 100644 --- a/library/alloc/src/collections/vec_deque/mod.rs +++ b/library/alloc/src/collections/vec_deque/mod.rs @@ -10,7 +10,7 @@ use core::cmp::{self, Ordering}; use core::fmt; use core::hash::{Hash, Hasher}; -use core::iter::{repeat_n, repeat_with, ByRefSized, FromIterator}; +use core::iter::{repeat_n, repeat_with, ByRefSized}; use core::mem::{ManuallyDrop, SizedTypeProperties}; use core::ops::{Index, IndexMut, Range, RangeBounds}; use core::ptr; @@ -1156,7 +1156,7 @@ impl<T, A: Allocator> VecDeque<T, A> { #[inline] #[stable(feature = "deque_extras_15", since = "1.5.0")] pub fn as_slices(&self) -> (&[T], &[T]) { - let (a_range, b_range) = self.slice_ranges(..); + let (a_range, b_range) = self.slice_ranges(.., self.len); // SAFETY: `slice_ranges` always returns valid ranges into // the physical buffer. unsafe { (&*self.buffer_range(a_range), &*self.buffer_range(b_range)) } @@ -1190,7 +1190,7 @@ impl<T, A: Allocator> VecDeque<T, A> { #[inline] #[stable(feature = "deque_extras_15", since = "1.5.0")] pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) { - let (a_range, b_range) = self.slice_ranges(..); + let (a_range, b_range) = self.slice_ranges(.., self.len); // SAFETY: `slice_ranges` always returns valid ranges into // the physical buffer. unsafe { (&mut *self.buffer_range(a_range), &mut *self.buffer_range(b_range)) } @@ -1232,19 +1232,28 @@ impl<T, A: Allocator> VecDeque<T, A> { /// Given a range into the logical buffer of the deque, this function /// return two ranges into the physical buffer that correspond to - /// the given range. - fn slice_ranges<R>(&self, range: R) -> (Range<usize>, Range<usize>) + /// the given range. The `len` parameter should usually just be `self.len`; + /// the reason it's passed explicitly is that if the deque is wrapped in + /// a `Drain`, then `self.len` is not actually the length of the deque. + /// + /// # Safety + /// + /// This function is always safe to call. For the resulting ranges to be valid + /// ranges into the physical buffer, the caller must ensure that the result of + /// calling `slice::range(range, ..len)` represents a valid range into the + /// logical buffer, and that all elements in that range are initialized. + fn slice_ranges<R>(&self, range: R, len: usize) -> (Range<usize>, Range<usize>) where R: RangeBounds<usize>, { - let Range { start, end } = slice::range(range, ..self.len); + let Range { start, end } = slice::range(range, ..len); let len = end - start; if len == 0 { (0..0, 0..0) } else { - // `slice::range` guarantees that `start <= end <= self.len`. - // because `len != 0`, we know that `start < end`, so `start < self.len` + // `slice::range` guarantees that `start <= end <= len`. + // because `len != 0`, we know that `start < end`, so `start < len` // and the indexing is valid. let wrapped_start = self.to_physical_idx(start); @@ -1290,7 +1299,7 @@ impl<T, A: Allocator> VecDeque<T, A> { where R: RangeBounds<usize>, { - let (a_range, b_range) = self.slice_ranges(range); + let (a_range, b_range) = self.slice_ranges(range, self.len); // SAFETY: The ranges returned by `slice_ranges` // are valid ranges into the physical buffer, so // it's ok to pass them to `buffer_range` and @@ -1330,7 +1339,7 @@ impl<T, A: Allocator> VecDeque<T, A> { where R: RangeBounds<usize>, { - let (a_range, b_range) = self.slice_ranges(range); + let (a_range, b_range) = self.slice_ranges(range, self.len); // SAFETY: The ranges returned by `slice_ranges` // are valid ranges into the physical buffer, so // it's ok to pass them to `buffer_range` and @@ -2385,7 +2394,8 @@ impl<T, A: Allocator> VecDeque<T, A> { } /// Binary searches this `VecDeque` for a given element. - /// This behaves similarly to [`contains`] if this `VecDeque` is sorted. + /// If the `VecDeque` is not sorted, the returned result is unspecified and + /// meaningless. /// /// If the value is found then [`Result::Ok`] is returned, containing the /// index of the matching element. If there are multiple matches, then any @@ -2395,7 +2405,6 @@ impl<T, A: Allocator> VecDeque<T, A> { /// /// See also [`binary_search_by`], [`binary_search_by_key`], and [`partition_point`]. /// - /// [`contains`]: VecDeque::contains /// [`binary_search_by`]: VecDeque::binary_search_by /// [`binary_search_by_key`]: VecDeque::binary_search_by_key /// [`partition_point`]: VecDeque::partition_point @@ -2441,12 +2450,13 @@ impl<T, A: Allocator> VecDeque<T, A> { } /// Binary searches this `VecDeque` with a comparator function. - /// This behaves similarly to [`contains`] if this `VecDeque` is sorted. /// - /// The comparator function should implement an order consistent - /// with the sort order of the deque, returning an order code that - /// indicates whether its argument is `Less`, `Equal` or `Greater` - /// than the desired target. + /// The comparator function should return an order code that indicates + /// whether its argument is `Less`, `Equal` or `Greater` the desired + /// target. + /// If the `VecDeque` is not sorted or if the comparator function does not + /// implement an order consistent with the sort order of the underlying + /// `VecDeque`, the returned result is unspecified and meaningless. /// /// If the value is found then [`Result::Ok`] is returned, containing the /// index of the matching element. If there are multiple matches, then any @@ -2456,7 +2466,6 @@ impl<T, A: Allocator> VecDeque<T, A> { /// /// See also [`binary_search`], [`binary_search_by_key`], and [`partition_point`]. /// - /// [`contains`]: VecDeque::contains /// [`binary_search`]: VecDeque::binary_search /// [`binary_search_by_key`]: VecDeque::binary_search_by_key /// [`partition_point`]: VecDeque::partition_point @@ -2496,10 +2505,11 @@ impl<T, A: Allocator> VecDeque<T, A> { } /// Binary searches this `VecDeque` with a key extraction function. - /// This behaves similarly to [`contains`] if this `VecDeque` is sorted. /// /// Assumes that the deque is sorted by the key, for instance with /// [`make_contiguous().sort_by_key()`] using the same key extraction function. + /// If the deque is not sorted by the key, the returned result is + /// unspecified and meaningless. /// /// If the value is found then [`Result::Ok`] is returned, containing the /// index of the matching element. If there are multiple matches, then any @@ -2509,7 +2519,6 @@ impl<T, A: Allocator> VecDeque<T, A> { /// /// See also [`binary_search`], [`binary_search_by`], and [`partition_point`]. /// - /// [`contains`]: VecDeque::contains /// [`make_contiguous().sort_by_key()`]: VecDeque::make_contiguous /// [`binary_search`]: VecDeque::binary_search /// [`binary_search_by`]: VecDeque::binary_search_by |