Mesa (master): util: rb_tree: add safe iterators
GitLab Mirror
gitlab-mirror at kemper.freedesktop.org
Wed Aug 22 17:06:09 UTC 2018
Module: Mesa
Branch: master
Commit: 14a1cb37ebd3adbceb56f99f4727e45309b75ec2
URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=14a1cb37ebd3adbceb56f99f4727e45309b75ec2
Author: Lionel Landwerlin <lionel.g.landwerlin at intel.com>
Date: Sun Jul 29 14:13:25 2018 +0100
util: rb_tree: add safe iterators
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 c77e9255ea..1e8aeb4a7b 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-
More information about the mesa-commit
mailing list