[Mesa-dev] [PATCH v2 02/11] util: rb_tree: add safe iterators

[Rafael Antognolli]

On Tue, Aug 07, 2018 at 06:35:13PM +0100, Lionel Landwerlin wrote:
> v2: Add helper to make iterators more readable (Rafael)
>     Fix rev iterator bug (Rafael)
> 
> Signed-off-by: Lionel Landwerlin <lionel.g.landwerlin at intel.com>

Reviewed-by: Rafael Antognolli <rafael.antognolli at intel.com>

> ---
>  src/util/rb_tree.h | 58 ++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 58 insertions(+)
> 
> diff --git a/src/util/rb_tree.h b/src/util/rb_tree.h
> index c77e9255ea2..1e8aeb4a7b2 100644
> --- a/src/util/rb_tree.h
> +++ b/src/util/rb_tree.h
> @@ -227,6 +227,30 @@ struct rb_node *rb_node_next(struct rb_node *node);
>  /** Get the next previous (to the left) in the tree or NULL */
>  struct rb_node *rb_node_prev(struct rb_node *node);
>  
> +/** Get the next node if available or the same node again.
> + *
> + * \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   field   The rb_node field in containing data structure
> + */
> +#define rb_tree_node_next_if_available(type, node, field) \
> +   (&node->field != NULL) ? rb_node_data(type, rb_node_next(&node->field), field) : node
> +
> +/** Get the previous node if available or the same node again.
> + *
> + * \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   field   The rb_node field in containing data structure
> + */
> +#define rb_tree_node_prev_if_available(type, node, field) \
> +   (&node->field != NULL) ? rb_node_data(type, rb_node_prev(&node->field), field) : node
> +
>  /** Iterate over the nodes in the tree
>   *
>   * \param   type    The type of the containing data structure
> @@ -243,6 +267,23 @@ 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 = rb_tree_node_next_if_available(type, node, field); \
> +        &node->field != NULL; \
> +        node = __next, __next = rb_tree_node_next_if_available(type, node, field))
> +
>  /** Iterate over the nodes in the tree in reverse
>   *
>   * \param   type    The type of the containing data structure
> @@ -259,6 +300,23 @@ 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_tree_node_prev_if_available(type, node, field);  \
> +        &node->field != NULL; \
> +        node = __prev, __prev = rb_tree_node_prev_if_available(type, node, field))
> +
>  /** 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