llvm/unittests/ADT/SmallSetTest.cpp

   1 //===- llvm/unittest/ADT/SmallSetTest.cpp ------------------------------===//
   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 // SmallSet unit tests.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/ADT/SmallSet.h"
  14 #include "llvm/ADT/STLExtras.h"
  15 #include "gmock/gmock.h"
  16 #include "gtest/gtest.h"
  17 #include <string>
  18
  19 using namespace llvm;
  20
  21 TEST(SmallSetTest, ConstructorIteratorPair) {
  22   std::initializer_list<int> L = {1, 2, 3, 4, 5};
  23   SmallSet<int, 4> S(std::begin(L), std::end(L));
  24   EXPECT_THAT(S, testing::UnorderedElementsAreArray(L));
  25 }
  26
  27 TEST(SmallSet, ConstructorRange) {
  28   std::initializer_list<int> L = {1, 2, 3, 4, 5};
  29
  30   SmallSet<int, 4> S(llvm::make_range(std::begin(L), std::end(L)));
  31   EXPECT_THAT(S, testing::UnorderedElementsAreArray(L));
  32 }
  33
  34 TEST(SmallSet, ConstructorInitializerList) {
  35   std::initializer_list<int> L = {1, 2, 3, 4, 5};
  36   SmallSet<int, 4> S = {1, 2, 3, 4, 5};
  37   EXPECT_THAT(S, testing::UnorderedElementsAreArray(L));
  38 }
  39
  40 TEST(SmallSet, CopyConstructor) {
  41   SmallSet<int, 4> S = {1, 2, 3};
  42   SmallSet<int, 4> T = S;
  43
  44   EXPECT_THAT(S, testing::ContainerEq(T));
  45 }
  46
  47 TEST(SmallSet, MoveConstructor) {
  48   std::initializer_list<int> L = {1, 2, 3};
  49   SmallSet<int, 4> S = L;
  50   SmallSet<int, 4> T = std::move(S);
  51
  52   EXPECT_THAT(T, testing::UnorderedElementsAreArray(L));
  53 }
  54
  55 TEST(SmallSet, CopyAssignment) {
  56   SmallSet<int, 4> S = {1, 2, 3};
  57   SmallSet<int, 4> T;
  58   T = S;
  59
  60   EXPECT_THAT(S, testing::ContainerEq(T));
  61 }
  62
  63 TEST(SmallSet, MoveAssignment) {
  64   std::initializer_list<int> L = {1, 2, 3};
  65   SmallSet<int, 4> S = L;
  66   SmallSet<int, 4> T;
  67   T = std::move(S);
  68
  69   EXPECT_THAT(T, testing::UnorderedElementsAreArray(L));
  70 }
  71
  72 TEST(SmallSetTest, Insert) {
  73
  74   SmallSet<int, 4> s1;
  75
  76   for (int i = 0; i < 4; i++) {
  77     auto InsertResult = s1.insert(i);
  78     EXPECT_EQ(*InsertResult.first, i);
  79     EXPECT_EQ(InsertResult.second, true);
  80   }
  81
  82   for (int i = 0; i < 4; i++) {
  83     auto InsertResult = s1.insert(i);
  84     EXPECT_EQ(*InsertResult.first, i);
  85     EXPECT_EQ(InsertResult.second, false);
  86   }
  87
  88   EXPECT_EQ(4u, s1.size());
  89
  90   for (int i = 0; i < 4; i++)
  91     EXPECT_EQ(1u, s1.count(i));
  92
  93   EXPECT_EQ(0u, s1.count(4));
  94 }
  95
  96 TEST(SmallSetTest, InsertPerfectFwd) {
  97   struct Value {
  98     int Key;
  99     bool Moved;
 100
 101     Value(int Key) : Key(Key), Moved(false) {}
 102     Value(const Value &) = default;
 103     Value(Value &&Other) : Key(Other.Key), Moved(false) { Other.Moved = true; }
 104     bool operator==(const Value &Other) const { return Key == Other.Key; }
 105     bool operator<(const Value &Other) const { return Key < Other.Key; }
 106   };
 107
 108   {
 109     SmallSet<Value, 4> S;
 110     Value V1(1), V2(2);
 111
 112     S.insert(V1);
 113     EXPECT_EQ(V1.Moved, false);
 114
 115     S.insert(std::move(V2));
 116     EXPECT_EQ(V2.Moved, true);
 117   }
 118   {
 119     SmallSet<Value, 1> S;
 120     Value V1(1), V2(2);
 121
 122     S.insert(V1);
 123     EXPECT_EQ(V1.Moved, false);
 124
 125     S.insert(std::move(V2));
 126     EXPECT_EQ(V2.Moved, true);
 127   }
 128 }
 129
 130 TEST(SmallSetTest, Grow) {
 131   SmallSet<int, 4> s1;
 132
 133   for (int i = 0; i < 8; i++) {
 134     auto InsertResult = s1.insert(i);
 135     EXPECT_EQ(*InsertResult.first, i);
 136     EXPECT_EQ(InsertResult.second, true);
 137   }
 138
 139   for (int i = 0; i < 8; i++) {
 140     auto InsertResult = s1.insert(i);
 141     EXPECT_EQ(*InsertResult.first, i);
 142     EXPECT_EQ(InsertResult.second, false);
 143   }
 144
 145   EXPECT_EQ(8u, s1.size());
 146
 147   for (int i = 0; i < 8; i++)
 148     EXPECT_EQ(1u, s1.count(i));
 149
 150   EXPECT_EQ(0u, s1.count(8));
 151 }
 152
 153 TEST(SmallSetTest, Erase) {
 154   SmallSet<int, 4> s1;
 155
 156   for (int i = 0; i < 8; i++)
 157     s1.insert(i);
 158
 159   EXPECT_EQ(8u, s1.size());
 160
 161   // Remove elements one by one and check if all other elements are still there.
 162   for (int i = 0; i < 8; i++) {
 163     EXPECT_EQ(1u, s1.count(i));
 164     EXPECT_TRUE(s1.erase(i));
 165     EXPECT_EQ(0u, s1.count(i));
 166     EXPECT_EQ(8u - i - 1, s1.size());
 167     for (int j = i + 1; j < 8; j++)
 168       EXPECT_EQ(1u, s1.count(j));
 169   }
 170
 171   EXPECT_EQ(0u, s1.count(8));
 172 }
 173
 174 TEST(SmallSetTest, IteratorInt) {
 175   SmallSet<int, 4> s1;
 176
 177   // Test the 'small' case.
 178   for (int i = 0; i < 3; i++)
 179     s1.insert(i);
 180
 181   std::vector<int> V(s1.begin(), s1.end());
 182   // Make sure the elements are in the expected order.
 183   llvm::sort(V);
 184   for (int i = 0; i < 3; i++)
 185     EXPECT_EQ(i, V[i]);
 186
 187   // Test the 'big' case by adding a few more elements to switch to std::set
 188   // internally.
 189   for (int i = 3; i < 6; i++)
 190     s1.insert(i);
 191
 192   V.assign(s1.begin(), s1.end());
 193   // Make sure the elements are in the expected order.
 194   llvm::sort(V);
 195   for (int i = 0; i < 6; i++)
 196     EXPECT_EQ(i, V[i]);
 197 }
 198
 199 TEST(SmallSetTest, IteratorString) {
 200   // Test SmallSetIterator for SmallSet with a type with non-trivial
 201   // ctors/dtors.
 202   SmallSet<std::string, 2> s1;
 203
 204   s1.insert("str 1");
 205   s1.insert("str 2");
 206   s1.insert("str 1");
 207
 208   std::vector<std::string> V(s1.begin(), s1.end());
 209   llvm::sort(V);
 210   EXPECT_EQ(2u, s1.size());
 211   EXPECT_EQ("str 1", V[0]);
 212   EXPECT_EQ("str 2", V[1]);
 213
 214   s1.insert("str 4");
 215   s1.insert("str 0");
 216   s1.insert("str 4");
 217
 218   V.assign(s1.begin(), s1.end());
 219   // Make sure the elements are in the expected order.
 220   llvm::sort(V);
 221   EXPECT_EQ(4u, s1.size());
 222   EXPECT_EQ("str 0", V[0]);
 223   EXPECT_EQ("str 1", V[1]);
 224   EXPECT_EQ("str 2", V[2]);
 225   EXPECT_EQ("str 4", V[3]);
 226 }
 227
 228 TEST(SmallSetTest, IteratorIncMoveCopy) {
 229   // Test SmallSetIterator for SmallSet with a type with non-trivial
 230   // ctors/dtors.
 231   SmallSet<std::string, 2> s1;
 232
 233   s1.insert("str 1");
 234   s1.insert("str 2");
 235
 236   auto Iter = s1.begin();
 237   EXPECT_EQ("str 1", *Iter);
 238   ++Iter;
 239   EXPECT_EQ("str 2", *Iter);
 240
 241   s1.insert("str 4");
 242   s1.insert("str 0");
 243   auto Iter2 = s1.begin();
 244   Iter = std::move(Iter2);
 245   EXPECT_EQ("str 0", *Iter);
 246 }
 247
 248 TEST(SmallSetTest, EqualityComparisonTest) {
 249   SmallSet<int, 8> s1small;
 250   SmallSet<int, 10> s2small;
 251   SmallSet<int, 3> s3large;
 252   SmallSet<int, 8> s4large;
 253
 254   for (int i = 1; i < 5; i++) {
 255     s1small.insert(i);
 256     s2small.insert(5 - i);
 257     s3large.insert(i);
 258   }
 259   for (int i = 1; i < 11; i++)
 260     s4large.insert(i);
 261
 262   EXPECT_EQ(s1small, s1small);
 263   EXPECT_EQ(s3large, s3large);
 264
 265   EXPECT_EQ(s1small, s2small);
 266   EXPECT_EQ(s1small, s3large);
 267   EXPECT_EQ(s2small, s3large);
 268
 269   EXPECT_NE(s1small, s4large);
 270   EXPECT_NE(s4large, s3large);
 271 }
 272
 273 TEST(SmallSetTest, Contains) {
 274   SmallSet<int, 2> Set;
 275   EXPECT_FALSE(Set.contains(0));
 276   EXPECT_FALSE(Set.contains(1));
 277
 278   Set.insert(0);
 279   Set.insert(1);
 280   EXPECT_TRUE(Set.contains(0));
 281   EXPECT_TRUE(Set.contains(1));
 282
 283   Set.insert(1);
 284   EXPECT_TRUE(Set.contains(0));
 285   EXPECT_TRUE(Set.contains(1));
 286
 287   Set.erase(1);
 288   EXPECT_TRUE(Set.contains(0));
 289   EXPECT_FALSE(Set.contains(1));
 290
 291   Set.insert(1);
 292   Set.insert(2);
 293   EXPECT_TRUE(Set.contains(0));
 294   EXPECT_TRUE(Set.contains(1));
 295   EXPECT_TRUE(Set.contains(2));
 296 }