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 208 TEST(SparseSetTest, MoveConstructor) { 209 USet Set; 210 Set.setUniverse(2); 211 Set.insert(1); 212 EXPECT_FALSE(Set.empty()); 213 // Move and check original is empty. 214 USet OtherSet(std::move(Set)); 215 EXPECT_TRUE(Set.empty()); 216 EXPECT_TRUE(OtherSet.contains(1)); 217 } 218 219 } // namespace 220