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/SparseMultiSet.h"
10 #include "gtest/gtest.h"
11 
12 using namespace llvm;
13 
14 namespace {
15 
16 typedef SparseMultiSet<unsigned> USet;
17 
18 // Empty set tests.
19 TEST(SparseMultiSetTest, EmptySet) {
20   USet Set;
21   EXPECT_TRUE(Set.empty());
22   EXPECT_EQ(0u, Set.size());
23 
24   Set.setUniverse(10);
25 
26   // Lookups on empty set.
27   EXPECT_TRUE(Set.find(0) == Set.end());
28   EXPECT_TRUE(Set.find(9) == Set.end());
29 
30   // Same thing on a const reference.
31   const USet &CSet = Set;
32   EXPECT_TRUE(CSet.empty());
33   EXPECT_EQ(0u, CSet.size());
34   EXPECT_TRUE(CSet.find(0) == CSet.end());
35   USet::const_iterator I = CSet.find(5);
36   EXPECT_TRUE(I == CSet.end());
37 }
38 
39 // Single entry set tests.
40 TEST(SparseMultiSetTest, SingleEntrySet) {
41   USet Set;
42   Set.setUniverse(10);
43   USet::iterator I = Set.insert(5);
44   EXPECT_TRUE(I != Set.end());
45   EXPECT_TRUE(*I == 5);
46 
47   EXPECT_FALSE(Set.empty());
48   EXPECT_EQ(1u, Set.size());
49 
50   EXPECT_TRUE(Set.find(0) == Set.end());
51   EXPECT_TRUE(Set.find(9) == Set.end());
52 
53   EXPECT_FALSE(Set.contains(0));
54   EXPECT_TRUE(Set.contains(5));
55 
56   // Extra insert.
57   I = Set.insert(5);
58   EXPECT_TRUE(I != Set.end());
59   EXPECT_TRUE(I == ++Set.find(5));
60   I--;
61   EXPECT_TRUE(I == Set.find(5));
62 
63   // Erase non-existent element.
64   I = Set.find(1);
65   EXPECT_TRUE(I == Set.end());
66   EXPECT_EQ(2u, Set.size());
67   EXPECT_EQ(5u, *Set.find(5));
68 
69   // Erase iterator.
70   I = Set.find(5);
71   EXPECT_TRUE(I != Set.end());
72   I = Set.erase(I);
73   EXPECT_TRUE(I != Set.end());
74   I = Set.erase(I);
75   EXPECT_TRUE(I == Set.end());
76   EXPECT_TRUE(Set.empty());
77 }
78 
79 // Multiple entry set tests.
80 TEST(SparseMultiSetTest, MultipleEntrySet) {
81   USet Set;
82   Set.setUniverse(10);
83 
84   Set.insert(5);
85   Set.insert(5);
86   Set.insert(5);
87   Set.insert(3);
88   Set.insert(2);
89   Set.insert(1);
90   Set.insert(4);
91   EXPECT_EQ(7u, Set.size());
92 
93   // Erase last element by key.
94   EXPECT_TRUE(Set.erase(Set.find(4)) == Set.end());
95   EXPECT_EQ(6u, Set.size());
96   EXPECT_FALSE(Set.contains(4));
97   EXPECT_TRUE(Set.find(4) == Set.end());
98 
99   // Erase first element by key.
100   EXPECT_EQ(3u, Set.count(5));
101   EXPECT_TRUE(Set.find(5) != Set.end());
102   EXPECT_TRUE(Set.erase(Set.find(5)) != Set.end());
103   EXPECT_EQ(5u, Set.size());
104   EXPECT_EQ(2u, Set.count(5));
105 
106   Set.insert(6);
107   Set.insert(7);
108   EXPECT_EQ(7u, Set.size());
109 
110   // Erase tail by iterator.
111   EXPECT_TRUE(Set.getTail(6) == Set.getHead(6));
112   USet::iterator I = Set.erase(Set.find(6));
113   EXPECT_TRUE(I == Set.end());
114   EXPECT_EQ(6u, Set.size());
115 
116   // Erase tails by iterator.
117   EXPECT_EQ(2u, Set.count(5));
118   I = Set.getTail(5);
119   I = Set.erase(I);
120   EXPECT_TRUE(I == Set.end());
121   --I;
122   EXPECT_EQ(1u, Set.count(5));
123   EXPECT_EQ(5u, *I);
124   I = Set.erase(I);
125   EXPECT_TRUE(I == Set.end());
126   EXPECT_EQ(0u, Set.count(5));
127 
128   Set.insert(8);
129   Set.insert(8);
130   Set.insert(8);
131   Set.insert(8);
132   Set.insert(8);
133 
134   // Erase all the 8s
135   EXPECT_EQ(5, std::distance(Set.getHead(8), Set.end()));
136   Set.eraseAll(8);
137   EXPECT_EQ(0, std::distance(Set.getHead(8), Set.end()));
138 
139   // Clear and resize the universe.
140   Set.clear();
141   EXPECT_EQ(0u, Set.size());
142   EXPECT_FALSE(Set.contains(3));
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.eraseAll(i);
151 
152   for (unsigned i = 100; i != 800; ++i)
153     EXPECT_EQ(1u, Set.count(i));
154 
155   EXPECT_FALSE(Set.contains(99));
156   EXPECT_FALSE(Set.contains(800));
157   EXPECT_EQ(700u, Set.size());
158 }
159 
160 // Test out iterators
161 TEST(SparseMultiSetTest, Iterators) {
162   USet Set;
163   Set.setUniverse(100);
164 
165   Set.insert(0);
166   Set.insert(1);
167   Set.insert(2);
168   Set.insert(0);
169   Set.insert(1);
170   Set.insert(0);
171 
172   USet::RangePair RangePair = Set.equal_range(0);
173   USet::iterator B = RangePair.first;
174   USet::iterator E = RangePair.second;
175 
176   // Move the iterators around, going to end and coming back.
177   EXPECT_EQ(3, std::distance(B, E));
178   EXPECT_EQ(B, --(--(--E)));
179   EXPECT_EQ(++(++(++E)), Set.end());
180   EXPECT_EQ(B, --(--(--E)));
181   EXPECT_EQ(++(++(++E)), Set.end());
182 
183   // Insert into the tail, and move around again
184   Set.insert(0);
185   EXPECT_EQ(B, --(--(--(--E))));
186   EXPECT_EQ(++(++(++(++E))), Set.end());
187   EXPECT_EQ(B, --(--(--(--E))));
188   EXPECT_EQ(++(++(++(++E))), Set.end());
189 
190   // Erase a tail, and move around again
191   USet::iterator Erased = Set.erase(Set.getTail(0));
192   EXPECT_EQ(Erased, E);
193   EXPECT_EQ(B, --(--(--E)));
194 
195   USet Set2;
196   Set2.setUniverse(11);
197   Set2.insert(3);
198   EXPECT_TRUE(!Set2.contains(0));
199   EXPECT_TRUE(!Set.contains(3));
200 
201   EXPECT_EQ(Set2.getHead(3), Set2.getTail(3));
202   EXPECT_EQ(Set2.getHead(0), Set2.getTail(0));
203   B = Set2.find(3);
204   EXPECT_EQ(Set2.find(3), --(++B));
205 }
206 
207 struct Alt {
208   unsigned Value;
209   explicit Alt(unsigned x) : Value(x) {}
210   unsigned getSparseSetIndex() const { return Value - 1000; }
211 };
212 
213 TEST(SparseMultiSetTest, AltStructSet) {
214   typedef SparseMultiSet<Alt> ASet;
215   ASet Set;
216   Set.setUniverse(10);
217   Set.insert(Alt(1005));
218 
219   ASet::iterator I = Set.find(5);
220   ASSERT_TRUE(I != Set.end());
221   EXPECT_EQ(1005u, I->Value);
222 
223   Set.insert(Alt(1006));
224   Set.insert(Alt(1006));
225   I = Set.erase(Set.find(6));
226   ASSERT_TRUE(I != Set.end());
227   EXPECT_EQ(1006u, I->Value);
228   I = Set.erase(Set.find(6));
229   ASSERT_TRUE(I == Set.end());
230 
231   EXPECT_TRUE(Set.contains(5));
232   EXPECT_FALSE(Set.contains(6));
233 }
234 } // namespace
235