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
12using namespace llvm;
13
14namespace {
15
16typedef SparseSet<unsigned> USet;
17
18// Empty set tests.
19TEST(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.
42TEST(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.
81TEST(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
162struct Alt {
163 unsigned Value;
164 explicit Alt(unsigned x) : Value(x) {}
165 unsigned getSparseSetIndex() const { return Value - 1000; }
166};
167
168TEST(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
188TEST(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

source code of llvm/unittests/ADT/SparseSetTest.cpp