Lines Matching +full:exact +full:- +full:len
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
111 len: usize, field
175 const fn is_zst() -> bool { in is_zst()
181 pub const fn capacity(&self) -> usize { in capacity()
185 self.layout.len() in capacity()
191 pub const fn len(&self) -> usize { in len() function
192 self.len in len()
195 /// Increments `self.len` by `additional`.
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()
205 // INVARIANT: By the safety requirements of this method this represents the exact number of in inc_len()
207 self.len += additional; in inc_len()
210 /// Decreases `self.len` by `count`.
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()
219 debug_assert!(count <= self.len()); in dec_len()
220 // INVARIANT: We relinquish ownership of the elements within the range `[self.len - count, in dec_len()
221 // self.len)`, hence the updated value of `set.len` represents the exact number of elements in dec_len()
223 self.len -= count; in dec_len()
224 // SAFETY: The memory after `self.len()` is guaranteed to contain `count` initialized in dec_len()
226 unsafe { slice::from_raw_parts_mut(self.as_mut_ptr().add(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()
278 self.len() == 0 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()
294 len: 0, 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()
305 let ptr = unsafe { self.as_mut_ptr().add(self.len) }.cast::<MaybeUninit<T>>(); in spare_capacity_mut()
307 // SAFETY: The memory between `self.len` and `self.capacity` is guaranteed to be allocated 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()
349 if self.len() < self.capacity() { in push_within_capacity()
366 // SAFETY: By the safety requirements, `spare` is non-empty. in push_within_capacity_unchecked()
399 ) -> Result<(), InsertError<T>> { in insert_within_capacity()
400 let len = self.len(); in insert_within_capacity() localVariable
401 if index > len { in insert_within_capacity()
405 if len >= self.capacity() { in insert_within_capacity()
409 // SAFETY: This is in bounds since `index <= len < capacity`. 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()
419 // SAFETY: Index `len` contains a valid element due to the above copy and write. 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()
517 /// let (mut ptr, mut len, cap) = v.into_raw_parts();
520 /// unsafe { ptr.add(len).write(4) };
521 /// len += 1;
525 /// // from the exact same raw parts.
526 /// let v = unsafe { KVec::from_raw_parts(ptr, len, cap) };
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`.
549 /// `cap` and `len`.
550 pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self { in from_raw_parts()
566 len: length, 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()
578 let len = me.len(); in into_raw_parts() localVariable
581 (ptr, len, capacity) in into_raw_parts()
622 pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> { in reserve()
623 let len = self.len(); in reserve() localVariable
626 if cap - len >= additional { in reserve()
637 let new_cap = core::cmp::max(cap * 2, len.checked_add(additional).ok_or(AllocError)?); 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()
663 /// Shortens the vector, setting the length to `len` and drops the removed values.
664 /// If `len` is greater than or equal to the current length, this does nothing.
673 /// assert_eq!(v.len(), 1);
678 pub fn truncate(&mut self, len: usize) { in truncate()
679 if let Some(count) = self.len().checked_sub(len) { in truncate()
680 // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or in truncate()
681 // equal to `self.len()`. in truncate()
704 pub fn drain_all(&mut self) -> DrainAll<'_, T> { in drain_all()
706 let elems = unsafe { self.dec_len(self.len()) }; in drain_all()
707 // INVARIANT: The first `len` elements of the spare capacity are valid values, and as we 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()
780 self.reserve(other.len(), flags)?; 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()
790 unsafe { self.inc_len(other.len()) }; in extend_from_slice()
795 pub fn from_elem(value: T, n: usize, flags: Flags) -> Result<Self, AllocError> { in from_elem()
803 /// Resizes the [`Vec`] so that `len` is equal to `new_len`.
805 /// If `new_len` is smaller than `len`, the `Vec` is [`Vec::truncate`]d.
820 pub fn resize(&mut self, new_len: usize, value: T, flags: Flags) -> Result<(), AllocError> { in resize()
821 match new_len.checked_sub(self.len()) { in resize()
840 self.len, in drop()
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()
856 let len = b.len(); localVariable
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`.
865 unsafe { Vec::from_raw_parts(ptr.cast(), len, len) }
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()
890 // SAFETY: The memory behind `self.as_ptr()` is guaranteed to contain `self.len` in deref()
892 unsafe { slice::from_raw_parts(self.as_ptr(), self.len) } in deref()
901 fn deref_mut(&mut self) -> &mut [T] { in deref_mut()
902 // SAFETY: The memory behind `self.as_ptr()` is guaranteed to contain `self.len` in deref_mut()
904 unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) } 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()
1087 len: usize, field
1096 fn into_raw_parts(self) -> (*mut T, NonNull<T>, usize, usize) { in into_raw_parts()
1100 let len = me.len; in into_raw_parts() localVariable
1101 let cap = me.layout.len(); in into_raw_parts()
1102 (ptr, buf, len, cap) 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()
1142 let (mut ptr, buf, len, mut cap) = self.into_raw_parts(); 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()
1154 unsafe { ptr::copy(ptr, buf.as_ptr(), len) }; in collect()
1157 // SAFETY: `len` is guaranteed to be smaller than `self.layout.len()` by the type in collect()
1159 let layout = unsafe { ArrayLayout::<T>::new_unchecked(len) }; in collect()
1161 // SAFETY: `buf` points to the start of the backing buffer and `len` is guaranteed by in collect()
1177 cap = len; in collect()
1184 // the beginning of the buffer and `len` has been adjusted accordingly. 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()
1190 unsafe { Vec::from_raw_parts(ptr, len, cap) } in collect()
1213 fn next(&mut self) -> Option<T> { in next()
1214 if self.len == 0 { in next()
1220 // SAFETY: We can't overflow; decreasing `self.len` by one every time we advance `self.ptr` 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()
1249 (self.len, Some(self.len)) in size_hint()
1259 unsafe { ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr, self.len)) }; in drop()
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()
1307 let (ptr, len, _) = self.into_raw_parts(); in into_iter()
1312 len, in into_iter()
1332 fn next(&mut self) -> Option<T> { in next()
1338 fn size_hint(&self) -> (usize, Option<usize>) { in size_hint()
1364 let mut vec1: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap(); in test_kvec_retain()
1365 let mut vec2: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap(); in test_kvec_retain()
1367 for i in 0..c.len() { in test_kvec_retain()
1393 for len in 0..10 { in test_kvec_retain()
1394 for _ in 0u32..1u32 << len { in test_kvec_retain()