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

[Lionel Landwerlin]

On 04/08/18 01:31, Rafael Antognolli wrote:
> 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.

Yeah sounds nice, thanks!

>
>>   /** 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.

Oops, indeed it's a bug. Didn't notice because I didn't use that macro...

>
>> +
>>   /** 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
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev