summaryrefslogtreecommitdiff
path: root/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp')
-rw-r--r--Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp254
1 files changed, 250 insertions, 4 deletions
diff --git a/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp b/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp
index 88e7d075f..1d6ffc039 100644
--- a/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp
+++ b/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp
@@ -25,9 +25,10 @@
#include "config.h"
+#include "Counters.h"
#include "MoveOnly.h"
#include <wtf/HashSet.h>
-
+#include <wtf/RefPtr.h>
namespace TestWebKitAPI {
@@ -43,7 +44,7 @@ void testInitialCapacity()
HashSet<int, DefaultHash<int>::Hash, InitialCapacityTestHashTraits<initialCapacity> > testSet;
// Initial capacity is null.
- ASSERT_EQ(0, testSet.capacity());
+ ASSERT_EQ(0u, testSet.capacity());
// Adding items up to size should never change the capacity.
for (size_t i = 0; i < size; ++i) {
@@ -84,7 +85,7 @@ TEST(WTF_HashSet, MoveOnly)
for (size_t i = 0; i < 100; ++i) {
MoveOnly moveOnly(i + 1);
- hashSet.add(std::move(moveOnly));
+ hashSet.add(WTFMove(moveOnly));
}
for (size_t i = 0; i < 100; ++i)
@@ -96,11 +97,256 @@ TEST(WTF_HashSet, MoveOnly)
EXPECT_TRUE(hashSet.isEmpty());
for (size_t i = 0; i < 100; ++i)
- hashSet.add(std::move(MoveOnly(i + 1)));
+ hashSet.add(MoveOnly(i + 1));
for (size_t i = 0; i < 100; ++i)
EXPECT_TRUE(hashSet.take(MoveOnly(i + 1)) == MoveOnly(i + 1));
+ EXPECT_TRUE(hashSet.isEmpty());
+
+ for (size_t i = 0; i < 100; ++i)
+ hashSet.add(MoveOnly(i + 1));
+
+ HashSet<MoveOnly> secondSet;
+
+ for (size_t i = 0; i < 100; ++i)
+ secondSet.add(hashSet.takeAny());
+
+ EXPECT_TRUE(hashSet.isEmpty());
+
+ for (size_t i = 0; i < 100; ++i)
+ EXPECT_TRUE(secondSet.contains(MoveOnly(i + 1)));
+}
+
+
+TEST(WTF_HashSet, UniquePtrKey)
+{
+ ConstructorDestructorCounter::TestingScope scope;
+
+ HashSet<std::unique_ptr<ConstructorDestructorCounter>> set;
+
+ auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
+ set.add(WTFMove(uniquePtr));
+
+ EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
+ EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
+
+ set.clear();
+
+ EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
+ EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
+}
+
+TEST(WTF_HashSet, UniquePtrKey_FindUsingRawPointer)
+{
+ HashSet<std::unique_ptr<int>> set;
+
+ auto uniquePtr = std::make_unique<int>(5);
+ int* ptr = uniquePtr.get();
+ set.add(WTFMove(uniquePtr));
+
+ auto it = set.find(ptr);
+ ASSERT_TRUE(it != set.end());
+ EXPECT_EQ(ptr, it->get());
+ EXPECT_EQ(5, *it->get());
+}
+
+TEST(WTF_HashSet, UniquePtrKey_ContainsUsingRawPointer)
+{
+ HashSet<std::unique_ptr<int>> set;
+
+ auto uniquePtr = std::make_unique<int>(5);
+ int* ptr = uniquePtr.get();
+ set.add(WTFMove(uniquePtr));
+
+ EXPECT_EQ(true, set.contains(ptr));
+}
+
+TEST(WTF_HashSet, UniquePtrKey_RemoveUsingRawPointer)
+{
+ ConstructorDestructorCounter::TestingScope scope;
+
+ HashSet<std::unique_ptr<ConstructorDestructorCounter>> set;
+
+ auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
+ ConstructorDestructorCounter* ptr = uniquePtr.get();
+ set.add(WTFMove(uniquePtr));
+
+ EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
+ EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
+
+ bool result = set.remove(ptr);
+ EXPECT_EQ(true, result);
+
+ EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
+ EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
}
+TEST(WTF_HashSet, UniquePtrKey_TakeUsingRawPointer)
+{
+ ConstructorDestructorCounter::TestingScope scope;
+
+ HashSet<std::unique_ptr<ConstructorDestructorCounter>> set;
+
+ auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
+ ConstructorDestructorCounter* ptr = uniquePtr.get();
+ set.add(WTFMove(uniquePtr));
+
+ EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
+ EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
+
+ auto result = set.take(ptr);
+ EXPECT_EQ(ptr, result.get());
+
+ EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
+ EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
+
+ result = nullptr;
+
+ EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
+ EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
+}
+
+TEST(WTF_HashSet, CopyEmpty)
+{
+ {
+ HashSet<unsigned> foo;
+ HashSet<unsigned> bar(foo);
+
+ EXPECT_EQ(0u, bar.capacity());
+ EXPECT_EQ(0u, bar.size());
+ }
+ {
+ HashSet<unsigned> foo({ 1, 5, 64, 42 });
+ EXPECT_EQ(4u, foo.size());
+ foo.remove(1);
+ foo.remove(5);
+ foo.remove(42);
+ foo.remove(64);
+ HashSet<unsigned> bar(foo);
+
+ EXPECT_EQ(0u, bar.capacity());
+ EXPECT_EQ(0u, bar.size());
+ }
+}
+
+TEST(WTF_HashSet, CopyAllocateAtLeastMinimumCapacity)
+{
+ HashSet<unsigned> foo({ 42 });
+ EXPECT_EQ(1u, foo.size());
+ HashSet<unsigned> bar(foo);
+
+ EXPECT_EQ(8u, bar.capacity());
+ EXPECT_EQ(1u, bar.size());
+}
+
+TEST(WTF_HashSet, CopyCapacityIsNotOnBoundary)
+{
+ // Starting at 4 because the minimum size is 8.
+ // With a size of 8, a medium load can be up to 3.3333->3.
+ // Adding 1 to 3 would reach max load.
+ // While correct, that's not really what we care about here.
+ for (unsigned size = 4; size < 100; ++size) {
+ HashSet<unsigned> source;
+ for (unsigned i = 1; i < size + 1; ++i)
+ source.add(i);
+
+ HashSet<unsigned> copy1(source);
+ HashSet<unsigned> copy2(source);
+ HashSet<unsigned> copy3(source);
+
+ EXPECT_EQ(size, copy1.size());
+ EXPECT_EQ(size, copy2.size());
+ EXPECT_EQ(size, copy3.size());
+ for (unsigned i = 1; i < size + 1; ++i) {
+ EXPECT_TRUE(copy1.contains(i));
+ EXPECT_TRUE(copy2.contains(i));
+ EXPECT_TRUE(copy3.contains(i));
+ }
+ EXPECT_FALSE(copy1.contains(size + 2));
+ EXPECT_FALSE(copy2.contains(size + 2));
+ EXPECT_FALSE(copy3.contains(size + 2));
+
+ EXPECT_TRUE(copy2.remove(1));
+ EXPECT_EQ(copy1.capacity(), copy2.capacity());
+ EXPECT_FALSE(copy2.contains(1));
+
+ EXPECT_TRUE(copy3.add(size + 2).isNewEntry);
+ EXPECT_EQ(copy1.capacity(), copy3.capacity());
+ EXPECT_TRUE(copy3.contains(size + 2));
+ }
+}
+
+TEST(WTF_HashSet, RefPtrNotZeroedBeforeDeref)
+{
+ struct DerefObserver {
+ NEVER_INLINE void ref()
+ {
+ ++count;
+ }
+ NEVER_INLINE void deref()
+ {
+ --count;
+ observedBucket = bucketAddress->get();
+ }
+ unsigned count { 1 };
+ const RefPtr<DerefObserver>* bucketAddress { nullptr };
+ const DerefObserver* observedBucket { nullptr };
+ };
+
+ auto observer = std::make_unique<DerefObserver>();
+
+ HashSet<RefPtr<DerefObserver>> set;
+ set.add(adoptRef(observer.get()));
+
+ auto iterator = set.find(observer.get());
+ EXPECT_TRUE(iterator != set.end());
+
+ observer->bucketAddress = iterator.get();
+
+ EXPECT_TRUE(observer->observedBucket == nullptr);
+ EXPECT_TRUE(set.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<DerefObserver>::hashTableDeletedValue());
+ EXPECT_EQ(observer->count, 0u);
+}
+
+
+TEST(WTF_HashSet, UniquePtrNotZeroedBeforeDestructor)
+{
+ struct DestructorObserver {
+ ~DestructorObserver()
+ {
+ observe();
+ }
+ std::function<void()> observe;
+ };
+
+ const std::unique_ptr<DestructorObserver>* bucketAddress = nullptr;
+ const DestructorObserver* observedBucket = nullptr;
+ std::unique_ptr<DestructorObserver> observer(new DestructorObserver { [&]() {
+ observedBucket = bucketAddress->get();
+ }});
+
+ const DestructorObserver* observerAddress = observer.get();
+
+ HashSet<std::unique_ptr<DestructorObserver>> set;
+ auto addResult = set.add(WTFMove(observer));
+
+ EXPECT_TRUE(addResult.isNewEntry);
+ EXPECT_TRUE(observedBucket == nullptr);
+
+ bucketAddress = addResult.iterator.get();
+
+ EXPECT_TRUE(observedBucket == nullptr);
+ EXPECT_TRUE(set.remove(*addResult.iterator));
+
+ EXPECT_TRUE(observedBucket == observerAddress || observedBucket == reinterpret_cast<const DestructorObserver*>(-1));
+}
+
+
} // namespace TestWebKitAPI