Mesa (main): util: Add unit tests for dag
GitLab Mirror
gitlab-mirror at kemper.freedesktop.org
Tue Aug 17 18:32:17 UTC 2021
Module: Mesa
Branch: main
Commit: 9261a020280ea597d1862288bf81771672c10f75
URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=9261a020280ea597d1862288bf81771672c10f75
Author: Matt Turner <mattst88 at gmail.com>
Date: Tue Aug 10 12:10:22 2021 -0700
util: Add unit tests for dag
Reviewed-by: Emma Anholt <emma at anholt.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/12232>
---
src/util/meson.build | 11 +++
src/util/tests/dag_test.cpp | 230 ++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 241 insertions(+)
diff --git a/src/util/meson.build b/src/util/meson.build
index 319b22d9bf7..88f06e23268 100644
--- a/src/util/meson.build
+++ b/src/util/meson.build
@@ -392,6 +392,17 @@ if with_tests
suite : ['util'],
)
+ test(
+ 'dag',
+ executable(
+ 'dag_test',
+ 'tests/dag_test.cpp',
+ dependencies : [idep_mesautil, idep_gtest],
+ include_directories : [inc_include, inc_src],
+ ),
+ suite : ['util'],
+ )
+
subdir('tests/cache')
subdir('tests/fast_idiv_by_const')
subdir('tests/fast_urem_by_const')
diff --git a/src/util/tests/dag_test.cpp b/src/util/tests/dag_test.cpp
new file mode 100644
index 00000000000..f807962f793
--- /dev/null
+++ b/src/util/tests/dag_test.cpp
@@ -0,0 +1,230 @@
+/*
+ * Copyright © 2021 Google, Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ */
+
+#include <gtest/gtest.h>
+#include "util/dag.h"
+
+class dag_test : public ::testing::Test {
+protected:
+ dag_test();
+ ~dag_test();
+
+ void *mem_ctx;
+ struct util_dynarray expect, actual;
+ struct dag *dag;
+};
+
+dag_test::dag_test()
+{
+ mem_ctx = ralloc_context(NULL);
+ util_dynarray_init(&expect, mem_ctx);
+ util_dynarray_init(&actual, mem_ctx);
+ dag = dag_create(mem_ctx);
+}
+
+dag_test::~dag_test()
+{
+ ralloc_free(mem_ctx);
+}
+
+struct node: public dag_node {
+ int val;
+
+ /* Overload >> to make describing our test case graphs easier to read */
+ struct node &operator>>(struct node &child) {
+ dag_add_edge(static_cast<struct dag_node *>(this),
+ static_cast<struct dag_node *>(&child), NULL);
+ return child;
+ }
+};
+
+static void output_cb(struct dag_node *dag_node, void *data)
+{
+ struct node *node = static_cast<struct node *>(dag_node);
+ struct util_dynarray *output = (struct util_dynarray *)data;
+ util_dynarray_append(output, int, node->val);
+}
+
+static void
+init_nodes(struct dag *dag, struct node *nodes, unsigned num_nodes)
+{
+ for (unsigned i = 0; i < num_nodes; i++) {
+ dag_init_node(dag, static_cast<struct dag_node *>(&nodes[i]));
+ nodes[i].val = i;
+ }
+}
+
+#define INIT_NODES(num_nodes) \
+ typedef struct { int order[num_nodes]; } result_type; \
+ struct node node[(num_nodes)]; \
+ init_nodes(dag, node, (num_nodes))
+
+#define SET_EXPECTED(...) do { \
+ result_type res = {{ __VA_ARGS__ }}; \
+ util_dynarray_append(&expect, result_type, res); \
+} while (0)
+
+static bool
+int_dynarrays_equal(struct util_dynarray *a, struct util_dynarray *b)
+{
+ if (util_dynarray_num_elements(a, int) != util_dynarray_num_elements(b, int))
+ return false;
+
+ for (unsigned i = 0; i < util_dynarray_num_elements(a, int); i++) {
+ if (*util_dynarray_element(a, int, i) !=
+ *util_dynarray_element(b, int, i)) {
+ return false;
+ }
+ }
+ return true;
+}
+
+static testing::AssertionResult
+int_dynarrays_equal_pred(const char *a_expr,
+ const char *b_expr,
+ struct util_dynarray *a,
+ struct util_dynarray *b)
+{
+ if (int_dynarrays_equal(a, b)) return testing::AssertionSuccess();
+
+ testing::AssertionResult result = testing::AssertionFailure();
+
+ result << a_expr << " != " << b_expr;
+
+ result << ", (";
+ for (unsigned i = 0; i < util_dynarray_num_elements(a, int); i++) {
+ if (i != 0)
+ result << ", ";
+ result << *util_dynarray_element(a, int, i);
+ }
+
+ result << ") != (";
+ for (unsigned i = 0; i < util_dynarray_num_elements(b, int); i++) {
+ if (i != 0)
+ result << ", ";
+ result << *util_dynarray_element(b, int, i);
+ }
+
+ result << ")";
+
+ return result;
+}
+
+#define TEST_CHECK() EXPECT_PRED_FORMAT2(int_dynarrays_equal_pred, &expect, &actual)
+
+TEST_F(dag_test, simple)
+{
+ INIT_NODES(3);
+
+ /* 0
+ * / \
+ * 1 2
+ */
+ node[0] >> node[1];
+ node[0] >> node[2];
+
+ /* Expected traversal order: [1, 2, 0] */
+ SET_EXPECTED(1, 2, 0);
+
+ dag_traverse_bottom_up(dag, output_cb, &actual);
+
+ TEST_CHECK();
+}
+
+TEST_F(dag_test, simple_many_children)
+{
+ INIT_NODES(6);
+
+ /* _ 0 _
+ * / /|\ \
+ * / / | \ \
+ * | | | | |
+ * 1 2 3 4 5
+ */
+ node[0] >> node[1];
+ node[0] >> node[2];
+ node[0] >> node[3];
+ node[0] >> node[4];
+ node[0] >> node[5];
+
+ /* Expected traversal order: [1, 2, 3, 4, 5, 0] */
+ SET_EXPECTED(1, 2, 3, 4, 5, 0);
+
+ dag_traverse_bottom_up(dag, output_cb, &actual);
+
+ TEST_CHECK();
+}
+
+TEST_F(dag_test, simple_many_parents)
+{
+ INIT_NODES(7);
+
+ /* _ 0 _
+ * / /|\ \
+ * / / | \ \
+ * | | | | |
+ * 1 2 3 4 5
+ * | | | | |
+ * \ \ | / /
+ * \ \|/ /
+ * ‾ 6 ‾
+ */
+ node[0] >> node[1] >> node[6];
+ node[0] >> node[2] >> node[6];
+ node[0] >> node[3] >> node[6];
+ node[0] >> node[4] >> node[6];
+ node[0] >> node[5] >> node[6];
+
+ /* Expected traversal order: [6, 1, 2, 3, 4, 5, 0] */
+ SET_EXPECTED(6, 1, 2, 3, 4, 5, 0);
+
+ dag_traverse_bottom_up(dag, output_cb, &actual);
+
+ TEST_CHECK();
+}
+
+TEST_F(dag_test, complex)
+{
+ INIT_NODES(6);
+
+ /* 0
+ * / \
+ * 1 3
+ * / \ |\
+ * 2 | | \
+ * \ / / 5
+ * 4 ‾
+ */
+ node[0] >> node[1] >> node[2] >> node[4];
+ node[1] >> node[4];
+ node[0] >> node[3];
+ node[3] >> node[4];
+ node[3] >> node[5];
+
+ /* Expected traversal order: [4, 2, 1, 5, 3, 0] */
+ SET_EXPECTED(4, 2, 1, 5, 3, 0);
+
+ dag_traverse_bottom_up(dag, output_cb, &actual);
+
+ TEST_CHECK();
+}
More information about the mesa-commit
mailing list