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
13 using namespace llvm;
14
15 namespace {
16
17 typedef SparseSet<unsigned> USet;
18
19 // Empty set tests.
TEST(SparseSetTest,EmptySet)20 TEST(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.
TEST(SparseSetTest,SingleEntrySet)43 TEST(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.
TEST(SparseSetTest,MultipleEntrySet)80 TEST(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
161 struct Alt {
162 unsigned Value;
Alt__anon7a64ee740111::Alt163 explicit Alt(unsigned x) : Value(x) {}
getSparseSetKey__anon7a64ee740111::Alt164 unsigned getSparseSetKey() const { return Value - 1000; }
165 };
166
TEST(SparseSetTest,AltStructSet)167 TEST(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