unittests/ADT/IListTest.cpp

   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