unittests/ADT/SparseSetTest.cpp

   1 //===------ ADT/SparseSetTest.cpp - SparseSet unit tests -  -----*- C++ -*-===//
   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 #include "llvm/ADT/SparseSet.h"
  11 #include "gtest/gtest.h"
  12
  13 using namespace llvm;
  14
  15 namespace {
  16
  17 typedef SparseSet<unsigned> USet;
  18
  19 // Empty set tests.
  20 TEST(SparseSetTest, EmptySet) {
  21   USet Set;
  22   EXPECT_TRUE(Set.empty());
  23   EXPECT_TRUE(Set.begin() == Set.end());
  24   EXPECT_EQ(0u, Set.size());
  25
  26   Set.setUniverse(10);
  27
  28   // Lookups on empty set.
  29   EXPECT_TRUE(Set.find(0) == Set.end());
  30   EXPECT_TRUE(Set.find(9) == Set.end());
  31
  32   // Same thing on a const reference.
  33   const USet &CSet = Set;
  34   EXPECT_TRUE(CSet.empty());
  35   EXPECT_TRUE(CSet.begin() == CSet.end());
  36   EXPECT_EQ(0u, CSet.size());
  37   EXPECT_TRUE(CSet.find(0) == CSet.end());
  38   USet::const_iterator I = CSet.find(5);
  39   EXPECT_TRUE(I == CSet.end());
  40 }
  41
  42 // Single entry set tests.
  43 TEST(SparseSetTest, SingleEntrySet) {
  44   USet Set;
  45   Set.setUniverse(10);
  46   std::pair<USet::iterator, bool> IP = Set.insert(5);
  47   EXPECT_TRUE(IP.second);
  48   EXPECT_TRUE(IP.first == Set.begin());
  49
  50   EXPECT_FALSE(Set.empty());
  51   EXPECT_FALSE(Set.begin() == Set.end());
  52   EXPECT_TRUE(Set.begin() + 1 == Set.end());
  53   EXPECT_EQ(1u, Set.size());
  54
  55   EXPECT_TRUE(Set.find(0) == Set.end());
  56   EXPECT_TRUE(Set.find(9) == Set.end());
  57
  58   EXPECT_FALSE(Set.count(0));
  59   EXPECT_TRUE(Set.count(5));
  60
  61   // Redundant insert.
  62   IP = Set.insert(5);
  63   EXPECT_FALSE(IP.second);
  64   EXPECT_TRUE(IP.first == Set.begin());
  65
  66   // Erase non-existent element.
  67   EXPECT_FALSE(Set.erase(1));
  68   EXPECT_EQ(1u, Set.size());
  69   EXPECT_EQ(5u, *Set.begin());
  70
  71   // Erase iterator.
  72   USet::iterator I = Set.find(5);
  73   EXPECT_TRUE(I == Set.begin());
  74   I = Set.erase(I);
  75   EXPECT_TRUE(I == Set.end());
  76   EXPECT_TRUE(Set.empty());
  77 }
  78
  79 // Multiple entry set tests.
  80 TEST(SparseSetTest, MultipleEntrySet) {
  81   USet Set;
  82   Set.setUniverse(10);
  83
  84   Set.insert(5);
  85   Set.insert(3);
  86   Set.insert(2);
  87   Set.insert(1);
  88   Set.insert(4);
  89   EXPECT_EQ(5u, Set.size());
  90
  91   // Without deletions, iteration order == insertion order.
  92   USet::const_iterator I = Set.begin();
  93   EXPECT_EQ(5u, *I);
  94   ++I;
  95   EXPECT_EQ(3u, *I);
  96   ++I;
  97   EXPECT_EQ(2u, *I);
  98   ++I;
  99   EXPECT_EQ(1u, *I);
 100   ++I;
 101   EXPECT_EQ(4u, *I);
 102   ++I;
 103   EXPECT_TRUE(I == Set.end());
 104
 105   // Redundant insert.
 106   std::pair<USet::iterator, bool> IP = Set.insert(3);
 107   EXPECT_FALSE(IP.second);
 108   EXPECT_TRUE(IP.first == Set.begin() + 1);
 109
 110   // Erase last element by key.
 111   EXPECT_TRUE(Set.erase(4));
 112   EXPECT_EQ(4u, Set.size());
 113   EXPECT_FALSE(Set.count(4));
 114   EXPECT_FALSE(Set.erase(4));
 115   EXPECT_EQ(4u, Set.size());
 116   EXPECT_FALSE(Set.count(4));
 117
 118   // Erase first element by key.
 119   EXPECT_TRUE(Set.count(5));
 120   EXPECT_TRUE(Set.find(5) == Set.begin());
 121   EXPECT_TRUE(Set.erase(5));
 122   EXPECT_EQ(3u, Set.size());
 123   EXPECT_FALSE(Set.count(5));
 124   EXPECT_FALSE(Set.erase(5));
 125   EXPECT_EQ(3u, Set.size());
 126   EXPECT_FALSE(Set.count(5));
 127
 128   Set.insert(6);
 129   Set.insert(7);
 130   EXPECT_EQ(5u, Set.size());
 131
 132   // Erase last element by iterator.
 133   I = Set.erase(Set.end() - 1);
 134   EXPECT_TRUE(I == Set.end());
 135   EXPECT_EQ(4u, Set.size());
 136
 137   // Erase second element by iterator.
 138   I = Set.erase(Set.begin() + 1);
 139   EXPECT_TRUE(I == Set.begin() + 1);
 140
 141   // Clear and resize the universe.
 142   Set.clear();
 143   EXPECT_FALSE(Set.count(5));
 144   Set.setUniverse(1000);
 145
 146   // Add more than 256 elements.
 147   for (unsigned i = 100; i != 800; ++i)
 148     Set.insert(i);
 149
 150   for (unsigned i = 0; i != 10; ++i)
 151     Set.erase(i);
 152
 153   for (unsigned i = 100; i != 800; ++i)
 154     EXPECT_TRUE(Set.count(i));
 155
 156   EXPECT_FALSE(Set.count(99));
 157   EXPECT_FALSE(Set.count(800));
 158   EXPECT_EQ(700u, Set.size());
 159 }
 160
 161 struct Alt {
 162   unsigned Value;
 163   explicit Alt(unsigned x) : Value(x) {}
 164   unsigned getSparseSetIndex() const { return Value - 1000; }
 165 };
 166
 167 TEST(SparseSetTest, AltStructSet) {
 168   typedef SparseSet<Alt> ASet;
 169   ASet Set;
 170   Set.setUniverse(10);
 171   Set.insert(Alt(1005));
 172
 173   ASet::iterator I = Set.find(5);
 174   ASSERT_TRUE(I == Set.begin());
 175   EXPECT_EQ(1005u, I->Value);
 176
 177   Set.insert(Alt(1006));
 178   Set.insert(Alt(1006));
 179   I = Set.erase(Set.begin());
 180   ASSERT_TRUE(I == Set.begin());
 181   EXPECT_EQ(1006u, I->Value);
 182
 183   EXPECT_FALSE(Set.erase(5));
 184   EXPECT_TRUE(Set.erase(6));
 185 }
 186
 187 TEST(SparseSetTest, PopBack) {
 188   USet Set;
 189   const unsigned UpperBound = 300;
 190   Set.setUniverse(UpperBound);
 191   for (unsigned i = 0; i < UpperBound; ++i)
 192     Set.insert(i);
 193
 194   // Make sure pop back returns the values in the reverse order we
 195   // inserted them.
 196   unsigned Expected = UpperBound;
 197   while (!Set.empty())
 198     ASSERT_TRUE(--Expected == Set.pop_back_val());
 199
 200   // Insert again the same elements in the sparse set and make sure
 201   // each insertion actually inserts the elements. I.e., check
 202   // that the underlying data structure are properly cleared.
 203   for (unsigned i = 0; i < UpperBound; ++i)
 204     ASSERT_TRUE(Set.insert(i).second);
 205 }
 206 } // namespace