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