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_FALSE(Set.contains(0));
29 EXPECT_FALSE(Set.contains(9));
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_FALSE(CSet.contains(0));
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_FALSE(Set.contains(0));
55 EXPECT_FALSE(Set.contains(9));
56 EXPECT_TRUE(Set.contains(5));
57
58 EXPECT_FALSE(Set.count(0));
59 EXPECT_TRUE(Set.count(5));
60
61 // Redundant insert.
62 IP = Set.insert(5);
63 EXPECT_FALSE(IP.second);
64 EXPECT_TRUE(IP.first == Set.begin());
65
66 // Erase non-existent element.
67 EXPECT_FALSE(Set.erase(1));
68 EXPECT_EQ(1u, Set.size());
69 EXPECT_EQ(5u, *Set.begin());
70
71 // Erase iterator.
72 USet::iterator I = Set.find(5);
73 EXPECT_TRUE(I == Set.begin());
74 I = Set.erase(I);
75 EXPECT_FALSE(Set.contains(5));
76 EXPECT_TRUE(I == Set.end());
77 EXPECT_TRUE(Set.empty());
78 }
79
80 // Multiple entry set tests.
TEST(SparseSetTest,MultipleEntrySet)81 TEST(SparseSetTest, MultipleEntrySet) {
82 USet Set;
83 Set.setUniverse(10);
84
85 Set.insert(5);
86 Set.insert(3);
87 Set.insert(2);
88 Set.insert(1);
89 Set.insert(4);
90 EXPECT_EQ(5u, Set.size());
91
92 // Without deletions, iteration order == insertion order.
93 USet::const_iterator I = Set.begin();
94 EXPECT_EQ(5u, *I);
95 ++I;
96 EXPECT_EQ(3u, *I);
97 ++I;
98 EXPECT_EQ(2u, *I);
99 ++I;
100 EXPECT_EQ(1u, *I);
101 ++I;
102 EXPECT_EQ(4u, *I);
103 ++I;
104 EXPECT_TRUE(I == Set.end());
105
106 // Redundant insert.
107 std::pair<USet::iterator, bool> IP = Set.insert(3);
108 EXPECT_FALSE(IP.second);
109 EXPECT_TRUE(IP.first == Set.begin() + 1);
110
111 // Erase last element by key.
112 EXPECT_TRUE(Set.erase(4));
113 EXPECT_EQ(4u, Set.size());
114 EXPECT_FALSE(Set.count(4));
115 EXPECT_FALSE(Set.erase(4));
116 EXPECT_EQ(4u, Set.size());
117 EXPECT_FALSE(Set.count(4));
118
119 // Erase first element by key.
120 EXPECT_TRUE(Set.count(5));
121 EXPECT_TRUE(Set.find(5) == Set.begin());
122 EXPECT_TRUE(Set.erase(5));
123 EXPECT_EQ(3u, Set.size());
124 EXPECT_FALSE(Set.count(5));
125 EXPECT_FALSE(Set.erase(5));
126 EXPECT_EQ(3u, Set.size());
127 EXPECT_FALSE(Set.count(5));
128
129 Set.insert(6);
130 Set.insert(7);
131 EXPECT_EQ(5u, Set.size());
132
133 // Erase last element by iterator.
134 I = Set.erase(Set.end() - 1);
135 EXPECT_TRUE(I == Set.end());
136 EXPECT_EQ(4u, Set.size());
137
138 // Erase second element by iterator.
139 I = Set.erase(Set.begin() + 1);
140 EXPECT_TRUE(I == Set.begin() + 1);
141
142 // Clear and resize the universe.
143 Set.clear();
144 EXPECT_FALSE(Set.count(5));
145 Set.setUniverse(1000);
146
147 // Add more than 256 elements.
148 for (unsigned i = 100; i != 800; ++i)
149 Set.insert(i);
150
151 for (unsigned i = 0; i != 10; ++i)
152 Set.erase(i);
153
154 for (unsigned i = 100; i != 800; ++i)
155 EXPECT_TRUE(Set.count(i));
156
157 EXPECT_FALSE(Set.count(99));
158 EXPECT_FALSE(Set.count(800));
159 EXPECT_EQ(700u, Set.size());
160 }
161
162 struct Alt {
163 unsigned Value;
Alt__anonfd004f270111::Alt164 explicit Alt(unsigned x) : Value(x) {}
getSparseSetIndex__anonfd004f270111::Alt165 unsigned getSparseSetIndex() const { return Value - 1000; }
166 };
167
TEST(SparseSetTest,AltStructSet)168 TEST(SparseSetTest, AltStructSet) {
169 typedef SparseSet<Alt> ASet;
170 ASet Set;
171 Set.setUniverse(10);
172 Set.insert(Alt(1005));
173
174 ASet::iterator I = Set.find(5);
175 ASSERT_TRUE(I == Set.begin());
176 EXPECT_EQ(1005u, I->Value);
177
178 Set.insert(Alt(1006));
179 Set.insert(Alt(1006));
180 I = Set.erase(Set.begin());
181 ASSERT_TRUE(I == Set.begin());
182 EXPECT_EQ(1006u, I->Value);
183
184 EXPECT_FALSE(Set.erase(5));
185 EXPECT_TRUE(Set.erase(6));
186 }
187
TEST(SparseSetTest,PopBack)188 TEST(SparseSetTest, PopBack) {
189 USet Set;
190 const unsigned UpperBound = 300;
191 Set.setUniverse(UpperBound);
192 for (unsigned i = 0; i < UpperBound; ++i)
193 Set.insert(i);
194
195 // Make sure pop back returns the values in the reverse order we
196 // inserted them.
197 unsigned Expected = UpperBound;
198 while (!Set.empty())
199 ASSERT_TRUE(--Expected == Set.pop_back_val());
200
201 // Insert again the same elements in the sparse set and make sure
202 // each insertion actually inserts the elements. I.e., check
203 // that the underlying data structure are properly cleared.
204 for (unsigned i = 0; i < UpperBound; ++i)
205 ASSERT_TRUE(Set.insert(i).second);
206 }
207 } // namespace
208