Add WTF::move()
[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 <chrono>
31 #include <memory>
32 #include <wtf/Assertions.h>
33 #include <wtf/CheckedArithmetic.h>
34
35 // This was used to declare and define a static local variable (static T;) so that
36 //  it was leaked so that its destructors were not called at exit. Using this
37 //  macro also allowed to workaround a compiler bug present in Apple's version of GCC 4.0.1.
38 //
39 // Newly written code should use static NeverDestroyed<T> instead.
40 #ifndef DEPRECATED_DEFINE_STATIC_LOCAL
41 #if COMPILER(GCC) && defined(__APPLE_CC__) && __GNUC__ == 4 && __GNUC_MINOR__ == 0 && __GNUC_PATCHLEVEL__ == 1
42 #define DEPRECATED_DEFINE_STATIC_LOCAL(type, name, arguments) \
43     static type* name##Ptr = new type arguments; \
44     type& name = *name##Ptr
45 #else
46 #define DEPRECATED_DEFINE_STATIC_LOCAL(type, name, arguments) \
47     static type& name = *new type arguments
48 #endif
49 #endif
50
51 // Use this macro to declare and define a debug-only global variable that may have a
52 // non-trivial constructor and destructor. When building with clang, this will suppress
53 // warnings about global constructors and exit-time destructors.
54 #define DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments) \
55     _Pragma("clang diagnostic push") \
56     _Pragma("clang diagnostic ignored \"-Wglobal-constructors\"") \
57     _Pragma("clang diagnostic ignored \"-Wexit-time-destructors\"") \
58     static type name arguments; \
59     _Pragma("clang diagnostic pop")
60
61 #ifndef NDEBUG
62 #if COMPILER(CLANG)
63 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments)
64 #else
65 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
66     static type name arguments;
67 #endif // COMPILER(CLANG)
68 #else
69 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments)
70 #endif // NDEBUG
71
72 // OBJECT_OFFSETOF: Like the C++ offsetof macro, but you can use it with classes.
73 // The magic number 0x4000 is insignificant. We use it to avoid using NULL, since
74 // NULL can cause compiler problems, especially in cases of multiple inheritance.
75 #define OBJECT_OFFSETOF(class, field) (reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<class*>(0x4000)->field)) - 0x4000)
76
77 // STRINGIZE: Can convert any value to quoted string, even expandable macros
78 #define STRINGIZE(exp) #exp
79 #define STRINGIZE_VALUE_OF(exp) STRINGIZE(exp)
80
81 /*
82  * The reinterpret_cast<Type1*>([pointer to Type2]) expressions - where
83  * sizeof(Type1) > sizeof(Type2) - cause the following warning on ARM with GCC:
84  * increases required alignment of target type.
85  *
86  * An implicit or an extra static_cast<void*> bypasses the warning.
87  * For more info see the following bugzilla entries:
88  * - https://bugs.webkit.org/show_bug.cgi?id=38045
89  * - http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43976
90  */
91 #if (CPU(ARM) || CPU(MIPS)) && COMPILER(GCC)
92 template<typename Type>
93 inline bool isPointerTypeAlignmentOkay(Type* ptr)
94 {
95     return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
96 }
97
98 template<typename TypePtr>
99 inline TypePtr reinterpret_cast_ptr(void* ptr)
100 {
101     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
102     return reinterpret_cast<TypePtr>(ptr);
103 }
104
105 template<typename TypePtr>
106 inline TypePtr reinterpret_cast_ptr(const void* ptr)
107 {
108     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
109     return reinterpret_cast<TypePtr>(ptr);
110 }
111 #else
112 template<typename Type>
113 inline bool isPointerTypeAlignmentOkay(Type*)
114 {
115     return true;
116 }
117 #define reinterpret_cast_ptr reinterpret_cast
118 #endif
119
120 namespace WTF {
121
122 template<typename T>
123 ALWAYS_INLINE typename std::remove_reference<T>::type&& move(T&& value)
124 {
125     static_assert(std::is_lvalue_reference<T>::value, "T is not an lvalue reference; move() is unnecessary.");
126
127     using NonRefQualifiedType = typename std::remove_reference<T>::type;
128     static_assert(!std::is_const<NonRefQualifiedType>::value, "T is const qualified.");
129     return std::move(value);
130 }
131
132 static const size_t KB = 1024;
133 static const size_t MB = 1024 * 1024;
134
135 inline bool isPointerAligned(void* p)
136 {
137     return !((intptr_t)(p) & (sizeof(char*) - 1));
138 }
139
140 inline bool is8ByteAligned(void* p)
141 {
142     return !((uintptr_t)(p) & (sizeof(double) - 1));
143 }
144
145 /*
146  * C++'s idea of a reinterpret_cast lacks sufficient cojones.
147  */
148 template<typename ToType, typename FromType>
149 inline ToType bitwise_cast(FromType from)
150 {
151     static_assert(sizeof(FromType) == sizeof(ToType), "bitwise_cast size of FromType and ToType must be equal!");
152     union {
153         FromType from;
154         ToType to;
155     } u;
156     u.from = from;
157     return u.to;
158 }
159
160 template<typename ToType, typename FromType>
161 inline ToType safeCast(FromType value)
162 {
163     ASSERT(isInBounds<ToType>(value));
164     return static_cast<ToType>(value);
165 }
166
167 // Returns a count of the number of bits set in 'bits'.
168 inline size_t bitCount(unsigned bits)
169 {
170     bits = bits - ((bits >> 1) & 0x55555555);
171     bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
172     return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
173 }
174
175 inline size_t bitCount(uint64_t bits)
176 {
177     return bitCount(static_cast<unsigned>(bits)) + bitCount(static_cast<unsigned>(bits >> 32));
178 }
179
180 // Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array.
181 template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size];
182 // GCC needs some help to deduce a 0 length array.
183 #if COMPILER(GCC)
184 template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0];
185 #endif
186 #define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array))
187
188 // Efficient implementation that takes advantage of powers of two.
189 inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
190 {
191     ASSERT(divisor && !(divisor & (divisor - 1)));
192     size_t remainderMask = divisor - 1;
193     return (x + remainderMask) & ~remainderMask;
194 }
195
196 template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x)
197 {
198     static_assert(divisor && !(divisor & (divisor - 1)), "divisor must be a power of two!");
199     return roundUpToMultipleOf(divisor, x);
200 }
201
202 enum BinarySearchMode {
203     KeyMustBePresentInArray,
204     KeyMightNotBePresentInArray,
205     ReturnAdjacentElementIfKeyIsNotPresent
206 };
207
208 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
209 inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
210 {
211     size_t offset = 0;
212     while (size > 1) {
213         size_t pos = (size - 1) >> 1;
214         KeyType val = extractKey(&array[offset + pos]);
215         
216         if (val == key)
217             return &array[offset + pos];
218         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
219         // chopping off the right hand half of the array.
220         if (key < val)
221             size = pos;
222         // Discard all values in the left hand half of the array, up to and including the item at pos.
223         else {
224             size -= (pos + 1);
225             offset += (pos + 1);
226         }
227
228         ASSERT(mode != KeyMustBePresentInArray || size);
229     }
230     
231     if (mode == KeyMightNotBePresentInArray && !size)
232         return 0;
233     
234     ArrayElementType* result = &array[offset];
235
236     if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
237         return 0;
238
239     if (mode == KeyMustBePresentInArray) {
240         ASSERT(size == 1);
241         ASSERT(key == extractKey(result));
242     }
243
244     return result;
245 }
246
247 // If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
248 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
249 inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
250 {
251     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
252 }
253
254 // Return zero if the element is not found.
255 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
256 inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
257 {
258     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
259 }
260
261 // Return the element that is either to the left, or the right, of where the element would have been found.
262 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
263 inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
264 {
265     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
266 }
267
268 // Variants of the above that use const.
269 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
270 inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
271 {
272     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
273 }
274 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
275 inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
276 {
277     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
278 }
279 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
280 inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
281 {
282     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
283 }
284
285 template<typename VectorType, typename ElementType>
286 inline void insertIntoBoundedVector(VectorType& vector, size_t size, const ElementType& element, size_t index)
287 {
288     for (size_t i = size; i-- > index + 1;)
289         vector[i] = vector[i - 1];
290     vector[index] = element;
291 }
292
293 // This is here instead of CompilationThread.h to prevent that header from being included
294 // everywhere. The fact that this method, and that header, exist outside of JSC is a bug.
295 // https://bugs.webkit.org/show_bug.cgi?id=131815
296 WTF_EXPORT_PRIVATE bool isCompilationThread();
297
298 } // namespace WTF
299
300 #if OS(WINCE)
301 // Windows CE CRT has does not implement bsearch().
302 inline void* wtf_bsearch(const void* key, const void* base, size_t count, size_t size, int (*compare)(const void *, const void *))
303 {
304     const char* first = static_cast<const char*>(base);
305
306     while (count) {
307         size_t pos = (count - 1) >> 1;
308         const char* item = first + pos * size;
309         int compareResult = compare(item, key);
310         if (!compareResult)
311             return const_cast<char*>(item);
312         if (compareResult < 0) {
313             count -= (pos + 1);
314             first += (pos + 1) * size;
315         } else
316             count = pos;
317     }
318
319     return 0;
320 }
321
322 #define bsearch(key, base, count, size, compare) wtf_bsearch(key, base, count, size, compare)
323 #endif
324
325 // This version of placement new omits a 0 check.
326 enum NotNullTag { NotNull };
327 inline void* operator new(size_t, NotNullTag, void* location)
328 {
329     ASSERT(location);
330     return location;
331 }
332
333 #if (COMPILER(GCC) && !COMPILER(CLANG) && !GCC_VERSION_AT_LEAST(4, 8, 1))
334
335 // Work-around for Pre-C++11 syntax in MSVC 2010, and prior as well as GCC < 4.8.1.
336 namespace std {
337     template<class T> struct is_trivially_destructible {
338         static const bool value = std::has_trivial_destructor<T>::value;
339     };
340 }
341 #endif
342
343 // This adds various C++14 features for versions of the STL that may not yet have them.
344 namespace std {
345 // MSVC 2013 supports std::make_unique already.
346 #if !defined(_MSC_VER) || _MSC_VER < 1800
347 template<class T> struct _Unique_if {
348     typedef unique_ptr<T> _Single_object;
349 };
350
351 template<class T> struct _Unique_if<T[]> {
352     typedef unique_ptr<T[]> _Unknown_bound;
353 };
354
355 template<class T, size_t N> struct _Unique_if<T[N]> {
356     typedef void _Known_bound;
357 };
358
359 template<class T, class... Args> inline typename _Unique_if<T>::_Single_object
360 make_unique(Args&&... args)
361 {
362     return unique_ptr<T>(new T(std::forward<Args>(args)...));
363 }
364
365 template<class T> inline typename _Unique_if<T>::_Unknown_bound
366 make_unique(size_t n)
367 {
368     typedef typename remove_extent<T>::type U;
369     return unique_ptr<T>(new U[n]());
370 }
371
372 template<class T, class... Args> typename _Unique_if<T>::_Known_bound
373 make_unique(Args&&...) = delete;
374 #endif
375
376 // Compile-time integer sequences
377 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3658.html
378 // (Note that we only implement index_sequence, and not the more generic integer_sequence).
379 template<size_t... indexes> struct index_sequence {
380     static size_t size() { return sizeof...(indexes); }
381 };
382
383 template<size_t currentIndex, size_t...indexes> struct make_index_sequence_helper;
384
385 template<size_t...indexes> struct make_index_sequence_helper<0, indexes...> {
386     typedef std::index_sequence<indexes...> type;
387 };
388
389 template<size_t currentIndex, size_t...indexes> struct make_index_sequence_helper {
390     typedef typename make_index_sequence_helper<currentIndex - 1, currentIndex - 1, indexes...>::type type;
391 };
392
393 template<size_t length> struct make_index_sequence : public make_index_sequence_helper<length>::type { };
394
395 #if COMPILER_SUPPORTS(CXX_USER_LITERALS)
396 // These literals are available in C++14, so once we require C++14 compilers we can get rid of them here.
397 // (User-literals need to have a leading underscore so we add it here - the "real" literals don't have underscores).
398 namespace literals {
399 namespace chrono_literals {
400     CONSTEXPR inline chrono::seconds operator"" _s(unsigned long long s)
401     {
402         return chrono::seconds(static_cast<chrono::seconds::rep>(s));
403     }
404
405     CONSTEXPR chrono::milliseconds operator"" _ms(unsigned long long ms)
406     {
407         return chrono::milliseconds(static_cast<chrono::milliseconds::rep>(ms));
408     }
409 }
410 }
411 #endif
412 }
413
414 using WTF::KB;
415 using WTF::MB;
416 using WTF::isCompilationThread;
417 using WTF::insertIntoBoundedVector;
418 using WTF::isPointerAligned;
419 using WTF::is8ByteAligned;
420 using WTF::binarySearch;
421 using WTF::tryBinarySearch;
422 using WTF::approximateBinarySearch;
423 using WTF::bitwise_cast;
424 using WTF::safeCast;
425
426 #if COMPILER_SUPPORTS(CXX_USER_LITERALS)
427 // We normally don't want to bring in entire std namespaces, but literals are an exception.
428 using namespace std::literals::chrono_literals;
429 #endif
430
431 #endif // WTF_StdLibExtras_h