2008-10-24 Simon Fraser <simon.fraser@apple.com>
authorsimon.fraser@apple.com <simon.fraser@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 24 Oct 2008 19:32:51 +0000 (19:32 +0000)
committersimon.fraser@apple.com <simon.fraser@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 24 Oct 2008 19:32:51 +0000 (19:32 +0000)
        Reviewed by Darin Adler

        https://bugs.webkit.org/show_bug.cgi?id=21818

        Add HashTraits for AtomicString so that AtomicString can be used as
        the key for a HashMap or HashSet.

        * GNUmakefile.am: add AtomicStringHash.h
        * WebCore.vcproj/WebCore.vcproj: add AtomicStringHash.h
        * WebCore.xcodeproj/project.pbxproj: add AtomicStringHash.h
        * platform/text/AtomicString.h:
        (WebCore::AtomicString::AtomicString):
        (WebCore::AtomicString::isHashTableDeletedValue):
            specialize DefaultHash for AtomicString to use AtomicStringHash
        * platform/text/AtomicStringHash.h: Added.
        * platform/text/StringImpl.cpp:
        (WebCore::StringImpl::StringImpl):
            compute the hash up-front for the empty string
        * platform/text/StringImpl.h:
        (WebCore::StringImpl::existingHash):
            method to get the hash without a test and branch, for callers like
            AtomicStringHash who can guarantee that the hash has already been computed.

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

WebCore/ChangeLog
WebCore/GNUmakefile.am
WebCore/WebCore.vcproj/WebCore.vcproj
WebCore/WebCore.xcodeproj/project.pbxproj
WebCore/platform/text/AtomicString.h
WebCore/platform/text/AtomicStringHash.h [new file with mode: 0644]
WebCore/platform/text/StringImpl.cpp
WebCore/platform/text/StringImpl.h

index 58c8dad..38692e2 100644 (file)
@@ -1,5 +1,30 @@
 2008-10-24  Simon Fraser  <simon.fraser@apple.com>
 
+        Reviewed by Darin Adler
+
+        https://bugs.webkit.org/show_bug.cgi?id=21818
+        
+        Add HashTraits for AtomicString so that AtomicString can be used as
+        the key for a HashMap or HashSet.
+
+        * GNUmakefile.am: add AtomicStringHash.h
+        * WebCore.vcproj/WebCore.vcproj: add AtomicStringHash.h
+        * WebCore.xcodeproj/project.pbxproj: add AtomicStringHash.h
+        * platform/text/AtomicString.h:
+        (WebCore::AtomicString::AtomicString):
+        (WebCore::AtomicString::isHashTableDeletedValue):
+            specialize DefaultHash for AtomicString to use AtomicStringHash
+        * platform/text/AtomicStringHash.h: Added.
+        * platform/text/StringImpl.cpp:
+        (WebCore::StringImpl::StringImpl):
+            compute the hash up-front for the empty string
+        * platform/text/StringImpl.h:
+        (WebCore::StringImpl::existingHash):
+            method to get the hash without a test and branch, for callers like
+            AtomicStringHash who can guarantee that the hash has already been computed.
+
+2008-10-24  Simon Fraser  <simon.fraser@apple.com>
+
         Reviewed by Sam Weinig
 
         https://bugs.webkit.org/show_bug.cgi?id=21857
index 4c8aef9..989e7be 100644 (file)
@@ -1400,6 +1400,7 @@ webcore_sources += \
        WebCore/platform/network/ResourceResponseBase.h \
        WebCore/platform/text/AtomicString.cpp \
        WebCore/platform/text/AtomicString.h \
+       WebCore/platform/text/AtomicStringHash.h \
        WebCore/platform/text/AtomicStringImpl.h \
        WebCore/platform/text/Base64.cpp \
        WebCore/platform/text/Base64.h \
index 59334d3..7b718db 100644 (file)
                                        >\r
                                </File>\r
                                <File\r
+                                       RelativePath="..\platform\text\AtomicStringHash.h"\r
+                                       >\r
+                               </File>\r
+                               <File\r
                                        RelativePath="..\platform\text\AtomicStringImpl.h"\r
                                        >\r
                                </File>\r
index b704bc0..4ed8b2e 100644 (file)
@@ -44,6 +44,7 @@
                0A4844990CA44CB200B7BD48 /* SoftLinking.h in Headers */ = {isa = PBXBuildFile; fileRef = 0A4844980CA44CB200B7BD48 /* SoftLinking.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F56028F0E4B76580065B038 /* RenderMarquee.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F56028D0E4B76580065B038 /* RenderMarquee.h */; };
                0F5602900E4B76580065B038 /* RenderMarquee.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F56028E0E4B76580065B038 /* RenderMarquee.cpp */; };
+               0FC705210EB1815600B90AD8 /* AtomicStringHash.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC705200EB1815600B90AD8 /* AtomicStringHash.h */; };
                1402645E0AFDC19B005919E2 /* LoggingMac.mm in Sources */ = {isa = PBXBuildFile; fileRef = 1402645D0AFDC19B005919E2 /* LoggingMac.mm */; };
                1403B99709EB13AF00797C7F /* DOMWindow.h in Headers */ = {isa = PBXBuildFile; fileRef = 1403B99509EB13AF00797C7F /* DOMWindow.h */; settings = {ATTRIBUTES = (Private, ); }; };
                1403B99809EB13AF00797C7F /* DOMWindow.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1403B99609EB13AF00797C7F /* DOMWindow.cpp */; };
                0A4844980CA44CB200B7BD48 /* SoftLinking.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SoftLinking.h; sourceTree = "<group>"; };
                0F56028D0E4B76580065B038 /* RenderMarquee.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RenderMarquee.h; sourceTree = "<group>"; };
                0F56028E0E4B76580065B038 /* RenderMarquee.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RenderMarquee.cpp; sourceTree = "<group>"; };
+               0FC705200EB1815600B90AD8 /* AtomicStringHash.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AtomicStringHash.h; sourceTree = "<group>"; };
                1402645D0AFDC19B005919E2 /* LoggingMac.mm */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.objcpp; path = LoggingMac.mm; sourceTree = "<group>"; };
                1403B90C09EB124500797C7F /* DOMWindow.idl */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = DOMWindow.idl; sourceTree = "<group>"; };
                1403B99509EB13AF00797C7F /* DOMWindow.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DOMWindow.h; sourceTree = "<group>"; };
                                B2C3D9F90D006C1D00EF6F26 /* mac */,
                                B2C3D9ED0D006C1D00EF6F26 /* AtomicString.cpp */,
                                B2C3D9EE0D006C1D00EF6F26 /* AtomicString.h */,
+                               0FC705200EB1815600B90AD8 /* AtomicStringHash.h */,
                                B2C3D9EF0D006C1D00EF6F26 /* AtomicStringImpl.h */,
                                B2C3D9F00D006C1D00EF6F26 /* Base64.cpp */,
                                B2C3D9F10D006C1D00EF6F26 /* Base64.h */,
                                BCFF64910EAD15C200C1D6F7 /* LengthBox.h in Headers */,
                                BCFF64920EAD15C200C1D6F7 /* LengthSize.h in Headers */,
                                E1C36C030EB076D6007410BC /* JSDOMGlobalObject.h in Headers */,
+                               0FC705210EB1815600B90AD8 /* AtomicStringHash.h in Headers */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
index af72c46..a19c8d0 100644 (file)
@@ -26,6 +26,8 @@
 
 namespace WebCore {
 
+struct AtomicStringHash;
+
 class AtomicString {
 public:
     static void init();
@@ -42,6 +44,10 @@ public:
     AtomicString(AtomicStringImpl* imp) : m_string(imp) { }
     AtomicString(const String& s) : m_string(add(s.impl())) { }
 
+    // Hash table deleted values, which are only constructed and never copied or destroyed.
+    AtomicString(WTF::HashTableDeletedValueType) : m_string(WTF::HashTableDeletedValue) { }
+    bool isHashTableDeletedValue() const { return m_string.isHashTableDeletedValue(); }
+
 #if USE(JSC)
     static AtomicStringImpl* find(const JSC::Identifier&);
 #endif
@@ -138,4 +144,15 @@ inline bool equalIgnoringCase(const String& a, const AtomicString& b) { return e
 
 } // namespace WebCore
 
+
+namespace WTF {
+
+    // AtomicStringHash is the default hash for AtomicString
+    template<typename T> struct DefaultHash;
+    template<> struct DefaultHash<WebCore::AtomicString> {
+        typedef WebCore::AtomicStringHash Hash;
+    };
+
+} // namespace WTF
+
 #endif // AtomicString_h
diff --git a/WebCore/platform/text/AtomicStringHash.h b/WebCore/platform/text/AtomicStringHash.h
new file mode 100644 (file)
index 0000000..67a45de
--- /dev/null
@@ -0,0 +1,64 @@
+/*
+ * Copyright (C) 2008 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1.  Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer. 
+ * 2.  Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution. 
+ * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
+ *     its contributors may be used to endorse or promote products derived
+ *     from this software without specific prior written permission. 
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef AtomicStringHash_h
+#define AtomicStringHash_h
+
+#include "AtomicString.h"
+#include <wtf/HashTraits.h>
+
+namespace WebCore {
+
+    struct AtomicStringHash {
+        static unsigned hash(const AtomicString& key)
+        {
+            return key.impl()->existingHash();
+        }
+
+        static bool equal(const AtomicString& a, const AtomicString& b)
+        {
+            return a == b;
+        }
+
+        static const bool safeToCompareToEmptyOrDeleted = false;
+    };
+
+}
+
+namespace WTF {
+
+    // WebCore::AtomicStringHash is the default hash for AtomicString
+    template<> struct HashTraits<WebCore::AtomicString> : GenericHashTraits<WebCore::AtomicString> {
+        static const bool emptyValueIsZero = true;
+        static void constructDeletedValue(WebCore::AtomicString& slot) { new (&slot) WebCore::AtomicString(HashTableDeletedValue); }
+        static bool isDeletedValue(const WebCore::AtomicString& slot) { return slot.isHashTableDeletedValue(); }
+    };
+
+}
+
+#endif
index 0fc8232..911c0dc 100644 (file)
@@ -60,6 +60,10 @@ StringImpl::StringImpl()
     , m_inTable(false)
     , m_hasTerminatingNullCharacter(false)
 {
+    // Ensure that the hash is computed so that AtomicStringHash can call existingHash()
+    // with impunity. The empty string is special because it is never entered into
+    // AtomicString's HashKey, but still needs to compare correctly.
+    hash();
 }
 
 // This is one of the most common constructors, but it's also used for the copy()
index cc8f815..57f64c8 100644 (file)
@@ -86,6 +86,7 @@ public:
     bool hasTerminatingNullCharacter() { return m_hasTerminatingNullCharacter; }
 
     unsigned hash() { if (m_hash == 0) m_hash = computeHash(m_data, m_length); return m_hash; }
+    unsigned existingHash() const { ASSERT(m_hash); return m_hash; }
     static unsigned computeHash(const UChar*, unsigned len);
     static unsigned computeHash(const char*);