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 | |
22 | Node() {} |
23 | Node(int Value) : Value(Value) {} |
24 | Node(const Node&) = default; |
25 | ~Node() { Value = -1; } |
26 | }; |
27 | |
28 | TEST(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 | |
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(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 | |
77 | TEST(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 | |
97 | TEST(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 | |
113 | TEST(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 | |
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(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 | |
161 | struct 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 | |
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> { |
177 | static void deleteNode(NodeWithCallback *) {} |
178 | }; |
179 | |
180 | template <> 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 | |
195 | namespace { |
196 | |
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(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 | |
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(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 | |
244 | struct 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 | |
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(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 | |