Change a couple of HashMap value types from OwnPtr to std::unique_ptr
[WebKit-https.git] / Source / WTF / wtf / StdLibExtras.h
1 /*
2  * Copyright (C) 2008 Apple Inc. All Rights Reserved.
3  * Copyright (C) 2013 Patrick Gansterer <paroga@paroga.com>
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
25  */
26
27 #ifndef WTF_StdLibExtras_h
28 #define WTF_StdLibExtras_h
29
30 #include <memory>
31 #include <wtf/Assertions.h>
32 #include <wtf/CheckedArithmetic.h>
33
34 // Use these to declare and define a static local variable (static T;) so that
35 //  it is leaked so that its destructors are not called at exit. Using this
36 //  macro also allows workarounds a compiler bug present in Apple's version of GCC 4.0.1.
37 #ifndef DEFINE_STATIC_LOCAL
38 #if COMPILER(GCC) && defined(__APPLE_CC__) && __GNUC__ == 4 && __GNUC_MINOR__ == 0 && __GNUC_PATCHLEVEL__ == 1
39 #define DEFINE_STATIC_LOCAL(type, name, arguments) \
40     static type* name##Ptr = new type arguments; \
41     type& name = *name##Ptr
42 #else
43 #define DEFINE_STATIC_LOCAL(type, name, arguments) \
44     static type& name = *new type arguments
45 #endif
46 #endif
47
48 // Use this macro to declare and define a debug-only global variable that may have a
49 // non-trivial constructor and destructor. When building with clang, this will suppress
50 // warnings about global constructors and exit-time destructors.
51 #ifndef NDEBUG
52 #if COMPILER(CLANG)
53 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
54     _Pragma("clang diagnostic push") \
55     _Pragma("clang diagnostic ignored \"-Wglobal-constructors\"") \
56     _Pragma("clang diagnostic ignored \"-Wexit-time-destructors\"") \
57     static type name arguments; \
58     _Pragma("clang diagnostic pop")
59 #else
60 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
61     static type name arguments;
62 #endif // COMPILER(CLANG)
63 #else
64 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments)
65 #endif // NDEBUG
66
67 // OBJECT_OFFSETOF: Like the C++ offsetof macro, but you can use it with classes.
68 // The magic number 0x4000 is insignificant. We use it to avoid using NULL, since
69 // NULL can cause compiler problems, especially in cases of multiple inheritance.
70 #define OBJECT_OFFSETOF(class, field) (reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<class*>(0x4000)->field)) - 0x4000)
71
72 // STRINGIZE: Can convert any value to quoted string, even expandable macros
73 #define STRINGIZE(exp) #exp
74 #define STRINGIZE_VALUE_OF(exp) STRINGIZE(exp)
75
76 /*
77  * The reinterpret_cast<Type1*>([pointer to Type2]) expressions - where
78  * sizeof(Type1) > sizeof(Type2) - cause the following warning on ARM with GCC:
79  * increases required alignment of target type.
80  *
81  * An implicit or an extra static_cast<void*> bypasses the warning.
82  * For more info see the following bugzilla entries:
83  * - https://bugs.webkit.org/show_bug.cgi?id=38045
84  * - http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43976
85  */
86 #if (CPU(ARM) || CPU(MIPS)) && COMPILER(GCC)
87 template<typename Type>
88 bool isPointerTypeAlignmentOkay(Type* ptr)
89 {
90     return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
91 }
92
93 template<typename TypePtr>
94 TypePtr reinterpret_cast_ptr(void* ptr)
95 {
96     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
97     return reinterpret_cast<TypePtr>(ptr);
98 }
99
100 template<typename TypePtr>
101 TypePtr reinterpret_cast_ptr(const void* ptr)
102 {
103     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
104     return reinterpret_cast<TypePtr>(ptr);
105 }
106 #else
107 template<typename Type>
108 bool isPointerTypeAlignmentOkay(Type*)
109 {
110     return true;
111 }
112 #define reinterpret_cast_ptr reinterpret_cast
113 #endif
114
115 namespace WTF {
116
117 static const size_t KB = 1024;
118 static const size_t MB = 1024 * 1024;
119
120 inline bool isPointerAligned(void* p)
121 {
122     return !((intptr_t)(p) & (sizeof(char*) - 1));
123 }
124
125 inline bool is8ByteAligned(void* p)
126 {
127     return !((uintptr_t)(p) & (sizeof(double) - 1));
128 }
129
130 /*
131  * C++'s idea of a reinterpret_cast lacks sufficient cojones.
132  */
133 template<typename ToType, typename FromType>
134 inline ToType bitwise_cast(FromType from)
135 {
136     static_assert(sizeof(FromType) == sizeof(ToType), "bitwise_cast size of FromType and ToType must be equal!");
137     union {
138         FromType from;
139         ToType to;
140     } u;
141     u.from = from;
142     return u.to;
143 }
144
145 template<typename ToType, typename FromType>
146 inline ToType safeCast(FromType value)
147 {
148     ASSERT(isInBounds<ToType>(value));
149     return static_cast<ToType>(value);
150 }
151
152 // Returns a count of the number of bits set in 'bits'.
153 inline size_t bitCount(unsigned bits)
154 {
155     bits = bits - ((bits >> 1) & 0x55555555);
156     bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
157     return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
158 }
159
160 // Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array.
161 template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size];
162 // GCC needs some help to deduce a 0 length array.
163 #if COMPILER(GCC)
164 template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0];
165 #endif
166 #define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array))
167
168 // Efficient implementation that takes advantage of powers of two.
169 inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
170 {
171     ASSERT(divisor && !(divisor & (divisor - 1)));
172     size_t remainderMask = divisor - 1;
173     return (x + remainderMask) & ~remainderMask;
174 }
175
176 template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x)
177 {
178     static_assert(divisor && !(divisor & (divisor - 1)), "divisor must be a power of two!");
179     return roundUpToMultipleOf(divisor, x);
180 }
181
182 enum BinarySearchMode {
183     KeyMustBePresentInArray,
184     KeyMightNotBePresentInArray,
185     ReturnAdjacentElementIfKeyIsNotPresent
186 };
187
188 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
189 inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
190 {
191     size_t offset = 0;
192     while (size > 1) {
193         size_t pos = (size - 1) >> 1;
194         KeyType val = extractKey(&array[offset + pos]);
195         
196         if (val == key)
197             return &array[offset + pos];
198         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
199         // chopping off the right hand half of the array.
200         if (key < val)
201             size = pos;
202         // Discard all values in the left hand half of the array, up to and including the item at pos.
203         else {
204             size -= (pos + 1);
205             offset += (pos + 1);
206         }
207
208         ASSERT(mode != KeyMustBePresentInArray || size);
209     }
210     
211     if (mode == KeyMightNotBePresentInArray && !size)
212         return 0;
213     
214     ArrayElementType* result = &array[offset];
215
216     if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
217         return 0;
218
219     if (mode == KeyMustBePresentInArray) {
220         ASSERT(size == 1);
221         ASSERT(key == extractKey(result));
222     }
223
224     return result;
225 }
226
227 // If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
228 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
229 inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
230 {
231     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
232 }
233
234 // Return zero if the element is not found.
235 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
236 inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
237 {
238     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
239 }
240
241 // Return the element that is either to the left, or the right, of where the element would have been found.
242 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
243 inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
244 {
245     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
246 }
247
248 // Variants of the above that use const.
249 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
250 inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
251 {
252     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
253 }
254 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
255 inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
256 {
257     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
258 }
259 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
260 inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
261 {
262     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
263 }
264
265 template<typename VectorType, typename ElementType>
266 inline void insertIntoBoundedVector(VectorType& vector, size_t size, const ElementType& element, size_t index)
267 {
268     for (size_t i = size; i-- > index + 1;)
269         vector[i] = vector[i - 1];
270     vector[index] = element;
271 }
272
273 } // namespace WTF
274
275 #if OS(WINCE)
276 // Windows CE CRT has does not implement bsearch().
277 inline void* wtf_bsearch(const void* key, const void* base, size_t count, size_t size, int (*compare)(const void *, const void *))
278 {
279     const char* first = static_cast<const char*>(base);
280
281     while (count) {
282         size_t pos = (count - 1) >> 1;
283         const char* item = first + pos * size;
284         int compareResult = compare(item, key);
285         if (!compareResult)
286             return const_cast<char*>(item);
287         if (compareResult < 0) {
288             count -= (pos + 1);
289             first += (pos + 1) * size;
290         } else
291             count = pos;
292     }
293
294     return 0;
295 }
296
297 #define bsearch(key, base, count, size, compare) wtf_bsearch(key, base, count, size, compare)
298 #endif
299
300 // This version of placement new omits a 0 check.
301 enum NotNullTag { NotNull };
302 inline void* operator new(size_t, NotNullTag, void* location)
303 {
304     ASSERT(location);
305     return location;
306 }
307
308
309 // This adds various C++14 features for versions of the STL that may not yet have them.
310 namespace std {
311     template<class T> struct _Unique_if {
312         typedef unique_ptr<T> _Single_object;
313     };
314
315     template<class T> struct _Unique_if<T[]> {
316         typedef unique_ptr<T[]> _Unknown_bound;
317     };
318
319     template<class T, size_t N> struct _Unique_if<T[N]> {
320         typedef void _Known_bound;
321     };
322
323 #if COMPILER_SUPPORTS(CXX_VARIADIC_TEMPLATES)
324     template<class T, class... Args> typename _Unique_if<T>::_Single_object
325     make_unique(Args&&... args)
326     {
327         return unique_ptr<T>(new T(std::forward<Args>(args)...));
328     }
329 #else
330     template<class T> typename _Unique_if<T>::_Single_object
331     make_unique()
332     {
333         return unique_ptr<T>(new T);
334     }
335
336     template<class T, class A1> typename _Unique_if<T>::_Single_object
337     make_unique(A1&& a1)
338     {
339         return unique_ptr<T>(new T(std::forward<A1>(a1)));
340     }
341
342     template<class T, class A1, class A2> typename _Unique_if<T>::_Single_object
343     make_unique(A1&& a1, A1&& a2)
344     {
345         return unique_ptr<T>(new T(std::forward<A1>(a1), std::forward<A2>(a2)));
346     }
347
348     template<class T, class A1, class A2, class A3> typename _Unique_if<T>::_Single_object
349     make_unique(A1&& a1, A1&& a2, A3&& a3)
350     {
351         return unique_ptr<T>(new T(std::forward<A1>(a1), std::forward<A2>(a2), std::forward<A3>(a3)));
352     }
353
354     template<class T, class A1, class A2, class A3, class A4> typename _Unique_if<T>::_Single_object
355     make_unique(A1&& a1, A1&& a2, A3&& a3, A4&& a4)
356     {
357         return unique_ptr<T>(new T(std::forward<A1>(a1), std::forward<A2>(a2), std::forward<A3>(a3), std::forward<A4>(a4)));
358     }
359
360     template<class T, class A1, class A2, class A3, class A4, class A5> typename _Unique_if<T>::_Single_object
361     make_unique(A1&& a1, A1&& a2, A3&& a3, A4&& a4, A5&& a5)
362     {
363         return unique_ptr<T>(new T(std::forward<A1>(a1), std::forward<A2>(a2), std::forward<A3>(a3), std::forward<A4>(a4), std::forward<A5>(a5)));
364     }
365
366     template<class T, class A1, class A2, class A3, class A4, class A5, class A6> typename _Unique_if<T>::_Single_object
367     make_unique(A1&& a1, A1&& a2, A3&& a3, A4&& a4, A5&& a5, A6&& a6)
368     {
369         return unique_ptr<T>(new T(std::forward<A1>(a1), std::forward<A2>(a2), std::forward<A3>(a3), std::forward<A4>(a4), std::forward<A5>(a5), std::forward<A6>(a6)));
370     }
371
372 #endif
373
374     template<class T> typename _Unique_if<T>::_Unknown_bound
375     make_unique(size_t n)
376     {
377         typedef typename remove_extent<T>::type U;
378         return unique_ptr<T>(new U[n]());
379     }
380     
381 #if COMPILER_SUPPORTS(CXX_VARIADIC_TEMPLATES)
382     template<class T, class... Args> typename _Unique_if<T>::_Known_bound
383     make_unique(Args&&...) = delete;
384 #endif
385
386 #if COMPILER_SUPPORTS(CXX_VARIADIC_TEMPLATES)
387     // Compile-time integer sequences
388     // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3658.html
389     // (Note that we only implement index_sequence, and not the more generic integer_sequence).
390     template<size_t... indexes> struct index_sequence {
391         static size_t size() { return sizeof...(indexes); }
392     };
393
394     template<size_t currentIndex, size_t...indexes> struct make_index_sequence_helper;
395
396     template<size_t...indexes> struct make_index_sequence_helper<0, indexes...> {
397         typedef std::index_sequence<indexes...> type;
398     };
399
400     template<size_t currentIndex, size_t...indexes> struct make_index_sequence_helper {
401         typedef typename make_index_sequence_helper<currentIndex - 1, currentIndex - 1, indexes...>::type type;
402     };
403
404     template<size_t length> struct make_index_sequence : public make_index_sequence_helper<length>::type { };
405 #endif
406 }
407
408 using WTF::KB;
409 using WTF::MB;
410 using WTF::insertIntoBoundedVector;
411 using WTF::isPointerAligned;
412 using WTF::is8ByteAligned;
413 using WTF::binarySearch;
414 using WTF::tryBinarySearch;
415 using WTF::approximateBinarySearch;
416 using WTF::bitwise_cast;
417 using WTF::safeCast;
418
419 #endif // WTF_StdLibExtras_h