From: Benno Lossin <benno.lossin@proton.me>
To: "Matt Gilbride" <mattgilbride@google.com>,
"Miguel Ojeda" <ojeda@kernel.org>,
"Alex Gaynor" <alex.gaynor@gmail.com>,
"Wedson Almeida Filho" <wedsonaf@gmail.com>,
"Boqun Feng" <boqun.feng@gmail.com>,
"Gary Guo" <gary@garyguo.net>,
"Björn Roy Baron" <bjorn3_gh@protonmail.com>,
"Andreas Hindborg" <a.hindborg@samsung.com>,
"Alice Ryhl" <aliceryhl@google.com>,
"Greg Kroah-Hartman" <gregkh@linuxfoundation.org>,
"Arve Hjønnevåg" <arve@android.com>,
"Todd Kjos" <tkjos@android.com>,
"Martijn Coenen" <maco@android.com>,
"Joel Fernandes" <joel@joelfernandes.org>,
"Carlos Llamas" <cmllamas@google.com>,
"Suren Baghdasaryan" <surenb@google.com>,
"Christian Brauner" <brauner@kernel.org>
Cc: Rob Landley <rob@landley.net>,
Davidlohr Bueso <dave@stgolabs.net>,
Michel Lespinasse <michel@lespinasse.org>,
rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: Re: [PATCH v2 3/6] rust: rbtree: add `RBTreeIterator`
Date: Thu, 14 Mar 2024 16:24:23 +0000 [thread overview]
Message-ID: <00178dbe-6dfc-48f5-9712-b0b7361d14e4@proton.me> (raw)
In-Reply-To: <20240219-b4-rbtree-v2-3-0b113aab330d@google.com>
On 2/19/24 12:48, Matt Gilbride wrote:
> @@ -350,6 +393,52 @@ fn drop(&mut self) {
> }
> }
>
> +impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
> + type Item = (&'a K, &'a V);
> + type IntoIter = RBTreeIterator<'a, K, V>;
> +
> + fn into_iter(self) -> Self::IntoIter {
> + self.iter()
> + }
> +}
> +
> +/// An iterator over the nodes of a [`RBTree`].
> +///
> +/// Instances are created by calling [`RBTree::iter`].
There probably should be some invariants here, like
- `self.next` is a valid pointer
- `self.next` points to a node stored inside of a valid `RBtree`
> +pub struct RBTreeIterator<'a, K, V> {
> + _tree: PhantomData<&'a RBTree<K, V>>,
> + next: *mut bindings::rb_node,
> +}
> +
> +// SAFETY: An [`RBTree`] allows the same kinds of access to its values that a struct allows to its
> +// fields, so we use the same Send condition as would be used for a struct with K and V fields.
> +unsafe impl<'a, K: Send, V: Send> Send for RBTreeIterator<'a, K, V> {}
> +
> +// SAFETY: An [`RBTree`] allows the same kinds of access to its values that a struct allows to its
> +// fields, so we use the same Sync condition as would be used for a struct with K and V fields.
> +unsafe impl<'a, K: Sync, V: Sync> Sync for RBTreeIterator<'a, K, V> {}
These comments should also be updated.
> +
> +impl<'a, K, V> Iterator for RBTreeIterator<'a, K, V> {
> + type Item = (&'a K, &'a V);
> +
> + fn next(&mut self) -> Option<Self::Item> {
> + if self.next.is_null() {
> + return None;
> + }
> +
> + // SAFETY: All links fields we create are in a `Node<K, V>`.
See my suggestion on patch 2.
> + let cur = unsafe { crate::container_of!(self.next, Node<K, V>, links) };
> +
> + // SAFETY: The reference to the tree used to create the iterator outlives the iterator, so
> + // the tree cannot change. By the tree invariant, all nodes are valid.
Why does the pointer come from a tree to begin with? (ie you need the
invariants I stated above)
--
Cheers,
Benno
> + self.next = unsafe { bindings::rb_next(self.next) };
> +
> + // SAFETY: By the same reasoning above, it is safe to dereference the node. Additionally,
> + // it is ok to return a reference to members because the iterator must outlive it.
> + Some(unsafe { (&(*cur).key, &(*cur).value) })
> + }
> +}
> +
> /// A memory reservation for a red-black tree node.
> ///
> /// It contains the memory needed to hold a node that can be inserted into a red-black tree. One
>
> --
> 2.44.0.rc0.258.g7320e95886-goog
>
next prev parent reply other threads:[~2024-03-14 16:24 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-02-19 11:48 [PATCH v2 0/6] Red-black tree abstraction needed by Rust Binder Matt Gilbride
2024-02-19 11:48 ` [PATCH v2 1/6] rust: add `container_of!` macro Matt Gilbride
2024-02-25 20:28 ` Miguel Ojeda
2024-02-19 11:48 ` [PATCH v2 2/6] rust: rbtree: add red-black tree implementation backed by the C version Matt Gilbride
2024-03-14 14:19 ` Benno Lossin
2024-02-19 11:48 ` [PATCH v2 3/6] rust: rbtree: add `RBTreeIterator` Matt Gilbride
2024-03-14 16:24 ` Benno Lossin [this message]
2024-02-19 11:48 ` [PATCH v2 4/6] rust: rbtree: add `RBTreeIteratorMut` Matt Gilbride
2024-03-14 16:27 ` Benno Lossin
2024-02-19 11:48 ` [PATCH v2 5/6] rust: rbtree: add `RBTreeCursor` Matt Gilbride
2024-03-14 17:13 ` Benno Lossin
2024-02-19 11:48 ` [PATCH v2 6/6] rust: rbtree: add `RBTree::entry` Matt Gilbride
2024-03-15 11:43 ` Benno Lossin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=00178dbe-6dfc-48f5-9712-b0b7361d14e4@proton.me \
--to=benno.lossin@proton.me \
--cc=a.hindborg@samsung.com \
--cc=alex.gaynor@gmail.com \
--cc=aliceryhl@google.com \
--cc=arve@android.com \
--cc=bjorn3_gh@protonmail.com \
--cc=boqun.feng@gmail.com \
--cc=brauner@kernel.org \
--cc=cmllamas@google.com \
--cc=dave@stgolabs.net \
--cc=gary@garyguo.net \
--cc=gregkh@linuxfoundation.org \
--cc=joel@joelfernandes.org \
--cc=linux-kernel@vger.kernel.org \
--cc=maco@android.com \
--cc=mattgilbride@google.com \
--cc=michel@lespinasse.org \
--cc=ojeda@kernel.org \
--cc=rob@landley.net \
--cc=rust-for-linux@vger.kernel.org \
--cc=surenb@google.com \
--cc=tkjos@android.com \
--cc=wedsonaf@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).