From 336f802b94badd3742d0e4c38b95b0730c3e39d6 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Tue, 23 Jul 2024 18:59:07 +0200 Subject: rust: alloc: implement `IntoIterator` for `Vec` 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 --- 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 4d7190594076..4035644b5dca 100644 --- a/rust/kernel/alloc.rs +++ b/rust/kernel/alloc.rs @@ -19,6 +19,7 @@ pub use self::kbox::KBox; 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 351c4f1702db..cc8f3c555d1e 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -11,6 +11,7 @@ use core::{ ops::DerefMut, ops::Index, ops::IndexMut, + ptr, ptr::NonNull, slice, slice::SliceIndex, @@ -611,3 +612,186 @@ __impl_slice_eq! { [A: Allocator] Vec, [U] } __impl_slice_eq! { [A: Allocator] [T], Vec } __impl_slice_eq! { [A: Allocator, const N: usize] Vec, [U; N] } __impl_slice_eq! { [A: Allocator, const N: usize] Vec, &[U; N] } + +impl<'a, T, A> IntoIterator for &'a Vec +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 +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 { + ptr: *mut T, + buf: NonNull, + len: usize, + cap: usize, + _p: PhantomData, +} + +impl IntoIter +where + A: Allocator, +{ + fn as_raw_mut_slice(&mut self) -> *mut [T] { + ptr::slice_from_raw_parts_mut(self.ptr, self.len) + } +} + +impl Iterator for IntoIter +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 { + if self.len == 0 { + return None; + } + + let ptr = self.ptr; + if !Vec::::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 = 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) { + (self.len, Some(self.len)) + } +} + +impl Drop for IntoIter +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 IntoIterator for Vec +where + A: Allocator, +{ + type Item = T; + type IntoIter = IntoIter; + + /// Consumes the `Vec` 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 = 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 = 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::, + } + } +} -- cgit v1.2.3-58-ga151