JavaScriptCore:
authordarin <darin@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 5 Apr 2006 21:19:57 +0000 (21:19 +0000)
committerdarin <darin@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 5 Apr 2006 21:19:57 +0000 (21:19 +0000)
        Reviewed by Maciej.

        - JavaScriptCore part of fix for http://bugzilla.opendarwin.org/show_bug.cgi?id=8049
          StringImpl hash traits deleted value creates an init routine for WebCore
          <rdar://problem/4442248> REGRESSION: WebCore has init routines (8049)

        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.

        - fix for http://bugzilla.opendarwin.org/show_bug.cgi?id=8049
          StringImpl hash traits deleted value creates an init routine for WebCore
          <rdar://problem/4442248> REGRESSION: WebCore has init routines (8049)

        * 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.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@13703 268f45cc-cd09-0410-ab3c-d52691b4dbfc

37 files changed:
JavaScriptCore/ChangeLog
JavaScriptCore/JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj
JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
JavaScriptCore/kxmlcore/HashFunctions.h
JavaScriptCore/kxmlcore/HashMap.h
JavaScriptCore/kxmlcore/HashMapPtrSpec.h [deleted file]
JavaScriptCore/kxmlcore/HashSet.h
JavaScriptCore/kxmlcore/HashTable.h
JavaScriptCore/kxmlcore/HashTraits.h
WebCore/ChangeLog
WebCore/ForwardingHeaders/kxmlcore/HashTraits.h [new file with mode: 0644]
WebCore/WebCore.xcodeproj/project.pbxproj
WebCore/bridge/mac/FrameMac.h
WebCore/bridge/mac/FrameMac.mm
WebCore/dom/Document.h
WebCore/dom/Node.cpp
WebCore/dom/StyledElement.cpp
WebCore/dom/xml_tokenizer.h
WebCore/khtml/xsl/XSLTProcessor.cpp
WebCore/khtml/xsl/XSLTProcessor.h
WebCore/kwq/AccessibilityObjectCache.h
WebCore/kwq/JavaAppletWidget.h
WebCore/loader/Cache.cpp
WebCore/page/FramePrivate.h
WebCore/page/Page.cpp
WebCore/platform/AtomicString.cpp
WebCore/platform/AtomicString.h
WebCore/platform/CharsetNames.cpp
WebCore/platform/PlatformString.h
WebCore/platform/StringHash.h [new file with mode: 0644]
WebCore/platform/StringImpl.cpp
WebCore/platform/StringImpl.h
WebCore/platform/TransferJob.h
WebCore/rendering/render_applet.h
WebKitTools/ChangeLog
WebKitTools/Scripts/check-for-global-initializers
WebKitTools/Scripts/run-webkit-tests

index cdc5c4c04c6f3aab7b2bf24997c0dd3092b3157c..ed8416d0517925796374c61ab6c3659c3d3fe6e2 100644 (file)
@@ -1,3 +1,68 @@
+2006-04-05  Darin Adler  <darin@apple.com>
+
+        Reviewed by Maciej.
+
+        - JavaScriptCore part of fix for http://bugzilla.opendarwin.org/show_bug.cgi?id=8049
+          StringImpl hash traits deleted value creates an init routine for WebCore
+          <rdar://problem/4442248> REGRESSION: WebCore has init routines (8049)
+
+        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.
+
 2006-04-04  Timothy Hatcher  <timothy@apple.com>
 
         Reviewed by Darin.
index 72edba3476a8f7bff1c902db92a3378ed949c67c..b1739f5c934b96e72531974b8da74a005c4b760b 100644 (file)
                                RelativePath="..\..\kxmlcore\HashMap.h"
                                >
                        </File>
-                       <File
-                               RelativePath="..\..\kxmlcore\HashMapPtrSpec.h"
-                               >
-                       </File>
                        <File
                                RelativePath="..\..\kxmlcore\HashSet.h"
                                >
index b0214f08545f8b44bc56b1c6f522c4cf326d3d59..1dc9abe178892133ba01421b7f18b4594e44a634 100644 (file)
                        buildPhases = (
                                65FB3F6509D11E9100F49DEB /* Generate Derived Sources */,
                        );
-                       buildSettings = {
-                               PRODUCT_NAME = "Generate Derived Sources";
-                       };
-                       dependencies = (
-                       );
                        name = "Derived Sources";
-                       productName = "Generate Derived Sources";
+                       productName = "Derived Sources";
                };
                932F5BE30822A1C700736975 /* All */ = {
                        isa = PBXAggregateTarget;
@@ -49,7 +44,6 @@
                6541BD7308E80A17002CBEE7 /* TCSpinLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 6541BD6F08E80A17002CBEE7 /* TCSpinLock.h */; };
                6541BD7408E80A17002CBEE7 /* TCSystemAlloc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 6541BD7008E80A17002CBEE7 /* TCSystemAlloc.cpp */; };
                6541BD7508E80A17002CBEE7 /* TCSystemAlloc.h in Headers */ = {isa = PBXBuildFile; fileRef = 6541BD7108E80A17002CBEE7 /* TCSystemAlloc.h */; };
-               6557E8F808EA5D4D0049CDFC /* HashMapPtrSpec.h in Headers */ = {isa = PBXBuildFile; fileRef = 6557E8F708EA5D4D0049CDFC /* HashMapPtrSpec.h */; settings = {ATTRIBUTES = (Private, ); }; };
                65621E6D089E859700760F35 /* property_slot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 65621E6B089E859700760F35 /* property_slot.cpp */; };
                65621E6E089E859700760F35 /* property_slot.h in Headers */ = {isa = PBXBuildFile; fileRef = 65621E6C089E859700760F35 /* property_slot.h */; settings = {ATTRIBUTES = (Private, ); }; };
                657EEBC0094E445E008C9C7B /* HashCountedSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 657EEBBF094E445E008C9C7B /* HashCountedSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
                6541BD6F08E80A17002CBEE7 /* TCSpinLock.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = TCSpinLock.h; sourceTree = "<group>"; tabWidth = 8; };
                6541BD7008E80A17002CBEE7 /* TCSystemAlloc.cpp */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TCSystemAlloc.cpp; sourceTree = "<group>"; tabWidth = 8; };
                6541BD7108E80A17002CBEE7 /* TCSystemAlloc.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = TCSystemAlloc.h; sourceTree = "<group>"; tabWidth = 8; };
-               6557E8F708EA5D4D0049CDFC /* HashMapPtrSpec.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = HashMapPtrSpec.h; sourceTree = "<group>"; tabWidth = 8; };
                6560A4CF04B3B3E7008AE952 /* CoreFoundation.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = CoreFoundation.framework; path = /System/Library/Frameworks/CoreFoundation.framework; sourceTree = "<absolute>"; };
                6560A63D04B3B69F008AE952 /* CoreServices.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = CoreServices.framework; path = /System/Library/Frameworks/CoreServices.framework; sourceTree = "<absolute>"; };
                65621E6B089E859700760F35 /* property_slot.cpp */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.cpp.cpp; path = property_slot.cpp; sourceTree = "<group>"; tabWidth = 8; };
                65162EF108E6A21C007556CD /* kxmlcore */ = {
                        isa = PBXGroup;
                        children = (
-                               65D6D87E09B5A32E0002E4D7 /* Platform.h */,
                                93AA4F770957251F0084B3A7 /* AlwaysInline.h */,
-                               65E217B708E7EECC0023E5F6 /* Assertions.h */,
                                65E217B808E7EECC0023E5F6 /* Assertions.cpp */,
+                               65E217B708E7EECC0023E5F6 /* Assertions.h */,
                                65E217B908E7EECC0023E5F6 /* FastMalloc.cpp */,
                                65E217BA08E7EECC0023E5F6 /* FastMalloc.h */,
                                65D7D19B08F10B5B0015ABD8 /* FastMallocInternal.h */,
                                657EEBBF094E445E008C9C7B /* HashCountedSet.h */,
                                65DFC92A08EA173A00F7300B /* HashFunctions.h */,
                                65DFC92B08EA173A00F7300B /* HashMap.h */,
-                               6557E8F708EA5D4D0049CDFC /* HashMapPtrSpec.h */,
                                65DFC92C08EA173A00F7300B /* HashSet.h */,
                                65DFC92D08EA173A00F7300B /* HashTable.cpp */,
                                65DFC92E08EA173A00F7300B /* HashTable.h */,
                                9303F5A409911A5800AD71B8 /* OwnArrayPtr.h */,
                                9303F567099118FA00AD71B8 /* OwnPtr.h */,
                                6580F795094070560082C219 /* PassRefPtr.h */,
+                               65D6D87E09B5A32E0002E4D7 /* Platform.h */,
                                65C647B3093EF8D60022C380 /* RefPtr.h */,
                                6541BD6E08E80A17002CBEE7 /* TCPageMap.h */,
                                6541BD6F08E80A17002CBEE7 /* TCSpinLock.h */,
                                65DFC93208EA173A00F7300B /* HashSet.h in Headers */,
                                65DFC93408EA173A00F7300B /* HashTable.h in Headers */,
                                65DFC93508EA173A00F7300B /* HashTraits.h in Headers */,
-                               6557E8F808EA5D4D0049CDFC /* HashMapPtrSpec.h in Headers */,
                                65D7D19C08F10B5B0015ABD8 /* FastMallocInternal.h in Headers */,
                                65EA4C9C092AF9E20093D800 /* JSLock.h in Headers */,
                                65C647B4093EF8D60022C380 /* RefPtr.h in Headers */,
                65FB3F7809D11EBD00F49DEB /* Debug */ = {
                        isa = XCBuildConfiguration;
                        buildSettings = {
-                               COPY_PHASE_STRIP = NO;
-                               GCC_DYNAMIC_NO_PIC = NO;
-                               GCC_GENERATE_DEBUGGING_SYMBOLS = YES;
-                               GCC_OPTIMIZATION_LEVEL = 0;
                                PRODUCT_NAME = "Generate Derived Sources";
                        };
                        name = Debug;
                65FB3F7909D11EBD00F49DEB /* Release */ = {
                        isa = XCBuildConfiguration;
                        buildSettings = {
-                               COPY_PHASE_STRIP = YES;
-                               GCC_ENABLE_FIX_AND_CONTINUE = NO;
-                               GCC_GENERATE_DEBUGGING_SYMBOLS = NO;
                                PRODUCT_NAME = "Generate Derived Sources";
-                               ZERO_LINK = NO;
                        };
                        name = Release;
                };
index 17496eaa76916d042c069424dc4db47264633b28..26f030e87d8df0afa1c863d81f793157a519addd 100644 (file)
@@ -1,7 +1,7 @@
 // -*- mode: c++; c-basic-offset: 4 -*-
 /*
  * This file is part of the KDE libraries
- * Copyright (C) 2005 Apple Computer, Inc.
+ * Copyright (C) 2005, 2006 Apple Computer, Inc.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
 #ifndef KXMLCORE_HASH_FUNCTIONS_H
 #define KXMLCORE_HASH_FUNCTIONS_H
 
-#include <stdint.h>
-
 #include "RefPtr.h"
+#include <stdint.h>
 
 namespace KXMLCore {
 
-    template<typename T> class DefaultHash;
+    template<size_t size> struct IntTypes;
+    template<> struct IntTypes<1> { typedef int8_t SignedType; typedef uint8_t UnsignedType; };
+    template<> struct IntTypes<2> { typedef int16_t SignedType; typedef uint16_t UnsignedType; };
+    template<> struct IntTypes<4> { typedef int32_t SignedType; typedef uint32_t UnsignedType; };
+    template<> struct IntTypes<8> { typedef int64_t SignedType; typedef uint64_t UnsignedType; };
 
-    template<int size> unsigned pointerHash(void *pointer);
+    // integer hash function
 
-    // Thomas Wang's 32 bit mix
-    // http://www.cris.com/~Ttwang/tech/inthash.htm
-    template<> inline unsigned pointerHash<4>(void *pointer) 
+    // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
+    inline unsigned intHash(uint32_t key) 
     {
-        uint32_t key = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(pointer));
         key += ~(key << 15);
         key ^= (key >> 10);
         key += (key << 3);
@@ -47,11 +48,9 @@ namespace KXMLCore {
         return key;
     }
     
-    // Thomas Wang's 64 bit mix
-    // http://www.cris.com/~Ttwang/tech/inthash.htm
-    template<> inline unsigned pointerHash<8>(void *pointer)
+    // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
+    inline unsigned intHash(uint64_t key)
     {
-        uint64_t key = reinterpret_cast<uint64_t>(pointer);
         key += ~(key << 32);
         key ^= (key >> 22);
         key += ~(key << 13);
@@ -63,30 +62,44 @@ namespace KXMLCore {
         return key;
     }
 
-    // pointer identity hash - default for pointer types that don't
-    // explicitly specialize otherwise; also should work for integer
-    // types
-    template<typename T> struct PtrHash {
-        static unsigned hash(T key) { return pointerHash<sizeof(void *)>((void *)key); }
+    template<typename T> struct IntHash {
+        static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); }
         static bool equal(T a, T b) { return a == b; }
     };
 
+    // pointer identity hash function
+
+    template<typename T> struct PtrHash {
+        static unsigned hash(T key) { return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key)); }
+        static bool equal(T a, T b) { return a == b; }
+    };
     template<typename P> struct PtrHash<RefPtr<P> > {
-        static unsigned hash(const RefPtr<P>& key) { return  pointerHash<sizeof(void *)>((void *)key.get()); }
+        static unsigned hash(const RefPtr<P>& key) { return PtrHash<P*>::hash(key.get()); }
         static bool equal(const RefPtr<P>& a, const RefPtr<P>& b) { return a == b; }
     };
 
-    template<typename P> struct DefaultHash<P *> {
-        typedef PtrHash<P *> Hash;
-    };
+    // default hash function for each type
+
+    template<typename T> struct DefaultHash;
+
+    // make IntHash the default hash function for many integer types
+
+    template<> struct DefaultHash<int> { typedef IntHash<unsigned> Hash; };
+    template<> struct DefaultHash<unsigned> { typedef IntHash<unsigned> Hash; };
+    template<> struct DefaultHash<long> { typedef IntHash<unsigned long> Hash; };
+    template<> struct DefaultHash<unsigned long> { typedef IntHash<unsigned long> Hash; };
+    template<> struct DefaultHash<long long> { typedef IntHash<unsigned long long> Hash; };
+    template<> struct DefaultHash<unsigned long long> { typedef IntHash<unsigned long long> Hash; };
+
+    // make PtrHash the default hash function for pointer types that don't specialize
+
+    template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; };
+    template<typename P> struct DefaultHash<RefPtr<P> > { typedef PtrHash<RefPtr<P> > Hash; };
 
-    template<> struct DefaultHash<int> {
-        typedef PtrHash<int> Hash;
-    };
-    
 } // namespace KXMLCore
 
 using KXMLCore::DefaultHash;
+using KXMLCore::IntHash;
 using KXMLCore::PtrHash;
 
 #endif // KXLMCORE_HASH_FUNCTIONS_H
index 46263575dea04f5d6ae97dd09595f736add391d1..251860997846e577f403aa54bc6c13d5fb78eafa 100644 (file)
 #define KXMLCORE_HASH_MAP_H
 
 #include "HashTable.h"
-#include "HashTraits.h"
-#include "HashFunctions.h"
 
 namespace KXMLCore {
 
-template<typename Key, typename Mapped>
-class PairFirstExtractor
-{
-    typedef pair<Key, Mapped> ValueType;
-        
-public:
-    static const Key& extract(const ValueType& value) 
+    template<typename PairType> struct PairFirstExtractor;
+
+    template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
+        typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> > class HashMap {
+    private:
+        typedef KeyTraitsArg KeyTraits;
+        typedef MappedTraitsArg MappedTraits;
+        typedef PairBaseHashTraits<KeyTraits, MappedTraits> ValueTraits;
+
+    public:
+        typedef typename KeyTraits::TraitType KeyType;
+        typedef typename MappedTraits::TraitType MappedType;
+        typedef typename ValueTraits::TraitType ValueType;
+
+    private:
+        typedef HashArg HashFunctions;
+
+        typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Hash StorageHashFunctions;
+
+        typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Traits KeyStorageTraits;
+        typedef typename MappedTraits::StorageTraits MappedStorageTraits;
+        typedef PairHashTraits<KeyStorageTraits, MappedStorageTraits> ValueStorageTraits;
+
+        typedef typename KeyStorageTraits::TraitType KeyStorageType;
+        typedef typename MappedStorageTraits::TraitType MappedStorageType;
+        typedef typename ValueStorageTraits::TraitType ValueStorageType;
+
+        typedef HashTable<KeyStorageType, ValueStorageType, PairFirstExtractor<ValueStorageType>,
+            StorageHashFunctions, ValueStorageTraits, KeyStorageTraits> HashTableType;
+
+    public:
+        typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
+        typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
+
+        HashMap();
+        HashMap(const HashMap&);
+        HashMap& operator=(const HashMap&);
+        ~HashMap();
+
+        int size() const;
+        int capacity() const;
+        bool isEmpty() const;
+
+        // iterators iterate over pairs of keys and values
+        iterator begin();
+        iterator end();
+        const_iterator begin() const;
+        const_iterator end() const;
+
+        iterator find(const KeyType&);
+        const_iterator find(const KeyType&) const;
+        bool contains(const KeyType&) const;
+        MappedType get(const KeyType&) const;
+
+        // replaces value but not key if key is already present
+        // return value is a pair of the iterator to the key location, 
+        // and a boolean that's true if a new value was actually added
+        pair<iterator, bool> set(const KeyType&, const MappedType&); 
+
+        // does nothing if key is already present
+        // return value is a pair of the iterator to the key location, 
+        // and a boolean that's true if a new value was actually added
+        pair<iterator, bool> add(const KeyType&, const MappedType&); 
+
+        void remove(const KeyType&);
+        void remove(iterator it);
+        void clear();
+
+    private:
+        pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
+        void refAll();
+        void derefAll();
+
+        HashTableType m_impl;
+    };
+
+    template<typename PairType> struct PairFirstExtractor {
+        static const typename PairType::first_type& extract(const PairType& p) { return p.first; }
+    };
+
+    template<bool canReplaceDeletedKey, typename ValueType, typename ValueStorageTraits, typename HashFunctions>
+    struct HashMapTranslator;
+
+    template<typename ValueType, typename ValueStorageTraits, typename HashFunctions>
+    struct HashMapTranslator<true, ValueType, ValueStorageTraits, HashFunctions> {
+        typedef typename ValueType::first_type KeyType;
+        typedef typename ValueType::second_type MappedType;
+        typedef typename ValueStorageTraits::TraitType ValueStorageType;
+        typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;
+        typedef typename KeyStorageTraits::TraitType KeyStorageType;
+
+        static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
+        static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
+        static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped, unsigned)
+        {
+            *(KeyType*)&location.first = key;
+            *(MappedType*)&location.second = mapped;
+        }
+    };
+
+    template<typename ValueType, typename ValueStorageTraits, typename HashFunctions>
+    struct HashMapTranslator<false, ValueType, ValueStorageTraits, HashFunctions> {
+        typedef typename ValueType::first_type KeyType;
+        typedef typename ValueType::second_type MappedType;
+        typedef typename ValueStorageTraits::TraitType ValueStorageType;
+        typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;
+        typedef typename KeyStorageTraits::TraitType KeyStorageType;
+
+        static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
+        static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
+        static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped, unsigned)
+        {
+            if (location.first == KeyStorageTraits::deletedValue())
+                location.first = KeyStorageTraits::emptyValue();
+            *(KeyType*)&location.first = key;
+            *(MappedType*)&location.second = mapped;
+        }
+    };
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline void HashMap<T, U, V, W, X>::refAll()
+    {
+        HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline void HashMap<T, U, V, W, X>::derefAll()
+    {
+        HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline HashMap<T, U, V, W, X>::HashMap()
+    {
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline HashMap<T, U, V, W, X>::HashMap(const HashMap& other)
+        : m_impl(other.m_impl)
+    {
+        refAll();
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline HashMap<T, U, V, W, X>& HashMap<T, U, V, W, X>::operator=(const HashMap& other)
+    {
+        HashMap tmp(other);
+        m_impl.swap(tmp.m_impl); 
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline HashMap<T, U, V, W, X>::~HashMap()
+    {
+        derefAll();
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline int HashMap<T, U, V, W, X>::size() const
+    {
+        return m_impl.size(); 
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline int HashMap<T, U, V, W, X>::capacity() const
     { 
-        return value.first;
-    }
-};
-
-template<typename Key, typename Mapped, typename HashFunctions>
-class HashMapTranslator 
-{
-    typedef pair<Key, Mapped> ValueType;
-        
-public:
-    static unsigned hash(const Key& key)
-    {
-        return HashFunctions::hash(key);
-    }
-    
-    static bool equal(const Key& a, const Key& b)
-    {
-        return HashFunctions::equal(a, b);
-    }
-    
-    static void translate(ValueType& location, const Key& key, const Mapped& mapped, unsigned)
-    {
-        ValueType tmp(key, mapped);
-        swap(tmp, location);
-    }
-};
-
-
-template<typename Key, typename Mapped, typename HashFunctions = typename DefaultHash<Key>::Hash, typename KeyTraits = HashTraits<Key>, typename MappedTraits = HashTraits<Mapped> >
-class HashMap {
- public:
-    typedef Key KeyType;
-    typedef Mapped MappedType;
-    typedef pair<Key, Mapped> ValueType;
-    typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits;
- private:
-    typedef HashTable<KeyType, ValueType, PairFirstExtractor<KeyType, MappedType>, HashFunctions, ValueTraits, KeyTraits> ImplType;
-    typedef HashMapTranslator<Key, Mapped, HashFunctions> TranslatorType; 
- public:
-    typedef typename ImplType::iterator iterator;
-    typedef typename ImplType::const_iterator const_iterator;
-
-    HashMap() {}
-
-    int size() const;
-    int capacity() const;
-    bool isEmpty() const;
-
-    // iterators iterate over pairs of keys and values
-    iterator begin();
-    iterator end();
-    const_iterator begin() const;
-    const_iterator end() const;
-
-    iterator find(const KeyType& key);
-    const_iterator find(const KeyType& key) const;
-    bool contains(const KeyType& key) const;
-    MappedType get(const KeyType &key) const;
-
-    // replaces value but not key if key is already present
-    // return value is a pair of the iterator to the key location, 
-    // and a boolean that's true if a new value was actually added
-    pair<iterator, bool> set(const KeyType &key, const MappedType &mapped); 
-
-    // does nothing if key is already present
-    // return value is a pair of the iterator to the key location, 
-    // and a boolean that's true if a new value was actually added
-    pair<iterator, bool> add(const KeyType &key, const MappedType &mapped); 
-
-    void remove(const KeyType& key);
-    void remove(iterator it);
-    void clear();
-
- private:
-    pair<iterator, bool> inlineAdd(const KeyType &key, const MappedType &mapped);
-
-    ImplType m_impl;
-};
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-inline int HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::size() const
-{
-    return m_impl.size(); 
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-int HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::capacity() const
-{ 
-    return m_impl.capacity(); 
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-inline bool HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::isEmpty() const
-{
-    return size() == 0;
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-inline typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::begin()
-{
-    return m_impl.begin();
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-inline typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::end()
-{
-    return m_impl.end();
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-inline typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::const_iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::begin() const
-{
-    return m_impl.begin();
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-inline typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::const_iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::end() const
-{
-    return m_impl.end();
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::find(const KeyType& key)
-{
-    return m_impl.find(key);
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::const_iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::find(const KeyType& key) const
-{
-    return m_impl.find(key);
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-bool HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::contains(const KeyType& key) const
-{
-    return m_impl.contains(key);
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::inlineAdd(const KeyType &key, const MappedType &mapped) 
-{
-    return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped); 
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::set(const KeyType &key, const MappedType &mapped) 
-{
-    pair<iterator, bool> result = inlineAdd(key, mapped);
-    // the add call above won't change anything if the key is
-    // already there; in that case, make sure to set the value.
-    if (!result.second)
-        result.first->second = mapped;    
-    return result;
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::add(const KeyType &key, const MappedType &mapped)
-{
-    return inlineAdd(key, mapped);
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-inline Mapped HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::get(const KeyType &key) const
-{
-    const_iterator it = find(key);
-    if (it == end())
-        return MappedTraits::emptyValue();
-    return it->second;
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-void HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::remove(const KeyType& key)
-{
-    m_impl.remove(key);
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-void HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::remove(iterator it)
-{
-    m_impl.remove(it);
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-void HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::clear()
-{
-    m_impl.clear();
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-void deleteAllValues(HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>& collection)
-{
-    typedef HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits> T;
-    typename T::iterator end = collection.end();
-    for (typename T::iterator it = collection.begin(); it != end; ++it)
-        delete it->second;
-}
+        return m_impl.capacity(); 
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline bool HashMap<T, U, V, W, X>::isEmpty() const
+    {
+        return m_impl.isEmpty();
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin()
+    {
+        return m_impl.begin();
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end()
+    {
+        return m_impl.end();
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const
+    {
+        return m_impl.begin();
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const
+    {
+        return m_impl.end();
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key)
+    {
+        return m_impl.find(*(const KeyStorageType*)&key);
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const
+    {
+        return m_impl.find(*(const KeyStorageType*)&key);
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const
+    {
+        return m_impl.contains(*(const KeyStorageType*)&key);
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline pair<typename HashMap<T, U, V, W, X>::iterator, bool>
+    HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) 
+    {
+        const bool canReplaceDeletedKey = !KeyTraits::needsDestruction || KeyStorageTraits::needsDestruction;
+        typedef HashMapTranslator<canReplaceDeletedKey, ValueType, ValueStorageTraits, HashFunctions> TranslatorType;
+        return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    pair<typename HashMap<T, U, V, W, X>::iterator, bool>
+    HashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) 
+    {
+        pair<iterator, bool> result = inlineAdd(key, mapped);
+        if (!result.second)
+            // add call above didn't change anything, so set the mapped value
+            result.first->second = mapped;
+        return result;
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    pair<typename HashMap<T, U, V, W, X>::iterator, bool>
+    HashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
+    {
+        return inlineAdd(key, mapped);
+    }
+
+    template<typename T, typename U, typename V, typename W, typename MappedTraits>
+    inline typename HashMap<T, U, V, W, MappedTraits>::MappedType
+    HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const
+    {
+        const_iterator it = find(key);
+        if (it == end())
+            return MappedTraits::emptyValue();
+        return it->second;
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline void HashMap<T, U, V, W, X>::remove(iterator it)
+    {
+        if (it.m_impl == m_impl.end())
+            return;
+        it->~ValueType();
+        m_impl.remove(it.m_impl);
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline void HashMap<T, U, V, W, X>::remove(const KeyType& key)
+    {
+        remove(find(key));
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline void HashMap<T, U, V, W, X>::clear()
+    {
+        derefAll();
+        m_impl.clear();
+    }
+
+    template<typename MappedType, typename HashTableType>
+    void deleteAllPairSeconds(HashTableType& collection)
+    {
+        typedef typename HashTableType::iterator iterator;
+        iterator end = collection.end();
+        for (iterator it = collection.begin(); it != end; ++it)
+            delete *(MappedType*)&it->second;
+    }
+
+    template<typename T, typename U, typename V, typename W, typename X>
+    inline void deleteAllValues(HashMap<T, U, V, W, X>& collection)
+    {
+        deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection);
+    }
 
 } // namespace KXMLCore
 
 using KXMLCore::HashMap;
 
-#ifndef HASH_MAP_PTR_SPEC_WORKAROUND
-#include "HashMapPtrSpec.h"
-#endif
-
 #endif /* KXMLCORE_HASH_MAP_H */
diff --git a/JavaScriptCore/kxmlcore/HashMapPtrSpec.h b/JavaScriptCore/kxmlcore/HashMapPtrSpec.h
deleted file mode 100644 (file)
index 58a6309..0000000
+++ /dev/null
@@ -1,228 +0,0 @@
-// -*- mode: c++; c-basic-offset: 4 -*-
-/*
- * This file is part of the KDE libraries
- * Copyright (C) 2005 Apple Computer, Inc.
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Library General Public
- * License as published by the Free Software Foundation; either
- * version 2 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Library General Public License for more details.
- *
- * You should have received a copy of the GNU Library General Public License
- * along with this library; see the file COPYING.LIB.  If not, write to
- * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
- * Boston, MA 02110-1301, USA.
- *
- */
-
-#ifndef KXMLCORE_HASH_MAP_PTR_SPEC_H
-#define KXMLCORE_HASH_MAP_PTR_SPEC_H
-
-#include "HashMap.h"
-
-// This file includes specializations of HashMap for pointer types using raw pointer hashing
-// try to share implementation by making them use the void * version of the code
-// and casting at interfaces
-
-namespace KXMLCore {
-
-    struct VoidPtrHash : public PtrHash<void *>
-    {
-    };
-
-    template<typename P, typename Mapped> class PtrHashConstIteratorAdapter;
-
-    template<typename P, typename Mapped>
-    class PtrHashIteratorAdapter {
-    private:
-        typedef HashMap<P *, Mapped, PtrHash<P *>, HashTraits<P *>, HashTraits<Mapped> > MapType;
-        typedef typename MapType::ValueType ValueType;
-        typedef typename MapType::ImplValueType ImplValueType;
-        typedef typename HashMap<P *, Mapped, PtrHash<P *>, HashTraits<P *>, HashTraits<Mapped> >::ImplIterator ImplIterator;
-        typedef PtrHashIteratorAdapter<P, Mapped> iterator;
-        typedef ValueType& ReferenceType;
-        typedef ValueType *PointerType;
-        
-        friend class HashMap<P *, Mapped, PtrHash<P *>, HashTraits<P *>, HashTraits<Mapped> >;
-        friend class PtrHashConstIteratorAdapter<P, Mapped>;
-        
-    public:
-        PtrHashIteratorAdapter() {}
-        PtrHashIteratorAdapter(const ImplIterator &impl) : m_impl(impl) {}
-        
-        // default copy, assignment and destructor are ok
-        
-        ReferenceType operator*() const { return *reinterpret_cast<PointerType>(m_impl.operator->()); }
-        PointerType operator->() const { return &(operator*()); }
-        
-        iterator& operator++()
-        {
-            ++m_impl;
-            return *this;
-        }
-        
-        // postfix ++ intentionally omitted
-        
-        // Comparison.
-        bool operator==(const iterator& other) const
-        { 
-            return m_impl == other.m_impl; 
-        }
-        
-        bool operator!=(const iterator& other) const 
-        { 
-            return m_impl != other.m_impl; 
-        }
-        
-    private:
-        ImplIterator m_impl;
-    };
-
-    template<typename P, typename Mapped>
-    class PtrHashConstIteratorAdapter {
-    private:
-        typedef HashMap<P *, Mapped, PtrHash<P *>, HashTraits<P *>, HashTraits<Mapped> > MapType;
-        typedef typename MapType::ValueType ValueType;
-        typedef typename MapType::ImplValueType ImplValueType;
-        typedef typename MapType::ImplIterator ImplIterator;
-        typedef typename MapType::ImplConstIterator ImplConstIterator;
-        typedef PtrHashIteratorAdapter<P, Mapped> iterator;
-        typedef PtrHashConstIteratorAdapter<P, Mapped> const_iterator;
-        typedef const ValueType& ReferenceType;
-        typedef const ValueType *PointerType;
-        
-        friend class HashMap<P *, Mapped, PtrHash<P *>, HashTraits<P *>, HashTraits<Mapped> >;
-        
-    public:
-        PtrHashConstIteratorAdapter() {}
-        PtrHashConstIteratorAdapter(const ImplConstIterator &impl) : m_impl(impl) {}
-        PtrHashConstIteratorAdapter(const iterator &other) : m_impl(other.m_impl) { }
-        
-        // default copy, assignment and destructor are ok
-        
-        ReferenceType operator*() const { return *reinterpret_cast<PointerType>(m_impl.operator->()); }
-        PointerType operator->() const { return &(operator*()); }
-        
-        const_iterator& operator++()
-        {
-            ++m_impl;
-            return *this;
-        }
-        
-        // postfix ++ intentionally omitted
-        
-        // Comparison.
-        bool operator==(const const_iterator& other) const
-        { 
-            return m_impl == other.m_impl; 
-        }
-        
-        bool operator!=(const const_iterator& other) const 
-        { 
-            return m_impl != other.m_impl; 
-        }
-        
-    private:
-        ImplConstIterator m_impl;
-    };
-
-    template<typename P, typename Mapped>
-    class HashMap<P *, Mapped, PtrHash<P *>, HashTraits<P *>, HashTraits<Mapped> > {
-    public:
-        typedef P *KeyType;
-        typedef Mapped MappedType;
-        typedef std::pair<KeyType, Mapped> ValueType;
-    private:
-        // important not to use pointerHash/pointerEqual here or instantiation would recurse
-        typedef HashMap<void *, MappedType, VoidPtrHash, HashTraits<void *>, HashTraits<Mapped> > ImplType;
-    public:
-        typedef typename ImplType::ValueType ImplValueType;
-        typedef typename ImplType::iterator ImplIterator;
-        typedef typename ImplType::const_iterator ImplConstIterator;
-        typedef PtrHashIteratorAdapter<P, Mapped> iterator;
-        typedef PtrHashConstIteratorAdapter<P, Mapped> const_iterator;
-        
-        HashMap() {}
-        
-        int size() const { return m_impl.size(); }
-        int capacity() const { return m_impl.capacity(); }
-        bool isEmpty() const { return m_impl.isEmpty(); }
-        
-        iterator begin() { return m_impl.begin(); }
-        iterator end() { return m_impl.end(); }
-        const_iterator begin() const { return m_impl.begin(); }
-        const_iterator end() const { return m_impl.end(); }
-        
-        iterator find(const KeyType& key) { return m_impl.find((void *)(key)); }
-        const_iterator find(const KeyType& key) const { return m_impl.find((void *)(key)); }
-        bool contains(const KeyType& key) const { return m_impl.contains((void *)(key)); }
-        MappedType get(const KeyType &key) const { return m_impl.get((void *)(key)); }
-        
-        std::pair<iterator, bool> set(const KeyType &key, const MappedType &mapped) 
-        { return m_impl.set((void *)(key), mapped); }
-
-        std::pair<iterator, bool> add(const KeyType &key, const MappedType &mapped) 
-        { return m_impl.add((void *)(key), mapped); }
-        
-        void remove(const KeyType& key) { m_impl.remove((void *)(key)); }
-        void remove(iterator it) { m_impl.remove(it.m_impl); }
-        void clear() { m_impl.clear(); }
-        
-    private:
-        ImplType m_impl;
-    };
-    
-    template<typename P, typename Q>
-    class HashMap<P *, Q *, PtrHash<P *>, HashTraits<P *>, HashTraits<Q *> > {
-    private:
-        // important not to use PtrHash here or instantiation would recurse
-        typedef HashMap<void *, void *, VoidPtrHash, HashTraits<void *>, HashTraits<void *> > ImplMapType;
-    public:
-        typedef P *KeyType;
-        typedef Q *MappedType;
-        typedef std::pair<KeyType, MappedType> ValueType;
-        typedef typename std::pair<void *, void *> ImplValueType;
-        typedef HashTableIterator<void *, ImplValueType, PairFirstExtractor<void *, void*>, VoidPtrHash, PairHashTraits<HashTraits<void *>, HashTraits<void *> >, HashTraits<void *> > ImplIterator;
-        typedef HashTableConstIterator<void *, ImplValueType, PairFirstExtractor<void *, void*>, VoidPtrHash, PairHashTraits<HashTraits<void *>, HashTraits<void *> >, HashTraits<void *> > ImplConstIterator;
-        
-        typedef PtrHashIteratorAdapter<P, Q *> iterator;
-        typedef PtrHashConstIteratorAdapter<P, Q *> const_iterator;
-        
-        HashMap() {}
-        
-        int size() const { return m_impl.size(); }
-        int capacity() const { return m_impl.capacity(); }
-        bool isEmpty() const { return m_impl.isEmpty(); }
-        
-        iterator begin() { return m_impl.begin(); }
-        iterator end() { return m_impl.end(); }
-        const_iterator begin() const { return m_impl.begin(); }
-        const_iterator end() const { return m_impl.end(); }
-        
-        iterator find(const KeyType& key) { return m_impl.find((void *)(key)); }
-        const_iterator find(const KeyType& key) const { return m_impl.find((void *)(key)); }
-        bool contains(const KeyType& key) const { return m_impl.contains((void *)(key)); }
-        MappedType get(const KeyType &key) const { return reinterpret_cast<MappedType>(m_impl.get((void *)(key))); }
-        
-        std::pair<iterator, bool> set(const KeyType &key, const MappedType &mapped) 
-        { return m_impl.set((void *)(key), (void *)(mapped)); }
-
-        std::pair<iterator, bool> add(const KeyType &key, const MappedType &mapped) 
-        { return m_impl.add((void *)(key), (void *)(mapped)); }
-        
-        void remove(const KeyType& key) { m_impl.remove((void *)(key)); }
-        void remove(iterator it) { m_impl.remove(it.m_impl); }
-        void clear() { m_impl.clear(); }
-        
-    private:
-        ImplMapType m_impl;
-    };
-
-} // namespace KXMLCore
-
-#endif // KXMLCORE_HASH_MAP_PTR_SPEC_H
index 556a54ea2705b11e12d860891739d20d050bb0a9..3c3212581982cecb51bc62d0194fb0766b506bbc 100644 (file)
 #define KXMLCORE_HASH_SET_H
 
 #include "HashTable.h"
-#include "HashTraits.h"
-#include "HashFunctions.h"
 
 namespace KXMLCore {
 
-    template <typename T>
-    struct IdentityExtractor
-    {
-        static const T& extract(const T& t) 
-        { 
-            return t; 
-        }
-    };
+    template<typename T> struct IdentityExtractor;
 
-    template<typename Value, typename T, typename HashSetTranslator>
-    struct HashSetTranslatorAdapter 
-    {
-        static unsigned hash(const T& key)
-        {
-            return HashSetTranslator::hash(key);
-        }
-        
-        static bool equal(const Value& a, const T& b)
-        {
-            return HashSetTranslator::equal(a, b);
-        }
-        
-        static void translate(Value& location, const T& key, const T&, unsigned hashCode)
-        {
-            HashSetTranslator::translate(location, key, hashCode);
-        }
-    };
-    
-    template<typename Value, typename HashFunctions = typename DefaultHash<Value>::Hash, typename Traits = HashTraits<Value> >
-    class HashSet {
+    template<typename Value, typename HashFunctions, typename Traits> class HashSet;
+    template<typename Value, typename HashFunctions, typename Traits>
+    void deleteAllValues(HashSet<Value, HashFunctions, Traits>&);
+
+    template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
+        typename TraitsArg = HashTraits<ValueArg> > class HashSet {
     private:
-        typedef HashTable<Value, Value, IdentityExtractor<Value>, HashFunctions, Traits, Traits> ImplType;
+        typedef HashArg HashFunctions;
+        typedef TraitsArg ValueTraits;
+
+        typedef typename HashKeyStorageTraits<HashFunctions, ValueTraits>::Hash StorageHashFunctions;
+
+        typedef typename HashKeyStorageTraits<HashFunctions, ValueTraits>::Traits StorageTraits;
+        typedef typename StorageTraits::TraitType StorageType;
+
+        typedef HashTable<StorageType, StorageType, IdentityExtractor<StorageType>,
+            StorageHashFunctions, StorageTraits, StorageTraits> HashTableType;
+
     public:
-        typedef Value ValueType;
-        typedef typename ImplType::iterator iterator;
-        typedef typename ImplType::const_iterator const_iterator;
-        
-        HashSet() {}
-        
+        typedef typename ValueTraits::TraitType ValueType;
+        typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
+        typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
+
+        HashSet();
+        HashSet(const HashSet&);
+        HashSet& operator=(const HashSet&);
+        ~HashSet();
+
         int size() const;
         int capacity() const;
         bool isEmpty() const;
-        
+
         iterator begin();
         iterator end();
         const_iterator begin() const;
         const_iterator end() const;
-        
-        iterator find(const ValueType& value);
-        const_iterator find(const ValueType& value) const;
-        bool contains(const ValueType& value) const;
-        
+
+        iterator find(const ValueType&);
+        const_iterator find(const ValueType&) const;
+        bool contains(const ValueType&) const;
+
         // the return value is a pair of an interator to the new value's location, 
         // and a bool that is true if an new entry was added
-        std::pair<iterator, bool> add(const ValueType &value);
-        
+        pair<iterator, bool> add(const ValueType&);
+
         // a special version of add() that finds the object by hashing and comparing
         // with some other type, to avoid the cost of type conversion if the object is already
         // in the table. HashTranslator should have the following methods:
         //   static unsigned hash(const T&);
         //   static bool equal(const ValueType&, const T&);
         //   static translate(ValueType&, const T&, unsigned hashCode);
-        template<typename T, typename HashTranslator> 
-        std::pair<iterator, bool> add(const T& value);
-        
-        void remove(const ValueType& value);
-        void remove(iterator it);
+        template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&);
+
+        void remove(const ValueType&);
+        void remove(iterator);
         void clear();
-        
+
     private:
-        ImplType m_impl;
+        void refAll();
+        void derefAll();
+
+        friend void deleteAllValues<>(HashSet&);
+
+        HashTableType m_impl;
     };
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    inline int HashSet<Value, HashFunctions, Traits>::size() const
+
+    template<typename T> struct IdentityExtractor {
+        static const T& extract(const T& t) { return t; }
+    };
+
+    template<bool canReplaceDeletedValue, typename ValueType, typename StorageTraits, typename HashFunctions>
+    struct HashSetTranslator;
+
+    template<typename ValueType, typename StorageTraits, typename HashFunctions>
+    struct HashSetTranslator<true, ValueType, StorageTraits, HashFunctions> {
+        typedef typename StorageTraits::TraitType StorageType;
+        static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
+        static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }
+        static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)
+        {
+            *(ValueType*)&location = key;
+        }
+    };
+
+    template<typename ValueType, typename StorageTraits, typename HashFunctions>
+    struct HashSetTranslator<false, ValueType, StorageTraits, HashFunctions> {
+        typedef typename StorageTraits::TraitType StorageType;
+        static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
+        static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }
+        static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)
+        {
+            if (location == StorageTraits::deletedValue())
+                location = StorageTraits::emptyValue();
+            *(ValueType*)&location = key;
+        }
+    };
+
+    template<bool canReplaceDeletedValue, typename ValueType, typename StorageTraits, typename T, typename Translator>
+    struct HashSetTranslatorAdapter;
+
+    template<typename ValueType, typename StorageTraits, typename T, typename Translator>
+    struct HashSetTranslatorAdapter<true, ValueType, StorageTraits, T, Translator> {
+        typedef typename StorageTraits::TraitType StorageType;
+        static unsigned hash(const T& key) { return Translator::hash(key); }
+        static bool equal(const StorageType& a, const T& b) { return Translator::equal(*(const ValueType*)&a, b); }
+        static void translate(StorageType& location, const T& key, const T&, unsigned hashCode)
+        {
+            Translator::translate(*(ValueType*)&location, key, hashCode);
+        }
+    };
+
+    template<typename ValueType, typename StorageTraits, typename T, typename Translator>
+    struct HashSetTranslatorAdapter<false, ValueType, StorageTraits, T, Translator> {
+        typedef typename StorageTraits::TraitType StorageType;
+        static unsigned hash(const T& key) { return Translator::hash(key); }
+        static bool equal(const StorageType& a, const T& b) { return Translator::equal(*(const ValueType*)&a, b); }
+        static void translate(StorageType& location, const T& key, const T&, unsigned hashCode)
+        {
+            if (location == StorageTraits::deletedValue())
+                location = StorageTraits::emptyValue();
+            Translator::translate(*(ValueType*)&location, key, hashCode);
+        }
+    };
+
+    template<typename T, typename U, typename V>
+    inline void HashSet<T, U, V>::refAll()
+    {
+        HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
+    }
+
+    template<typename T, typename U, typename V>
+    inline void HashSet<T, U, V>::derefAll()
+    {
+        HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
+    }
+
+    template<typename T, typename U, typename V>
+    inline HashSet<T, U, V>::HashSet()
+    {
+    }
+
+    template<typename T, typename U, typename V>
+    inline HashSet<T, U, V>::HashSet(const HashSet& other)
+        : m_impl(other.m_impl)
+    {
+        refAll();
+    }
+
+    template<typename T, typename U, typename V>
+    inline HashSet<T, U, V>& HashSet<T, U, V>::operator=(const HashSet& other)
+    {
+        HashSet tmp(other);
+        m_impl.swap(tmp.m_impl); 
+    }
+
+    template<typename T, typename U, typename V>
+    inline HashSet<T, U, V>::~HashSet()
+    {
+        derefAll();
+    }
+
+    template<typename T, typename U, typename V>
+    inline int HashSet<T, U, V>::size() const
     {
         return m_impl.size(); 
     }
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    int HashSet<Value, HashFunctions, Traits>::capacity() const
+
+    template<typename T, typename U, typename V>
+    inline int HashSet<T, U, V>::capacity() const
     {
         return m_impl.capacity(); 
     }
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    inline bool HashSet<Value, HashFunctions, Traits>::isEmpty() const
+
+    template<typename T, typename U, typename V>
+    inline bool HashSet<T, U, V>::isEmpty() const
     {
-        return size() == 0
+        return m_impl.isEmpty()
     }
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    inline typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::begin()
+
+    template<typename T, typename U, typename V>
+    inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin()
     {
         return m_impl.begin(); 
     }
 
-    template<typename Value, typename HashFunctions, typename Traits>
-    inline typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::end()
+    template<typename T, typename U, typename V>
+    inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end()
     {
         return m_impl.end(); 
     }
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    inline typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::begin() const
+
+    template<typename T, typename U, typename V>
+    inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::begin() const
     {
         return m_impl.begin(); 
     }
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    inline typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::end() const
+
+    template<typename T, typename U, typename V>
+    inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::end() const
     {
         return m_impl.end(); 
     }
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::find(const ValueType& value)
+
+    template<typename T, typename U, typename V>
+    inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value)
     {
-        return m_impl.find(value); 
+        return m_impl.find(*(const StorageType*)&value); 
     }
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::find(const ValueType& value) const
+
+    template<typename T, typename U, typename V>
+    inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::find(const ValueType& value) const
     {
-        return m_impl.find(value); 
+        return m_impl.find(*(const StorageType*)&value); 
     }
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    inline bool HashSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const
+
+    template<typename T, typename U, typename V>
+    inline bool HashSet<T, U, V>::contains(const ValueType& value) const
     {
-        return m_impl.contains(value); 
+        return m_impl.contains(*(const StorageType*)&value); 
     }
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    std::pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> HashSet<Value, HashFunctions, Traits>::add(const ValueType &value)
+
+    template<typename T, typename U, typename V>
+    pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType &value)
     {
-        return m_impl.add(value); 
+        const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;
+        typedef HashSetTranslator<canReplaceDeletedValue, ValueType, StorageTraits, HashFunctions> Translator;
+        return m_impl.template add<ValueType, ValueType, Translator>(value, value);
     }
-    
+
     template<typename Value, typename HashFunctions, typename Traits>
-    template<typename T, typename HashSetTranslator> 
-    std::pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> HashSet<Value, HashFunctions, Traits>::add(const T& value)
+    template<typename T, typename Translator> 
+    pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>
+    HashSet<Value, HashFunctions, Traits>::add(const T& value)
     {
-        return m_impl.template add<T, T, HashSetTranslatorAdapter<ValueType, T, HashSetTranslator> >(value, value); 
+        const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;
+        typedef HashSetTranslatorAdapter<canReplaceDeletedValue, ValueType, StorageTraits, T, Translator> Adapter;
+        return m_impl.template add<T, T, Adapter>(value, value);
     }
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    void HashSet<Value, HashFunctions, Traits>::remove(const ValueType& value)
+
+    template<typename T, typename U, typename V>
+    inline void HashSet<T, U, V>::remove(iterator it)
     {
-        m_impl.remove(value); 
+        if (it.m_impl == m_impl.end())
+            return;
+        it->~ValueType();
+        m_impl.remove(it.m_impl);
     }
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    void HashSet<Value, HashFunctions, Traits>::remove(iterator it)
+
+    template<typename T, typename U, typename V>
+    inline void HashSet<T, U, V>::remove(const ValueType& value)
     {
-        m_impl.remove(it); 
+        remove(find(value));
     }
-    
-    template<typename Value, typename HashFunctions, typename Traits>
-    void HashSet<Value, HashFunctions, Traits>::clear()
+
+    template<typename T, typename U, typename V>
+    inline void HashSet<T, U, V>::clear()
     {
+        derefAll();
         m_impl.clear(); 
     }
 
-    template<typename Value, typename HashFunctions, typename Traits>
-    void deleteAllValues(HashSet<Value, HashFunctions, Traits>& collection)
+    template<typename ValueType, typename HashTableType>
+    void deleteAllValues(HashTableType& collection)
+    {
+        typedef typename HashTableType::iterator iterator;
+        iterator end = collection.end();
+        for (iterator it = collection.begin(); it != end; ++it)
+            delete *(ValueType*)&*it;
+    }
+
+    template<typename T, typename U, typename V>
+    inline void deleteAllValues(HashSet<T, U, V>& collection)
     {
-        typedef HashSet<Value, HashFunctions, Traits> T;
-        typename T::iterator end = collection.end();
-        for (typename T::iterator it = collection.begin(); it != end; ++it)
-            delete (*it);
+        deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
     }
 
-} // namespace khtml
+} // namespace KXMLCore
 
 using KXMLCore::HashSet;
 
 #endif /* KXMLCORE_HASH_SET_H */
-
-
index f205428ab9a05e8818176fcf8700bbc3f5ed3b63..adc697d5094bd883033a964bd11dc954024554b8 100644 (file)
@@ -136,12 +136,13 @@ namespace KXMLCore {
         }
 #endif
 
-        ReferenceType operator*() const
+        PointerType get() const
         {
             checkValidity();
-            return *m_position;
+            return m_position;
         }
-        PointerType operator->() const { return &**this; }
+        ReferenceType operator*() const { return *get(); }
+        PointerType operator->() const { return get(); }
 
         const_iterator& operator++()
         {
@@ -216,8 +217,9 @@ namespace KXMLCore {
 
         // default copy, assignment and destructor are OK
 
-        ReferenceType operator*() const { return const_cast<ReferenceType>(*m_iterator); }
-        PointerType operator->() const { return &**this; }
+        PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
+        ReferenceType operator*() const { return *get(); }
+        PointerType operator->() const { return get(); }
 
         iterator& operator++() { ++m_iterator; return *this; }
 
@@ -262,6 +264,7 @@ namespace KXMLCore {
     public:
         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
+        typedef Traits ValueTraits;
         typedef Key KeyType;
         typedef Value ValueType;
         typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType;
@@ -280,6 +283,7 @@ namespace KXMLCore {
 
         int size() const { return m_keyCount; }
         int capacity() const { return m_tableSize; }
+        bool isEmpty() const { return !m_keyCount; }
 
         pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); }
 
@@ -464,7 +468,7 @@ namespace KXMLCore {
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
-    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key)
+    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key)
     {
         if (!m_table)
             return end();
@@ -476,7 +480,7 @@ namespace KXMLCore {
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
-    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key) const
+    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key) const
     {
         if (!m_table)
             return end();
@@ -488,7 +492,7 @@ namespace KXMLCore {
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
-    inline bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const KeyType& key) const
+    bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const KeyType& key) const
     {
         if (!m_table)
             return false;
@@ -497,7 +501,7 @@ namespace KXMLCore {
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
-    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
+    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
     {
         invalidateIterators();
         checkTableConsistency();
@@ -516,15 +520,6 @@ namespace KXMLCore {
         checkTableConsistency();
     }
 
-    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
-    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
-    {
-        if (!m_table)
-            return;
-
-        remove(find(key));
-    }
-
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
     {
@@ -534,37 +529,36 @@ namespace KXMLCore {
         remove(const_cast<ValueType*>(it.m_iterator.m_position));
     }
 
+    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
+    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
+    {
+        remove(find(key));
+    }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
-    inline Value *HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
+    Value *HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
     {
         // would use a template member function with explicit specializations here, but
         // gcc doesn't appear to support that
         if (Traits::emptyValueIsZero)
-            return reinterpret_cast<ValueType *>(fastCalloc(size, sizeof(ValueType)));
-        else {
-            ValueType *result = reinterpret_cast<ValueType *>(fastMalloc(size * sizeof(ValueType)));
-            for (int i = 0; i < size; i++) {
-                initializeBucket(result[i]);
-            }
-            return result;
-        }
+            return static_cast<ValueType *>(fastCalloc(size, sizeof(ValueType)));
+        ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
+        for (int i = 0; i < size; i++)
+            initializeBucket(result[i]);
+        return result;
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
-    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size)
+    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size)
     {
-        if (Traits::needsDestruction) {
-            for (int i = 0; i < size; ++i) {
-                (&table[i])->~ValueType();
-            }
-        }
-
+        if (Traits::needsDestruction)
+            for (int i = 0; i < size; ++i)
+                table[i].~ValueType();
         fastFree(table);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
-    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
+    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
     {
         int newSize;
         if (m_tableSize == 0)
@@ -594,10 +588,9 @@ namespace KXMLCore {
         m_tableSizeMask = newTableSize - 1;
         m_table = allocateTable(newTableSize);
 
-        for (int i = 0; i != oldTableSize; ++i) {
+        for (int i = 0; i != oldTableSize; ++i)
             if (!isEmptyOrDeletedBucket(oldTable[i]))
                 reinsert(oldTable[i]);
-        }
 
         m_deletedCount = 0;
 
@@ -607,7 +600,7 @@ namespace KXMLCore {
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
-    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
+    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
     {
         invalidateIterators();
         deallocateTable(m_table, m_tableSize);
@@ -780,6 +773,156 @@ namespace KXMLCore {
 
 #endif // CHECK_HASHTABLE_ITERATORS
 
+    // iterator adapters
+
+    template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {
+        HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
+
+        const ValueType* get() const { return (const ValueType*)m_impl.get(); }
+        const ValueType& operator*() const { return *get(); }
+        const ValueType* operator->() const { return get(); }
+
+        HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
+        // postfix ++ intentionally omitted
+
+        typename HashTableType::const_iterator m_impl;
+    };
+
+    template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {
+        HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
+
+        ValueType* get() const { return (ValueType*)m_impl.get(); }
+        ValueType& operator*() const { return *get(); }
+        ValueType* operator->() const { return get(); }
+
+        HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
+        // postfix ++ intentionally omitted
+
+        operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
+            typename HashTableType::const_iterator i = m_impl;
+            return i;
+        }
+
+        typename HashTableType::iterator m_impl;
+    };
+
+    template<typename T, typename U>
+    inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
+    {
+        return a.m_impl == b.m_impl;
+    }
+
+    template<typename T, typename U>
+    inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
+    {
+        return a.m_impl != b.m_impl;
+    }
+
+    template<typename T, typename U>
+    inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
+    {
+        return a.m_impl == b.m_impl;
+    }
+
+    template<typename T, typename U>
+    inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
+    {
+        return a.m_impl != b.m_impl;
+    }
+
+    // reference count manager
+    
+    template<typename ValueTraits, typename ValueStorageTraits> struct NeedsRef {
+        static const bool value = ValueTraits::needsRef && !ValueStorageTraits::needsRef;
+    };
+
+    template<bool needsRef, typename ValueTraits> struct RefCounterBase;
+
+    template<typename ValueTraits>
+    struct RefCounterBase<false, ValueTraits> {
+        typedef typename ValueTraits::TraitType ValueType;
+        static void ref(const ValueType&) { }
+        static void deref(const ValueType&) { }
+    };
+
+    template<typename ValueTraits>
+    struct RefCounterBase<true, ValueTraits> {
+        typedef typename ValueTraits::TraitType ValueType;
+        static void ref(const ValueType& v) { ValueTraits::ref(*(const ValueType*)&v); }
+        static void deref(const ValueType& v) { ValueTraits::deref(*(const ValueType*)&v); }
+    };
+
+    template<typename ValueTraits, typename ValueStorageTraits> struct RefCounter {
+        typedef typename ValueTraits::TraitType ValueType;
+        typedef typename ValueStorageTraits::TraitType ValueStorageType;
+        static const bool needsRef = NeedsRef<ValueTraits, ValueStorageTraits>::value;
+        typedef RefCounterBase<needsRef, ValueTraits> Base;
+        static void ref(const ValueStorageType& v) { Base::ref(*(const ValueType*)&v); }
+        static void deref(const ValueStorageType& v) { Base::deref(*(const ValueType*)&v); }
+    };
+
+    template<typename FirstTraits, typename SecondTraits, typename ValueStorageTraits>
+    struct RefCounter<PairBaseHashTraits<FirstTraits, SecondTraits>, ValueStorageTraits> {
+        typedef typename FirstTraits::TraitType FirstType;
+        typedef typename SecondTraits::TraitType SecondType;
+        typedef typename ValueStorageTraits::FirstTraits FirstStorageTraits;
+        typedef typename ValueStorageTraits::SecondTraits SecondStorageTraits;
+        typedef typename ValueStorageTraits::TraitType ValueStorageType;
+        static const bool firstNeedsRef = NeedsRef<FirstTraits, FirstStorageTraits>::value;
+        static const bool secondNeedsRef = NeedsRef<SecondTraits, SecondStorageTraits>::value;
+        typedef RefCounterBase<firstNeedsRef, FirstTraits> FirstBase;
+        typedef RefCounterBase<secondNeedsRef, SecondTraits> SecondBase;
+        static void ref(const ValueStorageType& v) {
+            FirstBase::ref(*(const FirstType*)&v.first);
+            SecondBase::ref(*(const SecondType*)&v.second);
+        }
+        static void deref(const ValueStorageType& v) {
+            FirstBase::deref(*(const FirstType*)&v.first);
+            SecondBase::deref(*(const SecondType*)&v.second);
+        }
+    };
+
+    template<bool needsRef, typename HashTableType, typename ValueTraits> struct HashTableRefCounterBase;
+
+    template<typename HashTableType, typename ValueTraits>
+    struct HashTableRefCounterBase<false, HashTableType, ValueTraits>
+    {
+        static void refAll(HashTableType&) { }
+        static void derefAll(HashTableType&) { }
+    };
+
+    template<typename HashTableType, typename ValueTraits>
+    struct HashTableRefCounterBase<true, HashTableType, ValueTraits>
+    {
+        typedef typename HashTableType::iterator iterator;
+        typedef RefCounter<ValueTraits, typename HashTableType::ValueTraits> ValueRefCounter;
+        static void refAll(HashTableType&);
+        static void derefAll(HashTableType&);
+    };
+
+    template<typename HashTableType, typename ValueTraits>
+    void HashTableRefCounterBase<true, HashTableType, ValueTraits>::refAll(HashTableType& table)
+    {
+        iterator end = table.end();
+        for (iterator it = table.begin(); it != end; ++it)
+            ValueRefCounter::ref(*it);
+    }
+
+    template<typename HashTableType, typename ValueTraits>
+    void HashTableRefCounterBase<true, HashTableType, ValueTraits>::derefAll(HashTableType& table)
+    {
+        iterator end = table.end();
+        for (iterator it = table.begin(); it != end; ++it)
+            ValueRefCounter::deref(*it);
+    }
+
+    template<typename HashTableType, typename ValueTraits> struct HashTableRefCounter {
+        static const bool needsRef = NeedsRef<ValueTraits, typename HashTableType::ValueTraits>::value;
+        typedef HashTableRefCounterBase<needsRef, HashTableType, ValueTraits> Base;
+        static void refAll(HashTableType& table) { Base::refAll(table); }
+        static void derefAll(HashTableType& table) { Base::derefAll(table); }
+    };
+
 } // namespace KXMLCore
 
 #endif // KXMLCORE_HASH_TABLE_H
index 5999a4787149b4972534bac91d246f1afe9beaad..e3cf269ff5b27e1414187e8686055e15f9084f80 100644 (file)
 #ifndef KXMLCORE_HASH_TRAITS_H
 #define KXMLCORE_HASH_TRAITS_H
 
-#include "RefPtr.h"
+#include "HashFunctions.h"
 #include <utility>
 
 namespace KXMLCore {
 
     using std::pair;
-
-    template <typename T> struct IsInteger           { static const bool value = false; };
-    template <> struct IsInteger<bool>               { static const bool value = true; };
-    template <> struct IsInteger<char>               { static const bool value = true; };
-    template <> struct IsInteger<signed char>        { static const bool value = true; };
-    template <> struct IsInteger<unsigned char>      { static const bool value = true; };
-    template <> struct IsInteger<short>              { static const bool value = true; };
-    template <> struct IsInteger<unsigned short>     { static const bool value = true; };
-    template <> struct IsInteger<int>                { static const bool value = true; };
-    template <> struct IsInteger<unsigned int>       { static const bool value = true; };
-    template <> struct IsInteger<long>               { static const bool value = true; };
-    template <> struct IsInteger<unsigned long>      { static const bool value = true; };
-    template <> struct IsInteger<long long>          { static const bool value = true; };
-    template <> struct IsInteger<unsigned long long> { static const bool value = true; };
+    using std::make_pair;
+
+    template<typename T> struct IsInteger           { static const bool value = false; };
+    template<> struct IsInteger<bool>               { static const bool value = true; };
+    template<> struct IsInteger<char>               { static const bool value = true; };
+    template<> struct IsInteger<signed char>        { static const bool value = true; };
+    template<> struct IsInteger<unsigned char>      { static const bool value = true; };
+    template<> struct IsInteger<short>              { static const bool value = true; };
+    template<> struct IsInteger<unsigned short>     { static const bool value = true; };
+    template<> struct IsInteger<int>                { static const bool value = true; };
+    template<> struct IsInteger<unsigned int>       { static const bool value = true; };
+    template<> struct IsInteger<long>               { static const bool value = true; };
+    template<> struct IsInteger<unsigned long>      { static const bool value = true; };
+    template<> struct IsInteger<long long>          { static const bool value = true; };
+    template<> struct IsInteger<unsigned long long> { static const bool value = true; };
+
+    template<typename T> struct HashTraits;
 
     template<bool isInteger, typename T> struct GenericHashTraitsBase;
     template<typename T> struct GenericHashTraitsBase<true, T> {
         typedef T TraitType;
+        typedef HashTraits<typename IntTypes<sizeof(T)>::SignedType> StorageTraits;
         static const bool emptyValueIsZero = true;
         static const bool needsDestruction = false;
-        static TraitType emptyValue() { return 0; }
     };
     template<typename T> struct GenericHashTraitsBase<false, T> {
         typedef T TraitType;
+        typedef HashTraits<T> StorageTraits;
         static const bool emptyValueIsZero = false;
         static const bool needsDestruction = true;
-        static TraitType emptyValue() { return TraitType(); }
     };
 
-    template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> { };
+    template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
+        static T emptyValue() { return T(); }
+        static const bool needsRef = false;
+    };
 
     template<typename T> struct HashTraits : GenericHashTraits<T> { };
 
-    // may not be appropriate for all uses since it disallows 0 and -1 as keys
+    // signed integer traits may not be appropriate for all uses since they disallow 0 and -1 as keys
+    template<> struct HashTraits<signed char> : GenericHashTraits<int> {
+        static signed char deletedValue() { return -1; }
+    };
+    template<> struct HashTraits<short> : GenericHashTraits<int> {
+        static short deletedValue() { return -1; }
+    };
     template<> struct HashTraits<int> : GenericHashTraits<int> {
-        static TraitType deletedValue() { return -1; }
+        static int deletedValue() { return -1; }
+    };
+    template<> struct HashTraits<long> : GenericHashTraits<long> {
+        static long deletedValue() { return -1; }
+    };
+    template<> struct HashTraits<long long> : GenericHashTraits<long long> {
+        static long deletedValue() { return -1; }
     };
 
     template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
-        typedef P* TraitType;
+        typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
         static const bool emptyValueIsZero = true;
         static const bool needsDestruction = false;
-        static TraitType emptyValue() { return 0; }
-        static TraitType deletedValue() { return reinterpret_cast<P*>(-1); }
+        static P* deletedValue() { return reinterpret_cast<P*>(-1); }
     };
 
     template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > {
+        typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
         static const bool emptyValueIsZero = true;
+        static const bool needsRef = true;
+        static void ref(const RefPtr<P>& p) { if (p) p->ref(); }
+        static void deref(const RefPtr<P>& p) { if (p) p->deref(); }
     };
 
-    template<typename T, typename Traits> class DeletedValueAssigner;
+    // template to set deleted values
+
+    template<typename Traits> struct DeletedValueAssigner {
+        static void assignDeletedValue(typename Traits::TraitType& location) { location = Traits::deletedValue(); }
+    };
 
     template<typename T, typename Traits> inline void assignDeleted(T& location)
     {
-        DeletedValueAssigner<T, Traits>::assignDeletedValue(location);
+        DeletedValueAssigner<Traits>::assignDeletedValue(location);
     }
 
-    template<typename FirstTraits, typename SecondTraits>
-    struct PairHashTraits : GenericHashTraits<pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> > {
-    private:
-        typedef typename FirstTraits::TraitType FirstType;
-        typedef typename SecondTraits::TraitType SecondType;
-    public:
-        typedef pair<FirstType, SecondType> TraitType;
+    // special traits for pairs, helpful for their use in HashMap implementation
+
+    template<typename FirstTraits, typename SecondTraits> struct PairHashTraits;
+
+    template<typename FirstTraitsArg, typename SecondTraitsArg>
+    struct PairBaseHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
+        typedef FirstTraitsArg FirstTraits;
+        typedef SecondTraitsArg SecondTraits;
+        typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
+
+        typedef PairHashTraits<typename FirstTraits::StorageTraits, typename SecondTraits::StorageTraits> StorageTraits;
 
         static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
-        static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
 
         static TraitType emptyValue()
         {
-            return TraitType(FirstTraits::emptyValue(), SecondTraits::emptyValue());
+            return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue());
         }
+    };
+
+    template<typename FirstTraits, typename SecondTraits>
+    struct PairHashTraits : PairBaseHashTraits<FirstTraits, SecondTraits> {
+        typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
+
+        static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
 
         static TraitType deletedValue()
         {
@@ -109,7 +144,7 @@ namespace KXMLCore {
 
         static void assignDeletedValue(TraitType& location)
         {
-            assignDeleted<FirstType, FirstTraits>(location.first);
+            assignDeleted<typename FirstTraits::TraitType, FirstTraits>(location.first);
             location.second = SecondTraits::emptyValue();
         }
     };
@@ -117,12 +152,8 @@ namespace KXMLCore {
     template<typename First, typename Second>
     struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
 
-    template<typename T, typename Traits> struct DeletedValueAssigner {
-        static void assignDeletedValue(T& location) { location = Traits::deletedValue(); }
-    };
-
     template<typename FirstTraits, typename SecondTraits>
-    struct DeletedValueAssigner<pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>, PairHashTraits<FirstTraits, SecondTraits> >
+    struct DeletedValueAssigner<PairHashTraits<FirstTraits, SecondTraits> >
     {
         static void assignDeletedValue(pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>& location)
         {
@@ -131,7 +162,7 @@ namespace KXMLCore {
     };
 
     template<typename First, typename Second>
-    struct DeletedValueAssigner<pair<First, Second>, HashTraits<pair<First, Second> > >
+    struct DeletedValueAssigner<HashTraits<pair<First, Second> > >
     {
         static void assignDeletedValue(pair<First, Second>& location)
         {
@@ -139,6 +170,22 @@ namespace KXMLCore {
         }
     };
 
+    // hassh functions and traits that are equivalent (for code sharing)
+
+    template<typename HashArg, typename TraitsArg> struct HashKeyStorageTraits {
+        typedef HashArg Hash;
+        typedef TraitsArg Traits;
+    };
+    template<typename P> struct HashKeyStorageTraits<PtrHash<P*>, HashTraits<P*> > {
+        typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
+        typedef IntHash<IntType> Hash;
+        typedef HashTraits<IntType> Traits;
+    };
+    template<typename P> struct HashKeyStorageTraits<PtrHash<RefPtr<P> >, HashTraits<RefPtr<P> > > {
+        typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
+        typedef IntHash<IntType> Hash;
+        typedef HashTraits<IntType> Traits;
+    };
 
 } // namespace KXMLCore
 
index 8718e75feaac12f5dc282adfb1542267f2090e06..06c3e52393c0487b70646527d0128d9efe6c522c 100644 (file)
@@ -1,3 +1,69 @@
+2006-04-05  Darin Adler  <darin@apple.com>
+
+        Reviewed by Maciej.
+
+        - fix for http://bugzilla.opendarwin.org/show_bug.cgi?id=8049
+          StringImpl hash traits deleted value creates an init routine for WebCore
+          <rdar://problem/4442248> REGRESSION: WebCore has init routines (8049)
+
+        * 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.
+
 2006-04-05  Beth Dakin  <bdakin@apple.com>
 
         Reviewed by Darin.
         (WebCore::RenderTheme::paintBorderOnly):
         * rendering/RenderTheme.h:
 
-2006-03-30  Darin Adler  <darin@apple.com>
+2006-03-31  Darin Adler  <darin@apple.com>
 
         Reviewed by John Sullivan.
 
diff --git a/WebCore/ForwardingHeaders/kxmlcore/HashTraits.h b/WebCore/ForwardingHeaders/kxmlcore/HashTraits.h
new file mode 100644 (file)
index 0000000..fa2ce1c
--- /dev/null
@@ -0,0 +1 @@
+#import <JavaScriptCore/HashTraits.h>
index 40c63696ffb6ccff468d6cfe8a3ac8e95344db18..99d24af4910d6d53054ec23f03ab9bfd7a25a6f0 100644 (file)
                930705EB09E0C9F600B17FE4 /* JSCSSPrimitiveValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 930705EA09E0C9F600B17FE4 /* JSCSSPrimitiveValue.h */; };
                930CAD1509C4F3C300229C04 /* JSCanvasRenderingContext2DBase.h in Headers */ = {isa = PBXBuildFile; fileRef = 930CAD1409C4F3C300229C04 /* JSCanvasRenderingContext2DBase.h */; };
                930CAD2609C4F49100229C04 /* JSCanvasRenderingContext2DBase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 930CAD2509C4F49100229C04 /* JSCanvasRenderingContext2DBase.cpp */; };
+               93126F6109D7A736008D9626 /* StringHash.h in Headers */ = {isa = PBXBuildFile; fileRef = 93126F6009D7A736008D9626 /* StringHash.h */; };
                9326DC0B09DAD5BE00AFC847 /* CharsetData.h in Headers */ = {isa = PBXBuildFile; fileRef = 9326DC0A09DAD5BE00AFC847 /* CharsetData.h */; };
                9326DC0C09DAD5D600AFC847 /* CharsetData.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 656581AC09D14EE6000E61D7 /* CharsetData.cpp */; };
                9327A94209968D1A0068A546 /* HTMLOptionsCollection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 9327A94109968D1A0068A546 /* HTMLOptionsCollection.cpp */; };
                014CEA440018CDF011CA2923 /* Development */ = {
                        isa = PBXBuildStyle;
                        buildSettings = {
-                               CREATE_HASH_TABLE = "$(BUILT_PRODUCTS_DIR)/JavaScriptCore.framework/PrivateHeaders/create_hash_table";
                                DEBUG_DEFINES = "";
                                EXPORTED_SYMBOLS_FILE = "$(DERIVED_FILES_DIR)/WebCore-combined.exp";
                                GCC_GENERATE_DEBUGGING_SYMBOLS = YES;
                014CEA450018CDF011CA2923 /* Deployment */ = {
                        isa = PBXBuildStyle;
                        buildSettings = {
-                               CREATE_HASH_TABLE = "$(BUILT_PRODUCTS_DIR)/JavaScriptCore.framework/PrivateHeaders/create_hash_table";
                                GCC_GENERATE_DEBUGGING_SYMBOLS = YES;
                                MACOSX_DEPLOYMENT_TARGET = 10.3;
                                PREBINDING = NO;
                F58C8A07025BD3BC018635CA /* OptimizedWithSymbols */ = {
                        isa = PBXBuildStyle;
                        buildSettings = {
-                               CREATE_HASH_TABLE = "$(BUILT_PRODUCTS_DIR)/JavaScriptCore.framework/PrivateHeaders/create_hash_table";
                                GCC_GENERATE_DEBUGGING_SYMBOLS = YES;
                                MACOSX_DEPLOYMENT_TARGET = 10.3;
                                PREBINDING = NO;
                930CAB9609C49FAA00229C04 /* CodeGeneratorJS.pm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.script.perl; name = CodeGeneratorJS.pm; path = bindings/scripts/CodeGeneratorJS.pm; sourceTree = "<group>"; };
                930CAD1409C4F3C300229C04 /* JSCanvasRenderingContext2DBase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = JSCanvasRenderingContext2DBase.h; path = bindings/js/JSCanvasRenderingContext2DBase.h; sourceTree = "<group>"; };
                930CAD2509C4F49100229C04 /* JSCanvasRenderingContext2DBase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = JSCanvasRenderingContext2DBase.cpp; path = bindings/js/JSCanvasRenderingContext2DBase.cpp; sourceTree = "<group>"; };
+               93126F6009D7A736008D9626 /* StringHash.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = StringHash.h; path = platform/StringHash.h; sourceTree = "<group>"; };
                9326DC0A09DAD5BE00AFC847 /* CharsetData.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = CharsetData.h; path = platform/CharsetData.h; sourceTree = "<group>"; };
                9327A94109968D1A0068A546 /* HTMLOptionsCollection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = HTMLOptionsCollection.cpp; sourceTree = "<group>"; };
                93309D87099E64910056E581 /* AppendNodeCommand.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AppendNodeCommand.cpp; sourceTree = "<group>"; };
                                6582A14809999D6C00BEEB6D /* mac */,
                                BCFB2F74097A2E1A00BA703D /* Arena.cpp */,
                                BCFB2F75097A2E1A00BA703D /* Arena.h */,
-                               BCB16B880979B01400467741 /* DeprecatedArray.h */,
                                BCB16B890979B01400467741 /* ArrayImpl.cpp */,
                                BCB16B8A0979B01400467741 /* ArrayImpl.h */,
                                93CD4FD70995F9EA007ECC97 /* AtomicString.cpp */,
                                BCC8CFCA0986CD2400140BF2 /* ColorData.gperf */,
                                9352088109BD45E900F2038D /* CookieJar.h */,
                                F587868402DE3B8601EA4122 /* Cursor.h */,
+                               BCB16B880979B01400467741 /* DeprecatedArray.h */,
+                               6582A13D09999CD600BEEB6D /* DeprecatedString.cpp */,
+                               6582A13E09999CD600BEEB6D /* DeprecatedString.h */,
+                               651B4D8309AC83370029F1EF /* DeprecatedStringList.cpp */,
+                               651B4D8409AC83370029F1EF /* DeprecatedStringList.h */,
                                BC73E3900978CED700EDFF8A /* FloatPoint.cpp */,
                                BC73E3910978CED700EDFF8A /* FloatPoint.h */,
                                BCB16AF50979A08500467741 /* FloatRect.cpp */,
                                BC73E25C0978682700EDFF8A /* FloatSize.h */,
                                BC6D6DD009AF906600F59759 /* Font.cpp */,
                                BC6D6DD109AF906600F59759 /* Font.h */,
+                               BCEB377509B7BB0D00CB38B1 /* FontDataSet.h */,
                                BCC47E6A09A3FE4700ADB771 /* FontDescription.h */,
                                BCC47E2409A3D6F100ADB771 /* FontFamily.cpp */,
                                BCC47E2509A3D6F100ADB771 /* FontFamily.h */,
-                               BCEB377509B7BB0D00CB38B1 /* FontDataSet.h */,
                                A823A75B09B6E53900B60641 /* GraphicsContext.cpp */,
                                935367E409AF77DD00D35CD6 /* GraphicsContext.h */,
                                BC6B7BAE0993603C0052867B /* Image.cpp */,
                                BCB16AF70979A08500467741 /* IntRect.cpp */,
                                BCB16AF80979A08500467741 /* IntRect.h */,
                                BCF1A5EF097839600061A123 /* IntSize.h */,
-                               935C476609AC4D4300A6AAB4 /* PlatformKeyboardEvent.h */,
                                6593923509AE4346002C531F /* KURL.cpp */,
                                6593923609AE4346002C531F /* KURL.h */,
                                935207BD09BD410A00F2038D /* LocalizedStrings.h */,
                                A8239DFE09B3CF8A00B60641 /* Logging.cpp */,
                                A8239DFF09B3CF8A00B60641 /* Logging.h */,
                                65F5382109B2B55700F3DC4A /* make-charset-table.pl */,
-                               935C476709AC4D4300A6AAB4 /* PlatformMouseEvent.h */,
                                93032CC909AEC34B00F82A18 /* Path.h */,
                                BC6B7BBB0993611A0052867B /* PDFDocumentImage.h */,
                                BCC8D1710988301200140BF2 /* Pen.cpp */,
                                BCC8D1720988301200140BF2 /* Pen.h */,
+                               935C476609AC4D4300A6AAB4 /* PlatformKeyboardEvent.h */,
+                               935C476709AC4D4300A6AAB4 /* PlatformMouseEvent.h */,
                                93CD4FEB0995FD2A007ECC97 /* PlatformString.h */,
+                               935C476A09AC4D4F00A6AAB4 /* PlatformWheelEvent.h */,
                                A82398A509B3ACDB00B60641 /* PlugInInfoStore.h */,
-                               6582A13D09999CD600BEEB6D /* DeprecatedString.cpp */,
-                               6582A13E09999CD600BEEB6D /* DeprecatedString.h */,
-                               651B4D8309AC83370029F1EF /* DeprecatedStringList.cpp */,
-                               651B4D8409AC83370029F1EF /* DeprecatedStringList.h */,
                                9385F761098D9C3100D90D24 /* Screen.h */,
                                9353673E09AED79200D35CD6 /* ScrollBarMode.h */,
                                BC6D6E2509AF943500F59759 /* ScrollView.h */,
                                657BD74909AFDC54005A2056 /* StreamingTextDecoder.cpp */,
                                657BD74A09AFDC54005A2056 /* StreamingTextDecoder.h */,
                                93CD4FDA0995F9EA007ECC97 /* String.cpp */,
+                               93126F6009D7A736008D9626 /* StringHash.h */,
                                93CD4FDC0995F9EA007ECC97 /* StringImpl.cpp */,
                                93CD4FDD0995F9EA007ECC97 /* StringImpl.h */,
                                93E62D990985F41600E1B5E3 /* SystemTime.h */,
                                6545F66D09B82FED0013006F /* TransferJob.h */,
                                6545F66E09B82FED0013006F /* TransferJobClient.h */,
                                6545F66F09B82FED0013006F /* TransferJobInternal.h */,
-                               935C476A09AC4D4F00A6AAB4 /* PlatformWheelEvent.h */,
                                9380F47109A11AB4001FDB34 /* Widget.cpp */,
                                9380F47209A11AB4001FDB34 /* Widget.h */,
                                93B780C909B3B7FE00690162 /* WidgetClient.h */,
                                65DF323A09D1DE65000BE325 /* JSCanvasGradient.h in Headers */,
                                65DF323C09D1DE65000BE325 /* JSCanvasPattern.h in Headers */,
                                65DF323E09D1DE65000BE325 /* JSCanvasRenderingContext2D.h in Headers */,
+                               93126F6109D7A736008D9626 /* StringHash.h in Headers */,
                                D086FE9809D53AAB005BC74D /* UnlinkCommand.h in Headers */,
                                A8C4A7FD09D563270003AC8D /* StyledElement.h in Headers */,
                                A8C4A7FF09D563270003AC8D /* Node.h in Headers */,
                        buildRules = (
                        );
                        buildSettings = {
-                               CREATE_HASH_TABLE = /System/Library/Frameworks/WebKit.framework/Versions/A/Frameworks/JavaScriptCore.framework/PrivateHeaders/create_hash_table;
                                DEBUG_DEFINES = NDEBUG;
                                DYLIB_COMPATIBILITY_VERSION = 1;
                                DYLIB_CURRENT_VERSION = 1;
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                        shellPath = /bin/sh;
+<<<<<<< .mine
+                       shellScript = "if [ \"${BUILD_STYLE}\" = \"Release\" -o \"${BUILD_STYLE}\" = \"Debug\" ] ; then\n    export CREATE_HASH_TABLE=\"${BUILT_PRODUCTS_DIR}/JavaScriptCore.framework/PrivateHeaders/create_hash_table\"\nelse\n    export CREATE_HASH_TABLE=\"${NEXT_ROOT}${SYSTEM_LIBRARY_DIR}/Frameworks/WebKit.framework/Versions/A/Frameworks/JavaScriptCore.framework/PrivateHeaders/create_hash_table\"\nfi\n./generate-derived-sources\n";
+=======
                        shellScript = "if [ \"${BUILD_STYLE}\" = \"Release\" -o \"${BUILD_STYLE}\" = \"Debug\" ] ; then\n    export CREATE_HASH_TABLE=\"${BUILT_PRODUCTS_DIR}/JavaScriptCore.framework/PrivateHeaders/create_hash_table\"\nelse\n    export CREATE_HASH_TABLE=\"${NEXT_ROOT}${SYSTEM_LIBRARY_DIR}/Frameworks/WebKit.framework/Versions/A/Frameworks/JavaScriptCore.framework/PrivateHeaders/create_hash_table\"\nfi\n\nmkdir -p \"${BUILT_PRODUCTS_DIR}/DerivedSources/WebCore\"\ncd \"${BUILT_PRODUCTS_DIR}/DerivedSources/WebCore\"\n\nexport WebCore=\"${SRCROOT}\"\n\nexport ENCODINGS_FILE=\"${WebCore}/platform/mac/mac-encodings.txt\"\nexport ENCODINGS_PREFIX=\"kCFStringEncoding\"\n\nmake -f \"$WebCore/DerivedSources.make\"\n";
+>>>>>>> .r13702
                };
 /* End PBXShellScriptBuildPhase section */
 
                149C283A08902B11008A9EFC /* Debug */ = {
                        isa = XCBuildConfiguration;
                        buildSettings = {
-                               CREATE_HASH_TABLE = "$(BUILT_PRODUCTS_DIR)/JavaScriptCore.framework/PrivateHeaders/create_hash_table";
                                DEBUG_DEFINES = "";
                                DYLIB_COMPATIBILITY_VERSION = 1;
                                DYLIB_CURRENT_VERSION = 1;
                149C283B08902B11008A9EFC /* Release */ = {
                        isa = XCBuildConfiguration;
                        buildSettings = {
-                               CREATE_HASH_TABLE = "$(BUILT_PRODUCTS_DIR)/JavaScriptCore.framework/PrivateHeaders/create_hash_table";
                                DEBUG_DEFINES = NDEBUG;
                                DYLIB_COMPATIBILITY_VERSION = 1;
                                DYLIB_CURRENT_VERSION = 1;
                149C283D08902B11008A9EFC /* Production */ = {
                        isa = XCBuildConfiguration;
                        buildSettings = {
-                               CREATE_HASH_TABLE = "$(NEXT_ROOT)$(SYSTEM_LIBRARY_DIR)/Frameworks/WebKit.framework/Versions/A/Frameworks/JavaScriptCore.framework/PrivateHeaders/create_hash_table";
                                DEBUG_DEFINES = NDEBUG;
                                DYLIB_COMPATIBILITY_VERSION = 1;
                                DYLIB_CURRENT_VERSION = 1;
                DD041FC209D9DDDC0010AF2A /* Debug */ = {
                        isa = XCBuildConfiguration;
                        buildSettings = {
-                               COPY_PHASE_STRIP = NO;
-                               GCC_DYNAMIC_NO_PIC = NO;
-                               GCC_GENERATE_DEBUGGING_SYMBOLS = YES;
-                               GCC_OPTIMIZATION_LEVEL = 0;
                                PRODUCT_NAME = "Derived Sources";
                        };
                        name = Debug;
                DD041FC309D9DDDC0010AF2A /* Release */ = {
                        isa = XCBuildConfiguration;
                        buildSettings = {
-                               COPY_PHASE_STRIP = YES;
-                               GCC_ENABLE_FIX_AND_CONTINUE = NO;
-                               GCC_GENERATE_DEBUGGING_SYMBOLS = NO;
                                PRODUCT_NAME = "Derived Sources";
-                               ZERO_LINK = NO;
                        };
                        name = Release;
                };
index 89650e4c8e99b07dba25016c1d55127183248955..56116bccf4f1332915d23aed6717f606739a7c8d 100644 (file)
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  */
 
-#ifndef MacFrame_H
-#define MacFrame_H
-
-#include "Frame.h"
-#include "IntRect.h"
-#include "ClipboardMac.h"
-#include "KWQScrollBar.h"
-#include "PlatformMouseEvent.h"
-#include "Node.h"
-#include "WebCoreKeyboardAccess.h"
-#include "TextAffinity.h"
-#include <kxmlcore/HashSet.h>
-
+#ifndef FrameMac_h
+#define FrameMac_h
+
+#import "ClipboardMac.h"
+#import "Frame.h"
+#import "IntRect.h"
+#import "KWQScrollBar.h"
+#import "Node.h"
+#import "PlatformMouseEvent.h"
+#import "StringHash.h"
+#import "TextAffinity.h"
+#import "WebCoreKeyboardAccess.h"
 #import <CoreFoundation/CoreFoundation.h>
+#import <kxmlcore/HashSet.h>
 
 class NPObject;
 
index 142b4d701d2d6eab5f88365aa0d45af71b4c5398..4db3494e52d1526d146e896713ba7db97ec41a61 100644 (file)
 #import "config.h"
 #import "FrameMac.h"
 
+#import "AccessibilityObjectCache.h"
+#import "BlockExceptions.h"
 #import "BrowserExtensionMac.h"
+#import "CSSComputedStyleDeclaration.h"
 #import "Cache.h"
+#import "ClipboardMac.h"
 #import "Cursor.h"
 #import "DOMInternal.h"
 #import "EventNames.h"
 #import "FramePrivate.h"
 #import "FrameView.h"
 #import "GraphicsContext.h"
+#import "HTMLDocument.h"
 #import "HTMLFormElement.h"
 #import "HTMLGenericFormElement.h"
 #import "InlineTextBox.h"
-#import "AccessibilityObjectCache.h"
-#import "ClipboardMac.h"
 #import "KWQEditCommand.h"
-#import "BlockExceptions.h"
 #import "KWQFormData.h"
-#import "TransferJob.h"
-#import "Logging.h"
 #import "KWQPageState.h"
-#import "RegularExpression.h"
 #import "KWQScrollBar.h"
-#import "TextEncoding.h"
+#import "Logging.h"
+#import "MouseEventWithHitTestResults.h"
 #import "PlatformKeyboardEvent.h"
 #import "PlatformMouseEvent.h"
-#import "MouseEventWithHitTestResults.h"
+#import "PlatformWheelEvent.h"
 #import "Plugin.h"
+#import "Position.h"
+#import "Range.h"
+#import "RegularExpression.h"
+#import "RenderCanvas.h"
+#import "RenderImage.h"
 #import "RenderTableCell.h"
+#import "RenderTheme.h"
 #import "SelectionController.h"
+#import "TextEncoding.h"
+#import "TextIterator.h"
+#import "TransferJob.h"
 #import "VisiblePosition.h"
 #import "WebCoreFrameBridge.h"
 #import "WebCoreGraphicsBridge.h"
 #import "WebCoreViewFactory.h"
 #import "WebDashboardRegion.h"
-#import "PlatformWheelEvent.h"
-#import "CSSComputedStyleDeclaration.h"
 #import "csshelper.h"
 #import "dom2_eventsimpl.h"
-#import "Range.h"
-#import "Position.h"
-#import "HTMLDocument.h"
 #import "html_tableimpl.h"
 #import "kjs_binding.h"
 #import "kjs_window.h"
-#import "RenderCanvas.h"
 #import "render_frames.h"
-#import "RenderImage.h"
 #import "render_list.h"
 #import "render_style.h"
-#import "RenderTheme.h"
-#import "TextIterator.h"
 #import "visible_units.h"
 #import <JavaScriptCore/NP_jsobject.h>
 #import <JavaScriptCore/WebScriptObjectPrivate.h>
index 4d7123ecff1d9a7b80255789b2032e49f3a9ec46..634c102eae31f77a078805107542fb3c89f5d624 100644 (file)
 #include "ContainerNode.h"
 #include "DocumentMarker.h"
 #include "Shared.h"
+#include "StringHash.h"
 #include "Timer.h"
 #include "decoder.h"
 #include "dom2_traversalimpl.h"
+#include <DeprecatedStringList.h>
 #include <KURL.h>
 #include <kxmlcore/HashCountedSet.h>
 #include <kxmlcore/HashMap.h>
 #include <qptrlist.h>
-#include <DeprecatedStringList.h>
 
 class RenderArena;
 
index d8afa236036e08ba95ce4219e94df5e573849f71..b28b712c74f054be626acb85b4a4776afd49d705 100644 (file)
@@ -105,7 +105,7 @@ int NodeImplCounter::count = 0;
 static NodeImplCounter nodeImplCounter;
 
 int gEventDispatchForbidden = 0;
-#endif NDEBUG
+#endif
 
 Node::Node(Document *doc)
     : m_document(doc),
index 6c981170b79ec5b3077904c535b38f964a337ba0..d919023c1fab0f7fa84a814e49d956f293ae4da9 100644 (file)
  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  * Boston, MA 02111-1307, USA.
  */
+
 #include "config.h"
 #include "StyledElement.h"
 
-#include "css_stylesheetimpl.h"
-#include "css_valueimpl.h"
 #include "CSSValueKeywords.h"
 #include "Document.h"
 #include "HTMLNames.h"
+#include "css_stylesheetimpl.h"
+#include "css_valueimpl.h"
+#include <kxmlcore/HashTraits.h>
 
 namespace WebCore {
 
@@ -39,19 +41,17 @@ struct MappedAttributeKey {
     uint16_t type;
     StringImpl* name;
     StringImpl* value;
-    MappedAttributeKey(MappedAttributeEntry t, StringImpl* n, StringImpl* v)
+    MappedAttributeKey(MappedAttributeEntry t = eNone, StringImpl* n = 0, StringImpl* v = 0)
         : type(t), name(n), value(v) { }
 };
 
 static inline bool operator==(const MappedAttributeKey& a, const MappedAttributeKey& b)
     { return a.type == b.type && a.name == b.name && a.value == b.value; } 
 
-struct MappedAttributeKeyTraits {
-    typedef MappedAttributeKey TraitType;
+struct MappedAttributeKeyTraits : KXMLCore::GenericHashTraits<MappedAttributeKey> {
     static const bool emptyValueIsZero = true;
     static const bool needsDestruction = false;
-    static MappedAttributeKey emptyValue() { return MappedAttributeKey(eNone, 0, 0); }
-    static MappedAttributeKey deletedValue() { return MappedAttributeKey(eLastEntry, 0, 0); }
+    static MappedAttributeKey deletedValue() { return eLastEntry; }
 };
 
 struct MappedAttributeHash {
index 590c00a984caa04336eecd4dd680ced298f00f2e..ba2ca696cf4446b9a0d467574950a36b851f77be 100644 (file)
@@ -24,7 +24,7 @@
 #ifndef XML_Tokenizer_h_
 #define XML_Tokenizer_h_
 
-#include "PlatformString.h"
+#include "StringHash.h"
 #include <kxmlcore/HashMap.h>
 
 namespace WebCore {
index 648326a8ad100046c3ade6e90473290a5cc4f629..4471543cf96feb59438c9193042a10562b4e92d2 100644 (file)
 
 #ifdef KHTML_XSLT
 
-#include "XSLTProcessor.h"
-#include "XSLStyleSheet.h"
-#include "xml_tokenizer.h"
-#include "Text.h"
-#include "HTMLTokenizer.h"
-#include "HTMLDocument.h"
-#include "DOMImplementation.h"
-#include "loader.h"
 #include "Cache.h"
+#include "DOMImplementation.h"
 #include "DocLoader.h"
-#include "markup.h"
-#include "FrameView.h"
 #include "Frame.h"
+#include "FrameView.h"
+#include "HTMLDocument.h"
+#include "HTMLTokenizer.h"
 #include "KWQLoader.h"
-
+#include "Text.h"
 #include "TransferJob.h"
-
-#include <libxslt/xsltutils.h>
+#include "XSLStyleSheet.h"
+#include "XSLTProcessor.h"
+#include "loader.h"
+#include "markup.h"
+#include "xml_tokenizer.h"
+#include <kxmlcore/Assertions.h>
 #include <libxslt/documents.h>
 #include <libxslt/imports.h>
-
-#include <kxmlcore/Assertions.h>
-
-using namespace WebCore;
-using namespace WebCore;
+#include <libxslt/xsltutils.h>
 
 namespace WebCore {
 
index 4d6753af233a6a9b5c899e9ff446ceb0d6df8ede..3c24395bbf30a9eb27133f93ebf122cf01f2b255 100644 (file)
  *
  */
 
-#ifndef _xslt_processorimpl_h_
-#define _xslt_processorimpl_h_
+#ifndef xslt_processorimpl_h_
+#define xslt_processorimpl_h_
 
 #ifdef KHTML_XSLT
 
 #include "Shared.h"
-#include "StringImpl.h"
+#include "StringHash.h"
 #include "XSLStyleSheet.h"
+#include <DeprecatedString.h>
+#include <kxmlcore/HashMap.h>
 #include <libxml/parser.h>
 #include <libxml/parserInternals.h>
 #include <libxslt/documents.h>
 #include <libxslt/transform.h>
-#include <DeprecatedString.h>
-
-#include <kxmlcore/HashMap.h>
 
 namespace WebCore {
 
index c748aeffe12b8123979de9dcf482443b2bd75a81..c83cb39e85bc2e98cb392525fd5ae136a52e7c62 100644 (file)
@@ -75,7 +75,7 @@ namespace WebCore {
         AXID getAXID(WebCoreAXObject*);
 
         HashMap<RenderObject*, WebCoreAXObject*> m_objects;
-        HashSet<AXID, PtrHash<AXID>, AXIDHashTraits> m_idsInUse;
+        HashSet<AXID, IntHash<AXID>, AXIDHashTraits> m_idsInUse;
     };
 
 #ifndef __APPLE__
index 567bc7ffb8a61c7f24a1f55f283084632b4dbd2b..1049fde86fceb9ca56578ff64c41f858ddfcabc1 100644 (file)
@@ -23,7 +23,7 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  */
 
-#include "PlatformString.h"
+#include "StringHash.h"
 #include "Widget.h"
 #include <kxmlcore/HashMap.h>
 
index 04459269114c27219a9048d4f02c450b4f28c9fc..abc1e898abe86838a48f60e41d686df1ef623d4d 100644 (file)
 #include "CachedXSLStyleSheet.h"
 #include "DocLoader.h"
 #include "Document.h"
-#include "loader.h"
-#include "TransferJob.h"
+#include "Image.h"
 #include "TransferJob.h"
+#include "loader.h"
 #include <kxmlcore/Assertions.h>
-#include "Image.h"
-
-using namespace WebCore;
 
 namespace WebCore {
 
index 89613875b1f85e151fd27c73ab4105c655e17171..1986bd5b75900f7ff2a0fb4e88a6d6f2bf731624 100644 (file)
@@ -31,6 +31,7 @@
 #include "Frame.h"
 #include "FrameTree.h"
 #include "SelectionController.h"
+#include "StringHash.h"
 #include "Timer.h"
 #include "css_valueimpl.h"
 #include "kjs_proxy.h"
index b60bfe77fe78125d50405d3011ec5ef7282cbe7f..74f438e4487bb632d820635386b6110939f56c03 100644 (file)
@@ -24,6 +24,7 @@
 #include "Color.h"
 #include "Frame.h"
 #include "FrameTree.h"
+#include "StringHash.h"
 #include <kjs/collector.h>
 #include <kjs/JSLock.h>
 #include <kxmlcore/HashMap.h>
index 92154775cb79efcd84d687e2a9fec204b1f4e54f..80f2b754352cf2805158ca9c224b8efc927ede0f 100644 (file)
@@ -29,6 +29,7 @@
 #include "AtomicString.h"
 
 #include "StaticConstructors.h"
+#include "StringHash.h"
 #include <kjs/identifier.h>
 #include <kxmlcore/HashSet.h>
 
index 962b16281a6d7fdadeee15afce9f948c732c2d36..387cbda1eb6fcb86244d93b09c32dd6f8158880f 100644 (file)
@@ -125,14 +125,4 @@ inline bool equalIgnoringCase(const String& a, const AtomicString& b) { return e
 
 }
 
-namespace KXMLCore {
-
-    template<typename T> class StrHash;
-
-    template<> struct StrHash<WebCore::AtomicStringImpl*> : public StrHash<WebCore::StringImpl*>
-    {
-    };
-
-}
-
 #endif
index 5d4c5a87a15491fd59dbfae25b2d9e92afcef9b7..ba2cf37537a4d174f9a9b4056c4448a04db0a14f 100644 (file)
 #include <unicode/ucnv.h>
 #include <unicode/utypes.h>
 
+using namespace KXMLCore;
+using namespace WebCore;
+
+namespace WebCore {
+
+struct TextEncodingIDHashTraits : GenericHashTraits<TextEncodingID> {
+    static TraitType deletedValue() { return InvalidEncoding; }
+};
+
+}
+
 namespace KXMLCore {
 
-    template<> struct DefaultHash<WebCore::TextEncodingID> {
-        typedef PtrHash<WebCore::TextEncodingID> Hash;
-    };
+template<> struct HashKeyStorageTraits<IntHash<TextEncodingID>, TextEncodingIDHashTraits> {
+    typedef IntTypes<sizeof(TextEncodingID)>::SignedType IntType;
+    typedef IntHash<IntType> Hash;
+    typedef HashTraits<IntType> Traits;
+};
 
-    template<> struct HashTraits<WebCore::TextEncodingID> : GenericHashTraits<WebCore::TextEncodingID> {
-        static TraitType deletedValue() { return WebCore::InvalidEncoding; }
-    };
-    
-} // namespace KXMLCore
+}
 
 namespace WebCore {
 
@@ -99,13 +108,16 @@ struct EncodingHash {
     }
 };
 
-static HashMap<const char*, const CharsetEntry*, EncodingHash>* nameMap;
-static HashMap<TextEncodingID, const CharsetEntry*>* encodingMap;
+typedef HashMap<const char*, const CharsetEntry*, EncodingHash> NameMap;
+typedef HashMap<TextEncodingID, const CharsetEntry*, IntHash<TextEncodingID>, TextEncodingIDHashTraits> EncodingMap;
+
+static NameMap* nameMap;
+static EncodingMap* encodingMap;
 
 static void buildDictionaries()
 {
-    nameMap = new HashMap<const char*, const CharsetEntry*, EncodingHash>();
-    encodingMap = new HashMap<TextEncodingID, const CharsetEntry*>();
+    nameMap = new NameMap;
+    encodingMap = new EncodingMap;
 
     for (int i = 0; CharsetTable[i].name; ++i) {
         nameMap->add(CharsetTable[i].name, &CharsetTable[i]);
index 5c893ce4ad6224868e7a96e6ba8bcae2552d47f4..c272685f88aa8c116f7a574ea115089a2628a789 100644 (file)
@@ -169,23 +169,13 @@ inline bool operator!=(const DeprecatedString& b, const String& a ) { return !(a
 
 namespace KXMLCore {
 
-    template<> struct StrHash<WebCore::String> {
-        static unsigned hash(const WebCore::String& key) { return key.impl()->hash(); }
-        static bool equal(const WebCore::String& a, const WebCore::String& b)
-            { return StrHash<WebCore::StringImpl*>::equal(a.impl(), b.impl()); }
-    };
-    
+    // StrHash is the default hash for String
+    template<typename T> struct DefaultHash;
+    template<typename T> struct StrHash;
     template<> struct DefaultHash<WebCore::String> {
         typedef StrHash<WebCore::String> Hash;
     };
 
-    template<> struct HashTraits<WebCore::String> {
-        typedef WebCore::String TraitType;
-        static const bool emptyValueIsZero = true;
-        static const bool needsDestruction = true;
-        static TraitType emptyValue() { return TraitType(); }
-        static TraitType deletedValue() { return HashTraits<RefPtr<WebCore::StringImpl> >::_deleted.get(); }
-    };
 }
 
 #endif
diff --git a/WebCore/platform/StringHash.h b/WebCore/platform/StringHash.h
new file mode 100644 (file)
index 0000000..b5b45fa
--- /dev/null
@@ -0,0 +1,216 @@
+/*
+ * Copyright (C) 2006 Apple Computer, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ *
+ */
+
+#ifndef StringHash_h
+#define StringHash_h
+
+#include "AtomicStringImpl.h"
+#include "PlatformString.h"
+#include <kxmlcore/HashTraits.h>
+
+namespace KXMLCore {
+
+    template<typename T> struct StrHash;
+
+    template<> struct StrHash<WebCore::StringImpl*> {
+        static unsigned hash(const WebCore::StringImpl* key) { return key->hash(); }
+        static bool equal(const WebCore::StringImpl* a, const WebCore::StringImpl* b)
+        {
+            if (a == b)
+                return true;
+            if (!a || !b)
+                return false;
+
+            unsigned aLength = a->length();
+            unsigned bLength = b->length();
+            if (aLength != bLength)
+                return false;
+
+            const uint32_t* aChars = reinterpret_cast<const uint32_t*>(a->unicode());
+            const uint32_t* bChars = reinterpret_cast<const uint32_t*>(b->unicode());
+
+            unsigned halfLength = aLength >> 1;
+            for (unsigned i = 0; i != halfLength; ++i)
+                if (*aChars++ != *bChars++)
+                    return false;
+
+            if (aLength & 1 && *reinterpret_cast<const uint16_t*>(aChars) != *reinterpret_cast<const uint16_t*>(bChars))
+                return false;
+
+            return true;
+        }
+    };
+    
+    class CaseInsensitiveHash {
+    private:
+        // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
+        static const unsigned PHI = 0x9e3779b9U;
+    public:
+        // Paul Hsieh's SuperFastHash
+        // http://www.azillionmonkeys.com/qed/hash.html
+        static unsigned hash(const WebCore::StringImpl* str)
+        {
+            unsigned l = str->length();
+            const QChar* s = str->unicode();
+            uint32_t hash = PHI;
+            uint32_t tmp;
+            
+            int rem = l & 1;
+            l >>= 1;
+            
+            // Main loop
+            for (; l > 0; l--) {
+                hash += s[0].lower().unicode();
+                tmp = (s[1].lower().unicode() << 11) ^ hash;
+                hash = (hash << 16) ^ tmp;
+                s += 2;
+                hash += hash >> 11;
+            }
+            
+            // Handle end case
+            if (rem) {
+                hash += s[0].lower().unicode();
+                hash ^= hash << 11;
+                hash += hash >> 17;
+            }
+            
+            // Force "avalanching" of final 127 bits
+            hash ^= hash << 3;
+            hash += hash >> 5;
+            hash ^= hash << 2;
+            hash += hash >> 15;
+            hash ^= hash << 10;
+            
+            // this avoids ever returning a hash code of 0, since that is used to
+            // signal "hash not computed yet", using a value that is likely to be
+            // effectively the same as 0 when the low bits are masked
+            if (hash == 0)
+                hash = 0x80000000;
+            
+            return hash;
+        }
+        
+        static unsigned hash(const char* str, unsigned length)
+        {
+            // This hash is designed to work on 16-bit chunks at a time. But since the normal case
+            // (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
+            // were 16-bit chunks, which will give matching results.
+
+            unsigned l = length;
+            const char* s = str;
+            uint32_t hash = PHI;
+            uint32_t tmp;
+            
+            int rem = l & 1;
+            l >>= 1;
+            
+            // Main loop
+            for (; l > 0; l--) {
+                hash += QChar(s[0]).lower().unicode();
+                tmp = (QChar(s[1]).lower().unicode() << 11) ^ hash;
+                hash = (hash << 16) ^ tmp;
+                s += 2;
+                hash += hash >> 11;
+            }
+            
+            // Handle end case
+            if (rem) {
+                hash += QChar(s[0]).lower().unicode();
+                hash ^= hash << 11;
+                hash += hash >> 17;
+            }
+            
+            // Force "avalanching" of final 127 bits
+            hash ^= hash << 3;
+            hash += hash >> 5;
+            hash ^= hash << 2;
+            hash += hash >> 15;
+            hash ^= hash << 10;
+            
+            // this avoids ever returning a hash code of 0, since that is used to
+            // signal "hash not computed yet", using a value that is likely to be
+            // effectively the same as 0 when the low bits are masked
+            if (hash == 0)
+                hash = 0x80000000;
+            
+            return hash;
+        }
+        
+        static bool equal(const WebCore::StringImpl* a, const WebCore::StringImpl* b)
+        {
+            if (a == b) return true;
+            if (!a || !b) return false;
+            unsigned length = a->length();
+            if (length != b->length())
+                return false;
+            const QChar* as = a->unicode();
+            const QChar* bs = b->unicode();
+            for (unsigned i = 0; i != length; ++i)
+                if (as[i].lower() != bs[i].lower())
+                    return false;
+            return true;
+        }
+    };
+
+    template<> struct StrHash<WebCore::AtomicStringImpl*> : public StrHash<WebCore::StringImpl*> {
+    };
+
+    template<> struct StrHash<RefPtr<WebCore::StringImpl> > {
+        static unsigned hash(const RefPtr<WebCore::StringImpl>& key) { return key->hash(); }
+        static bool equal(const RefPtr<WebCore::StringImpl>& a, const RefPtr<WebCore::StringImpl>& b)
+        {
+            return StrHash<WebCore::StringImpl*>::equal(a.get(), b.get());
+        }
+    };
+
+    template<> struct StrHash<WebCore::String> {
+        static unsigned hash(const WebCore::String& key) { return key.impl()->hash(); }
+        static bool equal(const WebCore::String& a, const WebCore::String& b)
+        {
+            return StrHash<WebCore::StringImpl*>::equal(a.impl(), b.impl());
+        }
+    };
+
+    // store WebCore::String as StringImpl*
+
+    template<> struct HashTraits<WebCore::String> : GenericHashTraits<WebCore::String> {
+        typedef HashTraits<WebCore::StringImpl*>::StorageTraits StorageTraits;
+        static const bool emptyValueIsZero = true;
+        static const bool needsRef = true;
+        static void ref(const WebCore::String& s) { if (s.impl()) s.impl()->ref(); }
+        static void deref(const WebCore::String& s) { if (s.impl()) s.impl()->deref(); }
+    };
+
+    // share code between StringImpl*, RefPtr<StringImpl>, and String
+
+    template<> struct HashKeyStorageTraits<StrHash<RefPtr<WebCore::StringImpl> >, HashTraits<RefPtr<WebCore::StringImpl> > > {
+        typedef StrHash<WebCore::StringImpl*> Hash;
+        typedef HashTraits<WebCore::StringImpl*> Traits;
+    };
+    template<> struct HashKeyStorageTraits<StrHash<WebCore::String>, HashTraits<WebCore::String> > {
+        typedef StrHash<WebCore::StringImpl*> Hash;
+        typedef HashTraits<WebCore::StringImpl*> Traits;
+    };
+
+}
+
+using KXMLCore::CaseInsensitiveHash;
+
+#endif
index 1f56d54de5aa4d07738544c823ed49d474205efb..2951dfa71fe4716ffca8e1c12a5347f5ed03decb 100644 (file)
@@ -29,6 +29,7 @@
 
 #include "AtomicString.h"
 #include "Length.h"
+#include "StringHash.h"
 #include <kjs/identifier.h>
 #include <kxmlcore/Assertions.h>
 #include <string.h>
@@ -876,9 +877,3 @@ StringImpl::StringImpl(const UString& str)
 }
 
 } // namespace WebCore
-
-namespace KXMLCore {
-
-const RefPtr<WebCore::StringImpl> HashTraits<RefPtr<WebCore::StringImpl> >::_deleted = new WebCore::StringImpl(static_cast<char*>(0), 0);
-
-}
index acbd046f078bb32d3f2cb468aa4ff28c3307c9c7..9c5f312aed0bebba64b6f0439a53fa82d473cf83 100644 (file)
@@ -45,7 +45,7 @@ struct QCharBufferTranslator;
 struct CStringTranslator;
 struct Length;
 
-class StringImpl : public Shared<StringImpl>
+class StringImpl : public Shared<StringImpl>, Noncopyable
 {
 private:
     struct WithOneRef { };
@@ -115,27 +115,25 @@ public:
     // For debugging only, leaks memory.
     const char* ascii() const;
 
+#if __APPLE__
+    StringImpl(CFStringRef);
+    CFStringRef createCFString() const;
+#endif
+#if __OBJC__
+    StringImpl(NSString*);
+    operator NSString*() const;
+#endif
+
 private:
     unsigned m_length;
     QChar* m_data;
 
-private:
     friend class AtomicString;
     friend struct QCharBufferTranslator;
     friend struct CStringTranslator;
     
     mutable unsigned m_hash;
     bool m_inTable;
-
-public:
-#if __APPLE__
-    StringImpl(CFStringRef);
-    CFStringRef createCFString() const;
-#endif
-#if __OBJC__
-    StringImpl(NSString*);
-    operator NSString*() const;
-#endif
 };
 
 bool equal(const StringImpl*, const StringImpl*);
@@ -150,182 +148,16 @@ bool equalIgnoringCase(const char*, const StringImpl*);
 
 namespace KXMLCore {
 
-    template<typename T> class DefaultHash;
-    template<typename T> class StrHash;
-
-    template<> struct StrHash<WebCore::StringImpl*> {
-        static unsigned hash(const WebCore::StringImpl* key) { return key->hash(); }
-        static bool equal(const WebCore::StringImpl* a, const WebCore::StringImpl* b)
-        {
-            if (a == b) return true;
-            if (!a || !b) return false;
-            
-            unsigned aLength = a->length();
-            unsigned bLength = b->length();
-            if (aLength != bLength)
-                return false;
-            
-            const uint32_t* aChars = reinterpret_cast<const uint32_t*>(a->unicode());
-            const uint32_t* bChars = reinterpret_cast<const uint32_t*>(b->unicode());
-            
-            unsigned halfLength = aLength >> 1;
-            for (unsigned i = 0; i != halfLength; ++i)
-                if (*aChars++ != *bChars++)
-                    return false;
-            
-            if (aLength & 1 && *reinterpret_cast<const uint16_t*>(aChars) != *reinterpret_cast<const uint16_t*>(bChars))
-                return false;
-            
-            return true;
-        }
-    };
-    
-    class CaseInsensitiveHash {
-    private:
-        // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
-        static const unsigned PHI = 0x9e3779b9U;
-    public:
-        // Paul Hsieh's SuperFastHash
-        // http://www.azillionmonkeys.com/qed/hash.html
-        static unsigned hash(const WebCore::StringImpl* str)
-        {
-            unsigned m_length = str->length();
-            const QChar* m_data = str->unicode();
-            uint32_t hash = PHI;
-            uint32_t tmp;
-            
-            int rem = m_length & 1;
-            m_length >>= 1;
-            
-            // Main loop
-            for (; m_length > 0; m_length--) {
-                hash += m_data[0].lower().unicode();
-                tmp = (m_data[1].lower().unicode() << 11) ^ hash;
-                hash = (hash << 16) ^ tmp;
-                m_data += 2;
-                hash += hash >> 11;
-            }
-            
-            // Handle end case
-            if (rem) {
-                hash += m_data[0].lower().unicode();
-                hash ^= hash << 11;
-                hash += hash >> 17;
-            }
-            
-            // Force "avalanching" of final 127 bits
-            hash ^= hash << 3;
-            hash += hash >> 5;
-            hash ^= hash << 2;
-            hash += hash >> 15;
-            hash ^= hash << 10;
-            
-            // this avoids ever returning a hash code of 0, since that is used to
-            // signal "hash not computed yet", using a value that is likely to be
-            // effectively the same as 0 when the low bits are masked
-            if (hash == 0)
-                hash = 0x80000000;
-            
-            return hash;
-        }
-        
-        static unsigned hash(const char* str, unsigned length)
-        {
-            // This hash is designed to work on 16-bit chunks at a time. But since the normal case
-            // (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
-            // were 16-bit chunks, which will give matching results.
-
-            unsigned m_length = length;
-            const char* m_data = str;
-            uint32_t hash = PHI;
-            uint32_t tmp;
-            
-            int rem = m_length & 1;
-            m_length >>= 1;
-            
-            // Main loop
-            for (; m_length > 0; m_length--) {
-                hash += QChar(m_data[0]).lower().unicode();
-                tmp = (QChar(m_data[1]).lower().unicode() << 11) ^ hash;
-                hash = (hash << 16) ^ tmp;
-                m_data += 2;
-                hash += hash >> 11;
-            }
-            
-            // Handle end case
-            if (rem) {
-                hash += QChar(m_data[0]).lower().unicode();
-                hash ^= hash << 11;
-                hash += hash >> 17;
-            }
-            
-            // Force "avalanching" of final 127 bits
-            hash ^= hash << 3;
-            hash += hash >> 5;
-            hash ^= hash << 2;
-            hash += hash >> 15;
-            hash ^= hash << 10;
-            
-            // this avoids ever returning a hash code of 0, since that is used to
-            // signal "hash not computed yet", using a value that is likely to be
-            // effectively the same as 0 when the low bits are masked
-            if (hash == 0)
-                hash = 0x80000000;
-            
-            return hash;
-        }
-        
-        static bool equal(const WebCore::StringImpl* a, const WebCore::StringImpl* b)
-        {
-            if (a == b) return true;
-            if (!a || !b) return false;
-            unsigned length = a->length();
-            if (length != b->length())
-                return false;
-            const QChar* as = a->unicode();
-            const QChar* bs = b->unicode();
-            for (unsigned i = 0; i != length; ++i)
-                if (as[i].lower() != bs[i].lower())
-                    return false;
-            return true;
-        }
-    };
-
-    template<> struct StrHash<RefPtr<WebCore::StringImpl> > {
-        static unsigned hash(const RefPtr<WebCore::StringImpl>& key) 
-        { 
-            return StrHash<WebCore::StringImpl*>::hash(key.get());
-        }
-
-        static bool equal(const RefPtr<WebCore::StringImpl>& a, const RefPtr<WebCore::StringImpl>& b)
-        {
-            return StrHash<WebCore::StringImpl*>::equal(a.get(), b.get());
-        }
-    };
-
+    // StrHash is the default hash for StringImpl* and RefPtr<StringImpl>
+    template<typename T> struct DefaultHash;
+    template<typename T> struct StrHash;
     template<> struct DefaultHash<WebCore::StringImpl*> {
         typedef StrHash<WebCore::StringImpl*> Hash;
     };
-
     template<> struct DefaultHash<RefPtr<WebCore::StringImpl> > {
         typedef StrHash<RefPtr<WebCore::StringImpl> > Hash;
     };
-    
-    template <typename T> class HashTraits;
-
-    template<> struct HashTraits<RefPtr<WebCore::StringImpl> > {
-        typedef RefPtr<WebCore::StringImpl> TraitType;
-
-        static const bool emptyValueIsZero = true;
-        static const bool needsDestruction = true;
-        static const TraitType emptyValue() { return TraitType(); }
-
-        static const TraitType _deleted;
-        static const TraitType& deletedValue() { return _deleted; }
-    };
 
 }
 
-using KXMLCore::CaseInsensitiveHash;
-
 #endif
index e215000b66daedc930d49a9fb4e9ead6696609e2..4b142be3304783c2f7e6b834129056b7e3237c7d 100644 (file)
 #ifndef TransferJob_H_
 #define TransferJob_H_
 
-#include "PlatformString.h"
+#include "StringHash.h"
+#include "Timer.h"
 #include "TransferJobClient.h" // for PlatformResponse
 #include <kxmlcore/HashMap.h>
-#include "Timer.h"
 
 #ifdef WIN32
 typedef unsigned long DWORD;
index 21a34147be3c12da0724a9e733d559ed32a7288f..0112d80c8c3a259c800fd6cea437e03bf39584a4 100644 (file)
@@ -25,6 +25,7 @@
 #define render_applet_h
 
 #include "HTMLElement.h"
+#include "StringHash.h"
 #include "render_replaced.h"
 
 namespace WebCore {
index 66f910a76741a5b260800355b48abeea18a3b723..aaa5c3245876f33d186fa6d654142d10aec25b6f 100644 (file)
@@ -1,3 +1,10 @@
+2006-04-05  Darin Adler  <darin@apple.com>
+
+        Reviewed by Maciej.
+
+        * Scripts/check-for-global-initializers: Remove StringImpl from the list of files that
+        are allowed to have global initializers.
+
 2006-04-05  Geoffrey Garen  <ggaren@apple.com>
 
         Reviewed by OMG BETH
index 0787d3397cd0ecb0a7abdec489a316ec4e3b25eb..4209bfcf5f8a939281e7a61d2d16fd8b94db9742 100755 (executable)
@@ -90,9 +90,6 @@ for my $file (sort @files) {
         if ($target eq "JavaScriptCore") {
             next if $shortName eq "FastMalloc.o";
         }
-        if ($target eq "WebCore") {
-            next if $shortName eq "StringImpl.o";
-        }
 
         print "$shortName has a global initializer in it! ($file)\n";
         $sawError = 1;
index 2f478f01e4262e534528d3890e3054377843603b..de5ea5a1cda88475b6dbbdc6b53571c87240b22a 100755 (executable)
@@ -745,7 +745,9 @@ sub openHTTPDIfNeeded()
         }
     }
     
+    my $httpdPath = "/usr/sbin/httpd";
     my $httpdConfig = "$testDirectory/http/conf/httpd.conf";
+    $httpdConfig = "$testDirectory/http/conf/apache2-httpd.conf" if `$httpdPath -v` =~ m|Apache/2|;
     my $documentRoot = "$testDirectory/http/tests";
     my $typesConfig = "$testDirectory/http/conf/mime.types";
     my $listen = "127.0.0.1:$httpdPort";
@@ -753,24 +755,6 @@ sub openHTTPDIfNeeded()
 
     mkpath $absTestResultsDirectory;
 
-    my $httpdPath;
-    if (-x "/usr/sbin/httpd-1.3") {
-        $httpdPath = "/usr/sbin/httpd-1.3";
-        open CONFIG, $httpdConfig or die;
-        open CONFIGOUT, ">", "/tmp/WebKit/httpd.conf" or die;
-        while (<CONFIG>) {
-            s|/httpd/|/httpd-1.3/|g;
-            print CONFIGOUT;
-        }
-        close CONFIG;
-        close CONFIGOUT;
-        $httpdConfig = "/tmp/WebKit/httpd.conf";
-    } elsif (-x "/usr/sbin/httpd") {
-        $httpdPath = "/usr/sbin/httpd";
-    } else {
-        die "Can't locate the httpd binary";
-    }
-
     open2(\*HTTPDIN, \*HTTPDOUT, $httpdPath, 
         "-f", "$httpdConfig",
         "-C", "DocumentRoot \"$documentRoot\"",