llvm/unittests/ADT/SparseSetTest.cpp

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