1 #include <algorithm> // std::find 2 #include <cstdio> // log redirection 3 #include <functional> // std::greater 4 #include <initializer_list> 5 #include <iterator> 6 #include <type_traits> 7 #include <vector> // range-insert testing 8 9 #include "catch/catch.hpp" 10 #include "colony_list_test_helpers.h" 11 #include "list.h" 12 13 TEST_CASE( "list basics", "[list]" ) 14 { 15 { 16 cata::list<int *> test_list; 17 int ten = 10; 18 int twenty = 20; 19 20 SECTION( "empty()" ) { 21 CHECK( test_list.empty() ); 22 23 test_list.push_front( &ten ); 24 25 CHECK( !test_list.empty() ); 26 } 27 28 SECTION( "begin() and end()" ) { 29 test_list.push_front( &ten ); 30 31 CHECK( **test_list.begin() == 10 ); 32 CHECK_FALSE( test_list.begin() == test_list.end() ); 33 34 test_list.clear(); 35 36 CHECK( test_list.begin() == test_list.end() ); 37 } 38 39 for( int i = 0; i < 200; i++ ) { 40 test_list.push_back( &ten ); 41 test_list.push_back( &twenty ); 42 } 43 44 SECTION( "iterator count/access" ) { 45 int count = 0; 46 int sum = 0; 47 for( cata::list<int *>::iterator it = test_list.begin(); it != test_list.end(); 48 ++it ) { 49 ++count; 50 sum += **it; 51 } 52 53 CHECK( count == 400 ); 54 CHECK( sum == 6000 ); 55 } 56 57 SECTION( "iterator distance" ) { 58 cata::list<int *>::iterator plus_twenty = test_list.begin(); 59 std::advance( plus_twenty, 20 ); 60 61 cata::list<int *>::iterator plus_two_hundred = test_list.begin(); 62 std::advance( plus_two_hundred, 200 ); 63 64 CHECK( std::distance( test_list.begin(), plus_twenty ) == 20 ); 65 CHECK( std::distance( test_list.begin(), plus_two_hundred ) == 200 ); 66 } 67 68 SECTION( "iterator next/prev" ) { 69 cata::list<int *>::iterator next_iterator = std::next( test_list.begin(), 5 ); 70 cata::list<int *>::const_iterator prev_iterator = std::prev( test_list.cend(), 300 ); 71 72 CHECK( std::distance( test_list.begin(), next_iterator ) == 5 ); 73 CHECK( std::distance( prev_iterator, test_list.cend() ) == 300 ); 74 } 75 76 SECTION( "iterator/const_iterator equality" ) { 77 cata::list<int *>::const_iterator prev_iterator = std::prev( test_list.cend(), 300 ); 78 cata::list<int *>::iterator prev_iterator2 = std::prev( test_list.end(), 300 ); 79 80 CHECK( prev_iterator == prev_iterator2 ); 81 } 82 83 SECTION( "copy, equality, and inequality" ) { 84 cata::list<int *> test_list_2; 85 test_list_2 = test_list; 86 cata::list<int *> test_list_3( test_list ); 87 cata::list<int *> test_list_4( test_list_2, test_list_2.get_allocator() ); 88 89 cata::list<int *>::iterator it1 = test_list.begin(); 90 cata::list<int *>::const_iterator cit( it1 ); 91 92 CHECK( test_list_2.size() == 400 ); 93 CHECK( test_list_3.size() == 400 ); 94 CHECK( test_list_4.size() == 400 ); 95 96 CHECK( test_list == test_list_2 ); 97 CHECK( test_list_2 == test_list_3 ); 98 99 test_list_2.push_back( &ten ); 100 101 CHECK( test_list_2 != test_list_3 ); 102 } 103 104 SECTION( "reverse iterator count/access" ) { 105 int count = 0; 106 int sum = 0; 107 for( cata::list<int *>::reverse_iterator it = test_list.rbegin(); 108 it != test_list.rend(); ++it ) { 109 ++count; 110 sum += **it; 111 } 112 113 CHECK( count == 400 ); 114 CHECK( sum == 6000 ); 115 } 116 117 SECTION( "reverse iterator advance, next, and distance" ) { 118 cata::list<int *>::reverse_iterator r_iterator = test_list.rbegin(); 119 std::advance( r_iterator, 50 ); 120 121 CHECK( std::distance( test_list.rbegin(), r_iterator ) == 50 ); 122 123 cata::list<int *>::reverse_iterator r_iterator2 = std::next( r_iterator, 2 ); 124 125 CHECK( std::distance( test_list.rbegin(), r_iterator2 ) == 52 ); 126 } 127 128 SECTION( "multiple iteration" ) { 129 int count = 0; 130 int sum = 0; 131 for( cata::list<int *>::iterator it = test_list.begin(); it != test_list.end(); 132 std::advance( it, 2 ) ) { 133 ++count; 134 sum += **it; 135 } 136 137 CHECK( count == 200 ); 138 CHECK( sum == 2000 ); 139 } 140 141 SECTION( "reverse iterator count/access" ) { 142 int count = 0; 143 int sum = 0; 144 for( cata::list<int *>::const_iterator it = test_list.cbegin(); 145 it != test_list.cend(); ++it ) { 146 ++count; 147 sum += **it; 148 } 149 150 CHECK( count == 400 ); 151 CHECK( sum == 6000 ); 152 } 153 154 SECTION( "reverse iterator count/access" ) { 155 int count = 0; 156 int sum = 0; 157 for( cata::list<int *>::const_reverse_iterator it = test_list.crbegin(); 158 it != test_list.crend(); ++it ) { 159 ++count; 160 sum += **it; 161 } 162 163 CHECK( count == 400 ); 164 CHECK( sum == 6000 ); 165 } 166 167 SECTION( "post erase iteration and shrink to fit" ) { 168 int count = 0; 169 for( cata::list<int *>::iterator it = std::next( test_list.begin() ); 170 it != test_list.end(); ++it ) { 171 ++count; 172 it = test_list.erase( it ); 173 174 if( it == test_list.end() ) { 175 break; 176 } 177 } 178 179 CHECK( count == 200 ); 180 CHECK( test_list.size() == 200 ); 181 182 const size_t prev_capacity = test_list.capacity(); 183 test_list.shrink_to_fit(); 184 185 CHECK( test_list.capacity() < prev_capacity ); 186 CHECK( test_list.capacity() == 200 ); 187 188 count = 0; 189 for( cata::list<int *>::reverse_iterator it = test_list.rbegin(); 190 it != test_list.rend(); ) { 191 ++it; 192 cata::list<int *>::iterator it2 = it.base(); // grabs it--, essentially 193 test_list.erase( it2 ); 194 ++count; 195 } 196 197 CHECK( count == 200 ); 198 CHECK( test_list.empty() ); 199 } 200 201 SECTION( "negative iteration" ) { 202 int count = 0; 203 for( cata::list<int *>::iterator it = std::prev( test_list.end() ); 204 it != test_list.begin(); --it ) { 205 ++count; 206 } 207 208 CHECK( count == 399 ); 209 } 210 211 SECTION( "negative multiple iteration" ) { 212 int count = 0; 213 for( cata::list<int *>::iterator it = std::prev( test_list.end() ); 214 it != test_list.begin() && 215 it != std::next( test_list.begin() ); std::advance( it, -2 ) ) { 216 ++count; 217 } 218 219 CHECK( count == 199 ); 220 } 221 222 SECTION( "move" ) { 223 cata::list<int *> test_list_2; 224 test_list_2 = std::move( test_list ); 225 226 CHECK( test_list_2.size() == 400 ); 227 228 cata::list<int *> test_list_3( test_list_2 ); 229 cata::list<int *> test_list_4( std::move( test_list_3 ), test_list_2.get_allocator() ); 230 231 CHECK( test_list_4.size() == 400 ); 232 } 233 234 SECTION( "swap() and max_size()" ) { 235 cata::list<int *> test_list_2; 236 // NOLINTNEXTLINE(bugprone-use-after-move) 237 test_list_2 = test_list; 238 239 CHECK( test_list_2.size() == 400 ); 240 241 test_list.push_back( &ten ); 242 243 test_list.swap( test_list_2 ); 244 245 CHECK( test_list.size() == test_list_2.size() - 1 ); 246 247 swap( test_list, test_list_2 ); 248 249 CHECK( test_list_2.size() == test_list.size() - 1 ); 250 251 CHECK( test_list_2.max_size() > test_list_2.size() ); 252 } 253 } 254 } 255 256 TEST_CASE( "list insert and erase", "[list]" ) 257 { 258 cata::list<int> test_list; 259 260 for( int i = 0; i < 500000; i++ ) { 261 test_list.push_back( i ); 262 } 263 264 SECTION( "size after insert" ) { 265 CHECK( test_list.size() == 500000 ); 266 } 267 268 SECTION( "find iterator" ) { 269 cata::list<int>::iterator found_item = std::find( test_list.begin(), test_list.end(), 5000 ); 270 271 CHECK( *found_item == 5000 ); 272 } 273 274 SECTION( "find reverse iterator" ) { 275 cata::list<int>::reverse_iterator found_item2 = std::find( test_list.rbegin(), test_list.rend(), 276 5000 ); 277 278 CHECK( *found_item2 == 5000 ); 279 } 280 281 SECTION( "erase alternating/randomly" ) { 282 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); 283 ++it ) { 284 it = test_list.erase( it ); 285 } 286 287 CHECK( test_list.size() == 250000 ); 288 289 do { 290 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ) { 291 if( ( xor_rand() & 7 ) == 0 ) { 292 it = test_list.erase( it ); 293 } else { 294 ++it; 295 } 296 } 297 298 } while( !test_list.empty() ); 299 300 CHECK( test_list.empty() ); 301 } 302 303 SECTION( "erase randomly till half empty" ) { 304 size_t count = 0; 305 do { 306 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ) { 307 if( ( xor_rand() & 7 ) == 0 ) { 308 it = test_list.erase( it ); 309 ++count; 310 } else { 311 ++it; 312 } 313 } 314 315 } while( count < 250000 ); 316 317 CHECK( test_list.size() == 500000 - count ); 318 319 for( size_t i = 0; i < count; i++ ) { 320 test_list.push_front( 1 ); 321 } 322 323 CHECK( test_list.size() == 500000 ); 324 } 325 326 SECTION( "alternating insert/erase" ) { 327 int count = 0; 328 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ) { 329 if( ++count == 5 ) { 330 count = 0; 331 it = test_list.erase( it ); 332 } else { 333 test_list.insert( it, 1 ); 334 ++it; 335 } 336 } 337 338 CHECK( test_list.size() == 800000 ); 339 } 340 341 test_list.clear(); 342 for( int i = 0; i < 500000; i++ ) { 343 test_list.push_back( 1 ); 344 } 345 346 SECTION( "large multi increment erasure" ) { 347 cata::list<int>::iterator it = test_list.begin(); 348 std::advance( it, 250000 ); 349 350 for( ; it != test_list.end(); ) { 351 it = test_list.erase( it ); 352 } 353 354 CHECK( test_list.size() == 250000 ); 355 356 SECTION( "re-insert post heavy erasure" ) { 357 for( int i = 0; i < 250000; i++ ) { 358 test_list.push_front( 1 ); 359 } 360 361 int sum = 0; 362 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); 363 ++it ) { 364 sum += *it; 365 } 366 367 CHECK( sum == 500000 ); 368 } 369 } 370 371 SECTION( "large multi decrement erasure" ) { 372 cata::list<int>::iterator end_iterator = test_list.end(); 373 std::advance( end_iterator, -250000 ); 374 375 for( cata::list<int>::iterator it = test_list.begin(); it != end_iterator; ) { 376 it = test_list.erase( it ); 377 } 378 379 CHECK( test_list.size() == 250000 ); 380 381 SECTION( "re-insert post heavy erasure" ) { 382 for( int i = 0; i < 250000; i++ ) { 383 test_list.push_front( 1 ); 384 } 385 386 int sum = 0; 387 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); 388 ++it ) { 389 sum += *it; 390 } 391 392 CHECK( sum == 500000 ); 393 } 394 } 395 396 SECTION( "erase from middle" ) { 397 cata::list<int>::iterator end_iterator = test_list.end(); 398 std::advance( end_iterator, -50001 ); 399 cata::list<int>::iterator begin_iterator = test_list.begin(); 400 std::advance( begin_iterator, 300000 ); 401 402 for( cata::list<int>::iterator it = begin_iterator; it != end_iterator; ) { 403 it = test_list.erase( it ); 404 } 405 406 CHECK( test_list.size() == 350001 ); 407 } 408 409 SECTION( "total erase edge case" ) { 410 cata::list<int>::iterator temp_iterator = test_list.begin(); 411 std::advance( temp_iterator, 2 ); // Advance test 1 412 413 test_list.erase( temp_iterator ); 414 // Check edge-case with advance when erasures present in initial group 415 temp_iterator = test_list.begin(); 416 std::advance( temp_iterator, 500 ); 417 418 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ) { 419 it = test_list.erase( it ); 420 } 421 422 CHECK( test_list.empty() ); 423 } 424 425 SECTION( "multiple sequential small insert/erase" ) { 426 test_list.clear(); 427 test_list.shrink_to_fit(); 428 429 const size_t prev_capacity = test_list.capacity(); 430 test_list.reserve( 1000 ); 431 432 CHECK( prev_capacity != test_list.capacity() ); 433 CHECK( test_list.capacity() == 1000 ); 434 435 size_t count = 0; 436 for( int loop1 = 0; loop1 < 50000; loop1++ ) { 437 for( int loop = 0; loop < 10; loop++ ) { 438 if( ( xor_rand() & 7 ) == 0 ) { 439 test_list.push_back( 1 ); 440 ++count; 441 } 442 } 443 444 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ) { 445 if( ( xor_rand() & 7 ) == 0 ) { 446 it = test_list.erase( it ); 447 --count; 448 } else { 449 ++it; 450 } 451 } 452 } 453 454 CHECK( count == test_list.size() ); 455 } 456 } 457 458 TEST_CASE( "list merge", "[list]" ) 459 { 460 cata::list<int> test_list; 461 test_list.insert( test_list.end(), {1, 3, 5, 7, 9} ); 462 cata::list<int> test_list_2 = {2, 4, 6, 8, 10}; 463 464 test_list.merge( test_list_2 ); 465 466 bool passed = true; 467 int count = 0; 468 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 469 if( ++count != *it ) { 470 passed = false; 471 break; 472 } 473 } 474 475 CHECK( passed ); 476 } 477 478 TEST_CASE( "list splice", "[list]" ) 479 { 480 cata::list<int> test_list = {1, 2, 3, 4, 5}; 481 cata::list<int> test_list_2 = {6, 7, 8, 9, 10}; 482 483 SECTION( "splice at end" ) { 484 test_list.splice( test_list.end(), test_list_2 ); 485 486 bool passed = true; 487 int count = 0; 488 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 489 if( ++count != *it ) { 490 passed = false; 491 break; 492 } 493 } 494 495 CHECK( passed ); 496 } 497 498 SECTION( "splice at begin" ) { 499 test_list.splice( test_list.begin(), test_list_2 ); 500 501 int count = 0; 502 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 503 count += *it; 504 } 505 506 CHECK( count == 55 ); 507 } 508 509 SECTION( "splice past middle" ) { 510 cata::list<int>::iterator it2 = test_list.begin(); 511 std::advance( it2, 3 ); 512 513 test_list.splice( it2, test_list_2 ); 514 515 int count = 0; 516 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 517 count += *it; 518 } 519 520 test_list.clear(); 521 test_list_2.clear(); 522 523 for( int i = 1; i < 25; i++ ) { 524 test_list.push_back( i ); 525 test_list_2.push_back( i + 25 ); 526 } 527 528 cata::list<int>::iterator it3 = test_list.begin(); 529 std::advance( it3, 18 ); 530 531 test_list.splice( it3, test_list_2 ); 532 533 count = 0; 534 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 535 count += *it; 536 } 537 538 CHECK( count == 1200 ); 539 } 540 541 SECTION( "large splice" ) { 542 test_list.clear(); 543 test_list_2.clear(); 544 545 for( int i = 5; i < 36; i++ ) { 546 test_list.push_back( i ); 547 test_list_2.push_front( i ); 548 } 549 550 test_list.splice( test_list.begin(), test_list_2 ); 551 552 int count = 0; 553 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 554 count += *it; 555 } 556 557 CHECK( count == 1240 ); 558 } 559 } 560 561 TEST_CASE( "list sort and reverse", "[list]" ) 562 { 563 cata::list<int> test_list; 564 565 for( int i = 0; i < 500; ++i ) { 566 test_list.push_back( xor_rand() & 65535 ); 567 } 568 569 SECTION( "less than (default)" ) { 570 test_list.sort(); 571 572 bool passed = true; 573 int previous = 0; 574 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 575 if( *it < previous ) { 576 passed = false; 577 break; 578 } 579 previous = *it; 580 } 581 582 CHECK( passed ); 583 } 584 585 SECTION( "greater than (predicate)" ) { 586 test_list.sort( std::greater<>() ); 587 588 bool passed = true; 589 int previous = 65535; 590 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 591 if( *it > previous ) { 592 passed = false; 593 break; 594 } 595 previous = *it; 596 } 597 598 CHECK( passed ); 599 600 SECTION( "reverse" ) { 601 test_list.reverse(); 602 603 passed = true; 604 previous = 0; 605 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 606 607 if( *it < previous ) { 608 passed = false; 609 break; 610 } 611 612 previous = *it; 613 } 614 615 CHECK( passed ); 616 } 617 } 618 } 619 620 TEST_CASE( "list unique", "[list]" ) 621 { 622 cata::list<int> test_list = {1, 1, 2, 3, 3, 4, 5, 5}; 623 624 SECTION( "control case" ) { 625 bool passed = true; 626 int previous = 0; 627 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 628 if( *it == previous ) { 629 passed = false; 630 } 631 632 previous = *it; 633 } 634 635 CHECK_FALSE( passed ); 636 } 637 638 SECTION( "invoke unique" ) { 639 test_list.unique(); 640 641 bool passed = true; 642 int previous = 0; 643 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 644 if( *it == previous ) { 645 passed = false; 646 break; 647 } 648 649 previous = *it; 650 } 651 652 CHECK( passed ); 653 } 654 } 655 656 TEST_CASE( "list remove", "[list]" ) 657 { 658 cata::list<int> test_list = {1, 3, 1, 50, 16, 15, 2, 22}; 659 660 SECTION( "remove_if()" ) { __anon7b0a683f0102( int value ) 661 test_list.remove_if( []( int value ) { 662 return value > 15; 663 } ); 664 665 bool passed = true; 666 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 667 if( *it > 15 ) { 668 passed = false; 669 break; 670 } 671 } 672 673 CHECK( passed ); 674 } 675 676 SECTION( "remove()" ) { 677 test_list.remove( 1 ); 678 679 bool passed = true; 680 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 681 if( *it == 1 ) { 682 passed = false; 683 break; 684 } 685 } 686 687 CHECK( passed ); 688 } 689 690 SECTION( "remove() till empty" ) { 691 test_list.remove( 1 ); 692 test_list.remove( 22 ); 693 test_list.remove( 15 ); 694 test_list.remove( 16 ); 695 test_list.remove( 3 ); 696 test_list.remove( 50 ); 697 test_list.remove( 2 ); 698 699 CHECK( test_list.empty() ); 700 } 701 } 702 703 TEST_CASE( "list reserve", "[list]" ) 704 { 705 cata::list<int> test_list; 706 707 test_list.reserve( 4097 ); 708 709 CHECK( test_list.capacity() >= 4097 ); 710 711 test_list.push_back( 15 ); 712 713 int count = 0; 714 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 715 ++count; 716 } 717 718 CHECK( test_list.size() == static_cast<size_t>( count ) ); 719 720 test_list.insert( test_list.end(), 10000, 15 ); 721 722 count = 0; 723 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 724 ++count; 725 } 726 727 CHECK( test_list.size() == 10001 ); 728 CHECK( count == 10001 ); 729 CHECK( test_list.capacity() >= 10001 ); 730 731 test_list.reserve( 15000 ); 732 733 CHECK( test_list.capacity() >= 15000 ); 734 } 735 736 TEST_CASE( "list resize", "[list]" ) 737 { 738 cata::list<int> test_list = { 1, 2, 3, 4, 5, 6, 7 }; 739 740 test_list.resize( 2 ); 741 742 int count = 0; 743 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 744 ++count; 745 } 746 747 CHECK( test_list.size() == 2 ); 748 CHECK( count == 2 ); 749 } 750 751 TEST_CASE( "list assign", "[list]" ) 752 { 753 cata::list<int> test_list; 754 755 SECTION( "range assign" ) { 756 std::vector<int> test_vector = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 757 758 test_list.assign( test_vector.begin(), test_vector.end() ); 759 760 bool passed = true; 761 int count = 0; 762 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 763 if( ++count != *it ) { 764 passed = false; 765 break; 766 } 767 } 768 769 CHECK( test_list.size() == 10 ); 770 CHECK( count == 10 ); 771 CHECK( passed ); 772 } 773 774 SECTION( "fill assign" ) { 775 test_list.assign( 20, 1 ); 776 777 bool passed = true; 778 int count = 0; 779 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 780 if( *it != 1 ) { 781 passed = false; 782 break; 783 } 784 ++count; 785 } 786 787 CHECK( test_list.size() == 20 ); 788 CHECK( count == 20 ); 789 CHECK( passed ); 790 } 791 792 SECTION( "initializer list assign" ) { 793 std::initializer_list<int> inlist = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 794 795 test_list.assign( inlist ); 796 797 bool passed = true; 798 int count = 11; 799 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 800 if( --count != *it ) { 801 passed = false; 802 break; 803 } 804 } 805 806 CHECK( test_list.size() == 10 ); 807 CHECK( count == 1 ); 808 CHECK( passed ); 809 } 810 } 811 812 TEST_CASE( "list insert", "[list]" ) 813 { 814 cata::list<int> test_list; 815 816 std::vector<int> test_vector = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 817 test_list.insert( test_list.end(), test_vector.begin(), test_vector.end() ); 818 819 SECTION( "range insert" ) { 820 821 bool passed = true; 822 int count = 0; 823 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 824 if( ++count != *it ) { 825 passed = false; 826 } 827 } 828 829 CHECK( passed ); 830 } 831 832 test_list.insert( test_list.begin(), 50, 50000 ); 833 834 SECTION( "fill insert" ) { 835 int count = 0; 836 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 837 ++count; 838 } 839 840 CHECK( count == 60 ); 841 CHECK( test_list.size() == 60 ); 842 } 843 844 SECTION( "erase/insert randomly til empty" ) { 845 while( !test_list.empty() ) { 846 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ) { 847 if( ( xor_rand() & 15 ) == 0 ) { 848 test_list.insert( it, 13 ); 849 } 850 851 if( ( xor_rand() & 7 ) == 0 ) { 852 it = test_list.erase( it ); 853 } else { 854 ++it; 855 } 856 } 857 } 858 859 CHECK( test_list.empty() ); 860 } 861 } 862 863 TEST_CASE( "list emplace, move, copy, and reverse iterate", "[list]" ) 864 { 865 cata::list<small_struct> test_list; 866 867 for( int counter = 0; counter < 254; counter++ ) { 868 test_list.emplace_back( counter ); 869 } 870 871 SECTION( "emplace_back() success" ) { 872 bool passed = true; 873 int count = 0; 874 for( cata::list<small_struct>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 875 if( count++ != it->number ) { 876 passed = false; 877 break; 878 } 879 } 880 881 CHECK( passed ); 882 } 883 884 SECTION( "emplace_back() return value" ) { 885 small_struct &temp = test_list.emplace_back( 254 ); 886 CHECK( temp.number == 254 ); 887 } 888 889 SECTION( "reverse iteration" ) { 890 bool passed = true; 891 int count = 254; 892 for( cata::list<small_struct>::reverse_iterator rit = test_list.rbegin(); 893 rit != test_list.rend(); ++rit ) { 894 if( --count != rit->number ) { 895 passed = false; 896 break; 897 } 898 } 899 900 CHECK( passed ); 901 } 902 903 for( int counter = -1; counter != -255; --counter ) { 904 test_list.emplace_front( counter ); 905 } 906 907 SECTION( "emplace_front()" ) { 908 bool passed = true; 909 int count = -255; 910 for( cata::list<small_struct>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 911 if( ++count != it->number ) { 912 passed = false; 913 break; 914 } 915 } 916 917 CHECK( passed ); 918 } 919 920 SECTION( "emplace_front() return value" ) { 921 small_struct &temp = test_list.emplace_front( -255 ); 922 CHECK( temp.number == -255 ); 923 } 924 925 SECTION( "reverse iteration 2" ) { 926 bool passed = true; 927 int count = 254; 928 for( cata::list<small_struct>::reverse_iterator rit = test_list.rbegin(); 929 rit != test_list.rend(); ++rit ) { 930 if( --count != rit->number ) { 931 passed = false; 932 break; 933 } 934 } 935 936 CHECK( passed ); 937 } 938 939 cata::list<small_struct> test_list_2( std::move( test_list ) ); 940 941 SECTION( "move constructor" ) { 942 bool passed = true; 943 int count = 254; 944 for( cata::list<small_struct>::reverse_iterator rit = test_list_2.rbegin(); 945 rit != test_list_2.rend(); ++rit ) { 946 if( --count != rit->number ) { 947 passed = false; 948 break; 949 } 950 } 951 952 CHECK( passed ); 953 // NOLINTNEXTLINE(bugprone-use-after-move) 954 CHECK( test_list.empty() ); 955 } 956 957 SECTION( "emplace post-moved list" ) { 958 // Reuse the moved list will cause segmentation fault 959 test_list.emplace_back( 3 ); 960 CHECK( test_list.size() == 1 ); 961 } 962 963 test_list = std::move( test_list_2 ); 964 965 SECTION( "move assignment" ) { 966 bool passed = true; 967 int count = 254; 968 for( cata::list<small_struct>::reverse_iterator rit = test_list.rbegin(); 969 rit != test_list.rend(); ++rit ) { 970 if( --count != rit->number ) { 971 passed = false; 972 break; 973 } 974 } 975 976 CHECK( passed ); 977 // NOLINTNEXTLINE(bugprone-use-after-move) 978 CHECK( test_list_2.empty() ); 979 } 980 981 SECTION( "copy assignment" ) { 982 test_list_2 = test_list; 983 984 bool passed = true; 985 int count = 254; 986 for( cata::list<small_struct>::reverse_iterator rit = test_list_2.rbegin(); 987 rit != test_list_2.rend(); 988 ++rit ) { 989 if( --count != rit->number ) { 990 passed = false; 991 break; 992 } 993 } 994 995 CHECK( passed ); 996 } 997 998 SECTION( "copy constructor" ) { 999 // NOLINTNEXTLINE(performance-unnecessary-copy-initialization) 1000 cata::list<small_struct> list3( test_list ); 1001 1002 bool passed = true; 1003 int count = 254; 1004 for( cata::list<small_struct>::reverse_iterator rit = list3.rbegin(); 1005 rit != list3.rend(); ++rit ) { 1006 if( --count != rit->number ) { 1007 passed = false; 1008 break; 1009 } 1010 } 1011 1012 CHECK( passed ); 1013 } 1014 } 1015 1016 TEST_CASE( "list reorder", "[list]" ) 1017 { 1018 cata::list<int> test_list; 1019 1020 for( int i = 0; i < 255; ++i ) { 1021 test_list.push_back( i ); 1022 } 1023 1024 // Used for the post reorder data consistency test 1025 int original_sum = 0; 1026 for( cata::list<int>::iterator it = test_list.begin(); it != test_list.end(); ++it ) { 1027 original_sum += *it; 1028 } 1029 1030 cata::list<int>::iterator it1 = test_list.begin(); 1031 cata::list<int>::iterator it2 = test_list.begin(); 1032 cata::list<int>::iterator it3 = test_list.begin(); 1033 1034 std::advance( it1, 25 ); 1035 std::advance( it2, 5 ); 1036 1037 test_list.reorder( it2, it1 ); 1038 1039 it1 = test_list.begin(); 1040 std::advance( it1, 5 ); 1041 1042 SECTION( "single reorder" ) { 1043 CHECK( *it1 == 25 ); 1044 } 1045 1046 it1 = test_list.begin(); 1047 std::advance( it1, 152 ); 1048 1049 test_list.reorder( test_list.begin(), it1 ); 1050 1051 SECTION( "single reorder to begin" ) { 1052 CHECK( test_list.front() == 152 ); 1053 } 1054 1055 test_list.reorder( test_list.end(), it2 ); 1056 1057 SECTION( "single reorder to end" ) { 1058 it1 = std::prev( test_list.end() ); 1059 CHECK( *it1 == 5 ); 1060 } 1061 1062 it1 = test_list.begin(); 1063 it2 = test_list.begin(); 1064 1065 std::advance( it1, 50 ); 1066 std::advance( it2, 60 ); 1067 std::advance( it3, 70 ); 1068 1069 test_list.reorder( it3, it1, it2 ); 1070 1071 SECTION( "range reorder" ) { 1072 it3 = test_list.begin(); 1073 std::advance( it3, 60 ); 1074 1075 bool passed = true; 1076 for( int test = 50; test < 60; test++ ) { 1077 if( *it3 != test ) { 1078 passed = false; 1079 } 1080 ++it3; 1081 } 1082 1083 CHECK( passed == true ); 1084 } 1085 1086 it1 = test_list.begin(); 1087 it2 = test_list.begin(); 1088 1089 std::advance( it1, 80 ); 1090 std::advance( it2, 120 ); 1091 1092 test_list.reorder( test_list.end(), it1, it2 ); 1093 1094 SECTION( "range reorer to end" ) { 1095 it3 = test_list.end(); 1096 std::advance( it3, -41 ); 1097 1098 bool passed = true; 1099 for( int test = 80; test < 120; test++ ) { 1100 if( *it3 != test ) { 1101 passed = false; 1102 } 1103 ++it3; 1104 } 1105 1106 CHECK( passed == true ); 1107 } 1108 1109 it1 = test_list.begin(); 1110 it2 = test_list.begin(); 1111 1112 std::advance( it1, 40 ); 1113 std::advance( it2, 45 ); 1114 1115 test_list.reorder( test_list.begin(), it1, it2 ); 1116 1117 SECTION( "range reorder to begin" ) { 1118 it3 = test_list.begin(); 1119 1120 bool passed = true; 1121 for( int test = 40; test < 45; test++ ) { 1122 if( *it3 != test ) { 1123 passed = false; 1124 } 1125 ++it3; 1126 } 1127 1128 CHECK( passed == true ); 1129 } 1130 1131 SECTION( "post reorder data consistency" ) { 1132 int sum = 0; 1133 for( it1 = test_list.begin(); it1 != test_list.end(); ++it1 ) { 1134 sum += *it1; 1135 } 1136 1137 CHECK( sum == original_sum ); 1138 } 1139 } 1140 1141 TEST_CASE( "list insertion styles", "[list]" ) 1142 { 1143 cata::list<int> test_list = {1, 2, 3}; 1144 1145 CHECK( test_list.size() == 3 ); 1146 1147 cata::list<int> test_list_2( test_list.begin(), test_list.end() ); 1148 1149 CHECK( test_list_2.size() == 3 ); 1150 1151 cata::list<int> test_list_3( 5000, 2 ); 1152 1153 CHECK( test_list_3.size() == 5000 ); 1154 1155 test_list_2.insert( test_list_2.end(), 500000, 5 ); 1156 1157 CHECK( test_list_2.size() == 500003 ); 1158 1159 std::vector<int> some_ints( 500, 2 ); 1160 1161 test_list_2.insert( test_list_2.begin(), some_ints.begin(), some_ints.end() ); 1162 1163 CHECK( test_list_2.size() == 500503 ); 1164 } 1165 1166 TEST_CASE( "list perfect forwarding", "[list]" ) 1167 { 1168 cata::list<perfect_forwarding_test> test_list; 1169 1170 int lvalue = 0; 1171 int &lvalueref = lvalue; 1172 1173 test_list.emplace( test_list.end(), 7, lvalueref ); 1174 1175 CHECK( ( *test_list.begin() ).success ); 1176 CHECK( lvalueref == 1 ); 1177 } 1178