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.
Reviewed-by: Alice Ryhl <aliceryhl@xxxxxxxxxx>
Signed-off-by: Danilo Krummrich <dakr@xxxxxxxxxx>
---
rust/kernel/alloc.rs | 1 +
rust/kernel/alloc/kvec.rs | 181 ++++++++++++++++++++++++++++++++++++++
2 files changed, 182 insertions(+)
diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
index 4fb983b63d46..e8fbae2adadb 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 631a44e19f35..e91761c5c52d 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -14,6 +14,7 @@
ops::DerefMut,
ops::Index,
ops::IndexMut,
+ ptr,
ptr::NonNull,
slice,
slice::SliceIndex,
@@ -636,3 +637,183 @@ 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`] 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,
+ 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 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: The pointer in `self.0` is guaranteed to be valid by the type invariant.
+ 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()) };
+ }
+ }
+}
+
+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 (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.46.0
