GraphTest.cpp revision 87f34658dec9097d987d254a990ea7f311bfc95f 
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
22// Destructor can do clean-up work that doesn't throw exceptions here.
23GraphTest::~GraphTest()
24{
25}
26
27// SetUp() will be called immediately before each test.
28void GraphTest::SetUp()
29{
30}
31
32// TearDown() will be called immediately after each test.
33void GraphTest::TearDown()
34{
35}
36
37//===----------------------------------------------------------------------===//
38// Testcases
39//===----------------------------------------------------------------------===//
40TEST_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
88TEST_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
136TEST_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
185TEST_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
206TEST_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
227TEST_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
255TEST_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
282TEST_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
309TEST_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
329TEST_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