1 /*
2 * Copyright © 2021 Google, Inc.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21 * IN THE SOFTWARE.
22 */
23
24 #include <gtest/gtest.h>
25 #include "util/dag.h"
26
27 class dag_test : public ::testing::Test {
28 protected:
29 dag_test();
30 ~dag_test();
31
32 void *mem_ctx;
33 struct util_dynarray expect, actual;
34 struct dag *dag;
35 };
36
dag_test()37 dag_test::dag_test()
38 {
39 mem_ctx = ralloc_context(NULL);
40 util_dynarray_init(&expect, mem_ctx);
41 util_dynarray_init(&actual, mem_ctx);
42 dag = dag_create(mem_ctx);
43 }
44
~dag_test()45 dag_test::~dag_test()
46 {
47 ralloc_free(mem_ctx);
48 }
49
50 struct node: public dag_node {
51 int val;
52
53 /* Overload >> to make describing our test case graphs easier to read */
operator >>node54 struct node &operator>>(struct node &child) {
55 dag_add_edge(static_cast<struct dag_node *>(this),
56 static_cast<struct dag_node *>(&child), NULL);
57 return child;
58 }
59 };
60
output_cb(struct dag_node * dag_node,void * data)61 static void output_cb(struct dag_node *dag_node, void *data)
62 {
63 struct node *node = static_cast<struct node *>(dag_node);
64 struct util_dynarray *output = (struct util_dynarray *)data;
65 util_dynarray_append(output, int, node->val);
66 }
67
68 static void
init_nodes(struct dag * dag,struct node * nodes,unsigned num_nodes)69 init_nodes(struct dag *dag, struct node *nodes, unsigned num_nodes)
70 {
71 for (unsigned i = 0; i < num_nodes; i++) {
72 dag_init_node(dag, static_cast<struct dag_node *>(&nodes[i]));
73 nodes[i].val = i;
74 }
75 }
76
77 #define INIT_NODES(num_nodes) \
78 typedef struct { int order[num_nodes]; } result_type; \
79 struct node node[(num_nodes)]; \
80 init_nodes(dag, node, (num_nodes))
81
82 #define SET_EXPECTED(...) do { \
83 result_type res = {{ __VA_ARGS__ }}; \
84 util_dynarray_append(&expect, result_type, res); \
85 } while (0)
86
87 static bool
int_dynarrays_equal(struct util_dynarray * a,struct util_dynarray * b)88 int_dynarrays_equal(struct util_dynarray *a, struct util_dynarray *b)
89 {
90 if (util_dynarray_num_elements(a, int) != util_dynarray_num_elements(b, int))
91 return false;
92
93 for (unsigned i = 0; i < util_dynarray_num_elements(a, int); i++) {
94 if (*util_dynarray_element(a, int, i) !=
95 *util_dynarray_element(b, int, i)) {
96 return false;
97 }
98 }
99 return true;
100 }
101
102 static testing::AssertionResult
int_dynarrays_equal_pred(const char * a_expr,const char * b_expr,struct util_dynarray * a,struct util_dynarray * b)103 int_dynarrays_equal_pred(const char *a_expr,
104 const char *b_expr,
105 struct util_dynarray *a,
106 struct util_dynarray *b)
107 {
108 if (int_dynarrays_equal(a, b)) return testing::AssertionSuccess();
109
110 testing::AssertionResult result = testing::AssertionFailure();
111
112 result << a_expr << " != " << b_expr;
113
114 result << ", (";
115 for (unsigned i = 0; i < util_dynarray_num_elements(a, int); i++) {
116 if (i != 0)
117 result << ", ";
118 result << *util_dynarray_element(a, int, i);
119 }
120
121 result << ") != (";
122 for (unsigned i = 0; i < util_dynarray_num_elements(b, int); i++) {
123 if (i != 0)
124 result << ", ";
125 result << *util_dynarray_element(b, int, i);
126 }
127
128 result << ")";
129
130 return result;
131 }
132
133 #define TEST_CHECK() EXPECT_PRED_FORMAT2(int_dynarrays_equal_pred, &expect, &actual)
134
TEST_F(dag_test,simple)135 TEST_F(dag_test, simple)
136 {
137 INIT_NODES(3);
138
139 /* 0
140 * / \
141 * 1 2
142 */
143 node[0] >> node[1];
144 node[0] >> node[2];
145
146 /* Expected traversal order: [1, 2, 0] */
147 SET_EXPECTED(1, 2, 0);
148
149 dag_traverse_bottom_up(dag, output_cb, &actual);
150
151 TEST_CHECK();
152 }
153
TEST_F(dag_test,simple_many_children)154 TEST_F(dag_test, simple_many_children)
155 {
156 INIT_NODES(6);
157
158 /* _ 0 _
159 * / /|\ \
160 * / / | \ \
161 * | | | | |
162 * 1 2 3 4 5
163 */
164 node[0] >> node[1];
165 node[0] >> node[2];
166 node[0] >> node[3];
167 node[0] >> node[4];
168 node[0] >> node[5];
169
170 /* Expected traversal order: [1, 2, 3, 4, 5, 0] */
171 SET_EXPECTED(1, 2, 3, 4, 5, 0);
172
173 dag_traverse_bottom_up(dag, output_cb, &actual);
174
175 TEST_CHECK();
176 }
177
TEST_F(dag_test,simple_many_parents)178 TEST_F(dag_test, simple_many_parents)
179 {
180 INIT_NODES(7);
181
182 /* _ 0 _
183 * / /|\ \
184 * / / | \ \
185 * | | | | |
186 * 1 2 3 4 5
187 * | | | | |
188 * \ \ | / /
189 * \ \|/ /
190 * ‾ 6 ‾
191 */
192 node[0] >> node[1] >> node[6];
193 node[0] >> node[2] >> node[6];
194 node[0] >> node[3] >> node[6];
195 node[0] >> node[4] >> node[6];
196 node[0] >> node[5] >> node[6];
197
198 /* Expected traversal order: [6, 1, 2, 3, 4, 5, 0] */
199 SET_EXPECTED(6, 1, 2, 3, 4, 5, 0);
200
201 dag_traverse_bottom_up(dag, output_cb, &actual);
202
203 TEST_CHECK();
204 }
205
TEST_F(dag_test,complex)206 TEST_F(dag_test, complex)
207 {
208 INIT_NODES(6);
209
210 /* 0
211 * / \
212 * 1 3
213 * / \ |\
214 * 2 | | \
215 * \ / / 5
216 * 4 ‾
217 */
218 node[0] >> node[1] >> node[2] >> node[4];
219 node[1] >> node[4];
220 node[0] >> node[3];
221 node[3] >> node[4];
222 node[3] >> node[5];
223
224 /* Expected traversal order: [4, 2, 1, 5, 3, 0] */
225 SET_EXPECTED(4, 2, 1, 5, 3, 0);
226
227 dag_traverse_bottom_up(dag, output_cb, &actual);
228
229 TEST_CHECK();
230 }
231