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. |
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(Key: 5); |
38 | EXPECT_TRUE(I == CSet.end()); |
39 | } |
40 | |
41 | // Single entry set tests. |
42 | TEST(SparseSetTest, SingleEntrySet) { |
43 | USet Set; |
44 | Set.setUniverse(10); |
45 | std::pair<USet::iterator, bool> IP = Set.insert(Val: 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(Val: 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(Key: 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. |
81 | TEST(SparseSetTest, MultipleEntrySet) { |
82 | USet Set; |
83 | Set.setUniverse(10); |
84 | |
85 | Set.insert(Val: 5); |
86 | Set.insert(Val: 3); |
87 | Set.insert(Val: 2); |
88 | Set.insert(Val: 1); |
89 | Set.insert(Val: 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(Val: 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(Val: 6); |
130 | Set.insert(Val: 7); |
131 | EXPECT_EQ(5u, Set.size()); |
132 | |
133 | // Erase last element by iterator. |
134 | I = Set.erase(I: 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(I: 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(Val: i); |
150 | |
151 | for (unsigned i = 0; i != 10; ++i) |
152 | Set.erase(Key: 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; |
164 | explicit Alt(unsigned x) : Value(x) {} |
165 | unsigned getSparseSetIndex() const { return Value - 1000; } |
166 | }; |
167 | |
168 | TEST(SparseSetTest, AltStructSet) { |
169 | typedef SparseSet<Alt> ASet; |
170 | ASet Set; |
171 | Set.setUniverse(10); |
172 | Set.insert(Val: Alt(1005)); |
173 | |
174 | ASet::iterator I = Set.find(Key: 5); |
175 | ASSERT_TRUE(I == Set.begin()); |
176 | EXPECT_EQ(1005u, I->Value); |
177 | |
178 | Set.insert(Val: Alt(1006)); |
179 | Set.insert(Val: Alt(1006)); |
180 | I = Set.erase(I: 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 | |
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(Val: 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 | |