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@kernel.org>
---
rust/kernel/alloc.rs | 1 +
rust/kernel/alloc/kvec.rs | 184 ++++++++++++++++++++++++++++++++++++++
2 files changed, 185 insertions(+)
diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
index e88c7e10ee9b..4ff4df4597a3 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 89afc0f25bd4..3b79f977b65e 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -11,6 +11,7 @@
ops::DerefMut,
ops::Index,
ops::IndexMut,
+ ptr,
ptr::NonNull,
slice,
slice::SliceIndex,
@@ -627,3 +628,186 @@ 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<T,A>` 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 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()) };
+ }
+ }
+}
+
+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.0On 16.08.24 02:10, Danilo Krummrich 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@kernel.org>
> ---
> rust/kernel/alloc.rs | 1 +
> rust/kernel/alloc/kvec.rs | 184 ++++++++++++++++++++++++++++++++++++++
> 2 files changed, 185 insertions(+)
>
> diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
> index e88c7e10ee9b..4ff4df4597a3 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 89afc0f25bd4..3b79f977b65e 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -11,6 +11,7 @@
> ops::DerefMut,
> ops::Index,
> ops::IndexMut,
> + ptr,
> ptr::NonNull,
> slice,
> slice::SliceIndex,
> @@ -627,3 +628,186 @@ 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<T,A>` that moves elements out of a vector.
Please make both links.
> +///
> +/// This structure is created by the `Vec::into_iter` method on [`Vec`] (provided by the
Ditto.
> +/// [`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>,
No invariants for these two fields?
> + 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>(())
> + /// ```
AFAIK documentation on functions in trait implementations won't show up
in rustdoc (I just checked this). So I would remove it.
> + 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.
Note that `<*mut T>::add` advances the pointer by `size_of::<T>()`
bytes. So in the case that `T` is a ZST, it won't be advanced.
So you could remove this `if`.
> + }
> + 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.
This comment explains why you are doing it, not why it's ok to do it.
> + 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>(())
> + /// ```
I feel a bit bad that you wrote all of this nice documentation for
functions that receive their documentation from the trait...
---
Cheers,
Benno
> + #[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
>
On Tue, Sep 10, 2024 at 08:04:27PM +0000, Benno Lossin wrote:
> On 16.08.24 02:10, Danilo Krummrich 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@kernel.org>
> > ---
> > rust/kernel/alloc.rs | 1 +
> > rust/kernel/alloc/kvec.rs | 184 ++++++++++++++++++++++++++++++++++++++
> > 2 files changed, 185 insertions(+)
> >
> > diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
> > index e88c7e10ee9b..4ff4df4597a3 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 89afc0f25bd4..3b79f977b65e 100644
> > --- a/rust/kernel/alloc/kvec.rs
> > +++ b/rust/kernel/alloc/kvec.rs
> > @@ -11,6 +11,7 @@
> > ops::DerefMut,
> > ops::Index,
> > ops::IndexMut,
> > + ptr,
> > ptr::NonNull,
> > slice,
> > slice::SliceIndex,
> > @@ -627,3 +628,186 @@ 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<T,A>` that moves elements out of a vector.
>
> Please make both links.
>
> > +///
> > +/// This structure is created by the `Vec::into_iter` method on [`Vec`] (provided by the
>
> Ditto.
>
> > +/// [`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>,
>
> No invariants for these two fields?
Suggestions?
>
> > + 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>(())
> > + /// ```
>
> AFAIK documentation on functions in trait implementations won't show up
> in rustdoc (I just checked this). So I would remove it.
They don't, but the KUnit tests are still executed. :)
>
> > + 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.
>
> Note that `<*mut T>::add` advances the pointer by `size_of::<T>()`
> bytes. So in the case that `T` is a ZST, it won't be advanced.
> So you could remove this `if`.
>
> > + }
> > + 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.
>
> This comment explains why you are doing it, not why it's ok to do it.
>
> > + 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>(())
> > + /// ```
>
> I feel a bit bad that you wrote all of this nice documentation for
> functions that receive their documentation from the trait...
No worries, I really only added them for the KUnit tests.
>
> ---
> Cheers,
> Benno
>
> > + #[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
> >
>
On 11.09.24 01:39, Danilo Krummrich wrote:
> On Tue, Sep 10, 2024 at 08:04:27PM +0000, Benno Lossin wrote:
>> On 16.08.24 02:10, Danilo Krummrich wrote:
>>> +/// [`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>,
>>
>> No invariants for these two fields?
>
> Suggestions?
When determining the invariants, I look at the places where you would
want to use them, ie the `SAFETY` comments that use these fields:
- for `buf` you only use it to free the backing allocation, so you only
need that it has been allocated by `A` if `cap != 0`.
- for `ptr` you need that it is valid for reads for `size_of::<T>() *
length` bytes.
So I would put those two things into invariants.
>>> + 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>(())
>>> + /// ```
>>
>> AFAIK documentation on functions in trait implementations won't show up
>> in rustdoc (I just checked this). So I would remove it.
>
> They don't, but the KUnit tests are still executed. :)
Oh I see, then may I suggest moving them to the module documentation or
put them onto `Vec`, that way people can also read them :)
---
Cheers,
Benno
On Wed, Sep 11, 2024 at 08:52:03AM +0000, Benno Lossin wrote:
> On 11.09.24 01:39, Danilo Krummrich wrote:
> > On Tue, Sep 10, 2024 at 08:04:27PM +0000, Benno Lossin wrote:
> >> On 16.08.24 02:10, Danilo Krummrich wrote:
> >>> +/// [`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>,
> >>
> >> No invariants for these two fields?
> >
> > Suggestions?
>
> When determining the invariants, I look at the places where you would
> want to use them, ie the `SAFETY` comments that use these fields:
> - for `buf` you only use it to free the backing allocation, so you only
> need that it has been allocated by `A` if `cap != 0`.
> - for `ptr` you need that it is valid for reads for `size_of::<T>() *
> length` bytes.
>
> So I would put those two things into invariants.
>
> >>> + 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>(())
> >>> + /// ```
> >>
> >> AFAIK documentation on functions in trait implementations won't show up
> >> in rustdoc (I just checked this). So I would remove it.
> >
> > They don't, but the KUnit tests are still executed. :)
>
> Oh I see, then may I suggest moving them to the module documentation or
> put them onto `Vec`, that way people can also read them :)
Hm, I'd rather keep them close on the functions they're testing. Those examples
probably don't have a huge documentation purpose. As you've said, the trait is
documented already and has examples.
>
> ---
> Cheers,
> Benno
>
>
On Fri, Aug 16, 2024 at 2:13 AM Danilo Krummrich <dakr@kernel.org> 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@kernel.org>
This looks ok to me. One nit below, though. Either way:
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
> rust/kernel/alloc.rs | 1 +
> rust/kernel/alloc/kvec.rs | 184 ++++++++++++++++++++++++++++++++++++++
> 2 files changed, 185 insertions(+)
>
> diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
> index e88c7e10ee9b..4ff4df4597a3 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 89afc0f25bd4..3b79f977b65e 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -11,6 +11,7 @@
> ops::DerefMut,
> ops::Index,
> ops::IndexMut,
> + ptr,
> ptr::NonNull,
> slice,
> slice::SliceIndex,
> @@ -627,3 +628,186 @@ 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<T,A>` 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 ptr = self.ptr;
Nit: It would probably be slightly clearer to rename this variable to `current`.
> + 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()) };
> + }
> + }
> +}
> +
> +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
>
© 2016 - 2024 Red Hat, Inc.