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 "gtest/gtest.h"
  15 #include <string>
  16
  17 using namespace llvm;
  18
  19 TEST(SmallSetTest, Insert) {
  20
  21   SmallSet<int, 4> s1;
  22
  23   for (int i = 0; i < 4; i++)
  24     s1.insert(i);
  25
  26   for (int i = 0; i < 4; i++)
  27     s1.insert(i);
  28
  29   EXPECT_EQ(4u, s1.size());
  30
  31   for (int i = 0; i < 4; i++)
  32     EXPECT_EQ(1u, s1.count(i));
  33
  34   EXPECT_EQ(0u, s1.count(4));
  35 }
  36
  37 TEST(SmallSetTest, Grow) {
  38   SmallSet<int, 4> s1;
  39
  40   for (int i = 0; i < 8; i++)
  41     s1.insert(i);
  42
  43   EXPECT_EQ(8u, s1.size());
  44
  45   for (int i = 0; i < 8; i++)
  46     EXPECT_EQ(1u, s1.count(i));
  47
  48   EXPECT_EQ(0u, s1.count(8));
  49 }
  50
  51 TEST(SmallSetTest, Erase) {
  52   SmallSet<int, 4> s1;
  53
  54   for (int i = 0; i < 8; i++)
  55     s1.insert(i);
  56
  57   EXPECT_EQ(8u, s1.size());
  58
  59   // Remove elements one by one and check if all other elements are still there.
  60   for (int i = 0; i < 8; i++) {
  61     EXPECT_EQ(1u, s1.count(i));
  62     EXPECT_TRUE(s1.erase(i));
  63     EXPECT_EQ(0u, s1.count(i));
  64     EXPECT_EQ(8u - i - 1, s1.size());
  65     for (int j = i + 1; j < 8; j++)
  66       EXPECT_EQ(1u, s1.count(j));
  67   }
  68
  69   EXPECT_EQ(0u, s1.count(8));
  70 }
  71
  72 TEST(SmallSetTest, IteratorInt) {
  73   SmallSet<int, 4> s1;
  74
  75   // Test the 'small' case.
  76   for (int i = 0; i < 3; i++)
  77     s1.insert(i);
  78
  79   std::vector<int> V(s1.begin(), s1.end());
  80   // Make sure the elements are in the expected order.
  81   std::sort(V.begin(), V.end());
  82   for (int i = 0; i < 3; i++)
  83     EXPECT_EQ(i, V[i]);
  84
  85   // Test the 'big' case by adding a few more elements to switch to std::set
  86   // internally.
  87   for (int i = 3; i < 6; i++)
  88     s1.insert(i);
  89
  90   V.assign(s1.begin(), s1.end());
  91   // Make sure the elements are in the expected order.
  92   std::sort(V.begin(), V.end());
  93   for (int i = 0; i < 6; i++)
  94     EXPECT_EQ(i, V[i]);
  95 }
  96
  97 TEST(SmallSetTest, IteratorString) {
  98   // Test SmallSetIterator for SmallSet with a type with non-trivial
  99   // ctors/dtors.
 100   SmallSet<std::string, 2> s1;
 101
 102   s1.insert("str 1");
 103   s1.insert("str 2");
 104   s1.insert("str 1");
 105
 106   std::vector<std::string> V(s1.begin(), s1.end());
 107   std::sort(V.begin(), V.end());
 108   EXPECT_EQ(2u, s1.size());
 109   EXPECT_EQ("str 1", V[0]);
 110   EXPECT_EQ("str 2", V[1]);
 111
 112   s1.insert("str 4");
 113   s1.insert("str 0");
 114   s1.insert("str 4");
 115
 116   V.assign(s1.begin(), s1.end());
 117   // Make sure the elements are in the expected order.
 118   std::sort(V.begin(), V.end());
 119   EXPECT_EQ(4u, s1.size());
 120   EXPECT_EQ("str 0", V[0]);
 121   EXPECT_EQ("str 1", V[1]);
 122   EXPECT_EQ("str 2", V[2]);
 123   EXPECT_EQ("str 4", V[3]);
 124 }
 125
 126 TEST(SmallSetTest, IteratorIncMoveCopy) {
 127   // Test SmallSetIterator for SmallSet with a type with non-trivial
 128   // ctors/dtors.
 129   SmallSet<std::string, 2> s1;
 130
 131   s1.insert("str 1");
 132   s1.insert("str 2");
 133
 134   auto Iter = s1.begin();
 135   EXPECT_EQ("str 1", *Iter);
 136   ++Iter;
 137   EXPECT_EQ("str 2", *Iter);
 138
 139   s1.insert("str 4");
 140   s1.insert("str 0");
 141   auto Iter2 = s1.begin();
 142   Iter = std::move(Iter2);
 143   EXPECT_EQ("str 0", *Iter);
 144 }