unittests/ADT/SmallSetTest.cpp

   1 //===- llvm/unittest/ADT/SmallSetTest.cpp ------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // SmallSet unit tests.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/ADT/SmallSet.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   std::sort(V.begin(), V.end());
  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   std::sort(V.begin(), V.end());
  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   std::sort(V.begin(), V.end());
 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   std::sort(V.begin(), V.end());
 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   auto Iter3 = s1.end();
 147   Iter3 = Iter2;
 148   EXPECT_EQ(Iter3, Iter2);
 149 }