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