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