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. 18 GraphTest::GraphTest() 19 { 20 } 21 22 // Destructor can do clean-up work that doesn't throw exceptions here. 23 GraphTest::~GraphTest() 24 { 25 } 26 27 // SetUp() will be called immediately before each test. 28 void GraphTest::SetUp() 29 { 30 } 31 32 // TearDown() will be called immediately after each test. 33 void GraphTest::TearDown() 34 { 35 } 36 37 //===----------------------------------------------------------------------===// 38 // Testcases 39 //===----------------------------------------------------------------------===// 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 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 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 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 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 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 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 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 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 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
