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__anon9ccdcaa90111::Node22   Node() {}
Node__anon9ccdcaa90111::Node23   Node(int Value) : Value(Value) {}
24   Node(const Node&) = default;
~Node__anon9ccdcaa90111::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 Empty {};
TEST(IListTest,HasObsoleteCustomizationTrait)162 TEST(IListTest, HasObsoleteCustomizationTrait) {
163   // Negative test for HasObsoleteCustomization.
164   static_assert(!ilist_detail::HasObsoleteCustomization<Empty, Node>::value,
165                 "Empty has no customizations");
166 }
167 
168 struct GetNext {
169   Node *getNext(Node *);
170 };
TEST(IListTest,HasGetNextTrait)171 TEST(IListTest, HasGetNextTrait) {
172   static_assert(ilist_detail::HasGetNext<GetNext, Node>::value,
173                 "GetNext has a getNext(Node*)");
174   static_assert(ilist_detail::HasObsoleteCustomization<GetNext, Node>::value,
175                 "Empty should be obsolete because of getNext()");
176 
177   // Negative test for HasGetNext.
178   static_assert(!ilist_detail::HasGetNext<Empty, Node>::value,
179                 "Empty does not have a getNext(Node*)");
180 }
181 
182 struct CreateSentinel {
183   Node *createSentinel();
184 };
TEST(IListTest,HasCreateSentinelTrait)185 TEST(IListTest, HasCreateSentinelTrait) {
186   static_assert(ilist_detail::HasCreateSentinel<CreateSentinel>::value,
187                 "CreateSentinel has a getNext(Node*)");
188   static_assert(
189       ilist_detail::HasObsoleteCustomization<CreateSentinel, Node>::value,
190       "Empty should be obsolete because of createSentinel()");
191 
192   // Negative test for HasCreateSentinel.
193   static_assert(!ilist_detail::HasCreateSentinel<Empty>::value,
194                 "Empty does not have a createSentinel()");
195 }
196 
197 struct NodeWithCallback : ilist_node<NodeWithCallback> {
198   int Value = 0;
199   bool IsInList = false;
200   bool WasTransferred = false;
201 
202   NodeWithCallback() = default;
NodeWithCallback__anon9ccdcaa90111::NodeWithCallback203   NodeWithCallback(int Value) : Value(Value) {}
204   NodeWithCallback(const NodeWithCallback &) = delete;
205 };
206 
207 } // end namespace
208 
209 namespace llvm {
210 // These nodes are stack-allocated for testing purposes, so don't let the ilist
211 // own or delete them.
212 template <> struct ilist_alloc_traits<NodeWithCallback> {
deleteNodellvm::ilist_alloc_traits213   static void deleteNode(NodeWithCallback *) {}
214 };
215 
216 template <> struct ilist_callback_traits<NodeWithCallback> {
addNodeToListllvm::ilist_callback_traits217   void addNodeToList(NodeWithCallback *N) { N->IsInList = true; }
removeNodeFromListllvm::ilist_callback_traits218   void removeNodeFromList(NodeWithCallback *N) { N->IsInList = false; }
219   template <class Iterator>
transferNodesFromListllvm::ilist_callback_traits220   void transferNodesFromList(ilist_callback_traits &Other, Iterator First,
221                              Iterator Last) {
222     for (; First != Last; ++First) {
223       First->WasTransferred = true;
224       Other.removeNodeFromList(&*First);
225       addNodeToList(&*First);
226     }
227   }
228 };
229 } // end namespace llvm
230 
231 namespace {
232 
TEST(IListTest,addNodeToList)233 TEST(IListTest, addNodeToList) {
234   ilist<NodeWithCallback> L1, L2;
235   NodeWithCallback N(7);
236   ASSERT_FALSE(N.IsInList);
237   ASSERT_FALSE(N.WasTransferred);
238 
239   L1.insert(L1.begin(), &N);
240   ASSERT_EQ(1u, L1.size());
241   ASSERT_EQ(&N, &L1.front());
242   ASSERT_TRUE(N.IsInList);
243   ASSERT_FALSE(N.WasTransferred);
244 
245   L2.splice(L2.end(), L1);
246   ASSERT_EQ(&N, &L2.front());
247   ASSERT_TRUE(N.IsInList);
248   ASSERT_TRUE(N.WasTransferred);
249 
250   L1.remove(&N);
251   ASSERT_EQ(0u, L1.size());
252   ASSERT_FALSE(N.IsInList);
253   ASSERT_TRUE(N.WasTransferred);
254 }
255 
TEST(IListTest,sameListSplice)256 TEST(IListTest, sameListSplice) {
257   NodeWithCallback N1(1);
258   NodeWithCallback N2(2);
259   ASSERT_FALSE(N1.WasTransferred);
260   ASSERT_FALSE(N2.WasTransferred);
261 
262   ilist<NodeWithCallback> L1;
263   L1.insert(L1.end(), &N1);
264   L1.insert(L1.end(), &N2);
265   ASSERT_EQ(2u, L1.size());
266   ASSERT_EQ(&N1, &L1.front());
267   ASSERT_FALSE(N1.WasTransferred);
268   ASSERT_FALSE(N2.WasTransferred);
269 
270   // Swap the nodes with splice inside the same list. Check that we get the
271   // transfer callback.
272   L1.splice(L1.begin(), L1, std::next(L1.begin()), L1.end());
273   ASSERT_EQ(2u, L1.size());
274   ASSERT_EQ(&N1, &L1.back());
275   ASSERT_EQ(&N2, &L1.front());
276   ASSERT_FALSE(N1.WasTransferred);
277   ASSERT_TRUE(N2.WasTransferred);
278 }
279 
280 struct PrivateNode : private ilist_node<PrivateNode> {
281   friend struct llvm::ilist_detail::NodeAccess;
282 
283   int Value = 0;
284 
285   PrivateNode() = default;
PrivateNode__anon9ccdcaa90411::PrivateNode286   PrivateNode(int Value) : Value(Value) {}
287   PrivateNode(const PrivateNode &) = delete;
288 };
289 
TEST(IListTest,privateNode)290 TEST(IListTest, privateNode) {
291   // Instantiate various APIs to be sure they're callable when ilist_node is
292   // inherited privately.
293   ilist<PrivateNode> L;
294   PrivateNode N(7);
295   L.insert(L.begin(), &N);
296   ++L.begin();
297   (void)*L.begin();
298   (void)(L.begin() == L.end());
299 
300   ilist<PrivateNode> L2;
301   L2.splice(L2.end(), L);
302   L2.remove(&N);
303 }
304 
305 } // end namespace
306