Messages in this thread | ![/](/images/icornerl.gif) | | Date | Thu, 25 Apr 2024 21:45:54 +0000 | From | Benno Lossin <> | Subject | Re: [PATCH v3 2/5] rust: rbtree: add `RBTreeIterator` |
| |
On 18.04.24 16:15, Matt Gilbride wrote: > @@ -188,6 +212,25 @@ pub fn try_reserve_node() -> Result<RBTreeNodeReservation<K, V>> { > pub fn try_allocate_node(key: K, value: V) -> Result<RBTreeNode<K, V>> { > Ok(Self::try_reserve_node()?.into_node(key, value)) > } > + > + /// Returns an iterator over the tree nodes, sorted by key. > + pub fn iter(&self) -> RBTreeIterator<'_, K, V> { > + RBTreeIterator {
There is a missing `INVARIANT` comment here justifying the invariants of `RBTreeIterator`.
> + _tree: PhantomData, > + // SAFETY: `root` is valid as it's embedded in `self` and we have a valid `self`. > + next: unsafe { bindings::rb_first(&self.root) }, > + } > + } > + > + /// Returns an iterator over the keys of the nodes in the tree, in sorted order. > + pub fn keys(&self) -> impl Iterator<Item = &'_ K> { > + self.iter().map(|(k, _)| k) > + } > + > + /// Returns an iterator over the values of the nodes in the tree, sorted by key. > + pub fn values(&self) -> impl Iterator<Item = &'_ V> { > + self.iter().map(|(_, v)| v) > + } > } > > impl<K, V> RBTree<K, V> > @@ -373,6 +416,56 @@ 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`]. > +/// > +/// # Invariants > +/// - `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: The [`RBTreeIterator`] gives out immutable references to K and V, so it has the same > +// thread safety requirements as immutable references. > +unsafe impl<'a, K: Sync, V: Sync> Send for RBTreeIterator<'a, K, V> {}
The bounds on `K` and `V` look like typos to me. They should be `Send` instead.
> + > +// SAFETY: The [`RBTreeIterator`] gives out immutable references to K and V, so it has the same > +// thread safety requirements as immutable references. > +unsafe impl<'a, K: Sync, V: Sync> Sync for RBTreeIterator<'a, K, V> {} > + > +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: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self`
This is not an invariant of `Self`, but rather `RBTree` and `self` should be "`RBtree`s".
-- Cheers, Benno
> + // point to the links field of `Node<K, V>` objects. > + let cur = unsafe { container_of!(self.next, Node<K, V>, links) }; > + > + // SAFETY: `self.next` is a valid tree node by the type invariants. > + 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.769.g3c40516874-goog >
| ![\](/images/icornerr.gif) |