From patchwork Tue Oct 1 14:59:52 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Danilo Krummrich X-Patchwork-Id: 13818236 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 59ED5CEACD5 for ; Tue, 1 Oct 2024 15:01:56 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DADF8680014; Tue, 1 Oct 2024 11:01:55 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id D34EB280068; Tue, 1 Oct 2024 11:01:55 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id BD655680014; Tue, 1 Oct 2024 11:01:55 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 9D0A4280068 for ; Tue, 1 Oct 2024 11:01:55 -0400 (EDT) Received: from smtpin12.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 44A86ACC16 for ; Tue, 1 Oct 2024 15:01:55 +0000 (UTC) X-FDA: 82625348190.12.AEA5F5F Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf28.hostedemail.com (Postfix) with ESMTP id 2331CC004B for ; Tue, 1 Oct 2024 15:01:49 +0000 (UTC) Authentication-Results: imf28.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=k+4rDUfw; spf=pass (imf28.hostedemail.com: domain of dakr@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=dakr@kernel.org; dmarc=pass (policy=quarantine) header.from=kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1727794845; a=rsa-sha256; cv=none; b=V1dIowkN9/wnEj4HQ4Tk/zoclnIQKPFJljMOtJzA+fL/Bvji7585ghVfLQ7LrT7X1or7oe jh9thUFbL2ak8E+jftRTyrztxPy9qBX1ZTMzPZzfX2ZzXQpSfn+rnZ5QEcnWNqfyeukCwY BKJyxHPKjUfguSkzCp9ey6h5SDTIRYQ= ARC-Authentication-Results: i=1; imf28.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=k+4rDUfw; spf=pass (imf28.hostedemail.com: domain of dakr@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=dakr@kernel.org; dmarc=pass (policy=quarantine) header.from=kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1727794845; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=/E1181t6qi/Z0YbUxbEc267BdYuyo2NyzYGplhXduPg=; b=5F0LmR7V3080by/sX/zNeaczydAC2r10/OFNIhFoGbOFQKI6WvtqZbKvbuvJ6oM0yw7EEU 4j1QOHNEzmc+sDwyUunCL5SEwl8prKxOxGjwo6Cunftr3B7WKmfyhBMjwaFN4VaSLBrLR2 2mf1yXjWIM3YoGETsuF6NJqDSRW9MZo= Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by dfw.source.kernel.org (Postfix) with ESMTP id 17BDD5C4CCF; Tue, 1 Oct 2024 15:01:45 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id DD97FC4CED2; Tue, 1 Oct 2024 15:01:43 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1727794908; bh=WU3ilb+F7s6b0hCQthPkZjMBffv2TQREL2Wt+coFn1Y=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=k+4rDUfwl31k9vhU3jqNUMnH4fBOcloRkW7bgFCmZteeG1L7uc8Onk3lICt6F2g7+ LPnLqF6Gnx6shQhayZZV8xFbO7RbPBVcfB3Zc3aigG0yeGTs8z6WVJ0zLwzlAfpX7Z UUDGoOQY6GGxPO8RzrxBJsyacERIK386bw4pVODb33U0ExScCmvhFzNC1OE6fhfuji j3RB4zmU7ne40f5en49QARsqgPATsXh0dlniG0PKwZoOk4iRITv2V2nUPmbue2Zkz9 AC4RjZtjgb0zVt7med1hZfU9dG5GUDo675PpSipEdmGHY37AjT0DYIryY7p2QuOvTC YcmG6MBUkUUKg== From: Danilo Krummrich To: ojeda@kernel.org, alex.gaynor@gmail.com, wedsonaf@gmail.com, boqun.feng@gmail.com, gary@garyguo.net, bjorn3_gh@protonmail.com, benno.lossin@proton.me, a.hindborg@samsung.com, aliceryhl@google.com, akpm@linux-foundation.org Cc: daniel.almeida@collabora.com, faith.ekstrand@collabora.com, boris.brezillon@collabora.com, lina@asahilina.net, mcanal@igalia.com, zhiw@nvidia.com, cjia@nvidia.com, jhubbard@nvidia.com, airlied@redhat.com, ajanulgu@redhat.com, lyude@redhat.com, linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, linux-mm@kvack.org, Danilo Krummrich Subject: [PATCH v8 17/29] rust: alloc: implement `IntoIterator` for `Vec` Date: Tue, 1 Oct 2024 16:59:52 +0200 Message-ID: <20241001150008.183102-18-dakr@kernel.org> X-Mailer: git-send-email 2.46.1 In-Reply-To: <20241001150008.183102-1-dakr@kernel.org> References: <20241001150008.183102-1-dakr@kernel.org> MIME-Version: 1.0 X-Stat-Signature: 8pnhpchgxebzfthrsfgpf8bjawk3kkm3 X-Rspamd-Queue-Id: 2331CC004B X-Rspam-User: X-Rspamd-Server: rspam10 X-HE-Tag: 1727794909-414174 X-HE-Meta: U2FsdGVkX1+tSWXXSiQUBiFFyaGgLg992IgRD7BQvdQVtdOEe6ob4oLTmHtPylgz9oBNrwJKrdbVG2bhJQZMn1N2JMq+Hbb/DI3I4ALS0hOIuuxc0X9HTWBErBy7igFMePWLDw4ye6t5cWWFO/7+bZBnKC624YYxPyWp4P2btxyX/sbiXu8pbgry1NNcETzQ9aqwUeDO1az8NXAJetXh41SVkLmiuX+uup3tXoxBq5t7fqL5l5um9bxg3I0udl3MJdPNn1WSdsRIfyn9YlSUrvOLnR+Ihp6t1gaU5NiN5FW68bzjZjQp6zoGvImfKVVewVjUa1DF2iXtk8S0HH0ZdNy+7chMNk8tIkSHXinLZJw/Qqs3qIxTCT/ACu9m9sC7o99iuP4f9z9FNe92j/2QJmQ7OG/XCXE0bwLUMHq3XVFd+3+ves6zoboh607vgAOvcAMh9i2VIAV11yUEfN/zsF1Yy/1tZcOmQwz8cJnxugRYrRe8SH+sM8JUQqG/bpgpzRtGhE6I+pNc8v77+dAXkfVt28DqEevaymzvT2nMcMctY2iBTK0hWmwBgvd+O+2oPyuB3aMmyo/FGfYAtdTYaZQOaaah8ASfYUlr/VP09diAH4pRvOJkcKyZA4iINNlcVIyoEJ884Is+efeHczcalbL+ZEXVpCLADXLjD58XeGLXnymShLhkgJKb4lg40TbYyOiA0zc2h8kbObAVebhWt/2rnXClbIlFnZ1bnptY/OW1g2vJs7umIKRXNml3ugLpZZlVQ7EwP2D+Elykz7dUAUOg8D31saC4g/38huv/P7UB/m7lbk4Wu+XVXz6XJYZSlo3OdbudyFR5F3nw+h2yb5LQEH0VBkzSsqLR2ujm37gIzbDKJww+ftewboVnkwUJKdNpQyz/zE/3EEIFiGi/xcQq8683ay9HeZR3Soic/970UoEaEmQXmaWhAn91sDKVzW/ek5l0rA6XRPXKl6x poIngHDe 7LR+PmdgG8ks+0LhtN1f14UYi6TUvS3kX2TmDf7o6yOyrqsACABsjZlza04m8n7bEWex4zx9E4CfUhR6C/t0x2YOfGPGjVsFZGCeR2W39qIYkLdQdl+zyBV4ZLFBGdh1Xsy2YeKjXxdpbK5ZJqPZivFBkMUbUFgHUhGnwhJ3RgQRCSMfB4Sfzfnm/sMRUY9D/Yr4os5xDKz5VPzPNpo7lDNXuuHBpUh+Vfb1g9JDWyltGFoLsgL0KmnXvCBfRxjg9cwprIzibHduITOeEVghaf7asxaJeyxKR7yjncwAL5+f2O50mGm98hnBWDs/57jZJj5F6zo4g1xyLV8khNDmCJbdfWZx2eEPJG+M6d2WRsMqf2OabN17O7ug1/eZiMWpUmn4Z X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 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 Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich --- rust/kernel/alloc.rs | 1 + rust/kernel/alloc/kvec.rs | 170 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 171 insertions(+) diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs index 961070daf6db..1d57bfe2acb1 100644 --- a/rust/kernel/alloc.rs +++ b/rust/kernel/alloc.rs @@ -20,6 +20,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 44aade0a653b..ff1c152d3423 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -635,3 +635,173 @@ fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] } [A: Allocator, const N: usize] Vec, [U; N], [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, + layout: ArrayLayout, + _p: PhantomData, +} + +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 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 = 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: `self.ptr` is guaranteed to be valid by the type invariant. + unsafe { ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr, self.len)) }; + + // SAFETY: + // - `self.buf` was previously allocated with `A`. + // - `self.layout` matches the `ArrayLayout` of the preceeding allocation. + unsafe { A::free(self.buf.cast(), self.layout.into()) }; + } +} + +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 buf = self.ptr; + let layout = self.layout; + let (ptr, len, _) = self.into_raw_parts(); + + IntoIter { + ptr, + buf, + len, + layout, + _p: PhantomData::, + } + } +}