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