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