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/SparseSet.h"
10 #include "gtest/gtest.h"
11
12 using namespace llvm;
13
14 namespace {
15
16 typedef SparseSet<unsigned> USet;
17
18 // Empty set tests.
TEST(SparseSetTest,EmptySet)19 TEST(SparseSetTest, EmptySet) {
20 USet Set;
21 EXPECT_TRUE(Set.empty());
22 EXPECT_TRUE(Set.begin() == Set.end());
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_TRUE(CSet.begin() == CSet.end());
35 EXPECT_EQ(0u, CSet.size());
36 EXPECT_TRUE(CSet.find(0) == CSet.end());
37 USet::const_iterator I = CSet.find(5);
38 EXPECT_TRUE(I == CSet.end());
39 }
40
41 // Single entry set tests.
TEST(SparseSetTest,SingleEntrySet)42 TEST(SparseSetTest, SingleEntrySet) {
43 USet Set;
44 Set.setUniverse(10);
45 std::pair<USet::iterator, bool> IP = Set.insert(5);
46 EXPECT_TRUE(IP.second);
47 EXPECT_TRUE(IP.first == Set.begin());
48
49 EXPECT_FALSE(Set.empty());
50 EXPECT_FALSE(Set.begin() == Set.end());
51 EXPECT_TRUE(Set.begin() + 1 == Set.end());
52 EXPECT_EQ(1u, Set.size());
53
54 EXPECT_TRUE(Set.find(0) == Set.end());
55 EXPECT_TRUE(Set.find(9) == Set.end());
56
57 EXPECT_FALSE(Set.count(0));
58 EXPECT_TRUE(Set.count(5));
59
60 // Redundant insert.
61 IP = Set.insert(5);
62 EXPECT_FALSE(IP.second);
63 EXPECT_TRUE(IP.first == Set.begin());
64
65 // Erase non-existent element.
66 EXPECT_FALSE(Set.erase(1));
67 EXPECT_EQ(1u, Set.size());
68 EXPECT_EQ(5u, *Set.begin());
69
70 // Erase iterator.
71 USet::iterator I = Set.find(5);
72 EXPECT_TRUE(I == Set.begin());
73 I = Set.erase(I);
74 EXPECT_TRUE(I == Set.end());
75 EXPECT_TRUE(Set.empty());
76 }
77
78 // Multiple entry set tests.
TEST(SparseSetTest,MultipleEntrySet)79 TEST(SparseSetTest, MultipleEntrySet) {
80 USet Set;
81 Set.setUniverse(10);
82
83 Set.insert(5);
84 Set.insert(3);
85 Set.insert(2);
86 Set.insert(1);
87 Set.insert(4);
88 EXPECT_EQ(5u, Set.size());
89
90 // Without deletions, iteration order == insertion order.
91 USet::const_iterator I = Set.begin();
92 EXPECT_EQ(5u, *I);
93 ++I;
94 EXPECT_EQ(3u, *I);
95 ++I;
96 EXPECT_EQ(2u, *I);
97 ++I;
98 EXPECT_EQ(1u, *I);
99 ++I;
100 EXPECT_EQ(4u, *I);
101 ++I;
102 EXPECT_TRUE(I == Set.end());
103
104 // Redundant insert.
105 std::pair<USet::iterator, bool> IP = Set.insert(3);
106 EXPECT_FALSE(IP.second);
107 EXPECT_TRUE(IP.first == Set.begin() + 1);
108
109 // Erase last element by key.
110 EXPECT_TRUE(Set.erase(4));
111 EXPECT_EQ(4u, Set.size());
112 EXPECT_FALSE(Set.count(4));
113 EXPECT_FALSE(Set.erase(4));
114 EXPECT_EQ(4u, Set.size());
115 EXPECT_FALSE(Set.count(4));
116
117 // Erase first element by key.
118 EXPECT_TRUE(Set.count(5));
119 EXPECT_TRUE(Set.find(5) == Set.begin());
120 EXPECT_TRUE(Set.erase(5));
121 EXPECT_EQ(3u, Set.size());
122 EXPECT_FALSE(Set.count(5));
123 EXPECT_FALSE(Set.erase(5));
124 EXPECT_EQ(3u, Set.size());
125 EXPECT_FALSE(Set.count(5));
126
127 Set.insert(6);
128 Set.insert(7);
129 EXPECT_EQ(5u, Set.size());
130
131 // Erase last element by iterator.
132 I = Set.erase(Set.end() - 1);
133 EXPECT_TRUE(I == Set.end());
134 EXPECT_EQ(4u, Set.size());
135
136 // Erase second element by iterator.
137 I = Set.erase(Set.begin() + 1);
138 EXPECT_TRUE(I == Set.begin() + 1);
139
140 // Clear and resize the universe.
141 Set.clear();
142 EXPECT_FALSE(Set.count(5));
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.erase(i);
151
152 for (unsigned i = 100; i != 800; ++i)
153 EXPECT_TRUE(Set.count(i));
154
155 EXPECT_FALSE(Set.count(99));
156 EXPECT_FALSE(Set.count(800));
157 EXPECT_EQ(700u, Set.size());
158 }
159
160 struct Alt {
161 unsigned Value;
Alt__anon3f20d3970111::Alt162 explicit Alt(unsigned x) : Value(x) {}
getSparseSetIndex__anon3f20d3970111::Alt163 unsigned getSparseSetIndex() const { return Value - 1000; }
164 };
165
TEST(SparseSetTest,AltStructSet)166 TEST(SparseSetTest, AltStructSet) {
167 typedef SparseSet<Alt> ASet;
168 ASet Set;
169 Set.setUniverse(10);
170 Set.insert(Alt(1005));
171
172 ASet::iterator I = Set.find(5);
173 ASSERT_TRUE(I == Set.begin());
174 EXPECT_EQ(1005u, I->Value);
175
176 Set.insert(Alt(1006));
177 Set.insert(Alt(1006));
178 I = Set.erase(Set.begin());
179 ASSERT_TRUE(I == Set.begin());
180 EXPECT_EQ(1006u, I->Value);
181
182 EXPECT_FALSE(Set.erase(5));
183 EXPECT_TRUE(Set.erase(6));
184 }
185
TEST(SparseSetTest,PopBack)186 TEST(SparseSetTest, PopBack) {
187 USet Set;
188 const unsigned UpperBound = 300;
189 Set.setUniverse(UpperBound);
190 for (unsigned i = 0; i < UpperBound; ++i)
191 Set.insert(i);
192
193 // Make sure pop back returns the values in the reverse order we
194 // inserted them.
195 unsigned Expected = UpperBound;
196 while (!Set.empty())
197 ASSERT_TRUE(--Expected == Set.pop_back_val());
198
199 // Insert again the same elements in the sparse set and make sure
200 // each insertion actually inserts the elements. I.e., check
201 // that the underlying data structure are properly cleared.
202 for (unsigned i = 0; i < UpperBound; ++i)
203 ASSERT_TRUE(Set.insert(i).second);
204 }
205 } // namespace
206