From 6882a04fb36642862b11efe514251d32070c3d65 Mon Sep 17 00:00:00 2001 From: Konstantin Tokarev Date: Thu, 25 Aug 2016 19:20:41 +0300 Subject: Imported QtWebKit TP3 (git b57bc6801f1876c3220d5a4bfea33d620d477443) Change-Id: I3b1d8a2808782c9f34d50240000e20cb38d3680f Reviewed-by: Konstantin Tokarev --- Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp | 622 +++++++++++++++++++++++++++++- 1 file changed, 620 insertions(+), 2 deletions(-) (limited to 'Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp') diff --git a/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp b/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp index db6ca814f..145edae1a 100644 --- a/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp +++ b/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp @@ -25,13 +25,18 @@ #include "config.h" +#include "Counters.h" +#include "MoveOnly.h" +#include "RefLogger.h" +#include #include +#include namespace TestWebKitAPI { typedef WTF::HashMap IntHashMap; -TEST(WTF, HashTableIteratorComparison) +TEST(WTF_HashMap, HashTableIteratorComparison) { IntHashMap map; map.add(1, 2); @@ -60,7 +65,7 @@ static int bucketForKey(double key) return DefaultHash::Hash::hash(key) & (TestDoubleHashTraits::minimumTableSize - 1); } -TEST(WTF, DoubleHashCollisions) +TEST(WTF_HashMap, DoubleHashCollisions) { // The "clobber" key here is one that ends up stealing the bucket that the -0 key // originally wants to be in. This makes the 0 and -0 keys collide and the test then @@ -81,4 +86,617 @@ TEST(WTF, DoubleHashCollisions) ASSERT_EQ(map.get(negativeZeroKey), 3); } +TEST(WTF_HashMap, MoveOnlyValues) +{ + HashMap moveOnlyValues; + + for (size_t i = 0; i < 100; ++i) { + MoveOnly moveOnly(i + 1); + moveOnlyValues.set(i + 1, WTFMove(moveOnly)); + } + + for (size_t i = 0; i < 100; ++i) { + auto it = moveOnlyValues.find(i + 1); + ASSERT_FALSE(it == moveOnlyValues.end()); + } + + for (size_t i = 0; i < 50; ++i) + ASSERT_EQ(moveOnlyValues.take(i + 1).value(), i + 1); + + for (size_t i = 50; i < 100; ++i) + ASSERT_TRUE(moveOnlyValues.remove(i + 1)); + + ASSERT_TRUE(moveOnlyValues.isEmpty()); +} + +TEST(WTF_HashMap, MoveOnlyKeys) +{ + HashMap moveOnlyKeys; + + for (size_t i = 0; i < 100; ++i) { + MoveOnly moveOnly(i + 1); + moveOnlyKeys.set(WTFMove(moveOnly), i + 1); + } + + for (size_t i = 0; i < 100; ++i) { + auto it = moveOnlyKeys.find(MoveOnly(i + 1)); + ASSERT_FALSE(it == moveOnlyKeys.end()); + } + + for (size_t i = 0; i < 100; ++i) + ASSERT_FALSE(moveOnlyKeys.add(MoveOnly(i + 1), i + 1).isNewEntry); + + for (size_t i = 0; i < 100; ++i) + ASSERT_TRUE(moveOnlyKeys.remove(MoveOnly(i + 1))); + + ASSERT_TRUE(moveOnlyKeys.isEmpty()); +} + +TEST(WTF_HashMap, InitializerList) +{ + HashMap map = { + { 1, "one" }, + { 2, "two" }, + { 3, "three" }, + { 4, "four" }, + }; + + EXPECT_EQ(4u, map.size()); + + EXPECT_EQ("one", map.get(1)); + EXPECT_EQ("two", map.get(2)); + EXPECT_EQ("three", map.get(3)); + EXPECT_EQ("four", map.get(4)); + EXPECT_EQ(std::string(), map.get(5)); +} + +TEST(WTF_HashMap, EfficientGetter) +{ + HashMap map; + map.set(1, CopyMoveCounter()); + + { + CopyMoveCounter::TestingScope scope; + map.get(1); + EXPECT_EQ(0U, CopyMoveCounter::constructionCount); + EXPECT_EQ(1U, CopyMoveCounter::copyCount); + EXPECT_EQ(0U, CopyMoveCounter::moveCount); + } + + { + CopyMoveCounter::TestingScope scope; + map.get(2); + EXPECT_EQ(1U, CopyMoveCounter::constructionCount); + EXPECT_EQ(0U, CopyMoveCounter::copyCount); + EXPECT_EQ(1U, CopyMoveCounter::moveCount); + } +} + +TEST(WTF_HashMap, UniquePtrKey) +{ + ConstructorDestructorCounter::TestingScope scope; + + HashMap, int> map; + + auto uniquePtr = std::make_unique(); + map.add(WTFMove(uniquePtr), 2); + + EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount); + EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount); + + map.clear(); + + EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount); + EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount); +} + +TEST(WTF_HashMap, UniquePtrKey_CustomDeleter) +{ + ConstructorDestructorCounter::TestingScope constructorDestructorCounterScope; + DeleterCounter::TestingScope deleterCounterScope; + + HashMap>, int> map; + + std::unique_ptr> uniquePtr(new ConstructorDestructorCounter(), DeleterCounter()); + map.add(WTFMove(uniquePtr), 2); + + EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount); + EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount); + + EXPECT_EQ(0u, DeleterCounter::deleterCount); + + map.clear(); + + EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount); + EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount); + + EXPECT_EQ(1u, DeleterCounter::deleterCount); +} + +TEST(WTF_HashMap, UniquePtrKey_FindUsingRawPointer) +{ + HashMap, int> map; + + auto uniquePtr = std::make_unique(5); + int* ptr = uniquePtr.get(); + map.add(WTFMove(uniquePtr), 2); + + auto it = map.find(ptr); + ASSERT_TRUE(it != map.end()); + EXPECT_EQ(ptr, it->key.get()); + EXPECT_EQ(2, it->value); +} + +TEST(WTF_HashMap, UniquePtrKey_ContainsUsingRawPointer) +{ + HashMap, int> map; + + auto uniquePtr = std::make_unique(5); + int* ptr = uniquePtr.get(); + map.add(WTFMove(uniquePtr), 2); + + EXPECT_EQ(true, map.contains(ptr)); +} + +TEST(WTF_HashMap, UniquePtrKey_GetUsingRawPointer) +{ + HashMap, int> map; + + auto uniquePtr = std::make_unique(5); + int* ptr = uniquePtr.get(); + map.add(WTFMove(uniquePtr), 2); + + int value = map.get(ptr); + EXPECT_EQ(2, value); +} + +TEST(WTF_HashMap, UniquePtrKey_RemoveUsingRawPointer) +{ + ConstructorDestructorCounter::TestingScope scope; + + HashMap, int> map; + + auto uniquePtr = std::make_unique(); + ConstructorDestructorCounter* ptr = uniquePtr.get(); + map.add(WTFMove(uniquePtr), 2); + + EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount); + EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount); + + bool result = map.remove(ptr); + EXPECT_EQ(true, result); + + EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount); + EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount); +} + +TEST(WTF_HashMap, UniquePtrKey_TakeUsingRawPointer) +{ + ConstructorDestructorCounter::TestingScope scope; + + HashMap, int> map; + + auto uniquePtr = std::make_unique(); + ConstructorDestructorCounter* ptr = uniquePtr.get(); + map.add(WTFMove(uniquePtr), 2); + + EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount); + EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount); + + int result = map.take(ptr); + EXPECT_EQ(2, result); + + EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount); + EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount); +} + +TEST(WTF_HashMap, RefPtrKey_Add) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + RefPtr ptr(&a); + map.add(ptr, 0); + + ASSERT_STREQ("ref(a) ref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, RefPtrKey_AddUsingRelease) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + RefPtr ptr(&a); + map.add(ptr.release(), 0); + + EXPECT_STREQ("ref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, RefPtrKey_AddUsingMove) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + RefPtr ptr(&a); + map.add(WTFMove(ptr), 0); + + EXPECT_STREQ("ref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, RefPtrKey_AddUsingRaw) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + RefPtr ptr(&a); + map.add(ptr.get(), 0); + + EXPECT_STREQ("ref(a) ref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, RefPtrKey_AddKeyAlreadyPresent) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + + { + RefPtr ptr(&a); + map.add(ptr, 0); + } + + EXPECT_STREQ("ref(a) ref(a) deref(a) ", takeLogStr().c_str()); + + { + RefPtr ptr2(&a); + auto addResult = map.add(ptr2, 0); + EXPECT_FALSE(addResult.isNewEntry); + } + + EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, RefPtrKey_AddUsingReleaseKeyAlreadyPresent) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + + { + RefPtr ptr(&a); + map.add(ptr, 0); + } + + EXPECT_STREQ("ref(a) ref(a) deref(a) ", takeLogStr().c_str()); + + { + RefPtr ptr2(&a); + auto addResult = map.add(ptr2.release(), 0); + EXPECT_FALSE(addResult.isNewEntry); + } + + EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, RefPtrKey_AddUsingMoveKeyAlreadyPresent) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + + { + RefPtr ptr(&a); + map.add(ptr, 0); + } + + EXPECT_STREQ("ref(a) ref(a) deref(a) ", takeLogStr().c_str()); + + { + RefPtr ptr2(&a); + auto addResult = map.add(WTFMove(ptr2), 0); + EXPECT_FALSE(addResult.isNewEntry); + } + + EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, RefPtrKey_Set) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + RefPtr ptr(&a); + map.set(ptr, 0); + + ASSERT_STREQ("ref(a) ref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, RefPtrKey_SetUsingRelease) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + RefPtr ptr(&a); + map.set(ptr.release(), 0); + + EXPECT_STREQ("ref(a) ", takeLogStr().c_str()); +} + + +TEST(WTF_HashMap, RefPtrKey_SetUsingMove) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + RefPtr ptr(&a); + map.set(WTFMove(ptr), 0); + + EXPECT_STREQ("ref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, RefPtrKey_SetUsingRaw) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + RefPtr ptr(&a); + map.set(ptr.get(), 0); + + EXPECT_STREQ("ref(a) ref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, RefPtrKey_SetKeyAlreadyPresent) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + + RefPtr ptr(&a); + map.set(ptr, 0); + + EXPECT_STREQ("ref(a) ref(a) ", takeLogStr().c_str()); + + { + RefPtr ptr2(&a); + auto addResult = map.set(ptr2, 1); + EXPECT_FALSE(addResult.isNewEntry); + EXPECT_EQ(1, map.get(ptr.get())); + } + + EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, RefPtrKey_SetUsingReleaseKeyAlreadyPresent) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + + RefPtr ptr(&a); + map.set(ptr, 0); + + EXPECT_STREQ("ref(a) ref(a) ", takeLogStr().c_str()); + + { + RefPtr ptr2(&a); + auto addResult = map.set(ptr2.release(), 1); + EXPECT_FALSE(addResult.isNewEntry); + EXPECT_EQ(1, map.get(ptr.get())); + } + + EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, RefPtrKey_SetUsingMoveKeyAlreadyPresent) +{ + HashMap, int> map; + + DerivedRefLogger a("a"); + + RefPtr ptr(&a); + map.set(ptr, 0); + + EXPECT_STREQ("ref(a) ref(a) ", takeLogStr().c_str()); + + { + RefPtr ptr2(&a); + auto addResult = map.set(WTFMove(ptr2), 1); + EXPECT_FALSE(addResult.isNewEntry); + EXPECT_EQ(1, map.get(ptr.get())); + } + + EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str()); +} + +TEST(WTF_HashMap, Ensure) +{ + HashMap map; + { + auto addResult = map.ensure(1, [] { return 1; }); + EXPECT_EQ(1u, addResult.iterator->value); + EXPECT_EQ(1u, addResult.iterator->key); + EXPECT_TRUE(addResult.isNewEntry); + auto addResult2 = map.ensure(1, [] { return 2; }); + EXPECT_EQ(1u, addResult2.iterator->value); + EXPECT_EQ(1u, addResult2.iterator->key); + EXPECT_FALSE(addResult2.isNewEntry); + } +} + +TEST(WTF_HashMap, Ensure_MoveOnlyValues) +{ + HashMap moveOnlyValues; + { + auto addResult = moveOnlyValues.ensure(1, [] { return MoveOnly(1); }); + EXPECT_EQ(1u, addResult.iterator->value.value()); + EXPECT_EQ(1u, addResult.iterator->key); + EXPECT_TRUE(addResult.isNewEntry); + auto addResult2 = moveOnlyValues.ensure(1, [] { return MoveOnly(2); }); + EXPECT_EQ(1u, addResult2.iterator->value.value()); + EXPECT_EQ(1u, addResult2.iterator->key); + EXPECT_FALSE(addResult2.isNewEntry); + } +} + +TEST(WTF_HashMap, Ensure_UniquePointer) +{ + HashMap> map; + { + auto addResult = map.ensure(1, [] { return std::make_unique(1); }); + EXPECT_EQ(1u, *map.get(1)); + EXPECT_EQ(1u, *addResult.iterator->value.get()); + EXPECT_EQ(1u, addResult.iterator->key); + EXPECT_TRUE(addResult.isNewEntry); + auto addResult2 = map.ensure(1, [] { return std::make_unique(2); }); + EXPECT_EQ(1u, *map.get(1)); + EXPECT_EQ(1u, *addResult2.iterator->value.get()); + EXPECT_EQ(1u, addResult2.iterator->key); + EXPECT_FALSE(addResult2.isNewEntry); + } +} + +TEST(WTF_HashMap, Ensure_RefPtr) +{ + HashMap> map; + + { + DerivedRefLogger a("a"); + + map.ensure(1, [&] { return RefPtr(&a); }); + EXPECT_STREQ("ref(a) ", takeLogStr().c_str()); + + map.ensure(1, [&] { return RefPtr(&a); }); + EXPECT_STREQ("", takeLogStr().c_str()); + } +} + +class ObjectWithRefLogger { +public: + ObjectWithRefLogger(Ref&& logger) + : m_logger(WTFMove(logger)) + { + } + + Ref m_logger; +}; + + +void testMovingUsingEnsure(Ref&& logger) +{ + HashMap> map; + + map.ensure(1, [&] { return std::make_unique(WTFMove(logger)); }); +} + +void testMovingUsingAdd(Ref&& logger) +{ + HashMap> map; + + auto& slot = map.add(1, nullptr).iterator->value; + slot = std::make_unique(WTFMove(logger)); +} + +TEST(WTF_HashMap, Ensure_LambdasCapturingByReference) +{ + { + DerivedRefLogger a("a"); + Ref ref(a); + testMovingUsingEnsure(WTFMove(ref)); + + EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str()); + } + + { + DerivedRefLogger a("a"); + Ref ref(a); + testMovingUsingAdd(WTFMove(ref)); + + EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str()); + } +} + + +TEST(WTF_HashMap, ValueIsDestructedOnRemove) +{ + struct DestructorObserver { + DestructorObserver() = default; + + DestructorObserver(bool* destructed) + : destructed(destructed) + { + } + + ~DestructorObserver() + { + if (destructed) + *destructed = true; + } + + DestructorObserver(DestructorObserver&& other) + : destructed(other.destructed) + { + other.destructed = nullptr; + } + + DestructorObserver& operator=(DestructorObserver&& other) + { + destructed = other.destructed; + other.destructed = nullptr; + return *this; + } + + bool* destructed { nullptr }; + }; + + HashMap map; + + bool destructed = false; + map.add(5, DestructorObserver { &destructed }); + + EXPECT_FALSE(destructed); + + bool removeResult = map.remove(5); + + EXPECT_TRUE(removeResult); + EXPECT_TRUE(destructed); +} + +TEST(WTF_HashMap, RefPtrNotZeroedBeforeDeref) +{ + struct DerefObserver { + NEVER_INLINE void ref() + { + ++count; + } + NEVER_INLINE void deref() + { + --count; + observedBucket = bucketAddress->get(); + } + unsigned count { 1 }; + const RefPtr* bucketAddress { nullptr }; + const DerefObserver* observedBucket { nullptr }; + }; + + auto observer = std::make_unique(); + + HashMap, int> map; + map.add(adoptRef(observer.get()), 5); + + auto iterator = map.find(observer.get()); + EXPECT_TRUE(iterator != map.end()); + + observer->bucketAddress = &iterator->key; + + EXPECT_TRUE(observer->observedBucket == nullptr); + EXPECT_TRUE(map.remove(observer.get())); + + // It if fine to either leave the old value intact at deletion or already set it to the deleted + // value. + // A zero would be a incorrect outcome as it would mean we nulled the bucket before an opaque + // call. + EXPECT_TRUE(observer->observedBucket == observer.get() || observer->observedBucket == RefPtr::hashTableDeletedValue()); + EXPECT_EQ(observer->count, 0u); +} + } // namespace TestWebKitAPI -- cgit v1.2.1