// SPDX-License-Identifier: GPL-2.0 //! Implementation of [`Vec`]. use super::{ allocator::{KVmalloc, Kmalloc, Vmalloc}, layout::ArrayLayout, AllocError, Allocator, Box, Flags,};use core::{ 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) } as *mut 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]?;Lines 1–500 of 1291. Load more
// SPDX-License-Identifier: GPL-2.0 //! Implementation of [`Vec`]. use super::{ allocator::{KVmalloc, Kmalloc, Vmalloc}, layout::ArrayLayout, AllocError, Allocator, Box, Flags, }; use core::{ 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) } as *mut 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]?;