Diff
Modified: trunk/Source/WTF/ChangeLog (225462 => 225463)
--- trunk/Source/WTF/ChangeLog 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Source/WTF/ChangeLog 2017-12-03 22:48:40 UTC (rev 225463)
@@ -1,3 +1,30 @@
+2017-12-03 Darin Adler <[email protected]>
+
+ Add WTF::Hasher, an easier to use replacement for WTF::IntegerHasher
+ https://bugs.webkit.org/show_bug.cgi?id=180318
+
+ Reviewed by JF Bastien.
+
+ * WTF.xcodeproj/project.pbxproj: Added Hasher.h.
+ * wtf/CMakeLists.txt: Ditto.
+
+ * wtf/Forward.h: Added Hasher and TextStream.
+
+ * wtf/Hasher.h: Moved StringHasher into a separate header. Added Hasher.
+ Marked IntegerHasher deprecated.
+
+ * wtf/text/CString.cpp: Include StringHasher.h instead of Hasher.h.
+ * wtf/text/StringHash.h: Ditto.
+
+ * wtf/text/StringHasher.h: Added. Moved StringHasher here from Hasher.h.
+
+ * wtf/text/StringImpl.h: Include StringHasher.h instead of Hasher.h.
+
+ * wtf/text/WTFString.h: Added a hash function. This was useful in some
+ adoption I was doing in WebCore, not included in this patch.
+
+ * wtf/unicode/UTF8.cpp: Include StringHasher.h instead of Hasher.h.
+
2017-12-02 Brady Eidson <[email protected]>
Factor out the "databaseTaskQueue" parts of IDBServer into something reusable.
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (225462 => 225463)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2017-12-03 22:48:40 UTC (rev 225463)
@@ -378,6 +378,7 @@
83F2BADE1CF9524E003E99C3 /* Function.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Function.h; sourceTree = "<group>"; };
83FBA93119DF459700F30ADB /* TypeCasts.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TypeCasts.h; sourceTree = "<group>"; };
86F46F5F1A2840EE00CCBF22 /* RefCounter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RefCounter.h; sourceTree = "<group>"; };
+ 933D63191FCB6AB90032ECD6 /* StringHasher.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StringHasher.h; sourceTree = "<group>"; };
93934BD218A1E8C300D0D6A1 /* StringViewObjC.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = StringViewObjC.mm; path = mac/StringViewObjC.mm; sourceTree = "<group>"; };
93934BD418A1F16900D0D6A1 /* StringViewCF.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = StringViewCF.cpp; path = cf/StringViewCF.cpp; sourceTree = "<group>"; };
93AC91A718942FC400244939 /* LChar.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LChar.h; sourceTree = "<group>"; };
@@ -1141,6 +1142,7 @@
A8A47326151A825B004123FF /* StringConcatenate.h */,
7CD4C26F1E2C82B900929470 /* StringConcatenateNumbers.h */,
A8A47327151A825B004123FF /* StringHash.h */,
+ 933D63191FCB6AB90032ECD6 /* StringHasher.h */,
A8A47328151A825B004123FF /* StringImpl.cpp */,
A8A47329151A825B004123FF /* StringImpl.h */,
0F0F52691F421FF8004A452C /* StringMalloc.cpp */,
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (225462 => 225463)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2017-12-03 22:48:40 UTC (rev 225463)
@@ -186,6 +186,7 @@
text/StringBuffer.h
text/StringCommon.h
text/StringHash.h
+ text/StringHasher.h
text/StringImpl.h
text/StringMalloc.h
text/StringVector.h
Modified: trunk/Source/WTF/wtf/Forward.h (225462 => 225463)
--- trunk/Source/WTF/wtf/Forward.h 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Source/WTF/wtf/Forward.h 2017-12-03 22:48:40 UTC (rev 225463)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2006, 2009, 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2006-2017 Apple Inc. All rights reserved.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
@@ -34,6 +34,7 @@
class CString;
class CrashOnOverflow;
class FunctionDispatcher;
+class Hasher;
class OrdinalNumber;
class PrintStream;
class SHA1;
@@ -42,6 +43,7 @@
class StringImpl;
class StringView;
class TextPosition;
+class TextStream;
struct FastMalloc;
@@ -69,8 +71,8 @@
using WTF::AtomicString;
using WTF::AtomicStringImpl;
using WTF::BinarySemaphore;
+using WTF::CString;
using WTF::CompletionHandler;
-using WTF::CString;
using WTF::Expected;
using WTF::Function;
using WTF::FunctionDispatcher;
@@ -77,6 +79,7 @@
using WTF::HashCountedSet;
using WTF::HashMap;
using WTF::HashSet;
+using WTF::Hasher;
using WTF::LazyNeverDestroyed;
using WTF::NeverDestroyed;
using WTF::OptionSet;
@@ -91,5 +94,6 @@
using WTF::StringImpl;
using WTF::StringView;
using WTF::TextPosition;
+using WTF::TextStream;
using WTF::Variant;
using WTF::Vector;
Modified: trunk/Source/WTF/wtf/Hasher.h (225462 => 225463)
--- trunk/Source/WTF/wtf/Hasher.h 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Source/WTF/wtf/Hasher.h 2017-12-03 22:48:40 UTC (rev 225463)
@@ -1,6 +1,5 @@
/*
- * Copyright (C) 2005-2006, 2008, 2010, 2013, 2016 Apple Inc. All rights reserved.
- * Copyright (C) 2010 Patrick Gansterer <[email protected]>
+ * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
@@ -19,371 +18,147 @@
*
*/
-#ifndef WTF_Hasher_h
-#define WTF_Hasher_h
+#pragma once
-#include <unicode/utypes.h>
-#include <wtf/text/LChar.h>
+#include <wtf/Forward.h>
+#include <wtf/StdLibExtras.h>
+#include <wtf/text/StringHasher.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 constexpr const unsigned stringHashingStartValue = 0x9E3779B9U;
-
-class StringHasher {
+// Deprecated. Use Hasher instead.
+class IntegerHasher {
public:
- static constexpr const unsigned flagCount = 8; // Save 8 bits for StringImpl to use as flags.
- static constexpr const unsigned maskHash = (1U << (sizeof(unsigned) * 8 - flagCount)) - 1;
-
- StringHasher()
- : m_hash(stringHashingStartValue)
- , m_hasPendingCharacter(false)
- , m_pendingCharacter(0)
+ void add(uint32_t integer)
{
+ m_underlyingHasher.addCharactersAssumingAligned(integer, integer >> 16);
}
- // 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 (!length)
- return;
- if (m_hasPendingCharacter) {
- 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
- {
- return finalizeAndMaskTop8Bits(processPendingCharacter());
- }
-
unsigned hash() const
{
- return finalize(processPendingCharacter());
+ return m_underlyingHasher.hash();
}
- 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();
- }
+private:
+ StringHasher m_underlyingHasher;
+};
- template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data)
- {
- StringHasher hasher;
- hasher.addCharactersAssumingAligned<T, Converter>(data);
- return hasher.hashWithTop8BitsMasked();
- }
+template<typename... Types> uint32_t computeHash(const Types&...);
+template<typename T, typename... OtherTypes> uint32_t computeHash(std::initializer_list<T>, std::initializer_list<OtherTypes>...);
- template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length)
+class Hasher {
+public:
+ template<typename... Types> friend uint32_t computeHash(const Types&... values)
{
- return computeHashAndMaskTop8Bits<T, defaultConverter>(data, length);
+ Hasher hasher;
+ add(hasher, std::forward_as_tuple(values...));
+ return hasher.m_underlyingHasher.hash();
}
- template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data)
+ template<typename T, typename... OtherTypes> friend uint32_t computeHash(std::initializer_list<T> list, std::initializer_list<OtherTypes>... otherLists)
{
- return computeHashAndMaskTop8Bits<T, defaultConverter>(data);
+ Hasher hasher;
+ add(hasher, list);
+ add(hasher, std::forward_as_tuple(otherLists...));
+ return hasher.m_underlyingHasher.hash();
}
- template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data, unsigned length)
+ template<typename UnsignedInteger> friend std::enable_if_t<std::is_unsigned<UnsignedInteger>::value && sizeof(UnsignedInteger) <= sizeof(uint32_t), void> add(Hasher& hasher, UnsignedInteger integer)
{
- StringHasher hasher;
- hasher.addCharactersAssumingAligned<T, Converter>(data, length);
- return hasher.hash();
+ // We can consider adding a more efficient code path for hashing booleans or individual bytes if needed.
+ // We can consider adding a more efficient code path for hashing 16-bit values if needed, perhaps using addCharacter,
+ // but getting rid of "assuming aligned" would make hashing values 32-bit or larger slower.
+ uint32_t sizedInteger = integer;
+ hasher.m_underlyingHasher.addCharactersAssumingAligned(sizedInteger, sizedInteger >> 16);
}
- 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)
- {
- size_t lengthInUChar = length / sizeof(UChar);
- StringHasher hasher;
- hasher.addCharactersAssumingAligned(static_cast<const UChar*>(data), lengthInUChar);
-
- for (size_t i = 0; i < length % sizeof(UChar); ++i)
- hasher.addCharacter(static_cast<const char*>(data)[lengthInUChar * sizeof(UChar) + i]);
-
- return hasher.hash();
- }
-
- template<size_t length> static unsigned hashMemory(const void* data)
- {
- return hashMemory(data, length);
- }
-
- static constexpr unsigned finalize(unsigned hash)
- {
- return avoidZero(avalancheBits(hash));
- }
-
- static constexpr unsigned finalizeAndMaskTop8Bits(unsigned hash)
- {
- // 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.
- return avoidZero(avalancheBits(hash) & StringHasher::maskHash);
- }
-
- template<typename T, unsigned characterCount>
- static constexpr unsigned computeLiteralHash(const T (&characters)[characterCount])
- {
- return StringHasher::finalize(computeLiteralHashImpl(stringHashingStartValue, 0, characters, characterCount - 1));
- }
-
- template<typename T, unsigned characterCount>
- static constexpr unsigned computeLiteralHashAndMaskTop8Bits(const T (&characters)[characterCount])
- {
- return StringHasher::finalizeAndMaskTop8Bits(computeLiteralHashImpl(stringHashingStartValue, 0, characters, characterCount - 1));
- }
-
private:
- static UChar defaultConverter(UChar character)
- {
- return character;
- }
+ StringHasher m_underlyingHasher;
+};
- static UChar defaultConverter(LChar character)
- {
- return character;
- }
+template<typename UnsignedInteger> std::enable_if_t<std::is_unsigned<UnsignedInteger>::value && sizeof(UnsignedInteger) == sizeof(uint64_t), void> add(Hasher& hasher, UnsignedInteger integer)
+{
+ add(hasher, static_cast<uint32_t>(integer));
+ add(hasher, static_cast<uint32_t>(integer >> 32));
+}
- ALWAYS_INLINE static constexpr unsigned avalancheBits3(unsigned hash)
- {
- return hash ^ (hash << 10);
- }
+template<typename SignedArithmetic> std::enable_if_t<std::is_signed<SignedArithmetic>::value, void> add(Hasher& hasher, SignedArithmetic number)
+{
+ // We overloaded for double and float below, just deal with integers here.
+ add(hasher, static_cast<std::make_unsigned_t<SignedArithmetic>>(number));
+}
- ALWAYS_INLINE static constexpr unsigned avalancheBits2(unsigned hash)
- {
- return avalancheBits3(hash + (hash >> 15));
- }
+inline void add(Hasher& hasher, double number)
+{
+ add(hasher, bitwise_cast<uint64_t>(number));
+}
- ALWAYS_INLINE static constexpr unsigned avalancheBits1(unsigned hash)
- {
- return avalancheBits2(hash ^ (hash << 2));
- }
+inline void add(Hasher& hasher, float number)
+{
+ add(hasher, bitwise_cast<uint32_t>(number));
+}
- ALWAYS_INLINE static constexpr unsigned avalancheBits0(unsigned hash)
- {
- return avalancheBits1(hash + (hash >> 5));
- }
+template<typename Enumeration> std::enable_if_t<std::is_enum<Enumeration>::value, void> add(Hasher& hasher, Enumeration value)
+{
+ add(hasher, static_cast<std::underlying_type_t<Enumeration>>(value));
+}
- ALWAYS_INLINE static constexpr unsigned avalancheBits(unsigned hash)
- {
- return avalancheBits0(hash ^ (hash << 3));
- }
+template<typename> struct TypeCheckHelper { };
+template<typename, typename = void> struct HasBeginFunctionMember : std::false_type { };
+template<typename Container> struct HasBeginFunctionMember<Container, std::conditional_t<false, TypeCheckHelper<decltype(std::declval<Container>().begin())>, void>> : std::true_type { };
- // 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.
- ALWAYS_INLINE static constexpr unsigned avoidZero(unsigned hash)
- {
- return hash ? hash : (0x80000000 >> StringHasher::flagCount);
- }
+template<typename Container> std::enable_if_t<HasBeginFunctionMember<Container>::value, void> add(Hasher& hasher, const Container& container)
+{
+ for (const auto& value : container)
+ add(hasher, value);
+}
- unsigned processPendingCharacter() const
- {
- unsigned result = m_hash;
+template<typename Tuple, std::size_t ...i> void addTupleHelper(Hasher& hasher, const Tuple& values, std::index_sequence<i...>)
+{
+ [] (...) { }((add(hasher, std::get<i>(values)), 0)...);
+}
- // Handle end case.
- if (m_hasPendingCharacter) {
- result += m_pendingCharacter;
- result ^= result << 11;
- result += result >> 17;
- }
- return result;
- }
+template<typename... Types> void add(Hasher& hasher, const std::tuple<Types...>& tuple)
+{
+ addTupleHelper(hasher, tuple, std::make_index_sequence<std::tuple_size<std::tuple<Types...>>::value> { });
+}
+template<typename T1, typename T2> void add(Hasher& hasher, const std::pair<T1, T2>& pair)
+{
+ add(hasher, pair.first);
+ add(hasher, pair.second);
+}
- // FIXME: This code limits itself to the older, more limited C++11 constexpr capabilities, using
- // recursion instead of looping, for example. Would be nice to rewrite this in a simpler way
- // once we no longer need to support compilers like GCC 4.9 that do not yet support it.
- static constexpr unsigned calculateWithRemainingLastCharacter1(unsigned hash)
- {
- return hash + (hash >> 17);
- }
+template<typename T> void add(Hasher& hasher, const std::optional<T>& optional)
+{
+ add(hasher, optional.has_value());
+ if (optional.has_value())
+ add(hasher, optional.value());
+}
- static constexpr unsigned calculateWithRemainingLastCharacter0(unsigned hash)
- {
- return calculateWithRemainingLastCharacter1((hash << 11) ^ hash);
- }
+template<typename... Types> void add(Hasher& hasher, const Variant<Types...>& variant)
+{
+ add(hasher, variant.index());
+ visit([&hasher] (auto& value) {
+ add(hasher, value);
+ }, variant);
+}
- static constexpr unsigned calculateWithRemainingLastCharacter(unsigned hash, unsigned character)
- {
- return calculateWithRemainingLastCharacter0(hash + character);
- }
+template<typename T1, typename T2, typename... OtherTypes> void add(Hasher& hasher, const T1& value1, const T2& value2, const OtherTypes&... otherValues)
+{
+ add(hasher, value1);
+ add(hasher, value2);
+ add(hasher, std::forward_as_tuple(otherValues...));
+}
- static constexpr unsigned calculate1(unsigned hash)
- {
- return hash + (hash >> 11);
- }
+template<typename T> void add(Hasher& hasher, std::initializer_list<T> values)
+{
+ for (auto& value : values)
+ add(hasher, value);
+}
- static constexpr unsigned calculate0(unsigned hash, unsigned secondCharacter)
- {
- return calculate1((hash << 16) ^ ((secondCharacter << 11) ^ hash));
- }
-
- static constexpr unsigned calculate(unsigned hash, unsigned firstCharacter, unsigned secondCharacter)
- {
- return calculate0(hash + firstCharacter, secondCharacter);
- }
-
- static constexpr unsigned computeLiteralHashImpl(unsigned hash, unsigned index, const char* characters, unsigned length)
- {
- return (index == length)
- ? hash : ((index + 1) == length)
- ? calculateWithRemainingLastCharacter(hash, characters[index])
- : computeLiteralHashImpl(calculate(hash, characters[index], characters[index + 1]), index + 2, characters, length);
- }
-
- 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::computeHash;
+using WTF::Hasher;
using WTF::IntegerHasher;
-using WTF::StringHasher;
-
-#endif // WTF_Hasher_h
Modified: trunk/Source/WTF/wtf/text/CString.cpp (225462 => 225463)
--- trunk/Source/WTF/wtf/text/CString.cpp 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Source/WTF/wtf/text/CString.cpp 2017-12-03 22:48:40 UTC (rev 225463)
@@ -28,7 +28,7 @@
#include "CString.h"
#include <string.h>
-#include <wtf/Hasher.h>
+#include <wtf/text/StringHasher.h>
#include <wtf/text/StringMalloc.h>
namespace WTF {
Modified: trunk/Source/WTF/wtf/text/StringHash.h (225462 => 225463)
--- trunk/Source/WTF/wtf/text/StringHash.h 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Source/WTF/wtf/text/StringHash.h 2017-12-03 22:48:40 UTC (rev 225463)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2006-2008, 2012-2013, 2016 Apple Inc. All rights reserved
+ * Copyright (C) 2006-2017 Apple Inc. All rights reserved
* Copyright (C) Research In Motion Limited 2009. All rights reserved.
*
* This library is free software; you can redistribute it and/or
@@ -22,9 +22,9 @@
#ifndef StringHash_h
#define StringHash_h
+#include <wtf/HashTraits.h>
#include <wtf/text/AtomicString.h>
-#include <wtf/HashTraits.h>
-#include <wtf/Hasher.h>
+#include <wtf/text/StringHasher.h>
namespace WTF {
Copied: trunk/Source/WTF/wtf/text/StringHasher.h (from rev 225462, trunk/Source/WTF/wtf/Hasher.h) (0 => 225463)
--- trunk/Source/WTF/wtf/text/StringHasher.h (rev 0)
+++ trunk/Source/WTF/wtf/text/StringHasher.h 2017-12-03 22:48:40 UTC (rev 225463)
@@ -0,0 +1,368 @@
+/*
+ * Copyright (C) 2005-2017 Apple Inc. All rights reserved.
+ * Copyright (C) 2010 Patrick Gansterer <[email protected]>
+ *
+ * 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.
+ *
+ */
+
+#pragma once
+
+#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 constexpr const unsigned stringHashingStartValue = 0x9E3779B9U;
+
+class StringHasher {
+public:
+ static constexpr const unsigned flagCount = 8; // Save 8 bits for StringImpl to use as flags.
+ static constexpr const unsigned maskHash = (1U << (sizeof(unsigned) * 8 - flagCount)) - 1;
+
+ 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 (!length)
+ return;
+ if (m_hasPendingCharacter) {
+ 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
+ {
+ return finalizeAndMaskTop8Bits(processPendingCharacter());
+ }
+
+ unsigned hash() const
+ {
+ return finalize(processPendingCharacter());
+ }
+
+ 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)
+ {
+ size_t lengthInUChar = length / sizeof(UChar);
+ StringHasher hasher;
+ hasher.addCharactersAssumingAligned(static_cast<const UChar*>(data), lengthInUChar);
+
+ for (size_t i = 0; i < length % sizeof(UChar); ++i)
+ hasher.addCharacter(static_cast<const char*>(data)[lengthInUChar * sizeof(UChar) + i]);
+
+ return hasher.hash();
+ }
+
+ template<size_t length> static unsigned hashMemory(const void* data)
+ {
+ return hashMemory(data, length);
+ }
+
+ static constexpr unsigned finalize(unsigned hash)
+ {
+ return avoidZero(avalancheBits(hash));
+ }
+
+ static constexpr unsigned finalizeAndMaskTop8Bits(unsigned hash)
+ {
+ // 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.
+ return avoidZero(avalancheBits(hash) & StringHasher::maskHash);
+ }
+
+ template<typename T, unsigned characterCount>
+ static constexpr unsigned computeLiteralHash(const T (&characters)[characterCount])
+ {
+ return StringHasher::finalize(computeLiteralHashImpl(stringHashingStartValue, 0, characters, characterCount - 1));
+ }
+
+ template<typename T, unsigned characterCount>
+ static constexpr unsigned computeLiteralHashAndMaskTop8Bits(const T (&characters)[characterCount])
+ {
+ return StringHasher::finalizeAndMaskTop8Bits(computeLiteralHashImpl(stringHashingStartValue, 0, characters, characterCount - 1));
+ }
+
+private:
+ static UChar defaultConverter(UChar character)
+ {
+ return character;
+ }
+
+ static UChar defaultConverter(LChar character)
+ {
+ return character;
+ }
+
+ ALWAYS_INLINE static constexpr unsigned avalancheBits3(unsigned hash)
+ {
+ return hash ^ (hash << 10);
+ }
+
+ ALWAYS_INLINE static constexpr unsigned avalancheBits2(unsigned hash)
+ {
+ return avalancheBits3(hash + (hash >> 15));
+ }
+
+ ALWAYS_INLINE static constexpr unsigned avalancheBits1(unsigned hash)
+ {
+ return avalancheBits2(hash ^ (hash << 2));
+ }
+
+ ALWAYS_INLINE static constexpr unsigned avalancheBits0(unsigned hash)
+ {
+ return avalancheBits1(hash + (hash >> 5));
+ }
+
+ ALWAYS_INLINE static constexpr unsigned avalancheBits(unsigned hash)
+ {
+ return avalancheBits0(hash ^ (hash << 3));
+ }
+
+ // 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.
+ ALWAYS_INLINE static constexpr unsigned avoidZero(unsigned hash)
+ {
+ return hash ? hash : (0x80000000 >> StringHasher::flagCount);
+ }
+
+ unsigned processPendingCharacter() const
+ {
+ unsigned result = m_hash;
+
+ // Handle end case.
+ if (m_hasPendingCharacter) {
+ result += m_pendingCharacter;
+ result ^= result << 11;
+ result += result >> 17;
+ }
+ return result;
+ }
+
+ // FIXME: This code limits itself to the older, more limited C++11 constexpr capabilities, using
+ // recursion instead of looping, for example. Would be nice to rewrite this in a simpler way
+ // once we no longer need to support compilers like GCC 4.9 that do not yet support it.
+ static constexpr unsigned calculateWithRemainingLastCharacter1(unsigned hash)
+ {
+ return hash + (hash >> 17);
+ }
+
+ static constexpr unsigned calculateWithRemainingLastCharacter0(unsigned hash)
+ {
+ return calculateWithRemainingLastCharacter1((hash << 11) ^ hash);
+ }
+
+ static constexpr unsigned calculateWithRemainingLastCharacter(unsigned hash, unsigned character)
+ {
+ return calculateWithRemainingLastCharacter0(hash + character);
+ }
+
+ static constexpr unsigned calculate1(unsigned hash)
+ {
+ return hash + (hash >> 11);
+ }
+
+ static constexpr unsigned calculate0(unsigned hash, unsigned secondCharacter)
+ {
+ return calculate1((hash << 16) ^ ((secondCharacter << 11) ^ hash));
+ }
+
+ static constexpr unsigned calculate(unsigned hash, unsigned firstCharacter, unsigned secondCharacter)
+ {
+ return calculate0(hash + firstCharacter, secondCharacter);
+ }
+
+ static constexpr unsigned computeLiteralHashImpl(unsigned hash, unsigned index, const char* characters, unsigned length)
+ {
+ return (index == length)
+ ? hash : ((index + 1) == length)
+ ? calculateWithRemainingLastCharacter(hash, characters[index])
+ : computeLiteralHashImpl(calculate(hash, characters[index], characters[index + 1]), index + 2, characters, length);
+ }
+
+ unsigned m_hash;
+ bool m_hasPendingCharacter;
+ UChar m_pendingCharacter;
+};
+
+} // namespace WTF
+
+using WTF::StringHasher;
Modified: trunk/Source/WTF/wtf/text/StringImpl.h (225462 => 225463)
--- trunk/Source/WTF/wtf/text/StringImpl.h 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Source/WTF/wtf/text/StringImpl.h 2017-12-03 22:48:40 UTC (rev 225463)
@@ -27,8 +27,6 @@
#include <unicode/ustring.h>
#include <wtf/ASCIICType.h>
#include <wtf/CheckedArithmetic.h>
-#include <wtf/Forward.h>
-#include <wtf/Hasher.h>
#include <wtf/MathExtras.h>
#include <wtf/StdLibExtras.h>
#include <wtf/Vector.h>
@@ -35,7 +33,7 @@
#include <wtf/text/ASCIIFastPath.h>
#include <wtf/text/ConversionMode.h>
#include <wtf/text/StringCommon.h>
-#include <wtf/text/StringMalloc.h>
+#include <wtf/text/StringHasher.h>
#include <wtf/text/StringVector.h>
#if USE(CF)
Modified: trunk/Source/WTF/wtf/text/WTFString.h (225462 => 225463)
--- trunk/Source/WTF/wtf/text/WTFString.h 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Source/WTF/wtf/text/WTFString.h 2017-12-03 22:48:40 UTC (rev 225463)
@@ -357,6 +357,7 @@
String(WTF::HashTableDeletedValueType) : m_impl(WTF::HashTableDeletedValue) { }
bool isHashTableDeletedValue() const { return m_impl.isHashTableDeletedValue(); }
+ unsigned hash() const { return isNull() ? 0 : impl()->hash(); }
unsigned existingHash() const { return isNull() ? 0 : impl()->existingHash(); }
#ifndef NDEBUG
Modified: trunk/Source/WTF/wtf/unicode/UTF8.cpp (225462 => 225463)
--- trunk/Source/WTF/wtf/unicode/UTF8.cpp 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Source/WTF/wtf/unicode/UTF8.cpp 2017-12-03 22:48:40 UTC (rev 225463)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2007, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2007, 2014 Apple Inc. All rights reserved.
* Copyright (C) 2010 Patrick Gansterer <[email protected]>
*
* Redistribution and use in source and binary forms, with or without
@@ -28,7 +28,7 @@
#include "UTF8.h"
#include "ASCIICType.h"
-#include <wtf/Hasher.h>
+#include <wtf/text/StringHasher.h>
#include <wtf/unicode/CharacterNames.h>
namespace WTF {
Modified: trunk/Tools/ChangeLog (225462 => 225463)
--- trunk/Tools/ChangeLog 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Tools/ChangeLog 2017-12-03 22:48:40 UTC (rev 225463)
@@ -1,3 +1,19 @@
+2017-12-03 Darin Adler <[email protected]>
+
+ Add WTF::Hasher, an easier to use replacement for WTF::IntegerHasher
+ https://bugs.webkit.org/show_bug.cgi?id=180318
+
+ Reviewed by JF Bastien.
+
+ * TestWebKitAPI/CMakeLists.txt: Added Hasher.cpp.
+ * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj: Ditto.
+
+ * TestWebKitAPI/Tests/WTF/Hasher.cpp: Added. Contains tests of the new
+ WTF::Hasher class.
+
+ * TestWebKitAPI/Tests/WTF/StringHasher.cpp: Include StringHasher.h instead of
+ Hasher.h.
+
2017-12-01 Carlos Garcia Campos <[email protected]>
WebDriver: auto-install pytest instead of importing it from wpt tools directory
Modified: trunk/Tools/TestWebKitAPI/CMakeLists.txt (225462 => 225463)
--- trunk/Tools/TestWebKitAPI/CMakeLists.txt 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Tools/TestWebKitAPI/CMakeLists.txt 2017-12-03 22:48:40 UTC (rev 225463)
@@ -103,6 +103,7 @@
${TESTWEBKITAPI_DIR}/Tests/WTF/HashCountedSet.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/HashMap.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/HashSet.cpp
+ ${TESTWEBKITAPI_DIR}/Tests/WTF/Hasher.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/IntegerToStringConversion.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/JSONValue.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/LEBDecoder.cpp
Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj (225462 => 225463)
--- trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2017-12-03 22:48:40 UTC (rev 225463)
@@ -532,6 +532,7 @@
9310CD381EF708FB0050FFE0 /* Function.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 9310CD361EF708FB0050FFE0 /* Function.cpp */; };
9329AA291DE3F81E003ABD07 /* TextBreakIterator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 9329AA281DE3F81E003ABD07 /* TextBreakIterator.cpp */; };
932AE53D1D371047005DFFAF /* focus-inputs.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 93575C551D30366E000D604D /* focus-inputs.html */; };
+ 933D631D1FCB76200032ECD6 /* Hasher.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 933D631B1FCB76180032ECD6 /* Hasher.cpp */; };
9361002914DC95A70061379D /* lots-of-iframes.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 9361002814DC957B0061379D /* lots-of-iframes.html */; };
93625D271CD9741C006DC1F1 /* large-video-without-audio.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 93625D261CD973AF006DC1F1 /* large-video-without-audio.html */; };
936F72801CD7D9EC0068A0FB /* large-video-with-audio.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 936F727E1CD7D9D00068A0FB /* large-video-with-audio.html */; };
@@ -1494,6 +1495,7 @@
9310CD361EF708FB0050FFE0 /* Function.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Function.cpp; sourceTree = "<group>"; };
9329AA281DE3F81E003ABD07 /* TextBreakIterator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TextBreakIterator.cpp; sourceTree = "<group>"; };
9331407B17B4419000F083B1 /* DidNotHandleKeyDown.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DidNotHandleKeyDown.cpp; sourceTree = "<group>"; };
+ 933D631B1FCB76180032ECD6 /* Hasher.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Hasher.cpp; sourceTree = "<group>"; };
93575C551D30366E000D604D /* focus-inputs.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = "focus-inputs.html"; sourceTree = "<group>"; };
9361002814DC957B0061379D /* lots-of-iframes.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = "lots-of-iframes.html"; sourceTree = "<group>"; };
93625D261CD973AF006DC1F1 /* large-video-without-audio.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = "large-video-without-audio.html"; sourceTree = "<group>"; };
@@ -2604,6 +2606,7 @@
9310CD361EF708FB0050FFE0 /* Function.cpp */,
83DB79671EF63B3C00BFA5E5 /* Function.cpp */,
7A38D7E51C752D5F004F157D /* HashCountedSet.cpp */,
+ 933D631B1FCB76180032ECD6 /* Hasher.cpp */,
0BCD833414857CE400EA2003 /* HashMap.cpp */,
26B2DFF815BDE599004F691D /* HashSet.cpp */,
266FAFD215E5775200F61D5B /* IntegerToStringConversion.cpp */,
@@ -3164,6 +3167,7 @@
AD7C434D1DD2A54E0026888B /* Expected.cpp in Sources */,
9310CD381EF708FB0050FFE0 /* Function.cpp in Sources */,
6BFD294C1D5E6C1D008EC968 /* HashCountedSet.cpp in Sources */,
+ 933D631D1FCB76200032ECD6 /* Hasher.cpp in Sources */,
7C83DED21D0A590C00FEBCF3 /* HashMap.cpp in Sources */,
7C83DED41D0A590C00FEBCF3 /* HashSet.cpp in Sources */,
7C83DEE01D0A590C00FEBCF3 /* IntegerToStringConversion.cpp in Sources */,
Added: trunk/Tools/TestWebKitAPI/Tests/WTF/Hasher.cpp (0 => 225463)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/Hasher.cpp (rev 0)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/Hasher.cpp 2017-12-03 22:48:40 UTC (rev 225463)
@@ -0,0 +1,251 @@
+/*
+ * Copyright (C) 2017 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. 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 INC. 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.
+ */
+
+#include "config.h"
+
+#include <array>
+#include <limits>
+#include <wtf/Hasher.h>
+#include <wtf/Optional.h>
+#include <wtf/Vector.h>
+
+namespace TestWebKitAPI {
+
+// Test against actual hash values.
+// We don't really depend on specific values, but it makes testing simpler.
+// Could instead construct tests that check hashes against each other.
+// No big deal to update all of these if we change the hash algorithm.
+
+const uint32_t emptyHash = 82610334U;
+const uint32_t zero32BitHash = 242183504U;
+const uint32_t zero64BitHash = 579236260U;
+const uint32_t _one32BitHash_ = 690138192U;
+const uint32_t _one64BitHash_ = 1621454911U;
+
+TEST(WTF, Hasher_integer)
+{
+ EXPECT_EQ(zero32BitHash, computeHash(0U));
+ EXPECT_EQ(zero32BitHash, computeHash(false));
+ EXPECT_EQ(zero32BitHash, computeHash(static_cast<char>(0)));
+ EXPECT_EQ(zero32BitHash, computeHash(static_cast<int8_t>(0)));
+ EXPECT_EQ(zero32BitHash, computeHash(static_cast<uint8_t>(0)));
+ EXPECT_EQ(zero32BitHash, computeHash(static_cast<int16_t>(0)));
+ EXPECT_EQ(zero32BitHash, computeHash(static_cast<uint16_t>(0)));
+ EXPECT_EQ(zero32BitHash, computeHash(0));
+
+ EXPECT_EQ(zero64BitHash, computeHash(0ULL));
+ EXPECT_EQ(zero64BitHash, computeHash(0L));
+ EXPECT_EQ(zero64BitHash, computeHash(0UL));
+ EXPECT_EQ(zero64BitHash, computeHash(0LL));
+
+ EXPECT_EQ(one32BitHash, computeHash(1U));
+ EXPECT_EQ(one32BitHash, computeHash(true));
+ EXPECT_EQ(one32BitHash, computeHash(static_cast<char>(1)));
+ EXPECT_EQ(one32BitHash, computeHash(static_cast<int8_t>(1)));
+ EXPECT_EQ(one32BitHash, computeHash(static_cast<uint8_t>(1)));
+ EXPECT_EQ(one32BitHash, computeHash(static_cast<int16_t>(1)));
+ EXPECT_EQ(one32BitHash, computeHash(static_cast<uint16_t>(1)));
+ EXPECT_EQ(one32BitHash, computeHash(1));
+
+ EXPECT_EQ(one64BitHash, computeHash(1ULL));
+ EXPECT_EQ(one64BitHash, computeHash(1L));
+ EXPECT_EQ(one64BitHash, computeHash(1UL));
+ EXPECT_EQ(one64BitHash, computeHash(1LL));
+
+ EXPECT_EQ(1772381661U, computeHash(0x7FU));
+ EXPECT_EQ(1772381661U, computeHash(std::numeric_limits<int8_t>::max()));
+
+ EXPECT_EQ(3730877340U, computeHash(0x80U));
+ EXPECT_EQ(3730877340U, computeHash(std::numeric_limits<int8_t>::min()));
+
+ EXPECT_EQ(376510634U, computeHash(0xFFU));
+ EXPECT_EQ(376510634U, computeHash(std::numeric_limits<uint8_t>::max()));
+ EXPECT_EQ(376510634U, computeHash(static_cast<char>(-1)));
+ EXPECT_EQ(376510634U, computeHash(static_cast<int8_t>(-1)));
+
+ EXPECT_EQ(262632278U, computeHash(0x7FFFU));
+ EXPECT_EQ(262632278U, computeHash(std::numeric_limits<int16_t>::max()));
+
+ EXPECT_EQ(2981978661U, computeHash(0x8000U));
+ EXPECT_EQ(2981978661U, computeHash(std::numeric_limits<int16_t>::min()));
+
+ EXPECT_EQ(894984179U, computeHash(0xFFFFU));
+ EXPECT_EQ(894984179U, computeHash(std::numeric_limits<uint16_t>::max()));
+ EXPECT_EQ(894984179U, computeHash(static_cast<int16_t>(-1)));
+
+ EXPECT_EQ(3430670328U, computeHash(0x7FFFFFFFU));
+ EXPECT_EQ(3430670328U, computeHash(std::numeric_limits<int32_t>::max()));
+
+ EXPECT_EQ(2425683428U, computeHash(0x80000000U));
+ EXPECT_EQ(2425683428U, computeHash(std::numeric_limits<int32_t>::min()));
+
+ EXPECT_EQ(1955511435U, computeHash(0xFFFFFFFFU));
+ EXPECT_EQ(1955511435U, computeHash(std::numeric_limits<uint32_t>::max()));
+ EXPECT_EQ(1955511435U, computeHash(-1));
+
+ EXPECT_EQ(1264532604U, computeHash(0x8000000000000000ULL));
+ EXPECT_EQ(1264532604U, computeHash(std::numeric_limits<int64_t>::min()));
+ EXPECT_EQ(1264532604U, computeHash(std::numeric_limits<long>::min()));
+
+ EXPECT_EQ(2961049834U, computeHash(0x7FFFFFFFFFFFFFFFULL));
+ EXPECT_EQ(2961049834U, computeHash(std::numeric_limits<int64_t>::max()));
+ EXPECT_EQ(2961049834U, computeHash(std::numeric_limits<long>::max()));
+
+ EXPECT_EQ(1106332091U, computeHash(0xFFFFFFFFFFFFFFFFULL));
+ EXPECT_EQ(1106332091U, computeHash(std::numeric_limits<uint64_t>::max()));
+ EXPECT_EQ(1106332091U, computeHash(std::numeric_limits<unsigned long>::max()));
+ EXPECT_EQ(1106332091U, computeHash(-1L));
+ EXPECT_EQ(1106332091U, computeHash(-1LL));
+}
+
+TEST(WTF, Hasher_floatingPoint)
+{
+ EXPECT_EQ(zero64BitHash, computeHash(0.0));
+ EXPECT_EQ(1264532604U, computeHash(-0.0)); // Note, not same as hash of 0.0.
+ EXPECT_EQ(one64BitHash, computeHash(std::numeric_limits<double>::denorm_min()));
+
+ EXPECT_EQ(2278399980U, computeHash(1.0));
+ EXPECT_EQ(3870689297U, computeHash(-1.0));
+
+ EXPECT_EQ(3016344414U, computeHash(std::numeric_limits<double>::min()));
+ EXPECT_EQ(1597662982U, computeHash(std::numeric_limits<double>::max()));
+
+ EXPECT_EQ(2501702556U, computeHash(std::numeric_limits<double>::lowest()));
+ EXPECT_EQ(2214439802U, computeHash(std::numeric_limits<double>::epsilon()));
+
+ EXPECT_EQ(2678086759U, computeHash(std::numeric_limits<double>::quiet_NaN()));
+ EXPECT_EQ(2304445393U, computeHash(std::numeric_limits<double>::infinity()));
+ EXPECT_EQ(2232593311U, computeHash(-std::numeric_limits<double>::infinity()));
+
+ EXPECT_EQ(zero32BitHash, computeHash(0.0f));
+ EXPECT_EQ(2425683428U, computeHash(-0.0f)); // Note, not same as hash of 0.0f.
+ EXPECT_EQ(one32BitHash, computeHash(std::numeric_limits<float>::denorm_min()));
+
+ EXPECT_EQ(1081575966U, computeHash(1.0f));
+ EXPECT_EQ(3262093188U, computeHash(-1.0f));
+
+ EXPECT_EQ(3170189524U, computeHash(std::numeric_limits<float>::min()));
+ EXPECT_EQ(11021299U, computeHash(std::numeric_limits<float>::max()));
+
+ EXPECT_EQ(3212069506U, computeHash(std::numeric_limits<float>::lowest()));
+ EXPECT_EQ(1308784506U, computeHash(std::numeric_limits<float>::epsilon()));
+
+ EXPECT_EQ(2751288511U, computeHash(std::numeric_limits<float>::quiet_NaN()));
+ EXPECT_EQ(3457049256U, computeHash(std::numeric_limits<float>::infinity()));
+ EXPECT_EQ(4208873971U, computeHash(-std::numeric_limits<float>::infinity()));
+}
+
+TEST(WTF, Hasher_multiple)
+{
+ EXPECT_EQ(emptyHash, computeHash());
+ EXPECT_EQ(emptyHash, computeHash(std::make_tuple()));
+ EXPECT_EQ(emptyHash, computeHash(std::array<int, 0> { }));
+ EXPECT_EQ(emptyHash, computeHash(Vector<int> { }));
+ EXPECT_EQ(emptyHash, computeHash(Vector<int, 1> { }));
+
+ EXPECT_EQ(zero32BitHash, computeHash(std::array<int, 1> { { 0 } }));
+ EXPECT_EQ(zero32BitHash, computeHash(Vector<int> { 0 }));
+ EXPECT_EQ(zero32BitHash, computeHash(Vector<int, 1> { 0 }));
+ EXPECT_EQ(zero32BitHash, computeHash(std::optional<int> { std::nullopt }));
+
+ EXPECT_EQ(one64BitHash, computeHash(1, 0));
+ EXPECT_EQ(one64BitHash, computeHash(std::make_tuple(1, 0)));
+ EXPECT_EQ(one64BitHash, computeHash(std::make_pair(1, 0)));
+ EXPECT_EQ(one64BitHash, computeHash(std::array<int, 2> { { 1, 0 } }));
+ EXPECT_EQ(one64BitHash, computeHash({ 1, 0 }));
+ EXPECT_EQ(one64BitHash, computeHash(std::optional<int> { 0 }));
+ EXPECT_EQ(one64BitHash, computeHash(Vector<int> { { 1, 0 } }));
+ EXPECT_EQ(one64BitHash, computeHash(Vector<int, 1> { { 1, 0 } }));
+
+ EXPECT_EQ(one64BitHash, computeHash(std::make_tuple(1), std::array<int, 1> { { 0 } }));
+ EXPECT_EQ(one64BitHash, computeHash(std::make_tuple(std::make_tuple(1), std::array<int, 1> { { 0 } })));
+
+ EXPECT_EQ(1652352321U, computeHash(1, 2, 3, 4));
+ EXPECT_EQ(1652352321U, computeHash(std::make_tuple(1, 2, 3, 4)));
+ EXPECT_EQ(1652352321U, computeHash(std::make_pair(std::make_pair(1, 2), std::make_pair(3, 4))));
+}
+
+struct HasherAddCustom1 { };
+
+void add(Hasher& hasher, const HasherAddCustom1&)
+{
+ add(hasher, 1, 2, 3, 4);
+}
+
+struct HasherAddCustom2 { };
+
+void add(Hasher& hasher, const HasherAddCustom2&)
+{
+ add(hasher, { 1, 2, 3, 4 });
+}
+
+TEST(WTF, Hasher_custom)
+{
+ EXPECT_EQ(1652352321U, computeHash(HasherAddCustom1 { }));
+ EXPECT_EQ(1652352321U, computeHash(HasherAddCustom2 { }));
+}
+
+#if 0 // FIXME: Add support for tuple-like classes.
+
+struct HasherAddTupleLikeClass1 {
+ std::array<int, 4> array { { 1, 2, 3, 4 } };
+ template<size_t i> int get() const { return std::get<i>(array); }
+};
+
+struct HasherAddTupleLikeClass2 {
+ std::array<int, 4> array { { 1, 2, 3, 4 } };
+};
+
+}
+
+namespace std {
+
+// FIXME: Documentation at cppreference.cpp says std::tuple_size is a struct, but it's a class in current macOS tools.
+// FIXME: It's inelegant to inject this into the std namespace. Is that really how a tuple-like class needs to be defined?
+// FIXME: This is so inconvenient that I am not sure it's something we want to do for lots of classes in WebKit.
+template<> class std::tuple_size<TestWebKitAPI::HasherAddTupleLikeClass1> : public std::integral_constant<size_t, std::tuple_size<decltype(TestWebKitAPI::HasherAddTupleLikeClass1::array)>::value> { };
+
+template<> class std::tuple_size<TestWebKitAPI::HasherAddTupleLikeClass2> : public std::integral_constant<size_t, std::tuple_size<decltype(TestWebKitAPI::HasherAddTupleLikeClass2::array)>::value> { };
+
+}
+
+namespace TestWebKitAPI {
+
+// FIXME: Is it OK for the get to be in the class's namespace and rely on argument-dependent lookup?
+// Or does this function template need to be moved into the std namespace like the tuple_size specialization?
+template<size_t i> int get(const HasherAddTupleLikeClass2& object)
+{
+ return get<i>(object.array);
+}
+
+TEST(WTF, Hasher_tupleLike)
+{
+ EXPECT_EQ(1652352321U, computeHash(HasherAddTupleLikeClass1 { }));
+ EXPECT_EQ(1652352321U, computeHash(HasherAddTupleLikeClass2 { }));
+}
+
+#endif
+
+} // namespace TestWebKitAPI
Property changes on: trunk/Tools/TestWebKitAPI/Tests/WTF/Hasher.cpp
___________________________________________________________________
Added: svn:eol-style
+native
\ No newline at end of property
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/StringHasher.cpp (225462 => 225463)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/StringHasher.cpp 2017-12-03 22:24:45 UTC (rev 225462)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/StringHasher.cpp 2017-12-03 22:48:40 UTC (rev 225463)
@@ -25,7 +25,7 @@
#include "config.h"
-#include <wtf/Hasher.h>
+#include <wtf/text/StringHasher.h>
namespace TestWebKitAPI {
