| 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(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(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(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(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(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(i); |
| 94 |
|
| 95 |
std::vector<int> V(s1.begin(), s1.end()); |
| 96 |
// Make sure the elements are in the expected order. |
| 97 |
llvm::sort(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(i); |
| 105 |
|
| 106 |
V.assign(s1.begin(), s1.end()); |
| 107 |
// Make sure the elements are in the expected order. |
| 108 |
llvm::sort(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("str 1"); |
| 119 |
s1.insert("str 2"); |
| 120 |
s1.insert("str 1"); |
| 121 |
|
| 122 |
std::vector<std::string> V(s1.begin(), s1.end()); |
| 123 |
llvm::sort(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("str 4"); |
| 129 |
s1.insert("str 0"); |
| 130 |
s1.insert("str 4"); |
| 131 |
|
| 132 |
V.assign(s1.begin(), s1.end()); |
| 133 |
// Make sure the elements are in the expected order. |
| 134 |
llvm::sort(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("str 1"); |
| 148 |
s1.insert("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("str 4"); |
| 156 |
s1.insert("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(i); |
| 170 |
s2small.insert(5 - i); |
| 171 |
s3large.insert(i); |
| 172 |
} |
| 173 |
for (int i = 1; i < 11; i++) |
| 174 |
s4large.insert(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(0); |
| 193 |
Set.insert(1); |
| 194 |
EXPECT_TRUE(Set.contains(0)); |
| 195 |
EXPECT_TRUE(Set.contains(1)); |
| 196 |
|
| 197 |
Set.insert(1); |
| 198 |
EXPECT_TRUE(Set.contains(0)); |
| 199 |
EXPECT_TRUE(Set.contains(1)); |
| 200 |
|
| 201 |
Set.erase(1); |
| 202 |
EXPECT_TRUE(Set.contains(0)); |
| 203 |
EXPECT_FALSE(Set.contains(1)); |
| 204 |
|
| 205 |
Set.insert(1); |
| 206 |
Set.insert(2); |
| 207 |
EXPECT_TRUE(Set.contains(0)); |
| 208 |
EXPECT_TRUE(Set.contains(1)); |
| 209 |
EXPECT_TRUE(Set.contains(2)); |
| 210 |
} |