Improve HashMap and HashSet support for Ref
https://bugs.webkit.org/show_bug.cgi?id=158789
Patch by Sam Weinig <sam@webkit.org> on 2016-06-15
Reviewed by Chris Dumez.
Source/WTF:
Tests: Add more cases to WTF_HashMap.Ref_Key, WTF_HashMap.Ref_Value and WTF_HashSet.Ref
* wtf/HashMap.h:
* wtf/HashSet.h:
Add a MappedTakeType typedef and rework the take functions to use it and HashTraits::take(...).
* wtf/HashTraits.h:
(WTF::GenericHashTraits::assignToEmpty):
Move to GenericHashTraits rather than GenericHashTraitsBase, since it is not different
between integral and non-integral HashTraits.
(WTF::GenericHashTraits::take):
Add a trait function for take that defaults as a forward. This allows us to override take
just like we do with get/peek.
(WTF::HashTraits<Ref<P>>::emptyValue):
Remove unnecessary explicit construction.
(WTF::HashTraits<Ref<P>>::peek):
Fix assertion that could happen if you did a HashMap.get() on an empty Ref value.
(WTF::HashTraits<Ref<P>>::take):
Make the TakeType of a Ref<P> be Optional<Ref<P>>, to avoid having empty
Refs returned from HashMap and HashSet. Implement an explicit take() function to
construct one.
(WTF::HashTraits<Ref<P>>::customDeleteBucket): Deleted.
Remove unnecessary customDeleteBucket implementation. Ref does not assign nullptr to
it's m_ptr in destruction, so there is no dead store to avoid here.
* wtf/Ref.h:
(WTF::Ref::ptrAllowingHashTableEmptyValue):
Add HashTrait helper to allow getting the value of m_ptr even when it is null. This
allows us to avoid a branch in HashTraits<Ref<P>>::peek().
Tools:
* TestWebKitAPI/Tests/WTF/HashMap.cpp:
* TestWebKitAPI/Tests/WTF/HashSet.cpp:
Add more cases to WTF_HashMap.Ref_Key, WTF_HashMap.Ref_Value and WTF_HashSet.Ref
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@202111 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/WTF/ChangeLog b/Source/WTF/ChangeLog
index 5e75af2..b46b287 100644
--- a/Source/WTF/ChangeLog
+++ b/Source/WTF/ChangeLog
@@ -1,3 +1,45 @@
+2016-06-15 Sam Weinig <sam@webkit.org>
+
+ Improve HashMap and HashSet support for Ref
+ https://bugs.webkit.org/show_bug.cgi?id=158789
+
+ Reviewed by Chris Dumez.
+
+ Tests: Add more cases to WTF_HashMap.Ref_Key, WTF_HashMap.Ref_Value and WTF_HashSet.Ref
+
+ * wtf/HashMap.h:
+ * wtf/HashSet.h:
+ Add a MappedTakeType typedef and rework the take functions to use it and HashTraits::take(...).
+
+ * wtf/HashTraits.h:
+ (WTF::GenericHashTraits::assignToEmpty):
+ Move to GenericHashTraits rather than GenericHashTraitsBase, since it is not different
+ between integral and non-integral HashTraits.
+
+ (WTF::GenericHashTraits::take):
+ Add a trait function for take that defaults as a forward. This allows us to override take
+ just like we do with get/peek.
+
+ (WTF::HashTraits<Ref<P>>::emptyValue):
+ Remove unnecessary explicit construction.
+
+ (WTF::HashTraits<Ref<P>>::peek):
+ Fix assertion that could happen if you did a HashMap.get() on an empty Ref value.
+
+ (WTF::HashTraits<Ref<P>>::take):
+ Make the TakeType of a Ref<P> be Optional<Ref<P>>, to avoid having empty
+ Refs returned from HashMap and HashSet. Implement an explicit take() function to
+ construct one.
+
+ (WTF::HashTraits<Ref<P>>::customDeleteBucket): Deleted.
+ Remove unnecessary customDeleteBucket implementation. Ref does not assign nullptr to
+ it's m_ptr in destruction, so there is no dead store to avoid here.
+
+ * wtf/Ref.h:
+ (WTF::Ref::ptrAllowingHashTableEmptyValue):
+ Add HashTrait helper to allow getting the value of m_ptr even when it is null. This
+ allows us to avoid a branch in HashTraits<Ref<P>>::peek().
+
2016-06-15 Konstantin Tokarev <annulen@yandex.ru>
Only Mac port needs ObjC API for JSC
diff --git a/Source/WTF/wtf/HashMap.h b/Source/WTF/wtf/HashMap.h
index 40d132c..06179d9 100644
--- a/Source/WTF/wtf/HashMap.h
+++ b/Source/WTF/wtf/HashMap.h
@@ -54,6 +54,7 @@
private:
typedef typename MappedTraits::PeekType MappedPeekType;
+ typedef typename MappedTraits::TakeType MappedTakeType;
typedef HashArg HashFunctions;
@@ -130,7 +131,7 @@
void removeIf(const Functor& functor);
void clear();
- MappedType take(const KeyType&); // efficient combination of get with remove
+ MappedTakeType take(const KeyType&); // efficient combination of get with remove
// An alternate version of find() that finds the object by hashing and comparing
// with some other type, to avoid the cost of type conversion. HashTranslator
@@ -156,7 +157,7 @@
template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, MappedPeekType>::type inlineGet(typename GetPtrHelper<K>::PtrType) const;
template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, MappedPeekType>::type get(typename GetPtrHelper<K>::PtrType) const;
template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, bool>::type remove(typename GetPtrHelper<K>::PtrType);
- template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, MappedType>::type take(typename GetPtrHelper<K>::PtrType);
+ template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, MappedTakeType>::type take(typename GetPtrHelper<K>::PtrType);
void checkConsistency() const;
@@ -434,12 +435,12 @@
}
template<typename T, typename U, typename V, typename W, typename MappedTraits>
-auto HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key) -> MappedType
+auto HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key) -> MappedTakeType
{
iterator it = find(key);
if (it == end())
- return MappedTraits::emptyValue();
- MappedType value = WTFMove(it->value);
+ return MappedTraits::take(MappedTraits::emptyValue());
+ auto value = MappedTraits::take(WTFMove(it->value));
remove(it);
return value;
}
@@ -491,12 +492,12 @@
template<typename T, typename U, typename V, typename W, typename X>
template<typename K>
-inline auto HashMap<T, U, V, W, X>::take(typename GetPtrHelper<K>::PtrType key) -> typename std::enable_if<IsSmartPtr<K>::value, MappedType>::type
+inline auto HashMap<T, U, V, W, X>::take(typename GetPtrHelper<K>::PtrType key) -> typename std::enable_if<IsSmartPtr<K>::value, MappedTakeType>::type
{
iterator it = find(key);
if (it == end())
- return MappedTraits::emptyValue();
- MappedType value = WTFMove(it->value);
+ return MappedTraits::take(MappedTraits::emptyValue());
+ auto value = MappedTraits::take(WTFMove(it->value));
remove(it);
return value;
}
diff --git a/Source/WTF/wtf/HashSet.h b/Source/WTF/wtf/HashSet.h
index d21d93e..cf1f942 100644
--- a/Source/WTF/wtf/HashSet.h
+++ b/Source/WTF/wtf/HashSet.h
@@ -38,6 +38,7 @@
private:
typedef HashArg HashFunctions;
typedef TraitsArg ValueTraits;
+ typedef typename ValueTraits::TakeType TakeType;
public:
typedef typename ValueTraits::TraitType ValueType;
@@ -105,15 +106,15 @@
void removeIf(const Functor&);
void clear();
- ValueType take(const ValueType&);
- ValueType take(iterator);
- ValueType takeAny();
+ TakeType take(const ValueType&);
+ TakeType take(iterator);
+ TakeType takeAny();
// Overloads for smart pointer values that take the raw pointer type as the parameter.
template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, iterator>::type find(typename GetPtrHelper<V>::PtrType) const;
template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, bool>::type contains(typename GetPtrHelper<V>::PtrType) const;
template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, bool>::type remove(typename GetPtrHelper<V>::PtrType);
- template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, ValueType>::type take(typename GetPtrHelper<V>::PtrType);
+ template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, TakeType>::type take(typename GetPtrHelper<V>::PtrType);
static bool isValidValue(const ValueType&);
@@ -269,24 +270,24 @@
}
template<typename T, typename U, typename V>
- inline auto HashSet<T, U, V>::take(iterator it) -> ValueType
+ inline auto HashSet<T, U, V>::take(iterator it) -> TakeType
{
if (it == end())
- return ValueTraits::emptyValue();
+ return ValueTraits::take(ValueTraits::emptyValue());
- ValueType result = WTFMove(const_cast<ValueType&>(*it));
+ auto result = ValueTraits::take(WTFMove(const_cast<ValueType&>(*it)));
remove(it);
return result;
}
template<typename T, typename U, typename V>
- inline auto HashSet<T, U, V>::take(const ValueType& value) -> ValueType
+ inline auto HashSet<T, U, V>::take(const ValueType& value) -> TakeType
{
return take(find(value));
}
template<typename T, typename U, typename V>
- inline auto HashSet<T, U, V>::takeAny() -> ValueType
+ inline auto HashSet<T, U, V>::takeAny() -> TakeType
{
return take(begin());
}
@@ -314,7 +315,7 @@
template<typename Value, typename HashFunctions, typename Traits>
template<typename V>
- inline auto HashSet<Value, HashFunctions, Traits>::take(typename GetPtrHelper<V>::PtrType value) -> typename std::enable_if<IsSmartPtr<V>::value, ValueType>::type
+ inline auto HashSet<Value, HashFunctions, Traits>::take(typename GetPtrHelper<V>::PtrType value) -> typename std::enable_if<IsSmartPtr<V>::value, TakeType>::type
{
return take(find(value));
}
diff --git a/Source/WTF/wtf/HashTraits.h b/Source/WTF/wtf/HashTraits.h
index f3aa62e..eb04847 100644
--- a/Source/WTF/wtf/HashTraits.h
+++ b/Source/WTF/wtf/HashTraits.h
@@ -21,10 +21,11 @@
#ifndef WTF_HashTraits_h
#define WTF_HashTraits_h
-#include <wtf/HashFunctions.h>
-#include <wtf/StdLibExtras.h>
-#include <utility>
#include <limits>
+#include <utility>
+#include <wtf/HashFunctions.h>
+#include <wtf/Optional.h>
+#include <wtf/StdLibExtras.h>
namespace WTF {
@@ -43,12 +44,6 @@
// for cases like String that need them.
static const bool hasIsEmptyValueFunction = false;
- template<typename U, typename V>
- static void assignToEmpty(U& emptyValue, V&& value)
- {
- emptyValue = std::forward<V>(value);
- }
-
// The starting table size. Can be overridden when we know beforehand that
// a hash table will have at least N entries.
static const unsigned minimumTableSize = 8;
@@ -67,9 +62,18 @@
static T emptyValue() { return T(); }
+ template<typename U, typename V>
+ static void assignToEmpty(U& emptyValue, V&& value)
+ {
+ emptyValue = std::forward<V>(value);
+ }
+
// Type for return value of functions that do not transfer ownership, such as get.
typedef T PeekType;
template<typename U> static U&& peek(U&& value) { return std::forward<U>(value); }
+
+ typedef T TakeType;
+ template<typename U> static TakeType take(U&& value) { return std::forward<U>(value); }
};
template<typename T> struct HashTraits : GenericHashTraits<T> { };
@@ -173,28 +177,19 @@
template<typename P> struct HashTraits<Ref<P>> : SimpleClassHashTraits<Ref<P>> {
static const bool emptyValueIsZero = true;
- static Ref<P> emptyValue() { return Ref<P>(HashTableEmptyValue); }
+ static Ref<P> emptyValue() { return HashTableEmptyValue; }
static const bool hasIsEmptyValueFunction = true;
static bool isEmptyValue(const Ref<P>& value) { return value.isHashTableEmptyValue(); }
- static void assignToEmpty(Ref<P>& emptyValue, Ref<P>&& newValue)
- {
- ASSERT(isEmptyValue(emptyValue));
- emptyValue.assignToHashTableEmptyValue(WTFMove(newValue));
- }
+ static void assignToEmpty(Ref<P>& emptyValue, Ref<P>&& newValue) { ASSERT(isEmptyValue(emptyValue)); emptyValue.assignToHashTableEmptyValue(WTFMove(newValue)); }
typedef P* PeekType;
- static PeekType peek(const Ref<P>& value) { return const_cast<PeekType>(value.ptr()); }
+ static PeekType peek(const Ref<P>& value) { return const_cast<PeekType>(value.ptrAllowingHashTableEmptyValue()); }
static PeekType peek(P* value) { return value; }
- static void customDeleteBucket(Ref<P>& value)
- {
- // See unique_ptr's customDeleteBucket() for an explanation.
- ASSERT(!SimpleClassHashTraits<Ref<P>>::isDeletedValue(value));
- auto valueToBeDestroyed = WTFMove(value);
- SimpleClassHashTraits<Ref<P>>::constructDeletedValue(value);
- }
+ typedef Optional<Ref<P>> TakeType;
+ static TakeType take(Ref<P>&& value) { return isEmptyValue(value) ? Nullopt : Optional<Ref<P>>(WTFMove(value)); }
};
template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
diff --git a/Source/WTF/wtf/Ref.h b/Source/WTF/wtf/Ref.h
index 2e595e0..bd632db 100644
--- a/Source/WTF/wtf/Ref.h
+++ b/Source/WTF/wtf/Ref.h
@@ -123,6 +123,9 @@
bool isHashTableEmptyValue() const { return m_ptr == hashTableEmptyValue(); }
static T* hashTableEmptyValue() { return nullptr; }
+ const T* ptrAllowingHashTableEmptyValue() const { ASSERT(m_ptr || isHashTableEmptyValue()); return m_ptr; }
+ T* ptrAllowingHashTableEmptyValue() { ASSERT(m_ptr || isHashTableEmptyValue()); return m_ptr; }
+
void assignToHashTableEmptyValue(Ref&& reference)
{
ASSERT(m_ptr == hashTableEmptyValue());
diff --git a/Tools/ChangeLog b/Tools/ChangeLog
index 348bd73..2987f13 100644
--- a/Tools/ChangeLog
+++ b/Tools/ChangeLog
@@ -1,3 +1,14 @@
+2016-06-15 Sam Weinig <sam@webkit.org>
+
+ Improve HashMap and HashSet support for Ref
+ https://bugs.webkit.org/show_bug.cgi?id=158789
+
+ Reviewed by Chris Dumez.
+
+ * TestWebKitAPI/Tests/WTF/HashMap.cpp:
+ * TestWebKitAPI/Tests/WTF/HashSet.cpp:
+ Add more cases to WTF_HashMap.Ref_Key, WTF_HashMap.Ref_Value and WTF_HashSet.Ref
+
2016-06-15 Aakash Jain <aakash_jain@apple.com>
Too much log data generated during layout-tests on iOS Simulator
diff --git a/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp b/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp
index 55ec60f..2906e7b 100644
--- a/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp
+++ b/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp
@@ -833,25 +833,42 @@
Ref<RefLogger> ref(a);
map.add(1, WTFMove(ref));
- ASSERT_EQ(map.get(1), &a);
+ auto aGet = map.get(1);
+ ASSERT_EQ(aGet, &a);
}
ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
{
HashMap<int, Ref<RefLogger>> map;
+
+ auto emptyGet = map.get(1);
+ ASSERT_TRUE(emptyGet == nullptr);
+ }
+
+ {
+ HashMap<int, Ref<RefLogger>> map;
RefLogger a("a");
Ref<RefLogger> ref(a);
map.add(1, WTFMove(ref));
- Ref<RefLogger> aOut = map.take(1);
+ auto aOut = map.take(1);
+ ASSERT_TRUE(static_cast<bool>(aOut));
+ ASSERT_EQ(&a, aOut.value().ptr());
}
ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
{
HashMap<int, Ref<RefLogger>> map;
+
+ auto emptyTake = map.take(1);
+ ASSERT_FALSE(static_cast<bool>(emptyTake));
+ }
+
+ {
+ HashMap<int, Ref<RefLogger>> map;
RefLogger a("a");
Ref<RefLogger> ref(a);
diff --git a/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp b/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp
index c2fbda4..6b81300 100644
--- a/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp
+++ b/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp
@@ -388,6 +388,40 @@
RefLogger a("a");
Ref<RefLogger> ref(a);
set.add(WTFMove(ref));
+
+ auto aOut = set.take(&a);
+ ASSERT_TRUE(static_cast<bool>(aOut));
+ ASSERT_EQ(&a, aOut.value().ptr());
+ }
+
+ ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
+
+ {
+ HashSet<Ref<RefLogger>> set;
+
+ RefLogger a("a");
+ Ref<RefLogger> ref(a);
+ set.add(WTFMove(ref));
+
+ auto aOut = set.takeAny();
+ ASSERT_TRUE(static_cast<bool>(aOut));
+ ASSERT_EQ(&a, aOut.value().ptr());
+ }
+
+ ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
+
+ {
+ HashSet<Ref<RefLogger>> set;
+ auto emptyTake = set.takeAny();
+ ASSERT_FALSE(static_cast<bool>(emptyTake));
+ }
+
+ {
+ HashSet<Ref<RefLogger>> set;
+
+ RefLogger a("a");
+ Ref<RefLogger> ref(a);
+ set.add(WTFMove(ref));
ASSERT_TRUE(set.contains(&a));
}
