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.
TEST(SparseMultiSetTest,EmptySet)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.
TEST(SparseMultiSetTest,SingleEntrySet)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.
TEST(SparseMultiSetTest,MultipleEntrySet)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
TEST(SparseMultiSetTest,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;
Alt__anon554c0b5b0111::Alt210 explicit Alt(unsigned x) : Value(x) {}
getSparseSetIndex__anon554c0b5b0111::Alt211 unsigned getSparseSetIndex() const { return Value - 1000; }
212 };
213
TEST(SparseMultiSetTest,AltStructSet)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