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/SparseSet.h"
11#include "gtest/gtest.h"
12
13using namespace llvm;
14
15namespace {
16
17typedef SparseSet<unsigned> USet;
18
19// Empty set tests.
20TEST(SparseSetTest, EmptySet) {
21  USet Set;
22  EXPECT_TRUE(Set.empty());
23  EXPECT_TRUE(Set.begin() == Set.end());
24  EXPECT_EQ(0u, Set.size());
25
26  Set.setUniverse(10);
27
28  // Lookups on empty set.
29  EXPECT_TRUE(Set.find(0) == Set.end());
30  EXPECT_TRUE(Set.find(9) == Set.end());
31
32  // Same thing on a const reference.
33  const USet &CSet = Set;
34  EXPECT_TRUE(CSet.empty());
35  EXPECT_TRUE(CSet.begin() == CSet.end());
36  EXPECT_EQ(0u, CSet.size());
37  EXPECT_TRUE(CSet.find(0) == CSet.end());
38  USet::const_iterator I = CSet.find(5);
39  EXPECT_TRUE(I == CSet.end());
40}
41
42// Single entry set tests.
43TEST(SparseSetTest, SingleEntrySet) {
44  USet Set;
45  Set.setUniverse(10);
46  std::pair<USet::iterator, bool> IP = Set.insert(5);
47  EXPECT_TRUE(IP.second);
48  EXPECT_TRUE(IP.first == Set.begin());
49
50  EXPECT_FALSE(Set.empty());
51  EXPECT_FALSE(Set.begin() == Set.end());
52  EXPECT_TRUE(Set.begin() + 1 == Set.end());
53  EXPECT_EQ(1u, Set.size());
54
55  EXPECT_TRUE(Set.find(0) == Set.end());
56  EXPECT_TRUE(Set.find(9) == Set.end());
57
58  EXPECT_FALSE(Set.count(0));
59  EXPECT_TRUE(Set.count(5));
60
61  // Redundant insert.
62  IP = Set.insert(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(5);
73  EXPECT_TRUE(I == Set.begin());
74  I = Set.erase(I);
75  EXPECT_TRUE(I == Set.end());
76  EXPECT_TRUE(Set.empty());
77}
78
79// Multiple entry set tests.
80TEST(SparseSetTest, MultipleEntrySet) {
81  USet Set;
82  Set.setUniverse(10);
83
84  Set.insert(5);
85  Set.insert(3);
86  Set.insert(2);
87  Set.insert(1);
88  Set.insert(4);
89  EXPECT_EQ(5u, Set.size());
90
91  // Without deletions, iteration order == insertion order.
92  USet::const_iterator I = Set.begin();
93  EXPECT_EQ(5u, *I);
94  ++I;
95  EXPECT_EQ(3u, *I);
96  ++I;
97  EXPECT_EQ(2u, *I);
98  ++I;
99  EXPECT_EQ(1u, *I);
100  ++I;
101  EXPECT_EQ(4u, *I);
102  ++I;
103  EXPECT_TRUE(I == Set.end());
104
105  // Redundant insert.
106  std::pair<USet::iterator, bool> IP = Set.insert(3);
107  EXPECT_FALSE(IP.second);
108  EXPECT_TRUE(IP.first == Set.begin() + 1);
109
110  // Erase last element by key.
111  EXPECT_TRUE(Set.erase(4));
112  EXPECT_EQ(4u, Set.size());
113  EXPECT_FALSE(Set.count(4));
114  EXPECT_FALSE(Set.erase(4));
115  EXPECT_EQ(4u, Set.size());
116  EXPECT_FALSE(Set.count(4));
117
118  // Erase first element by key.
119  EXPECT_TRUE(Set.count(5));
120  EXPECT_TRUE(Set.find(5) == Set.begin());
121  EXPECT_TRUE(Set.erase(5));
122  EXPECT_EQ(3u, Set.size());
123  EXPECT_FALSE(Set.count(5));
124  EXPECT_FALSE(Set.erase(5));
125  EXPECT_EQ(3u, Set.size());
126  EXPECT_FALSE(Set.count(5));
127
128  Set.insert(6);
129  Set.insert(7);
130  EXPECT_EQ(5u, Set.size());
131
132  // Erase last element by iterator.
133  I = Set.erase(Set.end() - 1);
134  EXPECT_TRUE(I == Set.end());
135  EXPECT_EQ(4u, Set.size());
136
137  // Erase second element by iterator.
138  I = Set.erase(Set.begin() + 1);
139  EXPECT_TRUE(I == Set.begin() + 1);
140
141  // Clear and resize the universe.
142  Set.clear();
143  EXPECT_FALSE(Set.count(5));
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.erase(i);
152
153  for (unsigned i = 100; i != 800; ++i)
154    EXPECT_TRUE(Set.count(i));
155
156  EXPECT_FALSE(Set.count(99));
157  EXPECT_FALSE(Set.count(800));
158  EXPECT_EQ(700u, Set.size());
159}
160
161struct Alt {
162  unsigned Value;
163  explicit Alt(unsigned x) : Value(x) {}
164  unsigned getSparseSetIndex() const { return Value - 1000; }
165};
166
167TEST(SparseSetTest, AltStructSet) {
168  typedef SparseSet<Alt> ASet;
169  ASet Set;
170  Set.setUniverse(10);
171  Set.insert(Alt(1005));
172
173  ASet::iterator I = Set.find(5);
174  ASSERT_TRUE(I == Set.begin());
175  EXPECT_EQ(1005u, I->Value);
176
177  Set.insert(Alt(1006));
178  Set.insert(Alt(1006));
179  I = Set.erase(Set.begin());
180  ASSERT_TRUE(I == Set.begin());
181  EXPECT_EQ(1006u, I->Value);
182
183  EXPECT_FALSE(Set.erase(5));
184  EXPECT_TRUE(Set.erase(6));
185}
186} // namespace
187