From f18aad6dc0ac8408bc73f3fbf31b976114a5e1bc Mon Sep 17 00:00:00 2001 From: Jason Ekstrand Date: Wed, 25 Sep 2019 10:01:27 -0500 Subject: [PATCH] util/rb_tree: Also test _safe iterators MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Acked-by: Michel Dänzer Tested-by: Michel Dänzer Reviewed-by: Lionel Landwerlin --- 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 @@ -92,6 +92,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; @@ -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 -- 2.30.2