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