1 //===- llvm/unittest/ADT/SmallPtrSetTest.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 // SmallPtrSet unit tests. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/ADT/SmallPtrSet.h" 14 #include "llvm/ADT/PointerIntPair.h" 15 #include "llvm/Support/PointerLikeTypeTraits.h" 16 #include "gtest/gtest.h" 17 18 using namespace llvm; 19 20 TEST(SmallPtrSetTest, Assignment) { 21 int buf[8]; 22 for (int i = 0; i < 8; ++i) 23 buf[i] = 0; 24 25 SmallPtrSet<int *, 4> s1 = {&buf[0], &buf[1]}; 26 SmallPtrSet<int *, 4> s2; 27 (s2 = s1).insert(&buf[2]); 28 29 // Self assign as well. 30 (s2 = static_cast<SmallPtrSet<int *, 4> &>(s2)).insert(&buf[3]); 31 32 s1 = s2; 33 EXPECT_EQ(4U, s1.size()); 34 for (int i = 0; i < 8; ++i) 35 if (i < 4) 36 EXPECT_TRUE(s1.count(&buf[i])); 37 else 38 EXPECT_FALSE(s1.count(&buf[i])); 39 40 // Assign and insert with initializer lists, and ones that contain both 41 // duplicates and out-of-order elements. 42 (s2 = {&buf[6], &buf[7], &buf[6]}).insert({&buf[5], &buf[4]}); 43 for (int i = 0; i < 8; ++i) 44 if (i < 4) 45 EXPECT_FALSE(s2.count(&buf[i])); 46 else 47 EXPECT_TRUE(s2.count(&buf[i])); 48 } 49 50 TEST(SmallPtrSetTest, GrowthTest) { 51 int i; 52 int buf[8]; 53 for(i=0; i<8; ++i) buf[i]=0; 54 55 56 SmallPtrSet<int *, 4> s; 57 typedef SmallPtrSet<int *, 4>::iterator iter; 58 59 s.insert(&buf[0]); 60 s.insert(&buf[1]); 61 s.insert(&buf[2]); 62 s.insert(&buf[3]); 63 EXPECT_EQ(4U, s.size()); 64 65 i = 0; 66 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) 67 (**I)++; 68 EXPECT_EQ(4, i); 69 for(i=0; i<8; ++i) 70 EXPECT_EQ(i<4?1:0,buf[i]); 71 72 s.insert(&buf[4]); 73 s.insert(&buf[5]); 74 s.insert(&buf[6]); 75 s.insert(&buf[7]); 76 77 i = 0; 78 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) 79 (**I)++; 80 EXPECT_EQ(8, i); 81 s.erase(&buf[4]); 82 s.erase(&buf[5]); 83 s.erase(&buf[6]); 84 s.erase(&buf[7]); 85 EXPECT_EQ(4U, s.size()); 86 87 i = 0; 88 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) 89 (**I)++; 90 EXPECT_EQ(4, i); 91 for(i=0; i<8; ++i) 92 EXPECT_EQ(i<4?3:1,buf[i]); 93 94 s.clear(); 95 for(i=0; i<8; ++i) buf[i]=0; 96 for(i=0; i<128; ++i) s.insert(&buf[i%8]); // test repeated entires 97 EXPECT_EQ(8U, s.size()); 98 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) 99 (**I)++; 100 for(i=0; i<8; ++i) 101 EXPECT_EQ(1,buf[i]); 102 } 103 104 TEST(SmallPtrSetTest, CopyAndMoveTest) { 105 int buf[8]; 106 for (int i = 0; i < 8; ++i) 107 buf[i] = 0; 108 109 SmallPtrSet<int *, 4> s1; 110 s1.insert(&buf[0]); 111 s1.insert(&buf[1]); 112 s1.insert(&buf[2]); 113 s1.insert(&buf[3]); 114 EXPECT_EQ(4U, s1.size()); 115 for (int i = 0; i < 8; ++i) 116 if (i < 4) 117 EXPECT_TRUE(s1.count(&buf[i])); 118 else 119 EXPECT_FALSE(s1.count(&buf[i])); 120 121 SmallPtrSet<int *, 4> s2(s1); 122 EXPECT_EQ(4U, s2.size()); 123 for (int i = 0; i < 8; ++i) 124 if (i < 4) 125 EXPECT_TRUE(s2.count(&buf[i])); 126 else 127 EXPECT_FALSE(s2.count(&buf[i])); 128 129 s1 = s2; 130 EXPECT_EQ(4U, s1.size()); 131 EXPECT_EQ(4U, s2.size()); 132 for (int i = 0; i < 8; ++i) 133 if (i < 4) 134 EXPECT_TRUE(s1.count(&buf[i])); 135 else 136 EXPECT_FALSE(s1.count(&buf[i])); 137 138 SmallPtrSet<int *, 4> s3(std::move(s1)); 139 EXPECT_EQ(4U, s3.size()); 140 EXPECT_TRUE(s1.empty()); 141 for (int i = 0; i < 8; ++i) 142 if (i < 4) 143 EXPECT_TRUE(s3.count(&buf[i])); 144 else 145 EXPECT_FALSE(s3.count(&buf[i])); 146 147 // Move assign into the moved-from object. Also test move of a non-small 148 // container. 149 s3.insert(&buf[4]); 150 s3.insert(&buf[5]); 151 s3.insert(&buf[6]); 152 s3.insert(&buf[7]); 153 s1 = std::move(s3); 154 EXPECT_EQ(8U, s1.size()); 155 EXPECT_TRUE(s3.empty()); 156 for (int i = 0; i < 8; ++i) 157 EXPECT_TRUE(s1.count(&buf[i])); 158 159 // Copy assign into a moved-from object. 160 s3 = s1; 161 EXPECT_EQ(8U, s3.size()); 162 EXPECT_EQ(8U, s1.size()); 163 for (int i = 0; i < 8; ++i) 164 EXPECT_TRUE(s3.count(&buf[i])); 165 } 166 167 TEST(SmallPtrSetTest, SwapTest) { 168 int buf[10]; 169 170 SmallPtrSet<int *, 2> a; 171 SmallPtrSet<int *, 2> b; 172 173 a.insert(&buf[0]); 174 a.insert(&buf[1]); 175 b.insert(&buf[2]); 176 177 EXPECT_EQ(2U, a.size()); 178 EXPECT_EQ(1U, b.size()); 179 EXPECT_TRUE(a.count(&buf[0])); 180 EXPECT_TRUE(a.count(&buf[1])); 181 EXPECT_FALSE(a.count(&buf[2])); 182 EXPECT_FALSE(a.count(&buf[3])); 183 EXPECT_FALSE(b.count(&buf[0])); 184 EXPECT_FALSE(b.count(&buf[1])); 185 EXPECT_TRUE(b.count(&buf[2])); 186 EXPECT_FALSE(b.count(&buf[3])); 187 188 std::swap(a, b); 189 190 EXPECT_EQ(1U, a.size()); 191 EXPECT_EQ(2U, b.size()); 192 EXPECT_FALSE(a.count(&buf[0])); 193 EXPECT_FALSE(a.count(&buf[1])); 194 EXPECT_TRUE(a.count(&buf[2])); 195 EXPECT_FALSE(a.count(&buf[3])); 196 EXPECT_TRUE(b.count(&buf[0])); 197 EXPECT_TRUE(b.count(&buf[1])); 198 EXPECT_FALSE(b.count(&buf[2])); 199 EXPECT_FALSE(b.count(&buf[3])); 200 201 b.insert(&buf[3]); 202 std::swap(a, b); 203 204 EXPECT_EQ(3U, a.size()); 205 EXPECT_EQ(1U, b.size()); 206 EXPECT_TRUE(a.count(&buf[0])); 207 EXPECT_TRUE(a.count(&buf[1])); 208 EXPECT_FALSE(a.count(&buf[2])); 209 EXPECT_TRUE(a.count(&buf[3])); 210 EXPECT_FALSE(b.count(&buf[0])); 211 EXPECT_FALSE(b.count(&buf[1])); 212 EXPECT_TRUE(b.count(&buf[2])); 213 EXPECT_FALSE(b.count(&buf[3])); 214 215 std::swap(a, b); 216 217 EXPECT_EQ(1U, a.size()); 218 EXPECT_EQ(3U, b.size()); 219 EXPECT_FALSE(a.count(&buf[0])); 220 EXPECT_FALSE(a.count(&buf[1])); 221 EXPECT_TRUE(a.count(&buf[2])); 222 EXPECT_FALSE(a.count(&buf[3])); 223 EXPECT_TRUE(b.count(&buf[0])); 224 EXPECT_TRUE(b.count(&buf[1])); 225 EXPECT_FALSE(b.count(&buf[2])); 226 EXPECT_TRUE(b.count(&buf[3])); 227 228 a.insert(&buf[4]); 229 a.insert(&buf[5]); 230 a.insert(&buf[6]); 231 232 std::swap(b, a); 233 234 EXPECT_EQ(3U, a.size()); 235 EXPECT_EQ(4U, b.size()); 236 EXPECT_TRUE(b.count(&buf[2])); 237 EXPECT_TRUE(b.count(&buf[4])); 238 EXPECT_TRUE(b.count(&buf[5])); 239 EXPECT_TRUE(b.count(&buf[6])); 240 EXPECT_TRUE(a.count(&buf[0])); 241 EXPECT_TRUE(a.count(&buf[1])); 242 EXPECT_TRUE(a.count(&buf[3])); 243 } 244 245 void checkEraseAndIterators(SmallPtrSetImpl<int*> &S) { 246 int buf[3]; 247 248 S.insert(&buf[0]); 249 S.insert(&buf[1]); 250 S.insert(&buf[2]); 251 252 // Iterators must still be valid after erase() calls; 253 auto B = S.begin(); 254 auto M = std::next(B); 255 auto E = S.end(); 256 EXPECT_TRUE(*B == &buf[0] || *B == &buf[1] || *B == &buf[2]); 257 EXPECT_TRUE(*M == &buf[0] || *M == &buf[1] || *M == &buf[2]); 258 EXPECT_TRUE(*B != *M); 259 int *Removable = *std::next(M); 260 // No iterator points to Removable now. 261 EXPECT_TRUE(Removable == &buf[0] || Removable == &buf[1] || 262 Removable == &buf[2]); 263 EXPECT_TRUE(Removable != *B && Removable != *M); 264 265 S.erase(Removable); 266 267 // B,M,E iterators should still be valid 268 EXPECT_EQ(B, S.begin()); 269 EXPECT_EQ(M, std::next(B)); 270 EXPECT_EQ(E, S.end()); 271 EXPECT_EQ(std::next(M), E); 272 } 273 274 TEST(SmallPtrSetTest, EraseTest) { 275 // Test when set stays small. 276 SmallPtrSet<int *, 8> B; 277 checkEraseAndIterators(B); 278 279 // Test when set grows big. 280 SmallPtrSet<int *, 2> A; 281 checkEraseAndIterators(A); 282 } 283 284 // Verify that dereferencing and iteration work. 285 TEST(SmallPtrSetTest, dereferenceAndIterate) { 286 int Ints[] = {0, 1, 2, 3, 4, 5, 6, 7}; 287 SmallPtrSet<const int *, 4> S; 288 for (int &I : Ints) { 289 EXPECT_EQ(&I, *S.insert(&I).first); 290 EXPECT_EQ(&I, *S.find(&I)); 291 } 292 293 // Iterate from each and count how many times each element is found. 294 int Found[sizeof(Ints)/sizeof(int)] = {0}; 295 for (int &I : Ints) 296 for (auto F = S.find(&I), E = S.end(); F != E; ++F) 297 ++Found[*F - Ints]; 298 299 // Sort. We should hit the first element just once and the final element N 300 // times. 301 llvm::sort(std::begin(Found), std::end(Found)); 302 for (auto F = std::begin(Found), E = std::end(Found); F != E; ++F) 303 EXPECT_EQ(F - Found + 1, *F); 304 } 305 306 // Verify that const pointers work for count and find even when the underlying 307 // SmallPtrSet is not for a const pointer type. 308 TEST(SmallPtrSetTest, ConstTest) { 309 SmallPtrSet<int *, 8> IntSet; 310 int A; 311 int *B = &A; 312 const int *C = &A; 313 IntSet.insert(B); 314 EXPECT_EQ(IntSet.count(B), 1u); 315 EXPECT_EQ(IntSet.count(C), 1u); 316 EXPECT_NE(IntSet.find(B), IntSet.end()); 317 EXPECT_NE(IntSet.find(C), IntSet.end()); 318 } 319 320 // Verify that we automatically get the const version of PointerLikeTypeTraits 321 // filled in for us, even for a non-pointer type 322 using TestPair = PointerIntPair<int *, 1>; 323 324 TEST(SmallPtrSetTest, ConstNonPtrTest) { 325 SmallPtrSet<TestPair, 8> IntSet; 326 int A[1]; 327 TestPair Pair(&A[0], 1); 328 IntSet.insert(Pair); 329 EXPECT_EQ(IntSet.count(Pair), 1u); 330 EXPECT_NE(IntSet.find(Pair), IntSet.end()); 331 } 332