1 //===- GraphTest.cpp ------------------------------------------------------===//
2 //
3 // The MCLinker Project
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 #include "GraphTest.h"
10 #include <mcld/ADT/GraphLite/Digraph.h>
11 #include <mcld/ADT/GraphLite/ListDigraph.h>
12
13 using namespace mcld;
14 using namespace mcld::test;
15 using namespace mcld::graph;
16
17 // Constructor can do set-up work for all test here.
GraphTest()18 GraphTest::GraphTest()
19 {
20 }
21
22 // Destructor can do clean-up work that doesn't throw exceptions here.
~GraphTest()23 GraphTest::~GraphTest()
24 {
25 }
26
27 // SetUp() will be called immediately before each test.
SetUp()28 void GraphTest::SetUp()
29 {
30 }
31
32 // TearDown() will be called immediately after each test.
TearDown()33 void GraphTest::TearDown()
34 {
35 }
36
37 //===----------------------------------------------------------------------===//
38 // Testcases
39 //===----------------------------------------------------------------------===//
TEST_F(GraphTest,list_digraph_add_n_erase_nodes_1)40 TEST_F(GraphTest, list_digraph_add_n_erase_nodes_1)
41 {
42 ListDigraph graph;
43
44 ListDigraph::Node* u1 = graph.addNode();
45 ListDigraph::Node* u2 = graph.addNode();
46 ListDigraph::Node* u3 = graph.addNode();
47
48 ASSERT_TRUE(NULL == u1->first_in);
49 ASSERT_TRUE(NULL == u1->first_out);
50 ASSERT_TRUE(u2 == u1->prev);
51 ASSERT_TRUE(NULL == u1->next);
52
53 ASSERT_TRUE(NULL == u2->first_in);
54 ASSERT_TRUE(NULL == u2->first_out);
55 ASSERT_TRUE(u3 == u2->prev);
56 ASSERT_TRUE(u1 == u2->next);
57
58 ASSERT_TRUE(NULL == u3->first_in);
59 ASSERT_TRUE(NULL == u3->first_out);
60 ASSERT_TRUE(u2 == u3->next);
61 ASSERT_TRUE(NULL == u3->prev);
62
63 ListDigraph::Node* head = NULL;
64 graph.getHead(head);
65 ASSERT_TRUE(head == u3);
66
67 graph.erase(*u2);
68
69 ASSERT_TRUE(NULL == u1->first_in);
70 ASSERT_TRUE(NULL == u1->first_out);
71 ASSERT_TRUE(u3 == u1->prev);
72 ASSERT_TRUE(NULL == u1->next);
73
74 ASSERT_TRUE(NULL == u3->first_in);
75 ASSERT_TRUE(NULL == u3->first_out);
76 ASSERT_TRUE(u1 == u3->next);
77 ASSERT_TRUE(NULL == u3->prev);
78
79 ASSERT_TRUE(NULL == u2->first_in);
80 ASSERT_TRUE(NULL == u2->first_out);
81 ASSERT_TRUE(NULL == u2->prev);
82 ASSERT_TRUE(NULL == u2->next);
83
84 graph.getHead(head);
85 ASSERT_TRUE(head == u3);
86 }
87
TEST_F(GraphTest,list_digraph_add_n_erase_nodes_2)88 TEST_F(GraphTest, list_digraph_add_n_erase_nodes_2)
89 {
90 ListDigraph graph;
91
92 ListDigraph::Node* u1 = graph.addNode();
93 ListDigraph::Node* u2 = graph.addNode();
94 ListDigraph::Node* u3 = graph.addNode();
95
96 ASSERT_TRUE(NULL == u1->first_in);
97 ASSERT_TRUE(NULL == u1->first_out);
98 ASSERT_TRUE(u2 == u1->prev);
99 ASSERT_TRUE(NULL == u1->next);
100
101 ASSERT_TRUE(NULL == u2->first_in);
102 ASSERT_TRUE(NULL == u2->first_out);
103 ASSERT_TRUE(u3 == u2->prev);
104 ASSERT_TRUE(u1 == u2->next);
105
106 ASSERT_TRUE(NULL == u3->first_in);
107 ASSERT_TRUE(NULL == u3->first_out);
108 ASSERT_TRUE(u2 == u3->next);
109 ASSERT_TRUE(NULL == u3->prev);
110
111 ListDigraph::Node* head = NULL;
112 graph.getHead(head);
113 ASSERT_TRUE(head == u3);
114
115 graph.erase(*u1);
116
117 ASSERT_TRUE(NULL == u1->first_in);
118 ASSERT_TRUE(NULL == u1->first_out);
119 ASSERT_TRUE(NULL == u1->prev);
120 ASSERT_TRUE(NULL == u1->next);
121
122 ASSERT_TRUE(NULL == u2->first_in);
123 ASSERT_TRUE(NULL == u2->first_out);
124 ASSERT_TRUE(u3 == u2->prev);
125 ASSERT_TRUE(NULL == u2->next);
126
127 ASSERT_TRUE(NULL == u3->first_in);
128 ASSERT_TRUE(NULL == u3->first_out);
129 ASSERT_TRUE(u2 == u3->next);
130 ASSERT_TRUE(NULL == u3->prev);
131
132 graph.getHead(head);
133 ASSERT_TRUE(head == u3);
134 }
135
TEST_F(GraphTest,list_digraph_add_n_erase_nodes_3)136 TEST_F(GraphTest, list_digraph_add_n_erase_nodes_3)
137 {
138 ListDigraph graph;
139
140 ListDigraph::Node* u1 = graph.addNode();
141 ListDigraph::Node* u2 = graph.addNode();
142 ListDigraph::Node* u3 = graph.addNode();
143
144 ASSERT_TRUE(NULL == u1->first_in);
145 ASSERT_TRUE(NULL == u1->first_out);
146 ASSERT_TRUE(u2 == u1->prev);
147 ASSERT_TRUE(NULL == u1->next);
148
149 ASSERT_TRUE(NULL == u2->first_in);
150 ASSERT_TRUE(NULL == u2->first_out);
151 ASSERT_TRUE(u3 == u2->prev);
152 ASSERT_TRUE(u1 == u2->next);
153
154 ASSERT_TRUE(NULL == u3->first_in);
155 ASSERT_TRUE(NULL == u3->first_out);
156 ASSERT_TRUE(u2 == u3->next);
157 ASSERT_TRUE(NULL == u3->prev);
158
159 ListDigraph::Node* head = NULL;
160 graph.getHead(head);
161 ASSERT_TRUE(head == u3);
162
163 graph.erase(*u3);
164
165 ASSERT_TRUE(NULL == u3->first_in);
166 ASSERT_TRUE(NULL == u3->first_out);
167 ASSERT_TRUE(NULL == u3->prev);
168 ASSERT_TRUE(NULL == u3->next);
169
170 ASSERT_TRUE(NULL == u1->first_in);
171 ASSERT_TRUE(NULL == u1->first_out);
172 ASSERT_TRUE(u2 == u1->prev);
173 ASSERT_TRUE(NULL == u1->next);
174
175 ASSERT_TRUE(NULL == u2->first_in);
176 ASSERT_TRUE(NULL == u2->first_out);
177 ASSERT_TRUE(u1 == u2->next);
178 ASSERT_TRUE(NULL == u2->prev);
179
180 graph.getHead(head);
181 ASSERT_TRUE(head == u2);
182
183 }
184
TEST_F(GraphTest,list_digraph_add_arcs_1)185 TEST_F(GraphTest, list_digraph_add_arcs_1)
186 {
187 ListDigraph graph;
188
189 ListDigraph::Node* u1 = graph.addNode();
190 ListDigraph::Node* u2 = graph.addNode();
191 ListDigraph::Node* u3 = graph.addNode();
192
193 ListDigraph::Arc* a1 = graph.addArc(*u1, *u2);
194 ListDigraph::Arc* a2 = graph.addArc(*u2, *u3);
195 ListDigraph::Arc* a3 = graph.addArc(*u3, *u1);
196
197 ASSERT_TRUE(u1 == a1->source && u2 == a1->target);
198 ASSERT_TRUE(u2 == a2->source && u3 == a2->target);
199 ASSERT_TRUE(u3 == a3->source && u1 == a3->target);
200
201 ASSERT_TRUE(u1->first_in == a3 && u1->first_out == a1);
202 ASSERT_TRUE(u2->first_in == a1 && u2->first_out == a2);
203 ASSERT_TRUE(u3->first_in == a2 && u3->first_out == a3);
204 }
205
TEST_F(GraphTest,list_digraph_add_arcs_2)206 TEST_F(GraphTest, list_digraph_add_arcs_2)
207 {
208 ListDigraph graph;
209
210 ListDigraph::Node* u1 = graph.addNode();
211 ListDigraph::Node* u2 = graph.addNode();
212 ListDigraph::Node* u3 = graph.addNode();
213
214 ListDigraph::Arc* a1 = graph.addArc(*u1, *u1);
215 ListDigraph::Arc* a2 = graph.addArc(*u1, *u2);
216 ListDigraph::Arc* a3 = graph.addArc(*u1, *u3);
217
218 ASSERT_TRUE(u1 == a1->source && u1 == a1->target);
219 ASSERT_TRUE(u1 == a2->source && u2 == a2->target);
220 ASSERT_TRUE(u1 == a3->source && u3 == a3->target);
221
222 ASSERT_TRUE(u1->first_in == a1 && u1->first_out == a3);
223 ASSERT_TRUE(u2->first_in == a2 && u2->first_out == NULL);
224 ASSERT_TRUE(u3->first_in == a3 && u3->first_out == NULL);
225 }
226
TEST_F(GraphTest,list_digraph_add_n_erase_arcs_1)227 TEST_F(GraphTest, list_digraph_add_n_erase_arcs_1)
228 {
229 ListDigraph graph;
230
231 ListDigraph::Node* u1 = graph.addNode();
232 ListDigraph::Node* u2 = graph.addNode();
233 ListDigraph::Node* u3 = graph.addNode();
234
235 ListDigraph::Arc* a1 = graph.addArc(*u1, *u2);
236 ListDigraph::Arc* a2 = graph.addArc(*u2, *u3);
237 ListDigraph::Arc* a3 = graph.addArc(*u3, *u1);
238
239 graph.erase(*a2);
240
241 ASSERT_TRUE(u1 == a1->source && u2 == a1->target);
242 ASSERT_TRUE(u3 == a3->source && u1 == a3->target);
243
244 // remove from the fan-out list
245 ASSERT_TRUE(u2->first_in == a1 && u2->first_out == NULL);
246
247 // remove from the fan-in list
248 ASSERT_TRUE(u3->first_in == NULL && u3->first_out == a3);
249
250 // put into free list
251 ASSERT_TRUE(NULL == a2->next_in);
252 }
253
254
TEST_F(GraphTest,list_digraph_add_n_erase_arcs_2)255 TEST_F(GraphTest, list_digraph_add_n_erase_arcs_2)
256 {
257 ListDigraph graph;
258
259 ListDigraph::Node* u1 = graph.addNode();
260 ListDigraph::Node* u2 = graph.addNode();
261 ListDigraph::Node* u3 = graph.addNode();
262
263 ListDigraph::Arc* a1 = graph.addArc(*u1, *u2);
264 ListDigraph::Arc* a2 = graph.addArc(*u2, *u3);
265 ListDigraph::Arc* a3 = graph.addArc(*u3, *u1);
266
267 graph.erase(*a1);
268
269 ASSERT_TRUE(u2 == a2->source && u3 == a2->target);
270 ASSERT_TRUE(u3 == a3->source && u1 == a3->target);
271
272 // remove from the fan-out list
273 ASSERT_TRUE(u1->first_in == a3 && u1->first_out == NULL);
274
275 // remove from the fan-in list
276 ASSERT_TRUE(u2->first_in == NULL && u2->first_out == a2);
277
278 // put into free list
279 ASSERT_TRUE(NULL == a1->next_in);
280 }
281
TEST_F(GraphTest,list_digraph_add_n_erase_arcs_3)282 TEST_F(GraphTest, list_digraph_add_n_erase_arcs_3)
283 {
284 ListDigraph graph;
285
286 ListDigraph::Node* u1 = graph.addNode();
287 ListDigraph::Node* u2 = graph.addNode();
288 ListDigraph::Node* u3 = graph.addNode();
289
290 ListDigraph::Arc* a1 = graph.addArc(*u1, *u2);
291 ListDigraph::Arc* a2 = graph.addArc(*u2, *u3);
292 ListDigraph::Arc* a3 = graph.addArc(*u3, *u1);
293
294 graph.erase(*a3);
295
296 ASSERT_TRUE(u1 == a1->source && u2 == a1->target);
297 ASSERT_TRUE(u2 == a2->source && u3 == a2->target);
298
299 // remove from the fan-out list
300 ASSERT_TRUE(u1->first_in == NULL && u1->first_out == a1);
301
302 // remove from the fan-in list
303 ASSERT_TRUE(u3->first_in == a2 && u3->first_out == NULL);
304
305 // put into free list
306 ASSERT_TRUE(NULL == a3->next_in);
307 }
308
TEST_F(GraphTest,list_digraph_add_n_erase_arcs_4)309 TEST_F(GraphTest, list_digraph_add_n_erase_arcs_4)
310 {
311 ListDigraph graph;
312
313 ListDigraph::Node* u1 = graph.addNode();
314 ListDigraph::Node* u2 = graph.addNode();
315 ListDigraph::Node* u3 = graph.addNode();
316
317 ListDigraph::Arc* a1 = graph.addArc(*u1, *u1);
318 graph.addArc(*u1, *u2);
319 graph.addArc(*u1, *u3);
320
321 graph.erase(*u1);
322
323 ASSERT_TRUE(u2->first_in == NULL);
324 ASSERT_TRUE(u3->first_in == NULL);
325 ASSERT_TRUE(a1->next_in == NULL);
326
327 }
328
TEST_F(GraphTest,api_test)329 TEST_F(GraphTest, api_test)
330 {
331 Digraph graph;
332
333 Digraph::Node node = graph.addNode();
334 graph.addNode();
335 graph.addNode();
336 graph.addNode();
337
338 ASSERT_EQ(4, graph.numOfNodes());
339 ASSERT_EQ(0, graph.numOfArcs());
340 }
341