use core::hash::{Hash, Hasher};
use core::iter::{repeat_with, FromIterator};
use core::marker::PhantomData;
-use core::mem::{self, ManuallyDrop};
+use core::mem::{self, ManuallyDrop, MaybeUninit};
use core::ops::{Index, IndexMut, Range, RangeBounds};
use core::ptr::{self, NonNull};
use core::slice;
}
}
- /// Turn ptr into a slice
+ /// Turn ptr into a slice, since the elements of the backing buffer may be uninitialized,
+ /// we will return a slice of [`MaybeUninit<T>`].
+ ///
+ /// See [`MaybeUninit::zeroed`][zeroed] for examples of correct and
+ /// incorrect usage of this method.
+ ///
+ /// [zeroed]: mem::MaybeUninit::zeroed
#[inline]
- unsafe fn buffer_as_slice(&self) -> &[T] {
- unsafe { slice::from_raw_parts(self.ptr(), self.cap()) }
+ unsafe fn buffer_as_slice(&self) -> &[MaybeUninit<T>] {
+ unsafe { slice::from_raw_parts(self.ptr() as *mut MaybeUninit<T>, self.cap()) }
}
- /// Turn ptr into a mut slice
+ /// Turn ptr into a mut slice, since the elements of the backing buffer may be uninitialized,
+ /// we will return a slice of [`MaybeUninit<T>`].
+ ///
+ /// See [`MaybeUninit::zeroed`][zeroed] for examples of correct and
+ /// incorrect usage of this method.
+ ///
+ /// [zeroed]: mem::MaybeUninit::zeroed
#[inline]
- unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T] {
- unsafe { slice::from_raw_parts_mut(self.ptr(), self.cap()) }
+ unsafe fn buffer_as_mut_slice(&mut self) -> &mut [MaybeUninit<T>] {
+ unsafe { slice::from_raw_parts_mut(self.ptr() as *mut MaybeUninit<T>, self.cap()) }
}
/// Moves an element out of the buffer
#[inline]
#[stable(feature = "deque_extras_15", since = "1.5.0")]
pub fn as_slices(&self) -> (&[T], &[T]) {
+ // Safety:
+ // - `self.head` and `self.tail` in a ring buffer are always valid indices.
+ // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
unsafe {
let buf = self.buffer_as_slice();
- RingSlices::ring_slices(buf, self.head, self.tail)
+ let (front, back) = RingSlices::ring_slices(buf, self.head, self.tail);
+ (MaybeUninit::slice_assume_init_ref(front), MaybeUninit::slice_assume_init_ref(back))
}
}
#[inline]
#[stable(feature = "deque_extras_15", since = "1.5.0")]
pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
+ // Safety:
+ // - `self.head` and `self.tail` in a ring buffer are always valid indices.
+ // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
unsafe {
let head = self.head;
let tail = self.tail;
let buf = self.buffer_as_mut_slice();
- RingSlices::ring_slices(buf, head, tail)
+ let (front, back) = RingSlices::ring_slices(buf, head, tail);
+ (MaybeUninit::slice_assume_init_mut(front), MaybeUninit::slice_assume_init_mut(back))
}
}
/// Retains only the elements specified by the predicate.
///
- /// In other words, remove all elements `e` such that `f(&e)` returns false.
+ /// In other words, remove all elements `e` for which `f(&e)` returns false.
/// This method operates in place, visiting each element exactly once in the
/// original order, and preserves the order of the retained elements.
///
/// Retains only the elements specified by the predicate.
///
- /// In other words, remove all elements `e` such that `f(&e)` returns false.
+ /// In other words, remove all elements `e` for which `f(&e)` returns false.
/// This method operates in place, visiting each element exactly once in the
/// original order, and preserves the order of the retained elements.
///
/// # Examples
///
/// ```
- /// #![feature(vec_retain_mut)]
- ///
/// use std::collections::VecDeque;
///
/// let mut buf = VecDeque::new();
/// });
/// assert_eq!(buf, [3, 5]);
/// ```
- #[unstable(feature = "vec_retain_mut", issue = "90829")]
+ #[stable(feature = "vec_retain_mut", since = "1.61.0")]
pub fn retain_mut<F>(&mut self, mut f: F)
where
F: FnMut(&mut T) -> bool,
if self.is_contiguous() {
let tail = self.tail;
let head = self.head;
- return unsafe { RingSlices::ring_slices(self.buffer_as_mut_slice(), head, tail).0 };
+ // Safety:
+ // - `self.head` and `self.tail` in a ring buffer are always valid indices.
+ // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
+ return unsafe {
+ MaybeUninit::slice_assume_init_mut(
+ RingSlices::ring_slices(self.buffer_as_mut_slice(), head, tail).0,
+ )
+ };
}
let buf = self.buf.ptr();
let tail = self.tail;
let head = self.head;
- unsafe { RingSlices::ring_slices(self.buffer_as_mut_slice(), head, tail).0 }
+ // Safety:
+ // - `self.head` and `self.tail` in a ring buffer are always valid indices.
+ // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
+ unsafe {
+ MaybeUninit::slice_assume_init_mut(
+ RingSlices::ring_slices(self.buffer_as_mut_slice(), head, tail).0,
+ )
+ }
}
/// Rotates the double-ended queue `mid` places to the left.
/// ```
///
/// If you want to insert an item to a sorted deque, while maintaining
- /// sort order:
+ /// sort order, consider using [`partition_point`]:
///
/// ```
/// use std::collections::VecDeque;
///
/// let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
/// let num = 42;
- /// let idx = deque.binary_search(&num).unwrap_or_else(|x| x);
+ /// let idx = deque.partition_point(|&x| x < num);
+ /// // The above is equivalent to `let idx = deque.binary_search(&num).unwrap_or_else(|x| x);`
/// deque.insert(idx, num);
/// assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
/// ```
/// assert!(deque.iter().take(i).all(|&x| x < 5));
/// assert!(deque.iter().skip(i).all(|&x| !(x < 5)));
/// ```
+ ///
+ /// If you want to insert an item to a sorted deque, while maintaining
+ /// sort order:
+ ///
+ /// ```
+ /// use std::collections::VecDeque;
+ ///
+ /// let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
+ /// let num = 42;
+ /// let idx = deque.partition_point(|&x| x < num);
+ /// deque.insert(idx, num);
+ /// assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
+ /// ```
#[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
pub fn partition_point<P>(&self, mut pred: P) -> usize
where
projects / rust.git / blobdiff