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 // Test variants with the same test. 20 typedef ::testing::Types<ilist_base<false>, ilist_base<true>> 21 IListBaseTestTypes; 22 TYPED_TEST_SUITE(IListBaseTest, IListBaseTestTypes, ); 23 24 TYPED_TEST(IListBaseTest, insertBeforeImpl) { 25 typedef TypeParam list_base_type; 26 typedef typename list_base_type::node_base_type node_base_type; 27 28 node_base_type S, A, B; 29 30 // [S] <-> [S] 31 S.setPrev(&S); 32 S.setNext(&S); 33 34 // [S] <-> A <-> [S] 35 list_base_type::insertBeforeImpl(S, A); 36 EXPECT_EQ(&A, S.getPrev()); 37 EXPECT_EQ(&S, A.getPrev()); 38 EXPECT_EQ(&A, S.getNext()); 39 EXPECT_EQ(&S, A.getNext()); 40 41 // [S] <-> A <-> B <-> [S] 42 list_base_type::insertBeforeImpl(S, B); 43 EXPECT_EQ(&B, S.getPrev()); 44 EXPECT_EQ(&A, B.getPrev()); 45 EXPECT_EQ(&S, A.getPrev()); 46 EXPECT_EQ(&A, S.getNext()); 47 EXPECT_EQ(&B, A.getNext()); 48 EXPECT_EQ(&S, B.getNext()); 49 } 50 51 TYPED_TEST(IListBaseTest, removeImpl) { 52 typedef TypeParam list_base_type; 53 typedef typename list_base_type::node_base_type node_base_type; 54 55 node_base_type S, A, B; 56 57 // [S] <-> A <-> B <-> [S] 58 S.setPrev(&S); 59 S.setNext(&S); 60 list_base_type::insertBeforeImpl(S, A); 61 list_base_type::insertBeforeImpl(S, B); 62 63 // [S] <-> B <-> [S] 64 list_base_type::removeImpl(A); 65 EXPECT_EQ(&B, S.getPrev()); 66 EXPECT_EQ(&S, B.getPrev()); 67 EXPECT_EQ(&B, S.getNext()); 68 EXPECT_EQ(&S, B.getNext()); 69 EXPECT_EQ(nullptr, A.getPrev()); 70 EXPECT_EQ(nullptr, A.getNext()); 71 72 // [S] <-> [S] 73 list_base_type::removeImpl(B); 74 EXPECT_EQ(&S, S.getPrev()); 75 EXPECT_EQ(&S, S.getNext()); 76 EXPECT_EQ(nullptr, B.getPrev()); 77 EXPECT_EQ(nullptr, B.getNext()); 78 } 79 80 TYPED_TEST(IListBaseTest, removeRangeImpl) { 81 typedef TypeParam list_base_type; 82 typedef typename list_base_type::node_base_type node_base_type; 83 84 node_base_type S, A, B, C, D; 85 86 // [S] <-> A <-> B <-> C <-> D <-> [S] 87 S.setPrev(&S); 88 S.setNext(&S); 89 list_base_type::insertBeforeImpl(S, A); 90 list_base_type::insertBeforeImpl(S, B); 91 list_base_type::insertBeforeImpl(S, C); 92 list_base_type::insertBeforeImpl(S, D); 93 94 // [S] <-> A <-> D <-> [S] 95 list_base_type::removeRangeImpl(B, D); 96 EXPECT_EQ(&D, S.getPrev()); 97 EXPECT_EQ(&A, D.getPrev()); 98 EXPECT_EQ(&S, A.getPrev()); 99 EXPECT_EQ(&A, S.getNext()); 100 EXPECT_EQ(&D, A.getNext()); 101 EXPECT_EQ(&S, D.getNext()); 102 EXPECT_EQ(nullptr, B.getPrev()); 103 EXPECT_EQ(nullptr, C.getNext()); 104 } 105 106 TYPED_TEST(IListBaseTest, removeRangeImplAllButSentinel) { 107 typedef TypeParam list_base_type; 108 typedef typename list_base_type::node_base_type node_base_type; 109 110 node_base_type S, A, B; 111 112 // [S] <-> A <-> B <-> [S] 113 S.setPrev(&S); 114 S.setNext(&S); 115 list_base_type::insertBeforeImpl(S, A); 116 list_base_type::insertBeforeImpl(S, B); 117 118 // [S] <-> [S] 119 list_base_type::removeRangeImpl(A, S); 120 EXPECT_EQ(&S, S.getPrev()); 121 EXPECT_EQ(&S, S.getNext()); 122 EXPECT_EQ(nullptr, A.getPrev()); 123 EXPECT_EQ(nullptr, B.getNext()); 124 } 125 126 TYPED_TEST(IListBaseTest, transferBeforeImpl) { 127 typedef TypeParam list_base_type; 128 typedef typename list_base_type::node_base_type node_base_type; 129 130 node_base_type S1, S2, A, B, C, D, E; 131 132 // [S1] <-> A <-> B <-> C <-> [S1] 133 S1.setPrev(&S1); 134 S1.setNext(&S1); 135 list_base_type::insertBeforeImpl(S1, A); 136 list_base_type::insertBeforeImpl(S1, B); 137 list_base_type::insertBeforeImpl(S1, C); 138 139 // [S2] <-> D <-> E <-> [S2] 140 S2.setPrev(&S2); 141 S2.setNext(&S2); 142 list_base_type::insertBeforeImpl(S2, D); 143 list_base_type::insertBeforeImpl(S2, E); 144 145 // [S1] <-> C <-> [S1] 146 list_base_type::transferBeforeImpl(D, A, C); 147 EXPECT_EQ(&C, S1.getPrev()); 148 EXPECT_EQ(&S1, C.getPrev()); 149 EXPECT_EQ(&C, S1.getNext()); 150 EXPECT_EQ(&S1, C.getNext()); 151 152 // [S2] <-> A <-> B <-> D <-> E <-> [S2] 153 EXPECT_EQ(&E, S2.getPrev()); 154 EXPECT_EQ(&D, E.getPrev()); 155 EXPECT_EQ(&B, D.getPrev()); 156 EXPECT_EQ(&A, B.getPrev()); 157 EXPECT_EQ(&S2, A.getPrev()); 158 EXPECT_EQ(&A, S2.getNext()); 159 EXPECT_EQ(&B, A.getNext()); 160 EXPECT_EQ(&D, B.getNext()); 161 EXPECT_EQ(&E, D.getNext()); 162 EXPECT_EQ(&S2, E.getNext()); 163 } 164 165 } // end namespace 166