diff options
Diffstat (limited to 'library/alloc/src')
| -rw-r--r-- | library/alloc/src/collections/linked_list.rs | 54 | ||||
| -rw-r--r-- | library/alloc/src/collections/vec_deque/drain.rs | 2 | ||||
| -rw-r--r-- | library/alloc/src/collections/vec_deque/mod.rs | 96 | ||||
| -rw-r--r-- | library/alloc/src/lib.rs | 1 | ||||
| -rw-r--r-- | library/alloc/src/raw_vec/mod.rs | 2 | ||||
| -rw-r--r-- | library/alloc/src/slice.rs | 4 | ||||
| -rw-r--r-- | library/alloc/src/string.rs | 24 | ||||
| -rw-r--r-- | library/alloc/src/vec/mod.rs | 122 |
8 files changed, 257 insertions, 48 deletions
diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs index 70c344e49b7..31dfe73fc79 100644 --- a/library/alloc/src/collections/linked_list.rs +++ b/library/alloc/src/collections/linked_list.rs @@ -825,7 +825,7 @@ impl<T, A: Allocator> LinkedList<T, A> { unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().element) } } - /// Adds an element first in the list. + /// Adds an element to the front of the list. /// /// This operation should compute in *O*(1) time. /// @@ -844,11 +844,34 @@ impl<T, A: Allocator> LinkedList<T, A> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn push_front(&mut self, elt: T) { + let _ = self.push_front_mut(elt); + } + + /// Adds an element to the front of the list, returning a reference to it. + /// + /// This operation should compute in *O*(1) time. + /// + /// # Examples + /// + /// ``` + /// #![feature(push_mut)] + /// use std::collections::LinkedList; + /// + /// let mut dl = LinkedList::from([1, 2, 3]); + /// + /// let ptr = dl.push_front_mut(2); + /// *ptr += 4; + /// assert_eq!(dl.front().unwrap(), &6); + /// ``` + #[unstable(feature = "push_mut", issue = "135974")] + #[must_use = "if you don't need a reference to the value, use `LinkedList::push_front` instead"] + pub fn push_front_mut(&mut self, elt: T) -> &mut T { let node = Box::new_in(Node::new(elt), &self.alloc); - let node_ptr = NonNull::from(Box::leak(node)); + let mut node_ptr = NonNull::from(Box::leak(node)); // SAFETY: node_ptr is a unique pointer to a node we boxed with self.alloc and leaked unsafe { self.push_front_node(node_ptr); + &mut node_ptr.as_mut().element } } @@ -876,7 +899,7 @@ impl<T, A: Allocator> LinkedList<T, A> { self.pop_front_node().map(Node::into_element) } - /// Appends an element to the back of a list. + /// Adds an element to the back of the list. /// /// This operation should compute in *O*(1) time. /// @@ -893,11 +916,34 @@ impl<T, A: Allocator> LinkedList<T, A> { #[stable(feature = "rust1", since = "1.0.0")] #[rustc_confusables("push", "append")] pub fn push_back(&mut self, elt: T) { + let _ = self.push_back_mut(elt); + } + + /// Adds an element to the back of the list, returning a reference to it. + /// + /// This operation should compute in *O*(1) time. + /// + /// # Examples + /// + /// ``` + /// #![feature(push_mut)] + /// use std::collections::LinkedList; + /// + /// let mut dl = LinkedList::from([1, 2, 3]); + /// + /// let ptr = dl.push_back_mut(2); + /// *ptr += 4; + /// assert_eq!(dl.back().unwrap(), &6); + /// ``` + #[unstable(feature = "push_mut", issue = "135974")] + #[must_use = "if you don't need a reference to the value, use `LinkedList::push_back` instead"] + pub fn push_back_mut(&mut self, elt: T) -> &mut T { let node = Box::new_in(Node::new(elt), &self.alloc); - let node_ptr = NonNull::from(Box::leak(node)); + let mut node_ptr = NonNull::from(Box::leak(node)); // SAFETY: node_ptr is a unique pointer to a node we boxed with self.alloc and leaked unsafe { self.push_back_node(node_ptr); + &mut node_ptr.as_mut().element } } diff --git a/library/alloc/src/collections/vec_deque/drain.rs b/library/alloc/src/collections/vec_deque/drain.rs index 44fcef4ed7d..321621d18be 100644 --- a/library/alloc/src/collections/vec_deque/drain.rs +++ b/library/alloc/src/collections/vec_deque/drain.rs @@ -192,7 +192,7 @@ impl<T, A: Allocator> Drop for Drain<'_, T, A> { // this branch is never taken. // We use `#[cold]` instead of `#[inline(never)]`, because inlining this // function into the general case (`.drain(n..m)`) is fine. - // See `tests/codegen/vecdeque-drain.rs` for a test. + // See `tests/codegen-llvm/vecdeque-drain.rs` for a test. #[cold] fn join_head_and_tail_wrapping<T, A: Allocator>( source_deque: &mut VecDeque<T, A>, diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs index 08b1828ff00..2fce5c3e737 100644 --- a/library/alloc/src/collections/vec_deque/mod.rs +++ b/library/alloc/src/collections/vec_deque/mod.rs @@ -182,11 +182,16 @@ impl<T, A: Allocator> VecDeque<T, A> { unsafe { ptr::read(self.ptr().add(off)) } } - /// Writes an element into the buffer, moving it. + /// Writes an element into the buffer, moving it and returning a pointer to it. + /// # Safety + /// + /// May only be called if `off < self.capacity()`. #[inline] - unsafe fn buffer_write(&mut self, off: usize, value: T) { + unsafe fn buffer_write(&mut self, off: usize, value: T) -> &mut T { unsafe { - ptr::write(self.ptr().add(off), value); + let ptr = self.ptr().add(off); + ptr::write(ptr, value); + &mut *ptr } } @@ -1888,16 +1893,34 @@ impl<T, A: Allocator> VecDeque<T, A> { #[stable(feature = "rust1", since = "1.0.0")] #[track_caller] pub fn push_front(&mut self, value: T) { + let _ = self.push_front_mut(value); + } + + /// Prepends an element to the deque, returning a reference to it. + /// + /// # Examples + /// + /// ``` + /// #![feature(push_mut)] + /// use std::collections::VecDeque; + /// + /// let mut d = VecDeque::from([1, 2, 3]); + /// let x = d.push_front_mut(8); + /// *x -= 1; + /// assert_eq!(d.front(), Some(&7)); + /// ``` + #[unstable(feature = "push_mut", issue = "135974")] + #[track_caller] + #[must_use = "if you don't need a reference to the value, use `VecDeque::push_front` instead"] + pub fn push_front_mut(&mut self, value: T) -> &mut T { if self.is_full() { self.grow(); } self.head = self.wrap_sub(self.head, 1); self.len += 1; - - unsafe { - self.buffer_write(self.head, value); - } + // SAFETY: We know that self.head is within range of the deque. + unsafe { self.buffer_write(self.head, value) } } /// Appends an element to the back of the deque. @@ -1916,12 +1939,33 @@ impl<T, A: Allocator> VecDeque<T, A> { #[rustc_confusables("push", "put", "append")] #[track_caller] pub fn push_back(&mut self, value: T) { + let _ = self.push_back_mut(value); + } + + /// Appends an element to the back of the deque, returning a reference to it. + /// + /// # Examples + /// + /// ``` + /// #![feature(push_mut)] + /// use std::collections::VecDeque; + /// + /// let mut d = VecDeque::from([1, 2, 3]); + /// let x = d.push_back_mut(9); + /// *x += 1; + /// assert_eq!(d.back(), Some(&10)); + /// ``` + #[unstable(feature = "push_mut", issue = "135974")] + #[track_caller] + #[must_use = "if you don't need a reference to the value, use `VecDeque::push_back` instead"] + pub fn push_back_mut(&mut self, value: T) -> &mut T { if self.is_full() { self.grow(); } - unsafe { self.buffer_write(self.to_physical_idx(self.len), value) } + let len = self.len; self.len += 1; + unsafe { self.buffer_write(self.to_physical_idx(len), value) } } #[inline] @@ -2007,7 +2051,7 @@ impl<T, A: Allocator> VecDeque<T, A> { /// /// # Panics /// - /// Panics if `index` is strictly greater than deque's length + /// Panics if `index` is strictly greater than the deque's length. /// /// # Examples /// @@ -2029,7 +2073,37 @@ impl<T, A: Allocator> VecDeque<T, A> { #[stable(feature = "deque_extras_15", since = "1.5.0")] #[track_caller] pub fn insert(&mut self, index: usize, value: T) { + let _ = self.insert_mut(index, value); + } + + /// Inserts an element at `index` within the deque, shifting all elements + /// with indices greater than or equal to `index` towards the back, and + /// returning a reference to it. + /// + /// Element at index 0 is the front of the queue. + /// + /// # Panics + /// + /// Panics if `index` is strictly greater than the deque's length. + /// + /// # Examples + /// + /// ``` + /// #![feature(push_mut)] + /// use std::collections::VecDeque; + /// + /// let mut vec_deque = VecDeque::from([1, 2, 3]); + /// + /// let x = vec_deque.insert_mut(1, 5); + /// *x += 7; + /// assert_eq!(vec_deque, &[1, 12, 2, 3]); + /// ``` + #[unstable(feature = "push_mut", issue = "135974")] + #[track_caller] + #[must_use = "if you don't need a reference to the value, use `VecDeque::insert` instead"] + pub fn insert_mut(&mut self, index: usize, value: T) -> &mut T { assert!(index <= self.len(), "index out of bounds"); + if self.is_full() { self.grow(); } @@ -2042,16 +2116,16 @@ impl<T, A: Allocator> VecDeque<T, A> { unsafe { // see `remove()` for explanation why this wrap_copy() call is safe. self.wrap_copy(self.to_physical_idx(index), self.to_physical_idx(index + 1), k); - self.buffer_write(self.to_physical_idx(index), value); self.len += 1; + self.buffer_write(self.to_physical_idx(index), value) } } else { let old_head = self.head; self.head = self.wrap_sub(self.head, 1); unsafe { self.wrap_copy(old_head, self.head, index); - self.buffer_write(self.to_physical_idx(index), value); self.len += 1; + self.buffer_write(self.to_physical_idx(index), value) } } } diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs index 6b6e4df4cba..c091e496c50 100644 --- a/library/alloc/src/lib.rs +++ b/library/alloc/src/lib.rs @@ -94,7 +94,6 @@ // tidy-alphabetical-start #![feature(alloc_layout_extra)] #![feature(allocator_api)] -#![feature(array_chunks)] #![feature(array_into_iter_constructors)] #![feature(array_windows)] #![feature(ascii_char)] diff --git a/library/alloc/src/raw_vec/mod.rs b/library/alloc/src/raw_vec/mod.rs index 3e006a2d1bd..40716755aad 100644 --- a/library/alloc/src/raw_vec/mod.rs +++ b/library/alloc/src/raw_vec/mod.rs @@ -761,7 +761,7 @@ impl<A: Allocator> RawVecInner<A> { } // not marked inline(never) since we want optimizers to be able to observe the specifics of this -// function, see tests/codegen/vec-reserve-extend.rs. +// function, see tests/codegen-llvm/vec-reserve-extend.rs. #[cold] fn finish_grow<A>( new_layout: Layout, diff --git a/library/alloc/src/slice.rs b/library/alloc/src/slice.rs index b4da56578c8..ce9f967cc38 100644 --- a/library/alloc/src/slice.rs +++ b/library/alloc/src/slice.rs @@ -16,10 +16,6 @@ use core::cmp::Ordering::{self, Less}; use core::mem::MaybeUninit; #[cfg(not(no_global_oom_handling))] use core::ptr; -#[unstable(feature = "array_chunks", issue = "74985")] -pub use core::slice::ArrayChunks; -#[unstable(feature = "array_chunks", issue = "74985")] -pub use core::slice::ArrayChunksMut; #[unstable(feature = "array_windows", issue = "75027")] pub use core::slice::ArrayWindows; #[stable(feature = "inherent_ascii_escape", since = "1.60.0")] diff --git a/library/alloc/src/string.rs b/library/alloc/src/string.rs index a189c00a6b6..d58240f3051 100644 --- a/library/alloc/src/string.rs +++ b/library/alloc/src/string.rs @@ -787,12 +787,12 @@ impl String { #[cfg(not(no_global_oom_handling))] #[unstable(feature = "str_from_utf16_endian", issue = "116258")] pub fn from_utf16le(v: &[u8]) -> Result<String, FromUtf16Error> { - if v.len() % 2 != 0 { + let (chunks, []) = v.as_chunks::<2>() else { return Err(FromUtf16Error(())); - } + }; match (cfg!(target_endian = "little"), unsafe { v.align_to::<u16>() }) { (true, ([], v, [])) => Self::from_utf16(v), - _ => char::decode_utf16(v.array_chunks::<2>().copied().map(u16::from_le_bytes)) + _ => char::decode_utf16(chunks.iter().copied().map(u16::from_le_bytes)) .collect::<Result<_, _>>() .map_err(|_| FromUtf16Error(())), } @@ -830,11 +830,11 @@ impl String { (true, ([], v, [])) => Self::from_utf16_lossy(v), (true, ([], v, [_remainder])) => Self::from_utf16_lossy(v) + "\u{FFFD}", _ => { - let mut iter = v.array_chunks::<2>(); - let string = char::decode_utf16(iter.by_ref().copied().map(u16::from_le_bytes)) + let (chunks, remainder) = v.as_chunks::<2>(); + let string = char::decode_utf16(chunks.iter().copied().map(u16::from_le_bytes)) .map(|r| r.unwrap_or(char::REPLACEMENT_CHARACTER)) .collect(); - if iter.remainder().is_empty() { string } else { string + "\u{FFFD}" } + if remainder.is_empty() { string } else { string + "\u{FFFD}" } } } } @@ -862,12 +862,12 @@ impl String { #[cfg(not(no_global_oom_handling))] #[unstable(feature = "str_from_utf16_endian", issue = "116258")] pub fn from_utf16be(v: &[u8]) -> Result<String, FromUtf16Error> { - if v.len() % 2 != 0 { + let (chunks, []) = v.as_chunks::<2>() else { return Err(FromUtf16Error(())); - } + }; match (cfg!(target_endian = "big"), unsafe { v.align_to::<u16>() }) { (true, ([], v, [])) => Self::from_utf16(v), - _ => char::decode_utf16(v.array_chunks::<2>().copied().map(u16::from_be_bytes)) + _ => char::decode_utf16(chunks.iter().copied().map(u16::from_be_bytes)) .collect::<Result<_, _>>() .map_err(|_| FromUtf16Error(())), } @@ -905,11 +905,11 @@ impl String { (true, ([], v, [])) => Self::from_utf16_lossy(v), (true, ([], v, [_remainder])) => Self::from_utf16_lossy(v) + "\u{FFFD}", _ => { - let mut iter = v.array_chunks::<2>(); - let string = char::decode_utf16(iter.by_ref().copied().map(u16::from_be_bytes)) + let (chunks, remainder) = v.as_chunks::<2>(); + let string = char::decode_utf16(chunks.iter().copied().map(u16::from_be_bytes)) .map(|r| r.unwrap_or(char::REPLACEMENT_CHARACTER)) .collect(); - if iter.remainder().is_empty() { string } else { string + "\u{FFFD}" } + if remainder.is_empty() { string } else { string + "\u{FFFD}" } } } } diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 9856e9c18ec..ce74615dbcc 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -2046,6 +2046,38 @@ impl<T, A: Allocator> Vec<T, A> { #[stable(feature = "rust1", since = "1.0.0")] #[track_caller] pub fn insert(&mut self, index: usize, element: T) { + let _ = self.insert_mut(index, element); + } + + /// Inserts an element at position `index` within the vector, shifting all + /// elements after it to the right, and returning a reference to the new + /// element. + /// + /// # Panics + /// + /// Panics if `index > len`. + /// + /// # Examples + /// + /// ``` + /// #![feature(push_mut)] + /// let mut vec = vec![1, 3, 5, 9]; + /// let x = vec.insert_mut(3, 6); + /// *x += 1; + /// assert_eq!(vec, [1, 3, 5, 7, 9]); + /// ``` + /// + /// # Time complexity + /// + /// Takes *O*([`Vec::len`]) time. All items after the insertion index must be + /// shifted to the right. In the worst case, all elements are shifted when + /// the insertion index is 0. + #[cfg(not(no_global_oom_handling))] + #[inline] + #[unstable(feature = "push_mut", issue = "135974")] + #[track_caller] + #[must_use = "if you don't need a reference to the value, use `Vec::insert` instead"] + pub fn insert_mut(&mut self, index: usize, element: T) -> &mut T { #[cold] #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))] #[track_caller] @@ -2067,8 +2099,8 @@ impl<T, A: Allocator> Vec<T, A> { unsafe { // infallible // The spot to put the new value + let p = self.as_mut_ptr().add(index); { - let p = self.as_mut_ptr().add(index); if index < len { // Shift everything over to make space. (Duplicating the // `index`th element into two consecutive places.) @@ -2079,6 +2111,7 @@ impl<T, A: Allocator> Vec<T, A> { ptr::write(p, element); } self.set_len(len + 1); + &mut *p } } @@ -2486,18 +2519,7 @@ impl<T, A: Allocator> Vec<T, A> { #[rustc_confusables("push_back", "put", "append")] #[track_caller] pub fn push(&mut self, value: T) { - // Inform codegen that the length does not change across grow_one(). - let len = self.len; - // This will panic or abort if we would allocate > isize::MAX bytes - // or if the length increment would overflow for zero-sized types. - if len == self.buf.capacity() { - self.buf.grow_one(); - } - unsafe { - let end = self.as_mut_ptr().add(len); - ptr::write(end, value); - self.len = len + 1; - } + let _ = self.push_mut(value); } /// Appends an element if there is sufficient spare capacity, otherwise an error is returned @@ -2538,6 +2560,77 @@ impl<T, A: Allocator> Vec<T, A> { #[inline] #[unstable(feature = "vec_push_within_capacity", issue = "100486")] pub fn push_within_capacity(&mut self, value: T) -> Result<(), T> { + self.push_mut_within_capacity(value).map(|_| ()) + } + + /// Appends an element to the back of a collection, returning a reference to it. + /// + /// # Panics + /// + /// Panics if the new capacity exceeds `isize::MAX` _bytes_. + /// + /// # Examples + /// + /// ``` + /// #![feature(push_mut)] + /// + /// + /// let mut vec = vec![1, 2]; + /// let last = vec.push_mut(3); + /// assert_eq!(*last, 3); + /// assert_eq!(vec, [1, 2, 3]); + /// + /// let last = vec.push_mut(3); + /// *last += 1; + /// assert_eq!(vec, [1, 2, 3, 4]); + /// ``` + /// + /// # Time complexity + /// + /// Takes amortized *O*(1) time. If the vector's length would exceed its + /// capacity after the push, *O*(*capacity*) time is taken to copy the + /// vector's elements to a larger allocation. This expensive operation is + /// offset by the *capacity* *O*(1) insertions it allows. + #[cfg(not(no_global_oom_handling))] + #[inline] + #[unstable(feature = "push_mut", issue = "135974")] + #[track_caller] + #[must_use = "if you don't need a reference to the value, use `Vec::push` instead"] + pub fn push_mut(&mut self, value: T) -> &mut T { + // Inform codegen that the length does not change across grow_one(). + let len = self.len; + // This will panic or abort if we would allocate > isize::MAX bytes + // or if the length increment would overflow for zero-sized types. + if len == self.buf.capacity() { + self.buf.grow_one(); + } + unsafe { + let end = self.as_mut_ptr().add(len); + ptr::write(end, value); + self.len = len + 1; + // SAFETY: We just wrote a value to the pointer that will live the lifetime of the reference. + &mut *end + } + } + + /// Appends an element and returns a reference to it if there is sufficient spare capacity, + /// otherwise an error is returned with the element. + /// + /// Unlike [`push_mut`] this method will not reallocate when there's insufficient capacity. + /// The caller should use [`reserve`] or [`try_reserve`] to ensure that there is enough capacity. + /// + /// [`push_mut`]: Vec::push_mut + /// [`reserve`]: Vec::reserve + /// [`try_reserve`]: Vec::try_reserve + /// + /// # Time complexity + /// + /// Takes *O*(1) time. + #[unstable(feature = "push_mut", issue = "135974")] + // #[unstable(feature = "vec_push_within_capacity", issue = "100486")] + #[inline] + #[must_use = "if you don't need a reference to the value, use `Vec::push_within_capacity` instead"] + pub fn push_mut_within_capacity(&mut self, value: T) -> Result<&mut T, T> { if self.len == self.buf.capacity() { return Err(value); } @@ -2545,8 +2638,9 @@ impl<T, A: Allocator> Vec<T, A> { let end = self.as_mut_ptr().add(self.len); ptr::write(end, value); self.len += 1; + // SAFETY: We just wrote a value to the pointer that will live the lifetime of the reference. + Ok(&mut *end) } - Ok(()) } /// Removes the last element from a vector and returns it, or [`None`] if it |