Mesa (master): util/rb_tree: Also test _safe iterators

[GitLab Mirror]

Module: Mesa
Branch: master
Commit: f18aad6dc0ac8408bc73f3fbf31b976114a5e1bc
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=f18aad6dc0ac8408bc73f3fbf31b976114a5e1bc

Author: Jason Ekstrand <jason at jlekstrand.net>
Date:   Wed Sep 25 10:01:27 2019 -0500

util/rb_tree: Also test _safe iterators

Acked-by: Michel Dänzer <mdaenzer at redhat.com>
Tested-by: Michel Dänzer <mdaenzer at redhat.com>
Reviewed-by: Lionel Landwerlin <lionel.g.landwerlin at intel.com>

---

 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