gdb/unittests/intrusive_list-selftests.c

   1 /* Tests fpr intrusive double linked list for GDB, the GNU debugger.
   2    Copyright (C) 2021-2024 Free Software Foundation, Inc.
   3
   4    This file is part of GDB.
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  18
  19
  20 #include "gdbsupport/intrusive_list.h"
  21 #include "gdbsupport/owning_intrusive_list.h"
  22 #include "gdbsupport/selftest.h"
  23 #include <unordered_set>
  24
  25 /* Count of how many item_with_base or item_with_member objects are
  26    currently alive.  */
  27
  28 static int items_alive = 0;
  29
  30 /* An item type using intrusive_list_node by inheriting from it and its
  31    corresponding list type.  Put another base before intrusive_list_node
  32    so that a pointer to the node != a pointer to the item.  */
  33
  34 struct other_base
  35 {
  36   int n = 1;
  37 };
  38
  39 struct item_with_base : public other_base,
  40                         public intrusive_list_node<item_with_base>
  41 {
  42   explicit item_with_base (const char *name)
  43     : name (name)
  44   {
  45     ++items_alive;
  46   }
  47
  48   DISABLE_COPY_AND_ASSIGN (item_with_base);
  49
  50   ~item_with_base () { --items_alive; }
  51
  52   const char *const name;
  53 };
  54
  55 using item_with_base_list = intrusive_list<item_with_base>;
  56
  57 /* An item type using intrusive_list_node as a field and its corresponding
  58    list type.  Put the other field before the node, so that a pointer to the
  59    node != a pointer to the item.  */
  60
  61 struct item_with_member
  62 {
  63   explicit item_with_member (const char *name)
  64     : name (name)
  65   {
  66     ++items_alive;
  67   }
  68
  69   DISABLE_COPY_AND_ASSIGN (item_with_member);
  70
  71   ~item_with_member () { --items_alive; }
  72
  73   const char *const name;
  74   intrusive_list_node<item_with_member> node;
  75 };
  76
  77 /* Verify that LIST contains exactly the items in EXPECTED.
  78
  79    Traverse the list forward and backwards to exercise all links.  */
  80
  81 template <typename ListType>
  82 static void
  83 verify_items (const ListType &list,
  84               gdb::array_view<const typename ListType::value_type *> expected)
  85 {
  86   using item_type = typename ListType::value_type;
  87
  88   int i = 0;
  89
  90   for (typename ListType::iterator it = list.begin (); it != list.end (); ++it)
  91     {
  92       const item_type &item = *it;
  93
  94       SELF_CHECK (i < expected.size ());
  95       SELF_CHECK (&item == expected[i]);
  96
  97       /* Access the item, to make sure the object is still alive.  */
  98       SELF_CHECK (strcmp (item.name, expected[i]->name) == 0);
  99
 100       ++i;
 101     }
 102
 103   SELF_CHECK (i == expected.size ());
 104
 105   for (typename ListType::reverse_iterator it = list.rbegin ();
 106        it != list.rend (); ++it)
 107     {
 108       const item_type &item = *it;
 109
 110       --i;
 111
 112       SELF_CHECK (i >= 0);
 113       SELF_CHECK (&item == expected[i]);
 114
 115       /* Access the item, to make sure the object is still alive.  */
 116       SELF_CHECK (strcmp (item.name, expected[i]->name) == 0);
 117     }
 118
 119   SELF_CHECK (i == 0);
 120 }
 121
 122 /* intrusive_list tests
 123
 124    To run all tests using both the base and member methods, all tests are
 125    declared in this templated class, which is instantiated once for each
 126    list type.  */
 127
 128 using item_with_member_node
 129   = intrusive_member_node<item_with_member, &item_with_member::node>;
 130 using item_with_member_list
 131   = intrusive_list<item_with_member, item_with_member_node>;
 132
 133 template <typename ListType>
 134 struct intrusive_list_test
 135 {
 136   using item_type = typename ListType::value_type;
 137
 138   static void
 139   test_move_constructor ()
 140   {
 141     {
 142       /* Other list is not empty.  */
 143       item_type a ("a"), b ("b"), c ("c");
 144       ListType list1;
 145       std::vector<const item_type *> expected;
 146
 147       list1.push_back (a);
 148       list1.push_back (b);
 149       list1.push_back (c);
 150
 151       ListType list2 (std::move (list1));
 152
 153       expected = {};
 154       verify_items (list1, expected);
 155
 156       expected = {&a, &b, &c};
 157       verify_items (list2, expected);
 158     }
 159
 160     {
 161       /* Other list contains 1 element.  */
 162       item_type a ("a");
 163       ListType list1;
 164       std::vector<const item_type *> expected;
 165
 166       list1.push_back (a);
 167
 168       ListType list2 (std::move (list1));
 169
 170       expected = {};
 171       verify_items (list1, expected);
 172
 173       expected = {&a};
 174       verify_items (list2, expected);
 175     }
 176
 177     {
 178       /* Other list is empty.  */
 179       ListType list1;
 180       std::vector<const item_type *> expected;
 181
 182       ListType list2 (std::move (list1));
 183
 184       expected = {};
 185       verify_items (list1, expected);
 186
 187       expected = {};
 188       verify_items (list2, expected);
 189     }
 190   }
 191
 192   static void
 193   test_move_assignment ()
 194   {
 195     {
 196       /* Both lists are not empty.  */
 197       item_type a ("a"), b ("b"), c ("c"), d ("d"), e ("e");
 198       ListType list1;
 199       ListType list2;
 200       std::vector<const item_type *> expected;
 201
 202       list1.push_back (a);
 203       list1.push_back (b);
 204       list1.push_back (c);
 205
 206       list2.push_back (d);
 207       list2.push_back (e);
 208
 209       list2 = std::move (list1);
 210
 211       expected = {};
 212       verify_items (list1, expected);
 213
 214       expected = {&a, &b, &c};
 215       verify_items (list2, expected);
 216     }
 217
 218     {
 219       /* rhs list is empty.  */
 220       item_type a ("a"), b ("b"), c ("c");
 221       ListType list1;
 222       ListType list2;
 223       std::vector<const item_type *> expected;
 224
 225       list2.push_back (a);
 226       list2.push_back (b);
 227       list2.push_back (c);
 228
 229       list2 = std::move (list1);
 230
 231       expected = {};
 232       verify_items (list1, expected);
 233
 234       expected = {};
 235       verify_items (list2, expected);
 236     }
 237
 238     {
 239       /* lhs list is empty.  */
 240       item_type a ("a"), b ("b"), c ("c");
 241       ListType list1;
 242       ListType list2;
 243       std::vector<const item_type *> expected;
 244
 245       list1.push_back (a);
 246       list1.push_back (b);
 247       list1.push_back (c);
 248
 249       list2 = std::move (list1);
 250
 251       expected = {};
 252       verify_items (list1, expected);
 253
 254       expected = {&a, &b, &c};
 255       verify_items (list2, expected);
 256     }
 257
 258     {
 259       /* Both lists contain 1 item.  */
 260       item_type a ("a"), b ("b");
 261       ListType list1;
 262       ListType list2;
 263       std::vector<const item_type *> expected;
 264
 265       list1.push_back (a);
 266       list2.push_back (b);
 267
 268       list2 = std::move (list1);
 269
 270       expected = {};
 271       verify_items (list1, expected);
 272
 273       expected = {&a};
 274       verify_items (list2, expected);
 275     }
 276
 277     {
 278       /* Both lists are empty.  */
 279       ListType list1;
 280       ListType list2;
 281       std::vector<const item_type *> expected;
 282
 283       list2 = std::move (list1);
 284
 285       expected = {};
 286       verify_items (list1, expected);
 287
 288       expected = {};
 289       verify_items (list2, expected);
 290     }
 291   }
 292
 293   static void
 294   test_swap ()
 295   {
 296     {
 297       /* Two non-empty lists.  */
 298       item_type a ("a"), b ("b"), c ("c"), d ("d"), e ("e");
 299       ListType list1;
 300       ListType list2;
 301       std::vector<const item_type *> expected;
 302
 303       list1.push_back (a);
 304       list1.push_back (b);
 305       list1.push_back (c);
 306
 307       list2.push_back (d);
 308       list2.push_back (e);
 309
 310       std::swap (list1, list2);
 311
 312       expected = {&d, &e};
 313       verify_items (list1, expected);
 314
 315       expected = {&a, &b, &c};
 316       verify_items (list2, expected);
 317     }
 318
 319     {
 320       /* Other is empty.  */
 321       item_type a ("a"), b ("b"), c ("c");
 322       ListType list1;
 323       ListType list2;
 324       std::vector<const item_type *> expected;
 325
 326       list1.push_back (a);
 327       list1.push_back (b);
 328       list1.push_back (c);
 329
 330       std::swap (list1, list2);
 331
 332       expected = {};
 333       verify_items (list1, expected);
 334
 335       expected = {&a, &b, &c};
 336       verify_items (list2, expected);
 337     }
 338
 339     {
 340       /* *this is empty.  */
 341       item_type a ("a"), b ("b"), c ("c");
 342       ListType list1;
 343       ListType list2;
 344       std::vector<const item_type *> expected;
 345
 346       list2.push_back (a);
 347       list2.push_back (b);
 348       list2.push_back (c);
 349
 350       std::swap (list1, list2);
 351
 352       expected = {&a, &b, &c};
 353       verify_items (list1, expected);
 354
 355       expected = {};
 356       verify_items (list2, expected);
 357     }
 358
 359     {
 360       /* Both lists empty.  */
 361       ListType list1;
 362       ListType list2;
 363       std::vector<const item_type *> expected;
 364
 365       std::swap (list1, list2);
 366
 367       expected = {};
 368       verify_items (list1, expected);
 369
 370       expected = {};
 371       verify_items (list2, expected);
 372     }
 373
 374     {
 375       /* Swap one element twice.  */
 376       item_type a ("a");
 377       ListType list1;
 378       ListType list2;
 379       std::vector<const item_type *> expected;
 380
 381       list1.push_back (a);
 382
 383       std::swap (list1, list2);
 384
 385       expected = {};
 386       verify_items (list1, expected);
 387
 388       expected = {&a};
 389       verify_items (list2, expected);
 390
 391       std::swap (list1, list2);
 392
 393       expected = {&a};
 394       verify_items (list1, expected);
 395
 396       expected = {};
 397       verify_items (list2, expected);
 398     }
 399   }
 400
 401   static void
 402   test_front_back ()
 403   {
 404     item_type a ("a"), b ("b"), c ("c");
 405     ListType list;
 406     const ListType &clist = list;
 407
 408     list.push_back (a);
 409     list.push_back (b);
 410     list.push_back (c);
 411
 412     SELF_CHECK (&list.front () == &a);
 413     SELF_CHECK (&clist.front () == &a);
 414     SELF_CHECK (&list.back () == &c);
 415     SELF_CHECK (&clist.back () == &c);
 416   }
 417
 418   static void
 419   test_push_front ()
 420   {
 421     item_type a ("a"), b ("b"), c ("c");
 422     ListType list;
 423     std::vector<const item_type *> expected;
 424
 425     expected = {};
 426     verify_items (list, expected);
 427
 428     list.push_front (a);
 429     expected = {&a};
 430     verify_items (list, expected);
 431
 432     list.push_front (b);
 433     expected = {&b, &a};
 434     verify_items (list, expected);
 435
 436     list.push_front (c);
 437     expected = {&c, &b, &a};
 438     verify_items (list, expected);
 439   }
 440
 441   static void
 442   test_push_back ()
 443   {
 444     item_type a ("a"), b ("b"), c ("c");
 445     ListType list;
 446     std::vector<const item_type *> expected;
 447
 448     expected = {};
 449     verify_items (list, expected);
 450
 451     list.push_back (a);
 452     expected = {&a};
 453     verify_items (list, expected);
 454
 455     list.push_back (b);
 456     expected = {&a, &b};
 457     verify_items (list, expected);
 458
 459     list.push_back (c);
 460     expected = {&a, &b, &c};
 461     verify_items (list, expected);
 462   }
 463
 464   static void
 465   test_insert ()
 466   {
 467     std::vector<const item_type *> expected;
 468
 469     {
 470       /* Insert at beginning.  */
 471       item_type a ("a"), b ("b"), c ("c");
 472       ListType list;
 473
 474
 475       auto a_it = list.insert (list.begin (), a);
 476       SELF_CHECK (&*a_it == &a);
 477       expected = {&a};
 478       verify_items (list, expected);
 479
 480       auto b_it = list.insert (list.begin (), b);
 481       SELF_CHECK (&*b_it == &b);
 482       expected = {&b, &a};
 483       verify_items (list, expected);
 484
 485       auto c_it = list.insert (list.begin (), c);
 486       SELF_CHECK (&*c_it == &c);
 487       expected = {&c, &b, &a};
 488       verify_items (list, expected);
 489     }
 490
 491     {
 492       /* Insert at end.  */
 493       item_type a ("a"), b ("b"), c ("c");
 494       ListType list;
 495
 496
 497       auto a_it = list.insert (list.end (), a);
 498       SELF_CHECK (&*a_it == &a);
 499       expected = {&a};
 500       verify_items (list, expected);
 501
 502       auto b_it = list.insert (list.end (), b);
 503       SELF_CHECK (&*b_it == &b);
 504       expected = {&a, &b};
 505       verify_items (list, expected);
 506
 507       auto c_it = list.insert (list.end (), c);
 508       SELF_CHECK (&*c_it == &c);
 509       expected = {&a, &b, &c};
 510       verify_items (list, expected);
 511     }
 512
 513     {
 514       /* Insert in the middle.  */
 515       item_type a ("a"), b ("b"), c ("c");
 516       ListType list;
 517
 518       list.push_back (a);
 519       list.push_back (b);
 520
 521       auto c_it = list.insert (list.iterator_to (b), c);
 522       SELF_CHECK (&*c_it == &c);
 523       expected = {&a, &c, &b};
 524       verify_items (list, expected);
 525     }
 526
 527     {
 528       /* Insert in empty list. */
 529       item_type a ("a");
 530       ListType list;
 531
 532       auto a_it = list.insert (list.end (), a);
 533       SELF_CHECK (&*a_it == &a);
 534       expected = {&a};
 535       verify_items (list, expected);
 536     }
 537   }
 538
 539   static void
 540   test_splice ()
 541   {
 542     {
 543       /* Two non-empty lists.  */
 544       item_type a ("a"), b ("b"), c ("c"), d ("d"), e ("e");
 545       ListType list1;
 546       ListType list2;
 547       std::vector<const item_type *> expected;
 548
 549       list1.push_back (a);
 550       list1.push_back (b);
 551       list1.push_back (c);
 552
 553       list2.push_back (d);
 554       list2.push_back (e);
 555
 556       list1.splice (std::move (list2));
 557
 558       expected = {&a, &b, &c, &d, &e};
 559       verify_items (list1, expected);
 560
 561       expected = {};
 562       verify_items (list2, expected);
 563     }
 564
 565     {
 566       /* Receiving list empty.  */
 567       item_type a ("a"), b ("b"), c ("c");
 568       ListType list1;
 569       ListType list2;
 570       std::vector<const item_type *> expected;
 571
 572       list2.push_back (a);
 573       list2.push_back (b);
 574       list2.push_back (c);
 575
 576       list1.splice (std::move (list2));
 577
 578       expected = {&a, &b, &c};
 579       verify_items (list1, expected);
 580
 581       expected = {};
 582       verify_items (list2, expected);
 583     }
 584
 585     {
 586       /* Giving list empty.  */
 587       item_type a ("a"), b ("b"), c ("c");
 588       ListType list1;
 589       ListType list2;
 590       std::vector<const item_type *> expected;
 591
 592       list1.push_back (a);
 593       list1.push_back (b);
 594       list1.push_back (c);
 595
 596       list1.splice (std::move (list2));
 597
 598       expected = {&a, &b, &c};
 599       verify_items (list1, expected);
 600
 601       expected = {};
 602       verify_items (list2, expected);
 603     }
 604
 605     {
 606       /* Both lists empty.  */
 607       ListType list1;
 608       ListType list2;
 609       std::vector<const item_type *> expected;
 610
 611       list1.splice (std::move (list2));
 612
 613       expected = {};
 614       verify_items (list1, expected);
 615
 616       expected = {};
 617       verify_items (list2, expected);
 618     }
 619   }
 620
 621   static void
 622   test_pop_front ()
 623   {
 624     item_type a ("a"), b ("b"), c ("c");
 625     ListType list;
 626     std::vector<const item_type *> expected;
 627
 628     list.push_back (a);
 629     list.push_back (b);
 630     list.push_back (c);
 631
 632     list.pop_front ();
 633     expected = {&b, &c};
 634     verify_items (list, expected);
 635
 636     list.pop_front ();
 637     expected = {&c};
 638     verify_items (list, expected);
 639
 640     list.pop_front ();
 641     expected = {};
 642     verify_items (list, expected);
 643   }
 644
 645   static void
 646   test_pop_back ()
 647   {
 648     item_type a ("a"), b ("b"), c ("c");
 649     ListType list;
 650     std::vector<const item_type *> expected;
 651
 652     list.push_back (a);
 653     list.push_back (b);
 654     list.push_back (c);
 655
 656     list.pop_back();
 657     expected = {&a, &b};
 658     verify_items (list, expected);
 659
 660     list.pop_back ();
 661     expected = {&a};
 662     verify_items (list, expected);
 663
 664     list.pop_back ();
 665     expected = {};
 666     verify_items (list, expected);
 667   }
 668
 669   static void
 670   test_erase ()
 671   {
 672     item_type a ("a"), b ("b"), c ("c");
 673     ListType list;
 674     std::vector<const item_type *> expected;
 675
 676     list.push_back (a);
 677     list.push_back (b);
 678     list.push_back (c);
 679
 680     list.erase (list.iterator_to (b));
 681     expected = {&a, &c};
 682     verify_items (list, expected);
 683
 684     list.erase (list.iterator_to (c));
 685     expected = {&a};
 686     verify_items (list, expected);
 687
 688     list.erase (list.iterator_to (a));
 689     expected = {};
 690     verify_items (list, expected);
 691   }
 692
 693   static void
 694   test_clear ()
 695   {
 696     item_type a ("a"), b ("b"), c ("c");
 697     ListType list;
 698     std::vector<const item_type *> expected;
 699
 700     list.push_back (a);
 701     list.push_back (b);
 702     list.push_back (c);
 703
 704     list.clear ();
 705     expected = {};
 706     verify_items (list, expected);
 707
 708     /* Verify idempotency.  */
 709     list.clear ();
 710     expected = {};
 711     verify_items (list, expected);
 712   }
 713
 714   static void
 715   test_clear_and_dispose ()
 716   {
 717     item_type a ("a"), b ("b"), c ("c");
 718     ListType list;
 719     std::vector<const item_type *> expected;
 720     std::unordered_set<const item_type *> disposer_seen;
 721     int disposer_calls = 0;
 722
 723     list.push_back (a);
 724     list.push_back (b);
 725     list.push_back (c);
 726
 727     auto disposer = [&] (const item_type *item)
 728       {
 729         disposer_seen.insert (item);
 730         disposer_calls++;
 731       };
 732     list.clear_and_dispose (disposer);
 733
 734     expected = {};
 735     verify_items (list, expected);
 736     SELF_CHECK (disposer_calls == 3);
 737     SELF_CHECK (disposer_seen.find (&a) != disposer_seen.end ());
 738     SELF_CHECK (disposer_seen.find (&b) != disposer_seen.end ());
 739     SELF_CHECK (disposer_seen.find (&c) != disposer_seen.end ());
 740
 741     /* Verify idempotency.  */
 742     list.clear_and_dispose (disposer);
 743     SELF_CHECK (disposer_calls == 3);
 744   }
 745
 746   static void
 747   test_empty ()
 748   {
 749     item_type a ("a");
 750     ListType list;
 751
 752     SELF_CHECK (list.empty ());
 753     list.push_back (a);
 754     SELF_CHECK (!list.empty ());
 755     list.erase (list.iterator_to (a));
 756     SELF_CHECK (list.empty ());
 757   }
 758
 759   static void
 760   test_begin_end ()
 761   {
 762     item_type a ("a"), b ("b"), c ("c");
 763     ListType list;
 764     const ListType &clist = list;
 765
 766     list.push_back (a);
 767     list.push_back (b);
 768     list.push_back (c);
 769
 770     SELF_CHECK (&*list.begin () == &a);
 771     SELF_CHECK (&*list.cbegin () == &a);
 772     SELF_CHECK (&*clist.begin () == &a);
 773     SELF_CHECK (&*list.rbegin () == &c);
 774     SELF_CHECK (&*list.crbegin () == &c);
 775     SELF_CHECK (&*clist.rbegin () == &c);
 776
 777     /* At least check that they compile.  */
 778     list.end ();
 779     list.cend ();
 780     clist.end ();
 781     list.rend ();
 782     list.crend ();
 783     clist.end ();
 784   }
 785 };
 786
 787 template <typename ListType>
 788 static void
 789 test_intrusive_list_1 ()
 790 {
 791   intrusive_list_test<ListType> tests;
 792
 793   tests.test_move_constructor ();
 794   tests.test_move_assignment ();
 795   tests.test_swap ();
 796   tests.test_front_back ();
 797   tests.test_push_front ();
 798   tests.test_push_back ();
 799   tests.test_insert ();
 800   tests.test_splice ();
 801   tests.test_pop_front ();
 802   tests.test_pop_back ();
 803   tests.test_erase ();
 804   tests.test_clear ();
 805   tests.test_clear_and_dispose ();
 806   tests.test_empty ();
 807   tests.test_begin_end ();
 808 }
 809
 810 /* owning_intrusive_list tests
 811
 812    To run all tests using both the base and member methods, all tests are
 813    declared in this templated class, which is instantiated once for each
 814    list type.  */
 815
 816 using item_with_base_owning_list = owning_intrusive_list<item_with_base>;
 817 using item_with_member_owning_list
 818   = owning_intrusive_list<item_with_member, item_with_member_node>;
 819
 820 template<typename ListType>
 821 struct owning_intrusive_list_test
 822 {
 823   using item_type = typename ListType::value_type;
 824
 825   static void test_move_constructor ()
 826   {
 827     {
 828       /* Other list is not empty.  */
 829       ListType list1;
 830       std::vector<const item_type *> expected;
 831
 832       auto &a = list1.emplace_back ("a");
 833       auto &b = list1.emplace_back ("b");
 834       auto &c = list1.emplace_back ("c");
 835
 836       SELF_CHECK (items_alive == 3);
 837       ListType list2 (std::move (list1));
 838       SELF_CHECK (items_alive == 3);
 839
 840       expected = {};
 841       verify_items (list1, expected);
 842
 843       expected = { &a, &b, &c };
 844       verify_items (list2, expected);
 845     }
 846
 847     {
 848       /* Other list contains 1 element.  */
 849       ListType list1;
 850       std::vector<const item_type *> expected;
 851
 852       auto &a = list1.emplace_back ("a");
 853
 854       SELF_CHECK (items_alive == 1);
 855       ListType list2 (std::move (list1));
 856       SELF_CHECK (items_alive == 1);
 857
 858       expected = {};
 859       verify_items (list1, expected);
 860
 861       expected = { &a };
 862       verify_items (list2, expected);
 863     }
 864
 865     {
 866       /* Other list is empty.  */
 867       ListType list1;
 868       std::vector<const item_type *> expected;
 869
 870       SELF_CHECK (items_alive == 0);
 871       ListType list2 (std::move (list1));
 872       SELF_CHECK (items_alive == 0);
 873
 874       expected = {};
 875       verify_items (list1, expected);
 876
 877       expected = {};
 878       verify_items (list2, expected);
 879     }
 880   }
 881
 882   static void test_move_assignment ()
 883   {
 884     {
 885       /* Both lists are not empty.  */
 886       ListType list1;
 887       ListType list2;
 888       std::vector<const item_type *> expected;
 889
 890       auto &a = list1.emplace_back ("a");
 891       auto &b = list1.emplace_back ("b");
 892       auto &c = list1.emplace_back ("c");
 893
 894       list2.emplace_back ("d");
 895       list2.emplace_back ("e");
 896
 897       SELF_CHECK (items_alive == 5);
 898       list2 = std::move (list1);
 899       SELF_CHECK (items_alive == 3);
 900
 901       expected = {};
 902       verify_items (list1, expected);
 903
 904       expected = { &a, &b, &c };
 905       verify_items (list2, expected);
 906     }
 907
 908     {
 909       /* rhs list is empty.  */
 910       ListType list1;
 911       ListType list2;
 912       std::vector<const item_type *> expected;
 913
 914       list2.emplace_back ("a");
 915       list2.emplace_back ("b");
 916       list2.emplace_back ("c");
 917
 918       SELF_CHECK (items_alive == 3);
 919       list2 = std::move (list1);
 920       SELF_CHECK (items_alive == 0);
 921
 922       expected = {};
 923       verify_items (list1, expected);
 924
 925       expected = {};
 926       verify_items (list2, expected);
 927     }
 928
 929     {
 930       /* lhs list is empty.  */
 931       ListType list1;
 932       ListType list2;
 933       std::vector<const item_type *> expected;
 934
 935       auto &a = list1.emplace_back ("a");
 936       auto &b = list1.emplace_back ("b");
 937       auto &c = list1.emplace_back ("c");
 938
 939       SELF_CHECK (items_alive == 3);
 940       list2 = std::move (list1);
 941       SELF_CHECK (items_alive == 3);
 942
 943       expected = {};
 944       verify_items (list1, expected);
 945
 946       expected = { &a, &b, &c };
 947       verify_items (list2, expected);
 948     }
 949
 950     {
 951       /* Both lists contain 1 item.  */
 952       ListType list1;
 953       ListType list2;
 954       std::vector<const item_type *> expected;
 955
 956       auto &a = list1.emplace_back ("a");
 957       list2.emplace_back ("b");
 958
 959       SELF_CHECK (items_alive == 2);
 960       list2 = std::move (list1);
 961       SELF_CHECK (items_alive == 1);
 962
 963       expected = {};
 964       verify_items (list1, expected);
 965
 966       expected = { &a };
 967       verify_items (list2, expected);
 968     }
 969
 970     {
 971       /* Both lists are empty.  */
 972       ListType list1;
 973       ListType list2;
 974       std::vector<const item_type *> expected;
 975
 976       SELF_CHECK (items_alive == 0);
 977       list2 = std::move (list1);
 978       SELF_CHECK (items_alive == 0);
 979
 980       expected = {};
 981       verify_items (list1, expected);
 982
 983       expected = {};
 984       verify_items (list2, expected);
 985     }
 986   }
 987
 988   static void test_swap ()
 989   {
 990     {
 991       /* Two non-empty lists.  */
 992       ListType list1;
 993       ListType list2;
 994       std::vector<const item_type *> expected;
 995
 996       auto &a = list1.emplace_back ("a");
 997       auto &b = list1.emplace_back ("b");
 998       auto &c = list1.emplace_back ("c");
 999
1000       auto &d = list2.emplace_back ("d");
1001       auto &e = list2.emplace_back ("e");
1002
1003       SELF_CHECK (items_alive == 5);
1004       std::swap (list1, list2);
1005       SELF_CHECK (items_alive == 5);
1006
1007       expected = { &d, &e };
1008       verify_items (list1, expected);
1009
1010       expected = { &a, &b, &c };
1011       verify_items (list2, expected);
1012     }
1013
1014     {
1015       /* Other is empty.  */
1016       ListType list1;
1017       ListType list2;
1018       std::vector<const item_type *> expected;
1019
1020       auto &a = list1.emplace_back ("a");
1021       auto &b = list1.emplace_back ("b");
1022       auto &c = list1.emplace_back ("c");
1023
1024       SELF_CHECK (items_alive == 3);
1025       std::swap (list1, list2);
1026       SELF_CHECK (items_alive == 3);
1027
1028       expected = {};
1029       verify_items (list1, expected);
1030
1031       expected = { &a, &b, &c };
1032       verify_items (list2, expected);
1033     }
1034
1035     {
1036       /* *this is empty.  */
1037       ListType list1;
1038       ListType list2;
1039       std::vector<const item_type *> expected;
1040
1041       auto &a = list2.emplace_back ("a");
1042       auto &b = list2.emplace_back ("b");
1043       auto &c = list2.emplace_back ("c");
1044
1045       SELF_CHECK (items_alive == 3);
1046       std::swap (list1, list2);
1047       SELF_CHECK (items_alive == 3);
1048
1049       expected = { &a, &b, &c };
1050       verify_items (list1, expected);
1051
1052       expected = {};
1053       verify_items (list2, expected);
1054     }
1055
1056     {
1057       /* Both lists empty.  */
1058       ListType list1;
1059       ListType list2;
1060       std::vector<const item_type *> expected;
1061
1062       SELF_CHECK (items_alive == 0);
1063       std::swap (list1, list2);
1064       SELF_CHECK (items_alive == 0);
1065
1066       expected = {};
1067       verify_items (list1, expected);
1068
1069       expected = {};
1070       verify_items (list2, expected);
1071     }
1072
1073     {
1074       /* Swap one element twice.  */
1075       ListType list1;
1076       ListType list2;
1077       std::vector<const item_type *> expected;
1078
1079       auto &a = list1.emplace_back ("a");
1080
1081       SELF_CHECK (items_alive == 1);
1082       std::swap (list1, list2);
1083       SELF_CHECK (items_alive == 1);
1084
1085       expected = {};
1086       verify_items (list1, expected);
1087
1088       expected = { &a };
1089       verify_items (list2, expected);
1090
1091       std::swap (list1, list2);
1092       SELF_CHECK (items_alive == 1);
1093
1094       expected = { &a };
1095       verify_items (list1, expected);
1096
1097       expected = {};
1098       verify_items (list2, expected);
1099     }
1100   }
1101
1102   static void test_front_back ()
1103   {
1104     ListType list;
1105     const ListType &clist = list;
1106
1107     auto &a = list.emplace_back ("a");
1108     list.emplace_back ("b");
1109     auto &c = list.emplace_back ("c");
1110
1111     SELF_CHECK (&list.front () == &a);
1112     SELF_CHECK (&clist.front () == &a);
1113     SELF_CHECK (&list.back () == &c);
1114     SELF_CHECK (&clist.back () == &c);
1115   }
1116
1117   static void test_push_front ()
1118   {
1119     ListType list;
1120     std::vector<const item_type *> expected;
1121
1122     SELF_CHECK (items_alive == 0);
1123     list.push_front (std::make_unique<item_type> ("a"));
1124     auto &a = list.front ();
1125     expected = { &a };
1126     verify_items (list, expected);
1127     SELF_CHECK (items_alive == 1);
1128
1129     list.push_front (std::make_unique<item_type> ("b"));
1130     auto &b = list.front ();
1131     expected = { &b, &a };
1132     verify_items (list, expected);
1133     SELF_CHECK (items_alive == 2);
1134
1135     list.push_front (std::make_unique<item_type> ("c"));
1136     auto &c = list.front ();
1137     expected = { &c, &b, &a };
1138     verify_items (list, expected);
1139     SELF_CHECK (items_alive == 3);
1140   }
1141
1142   static void test_push_back ()
1143   {
1144     ListType list;
1145     std::vector<const item_type *> expected;
1146
1147     SELF_CHECK (items_alive == 0);
1148     list.push_back (std::make_unique<item_type> ("a"));
1149     auto &a = list.back ();
1150     expected = { &a };
1151     verify_items (list, expected);
1152     SELF_CHECK (items_alive == 1);
1153
1154     list.push_back (std::make_unique<item_type> ("b"));
1155     auto &b = list.back ();
1156     expected = { &a, &b };
1157     verify_items (list, expected);
1158     SELF_CHECK (items_alive == 2);
1159
1160     list.push_back (std::make_unique<item_type> ("c"));
1161     auto &c = list.back ();
1162     expected = { &a, &b, &c };
1163     verify_items (list, expected);
1164     SELF_CHECK (items_alive == 3);
1165   }
1166
1167   static void test_insert ()
1168   {
1169     std::vector<const item_type *> expected;
1170
1171     {
1172       /* Insert at beginning.  */
1173       ListType list;
1174
1175       auto &a = *list.insert (list.begin (), std::make_unique<item_type> ("a"));
1176       expected = { &a };
1177       verify_items (list, expected);
1178       SELF_CHECK (items_alive == 1);
1179
1180       auto &b = *list.insert (list.begin (), std::make_unique<item_type> ("b"));
1181       expected = { &b, &a };
1182       verify_items (list, expected);
1183       SELF_CHECK (items_alive == 2);
1184
1185       auto &c = *list.insert (list.begin (), std::make_unique<item_type> ("c"));
1186       expected = { &c, &b, &a };
1187       verify_items (list, expected);
1188       SELF_CHECK (items_alive == 3);
1189     }
1190
1191     {
1192       /* Insert at end.  */
1193       ListType list;
1194
1195       auto &a = *list.insert (list.end (), std::make_unique<item_type> ("a"));
1196       expected = { &a };
1197       verify_items (list, expected);
1198       SELF_CHECK (items_alive == 1);
1199
1200       auto &b = *list.insert (list.end (), std::make_unique<item_type> ("b"));
1201       expected = { &a, &b };
1202       verify_items (list, expected);
1203       SELF_CHECK (items_alive == 2);
1204
1205       auto &c = *list.insert (list.end (), std::make_unique<item_type> ("c"));
1206       expected = { &a, &b, &c };
1207       verify_items (list, expected);
1208       SELF_CHECK (items_alive == 3);
1209     }
1210
1211     {
1212       /* Insert in the middle.  */
1213       ListType list;
1214
1215       auto &a = list.emplace_back ("a");
1216       auto &b = list.emplace_back ("b");
1217
1218       SELF_CHECK (items_alive == 2);
1219       auto &c = *list.insert (list.iterator_to (b),
1220                               std::make_unique<item_type> ("c"));
1221       expected = { &a, &c, &b };
1222       verify_items (list, expected);
1223       SELF_CHECK (items_alive == 3);
1224     }
1225
1226     {
1227       /* Insert in empty list. */
1228       ListType list;
1229
1230       SELF_CHECK (items_alive == 0);
1231       auto &a = *list.insert (list.end (), std::make_unique<item_type> ("a"));
1232       expected = { &a };
1233       verify_items (list, expected);
1234       SELF_CHECK (items_alive == 1);
1235     }
1236   }
1237
1238   static void test_emplace_front ()
1239   {
1240     ListType list;
1241     std::vector<const item_type *> expected;
1242
1243     SELF_CHECK (items_alive == 0);
1244     auto &a = list.emplace_front ("a");
1245     expected = { &a };
1246     verify_items (list, expected);
1247     SELF_CHECK (items_alive == 1);
1248
1249     auto &b = list.emplace_front ("b");
1250     expected = { &b, &a };
1251     verify_items (list, expected);
1252     SELF_CHECK (items_alive == 2);
1253
1254     auto &c = list.emplace_front ("c");
1255     expected = { &c, &b, &a };
1256     verify_items (list, expected);
1257     SELF_CHECK (items_alive == 3);
1258   }
1259
1260   static void test_emplace_back ()
1261   {
1262     ListType list;
1263     std::vector<const item_type *> expected;
1264
1265     SELF_CHECK (items_alive == 0);
1266     auto &a = list.emplace_back ("a");
1267     expected = { &a };
1268     verify_items (list, expected);
1269     SELF_CHECK (items_alive == 1);
1270
1271     auto &b = list.emplace_back ("b");
1272     expected = { &a, &b };
1273     verify_items (list, expected);
1274     SELF_CHECK (items_alive == 2);
1275
1276     auto &c = list.emplace_back ("c");
1277     expected = { &a, &b, &c };
1278     verify_items (list, expected);
1279     SELF_CHECK (items_alive == 3);
1280   }
1281
1282   static void test_emplace ()
1283   {
1284     std::vector<const item_type *> expected;
1285
1286     {
1287       /* Emplace at beginning.  */
1288       ListType list;
1289
1290       auto &a = list.emplace (list.begin (), "a");
1291       expected = { &a };
1292       verify_items (list, expected);
1293       SELF_CHECK (items_alive == 1);
1294
1295       auto &b = list.emplace (list.begin (), "b");
1296       expected = { &b, &a };
1297       verify_items (list, expected);
1298       SELF_CHECK (items_alive == 2);
1299
1300       auto &c = list.emplace (list.begin (), "c");
1301       expected = { &c, &b, &a };
1302       verify_items (list, expected);
1303       SELF_CHECK (items_alive == 3);
1304     }
1305
1306     {
1307       /* Emplace at end.  */
1308       ListType list;
1309
1310       auto &a = list.emplace (list.end (), "a");
1311       expected = { &a };
1312       verify_items (list, expected);
1313       SELF_CHECK (items_alive == 1);
1314
1315       auto &b = list.emplace (list.end (), "b");
1316       expected = { &a, &b };
1317       verify_items (list, expected);
1318       SELF_CHECK (items_alive == 2);
1319
1320       auto &c = list.emplace (list.end (), "c");
1321       expected = { &a, &b, &c };
1322       verify_items (list, expected);
1323       SELF_CHECK (items_alive == 3);
1324     }
1325
1326     {
1327       /* Emplace in the middle.  */
1328       ListType list;
1329
1330       auto &a = list.emplace_back ("a");
1331       auto &b = list.emplace_back ("b");
1332
1333       SELF_CHECK (items_alive == 2);
1334       auto &c = list.emplace (list.iterator_to (b), "c");
1335       expected = { &a, &c, &b };
1336       verify_items (list, expected);
1337       SELF_CHECK (items_alive == 3);
1338     }
1339
1340     {
1341       /* Emplace in empty list. */
1342       ListType list;
1343
1344       SELF_CHECK (items_alive == 0);
1345       auto &a = list.emplace (list.end (), "a");
1346       expected = { &a };
1347       verify_items (list, expected);
1348       SELF_CHECK (items_alive == 1);
1349     }
1350   }
1351
1352   static void test_splice ()
1353   {
1354     {
1355       /* Two non-empty lists.  */
1356       ListType list1;
1357       ListType list2;
1358       std::vector<const item_type *> expected;
1359
1360       auto &a = list1.emplace_back ("a");
1361       auto &b = list1.emplace_back ("b");
1362       auto &c = list1.emplace_back ("c");
1363
1364       auto &d = list2.emplace_back ("d");
1365       auto &e = list2.emplace_back ("e");
1366
1367       SELF_CHECK (items_alive == 5);
1368       list1.splice (std::move (list2));
1369       SELF_CHECK (items_alive == 5);
1370
1371       expected = { &a, &b, &c, &d, &e };
1372       verify_items (list1, expected);
1373
1374       expected = {};
1375       verify_items (list2, expected);
1376     }
1377
1378     {
1379       /* Receiving list empty.  */
1380       ListType list1;
1381       ListType list2;
1382       std::vector<const item_type *> expected;
1383
1384       auto &a = list2.emplace_back ("a");
1385       auto &b = list2.emplace_back ("b");
1386       auto &c = list2.emplace_back ("c");
1387
1388       SELF_CHECK (items_alive == 3);
1389       list1.splice (std::move (list2));
1390       SELF_CHECK (items_alive == 3);
1391
1392       expected = { &a, &b, &c };
1393       verify_items (list1, expected);
1394
1395       expected = {};
1396       verify_items (list2, expected);
1397     }
1398
1399     {
1400       /* Giving list empty.  */
1401       ListType list1;
1402       ListType list2;
1403       std::vector<const item_type *> expected;
1404
1405       auto &a = list1.emplace_back ("a");
1406       auto &b = list1.emplace_back ("b");
1407       auto &c = list1.emplace_back ("c");
1408
1409       SELF_CHECK (items_alive == 3);
1410       list1.splice (std::move (list2));
1411       SELF_CHECK (items_alive == 3);
1412
1413       expected = { &a, &b, &c };
1414       verify_items (list1, expected);
1415
1416       expected = {};
1417       verify_items (list2, expected);
1418     }
1419
1420     {
1421       /* Both lists empty.  */
1422       ListType list1;
1423       ListType list2;
1424       std::vector<const item_type *> expected;
1425
1426       SELF_CHECK (items_alive == 0);
1427       list1.splice (std::move (list2));
1428       SELF_CHECK (items_alive == 0);
1429
1430       expected = {};
1431       verify_items (list1, expected);
1432
1433       expected = {};
1434       verify_items (list2, expected);
1435     }
1436   }
1437
1438   static void test_pop_front ()
1439   {
1440     ListType list;
1441     std::vector<const item_type *> expected;
1442
1443     list.emplace_back ("a");
1444     auto &b = list.emplace_back ("b");
1445     auto &c = list.emplace_back ("c");
1446
1447     SELF_CHECK (items_alive == 3);
1448     list.pop_front ();
1449     expected = { &b, &c };
1450     verify_items (list, expected);
1451     SELF_CHECK (items_alive == 2);
1452
1453     list.pop_front ();
1454     expected = { &c };
1455     verify_items (list, expected);
1456     SELF_CHECK (items_alive == 1);
1457
1458     list.pop_front ();
1459     expected = {};
1460     verify_items (list, expected);
1461     SELF_CHECK (items_alive == 0);
1462   }
1463
1464   static void test_pop_back ()
1465   {
1466     ListType list;
1467     std::vector<const item_type *> expected;
1468
1469     auto &a = list.emplace_back ("a");
1470     auto &b = list.emplace_back ("b");
1471     list.emplace_back ("c");
1472
1473     SELF_CHECK (items_alive == 3);
1474     list.pop_back ();
1475     expected = { &a, &b };
1476     verify_items (list, expected);
1477     SELF_CHECK (items_alive == 2);
1478
1479     list.pop_back ();
1480     expected = { &a };
1481     verify_items (list, expected);
1482     SELF_CHECK (items_alive == 1);
1483
1484     list.pop_back ();
1485     expected = {};
1486     verify_items (list, expected);
1487     SELF_CHECK (items_alive == 0);
1488   }
1489
1490   static void test_release ()
1491   {
1492     ListType list;
1493     std::vector<const item_type *> expected;
1494
1495     auto &a = list.emplace_back ("a");
1496     auto &b = list.emplace_back ("b");
1497     auto &c = list.emplace_back ("c");
1498
1499     {
1500       SELF_CHECK (items_alive == 3);
1501       auto [next_it, released] = list.release (list.iterator_to (b));
1502       SELF_CHECK (&*next_it == &c);
1503       expected = { &a, &c };
1504       verify_items (list, expected);
1505       SELF_CHECK (items_alive == 3);
1506       released.reset ();
1507       SELF_CHECK (items_alive == 2);
1508     }
1509
1510     {
1511       auto [next_it, released] = list.release (list.iterator_to (c));
1512       SELF_CHECK (next_it == list.end ());
1513       expected = { &a };
1514       verify_items (list, expected);
1515       SELF_CHECK (items_alive == 2);
1516       released.reset ();
1517       SELF_CHECK (items_alive == 1);
1518     }
1519
1520     {
1521       auto [next_it, released] = list.release (list.iterator_to (a));
1522       SELF_CHECK (next_it == list.end ());
1523       expected = {};
1524       verify_items (list, expected);
1525       SELF_CHECK (items_alive == 1);
1526       released.reset ();
1527       SELF_CHECK (items_alive == 0);
1528     }
1529   }
1530
1531   static void test_clear ()
1532   {
1533     ListType list;
1534     std::vector<const item_type *> expected;
1535
1536     list.emplace_back ("a");
1537     list.emplace_back ("b");
1538     list.emplace_back ("c");
1539
1540     SELF_CHECK (items_alive == 3);
1541     list.clear ();
1542     expected = {};
1543     verify_items (list, expected);
1544     SELF_CHECK (items_alive == 0);
1545
1546     /* Verify idempotency.  */
1547     list.clear ();
1548     expected = {};
1549     verify_items (list, expected);
1550     SELF_CHECK (items_alive == 0);
1551   }
1552
1553   static void test_empty ()
1554   {
1555     ListType list;
1556
1557     SELF_CHECK (list.empty ());
1558     auto &a = list.emplace_back ("a");
1559     SELF_CHECK (!list.empty ());
1560     list.erase (list.iterator_to (a));
1561     SELF_CHECK (list.empty ());
1562   }
1563
1564   static void test_begin_end ()
1565   {
1566     ListType list;
1567     const ListType &clist = list;
1568
1569     auto &a = list.emplace_back ("a");
1570     list.emplace_back ("b");
1571     auto &c = list.emplace_back ("c");
1572
1573     SELF_CHECK (&*list.begin () == &a);
1574     SELF_CHECK (&*list.cbegin () == &a);
1575     SELF_CHECK (&*clist.begin () == &a);
1576     SELF_CHECK (&*list.rbegin () == &c);
1577     SELF_CHECK (&*list.crbegin () == &c);
1578     SELF_CHECK (&*clist.rbegin () == &c);
1579
1580     /* At least check that they compile.  */
1581     list.end ();
1582     list.cend ();
1583     clist.end ();
1584     list.rend ();
1585     list.crend ();
1586     clist.end ();
1587   }
1588 };
1589
1590 template<typename ListType>
1591 static void
1592 test_owning_intrusive_list_1 ()
1593 {
1594   owning_intrusive_list_test<ListType> tests;
1595
1596   tests.test_move_constructor ();
1597   tests.test_move_assignment ();
1598   tests.test_swap ();
1599   tests.test_front_back ();
1600   tests.test_push_front ();
1601   tests.test_push_back ();
1602   tests.test_insert ();
1603   tests.test_emplace_front ();
1604   tests.test_emplace_back ();
1605   tests.test_emplace ();
1606   tests.test_splice ();
1607   tests.test_pop_front ();
1608   tests.test_pop_back ();
1609   tests.test_release ();
1610   tests.test_clear ();
1611   tests.test_empty ();
1612   tests.test_begin_end ();
1613 }
1614
1615 static void
1616 test_node_is_linked ()
1617 {
1618   {
1619     item_with_base a ("a");
1620     item_with_base_list list;
1621
1622     SELF_CHECK (!a.is_linked ());
1623     list.push_back (a);
1624     SELF_CHECK (a.is_linked ());
1625     list.pop_back ();
1626     SELF_CHECK (!a.is_linked ());
1627   }
1628
1629   {
1630     item_with_member a ("a");
1631     item_with_member_list list;
1632
1633     SELF_CHECK (!a.node.is_linked ());
1634     list.push_back (a);
1635     SELF_CHECK (a.node.is_linked ());
1636     list.pop_back ();
1637     SELF_CHECK (!a.node.is_linked ());
1638   }
1639 }
1640
1641 static void
1642 test_intrusive_list ()
1643 {
1644   test_intrusive_list_1<item_with_base_list> ();
1645   test_intrusive_list_1<item_with_member_list> ();
1646   test_owning_intrusive_list_1<item_with_base_owning_list> ();
1647   test_owning_intrusive_list_1<item_with_member_owning_list> ();
1648   test_node_is_linked ();
1649 }
1650
1651 void _initialize_intrusive_list_selftests ();
1652
1653 void
1654 _initialize_intrusive_list_selftests ()
1655 {
1656   selftests::register_test ("intrusive_list", test_intrusive_list);
1657 }