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