diff options
| author | yanchith <yanchi.toth@gmail.com> | 2023-06-09 11:22:08 +0200 |
|---|---|---|
| committer | yanchith <yanchi.toth@gmail.com> | 2023-06-09 11:22:08 +0200 |
| commit | cb5c011670ce8d073d0aae8c45e73c20593bfa11 (patch) | |
| tree | a11259b0350c7bfc4e4c642e8e00b5cd6e901444 /library/alloc/src/collections | |
| parent | 24df5f28e12c6ca4c1c6ef36f6d42f376c6060c3 (diff) | |
| parent | 9c843d9fa322596c7d525c78fa89731ecf7afbfe (diff) | |
Merge branch 'master' into binary-heap-ta
Diffstat (limited to 'library/alloc/src/collections')
30 files changed, 3225 insertions, 1941 deletions
diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap/mod.rs index c9f0e086495..f5e6bd20ea5 100644 --- a/library/alloc/src/collections/binary_heap.rs +++ b/library/alloc/src/collections/binary_heap/mod.rs @@ -145,8 +145,9 @@ use core::alloc::Allocator; 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}; use core::ptr; @@ -155,8 +156,6 @@ use crate::collections::TryReserveError; use crate::slice; use crate::vec::{self, AsVecIntoIter, Vec}; -use super::SpecExtend; - #[cfg(test)] mod tests; @@ -167,12 +166,20 @@ mod tests; /// It is a logic error for an item to be modified in such a way that the /// item's ordering relative to any other item, as determined by the [`Ord`] /// trait, changes while it is in the heap. This is normally only possible -/// through [`Cell`], [`RefCell`], global state, I/O, or unsafe code. The +/// through interior mutability, global state, I/O, or unsafe code. The /// behavior resulting from such a logic error is not specified, but will /// be encapsulated to the `BinaryHeap` that observed the logic error and not /// result in undefined behavior. This could include panics, incorrect results, /// aborts, memory leaks, and non-termination. /// +/// As long as no elements change their relative order while being in the heap +/// as described above, the API of `BinaryHeap` guarantees that the heap +/// invariant remains intact i.e. its methods all behave as documented. For +/// example if a method is documented as iterating in sorted order, that's +/// guaranteed to work as long as elements in the heap have not changed order, +/// even in the presence of closures getting unwinded out of, iterators getting +/// leaked, and similar foolishness. +/// /// # Examples /// /// ``` @@ -258,7 +265,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 @@ -274,6 +280,7 @@ pub struct BinaryHeap< data: Vec<T, A>, } +// XXX: PeekMut<A> /// Structure wrapping a mutable reference to the greatest item on a /// `BinaryHeap`. /// @@ -282,13 +289,11 @@ pub struct BinaryHeap< /// /// [`peek_mut`]: BinaryHeap::peek_mut #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] -pub struct PeekMut< - 'a, - T: 'a + Ord, - #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global, -> { - heap: &'a mut BinaryHeap<T, A>, - sift: bool, +pub struct PeekMut<'a, T: 'a + Ord> { + heap: &'a mut BinaryHeap<T>, + // If a set_len + sift_down are required, this is Some. If a &mut T has not + // yet been exposed to peek_mut()'s caller, it's None. + original_len: Option<NonZeroUsize>, } #[stable(feature = "collection_debug", since = "1.17.0")] @@ -301,7 +306,14 @@ impl<'a, T: Ord + fmt::Debug, A: Allocator + 'a> fmt::Debug for PeekMut<'a, T, A #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] impl<'a, T: Ord, A: Allocator + 'a> Drop for PeekMut<'a, T, A> { fn drop(&mut self) { - if self.sift { + if let Some(original_len) = self.original_len { + // SAFETY: That's how many elements were in the Vec at the time of + // the PeekMut::deref_mut call, and therefore also at the time of + // the BinaryHeap::peek_mut call. Since the PeekMut did not end up + // getting leaked, we are now undoing the leak amplification that + // the DerefMut prepared for. + unsafe { self.heap.data.set_len(original_len.get()) }; + // SAFETY: PeekMut is only instantiated for non-empty heaps. unsafe { self.heap.sift_down(0) }; } @@ -322,19 +334,46 @@ impl<'a, T: Ord, A: Allocator + 'a> Deref for PeekMut<'a, T, A> { impl<'a, T: Ord, A: Allocator + 'a> DerefMut for PeekMut<'a, T, A> { fn deref_mut(&mut self) -> &mut T { debug_assert!(!self.heap.is_empty()); - self.sift = true; + + let len = self.heap.len(); + if len > 1 { + // Here we preemptively leak all the rest of the underlying vector + // after the currently max element. If the caller mutates the &mut T + // we're about to give them, and then leaks the PeekMut, all these + // elements will remain leaked. If they don't leak the PeekMut, then + // either Drop or PeekMut::pop will un-leak the vector elements. + // + // This is technique is described throughout several other places in + // the standard library as "leak amplification". + unsafe { + // SAFETY: len > 1 so len != 0. + self.original_len = Some(NonZeroUsize::new_unchecked(len)); + // SAFETY: len > 1 so all this does for now is leak elements, + // which is safe. + self.heap.data.set_len(1); + } + } + // SAFE: PeekMut is only instantiated for non-empty heaps unsafe { self.heap.data.get_unchecked_mut(0) } } } +// XXX: PeekMut<A> impl<'a, T: Ord, A: Allocator + 'a> PeekMut<'a, T, A> { /// Removes the peeked value from the heap and returns it. #[stable(feature = "binary_heap_peek_mut_pop", since = "1.18.0")] - pub fn pop(mut this: PeekMut<'a, T, A>) -> T { - let value = this.heap.pop().unwrap(); - this.sift = false; - value + pub fn pop(mut this: PeekMut<'a, T>) -> T { + if let Some(original_len) = this.original_len.take() { + // SAFETY: This is how many elements were in the Vec at the time of + // the BinaryHeap::peek_mut call. + unsafe { this.heap.data.set_len(original_len.get()) }; + + // Unlike in Drop, here we don't also need to do a sift_down even if + // the caller could've mutated the element. It is removed from the + // heap on the next line and pop() is not sensitive to its value. + } + this.heap.pop().unwrap() } } @@ -365,7 +404,19 @@ impl<T: fmt::Debug, A: Allocator> fmt::Debug for BinaryHeap<T, A> { } } -impl<T: Ord> BinaryHeap<T, Global> { +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); + } +} + +// XXX: BinaryHeap<T, A> +impl<T: Ord> BinaryHeap<T> { /// Creates an empty `BinaryHeap` as a max-heap. /// /// # Examples @@ -450,11 +501,13 @@ impl<T: Ord, A: Allocator> BinaryHeap<T, A> { BinaryHeap { data: Vec::with_capacity_in(capacity, alloc) } } + // XXX: peek_mut /// Returns a mutable reference to the greatest item in the binary heap, or /// `None` if it is empty. /// - /// Note: If the `PeekMut` value is leaked, the heap may be in an - /// inconsistent state. + /// Note: If the `PeekMut` value is leaked, some heap elements might get + /// leaked along with it, but the remaining elements will remain a valid + /// heap. /// /// # Examples /// @@ -480,8 +533,12 @@ impl<T: Ord, A: Allocator> BinaryHeap<T, A> { /// If the item is modified then the worst case time complexity is *O*(log(*n*)), /// otherwise it's *O*(1). #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] - pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T, A>> { - if self.is_empty() { None } else { Some(PeekMut { heap: self, sift: false }) } + pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>> { + if self.is_empty() { + None + } else { + Some(PeekMut { heap: self, original_len: None }) + } } /// Removes the greatest item from the binary heap and returns it, or `None` if it @@ -847,7 +904,6 @@ impl<T: Ord, A: Allocator> BinaryHeap<T, A> { /// Basic usage: /// /// ``` - /// #![feature(binary_heap_retain)] /// use std::collections::BinaryHeap; /// /// let mut heap = BinaryHeap::from([-10, -5, 1, 2, 4, 13]); @@ -856,23 +912,24 @@ impl<T: Ord, A: Allocator> BinaryHeap<T, A> { /// /// 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, { - let mut first_removed = self.len(); + // 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; - self.data.retain(|e| { + + guard.heap.data.retain(|e| { let keep = f(e); - if !keep && i < first_removed { - first_removed = i; + if !keep && i < guard.rebuild_from { + guard.rebuild_from = i; } i += 1; keep }); - // data[0..first_removed] is untouched, so we only need to rebuild the tail: - self.rebuild_tail(first_removed); } } @@ -1065,7 +1122,8 @@ impl<T, A: Allocator> BinaryHeap<T, A> { /// current length. The allocator may reserve more space to speculatively /// avoid frequent allocations. After calling `try_reserve`, capacity will be /// greater than or equal to `self.len() + additional` if it returns - /// `Ok(())`. Does nothing if capacity is already sufficient. + /// `Ok(())`. Does nothing if capacity is already sufficient. This method + /// preserves the contents even if an error occurs. /// /// # Errors /// @@ -1418,7 +1476,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< @@ -1468,6 +1525,20 @@ impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> { #[stable(feature = "fused", since = "1.26.0")] impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {} +#[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")] @@ -1726,7 +1797,8 @@ impl<'a, T, A: Allocator + 'a> IntoIterator for &'a BinaryHeap<T, A> { impl<T: Ord, A: Allocator> Extend<T> for BinaryHeap<T, A> { #[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] @@ -1740,37 +1812,6 @@ impl<T: Ord, A: Allocator> Extend<T> for BinaryHeap<T, A> { } } -impl<T: Ord, A: Allocator, I: IntoIterator<Item = T>> SpecExtend<I> for BinaryHeap<T, A> { - 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, A: Allocator> BinaryHeap<T, A> { - 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/binary_heap/tests.rs b/library/alloc/src/collections/binary_heap/tests.rs index 5a05215aeed..500caa35678 100644 --- a/library/alloc/src/collections/binary_heap/tests.rs +++ b/library/alloc/src/collections/binary_heap/tests.rs @@ -1,8 +1,9 @@ use super::*; use crate::boxed::Box; +use crate::testing::crash_test::{CrashTestDummy, Panic}; +use core::mem; use std::iter::TrustedLen; use std::panic::{catch_unwind, AssertUnwindSafe}; -use std::sync::atomic::{AtomicU32, Ordering}; #[test] fn test_iterator() { @@ -147,6 +148,24 @@ fn test_peek_mut() { } #[test] +fn test_peek_mut_leek() { + let data = vec![4, 2, 7]; + let mut heap = BinaryHeap::from(data); + let mut max = heap.peek_mut().unwrap(); + *max = -1; + + // The PeekMut object's Drop impl would have been responsible for moving the + // -1 out of the max position of the BinaryHeap, but we don't run it. + mem::forget(max); + + // Absent some mitigation like leak amplification, the -1 would incorrectly + // end up in the last position of the returned Vec, with the rest of the + // heap's original contents in front of it in sorted order. + let sorted_vec = heap.into_sorted_vec(); + assert!(sorted_vec.is_sorted(), "{:?}", sorted_vec); +} + +#[test] fn test_peek_mut_pop() { let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; let mut heap = BinaryHeap::from(data); @@ -291,33 +310,83 @@ fn test_drain_sorted() { #[test] fn test_drain_sorted_leak() { - static DROPS: AtomicU32 = AtomicU32::new(0); - - #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)] - struct D(u32, bool); - - impl Drop for D { - fn drop(&mut self) { - DROPS.fetch_add(1, Ordering::SeqCst); - - if self.1 { - panic!("panic in `drop`"); - } - } - } - + let d0 = CrashTestDummy::new(0); + let d1 = CrashTestDummy::new(1); + let d2 = CrashTestDummy::new(2); + let d3 = CrashTestDummy::new(3); + let d4 = CrashTestDummy::new(4); + let d5 = CrashTestDummy::new(5); let mut q = BinaryHeap::from(vec![ - D(0, false), - D(1, false), - D(2, false), - D(3, true), - D(4, false), - D(5, false), + d0.spawn(Panic::Never), + d1.spawn(Panic::Never), + d2.spawn(Panic::Never), + d3.spawn(Panic::InDrop), + d4.spawn(Panic::Never), + d5.spawn(Panic::Never), ]); - catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).ok(); + catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).unwrap_err(); - assert_eq!(DROPS.load(Ordering::SeqCst), 6); + assert_eq!(d0.dropped(), 1); + assert_eq!(d1.dropped(), 1); + assert_eq!(d2.dropped(), 1); + assert_eq!(d3.dropped(), 1); + assert_eq!(d4.dropped(), 1); + assert_eq!(d5.dropped(), 1); + assert!(q.is_empty()); +} + +#[test] +fn test_drain_forget() { + let a = CrashTestDummy::new(0); + let b = CrashTestDummy::new(1); + let c = CrashTestDummy::new(2); + let mut q = + BinaryHeap::from(vec![a.spawn(Panic::Never), b.spawn(Panic::Never), c.spawn(Panic::Never)]); + + catch_unwind(AssertUnwindSafe(|| { + let mut it = q.drain(); + it.next(); + mem::forget(it); + })) + .unwrap(); + // Behaviour after leaking is explicitly unspecified and order is arbitrary, + // so it's fine if these start failing, but probably worth knowing. + assert!(q.is_empty()); + assert_eq!(a.dropped() + b.dropped() + c.dropped(), 1); + assert_eq!(a.dropped(), 0); + assert_eq!(b.dropped(), 0); + assert_eq!(c.dropped(), 1); + drop(q); + assert_eq!(a.dropped(), 0); + assert_eq!(b.dropped(), 0); + assert_eq!(c.dropped(), 1); +} + +#[test] +fn test_drain_sorted_forget() { + let a = CrashTestDummy::new(0); + let b = CrashTestDummy::new(1); + let c = CrashTestDummy::new(2); + let mut q = + BinaryHeap::from(vec![a.spawn(Panic::Never), b.spawn(Panic::Never), c.spawn(Panic::Never)]); + + catch_unwind(AssertUnwindSafe(|| { + let mut it = q.drain_sorted(); + it.next(); + mem::forget(it); + })) + .unwrap(); + // Behaviour after leaking is explicitly unspecified, + // so it's fine if these start failing, but probably worth knowing. + assert_eq!(q.len(), 2); + assert_eq!(a.dropped(), 0); + assert_eq!(b.dropped(), 0); + assert_eq!(c.dropped(), 1); + drop(q); + assert_eq!(a.dropped(), 1); + assert_eq!(b.dropped(), 1); + assert_eq!(c.dropped(), 1); } #[test] @@ -405,6 +474,25 @@ fn test_retain() { assert!(a.is_empty()); } +#[test] +fn test_retain_catch_unwind() { + let mut heap = BinaryHeap::from(vec![3, 1, 2]); + + // Removes the 3, then unwinds out of retain. + let _ = catch_unwind(AssertUnwindSafe(|| { + heap.retain(|e| { + if *e == 1 { + panic!(); + } + false + }); + })); + + // Naively this would be [1, 2] (an invalid heap) if BinaryHeap delegates to + // Vec's retain impl and then does not rebuild the heap after that unwinds. + assert_eq!(heap.into_vec(), [2, 1]); +} + // old binaryheap failed this test // // Integrity means that all elements are present after a comparison panics, @@ -415,7 +503,7 @@ fn test_retain() { #[test] #[cfg(not(target_os = "emscripten"))] fn panic_safe() { - use rand::{seq::SliceRandom, thread_rng}; + use rand::seq::SliceRandom; use std::cmp; use std::panic::{self, AssertUnwindSafe}; use std::sync::atomic::{AtomicUsize, Ordering}; @@ -440,7 +528,7 @@ fn panic_safe() { self.0.partial_cmp(&other.0) } } - let mut rng = thread_rng(); + let mut rng = crate::test_helpers::test_rng(); const DATASZ: usize = 32; // Miri is too slow let ntest = if cfg!(miri) { 1 } else { 10 }; diff --git a/library/alloc/src/collections/btree/borrow.rs b/library/alloc/src/collections/btree/borrow.rs index 016f139a501..000b9bd0fab 100644 --- a/library/alloc/src/collections/btree/borrow.rs +++ b/library/alloc/src/collections/btree/borrow.rs @@ -41,6 +41,28 @@ impl<'a, T> DormantMutRef<'a, T> { // SAFETY: our own safety conditions imply this reference is again unique. unsafe { &mut *self.ptr.as_ptr() } } + + /// Borrows a new mutable reference from the unique borrow initially captured. + /// + /// # Safety + /// + /// The reborrow must have ended, i.e., the reference returned by `new` and + /// all pointers and references derived from it, must not be used anymore. + pub unsafe fn reborrow(&mut self) -> &'a mut T { + // SAFETY: our own safety conditions imply this reference is again unique. + unsafe { &mut *self.ptr.as_ptr() } + } + + /// Borrows a new shared reference from the unique borrow initially captured. + /// + /// # Safety + /// + /// The reborrow must have ended, i.e., the reference returned by `new` and + /// all pointers and references derived from it, must not be used anymore. + pub unsafe fn reborrow_shared(&self) -> &'a T { + // SAFETY: our own safety conditions imply this reference is again unique. + unsafe { &*self.ptr.as_ptr() } + } } #[cfg(test)] diff --git a/library/alloc/src/collections/btree/dedup_sorted_iter.rs b/library/alloc/src/collections/btree/dedup_sorted_iter.rs index 60bf83b8387..17ee78045a9 100644 --- a/library/alloc/src/collections/btree/dedup_sorted_iter.rs +++ b/library/alloc/src/collections/btree/dedup_sorted_iter.rs @@ -3,7 +3,9 @@ use core::iter::Peekable; /// A iterator for deduping the key of a sorted iterator. /// When encountering the duplicated key, only the last key-value pair is yielded. /// -/// Used by [`BTreeMap::bulk_build_from_sorted_iter`]. +/// Used by [`BTreeMap::bulk_build_from_sorted_iter`][1]. +/// +/// [1]: crate::collections::BTreeMap::bulk_build_from_sorted_iter pub struct DedupSortedIter<K, V, I> where I: Iterator<Item = (K, V)>, diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 0bddd7a9906..1f8a1ecba6e 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -3,10 +3,10 @@ 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::{Index, RangeBounds}; +use core::ops::{Bound, Index, RangeBounds}; use core::ptr; use crate::alloc::{Allocator, Global}; @@ -15,7 +15,7 @@ use super::borrow::DormantMutRef; use super::dedup_sorted_iter::DedupSortedIter; use super::navigate::{LazyLeafRange, LeafRange}; use super::node::{self, marker, ForceResult::*, Handle, NodeRef, Root}; -use super::search::SearchResult::*; +use super::search::{SearchBound, SearchResult::*}; use super::set_val::SetValZST; mod entry; @@ -46,8 +46,8 @@ pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT; /// is done is *very* inefficient for modern computer architectures. In particular, every element /// is stored in its own individually heap-allocated node. This means that every single insertion /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these -/// are both notably expensive things to do in practice, we are forced to at very least reconsider -/// the BST strategy. +/// are both notably expensive things to do in practice, we are forced to, at the very least, +/// reconsider the BST strategy. /// /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in @@ -178,6 +178,8 @@ pub struct BTreeMap< length: usize, /// `ManuallyDrop` to control drop order (needs to be dropped after all the nodes). pub(super) alloc: ManuallyDrop<A>, + // For dropck; the `Box` avoids making the `Unpin` impl more strict than before + _marker: PhantomData<crate::boxed::Box<(K, V)>>, } #[stable(feature = "btree_drop", since = "1.7.0")] @@ -187,6 +189,19 @@ unsafe impl<#[may_dangle] K, #[may_dangle] V, A: Allocator + Clone> Drop for BTr } } +// FIXME: This implementation is "wrong", but changing it would be a breaking change. +// (The bounds of the automatic `UnwindSafe` implementation have been like this since Rust 1.50.) +// Maybe we can fix it nonetheless with a crater run, or if the `UnwindSafe` +// traits are deprecated, or disarmed (no longer causing hard errors) in the future. +#[stable(feature = "btree_unwindsafe", since = "1.64.0")] +impl<K, V, A: Allocator + Clone> core::panic::UnwindSafe for BTreeMap<K, V, A> +where + A: core::panic::UnwindSafe, + K: core::panic::RefUnwindSafe, + V: core::panic::RefUnwindSafe, +{ +} + #[stable(feature = "rust1", since = "1.0.0")] impl<K: Clone, V: Clone, A: Allocator + Clone> Clone for BTreeMap<K, V, A> { fn clone(&self) -> BTreeMap<K, V, A> { @@ -204,6 +219,7 @@ impl<K: Clone, V: Clone, A: Allocator + Clone> Clone for BTreeMap<K, V, A> { root: Some(Root::new(alloc.clone())), length: 0, alloc: ManuallyDrop::new(alloc), + _marker: PhantomData, }; { @@ -346,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 @@ -370,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< @@ -405,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 @@ -564,10 +624,10 @@ impl<K, V> BTreeMap<K, V> { /// map.insert(1, "a"); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] + #[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")] #[must_use] pub const fn new() -> BTreeMap<K, V> { - BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(Global) } + BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(Global), _marker: PhantomData } } } @@ -589,10 +649,11 @@ 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(), + _marker: PhantomData, }); } @@ -615,7 +676,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// ``` #[unstable(feature = "btreemap_alloc", issue = "32838")] pub fn new_in(alloc: A) -> BTreeMap<K, V, A> { - BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(alloc) } + BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(alloc), _marker: PhantomData } } } @@ -686,7 +747,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// Basic usage: /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); @@ -695,7 +755,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// map.insert(2, "a"); /// assert_eq!(map.first_key_value(), Some((&1, &"b"))); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn first_key_value(&self) -> Option<(&K, &V)> where K: Ord, @@ -710,7 +770,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// # Examples /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); @@ -724,7 +783,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// assert_eq!(*map.get(&1).unwrap(), "first"); /// assert_eq!(*map.get(&2).unwrap(), "b"); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>> where K: Ord, @@ -748,7 +807,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// Draining elements in ascending order, while keeping a usable map each iteration. /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); @@ -759,7 +817,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// } /// assert!(map.is_empty()); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn pop_first(&mut self) -> Option<(K, V)> where K: Ord, @@ -775,7 +833,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// Basic usage: /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); @@ -783,7 +840,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// map.insert(2, "a"); /// assert_eq!(map.last_key_value(), Some((&2, &"a"))); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn last_key_value(&self) -> Option<(&K, &V)> where K: Ord, @@ -798,7 +855,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// # Examples /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); @@ -812,7 +868,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// assert_eq!(*map.get(&1).unwrap(), "a"); /// assert_eq!(*map.get(&2).unwrap(), "last"); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>> where K: Ord, @@ -836,7 +892,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// Draining elements in descending order, while keeping a usable map each iteration. /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); @@ -847,7 +902,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// } /// assert!(map.is_empty()); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn pop_last(&mut self) -> Option<(K, V)> where K: Ord, @@ -1082,6 +1137,9 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// Moves all elements from `other` into `self`, leaving `other` empty. /// + /// If a key from `other` is already present in `self`, the respective + /// value from `self` will be overwritten with the respective value from `other`. + /// /// # Examples /// /// ``` @@ -1090,10 +1148,10 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// let mut a = BTreeMap::new(); /// a.insert(1, "a"); /// a.insert(2, "b"); - /// a.insert(3, "c"); + /// a.insert(3, "c"); // Note: Key (3) also present in b. /// /// let mut b = BTreeMap::new(); - /// b.insert(3, "d"); + /// b.insert(3, "d"); // Note: Key (3) also present in a. /// b.insert(4, "e"); /// b.insert(5, "f"); /// @@ -1104,7 +1162,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// /// assert_eq!(a[&1], "a"); /// assert_eq!(a[&2], "b"); - /// assert_eq!(a[&3], "d"); + /// assert_eq!(a[&3], "d"); // Note: "c" has been overwritten. /// assert_eq!(a[&4], "e"); /// assert_eq!(a[&5], "f"); /// ``` @@ -1320,7 +1378,12 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { let (new_left_len, right_len) = Root::calc_split_length(total_num, &left_root, &right_root); self.length = new_left_len; - BTreeMap { root: Some(right_root), length: right_len, alloc: self.alloc.clone() } + BTreeMap { + root: Some(right_root), + length: right_len, + alloc: self.alloc.clone(), + _marker: PhantomData, + } } /// Creates an iterator that visits all elements (key-value pairs) in @@ -1445,7 +1508,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { let mut root = Root::new(alloc.clone()); let mut length = 0; root.bulk_push(DedupSortedIter::new(iter.into_iter()), &mut length, alloc.clone()); - BTreeMap { root: Some(root), length, alloc: ManuallyDrop::new(alloc) } + BTreeMap { root: Some(root), length, alloc: ManuallyDrop::new(alloc), _marker: PhantomData } } } @@ -1480,11 +1543,17 @@ impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> { self.next_back() } - fn min(mut self) -> Option<(&'a K, &'a V)> { + fn min(mut self) -> Option<(&'a K, &'a V)> + where + (&'a K, &'a V): Ord, + { self.next() } - fn max(mut self) -> Option<(&'a K, &'a V)> { + fn max(mut self) -> Option<(&'a K, &'a V)> + where + (&'a K, &'a V): Ord, + { self.next_back() } } @@ -1549,11 +1618,17 @@ impl<'a, K, V> Iterator for IterMut<'a, K, V> { self.next_back() } - fn min(mut self) -> Option<(&'a K, &'a mut V)> { + fn min(mut self) -> Option<(&'a K, &'a mut V)> + where + (&'a K, &'a mut V): Ord, + { self.next() } - fn max(mut self) -> Option<(&'a K, &'a mut V)> { + fn max(mut self) -> Option<(&'a K, &'a mut V)> + where + (&'a K, &'a mut V): Ord, + { self.next_back() } } @@ -1716,11 +1791,17 @@ impl<'a, K, V> Iterator for Keys<'a, K, V> { self.next_back() } - fn min(mut self) -> Option<&'a K> { + fn min(mut self) -> Option<&'a K> + where + &'a K: Ord, + { self.next() } - fn max(mut self) -> Option<&'a K> { + fn max(mut self) -> Option<&'a K> + where + &'a K: Ord, + { self.next_back() } } @@ -1749,6 +1830,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; @@ -1790,6 +1885,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< @@ -1917,15 +2026,35 @@ impl<'a, K, V> Iterator for Range<'a, K, V> { self.next_back() } - fn min(mut self) -> Option<(&'a K, &'a V)> { + fn min(mut self) -> Option<(&'a K, &'a V)> + where + (&'a K, &'a V): Ord, + { self.next() } - fn max(mut self) -> Option<(&'a K, &'a V)> { + fn max(mut self) -> Option<(&'a K, &'a V)> + where + (&'a K, &'a V): Ord, + { self.next_back() } } +#[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; @@ -1976,11 +2105,17 @@ impl<K, V, A: Allocator + Clone> Iterator for IntoKeys<K, V, A> { self.next_back() } - fn min(mut self) -> Option<K> { + fn min(mut self) -> Option<K> + where + K: Ord, + { self.next() } - fn max(mut self) -> Option<K> { + fn max(mut self) -> Option<K> + where + K: Ord, + { self.next_back() } } @@ -2002,6 +2137,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; @@ -2036,6 +2188,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)> { @@ -2065,11 +2234,17 @@ impl<'a, K, V> Iterator for RangeMut<'a, K, V> { self.next_back() } - fn min(mut self) -> Option<(&'a K, &'a mut V)> { + fn min(mut self) -> Option<(&'a K, &'a mut V)> + where + (&'a K, &'a mut V): Ord, + { self.next() } - fn max(mut self) -> Option<(&'a K, &'a mut V)> { + fn max(mut self) -> Option<(&'a K, &'a mut V)> + where + (&'a K, &'a mut V): Ord, + { self.next_back() } } @@ -2370,7 +2545,11 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// ``` #[must_use] #[stable(feature = "rust1", since = "1.0.0")] - #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] + #[rustc_const_unstable( + feature = "const_btree_len", + issue = "71835", + implied_by = "const_btree_new" + )] pub const fn len(&self) -> usize { self.length } @@ -2391,10 +2570,740 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// ``` #[must_use] #[stable(feature = "rust1", since = "1.0.0")] - #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] + #[rustc_const_unstable( + feature = "const_btree_len", + issue = "71835", + implied_by = "const_btree_new" + )] pub const fn is_empty(&self) -> bool { self.len() == 0 } + + /// Returns a [`Cursor`] pointing at the first element that is above the + /// given bound. + /// + /// If no such element exists then a cursor pointing at the "ghost" + /// non-element is returned. + /// + /// Passing [`Bound::Unbounded`] will return a cursor pointing at the first + /// element of the map. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(btree_cursors)] + /// + /// use std::collections::BTreeMap; + /// use std::ops::Bound; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// a.insert(3, "c"); + /// a.insert(4, "c"); + /// let cursor = a.lower_bound(Bound::Excluded(&2)); + /// assert_eq!(cursor.key(), Some(&3)); + /// ``` + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> + where + K: Borrow<Q> + Ord, + Q: Ord, + { + let root_node = match self.root.as_ref() { + None => return Cursor { current: None, root: None }, + Some(root) => root.reborrow(), + }; + let edge = root_node.lower_bound(SearchBound::from_range(bound)); + Cursor { current: edge.next_kv().ok(), root: self.root.as_ref() } + } + + /// Returns a [`CursorMut`] pointing at the first element that is above the + /// given bound. + /// + /// If no such element exists then a cursor pointing at the "ghost" + /// non-element is returned. + /// + /// Passing [`Bound::Unbounded`] will return a cursor pointing at the first + /// element of the map. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(btree_cursors)] + /// + /// use std::collections::BTreeMap; + /// use std::ops::Bound; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// a.insert(3, "c"); + /// a.insert(4, "c"); + /// let cursor = a.lower_bound_mut(Bound::Excluded(&2)); + /// assert_eq!(cursor.key(), Some(&3)); + /// ``` + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A> + where + K: Borrow<Q> + Ord, + Q: Ord, + { + let (root, dormant_root) = DormantMutRef::new(&mut self.root); + let root_node = match root.as_mut() { + None => { + return CursorMut { + current: None, + root: dormant_root, + length: &mut self.length, + alloc: &mut *self.alloc, + }; + } + Some(root) => root.borrow_mut(), + }; + let edge = root_node.lower_bound(SearchBound::from_range(bound)); + CursorMut { + current: edge.next_kv().ok(), + root: dormant_root, + length: &mut self.length, + alloc: &mut *self.alloc, + } + } + + /// Returns a [`Cursor`] pointing at the last element that is below the + /// given bound. + /// + /// If no such element exists then a cursor pointing at the "ghost" + /// non-element is returned. + /// + /// Passing [`Bound::Unbounded`] will return a cursor pointing at the last + /// element of the map. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(btree_cursors)] + /// + /// use std::collections::BTreeMap; + /// use std::ops::Bound; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// a.insert(3, "c"); + /// a.insert(4, "c"); + /// let cursor = a.upper_bound(Bound::Excluded(&3)); + /// assert_eq!(cursor.key(), Some(&2)); + /// ``` + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> + where + K: Borrow<Q> + Ord, + Q: Ord, + { + let root_node = match self.root.as_ref() { + None => return Cursor { current: None, root: None }, + Some(root) => root.reborrow(), + }; + let edge = root_node.upper_bound(SearchBound::from_range(bound)); + Cursor { current: edge.next_back_kv().ok(), root: self.root.as_ref() } + } + + /// Returns a [`CursorMut`] pointing at the last element that is below the + /// given bound. + /// + /// If no such element exists then a cursor pointing at the "ghost" + /// non-element is returned. + /// + /// Passing [`Bound::Unbounded`] will return a cursor pointing at the last + /// element of the map. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(btree_cursors)] + /// + /// use std::collections::BTreeMap; + /// use std::ops::Bound; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// a.insert(3, "c"); + /// a.insert(4, "c"); + /// let cursor = a.upper_bound_mut(Bound::Excluded(&3)); + /// assert_eq!(cursor.key(), Some(&2)); + /// ``` + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A> + where + K: Borrow<Q> + Ord, + Q: Ord, + { + let (root, dormant_root) = DormantMutRef::new(&mut self.root); + let root_node = match root.as_mut() { + None => { + return CursorMut { + current: None, + root: dormant_root, + length: &mut self.length, + alloc: &mut *self.alloc, + }; + } + Some(root) => root.borrow_mut(), + }; + let edge = root_node.upper_bound(SearchBound::from_range(bound)); + CursorMut { + current: edge.next_back_kv().ok(), + root: dormant_root, + length: &mut self.length, + alloc: &mut *self.alloc, + } + } +} + +/// A cursor over a `BTreeMap`. +/// +/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth. +/// +/// Cursors always point to an element in the tree, and index in a logically circular way. +/// To accommodate this, there is a "ghost" non-element that yields `None` between the last and +/// first elements of the tree. +/// +/// A `Cursor` is created with the [`BTreeMap::lower_bound`] and [`BTreeMap::upper_bound`] methods. +#[unstable(feature = "btree_cursors", issue = "107540")] +pub struct Cursor<'a, K: 'a, V: 'a> { + current: Option<Handle<NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>, marker::KV>>, + root: Option<&'a node::Root<K, V>>, +} + +#[unstable(feature = "btree_cursors", issue = "107540")] +impl<K, V> Clone for Cursor<'_, K, V> { + fn clone(&self) -> Self { + let Cursor { current, root } = *self; + Cursor { current, root } + } +} + +#[unstable(feature = "btree_cursors", issue = "107540")] +impl<K: Debug, V: Debug> Debug for Cursor<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("Cursor").field(&self.key_value()).finish() + } +} + +/// A cursor over a `BTreeMap` with editing operations. +/// +/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can +/// safely mutate the tree during iteration. This is because the lifetime of its yielded +/// references is tied to its own lifetime, instead of just the underlying tree. This means +/// cursors cannot yield multiple elements at once. +/// +/// Cursors always point to an element in the tree, and index in a logically circular way. +/// To accommodate this, there is a "ghost" non-element that yields `None` between the last and +/// first elements of the tree. +/// +/// A `Cursor` is created with the [`BTreeMap::lower_bound_mut`] and [`BTreeMap::upper_bound_mut`] +/// methods. +#[unstable(feature = "btree_cursors", issue = "107540")] +pub struct CursorMut< + 'a, + K: 'a, + V: 'a, + #[unstable(feature = "allocator_api", issue = "32838")] A = Global, +> { + current: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>>, + root: DormantMutRef<'a, Option<node::Root<K, V>>>, + length: &'a mut usize, + alloc: &'a mut A, +} + +#[unstable(feature = "btree_cursors", issue = "107540")] +impl<K: Debug, V: Debug, A> Debug for CursorMut<'_, K, V, A> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("CursorMut").field(&self.key_value()).finish() + } +} + +impl<'a, K, V> Cursor<'a, K, V> { + /// Moves the cursor to the next element of the `BTreeMap`. + /// + /// If the cursor is pointing to the "ghost" non-element then this will move it to + /// the first element of the `BTreeMap`. If it is pointing to the last + /// element of the `BTreeMap` then this will move it to the "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn move_next(&mut self) { + match self.current.take() { + None => { + self.current = self.root.and_then(|root| { + root.reborrow().first_leaf_edge().forget_node_type().right_kv().ok() + }); + } + Some(current) => { + self.current = current.next_leaf_edge().next_kv().ok(); + } + } + } + + /// Moves the cursor to the previous element of the `BTreeMap`. + /// + /// If the cursor is pointing to the "ghost" non-element then this will move it to + /// the last element of the `BTreeMap`. If it is pointing to the first + /// element of the `BTreeMap` then this will move it to the "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn move_prev(&mut self) { + match self.current.take() { + None => { + self.current = self.root.and_then(|root| { + root.reborrow().last_leaf_edge().forget_node_type().left_kv().ok() + }); + } + Some(current) => { + self.current = current.next_back_leaf_edge().next_back_kv().ok(); + } + } + } + + /// Returns a reference to the key of the element that the cursor is + /// currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn key(&self) -> Option<&'a K> { + self.current.as_ref().map(|current| current.into_kv().0) + } + + /// Returns a reference to the value of the element that the cursor is + /// currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn value(&self) -> Option<&'a V> { + self.current.as_ref().map(|current| current.into_kv().1) + } + + /// Returns a reference to the key and value of the element that the cursor + /// is currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn key_value(&self) -> Option<(&'a K, &'a V)> { + self.current.as_ref().map(|current| current.into_kv()) + } + + /// Returns a reference to the next element. + /// + /// If the cursor is pointing to the "ghost" non-element then this returns + /// the first element of the `BTreeMap`. If it is pointing to the last + /// element of the `BTreeMap` then this returns `None`. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_next(&self) -> Option<(&'a K, &'a V)> { + let mut next = self.clone(); + next.move_next(); + next.current.as_ref().map(|current| current.into_kv()) + } + + /// Returns a reference to the previous element. + /// + /// If the cursor is pointing to the "ghost" non-element then this returns + /// the last element of the `BTreeMap`. If it is pointing to the first + /// element of the `BTreeMap` then this returns `None`. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_prev(&self) -> Option<(&'a K, &'a V)> { + let mut prev = self.clone(); + prev.move_prev(); + prev.current.as_ref().map(|current| current.into_kv()) + } +} + +impl<'a, K, V, A> CursorMut<'a, K, V, A> { + /// Moves the cursor to the next element of the `BTreeMap`. + /// + /// If the cursor is pointing to the "ghost" non-element then this will move it to + /// the first element of the `BTreeMap`. If it is pointing to the last + /// element of the `BTreeMap` then this will move it to the "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn move_next(&mut self) { + match self.current.take() { + None => { + // SAFETY: The previous borrow of root has ended. + self.current = unsafe { self.root.reborrow() }.as_mut().and_then(|root| { + root.borrow_mut().first_leaf_edge().forget_node_type().right_kv().ok() + }); + } + Some(current) => { + self.current = current.next_leaf_edge().next_kv().ok(); + } + } + } + + /// Moves the cursor to the previous element of the `BTreeMap`. + /// + /// If the cursor is pointing to the "ghost" non-element then this will move it to + /// the last element of the `BTreeMap`. If it is pointing to the first + /// element of the `BTreeMap` then this will move it to the "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn move_prev(&mut self) { + match self.current.take() { + None => { + // SAFETY: The previous borrow of root has ended. + self.current = unsafe { self.root.reborrow() }.as_mut().and_then(|root| { + root.borrow_mut().last_leaf_edge().forget_node_type().left_kv().ok() + }); + } + Some(current) => { + self.current = current.next_back_leaf_edge().next_back_kv().ok(); + } + } + } + + /// Returns a reference to the key of the element that the cursor is + /// currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn key(&self) -> Option<&K> { + self.current.as_ref().map(|current| current.reborrow().into_kv().0) + } + + /// Returns a reference to the value of the element that the cursor is + /// currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn value(&self) -> Option<&V> { + self.current.as_ref().map(|current| current.reborrow().into_kv().1) + } + + /// Returns a reference to the key and value of the element that the cursor + /// is currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn key_value(&self) -> Option<(&K, &V)> { + self.current.as_ref().map(|current| current.reborrow().into_kv()) + } + + /// Returns a mutable reference to the value of the element that the cursor + /// is currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn value_mut(&mut self) -> Option<&mut V> { + self.current.as_mut().map(|current| current.kv_mut().1) + } + + /// Returns a reference to the key and mutable reference to the value of the + /// element that the cursor is currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn key_value_mut(&mut self) -> Option<(&K, &mut V)> { + self.current.as_mut().map(|current| { + let (k, v) = current.kv_mut(); + (&*k, v) + }) + } + + /// Returns a mutable reference to the key of the element that the cursor is + /// currently pointing to. + /// + /// This returns `None` if the cursor is currently pointing to the + /// "ghost" non-element. + /// + /// # Safety + /// + /// This can be used to modify the key, but you must ensure that the + /// `BTreeMap` invariants are maintained. Specifically: + /// + /// * The key must remain unique within the tree. + /// * The key must remain in sorted order with regards to other elements in + /// the tree. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn key_mut_unchecked(&mut self) -> Option<&mut K> { + self.current.as_mut().map(|current| current.kv_mut().0) + } + + /// Returns a reference to the key and value of the next element. + /// + /// If the cursor is pointing to the "ghost" non-element then this returns + /// the first element of the `BTreeMap`. If it is pointing to the last + /// element of the `BTreeMap` then this returns `None`. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_next(&mut self) -> Option<(&K, &mut V)> { + let (k, v) = match self.current { + None => { + // SAFETY: The previous borrow of root has ended. + unsafe { self.root.reborrow() } + .as_mut()? + .borrow_mut() + .first_leaf_edge() + .next_kv() + .ok()? + .into_kv_valmut() + } + // SAFETY: We're not using this to mutate the tree. + Some(ref mut current) => { + unsafe { current.reborrow_mut() }.next_leaf_edge().next_kv().ok()?.into_kv_valmut() + } + }; + Some((k, v)) + } + + /// Returns a reference to the key and value of the previous element. + /// + /// If the cursor is pointing to the "ghost" non-element then this returns + /// the last element of the `BTreeMap`. If it is pointing to the first + /// element of the `BTreeMap` then this returns `None`. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_prev(&mut self) -> Option<(&K, &mut V)> { + let (k, v) = match self.current.as_mut() { + None => { + // SAFETY: The previous borrow of root has ended. + unsafe { self.root.reborrow() } + .as_mut()? + .borrow_mut() + .last_leaf_edge() + .next_back_kv() + .ok()? + .into_kv_valmut() + } + Some(current) => { + // SAFETY: We're not using this to mutate the tree. + unsafe { current.reborrow_mut() } + .next_back_leaf_edge() + .next_back_kv() + .ok()? + .into_kv_valmut() + } + }; + Some((k, v)) + } + + /// Returns a read-only cursor pointing to the current element. + /// + /// The lifetime of the returned `Cursor` is bound to that of the + /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the + /// `CursorMut` is frozen for the lifetime of the `Cursor`. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn as_cursor(&self) -> Cursor<'_, K, V> { + Cursor { + // SAFETY: The tree is immutable while the cursor exists. + root: unsafe { self.root.reborrow_shared().as_ref() }, + current: self.current.as_ref().map(|current| current.reborrow()), + } + } +} + +// Now the tree editing operations +impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { + /// Inserts a new element into the `BTreeMap` after the current one. + /// + /// If the cursor is pointing at the "ghost" non-element then the new element is + /// inserted at the front of the `BTreeMap`. + /// + /// # Safety + /// + /// You must ensure that the `BTreeMap` invariants are maintained. + /// Specifically: + /// + /// * The key of the newly inserted element must be unique in the tree. + /// * All keys in the tree must remain in sorted order. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn insert_after_unchecked(&mut self, key: K, value: V) { + let edge = match self.current.take() { + None => { + // SAFETY: We have no other reference to the tree. + match unsafe { self.root.reborrow() } { + root @ None => { + // Tree is empty, allocate a new root. + let mut node = NodeRef::new_leaf(self.alloc.clone()); + node.borrow_mut().push(key, value); + *root = Some(node.forget_type()); + *self.length += 1; + return; + } + Some(root) => root.borrow_mut().first_leaf_edge(), + } + } + Some(current) => current.next_leaf_edge(), + }; + + let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| { + drop(ins.left); + // SAFETY: The handle to the newly inserted value is always on a + // leaf node, so adding a new root node doesn't invalidate it. + let root = unsafe { self.root.reborrow().as_mut().unwrap() }; + root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right) + }); + self.current = handle.left_edge().next_back_kv().ok(); + *self.length += 1; + } + + /// Inserts a new element into the `BTreeMap` before the current one. + /// + /// If the cursor is pointing at the "ghost" non-element then the new element is + /// inserted at the end of the `BTreeMap`. + /// + /// # Safety + /// + /// You must ensure that the `BTreeMap` invariants are maintained. + /// Specifically: + /// + /// * The key of the newly inserted element must be unique in the tree. + /// * All keys in the tree must remain in sorted order. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn insert_before_unchecked(&mut self, key: K, value: V) { + let edge = match self.current.take() { + None => { + // SAFETY: We have no other reference to the tree. + match unsafe { self.root.reborrow() } { + root @ None => { + // Tree is empty, allocate a new root. + let mut node = NodeRef::new_leaf(self.alloc.clone()); + node.borrow_mut().push(key, value); + *root = Some(node.forget_type()); + *self.length += 1; + return; + } + Some(root) => root.borrow_mut().last_leaf_edge(), + } + } + Some(current) => current.next_back_leaf_edge(), + }; + + let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| { + drop(ins.left); + // SAFETY: The handle to the newly inserted value is always on a + // leaf node, so adding a new root node doesn't invalidate it. + let root = unsafe { self.root.reborrow().as_mut().unwrap() }; + root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right) + }); + self.current = handle.right_edge().next_kv().ok(); + *self.length += 1; + } + + /// Inserts a new element into the `BTreeMap` after the current one. + /// + /// If the cursor is pointing at the "ghost" non-element then the new element is + /// inserted at the front of the `BTreeMap`. + /// + /// # Panics + /// + /// This function panics if: + /// - the given key compares less than or equal to the current element (if + /// any). + /// - the given key compares greater than or equal to the next element (if + /// any). + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn insert_after(&mut self, key: K, value: V) { + if let Some(current) = self.key() { + if &key <= current { + panic!("key must be ordered above the current element"); + } + } + if let Some((next, _)) = self.peek_next() { + if &key >= next { + panic!("key must be ordered below the next element"); + } + } + unsafe { + self.insert_after_unchecked(key, value); + } + } + + /// Inserts a new element into the `BTreeMap` before the current one. + /// + /// If the cursor is pointing at the "ghost" non-element then the new element is + /// inserted at the end of the `BTreeMap`. + /// + /// # Panics + /// + /// This function panics if: + /// - the given key compares greater than or equal to the current element + /// (if any). + /// - the given key compares less than or equal to the previous element (if + /// any). + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn insert_before(&mut self, key: K, value: V) { + if let Some(current) = self.key() { + if &key >= current { + panic!("key must be ordered below the current element"); + } + } + if let Some((prev, _)) = self.peek_prev() { + if &key <= prev { + panic!("key must be ordered above the previous element"); + } + } + unsafe { + self.insert_before_unchecked(key, value); + } + } + + /// Removes the current element from the `BTreeMap`. + /// + /// The element that was removed is returned, and the cursor is + /// moved to point to the next element in the `BTreeMap`. + /// + /// If the cursor is currently pointing to the "ghost" non-element then no element + /// is removed and `None` is returned. The cursor is not moved in this case. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn remove_current(&mut self) -> Option<(K, V)> { + let current = self.current.take()?; + let mut emptied_internal_root = false; + let (kv, pos) = + current.remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone()); + self.current = pos.next_kv().ok(); + *self.length -= 1; + if emptied_internal_root { + // SAFETY: This is safe since current does not point within the now + // empty root node. + let root = unsafe { self.root.reborrow().as_mut().unwrap() }; + root.pop_internal_level(self.alloc.clone()); + } + Some(kv) + } + + /// Removes the current element from the `BTreeMap`. + /// + /// The element that was removed is returned, and the cursor is + /// moved to point to the previous element in the `BTreeMap`. + /// + /// If the cursor is currently pointing to the "ghost" non-element then no element + /// is removed and `None` is returned. The cursor is not moved in this case. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn remove_current_and_move_back(&mut self) -> Option<(K, V)> { + let current = self.current.take()?; + let mut emptied_internal_root = false; + let (kv, pos) = + current.remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone()); + self.current = pos.next_back_kv().ok(); + *self.length -= 1; + if emptied_internal_root { + // SAFETY: This is safe since current does not point within the now + // empty root node. + let root = unsafe { self.root.reborrow().as_mut().unwrap() }; + root.pop_internal_level(self.alloc.clone()); + } + Some(kv) + } } #[cfg(test)] diff --git a/library/alloc/src/collections/btree/map/entry.rs b/library/alloc/src/collections/btree/map/entry.rs index b6eecf9b0e9..e9366eec9ce 100644 --- a/library/alloc/src/collections/btree/map/entry.rs +++ b/library/alloc/src/collections/btree/map/entry.rs @@ -133,6 +133,16 @@ impl<'a, K: Debug + Ord, V: Debug, A: Allocator + Clone> fmt::Display } } +#[unstable(feature = "map_try_insert", issue = "82766")] +impl<'a, K: core::fmt::Debug + Ord, V: core::fmt::Debug> core::error::Error + for crate::collections::btree_map::OccupiedError<'a, K, V> +{ + #[allow(deprecated)] + fn description(&self) -> &str { + "key already exists" + } +} + impl<'a, K: Ord, V, A: Allocator + Clone> Entry<'a, K, V, A> { /// Ensures a value is in the entry by inserting the default if empty, and returns /// a mutable reference to the value in the entry. @@ -337,7 +347,7 @@ impl<'a, K: Ord, V, A: Allocator + Clone> VacantEntry<'a, K, V, A> { /// assert_eq!(map["poneyland"], 37); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn insert(self, value: V) -> &'a mut V { + pub fn insert(mut self, value: V) -> &'a mut V { let out_ptr = match self.handle { None => { // SAFETY: There is no tree yet so no reference to it exists. @@ -348,25 +358,27 @@ impl<'a, K: Ord, V, A: Allocator + Clone> VacantEntry<'a, K, V, A> { map.length = 1; val_ptr } - Some(handle) => match handle.insert_recursing(self.key, value, self.alloc.clone()) { - (None, val_ptr) => { - // SAFETY: We have consumed self.handle. - let map = unsafe { self.dormant_map.awaken() }; - map.length += 1; - val_ptr - } - (Some(ins), val_ptr) => { - drop(ins.left); - // SAFETY: We have consumed self.handle and dropped the - // remaining reference to the tree, ins.left. - let map = unsafe { self.dormant_map.awaken() }; - let root = map.root.as_mut().unwrap(); // same as ins.left - root.push_internal_level(self.alloc).push(ins.kv.0, ins.kv.1, ins.right); - map.length += 1; - val_ptr - } - }, + Some(handle) => { + let new_handle = + handle.insert_recursing(self.key, value, self.alloc.clone(), |ins| { + drop(ins.left); + // SAFETY: Pushing a new root node doesn't invalidate + // handles to existing nodes. + let map = unsafe { self.dormant_map.reborrow() }; + let root = map.root.as_mut().unwrap(); // same as ins.left + root.push_internal_level(self.alloc).push(ins.kv.0, ins.kv.1, ins.right) + }); + + // Get the pointer to the value + let val_ptr = new_handle.into_val_mut(); + + // SAFETY: We have consumed self.handle. + let map = unsafe { self.dormant_map.awaken() }; + map.length += 1; + val_ptr + } }; + // Now that we have finished growing the tree using borrowed references, // dereference the pointer to a part of it, that we picked up along the way. unsafe { &mut *out_ptr } diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index 4c372b1d60a..7ecffe3eef2 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -1,16 +1,16 @@ -use super::super::testing::crash_test::{CrashTestDummy, Panic}; -use super::super::testing::ord_chaos::{Cyclic3, Governed, Governor}; -use super::super::testing::rng::DeterministicRng; use super::Entry::{Occupied, Vacant}; use super::*; use crate::boxed::Box; use crate::fmt::Debug; use crate::rc::Rc; use crate::string::{String, ToString}; +use crate::testing::crash_test::{CrashTestDummy, Panic}; +use crate::testing::ord_chaos::{Cyclic3, Governed, Governor}; +use crate::testing::rng::DeterministicRng; use crate::vec::Vec; +use core::assert_matches::assert_matches; 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; @@ -2336,3 +2336,134 @@ fn from_array() { let unordered_duplicates = BTreeMap::from([(3, 4), (1, 2), (1, 2)]); assert_eq!(map, unordered_duplicates); } + +#[test] +fn test_cursor() { + let map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + + let mut cur = map.lower_bound(Bound::Unbounded); + assert_eq!(cur.key(), Some(&1)); + cur.move_next(); + assert_eq!(cur.key(), Some(&2)); + assert_eq!(cur.peek_next(), Some((&3, &'c'))); + cur.move_prev(); + assert_eq!(cur.key(), Some(&1)); + assert_eq!(cur.peek_prev(), None); + + let mut cur = map.upper_bound(Bound::Excluded(&1)); + assert_eq!(cur.key(), None); + cur.move_next(); + assert_eq!(cur.key(), Some(&1)); + cur.move_prev(); + assert_eq!(cur.key(), None); + assert_eq!(cur.peek_prev(), Some((&3, &'c'))); +} + +#[test] +fn test_cursor_mut() { + let mut map = BTreeMap::from([(1, 'a'), (3, 'c'), (5, 'e')]); + let mut cur = map.lower_bound_mut(Bound::Excluded(&3)); + assert_eq!(cur.key(), Some(&5)); + cur.insert_before(4, 'd'); + assert_eq!(cur.key(), Some(&5)); + assert_eq!(cur.peek_prev(), Some((&4, &mut 'd'))); + cur.move_next(); + assert_eq!(cur.key(), None); + cur.insert_before(6, 'f'); + assert_eq!(cur.key(), None); + assert_eq!(cur.remove_current(), None); + assert_eq!(cur.key(), None); + cur.insert_after(0, '?'); + assert_eq!(cur.key(), None); + assert_eq!(map, BTreeMap::from([(0, '?'), (1, 'a'), (3, 'c'), (4, 'd'), (5, 'e'), (6, 'f')])); + + let mut cur = map.upper_bound_mut(Bound::Included(&5)); + assert_eq!(cur.key(), Some(&5)); + assert_eq!(cur.remove_current(), Some((5, 'e'))); + assert_eq!(cur.key(), Some(&6)); + assert_eq!(cur.remove_current_and_move_back(), Some((6, 'f'))); + 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'); +} + +#[test] +fn cursor_peek_prev_agrees_with_cursor_mut() { + let mut map = BTreeMap::from([(1, 1), (2, 2), (3, 3)]); + + let cursor = map.lower_bound(Bound::Excluded(&3)); + assert!(cursor.key().is_none()); + + let prev = cursor.peek_prev(); + assert_matches!(prev, Some((&3, _))); + + // Shadow names so the two parts of this test match. + let mut cursor = map.lower_bound_mut(Bound::Excluded(&3)); + assert!(cursor.key().is_none()); + + let prev = cursor.peek_prev(); + assert_matches!(prev, Some((&3, _))); +} diff --git a/library/alloc/src/collections/btree/mod.rs b/library/alloc/src/collections/btree/mod.rs index 9d43ac5c5be..c7d0144de30 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; @@ -21,6 +20,3 @@ trait Recover<Q: ?Sized> { fn take(&mut self, key: &Q) -> Option<Self::Key>; fn replace(&mut self, key: Self::Key) -> Option<Self::Key>; } - -#[cfg(test)] -mod testing; diff --git a/library/alloc/src/collections/btree/navigate.rs b/library/alloc/src/collections/btree/navigate.rs index 1e33c1e64d6..a85a3162451 100644 --- a/library/alloc/src/collections/btree/navigate.rs +++ b/library/alloc/src/collections/btree/navigate.rs @@ -4,6 +4,7 @@ use core::ops::RangeBounds; use core::ptr; use super::node::{marker, ForceResult::*, Handle, NodeRef}; +use super::search::SearchBound; use crate::alloc::Allocator; // `front` and `back` are always both `None` or both `Some`. @@ -18,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 } @@ -123,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() } @@ -386,7 +399,7 @@ impl<BorrowType: marker::BorrowType, K, V> /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV /// on the left side, which is either in the same leaf node or in an ancestor node. /// If the leaf edge is the first one in the tree, returns [`Result::Err`] with the root node. - fn next_back_kv( + pub fn next_back_kv( self, ) -> Result< Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>, @@ -707,7 +720,9 @@ impl<BorrowType: marker::BorrowType, K, V> } /// Returns the leaf edge closest to a KV for backward navigation. - fn next_back_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> { + pub fn next_back_leaf_edge( + self, + ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> { match self.force() { Leaf(leaf_kv) => leaf_kv.left_edge(), Internal(internal_kv) => { @@ -717,3 +732,51 @@ impl<BorrowType: marker::BorrowType, K, V> } } } + +impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { + /// Returns the leaf edge corresponding to the first point at which the + /// given bound is true. + pub fn lower_bound<Q: ?Sized>( + self, + mut bound: SearchBound<&Q>, + ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> + where + Q: Ord, + K: Borrow<Q>, + { + let mut node = self; + loop { + let (edge, new_bound) = node.find_lower_bound_edge(bound); + match edge.force() { + Leaf(edge) => return edge, + Internal(edge) => { + node = edge.descend(); + bound = new_bound; + } + } + } + } + + /// Returns the leaf edge corresponding to the last point at which the + /// given bound is true. + pub fn upper_bound<Q: ?Sized>( + self, + mut bound: SearchBound<&Q>, + ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> + where + Q: Ord, + K: Borrow<Q>, + { + let mut node = self; + loop { + let (edge, new_bound) = node.find_upper_bound_edge(bound); + match edge.force() { + Leaf(edge) => return edge, + Internal(edge) => { + node = edge.descend(); + bound = new_bound; + } + } + } + } +} diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index d831161bcb6..3233a575ecf 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -206,9 +206,9 @@ impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> { unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {} -unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send for NodeRef<marker::Immut<'a>, K, V, Type> {} -unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::Mut<'a>, K, V, Type> {} -unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::ValMut<'a>, K, V, Type> {} +unsafe impl<K: Sync, V: Sync, Type> Send for NodeRef<marker::Immut<'_>, K, V, Type> {} +unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Mut<'_>, K, V, Type> {} +unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::ValMut<'_>, K, V, Type> {} unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {} unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Dying, K, V, Type> {} @@ -318,7 +318,10 @@ impl<BorrowType: marker::BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> pub fn ascend( self, ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> { - assert!(BorrowType::PERMITS_TRAVERSAL); + const { + assert!(BorrowType::TRAVERSAL_PERMIT); + } + // We need to use raw pointers to nodes because, if BorrowType is marker::ValMut, // there might be outstanding mutable references to values that we must not invalidate. let leaf_ptr: *const _ = Self::as_leaf_ptr(&self); @@ -439,6 +442,24 @@ impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> { // SAFETY: we have exclusive access to the entire node. unsafe { &mut *ptr } } + + /// Returns a dormant copy of this node with its lifetime erased which can + /// be reawakened later. + pub fn dormant(&self) -> NodeRef<marker::DormantMut, K, V, Type> { + NodeRef { height: self.height, node: self.node, _marker: PhantomData } + } +} + +impl<K, V, Type> NodeRef<marker::DormantMut, K, V, Type> { + /// Revert to the unique borrow initially captured. + /// + /// # Safety + /// + /// The reborrow must have ended, i.e., the reference returned by `new` and + /// all pointers and references derived from it, must not be used anymore. + pub unsafe fn awaken<'a>(self) -> NodeRef<marker::Mut<'a>, K, V, Type> { + NodeRef { height: self.height, node: self.node, _marker: PhantomData } + } } impl<K, V, Type> NodeRef<marker::Dying, K, V, Type> { @@ -795,6 +816,25 @@ impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeT // We can't use Handle::new_kv or Handle::new_edge because we don't know our type Handle { node: unsafe { self.node.reborrow_mut() }, idx: self.idx, _marker: PhantomData } } + + /// Returns a dormant copy of this handle which can be reawakened later. + /// + /// See `DormantMutRef` for more details. + pub fn dormant(&self) -> Handle<NodeRef<marker::DormantMut, K, V, NodeType>, HandleType> { + Handle { node: self.node.dormant(), idx: self.idx, _marker: PhantomData } + } +} + +impl<K, V, NodeType, HandleType> Handle<NodeRef<marker::DormantMut, K, V, NodeType>, HandleType> { + /// Revert to the unique borrow initially captured. + /// + /// # Safety + /// + /// The reborrow must have ended, i.e., the reference returned by `new` and + /// all pointers and references derived from it, must not be used anymore. + pub unsafe fn awaken<'a>(self) -> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> { + Handle { node: unsafe { self.node.awaken() }, idx: self.idx, _marker: PhantomData } + } } impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> { @@ -848,9 +888,11 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, mark /// Inserts a new key-value pair between the key-value pairs to the right and left of /// this edge. This method assumes that there is enough space in the node for the new /// pair to fit. - /// - /// The returned pointer points to the inserted value. - fn insert_fit(&mut self, key: K, val: V) -> *mut V { + unsafe fn insert_fit( + mut self, + key: K, + val: V, + ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> { debug_assert!(self.node.len() < CAPACITY); let new_len = self.node.len() + 1; @@ -859,7 +901,7 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, mark slice_insert(self.node.val_area_mut(..new_len), self.idx, val); *self.node.len_mut() = new_len as u16; - self.node.val_area_mut(self.idx).assume_init_mut() + Handle::new_kv(self.node, self.idx) } } } @@ -868,21 +910,26 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, mark /// Inserts a new key-value pair between the key-value pairs to the right and left of /// this edge. This method splits the node if there isn't enough room. /// - /// The returned pointer points to the inserted value. + /// Returns a dormant handle to the inserted node which can be reawakened + /// once splitting is complete. fn insert<A: Allocator + Clone>( - mut self, + self, key: K, val: V, alloc: A, - ) -> (Option<SplitResult<'a, K, V, marker::Leaf>>, *mut V) { + ) -> ( + Option<SplitResult<'a, K, V, marker::Leaf>>, + Handle<NodeRef<marker::DormantMut, K, V, marker::Leaf>, marker::KV>, + ) { if self.node.len() < CAPACITY { - let val_ptr = self.insert_fit(key, val); - (None, val_ptr) + // SAFETY: There is enough space in the node for insertion. + let handle = unsafe { self.insert_fit(key, val) }; + (None, handle.dormant()) } else { let (middle_kv_idx, insertion) = splitpoint(self.idx); let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) }; let mut result = middle.split(alloc); - let mut insertion_edge = match insertion { + let insertion_edge = match insertion { LeftOrRight::Left(insert_idx) => unsafe { Handle::new_edge(result.left.reborrow_mut(), insert_idx) }, @@ -890,8 +937,10 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, mark Handle::new_edge(result.right.borrow_mut(), insert_idx) }, }; - let val_ptr = insertion_edge.insert_fit(key, val); - (Some(result), val_ptr) + // SAFETY: We just split the node, so there is enough space for + // insertion. + let handle = unsafe { insertion_edge.insert_fit(key, val).dormant() }; + (Some(result), handle) } } } @@ -973,21 +1022,31 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, mark key: K, value: V, alloc: A, - ) -> (Option<SplitResult<'a, K, V, marker::LeafOrInternal>>, *mut V) { - let (mut split, val_ptr) = match self.insert(key, value, alloc.clone()) { - (None, val_ptr) => return (None, val_ptr), - (Some(split), val_ptr) => (split.forget_node_type(), val_ptr), + split_root: impl FnOnce(SplitResult<'a, K, V, marker::LeafOrInternal>), + ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> { + let (mut split, handle) = match self.insert(key, value, alloc.clone()) { + // SAFETY: we have finished splitting and can now re-awaken the + // handle to the inserted element. + (None, handle) => return unsafe { handle.awaken() }, + (Some(split), handle) => (split.forget_node_type(), handle), }; loop { split = match split.left.ascend() { Ok(parent) => { match parent.insert(split.kv.0, split.kv.1, split.right, alloc.clone()) { - None => return (None, val_ptr), + // SAFETY: we have finished splitting and can now re-awaken the + // handle to the inserted element. + None => return unsafe { handle.awaken() }, Some(split) => split.forget_node_type(), } } - Err(root) => return (Some(SplitResult { left: root, ..split }), val_ptr), + Err(root) => { + split_root(SplitResult { left: root, ..split }); + // SAFETY: we have finished splitting and can now re-awaken the + // handle to the inserted element. + return unsafe { handle.awaken() }; + } }; } } @@ -1003,7 +1062,10 @@ impl<BorrowType: marker::BorrowType, K, V> /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should /// both, upon success, do nothing. pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { - assert!(BorrowType::PERMITS_TRAVERSAL); + const { + assert!(BorrowType::TRAVERSAL_PERMIT); + } + // We need to use raw pointers to nodes because, if BorrowType is // marker::ValMut, there might be outstanding mutable references to // values that we must not invalidate. There's no worry accessing the @@ -1037,6 +1099,14 @@ impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType> let leaf = self.node.into_leaf_mut(); unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() } } + + pub fn into_kv_valmut(self) -> (&'a K, &'a mut V) { + debug_assert!(self.idx < self.node.len()); + let leaf = self.node.into_leaf_mut(); + let k = unsafe { leaf.keys.get_unchecked(self.idx).assume_init_ref() }; + let v = unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() }; + (k, v) + } } impl<'a, K, V, NodeType> Handle<NodeRef<marker::ValMut<'a>, K, V, NodeType>, marker::KV> { @@ -1661,25 +1731,29 @@ pub mod marker { pub enum Owned {} pub enum Dying {} + pub enum DormantMut {} pub struct Immut<'a>(PhantomData<&'a ()>); pub struct Mut<'a>(PhantomData<&'a mut ()>); pub struct ValMut<'a>(PhantomData<&'a mut ()>); pub trait BorrowType { - // Whether node references of this borrow type allow traversing - // to other nodes in the tree. - const PERMITS_TRAVERSAL: bool = true; + /// If node references of this borrow type allow traversing to other + /// nodes in the tree, this constant is set to `true`. It can be used + /// for a compile-time assertion. + const TRAVERSAL_PERMIT: bool = true; } impl BorrowType for Owned { - // Traversal isn't needed, it happens using the result of `borrow_mut`. - // By disabling traversal, and only creating new references to roots, - // we know that every reference of the `Owned` type is to a root node. - const PERMITS_TRAVERSAL: bool = false; + /// Reject traversal, because it isn't needed. Instead traversal + /// happens using the result of `borrow_mut`. + /// By disabling traversal, and only creating new references to roots, + /// we know that every reference of the `Owned` type is to a root node. + const TRAVERSAL_PERMIT: bool = false; } impl BorrowType for Dying {} impl<'a> BorrowType for Immut<'a> {} impl<'a> BorrowType for Mut<'a> {} impl<'a> BorrowType for ValMut<'a> {} + impl BorrowType for DormantMut {} pub enum KV {} pub enum Edge {} diff --git a/library/alloc/src/collections/btree/node/tests.rs b/library/alloc/src/collections/btree/node/tests.rs index aadb0dc9c40..64bce0ff8c0 100644 --- a/library/alloc/src/collections/btree/node/tests.rs +++ b/library/alloc/src/collections/btree/node/tests.rs @@ -94,6 +94,7 @@ fn test_partial_eq() { #[test] #[cfg(target_arch = "x86_64")] +#[cfg_attr(miri, ignore)] // We'd like to run Miri with layout randomization fn test_sizes() { assert_eq!(core::mem::size_of::<LeafNode<(), ()>>(), 16); assert_eq!(core::mem::size_of::<LeafNode<i64, i64>>(), 16 + CAPACITY * 2 * 8); diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs index 2cfc0807409..940fa30afb8 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< @@ -343,7 +336,7 @@ impl<T> BTreeSet<T> { /// let mut set: BTreeSet<i32> = BTreeSet::new(); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] + #[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")] #[must_use] pub const fn new() -> BTreeSet<T> { BTreeSet { map: BTreeMap::new() } @@ -786,7 +779,6 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// Basic usage: /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeSet; /// /// let mut set = BTreeSet::new(); @@ -797,7 +789,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// assert_eq!(set.first(), Some(&1)); /// ``` #[must_use] - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn first(&self) -> Option<&T> where T: Ord, @@ -813,7 +805,6 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// Basic usage: /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeSet; /// /// let mut set = BTreeSet::new(); @@ -824,7 +815,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// assert_eq!(set.last(), Some(&2)); /// ``` #[must_use] - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn last(&self) -> Option<&T> where T: Ord, @@ -838,7 +829,6 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// # Examples /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeSet; /// /// let mut set = BTreeSet::new(); @@ -849,7 +839,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// } /// assert!(set.is_empty()); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn pop_first(&mut self) -> Option<T> where T: Ord, @@ -863,7 +853,6 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// # Examples /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeSet; /// /// let mut set = BTreeSet::new(); @@ -874,7 +863,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// } /// assert!(set.is_empty()); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn pop_last(&mut self) -> Option<T> where T: Ord, @@ -1174,7 +1163,11 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// ``` #[must_use] #[stable(feature = "rust1", since = "1.0.0")] - #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] + #[rustc_const_unstable( + feature = "const_btree_len", + issue = "71835", + implied_by = "const_btree_new" + )] pub const fn len(&self) -> usize { self.map.len() } @@ -1193,7 +1186,11 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// ``` #[must_use] #[stable(feature = "rust1", since = "1.0.0")] - #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] + #[rustc_const_unstable( + feature = "const_btree_len", + issue = "71835", + implied_by = "const_btree_new" + )] pub const fn is_empty(&self) -> bool { self.len() == 0 } @@ -1504,11 +1501,17 @@ impl<'a, T> Iterator for Iter<'a, T> { self.next_back() } - fn min(mut self) -> Option<&'a T> { + fn min(mut self) -> Option<&'a T> + where + &'a T: Ord, + { self.next() } - fn max(mut self) -> Option<&'a T> { + fn max(mut self) -> Option<&'a T> + where + &'a T: Ord, + { self.next_back() } } @@ -1540,6 +1543,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> { @@ -1556,6 +1574,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 { @@ -1575,11 +1610,17 @@ impl<'a, T> Iterator for Range<'a, T> { self.next_back() } - fn min(mut self) -> Option<&'a T> { + fn min(mut self) -> Option<&'a T> + where + &'a T: Ord, + { self.next() } - fn max(mut self) -> Option<&'a T> { + fn max(mut self) -> Option<&'a T> + where + &'a T: Ord, + { self.next_back() } } @@ -1594,6 +1635,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 502d3e1d126..a7c839d77ed 100644 --- a/library/alloc/src/collections/btree/set/tests.rs +++ b/library/alloc/src/collections/btree/set/tests.rs @@ -1,10 +1,9 @@ -use super::super::testing::crash_test::{CrashTestDummy, Panic}; -use super::super::testing::rng::DeterministicRng; use super::*; +use crate::testing::crash_test::{CrashTestDummy, Panic}; +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/btree/testing/crash_test.rs b/library/alloc/src/collections/btree/testing/crash_test.rs deleted file mode 100644 index bcf5f5f7251..00000000000 --- a/library/alloc/src/collections/btree/testing/crash_test.rs +++ /dev/null @@ -1,119 +0,0 @@ -// We avoid relying on anything else in the crate, apart from the `Debug` trait. -use crate::fmt::Debug; -use std::cmp::Ordering; -use std::sync::atomic::{AtomicUsize, Ordering::SeqCst}; - -/// A blueprint for crash test dummy instances that monitor particular events. -/// Some instances may be configured to panic at some point. -/// Events are `clone`, `drop` or some anonymous `query`. -/// -/// Crash test dummies are identified and ordered by an id, so they can be used -/// as keys in a BTreeMap. -#[derive(Debug)] -pub struct CrashTestDummy { - pub id: usize, - cloned: AtomicUsize, - dropped: AtomicUsize, - queried: AtomicUsize, -} - -impl CrashTestDummy { - /// Creates a crash test dummy design. The `id` determines order and equality of instances. - pub fn new(id: usize) -> CrashTestDummy { - CrashTestDummy { - id, - cloned: AtomicUsize::new(0), - dropped: AtomicUsize::new(0), - queried: AtomicUsize::new(0), - } - } - - /// Creates an instance of a crash test dummy that records what events it experiences - /// and optionally panics. - pub fn spawn(&self, panic: Panic) -> Instance<'_> { - Instance { origin: self, panic } - } - - /// Returns how many times instances of the dummy have been cloned. - pub fn cloned(&self) -> usize { - self.cloned.load(SeqCst) - } - - /// Returns how many times instances of the dummy have been dropped. - pub fn dropped(&self) -> usize { - self.dropped.load(SeqCst) - } - - /// Returns how many times instances of the dummy have had their `query` member invoked. - pub fn queried(&self) -> usize { - self.queried.load(SeqCst) - } -} - -#[derive(Debug)] -pub struct Instance<'a> { - origin: &'a CrashTestDummy, - panic: Panic, -} - -#[derive(Copy, Clone, Debug, PartialEq, Eq)] -pub enum Panic { - Never, - InClone, - InDrop, - InQuery, -} - -impl Instance<'_> { - pub fn id(&self) -> usize { - self.origin.id - } - - /// Some anonymous query, the result of which is already given. - pub fn query<R>(&self, result: R) -> R { - self.origin.queried.fetch_add(1, SeqCst); - if self.panic == Panic::InQuery { - panic!("panic in `query`"); - } - result - } -} - -impl Clone for Instance<'_> { - fn clone(&self) -> Self { - self.origin.cloned.fetch_add(1, SeqCst); - if self.panic == Panic::InClone { - panic!("panic in `clone`"); - } - Self { origin: self.origin, panic: Panic::Never } - } -} - -impl Drop for Instance<'_> { - fn drop(&mut self) { - self.origin.dropped.fetch_add(1, SeqCst); - if self.panic == Panic::InDrop { - panic!("panic in `drop`"); - } - } -} - -impl PartialOrd for Instance<'_> { - fn partial_cmp(&self, other: &Self) -> Option<Ordering> { - self.id().partial_cmp(&other.id()) - } -} - -impl Ord for Instance<'_> { - fn cmp(&self, other: &Self) -> Ordering { - self.id().cmp(&other.id()) - } -} - -impl PartialEq for Instance<'_> { - fn eq(&self, other: &Self) -> bool { - self.id().eq(&other.id()) - } -} - -impl Eq for Instance<'_> {} diff --git a/library/alloc/src/collections/btree/testing/mod.rs b/library/alloc/src/collections/btree/testing/mod.rs deleted file mode 100644 index 7a094f8a595..00000000000 --- a/library/alloc/src/collections/btree/testing/mod.rs +++ /dev/null @@ -1,3 +0,0 @@ -pub mod crash_test; -pub mod ord_chaos; -pub mod rng; diff --git a/library/alloc/src/collections/btree/testing/ord_chaos.rs b/library/alloc/src/collections/btree/testing/ord_chaos.rs deleted file mode 100644 index 96ce7c15790..00000000000 --- a/library/alloc/src/collections/btree/testing/ord_chaos.rs +++ /dev/null @@ -1,81 +0,0 @@ -use std::cell::Cell; -use std::cmp::Ordering::{self, *}; -use std::ptr; - -// Minimal type with an `Ord` implementation violating transitivity. -#[derive(Debug)] -pub enum Cyclic3 { - A, - B, - C, -} -use Cyclic3::*; - -impl PartialOrd for Cyclic3 { - fn partial_cmp(&self, other: &Self) -> Option<Ordering> { - Some(self.cmp(other)) - } -} - -impl Ord for Cyclic3 { - fn cmp(&self, other: &Self) -> Ordering { - match (self, other) { - (A, A) | (B, B) | (C, C) => Equal, - (A, B) | (B, C) | (C, A) => Less, - (A, C) | (B, A) | (C, B) => Greater, - } - } -} - -impl PartialEq for Cyclic3 { - fn eq(&self, other: &Self) -> bool { - self.cmp(&other) == Equal - } -} - -impl Eq for Cyclic3 {} - -// Controls the ordering of values wrapped by `Governed`. -#[derive(Debug)] -pub struct Governor { - flipped: Cell<bool>, -} - -impl Governor { - pub fn new() -> Self { - Governor { flipped: Cell::new(false) } - } - - pub fn flip(&self) { - self.flipped.set(!self.flipped.get()); - } -} - -// Type with an `Ord` implementation that forms a total order at any moment -// (assuming that `T` respects total order), but can suddenly be made to invert -// that total order. -#[derive(Debug)] -pub struct Governed<'a, T>(pub T, pub &'a Governor); - -impl<T: Ord> PartialOrd for Governed<'_, T> { - fn partial_cmp(&self, other: &Self) -> Option<Ordering> { - Some(self.cmp(other)) - } -} - -impl<T: Ord> Ord for Governed<'_, T> { - fn cmp(&self, other: &Self) -> Ordering { - assert!(ptr::eq(self.1, other.1)); - let ord = self.0.cmp(&other.0); - if self.1.flipped.get() { ord.reverse() } else { ord } - } -} - -impl<T: PartialEq> PartialEq for Governed<'_, T> { - fn eq(&self, other: &Self) -> bool { - assert!(ptr::eq(self.1, other.1)); - self.0.eq(&other.0) - } -} - -impl<T: Eq> Eq for Governed<'_, T> {} diff --git a/library/alloc/src/collections/btree/testing/rng.rs b/library/alloc/src/collections/btree/testing/rng.rs deleted file mode 100644 index ecf543bee03..00000000000 --- a/library/alloc/src/collections/btree/testing/rng.rs +++ /dev/null @@ -1,28 +0,0 @@ -/// XorShiftRng -pub struct DeterministicRng { - count: usize, - x: u32, - y: u32, - z: u32, - w: u32, -} - -impl DeterministicRng { - pub fn new() -> Self { - DeterministicRng { count: 0, x: 0x193a6754, y: 0xa8a7d469, z: 0x97830e05, w: 0x113ba7bb } - } - - /// Guarantees that each returned number is unique. - pub fn next(&mut self) -> u32 { - self.count += 1; - assert!(self.count <= 70029); - let x = self.x; - let t = x ^ (x << 11); - self.x = self.y; - self.y = self.z; - self.z = self.w; - let w_ = self.w; - self.w = w_ ^ (w_ >> 19) ^ (t ^ (t >> 8)); - self.w - } -} diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs index e21c8aa3bd5..4cd34ac2fa7 100644 --- a/library/alloc/src/collections/linked_list.rs +++ b/library/alloc/src/collections/linked_list.rs @@ -15,12 +15,13 @@ 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; +use core::ptr::{NonNull, Unique}; use super::SpecExtend; +use crate::alloc::{Allocator, Global}; use crate::boxed::Box; #[cfg(test)] @@ -47,11 +48,15 @@ mod tests; #[stable(feature = "rust1", since = "1.0.0")] #[cfg_attr(not(test), rustc_diagnostic_item = "LinkedList")] #[rustc_insignificant_dtor] -pub struct LinkedList<T> { +pub struct LinkedList< + T, + #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, +> { head: Option<NonNull<Node<T>>>, tail: Option<NonNull<Node<T>>>, len: usize, - marker: PhantomData<Box<Node<T>>>, + alloc: A, + marker: PhantomData<Box<Node<T>, A>>, } struct Node<T> { @@ -81,6 +86,7 @@ impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { head: self.head, tail: self.tail, len: self.len, + alloc: Global, marker: PhantomData, })) .field(&self.len) @@ -117,6 +123,7 @@ impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> { head: self.head, tail: self.tail, len: self.len, + alloc: Global, marker: PhantomData, })) .field(&self.len) @@ -130,15 +137,17 @@ 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> { - list: LinkedList<T>, +pub struct IntoIter< + T, + #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, +> { + list: LinkedList<T, A>, } #[stable(feature = "collection_debug", since = "1.17.0")] -impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { +impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_tuple("IntoIter").field(&self.list).finish() } @@ -149,22 +158,25 @@ impl<T> Node<T> { Node { next: None, prev: None, element } } - fn into_element(self: Box<Self>) -> T { + fn into_element<A: Allocator>(self: Box<Self, A>) -> T { self.element } } // private methods -impl<T> LinkedList<T> { +impl<T, A: Allocator> LinkedList<T, A> { /// Adds the given node to the front of the list. + /// + /// # Safety + /// `node` must point to a valid node that was boxed using the list's allocator. #[inline] - fn push_front_node(&mut self, mut node: Box<Node<T>>) { + unsafe fn push_front_node(&mut self, node: Unique<Node<T>>) { // This method takes care not to create mutable references to whole nodes, // to maintain validity of aliasing pointers into `element`. unsafe { - node.next = self.head; - node.prev = None; - let node = Some(Box::leak(node).into()); + (*node.as_ptr()).next = self.head; + (*node.as_ptr()).prev = None; + let node = Some(NonNull::from(node)); match self.head { None => self.tail = node, @@ -179,11 +191,11 @@ impl<T> LinkedList<T> { /// Removes and returns the node at the front of the list. #[inline] - fn pop_front_node(&mut self) -> Option<Box<Node<T>>> { + fn pop_front_node(&mut self) -> Option<Box<Node<T>, &A>> { // This method takes care not to create mutable references to whole nodes, // to maintain validity of aliasing pointers into `element`. self.head.map(|node| unsafe { - let node = Box::from_raw(node.as_ptr()); + let node = Box::from_raw_in(node.as_ptr(), &self.alloc); self.head = node.next; match self.head { @@ -198,14 +210,17 @@ impl<T> LinkedList<T> { } /// Adds the given node to the back of the list. + /// + /// # Safety + /// `node` must point to a valid node that was boxed using the list's allocator. #[inline] - fn push_back_node(&mut self, mut node: Box<Node<T>>) { + unsafe fn push_back_node(&mut self, node: Unique<Node<T>>) { // This method takes care not to create mutable references to whole nodes, // to maintain validity of aliasing pointers into `element`. unsafe { - node.next = None; - node.prev = self.tail; - let node = Some(Box::leak(node).into()); + (*node.as_ptr()).next = None; + (*node.as_ptr()).prev = self.tail; + let node = Some(NonNull::from(node)); match self.tail { None => self.head = node, @@ -220,11 +235,11 @@ impl<T> LinkedList<T> { /// Removes and returns the node at the back of the list. #[inline] - fn pop_back_node(&mut self) -> Option<Box<Node<T>>> { + fn pop_back_node(&mut self) -> Option<Box<Node<T>, &A>> { // This method takes care not to create mutable references to whole nodes, // to maintain validity of aliasing pointers into `element`. self.tail.map(|node| unsafe { - let node = Box::from_raw(node.as_ptr()); + let node = Box::from_raw_in(node.as_ptr(), &self.alloc); self.tail = node.prev; match self.tail { @@ -322,7 +337,10 @@ impl<T> LinkedList<T> { &mut self, split_node: Option<NonNull<Node<T>>>, at: usize, - ) -> Self { + ) -> Self + where + A: Clone, + { // The split node is the new head node of the second part if let Some(mut split_node) = split_node { let first_part_head; @@ -343,6 +361,7 @@ impl<T> LinkedList<T> { head: first_part_head, tail: first_part_tail, len: at, + alloc: self.alloc.clone(), marker: PhantomData, }; @@ -352,7 +371,7 @@ impl<T> LinkedList<T> { first_part } else { - mem::replace(self, LinkedList::new()) + mem::replace(self, LinkedList::new_in(self.alloc.clone())) } } @@ -361,7 +380,10 @@ impl<T> LinkedList<T> { &mut self, split_node: Option<NonNull<Node<T>>>, at: usize, - ) -> Self { + ) -> Self + where + A: Clone, + { // The split node is the new tail node of the first part and owns // the head of the second part. if let Some(mut split_node) = split_node { @@ -383,6 +405,7 @@ impl<T> LinkedList<T> { head: second_part_head, tail: second_part_tail, len: self.len - at, + alloc: self.alloc.clone(), marker: PhantomData, }; @@ -392,7 +415,7 @@ impl<T> LinkedList<T> { second_part } else { - mem::replace(self, LinkedList::new()) + mem::replace(self, LinkedList::new_in(self.alloc.clone())) } } } @@ -421,7 +444,7 @@ impl<T> LinkedList<T> { #[stable(feature = "rust1", since = "1.0.0")] #[must_use] pub const fn new() -> Self { - LinkedList { head: None, tail: None, len: 0, marker: PhantomData } + LinkedList { head: None, tail: None, len: 0, alloc: Global, marker: PhantomData } } /// Moves all elements from `other` to the end of the list. @@ -472,7 +495,26 @@ impl<T> LinkedList<T> { } } } +} +impl<T, A: Allocator> LinkedList<T, A> { + /// Constructs an empty `LinkedList<T, A>`. + /// + /// # Examples + /// + /// ``` + /// #![feature(allocator_api)] + /// + /// use std::alloc::System; + /// use std::collections::LinkedList; + /// + /// let list: LinkedList<u32, _> = LinkedList::new_in(System); + /// ``` + #[inline] + #[unstable(feature = "allocator_api", issue = "32838")] + pub const fn new_in(alloc: A) -> Self { + LinkedList { head: None, tail: None, len: 0, alloc, marker: PhantomData } + } /// Provides a forward iterator. /// /// # Examples @@ -533,7 +575,7 @@ impl<T> LinkedList<T> { #[inline] #[must_use] #[unstable(feature = "linked_list_cursors", issue = "58533")] - pub fn cursor_front(&self) -> Cursor<'_, T> { + pub fn cursor_front(&self) -> Cursor<'_, T, A> { Cursor { index: 0, current: self.head, list: self } } @@ -543,7 +585,7 @@ impl<T> LinkedList<T> { #[inline] #[must_use] #[unstable(feature = "linked_list_cursors", issue = "58533")] - pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T> { + pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T, A> { CursorMut { index: 0, current: self.head, list: self } } @@ -553,7 +595,7 @@ impl<T> LinkedList<T> { #[inline] #[must_use] #[unstable(feature = "linked_list_cursors", issue = "58533")] - pub fn cursor_back(&self) -> Cursor<'_, T> { + pub fn cursor_back(&self) -> Cursor<'_, T, A> { Cursor { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self } } @@ -563,7 +605,7 @@ impl<T> LinkedList<T> { #[inline] #[must_use] #[unstable(feature = "linked_list_cursors", issue = "58533")] - pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T> { + pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T, A> { CursorMut { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self } } @@ -639,7 +681,15 @@ impl<T> LinkedList<T> { #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn clear(&mut self) { - *self = Self::new(); + // We need to drop the nodes while keeping self.alloc + // We can do this by moving (head, tail, len) into a new list that borrows self.alloc + drop(LinkedList { + head: self.head.take(), + tail: self.tail.take(), + len: mem::take(&mut self.len), + alloc: &self.alloc, + marker: PhantomData, + }); } /// Returns `true` if the `LinkedList` contains an element equal to the @@ -791,7 +841,12 @@ impl<T> LinkedList<T> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn push_front(&mut self, elt: T) { - self.push_front_node(Box::new(Node::new(elt))); + let node = Box::new_in(Node::new(elt), &self.alloc); + let node_ptr = Unique::from(Box::leak(node)); + // SAFETY: node_ptr is a unique pointer to a node we boxed with self.alloc + unsafe { + self.push_front_node(node_ptr); + } } /// Removes the first element and returns it, or `None` if the list is @@ -834,7 +889,12 @@ impl<T> LinkedList<T> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn push_back(&mut self, elt: T) { - self.push_back_node(Box::new(Node::new(elt))); + let node = Box::new_in(Node::new(elt), &self.alloc); + let node_ptr = Unique::from(Box::leak(node)); + // SAFETY: node_ptr is a unique pointer to a node we boxed with self.alloc + unsafe { + self.push_back_node(node_ptr); + } } /// Removes the last element from a list and returns it, or `None` if @@ -884,13 +944,16 @@ impl<T> LinkedList<T> { /// assert_eq!(split.pop_front(), None); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn split_off(&mut self, at: usize) -> LinkedList<T> { + pub fn split_off(&mut self, at: usize) -> LinkedList<T, A> + where + A: Clone, + { let len = self.len(); assert!(at <= len, "Cannot split off at a nonexistent index"); if at == 0 { - return mem::take(self); + return mem::replace(self, Self::new_in(self.alloc.clone())); } else if at == len { - return Self::new(); + return Self::new_in(self.alloc.clone()); } // Below, we iterate towards the `i-1`th node, either from the start or the end, @@ -988,7 +1051,7 @@ impl<T> LinkedList<T> { /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]); /// ``` #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] - pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F> + pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F, A> where F: FnMut(&mut T) -> bool, { @@ -1001,11 +1064,11 @@ impl<T> LinkedList<T> { } #[stable(feature = "rust1", since = "1.0.0")] -unsafe impl<#[may_dangle] T> Drop for LinkedList<T> { +unsafe impl<#[may_dangle] T, A: Allocator> Drop for LinkedList<T, A> { fn drop(&mut self) { - struct DropGuard<'a, T>(&'a mut LinkedList<T>); + struct DropGuard<'a, T, A: Allocator>(&'a mut LinkedList<T, A>); - impl<'a, T> Drop for DropGuard<'a, T> { + impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> { fn drop(&mut self) { // Continue the same loop we do below. This only runs when a destructor has // panicked. If another one panics this will abort. @@ -1013,11 +1076,10 @@ unsafe impl<#[may_dangle] T> Drop for LinkedList<T> { } } - while let Some(node) = self.pop_front_node() { - let guard = DropGuard(self); - drop(node); - mem::forget(guard); - } + // Wrap self so that if a destructor panics, we can try to keep looping + let guard = DropGuard(self); + while guard.0.pop_front_node().is_some() {} + mem::forget(guard); } } @@ -1075,6 +1137,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 +1205,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. @@ -1139,14 +1222,18 @@ impl<T> FusedIterator for IterMut<'_, T> {} /// /// When created, cursors start at the front of the list, or the "ghost" non-element if the list is empty. #[unstable(feature = "linked_list_cursors", issue = "58533")] -pub struct Cursor<'a, T: 'a> { +pub struct Cursor< + 'a, + T: 'a, + #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, +> { index: usize, current: Option<NonNull<Node<T>>>, - list: &'a LinkedList<T>, + list: &'a LinkedList<T, A>, } #[unstable(feature = "linked_list_cursors", issue = "58533")] -impl<T> Clone for Cursor<'_, T> { +impl<T, A: Allocator> Clone for Cursor<'_, T, A> { fn clone(&self) -> Self { let Cursor { index, current, list } = *self; Cursor { index, current, list } @@ -1154,7 +1241,7 @@ impl<T> Clone for Cursor<'_, T> { } #[unstable(feature = "linked_list_cursors", issue = "58533")] -impl<T: fmt::Debug> fmt::Debug for Cursor<'_, T> { +impl<T: fmt::Debug, A: Allocator> fmt::Debug for Cursor<'_, T, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_tuple("Cursor").field(&self.list).field(&self.index()).finish() } @@ -1171,20 +1258,24 @@ impl<T: fmt::Debug> fmt::Debug for Cursor<'_, T> { /// To accommodate this, there is a "ghost" non-element that yields `None` between the head and /// tail of the list. #[unstable(feature = "linked_list_cursors", issue = "58533")] -pub struct CursorMut<'a, T: 'a> { +pub struct CursorMut< + 'a, + T: 'a, + #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, +> { index: usize, current: Option<NonNull<Node<T>>>, - list: &'a mut LinkedList<T>, + list: &'a mut LinkedList<T, A>, } #[unstable(feature = "linked_list_cursors", issue = "58533")] -impl<T: fmt::Debug> fmt::Debug for CursorMut<'_, T> { +impl<T: fmt::Debug, A: Allocator> fmt::Debug for CursorMut<'_, T, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_tuple("CursorMut").field(&self.list).field(&self.index()).finish() } } -impl<'a, T> Cursor<'a, T> { +impl<'a, T, A: Allocator> Cursor<'a, T, A> { /// Returns the cursor position index within the `LinkedList`. /// /// This returns `None` if the cursor is currently pointing to the @@ -1301,7 +1392,7 @@ impl<'a, T> Cursor<'a, T> { } } -impl<'a, T> CursorMut<'a, T> { +impl<'a, T, A: Allocator> CursorMut<'a, T, A> { /// Returns the cursor position index within the `LinkedList`. /// /// This returns `None` if the cursor is currently pointing to the @@ -1406,7 +1497,7 @@ impl<'a, T> CursorMut<'a, T> { /// `CursorMut` is frozen for the lifetime of the `Cursor`. #[must_use] #[unstable(feature = "linked_list_cursors", issue = "58533")] - pub fn as_cursor(&self) -> Cursor<'_, T> { + pub fn as_cursor(&self) -> Cursor<'_, T, A> { Cursor { list: self.list, current: self.current, index: self.index } } } @@ -1414,6 +1505,51 @@ impl<'a, T> CursorMut<'a, T> { // Now the list editing operations impl<'a, T> CursorMut<'a, T> { + /// Inserts the elements from the given `LinkedList` after the current one. + /// + /// If the cursor is pointing at the "ghost" non-element then the new elements are + /// inserted at the start of the `LinkedList`. + #[unstable(feature = "linked_list_cursors", issue = "58533")] + pub fn splice_after(&mut self, list: LinkedList<T>) { + unsafe { + let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() { + Some(parts) => parts, + _ => return, + }; + let node_next = match self.current { + None => self.list.head, + Some(node) => node.as_ref().next, + }; + self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len); + if self.current.is_none() { + // The "ghost" non-element's index has changed. + self.index = self.list.len; + } + } + } + + /// Inserts the elements from the given `LinkedList` before the current one. + /// + /// If the cursor is pointing at the "ghost" non-element then the new elements are + /// inserted at the end of the `LinkedList`. + #[unstable(feature = "linked_list_cursors", issue = "58533")] + pub fn splice_before(&mut self, list: LinkedList<T>) { + unsafe { + let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() { + Some(parts) => parts, + _ => return, + }; + let node_prev = match self.current { + None => self.list.tail, + Some(node) => node.as_ref().prev, + }; + self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len); + self.index += splice_len; + } + } +} + +impl<'a, T, A: Allocator> CursorMut<'a, T, A> { /// Inserts a new element into the `LinkedList` after the current one. /// /// If the cursor is pointing at the "ghost" non-element then the new element is @@ -1421,7 +1557,7 @@ impl<'a, T> CursorMut<'a, T> { #[unstable(feature = "linked_list_cursors", issue = "58533")] pub fn insert_after(&mut self, item: T) { unsafe { - let spliced_node = Box::leak(Box::new(Node::new(item))).into(); + let spliced_node = Box::leak(Box::new_in(Node::new(item), &self.list.alloc)).into(); let node_next = match self.current { None => self.list.head, Some(node) => node.as_ref().next, @@ -1441,7 +1577,7 @@ impl<'a, T> CursorMut<'a, T> { #[unstable(feature = "linked_list_cursors", issue = "58533")] pub fn insert_before(&mut self, item: T) { unsafe { - let spliced_node = Box::leak(Box::new(Node::new(item))).into(); + let spliced_node = Box::leak(Box::new_in(Node::new(item), &self.list.alloc)).into(); let node_prev = match self.current { None => self.list.tail, Some(node) => node.as_ref().prev, @@ -1477,7 +1613,10 @@ impl<'a, T> CursorMut<'a, T> { /// If the cursor is currently pointing to the "ghost" non-element then no element /// is removed and `None` is returned. #[unstable(feature = "linked_list_cursors", issue = "58533")] - pub fn remove_current_as_list(&mut self) -> Option<LinkedList<T>> { + pub fn remove_current_as_list(&mut self) -> Option<LinkedList<T, A>> + where + A: Clone, + { let mut unlinked_node = self.current?; unsafe { self.current = unlinked_node.as_ref().next; @@ -1489,54 +1628,12 @@ impl<'a, T> CursorMut<'a, T> { head: Some(unlinked_node), tail: Some(unlinked_node), len: 1, + alloc: self.list.alloc.clone(), marker: PhantomData, }) } } - /// Inserts the elements from the given `LinkedList` after the current one. - /// - /// If the cursor is pointing at the "ghost" non-element then the new elements are - /// inserted at the start of the `LinkedList`. - #[unstable(feature = "linked_list_cursors", issue = "58533")] - pub fn splice_after(&mut self, list: LinkedList<T>) { - unsafe { - let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() { - Some(parts) => parts, - _ => return, - }; - let node_next = match self.current { - None => self.list.head, - Some(node) => node.as_ref().next, - }; - self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len); - if self.current.is_none() { - // The "ghost" non-element's index has changed. - self.index = self.list.len; - } - } - } - - /// Inserts the elements from the given `LinkedList` before the current one. - /// - /// If the cursor is pointing at the "ghost" non-element then the new elements are - /// inserted at the end of the `LinkedList`. - #[unstable(feature = "linked_list_cursors", issue = "58533")] - pub fn splice_before(&mut self, list: LinkedList<T>) { - unsafe { - let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() { - Some(parts) => parts, - _ => return, - }; - let node_prev = match self.current { - None => self.list.tail, - Some(node) => node.as_ref().prev, - }; - self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len); - self.index += splice_len; - } - } - /// Splits the list into two after the current element. This will return a /// new list consisting of everything after the cursor, with the original /// list retaining everything before. @@ -1544,7 +1641,10 @@ impl<'a, T> CursorMut<'a, T> { /// If the cursor is pointing at the "ghost" non-element then the entire contents /// of the `LinkedList` are moved. #[unstable(feature = "linked_list_cursors", issue = "58533")] - pub fn split_after(&mut self) -> LinkedList<T> { + pub fn split_after(&mut self) -> LinkedList<T, A> + where + A: Clone, + { let split_off_idx = if self.index == self.list.len { 0 } else { self.index + 1 }; if self.index == self.list.len { // The "ghost" non-element's index has changed to 0. @@ -1560,7 +1660,10 @@ impl<'a, T> CursorMut<'a, T> { /// If the cursor is pointing at the "ghost" non-element then the entire contents /// of the `LinkedList` are moved. #[unstable(feature = "linked_list_cursors", issue = "58533")] - pub fn split_before(&mut self) -> LinkedList<T> { + pub fn split_before(&mut self) -> LinkedList<T, A> + where + A: Clone, + { let split_off_idx = self.index; self.index = 0; unsafe { self.list.split_off_before_node(self.current, split_off_idx) } @@ -1570,7 +1673,7 @@ impl<'a, T> CursorMut<'a, T> { /// that the cursor points to is unchanged, even if it is the "ghost" node. /// /// This operation should compute in *O*(1) time. - // `push_front` continues to point to "ghost" when it addes a node to mimic + // `push_front` continues to point to "ghost" when it adds a node to mimic // the behavior of `insert_before` on an empty list. #[unstable(feature = "linked_list_cursors", issue = "58533")] pub fn push_front(&mut self, elt: T) { @@ -1613,7 +1716,7 @@ impl<'a, T> CursorMut<'a, T> { None } else { // We can't point to the node that we pop. Copying the behavior of - // `remove_current`, we move on the the next node in the sequence. + // `remove_current`, we move on to the next node in the sequence. // If the list is of length 1 then we end pointing to the "ghost" // node at index 0, which is expected. if self.list.head == self.current { @@ -1702,11 +1805,15 @@ impl<'a, T> CursorMut<'a, T> { /// An iterator produced by calling `drain_filter` on LinkedList. #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] -pub struct DrainFilter<'a, T: 'a, F: 'a> -where +pub struct DrainFilter< + 'a, + T: 'a, + F: 'a, + #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, +> where F: FnMut(&mut T) -> bool, { - list: &'a mut LinkedList<T>, + list: &'a mut LinkedList<T, A>, it: Option<NonNull<Node<T>>>, pred: F, idx: usize, @@ -1714,7 +1821,7 @@ where } #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] -impl<T, F> Iterator for DrainFilter<'_, T, F> +impl<T, F, A: Allocator> Iterator for DrainFilter<'_, T, F, A> where F: FnMut(&mut T) -> bool, { @@ -1743,16 +1850,16 @@ where } #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] -impl<T, F> Drop for DrainFilter<'_, T, F> +impl<T, F, A: Allocator> Drop for DrainFilter<'_, T, F, A> where F: FnMut(&mut T) -> bool, { fn drop(&mut self) { - struct DropGuard<'r, 'a, T, F>(&'r mut DrainFilter<'a, T, F>) + struct DropGuard<'r, 'a, T, F, A: Allocator>(&'r mut DrainFilter<'a, T, F, A>) where F: FnMut(&mut T) -> bool; - impl<'r, 'a, T, F> Drop for DropGuard<'r, 'a, T, F> + impl<'r, 'a, T, F, A: Allocator> Drop for DropGuard<'r, 'a, T, F, A> where F: FnMut(&mut T) -> bool, { @@ -1780,7 +1887,7 @@ where } #[stable(feature = "rust1", since = "1.0.0")] -impl<T> Iterator for IntoIter<T> { +impl<T, A: Allocator> Iterator for IntoIter<T, A> { type Item = T; #[inline] @@ -1795,7 +1902,7 @@ impl<T> Iterator for IntoIter<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<T> DoubleEndedIterator for IntoIter<T> { +impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> { #[inline] fn next_back(&mut self) -> Option<T> { self.list.pop_back() @@ -1803,10 +1910,24 @@ impl<T> DoubleEndedIterator for IntoIter<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<T> ExactSizeIterator for IntoIter<T> {} +impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {} #[stable(feature = "fused", since = "1.26.0")] -impl<T> FusedIterator for IntoIter<T> {} +impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {} + +#[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> { @@ -1818,19 +1939,19 @@ impl<T> FromIterator<T> for LinkedList<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<T> IntoIterator for LinkedList<T> { +impl<T, A: Allocator> IntoIterator for LinkedList<T, A> { type Item = T; - type IntoIter = IntoIter<T>; + type IntoIter = IntoIter<T, A>; /// Consumes the list into an iterator yielding elements by value. #[inline] - fn into_iter(self) -> IntoIter<T> { + fn into_iter(self) -> IntoIter<T, A> { IntoIter { list: self } } } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T> IntoIterator for &'a LinkedList<T> { +impl<'a, T, A: Allocator> IntoIterator for &'a LinkedList<T, A> { type Item = &'a T; type IntoIter = Iter<'a, T>; @@ -1840,7 +1961,7 @@ impl<'a, T> IntoIterator for &'a LinkedList<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T> IntoIterator for &'a mut LinkedList<T> { +impl<'a, T, A: Allocator> IntoIterator for &'a mut LinkedList<T, A> { type Item = &'a mut T; type IntoIter = IterMut<'a, T>; @@ -1850,7 +1971,7 @@ impl<'a, T> IntoIterator for &'a mut LinkedList<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<T> Extend<T> for LinkedList<T> { +impl<T, A: Allocator> Extend<T> for LinkedList<T, A> { fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { <Self as SpecExtend<I>>::spec_extend(self, iter); } @@ -1861,7 +1982,7 @@ impl<T> Extend<T> for LinkedList<T> { } } -impl<I: IntoIterator> SpecExtend<I> for LinkedList<I::Item> { +impl<I: IntoIterator, A: Allocator> SpecExtend<I> for LinkedList<I::Item, A> { default fn spec_extend(&mut self, iter: I) { iter.into_iter().for_each(move |elt| self.push_back(elt)); } @@ -1874,7 +1995,7 @@ impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> { } #[stable(feature = "extend_ref", since = "1.2.0")] -impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> { +impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for LinkedList<T, A> { fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { self.extend(iter.into_iter().cloned()); } @@ -1886,7 +2007,7 @@ impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<T: PartialEq> PartialEq for LinkedList<T> { +impl<T: PartialEq, A: Allocator> PartialEq for LinkedList<T, A> { fn eq(&self, other: &Self) -> bool { self.len() == other.len() && self.iter().eq(other) } @@ -1897,17 +2018,17 @@ impl<T: PartialEq> PartialEq for LinkedList<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<T: Eq> Eq for LinkedList<T> {} +impl<T: Eq, A: Allocator> Eq for LinkedList<T, A> {} #[stable(feature = "rust1", since = "1.0.0")] -impl<T: PartialOrd> PartialOrd for LinkedList<T> { +impl<T: PartialOrd, A: Allocator> PartialOrd for LinkedList<T, A> { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.iter().partial_cmp(other) } } #[stable(feature = "rust1", since = "1.0.0")] -impl<T: Ord> Ord for LinkedList<T> { +impl<T: Ord, A: Allocator> Ord for LinkedList<T, A> { #[inline] fn cmp(&self, other: &Self) -> Ordering { self.iter().cmp(other) @@ -1915,9 +2036,11 @@ impl<T: Ord> Ord for LinkedList<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<T: Clone> Clone for LinkedList<T> { +impl<T: Clone, A: Allocator + Clone> Clone for LinkedList<T, A> { fn clone(&self) -> Self { - self.iter().cloned().collect() + let mut list = Self::new_in(self.alloc.clone()); + list.extend(self.iter().cloned()); + list } fn clone_from(&mut self, other: &Self) { @@ -1935,14 +2058,14 @@ impl<T: Clone> Clone for LinkedList<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<T: fmt::Debug> fmt::Debug for LinkedList<T> { +impl<T: fmt::Debug, A: Allocator> fmt::Debug for LinkedList<T, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self).finish() } } #[stable(feature = "rust1", since = "1.0.0")] -impl<T: Hash> Hash for LinkedList<T> { +impl<T: Hash, A: Allocator> Hash for LinkedList<T, A> { fn hash<H: Hasher>(&self, state: &mut H) { state.write_length_prefix(self.len()); for elt in self { @@ -1982,10 +2105,10 @@ fn assert_covariance() { } #[stable(feature = "rust1", since = "1.0.0")] -unsafe impl<T: Send> Send for LinkedList<T> {} +unsafe impl<T: Send, A: Allocator + Send> Send for LinkedList<T, A> {} #[stable(feature = "rust1", since = "1.0.0")] -unsafe impl<T: Sync> Sync for LinkedList<T> {} +unsafe impl<T: Sync, A: Allocator + Sync> Sync for LinkedList<T, A> {} #[stable(feature = "rust1", since = "1.0.0")] unsafe impl<T: Sync> Send for Iter<'_, T> {} @@ -2000,13 +2123,13 @@ unsafe impl<T: Send> Send for IterMut<'_, T> {} unsafe impl<T: Sync> Sync for IterMut<'_, T> {} #[unstable(feature = "linked_list_cursors", issue = "58533")] -unsafe impl<T: Sync> Send for Cursor<'_, T> {} +unsafe impl<T: Sync, A: Allocator + Sync> Send for Cursor<'_, T, A> {} #[unstable(feature = "linked_list_cursors", issue = "58533")] -unsafe impl<T: Sync> Sync for Cursor<'_, T> {} +unsafe impl<T: Sync, A: Allocator + Sync> Sync for Cursor<'_, T, A> {} #[unstable(feature = "linked_list_cursors", issue = "58533")] -unsafe impl<T: Send> Send for CursorMut<'_, T> {} +unsafe impl<T: Send, A: Allocator + Send> Send for CursorMut<'_, T, A> {} #[unstable(feature = "linked_list_cursors", issue = "58533")] -unsafe impl<T: Sync> Sync for CursorMut<'_, T> {} +unsafe impl<T: Sync, A: Allocator + Sync> Sync for CursorMut<'_, T, A> {} diff --git a/library/alloc/src/collections/linked_list/tests.rs b/library/alloc/src/collections/linked_list/tests.rs index f8fbfa1bfbc..04594d55b6a 100644 --- a/library/alloc/src/collections/linked_list/tests.rs +++ b/library/alloc/src/collections/linked_list/tests.rs @@ -1,10 +1,11 @@ use super::*; +use crate::testing::crash_test::{CrashTestDummy, Panic}; use crate::vec::Vec; use std::panic::{catch_unwind, AssertUnwindSafe}; use std::thread; -use rand::{thread_rng, RngCore}; +use rand::RngCore; #[test] fn test_basic() { @@ -480,12 +481,12 @@ fn test_split_off_2() { } } -fn fuzz_test(sz: i32) { +fn fuzz_test(sz: i32, rng: &mut impl RngCore) { let mut m: LinkedList<_> = LinkedList::new(); let mut v = vec![]; for i in 0..sz { check_links(&m); - let r: u8 = thread_rng().next_u32() as u8; + let r: u8 = rng.next_u32() as u8; match r % 6 { 0 => { m.pop_back(); @@ -520,11 +521,12 @@ fn fuzz_test(sz: i32) { #[test] fn test_fuzz() { + let mut rng = crate::test_helpers::test_rng(); for _ in 0..25 { - fuzz_test(3); - fuzz_test(16); + fuzz_test(3, &mut rng); + fuzz_test(16, &mut rng); #[cfg(not(miri))] // Miri is too slow - fuzz_test(189); + fuzz_test(189, &mut rng); } } @@ -984,35 +986,34 @@ fn drain_filter_complex() { #[test] fn drain_filter_drop_panic_leak() { - static mut DROPS: i32 = 0; - - struct D(bool); - - impl Drop for D { - fn drop(&mut self) { - unsafe { - DROPS += 1; - } - - if self.0 { - panic!("panic in `drop`"); - } - } - } - + let d0 = CrashTestDummy::new(0); + let d1 = CrashTestDummy::new(1); + let d2 = CrashTestDummy::new(2); + let d3 = CrashTestDummy::new(3); + let d4 = CrashTestDummy::new(4); + let d5 = CrashTestDummy::new(5); + let d6 = CrashTestDummy::new(6); + let d7 = CrashTestDummy::new(7); let mut q = LinkedList::new(); - q.push_back(D(false)); - q.push_back(D(false)); - q.push_back(D(false)); - q.push_back(D(false)); - q.push_back(D(false)); - q.push_front(D(false)); - q.push_front(D(true)); - q.push_front(D(false)); - - catch_unwind(AssertUnwindSafe(|| drop(q.drain_filter(|_| true)))).ok(); - - assert_eq!(unsafe { DROPS }, 8); + q.push_back(d3.spawn(Panic::Never)); + q.push_back(d4.spawn(Panic::Never)); + q.push_back(d5.spawn(Panic::Never)); + q.push_back(d6.spawn(Panic::Never)); + q.push_back(d7.spawn(Panic::Never)); + q.push_front(d2.spawn(Panic::Never)); + q.push_front(d1.spawn(Panic::InDrop)); + q.push_front(d0.spawn(Panic::Never)); + + catch_unwind(AssertUnwindSafe(|| drop(q.drain_filter(|_| true)))).unwrap_err(); + + assert_eq!(d0.dropped(), 1); + assert_eq!(d1.dropped(), 1); + assert_eq!(d2.dropped(), 1); + assert_eq!(d3.dropped(), 1); + assert_eq!(d4.dropped(), 1); + assert_eq!(d5.dropped(), 1); + assert_eq!(d6.dropped(), 1); + assert_eq!(d7.dropped(), 1); assert!(q.is_empty()); } diff --git a/library/alloc/src/collections/mod.rs b/library/alloc/src/collections/mod.rs index 628a5b15567..3e0b0f73550 100644 --- a/library/alloc/src/collections/mod.rs +++ b/library/alloc/src/collections/mod.rs @@ -139,7 +139,7 @@ impl Display for TryReserveError { " because the computed capacity exceeded the collection's maximum" } TryReserveErrorKind::AllocError { .. } => { - " because the memory allocator returned a error" + " because the memory allocator returned an error" } }; fmt.write_str(reason) @@ -152,3 +152,6 @@ trait SpecExtend<I: IntoIterator> { /// Extends `self` with the contents of the given iterator. fn spec_extend(&mut self, iter: I); } + +#[stable(feature = "try_reserve", since = "1.57.0")] +impl core::error::Error for TryReserveError {} diff --git a/library/alloc/src/collections/vec_deque/drain.rs b/library/alloc/src/collections/vec_deque/drain.rs index 05f94da6de7..0be274a3822 100644 --- a/library/alloc/src/collections/vec_deque/drain.rs +++ b/library/alloc/src/collections/vec_deque/drain.rs @@ -1,10 +1,12 @@ use core::iter::FusedIterator; -use core::ptr::{self, NonNull}; -use core::{fmt, mem}; +use core::marker::PhantomData; +use core::mem::{self, SizedTypeProperties}; +use core::ptr::NonNull; +use core::{fmt, ptr}; use crate::alloc::{Allocator, Global}; -use super::{count, Iter, VecDeque}; +use super::VecDeque; /// A draining iterator over the elements of a `VecDeque`. /// @@ -18,20 +20,56 @@ pub struct Drain< T: 'a, #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, > { - after_tail: usize, - after_head: usize, - iter: Iter<'a, T>, + // We can't just use a &mut VecDeque<T, A>, as that would make Drain invariant over T + // and we want it to be covariant instead deque: NonNull<VecDeque<T, A>>, + // drain_start is stored in deque.len + drain_len: usize, + // index into the logical array, not the physical one (always lies in [0..deque.len)) + idx: usize, + // number of elements after the drain range + tail_len: usize, + remaining: usize, + // Needed to make Drain covariant over T + _marker: PhantomData<&'a T>, } impl<'a, T, A: Allocator> Drain<'a, T, A> { pub(super) unsafe fn new( - after_tail: usize, - after_head: usize, - iter: Iter<'a, T>, - deque: NonNull<VecDeque<T, A>>, + deque: &'a mut VecDeque<T, A>, + drain_start: usize, + drain_len: usize, ) -> Self { - Drain { after_tail, after_head, iter, deque } + let orig_len = mem::replace(&mut deque.len, drain_start); + let tail_len = orig_len - drain_start - drain_len; + Drain { + deque: NonNull::from(deque), + drain_len, + idx: drain_start, + tail_len, + remaining: drain_len, + _marker: PhantomData, + } + } + + // 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(); + + // 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)) + } } } @@ -39,9 +77,10 @@ impl<'a, T, A: Allocator> Drain<'a, T, A> { impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_tuple("Drain") - .field(&self.after_tail) - .field(&self.after_head) - .field(&self.iter) + .field(&self.drain_len) + .field(&self.idx) + .field(&self.tail_len) + .field(&self.remaining) .finish() } } @@ -58,57 +97,81 @@ impl<T, A: Allocator> Drop for Drain<'_, T, A> { impl<'r, 'a, T, A: Allocator> Drop for DropGuard<'r, 'a, T, A> { fn drop(&mut self) { - self.0.for_each(drop); + if self.0.remaining != 0 { + unsafe { + // SAFETY: We just checked that `self.remaining != 0`. + let (front, back) = self.0.as_slices(); + ptr::drop_in_place(front); + ptr::drop_in_place(back); + } + } let source_deque = unsafe { self.0.deque.as_mut() }; - // T = source_deque_tail; H = source_deque_head; t = drain_tail; h = drain_head - // - // T t h H - // [. . . o o x x o o . . .] - // - let orig_tail = source_deque.tail; - let drain_tail = source_deque.head; - let drain_head = self.0.after_tail; - let orig_head = self.0.after_head; + let drain_start = source_deque.len(); + let drain_len = self.0.drain_len; + let drain_end = drain_start + drain_len; - let tail_len = count(orig_tail, drain_tail, source_deque.cap()); - let head_len = count(drain_head, orig_head, source_deque.cap()); + let orig_len = self.0.tail_len + drain_end; - // Restore the original head value - source_deque.head = orig_head; + if T::IS_ZST { + // no need to copy around any memory if T is a ZST + source_deque.len = orig_len - drain_len; + return; + } + + let head_len = drain_start; + let tail_len = self.0.tail_len; - match (tail_len, head_len) { + match (head_len, tail_len) { (0, 0) => { source_deque.head = 0; - source_deque.tail = 0; + source_deque.len = 0; } (0, _) => { - source_deque.tail = drain_head; + source_deque.head = source_deque.to_physical_idx(drain_len); + source_deque.len = orig_len - drain_len; } (_, 0) => { - source_deque.head = drain_tail; + source_deque.len = orig_len - drain_len; } _ => unsafe { - if tail_len <= head_len { - source_deque.tail = source_deque.wrap_sub(drain_head, tail_len); - source_deque.wrap_copy(source_deque.tail, orig_tail, tail_len); + if head_len <= tail_len { + source_deque.wrap_copy( + source_deque.head, + source_deque.to_physical_idx(drain_len), + head_len, + ); + source_deque.head = source_deque.to_physical_idx(drain_len); + source_deque.len = orig_len - drain_len; } else { - source_deque.head = source_deque.wrap_add(drain_tail, head_len); - source_deque.wrap_copy(drain_tail, drain_head, head_len); + source_deque.wrap_copy( + source_deque.to_physical_idx(head_len + drain_len), + source_deque.to_physical_idx(head_len), + tail_len, + ); + source_deque.len = orig_len - drain_len; } }, } } } - while let Some(item) = self.next() { - let guard = DropGuard(self); - drop(item); - mem::forget(guard); + let guard = DropGuard(self); + if guard.0.remaining != 0 { + unsafe { + // SAFETY: We just checked that `self.remaining != 0`. + let (front, back) = guard.0.as_slices(); + // since idx is a logical index, we don't need to worry about wrapping. + guard.0.idx += front.len(); + guard.0.remaining -= front.len(); + ptr::drop_in_place(front); + guard.0.remaining = 0; + ptr::drop_in_place(back); + } } - DropGuard(self); + // Dropping `guard` handles moving the remaining elements into place. } } @@ -118,12 +181,19 @@ impl<T, A: Allocator> Iterator for Drain<'_, T, A> { #[inline] fn next(&mut self) -> Option<T> { - self.iter.next().map(|elt| unsafe { ptr::read(elt) }) + if self.remaining == 0 { + return None; + } + let wrapped_idx = unsafe { self.deque.as_ref().to_physical_idx(self.idx) }; + self.idx += 1; + self.remaining -= 1; + Some(unsafe { self.deque.as_mut().buffer_read(wrapped_idx) }) } #[inline] fn size_hint(&self) -> (usize, Option<usize>) { - self.iter.size_hint() + let len = self.remaining; + (len, Some(len)) } } @@ -131,7 +201,12 @@ impl<T, A: Allocator> Iterator for Drain<'_, T, A> { impl<T, A: Allocator> DoubleEndedIterator for Drain<'_, T, A> { #[inline] fn next_back(&mut self) -> Option<T> { - self.iter.next_back().map(|elt| unsafe { ptr::read(elt) }) + if self.remaining == 0 { + return None; + } + self.remaining -= 1; + let wrapped_idx = unsafe { self.deque.as_ref().to_physical_idx(self.idx + self.remaining) }; + Some(unsafe { self.deque.as_mut().buffer_read(wrapped_idx) }) } } diff --git a/library/alloc/src/collections/vec_deque/into_iter.rs b/library/alloc/src/collections/vec_deque/into_iter.rs index 55f6138cd0f..d9e274df0f5 100644 --- a/library/alloc/src/collections/vec_deque/into_iter.rs +++ b/library/alloc/src/collections/vec_deque/into_iter.rs @@ -1,5 +1,6 @@ -use core::fmt; 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< @@ -25,6 +25,10 @@ impl<T, A: Allocator> IntoIter<T, A> { pub(super) fn new(inner: VecDeque<T, A>) -> Self { IntoIter { inner } } + + pub(super) fn into_vecdeque(self) -> VecDeque<T, A> { + self.inner + } } #[stable(feature = "collection_debug", since = "1.17.0")] @@ -48,6 +52,127 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { let len = self.inner.len(); (len, Some(len)) } + + #[inline] + fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { + let len = self.inner.len; + let rem = if len < n { + self.inner.clear(); + n - len + } else { + self.inner.drain(..n); + 0 + }; + NonZeroUsize::new(rem).map_or(Ok(()), Err) + } + + #[inline] + fn count(self) -> usize { + self.inner.len + } + + fn try_fold<B, F, R>(&mut self, mut init: B, mut f: F) -> R + where + F: FnMut(B, Self::Item) -> R, + R: Try<Output = B>, + { + struct Guard<'a, T, A: Allocator> { + deque: &'a mut VecDeque<T, A>, + // `consumed <= deque.len` always holds. + consumed: usize, + } + + impl<'a, T, A: Allocator> Drop for Guard<'a, T, A> { + fn drop(&mut self) { + self.deque.len -= self.consumed; + self.deque.head = self.deque.to_physical_idx(self.consumed); + } + } + + let mut guard = Guard { deque: &mut self.inner, consumed: 0 }; + + let (head, tail) = guard.deque.as_slices(); + + init = head + .iter() + .map(|elem| { + guard.consumed += 1; + // SAFETY: Because we incremented `guard.consumed`, the + // deque effectively forgot the element, so we can take + // ownership + unsafe { ptr::read(elem) } + }) + .try_fold(init, &mut f)?; + + tail.iter() + .map(|elem| { + guard.consumed += 1; + // SAFETY: Same as above. + unsafe { ptr::read(elem) } + }) + .try_fold(init, &mut f) + } + + #[inline] + fn fold<B, F>(mut self, init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + match self.try_fold(init, |b, item| Ok::<B, !>(f(b, item))) { + Ok(b) => b, + Err(e) => match e {}, + } + } + + #[inline] + fn last(mut self) -> Option<Self::Item> { + self.inner.pop_back() + } + + fn next_chunk<const N: usize>( + &mut self, + ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>> { + let mut raw_arr = MaybeUninit::uninit_array(); + let raw_arr_ptr = raw_arr.as_mut_ptr().cast(); + let (head, tail) = self.inner.as_slices(); + + if head.len() >= N { + // SAFETY: By manually adjusting the head and length of the deque, we effectively + // make it forget the first `N` elements, so taking ownership of them is safe. + unsafe { ptr::copy_nonoverlapping(head.as_ptr(), raw_arr_ptr, N) }; + self.inner.head = self.inner.to_physical_idx(N); + self.inner.len -= N; + // SAFETY: We initialized the entire array with items from `head` + return Ok(unsafe { raw_arr.transpose().assume_init() }); + } + + // SAFETY: Same argument as above. + unsafe { ptr::copy_nonoverlapping(head.as_ptr(), raw_arr_ptr, head.len()) }; + let remaining = N - head.len(); + + if tail.len() >= remaining { + // SAFETY: Same argument as above. + unsafe { + ptr::copy_nonoverlapping(tail.as_ptr(), raw_arr_ptr.add(head.len()), remaining) + }; + self.inner.head = self.inner.to_physical_idx(N); + self.inner.len -= N; + // SAFETY: We initialized the entire array with items from `head` and `tail` + Ok(unsafe { raw_arr.transpose().assume_init() }) + } else { + // SAFETY: Same argument as above. + unsafe { + ptr::copy_nonoverlapping(tail.as_ptr(), raw_arr_ptr.add(head.len()), tail.len()) + }; + let init = head.len() + tail.len(); + // We completely drained all the deques elements. + self.inner.head = 0; + self.inner.len = 0; + // SAFETY: We copied all elements from both slices to the beginning of the array, so + // the given range is initialized. + Err(unsafe { array::IntoIter::new_unchecked(raw_arr, 0..init) }) + } + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -56,10 +181,74 @@ impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> { fn next_back(&mut self) -> Option<T> { self.inner.pop_back() } + + #[inline] + fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> { + let len = self.inner.len; + let rem = if len < n { + self.inner.clear(); + 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 + where + F: FnMut(B, Self::Item) -> R, + R: Try<Output = B>, + { + struct Guard<'a, T, A: Allocator> { + deque: &'a mut VecDeque<T, A>, + // `consumed <= deque.len` always holds. + consumed: usize, + } + + impl<'a, T, A: Allocator> Drop for Guard<'a, T, A> { + fn drop(&mut self) { + self.deque.len -= self.consumed; + } + } + + let mut guard = Guard { deque: &mut self.inner, consumed: 0 }; + + let (head, tail) = guard.deque.as_slices(); + + init = tail + .iter() + .map(|elem| { + guard.consumed += 1; + // SAFETY: See `try_fold`'s safety comment. + unsafe { ptr::read(elem) } + }) + .try_rfold(init, &mut f)?; + + head.iter() + .map(|elem| { + guard.consumed += 1; + // SAFETY: Same as above. + unsafe { ptr::read(elem) } + }) + .try_rfold(init, &mut f) + } + + #[inline] + fn rfold<B, F>(mut self, init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + match self.try_rfold(init, |b, item| Ok::<B, !>(f(b, item))) { + Ok(b) => b, + Err(e) => match e {}, + } + } } #[stable(feature = "rust1", since = "1.0.0")] impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> { + #[inline] fn is_empty(&self) -> bool { self.inner.is_empty() } diff --git a/library/alloc/src/collections/vec_deque/iter.rs b/library/alloc/src/collections/vec_deque/iter.rs index e696d7ed636..646a2a991e7 100644 --- a/library/alloc/src/collections/vec_deque/iter.rs +++ b/library/alloc/src/collections/vec_deque/iter.rs @@ -1,9 +1,7 @@ -use core::fmt; use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce}; -use core::mem::MaybeUninit; +use core::num::NonZeroUsize; use core::ops::Try; - -use super::{count, wrap_index, RingSlices}; +use core::{fmt, mem, slice}; /// An iterator over the elements of a `VecDeque`. /// @@ -13,30 +11,20 @@ use super::{count, wrap_index, RingSlices}; /// [`iter`]: super::VecDeque::iter #[stable(feature = "rust1", since = "1.0.0")] pub struct Iter<'a, T: 'a> { - ring: &'a [MaybeUninit<T>], - tail: usize, - head: usize, + i1: slice::Iter<'a, T>, + i2: slice::Iter<'a, T>, } impl<'a, T> Iter<'a, T> { - pub(super) fn new(ring: &'a [MaybeUninit<T>], tail: usize, head: usize) -> Self { - Iter { ring, tail, head } + pub(super) fn new(i1: slice::Iter<'a, T>, i2: slice::Iter<'a, T>) -> Self { + Self { i1, i2 } } } #[stable(feature = "collection_debug", since = "1.17.0")] impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail); - // Safety: - // - `self.head` and `self.tail` in a ring buffer are always valid indices. - // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized. - unsafe { - f.debug_tuple("Iter") - .field(&MaybeUninit::slice_assume_init_ref(front)) - .field(&MaybeUninit::slice_assume_init_ref(back)) - .finish() - } + f.debug_tuple("Iter").field(&self.i1.as_slice()).field(&self.i2.as_slice()).finish() } } @@ -44,7 +32,7 @@ impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { #[stable(feature = "rust1", since = "1.0.0")] impl<T> Clone for Iter<'_, T> { fn clone(&self) -> Self { - Iter { ring: self.ring, tail: self.tail, head: self.head } + Iter { i1: self.i1.clone(), i2: self.i2.clone() } } } @@ -54,72 +42,52 @@ impl<'a, T> Iterator for Iter<'a, T> { #[inline] fn next(&mut self) -> Option<&'a T> { - if self.tail == self.head { - return None; + match self.i1.next() { + Some(val) => Some(val), + None => { + // most of the time, the iterator will either always + // call next(), or always call next_back(). By swapping + // the iterators once the first one is empty, we ensure + // that the first branch is taken as often as possible, + // without sacrificing correctness, as i1 is empty anyways + mem::swap(&mut self.i1, &mut self.i2); + self.i1.next() + } + } + } + + 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()) + } } - let tail = self.tail; - self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len()); - // Safety: - // - `self.tail` in a ring buffer is always a valid index. - // - `self.head` and `self.tail` equality is checked above. - unsafe { Some(self.ring.get_unchecked(tail).assume_init_ref()) } } #[inline] fn size_hint(&self) -> (usize, Option<usize>) { - let len = count(self.tail, self.head, self.ring.len()); + let len = self.len(); (len, Some(len)) } - fn fold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc + fn fold<Acc, F>(self, accum: Acc, mut f: F) -> Acc where F: FnMut(Acc, Self::Item) -> Acc, { - let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail); - // Safety: - // - `self.head` and `self.tail` in a ring buffer are always valid indices. - // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized. - unsafe { - accum = MaybeUninit::slice_assume_init_ref(front).iter().fold(accum, &mut f); - MaybeUninit::slice_assume_init_ref(back).iter().fold(accum, &mut f) - } + let accum = self.i1.fold(accum, &mut f); + self.i2.fold(accum, &mut f) } fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where - Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Output = B>, { - let (mut iter, final_res); - if self.tail <= self.head { - // Safety: single slice self.ring[self.tail..self.head] is initialized. - iter = unsafe { MaybeUninit::slice_assume_init_ref(&self.ring[self.tail..self.head]) } - .iter(); - final_res = iter.try_fold(init, &mut f); - } else { - // Safety: two slices: self.ring[self.tail..], self.ring[..self.head] both are initialized. - let (front, back) = self.ring.split_at(self.tail); - - let mut back_iter = unsafe { MaybeUninit::slice_assume_init_ref(back).iter() }; - let res = back_iter.try_fold(init, &mut f); - let len = self.ring.len(); - self.tail = (self.ring.len() - back_iter.len()) & (len - 1); - iter = unsafe { MaybeUninit::slice_assume_init_ref(&front[..self.head]).iter() }; - final_res = iter.try_fold(res?, &mut f); - } - self.tail = self.head - iter.len(); - final_res - } - - fn nth(&mut self, n: usize) -> Option<Self::Item> { - if n >= count(self.tail, self.head, self.ring.len()) { - self.tail = self.head; - None - } else { - self.tail = wrap_index(self.tail.wrapping_add(n), self.ring.len()); - self.next() - } + let acc = self.i1.try_fold(init, &mut f)?; + self.i2.try_fold(acc, &mut f) } #[inline] @@ -132,8 +100,12 @@ impl<'a, T> Iterator for Iter<'a, T> { // Safety: The TrustedRandomAccess contract requires that callers only pass an index // that is in bounds. unsafe { - let idx = wrap_index(self.tail.wrapping_add(idx), self.ring.len()); - self.ring.get_unchecked(idx).assume_init_ref() + let i1_len = self.i1.len(); + if idx < i1_len { + self.i1.__iterator_get_unchecked(idx) + } else { + self.i2.__iterator_get_unchecked(idx - i1_len) + } } } } @@ -142,63 +114,56 @@ impl<'a, T> Iterator for Iter<'a, T> { impl<'a, T> DoubleEndedIterator for Iter<'a, T> { #[inline] fn next_back(&mut self) -> Option<&'a T> { - if self.tail == self.head { - return None; + match self.i2.next_back() { + Some(val) => Some(val), + None => { + // most of the time, the iterator will either always + // call next(), or always call next_back(). By swapping + // the iterators once the second one is empty, we ensure + // that the first branch is taken as often as possible, + // without sacrificing correctness, as i2 is empty anyways + mem::swap(&mut self.i1, &mut self.i2); + self.i2.next_back() + } + } + } + + 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()) + } } - self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len()); - // Safety: - // - `self.head` in a ring buffer is always a valid index. - // - `self.head` and `self.tail` equality is checked above. - unsafe { Some(self.ring.get_unchecked(self.head).assume_init_ref()) } } - fn rfold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc + fn rfold<Acc, F>(self, accum: Acc, mut f: F) -> Acc where F: FnMut(Acc, Self::Item) -> Acc, { - let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail); - // Safety: - // - `self.head` and `self.tail` in a ring buffer are always valid indices. - // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized. - unsafe { - accum = MaybeUninit::slice_assume_init_ref(back).iter().rfold(accum, &mut f); - MaybeUninit::slice_assume_init_ref(front).iter().rfold(accum, &mut f) - } + let accum = self.i2.rfold(accum, &mut f); + self.i1.rfold(accum, &mut f) } fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where - Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Output = B>, { - let (mut iter, final_res); - if self.tail <= self.head { - // Safety: single slice self.ring[self.tail..self.head] is initialized. - iter = unsafe { - MaybeUninit::slice_assume_init_ref(&self.ring[self.tail..self.head]).iter() - }; - final_res = iter.try_rfold(init, &mut f); - } else { - // Safety: two slices: self.ring[self.tail..], self.ring[..self.head] both are initialized. - let (front, back) = self.ring.split_at(self.tail); - - let mut front_iter = - unsafe { MaybeUninit::slice_assume_init_ref(&front[..self.head]).iter() }; - let res = front_iter.try_rfold(init, &mut f); - self.head = front_iter.len(); - iter = unsafe { MaybeUninit::slice_assume_init_ref(back).iter() }; - final_res = iter.try_rfold(res?, &mut f); - } - self.head = self.tail + iter.len(); - final_res + let acc = self.i2.try_rfold(init, &mut f)?; + self.i1.try_rfold(acc, &mut f) } } #[stable(feature = "rust1", since = "1.0.0")] impl<T> ExactSizeIterator for Iter<'_, T> { + fn len(&self) -> usize { + self.i1.len() + self.i2.len() + } + fn is_empty(&self) -> bool { - self.head == self.tail + self.i1.is_empty() && self.i2.is_empty() } } diff --git a/library/alloc/src/collections/vec_deque/iter_mut.rs b/library/alloc/src/collections/vec_deque/iter_mut.rs index b78c0d5e1b3..7defbb1090f 100644 --- a/library/alloc/src/collections/vec_deque/iter_mut.rs +++ b/library/alloc/src/collections/vec_deque/iter_mut.rs @@ -1,8 +1,7 @@ -use core::fmt; use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce}; -use core::marker::PhantomData; - -use super::{count, wrap_index, RingSlices}; +use core::num::NonZeroUsize; +use core::ops::Try; +use core::{fmt, mem, slice}; /// A mutable iterator over the elements of a `VecDeque`. /// @@ -12,39 +11,20 @@ use super::{count, wrap_index, RingSlices}; /// [`iter_mut`]: super::VecDeque::iter_mut #[stable(feature = "rust1", since = "1.0.0")] pub struct IterMut<'a, T: 'a> { - // Internal safety invariant: the entire slice is dereferenceable. - ring: *mut [T], - tail: usize, - head: usize, - phantom: PhantomData<&'a mut [T]>, + i1: slice::IterMut<'a, T>, + i2: slice::IterMut<'a, T>, } impl<'a, T> IterMut<'a, T> { - pub(super) unsafe fn new( - ring: *mut [T], - tail: usize, - head: usize, - phantom: PhantomData<&'a mut [T]>, - ) -> Self { - IterMut { ring, tail, head, phantom } + pub(super) fn new(i1: slice::IterMut<'a, T>, i2: slice::IterMut<'a, T>) -> Self { + Self { i1, i2 } } } -// SAFETY: we do nothing thread-local and there is no interior mutability, -// so the usual structural `Send`/`Sync` apply. -#[stable(feature = "rust1", since = "1.0.0")] -unsafe impl<T: Send> Send for IterMut<'_, T> {} -#[stable(feature = "rust1", since = "1.0.0")] -unsafe impl<T: Sync> Sync for IterMut<'_, T> {} - #[stable(feature = "collection_debug", since = "1.17.0")] impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail); - // SAFETY: these are the elements we have not handed out yet, so aliasing is fine. - // The `IterMut` invariant also ensures everything is dereferenceable. - let (front, back) = unsafe { (&*front, &*back) }; - f.debug_tuple("IterMut").field(&front).field(&back).finish() + f.debug_tuple("IterMut").field(&self.i1.as_slice()).field(&self.i2.as_slice()).finish() } } @@ -54,44 +34,51 @@ impl<'a, T> Iterator for IterMut<'a, T> { #[inline] fn next(&mut self) -> Option<&'a mut T> { - if self.tail == self.head { - return None; + match self.i1.next() { + Some(val) => Some(val), + None => { + // most of the time, the iterator will either always + // call next(), or always call next_back(). By swapping + // the iterators once the first one is empty, we ensure + // that the first branch is taken as often as possible, + // without sacrificing correctness, as i1 is empty anyways + mem::swap(&mut self.i1, &mut self.i2); + self.i1.next() + } } - let tail = self.tail; - self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len()); + } - unsafe { - let elem = self.ring.get_unchecked_mut(tail); - Some(&mut *elem) + 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] fn size_hint(&self) -> (usize, Option<usize>) { - let len = count(self.tail, self.head, self.ring.len()); + let len = self.len(); (len, Some(len)) } - fn fold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc + fn fold<Acc, F>(self, accum: Acc, mut f: F) -> Acc where F: FnMut(Acc, Self::Item) -> Acc, { - let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail); - // SAFETY: these are the elements we have not handed out yet, so aliasing is fine. - // The `IterMut` invariant also ensures everything is dereferenceable. - let (front, back) = unsafe { (&mut *front, &mut *back) }; - accum = front.iter_mut().fold(accum, &mut f); - back.iter_mut().fold(accum, &mut f) + let accum = self.i1.fold(accum, &mut f); + self.i2.fold(accum, &mut f) } - fn nth(&mut self, n: usize) -> Option<Self::Item> { - if n >= count(self.tail, self.head, self.ring.len()) { - self.tail = self.head; - None - } else { - self.tail = wrap_index(self.tail.wrapping_add(n), self.ring.len()); - self.next() - } + fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R + where + F: FnMut(B, Self::Item) -> R, + R: Try<Output = B>, + { + let acc = self.i1.try_fold(init, &mut f)?; + self.i2.try_fold(acc, &mut f) } #[inline] @@ -104,8 +91,12 @@ impl<'a, T> Iterator for IterMut<'a, T> { // Safety: The TrustedRandomAccess contract requires that callers only pass an index // that is in bounds. unsafe { - let idx = wrap_index(self.tail.wrapping_add(idx), self.ring.len()); - &mut *self.ring.get_unchecked_mut(idx) + let i1_len = self.i1.len(); + if idx < i1_len { + self.i1.__iterator_get_unchecked(idx) + } else { + self.i2.__iterator_get_unchecked(idx - i1_len) + } } } } @@ -114,34 +105,56 @@ impl<'a, T> Iterator for IterMut<'a, T> { impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { #[inline] fn next_back(&mut self) -> Option<&'a mut T> { - if self.tail == self.head { - return None; + match self.i2.next_back() { + Some(val) => Some(val), + None => { + // most of the time, the iterator will either always + // call next(), or always call next_back(). By swapping + // the iterators once the first one is empty, we ensure + // that the first branch is taken as often as possible, + // without sacrificing correctness, as i2 is empty anyways + mem::swap(&mut self.i1, &mut self.i2); + self.i2.next_back() + } } - self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len()); + } - unsafe { - let elem = self.ring.get_unchecked_mut(self.head); - Some(&mut *elem) + 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, mut accum: Acc, mut f: F) -> Acc + fn rfold<Acc, F>(self, accum: Acc, mut f: F) -> Acc where F: FnMut(Acc, Self::Item) -> Acc, { - let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail); - // SAFETY: these are the elements we have not handed out yet, so aliasing is fine. - // The `IterMut` invariant also ensures everything is dereferenceable. - let (front, back) = unsafe { (&mut *front, &mut *back) }; - accum = back.iter_mut().rfold(accum, &mut f); - front.iter_mut().rfold(accum, &mut f) + let accum = self.i2.rfold(accum, &mut f); + self.i1.rfold(accum, &mut f) + } + + fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R + where + F: FnMut(B, Self::Item) -> R, + R: Try<Output = B>, + { + let acc = self.i2.try_rfold(init, &mut f)?; + self.i1.try_rfold(acc, &mut f) } } #[stable(feature = "rust1", since = "1.0.0")] impl<T> ExactSizeIterator for IterMut<'_, T> { + fn len(&self) -> usize { + self.i1.len() + self.i2.len() + } + fn is_empty(&self) -> bool { - self.head == self.tail + self.i1.is_empty() && self.i2.is_empty() } } diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs index 4d895d83745..896da37f94c 100644 --- a/library/alloc/src/collections/vec_deque/mod.rs +++ b/library/alloc/src/collections/vec_deque/mod.rs @@ -10,13 +10,18 @@ use core::cmp::{self, Ordering}; use core::fmt; use core::hash::{Hash, Hasher}; -use core::iter::{repeat_with, FromIterator}; -use core::marker::PhantomData; -use core::mem::{self, ManuallyDrop, MaybeUninit}; +use core::iter::{repeat_n, repeat_with, ByRefSized}; +use core::mem::{ManuallyDrop, SizedTypeProperties}; use core::ops::{Index, IndexMut, Range, RangeBounds}; -use core::ptr::{self, NonNull}; +use core::ptr; use core::slice; +// This is used in a bunch of intra-doc links. +// FIXME: For some reason, `#[cfg(doc)]` wasn't sufficient, resulting in +// failures in linkchecker even though rustdoc built the docs just fine. +#[allow(unused_imports)] +use core::mem; + use crate::alloc::{Allocator, Global}; use crate::collections::TryReserveError; use crate::collections::TryReserveErrorKind; @@ -46,25 +51,16 @@ pub use self::iter::Iter; mod iter; -use self::pair_slices::PairSlices; - -mod pair_slices; - -use self::ring_slices::RingSlices; - -mod ring_slices; - use self::spec_extend::SpecExtend; mod spec_extend; -#[cfg(test)] -mod tests; +use self::spec_from_iter::SpecFromIter; -const INITIAL_CAPACITY: usize = 7; // 2^3 - 1 -const MINIMUM_CAPACITY: usize = 1; // 2 - 1 +mod spec_from_iter; -const MAXIMUM_ZST_CAPACITY: usize = 1 << (usize::BITS - 1); // Largest possible power of two +#[cfg(test)] +mod tests; /// A double-ended queue implemented with a growable ring buffer. /// @@ -99,13 +95,13 @@ pub struct VecDeque< T, #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, > { - // tail and head are pointers into the buffer. Tail always points - // to the first element that could be read, Head always points - // to where data should be written. - // If tail == head the buffer is empty. The length of the ringbuffer - // is defined as the distance between the two. - tail: usize, + // `self[0]`, if it exists, is `buf[head]`. + // `head < buf.capacity()`, unless `buf.capacity() == 0` when `head == 0`. head: usize, + // the number of initialized elements, starting from the one at `head` and potentially wrapping around. + // if `len == 0`, the exact value of `head` is unimportant. + // if `T` is zero-Sized, then `self.len <= usize::MAX`, otherwise `self.len <= isize::MAX as usize`. + len: usize, buf: RawVec<T, A>, } @@ -118,18 +114,8 @@ impl<T: Clone, A: Allocator + Clone> Clone for VecDeque<T, A> { } fn clone_from(&mut self, other: &Self) { - self.truncate(other.len()); - - let mut iter = PairSlices::from(self, other); - while let Some((dst, src)) = iter.next() { - dst.clone_from_slice(&src); - } - - if iter.has_remainder() { - for remainder in iter.remainder() { - self.extend(remainder.iter().cloned()); - } - } + self.clear(); + self.extend(other.iter().cloned()); } } @@ -174,41 +160,6 @@ impl<T, A: Allocator> VecDeque<T, A> { self.buf.ptr() } - /// Marginally more convenient - #[inline] - fn cap(&self) -> usize { - if mem::size_of::<T>() == 0 { - // For zero sized types, we are always at maximum capacity - MAXIMUM_ZST_CAPACITY - } else { - self.buf.capacity() - } - } - - /// Turn ptr into a slice, since the elements of the backing buffer may be uninitialized, - /// we will return a slice of [`MaybeUninit<T>`]. - /// - /// See [`MaybeUninit::zeroed`][zeroed] for examples of correct and - /// incorrect usage of this method. - /// - /// [zeroed]: mem::MaybeUninit::zeroed - #[inline] - unsafe fn buffer_as_slice(&self) -> &[MaybeUninit<T>] { - unsafe { slice::from_raw_parts(self.ptr() as *mut MaybeUninit<T>, self.cap()) } - } - - /// Turn ptr into a mut slice, since the elements of the backing buffer may be uninitialized, - /// we will return a slice of [`MaybeUninit<T>`]. - /// - /// See [`MaybeUninit::zeroed`][zeroed] for examples of correct and - /// incorrect usage of this method. - /// - /// [zeroed]: mem::MaybeUninit::zeroed - #[inline] - unsafe fn buffer_as_mut_slice(&mut self) -> &mut [MaybeUninit<T>] { - unsafe { slice::from_raw_parts_mut(self.ptr() as *mut MaybeUninit<T>, self.cap()) } - } - /// Moves an element out of the buffer #[inline] unsafe fn buffer_read(&mut self, off: usize) -> T { @@ -223,51 +174,58 @@ impl<T, A: Allocator> VecDeque<T, A> { } } - /// Returns `true` if the buffer is at full capacity. + /// Returns a slice pointer into the buffer. + /// `range` must lie inside `0..self.capacity()`. #[inline] - fn is_full(&self) -> bool { - self.cap() - self.len() == 1 + unsafe fn buffer_range(&self, range: Range<usize>) -> *mut [T] { + unsafe { + ptr::slice_from_raw_parts_mut(self.ptr().add(range.start), range.end - range.start) + } } - /// Returns the index in the underlying buffer for a given logical element - /// index. + /// Returns `true` if the buffer is at full capacity. #[inline] - fn wrap_index(&self, idx: usize) -> usize { - wrap_index(idx, self.cap()) + fn is_full(&self) -> bool { + self.len == self.capacity() } /// Returns the index in the underlying buffer for a given logical element /// index + addend. #[inline] fn wrap_add(&self, idx: usize, addend: usize) -> usize { - wrap_index(idx.wrapping_add(addend), self.cap()) + wrap_index(idx.wrapping_add(addend), self.capacity()) + } + + #[inline] + fn to_physical_idx(&self, idx: usize) -> usize { + self.wrap_add(self.head, idx) } /// Returns the index in the underlying buffer for a given logical element /// index - subtrahend. #[inline] fn wrap_sub(&self, idx: usize, subtrahend: usize) -> usize { - wrap_index(idx.wrapping_sub(subtrahend), self.cap()) + wrap_index(idx.wrapping_sub(subtrahend).wrapping_add(self.capacity()), self.capacity()) } /// Copies a contiguous block of memory len long from src to dst #[inline] - unsafe fn copy(&self, dst: usize, src: usize, len: usize) { + unsafe fn copy(&mut self, src: usize, dst: usize, len: usize) { debug_assert!( - dst + len <= self.cap(), + dst + len <= self.capacity(), "cpy dst={} src={} len={} cap={}", dst, src, len, - self.cap() + self.capacity() ); debug_assert!( - src + len <= self.cap(), + src + len <= self.capacity(), "cpy dst={} src={} len={} cap={}", dst, src, len, - self.cap() + self.capacity() ); unsafe { ptr::copy(self.ptr().add(src), self.ptr().add(dst), len); @@ -276,22 +234,22 @@ impl<T, A: Allocator> VecDeque<T, A> { /// Copies a contiguous block of memory len long from src to dst #[inline] - unsafe fn copy_nonoverlapping(&self, dst: usize, src: usize, len: usize) { + unsafe fn copy_nonoverlapping(&mut self, src: usize, dst: usize, len: usize) { debug_assert!( - dst + len <= self.cap(), + dst + len <= self.capacity(), "cno dst={} src={} len={} cap={}", dst, src, len, - self.cap() + self.capacity() ); debug_assert!( - src + len <= self.cap(), + src + len <= self.capacity(), "cno dst={} src={} len={} cap={}", dst, src, len, - self.cap() + self.capacity() ); unsafe { ptr::copy_nonoverlapping(self.ptr().add(src), self.ptr().add(dst), len); @@ -299,30 +257,28 @@ impl<T, A: Allocator> VecDeque<T, A> { } /// Copies a potentially wrapping block of memory len long from src to dest. - /// (abs(dst - src) + len) must be no larger than cap() (There must be at + /// (abs(dst - src) + len) must be no larger than capacity() (There must be at /// most one continuous overlapping region between src and dest). - unsafe fn wrap_copy(&self, dst: usize, src: usize, len: usize) { - #[allow(dead_code)] - fn diff(a: usize, b: usize) -> usize { - if a <= b { b - a } else { a - b } - } + unsafe fn wrap_copy(&mut self, src: usize, dst: usize, len: usize) { debug_assert!( - cmp::min(diff(dst, src), self.cap() - diff(dst, src)) + len <= self.cap(), + cmp::min(src.abs_diff(dst), self.capacity() - src.abs_diff(dst)) + len + <= self.capacity(), "wrc dst={} src={} len={} cap={}", dst, src, len, - self.cap() + self.capacity() ); - if src == dst || len == 0 { + // If T is a ZST, don't do any copying. + if T::IS_ZST || src == dst || len == 0 { return; } let dst_after_src = self.wrap_sub(dst, src) < len; - let src_pre_wrap_len = self.cap() - src; - let dst_pre_wrap_len = self.cap() - dst; + let src_pre_wrap_len = self.capacity() - src; + let dst_pre_wrap_len = self.capacity() - dst; let src_wraps = src_pre_wrap_len < len; let dst_wraps = dst_pre_wrap_len < len; @@ -336,7 +292,7 @@ impl<T, A: Allocator> VecDeque<T, A> { // D . . . // unsafe { - self.copy(dst, src, len); + self.copy(src, dst, len); } } (false, false, true) => { @@ -349,8 +305,8 @@ impl<T, A: Allocator> VecDeque<T, A> { // . . D . // unsafe { - self.copy(dst, src, dst_pre_wrap_len); - self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len); + self.copy(src, dst, dst_pre_wrap_len); + self.copy(src + dst_pre_wrap_len, 0, len - dst_pre_wrap_len); } } (true, false, true) => { @@ -363,8 +319,8 @@ impl<T, A: Allocator> VecDeque<T, A> { // . . D . // unsafe { - self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len); - self.copy(dst, src, dst_pre_wrap_len); + self.copy(src + dst_pre_wrap_len, 0, len - dst_pre_wrap_len); + self.copy(src, dst, dst_pre_wrap_len); } } (false, true, false) => { @@ -377,8 +333,8 @@ impl<T, A: Allocator> VecDeque<T, A> { // D . . . // unsafe { - self.copy(dst, src, src_pre_wrap_len); - self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len); + self.copy(src, dst, src_pre_wrap_len); + self.copy(0, dst + src_pre_wrap_len, len - src_pre_wrap_len); } } (true, true, false) => { @@ -391,8 +347,8 @@ impl<T, A: Allocator> VecDeque<T, A> { // D . . . // unsafe { - self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len); - self.copy(dst, src, src_pre_wrap_len); + self.copy(0, dst + src_pre_wrap_len, len - src_pre_wrap_len); + self.copy(src, dst, src_pre_wrap_len); } } (false, true, true) => { @@ -408,9 +364,9 @@ impl<T, A: Allocator> VecDeque<T, A> { debug_assert!(dst_pre_wrap_len > src_pre_wrap_len); let delta = dst_pre_wrap_len - src_pre_wrap_len; unsafe { - self.copy(dst, src, src_pre_wrap_len); - self.copy(dst + src_pre_wrap_len, 0, delta); - self.copy(0, delta, len - dst_pre_wrap_len); + self.copy(src, dst, src_pre_wrap_len); + self.copy(0, dst + src_pre_wrap_len, delta); + self.copy(delta, 0, len - dst_pre_wrap_len); } } (true, true, true) => { @@ -426,9 +382,9 @@ impl<T, A: Allocator> VecDeque<T, A> { debug_assert!(src_pre_wrap_len > dst_pre_wrap_len); let delta = src_pre_wrap_len - dst_pre_wrap_len; unsafe { - self.copy(delta, 0, len - src_pre_wrap_len); - self.copy(0, self.cap() - delta, delta); - self.copy(dst, src, dst_pre_wrap_len); + self.copy(0, delta, len - src_pre_wrap_len); + self.copy(self.capacity() - delta, 0, delta); + self.copy(src, dst, dst_pre_wrap_len); } } } @@ -438,8 +394,8 @@ impl<T, A: Allocator> VecDeque<T, A> { /// Assumes capacity is sufficient. #[inline] unsafe fn copy_slice(&mut self, dst: usize, src: &[T]) { - debug_assert!(src.len() <= self.cap()); - let head_room = self.cap() - dst; + debug_assert!(src.len() <= self.capacity()); + let head_room = self.capacity() - dst; if src.len() <= head_room { unsafe { ptr::copy_nonoverlapping(src.as_ptr(), self.ptr().add(dst), src.len()); @@ -472,48 +428,100 @@ impl<T, A: Allocator> VecDeque<T, A> { }); } + /// Writes all values from `iter` to `dst`, wrapping + /// at the end of the buffer and returns the number + /// of written values. + /// + /// # Safety + /// + /// Assumes that `iter` yields at most `len` items. + /// Assumes capacity is sufficient. + unsafe fn write_iter_wrapping( + &mut self, + dst: usize, + mut iter: impl Iterator<Item = T>, + len: usize, + ) -> usize { + struct Guard<'a, T, A: Allocator> { + deque: &'a mut VecDeque<T, A>, + written: usize, + } + + impl<'a, T, A: Allocator> Drop for Guard<'a, T, A> { + fn drop(&mut self) { + self.deque.len += self.written; + } + } + + let head_room = self.capacity() - dst; + + let mut guard = Guard { deque: self, written: 0 }; + + if head_room >= len { + unsafe { guard.deque.write_iter(dst, iter, &mut guard.written) }; + } else { + unsafe { + guard.deque.write_iter( + dst, + ByRefSized(&mut iter).take(head_room), + &mut guard.written, + ); + guard.deque.write_iter(0, iter, &mut guard.written) + }; + } + + guard.written + } + /// Frobs the head and tail sections around to handle the fact that we /// just reallocated. Unsafe because it trusts old_capacity. #[inline] unsafe fn handle_capacity_increase(&mut self, old_capacity: usize) { - let new_capacity = self.cap(); + let new_capacity = self.capacity(); + debug_assert!(new_capacity >= old_capacity); // Move the shortest contiguous section of the ring buffer - // T H + // + // H := head + // L := last element (`self.to_physical_idx(self.len - 1)`) + // + // H L // [o o o o o o o . ] - // T H + // H L // A [o o o o o o o . . . . . . . . . ] - // H T - // [o o . o o o o o ] - // T H + // L H + // [o o o o o o o o ] + // H L // B [. . . o o o o o o o . . . . . . ] - // H T - // [o o o o o . o o ] - // H T + // L H + // [o o o o o o o o ] + // L H // C [o o o o o . . . . . . . . . o o ] - if self.tail <= self.head { + // can't use is_contiguous() because the capacity is already updated. + if self.head <= old_capacity - self.len { // A // Nop - } else if self.head < old_capacity - self.tail { - // B - unsafe { - self.copy_nonoverlapping(old_capacity, 0, self.head); - } - self.head += old_capacity; - debug_assert!(self.head > self.tail); } else { - // C - let new_tail = new_capacity - (old_capacity - self.tail); - unsafe { - self.copy_nonoverlapping(new_tail, self.tail, old_capacity - self.tail); + let head_len = old_capacity - self.head; + let tail_len = self.len - head_len; + if head_len > tail_len && new_capacity - old_capacity >= tail_len { + // B + unsafe { + self.copy_nonoverlapping(0, old_capacity, tail_len); + } + } else { + // C + let new_head = new_capacity - head_len; + unsafe { + // can't use copy_nonoverlapping here, because if e.g. head_len = 2 + // and new_capacity = old_capacity + 1, then the heads overlap. + self.copy(self.head, new_head, head_len); + } + self.head = new_head; } - self.tail = new_tail; - debug_assert!(self.head < self.tail); } - debug_assert!(self.head < self.cap()); - debug_assert!(self.tail < self.cap()); - debug_assert!(self.cap().count_ones() == 1); + debug_assert!(self.head < self.capacity() || self.capacity() == 0); } } @@ -529,9 +537,11 @@ impl<T> VecDeque<T> { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_const_stable(feature = "const_vec_deque_new", since = "1.68.0")] #[must_use] - pub fn new() -> VecDeque<T> { - VecDeque::new_in(Global) + pub const fn new() -> VecDeque<T> { + // FIXME: This should just be `VecDeque::new_in(Global)` once that hits stable. + VecDeque { head: 0, len: 0, buf: RawVec::NEW } } /// Creates an empty deque with space for at least `capacity` elements. @@ -563,8 +573,8 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[inline] #[unstable(feature = "allocator_api", issue = "32838")] - pub fn new_in(alloc: A) -> VecDeque<T, A> { - VecDeque::with_capacity_in(INITIAL_CAPACITY, alloc) + pub const fn new_in(alloc: A) -> VecDeque<T, A> { + VecDeque { head: 0, len: 0, buf: RawVec::new_in(alloc) } } /// Creates an empty deque with space for at least `capacity` elements. @@ -578,11 +588,39 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[unstable(feature = "allocator_api", issue = "32838")] pub fn with_capacity_in(capacity: usize, alloc: A) -> VecDeque<T, A> { - assert!(capacity < 1_usize << usize::BITS - 1, "capacity overflow"); - // +1 since the ringbuffer always leaves one space empty - let cap = cmp::max(capacity + 1, MINIMUM_CAPACITY + 1).next_power_of_two(); + VecDeque { head: 0, len: 0, buf: RawVec::with_capacity_in(capacity, alloc) } + } - VecDeque { tail: 0, head: 0, buf: RawVec::with_capacity_in(cap, alloc) } + /// Creates a `VecDeque` from a raw allocation, when the initialized + /// part of that allocation forms a *contiguous* subslice thereof. + /// + /// For use by `vec::IntoIter::into_vecdeque` + /// + /// # Safety + /// + /// All the usual requirements on the allocated memory like in + /// `Vec::from_raw_parts_in`, but takes a *range* of elements that are + /// initialized rather than only supporting `0..len`. Requires that + /// `initialized.start` ≤ `initialized.end` ≤ `capacity`. + #[inline] + pub(crate) unsafe fn from_contiguous_raw_parts_in( + ptr: *mut T, + initialized: Range<usize>, + capacity: usize, + alloc: A, + ) -> Self { + debug_assert!(initialized.start <= initialized.end); + debug_assert!(initialized.end <= capacity); + + // SAFETY: Our safety precondition guarantees the range length won't wrap, + // and that the allocation is valid for use in `RawVec`. + unsafe { + VecDeque { + head: initialized.start, + len: initialized.end.unchecked_sub(initialized.start), + buf: RawVec::from_raw_parts_in(ptr, capacity, alloc), + } + } } /// Provides a reference to the element at the given index. @@ -598,12 +636,13 @@ impl<T, A: Allocator> VecDeque<T, A> { /// buf.push_back(3); /// buf.push_back(4); /// buf.push_back(5); + /// buf.push_back(6); /// assert_eq!(buf.get(1), Some(&4)); /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn get(&self, index: usize) -> Option<&T> { - if index < self.len() { - let idx = self.wrap_add(self.tail, index); + if index < self.len { + let idx = self.to_physical_idx(index); unsafe { Some(&*self.ptr().add(idx)) } } else { None @@ -623,16 +662,17 @@ impl<T, A: Allocator> VecDeque<T, A> { /// buf.push_back(3); /// buf.push_back(4); /// buf.push_back(5); + /// buf.push_back(6); + /// assert_eq!(buf[1], 4); /// if let Some(elem) = buf.get_mut(1) { /// *elem = 7; /// } - /// /// assert_eq!(buf[1], 7); /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn get_mut(&mut self, index: usize) -> Option<&mut T> { - if index < self.len() { - let idx = self.wrap_add(self.tail, index); + if index < self.len { + let idx = self.to_physical_idx(index); unsafe { Some(&mut *self.ptr().add(idx)) } } else { None @@ -666,8 +706,8 @@ impl<T, A: Allocator> VecDeque<T, A> { pub fn swap(&mut self, i: usize, j: usize) { assert!(i < self.len()); assert!(j < self.len()); - let ri = self.wrap_add(self.tail, i); - let rj = self.wrap_add(self.tail, j); + let ri = self.to_physical_idx(i); + let rj = self.to_physical_idx(j); unsafe { ptr::swap(self.ptr().add(ri), self.ptr().add(rj)) } } @@ -685,7 +725,7 @@ impl<T, A: Allocator> VecDeque<T, A> { #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn capacity(&self) -> usize { - self.cap() - 1 + if T::IS_ZST { usize::MAX } else { self.buf.capacity() } } /// Reserves the minimum capacity for at least `additional` more elements to be inserted in the @@ -712,7 +752,15 @@ impl<T, A: Allocator> VecDeque<T, A> { /// [`reserve`]: VecDeque::reserve #[stable(feature = "rust1", since = "1.0.0")] pub fn reserve_exact(&mut self, additional: usize) { - self.reserve(additional); + let new_cap = self.len.checked_add(additional).expect("capacity overflow"); + let old_cap = self.capacity(); + + if new_cap > old_cap { + self.buf.reserve_exact(self.len, additional); + unsafe { + self.handle_capacity_increase(old_cap); + } + } } /// Reserves capacity for at least `additional` more elements to be inserted in the given @@ -733,15 +781,13 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn reserve(&mut self, additional: usize) { - let old_cap = self.cap(); - let used_cap = self.len() + 1; - let new_cap = used_cap - .checked_add(additional) - .and_then(|needed_cap| needed_cap.checked_next_power_of_two()) - .expect("capacity overflow"); + let new_cap = self.len.checked_add(additional).expect("capacity overflow"); + let old_cap = self.capacity(); if new_cap > old_cap { - self.buf.reserve_exact(used_cap, new_cap - used_cap); + // we don't need to reserve_exact(), as the size doesn't have + // to be a power of 2. + self.buf.reserve(self.len, additional); unsafe { self.handle_capacity_increase(old_cap); } @@ -787,14 +833,25 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "try_reserve", since = "1.57.0")] pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { - self.try_reserve(additional) + let new_cap = + self.len.checked_add(additional).ok_or(TryReserveErrorKind::CapacityOverflow)?; + let old_cap = self.capacity(); + + if new_cap > old_cap { + self.buf.try_reserve_exact(self.len, additional)?; + unsafe { + self.handle_capacity_increase(old_cap); + } + } + Ok(()) } /// Tries to reserve capacity for at least `additional` more elements to be inserted /// in the given deque. The collection may reserve more space to speculatively avoid /// frequent reallocations. After calling `try_reserve`, capacity will be /// greater than or equal to `self.len() + additional` if it returns - /// `Ok(())`. Does nothing if capacity is already sufficient. + /// `Ok(())`. Does nothing if capacity is already sufficient. This method + /// preserves the contents even if an error occurs. /// /// # Errors /// @@ -824,15 +881,12 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "try_reserve", since = "1.57.0")] pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { - let old_cap = self.cap(); - let used_cap = self.len() + 1; - let new_cap = used_cap - .checked_add(additional) - .and_then(|needed_cap| needed_cap.checked_next_power_of_two()) - .ok_or(TryReserveErrorKind::CapacityOverflow)?; + let new_cap = + self.len.checked_add(additional).ok_or(TryReserveErrorKind::CapacityOverflow)?; + let old_cap = self.capacity(); if new_cap > old_cap { - self.buf.try_reserve_exact(used_cap, new_cap - used_cap)?; + self.buf.try_reserve(self.len, additional)?; unsafe { self.handle_capacity_increase(old_cap); } @@ -883,65 +937,79 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "shrink_to", since = "1.56.0")] pub fn shrink_to(&mut self, min_capacity: usize) { - let min_capacity = cmp::min(min_capacity, self.capacity()); - // We don't have to worry about an overflow as neither `self.len()` nor `self.capacity()` - // can ever be `usize::MAX`. +1 as the ringbuffer always leaves one space empty. - let target_cap = cmp::max(cmp::max(min_capacity, self.len()) + 1, MINIMUM_CAPACITY + 1) - .next_power_of_two(); - - if target_cap < self.cap() { - // There are three cases of interest: - // All elements are out of desired bounds - // Elements are contiguous, and head is out of desired bounds - // Elements are discontiguous, and tail is out of desired bounds + let target_cap = min_capacity.max(self.len); + + // never shrink ZSTs + if T::IS_ZST || self.capacity() <= target_cap { + return; + } + + // There are three cases of interest: + // All elements are out of desired bounds + // Elements are contiguous, and tail is out of desired bounds + // Elements are discontiguous + // + // At all other times, element positions are unaffected. + + // `head` and `len` are at most `isize::MAX` and `target_cap < self.capacity()`, so nothing can + // overflow. + let tail_outside = (target_cap + 1..=self.capacity()).contains(&(self.head + self.len)); + + if self.len == 0 { + self.head = 0; + } else if self.head >= target_cap && tail_outside { + // Head and tail are both out of bounds, so copy all of them to the front. // - // At all other times, element positions are unaffected. + // H := head + // L := last element + // H L + // [. . . . . . . . o o o o o o o . ] + // H L + // [o o o o o o o . ] + unsafe { + // nonoverlapping because `self.head >= target_cap >= self.len`. + self.copy_nonoverlapping(self.head, 0, self.len); + } + self.head = 0; + } else if self.head < target_cap && tail_outside { + // Head is in bounds, tail is out of bounds. + // Copy the overflowing part to the beginning of the + // buffer. This won't overlap because `target_cap >= self.len`. // - // Indicates that elements at the head should be moved. - let head_outside = self.head == 0 || self.head >= target_cap; - // Move elements from out of desired bounds (positions after target_cap) - if self.tail >= target_cap && head_outside { - // T H - // [. . . . . . . . o o o o o o o . ] - // T H - // [o o o o o o o . ] - unsafe { - self.copy_nonoverlapping(0, self.tail, self.len()); - } - self.head = self.len(); - self.tail = 0; - } else if self.tail != 0 && self.tail < target_cap && head_outside { - // T H - // [. . . o o o o o o o . . . . . . ] - // H T - // [o o . o o o o o ] - let len = self.wrap_sub(self.head, target_cap); - unsafe { - self.copy_nonoverlapping(0, target_cap, len); - } - self.head = len; - debug_assert!(self.head < self.tail); - } else if self.tail >= target_cap { - // H T - // [o o o o o . . . . . . . . . o o ] - // H T - // [o o o o o . o o ] - debug_assert!(self.wrap_sub(self.head, 1) < target_cap); - let len = self.cap() - self.tail; - let new_tail = target_cap - len; - unsafe { - self.copy_nonoverlapping(new_tail, self.tail, len); - } - self.tail = new_tail; - debug_assert!(self.head < self.tail); + // H := head + // L := last element + // H L + // [. . . o o o o o o o . . . . . . ] + // L H + // [o o . o o o o o ] + let len = self.head + self.len - target_cap; + unsafe { + self.copy_nonoverlapping(target_cap, 0, len); } - - self.buf.shrink_to_fit(target_cap); - - debug_assert!(self.head < self.cap()); - debug_assert!(self.tail < self.cap()); - debug_assert!(self.cap().count_ones() == 1); + } else if !self.is_contiguous() { + // The head slice is at least partially out of bounds, tail is in bounds. + // Copy the head backwards so it lines up with the target capacity. + // This won't overlap because `target_cap >= self.len`. + // + // H := head + // L := last element + // L H + // [o o o o o . . . . . . . . . o o ] + // L H + // [o o o o o . o o ] + let head_len = self.capacity() - self.head; + let new_head = target_cap - head_len; + unsafe { + // can't use `copy_nonoverlapping()` here because the new and old + // regions for the head might overlap. + self.copy(self.head, new_head, head_len); + } + self.head = new_head; } + self.buf.shrink_to_fit(target_cap); + + debug_assert!(self.head < self.capacity() || self.capacity() == 0); + debug_assert!(self.len <= self.capacity()); } /// Shortens the deque, keeping the first `len` elements and dropping @@ -985,20 +1053,20 @@ impl<T, A: Allocator> VecDeque<T, A> { // * The head of the VecDeque is moved before calling `drop_in_place`, // so no value is dropped twice if `drop_in_place` panics unsafe { - if len > self.len() { + if len >= self.len { return; } - let num_dropped = self.len() - len; + let (front, back) = self.as_mut_slices(); if len > front.len() { let begin = len - front.len(); let drop_back = back.get_unchecked_mut(begin..) as *mut _; - self.head = self.wrap_sub(self.head, num_dropped); + self.len = len; ptr::drop_in_place(drop_back); } else { let drop_back = back as *mut _; let drop_front = front.get_unchecked_mut(len..) as *mut _; - self.head = self.wrap_sub(self.head, num_dropped); + self.len = len; // Make sure the second half is dropped even when a destructor // in the first one panics. @@ -1032,7 +1100,8 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn iter(&self) -> Iter<'_, T> { - Iter::new(unsafe { self.buffer_as_slice() }, self.tail, self.head) + let (a, b) = self.as_slices(); + Iter::new(a.iter(), b.iter()) } /// Returns a front-to-back iterator that returns mutable references. @@ -1054,11 +1123,8 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn iter_mut(&mut self) -> IterMut<'_, T> { - // SAFETY: The internal `IterMut` safety invariant is established because the - // `ring` we create is a dereferenceable slice for lifetime '_. - let ring = ptr::slice_from_raw_parts_mut(self.ptr(), self.cap()); - - unsafe { IterMut::new(ring, self.tail, self.head, PhantomData) } + let (a, b) = self.as_mut_slices(); + IterMut::new(a.iter_mut(), b.iter_mut()) } /// Returns a pair of slices which contain, in order, the contents of the @@ -1090,14 +1156,10 @@ impl<T, A: Allocator> VecDeque<T, A> { #[inline] #[stable(feature = "deque_extras_15", since = "1.5.0")] pub fn as_slices(&self) -> (&[T], &[T]) { - // Safety: - // - `self.head` and `self.tail` in a ring buffer are always valid indices. - // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized. - unsafe { - let buf = self.buffer_as_slice(); - let (front, back) = RingSlices::ring_slices(buf, self.head, self.tail); - (MaybeUninit::slice_assume_init_ref(front), MaybeUninit::slice_assume_init_ref(back)) - } + 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)) } } /// Returns a pair of slices which contain, in order, the contents of the @@ -1128,16 +1190,10 @@ 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]) { - // Safety: - // - `self.head` and `self.tail` in a ring buffer are always valid indices. - // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized. - unsafe { - let head = self.head; - let tail = self.tail; - let buf = self.buffer_as_mut_slice(); - let (front, back) = RingSlices::ring_slices(buf, head, tail); - (MaybeUninit::slice_assume_init_mut(front), MaybeUninit::slice_assume_init_mut(back)) - } + 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)) } } /// Returns the number of elements in the deque. @@ -1154,7 +1210,7 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn len(&self) -> usize { - count(self.tail, self.head, self.cap()) + self.len } /// Returns `true` if the deque is empty. @@ -1171,17 +1227,50 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn is_empty(&self) -> bool { - self.tail == self.head + self.len == 0 } - fn range_tail_head<R>(&self, range: R) -> (usize, usize) + /// 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. 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 tail = self.wrap_add(self.tail, start); - let head = self.wrap_add(self.tail, end); - (tail, head) + 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 <= 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); + + // this subtraction can never overflow because `wrapped_start` is + // at most `self.capacity()` (and if `self.capacity != 0`, then `wrapped_start` is strictly less + // than `self.capacity`). + let head_len = self.capacity() - wrapped_start; + + if head_len >= len { + // we know that `len + wrapped_start <= self.capacity <= usize::MAX`, so this addition can't overflow + (wrapped_start..wrapped_start + len, 0..0) + } else { + // can't overflow because of the if condition + let tail_len = len - head_len; + (wrapped_start..self.capacity(), 0..tail_len) + } + } } /// Creates an iterator that covers the specified range in the deque. @@ -1210,9 +1299,14 @@ impl<T, A: Allocator> VecDeque<T, A> { where R: RangeBounds<usize>, { - let (tail, head) = self.range_tail_head(range); - // The shared reference we have in &self is maintained in the '_ of Iter. - Iter::new(unsafe { self.buffer_as_slice() }, tail, head) + 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 + // dereference the result. + let a = unsafe { &*self.buffer_range(a_range) }; + let b = unsafe { &*self.buffer_range(b_range) }; + Iter::new(a.iter(), b.iter()) } /// Creates an iterator that covers the specified mutable range in the deque. @@ -1245,13 +1339,14 @@ impl<T, A: Allocator> VecDeque<T, A> { where R: RangeBounds<usize>, { - let (tail, head) = self.range_tail_head(range); - - // SAFETY: The internal `IterMut` safety invariant is established because the - // `ring` we create is a dereferenceable slice for lifetime '_. - let ring = ptr::slice_from_raw_parts_mut(self.ptr(), self.cap()); - - unsafe { IterMut::new(ring, tail, head, PhantomData) } + 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 + // dereference the result. + let a = unsafe { &mut *self.buffer_range(a_range) }; + let b = unsafe { &mut *self.buffer_range(b_range) }; + IterMut::new(a.iter_mut(), b.iter_mut()) } /// Removes the specified range from the deque in bulk, returning all @@ -1303,40 +1398,30 @@ impl<T, A: Allocator> VecDeque<T, A> { // When finished, the remaining data will be copied back to cover the hole, // and the head/tail values will be restored correctly. // - let (drain_tail, drain_head) = self.range_tail_head(range); + let Range { start, end } = slice::range(range, ..self.len); + let drain_start = start; + let drain_len = end - start; // The deque's elements are parted into three segments: - // * self.tail -> drain_tail - // * drain_tail -> drain_head - // * drain_head -> self.head + // * 0 -> drain_start + // * drain_start -> drain_start+drain_len + // * drain_start+drain_len -> self.len // - // T = self.tail; H = self.head; t = drain_tail; h = drain_head + // H = self.head; T = self.head+self.len; t = drain_start+drain_len; h = drain_head // - // We store drain_tail as self.head, and drain_head and self.head as - // after_tail and after_head respectively on the Drain. This also + // We store drain_start as self.len, and drain_len and self.len as + // drain_len and orig_len respectively on the Drain. This also // truncates the effective array such that if the Drain is leaked, we // have forgotten about the potentially moved values after the start of // the drain. // - // T t h H + // H h t T // [. . . o o x x o o . . .] // - let head = self.head; - // "forget" about the values after the start of the drain until after // the drain is complete and the Drain destructor is run. - self.head = drain_tail; - let deque = NonNull::from(&mut *self); - unsafe { - // Crucially, we only create shared references from `self` here and read from - // it. We do not write to `self` nor reborrow to a mutable reference. - // Hence the raw pointer we created above, for `deque`, remains valid. - let ring = self.buffer_as_slice(); - let iter = Iter::new(ring, drain_tail, drain_head); - - Drain::new(drain_head, head, iter, deque) - } + unsafe { Drain::new(self, drain_start, drain_len) } } /// Clears the deque, removing all values. @@ -1355,6 +1440,8 @@ impl<T, A: Allocator> VecDeque<T, A> { #[inline] pub fn clear(&mut self) { self.truncate(0); + // Not strictly necessary, but leaves things in a more consistent/predictable state. + self.head = 0; } /// Returns `true` if the deque contains an element equal to the @@ -1449,7 +1536,7 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn back(&self) -> Option<&T> { - self.get(self.len().wrapping_sub(1)) + self.get(self.len.wrapping_sub(1)) } /// Provides a mutable reference to the back element, or `None` if the @@ -1473,7 +1560,7 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn back_mut(&mut self) -> Option<&mut T> { - self.get_mut(self.len().wrapping_sub(1)) + self.get_mut(self.len.wrapping_sub(1)) } /// Removes the first element and returns it, or `None` if the deque is @@ -1497,9 +1584,10 @@ impl<T, A: Allocator> VecDeque<T, A> { if self.is_empty() { None } else { - let tail = self.tail; - self.tail = self.wrap_add(self.tail, 1); - unsafe { Some(self.buffer_read(tail)) } + let old_head = self.head; + self.head = self.to_physical_idx(1); + self.len -= 1; + Some(unsafe { self.buffer_read(old_head) }) } } @@ -1522,9 +1610,8 @@ impl<T, A: Allocator> VecDeque<T, A> { if self.is_empty() { None } else { - self.head = self.wrap_sub(self.head, 1); - let head = self.head; - unsafe { Some(self.buffer_read(head)) } + self.len -= 1; + Some(unsafe { self.buffer_read(self.to_physical_idx(self.len)) }) } } @@ -1546,10 +1633,11 @@ impl<T, A: Allocator> VecDeque<T, A> { self.grow(); } - self.tail = self.wrap_sub(self.tail, 1); - let tail = self.tail; + self.head = self.wrap_sub(self.head, 1); + self.len += 1; + unsafe { - self.buffer_write(tail, value); + self.buffer_write(self.head, value); } } @@ -1571,16 +1659,14 @@ impl<T, A: Allocator> VecDeque<T, A> { self.grow(); } - let head = self.head; - self.head = self.wrap_add(self.head, 1); - unsafe { self.buffer_write(head, value) } + unsafe { self.buffer_write(self.to_physical_idx(self.len), value) } + self.len += 1; } #[inline] fn is_contiguous(&self) -> bool { - // FIXME: Should we consider `head == 0` to mean - // that `self` is contiguous? - self.tail <= self.head + // Do the calculation like this to avoid overflowing if len + head > usize::MAX + self.head <= self.capacity() - self.len } /// Removes an element from anywhere in the deque and returns it, @@ -1609,8 +1695,8 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "deque_extras_15", since = "1.5.0")] pub fn swap_remove_front(&mut self, index: usize) -> Option<T> { - let length = self.len(); - if length > 0 && index < length && index != 0 { + let length = self.len; + if index < length && index != 0 { self.swap(index, 0); } else if index >= length { return None; @@ -1644,7 +1730,7 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "deque_extras_15", since = "1.5.0")] pub fn swap_remove_back(&mut self, index: usize) -> Option<T> { - let length = self.len(); + let length = self.len; if length > 0 && index < length - 1 { self.swap(index, length - 1); } else if index >= length { @@ -1683,198 +1769,26 @@ impl<T, A: Allocator> VecDeque<T, A> { self.grow(); } - // Move the least number of elements in the ring buffer and insert - // the given object - // - // At most len/2 - 1 elements will be moved. O(min(n, n-i)) - // - // There are three main cases: - // Elements are contiguous - // - special case when tail is 0 - // Elements are discontiguous and the insert is in the tail section - // Elements are discontiguous and the insert is in the head section - // - // For each of those there are two more cases: - // Insert is closer to tail - // Insert is closer to head - // - // Key: H - self.head - // T - self.tail - // o - Valid element - // I - Insertion element - // A - The element that should be after the insertion point - // M - Indicates element was moved - - let idx = self.wrap_add(self.tail, index); - - let distance_to_tail = index; - let distance_to_head = self.len() - index; - - let contiguous = self.is_contiguous(); - - match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) { - (true, true, _) if index == 0 => { - // push_front - // - // T - // I H - // [A o o o o o o . . . . . . . . .] - // - // H T - // [A o o o o o o o . . . . . I] - // - - self.tail = self.wrap_sub(self.tail, 1); - } - (true, true, _) => { - unsafe { - // contiguous, insert closer to tail: - // - // T I H - // [. . . o o A o o o o . . . . . .] - // - // T H - // [. . o o I A o o o o . . . . . .] - // M M - // - // contiguous, insert closer to tail and tail is 0: - // - // - // T I H - // [o o A o o o o . . . . . . . . .] - // - // H T - // [o I A o o o o o . . . . . . . o] - // M M - - let new_tail = self.wrap_sub(self.tail, 1); - - self.copy(new_tail, self.tail, 1); - // Already moved the tail, so we only copy `index - 1` elements. - self.copy(self.tail, self.tail + 1, index - 1); - - self.tail = new_tail; - } - } - (true, false, _) => { - unsafe { - // contiguous, insert closer to head: - // - // T I H - // [. . . o o o o A o o . . . . . .] - // - // T H - // [. . . o o o o I A o o . . . . .] - // M M M - - self.copy(idx + 1, idx, self.head - idx); - self.head = self.wrap_add(self.head, 1); - } - } - (false, true, true) => { - unsafe { - // discontiguous, insert closer to tail, tail section: - // - // H T I - // [o o o o o o . . . . . o o A o o] - // - // H T - // [o o o o o o . . . . o o I A o o] - // M M - - self.copy(self.tail - 1, self.tail, index); - self.tail -= 1; - } - } - (false, false, true) => { - unsafe { - // discontiguous, insert closer to head, tail section: - // - // H T I - // [o o . . . . . . . o o o o o A o] - // - // H T - // [o o o . . . . . . o o o o o I A] - // M M M M - - // copy elements up to new head - self.copy(1, 0, self.head); - - // copy last element into empty spot at bottom of buffer - self.copy(0, self.cap() - 1, 1); - - // move elements from idx to end forward not including ^ element - self.copy(idx + 1, idx, self.cap() - 1 - idx); - - self.head += 1; - } - } - (false, true, false) if idx == 0 => { - unsafe { - // discontiguous, insert is closer to tail, head section, - // and is at index zero in the internal buffer: - // - // I H T - // [A o o o o o o o o o . . . o o o] - // - // H T - // [A o o o o o o o o o . . o o o I] - // M M M - - // copy elements up to new tail - self.copy(self.tail - 1, self.tail, self.cap() - self.tail); - - // copy last element into empty spot at bottom of buffer - self.copy(self.cap() - 1, 0, 1); - - self.tail -= 1; - } - } - (false, true, false) => { - unsafe { - // discontiguous, insert closer to tail, head section: - // - // I H T - // [o o o A o o o o o o . . . o o o] - // - // H T - // [o o I A o o o o o o . . o o o o] - // M M M M M M - - // copy elements up to new tail - self.copy(self.tail - 1, self.tail, self.cap() - self.tail); - - // copy last element into empty spot at bottom of buffer - self.copy(self.cap() - 1, 0, 1); - - // move elements from idx-1 to end forward not including ^ element - self.copy(0, 1, idx - 1); - - self.tail -= 1; - } + let k = self.len - index; + if k < index { + // `index + 1` can't overflow, because if index was usize::MAX, then either the + // assert would've failed, or the deque would've tried to grow past usize::MAX + // and panicked. + unsafe { + // see `remove()` for explanation why this wrap_copy() call is safe. + self.wrap_copy(self.to_physical_idx(index), self.to_physical_idx(index + 1), k); + self.buffer_write(self.to_physical_idx(index), value); + self.len += 1; } - (false, false, false) => { - unsafe { - // discontiguous, insert closer to head, head section: - // - // I H T - // [o o o o A o o . . . . . . o o o] - // - // H T - // [o o o o I A o o . . . . . o o o] - // M M M - - self.copy(idx + 1, idx, self.head - idx); - self.head += 1; - } + } else { + let old_head = self.head; + self.head = self.wrap_sub(self.head, 1); + unsafe { + self.wrap_copy(old_head, self.head, index); + self.buffer_write(self.to_physical_idx(index), value); + self.len += 1; } } - - // tail might've been changed so we need to recalculate - let new_idx = self.wrap_add(self.tail, index); - unsafe { - self.buffer_write(new_idx, value); - } } /// Removes and returns the element at `index` from the deque. @@ -1900,156 +1814,26 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn remove(&mut self, index: usize) -> Option<T> { - if self.is_empty() || self.len() <= index { + if self.len <= index { return None; } - // There are three main cases: - // Elements are contiguous - // Elements are discontiguous and the removal is in the tail section - // Elements are discontiguous and the removal is in the head section - // - special case when elements are technically contiguous, - // but self.head = 0 - // - // For each of those there are two more cases: - // Insert is closer to tail - // Insert is closer to head - // - // Key: H - self.head - // T - self.tail - // o - Valid element - // x - Element marked for removal - // R - Indicates element that is being removed - // M - Indicates element was moved - - let idx = self.wrap_add(self.tail, index); - - let elem = unsafe { Some(self.buffer_read(idx)) }; - - let distance_to_tail = index; - let distance_to_head = self.len() - index; - - let contiguous = self.is_contiguous(); - - match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) { - (true, true, _) => { - unsafe { - // contiguous, remove closer to tail: - // - // T R H - // [. . . o o x o o o o . . . . . .] - // - // T H - // [. . . . o o o o o o . . . . . .] - // M M - - self.copy(self.tail + 1, self.tail, index); - self.tail += 1; - } - } - (true, false, _) => { - unsafe { - // contiguous, remove closer to head: - // - // T R H - // [. . . o o o o x o o . . . . . .] - // - // T H - // [. . . o o o o o o . . . . . . .] - // M M - - self.copy(idx, idx + 1, self.head - idx - 1); - self.head -= 1; - } - } - (false, true, true) => { - unsafe { - // discontiguous, remove closer to tail, tail section: - // - // H T R - // [o o o o o o . . . . . o o x o o] - // - // H T - // [o o o o o o . . . . . . o o o o] - // M M - - self.copy(self.tail + 1, self.tail, index); - self.tail = self.wrap_add(self.tail, 1); - } - } - (false, false, false) => { - unsafe { - // discontiguous, remove closer to head, head section: - // - // R H T - // [o o o o x o o . . . . . . o o o] - // - // H T - // [o o o o o o . . . . . . . o o o] - // M M - - self.copy(idx, idx + 1, self.head - idx - 1); - self.head -= 1; - } - } - (false, false, true) => { - unsafe { - // discontiguous, remove closer to head, tail section: - // - // H T R - // [o o o . . . . . . o o o o o x o] - // - // H T - // [o o . . . . . . . o o o o o o o] - // M M M M - // - // or quasi-discontiguous, remove next to head, tail section: - // - // H T R - // [. . . . . . . . . o o o o o x o] - // - // T H - // [. . . . . . . . . o o o o o o .] - // M - - // draw in elements in the tail section - self.copy(idx, idx + 1, self.cap() - idx - 1); - - // Prevents underflow. - if self.head != 0 { - // copy first element into empty spot - self.copy(self.cap() - 1, 0, 1); - - // move elements in the head section backwards - self.copy(0, 1, self.head - 1); - } - - self.head = self.wrap_sub(self.head, 1); - } - } - (false, true, false) => { - unsafe { - // discontiguous, remove closer to tail, head section: - // - // R H T - // [o o x o o o o o o o . . . o o o] - // - // H T - // [o o o o o o o o o o . . . . o o] - // M M M M M - - // draw in elements up to idx - self.copy(1, 0, idx); - - // copy last element into empty spot - self.copy(0, self.cap() - 1, 1); + let wrapped_idx = self.to_physical_idx(index); - // move elements from tail to end forward, excluding the last one - self.copy(self.tail + 1, self.tail, self.cap() - self.tail - 1); + let elem = unsafe { Some(self.buffer_read(wrapped_idx)) }; - self.tail = self.wrap_add(self.tail, 1); - } - } + let k = self.len - index - 1; + // safety: due to the nature of the if-condition, whichever wrap_copy gets called, + // its length argument will be at most `self.len / 2`, so there can't be more than + // one overlapping area. + if k < index { + unsafe { self.wrap_copy(self.wrap_add(wrapped_idx, 1), wrapped_idx, k) }; + self.len -= 1; + } else { + let old_head = self.head; + self.head = self.to_physical_idx(1); + unsafe { self.wrap_copy(old_head, self.head, index) }; + self.len -= 1; } elem @@ -2085,7 +1869,7 @@ impl<T, A: Allocator> VecDeque<T, A> { where A: Clone, { - let len = self.len(); + let len = self.len; assert!(at <= len, "`at` out of bounds"); let other_len = len - at; @@ -2122,8 +1906,8 @@ impl<T, A: Allocator> VecDeque<T, A> { } // Cleanup where the ends of the buffers are - self.head = self.wrap_sub(self.head, other_len); - other.head = other.wrap_index(other_len); + self.len = at; + other.len = other_len; other } @@ -2148,17 +1932,26 @@ impl<T, A: Allocator> VecDeque<T, A> { #[inline] #[stable(feature = "append", since = "1.4.0")] pub fn append(&mut self, other: &mut Self) { - self.reserve(other.len()); + if T::IS_ZST { + self.len = self.len.checked_add(other.len).expect("capacity overflow"); + other.len = 0; + other.head = 0; + return; + } + + self.reserve(other.len); unsafe { let (left, right) = other.as_slices(); - self.copy_slice(self.head, left); - self.copy_slice(self.wrap_add(self.head, left.len()), right); + self.copy_slice(self.to_physical_idx(self.len), left); + // no overflow, because self.capacity() >= old_cap + left.len() >= self.len + left.len() + self.copy_slice(self.to_physical_idx(self.len + left.len()), right); } // SAFETY: Update pointers after copying to avoid leaving doppelganger // in case of panics. - self.head = self.wrap_add(self.head, other.len()); - // Silently drop values in `other`. - other.tail = other.head; + self.len += other.len; + // Now that we own its values, forget everything in `other`. + other.len = 0; + other.head = 0; } /// Retains only the elements specified by the predicate. @@ -2226,7 +2019,7 @@ impl<T, A: Allocator> VecDeque<T, A> { where F: FnMut(&mut T) -> bool, { - let len = self.len(); + let len = self.len; let mut idx = 0; let mut cur = 0; @@ -2264,9 +2057,8 @@ impl<T, A: Allocator> VecDeque<T, A> { // Extend or possibly remove this assertion when valid use-cases for growing the // buffer without it being full emerge debug_assert!(self.is_full()); - let old_cap = self.cap(); - self.buf.reserve_exact(old_cap, old_cap); - assert!(self.cap() == old_cap * 2); + let old_cap = self.capacity(); + self.buf.reserve_for_push(old_cap); unsafe { self.handle_capacity_increase(old_cap); } @@ -2300,7 +2092,7 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "vec_resize_with", since = "1.33.0")] pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T) { - let len = self.len(); + let len = self.len; if new_len > len { self.extend(repeat_with(generator).take(new_len - len)) @@ -2366,110 +2158,129 @@ impl<T, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "deque_make_contiguous", since = "1.48.0")] pub fn make_contiguous(&mut self) -> &mut [T] { + if T::IS_ZST { + self.head = 0; + } + if self.is_contiguous() { - let tail = self.tail; - let head = self.head; - // Safety: - // - `self.head` and `self.tail` in a ring buffer are always valid indices. - // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized. - return unsafe { - MaybeUninit::slice_assume_init_mut( - RingSlices::ring_slices(self.buffer_as_mut_slice(), head, tail).0, - ) - }; + unsafe { return slice::from_raw_parts_mut(self.ptr().add(self.head), self.len) } } - let buf = self.buf.ptr(); - let cap = self.cap(); - let len = self.len(); + let &mut Self { head, len, .. } = self; + let ptr = self.ptr(); + let cap = self.capacity(); - let free = self.tail - self.head; - let tail_len = cap - self.tail; + let free = cap - len; + let head_len = cap - head; + let tail = len - head_len; + let tail_len = tail; - if free >= tail_len { - // there is enough free space to copy the tail in one go, - // this means that we first shift the head backwards, and then - // copy the tail to the correct position. + if free >= head_len { + // there is enough free space to copy the head in one go, + // this means that we first shift the tail backwards, and then + // copy the head to the correct position. // // from: DEFGH....ABC // to: ABCDEFGH.... unsafe { - ptr::copy(buf, buf.add(tail_len), self.head); + self.copy(0, head_len, tail_len); // ...DEFGH.ABC - ptr::copy_nonoverlapping(buf.add(self.tail), buf, tail_len); + self.copy_nonoverlapping(head, 0, head_len); // ABCDEFGH.... - - self.tail = 0; - self.head = len; } - } else if free > self.head { - // FIXME: We currently do not consider ....ABCDEFGH - // to be contiguous because `head` would be `0` in this - // case. While we probably want to change this it - // isn't trivial as a few places expect `is_contiguous` - // to mean that we can just slice using `buf[tail..head]`. - // there is enough free space to copy the head in one go, - // this means that we first shift the tail forwards, and then - // copy the head to the correct position. + self.head = 0; + } else if free >= tail_len { + // there is enough free space to copy the tail in one go, + // this means that we first shift the head forwards, and then + // copy the tail to the correct position. // // from: FGH....ABCDE // to: ...ABCDEFGH. unsafe { - ptr::copy(buf.add(self.tail), buf.add(self.head), tail_len); + self.copy(head, tail, head_len); // FGHABCDE.... - ptr::copy_nonoverlapping(buf, buf.add(self.head + tail_len), self.head); + self.copy_nonoverlapping(0, tail + head_len, tail_len); // ...ABCDEFGH. - - self.tail = self.head; - self.head = self.wrap_add(self.tail, len); } + + self.head = tail; } else { - // free is smaller than both head and tail, - // this means we have to slowly "swap" the tail and the head. + // `free` is smaller than both `head_len` and `tail_len`. + // the general algorithm for this first moves the slices + // right next to each other and then uses `slice::rotate` + // to rotate them into place: // - // from: EFGHI...ABCD or HIJK.ABCDEFG - // to: ABCDEFGHI... or ABCDEFGHIJK. - let mut left_edge: usize = 0; - let mut right_edge: usize = self.tail; - unsafe { - // The general problem looks like this - // GHIJKLM...ABCDEF - before any swaps - // ABCDEFM...GHIJKL - after 1 pass of swaps - // ABCDEFGHIJM...KL - swap until the left edge reaches the temp store - // - then restart the algorithm with a new (smaller) store - // Sometimes the temp store is reached when the right edge is at the end - // of the buffer - this means we've hit the right order with fewer swaps! - // E.g - // EF..ABCD - // ABCDEF.. - after four only swaps we've finished - while left_edge < len && right_edge != cap { - let mut right_offset = 0; - for i in left_edge..right_edge { - right_offset = (i - left_edge) % (cap - right_edge); - let src: isize = (right_edge + right_offset) as isize; - ptr::swap(buf.add(i), buf.offset(src)); + // initially: HIJK..ABCDEFG + // step 1: ..HIJKABCDEFG + // step 2: ..ABCDEFGHIJK + // + // or: + // + // initially: FGHIJK..ABCDE + // step 1: FGHIJKABCDE.. + // step 2: ABCDEFGHIJK.. + + // pick the shorter of the 2 slices to reduce the amount + // of memory that needs to be moved around. + if head_len > tail_len { + // tail is shorter, so: + // 1. copy tail forwards + // 2. rotate used part of the buffer + // 3. update head to point to the new beginning (which is just `free`) + + unsafe { + // if there is no free space in the buffer, then the slices are already + // right next to each other and we don't need to move any memory. + if free != 0 { + // because we only move the tail forward as much as there's free space + // behind it, we don't overwrite any elements of the head slice, and + // the slices end up right next to each other. + self.copy(0, free, tail_len); } - let n_ops = right_edge - left_edge; - left_edge += n_ops; - right_edge += right_offset + 1; + + // We just copied the tail right next to the head slice, + // so all of the elements in the range are initialized + let slice = &mut *self.buffer_range(free..self.capacity()); + + // because the deque wasn't contiguous, we know that `tail_len < self.len == slice.len()`, + // so this will never panic. + slice.rotate_left(tail_len); + + // the used part of the buffer now is `free..self.capacity()`, so set + // `head` to the beginning of that range. + self.head = free; } + } else { + // head is shorter so: + // 1. copy head backwards + // 2. rotate used part of the buffer + // 3. update head to point to the new beginning (which is the beginning of the buffer) + + unsafe { + // if there is no free space in the buffer, then the slices are already + // right next to each other and we don't need to move any memory. + if free != 0 { + // copy the head slice to lie right behind the tail slice. + self.copy(self.head, tail_len, head_len); + } + + // because we copied the head slice so that both slices lie right + // next to each other, all the elements in the range are initialized. + let slice = &mut *self.buffer_range(0..self.len); + + // because the deque wasn't contiguous, we know that `head_len < self.len == slice.len()` + // so this will never panic. + slice.rotate_right(head_len); - self.tail = 0; - self.head = len; + // the used part of the buffer now is `0..self.len`, so set + // `head` to the beginning of that range. + self.head = 0; + } } } - let tail = self.tail; - let head = self.head; - // Safety: - // - `self.head` and `self.tail` in a ring buffer are always valid indices. - // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized. - unsafe { - MaybeUninit::slice_assume_init_mut( - RingSlices::ring_slices(self.buffer_as_mut_slice(), head, tail).0, - ) - } + unsafe { slice::from_raw_parts_mut(ptr.add(self.head), self.len) } } /// Rotates the double-ended queue `mid` places to the left. @@ -2507,7 +2318,7 @@ impl<T, A: Allocator> VecDeque<T, A> { #[stable(feature = "vecdeque_rotate", since = "1.36.0")] pub fn rotate_left(&mut self, mid: usize) { assert!(mid <= self.len()); - let k = self.len() - mid; + let k = self.len - mid; if mid <= k { unsafe { self.rotate_left_inner(mid) } } else { @@ -2550,7 +2361,7 @@ impl<T, A: Allocator> VecDeque<T, A> { #[stable(feature = "vecdeque_rotate", since = "1.36.0")] pub fn rotate_right(&mut self, k: usize) { assert!(k <= self.len()); - let mid = self.len() - k; + let mid = self.len - k; if k <= mid { unsafe { self.rotate_right_inner(k) } } else { @@ -2561,31 +2372,30 @@ impl<T, A: Allocator> VecDeque<T, A> { // SAFETY: the following two methods require that the rotation amount // be less than half the length of the deque. // - // `wrap_copy` requires that `min(x, cap() - x) + copy_len <= cap()`, - // but than `min` is never more than half the capacity, regardless of x, + // `wrap_copy` requires that `min(x, capacity() - x) + copy_len <= capacity()`, + // but then `min` is never more than half the capacity, regardless of x, // so it's sound to call here because we're calling with something // less than half the length, which is never above half the capacity. unsafe fn rotate_left_inner(&mut self, mid: usize) { debug_assert!(mid * 2 <= self.len()); unsafe { - self.wrap_copy(self.head, self.tail, mid); + self.wrap_copy(self.head, self.to_physical_idx(self.len), mid); } - self.head = self.wrap_add(self.head, mid); - self.tail = self.wrap_add(self.tail, mid); + self.head = self.to_physical_idx(mid); } unsafe fn rotate_right_inner(&mut self, k: usize) { debug_assert!(k * 2 <= self.len()); self.head = self.wrap_sub(self.head, k); - self.tail = self.wrap_sub(self.tail, k); unsafe { - self.wrap_copy(self.tail, self.head, k); + self.wrap_copy(self.to_physical_idx(self.len), self.head, k); } } /// 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 @@ -2595,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 @@ -2641,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 @@ -2656,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 @@ -2696,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 @@ -2709,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 @@ -2751,7 +2560,7 @@ impl<T, A: Allocator> VecDeque<T, A> { /// The deque is assumed to be partitioned according to the given predicate. /// This means that all elements for which the predicate returns true are at the start of the deque /// and all elements for which the predicate returns false are at the end. - /// For example, [7, 15, 3, 5, 4, 12, 6] is a partitioned under the predicate x % 2 != 0 + /// For example, `[7, 15, 3, 5, 4, 12, 6]` is partitioned under the predicate `x % 2 != 0` /// (all odd numbers are at the start, all even at the end). /// /// If the deque is not partitioned, the returned result is unspecified and meaningless, @@ -2827,29 +2636,30 @@ impl<T: Clone, A: Allocator> VecDeque<T, A> { /// ``` #[stable(feature = "deque_extras", since = "1.16.0")] pub fn resize(&mut self, new_len: usize, value: T) { - self.resize_with(new_len, || value.clone()); + if new_len > self.len() { + let extra = new_len - self.len(); + self.extend(repeat_n(value, extra)) + } else { + self.truncate(new_len); + } } } /// Returns the index in the underlying buffer for a given logical element index. #[inline] -fn wrap_index(index: usize, size: usize) -> usize { - // size is always a power of 2 - debug_assert!(size.is_power_of_two()); - index & (size - 1) -} - -/// Calculate the number of elements left to be read in the buffer -#[inline] -fn count(tail: usize, head: usize, size: usize) -> usize { - // size is always a power of 2 - (head.wrapping_sub(tail)) & (size - 1) +fn wrap_index(logical_index: usize, capacity: usize) -> usize { + debug_assert!( + (logical_index == 0 && capacity == 0) + || logical_index < capacity + || (logical_index - capacity) < capacity + ); + if logical_index >= capacity { logical_index - capacity } else { logical_index } } #[stable(feature = "rust1", since = "1.0.0")] impl<T: PartialEq, A: Allocator> PartialEq for VecDeque<T, A> { fn eq(&self, other: &Self) -> bool { - if self.len() != other.len() { + if self.len != other.len() { return false; } let (sa, sb) = self.as_slices(); @@ -2913,7 +2723,7 @@ impl<T: Ord, A: Allocator> Ord for VecDeque<T, A> { #[stable(feature = "rust1", since = "1.0.0")] impl<T: Hash, A: Allocator> Hash for VecDeque<T, A> { fn hash<H: Hasher>(&self, state: &mut H) { - state.write_length_prefix(self.len()); + state.write_length_prefix(self.len); // It's not possible to use Hash::hash_slice on slices // returned by as_slices method as their length can vary // in otherwise identical deques. @@ -2945,11 +2755,7 @@ impl<T, A: Allocator> IndexMut<usize> for VecDeque<T, A> { #[stable(feature = "rust1", since = "1.0.0")] impl<T> FromIterator<T> for VecDeque<T> { fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> VecDeque<T> { - let iterator = iter.into_iter(); - let (lower, _) = iterator.size_hint(); - let mut deq = VecDeque::with_capacity(lower); - deq.extend(iterator); - deq + SpecFromIter::spec_from_iter(iter.into_iter()) } } @@ -3009,7 +2815,7 @@ impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A> { } #[inline] - fn extend_one(&mut self, &elem: &T) { + fn extend_one(&mut self, &elem: &'a T) { self.push_back(elem); } @@ -3022,7 +2828,7 @@ impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A> { #[stable(feature = "rust1", since = "1.0.0")] impl<T: fmt::Debug, A: Allocator> fmt::Debug for VecDeque<T, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self).finish() + f.debug_list().entries(self.iter()).finish() } } @@ -3033,31 +2839,13 @@ impl<T, A: Allocator> From<Vec<T, A>> for VecDeque<T, A> { /// [`Vec<T>`]: crate::vec::Vec /// [`VecDeque<T>`]: crate::collections::VecDeque /// - /// This avoids reallocating where possible, but the conditions for that are - /// strict, and subject to change, and so shouldn't be relied upon unless the - /// `Vec<T>` came from `From<VecDeque<T>>` and hasn't been reallocated. - fn from(mut other: Vec<T, A>) -> Self { - let len = other.len(); - if mem::size_of::<T>() == 0 { - // There's no actual allocation for ZSTs to worry about capacity, - // but `VecDeque` can't handle as much length as `Vec`. - assert!(len < MAXIMUM_ZST_CAPACITY, "capacity overflow"); - } else { - // We need to resize if the capacity is not a power of two, too small or - // doesn't have at least one free space. We do this while it's still in - // the `Vec` so the items will drop on panic. - let min_cap = cmp::max(MINIMUM_CAPACITY, len) + 1; - let cap = cmp::max(min_cap, other.capacity()).next_power_of_two(); - if other.capacity() != cap { - other.reserve_exact(cap - len); - } - } - - unsafe { - let (other_buf, len, capacity, alloc) = other.into_raw_parts_with_alloc(); - let buf = RawVec::from_raw_parts_in(other_buf, capacity, alloc); - VecDeque { tail: 0, head: len, buf } - } + /// This conversion is guaranteed to run in *O*(1) time + /// and to not re-allocate the `Vec`'s buffer or allocate + /// any additional memory. + #[inline] + fn from(other: Vec<T, A>) -> Self { + let (ptr, len, cap, alloc) = other.into_raw_parts_with_alloc(); + Self { head: 0, len, buf: unsafe { RawVec::from_raw_parts_in(ptr, cap, alloc) } } } } @@ -3099,11 +2887,11 @@ impl<T, A: Allocator> From<VecDeque<T, A>> for Vec<T, A> { let other = ManuallyDrop::new(other); let buf = other.buf.ptr(); let len = other.len(); - let cap = other.cap(); + let cap = other.capacity(); let alloc = ptr::read(other.allocator()); - if other.tail != 0 { - ptr::copy(buf.add(other.tail), buf, len); + if other.head != 0 { + ptr::copy(buf.add(other.head), buf, len); } Vec::from_raw_parts_in(buf, len, cap, alloc) } @@ -3124,14 +2912,14 @@ impl<T, const N: usize> From<[T; N]> for VecDeque<T> { fn from(arr: [T; N]) -> Self { let mut deq = VecDeque::with_capacity(N); let arr = ManuallyDrop::new(arr); - if mem::size_of::<T>() != 0 { + if !<T>::IS_ZST { // SAFETY: VecDeque::with_capacity ensures that there is enough capacity. unsafe { ptr::copy_nonoverlapping(arr.as_ptr(), deq.ptr(), N); } } - deq.tail = 0; - deq.head = N; + deq.head = 0; + deq.len = N; deq } } diff --git a/library/alloc/src/collections/vec_deque/pair_slices.rs b/library/alloc/src/collections/vec_deque/pair_slices.rs deleted file mode 100644 index 6735424a3ef..00000000000 --- a/library/alloc/src/collections/vec_deque/pair_slices.rs +++ /dev/null @@ -1,67 +0,0 @@ -use core::cmp::{self}; -use core::mem::replace; - -use crate::alloc::Allocator; - -use super::VecDeque; - -/// PairSlices pairs up equal length slice parts of two deques -/// -/// For example, given deques "A" and "B" with the following division into slices: -/// -/// A: [0 1 2] [3 4 5] -/// B: [a b] [c d e] -/// -/// It produces the following sequence of matching slices: -/// -/// ([0 1], [a b]) -/// (\[2\], \[c\]) -/// ([3 4], [d e]) -/// -/// and the uneven remainder of either A or B is skipped. -pub struct PairSlices<'a, 'b, T> { - a0: &'a mut [T], - a1: &'a mut [T], - b0: &'b [T], - b1: &'b [T], -} - -impl<'a, 'b, T> PairSlices<'a, 'b, T> { - pub fn from<A: Allocator>(to: &'a mut VecDeque<T, A>, from: &'b VecDeque<T, A>) -> Self { - let (a0, a1) = to.as_mut_slices(); - let (b0, b1) = from.as_slices(); - PairSlices { a0, a1, b0, b1 } - } - - pub fn has_remainder(&self) -> bool { - !self.b0.is_empty() - } - - pub fn remainder(self) -> impl Iterator<Item = &'b [T]> { - IntoIterator::into_iter([self.b0, self.b1]) - } -} - -impl<'a, 'b, T> Iterator for PairSlices<'a, 'b, T> { - type Item = (&'a mut [T], &'b [T]); - fn next(&mut self) -> Option<Self::Item> { - // Get next part length - let part = cmp::min(self.a0.len(), self.b0.len()); - if part == 0 { - return None; - } - let (p0, p1) = replace(&mut self.a0, &mut []).split_at_mut(part); - let (q0, q1) = self.b0.split_at(part); - - // Move a1 into a0, if it's empty (and b1, b0 the same way). - self.a0 = p1; - self.b0 = q1; - if self.a0.is_empty() { - self.a0 = replace(&mut self.a1, &mut []); - } - if self.b0.is_empty() { - self.b0 = replace(&mut self.b1, &[]); - } - Some((p0, q0)) - } -} diff --git a/library/alloc/src/collections/vec_deque/ring_slices.rs b/library/alloc/src/collections/vec_deque/ring_slices.rs deleted file mode 100644 index dd0fa7d6074..00000000000 --- a/library/alloc/src/collections/vec_deque/ring_slices.rs +++ /dev/null @@ -1,56 +0,0 @@ -use core::ptr::{self}; - -/// Returns the two slices that cover the `VecDeque`'s valid range -pub trait RingSlices: Sized { - fn slice(self, from: usize, to: usize) -> Self; - fn split_at(self, i: usize) -> (Self, Self); - - fn ring_slices(buf: Self, head: usize, tail: usize) -> (Self, Self) { - let contiguous = tail <= head; - if contiguous { - let (empty, buf) = buf.split_at(0); - (buf.slice(tail, head), empty) - } else { - let (mid, right) = buf.split_at(tail); - let (left, _) = mid.split_at(head); - (right, left) - } - } -} - -impl<T> RingSlices for &[T] { - fn slice(self, from: usize, to: usize) -> Self { - &self[from..to] - } - fn split_at(self, i: usize) -> (Self, Self) { - (*self).split_at(i) - } -} - -impl<T> RingSlices for &mut [T] { - fn slice(self, from: usize, to: usize) -> Self { - &mut self[from..to] - } - fn split_at(self, i: usize) -> (Self, Self) { - (*self).split_at_mut(i) - } -} - -impl<T> RingSlices for *mut [T] { - fn slice(self, from: usize, to: usize) -> Self { - assert!(from <= to && to < self.len()); - // Not using `get_unchecked_mut` to keep this a safe operation. - let len = to - from; - ptr::slice_from_raw_parts_mut(self.as_mut_ptr().wrapping_add(from), len) - } - - fn split_at(self, mid: usize) -> (Self, Self) { - let len = self.len(); - let ptr = self.as_mut_ptr(); - assert!(mid <= len); - ( - ptr::slice_from_raw_parts_mut(ptr, mid), - ptr::slice_from_raw_parts_mut(ptr.wrapping_add(mid), len - mid), - ) - } -} diff --git a/library/alloc/src/collections/vec_deque/spec_extend.rs b/library/alloc/src/collections/vec_deque/spec_extend.rs index 97ff8b76524..dccf40ccb38 100644 --- a/library/alloc/src/collections/vec_deque/spec_extend.rs +++ b/library/alloc/src/collections/vec_deque/spec_extend.rs @@ -1,6 +1,6 @@ use crate::alloc::Allocator; use crate::vec; -use core::iter::{ByRefSized, TrustedLen}; +use core::iter::TrustedLen; use core::slice; use super::VecDeque; @@ -17,19 +17,33 @@ where default fn spec_extend(&mut self, mut iter: I) { // This function should be the moral equivalent of: // - // for item in iter { - // self.push_back(item); - // } - while let Some(element) = iter.next() { - if self.len() == self.capacity() { - let (lower, _) = iter.size_hint(); - self.reserve(lower.saturating_add(1)); - } + // for item in iter { + // self.push_back(item); + // } + + // May only be called if `deque.len() < deque.capacity()` + unsafe fn push_unchecked<T, A: Allocator>(deque: &mut VecDeque<T, A>, element: T) { + // SAFETY: Because of the precondition, it's guaranteed that there is space + // in the logical array after the last element. + unsafe { deque.buffer_write(deque.to_physical_idx(deque.len), element) }; + // This can't overflow because `deque.len() < deque.capacity() <= usize::MAX`. + deque.len += 1; + } - let head = self.head; - self.head = self.wrap_add(self.head, 1); - unsafe { - self.buffer_write(head, element); + while let Some(element) = iter.next() { + let (lower, _) = iter.size_hint(); + self.reserve(lower.saturating_add(1)); + + // SAFETY: We just reserved space for at least one element. + unsafe { push_unchecked(self, element) }; + + // Inner loop to avoid repeatedly calling `reserve`. + while self.len < self.capacity() { + let Some(element) = iter.next() else { + return; + }; + // SAFETY: The loop condition guarantees that `self.len() < self.capacity()`. + unsafe { push_unchecked(self, element) }; } } } @@ -39,7 +53,7 @@ impl<T, I, A: Allocator> SpecExtend<T, I> for VecDeque<T, A> where I: TrustedLen<Item = T>, { - default fn spec_extend(&mut self, mut iter: I) { + default fn spec_extend(&mut self, iter: I) { // This is the case for a TrustedLen iterator. let (low, high) = iter.size_hint(); if let Some(additional) = high { @@ -51,35 +65,12 @@ where ); self.reserve(additional); - struct WrapAddOnDrop<'a, T, A: Allocator> { - vec_deque: &'a mut VecDeque<T, A>, - written: usize, - } - - impl<'a, T, A: Allocator> Drop for WrapAddOnDrop<'a, T, A> { - fn drop(&mut self) { - self.vec_deque.head = - self.vec_deque.wrap_add(self.vec_deque.head, self.written); - } - } - - let mut wrapper = WrapAddOnDrop { vec_deque: self, written: 0 }; - - let head_room = wrapper.vec_deque.cap() - wrapper.vec_deque.head; - unsafe { - wrapper.vec_deque.write_iter( - wrapper.vec_deque.head, - ByRefSized(&mut iter).take(head_room), - &mut wrapper.written, - ); - - if additional > head_room { - wrapper.vec_deque.write_iter(0, iter, &mut wrapper.written); - } - } + let written = unsafe { + self.write_iter_wrapping(self.to_physical_idx(self.len), iter, additional) + }; debug_assert_eq!( - additional, wrapper.written, + additional, written, "The number of items written to VecDeque doesn't match the TrustedLen size hint" ); } else { @@ -99,8 +90,8 @@ impl<T, A: Allocator> SpecExtend<T, vec::IntoIter<T>> for VecDeque<T, A> { self.reserve(slice.len()); unsafe { - self.copy_slice(self.head, slice); - self.head = self.wrap_add(self.head, slice.len()); + self.copy_slice(self.to_physical_idx(self.len), slice); + self.len += slice.len(); } iterator.forget_remaining_elements(); } @@ -125,8 +116,8 @@ where self.reserve(slice.len()); unsafe { - self.copy_slice(self.head, slice); - self.head = self.wrap_add(self.head, slice.len()); + self.copy_slice(self.to_physical_idx(self.len), slice); + self.len += slice.len(); } } } diff --git a/library/alloc/src/collections/vec_deque/spec_from_iter.rs b/library/alloc/src/collections/vec_deque/spec_from_iter.rs new file mode 100644 index 00000000000..2708c7fe102 --- /dev/null +++ b/library/alloc/src/collections/vec_deque/spec_from_iter.rs @@ -0,0 +1,33 @@ +use super::{IntoIter, VecDeque}; + +/// Specialization trait used for `VecDeque::from_iter` +pub(super) trait SpecFromIter<T, I> { + fn spec_from_iter(iter: I) -> Self; +} + +impl<T, I> SpecFromIter<T, I> for VecDeque<T> +where + I: Iterator<Item = T>, +{ + default fn spec_from_iter(iterator: I) -> Self { + // Since converting is O(1) now, just re-use the `Vec` logic for + // anything where we can't do something extra-special for `VecDeque`, + // especially as that could save us some monomorphization work + // if one uses the same iterators (like slice ones) with both. + crate::vec::Vec::from_iter(iterator).into() + } +} + +impl<T> SpecFromIter<T, crate::vec::IntoIter<T>> for VecDeque<T> { + #[inline] + fn spec_from_iter(iterator: crate::vec::IntoIter<T>) -> Self { + iterator.into_vecdeque() + } +} + +impl<T> SpecFromIter<T, IntoIter<T>> for VecDeque<T> { + #[inline] + fn spec_from_iter(iterator: IntoIter<T>) -> Self { + iterator.into_vecdeque() + } +} diff --git a/library/alloc/src/collections/vec_deque/tests.rs b/library/alloc/src/collections/vec_deque/tests.rs index 1f2daef213c..205a8ff3c19 100644 --- a/library/alloc/src/collections/vec_deque/tests.rs +++ b/library/alloc/src/collections/vec_deque/tests.rs @@ -3,7 +3,6 @@ use core::iter::TrustedLen; use super::*; #[bench] -#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks fn bench_push_back_100(b: &mut test::Bencher) { let mut deq = VecDeque::with_capacity(101); b.iter(|| { @@ -11,12 +10,11 @@ fn bench_push_back_100(b: &mut test::Bencher) { deq.push_back(i); } deq.head = 0; - deq.tail = 0; + deq.len = 0; }) } #[bench] -#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks fn bench_push_front_100(b: &mut test::Bencher) { let mut deq = VecDeque::with_capacity(101); b.iter(|| { @@ -24,18 +22,21 @@ fn bench_push_front_100(b: &mut test::Bencher) { deq.push_front(i); } deq.head = 0; - deq.tail = 0; + deq.len = 0; }) } #[bench] -#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks fn bench_pop_back_100(b: &mut test::Bencher) { - let mut deq = VecDeque::<i32>::with_capacity(101); + let size = 100; + let mut deq = VecDeque::<i32>::with_capacity(size + 1); + // We'll mess with private state to pretend like `deq` is filled. + // Make sure the buffer is initialized so that we don't read uninit memory. + unsafe { deq.ptr().write_bytes(0u8, size + 1) }; b.iter(|| { - deq.head = 100; - deq.tail = 0; + deq.head = 0; + deq.len = 100; while !deq.is_empty() { test::black_box(deq.pop_back()); } @@ -43,9 +44,9 @@ fn bench_pop_back_100(b: &mut test::Bencher) { } #[bench] -#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks fn bench_retain_whole_10000(b: &mut test::Bencher) { - let v = (1..100000).collect::<VecDeque<u32>>(); + let size = if cfg!(miri) { 1000 } else { 100000 }; + let v = (1..size).collect::<VecDeque<u32>>(); b.iter(|| { let mut v = v.clone(); @@ -54,9 +55,9 @@ fn bench_retain_whole_10000(b: &mut test::Bencher) { } #[bench] -#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks fn bench_retain_odd_10000(b: &mut test::Bencher) { - let v = (1..100000).collect::<VecDeque<u32>>(); + let size = if cfg!(miri) { 1000 } else { 100000 }; + let v = (1..size).collect::<VecDeque<u32>>(); b.iter(|| { let mut v = v.clone(); @@ -65,24 +66,27 @@ fn bench_retain_odd_10000(b: &mut test::Bencher) { } #[bench] -#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks fn bench_retain_half_10000(b: &mut test::Bencher) { - let v = (1..100000).collect::<VecDeque<u32>>(); + let size = if cfg!(miri) { 1000 } else { 100000 }; + let v = (1..size).collect::<VecDeque<u32>>(); b.iter(|| { let mut v = v.clone(); - v.retain(|x| *x > 50000) + v.retain(|x| *x > size / 2) }) } #[bench] -#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks fn bench_pop_front_100(b: &mut test::Bencher) { - let mut deq = VecDeque::<i32>::with_capacity(101); + let size = 100; + let mut deq = VecDeque::<i32>::with_capacity(size + 1); + // We'll mess with private state to pretend like `deq` is filled. + // Make sure the buffer is initialized so that we don't read uninit memory. + unsafe { deq.ptr().write_bytes(0u8, size + 1) }; b.iter(|| { - deq.head = 100; - deq.tail = 0; + deq.head = 0; + deq.len = 100; while !deq.is_empty() { test::black_box(deq.pop_front()); } @@ -101,9 +105,9 @@ fn test_swap_front_back_remove() { for len in 0..final_len { let expected: VecDeque<_> = if back { (0..len).collect() } else { (0..len).rev().collect() }; - for tail_pos in 0..usable_cap { - tester.tail = tail_pos; - tester.head = tail_pos; + for head_pos in 0..usable_cap { + tester.head = head_pos; + tester.len = 0; if back { for i in 0..len * 2 { tester.push_front(i); @@ -120,8 +124,8 @@ fn test_swap_front_back_remove() { assert_eq!(tester.swap_remove_front(idx), Some(len * 2 - 1 - i)); } } - assert!(tester.tail < tester.cap()); - assert!(tester.head < tester.cap()); + assert!(tester.head <= tester.capacity()); + assert!(tester.len <= tester.capacity()); assert_eq!(tester, expected); } } @@ -146,18 +150,18 @@ fn test_insert() { for len in minlen..cap { // 0, 1, 2, .., len - 1 let expected = (0..).take(len).collect::<VecDeque<_>>(); - for tail_pos in 0..cap { + for head_pos in 0..cap { for to_insert in 0..len { - tester.tail = tail_pos; - tester.head = tail_pos; + tester.head = head_pos; + tester.len = 0; for i in 0..len { if i != to_insert { tester.push_back(i); } } tester.insert(to_insert, to_insert); - assert!(tester.tail < tester.cap()); - assert!(tester.head < tester.cap()); + assert!(tester.head <= tester.capacity()); + assert!(tester.len <= tester.capacity()); assert_eq!(tester, expected); } } @@ -253,13 +257,14 @@ fn test_swap_panic() { #[test] fn test_reserve_exact() { let mut tester: VecDeque<i32> = VecDeque::with_capacity(1); - assert!(tester.capacity() == 1); + assert_eq!(tester.capacity(), 1); tester.reserve_exact(50); - assert!(tester.capacity() >= 51); + assert_eq!(tester.capacity(), 50); tester.reserve_exact(40); - assert!(tester.capacity() >= 51); + // reserving won't shrink the buffer + assert_eq!(tester.capacity(), 50); tester.reserve_exact(200); - assert!(tester.capacity() >= 200); + assert_eq!(tester.capacity(), 200); } #[test] @@ -319,6 +324,7 @@ fn test_contains() { #[test] fn test_rotate_left_right() { let mut tester: VecDeque<_> = (1..=10).collect(); + tester.reserve(1); assert_eq!(tester.len(), 10); @@ -459,7 +465,7 @@ fn test_binary_search_key() { } #[test] -fn make_contiguous_big_tail() { +fn make_contiguous_big_head() { let mut tester = VecDeque::with_capacity(15); for i in 0..3 { @@ -474,14 +480,14 @@ fn make_contiguous_big_tail() { assert_eq!(tester.capacity(), 15); assert_eq!((&[9, 8, 7, 6, 5, 4, 3] as &[_], &[0, 1, 2] as &[_]), tester.as_slices()); - let expected_start = tester.head; + let expected_start = tester.as_slices().1.len(); tester.make_contiguous(); - assert_eq!(tester.tail, expected_start); + assert_eq!(tester.head, expected_start); assert_eq!((&[9, 8, 7, 6, 5, 4, 3, 0, 1, 2] as &[_], &[] as &[_]), tester.as_slices()); } #[test] -fn make_contiguous_big_head() { +fn make_contiguous_big_tail() { let mut tester = VecDeque::with_capacity(15); for i in 0..8 { @@ -495,44 +501,46 @@ fn make_contiguous_big_head() { // 01234567......98 let expected_start = 0; tester.make_contiguous(); - assert_eq!(tester.tail, expected_start); + assert_eq!(tester.head, expected_start); assert_eq!((&[9, 8, 0, 1, 2, 3, 4, 5, 6, 7] as &[_], &[] as &[_]), tester.as_slices()); } #[test] fn make_contiguous_small_free() { - let mut tester = VecDeque::with_capacity(15); + let mut tester = VecDeque::with_capacity(16); - for i in 'A' as u8..'I' as u8 { + for i in b'A'..b'I' { tester.push_back(i as char); } - for i in 'I' as u8..'N' as u8 { + for i in b'I'..b'N' { tester.push_front(i as char); } + assert_eq!(tester, ['M', 'L', 'K', 'J', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']); + // ABCDEFGH...MLKJI let expected_start = 0; tester.make_contiguous(); - assert_eq!(tester.tail, expected_start); + assert_eq!(tester.head, expected_start); assert_eq!( (&['M', 'L', 'K', 'J', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] as &[_], &[] as &[_]), tester.as_slices() ); tester.clear(); - for i in 'I' as u8..'N' as u8 { + for i in b'I'..b'N' { tester.push_back(i as char); } - for i in 'A' as u8..'I' as u8 { + for i in b'A'..b'I' { tester.push_front(i as char); } // IJKLM...HGFEDCBA - let expected_start = 0; + let expected_start = 3; tester.make_contiguous(); - assert_eq!(tester.tail, expected_start); + assert_eq!(tester.head, expected_start); assert_eq!( (&['H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'I', 'J', 'K', 'L', 'M'] as &[_], &[] as &[_]), tester.as_slices() @@ -541,16 +549,55 @@ fn make_contiguous_small_free() { #[test] fn make_contiguous_head_to_end() { - let mut dq = VecDeque::with_capacity(3); - dq.push_front('B'); - dq.push_front('A'); - dq.push_back('C'); - dq.make_contiguous(); - let expected_tail = 0; - let expected_head = 3; - assert_eq!(expected_tail, dq.tail); - assert_eq!(expected_head, dq.head); - assert_eq!((&['A', 'B', 'C'] as &[_], &[] as &[_]), dq.as_slices()); + let mut tester = VecDeque::with_capacity(16); + + for i in b'A'..b'L' { + tester.push_back(i as char); + } + + for i in b'L'..b'Q' { + tester.push_front(i as char); + } + + assert_eq!( + tester, + ['P', 'O', 'N', 'M', 'L', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'] + ); + + // ABCDEFGHIJKPONML + let expected_start = 0; + tester.make_contiguous(); + assert_eq!(tester.head, expected_start); + assert_eq!( + ( + &['P', 'O', 'N', 'M', 'L', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'] + as &[_], + &[] as &[_] + ), + tester.as_slices() + ); + + tester.clear(); + for i in b'L'..b'Q' { + tester.push_back(i as char); + } + + for i in b'A'..b'L' { + tester.push_front(i as char); + } + + // LMNOPKJIHGFEDCBA + let expected_start = 0; + tester.make_contiguous(); + assert_eq!(tester.head, expected_start); + assert_eq!( + ( + &['K', 'J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'L', 'M', 'N', 'O', 'P'] + as &[_], + &[] as &[_] + ), + tester.as_slices() + ); } #[test] @@ -584,10 +631,10 @@ fn test_remove() { for len in minlen..cap - 1 { // 0, 1, 2, .., len - 1 let expected = (0..).take(len).collect::<VecDeque<_>>(); - for tail_pos in 0..cap { + for head_pos in 0..cap { for to_remove in 0..=len { - tester.tail = tail_pos; - tester.head = tail_pos; + tester.head = head_pos; + tester.len = 0; for i in 0..len { if i == to_remove { tester.push_back(1234); @@ -598,8 +645,8 @@ fn test_remove() { tester.push_back(1234); } tester.remove(to_remove); - assert!(tester.tail < tester.cap()); - assert!(tester.head < tester.cap()); + assert!(tester.head <= tester.capacity()); + assert!(tester.len <= tester.capacity()); assert_eq!(tester, expected); } } @@ -613,11 +660,11 @@ fn test_range() { let cap = tester.capacity(); let minlen = if cfg!(miri) { cap - 1 } else { 0 }; // Miri is too slow for len in minlen..=cap { - for tail in 0..=cap { + for head in 0..=cap { for start in 0..=len { for end in start..=len { - tester.tail = tail; - tester.head = tail; + tester.head = head; + tester.len = 0; for i in 0..len { tester.push_back(i); } @@ -638,17 +685,17 @@ fn test_range_mut() { let cap = tester.capacity(); for len in 0..=cap { - for tail in 0..=cap { + for head in 0..=cap { for start in 0..=len { for end in start..=len { - tester.tail = tail; - tester.head = tail; + tester.head = head; + tester.len = 0; for i in 0..len { tester.push_back(i); } let head_was = tester.head; - let tail_was = tester.tail; + let len_was = tester.len; // Check that we iterate over the correct values let range: VecDeque<_> = tester.range_mut(start..end).map(|v| *v).collect(); @@ -658,8 +705,8 @@ fn test_range_mut() { // We shouldn't have changed the capacity or made the // head or tail out of bounds assert_eq!(tester.capacity(), cap); - assert_eq!(tester.tail, tail_was); assert_eq!(tester.head, head_was); + assert_eq!(tester.len, len_was); } } } @@ -672,11 +719,11 @@ fn test_drain() { let cap = tester.capacity(); for len in 0..=cap { - for tail in 0..=cap { + for head in 0..cap { for drain_start in 0..=len { for drain_end in drain_start..=len { - tester.tail = tail; - tester.head = tail; + tester.head = head; + tester.len = 0; for i in 0..len { tester.push_back(i); } @@ -689,8 +736,8 @@ fn test_drain() { // We shouldn't have changed the capacity or made the // head or tail out of bounds assert_eq!(tester.capacity(), cap); - assert!(tester.tail < tester.cap()); - assert!(tester.head < tester.cap()); + assert!(tester.head <= tester.capacity()); + assert!(tester.len <= tester.capacity()); // We should see the correct values in the VecDeque let expected: VecDeque<_> = (0..drain_start).chain(drain_end..len).collect(); @@ -702,6 +749,48 @@ fn test_drain() { } #[test] +fn issue_108453() { + let mut deque = VecDeque::with_capacity(10); + + deque.push_back(1u8); + deque.push_back(2); + deque.push_back(3); + + deque.push_front(10); + deque.push_front(9); + + deque.shrink_to(9); + + assert_eq!(deque.into_iter().collect::<Vec<_>>(), vec![9, 10, 1, 2, 3]); +} + +#[test] +fn test_shrink_to() { + // test deques with capacity 16 with all possible head positions, lengths and target capacities. + let cap = 16; + + for len in 0..cap { + for head in 0..cap { + let expected = (1..=len).collect::<VecDeque<_>>(); + + for target_cap in len..cap { + let mut deque = VecDeque::with_capacity(cap); + // currently, `with_capacity` always allocates the exact capacity if it's greater than 8. + assert_eq!(deque.capacity(), cap); + + // we can let the head point anywhere in the buffer since the deque is empty. + deque.head = head; + deque.extend(1..=len); + + deque.shrink_to(target_cap); + + assert_eq!(deque, expected); + } + } + } +} + +#[test] fn test_shrink_to_fit() { // This test checks that every single combination of head and tail position, // is tested. Capacity 15 should be large enough to cover every case. @@ -717,17 +806,18 @@ fn test_shrink_to_fit() { for len in 0..=cap { // 0, 1, 2, .., len - 1 let expected = (0..).take(len).collect::<VecDeque<_>>(); - for tail_pos in 0..=max_cap { - tester.tail = tail_pos; - tester.head = tail_pos; + for head_pos in 0..=max_cap { + tester.reserve(head_pos); + tester.head = head_pos; + tester.len = 0; tester.reserve(63); for i in 0..len { tester.push_back(i); } tester.shrink_to_fit(); assert!(tester.capacity() <= cap); - assert!(tester.tail < tester.cap()); - assert!(tester.head < tester.cap()); + assert!(tester.head <= tester.capacity()); + assert!(tester.len <= tester.capacity()); assert_eq!(tester, expected); } } @@ -754,17 +844,17 @@ fn test_split_off() { // at, at + 1, .., len - 1 (may be empty) let expected_other = (at..).take(len - at).collect::<VecDeque<_>>(); - for tail_pos in 0..cap { - tester.tail = tail_pos; - tester.head = tail_pos; + for head_pos in 0..cap { + tester.head = head_pos; + tester.len = 0; for i in 0..len { tester.push_back(i); } let result = tester.split_off(at); - assert!(tester.tail < tester.cap()); - assert!(tester.head < tester.cap()); - assert!(result.tail < result.cap()); - assert!(result.head < result.cap()); + assert!(tester.head <= tester.capacity()); + assert!(tester.len <= tester.capacity()); + assert!(result.head <= result.capacity()); + assert!(result.len <= result.capacity()); assert_eq!(tester, expected_self); assert_eq!(result, expected_other); } @@ -781,16 +871,10 @@ fn test_from_vec() { vec.extend(0..len); let vd = VecDeque::from(vec.clone()); - assert!(vd.cap().is_power_of_two()); assert_eq!(vd.len(), vec.len()); assert!(vd.into_iter().eq(vec)); } } - - let vec = Vec::from([(); MAXIMUM_ZST_CAPACITY - 1]); - let vd = VecDeque::from(vec.clone()); - assert!(vd.cap().is_power_of_two()); - assert_eq!(vd.len(), vec.len()); } #[test] @@ -842,10 +926,6 @@ fn test_extend_impl(trusted_len: bool) { } assert_eq!(self.test, self.expected); - let (a1, b1) = self.test.as_slices(); - let (a2, b2) = self.expected.as_slices(); - assert_eq!(a1, a2); - assert_eq!(b1, b2); } fn drain<R: RangeBounds<usize> + Clone>(&mut self, range: R) { @@ -868,7 +948,7 @@ fn test_extend_impl(trusted_len: bool) { let mut tester = VecDequeTester::new(trusted_len); // Initial capacity - tester.test_extend(0..tester.remaining_capacity() - 1); + tester.test_extend(0..tester.remaining_capacity()); // Grow tester.test_extend(1024..2048); @@ -876,7 +956,7 @@ fn test_extend_impl(trusted_len: bool) { // Wrap around tester.drain(..128); - tester.test_extend(0..tester.remaining_capacity() - 1); + tester.test_extend(0..tester.remaining_capacity()); // Continue tester.drain(256..); @@ -889,16 +969,6 @@ fn test_extend_impl(trusted_len: bool) { } #[test] -#[should_panic = "capacity overflow"] -fn test_from_vec_zst_overflow() { - use crate::vec::Vec; - let vec = Vec::from([(); MAXIMUM_ZST_CAPACITY]); - let vd = VecDeque::from(vec.clone()); // no room for +1 - assert!(vd.cap().is_power_of_two()); - assert_eq!(vd.len(), vec.len()); -} - -#[test] fn test_from_array() { fn test<const N: usize>() { let mut array: [usize; N] = [0; N]; @@ -913,7 +983,6 @@ fn test_from_array() { assert_eq!(deq[i], i); } - assert!(deq.cap().is_power_of_two()); assert_eq!(deq.len(), N); } test::<0>(); @@ -921,11 +990,6 @@ fn test_from_array() { test::<2>(); test::<32>(); test::<35>(); - - let array = [(); MAXIMUM_ZST_CAPACITY - 1]; - let deq = VecDeque::from(array); - assert!(deq.cap().is_power_of_two()); - assert_eq!(deq.len(), MAXIMUM_ZST_CAPACITY - 1); } #[test] |
