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/SparseMultiSet.h" |
10 | #include "gtest/gtest.h" |
11 | |
12 | using namespace llvm; |
13 | |
14 | namespace { |
15 | |
16 | typedef SparseMultiSet<unsigned> USet; |
17 | |
18 | // Empty set tests. |
19 | TEST(SparseMultiSetTest, EmptySet) { |
20 | USet Set; |
21 | EXPECT_TRUE(Set.empty()); |
22 | EXPECT_EQ(0u, Set.size()); |
23 | |
24 | Set.setUniverse(10); |
25 | |
26 | // Lookups on empty set. |
27 | EXPECT_TRUE(Set.find(0) == Set.end()); |
28 | EXPECT_TRUE(Set.find(9) == Set.end()); |
29 | |
30 | // Same thing on a const reference. |
31 | const USet &CSet = Set; |
32 | EXPECT_TRUE(CSet.empty()); |
33 | EXPECT_EQ(0u, CSet.size()); |
34 | EXPECT_TRUE(CSet.find(0) == CSet.end()); |
35 | USet::const_iterator I = CSet.find(Key: 5); |
36 | EXPECT_TRUE(I == CSet.end()); |
37 | } |
38 | |
39 | // Single entry set tests. |
40 | TEST(SparseMultiSetTest, SingleEntrySet) { |
41 | USet Set; |
42 | Set.setUniverse(10); |
43 | USet::iterator I = Set.insert(Val: 5); |
44 | EXPECT_TRUE(I != Set.end()); |
45 | EXPECT_TRUE(*I == 5); |
46 | |
47 | EXPECT_FALSE(Set.empty()); |
48 | EXPECT_EQ(1u, Set.size()); |
49 | |
50 | EXPECT_TRUE(Set.find(0) == Set.end()); |
51 | EXPECT_TRUE(Set.find(9) == Set.end()); |
52 | |
53 | EXPECT_FALSE(Set.contains(0)); |
54 | EXPECT_TRUE(Set.contains(5)); |
55 | |
56 | // Extra insert. |
57 | I = Set.insert(Val: 5); |
58 | EXPECT_TRUE(I != Set.end()); |
59 | EXPECT_TRUE(I == ++Set.find(5)); |
60 | I--; |
61 | EXPECT_TRUE(I == Set.find(5)); |
62 | |
63 | // Erase non-existent element. |
64 | I = Set.find(Key: 1); |
65 | EXPECT_TRUE(I == Set.end()); |
66 | EXPECT_EQ(2u, Set.size()); |
67 | EXPECT_EQ(5u, *Set.find(5)); |
68 | |
69 | // Erase iterator. |
70 | I = Set.find(Key: 5); |
71 | EXPECT_TRUE(I != Set.end()); |
72 | I = Set.erase(I); |
73 | EXPECT_TRUE(I != Set.end()); |
74 | I = Set.erase(I); |
75 | EXPECT_TRUE(I == Set.end()); |
76 | EXPECT_TRUE(Set.empty()); |
77 | } |
78 | |
79 | // Multiple entry set tests. |
80 | TEST(SparseMultiSetTest, MultipleEntrySet) { |
81 | USet Set; |
82 | Set.setUniverse(10); |
83 | |
84 | Set.insert(Val: 5); |
85 | Set.insert(Val: 5); |
86 | Set.insert(Val: 5); |
87 | Set.insert(Val: 3); |
88 | Set.insert(Val: 2); |
89 | Set.insert(Val: 1); |
90 | Set.insert(Val: 4); |
91 | EXPECT_EQ(7u, Set.size()); |
92 | |
93 | // Erase last element by key. |
94 | EXPECT_TRUE(Set.erase(Set.find(4)) == Set.end()); |
95 | EXPECT_EQ(6u, Set.size()); |
96 | EXPECT_FALSE(Set.contains(4)); |
97 | EXPECT_TRUE(Set.find(4) == Set.end()); |
98 | |
99 | // Erase first element by key. |
100 | EXPECT_EQ(3u, Set.count(5)); |
101 | EXPECT_TRUE(Set.find(5) != Set.end()); |
102 | EXPECT_TRUE(Set.erase(Set.find(5)) != Set.end()); |
103 | EXPECT_EQ(5u, Set.size()); |
104 | EXPECT_EQ(2u, Set.count(5)); |
105 | |
106 | Set.insert(Val: 6); |
107 | Set.insert(Val: 7); |
108 | EXPECT_EQ(7u, Set.size()); |
109 | |
110 | // Erase tail by iterator. |
111 | EXPECT_TRUE(Set.getTail(6) == Set.getHead(6)); |
112 | USet::iterator I = Set.erase(I: Set.find(Key: 6)); |
113 | EXPECT_TRUE(I == Set.end()); |
114 | EXPECT_EQ(6u, Set.size()); |
115 | |
116 | // Erase tails by iterator. |
117 | EXPECT_EQ(2u, Set.count(5)); |
118 | I = Set.getTail(Key: 5); |
119 | I = Set.erase(I); |
120 | EXPECT_TRUE(I == Set.end()); |
121 | --I; |
122 | EXPECT_EQ(1u, Set.count(5)); |
123 | EXPECT_EQ(5u, *I); |
124 | I = Set.erase(I); |
125 | EXPECT_TRUE(I == Set.end()); |
126 | EXPECT_EQ(0u, Set.count(5)); |
127 | |
128 | Set.insert(Val: 8); |
129 | Set.insert(Val: 8); |
130 | Set.insert(Val: 8); |
131 | Set.insert(Val: 8); |
132 | Set.insert(Val: 8); |
133 | |
134 | // Erase all the 8s |
135 | EXPECT_EQ(5, std::distance(Set.getHead(8), Set.end())); |
136 | Set.eraseAll(K: 8); |
137 | EXPECT_EQ(0, std::distance(Set.getHead(8), Set.end())); |
138 | |
139 | // Clear and resize the universe. |
140 | Set.clear(); |
141 | EXPECT_EQ(0u, Set.size()); |
142 | EXPECT_FALSE(Set.contains(3)); |
143 | Set.setUniverse(1000); |
144 | |
145 | // Add more than 256 elements. |
146 | for (unsigned i = 100; i != 800; ++i) |
147 | Set.insert(Val: i); |
148 | |
149 | for (unsigned i = 0; i != 10; ++i) |
150 | Set.eraseAll(K: i); |
151 | |
152 | for (unsigned i = 100; i != 800; ++i) |
153 | EXPECT_EQ(1u, Set.count(i)); |
154 | |
155 | EXPECT_FALSE(Set.contains(99)); |
156 | EXPECT_FALSE(Set.contains(800)); |
157 | EXPECT_EQ(700u, Set.size()); |
158 | } |
159 | |
160 | // Test out iterators |
161 | TEST(SparseMultiSetTest, Iterators) { |
162 | USet Set; |
163 | Set.setUniverse(100); |
164 | |
165 | Set.insert(Val: 0); |
166 | Set.insert(Val: 1); |
167 | Set.insert(Val: 2); |
168 | Set.insert(Val: 0); |
169 | Set.insert(Val: 1); |
170 | Set.insert(Val: 0); |
171 | |
172 | USet::RangePair RangePair = Set.equal_range(K: 0); |
173 | USet::iterator B = RangePair.first; |
174 | USet::iterator E = RangePair.second; |
175 | |
176 | // Move the iterators around, going to end and coming back. |
177 | EXPECT_EQ(3, std::distance(B, E)); |
178 | EXPECT_EQ(B, --(--(--E))); |
179 | EXPECT_EQ(++(++(++E)), Set.end()); |
180 | EXPECT_EQ(B, --(--(--E))); |
181 | EXPECT_EQ(++(++(++E)), Set.end()); |
182 | |
183 | // Insert into the tail, and move around again |
184 | Set.insert(Val: 0); |
185 | EXPECT_EQ(B, --(--(--(--E)))); |
186 | EXPECT_EQ(++(++(++(++E))), Set.end()); |
187 | EXPECT_EQ(B, --(--(--(--E)))); |
188 | EXPECT_EQ(++(++(++(++E))), Set.end()); |
189 | |
190 | // Erase a tail, and move around again |
191 | USet::iterator Erased = Set.erase(I: Set.getTail(Key: 0)); |
192 | EXPECT_EQ(Erased, E); |
193 | EXPECT_EQ(B, --(--(--E))); |
194 | |
195 | USet Set2; |
196 | Set2.setUniverse(11); |
197 | Set2.insert(Val: 3); |
198 | EXPECT_TRUE(!Set2.contains(0)); |
199 | EXPECT_TRUE(!Set.contains(3)); |
200 | |
201 | EXPECT_EQ(Set2.getHead(3), Set2.getTail(3)); |
202 | EXPECT_EQ(Set2.getHead(0), Set2.getTail(0)); |
203 | B = Set2.find(Key: 3); |
204 | EXPECT_EQ(Set2.find(3), --(++B)); |
205 | } |
206 | |
207 | struct Alt { |
208 | unsigned Value; |
209 | explicit Alt(unsigned x) : Value(x) {} |
210 | unsigned getSparseSetIndex() const { return Value - 1000; } |
211 | }; |
212 | |
213 | TEST(SparseMultiSetTest, AltStructSet) { |
214 | typedef SparseMultiSet<Alt> ASet; |
215 | ASet Set; |
216 | Set.setUniverse(10); |
217 | Set.insert(Val: Alt(1005)); |
218 | |
219 | ASet::iterator I = Set.find(Key: 5); |
220 | ASSERT_TRUE(I != Set.end()); |
221 | EXPECT_EQ(1005u, I->Value); |
222 | |
223 | Set.insert(Val: Alt(1006)); |
224 | Set.insert(Val: Alt(1006)); |
225 | I = Set.erase(I: Set.find(Key: 6)); |
226 | ASSERT_TRUE(I != Set.end()); |
227 | EXPECT_EQ(1006u, I->Value); |
228 | I = Set.erase(I: Set.find(Key: 6)); |
229 | ASSERT_TRUE(I == Set.end()); |
230 | |
231 | EXPECT_TRUE(Set.contains(5)); |
232 | EXPECT_FALSE(Set.contains(6)); |
233 | } |
234 | } // namespace |
235 | |