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
13using namespace mcld;
14using namespace mcld::test;
15using namespace mcld::graph;
16
17// Constructor can do set-up work for all test here.
18GraphTest::GraphTest() {
19}
20
21// Destructor can do clean-up work that doesn't throw exceptions here.
22GraphTest::~GraphTest() {
23}
24
25// SetUp() will be called immediately before each test.
26void GraphTest::SetUp() {
27}
28
29// TearDown() will be called immediately after each test.
30void GraphTest::TearDown() {
31}
32
33//===----------------------------------------------------------------------===//
34// Testcases
35//===----------------------------------------------------------------------===//
36TEST_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
83TEST_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
130TEST_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
177TEST_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
197TEST_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
217TEST_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
243TEST_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
269TEST_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
295TEST_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
313TEST_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