kvec.rs

   1// SPDX-License-Identifier: GPL-2.0
   2
   3//! Implementation of [`Vec`].
   4
   5use super::{
   6    allocator::{KVmalloc, Kmalloc, Vmalloc, VmallocPageIter},
   7    layout::ArrayLayout,
   8    AllocError, Allocator, Box, Flags, NumaNode,
   9};
  10use crate::{
  11    fmt,
  12    page::AsPageIter, //
  13};
  14use core::{
  15    borrow::{Borrow, BorrowMut},
  16    marker::PhantomData,
  17    mem::{ManuallyDrop, MaybeUninit},
  18    ops::Deref,
  19    ops::DerefMut,
  20    ops::Index,
  21    ops::IndexMut,
  22    ptr,
  23    ptr::NonNull,
  24    slice,
  25    slice::SliceIndex,
  26};
  27
  28mod errors;
  29pub use self::errors::{InsertError, PushError, RemoveError};
  30
  31/// Create a [`KVec`] containing the arguments.
  32///
  33/// New memory is allocated with `GFP_KERNEL`.
  34///
  35/// # Examples
  36///
  37/// ```
  38/// let mut v = kernel::kvec![];
  39/// v.push(1, GFP_KERNEL)?;
  40/// assert_eq!(v, [1]);
  41///
  42/// let mut v = kernel::kvec![1; 3]?;
  43/// v.push(4, GFP_KERNEL)?;
  44/// assert_eq!(v, [1, 1, 1, 4]);
  45///
  46/// let mut v = kernel::kvec![1, 2, 3]?;
  47/// v.push(4, GFP_KERNEL)?;
  48/// assert_eq!(v, [1, 2, 3, 4]);
  49///
  50/// # Ok::<(), Error>(())
  51/// ```
  52#[macro_export]
  53macro_rules! kvec {
  54    () => (
  55        $crate::alloc::KVec::new()
  56    );
  57    ($elem:expr; $n:expr) => (
  58        $crate::alloc::KVec::from_elem($elem, $n, GFP_KERNEL)
  59    );
  60    ($($x:expr),+ $(,)?) => (
  61        match $crate::alloc::KBox::new_uninit(GFP_KERNEL) {
  62            Ok(b) => Ok($crate::alloc::KVec::from($crate::alloc::KBox::write(b, [$($x),+]))),
  63            Err(e) => Err(e),
  64        }
  65    );
  66}
  67
  68/// The kernel's [`Vec`] type.
  69///
  70/// A contiguous growable array type with contents allocated with the kernel's allocators (e.g.
  71/// [`Kmalloc`], [`Vmalloc`] or [`KVmalloc`]), written `Vec<T, A>`.
  72///
  73/// For non-zero-sized values, a [`Vec`] will use the given allocator `A` for its allocation. For
  74/// the most common allocators the type aliases [`KVec`], [`VVec`] and [`KVVec`] exist.
  75///
  76/// For zero-sized types the [`Vec`]'s pointer must be `dangling_mut::<T>`; no memory is allocated.
  77///
  78/// Generally, [`Vec`] consists of a pointer that represents the vector's backing buffer, the
  79/// capacity of the vector (the number of elements that currently fit into the vector), its length
  80/// (the number of elements that are currently stored in the vector) and the `Allocator` type used
  81/// to allocate (and free) the backing buffer.
  82///
  83/// A [`Vec`] can be deconstructed into and (re-)constructed from its previously named raw parts
  84/// and manually modified.
  85///
  86/// [`Vec`]'s backing buffer gets, if required, automatically increased (re-allocated) when elements
  87/// are added to the vector.
  88///
  89/// # Invariants
  90///
  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.
  93///
  94/// - `self.len` always represents the exact number of elements stored in the vector.
  95///
  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
  98///   backing buffer to be larger than `layout`.
  99///
 100/// - `self.len()` is always less than or equal to `self.capacity()`.
 101///
 102/// - The `Allocator` type `A` of the vector is the exact same `Allocator` type the backing buffer
 103///   was allocated with (and must be freed with).
 104pub struct Vec<T, A: Allocator> {
 105    ptr: NonNull<T>,
 106    /// Represents the actual buffer size as `cap` times `size_of::<T>` bytes.
 107    ///
 108    /// Note: This isn't quite the same as `Self::capacity`, which in contrast returns the number of
 109    /// elements we can still store without reallocating.
 110    layout: ArrayLayout<T>,
 111    len: usize,
 112    _p: PhantomData<A>,
 113}
 114
 115/// Type alias for [`Vec`] with a [`Kmalloc`] allocator.
 116///
 117/// # Examples
 118///
 119/// ```
 120/// let mut v = KVec::new();
 121/// v.push(1, GFP_KERNEL)?;
 122/// assert_eq!(&v, &[1]);
 123///
 124/// # Ok::<(), Error>(())
 125/// ```
 126pub type KVec<T> = Vec<T, Kmalloc>;
 127
 128/// Type alias for [`Vec`] with a [`Vmalloc`] allocator.
 129///
 130/// # Examples
 131///
 132/// ```
 133/// let mut v = VVec::new();
 134/// v.push(1, GFP_KERNEL)?;
 135/// assert_eq!(&v, &[1]);
 136///
 137/// # Ok::<(), Error>(())
 138/// ```
 139pub type VVec<T> = Vec<T, Vmalloc>;
 140
 141/// Type alias for [`Vec`] with a [`KVmalloc`] allocator.
 142///
 143/// # Examples
 144///
 145/// ```
 146/// let mut v = KVVec::new();
 147/// v.push(1, GFP_KERNEL)?;
 148/// assert_eq!(&v, &[1]);
 149///
 150/// # Ok::<(), Error>(())
 151/// ```
 152pub type KVVec<T> = Vec<T, KVmalloc>;
 153
 154// SAFETY: `Vec` is `Send` if `T` is `Send` because `Vec` owns its elements.
 155unsafe impl<T, A> Send for Vec<T, A>
 156where
 157    T: Send,
 158    A: Allocator,
 159{
 160}
 161
 162// SAFETY: `Vec` is `Sync` if `T` is `Sync` because `Vec` owns its elements.
 163unsafe impl<T, A> Sync for Vec<T, A>
 164where
 165    T: Sync,
 166    A: Allocator,
 167{
 168}
 169
 170impl<T, A> Vec<T, A>
 171where
 172    A: Allocator,
 173{
 174    #[inline]
 175    const fn is_zst() -> bool {
 176        core::mem::size_of::<T>() == 0
 177    }
 178
 179    /// Returns the number of elements that can be stored within the vector without allocating
 180    /// additional memory.
 181    pub const fn capacity(&self) -> usize {
 182        if const { Self::is_zst() } {
 183            usize::MAX
 184        } else {
 185            self.layout.len()
 186        }
 187    }
 188
 189    /// Returns the number of elements stored within the vector.
 190    #[inline]
 191    pub const fn len(&self) -> usize {
 192        self.len
 193    }
 194
 195    /// Increments `self.len` by `additional`.
 196    ///
 197    /// # Safety
 198    ///
 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.
 201    #[inline]
 202    pub const unsafe fn inc_len(&mut self, additional: usize) {
 203        // Guaranteed by the type invariant to never underflow.
 204        debug_assert!(additional <= self.capacity() - self.len());
 205        // INVARIANT: By the safety requirements of this method this represents the exact number of
 206        // elements stored within `self`.
 207        self.len += additional;
 208    }
 209
 210    /// Decreases `self.len` by `count`.
 211    ///
 212    /// Returns a mutable slice to the elements forgotten by the vector. It is the caller's
 213    /// responsibility to drop these elements if necessary.
 214    ///
 215    /// # Safety
 216    ///
 217    /// - `count` must be less than or equal to `self.len`.
 218    unsafe fn dec_len(&mut self, count: usize) -> &mut [T] {
 219        debug_assert!(count <= self.len());
 220        // INVARIANT: We relinquish ownership of the elements within the range `[self.len - count,
 221        // self.len)`, hence the updated value of `set.len` represents the exact number of elements
 222        // stored within `self`.
 223        self.len -= count;
 224        // SAFETY: The memory after `self.len()` is guaranteed to contain `count` initialized
 225        // elements of type `T`.
 226        unsafe { slice::from_raw_parts_mut(self.as_mut_ptr().add(self.len), count) }
 227    }
 228
 229    /// Returns a slice of the entire vector.
 230    ///
 231    /// # Examples
 232    ///
 233    /// ```
 234    /// let mut v = KVec::new();
 235    /// v.push(1, GFP_KERNEL)?;
 236    /// v.push(2, GFP_KERNEL)?;
 237    /// assert_eq!(v.as_slice(), &[1, 2]);
 238    /// # Ok::<(), Error>(())
 239    /// ```
 240    #[inline]
 241    pub fn as_slice(&self) -> &[T] {
 242        self
 243    }
 244
 245    /// Returns a mutable slice of the entire vector.
 246    #[inline]
 247    pub fn as_mut_slice(&mut self) -> &mut [T] {
 248        self
 249    }
 250
 251    /// Returns a mutable raw pointer to the vector's backing buffer, or, if `T` is a ZST, a
 252    /// dangling raw pointer.
 253    #[inline]
 254    pub fn as_mut_ptr(&mut self) -> *mut T {
 255        self.ptr.as_ptr()
 256    }
 257
 258    /// Returns a raw pointer to the vector's backing buffer, or, if `T` is a ZST, a dangling raw
 259    /// pointer.
 260    #[inline]
 261    pub const fn as_ptr(&self) -> *const T {
 262        self.ptr.as_ptr()
 263    }
 264
 265    /// Returns `true` if the vector contains no elements, `false` otherwise.
 266    ///
 267    /// # Examples
 268    ///
 269    /// ```
 270    /// let mut v = KVec::new();
 271    /// assert!(v.is_empty());
 272    ///
 273    /// v.push(1, GFP_KERNEL);
 274    /// assert!(!v.is_empty());
 275    /// ```
 276    #[inline]
 277    pub const fn is_empty(&self) -> bool {
 278        self.len() == 0
 279    }
 280
 281    /// Creates a new, empty `Vec<T, A>`.
 282    ///
 283    /// This method does not allocate by itself.
 284    #[inline]
 285    pub const fn new() -> Self {
 286        // INVARIANT: Since this is a new, empty `Vec` with no backing memory yet,
 287        // - `ptr` is a properly aligned dangling pointer for type `T`,
 288        // - `layout` is an empty `ArrayLayout` (zero capacity)
 289        // - `len` is zero, since no elements can be or have been stored,
 290        // - `A` is always valid.
 291        Self {
 292            ptr: NonNull::dangling(),
 293            layout: ArrayLayout::empty(),
 294            len: 0,
 295            _p: PhantomData::<A>,
 296        }
 297    }
 298
 299    /// Returns a slice of `MaybeUninit<T>` for the remaining spare capacity of the vector.
 300    pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
 301        // SAFETY:
 302        // - `self.len` is smaller than `self.capacity` by the type invariant and hence, the
 303        //   resulting pointer is guaranteed to be part of the same allocated object.
 304        // - `self.len` can not overflow `isize`.
 305        let ptr = unsafe { self.as_mut_ptr().add(self.len) }.cast::<MaybeUninit<T>>();
 306
 307        // SAFETY: The memory between `self.len` and `self.capacity` is guaranteed to be allocated
 308        // and valid, but uninitialized.
 309        unsafe { slice::from_raw_parts_mut(ptr, self.capacity() - self.len) }
 310    }
 311
 312    /// Appends an element to the back of the [`Vec`] instance.
 313    ///
 314    /// # Examples
 315    ///
 316    /// ```
 317    /// let mut v = KVec::new();
 318    /// v.push(1, GFP_KERNEL)?;
 319    /// assert_eq!(&v, &[1]);
 320    ///
 321    /// v.push(2, GFP_KERNEL)?;
 322    /// assert_eq!(&v, &[1, 2]);
 323    /// # Ok::<(), Error>(())
 324    /// ```
 325    pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
 326        self.reserve(1, flags)?;
 327        // SAFETY: The call to `reserve` was successful, so the capacity is at least one greater
 328        // than the length.
 329        unsafe { self.push_within_capacity_unchecked(v) };
 330        Ok(())
 331    }
 332
 333    /// Appends an element to the back of the [`Vec`] instance without reallocating.
 334    ///
 335    /// Fails if the vector does not have capacity for the new element.
 336    ///
 337    /// # Examples
 338    ///
 339    /// ```
 340    /// let mut v = KVec::with_capacity(10, GFP_KERNEL)?;
 341    /// for i in 0..10 {
 342    ///     v.push_within_capacity(i)?;
 343    /// }
 344    ///
 345    /// assert!(v.push_within_capacity(10).is_err());
 346    /// # Ok::<(), Error>(())
 347    /// ```
 348    pub fn push_within_capacity(&mut self, v: T) -> Result<(), PushError<T>> {
 349        if self.len() < self.capacity() {
 350            // SAFETY: The length is less than the capacity.
 351            unsafe { self.push_within_capacity_unchecked(v) };
 352            Ok(())
 353        } else {
 354            Err(PushError(v))
 355        }
 356    }
 357
 358    /// Appends an element to the back of the [`Vec`] instance without reallocating.
 359    ///
 360    /// # Safety
 361    ///
 362    /// The length must be less than the capacity.
 363    unsafe fn push_within_capacity_unchecked(&mut self, v: T) {
 364        let spare = self.spare_capacity_mut();
 365
 366        // SAFETY: By the safety requirements, `spare` is non-empty.
 367        unsafe { spare.get_unchecked_mut(0) }.write(v);
 368
 369        // SAFETY: We just initialised the first spare entry, so it is safe to increase the length
 370        // by 1. We also know that the new length is <= capacity because the caller guarantees that
 371        // the length is less than the capacity at the beginning of this function.
 372        unsafe { self.inc_len(1) };
 373    }
 374
 375    /// Inserts an element at the given index in the [`Vec`] instance.
 376    ///
 377    /// Fails if the vector does not have capacity for the new element. Panics if the index is out
 378    /// of bounds.
 379    ///
 380    /// # Examples
 381    ///
 382    /// ```
 383    /// use kernel::alloc::kvec::InsertError;
 384    ///
 385    /// let mut v = KVec::with_capacity(5, GFP_KERNEL)?;
 386    /// for i in 0..5 {
 387    ///     v.insert_within_capacity(0, i)?;
 388    /// }
 389    ///
 390    /// assert!(matches!(v.insert_within_capacity(0, 5), Err(InsertError::OutOfCapacity(_))));
 391    /// assert!(matches!(v.insert_within_capacity(1000, 5), Err(InsertError::IndexOutOfBounds(_))));
 392    /// assert_eq!(v, [4, 3, 2, 1, 0]);
 393    /// # Ok::<(), Error>(())
 394    /// ```
 395    pub fn insert_within_capacity(
 396        &mut self,
 397        index: usize,
 398        element: T,
 399    ) -> Result<(), InsertError<T>> {
 400        let len = self.len();
 401        if index > len {
 402            return Err(InsertError::IndexOutOfBounds(element));
 403        }
 404
 405        if len >= self.capacity() {
 406            return Err(InsertError::OutOfCapacity(element));
 407        }
 408
 409        // SAFETY: This is in bounds since `index <= len < capacity`.
 410        let p = unsafe { self.as_mut_ptr().add(index) };
 411        // INVARIANT: This breaks the Vec invariants by making `index` contain an invalid element,
 412        // but we restore the invariants below.
 413        // SAFETY: Both the src and dst ranges end no later than one element after the length.
 414        // Since the length is less than the capacity, both ranges are in bounds of the allocation.
 415        unsafe { ptr::copy(p, p.add(1), len - index) };
 416        // INVARIANT: This restores the Vec invariants.
 417        // SAFETY: The pointer is in-bounds of the allocation.
 418        unsafe { ptr::write(p, element) };
 419        // SAFETY: Index `len` contains a valid element due to the above copy and write.
 420        unsafe { self.inc_len(1) };
 421        Ok(())
 422    }
 423
 424    /// Removes the last element from a vector and returns it, or `None` if it is empty.
 425    ///
 426    /// # Examples
 427    ///
 428    /// ```
 429    /// let mut v = KVec::new();
 430    /// v.push(1, GFP_KERNEL)?;
 431    /// v.push(2, GFP_KERNEL)?;
 432    /// assert_eq!(&v, &[1, 2]);
 433    ///
 434    /// assert_eq!(v.pop(), Some(2));
 435    /// assert_eq!(v.pop(), Some(1));
 436    /// assert_eq!(v.pop(), None);
 437    /// # Ok::<(), Error>(())
 438    /// ```
 439    pub fn pop(&mut self) -> Option<T> {
 440        if self.is_empty() {
 441            return None;
 442        }
 443
 444        let removed: *mut T = {
 445            // SAFETY: We just checked that the length is at least one.
 446            let slice = unsafe { self.dec_len(1) };
 447            // SAFETY: The argument to `dec_len` was 1 so this returns a slice of length 1.
 448            unsafe { slice.get_unchecked_mut(0) }
 449        };
 450
 451        // SAFETY: The guarantees of `dec_len` allow us to take ownership of this value.
 452        Some(unsafe { removed.read() })
 453    }
 454
 455    /// Removes the element at the given index.
 456    ///
 457    /// # Examples
 458    ///
 459    /// ```
 460    /// let mut v = kernel::kvec![1, 2, 3]?;
 461    /// assert_eq!(v.remove(1)?, 2);
 462    /// assert_eq!(v, [1, 3]);
 463    /// # Ok::<(), Error>(())
 464    /// ```
 465    pub fn remove(&mut self, i: usize) -> Result<T, RemoveError> {
 466        let value = {
 467            let value_ref = self.get(i).ok_or(RemoveError)?;
 468            // INVARIANT: This breaks the invariants by invalidating the value at index `i`, but we
 469            // restore the invariants below.
 470            // SAFETY: The value at index `i` is valid, because otherwise we would have already
 471            // failed with `RemoveError`.
 472            unsafe { ptr::read(value_ref) }
 473        };
 474
 475        // SAFETY: We checked that `i` is in-bounds.
 476        let p = unsafe { self.as_mut_ptr().add(i) };
 477
 478        // INVARIANT: After this call, the invalid value is at the last slot, so the Vec invariants
 479        // are restored after the below call to `dec_len(1)`.
 480        // SAFETY: `p.add(1).add(self.len - i - 1)` is `i+1+len-i-1 == len` elements after the
 481        // beginning of the vector, so this is in-bounds of the vector's allocation.
 482        unsafe { ptr::copy(p.add(1), p, self.len - i - 1) };
 483
 484        // SAFETY: Since the check at the beginning of this call did not fail with `RemoveError`,
 485        // the length is at least one.
 486        unsafe { self.dec_len(1) };
 487
 488        Ok(value)
 489    }
 490
 491    /// Creates a new [`Vec`] instance with at least the given capacity.
 492    ///
 493    /// # Examples
 494    ///
 495    /// ```
 496    /// let v = KVec::<u32>::with_capacity(20, GFP_KERNEL)?;
 497    ///
 498    /// assert!(v.capacity() >= 20);
 499    /// # Ok::<(), Error>(())
 500    /// ```
 501    pub fn with_capacity(capacity: usize, flags: Flags) -> Result<Self, AllocError> {
 502        let mut v = Vec::new();
 503
 504        v.reserve(capacity, flags)?;
 505
 506        Ok(v)
 507    }
 508
 509    /// Creates a `Vec<T, A>` from a pointer, a length and a capacity using the allocator `A`.
 510    ///
 511    /// # Examples
 512    ///
 513    /// ```
 514    /// let mut v = kernel::kvec![1, 2, 3]?;
 515    /// v.reserve(1, GFP_KERNEL)?;
 516    ///
 517    /// let (mut ptr, mut len, cap) = v.into_raw_parts();
 518    ///
 519    /// // SAFETY: We've just reserved memory for another element.
 520    /// unsafe { ptr.add(len).write(4) };
 521    /// len += 1;
 522    ///
 523    /// // SAFETY: We only wrote an additional element at the end of the `KVec`'s buffer and
 524    /// // correspondingly increased the length of the `KVec` by one. Otherwise, we construct it
 525    /// // from the exact same raw parts.
 526    /// let v = unsafe { KVec::from_raw_parts(ptr, len, cap) };
 527    ///
 528    /// assert_eq!(v, [1, 2, 3, 4]);
 529    ///
 530    /// # Ok::<(), Error>(())
 531    /// ```
 532    ///
 533    /// # Safety
 534    ///
 535    /// If `T` is a ZST:
 536    ///
 537    /// - `ptr` must be a dangling, well aligned pointer.
 538    ///
 539    /// Otherwise:
 540    ///
 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`.
 547    ///
 548    /// It is also valid to create an empty `Vec` passing a dangling pointer for `ptr` and zero for
 549    /// `cap` and `len`.
 550    pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {
 551        let layout = if Self::is_zst() {
 552            ArrayLayout::empty()
 553        } else {
 554            // SAFETY: By the safety requirements of this function, `capacity * size_of::<T>()` is
 555            // smaller than `isize::MAX`.
 556            unsafe { ArrayLayout::new_unchecked(capacity) }
 557        };
 558
 559        // INVARIANT: For ZSTs, we store an empty `ArrayLayout`, all other type invariants are
 560        // covered by the safety requirements of this function.
 561        Self {
 562            // SAFETY: By the safety requirements, `ptr` is either dangling or pointing to a valid
 563            // memory allocation, allocated with `A`.
 564            ptr: unsafe { NonNull::new_unchecked(ptr) },
 565            layout,
 566            len: length,
 567            _p: PhantomData::<A>,
 568        }
 569    }
 570
 571    /// Consumes the `Vec<T, A>` and returns its raw components `pointer`, `length` and `capacity`.
 572    ///
 573    /// This will not run the destructor of the contained elements and for non-ZSTs the allocation
 574    /// will stay alive indefinitely. Use [`Vec::from_raw_parts`] to recover the [`Vec`], drop the
 575    /// elements and free the allocation, if any.
 576    pub fn into_raw_parts(self) -> (*mut T, usize, usize) {
 577        let mut me = ManuallyDrop::new(self);
 578        let len = me.len();
 579        let capacity = me.capacity();
 580        let ptr = me.as_mut_ptr();
 581        (ptr, len, capacity)
 582    }
 583
 584    /// Clears the vector, removing all values.
 585    ///
 586    /// Note that this method has no effect on the allocated capacity
 587    /// of the vector.
 588    ///
 589    /// # Examples
 590    ///
 591    /// ```
 592    /// let mut v = kernel::kvec![1, 2, 3]?;
 593    ///
 594    /// v.clear();
 595    ///
 596    /// assert!(v.is_empty());
 597    /// # Ok::<(), Error>(())
 598    /// ```
 599    #[inline]
 600    pub fn clear(&mut self) {
 601        self.truncate(0);
 602    }
 603
 604    /// Ensures that the capacity exceeds the length by at least `additional` elements.
 605    ///
 606    /// # Examples
 607    ///
 608    /// ```
 609    /// let mut v = KVec::new();
 610    /// v.push(1, GFP_KERNEL)?;
 611    ///
 612    /// v.reserve(10, GFP_KERNEL)?;
 613    /// let cap = v.capacity();
 614    /// assert!(cap >= 10);
 615    ///
 616    /// v.reserve(10, GFP_KERNEL)?;
 617    /// let new_cap = v.capacity();
 618    /// assert_eq!(new_cap, cap);
 619    ///
 620    /// # Ok::<(), Error>(())
 621    /// ```
 622    pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> {
 623        let len = self.len();
 624        let cap = self.capacity();
 625
 626        if cap - len >= additional {
 627            return Ok(());
 628        }
 629
 630        if Self::is_zst() {
 631            // The capacity is already `usize::MAX` for ZSTs, we can't go higher.
 632            return Err(AllocError);
 633        }
 634
 635        // We know that `cap <= isize::MAX` because of the type invariants of `Self`. So the
 636        // multiplication by two won't overflow.
 637        let new_cap = core::cmp::max(cap * 2, len.checked_add(additional).ok_or(AllocError)?);
 638        let layout = ArrayLayout::new(new_cap).map_err(|_| AllocError)?;
 639
 640        // SAFETY:
 641        // - `ptr` is valid because it's either `None` or comes from a previous call to
 642        //   `A::realloc`.
 643        // - `self.layout` matches the `ArrayLayout` of the preceding allocation.
 644        let ptr = unsafe {
 645            A::realloc(
 646                Some(self.ptr.cast()),
 647                layout.into(),
 648                self.layout.into(),
 649                flags,
 650                NumaNode::NO_NODE,
 651            )?
 652        };
 653
 654        // INVARIANT:
 655        // - `layout` is some `ArrayLayout::<T>`,
 656        // - `ptr` has been created by `A::realloc` from `layout`.
 657        self.ptr = ptr.cast();
 658        self.layout = layout;
 659
 660        Ok(())
 661    }
 662
 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.
 665    ///
 666    /// This has no effect on the capacity and will not allocate.
 667    ///
 668    /// # Examples
 669    ///
 670    /// ```
 671    /// let mut v = kernel::kvec![1, 2, 3]?;
 672    /// v.truncate(1);
 673    /// assert_eq!(v.len(), 1);
 674    /// assert_eq!(&v, &[1]);
 675    ///
 676    /// # Ok::<(), Error>(())
 677    /// ```
 678    pub fn truncate(&mut self, len: usize) {
 679        if let Some(count) = self.len().checked_sub(len) {
 680            // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or
 681            // equal to `self.len()`.
 682            let ptr: *mut [T] = unsafe { self.dec_len(count) };
 683
 684            // SAFETY: the contract of `dec_len` guarantees that the elements in `ptr` are
 685            // valid elements whose ownership has been transferred to the caller.
 686            unsafe { ptr::drop_in_place(ptr) };
 687        }
 688    }
 689
 690    /// Takes ownership of all items in this vector without consuming the allocation.
 691    ///
 692    /// # Examples
 693    ///
 694    /// ```
 695    /// let mut v = kernel::kvec![0, 1, 2, 3]?;
 696    ///
 697    /// for (i, j) in v.drain_all().enumerate() {
 698    ///     assert_eq!(i, j);
 699    /// }
 700    ///
 701    /// assert!(v.capacity() >= 4);
 702    /// # Ok::<(), Error>(())
 703    /// ```
 704    pub fn drain_all(&mut self) -> DrainAll<'_, T> {
 705        // SAFETY: This does not underflow the length.
 706        let elems = unsafe { self.dec_len(self.len()) };
 707        // INVARIANT: The first `len` elements of the spare capacity are valid values, and as we
 708        // just set the length to zero, we may transfer ownership to the `DrainAll` object.
 709        DrainAll {
 710            elements: elems.iter_mut(),
 711        }
 712    }
 713
 714    /// Removes all elements that don't match the provided closure.
 715    ///
 716    /// # Examples
 717    ///
 718    /// ```
 719    /// let mut v = kernel::kvec![1, 2, 3, 4]?;
 720    /// v.retain(|i| *i % 2 == 0);
 721    /// assert_eq!(v, [2, 4]);
 722    /// # Ok::<(), Error>(())
 723    /// ```
 724    pub fn retain(&mut self, mut f: impl FnMut(&mut T) -> bool) {
 725        let mut num_kept = 0;
 726        let mut next_to_check = 0;
 727        while let Some(to_check) = self.get_mut(next_to_check) {
 728            if f(to_check) {
 729                self.swap(num_kept, next_to_check);
 730                num_kept += 1;
 731            }
 732            next_to_check += 1;
 733        }
 734        self.truncate(num_kept);
 735    }
 736}
 737
 738impl<T: Clone, A: Allocator> Vec<T, A> {
 739    /// Extend the vector by `n` clones of `value`.
 740    pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), AllocError> {
 741        if n == 0 {
 742            return Ok(());
 743        }
 744
 745        self.reserve(n, flags)?;
 746
 747        let spare = self.spare_capacity_mut();
 748
 749        for item in spare.iter_mut().take(n - 1) {
 750            item.write(value.clone());
 751        }
 752
 753        // We can write the last element directly without cloning needlessly.
 754        spare[n - 1].write(value);
 755
 756        // SAFETY:
 757        // - `self.len() + n < self.capacity()` due to the call to reserve above,
 758        // - the loop and the line above initialized the next `n` elements.
 759        unsafe { self.inc_len(n) };
 760
 761        Ok(())
 762    }
 763
 764    /// Pushes clones of the elements of slice into the [`Vec`] instance.
 765    ///
 766    /// # Examples
 767    ///
 768    /// ```
 769    /// let mut v = KVec::new();
 770    /// v.push(1, GFP_KERNEL)?;
 771    ///
 772    /// v.extend_from_slice(&[20, 30, 40], GFP_KERNEL)?;
 773    /// assert_eq!(&v, &[1, 20, 30, 40]);
 774    ///
 775    /// v.extend_from_slice(&[50, 60], GFP_KERNEL)?;
 776    /// assert_eq!(&v, &[1, 20, 30, 40, 50, 60]);
 777    /// # Ok::<(), Error>(())
 778    /// ```
 779    pub fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError> {
 780        self.reserve(other.len(), flags)?;
 781        for (slot, item) in core::iter::zip(self.spare_capacity_mut(), other) {
 782            slot.write(item.clone());
 783        }
 784
 785        // SAFETY:
 786        // - `other.len()` spare entries have just been initialized, so it is safe to increase
 787        //   the length by the same number.
 788        // - `self.len() + other.len() <= self.capacity()` is guaranteed by the preceding `reserve`
 789        //   call.
 790        unsafe { self.inc_len(other.len()) };
 791        Ok(())
 792    }
 793
 794    /// Create a new `Vec<T, A>` and extend it by `n` clones of `value`.
 795    pub fn from_elem(value: T, n: usize, flags: Flags) -> Result<Self, AllocError> {
 796        let mut v = Self::with_capacity(n, flags)?;
 797
 798        v.extend_with(n, value, flags)?;
 799
 800        Ok(v)
 801    }
 802
 803    /// Resizes the [`Vec`] so that `len` is equal to `new_len`.
 804    ///
 805    /// If `new_len` is smaller than `len`, the `Vec` is [`Vec::truncate`]d.
 806    /// If `new_len` is larger, each new slot is filled with clones of `value`.
 807    ///
 808    /// # Examples
 809    ///
 810    /// ```
 811    /// let mut v = kernel::kvec![1, 2, 3]?;
 812    /// v.resize(1, 42, GFP_KERNEL)?;
 813    /// assert_eq!(&v, &[1]);
 814    ///
 815    /// v.resize(3, 42, GFP_KERNEL)?;
 816    /// assert_eq!(&v, &[1, 42, 42]);
 817    ///
 818    /// # Ok::<(), Error>(())
 819    /// ```
 820    pub fn resize(&mut self, new_len: usize, value: T, flags: Flags) -> Result<(), AllocError> {
 821        match new_len.checked_sub(self.len()) {
 822            Some(n) => self.extend_with(n, value, flags),
 823            None => {
 824                self.truncate(new_len);
 825                Ok(())
 826            }
 827        }
 828    }
 829}
 830
 831impl<T, A> Drop for Vec<T, A>
 832where
 833    A: Allocator,
 834{
 835    fn drop(&mut self) {
 836        // SAFETY: `self.as_mut_ptr` is guaranteed to be valid by the type invariant.
 837        unsafe {
 838            ptr::drop_in_place(core::ptr::slice_from_raw_parts_mut(
 839                self.as_mut_ptr(),
 840                self.len,
 841            ))
 842        };
 843
 844        // SAFETY:
 845        // - `self.ptr` was previously allocated with `A`.
 846        // - `self.layout` matches the `ArrayLayout` of the preceding allocation.
 847        unsafe { A::free(self.ptr.cast(), self.layout.into()) };
 848    }
 849}
 850
 851impl<T, A, const N: usize> From<Box<[T; N], A>> for Vec<T, A>
 852where
 853    A: Allocator,
 854{
 855    fn from(b: Box<[T; N], A>) -> Vec<T, A> {
 856        let len = b.len();
 857        let ptr = Box::into_raw(b);
 858
 859        // SAFETY:
 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) }
 866    }
 867}
 868
 869impl<T, A: Allocator> Default for Vec<T, A> {
 870    #[inline]
 871    fn default() -> Self {
 872        Self::new()
 873    }
 874}
 875
 876impl<T: fmt::Debug, A: Allocator> fmt::Debug for Vec<T, A> {
 877    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 878        fmt::Debug::fmt(&**self, f)
 879    }
 880}
 881
 882impl<T, A> Deref for Vec<T, A>
 883where
 884    A: Allocator,
 885{
 886    type Target = [T];
 887
 888    #[inline]
 889    fn deref(&self) -> &[T] {
 890        // SAFETY: The memory behind `self.as_ptr()` is guaranteed to contain `self.len`
 891        // initialized elements of type `T`.
 892        unsafe { slice::from_raw_parts(self.as_ptr(), self.len) }
 893    }
 894}
 895
 896impl<T, A> DerefMut for Vec<T, A>
 897where
 898    A: Allocator,
 899{
 900    #[inline]
 901    fn deref_mut(&mut self) -> &mut [T] {
 902        // SAFETY: The memory behind `self.as_ptr()` is guaranteed to contain `self.len`
 903        // initialized elements of type `T`.
 904        unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) }
 905    }
 906}
 907
 908/// # Examples
 909///
 910/// ```
 911/// # use core::borrow::Borrow;
 912/// struct Foo<B: Borrow<[u32]>>(B);
 913///
 914/// // Owned array.
 915/// let owned_array = Foo([1, 2, 3]);
 916///
 917/// // Owned vector.
 918/// let owned_vec = Foo(KVec::from_elem(0, 3, GFP_KERNEL)?);
 919///
 920/// let arr = [1, 2, 3];
 921/// // Borrowed slice from `arr`.
 922/// let borrowed_slice = Foo(&arr[..]);
 923/// # Ok::<(), Error>(())
 924/// ```
 925impl<T, A> Borrow<[T]> for Vec<T, A>
 926where
 927    A: Allocator,
 928{
 929    fn borrow(&self) -> &[T] {
 930        self.as_slice()
 931    }
 932}
 933
 934/// # Examples
 935///
 936/// ```
 937/// # use core::borrow::BorrowMut;
 938/// struct Foo<B: BorrowMut<[u32]>>(B);
 939///
 940/// // Owned array.
 941/// let owned_array = Foo([1, 2, 3]);
 942///
 943/// // Owned vector.
 944/// let owned_vec = Foo(KVec::from_elem(0, 3, GFP_KERNEL)?);
 945///
 946/// let mut arr = [1, 2, 3];
 947/// // Borrowed slice from `arr`.
 948/// let borrowed_slice = Foo(&mut arr[..]);
 949/// # Ok::<(), Error>(())
 950/// ```
 951impl<T, A> BorrowMut<[T]> for Vec<T, A>
 952where
 953    A: Allocator,
 954{
 955    fn borrow_mut(&mut self) -> &mut [T] {
 956        self.as_mut_slice()
 957    }
 958}
 959
 960impl<T: Eq, A> Eq for Vec<T, A> where A: Allocator {}
 961
 962impl<T, I: SliceIndex<[T]>, A> Index<I> for Vec<T, A>
 963where
 964    A: Allocator,
 965{
 966    type Output = I::Output;
 967
 968    #[inline]
 969    fn index(&self, index: I) -> &Self::Output {
 970        Index::index(&**self, index)
 971    }
 972}
 973
 974impl<T, I: SliceIndex<[T]>, A> IndexMut<I> for Vec<T, A>
 975where
 976    A: Allocator,
 977{
 978    #[inline]
 979    fn index_mut(&mut self, index: I) -> &mut Self::Output {
 980        IndexMut::index_mut(&mut **self, index)
 981    }
 982}
 983
 984macro_rules! impl_slice_eq {
 985    ($([$($vars:tt)*] $lhs:ty, $rhs:ty,)*) => {
 986        $(
 987            impl<T, U, $($vars)*> PartialEq<$rhs> for $lhs
 988            where
 989                T: PartialEq<U>,
 990            {
 991                #[inline]
 992                fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] }
 993            }
 994        )*
 995    }
 996}
 997
 998impl_slice_eq! {
 999    [A1: Allocator, A2: Allocator] Vec<T, A1>, Vec<U, A2>,
1000    [A: Allocator] Vec<T, A>, &[U],
1001    [A: Allocator] Vec<T, A>, &mut [U],
1002    [A: Allocator] &[T], Vec<U, A>,
1003    [A: Allocator] &mut [T], Vec<U, A>,
1004    [A: Allocator] Vec<T, A>, [U],
1005    [A: Allocator] [T], Vec<U, A>,
1006    [A: Allocator, const N: usize] Vec<T, A>, [U; N],
1007    [A: Allocator, const N: usize] Vec<T, A>, &[U; N],
1008}
1009
1010impl<'a, T, A> IntoIterator for &'a Vec<T, A>
1011where
1012    A: Allocator,
1013{
1014    type Item = &'a T;
1015    type IntoIter = slice::Iter<'a, T>;
1016
1017    fn into_iter(self) -> Self::IntoIter {
1018        self.iter()
1019    }
1020}
1021
1022impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A>
1023where
1024    A: Allocator,
1025{
1026    type Item = &'a mut T;
1027    type IntoIter = slice::IterMut<'a, T>;
1028
1029    fn into_iter(self) -> Self::IntoIter {
1030        self.iter_mut()
1031    }
1032}
1033
1034/// # Examples
1035///
1036/// ```
1037/// # use kernel::prelude::*;
1038/// use kernel::alloc::allocator::VmallocPageIter;
1039/// use kernel::page::{AsPageIter, PAGE_SIZE};
1040///
1041/// let mut vec = VVec::<u8>::new();
1042///
1043/// assert!(vec.page_iter().next().is_none());
1044///
1045/// vec.reserve(PAGE_SIZE, GFP_KERNEL)?;
1046///
1047/// let page = vec.page_iter().next().expect("At least one page should be available.\n");
1048///
1049/// // SAFETY: There is no concurrent read or write to the same page.
1050/// unsafe { page.fill_zero_raw(0, PAGE_SIZE)? };
1051/// # Ok::<(), Error>(())
1052/// ```
1053impl<T> AsPageIter for VVec<T> {
1054    type Iter<'a>
1055        = VmallocPageIter<'a>
1056    where
1057        T: 'a;
1058
1059    fn page_iter(&mut self) -> Self::Iter<'_> {
1060        let ptr = self.ptr.cast();
1061        let size = self.layout.size();
1062
1063        // SAFETY:
1064        // - `ptr` is a valid pointer to the beginning of a `Vmalloc` allocation.
1065        // - `ptr` is guaranteed to be valid for the lifetime of `'a`.
1066        // - `size` is the size of the `Vmalloc` allocation `ptr` points to.
1067        unsafe { VmallocPageIter::new(ptr, size) }
1068    }
1069}
1070
1071/// An [`Iterator`] implementation for [`Vec`] that moves elements out of a vector.
1072///
1073/// This structure is created by the [`Vec::into_iter`] method on [`Vec`] (provided by the
1074/// [`IntoIterator`] trait).
1075///
1076/// # Examples
1077///
1078/// ```
1079/// let v = kernel::kvec![0, 1, 2]?;
1080/// let iter = v.into_iter();
1081///
1082/// # Ok::<(), Error>(())
1083/// ```
1084pub struct IntoIter<T, A: Allocator> {
1085    ptr: *mut T,
1086    buf: NonNull<T>,
1087    len: usize,
1088    layout: ArrayLayout<T>,
1089    _p: PhantomData<A>,
1090}
1091
1092impl<T, A> IntoIter<T, A>
1093where
1094    A: Allocator,
1095{
1096    fn into_raw_parts(self) -> (*mut T, NonNull<T>, usize, usize) {
1097        let me = ManuallyDrop::new(self);
1098        let ptr = me.ptr;
1099        let buf = me.buf;
1100        let len = me.len;
1101        let cap = me.layout.len();
1102        (ptr, buf, len, cap)
1103    }
1104
1105    /// Same as `Iterator::collect` but specialized for `Vec`'s `IntoIter`.
1106    ///
1107    /// # Examples
1108    ///
1109    /// ```
1110    /// let v = kernel::kvec![1, 2, 3]?;
1111    /// let mut it = v.into_iter();
1112    ///
1113    /// assert_eq!(it.next(), Some(1));
1114    ///
1115    /// let v = it.collect(GFP_KERNEL);
1116    /// assert_eq!(v, [2, 3]);
1117    ///
1118    /// # Ok::<(), Error>(())
1119    /// ```
1120    ///
1121    /// # Implementation details
1122    ///
1123    /// Currently, we can't implement `FromIterator`. There are a couple of issues with this trait
1124    /// in the kernel, namely:
1125    ///
1126    /// - Rust's specialization feature is unstable. This prevents us to optimize for the special
1127    ///   case where `I::IntoIter` equals `Vec`'s `IntoIter` type.
1128    /// - We also can't use `I::IntoIter`'s type ID either to work around this, since `FromIterator`
1129    ///   doesn't require this type to be `'static`.
1130    /// - `FromIterator::from_iter` does return `Self` instead of `Result<Self, AllocError>`, hence
1131    ///   we can't properly handle allocation failures.
1132    /// - Neither `Iterator::collect` nor `FromIterator::from_iter` can handle additional allocation
1133    ///   flags.
1134    ///
1135    /// Instead, provide `IntoIter::collect`, such that we can at least convert a `IntoIter` into a
1136    /// `Vec` again.
1137    ///
1138    /// Note that `IntoIter::collect` doesn't require `Flags`, since it re-uses the existing backing
1139    /// buffer. However, this backing buffer may be shrunk to the actual count of elements.
1140    pub fn collect(self, flags: Flags) -> Vec<T, A> {
1141        let old_layout = self.layout;
1142        let (mut ptr, buf, len, mut cap) = self.into_raw_parts();
1143        let has_advanced = ptr != buf.as_ptr();
1144
1145        if has_advanced {
1146            // Copy the contents we have advanced to at the beginning of the buffer.
1147            //
1148            // SAFETY:
1149            // - `ptr` is valid for reads of `len * size_of::<T>()` bytes,
1150            // - `buf.as_ptr()` is valid for writes of `len * size_of::<T>()` bytes,
1151            // - `ptr` and `buf.as_ptr()` are not be subject to aliasing restrictions relative to
1152            //   each other,
1153            // - both `ptr` and `buf.ptr()` are properly aligned.
1154            unsafe { ptr::copy(ptr, buf.as_ptr(), len) };
1155            ptr = buf.as_ptr();
1156
1157            // SAFETY: `len` is guaranteed to be smaller than `self.layout.len()` by the type
1158            // invariant.
1159            let layout = unsafe { ArrayLayout::<T>::new_unchecked(len) };
1160
1161            // SAFETY: `buf` points to the start of the backing buffer and `len` is guaranteed by
1162            // the type invariant to be smaller than `cap`. Depending on `realloc` this operation
1163            // may shrink the buffer or leave it as it is.
1164            ptr = match unsafe {
1165                A::realloc(
1166                    Some(buf.cast()),
1167                    layout.into(),
1168                    old_layout.into(),
1169                    flags,
1170                    NumaNode::NO_NODE,
1171                )
1172            } {
1173                // If we fail to shrink, which likely can't even happen, continue with the existing
1174                // buffer.
1175                Err(_) => ptr,
1176                Ok(ptr) => {
1177                    cap = len;
1178                    ptr.as_ptr().cast()
1179                }
1180            };
1181        }
1182
1183        // SAFETY: If the iterator has been advanced, the advanced elements have been copied to
1184        // the beginning of the buffer and `len` has been adjusted accordingly.
1185        //
1186        // - `ptr` is guaranteed to point to the start of the backing buffer.
1187        // - `cap` is either the original capacity or, after shrinking the buffer, equal to `len`.
1188        // - `alloc` is guaranteed to be unchanged since `into_iter` has been called on the original
1189        //   `Vec`.
1190        unsafe { Vec::from_raw_parts(ptr, len, cap) }
1191    }
1192}
1193
1194impl<T, A> Iterator for IntoIter<T, A>
1195where
1196    A: Allocator,
1197{
1198    type Item = T;
1199
1200    /// # Examples
1201    ///
1202    /// ```
1203    /// let v = kernel::kvec![1, 2, 3]?;
1204    /// let mut it = v.into_iter();
1205    ///
1206    /// assert_eq!(it.next(), Some(1));
1207    /// assert_eq!(it.next(), Some(2));
1208    /// assert_eq!(it.next(), Some(3));
1209    /// assert_eq!(it.next(), None);
1210    ///
1211    /// # Ok::<(), Error>(())
1212    /// ```
1213    fn next(&mut self) -> Option<T> {
1214        if self.len == 0 {
1215            return None;
1216        }
1217
1218        let current = self.ptr;
1219
1220        // SAFETY: We can't overflow; decreasing `self.len` by one every time we advance `self.ptr`
1221        // by one guarantees that.
1222        unsafe { self.ptr = self.ptr.add(1) };
1223
1224        self.len -= 1;
1225
1226        // SAFETY: `current` is guaranteed to point at a valid element within the buffer.
1227        Some(unsafe { current.read() })
1228    }
1229
1230    /// # Examples
1231    ///
1232    /// ```
1233    /// let v: KVec<u32> = kernel::kvec![1, 2, 3]?;
1234    /// let mut iter = v.into_iter();
1235    /// let size = iter.size_hint().0;
1236    ///
1237    /// iter.next();
1238    /// assert_eq!(iter.size_hint().0, size - 1);
1239    ///
1240    /// iter.next();
1241    /// assert_eq!(iter.size_hint().0, size - 2);
1242    ///
1243    /// iter.next();
1244    /// assert_eq!(iter.size_hint().0, size - 3);
1245    ///
1246    /// # Ok::<(), Error>(())
1247    /// ```
1248    fn size_hint(&self) -> (usize, Option<usize>) {
1249        (self.len, Some(self.len))
1250    }
1251}
1252
1253impl<T, A> Drop for IntoIter<T, A>
1254where
1255    A: Allocator,
1256{
1257    fn drop(&mut self) {
1258        // SAFETY: `self.ptr` is guaranteed to be valid by the type invariant.
1259        unsafe { ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr, self.len)) };
1260
1261        // SAFETY:
1262        // - `self.buf` was previously allocated with `A`.
1263        // - `self.layout` matches the `ArrayLayout` of the preceding allocation.
1264        unsafe { A::free(self.buf.cast(), self.layout.into()) };
1265    }
1266}
1267
1268impl<T, A> IntoIterator for Vec<T, A>
1269where
1270    A: Allocator,
1271{
1272    type Item = T;
1273    type IntoIter = IntoIter<T, A>;
1274
1275    /// Consumes the `Vec<T, A>` and creates an `Iterator`, which moves each value out of the
1276    /// vector (from start to end).
1277    ///
1278    /// # Examples
1279    ///
1280    /// ```
1281    /// let v = kernel::kvec![1, 2]?;
1282    /// let mut v_iter = v.into_iter();
1283    ///
1284    /// let first_element: Option<u32> = v_iter.next();
1285    ///
1286    /// assert_eq!(first_element, Some(1));
1287    /// assert_eq!(v_iter.next(), Some(2));
1288    /// assert_eq!(v_iter.next(), None);
1289    ///
1290    /// # Ok::<(), Error>(())
1291    /// ```
1292    ///
1293    /// ```
1294    /// let v = kernel::kvec![];
1295    /// let mut v_iter = v.into_iter();
1296    ///
1297    /// let first_element: Option<u32> = v_iter.next();
1298    ///
1299    /// assert_eq!(first_element, None);
1300    ///
1301    /// # Ok::<(), Error>(())
1302    /// ```
1303    #[inline]
1304    fn into_iter(self) -> Self::IntoIter {
1305        let buf = self.ptr;
1306        let layout = self.layout;
1307        let (ptr, len, _) = self.into_raw_parts();
1308
1309        IntoIter {
1310            ptr,
1311            buf,
1312            len,
1313            layout,
1314            _p: PhantomData::<A>,
1315        }
1316    }
1317}
1318
1319/// An iterator that owns all items in a vector, but does not own its allocation.
1320///
1321/// # Invariants
1322///
1323/// Every `&mut T` returned by the iterator references a `T` that the iterator may take ownership
1324/// of.
1325pub struct DrainAll<'vec, T> {
1326    elements: slice::IterMut<'vec, T>,
1327}
1328
1329impl<'vec, T> Iterator for DrainAll<'vec, T> {
1330    type Item = T;
1331
1332    fn next(&mut self) -> Option<T> {
1333        let elem: *mut T = self.elements.next()?;
1334        // SAFETY: By the type invariants, we may take ownership of this value.
1335        Some(unsafe { elem.read() })
1336    }
1337
1338    fn size_hint(&self) -> (usize, Option<usize>) {
1339        self.elements.size_hint()
1340    }
1341}
1342
1343impl<'vec, T> Drop for DrainAll<'vec, T> {
1344    fn drop(&mut self) {
1345        if core::mem::needs_drop::<T>() {
1346            let iter = core::mem::take(&mut self.elements);
1347            let ptr: *mut [T] = iter.into_slice();
1348            // SAFETY: By the type invariants, we own these values so we may destroy them.
1349            unsafe { ptr::drop_in_place(ptr) };
1350        }
1351    }
1352}
1353
1354#[macros::kunit_tests(rust_kvec)]
1355mod tests {
1356    use super::*;
1357    use crate::prelude::*;
1358
1359    #[test]
1360    fn test_kvec_retain() {
1361        /// Verify correctness for one specific function.
1362        #[expect(clippy::needless_range_loop)]
1363        fn verify(c: &[bool]) {
1364            let mut vec1: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
1365            let mut vec2: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
1366
1367            for i in 0..c.len() {
1368                vec1.push_within_capacity(i).unwrap();
1369                if c[i] {
1370                    vec2.push_within_capacity(i).unwrap();
1371                }
1372            }
1373
1374            vec1.retain(|i| c[*i]);
1375
1376            assert_eq!(vec1, vec2);
1377        }
1378
1379        /// Add one to a binary integer represented as a boolean array.
1380        fn add(value: &mut [bool]) {
1381            let mut carry = true;
1382            for v in value {
1383                let new_v = carry != *v;
1384                carry = carry && *v;
1385                *v = new_v;
1386            }
1387        }
1388
1389        // This boolean array represents a function from index to boolean. We check that `retain`
1390        // behaves correctly for all possible boolean arrays of every possible length less than
1391        // ten.
1392        let mut func = KVec::with_capacity(10, GFP_KERNEL).unwrap();
1393        for len in 0..10 {
1394            for _ in 0u32..1u32 << len {
1395                verify(&func);
1396                add(&mut func);
1397            }
1398            func.push_within_capacity(false).unwrap();
1399        }
1400    }
1401}