1 //===- unittests/ADT/IListTest.cpp - ilist 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.h"
10 #include "llvm/ADT/STLExtras.h"
11 #include "llvm/ADT/ilist_node.h"
12 #include "gtest/gtest.h"
13 #include <ostream>
14
15 using namespace llvm;
16
17 namespace {
18
19 struct Node : ilist_node<Node> {
20 int Value;
21
Node__anonf6b516cc0111::Node22 Node() {}
Node__anonf6b516cc0111::Node23 Node(int Value) : Value(Value) {}
24 Node(const Node&) = default;
~Node__anonf6b516cc0111::Node25 ~Node() { Value = -1; }
26 };
27
TEST(IListTest,Basic)28 TEST(IListTest, Basic) {
29 ilist<Node> List;
30 List.push_back(new Node(1));
31 EXPECT_EQ(1, List.back().Value);
32 EXPECT_EQ(nullptr, List.getPrevNode(List.back()));
33 EXPECT_EQ(nullptr, List.getNextNode(List.back()));
34
35 List.push_back(new Node(2));
36 EXPECT_EQ(2, List.back().Value);
37 EXPECT_EQ(2, List.getNextNode(List.front())->Value);
38 EXPECT_EQ(1, List.getPrevNode(List.back())->Value);
39
40 const ilist<Node> &ConstList = List;
41 EXPECT_EQ(2, ConstList.back().Value);
42 EXPECT_EQ(2, ConstList.getNextNode(ConstList.front())->Value);
43 EXPECT_EQ(1, ConstList.getPrevNode(ConstList.back())->Value);
44 }
45
TEST(IListTest,cloneFrom)46 TEST(IListTest, cloneFrom) {
47 Node L1Nodes[] = {Node(0), Node(1)};
48 Node L2Nodes[] = {Node(0), Node(1)};
49 ilist<Node> L1, L2, L3;
50
51 // Build L1 from L1Nodes.
52 L1.push_back(&L1Nodes[0]);
53 L1.push_back(&L1Nodes[1]);
54
55 // Build L2 from L2Nodes, based on L1 nodes.
56 L2.cloneFrom(L1, [&](const Node &N) { return &L2Nodes[N.Value]; });
57
58 // Add a node to L3 to be deleted, and then rebuild L3 by copying L1.
59 L3.push_back(new Node(7));
60 L3.cloneFrom(L1, [](const Node &N) { return new Node(N); });
61
62 EXPECT_EQ(2u, L1.size());
63 EXPECT_EQ(&L1Nodes[0], &L1.front());
64 EXPECT_EQ(&L1Nodes[1], &L1.back());
65 EXPECT_EQ(2u, L2.size());
66 EXPECT_EQ(&L2Nodes[0], &L2.front());
67 EXPECT_EQ(&L2Nodes[1], &L2.back());
68 EXPECT_EQ(2u, L3.size());
69 EXPECT_EQ(0, L3.front().Value);
70 EXPECT_EQ(1, L3.back().Value);
71
72 // Don't free nodes on the stack.
73 L1.clearAndLeakNodesUnsafely();
74 L2.clearAndLeakNodesUnsafely();
75 }
76
TEST(IListTest,SpliceOne)77 TEST(IListTest, SpliceOne) {
78 ilist<Node> List;
79 List.push_back(new Node(1));
80
81 // The single-element splice operation supports noops.
82 List.splice(List.begin(), List, List.begin());
83 EXPECT_EQ(1u, List.size());
84 EXPECT_EQ(1, List.front().Value);
85 EXPECT_TRUE(std::next(List.begin()) == List.end());
86
87 // Altenative noop. Move the first element behind itself.
88 List.push_back(new Node(2));
89 List.push_back(new Node(3));
90 List.splice(std::next(List.begin()), List, List.begin());
91 EXPECT_EQ(3u, List.size());
92 EXPECT_EQ(1, List.front().Value);
93 EXPECT_EQ(2, std::next(List.begin())->Value);
94 EXPECT_EQ(3, List.back().Value);
95 }
96
TEST(IListTest,SpliceSwap)97 TEST(IListTest, SpliceSwap) {
98 ilist<Node> L;
99 Node N0(0);
100 Node N1(1);
101 L.insert(L.end(), &N0);
102 L.insert(L.end(), &N1);
103 EXPECT_EQ(0, L.front().Value);
104 EXPECT_EQ(1, L.back().Value);
105
106 L.splice(L.begin(), L, ++L.begin());
107 EXPECT_EQ(1, L.front().Value);
108 EXPECT_EQ(0, L.back().Value);
109
110 L.clearAndLeakNodesUnsafely();
111 }
112
TEST(IListTest,SpliceSwapOtherWay)113 TEST(IListTest, SpliceSwapOtherWay) {
114 ilist<Node> L;
115 Node N0(0);
116 Node N1(1);
117 L.insert(L.end(), &N0);
118 L.insert(L.end(), &N1);
119 EXPECT_EQ(0, L.front().Value);
120 EXPECT_EQ(1, L.back().Value);
121
122 L.splice(L.end(), L, L.begin());
123 EXPECT_EQ(1, L.front().Value);
124 EXPECT_EQ(0, L.back().Value);
125
126 L.clearAndLeakNodesUnsafely();
127 }
128
TEST(IListTest,UnsafeClear)129 TEST(IListTest, UnsafeClear) {
130 ilist<Node> List;
131
132 // Before even allocating a sentinel.
133 List.clearAndLeakNodesUnsafely();
134 EXPECT_EQ(0u, List.size());
135
136 // Empty list with sentinel.
137 ilist<Node>::iterator E = List.end();
138 List.clearAndLeakNodesUnsafely();
139 EXPECT_EQ(0u, List.size());
140 // The sentinel shouldn't change.
141 EXPECT_TRUE(E == List.end());
142
143 // List with contents.
144 List.push_back(new Node(1));
145 ASSERT_EQ(1u, List.size());
146 Node *N = &*List.begin();
147 EXPECT_EQ(1, N->Value);
148 List.clearAndLeakNodesUnsafely();
149 EXPECT_EQ(0u, List.size());
150 ASSERT_EQ(1, N->Value);
151 delete N;
152
153 // List is still functional.
154 List.push_back(new Node(5));
155 List.push_back(new Node(6));
156 ASSERT_EQ(2u, List.size());
157 EXPECT_EQ(5, List.front().Value);
158 EXPECT_EQ(6, List.back().Value);
159 }
160
161 struct NodeWithCallback : ilist_node<NodeWithCallback> {
162 int Value = 0;
163 bool IsInList = false;
164 bool WasTransferred = false;
165
166 NodeWithCallback() = default;
NodeWithCallback__anonf6b516cc0111::NodeWithCallback167 NodeWithCallback(int Value) : Value(Value) {}
168 NodeWithCallback(const NodeWithCallback &) = delete;
169 };
170
171 } // end namespace
172
173 namespace llvm {
174 // These nodes are stack-allocated for testing purposes, so don't let the ilist
175 // own or delete them.
176 template <> struct ilist_alloc_traits<NodeWithCallback> {
deleteNodellvm::ilist_alloc_traits177 static void deleteNode(NodeWithCallback *) {}
178 };
179
180 template <> struct ilist_callback_traits<NodeWithCallback> {
addNodeToListllvm::ilist_callback_traits181 void addNodeToList(NodeWithCallback *N) { N->IsInList = true; }
removeNodeFromListllvm::ilist_callback_traits182 void removeNodeFromList(NodeWithCallback *N) { N->IsInList = false; }
183 template <class Iterator>
transferNodesFromListllvm::ilist_callback_traits184 void transferNodesFromList(ilist_callback_traits &Other, Iterator First,
185 Iterator Last) {
186 for (; First != Last; ++First) {
187 First->WasTransferred = true;
188 Other.removeNodeFromList(&*First);
189 addNodeToList(&*First);
190 }
191 }
192 };
193 } // end namespace llvm
194
195 namespace {
196
TEST(IListTest,addNodeToList)197 TEST(IListTest, addNodeToList) {
198 ilist<NodeWithCallback> L1, L2;
199 NodeWithCallback N(7);
200 ASSERT_FALSE(N.IsInList);
201 ASSERT_FALSE(N.WasTransferred);
202
203 L1.insert(L1.begin(), &N);
204 ASSERT_EQ(1u, L1.size());
205 ASSERT_EQ(&N, &L1.front());
206 ASSERT_TRUE(N.IsInList);
207 ASSERT_FALSE(N.WasTransferred);
208
209 L2.splice(L2.end(), L1);
210 ASSERT_EQ(&N, &L2.front());
211 ASSERT_TRUE(N.IsInList);
212 ASSERT_TRUE(N.WasTransferred);
213
214 L1.remove(&N);
215 ASSERT_EQ(0u, L1.size());
216 ASSERT_FALSE(N.IsInList);
217 ASSERT_TRUE(N.WasTransferred);
218 }
219
TEST(IListTest,sameListSplice)220 TEST(IListTest, sameListSplice) {
221 NodeWithCallback N1(1);
222 NodeWithCallback N2(2);
223 ASSERT_FALSE(N1.WasTransferred);
224 ASSERT_FALSE(N2.WasTransferred);
225
226 ilist<NodeWithCallback> L1;
227 L1.insert(L1.end(), &N1);
228 L1.insert(L1.end(), &N2);
229 ASSERT_EQ(2u, L1.size());
230 ASSERT_EQ(&N1, &L1.front());
231 ASSERT_FALSE(N1.WasTransferred);
232 ASSERT_FALSE(N2.WasTransferred);
233
234 // Swap the nodes with splice inside the same list. Check that we get the
235 // transfer callback.
236 L1.splice(L1.begin(), L1, std::next(L1.begin()), L1.end());
237 ASSERT_EQ(2u, L1.size());
238 ASSERT_EQ(&N1, &L1.back());
239 ASSERT_EQ(&N2, &L1.front());
240 ASSERT_FALSE(N1.WasTransferred);
241 ASSERT_TRUE(N2.WasTransferred);
242 }
243
244 struct PrivateNode : private ilist_node<PrivateNode> {
245 friend struct llvm::ilist_detail::NodeAccess;
246
247 int Value = 0;
248
249 PrivateNode() = default;
PrivateNode__anonf6b516cc0411::PrivateNode250 PrivateNode(int Value) : Value(Value) {}
251 PrivateNode(const PrivateNode &) = delete;
252 };
253
TEST(IListTest,privateNode)254 TEST(IListTest, privateNode) {
255 // Instantiate various APIs to be sure they're callable when ilist_node is
256 // inherited privately.
257 ilist<PrivateNode> L;
258 PrivateNode N(7);
259 L.insert(L.begin(), &N);
260 ++L.begin();
261 (void)*L.begin();
262 (void)(L.begin() == L.end());
263
264 ilist<PrivateNode> L2;
265 L2.splice(L2.end(), L);
266 L2.remove(&N);
267 }
268
269 } // end namespace
270