Module: Mesa Branch: master Commit: f18aad6dc0ac8408bc73f3fbf31b976114a5e1bc URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=f18aad6dc0ac8408bc73f3fbf31b976114a5e1bc
Author: Jason Ekstrand <[email protected]> Date: Wed Sep 25 10:01:27 2019 -0500 util/rb_tree: Also test _safe iterators Acked-by: Michel Dänzer <[email protected]> Tested-by: Michel Dänzer <[email protected]> Reviewed-by: Lionel Landwerlin <[email protected]> --- src/util/rb_tree_test.c | 42 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+) diff --git a/src/util/rb_tree_test.c b/src/util/rb_tree_test.c index 20a236d2eec..7551add95c1 100644 --- a/src/util/rb_tree_test.c +++ b/src/util/rb_tree_test.c @@ -93,6 +93,27 @@ validate_tree_order(struct rb_tree *tree, unsigned expected_count) assert(count == expected_count); prev = NULL; + max_val = -1; + count = 0; + rb_tree_foreach_safe(struct rb_test_node, n, tree, node) { + /* Everything should be in increasing order */ + assert(n->key >= max_val); + if (n->key > max_val) { + max_val = n->key; + } else { + /* Things should be stable, i.e., given equal keys, they should + * show up in the list in order of insertion. We insert them + * in the order they are in in the array. + */ + assert(prev == NULL || prev < n); + } + + prev = n; + count++; + } + assert(count == expected_count); + + prev = NULL; int min_val = INT_MAX; count = 0; rb_tree_foreach_rev(struct rb_test_node, n, tree, node) { @@ -112,6 +133,27 @@ validate_tree_order(struct rb_tree *tree, unsigned expected_count) count++; } assert(count == expected_count); + + prev = NULL; + min_val = INT_MAX; + count = 0; + rb_tree_foreach_rev_safe(struct rb_test_node, n, tree, node) { + /* Everything should be in increasing order */ + assert(n->key <= min_val); + if (n->key < min_val) { + min_val = n->key; + } else { + /* Things should be stable, i.e., given equal keys, they should + * show up in the list in order of insertion. We insert them + * in the order they are in in the array. + */ + assert(prev == NULL || prev > n); + } + + prev = n; + count++; + } + assert(count == expected_count); } static void _______________________________________________ mesa-commit mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/mesa-commit
