From 64d98f8ee037282c35007b64c2649055c56af1db Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:19:03 +0200 Subject: Merging upstream version 1.68.2+dfsg1. Signed-off-by: Daniel Baumann --- library/alloc/src/collections/binary_heap.rs | 1721 ------------------- library/alloc/src/collections/binary_heap/mod.rs | 1766 ++++++++++++++++++++ library/alloc/src/collections/binary_heap/tests.rs | 121 +- library/alloc/src/collections/btree/map/tests.rs | 6 +- library/alloc/src/collections/btree/mod.rs | 3 - library/alloc/src/collections/btree/node.rs | 28 +- library/alloc/src/collections/btree/set/tests.rs | 4 +- .../src/collections/btree/testing/crash_test.rs | 119 -- library/alloc/src/collections/btree/testing/mod.rs | 3 - .../src/collections/btree/testing/ord_chaos.rs | 81 - library/alloc/src/collections/btree/testing/rng.rs | 28 - library/alloc/src/collections/linked_list/tests.rs | 69 +- .../alloc/src/collections/vec_deque/into_iter.rs | 4 + library/alloc/src/collections/vec_deque/mod.rs | 186 ++- .../src/collections/vec_deque/spec_from_iter.rs | 33 + library/alloc/src/collections/vec_deque/tests.rs | 42 + 16 files changed, 2108 insertions(+), 2106 deletions(-) delete mode 100644 library/alloc/src/collections/binary_heap.rs create mode 100644 library/alloc/src/collections/binary_heap/mod.rs delete mode 100644 library/alloc/src/collections/btree/testing/crash_test.rs delete mode 100644 library/alloc/src/collections/btree/testing/mod.rs delete mode 100644 library/alloc/src/collections/btree/testing/ord_chaos.rs delete mode 100644 library/alloc/src/collections/btree/testing/rng.rs create mode 100644 library/alloc/src/collections/vec_deque/spec_from_iter.rs (limited to 'library/alloc/src/collections') diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap.rs deleted file mode 100644 index 4583bc9a1..000000000 --- a/library/alloc/src/collections/binary_heap.rs +++ /dev/null @@ -1,1721 +0,0 @@ -//! A priority queue implemented with a binary heap. -//! -//! Insertion and popping the largest element have *O*(log(*n*)) time complexity. -//! Checking the largest element is *O*(1). Converting a vector to a binary heap -//! can be done in-place, and has *O*(*n*) complexity. A binary heap can also be -//! converted to a sorted vector in-place, allowing it to be used for an *O*(*n* * log(*n*)) -//! in-place heapsort. -//! -//! # Examples -//! -//! This is a larger example that implements [Dijkstra's algorithm][dijkstra] -//! to solve the [shortest path problem][sssp] on a [directed graph][dir_graph]. -//! It shows how to use [`BinaryHeap`] with custom types. -//! -//! [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 -//! -//! ``` -//! use std::cmp::Ordering; -//! use std::collections::BinaryHeap; -//! -//! #[derive(Copy, Clone, Eq, PartialEq)] -//! struct State { -//! cost: usize, -//! position: usize, -//! } -//! -//! // The priority queue depends on `Ord`. -//! // Explicitly implement the trait so the queue becomes a min-heap -//! // instead of a max-heap. -//! impl Ord for State { -//! fn cmp(&self, other: &Self) -> Ordering { -//! // Notice that the we flip the ordering on costs. -//! // In case of a tie we compare positions - this step is necessary -//! // to make implementations of `PartialEq` and `Ord` consistent. -//! other.cost.cmp(&self.cost) -//! .then_with(|| self.position.cmp(&other.position)) -//! } -//! } -//! -//! // `PartialOrd` needs to be implemented as well. -//! impl PartialOrd for State { -//! fn partial_cmp(&self, other: &Self) -> Option { -//! Some(self.cmp(other)) -//! } -//! } -//! -//! // Each node is represented as a `usize`, for a shorter implementation. -//! struct Edge { -//! node: usize, -//! cost: usize, -//! } -//! -//! // Dijkstra's shortest path algorithm. -//! -//! // Start at `start` and use `dist` to track the current shortest distance -//! // to each node. This implementation isn't memory-efficient as it may leave duplicate -//! // nodes in the queue. It also uses `usize::MAX` as a sentinel value, -//! // for a simpler implementation. -//! fn shortest_path(adj_list: &Vec>, start: usize, goal: usize) -> Option { -//! // dist[node] = current shortest distance from `start` to `node` -//! let mut dist: Vec<_> = (0..adj_list.len()).map(|_| usize::MAX).collect(); -//! -//! let mut heap = BinaryHeap::new(); -//! -//! // We're at `start`, with a zero cost -//! dist[start] = 0; -//! heap.push(State { cost: 0, position: start }); -//! -//! // Examine the frontier with lower cost nodes first (min-heap) -//! while let Some(State { cost, position }) = heap.pop() { -//! // Alternatively we could have continued to find all shortest paths -//! if position == goal { return Some(cost); } -//! -//! // Important as we may have already found a better way -//! if cost > dist[position] { continue; } -//! -//! // For each node we can reach, see if we can find a way with -//! // a lower cost going through this node -//! for edge in &adj_list[position] { -//! let next = State { cost: cost + edge.cost, position: edge.node }; -//! -//! // If so, add it to the frontier and continue -//! if next.cost < dist[next.position] { -//! heap.push(next); -//! // Relaxation, we have now found a better way -//! dist[next.position] = next.cost; -//! } -//! } -//! } -//! -//! // Goal not reachable -//! None -//! } -//! -//! fn main() { -//! // This is the directed graph we're going to use. -//! // The node numbers correspond to the different states, -//! // and the edge weights symbolize the cost of moving -//! // from one node to another. -//! // Note that the edges are one-way. -//! // -//! // 7 -//! // +-----------------+ -//! // | | -//! // v 1 2 | 2 -//! // 0 -----> 1 -----> 3 ---> 4 -//! // | ^ ^ ^ -//! // | | 1 | | -//! // | | | 3 | 1 -//! // +------> 2 -------+ | -//! // 10 | | -//! // +---------------+ -//! // -//! // The graph is represented as an adjacency list where each index, -//! // corresponding to a node value, has a list of outgoing edges. -//! // Chosen for its efficiency. -//! let graph = vec![ -//! // Node 0 -//! vec![Edge { node: 2, cost: 10 }, -//! Edge { node: 1, cost: 1 }], -//! // Node 1 -//! vec![Edge { node: 3, cost: 2 }], -//! // Node 2 -//! vec![Edge { node: 1, cost: 1 }, -//! Edge { node: 3, cost: 3 }, -//! Edge { node: 4, cost: 1 }], -//! // Node 3 -//! vec![Edge { node: 0, cost: 7 }, -//! Edge { node: 4, cost: 2 }], -//! // Node 4 -//! vec![]]; -//! -//! assert_eq!(shortest_path(&graph, 0, 1), Some(1)); -//! assert_eq!(shortest_path(&graph, 0, 3), Some(3)); -//! assert_eq!(shortest_path(&graph, 3, 0), Some(7)); -//! assert_eq!(shortest_path(&graph, 0, 4), Some(5)); -//! assert_eq!(shortest_path(&graph, 4, 0), None); -//! } -//! ``` - -#![allow(missing_docs)] -#![stable(feature = "rust1", since = "1.0.0")] - -use core::fmt; -use core::iter::{FromIterator, FusedIterator, InPlaceIterable, SourceIter, TrustedLen}; -use core::mem::{self, swap, ManuallyDrop}; -use core::ops::{Deref, DerefMut}; -use core::ptr; - -use crate::collections::TryReserveError; -use crate::slice; -use crate::vec::{self, AsVecIntoIter, Vec}; - -use super::SpecExtend; - -#[cfg(test)] -mod tests; - -/// A priority queue implemented with a binary heap. -/// -/// This will be a max-heap. -/// -/// It is a logic error for an item to be modified in such a way that the -/// item's ordering relative to any other item, as determined by the [`Ord`] -/// trait, changes while it is in the heap. This is normally only possible -/// through [`Cell`], [`RefCell`], global state, I/O, or unsafe code. The -/// behavior resulting from such a logic error is not specified, but will -/// be encapsulated to the `BinaryHeap` that observed the logic error and not -/// result in undefined behavior. This could include panics, incorrect results, -/// aborts, memory leaks, and non-termination. -/// -/// # Examples -/// -/// ``` -/// use std::collections::BinaryHeap; -/// -/// // Type inference lets us omit an explicit type signature (which -/// // would be `BinaryHeap` in this example). -/// let mut heap = BinaryHeap::new(); -/// -/// // We can use peek to look at the next item in the heap. In this case, -/// // there's no items in there yet so we get None. -/// assert_eq!(heap.peek(), None); -/// -/// // Let's add some scores... -/// heap.push(1); -/// heap.push(5); -/// heap.push(2); -/// -/// // Now peek shows the most important item in the heap. -/// assert_eq!(heap.peek(), Some(&5)); -/// -/// // We can check the length of a heap. -/// assert_eq!(heap.len(), 3); -/// -/// // We can iterate over the items in the heap, although they are returned in -/// // a random order. -/// for x in &heap { -/// println!("{x}"); -/// } -/// -/// // If we instead pop these scores, they should come back in order. -/// assert_eq!(heap.pop(), Some(5)); -/// assert_eq!(heap.pop(), Some(2)); -/// assert_eq!(heap.pop(), Some(1)); -/// assert_eq!(heap.pop(), None); -/// -/// // We can clear the heap of any remaining items. -/// heap.clear(); -/// -/// // The heap should now be empty. -/// assert!(heap.is_empty()) -/// ``` -/// -/// A `BinaryHeap` with a known list of items can be initialized from an array: -/// -/// ``` -/// use std::collections::BinaryHeap; -/// -/// let heap = BinaryHeap::from([1, 5, 2]); -/// ``` -/// -/// ## Min-heap -/// -/// Either [`core::cmp::Reverse`] or a custom [`Ord`] implementation can be used to -/// make `BinaryHeap` a min-heap. This makes `heap.pop()` return the smallest -/// value instead of the greatest one. -/// -/// ``` -/// use std::collections::BinaryHeap; -/// use std::cmp::Reverse; -/// -/// let mut heap = BinaryHeap::new(); -/// -/// // Wrap values in `Reverse` -/// heap.push(Reverse(1)); -/// heap.push(Reverse(5)); -/// heap.push(Reverse(2)); -/// -/// // If we pop these scores now, they should come back in the reverse order. -/// assert_eq!(heap.pop(), Some(Reverse(1))); -/// assert_eq!(heap.pop(), Some(Reverse(2))); -/// assert_eq!(heap.pop(), Some(Reverse(5))); -/// assert_eq!(heap.pop(), None); -/// ``` -/// -/// # Time complexity -/// -/// | [push] | [pop] | [peek]/[peek\_mut] | -/// |---------|---------------|--------------------| -/// | *O*(1)~ | *O*(log(*n*)) | *O*(1) | -/// -/// The value for `push` is an expected cost; the method documentation gives a -/// more detailed analysis. -/// -/// [`core::cmp::Reverse`]: core::cmp::Reverse -/// [`Ord`]: core::cmp::Ord -/// [`Cell`]: core::cell::Cell -/// [`RefCell`]: core::cell::RefCell -/// [push]: BinaryHeap::push -/// [pop]: BinaryHeap::pop -/// [peek]: BinaryHeap::peek -/// [peek\_mut]: BinaryHeap::peek_mut -#[stable(feature = "rust1", since = "1.0.0")] -#[cfg_attr(not(test), rustc_diagnostic_item = "BinaryHeap")] -pub struct BinaryHeap { - data: Vec, -} - -/// Structure wrapping a mutable reference to the greatest item on a -/// `BinaryHeap`. -/// -/// This `struct` is created by the [`peek_mut`] method on [`BinaryHeap`]. See -/// its documentation for more. -/// -/// [`peek_mut`]: BinaryHeap::peek_mut -#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] -pub struct PeekMut<'a, T: 'a + Ord> { - heap: &'a mut BinaryHeap, - sift: bool, -} - -#[stable(feature = "collection_debug", since = "1.17.0")] -impl fmt::Debug for PeekMut<'_, T> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_tuple("PeekMut").field(&self.heap.data[0]).finish() - } -} - -#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] -impl Drop for PeekMut<'_, T> { - fn drop(&mut self) { - if self.sift { - // SAFETY: PeekMut is only instantiated for non-empty heaps. - unsafe { self.heap.sift_down(0) }; - } - } -} - -#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] -impl Deref for PeekMut<'_, T> { - type Target = T; - fn deref(&self) -> &T { - debug_assert!(!self.heap.is_empty()); - // SAFE: PeekMut is only instantiated for non-empty heaps - unsafe { self.heap.data.get_unchecked(0) } - } -} - -#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] -impl DerefMut for PeekMut<'_, T> { - fn deref_mut(&mut self) -> &mut T { - debug_assert!(!self.heap.is_empty()); - self.sift = true; - // SAFE: PeekMut is only instantiated for non-empty heaps - unsafe { self.heap.data.get_unchecked_mut(0) } - } -} - -impl<'a, T: Ord> PeekMut<'a, T> { - /// Removes the peeked value from the heap and returns it. - #[stable(feature = "binary_heap_peek_mut_pop", since = "1.18.0")] - pub fn pop(mut this: PeekMut<'a, T>) -> T { - let value = this.heap.pop().unwrap(); - this.sift = false; - value - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Clone for BinaryHeap { - fn clone(&self) -> Self { - BinaryHeap { data: self.data.clone() } - } - - fn clone_from(&mut self, source: &Self) { - self.data.clone_from(&source.data); - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Default for BinaryHeap { - /// Creates an empty `BinaryHeap`. - #[inline] - fn default() -> BinaryHeap { - BinaryHeap::new() - } -} - -#[stable(feature = "binaryheap_debug", since = "1.4.0")] -impl fmt::Debug for BinaryHeap { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self.iter()).finish() - } -} - -impl BinaryHeap { - /// Creates an empty `BinaryHeap` as a max-heap. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap = BinaryHeap::new(); - /// heap.push(4); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - #[must_use] - pub fn new() -> BinaryHeap { - BinaryHeap { data: vec![] } - } - - /// Creates an empty `BinaryHeap` with at least the specified capacity. - /// - /// The binary heap will be able to hold at least `capacity` elements without - /// reallocating. This method is allowed to allocate for more elements than - /// `capacity`. If `capacity` is 0, the binary heap will not allocate. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap = BinaryHeap::with_capacity(10); - /// heap.push(4); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - #[must_use] - pub fn with_capacity(capacity: usize) -> BinaryHeap { - BinaryHeap { data: Vec::with_capacity(capacity) } - } - - /// Returns a mutable reference to the greatest item in the binary heap, or - /// `None` if it is empty. - /// - /// Note: If the `PeekMut` value is leaked, the heap may be in an - /// inconsistent state. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap = BinaryHeap::new(); - /// assert!(heap.peek_mut().is_none()); - /// - /// heap.push(1); - /// heap.push(5); - /// heap.push(2); - /// { - /// let mut val = heap.peek_mut().unwrap(); - /// *val = 0; - /// } - /// assert_eq!(heap.peek(), Some(&2)); - /// ``` - /// - /// # Time complexity - /// - /// If the item is modified then the worst case time complexity is *O*(log(*n*)), - /// otherwise it's *O*(1). - #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] - pub fn peek_mut(&mut self) -> Option> { - if self.is_empty() { None } else { Some(PeekMut { heap: self, sift: false }) } - } - - /// Removes the greatest item from the binary heap and returns it, or `None` if it - /// is empty. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap = BinaryHeap::from([1, 3]); - /// - /// assert_eq!(heap.pop(), Some(3)); - /// assert_eq!(heap.pop(), Some(1)); - /// assert_eq!(heap.pop(), None); - /// ``` - /// - /// # Time complexity - /// - /// The worst case cost of `pop` on a heap containing *n* elements is *O*(log(*n*)). - #[stable(feature = "rust1", since = "1.0.0")] - pub fn pop(&mut self) -> Option { - self.data.pop().map(|mut item| { - if !self.is_empty() { - swap(&mut item, &mut self.data[0]); - // SAFETY: !self.is_empty() means that self.len() > 0 - unsafe { self.sift_down_to_bottom(0) }; - } - item - }) - } - - /// Pushes an item onto the binary heap. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap = BinaryHeap::new(); - /// heap.push(3); - /// heap.push(5); - /// heap.push(1); - /// - /// assert_eq!(heap.len(), 3); - /// assert_eq!(heap.peek(), Some(&5)); - /// ``` - /// - /// # Time complexity - /// - /// The expected cost of `push`, averaged over every possible ordering of - /// the elements being pushed, and over a sufficiently large number of - /// pushes, is *O*(1). This is the most meaningful cost metric when pushing - /// elements that are *not* already in any sorted pattern. - /// - /// The time complexity degrades if elements are pushed in predominantly - /// ascending order. In the worst case, elements are pushed in ascending - /// sorted order and the amortized cost per push is *O*(log(*n*)) against a heap - /// containing *n* elements. - /// - /// The worst case cost of a *single* call to `push` is *O*(*n*). The worst case - /// occurs when capacity is exhausted and needs a resize. The resize cost - /// has been amortized in the previous figures. - #[stable(feature = "rust1", since = "1.0.0")] - pub fn push(&mut self, item: T) { - let old_len = self.len(); - self.data.push(item); - // SAFETY: Since we pushed a new item it means that - // old_len = self.len() - 1 < self.len() - unsafe { self.sift_up(0, old_len) }; - } - - /// Consumes the `BinaryHeap` and returns a vector in sorted - /// (ascending) order. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// - /// let mut heap = BinaryHeap::from([1, 2, 4, 5, 7]); - /// heap.push(6); - /// heap.push(3); - /// - /// let vec = heap.into_sorted_vec(); - /// assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]); - /// ``` - #[must_use = "`self` will be dropped if the result is not used"] - #[stable(feature = "binary_heap_extras_15", since = "1.5.0")] - pub fn into_sorted_vec(mut self) -> Vec { - let mut end = self.len(); - while end > 1 { - end -= 1; - // SAFETY: `end` goes from `self.len() - 1` to 1 (both included), - // so it's always a valid index to access. - // It is safe to access index 0 (i.e. `ptr`), because - // 1 <= end < self.len(), which means self.len() >= 2. - unsafe { - let ptr = self.data.as_mut_ptr(); - ptr::swap(ptr, ptr.add(end)); - } - // SAFETY: `end` goes from `self.len() - 1` to 1 (both included) so: - // 0 < 1 <= end <= self.len() - 1 < self.len() - // Which means 0 < end and end < self.len(). - unsafe { self.sift_down_range(0, end) }; - } - self.into_vec() - } - - // The implementations of sift_up and sift_down use unsafe blocks in - // order to move an element out of the vector (leaving behind a - // hole), shift along the others and move the removed element back into the - // vector at the final location of the hole. - // The `Hole` type is used to represent this, and make sure - // the hole is filled back at the end of its scope, even on panic. - // Using a hole reduces the constant factor compared to using swaps, - // which involves twice as many moves. - - /// # Safety - /// - /// The caller must guarantee that `pos < self.len()`. - unsafe fn sift_up(&mut self, start: usize, pos: usize) -> usize { - // Take out the value at `pos` and create a hole. - // SAFETY: The caller guarantees that pos < self.len() - let mut hole = unsafe { Hole::new(&mut self.data, pos) }; - - while hole.pos() > start { - let parent = (hole.pos() - 1) / 2; - - // SAFETY: hole.pos() > start >= 0, which means hole.pos() > 0 - // and so hole.pos() - 1 can't underflow. - // This guarantees that parent < hole.pos() so - // it's a valid index and also != hole.pos(). - if hole.element() <= unsafe { hole.get(parent) } { - break; - } - - // SAFETY: Same as above - unsafe { hole.move_to(parent) }; - } - - hole.pos() - } - - /// Take an element at `pos` and move it down the heap, - /// while its children are larger. - /// - /// # Safety - /// - /// The caller must guarantee that `pos < end <= self.len()`. - unsafe fn sift_down_range(&mut self, pos: usize, end: usize) { - // SAFETY: The caller guarantees that pos < end <= self.len(). - let mut hole = unsafe { Hole::new(&mut self.data, pos) }; - let mut child = 2 * hole.pos() + 1; - - // Loop invariant: child == 2 * hole.pos() + 1. - while child <= end.saturating_sub(2) { - // compare with the greater of the two children - // SAFETY: child < end - 1 < self.len() and - // child + 1 < end <= self.len(), so they're valid indexes. - // child == 2 * hole.pos() + 1 != hole.pos() and - // child + 1 == 2 * hole.pos() + 2 != hole.pos(). - // FIXME: 2 * hole.pos() + 1 or 2 * hole.pos() + 2 could overflow - // if T is a ZST - child += unsafe { hole.get(child) <= hole.get(child + 1) } as usize; - - // if we are already in order, stop. - // SAFETY: child is now either the old child or the old child+1 - // We already proven that both are < self.len() and != hole.pos() - if hole.element() >= unsafe { hole.get(child) } { - return; - } - - // SAFETY: same as above. - unsafe { hole.move_to(child) }; - child = 2 * hole.pos() + 1; - } - - // SAFETY: && short circuit, which means that in the - // second condition it's already true that child == end - 1 < self.len(). - if child == end - 1 && hole.element() < unsafe { hole.get(child) } { - // SAFETY: child is already proven to be a valid index and - // child == 2 * hole.pos() + 1 != hole.pos(). - unsafe { hole.move_to(child) }; - } - } - - /// # Safety - /// - /// The caller must guarantee that `pos < self.len()`. - unsafe fn sift_down(&mut self, pos: usize) { - let len = self.len(); - // SAFETY: pos < len is guaranteed by the caller and - // obviously len = self.len() <= self.len(). - unsafe { self.sift_down_range(pos, len) }; - } - - /// Take an element at `pos` and move it all the way down the heap, - /// then sift it up to its position. - /// - /// Note: This is faster when the element is known to be large / should - /// be closer to the bottom. - /// - /// # Safety - /// - /// The caller must guarantee that `pos < self.len()`. - unsafe fn sift_down_to_bottom(&mut self, mut pos: usize) { - let end = self.len(); - let start = pos; - - // SAFETY: The caller guarantees that pos < self.len(). - let mut hole = unsafe { Hole::new(&mut self.data, pos) }; - let mut child = 2 * hole.pos() + 1; - - // Loop invariant: child == 2 * hole.pos() + 1. - while child <= end.saturating_sub(2) { - // SAFETY: child < end - 1 < self.len() and - // child + 1 < end <= self.len(), so they're valid indexes. - // child == 2 * hole.pos() + 1 != hole.pos() and - // child + 1 == 2 * hole.pos() + 2 != hole.pos(). - // FIXME: 2 * hole.pos() + 1 or 2 * hole.pos() + 2 could overflow - // if T is a ZST - child += unsafe { hole.get(child) <= hole.get(child + 1) } as usize; - - // SAFETY: Same as above - unsafe { hole.move_to(child) }; - child = 2 * hole.pos() + 1; - } - - if child == end - 1 { - // SAFETY: child == end - 1 < self.len(), so it's a valid index - // and child == 2 * hole.pos() + 1 != hole.pos(). - unsafe { hole.move_to(child) }; - } - pos = hole.pos(); - drop(hole); - - // SAFETY: pos is the position in the hole and was already proven - // to be a valid index. - unsafe { self.sift_up(start, pos) }; - } - - /// Rebuild assuming data[0..start] is still a proper heap. - fn rebuild_tail(&mut self, start: usize) { - if start == self.len() { - return; - } - - let tail_len = self.len() - start; - - #[inline(always)] - fn log2_fast(x: usize) -> usize { - (usize::BITS - x.leading_zeros() - 1) as usize - } - - // `rebuild` takes O(self.len()) operations - // and about 2 * self.len() comparisons in the worst case - // while repeating `sift_up` takes O(tail_len * log(start)) operations - // and about 1 * tail_len * log_2(start) comparisons in the worst case, - // assuming start >= tail_len. For larger heaps, the crossover point - // no longer follows this reasoning and was determined empirically. - let better_to_rebuild = if start < tail_len { - true - } else if self.len() <= 2048 { - 2 * self.len() < tail_len * log2_fast(start) - } else { - 2 * self.len() < tail_len * 11 - }; - - if better_to_rebuild { - self.rebuild(); - } else { - for i in start..self.len() { - // SAFETY: The index `i` is always less than self.len(). - unsafe { self.sift_up(0, i) }; - } - } - } - - fn rebuild(&mut self) { - let mut n = self.len() / 2; - while n > 0 { - n -= 1; - // SAFETY: n starts from self.len() / 2 and goes down to 0. - // The only case when !(n < self.len()) is if - // self.len() == 0, but it's ruled out by the loop condition. - unsafe { self.sift_down(n) }; - } - } - - /// Moves all the elements of `other` into `self`, leaving `other` empty. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// - /// let mut a = BinaryHeap::from([-10, 1, 2, 3, 3]); - /// let mut b = BinaryHeap::from([-20, 5, 43]); - /// - /// a.append(&mut b); - /// - /// assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]); - /// assert!(b.is_empty()); - /// ``` - #[stable(feature = "binary_heap_append", since = "1.11.0")] - pub fn append(&mut self, other: &mut Self) { - if self.len() < other.len() { - swap(self, other); - } - - let start = self.data.len(); - - self.data.append(&mut other.data); - - self.rebuild_tail(start); - } - - /// Clears the binary heap, returning an iterator over the removed elements - /// in heap order. If the iterator is dropped before being fully consumed, - /// it drops the remaining elements in heap order. - /// - /// The returned iterator keeps a mutable borrow on the heap to optimize - /// its implementation. - /// - /// Note: - /// * `.drain_sorted()` is *O*(*n* \* log(*n*)); much slower than `.drain()`. - /// You should use the latter for most cases. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// #![feature(binary_heap_drain_sorted)] - /// use std::collections::BinaryHeap; - /// - /// let mut heap = BinaryHeap::from([1, 2, 3, 4, 5]); - /// assert_eq!(heap.len(), 5); - /// - /// drop(heap.drain_sorted()); // removes all elements in heap order - /// assert_eq!(heap.len(), 0); - /// ``` - #[inline] - #[unstable(feature = "binary_heap_drain_sorted", issue = "59278")] - pub fn drain_sorted(&mut self) -> DrainSorted<'_, T> { - DrainSorted { inner: self } - } - - /// Retains only the elements specified by the predicate. - /// - /// In other words, remove all elements `e` for which `f(&e)` returns - /// `false`. The elements are visited in unsorted (and unspecified) order. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// #![feature(binary_heap_retain)] - /// use std::collections::BinaryHeap; - /// - /// let mut heap = BinaryHeap::from([-10, -5, 1, 2, 4, 13]); - /// - /// heap.retain(|x| x % 2 == 0); // only keep even numbers - /// - /// assert_eq!(heap.into_sorted_vec(), [-10, 2, 4]) - /// ``` - #[unstable(feature = "binary_heap_retain", issue = "71503")] - pub fn retain(&mut self, mut f: F) - where - F: FnMut(&T) -> bool, - { - let mut first_removed = self.len(); - let mut i = 0; - self.data.retain(|e| { - let keep = f(e); - if !keep && i < first_removed { - first_removed = i; - } - i += 1; - keep - }); - // data[0..first_removed] is untouched, so we only need to rebuild the tail: - self.rebuild_tail(first_removed); - } -} - -impl BinaryHeap { - /// Returns an iterator visiting all values in the underlying vector, in - /// arbitrary order. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let heap = BinaryHeap::from([1, 2, 3, 4]); - /// - /// // Print 1, 2, 3, 4 in arbitrary order - /// for x in heap.iter() { - /// println!("{x}"); - /// } - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn iter(&self) -> Iter<'_, T> { - Iter { iter: self.data.iter() } - } - - /// Returns an iterator which retrieves elements in heap order. - /// This method consumes the original heap. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// #![feature(binary_heap_into_iter_sorted)] - /// use std::collections::BinaryHeap; - /// let heap = BinaryHeap::from([1, 2, 3, 4, 5]); - /// - /// assert_eq!(heap.into_iter_sorted().take(2).collect::>(), [5, 4]); - /// ``` - #[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")] - pub fn into_iter_sorted(self) -> IntoIterSorted { - IntoIterSorted { inner: self } - } - - /// Returns the greatest item in the binary heap, or `None` if it is empty. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap = BinaryHeap::new(); - /// assert_eq!(heap.peek(), None); - /// - /// heap.push(1); - /// heap.push(5); - /// heap.push(2); - /// assert_eq!(heap.peek(), Some(&5)); - /// - /// ``` - /// - /// # Time complexity - /// - /// Cost is *O*(1) in the worst case. - #[must_use] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn peek(&self) -> Option<&T> { - self.data.get(0) - } - - /// Returns the number of elements the binary heap can hold without reallocating. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap = BinaryHeap::with_capacity(100); - /// assert!(heap.capacity() >= 100); - /// heap.push(4); - /// ``` - #[must_use] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn capacity(&self) -> usize { - self.data.capacity() - } - - /// Reserves the minimum capacity for at least `additional` elements more than - /// the current length. Unlike [`reserve`], this will not - /// deliberately over-allocate to speculatively avoid frequent allocations. - /// After calling `reserve_exact`, capacity will be greater than or equal to - /// `self.len() + additional`. Does nothing if the capacity is already - /// sufficient. - /// - /// [`reserve`]: BinaryHeap::reserve - /// - /// # Panics - /// - /// Panics if the new capacity overflows [`usize`]. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap = BinaryHeap::new(); - /// heap.reserve_exact(100); - /// assert!(heap.capacity() >= 100); - /// heap.push(4); - /// ``` - /// - /// [`reserve`]: BinaryHeap::reserve - #[stable(feature = "rust1", since = "1.0.0")] - pub fn reserve_exact(&mut self, additional: usize) { - self.data.reserve_exact(additional); - } - - /// Reserves capacity for at least `additional` elements more than the - /// current length. The allocator may reserve more space to speculatively - /// avoid frequent allocations. After calling `reserve`, - /// capacity will be greater than or equal to `self.len() + additional`. - /// Does nothing if capacity is already sufficient. - /// - /// # Panics - /// - /// Panics if the new capacity overflows [`usize`]. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap = BinaryHeap::new(); - /// heap.reserve(100); - /// assert!(heap.capacity() >= 100); - /// heap.push(4); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn reserve(&mut self, additional: usize) { - self.data.reserve(additional); - } - - /// Tries to reserve the minimum capacity for at least `additional` elements - /// more than the current length. Unlike [`try_reserve`], this will not - /// deliberately over-allocate to speculatively avoid frequent allocations. - /// After calling `try_reserve_exact`, capacity will be greater than or - /// equal to `self.len() + additional` if it returns `Ok(())`. - /// Does nothing if the capacity is already sufficient. - /// - /// Note that the allocator may give the collection more space than it - /// requests. Therefore, capacity can not be relied upon to be precisely - /// minimal. Prefer [`try_reserve`] if future insertions are expected. - /// - /// [`try_reserve`]: BinaryHeap::try_reserve - /// - /// # Errors - /// - /// If the capacity overflows, or the allocator reports a failure, then an error - /// is returned. - /// - /// # Examples - /// - /// ``` - /// use std::collections::BinaryHeap; - /// use std::collections::TryReserveError; - /// - /// fn find_max_slow(data: &[u32]) -> Result, TryReserveError> { - /// let mut heap = BinaryHeap::new(); - /// - /// // Pre-reserve the memory, exiting if we can't - /// heap.try_reserve_exact(data.len())?; - /// - /// // Now we know this can't OOM in the middle of our complex work - /// heap.extend(data.iter()); - /// - /// Ok(heap.pop()) - /// } - /// # find_max_slow(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?"); - /// ``` - #[stable(feature = "try_reserve_2", since = "1.63.0")] - pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { - self.data.try_reserve_exact(additional) - } - - /// Tries to reserve capacity for at least `additional` elements more than the - /// current length. The allocator may reserve more space to speculatively - /// avoid frequent allocations. After calling `try_reserve`, capacity will be - /// greater than or equal to `self.len() + additional` if it returns - /// `Ok(())`. Does nothing if capacity is already sufficient. This method - /// preserves the contents even if an error occurs. - /// - /// # Errors - /// - /// If the capacity overflows, or the allocator reports a failure, then an error - /// is returned. - /// - /// # Examples - /// - /// ``` - /// use std::collections::BinaryHeap; - /// use std::collections::TryReserveError; - /// - /// fn find_max_slow(data: &[u32]) -> Result, TryReserveError> { - /// let mut heap = BinaryHeap::new(); - /// - /// // Pre-reserve the memory, exiting if we can't - /// heap.try_reserve(data.len())?; - /// - /// // Now we know this can't OOM in the middle of our complex work - /// heap.extend(data.iter()); - /// - /// Ok(heap.pop()) - /// } - /// # find_max_slow(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?"); - /// ``` - #[stable(feature = "try_reserve_2", since = "1.63.0")] - pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { - self.data.try_reserve(additional) - } - - /// Discards as much additional capacity as possible. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap: BinaryHeap = BinaryHeap::with_capacity(100); - /// - /// assert!(heap.capacity() >= 100); - /// heap.shrink_to_fit(); - /// assert!(heap.capacity() == 0); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn shrink_to_fit(&mut self) { - self.data.shrink_to_fit(); - } - - /// Discards capacity with a lower bound. - /// - /// The capacity will remain at least as large as both the length - /// and the supplied value. - /// - /// If the current capacity is less than the lower limit, this is a no-op. - /// - /// # Examples - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap: BinaryHeap = BinaryHeap::with_capacity(100); - /// - /// assert!(heap.capacity() >= 100); - /// heap.shrink_to(10); - /// assert!(heap.capacity() >= 10); - /// ``` - #[inline] - #[stable(feature = "shrink_to", since = "1.56.0")] - pub fn shrink_to(&mut self, min_capacity: usize) { - self.data.shrink_to(min_capacity) - } - - /// Returns a slice of all values in the underlying vector, in arbitrary - /// order. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// #![feature(binary_heap_as_slice)] - /// use std::collections::BinaryHeap; - /// use std::io::{self, Write}; - /// - /// let heap = BinaryHeap::from([1, 2, 3, 4, 5, 6, 7]); - /// - /// io::sink().write(heap.as_slice()).unwrap(); - /// ``` - #[must_use] - #[unstable(feature = "binary_heap_as_slice", issue = "83659")] - pub fn as_slice(&self) -> &[T] { - self.data.as_slice() - } - - /// Consumes the `BinaryHeap` and returns the underlying vector - /// in arbitrary order. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let heap = BinaryHeap::from([1, 2, 3, 4, 5, 6, 7]); - /// let vec = heap.into_vec(); - /// - /// // Will print in some order - /// for x in vec { - /// println!("{x}"); - /// } - /// ``` - #[must_use = "`self` will be dropped if the result is not used"] - #[stable(feature = "binary_heap_extras_15", since = "1.5.0")] - pub fn into_vec(self) -> Vec { - self.into() - } - - /// Returns the length of the binary heap. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let heap = BinaryHeap::from([1, 3]); - /// - /// assert_eq!(heap.len(), 2); - /// ``` - #[must_use] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn len(&self) -> usize { - self.data.len() - } - - /// Checks if the binary heap is empty. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap = BinaryHeap::new(); - /// - /// assert!(heap.is_empty()); - /// - /// heap.push(3); - /// heap.push(5); - /// heap.push(1); - /// - /// assert!(!heap.is_empty()); - /// ``` - #[must_use] - #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_empty(&self) -> bool { - self.len() == 0 - } - - /// Clears the binary heap, returning an iterator over the removed elements - /// in arbitrary order. If the iterator is dropped before being fully - /// consumed, it drops the remaining elements in arbitrary order. - /// - /// The returned iterator keeps a mutable borrow on the heap to optimize - /// its implementation. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap = BinaryHeap::from([1, 3]); - /// - /// assert!(!heap.is_empty()); - /// - /// for x in heap.drain() { - /// println!("{x}"); - /// } - /// - /// assert!(heap.is_empty()); - /// ``` - #[inline] - #[stable(feature = "drain", since = "1.6.0")] - pub fn drain(&mut self) -> Drain<'_, T> { - Drain { iter: self.data.drain(..) } - } - - /// Drops all items from the binary heap. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let mut heap = BinaryHeap::from([1, 3]); - /// - /// assert!(!heap.is_empty()); - /// - /// heap.clear(); - /// - /// assert!(heap.is_empty()); - /// ``` - #[stable(feature = "rust1", since = "1.0.0")] - pub fn clear(&mut self) { - self.drain(); - } -} - -/// Hole represents a hole in a slice i.e., an index without valid value -/// (because it was moved from or duplicated). -/// In drop, `Hole` will restore the slice by filling the hole -/// position with the value that was originally removed. -struct Hole<'a, T: 'a> { - data: &'a mut [T], - elt: ManuallyDrop, - pos: usize, -} - -impl<'a, T> Hole<'a, T> { - /// Create a new `Hole` at index `pos`. - /// - /// Unsafe because pos must be within the data slice. - #[inline] - unsafe fn new(data: &'a mut [T], pos: usize) -> Self { - debug_assert!(pos < data.len()); - // SAFE: pos should be inside the slice - let elt = unsafe { ptr::read(data.get_unchecked(pos)) }; - Hole { data, elt: ManuallyDrop::new(elt), pos } - } - - #[inline] - fn pos(&self) -> usize { - self.pos - } - - /// Returns a reference to the element removed. - #[inline] - fn element(&self) -> &T { - &self.elt - } - - /// Returns a reference to the element at `index`. - /// - /// Unsafe because index must be within the data slice and not equal to pos. - #[inline] - unsafe fn get(&self, index: usize) -> &T { - debug_assert!(index != self.pos); - debug_assert!(index < self.data.len()); - unsafe { self.data.get_unchecked(index) } - } - - /// Move hole to new location - /// - /// Unsafe because index must be within the data slice and not equal to pos. - #[inline] - unsafe fn move_to(&mut self, index: usize) { - debug_assert!(index != self.pos); - debug_assert!(index < self.data.len()); - unsafe { - let ptr = self.data.as_mut_ptr(); - let index_ptr: *const _ = ptr.add(index); - let hole_ptr = ptr.add(self.pos); - ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1); - } - self.pos = index; - } -} - -impl Drop for Hole<'_, T> { - #[inline] - fn drop(&mut self) { - // fill the hole again - unsafe { - let pos = self.pos; - ptr::copy_nonoverlapping(&*self.elt, self.data.get_unchecked_mut(pos), 1); - } - } -} - -/// An iterator over the elements of a `BinaryHeap`. -/// -/// This `struct` is created by [`BinaryHeap::iter()`]. See its -/// documentation for more. -/// -/// [`iter`]: BinaryHeap::iter -#[must_use = "iterators are lazy and do nothing unless consumed"] -#[stable(feature = "rust1", since = "1.0.0")] -pub struct Iter<'a, T: 'a> { - iter: slice::Iter<'a, T>, -} - -#[stable(feature = "collection_debug", since = "1.17.0")] -impl fmt::Debug for Iter<'_, T> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_tuple("Iter").field(&self.iter.as_slice()).finish() - } -} - -// FIXME(#26925) Remove in favor of `#[derive(Clone)]` -#[stable(feature = "rust1", since = "1.0.0")] -impl Clone for Iter<'_, T> { - fn clone(&self) -> Self { - Iter { iter: self.iter.clone() } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T> Iterator for Iter<'a, T> { - type Item = &'a T; - - #[inline] - fn next(&mut self) -> Option<&'a T> { - self.iter.next() - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - self.iter.size_hint() - } - - #[inline] - fn last(self) -> Option<&'a T> { - self.iter.last() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T> DoubleEndedIterator for Iter<'a, T> { - #[inline] - fn next_back(&mut self) -> Option<&'a T> { - self.iter.next_back() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl ExactSizeIterator for Iter<'_, T> { - fn is_empty(&self) -> bool { - self.iter.is_empty() - } -} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for Iter<'_, T> {} - -/// An owning iterator over the elements of a `BinaryHeap`. -/// -/// This `struct` is created by [`BinaryHeap::into_iter()`] -/// (provided by the [`IntoIterator`] trait). See its documentation for more. -/// -/// [`into_iter`]: BinaryHeap::into_iter -/// [`IntoIterator`]: core::iter::IntoIterator -#[stable(feature = "rust1", since = "1.0.0")] -#[derive(Clone)] -pub struct IntoIter { - iter: vec::IntoIter, -} - -#[stable(feature = "collection_debug", since = "1.17.0")] -impl fmt::Debug for IntoIter { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_tuple("IntoIter").field(&self.iter.as_slice()).finish() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Iterator for IntoIter { - type Item = T; - - #[inline] - fn next(&mut self) -> Option { - self.iter.next() - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - self.iter.size_hint() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl DoubleEndedIterator for IntoIter { - #[inline] - fn next_back(&mut self) -> Option { - self.iter.next_back() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl ExactSizeIterator for IntoIter { - fn is_empty(&self) -> bool { - self.iter.is_empty() - } -} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for IntoIter {} - -// In addition to the SAFETY invariants of the following three unsafe traits -// also refer to the vec::in_place_collect module documentation to get an overview -#[unstable(issue = "none", feature = "inplace_iteration")] -#[doc(hidden)] -unsafe impl SourceIter for IntoIter { - type Source = IntoIter; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut Self::Source { - self - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -#[doc(hidden)] -unsafe impl InPlaceIterable for IntoIter {} - -unsafe impl AsVecIntoIter for IntoIter { - type Item = I; - - fn as_into_iter(&mut self) -> &mut vec::IntoIter { - &mut self.iter - } -} - -#[must_use = "iterators are lazy and do nothing unless consumed"] -#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")] -#[derive(Clone, Debug)] -pub struct IntoIterSorted { - inner: BinaryHeap, -} - -#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")] -impl Iterator for IntoIterSorted { - type Item = T; - - #[inline] - fn next(&mut self) -> Option { - self.inner.pop() - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - let exact = self.inner.len(); - (exact, Some(exact)) - } -} - -#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")] -impl ExactSizeIterator for IntoIterSorted {} - -#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")] -impl FusedIterator for IntoIterSorted {} - -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl TrustedLen for IntoIterSorted {} - -/// A draining iterator over the elements of a `BinaryHeap`. -/// -/// This `struct` is created by [`BinaryHeap::drain()`]. See its -/// documentation for more. -/// -/// [`drain`]: BinaryHeap::drain -#[stable(feature = "drain", since = "1.6.0")] -#[derive(Debug)] -pub struct Drain<'a, T: 'a> { - iter: vec::Drain<'a, T>, -} - -#[stable(feature = "drain", since = "1.6.0")] -impl Iterator for Drain<'_, T> { - type Item = T; - - #[inline] - fn next(&mut self) -> Option { - self.iter.next() - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - self.iter.size_hint() - } -} - -#[stable(feature = "drain", since = "1.6.0")] -impl DoubleEndedIterator for Drain<'_, T> { - #[inline] - fn next_back(&mut self) -> Option { - self.iter.next_back() - } -} - -#[stable(feature = "drain", since = "1.6.0")] -impl ExactSizeIterator for Drain<'_, T> { - fn is_empty(&self) -> bool { - self.iter.is_empty() - } -} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for Drain<'_, T> {} - -/// A draining iterator over the elements of a `BinaryHeap`. -/// -/// This `struct` is created by [`BinaryHeap::drain_sorted()`]. See its -/// documentation for more. -/// -/// [`drain_sorted`]: BinaryHeap::drain_sorted -#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")] -#[derive(Debug)] -pub struct DrainSorted<'a, T: Ord> { - inner: &'a mut BinaryHeap, -} - -#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")] -impl<'a, T: Ord> Drop for DrainSorted<'a, T> { - /// Removes heap elements in heap order. - fn drop(&mut self) { - struct DropGuard<'r, 'a, T: Ord>(&'r mut DrainSorted<'a, T>); - - impl<'r, 'a, T: Ord> Drop for DropGuard<'r, 'a, T> { - fn drop(&mut self) { - while self.0.inner.pop().is_some() {} - } - } - - while let Some(item) = self.inner.pop() { - let guard = DropGuard(self); - drop(item); - mem::forget(guard); - } - } -} - -#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")] -impl Iterator for DrainSorted<'_, T> { - type Item = T; - - #[inline] - fn next(&mut self) -> Option { - self.inner.pop() - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - let exact = self.inner.len(); - (exact, Some(exact)) - } -} - -#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")] -impl ExactSizeIterator for DrainSorted<'_, T> {} - -#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")] -impl FusedIterator for DrainSorted<'_, T> {} - -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl TrustedLen for DrainSorted<'_, T> {} - -#[stable(feature = "binary_heap_extras_15", since = "1.5.0")] -impl From> for BinaryHeap { - /// Converts a `Vec` into a `BinaryHeap`. - /// - /// This conversion happens in-place, and has *O*(*n*) time complexity. - fn from(vec: Vec) -> BinaryHeap { - let mut heap = BinaryHeap { data: vec }; - heap.rebuild(); - heap - } -} - -#[stable(feature = "std_collections_from_array", since = "1.56.0")] -impl From<[T; N]> for BinaryHeap { - /// ``` - /// use std::collections::BinaryHeap; - /// - /// let mut h1 = BinaryHeap::from([1, 4, 2, 3]); - /// let mut h2: BinaryHeap<_> = [1, 4, 2, 3].into(); - /// while let Some((a, b)) = h1.pop().zip(h2.pop()) { - /// assert_eq!(a, b); - /// } - /// ``` - fn from(arr: [T; N]) -> Self { - Self::from_iter(arr) - } -} - -#[stable(feature = "binary_heap_extras_15", since = "1.5.0")] -impl From> for Vec { - /// Converts a `BinaryHeap` into a `Vec`. - /// - /// This conversion requires no data movement or allocation, and has - /// constant time complexity. - fn from(heap: BinaryHeap) -> Vec { - heap.data - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl FromIterator for BinaryHeap { - fn from_iter>(iter: I) -> BinaryHeap { - BinaryHeap::from(iter.into_iter().collect::>()) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl IntoIterator for BinaryHeap { - type Item = T; - type IntoIter = IntoIter; - - /// Creates a consuming iterator, that is, one that moves each value out of - /// the binary heap in arbitrary order. The binary heap cannot be used - /// after calling this. - /// - /// # Examples - /// - /// Basic usage: - /// - /// ``` - /// use std::collections::BinaryHeap; - /// let heap = BinaryHeap::from([1, 2, 3, 4]); - /// - /// // Print 1, 2, 3, 4 in arbitrary order - /// for x in heap.into_iter() { - /// // x has type i32, not &i32 - /// println!("{x}"); - /// } - /// ``` - fn into_iter(self) -> IntoIter { - IntoIter { iter: self.data.into_iter() } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T> IntoIterator for &'a BinaryHeap { - type Item = &'a T; - type IntoIter = Iter<'a, T>; - - fn into_iter(self) -> Iter<'a, T> { - self.iter() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Extend for BinaryHeap { - #[inline] - fn extend>(&mut self, iter: I) { - >::spec_extend(self, iter); - } - - #[inline] - fn extend_one(&mut self, item: T) { - self.push(item); - } - - #[inline] - fn extend_reserve(&mut self, additional: usize) { - self.reserve(additional); - } -} - -impl> SpecExtend for BinaryHeap { - default fn spec_extend(&mut self, iter: I) { - self.extend_desugared(iter.into_iter()); - } -} - -impl SpecExtend> for BinaryHeap { - fn spec_extend(&mut self, ref mut other: Vec) { - let start = self.data.len(); - self.data.append(other); - self.rebuild_tail(start); - } -} - -impl SpecExtend> for BinaryHeap { - fn spec_extend(&mut self, ref mut other: BinaryHeap) { - self.append(other); - } -} - -impl BinaryHeap { - fn extend_desugared>(&mut self, iter: I) { - let iterator = iter.into_iter(); - let (lower, _) = iterator.size_hint(); - - self.reserve(lower); - - iterator.for_each(move |elem| self.push(elem)); - } -} - -#[stable(feature = "extend_ref", since = "1.2.0")] -impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BinaryHeap { - fn extend>(&mut self, iter: I) { - self.extend(iter.into_iter().cloned()); - } - - #[inline] - fn extend_one(&mut self, &item: &'a T) { - self.push(item); - } - - #[inline] - fn extend_reserve(&mut self, additional: usize) { - self.reserve(additional); - } -} diff --git a/library/alloc/src/collections/binary_heap/mod.rs b/library/alloc/src/collections/binary_heap/mod.rs new file mode 100644 index 000000000..0b73b1af4 --- /dev/null +++ b/library/alloc/src/collections/binary_heap/mod.rs @@ -0,0 +1,1766 @@ +//! A priority queue implemented with a binary heap. +//! +//! Insertion and popping the largest element have *O*(log(*n*)) time complexity. +//! Checking the largest element is *O*(1). Converting a vector to a binary heap +//! can be done in-place, and has *O*(*n*) complexity. A binary heap can also be +//! converted to a sorted vector in-place, allowing it to be used for an *O*(*n* * log(*n*)) +//! in-place heapsort. +//! +//! # Examples +//! +//! This is a larger example that implements [Dijkstra's algorithm][dijkstra] +//! to solve the [shortest path problem][sssp] on a [directed graph][dir_graph]. +//! It shows how to use [`BinaryHeap`] with custom types. +//! +//! [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 +//! +//! ``` +//! use std::cmp::Ordering; +//! use std::collections::BinaryHeap; +//! +//! #[derive(Copy, Clone, Eq, PartialEq)] +//! struct State { +//! cost: usize, +//! position: usize, +//! } +//! +//! // The priority queue depends on `Ord`. +//! // Explicitly implement the trait so the queue becomes a min-heap +//! // instead of a max-heap. +//! impl Ord for State { +//! fn cmp(&self, other: &Self) -> Ordering { +//! // Notice that the we flip the ordering on costs. +//! // In case of a tie we compare positions - this step is necessary +//! // to make implementations of `PartialEq` and `Ord` consistent. +//! other.cost.cmp(&self.cost) +//! .then_with(|| self.position.cmp(&other.position)) +//! } +//! } +//! +//! // `PartialOrd` needs to be implemented as well. +//! impl PartialOrd for State { +//! fn partial_cmp(&self, other: &Self) -> Option { +//! Some(self.cmp(other)) +//! } +//! } +//! +//! // Each node is represented as a `usize`, for a shorter implementation. +//! struct Edge { +//! node: usize, +//! cost: usize, +//! } +//! +//! // Dijkstra's shortest path algorithm. +//! +//! // Start at `start` and use `dist` to track the current shortest distance +//! // to each node. This implementation isn't memory-efficient as it may leave duplicate +//! // nodes in the queue. It also uses `usize::MAX` as a sentinel value, +//! // for a simpler implementation. +//! fn shortest_path(adj_list: &Vec>, start: usize, goal: usize) -> Option { +//! // dist[node] = current shortest distance from `start` to `node` +//! let mut dist: Vec<_> = (0..adj_list.len()).map(|_| usize::MAX).collect(); +//! +//! let mut heap = BinaryHeap::new(); +//! +//! // We're at `start`, with a zero cost +//! dist[start] = 0; +//! heap.push(State { cost: 0, position: start }); +//! +//! // Examine the frontier with lower cost nodes first (min-heap) +//! while let Some(State { cost, position }) = heap.pop() { +//! // Alternatively we could have continued to find all shortest paths +//! if position == goal { return Some(cost); } +//! +//! // Important as we may have already found a better way +//! if cost > dist[position] { continue; } +//! +//! // For each node we can reach, see if we can find a way with +//! // a lower cost going through this node +//! for edge in &adj_list[position] { +//! let next = State { cost: cost + edge.cost, position: edge.node }; +//! +//! // If so, add it to the frontier and continue +//! if next.cost < dist[next.position] { +//! heap.push(next); +//! // Relaxation, we have now found a better way +//! dist[next.position] = next.cost; +//! } +//! } +//! } +//! +//! // Goal not reachable +//! None +//! } +//! +//! fn main() { +//! // This is the directed graph we're going to use. +//! // The node numbers correspond to the different states, +//! // and the edge weights symbolize the cost of moving +//! // from one node to another. +//! // Note that the edges are one-way. +//! // +//! // 7 +//! // +-----------------+ +//! // | | +//! // v 1 2 | 2 +//! // 0 -----> 1 -----> 3 ---> 4 +//! // | ^ ^ ^ +//! // | | 1 | | +//! // | | | 3 | 1 +//! // +------> 2 -------+ | +//! // 10 | | +//! // +---------------+ +//! // +//! // The graph is represented as an adjacency list where each index, +//! // corresponding to a node value, has a list of outgoing edges. +//! // Chosen for its efficiency. +//! let graph = vec![ +//! // Node 0 +//! vec![Edge { node: 2, cost: 10 }, +//! Edge { node: 1, cost: 1 }], +//! // Node 1 +//! vec![Edge { node: 3, cost: 2 }], +//! // Node 2 +//! vec![Edge { node: 1, cost: 1 }, +//! Edge { node: 3, cost: 3 }, +//! Edge { node: 4, cost: 1 }], +//! // Node 3 +//! vec![Edge { node: 0, cost: 7 }, +//! Edge { node: 4, cost: 2 }], +//! // Node 4 +//! vec![]]; +//! +//! assert_eq!(shortest_path(&graph, 0, 1), Some(1)); +//! assert_eq!(shortest_path(&graph, 0, 3), Some(3)); +//! assert_eq!(shortest_path(&graph, 3, 0), Some(7)); +//! assert_eq!(shortest_path(&graph, 0, 4), Some(5)); +//! assert_eq!(shortest_path(&graph, 4, 0), None); +//! } +//! ``` + +#![allow(missing_docs)] +#![stable(feature = "rust1", since = "1.0.0")] + +use core::fmt; +use core::iter::{FromIterator, FusedIterator, InPlaceIterable, SourceIter, TrustedLen}; +use core::mem::{self, swap, ManuallyDrop}; +use core::num::NonZeroUsize; +use core::ops::{Deref, DerefMut}; +use core::ptr; + +use crate::collections::TryReserveError; +use crate::slice; +use crate::vec::{self, AsVecIntoIter, Vec}; + +use super::SpecExtend; + +#[cfg(test)] +mod tests; + +/// A priority queue implemented with a binary heap. +/// +/// This will be a max-heap. +/// +/// It is a logic error for an item to be modified in such a way that the +/// item's ordering relative to any other item, as determined by the [`Ord`] +/// trait, changes while it is in the heap. This is normally only possible +/// through interior mutability, global state, I/O, or unsafe code. The +/// behavior resulting from such a logic error is not specified, but will +/// be encapsulated to the `BinaryHeap` that observed the logic error and not +/// result in undefined behavior. This could include panics, incorrect results, +/// aborts, memory leaks, and non-termination. +/// +/// As long as no elements change their relative order while being in the heap +/// as described above, the API of `BinaryHeap` guarantees that the heap +/// invariant remains intact i.e. its methods all behave as documented. For +/// example if a method is documented as iterating in sorted order, that's +/// guaranteed to work as long as elements in the heap have not changed order, +/// even in the presence of closures getting unwinded out of, iterators getting +/// leaked, and similar foolishness. +/// +/// # Examples +/// +/// ``` +/// use std::collections::BinaryHeap; +/// +/// // Type inference lets us omit an explicit type signature (which +/// // would be `BinaryHeap` in this example). +/// let mut heap = BinaryHeap::new(); +/// +/// // We can use peek to look at the next item in the heap. In this case, +/// // there's no items in there yet so we get None. +/// assert_eq!(heap.peek(), None); +/// +/// // Let's add some scores... +/// heap.push(1); +/// heap.push(5); +/// heap.push(2); +/// +/// // Now peek shows the most important item in the heap. +/// assert_eq!(heap.peek(), Some(&5)); +/// +/// // We can check the length of a heap. +/// assert_eq!(heap.len(), 3); +/// +/// // We can iterate over the items in the heap, although they are returned in +/// // a random order. +/// for x in &heap { +/// println!("{x}"); +/// } +/// +/// // If we instead pop these scores, they should come back in order. +/// assert_eq!(heap.pop(), Some(5)); +/// assert_eq!(heap.pop(), Some(2)); +/// assert_eq!(heap.pop(), Some(1)); +/// assert_eq!(heap.pop(), None); +/// +/// // We can clear the heap of any remaining items. +/// heap.clear(); +/// +/// // The heap should now be empty. +/// assert!(heap.is_empty()) +/// ``` +/// +/// A `BinaryHeap` with a known list of items can be initialized from an array: +/// +/// ``` +/// use std::collections::BinaryHeap; +/// +/// let heap = BinaryHeap::from([1, 5, 2]); +/// ``` +/// +/// ## Min-heap +/// +/// Either [`core::cmp::Reverse`] or a custom [`Ord`] implementation can be used to +/// make `BinaryHeap` a min-heap. This makes `heap.pop()` return the smallest +/// value instead of the greatest one. +/// +/// ``` +/// use std::collections::BinaryHeap; +/// use std::cmp::Reverse; +/// +/// let mut heap = BinaryHeap::new(); +/// +/// // Wrap values in `Reverse` +/// heap.push(Reverse(1)); +/// heap.push(Reverse(5)); +/// heap.push(Reverse(2)); +/// +/// // If we pop these scores now, they should come back in the reverse order. +/// assert_eq!(heap.pop(), Some(Reverse(1))); +/// assert_eq!(heap.pop(), Some(Reverse(2))); +/// assert_eq!(heap.pop(), Some(Reverse(5))); +/// assert_eq!(heap.pop(), None); +/// ``` +/// +/// # Time complexity +/// +/// | [push] | [pop] | [peek]/[peek\_mut] | +/// |---------|---------------|--------------------| +/// | *O*(1)~ | *O*(log(*n*)) | *O*(1) | +/// +/// The value for `push` is an expected cost; the method documentation gives a +/// more detailed analysis. +/// +/// [`core::cmp::Reverse`]: core::cmp::Reverse +/// [`Ord`]: core::cmp::Ord +/// [`Cell`]: core::cell::Cell +/// [`RefCell`]: core::cell::RefCell +/// [push]: BinaryHeap::push +/// [pop]: BinaryHeap::pop +/// [peek]: BinaryHeap::peek +/// [peek\_mut]: BinaryHeap::peek_mut +#[stable(feature = "rust1", since = "1.0.0")] +#[cfg_attr(not(test), rustc_diagnostic_item = "BinaryHeap")] +pub struct BinaryHeap { + data: Vec, +} + +/// Structure wrapping a mutable reference to the greatest item on a +/// `BinaryHeap`. +/// +/// This `struct` is created by the [`peek_mut`] method on [`BinaryHeap`]. See +/// its documentation for more. +/// +/// [`peek_mut`]: BinaryHeap::peek_mut +#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] +pub struct PeekMut<'a, T: 'a + Ord> { + heap: &'a mut BinaryHeap, + // If a set_len + sift_down are required, this is Some. If a &mut T has not + // yet been exposed to peek_mut()'s caller, it's None. + original_len: Option, +} + +#[stable(feature = "collection_debug", since = "1.17.0")] +impl fmt::Debug for PeekMut<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("PeekMut").field(&self.heap.data[0]).finish() + } +} + +#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] +impl Drop for PeekMut<'_, T> { + fn drop(&mut self) { + if let Some(original_len) = self.original_len { + // SAFETY: That's how many elements were in the Vec at the time of + // the PeekMut::deref_mut call, and therefore also at the time of + // the BinaryHeap::peek_mut call. Since the PeekMut did not end up + // getting leaked, we are now undoing the leak amplification that + // the DerefMut prepared for. + unsafe { self.heap.data.set_len(original_len.get()) }; + + // SAFETY: PeekMut is only instantiated for non-empty heaps. + unsafe { self.heap.sift_down(0) }; + } + } +} + +#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] +impl Deref for PeekMut<'_, T> { + type Target = T; + fn deref(&self) -> &T { + debug_assert!(!self.heap.is_empty()); + // SAFE: PeekMut is only instantiated for non-empty heaps + unsafe { self.heap.data.get_unchecked(0) } + } +} + +#[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] +impl DerefMut for PeekMut<'_, T> { + fn deref_mut(&mut self) -> &mut T { + debug_assert!(!self.heap.is_empty()); + + let len = self.heap.len(); + if len > 1 { + // Here we preemptively leak all the rest of the underlying vector + // after the currently max element. If the caller mutates the &mut T + // we're about to give them, and then leaks the PeekMut, all these + // elements will remain leaked. If they don't leak the PeekMut, then + // either Drop or PeekMut::pop will un-leak the vector elements. + // + // This is technique is described throughout several other places in + // the standard library as "leak amplification". + unsafe { + // SAFETY: len > 1 so len != 0. + self.original_len = Some(NonZeroUsize::new_unchecked(len)); + // SAFETY: len > 1 so all this does for now is leak elements, + // which is safe. + self.heap.data.set_len(1); + } + } + + // SAFE: PeekMut is only instantiated for non-empty heaps + unsafe { self.heap.data.get_unchecked_mut(0) } + } +} + +impl<'a, T: Ord> PeekMut<'a, T> { + /// Removes the peeked value from the heap and returns it. + #[stable(feature = "binary_heap_peek_mut_pop", since = "1.18.0")] + pub fn pop(mut this: PeekMut<'a, T>) -> T { + if let Some(original_len) = this.original_len.take() { + // SAFETY: This is how many elements were in the Vec at the time of + // the BinaryHeap::peek_mut call. + unsafe { this.heap.data.set_len(original_len.get()) }; + + // Unlike in Drop, here we don't also need to do a sift_down even if + // the caller could've mutated the element. It is removed from the + // heap on the next line and pop() is not sensitive to its value. + } + this.heap.pop().unwrap() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Clone for BinaryHeap { + fn clone(&self) -> Self { + BinaryHeap { data: self.data.clone() } + } + + fn clone_from(&mut self, source: &Self) { + self.data.clone_from(&source.data); + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Default for BinaryHeap { + /// Creates an empty `BinaryHeap`. + #[inline] + fn default() -> BinaryHeap { + BinaryHeap::new() + } +} + +#[stable(feature = "binaryheap_debug", since = "1.4.0")] +impl fmt::Debug for BinaryHeap { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.iter()).finish() + } +} + +impl BinaryHeap { + /// Creates an empty `BinaryHeap` as a max-heap. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap = BinaryHeap::new(); + /// heap.push(4); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + #[must_use] + pub fn new() -> BinaryHeap { + BinaryHeap { data: vec![] } + } + + /// Creates an empty `BinaryHeap` with at least the specified capacity. + /// + /// The binary heap will be able to hold at least `capacity` elements without + /// reallocating. This method is allowed to allocate for more elements than + /// `capacity`. If `capacity` is 0, the binary heap will not allocate. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap = BinaryHeap::with_capacity(10); + /// heap.push(4); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + #[must_use] + pub fn with_capacity(capacity: usize) -> BinaryHeap { + BinaryHeap { data: Vec::with_capacity(capacity) } + } + + /// Returns a mutable reference to the greatest item in the binary heap, or + /// `None` if it is empty. + /// + /// Note: If the `PeekMut` value is leaked, some heap elements might get + /// leaked along with it, but the remaining elements will remain a valid + /// heap. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap = BinaryHeap::new(); + /// assert!(heap.peek_mut().is_none()); + /// + /// heap.push(1); + /// heap.push(5); + /// heap.push(2); + /// { + /// let mut val = heap.peek_mut().unwrap(); + /// *val = 0; + /// } + /// assert_eq!(heap.peek(), Some(&2)); + /// ``` + /// + /// # Time complexity + /// + /// If the item is modified then the worst case time complexity is *O*(log(*n*)), + /// otherwise it's *O*(1). + #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] + pub fn peek_mut(&mut self) -> Option> { + if self.is_empty() { None } else { Some(PeekMut { heap: self, original_len: None }) } + } + + /// Removes the greatest item from the binary heap and returns it, or `None` if it + /// is empty. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap = BinaryHeap::from([1, 3]); + /// + /// assert_eq!(heap.pop(), Some(3)); + /// assert_eq!(heap.pop(), Some(1)); + /// assert_eq!(heap.pop(), None); + /// ``` + /// + /// # Time complexity + /// + /// The worst case cost of `pop` on a heap containing *n* elements is *O*(log(*n*)). + #[stable(feature = "rust1", since = "1.0.0")] + pub fn pop(&mut self) -> Option { + self.data.pop().map(|mut item| { + if !self.is_empty() { + swap(&mut item, &mut self.data[0]); + // SAFETY: !self.is_empty() means that self.len() > 0 + unsafe { self.sift_down_to_bottom(0) }; + } + item + }) + } + + /// Pushes an item onto the binary heap. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap = BinaryHeap::new(); + /// heap.push(3); + /// heap.push(5); + /// heap.push(1); + /// + /// assert_eq!(heap.len(), 3); + /// assert_eq!(heap.peek(), Some(&5)); + /// ``` + /// + /// # Time complexity + /// + /// The expected cost of `push`, averaged over every possible ordering of + /// the elements being pushed, and over a sufficiently large number of + /// pushes, is *O*(1). This is the most meaningful cost metric when pushing + /// elements that are *not* already in any sorted pattern. + /// + /// The time complexity degrades if elements are pushed in predominantly + /// ascending order. In the worst case, elements are pushed in ascending + /// sorted order and the amortized cost per push is *O*(log(*n*)) against a heap + /// containing *n* elements. + /// + /// The worst case cost of a *single* call to `push` is *O*(*n*). The worst case + /// occurs when capacity is exhausted and needs a resize. The resize cost + /// has been amortized in the previous figures. + #[stable(feature = "rust1", since = "1.0.0")] + pub fn push(&mut self, item: T) { + let old_len = self.len(); + self.data.push(item); + // SAFETY: Since we pushed a new item it means that + // old_len = self.len() - 1 < self.len() + unsafe { self.sift_up(0, old_len) }; + } + + /// Consumes the `BinaryHeap` and returns a vector in sorted + /// (ascending) order. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// + /// let mut heap = BinaryHeap::from([1, 2, 4, 5, 7]); + /// heap.push(6); + /// heap.push(3); + /// + /// let vec = heap.into_sorted_vec(); + /// assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]); + /// ``` + #[must_use = "`self` will be dropped if the result is not used"] + #[stable(feature = "binary_heap_extras_15", since = "1.5.0")] + pub fn into_sorted_vec(mut self) -> Vec { + let mut end = self.len(); + while end > 1 { + end -= 1; + // SAFETY: `end` goes from `self.len() - 1` to 1 (both included), + // so it's always a valid index to access. + // It is safe to access index 0 (i.e. `ptr`), because + // 1 <= end < self.len(), which means self.len() >= 2. + unsafe { + let ptr = self.data.as_mut_ptr(); + ptr::swap(ptr, ptr.add(end)); + } + // SAFETY: `end` goes from `self.len() - 1` to 1 (both included) so: + // 0 < 1 <= end <= self.len() - 1 < self.len() + // Which means 0 < end and end < self.len(). + unsafe { self.sift_down_range(0, end) }; + } + self.into_vec() + } + + // The implementations of sift_up and sift_down use unsafe blocks in + // order to move an element out of the vector (leaving behind a + // hole), shift along the others and move the removed element back into the + // vector at the final location of the hole. + // The `Hole` type is used to represent this, and make sure + // the hole is filled back at the end of its scope, even on panic. + // Using a hole reduces the constant factor compared to using swaps, + // which involves twice as many moves. + + /// # Safety + /// + /// The caller must guarantee that `pos < self.len()`. + unsafe fn sift_up(&mut self, start: usize, pos: usize) -> usize { + // Take out the value at `pos` and create a hole. + // SAFETY: The caller guarantees that pos < self.len() + let mut hole = unsafe { Hole::new(&mut self.data, pos) }; + + while hole.pos() > start { + let parent = (hole.pos() - 1) / 2; + + // SAFETY: hole.pos() > start >= 0, which means hole.pos() > 0 + // and so hole.pos() - 1 can't underflow. + // This guarantees that parent < hole.pos() so + // it's a valid index and also != hole.pos(). + if hole.element() <= unsafe { hole.get(parent) } { + break; + } + + // SAFETY: Same as above + unsafe { hole.move_to(parent) }; + } + + hole.pos() + } + + /// Take an element at `pos` and move it down the heap, + /// while its children are larger. + /// + /// # Safety + /// + /// The caller must guarantee that `pos < end <= self.len()`. + unsafe fn sift_down_range(&mut self, pos: usize, end: usize) { + // SAFETY: The caller guarantees that pos < end <= self.len(). + let mut hole = unsafe { Hole::new(&mut self.data, pos) }; + let mut child = 2 * hole.pos() + 1; + + // Loop invariant: child == 2 * hole.pos() + 1. + while child <= end.saturating_sub(2) { + // compare with the greater of the two children + // SAFETY: child < end - 1 < self.len() and + // child + 1 < end <= self.len(), so they're valid indexes. + // child == 2 * hole.pos() + 1 != hole.pos() and + // child + 1 == 2 * hole.pos() + 2 != hole.pos(). + // FIXME: 2 * hole.pos() + 1 or 2 * hole.pos() + 2 could overflow + // if T is a ZST + child += unsafe { hole.get(child) <= hole.get(child + 1) } as usize; + + // if we are already in order, stop. + // SAFETY: child is now either the old child or the old child+1 + // We already proven that both are < self.len() and != hole.pos() + if hole.element() >= unsafe { hole.get(child) } { + return; + } + + // SAFETY: same as above. + unsafe { hole.move_to(child) }; + child = 2 * hole.pos() + 1; + } + + // SAFETY: && short circuit, which means that in the + // second condition it's already true that child == end - 1 < self.len(). + if child == end - 1 && hole.element() < unsafe { hole.get(child) } { + // SAFETY: child is already proven to be a valid index and + // child == 2 * hole.pos() + 1 != hole.pos(). + unsafe { hole.move_to(child) }; + } + } + + /// # Safety + /// + /// The caller must guarantee that `pos < self.len()`. + unsafe fn sift_down(&mut self, pos: usize) { + let len = self.len(); + // SAFETY: pos < len is guaranteed by the caller and + // obviously len = self.len() <= self.len(). + unsafe { self.sift_down_range(pos, len) }; + } + + /// Take an element at `pos` and move it all the way down the heap, + /// then sift it up to its position. + /// + /// Note: This is faster when the element is known to be large / should + /// be closer to the bottom. + /// + /// # Safety + /// + /// The caller must guarantee that `pos < self.len()`. + unsafe fn sift_down_to_bottom(&mut self, mut pos: usize) { + let end = self.len(); + let start = pos; + + // SAFETY: The caller guarantees that pos < self.len(). + let mut hole = unsafe { Hole::new(&mut self.data, pos) }; + let mut child = 2 * hole.pos() + 1; + + // Loop invariant: child == 2 * hole.pos() + 1. + while child <= end.saturating_sub(2) { + // SAFETY: child < end - 1 < self.len() and + // child + 1 < end <= self.len(), so they're valid indexes. + // child == 2 * hole.pos() + 1 != hole.pos() and + // child + 1 == 2 * hole.pos() + 2 != hole.pos(). + // FIXME: 2 * hole.pos() + 1 or 2 * hole.pos() + 2 could overflow + // if T is a ZST + child += unsafe { hole.get(child) <= hole.get(child + 1) } as usize; + + // SAFETY: Same as above + unsafe { hole.move_to(child) }; + child = 2 * hole.pos() + 1; + } + + if child == end - 1 { + // SAFETY: child == end - 1 < self.len(), so it's a valid index + // and child == 2 * hole.pos() + 1 != hole.pos(). + unsafe { hole.move_to(child) }; + } + pos = hole.pos(); + drop(hole); + + // SAFETY: pos is the position in the hole and was already proven + // to be a valid index. + unsafe { self.sift_up(start, pos) }; + } + + /// Rebuild assuming data[0..start] is still a proper heap. + fn rebuild_tail(&mut self, start: usize) { + if start == self.len() { + return; + } + + let tail_len = self.len() - start; + + #[inline(always)] + fn log2_fast(x: usize) -> usize { + (usize::BITS - x.leading_zeros() - 1) as usize + } + + // `rebuild` takes O(self.len()) operations + // and about 2 * self.len() comparisons in the worst case + // while repeating `sift_up` takes O(tail_len * log(start)) operations + // and about 1 * tail_len * log_2(start) comparisons in the worst case, + // assuming start >= tail_len. For larger heaps, the crossover point + // no longer follows this reasoning and was determined empirically. + let better_to_rebuild = if start < tail_len { + true + } else if self.len() <= 2048 { + 2 * self.len() < tail_len * log2_fast(start) + } else { + 2 * self.len() < tail_len * 11 + }; + + if better_to_rebuild { + self.rebuild(); + } else { + for i in start..self.len() { + // SAFETY: The index `i` is always less than self.len(). + unsafe { self.sift_up(0, i) }; + } + } + } + + fn rebuild(&mut self) { + let mut n = self.len() / 2; + while n > 0 { + n -= 1; + // SAFETY: n starts from self.len() / 2 and goes down to 0. + // The only case when !(n < self.len()) is if + // self.len() == 0, but it's ruled out by the loop condition. + unsafe { self.sift_down(n) }; + } + } + + /// Moves all the elements of `other` into `self`, leaving `other` empty. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// + /// let mut a = BinaryHeap::from([-10, 1, 2, 3, 3]); + /// let mut b = BinaryHeap::from([-20, 5, 43]); + /// + /// a.append(&mut b); + /// + /// assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]); + /// assert!(b.is_empty()); + /// ``` + #[stable(feature = "binary_heap_append", since = "1.11.0")] + pub fn append(&mut self, other: &mut Self) { + if self.len() < other.len() { + swap(self, other); + } + + let start = self.data.len(); + + self.data.append(&mut other.data); + + self.rebuild_tail(start); + } + + /// Clears the binary heap, returning an iterator over the removed elements + /// in heap order. If the iterator is dropped before being fully consumed, + /// it drops the remaining elements in heap order. + /// + /// The returned iterator keeps a mutable borrow on the heap to optimize + /// its implementation. + /// + /// Note: + /// * `.drain_sorted()` is *O*(*n* \* log(*n*)); much slower than `.drain()`. + /// You should use the latter for most cases. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(binary_heap_drain_sorted)] + /// use std::collections::BinaryHeap; + /// + /// let mut heap = BinaryHeap::from([1, 2, 3, 4, 5]); + /// assert_eq!(heap.len(), 5); + /// + /// drop(heap.drain_sorted()); // removes all elements in heap order + /// assert_eq!(heap.len(), 0); + /// ``` + #[inline] + #[unstable(feature = "binary_heap_drain_sorted", issue = "59278")] + pub fn drain_sorted(&mut self) -> DrainSorted<'_, T> { + DrainSorted { inner: self } + } + + /// Retains only the elements specified by the predicate. + /// + /// In other words, remove all elements `e` for which `f(&e)` returns + /// `false`. The elements are visited in unsorted (and unspecified) order. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(binary_heap_retain)] + /// use std::collections::BinaryHeap; + /// + /// let mut heap = BinaryHeap::from([-10, -5, 1, 2, 4, 13]); + /// + /// heap.retain(|x| x % 2 == 0); // only keep even numbers + /// + /// assert_eq!(heap.into_sorted_vec(), [-10, 2, 4]) + /// ``` + #[unstable(feature = "binary_heap_retain", issue = "71503")] + pub fn retain(&mut self, mut f: F) + where + F: FnMut(&T) -> bool, + { + let mut first_removed = self.len(); + let mut i = 0; + self.data.retain(|e| { + let keep = f(e); + if !keep && i < first_removed { + first_removed = i; + } + i += 1; + keep + }); + // data[0..first_removed] is untouched, so we only need to rebuild the tail: + self.rebuild_tail(first_removed); + } +} + +impl BinaryHeap { + /// Returns an iterator visiting all values in the underlying vector, in + /// arbitrary order. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let heap = BinaryHeap::from([1, 2, 3, 4]); + /// + /// // Print 1, 2, 3, 4 in arbitrary order + /// for x in heap.iter() { + /// println!("{x}"); + /// } + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn iter(&self) -> Iter<'_, T> { + Iter { iter: self.data.iter() } + } + + /// Returns an iterator which retrieves elements in heap order. + /// This method consumes the original heap. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(binary_heap_into_iter_sorted)] + /// use std::collections::BinaryHeap; + /// let heap = BinaryHeap::from([1, 2, 3, 4, 5]); + /// + /// assert_eq!(heap.into_iter_sorted().take(2).collect::>(), [5, 4]); + /// ``` + #[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")] + pub fn into_iter_sorted(self) -> IntoIterSorted { + IntoIterSorted { inner: self } + } + + /// Returns the greatest item in the binary heap, or `None` if it is empty. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap = BinaryHeap::new(); + /// assert_eq!(heap.peek(), None); + /// + /// heap.push(1); + /// heap.push(5); + /// heap.push(2); + /// assert_eq!(heap.peek(), Some(&5)); + /// + /// ``` + /// + /// # Time complexity + /// + /// Cost is *O*(1) in the worst case. + #[must_use] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn peek(&self) -> Option<&T> { + self.data.get(0) + } + + /// Returns the number of elements the binary heap can hold without reallocating. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap = BinaryHeap::with_capacity(100); + /// assert!(heap.capacity() >= 100); + /// heap.push(4); + /// ``` + #[must_use] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn capacity(&self) -> usize { + self.data.capacity() + } + + /// Reserves the minimum capacity for at least `additional` elements more than + /// the current length. Unlike [`reserve`], this will not + /// deliberately over-allocate to speculatively avoid frequent allocations. + /// After calling `reserve_exact`, capacity will be greater than or equal to + /// `self.len() + additional`. Does nothing if the capacity is already + /// sufficient. + /// + /// [`reserve`]: BinaryHeap::reserve + /// + /// # Panics + /// + /// Panics if the new capacity overflows [`usize`]. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap = BinaryHeap::new(); + /// heap.reserve_exact(100); + /// assert!(heap.capacity() >= 100); + /// heap.push(4); + /// ``` + /// + /// [`reserve`]: BinaryHeap::reserve + #[stable(feature = "rust1", since = "1.0.0")] + pub fn reserve_exact(&mut self, additional: usize) { + self.data.reserve_exact(additional); + } + + /// Reserves capacity for at least `additional` elements more than the + /// current length. The allocator may reserve more space to speculatively + /// avoid frequent allocations. After calling `reserve`, + /// capacity will be greater than or equal to `self.len() + additional`. + /// Does nothing if capacity is already sufficient. + /// + /// # Panics + /// + /// Panics if the new capacity overflows [`usize`]. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap = BinaryHeap::new(); + /// heap.reserve(100); + /// assert!(heap.capacity() >= 100); + /// heap.push(4); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn reserve(&mut self, additional: usize) { + self.data.reserve(additional); + } + + /// Tries to reserve the minimum capacity for at least `additional` elements + /// more than the current length. Unlike [`try_reserve`], this will not + /// deliberately over-allocate to speculatively avoid frequent allocations. + /// After calling `try_reserve_exact`, capacity will be greater than or + /// equal to `self.len() + additional` if it returns `Ok(())`. + /// Does nothing if the capacity is already sufficient. + /// + /// Note that the allocator may give the collection more space than it + /// requests. Therefore, capacity can not be relied upon to be precisely + /// minimal. Prefer [`try_reserve`] if future insertions are expected. + /// + /// [`try_reserve`]: BinaryHeap::try_reserve + /// + /// # Errors + /// + /// If the capacity overflows, or the allocator reports a failure, then an error + /// is returned. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BinaryHeap; + /// use std::collections::TryReserveError; + /// + /// fn find_max_slow(data: &[u32]) -> Result, TryReserveError> { + /// let mut heap = BinaryHeap::new(); + /// + /// // Pre-reserve the memory, exiting if we can't + /// heap.try_reserve_exact(data.len())?; + /// + /// // Now we know this can't OOM in the middle of our complex work + /// heap.extend(data.iter()); + /// + /// Ok(heap.pop()) + /// } + /// # find_max_slow(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?"); + /// ``` + #[stable(feature = "try_reserve_2", since = "1.63.0")] + pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.data.try_reserve_exact(additional) + } + + /// Tries to reserve capacity for at least `additional` elements more than the + /// current length. The allocator may reserve more space to speculatively + /// avoid frequent allocations. After calling `try_reserve`, capacity will be + /// greater than or equal to `self.len() + additional` if it returns + /// `Ok(())`. Does nothing if capacity is already sufficient. This method + /// preserves the contents even if an error occurs. + /// + /// # Errors + /// + /// If the capacity overflows, or the allocator reports a failure, then an error + /// is returned. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BinaryHeap; + /// use std::collections::TryReserveError; + /// + /// fn find_max_slow(data: &[u32]) -> Result, TryReserveError> { + /// let mut heap = BinaryHeap::new(); + /// + /// // Pre-reserve the memory, exiting if we can't + /// heap.try_reserve(data.len())?; + /// + /// // Now we know this can't OOM in the middle of our complex work + /// heap.extend(data.iter()); + /// + /// Ok(heap.pop()) + /// } + /// # find_max_slow(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?"); + /// ``` + #[stable(feature = "try_reserve_2", since = "1.63.0")] + pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.data.try_reserve(additional) + } + + /// Discards as much additional capacity as possible. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap: BinaryHeap = BinaryHeap::with_capacity(100); + /// + /// assert!(heap.capacity() >= 100); + /// heap.shrink_to_fit(); + /// assert!(heap.capacity() == 0); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn shrink_to_fit(&mut self) { + self.data.shrink_to_fit(); + } + + /// Discards capacity with a lower bound. + /// + /// The capacity will remain at least as large as both the length + /// and the supplied value. + /// + /// If the current capacity is less than the lower limit, this is a no-op. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap: BinaryHeap = BinaryHeap::with_capacity(100); + /// + /// assert!(heap.capacity() >= 100); + /// heap.shrink_to(10); + /// assert!(heap.capacity() >= 10); + /// ``` + #[inline] + #[stable(feature = "shrink_to", since = "1.56.0")] + pub fn shrink_to(&mut self, min_capacity: usize) { + self.data.shrink_to(min_capacity) + } + + /// Returns a slice of all values in the underlying vector, in arbitrary + /// order. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// #![feature(binary_heap_as_slice)] + /// use std::collections::BinaryHeap; + /// use std::io::{self, Write}; + /// + /// let heap = BinaryHeap::from([1, 2, 3, 4, 5, 6, 7]); + /// + /// io::sink().write(heap.as_slice()).unwrap(); + /// ``` + #[must_use] + #[unstable(feature = "binary_heap_as_slice", issue = "83659")] + pub fn as_slice(&self) -> &[T] { + self.data.as_slice() + } + + /// Consumes the `BinaryHeap` and returns the underlying vector + /// in arbitrary order. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let heap = BinaryHeap::from([1, 2, 3, 4, 5, 6, 7]); + /// let vec = heap.into_vec(); + /// + /// // Will print in some order + /// for x in vec { + /// println!("{x}"); + /// } + /// ``` + #[must_use = "`self` will be dropped if the result is not used"] + #[stable(feature = "binary_heap_extras_15", since = "1.5.0")] + pub fn into_vec(self) -> Vec { + self.into() + } + + /// Returns the length of the binary heap. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let heap = BinaryHeap::from([1, 3]); + /// + /// assert_eq!(heap.len(), 2); + /// ``` + #[must_use] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn len(&self) -> usize { + self.data.len() + } + + /// Checks if the binary heap is empty. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap = BinaryHeap::new(); + /// + /// assert!(heap.is_empty()); + /// + /// heap.push(3); + /// heap.push(5); + /// heap.push(1); + /// + /// assert!(!heap.is_empty()); + /// ``` + #[must_use] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// Clears the binary heap, returning an iterator over the removed elements + /// in arbitrary order. If the iterator is dropped before being fully + /// consumed, it drops the remaining elements in arbitrary order. + /// + /// The returned iterator keeps a mutable borrow on the heap to optimize + /// its implementation. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap = BinaryHeap::from([1, 3]); + /// + /// assert!(!heap.is_empty()); + /// + /// for x in heap.drain() { + /// println!("{x}"); + /// } + /// + /// assert!(heap.is_empty()); + /// ``` + #[inline] + #[stable(feature = "drain", since = "1.6.0")] + pub fn drain(&mut self) -> Drain<'_, T> { + Drain { iter: self.data.drain(..) } + } + + /// Drops all items from the binary heap. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let mut heap = BinaryHeap::from([1, 3]); + /// + /// assert!(!heap.is_empty()); + /// + /// heap.clear(); + /// + /// assert!(heap.is_empty()); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn clear(&mut self) { + self.drain(); + } +} + +/// Hole represents a hole in a slice i.e., an index without valid value +/// (because it was moved from or duplicated). +/// In drop, `Hole` will restore the slice by filling the hole +/// position with the value that was originally removed. +struct Hole<'a, T: 'a> { + data: &'a mut [T], + elt: ManuallyDrop, + pos: usize, +} + +impl<'a, T> Hole<'a, T> { + /// Create a new `Hole` at index `pos`. + /// + /// Unsafe because pos must be within the data slice. + #[inline] + unsafe fn new(data: &'a mut [T], pos: usize) -> Self { + debug_assert!(pos < data.len()); + // SAFE: pos should be inside the slice + let elt = unsafe { ptr::read(data.get_unchecked(pos)) }; + Hole { data, elt: ManuallyDrop::new(elt), pos } + } + + #[inline] + fn pos(&self) -> usize { + self.pos + } + + /// Returns a reference to the element removed. + #[inline] + fn element(&self) -> &T { + &self.elt + } + + /// Returns a reference to the element at `index`. + /// + /// Unsafe because index must be within the data slice and not equal to pos. + #[inline] + unsafe fn get(&self, index: usize) -> &T { + debug_assert!(index != self.pos); + debug_assert!(index < self.data.len()); + unsafe { self.data.get_unchecked(index) } + } + + /// Move hole to new location + /// + /// Unsafe because index must be within the data slice and not equal to pos. + #[inline] + unsafe fn move_to(&mut self, index: usize) { + debug_assert!(index != self.pos); + debug_assert!(index < self.data.len()); + unsafe { + let ptr = self.data.as_mut_ptr(); + let index_ptr: *const _ = ptr.add(index); + let hole_ptr = ptr.add(self.pos); + ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1); + } + self.pos = index; + } +} + +impl Drop for Hole<'_, T> { + #[inline] + fn drop(&mut self) { + // fill the hole again + unsafe { + let pos = self.pos; + ptr::copy_nonoverlapping(&*self.elt, self.data.get_unchecked_mut(pos), 1); + } + } +} + +/// An iterator over the elements of a `BinaryHeap`. +/// +/// This `struct` is created by [`BinaryHeap::iter()`]. See its +/// documentation for more. +/// +/// [`iter`]: BinaryHeap::iter +#[must_use = "iterators are lazy and do nothing unless consumed"] +#[stable(feature = "rust1", since = "1.0.0")] +pub struct Iter<'a, T: 'a> { + iter: slice::Iter<'a, T>, +} + +#[stable(feature = "collection_debug", since = "1.17.0")] +impl fmt::Debug for Iter<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("Iter").field(&self.iter.as_slice()).finish() + } +} + +// FIXME(#26925) Remove in favor of `#[derive(Clone)]` +#[stable(feature = "rust1", since = "1.0.0")] +impl Clone for Iter<'_, T> { + fn clone(&self) -> Self { + Iter { iter: self.iter.clone() } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T> Iterator for Iter<'a, T> { + type Item = &'a T; + + #[inline] + fn next(&mut self) -> Option<&'a T> { + self.iter.next() + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + #[inline] + fn last(self) -> Option<&'a T> { + self.iter.last() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T> DoubleEndedIterator for Iter<'a, T> { + #[inline] + fn next_back(&mut self) -> Option<&'a T> { + self.iter.next_back() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl ExactSizeIterator for Iter<'_, T> { + fn is_empty(&self) -> bool { + self.iter.is_empty() + } +} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for Iter<'_, T> {} + +/// An owning iterator over the elements of a `BinaryHeap`. +/// +/// This `struct` is created by [`BinaryHeap::into_iter()`] +/// (provided by the [`IntoIterator`] trait). See its documentation for more. +/// +/// [`into_iter`]: BinaryHeap::into_iter +/// [`IntoIterator`]: core::iter::IntoIterator +#[stable(feature = "rust1", since = "1.0.0")] +#[derive(Clone)] +pub struct IntoIter { + iter: vec::IntoIter, +} + +#[stable(feature = "collection_debug", since = "1.17.0")] +impl fmt::Debug for IntoIter { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("IntoIter").field(&self.iter.as_slice()).finish() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Iterator for IntoIter { + type Item = T; + + #[inline] + fn next(&mut self) -> Option { + self.iter.next() + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl DoubleEndedIterator for IntoIter { + #[inline] + fn next_back(&mut self) -> Option { + self.iter.next_back() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl ExactSizeIterator for IntoIter { + fn is_empty(&self) -> bool { + self.iter.is_empty() + } +} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for IntoIter {} + +// In addition to the SAFETY invariants of the following three unsafe traits +// also refer to the vec::in_place_collect module documentation to get an overview +#[unstable(issue = "none", feature = "inplace_iteration")] +#[doc(hidden)] +unsafe impl SourceIter for IntoIter { + type Source = IntoIter; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut Self::Source { + self + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +#[doc(hidden)] +unsafe impl InPlaceIterable for IntoIter {} + +unsafe impl AsVecIntoIter for IntoIter { + type Item = I; + + fn as_into_iter(&mut self) -> &mut vec::IntoIter { + &mut self.iter + } +} + +#[must_use = "iterators are lazy and do nothing unless consumed"] +#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")] +#[derive(Clone, Debug)] +pub struct IntoIterSorted { + inner: BinaryHeap, +} + +#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")] +impl Iterator for IntoIterSorted { + type Item = T; + + #[inline] + fn next(&mut self) -> Option { + self.inner.pop() + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let exact = self.inner.len(); + (exact, Some(exact)) + } +} + +#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")] +impl ExactSizeIterator for IntoIterSorted {} + +#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")] +impl FusedIterator for IntoIterSorted {} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for IntoIterSorted {} + +/// A draining iterator over the elements of a `BinaryHeap`. +/// +/// This `struct` is created by [`BinaryHeap::drain()`]. See its +/// documentation for more. +/// +/// [`drain`]: BinaryHeap::drain +#[stable(feature = "drain", since = "1.6.0")] +#[derive(Debug)] +pub struct Drain<'a, T: 'a> { + iter: vec::Drain<'a, T>, +} + +#[stable(feature = "drain", since = "1.6.0")] +impl Iterator for Drain<'_, T> { + type Item = T; + + #[inline] + fn next(&mut self) -> Option { + self.iter.next() + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } +} + +#[stable(feature = "drain", since = "1.6.0")] +impl DoubleEndedIterator for Drain<'_, T> { + #[inline] + fn next_back(&mut self) -> Option { + self.iter.next_back() + } +} + +#[stable(feature = "drain", since = "1.6.0")] +impl ExactSizeIterator for Drain<'_, T> { + fn is_empty(&self) -> bool { + self.iter.is_empty() + } +} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for Drain<'_, T> {} + +/// A draining iterator over the elements of a `BinaryHeap`. +/// +/// This `struct` is created by [`BinaryHeap::drain_sorted()`]. See its +/// documentation for more. +/// +/// [`drain_sorted`]: BinaryHeap::drain_sorted +#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")] +#[derive(Debug)] +pub struct DrainSorted<'a, T: Ord> { + inner: &'a mut BinaryHeap, +} + +#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")] +impl<'a, T: Ord> Drop for DrainSorted<'a, T> { + /// Removes heap elements in heap order. + fn drop(&mut self) { + struct DropGuard<'r, 'a, T: Ord>(&'r mut DrainSorted<'a, T>); + + impl<'r, 'a, T: Ord> Drop for DropGuard<'r, 'a, T> { + fn drop(&mut self) { + while self.0.inner.pop().is_some() {} + } + } + + while let Some(item) = self.inner.pop() { + let guard = DropGuard(self); + drop(item); + mem::forget(guard); + } + } +} + +#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")] +impl Iterator for DrainSorted<'_, T> { + type Item = T; + + #[inline] + fn next(&mut self) -> Option { + self.inner.pop() + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let exact = self.inner.len(); + (exact, Some(exact)) + } +} + +#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")] +impl ExactSizeIterator for DrainSorted<'_, T> {} + +#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")] +impl FusedIterator for DrainSorted<'_, T> {} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for DrainSorted<'_, T> {} + +#[stable(feature = "binary_heap_extras_15", since = "1.5.0")] +impl From> for BinaryHeap { + /// Converts a `Vec` into a `BinaryHeap`. + /// + /// This conversion happens in-place, and has *O*(*n*) time complexity. + fn from(vec: Vec) -> BinaryHeap { + let mut heap = BinaryHeap { data: vec }; + heap.rebuild(); + heap + } +} + +#[stable(feature = "std_collections_from_array", since = "1.56.0")] +impl From<[T; N]> for BinaryHeap { + /// ``` + /// use std::collections::BinaryHeap; + /// + /// let mut h1 = BinaryHeap::from([1, 4, 2, 3]); + /// let mut h2: BinaryHeap<_> = [1, 4, 2, 3].into(); + /// while let Some((a, b)) = h1.pop().zip(h2.pop()) { + /// assert_eq!(a, b); + /// } + /// ``` + fn from(arr: [T; N]) -> Self { + Self::from_iter(arr) + } +} + +#[stable(feature = "binary_heap_extras_15", since = "1.5.0")] +impl From> for Vec { + /// Converts a `BinaryHeap` into a `Vec`. + /// + /// This conversion requires no data movement or allocation, and has + /// constant time complexity. + fn from(heap: BinaryHeap) -> Vec { + heap.data + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl FromIterator for BinaryHeap { + fn from_iter>(iter: I) -> BinaryHeap { + BinaryHeap::from(iter.into_iter().collect::>()) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl IntoIterator for BinaryHeap { + type Item = T; + type IntoIter = IntoIter; + + /// Creates a consuming iterator, that is, one that moves each value out of + /// the binary heap in arbitrary order. The binary heap cannot be used + /// after calling this. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BinaryHeap; + /// let heap = BinaryHeap::from([1, 2, 3, 4]); + /// + /// // Print 1, 2, 3, 4 in arbitrary order + /// for x in heap.into_iter() { + /// // x has type i32, not &i32 + /// println!("{x}"); + /// } + /// ``` + fn into_iter(self) -> IntoIter { + IntoIter { iter: self.data.into_iter() } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T> IntoIterator for &'a BinaryHeap { + type Item = &'a T; + type IntoIter = Iter<'a, T>; + + fn into_iter(self) -> Iter<'a, T> { + self.iter() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Extend for BinaryHeap { + #[inline] + fn extend>(&mut self, iter: I) { + >::spec_extend(self, iter); + } + + #[inline] + fn extend_one(&mut self, item: T) { + self.push(item); + } + + #[inline] + fn extend_reserve(&mut self, additional: usize) { + self.reserve(additional); + } +} + +impl> SpecExtend for BinaryHeap { + default fn spec_extend(&mut self, iter: I) { + self.extend_desugared(iter.into_iter()); + } +} + +impl SpecExtend> for BinaryHeap { + fn spec_extend(&mut self, ref mut other: Vec) { + let start = self.data.len(); + self.data.append(other); + self.rebuild_tail(start); + } +} + +impl SpecExtend> for BinaryHeap { + fn spec_extend(&mut self, ref mut other: BinaryHeap) { + self.append(other); + } +} + +impl BinaryHeap { + fn extend_desugared>(&mut self, iter: I) { + let iterator = iter.into_iter(); + let (lower, _) = iterator.size_hint(); + + self.reserve(lower); + + iterator.for_each(move |elem| self.push(elem)); + } +} + +#[stable(feature = "extend_ref", since = "1.2.0")] +impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BinaryHeap { + fn extend>(&mut self, iter: I) { + self.extend(iter.into_iter().cloned()); + } + + #[inline] + fn extend_one(&mut self, &item: &'a T) { + self.push(item); + } + + #[inline] + fn extend_reserve(&mut self, additional: usize) { + self.reserve(additional); + } +} diff --git a/library/alloc/src/collections/binary_heap/tests.rs b/library/alloc/src/collections/binary_heap/tests.rs index 5a05215ae..ffbb6c80a 100644 --- a/library/alloc/src/collections/binary_heap/tests.rs +++ b/library/alloc/src/collections/binary_heap/tests.rs @@ -1,8 +1,9 @@ use super::*; use crate::boxed::Box; +use crate::testing::crash_test::{CrashTestDummy, Panic}; +use core::mem; use std::iter::TrustedLen; use std::panic::{catch_unwind, AssertUnwindSafe}; -use std::sync::atomic::{AtomicU32, Ordering}; #[test] fn test_iterator() { @@ -146,6 +147,24 @@ fn test_peek_mut() { assert_eq!(heap.peek(), Some(&9)); } +#[test] +fn test_peek_mut_leek() { + let data = vec![4, 2, 7]; + let mut heap = BinaryHeap::from(data); + let mut max = heap.peek_mut().unwrap(); + *max = -1; + + // The PeekMut object's Drop impl would have been responsible for moving the + // -1 out of the max position of the BinaryHeap, but we don't run it. + mem::forget(max); + + // Absent some mitigation like leak amplification, the -1 would incorrectly + // end up in the last position of the returned Vec, with the rest of the + // heap's original contents in front of it in sorted order. + let sorted_vec = heap.into_sorted_vec(); + assert!(sorted_vec.is_sorted(), "{:?}", sorted_vec); +} + #[test] fn test_peek_mut_pop() { let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; @@ -291,33 +310,83 @@ fn test_drain_sorted() { #[test] fn test_drain_sorted_leak() { - static DROPS: AtomicU32 = AtomicU32::new(0); - - #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)] - struct D(u32, bool); - - impl Drop for D { - fn drop(&mut self) { - DROPS.fetch_add(1, Ordering::SeqCst); - - if self.1 { - panic!("panic in `drop`"); - } - } - } - + let d0 = CrashTestDummy::new(0); + let d1 = CrashTestDummy::new(1); + let d2 = CrashTestDummy::new(2); + let d3 = CrashTestDummy::new(3); + let d4 = CrashTestDummy::new(4); + let d5 = CrashTestDummy::new(5); let mut q = BinaryHeap::from(vec![ - D(0, false), - D(1, false), - D(2, false), - D(3, true), - D(4, false), - D(5, false), + d0.spawn(Panic::Never), + d1.spawn(Panic::Never), + d2.spawn(Panic::Never), + d3.spawn(Panic::InDrop), + d4.spawn(Panic::Never), + d5.spawn(Panic::Never), ]); - catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).ok(); + catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).unwrap_err(); + + assert_eq!(d0.dropped(), 1); + assert_eq!(d1.dropped(), 1); + assert_eq!(d2.dropped(), 1); + assert_eq!(d3.dropped(), 1); + assert_eq!(d4.dropped(), 1); + assert_eq!(d5.dropped(), 1); + assert!(q.is_empty()); +} + +#[test] +fn test_drain_forget() { + let a = CrashTestDummy::new(0); + let b = CrashTestDummy::new(1); + let c = CrashTestDummy::new(2); + let mut q = + BinaryHeap::from(vec![a.spawn(Panic::Never), b.spawn(Panic::Never), c.spawn(Panic::Never)]); + + catch_unwind(AssertUnwindSafe(|| { + let mut it = q.drain(); + it.next(); + mem::forget(it); + })) + .unwrap(); + // Behaviour after leaking is explicitly unspecified and order is arbitrary, + // so it's fine if these start failing, but probably worth knowing. + assert!(q.is_empty()); + assert_eq!(a.dropped() + b.dropped() + c.dropped(), 1); + assert_eq!(a.dropped(), 0); + assert_eq!(b.dropped(), 0); + assert_eq!(c.dropped(), 1); + drop(q); + assert_eq!(a.dropped(), 0); + assert_eq!(b.dropped(), 0); + assert_eq!(c.dropped(), 1); +} - assert_eq!(DROPS.load(Ordering::SeqCst), 6); +#[test] +fn test_drain_sorted_forget() { + let a = CrashTestDummy::new(0); + let b = CrashTestDummy::new(1); + let c = CrashTestDummy::new(2); + let mut q = + BinaryHeap::from(vec![a.spawn(Panic::Never), b.spawn(Panic::Never), c.spawn(Panic::Never)]); + + catch_unwind(AssertUnwindSafe(|| { + let mut it = q.drain_sorted(); + it.next(); + mem::forget(it); + })) + .unwrap(); + // Behaviour after leaking is explicitly unspecified, + // so it's fine if these start failing, but probably worth knowing. + assert_eq!(q.len(), 2); + assert_eq!(a.dropped(), 0); + assert_eq!(b.dropped(), 0); + assert_eq!(c.dropped(), 1); + drop(q); + assert_eq!(a.dropped(), 1); + assert_eq!(b.dropped(), 1); + assert_eq!(c.dropped(), 1); } #[test] @@ -415,7 +484,7 @@ fn test_retain() { #[test] #[cfg(not(target_os = "emscripten"))] fn panic_safe() { - use rand::{seq::SliceRandom, thread_rng}; + use rand::seq::SliceRandom; use std::cmp; use std::panic::{self, AssertUnwindSafe}; use std::sync::atomic::{AtomicUsize, Ordering}; @@ -440,7 +509,7 @@ fn panic_safe() { self.0.partial_cmp(&other.0) } } - let mut rng = thread_rng(); + let mut rng = crate::test_helpers::test_rng(); const DATASZ: usize = 32; // Miri is too slow let ntest = if cfg!(miri) { 1 } else { 10 }; diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index 4c372b1d6..700b1463b 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -1,12 +1,12 @@ -use super::super::testing::crash_test::{CrashTestDummy, Panic}; -use super::super::testing::ord_chaos::{Cyclic3, Governed, Governor}; -use super::super::testing::rng::DeterministicRng; use super::Entry::{Occupied, Vacant}; use super::*; use crate::boxed::Box; use crate::fmt::Debug; use crate::rc::Rc; use crate::string::{String, ToString}; +use crate::testing::crash_test::{CrashTestDummy, Panic}; +use crate::testing::ord_chaos::{Cyclic3, Governed, Governor}; +use crate::testing::rng::DeterministicRng; use crate::vec::Vec; use std::cmp::Ordering; use std::convert::TryFrom; diff --git a/library/alloc/src/collections/btree/mod.rs b/library/alloc/src/collections/btree/mod.rs index 9d43ac5c5..7552f2fc0 100644 --- a/library/alloc/src/collections/btree/mod.rs +++ b/library/alloc/src/collections/btree/mod.rs @@ -21,6 +21,3 @@ trait Recover { fn take(&mut self, key: &Q) -> Option; fn replace(&mut self, key: Self::Key) -> Option; } - -#[cfg(test)] -mod testing; diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index da766b67a..691246644 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -318,7 +318,10 @@ impl NodeRef pub fn ascend( self, ) -> Result, marker::Edge>, Self> { - let _ = BorrowType::TRAVERSAL_PERMIT; + const { + assert!(BorrowType::TRAVERSAL_PERMIT); + } + // We need to use raw pointers to nodes because, if BorrowType is marker::ValMut, // there might be outstanding mutable references to values that we must not invalidate. let leaf_ptr: *const _ = Self::as_leaf_ptr(&self); @@ -1003,7 +1006,10 @@ impl /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should /// both, upon success, do nothing. pub fn descend(self) -> NodeRef { - let _ = BorrowType::TRAVERSAL_PERMIT; + const { + assert!(BorrowType::TRAVERSAL_PERMIT); + } + // We need to use raw pointers to nodes because, if BorrowType is // marker::ValMut, there might be outstanding mutable references to // values that we must not invalidate. There's no worry accessing the @@ -1666,17 +1672,17 @@ pub mod marker { pub struct ValMut<'a>(PhantomData<&'a mut ()>); pub trait BorrowType { - // If node references of this borrow type allow traversing to other - // nodes in the tree, this constant can be evaluated. Thus reading it - // serves as a compile-time assertion. - const TRAVERSAL_PERMIT: () = (); + /// If node references of this borrow type allow traversing to other + /// nodes in the tree, this constant is set to `true`. It can be used + /// for a compile-time assertion. + const TRAVERSAL_PERMIT: bool = true; } impl BorrowType for Owned { - // Reject evaluation, because traversal isn't needed. Instead traversal - // happens using the result of `borrow_mut`. - // By disabling traversal, and only creating new references to roots, - // we know that every reference of the `Owned` type is to a root node. - const TRAVERSAL_PERMIT: () = panic!(); + /// Reject traversal, because it isn't needed. Instead traversal + /// happens using the result of `borrow_mut`. + /// By disabling traversal, and only creating new references to roots, + /// we know that every reference of the `Owned` type is to a root node. + const TRAVERSAL_PERMIT: bool = false; } impl BorrowType for Dying {} impl<'a> BorrowType for Immut<'a> {} diff --git a/library/alloc/src/collections/btree/set/tests.rs b/library/alloc/src/collections/btree/set/tests.rs index 502d3e1d1..7b8d41a60 100644 --- a/library/alloc/src/collections/btree/set/tests.rs +++ b/library/alloc/src/collections/btree/set/tests.rs @@ -1,6 +1,6 @@ -use super::super::testing::crash_test::{CrashTestDummy, Panic}; -use super::super::testing::rng::DeterministicRng; use super::*; +use crate::testing::crash_test::{CrashTestDummy, Panic}; +use crate::testing::rng::DeterministicRng; use crate::vec::Vec; use std::cmp::Ordering; use std::hash::{Hash, Hasher}; diff --git a/library/alloc/src/collections/btree/testing/crash_test.rs b/library/alloc/src/collections/btree/testing/crash_test.rs deleted file mode 100644 index bcf5f5f72..000000000 --- a/library/alloc/src/collections/btree/testing/crash_test.rs +++ /dev/null @@ -1,119 +0,0 @@ -// We avoid relying on anything else in the crate, apart from the `Debug` trait. -use crate::fmt::Debug; -use std::cmp::Ordering; -use std::sync::atomic::{AtomicUsize, Ordering::SeqCst}; - -/// A blueprint for crash test dummy instances that monitor particular events. -/// Some instances may be configured to panic at some point. -/// Events are `clone`, `drop` or some anonymous `query`. -/// -/// Crash test dummies are identified and ordered by an id, so they can be used -/// as keys in a BTreeMap. -#[derive(Debug)] -pub struct CrashTestDummy { - pub id: usize, - cloned: AtomicUsize, - dropped: AtomicUsize, - queried: AtomicUsize, -} - -impl CrashTestDummy { - /// Creates a crash test dummy design. The `id` determines order and equality of instances. - pub fn new(id: usize) -> CrashTestDummy { - CrashTestDummy { - id, - cloned: AtomicUsize::new(0), - dropped: AtomicUsize::new(0), - queried: AtomicUsize::new(0), - } - } - - /// Creates an instance of a crash test dummy that records what events it experiences - /// and optionally panics. - pub fn spawn(&self, panic: Panic) -> Instance<'_> { - Instance { origin: self, panic } - } - - /// Returns how many times instances of the dummy have been cloned. - pub fn cloned(&self) -> usize { - self.cloned.load(SeqCst) - } - - /// Returns how many times instances of the dummy have been dropped. - pub fn dropped(&self) -> usize { - self.dropped.load(SeqCst) - } - - /// Returns how many times instances of the dummy have had their `query` member invoked. - pub fn queried(&self) -> usize { - self.queried.load(SeqCst) - } -} - -#[derive(Debug)] -pub struct Instance<'a> { - origin: &'a CrashTestDummy, - panic: Panic, -} - -#[derive(Copy, Clone, Debug, PartialEq, Eq)] -pub enum Panic { - Never, - InClone, - InDrop, - InQuery, -} - -impl Instance<'_> { - pub fn id(&self) -> usize { - self.origin.id - } - - /// Some anonymous query, the result of which is already given. - pub fn query(&self, result: R) -> R { - self.origin.queried.fetch_add(1, SeqCst); - if self.panic == Panic::InQuery { - panic!("panic in `query`"); - } - result - } -} - -impl Clone for Instance<'_> { - fn clone(&self) -> Self { - self.origin.cloned.fetch_add(1, SeqCst); - if self.panic == Panic::InClone { - panic!("panic in `clone`"); - } - Self { origin: self.origin, panic: Panic::Never } - } -} - -impl Drop for Instance<'_> { - fn drop(&mut self) { - self.origin.dropped.fetch_add(1, SeqCst); - if self.panic == Panic::InDrop { - panic!("panic in `drop`"); - } - } -} - -impl PartialOrd for Instance<'_> { - fn partial_cmp(&self, other: &Self) -> Option { - self.id().partial_cmp(&other.id()) - } -} - -impl Ord for Instance<'_> { - fn cmp(&self, other: &Self) -> Ordering { - self.id().cmp(&other.id()) - } -} - -impl PartialEq for Instance<'_> { - fn eq(&self, other: &Self) -> bool { - self.id().eq(&other.id()) - } -} - -impl Eq for Instance<'_> {} diff --git a/library/alloc/src/collections/btree/testing/mod.rs b/library/alloc/src/collections/btree/testing/mod.rs deleted file mode 100644 index 7a094f8a5..000000000 --- a/library/alloc/src/collections/btree/testing/mod.rs +++ /dev/null @@ -1,3 +0,0 @@ -pub mod crash_test; -pub mod ord_chaos; -pub mod rng; diff --git a/library/alloc/src/collections/btree/testing/ord_chaos.rs b/library/alloc/src/collections/btree/testing/ord_chaos.rs deleted file mode 100644 index 96ce7c157..000000000 --- a/library/alloc/src/collections/btree/testing/ord_chaos.rs +++ /dev/null @@ -1,81 +0,0 @@ -use std::cell::Cell; -use std::cmp::Ordering::{self, *}; -use std::ptr; - -// Minimal type with an `Ord` implementation violating transitivity. -#[derive(Debug)] -pub enum Cyclic3 { - A, - B, - C, -} -use Cyclic3::*; - -impl PartialOrd for Cyclic3 { - fn partial_cmp(&self, other: &Self) -> Option { - Some(self.cmp(other)) - } -} - -impl Ord for Cyclic3 { - fn cmp(&self, other: &Self) -> Ordering { - match (self, other) { - (A, A) | (B, B) | (C, C) => Equal, - (A, B) | (B, C) | (C, A) => Less, - (A, C) | (B, A) | (C, B) => Greater, - } - } -} - -impl PartialEq for Cyclic3 { - fn eq(&self, other: &Self) -> bool { - self.cmp(&other) == Equal - } -} - -impl Eq for Cyclic3 {} - -// Controls the ordering of values wrapped by `Governed`. -#[derive(Debug)] -pub struct Governor { - flipped: Cell, -} - -impl Governor { - pub fn new() -> Self { - Governor { flipped: Cell::new(false) } - } - - pub fn flip(&self) { - self.flipped.set(!self.flipped.get()); - } -} - -// Type with an `Ord` implementation that forms a total order at any moment -// (assuming that `T` respects total order), but can suddenly be made to invert -// that total order. -#[derive(Debug)] -pub struct Governed<'a, T>(pub T, pub &'a Governor); - -impl PartialOrd for Governed<'_, T> { - fn partial_cmp(&self, other: &Self) -> Option { - Some(self.cmp(other)) - } -} - -impl Ord for Governed<'_, T> { - fn cmp(&self, other: &Self) -> Ordering { - assert!(ptr::eq(self.1, other.1)); - let ord = self.0.cmp(&other.0); - if self.1.flipped.get() { ord.reverse() } else { ord } - } -} - -impl PartialEq for Governed<'_, T> { - fn eq(&self, other: &Self) -> bool { - assert!(ptr::eq(self.1, other.1)); - self.0.eq(&other.0) - } -} - -impl Eq for Governed<'_, T> {} diff --git a/library/alloc/src/collections/btree/testing/rng.rs b/library/alloc/src/collections/btree/testing/rng.rs deleted file mode 100644 index ecf543bee..000000000 --- a/library/alloc/src/collections/btree/testing/rng.rs +++ /dev/null @@ -1,28 +0,0 @@ -/// XorShiftRng -pub struct DeterministicRng { - count: usize, - x: u32, - y: u32, - z: u32, - w: u32, -} - -impl DeterministicRng { - pub fn new() -> Self { - DeterministicRng { count: 0, x: 0x193a6754, y: 0xa8a7d469, z: 0x97830e05, w: 0x113ba7bb } - } - - /// Guarantees that each returned number is unique. - pub fn next(&mut self) -> u32 { - self.count += 1; - assert!(self.count <= 70029); - let x = self.x; - let t = x ^ (x << 11); - self.x = self.y; - self.y = self.z; - self.z = self.w; - let w_ = self.w; - self.w = w_ ^ (w_ >> 19) ^ (t ^ (t >> 8)); - self.w - } -} diff --git a/library/alloc/src/collections/linked_list/tests.rs b/library/alloc/src/collections/linked_list/tests.rs index f8fbfa1bf..04594d55b 100644 --- a/library/alloc/src/collections/linked_list/tests.rs +++ b/library/alloc/src/collections/linked_list/tests.rs @@ -1,10 +1,11 @@ use super::*; +use crate::testing::crash_test::{CrashTestDummy, Panic}; use crate::vec::Vec; use std::panic::{catch_unwind, AssertUnwindSafe}; use std::thread; -use rand::{thread_rng, RngCore}; +use rand::RngCore; #[test] fn test_basic() { @@ -480,12 +481,12 @@ fn test_split_off_2() { } } -fn fuzz_test(sz: i32) { +fn fuzz_test(sz: i32, rng: &mut impl RngCore) { let mut m: LinkedList<_> = LinkedList::new(); let mut v = vec![]; for i in 0..sz { check_links(&m); - let r: u8 = thread_rng().next_u32() as u8; + let r: u8 = rng.next_u32() as u8; match r % 6 { 0 => { m.pop_back(); @@ -520,11 +521,12 @@ fn fuzz_test(sz: i32) { #[test] fn test_fuzz() { + let mut rng = crate::test_helpers::test_rng(); for _ in 0..25 { - fuzz_test(3); - fuzz_test(16); + fuzz_test(3, &mut rng); + fuzz_test(16, &mut rng); #[cfg(not(miri))] // Miri is too slow - fuzz_test(189); + fuzz_test(189, &mut rng); } } @@ -984,35 +986,34 @@ fn drain_filter_complex() { #[test] fn drain_filter_drop_panic_leak() { - static mut DROPS: i32 = 0; - - struct D(bool); - - impl Drop for D { - fn drop(&mut self) { - unsafe { - DROPS += 1; - } - - if self.0 { - panic!("panic in `drop`"); - } - } - } - + let d0 = CrashTestDummy::new(0); + let d1 = CrashTestDummy::new(1); + let d2 = CrashTestDummy::new(2); + let d3 = CrashTestDummy::new(3); + let d4 = CrashTestDummy::new(4); + let d5 = CrashTestDummy::new(5); + let d6 = CrashTestDummy::new(6); + let d7 = CrashTestDummy::new(7); let mut q = LinkedList::new(); - q.push_back(D(false)); - q.push_back(D(false)); - q.push_back(D(false)); - q.push_back(D(false)); - q.push_back(D(false)); - q.push_front(D(false)); - q.push_front(D(true)); - q.push_front(D(false)); - - catch_unwind(AssertUnwindSafe(|| drop(q.drain_filter(|_| true)))).ok(); - - assert_eq!(unsafe { DROPS }, 8); + q.push_back(d3.spawn(Panic::Never)); + q.push_back(d4.spawn(Panic::Never)); + q.push_back(d5.spawn(Panic::Never)); + q.push_back(d6.spawn(Panic::Never)); + q.push_back(d7.spawn(Panic::Never)); + q.push_front(d2.spawn(Panic::Never)); + q.push_front(d1.spawn(Panic::InDrop)); + q.push_front(d0.spawn(Panic::Never)); + + catch_unwind(AssertUnwindSafe(|| drop(q.drain_filter(|_| true)))).unwrap_err(); + + assert_eq!(d0.dropped(), 1); + assert_eq!(d1.dropped(), 1); + assert_eq!(d2.dropped(), 1); + assert_eq!(d3.dropped(), 1); + assert_eq!(d4.dropped(), 1); + assert_eq!(d5.dropped(), 1); + assert_eq!(d6.dropped(), 1); + assert_eq!(d7.dropped(), 1); assert!(q.is_empty()); } diff --git a/library/alloc/src/collections/vec_deque/into_iter.rs b/library/alloc/src/collections/vec_deque/into_iter.rs index 55f6138cd..e54880e86 100644 --- a/library/alloc/src/collections/vec_deque/into_iter.rs +++ b/library/alloc/src/collections/vec_deque/into_iter.rs @@ -25,6 +25,10 @@ impl IntoIter { pub(super) fn new(inner: VecDeque) -> Self { IntoIter { inner } } + + pub(super) fn into_vecdeque(self) -> VecDeque { + self.inner + } } #[stable(feature = "collection_debug", since = "1.17.0")] diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs index 4866c53e7..8317ac431 100644 --- a/library/alloc/src/collections/vec_deque/mod.rs +++ b/library/alloc/src/collections/vec_deque/mod.rs @@ -55,6 +55,10 @@ use self::spec_extend::SpecExtend; mod spec_extend; +use self::spec_from_iter::SpecFromIter; + +mod spec_from_iter; + #[cfg(test)] mod tests; @@ -531,12 +535,13 @@ impl VecDeque { /// /// let deque: VecDeque = VecDeque::new(); /// ``` - // FIXME: This should probably be const #[inline] #[stable(feature = "rust1", since = "1.0.0")] + #[rustc_const_stable(feature = "const_vec_deque_new", since = "1.68.0")] #[must_use] - pub fn new() -> VecDeque { - VecDeque::new_in(Global) + pub const fn new() -> VecDeque { + // FIXME: This should just be `VecDeque::new_in(Global)` once that hits stable. + VecDeque { head: 0, len: 0, buf: RawVec::NEW } } /// Creates an empty deque with space for at least `capacity` elements. @@ -586,6 +591,38 @@ impl VecDeque { VecDeque { head: 0, len: 0, buf: RawVec::with_capacity_in(capacity, alloc) } } + /// Creates a `VecDeque` from a raw allocation, when the initialized + /// part of that allocation forms a *contiguous* subslice thereof. + /// + /// For use by `vec::IntoIter::into_vecdeque` + /// + /// # Safety + /// + /// All the usual requirements on the allocated memory like in + /// `Vec::from_raw_parts_in`, but takes a *range* of elements that are + /// initialized rather than only supporting `0..len`. Requires that + /// `initialized.start` ≤ `initialized.end` ≤ `capacity`. + #[inline] + pub(crate) unsafe fn from_contiguous_raw_parts_in( + ptr: *mut T, + initialized: Range, + capacity: usize, + alloc: A, + ) -> Self { + debug_assert!(initialized.start <= initialized.end); + debug_assert!(initialized.end <= capacity); + + // SAFETY: Our safety precondition guarantees the range length won't wrap, + // and that the allocation is valid for use in `RawVec`. + unsafe { + VecDeque { + head: initialized.start, + len: initialized.end.unchecked_sub(initialized.start), + buf: RawVec::from_raw_parts_in(ptr, capacity, alloc), + } + } + } + /// Provides a reference to the element at the given index. /// /// Element at index 0 is the front of the queue. @@ -599,6 +636,7 @@ impl VecDeque { /// buf.push_back(3); /// buf.push_back(4); /// buf.push_back(5); + /// buf.push_back(6); /// assert_eq!(buf.get(1), Some(&4)); /// ``` #[stable(feature = "rust1", since = "1.0.0")] @@ -624,10 +662,11 @@ impl VecDeque { /// buf.push_back(3); /// buf.push_back(4); /// buf.push_back(5); + /// buf.push_back(6); + /// assert_eq!(buf[1], 4); /// if let Some(elem) = buf.get_mut(1) { /// *elem = 7; /// } - /// /// assert_eq!(buf[1], 7); /// ``` #[stable(feature = "rust1", since = "1.0.0")] @@ -905,65 +944,72 @@ impl VecDeque { return; } - if target_cap < self.capacity() { - // There are three cases of interest: - // All elements are out of desired bounds - // Elements are contiguous, and head is out of desired bounds - // Elements are discontiguous, and tail is out of desired bounds + // There are three cases of interest: + // All elements are out of desired bounds + // Elements are contiguous, and tail is out of desired bounds + // Elements are discontiguous + // + // At all other times, element positions are unaffected. + + // `head` and `len` are at most `isize::MAX` and `target_cap < self.capacity()`, so nothing can + // overflow. + let tail_outside = (target_cap + 1..=self.capacity()).contains(&(self.head + self.len)); + + if self.len == 0 { + self.head = 0; + } else if self.head >= target_cap && tail_outside { + // Head and tail are both out of bounds, so copy all of them to the front. // - // At all other times, element positions are unaffected. + // H := head + // L := last element + // H L + // [. . . . . . . . o o o o o o o . ] + // H L + // [o o o o o o o . ] + unsafe { + // nonoverlapping because `self.head >= target_cap >= self.len`. + self.copy_nonoverlapping(self.head, 0, self.len); + } + self.head = 0; + } else if self.head < target_cap && tail_outside { + // Head is in bounds, tail is out of bounds. + // Copy the overflowing part to the beginning of the + // buffer. This won't overlap because `target_cap >= self.len`. // - // Indicates that elements at the head should be moved. - - let tail_outside = (target_cap + 1..=self.capacity()).contains(&(self.head + self.len)); - // Move elements from out of desired bounds (positions after target_cap) - if self.len == 0 { - self.head = 0; - } else if self.head >= target_cap && tail_outside { - // H := head - // L := last element - // H L - // [. . . . . . . . o o o o o o o . ] - // H L - // [o o o o o o o . ] - unsafe { - // nonoverlapping because self.head >= target_cap >= self.len - self.copy_nonoverlapping(self.head, 0, self.len); - } - self.head = 0; - } else if self.head < target_cap && tail_outside { - // H := head - // L := last element - // H L - // [. . . o o o o o o o . . . . . . ] - // L H - // [o o . o o o o o ] - let len = self.head + self.len - target_cap; - unsafe { - self.copy_nonoverlapping(target_cap, 0, len); - } - } else if self.head >= target_cap { - // H := head - // L := last element - // L H - // [o o o o o . . . . . . . . . o o ] - // L H - // [o o o o o . o o ] - let len = self.capacity() - self.head; - let new_head = target_cap - len; - unsafe { - // can't use copy_nonoverlapping here for the same reason - // as in `handle_capacity_increase()` - self.copy(self.head, new_head, len); - } - self.head = new_head; + // H := head + // L := last element + // H L + // [. . . o o o o o o o . . . . . . ] + // L H + // [o o . o o o o o ] + let len = self.head + self.len - target_cap; + unsafe { + self.copy_nonoverlapping(target_cap, 0, len); } - - self.buf.shrink_to_fit(target_cap); - - debug_assert!(self.head < self.capacity() || self.capacity() == 0); - debug_assert!(self.len <= self.capacity()); + } else if !self.is_contiguous() { + // The head slice is at least partially out of bounds, tail is in bounds. + // Copy the head backwards so it lines up with the target capacity. + // This won't overlap because `target_cap >= self.len`. + // + // H := head + // L := last element + // L H + // [o o o o o . . . . . . . . . o o ] + // L H + // [o o o o o . o o ] + let head_len = self.capacity() - self.head; + let new_head = target_cap - head_len; + unsafe { + // can't use `copy_nonoverlapping()` here because the new and old + // regions for the head might overlap. + self.copy(self.head, new_head, head_len); + } + self.head = new_head; } + self.buf.shrink_to_fit(target_cap); + + debug_assert!(self.head < self.capacity() || self.capacity() == 0); + debug_assert!(self.len <= self.capacity()); } /// Shortens the deque, keeping the first `len` elements and dropping @@ -1878,7 +1924,7 @@ impl VecDeque { #[stable(feature = "append", since = "1.4.0")] pub fn append(&mut self, other: &mut Self) { if T::IS_ZST { - self.len += other.len; + self.len = self.len.checked_add(other.len).expect("capacity overflow"); other.len = 0; other.head = 0; return; @@ -2505,7 +2551,7 @@ impl VecDeque { /// The deque is assumed to be partitioned according to the given predicate. /// This means that all elements for which the predicate returns true are at the start of the deque /// and all elements for which the predicate returns false are at the end. - /// For example, [7, 15, 3, 5, 4, 12, 6] is a partitioned under the predicate x % 2 != 0 + /// For example, `[7, 15, 3, 5, 4, 12, 6]` is partitioned under the predicate `x % 2 != 0` /// (all odd numbers are at the start, all even at the end). /// /// If the deque is not partitioned, the returned result is unspecified and meaningless, @@ -2699,18 +2745,8 @@ impl IndexMut for VecDeque { #[stable(feature = "rust1", since = "1.0.0")] impl FromIterator for VecDeque { - #[inline] fn from_iter>(iter: I) -> VecDeque { - // Since converting is O(1) now, might as well re-use that logic - // (including things like the `vec::IntoIter`→`Vec` specialization) - // especially as that could save us some monomorphiziation work - // if one uses the same iterators (like slice ones) with both. - return from_iter_via_vec(iter.into_iter()); - - #[inline] - fn from_iter_via_vec(iter: impl Iterator) -> VecDeque { - Vec::from_iter(iter).into() - } + SpecFromIter::spec_from_iter(iter.into_iter()) } } @@ -2794,9 +2830,9 @@ impl From> for VecDeque { /// [`Vec`]: crate::vec::Vec /// [`VecDeque`]: crate::collections::VecDeque /// - /// In its current implementation, this is a very cheap - /// conversion. This isn't yet a guarantee though, and - /// shouldn't be relied on. + /// This conversion is guaranteed to run in *O*(1) time + /// and to not re-allocate the `Vec`'s buffer or allocate + /// any additional memory. #[inline] fn from(other: Vec) -> Self { let (ptr, len, cap, alloc) = other.into_raw_parts_with_alloc(); diff --git a/library/alloc/src/collections/vec_deque/spec_from_iter.rs b/library/alloc/src/collections/vec_deque/spec_from_iter.rs new file mode 100644 index 000000000..7650492eb --- /dev/null +++ b/library/alloc/src/collections/vec_deque/spec_from_iter.rs @@ -0,0 +1,33 @@ +use super::{IntoIter, VecDeque}; + +/// Specialization trait used for `VecDeque::from_iter` +pub(super) trait SpecFromIter { + fn spec_from_iter(iter: I) -> Self; +} + +impl SpecFromIter for VecDeque +where + I: Iterator, +{ + default fn spec_from_iter(iterator: I) -> Self { + // Since converting is O(1) now, just re-use the `Vec` logic for + // anything where we can't do something extra-special for `VecDeque`, + // especially as that could save us some monomorphiziation work + // if one uses the same iterators (like slice ones) with both. + crate::vec::Vec::from_iter(iterator).into() + } +} + +impl SpecFromIter> for VecDeque { + #[inline] + fn spec_from_iter(iterator: crate::vec::IntoIter) -> Self { + iterator.into_vecdeque() + } +} + +impl SpecFromIter> for VecDeque { + #[inline] + fn spec_from_iter(iterator: IntoIter) -> Self { + iterator.into_vecdeque() + } +} diff --git a/library/alloc/src/collections/vec_deque/tests.rs b/library/alloc/src/collections/vec_deque/tests.rs index 220ad71be..205a8ff3c 100644 --- a/library/alloc/src/collections/vec_deque/tests.rs +++ b/library/alloc/src/collections/vec_deque/tests.rs @@ -748,6 +748,48 @@ fn test_drain() { } } +#[test] +fn issue_108453() { + let mut deque = VecDeque::with_capacity(10); + + deque.push_back(1u8); + deque.push_back(2); + deque.push_back(3); + + deque.push_front(10); + deque.push_front(9); + + deque.shrink_to(9); + + assert_eq!(deque.into_iter().collect::>(), vec![9, 10, 1, 2, 3]); +} + +#[test] +fn test_shrink_to() { + // test deques with capacity 16 with all possible head positions, lengths and target capacities. + let cap = 16; + + for len in 0..cap { + for head in 0..cap { + let expected = (1..=len).collect::>(); + + for target_cap in len..cap { + let mut deque = VecDeque::with_capacity(cap); + // currently, `with_capacity` always allocates the exact capacity if it's greater than 8. + assert_eq!(deque.capacity(), cap); + + // we can let the head point anywhere in the buffer since the deque is empty. + deque.head = head; + deque.extend(1..=len); + + deque.shrink_to(target_cap); + + assert_eq!(deque, expected); + } + } + } +} + #[test] fn test_shrink_to_fit() { // This test checks that every single combination of head and tail position, -- cgit v1.2.3