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_CASE(IListBaseTest, IListBaseTestTypes);
23
TYPED_TEST(IListBaseTest,insertBeforeImpl)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
TYPED_TEST(IListBaseTest,removeImpl)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
TYPED_TEST(IListBaseTest,removeRangeImpl)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
TYPED_TEST(IListBaseTest,removeRangeImplAllButSentinel)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
TYPED_TEST(IListBaseTest,transferBeforeImpl)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