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
15using namespace llvm;
16
17namespace {
18
19struct Node : ilist_node<Node> {
20 int Value;
21
22 Node() {}
23 Node(int Value) : Value(Value) {}
24 Node(const Node&) = default;
25 ~Node() { Value = -1; }
26};
27
28TEST(IListTest, Basic) {
29 ilist<Node> List;
30 List.push_back(val: 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(val: 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
46TEST(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(val: &L1Nodes[0]);
53 L1.push_back(val: &L1Nodes[1]);
54
55 // Build L2 from L2Nodes, based on L1 nodes.
56 L2.cloneFrom(L2: L1, clone: [&](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(val: new Node(7));
60 L3.cloneFrom(L2: L1, clone: [](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
77TEST(IListTest, SpliceOne) {
78 ilist<Node> List;
79 List.push_back(val: new Node(1));
80
81 // The single-element splice operation supports noops.
82 List.splice(where: List.begin(), L2&: List, first: 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(val: new Node(2));
89 List.push_back(val: new Node(3));
90 List.splice(where: std::next(x: List.begin()), L2&: List, first: 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
97TEST(IListTest, SpliceSwap) {
98 ilist<Node> L;
99 Node N0(0);
100 Node N1(1);
101 L.insert(where: L.end(), New: &N0);
102 L.insert(where: L.end(), New: &N1);
103 EXPECT_EQ(0, L.front().Value);
104 EXPECT_EQ(1, L.back().Value);
105
106 L.splice(where: L.begin(), L2&: L, first: ++L.begin());
107 EXPECT_EQ(1, L.front().Value);
108 EXPECT_EQ(0, L.back().Value);
109
110 L.clearAndLeakNodesUnsafely();
111}
112
113TEST(IListTest, SpliceSwapOtherWay) {
114 ilist<Node> L;
115 Node N0(0);
116 Node N1(1);
117 L.insert(where: L.end(), New: &N0);
118 L.insert(where: L.end(), New: &N1);
119 EXPECT_EQ(0, L.front().Value);
120 EXPECT_EQ(1, L.back().Value);
121
122 L.splice(where: L.end(), L2&: L, first: L.begin());
123 EXPECT_EQ(1, L.front().Value);
124 EXPECT_EQ(0, L.back().Value);
125
126 L.clearAndLeakNodesUnsafely();
127}
128
129TEST(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(val: 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(val: new Node(5));
155 List.push_back(val: 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
161struct NodeWithCallback : ilist_node<NodeWithCallback> {
162 int Value = 0;
163 bool IsInList = false;
164 bool WasTransferred = false;
165
166 NodeWithCallback() = default;
167 NodeWithCallback(int Value) : Value(Value) {}
168 NodeWithCallback(const NodeWithCallback &) = delete;
169};
170
171} // end namespace
172
173namespace llvm {
174// These nodes are stack-allocated for testing purposes, so don't let the ilist
175// own or delete them.
176template <> struct ilist_alloc_traits<NodeWithCallback> {
177 static void deleteNode(NodeWithCallback *) {}
178};
179
180template <> struct ilist_callback_traits<NodeWithCallback> {
181 void addNodeToList(NodeWithCallback *N) { N->IsInList = true; }
182 void removeNodeFromList(NodeWithCallback *N) { N->IsInList = false; }
183 template <class Iterator>
184 void transferNodesFromList(ilist_callback_traits &Other, Iterator First,
185 Iterator Last) {
186 for (; First != Last; ++First) {
187 First->WasTransferred = true;
188 Other.removeNodeFromList(N: &*First);
189 addNodeToList(N: &*First);
190 }
191 }
192};
193} // end namespace llvm
194
195namespace {
196
197TEST(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(where: L1.begin(), New: &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(where: L2.end(), L2&: L1);
210 ASSERT_EQ(&N, &L2.front());
211 ASSERT_TRUE(N.IsInList);
212 ASSERT_TRUE(N.WasTransferred);
213
214 L1.remove(IT: &N);
215 ASSERT_EQ(0u, L1.size());
216 ASSERT_FALSE(N.IsInList);
217 ASSERT_TRUE(N.WasTransferred);
218}
219
220TEST(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(where: L1.end(), New: &N1);
228 L1.insert(where: L1.end(), New: &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(where: L1.begin(), L2&: L1, first: std::next(x: L1.begin()), last: 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
244struct PrivateNode : private ilist_node<PrivateNode> {
245 friend struct llvm::ilist_detail::NodeAccess;
246
247 int Value = 0;
248
249 PrivateNode() = default;
250 PrivateNode(int Value) : Value(Value) {}
251 PrivateNode(const PrivateNode &) = delete;
252};
253
254TEST(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(where: L.begin(), New: &N);
260 ++L.begin();
261 (void)*L.begin();
262 (void)(L.begin() == L.end());
263
264 ilist<PrivateNode> L2;
265 L2.splice(where: L2.end(), L2&: L);
266 L2.remove(IT: &N);
267}
268
269} // end namespace
270

source code of llvm/unittests/ADT/IListTest.cpp