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

source code of llvm/unittests/ADT/SmallSetTest.cpp