llvm/unittests/ADT/IListTest.cpp

   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(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
  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
  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
  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
 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
 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 {};
 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 };
 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 };
 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;
 203   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> {
 213   static void deleteNode(NodeWithCallback *) {}
 214 };
 215
 216 template <> struct ilist_callback_traits<NodeWithCallback> {
 217   void addNodeToList(NodeWithCallback *N) { N->IsInList = true; }
 218   void removeNodeFromList(NodeWithCallback *N) { N->IsInList = false; }
 219   template <class Iterator>
 220   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
 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
 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;
 286   PrivateNode(int Value) : Value(Value) {}
 287   PrivateNode(const PrivateNode &) = delete;
 288 };
 289
 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