Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (101941 => 101942)
--- trunk/Source/_javascript_Core/ChangeLog 2011-12-04 03:25:41 UTC (rev 101941)
+++ trunk/Source/_javascript_Core/ChangeLog 2011-12-04 03:45:11 UTC (rev 101942)
@@ -1,3 +1,23 @@
+2011-12-03 Darin Adler <[email protected]>
+
+ Change HashMap implementation to use the pass type and peek type from traits for the mapped value
+ https://bugs.webkit.org/show_bug.cgi?id=72474
+
+ Reviewed by Anders Carlsson.
+
+ * wtf/HashMap.h: Added ReferenceTypeMaker struct template. Get PassInType, PassOutType,
+ and PeekType from the traits of the mapped value instead of hard-coding them here.
+ Changed inlineAdd to take a reference to the PassInType instead of the PassInType itself,
+ to accomodate a PassInType that can't be copied. Use the store, peek, and passOut
+ functions from the traits as well.
+
+ * wtf/HashTraits.h: Updated GenericHashTraits and HashTraits for OwnPtr to include
+ PassInType, PassOutType, PeekType, store, passOut, and peek. Before this, the file had
+ an earlier version that was just PassType, PeekType, pass, and peek. Also commented
+ the HashTraits for RefPtr to foreshadow some work we can do there.
+
+ * wtf/RefPtrHashMap.h: Same changes as HashMap.h.
+
2011-12-02 David Levin <[email protected]>
Rename WTF class from TemporarilyChange to TemporaryChange.
Modified: trunk/Source/_javascript_Core/wtf/HashMap.h (101941 => 101942)
--- trunk/Source/_javascript_Core/wtf/HashMap.h 2011-12-04 03:25:41 UTC (rev 101941)
+++ trunk/Source/_javascript_Core/wtf/HashMap.h 2011-12-04 03:45:11 UTC (rev 101942)
@@ -27,6 +27,13 @@
template<typename PairType> struct PairFirstExtractor;
+ template<typename T> struct ReferenceTypeMaker {
+ typedef T& ReferenceType;
+ };
+ template<typename T> struct ReferenceTypeMaker<T&> {
+ typedef T& ReferenceType;
+ };
+
template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> >
class HashMap {
@@ -42,10 +49,12 @@
typedef typename ValueTraits::TraitType ValueType;
private:
- typedef const MappedType& MappedPassInType;
- typedef MappedType MappedPassOutType;
- typedef MappedType MappedPeekType;
-
+ typedef typename MappedTraits::PassInType MappedPassInType;
+ typedef typename MappedTraits::PassOutType MappedPassOutType;
+ typedef typename MappedTraits::PeekType MappedPeekType;
+
+ typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType MappedPassInReferenceType;
+
typedef HashArg HashFunctions;
typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>,
@@ -108,7 +117,7 @@
void checkConsistency() const;
private:
- pair<iterator, bool> inlineAdd(const KeyType&, MappedPassInType);
+ pair<iterator, bool> inlineAdd(const KeyType&, MappedPassInReferenceType);
HashTableType m_impl;
};
@@ -124,7 +133,7 @@
template<typename T, typename U, typename V> static void translate(T& location, const U& key, const V& mapped)
{
location.first = key;
- location.second = mapped;
+ ValueTraits::SecondTraits::store(mapped, location.second);
}
};
@@ -135,7 +144,7 @@
template<typename T, typename U, typename V> static void translate(T& location, const U& key, const V& mapped, unsigned hashCode)
{
Translator::translate(location.first, key, hashCode);
- location.second = mapped;
+ ValueTraits::SecondTraits::store(mapped, location.second);
}
};
@@ -231,7 +240,7 @@
template<typename T, typename U, typename V, typename W, typename X>
inline pair<typename HashMap<T, U, V, W, X>::iterator, bool>
- HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInType mapped)
+ HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInReferenceType mapped)
{
return m_impl.template add<HashMapTranslator<ValueTraits, HashFunctions> >(key, mapped);
}
@@ -242,8 +251,8 @@
{
pair<iterator, bool> result = inlineAdd(key, mapped);
if (!result.second) {
- // add call above didn't change anything, so set the mapped value
- result.first->second = mapped;
+ // The inlineAdd call above found an existing hash table entry; we need to set the mapped value.
+ MappedTraits::store(mapped, result.first->second);
}
return result;
}
@@ -269,8 +278,8 @@
{
ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key);
if (!entry)
- return MappedTraits::emptyValue();
- return entry->second;
+ return MappedTraits::peek(MappedTraits::emptyValue());
+ return MappedTraits::peek(entry->second);
}
template<typename T, typename U, typename V, typename W, typename X>
@@ -298,11 +307,10 @@
typename HashMap<T, U, V, W, MappedTraits>::MappedPassOutType
HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key)
{
- // This can probably be made more efficient to avoid ref/deref churn.
iterator it = find(key);
if (it == end())
- return MappedTraits::emptyValue();
- MappedPassOutType result = it->second;
+ return MappedTraits::passOut(MappedTraits::emptyValue());
+ MappedPassOutType result = MappedTraits::passOut(it->second);
remove(it);
return result;
}
@@ -313,7 +321,6 @@
m_impl.checkTableConsistency();
}
-
template<typename T, typename U, typename V, typename W, typename X>
bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
{
Modified: trunk/Source/_javascript_Core/wtf/HashTraits.h (101941 => 101942)
--- trunk/Source/_javascript_Core/wtf/HashTraits.h 2011-12-04 03:25:41 UTC (rev 101941)
+++ trunk/Source/_javascript_Core/wtf/HashTraits.h 2011-12-04 03:45:11 UTC (rev 101942)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
+ * Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
@@ -56,11 +56,23 @@
template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
typedef T TraitType;
+
static T emptyValue() { return T(); }
- typedef const T& PassType;
- static const T& pass(const T& value) { return value; }
- typedef const T& PeekType;
- static const T& peek(const T& value) { return value; }
+
+ // Type for functions that take ownership, such as add.
+ // The store function either not be called or called once to store something passed in.
+ // The value passed to the store function will be either PassInType or PassInType&.
+ typedef const T& PassInType;
+ static void store(const T& value, T& storage) { storage = value; }
+
+ // Type for return value of functions that transfer ownership, such as take.
+ typedef T PassOutType;
+ static PassOutType passOut(const T& value) { return value; }
+
+ // Type for return value of functions that do not transfer ownership, such as get.
+ // FIXME: We should change this type to const T& for better performance.
+ typedef T PeekType;
+ static PeekType peek(const T& value) { return value; }
};
template<typename T> struct HashTraits : GenericHashTraits<T> { };
@@ -99,13 +111,25 @@
template<typename P> struct HashTraits<OwnPtr<P> > : SimpleClassHashTraits<OwnPtr<P> > {
static std::nullptr_t emptyValue() { return nullptr; }
- typedef PassOwnPtr<P> PassType;
- static PassOwnPtr<P> pass(const OwnPtr<P>& value) { return value.release(); }
+
+ typedef PassOwnPtr<P> PassInType;
+ static void store(PassOwnPtr<P> value, OwnPtr<P>& storage) { storage = value; }
+
+ typedef PassOwnPtr<P> PassOutType;
+ static PassOwnPtr<P> passOut(OwnPtr<P>& value) { return value.release(); }
+
typedef typename OwnPtr<P>::PtrType PeekType;
static PeekType peek(const OwnPtr<P>& value) { return value.get(); }
static PeekType peek(std::nullptr_t) { return 0; }
};
- template<typename P> struct HashTraits<RefPtr<P> > : SimpleClassHashTraits<RefPtr<P> > { };
+
+ template<typename P> struct HashTraits<RefPtr<P> > : SimpleClassHashTraits<RefPtr<P> > {
+ // FIXME: We should change PassInType to PassRefPtr for better performance.
+ // FIXME: We should change PassOutType to PassRefPtr for better performance.
+ // FIXME: We could consider changing PeekType to a raw pointer so callers don't need to
+ // call get; doing so will require updating many call sites.
+ };
+
template<> struct HashTraits<String> : SimpleClassHashTraits<String> { };
// special traits for pairs, helpful for their use in HashMap implementation
Modified: trunk/Source/_javascript_Core/wtf/RefPtrHashMap.h (101941 => 101942)
--- trunk/Source/_javascript_Core/wtf/RefPtrHashMap.h 2011-12-04 03:25:41 UTC (rev 101941)
+++ trunk/Source/_javascript_Core/wtf/RefPtrHashMap.h 2011-12-04 03:45:11 UTC (rev 101942)
@@ -43,9 +43,11 @@
typedef typename ValueTraits::TraitType ValueType;
private:
- typedef const MappedType& MappedPassInType;
- typedef MappedType MappedPassOutType;
- typedef MappedType MappedPeekType;
+ typedef typename MappedTraits::PassInType MappedPassInType;
+ typedef typename MappedTraits::PassOutType MappedPassOutType;
+ typedef typename MappedTraits::PeekType MappedPeekType;
+
+ typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType MappedPassInReferenceType;
typedef HashArg HashFunctions;
@@ -102,8 +104,8 @@
MappedPassOutType take(RawKeyType); // efficient combination of get with remove
private:
- pair<iterator, bool> inlineAdd(const KeyType&, MappedPassInType);
- pair<iterator, bool> inlineAdd(RawKeyType, MappedPassInType);
+ pair<iterator, bool> inlineAdd(const KeyType&, MappedPassInReferenceType);
+ pair<iterator, bool> inlineAdd(RawKeyType, MappedPassInReferenceType);
HashTableType m_impl;
};
@@ -194,14 +196,14 @@
template<typename T, typename U, typename V, typename W, typename X>
inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
- HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInType mapped)
+ HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInReferenceType mapped)
{
return m_impl.template add<Translator>(key, mapped);
}
template<typename T, typename U, typename V, typename W, typename X>
inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
- HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, MappedPassInType mapped)
+ HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, MappedPassInReferenceType mapped)
{
return m_impl.template add<Translator>(key, mapped);
}
@@ -212,8 +214,8 @@
{
pair<iterator, bool> result = inlineAdd(key, mapped);
if (!result.second) {
- // add call above didn't change anything, so set the mapped value
- result.first->second = mapped;
+ // The inlineAdd call above found an existing hash table entry; we need to set the mapped value.
+ MappedTraits::store(mapped, result.first->second);
}
return result;
}
@@ -224,8 +226,8 @@
{
pair<iterator, bool> result = inlineAdd(key, mapped);
if (!result.second) {
- // add call above didn't change anything, so set the mapped value
- result.first->second = mapped;
+ // The inlineAdd call above found an existing hash table entry; we need to set the mapped value.
+ MappedTraits::store(mapped, result.first->second);
}
return result;
}
@@ -250,8 +252,8 @@
{
ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key);
if (!entry)
- return MappedTraits::emptyValue();
- return entry->second;
+ return MappedTraits::peek(MappedTraits::emptyValue());
+ return MappedTraits::peek(entry->second);
}
template<typename T, typename U, typename V, typename W, typename MappedTraits>
@@ -260,8 +262,8 @@
{
ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<Translator>(key);
if (!entry)
- return MappedTraits::emptyValue();
- return entry->second;
+ return MappedTraits::peek(MappedTraits::emptyValue());
+ return MappedTraits::peek(entry->second);
}
template<typename T, typename U, typename V, typename W, typename MappedTraits>
@@ -302,11 +304,10 @@
typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPassOutType
HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key)
{
- // This can probably be made more efficient to avoid ref/deref churn.
iterator it = find(key);
if (it == end())
- return MappedTraits::emptyValue();
- MappedPassOutType result = it->second;
+ return MappedTraits::passOut(MappedTraits::emptyValue());
+ MappedPassOutType result = MappedTraits::passOut(it->second);
remove(it);
return result;
}
@@ -315,11 +316,10 @@
typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPassOutType
HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key)
{
- // This can probably be made more efficient to avoid ref/deref churn.
iterator it = find(key);
if (it == end())
- return MappedTraits::emptyValue();
- MappedPassOutType result = it->second;
+ return MappedTraits::passOut(MappedTraits::emptyValue());
+ MappedPassOutType result = MappedTraits::passOut(it->second);
remove(it);
return result;
}
