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