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 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(&*First);
 189       addNodeToList(&*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(L1.begin(), &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(L2.end(), L1);
 210   ASSERT_EQ(&N, &L2.front());
 211   ASSERT_TRUE(N.IsInList);
 212   ASSERT_TRUE(N.WasTransferred);
 213
 214   L1.remove(&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(L1.end(), &N1);
 228   L1.insert(L1.end(), &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(L1.begin(), L1, std::next(L1.begin()), 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(L.begin(), &N);
 260   ++L.begin();
 261   (void)*L.begin();
 262   (void)(L.begin() == L.end());
 263
 264   ilist<PrivateNode> L2;
 265   L2.splice(L2.end(), L);
 266   L2.remove(&N);
 267 }
 268
 269 } // end namespace