diff options
| author | Jon Gjengset <jon@thesquareplanet.com> | 2020-09-01 09:49:42 -0400 |
|---|---|---|
| committer | Jon Gjengset <jon@thesquareplanet.com> | 2020-09-01 09:49:42 -0400 |
| commit | 010891f8b83d0795d8d92770755f0a0cc1d0a91d (patch) | |
| tree | 62e5619a7dbcd0f1ca3df8863803c9bce980fcad /library/alloc/src | |
| parent | 2f96ce89d03b248c269513b011d328bff2c8dc21 (diff) | |
| parent | e88e908e66cd1e6e30d789b37bcd774951d01856 (diff) | |
| download | rust-010891f8b83d0795d8d92770755f0a0cc1d0a91d.tar.gz rust-010891f8b83d0795d8d92770755f0a0cc1d0a91d.zip | |
Merge branch 'master' into stabilize-vecdeque-make_contiguous
Diffstat (limited to 'library/alloc/src')
28 files changed, 3744 insertions, 980 deletions
diff --git a/library/alloc/src/alloc.rs b/library/alloc/src/alloc.rs index 98c7ac3f2ef..5f09f8def4d 100644 --- a/library/alloc/src/alloc.rs +++ b/library/alloc/src/alloc.rs @@ -3,7 +3,7 @@ #![stable(feature = "alloc_module", since = "1.28.0")] use core::intrinsics::{self, min_align_of_val, size_of_val}; -use core::ptr::{NonNull, Unique}; +use core::ptr::{self, NonNull, Unique}; #[stable(feature = "alloc_module", since = "1.28.0")] #[doc(inline)] @@ -36,8 +36,6 @@ extern "Rust" { /// /// Note: while this type is unstable, the functionality it provides can be /// accessed through the [free functions in `alloc`](index.html#functions). -/// -/// [`AllocRef`]: trait.AllocRef.html #[unstable(feature = "allocator_api", issue = "32838")] #[derive(Copy, Clone, Default, Debug)] pub struct Global; @@ -55,10 +53,6 @@ pub struct Global; /// /// See [`GlobalAlloc::alloc`]. /// -/// [`Global`]: struct.Global.html -/// [`AllocRef`]: trait.AllocRef.html -/// [`GlobalAlloc::alloc`]: trait.GlobalAlloc.html#tymethod.alloc -/// /// # Examples /// /// ``` @@ -92,10 +86,6 @@ pub unsafe fn alloc(layout: Layout) -> *mut u8 { /// # Safety /// /// See [`GlobalAlloc::dealloc`]. -/// -/// [`Global`]: struct.Global.html -/// [`AllocRef`]: trait.AllocRef.html -/// [`GlobalAlloc::dealloc`]: trait.GlobalAlloc.html#tymethod.dealloc #[stable(feature = "global_alloc", since = "1.28.0")] #[inline] pub unsafe fn dealloc(ptr: *mut u8, layout: Layout) { @@ -114,10 +104,6 @@ pub unsafe fn dealloc(ptr: *mut u8, layout: Layout) { /// # Safety /// /// See [`GlobalAlloc::realloc`]. -/// -/// [`Global`]: struct.Global.html -/// [`AllocRef`]: trait.AllocRef.html -/// [`GlobalAlloc::realloc`]: trait.GlobalAlloc.html#method.realloc #[stable(feature = "global_alloc", since = "1.28.0")] #[inline] pub unsafe fn realloc(ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 { @@ -137,10 +123,6 @@ pub unsafe fn realloc(ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 /// /// See [`GlobalAlloc::alloc_zeroed`]. /// -/// [`Global`]: struct.Global.html -/// [`AllocRef`]: trait.AllocRef.html -/// [`GlobalAlloc::alloc_zeroed`]: trait.GlobalAlloc.html#method.alloc_zeroed -/// /// # Examples /// /// ``` @@ -161,28 +143,85 @@ pub unsafe fn alloc_zeroed(layout: Layout) -> *mut u8 { unsafe { __rust_alloc_zeroed(layout.size(), layout.align()) } } -#[unstable(feature = "allocator_api", issue = "32838")] -unsafe impl AllocRef for Global { +impl Global { #[inline] - fn alloc(&mut self, layout: Layout, init: AllocInit) -> Result<MemoryBlock, AllocErr> { - unsafe { - let size = layout.size(); - if size == 0 { - Ok(MemoryBlock { ptr: layout.dangling(), size: 0 }) - } else { - let raw_ptr = match init { - AllocInit::Uninitialized => alloc(layout), - AllocInit::Zeroed => alloc_zeroed(layout), - }; + fn alloc_impl(&mut self, layout: Layout, zeroed: bool) -> Result<NonNull<[u8]>, AllocErr> { + match layout.size() { + 0 => Ok(NonNull::slice_from_raw_parts(layout.dangling(), 0)), + // SAFETY: `layout` is non-zero in size, + size => unsafe { + let raw_ptr = if zeroed { alloc_zeroed(layout) } else { alloc(layout) }; let ptr = NonNull::new(raw_ptr).ok_or(AllocErr)?; - Ok(MemoryBlock { ptr, size }) - } + Ok(NonNull::slice_from_raw_parts(ptr, size)) + }, } } + // Safety: Same as `AllocRef::grow` + #[inline] + unsafe fn grow_impl( + &mut self, + ptr: NonNull<u8>, + old_layout: Layout, + new_layout: Layout, + zeroed: bool, + ) -> Result<NonNull<[u8]>, AllocErr> { + debug_assert!( + new_layout.size() >= old_layout.size(), + "`new_layout.size()` must be greater than or equal to `old_layout.size()`" + ); + + match old_layout.size() { + 0 => self.alloc_impl(new_layout, zeroed), + + // SAFETY: `new_size` is non-zero as `old_size` is greater than or equal to `new_size` + // as required by safety conditions. Other conditions must be upheld by the caller + old_size if old_layout.align() == new_layout.align() => unsafe { + let new_size = new_layout.size(); + + // `realloc` probably checks for `new_size >= old_layout.size()` or something similar. + intrinsics::assume(new_size >= old_layout.size()); + + let raw_ptr = realloc(ptr.as_ptr(), old_layout, new_size); + let ptr = NonNull::new(raw_ptr).ok_or(AllocErr)?; + if zeroed { + raw_ptr.add(old_size).write_bytes(0, new_size - old_size); + } + Ok(NonNull::slice_from_raw_parts(ptr, new_size)) + }, + + // SAFETY: because `new_layout.size()` must be greater than or equal to `old_size`, + // both the old and new memory allocation are valid for reads and writes for `old_size` + // bytes. Also, because the old allocation wasn't yet deallocated, it cannot overlap + // `new_ptr`. Thus, the call to `copy_nonoverlapping` is safe. The safety contract + // for `dealloc` must be upheld by the caller. + old_size => unsafe { + let new_ptr = self.alloc_impl(new_layout, zeroed)?; + ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_mut_ptr(), old_size); + self.dealloc(ptr, old_layout); + Ok(new_ptr) + }, + } + } +} + +#[unstable(feature = "allocator_api", issue = "32838")] +unsafe impl AllocRef for Global { + #[inline] + fn alloc(&mut self, layout: Layout) -> Result<NonNull<[u8]>, AllocErr> { + self.alloc_impl(layout, false) + } + + #[inline] + fn alloc_zeroed(&mut self, layout: Layout) -> Result<NonNull<[u8]>, AllocErr> { + self.alloc_impl(layout, true) + } + #[inline] unsafe fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout) { if layout.size() != 0 { + // SAFETY: `layout` is non-zero in size, + // other conditions must be upheld by the caller unsafe { dealloc(ptr.as_ptr(), layout) } } } @@ -191,78 +230,64 @@ unsafe impl AllocRef for Global { unsafe fn grow( &mut self, ptr: NonNull<u8>, - layout: Layout, - new_size: usize, - placement: ReallocPlacement, - init: AllocInit, - ) -> Result<MemoryBlock, AllocErr> { - let size = layout.size(); - debug_assert!( - new_size >= size, - "`new_size` must be greater than or equal to `memory.size()`" - ); - - if size == new_size { - return Ok(MemoryBlock { ptr, size }); - } + old_layout: Layout, + new_layout: Layout, + ) -> Result<NonNull<[u8]>, AllocErr> { + // SAFETY: all conditions must be upheld by the caller + unsafe { self.grow_impl(ptr, old_layout, new_layout, false) } + } - match placement { - ReallocPlacement::InPlace => Err(AllocErr), - ReallocPlacement::MayMove if layout.size() == 0 => { - let new_layout = - unsafe { Layout::from_size_align_unchecked(new_size, layout.align()) }; - self.alloc(new_layout, init) - } - ReallocPlacement::MayMove => { - // `realloc` probably checks for `new_size > size` or something similar. - let ptr = unsafe { - intrinsics::assume(new_size > size); - realloc(ptr.as_ptr(), layout, new_size) - }; - let memory = - MemoryBlock { ptr: NonNull::new(ptr).ok_or(AllocErr)?, size: new_size }; - unsafe { - init.init_offset(memory, size); - } - Ok(memory) - } - } + #[inline] + unsafe fn grow_zeroed( + &mut self, + ptr: NonNull<u8>, + old_layout: Layout, + new_layout: Layout, + ) -> Result<NonNull<[u8]>, AllocErr> { + // SAFETY: all conditions must be upheld by the caller + unsafe { self.grow_impl(ptr, old_layout, new_layout, true) } } #[inline] unsafe fn shrink( &mut self, ptr: NonNull<u8>, - layout: Layout, - new_size: usize, - placement: ReallocPlacement, - ) -> Result<MemoryBlock, AllocErr> { - let size = layout.size(); + old_layout: Layout, + new_layout: Layout, + ) -> Result<NonNull<[u8]>, AllocErr> { debug_assert!( - new_size <= size, - "`new_size` must be smaller than or equal to `memory.size()`" + new_layout.size() <= old_layout.size(), + "`new_layout.size()` must be smaller than or equal to `old_layout.size()`" ); - if size == new_size { - return Ok(MemoryBlock { ptr, size }); - } + match new_layout.size() { + // SAFETY: conditions must be upheld by the caller + 0 => unsafe { + self.dealloc(ptr, old_layout); + Ok(NonNull::slice_from_raw_parts(new_layout.dangling(), 0)) + }, - match placement { - ReallocPlacement::InPlace => Err(AllocErr), - ReallocPlacement::MayMove if new_size == 0 => { - unsafe { - self.dealloc(ptr, layout); - } - Ok(MemoryBlock { ptr: layout.dangling(), size: 0 }) - } - ReallocPlacement::MayMove => { - // `realloc` probably checks for `new_size < size` or something similar. - let ptr = unsafe { - intrinsics::assume(new_size < size); - realloc(ptr.as_ptr(), layout, new_size) - }; - Ok(MemoryBlock { ptr: NonNull::new(ptr).ok_or(AllocErr)?, size: new_size }) - } + // SAFETY: `new_size` is non-zero. Other conditions must be upheld by the caller + new_size if old_layout.align() == new_layout.align() => unsafe { + // `realloc` probably checks for `new_size <= old_layout.size()` or something similar. + intrinsics::assume(new_size <= old_layout.size()); + + let raw_ptr = realloc(ptr.as_ptr(), old_layout, new_size); + let ptr = NonNull::new(raw_ptr).ok_or(AllocErr)?; + Ok(NonNull::slice_from_raw_parts(ptr, new_size)) + }, + + // SAFETY: because `new_size` must be smaller than or equal to `old_layout.size()`, + // both the old and new memory allocation are valid for reads and writes for `new_size` + // bytes. Also, because the old allocation wasn't yet deallocated, it cannot overlap + // `new_ptr`. Thus, the call to `copy_nonoverlapping` is safe. The safety contract + // for `dealloc` must be upheld by the caller. + new_size => unsafe { + let new_ptr = self.alloc(new_layout)?; + ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_mut_ptr(), new_size); + self.dealloc(ptr, old_layout); + Ok(new_ptr) + }, } } } @@ -274,8 +299,8 @@ unsafe impl AllocRef for Global { #[inline] unsafe fn exchange_malloc(size: usize, align: usize) -> *mut u8 { let layout = unsafe { Layout::from_size_align_unchecked(size, align) }; - match Global.alloc(layout, AllocInit::Uninitialized) { - Ok(memory) => memory.ptr.as_ptr(), + match Global.alloc(layout) { + Ok(ptr) => ptr.as_mut_ptr(), Err(_) => handle_alloc_error(layout), } } diff --git a/library/alloc/src/alloc/tests.rs b/library/alloc/src/alloc/tests.rs index 1c003983df9..f7463d0daac 100644 --- a/library/alloc/src/alloc/tests.rs +++ b/library/alloc/src/alloc/tests.rs @@ -8,17 +8,16 @@ use test::Bencher; fn allocate_zeroed() { unsafe { let layout = Layout::from_size_align(1024, 1).unwrap(); - let memory = Global - .alloc(layout.clone(), AllocInit::Zeroed) - .unwrap_or_else(|_| handle_alloc_error(layout)); + let ptr = + Global.alloc_zeroed(layout.clone()).unwrap_or_else(|_| handle_alloc_error(layout)); - let mut i = memory.ptr.cast::<u8>().as_ptr(); + let mut i = ptr.as_non_null_ptr().as_ptr(); let end = i.add(layout.size()); while i < end { assert_eq!(*i, 0); i = i.offset(1); } - Global.dealloc(memory.ptr, layout); + Global.dealloc(ptr.as_non_null_ptr(), layout); } } diff --git a/library/alloc/src/borrow.rs b/library/alloc/src/borrow.rs index 51c233a21f1..e7260f3956c 100644 --- a/library/alloc/src/borrow.rs +++ b/library/alloc/src/borrow.rs @@ -217,7 +217,7 @@ impl<B: ?Sized + ToOwned> Cow<'_, B> { /// assert!(!bull.is_borrowed()); /// ``` #[unstable(feature = "cow_is_borrowed", issue = "65143")] - pub fn is_borrowed(&self) -> bool { + pub const fn is_borrowed(&self) -> bool { match *self { Borrowed(_) => true, Owned(_) => false, @@ -239,7 +239,7 @@ impl<B: ?Sized + ToOwned> Cow<'_, B> { /// assert!(!bull.is_owned()); /// ``` #[unstable(feature = "cow_is_borrowed", issue = "65143")] - pub fn is_owned(&self) -> bool { + pub const fn is_owned(&self) -> bool { !self.is_borrowed() } diff --git a/library/alloc/src/boxed.rs b/library/alloc/src/boxed.rs index f225aa18853..05211e2037b 100644 --- a/library/alloc/src/boxed.rs +++ b/library/alloc/src/boxed.rs @@ -118,14 +118,13 @@ //! described in [rust-lang/unsafe-code-guidelines#198][ucg#198]. //! //! [ucg#198]: https://github.com/rust-lang/unsafe-code-guidelines/issues/198 -//! [dereferencing]: ../../std/ops/trait.Deref.html -//! [`Box`]: struct.Box.html -//! [`Box<T>`]: struct.Box.html -//! [`Box::<T>::from_raw(value)`]: struct.Box.html#method.from_raw -//! [`Box::<T>::into_raw`]: struct.Box.html#method.into_raw -//! [`Global`]: ../alloc/struct.Global.html -//! [`Layout`]: ../alloc/struct.Layout.html -//! [`Layout::for_value(&*value)`]: ../alloc/struct.Layout.html#method.for_value +//! [dereferencing]: core::ops::Deref +//! [`Box<T>`]: Box +//! [`Box::<T>::from_raw(value)`]: Box::from_raw +//! [`Box::<T>::into_raw`]: Box::into_raw +//! [`Global`]: crate::alloc::Global +//! [`Layout`]: crate::alloc::Layout +//! [`Layout::for_value(&*value)`]: crate::alloc::Layout::for_value #![stable(feature = "rust1", since = "1.0.0")] @@ -143,10 +142,10 @@ use core::ops::{ CoerceUnsized, Deref, DerefMut, DispatchFromDyn, Generator, GeneratorState, Receiver, }; use core::pin::Pin; -use core::ptr::{self, NonNull, Unique}; +use core::ptr::{self, Unique}; use core::task::{Context, Poll}; -use crate::alloc::{self, AllocInit, AllocRef, Global}; +use crate::alloc::{self, AllocRef, Global}; use crate::borrow::Cow; use crate::raw_vec::RawVec; use crate::str::from_boxed_utf8_unchecked; @@ -197,11 +196,7 @@ impl<T> Box<T> { #[unstable(feature = "new_uninit", issue = "63291")] pub fn new_uninit() -> Box<mem::MaybeUninit<T>> { let layout = alloc::Layout::new::<mem::MaybeUninit<T>>(); - let ptr = Global - .alloc(layout, AllocInit::Uninitialized) - .unwrap_or_else(|_| alloc::handle_alloc_error(layout)) - .ptr - .cast(); + let ptr = Global.alloc(layout).unwrap_or_else(|_| alloc::handle_alloc_error(layout)).cast(); unsafe { Box::from_raw(ptr.as_ptr()) } } @@ -227,9 +222,8 @@ impl<T> Box<T> { pub fn new_zeroed() -> Box<mem::MaybeUninit<T>> { let layout = alloc::Layout::new::<mem::MaybeUninit<T>>(); let ptr = Global - .alloc(layout, AllocInit::Zeroed) + .alloc_zeroed(layout) .unwrap_or_else(|_| alloc::handle_alloc_error(layout)) - .ptr .cast(); unsafe { Box::from_raw(ptr.as_ptr()) } } @@ -245,7 +239,6 @@ impl<T> Box<T> { /// Converts a `Box<T>` into a `Box<[T]>` /// /// This conversion does not allocate on the heap and happens in place. - /// #[unstable(feature = "box_into_boxed_slice", issue = "71582")] pub fn into_boxed_slice(boxed: Box<T>) -> Box<[T]> { // *mut T and *mut [T; 1] have the same size and alignment @@ -278,6 +271,29 @@ impl<T> Box<[T]> { pub fn new_uninit_slice(len: usize) -> Box<[mem::MaybeUninit<T>]> { unsafe { RawVec::with_capacity(len).into_box(len) } } + + /// Constructs a new boxed slice with uninitialized contents, with the memory + /// being filled with `0` bytes. + /// + /// See [`MaybeUninit::zeroed`][zeroed] for examples of correct and incorrect usage + /// of this method. + /// + /// # Examples + /// + /// ``` + /// #![feature(new_uninit)] + /// + /// let values = Box::<[u32]>::new_zeroed_slice(3); + /// let values = unsafe { values.assume_init() }; + /// + /// assert_eq!(*values, [0, 0, 0]) + /// ``` + /// + /// [zeroed]: ../../std/mem/union.MaybeUninit.html#method.zeroed + #[unstable(feature = "new_uninit", issue = "63291")] + pub fn new_zeroed_slice(len: usize) -> Box<[mem::MaybeUninit<T>]> { + unsafe { RawVec::with_capacity_zeroed(len).into_box(len) } + } } impl<T> Box<mem::MaybeUninit<T>> { @@ -391,9 +407,8 @@ impl<T: ?Sized> Box<T> { /// } /// ``` /// - /// [memory layout]: index.html#memory-layout - /// [`Layout`]: ../alloc/struct.Layout.html - /// [`Box::into_raw`]: struct.Box.html#method.into_raw + /// [memory layout]: self#memory-layout + /// [`Layout`]: crate::Layout #[stable(feature = "box_raw", since = "1.4.0")] #[inline] pub unsafe fn from_raw(raw: *mut T) -> Self { @@ -438,8 +453,7 @@ impl<T: ?Sized> Box<T> { /// } /// ``` /// - /// [memory layout]: index.html#memory-layout - /// [`Box::from_raw`]: struct.Box.html#method.from_raw + /// [memory layout]: self#memory-layout #[stable(feature = "box_raw", since = "1.4.0")] #[inline] pub fn into_raw(b: Box<T>) -> *mut T { @@ -451,50 +465,6 @@ impl<T: ?Sized> Box<T> { Box::leak(b) as *mut T } - /// Consumes the `Box`, returning the wrapped pointer as `NonNull<T>`. - /// - /// After calling this function, the caller is responsible for the - /// memory previously managed by the `Box`. In particular, the - /// caller should properly destroy `T` and release the memory. The - /// easiest way to do so is to convert the `NonNull<T>` pointer - /// into a raw pointer and back into a `Box` with the [`Box::from_raw`] - /// function. - /// - /// Note: this is an associated function, which means that you have - /// to call it as `Box::into_raw_non_null(b)` - /// instead of `b.into_raw_non_null()`. This - /// is so that there is no conflict with a method on the inner type. - /// - /// [`Box::from_raw`]: struct.Box.html#method.from_raw - /// - /// # Examples - /// - /// ``` - /// #![feature(box_into_raw_non_null)] - /// #![allow(deprecated)] - /// - /// let x = Box::new(5); - /// let ptr = Box::into_raw_non_null(x); - /// - /// // Clean up the memory by converting the NonNull pointer back - /// // into a Box and letting the Box be dropped. - /// let x = unsafe { Box::from_raw(ptr.as_ptr()) }; - /// ``` - #[unstable(feature = "box_into_raw_non_null", issue = "47336")] - #[rustc_deprecated( - since = "1.44.0", - reason = "use `Box::leak(b).into()` or `NonNull::from(Box::leak(b))` instead" - )] - #[inline] - pub fn into_raw_non_null(b: Box<T>) -> NonNull<T> { - // Box is recognized as a "unique pointer" by Stacked Borrows, but internally it is a - // raw pointer for the type system. Turning it directly into a raw pointer would not be - // recognized as "releasing" the unique pointer to permit aliased raw accesses, - // so all raw pointer methods go through `leak` which creates a (unique) - // mutable reference. Turning *that* to a raw pointer behaves correctly. - Box::leak(b).into() - } - #[unstable( feature = "ptr_internals", issue = "none", @@ -527,8 +497,6 @@ impl<T: ?Sized> Box<T> { /// to call it as `Box::leak(b)` instead of `b.leak()`. This /// is so that there is no conflict with a method on the inner type. /// - /// [`Box::from_raw`]: struct.Box.html#method.from_raw - /// /// # Examples /// /// Simple usage: diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap.rs index 8398cfa3bd3..477a598ff5b 100644 --- a/library/alloc/src/collections/binary_heap.rs +++ b/library/alloc/src/collections/binary_heap.rs @@ -12,9 +12,9 @@ //! to solve the [shortest path problem][sssp] on a [directed graph][dir_graph]. //! It shows how to use [`BinaryHeap`] with custom types. //! -//! [dijkstra]: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm -//! [sssp]: http://en.wikipedia.org/wiki/Shortest_path_problem -//! [dir_graph]: http://en.wikipedia.org/wiki/Directed_graph +//! [dijkstra]: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm +//! [sssp]: https://en.wikipedia.org/wiki/Shortest_path_problem +//! [dir_graph]: https://en.wikipedia.org/wiki/Directed_graph //! [`BinaryHeap`]: struct.BinaryHeap.html //! //! ``` diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 24d1f61fa68..f8729c33c67 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -1,13 +1,13 @@ use core::borrow::Borrow; use core::cmp::Ordering; -use core::fmt::Debug; +use core::fmt::{self, Debug}; use core::hash::{Hash, Hasher}; use core::iter::{FromIterator, FusedIterator, Peekable}; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop}; use core::ops::Bound::{Excluded, Included, Unbounded}; use core::ops::{Index, RangeBounds}; -use core::{fmt, ptr}; +use core::ptr; use super::node::{self, marker, ForceResult::*, Handle, InsertResult::*, NodeRef}; use super::search::{self, SearchResult::*}; @@ -152,7 +152,7 @@ impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> { { let root = out_tree.root.as_mut().unwrap(); // unwrap succeeds because we just wrapped - let mut out_node = match root.as_mut().force() { + let mut out_node = match root.node_as_mut().force() { Leaf(leaf) => leaf, Internal(_) => unreachable!(), }; @@ -174,7 +174,7 @@ impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> { { let out_root = BTreeMap::ensure_is_owned(&mut out_tree.root); - let mut out_node = out_root.push_level(); + let mut out_node = out_root.push_internal_level(); let mut in_edge = internal.first_edge(); while let Ok(kv) = in_edge.right_kv() { let (k, v) = kv.into_kv(); @@ -208,7 +208,7 @@ impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> { // Ord` constraint, which this method lacks. BTreeMap { root: None, length: 0 } } else { - clone_subtree(self.root.as_ref().unwrap().as_ref()) // unwrap succeeds because not empty + clone_subtree(self.root.as_ref().unwrap().node_as_ref()) // unwrap succeeds because not empty } } } @@ -221,14 +221,16 @@ where type Key = K; fn get(&self, key: &Q) -> Option<&K> { - match search::search_tree(self.root.as_ref()?.as_ref(), key) { + let root_node = self.root.as_ref()?.node_as_ref(); + match search::search_tree(root_node, key) { Found(handle) => Some(handle.into_kv().0), GoDown(_) => None, } } fn take(&mut self, key: &Q) -> Option<K> { - match search::search_tree(self.root.as_mut()?.as_mut(), key) { + let root_node = self.root.as_mut()?.node_as_mut(); + match search::search_tree(root_node, key) { Found(handle) => Some( OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData } .remove_kv() @@ -240,8 +242,8 @@ where fn replace(&mut self, key: K) -> Option<K> { let root = Self::ensure_is_owned(&mut self.root); - match search::search_tree::<marker::Mut<'_>, K, (), K>(root.as_mut(), &key) { - Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)), + match search::search_tree::<marker::Mut<'_>, K, (), K>(root.node_as_mut(), &key) { + Found(handle) => Some(mem::replace(handle.into_key_mut(), key)), GoDown(handle) => { VacantEntry { key, handle, length: &mut self.length, _marker: PhantomData } .insert(()); @@ -355,6 +357,30 @@ pub struct ValuesMut<'a, K: 'a, V: 'a> { inner: IterMut<'a, K, V>, } +/// An owning iterator over the keys of a `BTreeMap`. +/// +/// This `struct` is created by the [`into_keys`] method on [`BTreeMap`]. +/// See its documentation for more. +/// +/// [`into_keys`]: BTreeMap::into_keys +#[unstable(feature = "map_into_keys_values", issue = "75294")] +#[derive(Debug)] +pub struct IntoKeys<K, V> { + inner: IntoIter<K, V>, +} + +/// An owning iterator over the values of a `BTreeMap`. +/// +/// This `struct` is created by the [`into_values`] method on [`BTreeMap`]. +/// See its documentation for more. +/// +/// [`into_values`]: BTreeMap::into_values +#[unstable(feature = "map_into_keys_values", issue = "75294")] +#[derive(Debug)] +pub struct IntoValues<K, V> { + inner: IntoIter<K, V>, +} + /// An iterator over a sub-range of entries in a `BTreeMap`. /// /// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its @@ -539,7 +565,8 @@ impl<K: Ord, V> BTreeMap<K, V> { K: Borrow<Q>, Q: Ord, { - match search::search_tree(self.root.as_ref()?.as_ref(), key) { + let root_node = self.root.as_ref()?.node_as_ref(); + match search::search_tree(root_node, key) { Found(handle) => Some(handle.into_kv().1), GoDown(_) => None, } @@ -566,7 +593,8 @@ impl<K: Ord, V> BTreeMap<K, V> { K: Borrow<Q>, Q: Ord, { - match search::search_tree(self.root.as_ref()?.as_ref(), k) { + let root_node = self.root.as_ref()?.node_as_ref(); + match search::search_tree(root_node, k) { Found(handle) => Some(handle.into_kv()), GoDown(_) => None, } @@ -591,8 +619,8 @@ impl<K: Ord, V> BTreeMap<K, V> { /// ``` #[unstable(feature = "map_first_last", issue = "62924")] pub fn first_key_value(&self) -> Option<(&K, &V)> { - let front = self.root.as_ref()?.as_ref().first_leaf_edge(); - front.right_kv().ok().map(Handle::into_kv) + let root_node = self.root.as_ref()?.node_as_ref(); + root_node.first_leaf_edge().right_kv().ok().map(Handle::into_kv) } /// Returns the first entry in the map for in-place manipulation. @@ -617,8 +645,8 @@ impl<K: Ord, V> BTreeMap<K, V> { /// ``` #[unstable(feature = "map_first_last", issue = "62924")] pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> { - let front = self.root.as_mut()?.as_mut().first_leaf_edge(); - let kv = front.right_kv().ok()?; + let root_node = self.root.as_mut()?.node_as_mut(); + let kv = root_node.first_leaf_edge().right_kv().ok()?; Some(OccupiedEntry { handle: kv.forget_node_type(), length: &mut self.length, @@ -668,8 +696,8 @@ impl<K: Ord, V> BTreeMap<K, V> { /// ``` #[unstable(feature = "map_first_last", issue = "62924")] pub fn last_key_value(&self) -> Option<(&K, &V)> { - let back = self.root.as_ref()?.as_ref().last_leaf_edge(); - back.left_kv().ok().map(Handle::into_kv) + let root_node = self.root.as_ref()?.node_as_ref(); + root_node.last_leaf_edge().left_kv().ok().map(Handle::into_kv) } /// Returns the last entry in the map for in-place manipulation. @@ -694,8 +722,8 @@ impl<K: Ord, V> BTreeMap<K, V> { /// ``` #[unstable(feature = "map_first_last", issue = "62924")] pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> { - let back = self.root.as_mut()?.as_mut().last_leaf_edge(); - let kv = back.left_kv().ok()?; + let root_node = self.root.as_mut()?.node_as_mut(); + let kv = root_node.last_leaf_edge().left_kv().ok()?; Some(OccupiedEntry { handle: kv.forget_node_type(), length: &mut self.length, @@ -779,8 +807,9 @@ impl<K: Ord, V> BTreeMap<K, V> { K: Borrow<Q>, Q: Ord, { - match search::search_tree(self.root.as_mut()?.as_mut(), key) { - Found(handle) => Some(handle.into_kv_mut().1), + let root_node = self.root.as_mut()?.node_as_mut(); + match search::search_tree(root_node, key) { + Found(handle) => Some(handle.into_val_mut()), GoDown(_) => None, } } @@ -873,7 +902,8 @@ impl<K: Ord, V> BTreeMap<K, V> { K: Borrow<Q>, Q: Ord, { - match search::search_tree(self.root.as_mut()?.as_mut(), key) { + let root_node = self.root.as_mut()?.node_as_mut(); + match search::search_tree(root_node, key) { Found(handle) => Some( OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData } .remove_entry(), @@ -969,7 +999,7 @@ impl<K: Ord, V> BTreeMap<K, V> { R: RangeBounds<T>, { if let Some(root) = &self.root { - let (f, b) = range_search(root.as_ref(), range); + let (f, b) = range_search(root.node_as_ref(), range); Range { front: Some(f), back: Some(b) } } else { @@ -1015,7 +1045,7 @@ impl<K: Ord, V> BTreeMap<K, V> { R: RangeBounds<T>, { if let Some(root) = &mut self.root { - let (f, b) = range_search(root.as_mut(), range); + let (f, b) = range_search(root.node_as_mut(), range); RangeMut { front: Some(f), back: Some(b), _marker: PhantomData } } else { @@ -1045,7 +1075,7 @@ impl<K: Ord, V> BTreeMap<K, V> { pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { // FIXME(@porglezomp) Avoid allocating if we don't insert let root = Self::ensure_is_owned(&mut self.root); - match search::search_tree(root.as_mut(), &key) { + match search::search_tree(root.node_as_mut(), &key) { Found(handle) => { Occupied(OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData }) } @@ -1057,7 +1087,7 @@ impl<K: Ord, V> BTreeMap<K, V> { fn from_sorted_iter<I: Iterator<Item = (K, V)>>(&mut self, iter: I) { let root = Self::ensure_is_owned(&mut self.root); - let mut cur_node = root.as_mut().last_leaf_edge().into_node(); + let mut cur_node = root.node_as_mut().last_leaf_edge().into_node(); // Iterate through all key-value pairs, pushing them into nodes at the right level. for (key, value) in iter { // Try to push key-value pair into the current leaf node. @@ -1080,9 +1110,9 @@ impl<K: Ord, V> BTreeMap<K, V> { test_node = parent.forget_type(); } } - Err(node) => { + Err(_) => { // We are at the top, create a new root node and push there. - open_node = node.into_root_mut().push_level(); + open_node = root.push_internal_level(); break; } } @@ -1092,7 +1122,7 @@ impl<K: Ord, V> BTreeMap<K, V> { let tree_height = open_node.height() - 1; let mut right_tree = node::Root::new_leaf(); for _ in 0..tree_height { - right_tree.push_level(); + right_tree.push_internal_level(); } open_node.push(key, value, right_tree); @@ -1107,7 +1137,7 @@ impl<K: Ord, V> BTreeMap<K, V> { fn fix_right_edge(root: &mut node::Root<K, V>) { // Handle underfull nodes, start from the top. - let mut cur_node = root.as_mut(); + let mut cur_node = root.node_as_mut(); while let Internal(internal) = cur_node.force() { // Check if right-most child is underfull. let mut last_edge = internal.last_edge(); @@ -1171,12 +1201,12 @@ impl<K: Ord, V> BTreeMap<K, V> { let mut right = Self::new(); let right_root = Self::ensure_is_owned(&mut right.root); for _ in 0..left_root.height() { - right_root.push_level(); + right_root.push_internal_level(); } { - let mut left_node = left_root.as_mut(); - let mut right_node = right_root.as_mut(); + let mut left_node = left_root.node_as_mut(); + let mut right_node = right_root.node_as_mut(); loop { let mut split_edge = match search::search_node(left_node, key) { @@ -1206,10 +1236,10 @@ impl<K: Ord, V> BTreeMap<K, V> { right_root.fix_left_border(); if left_root.height() < right_root.height() { - self.recalc_length(); + self.length = left_root.node_as_ref().calc_length(); right.length = total_num - self.len(); } else { - right.recalc_length(); + right.length = right_root.node_as_ref().calc_length(); self.length = total_num - right.len(); } @@ -1253,44 +1283,62 @@ impl<K: Ord, V> BTreeMap<K, V> { { DrainFilter { pred, inner: self.drain_filter_inner() } } + pub(super) fn drain_filter_inner(&mut self) -> DrainFilterInner<'_, K, V> { - let front = self.root.as_mut().map(|r| r.as_mut().first_leaf_edge()); + let root_node = self.root.as_mut().map(|r| r.node_as_mut()); + let front = root_node.map(|rn| rn.first_leaf_edge()); DrainFilterInner { length: &mut self.length, cur_leaf_edge: front } } - /// Calculates the number of elements if it is incorrect. - fn recalc_length(&mut self) { - fn dfs<'a, K, V>(node: NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>) -> usize - where - K: 'a, - V: 'a, - { - let mut res = node.len(); - - if let Internal(node) = node.force() { - let mut edge = node.first_edge(); - loop { - res += dfs(edge.reborrow().descend()); - match edge.right_kv() { - Ok(right_kv) => { - edge = right_kv.right_edge(); - } - Err(_) => { - break; - } - } - } - } - - res - } + /// Creates a consuming iterator visiting all the keys, in sorted order. + /// The map cannot be used after calling this. + /// The iterator element type is `K`. + /// + /// # Examples + /// + /// ``` + /// #![feature(map_into_keys_values)] + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(2, "b"); + /// a.insert(1, "a"); + /// + /// let keys: Vec<i32> = a.into_keys().collect(); + /// assert_eq!(keys, [1, 2]); + /// ``` + #[inline] + #[unstable(feature = "map_into_keys_values", issue = "75294")] + pub fn into_keys(self) -> IntoKeys<K, V> { + IntoKeys { inner: self.into_iter() } + } - self.length = dfs(self.root.as_ref().unwrap().as_ref()); + /// Creates a consuming iterator visiting all the values, in order by key. + /// The map cannot be used after calling this. + /// The iterator element type is `V`. + /// + /// # Examples + /// + /// ``` + /// #![feature(map_into_keys_values)] + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "hello"); + /// a.insert(2, "goodbye"); + /// + /// let values: Vec<&str> = a.into_values().collect(); + /// assert_eq!(values, ["hello", "goodbye"]); + /// ``` + #[inline] + #[unstable(feature = "map_into_keys_values", issue = "75294")] + pub fn into_values(self) -> IntoValues<K, V> { + IntoValues { inner: self.into_iter() } } } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> { +impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V> { type Item = (&'a K, &'a V); type IntoIter = Iter<'a, K, V>; @@ -1359,7 +1407,7 @@ impl<K, V> Clone for Iter<'_, K, V> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap<K, V> { +impl<'a, K, V> IntoIterator for &'a mut BTreeMap<K, V> { type Item = (&'a K, &'a mut V); type IntoIter = IterMut<'a, K, V>; @@ -1681,9 +1729,9 @@ impl<'a, K: 'a, V: 'a> DrainFilterInner<'a, K, V> { let (k, v) = kv.kv_mut(); if pred(k, v) { *self.length -= 1; - let (k, v, leaf_edge_location) = kv.remove_kv_tracking(); - self.cur_leaf_edge = Some(leaf_edge_location); - return Some((k, v)); + let (kv, pos) = kv.remove_kv_tracking(); + self.cur_leaf_edge = Some(pos); + return Some(kv); } self.cur_leaf_edge = Some(kv.next_leaf_edge()); } @@ -1764,6 +1812,82 @@ impl<'a, K, V> Range<'a, K, V> { } } +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl<K, V> Iterator for IntoKeys<K, V> { + type Item = K; + + fn next(&mut self) -> Option<K> { + self.inner.next().map(|(k, _)| k) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } + + fn last(mut self) -> Option<K> { + self.next_back() + } + + fn min(mut self) -> Option<K> { + self.next() + } + + fn max(mut self) -> Option<K> { + self.next_back() + } +} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl<K, V> DoubleEndedIterator for IntoKeys<K, V> { + fn next_back(&mut self) -> Option<K> { + self.inner.next_back().map(|(k, _)| k) + } +} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl<K, V> ExactSizeIterator for IntoKeys<K, V> { + fn len(&self) -> usize { + self.inner.len() + } +} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl<K, V> FusedIterator for IntoKeys<K, V> {} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl<K, V> Iterator for IntoValues<K, V> { + type Item = V; + + fn next(&mut self) -> Option<V> { + self.inner.next().map(|(_, v)| v) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } + + fn last(mut self) -> Option<V> { + self.next_back() + } +} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl<K, V> DoubleEndedIterator for IntoValues<K, V> { + fn next_back(&mut self) -> Option<V> { + self.inner.next_back().map(|(_, v)| v) + } +} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl<K, V> ExactSizeIterator for IntoValues<K, V> { + fn len(&self) -> usize { + self.inner.len() + } +} + +#[unstable(feature = "map_into_keys_values", issue = "75294")] +impl<K, V> FusedIterator for IntoValues<K, V> {} + #[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)> { @@ -2087,7 +2211,7 @@ impl<K, V> BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] pub fn iter(&self) -> Iter<'_, K, V> { if let Some(root) = &self.root { - let (f, b) = full_range_search(root.as_ref()); + let (f, b) = full_range_search(root.node_as_ref()); Iter { range: Range { front: Some(f), back: Some(b) }, length: self.length } } else { @@ -2119,7 +2243,7 @@ impl<K, V> BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { if let Some(root) = &mut self.root { - let (f, b) = full_range_search(root.as_mut()); + let (f, b) = full_range_search(root.node_as_mut()); IterMut { range: RangeMut { front: Some(f), back: Some(b), _marker: PhantomData }, @@ -2448,40 +2572,17 @@ impl<'a, K: Ord, V> VacantEntry<'a, K, V> { pub fn insert(self, value: V) -> &'a mut V { *self.length += 1; - let out_ptr; - - let mut ins_k; - let mut ins_v; - let mut ins_edge; - - let mut cur_parent = match self.handle.insert(self.key, value) { - (Fit(handle), _) => return handle.into_kv_mut().1, - (Split(left, k, v, right), ptr) => { - ins_k = k; - ins_v = v; - ins_edge = right; - out_ptr = ptr; - left.ascend().map_err(|n| n.into_root_mut()) + let out_ptr = match self.handle.insert_recursing(self.key, value) { + (Fit(_), val_ptr) => val_ptr, + (Split(ins), val_ptr) => { + let root = ins.left.into_root_mut(); + root.push_internal_level().push(ins.k, ins.v, ins.right); + val_ptr } }; - - loop { - match cur_parent { - Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) { - Fit(_) => return unsafe { &mut *out_ptr }, - Split(left, k, v, right) => { - ins_k = k; - ins_v = v; - ins_edge = right; - cur_parent = left.ascend().map_err(|n| n.into_root_mut()); - } - }, - Err(root) => { - root.push_level().push(ins_k, ins_v, ins_edge); - return unsafe { &mut *out_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 } } } @@ -2600,7 +2701,7 @@ impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn into_mut(self) -> &'a mut V { - self.handle.into_kv_mut().1 + self.handle.into_val_mut() } /// Sets the value of the entry with the `OccupiedEntry`'s key, @@ -2647,11 +2748,12 @@ impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> { self.remove_kv().1 } + // Body of `remove_entry`, separate to keep the above implementations short. fn remove_kv(self) -> (K, V) { *self.length -= 1; - let (old_key, old_val, _) = self.handle.remove_kv_tracking(); - (old_key, old_val) + let (old_kv, _) = self.handle.remove_kv_tracking(); + old_kv } } @@ -2660,31 +2762,31 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInter /// the leaf edge corresponding to that former pair. fn remove_kv_tracking( self, - ) -> (K, V, Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) { - let (mut pos, old_key, old_val, was_internal) = match self.force() { + ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) { + let (old_kv, mut pos, was_internal) = match self.force() { Leaf(leaf) => { - let (hole, old_key, old_val) = leaf.remove(); - (hole, old_key, old_val, false) + let (old_kv, pos) = leaf.remove(); + (old_kv, pos, false) } Internal(mut internal) => { - // Replace the location freed in the internal node with the next KV, - // and remove that next KV from its leaf. + // Replace the location freed in the internal node with an + // adjacent KV, and remove that adjacent KV from its leaf. + // Always choose the adjacent KV on the left side because + // it is typically faster to pop an element from the end + // of the KV arrays without needing to shift other elements. let key_loc = internal.kv_mut().0 as *mut K; let val_loc = internal.kv_mut().1 as *mut V; - // Deleting from the left side is typically faster since we can - // just pop an element from the end of the KV array without - // needing to shift the other values. let to_remove = internal.left_edge().descend().last_leaf_edge().left_kv().ok(); let to_remove = unsafe { unwrap_unchecked(to_remove) }; - let (hole, key, val) = to_remove.remove(); + let (kv, pos) = to_remove.remove(); - let old_key = unsafe { mem::replace(&mut *key_loc, key) }; - let old_val = unsafe { mem::replace(&mut *val_loc, val) }; + let old_key = unsafe { mem::replace(&mut *key_loc, kv.0) }; + let old_val = unsafe { mem::replace(&mut *val_loc, kv.1) }; - (hole, old_key, old_val, true) + ((old_key, old_val), pos, true) } }; @@ -2709,8 +2811,10 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInter let parent = edge.into_node(); if parent.len() == 0 { - // We must be at the root - parent.into_root_mut().pop_level(); + // The parent that was just emptied must be the root, + // because nodes on a lower level would not have been + // left with a single child. + parent.into_root_mut().pop_internal_level(); break; } else { cur_node = parent.forget_type(); @@ -2737,15 +2841,15 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInter pos = unsafe { unwrap_unchecked(pos.next_kv().ok()).next_leaf_edge() }; } - (old_key, old_val, pos) + (old_kv, pos) } } impl<K, V> node::Root<K, V> { /// Removes empty levels on the top, but keep an empty leaf if the entire tree is empty. fn fix_top(&mut self) { - while self.height() > 0 && self.as_ref().len() == 0 { - self.pop_level(); + while self.height() > 0 && self.node_as_ref().len() == 0 { + self.pop_internal_level(); } } @@ -2753,7 +2857,7 @@ impl<K, V> node::Root<K, V> { self.fix_top(); { - let mut cur_node = self.as_mut(); + let mut cur_node = self.node_as_mut(); while let Internal(node) = cur_node.force() { let mut last_kv = node.last_kv(); @@ -2779,7 +2883,7 @@ impl<K, V> node::Root<K, V> { self.fix_top(); { - let mut cur_node = self.as_mut(); + let mut cur_node = self.node_as_mut(); while let Internal(node) = cur_node.force() { let mut first_kv = node.first_kv(); @@ -2814,6 +2918,10 @@ fn handle_underfull_node<K, V>( Err(_) => return AtRoot, }; + // Prefer the left KV if it exists. Merging with the left side is faster, + // since merging happens towards the left and `node` has fewer elements. + // Stealing from the left side is faster, since we can pop from the end of + // the KV arrays. let (is_left, mut handle) = match parent.left_kv() { Ok(left) => (true, left), Err(parent) => { @@ -2858,3 +2966,6 @@ impl<K: Ord, V, I: Iterator<Item = (K, V)>> Iterator for MergeIter<K, V, I> { } } } + +#[cfg(test)] +mod tests; diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs new file mode 100644 index 00000000000..eb8d86b9693 --- /dev/null +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -0,0 +1,1705 @@ +use crate::boxed::Box; +use crate::collections::btree::navigate::Position; +use crate::collections::btree::node; +use crate::collections::btree_map::Entry::{Occupied, Vacant}; +use crate::collections::BTreeMap; +use crate::fmt::Debug; +use crate::rc::Rc; +use crate::string::String; +use crate::string::ToString; +use crate::vec::Vec; +use std::convert::TryFrom; +use std::iter::FromIterator; +use std::mem; +use std::ops::Bound::{self, Excluded, Included, Unbounded}; +use std::ops::RangeBounds; +use std::panic::{catch_unwind, AssertUnwindSafe}; +use std::sync::atomic::{AtomicUsize, Ordering}; + +use super::super::DeterministicRng; + +// Capacity of a tree with a single level, +// i.e. a tree who's root is a leaf node at height 0. +const NODE_CAPACITY: usize = node::CAPACITY; + +// Minimum number of elements to insert, to guarantee a tree with 2 levels, +// i.e. a tree who's root is an internal node at height 1, with edges to leaf nodes. +// It's not the minimum size: removing an element from such a tree does not always reduce height. +const MIN_INSERTS_HEIGHT_1: usize = NODE_CAPACITY + 1; + +// Minimum number of elements to insert in ascending order, to guarantee a tree with 3 levels, +// i.e. a tree who's root is an internal node at height 2, with edges to more internal nodes. +// It's not the minimum size: removing an element from such a tree does not always reduce height. +const MIN_INSERTS_HEIGHT_2: usize = 89; + +// Gather all references from a mutable iterator and make sure Miri notices if +// using them is dangerous. +fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) { + // Gather all those references. + let mut refs: Vec<&mut T> = iter.collect(); + // Use them all. Twice, to be sure we got all interleavings. + for r in refs.iter_mut() { + mem::swap(dummy, r); + } + for r in refs { + mem::swap(dummy, r); + } +} + +struct SeriesChecker<T> { + previous: Option<T>, +} + +impl<T: Copy + Debug + Ord> SeriesChecker<T> { + fn is_ascending(&mut self, next: T) { + if let Some(previous) = self.previous { + assert!(previous < next, "{:?} >= {:?}", previous, next); + } + self.previous = Some(next); + } +} + +impl<'a, K: 'a, V: 'a> BTreeMap<K, V> { + /// Panics if the map (or the code navigating it) is corrupted. + fn check(&self) + where + K: Copy + Debug + Ord, + { + if let Some(root) = &self.root { + let root_node = root.node_as_ref(); + let mut checker = SeriesChecker { previous: None }; + let mut internal_length = 0; + let mut internal_kv_count = 0; + let mut leaf_length = 0; + root_node.visit_nodes_in_order(|pos| match pos { + Position::Leaf(node) => { + let is_root = root_node.height() == 0; + let min_len = if is_root { 0 } else { node::MIN_LEN }; + assert!(node.len() >= min_len, "{} < {}", node.len(), min_len); + + for &key in node.keys() { + checker.is_ascending(key); + } + leaf_length += node.len(); + } + Position::Internal(node) => { + let is_root = root_node.height() == node.height(); + let min_len = if is_root { 1 } else { node::MIN_LEN }; + assert!(node.len() >= min_len, "{} < {}", node.len(), min_len); + + internal_length += node.len(); + } + Position::InternalKV(kv) => { + let key = *kv.into_kv().0; + checker.is_ascending(key); + + internal_kv_count += 1; + } + }); + assert_eq!(internal_length, internal_kv_count); + assert_eq!(root_node.calc_length(), internal_length + leaf_length); + assert_eq!(self.length, internal_length + leaf_length); + } else { + assert_eq!(self.length, 0); + } + } + + /// Returns the height of the root, if any. + fn height(&self) -> Option<usize> { + self.root.as_ref().map(node::Root::height) + } + + fn dump_keys(&self) -> String + where + K: Debug, + { + if let Some(root) = self.root.as_ref() { + let mut result = String::new(); + let root_node = root.node_as_ref(); + root_node.visit_nodes_in_order(|pos| match pos { + Position::Leaf(leaf) => { + let depth = root_node.height(); + let indent = " ".repeat(depth); + result += &format!("\n{}{:?}", indent, leaf.keys()) + } + Position::Internal(_) => {} + Position::InternalKV(kv) => { + let depth = root_node.height() - kv.into_node().height(); + let indent = " ".repeat(depth); + result += &format!("\n{}{:?}", indent, kv.into_kv().0); + } + }); + result + } else { + String::from("not yet allocated") + } + } +} + +// Test our value of MIN_INSERTS_HEIGHT_2. It may change according to the +// implementation of insertion, but it's best to be aware of when it does. +#[test] +fn test_levels() { + let mut map = BTreeMap::new(); + map.check(); + assert_eq!(map.height(), None); + assert_eq!(map.len(), 0); + + map.insert(0, ()); + while map.height() == Some(0) { + let last_key = *map.last_key_value().unwrap().0; + map.insert(last_key + 1, ()); + } + map.check(); + // Structure: + // - 1 element in internal root node with 2 children + // - 6 elements in left leaf child + // - 5 elements in right leaf child + assert_eq!(map.height(), Some(1)); + assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1, "{}", map.dump_keys()); + + while map.height() == Some(1) { + let last_key = *map.last_key_value().unwrap().0; + map.insert(last_key + 1, ()); + } + println!("{}", map.dump_keys()); + map.check(); + // Structure: + // - 1 element in internal root node with 2 children + // - 6 elements in left internal child with 7 grandchildren + // - 42 elements in left child's 7 grandchildren with 6 elements each + // - 5 elements in right internal child with 6 grandchildren + // - 30 elements in right child's 5 first grandchildren with 6 elements each + // - 5 elements in right child's last grandchild + assert_eq!(map.height(), Some(2)); + assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2, "{}", map.dump_keys()); +} + +#[test] +fn test_basic_large() { + let mut map = BTreeMap::new(); + // Miri is too slow + let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 } else { 10000 }; + let size = size + (size % 2); // round up to even number + assert_eq!(map.len(), 0); + + for i in 0..size { + assert_eq!(map.insert(i, 10 * i), None); + assert_eq!(map.len(), i + 1); + } + + assert_eq!(map.first_key_value(), Some((&0, &0))); + assert_eq!(map.last_key_value(), Some((&(size - 1), &(10 * (size - 1))))); + assert_eq!(map.first_entry().unwrap().key(), &0); + assert_eq!(map.last_entry().unwrap().key(), &(size - 1)); + + for i in 0..size { + assert_eq!(map.get(&i).unwrap(), &(i * 10)); + } + + for i in size..size * 2 { + assert_eq!(map.get(&i), None); + } + + for i in 0..size { + assert_eq!(map.insert(i, 100 * i), Some(10 * i)); + assert_eq!(map.len(), size); + } + + for i in 0..size { + assert_eq!(map.get(&i).unwrap(), &(i * 100)); + } + + for i in 0..size / 2 { + assert_eq!(map.remove(&(i * 2)), Some(i * 200)); + assert_eq!(map.len(), size - i - 1); + } + + for i in 0..size / 2 { + assert_eq!(map.get(&(2 * i)), None); + assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100)); + } + + for i in 0..size / 2 { + assert_eq!(map.remove(&(2 * i)), None); + assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100)); + assert_eq!(map.len(), size / 2 - i - 1); + } + map.check(); +} + +#[test] +fn test_basic_small() { + let mut map = BTreeMap::new(); + // Empty, root is absent (None): + assert_eq!(map.remove(&1), None); + assert_eq!(map.len(), 0); + assert_eq!(map.get(&1), None); + assert_eq!(map.get_mut(&1), None); + assert_eq!(map.first_key_value(), None); + assert_eq!(map.last_key_value(), None); + assert_eq!(map.keys().count(), 0); + assert_eq!(map.values().count(), 0); + assert_eq!(map.range(..).next(), None); + assert_eq!(map.range(..1).next(), None); + assert_eq!(map.range(1..).next(), None); + assert_eq!(map.range(1..=1).next(), None); + assert_eq!(map.range(1..2).next(), None); + assert_eq!(map.height(), None); + assert_eq!(map.insert(1, 1), None); + assert_eq!(map.height(), Some(0)); + map.check(); + + // 1 key-value pair: + assert_eq!(map.len(), 1); + assert_eq!(map.get(&1), Some(&1)); + assert_eq!(map.get_mut(&1), Some(&mut 1)); + assert_eq!(map.first_key_value(), Some((&1, &1))); + assert_eq!(map.last_key_value(), Some((&1, &1))); + assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]); + assert_eq!(map.values().collect::<Vec<_>>(), vec![&1]); + assert_eq!(map.insert(1, 2), Some(1)); + assert_eq!(map.len(), 1); + assert_eq!(map.get(&1), Some(&2)); + assert_eq!(map.get_mut(&1), Some(&mut 2)); + assert_eq!(map.first_key_value(), Some((&1, &2))); + assert_eq!(map.last_key_value(), Some((&1, &2))); + assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]); + assert_eq!(map.values().collect::<Vec<_>>(), vec![&2]); + assert_eq!(map.insert(2, 4), None); + assert_eq!(map.height(), Some(0)); + map.check(); + + // 2 key-value pairs: + assert_eq!(map.len(), 2); + assert_eq!(map.get(&2), Some(&4)); + assert_eq!(map.get_mut(&2), Some(&mut 4)); + assert_eq!(map.first_key_value(), Some((&1, &2))); + assert_eq!(map.last_key_value(), Some((&2, &4))); + assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1, &2]); + assert_eq!(map.values().collect::<Vec<_>>(), vec![&2, &4]); + assert_eq!(map.remove(&1), Some(2)); + assert_eq!(map.height(), Some(0)); + map.check(); + + // 1 key-value pair: + assert_eq!(map.len(), 1); + assert_eq!(map.get(&1), None); + assert_eq!(map.get_mut(&1), None); + assert_eq!(map.get(&2), Some(&4)); + assert_eq!(map.get_mut(&2), Some(&mut 4)); + assert_eq!(map.first_key_value(), Some((&2, &4))); + assert_eq!(map.last_key_value(), Some((&2, &4))); + assert_eq!(map.keys().collect::<Vec<_>>(), vec![&2]); + assert_eq!(map.values().collect::<Vec<_>>(), vec![&4]); + assert_eq!(map.remove(&2), Some(4)); + assert_eq!(map.height(), Some(0)); + map.check(); + + // Empty but root is owned (Some(...)): + assert_eq!(map.len(), 0); + assert_eq!(map.get(&1), None); + assert_eq!(map.get_mut(&1), None); + assert_eq!(map.first_key_value(), None); + assert_eq!(map.last_key_value(), None); + assert_eq!(map.keys().count(), 0); + assert_eq!(map.values().count(), 0); + assert_eq!(map.range(..).next(), None); + assert_eq!(map.range(..1).next(), None); + assert_eq!(map.range(1..).next(), None); + assert_eq!(map.range(1..=1).next(), None); + assert_eq!(map.range(1..2).next(), None); + assert_eq!(map.remove(&1), None); + assert_eq!(map.height(), Some(0)); + map.check(); +} + +#[test] +fn test_iter() { + // Miri is too slow + let size = if cfg!(miri) { 200 } else { 10000 }; + + let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + + fn test<T>(size: usize, mut iter: T) + where + T: Iterator<Item = (usize, usize)>, + { + for i in 0..size { + assert_eq!(iter.size_hint(), (size - i, Some(size - i))); + assert_eq!(iter.next().unwrap(), (i, i)); + } + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + } + test(size, map.iter().map(|(&k, &v)| (k, v))); + test(size, map.iter_mut().map(|(&k, &mut v)| (k, v))); + test(size, map.into_iter()); +} + +#[test] +fn test_iter_rev() { + // Miri is too slow + let size = if cfg!(miri) { 200 } else { 10000 }; + + let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + + fn test<T>(size: usize, mut iter: T) + where + T: Iterator<Item = (usize, usize)>, + { + for i in 0..size { + assert_eq!(iter.size_hint(), (size - i, Some(size - i))); + assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1)); + } + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + } + test(size, map.iter().rev().map(|(&k, &v)| (k, v))); + test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v))); + test(size, map.into_iter().rev()); +} + +/// Specifically tests iter_mut's ability to mutate the value of pairs in-line +fn do_test_iter_mut_mutation<T>(size: usize) +where + T: Copy + Debug + Ord + TryFrom<usize>, + <T as std::convert::TryFrom<usize>>::Error: std::fmt::Debug, +{ + let zero = T::try_from(0).unwrap(); + let mut map: BTreeMap<T, T> = (0..size).map(|i| (T::try_from(i).unwrap(), zero)).collect(); + + // Forward and backward iteration sees enough pairs (also tested elsewhere) + assert_eq!(map.iter_mut().count(), size); + assert_eq!(map.iter_mut().rev().count(), size); + + // Iterate forwards, trying to mutate to unique values + for (i, (k, v)) in map.iter_mut().enumerate() { + assert_eq!(*k, T::try_from(i).unwrap()); + assert_eq!(*v, zero); + *v = T::try_from(i + 1).unwrap(); + } + + // Iterate backwards, checking that mutations succeeded and trying to mutate again + for (i, (k, v)) in map.iter_mut().rev().enumerate() { + assert_eq!(*k, T::try_from(size - i - 1).unwrap()); + assert_eq!(*v, T::try_from(size - i).unwrap()); + *v = T::try_from(2 * size - i).unwrap(); + } + + // Check that backward mutations succeeded + for (i, (k, v)) in map.iter_mut().enumerate() { + assert_eq!(*k, T::try_from(i).unwrap()); + assert_eq!(*v, T::try_from(size + i + 1).unwrap()); + } + map.check(); +} + +#[derive(Clone, Copy, Debug, Eq, PartialEq, PartialOrd, Ord)] +#[repr(align(32))] +struct Align32(usize); + +impl TryFrom<usize> for Align32 { + type Error = (); + + fn try_from(s: usize) -> Result<Align32, ()> { + Ok(Align32(s)) + } +} + +#[test] +fn test_iter_mut_mutation() { + // Check many alignments and trees with roots at various heights. + do_test_iter_mut_mutation::<u8>(0); + do_test_iter_mut_mutation::<u8>(1); + do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_1); + do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_2); + do_test_iter_mut_mutation::<u16>(1); + do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_1); + do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_2); + do_test_iter_mut_mutation::<u32>(1); + do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_1); + do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_2); + do_test_iter_mut_mutation::<u64>(1); + do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_1); + do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_2); + do_test_iter_mut_mutation::<u128>(1); + do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_1); + do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_2); + do_test_iter_mut_mutation::<Align32>(1); + do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_1); + do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_2); +} + +#[test] +#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915> +fn test_values_mut() { + let mut a: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect(); + test_all_refs(&mut 13, a.values_mut()); + a.check(); +} + +#[test] +fn test_values_mut_mutation() { + let mut a = BTreeMap::new(); + a.insert(1, String::from("hello")); + a.insert(2, String::from("goodbye")); + + for value in a.values_mut() { + value.push_str("!"); + } + + let values: Vec<String> = a.values().cloned().collect(); + assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]); + a.check(); +} + +#[test] +#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915> +fn test_iter_entering_root_twice() { + let mut map: BTreeMap<_, _> = (0..2).map(|i| (i, i)).collect(); + let mut it = map.iter_mut(); + let front = it.next().unwrap(); + let back = it.next_back().unwrap(); + assert_eq!(front, (&0, &mut 0)); + assert_eq!(back, (&1, &mut 1)); + *front.1 = 24; + *back.1 = 42; + assert_eq!(front, (&0, &mut 24)); + assert_eq!(back, (&1, &mut 42)); + map.check(); +} + +#[test] +#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915> +fn test_iter_descending_to_same_node_twice() { + let mut map: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)).collect(); + let mut it = map.iter_mut(); + // Descend into first child. + let front = it.next().unwrap(); + // Descend into first child again, after running through second child. + while it.next_back().is_some() {} + // Check immutable access. + assert_eq!(front, (&0, &mut 0)); + // Perform mutable access. + *front.1 = 42; + map.check(); +} + +#[test] +fn test_iter_mixed() { + // Miri is too slow + let size = if cfg!(miri) { 200 } else { 10000 }; + + let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + + fn test<T>(size: usize, mut iter: T) + where + T: Iterator<Item = (usize, usize)> + DoubleEndedIterator, + { + for i in 0..size / 4 { + assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2))); + assert_eq!(iter.next().unwrap(), (i, i)); + assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1)); + } + for i in size / 4..size * 3 / 4 { + assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i))); + assert_eq!(iter.next().unwrap(), (i, i)); + } + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + } + test(size, map.iter().map(|(&k, &v)| (k, v))); + test(size, map.iter_mut().map(|(&k, &mut v)| (k, v))); + test(size, map.into_iter()); +} + +#[test] +#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915> +fn test_iter_min_max() { + let mut a = BTreeMap::new(); + assert_eq!(a.iter().min(), None); + assert_eq!(a.iter().max(), None); + assert_eq!(a.iter_mut().min(), None); + assert_eq!(a.iter_mut().max(), None); + assert_eq!(a.range(..).min(), None); + assert_eq!(a.range(..).max(), None); + assert_eq!(a.range_mut(..).min(), None); + assert_eq!(a.range_mut(..).max(), None); + assert_eq!(a.keys().min(), None); + assert_eq!(a.keys().max(), None); + assert_eq!(a.values().min(), None); + assert_eq!(a.values().max(), None); + assert_eq!(a.values_mut().min(), None); + assert_eq!(a.values_mut().max(), None); + a.insert(1, 42); + a.insert(2, 24); + assert_eq!(a.iter().min(), Some((&1, &42))); + assert_eq!(a.iter().max(), Some((&2, &24))); + assert_eq!(a.iter_mut().min(), Some((&1, &mut 42))); + assert_eq!(a.iter_mut().max(), Some((&2, &mut 24))); + assert_eq!(a.range(..).min(), Some((&1, &42))); + assert_eq!(a.range(..).max(), Some((&2, &24))); + assert_eq!(a.range_mut(..).min(), Some((&1, &mut 42))); + assert_eq!(a.range_mut(..).max(), Some((&2, &mut 24))); + assert_eq!(a.keys().min(), Some(&1)); + assert_eq!(a.keys().max(), Some(&2)); + assert_eq!(a.values().min(), Some(&24)); + assert_eq!(a.values().max(), Some(&42)); + assert_eq!(a.values_mut().min(), Some(&mut 24)); + assert_eq!(a.values_mut().max(), Some(&mut 42)); + a.check(); +} + +fn range_keys(map: &BTreeMap<i32, i32>, range: impl RangeBounds<i32>) -> Vec<i32> { + map.range(range) + .map(|(&k, &v)| { + assert_eq!(k, v); + k + }) + .collect() +} + +#[test] +fn test_range_small() { + let size = 4; + + let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect(); + let all: Vec<_> = (1..=size).collect(); + let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]); + + assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all); + assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all); + assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all); + assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all); + assert_eq!(range_keys(&map, (Included(0), Included(size))), all); + assert_eq!(range_keys(&map, (Included(0), Unbounded)), all); + assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all); + assert_eq!(range_keys(&map, (Included(1), Included(size))), all); + assert_eq!(range_keys(&map, (Included(1), Unbounded)), all); + assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all); + assert_eq!(range_keys(&map, (Unbounded, Included(size))), all); + assert_eq!(range_keys(&map, ..), all); + + assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]); + assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]); + assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]); + assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]); + assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]); + assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]); + assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first); + assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first); + assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first); + assert_eq!(range_keys(&map, (Included(0), Included(1))), first); + assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first); + assert_eq!(range_keys(&map, (Included(1), Included(1))), first); + assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first); + assert_eq!(range_keys(&map, (Unbounded, Included(1))), first); + assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last); + assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last); + assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last); + assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last); + assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last); + assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last); + assert_eq!(range_keys(&map, (Included(size), Included(size))), last); + assert_eq!(range_keys(&map, (Included(size), Unbounded)), last); + assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]); + assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]); + assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]); + assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]); + assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]); + assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]); + + assert_eq!(range_keys(&map, ..3), vec![1, 2]); + assert_eq!(range_keys(&map, 3..), vec![3, 4]); + assert_eq!(range_keys(&map, 2..=3), vec![2, 3]); +} + +#[test] +fn test_range_height_1() { + // Tests tree with a root and 2 leaves. Depending on details we don't want or need + // to rely upon, the single key at the root will be 6 or 7. + + let map: BTreeMap<_, _> = (1..=MIN_INSERTS_HEIGHT_1 as i32).map(|i| (i, i)).collect(); + for &root in &[6, 7] { + assert_eq!(range_keys(&map, (Excluded(root), Excluded(root + 1))), vec![]); + assert_eq!(range_keys(&map, (Excluded(root), Included(root + 1))), vec![root + 1]); + assert_eq!(range_keys(&map, (Included(root), Excluded(root + 1))), vec![root]); + assert_eq!(range_keys(&map, (Included(root), Included(root + 1))), vec![root, root + 1]); + + assert_eq!(range_keys(&map, (Excluded(root - 1), Excluded(root))), vec![]); + assert_eq!(range_keys(&map, (Included(root - 1), Excluded(root))), vec![root - 1]); + assert_eq!(range_keys(&map, (Excluded(root - 1), Included(root))), vec![root]); + assert_eq!(range_keys(&map, (Included(root - 1), Included(root))), vec![root - 1, root]); + } +} + +#[test] +fn test_range_large() { + let size = 200; + + let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect(); + let all: Vec<_> = (1..=size).collect(); + let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]); + + assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all); + assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all); + assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all); + assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all); + assert_eq!(range_keys(&map, (Included(0), Included(size))), all); + assert_eq!(range_keys(&map, (Included(0), Unbounded)), all); + assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all); + assert_eq!(range_keys(&map, (Included(1), Included(size))), all); + assert_eq!(range_keys(&map, (Included(1), Unbounded)), all); + assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all); + assert_eq!(range_keys(&map, (Unbounded, Included(size))), all); + assert_eq!(range_keys(&map, ..), all); + + assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]); + assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]); + assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]); + assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]); + assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]); + assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]); + assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first); + assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first); + assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first); + assert_eq!(range_keys(&map, (Included(0), Included(1))), first); + assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first); + assert_eq!(range_keys(&map, (Included(1), Included(1))), first); + assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first); + assert_eq!(range_keys(&map, (Unbounded, Included(1))), first); + assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last); + assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last); + assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last); + assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last); + assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last); + assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last); + assert_eq!(range_keys(&map, (Included(size), Included(size))), last); + assert_eq!(range_keys(&map, (Included(size), Unbounded)), last); + assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]); + assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]); + assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]); + assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]); + assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]); + assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]); + + fn check<'a, L, R>(lhs: L, rhs: R) + where + L: IntoIterator<Item = (&'a i32, &'a i32)>, + R: IntoIterator<Item = (&'a i32, &'a i32)>, + { + let lhs: Vec<_> = lhs.into_iter().collect(); + let rhs: Vec<_> = rhs.into_iter().collect(); + assert_eq!(lhs, rhs); + } + + check(map.range(..=100), map.range(..101)); + check(map.range(5..=8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]); + check(map.range(-1..=2), vec![(&1, &1), (&2, &2)]); +} + +#[test] +fn test_range_inclusive_max_value() { + let max = usize::MAX; + let map: BTreeMap<_, _> = vec![(max, 0)].into_iter().collect(); + + assert_eq!(map.range(max..=max).collect::<Vec<_>>(), &[(&max, &0)]); +} + +#[test] +fn test_range_equal_empty_cases() { + let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect(); + assert_eq!(map.range((Included(2), Excluded(2))).next(), None); + assert_eq!(map.range((Excluded(2), Included(2))).next(), None); +} + +#[test] +#[should_panic] +fn test_range_equal_excluded() { + let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect(); + map.range((Excluded(2), Excluded(2))); +} + +#[test] +#[should_panic] +fn test_range_backwards_1() { + let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect(); + map.range((Included(3), Included(2))); +} + +#[test] +#[should_panic] +fn test_range_backwards_2() { + let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect(); + map.range((Included(3), Excluded(2))); +} + +#[test] +#[should_panic] +fn test_range_backwards_3() { + let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect(); + map.range((Excluded(3), Included(2))); +} + +#[test] +#[should_panic] +fn test_range_backwards_4() { + let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect(); + map.range((Excluded(3), Excluded(2))); +} + +#[test] +fn test_range_1000() { + // Miri is too slow + let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 as u32 } else { 1000 }; + let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + + fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) { + let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v)); + let mut pairs = (0..size).map(|i| (i, i)); + + for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) { + assert_eq!(kv, pair); + } + assert_eq!(kvs.next(), None); + assert_eq!(pairs.next(), None); + } + test(&map, size, Included(&0), Excluded(&size)); + test(&map, size, Unbounded, Excluded(&size)); + test(&map, size, Included(&0), Included(&(size - 1))); + test(&map, size, Unbounded, Included(&(size - 1))); + test(&map, size, Included(&0), Unbounded); + test(&map, size, Unbounded, Unbounded); +} + +#[test] +fn test_range_borrowed_key() { + let mut map = BTreeMap::new(); + map.insert("aardvark".to_string(), 1); + map.insert("baboon".to_string(), 2); + map.insert("coyote".to_string(), 3); + map.insert("dingo".to_string(), 4); + // NOTE: would like to use simply "b".."d" here... + let mut iter = map.range::<str, _>((Included("b"), Excluded("d"))); + assert_eq!(iter.next(), Some((&"baboon".to_string(), &2))); + assert_eq!(iter.next(), Some((&"coyote".to_string(), &3))); + assert_eq!(iter.next(), None); +} + +#[test] +fn test_range() { + let size = 200; + // Miri is too slow + let step = if cfg!(miri) { 66 } else { 1 }; + let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + + for i in (0..size).step_by(step) { + for j in (i..size).step_by(step) { + let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v)); + let mut pairs = (i..=j).map(|i| (i, i)); + + for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) { + assert_eq!(kv, pair); + } + assert_eq!(kvs.next(), None); + assert_eq!(pairs.next(), None); + } + } +} + +#[test] +fn test_range_mut() { + let size = 200; + // Miri is too slow + let step = if cfg!(miri) { 66 } else { 1 }; + let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + + for i in (0..size).step_by(step) { + for j in (i..size).step_by(step) { + let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v)); + let mut pairs = (i..=j).map(|i| (i, i)); + + for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) { + assert_eq!(kv, pair); + } + assert_eq!(kvs.next(), None); + assert_eq!(pairs.next(), None); + } + } + map.check(); +} + +mod test_drain_filter { + use super::*; + + #[test] + fn empty() { + let mut map: BTreeMap<i32, i32> = BTreeMap::new(); + map.drain_filter(|_, _| unreachable!("there's nothing to decide on")); + assert!(map.is_empty()); + map.check(); + } + + #[test] + fn consuming_nothing() { + let pairs = (0..3).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + assert!(map.drain_filter(|_, _| false).eq(std::iter::empty())); + map.check(); + } + + #[test] + fn consuming_all() { + let pairs = (0..3).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + assert!(map.drain_filter(|_, _| true).eq(pairs)); + map.check(); + } + + #[test] + fn mutating_and_keeping() { + let pairs = (0..3).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + assert!( + map.drain_filter(|_, v| { + *v += 6; + false + }) + .eq(std::iter::empty()) + ); + assert!(map.keys().copied().eq(0..3)); + assert!(map.values().copied().eq(6..9)); + map.check(); + } + + #[test] + fn mutating_and_removing() { + let pairs = (0..3).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + assert!( + map.drain_filter(|_, v| { + *v += 6; + true + }) + .eq((0..3).map(|i| (i, i + 6))) + ); + assert!(map.is_empty()); + map.check(); + } + + #[test] + fn underfull_keeping_all() { + let pairs = (0..3).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + map.drain_filter(|_, _| false); + assert!(map.keys().copied().eq(0..3)); + map.check(); + } + + #[test] + fn underfull_removing_one() { + let pairs = (0..3).map(|i| (i, i)); + for doomed in 0..3 { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i == doomed); + assert_eq!(map.len(), 2); + map.check(); + } + } + + #[test] + fn underfull_keeping_one() { + let pairs = (0..3).map(|i| (i, i)); + for sacred in 0..3 { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i != sacred); + assert!(map.keys().copied().eq(sacred..=sacred)); + map.check(); + } + } + + #[test] + fn underfull_removing_all() { + let pairs = (0..3).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + map.drain_filter(|_, _| true); + assert!(map.is_empty()); + map.check(); + } + + #[test] + fn height_0_keeping_all() { + let pairs = (0..NODE_CAPACITY).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + map.drain_filter(|_, _| false); + assert!(map.keys().copied().eq(0..NODE_CAPACITY)); + map.check(); + } + + #[test] + fn height_0_removing_one() { + let pairs = (0..NODE_CAPACITY).map(|i| (i, i)); + for doomed in 0..NODE_CAPACITY { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i == doomed); + assert_eq!(map.len(), NODE_CAPACITY - 1); + map.check(); + } + } + + #[test] + fn height_0_keeping_one() { + let pairs = (0..NODE_CAPACITY).map(|i| (i, i)); + for sacred in 0..NODE_CAPACITY { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i != sacred); + assert!(map.keys().copied().eq(sacred..=sacred)); + map.check(); + } + } + + #[test] + fn height_0_removing_all() { + let pairs = (0..NODE_CAPACITY).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + map.drain_filter(|_, _| true); + assert!(map.is_empty()); + map.check(); + } + + #[test] + fn height_0_keeping_half() { + let mut map: BTreeMap<_, _> = (0..16).map(|i| (i, i)).collect(); + assert_eq!(map.drain_filter(|i, _| *i % 2 == 0).count(), 8); + assert_eq!(map.len(), 8); + map.check(); + } + + #[test] + fn height_1_removing_all() { + let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + map.drain_filter(|_, _| true); + assert!(map.is_empty()); + map.check(); + } + + #[test] + fn height_1_removing_one() { + let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)); + for doomed in 0..MIN_INSERTS_HEIGHT_1 { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i == doomed); + assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1 - 1); + map.check(); + } + } + + #[test] + fn height_1_keeping_one() { + let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)); + for sacred in 0..MIN_INSERTS_HEIGHT_1 { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i != sacred); + assert!(map.keys().copied().eq(sacred..=sacred)); + map.check(); + } + } + + #[test] + fn height_2_removing_one() { + let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); + for doomed in (0..MIN_INSERTS_HEIGHT_2).step_by(12) { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i == doomed); + assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1); + map.check(); + } + } + + #[test] + fn height_2_keeping_one() { + let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); + for sacred in (0..MIN_INSERTS_HEIGHT_2).step_by(12) { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i != sacred); + assert!(map.keys().copied().eq(sacred..=sacred)); + map.check(); + } + } + + #[test] + fn height_2_removing_all() { + let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + map.drain_filter(|_, _| true); + assert!(map.is_empty()); + map.check(); + } + + #[test] + fn drop_panic_leak() { + static PREDS: AtomicUsize = AtomicUsize::new(0); + static DROPS: AtomicUsize = AtomicUsize::new(0); + + struct D; + impl Drop for D { + fn drop(&mut self) { + if DROPS.fetch_add(1, Ordering::SeqCst) == 1 { + panic!("panic in `drop`"); + } + } + } + + // Keys are multiples of 4, so that each key is counted by a hexadecimal digit. + let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>(); + + catch_unwind(move || { + drop(map.drain_filter(|i, _| { + PREDS.fetch_add(1usize << i, Ordering::SeqCst); + true + })) + }) + .unwrap_err(); + + assert_eq!(PREDS.load(Ordering::SeqCst), 0x011); + assert_eq!(DROPS.load(Ordering::SeqCst), 3); + } + + #[test] + fn pred_panic_leak() { + static PREDS: AtomicUsize = AtomicUsize::new(0); + static DROPS: AtomicUsize = AtomicUsize::new(0); + + struct D; + impl Drop for D { + fn drop(&mut self) { + DROPS.fetch_add(1, Ordering::SeqCst); + } + } + + // Keys are multiples of 4, so that each key is counted by a hexadecimal digit. + let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>(); + + catch_unwind(AssertUnwindSafe(|| { + drop(map.drain_filter(|i, _| { + PREDS.fetch_add(1usize << i, Ordering::SeqCst); + match i { + 0 => true, + _ => panic!(), + } + })) + })) + .unwrap_err(); + + assert_eq!(PREDS.load(Ordering::SeqCst), 0x011); + assert_eq!(DROPS.load(Ordering::SeqCst), 1); + assert_eq!(map.len(), 2); + assert_eq!(map.first_entry().unwrap().key(), &4); + assert_eq!(map.last_entry().unwrap().key(), &8); + map.check(); + } + + // Same as above, but attempt to use the iterator again after the panic in the predicate + #[test] + fn pred_panic_reuse() { + static PREDS: AtomicUsize = AtomicUsize::new(0); + static DROPS: AtomicUsize = AtomicUsize::new(0); + + struct D; + impl Drop for D { + fn drop(&mut self) { + DROPS.fetch_add(1, Ordering::SeqCst); + } + } + + // Keys are multiples of 4, so that each key is counted by a hexadecimal digit. + let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>(); + + { + let mut it = map.drain_filter(|i, _| { + PREDS.fetch_add(1usize << i, Ordering::SeqCst); + match i { + 0 => true, + _ => panic!(), + } + }); + catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err(); + // Iterator behaviour after a panic is explicitly unspecified, + // so this is just the current implementation: + let result = catch_unwind(AssertUnwindSafe(|| it.next())); + assert!(matches!(result, Ok(None))); + } + + assert_eq!(PREDS.load(Ordering::SeqCst), 0x011); + assert_eq!(DROPS.load(Ordering::SeqCst), 1); + assert_eq!(map.len(), 2); + assert_eq!(map.first_entry().unwrap().key(), &4); + assert_eq!(map.last_entry().unwrap().key(), &8); + map.check(); + } +} + +#[test] +fn test_borrow() { + // make sure these compile -- using the Borrow trait + { + let mut map = BTreeMap::new(); + map.insert("0".to_string(), 1); + assert_eq!(map["0"], 1); + } + + { + let mut map = BTreeMap::new(); + map.insert(Box::new(0), 1); + assert_eq!(map[&0], 1); + } + + { + let mut map = BTreeMap::new(); + map.insert(Box::new([0, 1]) as Box<[i32]>, 1); + assert_eq!(map[&[0, 1][..]], 1); + } + + { + let mut map = BTreeMap::new(); + map.insert(Rc::new(0), 1); + assert_eq!(map[&0], 1); + } +} + +#[test] +fn test_entry() { + let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)]; + + let mut map: BTreeMap<_, _> = xs.iter().cloned().collect(); + + // Existing key (insert) + match map.entry(1) { + Vacant(_) => unreachable!(), + Occupied(mut view) => { + assert_eq!(view.get(), &10); + assert_eq!(view.insert(100), 10); + } + } + assert_eq!(map.get(&1).unwrap(), &100); + assert_eq!(map.len(), 6); + + // Existing key (update) + match map.entry(2) { + Vacant(_) => unreachable!(), + Occupied(mut view) => { + let v = view.get_mut(); + *v *= 10; + } + } + assert_eq!(map.get(&2).unwrap(), &200); + assert_eq!(map.len(), 6); + map.check(); + + // Existing key (take) + match map.entry(3) { + Vacant(_) => unreachable!(), + Occupied(view) => { + assert_eq!(view.remove(), 30); + } + } + assert_eq!(map.get(&3), None); + assert_eq!(map.len(), 5); + map.check(); + + // Inexistent key (insert) + match map.entry(10) { + Occupied(_) => unreachable!(), + Vacant(view) => { + assert_eq!(*view.insert(1000), 1000); + } + } + assert_eq!(map.get(&10).unwrap(), &1000); + assert_eq!(map.len(), 6); + map.check(); +} + +#[test] +fn test_extend_ref() { + let mut a = BTreeMap::new(); + a.insert(1, "one"); + let mut b = BTreeMap::new(); + b.insert(2, "two"); + b.insert(3, "three"); + + a.extend(&b); + + assert_eq!(a.len(), 3); + assert_eq!(a[&1], "one"); + assert_eq!(a[&2], "two"); + assert_eq!(a[&3], "three"); + a.check(); +} + +#[test] +fn test_zst() { + let mut m = BTreeMap::new(); + assert_eq!(m.len(), 0); + + assert_eq!(m.insert((), ()), None); + assert_eq!(m.len(), 1); + + assert_eq!(m.insert((), ()), Some(())); + assert_eq!(m.len(), 1); + assert_eq!(m.iter().count(), 1); + + m.clear(); + assert_eq!(m.len(), 0); + + for _ in 0..100 { + m.insert((), ()); + } + + assert_eq!(m.len(), 1); + assert_eq!(m.iter().count(), 1); + m.check(); +} + +// This test's only purpose is to ensure that zero-sized keys with nonsensical orderings +// do not cause segfaults when used with zero-sized values. All other map behavior is +// undefined. +#[test] +fn test_bad_zst() { + use std::cmp::Ordering; + + #[derive(Clone, Copy, Debug)] + struct Bad; + + impl PartialEq for Bad { + fn eq(&self, _: &Self) -> bool { + false + } + } + + impl Eq for Bad {} + + impl PartialOrd for Bad { + fn partial_cmp(&self, _: &Self) -> Option<Ordering> { + Some(Ordering::Less) + } + } + + impl Ord for Bad { + fn cmp(&self, _: &Self) -> Ordering { + Ordering::Less + } + } + + let mut m = BTreeMap::new(); + + for _ in 0..100 { + m.insert(Bad, Bad); + } + m.check(); +} + +#[test] +fn test_clone() { + let mut map = BTreeMap::new(); + let size = MIN_INSERTS_HEIGHT_1; + assert_eq!(map.len(), 0); + + for i in 0..size { + assert_eq!(map.insert(i, 10 * i), None); + assert_eq!(map.len(), i + 1); + map.check(); + assert_eq!(map, map.clone()); + } + + for i in 0..size { + assert_eq!(map.insert(i, 100 * i), Some(10 * i)); + assert_eq!(map.len(), size); + map.check(); + assert_eq!(map, map.clone()); + } + + for i in 0..size / 2 { + assert_eq!(map.remove(&(i * 2)), Some(i * 200)); + assert_eq!(map.len(), size - i - 1); + map.check(); + assert_eq!(map, map.clone()); + } + + for i in 0..size / 2 { + assert_eq!(map.remove(&(2 * i)), None); + assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100)); + assert_eq!(map.len(), size / 2 - i - 1); + map.check(); + assert_eq!(map, map.clone()); + } + + // Test a tree with 2 semi-full levels and a tree with 3 levels. + map = (1..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect(); + assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1); + assert_eq!(map, map.clone()); + map.insert(0, 0); + assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2); + assert_eq!(map, map.clone()); + map.check(); +} + +#[test] +fn test_clone_from() { + let mut map1 = BTreeMap::new(); + let max_size = MIN_INSERTS_HEIGHT_1; + + // Range to max_size inclusive, because i is the size of map1 being tested. + for i in 0..=max_size { + let mut map2 = BTreeMap::new(); + for j in 0..i { + let mut map1_copy = map2.clone(); + map1_copy.clone_from(&map1); // small cloned from large + assert_eq!(map1_copy, map1); + let mut map2_copy = map1.clone(); + map2_copy.clone_from(&map2); // large cloned from small + assert_eq!(map2_copy, map2); + map2.insert(100 * j + 1, 2 * j + 1); + } + map2.clone_from(&map1); // same length + map2.check(); + assert_eq!(map2, map1); + map1.insert(i, 10 * i); + map1.check(); + } +} + +#[test] +#[allow(dead_code)] +fn test_variance() { + use std::collections::btree_map::{IntoIter, Iter, Keys, Range, Values}; + + fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> { + v + } + fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> { + v + } + fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> { + v + } + fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> { + v + } + fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> { + v + } + fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> { + v + } + fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> { + v + } + fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> { + v + } + fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> { + v + } + fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> { + v + } +} + +#[test] +fn test_occupied_entry_key() { + let mut a = BTreeMap::new(); + let key = "hello there"; + let value = "value goes here"; + assert!(a.is_empty()); + a.insert(key.clone(), value.clone()); + assert_eq!(a.len(), 1); + assert_eq!(a[key], value); + + match a.entry(key.clone()) { + Vacant(_) => panic!(), + Occupied(e) => assert_eq!(key, *e.key()), + } + assert_eq!(a.len(), 1); + assert_eq!(a[key], value); + a.check(); +} + +#[test] +fn test_vacant_entry_key() { + let mut a = BTreeMap::new(); + let key = "hello there"; + let value = "value goes here"; + + assert!(a.is_empty()); + match a.entry(key.clone()) { + Occupied(_) => panic!(), + Vacant(e) => { + assert_eq!(key, *e.key()); + e.insert(value.clone()); + } + } + assert_eq!(a.len(), 1); + assert_eq!(a[key], value); + a.check(); +} + +#[test] +fn test_first_last_entry() { + let mut a = BTreeMap::new(); + assert!(a.first_entry().is_none()); + assert!(a.last_entry().is_none()); + a.insert(1, 42); + assert_eq!(a.first_entry().unwrap().key(), &1); + assert_eq!(a.last_entry().unwrap().key(), &1); + a.insert(2, 24); + assert_eq!(a.first_entry().unwrap().key(), &1); + assert_eq!(a.last_entry().unwrap().key(), &2); + a.insert(0, 6); + assert_eq!(a.first_entry().unwrap().key(), &0); + assert_eq!(a.last_entry().unwrap().key(), &2); + let (k1, v1) = a.first_entry().unwrap().remove_entry(); + assert_eq!(k1, 0); + assert_eq!(v1, 6); + let (k2, v2) = a.last_entry().unwrap().remove_entry(); + assert_eq!(k2, 2); + assert_eq!(v2, 24); + assert_eq!(a.first_entry().unwrap().key(), &1); + assert_eq!(a.last_entry().unwrap().key(), &1); + a.check(); +} + +#[test] +fn test_insert_into_full_left() { + let mut map: BTreeMap<_, _> = (0..NODE_CAPACITY).map(|i| (i * 2, ())).collect(); + assert!(map.insert(NODE_CAPACITY, ()).is_none()); + map.check(); +} + +#[test] +fn test_insert_into_full_right() { + let mut map: BTreeMap<_, _> = (0..NODE_CAPACITY).map(|i| (i * 2, ())).collect(); + assert!(map.insert(NODE_CAPACITY + 2, ()).is_none()); + map.check(); +} + +macro_rules! create_append_test { + ($name:ident, $len:expr) => { + #[test] + fn $name() { + let mut a = BTreeMap::new(); + for i in 0..8 { + a.insert(i, i); + } + + let mut b = BTreeMap::new(); + for i in 5..$len { + b.insert(i, 2 * i); + } + + a.append(&mut b); + + assert_eq!(a.len(), $len); + assert_eq!(b.len(), 0); + + for i in 0..$len { + if i < 5 { + assert_eq!(a[&i], i); + } else { + assert_eq!(a[&i], 2 * i); + } + } + + a.check(); + assert_eq!(a.remove(&($len - 1)), Some(2 * ($len - 1))); + assert_eq!(a.insert($len - 1, 20), None); + a.check(); + } + }; +} + +// These are mostly for testing the algorithm that "fixes" the right edge after insertion. +// Single node. +create_append_test!(test_append_9, 9); +// Two leafs that don't need fixing. +create_append_test!(test_append_17, 17); +// Two leafs where the second one ends up underfull and needs stealing at the end. +create_append_test!(test_append_14, 14); +// Two leafs where the second one ends up empty because the insertion finished at the root. +create_append_test!(test_append_12, 12); +// Three levels; insertion finished at the root. +create_append_test!(test_append_144, 144); +// Three levels; insertion finished at leaf while there is an empty node on the second level. +create_append_test!(test_append_145, 145); +// Tests for several randomly chosen sizes. +create_append_test!(test_append_170, 170); +create_append_test!(test_append_181, 181); +#[cfg(not(miri))] // Miri is too slow +create_append_test!(test_append_239, 239); +#[cfg(not(miri))] // Miri is too slow +create_append_test!(test_append_1700, 1700); + +fn rand_data(len: usize) -> Vec<(u32, u32)> { + let mut rng = DeterministicRng::new(); + Vec::from_iter((0..len).map(|_| (rng.next(), rng.next()))) +} + +#[test] +fn test_split_off_empty_right() { + let mut data = rand_data(173); + + let mut map = BTreeMap::from_iter(data.clone()); + let right = map.split_off(&(data.iter().max().unwrap().0 + 1)); + map.check(); + right.check(); + + data.sort(); + assert!(map.into_iter().eq(data)); + assert!(right.into_iter().eq(None)); +} + +#[test] +fn test_split_off_empty_left() { + let mut data = rand_data(314); + + let mut map = BTreeMap::from_iter(data.clone()); + let right = map.split_off(&data.iter().min().unwrap().0); + map.check(); + right.check(); + + data.sort(); + assert!(map.into_iter().eq(None)); + assert!(right.into_iter().eq(data)); +} + +// In a tree with 3 levels, if all but a part of the first leaf node is split off, +// make sure fix_top eliminates both top levels. +#[test] +fn test_split_off_tiny_left_height_2() { + let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); + let mut left: BTreeMap<_, _> = pairs.clone().collect(); + let right = left.split_off(&1); + left.check(); + right.check(); + assert_eq!(left.len(), 1); + assert_eq!(right.len(), MIN_INSERTS_HEIGHT_2 - 1); + assert_eq!(*left.first_key_value().unwrap().0, 0); + assert_eq!(*right.first_key_value().unwrap().0, 1); +} + +// In a tree with 3 levels, if only part of the last leaf node is split off, +// make sure fix_top eliminates both top levels. +#[test] +fn test_split_off_tiny_right_height_2() { + let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); + let last = MIN_INSERTS_HEIGHT_2 - 1; + let mut left: BTreeMap<_, _> = pairs.clone().collect(); + assert_eq!(*left.last_key_value().unwrap().0, last); + let right = left.split_off(&last); + left.check(); + right.check(); + assert_eq!(left.len(), MIN_INSERTS_HEIGHT_2 - 1); + assert_eq!(right.len(), 1); + assert_eq!(*left.last_key_value().unwrap().0, last - 1); + assert_eq!(*right.last_key_value().unwrap().0, last); +} + +#[test] +fn test_split_off_large_random_sorted() { + // Miri is too slow + let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) }; + // special case with maximum height. + data.sort(); + + let mut map = BTreeMap::from_iter(data.clone()); + let key = data[data.len() / 2].0; + let right = map.split_off(&key); + map.check(); + right.check(); + + assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key))); + assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key))); +} + +#[test] +fn test_into_iter_drop_leak_height_0() { + static DROPS: AtomicUsize = AtomicUsize::new(0); + + struct D; + + impl Drop for D { + fn drop(&mut self) { + if DROPS.fetch_add(1, Ordering::SeqCst) == 3 { + panic!("panic in `drop`"); + } + } + } + + let mut map = BTreeMap::new(); + map.insert("a", D); + map.insert("b", D); + map.insert("c", D); + map.insert("d", D); + map.insert("e", D); + + catch_unwind(move || drop(map.into_iter())).unwrap_err(); + + assert_eq!(DROPS.load(Ordering::SeqCst), 5); +} + +#[test] +fn test_into_iter_drop_leak_height_1() { + let size = MIN_INSERTS_HEIGHT_1; + static DROPS: AtomicUsize = AtomicUsize::new(0); + static PANIC_POINT: AtomicUsize = AtomicUsize::new(0); + + struct D; + impl Drop for D { + fn drop(&mut self) { + if DROPS.fetch_add(1, Ordering::SeqCst) == PANIC_POINT.load(Ordering::SeqCst) { + panic!("panic in `drop`"); + } + } + } + + for panic_point in vec![0, 1, size - 2, size - 1] { + DROPS.store(0, Ordering::SeqCst); + PANIC_POINT.store(panic_point, Ordering::SeqCst); + let map: BTreeMap<_, _> = (0..size).map(|i| (i, D)).collect(); + catch_unwind(move || drop(map.into_iter())).unwrap_err(); + assert_eq!(DROPS.load(Ordering::SeqCst), size); + } +} + +#[test] +fn test_into_keys() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: BTreeMap<_, _> = vec.into_iter().collect(); + let keys: Vec<_> = map.into_keys().collect(); + + assert_eq!(keys.len(), 3); + assert!(keys.contains(&1)); + assert!(keys.contains(&2)); + assert!(keys.contains(&3)); +} + +#[test] +fn test_into_values() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: BTreeMap<_, _> = vec.into_iter().collect(); + let values: Vec<_> = map.into_values().collect(); + + assert_eq!(values.len(), 3); + assert!(values.contains(&'a')); + assert!(values.contains(&'b')); + assert!(values.contains(&'c')); +} diff --git a/library/alloc/src/collections/btree/mod.rs b/library/alloc/src/collections/btree/mod.rs index 543ff41a4d4..6c8a588eb58 100644 --- a/library/alloc/src/collections/btree/mod.rs +++ b/library/alloc/src/collections/btree/mod.rs @@ -25,3 +25,30 @@ pub unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T { } }) } + +#[cfg(test)] +/// XorShiftRng +struct DeterministicRng { + x: u32, + y: u32, + z: u32, + w: u32, +} + +#[cfg(test)] +impl DeterministicRng { + fn new() -> Self { + DeterministicRng { x: 0x193a6754, y: 0xa8a7d469, z: 0x97830e05, w: 0x113ba7bb } + } + + fn next(&mut self) -> u32 { + 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/btree/navigate.rs b/library/alloc/src/collections/btree/navigate.rs index 44f0e25bbd7..b7b66ac7cec 100644 --- a/library/alloc/src/collections/btree/navigate.rs +++ b/library/alloc/src/collections/btree/navigate.rs @@ -1,3 +1,5 @@ +use core::intrinsics; +use core::mem; use core::ptr; use super::node::{marker, ForceResult::*, Handle, NodeRef}; @@ -19,7 +21,7 @@ impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::E Ok(internal_kv) => return Ok(internal_kv), Err(last_edge) => match last_edge.into_node().ascend() { Ok(parent_edge) => parent_edge.forget_node_type(), - Err(root) => return Err(root.forget_type()), + Err(root) => return Err(root), }, } } @@ -40,7 +42,30 @@ impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::E Ok(internal_kv) => return Ok(internal_kv), Err(last_edge) => match last_edge.into_node().ascend() { Ok(parent_edge) => parent_edge.forget_node_type(), - Err(root) => return Err(root.forget_type()), + Err(root) => return Err(root), + }, + } + } + } +} + +impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> { + /// Given an internal edge handle, returns [`Result::Ok`] with a handle to the neighboring KV + /// on the right side, which is either in the same internal node or in an ancestor node. + /// If the internal edge is the last one in the tree, returns [`Result::Err`] with the root node. + pub fn next_kv( + self, + ) -> Result< + Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV>, + NodeRef<BorrowType, K, V, marker::Internal>, + > { + let mut edge = self; + loop { + edge = match edge.right_kv() { + Ok(internal_kv) => return Ok(internal_kv), + Err(last_edge) => match last_edge.into_node().ascend() { + Ok(parent_edge) => parent_edge, + Err(root) => return Err(root), }, } } @@ -79,16 +104,24 @@ def_next_kv_uncheched_dealloc! {unsafe fn next_kv_unchecked_dealloc: right_kv} def_next_kv_uncheched_dealloc! {unsafe fn next_back_kv_unchecked_dealloc: left_kv} /// This replaces the value behind the `v` unique reference by calling the -/// relevant function. +/// relevant function, and returns a result obtained along the way. /// -/// Safety: The change closure must not panic. +/// If a panic occurs in the `change` closure, the entire process will be aborted. #[inline] -unsafe fn replace<T, R>(v: &mut T, change: impl FnOnce(T) -> (T, R)) -> R { +fn replace<T, R>(v: &mut T, change: impl FnOnce(T) -> (T, R)) -> R { + struct PanicGuard; + impl Drop for PanicGuard { + fn drop(&mut self) { + intrinsics::abort() + } + } + let guard = PanicGuard; let value = unsafe { ptr::read(v) }; let (new_value, ret) = change(value); unsafe { ptr::write(v, new_value); } + mem::forget(guard); ret } @@ -97,26 +130,22 @@ impl<'a, K, V> Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Ed /// key and value in between. /// Unsafe because the caller must ensure that the leaf edge is not the last one in the tree. pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) { - unsafe { - replace(self, |leaf_edge| { - let kv = leaf_edge.next_kv(); - let kv = unwrap_unchecked(kv.ok()); - (kv.next_leaf_edge(), kv.into_kv()) - }) - } + replace(self, |leaf_edge| { + let kv = leaf_edge.next_kv(); + let kv = unsafe { unwrap_unchecked(kv.ok()) }; + (kv.next_leaf_edge(), kv.into_kv()) + }) } /// Moves the leaf edge handle to the previous leaf edge and returns references to the /// key and value in between. /// Unsafe because the caller must ensure that the leaf edge is not the first one in the tree. pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) { - unsafe { - replace(self, |leaf_edge| { - let kv = leaf_edge.next_back_kv(); - let kv = unwrap_unchecked(kv.ok()); - (kv.next_back_leaf_edge(), kv.into_kv()) - }) - } + replace(self, |leaf_edge| { + let kv = leaf_edge.next_back_kv(); + let kv = unsafe { unwrap_unchecked(kv.ok()) }; + (kv.next_back_leaf_edge(), kv.into_kv()) + }) } } @@ -127,16 +156,14 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge /// - The caller must ensure that the leaf edge is not the last one in the tree. /// - Using the updated handle may well invalidate the returned references. pub unsafe fn next_unchecked(&mut self) -> (&'a mut K, &'a mut V) { - unsafe { - let kv = replace(self, |leaf_edge| { - let kv = leaf_edge.next_kv(); - let kv = unwrap_unchecked(kv.ok()); - (ptr::read(&kv).next_leaf_edge(), kv) - }); - // Doing the descend (and perhaps another move) invalidates the references - // returned by `into_kv_mut`, so we have to do this last. - kv.into_kv_mut() - } + let kv = replace(self, |leaf_edge| { + let kv = leaf_edge.next_kv(); + let kv = unsafe { unwrap_unchecked(kv.ok()) }; + (unsafe { ptr::read(&kv) }.next_leaf_edge(), kv) + }); + // Doing the descend (and perhaps another move) invalidates the references + // returned by `into_kv_mut`, so we have to do this last. + kv.into_kv_mut() } /// Moves the leaf edge handle to the previous leaf and returns references to the @@ -145,16 +172,14 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge /// - The caller must ensure that the leaf edge is not the first one in the tree. /// - Using the updated handle may well invalidate the returned references. pub unsafe fn next_back_unchecked(&mut self) -> (&'a mut K, &'a mut V) { - unsafe { - let kv = replace(self, |leaf_edge| { - let kv = leaf_edge.next_back_kv(); - let kv = unwrap_unchecked(kv.ok()); - (ptr::read(&kv).next_back_leaf_edge(), kv) - }); - // Doing the descend (and perhaps another move) invalidates the references - // returned by `into_kv_mut`, so we have to do this last. - kv.into_kv_mut() - } + let kv = replace(self, |leaf_edge| { + let kv = leaf_edge.next_back_kv(); + let kv = unsafe { unwrap_unchecked(kv.ok()) }; + (unsafe { ptr::read(&kv) }.next_back_leaf_edge(), kv) + }); + // Doing the descend (and perhaps another move) invalidates the references + // returned by `into_kv_mut`, so we have to do this last. + kv.into_kv_mut() } } @@ -172,14 +197,12 @@ impl<K, V> Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge> { /// call this method again subject to both preconditions listed in the first point, /// or call counterpart `next_back_unchecked` subject to its preconditions. pub unsafe fn next_unchecked(&mut self) -> (K, V) { - unsafe { - replace(self, |leaf_edge| { - let kv = next_kv_unchecked_dealloc(leaf_edge); - let k = ptr::read(kv.reborrow().into_kv().0); - let v = ptr::read(kv.reborrow().into_kv().1); - (kv.next_leaf_edge(), (k, v)) - }) - } + replace(self, |leaf_edge| { + let kv = unsafe { next_kv_unchecked_dealloc(leaf_edge) }; + let k = unsafe { ptr::read(kv.reborrow().into_kv().0) }; + let v = unsafe { ptr::read(kv.reborrow().into_kv().1) }; + (kv.next_leaf_edge(), (k, v)) + }) } /// Moves the leaf edge handle to the previous leaf edge and returns the key @@ -195,14 +218,12 @@ impl<K, V> Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge> { /// call this method again subject to both preconditions listed in the first point, /// or call counterpart `next_unchecked` subject to its preconditions. pub unsafe fn next_back_unchecked(&mut self) -> (K, V) { - unsafe { - replace(self, |leaf_edge| { - let kv = next_back_kv_unchecked_dealloc(leaf_edge); - let k = ptr::read(kv.reborrow().into_kv().0); - let v = ptr::read(kv.reborrow().into_kv().1); - (kv.next_back_leaf_edge(), (k, v)) - }) - } + replace(self, |leaf_edge| { + let kv = unsafe { next_back_kv_unchecked_dealloc(leaf_edge) }; + let k = unsafe { ptr::read(kv.reborrow().into_kv().0) }; + let v = unsafe { ptr::read(kv.reborrow().into_kv().1) }; + (kv.next_back_leaf_edge(), (k, v)) + }) } } @@ -234,6 +255,59 @@ impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { } } +pub enum Position<BorrowType, K, V> { + Leaf(NodeRef<BorrowType, K, V, marker::Leaf>), + Internal(NodeRef<BorrowType, K, V, marker::Internal>), + InternalKV(Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV>), +} + +impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> { + /// Visits leaf nodes and internal KVs in order of ascending keys, and also + /// visits internal nodes as a whole in a depth first order, meaning that + /// internal nodes precede their individual KVs and their child nodes. + pub fn visit_nodes_in_order<F>(self, mut visit: F) + where + F: FnMut(Position<marker::Immut<'a>, K, V>), + { + match self.force() { + Leaf(leaf) => visit(Position::Leaf(leaf)), + Internal(internal) => { + visit(Position::Internal(internal)); + let mut edge = internal.first_edge(); + loop { + edge = match edge.descend().force() { + Leaf(leaf) => { + visit(Position::Leaf(leaf)); + match edge.next_kv() { + Ok(kv) => { + visit(Position::InternalKV(kv)); + kv.right_edge() + } + Err(_) => return, + } + } + Internal(internal) => { + visit(Position::Internal(internal)); + internal.first_edge() + } + } + } + } + } + } + + /// Calculates the number of elements in a (sub)tree. + pub fn calc_length(self) -> usize { + let mut result = 0; + self.visit_nodes_in_order(|pos| match pos { + Position::Leaf(node) => result += node.len(), + Position::Internal(node) => result += node.len(), + Position::InternalKV(_) => (), + }); + result + } +} + impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> { /// Returns the leaf edge closest to a KV for forward navigation. pub fn next_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> { diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index f7bd64608d6..acc2ae73572 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -43,6 +43,9 @@ use crate::boxed::Box; const B: usize = 6; pub const MIN_LEN: usize = B - 1; pub const CAPACITY: usize = 2 * B - 1; +const KV_IDX_CENTER: usize = B - 1; +const EDGE_IDX_LEFT_OF_CENTER: usize = B - 1; +const EDGE_IDX_RIGHT_OF_CENTER: usize = B; /// The underlying representation of leaf nodes. #[repr(C)] @@ -163,7 +166,8 @@ impl<K, V> Root<K, V> { Root { node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })), height: 0 } } - pub fn as_ref(&self) -> NodeRef<marker::Immut<'_>, K, V, marker::LeafOrInternal> { + /// Borrows and returns an immutable reference to the node owned by the root. + pub fn node_as_ref(&self) -> NodeRef<marker::Immut<'_>, K, V, marker::LeafOrInternal> { NodeRef { height: self.height, node: self.node.as_ptr(), @@ -172,7 +176,8 @@ impl<K, V> Root<K, V> { } } - pub fn as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::LeafOrInternal> { + /// Borrows and returns a mutable reference to the node owned by the root. + pub fn node_as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::LeafOrInternal> { NodeRef { height: self.height, node: self.node.as_ptr(), @@ -191,8 +196,9 @@ impl<K, V> Root<K, V> { } /// Adds a new internal node with a single edge, pointing to the previous root, and make that - /// new node the root. This increases the height by 1 and is the opposite of `pop_level`. - pub fn push_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> { + /// new node the root. This increases the height by 1 and is the opposite of + /// `pop_internal_level`. + pub fn push_internal_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> { let mut new_node = Box::new(unsafe { InternalNode::new() }); new_node.edges[0].write(unsafe { BoxedNode::from_ptr(self.node.as_ptr()) }); @@ -213,23 +219,24 @@ impl<K, V> Root<K, V> { ret } - /// Removes the root node, using its first child as the new root. This cannot be called when - /// the tree consists only of a leaf node. As it is intended only to be called when the root - /// has only one edge, no cleanup is done on any of the other children of the root. - /// This decreases the height by 1 and is the opposite of `push_level`. - pub fn pop_level(&mut self) { + /// Removes the internal root node, using its first child as the new root. + /// As it is intended only to be called when the root has only one child, + /// no cleanup is done on any of the other children of the root. + /// This decreases the height by 1 and is the opposite of `push_internal_level`. + /// Panics if there is no internal level, i.e. if the root is a leaf. + pub fn pop_internal_level(&mut self) { assert!(self.height > 0); let top = self.node.ptr; self.node = unsafe { BoxedNode::from_ptr( - self.as_mut().cast_unchecked::<marker::Internal>().first_edge().descend().node, + self.node_as_mut().cast_unchecked::<marker::Internal>().first_edge().descend().node, ) }; self.height -= 1; unsafe { - (*self.as_mut().as_leaf_mut()).parent = ptr::null(); + (*self.node_as_mut().as_leaf_mut()).parent = ptr::null(); } unsafe { @@ -305,12 +312,6 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> { self.height } - /// Removes any static information about whether this node is a `Leaf` or an - /// `Internal` node. - pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { - NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData } - } - /// Temporarily takes out another, immutable reference to the same node. fn reborrow(&self) -> NodeRef<marker::Immut<'_>, K, V, Type> { NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData } @@ -415,7 +416,7 @@ impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> { impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> { /// Unsafely asserts to the compiler some static information about whether this /// node is a `Leaf` or an `Internal`. - unsafe fn cast_unchecked<NewType>(&mut self) -> NodeRef<marker::Mut<'_>, K, V, NewType> { + unsafe fn cast_unchecked<NewType>(self) -> NodeRef<marker::Mut<'a>, K, V, NewType> { NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData } } @@ -466,12 +467,6 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> { fn into_val_slice(self) -> &'a [V] { unsafe { slice::from_raw_parts(MaybeUninit::first_ptr(&self.as_leaf().vals), self.len()) } } - - fn into_slices(self) -> (&'a [K], &'a [V]) { - // SAFETY: equivalent to reborrow() except not requiring Type: 'a - let k = unsafe { ptr::read(&self) }; - (k.into_key_slice(), self.into_val_slice()) - } } impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> { @@ -626,7 +621,7 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> { let edge = ptr::read(internal.as_internal().edges.get_unchecked(idx + 1).as_ptr()); let mut new_root = Root { node: edge, height: internal.height - 1 }; - (*new_root.as_mut().as_leaf_mut()).parent = ptr::null(); + (*new_root.node_as_mut().as_leaf_mut()).parent = ptr::null(); Some(new_root) } }; @@ -658,7 +653,7 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> { ); let mut new_root = Root { node: edge, height: internal.height - 1 }; - (*new_root.as_mut().as_leaf_mut()).parent = ptr::null(); + (*new_root.node_as_mut().as_leaf_mut()).parent = ptr::null(); for i in 0..old_len { Handle::new_edge(internal.reborrow_mut(), i).correct_parent_link(); @@ -729,7 +724,7 @@ impl<Node: Copy, Type> Clone for Handle<Node, Type> { } impl<Node, Type> Handle<Node, Type> { - /// Retrieves the node that contains the edge of key/value pair this handle points to. + /// Retrieves the node that contains the edge or key/value pair this handle points to. pub fn into_node(self) -> Node { self.node } @@ -829,13 +824,34 @@ impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, mar } } -impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> { +enum InsertionPlace { + Left(usize), + Right(usize), +} + +/// Given an edge index where we want to insert into a node filled to capacity, +/// computes a sensible KV index of a split point and where to perform the insertion. +/// The goal of the split point is for its key and value to end up in a parent node; +/// the keys, values and edges to the left of the split point become the left child; +/// the keys, values and edges to the right of the split point become the right child. +fn splitpoint(edge_idx: usize) -> (usize, InsertionPlace) { + debug_assert!(edge_idx <= CAPACITY); + // Rust issue #74834 tries to explain these symmetric rules. + match edge_idx { + 0..EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER - 1, InsertionPlace::Left(edge_idx)), + EDGE_IDX_LEFT_OF_CENTER => (KV_IDX_CENTER, InsertionPlace::Left(edge_idx)), + EDGE_IDX_RIGHT_OF_CENTER => (KV_IDX_CENTER, InsertionPlace::Right(0)), + _ => (KV_IDX_CENTER + 1, InsertionPlace::Right(edge_idx - (KV_IDX_CENTER + 1 + 1))), + } +} + +impl<'a, K, V, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::Edge> { + /// Helps implementations of `insert_fit` for a particular `NodeType`, + /// by taking care of leaf data. /// 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 { + fn leafy_insert_fit(&mut self, key: K, val: V) { // Necessary for correctness, but in a private module debug_assert!(self.node.len() < CAPACITY); @@ -844,35 +860,49 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge slice_insert(self.node.vals_mut(), self.idx, val); (*self.node.as_leaf_mut()).len += 1; - - self.node.vals_mut().get_unchecked_mut(self.idx) } } +} + +impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> { + /// 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 { + self.leafy_insert_fit(key, val); + unsafe { self.node.vals_mut().get_unchecked_mut(self.idx) } + } +} +impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> { /// 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. - pub fn insert(mut self, key: K, val: V) -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) { + fn insert(mut self, key: K, val: V) -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) { if self.node.len() < CAPACITY { let ptr = self.insert_fit(key, val); let kv = unsafe { Handle::new_kv(self.node, self.idx) }; (InsertResult::Fit(kv), ptr) } else { - let middle = unsafe { Handle::new_kv(self.node, B) }; + let (middle_kv_idx, insertion) = splitpoint(self.idx); + let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) }; let (mut left, k, v, mut right) = middle.split(); - let ptr = if self.idx <= B { - unsafe { Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val) } - } else { - unsafe { + let ptr = match insertion { + InsertionPlace::Left(insert_idx) => unsafe { + Handle::new_edge(left.reborrow_mut(), insert_idx).insert_fit(key, val) + }, + InsertionPlace::Right(insert_idx) => unsafe { Handle::new_edge( - right.as_mut().cast_unchecked::<marker::Leaf>(), - self.idx - (B + 1), + right.node_as_mut().cast_unchecked::<marker::Leaf>(), + insert_idx, ) .insert_fit(key, val) - } + }, }; - (InsertResult::Split(left, k, v, right), ptr) + (InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }), ptr) } } } @@ -890,14 +920,6 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: } } - /// Unsafely asserts to the compiler some static information about whether the underlying - /// node of this handle is a `Leaf` or an `Internal`. - unsafe fn cast_unchecked<NewType>( - &mut self, - ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NewType>, marker::Edge> { - unsafe { Handle::new_edge(self.node.cast_unchecked(), self.idx) } - } - /// Inserts a new key/value pair and an edge that will go to the right of that new pair /// between this edge and the key/value pair to the right of this edge. This method assumes /// that there is enough space in the node for the new pair to fit. @@ -907,8 +929,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: debug_assert!(edge.height == self.node.height - 1); unsafe { - // This cast is a lie, but it allows us to reuse the key/value insertion logic. - self.cast_unchecked::<marker::Leaf>().insert_fit(key, val); + self.leafy_insert_fit(key, val); slice_insert( slice::from_raw_parts_mut( @@ -928,7 +949,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: /// Inserts a new key/value pair and an edge that will go to the right of that new pair /// between this edge and the key/value pair to the right of this edge. This method splits /// the node if there isn't enough room. - pub fn insert( + fn insert( mut self, key: K, val: V, @@ -941,22 +962,58 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: let kv = unsafe { Handle::new_kv(self.node, self.idx) }; InsertResult::Fit(kv) } else { - let middle = unsafe { Handle::new_kv(self.node, B) }; + let (middle_kv_idx, insertion) = splitpoint(self.idx); + let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) }; let (mut left, k, v, mut right) = middle.split(); - if self.idx <= B { - unsafe { - Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val, edge); - } - } else { - unsafe { + match insertion { + InsertionPlace::Left(insert_idx) => unsafe { + Handle::new_edge(left.reborrow_mut(), insert_idx).insert_fit(key, val, edge); + }, + InsertionPlace::Right(insert_idx) => unsafe { Handle::new_edge( - right.as_mut().cast_unchecked::<marker::Internal>(), - self.idx - (B + 1), + right.node_as_mut().cast_unchecked::<marker::Internal>(), + insert_idx, ) .insert_fit(key, val, edge); - } + }, + } + InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }) + } + } +} + +impl<'a, K: 'a, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> { + /// 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, and tries to + /// insert the split off portion into the parent node recursively, until the root is reached. + /// + /// If the returned result is a `Fit`, its handle's node can be this edge's node or an ancestor. + /// If the returned result is a `Split`, the `left` field will be the root node. + /// The returned pointer points to the inserted value. + pub fn insert_recursing( + self, + key: K, + value: V, + ) -> (InsertResult<'a, K, V, marker::LeafOrInternal>, *mut V) { + let (mut split, val_ptr) = match self.insert(key, value) { + (InsertResult::Fit(handle), ptr) => { + return (InsertResult::Fit(handle.forget_node_type()), ptr); } - InsertResult::Split(left, k, v, right) + (InsertResult::Split(split), val_ptr) => (split, val_ptr), + }; + + loop { + split = match split.left.ascend() { + Ok(parent) => match parent.insert(split.k, split.v, split.right) { + InsertResult::Fit(handle) => { + return (InsertResult::Fit(handle.forget_node_type()), val_ptr); + } + InsertResult::Split(split) => split, + }, + Err(root) => { + return (InsertResult::Split(SplitResult { left: root, ..split }), val_ptr); + } + }; } } } @@ -980,14 +1037,23 @@ impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marke impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> { pub fn into_kv(self) -> (&'a K, &'a V) { - unsafe { - let (keys, vals) = self.node.into_slices(); - (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx)) - } + let keys = self.node.into_key_slice(); + let vals = self.node.into_val_slice(); + unsafe { (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx)) } } } impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> { + pub fn into_key_mut(self) -> &'a mut K { + let keys = self.node.into_key_slice_mut(); + unsafe { keys.get_unchecked_mut(self.idx) } + } + + pub fn into_val_mut(self) -> &'a mut V { + let vals = self.node.into_val_slice_mut(); + unsafe { vals.get_unchecked_mut(self.idx) } + } + pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) { unsafe { let (keys, vals) = self.node.into_slices_mut(); @@ -1005,18 +1071,11 @@ impl<'a, K, V, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker } } -impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> { - /// Splits the underlying node into three parts: - /// - /// - The node is truncated to only contain the key/value pairs to the right of - /// this handle. - /// - The key and value pointed to by this handle and extracted. - /// - All the key/value pairs to the right of this handle are put into a newly - /// allocated node. - pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) { +impl<'a, K, V, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> { + /// Helps implementations of `split` for a particular `NodeType`, + /// by taking care of leaf data. + fn leafy_split(&mut self, new_node: &mut LeafNode<K, V>) -> (K, V, usize) { unsafe { - let mut new_node = Box::new(LeafNode::new()); - let k = ptr::read(self.node.keys().get_unchecked(self.idx)); let v = ptr::read(self.node.vals().get_unchecked(self.idx)); @@ -1035,21 +1094,39 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> (*self.node.as_leaf_mut()).len = self.idx as u16; new_node.len = new_len as u16; + (k, v, new_len) + } + } +} + +impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> { + /// Splits the underlying node into three parts: + /// + /// - The node is truncated to only contain the key/value pairs to the right of + /// this handle. + /// - The key and value pointed to by this handle and extracted. + /// - All the key/value pairs to the right of this handle are put into a newly + /// allocated node. + pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) { + unsafe { + let mut new_node = Box::new(LeafNode::new()); + + let (k, v, _) = self.leafy_split(&mut new_node); (self.node, k, v, Root { node: BoxedNode::from_leaf(new_node), height: 0 }) } } /// Removes the key/value pair pointed to by this handle and returns it, along with the edge - /// between the now adjacent key/value pairs (if any) to the left and right of this handle. + /// that the key/value pair collapsed into. pub fn remove( mut self, - ) -> (Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, K, V) { + ) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) { unsafe { let k = slice_remove(self.node.keys_mut(), self.idx); let v = slice_remove(self.node.vals_mut(), self.idx); (*self.node.as_leaf_mut()).len -= 1; - (self.left_edge(), k, v) + ((k, v), self.left_edge()) } } } @@ -1066,35 +1143,19 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: unsafe { let mut new_node = Box::new(InternalNode::new()); - let k = ptr::read(self.node.keys().get_unchecked(self.idx)); - let v = ptr::read(self.node.vals().get_unchecked(self.idx)); - + let (k, v, new_len) = self.leafy_split(&mut new_node.data); let height = self.node.height; - let new_len = self.node.len() - self.idx - 1; ptr::copy_nonoverlapping( - self.node.keys().as_ptr().add(self.idx + 1), - new_node.data.keys.as_mut_ptr() as *mut K, - new_len, - ); - ptr::copy_nonoverlapping( - self.node.vals().as_ptr().add(self.idx + 1), - new_node.data.vals.as_mut_ptr() as *mut V, - new_len, - ); - ptr::copy_nonoverlapping( self.node.as_internal().edges.as_ptr().add(self.idx + 1), new_node.edges.as_mut_ptr(), new_len + 1, ); - (*self.node.as_leaf_mut()).len = self.idx as u16; - new_node.data.len = new_len as u16; - let mut new_root = Root { node: BoxedNode::from_internal(new_node), height }; for i in 0..(new_len + 1) { - Handle::new_edge(new_root.as_mut().cast_unchecked(), i).correct_parent_link(); + Handle::new_edge(new_root.node_as_mut().cast_unchecked(), i).correct_parent_link(); } (self.node, k, v, new_root) @@ -1115,7 +1176,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: /// to by this handle, and the node immediately to the right of this handle into one new /// child of the underlying node, returning an edge referencing that new child. /// - /// Assumes that this edge `.can_merge()`. + /// Panics unless this edge `.can_merge()`. pub fn merge( mut self, ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> { @@ -1123,10 +1184,9 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: let self2 = unsafe { ptr::read(&self) }; let mut left_node = self1.left_edge().descend(); let left_len = left_node.len(); - let mut right_node = self2.right_edge().descend(); + let right_node = self2.right_edge().descend(); let right_len = right_node.len(); - // necessary for correctness, but in a private module assert!(left_len + right_len < CAPACITY); unsafe { @@ -1157,28 +1217,25 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: (*left_node.as_leaf_mut()).len += right_len as u16 + 1; - let layout = if self.node.height > 1 { + if self.node.height > 1 { + // SAFETY: the height of the nodes being merged is one below the height + // of the node of this edge, thus above zero, so they are internal. + let mut left_node = left_node.cast_unchecked(); + let right_node = right_node.cast_unchecked(); ptr::copy_nonoverlapping( - right_node.cast_unchecked().as_internal().edges.as_ptr(), - left_node - .cast_unchecked() - .as_internal_mut() - .edges - .as_mut_ptr() - .add(left_len + 1), + right_node.reborrow().as_internal().edges.as_ptr(), + left_node.reborrow_mut().as_internal_mut().edges.as_mut_ptr().add(left_len + 1), right_len + 1, ); for i in left_len + 1..left_len + right_len + 2 { - Handle::new_edge(left_node.cast_unchecked().reborrow_mut(), i) - .correct_parent_link(); + Handle::new_edge(left_node.reborrow_mut(), i).correct_parent_link(); } - Layout::new::<InternalNode<K, V>>() + Global.dealloc(right_node.node.cast(), Layout::new::<InternalNode<K, V>>()); } else { - Layout::new::<LeafNode<K, V>>() - }; - Global.dealloc(right_node.node.cast(), layout); + Global.dealloc(right_node.node.cast(), Layout::new::<LeafNode<K, V>>()); + } Handle::new_edge(self.node, self.idx) } @@ -1191,8 +1248,8 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: unsafe { let (k, v, edge) = self.reborrow_mut().left_edge().descend().pop(); - let k = mem::replace(self.reborrow_mut().into_kv_mut().0, k); - let v = mem::replace(self.reborrow_mut().into_kv_mut().1, v); + let k = mem::replace(self.kv_mut().0, k); + let v = mem::replace(self.kv_mut().1, v); match self.reborrow_mut().right_edge().descend().force() { ForceResult::Leaf(mut leaf) => leaf.push_front(k, v), @@ -1208,8 +1265,8 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: unsafe { let (k, v, edge) = self.reborrow_mut().right_edge().descend().pop_front(); - let k = mem::replace(self.reborrow_mut().into_kv_mut().0, k); - let v = mem::replace(self.reborrow_mut().into_kv_mut().1, v); + let k = mem::replace(self.kv_mut().0, k); + let v = mem::replace(self.kv_mut().1, v); match self.reborrow_mut().left_edge().descend().force() { ForceResult::Leaf(mut leaf) => leaf.push(k, v), @@ -1237,7 +1294,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); let parent_kv = { - let kv = self.reborrow_mut().into_kv_mut(); + let kv = self.kv_mut(); (kv.0 as *mut K, kv.1 as *mut V) }; @@ -1294,7 +1351,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker:: let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); let parent_kv = { - let kv = self.reborrow_mut().into_kv_mut(); + let kv = self.kv_mut(); (kv.0 as *mut K, kv.1 as *mut V) }; @@ -1362,6 +1419,20 @@ unsafe fn move_edges<K, V>( } } +impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> { + /// Removes any static information asserting that this node is a `Leaf` node. + pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { + NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData } + } +} + +impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> { + /// Removes any static information asserting that this node is an `Internal` node. + pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { + NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData } + } +} + impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> { pub fn forget_node_type( self, @@ -1386,6 +1457,14 @@ impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::K } } +impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV> { + pub fn forget_node_type( + self, + ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> { + unsafe { Handle::new_kv(self.node.forget_type(), self.idx) } + } +} + impl<BorrowType, K, V, HandleType> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType> { @@ -1452,9 +1531,21 @@ pub enum ForceResult<Leaf, Internal> { Internal(Internal), } +/// Result of insertion, when a node needed to expand beyond its capacity. +/// Does not distinguish between `Leaf` and `Internal` because `Root` doesn't. +pub struct SplitResult<'a, K, V> { + // Altered node in existing tree with elements and edges that belong to the left of `k`. + pub left: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, + // Some key and value split off, to be inserted elsewhere. + pub k: K, + pub v: V, + // Owned, unattached, new node with elements and edges that belong to the right of `k`. + pub right: Root<K, V>, +} + pub enum InsertResult<'a, K, V, Type> { Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>), - Split(NodeRef<marker::Mut<'a>, K, V, Type>, K, V, Root<K, V>), + Split(SplitResult<'a, K, V>), } pub mod marker { @@ -1486,3 +1577,6 @@ unsafe fn slice_remove<T>(slice: &mut [T], idx: usize) -> T { ret } } + +#[cfg(test)] +mod tests; diff --git a/library/alloc/src/collections/btree/node/tests.rs b/library/alloc/src/collections/btree/node/tests.rs new file mode 100644 index 00000000000..e2416974ddc --- /dev/null +++ b/library/alloc/src/collections/btree/node/tests.rs @@ -0,0 +1,25 @@ +use super::*; + +#[test] +fn test_splitpoint() { + for idx in 0..=CAPACITY { + let (middle_kv_idx, insertion) = splitpoint(idx); + + // Simulate performing the split: + let mut left_len = middle_kv_idx; + let mut right_len = CAPACITY - middle_kv_idx - 1; + match insertion { + InsertionPlace::Left(edge_idx) => { + assert!(edge_idx <= left_len); + left_len += 1; + } + InsertionPlace::Right(edge_idx) => { + assert!(edge_idx <= right_len); + right_len += 1; + } + } + assert!(left_len >= MIN_LEN); + assert!(right_len >= MIN_LEN); + assert!(left_len + right_len == CAPACITY); + } +} diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs index 35f4ef1d9b4..a559e87e4e2 100644 --- a/library/alloc/src/collections/btree/set.rs +++ b/library/alloc/src/collections/btree/set.rs @@ -1572,3 +1572,6 @@ impl<'a, T: Ord> Iterator for Union<'a, T> { #[stable(feature = "fused", since = "1.26.0")] impl<T: Ord> FusedIterator for Union<'_, T> {} + +#[cfg(test)] +mod tests; diff --git a/library/alloc/src/collections/btree/set/tests.rs b/library/alloc/src/collections/btree/set/tests.rs new file mode 100644 index 00000000000..f4e957e22fe --- /dev/null +++ b/library/alloc/src/collections/btree/set/tests.rs @@ -0,0 +1,649 @@ +use crate::collections::BTreeSet; +use crate::vec::Vec; +use std::iter::FromIterator; +use std::panic::{catch_unwind, AssertUnwindSafe}; +use std::sync::atomic::{AtomicU32, Ordering}; + +use super::super::DeterministicRng; + +#[test] +fn test_clone_eq() { + let mut m = BTreeSet::new(); + + m.insert(1); + m.insert(2); + + assert_eq!(m.clone(), m); +} + +#[test] +fn test_iter_min_max() { + let mut a = BTreeSet::new(); + assert_eq!(a.iter().min(), None); + assert_eq!(a.iter().max(), None); + assert_eq!(a.range(..).min(), None); + assert_eq!(a.range(..).max(), None); + assert_eq!(a.difference(&BTreeSet::new()).min(), None); + assert_eq!(a.difference(&BTreeSet::new()).max(), None); + assert_eq!(a.intersection(&a).min(), None); + assert_eq!(a.intersection(&a).max(), None); + assert_eq!(a.symmetric_difference(&BTreeSet::new()).min(), None); + assert_eq!(a.symmetric_difference(&BTreeSet::new()).max(), None); + assert_eq!(a.union(&a).min(), None); + assert_eq!(a.union(&a).max(), None); + a.insert(1); + a.insert(2); + assert_eq!(a.iter().min(), Some(&1)); + assert_eq!(a.iter().max(), Some(&2)); + assert_eq!(a.range(..).min(), Some(&1)); + assert_eq!(a.range(..).max(), Some(&2)); + assert_eq!(a.difference(&BTreeSet::new()).min(), Some(&1)); + assert_eq!(a.difference(&BTreeSet::new()).max(), Some(&2)); + assert_eq!(a.intersection(&a).min(), Some(&1)); + assert_eq!(a.intersection(&a).max(), Some(&2)); + assert_eq!(a.symmetric_difference(&BTreeSet::new()).min(), Some(&1)); + assert_eq!(a.symmetric_difference(&BTreeSet::new()).max(), Some(&2)); + assert_eq!(a.union(&a).min(), Some(&1)); + assert_eq!(a.union(&a).max(), Some(&2)); +} + +fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F) +where + F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut dyn FnMut(&i32) -> bool) -> bool, +{ + let mut set_a = BTreeSet::new(); + let mut set_b = BTreeSet::new(); + + for x in a { + assert!(set_a.insert(*x)) + } + for y in b { + assert!(set_b.insert(*y)) + } + + let mut i = 0; + f(&set_a, &set_b, &mut |&x| { + if i < expected.len() { + assert_eq!(x, expected[i]); + } + i += 1; + true + }); + assert_eq!(i, expected.len()); +} + +#[test] +fn test_intersection() { + fn check_intersection(a: &[i32], b: &[i32], expected: &[i32]) { + check(a, b, expected, |x, y, f| x.intersection(y).all(f)) + } + + check_intersection(&[], &[], &[]); + check_intersection(&[1, 2, 3], &[], &[]); + check_intersection(&[], &[1, 2, 3], &[]); + check_intersection(&[2], &[1, 2, 3], &[2]); + check_intersection(&[1, 2, 3], &[2], &[2]); + check_intersection(&[11, 1, 3, 77, 103, 5, -5], &[2, 11, 77, -9, -42, 5, 3], &[3, 5, 11, 77]); + + if cfg!(miri) { + // Miri is too slow + return; + } + + let large = (0..100).collect::<Vec<_>>(); + check_intersection(&[], &large, &[]); + check_intersection(&large, &[], &[]); + check_intersection(&[-1], &large, &[]); + check_intersection(&large, &[-1], &[]); + check_intersection(&[0], &large, &[0]); + check_intersection(&large, &[0], &[0]); + check_intersection(&[99], &large, &[99]); + check_intersection(&large, &[99], &[99]); + check_intersection(&[100], &large, &[]); + check_intersection(&large, &[100], &[]); + check_intersection(&[11, 5000, 1, 3, 77, 8924], &large, &[1, 3, 11, 77]); +} + +#[test] +fn test_intersection_size_hint() { + let x: BTreeSet<i32> = [3, 4].iter().copied().collect(); + let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect(); + let mut iter = x.intersection(&y); + assert_eq!(iter.size_hint(), (1, Some(1))); + assert_eq!(iter.next(), Some(&3)); + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + + iter = y.intersection(&y); + assert_eq!(iter.size_hint(), (0, Some(3))); + assert_eq!(iter.next(), Some(&1)); + assert_eq!(iter.size_hint(), (0, Some(2))); +} + +#[test] +fn test_difference() { + fn check_difference(a: &[i32], b: &[i32], expected: &[i32]) { + check(a, b, expected, |x, y, f| x.difference(y).all(f)) + } + + check_difference(&[], &[], &[]); + check_difference(&[1, 12], &[], &[1, 12]); + check_difference(&[], &[1, 2, 3, 9], &[]); + check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]); + check_difference(&[1, 3, 5, 9, 11], &[3, 6, 9], &[1, 5, 11]); + check_difference(&[1, 3, 5, 9, 11], &[0, 1], &[3, 5, 9, 11]); + check_difference(&[1, 3, 5, 9, 11], &[11, 12], &[1, 3, 5, 9]); + check_difference( + &[-5, 11, 22, 33, 40, 42], + &[-12, -5, 14, 23, 34, 38, 39, 50], + &[11, 22, 33, 40, 42], + ); + + if cfg!(miri) { + // Miri is too slow + return; + } + + let large = (0..100).collect::<Vec<_>>(); + check_difference(&[], &large, &[]); + check_difference(&[-1], &large, &[-1]); + check_difference(&[0], &large, &[]); + check_difference(&[99], &large, &[]); + check_difference(&[100], &large, &[100]); + check_difference(&[11, 5000, 1, 3, 77, 8924], &large, &[5000, 8924]); + check_difference(&large, &[], &large); + check_difference(&large, &[-1], &large); + check_difference(&large, &[100], &large); +} + +#[test] +fn test_difference_size_hint() { + let s246: BTreeSet<i32> = [2, 4, 6].iter().copied().collect(); + let s23456: BTreeSet<i32> = (2..=6).collect(); + let mut iter = s246.difference(&s23456); + assert_eq!(iter.size_hint(), (0, Some(3))); + assert_eq!(iter.next(), None); + + let s12345: BTreeSet<i32> = (1..=5).collect(); + iter = s246.difference(&s12345); + assert_eq!(iter.size_hint(), (0, Some(3))); + assert_eq!(iter.next(), Some(&6)); + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + + let s34567: BTreeSet<i32> = (3..=7).collect(); + iter = s246.difference(&s34567); + assert_eq!(iter.size_hint(), (0, Some(3))); + assert_eq!(iter.next(), Some(&2)); + assert_eq!(iter.size_hint(), (0, Some(2))); + assert_eq!(iter.next(), None); + + let s1: BTreeSet<i32> = (-9..=1).collect(); + iter = s246.difference(&s1); + assert_eq!(iter.size_hint(), (3, Some(3))); + + let s2: BTreeSet<i32> = (-9..=2).collect(); + iter = s246.difference(&s2); + assert_eq!(iter.size_hint(), (2, Some(2))); + assert_eq!(iter.next(), Some(&4)); + assert_eq!(iter.size_hint(), (1, Some(1))); + + let s23: BTreeSet<i32> = (2..=3).collect(); + iter = s246.difference(&s23); + assert_eq!(iter.size_hint(), (1, Some(3))); + assert_eq!(iter.next(), Some(&4)); + assert_eq!(iter.size_hint(), (1, Some(1))); + + let s4: BTreeSet<i32> = (4..=4).collect(); + iter = s246.difference(&s4); + assert_eq!(iter.size_hint(), (2, Some(3))); + assert_eq!(iter.next(), Some(&2)); + assert_eq!(iter.size_hint(), (1, Some(2))); + assert_eq!(iter.next(), Some(&6)); + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + + let s56: BTreeSet<i32> = (5..=6).collect(); + iter = s246.difference(&s56); + assert_eq!(iter.size_hint(), (1, Some(3))); + assert_eq!(iter.next(), Some(&2)); + assert_eq!(iter.size_hint(), (0, Some(2))); + + let s6: BTreeSet<i32> = (6..=19).collect(); + iter = s246.difference(&s6); + assert_eq!(iter.size_hint(), (2, Some(2))); + assert_eq!(iter.next(), Some(&2)); + assert_eq!(iter.size_hint(), (1, Some(1))); + + let s7: BTreeSet<i32> = (7..=19).collect(); + iter = s246.difference(&s7); + assert_eq!(iter.size_hint(), (3, Some(3))); +} + +#[test] +fn test_symmetric_difference() { + fn check_symmetric_difference(a: &[i32], b: &[i32], expected: &[i32]) { + check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f)) + } + + check_symmetric_difference(&[], &[], &[]); + check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]); + check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]); + check_symmetric_difference(&[1, 3, 5, 9, 11], &[-2, 3, 9, 14, 22], &[-2, 1, 5, 11, 14, 22]); +} + +#[test] +fn test_symmetric_difference_size_hint() { + let x: BTreeSet<i32> = [2, 4].iter().copied().collect(); + let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect(); + let mut iter = x.symmetric_difference(&y); + assert_eq!(iter.size_hint(), (0, Some(5))); + assert_eq!(iter.next(), Some(&1)); + assert_eq!(iter.size_hint(), (0, Some(4))); + assert_eq!(iter.next(), Some(&3)); + assert_eq!(iter.size_hint(), (0, Some(1))); +} + +#[test] +fn test_union() { + fn check_union(a: &[i32], b: &[i32], expected: &[i32]) { + check(a, b, expected, |x, y, f| x.union(y).all(f)) + } + + check_union(&[], &[], &[]); + check_union(&[1, 2, 3], &[2], &[1, 2, 3]); + check_union(&[2], &[1, 2, 3], &[1, 2, 3]); + check_union( + &[1, 3, 5, 9, 11, 16, 19, 24], + &[-2, 1, 5, 9, 13, 19], + &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24], + ); +} + +#[test] +fn test_union_size_hint() { + let x: BTreeSet<i32> = [2, 4].iter().copied().collect(); + let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect(); + let mut iter = x.union(&y); + assert_eq!(iter.size_hint(), (3, Some(5))); + assert_eq!(iter.next(), Some(&1)); + assert_eq!(iter.size_hint(), (2, Some(4))); + assert_eq!(iter.next(), Some(&2)); + assert_eq!(iter.size_hint(), (1, Some(2))); +} + +#[test] +// Only tests the simple function definition with respect to intersection +fn test_is_disjoint() { + let one = [1].iter().collect::<BTreeSet<_>>(); + let two = [2].iter().collect::<BTreeSet<_>>(); + assert!(one.is_disjoint(&two)); +} + +#[test] +// Also implicitly tests the trivial function definition of is_superset +fn test_is_subset() { + fn is_subset(a: &[i32], b: &[i32]) -> bool { + let set_a = a.iter().collect::<BTreeSet<_>>(); + let set_b = b.iter().collect::<BTreeSet<_>>(); + set_a.is_subset(&set_b) + } + + assert_eq!(is_subset(&[], &[]), true); + assert_eq!(is_subset(&[], &[1, 2]), true); + assert_eq!(is_subset(&[0], &[1, 2]), false); + assert_eq!(is_subset(&[1], &[1, 2]), true); + assert_eq!(is_subset(&[2], &[1, 2]), true); + assert_eq!(is_subset(&[3], &[1, 2]), false); + assert_eq!(is_subset(&[1, 2], &[1]), false); + assert_eq!(is_subset(&[1, 2], &[1, 2]), true); + assert_eq!(is_subset(&[1, 2], &[2, 3]), false); + assert_eq!( + is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 33, 34, 38, 39, 40, 42]), + true + ); + assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 34, 38]), false); + + if cfg!(miri) { + // Miri is too slow + return; + } + + let large = (0..100).collect::<Vec<_>>(); + assert_eq!(is_subset(&[], &large), true); + assert_eq!(is_subset(&large, &[]), false); + assert_eq!(is_subset(&[-1], &large), false); + assert_eq!(is_subset(&[0], &large), true); + assert_eq!(is_subset(&[1, 2], &large), true); + assert_eq!(is_subset(&[99, 100], &large), false); +} + +#[test] +fn test_drain_filter() { + let mut x: BTreeSet<_> = [1].iter().copied().collect(); + let mut y: BTreeSet<_> = [1].iter().copied().collect(); + + x.drain_filter(|_| true); + y.drain_filter(|_| false); + assert_eq!(x.len(), 0); + assert_eq!(y.len(), 1); +} + +#[test] +fn test_drain_filter_drop_panic_leak() { + static PREDS: AtomicU32 = AtomicU32::new(0); + static DROPS: AtomicU32 = AtomicU32::new(0); + + #[derive(PartialEq, Eq, PartialOrd, Ord)] + struct D(i32); + impl Drop for D { + fn drop(&mut self) { + if DROPS.fetch_add(1, Ordering::SeqCst) == 1 { + panic!("panic in `drop`"); + } + } + } + + let mut set = BTreeSet::new(); + set.insert(D(0)); + set.insert(D(4)); + set.insert(D(8)); + + catch_unwind(move || { + drop(set.drain_filter(|d| { + PREDS.fetch_add(1u32 << d.0, Ordering::SeqCst); + true + })) + }) + .ok(); + + assert_eq!(PREDS.load(Ordering::SeqCst), 0x011); + assert_eq!(DROPS.load(Ordering::SeqCst), 3); +} + +#[test] +fn test_drain_filter_pred_panic_leak() { + static PREDS: AtomicU32 = AtomicU32::new(0); + static DROPS: AtomicU32 = AtomicU32::new(0); + + #[derive(PartialEq, Eq, PartialOrd, Ord)] + struct D(i32); + impl Drop for D { + fn drop(&mut self) { + DROPS.fetch_add(1, Ordering::SeqCst); + } + } + + let mut set = BTreeSet::new(); + set.insert(D(0)); + set.insert(D(4)); + set.insert(D(8)); + + catch_unwind(AssertUnwindSafe(|| { + drop(set.drain_filter(|d| { + PREDS.fetch_add(1u32 << d.0, Ordering::SeqCst); + match d.0 { + 0 => true, + _ => panic!(), + } + })) + })) + .ok(); + + assert_eq!(PREDS.load(Ordering::SeqCst), 0x011); + assert_eq!(DROPS.load(Ordering::SeqCst), 1); + assert_eq!(set.len(), 2); + assert_eq!(set.first().unwrap().0, 4); + assert_eq!(set.last().unwrap().0, 8); +} + +#[test] +fn test_clear() { + let mut x = BTreeSet::new(); + x.insert(1); + + x.clear(); + assert!(x.is_empty()); +} + +#[test] +fn test_zip() { + let mut x = BTreeSet::new(); + x.insert(5); + x.insert(12); + x.insert(11); + + let mut y = BTreeSet::new(); + y.insert("foo"); + y.insert("bar"); + + let x = x; + let y = y; + let mut z = x.iter().zip(&y); + + assert_eq!(z.next().unwrap(), (&5, &("bar"))); + assert_eq!(z.next().unwrap(), (&11, &("foo"))); + assert!(z.next().is_none()); +} + +#[test] +fn test_from_iter() { + let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9]; + + let set: BTreeSet<_> = xs.iter().cloned().collect(); + + for x in &xs { + assert!(set.contains(x)); + } +} + +#[test] +fn test_show() { + let mut set = BTreeSet::new(); + let empty = BTreeSet::<i32>::new(); + + set.insert(1); + set.insert(2); + + let set_str = format!("{:?}", set); + + assert_eq!(set_str, "{1, 2}"); + assert_eq!(format!("{:?}", empty), "{}"); +} + +#[test] +fn test_extend_ref() { + let mut a = BTreeSet::new(); + a.insert(1); + + a.extend(&[2, 3, 4]); + + assert_eq!(a.len(), 4); + assert!(a.contains(&1)); + assert!(a.contains(&2)); + assert!(a.contains(&3)); + assert!(a.contains(&4)); + + let mut b = BTreeSet::new(); + b.insert(5); + b.insert(6); + + a.extend(&b); + + assert_eq!(a.len(), 6); + assert!(a.contains(&1)); + assert!(a.contains(&2)); + assert!(a.contains(&3)); + assert!(a.contains(&4)); + assert!(a.contains(&5)); + assert!(a.contains(&6)); +} + +#[test] +fn test_recovery() { + use std::cmp::Ordering; + + #[derive(Debug)] + struct Foo(&'static str, i32); + + impl PartialEq for Foo { + fn eq(&self, other: &Self) -> bool { + self.0 == other.0 + } + } + + impl Eq for Foo {} + + impl PartialOrd for Foo { + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + self.0.partial_cmp(&other.0) + } + } + + impl Ord for Foo { + fn cmp(&self, other: &Self) -> Ordering { + self.0.cmp(&other.0) + } + } + + let mut s = BTreeSet::new(); + assert_eq!(s.replace(Foo("a", 1)), None); + assert_eq!(s.len(), 1); + assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1))); + assert_eq!(s.len(), 1); + + { + let mut it = s.iter(); + assert_eq!(it.next(), Some(&Foo("a", 2))); + assert_eq!(it.next(), None); + } + + assert_eq!(s.get(&Foo("a", 1)), Some(&Foo("a", 2))); + assert_eq!(s.take(&Foo("a", 1)), Some(Foo("a", 2))); + assert_eq!(s.len(), 0); + + assert_eq!(s.get(&Foo("a", 1)), None); + assert_eq!(s.take(&Foo("a", 1)), None); + + assert_eq!(s.iter().next(), None); +} + +#[test] +#[allow(dead_code)] +fn test_variance() { + use std::collections::btree_set::{IntoIter, Iter, Range}; + + fn set<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> { + v + } + fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> { + v + } + fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> { + v + } + fn range<'a, 'new>(v: Range<'a, &'static str>) -> Range<'a, &'new str> { + v + } +} + +#[test] +fn test_append() { + let mut a = BTreeSet::new(); + a.insert(1); + a.insert(2); + a.insert(3); + + let mut b = BTreeSet::new(); + b.insert(3); + b.insert(4); + b.insert(5); + + a.append(&mut b); + + assert_eq!(a.len(), 5); + assert_eq!(b.len(), 0); + + assert_eq!(a.contains(&1), true); + assert_eq!(a.contains(&2), true); + assert_eq!(a.contains(&3), true); + assert_eq!(a.contains(&4), true); + assert_eq!(a.contains(&5), true); +} + +#[test] +fn test_first_last() { + let mut a = BTreeSet::new(); + assert_eq!(a.first(), None); + assert_eq!(a.last(), None); + a.insert(1); + assert_eq!(a.first(), Some(&1)); + assert_eq!(a.last(), Some(&1)); + a.insert(2); + assert_eq!(a.first(), Some(&1)); + assert_eq!(a.last(), Some(&2)); + for i in 3..=12 { + a.insert(i); + } + assert_eq!(a.first(), Some(&1)); + assert_eq!(a.last(), Some(&12)); + assert_eq!(a.pop_first(), Some(1)); + assert_eq!(a.pop_last(), Some(12)); + assert_eq!(a.pop_first(), Some(2)); + assert_eq!(a.pop_last(), Some(11)); + assert_eq!(a.pop_first(), Some(3)); + assert_eq!(a.pop_last(), Some(10)); + assert_eq!(a.pop_first(), Some(4)); + assert_eq!(a.pop_first(), Some(5)); + assert_eq!(a.pop_first(), Some(6)); + assert_eq!(a.pop_first(), Some(7)); + assert_eq!(a.pop_first(), Some(8)); + assert_eq!(a.clone().pop_last(), Some(9)); + assert_eq!(a.pop_first(), Some(9)); + assert_eq!(a.pop_first(), None); + assert_eq!(a.pop_last(), None); +} + +fn rand_data(len: usize) -> Vec<u32> { + let mut rng = DeterministicRng::new(); + Vec::from_iter((0..len).map(|_| rng.next())) +} + +#[test] +fn test_split_off_empty_right() { + let mut data = rand_data(173); + + let mut set = BTreeSet::from_iter(data.clone()); + let right = set.split_off(&(data.iter().max().unwrap() + 1)); + + data.sort(); + assert!(set.into_iter().eq(data)); + assert!(right.into_iter().eq(None)); +} + +#[test] +fn test_split_off_empty_left() { + let mut data = rand_data(314); + + let mut set = BTreeSet::from_iter(data.clone()); + let right = set.split_off(data.iter().min().unwrap()); + + data.sort(); + assert!(set.into_iter().eq(None)); + assert!(right.into_iter().eq(data)); +} + +#[test] +fn test_split_off_large_random_sorted() { + // Miri is too slow + let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) }; + // special case with maximum height. + data.sort(); + + let mut set = BTreeSet::from_iter(data.clone()); + let key = data[data.len() / 2]; + let right = set.split_off(&key); + + assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key))); + assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key))); +} diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs index 1f875f6c521..5390b57a1d9 100644 --- a/library/alloc/src/collections/linked_list.rs +++ b/library/alloc/src/collections/linked_list.rs @@ -7,8 +7,8 @@ //! array-based containers are generally faster, //! more memory efficient, and make better use of CPU cache. //! -//! [`Vec`]: ../../vec/struct.Vec.html -//! [`VecDeque`]: ../vec_deque/struct.VecDeque.html +//! [`Vec`]: crate::vec::Vec +//! [`VecDeque`]: super::vec_deque::VecDeque #![stable(feature = "rust1", since = "1.0.0")] @@ -50,11 +50,8 @@ struct Node<T> { /// An iterator over the elements of a `LinkedList`. /// -/// This `struct` is created by the [`iter`] method on [`LinkedList`]. See its +/// This `struct` is created by [`LinkedList::iter()`]. See its /// documentation for more. -/// -/// [`iter`]: struct.LinkedList.html#method.iter -/// [`LinkedList`]: struct.LinkedList.html #[stable(feature = "rust1", since = "1.0.0")] pub struct Iter<'a, T: 'a> { head: Option<NonNull<Node<T>>>, @@ -80,11 +77,8 @@ impl<T> Clone for Iter<'_, T> { /// A mutable iterator over the elements of a `LinkedList`. /// -/// This `struct` is created by the [`iter_mut`] method on [`LinkedList`]. See its +/// This `struct` is created by [`LinkedList::iter_mut()`]. See its /// documentation for more. -/// -/// [`iter_mut`]: struct.LinkedList.html#method.iter_mut -/// [`LinkedList`]: struct.LinkedList.html #[stable(feature = "rust1", since = "1.0.0")] pub struct IterMut<'a, T: 'a> { // We do *not* exclusively own the entire list here, references to node's `element` @@ -109,7 +103,6 @@ impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> { /// (provided by the `IntoIterator` trait). See its documentation for more. /// /// [`into_iter`]: struct.LinkedList.html#method.into_iter -/// [`LinkedList`]: struct.LinkedList.html #[derive(Clone)] #[stable(feature = "rust1", since = "1.0.0")] pub struct IntoIter<T> { @@ -1110,32 +1103,17 @@ impl<T> IterMut<'_, T> { /// Inserts the given element just after the element most recently returned by `.next()`. /// The inserted element does not appear in the iteration. /// - /// # Examples - /// - /// ``` - /// #![feature(linked_list_extras)] - /// - /// use std::collections::LinkedList; - /// - /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect(); - /// - /// { - /// let mut it = list.iter_mut(); - /// assert_eq!(it.next().unwrap(), &1); - /// // insert `2` after `1` - /// it.insert_next(2); - /// } - /// { - /// let vec: Vec<_> = list.into_iter().collect(); - /// assert_eq!(vec, [1, 2, 3, 4]); - /// } - /// ``` + /// This method will be removed soon. #[inline] #[unstable( feature = "linked_list_extras", reason = "this is probably better handled by a cursor type -- we'll see", issue = "27794" )] + #[rustc_deprecated( + reason = "Deprecated in favor of CursorMut methods. This method will be removed soon.", + since = "1.47.0" + )] pub fn insert_next(&mut self, element: T) { match self.head { // `push_back` is okay with aliasing `element` references @@ -1163,27 +1141,17 @@ impl<T> IterMut<'_, T> { /// Provides a reference to the next element, without changing the iterator. /// - /// # Examples - /// - /// ``` - /// #![feature(linked_list_extras)] - /// - /// use std::collections::LinkedList; - /// - /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect(); - /// - /// let mut it = list.iter_mut(); - /// assert_eq!(it.next().unwrap(), &1); - /// assert_eq!(it.peek_next().unwrap(), &2); - /// // We just peeked at 2, so it was not consumed from the iterator. - /// assert_eq!(it.next().unwrap(), &2); - /// ``` + /// This method will be removed soon. #[inline] #[unstable( feature = "linked_list_extras", reason = "this is probably better handled by a cursor type -- we'll see", issue = "27794" )] + #[rustc_deprecated( + reason = "Deprecated in favor of CursorMut methods. This method will be removed soon.", + since = "1.47.0" + )] pub fn peek_next(&mut self) -> Option<&mut T> { if self.len == 0 { None diff --git a/library/alloc/src/collections/linked_list/tests.rs b/library/alloc/src/collections/linked_list/tests.rs index b8c93a28bba..ad643a7bdf1 100644 --- a/library/alloc/src/collections/linked_list/tests.rs +++ b/library/alloc/src/collections/linked_list/tests.rs @@ -154,33 +154,6 @@ fn test_clone_from() { } #[test] -fn test_insert_prev() { - let mut m = list_from(&[0, 2, 4, 6, 8]); - let len = m.len(); - { - let mut it = m.iter_mut(); - it.insert_next(-2); - loop { - match it.next() { - None => break, - Some(elt) => { - it.insert_next(*elt + 1); - match it.peek_next() { - Some(x) => assert_eq!(*x, *elt + 2), - None => assert_eq!(8, *elt), - } - } - } - } - it.insert_next(0); - it.insert_next(1); - } - check_links(&m); - assert_eq!(m.len(), 3 + len * 2); - assert_eq!(m.into_iter().collect::<Vec<_>>(), [-2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]); -} - -#[test] #[cfg_attr(target_os = "emscripten", ignore)] fn test_send() { let n = list_from(&[1, 2, 3]); diff --git a/library/alloc/src/collections/vec_deque/tests.rs b/library/alloc/src/collections/vec_deque/tests.rs index e5edfe02a52..d74f91c752c 100644 --- a/library/alloc/src/collections/vec_deque/tests.rs +++ b/library/alloc/src/collections/vec_deque/tests.rs @@ -107,7 +107,8 @@ fn test_insert() { let cap = tester.capacity(); // len is the length *after* insertion - for len in 1..cap { + let minlen = if cfg!(miri) { cap - 1 } else { 1 }; // Miri is too slow + for len in minlen..cap { // 0, 1, 2, .., len - 1 let expected = (0..).take(len).collect::<VecDeque<_>>(); for tail_pos in 0..cap { @@ -221,7 +222,8 @@ fn test_remove() { let cap = tester.capacity(); // len is the length *after* removal - for len in 0..cap - 1 { + let minlen = if cfg!(miri) { cap - 2 } else { 0 }; // Miri is too slow + for len in minlen..cap - 1 { // 0, 1, 2, .., len - 1 let expected = (0..).take(len).collect::<VecDeque<_>>(); for tail_pos in 0..cap { @@ -251,7 +253,8 @@ fn test_range() { let mut tester: VecDeque<usize> = VecDeque::with_capacity(7); let cap = tester.capacity(); - for len in 0..=cap { + let minlen = if cfg!(miri) { cap - 1 } else { 0 }; // Miri is too slow + for len in minlen..=cap { for tail in 0..=cap { for start in 0..=len { for end in start..=len { @@ -384,7 +387,8 @@ fn test_split_off() { let cap = tester.capacity(); // len is the length *before* splitting - for len in 0..cap { + let minlen = if cfg!(miri) { cap - 1 } else { 0 }; // Miri is too slow + for len in minlen..cap { // index to split at for at in 0..=len { // 0, 1, 2, .., at - 1 (may be empty) @@ -495,8 +499,9 @@ fn test_vec_from_vecdeque() { fn test_clone_from() { let m = vec![1; 8]; let n = vec![2; 12]; - for pfv in 0..8 { - for pfu in 0..8 { + let limit = if cfg!(miri) { 4 } else { 8 }; // Miri is too slow + for pfv in 0..limit { + for pfu in 0..limit { for longer in 0..2 { let (vr, ur) = if longer == 0 { (&m, &n) } else { (&n, &m) }; let mut v = VecDeque::from(vr.clone()); diff --git a/library/alloc/src/fmt.rs b/library/alloc/src/fmt.rs index 26077f3c8d1..a886e17f5a9 100644 --- a/library/alloc/src/fmt.rs +++ b/library/alloc/src/fmt.rs @@ -83,7 +83,7 @@ //! # Formatting Parameters //! //! Each argument being formatted can be transformed by a number of formatting -//! parameters (corresponding to `format_spec` in the syntax above). These +//! parameters (corresponding to `format_spec` in [the syntax](#syntax)). These //! parameters affect the string representation of what's being formatted. //! //! ## Width @@ -239,7 +239,7 @@ //! println!("{}, `{name:>8.*}` has 3 right-aligned characters", "Hello", 3, name="1234.56"); //! ``` //! -//! print two significantly different things: +//! print three significantly different things: //! //! ```text //! Hello, `1234.560` has 3 fractional digits @@ -501,31 +501,23 @@ //! it would internally pass around this structure until it has been determined //! where output should go to. //! -//! [`usize`]: ../../std/primitive.usize.html -//! [`isize`]: ../../std/primitive.isize.html -//! [`i8`]: ../../std/primitive.i8.html -//! [`Display`]: trait.Display.html -//! [`Binary`]: trait.Binary.html -//! [`fmt::Result`]: type.Result.html -//! [`Result`]: ../../std/result/enum.Result.html -//! [`std::fmt::Error`]: struct.Error.html -//! [`Formatter`]: struct.Formatter.html -//! [`write!`]: ../../std/macro.write.html -//! [`Debug`]: trait.Debug.html -//! [`format!`]: ../../std/macro.format.html -//! [`to_string`]: ../../std/string/trait.ToString.html -//! [`writeln!`]: ../../std/macro.writeln.html +//! [`fmt::Result`]: Result +//! [`Result`]: core::result::Result +//! [`std::fmt::Error`]: Error +//! [`write!`]: core::write +//! [`write`]: core::write +//! [`format!`]: crate::format +//! [`to_string`]: crate::string::ToString +//! [`writeln!`]: core::writeln //! [`write_fmt`]: ../../std/io/trait.Write.html#method.write_fmt //! [`std::io::Write`]: ../../std/io/trait.Write.html //! [`print!`]: ../../std/macro.print.html //! [`println!`]: ../../std/macro.println.html //! [`eprint!`]: ../../std/macro.eprint.html //! [`eprintln!`]: ../../std/macro.eprintln.html -//! [`write!`]: ../../std/macro.write.html -//! [`format_args!`]: ../../std/macro.format_args.html -//! [`fmt::Arguments`]: struct.Arguments.html -//! [`write`]: fn.write.html -//! [`format`]: fn.format.html +//! [`format_args!`]: core::format_args +//! [`fmt::Arguments`]: Arguments +//! [`format`]: crate::format #![stable(feature = "rust1", since = "1.0.0")] @@ -576,9 +568,8 @@ use crate::string; /// assert_eq!(s, "Hello, world!"); /// ``` /// -/// [`Arguments`]: struct.Arguments.html -/// [`format_args!`]: ../../std/macro.format_args.html -/// [`format!`]: ../../std/macro.format.html +/// [`format_args!`]: core::format_args +/// [`format!`]: crate::format #[stable(feature = "rust1", since = "1.0.0")] pub fn format(args: Arguments<'_>) -> string::String { let capacity = args.estimated_capacity(); diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs index 90e2d2531c5..755a21934f0 100644 --- a/library/alloc/src/lib.rs +++ b/library/alloc/src/lib.rs @@ -50,11 +50,11 @@ //! The [`alloc`](alloc/index.html) module defines the low-level interface to the //! default global allocator. It is not compatible with the libc allocator API. //! -//! [`Arc`]: sync/index.html -//! [`Box`]: boxed/index.html -//! [`Cell`]: ../core/cell/index.html -//! [`Rc`]: rc/index.html -//! [`RefCell`]: ../core/cell/index.html +//! [`Arc`]: sync +//! [`Box`]: boxed +//! [`Cell`]: core::cell +//! [`Rc`]: rc +//! [`RefCell`]: core::cell #![allow(unused_attributes)] #![stable(feature = "alloc", since = "1.36.0")] @@ -69,17 +69,18 @@ #![warn(deprecated_in_future)] #![warn(missing_docs)] #![warn(missing_debug_implementations)] -#![deny(intra_doc_link_resolution_failure)] // rustdoc is run without -D warnings #![allow(explicit_outlives_requirements)] #![allow(incomplete_features)] #![deny(unsafe_op_in_unsafe_fn)] #![cfg_attr(not(test), feature(generator_trait))] #![cfg_attr(test, feature(test))] #![feature(allocator_api)] +#![feature(array_chunks)] #![feature(allow_internal_unstable)] #![feature(arbitrary_self_types)] #![feature(box_patterns)] #![feature(box_syntax)] +#![feature(btree_drain_filter)] #![feature(cfg_sanitize)] #![feature(cfg_target_has_atomic)] #![feature(coerce_unsized)] @@ -93,6 +94,7 @@ #![feature(container_error_extra)] #![feature(dropck_eyepatch)] #![feature(exact_size_is_empty)] +#![feature(exclusive_range_pattern)] #![feature(extend_one)] #![feature(fmt_internals)] #![feature(fn_traits)] @@ -101,18 +103,22 @@ #![feature(lang_items)] #![feature(layout_for_ptr)] #![feature(libc)] +#![feature(map_first_last)] +#![feature(map_into_keys_values)] #![feature(negative_impls)] #![feature(new_uninit)] #![feature(nll)] +#![feature(nonnull_slice_from_raw_parts)] #![feature(optin_builtin_traits)] #![feature(or_patterns)] #![feature(pattern)] #![feature(ptr_internals)] -#![feature(ptr_offset_from)] #![feature(raw_ref_op)] #![feature(rustc_attrs)] #![feature(receiver_trait)] #![feature(min_specialization)] +#![feature(slice_ptr_get)] +#![feature(slice_ptr_len)] #![feature(staged_api)] #![feature(std_internals)] #![feature(str_internals)] @@ -129,7 +135,6 @@ #![feature(alloc_layout_extra)] #![feature(try_trait)] #![feature(associated_type_bounds)] - // Allow testing this library #[cfg(test)] diff --git a/library/alloc/src/macros.rs b/library/alloc/src/macros.rs index e163a166b49..2f744618d69 100644 --- a/library/alloc/src/macros.rs +++ b/library/alloc/src/macros.rs @@ -29,8 +29,7 @@ /// to the same boxed integer value, not five references pointing to independently /// boxed integers. /// -/// [`Vec`]: ../std/vec/struct.Vec.html -/// [`Clone`]: ../std/clone/trait.Clone.html +/// [`Vec`]: crate::vec::Vec #[cfg(not(test))] #[macro_export] #[stable(feature = "rust1", since = "1.0.0")] @@ -81,11 +80,11 @@ macro_rules! vec { /// To convert a single value to a string, use the [`to_string`] method. This /// will use the [`Display`] formatting trait. /// -/// [fmt]: ../std/fmt/index.html +/// [fmt]: core::fmt /// [`print!`]: ../std/macro.print.html -/// [`write!`]: ../std/macro.write.html -/// [`to_string`]: ../std/string/trait.ToString.html -/// [`Display`]: ../std/fmt/trait.Display.html +/// [`write!`]: core::write +/// [`to_string`]: crate::string::ToString +/// [`Display`]: core::fmt::Display /// /// # Panics /// diff --git a/library/alloc/src/raw_vec.rs b/library/alloc/src/raw_vec.rs index ed81ce71ddf..05382d0b559 100644 --- a/library/alloc/src/raw_vec.rs +++ b/library/alloc/src/raw_vec.rs @@ -1,25 +1,28 @@ #![unstable(feature = "raw_vec_internals", reason = "implementation detail", issue = "none")] #![doc(hidden)] -use core::alloc::{LayoutErr, MemoryBlock}; +use core::alloc::LayoutErr; use core::cmp; +use core::intrinsics; use core::mem::{self, ManuallyDrop, MaybeUninit}; use core::ops::Drop; use core::ptr::{NonNull, Unique}; use core::slice; -use crate::alloc::{ - handle_alloc_error, - AllocInit::{self, *}, - AllocRef, Global, Layout, - ReallocPlacement::{self, *}, -}; +use crate::alloc::{handle_alloc_error, AllocRef, Global, Layout}; use crate::boxed::Box; use crate::collections::TryReserveError::{self, *}; #[cfg(test)] mod tests; +enum AllocInit { + /// The contents of the new memory are uninitialized. + Uninitialized, + /// The new memory is guaranteed to be zeroed. + Zeroed, +} + /// A low-level utility for more ergonomically allocating, reallocating, and deallocating /// a buffer of memory on the heap without having to worry about all the corner cases /// involved. This type is excellent for building your own data structures like Vec and VecDeque. @@ -156,14 +159,14 @@ impl<T, A: AllocRef> RawVec<T, A> { /// allocator for the returned `RawVec`. #[inline] pub fn with_capacity_in(capacity: usize, alloc: A) -> Self { - Self::allocate_in(capacity, Uninitialized, alloc) + Self::allocate_in(capacity, AllocInit::Uninitialized, alloc) } /// Like `with_capacity_zeroed`, but parameterized over the choice /// of allocator for the returned `RawVec`. #[inline] pub fn with_capacity_zeroed_in(capacity: usize, alloc: A) -> Self { - Self::allocate_in(capacity, Zeroed, alloc) + Self::allocate_in(capacity, AllocInit::Zeroed, alloc) } fn allocate_in(capacity: usize, init: AllocInit, mut alloc: A) -> Self { @@ -180,14 +183,18 @@ impl<T, A: AllocRef> RawVec<T, A> { Ok(_) => {} Err(_) => capacity_overflow(), } - let memory = match alloc.alloc(layout, init) { - Ok(memory) => memory, + let result = match init { + AllocInit::Uninitialized => alloc.alloc(layout), + AllocInit::Zeroed => alloc.alloc_zeroed(layout), + }; + let ptr = match result { + Ok(ptr) => ptr, Err(_) => handle_alloc_error(layout), }; Self { - ptr: unsafe { Unique::new_unchecked(memory.ptr.cast().as_ptr()) }, - cap: Self::capacity_from_bytes(memory.size), + ptr: unsafe { Unique::new_unchecked(ptr.cast().as_ptr()) }, + cap: Self::capacity_from_bytes(ptr.len()), alloc, } } @@ -197,13 +204,15 @@ impl<T, A: AllocRef> RawVec<T, A> { /// /// # Safety /// - /// The `ptr` must be allocated (via the given allocator `a`), and with the given `capacity`. + /// The `ptr` must be allocated (via the given allocator `alloc`), and with the given + /// `capacity`. /// The `capacity` cannot exceed `isize::MAX` for sized types. (only a concern on 32-bit /// systems). ZST vectors may have a capacity up to `usize::MAX`. - /// If the `ptr` and `capacity` come from a `RawVec` created via `a`, then this is guaranteed. + /// If the `ptr` and `capacity` come from a `RawVec` created via `alloc`, then this is + /// guaranteed. #[inline] - pub unsafe fn from_raw_parts_in(ptr: *mut T, capacity: usize, a: A) -> Self { - Self { ptr: unsafe { Unique::new_unchecked(ptr) }, cap: capacity, alloc: a } + pub unsafe fn from_raw_parts_in(ptr: *mut T, capacity: usize, alloc: A) -> Self { + Self { ptr: unsafe { Unique::new_unchecked(ptr) }, cap: capacity, alloc } } /// Gets a raw pointer to the start of the allocation. Note that this is @@ -358,7 +367,7 @@ impl<T, A: AllocRef> RawVec<T, A> { /// /// Aborts on OOM. pub fn shrink_to_fit(&mut self, amount: usize) { - match self.shrink(amount, MayMove) { + match self.shrink(amount) { Err(CapacityOverflow) => capacity_overflow(), Err(AllocError { layout, .. }) => handle_alloc_error(layout), Ok(()) => { /* yay */ } @@ -378,9 +387,9 @@ impl<T, A: AllocRef> RawVec<T, A> { excess / mem::size_of::<T>() } - fn set_memory(&mut self, memory: MemoryBlock) { - self.ptr = unsafe { Unique::new_unchecked(memory.ptr.cast().as_ptr()) }; - self.cap = Self::capacity_from_bytes(memory.size); + fn set_ptr(&mut self, ptr: NonNull<[u8]>) { + self.ptr = unsafe { Unique::new_unchecked(ptr.cast().as_ptr()) }; + self.cap = Self::capacity_from_bytes(ptr.len()); } // This method is usually instantiated many times. So we want it to be as @@ -426,8 +435,8 @@ impl<T, A: AllocRef> RawVec<T, A> { let new_layout = Layout::array::<T>(cap); // `finish_grow` is non-generic over `T`. - let memory = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?; - self.set_memory(memory); + let ptr = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?; + self.set_ptr(ptr); Ok(()) } @@ -445,30 +454,25 @@ impl<T, A: AllocRef> RawVec<T, A> { let new_layout = Layout::array::<T>(cap); // `finish_grow` is non-generic over `T`. - let memory = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?; - self.set_memory(memory); + let ptr = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?; + self.set_ptr(ptr); Ok(()) } - fn shrink( - &mut self, - amount: usize, - placement: ReallocPlacement, - ) -> Result<(), TryReserveError> { + fn shrink(&mut self, amount: usize) -> Result<(), TryReserveError> { assert!(amount <= self.capacity(), "Tried to shrink to a larger capacity"); let (ptr, layout) = if let Some(mem) = self.current_memory() { mem } else { return Ok(()) }; let new_size = amount * mem::size_of::<T>(); - let memory = unsafe { - self.alloc.shrink(ptr, layout, new_size, placement).map_err(|_| { - TryReserveError::AllocError { - layout: Layout::from_size_align_unchecked(new_size, layout.align()), - non_exhaustive: (), - } + let ptr = unsafe { + let new_layout = Layout::from_size_align_unchecked(new_size, layout.align()); + self.alloc.shrink(ptr, layout, new_layout).map_err(|_| TryReserveError::AllocError { + layout: new_layout, + non_exhaustive: (), })? }; - self.set_memory(memory); + self.set_ptr(ptr); Ok(()) } } @@ -481,7 +485,7 @@ fn finish_grow<A>( new_layout: Result<Layout, LayoutErr>, current_memory: Option<(NonNull<u8>, Layout)>, alloc: &mut A, -) -> Result<MemoryBlock, TryReserveError> +) -> Result<NonNull<[u8]>, TryReserveError> where A: AllocRef, { @@ -492,13 +496,16 @@ where let memory = if let Some((ptr, old_layout)) = current_memory { debug_assert_eq!(old_layout.align(), new_layout.align()); - unsafe { alloc.grow(ptr, old_layout, new_layout.size(), MayMove, Uninitialized) } + unsafe { + // The allocator checks for alignment equality + intrinsics::assume(old_layout.align() == new_layout.align()); + alloc.grow(ptr, old_layout, new_layout) + } } else { - alloc.alloc(new_layout, Uninitialized) - } - .map_err(|_| AllocError { layout: new_layout, non_exhaustive: () })?; + alloc.alloc(new_layout) + }; - Ok(memory) + memory.map_err(|_| AllocError { layout: new_layout, non_exhaustive: () }) } unsafe impl<#[may_dangle] T, A: AllocRef> Drop for RawVec<T, A> { diff --git a/library/alloc/src/raw_vec/tests.rs b/library/alloc/src/raw_vec/tests.rs index 5408faa079c..cadd913aa6b 100644 --- a/library/alloc/src/raw_vec/tests.rs +++ b/library/alloc/src/raw_vec/tests.rs @@ -20,12 +20,12 @@ fn allocator_param() { fuel: usize, } unsafe impl AllocRef for BoundedAlloc { - fn alloc(&mut self, layout: Layout, init: AllocInit) -> Result<MemoryBlock, AllocErr> { + fn alloc(&mut self, layout: Layout) -> Result<NonNull<[u8]>, AllocErr> { let size = layout.size(); if size > self.fuel { return Err(AllocErr); } - match Global.alloc(layout, init) { + match Global.alloc(layout) { ok @ Ok(_) => { self.fuel -= size; ok diff --git a/library/alloc/src/rc.rs b/library/alloc/src/rc.rs index 96dfc2f4251..1046397f4be 100644 --- a/library/alloc/src/rc.rs +++ b/library/alloc/src/rc.rs @@ -214,18 +214,15 @@ //! } //! ``` //! -//! [`Rc`]: struct.Rc.html -//! [`Weak`]: struct.Weak.html -//! [clone]: ../../std/clone/trait.Clone.html#tymethod.clone -//! [`Cell`]: ../../std/cell/struct.Cell.html -//! [`RefCell`]: ../../std/cell/struct.RefCell.html -//! [send]: ../../std/marker/trait.Send.html +//! [clone]: Clone::clone +//! [`Cell`]: core::cell::Cell +//! [`RefCell`]: core::cell::RefCell +//! [send]: core::marker::Send //! [arc]: ../../std/sync/struct.Arc.html -//! [`Deref`]: ../../std/ops/trait.Deref.html -//! [downgrade]: struct.Rc.html#method.downgrade -//! [upgrade]: struct.Weak.html#method.upgrade -//! [`None`]: ../../std/option/enum.Option.html#variant.None -//! [mutability]: ../../std/cell/index.html#introducing-mutability-inside-of-something-immutable +//! [`Deref`]: core::ops::Deref +//! [downgrade]: Rc::downgrade +//! [upgrade]: Weak::upgrade +//! [mutability]: core::cell#introducing-mutability-inside-of-something-immutable #![stable(feature = "rust1", since = "1.0.0")] @@ -250,7 +247,7 @@ use core::pin::Pin; use core::ptr::{self, NonNull}; use core::slice::from_raw_parts_mut; -use crate::alloc::{box_free, handle_alloc_error, AllocInit, AllocRef, Global, Layout}; +use crate::alloc::{box_free, handle_alloc_error, AllocErr, AllocRef, Global, Layout}; use crate::borrow::{Cow, ToOwned}; use crate::string::String; use crate::vec::Vec; @@ -352,9 +349,11 @@ impl<T> Rc<T> { #[unstable(feature = "new_uninit", issue = "63291")] pub fn new_uninit() -> Rc<mem::MaybeUninit<T>> { unsafe { - Rc::from_ptr(Rc::allocate_for_layout(Layout::new::<T>(), |mem| { - mem as *mut RcBox<mem::MaybeUninit<T>> - })) + Rc::from_ptr(Rc::allocate_for_layout( + Layout::new::<T>(), + |layout| Global.alloc(layout), + |mem| mem as *mut RcBox<mem::MaybeUninit<T>>, + )) } } @@ -381,9 +380,11 @@ impl<T> Rc<T> { #[unstable(feature = "new_uninit", issue = "63291")] pub fn new_zeroed() -> Rc<mem::MaybeUninit<T>> { unsafe { - let mut uninit = Self::new_uninit(); - ptr::write_bytes::<T>(Rc::get_mut_unchecked(&mut uninit).as_mut_ptr(), 0, 1); - uninit + Rc::from_ptr(Rc::allocate_for_layout( + Layout::new::<T>(), + |layout| Global.alloc_zeroed(layout), + |mem| mem as *mut RcBox<mem::MaybeUninit<T>>, + )) } } @@ -396,13 +397,11 @@ impl<T> Rc<T> { /// Returns the inner value, if the `Rc` has exactly one strong reference. /// - /// Otherwise, an [`Err`][result] is returned with the same `Rc` that was + /// Otherwise, an [`Err`] is returned with the same `Rc` that was /// passed in. /// /// This will succeed even if there are outstanding weak references. /// - /// [result]: ../../std/result/enum.Result.html - /// /// # Examples /// /// ``` @@ -465,6 +464,40 @@ impl<T> Rc<[T]> { pub fn new_uninit_slice(len: usize) -> Rc<[mem::MaybeUninit<T>]> { unsafe { Rc::from_ptr(Rc::allocate_for_slice(len)) } } + + /// Constructs a new reference-counted slice with uninitialized contents, with the memory being + /// filled with `0` bytes. + /// + /// See [`MaybeUninit::zeroed`][zeroed] for examples of correct and + /// incorrect usage of this method. + /// + /// # Examples + /// + /// ``` + /// #![feature(new_uninit)] + /// + /// use std::rc::Rc; + /// + /// let values = Rc::<[u32]>::new_zeroed_slice(3); + /// let values = unsafe { values.assume_init() }; + /// + /// assert_eq!(*values, [0, 0, 0]) + /// ``` + /// + /// [zeroed]: ../../std/mem/union.MaybeUninit.html#method.zeroed + #[unstable(feature = "new_uninit", issue = "63291")] + pub fn new_zeroed_slice(len: usize) -> Rc<[mem::MaybeUninit<T>]> { + unsafe { + Rc::from_ptr(Rc::allocate_for_layout( + Layout::array::<T>(len).unwrap(), + |layout| Global.alloc_zeroed(layout), + |mem| { + ptr::slice_from_raw_parts_mut(mem as *mut T, len) + as *mut RcBox<[mem::MaybeUninit<T>]> + }, + )) + } + } } impl<T> Rc<mem::MaybeUninit<T>> { @@ -553,7 +586,7 @@ impl<T: ?Sized> Rc<T> { /// To avoid a memory leak the pointer must be converted back to an `Rc` using /// [`Rc::from_raw`][from_raw]. /// - /// [from_raw]: struct.Rc.html#method.from_raw + /// [from_raw]: Rc::from_raw /// /// # Examples /// @@ -613,8 +646,8 @@ impl<T: ?Sized> Rc<T> { /// This function is unsafe because improper use may lead to memory unsafety, /// even if the returned `Rc<T>` is never accessed. /// - /// [into_raw]: struct.Rc.html#method.into_raw - /// [transmute]: ../../std/mem/fn.transmute.html + /// [into_raw]: Rc::into_raw + /// [transmute]: core::mem::transmute /// /// # Examples /// @@ -645,32 +678,7 @@ impl<T: ?Sized> Rc<T> { unsafe { Self::from_ptr(rc_ptr) } } - /// Consumes the `Rc`, returning the wrapped pointer as `NonNull<T>`. - /// - /// # Examples - /// - /// ``` - /// #![feature(rc_into_raw_non_null)] - /// #![allow(deprecated)] - /// - /// use std::rc::Rc; - /// - /// let x = Rc::new("hello".to_owned()); - /// let ptr = Rc::into_raw_non_null(x); - /// let deref = unsafe { ptr.as_ref() }; - /// assert_eq!(deref, "hello"); - /// ``` - #[unstable(feature = "rc_into_raw_non_null", issue = "47336")] - #[rustc_deprecated(since = "1.44.0", reason = "use `Rc::into_raw` instead")] - #[inline] - pub fn into_raw_non_null(this: Self) -> NonNull<T> { - // safe because Rc guarantees its pointer is non-null - unsafe { NonNull::new_unchecked(Rc::into_raw(this) as *mut _) } - } - - /// Creates a new [`Weak`][weak] pointer to this allocation. - /// - /// [weak]: struct.Weak.html + /// Creates a new [`Weak`] pointer to this allocation. /// /// # Examples /// @@ -689,9 +697,7 @@ impl<T: ?Sized> Rc<T> { Weak { ptr: this.ptr } } - /// Gets the number of [`Weak`][weak] pointers to this allocation. - /// - /// [weak]: struct.Weak.html + /// Gets the number of [`Weak`] pointers to this allocation. /// /// # Examples /// @@ -727,17 +733,15 @@ impl<T: ?Sized> Rc<T> { this.strong() } - /// Returns `true` if there are no other `Rc` or [`Weak`][weak] pointers to + /// Returns `true` if there are no other `Rc` or [`Weak`] pointers to /// this allocation. - /// - /// [weak]: struct.Weak.html #[inline] fn is_unique(this: &Self) -> bool { Rc::weak_count(this) == 0 && Rc::strong_count(this) == 1 } /// Returns a mutable reference into the given `Rc`, if there are - /// no other `Rc` or [`Weak`][weak] pointers to the same allocation. + /// no other `Rc` or [`Weak`] pointers to the same allocation. /// /// Returns [`None`] otherwise, because it is not safe to /// mutate a shared value. @@ -745,10 +749,8 @@ impl<T: ?Sized> Rc<T> { /// See also [`make_mut`][make_mut], which will [`clone`][clone] /// the inner value when there are other pointers. /// - /// [weak]: struct.Weak.html - /// [`None`]: ../../std/option/enum.Option.html#variant.None - /// [make_mut]: struct.Rc.html#method.make_mut - /// [clone]: ../../std/clone/trait.Clone.html#tymethod.clone + /// [make_mut]: Rc::make_mut + /// [clone]: Clone::clone /// /// # Examples /// @@ -773,7 +775,7 @@ impl<T: ?Sized> Rc<T> { /// /// See also [`get_mut`], which is safe and does appropriate checks. /// - /// [`get_mut`]: struct.Rc.html#method.get_mut + /// [`get_mut`]: Rc::get_mut /// /// # Safety /// @@ -819,7 +821,7 @@ impl<T: ?Sized> Rc<T> { /// assert!(!Rc::ptr_eq(&five, &other_five)); /// ``` /// - /// [`ptr::eq`]: ../../std/ptr/fn.eq.html + /// [`ptr::eq`]: core::ptr::eq pub fn ptr_eq(this: &Self, other: &Self) -> bool { this.ptr.as_ptr() == other.ptr.as_ptr() } @@ -837,9 +839,8 @@ impl<T: Clone> Rc<T> { /// /// See also [`get_mut`], which will fail rather than cloning. /// - /// [`Weak`]: struct.Weak.html - /// [`clone`]: ../../std/clone/trait.Clone.html#tymethod.clone - /// [`get_mut`]: struct.Rc.html#method.get_mut + /// [`clone`]: Clone::clone + /// [`get_mut`]: Rc::get_mut /// /// # Examples /// @@ -942,6 +943,7 @@ impl<T: ?Sized> Rc<T> { /// and must return back a (potentially fat)-pointer for the `RcBox<T>`. unsafe fn allocate_for_layout( value_layout: Layout, + allocate: impl FnOnce(Layout) -> Result<NonNull<[u8]>, AllocErr>, mem_to_rcbox: impl FnOnce(*mut u8) -> *mut RcBox<T>, ) -> *mut RcBox<T> { // Calculate layout using the given value layout. @@ -951,12 +953,10 @@ impl<T: ?Sized> Rc<T> { let layout = Layout::new::<RcBox<()>>().extend(value_layout).unwrap().0.pad_to_align(); // Allocate for the layout. - let mem = Global - .alloc(layout, AllocInit::Uninitialized) - .unwrap_or_else(|_| handle_alloc_error(layout)); + let ptr = allocate(layout).unwrap_or_else(|_| handle_alloc_error(layout)); // Initialize the RcBox - let inner = mem_to_rcbox(mem.ptr.as_ptr()); + let inner = mem_to_rcbox(ptr.as_non_null_ptr().as_ptr()); unsafe { debug_assert_eq!(Layout::for_value(&*inner), layout); @@ -971,9 +971,11 @@ impl<T: ?Sized> Rc<T> { unsafe fn allocate_for_ptr(ptr: *const T) -> *mut RcBox<T> { // Allocate for the `RcBox<T>` using the given value. unsafe { - Self::allocate_for_layout(Layout::for_value(&*ptr), |mem| { - set_data_ptr(ptr as *mut T, mem) as *mut RcBox<T> - }) + Self::allocate_for_layout( + Layout::for_value(&*ptr), + |layout| Global.alloc(layout), + |mem| set_data_ptr(ptr as *mut T, mem) as *mut RcBox<T>, + ) } } @@ -1004,9 +1006,11 @@ impl<T> Rc<[T]> { /// Allocates an `RcBox<[T]>` with the given length. unsafe fn allocate_for_slice(len: usize) -> *mut RcBox<[T]> { unsafe { - Self::allocate_for_layout(Layout::array::<T>(len).unwrap(), |mem| { - ptr::slice_from_raw_parts_mut(mem as *mut T, len) as *mut RcBox<[T]> - }) + Self::allocate_for_layout( + Layout::array::<T>(len).unwrap(), + |layout| Global.alloc(layout), + |mem| ptr::slice_from_raw_parts_mut(mem as *mut T, len) as *mut RcBox<[T]>, + ) } } } @@ -1142,8 +1146,6 @@ unsafe impl<#[may_dangle] T: ?Sized> Drop for Rc<T> { /// drop(foo); // Doesn't print anything /// drop(foo2); // Prints "dropped!" /// ``` - /// - /// [`Weak`]: ../../std/rc/struct.Weak.html fn drop(&mut self) { unsafe { self.dec_strong(); @@ -1625,11 +1627,7 @@ impl<T, I: iter::TrustedLen<Item = T>> ToRcSlice<T> for I { /// /// The typical way to obtain a `Weak` pointer is to call [`Rc::downgrade`]. /// -/// [`Rc`]: struct.Rc.html -/// [`Rc::downgrade`]: struct.Rc.html#method.downgrade -/// [`upgrade`]: struct.Weak.html#method.upgrade -/// [`Option`]: ../../std/option/enum.Option.html -/// [`None`]: ../../std/option/enum.Option.html#variant.None +/// [`upgrade`]: Weak::upgrade #[stable(feature = "rc_weak", since = "1.4.0")] pub struct Weak<T: ?Sized> { // This is a `NonNull` to allow optimizing the size of this type in enums, @@ -1656,8 +1654,7 @@ impl<T> Weak<T> { /// Constructs a new `Weak<T>`, without allocating any memory. /// Calling [`upgrade`] on the return value always gives [`None`]. /// - /// [`upgrade`]: #method.upgrade - /// [`None`]: ../../std/option/enum.Option.html + /// [`upgrade`]: Weak::upgrade /// /// # Examples /// @@ -1696,7 +1693,7 @@ impl<T> Weak<T> { /// // assert_eq!("hello", unsafe { &*weak.as_ptr() }); /// ``` /// - /// [`null`]: ../../std/ptr/fn.null.html + /// [`null`]: core::ptr::null #[stable(feature = "rc_as_ptr", since = "1.45.0")] pub fn as_ptr(&self) -> *const T { let ptr: *mut RcBox<T> = NonNull::as_ptr(self.ptr); @@ -1715,8 +1712,9 @@ impl<T> Weak<T> { /// Consumes the `Weak<T>` and turns it into a raw pointer. /// - /// This converts the weak pointer into a raw pointer, preserving the original weak count. It - /// can be turned back into the `Weak<T>` with [`from_raw`]. + /// This converts the weak pointer into a raw pointer, while still preserving the ownership of + /// one weak reference (the weak count is not modified by this operation). It can be turned + /// back into the `Weak<T>` with [`from_raw`]. /// /// The same restrictions of accessing the target of the pointer as with /// [`as_ptr`] apply. @@ -1737,8 +1735,8 @@ impl<T> Weak<T> { /// assert_eq!(0, Rc::weak_count(&strong)); /// ``` /// - /// [`from_raw`]: struct.Weak.html#method.from_raw - /// [`as_ptr`]: struct.Weak.html#method.as_ptr + /// [`from_raw`]: Weak::from_raw + /// [`as_ptr`]: Weak::as_ptr #[stable(feature = "weak_into_raw", since = "1.45.0")] pub fn into_raw(self) -> *const T { let result = self.as_ptr(); @@ -1751,17 +1749,18 @@ impl<T> Weak<T> { /// This can be used to safely get a strong reference (by calling [`upgrade`] /// later) or to deallocate the weak count by dropping the `Weak<T>`. /// - /// It takes ownership of one weak count (with the exception of pointers created by [`new`], - /// as these don't have any corresponding weak count). + /// It takes ownership of one weak reference (with the exception of pointers created by [`new`], + /// as these don't own anything; the method still works on them). /// /// # Safety /// - /// The pointer must have originated from the [`into_raw`] and must still own its potential - /// weak reference count. + /// The pointer must have originated from the [`into_raw`] and must still own its potential + /// weak reference. /// - /// It is allowed for the strong count to be 0 at the time of calling this, but the weak count - /// must be non-zero or the pointer must have originated from a dangling `Weak<T>` (one created - /// by [`new`]). + /// It is allowed for the strong count to be 0 at the time of calling this. Nevertheless, this + /// takes ownership of one weak reference currently represented as a raw pointer (the weak + /// count is not modified by this operation) and therefore it must be paired with a previous + /// call to [`into_raw`]. /// /// # Examples /// @@ -1784,12 +1783,9 @@ impl<T> Weak<T> { /// assert!(unsafe { Weak::from_raw(raw_2) }.upgrade().is_none()); /// ``` /// - /// [`into_raw`]: struct.Weak.html#method.into_raw - /// [`upgrade`]: struct.Weak.html#method.upgrade - /// [`Rc`]: struct.Rc.html - /// [`Weak`]: struct.Weak.html - /// [`new`]: struct.Weak.html#method.new - /// [`forget`]: ../../std/mem/fn.forget.html + /// [`into_raw`]: Weak::into_raw + /// [`upgrade`]: Weak::upgrade + /// [`new`]: Weak::new #[stable(feature = "weak_into_raw", since = "1.45.0")] pub unsafe fn from_raw(ptr: *const T) -> Self { if ptr.is_null() { @@ -1817,9 +1813,6 @@ impl<T: ?Sized> Weak<T> { /// /// Returns [`None`] if the inner value has since been dropped. /// - /// [`Rc`]: struct.Rc.html - /// [`None`]: ../../std/option/enum.Option.html - /// /// # Examples /// /// ``` @@ -1852,8 +1845,6 @@ impl<T: ?Sized> Weak<T> { /// Gets the number of strong (`Rc`) pointers pointing to this allocation. /// /// If `self` was created using [`Weak::new`], this will return 0. - /// - /// [`Weak::new`]: #method.new #[stable(feature = "weak_counts", since = "1.41.0")] pub fn strong_count(&self) -> usize { if let Some(inner) = self.inner() { inner.strong() } else { 0 } @@ -1922,7 +1913,7 @@ impl<T: ?Sized> Weak<T> { /// assert!(!first.ptr_eq(&third)); /// ``` /// - /// [`ptr::eq`]: ../../std/ptr/fn.eq.html + /// [`ptr::eq`]: core::ptr::eq #[inline] #[stable(feature = "weak_ptr_eq", since = "1.39.0")] pub fn ptr_eq(&self, other: &Self) -> bool { @@ -2004,8 +1995,8 @@ impl<T> Default for Weak<T> { /// Constructs a new `Weak<T>`, allocating memory for `T` without initializing /// it. Calling [`upgrade`] on the return value always gives [`None`]. /// - /// [`None`]: ../../std/option/enum.Option.html - /// [`upgrade`]: ../../std/rc/struct.Weak.html#method.upgrade + /// [`None`]: Option + /// [`upgrade`]: Weak::upgrade /// /// # Examples /// @@ -2113,7 +2104,7 @@ impl<T: ?Sized> AsRef<T> for Rc<T> { #[stable(feature = "pin", since = "1.33.0")] impl<T: ?Sized> Unpin for Rc<T> {} -/// Get the offset within an `ArcInner` for +/// Get the offset within an `RcBox` for /// a payload of type described by a pointer. /// /// # Safety @@ -2122,7 +2113,7 @@ impl<T: ?Sized> Unpin for Rc<T> {} /// /// - This function is safe for any argument if `T` is sized, and /// - if `T` is unsized, the pointer must have appropriate pointer metadata -/// aquired from the real instance that you are getting this offset for. +/// acquired from the real instance that you are getting this offset for. unsafe fn data_offset<T: ?Sized>(ptr: *const T) -> isize { // Align the unsized value to the end of the `RcBox`. // Because it is ?Sized, it will always be the last field in memory. diff --git a/library/alloc/src/slice.rs b/library/alloc/src/slice.rs index 3d51115fe01..8ea2c6dc859 100644 --- a/library/alloc/src/slice.rs +++ b/library/alloc/src/slice.rs @@ -70,11 +70,7 @@ //! * Further methods that return iterators are [`.split`], [`.splitn`], //! [`.chunks`], [`.windows`] and more. //! -//! [`Clone`]: ../../std/clone/trait.Clone.html -//! [`Eq`]: ../../std/cmp/trait.Eq.html -//! [`Ord`]: ../../std/cmp/trait.Ord.html -//! [`Iter`]: struct.Iter.html -//! [`Hash`]: ../../std/hash/trait.Hash.html +//! [`Hash`]: core::hash::Hash //! [`.iter`]: ../../std/primitive.slice.html#method.iter //! [`.iter_mut`]: ../../std/primitive.slice.html#method.iter_mut //! [`.split`]: ../../std/primitive.slice.html#method.split @@ -95,6 +91,8 @@ use crate::borrow::ToOwned; use crate::boxed::Box; use crate::vec::Vec; +#[unstable(feature = "array_chunks", issue = "74985")] +pub use core::slice::ArrayChunks; #[stable(feature = "slice_get_slice", since = "1.28.0")] pub use core::slice::SliceIndex; #[stable(feature = "from_ref", since = "1.28.0")] @@ -558,7 +556,7 @@ impl [u8] { /// /// To uppercase the value in-place, use [`make_ascii_uppercase`]. /// - /// [`make_ascii_uppercase`]: #method.make_ascii_uppercase + /// [`make_ascii_uppercase`]: u8::make_ascii_uppercase #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")] #[inline] pub fn to_ascii_uppercase(&self) -> Vec<u8> { @@ -575,7 +573,7 @@ impl [u8] { /// /// To lowercase the value in-place, use [`make_ascii_lowercase`]. /// - /// [`make_ascii_lowercase`]: #method.make_ascii_lowercase + /// [`make_ascii_lowercase`]: u8::make_ascii_lowercase #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")] #[inline] pub fn to_ascii_lowercase(&self) -> Vec<u8> { diff --git a/library/alloc/src/string.rs b/library/alloc/src/string.rs index 05398ca68c8..05690e19d23 100644 --- a/library/alloc/src/string.rs +++ b/library/alloc/src/string.rs @@ -268,8 +268,8 @@ use crate::vec::Vec; /// /// Here, there's no need to allocate more memory inside the loop. /// -/// [`str`]: type@str -/// [`&str`]: type@str +/// [`str`]: prim@str +/// [`&str`]: prim@str /// [`Deref`]: core::ops::Deref /// [`as_str()`]: String::as_str #[derive(PartialOrd, Eq, Ord)] @@ -296,7 +296,7 @@ pub struct String { /// /// [`Utf8Error`]: core::str::Utf8Error /// [`std::str`]: core::str -/// [`&str`]: str +/// [`&str`]: prim@str /// [`utf8_error`]: Self::utf8_error /// /// # Examples @@ -472,7 +472,7 @@ impl String { /// /// [`from_utf8_unchecked`]: String::from_utf8_unchecked /// [`Vec<u8>`]: crate::vec::Vec - /// [`&str`]: str + /// [`&str`]: prim@str /// [`into_bytes`]: String::into_bytes #[inline] #[stable(feature = "rust1", since = "1.0.0")] @@ -1576,6 +1576,8 @@ impl String { /// /// This will drop any excess capacity. /// + /// [`str`]: prim@str + /// /// # Examples /// /// Basic usage: @@ -1644,7 +1646,7 @@ impl FromUtf8Error { /// on using it. /// /// [`std::str`]: core::str - /// [`&str`]: str + /// [`&str`]: prim@str /// /// # Examples /// @@ -2196,6 +2198,9 @@ pub trait ToString { /// since `fmt::Write for String` never returns an error itself. #[stable(feature = "rust1", since = "1.0.0")] impl<T: fmt::Display + ?Sized> ToString for T { + // A common guideline is to not inline generic functions. However, + // remove `#[inline]` from this method causes non-negligible regression. + // See <https://github.com/rust-lang/rust/pull/74852> as last attempt try to remove it. #[inline] default fn to_string(&self) -> String { use fmt::Write; diff --git a/library/alloc/src/sync.rs b/library/alloc/src/sync.rs index 8a5f1ee5076..ff07bf52c02 100644 --- a/library/alloc/src/sync.rs +++ b/library/alloc/src/sync.rs @@ -2,9 +2,7 @@ //! Thread-safe reference-counting pointers. //! -//! See the [`Arc<T>`][arc] documentation for more details. -//! -//! [arc]: struct.Arc.html +//! See the [`Arc<T>`][Arc] documentation for more details. use core::any::Any; use core::borrow; @@ -23,7 +21,7 @@ use core::slice::from_raw_parts_mut; use core::sync::atomic; use core::sync::atomic::Ordering::{Acquire, Relaxed, Release, SeqCst}; -use crate::alloc::{box_free, handle_alloc_error, AllocInit, AllocRef, Global, Layout}; +use crate::alloc::{box_free, handle_alloc_error, AllocErr, AllocRef, Global, Layout}; use crate::borrow::{Cow, ToOwned}; use crate::boxed::Box; use crate::rc::is_dangling; @@ -100,21 +98,21 @@ macro_rules! acquire { /// ## Breaking cycles with `Weak` /// /// The [`downgrade`][downgrade] method can be used to create a non-owning -/// [`Weak`][weak] pointer. A [`Weak`][weak] pointer can be [`upgrade`][upgrade]d +/// [`Weak`] pointer. A [`Weak`] pointer can be [`upgrade`][upgrade]d /// to an `Arc`, but this will return [`None`] if the value stored in the allocation has /// already been dropped. In other words, `Weak` pointers do not keep the value /// inside the allocation alive; however, they *do* keep the allocation /// (the backing store for the value) alive. /// /// A cycle between `Arc` pointers will never be deallocated. For this reason, -/// [`Weak`][weak] is used to break cycles. For example, a tree could have -/// strong `Arc` pointers from parent nodes to children, and [`Weak`][weak] +/// [`Weak`] is used to break cycles. For example, a tree could have +/// strong `Arc` pointers from parent nodes to children, and [`Weak`] /// pointers from children back to their parents. /// /// # Cloning references /// -/// Creating a new reference from an existing reference counted pointer is done using the -/// `Clone` trait implemented for [`Arc<T>`][arc] and [`Weak<T>`][weak]. +/// Creating a new reference from an existing reference-counted pointer is done using the +/// `Clone` trait implemented for [`Arc<T>`][Arc] and [`Weak<T>`][Weak]. /// /// ``` /// use std::sync::Arc; @@ -139,23 +137,20 @@ macro_rules! acquire { /// Arc::downgrade(&my_arc); /// ``` /// -/// [`Weak<T>`][weak] does not auto-dereference to `T`, because the inner value may have +/// [`Weak<T>`][Weak] does not auto-dereference to `T`, because the inner value may have /// already been dropped. /// -/// [arc]: struct.Arc.html -/// [weak]: struct.Weak.html -/// [`Rc<T>`]: ../../std/rc/struct.Rc.html -/// [clone]: ../../std/clone/trait.Clone.html#tymethod.clone +/// [`Rc<T>`]: crate::rc::Rc +/// [clone]: Clone::clone /// [mutex]: ../../std/sync/struct.Mutex.html /// [rwlock]: ../../std/sync/struct.RwLock.html -/// [atomic]: ../../std/sync/atomic/index.html -/// [`Send`]: ../../std/marker/trait.Send.html -/// [`Sync`]: ../../std/marker/trait.Sync.html -/// [deref]: ../../std/ops/trait.Deref.html -/// [downgrade]: struct.Arc.html#method.downgrade -/// [upgrade]: struct.Weak.html#method.upgrade -/// [`None`]: ../../std/option/enum.Option.html#variant.None -/// [`RefCell<T>`]: ../../std/cell/struct.RefCell.html +/// [atomic]: core::sync::atomic +/// [`Send`]: core::marker::Send +/// [`Sync`]: core::marker::Sync +/// [deref]: core::ops::Deref +/// [downgrade]: Arc::downgrade +/// [upgrade]: Weak::upgrade +/// [`RefCell<T>`]: core::cell::RefCell /// [`std::sync`]: ../../std/sync/index.html /// [`Arc::clone(&from)`]: #method.clone /// @@ -184,7 +179,7 @@ macro_rules! acquire { /// /// Sharing a mutable [`AtomicUsize`]: /// -/// [`AtomicUsize`]: ../../std/sync/atomic/struct.AtomicUsize.html +/// [`AtomicUsize`]: core::sync::atomic::AtomicUsize /// /// ```no_run /// use std::sync::Arc; @@ -254,11 +249,7 @@ impl<T: ?Sized> Arc<T> { /// /// The typical way to obtain a `Weak` pointer is to call [`Arc::downgrade`]. /// -/// [`Arc`]: struct.Arc.html -/// [`Arc::downgrade`]: struct.Arc.html#method.downgrade -/// [`upgrade`]: struct.Weak.html#method.upgrade -/// [`Option`]: ../../std/option/enum.Option.html -/// [`None`]: ../../std/option/enum.Option.html#variant.None +/// [`upgrade`]: Weak::upgrade #[stable(feature = "arc_weak", since = "1.4.0")] pub struct Weak<T: ?Sized> { // This is a `NonNull` to allow optimizing the size of this type in enums, @@ -328,6 +319,79 @@ impl<T> Arc<T> { Self::from_inner(Box::leak(x).into()) } + /// Constructs a new `Arc<T>` using a weak reference to itself. Attempting + /// to upgrade the weak reference before this function returns will result + /// in a `None` value. However, the weak reference may be cloned freely and + /// stored for use at a later time. + /// + /// # Examples + /// ``` + /// #![feature(arc_new_cyclic)] + /// #![allow(dead_code)] + /// + /// use std::sync::{Arc, Weak}; + /// + /// struct Foo { + /// me: Weak<Foo>, + /// } + /// + /// let foo = Arc::new_cyclic(|me| Foo { + /// me: me.clone(), + /// }); + /// ``` + #[inline] + #[unstable(feature = "arc_new_cyclic", issue = "75861")] + pub fn new_cyclic(data_fn: impl FnOnce(&Weak<T>) -> T) -> Arc<T> { + // Construct the inner in the "uninitialized" state with a single + // weak reference. + let uninit_ptr: NonNull<_> = Box::leak(box ArcInner { + strong: atomic::AtomicUsize::new(0), + weak: atomic::AtomicUsize::new(1), + data: mem::MaybeUninit::<T>::uninit(), + }) + .into(); + let init_ptr: NonNull<ArcInner<T>> = uninit_ptr.cast(); + + let weak = Weak { ptr: init_ptr }; + + // It's important we don't give up ownership of the weak pointer, or + // else the memory might be freed by the time `data_fn` returns. If + // we really wanted to pass ownership, we could create an additional + // weak pointer for ourselves, but this would result in additional + // updates to the weak reference count which might not be necessary + // otherwise. + let data = data_fn(&weak); + + // Now we can properly initialize the inner value and turn our weak + // reference into a strong reference. + unsafe { + let inner = init_ptr.as_ptr(); + ptr::write(&raw mut (*inner).data, data); + + // The above write to the data field must be visible to any threads which + // observe a non-zero strong count. Therefore we need at least "Release" ordering + // in order to synchronize with the `compare_exchange_weak` in `Weak::upgrade`. + // + // "Acquire" ordering is not required. When considering the possible behaviours + // of `data_fn` we only need to look at what it could do with a reference to a + // non-upgradeable `Weak`: + // - It can *clone* the `Weak`, increasing the weak reference count. + // - It can drop those clones, decreasing the weak reference count (but never to zero). + // + // These side effects do not impact us in any way, and no other side effects are + // possible with safe code alone. + let prev_value = (*inner).strong.fetch_add(1, Release); + debug_assert_eq!(prev_value, 0, "No prior strong references should exist"); + } + + let strong = Arc::from_inner(init_ptr); + + // Strong references should collectively own a shared weak reference, + // so don't run the destructor for our old weak reference. + mem::forget(weak); + strong + } + /// Constructs a new `Arc` with uninitialized contents. /// /// # Examples @@ -352,9 +416,11 @@ impl<T> Arc<T> { #[unstable(feature = "new_uninit", issue = "63291")] pub fn new_uninit() -> Arc<mem::MaybeUninit<T>> { unsafe { - Arc::from_ptr(Arc::allocate_for_layout(Layout::new::<T>(), |mem| { - mem as *mut ArcInner<mem::MaybeUninit<T>> - })) + Arc::from_ptr(Arc::allocate_for_layout( + Layout::new::<T>(), + |layout| Global.alloc(layout), + |mem| mem as *mut ArcInner<mem::MaybeUninit<T>>, + )) } } @@ -381,9 +447,11 @@ impl<T> Arc<T> { #[unstable(feature = "new_uninit", issue = "63291")] pub fn new_zeroed() -> Arc<mem::MaybeUninit<T>> { unsafe { - let mut uninit = Self::new_uninit(); - ptr::write_bytes::<T>(Arc::get_mut_unchecked(&mut uninit).as_mut_ptr(), 0, 1); - uninit + Arc::from_ptr(Arc::allocate_for_layout( + Layout::new::<T>(), + |layout| Global.alloc_zeroed(layout), + |mem| mem as *mut ArcInner<mem::MaybeUninit<T>>, + )) } } @@ -396,13 +464,11 @@ impl<T> Arc<T> { /// Returns the inner value, if the `Arc` has exactly one strong reference. /// - /// Otherwise, an [`Err`][result] is returned with the same `Arc` that was + /// Otherwise, an [`Err`] is returned with the same `Arc` that was /// passed in. /// /// This will succeed even if there are outstanding weak references. /// - /// [result]: ../../std/result/enum.Result.html - /// /// # Examples /// /// ``` @@ -437,7 +503,7 @@ impl<T> Arc<T> { } impl<T> Arc<[T]> { - /// Constructs a new reference-counted slice with uninitialized contents. + /// Constructs a new atomically reference-counted slice with uninitialized contents. /// /// # Examples /// @@ -464,6 +530,40 @@ impl<T> Arc<[T]> { pub fn new_uninit_slice(len: usize) -> Arc<[mem::MaybeUninit<T>]> { unsafe { Arc::from_ptr(Arc::allocate_for_slice(len)) } } + + /// Constructs a new atomically reference-counted slice with uninitialized contents, with the memory being + /// filled with `0` bytes. + /// + /// See [`MaybeUninit::zeroed`][zeroed] for examples of correct and + /// incorrect usage of this method. + /// + /// # Examples + /// + /// ``` + /// #![feature(new_uninit)] + /// + /// use std::sync::Arc; + /// + /// let values = Arc::<[u32]>::new_zeroed_slice(3); + /// let values = unsafe { values.assume_init() }; + /// + /// assert_eq!(*values, [0, 0, 0]) + /// ``` + /// + /// [zeroed]: ../../std/mem/union.MaybeUninit.html#method.zeroed + #[unstable(feature = "new_uninit", issue = "63291")] + pub fn new_zeroed_slice(len: usize) -> Arc<[mem::MaybeUninit<T>]> { + unsafe { + Arc::from_ptr(Arc::allocate_for_layout( + Layout::array::<T>(len).unwrap(), + |layout| Global.alloc_zeroed(layout), + |mem| { + ptr::slice_from_raw_parts_mut(mem as *mut T, len) + as *mut ArcInner<[mem::MaybeUninit<T>]> + }, + )) + } + } } impl<T> Arc<mem::MaybeUninit<T>> { @@ -550,9 +650,7 @@ impl<T: ?Sized> Arc<T> { /// Consumes the `Arc`, returning the wrapped pointer. /// /// To avoid a memory leak the pointer must be converted back to an `Arc` using - /// [`Arc::from_raw`][from_raw]. - /// - /// [from_raw]: struct.Arc.html#method.from_raw + /// [`Arc::from_raw`]. /// /// # Examples /// @@ -612,8 +710,8 @@ impl<T: ?Sized> Arc<T> { /// This function is unsafe because improper use may lead to memory unsafety, /// even if the returned `Arc<T>` is never accessed. /// - /// [into_raw]: struct.Arc.html#method.into_raw - /// [transmute]: ../../std/mem/fn.transmute.html + /// [into_raw]: Arc::into_raw + /// [transmute]: core::mem::transmute /// /// # Examples /// @@ -646,32 +744,7 @@ impl<T: ?Sized> Arc<T> { } } - /// Consumes the `Arc`, returning the wrapped pointer as `NonNull<T>`. - /// - /// # Examples - /// - /// ``` - /// #![feature(rc_into_raw_non_null)] - /// #![allow(deprecated)] - /// - /// use std::sync::Arc; - /// - /// let x = Arc::new("hello".to_owned()); - /// let ptr = Arc::into_raw_non_null(x); - /// let deref = unsafe { ptr.as_ref() }; - /// assert_eq!(deref, "hello"); - /// ``` - #[unstable(feature = "rc_into_raw_non_null", issue = "47336")] - #[rustc_deprecated(since = "1.44.0", reason = "use `Arc::into_raw` instead")] - #[inline] - pub fn into_raw_non_null(this: Self) -> NonNull<T> { - // safe because Arc guarantees its pointer is non-null - unsafe { NonNull::new_unchecked(Arc::into_raw(this) as *mut _) } - } - - /// Creates a new [`Weak`][weak] pointer to this allocation. - /// - /// [weak]: struct.Weak.html + /// Creates a new [`Weak`] pointer to this allocation. /// /// # Examples /// @@ -713,9 +786,7 @@ impl<T: ?Sized> Arc<T> { } } - /// Gets the number of [`Weak`][weak] pointers to this allocation. - /// - /// [weak]: struct.Weak.html + /// Gets the number of [`Weak`] pointers to this allocation. /// /// # Safety /// @@ -884,7 +955,7 @@ impl<T: ?Sized> Arc<T> { /// assert!(!Arc::ptr_eq(&five, &other_five)); /// ``` /// - /// [`ptr::eq`]: ../../std/ptr/fn.eq.html + /// [`ptr::eq`]: core::ptr::eq pub fn ptr_eq(this: &Self, other: &Self) -> bool { this.ptr.as_ptr() == other.ptr.as_ptr() } @@ -898,6 +969,7 @@ impl<T: ?Sized> Arc<T> { /// and must return back a (potentially fat)-pointer for the `ArcInner<T>`. unsafe fn allocate_for_layout( value_layout: Layout, + allocate: impl FnOnce(Layout) -> Result<NonNull<[u8]>, AllocErr>, mem_to_arcinner: impl FnOnce(*mut u8) -> *mut ArcInner<T>, ) -> *mut ArcInner<T> { // Calculate layout using the given value layout. @@ -906,12 +978,10 @@ impl<T: ?Sized> Arc<T> { // reference (see #54908). let layout = Layout::new::<ArcInner<()>>().extend(value_layout).unwrap().0.pad_to_align(); - let mem = Global - .alloc(layout, AllocInit::Uninitialized) - .unwrap_or_else(|_| handle_alloc_error(layout)); + let ptr = allocate(layout).unwrap_or_else(|_| handle_alloc_error(layout)); // Initialize the ArcInner - let inner = mem_to_arcinner(mem.ptr.as_ptr()); + let inner = mem_to_arcinner(ptr.as_non_null_ptr().as_ptr()); debug_assert_eq!(unsafe { Layout::for_value(&*inner) }, layout); unsafe { @@ -926,9 +996,11 @@ impl<T: ?Sized> Arc<T> { unsafe fn allocate_for_ptr(ptr: *const T) -> *mut ArcInner<T> { // Allocate for the `ArcInner<T>` using the given value. unsafe { - Self::allocate_for_layout(Layout::for_value(&*ptr), |mem| { - set_data_ptr(ptr as *mut T, mem) as *mut ArcInner<T> - }) + Self::allocate_for_layout( + Layout::for_value(&*ptr), + |layout| Global.alloc(layout), + |mem| set_data_ptr(ptr as *mut T, mem) as *mut ArcInner<T>, + ) } } @@ -959,9 +1031,11 @@ impl<T> Arc<[T]> { /// Allocates an `ArcInner<[T]>` with the given length. unsafe fn allocate_for_slice(len: usize) -> *mut ArcInner<[T]> { unsafe { - Self::allocate_for_layout(Layout::array::<T>(len).unwrap(), |mem| { - ptr::slice_from_raw_parts_mut(mem as *mut T, len) as *mut ArcInner<[T]> - }) + Self::allocate_for_layout( + Layout::array::<T>(len).unwrap(), + |layout| Global.alloc(layout), + |mem| ptr::slice_from_raw_parts_mut(mem as *mut T, len) as *mut ArcInner<[T]>, + ) } } } @@ -1011,7 +1085,7 @@ impl<T> Arc<[T]> { let slice = from_raw_parts_mut(self.elems, self.n_elems); ptr::drop_in_place(slice); - Global.dealloc(self.mem.cast(), self.layout); + Global.dealloc(self.mem, self.layout); } } } @@ -1123,7 +1197,7 @@ impl<T: ?Sized> Receiver for Arc<T> {} impl<T: Clone> Arc<T> { /// Makes a mutable reference into the given `Arc`. /// - /// If there are other `Arc` or [`Weak`][weak] pointers to the same allocation, + /// If there are other `Arc` or [`Weak`] pointers to the same allocation, /// then `make_mut` will create a new allocation and invoke [`clone`][clone] on the inner value /// to ensure unique ownership. This is also referred to as clone-on-write. /// @@ -1132,10 +1206,9 @@ impl<T: Clone> Arc<T> { /// /// See also [`get_mut`][get_mut], which will fail rather than cloning. /// - /// [weak]: struct.Weak.html - /// [clone]: ../../std/clone/trait.Clone.html#tymethod.clone - /// [get_mut]: struct.Arc.html#method.get_mut - /// [`Rc::make_mut`]: ../rc/struct.Rc.html#method.make_mut + /// [clone]: Clone::clone + /// [get_mut]: Arc::get_mut + /// [`Rc::make_mut`]: super::rc::Rc::make_mut /// /// # Examples /// @@ -1209,18 +1282,16 @@ impl<T: Clone> Arc<T> { impl<T: ?Sized> Arc<T> { /// Returns a mutable reference into the given `Arc`, if there are - /// no other `Arc` or [`Weak`][weak] pointers to the same allocation. + /// no other `Arc` or [`Weak`] pointers to the same allocation. /// - /// Returns [`None`][option] otherwise, because it is not safe to + /// Returns [`None`] otherwise, because it is not safe to /// mutate a shared value. /// /// See also [`make_mut`][make_mut], which will [`clone`][clone] /// the inner value when there are other pointers. /// - /// [weak]: struct.Weak.html - /// [option]: ../../std/option/enum.Option.html - /// [make_mut]: struct.Arc.html#method.make_mut - /// [clone]: ../../std/clone/trait.Clone.html#tymethod.clone + /// [make_mut]: Arc::make_mut + /// [clone]: Clone::clone /// /// # Examples /// @@ -1254,7 +1325,7 @@ impl<T: ?Sized> Arc<T> { /// /// See also [`get_mut`], which is safe and does appropriate checks. /// - /// [`get_mut`]: struct.Arc.html#method.get_mut + /// [`get_mut`]: Arc::get_mut /// /// # Safety /// @@ -1340,8 +1411,6 @@ unsafe impl<#[may_dangle] T: ?Sized> Drop for Arc<T> { /// drop(foo); // Doesn't print anything /// drop(foo2); // Prints "dropped!" /// ``` - /// - /// [`Weak`]: ../../std/sync/struct.Weak.html #[inline] fn drop(&mut self) { // Because `fetch_sub` is already atomic, we do not need to synchronize @@ -1426,8 +1495,7 @@ impl<T> Weak<T> { /// Constructs a new `Weak<T>`, without allocating any memory. /// Calling [`upgrade`] on the return value always gives [`None`]. /// - /// [`upgrade`]: struct.Weak.html#method.upgrade - /// [`None`]: ../../std/option/enum.Option.html#variant.None + /// [`upgrade`]: Weak::upgrade /// /// # Examples /// @@ -1466,7 +1534,7 @@ impl<T> Weak<T> { /// // assert_eq!("hello", unsafe { &*weak.as_ptr() }); /// ``` /// - /// [`null`]: ../../std/ptr/fn.null.html + /// [`null`]: core::ptr::null #[stable(feature = "weak_into_raw", since = "1.45.0")] pub fn as_ptr(&self) -> *const T { let ptr: *mut ArcInner<T> = NonNull::as_ptr(self.ptr); @@ -1485,8 +1553,9 @@ impl<T> Weak<T> { /// Consumes the `Weak<T>` and turns it into a raw pointer. /// - /// This converts the weak pointer into a raw pointer, preserving the original weak count. It - /// can be turned back into the `Weak<T>` with [`from_raw`]. + /// This converts the weak pointer into a raw pointer, while still preserving the ownership of + /// one weak reference (the weak count is not modified by this operation). It can be turned + /// back into the `Weak<T>` with [`from_raw`]. /// /// The same restrictions of accessing the target of the pointer as with /// [`as_ptr`] apply. @@ -1507,8 +1576,8 @@ impl<T> Weak<T> { /// assert_eq!(0, Arc::weak_count(&strong)); /// ``` /// - /// [`from_raw`]: struct.Weak.html#method.from_raw - /// [`as_ptr`]: struct.Weak.html#method.as_ptr + /// [`from_raw`]: Weak::from_raw + /// [`as_ptr`]: Weak::as_ptr #[stable(feature = "weak_into_raw", since = "1.45.0")] pub fn into_raw(self) -> *const T { let result = self.as_ptr(); @@ -1516,24 +1585,23 @@ impl<T> Weak<T> { result } - /// Converts a raw pointer previously created by [`into_raw`] back into - /// `Weak<T>`. + /// Converts a raw pointer previously created by [`into_raw`] back into `Weak<T>`. /// /// This can be used to safely get a strong reference (by calling [`upgrade`] /// later) or to deallocate the weak count by dropping the `Weak<T>`. /// - /// It takes ownership of one weak count (with the exception of pointers created by [`new`], - /// as these don't have any corresponding weak count). + /// It takes ownership of one weak reference (with the exception of pointers created by [`new`], + /// as these don't own anything; the method still works on them). /// /// # Safety /// /// The pointer must have originated from the [`into_raw`] and must still own its potential - /// weak reference count. - /// - /// It is allowed for the strong count to be 0 at the time of calling this, but the weak count - /// must be non-zero or the pointer must have originated from a dangling `Weak<T>` (one created - /// by [`new`]). + /// weak reference. /// + /// It is allowed for the strong count to be 0 at the time of calling this. Nevertheless, this + /// takes ownership of one weak reference currently represented as a raw pointer (the weak + /// count is not modified by this operation) and therefore it must be paired with a previous + /// call to [`into_raw`]. /// # Examples /// /// ``` @@ -1555,12 +1623,10 @@ impl<T> Weak<T> { /// assert!(unsafe { Weak::from_raw(raw_2) }.upgrade().is_none()); /// ``` /// - /// [`new`]: struct.Weak.html#method.new - /// [`into_raw`]: struct.Weak.html#method.into_raw - /// [`upgrade`]: struct.Weak.html#method.upgrade - /// [`Weak`]: struct.Weak.html - /// [`Arc`]: struct.Arc.html - /// [`forget`]: ../../std/mem/fn.forget.html + /// [`new`]: Weak::new + /// [`into_raw`]: Weak::into_raw + /// [`upgrade`]: Weak::upgrade + /// [`forget`]: std::mem::forget #[stable(feature = "weak_into_raw", since = "1.45.0")] pub unsafe fn from_raw(ptr: *const T) -> Self { if ptr.is_null() { @@ -1590,9 +1656,6 @@ impl<T: ?Sized> Weak<T> { /// /// Returns [`None`] if the inner value has since been dropped. /// - /// [`Arc`]: struct.Arc.html - /// [`None`]: ../../std/option/enum.Option.html#variant.None - /// /// # Examples /// /// ``` @@ -1614,7 +1677,8 @@ impl<T: ?Sized> Weak<T> { #[stable(feature = "arc_weak", since = "1.4.0")] pub fn upgrade(&self) -> Option<Arc<T>> { // We use a CAS loop to increment the strong count instead of a - // fetch_add because once the count hits 0 it must never be above 0. + // fetch_add as this function should never take the reference count + // from zero to one. let inner = self.inner()?; // Relaxed load because any write of 0 that we can observe @@ -1633,8 +1697,11 @@ impl<T: ?Sized> Weak<T> { abort(); } - // Relaxed is valid for the same reason it is on Arc's Clone impl - match inner.strong.compare_exchange_weak(n, n + 1, Relaxed, Relaxed) { + // Relaxed is fine for the failure case because we don't have any expectations about the new state. + // Acquire is necessary for the success case to synchronise with `Arc::new_cyclic`, when the inner + // value can be initialized after `Weak` references have already been created. In that case, we + // expect to observe the fully initialized value. + match inner.strong.compare_exchange_weak(n, n + 1, Acquire, Relaxed) { Ok(_) => return Some(Arc::from_inner(self.ptr)), // null checked above Err(old) => n = old, } @@ -1644,8 +1711,6 @@ impl<T: ?Sized> Weak<T> { /// Gets the number of strong (`Arc`) pointers pointing to this allocation. /// /// If `self` was created using [`Weak::new`], this will return 0. - /// - /// [`Weak::new`]: #method.new #[stable(feature = "weak_counts", since = "1.41.0")] pub fn strong_count(&self) -> usize { if let Some(inner) = self.inner() { inner.strong.load(SeqCst) } else { 0 } @@ -1662,8 +1727,6 @@ impl<T: ?Sized> Weak<T> { /// Due to implementation details, the returned value can be off by 1 in /// either direction when other threads are manipulating any `Arc`s or /// `Weak`s pointing to the same allocation. - /// - /// [`Weak::new`]: #method.new #[stable(feature = "weak_counts", since = "1.41.0")] pub fn weak_count(&self) -> usize { self.inner() @@ -1741,7 +1804,7 @@ impl<T: ?Sized> Weak<T> { /// assert!(!first.ptr_eq(&third)); /// ``` /// - /// [`ptr::eq`]: ../../std/ptr/fn.eq.html + /// [`ptr::eq`]: core::ptr::eq #[inline] #[stable(feature = "weak_ptr_eq", since = "1.39.0")] pub fn ptr_eq(&self, other: &Self) -> bool { @@ -1790,8 +1853,7 @@ impl<T> Default for Weak<T> { /// Calling [`upgrade`] on the return value always /// gives [`None`]. /// - /// [`None`]: ../../std/option/enum.Option.html#variant.None - /// [`upgrade`]: ../../std/sync/struct.Weak.html#method.upgrade + /// [`upgrade`]: Weak::upgrade /// /// # Examples /// @@ -2278,7 +2340,7 @@ impl<T: ?Sized> Unpin for Arc<T> {} /// /// - This function is safe for any argument if `T` is sized, and /// - if `T` is unsized, the pointer must have appropriate pointer metadata -/// aquired from the real instance that you are getting this offset for. +/// acquired from the real instance that you are getting this offset for. unsafe fn data_offset<T: ?Sized>(ptr: *const T) -> isize { // Align the unsized value to the end of the `ArcInner`. // Because it is `?Sized`, it will always be the last field in memory. diff --git a/library/alloc/src/sync/tests.rs b/library/alloc/src/sync/tests.rs index 6f08cd7f123..d2517171606 100644 --- a/library/alloc/src/sync/tests.rs +++ b/library/alloc/src/sync/tests.rs @@ -492,3 +492,70 @@ fn test_array_from_slice() { let a: Result<Arc<[u32; 2]>, _> = r.clone().try_into(); assert!(a.is_err()); } + +#[test] +fn test_arc_cyclic_with_zero_refs() { + struct ZeroRefs { + inner: Weak<ZeroRefs>, + } + let zero_refs = Arc::new_cyclic(|inner| { + assert_eq!(inner.strong_count(), 0); + assert!(inner.upgrade().is_none()); + ZeroRefs { inner: Weak::new() } + }); + + assert_eq!(Arc::strong_count(&zero_refs), 1); + assert_eq!(Arc::weak_count(&zero_refs), 0); + assert_eq!(zero_refs.inner.strong_count(), 0); + assert_eq!(zero_refs.inner.weak_count(), 0); +} + +#[test] +fn test_arc_new_cyclic_one_ref() { + struct OneRef { + inner: Weak<OneRef>, + } + let one_ref = Arc::new_cyclic(|inner| { + assert_eq!(inner.strong_count(), 0); + assert!(inner.upgrade().is_none()); + OneRef { inner: inner.clone() } + }); + + assert_eq!(Arc::strong_count(&one_ref), 1); + assert_eq!(Arc::weak_count(&one_ref), 1); + + let one_ref2 = Weak::upgrade(&one_ref.inner).unwrap(); + assert!(Arc::ptr_eq(&one_ref, &one_ref2)); + + assert_eq!(Arc::strong_count(&one_ref), 2); + assert_eq!(Arc::weak_count(&one_ref), 1); +} + +#[test] +fn test_arc_cyclic_two_refs() { + struct TwoRefs { + inner1: Weak<TwoRefs>, + inner2: Weak<TwoRefs>, + } + let two_refs = Arc::new_cyclic(|inner| { + assert_eq!(inner.strong_count(), 0); + assert!(inner.upgrade().is_none()); + + let inner1 = inner.clone(); + let inner2 = inner1.clone(); + + TwoRefs { inner1, inner2 } + }); + + assert_eq!(Arc::strong_count(&two_refs), 1); + assert_eq!(Arc::weak_count(&two_refs), 2); + + let two_refs1 = Weak::upgrade(&two_refs.inner1).unwrap(); + assert!(Arc::ptr_eq(&two_refs, &two_refs1)); + + let two_refs2 = Weak::upgrade(&two_refs.inner2).unwrap(); + assert!(Arc::ptr_eq(&two_refs, &two_refs2)); + + assert_eq!(Arc::strong_count(&two_refs), 3); + assert_eq!(Arc::weak_count(&two_refs), 2); +} diff --git a/library/alloc/src/task.rs b/library/alloc/src/task.rs index 252e04a4105..5edc5796056 100644 --- a/library/alloc/src/task.rs +++ b/library/alloc/src/task.rs @@ -13,11 +13,9 @@ use crate::sync::Arc; /// /// This trait is a memory-safe and ergonomic alternative to constructing a /// [`RawWaker`]. It supports the common executor design in which the data used -/// to wake up a task is stored in an [`Arc`][arc]. Some executors (especially +/// to wake up a task is stored in an [`Arc`]. Some executors (especially /// those for embedded systems) cannot use this API, which is why [`RawWaker`] /// exists as an alternative for those systems. -/// -/// [arc]: ../../std/sync/struct.Arc.html #[unstable(feature = "wake_trait", issue = "69912")] pub trait Wake { /// Wake this task. diff --git a/library/alloc/src/vec.rs b/library/alloc/src/vec.rs index f5a3d0cd4af..c86798a1bd3 100644 --- a/library/alloc/src/vec.rs +++ b/library/alloc/src/vec.rs @@ -9,7 +9,7 @@ //! //! # Examples //! -//! You can explicitly create a [`Vec<T>`] with [`new`]: +//! You can explicitly create a [`Vec`] with [`Vec::new`]: //! //! ``` //! let v: Vec<i32> = Vec::new(); @@ -50,12 +50,7 @@ //! v[1] = v[1] + 5; //! ``` //! -//! [`Vec<T>`]: ../../std/vec/struct.Vec.html -//! [`new`]: ../../std/vec/struct.Vec.html#method.new -//! [`push`]: ../../std/vec/struct.Vec.html#method.push -//! [`Index`]: ../../std/ops/trait.Index.html -//! [`IndexMut`]: ../../std/ops/trait.IndexMut.html -//! [`vec!`]: ../../std/macro.vec.html +//! [`push`]: Vec::push #![stable(feature = "rust1", since = "1.0.0")] @@ -65,7 +60,7 @@ use core::hash::{Hash, Hasher}; use core::intrinsics::{arith_offset, assume}; use core::iter::{FromIterator, FusedIterator, TrustedLen}; use core::marker::PhantomData; -use core::mem::{self, ManuallyDrop}; +use core::mem::{self, ManuallyDrop, MaybeUninit}; use core::ops::Bound::{Excluded, Included, Unbounded}; use core::ops::{self, Index, IndexMut, RangeBounds}; use core::ptr::{self, NonNull}; @@ -119,8 +114,9 @@ use crate::raw_vec::RawVec; /// assert_eq!(vec, [0, 0, 0, 0, 0]); /// /// // The following is equivalent, but potentially slower: -/// let mut vec1 = Vec::with_capacity(5); -/// vec1.resize(5, 0); +/// let mut vec = Vec::with_capacity(5); +/// vec.resize(5, 0); +/// assert_eq!(vec, [0, 0, 0, 0, 0]); /// ``` /// /// Use a `Vec<T>` as an efficient stack: @@ -278,22 +274,18 @@ use crate::raw_vec::RawVec; /// `Vec` does not currently guarantee the order in which elements are dropped. /// The order has changed in the past and may change again. /// -/// [`vec!`]: ../../std/macro.vec.html /// [`get`]: ../../std/vec/struct.Vec.html#method.get /// [`get_mut`]: ../../std/vec/struct.Vec.html#method.get_mut -/// [`Index`]: ../../std/ops/trait.Index.html -/// [`String`]: ../../std/string/struct.String.html -/// [`&str`]: ../../std/primitive.str.html -/// [`Vec::with_capacity`]: ../../std/vec/struct.Vec.html#method.with_capacity -/// [`Vec::new`]: ../../std/vec/struct.Vec.html#method.new -/// [`shrink_to_fit`]: ../../std/vec/struct.Vec.html#method.shrink_to_fit -/// [`capacity`]: ../../std/vec/struct.Vec.html#method.capacity -/// [`mem::size_of::<T>`]: ../../std/mem/fn.size_of.html -/// [`len`]: ../../std/vec/struct.Vec.html#method.len -/// [`push`]: ../../std/vec/struct.Vec.html#method.push -/// [`insert`]: ../../std/vec/struct.Vec.html#method.insert -/// [`reserve`]: ../../std/vec/struct.Vec.html#method.reserve -/// [owned slice]: ../../std/boxed/struct.Box.html +/// [`String`]: crate::string::String +/// [`&str`]: type@str +/// [`shrink_to_fit`]: Vec::shrink_to_fit +/// [`capacity`]: Vec::capacity +/// [`mem::size_of::<T>`]: core::mem::size_of +/// [`len`]: Vec::len +/// [`push`]: Vec::push +/// [`insert`]: Vec::insert +/// [`reserve`]: Vec::reserve +/// [owned slice]: Box #[stable(feature = "rust1", since = "1.0.0")] #[cfg_attr(not(test), rustc_diagnostic_item = "vec_type")] pub struct Vec<T> { @@ -375,7 +367,7 @@ impl<T> Vec<T> { /// into a `Vec` with the [`from_raw_parts`] function, allowing /// the destructor to perform the cleanup. /// - /// [`from_raw_parts`]: #method.from_raw_parts + /// [`from_raw_parts`]: Vec::from_raw_parts /// /// # Examples /// @@ -430,8 +422,8 @@ impl<T> Vec<T> { /// that nothing else uses the pointer after calling this /// function. /// - /// [`String`]: ../../std/string/struct.String.html - /// [`dealloc`]: ../../alloc/alloc/trait.GlobalAlloc.html#tymethod.dealloc + /// [`String`]: crate::string::String + /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc /// /// # Examples /// @@ -622,7 +614,10 @@ impl<T> Vec<T> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn shrink_to_fit(&mut self) { - if self.capacity() != self.len { + // The capacity is never less than the length, and there's nothing to do when + // they are equal, so we can avoid the panic case in `RawVec::shrink_to_fit` + // by only calling it with a greater capacity. + if self.capacity() > self.len { self.buf.shrink_to_fit(self.len); } } @@ -658,7 +653,7 @@ impl<T> Vec<T> { /// /// Note that this will drop any excess capacity. /// - /// [owned slice]: ../../std/boxed/struct.Box.html + /// [owned slice]: Box /// /// # Examples /// @@ -729,8 +724,8 @@ impl<T> Vec<T> { /// assert_eq!(vec, []); /// ``` /// - /// [`clear`]: #method.clear - /// [`drain`]: #method.drain + /// [`clear`]: Vec::clear + /// [`drain`]: Vec::drain #[stable(feature = "rust1", since = "1.0.0")] pub fn truncate(&mut self, len: usize) { // This is safe because: @@ -809,7 +804,7 @@ impl<T> Vec<T> { /// } /// ``` /// - /// [`as_mut_ptr`]: #method.as_mut_ptr + /// [`as_mut_ptr`]: Vec::as_mut_ptr #[stable(feature = "vec_as_ptr", since = "1.37.0")] #[inline] pub fn as_ptr(&self) -> *const T { @@ -865,17 +860,17 @@ impl<T> Vec<T> { /// is done using one of the safe operations instead, such as /// [`truncate`], [`resize`], [`extend`], or [`clear`]. /// - /// [`truncate`]: #method.truncate - /// [`resize`]: #method.resize - /// [`extend`]: ../../std/iter/trait.Extend.html#tymethod.extend - /// [`clear`]: #method.clear + /// [`truncate`]: Vec::truncate + /// [`resize`]: Vec::resize + /// [`extend`]: Extend::extend + /// [`clear`]: Vec::clear /// /// # Safety /// /// - `new_len` must be less than or equal to [`capacity()`]. /// - The elements at `old_len..new_len` must be initialized. /// - /// [`capacity()`]: #method.capacity + /// [`capacity()`]: Vec::capacity /// /// # Examples /// @@ -1214,8 +1209,6 @@ impl<T> Vec<T> { /// Removes the last element from a vector and returns it, or [`None`] if it /// is empty. /// - /// [`None`]: ../../std/option/enum.Option.html#variant.None - /// /// # Examples /// /// ``` @@ -1462,9 +1455,9 @@ impl<T> Vec<T> { /// If `new_len` is less than `len`, the `Vec` is simply truncated. /// /// This method uses a closure to create new values on every push. If - /// you'd rather [`Clone`] a given value, use [`resize`]. If you want - /// to use the [`Default`] trait to generate values, you can pass - /// [`Default::default()`] as the second argument. + /// you'd rather [`Clone`] a given value, use [`Vec::resize`]. If you + /// want to use the [`Default`] trait to generate values, you can + /// pass [`Default::default`] as the second argument. /// /// # Examples /// @@ -1478,9 +1471,6 @@ impl<T> Vec<T> { /// vec.resize_with(4, || { p *= 2; p }); /// assert_eq!(vec, [2, 4, 8, 16]); /// ``` - /// - /// [`resize`]: #method.resize - /// [`Clone`]: ../../std/clone/trait.Clone.html #[stable(feature = "vec_resize_with", since = "1.33.0")] pub fn resize_with<F>(&mut self, new_len: usize, f: F) where @@ -1510,20 +1500,59 @@ impl<T> Vec<T> { /// Simple usage: /// /// ``` - /// #![feature(vec_leak)] - /// /// let x = vec![1, 2, 3]; - /// let static_ref: &'static mut [usize] = Vec::leak(x); + /// let static_ref: &'static mut [usize] = x.leak(); /// static_ref[0] += 1; /// assert_eq!(static_ref, &[2, 2, 3]); /// ``` - #[unstable(feature = "vec_leak", issue = "62195")] + #[stable(feature = "vec_leak", since = "1.47.0")] #[inline] - pub fn leak<'a>(vec: Vec<T>) -> &'a mut [T] + pub fn leak<'a>(self) -> &'a mut [T] where T: 'a, // Technically not needed, but kept to be explicit. { - Box::leak(vec.into_boxed_slice()) + Box::leak(self.into_boxed_slice()) + } + + /// Returns the remaining spare capacity of the vector as a slice of + /// `MaybeUninit<T>`. + /// + /// The returned slice can be used to fill the vector with data (e.g. by + /// reading from a file) before marking the data as initialized using the + /// [`set_len`] method. + /// + /// [`set_len`]: Vec::set_len + /// + /// # Examples + /// + /// ``` + /// #![feature(vec_spare_capacity, maybe_uninit_extra)] + /// + /// // Allocate vector big enough for 10 elements. + /// let mut v = Vec::with_capacity(10); + /// + /// // Fill in the first 3 elements. + /// let uninit = v.spare_capacity_mut(); + /// uninit[0].write(0); + /// uninit[1].write(1); + /// uninit[2].write(2); + /// + /// // Mark the first 3 elements of the vector as being initialized. + /// unsafe { + /// v.set_len(3); + /// } + /// + /// assert_eq!(&v, &[0, 1, 2]); + /// ``` + #[unstable(feature = "vec_spare_capacity", issue = "75017")] + #[inline] + pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] { + unsafe { + slice::from_raw_parts_mut( + self.as_mut_ptr().add(self.len) as *mut MaybeUninit<T>, + self.buf.capacity() - self.len, + ) + } } } @@ -1537,7 +1566,7 @@ impl<T: Clone> Vec<T> { /// This method requires `T` to implement [`Clone`], /// in order to be able to clone the passed value. /// If you need more flexibility (or want to rely on [`Default`] instead of - /// [`Clone`]), use [`resize_with`]. + /// [`Clone`]), use [`Vec::resize_with`]. /// /// # Examples /// @@ -1550,10 +1579,6 @@ impl<T: Clone> Vec<T> { /// vec.resize(2, 0); /// assert_eq!(vec, [1, 2]); /// ``` - /// - /// [`Clone`]: ../../std/clone/trait.Clone.html - /// [`Default`]: ../../std/default/trait.Default.html - /// [`resize_with`]: #method.resize_with #[stable(feature = "vec_resize", since = "1.5.0")] pub fn resize(&mut self, new_len: usize, value: T) { let len = self.len(); @@ -1583,7 +1608,7 @@ impl<T: Clone> Vec<T> { /// assert_eq!(vec, [1, 2, 3, 4]); /// ``` /// - /// [`extend`]: #method.extend + /// [`extend`]: Vec::extend #[stable(feature = "vec_extend_from_slice", since = "1.6.0")] pub fn extend_from_slice(&mut self, other: &[T]) { self.spec_extend(other.iter()) @@ -1615,10 +1640,7 @@ impl<T: Default> Vec<T> { /// assert_eq!(vec, [1, 2]); /// ``` /// - /// [`resize`]: #method.resize - /// [`Default::default()`]: ../../std/default/trait.Default.html#tymethod.default - /// [`Default`]: ../../std/default/trait.Default.html - /// [`Clone`]: ../../std/clone/trait.Clone.html + /// [`resize`]: Vec::resize #[unstable(feature = "vec_resize_default", issue = "41758")] #[rustc_deprecated( reason = "This is moving towards being removed in favor \ @@ -2230,7 +2252,7 @@ impl<T> Vec<T> { /// with the given `replace_with` iterator and yields the removed items. /// `replace_with` does not need to be the same length as `range`. /// - /// The element range is removed even if the iterator is not consumed until the end. + /// `range` is removed even if the iterator is not consumed until the end. /// /// It is unspecified how many elements are removed from the vector /// if the `Splice` value is leaked. @@ -2299,7 +2321,6 @@ impl<T> Vec<T> { /// Note that `drain_filter` also lets you mutate every element in the filter closure, /// regardless of whether you choose to keep or remove it. /// - /// /// # Examples /// /// Splitting an array into evens and odds, reusing the original allocation: @@ -2581,9 +2602,6 @@ where /// /// This `struct` is created by the `into_iter` method on [`Vec`] (provided /// by the [`IntoIterator`] trait). -/// -/// [`Vec`]: struct.Vec.html -/// [`IntoIterator`]: ../../std/iter/trait.IntoIterator.html #[stable(feature = "rust1", since = "1.0.0")] pub struct IntoIter<T> { buf: NonNull<T>, @@ -2763,10 +2781,7 @@ unsafe impl<#[may_dangle] T> Drop for IntoIter<T> { /// A draining iterator for `Vec<T>`. /// -/// This `struct` is created by the [`drain`] method on [`Vec`]. -/// -/// [`drain`]: struct.Vec.html#method.drain -/// [`Vec`]: struct.Vec.html +/// This `struct` is created by [`Vec::drain`]. #[stable(feature = "drain", since = "1.6.0")] pub struct Drain<'a, T: 'a> { /// Index of tail to preserve @@ -2894,11 +2909,8 @@ impl<T> FusedIterator for Drain<'_, T> {} /// A splicing iterator for `Vec`. /// -/// This struct is created by the [`splice()`] method on [`Vec`]. See its -/// documentation for more. -/// -/// [`splice()`]: struct.Vec.html#method.splice -/// [`Vec`]: struct.Vec.html +/// This struct is created by [`Vec::splice()`]. +/// See its documentation for more. #[derive(Debug)] #[stable(feature = "vec_splice", since = "1.21.0")] pub struct Splice<'a, I: Iterator + 'a> { @@ -3011,7 +3023,10 @@ impl<T> Drain<'_, T> { } } -/// An iterator produced by calling `drain_filter` on Vec. +/// An iterator which uses a closure to determine if an element should be removed. +/// +/// This struct is created by [`Vec::drain_filter`]. +/// See its documentation for more. #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] #[derive(Debug)] pub struct DrainFilter<'a, T, F> |