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