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_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.
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.
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;
162   explicit Alt(unsigned x) : Value(x) {}
163   unsigned getSparseSetIndex() const { return Value - 1000; }
164 };
165 
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 
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