Changeset 101806 in webkit for trunk/Source/JavaScriptCore/wtf/HashSet.h

Timestamp:

Dec 2, 2011, 8:50:32 AM (14 years ago)

Author:

Darin Adler

Message:

Prepare to deploy pass and peek types in the HashMap class
​https://bugs.webkit.org/show_bug.cgi?id=73477

Reviewed by Adam Roben.

This patch adds private typedefs inside the HashMap class,
and uses them as appropriate. A future patch will actually
tie those typedefs to hash traits, which will allow us to
make HashMap work with OwnPtr mapped values and to optimize
how HashMap works with RefPtr mapped values.

Also changed the hash translator and adapter struct templates
to use template functions to simplify them and make them more
flexible.

Also removed some unused template arguments.

This goes out of its way to not change behavior. Future patches
will change the peek type to be a reference type, which will
reduce reference count churn a bit for hash tables with RefPtr
mapped values, and then do further optimizations for RefPtr
and OwnPtr by getting types from the hash traits.

• wtf/HashMap.h: Added MappedPassInType, MappedPassOutType,

and MappedPeekType typedefs, and used them for the arguments
and return types of the get, set, add, take, and inlineAdd
functions.
(WTF::HashMapTranslator): Changed this struct template to take
fewer arguments, and changed its member functions to be
function templates instead. This allows the compiler to
determine types more flexibly and also simplifies use of it.
(WTF::HashMapTranslatorAdapter): Ditto.
(WTF::HashMap::find): Updated to use new HashMapTranslatorAdapter.
Also reduced the arguments passed to the HashTable function template.
(WTF::HashMap::contains): Ditto.
(WTF::HashMap::inlineAdd): Ditto. Also take MappedPassInType.
(WTF::HashMap::set): Ditto.
(WTF::HashMap::add): Ditto.
(WTF::HashMap::inlineGet): Ditto, but return MappedPeekType.
(WTF::HashMap::get): Ditto.
(WTF::HashMap::take): Ditto, but return MappedPassOutType and use
that type in the implementation.
(WTF::deleteAllValues): Removed unneeded template arguments from
call to deleteAllPairSeconds.
(WTF::deleteAllKeys): Removed unneeded template arguments from
call to deleteAllPairFirsts.

• wtf/HashSet.h:

(WTF::IdentityExtractor): Changed this to be a struct rather than
a struct template, and replaced the extract function with a function
template. This allows the compiler to deduce the type.
(WTF::HashSetTranslatorAdapter): Changed this struct template to take
fewer arguments, and changed its member functions to be
function templates instead. This allows the compiler to
determine types more flexibly and also simplifies use of it.
(WTF::HashSet::find): Updated to use new HashSetTranslatorAdapter.
Also reduced the arguments passed to the HashTable function template.
(WTF::HashSet::contains): Ditto.
(WTF::HashSet::add): Ditto.

• wtf/HashTable.h:

(WTF::IdentityHashTranslator): Changed this struct template to take
fewer arguments, and changed its member functions to be
function templates instead. This allows the compiler to
determine types more flexibly and also simplifies use of it.
(WTF::HashTable::add): Reduced arguments passed to the function template.
(WTF::HashTable::find): Ditto, also reversed the template arguments so the
translator comes first so the compiler can deduce the other type.
(WTF::HashTable::contains): Ditto.
(WTF::HashTable::lookup): Ditto.
(WTF::HashTable::lookupForWriting): Ditto.
(WTF::HashTable::checkKey): Ditto.
(WTF::HashTable::fullLookupForWriting): Ditto.
(WTF::HashTable::add): Ditto.
(WTF::HashTable::addPassingHashCode): Ditto.
(WTF::HashTable::find): Ditto.
(WTF::HashTable::contains): Ditto.

• wtf/ListHashSet.h:

(WTF::ListHashSetNodeHashFunctions): Changed this struct template to take
fewer arguments, and changed its member functions to be function templates
instead. This allows the compiler to determine types more flexibly and
also simplifies use of it.
(WTF::ListHashSet::find): Reduced the arguments passed to the HashTable
functon template.
(WTF::ListHashSetTranslatorAdapter): Changed this struct template in the
same way we changed ListHashSetNodeHashFunctions above.
(WTF::ListHashSetTranslatorAdapter::equal):
(WTF::::contains):
(WTF::::add):
(WTF::::insertBefore):

• wtf/RefPtrHashMap.h: Updated comments. Removed the

RefPtrHashMapRawKeyTranslator struct template; we can use the
HashMapTranslator struct template from HashMap.h instead now that
it is more flexible. Added MappedPassInType, MappedPassOutType,
and MappedPeekType typedefs, and used them for the arguments
and return types of the get, inlineGet, set, add, take, and inlineAdd
functions. Changed the name of the RawKeyTranslator type to
Translator since it's now a class that can handle both raw keys
and conventional keys.
(WTF::HashMap::find): Changed to use Translator instead of RawKeyTranslator.
Reduced the arguments passed to the HashTable function template.
(WTF::HashMap::contains): Ditto.
(WTF::HashMap::inlineAdd): Ditto. Also take MappedPassInType.
(WTF::HashMap::set): Ditto.
(WTF::HashMap::add): Ditto.
(WTF::HashMap::inlineGet): Ditto, but return MappedPeekType.
(WTF::HashMap::get): Ditto.
(WTF::HashMap::take): Ditto, but return MappedPassOutType and use
that type in the implementation.
(WTF::deleteAllValues): Removed unneeded template arguments from
call to deleteAllPairSeconds.
(WTF::deleteAllKeys): Removed unneeded template arguments from
call to deleteAllPairFirsts.

File:

• trunk/Source/JavaScriptCore/wtf/HashSet.h (modified) (10 diffs)

trunk/Source/JavaScriptCore/wtf/HashSet.h

@@ -1 +1 @@
 /*
- * 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
@@ -27 +27 @@
 namespace WTF {
 
+    struct IdentityExtractor;
+    
     template<typename Value, typename HashFunctions, typename Traits> class HashSet;
     template<typename Value, typename HashFunctions, typename Traits>
@@ -32 +34 @@
     template<typename Value, typename HashFunctions, typename Traits>
     void fastDeleteAllValues(const HashSet<Value, HashFunctions, Traits>&);
-
-    template<typename T> struct IdentityExtractor;
 
     template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
@@ -46 +46 @@
 
     private:
-        typedef HashTable<ValueType, ValueType, IdentityExtractor<ValueType>,
+        typedef HashTable<ValueType, ValueType, IdentityExtractor,
             HashFunctions, ValueTraits, ValueTraits> HashTableType;
 
@@ -70 +70 @@
         //   static unsigned hash(const T&);
         //   static bool equal(const ValueType&, const T&);
+        // FIXME: We should reverse the order of the template arguments so that callers
+        // can just pass the translator and let the compiler deduce T.
         template<typename T, typename HashTranslator> iterator find(const T&) const;
         template<typename T, typename HashTranslator> bool contains(const T&) const;
@@ -83 +85 @@
         //   static bool equal(const ValueType&, const T&);
         //   static translate(ValueType&, const T&, unsigned hashCode);
+        // FIXME: We should reverse the order of the template arguments so that callers
+        // can just pass the translator and let the compiler deduce T.
         template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&);
 
@@ -96 +100 @@
     };
 
-    template<typename T> struct IdentityExtractor {
-        static const T& extract(const T& t) { return t; }
+    struct IdentityExtractor {
+        template<typename T> static const T& extract(const T& t) { return t; }
     };
 
-    template<typename ValueType, typename ValueTraits, typename T, typename Translator>
+    template<typename Translator>
     struct HashSetTranslatorAdapter {
-        static unsigned hash(const T& key) { return Translator::hash(key); }
-        static bool equal(const ValueType& a, const T& b) { return Translator::equal(a, b); }
-        static void translate(ValueType& location, const T& key, const T&, unsigned hashCode)
+        template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
+        template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); }
+        template<typename T, typename U> static void translate(T& location, const U& key, const U&, unsigned hashCode)
         {
             Translator::translate(location, key, hashCode);
@@ -163 +167 @@
     inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const
     {
-        typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
-        return m_impl.template find<T, Adapter>(value);
+        return m_impl.template find<HashSetTranslatorAdapter<HashTranslator> >(value);
     }
 
@@ -171 +174 @@
     inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const
     {
-        typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
-        return m_impl.template contains<T, Adapter>(value);
+        return m_impl.template contains<HashSetTranslatorAdapter<HashTranslator> >(value);
     }
 
@@ -186 +188 @@
     HashSet<Value, HashFunctions, Traits>::add(const T& value)
     {
-        typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
-        return m_impl.template addPassingHashCode<T, T, Adapter>(value, value);
+        return m_impl.template addPassingHashCode<HashSetTranslatorAdapter<HashTranslator> >(value, value);
     }