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), 0);
57 return child;
58 }
59
add_edgenode60 void add_edge(struct node &child, uintptr_t data) {
61 dag_add_edge(static_cast<struct dag_node *>(this),
62 static_cast<struct dag_node *>(&child), data);
63 }
64
add_edge_max_datanode65 void add_edge_max_data(struct node &child, uintptr_t data) {
66 dag_add_edge_max_data(static_cast<struct dag_node *>(this),
67 static_cast<struct dag_node *>(&child), data);
68 }
69 };
70
output_cb(struct dag_node * dag_node,void * data)71 static void output_cb(struct dag_node *dag_node, void *data)
72 {
73 struct node *node = static_cast<struct node *>(dag_node);
74 struct util_dynarray *output = (struct util_dynarray *)data;
75 util_dynarray_append(output, int, node->val);
76 }
77
78 static void
init_nodes(struct dag * dag,struct node * nodes,unsigned num_nodes)79 init_nodes(struct dag *dag, struct node *nodes, unsigned num_nodes)
80 {
81 for (unsigned i = 0; i < num_nodes; i++) {
82 dag_init_node(dag, static_cast<struct dag_node *>(&nodes[i]));
83 nodes[i].val = i;
84 }
85 }
86
87 #define INIT_NODES(num_nodes) \
88 typedef struct { int order[num_nodes]; } result_type; \
89 struct node node[(num_nodes)]; \
90 init_nodes(dag, node, (num_nodes))
91
92 #define SET_EXPECTED(...) do { \
93 result_type res = {{ __VA_ARGS__ }}; \
94 util_dynarray_append(&expect, result_type, res); \
95 } while (0)
96
97 static bool
int_dynarrays_equal(struct util_dynarray * a,struct util_dynarray * b)98 int_dynarrays_equal(struct util_dynarray *a, struct util_dynarray *b)
99 {
100 if (util_dynarray_num_elements(a, int) != util_dynarray_num_elements(b, int))
101 return false;
102
103 for (unsigned i = 0; i < util_dynarray_num_elements(a, int); i++) {
104 if (*util_dynarray_element(a, int, i) !=
105 *util_dynarray_element(b, int, i)) {
106 return false;
107 }
108 }
109 return true;
110 }
111
112 static testing::AssertionResult
int_dynarrays_equal_pred(const char * a_expr,const char * b_expr,struct util_dynarray * a,struct util_dynarray * b)113 int_dynarrays_equal_pred(const char *a_expr,
114 const char *b_expr,
115 struct util_dynarray *a,
116 struct util_dynarray *b)
117 {
118 if (int_dynarrays_equal(a, b)) return testing::AssertionSuccess();
119
120 testing::AssertionResult result = testing::AssertionFailure();
121
122 result << a_expr << " != " << b_expr;
123
124 result << ", (";
125 for (unsigned i = 0; i < util_dynarray_num_elements(a, int); i++) {
126 if (i != 0)
127 result << ", ";
128 result << *util_dynarray_element(a, int, i);
129 }
130
131 result << ") != (";
132 for (unsigned i = 0; i < util_dynarray_num_elements(b, int); i++) {
133 if (i != 0)
134 result << ", ";
135 result << *util_dynarray_element(b, int, i);
136 }
137
138 result << ")";
139
140 return result;
141 }
142
143 #define TEST_CHECK() EXPECT_PRED_FORMAT2(int_dynarrays_equal_pred, &expect, &actual)
144
TEST_F(dag_test,simple)145 TEST_F(dag_test, simple)
146 {
147 INIT_NODES(3);
148
149 /* 0
150 * / \
151 * 1 2
152 */
153 node[0] >> node[1];
154 node[0] >> node[2];
155
156 /* Expected traversal order: [1, 2, 0] */
157 SET_EXPECTED(1, 2, 0);
158
159 dag_traverse_bottom_up(dag, output_cb, &actual);
160
161 TEST_CHECK();
162 }
163
TEST_F(dag_test,duplicate_edge)164 TEST_F(dag_test, duplicate_edge)
165 {
166 INIT_NODES(3);
167
168 node[0].add_edge(node[1], 0);
169 node[0].add_edge(node[1], 1);
170 node[0].add_edge(node[2], 0);
171
172 EXPECT_EQ(util_dynarray_num_elements(&node[0].edges, struct dag_edge), 3);
173
174 SET_EXPECTED(1, 2, 0);
175
176 dag_traverse_bottom_up(dag, output_cb, &actual);
177
178 TEST_CHECK();
179 }
180
TEST_F(dag_test,duplicate_edge_max_data)181 TEST_F(dag_test, duplicate_edge_max_data)
182 {
183 INIT_NODES(3);
184
185 node[0].add_edge_max_data(node[1], 0);
186 node[0].add_edge_max_data(node[1], 1);
187 node[0].add_edge_max_data(node[2], 0);
188
189 EXPECT_EQ(util_dynarray_num_elements(&node[0].edges, struct dag_edge), 2);
190
191 util_dynarray_foreach (&node[0].edges, struct dag_edge, edge) {
192 if (edge->child == &node[1]) {
193 EXPECT_EQ(edge->data, 1);
194 } else {
195 EXPECT_EQ(edge->child, &node[2]);
196 EXPECT_EQ(edge->data, 0);
197 }
198 }
199
200 SET_EXPECTED(1, 2, 0);
201
202 dag_traverse_bottom_up(dag, output_cb, &actual);
203
204 TEST_CHECK();
205 }
206
TEST_F(dag_test,simple_many_children)207 TEST_F(dag_test, simple_many_children)
208 {
209 INIT_NODES(6);
210
211 /* _ 0 _
212 * / /|\ \
213 * / / | \ \
214 * | | | | |
215 * 1 2 3 4 5
216 */
217 node[0] >> node[1];
218 node[0] >> node[2];
219 node[0] >> node[3];
220 node[0] >> node[4];
221 node[0] >> node[5];
222
223 /* Expected traversal order: [1, 2, 3, 4, 5, 0] */
224 SET_EXPECTED(1, 2, 3, 4, 5, 0);
225
226 dag_traverse_bottom_up(dag, output_cb, &actual);
227
228 TEST_CHECK();
229 }
230
TEST_F(dag_test,simple_many_parents)231 TEST_F(dag_test, simple_many_parents)
232 {
233 INIT_NODES(7);
234
235 /* _ 0 _
236 * / /|\ \
237 * / / | \ \
238 * | | | | |
239 * 1 2 3 4 5
240 * | | | | |
241 * \ \ | / /
242 * \ \|/ /
243 * ‾ 6 ‾
244 */
245 node[0] >> node[1] >> node[6];
246 node[0] >> node[2] >> node[6];
247 node[0] >> node[3] >> node[6];
248 node[0] >> node[4] >> node[6];
249 node[0] >> node[5] >> node[6];
250
251 /* Expected traversal order: [6, 1, 2, 3, 4, 5, 0] */
252 SET_EXPECTED(6, 1, 2, 3, 4, 5, 0);
253
254 dag_traverse_bottom_up(dag, output_cb, &actual);
255
256 TEST_CHECK();
257 }
258
TEST_F(dag_test,complex)259 TEST_F(dag_test, complex)
260 {
261 INIT_NODES(6);
262
263 /* 0
264 * / \
265 * 1 3
266 * / \ |\
267 * 2 | | \
268 * \ / / 5
269 * 4 ‾
270 */
271 node[0] >> node[1] >> node[2] >> node[4];
272 node[1] >> node[4];
273 node[0] >> node[3];
274 node[3] >> node[4];
275 node[3] >> node[5];
276
277 /* Expected traversal order: [4, 2, 1, 5, 3, 0] */
278 SET_EXPECTED(4, 2, 1, 5, 3, 0);
279
280 dag_traverse_bottom_up(dag, output_cb, &actual);
281
282 TEST_CHECK();
283 }
284