Ignore:
Timestamp:
Apr 5, 2006, 2:19:57 PM (19 years ago)
Author:
darin
Message:

JavaScriptCore:

Reviewed by Maciej.

Change HashMap and HashSet implementation so they fold various types together.
This allows us to implement maps and sets that use RefPtr<WebCore::StringImpl>
and WebCore::String in terms of the underlying raw pointer type, and hence use
-1 for the deleted value.

  • kxmlcore/HashTraits.h: Added a new type to HashTraits, StorageTraits, which is a type to be used when storing a value that has the same layout as the type itself. This is used only for non-key cases. In the case of keys, the hash function must also be considered. Moved emptyValue out of GenericHashTraitsBase into GenericHashTraits. Added a new bool to HashTraits, needsRef, which indicates whether the type needs explicit reference counting. If the type itself has needsRef true, but the storage type has needsRef false, then the HashSet or HashMap has to handle the reference counting explicitly. Added hash trait specializations for all signed integer values that give -1 as the deleted value. Gave all integers StorageTraits of the canonical integer type of the same size so int and long will share code. Gave all pointers and RefPtrs StorageTraits of the appropriately sized integer type. Removed redundant TraitType and emptyValue definitions in the pointer specialization for HashTraits. Added PairBaseHashTraits, which doesn't try to set up needsDestruction and deletedValue. Useful for types where we don't want to force the existence of deletedValue, such as the type of a pair in a HashMap which is not the actual storage type. Removed an unneeded parameter from the DeletedValueAssigner template. Added HashKeyStorageTraits template, which determines what type can be used to store a given hash key type with a given hash function, and specialized it for pointers and RefPtr so that pointer hash tables share an underlying HashTable that uses IntHash.
  • kxmlcore/HashTable.h: Added HashTableConstIteratorAdapter, HashTableIteratorAdapter, NeedsRef, RefCountManagerBase, RefCountManager, HashTableRefCountManagerBase, and HashTableRefCountManager. All are used by both HashSet and HashMap to handle hash tables where the type stored is not the same as the real value type.


  • kxmlcore/HashFunctions.h: Added a new struct named IntTypes that finds an integer type given a sizeof value. Renamed pointerHash to intHash and made it use overloading and take integer parameters. Added an IntHash struct which is a hash function that works for integers. Changed PtrHash to call IntHash with an appropriately sized integer. Made IntHash the default hash function for many integer types. Made PtrHash the default hash function for RefPtr as well as for raw pointers.
  • kxmlcore/HashSet.h: Changed implementation to use a separate "storage type" derived from the new traits. The HashTable will use the storage type and all necessary translation and ref/deref is done at the HashSet level. Also reorganized the file so that the HashSet is at the top and has no inline implementation inside it so it's easy to read the interface to HashSet.
  • kxmlcore/HashMap.h: Changed implementation to use a separate "storage type" derived from the new traits. The HashTable will use the storage type and all necessary translation and ref/deref is done at the HashMap level. Also reorganized the file so that the HashMap is at the top and has no inline implementation inside it so it's easy to read the interface to HashMap.
  • kxmlcore/HashMapPtrSpec.h: Removed. Superceded by optimizations in HashMap itself.
  • JavaScriptCore.xcodeproj/project.pbxproj: Remove HashMapPtrSpec.h, resort files, and also remove some unnecessary build settings from the aggregate target that generates derived sources.
  • JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj: Ditto.

WebCore:

Reviewed by Maciej.

  • platform/StringHash.h: Added. Moved hash functions and such for WebCore::String and friends into this file so we don't have to include the hash traits header everywhere. Changed hashing for WebCore::StringImpl and WebCore::String so that they use a raw pointer for the underlying storage type, taking advantage of the new feature added in JavaScriptCore.
  • platform/AtomicString.h: Moved StrHash specialization to StringHash.h.
  • platform/PlatformString.h: Moved StrHash specialization to StringHash.h.
  • platform/StringImpl.h: Moved StrHash, CaseInsensitiveHash, and HashTraits to StringHash.h. Left DefaultHash behind so that you can't get the wrong hash function by accident if you forget to include "StringHash.h".
  • platform/StringImpl.cpp: Added include of StringHash.h and removed RefPtr<StringImpl> HashTraits<RefPtr<StringImpl> >::_deleted, which is the object with a global initializer causing all the trouble!
  • kwq/AccessibilityObjectCache.h: Changed hash function to be IntHash instead of PtrHash.
  • dom/StyledElement.cpp: Changed MappedAttributeKeyTraits to inherit from the generic traits in KXMLCore so we get a StorageType. Also cleaned up a tiny bit by adding default values to the MappedAttributeKey constructor.
  • platform/CharsetNames.cpp: Changed hash traits here to be a new TextEncodingIDHashTraits struct rather than defining new default traits for the integer type since more integer types have default traits in HashTraits.h now. Also added a specialization so this class will share the underlying implementation (since InvalidEncoding happens to be -1).
  • bridge/mac/FrameMac.h:
  • dom/Document.h:
  • dom/xml_tokenizer.h:
  • khtml/xsl/XSLTProcessor.h:
  • kwq/JavaAppletWidget.h:
  • page/FramePrivate.h:
  • page/Page.cpp:
  • platform/AtomicString.cpp:
  • platform/TransferJob.h:
  • rendering/render_applet.h: Added include of StringHash.h.
  • WebCore.xcodeproj/project.pbxproj: Added StringHash.h. Remove unneeded CREATE_HASH_TABLE variable in build settings. Re-sorted some file lists. Added quotes to the CREATE_HASH_TABLE initialization in the rule that builds generated files. Removed various unneeded build settings for that target as well.
  • ForwardingHeaders/kxmlcore/HashTraits.h: Added.
  • other minor cleanup
  • bridge/mac/FrameMac.mm: Sorted includes.
  • dom/Node.cpp: Removed bogus symbol after #endif.
  • khtml/xsl/XSLTProcessor.cpp: Sorted includes. Removed redundant using namespace WebCore.
  • loader/Cache.cpp: Ditto.

WebKitTools:

Reviewed by Maciej.

  • Scripts/check-for-global-initializers: Remove StringImpl from the list of files that are allowed to have global initializers.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/kxmlcore/HashSet.h

    r12511 r13703  
    2626
    2727#include "HashTable.h"
    28 #include "HashTraits.h"
    29 #include "HashFunctions.h"
    3028
    3129namespace KXMLCore {
    3230
    33     template <typename T>
    34     struct IdentityExtractor
    35     {
    36         static const T& extract(const T& t)
    37         {
    38             return t;
    39         }
    40     };
    41 
    42     template<typename Value, typename T, typename HashSetTranslator>
    43     struct HashSetTranslatorAdapter
    44     {
    45         static unsigned hash(const T& key)
    46         {
    47             return HashSetTranslator::hash(key);
    48         }
    49        
    50         static bool equal(const Value& a, const T& b)
    51         {
    52             return HashSetTranslator::equal(a, b);
    53         }
    54        
    55         static void translate(Value& location, const T& key, const T&, unsigned hashCode)
    56         {
    57             HashSetTranslator::translate(location, key, hashCode);
    58         }
    59     };
    60    
    61     template<typename Value, typename HashFunctions = typename DefaultHash<Value>::Hash, typename Traits = HashTraits<Value> >
    62     class HashSet {
     31    template<typename T> struct IdentityExtractor;
     32
     33    template<typename Value, typename HashFunctions, typename Traits> class HashSet;
     34    template<typename Value, typename HashFunctions, typename Traits>
     35    void deleteAllValues(HashSet<Value, HashFunctions, Traits>&);
     36
     37    template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
     38        typename TraitsArg = HashTraits<ValueArg> > class HashSet {
    6339    private:
    64         typedef HashTable<Value, Value, IdentityExtractor<Value>, HashFunctions, Traits, Traits> ImplType;
     40        typedef HashArg HashFunctions;
     41        typedef TraitsArg ValueTraits;
     42
     43        typedef typename HashKeyStorageTraits<HashFunctions, ValueTraits>::Hash StorageHashFunctions;
     44
     45        typedef typename HashKeyStorageTraits<HashFunctions, ValueTraits>::Traits StorageTraits;
     46        typedef typename StorageTraits::TraitType StorageType;
     47
     48        typedef HashTable<StorageType, StorageType, IdentityExtractor<StorageType>,
     49            StorageHashFunctions, StorageTraits, StorageTraits> HashTableType;
     50
    6551    public:
    66         typedef Value ValueType;
    67         typedef typename ImplType::iterator iterator;
    68         typedef typename ImplType::const_iterator const_iterator;
    69        
    70         HashSet() {}
    71        
     52        typedef typename ValueTraits::TraitType ValueType;
     53        typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
     54        typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
     55
     56        HashSet();
     57        HashSet(const HashSet&);
     58        HashSet& operator=(const HashSet&);
     59        ~HashSet();
     60
    7261        int size() const;
    7362        int capacity() const;
    7463        bool isEmpty() const;
    75        
     64
    7665        iterator begin();
    7766        iterator end();
    7867        const_iterator begin() const;
    7968        const_iterator end() const;
    80        
    81         iterator find(const ValueType& value);
    82         const_iterator find(const ValueType& value) const;
    83         bool contains(const ValueType& value) const;
    84        
     69
     70        iterator find(const ValueType&);
     71        const_iterator find(const ValueType&) const;
     72        bool contains(const ValueType&) const;
     73
    8574        // the return value is a pair of an interator to the new value's location,
    8675        // and a bool that is true if an new entry was added
    87         std::pair<iterator, bool> add(const ValueType &value);
    88        
     76        pair<iterator, bool> add(const ValueType&);
     77
    8978        // a special version of add() that finds the object by hashing and comparing
    9079        // with some other type, to avoid the cost of type conversion if the object is already
    … …  
    9382        //   static bool equal(const ValueType&, const T&);
    9483        //   static translate(ValueType&, const T&, unsigned hashCode);
    95         template<typename T, typename HashTranslator>
    96         std::pair<iterator, bool> add(const T& value);
    97        
    98         void remove(const ValueType& value);
    99         void remove(iterator it);
     84        template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&);
     85
     86        void remove(const ValueType&);
     87        void remove(iterator);
    10088        void clear();
    101        
     89
    10290    private:
    103         ImplType m_impl;
    104     };
    105    
     91        void refAll();
     92        void derefAll();
     93
     94        friend void deleteAllValues<>(HashSet&);
     95
     96        HashTableType m_impl;
     97    };
     98
     99    template<typename T> struct IdentityExtractor {
     100        static const T& extract(const T& t) { return t; }
     101    };
     102
     103    template<bool canReplaceDeletedValue, typename ValueType, typename StorageTraits, typename HashFunctions>
     104    struct HashSetTranslator;
     105
     106    template<typename ValueType, typename StorageTraits, typename HashFunctions>
     107    struct HashSetTranslator<true, ValueType, StorageTraits, HashFunctions> {
     108        typedef typename StorageTraits::TraitType StorageType;
     109        static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
     110        static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }
     111        static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)
     112        {
     113            *(ValueType*)&location = key;
     114        }
     115    };
     116
     117    template<typename ValueType, typename StorageTraits, typename HashFunctions>
     118    struct HashSetTranslator<false, ValueType, StorageTraits, HashFunctions> {
     119        typedef typename StorageTraits::TraitType StorageType;
     120        static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
     121        static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }
     122        static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)
     123        {
     124            if (location == StorageTraits::deletedValue())
     125                location = StorageTraits::emptyValue();
     126            *(ValueType*)&location = key;
     127        }
     128    };
     129
     130    template<bool canReplaceDeletedValue, typename ValueType, typename StorageTraits, typename T, typename Translator>
     131    struct HashSetTranslatorAdapter;
     132
     133    template<typename ValueType, typename StorageTraits, typename T, typename Translator>
     134    struct HashSetTranslatorAdapter<true, ValueType, StorageTraits, T, Translator> {
     135        typedef typename StorageTraits::TraitType StorageType;
     136        static unsigned hash(const T& key) { return Translator::hash(key); }
     137        static bool equal(const StorageType& a, const T& b) { return Translator::equal(*(const ValueType*)&a, b); }
     138        static void translate(StorageType& location, const T& key, const T&, unsigned hashCode)
     139        {
     140            Translator::translate(*(ValueType*)&location, key, hashCode);
     141        }
     142    };
     143
     144    template<typename ValueType, typename StorageTraits, typename T, typename Translator>
     145    struct HashSetTranslatorAdapter<false, ValueType, StorageTraits, T, Translator> {
     146        typedef typename StorageTraits::TraitType StorageType;
     147        static unsigned hash(const T& key) { return Translator::hash(key); }
     148        static bool equal(const StorageType& a, const T& b) { return Translator::equal(*(const ValueType*)&a, b); }
     149        static void translate(StorageType& location, const T& key, const T&, unsigned hashCode)
     150        {
     151            if (location == StorageTraits::deletedValue())
     152                location = StorageTraits::emptyValue();
     153            Translator::translate(*(ValueType*)&location, key, hashCode);
     154        }
     155    };
     156
     157    template<typename T, typename U, typename V>
     158    inline void HashSet<T, U, V>::refAll()
     159    {
     160        HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
     161    }
     162
     163    template<typename T, typename U, typename V>
     164    inline void HashSet<T, U, V>::derefAll()
     165    {
     166        HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
     167    }
     168
     169    template<typename T, typename U, typename V>
     170    inline HashSet<T, U, V>::HashSet()
     171    {
     172    }
     173
     174    template<typename T, typename U, typename V>
     175    inline HashSet<T, U, V>::HashSet(const HashSet& other)
     176        : m_impl(other.m_impl)
     177    {
     178        refAll();
     179    }
     180
     181    template<typename T, typename U, typename V>
     182    inline HashSet<T, U, V>& HashSet<T, U, V>::operator=(const HashSet& other)
     183    {
     184        HashSet tmp(other);
     185        m_impl.swap(tmp.m_impl);
     186    }
     187
     188    template<typename T, typename U, typename V>
     189    inline HashSet<T, U, V>::~HashSet()
     190    {
     191        derefAll();
     192    }
     193
     194    template<typename T, typename U, typename V>
     195    inline int HashSet<T, U, V>::size() const
     196    {
     197        return m_impl.size();
     198    }
     199
     200    template<typename T, typename U, typename V>
     201    inline int HashSet<T, U, V>::capacity() const
     202    {
     203        return m_impl.capacity();
     204    }
     205
     206    template<typename T, typename U, typename V>
     207    inline bool HashSet<T, U, V>::isEmpty() const
     208    {
     209        return m_impl.isEmpty();
     210    }
     211
     212    template<typename T, typename U, typename V>
     213    inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin()
     214    {
     215        return m_impl.begin();
     216    }
     217
     218    template<typename T, typename U, typename V>
     219    inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end()
     220    {
     221        return m_impl.end();
     222    }
     223
     224    template<typename T, typename U, typename V>
     225    inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::begin() const
     226    {
     227        return m_impl.begin();
     228    }
     229
     230    template<typename T, typename U, typename V>
     231    inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::end() const
     232    {
     233        return m_impl.end();
     234    }
     235
     236    template<typename T, typename U, typename V>
     237    inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value)
     238    {
     239        return m_impl.find(*(const StorageType*)&value);
     240    }
     241
     242    template<typename T, typename U, typename V>
     243    inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::find(const ValueType& value) const
     244    {
     245        return m_impl.find(*(const StorageType*)&value);
     246    }
     247
     248    template<typename T, typename U, typename V>
     249    inline bool HashSet<T, U, V>::contains(const ValueType& value) const
     250    {
     251        return m_impl.contains(*(const StorageType*)&value);
     252    }
     253
     254    template<typename T, typename U, typename V>
     255    pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType &value)
     256    {
     257        const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;
     258        typedef HashSetTranslator<canReplaceDeletedValue, ValueType, StorageTraits, HashFunctions> Translator;
     259        return m_impl.template add<ValueType, ValueType, Translator>(value, value);
     260    }
     261
    106262    template<typename Value, typename HashFunctions, typename Traits>
    107     inline int HashSet<Value, HashFunctions, Traits>::size() const
    108     {
    109         return m_impl.size();
    110     }
    111    
    112     template<typename Value, typename HashFunctions, typename Traits>
    113     int HashSet<Value, HashFunctions, Traits>::capacity() const
    114     {
    115         return m_impl.capacity();
    116     }
    117    
    118     template<typename Value, typename HashFunctions, typename Traits>
    119     inline bool HashSet<Value, HashFunctions, Traits>::isEmpty() const
    120     {
    121         return size() == 0;
    122     }
    123    
    124     template<typename Value, typename HashFunctions, typename Traits>
    125     inline typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::begin()
    126     {
    127         return m_impl.begin();
    128     }
    129 
    130     template<typename Value, typename HashFunctions, typename Traits>
    131     inline typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::end()
    132     {
    133         return m_impl.end();
    134     }
    135    
    136     template<typename Value, typename HashFunctions, typename Traits>
    137     inline typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::begin() const
    138     {
    139         return m_impl.begin();
    140     }
    141    
    142     template<typename Value, typename HashFunctions, typename Traits>
    143     inline typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::end() const
    144     {
    145         return m_impl.end();
    146     }
    147    
    148     template<typename Value, typename HashFunctions, typename Traits>
    149     typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::find(const ValueType& value)
    150     {
    151         return m_impl.find(value);
    152     }
    153    
    154     template<typename Value, typename HashFunctions, typename Traits>
    155     typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::find(const ValueType& value) const
    156     {
    157         return m_impl.find(value);
    158     }
    159    
    160     template<typename Value, typename HashFunctions, typename Traits>
    161     inline bool HashSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const
    162     {
    163         return m_impl.contains(value);
    164     }
    165    
    166     template<typename Value, typename HashFunctions, typename Traits>
    167     std::pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> HashSet<Value, HashFunctions, Traits>::add(const ValueType &value)
    168     {
    169         return m_impl.add(value);
    170     }
    171    
    172     template<typename Value, typename HashFunctions, typename Traits>
    173     template<typename T, typename HashSetTranslator>
    174     std::pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> HashSet<Value, HashFunctions, Traits>::add(const T& value)
    175     {
    176         return m_impl.template add<T, T, HashSetTranslatorAdapter<ValueType, T, HashSetTranslator> >(value, value);
    177     }
    178    
    179     template<typename Value, typename HashFunctions, typename Traits>
    180     void HashSet<Value, HashFunctions, Traits>::remove(const ValueType& value)
    181     {
    182         m_impl.remove(value);
    183     }
    184    
    185     template<typename Value, typename HashFunctions, typename Traits>
    186     void HashSet<Value, HashFunctions, Traits>::remove(iterator it)
    187     {
    188         m_impl.remove(it);
    189     }
    190    
    191     template<typename Value, typename HashFunctions, typename Traits>
    192     void HashSet<Value, HashFunctions, Traits>::clear()
    193     {
     263    template<typename T, typename Translator>
     264    pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>
     265    HashSet<Value, HashFunctions, Traits>::add(const T& value)
     266    {
     267        const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;
     268        typedef HashSetTranslatorAdapter<canReplaceDeletedValue, ValueType, StorageTraits, T, Translator> Adapter;
     269        return m_impl.template add<T, T, Adapter>(value, value);
     270    }
     271
     272    template<typename T, typename U, typename V>
     273    inline void HashSet<T, U, V>::remove(iterator it)
     274    {
     275        if (it.m_impl == m_impl.end())
     276            return;
     277        it->~ValueType();
     278        m_impl.remove(it.m_impl);
     279    }
     280
     281    template<typename T, typename U, typename V>
     282    inline void HashSet<T, U, V>::remove(const ValueType& value)
     283    {
     284        remove(find(value));
     285    }
     286
     287    template<typename T, typename U, typename V>
     288    inline void HashSet<T, U, V>::clear()
     289    {
     290        derefAll();
    194291        m_impl.clear();
    195292    }
    196293
    197     template<typename Value, typename HashFunctions, typename Traits>
    198     void deleteAllValues(HashSet<Value, HashFunctions, Traits>& collection)
    199     {
    200         typedef HashSet<Value, HashFunctions, Traits> T;
    201         typename T::iterator end = collection.end();
    202         for (typename T::iterator it = collection.begin(); it != end; ++it)
    203             delete (*it);
    204     }
    205 
    206 } // namespace khtml
     294    template<typename ValueType, typename HashTableType>
     295    void deleteAllValues(HashTableType& collection)
     296    {
     297        typedef typename HashTableType::iterator iterator;
     298        iterator end = collection.end();
     299        for (iterator it = collection.begin(); it != end; ++it)
     300            delete *(ValueType*)&*it;
     301    }
     302
     303    template<typename T, typename U, typename V>
     304    inline void deleteAllValues(HashSet<T, U, V>& collection)
     305    {
     306        deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
     307    }
     308
     309} // namespace KXMLCore
    207310
    208311using KXMLCore::HashSet;
    209312
    210313#endif /* KXMLCORE_HASH_SET_H */
    211 
    212 
Note: See TracChangeset for help on using the changeset viewer.