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 | |
20 | TEST(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 | |
44 | TEST(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 | |
67 | TEST(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 | |
88 | TEST(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 | |
113 | TEST(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 | |
142 | TEST(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 | |
162 | TEST(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 | |
187 | TEST(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 | |