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

    r13089 r13703  
    137137#endif
    138138
    139         ReferenceType operator*() const
     139        PointerType get() const
    140140        {
    141141            checkValidity();
    142             return *m_position;
    143         }
    144         PointerType operator->() const { return &**this; }
     142            return m_position;
     143        }
     144        ReferenceType operator*() const { return *get(); }
     145        PointerType operator->() const { return get(); }
    145146
    146147        const_iterator& operator++()
    … …  
    217218        // default copy, assignment and destructor are OK
    218219
    219         ReferenceType operator*() const { return const_cast<ReferenceType>(*m_iterator); }
    220         PointerType operator->() const { return &**this; }
     220        PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
     221        ReferenceType operator*() const { return *get(); }
     222        PointerType operator->() const { return get(); }
    221223
    222224        iterator& operator++() { ++m_iterator; return *this; }
    … …  
    263265        typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
    264266        typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
     267        typedef Traits ValueTraits;
    265268        typedef Key KeyType;
    266269        typedef Value ValueType;
    … …  
    281284        int size() const { return m_keyCount; }
    282285        int capacity() const { return m_tableSize; }
     286        bool isEmpty() const { return !m_keyCount; }
    283287
    284288        pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); }
    … …  
    465469
    466470    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    467     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key)
     471    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key)
    468472    {
    469473        if (!m_table)
    … …  
    477481
    478482    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    479     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key) const
     483    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key) const
    480484    {
    481485        if (!m_table)
    … …  
    489493
    490494    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    491     inline bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const KeyType& key) const
     495    bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const KeyType& key) const
    492496    {
    493497        if (!m_table)
    … …  
    498502
    499503    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    500     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
     504    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
    501505    {
    502506        invalidateIterators();
    … …  
    518522
    519523    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    520     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
    521     {
    522         if (!m_table)
    523             return;
    524 
    525         remove(find(key));
    526     }
    527 
    528     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    529524    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
    530525    {
    … …  
    535530    }
    536531
    537 
    538     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    539     inline Value *HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
     532    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     533    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
     534    {
     535        remove(find(key));
     536    }
     537
     538    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     539    Value *HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
    540540    {
    541541        // would use a template member function with explicit specializations here, but
    542542        // gcc doesn't appear to support that
    543543        if (Traits::emptyValueIsZero)
    544             return reinterpret_cast<ValueType *>(fastCalloc(size, sizeof(ValueType)));
    545         else {
    546             ValueType *result = reinterpret_cast<ValueType *>(fastMalloc(size * sizeof(ValueType)));
    547             for (int i = 0; i < size; i++) {
    548                 initializeBucket(result[i]);
    549             }
    550             return result;
    551         }
    552     }
    553 
    554     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    555     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size)
    556     {
    557         if (Traits::needsDestruction) {
    558             for (int i = 0; i < size; ++i) {
    559                 (&table[i])->~ValueType();
    560             }
    561         }
    562 
     544            return static_cast<ValueType *>(fastCalloc(size, sizeof(ValueType)));
     545        ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
     546        for (int i = 0; i < size; i++)
     547            initializeBucket(result[i]);
     548        return result;
     549    }
     550
     551    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     552    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size)
     553    {
     554        if (Traits::needsDestruction)
     555            for (int i = 0; i < size; ++i)
     556                table[i].~ValueType();
    563557        fastFree(table);
    564558    }
    565559
    566560    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    567     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
     561    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
    568562    {
    569563        int newSize;
    … …  
    595589        m_table = allocateTable(newTableSize);
    596590
    597         for (int i = 0; i != oldTableSize; ++i) {
     591        for (int i = 0; i != oldTableSize; ++i)
    598592            if (!isEmptyOrDeletedBucket(oldTable[i]))
    599593                reinsert(oldTable[i]);
    600         }
    601594
    602595        m_deletedCount = 0;
    … …  
    608601
    609602    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    610     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
     603    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
    611604    {
    612605        invalidateIterators();
    … …  
    781774#endif // CHECK_HASHTABLE_ITERATORS
    782775
     776    // iterator adapters
     777
     778    template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {
     779        HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
     780
     781        const ValueType* get() const { return (const ValueType*)m_impl.get(); }
     782        const ValueType& operator*() const { return *get(); }
     783        const ValueType* operator->() const { return get(); }
     784
     785        HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
     786        // postfix ++ intentionally omitted
     787
     788        typename HashTableType::const_iterator m_impl;
     789    };
     790
     791    template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {
     792        HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
     793
     794        ValueType* get() const { return (ValueType*)m_impl.get(); }
     795        ValueType& operator*() const { return *get(); }
     796        ValueType* operator->() const { return get(); }
     797
     798        HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
     799        // postfix ++ intentionally omitted
     800
     801        operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
     802            typename HashTableType::const_iterator i = m_impl;
     803            return i;
     804        }
     805
     806        typename HashTableType::iterator m_impl;
     807    };
     808
     809    template<typename T, typename U>
     810    inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
     811    {
     812        return a.m_impl == b.m_impl;
     813    }
     814
     815    template<typename T, typename U>
     816    inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
     817    {
     818        return a.m_impl != b.m_impl;
     819    }
     820
     821    template<typename T, typename U>
     822    inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
     823    {
     824        return a.m_impl == b.m_impl;
     825    }
     826
     827    template<typename T, typename U>
     828    inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
     829    {
     830        return a.m_impl != b.m_impl;
     831    }
     832
     833    // reference count manager
     834   
     835    template<typename ValueTraits, typename ValueStorageTraits> struct NeedsRef {
     836        static const bool value = ValueTraits::needsRef && !ValueStorageTraits::needsRef;
     837    };
     838
     839    template<bool needsRef, typename ValueTraits> struct RefCounterBase;
     840
     841    template<typename ValueTraits>
     842    struct RefCounterBase<false, ValueTraits> {
     843        typedef typename ValueTraits::TraitType ValueType;
     844        static void ref(const ValueType&) { }
     845        static void deref(const ValueType&) { }
     846    };
     847
     848    template<typename ValueTraits>
     849    struct RefCounterBase<true, ValueTraits> {
     850        typedef typename ValueTraits::TraitType ValueType;
     851        static void ref(const ValueType& v) { ValueTraits::ref(*(const ValueType*)&v); }
     852        static void deref(const ValueType& v) { ValueTraits::deref(*(const ValueType*)&v); }
     853    };
     854
     855    template<typename ValueTraits, typename ValueStorageTraits> struct RefCounter {
     856        typedef typename ValueTraits::TraitType ValueType;
     857        typedef typename ValueStorageTraits::TraitType ValueStorageType;
     858        static const bool needsRef = NeedsRef<ValueTraits, ValueStorageTraits>::value;
     859        typedef RefCounterBase<needsRef, ValueTraits> Base;
     860        static void ref(const ValueStorageType& v) { Base::ref(*(const ValueType*)&v); }
     861        static void deref(const ValueStorageType& v) { Base::deref(*(const ValueType*)&v); }
     862    };
     863
     864    template<typename FirstTraits, typename SecondTraits, typename ValueStorageTraits>
     865    struct RefCounter<PairBaseHashTraits<FirstTraits, SecondTraits>, ValueStorageTraits> {
     866        typedef typename FirstTraits::TraitType FirstType;
     867        typedef typename SecondTraits::TraitType SecondType;
     868        typedef typename ValueStorageTraits::FirstTraits FirstStorageTraits;
     869        typedef typename ValueStorageTraits::SecondTraits SecondStorageTraits;
     870        typedef typename ValueStorageTraits::TraitType ValueStorageType;
     871        static const bool firstNeedsRef = NeedsRef<FirstTraits, FirstStorageTraits>::value;
     872        static const bool secondNeedsRef = NeedsRef<SecondTraits, SecondStorageTraits>::value;
     873        typedef RefCounterBase<firstNeedsRef, FirstTraits> FirstBase;
     874        typedef RefCounterBase<secondNeedsRef, SecondTraits> SecondBase;
     875        static void ref(const ValueStorageType& v) {
     876            FirstBase::ref(*(const FirstType*)&v.first);
     877            SecondBase::ref(*(const SecondType*)&v.second);
     878        }
     879        static void deref(const ValueStorageType& v) {
     880            FirstBase::deref(*(const FirstType*)&v.first);
     881            SecondBase::deref(*(const SecondType*)&v.second);
     882        }
     883    };
     884
     885    template<bool needsRef, typename HashTableType, typename ValueTraits> struct HashTableRefCounterBase;
     886
     887    template<typename HashTableType, typename ValueTraits>
     888    struct HashTableRefCounterBase<false, HashTableType, ValueTraits>
     889    {
     890        static void refAll(HashTableType&) { }
     891        static void derefAll(HashTableType&) { }
     892    };
     893
     894    template<typename HashTableType, typename ValueTraits>
     895    struct HashTableRefCounterBase<true, HashTableType, ValueTraits>
     896    {
     897        typedef typename HashTableType::iterator iterator;
     898        typedef RefCounter<ValueTraits, typename HashTableType::ValueTraits> ValueRefCounter;
     899        static void refAll(HashTableType&);
     900        static void derefAll(HashTableType&);
     901    };
     902
     903    template<typename HashTableType, typename ValueTraits>
     904    void HashTableRefCounterBase<true, HashTableType, ValueTraits>::refAll(HashTableType& table)
     905    {
     906        iterator end = table.end();
     907        for (iterator it = table.begin(); it != end; ++it)
     908            ValueRefCounter::ref(*it);
     909    }
     910
     911    template<typename HashTableType, typename ValueTraits>
     912    void HashTableRefCounterBase<true, HashTableType, ValueTraits>::derefAll(HashTableType& table)
     913    {
     914        iterator end = table.end();
     915        for (iterator it = table.begin(); it != end; ++it)
     916            ValueRefCounter::deref(*it);
     917    }
     918
     919    template<typename HashTableType, typename ValueTraits> struct HashTableRefCounter {
     920        static const bool needsRef = NeedsRef<ValueTraits, typename HashTableType::ValueTraits>::value;
     921        typedef HashTableRefCounterBase<needsRef, HashTableType, ValueTraits> Base;
     922        static void refAll(HashTableType& table) { Base::refAll(table); }
     923        static void derefAll(HashTableType& table) { Base::derefAll(table); }
     924    };
     925
    783926} // namespace KXMLCore
    784927
Note: See TracChangeset for help on using the changeset viewer.