[Mesa-dev] [PATCH 08/14] util: rb_tree: add safe iterators

[Rafael Antognolli]

On Thu, Aug 02, 2018 at 10:39:20AM +0100, Lionel Landwerlin wrote:
> Signed-off-by: Lionel Landwerlin <lionel.g.landwerlin at intel.com>
> ---
>  src/util/rb_tree.h | 36 ++++++++++++++++++++++++++++++++++++
>  1 file changed, 36 insertions(+)
> 
> diff --git a/src/util/rb_tree.h b/src/util/rb_tree.h
> index c77e9255ea2..df1a4197b8a 100644
> --- a/src/util/rb_tree.h
> +++ b/src/util/rb_tree.h
> @@ -243,6 +243,24 @@ struct rb_node *rb_node_prev(struct rb_node *node);
>          &node->field != NULL; \
>          node = rb_node_data(type, rb_node_next(&node->field), field))
>  
> +/** Iterate over the nodes in the tree, allowing the current node to be freed
> + *
> + * \param   type    The type of the containing data structure
> + *
> + * \param   node    The variable name for current node in the iteration;
> + *                  this will be declared as a pointer to \p type
> + *
> + * \param   T       The red-black tree
> + *
> + * \param   field   The rb_node field in containing data structure
> + */
> +#define rb_tree_foreach_safe(type, node, T, field) \
> +   for (type *node = rb_node_data(type, rb_tree_first(T), field), \
> +           *_next = (&node->field != NULL) ? rb_node_data(type, rb_node_next(&node->field), field) : node; \
> +        &node->field != NULL; \
> +        node = _next, \
> +           _next = (&_next->field != NULL) ? rb_node_data(type, rb_node_next(&_next->field), field) : _next)
> +

This looks nice. I'm thinking if maybe a simple helper would make things
easier to read, like:

#define _next_if_available(node, type, field) \
   (&node->field != NULL) ? rb_node_data(type, rb_node_next(&node->field), field) : node

Wouldn't help to simplify things, but up to you in the end.

>  /** Iterate over the nodes in the tree in reverse
>   *
>   * \param   type    The type of the containing data structure
> @@ -259,6 +277,24 @@ struct rb_node *rb_node_prev(struct rb_node *node);
>          &node->field != NULL; \
>          node = rb_node_data(type, rb_node_prev(&node->field), field))
>  
> +/** Iterate over the nodes in the tree in reverse, allowing the current node to be freed
> + *
> + * \param   type    The type of the containing data structure
> + *
> + * \param   node    The variable name for current node in the iteration;
> + *                  this will be declared as a pointer to \p type
> + *
> + * \param   T       The red-black tree
> + *
> + * \param   field   The rb_node field in containing data structure
> + */
> +#define rb_tree_foreach_rev_safe(type, node, T, field) \
> +   for (type *node = rb_node_data(type, rb_tree_last(T), field), \
> +           *_prev = rb_node_prev(&node->field) ? rb_node_data(type, rb_node_prev(&node->field), field) : NULL; \
> +        &node->field != NULL; \
> +        node = _prev, \
> +           _prev = (prev && rb_node_prev(&_prev->field)) ? rb_node_data(type, rb_node_prev(&_prev->field), field) : NULL)
                       ^^^^
I can't really find where this "prev" came from, but I also don't see
any warning when building it.

Also, same comment about the helper could apply here I guess, but this
"prev" is making things confusing to me.

> +
>  /** Validate a red-black tree
>   *
>   * This function walks the tree and validates that this is a valid red-
> -- 
> 2.18.0
> 
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev