| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * Copyright (C) 2012 Apple Inc. All rights reserved. | |
| 3 * | |
| 4 * Redistribution and use in source and binary forms, with or without | |
| 5 * modification, are permitted provided that the following conditions | |
| 6 * are met: | |
| 7 * 1. Redistributions of source code must retain the above copyright | |
| 8 * notice, this list of conditions and the following disclaimer. | |
| 9 * 2. Redistributions in binary form must reproduce the above copyright | |
| 10 * notice, this list of conditions and the following disclaimer in the | |
| 11 * documentation and/or other materials provided with the distribution. | |
| 12 * | |
| 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' | |
| 14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, | |
| 15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
| 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS | |
| 17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
| 18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
| 19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | |
| 20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | |
| 21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
| 22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF | |
| 23 * THE POSSIBILITY OF SUCH DAMAGE. | |
| 24 */ | |
| 25 | |
| 26 #include "wtf/ListHashSet.h" | |
| 27 | |
| 28 #include "testing/gtest/include/gtest/gtest.h" | |
| 29 #include "wtf/LinkedHashSet.h" | |
| 30 #include "wtf/PassRefPtr.h" | |
| 31 #include "wtf/PtrUtil.h" | |
| 32 #include "wtf/RefCounted.h" | |
| 33 #include "wtf/RefPtr.h" | |
| 34 #include <memory> | |
| 35 #include <type_traits> | |
| 36 | |
| 37 namespace WTF { | |
| 38 | |
| 39 namespace { | |
| 40 | |
| 41 template <typename Set> | |
| 42 class ListOrLinkedHashSetTest : public ::testing::Test {}; | |
| 43 | |
| 44 using SetTypes = | |
| 45 ::testing::Types<ListHashSet<int>, ListHashSet<int, 1>, LinkedHashSet<int>>; | |
| 46 TYPED_TEST_CASE(ListOrLinkedHashSetTest, SetTypes); | |
| 47 | |
| 48 TYPED_TEST(ListOrLinkedHashSetTest, RemoveFirst) { | |
| 49 using Set = TypeParam; | |
| 50 Set list; | |
| 51 list.insert(-1); | |
| 52 list.insert(0); | |
| 53 list.insert(1); | |
| 54 list.insert(2); | |
| 55 list.insert(3); | |
| 56 | |
| 57 EXPECT_EQ(-1, list.front()); | |
| 58 EXPECT_EQ(3, list.back()); | |
| 59 | |
| 60 list.removeFirst(); | |
| 61 EXPECT_EQ(0, list.front()); | |
| 62 | |
| 63 list.pop_back(); | |
| 64 EXPECT_EQ(2, list.back()); | |
| 65 | |
| 66 list.removeFirst(); | |
| 67 EXPECT_EQ(1, list.front()); | |
| 68 | |
| 69 list.removeFirst(); | |
| 70 EXPECT_EQ(2, list.front()); | |
| 71 | |
| 72 list.removeFirst(); | |
| 73 EXPECT_TRUE(list.isEmpty()); | |
| 74 } | |
| 75 | |
| 76 TYPED_TEST(ListOrLinkedHashSetTest, AppendOrMoveToLastNewItems) { | |
| 77 using Set = TypeParam; | |
| 78 Set list; | |
| 79 typename Set::AddResult result = list.appendOrMoveToLast(1); | |
| 80 EXPECT_TRUE(result.isNewEntry); | |
| 81 result = list.insert(2); | |
| 82 EXPECT_TRUE(result.isNewEntry); | |
| 83 result = list.appendOrMoveToLast(3); | |
| 84 EXPECT_TRUE(result.isNewEntry); | |
| 85 | |
| 86 EXPECT_EQ(list.size(), 3UL); | |
| 87 | |
| 88 // The list should be in order 1, 2, 3. | |
| 89 typename Set::iterator iterator = list.begin(); | |
| 90 EXPECT_EQ(1, *iterator); | |
| 91 ++iterator; | |
| 92 EXPECT_EQ(2, *iterator); | |
| 93 ++iterator; | |
| 94 EXPECT_EQ(3, *iterator); | |
| 95 ++iterator; | |
| 96 } | |
| 97 | |
| 98 TYPED_TEST(ListOrLinkedHashSetTest, AppendOrMoveToLastWithDuplicates) { | |
| 99 using Set = TypeParam; | |
| 100 Set list; | |
| 101 | |
| 102 // Add a single element twice. | |
| 103 typename Set::AddResult result = list.insert(1); | |
| 104 EXPECT_TRUE(result.isNewEntry); | |
| 105 result = list.appendOrMoveToLast(1); | |
| 106 EXPECT_FALSE(result.isNewEntry); | |
| 107 EXPECT_EQ(1UL, list.size()); | |
| 108 | |
| 109 list.insert(2); | |
| 110 list.insert(3); | |
| 111 EXPECT_EQ(3UL, list.size()); | |
| 112 | |
| 113 // Appending 2 move it to the end. | |
| 114 EXPECT_EQ(3, list.back()); | |
| 115 result = list.appendOrMoveToLast(2); | |
| 116 EXPECT_FALSE(result.isNewEntry); | |
| 117 EXPECT_EQ(2, list.back()); | |
| 118 | |
| 119 // Inverse the list by moving each element to end end. | |
| 120 result = list.appendOrMoveToLast(3); | |
| 121 EXPECT_FALSE(result.isNewEntry); | |
| 122 result = list.appendOrMoveToLast(2); | |
| 123 EXPECT_FALSE(result.isNewEntry); | |
| 124 result = list.appendOrMoveToLast(1); | |
| 125 EXPECT_FALSE(result.isNewEntry); | |
| 126 EXPECT_EQ(3UL, list.size()); | |
| 127 | |
| 128 typename Set::iterator iterator = list.begin(); | |
| 129 EXPECT_EQ(3, *iterator); | |
| 130 ++iterator; | |
| 131 EXPECT_EQ(2, *iterator); | |
| 132 ++iterator; | |
| 133 EXPECT_EQ(1, *iterator); | |
| 134 ++iterator; | |
| 135 } | |
| 136 | |
| 137 TYPED_TEST(ListOrLinkedHashSetTest, PrependOrMoveToFirstNewItems) { | |
| 138 using Set = TypeParam; | |
| 139 Set list; | |
| 140 typename Set::AddResult result = list.prependOrMoveToFirst(1); | |
| 141 EXPECT_TRUE(result.isNewEntry); | |
| 142 result = list.insert(2); | |
| 143 EXPECT_TRUE(result.isNewEntry); | |
| 144 result = list.prependOrMoveToFirst(3); | |
| 145 EXPECT_TRUE(result.isNewEntry); | |
| 146 | |
| 147 EXPECT_EQ(list.size(), 3UL); | |
| 148 | |
| 149 // The list should be in order 3, 1, 2. | |
| 150 typename Set::iterator iterator = list.begin(); | |
| 151 EXPECT_EQ(3, *iterator); | |
| 152 ++iterator; | |
| 153 EXPECT_EQ(1, *iterator); | |
| 154 ++iterator; | |
| 155 EXPECT_EQ(2, *iterator); | |
| 156 ++iterator; | |
| 157 } | |
| 158 | |
| 159 TYPED_TEST(ListOrLinkedHashSetTest, PrependOrMoveToLastWithDuplicates) { | |
| 160 using Set = TypeParam; | |
| 161 Set list; | |
| 162 | |
| 163 // Add a single element twice. | |
| 164 typename Set::AddResult result = list.insert(1); | |
| 165 EXPECT_TRUE(result.isNewEntry); | |
| 166 result = list.prependOrMoveToFirst(1); | |
| 167 EXPECT_FALSE(result.isNewEntry); | |
| 168 EXPECT_EQ(1UL, list.size()); | |
| 169 | |
| 170 list.insert(2); | |
| 171 list.insert(3); | |
| 172 EXPECT_EQ(3UL, list.size()); | |
| 173 | |
| 174 // Prepending 2 move it to the beginning. | |
| 175 EXPECT_EQ(1, list.front()); | |
| 176 result = list.prependOrMoveToFirst(2); | |
| 177 EXPECT_FALSE(result.isNewEntry); | |
| 178 EXPECT_EQ(2, list.front()); | |
| 179 | |
| 180 // Inverse the list by moving each element to the first position. | |
| 181 result = list.prependOrMoveToFirst(1); | |
| 182 EXPECT_FALSE(result.isNewEntry); | |
| 183 result = list.prependOrMoveToFirst(2); | |
| 184 EXPECT_FALSE(result.isNewEntry); | |
| 185 result = list.prependOrMoveToFirst(3); | |
| 186 EXPECT_FALSE(result.isNewEntry); | |
| 187 EXPECT_EQ(3UL, list.size()); | |
| 188 | |
| 189 typename Set::iterator iterator = list.begin(); | |
| 190 EXPECT_EQ(3, *iterator); | |
| 191 ++iterator; | |
| 192 EXPECT_EQ(2, *iterator); | |
| 193 ++iterator; | |
| 194 EXPECT_EQ(1, *iterator); | |
| 195 ++iterator; | |
| 196 } | |
| 197 | |
| 198 TYPED_TEST(ListOrLinkedHashSetTest, Find) { | |
| 199 using Set = TypeParam; | |
| 200 Set set; | |
| 201 set.insert(-1); | |
| 202 set.insert(0); | |
| 203 set.insert(1); | |
| 204 set.insert(2); | |
| 205 set.insert(3); | |
| 206 | |
| 207 { | |
| 208 const Set& ref = set; | |
| 209 typename Set::const_iterator it = ref.find(2); | |
| 210 EXPECT_EQ(2, *it); | |
| 211 ++it; | |
| 212 EXPECT_EQ(3, *it); | |
| 213 --it; | |
| 214 --it; | |
| 215 EXPECT_EQ(1, *it); | |
| 216 } | |
| 217 { | |
| 218 Set& ref = set; | |
| 219 typename Set::iterator it = ref.find(2); | |
| 220 EXPECT_EQ(2, *it); | |
| 221 ++it; | |
| 222 EXPECT_EQ(3, *it); | |
| 223 --it; | |
| 224 --it; | |
| 225 EXPECT_EQ(1, *it); | |
| 226 } | |
| 227 } | |
| 228 | |
| 229 TYPED_TEST(ListOrLinkedHashSetTest, InsertBefore) { | |
| 230 using Set = TypeParam; | |
| 231 bool canModifyWhileIterating = !std::is_same<Set, LinkedHashSet<int>>::value; | |
| 232 Set set; | |
| 233 set.insert(-1); | |
| 234 set.insert(0); | |
| 235 set.insert(2); | |
| 236 set.insert(3); | |
| 237 | |
| 238 typename Set::iterator it = set.find(2); | |
| 239 EXPECT_EQ(2, *it); | |
| 240 set.insertBefore(it, 1); | |
| 241 if (!canModifyWhileIterating) | |
| 242 it = set.find(2); | |
| 243 ++it; | |
| 244 EXPECT_EQ(3, *it); | |
| 245 EXPECT_EQ(5u, set.size()); | |
| 246 --it; | |
| 247 --it; | |
| 248 EXPECT_EQ(1, *it); | |
| 249 if (canModifyWhileIterating) { | |
| 250 set.erase(-1); | |
| 251 set.erase(0); | |
| 252 set.erase(2); | |
| 253 set.erase(3); | |
| 254 EXPECT_EQ(1u, set.size()); | |
| 255 EXPECT_EQ(1, *it); | |
| 256 ++it; | |
| 257 EXPECT_EQ(it, set.end()); | |
| 258 --it; | |
| 259 EXPECT_EQ(1, *it); | |
| 260 set.insertBefore(it, -1); | |
| 261 set.insertBefore(it, 0); | |
| 262 set.insert(2); | |
| 263 set.insert(3); | |
| 264 } | |
| 265 set.insertBefore(2, 42); | |
| 266 set.insertBefore(-1, 103); | |
| 267 EXPECT_EQ(103, set.front()); | |
| 268 if (!canModifyWhileIterating) | |
| 269 it = set.find(1); | |
| 270 ++it; | |
| 271 EXPECT_EQ(42, *it); | |
| 272 EXPECT_EQ(7u, set.size()); | |
| 273 } | |
| 274 | |
| 275 TYPED_TEST(ListOrLinkedHashSetTest, AddReturnIterator) { | |
| 276 using Set = TypeParam; | |
| 277 bool canModifyWhileIterating = !std::is_same<Set, LinkedHashSet<int>>::value; | |
| 278 Set set; | |
| 279 set.insert(-1); | |
| 280 set.insert(0); | |
| 281 set.insert(1); | |
| 282 set.insert(2); | |
| 283 | |
| 284 typename Set::iterator it = set.addReturnIterator(3); | |
| 285 EXPECT_EQ(3, *it); | |
| 286 --it; | |
| 287 EXPECT_EQ(2, *it); | |
| 288 EXPECT_EQ(5u, set.size()); | |
| 289 --it; | |
| 290 EXPECT_EQ(1, *it); | |
| 291 --it; | |
| 292 EXPECT_EQ(0, *it); | |
| 293 it = set.addReturnIterator(4); | |
| 294 if (canModifyWhileIterating) { | |
| 295 set.erase(3); | |
| 296 set.erase(2); | |
| 297 set.erase(1); | |
| 298 set.erase(0); | |
| 299 set.erase(-1); | |
| 300 EXPECT_EQ(1u, set.size()); | |
| 301 } | |
| 302 EXPECT_EQ(4, *it); | |
| 303 ++it; | |
| 304 EXPECT_EQ(it, set.end()); | |
| 305 --it; | |
| 306 EXPECT_EQ(4, *it); | |
| 307 if (canModifyWhileIterating) { | |
| 308 set.insertBefore(it, -1); | |
| 309 set.insertBefore(it, 0); | |
| 310 set.insertBefore(it, 1); | |
| 311 set.insertBefore(it, 2); | |
| 312 set.insertBefore(it, 3); | |
| 313 } | |
| 314 EXPECT_EQ(6u, set.size()); | |
| 315 it = set.addReturnIterator(5); | |
| 316 EXPECT_EQ(7u, set.size()); | |
| 317 set.erase(it); | |
| 318 EXPECT_EQ(6u, set.size()); | |
| 319 EXPECT_EQ(4, set.back()); | |
| 320 } | |
| 321 | |
| 322 TYPED_TEST(ListOrLinkedHashSetTest, Swap) { | |
| 323 using Set = TypeParam; | |
| 324 int num = 10; | |
| 325 Set set0; | |
| 326 Set set1; | |
| 327 Set set2; | |
| 328 for (int i = 0; i < num; ++i) { | |
| 329 set1.insert(i + 1); | |
| 330 set2.insert(num - i); | |
| 331 } | |
| 332 | |
| 333 typename Set::iterator it1 = set1.begin(); | |
| 334 typename Set::iterator it2 = set2.begin(); | |
| 335 for (int i = 0; i < num; ++i, ++it1, ++it2) { | |
| 336 EXPECT_EQ(*it1, i + 1); | |
| 337 EXPECT_EQ(*it2, num - i); | |
| 338 } | |
| 339 EXPECT_EQ(set0.begin(), set0.end()); | |
| 340 EXPECT_EQ(it1, set1.end()); | |
| 341 EXPECT_EQ(it2, set2.end()); | |
| 342 | |
| 343 // Shift sets: 2->1, 1->0, 0->2 | |
| 344 set1.swap(set2); // Swap with non-empty sets. | |
| 345 set0.swap(set2); // Swap with an empty set. | |
| 346 | |
| 347 it1 = set0.begin(); | |
| 348 it2 = set1.begin(); | |
| 349 for (int i = 0; i < num; ++i, ++it1, ++it2) { | |
| 350 EXPECT_EQ(*it1, i + 1); | |
| 351 EXPECT_EQ(*it2, num - i); | |
| 352 } | |
| 353 EXPECT_EQ(it1, set0.end()); | |
| 354 EXPECT_EQ(it2, set1.end()); | |
| 355 EXPECT_EQ(set2.begin(), set2.end()); | |
| 356 | |
| 357 int removedIndex = num >> 1; | |
| 358 set0.erase(removedIndex + 1); | |
| 359 set1.erase(num - removedIndex); | |
| 360 | |
| 361 it1 = set0.begin(); | |
| 362 it2 = set1.begin(); | |
| 363 for (int i = 0; i < num; ++i, ++it1, ++it2) { | |
| 364 if (i == removedIndex) | |
| 365 ++i; | |
| 366 EXPECT_EQ(*it1, i + 1); | |
| 367 EXPECT_EQ(*it2, num - i); | |
| 368 } | |
| 369 EXPECT_EQ(it1, set0.end()); | |
| 370 EXPECT_EQ(it2, set1.end()); | |
| 371 } | |
| 372 | |
| 373 class DummyRefCounted : public RefCounted<DummyRefCounted> { | |
| 374 public: | |
| 375 DummyRefCounted(bool& isDeleted) : m_isDeleted(isDeleted) { | |
| 376 m_isDeleted = false; | |
| 377 } | |
| 378 ~DummyRefCounted() { m_isDeleted = true; } | |
| 379 void ref() { | |
| 380 WTF::RefCounted<DummyRefCounted>::ref(); | |
| 381 ++m_refInvokesCount; | |
| 382 } | |
| 383 | |
| 384 static int m_refInvokesCount; | |
| 385 | |
| 386 private: | |
| 387 bool& m_isDeleted; | |
| 388 }; | |
| 389 | |
| 390 int DummyRefCounted::m_refInvokesCount = 0; | |
| 391 | |
| 392 template <typename Set> | |
| 393 class ListOrLinkedHashSetRefPtrTest : public ::testing::Test {}; | |
| 394 | |
| 395 using RefPtrSetTypes = ::testing::Types<ListHashSet<RefPtr<DummyRefCounted>>, | |
| 396 ListHashSet<RefPtr<DummyRefCounted>, 1>, | |
| 397 LinkedHashSet<RefPtr<DummyRefCounted>>>; | |
| 398 TYPED_TEST_CASE(ListOrLinkedHashSetRefPtrTest, RefPtrSetTypes); | |
| 399 | |
| 400 TYPED_TEST(ListOrLinkedHashSetRefPtrTest, WithRefPtr) { | |
| 401 using Set = TypeParam; | |
| 402 bool isDeleted = false; | |
| 403 DummyRefCounted::m_refInvokesCount = 0; | |
| 404 RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted)); | |
| 405 EXPECT_EQ(0, DummyRefCounted::m_refInvokesCount); | |
| 406 | |
| 407 Set set; | |
| 408 set.insert(ptr); | |
| 409 // Referenced only once (to store a copy in the container). | |
| 410 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount); | |
| 411 EXPECT_EQ(ptr, set.front()); | |
| 412 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount); | |
| 413 | |
| 414 DummyRefCounted* rawPtr = ptr.get(); | |
| 415 | |
| 416 EXPECT_TRUE(set.contains(ptr)); | |
| 417 EXPECT_TRUE(set.contains(rawPtr)); | |
| 418 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount); | |
| 419 | |
| 420 ptr.clear(); | |
| 421 EXPECT_FALSE(isDeleted); | |
| 422 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount); | |
| 423 | |
| 424 set.erase(rawPtr); | |
| 425 EXPECT_TRUE(isDeleted); | |
| 426 | |
| 427 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount); | |
| 428 } | |
| 429 | |
| 430 TYPED_TEST(ListOrLinkedHashSetRefPtrTest, ExerciseValuePeekInType) { | |
| 431 using Set = TypeParam; | |
| 432 Set set; | |
| 433 bool isDeleted = false; | |
| 434 bool isDeleted2 = false; | |
| 435 | |
| 436 RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted)); | |
| 437 RefPtr<DummyRefCounted> ptr2 = adoptRef(new DummyRefCounted(isDeleted2)); | |
| 438 | |
| 439 typename Set::AddResult addResult = set.insert(ptr); | |
| 440 EXPECT_TRUE(addResult.isNewEntry); | |
| 441 set.find(ptr); | |
| 442 const Set& constSet(set); | |
| 443 constSet.find(ptr); | |
| 444 EXPECT_TRUE(set.contains(ptr)); | |
| 445 typename Set::iterator it = set.addReturnIterator(ptr); | |
| 446 set.appendOrMoveToLast(ptr); | |
| 447 set.prependOrMoveToFirst(ptr); | |
| 448 set.insertBefore(ptr, ptr); | |
| 449 set.insertBefore(it, ptr); | |
| 450 EXPECT_EQ(1u, set.size()); | |
| 451 set.insert(ptr2); | |
| 452 ptr2.clear(); | |
| 453 set.erase(ptr); | |
| 454 | |
| 455 EXPECT_FALSE(isDeleted); | |
| 456 ptr.clear(); | |
| 457 EXPECT_TRUE(isDeleted); | |
| 458 | |
| 459 EXPECT_FALSE(isDeleted2); | |
| 460 set.removeFirst(); | |
| 461 EXPECT_TRUE(isDeleted2); | |
| 462 | |
| 463 EXPECT_EQ(0u, set.size()); | |
| 464 } | |
| 465 | |
| 466 struct Simple { | |
| 467 Simple(int value) : m_value(value){}; | |
| 468 int m_value; | |
| 469 }; | |
| 470 | |
| 471 struct Complicated { | |
| 472 Complicated(int value) : m_simple(value) { s_objectsConstructed++; } | |
| 473 | |
| 474 Complicated(const Complicated& other) : m_simple(other.m_simple) { | |
| 475 s_objectsConstructed++; | |
| 476 } | |
| 477 | |
| 478 Simple m_simple; | |
| 479 static int s_objectsConstructed; | |
| 480 | |
| 481 private: | |
| 482 Complicated(); | |
| 483 }; | |
| 484 | |
| 485 int Complicated::s_objectsConstructed = 0; | |
| 486 | |
| 487 struct ComplicatedHashFunctions { | |
| 488 static unsigned hash(const Complicated& key) { return key.m_simple.m_value; } | |
| 489 static bool equal(const Complicated& a, const Complicated& b) { | |
| 490 return a.m_simple.m_value == b.m_simple.m_value; | |
| 491 } | |
| 492 }; | |
| 493 struct ComplexityTranslator { | |
| 494 static unsigned hash(const Simple& key) { return key.m_value; } | |
| 495 static bool equal(const Complicated& a, const Simple& b) { | |
| 496 return a.m_simple.m_value == b.m_value; | |
| 497 } | |
| 498 }; | |
| 499 | |
| 500 template <typename Set> | |
| 501 class ListOrLinkedHashSetTranslatorTest : public ::testing::Test {}; | |
| 502 | |
| 503 using TranslatorSetTypes = | |
| 504 ::testing::Types<ListHashSet<Complicated, 256, ComplicatedHashFunctions>, | |
| 505 ListHashSet<Complicated, 1, ComplicatedHashFunctions>, | |
| 506 LinkedHashSet<Complicated, ComplicatedHashFunctions>>; | |
| 507 TYPED_TEST_CASE(ListOrLinkedHashSetTranslatorTest, TranslatorSetTypes); | |
| 508 | |
| 509 TYPED_TEST(ListOrLinkedHashSetTranslatorTest, ComplexityTranslator) { | |
| 510 using Set = TypeParam; | |
| 511 Set set; | |
| 512 set.insert(Complicated(42)); | |
| 513 int baseLine = Complicated::s_objectsConstructed; | |
| 514 | |
| 515 typename Set::iterator it = | |
| 516 set.template find<ComplexityTranslator>(Simple(42)); | |
| 517 EXPECT_NE(it, set.end()); | |
| 518 EXPECT_EQ(baseLine, Complicated::s_objectsConstructed); | |
| 519 | |
| 520 it = set.template find<ComplexityTranslator>(Simple(103)); | |
| 521 EXPECT_EQ(it, set.end()); | |
| 522 EXPECT_EQ(baseLine, Complicated::s_objectsConstructed); | |
| 523 | |
| 524 const Set& constSet(set); | |
| 525 | |
| 526 typename Set::const_iterator constIterator = | |
| 527 constSet.template find<ComplexityTranslator>(Simple(42)); | |
| 528 EXPECT_NE(constIterator, constSet.end()); | |
| 529 EXPECT_EQ(baseLine, Complicated::s_objectsConstructed); | |
| 530 | |
| 531 constIterator = constSet.template find<ComplexityTranslator>(Simple(103)); | |
| 532 EXPECT_EQ(constIterator, constSet.end()); | |
| 533 EXPECT_EQ(baseLine, Complicated::s_objectsConstructed); | |
| 534 } | |
| 535 | |
| 536 struct Dummy { | |
| 537 Dummy(bool& deleted) : deleted(deleted) {} | |
| 538 | |
| 539 ~Dummy() { deleted = true; } | |
| 540 | |
| 541 bool& deleted; | |
| 542 }; | |
| 543 | |
| 544 TEST(ListHashSetTest, WithOwnPtr) { | |
| 545 bool deleted1 = false, deleted2 = false; | |
| 546 | |
| 547 typedef ListHashSet<std::unique_ptr<Dummy>> OwnPtrSet; | |
| 548 OwnPtrSet set; | |
| 549 | |
| 550 Dummy* ptr1 = new Dummy(deleted1); | |
| 551 { | |
| 552 // AddResult in a separate scope to avoid assertion hit, | |
| 553 // since we modify the container further. | |
| 554 OwnPtrSet::AddResult res1 = set.insert(WTF::wrapUnique(ptr1)); | |
| 555 EXPECT_EQ(res1.storedValue->get(), ptr1); | |
| 556 } | |
| 557 | |
| 558 EXPECT_FALSE(deleted1); | |
| 559 EXPECT_EQ(1UL, set.size()); | |
| 560 OwnPtrSet::iterator it1 = set.find(ptr1); | |
| 561 EXPECT_NE(set.end(), it1); | |
| 562 EXPECT_EQ(ptr1, (*it1).get()); | |
| 563 | |
| 564 Dummy* ptr2 = new Dummy(deleted2); | |
| 565 { | |
| 566 OwnPtrSet::AddResult res2 = set.insert(WTF::wrapUnique(ptr2)); | |
| 567 EXPECT_EQ(res2.storedValue->get(), ptr2); | |
| 568 } | |
| 569 | |
| 570 EXPECT_FALSE(deleted2); | |
| 571 EXPECT_EQ(2UL, set.size()); | |
| 572 OwnPtrSet::iterator it2 = set.find(ptr2); | |
| 573 EXPECT_NE(set.end(), it2); | |
| 574 EXPECT_EQ(ptr2, (*it2).get()); | |
| 575 | |
| 576 set.erase(ptr1); | |
| 577 EXPECT_TRUE(deleted1); | |
| 578 | |
| 579 set.clear(); | |
| 580 EXPECT_TRUE(deleted2); | |
| 581 EXPECT_TRUE(set.isEmpty()); | |
| 582 | |
| 583 deleted1 = false; | |
| 584 deleted2 = false; | |
| 585 { | |
| 586 OwnPtrSet set; | |
| 587 set.insert(WTF::makeUnique<Dummy>(deleted1)); | |
| 588 set.insert(WTF::makeUnique<Dummy>(deleted2)); | |
| 589 } | |
| 590 EXPECT_TRUE(deleted1); | |
| 591 EXPECT_TRUE(deleted2); | |
| 592 | |
| 593 deleted1 = false; | |
| 594 deleted2 = false; | |
| 595 std::unique_ptr<Dummy> ownPtr1; | |
| 596 std::unique_ptr<Dummy> ownPtr2; | |
| 597 ptr1 = new Dummy(deleted1); | |
| 598 ptr2 = new Dummy(deleted2); | |
| 599 { | |
| 600 OwnPtrSet set; | |
| 601 set.insert(WTF::wrapUnique(ptr1)); | |
| 602 set.insert(WTF::wrapUnique(ptr2)); | |
| 603 ownPtr1 = set.takeFirst(); | |
| 604 EXPECT_EQ(1UL, set.size()); | |
| 605 ownPtr2 = set.take(ptr2); | |
| 606 EXPECT_TRUE(set.isEmpty()); | |
| 607 } | |
| 608 EXPECT_FALSE(deleted1); | |
| 609 EXPECT_FALSE(deleted2); | |
| 610 | |
| 611 EXPECT_EQ(ptr1, ownPtr1.get()); | |
| 612 EXPECT_EQ(ptr2, ownPtr2.get()); | |
| 613 } | |
| 614 | |
| 615 class CountCopy final { | |
| 616 public: | |
| 617 static int* const kDeletedValue; | |
| 618 | |
| 619 explicit CountCopy(int* counter = nullptr) : m_counter(counter) {} | |
| 620 CountCopy(const CountCopy& other) : m_counter(other.m_counter) { | |
| 621 if (m_counter && m_counter != kDeletedValue) | |
| 622 ++*m_counter; | |
| 623 } | |
| 624 const int* counter() const { return m_counter; } | |
| 625 | |
| 626 private: | |
| 627 int* m_counter; | |
| 628 }; | |
| 629 | |
| 630 int* const CountCopy::kDeletedValue = | |
| 631 reinterpret_cast<int*>(static_cast<uintptr_t>(-1)); | |
| 632 | |
| 633 struct CountCopyHashTraits : public GenericHashTraits<CountCopy> { | |
| 634 static bool isEmptyValue(const CountCopy& value) { return !value.counter(); } | |
| 635 static void constructDeletedValue(CountCopy& slot, bool) { | |
| 636 slot = CountCopy(CountCopy::kDeletedValue); | |
| 637 } | |
| 638 static bool isDeletedValue(const CountCopy& value) { | |
| 639 return value.counter() == CountCopy::kDeletedValue; | |
| 640 } | |
| 641 }; | |
| 642 | |
| 643 struct CountCopyHash : public PtrHash<const int> { | |
| 644 static unsigned hash(const CountCopy& value) { | |
| 645 return PtrHash<const int>::hash(value.counter()); | |
| 646 } | |
| 647 static bool equal(const CountCopy& left, const CountCopy& right) { | |
| 648 return PtrHash<const int>::equal(left.counter(), right.counter()); | |
| 649 } | |
| 650 }; | |
| 651 | |
| 652 } // anonymous namespace | |
| 653 | |
| 654 template <> | |
| 655 struct HashTraits<CountCopy> : public CountCopyHashTraits {}; | |
| 656 | |
| 657 template <> | |
| 658 struct DefaultHash<CountCopy> { | |
| 659 using Hash = CountCopyHash; | |
| 660 }; | |
| 661 | |
| 662 namespace { | |
| 663 | |
| 664 template <typename Set> | |
| 665 class ListOrLinkedHashSetCountCopyTest : public ::testing::Test {}; | |
| 666 | |
| 667 using CountCopySetTypes = ::testing::Types<ListHashSet<CountCopy>, | |
| 668 ListHashSet<CountCopy, 1>, | |
| 669 LinkedHashSet<CountCopy>>; | |
| 670 TYPED_TEST_CASE(ListOrLinkedHashSetCountCopyTest, CountCopySetTypes); | |
| 671 | |
| 672 TYPED_TEST(ListOrLinkedHashSetCountCopyTest, | |
| 673 MoveConstructionShouldNotMakeCopy) { | |
| 674 using Set = TypeParam; | |
| 675 Set set; | |
| 676 int counter = 0; | |
| 677 set.insert(CountCopy(&counter)); | |
| 678 | |
| 679 counter = 0; | |
| 680 Set other(std::move(set)); | |
| 681 EXPECT_EQ(0, counter); | |
| 682 } | |
| 683 | |
| 684 TYPED_TEST(ListOrLinkedHashSetCountCopyTest, MoveAssignmentShouldNotMakeACopy) { | |
| 685 using Set = TypeParam; | |
| 686 Set set; | |
| 687 int counter = 0; | |
| 688 set.insert(CountCopy(&counter)); | |
| 689 | |
| 690 Set other(set); | |
| 691 counter = 0; | |
| 692 set = std::move(other); | |
| 693 EXPECT_EQ(0, counter); | |
| 694 } | |
| 695 | |
| 696 class MoveOnly { | |
| 697 public: | |
| 698 // kEmpty and kDeleted have special meanings when MoveOnly is used as the key | |
| 699 // of a hash table. | |
| 700 enum { kEmpty = 0, kDeleted = -1, kMovedOut = -2 }; | |
| 701 | |
| 702 explicit MoveOnly(int value = kEmpty, int id = 0) | |
| 703 : m_value(value), m_id(id) {} | |
| 704 MoveOnly(MoveOnly&& other) : m_value(other.m_value), m_id(other.m_id) { | |
| 705 other.m_value = kMovedOut; | |
| 706 other.m_id = 0; | |
| 707 } | |
| 708 MoveOnly& operator=(MoveOnly&& other) { | |
| 709 m_value = other.m_value; | |
| 710 m_id = other.m_id; | |
| 711 other.m_value = kMovedOut; | |
| 712 other.m_id = 0; | |
| 713 return *this; | |
| 714 } | |
| 715 | |
| 716 int value() const { return m_value; } | |
| 717 // id() is used for distinguishing MoveOnlys with the same value(). | |
| 718 int id() const { return m_id; } | |
| 719 | |
| 720 private: | |
| 721 MoveOnly(const MoveOnly&) = delete; | |
| 722 MoveOnly& operator=(const MoveOnly&) = delete; | |
| 723 | |
| 724 int m_value; | |
| 725 int m_id; | |
| 726 }; | |
| 727 | |
| 728 struct MoveOnlyHash { | |
| 729 static unsigned hash(const MoveOnly& value) { | |
| 730 return DefaultHash<int>::Hash::hash(value.value()); | |
| 731 } | |
| 732 static bool equal(const MoveOnly& left, const MoveOnly& right) { | |
| 733 return DefaultHash<int>::Hash::equal(left.value(), right.value()); | |
| 734 } | |
| 735 }; | |
| 736 | |
| 737 } // anonymous namespace | |
| 738 | |
| 739 template <> | |
| 740 struct DefaultHash<MoveOnly> { | |
| 741 using Hash = MoveOnlyHash; | |
| 742 }; | |
| 743 | |
| 744 namespace { | |
| 745 | |
| 746 template <typename Set> | |
| 747 class ListOrLinkedHashSetMoveOnlyTest : public ::testing::Test {}; | |
| 748 | |
| 749 using MoveOnlySetTypes = ::testing::Types<ListHashSet<MoveOnly>, | |
| 750 ListHashSet<MoveOnly, 1>, | |
| 751 LinkedHashSet<MoveOnly>>; | |
| 752 TYPED_TEST_CASE(ListOrLinkedHashSetMoveOnlyTest, MoveOnlySetTypes); | |
| 753 | |
| 754 TYPED_TEST(ListOrLinkedHashSetMoveOnlyTest, MoveOnlyValue) { | |
| 755 using Set = TypeParam; | |
| 756 using AddResult = typename Set::AddResult; | |
| 757 Set set; | |
| 758 { | |
| 759 AddResult addResult = set.insert(MoveOnly(1, 1)); | |
| 760 EXPECT_TRUE(addResult.isNewEntry); | |
| 761 EXPECT_EQ(1, addResult.storedValue->value()); | |
| 762 EXPECT_EQ(1, addResult.storedValue->id()); | |
| 763 } | |
| 764 { | |
| 765 AddResult addResult = set.insert(MoveOnly(1, 111)); | |
| 766 EXPECT_FALSE(addResult.isNewEntry); | |
| 767 EXPECT_EQ(1, addResult.storedValue->value()); | |
| 768 EXPECT_EQ(1, addResult.storedValue->id()); | |
| 769 } | |
| 770 auto iter = set.find(MoveOnly(1)); | |
| 771 ASSERT_TRUE(iter != set.end()); | |
| 772 EXPECT_EQ(1, iter->value()); | |
| 773 EXPECT_EQ(1, iter->id()); | |
| 774 | |
| 775 iter = set.find(MoveOnly(2)); | |
| 776 EXPECT_TRUE(iter == set.end()); | |
| 777 | |
| 778 // ListHashSet and LinkedHashSet have several flavors of add(). | |
| 779 iter = set.addReturnIterator(MoveOnly(2, 2)); | |
| 780 EXPECT_EQ(2, iter->value()); | |
| 781 EXPECT_EQ(2, iter->id()); | |
| 782 | |
| 783 iter = set.addReturnIterator(MoveOnly(2, 222)); | |
| 784 EXPECT_EQ(2, iter->value()); | |
| 785 EXPECT_EQ(2, iter->id()); | |
| 786 | |
| 787 { | |
| 788 AddResult addResult = set.appendOrMoveToLast(MoveOnly(3, 3)); | |
| 789 EXPECT_TRUE(addResult.isNewEntry); | |
| 790 EXPECT_EQ(3, addResult.storedValue->value()); | |
| 791 EXPECT_EQ(3, addResult.storedValue->id()); | |
| 792 } | |
| 793 { | |
| 794 AddResult addResult = set.prependOrMoveToFirst(MoveOnly(4, 4)); | |
| 795 EXPECT_TRUE(addResult.isNewEntry); | |
| 796 EXPECT_EQ(4, addResult.storedValue->value()); | |
| 797 EXPECT_EQ(4, addResult.storedValue->id()); | |
| 798 } | |
| 799 { | |
| 800 AddResult addResult = set.insertBefore(MoveOnly(4), MoveOnly(5, 5)); | |
| 801 EXPECT_TRUE(addResult.isNewEntry); | |
| 802 EXPECT_EQ(5, addResult.storedValue->value()); | |
| 803 EXPECT_EQ(5, addResult.storedValue->id()); | |
| 804 } | |
| 805 { | |
| 806 iter = set.find(MoveOnly(5)); | |
| 807 ASSERT_TRUE(iter != set.end()); | |
| 808 AddResult addResult = set.insertBefore(iter, MoveOnly(6, 6)); | |
| 809 EXPECT_TRUE(addResult.isNewEntry); | |
| 810 EXPECT_EQ(6, addResult.storedValue->value()); | |
| 811 EXPECT_EQ(6, addResult.storedValue->id()); | |
| 812 } | |
| 813 | |
| 814 // ... but they don't have any pass-out (like take()) methods. | |
| 815 | |
| 816 set.erase(MoveOnly(3)); | |
| 817 set.clear(); | |
| 818 } | |
| 819 | |
| 820 } // anonymous namespace | |
| 821 | |
| 822 } // namespace WTF | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2771783003:
Move wtf_unittests to platform/wtf/. (Closed)
