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 "gmock/gmock.h" 16 #include "gtest/gtest.h" 17 #include <string> 18 19 using namespace llvm; 20 21 TEST(SmallSetTest, ConstructorIteratorPair) { 22 std::initializer_list<int> L = {1, 2, 3, 4, 5}; 23 SmallSet<int, 4> S(std::begin(L), std::end(L)); 24 EXPECT_THAT(S, testing::UnorderedElementsAreArray(L)); 25 } 26 27 TEST(SmallSet, ConstructorRange) { 28 std::initializer_list<int> L = {1, 2, 3, 4, 5}; 29 30 SmallSet<int, 4> S(llvm::make_range(std::begin(L), std::end(L))); 31 EXPECT_THAT(S, testing::UnorderedElementsAreArray(L)); 32 } 33 34 TEST(SmallSet, ConstructorInitializerList) { 35 std::initializer_list<int> L = {1, 2, 3, 4, 5}; 36 SmallSet<int, 4> S = {1, 2, 3, 4, 5}; 37 EXPECT_THAT(S, testing::UnorderedElementsAreArray(L)); 38 } 39 40 TEST(SmallSet, CopyConstructor) { 41 SmallSet<int, 4> S = {1, 2, 3}; 42 SmallSet<int, 4> T = S; 43 44 EXPECT_THAT(S, testing::ContainerEq(T)); 45 } 46 47 TEST(SmallSet, MoveConstructor) { 48 std::initializer_list<int> L = {1, 2, 3}; 49 SmallSet<int, 4> S = L; 50 SmallSet<int, 4> T = std::move(S); 51 52 EXPECT_THAT(T, testing::UnorderedElementsAreArray(L)); 53 } 54 55 TEST(SmallSet, CopyAssignment) { 56 SmallSet<int, 4> S = {1, 2, 3}; 57 SmallSet<int, 4> T; 58 T = S; 59 60 EXPECT_THAT(S, testing::ContainerEq(T)); 61 } 62 63 TEST(SmallSet, MoveAssignment) { 64 std::initializer_list<int> L = {1, 2, 3}; 65 SmallSet<int, 4> S = L; 66 SmallSet<int, 4> T; 67 T = std::move(S); 68 69 EXPECT_THAT(T, testing::UnorderedElementsAreArray(L)); 70 } 71 72 TEST(SmallSetTest, Insert) { 73 74 SmallSet<int, 4> s1; 75 76 for (int i = 0; i < 4; i++) { 77 auto InsertResult = s1.insert(i); 78 EXPECT_EQ(*InsertResult.first, i); 79 EXPECT_EQ(InsertResult.second, true); 80 } 81 82 for (int i = 0; i < 4; i++) { 83 auto InsertResult = s1.insert(i); 84 EXPECT_EQ(*InsertResult.first, i); 85 EXPECT_EQ(InsertResult.second, false); 86 } 87 88 EXPECT_EQ(4u, s1.size()); 89 90 for (int i = 0; i < 4; i++) 91 EXPECT_EQ(1u, s1.count(i)); 92 93 EXPECT_EQ(0u, s1.count(4)); 94 } 95 96 TEST(SmallSetTest, InsertPerfectFwd) { 97 struct Value { 98 int Key; 99 bool Moved; 100 101 Value(int Key) : Key(Key), Moved(false) {} 102 Value(const Value &) = default; 103 Value(Value &&Other) : Key(Other.Key), Moved(false) { Other.Moved = true; } 104 bool operator==(const Value &Other) const { return Key == Other.Key; } 105 bool operator<(const Value &Other) const { return Key < Other.Key; } 106 }; 107 108 { 109 SmallSet<Value, 4> S; 110 Value V1(1), V2(2); 111 112 S.insert(V1); 113 EXPECT_EQ(V1.Moved, false); 114 115 S.insert(std::move(V2)); 116 EXPECT_EQ(V2.Moved, true); 117 } 118 { 119 SmallSet<Value, 1> S; 120 Value V1(1), V2(2); 121 122 S.insert(V1); 123 EXPECT_EQ(V1.Moved, false); 124 125 S.insert(std::move(V2)); 126 EXPECT_EQ(V2.Moved, true); 127 } 128 } 129 130 TEST(SmallSetTest, Grow) { 131 SmallSet<int, 4> s1; 132 133 for (int i = 0; i < 8; i++) { 134 auto InsertResult = s1.insert(i); 135 EXPECT_EQ(*InsertResult.first, i); 136 EXPECT_EQ(InsertResult.second, true); 137 } 138 139 for (int i = 0; i < 8; i++) { 140 auto InsertResult = s1.insert(i); 141 EXPECT_EQ(*InsertResult.first, i); 142 EXPECT_EQ(InsertResult.second, false); 143 } 144 145 EXPECT_EQ(8u, s1.size()); 146 147 for (int i = 0; i < 8; i++) 148 EXPECT_EQ(1u, s1.count(i)); 149 150 EXPECT_EQ(0u, s1.count(8)); 151 } 152 153 TEST(SmallSetTest, Erase) { 154 SmallSet<int, 4> s1; 155 156 for (int i = 0; i < 8; i++) 157 s1.insert(i); 158 159 EXPECT_EQ(8u, s1.size()); 160 161 // Remove elements one by one and check if all other elements are still there. 162 for (int i = 0; i < 8; i++) { 163 EXPECT_EQ(1u, s1.count(i)); 164 EXPECT_TRUE(s1.erase(i)); 165 EXPECT_EQ(0u, s1.count(i)); 166 EXPECT_EQ(8u - i - 1, s1.size()); 167 for (int j = i + 1; j < 8; j++) 168 EXPECT_EQ(1u, s1.count(j)); 169 } 170 171 EXPECT_EQ(0u, s1.count(8)); 172 } 173 174 TEST(SmallSetTest, IteratorInt) { 175 SmallSet<int, 4> s1; 176 177 // Test the 'small' case. 178 for (int i = 0; i < 3; i++) 179 s1.insert(i); 180 181 std::vector<int> V(s1.begin(), s1.end()); 182 // Make sure the elements are in the expected order. 183 llvm::sort(V); 184 for (int i = 0; i < 3; i++) 185 EXPECT_EQ(i, V[i]); 186 187 // Test the 'big' case by adding a few more elements to switch to std::set 188 // internally. 189 for (int i = 3; i < 6; i++) 190 s1.insert(i); 191 192 V.assign(s1.begin(), s1.end()); 193 // Make sure the elements are in the expected order. 194 llvm::sort(V); 195 for (int i = 0; i < 6; i++) 196 EXPECT_EQ(i, V[i]); 197 } 198 199 TEST(SmallSetTest, IteratorString) { 200 // Test SmallSetIterator for SmallSet with a type with non-trivial 201 // ctors/dtors. 202 SmallSet<std::string, 2> s1; 203 204 s1.insert("str 1"); 205 s1.insert("str 2"); 206 s1.insert("str 1"); 207 208 std::vector<std::string> V(s1.begin(), s1.end()); 209 llvm::sort(V); 210 EXPECT_EQ(2u, s1.size()); 211 EXPECT_EQ("str 1", V[0]); 212 EXPECT_EQ("str 2", V[1]); 213 214 s1.insert("str 4"); 215 s1.insert("str 0"); 216 s1.insert("str 4"); 217 218 V.assign(s1.begin(), s1.end()); 219 // Make sure the elements are in the expected order. 220 llvm::sort(V); 221 EXPECT_EQ(4u, s1.size()); 222 EXPECT_EQ("str 0", V[0]); 223 EXPECT_EQ("str 1", V[1]); 224 EXPECT_EQ("str 2", V[2]); 225 EXPECT_EQ("str 4", V[3]); 226 } 227 228 TEST(SmallSetTest, IteratorIncMoveCopy) { 229 // Test SmallSetIterator for SmallSet with a type with non-trivial 230 // ctors/dtors. 231 SmallSet<std::string, 2> s1; 232 233 s1.insert("str 1"); 234 s1.insert("str 2"); 235 236 auto Iter = s1.begin(); 237 EXPECT_EQ("str 1", *Iter); 238 ++Iter; 239 EXPECT_EQ("str 2", *Iter); 240 241 s1.insert("str 4"); 242 s1.insert("str 0"); 243 auto Iter2 = s1.begin(); 244 Iter = std::move(Iter2); 245 EXPECT_EQ("str 0", *Iter); 246 } 247 248 TEST(SmallSetTest, EqualityComparisonTest) { 249 SmallSet<int, 8> s1small; 250 SmallSet<int, 10> s2small; 251 SmallSet<int, 3> s3large; 252 SmallSet<int, 8> s4large; 253 254 for (int i = 1; i < 5; i++) { 255 s1small.insert(i); 256 s2small.insert(5 - i); 257 s3large.insert(i); 258 } 259 for (int i = 1; i < 11; i++) 260 s4large.insert(i); 261 262 EXPECT_EQ(s1small, s1small); 263 EXPECT_EQ(s3large, s3large); 264 265 EXPECT_EQ(s1small, s2small); 266 EXPECT_EQ(s1small, s3large); 267 EXPECT_EQ(s2small, s3large); 268 269 EXPECT_NE(s1small, s4large); 270 EXPECT_NE(s4large, s3large); 271 } 272 273 TEST(SmallSetTest, Contains) { 274 SmallSet<int, 2> Set; 275 EXPECT_FALSE(Set.contains(0)); 276 EXPECT_FALSE(Set.contains(1)); 277 278 Set.insert(0); 279 Set.insert(1); 280 EXPECT_TRUE(Set.contains(0)); 281 EXPECT_TRUE(Set.contains(1)); 282 283 Set.insert(1); 284 EXPECT_TRUE(Set.contains(0)); 285 EXPECT_TRUE(Set.contains(1)); 286 287 Set.erase(1); 288 EXPECT_TRUE(Set.contains(0)); 289 EXPECT_FALSE(Set.contains(1)); 290 291 Set.insert(1); 292 Set.insert(2); 293 EXPECT_TRUE(Set.contains(0)); 294 EXPECT_TRUE(Set.contains(1)); 295 EXPECT_TRUE(Set.contains(2)); 296 } 297