bcd8d7b0028c04e40854a5ae4a7a4130a440c20f
[WebKit.git] / Source / WTF / wtf / HashTraits.h
1 /*
2  * Copyright (C) 2005-2018 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 #ifndef WTF_HashTraits_h
22 #define WTF_HashTraits_h
23
24 #include <limits>
25 #include <utility>
26 #include <wtf/Forward.h>
27 #include <wtf/HashFunctions.h>
28 #include <wtf/KeyValuePair.h>
29 #include <wtf/Optional.h>
30 #include <wtf/StdLibExtras.h>
31
32 namespace WTF {
33
34 template<bool isInteger, typename T> struct GenericHashTraitsBase;
35
36 template<typename T> struct GenericHashTraitsBase<false, T> {
37     // The emptyValueIsZero flag is used to optimize allocation of empty hash tables with zeroed memory.
38     static const bool emptyValueIsZero = false;
39     
40     // The hasIsEmptyValueFunction flag allows the hash table to automatically generate code to check
41     // for the empty value when it can be done with the equality operator, but allows custom functions
42     // for cases like String that need them.
43     static const bool hasIsEmptyValueFunction = false;
44
45     // The starting table size. Can be overridden when we know beforehand that
46     // a hash table will have at least N entries.
47     static const unsigned minimumTableSize = 8;
48 };
49
50 // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned).
51 template<typename T> struct GenericHashTraitsBase<true, T> : GenericHashTraitsBase<false, T> {
52     static const bool emptyValueIsZero = true;
53     static void constructDeletedValue(T& slot) { slot = static_cast<T>(-1); }
54     static bool isDeletedValue(T value) { return value == static_cast<T>(-1); }
55 };
56
57 template<typename T> struct GenericHashTraits : GenericHashTraitsBase<std::is_integral<T>::value, T> {
58     typedef T TraitType;
59     typedef T EmptyValueType;
60
61     static T emptyValue() { return T(); }
62
63     template<typename U, typename V> 
64     static void assignToEmpty(U& emptyValue, V&& value)
65     { 
66         emptyValue = std::forward<V>(value);
67     }
68
69     // Type for return value of functions that do not transfer ownership, such as get.
70     typedef T PeekType;
71     template<typename U> static U&& peek(U&& value) { return std::forward<U>(value); }
72
73     typedef T TakeType;
74     template<typename U> static TakeType take(U&& value) { return std::forward<U>(value); }
75 };
76
77 template<typename T> struct HashTraits : GenericHashTraits<T> { };
78
79 template<typename T> struct FloatHashTraits : GenericHashTraits<T> {
80     static T emptyValue() { return std::numeric_limits<T>::infinity(); }
81     static void constructDeletedValue(T& slot) { slot = -std::numeric_limits<T>::infinity(); }
82     static bool isDeletedValue(T value) { return value == -std::numeric_limits<T>::infinity(); }
83 };
84
85 template<> struct HashTraits<float> : FloatHashTraits<float> { };
86 template<> struct HashTraits<double> : FloatHashTraits<double> { };
87
88 // Default unsigned traits disallow both 0 and max as keys -- use these traits to allow zero and disallow max - 1.
89 template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTraits<T> {
90     static const bool emptyValueIsZero = false;
91     static T emptyValue() { return std::numeric_limits<T>::max(); }
92     static void constructDeletedValue(T& slot) { slot = std::numeric_limits<T>::max() - 1; }
93     static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max() - 1; }
94 };
95
96 template<typename T> struct SignedWithZeroKeyHashTraits : GenericHashTraits<T> {
97     static const bool emptyValueIsZero = false;
98     static T emptyValue() { return std::numeric_limits<T>::min(); }
99     static void constructDeletedValue(T& slot) { slot = std::numeric_limits<T>::max(); }
100     static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max(); }
101 };
102
103 // Can be used with strong enums, allows zero as key.
104 template<typename T> struct StrongEnumHashTraits : GenericHashTraits<T> {
105     using UnderlyingType = typename std::underlying_type<T>::type;
106     static const bool emptyValueIsZero = false;
107     static T emptyValue() { return static_cast<T>(std::numeric_limits<UnderlyingType>::max()); }
108     static void constructDeletedValue(T& slot) { slot = static_cast<T>(std::numeric_limits<UnderlyingType>::max() - 1); }
109     static bool isDeletedValue(T value) { return value == static_cast<T>(std::numeric_limits<UnderlyingType>::max() - 1); }
110 };
111
112 template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
113     static const bool emptyValueIsZero = true;
114     static void constructDeletedValue(P*& slot) { slot = reinterpret_cast<P*>(-1); }
115     static bool isDeletedValue(P* value) { return value == reinterpret_cast<P*>(-1); }
116 };
117
118 template<typename T> struct SimpleClassHashTraits : GenericHashTraits<T> {
119     static const bool emptyValueIsZero = true;
120     static void constructDeletedValue(T& slot) { new (NotNull, std::addressof(slot)) T(HashTableDeletedValue); }
121     static bool isDeletedValue(const T& value) { return value.isHashTableDeletedValue(); }
122 };
123
124 template<typename T, typename Deleter> struct HashTraits<std::unique_ptr<T, Deleter>> : SimpleClassHashTraits<std::unique_ptr<T, Deleter>> {
125     typedef std::nullptr_t EmptyValueType;
126     static EmptyValueType emptyValue() { return nullptr; }
127
128     static void constructDeletedValue(std::unique_ptr<T, Deleter>& slot) { new (NotNull, std::addressof(slot)) std::unique_ptr<T, Deleter> { reinterpret_cast<T*>(-1) }; }
129     static bool isDeletedValue(const std::unique_ptr<T, Deleter>& value) { return value.get() == reinterpret_cast<T*>(-1); }
130
131     typedef T* PeekType;
132     static T* peek(const std::unique_ptr<T, Deleter>& value) { return value.get(); }
133     static T* peek(std::nullptr_t) { return nullptr; }
134
135     static void customDeleteBucket(std::unique_ptr<T, Deleter>& value)
136     {
137         // The custom delete function exists to avoid a dead store before the value is destructed.
138         // The normal destruction sequence of a bucket would be:
139         // 1) Call the destructor of unique_ptr.
140         // 2) unique_ptr store a zero for its internal pointer.
141         // 3) unique_ptr destroys its value.
142         // 4) Call constructDeletedValue() to set the bucket as destructed.
143         //
144         // The problem is the call in (3) prevents the compile from eliminating the dead store in (2)
145         // becase a side effect of free() could be observing the value.
146         //
147         // This version of deleteBucket() ensures the dead 2 stores changing "value"
148         // are on the same side of the function call.
149         ASSERT(!isDeletedValue(value));
150         T* pointer = value.release();
151         constructDeletedValue(value);
152
153         // The null case happens if a caller uses std::move() to remove the pointer before calling remove()
154         // with an iterator. This is very uncommon.
155         if (LIKELY(pointer))
156             Deleter()(pointer);
157     }
158 };
159
160 template<typename P> struct HashTraits<RefPtr<P>> : SimpleClassHashTraits<RefPtr<P>> {
161     static P* emptyValue() { return nullptr; }
162
163     typedef P* PeekType;
164     static PeekType peek(const RefPtr<P>& value) { return value.get(); }
165     static PeekType peek(P* value) { return value; }
166
167     static void customDeleteBucket(RefPtr<P>& value)
168     {
169         // See unique_ptr's customDeleteBucket() for an explanation.
170         ASSERT(!SimpleClassHashTraits<RefPtr<P>>::isDeletedValue(value));
171         auto valueToBeDestroyed = WTFMove(value);
172         SimpleClassHashTraits<RefPtr<P>>::constructDeletedValue(value);
173     }
174 };
175
176 template<typename P> struct HashTraits<Ref<P>> : SimpleClassHashTraits<Ref<P>> {
177     static const bool emptyValueIsZero = true;
178     static Ref<P> emptyValue() { return HashTableEmptyValue; }
179
180     static const bool hasIsEmptyValueFunction = true;
181     static bool isEmptyValue(const Ref<P>& value) { return value.isHashTableEmptyValue(); }
182
183     static void assignToEmpty(Ref<P>& emptyValue, Ref<P>&& newValue) { ASSERT(isEmptyValue(emptyValue)); emptyValue.assignToHashTableEmptyValue(WTFMove(newValue)); }
184
185     typedef P* PeekType;
186     static PeekType peek(const Ref<P>& value) { return const_cast<PeekType>(value.ptrAllowingHashTableEmptyValue()); }
187     static PeekType peek(P* value) { return value; }
188
189     typedef std::optional<Ref<P>> TakeType;
190     static TakeType take(Ref<P>&& value) { return isEmptyValue(value) ? std::nullopt : std::optional<Ref<P>>(WTFMove(value)); }
191 };
192
193 template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
194     static const bool hasIsEmptyValueFunction = true;
195     static bool isEmptyValue(const String&);
196
197     static void customDeleteBucket(String&);
198 };
199
200 // This struct template is an implementation detail of the isHashTraitsEmptyValue function,
201 // which selects either the emptyValue function or the isEmptyValue function to check for empty values.
202 template<typename Traits, bool hasEmptyValueFunction> struct HashTraitsEmptyValueChecker;
203 template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, true> {
204     template<typename T> static bool isEmptyValue(const T& value) { return Traits::isEmptyValue(value); }
205 };
206 template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, false> {
207     template<typename T> static bool isEmptyValue(const T& value) { return value == Traits::emptyValue(); }
208 };
209 template<typename Traits, typename T> inline bool isHashTraitsEmptyValue(const T& value)
210 {
211     return HashTraitsEmptyValueChecker<Traits, Traits::hasIsEmptyValueFunction>::isEmptyValue(value);
212 }
213
214 template<typename Traits, typename T>
215 struct HashTraitHasCustomDelete {
216     static T& bucketArg;
217     template<typename X> static std::true_type TestHasCustomDelete(X*, decltype(X::customDeleteBucket(bucketArg))* = nullptr);
218     static std::false_type TestHasCustomDelete(...);
219     typedef decltype(TestHasCustomDelete(static_cast<Traits*>(nullptr))) ResultType;
220     static const bool value = ResultType::value;
221 };
222
223 template<typename Traits, typename T>
224 typename std::enable_if<HashTraitHasCustomDelete<Traits, T>::value>::type
225 hashTraitsDeleteBucket(T& value)
226 {
227     Traits::customDeleteBucket(value);
228 }
229
230 template<typename Traits, typename T>
231 typename std::enable_if<!HashTraitHasCustomDelete<Traits, T>::value>::type
232 hashTraitsDeleteBucket(T& value)
233 {
234     value.~T();
235     Traits::constructDeletedValue(value);
236 }
237
238 template<typename FirstTraitsArg, typename SecondTraitsArg>
239 struct PairHashTraits : GenericHashTraits<std::pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType>> {
240     typedef FirstTraitsArg FirstTraits;
241     typedef SecondTraitsArg SecondTraits;
242     typedef std::pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
243     typedef std::pair<typename FirstTraits::EmptyValueType, typename SecondTraits::EmptyValueType> EmptyValueType;
244
245     static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
246     static EmptyValueType emptyValue() { return std::make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
247
248     static const unsigned minimumTableSize = FirstTraits::minimumTableSize;
249
250     static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); }
251     static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); }
252 };
253
254 template<typename First, typename Second>
255 struct HashTraits<std::pair<First, Second>> : public PairHashTraits<HashTraits<First>, HashTraits<Second>> { };
256
257 template<typename FirstTrait, typename... Traits>
258 struct TupleHashTraits : GenericHashTraits<std::tuple<typename FirstTrait::TraitType, typename Traits::TraitType...>> {
259     typedef std::tuple<typename FirstTrait::TraitType, typename Traits::TraitType...> TraitType;
260     typedef std::tuple<typename FirstTrait::EmptyValueType, typename Traits::EmptyValueType...> EmptyValueType;
261
262     // We should use emptyValueIsZero = Traits::emptyValueIsZero &&... whenever we switch to C++17. We can't do anything
263     // better here right now because GCC can't do C++.
264     template<typename BoolType>
265     static constexpr bool allTrue(BoolType value) { return value; }
266     template<typename BoolType, typename... BoolTypes>
267     static constexpr bool allTrue(BoolType value, BoolTypes... values) { return value && allTrue(values...); }
268     static const bool emptyValueIsZero = allTrue(FirstTrait::emptyValueIsZero, Traits::emptyValueIsZero...);
269     static EmptyValueType emptyValue() { return std::make_tuple(FirstTrait::emptyValue(), Traits::emptyValue()...); }
270
271     static const unsigned minimumTableSize = FirstTrait::minimumTableSize;
272
273     static void constructDeletedValue(TraitType& slot) { FirstTrait::constructDeletedValue(std::get<0>(slot)); }
274     static bool isDeletedValue(const TraitType& value) { return FirstTrait::isDeletedValue(std::get<0>(value)); }
275 };
276
277 template<typename... Traits>
278 struct HashTraits<std::tuple<Traits...>> : public TupleHashTraits<HashTraits<Traits>...> { };
279
280 template<typename KeyTraitsArg, typename ValueTraitsArg>
281 struct KeyValuePairHashTraits : GenericHashTraits<KeyValuePair<typename KeyTraitsArg::TraitType, typename ValueTraitsArg::TraitType>> {
282     typedef KeyTraitsArg KeyTraits;
283     typedef ValueTraitsArg ValueTraits;
284     typedef KeyValuePair<typename KeyTraits::TraitType, typename ValueTraits::TraitType> TraitType;
285     typedef KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType> EmptyValueType;
286     typedef typename ValueTraitsArg::TraitType ValueType;
287
288     static const bool emptyValueIsZero = KeyTraits::emptyValueIsZero && ValueTraits::emptyValueIsZero;
289     static EmptyValueType emptyValue() { return KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType>(KeyTraits::emptyValue(), ValueTraits::emptyValue()); }
290
291     static const unsigned minimumTableSize = KeyTraits::minimumTableSize;
292
293     static void constructDeletedValue(TraitType& slot) { KeyTraits::constructDeletedValue(slot.key); }
294     static bool isDeletedValue(const TraitType& value) { return KeyTraits::isDeletedValue(value.key); }
295
296     static void customDeleteBucket(TraitType& value)
297     {
298         static_assert(std::is_trivially_destructible<KeyValuePair<int, int>>::value,
299             "The wrapper itself has to be trivially destructible for customDeleteBucket() to make sense, since we do not destruct the wrapper itself.");
300
301         hashTraitsDeleteBucket<KeyTraits>(value.key);
302         value.value.~ValueType();
303     }
304 };
305
306 template<typename Key, typename Value>
307 struct HashTraits<KeyValuePair<Key, Value>> : public KeyValuePairHashTraits<HashTraits<Key>, HashTraits<Value>> { };
308
309 template<typename T>
310 struct NullableHashTraits : public HashTraits<T> {
311     static const bool emptyValueIsZero = false;
312     static T emptyValue() { return reinterpret_cast<T>(1); }
313 };
314
315 // Useful for classes that want complete control over what is empty and what is deleted,
316 // and how to construct both.
317 template<typename T>
318 struct CustomHashTraits : public GenericHashTraits<T> {
319     static const bool emptyValueIsZero = false;
320     static const bool hasIsEmptyValueFunction = true;
321     
322     static void constructDeletedValue(T& slot)
323     {
324         new (NotNull, std::addressof(slot)) T(T::DeletedValue);
325     }
326     
327     static bool isDeletedValue(const T& value)
328     {
329         return value.isDeletedValue();
330     }
331     
332     static T emptyValue()
333     {
334         return T(T::EmptyValue);
335     }
336     
337     static bool isEmptyValue(const T& value)
338     {
339         return value.isEmptyValue();
340     }
341 };
342
343 } // namespace WTF
344
345 using WTF::HashTraits;
346 using WTF::KeyValuePair;
347 using WTF::PairHashTraits;
348 using WTF::NullableHashTraits;
349 using WTF::SimpleClassHashTraits;
350
351 #endif // WTF_HashTraits_h