1 //===- llvm/unittest/ADT/SmallSetTest.cpp ------------------------------===//
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 // SmallSet unit tests.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "llvm/ADT/SmallSet.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "gtest/gtest.h"
16 #include <string>
17
18 using namespace llvm;
19
TEST(SmallSetTest,Insert)20 TEST(SmallSetTest, Insert) {
21
22 SmallSet<int, 4> s1;
23
24 for (int i = 0; i < 4; i++)
25 s1.insert(i);
26
27 for (int i = 0; i < 4; i++)
28 s1.insert(i);
29
30 EXPECT_EQ(4u, s1.size());
31
32 for (int i = 0; i < 4; i++)
33 EXPECT_EQ(1u, s1.count(i));
34
35 EXPECT_EQ(0u, s1.count(4));
36 }
37
TEST(SmallSetTest,Grow)38 TEST(SmallSetTest, Grow) {
39 SmallSet<int, 4> s1;
40
41 for (int i = 0; i < 8; i++)
42 s1.insert(i);
43
44 EXPECT_EQ(8u, s1.size());
45
46 for (int i = 0; i < 8; i++)
47 EXPECT_EQ(1u, s1.count(i));
48
49 EXPECT_EQ(0u, s1.count(8));
50 }
51
TEST(SmallSetTest,Erase)52 TEST(SmallSetTest, Erase) {
53 SmallSet<int, 4> s1;
54
55 for (int i = 0; i < 8; i++)
56 s1.insert(i);
57
58 EXPECT_EQ(8u, s1.size());
59
60 // Remove elements one by one and check if all other elements are still there.
61 for (int i = 0; i < 8; i++) {
62 EXPECT_EQ(1u, s1.count(i));
63 EXPECT_TRUE(s1.erase(i));
64 EXPECT_EQ(0u, s1.count(i));
65 EXPECT_EQ(8u - i - 1, s1.size());
66 for (int j = i + 1; j < 8; j++)
67 EXPECT_EQ(1u, s1.count(j));
68 }
69
70 EXPECT_EQ(0u, s1.count(8));
71 }
72
TEST(SmallSetTest,IteratorInt)73 TEST(SmallSetTest, IteratorInt) {
74 SmallSet<int, 4> s1;
75
76 // Test the 'small' case.
77 for (int i = 0; i < 3; i++)
78 s1.insert(i);
79
80 std::vector<int> V(s1.begin(), s1.end());
81 // Make sure the elements are in the expected order.
82 llvm::sort(V);
83 for (int i = 0; i < 3; i++)
84 EXPECT_EQ(i, V[i]);
85
86 // Test the 'big' case by adding a few more elements to switch to std::set
87 // internally.
88 for (int i = 3; i < 6; i++)
89 s1.insert(i);
90
91 V.assign(s1.begin(), s1.end());
92 // Make sure the elements are in the expected order.
93 llvm::sort(V);
94 for (int i = 0; i < 6; i++)
95 EXPECT_EQ(i, V[i]);
96 }
97
TEST(SmallSetTest,IteratorString)98 TEST(SmallSetTest, IteratorString) {
99 // Test SmallSetIterator for SmallSet with a type with non-trivial
100 // ctors/dtors.
101 SmallSet<std::string, 2> s1;
102
103 s1.insert("str 1");
104 s1.insert("str 2");
105 s1.insert("str 1");
106
107 std::vector<std::string> V(s1.begin(), s1.end());
108 llvm::sort(V);
109 EXPECT_EQ(2u, s1.size());
110 EXPECT_EQ("str 1", V[0]);
111 EXPECT_EQ("str 2", V[1]);
112
113 s1.insert("str 4");
114 s1.insert("str 0");
115 s1.insert("str 4");
116
117 V.assign(s1.begin(), s1.end());
118 // Make sure the elements are in the expected order.
119 llvm::sort(V);
120 EXPECT_EQ(4u, s1.size());
121 EXPECT_EQ("str 0", V[0]);
122 EXPECT_EQ("str 1", V[1]);
123 EXPECT_EQ("str 2", V[2]);
124 EXPECT_EQ("str 4", V[3]);
125 }
126
TEST(SmallSetTest,IteratorIncMoveCopy)127 TEST(SmallSetTest, IteratorIncMoveCopy) {
128 // Test SmallSetIterator for SmallSet with a type with non-trivial
129 // ctors/dtors.
130 SmallSet<std::string, 2> s1;
131
132 s1.insert("str 1");
133 s1.insert("str 2");
134
135 auto Iter = s1.begin();
136 EXPECT_EQ("str 1", *Iter);
137 ++Iter;
138 EXPECT_EQ("str 2", *Iter);
139
140 s1.insert("str 4");
141 s1.insert("str 0");
142 auto Iter2 = s1.begin();
143 Iter = std::move(Iter2);
144 EXPECT_EQ("str 0", *Iter);
145 }
146
TEST(SmallSetTest,EqualityComparisonTest)147 TEST(SmallSetTest, EqualityComparisonTest) {
148 SmallSet<int, 8> s1small;
149 SmallSet<int, 10> s2small;
150 SmallSet<int, 3> s3large;
151 SmallSet<int, 8> s4large;
152
153 for (int i = 1; i < 5; i++) {
154 s1small.insert(i);
155 s2small.insert(5 - i);
156 s3large.insert(i);
157 }
158 for (int i = 1; i < 11; i++)
159 s4large.insert(i);
160
161 EXPECT_EQ(s1small, s1small);
162 EXPECT_EQ(s3large, s3large);
163
164 EXPECT_EQ(s1small, s2small);
165 EXPECT_EQ(s1small, s3large);
166 EXPECT_EQ(s2small, s3large);
167
168 EXPECT_NE(s1small, s4large);
169 EXPECT_NE(s4large, s3large);
170 }
171
TEST(SmallSetTest,Contains)172 TEST(SmallSetTest, Contains) {
173 SmallSet<int, 2> Set;
174 EXPECT_FALSE(Set.contains(0));
175 EXPECT_FALSE(Set.contains(1));
176
177 Set.insert(0);
178 Set.insert(1);
179 EXPECT_TRUE(Set.contains(0));
180 EXPECT_TRUE(Set.contains(1));
181
182 Set.insert(1);
183 EXPECT_TRUE(Set.contains(0));
184 EXPECT_TRUE(Set.contains(1));
185
186 Set.erase(1);
187 EXPECT_TRUE(Set.contains(0));
188 EXPECT_FALSE(Set.contains(1));
189
190 Set.insert(1);
191 Set.insert(2);
192 EXPECT_TRUE(Set.contains(0));
193 EXPECT_TRUE(Set.contains(1));
194 EXPECT_TRUE(Set.contains(2));
195 }
196