1 // SPDX-License-Identifier: GPL-2.0
73 /// For non-zero-sized values, a [`Vec`] will use the given allocator `A` for its allocation. For
76 /// For zero-sized types the [`Vec`]'s pointer must be `dangling_mut::<T>`; no memory is allocated.
83 /// A [`Vec`] can be deconstructed into and (re-)constructed from its previously named raw parts
86 /// [`Vec`]'s backing buffer gets, if required, automatically increased (re-allocated) when elements
91 /// - `self.ptr` is always properly aligned and either points to memory allocated with `A` or, for
92 ///   zero-sized types, is a dangling, well aligned pointer.
94 /// - `self.len` always represents the exact number of elements stored in the vector.
96 /// - `self.layout` represents the absolute number of elements that can be stored within the vector
97 ///   without re-allocation. For ZSTs `self.layout`'s capacity is zero. However, it is legal for the
100 /// - `self.len()` is always less than or equal to `self.capacity()`.
102 /// - The `Allocator` type `A` of the vector is the exact same `Allocator` type the backing buffer
175     const fn is_zst() -> bool {  in is_zst()
181     pub const fn capacity(&self) -> usize {  in capacity()
191     pub const fn len(&self) -> usize {  in len()
199     /// - `additional` must be less than or equal to `self.capacity - self.len`.
200     /// - All elements within the interval [`self.len`,`self.len + additional`) must be initialized.
204         debug_assert!(additional <= self.capacity() - self.len());  in inc_len()
217     /// - `count` must be less than or equal to `self.len`.
218     unsafe fn dec_len(&mut self, count: usize) -> &mut [T] {  in dec_len()
220         // INVARIANT: We relinquish ownership of the elements within the range `[self.len - count,  in dec_len()
223         self.len -= count;  in dec_len()
241     pub fn as_slice(&self) -> &[T] {  in as_slice()
247     pub fn as_mut_slice(&mut self) -> &mut [T] {  in as_mut_slice()
254     pub fn as_mut_ptr(&mut self) -> *mut T {  in as_mut_ptr()
261     pub const fn as_ptr(&self) -> *const T {  in as_ptr()
277     pub const fn is_empty(&self) -> bool {  in is_empty()
285     pub const fn new() -> Self {  in new()
287         // - `ptr` is a properly aligned dangling pointer for type `T`,  in new()
288         // - `layout` is an empty `ArrayLayout` (zero capacity)  in new()
289         // - `len` is zero, since no elements can be or have been stored,  in new()
290         // - `A` is always valid.  in new()
300     pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {  in spare_capacity_mut()
302         // - `self.len` is smaller than `self.capacity` by the type invariant and hence, the  in spare_capacity_mut()
304         // - `self.len` can not overflow `isize`.  in spare_capacity_mut()
309         unsafe { slice::from_raw_parts_mut(ptr, self.capacity() - self.len) }  in spare_capacity_mut()
325     pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {  in push()
348     pub fn push_within_capacity(&mut self, v: T) -> Result<(), PushError<T>> {  in push_within_capacity()
350             // SAFETY: The length is less than the capacity.  in push_within_capacity()
362     /// The length must be less than the capacity.
366         // SAFETY: By the safety requirements, `spare` is non-empty.  in push_within_capacity_unchecked()
371         // the length is less than the capacity at the beginning of this function.  in push_within_capacity_unchecked()
399     ) -> Result<(), InsertError<T>> {  in insert_within_capacity()
414         // Since the length is less than the capacity, both ranges are in bounds of the allocation.  in insert_within_capacity()
415         unsafe { ptr::copy(p, p.add(1), len - index) };  in insert_within_capacity()
417         // SAFETY: The pointer is in-bounds of the allocation.  in insert_within_capacity()
439     pub fn pop(&mut self) -> Option<T> {  in pop()
465     pub fn remove(&mut self, i: usize) -> Result<T, RemoveError> {  in remove()
475         // SAFETY: We checked that `i` is in-bounds.  in remove()
480         // SAFETY: `p.add(1).add(self.len - i - 1)` is `i+1+len-i-1 == len` elements after the  in remove()
481         // beginning of the vector, so this is in-bounds of the vector's allocation.  in remove()
482         unsafe { ptr::copy(p.add(1), p, self.len - i - 1) };  in remove()
501     pub fn with_capacity(capacity: usize, flags: Flags) -> Result<Self, AllocError> {  in with_capacity()
537     /// - `ptr` must be a dangling, well aligned pointer.
541     /// - `ptr` must have been allocated with the allocator `A`.
542     /// - `ptr` must satisfy or exceed the alignment requirements of `T`.
543     /// - `ptr` must point to memory with a size of at least `size_of::<T>() * capacity` bytes.
544     /// - The allocated size in bytes must not be larger than `isize::MAX`.
545     /// - `length` must be less than or equal to `capacity`.
546     /// - The first `length` elements must be initialized values of type `T`.
550     pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {  in from_raw_parts()
573     /// This will not run the destructor of the contained elements and for non-ZSTs the allocation
576     pub fn into_raw_parts(self) -> (*mut T, usize, usize) {  in into_raw_parts()
622     pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> {  in reserve()
626         if cap - len >= additional {  in reserve()
641         // - `ptr` is valid because it's either `None` or comes from a previous call to  in reserve()
643         // - `self.layout` matches the `ArrayLayout` of the preceding allocation.  in reserve()
655         // - `layout` is some `ArrayLayout::<T>`,  in reserve()
656         // - `ptr` has been created by `A::realloc` from `layout`.  in reserve()
680             // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or  in truncate()
704     pub fn drain_all(&mut self) -> DrainAll<'_, T> {  in drain_all()
724     pub fn retain(&mut self, mut f: impl FnMut(&mut T) -> bool) {  in retain()
740     pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), AllocError> {  in extend_with()
749         for item in spare.iter_mut().take(n - 1) {  in extend_with()
754         spare[n - 1].write(value);  in extend_with()
757         // - `self.len() + n < self.capacity()` due to the call to reserve above,  in extend_with()
758         // - the loop and the line above initialized the next `n` elements.  in extend_with()
779     pub fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError> {  in extend_from_slice()
786         // - `other.len()` spare entries have just been initialized, so it is safe to increase  in extend_from_slice()
788         // - `self.len() + other.len() <= self.capacity()` is guaranteed by the preceding `reserve`  in extend_from_slice()
795     pub fn from_elem(value: T, n: usize, flags: Flags) -> Result<Self, AllocError> {  in from_elem()
820     pub fn resize(&mut self, new_len: usize, value: T, flags: Flags) -> Result<(), AllocError> {  in resize()
845         // - `self.ptr` was previously allocated with `A`.  in drop()
846         // - `self.layout` matches the `ArrayLayout` of the preceding allocation.  in drop()
855     fn from(b: Box<[T; N], A>) -> Vec<T, A> {  in from()
860         // - `b` has been allocated with `A`,
861         // - `ptr` fulfills the alignment requirements for `T`,
862         // - `ptr` points to memory with at least a size of `size_of::<T>() * len`,
863         // - all elements within `b` are initialized values of `T`,
864         // - `len` does not exceed `isize::MAX`.
871     fn default() -> Self {  in default()
877     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {  in fmt()
889     fn deref(&self) -> &[T] {  in deref()
901     fn deref_mut(&mut self) -> &mut [T] {  in deref_mut()
929     fn borrow(&self) -> &[T] {  in borrow()
955     fn borrow_mut(&mut self) -> &mut [T] {  in borrow_mut()
969     fn index(&self, index: I) -> &Self::Output {  in index()
979     fn index_mut(&mut self, index: I) -> &mut Self::Output {  in index_mut()
992                 fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] }
1017     fn into_iter(self) -> Self::IntoIter {  in into_iter()
1029     fn into_iter(self) -> Self::IntoIter {  in into_iter()
1059     fn page_iter(&mut self) -> Self::Iter<'_> {  in page_iter()
1064         // - `ptr` is a valid pointer to the beginning of a `Vmalloc` allocation.  in page_iter()
1065         // - `ptr` is guaranteed to be valid for the lifetime of `'a`.  in page_iter()
1066         // - `size` is the size of the `Vmalloc` allocation `ptr` points to.  in page_iter()
1096     fn into_raw_parts(self) -> (*mut T, NonNull<T>, usize, usize) {  in into_raw_parts()
1126     /// - Rust's specialization feature is unstable. This prevents us to optimize for the special
1128     /// - We also can't use `I::IntoIter`'s type ID either to work around this, since `FromIterator`
1130     /// - `FromIterator::from_iter` does return `Self` instead of `Result<Self, AllocError>`, hence
1132     /// - Neither `Iterator::collect` nor `FromIterator::from_iter` can handle additional allocation
1138     /// Note that `IntoIter::collect` doesn't require `Flags`, since it re-uses the existing backing
1140     pub fn collect(self, flags: Flags) -> Vec<T, A> {  in collect()
1149             // - `ptr` is valid for reads of `len * size_of::<T>()` bytes,  in collect()
1150             // - `buf.as_ptr()` is valid for writes of `len * size_of::<T>()` bytes,  in collect()
1151             // - `ptr` and `buf.as_ptr()` are not be subject to aliasing restrictions relative to  in collect()
1153             // - both `ptr` and `buf.ptr()` are properly aligned.  in collect()
1186         // - `ptr` is guaranteed to point to the start of the backing buffer.  in collect()
1187         // - `cap` is either the original capacity or, after shrinking the buffer, equal to `len`.  in collect()
1188         // - `alloc` is guaranteed to be unchanged since `into_iter` has been called on the original  in collect()
1213     fn next(&mut self) -> Option<T> {  in next()
1224         self.len -= 1;  in next()
1238     /// assert_eq!(iter.size_hint().0, size - 1);
1241     /// assert_eq!(iter.size_hint().0, size - 2);
1244     /// assert_eq!(iter.size_hint().0, size - 3);
1248     fn size_hint(&self) -> (usize, Option<usize>) {  in size_hint()
1262         // - `self.buf` was previously allocated with `A`.  in drop()
1263         // - `self.layout` matches the `ArrayLayout` of the preceding allocation.  in drop()
1304     fn into_iter(self) -> Self::IntoIter {  in into_iter()
1332     fn next(&mut self) -> Option<T> {  in next()
1338     fn size_hint(&self) -> (usize, Option<usize>) {  in size_hint()
1381             let mut carry = true;  in test_kvec_retain()  localVariable
1383                 let new_v = carry != *v;  in test_kvec_retain()
1384                 carry = carry && *v;  in test_kvec_retain()
1390         // behaves correctly for all possible boolean arrays of every possible length less than  in test_kvec_retain()