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.
TEST(SparseMultiSetTest,EmptySet)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(5);
36 EXPECT_TRUE(I == CSet.end());
37 }
38
39 // Single entry set tests.
TEST(SparseMultiSetTest,SingleEntrySet)40 TEST(SparseMultiSetTest, SingleEntrySet) {
41 USet Set;
42 Set.setUniverse(10);
43 USet::iterator I = Set.insert(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(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(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(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.
TEST(SparseMultiSetTest,MultipleEntrySet)80 TEST(SparseMultiSetTest, MultipleEntrySet) {
81 USet Set;
82 Set.setUniverse(10);
83
84 Set.insert(5);
85 Set.insert(5);
86 Set.insert(5);
87 Set.insert(3);
88 Set.insert(2);
89 Set.insert(1);
90 Set.insert(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(6);
107 Set.insert(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(Set.find(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(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(8);
129 Set.insert(8);
130 Set.insert(8);
131 Set.insert(8);
132 Set.insert(8);
133
134 // Erase all the 8s
135 EXPECT_EQ(5, std::distance(Set.getHead(8), Set.end()));
136 Set.eraseAll(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(i);
148
149 for (unsigned i = 0; i != 10; ++i)
150 Set.eraseAll(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
TEST(SparseMultiSetTest,Iterators)161 TEST(SparseMultiSetTest, Iterators) {
162 USet Set;
163 Set.setUniverse(100);
164
165 Set.insert(0);
166 Set.insert(1);
167 Set.insert(2);
168 Set.insert(0);
169 Set.insert(1);
170 Set.insert(0);
171
172 USet::RangePair RangePair = Set.equal_range(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(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(Set.getTail(0));
192 EXPECT_EQ(Erased, E);
193 EXPECT_EQ(B, --(--(--E)));
194
195 USet Set2;
196 Set2.setUniverse(11);
197 Set2.insert(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(3);
204 EXPECT_EQ(Set2.find(3), --(++B));
205 }
206
207 struct Alt {
208 unsigned Value;
Alt__anon314879870111::Alt209 explicit Alt(unsigned x) : Value(x) {}
getSparseSetIndex__anon314879870111::Alt210 unsigned getSparseSetIndex() const { return Value - 1000; }
211 };
212
TEST(SparseMultiSetTest,AltStructSet)213 TEST(SparseMultiSetTest, AltStructSet) {
214 typedef SparseMultiSet<Alt> ASet;
215 ASet Set;
216 Set.setUniverse(10);
217 Set.insert(Alt(1005));
218
219 ASet::iterator I = Set.find(5);
220 ASSERT_TRUE(I != Set.end());
221 EXPECT_EQ(1005u, I->Value);
222
223 Set.insert(Alt(1006));
224 Set.insert(Alt(1006));
225 I = Set.erase(Set.find(6));
226 ASSERT_TRUE(I != Set.end());
227 EXPECT_EQ(1006u, I->Value);
228 I = Set.erase(Set.find(6));
229 ASSERT_TRUE(I == Set.end());
230
231 EXPECT_TRUE(Set.contains(5));
232 EXPECT_FALSE(Set.contains(6));
233 }
234 } // namespace
235