On Thu, Aug 1, 2024 at 2:08 AM Danilo Krummrich <dakr@xxxxxxxxxx> wrote:
>
> Implement `IntoIterator` for `Vec`, `Vec`'s `IntoIter` type, as well as
> `Iterator` for `IntoIter`.
>
> `Vec::into_iter` disassembles the `Vec` into its raw parts; additionally,
> `IntoIter` keeps track of a separate pointer, which is incremented
> correspondingsly as the iterator advances, while the length, or the count
> of elements, is decremented.
>
> This also means that `IntoIter` takes the ownership of the backing
> buffer and is responsible to drop the remaining elements and free the
> backing buffer, if it's dropped.
>
> Signed-off-by: Danilo Krummrich <dakr@xxxxxxxxxx>
> ---
> rust/kernel/alloc.rs | 1 +
> rust/kernel/alloc/kvec.rs | 186 ++++++++++++++++++++++++++++++++++++++
> 2 files changed, 187 insertions(+)
>
> diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
> index bd93140f3094..f2998ad57456 100644
> --- a/rust/kernel/alloc.rs
> +++ b/rust/kernel/alloc.rs
> @@ -19,6 +19,7 @@
> pub use self::kbox::KVBox;
> pub use self::kbox::VBox;
>
> +pub use self::kvec::IntoIter;
> pub use self::kvec::KVVec;
> pub use self::kvec::KVec;
> pub use self::kvec::VVec;
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index 04cc85f7d92c..50e7705e5686 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -12,6 +12,8 @@
> ops::DerefMut,
> ops::Index,
> ops::IndexMut,
> + ptr,
> + ptr::NonNull,
> slice,
> slice::SliceIndex,
> };
> @@ -581,3 +583,187 @@ fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] }
> __impl_slice_eq! { [A: Allocator] [T], Vec<U, A> }
> __impl_slice_eq! { [A: Allocator, const N: usize] Vec<T, A>, [U; N] }
> __impl_slice_eq! { [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 that moves out of a vector.
> +///
> +/// This `struct` is created by the `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,
> + cap: usize,
> + _p: PhantomData<A>,
> +}
> +
> +impl<T, A> IntoIter<T, A>
> +where
> + A: Allocator,
> +{
> + fn as_raw_mut_slice(&mut self) -> *mut [T] {
> + ptr::slice_from_raw_parts_mut(self.ptr, self.len)
> + }
> +}
> +
> +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 ptr = self.ptr;
> + if !Vec::<T, A>::is_zst() {
> + // SAFETY: We can't overflow; `end` is guaranteed to mark the end of the buffer.
> + unsafe { self.ptr = self.ptr.add(1) };
> + } else {
> + // For ZST `ptr` has to stay where it is to remain aligned, so we just reduce `self.len`
> + // by 1.
> + }
> + self.len -= 1;
> +
> + // SAFETY: `ptr` is guaranteed to point at a valid element within the buffer.
> + Some(unsafe { ptr.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: Drop the remaining vector's elements in place, before we free the backing
> + // memory.
> + unsafe { ptr::drop_in_place(self.as_raw_mut_slice()) };
> +
> + // If `cap == 0` we never allocated any memory in the first place.
> + if self.cap != 0 {
> + // SAFETY: `self.buf` was previously allocated with `A`.
> + unsafe { A::free(self.buf.cast()) };
> + }
Is this ok for ZST?
> + }
> +}
> +
> +impl<T, A> IntoIterator for Vec<T, A>
> +where
> + A: Allocator,
> +{
> + type Item = T;
> + type IntoIter = IntoIter<T, A>;
> +
> + /// Creates a consuming iterator, that is, one that moves each value out of
> + /// the vector (from start to end). The vector cannot be used after calling
> + /// this.
> + ///
> + /// # 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 (ptr, len, cap) = self.into_raw_parts();
> +
> + IntoIter {
> + ptr,
> + // SAFETY: `ptr` is either a dangling pointer or a pointer to a valid memory
> + // allocation, allocated with `A`.
> + buf: unsafe { NonNull::new_unchecked(ptr) },
> + len,
> + cap,
> + _p: PhantomData::<A>,
> + }
> + }
> +}
> --
> 2.45.2
>
