gdb/unittests/intrusive_list-selftests.c

   1 /* Tests fpr intrusive double linked list for GDB, the GNU debugger.
   2    Copyright (C) 2021-2022 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 #include "defs.h"
  20
  21 #include "gdbsupport/intrusive_list.h"
  22 #include "gdbsupport/selftest.h"
  23 #include <unordered_set>
  24
  25 /* An item type using intrusive_list_node by inheriting from it and its
  26    corresponding list type.  Put another base before intrusive_list_node
  27    so that a pointer to the node != a pointer to the item.  */
  28
  29 struct other_base
  30 {
  31   int n = 1;
  32 };
  33
  34 struct item_with_base : public other_base,
  35                         public intrusive_list_node<item_with_base>
  36 {
  37   explicit item_with_base (const char *name)
  38     : name (name)
  39   {}
  40
  41   const char *const name;
  42 };
  43
  44 using item_with_base_list = intrusive_list<item_with_base>;
  45
  46 /* An item type using intrusive_list_node as a field and its corresponding
  47    list type.  Put the other field before the node, so that a pointer to the
  48    node != a pointer to the item.  */
  49
  50 struct item_with_member
  51 {
  52   explicit item_with_member (const char *name)
  53     : name (name)
  54   {}
  55
  56   const char *const name;
  57   intrusive_list_node<item_with_member> node;
  58 };
  59
  60 using item_with_member_node
  61   = intrusive_member_node<item_with_member, &item_with_member::node>;
  62 using item_with_member_list
  63   = intrusive_list<item_with_member, item_with_member_node>;
  64
  65 /* To run all tests using both the base and member methods, all tests are
  66    declared in this templated class, which is instantiated once for each
  67    list type.  */
  68
  69 template <typename ListType>
  70 struct intrusive_list_test
  71 {
  72   using item_type = typename ListType::value_type;
  73
  74   /* Verify that LIST contains exactly the items in EXPECTED.
  75
  76      Traverse the list forward and backwards to exercise all links.  */
  77
  78   static void
  79   verify_items (const ListType &list,
  80                 gdb::array_view<const typename ListType::value_type *> expected)
  81   {
  82     int i = 0;
  83
  84     for (typename ListType::iterator it = list.begin ();
  85          it != list.end ();
  86          ++it)
  87       {
  88         const item_type &item = *it;
  89
  90         gdb_assert (i < expected.size ());
  91         gdb_assert (&item == expected[i]);
  92
  93         ++i;
  94       }
  95
  96     gdb_assert (i == expected.size ());
  97
  98     for (typename ListType::reverse_iterator it = list.rbegin ();
  99          it != list.rend ();
 100          ++it)
 101       {
 102         const item_type &item = *it;
 103
 104         --i;
 105
 106         gdb_assert (i >= 0);
 107         gdb_assert (&item == expected[i]);
 108       }
 109
 110     gdb_assert (i == 0);
 111   }
 112
 113   static void
 114   test_move_constructor ()
 115   {
 116     {
 117       /* Other list is not empty.  */
 118       item_type a ("a"), b ("b"), c ("c");
 119       ListType list1;
 120       std::vector<const item_type *> expected;
 121
 122       list1.push_back (a);
 123       list1.push_back (b);
 124       list1.push_back (c);
 125
 126       ListType list2 (std::move (list1));
 127
 128       expected = {};
 129       verify_items (list1, expected);
 130
 131       expected = {&a, &b, &c};
 132       verify_items (list2, expected);
 133     }
 134
 135     {
 136       /* Other list contains 1 element.  */
 137       item_type a ("a");
 138       ListType list1;
 139       std::vector<const item_type *> expected;
 140
 141       list1.push_back (a);
 142
 143       ListType list2 (std::move (list1));
 144
 145       expected = {};
 146       verify_items (list1, expected);
 147
 148       expected = {&a};
 149       verify_items (list2, expected);
 150     }
 151
 152     {
 153       /* Other list is empty.  */
 154       ListType list1;
 155       std::vector<const item_type *> expected;
 156
 157       ListType list2 (std::move (list1));
 158
 159       expected = {};
 160       verify_items (list1, expected);
 161
 162       expected = {};
 163       verify_items (list2, expected);
 164     }
 165   }
 166
 167   static void
 168   test_move_assignment ()
 169   {
 170     {
 171       /* Both lists are not empty.  */
 172       item_type a ("a"), b ("b"), c ("c"), d ("d"), e ("e");
 173       ListType list1;
 174       ListType list2;
 175       std::vector<const item_type *> expected;
 176
 177       list1.push_back (a);
 178       list1.push_back (b);
 179       list1.push_back (c);
 180
 181       list2.push_back (d);
 182       list2.push_back (e);
 183
 184       list2 = std::move (list1);
 185
 186       expected = {};
 187       verify_items (list1, expected);
 188
 189       expected = {&a, &b, &c};
 190       verify_items (list2, expected);
 191     }
 192
 193     {
 194       /* rhs list is empty.  */
 195       item_type a ("a"), b ("b"), c ("c");
 196       ListType list1;
 197       ListType list2;
 198       std::vector<const item_type *> expected;
 199
 200       list2.push_back (a);
 201       list2.push_back (b);
 202       list2.push_back (c);
 203
 204       list2 = std::move (list1);
 205
 206       expected = {};
 207       verify_items (list1, expected);
 208
 209       expected = {};
 210       verify_items (list2, expected);
 211     }
 212
 213     {
 214       /* lhs list is empty.  */
 215       item_type a ("a"), b ("b"), c ("c");
 216       ListType list1;
 217       ListType list2;
 218       std::vector<const item_type *> expected;
 219
 220       list1.push_back (a);
 221       list1.push_back (b);
 222       list1.push_back (c);
 223
 224       list2 = std::move (list1);
 225
 226       expected = {};
 227       verify_items (list1, expected);
 228
 229       expected = {&a, &b, &c};
 230       verify_items (list2, expected);
 231     }
 232
 233     {
 234       /* Both lists contain 1 item.  */
 235       item_type a ("a"), b ("b");
 236       ListType list1;
 237       ListType list2;
 238       std::vector<const item_type *> expected;
 239
 240       list1.push_back (a);
 241       list2.push_back (b);
 242
 243       list2 = std::move (list1);
 244
 245       expected = {};
 246       verify_items (list1, expected);
 247
 248       expected = {&a};
 249       verify_items (list2, expected);
 250     }
 251
 252     {
 253       /* Both lists are empty.  */
 254       ListType list1;
 255       ListType list2;
 256       std::vector<const item_type *> expected;
 257
 258       list2 = std::move (list1);
 259
 260       expected = {};
 261       verify_items (list1, expected);
 262
 263       expected = {};
 264       verify_items (list2, expected);
 265     }
 266   }
 267
 268   static void
 269   test_swap ()
 270   {
 271     {
 272       /* Two non-empty lists.  */
 273       item_type a ("a"), b ("b"), c ("c"), d ("d"), e ("e");
 274       ListType list1;
 275       ListType list2;
 276       std::vector<const item_type *> expected;
 277
 278       list1.push_back (a);
 279       list1.push_back (b);
 280       list1.push_back (c);
 281
 282       list2.push_back (d);
 283       list2.push_back (e);
 284
 285       std::swap (list1, list2);
 286
 287       expected = {&d, &e};
 288       verify_items (list1, expected);
 289
 290       expected = {&a, &b, &c};
 291       verify_items (list2, expected);
 292     }
 293
 294     {
 295       /* Other is empty.  */
 296       item_type a ("a"), b ("b"), c ("c");
 297       ListType list1;
 298       ListType list2;
 299       std::vector<const item_type *> expected;
 300
 301       list1.push_back (a);
 302       list1.push_back (b);
 303       list1.push_back (c);
 304
 305       std::swap (list1, list2);
 306
 307       expected = {};
 308       verify_items (list1, expected);
 309
 310       expected = {&a, &b, &c};
 311       verify_items (list2, expected);
 312     }
 313
 314     {
 315       /* *this is empty.  */
 316       item_type a ("a"), b ("b"), c ("c");
 317       ListType list1;
 318       ListType list2;
 319       std::vector<const item_type *> expected;
 320
 321       list2.push_back (a);
 322       list2.push_back (b);
 323       list2.push_back (c);
 324
 325       std::swap (list1, list2);
 326
 327       expected = {&a, &b, &c};
 328       verify_items (list1, expected);
 329
 330       expected = {};
 331       verify_items (list2, expected);
 332     }
 333
 334     {
 335       /* Both lists empty.  */
 336       ListType list1;
 337       ListType list2;
 338       std::vector<const item_type *> expected;
 339
 340       std::swap (list1, list2);
 341
 342       expected = {};
 343       verify_items (list1, expected);
 344
 345       expected = {};
 346       verify_items (list2, expected);
 347     }
 348
 349     {
 350       /* Swap one element twice.  */
 351       item_type a ("a");
 352       ListType list1;
 353       ListType list2;
 354       std::vector<const item_type *> expected;
 355
 356       list1.push_back (a);
 357
 358       std::swap (list1, list2);
 359
 360       expected = {};
 361       verify_items (list1, expected);
 362
 363       expected = {&a};
 364       verify_items (list2, expected);
 365
 366       std::swap (list1, list2);
 367
 368       expected = {&a};
 369       verify_items (list1, expected);
 370
 371       expected = {};
 372       verify_items (list2, expected);
 373     }
 374   }
 375
 376   static void
 377   test_front_back ()
 378   {
 379     item_type a ("a"), b ("b"), c ("c");
 380     ListType list;
 381     const ListType &clist = list;
 382
 383     list.push_back (a);
 384     list.push_back (b);
 385     list.push_back (c);
 386
 387     gdb_assert (&list.front () == &a);
 388     gdb_assert (&clist.front () == &a);
 389     gdb_assert (&list.back () == &c);
 390     gdb_assert (&clist.back () == &c);
 391   }
 392
 393   static void
 394   test_push_front ()
 395   {
 396     item_type a ("a"), b ("b"), c ("c");
 397     ListType list;
 398     std::vector<const item_type *> expected;
 399
 400     expected = {};
 401     verify_items (list, expected);
 402
 403     list.push_front (a);
 404     expected = {&a};
 405     verify_items (list, expected);
 406
 407     list.push_front (b);
 408     expected = {&b, &a};
 409     verify_items (list, expected);
 410
 411     list.push_front (c);
 412     expected = {&c, &b, &a};
 413     verify_items (list, expected);
 414   }
 415
 416   static void
 417   test_push_back ()
 418   {
 419     item_type a ("a"), b ("b"), c ("c");
 420     ListType list;
 421     std::vector<const item_type *> expected;
 422
 423     expected = {};
 424     verify_items (list, expected);
 425
 426     list.push_back (a);
 427     expected = {&a};
 428     verify_items (list, expected);
 429
 430     list.push_back (b);
 431     expected = {&a, &b};
 432     verify_items (list, expected);
 433
 434     list.push_back (c);
 435     expected = {&a, &b, &c};
 436     verify_items (list, expected);
 437   }
 438
 439   static void
 440   test_insert ()
 441   {
 442     std::vector<const item_type *> expected;
 443
 444     {
 445       /* Insert at beginning.  */
 446       item_type a ("a"), b ("b"), c ("c");
 447       ListType list;
 448
 449
 450       list.insert (list.begin (), a);
 451       expected = {&a};
 452       verify_items (list, expected);
 453
 454       list.insert (list.begin (), b);
 455       expected = {&b, &a};
 456       verify_items (list, expected);
 457
 458       list.insert (list.begin (), c);
 459       expected = {&c, &b, &a};
 460       verify_items (list, expected);
 461     }
 462
 463     {
 464       /* Insert at end.  */
 465       item_type a ("a"), b ("b"), c ("c");
 466       ListType list;
 467
 468
 469       list.insert (list.end (), a);
 470       expected = {&a};
 471       verify_items (list, expected);
 472
 473       list.insert (list.end (), b);
 474       expected = {&a, &b};
 475       verify_items (list, expected);
 476
 477       list.insert (list.end (), c);
 478       expected = {&a, &b, &c};
 479       verify_items (list, expected);
 480     }
 481
 482     {
 483       /* Insert in the middle.  */
 484       item_type a ("a"), b ("b"), c ("c");
 485       ListType list;
 486
 487       list.push_back (a);
 488       list.push_back (b);
 489
 490       list.insert (list.iterator_to (b), c);
 491       expected = {&a, &c, &b};
 492       verify_items (list, expected);
 493     }
 494
 495     {
 496       /* Insert in empty list. */
 497       item_type a ("a");
 498       ListType list;
 499
 500       list.insert (list.end (), a);
 501       expected = {&a};
 502       verify_items (list, expected);
 503     }
 504   }
 505
 506   static void
 507   test_splice ()
 508   {
 509     {
 510       /* Two non-empty lists.  */
 511       item_type a ("a"), b ("b"), c ("c"), d ("d"), e ("e");
 512       ListType list1;
 513       ListType list2;
 514       std::vector<const item_type *> expected;
 515
 516       list1.push_back (a);
 517       list1.push_back (b);
 518       list1.push_back (c);
 519
 520       list2.push_back (d);
 521       list2.push_back (e);
 522
 523       list1.splice (std::move (list2));
 524
 525       expected = {&a, &b, &c, &d, &e};
 526       verify_items (list1, expected);
 527
 528       expected = {};
 529       verify_items (list2, expected);
 530     }
 531
 532     {
 533       /* Receiving list empty.  */
 534       item_type a ("a"), b ("b"), c ("c");
 535       ListType list1;
 536       ListType list2;
 537       std::vector<const item_type *> expected;
 538
 539       list2.push_back (a);
 540       list2.push_back (b);
 541       list2.push_back (c);
 542
 543       list1.splice (std::move (list2));
 544
 545       expected = {&a, &b, &c};
 546       verify_items (list1, expected);
 547
 548       expected = {};
 549       verify_items (list2, expected);
 550     }
 551
 552     {
 553       /* Giving list empty.  */
 554       item_type a ("a"), b ("b"), c ("c");
 555       ListType list1;
 556       ListType list2;
 557       std::vector<const item_type *> expected;
 558
 559       list1.push_back (a);
 560       list1.push_back (b);
 561       list1.push_back (c);
 562
 563       list1.splice (std::move (list2));
 564
 565       expected = {&a, &b, &c};
 566       verify_items (list1, expected);
 567
 568       expected = {};
 569       verify_items (list2, expected);
 570     }
 571
 572     {
 573       /* Both lists empty.  */
 574       item_type a ("a"), b ("b"), c ("c");
 575       ListType list1;
 576       ListType list2;
 577       std::vector<const item_type *> expected;
 578
 579       list1.splice (std::move (list2));
 580
 581       expected = {};
 582       verify_items (list1, expected);
 583
 584       expected = {};
 585       verify_items (list2, expected);
 586     }
 587   }
 588
 589   static void
 590   test_pop_front ()
 591   {
 592     item_type a ("a"), b ("b"), c ("c");
 593     ListType list;
 594     std::vector<const item_type *> expected;
 595
 596     list.push_back (a);
 597     list.push_back (b);
 598     list.push_back (c);
 599
 600     list.pop_front ();
 601     expected = {&b, &c};
 602     verify_items (list, expected);
 603
 604     list.pop_front ();
 605     expected = {&c};
 606     verify_items (list, expected);
 607
 608     list.pop_front ();
 609     expected = {};
 610     verify_items (list, expected);
 611   }
 612
 613   static void
 614   test_pop_back ()
 615   {
 616     item_type a ("a"), b ("b"), c ("c");
 617     ListType list;
 618     std::vector<const item_type *> expected;
 619
 620     list.push_back (a);
 621     list.push_back (b);
 622     list.push_back (c);
 623
 624     list.pop_back();
 625     expected = {&a, &b};
 626     verify_items (list, expected);
 627
 628     list.pop_back ();
 629     expected = {&a};
 630     verify_items (list, expected);
 631
 632     list.pop_back ();
 633     expected = {};
 634     verify_items (list, expected);
 635   }
 636
 637   static void
 638   test_erase ()
 639   {
 640     item_type a ("a"), b ("b"), c ("c");
 641     ListType list;
 642     std::vector<const item_type *> expected;
 643
 644     list.push_back (a);
 645     list.push_back (b);
 646     list.push_back (c);
 647
 648     list.erase (list.iterator_to (b));
 649     expected = {&a, &c};
 650     verify_items (list, expected);
 651
 652     list.erase (list.iterator_to (c));
 653     expected = {&a};
 654     verify_items (list, expected);
 655
 656     list.erase (list.iterator_to (a));
 657     expected = {};
 658     verify_items (list, expected);
 659   }
 660
 661   static void
 662   test_clear ()
 663   {
 664     item_type a ("a"), b ("b"), c ("c");
 665     ListType list;
 666     std::vector<const item_type *> expected;
 667
 668     list.push_back (a);
 669     list.push_back (b);
 670     list.push_back (c);
 671
 672     list.clear ();
 673     expected = {};
 674     verify_items (list, expected);
 675
 676     /* Verify idempotency.  */
 677     list.clear ();
 678     expected = {};
 679     verify_items (list, expected);
 680   }
 681
 682   static void
 683   test_clear_and_dispose ()
 684   {
 685     item_type a ("a"), b ("b"), c ("c");
 686     ListType list;
 687     std::vector<const item_type *> expected;
 688     std::unordered_set<const item_type *> disposer_seen;
 689     int disposer_calls = 0;
 690
 691     list.push_back (a);
 692     list.push_back (b);
 693     list.push_back (c);
 694
 695     auto disposer = [&] (const item_type *item)
 696       {
 697         disposer_seen.insert (item);
 698         disposer_calls++;
 699       };
 700     list.clear_and_dispose (disposer);
 701
 702     expected = {};
 703     verify_items (list, expected);
 704     gdb_assert (disposer_calls == 3);
 705     gdb_assert (disposer_seen.find (&a) != disposer_seen.end ());
 706     gdb_assert (disposer_seen.find (&b) != disposer_seen.end ());
 707     gdb_assert (disposer_seen.find (&c) != disposer_seen.end ());
 708
 709     /* Verify idempotency.  */
 710     list.clear_and_dispose (disposer);
 711     gdb_assert (disposer_calls == 3);
 712   }
 713
 714   static void
 715   test_empty ()
 716   {
 717     item_type a ("a");
 718     ListType list;
 719
 720     gdb_assert (list.empty ());
 721     list.push_back (a);
 722     gdb_assert (!list.empty ());
 723     list.erase (list.iterator_to (a));
 724     gdb_assert (list.empty ());
 725   }
 726
 727   static void
 728   test_begin_end ()
 729   {
 730     item_type a ("a"), b ("b"), c ("c");
 731     ListType list;
 732     const ListType &clist = list;
 733
 734     list.push_back (a);
 735     list.push_back (b);
 736     list.push_back (c);
 737
 738     gdb_assert (&*list.begin () == &a);
 739     gdb_assert (&*list.cbegin () == &a);
 740     gdb_assert (&*clist.begin () == &a);
 741     gdb_assert (&*list.rbegin () == &c);
 742     gdb_assert (&*list.crbegin () == &c);
 743     gdb_assert (&*clist.rbegin () == &c);
 744
 745     /* At least check that they compile.  */
 746     list.end ();
 747     list.cend ();
 748     clist.end ();
 749     list.rend ();
 750     list.crend ();
 751     clist.end ();
 752   }
 753 };
 754
 755 template <typename ListType>
 756 static void
 757 test_intrusive_list_1 ()
 758 {
 759   intrusive_list_test<ListType> tests;
 760
 761   tests.test_move_constructor ();
 762   tests.test_move_assignment ();
 763   tests.test_swap ();
 764   tests.test_front_back ();
 765   tests.test_push_front ();
 766   tests.test_push_back ();
 767   tests.test_insert ();
 768   tests.test_splice ();
 769   tests.test_pop_front ();
 770   tests.test_pop_back ();
 771   tests.test_erase ();
 772   tests.test_clear ();
 773   tests.test_clear_and_dispose ();
 774   tests.test_empty ();
 775   tests.test_begin_end ();
 776 }
 777
 778 static void
 779 test_node_is_linked ()
 780 {
 781   {
 782     item_with_base a ("a");
 783     item_with_base_list list;
 784
 785     gdb_assert (!a.is_linked ());
 786     list.push_back (a);
 787     gdb_assert (a.is_linked ());
 788     list.pop_back ();
 789     gdb_assert (!a.is_linked ());
 790   }
 791
 792   {
 793     item_with_member a ("a");
 794     item_with_member_list list;
 795
 796     gdb_assert (!a.node.is_linked ());
 797     list.push_back (a);
 798     gdb_assert (a.node.is_linked ());
 799     list.pop_back ();
 800     gdb_assert (!a.node.is_linked ());
 801   }
 802 }
 803
 804 static void
 805 test_intrusive_list ()
 806 {
 807   test_intrusive_list_1<item_with_base_list> ();
 808   test_intrusive_list_1<item_with_member_list> ();
 809   test_node_is_linked ();
 810 }
 811
 812 void _initialize_intrusive_list_selftests ();
 813 void
 814 _initialize_intrusive_list_selftests ()
 815 {
 816   selftests::register_test
 817     ("intrusive_list", test_intrusive_list);
 818 }