270 lines · 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-exception6//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 15using namespace llvm;16 17namespace {18 19struct Node : ilist_node<Node> {20 int Value;21 22 Node() = default;23 Node(int Value) : Value(Value) {}24 Node(const Node&) = default;25 ~Node() { Value = -1; }26};27 28TEST(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 46TEST(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 77TEST(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 97TEST(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 113TEST(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 129TEST(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 161struct 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 namespace172 173namespace llvm {174// These nodes are stack-allocated for testing purposes, so don't let the ilist175// own or delete them.176template <> struct ilist_alloc_traits<NodeWithCallback> {177 static void deleteNode(NodeWithCallback *) {}178};179 180template <> 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 llvm194 195namespace {196 197TEST(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 220TEST(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 the235 // 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 244struct 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 254TEST(IListTest, privateNode) {255 // Instantiate various APIs to be sure they're callable when ilist_node is256 // 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 namespace270