| // SPDX-License-Identifier: GPL-2.0 |
| |
| //! Implementation of [`Vec`]. |
| |
| use super::{ |
| allocator::{KVmalloc, Kmalloc, Vmalloc}, |
| layout::ArrayLayout, |
| AllocError, Allocator, Box, Flags, |
| }; |
| use core::{ |
| borrow::{Borrow, BorrowMut}, |
| fmt, |
| marker::PhantomData, |
| mem::{ManuallyDrop, MaybeUninit}, |
| ops::Deref, |
| ops::DerefMut, |
| ops::Index, |
| ops::IndexMut, |
| ptr, |
| ptr::NonNull, |
| slice, |
| slice::SliceIndex, |
| }; |
| |
| mod errors; |
| pub use self::errors::{InsertError, PushError, RemoveError}; |
| |
| /// Create a [`KVec`] containing the arguments. |
| /// |
| /// New memory is allocated with `GFP_KERNEL`. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = kernel::kvec![]; |
| /// v.push(1, GFP_KERNEL)?; |
| /// assert_eq!(v, [1]); |
| /// |
| /// let mut v = kernel::kvec![1; 3]?; |
| /// v.push(4, GFP_KERNEL)?; |
| /// assert_eq!(v, [1, 1, 1, 4]); |
| /// |
| /// let mut v = kernel::kvec![1, 2, 3]?; |
| /// v.push(4, GFP_KERNEL)?; |
| /// assert_eq!(v, [1, 2, 3, 4]); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| #[macro_export] |
| macro_rules! kvec { |
| () => ( |
| $crate::alloc::KVec::new() |
| ); |
| ($elem:expr; $n:expr) => ( |
| $crate::alloc::KVec::from_elem($elem, $n, GFP_KERNEL) |
| ); |
| ($($x:expr),+ $(,)?) => ( |
| match $crate::alloc::KBox::new_uninit(GFP_KERNEL) { |
| Ok(b) => Ok($crate::alloc::KVec::from($crate::alloc::KBox::write(b, [$($x),+]))), |
| Err(e) => Err(e), |
| } |
| ); |
| } |
| |
| /// The kernel's [`Vec`] type. |
| /// |
| /// A contiguous growable array type with contents allocated with the kernel's allocators (e.g. |
| /// [`Kmalloc`], [`Vmalloc`] or [`KVmalloc`]), written `Vec<T, A>`. |
| /// |
| /// For non-zero-sized values, a [`Vec`] will use the given allocator `A` for its allocation. For |
| /// the most common allocators the type aliases [`KVec`], [`VVec`] and [`KVVec`] exist. |
| /// |
| /// For zero-sized types the [`Vec`]'s pointer must be `dangling_mut::<T>`; no memory is allocated. |
| /// |
| /// Generally, [`Vec`] consists of a pointer that represents the vector's backing buffer, the |
| /// capacity of the vector (the number of elements that currently fit into the vector), its length |
| /// (the number of elements that are currently stored in the vector) and the `Allocator` type used |
| /// to allocate (and free) the backing buffer. |
| /// |
| /// A [`Vec`] can be deconstructed into and (re-)constructed from its previously named raw parts |
| /// and manually modified. |
| /// |
| /// [`Vec`]'s backing buffer gets, if required, automatically increased (re-allocated) when elements |
| /// are added to the vector. |
| /// |
| /// # Invariants |
| /// |
| /// - `self.ptr` is always properly aligned and either points to memory allocated with `A` or, for |
| /// zero-sized types, is a dangling, well aligned pointer. |
| /// |
| /// - `self.len` always represents the exact number of elements stored in the vector. |
| /// |
| /// - `self.layout` represents the absolute number of elements that can be stored within the vector |
| /// without re-allocation. For ZSTs `self.layout`'s capacity is zero. However, it is legal for the |
| /// backing buffer to be larger than `layout`. |
| /// |
| /// - `self.len()` is always less than or equal to `self.capacity()`. |
| /// |
| /// - The `Allocator` type `A` of the vector is the exact same `Allocator` type the backing buffer |
| /// was allocated with (and must be freed with). |
| pub struct Vec<T, A: Allocator> { |
| ptr: NonNull<T>, |
| /// Represents the actual buffer size as `cap` times `size_of::<T>` bytes. |
| /// |
| /// Note: This isn't quite the same as `Self::capacity`, which in contrast returns the number of |
| /// elements we can still store without reallocating. |
| layout: ArrayLayout<T>, |
| len: usize, |
| _p: PhantomData<A>, |
| } |
| |
| /// Type alias for [`Vec`] with a [`Kmalloc`] allocator. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = KVec::new(); |
| /// v.push(1, GFP_KERNEL)?; |
| /// assert_eq!(&v, &[1]); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub type KVec<T> = Vec<T, Kmalloc>; |
| |
| /// Type alias for [`Vec`] with a [`Vmalloc`] allocator. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = VVec::new(); |
| /// v.push(1, GFP_KERNEL)?; |
| /// assert_eq!(&v, &[1]); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub type VVec<T> = Vec<T, Vmalloc>; |
| |
| /// Type alias for [`Vec`] with a [`KVmalloc`] allocator. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = KVVec::new(); |
| /// v.push(1, GFP_KERNEL)?; |
| /// assert_eq!(&v, &[1]); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub type KVVec<T> = Vec<T, KVmalloc>; |
| |
| // SAFETY: `Vec` is `Send` if `T` is `Send` because `Vec` owns its elements. |
| unsafe impl<T, A> Send for Vec<T, A> |
| where |
| T: Send, |
| A: Allocator, |
| { |
| } |
| |
| // SAFETY: `Vec` is `Sync` if `T` is `Sync` because `Vec` owns its elements. |
| unsafe impl<T, A> Sync for Vec<T, A> |
| where |
| T: Sync, |
| A: Allocator, |
| { |
| } |
| |
| impl<T, A> Vec<T, A> |
| where |
| A: Allocator, |
| { |
| #[inline] |
| const fn is_zst() -> bool { |
| core::mem::size_of::<T>() == 0 |
| } |
| |
| /// Returns the number of elements that can be stored within the vector without allocating |
| /// additional memory. |
| pub fn capacity(&self) -> usize { |
| if const { Self::is_zst() } { |
| usize::MAX |
| } else { |
| self.layout.len() |
| } |
| } |
| |
| /// Returns the number of elements stored within the vector. |
| #[inline] |
| pub fn len(&self) -> usize { |
| self.len |
| } |
| |
| /// Increments `self.len` by `additional`. |
| /// |
| /// # Safety |
| /// |
| /// - `additional` must be less than or equal to `self.capacity - self.len`. |
| /// - All elements within the interval [`self.len`,`self.len + additional`) must be initialized. |
| #[inline] |
| pub unsafe fn inc_len(&mut self, additional: usize) { |
| // Guaranteed by the type invariant to never underflow. |
| debug_assert!(additional <= self.capacity() - self.len()); |
| // INVARIANT: By the safety requirements of this method this represents the exact number of |
| // elements stored within `self`. |
| self.len += additional; |
| } |
| |
| /// Decreases `self.len` by `count`. |
| /// |
| /// Returns a mutable slice to the elements forgotten by the vector. It is the caller's |
| /// responsibility to drop these elements if necessary. |
| /// |
| /// # Safety |
| /// |
| /// - `count` must be less than or equal to `self.len`. |
| unsafe fn dec_len(&mut self, count: usize) -> &mut [T] { |
| debug_assert!(count <= self.len()); |
| // INVARIANT: We relinquish ownership of the elements within the range `[self.len - count, |
| // self.len)`, hence the updated value of `set.len` represents the exact number of elements |
| // stored within `self`. |
| self.len -= count; |
| // SAFETY: The memory after `self.len()` is guaranteed to contain `count` initialized |
| // elements of type `T`. |
| unsafe { slice::from_raw_parts_mut(self.as_mut_ptr().add(self.len), count) } |
| } |
| |
| /// Returns a slice of the entire vector. |
| #[inline] |
| pub fn as_slice(&self) -> &[T] { |
| self |
| } |
| |
| /// Returns a mutable slice of the entire vector. |
| #[inline] |
| pub fn as_mut_slice(&mut self) -> &mut [T] { |
| self |
| } |
| |
| /// Returns a mutable raw pointer to the vector's backing buffer, or, if `T` is a ZST, a |
| /// dangling raw pointer. |
| #[inline] |
| pub fn as_mut_ptr(&mut self) -> *mut T { |
| self.ptr.as_ptr() |
| } |
| |
| /// Returns a raw pointer to the vector's backing buffer, or, if `T` is a ZST, a dangling raw |
| /// pointer. |
| #[inline] |
| pub fn as_ptr(&self) -> *const T { |
| self.ptr.as_ptr() |
| } |
| |
| /// Returns `true` if the vector contains no elements, `false` otherwise. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = KVec::new(); |
| /// assert!(v.is_empty()); |
| /// |
| /// v.push(1, GFP_KERNEL); |
| /// assert!(!v.is_empty()); |
| /// ``` |
| #[inline] |
| pub fn is_empty(&self) -> bool { |
| self.len() == 0 |
| } |
| |
| /// Creates a new, empty `Vec<T, A>`. |
| /// |
| /// This method does not allocate by itself. |
| #[inline] |
| pub const fn new() -> Self { |
| // INVARIANT: Since this is a new, empty `Vec` with no backing memory yet, |
| // - `ptr` is a properly aligned dangling pointer for type `T`, |
| // - `layout` is an empty `ArrayLayout` (zero capacity) |
| // - `len` is zero, since no elements can be or have been stored, |
| // - `A` is always valid. |
| Self { |
| ptr: NonNull::dangling(), |
| layout: ArrayLayout::empty(), |
| len: 0, |
| _p: PhantomData::<A>, |
| } |
| } |
| |
| /// Returns a slice of `MaybeUninit<T>` for the remaining spare capacity of the vector. |
| pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] { |
| // SAFETY: |
| // - `self.len` is smaller than `self.capacity` by the type invariant and hence, the |
| // resulting pointer is guaranteed to be part of the same allocated object. |
| // - `self.len` can not overflow `isize`. |
| let ptr = unsafe { self.as_mut_ptr().add(self.len) }.cast::<MaybeUninit<T>>(); |
| |
| // SAFETY: The memory between `self.len` and `self.capacity` is guaranteed to be allocated |
| // and valid, but uninitialized. |
| unsafe { slice::from_raw_parts_mut(ptr, self.capacity() - self.len) } |
| } |
| |
| /// Appends an element to the back of the [`Vec`] instance. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = KVec::new(); |
| /// v.push(1, GFP_KERNEL)?; |
| /// assert_eq!(&v, &[1]); |
| /// |
| /// v.push(2, GFP_KERNEL)?; |
| /// assert_eq!(&v, &[1, 2]); |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> { |
| self.reserve(1, flags)?; |
| // SAFETY: The call to `reserve` was successful, so the capacity is at least one greater |
| // than the length. |
| unsafe { self.push_within_capacity_unchecked(v) }; |
| Ok(()) |
| } |
| |
| /// Appends an element to the back of the [`Vec`] instance without reallocating. |
| /// |
| /// Fails if the vector does not have capacity for the new element. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = KVec::with_capacity(10, GFP_KERNEL)?; |
| /// for i in 0..10 { |
| /// v.push_within_capacity(i)?; |
| /// } |
| /// |
| /// assert!(v.push_within_capacity(10).is_err()); |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub fn push_within_capacity(&mut self, v: T) -> Result<(), PushError<T>> { |
| if self.len() < self.capacity() { |
| // SAFETY: The length is less than the capacity. |
| unsafe { self.push_within_capacity_unchecked(v) }; |
| Ok(()) |
| } else { |
| Err(PushError(v)) |
| } |
| } |
| |
| /// Appends an element to the back of the [`Vec`] instance without reallocating. |
| /// |
| /// # Safety |
| /// |
| /// The length must be less than the capacity. |
| unsafe fn push_within_capacity_unchecked(&mut self, v: T) { |
| let spare = self.spare_capacity_mut(); |
| |
| // SAFETY: By the safety requirements, `spare` is non-empty. |
| unsafe { spare.get_unchecked_mut(0) }.write(v); |
| |
| // SAFETY: We just initialised the first spare entry, so it is safe to increase the length |
| // by 1. We also know that the new length is <= capacity because the caller guarantees that |
| // the length is less than the capacity at the beginning of this function. |
| unsafe { self.inc_len(1) }; |
| } |
| |
| /// Inserts an element at the given index in the [`Vec`] instance. |
| /// |
| /// Fails if the vector does not have capacity for the new element. Panics if the index is out |
| /// of bounds. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use kernel::alloc::kvec::InsertError; |
| /// |
| /// let mut v = KVec::with_capacity(5, GFP_KERNEL)?; |
| /// for i in 0..5 { |
| /// v.insert_within_capacity(0, i)?; |
| /// } |
| /// |
| /// assert!(matches!(v.insert_within_capacity(0, 5), Err(InsertError::OutOfCapacity(_)))); |
| /// assert!(matches!(v.insert_within_capacity(1000, 5), Err(InsertError::IndexOutOfBounds(_)))); |
| /// assert_eq!(v, [4, 3, 2, 1, 0]); |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub fn insert_within_capacity( |
| &mut self, |
| index: usize, |
| element: T, |
| ) -> Result<(), InsertError<T>> { |
| let len = self.len(); |
| if index > len { |
| return Err(InsertError::IndexOutOfBounds(element)); |
| } |
| |
| if len >= self.capacity() { |
| return Err(InsertError::OutOfCapacity(element)); |
| } |
| |
| // SAFETY: This is in bounds since `index <= len < capacity`. |
| let p = unsafe { self.as_mut_ptr().add(index) }; |
| // INVARIANT: This breaks the Vec invariants by making `index` contain an invalid element, |
| // but we restore the invariants below. |
| // SAFETY: Both the src and dst ranges end no later than one element after the length. |
| // Since the length is less than the capacity, both ranges are in bounds of the allocation. |
| unsafe { ptr::copy(p, p.add(1), len - index) }; |
| // INVARIANT: This restores the Vec invariants. |
| // SAFETY: The pointer is in-bounds of the allocation. |
| unsafe { ptr::write(p, element) }; |
| // SAFETY: Index `len` contains a valid element due to the above copy and write. |
| unsafe { self.inc_len(1) }; |
| Ok(()) |
| } |
| |
| /// Removes the last element from a vector and returns it, or `None` if it is empty. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = KVec::new(); |
| /// v.push(1, GFP_KERNEL)?; |
| /// v.push(2, GFP_KERNEL)?; |
| /// assert_eq!(&v, &[1, 2]); |
| /// |
| /// assert_eq!(v.pop(), Some(2)); |
| /// assert_eq!(v.pop(), Some(1)); |
| /// assert_eq!(v.pop(), None); |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub fn pop(&mut self) -> Option<T> { |
| if self.is_empty() { |
| return None; |
| } |
| |
| let removed: *mut T = { |
| // SAFETY: We just checked that the length is at least one. |
| let slice = unsafe { self.dec_len(1) }; |
| // SAFETY: The argument to `dec_len` was 1 so this returns a slice of length 1. |
| unsafe { slice.get_unchecked_mut(0) } |
| }; |
| |
| // SAFETY: The guarantees of `dec_len` allow us to take ownership of this value. |
| Some(unsafe { removed.read() }) |
| } |
| |
| /// Removes the element at the given index. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = kernel::kvec![1, 2, 3]?; |
| /// assert_eq!(v.remove(1)?, 2); |
| /// assert_eq!(v, [1, 3]); |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub fn remove(&mut self, i: usize) -> Result<T, RemoveError> { |
| let value = { |
| let value_ref = self.get(i).ok_or(RemoveError)?; |
| // INVARIANT: This breaks the invariants by invalidating the value at index `i`, but we |
| // restore the invariants below. |
| // SAFETY: The value at index `i` is valid, because otherwise we would have already |
| // failed with `RemoveError`. |
| unsafe { ptr::read(value_ref) } |
| }; |
| |
| // SAFETY: We checked that `i` is in-bounds. |
| let p = unsafe { self.as_mut_ptr().add(i) }; |
| |
| // INVARIANT: After this call, the invalid value is at the last slot, so the Vec invariants |
| // are restored after the below call to `dec_len(1)`. |
| // SAFETY: `p.add(1).add(self.len - i - 1)` is `i+1+len-i-1 == len` elements after the |
| // beginning of the vector, so this is in-bounds of the vector's allocation. |
| unsafe { ptr::copy(p.add(1), p, self.len - i - 1) }; |
| |
| // SAFETY: Since the check at the beginning of this call did not fail with `RemoveError`, |
| // the length is at least one. |
| unsafe { self.dec_len(1) }; |
| |
| Ok(value) |
| } |
| |
| /// Creates a new [`Vec`] instance with at least the given capacity. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let v = KVec::<u32>::with_capacity(20, GFP_KERNEL)?; |
| /// |
| /// assert!(v.capacity() >= 20); |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub fn with_capacity(capacity: usize, flags: Flags) -> Result<Self, AllocError> { |
| let mut v = Vec::new(); |
| |
| v.reserve(capacity, flags)?; |
| |
| Ok(v) |
| } |
| |
| /// Creates a `Vec<T, A>` from a pointer, a length and a capacity using the allocator `A`. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = kernel::kvec![1, 2, 3]?; |
| /// v.reserve(1, GFP_KERNEL)?; |
| /// |
| /// let (mut ptr, mut len, cap) = v.into_raw_parts(); |
| /// |
| /// // SAFETY: We've just reserved memory for another element. |
| /// unsafe { ptr.add(len).write(4) }; |
| /// len += 1; |
| /// |
| /// // SAFETY: We only wrote an additional element at the end of the `KVec`'s buffer and |
| /// // correspondingly increased the length of the `KVec` by one. Otherwise, we construct it |
| /// // from the exact same raw parts. |
| /// let v = unsafe { KVec::from_raw_parts(ptr, len, cap) }; |
| /// |
| /// assert_eq!(v, [1, 2, 3, 4]); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| /// |
| /// # Safety |
| /// |
| /// If `T` is a ZST: |
| /// |
| /// - `ptr` must be a dangling, well aligned pointer. |
| /// |
| /// Otherwise: |
| /// |
| /// - `ptr` must have been allocated with the allocator `A`. |
| /// - `ptr` must satisfy or exceed the alignment requirements of `T`. |
| /// - `ptr` must point to memory with a size of at least `size_of::<T>() * capacity` bytes. |
| /// - The allocated size in bytes must not be larger than `isize::MAX`. |
| /// - `length` must be less than or equal to `capacity`. |
| /// - The first `length` elements must be initialized values of type `T`. |
| /// |
| /// It is also valid to create an empty `Vec` passing a dangling pointer for `ptr` and zero for |
| /// `cap` and `len`. |
| pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self { |
| let layout = if Self::is_zst() { |
| ArrayLayout::empty() |
| } else { |
| // SAFETY: By the safety requirements of this function, `capacity * size_of::<T>()` is |
| // smaller than `isize::MAX`. |
| unsafe { ArrayLayout::new_unchecked(capacity) } |
| }; |
| |
| // INVARIANT: For ZSTs, we store an empty `ArrayLayout`, all other type invariants are |
| // covered by the safety requirements of this function. |
| Self { |
| // SAFETY: By the safety requirements, `ptr` is either dangling or pointing to a valid |
| // memory allocation, allocated with `A`. |
| ptr: unsafe { NonNull::new_unchecked(ptr) }, |
| layout, |
| len: length, |
| _p: PhantomData::<A>, |
| } |
| } |
| |
| /// Consumes the `Vec<T, A>` and returns its raw components `pointer`, `length` and `capacity`. |
| /// |
| /// This will not run the destructor of the contained elements and for non-ZSTs the allocation |
| /// will stay alive indefinitely. Use [`Vec::from_raw_parts`] to recover the [`Vec`], drop the |
| /// elements and free the allocation, if any. |
| pub fn into_raw_parts(self) -> (*mut T, usize, usize) { |
| let mut me = ManuallyDrop::new(self); |
| let len = me.len(); |
| let capacity = me.capacity(); |
| let ptr = me.as_mut_ptr(); |
| (ptr, len, capacity) |
| } |
| |
| /// Clears the vector, removing all values. |
| /// |
| /// Note that this method has no effect on the allocated capacity |
| /// of the vector. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = kernel::kvec![1, 2, 3]?; |
| /// |
| /// v.clear(); |
| /// |
| /// assert!(v.is_empty()); |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| #[inline] |
| pub fn clear(&mut self) { |
| self.truncate(0); |
| } |
| |
| /// Ensures that the capacity exceeds the length by at least `additional` elements. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = KVec::new(); |
| /// v.push(1, GFP_KERNEL)?; |
| /// |
| /// v.reserve(10, GFP_KERNEL)?; |
| /// let cap = v.capacity(); |
| /// assert!(cap >= 10); |
| /// |
| /// v.reserve(10, GFP_KERNEL)?; |
| /// let new_cap = v.capacity(); |
| /// assert_eq!(new_cap, cap); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> { |
| let len = self.len(); |
| let cap = self.capacity(); |
| |
| if cap - len >= additional { |
| return Ok(()); |
| } |
| |
| if Self::is_zst() { |
| // The capacity is already `usize::MAX` for ZSTs, we can't go higher. |
| return Err(AllocError); |
| } |
| |
| // We know that `cap <= isize::MAX` because of the type invariants of `Self`. So the |
| // multiplication by two won't overflow. |
| let new_cap = core::cmp::max(cap * 2, len.checked_add(additional).ok_or(AllocError)?); |
| let layout = ArrayLayout::new(new_cap).map_err(|_| AllocError)?; |
| |
| // SAFETY: |
| // - `ptr` is valid because it's either `None` or comes from a previous call to |
| // `A::realloc`. |
| // - `self.layout` matches the `ArrayLayout` of the preceding allocation. |
| let ptr = unsafe { |
| A::realloc( |
| Some(self.ptr.cast()), |
| layout.into(), |
| self.layout.into(), |
| flags, |
| )? |
| }; |
| |
| // INVARIANT: |
| // - `layout` is some `ArrayLayout::<T>`, |
| // - `ptr` has been created by `A::realloc` from `layout`. |
| self.ptr = ptr.cast(); |
| self.layout = layout; |
| |
| Ok(()) |
| } |
| |
| /// Shortens the vector, setting the length to `len` and drops the removed values. |
| /// If `len` is greater than or equal to the current length, this does nothing. |
| /// |
| /// This has no effect on the capacity and will not allocate. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = kernel::kvec![1, 2, 3]?; |
| /// v.truncate(1); |
| /// assert_eq!(v.len(), 1); |
| /// assert_eq!(&v, &[1]); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub fn truncate(&mut self, len: usize) { |
| if let Some(count) = self.len().checked_sub(len) { |
| // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or |
| // equal to `self.len()`. |
| let ptr: *mut [T] = unsafe { self.dec_len(count) }; |
| |
| // SAFETY: the contract of `dec_len` guarantees that the elements in `ptr` are |
| // valid elements whose ownership has been transferred to the caller. |
| unsafe { ptr::drop_in_place(ptr) }; |
| } |
| } |
| |
| /// Takes ownership of all items in this vector without consuming the allocation. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = kernel::kvec![0, 1, 2, 3]?; |
| /// |
| /// for (i, j) in v.drain_all().enumerate() { |
| /// assert_eq!(i, j); |
| /// } |
| /// |
| /// assert!(v.capacity() >= 4); |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub fn drain_all(&mut self) -> DrainAll<'_, T> { |
| // SAFETY: This does not underflow the length. |
| let elems = unsafe { self.dec_len(self.len()) }; |
| // INVARIANT: The first `len` elements of the spare capacity are valid values, and as we |
| // just set the length to zero, we may transfer ownership to the `DrainAll` object. |
| DrainAll { |
| elements: elems.iter_mut(), |
| } |
| } |
| |
| /// Removes all elements that don't match the provided closure. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = kernel::kvec![1, 2, 3, 4]?; |
| /// v.retain(|i| *i % 2 == 0); |
| /// assert_eq!(v, [2, 4]); |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub fn retain(&mut self, mut f: impl FnMut(&mut T) -> bool) { |
| let mut num_kept = 0; |
| let mut next_to_check = 0; |
| while let Some(to_check) = self.get_mut(next_to_check) { |
| if f(to_check) { |
| self.swap(num_kept, next_to_check); |
| num_kept += 1; |
| } |
| next_to_check += 1; |
| } |
| self.truncate(num_kept); |
| } |
| } |
| |
| impl<T: Clone, A: Allocator> Vec<T, A> { |
| /// Extend the vector by `n` clones of `value`. |
| pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), AllocError> { |
| if n == 0 { |
| return Ok(()); |
| } |
| |
| self.reserve(n, flags)?; |
| |
| let spare = self.spare_capacity_mut(); |
| |
| for item in spare.iter_mut().take(n - 1) { |
| item.write(value.clone()); |
| } |
| |
| // We can write the last element directly without cloning needlessly. |
| spare[n - 1].write(value); |
| |
| // SAFETY: |
| // - `self.len() + n < self.capacity()` due to the call to reserve above, |
| // - the loop and the line above initialized the next `n` elements. |
| unsafe { self.inc_len(n) }; |
| |
| Ok(()) |
| } |
| |
| /// Pushes clones of the elements of slice into the [`Vec`] instance. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = KVec::new(); |
| /// v.push(1, GFP_KERNEL)?; |
| /// |
| /// v.extend_from_slice(&[20, 30, 40], GFP_KERNEL)?; |
| /// assert_eq!(&v, &[1, 20, 30, 40]); |
| /// |
| /// v.extend_from_slice(&[50, 60], GFP_KERNEL)?; |
| /// assert_eq!(&v, &[1, 20, 30, 40, 50, 60]); |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError> { |
| self.reserve(other.len(), flags)?; |
| for (slot, item) in core::iter::zip(self.spare_capacity_mut(), other) { |
| slot.write(item.clone()); |
| } |
| |
| // SAFETY: |
| // - `other.len()` spare entries have just been initialized, so it is safe to increase |
| // the length by the same number. |
| // - `self.len() + other.len() <= self.capacity()` is guaranteed by the preceding `reserve` |
| // call. |
| unsafe { self.inc_len(other.len()) }; |
| Ok(()) |
| } |
| |
| /// Create a new `Vec<T, A>` and extend it by `n` clones of `value`. |
| pub fn from_elem(value: T, n: usize, flags: Flags) -> Result<Self, AllocError> { |
| let mut v = Self::with_capacity(n, flags)?; |
| |
| v.extend_with(n, value, flags)?; |
| |
| Ok(v) |
| } |
| |
| /// Resizes the [`Vec`] so that `len` is equal to `new_len`. |
| /// |
| /// If `new_len` is smaller than `len`, the `Vec` is [`Vec::truncate`]d. |
| /// If `new_len` is larger, each new slot is filled with clones of `value`. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let mut v = kernel::kvec![1, 2, 3]?; |
| /// v.resize(1, 42, GFP_KERNEL)?; |
| /// assert_eq!(&v, &[1]); |
| /// |
| /// v.resize(3, 42, GFP_KERNEL)?; |
| /// assert_eq!(&v, &[1, 42, 42]); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub fn resize(&mut self, new_len: usize, value: T, flags: Flags) -> Result<(), AllocError> { |
| match new_len.checked_sub(self.len()) { |
| Some(n) => self.extend_with(n, value, flags), |
| None => { |
| self.truncate(new_len); |
| Ok(()) |
| } |
| } |
| } |
| } |
| |
| impl<T, A> Drop for Vec<T, A> |
| where |
| A: Allocator, |
| { |
| fn drop(&mut self) { |
| // SAFETY: `self.as_mut_ptr` is guaranteed to be valid by the type invariant. |
| unsafe { |
| ptr::drop_in_place(core::ptr::slice_from_raw_parts_mut( |
| self.as_mut_ptr(), |
| self.len, |
| )) |
| }; |
| |
| // SAFETY: |
| // - `self.ptr` was previously allocated with `A`. |
| // - `self.layout` matches the `ArrayLayout` of the preceding allocation. |
| unsafe { A::free(self.ptr.cast(), self.layout.into()) }; |
| } |
| } |
| |
| impl<T, A, const N: usize> From<Box<[T; N], A>> for Vec<T, A> |
| where |
| A: Allocator, |
| { |
| fn from(b: Box<[T; N], A>) -> Vec<T, A> { |
| let len = b.len(); |
| let ptr = Box::into_raw(b); |
| |
| // SAFETY: |
| // - `b` has been allocated with `A`, |
| // - `ptr` fulfills the alignment requirements for `T`, |
| // - `ptr` points to memory with at least a size of `size_of::<T>() * len`, |
| // - all elements within `b` are initialized values of `T`, |
| // - `len` does not exceed `isize::MAX`. |
| unsafe { Vec::from_raw_parts(ptr.cast(), len, len) } |
| } |
| } |
| |
| impl<T, A: Allocator> Default for Vec<T, A> { |
| #[inline] |
| fn default() -> Self { |
| Self::new() |
| } |
| } |
| |
| impl<T: fmt::Debug, A: Allocator> fmt::Debug for Vec<T, A> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| fmt::Debug::fmt(&**self, f) |
| } |
| } |
| |
| impl<T, A> Deref for Vec<T, A> |
| where |
| A: Allocator, |
| { |
| type Target = [T]; |
| |
| #[inline] |
| fn deref(&self) -> &[T] { |
| // SAFETY: The memory behind `self.as_ptr()` is guaranteed to contain `self.len` |
| // initialized elements of type `T`. |
| unsafe { slice::from_raw_parts(self.as_ptr(), self.len) } |
| } |
| } |
| |
| impl<T, A> DerefMut for Vec<T, A> |
| where |
| A: Allocator, |
| { |
| #[inline] |
| fn deref_mut(&mut self) -> &mut [T] { |
| // SAFETY: The memory behind `self.as_ptr()` is guaranteed to contain `self.len` |
| // initialized elements of type `T`. |
| unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) } |
| } |
| } |
| |
| /// # Examples |
| /// |
| /// ``` |
| /// # use core::borrow::Borrow; |
| /// struct Foo<B: Borrow<[u32]>>(B); |
| /// |
| /// // Owned array. |
| /// let owned_array = Foo([1, 2, 3]); |
| /// |
| /// // Owned vector. |
| /// let owned_vec = Foo(KVec::from_elem(0, 3, GFP_KERNEL)?); |
| /// |
| /// let arr = [1, 2, 3]; |
| /// // Borrowed slice from `arr`. |
| /// let borrowed_slice = Foo(&arr[..]); |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| impl<T, A> Borrow<[T]> for Vec<T, A> |
| where |
| A: Allocator, |
| { |
| fn borrow(&self) -> &[T] { |
| self.as_slice() |
| } |
| } |
| |
| /// # Examples |
| /// |
| /// ``` |
| /// # use core::borrow::BorrowMut; |
| /// struct Foo<B: BorrowMut<[u32]>>(B); |
| /// |
| /// // Owned array. |
| /// let owned_array = Foo([1, 2, 3]); |
| /// |
| /// // Owned vector. |
| /// let owned_vec = Foo(KVec::from_elem(0, 3, GFP_KERNEL)?); |
| /// |
| /// let mut arr = [1, 2, 3]; |
| /// // Borrowed slice from `arr`. |
| /// let borrowed_slice = Foo(&mut arr[..]); |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| impl<T, A> BorrowMut<[T]> for Vec<T, A> |
| where |
| A: Allocator, |
| { |
| fn borrow_mut(&mut self) -> &mut [T] { |
| self.as_mut_slice() |
| } |
| } |
| |
| impl<T: Eq, A> Eq for Vec<T, A> where A: Allocator {} |
| |
| impl<T, I: SliceIndex<[T]>, A> Index<I> for Vec<T, A> |
| where |
| A: Allocator, |
| { |
| type Output = I::Output; |
| |
| #[inline] |
| fn index(&self, index: I) -> &Self::Output { |
| Index::index(&**self, index) |
| } |
| } |
| |
| impl<T, I: SliceIndex<[T]>, A> IndexMut<I> for Vec<T, A> |
| where |
| A: Allocator, |
| { |
| #[inline] |
| fn index_mut(&mut self, index: I) -> &mut Self::Output { |
| IndexMut::index_mut(&mut **self, index) |
| } |
| } |
| |
| macro_rules! impl_slice_eq { |
| ($([$($vars:tt)*] $lhs:ty, $rhs:ty,)*) => { |
| $( |
| impl<T, U, $($vars)*> PartialEq<$rhs> for $lhs |
| where |
| T: PartialEq<U>, |
| { |
| #[inline] |
| fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] } |
| } |
| )* |
| } |
| } |
| |
| impl_slice_eq! { |
| [A1: Allocator, A2: Allocator] Vec<T, A1>, Vec<U, A2>, |
| [A: Allocator] Vec<T, A>, &[U], |
| [A: Allocator] Vec<T, A>, &mut [U], |
| [A: Allocator] &[T], Vec<U, A>, |
| [A: Allocator] &mut [T], Vec<U, A>, |
| [A: Allocator] Vec<T, A>, [U], |
| [A: Allocator] [T], Vec<U, A>, |
| [A: Allocator, const N: usize] Vec<T, A>, [U; N], |
| [A: Allocator, const N: usize] Vec<T, A>, &[U; N], |
| } |
| |
| impl<'a, T, A> IntoIterator for &'a Vec<T, A> |
| where |
| A: Allocator, |
| { |
| type Item = &'a T; |
| type IntoIter = slice::Iter<'a, T>; |
| |
| fn into_iter(self) -> Self::IntoIter { |
| self.iter() |
| } |
| } |
| |
| impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> |
| where |
| A: Allocator, |
| { |
| type Item = &'a mut T; |
| type IntoIter = slice::IterMut<'a, T>; |
| |
| fn into_iter(self) -> Self::IntoIter { |
| self.iter_mut() |
| } |
| } |
| |
| /// An [`Iterator`] implementation for [`Vec`] that moves elements out of a vector. |
| /// |
| /// This structure is created by the [`Vec::into_iter`] method on [`Vec`] (provided by the |
| /// [`IntoIterator`] trait). |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let v = kernel::kvec![0, 1, 2]?; |
| /// let iter = v.into_iter(); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| pub struct IntoIter<T, A: Allocator> { |
| ptr: *mut T, |
| buf: NonNull<T>, |
| len: usize, |
| layout: ArrayLayout<T>, |
| _p: PhantomData<A>, |
| } |
| |
| impl<T, A> IntoIter<T, A> |
| where |
| A: Allocator, |
| { |
| fn into_raw_parts(self) -> (*mut T, NonNull<T>, usize, usize) { |
| let me = ManuallyDrop::new(self); |
| let ptr = me.ptr; |
| let buf = me.buf; |
| let len = me.len; |
| let cap = me.layout.len(); |
| (ptr, buf, len, cap) |
| } |
| |
| /// Same as `Iterator::collect` but specialized for `Vec`'s `IntoIter`. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let v = kernel::kvec![1, 2, 3]?; |
| /// let mut it = v.into_iter(); |
| /// |
| /// assert_eq!(it.next(), Some(1)); |
| /// |
| /// let v = it.collect(GFP_KERNEL); |
| /// assert_eq!(v, [2, 3]); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| /// |
| /// # Implementation details |
| /// |
| /// Currently, we can't implement `FromIterator`. There are a couple of issues with this trait |
| /// in the kernel, namely: |
| /// |
| /// - Rust's specialization feature is unstable. This prevents us to optimize for the special |
| /// case where `I::IntoIter` equals `Vec`'s `IntoIter` type. |
| /// - We also can't use `I::IntoIter`'s type ID either to work around this, since `FromIterator` |
| /// doesn't require this type to be `'static`. |
| /// - `FromIterator::from_iter` does return `Self` instead of `Result<Self, AllocError>`, hence |
| /// we can't properly handle allocation failures. |
| /// - Neither `Iterator::collect` nor `FromIterator::from_iter` can handle additional allocation |
| /// flags. |
| /// |
| /// Instead, provide `IntoIter::collect`, such that we can at least convert a `IntoIter` into a |
| /// `Vec` again. |
| /// |
| /// Note that `IntoIter::collect` doesn't require `Flags`, since it re-uses the existing backing |
| /// buffer. However, this backing buffer may be shrunk to the actual count of elements. |
| pub fn collect(self, flags: Flags) -> Vec<T, A> { |
| let old_layout = self.layout; |
| let (mut ptr, buf, len, mut cap) = self.into_raw_parts(); |
| let has_advanced = ptr != buf.as_ptr(); |
| |
| if has_advanced { |
| // Copy the contents we have advanced to at the beginning of the buffer. |
| // |
| // SAFETY: |
| // - `ptr` is valid for reads of `len * size_of::<T>()` bytes, |
| // - `buf.as_ptr()` is valid for writes of `len * size_of::<T>()` bytes, |
| // - `ptr` and `buf.as_ptr()` are not be subject to aliasing restrictions relative to |
| // each other, |
| // - both `ptr` and `buf.ptr()` are properly aligned. |
| unsafe { ptr::copy(ptr, buf.as_ptr(), len) }; |
| ptr = buf.as_ptr(); |
| |
| // SAFETY: `len` is guaranteed to be smaller than `self.layout.len()` by the type |
| // invariant. |
| let layout = unsafe { ArrayLayout::<T>::new_unchecked(len) }; |
| |
| // SAFETY: `buf` points to the start of the backing buffer and `len` is guaranteed by |
| // the type invariant to be smaller than `cap`. Depending on `realloc` this operation |
| // may shrink the buffer or leave it as it is. |
| ptr = match unsafe { |
| A::realloc(Some(buf.cast()), layout.into(), old_layout.into(), flags) |
| } { |
| // If we fail to shrink, which likely can't even happen, continue with the existing |
| // buffer. |
| Err(_) => ptr, |
| Ok(ptr) => { |
| cap = len; |
| ptr.as_ptr().cast() |
| } |
| }; |
| } |
| |
| // SAFETY: If the iterator has been advanced, the advanced elements have been copied to |
| // the beginning of the buffer and `len` has been adjusted accordingly. |
| // |
| // - `ptr` is guaranteed to point to the start of the backing buffer. |
| // - `cap` is either the original capacity or, after shrinking the buffer, equal to `len`. |
| // - `alloc` is guaranteed to be unchanged since `into_iter` has been called on the original |
| // `Vec`. |
| unsafe { Vec::from_raw_parts(ptr, len, cap) } |
| } |
| } |
| |
| impl<T, A> Iterator for IntoIter<T, A> |
| where |
| A: Allocator, |
| { |
| type Item = T; |
| |
| /// # Examples |
| /// |
| /// ``` |
| /// let v = kernel::kvec![1, 2, 3]?; |
| /// let mut it = v.into_iter(); |
| /// |
| /// assert_eq!(it.next(), Some(1)); |
| /// assert_eq!(it.next(), Some(2)); |
| /// assert_eq!(it.next(), Some(3)); |
| /// assert_eq!(it.next(), None); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| fn next(&mut self) -> Option<T> { |
| if self.len == 0 { |
| return None; |
| } |
| |
| let current = self.ptr; |
| |
| // SAFETY: We can't overflow; decreasing `self.len` by one every time we advance `self.ptr` |
| // by one guarantees that. |
| unsafe { self.ptr = self.ptr.add(1) }; |
| |
| self.len -= 1; |
| |
| // SAFETY: `current` is guaranteed to point at a valid element within the buffer. |
| Some(unsafe { current.read() }) |
| } |
| |
| /// # Examples |
| /// |
| /// ``` |
| /// let v: KVec<u32> = kernel::kvec![1, 2, 3]?; |
| /// let mut iter = v.into_iter(); |
| /// let size = iter.size_hint().0; |
| /// |
| /// iter.next(); |
| /// assert_eq!(iter.size_hint().0, size - 1); |
| /// |
| /// iter.next(); |
| /// assert_eq!(iter.size_hint().0, size - 2); |
| /// |
| /// iter.next(); |
| /// assert_eq!(iter.size_hint().0, size - 3); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| (self.len, Some(self.len)) |
| } |
| } |
| |
| impl<T, A> Drop for IntoIter<T, A> |
| where |
| A: Allocator, |
| { |
| fn drop(&mut self) { |
| // SAFETY: `self.ptr` is guaranteed to be valid by the type invariant. |
| unsafe { ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr, self.len)) }; |
| |
| // SAFETY: |
| // - `self.buf` was previously allocated with `A`. |
| // - `self.layout` matches the `ArrayLayout` of the preceding allocation. |
| unsafe { A::free(self.buf.cast(), self.layout.into()) }; |
| } |
| } |
| |
| impl<T, A> IntoIterator for Vec<T, A> |
| where |
| A: Allocator, |
| { |
| type Item = T; |
| type IntoIter = IntoIter<T, A>; |
| |
| /// Consumes the `Vec<T, A>` and creates an `Iterator`, which moves each value out of the |
| /// vector (from start to end). |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// let v = kernel::kvec![1, 2]?; |
| /// let mut v_iter = v.into_iter(); |
| /// |
| /// let first_element: Option<u32> = v_iter.next(); |
| /// |
| /// assert_eq!(first_element, Some(1)); |
| /// assert_eq!(v_iter.next(), Some(2)); |
| /// assert_eq!(v_iter.next(), None); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| /// |
| /// ``` |
| /// let v = kernel::kvec![]; |
| /// let mut v_iter = v.into_iter(); |
| /// |
| /// let first_element: Option<u32> = v_iter.next(); |
| /// |
| /// assert_eq!(first_element, None); |
| /// |
| /// # Ok::<(), Error>(()) |
| /// ``` |
| #[inline] |
| fn into_iter(self) -> Self::IntoIter { |
| let buf = self.ptr; |
| let layout = self.layout; |
| let (ptr, len, _) = self.into_raw_parts(); |
| |
| IntoIter { |
| ptr, |
| buf, |
| len, |
| layout, |
| _p: PhantomData::<A>, |
| } |
| } |
| } |
| |
| /// An iterator that owns all items in a vector, but does not own its allocation. |
| /// |
| /// # Invariants |
| /// |
| /// Every `&mut T` returned by the iterator references a `T` that the iterator may take ownership |
| /// of. |
| pub struct DrainAll<'vec, T> { |
| elements: slice::IterMut<'vec, T>, |
| } |
| |
| impl<'vec, T> Iterator for DrainAll<'vec, T> { |
| type Item = T; |
| |
| fn next(&mut self) -> Option<T> { |
| let elem: *mut T = self.elements.next()?; |
| // SAFETY: By the type invariants, we may take ownership of this value. |
| Some(unsafe { elem.read() }) |
| } |
| |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| self.elements.size_hint() |
| } |
| } |
| |
| impl<'vec, T> Drop for DrainAll<'vec, T> { |
| fn drop(&mut self) { |
| if core::mem::needs_drop::<T>() { |
| let iter = core::mem::take(&mut self.elements); |
| let ptr: *mut [T] = iter.into_slice(); |
| // SAFETY: By the type invariants, we own these values so we may destroy them. |
| unsafe { ptr::drop_in_place(ptr) }; |
| } |
| } |
| } |
| |
| #[macros::kunit_tests(rust_kvec_kunit)] |
| mod tests { |
| use super::*; |
| use crate::prelude::*; |
| |
| #[test] |
| fn test_kvec_retain() { |
| /// Verify correctness for one specific function. |
| #[expect(clippy::needless_range_loop)] |
| fn verify(c: &[bool]) { |
| let mut vec1: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap(); |
| let mut vec2: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap(); |
| |
| for i in 0..c.len() { |
| vec1.push_within_capacity(i).unwrap(); |
| if c[i] { |
| vec2.push_within_capacity(i).unwrap(); |
| } |
| } |
| |
| vec1.retain(|i| c[*i]); |
| |
| assert_eq!(vec1, vec2); |
| } |
| |
| /// Add one to a binary integer represented as a boolean array. |
| fn add(value: &mut [bool]) { |
| let mut carry = true; |
| for v in value { |
| let new_v = carry != *v; |
| carry = carry && *v; |
| *v = new_v; |
| } |
| } |
| |
| // This boolean array represents a function from index to boolean. We check that `retain` |
| // behaves correctly for all possible boolean arrays of every possible length less than |
| // ten. |
| let mut func = KVec::with_capacity(10, GFP_KERNEL).unwrap(); |
| for len in 0..10 { |
| for _ in 0u32..1u32 << len { |
| verify(&func); |
| add(&mut func); |
| } |
| func.push_within_capacity(false).unwrap(); |
| } |
| } |
| } |
