1/*
2 * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Library General Public License for more details.
13 *
14 * You should have received a copy of the GNU Library General Public License
15 * along with this library; see the file COPYING.LIB. If not, write to
16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 *
19 */
20
21#pragma once
22
23#include <wtf/Forward.h>
24#include <wtf/Optional.h>
25#include <wtf/StdLibExtras.h>
26#include <wtf/text/StringHasher.h>
27
28namespace WTF {
29
30// Deprecated. Use Hasher instead.
31class IntegerHasher {
32public:
33 void add(uint32_t integer)
34 {
35 m_underlyingHasher.addCharactersAssumingAligned(integer, integer >> 16);
36 }
37
38 unsigned hash() const
39 {
40 return m_underlyingHasher.hash();
41 }
42
43private:
44 StringHasher m_underlyingHasher;
45};
46
47template<typename... Types> uint32_t computeHash(const Types&...);
48template<typename T, typename... OtherTypes> uint32_t computeHash(std::initializer_list<T>, std::initializer_list<OtherTypes>...);
49
50class Hasher {
51public:
52 template<typename... Types> friend uint32_t computeHash(const Types&... values)
53 {
54 Hasher hasher;
55 addArgs(hasher, values...);
56 return hasher.m_underlyingHasher.hash();
57 }
58
59 template<typename T, typename... OtherTypes> friend uint32_t computeHash(std::initializer_list<T> list, std::initializer_list<OtherTypes>... otherLists)
60 {
61 Hasher hasher;
62 add(hasher, list);
63 addArgs(hasher, otherLists...);
64 return hasher.m_underlyingHasher.hash();
65 }
66
67 template<typename UnsignedInteger> friend std::enable_if_t<std::is_unsigned<UnsignedInteger>::value && sizeof(UnsignedInteger) <= sizeof(uint32_t), void> add(Hasher& hasher, UnsignedInteger integer)
68 {
69 // We can consider adding a more efficient code path for hashing booleans or individual bytes if needed.
70 // We can consider adding a more efficient code path for hashing 16-bit values if needed, perhaps using addCharacter,
71 // but getting rid of "assuming aligned" would make hashing values 32-bit or larger slower.
72 uint32_t sizedInteger = integer;
73 hasher.m_underlyingHasher.addCharactersAssumingAligned(sizedInteger, sizedInteger >> 16);
74 }
75
76private:
77 StringHasher m_underlyingHasher;
78};
79
80template<typename UnsignedInteger> std::enable_if_t<std::is_unsigned<UnsignedInteger>::value && sizeof(UnsignedInteger) == sizeof(uint64_t), void> add(Hasher& hasher, UnsignedInteger integer)
81{
82 add(hasher, static_cast<uint32_t>(integer));
83 add(hasher, static_cast<uint32_t>(integer >> 32));
84}
85
86template<typename SignedArithmetic> std::enable_if_t<std::is_signed<SignedArithmetic>::value, void> add(Hasher& hasher, SignedArithmetic number)
87{
88 // We overloaded for double and float below, just deal with integers here.
89 add(hasher, static_cast<std::make_unsigned_t<SignedArithmetic>>(number));
90}
91
92inline void add(Hasher& hasher, double number)
93{
94 add(hasher, bitwise_cast<uint64_t>(number));
95}
96
97inline void add(Hasher& hasher, float number)
98{
99 add(hasher, bitwise_cast<uint32_t>(number));
100}
101
102template<typename Enumeration> std::enable_if_t<std::is_enum<Enumeration>::value, void> add(Hasher& hasher, Enumeration value)
103{
104 add(hasher, static_cast<std::underlying_type_t<Enumeration>>(value));
105}
106
107template<typename> struct TypeCheckHelper { };
108template<typename, typename = void> struct HasBeginFunctionMember : std::false_type { };
109template<typename Container> struct HasBeginFunctionMember<Container, std::conditional_t<false, TypeCheckHelper<decltype(std::declval<Container>().begin())>, void>> : std::true_type { };
110
111template<typename Container> std::enable_if_t<HasBeginFunctionMember<Container>::value, void> add(Hasher& hasher, const Container& container)
112{
113 for (const auto& value : container)
114 add(hasher, value);
115}
116
117inline void addArgs(Hasher&)
118{
119}
120
121template<typename Arg, typename ...Args> void addArgs(Hasher& hasher, const Arg& arg, const Args&... args)
122{
123 add(hasher, arg);
124 addArgs(hasher, args...);
125}
126
127template<typename Tuple, std::size_t ...i> void addTupleHelper(Hasher& hasher, const Tuple& values, std::index_sequence<i...>)
128{
129 addArgs(hasher, std::get<i>(values)...);
130}
131
132template<typename... Types> void add(Hasher& hasher, const std::tuple<Types...>& tuple)
133{
134 addTupleHelper(hasher, tuple, std::make_index_sequence<std::tuple_size<std::tuple<Types...>>::value> { });
135}
136
137template<typename T1, typename T2> void add(Hasher& hasher, const std::pair<T1, T2>& pair)
138{
139 add(hasher, pair.first);
140 add(hasher, pair.second);
141}
142
143template<typename T> void add(Hasher& hasher, const Optional<T>& optional)
144{
145 add(hasher, optional.hasValue());
146 if (optional.hasValue())
147 add(hasher, optional.value());
148}
149
150template<typename... Types> void add(Hasher& hasher, const Variant<Types...>& variant)
151{
152 add(hasher, variant.index());
153 visit([&hasher] (auto& value) {
154 add(hasher, value);
155 }, variant);
156}
157
158template<typename T1, typename T2, typename... OtherTypes> void add(Hasher& hasher, const T1& value1, const T2& value2, const OtherTypes&... otherValues)
159{
160 add(hasher, value1);
161 add(hasher, value2);
162 addArgs(hasher, otherValues...);
163}
164
165template<typename T> void add(Hasher& hasher, std::initializer_list<T> values)
166{
167 for (auto& value : values)
168 add(hasher, value);
169}
170
171} // namespace WTF
172
173using WTF::computeHash;
174using WTF::Hasher;
175using WTF::IntegerHasher;
176