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 "gtest/gtest.h"
  16 #include <string>
  17
  18 using namespace llvm;
  19
  20 TEST(SmallSetTest, Insert) {
  21
  22   SmallSet<int, 4> s1;
  23
  24   for (int i = 0; i < 4; i++) {
  25     auto InsertResult = s1.insert(i);
  26     EXPECT_EQ(*InsertResult.first, i);
  27     EXPECT_EQ(InsertResult.second, true);
  28   }
  29
  30   for (int i = 0; i < 4; i++) {
  31     auto InsertResult = s1.insert(i);
  32     EXPECT_EQ(*InsertResult.first, i);
  33     EXPECT_EQ(InsertResult.second, false);
  34   }
  35
  36   EXPECT_EQ(4u, s1.size());
  37
  38   for (int i = 0; i < 4; i++)
  39     EXPECT_EQ(1u, s1.count(i));
  40
  41   EXPECT_EQ(0u, s1.count(4));
  42 }
  43
  44 TEST(SmallSetTest, Grow) {
  45   SmallSet<int, 4> s1;
  46
  47   for (int i = 0; i < 8; i++) {
  48     auto InsertResult = s1.insert(i);
  49     EXPECT_EQ(*InsertResult.first, i);
  50     EXPECT_EQ(InsertResult.second, true);
  51   }
  52
  53   for (int i = 0; i < 8; i++) {
  54     auto InsertResult = s1.insert(i);
  55     EXPECT_EQ(*InsertResult.first, i);
  56     EXPECT_EQ(InsertResult.second, false);
  57   }
  58
  59   EXPECT_EQ(8u, s1.size());
  60
  61   for (int i = 0; i < 8; i++)
  62     EXPECT_EQ(1u, s1.count(i));
  63
  64   EXPECT_EQ(0u, s1.count(8));
  65 }
  66
  67 TEST(SmallSetTest, Erase) {
  68   SmallSet<int, 4> s1;
  69
  70   for (int i = 0; i < 8; i++)
  71     s1.insert(i);
  72
  73   EXPECT_EQ(8u, s1.size());
  74
  75   // Remove elements one by one and check if all other elements are still there.
  76   for (int i = 0; i < 8; i++) {
  77     EXPECT_EQ(1u, s1.count(i));
  78     EXPECT_TRUE(s1.erase(i));
  79     EXPECT_EQ(0u, s1.count(i));
  80     EXPECT_EQ(8u - i - 1, s1.size());
  81     for (int j = i + 1; j < 8; j++)
  82       EXPECT_EQ(1u, s1.count(j));
  83   }
  84
  85   EXPECT_EQ(0u, s1.count(8));
  86 }
  87
  88 TEST(SmallSetTest, IteratorInt) {
  89   SmallSet<int, 4> s1;
  90
  91   // Test the 'small' case.
  92   for (int i = 0; i < 3; i++)
  93     s1.insert(i);
  94
  95   std::vector<int> V(s1.begin(), s1.end());
  96   // Make sure the elements are in the expected order.
  97   llvm::sort(V);
  98   for (int i = 0; i < 3; i++)
  99     EXPECT_EQ(i, V[i]);
 100
 101   // Test the 'big' case by adding a few more elements to switch to std::set
 102   // internally.
 103   for (int i = 3; i < 6; i++)
 104     s1.insert(i);
 105
 106   V.assign(s1.begin(), s1.end());
 107   // Make sure the elements are in the expected order.
 108   llvm::sort(V);
 109   for (int i = 0; i < 6; i++)
 110     EXPECT_EQ(i, V[i]);
 111 }
 112
 113 TEST(SmallSetTest, IteratorString) {
 114   // Test SmallSetIterator for SmallSet with a type with non-trivial
 115   // ctors/dtors.
 116   SmallSet<std::string, 2> s1;
 117
 118   s1.insert("str 1");
 119   s1.insert("str 2");
 120   s1.insert("str 1");
 121
 122   std::vector<std::string> V(s1.begin(), s1.end());
 123   llvm::sort(V);
 124   EXPECT_EQ(2u, s1.size());
 125   EXPECT_EQ("str 1", V[0]);
 126   EXPECT_EQ("str 2", V[1]);
 127
 128   s1.insert("str 4");
 129   s1.insert("str 0");
 130   s1.insert("str 4");
 131
 132   V.assign(s1.begin(), s1.end());
 133   // Make sure the elements are in the expected order.
 134   llvm::sort(V);
 135   EXPECT_EQ(4u, s1.size());
 136   EXPECT_EQ("str 0", V[0]);
 137   EXPECT_EQ("str 1", V[1]);
 138   EXPECT_EQ("str 2", V[2]);
 139   EXPECT_EQ("str 4", V[3]);
 140 }
 141
 142 TEST(SmallSetTest, IteratorIncMoveCopy) {
 143   // Test SmallSetIterator for SmallSet with a type with non-trivial
 144   // ctors/dtors.
 145   SmallSet<std::string, 2> s1;
 146
 147   s1.insert("str 1");
 148   s1.insert("str 2");
 149
 150   auto Iter = s1.begin();
 151   EXPECT_EQ("str 1", *Iter);
 152   ++Iter;
 153   EXPECT_EQ("str 2", *Iter);
 154
 155   s1.insert("str 4");
 156   s1.insert("str 0");
 157   auto Iter2 = s1.begin();
 158   Iter = std::move(Iter2);
 159   EXPECT_EQ("str 0", *Iter);
 160 }
 161
 162 TEST(SmallSetTest, EqualityComparisonTest) {
 163   SmallSet<int, 8> s1small;
 164   SmallSet<int, 10> s2small;
 165   SmallSet<int, 3> s3large;
 166   SmallSet<int, 8> s4large;
 167
 168   for (int i = 1; i < 5; i++) {
 169     s1small.insert(i);
 170     s2small.insert(5 - i);
 171     s3large.insert(i);
 172   }
 173   for (int i = 1; i < 11; i++)
 174     s4large.insert(i);
 175
 176   EXPECT_EQ(s1small, s1small);
 177   EXPECT_EQ(s3large, s3large);
 178
 179   EXPECT_EQ(s1small, s2small);
 180   EXPECT_EQ(s1small, s3large);
 181   EXPECT_EQ(s2small, s3large);
 182
 183   EXPECT_NE(s1small, s4large);
 184   EXPECT_NE(s4large, s3large);
 185 }
 186
 187 TEST(SmallSetTest, Contains) {
 188   SmallSet<int, 2> Set;
 189   EXPECT_FALSE(Set.contains(0));
 190   EXPECT_FALSE(Set.contains(1));
 191
 192   Set.insert(0);
 193   Set.insert(1);
 194   EXPECT_TRUE(Set.contains(0));
 195   EXPECT_TRUE(Set.contains(1));
 196
 197   Set.insert(1);
 198   EXPECT_TRUE(Set.contains(0));
 199   EXPECT_TRUE(Set.contains(1));
 200
 201   Set.erase(1);
 202   EXPECT_TRUE(Set.contains(0));
 203   EXPECT_FALSE(Set.contains(1));
 204
 205   Set.insert(1);
 206   Set.insert(2);
 207   EXPECT_TRUE(Set.contains(0));
 208   EXPECT_TRUE(Set.contains(1));
 209   EXPECT_TRUE(Set.contains(2));
 210 }