Re: [PATCH v2 3/6] rust: rbtree: add `RBTreeIterator`

[Benno Lossin]

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
>