1 2 static char help[] = "Tests `PetscGarbageKeySortedIntersect()`\n\n"; 3 4 #include <petscsys.h> 5 #include <petsc/private/garbagecollector.h> 6 7 /* This program tests `PetscGarbageKeySortedIntersect(), which is the 8 public (MPI) interface to 9 `PetscErrorCode GarbageKeySortedIntersect_Private()`. 10 Sets are sent packed in arrays, with the first entry as the number of 11 set elements and the sets the remaining elements. This is because the 12 MPI reduction operation must have the call signature: 13 void PetscGarbageKeySortedIntersect(void *inset, void *inoutset, PetscMPIInt *length, MPI_Datatype *dtype) 14 This is a thin wrapper for the private routine: 15 PetscErrorCode GarbageKeySortedIntersect_Private(PetscInt64 seta[], PetscInt *lena, PetscInt64 setb[], PetscInt lenb) 16 Where 17 seta = (PetscInt64 *)inoutset; 18 setb = (PetscInt64 *)inset; 19 And the arguments are passed as: 20 &seta[1], (PetscInt *)&seta[0], &setb[1], (PetscInt)setb[0] 21 */ 22 23 /* Populate a set with upto the first 49 unique Fibonnaci numbers */ 24 PetscErrorCode Fibonnaci(PetscInt64 **set, PetscInt n) 25 { 26 PetscInt ii; 27 PetscInt64 fib[] = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 28 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 29 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025}; 30 31 PetscFunctionBeginUser; 32 PetscAssert((n < 50), PETSC_COMM_WORLD, PETSC_ERR_ARG_WRONGSTATE, "n must be less than 50\n"); 33 PetscCall(PetscMalloc1(n + 1, set)); 34 (*set)[0] = (PetscInt64)n; 35 for (ii = 0; ii < n; ii++) { (*set)[ii + 1] = fib[ii]; } 36 PetscFunctionReturn(PETSC_SUCCESS); 37 } 38 39 /* Populate a set with Square numbers */ 40 PetscErrorCode Square(PetscInt64 **set, PetscInt n) 41 { 42 PetscInt64 ii; 43 44 PetscFunctionBeginUser; 45 PetscCall(PetscMalloc1(n + 1, set)); 46 (*set)[0] = (PetscInt64)n; 47 for (ii = 1; ii < n + 1; ii++) { (*set)[ii] = ii * ii; } 48 PetscFunctionReturn(PETSC_SUCCESS); 49 } 50 51 /* Populate a set with Cube numbers */ 52 PetscErrorCode Cube(PetscInt64 **set, PetscInt n) 53 { 54 PetscInt64 ii; 55 56 PetscFunctionBeginUser; 57 PetscCall(PetscMalloc1(n + 1, set)); 58 (*set)[0] = (PetscInt64)n; 59 for (ii = 1; ii < n + 1; ii++) { (*set)[ii] = ii * ii * ii; } 60 PetscFunctionReturn(PETSC_SUCCESS); 61 } 62 63 /* Populate a set with numbers to sixth power */ 64 PetscErrorCode Sixth(PetscInt64 **set, PetscInt n) 65 { 66 PetscInt64 ii; 67 68 PetscFunctionBeginUser; 69 PetscCall(PetscMalloc1(n + 1, set)); 70 (*set)[0] = (PetscInt64)n; 71 for (ii = 1; ii < n + 1; ii++) { (*set)[ii] = ii * ii * ii * ii * ii * ii; } 72 PetscFunctionReturn(PETSC_SUCCESS); 73 } 74 75 /* Print out the contents of a set */ 76 PetscErrorCode PrintSet(PetscInt64 *set) 77 { 78 char text[64]; 79 PetscInt ii; 80 81 PetscFunctionBeginUser; 82 PetscCall(PetscPrintf(PETSC_COMM_WORLD, "[")); 83 for (ii = 1; ii <= (PetscInt)set[0]; ii++) { 84 PetscCall(PetscFormatConvert(" %" PetscInt64_FMT ",", text)); 85 PetscCall(PetscPrintf(PETSC_COMM_WORLD, text, set[ii])); 86 } 87 PetscCall(PetscPrintf(PETSC_COMM_WORLD, "]\n")); 88 PetscFunctionReturn(PETSC_SUCCESS); 89 } 90 91 /* Check set equality */ 92 PetscErrorCode AssertSetsEqual(PetscInt64 *set, PetscInt64 *true_set) 93 { 94 PetscInt ii; 95 96 PetscFunctionBeginUser; 97 PetscAssert((set[0] == true_set[0]), PETSC_COMM_WORLD, PETSC_ERR_ARG_INCOMP, "Sets of different sizes"); 98 for (ii = 1; ii < set[0] + 1; ii++) PetscAssert((set[ii] == true_set[ii]), PETSC_COMM_WORLD, PETSC_ERR_ARG_INCOMP, "Sets are different"); 99 PetscFunctionReturn(PETSC_SUCCESS); 100 } 101 102 /* Tests functionality when two enpty sets are passed */ 103 PetscErrorCode test_empty_empty() 104 { 105 PetscInt64 *set_a, *set_b; 106 PetscInt64 truth[] = {0}; 107 PetscMPIInt length = 1; 108 109 PetscFunctionBeginUser; 110 111 PetscCall(PetscMalloc1(1, &set_a)); 112 PetscCall(PetscMalloc1(1, &set_b)); 113 114 set_a[0] = 0; 115 116 set_b[0] = 0; 117 118 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 119 PetscCall(PrintSet(set_a)); 120 PetscCall(AssertSetsEqual(set_a, truth)); 121 122 PetscCall(PetscFree(set_a)); 123 PetscCall(PetscFree(set_b)); 124 125 PetscFunctionReturn(PETSC_SUCCESS); 126 } 127 128 /* Tests functionality when seta is empty */ 129 PetscErrorCode test_a_empty() 130 { 131 PetscInt64 *set_a, *set_b; 132 PetscInt64 truth[] = {0}; 133 PetscMPIInt length = 1; 134 135 PetscFunctionBeginUser; 136 137 PetscCall(PetscMalloc1(1, &set_a)); 138 PetscCall(PetscMalloc1(2, &set_b)); 139 140 set_a[0] = 0; 141 142 set_b[0] = 1; 143 set_b[1] = 1; 144 145 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 146 PetscCall(PrintSet(set_a)); 147 PetscCall(AssertSetsEqual(set_a, truth)); 148 149 PetscCall(PetscFree(set_a)); 150 PetscCall(PetscFree(set_b)); 151 152 PetscFunctionReturn(PETSC_SUCCESS); 153 } 154 155 /* Tests functionality when setb is empty */ 156 PetscErrorCode test_b_empty() 157 { 158 PetscInt64 *set_a, *set_b; 159 PetscInt64 truth[] = {0}; 160 PetscMPIInt length = 1; 161 162 PetscFunctionBeginUser; 163 164 PetscCall(PetscMalloc1(2, &set_a)); 165 PetscCall(PetscMalloc1(1, &set_b)); 166 167 set_a[0] = 1; 168 set_a[1] = 1; 169 170 set_b[0] = 0; 171 172 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 173 PetscCall(PrintSet(set_a)); 174 PetscCall(AssertSetsEqual(set_a, truth)); 175 176 PetscCall(PetscFree(set_a)); 177 PetscCall(PetscFree(set_b)); 178 179 PetscFunctionReturn(PETSC_SUCCESS); 180 } 181 182 /* Tests functionality when both sets are identical */ 183 PetscErrorCode test_identical() 184 { 185 PetscInt64 *set_a, *set_b; 186 PetscInt64 truth[] = {3, 1, 4, 9}; 187 PetscMPIInt length = 4; 188 189 PetscFunctionBeginUser; 190 191 PetscCall(PetscMalloc1(4, &set_a)); 192 PetscCall(PetscMalloc1(4, &set_b)); 193 194 set_a[0] = 3; 195 set_a[1] = 1; 196 set_a[2] = 4; 197 set_a[3] = 9; 198 199 set_b[0] = 3; 200 set_b[1] = 1; 201 set_b[2] = 4; 202 set_b[3] = 9; 203 204 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 205 PetscCall(PrintSet(set_a)); 206 PetscCall(AssertSetsEqual(set_a, truth)); 207 208 PetscCall(PetscFree(set_a)); 209 PetscCall(PetscFree(set_b)); 210 211 PetscFunctionReturn(PETSC_SUCCESS); 212 } 213 214 /* Tests functionality when sets have no elements in common */ 215 PetscErrorCode test_disjoint() 216 { 217 PetscInt64 *set_a, *set_b; 218 PetscInt64 truth[] = {0}; 219 PetscMPIInt length = 1; 220 221 PetscFunctionBeginUser; 222 223 PetscCall(PetscMalloc1(4, &set_a)); 224 PetscCall(PetscMalloc1(4, &set_b)); 225 226 set_a[0] = 3; 227 set_a[1] = 1; 228 set_a[2] = 4; 229 set_a[3] = 9; 230 231 set_b[0] = 3; 232 set_b[1] = 2; 233 set_b[2] = 6; 234 set_b[3] = 8; 235 236 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 237 PetscCall(PrintSet(set_a)); 238 PetscCall(AssertSetsEqual(set_a, truth)); 239 240 PetscCall(PetscFree(set_a)); 241 PetscCall(PetscFree(set_b)); 242 243 PetscFunctionReturn(PETSC_SUCCESS); 244 } 245 246 /* Tests functionality when sets only have one element in common */ 247 PetscErrorCode test_single_common() 248 { 249 PetscInt64 *set_a, *set_b; 250 PetscInt64 truth[] = {1, 4}; 251 PetscMPIInt length = 1; 252 253 PetscFunctionBeginUser; 254 255 PetscCall(PetscMalloc1(4, &set_a)); 256 PetscCall(PetscMalloc1(5, &set_b)); 257 258 set_a[0] = 3; 259 set_a[1] = 1; 260 set_a[2] = 4; 261 set_a[3] = 9; 262 263 set_b[0] = 3; 264 set_b[1] = 2; 265 set_b[2] = 4; 266 set_b[3] = 6; 267 set_b[4] = 8; 268 269 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 270 PetscCall(PrintSet(set_a)); 271 PetscCall(AssertSetsEqual(set_a, truth)); 272 273 PetscCall(PetscFree(set_a)); 274 PetscCall(PetscFree(set_b)); 275 276 PetscFunctionReturn(PETSC_SUCCESS); 277 } 278 279 /* Specific test case flagged by PETSc issue #1247 */ 280 PetscErrorCode test_issue_1247() 281 { 282 PetscInt64 *set_a, *set_b; 283 PetscInt64 truth[] = {0}; 284 PetscMPIInt length = 1; 285 286 PetscFunctionBeginUser; 287 288 PetscCall(PetscMalloc1(3, &set_a)); 289 PetscCall(PetscMalloc1(2, &set_b)); 290 291 set_a[0] = 2; 292 set_a[1] = 2; 293 set_a[2] = 3; 294 295 set_b[0] = 1; 296 set_b[1] = 1; 297 298 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 299 PetscCall(PrintSet(set_a)); 300 PetscCall(AssertSetsEqual(set_a, truth)); 301 302 PetscCall(PetscFree(set_a)); 303 PetscCall(PetscFree(set_b)); 304 305 PetscFunctionReturn(PETSC_SUCCESS); 306 } 307 308 /* Tests functionality when seta is empty and setb is large */ 309 PetscErrorCode test_empty_big() 310 { 311 PetscInt64 *set_a, *set_b; 312 PetscInt64 truth[] = {0}; 313 PetscMPIInt length = 1; 314 315 PetscFunctionBeginUser; 316 317 PetscCall(PetscMalloc1(1, &set_a)); 318 PetscCall(Square(&set_b, 999)); 319 320 set_a[0] = 0; 321 322 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 323 PetscCall(PrintSet(set_a)); 324 PetscCall(AssertSetsEqual(set_a, truth)); 325 326 PetscCall(PetscFree(set_a)); 327 PetscCall(PetscFree(set_b)); 328 329 PetscFunctionReturn(PETSC_SUCCESS); 330 } 331 332 /* Tests functionality when seta is small and setb is large */ 333 PetscErrorCode test_small_big() 334 { 335 PetscInt64 *set_a, *set_b; 336 PetscInt64 truth[] = {3, 1, 4, 9}; 337 PetscMPIInt length = 1; 338 339 PetscFunctionBeginUser; 340 341 PetscCall(PetscMalloc1(5, &set_a)); 342 PetscCall(Square(&set_b, 999)); 343 344 set_a[0] = 4; 345 set_a[1] = 1; 346 set_a[2] = 4; 347 set_a[3] = 8; 348 set_a[4] = 9; 349 350 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 351 PetscCall(PrintSet(set_a)); 352 PetscCall(AssertSetsEqual(set_a, truth)); 353 354 PetscCall(PetscFree(set_a)); 355 PetscCall(PetscFree(set_b)); 356 357 PetscFunctionReturn(PETSC_SUCCESS); 358 } 359 360 /* Tests functionality when seta is medium sized and setb is large */ 361 PetscErrorCode test_moderate_big() 362 { 363 PetscInt64 *set_a, *set_b; 364 PetscInt64 truth[] = {2, 1, 144}; 365 PetscMPIInt length = 1; 366 367 PetscFunctionBeginUser; 368 369 PetscCall(Fibonnaci(&set_a, 49)); 370 PetscCall(Square(&set_b, 999)); 371 372 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 373 PetscCall(PrintSet(set_a)); 374 PetscCall(AssertSetsEqual(set_a, truth)); 375 376 PetscCall(PetscFree(set_a)); 377 PetscCall(PetscFree(set_b)); 378 379 PetscFunctionReturn(PETSC_SUCCESS); 380 } 381 382 /* Tests functionality when seta and setb are large */ 383 PetscErrorCode test_big_big() 384 { 385 PetscInt64 *set_a, *set_b; 386 PetscInt64 *truth; 387 PetscMPIInt length = 1; 388 389 PetscFunctionBeginUser; 390 391 PetscCall(Cube(&set_a, 999)); 392 PetscCall(Square(&set_b, 999)); 393 394 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 395 PetscCall(PrintSet(set_a)); 396 397 PetscCall(Sixth(&truth, 9)); 398 PetscCall(AssertSetsEqual(set_a, truth)); 399 400 PetscCall(PetscFree(set_a)); 401 PetscCall(PetscFree(set_b)); 402 PetscCall(PetscFree(truth)); 403 404 PetscFunctionReturn(PETSC_SUCCESS); 405 } 406 407 /* Tests functionality when setb is empty and setb is large */ 408 PetscErrorCode test_big_empty() 409 { 410 PetscInt64 *set_a, *set_b; 411 PetscInt64 truth[] = {0}; 412 PetscMPIInt length = 1; 413 414 PetscFunctionBeginUser; 415 416 PetscCall(Cube(&set_a, 999)); 417 PetscCall(PetscMalloc1(1, &set_b)); 418 419 set_b[0] = 0; 420 421 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 422 PetscCall(PrintSet(set_a)); 423 PetscCall(AssertSetsEqual(set_a, truth)); 424 425 PetscCall(PetscFree(set_a)); 426 PetscCall(PetscFree(set_b)); 427 428 PetscFunctionReturn(PETSC_SUCCESS); 429 } 430 431 /* Tests functionality when setb is small and setb is large */ 432 PetscErrorCode test_big_small() 433 { 434 PetscInt64 *set_a, *set_b; 435 PetscInt64 truth[] = {2, 1, 8}; 436 PetscMPIInt length = 1; 437 438 PetscFunctionBeginUser; 439 440 PetscCall(Cube(&set_a, 999)); 441 PetscCall(PetscMalloc1(5, &set_b)); 442 443 set_b[0] = 4; 444 set_b[1] = 1; 445 set_b[2] = 4; 446 set_b[3] = 8; 447 set_b[4] = 9; 448 449 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 450 PetscCall(PrintSet(set_a)); 451 PetscCall(AssertSetsEqual(set_a, truth)); 452 453 PetscCall(PetscFree(set_a)); 454 PetscCall(PetscFree(set_b)); 455 456 PetscFunctionReturn(PETSC_SUCCESS); 457 } 458 459 /* Tests functionality when setb is medium sized and setb is large */ 460 PetscErrorCode test_big_moderate() 461 { 462 PetscInt64 *set_a, *set_b; 463 PetscInt64 truth[] = {2, 1, 8}; 464 PetscMPIInt length = 1; 465 466 PetscFunctionBeginUser; 467 468 PetscCall(Cube(&set_a, 999)); 469 PetscCall(Fibonnaci(&set_b, 49)); 470 471 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 472 PetscCall(PrintSet(set_a)); 473 PetscCall(AssertSetsEqual(set_a, truth)); 474 475 PetscCall(PetscFree(set_a)); 476 PetscCall(PetscFree(set_b)); 477 478 PetscFunctionReturn(PETSC_SUCCESS); 479 } 480 481 /* Tests functionality when seta and setb are large, in the opposite 482 order to test_big_big() */ 483 PetscErrorCode test_big_big_reversed() 484 { 485 PetscInt64 *set_a, *set_b; 486 PetscInt64 *truth; 487 PetscMPIInt length = 1; 488 489 PetscFunctionBeginUser; 490 491 PetscCall(Cube(&set_a, 999)); 492 PetscCall(Square(&set_b, 999)); 493 494 PetscGarbageKeySortedIntersect((void *)set_b, (void *)set_a, &length, NULL); 495 PetscCall(PrintSet(set_a)); 496 497 PetscCall(Sixth(&truth, 9)); 498 PetscCall(AssertSetsEqual(set_a, truth)); 499 500 PetscCall(PetscFree(set_a)); 501 PetscCall(PetscFree(set_b)); 502 PetscCall(PetscFree(truth)); 503 504 PetscFunctionReturn(PETSC_SUCCESS); 505 } 506 507 /* Main executes the individual tests in a predefined order */ 508 int main(int argc, char **argv) 509 { 510 PetscFunctionBeginUser; 511 PetscCall(PetscInitialize(&argc, &argv, (char *)0, help)); 512 513 /* Small tests */ 514 /* Test different edge cases with small sets */ 515 PetscCall(test_empty_empty()); 516 PetscCall(test_a_empty()); 517 PetscCall(test_b_empty()); 518 PetscCall(test_identical()); 519 PetscCall(test_disjoint()); 520 PetscCall(test_single_common()); 521 PetscCall(test_issue_1247()); 522 523 /* Big tests */ 524 /* Test different edge cases with big sets */ 525 PetscCall(test_empty_big()); 526 PetscCall(test_small_big()); 527 PetscCall(test_moderate_big()); 528 PetscCall(test_big_big()); 529 PetscCall(test_big_empty()); 530 PetscCall(test_big_small()); 531 PetscCall(test_big_moderate()); 532 PetscCall(test_big_big_reversed()); 533 534 PetscCall(PetscPrintf(PETSC_COMM_WORLD, "ALL PASSED\n")); 535 PetscCall(PetscFinalize()); 536 return 0; 537 } 538 539 /*TEST 540 541 test: 542 suffix: 0 543 544 TEST*/ 545