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/HashTraits.h

    r12301 r13703  
    2424#define KXMLCORE_HASH_TRAITS_H
    2525
    26 #include "RefPtr.h"
     26#include "HashFunctions.h"
    2727#include <utility>
    2828
    … …  
    3030
    3131    using std::pair;
     32    using std::make_pair;
    3233
    33     template <typename T> struct IsInteger           { static const bool value = false; };
    34     template <> struct IsInteger<bool>               { static const bool value = true; };
    35     template <> struct IsInteger<char>               { static const bool value = true; };
    36     template <> struct IsInteger<signed char>        { static const bool value = true; };
    37     template <> struct IsInteger<unsigned char>      { static const bool value = true; };
    38     template <> struct IsInteger<short>              { static const bool value = true; };
    39     template <> struct IsInteger<unsigned short>     { static const bool value = true; };
    40     template <> struct IsInteger<int>                { static const bool value = true; };
    41     template <> struct IsInteger<unsigned int>       { static const bool value = true; };
    42     template <> struct IsInteger<long>               { static const bool value = true; };
    43     template <> struct IsInteger<unsigned long>      { static const bool value = true; };
    44     template <> struct IsInteger<long long>          { static const bool value = true; };
    45     template <> struct IsInteger<unsigned long long> { static const bool value = true; };
     34    template<typename T> struct IsInteger           { static const bool value = false; };
     35    template<> struct IsInteger<bool>               { static const bool value = true; };
     36    template<> struct IsInteger<char>               { static const bool value = true; };
     37    template<> struct IsInteger<signed char>        { static const bool value = true; };
     38    template<> struct IsInteger<unsigned char>      { static const bool value = true; };
     39    template<> struct IsInteger<short>              { static const bool value = true; };
     40    template<> struct IsInteger<unsigned short>     { static const bool value = true; };
     41    template<> struct IsInteger<int>                { static const bool value = true; };
     42    template<> struct IsInteger<unsigned int>       { static const bool value = true; };
     43    template<> struct IsInteger<long>               { static const bool value = true; };
     44    template<> struct IsInteger<unsigned long>      { static const bool value = true; };
     45    template<> struct IsInteger<long long>          { static const bool value = true; };
     46    template<> struct IsInteger<unsigned long long> { static const bool value = true; };
     47
     48    template<typename T> struct HashTraits;
    4649
    4750    template<bool isInteger, typename T> struct GenericHashTraitsBase;
    4851    template<typename T> struct GenericHashTraitsBase<true, T> {
    4952        typedef T TraitType;
     53        typedef HashTraits<typename IntTypes<sizeof(T)>::SignedType> StorageTraits;
    5054        static const bool emptyValueIsZero = true;
    5155        static const bool needsDestruction = false;
    52         static TraitType emptyValue() { return 0; }
    5356    };
    5457    template<typename T> struct GenericHashTraitsBase<false, T> {
    5558        typedef T TraitType;
     59        typedef HashTraits<T> StorageTraits;
    5660        static const bool emptyValueIsZero = false;
    5761        static const bool needsDestruction = true;
    58         static TraitType emptyValue() { return TraitType(); }
    5962    };
    6063
    61     template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> { };
     64    template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
     65        static T emptyValue() { return T(); }
     66        static const bool needsRef = false;
     67    };
    6268
    6369    template<typename T> struct HashTraits : GenericHashTraits<T> { };
    6470
    65     // may not be appropriate for all uses since it disallows 0 and -1 as keys
     71    // signed integer traits may not be appropriate for all uses since they disallow 0 and -1 as keys
     72    template<> struct HashTraits<signed char> : GenericHashTraits<int> {
     73        static signed char deletedValue() { return -1; }
     74    };
     75    template<> struct HashTraits<short> : GenericHashTraits<int> {
     76        static short deletedValue() { return -1; }
     77    };
    6678    template<> struct HashTraits<int> : GenericHashTraits<int> {
    67         static TraitType deletedValue() { return -1; }
     79        static int deletedValue() { return -1; }
     80    };
     81    template<> struct HashTraits<long> : GenericHashTraits<long> {
     82        static long deletedValue() { return -1; }
     83    };
     84    template<> struct HashTraits<long long> : GenericHashTraits<long long> {
     85        static long deletedValue() { return -1; }
    6886    };
    6987
    7088    template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
    71         typedef P* TraitType;
     89        typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
    7290        static const bool emptyValueIsZero = true;
    7391        static const bool needsDestruction = false;
    74         static TraitType emptyValue() { return 0; }
    75         static TraitType deletedValue() { return reinterpret_cast<P*>(-1); }
     92        static P* deletedValue() { return reinterpret_cast<P*>(-1); }
    7693    };
    7794
    7895    template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > {
     96        typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
    7997        static const bool emptyValueIsZero = true;
     98        static const bool needsRef = true;
     99        static void ref(const RefPtr<P>& p) { if (p) p->ref(); }
     100        static void deref(const RefPtr<P>& p) { if (p) p->deref(); }
    80101    };
    81102
    82     template<typename T, typename Traits> class DeletedValueAssigner;
     103    // template to set deleted values
     104
     105    template<typename Traits> struct DeletedValueAssigner {
     106        static void assignDeletedValue(typename Traits::TraitType& location) { location = Traits::deletedValue(); }
     107    };
    83108
    84109    template<typename T, typename Traits> inline void assignDeleted(T& location)
    85110    {
    86         DeletedValueAssigner<T, Traits>::assignDeletedValue(location);
     111        DeletedValueAssigner<Traits>::assignDeletedValue(location);
    87112    }
    88113
    89     template<typename FirstTraits, typename SecondTraits>
    90     struct PairHashTraits : GenericHashTraits<pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> > {
    91     private:
    92         typedef typename FirstTraits::TraitType FirstType;
    93         typedef typename SecondTraits::TraitType SecondType;
    94     public:
    95         typedef pair<FirstType, SecondType> TraitType;
     114    // special traits for pairs, helpful for their use in HashMap implementation
     115
     116    template<typename FirstTraits, typename SecondTraits> struct PairHashTraits;
     117
     118    template<typename FirstTraitsArg, typename SecondTraitsArg>
     119    struct PairBaseHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
     120        typedef FirstTraitsArg FirstTraits;
     121        typedef SecondTraitsArg SecondTraits;
     122        typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
     123
     124        typedef PairHashTraits<typename FirstTraits::StorageTraits, typename SecondTraits::StorageTraits> StorageTraits;
    96125
    97126        static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
    98         static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
    99127
    100128        static TraitType emptyValue()
    101129        {
    102             return TraitType(FirstTraits::emptyValue(), SecondTraits::emptyValue());
     130            return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue());
    103131        }
     132    };
     133
     134    template<typename FirstTraits, typename SecondTraits>
     135    struct PairHashTraits : PairBaseHashTraits<FirstTraits, SecondTraits> {
     136        typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
     137
     138        static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
    104139
    105140        static TraitType deletedValue()
    … …  
    110145        static void assignDeletedValue(TraitType& location)
    111146        {
    112             assignDeleted<FirstType, FirstTraits>(location.first);
     147            assignDeleted<typename FirstTraits::TraitType, FirstTraits>(location.first);
    113148            location.second = SecondTraits::emptyValue();
    114149        }
    … …  
    118153    struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
    119154
    120     template<typename T, typename Traits> struct DeletedValueAssigner {
    121         static void assignDeletedValue(T& location) { location = Traits::deletedValue(); }
    122     };
    123 
    124155    template<typename FirstTraits, typename SecondTraits>
    125     struct DeletedValueAssigner<pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>, PairHashTraits<FirstTraits, SecondTraits> >
     156    struct DeletedValueAssigner<PairHashTraits<FirstTraits, SecondTraits> >
    126157    {
    127158        static void assignDeletedValue(pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>& location)
    … …  
    132163
    133164    template<typename First, typename Second>
    134     struct DeletedValueAssigner<pair<First, Second>, HashTraits<pair<First, Second> > >
     165    struct DeletedValueAssigner<HashTraits<pair<First, Second> > >
    135166    {
    136167        static void assignDeletedValue(pair<First, Second>& location)
    … …  
    140171    };
    141172
     173    // hassh functions and traits that are equivalent (for code sharing)
     174
     175    template<typename HashArg, typename TraitsArg> struct HashKeyStorageTraits {
     176        typedef HashArg Hash;
     177        typedef TraitsArg Traits;
     178    };
     179    template<typename P> struct HashKeyStorageTraits<PtrHash<P*>, HashTraits<P*> > {
     180        typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
     181        typedef IntHash<IntType> Hash;
     182        typedef HashTraits<IntType> Traits;
     183    };
     184    template<typename P> struct HashKeyStorageTraits<PtrHash<RefPtr<P> >, HashTraits<RefPtr<P> > > {
     185        typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
     186        typedef IntHash<IntType> Hash;
     187        typedef HashTraits<IntType> Traits;
     188    };
    142189
    143190} // namespace KXMLCore
Note: See TracChangeset for help on using the changeset viewer.