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 v3 5/5] rust: rbtree: add `RBTree::entry`
Date: Fri, 26 Apr 2024 07:05:07 +0000 [thread overview]
Message-ID: <d243524f-96af-4375-a8c9-44196a110853@proton.me> (raw)
In-Reply-To: <20240418-b4-rbtree-v3-5-323e134390ce@google.com>
On 18.04.24 16:15, Matt Gilbride wrote:
> @@ -332,63 +338,54 @@ pub fn insert(&mut self, RBTreeNode { node }: RBTreeNode<K, V>) -> Option<RBTree
> // we store `parent` and `child_field_of_parent`, and the new `node` will go somewhere
> // in the subtree of `parent` that `child_field_of_parent` points at. Once
> // we find an empty subtree, we can insert the new node using `rb_link_node`.
> - let mut parent = core::ptr::null_mut();
> let mut child_field_of_parent: &mut *mut bindings::rb_node = &mut self.root.rb_node;
> - while !child_field_of_parent.is_null() {
> - parent = *child_field_of_parent;
> + let mut parent = core::ptr::null_mut();
Nit: why are you moving this line below `child_field_of_parent`? Just an
artifact of rebasing?
> + while !(*child_field_of_parent).is_null() {
> + let curr = *child_field_of_parent;
> + // SAFETY: All links fields we create are in a `Node<K, V>`.
> + let node = unsafe { container_of!(curr, Node<K, V>, links) };
[...]
> @@ -1119,3 +1099,177 @@ unsafe impl<K: Send, V: Send> Send for RBTreeNode<K, V> {}
> // SAFETY: If K and V can be accessed without synchronization, then it's also okay to access
> // [`RBTreeNode`] without synchronization.
> unsafe impl<K: Sync, V: Sync> Sync for RBTreeNode<K, V> {}
> +
> +impl<K, V> RBTreeNode<K, V> {
> + /// Drop the key and value, but keep the allocation.
> + ///
> + /// It then becomes a reservation that can be re-initialised into a different node (i.e., with
> + /// a different key and/or value).
> + ///
> + /// The existing key and value are dropped in-place as part of this operation, that is, memory
> + /// may be freed (but only for the key/value; memory for the node itself is kept for reuse).
> + pub fn into_reservation(self) -> RBTreeNodeReservation<K, V> {
> + let raw = Box::into_raw(self.node);
> + let mut ret = RBTreeNodeReservation {
> + // SAFETY: The pointer came from a valid `Node`, which has the same layout as
> + // `MaybeUninit<Node>`.
> + node: unsafe { Box::from_raw(raw as _) },
> + };
> + // SAFETY: Although the type is `MaybeUninit<Node>`, we know it has been initialised
> + // because it came from a `Node`. So it is safe to drop it.
> + unsafe { core::ptr::drop_in_place::<Node<K, V>>(ret.node.as_mut_ptr()) };
> + ret
> + }
With my patch [1] this can be simplified.
[1]: https://lore.kernel.org/rust-for-linux/20240425213419.3904105-1-benno.lossin@proton.me/
> +}
> +
> +/// A view into a single entry in a map, which may either be vacant or occupied.
> +///
> +/// This enum is constructed from the [`entry`] method on [`RBTree`].
You could just write [`RBTree::entry`].
> +///
> +/// [`entry`]: fn@RBTree::entry
> +pub enum Entry<'a, K, V> {
> + /// This [`RBTree`] does not have a node with this key.
> + Vacant(VacantEntry<'a, K, V>),
> + /// This [`RBTree`] already has a node with this key.
> + Occupied(OccupiedEntry<'a, K, V>),
> +}
[...]
> +impl<'a, K, V> RawVacantEntry<'a, K, V> {
> + /// Inserts the given node into the [`RBTree`] at this entry.
> + ///
> + /// The `node` must have a key such that inserting it here does not break the ordering of this
> + /// [`RBTree`].
> + fn insert(self, node: RBTreeNode<K, V>) -> &'a mut V {
> + let node = Box::into_raw(node.node);
> +
> + // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when
> + // the node is removed or replaced.
> + let node_links = unsafe { addr_of_mut!((*node).links) };
> +
> + // INVARIANT: We are linking in a new node, which is valid. It remains valid because we
> + // "forgot" it with `Box::into_raw`.
> + // SAFETY: All pointers are null or valid in an appropriate way.
I don't like the formulation "valid in an appropriate way", since if you
don't know what the appropriate way is, this doesn't help you.
> + unsafe { bindings::rb_link_node(node_links, self.parent, self.child_field_of_parent) };
> +
> + // SAFETY: All pointers are valid. `node` has just been inserted into the tree.
> + unsafe { bindings::rb_insert_color(node_links, &mut self.rbtree.root) };
> +
> + // SAFETY: The node is valid until we remove it from the tree.
> + unsafe { &mut (*node).value }
> + }
> +}
> +
> +impl<'a, K, V> VacantEntry<'a, K, V> {
> + /// Inserts the given node into the [`RBTree`] at this entry.
> + pub fn insert(self, value: V, reservation: RBTreeNodeReservation<K, V>) -> &'a mut V {
> + self.raw.insert(reservation.into_node(self.key, value))
> + }
> +}
> +
> +/// A view into an occupied entry in a [`RBTree`]. It is part of the [`Entry`] enum.
> +///
> +/// # Invariants
> +/// - `node_links` is a valid, non-null pointer to a tree node.
It should be the same tree as `self.rbtree`, right? (I see you calling
`rb_replace_node` below with the rbtree root used)
--
Cheers,
Benno
> +pub struct OccupiedEntry<'a, K, V> {
> + rbtree: &'a mut RBTree<K, V>,
> + /// The node that this entry corresponds to.
> + node_links: *mut bindings::rb_node,
> +}
prev parent reply other threads:[~2024-04-26 7:05 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-04-18 14:15 [PATCH v3 0/5] Red-black tree abstraction needed by Rust Binder Matt Gilbride
2024-04-18 14:15 ` [PATCH v3 1/5] rust: rbtree: add red-black tree implementation backed by the C version Matt Gilbride
2024-04-25 21:26 ` Benno Lossin
2024-04-18 14:15 ` [PATCH v3 2/5] rust: rbtree: add `RBTreeIterator` Matt Gilbride
2024-04-25 21:45 ` Benno Lossin
2024-04-25 21:56 ` Benno Lossin
2024-04-18 14:15 ` [PATCH v3 3/5] rust: rbtree: add `RBTreeIteratorMut` Matt Gilbride
2024-04-25 21:58 ` Benno Lossin
2024-04-18 14:15 ` [PATCH v3 4/5] rust: rbtree: add `RBTreeCursor` Matt Gilbride
2024-04-25 22:20 ` Benno Lossin
2024-04-18 14:15 ` [PATCH v3 5/5] rust: rbtree: add `RBTree::entry` Matt Gilbride
2024-04-26 7:05 ` Benno Lossin [this message]
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=d243524f-96af-4375-a8c9-44196a110853@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).