llvm/unittests/ADT/IListBaseTest.cpp

   1 //===- unittests/ADT/IListBaseTest.cpp - ilist_base unit tests ------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/ilist_base.h"
  10 #include "gtest/gtest.h"
  11
  12 using namespace llvm;
  13
  14 namespace {
  15
  16 // Test fixture.
  17 template <typename T> class IListBaseTest : public ::testing::Test {};
  18
  19 class Parent;
  20
  21 // Test variants with the same test.
  22 typedef ::testing::Types<ilist_base<false, void>, ilist_base<true, void>, ilist_base<false, Parent*>, ilist_base<true, Parent*>>
  23     IListBaseTestTypes;
  24 TYPED_TEST_SUITE(IListBaseTest, IListBaseTestTypes, );
  25
  26 TYPED_TEST(IListBaseTest, insertBeforeImpl) {
  27   typedef TypeParam list_base_type;
  28   typedef typename list_base_type::node_base_type node_base_type;
  29
  30   node_base_type S, A, B;
  31
  32   // [S] <-> [S]
  33   S.setPrev(&S);
  34   S.setNext(&S);
  35
  36   // [S] <-> A <-> [S]
  37   list_base_type::insertBeforeImpl(S, A);
  38   EXPECT_EQ(&A, S.getPrev());
  39   EXPECT_EQ(&S, A.getPrev());
  40   EXPECT_EQ(&A, S.getNext());
  41   EXPECT_EQ(&S, A.getNext());
  42
  43   // [S] <-> A <-> B <-> [S]
  44   list_base_type::insertBeforeImpl(S, B);
  45   EXPECT_EQ(&B, S.getPrev());
  46   EXPECT_EQ(&A, B.getPrev());
  47   EXPECT_EQ(&S, A.getPrev());
  48   EXPECT_EQ(&A, S.getNext());
  49   EXPECT_EQ(&B, A.getNext());
  50   EXPECT_EQ(&S, B.getNext());
  51 }
  52
  53 TYPED_TEST(IListBaseTest, removeImpl) {
  54   typedef TypeParam list_base_type;
  55   typedef typename list_base_type::node_base_type node_base_type;
  56
  57   node_base_type S, A, B;
  58
  59   // [S] <-> A <-> B <-> [S]
  60   S.setPrev(&S);
  61   S.setNext(&S);
  62   list_base_type::insertBeforeImpl(S, A);
  63   list_base_type::insertBeforeImpl(S, B);
  64
  65   // [S] <-> B <-> [S]
  66   list_base_type::removeImpl(A);
  67   EXPECT_EQ(&B, S.getPrev());
  68   EXPECT_EQ(&S, B.getPrev());
  69   EXPECT_EQ(&B, S.getNext());
  70   EXPECT_EQ(&S, B.getNext());
  71   EXPECT_EQ(nullptr, A.getPrev());
  72   EXPECT_EQ(nullptr, A.getNext());
  73
  74   // [S] <-> [S]
  75   list_base_type::removeImpl(B);
  76   EXPECT_EQ(&S, S.getPrev());
  77   EXPECT_EQ(&S, S.getNext());
  78   EXPECT_EQ(nullptr, B.getPrev());
  79   EXPECT_EQ(nullptr, B.getNext());
  80 }
  81
  82 TYPED_TEST(IListBaseTest, removeRangeImpl) {
  83   typedef TypeParam list_base_type;
  84   typedef typename list_base_type::node_base_type node_base_type;
  85
  86   node_base_type S, A, B, C, D;
  87
  88   // [S] <-> A <-> B <-> C <-> D <-> [S]
  89   S.setPrev(&S);
  90   S.setNext(&S);
  91   list_base_type::insertBeforeImpl(S, A);
  92   list_base_type::insertBeforeImpl(S, B);
  93   list_base_type::insertBeforeImpl(S, C);
  94   list_base_type::insertBeforeImpl(S, D);
  95
  96   // [S] <-> A <-> D <-> [S]
  97   list_base_type::removeRangeImpl(B, D);
  98   EXPECT_EQ(&D, S.getPrev());
  99   EXPECT_EQ(&A, D.getPrev());
 100   EXPECT_EQ(&S, A.getPrev());
 101   EXPECT_EQ(&A, S.getNext());
 102   EXPECT_EQ(&D, A.getNext());
 103   EXPECT_EQ(&S, D.getNext());
 104   EXPECT_EQ(nullptr, B.getPrev());
 105   EXPECT_EQ(nullptr, C.getNext());
 106 }
 107
 108 TYPED_TEST(IListBaseTest, removeRangeImplAllButSentinel) {
 109   typedef TypeParam list_base_type;
 110   typedef typename list_base_type::node_base_type node_base_type;
 111
 112   node_base_type S, A, B;
 113
 114   // [S] <-> A <-> B <-> [S]
 115   S.setPrev(&S);
 116   S.setNext(&S);
 117   list_base_type::insertBeforeImpl(S, A);
 118   list_base_type::insertBeforeImpl(S, B);
 119
 120   // [S] <-> [S]
 121   list_base_type::removeRangeImpl(A, S);
 122   EXPECT_EQ(&S, S.getPrev());
 123   EXPECT_EQ(&S, S.getNext());
 124   EXPECT_EQ(nullptr, A.getPrev());
 125   EXPECT_EQ(nullptr, B.getNext());
 126 }
 127
 128 TYPED_TEST(IListBaseTest, transferBeforeImpl) {
 129   typedef TypeParam list_base_type;
 130   typedef typename list_base_type::node_base_type node_base_type;
 131
 132   node_base_type S1, S2, A, B, C, D, E;
 133
 134   // [S1] <-> A <-> B <-> C <-> [S1]
 135   S1.setPrev(&S1);
 136   S1.setNext(&S1);
 137   list_base_type::insertBeforeImpl(S1, A);
 138   list_base_type::insertBeforeImpl(S1, B);
 139   list_base_type::insertBeforeImpl(S1, C);
 140
 141   // [S2] <-> D <-> E <-> [S2]
 142   S2.setPrev(&S2);
 143   S2.setNext(&S2);
 144   list_base_type::insertBeforeImpl(S2, D);
 145   list_base_type::insertBeforeImpl(S2, E);
 146
 147   // [S1] <-> C <-> [S1]
 148   list_base_type::transferBeforeImpl(D, A, C);
 149   EXPECT_EQ(&C, S1.getPrev());
 150   EXPECT_EQ(&S1, C.getPrev());
 151   EXPECT_EQ(&C, S1.getNext());
 152   EXPECT_EQ(&S1, C.getNext());
 153
 154   // [S2] <-> A <-> B <-> D <-> E <-> [S2]
 155   EXPECT_EQ(&E, S2.getPrev());
 156   EXPECT_EQ(&D, E.getPrev());
 157   EXPECT_EQ(&B, D.getPrev());
 158   EXPECT_EQ(&A, B.getPrev());
 159   EXPECT_EQ(&S2, A.getPrev());
 160   EXPECT_EQ(&A, S2.getNext());
 161   EXPECT_EQ(&B, A.getNext());
 162   EXPECT_EQ(&D, B.getNext());
 163   EXPECT_EQ(&E, D.getNext());
 164   EXPECT_EQ(&S2, E.getNext());
 165 }
 166
 167 } // end namespace