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
TYPED_TEST(IListBaseTest,insertBeforeImpl)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
TYPED_TEST(IListBaseTest,removeImpl)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
TYPED_TEST(IListBaseTest,removeRangeImpl)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
TYPED_TEST(IListBaseTest,removeRangeImplAllButSentinel)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
TYPED_TEST(IListBaseTest,transferBeforeImpl)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
168