unittests/ADT/SparseMultiSetTest.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/SparseMultiSet.h"
  11 #include "gtest/gtest.h"
  12
  13 using namespace llvm;
  14
  15 namespace {
  16
  17 typedef SparseMultiSet<unsigned> USet;
  18
  19 // Empty set tests.
  20 TEST(SparseMultiSetTest, EmptySet) {
  21   USet Set;
  22   EXPECT_TRUE(Set.empty());
  23   EXPECT_EQ(0u, Set.size());
  24
  25   Set.setUniverse(10);
  26
  27   // Lookups on empty set.
  28   EXPECT_TRUE(Set.find(0) == Set.end());
  29   EXPECT_TRUE(Set.find(9) == Set.end());
  30
  31   // Same thing on a const reference.
  32   const USet &CSet = Set;
  33   EXPECT_TRUE(CSet.empty());
  34   EXPECT_EQ(0u, CSet.size());
  35   EXPECT_TRUE(CSet.find(0) == CSet.end());
  36   USet::const_iterator I = CSet.find(5);
  37   EXPECT_TRUE(I == CSet.end());
  38 }
  39
  40 // Single entry set tests.
  41 TEST(SparseMultiSetTest, SingleEntrySet) {
  42   USet Set;
  43   Set.setUniverse(10);
  44   USet::iterator I = Set.insert(5);
  45   EXPECT_TRUE(I != Set.end());
  46   EXPECT_TRUE(*I == 5);
  47
  48   EXPECT_FALSE(Set.empty());
  49   EXPECT_EQ(1u, Set.size());
  50
  51   EXPECT_TRUE(Set.find(0) == Set.end());
  52   EXPECT_TRUE(Set.find(9) == Set.end());
  53
  54   EXPECT_FALSE(Set.contains(0));
  55   EXPECT_TRUE(Set.contains(5));
  56
  57   // Extra insert.
  58   I = Set.insert(5);
  59   EXPECT_TRUE(I != Set.end());
  60   EXPECT_TRUE(I == ++Set.find(5));
  61   I--;
  62   EXPECT_TRUE(I == Set.find(5));
  63
  64   // Erase non-existent element.
  65   I = Set.find(1);
  66   EXPECT_TRUE(I == Set.end());
  67   EXPECT_EQ(2u, Set.size());
  68   EXPECT_EQ(5u, *Set.find(5));
  69
  70   // Erase iterator.
  71   I = Set.find(5);
  72   EXPECT_TRUE(I != Set.end());
  73   I = Set.erase(I);
  74   EXPECT_TRUE(I != Set.end());
  75   I = Set.erase(I);
  76   EXPECT_TRUE(I == Set.end());
  77   EXPECT_TRUE(Set.empty());
  78 }
  79
  80 // Multiple entry set tests.
  81 TEST(SparseMultiSetTest, MultipleEntrySet) {
  82   USet Set;
  83   Set.setUniverse(10);
  84
  85   Set.insert(5);
  86   Set.insert(5);
  87   Set.insert(5);
  88   Set.insert(3);
  89   Set.insert(2);
  90   Set.insert(1);
  91   Set.insert(4);
  92   EXPECT_EQ(7u, Set.size());
  93
  94   // Erase last element by key.
  95   EXPECT_TRUE(Set.erase(Set.find(4)) == Set.end());
  96   EXPECT_EQ(6u, Set.size());
  97   EXPECT_FALSE(Set.contains(4));
  98   EXPECT_TRUE(Set.find(4) == Set.end());
  99
 100   // Erase first element by key.
 101   EXPECT_EQ(3u, Set.count(5));
 102   EXPECT_TRUE(Set.find(5) != Set.end());
 103   EXPECT_TRUE(Set.erase(Set.find(5)) != Set.end());
 104   EXPECT_EQ(5u, Set.size());
 105   EXPECT_EQ(2u, Set.count(5));
 106
 107   Set.insert(6);
 108   Set.insert(7);
 109   EXPECT_EQ(7u, Set.size());
 110
 111   // Erase tail by iterator.
 112   EXPECT_TRUE(Set.getTail(6) == Set.getHead(6));
 113   USet::iterator I = Set.erase(Set.find(6));
 114   EXPECT_TRUE(I == Set.end());
 115   EXPECT_EQ(6u, Set.size());
 116
 117   // Erase tails by iterator.
 118   EXPECT_EQ(2u, Set.count(5));
 119   I = Set.getTail(5);
 120   I = Set.erase(I);
 121   EXPECT_TRUE(I == Set.end());
 122   --I;
 123   EXPECT_EQ(1u, Set.count(5));
 124   EXPECT_EQ(5u, *I);
 125   I = Set.erase(I);
 126   EXPECT_TRUE(I == Set.end());
 127   EXPECT_EQ(0u, Set.count(5));
 128
 129   Set.insert(8);
 130   Set.insert(8);
 131   Set.insert(8);
 132   Set.insert(8);
 133   Set.insert(8);
 134
 135   // Erase all the 8s
 136   EXPECT_EQ(5, std::distance(Set.getHead(8), Set.end()));
 137   Set.eraseAll(8);
 138   EXPECT_EQ(0, std::distance(Set.getHead(8), Set.end()));
 139
 140   // Clear and resize the universe.
 141   Set.clear();
 142   EXPECT_EQ(0u, Set.size());
 143   EXPECT_FALSE(Set.contains(3));
 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.eraseAll(i);
 152
 153   for (unsigned i = 100; i != 800; ++i)
 154     EXPECT_EQ(1u, Set.count(i));
 155
 156   EXPECT_FALSE(Set.contains(99));
 157   EXPECT_FALSE(Set.contains(800));
 158   EXPECT_EQ(700u, Set.size());
 159 }
 160
 161 // Test out iterators
 162 TEST(SparseMultiSetTest, Iterators) {
 163   USet Set;
 164   Set.setUniverse(100);
 165
 166   Set.insert(0);
 167   Set.insert(1);
 168   Set.insert(2);
 169   Set.insert(0);
 170   Set.insert(1);
 171   Set.insert(0);
 172
 173   USet::RangePair RangePair = Set.equal_range(0);
 174   USet::iterator B = RangePair.first;
 175   USet::iterator E = RangePair.second;
 176
 177   // Move the iterators around, going to end and coming back.
 178   EXPECT_EQ(3, std::distance(B, E));
 179   EXPECT_EQ(B, --(--(--E)));
 180   EXPECT_EQ(++(++(++E)), Set.end());
 181   EXPECT_EQ(B, --(--(--E)));
 182   EXPECT_EQ(++(++(++E)), Set.end());
 183
 184   // Insert into the tail, and move around again
 185   Set.insert(0);
 186   EXPECT_EQ(B, --(--(--(--E))));
 187   EXPECT_EQ(++(++(++(++E))), Set.end());
 188   EXPECT_EQ(B, --(--(--(--E))));
 189   EXPECT_EQ(++(++(++(++E))), Set.end());
 190
 191   // Erase a tail, and move around again
 192   USet::iterator Erased = Set.erase(Set.getTail(0));
 193   EXPECT_EQ(Erased, E);
 194   EXPECT_EQ(B, --(--(--E)));
 195
 196   USet Set2;
 197   Set2.setUniverse(11);
 198   Set2.insert(3);
 199   EXPECT_TRUE(!Set2.contains(0));
 200   EXPECT_TRUE(!Set.contains(3));
 201
 202   EXPECT_EQ(Set2.getHead(3), Set2.getTail(3));
 203   EXPECT_EQ(Set2.getHead(0), Set2.getTail(0));
 204   B = Set2.find(3);
 205   EXPECT_EQ(Set2.find(3), --(++B));
 206 }
 207
 208 struct Alt {
 209   unsigned Value;
 210   explicit Alt(unsigned x) : Value(x) {}
 211   unsigned getSparseSetIndex() const { return Value - 1000; }
 212 };
 213
 214 TEST(SparseMultiSetTest, AltStructSet) {
 215   typedef SparseMultiSet<Alt> ASet;
 216   ASet Set;
 217   Set.setUniverse(10);
 218   Set.insert(Alt(1005));
 219
 220   ASet::iterator I = Set.find(5);
 221   ASSERT_TRUE(I != Set.end());
 222   EXPECT_EQ(1005u, I->Value);
 223
 224   Set.insert(Alt(1006));
 225   Set.insert(Alt(1006));
 226   I = Set.erase(Set.find(6));
 227   ASSERT_TRUE(I != Set.end());
 228   EXPECT_EQ(1006u, I->Value);
 229   I = Set.erase(Set.find(6));
 230   ASSERT_TRUE(I == Set.end());
 231
 232   EXPECT_TRUE(Set.contains(5));
 233   EXPECT_FALSE(Set.contains(6));
 234 }
 235 } // namespace