Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/wtf/RefPtrHashMap.h

    r76248 r101806  
    11/*
    2  * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
     2 * Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved.
    33 *
    44 * This library is free software; you can redistribute it and/or
    … …  
    2424namespace WTF {
    2525
    26     // This specialization is a direct copy of HashMap, with overloaded functions
     26    // This specialization is a copy of HashMap for use with RefPtr keys, with overloaded functions
    2727    // to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn.
    2828   
    29     // FIXME: Find a better way that doesn't require an entire copy of the HashMap template.
     29     // FIXME: Find a way to do this with traits that doesn't require a copy of the HashMap template.
    3030   
    31     template<typename RawKeyType, typename ValueType, typename ValueTraits, typename HashFunctions>
    32     struct RefPtrHashMapRawKeyTranslator {
    33         typedef typename ValueType::first_type KeyType;
    34         typedef typename ValueType::second_type MappedType;
    35         typedef typename ValueTraits::FirstTraits KeyTraits;
    36         typedef typename ValueTraits::SecondTraits MappedTraits;
    37 
    38         static unsigned hash(RawKeyType key) { return HashFunctions::hash(key); }
    39         static bool equal(const KeyType& a, RawKeyType b) { return HashFunctions::equal(a, b); }
    40         static void translate(ValueType& location, RawKeyType key, const MappedType& mapped)
    41         {
    42             location.first = key;
    43             location.second = mapped;
    44         }
    45     };
    46 
    4731    template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
    4832    class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> {
    … …  
    6044
    6145    private:
     46        typedef const MappedType& MappedPassInType;
     47        typedef MappedType MappedPassOutType;
     48        typedef MappedType MappedPeekType;
     49       
    6250        typedef HashArg HashFunctions;
    6351
    … …  
    6553            HashFunctions, ValueTraits, KeyTraits> HashTableType;
    6654
    67         typedef RefPtrHashMapRawKeyTranslator<RawKeyType, ValueType, ValueTraits, HashFunctions>
    68             RawKeyTranslator;
     55        typedef HashMapTranslator<ValueTraits, HashFunctions>
     56            Translator;
    6957
    7058    public:
    … …  
    9078        bool contains(const KeyType&) const;
    9179        bool contains(RawKeyType) const;
    92         MappedType get(const KeyType&) const;
    93         MappedType get(RawKeyType) const;
    94         MappedType inlineGet(RawKeyType) const;
     80        MappedPeekType get(const KeyType&) const;
     81        MappedPeekType get(RawKeyType) const;
     82        MappedPeekType inlineGet(RawKeyType) const;
    9583
    9684        // replaces value but not key if key is already present
    9785        // return value is a pair of the iterator to the key location,
    9886        // and a boolean that's true if a new value was actually added
    99         pair<iterator, bool> set(const KeyType&, const MappedType&);
    100         pair<iterator, bool> set(RawKeyType, const MappedType&);
     87        pair<iterator, bool> set(const KeyType&, MappedPassInType);
     88        pair<iterator, bool> set(RawKeyType, MappedPassInType);
    10189
    10290        // does nothing if key is already present
    10391        // return value is a pair of the iterator to the key location,
    10492        // and a boolean that's true if a new value was actually added
    105         pair<iterator, bool> add(const KeyType&, const MappedType&);
    106         pair<iterator, bool> add(RawKeyType, const MappedType&);
     93        pair<iterator, bool> add(const KeyType&, MappedPassInType);
     94        pair<iterator, bool> add(RawKeyType, MappedPassInType);
    10795
    10896        void remove(const KeyType&);
    … …  
    11199        void clear();
    112100
    113         MappedType take(const KeyType&); // efficient combination of get with remove
    114         MappedType take(RawKeyType); // efficient combination of get with remove
     101        MappedPassOutType take(const KeyType&); // efficient combination of get with remove
     102        MappedPassOutType take(RawKeyType); // efficient combination of get with remove
    115103
    116104    private:
    117         pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
    118         pair<iterator, bool> inlineAdd(RawKeyType, const MappedType&);
     105        pair<iterator, bool> inlineAdd(const KeyType&, MappedPassInType);
     106        pair<iterator, bool> inlineAdd(RawKeyType, MappedPassInType);
    119107
    120108        HashTableType m_impl;
    … …  
    178166    inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key)
    179167    {
    180         return m_impl.template find<RawKeyType, RawKeyTranslator>(key);
     168        return m_impl.template find<Translator>(key);
    181169    }
    182170
    … …  
    190178    inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) const
    191179    {
    192         return m_impl.template find<RawKeyType, RawKeyTranslator>(key);
     180        return m_impl.template find<Translator>(key);
    193181    }
    194182
    … …  
    202190    inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const
    203191    {
    204         return m_impl.template contains<RawKeyType, RawKeyTranslator>(key);
     192        return m_impl.template contains<Translator>(key);
    205193    }
    206194
    207195    template<typename T, typename U, typename V, typename W, typename X>
    208196    inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
    209     HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped)
    210     {
    211         typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType;
    212         return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
     197    HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInType mapped)
     198    {
     199        return m_impl.template add<Translator>(key, mapped);
    213200    }
    214201
    215202    template<typename T, typename U, typename V, typename W, typename X>
    216203    inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
    217     HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType& mapped)
    218     {
    219         return m_impl.template add<RawKeyType, MappedType, RawKeyTranslator>(key, mapped);
     204    HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, MappedPassInType mapped)
     205    {
     206        return m_impl.template add<Translator>(key, mapped);
    220207    }
    221208
    222209    template<typename T, typename U, typename V, typename W, typename X>
    223210    pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
    224     HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, const MappedType& mapped)
     211    HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, MappedPassInType mapped)
    225212    {
    226213        pair<iterator, bool> result = inlineAdd(key, mapped);
    … …  
    234221    template<typename T, typename U, typename V, typename W, typename X>
    235222    pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
    236     HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, const MappedType& mapped)
     223    HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, MappedPassInType mapped)
    237224    {
    238225        pair<iterator, bool> result = inlineAdd(key, mapped);
    … …  
    246233    template<typename T, typename U, typename V, typename W, typename X>
    247234    pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
    248     HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
     235    HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType& key, MappedPassInType mapped)
    249236    {
    250237        return inlineAdd(key, mapped);
    … …  
    253240    template<typename T, typename U, typename V, typename W, typename X>
    254241    pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
    255     HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, const MappedType& mapped)
     242    HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, MappedPassInType mapped)
    256243    {
    257244        return inlineAdd(key, mapped);
    … …  
    259246
    260247    template<typename T, typename U, typename V, typename W, typename MappedTraits>
    261     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
     248    typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPeekType
    262249    HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType& key) const
    263250    {
    … …  
    269256
    270257    template<typename T, typename U, typename V, typename W, typename MappedTraits>
    271     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
     258    typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPeekType
    272259    inline HashMap<RefPtr<T>, U, V, W, MappedTraits>::inlineGet(RawKeyType key) const
    273260    {
    274         ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<RawKeyType, RawKeyTranslator>(key);
     261        ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<Translator>(key);
    275262        if (!entry)
    276263            return MappedTraits::emptyValue();
    … …  
    279266
    280267    template<typename T, typename U, typename V, typename W, typename MappedTraits>
    281     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
     268    typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPeekType
    282269    HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const
    283270    {
    … …  
    313300
    314301    template<typename T, typename U, typename V, typename W, typename MappedTraits>
    315     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
     302    typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPassOutType
    316303    HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key)
    317304    {
    … …  
    320307        if (it == end())
    321308            return MappedTraits::emptyValue();
    322         typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
     309        MappedPassOutType result = it->second;
    323310        remove(it);
    324311        return result;
    … …  
    326313
    327314    template<typename T, typename U, typename V, typename W, typename MappedTraits>
    328     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
     315    typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPassOutType
    329316    HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key)
    330317    {
    … …  
    333320        if (it == end())
    334321            return MappedTraits::emptyValue();
    335         typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
     322        MappedPassOutType result = it->second;
    336323        remove(it);
    337324        return result;
Note: See TracChangeset for help on using the changeset viewer.