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