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