Re: [PATCH v4 5/6] rust: rbtree: add `RBTreeCursor`

[Boqun Feng]

On Mon, Jun 03, 2024 at 04:05:20PM +0000, Matt Gilbride wrote:
[...]
> +    /// Remove the current node from the tree.
> +    ///
> +    /// Returns a cursor to the next node, if it exists,
> +    /// else the previous node. Returns [`None`] if the tree
> +    /// becomes empty.
> +    pub fn remove_current(self) -> Option<Self> {

I'd expect this function returns a `(Option<Self>, Option<RBTreeNode>)`
or something similar, since it removes a node in a tree, could you
explain why we don't need to care the removed node?

Regards,
Boqun

> +        let prev = self.get_neighbor_raw(Direction::Prev);
> +        let next = self.get_neighbor_raw(Direction::Next);
> +        // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self`
> +        // point to the links field of `Node<K, V>` objects.
> +        let this = unsafe { container_of!(self.current, Node<K, V>, links) }.cast_mut();
> +        // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so
> +        // the tree cannot change. By the tree invariant, all nodes are valid.
> +        unsafe { bindings::rb_erase(&mut (*this).links, addr_of_mut!(self.tree.root)) };
> +
> +        let current = match (prev, next) {
> +            (_, Some(next)) => next,
> +            (Some(prev), None) => prev,
> +            (None, None) => {
> +                return None;
> +            }
> +        };
> +
> +        // INVARIANT:
> +        // - `current` is a valid node in the [`RBTree`] pointed to by `self.tree`.
> +        // - Due to the function signature, `self` is an owned [`RBTreeCursor`],
> +        //   and [`RBTreeCursor`]s are only created via functions with a mutable reference
> +        //   to an [`RBTree`].
> +        Some(Self {
> +            current,
> +            tree: self.tree,
> +        })
> +    }
> +
> +    /// Remove the previous node, returning it if it exists.
> +    pub fn remove_prev(&mut self) -> Option<RBTreeNode<K, V>> {
> +        self.remove_neighbor(Direction::Prev)
> +    }
> +
> +    /// Remove the next node, returning it if it exists.
> +    pub fn remove_next(&mut self) -> Option<RBTreeNode<K, V>> {
> +        self.remove_neighbor(Direction::Next)
> +    }
> +
[...]