From 5ca4f574693800c254cfe834ddf2ce28c15d1746 Mon Sep 17 00:00:00 2001 From: Jason Ekstrand Date: Wed, 25 Sep 2019 10:02:15 -0500 Subject: [PATCH] util/rb_tree: Stop relying on &iter->field != NULL MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit The old version of the iterators relies on a &iter->field != NULL check which works fine on older GCC but newer GCC versions and clang have optimizations that break if you do pointer math on a null pointer. The correct solution to this is to do the null comparisons before we do any sort of &iter->field or use rb_node_data to do the reverse operation. Acked-by: Michel Dänzer Tested-by: Michel Dänzer Reviewed-by: Lionel Landwerlin --- src/util/rb_tree.h | 69 +++++++++++++++++++--------------------------- 1 file changed, 28 insertions(+), 41 deletions(-) diff --git a/src/util/rb_tree.h b/src/util/rb_tree.h index efdfb0411f1..8b354c091f5 100644 --- a/src/util/rb_tree.h +++ b/src/util/rb_tree.h @@ -227,29 +227,8 @@ 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 +#define rb_node_next_or_null(n) ((n) == NULL ? NULL : rb_node_next(n)) +#define rb_node_prev_or_null(n) ((n) == NULL ? NULL : rb_node_prev(n)) /** Iterate over the nodes in the tree * @@ -262,10 +241,11 @@ struct rb_node *rb_node_prev(struct rb_node *node); * * \param field The rb_node field in containing data structure */ -#define rb_tree_foreach(type, node, T, field) \ - for (type *node = rb_node_data(type, rb_tree_first(T), field); \ - &node->field != NULL; \ - node = rb_node_data(type, rb_node_next(&node->field), field)) +#define rb_tree_foreach(type, iter, T, field) \ + for (type *iter, *__node = (type *)rb_tree_first(T); \ + __node != NULL && \ + (iter = rb_node_data(type, (struct rb_node *)__node, field), true); \ + __node = (type *)rb_node_next((struct rb_node *)__node)) /** Iterate over the nodes in the tree, allowing the current node to be freed * @@ -278,11 +258,14 @@ struct rb_node *rb_node_prev(struct rb_node *node); * * \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)) +#define rb_tree_foreach_safe(type, iter, T, field) \ + for (type *iter, \ + *__node = (type *)rb_tree_first(T), \ + *__next = (type *)rb_node_next_or_null((struct rb_node *)__node); \ + __node != NULL && \ + (iter = rb_node_data(type, (struct rb_node *)__node, field), true); \ + __node = __next, \ + __next = (type *)rb_node_next_or_null((struct rb_node *)__node)) /** Iterate over the nodes in the tree in reverse * @@ -295,10 +278,11 @@ struct rb_node *rb_node_prev(struct rb_node *node); * * \param field The rb_node field in containing data structure */ -#define rb_tree_foreach_rev(type, node, T, field) \ - for (type *node = rb_node_data(type, rb_tree_last(T), field); \ - &node->field != NULL; \ - node = rb_node_data(type, rb_node_prev(&node->field), field)) +#define rb_tree_foreach_rev(type, iter, T, field) \ + for (type *iter, *__node = (type *)rb_tree_last(T); \ + __node != NULL && \ + (iter = rb_node_data(type, (struct rb_node *)__node, field), true); \ + __node = (type *)rb_node_prev((struct rb_node *)__node)) /** Iterate over the nodes in the tree in reverse, allowing the current node to be freed * @@ -311,11 +295,14 @@ struct rb_node *rb_node_prev(struct rb_node *node); * * \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)) +#define rb_tree_foreach_rev_safe(type, iter, T, field) \ + for (type *iter, \ + *__node = (type *)rb_tree_last(T), \ + *__prev = (type *)rb_node_prev_or_null((struct rb_node *)__node); \ + __node != NULL && \ + (iter = rb_node_data(type, (struct rb_node *)__node, field), true); \ + __node = __prev, \ + __prev = (type *)rb_node_prev_or_null((struct rb_node *)__node)) /** Validate a red-black tree * -- 2.30.2