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 236
