1 //===- llvm/unittest/ADT/SmallPtrSetTest.cpp ------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // SmallPtrSet unit tests. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "gtest/gtest.h" 15 #include "llvm/ADT/SmallPtrSet.h" 16 17 using namespace llvm; 18 19 TEST(SmallPtrSetTest, Assignment) { 20 int buf[8]; 21 for (int i = 0; i < 8; ++i) 22 buf[i] = 0; 23 24 SmallPtrSet<int *, 4> s1; 25 s1.insert(&buf[0]); 26 s1.insert(&buf[1]); 27 28 SmallPtrSet<int *, 4> s2; 29 (s2 = s1).insert(&buf[2]); 30 31 // Self assign as well. 32 (s2 = s2).insert(&buf[3]); 33 34 s1 = s2; 35 EXPECT_EQ(4U, s1.size()); 36 for (int i = 0; i < 8; ++i) 37 if (i < 4) 38 EXPECT_TRUE(s1.count(&buf[i])); 39 else 40 EXPECT_FALSE(s1.count(&buf[i])); 41 } 42 43 TEST(SmallPtrSetTest, GrowthTest) { 44 int i; 45 int buf[8]; 46 for(i=0; i<8; ++i) buf[i]=0; 47 48 49 SmallPtrSet<int *, 4> s; 50 typedef SmallPtrSet<int *, 4>::iterator iter; 51 52 s.insert(&buf[0]); 53 s.insert(&buf[1]); 54 s.insert(&buf[2]); 55 s.insert(&buf[3]); 56 EXPECT_EQ(4U, s.size()); 57 58 i = 0; 59 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) 60 (**I)++; 61 EXPECT_EQ(4, i); 62 for(i=0; i<8; ++i) 63 EXPECT_EQ(i<4?1:0,buf[i]); 64 65 s.insert(&buf[4]); 66 s.insert(&buf[5]); 67 s.insert(&buf[6]); 68 s.insert(&buf[7]); 69 70 i = 0; 71 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) 72 (**I)++; 73 EXPECT_EQ(8, i); 74 s.erase(&buf[4]); 75 s.erase(&buf[5]); 76 s.erase(&buf[6]); 77 s.erase(&buf[7]); 78 EXPECT_EQ(4U, s.size()); 79 80 i = 0; 81 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) 82 (**I)++; 83 EXPECT_EQ(4, i); 84 for(i=0; i<8; ++i) 85 EXPECT_EQ(i<4?3:1,buf[i]); 86 87 s.clear(); 88 for(i=0; i<8; ++i) buf[i]=0; 89 for(i=0; i<128; ++i) s.insert(&buf[i%8]); // test repeated entires 90 EXPECT_EQ(8U, s.size()); 91 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) 92 (**I)++; 93 for(i=0; i<8; ++i) 94 EXPECT_EQ(1,buf[i]); 95 } 96 97 TEST(SmallPtrSetTest, CopyAndMoveTest) { 98 int buf[8]; 99 for (int i = 0; i < 8; ++i) 100 buf[i] = 0; 101 102 SmallPtrSet<int *, 4> s1; 103 s1.insert(&buf[0]); 104 s1.insert(&buf[1]); 105 s1.insert(&buf[2]); 106 s1.insert(&buf[3]); 107 EXPECT_EQ(4U, s1.size()); 108 for (int i = 0; i < 8; ++i) 109 if (i < 4) 110 EXPECT_TRUE(s1.count(&buf[i])); 111 else 112 EXPECT_FALSE(s1.count(&buf[i])); 113 114 SmallPtrSet<int *, 4> s2(s1); 115 EXPECT_EQ(4U, s2.size()); 116 for (int i = 0; i < 8; ++i) 117 if (i < 4) 118 EXPECT_TRUE(s2.count(&buf[i])); 119 else 120 EXPECT_FALSE(s2.count(&buf[i])); 121 122 s1 = s2; 123 EXPECT_EQ(4U, s1.size()); 124 EXPECT_EQ(4U, s2.size()); 125 for (int i = 0; i < 8; ++i) 126 if (i < 4) 127 EXPECT_TRUE(s1.count(&buf[i])); 128 else 129 EXPECT_FALSE(s1.count(&buf[i])); 130 131 SmallPtrSet<int *, 4> s3(std::move(s1)); 132 EXPECT_EQ(4U, s3.size()); 133 EXPECT_TRUE(s1.empty()); 134 for (int i = 0; i < 8; ++i) 135 if (i < 4) 136 EXPECT_TRUE(s3.count(&buf[i])); 137 else 138 EXPECT_FALSE(s3.count(&buf[i])); 139 140 // Move assign into the moved-from object. Also test move of a non-small 141 // container. 142 s3.insert(&buf[4]); 143 s3.insert(&buf[5]); 144 s3.insert(&buf[6]); 145 s3.insert(&buf[7]); 146 s1 = std::move(s3); 147 EXPECT_EQ(8U, s1.size()); 148 EXPECT_TRUE(s3.empty()); 149 for (int i = 0; i < 8; ++i) 150 EXPECT_TRUE(s1.count(&buf[i])); 151 152 // Copy assign into a moved-from object. 153 s3 = s1; 154 EXPECT_EQ(8U, s3.size()); 155 EXPECT_EQ(8U, s1.size()); 156 for (int i = 0; i < 8; ++i) 157 EXPECT_TRUE(s3.count(&buf[i])); 158 } 159 160 TEST(SmallPtrSetTest, SwapTest) { 161 int buf[10]; 162 163 SmallPtrSet<int *, 2> a; 164 SmallPtrSet<int *, 2> b; 165 166 a.insert(&buf[0]); 167 a.insert(&buf[1]); 168 b.insert(&buf[2]); 169 170 EXPECT_EQ(2U, a.size()); 171 EXPECT_EQ(1U, b.size()); 172 EXPECT_TRUE(a.count(&buf[0])); 173 EXPECT_TRUE(a.count(&buf[1])); 174 EXPECT_FALSE(a.count(&buf[2])); 175 EXPECT_FALSE(a.count(&buf[3])); 176 EXPECT_FALSE(b.count(&buf[0])); 177 EXPECT_FALSE(b.count(&buf[1])); 178 EXPECT_TRUE(b.count(&buf[2])); 179 EXPECT_FALSE(b.count(&buf[3])); 180 181 std::swap(a, b); 182 183 EXPECT_EQ(1U, a.size()); 184 EXPECT_EQ(2U, b.size()); 185 EXPECT_FALSE(a.count(&buf[0])); 186 EXPECT_FALSE(a.count(&buf[1])); 187 EXPECT_TRUE(a.count(&buf[2])); 188 EXPECT_FALSE(a.count(&buf[3])); 189 EXPECT_TRUE(b.count(&buf[0])); 190 EXPECT_TRUE(b.count(&buf[1])); 191 EXPECT_FALSE(b.count(&buf[2])); 192 EXPECT_FALSE(b.count(&buf[3])); 193 194 b.insert(&buf[3]); 195 std::swap(a, b); 196 197 EXPECT_EQ(3U, a.size()); 198 EXPECT_EQ(1U, b.size()); 199 EXPECT_TRUE(a.count(&buf[0])); 200 EXPECT_TRUE(a.count(&buf[1])); 201 EXPECT_FALSE(a.count(&buf[2])); 202 EXPECT_TRUE(a.count(&buf[3])); 203 EXPECT_FALSE(b.count(&buf[0])); 204 EXPECT_FALSE(b.count(&buf[1])); 205 EXPECT_TRUE(b.count(&buf[2])); 206 EXPECT_FALSE(b.count(&buf[3])); 207 208 std::swap(a, b); 209 210 EXPECT_EQ(1U, a.size()); 211 EXPECT_EQ(3U, b.size()); 212 EXPECT_FALSE(a.count(&buf[0])); 213 EXPECT_FALSE(a.count(&buf[1])); 214 EXPECT_TRUE(a.count(&buf[2])); 215 EXPECT_FALSE(a.count(&buf[3])); 216 EXPECT_TRUE(b.count(&buf[0])); 217 EXPECT_TRUE(b.count(&buf[1])); 218 EXPECT_FALSE(b.count(&buf[2])); 219 EXPECT_TRUE(b.count(&buf[3])); 220 221 a.insert(&buf[4]); 222 a.insert(&buf[5]); 223 a.insert(&buf[6]); 224 225 std::swap(b, a); 226 227 EXPECT_EQ(3U, a.size()); 228 EXPECT_EQ(4U, b.size()); 229 EXPECT_TRUE(b.count(&buf[2])); 230 EXPECT_TRUE(b.count(&buf[4])); 231 EXPECT_TRUE(b.count(&buf[5])); 232 EXPECT_TRUE(b.count(&buf[6])); 233 EXPECT_TRUE(a.count(&buf[0])); 234 EXPECT_TRUE(a.count(&buf[1])); 235 EXPECT_TRUE(a.count(&buf[3])); 236 } 237 238 void checkEraseAndIterators(SmallPtrSetImpl<int*> &S) { 239 int buf[3]; 240 241 S.insert(&buf[0]); 242 S.insert(&buf[1]); 243 S.insert(&buf[2]); 244 245 // Iterators must still be valid after erase() calls; 246 auto B = S.begin(); 247 auto M = std::next(B); 248 auto E = S.end(); 249 EXPECT_TRUE(*B == &buf[0] || *B == &buf[1] || *B == &buf[2]); 250 EXPECT_TRUE(*M == &buf[0] || *M == &buf[1] || *M == &buf[2]); 251 EXPECT_TRUE(*B != *M); 252 int *Removable = *std::next(M); 253 // No iterator points to Removable now. 254 EXPECT_TRUE(Removable == &buf[0] || Removable == &buf[1] || 255 Removable == &buf[2]); 256 EXPECT_TRUE(Removable != *B && Removable != *M); 257 258 S.erase(Removable); 259 260 // B,M,E iterators should still be valid 261 EXPECT_EQ(B, S.begin()); 262 EXPECT_EQ(M, std::next(B)); 263 EXPECT_EQ(E, S.end()); 264 EXPECT_EQ(std::next(M), E); 265 } 266 267 TEST(SmallPtrSetTest, EraseTest) { 268 // Test when set stays small. 269 SmallPtrSet<int *, 8> B; 270 checkEraseAndIterators(B); 271 272 // Test when set grows big. 273 SmallPtrSet<int *, 2> A; 274 checkEraseAndIterators(A); 275 } 276
