Diff
Modified: trunk/Source/WTF/ChangeLog (188556 => 188557)
--- trunk/Source/WTF/ChangeLog 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WTF/ChangeLog 2015-08-17 23:59:05 UTC (rev 188557)
@@ -1,3 +1,22 @@
+2015-08-17 Myles C. Maxfield <mmaxfi...@apple.com>
+
+ Implement IntegerHasher
+ https://bugs.webkit.org/show_bug.cgi?id=147866
+
+ Reviewed by Darin Adler and Anders Carlsson.
+
+ Rename StringHasher.h to Hasher.h, and include an IntegerHasher class.
+
+ * WTF.vcxproj/WTF.vcxproj: Update to target new file.
+ * WTF.vcxproj/WTF.vcxproj.filters: Ditto.
+ * WTF.xcodeproj/project.pbxproj: Ditto.
+ * wtf/CMakeLists.txt: Ditto.
+ * wtf/Hasher.h: Renamed from Source/WTF/wtf/StringHasher.h.
+ * wtf/text/CString.cpp: Use new #include
+ * wtf/text/StringHash.h: Ditto.
+ * wtf/text/StringImpl.h: Ditto.
+ * wtf/unicode/UTF8.cpp: Ditto.
+
2015-08-17 Alex Christensen <achristen...@webkit.org>
Move some commands from ./CMakeLists.txt to Source/cmake
Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj (188556 => 188557)
--- trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-08-17 23:59:05 UTC (rev 188557)
@@ -216,6 +216,7 @@
<ClInclude Include="..\wtf\glib\GUniquePtr.h" />
<ClInclude Include="..\wtf\GregorianDateTime.h" />
<ClInclude Include="..\wtf\HashCountedSet.h" />
+ <ClInclude Include="..\wtf\Hasher.h" />
<ClInclude Include="..\wtf\HashFunctions.h" />
<ClInclude Include="..\wtf\HashIterators.h" />
<ClInclude Include="..\wtf\HashMap.h" />
@@ -276,7 +277,6 @@
<ClInclude Include="..\wtf\StdLibExtras.h" />
<ClInclude Include="..\wtf\Stopwatch.h" />
<ClInclude Include="..\wtf\StringExtras.h" />
- <ClInclude Include="..\wtf\StringHasher.h" />
<ClInclude Include="..\wtf\StringPrintStream.h" />
<ClInclude Include="..\wtf\TemporaryChange.h" />
<ClInclude Include="..\wtf\text\ASCIIFastPath.h" />
Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters (188556 => 188557)
--- trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters 2015-08-17 23:59:05 UTC (rev 188557)
@@ -463,6 +463,9 @@
<ClInclude Include="..\wtf\HashCountedSet.h">
<Filter>wtf</Filter>
</ClInclude>
+ <ClInclude Include="..\wtf\Hasher.h">
+ <Filter>wtf</Filter>
+ </ClInclude>
<ClInclude Include="..\wtf\HashFunctions.h">
<Filter>wtf</Filter>
</ClInclude>
@@ -622,9 +625,6 @@
<ClInclude Include="..\wtf\StringExtras.h">
<Filter>wtf</Filter>
</ClInclude>
- <ClInclude Include="..\wtf\StringHasher.h">
- <Filter>wtf</Filter>
- </ClInclude>
<ClInclude Include="..\wtf\StringPrintStream.h">
<Filter>wtf</Filter>
</ClInclude>
@@ -721,4 +721,4 @@
<None Include="WTFPostBuild.cmd" />
<None Include="WTFPreBuild.cmd" />
</ItemGroup>
-</Project>
\ No newline at end of file
+</Project>
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (188556 => 188557)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-08-17 23:59:05 UTC (rev 188557)
@@ -167,6 +167,7 @@
A8A473C9151A825B004123FF /* Functional.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A472A7151A825A004123FF /* Functional.h */; };
A8A473CA151A825B004123FF /* GetPtr.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A472A8151A825A004123FF /* GetPtr.h */; };
A8A473D3151A825B004123FF /* HashCountedSet.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A472B3151A825A004123FF /* HashCountedSet.h */; };
+ A8A4742D151A825B004123FF /* Hasher.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47314151A825B004123FF /* Hasher.h */; };
A8A473D4151A825B004123FF /* HashFunctions.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A472B4151A825A004123FF /* HashFunctions.h */; };
A8A473D5151A825B004123FF /* HashIterators.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A472B5151A825A004123FF /* HashIterators.h */; };
A8A473D6151A825B004123FF /* HashMap.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A472B6151A825A004123FF /* HashMap.h */; };
@@ -226,7 +227,6 @@
A8A47429151A825B004123FF /* StaticConstructors.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47310151A825B004123FF /* StaticConstructors.h */; };
A8A4742A151A825B004123FF /* StdLibExtras.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47311151A825B004123FF /* StdLibExtras.h */; };
A8A4742C151A825B004123FF /* StringExtras.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47313151A825B004123FF /* StringExtras.h */; };
- A8A4742D151A825B004123FF /* StringHasher.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47314151A825B004123FF /* StringHasher.h */; };
A8A47433151A825B004123FF /* TemporaryChange.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4731A151A825B004123FF /* TemporaryChange.h */; };
A8A47434151A825B004123FF /* ASCIIFastPath.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4731C151A825B004123FF /* ASCIIFastPath.h */; };
A8A47435151A825B004123FF /* AtomicString.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A8A4731D151A825B004123FF /* AtomicString.cpp */; };
@@ -465,6 +465,7 @@
A8A472A7151A825A004123FF /* Functional.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Functional.h; sourceTree = "<group>"; };
A8A472A8151A825A004123FF /* GetPtr.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = GetPtr.h; sourceTree = "<group>"; };
A8A472B3151A825A004123FF /* HashCountedSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HashCountedSet.h; sourceTree = "<group>"; };
+ A8A47314151A825B004123FF /* Hasher.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Hasher.h; sourceTree = "<group>"; };
A8A472B4151A825A004123FF /* HashFunctions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HashFunctions.h; sourceTree = "<group>"; };
A8A472B5151A825A004123FF /* HashIterators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HashIterators.h; sourceTree = "<group>"; };
A8A472B6151A825A004123FF /* HashMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HashMap.h; sourceTree = "<group>"; };
@@ -524,7 +525,6 @@
A8A47310151A825B004123FF /* StaticConstructors.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StaticConstructors.h; sourceTree = "<group>"; };
A8A47311151A825B004123FF /* StdLibExtras.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StdLibExtras.h; sourceTree = "<group>"; };
A8A47313151A825B004123FF /* StringExtras.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StringExtras.h; sourceTree = "<group>"; };
- A8A47314151A825B004123FF /* StringHasher.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StringHasher.h; sourceTree = "<group>"; };
A8A4731A151A825B004123FF /* TemporaryChange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TemporaryChange.h; sourceTree = "<group>"; };
A8A4731C151A825B004123FF /* ASCIIFastPath.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ASCIIFastPath.h; sourceTree = "<group>"; };
A8A4731D151A825B004123FF /* AtomicString.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AtomicString.cpp; sourceTree = "<group>"; };
@@ -768,6 +768,7 @@
2CCD892915C0390200285083 /* GregorianDateTime.cpp */,
2C05385315BC819000F21B96 /* GregorianDateTime.h */,
A8A472B3151A825A004123FF /* HashCountedSet.h */,
+ A8A47314151A825B004123FF /* Hasher.h */,
A8A472B4151A825A004123FF /* HashFunctions.h */,
A8A472B5151A825A004123FF /* HashIterators.h */,
A8A472B6151A825A004123FF /* HashMap.h */,
@@ -871,7 +872,6 @@
1A6BB768162F300500DD16DB /* StreamBuffer.h */,
A8A47313151A825B004123FF /* StringExtras.h */,
A748745117A0BDAE00FA04CB /* StringHashDumpContext.h */,
- A8A47314151A825B004123FF /* StringHasher.h */,
0FDDBFA51666DFA300C55FEF /* StringPrintStream.cpp */,
0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */,
A8A4731A151A825B004123FF /* TemporaryChange.h */,
@@ -1122,6 +1122,7 @@
A8A473CA151A825B004123FF /* GetPtr.h in Headers */,
2C05385415BC819000F21B96 /* GregorianDateTime.h in Headers */,
A8A473D3151A825B004123FF /* HashCountedSet.h in Headers */,
+ A8A4742D151A825B004123FF /* Hasher.h in Headers */,
A8A473D4151A825B004123FF /* HashFunctions.h in Headers */,
A8A473D5151A825B004123FF /* HashIterators.h in Headers */,
A8A473D6151A825B004123FF /* HashMap.h in Headers */,
@@ -1204,7 +1205,6 @@
A8A4743F151A825B004123FF /* StringHash.h in Headers */,
FE8225311B2A1E5B00BA68FD /* NakedPtr.h in Headers */,
A748745417A0BDAE00FA04CB /* StringHashDumpContext.h in Headers */,
- A8A4742D151A825B004123FF /* StringHasher.h in Headers */,
A8A47441151A825B004123FF /* StringImpl.h in Headers */,
A8A47442151A825B004123FF /* StringOperators.h in Headers */,
0FDDBFA81666DFA300C55FEF /* StringPrintStream.h in Headers */,
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (188556 => 188557)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2015-08-17 23:59:05 UTC (rev 188557)
@@ -31,6 +31,7 @@
GetPtr.h
GregorianDateTime.h
HashCountedSet.h
+ Hasher.h
HashFunctions.h
HashIterators.h
HashMap.h
@@ -90,7 +91,6 @@
StdLibExtras.h
Stopwatch.h
StringExtras.h
- StringHasher.h
StringPrintStream.h
ThreadIdentifierDataPthreads.h
ThreadSafeRefCounted.h
Copied: trunk/Source/WTF/wtf/Hasher.h (from rev 188553, trunk/Source/WTF/wtf/StringHasher.h) (0 => 188557)
--- trunk/Source/WTF/wtf/Hasher.h (rev 0)
+++ trunk/Source/WTF/wtf/Hasher.h 2015-08-17 23:59:05 UTC (rev 188557)
@@ -0,0 +1,314 @@
+/*
+ * Copyright (C) 2005, 2006, 2008, 2010, 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2010 Patrick Gansterer <par...@paroga.com>
+ *
+ * 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 WTF_Hasher_h
+#define WTF_Hasher_h
+
+#include <unicode/utypes.h>
+#include <wtf/text/LChar.h>
+
+namespace WTF {
+
+// Paul Hsieh's SuperFastHash
+// http://www.azillionmonkeys.com/qed/hash.html
+
+// LChar data is interpreted as Latin-1-encoded (zero extended to 16 bits).
+
+// NOTE: The hash computation here must stay in sync with the create_hash_table script in
+// _javascript_Core and the CodeGeneratorJS.pm script in WebCore.
+
+// Golden ratio. Arbitrary start value to avoid mapping all zeros to a hash value of zero.
+static const unsigned stringHashingStartValue = 0x9E3779B9U;
+
+class StringHasher {
+public:
+ static const unsigned flagCount = 8; // Save 8 bits for StringImpl to use as flags.
+
+ StringHasher()
+ : m_hash(stringHashingStartValue)
+ , m_hasPendingCharacter(false)
+ , m_pendingCharacter(0)
+ {
+ }
+
+ // The hasher hashes two characters at a time, and thus an "aligned" hasher is one
+ // where an even number of characters have been added. Callers that always add
+ // characters two at a time can use the "assuming aligned" functions.
+ void addCharactersAssumingAligned(UChar a, UChar b)
+ {
+ ASSERT(!m_hasPendingCharacter);
+ m_hash += a;
+ m_hash = (m_hash << 16) ^ ((b << 11) ^ m_hash);
+ m_hash += m_hash >> 11;
+ }
+
+ void addCharacter(UChar character)
+ {
+ if (m_hasPendingCharacter) {
+ m_hasPendingCharacter = false;
+ addCharactersAssumingAligned(m_pendingCharacter, character);
+ return;
+ }
+
+ m_pendingCharacter = character;
+ m_hasPendingCharacter = true;
+ }
+
+ void addCharacters(UChar a, UChar b)
+ {
+ if (m_hasPendingCharacter) {
+#if !ASSERT_DISABLED
+ m_hasPendingCharacter = false;
+#endif
+ addCharactersAssumingAligned(m_pendingCharacter, a);
+ m_pendingCharacter = b;
+#if !ASSERT_DISABLED
+ m_hasPendingCharacter = true;
+#endif
+ return;
+ }
+
+ addCharactersAssumingAligned(a, b);
+ }
+
+ template<typename T, UChar Converter(T)> void addCharactersAssumingAligned(const T* data, unsigned length)
+ {
+ ASSERT(!m_hasPendingCharacter);
+
+ bool remainder = length & 1;
+ length >>= 1;
+
+ while (length--) {
+ addCharactersAssumingAligned(Converter(data[0]), Converter(data[1]));
+ data += 2;
+ }
+
+ if (remainder)
+ addCharacter(Converter(*data));
+ }
+
+ template<typename T> void addCharactersAssumingAligned(const T* data, unsigned length)
+ {
+ addCharactersAssumingAligned<T, defaultConverter>(data, length);
+ }
+
+ template<typename T, UChar Converter(T)> void addCharactersAssumingAligned(const T* data)
+ {
+ ASSERT(!m_hasPendingCharacter);
+
+ while (T a = *data++) {
+ T b = *data++;
+ if (!b) {
+ addCharacter(Converter(a));
+ break;
+ }
+ addCharactersAssumingAligned(Converter(a), Converter(b));
+ }
+ }
+
+ template<typename T> void addCharactersAssumingAligned(const T* data)
+ {
+ addCharactersAssumingAligned<T, defaultConverter>(data);
+ }
+
+ template<typename T, UChar Converter(T)> void addCharacters(const T* data, unsigned length)
+ {
+ if (m_hasPendingCharacter && length) {
+ m_hasPendingCharacter = false;
+ addCharactersAssumingAligned(m_pendingCharacter, Converter(*data++));
+ --length;
+ }
+ addCharactersAssumingAligned<T, Converter>(data, length);
+ }
+
+ template<typename T> void addCharacters(const T* data, unsigned length)
+ {
+ addCharacters<T, defaultConverter>(data, length);
+ }
+
+ template<typename T, UChar Converter(T)> void addCharacters(const T* data)
+ {
+ if (m_hasPendingCharacter && *data) {
+ m_hasPendingCharacter = false;
+ addCharactersAssumingAligned(m_pendingCharacter, Converter(*data++));
+ }
+ addCharactersAssumingAligned<T, Converter>(data);
+ }
+
+ template<typename T> void addCharacters(const T* data)
+ {
+ addCharacters<T, defaultConverter>(data);
+ }
+
+ unsigned hashWithTop8BitsMasked() const
+ {
+ unsigned result = avalancheBits();
+
+ // Reserving space from the high bits for flags preserves most of the hash's
+ // value, since hash lookup typically masks out the high bits anyway.
+ result &= (1U << (sizeof(result) * 8 - flagCount)) - 1;
+
+ // This avoids ever returning a hash code of 0, since that is used to
+ // signal "hash not computed yet". Setting the high bit maintains
+ // reasonable fidelity to a hash code of 0 because it is likely to yield
+ // exactly 0 when hash lookup masks out the high bits.
+ if (!result)
+ result = 0x80000000 >> flagCount;
+
+ return result;
+ }
+
+ unsigned hash() const
+ {
+ unsigned result = avalancheBits();
+
+ // This avoids ever returning a hash code of 0, since that is used to
+ // signal "hash not computed yet". Setting the high bit maintains
+ // reasonable fidelity to a hash code of 0 because it is likely to yield
+ // exactly 0 when hash lookup masks out the high bits.
+ if (!result)
+ result = 0x80000000;
+
+ return result;
+ }
+
+ template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length)
+ {
+ StringHasher hasher;
+ hasher.addCharactersAssumingAligned<T, Converter>(data, length);
+ return hasher.hashWithTop8BitsMasked();
+ }
+
+ template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data)
+ {
+ StringHasher hasher;
+ hasher.addCharactersAssumingAligned<T, Converter>(data);
+ return hasher.hashWithTop8BitsMasked();
+ }
+
+ template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length)
+ {
+ return computeHashAndMaskTop8Bits<T, defaultConverter>(data, length);
+ }
+
+ template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data)
+ {
+ return computeHashAndMaskTop8Bits<T, defaultConverter>(data);
+ }
+
+ template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data, unsigned length)
+ {
+ StringHasher hasher;
+ hasher.addCharactersAssumingAligned<T, Converter>(data, length);
+ return hasher.hash();
+ }
+
+ template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data)
+ {
+ StringHasher hasher;
+ hasher.addCharactersAssumingAligned<T, Converter>(data);
+ return hasher.hash();
+ }
+
+ template<typename T> static unsigned computeHash(const T* data, unsigned length)
+ {
+ return computeHash<T, defaultConverter>(data, length);
+ }
+
+ template<typename T> static unsigned computeHash(const T* data)
+ {
+ return computeHash<T, defaultConverter>(data);
+ }
+
+ static unsigned hashMemory(const void* data, unsigned length)
+ {
+ // FIXME: Why does this function use the version of the hash that drops the top 8 bits?
+ // We want that for all string hashing so we can use those bits in StringImpl and hash
+ // strings consistently, but I don't see why we'd want that for general memory hashing.
+ ASSERT(!(length % 2));
+ return computeHashAndMaskTop8Bits<UChar>(static_cast<const UChar*>(data), length / sizeof(UChar));
+ }
+
+ template<size_t length> static unsigned hashMemory(const void* data)
+ {
+ static_assert(!(length % 2), "length must be a multiple of two!");
+ return hashMemory(data, length);
+ }
+
+private:
+ static UChar defaultConverter(UChar character)
+ {
+ return character;
+ }
+
+ static UChar defaultConverter(LChar character)
+ {
+ return character;
+ }
+
+ unsigned avalancheBits() const
+ {
+ unsigned result = m_hash;
+
+ // Handle end case.
+ if (m_hasPendingCharacter) {
+ result += m_pendingCharacter;
+ result ^= result << 11;
+ result += result >> 17;
+ }
+
+ // Force "avalanching" of final 31 bits.
+ result ^= result << 3;
+ result += result >> 5;
+ result ^= result << 2;
+ result += result >> 15;
+ result ^= result << 10;
+
+ return result;
+ }
+
+ unsigned m_hash;
+ bool m_hasPendingCharacter;
+ UChar m_pendingCharacter;
+};
+
+class IntegerHasher {
+public:
+ void add(unsigned integer)
+ {
+ m_underlyingHasher.addCharactersAssumingAligned(integer, integer >> 16);
+ }
+
+ unsigned hash() const
+ {
+ return m_underlyingHasher.hash();
+ }
+
+private:
+ StringHasher m_underlyingHasher;
+};
+
+} // namespace WTF
+
+using WTF::IntegerHasher;
+using WTF::StringHasher;
+
+#endif // WTF_Hasher_h
Deleted: trunk/Source/WTF/wtf/StringHasher.h (188556 => 188557)
--- trunk/Source/WTF/wtf/StringHasher.h 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WTF/wtf/StringHasher.h 2015-08-17 23:59:05 UTC (rev 188557)
@@ -1,297 +0,0 @@
-/*
- * Copyright (C) 2005, 2006, 2008, 2010, 2013 Apple Inc. All rights reserved.
- * Copyright (C) 2010 Patrick Gansterer <par...@paroga.com>
- *
- * 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 WTF_StringHasher_h
-#define WTF_StringHasher_h
-
-#include <unicode/utypes.h>
-#include <wtf/text/LChar.h>
-
-namespace WTF {
-
-// Paul Hsieh's SuperFastHash
-// http://www.azillionmonkeys.com/qed/hash.html
-
-// LChar data is interpreted as Latin-1-encoded (zero extended to 16 bits).
-
-// NOTE: The hash computation here must stay in sync with the create_hash_table script in
-// _javascript_Core and the CodeGeneratorJS.pm script in WebCore.
-
-// Golden ratio. Arbitrary start value to avoid mapping all zeros to a hash value of zero.
-static const unsigned stringHashingStartValue = 0x9E3779B9U;
-
-class StringHasher {
-public:
- static const unsigned flagCount = 8; // Save 8 bits for StringImpl to use as flags.
-
- StringHasher()
- : m_hash(stringHashingStartValue)
- , m_hasPendingCharacter(false)
- , m_pendingCharacter(0)
- {
- }
-
- // The hasher hashes two characters at a time, and thus an "aligned" hasher is one
- // where an even number of characters have been added. Callers that always add
- // characters two at a time can use the "assuming aligned" functions.
- void addCharactersAssumingAligned(UChar a, UChar b)
- {
- ASSERT(!m_hasPendingCharacter);
- m_hash += a;
- m_hash = (m_hash << 16) ^ ((b << 11) ^ m_hash);
- m_hash += m_hash >> 11;
- }
-
- void addCharacter(UChar character)
- {
- if (m_hasPendingCharacter) {
- m_hasPendingCharacter = false;
- addCharactersAssumingAligned(m_pendingCharacter, character);
- return;
- }
-
- m_pendingCharacter = character;
- m_hasPendingCharacter = true;
- }
-
- void addCharacters(UChar a, UChar b)
- {
- if (m_hasPendingCharacter) {
-#if !ASSERT_DISABLED
- m_hasPendingCharacter = false;
-#endif
- addCharactersAssumingAligned(m_pendingCharacter, a);
- m_pendingCharacter = b;
-#if !ASSERT_DISABLED
- m_hasPendingCharacter = true;
-#endif
- return;
- }
-
- addCharactersAssumingAligned(a, b);
- }
-
- template<typename T, UChar Converter(T)> void addCharactersAssumingAligned(const T* data, unsigned length)
- {
- ASSERT(!m_hasPendingCharacter);
-
- bool remainder = length & 1;
- length >>= 1;
-
- while (length--) {
- addCharactersAssumingAligned(Converter(data[0]), Converter(data[1]));
- data += 2;
- }
-
- if (remainder)
- addCharacter(Converter(*data));
- }
-
- template<typename T> void addCharactersAssumingAligned(const T* data, unsigned length)
- {
- addCharactersAssumingAligned<T, defaultConverter>(data, length);
- }
-
- template<typename T, UChar Converter(T)> void addCharactersAssumingAligned(const T* data)
- {
- ASSERT(!m_hasPendingCharacter);
-
- while (T a = *data++) {
- T b = *data++;
- if (!b) {
- addCharacter(Converter(a));
- break;
- }
- addCharactersAssumingAligned(Converter(a), Converter(b));
- }
- }
-
- template<typename T> void addCharactersAssumingAligned(const T* data)
- {
- addCharactersAssumingAligned<T, defaultConverter>(data);
- }
-
- template<typename T, UChar Converter(T)> void addCharacters(const T* data, unsigned length)
- {
- if (m_hasPendingCharacter && length) {
- m_hasPendingCharacter = false;
- addCharactersAssumingAligned(m_pendingCharacter, Converter(*data++));
- --length;
- }
- addCharactersAssumingAligned<T, Converter>(data, length);
- }
-
- template<typename T> void addCharacters(const T* data, unsigned length)
- {
- addCharacters<T, defaultConverter>(data, length);
- }
-
- template<typename T, UChar Converter(T)> void addCharacters(const T* data)
- {
- if (m_hasPendingCharacter && *data) {
- m_hasPendingCharacter = false;
- addCharactersAssumingAligned(m_pendingCharacter, Converter(*data++));
- }
- addCharactersAssumingAligned<T, Converter>(data);
- }
-
- template<typename T> void addCharacters(const T* data)
- {
- addCharacters<T, defaultConverter>(data);
- }
-
- unsigned hashWithTop8BitsMasked() const
- {
- unsigned result = avalancheBits();
-
- // Reserving space from the high bits for flags preserves most of the hash's
- // value, since hash lookup typically masks out the high bits anyway.
- result &= (1U << (sizeof(result) * 8 - flagCount)) - 1;
-
- // This avoids ever returning a hash code of 0, since that is used to
- // signal "hash not computed yet". Setting the high bit maintains
- // reasonable fidelity to a hash code of 0 because it is likely to yield
- // exactly 0 when hash lookup masks out the high bits.
- if (!result)
- result = 0x80000000 >> flagCount;
-
- return result;
- }
-
- unsigned hash() const
- {
- unsigned result = avalancheBits();
-
- // This avoids ever returning a hash code of 0, since that is used to
- // signal "hash not computed yet". Setting the high bit maintains
- // reasonable fidelity to a hash code of 0 because it is likely to yield
- // exactly 0 when hash lookup masks out the high bits.
- if (!result)
- result = 0x80000000;
-
- return result;
- }
-
- template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length)
- {
- StringHasher hasher;
- hasher.addCharactersAssumingAligned<T, Converter>(data, length);
- return hasher.hashWithTop8BitsMasked();
- }
-
- template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data)
- {
- StringHasher hasher;
- hasher.addCharactersAssumingAligned<T, Converter>(data);
- return hasher.hashWithTop8BitsMasked();
- }
-
- template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length)
- {
- return computeHashAndMaskTop8Bits<T, defaultConverter>(data, length);
- }
-
- template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data)
- {
- return computeHashAndMaskTop8Bits<T, defaultConverter>(data);
- }
-
- template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data, unsigned length)
- {
- StringHasher hasher;
- hasher.addCharactersAssumingAligned<T, Converter>(data, length);
- return hasher.hash();
- }
-
- template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data)
- {
- StringHasher hasher;
- hasher.addCharactersAssumingAligned<T, Converter>(data);
- return hasher.hash();
- }
-
- template<typename T> static unsigned computeHash(const T* data, unsigned length)
- {
- return computeHash<T, defaultConverter>(data, length);
- }
-
- template<typename T> static unsigned computeHash(const T* data)
- {
- return computeHash<T, defaultConverter>(data);
- }
-
- static unsigned hashMemory(const void* data, unsigned length)
- {
- // FIXME: Why does this function use the version of the hash that drops the top 8 bits?
- // We want that for all string hashing so we can use those bits in StringImpl and hash
- // strings consistently, but I don't see why we'd want that for general memory hashing.
- ASSERT(!(length % 2));
- return computeHashAndMaskTop8Bits<UChar>(static_cast<const UChar*>(data), length / sizeof(UChar));
- }
-
- template<size_t length> static unsigned hashMemory(const void* data)
- {
- static_assert(!(length % 2), "length must be a multiple of two!");
- return hashMemory(data, length);
- }
-
-private:
- static UChar defaultConverter(UChar character)
- {
- return character;
- }
-
- static UChar defaultConverter(LChar character)
- {
- return character;
- }
-
- unsigned avalancheBits() const
- {
- unsigned result = m_hash;
-
- // Handle end case.
- if (m_hasPendingCharacter) {
- result += m_pendingCharacter;
- result ^= result << 11;
- result += result >> 17;
- }
-
- // Force "avalanching" of final 31 bits.
- result ^= result << 3;
- result += result >> 5;
- result ^= result << 2;
- result += result >> 15;
- result ^= result << 10;
-
- return result;
- }
-
- unsigned m_hash;
- bool m_hasPendingCharacter;
- UChar m_pendingCharacter;
-};
-
-} // namespace WTF
-
-using WTF::StringHasher;
-
-#endif // WTF_StringHasher_h
Modified: trunk/Source/WTF/wtf/text/CString.cpp (188556 => 188557)
--- trunk/Source/WTF/wtf/text/CString.cpp 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WTF/wtf/text/CString.cpp 2015-08-17 23:59:05 UTC (rev 188557)
@@ -28,7 +28,7 @@
#include "CString.h"
#include <string.h>
-#include <wtf/StringHasher.h>
+#include <wtf/Hasher.h>
namespace WTF {
Modified: trunk/Source/WTF/wtf/text/StringHash.h (188556 => 188557)
--- trunk/Source/WTF/wtf/text/StringHash.h 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WTF/wtf/text/StringHash.h 2015-08-17 23:59:05 UTC (rev 188557)
@@ -24,7 +24,7 @@
#include <wtf/text/AtomicString.h>
#include <wtf/HashTraits.h>
-#include <wtf/StringHasher.h>
+#include <wtf/Hasher.h>
namespace WTF {
Modified: trunk/Source/WTF/wtf/text/StringImpl.h (188556 => 188557)
--- trunk/Source/WTF/wtf/text/StringImpl.h 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WTF/wtf/text/StringImpl.h 2015-08-17 23:59:05 UTC (rev 188557)
@@ -28,9 +28,9 @@
#include <unicode/ustring.h>
#include <wtf/ASCIICType.h>
#include <wtf/Forward.h>
+#include <wtf/Hasher.h>
#include <wtf/MathExtras.h>
#include <wtf/StdLibExtras.h>
-#include <wtf/StringHasher.h>
#include <wtf/Vector.h>
#include <wtf/text/ConversionMode.h>
#include <wtf/text/StringCommon.h>
Modified: trunk/Source/WTF/wtf/unicode/UTF8.cpp (188556 => 188557)
--- trunk/Source/WTF/wtf/unicode/UTF8.cpp 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WTF/wtf/unicode/UTF8.cpp 2015-08-17 23:59:05 UTC (rev 188557)
@@ -28,7 +28,7 @@
#include "UTF8.h"
#include "ASCIICType.h"
-#include <wtf/StringHasher.h>
+#include <wtf/Hasher.h>
#include <wtf/unicode/CharacterNames.h>
namespace WTF {
Modified: trunk/Source/WebCore/ChangeLog (188556 => 188557)
--- trunk/Source/WebCore/ChangeLog 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WebCore/ChangeLog 2015-08-17 23:59:05 UTC (rev 188557)
@@ -1,3 +1,23 @@
+2015-08-17 Myles C. Maxfield <mmaxfi...@apple.com>
+
+ Implement IntegerHasher
+ https://bugs.webkit.org/show_bug.cgi?id=147866
+
+ Reviewed by Darin Adler and Anders Carlsson.
+
+ Rename StringHasher.h to Hasher.
+
+ No new tests because there is no behavior difference.
+
+ * contentextensions/DFAMinimizer.cpp: Use new #include.
+ * contentextensions/HashableActionList.h: Ditto.
+ * platform/graphics/FontFeatureSettings.cpp:
+ (WebCore::FontFeatureSettings::hash): Use new IntegerHasher class.
+ (WebCore::FontFeature::hash): Deleted.
+ * platform/graphics/FontFeatureSettings.h: Remove unnecessary function.
+ * platform/graphics/Gradient.cpp: Use new #include.
+ * platform/graphics/WidthCache.h: Ditto.
+
2015-08-17 Chris Dumez <cdu...@apple.com>
Log actual PageCache retrieval success rate using diagnostic logging
Modified: trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp (188556 => 188557)
--- trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WebCore/contentextensions/DFAMinimizer.cpp 2015-08-17 23:59:05 UTC (rev 188557)
@@ -33,7 +33,7 @@
#include "MutableRangeList.h"
#include <wtf/HashMap.h>
#include <wtf/HashSet.h>
-#include <wtf/StringHasher.h>
+#include <wtf/Hasher.h>
#include <wtf/Vector.h>
namespace WebCore {
Modified: trunk/Source/WebCore/contentextensions/HashableActionList.h (188556 => 188557)
--- trunk/Source/WebCore/contentextensions/HashableActionList.h 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WebCore/contentextensions/HashableActionList.h 2015-08-17 23:59:05 UTC (rev 188557)
@@ -26,7 +26,7 @@
#ifndef HashableActionList_h
#define HashableActionList_h
-#include <wtf/StringHasher.h>
+#include <wtf/Hasher.h>
#include <wtf/Vector.h>
namespace WebCore {
Modified: trunk/Source/WebCore/platform/graphics/FontFeatureSettings.cpp (188556 => 188557)
--- trunk/Source/WebCore/platform/graphics/FontFeatureSettings.cpp 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WebCore/platform/graphics/FontFeatureSettings.cpp 2015-08-17 23:59:05 UTC (rev 188557)
@@ -46,11 +46,6 @@
return (m_tag.impl() < other.m_tag.impl()) || (m_tag.impl() == other.m_tag.impl() && m_value < other.m_value);
}
-unsigned FontFeature::hash() const
-{
- return WTF::PairHash<AtomicString, unsigned>::hash(std::make_pair(m_tag, m_value));
-}
-
Ref<FontFeatureSettings> FontFeatureSettings::create()
{
return adoptRef(*new FontFeatureSettings);
@@ -69,10 +64,12 @@
unsigned FontFeatureSettings::hash() const
{
- unsigned result = 0;
- for (size_t i = 0; i < size(); ++i)
- result = WTF::pairIntHash(result, at(i).hash());
- return result;
+ IntegerHasher hasher;
+ for (auto& feature : m_list) {
+ hasher.add(feature.tag().impl()->existingHash());
+ hasher.add(feature.value());
+ }
+ return hasher.hash();
}
}
Modified: trunk/Source/WebCore/platform/graphics/FontFeatureSettings.h (188556 => 188557)
--- trunk/Source/WebCore/platform/graphics/FontFeatureSettings.h 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WebCore/platform/graphics/FontFeatureSettings.h 2015-08-17 23:59:05 UTC (rev 188557)
@@ -45,8 +45,6 @@
int value() const { return m_value; }
bool enabled() const { return value(); }
- unsigned hash() const;
-
private:
AtomicString m_tag;
const int m_value { 0 };
Modified: trunk/Source/WebCore/platform/graphics/Gradient.cpp (188556 => 188557)
--- trunk/Source/WebCore/platform/graphics/Gradient.cpp 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WebCore/platform/graphics/Gradient.cpp 2015-08-17 23:59:05 UTC (rev 188557)
@@ -30,7 +30,7 @@
#include "Color.h"
#include "FloatRect.h"
#include <wtf/HashFunctions.h>
-#include <wtf/StringHasher.h>
+#include <wtf/Hasher.h>
using WTF::pairIntHash;
Modified: trunk/Source/WebCore/platform/graphics/WidthCache.h (188556 => 188557)
--- trunk/Source/WebCore/platform/graphics/WidthCache.h 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WebCore/platform/graphics/WidthCache.h 2015-08-17 23:59:05 UTC (rev 188557)
@@ -30,8 +30,8 @@
#include <wtf/Forward.h>
#include <wtf/HashFunctions.h>
#include <wtf/HashSet.h>
+#include <wtf/Hasher.h>
#include <wtf/RefPtr.h>
-#include <wtf/StringHasher.h>
namespace WebCore {
Modified: trunk/Source/WebInspectorUI/ChangeLog (188556 => 188557)
--- trunk/Source/WebInspectorUI/ChangeLog 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WebInspectorUI/ChangeLog 2015-08-17 23:59:05 UTC (rev 188557)
@@ -1,3 +1,14 @@
+2015-08-17 Myles C. Maxfield <mmaxfi...@apple.com>
+
+ Implement IntegerHasher
+ https://bugs.webkit.org/show_bug.cgi?id=147866
+
+ Reviewed by Darin Adler and Anders Carlsson.
+
+ Update comment.
+
+ * UserInterface/Base/Utilities.js:
+
2015-08-17 Brian Burg <bb...@apple.com>
Web Inspector: InspectorTest should be a subclass of TestHarness
Modified: trunk/Source/WebInspectorUI/UserInterface/Base/Utilities.js (188556 => 188557)
--- trunk/Source/WebInspectorUI/UserInterface/Base/Utilities.js 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WebInspectorUI/UserInterface/Base/Utilities.js 2015-08-17 23:59:05 UTC (rev 188557)
@@ -588,7 +588,7 @@
{
get: function()
{
- // Matches the wtf/StringHasher.h (SuperFastHash) algorithm.
+ // Matches the wtf/Hasher.h (SuperFastHash) algorithm.
// Arbitrary start value to avoid mapping all 0's to all 0's.
const stringHashingStartValue = 0x9e3779b9;
Modified: trunk/Source/WebKit2/ChangeLog (188556 => 188557)
--- trunk/Source/WebKit2/ChangeLog 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WebKit2/ChangeLog 2015-08-17 23:59:05 UTC (rev 188557)
@@ -1,3 +1,15 @@
+2015-08-17 Myles C. Maxfield <mmaxfi...@apple.com>
+
+ Implement IntegerHasher
+ https://bugs.webkit.org/show_bug.cgi?id=147866
+
+ Reviewed by Darin Adler and Anders Carlsson.
+
+ Use new #include.
+
+ * DatabaseProcess/IndexedDB/IDBIdentifier.h:
+ * Platform/IPC/StringReference.cpp:
+
2015-08-13 Anders Carlsson <ander...@apple.com>
Add WKWindowFeaturesRef and a new modern createNewPage UI client callback
Modified: trunk/Source/WebKit2/DatabaseProcess/IndexedDB/IDBIdentifier.h (188556 => 188557)
--- trunk/Source/WebKit2/DatabaseProcess/IndexedDB/IDBIdentifier.h 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WebKit2/DatabaseProcess/IndexedDB/IDBIdentifier.h 2015-08-17 23:59:05 UTC (rev 188557)
@@ -29,7 +29,7 @@
#if ENABLE(INDEXED_DATABASE) && ENABLE(DATABASE_PROCESS)
#include <wtf/HashTraits.h>
-#include <wtf/StringHasher.h>
+#include <wtf/Hasher.h>
namespace WebKit {
Modified: trunk/Source/WebKit2/Platform/IPC/StringReference.cpp (188556 => 188557)
--- trunk/Source/WebKit2/Platform/IPC/StringReference.cpp 2015-08-17 23:59:03 UTC (rev 188556)
+++ trunk/Source/WebKit2/Platform/IPC/StringReference.cpp 2015-08-17 23:59:05 UTC (rev 188557)
@@ -29,7 +29,7 @@
#include "ArgumentDecoder.h"
#include "ArgumentEncoder.h"
#include "DataReference.h"
-#include <wtf/StringHasher.h>
+#include <wtf/Hasher.h>
#include <wtf/text/CString.h>
namespace IPC {
