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