132c10eecffb4923e0721c395e4b80fb732543f18Behdad Esfahbod//===------ ADT/SparseSetTest.cpp - SparseSet unit tests - -----*- C++ -*-===// 27ed91eca1eaa96b79eae780778e89bb9ec44c1eeBehdad Esfahbod// 37842e56b97ce677b83bdab09cda48bc2d89ac75aJust// The LLVM Compiler Infrastructure 47842e56b97ce677b83bdab09cda48bc2d89ac75aJust// 57842e56b97ce677b83bdab09cda48bc2d89ac75aJust// This file is distributed under the University of Illinois Open Source 67842e56b97ce677b83bdab09cda48bc2d89ac75aJust// License. See LICENSE.TXT for details. 77842e56b97ce677b83bdab09cda48bc2d89ac75aJust// 87842e56b97ce677b83bdab09cda48bc2d89ac75aJust//===----------------------------------------------------------------------===// 9960280bbd6277b56be45595a050a720a49fd5917Behdad Esfahbod 107842e56b97ce677b83bdab09cda48bc2d89ac75aJust#include "llvm/ADT/SparseSet.h" 117842e56b97ce677b83bdab09cda48bc2d89ac75aJust#include "gtest/gtest.h" 127842e56b97ce677b83bdab09cda48bc2d89ac75aJust 137842e56b97ce677b83bdab09cda48bc2d89ac75aJustusing namespace llvm; 147842e56b97ce677b83bdab09cda48bc2d89ac75aJust 157842e56b97ce677b83bdab09cda48bc2d89ac75aJustnamespace { 167842e56b97ce677b83bdab09cda48bc2d89ac75aJust 177842e56b97ce677b83bdab09cda48bc2d89ac75aJusttypedef SparseSet<unsigned> USet; 18f8fd4777d273836a1222b72f6761cb6fdf9ec87aJust 19f8fd4777d273836a1222b72f6761cb6fdf9ec87aJust// Empty set tests. 20f8fd4777d273836a1222b72f6761cb6fdf9ec87aJustTEST(SparseSetTest, EmptySet) { 21f8fd4777d273836a1222b72f6761cb6fdf9ec87aJust USet Set; 22f8fd4777d273836a1222b72f6761cb6fdf9ec87aJust EXPECT_TRUE(Set.empty()); 237842e56b97ce677b83bdab09cda48bc2d89ac75aJust EXPECT_TRUE(Set.begin() == Set.end()); 247842e56b97ce677b83bdab09cda48bc2d89ac75aJust EXPECT_EQ(0u, Set.size()); 257842e56b97ce677b83bdab09cda48bc2d89ac75aJust 267842e56b97ce677b83bdab09cda48bc2d89ac75aJust Set.setUniverse(10); 277842e56b97ce677b83bdab09cda48bc2d89ac75aJust 287842e56b97ce677b83bdab09cda48bc2d89ac75aJust // Lookups on empty set. 293a9fd301808f5a8991ca9ac44028d1ecb22d307fBehdad Esfahbod EXPECT_TRUE(Set.find(0) == Set.end()); 307842e56b97ce677b83bdab09cda48bc2d89ac75aJust EXPECT_TRUE(Set.find(9) == Set.end()); 317842e56b97ce677b83bdab09cda48bc2d89ac75aJust 32180ace6a5ff1399ec53bc696e8bef7cce6eef39aBehdad Esfahbod // Same thing on a const reference. 33cd5aad92f23737ff93a110d5c73d624658a28da8Behdad Esfahbod const USet &CSet = Set; 347842e56b97ce677b83bdab09cda48bc2d89ac75aJust EXPECT_TRUE(CSet.empty()); 357842e56b97ce677b83bdab09cda48bc2d89ac75aJust EXPECT_TRUE(CSet.begin() == CSet.end()); 367842e56b97ce677b83bdab09cda48bc2d89ac75aJust EXPECT_EQ(0u, CSet.size()); 377842e56b97ce677b83bdab09cda48bc2d89ac75aJust EXPECT_TRUE(CSet.find(0) == CSet.end()); 387842e56b97ce677b83bdab09cda48bc2d89ac75aJust USet::const_iterator I = CSet.find(5); 39b7fd2e19138b177403689bdd6989cfd2402aa2b3Behdad Esfahbod EXPECT_TRUE(I == CSet.end()); 40b7fd2e19138b177403689bdd6989cfd2402aa2b3Behdad Esfahbod} 41b7fd2e19138b177403689bdd6989cfd2402aa2b3Behdad Esfahbod 42b7fd2e19138b177403689bdd6989cfd2402aa2b3Behdad Esfahbod// Single entry set tests. 43TEST(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. 80TEST(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 161struct Alt { 162 unsigned Value; 163 explicit Alt(unsigned x) : Value(x) {} 164 unsigned getSparseSetIndex() const { return Value - 1000; } 165}; 166 167TEST(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} // namespace 187